Fix high interrupt ISRs
[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;
273     u64 *block_map, *mark_map, *meta_map;
274     int idx, longidx;
275     u64 bit, meta_bit, meta_mask;
276
277     if (!obj)
278         return;
279
280     base = OBJBASE(obj);
281     block_map = OBJCACHE_BLOCK_BMAP(base);
282     mark_map = OBJCACHE_MARK_BMAP(base);
283     meta_map = OBJCACHE_META_BMAP(base);
284
285     idx = OBJIDX(obj);
286     longidx = idx / 64;
287     bit = FIRST_BIT >> (idx % 64);
288
289     meta_bit = (FIRST_BIT >> longidx);
290     meta_mask = meta_bit - 1;
291
292     assert(obj == OBJCACHE_CELL(base, idx));
293     assert(block_map[longidx] & bit);
294
295     block_map[longidx] &= ~bit;
296     mark_map[longidx] |= bit;
297
298     /* Convert bit to mask of following bits in this longidx */
299     bit--;
300
301     /* If all of the following bits are also clear, see if we're free up to
302      * free_cells and update if possible
303      */
304
305     if ((block_map[longidx] & bit) == 0) {
306         if (block_map[longidx] == 0)
307             *meta_map &= ~meta_bit;
308
309         if (*meta_map == 0) {
310             objcache->free_cells = FREE_CELLS; // TODO: Free last_alloc
311         } else if ((*meta_map & meta_mask) == 0)
312             objcache->free_cells = FREE_CELLS - idx;
313     }
314 }
315
316 void *objcache_realloc(struct objcache *objcache, void *obj, u32 size)
317 {
318     void *base = OBJBASE(obj);
319     u64 *block_map = OBJCACHE_BLOCK_BMAP(base);
320     u64 *mark_map = OBJCACHE_MARK_BMAP(base);
321
322     int idx = OBJIDX(obj);
323     int longidx = idx / 64;
324     u64 bit = FIRST_BIT >> (idx % 64);
325
326     int cur_cells = 0;
327     void *ret;
328
329     if (obj) {
330         assert(obj == OBJCACHE_CELL(base, idx));
331         assert(block_map[longidx] & bit);
332
333         /* Figure out how big the current allocation is */
334         do {
335             cur_cells++;
336
337             idx++;
338             if (idx >= FREE_CELLS)
339                 break;
340             longidx = idx / 64;
341             bit = FIRST_BIT >> (idx % 64);
342
343         } while ((!(block_map[longidx] & bit))&&
344                 (!(mark_map[longidx] & bit)));
345     }
346
347     ret = objcache_get(objcache, size);
348     
349     if (!ret)
350         return NULL;
351
352     memcpy(ret, obj, cur_cells * OC_CELL_SIZE);
353
354     objcache_free(objcache, obj);
355
356     return ret;
357 }
358
359 void objcache_destroy(struct objcache *objcache)
360 {
361     u64 *cur = objcache->data;
362     u64 next;
363
364     while(cur) {
365         next = OBJCACHE_PTR_NEXT(cur);
366         page_alloc_free(cur);
367         cur = (u64 *) next;
368     }
369
370     objcache->data = NULL;
371 }
372
373 void objcache_init(struct objcache *objcache)
374 {
375     objcache->data = NULL;
376     objcache->last_alloc = NULL;
377     objcache->free_cells = 0;
378
379     spinlock_init(&objcache->lock, 0);
380 }
381
382 #ifdef TEST_OBJCACHE
383
384 DEFINE_OBJCACHE(test_cache);
385
386 /* Return the count of overhead pages allocated */
387
388 static int __objcache_pages(struct objcache *objcache)
389 {
390     void *pages = objcache->data;
391     int count = 0;
392
393     while(pages) {
394         count += (1 << ALLOC_ORDER);
395         pages = (void *) OBJCACHE_PTR_NEXT(pages);
396     }
397
398     return count;
399 }
400
401 void test_objcache(void)
402 {
403     /* Pretty much the only test of the objcache is that it can spit out memory
404      * chunks until we run out, and that it will free blocks that are totally
405      * empty on free.
406      */
407
408     void *a = NULL, *b = NULL;
409     u64 *meta;
410     int i;
411
412     assert(__objcache_pages(&test_cache) == 0);
413
414     /* Allocating 32 bytes, which means 2 cells, or 2016 possible allocations
415      * in a single 64k allocation.
416      */
417
418     for(i = 0; i < 2016; i++) {
419         b = a;
420         a = objcache_get(&test_cache, 32);
421
422         if (b)
423             assert(OBJBASE(a) == OBJBASE(b));
424
425         /* make sure a is after b, also NULL check */
426         assert((u64) a > (u64) b);
427
428         /* shouldn't have caused expansion */
429         assert(__objcache_pages(&test_cache) == (1 << ALLOC_ORDER));
430
431         /* should have set meta bitmap */
432         meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
433         assert(*meta & (FIRST_BIT >> (i / 64)));
434     }
435
436     /* The 2017th should cause expansion */
437     a = objcache_get(&test_cache, 32);
438
439     assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
440
441     /* 2015 more, shouldn't expand */
442     for(i = 0; i < 2015; i++)
443         objcache_get(&test_cache, 32);
444
445     assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
446
447     /* With a full objcache last_alloc, free some in the middle and make sure
448      * it will fallback on the bitmap if the bump allocator is at the end
449      * of an alloc, as well as checking the meta bitmap is correct
450      */
451
452     for (i = 32; i < 64; i++) {
453         /* Make sure that the meta bitmap is still set */
454         meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
455         assert(*meta & (FIRST_BIT >> 1));
456         objcache_free(&test_cache, OBJCACHE_CELL(test_cache.last_alloc, i * 2));
457     }
458
459     /* After last free, meta bitmap should be unset */
460     meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
461     assert(!(*meta & (FIRST_BIT >> 1)));
462
463     for (i = 32; i < 64; i++) {
464         assert(objcache_get(&test_cache, 32) == OBJCACHE_CELL(test_cache.last_alloc, i * 2));
465         assert(__objcache_pages(&test_cache) == (2 << ALLOC_ORDER));
466     }
467
468     a = objcache_get(&test_cache, 32);
469
470     assert(__objcache_pages(&test_cache) == (3 << ALLOC_ORDER));
471
472     meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
473     assert(*meta == FIRST_BIT);
474
475     objcache_free(&test_cache, a);
476
477     meta = OBJCACHE_META_BMAP(test_cache.last_alloc);
478     assert(*meta == 0x0);
479
480     //assert(__objcache_pages(&test_cache) == 2);
481
482     /* Test destroy and clean up after our tests */
483     objcache_destroy(&test_cache);
484
485     assert(__objcache_pages(&test_cache) == 0);
486 }
487 #endif