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