arena: Connecting importers with sources
[akaros.git] / kern / src / slab.c
1 /* Copyright (c) 2009 The Regents of the University of California
2  * See LICENSE for details.
3  *
4  * Slab allocator, based on the SunOS 5.4 allocator paper.
5  *
6  * Barret Rhoden <brho@cs.berkeley.edu>
7  * Kevin Klues <klueska@cs.berkeley.edu>
8  *
9  * Copyright (c) 2016 Google Inc
10  *
11  * Upgraded and extended to support magazines, based on Bonwick and Adams's
12  * "Magazines and Vmem" paper.
13  *
14  * Barret Rhoden <brho@cs.berkeley.edu>
15  *
16  * FAQ:
17  * - What sort of allocator do we need for the kmem_pcpu_caches?  In general,
18  *   the base allocator.  All slabs/caches depend on the pcpu_caches for any
19  *   allocation, so we need something that does not rely on slabs.  We could use
20  *   generic kpages, if we knew that we weren't: qcaches for a kpages_arena, the
21  *   slab kcache, or the bufctl kcache.  This is the same set of restrictions
22  *   for the hash table allocations.
23  * - Why doesn't the magazine cache deadlock on itself?  Because magazines are
24  *   only allocated during the free path of another cache.  There are no
25  *   magazine allocations during a cache's allocation.
26  * - Does the magazine cache need to be statically allocated?  Maybe not, but it
27  *   doesn't hurt.  We need to set it up at some point.  We can use other caches
28  *   for allocations before the mag cache is initialized, but we can't free.
29  * - Does the magazine cache need to pull from the base arena?  Similar to the
30  *   static allocation question - by default, maybe not, but it is safer.  And
31  *   yes, due to other design choices.  We could initialize it after kpages is
32  *   allocated and use a kpages_arena, but that would require us to not free a
33  *   page before or during kpages_arena_init().  A related note is where the
34  *   first magazines in a pcpu_cache come from.  I'm currently going with "raw
35  *   slab alloc from the magazine cache", which means magazines need to work
36  *   when we're setting up the qcache's for kpages_arena.  That creates a
37  *   dependency, which means kpages depends on mags, which means mags can only
38  *   depend on base.  If we ever use slabs for non-base arena btags, we'll also
39  *   have this dependency between kpages and mags.
40  * - The paper talks about full and empty magazines.  Why does our code talk
41  *   about not_empty and empty?  The way we'll do our magazine resizing is to
42  *   just() increment the pcpu_cache's magsize.  Then we'll eventually start
43  *   filling the magazines to their new capacity (during frees, btw).  During
44  *   this time, a mag that was previously full will technically be not-empty,
45  *   but not full.  The correctness of the magazine code is still OK, I think,
46  *   since when they say 'full', they require 'not empty' in most cases.  In
47  *   short, 'not empty' is more accurate, though it makes sense to say 'full'
48  *   when explaining the basic idea for their paper.
49  * - Due to a resize, what happens when the depot gives a pcpu cache a magazine
50  *   with *more* rounds than ppc->magsize?  The allocation path doesn't care
51  *   about magsize - it just looks at nr_rounds.  So that's fine.  On the free
52  *   path, we might mistakenly think that a mag has no more room.  In that case,
53  *   we'll just hand it to the depot and it'll be a 'not-empty' mag.  Eventually
54  *   it'll get filled up, or it just won't matter.  'magsize' is basically an
55  *   instruction to the pcpu_cache: "fill to X, please."
56  * - Why is nr_rounds tracked in the magazine and not the pcpu cache?  The paper
57  *   uses the pcpu cache, but doesn't say whether or not the mag tracks it too.
58  *   We track it in the mag since not all mags have the same size (e.g.  during
59  *   a resize operation).  For performance (avoid an occasional cache miss), we
60  *   could consider tracking it in the pcpu_cache.  Might save a miss now and
61  *   then.
62  * - Why do we just disable IRQs for the pcpu_cache?  The paper explicitly talks
63  *   about using locks instead of disabling IRQs, since disabling IRQs can be
64  *   expensive.  First off, we only just disable IRQs when there's 1:1 core to
65  *   pcc.  If we were to use a spinlock, we'd be disabling IRQs anyway, since we
66  *   do allocations from IRQ context.  The other reason to lock is when changing
67  *   the pcpu state during a magazine resize.  I have two ways to do this: just
68  *   racily write and set pcc->magsize, or have the pcc's poll when they check
69  *   the depot during free.  Either approach doesn't require someone else to
70  *   grab a pcc lock.
71  *
72  * TODO:
73  * - Change the sigs of ctor/dtor, add reclaim function.
74  * - When resizing, do we want to go through the depot and consolidate
75  *   magazines?  (probably not a big deal.  maybe we'd deal with it when we
76  *   clean up our excess mags.)
77  * - Could do some working set tracking.  Like max/min over an interval, with
78  *   resetting (in the depot, used for reclaim and maybe aggressive freeing).
79  * - Debugging info
80  */
81
82 #include <slab.h>
83 #include <stdio.h>
84 #include <assert.h>
85 #include <pmap.h>
86 #include <kmalloc.h>
87 #include <hash.h>
88 #include <arena.h>
89
90 #define SLAB_POISON ((void*)0xdead1111)
91
92 /* Tunables.  I don't know which numbers to pick yet.  Maybe we play with it at
93  * runtime.  Though once a mag increases, it'll never decrease. */
94 uint64_t resize_timeout_ns = 1000000000;
95 unsigned int resize_threshold = 1;
96
97 struct kmem_cache_list kmem_caches = SLIST_HEAD_INITIALIZER(kmem_caches);
98 spinlock_t kmem_caches_lock = SPINLOCK_INITIALIZER_IRQSAVE;
99
100 /* Backend/internal functions, defined later.  Grab the lock before calling
101  * these. */
102 static bool kmem_cache_grow(struct kmem_cache *cp);
103 static void *__kmem_alloc_from_slab(struct kmem_cache *cp, int flags);
104 static void __kmem_free_to_slab(struct kmem_cache *cp, void *buf);
105
106 /* Cache of the kmem_cache objects, needed for bootstrapping */
107 struct kmem_cache kmem_cache_cache[1];
108 struct kmem_cache kmem_slab_cache[1];
109 struct kmem_cache kmem_bufctl_cache[1];
110 struct kmem_cache kmem_magazine_cache[1];
111
112 static bool __use_bufctls(struct kmem_cache *cp)
113 {
114         return cp->flags & __KMC_USE_BUFCTL;
115 }
116
117 /* Using a layer of indirection for the pcpu caches, in case we want to use
118  * clustered objects, only per-NUMA-domain caches, or something like that. */
119 unsigned int kmc_nr_pcpu_caches(void)
120 {
121         return num_cores;
122 }
123
124 static struct kmem_pcpu_cache *get_my_pcpu_cache(struct kmem_cache *kc)
125 {
126         return &kc->pcpu_caches[core_id()];
127 }
128
129 /* In our current model, there is one pcc per core.  If we had multiple cores
130  * that could use the pcc, such as with per-NUMA caches, then we'd need a
131  * spinlock.  Since we do allocations from IRQ context, we still need to disable
132  * IRQs. */
133 static void lock_pcu_cache(struct kmem_pcpu_cache *pcc)
134 {
135         disable_irqsave(&pcc->irq_state);
136 }
137
138 static void unlock_pcu_cache(struct kmem_pcpu_cache *pcc)
139 {
140         enable_irqsave(&pcc->irq_state);
141 }
142
143 static void lock_depot(struct kmem_depot *depot)
144 {
145         uint64_t time;
146
147         if (spin_trylock_irqsave(&depot->lock))
148                 return;
149         /* The lock is contended.  When we finally get the lock, we'll up the
150          * contention count and see if we've had too many contentions over time.
151          *
152          * The idea is that if there are bursts of contention worse than X contended
153          * acquisitions in Y nsec, then we'll grow the magazines.  This might not be
154          * that great of an approach - every thread gets one count, regardless of
155          * how long they take.
156          *
157          * We read the time before locking so that we don't artificially grow the
158          * window too much.  Say the lock is heavily contended and we take a long
159          * time to get it.  Perhaps X threads try to lock it immediately, but it
160          * takes over Y seconds for the Xth thread to actually get the lock.  We
161          * might then think the burst wasn't big enough. */
162         time = nsec();
163         spin_lock_irqsave(&depot->lock);
164         /* If there are no not-empty mags, we're probably fighting for the lock not
165          * because the magazines aren't big enough, but because there aren't enough
166          * mags in the system yet. */
167         if (!depot->nr_not_empty)
168                 return;
169         if (time - depot->busy_start > resize_timeout_ns) {
170                 depot->busy_count = 0;
171                 depot->busy_start = time;
172         }
173         depot->busy_count++;
174         if (depot->busy_count > resize_threshold) {
175                 depot->busy_count = 0;
176                 depot->magsize = MIN(KMC_MAG_MAX_SZ, depot->magsize + 1);
177                 /* That's all we do - the pccs will eventually notice and up their
178                  * magazine sizes. */
179         }
180 }
181
182 static void unlock_depot(struct kmem_depot *depot)
183 {
184         spin_unlock_irqsave(&depot->lock);
185 }
186
187 static void depot_init(struct kmem_depot *depot)
188 {
189         spinlock_init_irqsave(&depot->lock);
190         SLIST_INIT(&depot->not_empty);
191         SLIST_INIT(&depot->empty);
192         depot->magsize = KMC_MAG_MIN_SZ;
193         depot->nr_not_empty = 0;
194         depot->nr_empty = 0;
195         depot->busy_count = 0;
196         depot->busy_start = 0;
197 }
198
199 static bool mag_is_empty(struct kmem_magazine *mag)
200 {
201         return mag->nr_rounds == 0;
202 }
203
204 /* Helper, swaps the loaded and previous mags.  Hold the pcc lock. */
205 static void __swap_mags(struct kmem_pcpu_cache *pcc)
206 {
207         struct kmem_magazine *temp;
208
209         temp = pcc->prev;
210         pcc->prev = pcc->loaded;
211         pcc->loaded = temp;
212 }
213
214 /* Helper, returns a magazine to the depot.  Hold the depot lock. */
215 static void __return_to_depot(struct kmem_cache *kc, struct kmem_magazine *mag)
216 {
217         struct kmem_depot *depot = &kc->depot;
218
219         if (mag_is_empty(mag)) {
220                 SLIST_INSERT_HEAD(&depot->empty, mag, link);
221                 depot->nr_empty++;
222         } else {
223                 SLIST_INSERT_HEAD(&depot->not_empty, mag, link);
224                 depot->nr_not_empty++;
225         }
226 }
227
228 /* Helper, removes the contents of the magazine, giving them back to the slab
229  * layer. */
230 static void drain_mag(struct kmem_cache *kc, struct kmem_magazine *mag)
231 {
232         for (int i = 0; i < mag->nr_rounds; i++)
233                 __kmem_free_to_slab(kc, mag->rounds[i]);
234         mag->nr_rounds = 0;
235 }
236
237 static struct kmem_pcpu_cache *build_pcpu_caches(void)
238 {
239         struct kmem_pcpu_cache *pcc;
240
241         pcc = base_alloc(NULL,
242                          sizeof(struct kmem_pcpu_cache) * kmc_nr_pcpu_caches(),
243                          MEM_WAIT);
244         for (int i = 0; i < kmc_nr_pcpu_caches(); i++) {
245                 pcc[i].irq_state = 0;
246                 pcc[i].magsize = KMC_MAG_MIN_SZ;
247                 pcc[i].loaded = __kmem_alloc_from_slab(kmem_magazine_cache, MEM_WAIT);
248                 pcc[i].prev = __kmem_alloc_from_slab(kmem_magazine_cache, MEM_WAIT);
249                 pcc[i].nr_allocs_ever = 0;
250         }
251         return pcc;
252 }
253
254 void __kmem_cache_create(struct kmem_cache *kc, const char *name,
255                          size_t obj_size, int align, int flags,
256                          struct arena *source,
257                          void (*ctor)(void *, size_t),
258                          void (*dtor)(void *, size_t))
259 {
260         assert(kc);
261         assert(align);
262         spinlock_init_irqsave(&kc->cache_lock);
263         strlcpy(kc->name, name, KMC_NAME_SZ);
264         kc->obj_size = ROUNDUP(obj_size, align);
265         if (flags & KMC_QCACHE)
266                 kc->import_amt = ROUNDUPPWR2(3 * source->qcache_max);
267         else
268                 kc->import_amt = ROUNDUP(NUM_BUF_PER_SLAB * obj_size, PGSIZE);
269         kc->align = align;
270         if (align > PGSIZE)
271                 panic("Cache %s object alignment is actually MIN(PGSIZE, align (%p))",
272                       name, align);
273         kc->flags = flags;
274         /* We might want some sort of per-call site NUMA-awareness in the future. */
275         kc->source = source ? source : kpages_arena;
276         TAILQ_INIT(&kc->full_slab_list);
277         TAILQ_INIT(&kc->partial_slab_list);
278         TAILQ_INIT(&kc->empty_slab_list);
279         kc->ctor = ctor;
280         kc->dtor = dtor;
281         kc->nr_cur_alloc = 0;
282         kc->alloc_hash = kc->static_hash;
283         hash_init_hh(&kc->hh);
284         for (int i = 0; i < kc->hh.nr_hash_lists; i++)
285                 BSD_LIST_INIT(&kc->static_hash[i]);
286         /* No touch must use bufctls, even for small objects, so that it does not
287          * use the object as memory.  Note that if we have an arbitrary source,
288          * small objects, and we're 'pro-touch', the small allocation path will
289          * assume we're importing from a PGSIZE-aligned source arena. */
290         if ((obj_size > SLAB_LARGE_CUTOFF) || (flags & KMC_NOTOUCH))
291                 kc->flags |= __KMC_USE_BUFCTL;
292         depot_init(&kc->depot);
293         /* We do this last, since this will all into the magazine cache - which we
294          * could be creating on this call! */
295         kc->pcpu_caches = build_pcpu_caches();
296         add_importing_slab(kc->source, kc);
297         /* put in cache list based on it's size */
298         struct kmem_cache *i, *prev = NULL;
299         spin_lock_irqsave(&kmem_caches_lock);
300         /* find the kmem_cache before us in the list.  yes, this is O(n). */
301         SLIST_FOREACH(i, &kmem_caches, link) {
302                 if (i->obj_size < kc->obj_size)
303                         prev = i;
304                 else
305                         break;
306         }
307         if (prev)
308                 SLIST_INSERT_AFTER(prev, kc, link);
309         else
310                 SLIST_INSERT_HEAD(&kmem_caches, kc, link);
311         spin_unlock_irqsave(&kmem_caches_lock);
312 }
313
314 static void __mag_ctor(void *obj, size_t _ign)
315 {
316         struct kmem_magazine *mag = (struct kmem_magazine*)obj;
317
318         mag->nr_rounds = 0;
319 }
320
321 void kmem_cache_init(void)
322 {
323         /* magazine must be first - all caches, including mags, will do a slab alloc
324          * from the mag cache. */
325         static_assert(sizeof(struct kmem_magazine) <= SLAB_LARGE_CUTOFF);
326         __kmem_cache_create(kmem_magazine_cache, "kmem_magazine",
327                             sizeof(struct kmem_magazine),
328                             __alignof__(struct kmem_magazine), 0, base_arena,
329                             __mag_ctor, NULL);
330         __kmem_cache_create(kmem_cache_cache, "kmem_cache",
331                             sizeof(struct kmem_cache),
332                             __alignof__(struct kmem_cache), 0, base_arena,
333                             NULL, NULL);
334         __kmem_cache_create(kmem_slab_cache, "kmem_slab",
335                             sizeof(struct kmem_slab),
336                             __alignof__(struct kmem_slab), 0, base_arena,
337                             NULL, NULL);
338         __kmem_cache_create(kmem_bufctl_cache, "kmem_bufctl",
339                             sizeof(struct kmem_bufctl),
340                             __alignof__(struct kmem_bufctl), 0, base_arena,
341                             NULL, NULL);
342 }
343
344 /* Cache management */
345 struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
346                                      int align, int flags,
347                                      struct arena *source,
348                                      void (*ctor)(void *, size_t),
349                                      void (*dtor)(void *, size_t))
350 {
351         struct kmem_cache *kc = kmem_cache_alloc(kmem_cache_cache, 0);
352         __kmem_cache_create(kc, name, obj_size, align, flags, source, ctor, dtor);
353         return kc;
354 }
355
356 /* Helper during destruction.  No one should be touching the allocator anymore.
357  * We just need to hand objects back to the depot, which will hand them to the
358  * slab.  Locking is just a formality here. */
359 static void drain_pcpu_caches(struct kmem_cache *kc)
360 {
361         struct kmem_pcpu_cache *pcc;
362
363         for (int i = 0; i < kmc_nr_pcpu_caches(); i++) {
364                 pcc = &kc->pcpu_caches[i];
365                 lock_pcu_cache(pcc);
366                 lock_depot(&kc->depot);
367                 __return_to_depot(kc, pcc->loaded);
368                 __return_to_depot(kc, pcc->prev);
369                 unlock_depot(&kc->depot);
370                 pcc->loaded = SLAB_POISON;
371                 pcc->prev = SLAB_POISON;
372                 unlock_pcu_cache(pcc);
373         }
374 }
375
376 static void depot_destroy(struct kmem_cache *kc)
377 {
378         struct kmem_magazine *mag_i;
379         struct kmem_depot *depot = &kc->depot;
380
381         lock_depot(depot);
382         while ((mag_i = SLIST_FIRST(&depot->not_empty))) {
383                 drain_mag(kc, mag_i);
384                 kmem_cache_free(kmem_magazine_cache, mag_i);
385         }
386         while ((mag_i = SLIST_FIRST(&depot->empty)))
387                 kmem_cache_free(kmem_magazine_cache, mag_i);
388         unlock_depot(depot);
389 }
390
391 static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
392 {
393         if (!__use_bufctls(cp)) {
394                 arena_free(cp->source, ROUNDDOWN(a_slab, PGSIZE), PGSIZE);
395         } else {
396                 struct kmem_bufctl *i, *temp;
397                 void *buf_start = (void*)SIZE_MAX;
398
399                 BSD_LIST_FOREACH_SAFE(i, &a_slab->bufctl_freelist, link, temp) {
400                         // Track the lowest buffer address, which is the start of the buffer
401                         buf_start = MIN(buf_start, i->buf_addr);
402                         /* This is a little dangerous, but we can skip removing, since we
403                          * init the freelist when we reuse the slab. */
404                         kmem_cache_free(kmem_bufctl_cache, i);
405                 }
406                 arena_free(cp->source, buf_start, cp->import_amt);
407                 kmem_cache_free(kmem_slab_cache, a_slab);
408         }
409 }
410
411 /* Once you call destroy, never use this cache again... o/w there may be weird
412  * races, and other serious issues.  */
413 void kmem_cache_destroy(struct kmem_cache *cp)
414 {
415         struct kmem_slab *a_slab, *next;
416
417         del_importing_slab(cp->source, cp);
418         drain_pcpu_caches(cp);
419         depot_destroy(cp);
420         spin_lock_irqsave(&cp->cache_lock);
421         assert(TAILQ_EMPTY(&cp->full_slab_list));
422         assert(TAILQ_EMPTY(&cp->partial_slab_list));
423         /* Clean out the empty list.  We can't use a regular FOREACH here, since the
424          * link element is stored in the slab struct, which is stored on the page
425          * that we are freeing. */
426         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
427         while (a_slab) {
428                 next = TAILQ_NEXT(a_slab, link);
429                 kmem_slab_destroy(cp, a_slab);
430                 a_slab = next;
431         }
432         spin_lock_irqsave(&kmem_caches_lock);
433         SLIST_REMOVE(&kmem_caches, cp, kmem_cache, link);
434         spin_unlock_irqsave(&kmem_caches_lock);
435         kmem_cache_free(kmem_cache_cache, cp);
436         spin_unlock_irqsave(&cp->cache_lock);
437 }
438
439 static void __try_hash_resize(struct kmem_cache *cp)
440 {
441         struct kmem_bufctl_list *new_tbl, *old_tbl;
442         struct kmem_bufctl *bc_i;
443         unsigned int new_tbl_nr_lists, old_tbl_nr_lists;
444         size_t new_tbl_sz, old_tbl_sz;
445         size_t hash_idx;
446
447         if (!hash_needs_more(&cp->hh))
448                 return;
449         new_tbl_nr_lists = hash_next_nr_lists(&cp->hh);
450         new_tbl_sz = new_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
451         /* TODO: we only need to pull from base if our arena is a base or we are
452          * inside a kpages arena (keep in mind there could be more than one of
453          * those, depending on how we do NUMA allocs).  This might help with
454          * fragmentation.  To know this, we'll need the caller to pass us a flag. */
455         new_tbl = base_zalloc(NULL, new_tbl_sz, ARENA_INSTANTFIT | MEM_ATOMIC);
456         if (!new_tbl)
457                 return;
458         old_tbl = cp->alloc_hash;
459         old_tbl_nr_lists = cp->hh.nr_hash_lists;
460         old_tbl_sz = old_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
461         cp->alloc_hash = new_tbl;
462         hash_incr_nr_lists(&cp->hh);
463         for (int i = 0; i < old_tbl_nr_lists; i++) {
464                 while ((bc_i = BSD_LIST_FIRST(&old_tbl[i]))) {
465                         BSD_LIST_REMOVE(bc_i, link);
466                         hash_idx = hash_ptr(bc_i->buf_addr, cp->hh.nr_hash_bits);
467                         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc_i, link);
468                 }
469         }
470         hash_reset_load_limit(&cp->hh);
471         if (old_tbl != cp->static_hash)
472                 base_free(NULL, old_tbl, old_tbl_sz);
473 }
474
475 /* Helper, tracks the allocation of @bc in the hash table */
476 static void __track_alloc(struct kmem_cache *cp, struct kmem_bufctl *bc)
477 {
478         size_t hash_idx;
479
480         hash_idx = hash_ptr(bc->buf_addr, cp->hh.nr_hash_bits);
481         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc, link);
482         cp->hh.nr_items++;
483         __try_hash_resize(cp);
484 }
485
486 /* Helper, looks up and removes the bufctl corresponding to buf. */
487 static struct kmem_bufctl *__yank_bufctl(struct kmem_cache *cp, void *buf)
488 {
489         struct kmem_bufctl *bc_i;
490         size_t hash_idx;
491
492         hash_idx = hash_ptr(buf, cp->hh.nr_hash_bits);
493         BSD_LIST_FOREACH(bc_i, &cp->alloc_hash[hash_idx], link) {
494                 if (bc_i->buf_addr == buf) {
495                         BSD_LIST_REMOVE(bc_i, link);
496                         break;
497                 }
498         }
499         if (!bc_i)
500                 panic("Could not find buf %p in cache %s!", buf, cp->name);
501         return bc_i;
502 }
503
504 /* Alloc, bypassing the magazines and depot */
505 static void *__kmem_alloc_from_slab(struct kmem_cache *cp, int flags)
506 {
507         void *retval = NULL;
508         spin_lock_irqsave(&cp->cache_lock);
509         // look at partial list
510         struct kmem_slab *a_slab = TAILQ_FIRST(&cp->partial_slab_list);
511         //      if none, go to empty list and get an empty and make it partial
512         if (!a_slab) {
513                 // TODO: think about non-sleeping flags
514                 if (TAILQ_EMPTY(&cp->empty_slab_list) &&
515                         !kmem_cache_grow(cp)) {
516                         spin_unlock_irqsave(&cp->cache_lock);
517                         if (flags & MEM_ERROR)
518                                 error(ENOMEM, ERROR_FIXME);
519                         else
520                                 panic("[German Accent]: OOM for a small slab growth!!!");
521                 }
522                 // move to partial list
523                 a_slab = TAILQ_FIRST(&cp->empty_slab_list);
524                 TAILQ_REMOVE(&cp->empty_slab_list, a_slab, link);
525                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
526         }
527         // have a partial now (a_slab), get an item, return item
528         if (!__use_bufctls(cp)) {
529                 retval = a_slab->free_small_obj;
530                 /* the next free_small_obj address is stored at the beginning of the
531                  * current free_small_obj. */
532                 a_slab->free_small_obj = *(uintptr_t**)(a_slab->free_small_obj);
533         } else {
534                 // rip the first bufctl out of the partial slab's buf list
535                 struct kmem_bufctl *a_bufctl = BSD_LIST_FIRST(&a_slab->bufctl_freelist);
536
537                 BSD_LIST_REMOVE(a_bufctl, link);
538                 __track_alloc(cp, a_bufctl);
539                 retval = a_bufctl->buf_addr;
540         }
541         a_slab->num_busy_obj++;
542         // Check if we are full, if so, move to the full list
543         if (a_slab->num_busy_obj == a_slab->num_total_obj) {
544                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
545                 TAILQ_INSERT_HEAD(&cp->full_slab_list, a_slab, link);
546         }
547         cp->nr_cur_alloc++;
548         spin_unlock_irqsave(&cp->cache_lock);
549         if (cp->ctor)
550                 cp->ctor(retval, cp->obj_size);
551         return retval;
552 }
553
554 void *kmem_cache_alloc(struct kmem_cache *kc, int flags)
555 {
556         struct kmem_pcpu_cache *pcc = get_my_pcpu_cache(kc);
557         struct kmem_depot *depot = &kc->depot;
558         struct kmem_magazine *mag;
559         void *ret;
560
561         lock_pcu_cache(pcc);
562 try_alloc:
563         if (pcc->loaded->nr_rounds) {
564                 ret = pcc->loaded->rounds[pcc->loaded->nr_rounds - 1];
565                 pcc->loaded->nr_rounds--;
566                 pcc->nr_allocs_ever++;
567                 unlock_pcu_cache(pcc);
568                 return ret;
569         }
570         if (!mag_is_empty(pcc->prev)) {
571                 __swap_mags(pcc);
572                 goto try_alloc;
573         }
574         /* Note the lock ordering: pcc -> depot */
575         lock_depot(depot);
576         mag = SLIST_FIRST(&depot->not_empty);
577         if (mag) {
578                 SLIST_REMOVE_HEAD(&depot->not_empty, link);
579                 depot->nr_not_empty--;
580                 __return_to_depot(kc, pcc->prev);
581                 unlock_depot(depot);
582                 pcc->prev = pcc->loaded;
583                 pcc->loaded = mag;
584                 goto try_alloc;
585         }
586         unlock_depot(depot);
587         unlock_pcu_cache(pcc);
588         return __kmem_alloc_from_slab(kc, flags);
589 }
590
591 /* Returns an object to the slab layer.  Note that objects in the slabs are
592  * unconstructed. */
593 static void __kmem_free_to_slab(struct kmem_cache *cp, void *buf)
594 {
595         struct kmem_slab *a_slab;
596         struct kmem_bufctl *a_bufctl;
597
598         if (cp->dtor)
599                 cp->dtor(buf, cp->obj_size);
600         spin_lock_irqsave(&cp->cache_lock);
601         if (!__use_bufctls(cp)) {
602                 // find its slab
603                 a_slab = (struct kmem_slab*)(ROUNDDOWN((uintptr_t)buf, PGSIZE) +
604                                              PGSIZE - sizeof(struct kmem_slab));
605                 /* write location of next free small obj to the space at the beginning
606                  * of the buffer, then list buf as the next free small obj */
607                 *(uintptr_t**)buf = a_slab->free_small_obj;
608                 a_slab->free_small_obj = buf;
609         } else {
610                 /* Give the bufctl back to the parent slab */
611                 a_bufctl = __yank_bufctl(cp, buf);
612                 a_slab = a_bufctl->my_slab;
613                 BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
614         }
615         a_slab->num_busy_obj--;
616         cp->nr_cur_alloc--;
617         // if it was full, move it to partial
618         if (a_slab->num_busy_obj + 1 == a_slab->num_total_obj) {
619                 TAILQ_REMOVE(&cp->full_slab_list, a_slab, link);
620                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
621         } else if (!a_slab->num_busy_obj) {
622                 // if there are none, move to from partial to empty
623                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
624                 TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
625         }
626         spin_unlock_irqsave(&cp->cache_lock);
627 }
628
629 void kmem_cache_free(struct kmem_cache *kc, void *buf)
630 {
631         struct kmem_pcpu_cache *pcc = get_my_pcpu_cache(kc);
632         struct kmem_depot *depot = &kc->depot;
633         struct kmem_magazine *mag;
634
635         lock_pcu_cache(pcc);
636 try_free:
637         if (pcc->loaded->nr_rounds < pcc->magsize) {
638                 pcc->loaded->rounds[pcc->loaded->nr_rounds] = buf;
639                 pcc->loaded->nr_rounds++;
640                 unlock_pcu_cache(pcc);
641                 return;
642         }
643         /* The paper checks 'is empty' here.  But we actually just care if it has
644          * room left, not that prev is completely empty.  This could be the case due
645          * to magazine resize. */
646         if (pcc->prev->nr_rounds < pcc->magsize) {
647                 __swap_mags(pcc);
648                 goto try_free;
649         }
650         lock_depot(depot);
651         /* Here's where the resize magic happens.  We'll start using it for the next
652          * magazine. */
653         pcc->magsize = depot->magsize;
654         mag = SLIST_FIRST(&depot->empty);
655         if (mag) {
656                 SLIST_REMOVE_HEAD(&depot->empty, link);
657                 depot->nr_empty--;
658                 __return_to_depot(kc, pcc->prev);
659                 unlock_depot(depot);
660                 pcc->prev = pcc->loaded;
661                 pcc->loaded = mag;
662                 goto try_free;
663         }
664         unlock_depot(depot);
665         /* Need to unlock, in case we end up calling back into ourselves. */
666         unlock_pcu_cache(pcc);
667         /* don't want to wait on a free.  if this fails, we can still just give it
668          * to the slab layer. */
669         mag = kmem_cache_alloc(kmem_magazine_cache, MEM_ATOMIC);
670         if (mag) {
671                 assert(mag->nr_rounds == 0);    /* paranoia, can probably remove */
672                 lock_depot(depot);
673                 SLIST_INSERT_HEAD(&depot->empty, mag, link);
674                 depot->nr_empty++;
675                 unlock_depot(depot);
676                 lock_pcu_cache(pcc);
677                 goto try_free;
678         }
679         __kmem_free_to_slab(kc, buf);
680 }
681
682 /* Back end: internal functions */
683 /* When this returns, the cache has at least one slab in the empty list.  If
684  * page_alloc fails, there are some serious issues.  This only grows by one slab
685  * at a time.
686  *
687  * Grab the cache lock before calling this.
688  *
689  * TODO: think about page colouring issues with kernel memory allocation. */
690 static bool kmem_cache_grow(struct kmem_cache *cp)
691 {
692         struct kmem_slab *a_slab;
693         struct kmem_bufctl *a_bufctl;
694
695         if (!__use_bufctls(cp)) {
696                 void *a_page;
697
698                 /* Careful, this assumes our source is a PGSIZE-aligned allocator.  We
699                  * could use xalloc to enforce the alignment, but that'll bypass the
700                  * qcaches, which we don't want.  Caller beware. */
701                 a_page = arena_alloc(cp->source, PGSIZE, MEM_ATOMIC);
702                 if (!a_page)
703                         return FALSE;
704                 // the slab struct is stored at the end of the page
705                 a_slab = (struct kmem_slab*)(a_page + PGSIZE
706                                              - sizeof(struct kmem_slab));
707                 a_slab->num_busy_obj = 0;
708                 a_slab->num_total_obj = (PGSIZE - sizeof(struct kmem_slab)) /
709                                         cp->obj_size;
710                 // TODO: consider staggering this IAW section 4.3
711                 a_slab->free_small_obj = a_page;
712                 /* Walk and create the free list, which is circular.  Each item stores
713                  * the location of the next one at the beginning of the block. */
714                 void *buf = a_slab->free_small_obj;
715                 for (int i = 0; i < a_slab->num_total_obj - 1; i++) {
716                         *(uintptr_t**)buf = buf + cp->obj_size;
717                         buf += cp->obj_size;
718                 }
719                 *((uintptr_t**)buf) = NULL;
720         } else {
721                 void *buf;
722
723                 a_slab = kmem_cache_alloc(kmem_slab_cache, 0);
724                 if (!a_slab)
725                         return FALSE;
726                 buf = arena_alloc(cp->source, cp->import_amt, MEM_ATOMIC);
727                 if (!buf) {
728                         kmem_cache_free(kmem_slab_cache, a_slab);
729                         return FALSE;
730                 }
731                 a_slab->num_busy_obj = 0;
732                 a_slab->num_total_obj = cp->import_amt / cp->obj_size;
733                 BSD_LIST_INIT(&a_slab->bufctl_freelist);
734                 /* for each buffer, set up a bufctl and point to the buffer */
735                 for (int i = 0; i < a_slab->num_total_obj; i++) {
736                         a_bufctl = kmem_cache_alloc(kmem_bufctl_cache, 0);
737                         BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
738                         a_bufctl->buf_addr = buf;
739                         a_bufctl->my_slab = a_slab;
740                         buf += cp->obj_size;
741                 }
742         }
743         // add a_slab to the empty_list
744         TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
745
746         return TRUE;
747 }
748
749 /* This deallocs every slab from the empty list.  TODO: think a bit more about
750  * this.  We can do things like not free all of the empty lists to prevent
751  * thrashing.  See 3.4 in the paper. */
752 void kmem_cache_reap(struct kmem_cache *cp)
753 {
754         struct kmem_slab *a_slab, *next;
755
756         // Destroy all empty slabs.  Refer to the notes about the while loop
757         spin_lock_irqsave(&cp->cache_lock);
758         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
759         while (a_slab) {
760                 next = TAILQ_NEXT(a_slab, link);
761                 kmem_slab_destroy(cp, a_slab);
762                 a_slab = next;
763         }
764         spin_unlock_irqsave(&cp->cache_lock);
765 }
766
767 void print_kmem_cache(struct kmem_cache *cp)
768 {
769         spin_lock_irqsave(&cp->cache_lock);
770         printk("\nPrinting kmem_cache:\n---------------------\n");
771         printk("Name: %s\n", cp->name);
772         printk("Objsize (incl align): %d\n", cp->obj_size);
773         printk("Align: %d\n", cp->align);
774         printk("Flags: 0x%08x\n", cp->flags);
775         printk("Constructor: %p\n", cp->ctor);
776         printk("Destructor: %p\n", cp->dtor);
777         printk("Slab Full: %p\n", cp->full_slab_list);
778         printk("Slab Partial: %p\n", cp->partial_slab_list);
779         printk("Slab Empty: %p\n", cp->empty_slab_list);
780         printk("Current Allocations: %d\n", cp->nr_cur_alloc);
781         spin_unlock_irqsave(&cp->cache_lock);
782 }