Add the 'current_kthread' helper
[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;       /* connects 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; /* Does 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 /* Creates an area, with initial segment [@base, @base + @size).  Allocs are in
94  * units of @quantum.  If @source is provided, the arena will alloc new segments
95  * from @source, calling @afunc to alloc and @ffunc to free.  Uses a slab
96  * allocator for allocations up to @qcache_max (0 = no caching). */
97 struct arena *arena_create(char *name, void *base, size_t size, size_t quantum,
98                            void *(*afunc)(struct arena *, size_t, int),
99                            void (*ffunc)(struct arena *, void *, size_t),
100                            struct arena *source, size_t qcache_max, int flags);
101 /* Adds segment [@base, @base + @size) to @arena. */
102 void *arena_add(struct arena *arena, void *base, size_t size, int flags);
103 void arena_destroy(struct arena *arena);
104
105 void *arena_alloc(struct arena *arena, size_t size, int flags);
106 void arena_free(struct arena *arena, void *addr, size_t size);
107 void *arena_xalloc(struct arena *arena, size_t size, size_t align, size_t phase,
108                    size_t nocross, void *minaddr, void *maxaddr, int flags);
109 void arena_xfree(struct arena *arena, void *addr, size_t size);
110
111 size_t arena_amt_free(struct arena *arena);
112 size_t arena_amt_total(struct arena *arena);
113
114 /* All lists that track the existence of arenas, slabs, and the connections
115  * between them are tracked by a global qlock.  For the most part, slabs/arenas
116  * are created rarely, and the main lockers will be a reclaim ktask and #mem
117  * accessors. */
118 extern qlock_t arenas_and_slabs_lock;
119 void add_importing_arena(struct arena *source, struct arena *importer);
120 void del_importing_arena(struct arena *source, struct arena *importer);
121 void add_importing_slab(struct arena *source, struct kmem_cache *importer);
122 void del_importing_slab(struct arena *source, struct kmem_cache *importer);
123
124 /* Low-level memory allocator intefaces */
125 extern struct arena *base_arena;
126 extern struct arena *kpages_arena;
127 struct arena *arena_builder(void *pgaddr, char *name, size_t quantum,
128                             void *(*afunc)(struct arena *, size_t, int),
129                             void (*ffunc)(struct arena *, void *, size_t),
130                             struct arena *source, size_t qcache_max);
131 /* Allocate directly from the nearest base allocator.  Used by other mm code.
132  * Pass in your closest arena (such as your source) to help us find a base. */
133 void *base_alloc(struct arena *guess, size_t size, int flags);
134 void *base_zalloc(struct arena *guess, size_t size, int flags);
135 void base_free(struct arena *guess, void *addr, size_t size);