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