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