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