arena: Connecting importers with sources
[akaros.git] / kern / src / arena.c
1 /* Copyright (c) 2016 Google Inc
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Arena resource allocator, based on Bonwick and Adams's "Magazines and Vmem:
6  * Extending the Slab Allocator to Many CPUs and Arbitrary Resources".
7  *
8  * There are two major arenas (or arena types; see the NUMA discussion below):
9  * base_arena and kpages_arena.  The base_arena consists of all the virtual
10  * addresses of the KERNBASE mapping, and is entirely self-sufficient.  Some
11  * slab caches pull directly from this arena.  The kpages_arena pulls from the
12  * base_arena and adds a level of quantum/slab caching.  Most users will pull
13  * from kpages_arena.
14  *
15  * For jumbo pages, you'd think we'd want a larger page sizes to be the source
16  * for the smaller page size arenas.  E.g. 'base' is a PML3 allocator.  The
17  * problem with that is that a base allocator needs to be self-sufficient, which
18  * means it needs to allocate its own boundary tags.  We'd prefer to use a small
19  * page for that.  So instead, we can flip the hierarchy around.  A base
20  * allocator uses a PGSIZE quantum, and the jumbo allocators are source from
21  * the base arena using an aligned allocation helper for its afunc.  I think,
22  * without a lot of thought, that the fragmentation would be equivalent.
23  *
24  * In the future, we can set up N base_arenas, one for each NUMA domain, each of
25  * which is a source for other NUMA allocators, e.g. kpages_i_arena.  Higher
26  * level allocators (kmalloc()) will need to choose a NUMA domain and call into
27  * the correct allocator.  Each NUMA base arena is self-sufficient: they have no
28  * qcaches and their BTs come from their own free page list.  This just
29  * replicates the default memory allocator across each NUMA node, and at some
30  * point, some generic allocator software needs to pick which node to pull from.
31  * I tried to keep assumptions about a single base_arena to a minimum, but
32  * you'll see some places where the arena code needs to find some base arena for
33  * its BT allocations.  Also note that the base setup happens before we know
34  * about NUMA domains.  The plan is to do a small part of domain 0 during
35  * pmem_init(), then once we know the full memory layout, add in the rest of
36  * domain 0's memory and bootstrap the other domains.
37  *
38  * When it comes to importing spans, it's not clear whether or not we should
39  * import exactly the current allocation request or to bring in more.  If we
40  * don't bring in more, then a child arena will have a span for every allocation
41  * and will return that span to the source whenever the segment is freed.  We'll
42  * never get the Figure 4.4 from the Vmem paper.  Alternatively, we could either
43  * allow partial frees of segments or we could hang on to completely free spans
44  * for a *while*, and possibly require a reclaim callback.  In the meantime, I
45  * added a per-arena scaling factor where we can adjust how much we import.
46  *
47  * TODO:
48  * - Blocking.  We'll probably want to reserve some memory for emergencies to
49  *   help us get out of OOM.  So we might block when we're at low-mem, not at 0.
50  *   We probably should have a sorted list of desired amounts, and unblockers
51  *   poke the CV if the first waiter is likely to succeed.
52  * - qcaching
53  * - We'll need some linkage between sources and parent arenas, with callbacks
54  *   or something when the base arena starts to run low on memory.  Once an
55  *   arena (whether base or o/w) gets the "time to free up memory" call, it can
56  *   call into any of its children, to include slabs and whatever else.
57  *
58  * FAQ:
59  * - Does allocating memory from an arena require it to take a btag?  Yes -
60  *   unless the allocation is for the exact size of an existing btag/segment.
61  * - Why does arena_free() need size?  Isn't it just for sanity checks?  No - it
62  *   is also used to determine which slab/qcache to return the segment to.
63  * - Why does a jumbo page arena use its own import function, instead of just
64  *   xallocing from kpages with alignment?  Because of fragmentation.  kpages
65  *   pulls directly from base, using a normal alloc for its import function
66  *   (afunc).  Because of this, its xalloc needs to request size + align, which
67  *   will fragment base.  It's better for jumbo to call xalloc directly on base,
68  *   in essence pushing the aligned alloc as far down the stack as possible.
69  * - Does the stuff in a qcache (allocated or free/available) count against the
70  *   arena's total/free amounts?  No, at least not the way I did it.  That's why
71  *   it's called amt_total_segs: segments, not free memory.  Those slab/qcaches
72  *   will have their own stats, and it'd be a minor pain to sync up with them
73  *   all the time.  Also, the important stat is when the base arena starts to
74  *   run out of memory, and base arenas don't have qcaches, so it's moot.
75  */
76
77 #include <arena.h>
78 #include <kmalloc.h>
79 #include <string.h>
80 #include <stdio.h>
81 #include <hash.h>
82 #include <slab.h>
83 #include <kthread.h>
84
85 static struct arena_tailq all_arenas = TAILQ_HEAD_INITIALIZER(all_arenas);
86 static spinlock_t all_arenas_lock = SPINLOCK_INITIALIZER;
87 qlock_t arenas_and_slabs_lock = QLOCK_INITIALIZER(arenas_and_slabs_lock);
88
89 struct arena *base_arena;
90 struct arena *kpages_arena;
91
92 /* Misc helpers and forward declarations */
93 static struct btag *__get_from_freelists(struct arena *arena, int list_idx);
94 static bool __account_alloc(struct arena *arena, struct btag *bt, size_t size,
95                             struct btag *new);
96 static void *__xalloc_nextfit(struct arena *arena, size_t size, size_t align,
97                               size_t phase, size_t nocross);
98 static void __try_hash_resize(struct arena *arena, int flags,
99                               void **to_free_addr, size_t *to_free_sz);
100 static void __arena_asserter(struct arena *arena);
101 void print_arena_stats(struct arena *arena, bool verbose);
102
103 /* For NUMA situations, where there are multiple base arenas, we'll need a way
104  * to find *some* base arena.  Ideally, it'll be in the same NUMA domain as
105  * arena. */
106 static struct arena *find_my_base(struct arena *arena)
107 {
108         /* TODO: could walk down sources until is_base is set.  But barring that,
109          * we'd still need a way to find a base arena for some other allocator that
110          * just wants a page.  arena may be NULL, so handle that. */
111         return base_arena;
112 }
113
114 static void setup_qcaches(struct arena *arena, size_t quantum,
115                           size_t qcache_max)
116 {
117         int nr_qcaches = qcache_max / quantum;
118         char kc_name[KMC_NAME_SZ];
119         size_t qc_size;
120
121         if (!nr_qcaches)
122                 return;
123
124         /* TODO: same as with hash tables, here and in slab.c, we ideally want the
125          * nearest kpages arena, but bootstrappers need to use base_alloc. */
126         arena->qcaches = base_alloc(arena, nr_qcaches * sizeof(struct kmem_cache),
127                                     MEM_WAIT);
128         for (int i = 0; i < nr_qcaches; i++) {
129                 qc_size = (i + 1) * quantum;
130                 snprintf(kc_name, KMC_NAME_SZ, "%s_%d", arena->name, qc_size);
131                 __kmem_cache_create(&arena->qcaches[i], kc_name, qc_size, quantum,
132                                     KMC_NOTOUCH | KMC_QCACHE, arena, NULL, NULL);
133         }
134 }
135
136 /* Helper to init.  Split out from create so we can bootstrap. */
137 static void arena_init(struct arena *arena, char *name, size_t quantum,
138                        void *(*afunc)(struct arena *, size_t, int),
139                        void (*ffunc)(struct arena *, void *, size_t),
140                        struct arena *source, size_t qcache_max)
141 {
142         static_assert((ARENA_ALLOC_STYLES & MEM_FLAGS) == 0);
143
144         spinlock_init_irqsave(&arena->lock);
145         arena->import_scale = 0;
146         arena->is_base = FALSE;
147         if (qcache_max % quantum)
148                 panic("Arena %s, qcache_max %p must be a multiple of quantum %p",
149                       name, qcache_max, quantum);
150         arena->quantum = quantum;
151         arena->qcache_max = qcache_max;
152         arena->afunc = afunc;
153         arena->ffunc = ffunc;
154         arena->source = source;
155         if (source)
156                 assert(afunc && ffunc);
157         arena->amt_total_segs = 0;
158         arena->amt_alloc_segs = 0;
159         arena->nr_allocs_ever = 0;
160
161         arena->all_segs = RB_ROOT;
162         BSD_LIST_INIT(&arena->unused_btags);
163         for (int i = 0; i < ARENA_NR_FREE_LISTS; i++)
164                 BSD_LIST_INIT(&arena->free_segs[i]);
165
166         arena->alloc_hash = arena->static_hash;
167         hash_init_hh(&arena->hh);
168         for (int i = 0; i < arena->hh.nr_hash_lists; i++)
169                 BSD_LIST_INIT(&arena->static_hash[i]);
170
171         TAILQ_INIT(&arena->__importing_arenas);
172         TAILQ_INIT(&arena->__importing_slabs);
173
174         strlcpy(arena->name, name, ARENA_NAME_SZ);
175         setup_qcaches(arena, quantum, qcache_max);
176
177         if (source)
178                 add_importing_arena(source, arena);
179         spin_lock(&all_arenas_lock);
180         TAILQ_INSERT_TAIL(&all_arenas, arena, next);
181         spin_unlock(&all_arenas_lock);
182 }
183
184 struct arena *arena_create(char *name, void *base, size_t size, size_t quantum,
185                            void *(*afunc)(struct arena *, size_t, int),
186                            void (*ffunc)(struct arena *, void *, size_t),
187                            struct arena *source, size_t qcache_max, int flags)
188 {
189         struct arena *arena;
190
191         /* See note in arena_add() */
192         if (source && base)
193                 panic("Arena can't have both a source and an initial span");
194         arena = kmalloc(sizeof(struct arena), flags);
195         if (!arena)
196                 return 0;
197         arena_init(arena, name, quantum, afunc, ffunc, source, qcache_max);
198         if (base) {
199                 if (!arena_add(arena, base, size, flags)) {
200                         warn("Failed to add base to arena %s, aborting!", arena->name);
201                         arena_destroy(arena);
202                         return 0;
203                 }
204         }
205         return arena;
206 }
207
208 void arena_destroy(struct arena *arena)
209 {
210         struct btag *bt_i, *temp;
211
212         spin_lock(&all_arenas_lock);
213         TAILQ_REMOVE(&all_arenas, arena, next);
214         spin_unlock(&all_arenas_lock);
215         if (arena->source)
216                 del_importing_arena(arena->source, arena);
217
218         for (int i = 0; i < arena->hh.nr_hash_lists; i++)
219                 assert(BSD_LIST_EMPTY(&arena->alloc_hash[i]));
220         if (arena->alloc_hash != arena->static_hash)
221                 kfree(arena->alloc_hash);
222         /* We shouldn't have any spans left.  We can tell we messed up if we had a
223          * source and still have some free segments.  Otherwise, just collect the
224          * free tags on the unused btag list. */
225         for (int i = 0; i < ARENA_NR_FREE_LISTS; i++) {
226                 if (arena->source)
227                         assert(BSD_LIST_EMPTY(&arena->free_segs[i]));
228                 BSD_LIST_FOREACH_SAFE(bt_i, &arena->free_segs[i], misc_link, temp) {
229                         BSD_LIST_REMOVE(bt_i, misc_link);
230                         BSD_LIST_INSERT_HEAD(&arena->unused_btags, bt_i, misc_link);
231                 }
232         }
233         /* To free our BTs, we need to give the page back to the base arena.  The
234          * BTs that are page aligned are the ones we want.  We can just ignore the
235          * others (unlink from the list). */
236         BSD_LIST_FOREACH_SAFE(bt_i, &arena->unused_btags, misc_link, temp) {
237                 if (PGOFF(bt_i->start))
238                         BSD_LIST_REMOVE(bt_i, misc_link);
239         }
240         /* Now the remaining BTs are the first on their page. */
241         BSD_LIST_FOREACH_SAFE(bt_i, &arena->unused_btags, misc_link, temp)
242                 arena_free(find_my_base(arena), (void*)bt_i->start, PGSIZE);
243         kfree(arena);
244 }
245
246 static void __insert_btag(struct rb_root *root, struct btag *bt)
247 {
248         struct rb_node **new = &root->rb_node, *parent = NULL;
249         struct btag *node;
250
251         while (*new) {
252                 node = container_of(*new, struct btag, all_link);
253                 parent = *new;
254                 /* Span (BTAG_SPAN) nodes are ahead (less than) of regular segment nodes
255                  * (BTAG_FREE or BTAG_ALLOC) that have the same start. */
256                 if (bt->start < node->start)
257                         new = &parent->rb_left;
258                 else if (bt->start > node->start)
259                         new = &parent->rb_right;
260                 else if (node->status == BTAG_SPAN)
261                         new = &parent->rb_right;
262                 else
263                         panic("BT %p already in tree %p!", bt, root);
264         }
265         rb_link_node(&bt->all_link, parent, new);
266         rb_insert_color(&bt->all_link, root);
267 }
268
269 /* Helper: tracks a seg pointed to by @bt as being allocated, assuming it is
270  * already off the free list (or was never on).  This doesn't do anything with
271  * all_segs; that's someone else's job (usually bt is already on it). */
272 static void __track_alloc_seg(struct arena *arena, struct btag *bt)
273 {
274         size_t hash_idx;
275
276         bt->status = BTAG_ALLOC;
277         hash_idx = hash_long(bt->start, arena->hh.nr_hash_bits);
278         BSD_LIST_INSERT_HEAD(&arena->alloc_hash[hash_idx], bt, misc_link);
279         arena->hh.nr_items++;
280 }
281
282 /* Helper: untracks a seg pointed to by @bt as being allocated.  Basically,
283  * removes it from the alloc_hash. */
284 static struct btag *__untrack_alloc_seg(struct arena *arena, uintptr_t start)
285 {
286         size_t hash_idx;
287         struct btag *bt_i;
288
289         hash_idx = hash_long(start, arena->hh.nr_hash_bits);
290         BSD_LIST_FOREACH(bt_i, &arena->alloc_hash[hash_idx], misc_link) {
291                 if (bt_i->start == start) {
292                         BSD_LIST_REMOVE(bt_i, misc_link);
293                         assert(bt_i->status == BTAG_ALLOC);
294                         arena->hh.nr_items--;
295                         return bt_i;
296                 }
297         }
298         return NULL;
299 }
300
301 /* Helper, tries to resize our hash table, if necessary.  Call with the lock
302  * held, but beware that this will unlock and relock - meaning, don't rely on
303  * the lock to protect invariants, but hold it as an optimization.
304  *
305  * A lot of the nastiness here is related to the allocation.  Critically, we
306  * might be the base arena, so it'd be nice to unlock before calling into
307  * ourselves (o/w deadlock).  Likewise, we'd like to be able to do a blocking
308  * allocation, if flags has MEM_WAIT.  We'd need to unlock for that too. */
309 static void __try_hash_resize(struct arena *arena, int flags,
310                               void **to_free_addr, size_t *to_free_sz)
311 {
312         struct btag_list *new_tbl, *old_tbl;
313         struct btag *bt_i;
314         unsigned int new_tbl_nr_lists, old_tbl_nr_lists;
315         size_t new_tbl_sz, old_tbl_sz;
316         size_t hash_idx;
317
318         if (!hash_needs_more(&arena->hh))
319                 return;
320         new_tbl_nr_lists = hash_next_nr_lists(&arena->hh);
321         /* We want future checkers to not think we need an increase, to avoid
322          * excessive hash resizers as well as base arena deadlocks (base_alloc must
323          * not call into base_alloc infinitely) */
324         hash_set_load_limit(&arena->hh, SIZE_MAX);
325         spin_unlock_irqsave(&arena->lock);
326         new_tbl_sz = new_tbl_nr_lists * sizeof(struct btag_list);
327         /* Regardless of the caller's style, we'll try and be quick with INSTANT. */
328         flags &= ~ARENA_ALLOC_STYLES;
329         flags |= ARENA_INSTANTFIT;
330         new_tbl = base_zalloc(arena, new_tbl_sz, flags);
331         spin_lock_irqsave(&arena->lock);
332         if (!new_tbl) {
333                 /* Need to reset so future callers will try to grow. */
334                 hash_reset_load_limit(&arena->hh);
335                 spin_unlock_irqsave(&arena->lock);
336                 return;
337         }
338         /* After relocking, we need to re-verify that we want to go ahead.  It's
339          * possible that another thread resized the hash already, which we can
340          * detect because our alloc size is wrong. */
341         if (new_tbl_nr_lists != hash_next_nr_lists(&arena->hh)) {
342                 spin_unlock_irqsave(&arena->lock);
343                 base_free(arena, new_tbl, new_tbl_sz);
344                 return;
345         }
346         old_tbl = arena->alloc_hash;
347         old_tbl_nr_lists = arena->hh.nr_hash_lists;
348         old_tbl_sz = old_tbl_nr_lists * sizeof(struct btag_list);
349         arena->alloc_hash = new_tbl;
350         hash_incr_nr_lists(&arena->hh);
351         for (int i = 0; i < old_tbl_nr_lists; i++) {
352                 while ((bt_i = BSD_LIST_FIRST(&old_tbl[i]))) {
353                         BSD_LIST_REMOVE(bt_i, misc_link);
354                         hash_idx = hash_long(bt_i->start, arena->hh.nr_hash_bits);
355                         BSD_LIST_INSERT_HEAD(&arena->alloc_hash[hash_idx], bt_i, misc_link);
356                 }
357         }
358         hash_reset_load_limit(&arena->hh);
359         if (old_tbl != arena->static_hash) {
360                 *to_free_addr = old_tbl;
361                 *to_free_sz = old_tbl_sz;
362         }
363 }
364
365 /* Typically this will be just checking for one or two BTs on the free list */
366 static bool __has_enough_btags(struct arena *arena, size_t nr_needed)
367 {
368         struct btag *bt_i;
369         size_t so_far = 0;
370
371         BSD_LIST_FOREACH(bt_i, &arena->unused_btags, misc_link) {
372                 so_far++;
373                 if (so_far == nr_needed)
374                         return TRUE;
375         }
376         return FALSE;
377 }
378
379 /* Allocs new boundary tags and puts them on the arena's free list.  Returns 0
380  * on failure, which could happen if MEM_ATOMIC is set).  Hold the lock when you
381  * call this, but note it will unlock and relock.
382  *
383  * The base arena is special in that it must be self-sufficient.  It will create
384  * get its free page from itself.  Other arena's just pull from base in the
385  * normal fashion.  We could pull from kpages_arena, but that would require a
386  * little more special casing.  Maybe in the future.
387  *
388  * Note that BTs are only freed when the arena is destroyed.  We use the fact
389  * that the first BT is at an aligned address to track the specific page it came
390  * from. */
391 static struct btag *__add_more_btags(struct arena *arena, int mem_flags)
392 {
393         struct btag *bt, *tags;
394         size_t nr_bts = PGSIZE / sizeof(struct btag);
395
396         if (arena->is_base) {
397                 bt = __get_from_freelists(arena, LOG2_UP(PGSIZE));
398                 if (!bt) {
399                         /* TODO: block / reclaim if not MEM_ATOMIC.  Remember, we hold the
400                          * lock!  We might need to rework this or get a reserved page. */
401                         if (!(mem_flags & MEM_ATOMIC))
402                                 panic("Base failed to alloc its own btag, OOM!");
403                         return 0;
404                 }
405                 /* __account_alloc() will often need a new BT; specifically when we
406                  * only need part of the segment tracked by the BT.  Since we don't have
407                  * any extra BTs, we'll use the first one on the page we just allocated.
408                  */
409                 tags = (struct btag*)bt->start;
410                 if (__account_alloc(arena, bt, PGSIZE, &tags[0])) {
411                         /* We used the tag[0]; we'll have to skip over it now. */
412                         tags++;
413                         nr_bts--;
414                 }
415         } else {
416                 /* Here's where we unlock and relock around a blocking call */
417                 spin_unlock_irqsave(&arena->lock);
418                 tags = arena_alloc(find_my_base(arena), PGSIZE,
419                                    mem_flags | ARENA_INSTANTFIT);
420                 spin_lock_irqsave(&arena->lock);
421                 if (!tags)
422                         return 0;
423         }
424         for (int i = 0; i < nr_bts; i++)
425                 BSD_LIST_INSERT_HEAD(&arena->unused_btags, &tags[i], misc_link);
426         return tags;
427 }
428
429 /* Helper, returns TRUE when we have enough BTs.  Hold the lock, but note this
430  * will unlock and relock, and will attempt to acquire more BTs.  Returns FALSE
431  * if an alloc failed (MEM_ATOMIC).
432  *
433  * This complexity is so that we never fail an arena operation due to lack of
434  * memory unless the caller has MEM_ATOMIC set.  Further, __get_btag() never
435  * fails, which makes other code easier.  Otherwise, functions that currently
436  * call __get_btag will need one or two BTs passed in from their callers, who
437  * allocate/remove from the list at a place where they can easily fail. */
438 static bool __get_enough_btags(struct arena *arena, size_t nr_needed,
439                                int mem_flags)
440 {
441         if (__has_enough_btags(arena, nr_needed))
442                 return TRUE;
443         /* This will unlock and relock, and maybe block. */
444         if (!__add_more_btags(arena, mem_flags)) {
445                 /* This is the only failure scenario */
446                 assert(mem_flags & MEM_ATOMIC);
447                 return FALSE;
448         }
449         /* Since the lock was held in __add_more_btags, no one should have been able
450          * to drain them.  If someone asked for more than a page worth of BTs,
451          * there's a problem somewhere else. */
452         assert(__has_enough_btags(arena, nr_needed));
453         return TRUE;
454 }
455
456 /* Helper: gets a btag.  All callpaths must have made sure the arena has enough
457  * tags before starting its operation, holding the lock throughout.  Thus, this
458  * cannot fail. */
459 static struct btag *__get_btag(struct arena *arena)
460 {
461         struct btag *ret;
462
463         ret = BSD_LIST_FIRST(&arena->unused_btags);
464         /* All code paths should have made sure that there were enough BTs before
465          * diving in. */
466         assert(ret);
467         BSD_LIST_REMOVE(ret, misc_link);
468         return ret;
469 }
470
471 static void __free_btag(struct arena *arena, struct btag *bt)
472 {
473         BSD_LIST_INSERT_HEAD(&arena->unused_btags, bt, misc_link);
474 }
475
476 /* Helper: adds seg pointed to by @bt to the appropriate free list of @arena. */
477 static void __track_free_seg(struct arena *arena, struct btag *bt)
478 {
479         int list_idx = LOG2_DOWN(bt->size);
480
481         bt->status = BTAG_FREE;
482         BSD_LIST_INSERT_HEAD(&arena->free_segs[list_idx], bt, misc_link);
483 }
484
485 /* Helper: removes seg pointed to by @bt from the appropriate free list of
486  * @arena. */
487 static void __untrack_free_seg(struct arena *arena, struct btag *bt)
488 {
489         BSD_LIST_REMOVE(bt, misc_link);
490 }
491
492 /* Helper: we decided we want to alloc part of @bt, which has been removed from
493  * its old list.  We need @size units.  The rest can go back to the arena.
494  *
495  * Takes @new, which we'll use if we need a new btag.  If @new is NULL, we'll
496  * allocate one.  If we used the caller's btag, we'll return TRUE.  This
497  * complexity is for a base arena's manual btag allocation. */
498 static bool __account_alloc(struct arena *arena, struct btag *bt,
499                             size_t size, struct btag *new)
500 {
501         bool ret = FALSE;
502
503         assert(bt->status == BTAG_FREE);
504         if (bt->size != size) {
505                 assert(bt->size > size);
506                 if (new)
507                         ret = TRUE;
508                 else
509                         new = __get_btag(arena);
510                 new->start = bt->start + size;
511                 new->size = bt->size - size;
512                 bt->size = size;
513                 __track_free_seg(arena, new);
514                 __insert_btag(&arena->all_segs, new);
515         }
516         __track_alloc_seg(arena, bt);
517         arena->amt_alloc_segs += size;
518         arena->nr_allocs_ever++;
519         return ret;
520 }
521
522 /* Helper: gets the first segment from the smallest, populated list. */
523 static struct btag *__get_from_freelists(struct arena *arena, int list_idx)
524 {
525         struct btag *ret = NULL;
526
527         for (int i = list_idx; i < ARENA_NR_FREE_LISTS; i++) {
528                 ret = BSD_LIST_FIRST(&arena->free_segs[i]);
529                 if (ret) {
530                         BSD_LIST_REMOVE(ret, misc_link);
531                         break;
532                 }
533         }
534         return ret;
535 }
536
537 /* Allocates using the 'best fit' policy.  Recall that each free_segs list holds
538  * segments of size [ 2^n, 2^(n+1) )  We try to find the smallest segment on
539  * that list that can satisfy the request.  Otherwise, any segment from a larger
540  * list will suffice. */
541 static void *__alloc_bestfit(struct arena *arena, size_t size)
542 {
543         int list_idx = LOG2_DOWN(size);
544         struct btag *bt_i, *best = NULL;
545
546         BSD_LIST_FOREACH(bt_i, &arena->free_segs[list_idx], misc_link) {
547                 if (bt_i->size >= size) {
548                         if (!best || (best->size > bt_i->size))
549                                 best = bt_i;
550                 }
551         }
552         if (best)
553                 BSD_LIST_REMOVE(best, misc_link);
554         else
555                 best = __get_from_freelists(arena, list_idx + 1);
556         if (!best)
557                 return NULL;
558         __account_alloc(arena, best, size, NULL);
559         return (void*)best->start;
560 }
561
562 static void *__alloc_nextfit(struct arena *arena, size_t size)
563 {
564         return __xalloc_nextfit(arena, size, arena->quantum, 0, 0);
565 }
566
567 /* Instant fit grabs the first segment guaranteed to be big enough.  Note that
568  * we round list_idx up, compared to bestfit's initial list.  That way, you're
569  * always sure you have a big enough segment. */
570 static void *__alloc_instantfit(struct arena *arena, size_t size)
571 {
572         struct btag *ret;
573
574         ret = __get_from_freelists(arena, LOG2_UP(size));
575         if (!ret)
576                 return NULL;
577         __account_alloc(arena, ret, size, NULL);
578         return (void*)ret->start;
579 }
580
581 /* Non-qcache allocation.  Hold the arena's lock.  Note that all allocations are
582  * done in multiples of the quantum. */
583 static void *alloc_from_arena(struct arena *arena, size_t size, int flags)
584 {
585         void *ret;
586         void *to_free_addr = 0;
587         size_t to_free_sz = 0;
588
589         spin_lock_irqsave(&arena->lock);
590         if (!__get_enough_btags(arena, 1, flags & MEM_FLAGS)) {
591                 spin_unlock_irqsave(&arena->lock);
592                 return NULL;
593         }
594         if (flags & ARENA_BESTFIT)
595                 ret = __alloc_bestfit(arena, size);
596         else if (flags & ARENA_NEXTFIT)
597                 ret = __alloc_nextfit(arena, size);
598         else
599                 ret = __alloc_instantfit(arena, size);
600         /* Careful, this will unlock and relock.  It's OK right before an unlock. */
601         __try_hash_resize(arena, flags, &to_free_addr, &to_free_sz);
602         spin_unlock_irqsave(&arena->lock);
603         if (to_free_addr)
604                 base_free(arena, to_free_addr, to_free_sz);
605         return ret;
606 }
607
608 /* It's probably a kernel bug if we're adding the wrong sized segments, whether
609  * via direct add, a source import, or creation. */
610 static void assert_quantum_alignment(struct arena *arena, void *base,
611                                      size_t size)
612 {
613         if (!ALIGNED(base, arena->quantum))
614                 panic("Unaligned base %p for arena %s, quantum %p, source %s", base,
615                       arena->name, arena->quantum,
616                       arena->source ? arena->source->name : "none");
617         if (!ALIGNED(size, arena->quantum))
618                 panic("Unaligned size %p for arena %s, quantum %p, source %s", size,
619                       arena->name, arena->quantum,
620                       arena->source ? arena->source->name : "none");
621 }
622
623 /* Adds segment [@base, @base + @size) to @arena.  We'll add a span tag if the
624  * arena had a source. */
625 static void *__arena_add(struct arena *arena, void *base, size_t size,
626                          int flags)
627 {
628         struct btag *bt, *span_bt;
629
630         /* These are just sanity checks.  Our client is the kernel, and it could
631          * mess with us in other ways, such as adding overlapping spans. */
632         assert_quantum_alignment(arena, base, size);
633         assert(base < base + size);
634         spin_lock_irqsave(&arena->lock);
635         /* Make sure there are two, bt and span. */
636         if (!__get_enough_btags(arena, 2, flags & MEM_FLAGS)) {
637                 spin_unlock_irqsave(&arena->lock);
638                 return NULL;
639         }
640         bt = __get_btag(arena);
641         if (arena->source) {
642                 span_bt = __get_btag(arena);
643                 span_bt->start = (uintptr_t)base;
644                 span_bt->size = size;
645                 span_bt->status = BTAG_SPAN;
646                 /* Note the btag span is not on any list, but it is in all_segs */
647                 __insert_btag(&arena->all_segs, span_bt);
648         }
649         bt->start = (uintptr_t)base;
650         bt->size = size;
651         arena->amt_total_segs += size;
652         __track_free_seg(arena, bt);
653         __insert_btag(&arena->all_segs, bt);
654         spin_unlock_irqsave(&arena->lock);
655         return base;
656 }
657
658 /* Adds segment [@base, @base + @size) to @arena. */
659 void *arena_add(struct arena *arena, void *base, size_t size, int flags)
660 {
661         /* This wasn't clear from the paper, but mixing source spans and manually
662          * added spans seems like a pain when coalescing BTs and freeing. */
663         if (arena->source)
664                 panic("Arenas with sources must not manually add resources.");
665         return __arena_add(arena, base, size, flags);
666 }
667
668 /* Attempt to get more resources, either from a source or by blocking.  Returns
669  * TRUE if we got something.  FALSE on failure (e.g. MEM_ATOMIC). */
670 static bool get_more_resources(struct arena *arena, size_t size, int flags)
671 {
672         void *span;
673         size_t import_size;
674
675         /* MAX check, in case size << scale overflows */
676         import_size = MAX(size, size << arena->import_scale);
677         if (arena->source) {
678                 span = arena->afunc(arena->source, import_size, flags);
679                 if (!span)
680                         return FALSE;
681                 if (!__arena_add(arena, span, import_size, flags)) {
682                         /* We could fail if MEM_ATOMIC and we couldn't get a BT */
683                         warn("Excessively rare failure, tell brho");
684                         arena->ffunc(arena->source, span, import_size);
685                         return FALSE;
686                 }
687         } else {
688                 /* TODO: allow blocking */
689                 if (!(flags & MEM_ATOMIC))
690                         panic("OOM!");
691                 return FALSE;
692         }
693         return TRUE;
694 }
695
696 /* Helper.  For a given size, return the applicable qcache. */
697 static struct kmem_cache *size_to_qcache(struct arena *arena, size_t size)
698 {
699         /* If we ever get grumpy about the costs of dividing (both here and in the
700          * ROUND ops, we could either insist that quantum is a power of two, or
701          * track whether or not it is and use other shifting ops. */
702         return &arena->qcaches[(size / arena->quantum) - 1];
703 }
704
705 void *arena_alloc(struct arena *arena, size_t size, int flags)
706 {
707         void *ret;
708
709         size = ROUNDUP(size, arena->quantum);
710         if (!size)
711                 panic("Arena %s, request for zero", arena->name);
712         if (size <= arena->qcache_max) {
713                 /* NEXTFIT is an error, since free won't know to skip the qcache and
714                  * then we'd be handing an item to the qcache that it didn't alloc. */
715                 if (flags & ARENA_NEXTFIT)
716                         panic("Arena %s, NEXTFIT, but has qcaches.  Use xalloc.",
717                               arena->name);
718                 return kmem_cache_alloc(size_to_qcache(arena, size), flags);
719         }
720         while (1) {
721                 ret = alloc_from_arena(arena, size, flags);
722                 if (ret)
723                         return ret;
724                 /* This is a little nasty.  We asked our source for enough, but it may
725                  * be a bestfit sized chunk, not an instant fit.  Since we already
726                  * failed once, we can just downgrade to BESTFIT, which will likely find
727                  * our recently-allocated span.  Even worse, the source might only give
728                  * us segments that are BESTFIT, and if we only look at the INSTANTFIT,
729                  * we'll keep looping.  The invariant here is that if we
730                  * get_more_resources, then our allocation can succeed if no one else
731                  * grabs that memory first.
732                  *
733                  * We actually have two options here.  Either we downgrade to BESTFIT or
734                  * we round up our request to our source to the nearest power of two.
735                  * Doing so brings some of the fragmentation into our arena, but an
736                  * instant fit is likely to succeed.  Considering how the first item on
737                  * the BESTFIT list is likely ours, downgrading makes sense. */
738                 flags &= ~ARENA_ALLOC_STYLES;
739                 flags |= ARENA_BESTFIT;
740                 if (!get_more_resources(arena, size, flags))
741                         return NULL;
742         }
743 }
744
745 /* Helper: given a BT's start and size, return a starting address within the BT
746  * that satisfies the constraints.  Returns 0 on failure.
747  *
748  * The rough idea is to go from the start, round up to align, add the phase, and
749  * see if it's still within the BT.  The 'nocross' boundary (also an alignment)
750  * complicates things a little. */
751 static uintptr_t __find_sufficient(uintptr_t bt_start, size_t bt_size,
752                                    size_t size, size_t align,
753                                    size_t phase, size_t nocross)
754 {
755         uintptr_t try;
756         size_t try_size;
757
758         try = bt_start;
759         try = ROUNDUP(try, align);
760         try += phase;
761         /* Wraparound due to phase. */
762         if (try < bt_start)
763                 return 0;
764         /* Check wraparound */
765         if (try + size < try)
766                 return 0;
767         /* Too big for BT, no chance. */
768         if (try + size > bt_start + bt_size)
769                 return 0;
770         if (nocross == 0)
771                 return try;
772         /* Got to deal with nocross boundaries.  If we round up from our potential
773          * start and that is beyond our potential finish, we're OK. */
774         if (ROUNDUP(try, nocross) >= try + size)
775                 return try;
776         /* The segment still might have a chance.  Perhaps we started right before a
777          * nocross.  Let's try again, being careful of overflow.  The ROUNDUP
778          * shouldn't trigger a wraparound. */
779         try = ROUNDUP(bt_start, nocross);
780         try_size = bt_size - (try - bt_start);
781         /* Underflow of bt_size - large_number. */
782         if (try_size > bt_size)
783                 return 0;
784         /* The caller has some control over our next invocation's bt_start and
785          * bt_size.  Let's enforce sanity. */
786         if (try + try_size < try)
787                 return 0;
788         return __find_sufficient(try, try_size, size, align, phase, 0);
789 }
790
791 /* Helper: splits bt, which is not on any freelist, at @at, and puts the front
792  * part back on a free list. */
793 static void __split_bt_at(struct arena *arena, struct btag *bt, uintptr_t at)
794 {
795         struct btag *front = __get_btag(arena);
796
797         /* We're changing bt's start, which is its key for its position in the
798          * all_segs tree.  However, we don't need to remove and reinsert it, since
799          * although we increased its start, we know that no BT should be between its
800          * old start and its new start.  That's actually where the front BT will get
801          * inserted (so long as we insert after changing bt's start). */
802         front->status = BTAG_FREE;
803         front->start = bt->start;
804         front->size = at - bt->start;
805         bt->start += front->size;
806         bt->size -= front->size;
807         __track_free_seg(arena, front);
808         __insert_btag(&arena->all_segs, front);
809         /* At this point, bt's old space in all_segs is broken into:
810          * front: [old_start, try), bt: [try, old_end).  front is on the free list.
811          * bt is not. */
812 }
813
814 /* Helper.  We want the first bt >= mindaddr, with prev < minaddr. */
815 static bool __found_least_upper_btag(struct btag *bt, uintptr_t minaddr)
816 {
817         struct rb_node *prev;
818
819         if (bt->start < minaddr)
820                 return FALSE;
821         prev = rb_prev(&bt->all_link);
822         if (!prev)
823                 return TRUE;
824         if (container_of(prev, struct btag, all_link)->start < minaddr)
825                 return TRUE;
826         return FALSE;
827 }
828
829 /* Does the a search in min/max for a segment. */
830 static void *__xalloc_min_max(struct arena *arena, size_t size,
831                               size_t align, size_t phase, size_t nocross,
832                               uintptr_t minaddr, uintptr_t maxaddr)
833 {
834         struct rb_node *node = arena->all_segs.rb_node;
835         struct btag *bt;
836         uintptr_t try;
837
838         /* Find the first bt >= minaddr */
839         while (node) {
840                 bt = container_of(node, struct btag, all_link);
841                 if (__found_least_upper_btag(bt, minaddr))
842                         break;
843                 if (minaddr < bt->start)
844                         node = node->rb_left;
845                 else
846                         node = node->rb_right;
847         }
848         /* Now we're probably at the first start point (or there's no node).  Just
849          * scan from here. */
850         for (/* node set */; node; node = rb_next(node)) {
851                 bt = container_of(node, struct btag, all_link);
852                 try = __find_sufficient(bt->start, bt->size, size, align, phase,
853                                         nocross);
854                 if (!try)
855                         continue;
856                 if (maxaddr && (try + size > maxaddr))
857                         return NULL;
858                 __untrack_free_seg(arena, bt);
859                 if (try != bt->start)
860                         __split_bt_at(arena, bt, try);
861                 __account_alloc(arena, bt, size, NULL);
862                 return (void*)bt->start;
863         }
864         return NULL;
865 }
866
867 /* For xalloc, there isn't any real instant fit, due to the nocross issues.  We
868  * can still try to get a quicker fit by starting on a higher order list. */
869 static void *__xalloc_from_freelists(struct arena *arena, size_t size,
870                                      size_t align, size_t phase, size_t nocross,
871                                      bool try_instant_fit)
872 {
873         int list_idx;
874         struct btag *bt_i;
875         uintptr_t try = 0;
876
877         if (ROUNDUP(size, align) + phase < size)
878                 return NULL;
879         list_idx = LOG2_DOWN(ROUNDUP(size, align) + phase);
880         list_idx += try_instant_fit ? 1 : 0;
881         for (int i = list_idx; i < ARENA_NR_FREE_LISTS; i++) {
882                 BSD_LIST_FOREACH(bt_i, &arena->free_segs[i], misc_link) {
883                         try = __find_sufficient(bt_i->start, bt_i->size, size, align,
884                                                 phase, nocross);
885                         if (try) {
886                                 BSD_LIST_REMOVE(bt_i, misc_link);
887                                 break;
888                         }
889                 }
890                 if (try)
891                         break;
892         }
893         if (!try)
894                 return NULL;
895         if (try != bt_i->start)
896                 __split_bt_at(arena, bt_i, try);
897         __account_alloc(arena, bt_i, size, NULL);
898         return (void*)bt_i->start;
899 }
900
901 static void *__xalloc_nextfit(struct arena *arena, size_t size, size_t align,
902                               size_t phase, size_t nocross)
903 {
904         void *ret;
905
906         /* NEXTFIT is a lot like a minaddr.  We can start from the old addr + 1,
907          * since the implementation of that helper starts a search from minaddr.  If
908          * it fails, we can try again from 1 (quantum, really), skipping 0. */
909         ret = __xalloc_min_max(arena, size, align, phase, nocross,
910                                arena->last_nextfit_alloc + arena->quantum, 0);
911         if (!ret) {
912                 ret = __xalloc_min_max(arena, size, align, phase, nocross,
913                                        arena->quantum, 0);
914         }
915         if (!ret)
916                 return NULL;
917         arena->last_nextfit_alloc = (uintptr_t)ret;
918         return ret;
919 }
920
921 static void *xalloc_from_arena(struct arena *arena, size_t size,
922                                size_t align, size_t phase, size_t nocross,
923                                void *minaddr, void *maxaddr, int flags)
924 {
925         void *ret;
926         void *to_free_addr = 0;
927         size_t to_free_sz = 0;
928
929         spin_lock_irqsave(&arena->lock);
930         /* Need two, since we might split a BT into 3 BTs. */
931         if (!__get_enough_btags(arena, 2, flags & MEM_FLAGS)) {
932                 spin_unlock_irqsave(&arena->lock);
933                 return NULL;
934         }
935         if (minaddr || maxaddr) {
936                 ret = __xalloc_min_max(arena, size, align, phase, nocross,
937                                        (uintptr_t)minaddr, (uintptr_t)maxaddr);
938         } else {
939                 if (flags & ARENA_BESTFIT) {
940                         ret = __xalloc_from_freelists(arena, size, align, phase, nocross,
941                                                       FALSE);
942                 } else if (flags & ARENA_NEXTFIT) {
943                         ret = __xalloc_nextfit(arena, size, align, phase, nocross);
944                 } else {
945                         ret = __xalloc_from_freelists(arena, size, align, phase, nocross,
946                                                       TRUE);
947                 }
948         }
949         /* Careful, this will unlock and relock.  It's OK right before an unlock. */
950         __try_hash_resize(arena, flags, &to_free_addr, &to_free_sz);
951         spin_unlock_irqsave(&arena->lock);
952         if (to_free_addr)
953                 base_free(arena, to_free_addr, to_free_sz);
954         return ret;
955 }
956
957 void *arena_xalloc(struct arena *arena, size_t size, size_t align, size_t phase,
958                    size_t nocross, void *minaddr, void *maxaddr, int flags)
959 {
960         void *ret;
961         size_t req_size;
962
963         size = ROUNDUP(size, arena->quantum);
964         if (!size)
965                 panic("Arena %s, request for zero", arena->name);
966         if (!IS_PWR2(align))
967                 panic("Arena %s, non-power of two align %p", arena->name, align);
968         if (nocross && !IS_PWR2(nocross))
969                 panic("Arena %s, non-power of nocross %p", arena->name, nocross);
970         if (!ALIGNED(align, arena->quantum))
971                 panic("Arena %s, non-aligned align %p", arena->name, align);
972         if (!ALIGNED(nocross, arena->quantum))
973                 panic("Arena %s, non-aligned nocross %p", arena->name, nocross);
974         if (!ALIGNED(phase, arena->quantum))
975                 panic("Arena %s, non-aligned phase %p", arena->name, phase);
976         if (size + align < size)
977                 panic("Arena %s, size %p + align %p overflow%p", arena->name, size,
978                       align);
979         if (size + phase < size)
980                 panic("Arena %s, size %p + phase %p overflow%p", arena->name, size,
981                       phase);
982         if (align + phase < align)
983                 panic("Arena %s, align %p + phase %p overflow%p", arena->name, align,
984                       phase);
985         /* Ok, it's a pain to import resources from a source such that we'll be able
986          * to guarantee we make progress without stranding resources if we have
987          * nocross or min/maxaddr.  For min/maxaddr, when we ask the source, we
988          * aren't easily able to xalloc from their (it may depend on the afunc).
989          * For nocross, we can't easily ask the source for the right span that
990          * satisfies the request (again, no real xalloc).  Some constraints might
991          * not even be possible.
992          *
993          * If we get a span from the source and never use it, then we run a risk of
994          * fragmenting and stranding a bunch of spans in our current arena.  Imagine
995          * the loop where we keep asking for spans (e.g. 8 pgs) and getting
996          * something that doesn't work.  Those 8 pgs are fragmented, and we won't
997          * give them back to the source until we allocate and then free them
998          * (barring some sort of reclaim callback).
999          *
1000          * Besides, I don't know if we even need/want nocross/min/maxaddr. */
1001         if (arena->source && (nocross || minaddr || maxaddr))
1002                 panic("Arena %s, has source, can't xalloc with nocross %p, minaddr %p, or maxaddr %p",
1003                       arena->name, nocross, minaddr, maxaddr);
1004         while (1) {
1005                 ret = xalloc_from_arena(arena, size, align, phase, nocross, minaddr,
1006                                         maxaddr, flags);
1007                 if (ret)
1008                         return ret;
1009                 /* We checked earlier than no two of these overflow, so I think we don't
1010                  * need to worry about multiple overflows. */
1011                 req_size = size + align + phase;
1012                 /* Note that this check isn't the same as the one we make when finding a
1013                  * sufficient segment.  Here we check overflow on the requested size.
1014                  * Later, we check aligned bt_start + phase.  The concern is that this
1015                  * check succeeds, but the other fails.  (Say size = PGSIZE, phase =
1016                  * -PGSIZE -1.  req_size is very large.
1017                  *
1018                  * In this case, we're still fine - if our source is able to satisfy the
1019                  * request, our bt_start and bt_size will be able to express that size
1020                  * without wrapping. */
1021                 if (req_size < size)
1022                         panic("Arena %s, size %p + align %p + phase %p overflow",
1023                               arena->name, size, align, phase);
1024                 if (!get_more_resources(arena, req_size, flags))
1025                         return NULL;
1026                 /* Our source may have given us a segment that is on the BESTFIT list,
1027                  * same as with arena_alloc. */
1028                 flags &= ~ARENA_ALLOC_STYLES;
1029                 flags |= ARENA_BESTFIT;
1030                 /* TODO: could put a check in here to make sure we don't loop forever,
1031                  * in case we trip some other bug. */
1032         }
1033 }
1034
1035 /* Helper: if possible, merges the right BT to the left.  Returns TRUE if we
1036  * merged. */
1037 static bool __merge_right_to_left(struct arena *arena, struct btag *left,
1038                                   struct btag *right)
1039 {
1040         /* These checks will also make sure we never merge SPAN boundary tags. */
1041         if (left->status != BTAG_FREE)
1042                 return FALSE;
1043         if (right->status != BTAG_FREE)
1044                 return FALSE;
1045         if (left->start + left->size == right->start) {
1046                 /* Need to yank left off its list before changing its size. */
1047                 __untrack_free_seg(arena, left);
1048                 __untrack_free_seg(arena, right);
1049                 left->size += right->size;
1050                 __track_free_seg(arena, left);
1051                 rb_erase(&right->all_link, &arena->all_segs);
1052                 __free_btag(arena, right);
1053                 return TRUE;
1054         }
1055         return FALSE;
1056 }
1057
1058 /* Merges @bt's segments with its adjacent neighbors.  If we end up having an
1059  * entire span free, we'll stop tracking it in this arena and return it for our
1060  * caller to free. */
1061 static void __coalesce_free_seg(struct arena *arena, struct btag *bt,
1062                                 void **to_free_addr, size_t *to_free_sz)
1063 {
1064         struct rb_node *rb_p, *rb_n;
1065         struct btag *bt_p, *bt_n;
1066
1067         rb_n = rb_next(&bt->all_link);
1068         if (rb_n) {
1069                 bt_n = container_of(rb_n, struct btag, all_link);
1070                 __merge_right_to_left(arena, bt, bt_n);
1071         }
1072         rb_p = rb_prev(&bt->all_link);
1073         if (rb_p) {
1074                 bt_p = container_of(rb_p, struct btag, all_link);
1075                 if (__merge_right_to_left(arena, bt_p, bt))
1076                         bt = bt_p;
1077         }
1078         /* Check for a span */
1079         rb_p = rb_prev(&bt->all_link);
1080         if (rb_p) {
1081                 bt_p = container_of(rb_p, struct btag, all_link);
1082                 if ((bt_p->status == BTAG_SPAN) &&
1083                     (bt_p->start == bt->start) &&
1084                     (bt_p->size == bt->size)) {
1085
1086                         *to_free_addr = (void*)bt_p->start;
1087                         *to_free_sz = bt_p->size;
1088                         /* Note the span was not on a free list */
1089                         __untrack_free_seg(arena, bt);
1090                         rb_erase(&bt_p->all_link, &arena->all_segs);
1091                         __free_btag(arena, bt_p);
1092                         rb_erase(&bt->all_link, &arena->all_segs);
1093                         __free_btag(arena, bt);
1094                 }
1095         }
1096 }
1097
1098 static void free_from_arena(struct arena *arena, void *addr, size_t size)
1099 {
1100         struct btag *bt;
1101         void *to_free_addr = 0;
1102         size_t to_free_sz = 0;
1103
1104         spin_lock_irqsave(&arena->lock);
1105         bt = __untrack_alloc_seg(arena, (uintptr_t)addr);
1106         if (!bt)
1107                 panic("Free of unallocated addr %p from arena %s", addr, arena->name);
1108         if (bt->size != size)
1109                 panic("Free of %p with wrong size %p (%p) from arena %s", addr, size,
1110                       bt->size, arena->name);
1111         arena->amt_alloc_segs -= size;
1112         __track_free_seg(arena, bt);
1113         __coalesce_free_seg(arena, bt, &to_free_addr, &to_free_sz);
1114         arena->amt_total_segs -= to_free_sz;
1115         spin_unlock_irqsave(&arena->lock);
1116         if (to_free_addr)
1117                 arena->ffunc(arena->source, to_free_addr, to_free_sz);
1118 }
1119
1120 void arena_free(struct arena *arena, void *addr, size_t size)
1121 {
1122         size = ROUNDUP(size, arena->quantum);
1123         if (size <= arena->qcache_max)
1124                 return kmem_cache_free(size_to_qcache(arena, size), addr);
1125         free_from_arena(arena, addr, size);
1126 }
1127
1128 void arena_xfree(struct arena *arena, void *addr, size_t size)
1129 {
1130         size = ROUNDUP(size, arena->quantum);
1131         free_from_arena(arena, addr, size);
1132 }
1133
1134 /* Low-level arena builder.  Pass in a page address, and this will build an
1135  * arena in that memory.
1136  *
1137  * This will be used for each NUMA domain's base arena, kpages_arena, and
1138  * kmalloc_arena, since the normal arena_create() won't work yet (no kmalloc).
1139  */
1140 struct arena *arena_builder(void *pgaddr, char *name, size_t quantum,
1141                             void *(*afunc)(struct arena *, size_t, int),
1142                             void (*ffunc)(struct arena *, void *, size_t),
1143                             struct arena *source, size_t qcache_max)
1144 {
1145         struct arena *a = (struct arena*)pgaddr;
1146         struct btag *two_tags = (struct btag*)(pgaddr + sizeof(struct arena));
1147
1148         static_assert(sizeof(struct arena) + 2 * sizeof(struct btag) <= PGSIZE);
1149
1150         arena_init(a, name, quantum, afunc, ffunc, source, qcache_max);
1151         if (!source)
1152                 a->is_base = TRUE;
1153         BSD_LIST_INSERT_HEAD(&a->unused_btags, &two_tags[0], misc_link);
1154         BSD_LIST_INSERT_HEAD(&a->unused_btags, &two_tags[1], misc_link);
1155         return a;
1156 }
1157
1158 /* Sanity checker for an arena's structures.  Hold the lock. */
1159 static void __arena_asserter(struct arena *arena)
1160 {
1161         struct btag *bt_i;
1162         struct rb_node *rb_i;
1163         size_t amt_free = 0, amt_alloc = 0, nr_allocs = 0;
1164
1165         for (int i = 0; i < ARENA_NR_FREE_LISTS; i++) {
1166                 BSD_LIST_FOREACH(bt_i, &arena->free_segs[i], misc_link) {
1167                         assert(bt_i->status == BTAG_FREE);
1168                         assert(bt_i->size >= (1ULL << i));
1169                         assert(bt_i->size < (1ULL << (i + 1)));
1170                 }
1171         }
1172         for (int i = 0; i < arena->hh.nr_hash_lists; i++) {
1173                 BSD_LIST_FOREACH(bt_i, &arena->alloc_hash[i], misc_link)
1174                         assert(bt_i->status == BTAG_ALLOC);
1175         }
1176         for (rb_i = rb_first(&arena->all_segs); rb_i; rb_i = rb_next(rb_i)) {
1177                 bt_i = container_of(rb_i, struct btag, all_link);
1178                 if (bt_i->status == BTAG_FREE)
1179                         amt_free += bt_i->size;
1180                 if (bt_i->status == BTAG_ALLOC) {
1181                         amt_alloc += bt_i->size;
1182                         nr_allocs++;
1183                 }
1184         }
1185         assert(arena->amt_total_segs == amt_free + amt_alloc);
1186         assert(arena->amt_alloc_segs == amt_alloc);
1187         assert(arena->hh.nr_items == nr_allocs);
1188 }
1189
1190 size_t arena_amt_free(struct arena *arena)
1191 {
1192         return arena->amt_total_segs - arena->amt_alloc_segs;
1193 }
1194
1195 size_t arena_amt_total(struct arena *arena)
1196 {
1197         return arena->amt_total_segs;
1198 }
1199
1200 void add_importing_arena(struct arena *source, struct arena *importer)
1201 {
1202         qlock(&arenas_and_slabs_lock);
1203         TAILQ_INSERT_TAIL(&source->__importing_arenas, importer, import_link);
1204         qunlock(&arenas_and_slabs_lock);
1205 }
1206
1207 void del_importing_arena(struct arena *source, struct arena *importer)
1208 {
1209         qlock(&arenas_and_slabs_lock);
1210         TAILQ_REMOVE(&source->__importing_arenas, importer, import_link);
1211         qunlock(&arenas_and_slabs_lock);
1212 }
1213
1214 void add_importing_slab(struct arena *source, struct kmem_cache *importer)
1215 {
1216         qlock(&arenas_and_slabs_lock);
1217         TAILQ_INSERT_TAIL(&source->__importing_slabs, importer, import_link);
1218         qunlock(&arenas_and_slabs_lock);
1219 }
1220
1221 void del_importing_slab(struct arena *source, struct kmem_cache *importer)
1222 {
1223         qlock(&arenas_and_slabs_lock);
1224         TAILQ_REMOVE(&source->__importing_slabs, importer, import_link);
1225         qunlock(&arenas_and_slabs_lock);
1226 }
1227
1228 void *base_alloc(struct arena *guess, size_t size, int flags)
1229 {
1230         return arena_alloc(find_my_base(guess), size, flags);
1231 }
1232
1233 void *base_zalloc(struct arena *guess, size_t size, int flags)
1234 {
1235         void *ret = base_alloc(guess, size, flags);
1236
1237         if (!ret)
1238                 return NULL;
1239         memset(ret, 0, size);
1240         return ret;
1241 }
1242
1243 void base_free(struct arena *guess, void *addr, size_t size)
1244 {
1245         return arena_free(find_my_base(guess), addr, size);
1246 }
1247
1248 void print_arena_stats(struct arena *arena, bool verbose)
1249 {
1250         struct btag *bt_i;
1251         struct rb_node *rb_i;
1252         struct arena *a_i;
1253         struct kmem_cache *s_i;
1254
1255         size_t nr_allocs = 0;
1256         size_t nr_imports = 0;
1257         size_t amt_alloc = 0;
1258         size_t amt_free = 0;
1259         size_t amt_imported = 0;
1260         size_t empty_hash_chain = 0;
1261         size_t longest_hash_chain = 0;
1262
1263         printk("Arena: %s (%p)\n--------------\n", arena->name, arena);
1264         printk("\tquantum: %d, qcache_max: %d\n", arena->quantum,
1265                arena->qcache_max);
1266         printk("\tsource: %s\n", arena->source ? arena->source->name : "none");
1267
1268         spin_lock_irqsave(&arena->lock);
1269         for (int i = 0; i < ARENA_NR_FREE_LISTS; i++) {
1270                 int j = 0;
1271
1272                 if (!BSD_LIST_EMPTY(&arena->free_segs[i])) {
1273                         printk("\tList of [2^%d - 2^%d):\n", i, i + 1);
1274                         BSD_LIST_FOREACH(bt_i, &arena->free_segs[i], misc_link) {
1275                                 if (verbose)
1276                                         printk("\t\t%d: start %p, size %p\n", j, bt_i->start,
1277                                                bt_i->size);
1278                                 j++;
1279                         }
1280                         printk("\t\tNr free segs: %d\n", j);
1281                 }
1282         }
1283         for (int i = 0; i < arena->hh.nr_hash_lists; i++) {
1284                 int j = 0;
1285
1286                 if (BSD_LIST_EMPTY(&arena->alloc_hash[i]))
1287                         empty_hash_chain++;
1288                 BSD_LIST_FOREACH(bt_i, &arena->alloc_hash[i], misc_link)
1289                         j++;
1290                 longest_hash_chain = MAX(longest_hash_chain, j);
1291         }
1292         printk("\tSegments:\n\t--------------\n");
1293         for (rb_i = rb_first(&arena->all_segs); rb_i; rb_i = rb_next(rb_i)) {
1294                 bt_i = container_of(rb_i, struct btag, all_link);
1295                 if (bt_i->status == BTAG_SPAN) {
1296                         if (verbose)
1297                                 printk("\tSpan: start %p + %p\n", bt_i->start, bt_i->size);
1298                         nr_imports++;
1299                         amt_imported += bt_i->size;
1300                 }
1301                 if (bt_i->status == BTAG_FREE) {
1302                         if (verbose)
1303                                 printk("\t\tFree: start %p + %p\n", bt_i->start, bt_i->size);
1304                         amt_free += bt_i->size;
1305                 }
1306                 if (bt_i->status == BTAG_ALLOC) {
1307                         if (verbose)
1308                                 printk("\t\tAloc: start %p + %p\n", bt_i->start, bt_i->size);
1309                         nr_allocs++;
1310                         amt_alloc += bt_i->size;
1311                 }
1312         }
1313         printk("\tStats:\n\t-----------------\n");
1314         printk("\t\tAmt free: %llu (%p)\n", amt_free, amt_free);
1315         printk("\t\tAmt alloc: %llu (%p), nr allocs %d\n", amt_alloc, amt_alloc,
1316                nr_allocs);
1317         printk("\t\tAmt total segs: %llu, amt alloc segs %llu\n",
1318                arena->amt_total_segs, arena->amt_alloc_segs);
1319         printk("\t\tAmt imported: %llu (%p), nr imports %d\n", amt_imported,
1320                amt_imported, nr_imports);
1321         printk("\t\tNr hash %d, empty hash: %d, longest hash %d\n",
1322                arena->hh.nr_hash_lists, empty_hash_chain, longest_hash_chain);
1323         __arena_asserter(arena);
1324         spin_unlock_irqsave(&arena->lock);
1325
1326         qlock(&arenas_and_slabs_lock);
1327         printk("\tImporting Arenas:\n\t-----------------\n");
1328         TAILQ_FOREACH(a_i, &arena->__importing_arenas, import_link)
1329                 printk("\t\t%s\n", a_i->name);
1330         printk("\tImporting Slabs:\n\t-----------------\n");
1331         TAILQ_FOREACH(s_i, &arena->__importing_slabs, import_link)
1332                 printk("\t\t%s\n", s_i->name);
1333         qunlock(&arenas_and_slabs_lock);
1334 }