Overhaul lock_test.R
[akaros.git] / kern / include / slab.h
1 /*
2  * Copyright (c) 2009 The Regents of the University of California
3  * Barret Rhoden <brho@cs.berkeley.edu>
4  * Kevin Klues <klueska@cs.berkeley.edu>
5  * See LICENSE for details.
6  *
7  * Slab allocator, based on the SunOS 5.4 allocator paper.
8  *
9  * There is a list of kmem_cache, which are the caches of objects of a given
10  * size.  This list is sorted in order of size.  Each kmem_cache has three
11  * lists of slabs: full, partial, and empty.
12  *
13  * For large objects, the kmem_slabs point to bufctls, which have the address
14  * of their large buffers.  These slabs can consist of more than one contiguous
15  * page.
16  *
17  * For small objects, the slabs do not use the bufctls.  Instead, they point to
18  * the next free object in the slab.  The free objects themselves hold the
19  * address of the next free item.  The slab structure is stored at the end of
20  * the page.  There is only one page per slab.
21  *
22  * Be careful with source arenas and NOTOUCH.  If a cache's source arena is not
23  * page-aligned memory, you need to set NOTOUCH.  Otherwise, for small objects,
24  * a slab will be constructed that uses the source for a page of objects.
25  */
26
27 #pragma once
28
29 #include <ros/common.h>
30 #include <arch/mmu.h>
31 #include <sys/queue.h>
32 #include <atomic.h>
33 #include <hash_helper.h>
34 #include <arena.h>
35 #include <trap.h>
36
37 /* Back in the day, their cutoff for "large objects" was 512B, based on
38  * measurements and on not wanting more than 1/8 of internal fragmentation. */
39 #define NUM_BUF_PER_SLAB 8
40 #define SLAB_LARGE_CUTOFF (PGSIZE / NUM_BUF_PER_SLAB)
41
42 #define KMC_NAME_SZ             32
43 #define KMC_MAG_MIN_SZ          8
44 #define KMC_MAG_MAX_SZ          62      /* chosen for mag size and caching */
45
46 /* Cache creation flags: */
47 #define KMC_NOTOUCH             0x0001  /* Can't use source/object's memory */
48 #define KMC_QCACHE              0x0002  /* Cache is an arena's qcache */
49 #define KMC_NOTRACE             0x0004  /* Do not trace allocations */
50 #define __KMC_USE_BUFCTL        0x1000  /* Internal use */
51 #define __KMC_TRACED            0x2000  /* Internal use */
52 #define __KMC_EVER_TRACED       0x3000  /* Internal use */
53
54 struct kmem_magazine {
55         SLIST_ENTRY(kmem_magazine)      link;
56         unsigned int                    nr_rounds;
57         void                            *rounds[KMC_MAG_MAX_SZ];
58 } __attribute__((aligned(ARCH_CL_SIZE)));
59 SLIST_HEAD(kmem_mag_slist, kmem_magazine);
60
61 struct kmem_pcpu_cache {
62         int8_t                          irq_state;
63         unsigned int                    magsize;
64         struct kmem_magazine            *loaded;
65         struct kmem_magazine            *prev;
66         size_t                          nr_allocs_ever;
67 } __attribute__((aligned(ARCH_CL_SIZE)));
68
69 struct kmem_depot {
70         spinlock_t                      lock;
71         struct kmem_mag_slist           not_empty;
72         struct kmem_mag_slist           empty;
73         unsigned int                    magsize;
74         unsigned int                    nr_empty;
75         unsigned int                    nr_not_empty;
76         unsigned int                    busy_count;
77         uint64_t                        busy_start;
78 };
79
80 struct kmem_slab;
81
82 /* Control block for buffers for large-object slabs */
83 struct kmem_bufctl {
84         SLIST_ENTRY(kmem_bufctl) link;
85         void *buf_addr;
86         struct kmem_slab *my_slab;
87 };
88 SLIST_HEAD(kmem_bufctl_slist, kmem_bufctl);
89
90 /* Slabs contain the objects.  Can be either full, partial, or empty,
91  * determined by checking the number of objects busy vs total.  For large
92  * slabs, the bufctl list is used to find a free buffer.  For small, the void*
93  * is used instead.*/
94 struct kmem_slab {
95         TAILQ_ENTRY(kmem_slab) link;
96         size_t num_busy_obj;
97         size_t num_total_obj;
98         void *source_obj;
99         union {
100                 struct kmem_bufctl_slist bufctl_freelist;
101                 void *free_small_obj;
102         };
103 };
104 TAILQ_HEAD(kmem_slab_list, kmem_slab);
105
106 struct kmem_trace {
107         void                            *obj;
108         struct hlist_node               hash;
109         size_t                          nr_pcs;
110         uintptr_t                       pcs[MAX_BT_DEPTH];
111         char                            str[60];
112 };
113
114 struct kmem_trace_ht {
115         spinlock_t                      lock;
116         struct hash_helper              hh;
117         struct hlist_head               *ht;
118         struct hlist_head               static_ht[HASH_INIT_SZ];
119 };
120
121 /* Actual cache */
122 struct kmem_cache {
123         TAILQ_ENTRY(kmem_cache) all_kmc_link;
124         struct kmem_pcpu_cache *pcpu_caches;
125         struct kmem_depot depot;
126         spinlock_t cache_lock;
127         size_t obj_size;
128         size_t import_amt;
129         int align;
130         int flags;
131         struct arena *source;
132         struct kmem_slab_list full_slab_list;
133         struct kmem_slab_list partial_slab_list;
134         struct kmem_slab_list empty_slab_list;
135         int (*ctor)(void *obj, void *priv, int flags);
136         void (*dtor)(void *obj, void *priv);
137         void *priv;
138         unsigned long nr_cur_alloc;
139         unsigned long nr_direct_allocs_ever;
140         struct hash_helper hh;
141         struct kmem_bufctl_slist *alloc_hash;
142         struct kmem_bufctl_slist static_hash[HASH_INIT_SZ];
143         char name[KMC_NAME_SZ];
144         TAILQ_ENTRY(kmem_cache) import_link;
145         struct kmem_trace_ht trace_ht;
146 };
147
148 extern struct kmem_cache_tailq all_kmem_caches;
149
150 /* Cache management */
151 struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
152                                      int align, int flags,
153                                      struct arena *source,
154                                      int (*ctor)(void *, void *, int),
155                                      void (*dtor)(void *, void *),
156                                      void *priv);
157 void kmem_cache_destroy(struct kmem_cache *cp);
158 /* Front end: clients of caches use these */
159 void *kmem_cache_alloc(struct kmem_cache *cp, int flags);
160 void *kmem_cache_zalloc(struct kmem_cache *cp, int flags);
161 void kmem_cache_free(struct kmem_cache *cp, void *buf);
162 /* Back end: internal functions */
163 void kmem_cache_init(void);
164 void kmem_cache_reap(struct kmem_cache *cp);
165 unsigned int kmc_nr_pcpu_caches(void);
166 /* Low-level interface for creating/destroying; caller manages kc's memory */
167 void __kmem_cache_create(struct kmem_cache *kc, const char *name,
168                          size_t obj_size, int align, int flags,
169                          struct arena *source,
170                          int (*ctor)(void *, void *, int),
171                          void (*dtor)(void *, void *), void *priv);
172 void __kmem_cache_destroy(struct kmem_cache *cp);
173
174 /* Tracing */
175 int kmem_trace_start(struct kmem_cache *kc);
176 void kmem_trace_stop(struct kmem_cache *kc);
177 struct sized_alloc *kmem_trace_print(struct kmem_cache *kc);
178 void kmem_trace_reset(struct kmem_cache *kc);