slab: Remove obj_size from struct kmem_slab
[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 static void *__kmem_alloc_from_slab(struct kmem_cache *cp, int flags);
25 static void __kmem_free_to_slab(struct kmem_cache *cp, void *buf);
26
27 /* Cache of the kmem_cache objects, needed for bootstrapping */
28 struct kmem_cache kmem_cache_cache[1];
29 struct kmem_cache kmem_slab_cache[1];
30 struct kmem_cache kmem_bufctl_cache[1];
31
32 static bool __use_bufctls(struct kmem_cache *cp)
33 {
34         return cp->flags & __KMC_USE_BUFCTL;
35 }
36
37 void __kmem_cache_create(struct kmem_cache *kc, const char *name,
38                          size_t obj_size, int align, int flags,
39                          struct arena *source,
40                          void (*ctor)(void *, size_t),
41                          void (*dtor)(void *, size_t))
42 {
43         assert(kc);
44         assert(align);
45         spinlock_init_irqsave(&kc->cache_lock);
46         strlcpy(kc->name, name, KMC_NAME_SZ);
47         kc->obj_size = ROUNDUP(obj_size, align);
48         if (flags & KMC_QCACHE)
49                 kc->import_amt = ROUNDUPPWR2(3 * source->qcache_max);
50         else
51                 kc->import_amt = ROUNDUP(NUM_BUF_PER_SLAB * obj_size, PGSIZE);
52         kc->align = align;
53         if (align > PGSIZE)
54                 panic("Cache %s object alignment is actually MIN(PGSIZE, align (%p))",
55                       name, align);
56         kc->flags = flags;
57         /* We might want some sort of per-call site NUMA-awareness in the future. */
58         kc->source = source ? source : kpages_arena;
59         TAILQ_INIT(&kc->full_slab_list);
60         TAILQ_INIT(&kc->partial_slab_list);
61         TAILQ_INIT(&kc->empty_slab_list);
62         kc->ctor = ctor;
63         kc->dtor = dtor;
64         kc->nr_cur_alloc = 0;
65         kc->alloc_hash = kc->static_hash;
66         hash_init_hh(&kc->hh);
67         for (int i = 0; i < kc->hh.nr_hash_lists; i++)
68                 BSD_LIST_INIT(&kc->static_hash[i]);
69         /* No touch must use bufctls, even for small objects, so that it does not
70          * use the object as memory.  Note that if we have an arbitrary source,
71          * small objects, and we're 'pro-touch', the small allocation path will
72          * assume we're importing from a PGSIZE-aligned source arena. */
73         if ((obj_size > SLAB_LARGE_CUTOFF) || (flags & KMC_NOTOUCH))
74                 kc->flags |= __KMC_USE_BUFCTL;
75         /* put in cache list based on it's size */
76         struct kmem_cache *i, *prev = NULL;
77         spin_lock_irqsave(&kmem_caches_lock);
78         /* find the kmem_cache before us in the list.  yes, this is O(n). */
79         SLIST_FOREACH(i, &kmem_caches, link) {
80                 if (i->obj_size < kc->obj_size)
81                         prev = i;
82                 else
83                         break;
84         }
85         if (prev)
86                 SLIST_INSERT_AFTER(prev, kc, link);
87         else
88                 SLIST_INSERT_HEAD(&kmem_caches, kc, link);
89         spin_unlock_irqsave(&kmem_caches_lock);
90 }
91
92 void kmem_cache_init(void)
93 {
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                 arena_free(cp->source, ROUNDDOWN(a_slab, PGSIZE), PGSIZE);
124         } else {
125                 struct kmem_bufctl *i, *temp;
126                 void *buf_start = (void*)SIZE_MAX;
127
128                 BSD_LIST_FOREACH_SAFE(i, &a_slab->bufctl_freelist, link, temp) {
129                         // Track the lowest buffer address, which is the start of the buffer
130                         buf_start = MIN(buf_start, i->buf_addr);
131                         /* This is a little dangerous, but we can skip removing, since we
132                          * init the freelist when we reuse the slab. */
133                         kmem_cache_free(kmem_bufctl_cache, i);
134                 }
135                 arena_free(cp->source, buf_start, cp->import_amt);
136                 kmem_cache_free(kmem_slab_cache, a_slab);
137         }
138 }
139
140 /* Once you call destroy, never use this cache again... o/w there may be weird
141  * races, and other serious issues.  */
142 void kmem_cache_destroy(struct kmem_cache *cp)
143 {
144         struct kmem_slab *a_slab, *next;
145
146         spin_lock_irqsave(&cp->cache_lock);
147         assert(TAILQ_EMPTY(&cp->full_slab_list));
148         assert(TAILQ_EMPTY(&cp->partial_slab_list));
149         /* Clean out the empty list.  We can't use a regular FOREACH here, since the
150          * link element is stored in the slab struct, which is stored on the page
151          * that we are freeing. */
152         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
153         while (a_slab) {
154                 next = TAILQ_NEXT(a_slab, link);
155                 kmem_slab_destroy(cp, a_slab);
156                 a_slab = next;
157         }
158         spin_lock_irqsave(&kmem_caches_lock);
159         SLIST_REMOVE(&kmem_caches, cp, kmem_cache, link);
160         spin_unlock_irqsave(&kmem_caches_lock);
161         kmem_cache_free(kmem_cache_cache, cp);
162         spin_unlock_irqsave(&cp->cache_lock);
163 }
164
165 static void __try_hash_resize(struct kmem_cache *cp)
166 {
167         struct kmem_bufctl_list *new_tbl, *old_tbl;
168         struct kmem_bufctl *bc_i;
169         unsigned int new_tbl_nr_lists, old_tbl_nr_lists;
170         size_t new_tbl_sz, old_tbl_sz;
171         size_t hash_idx;
172
173         if (!hash_needs_more(&cp->hh))
174                 return;
175         new_tbl_nr_lists = hash_next_nr_lists(&cp->hh);
176         new_tbl_sz = new_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
177         /* TODO: we only need to pull from base if our arena is a base or we are
178          * inside a kpages arena (keep in mind there could be more than one of
179          * those, depending on how we do NUMA allocs).  This might help with
180          * fragmentation.  To know this, we'll need the caller to pass us a flag. */
181         new_tbl = base_zalloc(NULL, new_tbl_sz, ARENA_INSTANTFIT | MEM_ATOMIC);
182         if (!new_tbl)
183                 return;
184         old_tbl = cp->alloc_hash;
185         old_tbl_nr_lists = cp->hh.nr_hash_lists;
186         old_tbl_sz = old_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
187         cp->alloc_hash = new_tbl;
188         hash_incr_nr_lists(&cp->hh);
189         for (int i = 0; i < old_tbl_nr_lists; i++) {
190                 while ((bc_i = BSD_LIST_FIRST(&old_tbl[i]))) {
191                         BSD_LIST_REMOVE(bc_i, link);
192                         hash_idx = hash_ptr(bc_i->buf_addr, cp->hh.nr_hash_bits);
193                         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc_i, link);
194                 }
195         }
196         hash_reset_load_limit(&cp->hh);
197         if (old_tbl != cp->static_hash)
198                 base_free(NULL, old_tbl, old_tbl_sz);
199 }
200
201 /* Helper, tracks the allocation of @bc in the hash table */
202 static void __track_alloc(struct kmem_cache *cp, struct kmem_bufctl *bc)
203 {
204         size_t hash_idx;
205
206         hash_idx = hash_ptr(bc->buf_addr, cp->hh.nr_hash_bits);
207         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc, link);
208         cp->hh.nr_items++;
209         __try_hash_resize(cp);
210 }
211
212 /* Helper, looks up and removes the bufctl corresponding to buf. */
213 static struct kmem_bufctl *__yank_bufctl(struct kmem_cache *cp, void *buf)
214 {
215         struct kmem_bufctl *bc_i;
216         size_t hash_idx;
217
218         hash_idx = hash_ptr(buf, cp->hh.nr_hash_bits);
219         BSD_LIST_FOREACH(bc_i, &cp->alloc_hash[hash_idx], link) {
220                 if (bc_i->buf_addr == buf) {
221                         BSD_LIST_REMOVE(bc_i, link);
222                         break;
223                 }
224         }
225         if (!bc_i)
226                 panic("Could not find buf %p in cache %s!", buf, cp->name);
227         return bc_i;
228 }
229
230 /* Alloc, bypassing the magazines and depot */
231 static void *__kmem_alloc_from_slab(struct kmem_cache *cp, int flags)
232 {
233         void *retval = NULL;
234         spin_lock_irqsave(&cp->cache_lock);
235         // look at partial list
236         struct kmem_slab *a_slab = TAILQ_FIRST(&cp->partial_slab_list);
237         //      if none, go to empty list and get an empty and make it partial
238         if (!a_slab) {
239                 // TODO: think about non-sleeping flags
240                 if (TAILQ_EMPTY(&cp->empty_slab_list) &&
241                         !kmem_cache_grow(cp)) {
242                         spin_unlock_irqsave(&cp->cache_lock);
243                         if (flags & MEM_ERROR)
244                                 error(ENOMEM, ERROR_FIXME);
245                         else
246                                 panic("[German Accent]: OOM for a small slab growth!!!");
247                 }
248                 // move to partial list
249                 a_slab = TAILQ_FIRST(&cp->empty_slab_list);
250                 TAILQ_REMOVE(&cp->empty_slab_list, a_slab, link);
251                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
252         }
253         // have a partial now (a_slab), get an item, return item
254         if (!__use_bufctls(cp)) {
255                 retval = a_slab->free_small_obj;
256                 /* the next free_small_obj address is stored at the beginning of the
257                  * current free_small_obj. */
258                 a_slab->free_small_obj = *(uintptr_t**)(a_slab->free_small_obj);
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         if (cp->ctor)
276                 cp->ctor(retval, cp->obj_size);
277         return retval;
278 }
279
280 void *kmem_cache_alloc(struct kmem_cache *cp, int flags)
281 {
282         return __kmem_alloc_from_slab(cp, flags);
283 }
284
285 /* Returns an object to the slab layer.  Note that objects in the slabs are
286  * unconstructed. */
287 static void __kmem_free_to_slab(struct kmem_cache *cp, void *buf)
288 {
289         struct kmem_slab *a_slab;
290         struct kmem_bufctl *a_bufctl;
291
292         if (cp->dtor)
293                 cp->dtor(buf, cp->obj_size);
294         spin_lock_irqsave(&cp->cache_lock);
295         if (!__use_bufctls(cp)) {
296                 // find its slab
297                 a_slab = (struct kmem_slab*)(ROUNDDOWN((uintptr_t)buf, PGSIZE) +
298                                              PGSIZE - sizeof(struct kmem_slab));
299                 /* write location of next free small obj to the space at the beginning
300                  * of the buffer, then list buf as the next free small obj */
301                 *(uintptr_t**)buf = a_slab->free_small_obj;
302                 a_slab->free_small_obj = buf;
303         } else {
304                 /* Give the bufctl back to the parent slab */
305                 a_bufctl = __yank_bufctl(cp, buf);
306                 a_slab = a_bufctl->my_slab;
307                 BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
308         }
309         a_slab->num_busy_obj--;
310         cp->nr_cur_alloc--;
311         // if it was full, move it to partial
312         if (a_slab->num_busy_obj + 1 == a_slab->num_total_obj) {
313                 TAILQ_REMOVE(&cp->full_slab_list, a_slab, link);
314                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
315         } else if (!a_slab->num_busy_obj) {
316                 // if there are none, move to from partial to empty
317                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
318                 TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
319         }
320         spin_unlock_irqsave(&cp->cache_lock);
321 }
322
323 void kmem_cache_free(struct kmem_cache *cp, void *buf)
324 {
325         __kmem_free_to_slab(cp, buf);
326 }
327
328 /* Back end: internal functions */
329 /* When this returns, the cache has at least one slab in the empty list.  If
330  * page_alloc fails, there are some serious issues.  This only grows by one slab
331  * at a time.
332  *
333  * Grab the cache lock before calling this.
334  *
335  * TODO: think about page colouring issues with kernel memory allocation. */
336 static bool kmem_cache_grow(struct kmem_cache *cp)
337 {
338         struct kmem_slab *a_slab;
339         struct kmem_bufctl *a_bufctl;
340
341         if (!__use_bufctls(cp)) {
342                 void *a_page;
343
344                 /* Careful, this assumes our source is a PGSIZE-aligned allocator.  We
345                  * could use xalloc to enforce the alignment, but that'll bypass the
346                  * qcaches, which we don't want.  Caller beware. */
347                 a_page = arena_alloc(cp->source, PGSIZE, MEM_ATOMIC);
348                 if (!a_page)
349                         return FALSE;
350                 // the slab struct is stored at the end of the page
351                 a_slab = (struct kmem_slab*)(a_page + PGSIZE
352                                              - sizeof(struct kmem_slab));
353                 a_slab->num_busy_obj = 0;
354                 a_slab->num_total_obj = (PGSIZE - sizeof(struct kmem_slab)) /
355                                         cp->obj_size;
356                 // TODO: consider staggering this IAW section 4.3
357                 a_slab->free_small_obj = a_page;
358                 /* Walk and create the free list, which is circular.  Each item stores
359                  * the location of the next one at the beginning of the block. */
360                 void *buf = a_slab->free_small_obj;
361                 for (int i = 0; i < a_slab->num_total_obj - 1; i++) {
362                         *(uintptr_t**)buf = buf + cp->obj_size;
363                         buf += cp->obj_size;
364                 }
365                 *((uintptr_t**)buf) = NULL;
366         } else {
367                 void *buf;
368
369                 a_slab = kmem_cache_alloc(kmem_slab_cache, 0);
370                 if (!a_slab)
371                         return FALSE;
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 / cp->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                         a_bufctl = kmem_cache_alloc(kmem_bufctl_cache, 0);
383                         BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
384                         a_bufctl->buf_addr = buf;
385                         a_bufctl->my_slab = a_slab;
386                         buf += cp->obj_size;
387                 }
388         }
389         // add a_slab to the empty_list
390         TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
391
392         return TRUE;
393 }
394
395 /* This deallocs every slab from the empty list.  TODO: think a bit more about
396  * this.  We can do things like not free all of the empty lists to prevent
397  * thrashing.  See 3.4 in the paper. */
398 void kmem_cache_reap(struct kmem_cache *cp)
399 {
400         struct kmem_slab *a_slab, *next;
401
402         // Destroy all empty slabs.  Refer to the notes about the while loop
403         spin_lock_irqsave(&cp->cache_lock);
404         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
405         while (a_slab) {
406                 next = TAILQ_NEXT(a_slab, link);
407                 kmem_slab_destroy(cp, a_slab);
408                 a_slab = next;
409         }
410         spin_unlock_irqsave(&cp->cache_lock);
411 }
412
413 void print_kmem_cache(struct kmem_cache *cp)
414 {
415         spin_lock_irqsave(&cp->cache_lock);
416         printk("\nPrinting kmem_cache:\n---------------------\n");
417         printk("Name: %s\n", cp->name);
418         printk("Objsize (incl align): %d\n", cp->obj_size);
419         printk("Align: %d\n", cp->align);
420         printk("Flags: 0x%08x\n", cp->flags);
421         printk("Constructor: %p\n", cp->ctor);
422         printk("Destructor: %p\n", cp->dtor);
423         printk("Slab Full: %p\n", cp->full_slab_list);
424         printk("Slab Partial: %p\n", cp->partial_slab_list);
425         printk("Slab Empty: %p\n", cp->empty_slab_list);
426         printk("Current Allocations: %d\n", cp->nr_cur_alloc);
427         spin_unlock_irqsave(&cp->cache_lock);
428 }