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