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