slab: Bootstrap before setting up kpages_arena
[akaros.git] / kern / src / slab.c
1 /* Copyright (c) 2009 The Regents of the University of California
2  * Copyright (c) 2016 Google Inc
3  * Barret Rhoden <brho@cs.berkeley.edu>
4  * Kevin Klues <klueska@cs.berkeley.edu>
5  * See LICENSE for details.
6  *
7  * Slab allocator, based on the SunOS 5.4 allocator paper.
8  */
9
10 #include <slab.h>
11 #include <stdio.h>
12 #include <assert.h>
13 #include <pmap.h>
14 #include <kmalloc.h>
15 #include <hash.h>
16 #include <arena.h>
17
18 struct kmem_cache_list kmem_caches = SLIST_HEAD_INITIALIZER(kmem_caches);
19 spinlock_t kmem_caches_lock = SPINLOCK_INITIALIZER_IRQSAVE;
20
21 /* Backend/internal functions, defined later.  Grab the lock before calling
22  * these. */
23 static bool kmem_cache_grow(struct kmem_cache *cp);
24
25 /* Cache of the kmem_cache objects, needed for bootstrapping */
26 struct kmem_cache kmem_cache_cache[1];
27 struct kmem_cache kmem_slab_cache[1];
28 struct kmem_cache kmem_bufctl_cache[1];
29
30 static bool __use_bufctls(struct kmem_cache *cp)
31 {
32         return cp->flags & __KMC_USE_BUFCTL;
33 }
34
35 void __kmem_cache_create(struct kmem_cache *kc, const char *name,
36                          size_t obj_size, int align, int flags,
37                          struct arena *source,
38                          void (*ctor)(void *, size_t),
39                          void (*dtor)(void *, size_t))
40 {
41         assert(kc);
42         assert(align);
43         spinlock_init_irqsave(&kc->cache_lock);
44         strlcpy(kc->name, name, KMC_NAME_SZ);
45         kc->obj_size = obj_size;
46         /* TODO: when we are used from a qcache, we'll have a flag that tells us how
47          * to set this to interact with the arena nicely. */
48         kc->import_amt = ROUNDUP(NUM_BUF_PER_SLAB * ROUNDUP(obj_size, align),
49                                  PGSIZE);
50         kc->align = align;
51         if (align > PGSIZE)
52                 panic("Cache %s object alignment is actually MIN(PGSIZE, align (%p))",
53                       name, align);
54         kc->flags = flags;
55         /* We might want some sort of per-call site NUMA-awareness in the future. */
56         kc->source = source ? source : kpages_arena;
57         TAILQ_INIT(&kc->full_slab_list);
58         TAILQ_INIT(&kc->partial_slab_list);
59         TAILQ_INIT(&kc->empty_slab_list);
60         kc->ctor = ctor;
61         kc->dtor = dtor;
62         kc->nr_cur_alloc = 0;
63         kc->alloc_hash = kc->static_hash;
64         hash_init_hh(&kc->hh);
65         for (int i = 0; i < kc->hh.nr_hash_lists; i++)
66                 BSD_LIST_INIT(&kc->static_hash[i]);
67         /* No touch must use bufctls, even for small objects, so that it does not
68          * use the object as memory.  Note that if we have an arbitrary source,
69          * small objects, and we're 'pro-touch', the small allocation path will
70          * assume we're importing from a PGSIZE-aligned source arena. */
71         if ((obj_size > SLAB_LARGE_CUTOFF) || (flags & KMC_NOTOUCH))
72                 kc->flags |= __KMC_USE_BUFCTL;
73         /* put in cache list based on it's size */
74         struct kmem_cache *i, *prev = NULL;
75         spin_lock_irqsave(&kmem_caches_lock);
76         /* find the kmem_cache before us in the list.  yes, this is O(n). */
77         SLIST_FOREACH(i, &kmem_caches, link) {
78                 if (i->obj_size < kc->obj_size)
79                         prev = i;
80                 else
81                         break;
82         }
83         if (prev)
84                 SLIST_INSERT_AFTER(prev, kc, link);
85         else
86                 SLIST_INSERT_HEAD(&kmem_caches, kc, link);
87         spin_unlock_irqsave(&kmem_caches_lock);
88 }
89
90 void kmem_cache_init(void)
91 {
92         __kmem_cache_create(kmem_cache_cache, "kmem_cache",
93                             sizeof(struct kmem_cache),
94                             __alignof__(struct kmem_cache), 0, base_arena,
95                             NULL, NULL);
96         __kmem_cache_create(kmem_slab_cache, "kmem_slab",
97                             sizeof(struct kmem_slab),
98                             __alignof__(struct kmem_slab), 0, base_arena,
99                             NULL, NULL);
100         __kmem_cache_create(kmem_bufctl_cache, "kmem_bufctl",
101                             sizeof(struct kmem_bufctl),
102                             __alignof__(struct kmem_bufctl), 0, base_arena,
103                             NULL, NULL);
104 }
105
106 /* Cache management */
107 struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
108                                      int align, int flags,
109                                      struct arena *source,
110                                      void (*ctor)(void *, size_t),
111                                      void (*dtor)(void *, size_t))
112 {
113         struct kmem_cache *kc = kmem_cache_alloc(kmem_cache_cache, 0);
114         __kmem_cache_create(kc, name, obj_size, align, flags, source, ctor, dtor);
115         return kc;
116 }
117
118 static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
119 {
120         if (!__use_bufctls(cp)) {
121                 /* Deconstruct all the objects, if necessary */
122                 if (cp->dtor) {
123                         void *buf = a_slab->free_small_obj;
124                         for (int i = 0; i < a_slab->num_total_obj; i++) {
125                                 cp->dtor(buf, cp->obj_size);
126                                 buf += a_slab->obj_size;
127                         }
128                 }
129                 arena_free(cp->source, ROUNDDOWN(a_slab, PGSIZE), PGSIZE);
130         } else {
131                 struct kmem_bufctl *i, *temp;
132                 void *buf_start = (void*)SIZE_MAX;
133
134                 BSD_LIST_FOREACH_SAFE(i, &a_slab->bufctl_freelist, link, temp) {
135                         // Track the lowest buffer address, which is the start of the buffer
136                         buf_start = MIN(buf_start, i->buf_addr);
137                         /* Deconstruct all the objects, if necessary */
138                         if (cp->dtor)
139                                 cp->dtor(i->buf_addr, cp->obj_size);
140                         /* This is a little dangerous, but we can skip removing, since we
141                          * init the freelist when we reuse the slab. */
142                         kmem_cache_free(kmem_bufctl_cache, i);
143                 }
144                 arena_free(cp->source, buf_start, cp->import_amt);
145                 kmem_cache_free(kmem_slab_cache, a_slab);
146         }
147 }
148
149 /* Once you call destroy, never use this cache again... o/w there may be weird
150  * races, and other serious issues.  */
151 void kmem_cache_destroy(struct kmem_cache *cp)
152 {
153         struct kmem_slab *a_slab, *next;
154
155         spin_lock_irqsave(&cp->cache_lock);
156         assert(TAILQ_EMPTY(&cp->full_slab_list));
157         assert(TAILQ_EMPTY(&cp->partial_slab_list));
158         /* Clean out the empty list.  We can't use a regular FOREACH here, since the
159          * link element is stored in the slab struct, which is stored on the page
160          * that we are freeing. */
161         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
162         while (a_slab) {
163                 next = TAILQ_NEXT(a_slab, link);
164                 kmem_slab_destroy(cp, a_slab);
165                 a_slab = next;
166         }
167         spin_lock_irqsave(&kmem_caches_lock);
168         SLIST_REMOVE(&kmem_caches, cp, kmem_cache, link);
169         spin_unlock_irqsave(&kmem_caches_lock);
170         kmem_cache_free(kmem_cache_cache, cp);
171         spin_unlock_irqsave(&cp->cache_lock);
172 }
173
174 static void __try_hash_resize(struct kmem_cache *cp)
175 {
176         struct kmem_bufctl_list *new_tbl, *old_tbl;
177         struct kmem_bufctl *bc_i;
178         unsigned int new_tbl_nr_lists, old_tbl_nr_lists;
179         size_t new_tbl_sz, old_tbl_sz;
180         size_t hash_idx;
181
182         if (!hash_needs_more(&cp->hh))
183                 return;
184         new_tbl_nr_lists = hash_next_nr_lists(&cp->hh);
185         new_tbl_sz = new_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
186         /* TODO: we only need to pull from base if our arena is a base or we are
187          * inside a kpages arena (keep in mind there could be more than one of
188          * those, depending on how we do NUMA allocs).  This might help with
189          * fragmentation.  To know this, we'll need the caller to pass us a flag. */
190         new_tbl = base_zalloc(NULL, new_tbl_sz, ARENA_INSTANTFIT | MEM_ATOMIC);
191         if (!new_tbl)
192                 return;
193         old_tbl = cp->alloc_hash;
194         old_tbl_nr_lists = cp->hh.nr_hash_lists;
195         old_tbl_sz = old_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
196         cp->alloc_hash = new_tbl;
197         hash_incr_nr_lists(&cp->hh);
198         for (int i = 0; i < old_tbl_nr_lists; i++) {
199                 while ((bc_i = BSD_LIST_FIRST(&old_tbl[i]))) {
200                         BSD_LIST_REMOVE(bc_i, link);
201                         hash_idx = hash_ptr(bc_i->buf_addr, cp->hh.nr_hash_bits);
202                         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc_i, link);
203                 }
204         }
205         hash_reset_load_limit(&cp->hh);
206         if (old_tbl != cp->static_hash)
207                 base_free(NULL, old_tbl, old_tbl_sz);
208 }
209
210 /* Helper, tracks the allocation of @bc in the hash table */
211 static void __track_alloc(struct kmem_cache *cp, struct kmem_bufctl *bc)
212 {
213         size_t hash_idx;
214
215         hash_idx = hash_ptr(bc->buf_addr, cp->hh.nr_hash_bits);
216         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc, link);
217         cp->hh.nr_items++;
218         __try_hash_resize(cp);
219 }
220
221 /* Helper, looks up and removes the bufctl corresponding to buf. */
222 static struct kmem_bufctl *__yank_bufctl(struct kmem_cache *cp, void *buf)
223 {
224         struct kmem_bufctl *bc_i;
225         size_t hash_idx;
226
227         hash_idx = hash_ptr(buf, cp->hh.nr_hash_bits);
228         BSD_LIST_FOREACH(bc_i, &cp->alloc_hash[hash_idx], link) {
229                 if (bc_i->buf_addr == buf) {
230                         BSD_LIST_REMOVE(bc_i, link);
231                         break;
232                 }
233         }
234         if (!bc_i)
235                 panic("Could not find buf %p in cache %s!", buf, cp->name);
236         return bc_i;
237 }
238
239 /* Front end: clients of caches use these */
240 void *kmem_cache_alloc(struct kmem_cache *cp, int flags)
241 {
242         void *retval = NULL;
243         spin_lock_irqsave(&cp->cache_lock);
244         // look at partial list
245         struct kmem_slab *a_slab = TAILQ_FIRST(&cp->partial_slab_list);
246         //      if none, go to empty list and get an empty and make it partial
247         if (!a_slab) {
248                 // TODO: think about non-sleeping flags
249                 if (TAILQ_EMPTY(&cp->empty_slab_list) &&
250                         !kmem_cache_grow(cp)) {
251                         spin_unlock_irqsave(&cp->cache_lock);
252                         if (flags & MEM_ERROR)
253                                 error(ENOMEM, ERROR_FIXME);
254                         else
255                                 panic("[German Accent]: OOM for a small slab growth!!!");
256                 }
257                 // move to partial list
258                 a_slab = TAILQ_FIRST(&cp->empty_slab_list);
259                 TAILQ_REMOVE(&cp->empty_slab_list, a_slab, link);
260                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
261         }
262         // have a partial now (a_slab), get an item, return item
263         if (!__use_bufctls(cp)) {
264                 retval = a_slab->free_small_obj;
265                 /* adding the size of the cache_obj to get to the pointer at end of the
266                  * buffer pointing to the next free_small_obj */
267                 a_slab->free_small_obj = *(uintptr_t**)(a_slab->free_small_obj +
268                                                         cp->obj_size);
269         } else {
270                 // rip the first bufctl out of the partial slab's buf list
271                 struct kmem_bufctl *a_bufctl = BSD_LIST_FIRST(&a_slab->bufctl_freelist);
272
273                 BSD_LIST_REMOVE(a_bufctl, link);
274                 __track_alloc(cp, a_bufctl);
275                 retval = a_bufctl->buf_addr;
276         }
277         a_slab->num_busy_obj++;
278         // Check if we are full, if so, move to the full list
279         if (a_slab->num_busy_obj == a_slab->num_total_obj) {
280                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
281                 TAILQ_INSERT_HEAD(&cp->full_slab_list, a_slab, link);
282         }
283         cp->nr_cur_alloc++;
284         spin_unlock_irqsave(&cp->cache_lock);
285         return retval;
286 }
287
288 void kmem_cache_free(struct kmem_cache *cp, void *buf)
289 {
290         struct kmem_slab *a_slab;
291         struct kmem_bufctl *a_bufctl;
292
293         spin_lock_irqsave(&cp->cache_lock);
294         if (!__use_bufctls(cp)) {
295                 // find its slab
296                 a_slab = (struct kmem_slab*)(ROUNDDOWN((uintptr_t)buf, PGSIZE) +
297                                              PGSIZE - sizeof(struct kmem_slab));
298                 /* write location of next free small obj to the space at the end of the
299                  * buffer, then list buf as the next free small obj */
300                 *(uintptr_t**)(buf + cp->obj_size) = a_slab->free_small_obj;
301                 a_slab->free_small_obj = buf;
302         } else {
303                 /* Give the bufctl back to the parent slab */
304                 a_bufctl = __yank_bufctl(cp, buf);
305                 a_slab = a_bufctl->my_slab;
306                 BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
307         }
308         a_slab->num_busy_obj--;
309         cp->nr_cur_alloc--;
310         // if it was full, move it to partial
311         if (a_slab->num_busy_obj + 1 == a_slab->num_total_obj) {
312                 TAILQ_REMOVE(&cp->full_slab_list, a_slab, link);
313                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
314         } else if (!a_slab->num_busy_obj) {
315                 // if there are none, move to from partial to empty
316                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
317                 TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
318         }
319         spin_unlock_irqsave(&cp->cache_lock);
320 }
321
322 /* Back end: internal functions */
323 /* When this returns, the cache has at least one slab in the empty list.  If
324  * page_alloc fails, there are some serious issues.  This only grows by one slab
325  * at a time.
326  *
327  * Grab the cache lock before calling this.
328  *
329  * TODO: think about page colouring issues with kernel memory allocation. */
330 static bool kmem_cache_grow(struct kmem_cache *cp)
331 {
332         struct kmem_slab *a_slab;
333         struct kmem_bufctl *a_bufctl;
334
335         if (!__use_bufctls(cp)) {
336                 void *a_page;
337
338                 /* Careful, this assumes our source is a PGSIZE-aligned allocator.  We
339                  * could use xalloc to enforce the alignment, but that'll bypass the
340                  * qcaches, which we don't want.  Caller beware. */
341                 a_page = arena_alloc(cp->source, PGSIZE, MEM_ATOMIC);
342                 if (!a_page)
343                         return FALSE;
344                 // the slab struct is stored at the end of the page
345                 a_slab = (struct kmem_slab*)(a_page + PGSIZE
346                                              - sizeof(struct kmem_slab));
347                 // Need to add room for the next free item pointer in the object buffer.
348                 a_slab->obj_size = ROUNDUP(cp->obj_size + sizeof(uintptr_t), cp->align);
349                 a_slab->num_busy_obj = 0;
350                 a_slab->num_total_obj = (PGSIZE - sizeof(struct kmem_slab)) /
351                                         a_slab->obj_size;
352                 // TODO: consider staggering this IAW section 4.3
353                 a_slab->free_small_obj = a_page;
354                 /* Walk and create the free list, which is circular.  Each item stores
355                  * the location of the next one at the end of the block. */
356                 void *buf = a_slab->free_small_obj;
357                 for (int i = 0; i < a_slab->num_total_obj - 1; i++) {
358                         // Initialize the object, if necessary
359                         if (cp->ctor)
360                                 cp->ctor(buf, cp->obj_size);
361                         *(uintptr_t**)(buf + cp->obj_size) = buf + a_slab->obj_size;
362                         buf += a_slab->obj_size;
363                 }
364                 *((uintptr_t**)(buf + cp->obj_size)) = NULL;
365         } else {
366                 void *buf;
367
368                 a_slab = kmem_cache_alloc(kmem_slab_cache, 0);
369                 if (!a_slab)
370                         return FALSE;
371                 a_slab->obj_size = ROUNDUP(cp->obj_size, cp->align);
372                 buf = arena_alloc(cp->source, cp->import_amt, MEM_ATOMIC);
373                 if (!buf) {
374                         kmem_cache_free(kmem_slab_cache, a_slab);
375                         return FALSE;
376                 }
377                 a_slab->num_busy_obj = 0;
378                 a_slab->num_total_obj = cp->import_amt / a_slab->obj_size;
379                 BSD_LIST_INIT(&a_slab->bufctl_freelist);
380                 /* for each buffer, set up a bufctl and point to the buffer */
381                 for (int i = 0; i < a_slab->num_total_obj; i++) {
382                         // Initialize the object, if necessary
383                         if (cp->ctor)
384                                 cp->ctor(buf, cp->obj_size);
385                         a_bufctl = kmem_cache_alloc(kmem_bufctl_cache, 0);
386                         BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
387                         a_bufctl->buf_addr = buf;
388                         a_bufctl->my_slab = a_slab;
389                         buf += a_slab->obj_size;
390                 }
391         }
392         // add a_slab to the empty_list
393         TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
394
395         return TRUE;
396 }
397
398 /* This deallocs every slab from the empty list.  TODO: think a bit more about
399  * this.  We can do things like not free all of the empty lists to prevent
400  * thrashing.  See 3.4 in the paper. */
401 void kmem_cache_reap(struct kmem_cache *cp)
402 {
403         struct kmem_slab *a_slab, *next;
404
405         // Destroy all empty slabs.  Refer to the notes about the while loop
406         spin_lock_irqsave(&cp->cache_lock);
407         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
408         while (a_slab) {
409                 next = TAILQ_NEXT(a_slab, link);
410                 kmem_slab_destroy(cp, a_slab);
411                 a_slab = next;
412         }
413         spin_unlock_irqsave(&cp->cache_lock);
414 }
415
416 void print_kmem_cache(struct kmem_cache *cp)
417 {
418         spin_lock_irqsave(&cp->cache_lock);
419         printk("\nPrinting kmem_cache:\n---------------------\n");
420         printk("Name: %s\n", cp->name);
421         printk("Objsize: %d\n", cp->obj_size);
422         printk("Align: %d\n", cp->align);
423         printk("Flags: 0x%08x\n", cp->flags);
424         printk("Constructor: %p\n", cp->ctor);
425         printk("Destructor: %p\n", cp->dtor);
426         printk("Slab Full: %p\n", cp->full_slab_list);
427         printk("Slab Partial: %p\n", cp->partial_slab_list);
428         printk("Slab Empty: %p\n", cp->empty_slab_list);
429         printk("Current Allocations: %d\n", cp->nr_cur_alloc);
430         spin_unlock_irqsave(&cp->cache_lock);
431 }
432
433 void print_kmem_slab(struct kmem_slab *slab)
434 {
435         printk("\nPrinting kmem_slab:\n---------------------\n");
436         printk("Objsize: %d (%p)\n", slab->obj_size, slab->obj_size);
437         printk("NumBusy: %d\n", slab->num_busy_obj);
438         printk("Num_total: %d\n", slab->num_total_obj);
439         /* This will break if we have a NOTOUCH small slab.  It's debugging code, so
440          * just be careful. */
441         if (slab->obj_size + sizeof(uintptr_t) < SLAB_LARGE_CUTOFF) {
442                 printk("Free Small obj: %p\n", slab->free_small_obj);
443                 void *buf = slab->free_small_obj;
444                 for (int i = 0; i < slab->num_total_obj; i++) {
445                         printk("Addr of buf: %p, Addr of next: %p\n", buf,
446                                *((uintptr_t**)buf));
447                         buf += slab->obj_size;
448                 }
449         } else {
450                 printk("This is a big slab!\n");
451         }
452 }
453