Add the arena allocator
[akaros.git] / kern / include / arena.h
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 #pragma once
9
10 #include <sys/queue.h>
11 #include <atomic.h>
12 #include <rbtree.h>
13 #include <hash_helper.h>
14
15 /* Boundary tags track segments.  All segments, regardless of allocation status,
16  * are on the all_segs list.  BTs are on other lists, depending on their status.
17  * There is a list of unused BTs (those not in use by the arena), lists of free
18  * segments (the power-of-two lists in the array), and lists of allocated BTs in
19  * the hash table.
20  *
21  * BTs also track 'spans', which are contig segments that were allocated from a
22  * source arena.  SPANS are never merged with adjacent BTs, and they come before
23  * the ALLOC BTs that track the segments inside the span.  An entire span is
24  * returned to its source when all of its entries are freed (policy, up for
25  * debate/modification).  Spans are not on a free, unused, or hash list. */
26 typedef enum {
27         BTAG_FREE,
28         BTAG_ALLOC,
29         BTAG_SPAN,
30 } btag_status_t;
31
32 struct btag {
33         struct rb_node                          all_link;       /* connects all non-free BTs */
34         BSD_LIST_ENTRY(btag)            misc_link;      /* freelist, unused, or hash */
35         uintptr_t                                       start;
36         size_t                                          size;
37         btag_status_t                           status;
38 };
39 BSD_LIST_HEAD(btag_list, btag);
40
41 /* 64 is the most powers of two we can express with 64 bits. */
42 #define ARENA_NR_FREE_LISTS             64
43 #define ARENA_NAME_SZ                   32
44
45 /* The arena maintains an in-order list of all segments, allocated or otherwise.
46  * All free segments are on one of the free_segs[] lists.  There is one list for
47  * each power-of-two we can allocate. */
48 struct arena {
49         spinlock_t                                      lock;
50         uint8_t                                         import_scale;
51         bool                                            is_base;
52         size_t                                          quantum;
53         size_t                                          qcache_max;
54         struct rb_root                          all_segs;               /* BTs, using all_link */
55         struct btag_list                        unused_btags;   /* BTs, using misc_link */
56         struct btag_list                        *alloc_hash;    /* BTs, using misc_link */
57         struct hash_helper                      hh;
58         void *(*afunc)(struct arena *, size_t, int);
59         void (*ffunc)(struct arena *, void *, size_t);
60         struct arena                            *source;
61         size_t                                          amt_total_segs; /* Does not include qcache */
62         size_t                                          amt_alloc_segs;
63         size_t                                          nr_allocs_ever;
64         uintptr_t                                       last_nextfit_alloc;
65         struct btag_list                        free_segs[ARENA_NR_FREE_LISTS];
66         struct btag_list                        static_hash[HASH_INIT_SZ];
67
68         /* Accounting */
69         char                                            name[ARENA_NAME_SZ];
70         TAILQ_ENTRY(arena)                      next;
71 };
72
73 /* Arena allocation styles, or'd with MEM_FLAGS */
74 #define ARENA_BESTFIT                   0x100
75 #define ARENA_INSTANTFIT                0x200
76 #define ARENA_NEXTFIT                   0x400
77 #define ARENA_ALLOC_STYLES (ARENA_BESTFIT | ARENA_INSTANTFIT | ARENA_NEXTFIT)
78
79 /* Creates an area, with initial segment [@base, @base + @size).  Allocs are in
80  * units of @quantum.  If @source is provided, the arena will alloc new segments
81  * from @source, calling @afunc to alloc and @ffunc to free.  Uses a slab
82  * allocator for allocations up to @qcache_max (0 = no caching). */
83 struct arena *arena_create(char *name, void *base, size_t size, size_t quantum,
84                            void *(*afunc)(struct arena *, size_t, int),
85                            void (*ffunc)(struct arena *, void *, size_t),
86                            struct arena *source, size_t qcache_max, int flags);
87 /* Adds segment [@base, @base + @size) to @arena. */
88 void *arena_add(struct arena *arena, void *base, size_t size, int flags);
89 void arena_destroy(struct arena *arena);
90
91 void *arena_alloc(struct arena *arena, size_t size, int flags);
92 void arena_free(struct arena *arena, void *addr, size_t size);
93 void *arena_xalloc(struct arena *arena, size_t size, size_t align, size_t phase,
94                    size_t nocross, void *minaddr, void *maxaddr, int flags);
95 void arena_xfree(struct arena *arena, void *addr, size_t size);
96
97 size_t arena_amt_free(struct arena *arena);
98 size_t arena_amt_total(struct arena *arena);
99
100 /* Low-level memory allocator intefaces */
101 extern struct arena *base_arena;
102 extern struct arena *kpages_arena;
103 struct arena *arena_builder(void *pgaddr, char *name, size_t quantum,
104                             void *(*afunc)(struct arena *, size_t, int),
105                             void (*ffunc)(struct arena *, void *, size_t),
106                             struct arena *source, size_t qcache_max);
107 /* Allocate directly from the nearest base allocator.  Used by other mm code.
108  * Pass in your closest arena (such as your source) to help us find a base. */
109 void *base_alloc(struct arena *guess, size_t size, int flags);
110 void *base_zalloc(struct arena *guess, size_t size, int flags);
111 void base_free(struct arena *guess, void *addr, size_t size);