kconfig: use pkg-config for ncurses detection
[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 #include <kthread.h>
15
16 /* Boundary tags track segments.  All segments, regardless of allocation status,
17  * are on the all_segs list.  BTs are on other lists, depending on their status.
18  * There is a list of unused BTs (those not in use by the arena), lists of free
19  * segments (the power-of-two lists in the array), and lists of allocated BTs in
20  * the hash table.
21  *
22  * BTs also track 'spans', which are contig segments that were allocated from a
23  * source arena.  SPANS are never merged with adjacent BTs, and they come before
24  * the ALLOC BTs that track the segments inside the span.  An entire span is
25  * returned to its source when all of its entries are freed (policy, up for
26  * debate/modification).  Spans are not on a free, unused, or hash list. */
27 typedef enum {
28         BTAG_FREE,
29         BTAG_ALLOC,
30         BTAG_SPAN,
31 } btag_status_t;
32
33 struct btag {
34         struct rb_node                  all_link; /* all non-free BTs */
35         BSD_LIST_ENTRY(btag)            misc_link; /* freelist unused or hash */
36         uintptr_t                       start;
37         size_t                          size;
38         btag_status_t                   status;
39 };
40 BSD_LIST_HEAD(btag_list, btag);
41
42 /* 64 is the most powers of two we can express with 64 bits. */
43 #define ARENA_NR_FREE_LISTS     64
44 #define ARENA_NAME_SZ           32
45
46 /* Forward declarations of import lists */
47 struct arena;
48 TAILQ_HEAD(arena_tailq, arena);
49 struct kmem_cache;
50 TAILQ_HEAD(kmem_cache_tailq, kmem_cache);
51
52 /* The arena maintains an in-order list of all segments, allocated or otherwise.
53  * All free segments are on one of the free_segs[] lists.  There is one list for
54  * each power-of-two we can allocate. */
55 struct arena {
56         spinlock_t                      lock;
57         uint8_t                         import_scale;
58         bool                            is_base;
59         size_t                          quantum;
60         size_t                          qcache_max;
61         struct kmem_cache               *qcaches;
62         struct rb_root                  all_segs;    /* BTs, using all_link */
63         struct btag_list                unused_btags;/* BTs, using misc_link */
64         struct btag_list                *alloc_hash; /* BTs, using misc_link */
65         struct hash_helper              hh;
66         void *(*afunc)(struct arena *, size_t, int);
67         void (*ffunc)(struct arena *, void *, size_t);
68         struct arena                    *source;
69         size_t                          amt_total_segs; /* not include qcache */
70         size_t                          amt_alloc_segs;
71         size_t                          nr_allocs_ever;
72         uintptr_t                       last_nextfit_alloc;
73         struct btag_list                free_segs[ARENA_NR_FREE_LISTS];
74         struct btag_list                static_hash[HASH_INIT_SZ];
75
76         /* Accounting */
77         char                            name[ARENA_NAME_SZ];
78         TAILQ_ENTRY(arena)              next;
79         /* These lists are protected by the global arena_and_slab qlock */
80         TAILQ_ENTRY(arena)              import_link;
81         struct arena_tailq              __importing_arenas;
82         struct kmem_cache_tailq         __importing_slabs;
83 };
84
85 extern struct arena_tailq all_arenas;
86
87 /* Arena allocation styles, or'd with MEM_FLAGS */
88 #define ARENA_BESTFIT           0x100
89 #define ARENA_INSTANTFIT        0x200
90 #define ARENA_NEXTFIT           0x400
91 #define ARENA_ALLOC_STYLES (ARENA_BESTFIT | ARENA_INSTANTFIT | ARENA_NEXTFIT)
92
93 /* Magic source, for arenas that dynamically generate their contents. */
94 #define ARENA_SELF_SOURCE (void*)(-2)
95 /* Creates an area, with initial segment [@base, @base + @size).  Allocs are in
96  * units of @quantum.  If @source is provided, the arena will alloc new segments
97  * from @source, calling @afunc to alloc and @ffunc to free.  Uses a slab
98  * allocator for allocations up to @qcache_max (0 = no caching). */
99 struct arena *arena_create(const char *name, void *base, size_t size,
100                            size_t quantum,
101                            void *(*afunc)(struct arena *, size_t, int),
102                            void (*ffunc)(struct arena *, void *, size_t),
103                            struct arena *source, size_t qcache_max, int flags);
104 /* Adds segment [@base, @base + @size) to @arena. */
105 void *arena_add(struct arena *arena, void *base, size_t size, int flags);
106 void arena_destroy(struct arena *arena);
107 /* Lower-level create/destroy interface; caller manages the memory */
108 void __arena_create(struct arena *arena, const char *name, size_t quantum,
109                     void *(*afunc)(struct arena *, size_t, int),
110                     void (*ffunc)(struct arena *, void *, size_t),
111                     struct arena *source, size_t qcache_max);
112 void __arena_destroy(struct arena *arena);
113
114 void *arena_alloc(struct arena *arena, size_t size, int flags);
115 void arena_free(struct arena *arena, void *addr, size_t size);
116 void *arena_xalloc(struct arena *arena, size_t size, size_t align, size_t phase,
117                    size_t nocross, void *minaddr, void *maxaddr, int flags);
118 void arena_xfree(struct arena *arena, void *addr, size_t size);
119
120 size_t arena_amt_free(struct arena *arena);
121 size_t arena_amt_total(struct arena *arena);
122 void kmemstat(void);
123
124 /* All lists that track the existence of arenas, slabs, and the connections
125  * between them are tracked by a global qlock.  For the most part, slabs/arenas
126  * are created rarely, and the main lockers will be a reclaim ktask and #mem
127  * accessors. */
128 extern qlock_t arenas_and_slabs_lock;
129 void add_importing_arena(struct arena *source, struct arena *importer);
130 void del_importing_arena(struct arena *source, struct arena *importer);
131 void add_importing_slab(struct arena *source, struct kmem_cache *importer);
132 void del_importing_slab(struct arena *source, struct kmem_cache *importer);
133
134 /* Low-level memory allocator intefaces */
135 extern struct arena *base_arena;
136 extern struct arena *kpages_arena;
137 struct arena *arena_builder(void *pgaddr, const char *name, size_t quantum,
138                             void *(*afunc)(struct arena *, size_t, int),
139                             void (*ffunc)(struct arena *, void *, size_t),
140                             struct arena *source, size_t qcache_max);
141 /* Allocate directly from the nearest base allocator.  Used by other mm code.
142  * Pass in your closest arena (such as your source) to help us find a base. */
143 void *base_alloc(struct arena *guess, size_t size, int flags);
144 void *base_zalloc(struct arena *guess, size_t size, int flags);
145 void base_free(struct arena *guess, void *addr, size_t size);