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