vmm: refactor userspace's emsr_fakewrite()
[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  * - 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 #include <hashtable.h>
90
91 #define SLAB_POISON ((void*)0xdead1111)
92
93 /* Tunables.  I don't know which numbers to pick yet.  Maybe we play with it at
94  * runtime.  Though once a mag increases, it'll never decrease. */
95 uint64_t resize_timeout_ns = 1000000000;
96 unsigned int resize_threshold = 1;
97
98 /* Protected by the arenas_and_slabs_lock. */
99 struct kmem_cache_tailq all_kmem_caches =
100                 TAILQ_HEAD_INITIALIZER(all_kmem_caches);
101
102 static void kmc_track(struct kmem_cache *kc)
103 {
104         struct kmem_cache *kc_i;
105
106         qlock(&arenas_and_slabs_lock);
107         TAILQ_FOREACH(kc_i, &all_kmem_caches, all_kmc_link) {
108                 if (!strcmp(kc->name, kc_i->name))
109                         warn("Creatgin KMC %s, but one with that name exists!",
110                              kc->name);
111         }
112         TAILQ_INSERT_TAIL(&all_kmem_caches, kc, all_kmc_link);
113         qunlock(&arenas_and_slabs_lock);
114 }
115
116 static void kmc_untrack(struct kmem_cache *kc)
117 {
118         qlock(&arenas_and_slabs_lock);
119         TAILQ_REMOVE(&all_kmem_caches, kc, all_kmc_link);
120         qunlock(&arenas_and_slabs_lock);
121 }
122
123 /* Backend/internal functions, defined later.  Grab the lock before calling
124  * these. */
125 static bool kmem_cache_grow(struct kmem_cache *cp);
126 static void *__kmem_alloc_from_slab(struct kmem_cache *cp, int flags);
127 static void __kmem_free_to_slab(struct kmem_cache *cp, void *buf);
128
129 /* Forward declarations for trace hooks */
130 static void kmem_trace_ht_init(struct kmem_trace_ht *ht);
131 static void kmem_trace_free(struct kmem_cache *kc, void *obj);
132 static void kmem_trace_alloc(struct kmem_cache *kc, void *obj);
133 static void kmem_trace_warn_notempty(struct kmem_cache *kc);
134
135 /* Cache of the kmem_cache objects, needed for bootstrapping */
136 struct kmem_cache kmem_cache_cache[1];
137 struct kmem_cache kmem_slab_cache[1];
138 struct kmem_cache kmem_bufctl_cache[1];
139 struct kmem_cache kmem_magazine_cache[1];
140 struct kmem_cache kmem_trace_cache[1];
141
142 static bool __use_bufctls(struct kmem_cache *cp)
143 {
144         return cp->flags & __KMC_USE_BUFCTL;
145 }
146
147 /* Using a layer of indirection for the pcpu caches, in case we want to use
148  * clustered objects, only per-NUMA-domain caches, or something like that. */
149 unsigned int kmc_nr_pcpu_caches(void)
150 {
151         return num_cores;
152 }
153
154 static struct kmem_pcpu_cache *get_my_pcpu_cache(struct kmem_cache *kc)
155 {
156         return &kc->pcpu_caches[core_id()];
157 }
158
159 /* In our current model, there is one pcc per core.  If we had multiple cores
160  * that could use the pcc, such as with per-NUMA caches, then we'd need a
161  * spinlock.  Since we do allocations from IRQ context, we still need to disable
162  * IRQs. */
163 static void lock_pcu_cache(struct kmem_pcpu_cache *pcc)
164 {
165         disable_irqsave(&pcc->irq_state);
166 }
167
168 static void unlock_pcu_cache(struct kmem_pcpu_cache *pcc)
169 {
170         enable_irqsave(&pcc->irq_state);
171 }
172
173 static void lock_depot(struct kmem_depot *depot)
174 {
175         uint64_t time;
176
177         if (spin_trylock_irqsave(&depot->lock))
178                 return;
179         /* The lock is contended.  When we finally get the lock, we'll up the
180          * contention count and see if we've had too many contentions over time.
181          *
182          * The idea is that if there are bursts of contention worse than X
183          * contended acquisitions in Y nsec, then we'll grow the magazines.
184          * This might not be that great of an approach - every thread gets one
185          * count, regardless of how long they take.
186          *
187          * We read the time before locking so that we don't artificially grow
188          * the window too much.  Say the lock is heavily contended and we take a
189          * long time to get it.  Perhaps X threads try to lock it immediately,
190          * but it takes over Y seconds for the Xth thread to actually get the
191          * lock.  We might then think the burst wasn't big enough. */
192         time = nsec();
193         spin_lock_irqsave(&depot->lock);
194         /* If there are no not-empty mags, we're probably fighting for the lock
195          * not because the magazines aren't big enough, but because there aren't
196          * enough mags in the system yet. */
197         if (!depot->nr_not_empty)
198                 return;
199         if (time - depot->busy_start > resize_timeout_ns) {
200                 depot->busy_count = 0;
201                 depot->busy_start = time;
202         }
203         depot->busy_count++;
204         if (depot->busy_count > resize_threshold) {
205                 depot->busy_count = 0;
206                 depot->magsize = MIN(KMC_MAG_MAX_SZ, depot->magsize + 1);
207                 /* That's all we do - the pccs will eventually notice and up
208                  * their magazine sizes. */
209         }
210 }
211
212 static void unlock_depot(struct kmem_depot *depot)
213 {
214         spin_unlock_irqsave(&depot->lock);
215 }
216
217 static void depot_init(struct kmem_depot *depot)
218 {
219         spinlock_init_irqsave(&depot->lock);
220         SLIST_INIT(&depot->not_empty);
221         SLIST_INIT(&depot->empty);
222         depot->magsize = KMC_MAG_MIN_SZ;
223         depot->nr_not_empty = 0;
224         depot->nr_empty = 0;
225         depot->busy_count = 0;
226         depot->busy_start = 0;
227 }
228
229 static bool mag_is_empty(struct kmem_magazine *mag)
230 {
231         return mag->nr_rounds == 0;
232 }
233
234 /* Helper, swaps the loaded and previous mags.  Hold the pcc lock. */
235 static void __swap_mags(struct kmem_pcpu_cache *pcc)
236 {
237         struct kmem_magazine *temp;
238
239         temp = pcc->prev;
240         pcc->prev = pcc->loaded;
241         pcc->loaded = temp;
242 }
243
244 /* Helper, returns a magazine to the depot.  Hold the depot lock. */
245 static void __return_to_depot(struct kmem_cache *kc, struct kmem_magazine *mag)
246 {
247         struct kmem_depot *depot = &kc->depot;
248
249         if (mag_is_empty(mag)) {
250                 SLIST_INSERT_HEAD(&depot->empty, mag, link);
251                 depot->nr_empty++;
252         } else {
253                 SLIST_INSERT_HEAD(&depot->not_empty, mag, link);
254                 depot->nr_not_empty++;
255         }
256 }
257
258 /* Helper, removes the contents of the magazine, giving them back to the slab
259  * layer. */
260 static void drain_mag(struct kmem_cache *kc, struct kmem_magazine *mag)
261 {
262         for (int i = 0; i < mag->nr_rounds; i++) {
263                 if (kc->dtor)
264                         kc->dtor(mag->rounds[i], kc->priv);
265                 __kmem_free_to_slab(kc, mag->rounds[i]);
266         }
267         mag->nr_rounds = 0;
268 }
269
270 static struct kmem_pcpu_cache *build_pcpu_caches(void)
271 {
272         struct kmem_pcpu_cache *pcc;
273
274         pcc = base_alloc(NULL,
275                          sizeof(struct kmem_pcpu_cache) * kmc_nr_pcpu_caches(),
276                          MEM_WAIT);
277         for (int i = 0; i < kmc_nr_pcpu_caches(); i++) {
278                 pcc[i].irq_state = 0;
279                 pcc[i].magsize = KMC_MAG_MIN_SZ;
280                 pcc[i].loaded = __kmem_alloc_from_slab(kmem_magazine_cache,
281                                                        MEM_WAIT);
282                 pcc[i].prev = __kmem_alloc_from_slab(kmem_magazine_cache,
283                                                      MEM_WAIT);
284                 pcc[i].nr_allocs_ever = 0;
285         }
286         return pcc;
287 }
288
289 void __kmem_cache_create(struct kmem_cache *kc, const char *name,
290                          size_t obj_size, int align, int flags,
291                          struct arena *source,
292                          int (*ctor)(void *, void *, int),
293                          void (*dtor)(void *, void *), void *priv)
294 {
295         assert(kc);
296         assert(align);
297         spinlock_init_irqsave(&kc->cache_lock);
298         strlcpy(kc->name, name, KMC_NAME_SZ);
299         kc->obj_size = ROUNDUP(obj_size, align);
300         if (flags & KMC_QCACHE)
301                 kc->import_amt = ROUNDUPPWR2(3 * source->qcache_max);
302         else
303                 kc->import_amt = ROUNDUP(NUM_BUF_PER_SLAB * obj_size, PGSIZE);
304         kc->align = align;
305         if (align > PGSIZE)
306                 panic("Cache %s object alignment is actually MIN(PGSIZE, align (%p))",
307                       name, align);
308         kc->flags = flags;
309         /* We might want some sort of per-call site NUMA-awareness in the
310          * future. */
311         kc->source = source ? source : kpages_arena;
312         TAILQ_INIT(&kc->full_slab_list);
313         TAILQ_INIT(&kc->partial_slab_list);
314         TAILQ_INIT(&kc->empty_slab_list);
315         kc->ctor = ctor;
316         kc->dtor = dtor;
317         kc->priv = priv;
318         kc->nr_cur_alloc = 0;
319         kc->nr_direct_allocs_ever = 0;
320         kc->alloc_hash = kc->static_hash;
321         hash_init_hh(&kc->hh);
322         for (int i = 0; i < kc->hh.nr_hash_lists; i++)
323                 BSD_LIST_INIT(&kc->static_hash[i]);
324         /* No touch must use bufctls, even for small objects, so that it does
325          * not use the object as memory.  Note that if we have an arbitrary
326          * source, small objects, and we're 'pro-touch', the small allocation
327          * path will assume we're importing from a PGSIZE-aligned source arena.
328          */
329         if ((obj_size > SLAB_LARGE_CUTOFF) || (flags & KMC_NOTOUCH))
330                 kc->flags |= __KMC_USE_BUFCTL;
331         depot_init(&kc->depot);
332         kmem_trace_ht_init(&kc->trace_ht);
333         /* We do this last, since this will all into the magazine cache - which
334          * we could be creating on this call! */
335         kc->pcpu_caches = build_pcpu_caches();
336         add_importing_slab(kc->source, kc);
337         kmc_track(kc);
338 }
339
340 static int __mag_ctor(void *obj, void *priv, int flags)
341 {
342         struct kmem_magazine *mag = (struct kmem_magazine*)obj;
343
344         mag->nr_rounds = 0;
345         return 0;
346 }
347
348 void kmem_cache_init(void)
349 {
350         /* magazine must be first - all caches, including mags, will do a slab
351          * alloc from the mag cache. */
352         static_assert(sizeof(struct kmem_magazine) <= SLAB_LARGE_CUTOFF);
353         __kmem_cache_create(kmem_magazine_cache, "kmem_magazine",
354                             sizeof(struct kmem_magazine),
355                             __alignof__(struct kmem_magazine), KMC_NOTRACE,
356                             base_arena, __mag_ctor, NULL, NULL);
357         __kmem_cache_create(kmem_cache_cache, "kmem_cache",
358                             sizeof(struct kmem_cache),
359                             __alignof__(struct kmem_cache), 0, base_arena,
360                             NULL, NULL, NULL);
361         __kmem_cache_create(kmem_slab_cache, "kmem_slab",
362                             sizeof(struct kmem_slab),
363                             __alignof__(struct kmem_slab), KMC_NOTRACE,
364                             base_arena, NULL, NULL, NULL);
365         __kmem_cache_create(kmem_bufctl_cache, "kmem_bufctl",
366                             sizeof(struct kmem_bufctl),
367                             __alignof__(struct kmem_bufctl), KMC_NOTRACE,
368                             base_arena, NULL, NULL, NULL);
369         __kmem_cache_create(kmem_trace_cache, "kmem_trace",
370                             sizeof(struct kmem_trace),
371                             __alignof__(struct kmem_trace), KMC_NOTRACE,
372                             base_arena, NULL, NULL, NULL);
373 }
374
375 /* Cache management */
376 struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
377                                      int align, int flags,
378                                      struct arena *source,
379                                      int (*ctor)(void *, void *, int),
380                                      void (*dtor)(void *, void *),
381                                      void *priv)
382 {
383         struct kmem_cache *kc = kmem_cache_alloc(kmem_cache_cache, 0);
384
385         __kmem_cache_create(kc, name, obj_size, align, flags, source, ctor,
386                             dtor, priv);
387         return kc;
388 }
389
390 /* Helper during destruction.  No one should be touching the allocator anymore.
391  * We just need to hand objects back to the depot, which will hand them to the
392  * slab.  Locking is just a formality here. */
393 static void drain_pcpu_caches(struct kmem_cache *kc)
394 {
395         struct kmem_pcpu_cache *pcc;
396
397         for (int i = 0; i < kmc_nr_pcpu_caches(); i++) {
398                 pcc = &kc->pcpu_caches[i];
399                 lock_pcu_cache(pcc);
400                 lock_depot(&kc->depot);
401                 __return_to_depot(kc, pcc->loaded);
402                 __return_to_depot(kc, pcc->prev);
403                 unlock_depot(&kc->depot);
404                 pcc->loaded = SLAB_POISON;
405                 pcc->prev = SLAB_POISON;
406                 unlock_pcu_cache(pcc);
407         }
408 }
409
410 static void depot_destroy(struct kmem_cache *kc)
411 {
412         struct kmem_magazine *mag_i;
413         struct kmem_depot *depot = &kc->depot;
414
415         lock_depot(depot);
416         while ((mag_i = SLIST_FIRST(&depot->not_empty))) {
417                 drain_mag(kc, mag_i);
418                 kmem_cache_free(kmem_magazine_cache, mag_i);
419         }
420         while ((mag_i = SLIST_FIRST(&depot->empty)))
421                 kmem_cache_free(kmem_magazine_cache, mag_i);
422         unlock_depot(depot);
423 }
424
425 static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
426 {
427         if (!__use_bufctls(cp)) {
428                 arena_free(cp->source, ROUNDDOWN(a_slab, PGSIZE), PGSIZE);
429         } else {
430                 struct kmem_bufctl *i, *temp;
431                 void *buf_start = (void*)SIZE_MAX;
432
433                 BSD_LIST_FOREACH_SAFE(i, &a_slab->bufctl_freelist, link, temp) {
434                         // Track the lowest buffer address, which is the start
435                         // of the buffer
436                         buf_start = MIN(buf_start, i->buf_addr);
437                         /* This is a little dangerous, but we can skip removing,
438                          * since we init the freelist when we reuse the slab. */
439                         kmem_cache_free(kmem_bufctl_cache, i);
440                 }
441                 arena_free(cp->source, buf_start, cp->import_amt);
442                 kmem_cache_free(kmem_slab_cache, a_slab);
443         }
444 }
445
446 /* Once you call destroy, never use this cache again... o/w there may be weird
447  * races, and other serious issues.  */
448 void kmem_cache_destroy(struct kmem_cache *cp)
449 {
450         struct kmem_slab *a_slab, *next;
451
452         kmc_untrack(cp);
453         del_importing_slab(cp->source, cp);
454         drain_pcpu_caches(cp);
455         depot_destroy(cp);
456         spin_lock_irqsave(&cp->cache_lock);
457         assert(TAILQ_EMPTY(&cp->full_slab_list));
458         assert(TAILQ_EMPTY(&cp->partial_slab_list));
459         /* Clean out the empty list.  We can't use a regular FOREACH here, since
460          * the link element is stored in the slab struct, which is stored on the
461          * page that we are freeing. */
462         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
463         while (a_slab) {
464                 next = TAILQ_NEXT(a_slab, link);
465                 kmem_slab_destroy(cp, a_slab);
466                 a_slab = next;
467         }
468         spin_unlock_irqsave(&cp->cache_lock);
469         kmem_trace_warn_notempty(cp);
470         kmem_cache_free(kmem_cache_cache, cp);
471 }
472
473 static void __try_hash_resize(struct kmem_cache *cp)
474 {
475         struct kmem_bufctl_list *new_tbl, *old_tbl;
476         struct kmem_bufctl *bc_i;
477         unsigned int new_tbl_nr_lists, old_tbl_nr_lists;
478         size_t new_tbl_sz, old_tbl_sz;
479         size_t hash_idx;
480
481         if (!hash_needs_more(&cp->hh))
482                 return;
483         new_tbl_nr_lists = hash_next_nr_lists(&cp->hh);
484         new_tbl_sz = new_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
485         /* TODO: we only need to pull from base if our arena is a base or we are
486          * inside a kpages arena (keep in mind there could be more than one of
487          * those, depending on how we do NUMA allocs).  This might help with
488          * fragmentation.  To know this, we'll need the caller to pass us a
489          * flag. */
490         new_tbl = base_zalloc(NULL, new_tbl_sz, ARENA_INSTANTFIT | MEM_ATOMIC);
491         if (!new_tbl)
492                 return;
493         old_tbl = cp->alloc_hash;
494         old_tbl_nr_lists = cp->hh.nr_hash_lists;
495         old_tbl_sz = old_tbl_nr_lists * sizeof(struct kmem_bufctl_list);
496         cp->alloc_hash = new_tbl;
497         hash_incr_nr_lists(&cp->hh);
498         for (int i = 0; i < old_tbl_nr_lists; i++) {
499                 while ((bc_i = BSD_LIST_FIRST(&old_tbl[i]))) {
500                         BSD_LIST_REMOVE(bc_i, link);
501                         hash_idx = hash_ptr(bc_i->buf_addr,
502                                             cp->hh.nr_hash_bits);
503                         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc_i,
504                                              link);
505                 }
506         }
507         hash_reset_load_limit(&cp->hh);
508         if (old_tbl != cp->static_hash)
509                 base_free(NULL, old_tbl, old_tbl_sz);
510 }
511
512 /* Helper, tracks the allocation of @bc in the hash table */
513 static void __track_alloc(struct kmem_cache *cp, struct kmem_bufctl *bc)
514 {
515         size_t hash_idx;
516
517         hash_idx = hash_ptr(bc->buf_addr, cp->hh.nr_hash_bits);
518         BSD_LIST_INSERT_HEAD(&cp->alloc_hash[hash_idx], bc, link);
519         cp->hh.nr_items++;
520         __try_hash_resize(cp);
521 }
522
523 /* Helper, looks up and removes the bufctl corresponding to buf. */
524 static struct kmem_bufctl *__yank_bufctl(struct kmem_cache *cp, void *buf)
525 {
526         struct kmem_bufctl *bc_i;
527         size_t hash_idx;
528
529         hash_idx = hash_ptr(buf, cp->hh.nr_hash_bits);
530         BSD_LIST_FOREACH(bc_i, &cp->alloc_hash[hash_idx], link) {
531                 if (bc_i->buf_addr == buf) {
532                         BSD_LIST_REMOVE(bc_i, link);
533                         break;
534                 }
535         }
536         if (!bc_i)
537                 panic("Could not find buf %p in cache %s!", buf, cp->name);
538         return bc_i;
539 }
540
541 /* Alloc, bypassing the magazines and depot */
542 static void *__kmem_alloc_from_slab(struct kmem_cache *cp, int flags)
543 {
544         void *retval = NULL;
545
546         spin_lock_irqsave(&cp->cache_lock);
547         // look at partial list
548         struct kmem_slab *a_slab = TAILQ_FIRST(&cp->partial_slab_list);
549         //  if none, go to empty list and get an empty and make it partial
550         if (!a_slab) {
551                 // TODO: think about non-sleeping flags
552                 if (TAILQ_EMPTY(&cp->empty_slab_list) &&
553                         !kmem_cache_grow(cp)) {
554                         spin_unlock_irqsave(&cp->cache_lock);
555                         if (flags & MEM_ERROR)
556                                 error(ENOMEM, ERROR_FIXME);
557                         else
558                                 panic("[German Accent]: OOM for a small slab growth!!!");
559                 }
560                 // move to partial list
561                 a_slab = TAILQ_FIRST(&cp->empty_slab_list);
562                 TAILQ_REMOVE(&cp->empty_slab_list, a_slab, link);
563                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
564         }
565         // have a partial now (a_slab), get an item, return item
566         if (!__use_bufctls(cp)) {
567                 retval = a_slab->free_small_obj;
568                 /* the next free_small_obj address is stored at the beginning of
569                  * the current free_small_obj. */
570                 a_slab->free_small_obj = *(uintptr_t**)(a_slab->free_small_obj);
571         } else {
572                 // rip the first bufctl out of the partial slab's buf list
573                 struct kmem_bufctl *a_bufctl =
574                         BSD_LIST_FIRST(&a_slab->bufctl_freelist);
575
576                 BSD_LIST_REMOVE(a_bufctl, link);
577                 __track_alloc(cp, a_bufctl);
578                 retval = a_bufctl->buf_addr;
579         }
580         a_slab->num_busy_obj++;
581         // Check if we are full, if so, move to the full list
582         if (a_slab->num_busy_obj == a_slab->num_total_obj) {
583                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
584                 TAILQ_INSERT_HEAD(&cp->full_slab_list, a_slab, link);
585         }
586         cp->nr_cur_alloc++;
587         cp->nr_direct_allocs_ever++;
588         spin_unlock_irqsave(&cp->cache_lock);
589         if (cp->ctor) {
590                 if (cp->ctor(retval, cp->priv, flags)) {
591                         warn("Ctor %p failed, probably a bug!");
592                         __kmem_free_to_slab(cp, retval);
593                         return NULL;
594                 }
595         }
596         return retval;
597 }
598
599 void *kmem_cache_alloc(struct kmem_cache *kc, int flags)
600 {
601         struct kmem_pcpu_cache *pcc = get_my_pcpu_cache(kc);
602         struct kmem_depot *depot = &kc->depot;
603         struct kmem_magazine *mag;
604         void *ret;
605
606         lock_pcu_cache(pcc);
607 try_alloc:
608         if (pcc->loaded->nr_rounds) {
609                 ret = pcc->loaded->rounds[pcc->loaded->nr_rounds - 1];
610                 pcc->loaded->nr_rounds--;
611                 pcc->nr_allocs_ever++;
612                 unlock_pcu_cache(pcc);
613                 kmem_trace_alloc(kc, ret);
614                 return ret;
615         }
616         if (!mag_is_empty(pcc->prev)) {
617                 __swap_mags(pcc);
618                 goto try_alloc;
619         }
620         /* Note the lock ordering: pcc -> depot */
621         lock_depot(depot);
622         mag = SLIST_FIRST(&depot->not_empty);
623         if (mag) {
624                 SLIST_REMOVE_HEAD(&depot->not_empty, link);
625                 depot->nr_not_empty--;
626                 __return_to_depot(kc, pcc->prev);
627                 unlock_depot(depot);
628                 pcc->prev = pcc->loaded;
629                 pcc->loaded = mag;
630                 goto try_alloc;
631         }
632         unlock_depot(depot);
633         unlock_pcu_cache(pcc);
634         ret = __kmem_alloc_from_slab(kc, flags);
635         kmem_trace_alloc(kc, ret);
636         return ret;
637 }
638
639 /* Returns an object to the slab layer.  Caller must deconstruct the objects.
640  * Note that objects in the slabs are unconstructed. */
641 static void __kmem_free_to_slab(struct kmem_cache *cp, void *buf)
642 {
643         struct kmem_slab *a_slab;
644         struct kmem_bufctl *a_bufctl;
645
646         spin_lock_irqsave(&cp->cache_lock);
647         if (!__use_bufctls(cp)) {
648                 // find its slab
649                 a_slab = (struct kmem_slab*)(ROUNDDOWN((uintptr_t)buf, PGSIZE) +
650                                              PGSIZE - sizeof(struct kmem_slab));
651                 /* write location of next free small obj to the space at the
652                  * beginning of the buffer, then list buf as the next free small
653                  * obj */
654                 *(uintptr_t**)buf = a_slab->free_small_obj;
655                 a_slab->free_small_obj = buf;
656         } else {
657                 /* Give the bufctl back to the parent slab */
658                 a_bufctl = __yank_bufctl(cp, buf);
659                 a_slab = a_bufctl->my_slab;
660                 BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
661         }
662         a_slab->num_busy_obj--;
663         cp->nr_cur_alloc--;
664         // if it was full, move it to partial
665         if (a_slab->num_busy_obj + 1 == a_slab->num_total_obj) {
666                 TAILQ_REMOVE(&cp->full_slab_list, a_slab, link);
667                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
668         } else if (!a_slab->num_busy_obj) {
669                 // if there are none, move to from partial to empty
670                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
671                 TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
672         }
673         spin_unlock_irqsave(&cp->cache_lock);
674 }
675
676 void kmem_cache_free(struct kmem_cache *kc, void *buf)
677 {
678         struct kmem_pcpu_cache *pcc = get_my_pcpu_cache(kc);
679         struct kmem_depot *depot = &kc->depot;
680         struct kmem_magazine *mag;
681
682         assert(buf);    /* catch bugs */
683         kmem_trace_free(kc, buf);
684         lock_pcu_cache(pcc);
685 try_free:
686         if (pcc->loaded->nr_rounds < pcc->magsize) {
687                 pcc->loaded->rounds[pcc->loaded->nr_rounds] = buf;
688                 pcc->loaded->nr_rounds++;
689                 unlock_pcu_cache(pcc);
690                 return;
691         }
692         /* The paper checks 'is empty' here.  But we actually just care if it
693          * has room left, not that prev is completely empty.  This could be the
694          * case due to magazine resize. */
695         if (pcc->prev->nr_rounds < pcc->magsize) {
696                 __swap_mags(pcc);
697                 goto try_free;
698         }
699         lock_depot(depot);
700         /* Here's where the resize magic happens.  We'll start using it for the
701          * next magazine. */
702         pcc->magsize = depot->magsize;
703         mag = SLIST_FIRST(&depot->empty);
704         if (mag) {
705                 SLIST_REMOVE_HEAD(&depot->empty, link);
706                 depot->nr_empty--;
707                 __return_to_depot(kc, pcc->prev);
708                 unlock_depot(depot);
709                 pcc->prev = pcc->loaded;
710                 pcc->loaded = mag;
711                 goto try_free;
712         }
713         unlock_depot(depot);
714         /* Need to unlock, in case we end up calling back into ourselves. */
715         unlock_pcu_cache(pcc);
716         /* don't want to wait on a free.  if this fails, we can still just give
717          * it to the slab layer. */
718         mag = kmem_cache_alloc(kmem_magazine_cache, MEM_ATOMIC);
719         if (mag) {
720                 assert(mag->nr_rounds == 0);
721                 lock_depot(depot);
722                 SLIST_INSERT_HEAD(&depot->empty, mag, link);
723                 depot->nr_empty++;
724                 unlock_depot(depot);
725                 lock_pcu_cache(pcc);
726                 goto try_free;
727         }
728         if (kc->dtor)
729                 kc->dtor(buf, kc->priv);
730         __kmem_free_to_slab(kc, buf);
731 }
732
733 /* Back end: internal functions */
734 /* When this returns, the cache has at least one slab in the empty list.  If
735  * page_alloc fails, there are some serious issues.  This only grows by one slab
736  * at a time.
737  *
738  * Grab the cache lock before calling this.
739  *
740  * TODO: think about page colouring issues with kernel memory allocation. */
741 static bool kmem_cache_grow(struct kmem_cache *cp)
742 {
743         struct kmem_slab *a_slab;
744         struct kmem_bufctl *a_bufctl;
745
746         if (!__use_bufctls(cp)) {
747                 void *a_page;
748
749                 /* Careful, this assumes our source is a PGSIZE-aligned
750                  * allocator.  We could use xalloc to enforce the alignment, but
751                  * that'll bypass the qcaches, which we don't want.  Caller
752                  * beware. */
753                 a_page = arena_alloc(cp->source, PGSIZE, MEM_ATOMIC);
754                 if (!a_page)
755                         return FALSE;
756                 // the slab struct is stored at the end of the page
757                 a_slab = (struct kmem_slab*)(a_page + PGSIZE
758                                              - sizeof(struct kmem_slab));
759                 a_slab->num_busy_obj = 0;
760                 a_slab->num_total_obj = (PGSIZE - sizeof(struct kmem_slab)) /
761                                         cp->obj_size;
762                 // TODO: consider staggering this IAW section 4.3
763                 a_slab->free_small_obj = a_page;
764                 /* Walk and create the free list, which is circular.  Each item
765                  * stores the location of the next one at the beginning of the
766                  * block. */
767                 void *buf = a_slab->free_small_obj;
768
769                 for (int i = 0; i < a_slab->num_total_obj - 1; i++) {
770                         *(uintptr_t**)buf = buf + cp->obj_size;
771                         buf += cp->obj_size;
772                 }
773                 *((uintptr_t**)buf) = NULL;
774         } else {
775                 void *buf;
776
777                 a_slab = kmem_cache_alloc(kmem_slab_cache, 0);
778                 if (!a_slab)
779                         return FALSE;
780                 buf = arena_alloc(cp->source, cp->import_amt, MEM_ATOMIC);
781                 if (!buf) {
782                         kmem_cache_free(kmem_slab_cache, a_slab);
783                         return FALSE;
784                 }
785                 a_slab->num_busy_obj = 0;
786                 a_slab->num_total_obj = cp->import_amt / cp->obj_size;
787                 BSD_LIST_INIT(&a_slab->bufctl_freelist);
788                 /* for each buffer, set up a bufctl and point to the buffer */
789                 for (int i = 0; i < a_slab->num_total_obj; i++) {
790                         a_bufctl = kmem_cache_alloc(kmem_bufctl_cache, 0);
791                         BSD_LIST_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl,
792                                              link);
793                         a_bufctl->buf_addr = buf;
794                         a_bufctl->my_slab = a_slab;
795                         buf += cp->obj_size;
796                 }
797         }
798         // add a_slab to the empty_list
799         TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
800
801         return TRUE;
802 }
803
804 /* This deallocs every slab from the empty list.  TODO: think a bit more about
805  * this.  We can do things like not free all of the empty lists to prevent
806  * thrashing.  See 3.4 in the paper. */
807 void kmem_cache_reap(struct kmem_cache *cp)
808 {
809         struct kmem_slab *a_slab, *next;
810
811         // Destroy all empty slabs.  Refer to the notes about the while loop
812         spin_lock_irqsave(&cp->cache_lock);
813         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
814         while (a_slab) {
815                 next = TAILQ_NEXT(a_slab, link);
816                 kmem_slab_destroy(cp, a_slab);
817                 a_slab = next;
818         }
819         spin_unlock_irqsave(&cp->cache_lock);
820 }
821
822
823 /* Tracing */
824
825 static void kmem_trace_ht_foreach(struct kmem_trace_ht *ht,
826                                   void (*f)(struct kmem_trace *, void *),
827                                   void *arg)
828 {
829         struct kmem_trace *tr;
830         struct hlist_node *temp;
831
832         spin_lock_irqsave(&ht->lock);
833         for (int i = 0; i < ht->hh.nr_hash_lists; i++)
834                 hlist_for_each_entry_safe(tr, temp, &ht->ht[i], hash)
835                         f(tr, arg);
836         spin_unlock_irqsave(&ht->lock);
837 }
838
839 static void __kmem_trace_print(struct kmem_trace *tr, void *arg)
840 {
841         struct sized_alloc *sza = arg;
842
843         sza_printf(sza, "Obj %p, from %s:\n----\n", tr->obj, tr->str);
844         sza_print_backtrace_list(sza, tr->pcs, tr->nr_pcs);
845         sza_printf(sza, "\n");
846 }
847
848 static void __kmem_trace_bytes_needed(struct kmem_trace *tr, void *arg)
849 {
850         size_t *x = arg;
851
852         /* Just a guess of how much room we'll need, plus fudge. */
853         *x += tr->nr_pcs * 80 + 100;
854 }
855
856 struct sized_alloc *kmem_trace_print(struct kmem_cache *kc)
857 {
858         struct sized_alloc *sza;
859         size_t amt = 100;
860
861         kmem_trace_ht_foreach(&kc->trace_ht, __kmem_trace_bytes_needed, &amt);
862         sza = sized_kzmalloc(amt, MEM_WAIT);
863         sza_printf(sza, "Dumping outstanding allocs from %s\n", kc->name);
864         sza_printf(sza, "-------------------------\n");
865         kmem_trace_ht_foreach(&kc->trace_ht, __kmem_trace_print, sza);
866         return sza;
867 }
868
869 static void __kmem_trace_drop(struct kmem_trace *tr, void *arg)
870 {
871         hlist_del(&tr->hash);
872         kmem_cache_free(kmem_trace_cache, tr);
873 }
874
875 void kmem_trace_reset(struct kmem_cache *kc)
876 {
877         kmem_trace_ht_foreach(&kc->trace_ht, __kmem_trace_drop, NULL);
878 }
879
880 /* It's a bug to ever have a left-over trace when we delete a KMC, and probably
881  * will never happen.  If it does, we can expand the debugging info. */
882 static void __kmem_trace_warn_and_drop(struct kmem_trace *tr, void *arg)
883 {
884         warn("KMC had an object! (%p)", tr->obj);
885         __kmem_trace_drop(tr, NULL);
886 }
887
888 static void kmem_trace_warn_notempty(struct kmem_cache *kc)
889 {
890         kmem_trace_ht_foreach(&kc->trace_ht, __kmem_trace_warn_and_drop, NULL);
891 }
892
893 int kmem_trace_start(struct kmem_cache *kc)
894 {
895         spin_lock_irqsave(&kc->cache_lock);
896         if (kc->flags & KMC_NOTRACE) {
897                 spin_unlock_irqsave(&kc->cache_lock);
898                 return -1;
899         }
900         WRITE_ONCE(kc->flags, kc->flags | __KMC_TRACED | __KMC_EVER_TRACED);
901         spin_unlock_irqsave(&kc->cache_lock);
902         return 0;
903 }
904
905 /* Note that the tracers locklessly-peek at the flags, and we may have an
906  * allocation complete its trace after we stop.  You could conceivably stop,
907  * reset/remove all traces, and then have a trace appear still. */
908 void kmem_trace_stop(struct kmem_cache *kc)
909 {
910         spin_lock_irqsave(&kc->cache_lock);
911         WRITE_ONCE(kc->flags, kc->flags & ~__KMC_TRACED);
912         spin_unlock_irqsave(&kc->cache_lock);
913 }
914
915 static void kmem_trace_ht_init(struct kmem_trace_ht *ht)
916 {
917         spinlock_init(&ht->lock);
918         ht->ht = ht->static_ht;
919         hash_init_hh(&ht->hh);
920         for (int i = 0; i < ht->hh.nr_hash_lists; i++)
921                 INIT_HLIST_HEAD(&ht->ht[i]);
922 }
923
924 static void kmem_trace_ht_insert(struct kmem_trace_ht *ht,
925                                  struct kmem_trace *tr)
926 {
927         unsigned long hash_val = __generic_hash(tr->obj);
928         struct hlist_head *bucket;
929
930         spin_lock_irqsave(&ht->lock);
931         bucket = &ht->ht[hash_val % ht->hh.nr_hash_bits];
932         hlist_add_head(&tr->hash, bucket);
933         spin_unlock_irqsave(&ht->lock);
934 }
935
936 static struct kmem_trace *kmem_trace_ht_remove(struct kmem_trace_ht *ht,
937                                                void *obj)
938 {
939         struct kmem_trace *tr;
940         unsigned long hash_val = __generic_hash(obj);
941         struct hlist_head *bucket;
942
943         spin_lock_irqsave(&ht->lock);
944         bucket = &ht->ht[hash_val % ht->hh.nr_hash_bits];
945         hlist_for_each_entry(tr, bucket, hash) {
946                 if (tr->obj == obj) {
947                         hlist_del(&tr->hash);
948                         break;
949                 }
950         }
951         spin_unlock_irqsave(&ht->lock);
952         return tr;
953 }
954
955 static void kmem_trace_free(struct kmem_cache *kc, void *obj)
956 {
957         struct kmem_trace *tr;
958
959         /* Even if we turn off tracing, we still want to free traces that we may
960          * have collected earlier.  Otherwise, those objects will never get
961          * removed from the trace, and could lead to confusion if they are
962          * reallocated and traced again.  Still, we don't want to pay the cost
963          * on every free for untraced KCs. */
964         if (!(READ_ONCE(kc->flags) & __KMC_EVER_TRACED))
965                 return;
966         tr = kmem_trace_ht_remove(&kc->trace_ht, obj);
967         if (tr)
968                 kmem_cache_free(kmem_trace_cache, tr);
969 }
970
971 static void trace_context(struct kmem_trace *tr)
972 {
973         if (is_ktask(current_kthread)) {
974                 snprintf(tr->str, sizeof(tr->str), "ktask %s",
975                          current_kthread->name);
976         } else if (current) {
977                 /* When we're handling a page fault, knowing the user PC helps
978                  * determine the source.  A backtrace is nice, but harder to do.
979                  * Since we're deep in MM code and holding locks, we can't use
980                  * copy_from_user, which uses the page-fault fixups.  If you
981                  * need to get the BT, stash it in the genbuf in
982                  * handle_page_fault(). */
983                 snprintf(tr->str, sizeof(tr->str), "PID %d %s: %s, %p",
984                          current->pid, current->progname,
985                          current_kthread->name,
986                          current_ctx ? get_user_ctx_pc(current_ctx) : 0);
987         } else {
988                 snprintf(tr->str, sizeof(tr->str), "(none)");
989         }
990         tr->str[sizeof(tr->str) - 1] = 0;
991 }
992
993 static void kmem_trace_alloc(struct kmem_cache *kc, void *obj)
994 {
995         struct kmem_trace *tr;
996
997         if (!(READ_ONCE(kc->flags) & __KMC_TRACED))
998                 return;
999         tr = kmem_cache_alloc(kmem_trace_cache, MEM_ATOMIC);
1000         if (!tr)
1001                 return;
1002         tr->obj = obj;
1003         tr->nr_pcs = backtrace_list(get_caller_pc(), get_caller_fp(), tr->pcs,
1004                                     ARRAY_SIZE(tr->pcs));
1005         trace_context(tr);
1006         kmem_trace_ht_insert(&kc->trace_ht, tr);
1007 }