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