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