Add parlib/common.h
[akaros.git] / user / parlib / include / slab.h
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  * There is a list of kmem_cache, which are the caches of objects of a given
10  * size.  This list is sorted in order of size.  Each kmem_cache has three
11  * lists of slabs: full, partial, and empty.  
12  *
13  * For large objects, the kmem_slabs point to bufctls, which have the address
14  * of their large buffers.  These slabs can consist of more than one contiguous
15  * page.
16  *
17  * For small objects, the slabs do not use the bufctls.  Instead, they point to
18  * the next free object in the slab.  The free objects themselves hold the
19  * address of the next free item.  The slab structure is stored at the end of
20  * the page.  There is only one page per slab.
21  *
22  * TODO: Note, that this is a minor pain in the ass, and worth thinking about
23  * before implementing.  To keep the constructor's state valid, we can't just
24  * overwrite things, so we need to add an extra 4-8 bytes per object for the
25  * pointer, and then pass over that data when we return the actual object's
26  * address.  This also might fuck with alignment.
27  *
28  * Ported directly from the kernel's slab allocator. */
29
30 #ifndef PARLIB_SLAB_H
31 #define PARLIB_SLAB_H
32
33 #include <parlib/common.h>
34 #include <ros/arch/mmu.h>
35 #include <sys/queue.h>
36 #include <parlib/arch/atomic.h>
37 #include <parlib/spinlock.h>
38
39 __BEGIN_DECLS
40
41 /* Back in the day, their cutoff for "large objects" was 512B, based on
42  * measurements and on not wanting more than 1/8 of internal fragmentation. */
43 #define NUM_BUF_PER_SLAB 8
44 #define SLAB_LARGE_CUTOFF (PGSIZE / NUM_BUF_PER_SLAB)
45
46 struct kmem_slab;
47
48 /* Control block for buffers for large-object slabs */
49 struct kmem_bufctl {
50         TAILQ_ENTRY(kmem_bufctl) link;
51         void *buf_addr;
52         struct kmem_slab *my_slab;
53 };
54 TAILQ_HEAD(kmem_bufctl_list, kmem_bufctl);
55
56 /* Slabs contain the objects.  Can be either full, partial, or empty,
57  * determined by checking the number of objects busy vs total.  For large
58  * slabs, the bufctl list is used to find a free buffer.  For small, the void*
59  * is used instead.*/
60 struct kmem_slab {
61         TAILQ_ENTRY(kmem_slab) link;
62         size_t obj_size;
63         size_t num_busy_obj;
64         size_t num_total_obj;
65         union {
66                 struct kmem_bufctl_list bufctl_freelist;
67                 void *free_small_obj;
68         };
69 };
70 TAILQ_HEAD(kmem_slab_list, kmem_slab);
71
72 /* Actual cache */
73 struct kmem_cache {
74         SLIST_ENTRY(kmem_cache) link;
75         struct spin_pdr_lock cache_lock;
76         const char *name;
77         size_t obj_size;
78         int align;
79         int flags;
80         struct kmem_slab_list full_slab_list;
81         struct kmem_slab_list partial_slab_list;
82         struct kmem_slab_list empty_slab_list;
83         void (*ctor)(void *, size_t);
84         void (*dtor)(void *, size_t);
85         unsigned long nr_cur_alloc;
86 };
87
88 /* List of all kmem_caches, sorted in order of size */
89 SLIST_HEAD(kmem_cache_list, kmem_cache);
90 extern struct kmem_cache_list kmem_caches;
91
92 /* Cache management */
93 struct kmem_cache *kmem_cache_create(const char *name, size_t obj_size,
94                                      int align, int flags,
95                                      void (*ctor)(void *, size_t),
96                                      void (*dtor)(void *, size_t));
97 void kmem_cache_destroy(struct kmem_cache *cp);
98 /* Front end: clients of caches use these */
99 void *kmem_cache_alloc(struct kmem_cache *cp, int flags);
100 void kmem_cache_free(struct kmem_cache *cp, void *buf);
101 /* Back end: internal functions */
102 void kmem_cache_init(void);
103 void kmem_cache_reap(struct kmem_cache *cp);
104
105 /* Debug */
106 void print_kmem_cache(struct kmem_cache *kc);
107 void print_kmem_slab(struct kmem_slab *slab);
108
109 __END_DECLS
110
111 #endif /* PARLIB_SLAB_H */