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