Embed ISRs at known address
[viridis.git] / mm / objcache.c
1 /* vim: set ts=4 sw=4 sts=4 et : */
2
3 /* Objcache is an implementation of a localized general memory allocator */
4
5 /* Where the domain allocator is designed to deal with arbitrary sized
6  * allocations over huge ranges of numbers, the objcache is designed to
7  * efficiently pack small(ish) objects into pages with as little overhead as
8  * possible.
9  *
10  * This design was inspired by the "arena" concept planned by Mike Pall for the
11  * LuaJIT 3.0 GC. As of yet, that code hasn't landed (4/16), but the concept
12  * was pretty clear.
13  *
14  * An "arena" is a big virtually contiguous allocation of at least 64k and is
15  * comprised of 16 byte cells, which can be combined together to accomodate any
16  * reasonable allocation size. For each of these cells, you carry two bits of
17  * metadata. So in 64k you have (64k/16) = 4096 cells, and thus 8192 bits / 1k
18  * of overhead total.
19  *
20  * The 64k minimum is well chosen too, because at 64k you have enough overhead
21  * that you can assume the first (1/64th overhead of 4096 bits) = 64 bits of
22  * each bitmap is always used, which means that memory can be used for
23  * something else, like a couple of full pointers.
24  *
25  * In the mark bitmap, a garbage collector white / black is stored for each
26  * block. We don't have a GC yet, but we're planning that most of the objects
27  * in the objcache are going to be tracked by the GC eventually.
28  *
29  * In the block bitmap marks the start of each block.
30  *
31  * Block : 1 0 0 | 0 0 | 1 0
32  * Mark  : 0 0 0 | 1 0 | 1 0
33  *
34  * This translates to a white block that's three cells long, two free cells,
35  * and then a black block that's two cells long.
36  *
37  * When you allocate one of those free cells, you mark the block bit and unset
38  * the color mark bit (converting from a free block to a white block) for the
39  * initial cell and then, unless it was a perfect fit, you just set the mark
40  * bit for the first cell after your allocation. 2 or 3 writes total, without
41  * having to touch the intermediate blocks.
42  *
43  * The neat aspect of this is that you can use bit logic to operate on these
44  * many at a time, which will come in handy when we need to do stuff like
45  *
46  * Free all white objects
47  *
48  * B'=M&B  : 0 0 0 | 0 0 | 1 0 (unset all white blocks)
49  * M'=M|B  : 1 0 0 | 1 0 | 1 0 (mark all free - or set black bit again)
50  *
51  * switch all black objects to white objects at the end of a GC sweep.
52  *
53  * Block : 0 0 0 | 0 0 | 1 0
54  * M=B^M : 1 0 0 | 1 0 | 0 0 (color flips, others untouched)
55  *
56  * Anyway, even without a GC yet, this provides some benefits over our initial
57  * objcache implementation which had a variable size bitmap based on a single
58  * object size and would become inefficient with bigger allocation sizes.
59  */
60
61 #include <kernel.h>
62 #include <objcache.h>
63
64 #define ALLOC_ORDER             4 /* 64k */
65 #define ALLOC_SIZE              (1ULL << (PAGE_SHIFT + ALLOC_ORDER))
66 #define ALLOC_MASK              (ALLOC_SIZE - 1)
67 #define BASE_MASK               ~(ALLOC_MASK)
68
69 #define TOTAL_CELLS             (ALLOC_SIZE / OC_CELL_SIZE)
70
71 /* 2 bits per object, mark and block, expressed in different ways */
72 #define OVERHEAD_BITS           (2 * TOTAL_CELLS)
73 #define OVERHEAD_BYTES          (OVERHEAD_BITS / 8)
74 #define OVERHEAD_LONGS          (OVERHEAD_BYTES / 8)
75 #define OVERHEAD_CELLS          (OVERHEAD_BYTES / OC_CELL_SIZE)
76 #define FREE_CELLS              (TOTAL_CELLS - OVERHEAD_CELLS)
77 #define OBJCACHE_MAXSIZE        (FREE_CELLS * OC_CELL_SIZE)
78
79 /* Assert that we can store meta bitmap information in 8 bytes */
80 STATIC_ASSERT((FREE_CELLS / 64) <= 64);
81
82 /* How many bytes of the bitmap can we assume are taken by metadata */
83 #define SKIP_BYTES              (OVERHEAD_CELLS / 8)
84
85 /* Given a base allocation pointer, locate various overhead structures */
86
87 /* Yes, this is basically half-assed struct building, but eventually there will
88  * per-objcache allocation order, and these will have to be derived anyway
89  */
90
91 #define OBJCACHE_PTR_NEXT(x)    ((u64 *) (x))[0]
92 #define OBJCACHE_BLOCK_BMAP(x)  ((u64 *) &((u8 *)(x))[SKIP_BYTES])
93 #define OBJCACHE_META_BMAP(x)   ((u64 *) &((u8 *)(x))[OVERHEAD_BYTES / 2])
94 #define OBJCACHE_MARK_BMAP(x)   ((u64 *) &((u8 *)(x))[(OVERHEAD_BYTES / 2) + SKIP_BYTES])
95 #define OBJCACHE_BMAP_SIZE      ((OVERHEAD_LONGS / 2) - 1) /* To avoid the pointer at the head */
96
97 #define FIRST_BIT (1UL << 63)
98
99 /* Macros for finding base / idx from object pointer */
100 #define OBJBASE(x)              ((void *) (((u64) (x)) & BASE_MASK))
101
102 /* Macros to convert between idx and object. Note that the bitmap doesn't
103  * include the cells we ignore (and use for our pointer) so idx 0 is the first
104  * cell *after* our overhead, this is the only place we need to adjust for that
105  * fact.
106  */
107
108 #define OBJIDX(x)               (((((u64) (x)) & ALLOC_MASK) >> ALLOC_ORDER) - OVERHEAD_CELLS)
109 #define OBJCACHE_CELL(x, n)     ((void *) &((u8 *)(x))[OC_CELL_SIZE * (n + OVERHEAD_CELLS)])
110
111 static int __oc_find_free_cells(struct objcache *objcache, u32 cells, void **alloc)
112 {
113     u64 *mark_map, *block_map, *meta_map;
114     u64 curbit;
115
116     s32 free_start = -1;
117     u32 free_here = 0;
118
119     int i, j;
120
121     *alloc = objcache->data;
122
123     while (*alloc) {
124         block_map = (u64 *) OBJCACHE_BLOCK_BMAP(*alloc);
125         mark_map = (u64 *) OBJCACHE_MARK_BMAP(*alloc);
126         meta_map = (u64 *) OBJCACHE_META_BMAP(*alloc);
127
128         if (*meta_map == 0)
129             return 0;
130
131         for(i = 0; i < OBJCACHE_BMAP_SIZE; i++) {
132             curbit = FIRST_BIT;
133
134             for(j = 0; j < 64; j++) {
135                 if (*block_map & curbit)
136                     free_start = -1;
137                 else if (*mark_map & curbit) {
138                     if (free_start >= 0) /* Merge free blocks */
139                         *mark_map &= ~(curbit);
140                     else {
141                         free_start = ((i * 64) + j);
142                         free_here = 1;
143                     }
144                 } else if(free_start >= 0)
145                     free_here++;
146
147                 if (free_here >= cells)
148                     return free_start;
149
150                 curbit >>= 1;
151             }
152
153             block_map++;
154             mark_map++;
155         }
156
157         *alloc = (void *) OBJCACHE_PTR_NEXT(*alloc);
158     }
159
160     return -1;
161 }
162
163 static int __oc_bump_allocation(struct objcache *objcache)
164 {
165     u64 *new_pages = page_alloc(ALLOC_ORDER);
166     u64 *mark_map, *block_map;
167     int i;
168
169     if (!new_pages)
170         return -1;
171
172     /* Init bitmap and next ptr */
173
174     OBJCACHE_PTR_NEXT(new_pages) = 0x0;
175     *OBJCACHE_META_BMAP(new_pages) = 0x0;
176
177     mark_map = (u64 *) OBJCACHE_MARK_BMAP(new_pages);
178     block_map = (u64 *) OBJCACHE_BLOCK_BMAP(new_pages);
179
180     for (i = 0; i <= OBJCACHE_BMAP_SIZE; i++) {
181         block_map[i] = 0x0;
182         mark_map[i] = 0x0;
183     }
184
185     /* Start with a free block definition, mark = 1, block = 0 */
186     mark_map[0] = FIRST_BIT;
187
188     if (!objcache->data)
189         objcache->data = new_pages;
190     else
191         OBJCACHE_PTR_NEXT(objcache->last_alloc) = (u64) new_pages;
192
193     objcache->last_alloc = new_pages;
194     objcache->free_cells = FREE_CELLS;
195     return 0;
196 }
197
198 void *objcache_get(struct objcache *objcache, u32 size)
199 {
200     u64 *page;
201     u64 *mark_map, *block_map, *meta_map;
202     u64 longidx, metabit;
203     int idx;
204     void *ret;
205
206     if ((!size) || (size > OBJCACHE_MAXSIZE))
207         return NULL;
208
209     /* Convert size from bytes to cells */
210     size = (size + (OC_CELL_SIZE - 1)) / OC_CELL_SIZE;
211
212     if (size <= objcache->free_cells) {
213         idx = FREE_CELLS - objcache->free_cells;
214         page = objcache->last_alloc;
215         objcache->free_cells -= size;
216     } else {
217         idx = __oc_find_free_cells(objcache, size, (void **) &page);
218
219         if (idx == -1) {
220             if (__oc_bump_allocation(objcache))
221                 return NULL;
222             page = objcache->last_alloc;
223             objcache->free_cells -= size;
224             idx = 0;
225         }
226     }
227
228     block_map = OBJCACHE_BLOCK_BMAP(page);
229     mark_map = OBJCACHE_MARK_BMAP(page);
230     meta_map = OBJCACHE_META_BMAP(page);
231
232     ret = OBJCACHE_CELL(page, idx);
233
234     longidx = idx / 64;
235     metabit = FIRST_BIT >> longidx;
236
237     /* Turn this index into a white block */
238     block_map[longidx] |= (FIRST_BIT >> (idx % 64));
239     mark_map[longidx] &= ~(FIRST_BIT >> (idx % 64));
240     *meta_map |= metabit;
241
242     /* If there's a following block and it's free, turn it into a free header */
243
244     idx += size;
245
246     if (idx >= FREE_CELLS)
247         return ret;
248
249     if (!(block_map[idx / 64] & (FIRST_BIT >> (idx % 64))))
250         mark_map[idx / 64] |= (FIRST_BIT >> (idx % 64));
251
252     return ret;
253 }
254
255 /*
256 static int __oc_alloc_empty(u64 * page)
257 {
258     u64 *bmap = OBJCACHE_BLOCK_BMAP(page);
259     int i;
260
261     for (i = 0; i < OBJCACHE_BMAP_SIZE; i++) {
262         if (bmap[i] != 0)
263             return 0;
264     }
265
266     return 1;
267 }
268 */
269
270 void objcache_free(struct objcache *objcache, void *obj)
271 {
272     void *base = OBJBASE(obj);
273     u64 *block_map = OBJCACHE_BLOCK_BMAP(base);
274     u64 *mark_map = OBJCACHE_MARK_BMAP(base);
275     u64 *meta_map = OBJCACHE_META_BMAP(base);
276
277     int idx = OBJIDX(obj);
278     int longidx = idx / 64;
279     u64 bit = FIRST_BIT >> (idx % 64);
280
281     u64 meta_bit = (FIRST_BIT >> longidx);
282     u64 meta_mask = meta_bit - 1;
283
284     assert(obj == OBJCACHE_CELL(base, idx));
285     assert(block_map[longidx] & bit);
286
287     block_map[longidx] &= ~bit;
288     mark_map[longidx] |= bit;
289
290     /* Convert bit to mask of following bits in this longidx */
291     bit--;
292
293     /* If all of the following bits are also clear, see if we're free up to
294      * free_cells and update if possible
295      */
296
297     if ((block_map[longidx] & bit) == 0) {
298         if (block_map[longidx] == 0)
299             *meta_map &= ~meta_bit;
300
301         if (*meta_map == 0) {
302             objcache->free_cells = FREE_CELLS; // TODO: Free last_alloc
303         } else if ((*meta_map & meta_mask) == 0)
304             objcache->free_cells = FREE_CELLS - idx;
305     }
306 }
307
308 void objcache_destroy(struct objcache *objcache)
309 {
310     u64 *cur = objcache->data;
311     u64 next;
312
313     while(cur) {
314         next = OBJCACHE_PTR_NEXT(cur);
315         page_alloc_free(cur);
316         cur = (u64 *) next;
317     }
318
319     objcache->data = NULL;
320 }
321
322 void objcache_init(struct objcache *objcache)
323 {
324     objcache->data = NULL;
325     objcache->last_alloc = NULL;
326     objcache->free_cells = 0;
327
328     spinlock_init(&objcache->lock, 0);
329 }
330
331 #ifdef TEST_OBJCACHE
332
333 DEFINE_OBJCACHE(test_cache);
334
335 /* Return the count of overhead pages allocated */
336
337 static int __objcache_pages(struct objcache *objcache)
338 {
339     void *pages = objcache->data;
340     int count = 0;
341
342     while(pages) {
343         count += (1 << ALLOC_ORDER);
344         pages = (void *) OBJCACHE_PTR_NEXT(pages);
345     }
346
347     return count;
348 }
349
350 void test_objcache(void)
351 {
352     /* Pretty much the only test of the objcache is that it can spit out memory
353      * chunks until we run out, and that it will free blocks that are totally
354      * empty on free.
355      */
356
357     void *a = NULL, *b = NULL;
358     u64 *meta;
359     int i;
360
361     assert(__objcache_pages(&test_cache) == 0);
362
363     /* Allocating 32 bytes, which means 2 cells, or 2016 possible allocations
364      * in a single 64k allocation.
365      */
366
367     for(i = 0; i < 2016; i++) {
368         b = a;
369         a = objcache_get(&test_cache, 32);
370
371         if (b)
372             assert(OBJBASE(a) == OBJBASE(b));
373
374         /* make sure a is after b, also NULL check */
375         assert((u64) a > (u64) b);
376
377         /* shouldn't have caused expansion */
378         assert(__objcache_pages(&test_cache) == (1 << ALLOC_ORDER));
379
380         /* should have set meta bitmap */
381         meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
382         assert(*meta & (FIRST_BIT >> (i / 64)));
383     }
384
385     /* The 2017th should cause expansion */
386     a = objcache_get(&test_cache, 32);
387
388     assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
389
390     /* 2015 more, shouldn't expand */
391     for(i = 0; i < 2015; i++)
392         objcache_get(&test_cache, 32);
393
394     assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
395
396     /* With a full objcache last_alloc, free some in the middle and make sure
397      * it will fallback on the bitmap if the bump allocator is at the end
398      * of an alloc, as well as checking the meta bitmap is correct
399      */
400
401     for (i = 32; i < 64; i++) {
402         /* Make sure that the meta bitmap is still set */
403         meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
404         assert(*meta & (FIRST_BIT >> 1));
405         objcache_free(&test_cache, OBJCACHE_CELL(test_cache.last_alloc, i * 2));
406     }
407
408     /* After last free, meta bitmap should be unset */
409     meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
410     assert(!(*meta & (FIRST_BIT >> 1)));
411
412     for (i = 32; i < 64; i++) {
413         assert(objcache_get(&test_cache, 32) == OBJCACHE_CELL(test_cache.last_alloc, i * 2));
414         assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
415     }
416
417     a = objcache_get(&test_cache, 32);
418
419     assert(__objcache_pages(&test_cache) == (3 << ALLOC_ORDER));
420
421     meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
422     assert(*meta == FIRST_BIT);
423
424     objcache_free(&test_cache, a);
425
426     meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
427     assert(*meta == 0x0);
428
429     //assert(__objcache_pages(&test_cache) == 2);
430
431     /* Test destroy and clean up after our tests */
432     objcache_destroy(&test_cache);
433
434     assert(__objcache_pages(&test_cache) == 0);
435 }
436 #endif