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