Fixes slab page allocators
[akaros.git] / user / parlib / slab.c
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  * Note that we don't have a hash table for buf to bufctl for the large buffer
10  * objects, so we use the same style for small objects: store the pointer to the
11  * controlling bufctl at the top of the slab object.  Fix this with TODO (BUF).
12  *
13  * Ported directly from the kernel's slab allocator. */
14
15 #include <slab.h>
16 #include <stdio.h>
17 #include <assert.h>
18 #include <sys/mman.h>
19
20 struct kmem_cache_list kmem_caches;
21 struct mcs_pdr_lock kmem_caches_lock;
22
23 /* Backend/internal functions, defined later.  Grab the lock before calling
24  * these. */
25 static void kmem_cache_grow(struct kmem_cache *cp);
26
27 /* Cache of the kmem_cache objects, needed for bootstrapping */
28 struct kmem_cache kmem_cache_cache;
29 struct kmem_cache *kmem_slab_cache, *kmem_bufctl_cache;
30
31 static void __kmem_cache_create(struct kmem_cache *kc, const char *name,
32                                 size_t obj_size, int align, int flags,
33                                 void (*ctor)(void *, size_t),
34                                 void (*dtor)(void *, size_t))
35 {
36         assert(kc);
37         assert(align);
38         mcs_pdr_init(&kc->cache_lock);
39         kc->name = name;
40         kc->obj_size = obj_size;
41         kc->align = align;
42         kc->flags = flags;
43         TAILQ_INIT(&kc->full_slab_list);
44         TAILQ_INIT(&kc->partial_slab_list);
45         TAILQ_INIT(&kc->empty_slab_list);
46         kc->ctor = ctor;
47         kc->dtor = dtor;
48         kc->nr_cur_alloc = 0;
49         
50         /* put in cache list based on it's size */
51         struct kmem_cache *i, *prev = NULL;
52         mcs_pdr_lock(&kmem_caches_lock);
53         /* find the kmem_cache before us in the list.  yes, this is O(n). */
54         SLIST_FOREACH(i, &kmem_caches, link) {
55                 if (i->obj_size < kc->obj_size)
56                         prev = i;
57                 else
58                         break;
59         }
60         if (prev)
61                 SLIST_INSERT_AFTER(prev, kc, link);
62         else
63                 SLIST_INSERT_HEAD(&kmem_caches, kc, link);
64         mcs_pdr_unlock(&kmem_caches_lock);
65 }
66
67 void kmem_cache_init(void)
68 {
69         mcs_pdr_init(&kmem_caches_lock);
70         SLIST_INIT(&kmem_caches);
71         /* We need to call the __ version directly to bootstrap the global
72          * kmem_cache_cache. */
73         __kmem_cache_create(&kmem_cache_cache, "kmem_cache",
74                             sizeof(struct kmem_cache),
75                             __alignof__(struct kmem_cache), 0, NULL, NULL);
76         /* Build the slab and bufctl caches */
77         kmem_slab_cache = kmem_cache_alloc(&kmem_cache_cache, 0);
78         __kmem_cache_create(kmem_slab_cache, "kmem_slab", sizeof(struct kmem_slab),
79                             __alignof__(struct kmem_slab), 0, NULL, NULL); 
80         kmem_bufctl_cache = kmem_cache_alloc(&kmem_cache_cache, 0);
81         __kmem_cache_create(kmem_bufctl_cache, "kmem_bufctl",
82                             sizeof(struct kmem_bufctl),
83                             __alignof__(struct kmem_bufctl), 0, NULL, NULL); 
84 }
85
86 /* Cache management */
87 struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
88                                      int align, int flags,
89                                      void (*ctor)(void *, size_t),
90                                      void (*dtor)(void *, size_t))
91 {
92         run_once(kmem_cache_init());
93         struct kmem_cache *kc = kmem_cache_alloc(&kmem_cache_cache, 0);
94         __kmem_cache_create(kc, name, obj_size, align, flags, ctor, dtor);
95         return kc;
96 }
97
98 static void kmem_slab_destroy(struct kmem_cache *cp, struct kmem_slab *a_slab)
99 {
100         if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
101                 /* Deconstruct all the objects, if necessary */
102                 if (cp->dtor) {
103                         void *buf = a_slab->free_small_obj;
104                         for (int i = 0; i < a_slab->num_total_obj; i++) {
105                                 cp->dtor(buf, cp->obj_size);
106                                 buf += a_slab->obj_size;
107                         }
108                 }
109                 munmap(ROUNDDOWN(a_slab, PGSIZE), PGSIZE);
110         } else {
111                 struct kmem_bufctl *i;
112                 void *page_start = (void*)-1;
113                 /* compute how many pages are allocated, same as in grow */
114                 size_t nr_pgs = ROUNDUP(NUM_BUF_PER_SLAB * a_slab->obj_size, PGSIZE) /
115                                         PGSIZE;
116                 TAILQ_FOREACH(i, &a_slab->bufctl_freelist, link) {
117                         // Track the lowest buffer address, which is the start of the buffer
118                         page_start = MIN(page_start, i->buf_addr);
119                         /* Deconstruct all the objects, if necessary */
120                         if (cp->dtor) // TODO: (BUF)
121                                 cp->dtor(i->buf_addr, cp->obj_size);
122                         kmem_cache_free(kmem_bufctl_cache, i);
123                 }
124                 // free the pages for the slab's buffer
125                 munmap(page_start, nr_pgs * PGSIZE);
126                 // free the slab object
127                 kmem_cache_free(kmem_slab_cache, a_slab);
128         }
129 }
130
131 /* Once you call destroy, never use this cache again... o/w there may be weird
132  * races, and other serious issues.  */
133 void kmem_cache_destroy(struct kmem_cache *cp)
134 {
135         struct kmem_slab *a_slab, *next;
136
137         mcs_pdr_lock(&cp->cache_lock);
138         assert(TAILQ_EMPTY(&cp->full_slab_list));
139         assert(TAILQ_EMPTY(&cp->partial_slab_list));
140         /* Clean out the empty list.  We can't use a regular FOREACH here, since the
141          * link element is stored in the slab struct, which is stored on the page
142          * that we are freeing. */
143         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
144         while (a_slab) {
145                 next = TAILQ_NEXT(a_slab, link);
146                 kmem_slab_destroy(cp, a_slab);
147                 a_slab = next;
148         }
149         mcs_pdr_lock(&kmem_caches_lock);
150         SLIST_REMOVE(&kmem_caches, cp, kmem_cache, link);
151         mcs_pdr_unlock(&kmem_caches_lock);
152         kmem_cache_free(&kmem_cache_cache, cp); 
153         mcs_pdr_unlock(&cp->cache_lock);
154 }
155
156 /* Front end: clients of caches use these */
157 void *kmem_cache_alloc(struct kmem_cache *cp, int flags)
158 {
159         void *retval = NULL;
160         mcs_pdr_lock(&cp->cache_lock);
161         // look at partial list
162         struct kmem_slab *a_slab = TAILQ_FIRST(&cp->partial_slab_list);
163         //      if none, go to empty list and get an empty and make it partial
164         if (!a_slab) {
165                 if (TAILQ_EMPTY(&cp->empty_slab_list))
166                         // TODO: think about non-sleeping flags
167                         kmem_cache_grow(cp);
168                 // move to partial list
169                 a_slab = TAILQ_FIRST(&cp->empty_slab_list);
170                 TAILQ_REMOVE(&cp->empty_slab_list, a_slab, link);
171                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
172         } 
173         // have a partial now (a_slab), get an item, return item
174         if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
175                 retval = a_slab->free_small_obj;
176                 /* adding the size of the cache_obj to get to the pointer at end of the
177                  * buffer pointing to the next free_small_obj */
178                 a_slab->free_small_obj = *(uintptr_t**)(a_slab->free_small_obj +
179                                                         cp->obj_size);
180         } else {
181                 // rip the first bufctl out of the partial slab's buf list
182                 struct kmem_bufctl *a_bufctl = TAILQ_FIRST(&a_slab->bufctl_freelist);
183                 TAILQ_REMOVE(&a_slab->bufctl_freelist, a_bufctl, link);
184                 retval = a_bufctl->buf_addr;
185         }
186         a_slab->num_busy_obj++;
187         // Check if we are full, if so, move to the full list
188         if (a_slab->num_busy_obj == a_slab->num_total_obj) {
189                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
190                 TAILQ_INSERT_HEAD(&cp->full_slab_list, a_slab, link);
191         }
192         cp->nr_cur_alloc++;
193         mcs_pdr_unlock(&cp->cache_lock);
194         return retval;
195 }
196
197 static inline struct kmem_bufctl *buf2bufctl(void *buf, size_t offset)
198 {
199         // TODO: hash table for back reference (BUF)
200         return *((struct kmem_bufctl**)(buf + offset));
201 }
202
203 void kmem_cache_free(struct kmem_cache *cp, void *buf)
204 {
205         struct kmem_slab *a_slab;
206         struct kmem_bufctl *a_bufctl;
207
208         mcs_pdr_lock(&cp->cache_lock);
209         if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
210                 // find its slab
211                 a_slab = (struct kmem_slab*)(ROUNDDOWN(buf, PGSIZE) + PGSIZE -
212                                              sizeof(struct kmem_slab));
213                 /* write location of next free small obj to the space at the end of the
214                  * buffer, then list buf as the next free small obj */
215                 *(uintptr_t**)(buf + cp->obj_size) = a_slab->free_small_obj;
216                 a_slab->free_small_obj = buf;
217         } else {
218                 /* Give the bufctl back to the parent slab */
219                 // TODO: (BUF) change the interface to not take an offset
220                 a_bufctl = buf2bufctl(buf, cp->obj_size);
221                 a_slab = a_bufctl->my_slab;
222                 TAILQ_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
223         }
224         a_slab->num_busy_obj--;
225         cp->nr_cur_alloc--;
226         // if it was full, move it to partial
227         if (a_slab->num_busy_obj + 1 == a_slab->num_total_obj) {
228                 TAILQ_REMOVE(&cp->full_slab_list, a_slab, link);
229                 TAILQ_INSERT_HEAD(&cp->partial_slab_list, a_slab, link);
230         } else if (!a_slab->num_busy_obj) {
231                 // if there are none, move to from partial to empty
232                 TAILQ_REMOVE(&cp->partial_slab_list, a_slab, link);
233                 TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
234         }
235         mcs_pdr_unlock(&cp->cache_lock);
236 }
237
238 /* Back end: internal functions */
239 /* When this returns, the cache has at least one slab in the empty list.  If
240  * page_alloc fails, there are some serious issues.  This only grows by one slab
241  * at a time.
242  *
243  * Grab the cache lock before calling this.
244  *
245  * TODO: think about page colouring issues with kernel memory allocation. */
246 static void kmem_cache_grow(struct kmem_cache *cp)
247 {
248         struct kmem_slab *a_slab;
249         struct kmem_bufctl *a_bufctl;
250         void *a_page;
251         if (cp->obj_size <= SLAB_LARGE_CUTOFF) {
252                 // Just get a single page for small slabs
253                 a_page = mmap(0, PGSIZE, PROT_READ | PROT_WRITE,
254                               MAP_POPULATE | MAP_ANONYMOUS, -1, 0);
255                 assert(a_page != MAP_FAILED);
256                 // the slab struct is stored at the end of the page
257                 a_slab = (struct kmem_slab*)(a_page + PGSIZE -
258                                              sizeof(struct kmem_slab));
259                 // Need to add room for the next free item pointer in the object buffer.
260                 a_slab->obj_size = ROUNDUP(cp->obj_size + sizeof(uintptr_t), cp->align);
261                 a_slab->num_busy_obj = 0;
262                 a_slab->num_total_obj = (PGSIZE - sizeof(struct kmem_slab)) /
263                                         a_slab->obj_size;
264                 // TODO: consider staggering this IAW section 4.3
265                 a_slab->free_small_obj = a_page;
266                 /* Walk and create the free list, which is circular.  Each item stores
267                  * the location of the next one at the end of the block. */
268                 void *buf = a_slab->free_small_obj;
269                 for (int i = 0; i < a_slab->num_total_obj - 1; i++) {
270                         // Initialize the object, if necessary
271                         if (cp->ctor)
272                                 cp->ctor(buf, cp->obj_size);
273                         *(uintptr_t**)(buf + cp->obj_size) = buf + a_slab->obj_size;
274                         buf += a_slab->obj_size;
275                 }
276                 *((uintptr_t**)(buf + cp->obj_size)) = NULL;
277         } else {
278                 a_slab = kmem_cache_alloc(kmem_slab_cache, 0);
279                 // TODO: hash table for back reference (BUF)
280                 a_slab->obj_size = ROUNDUP(cp->obj_size + sizeof(uintptr_t), cp->align);
281                 /* Need at least nr_pgs to hold NUM_BUF objects.  Note we don't round up
282                  * to the next higher order (power of 2) number of pages, like we do in
283                  * the kernel. */
284                 size_t nr_pgs = ROUNDUP(NUM_BUF_PER_SLAB * a_slab->obj_size, PGSIZE) /
285                                          PGSIZE;
286                 void *buf = mmap(0, nr_pgs * PGSIZE, PROT_READ | PROT_WRITE,
287                                  MAP_POPULATE | MAP_ANONYMOUS, -1, 0);
288                 assert(buf != MAP_FAILED);
289                 a_slab->num_busy_obj = 0;
290                 a_slab->num_total_obj = nr_pgs * PGSIZE / a_slab->obj_size;
291                 TAILQ_INIT(&a_slab->bufctl_freelist);
292                 /* for each buffer, set up a bufctl and point to the buffer */
293                 for (int i = 0; i < a_slab->num_total_obj; i++) {
294                         // Initialize the object, if necessary
295                         if (cp->ctor)
296                                 cp->ctor(buf, cp->obj_size);
297                         a_bufctl = kmem_cache_alloc(kmem_bufctl_cache, 0);      
298                         TAILQ_INSERT_HEAD(&a_slab->bufctl_freelist, a_bufctl, link);
299                         a_bufctl->buf_addr = buf;
300                         a_bufctl->my_slab = a_slab;
301                         // TODO: (BUF) write the bufctl reference at the bottom of the buffer.
302                         *(struct kmem_bufctl**)(buf + cp->obj_size) = a_bufctl;
303                         buf += a_slab->obj_size;
304                 }
305         }
306         // add a_slab to the empty_list
307         TAILQ_INSERT_HEAD(&cp->empty_slab_list, a_slab, link);
308 }
309
310 /* This deallocs every slab from the empty list.  TODO: think a bit more about
311  * this.  We can do things like not free all of the empty lists to prevent
312  * thrashing.  See 3.4 in the paper. */
313 void kmem_cache_reap(struct kmem_cache *cp)
314 {
315         struct kmem_slab *a_slab, *next;
316         
317         // Destroy all empty slabs.  Refer to the notes about the while loop
318         mcs_pdr_lock(&cp->cache_lock);
319         a_slab = TAILQ_FIRST(&cp->empty_slab_list);
320         while (a_slab) {
321                 next = TAILQ_NEXT(a_slab, link);
322                 kmem_slab_destroy(cp, a_slab);
323                 a_slab = next;
324         }
325         mcs_pdr_unlock(&cp->cache_lock);
326 }
327
328 void print_kmem_cache(struct kmem_cache *cp)
329 {
330         mcs_pdr_lock(&cp->cache_lock);
331         printf("\nPrinting kmem_cache:\n---------------------\n");
332         printf("Name: %s\n", cp->name);
333         printf("Objsize: %d\n", cp->obj_size);
334         printf("Align: %d\n", cp->align);
335         printf("Flags: 0x%08x\n", cp->flags);
336         printf("Constructor: 0x%08x\n", cp->ctor);
337         printf("Destructor: 0x%08x\n", cp->dtor);
338         printf("Slab Full: 0x%08x\n", cp->full_slab_list);
339         printf("Slab Partial: 0x%08x\n", cp->partial_slab_list);
340         printf("Slab Empty: 0x%08x\n", cp->empty_slab_list);
341         printf("Current Allocations: %d\n", cp->nr_cur_alloc);
342         mcs_pdr_unlock(&cp->cache_lock);
343 }
344
345 void print_kmem_slab(struct kmem_slab *slab)
346 {
347         printf("\nPrinting kmem_slab:\n---------------------\n");
348         printf("Objsize: %d (%p)\n", slab->obj_size, slab->obj_size);
349         printf("NumBusy: %d\n", slab->num_busy_obj);
350         printf("Num_total: %d\n", slab->num_total_obj);
351         if (slab->obj_size + sizeof(uintptr_t) < SLAB_LARGE_CUTOFF) {
352                 printf("Free Small obj: 0x%08x\n", slab->free_small_obj);
353                 void *buf = slab->free_small_obj;
354                 for (int i = 0; i < slab->num_total_obj; i++) {
355                         printf("Addr of buf: 0x%08x, Addr of next: 0x%08x\n", buf,
356                                *((uintptr_t**)buf));
357                         buf += slab->obj_size;
358                 }
359         } else {
360                 printf("This is a big slab!\n");
361         }
362 }
363