1#include <compiler/core.h>
2#include <compiler/intrinsic.h>
3#include <math/align.h>
4#include <math/bit.h>
5#include <math/range.h>
6#include <math/units.h>
7#include <mem/asan.h>
8#include <mem/hhdm.h>
9#include <mem/pmm.h>
10#include <mem/vas.h>
11
12#include "internal.h"
13
14static inline uintptr_t vaddr_to_base_addr(vaddr_t vaddr) {
15 return ct_raw(vaddr) >> PAGE_4K_SHIFT;
16}
17
18static inline vaddr_t base_addr_to_vaddr(uintptr_t base_addr) {
19 return (vaddr_t) (base_addr << PAGE_4K_SHIFT);
20}
21
22static void validate_ptr_in_chunk(struct slab_chunk *chunk, void *ptr) {
23 vaddr_t vaddr = (vaddr_t) ptr;
24 vaddr_t min = base_addr_to_vaddr(base_addr: chunk->base_addr);
25 vaddr_t max = base_addr_to_vaddr(base_addr: chunk->base_addr) + SLAB_CHUNK_SIZE;
26 enforce(IN_RANGE(vaddr, min, max));
27}
28
29static struct list_head *chunk_list_for(struct slab_chunks *sc,
30 enum slab_chunk_state s) {
31 switch (s) {
32 case SLAB_CHUNK_PARTIAL: return &sc->partial_list;
33 case SLAB_CHUNK_USED: return &sc->used_list;
34 default: unreachable("invalid slab chunk state");
35 }
36}
37
38static void destroy_chunk(struct slab_chunks *sc, struct slab_chunk *c) {
39 vaddr_t vaddr = base_addr_to_vaddr(base_addr: c->base_addr);
40 uint8_t curr = slab_order_map_get(addr: vaddr);
41 enforce(curr != SLAB_POW2_ORDER_EMPTY);
42
43#ifdef DEBUG_ASAN
44 asan_free((void *) vaddr, SLAB_CHUNK_SIZE);
45 asan_shadow_release(vaddr, SLAB_CHUNK_SIZE);
46#endif
47
48 vas_free(vas: slab_global.vas, addr: vaddr, PAGE_2MB);
49 slab_order_map_set(addr: vaddr, SLAB_POW2_ORDER_EMPTY);
50
51 fixed_size_free(fsr: &sc->fsr, obj: c);
52}
53
54static bool move_to(struct slab_chunks *sc, struct slab_chunk *c,
55 enum slab_chunk_state s) {
56 enforce(c->state != s);
57 list_node_delete_init(n: &c->list);
58 if (s == SLAB_CHUNK_FREE) {
59 destroy_chunk(sc, c);
60 return true;
61 }
62 c->state = s;
63 list_head_push_back(h: chunk_list_for(sc, s), n: &c->list);
64 return false;
65}
66
67static struct slab_chunk *alloc_chunk(struct slab_chunks *sc,
68 enum irql *lirql) TSA_NO_ANALYSIS {
69 vaddr_t base = vas_alloc(vas: slab_global.vas, PAGE_2MB, PAGE_2MB);
70
71 if (!base)
72 return NULL;
73
74 uint8_t curr = slab_order_map_get(addr: base);
75 enforce(curr == SLAB_POW2_ORDER_EMPTY);
76 slab_order_map_set(addr: base, order: sc->pow2_order);
77
78 spin_unlock(&sc->lock, *lirql);
79 struct slab_chunk *ret = fixed_size_alloc(fsr: &sc->fsr);
80
81#ifdef DEBUG_ASAN
82 /* We have to do this here as the shadow must exist before alloc */
83 if (ret && asan_shadow_install(base, SLAB_CHUNK_SIZE) < 0) {
84 fixed_size_free(&sc->fsr, ret);
85 ret = NULL;
86 }
87#endif
88
89 *lirql = spin_lock(&sc->lock);
90
91 if (!ret) {
92 slab_order_map_set(addr: base, SLAB_POW2_ORDER_EMPTY);
93 vas_free(vas: slab_global.vas, addr: base, PAGE_2MB);
94 return NULL;
95 }
96
97 list_node_init(n: &ret->list);
98 ret->owner = sc;
99 ret->state = SLAB_CHUNK_PARTIAL;
100 ret->base_addr = vaddr_to_base_addr(vaddr: base);
101 ret->used = 0;
102 memset(ret->bitmap, 0, sc->bitmap_bytes);
103 list_head_push_back(h: &sc->partial_list, n: &ret->list);
104 return ret;
105}
106
107static vaddr_t alloc_from(struct slab_chunks *chunks,
108 struct slab_chunk *chunk) {
109 uint64_t *bm = (uint64_t *) chunk->bitmap;
110 size_t nwords = DIV_ROUND_UP(chunks->bitmap_bits, sizeof(uint64_t) * 8);
111
112 for (size_t w = 0; w < nwords; w++) {
113 if (bm[w] != UINT64_MAX) {
114 uint64_t free_bits = ~bm[w];
115 uint64_t bit = ci_ctzll(free_bits);
116 uint64_t i = w * 64 + bit;
117
118 if (i >= chunks->bitmap_bits)
119 break;
120
121 SLAB_BITMAP_SET(bm[w], BIT(bit));
122 chunk->used++;
123
124 return base_addr_to_vaddr(base_addr: chunk->base_addr) +
125 i * chunks->page_stride * PAGE_SIZE;
126 }
127 }
128
129 unreachable("alloc_from slab chunk should not fail");
130}
131
132static void free_to(struct slab_chunks *chunks, struct slab_chunk *chunk,
133 vaddr_t v) {
134 validate_ptr_in_chunk(chunk, ptr: (void *) v);
135 uint64_t offset = v - base_addr_to_vaddr(base_addr: chunk->base_addr);
136 enforce(offset % (PAGE_SIZE * chunks->page_stride) == 0);
137 uint64_t i = offset / (PAGE_SIZE * chunks->page_stride);
138
139 uint64_t *bm = (uint64_t *) chunk->bitmap;
140 enforce(i < chunks->bitmap_bits);
141
142 size_t w = i / 64;
143 size_t b = i % 64;
144 enforce(SLAB_BITMAP_TEST(bm[w], BIT(b)), BAD_FREE);
145 SLAB_BITMAP_UNSET(bm[w], BIT(b));
146 chunk->used--;
147}
148
149static vaddr_t chunk_alloc(struct slab_chunks *chunks,
150 struct slab_chunk *chunk) {
151 size_t max = chunks->bitmap_bits;
152 vaddr_t ret = alloc_from(chunks, chunk);
153 if (chunk->used == max)
154 move_to(sc: chunks, c: chunk, s: SLAB_CHUNK_USED);
155
156 return ret;
157}
158
159static bool chunk_free(struct slab_chunks *chunks, struct slab_chunk *chunk,
160 vaddr_t v) {
161 enum slab_chunk_state last = chunk->state;
162 enforce(last != SLAB_CHUNK_FREE);
163 free_to(chunks, chunk, v);
164
165 if (last == SLAB_CHUNK_USED) {
166 move_to(sc: chunks, c: chunk, s: SLAB_CHUNK_PARTIAL);
167 } else if (chunk->used == 0) {
168 return move_to(sc: chunks, c: chunk, s: SLAB_CHUNK_FREE);
169 }
170
171 return false;
172}
173
174/* Peek but do not pop, since chunk_alloc will re-link a chunk when it fills */
175static struct slab_chunk *try_peek(struct list_head *lh) {
176 struct list_node *peek = list_head_peek_front(h: lh);
177 if (!peek)
178 return NULL;
179
180 return container_of(peek, struct slab_chunk, list);
181}
182
183vaddr_t slab_chunks_alloc(struct slab_chunks *sc, struct slab_chunk **out) {
184 vaddr_t ret = 0x0;
185 enum irql irql = spin_lock(&sc->lock);
186
187 *out = try_peek(lh: &sc->partial_list);
188 if (!*out) {
189 if (!(*out = alloc_chunk(sc, lirql: &irql)))
190 goto out;
191 }
192
193 ret = chunk_alloc(chunks: sc, chunk: *out);
194
195out:
196 spin_unlock(&sc->lock, irql);
197 return ret;
198}
199
200void slab_chunks_free(struct slab_chunks *sc, struct slab_chunk *chunk,
201 vaddr_t addr) {
202 enum irql irql = spin_lock(&sc->lock);
203
204 chunk_free(chunks: sc, chunk, v: addr);
205
206 spin_unlock(&sc->lock, irql);
207}
208
209void slab_chunks_init(struct slab_chunks *sc, struct slab_cache *parent) {
210 sc->parent = parent;
211 sc->page_stride = next_pow2(x: parent->pages_per_slab);
212 size_t page_count = BIT(PAGE_2M_SHIFT - PAGE_4K_SHIFT);
213
214 /* Bytes rounded up to whole 64 bit words since bitmap is that width,
215 * bits stay the real slot count, because that is different */
216 sc->bitmap_bits = DIV_ROUND_UP(page_count, sc->page_stride);
217 sc->bitmap_bytes = SLAB_BITMAP_BYTES_FOR(sc->bitmap_bits);
218 list_head_init(h: &sc->partial_list);
219 list_head_init(h: &sc->used_list);
220
221 spinlock_init(&sc->lock);
222 sc->pow2_order = ilog2(x: sc->page_stride);
223
224 struct fixed_size_range_attributes attrs = {
225 .obj_size = sizeof(struct slab_chunk) + sc->bitmap_bytes,
226 .obj_align = cc_alignof(struct slab_chunk),
227 .init_obj = NULL,
228 .deinit_obj = NULL,
229 .bootstrap_mode = false,
230 };
231 fixed_size_range_init(fsr: &sc->fsr, attrs: &attrs);
232}
233