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