For your inspection: small id pool
[akaros.git] / kern / src / kmalloc.c
1 /* Copyright (c) 2009 The Regents of the University of California. 
2  * See the COPYRIGHT files at the top of this source tree for full 
3  * license information.
4  * 
5  * Barret Rhoden <brho@cs.berkeley.edu>
6  * Kevin Klues <klueska@cs.berkeley.edu>    
7  */
8
9 #ifdef __SHARC__
10 #pragma nosharc
11 #define SINIT(x) x
12 #endif
13
14 #ifdef __DEPUTY__
15 #pragma nodeputy
16 #endif
17
18 #include <ros/common.h>
19 #include <error.h>
20 #include <pmap.h>
21 #include <kmalloc.h>
22 #include <stdio.h>
23 #include <slab.h>
24 #include <assert.h>
25
26 #define kmallocdebug(args...)  //printk(args)
27
28 //List of physical pages used by kmalloc
29 static spinlock_t pages_list_lock = SPINLOCK_INITIALIZER;
30 static page_list_t LCKD(&pages_list_lock)pages_list;
31
32 struct kmem_cache *kmalloc_caches[NUM_KMALLOC_CACHES];
33
34 static void __kfree_release(struct kref *kref);
35
36 void kmalloc_init(void)
37 {
38         /* we want at least a 16 byte alignment of the tag so that the bufs kmalloc
39          * returns are 16 byte aligned.  we used to check the actual size == 16,
40          * since we adjusted the KMALLOC_SMALLEST based on that. */
41         static_assert(ALIGNED(sizeof(struct kmalloc_tag), 16));
42         /* build caches of common sizes.  this size will later include the tag and
43          * the actual returned buffer. */
44         size_t ksize = KMALLOC_SMALLEST;
45         for (int i = 0; i < NUM_KMALLOC_CACHES; i++) {
46                 kmalloc_caches[i] = kmem_cache_create("kmalloc_cache", ksize,
47                                                       KMALLOC_ALIGNMENT, 0, 0, 0);
48                 ksize <<= 1;
49         }
50 }
51
52 void *kmalloc(size_t size, int flags) 
53 {
54         // reserve space for bookkeeping and preserve alignment
55         size_t ksize = size + sizeof(struct kmalloc_tag);
56         void *buf;
57         int cache_id;
58         // determine cache to pull from
59         if (0)
60         if ((size < 9 ) && (!printx_on)) {
61                 extern bool printx_on;
62                 printx_on = 1;
63                 printk("alloc one lousy 64-bit int? \n");
64                 monitor(NULL);
65                 printx_on = 0;
66         }
67         if (ksize <= KMALLOC_SMALLEST)
68                 cache_id = 0;
69         else
70                 cache_id = LOG2_UP(ksize) - LOG2_UP(KMALLOC_SMALLEST);
71         // if we don't have a cache to handle it, alloc cont pages
72         if (cache_id >= NUM_KMALLOC_CACHES) {
73                 size_t num_pgs = ROUNDUP(size + sizeof(struct kmalloc_tag), PGSIZE) /
74                                            PGSIZE;
75                 buf = get_cont_pages(LOG2_UP(num_pgs), flags);
76                 if (!buf)
77                         panic("Kmalloc failed!  Handle me!");
78                 // fill in the kmalloc tag
79                 struct kmalloc_tag *tag = buf;
80                 tag->flags = KMALLOC_TAG_PAGES;
81                 tag->num_pages = num_pgs;
82                 tag->canary = KMALLOC_CANARY;
83                 kref_init(&tag->kref, __kfree_release, 1);
84                 return buf + sizeof(struct kmalloc_tag);
85         }
86         // else, alloc from the appropriate cache
87         buf = kmem_cache_alloc(kmalloc_caches[cache_id], flags);
88         if (!buf)
89                 panic("Kmalloc failed!  Handle me!");
90         // store a pointer to the buffers kmem_cache in it's bookkeeping space
91         struct kmalloc_tag *tag = buf;
92         tag->flags = KMALLOC_TAG_CACHE;
93         tag->my_cache = kmalloc_caches[cache_id];
94         tag->canary = KMALLOC_CANARY;
95         kref_init(&tag->kref, __kfree_release, 1);
96         return buf + sizeof(struct kmalloc_tag);
97 }
98
99 void *kzmalloc(size_t size, int flags) 
100 {
101         void *v = kmalloc(size, flags);
102         if (!v)
103                 return v;
104         memset(v, 0, size);
105         return v;
106 }
107
108 void *kmalloc_align(size_t size, int flags, size_t align)
109 {
110         void *addr, *retaddr;
111         int *tag_flags, offset;
112         /* alignment requests must be a multiple of long, even though we only need
113          * int in the current code. */
114         assert(ALIGNED(align, sizeof(long)));
115         /* must fit in the space reserved for the offset amount, which is at most
116          * 'align'. */
117         assert(align < (1 << (32 - KMALLOC_ALIGN_SHIFT)));
118         assert(IS_PWR2(align));
119         addr = kmalloc(size + align, flags);
120         if (!addr)
121                 return 0;
122         if (ALIGNED(addr, align))
123                 return addr;
124         retaddr = ROUNDUP(addr, align);
125         offset = retaddr - addr;
126         assert(offset < align);
127         /* we might not have room for a full tag.  we might have only 8 bytes.  but
128          * we'll at least have room for the flags part. */
129         tag_flags = (int*)(retaddr - sizeof(int));
130         *tag_flags = (offset << KMALLOC_ALIGN_SHIFT) | KMALLOC_TAG_UNALIGN;
131         return retaddr;
132 }
133
134 void *kzmalloc_align(size_t size, int flags, size_t align)
135 {
136         void *v = kmalloc_align(size, flags, align);
137         if (!v)
138                 return v;
139         memset(v, 0, size);
140         return v;
141 }
142
143 static struct kmalloc_tag *__get_km_tag(void *buf)
144 {
145         struct kmalloc_tag *tag = (struct kmalloc_tag*)(buf -
146                                                     sizeof(struct kmalloc_tag));
147         if (tag->canary != KMALLOC_CANARY){
148                 printk("__get_km_tag bad canary: %08lx, expected %08lx\n", tag->canary,
149                        KMALLOC_CANARY);
150                 hexdump((void *)(buf - sizeof(struct kmalloc_tag)), 256);
151                 panic("Bad canary");
152         }
153         return tag;
154 }
155
156 /* If we kmalloc_aligned, the buf we got back (and are now trying to perform
157  * some operation on) might not be the original, underlying, unaligned buf.
158  *
159  * This returns the underlying, unaligned buf, or 0 if the buf was not realigned
160  * in the first place. */
161 static void *__get_unaligned_orig_buf(void *buf)
162 {
163         int *tag_flags = (int*)(buf - sizeof(int));
164         if ((*tag_flags & KMALLOC_FLAG_MASK) == KMALLOC_TAG_UNALIGN)
165                 return (buf - (*tag_flags >> KMALLOC_ALIGN_SHIFT));
166         else
167                 return 0;
168 }
169
170 void *krealloc(void* buf, size_t size, int flags)
171 {
172         void *nbuf;
173         size_t osize = 0;
174         struct kmalloc_tag *tag;
175
176         if (buf){
177                 if (__get_unaligned_orig_buf(buf))
178                         panic("krealloc of a kmalloc_align not supported");
179                 tag = __get_km_tag(buf);
180                 /* whatever we got from either a slab or the page allocator is meant for
181                  * both the buf+size as well as the kmalloc tag */
182                 if ((tag->flags & KMALLOC_FLAG_MASK) == KMALLOC_TAG_CACHE) {
183                         osize = tag->my_cache->obj_size - sizeof(struct kmalloc_tag);
184                 } else if ((tag->flags & KMALLOC_FLAG_MASK) == KMALLOC_TAG_PAGES) {
185                         osize = LOG2_UP(tag->num_pages) * PGSIZE
186                                 - sizeof(struct kmalloc_tag);
187                 } else {
188                         panic("Probably a bad tag, flags %p\n", tag->flags);
189                 }
190                 if (osize >= size)
191                         return buf;
192         }
193
194         nbuf = kmalloc(size, flags);
195
196         /* would be more interesting to user error(...) here. */
197         /* but in any event, NEVER destroy buf! */
198         if (! nbuf)
199                 return NULL;
200
201         if (osize)
202                 memmove(nbuf, buf, osize);
203
204         if (buf)
205                 kfree(buf);
206
207         return nbuf;
208 }
209
210 /* Grabs a reference on a buffer.  Release with kfree().
211  *
212  * Note that a krealloc on a buffer with ref > 1 that needs a new, underlying
213  * buffer will result in two buffers existing.  In this case, the krealloc is a
214  * kmalloc and a kfree, but that kfree does not completely free since the
215  * original ref > 1. */
216 void kmalloc_incref(void *buf)
217 {
218         void *orig_buf = __get_unaligned_orig_buf(buf);
219         buf = orig_buf ? orig_buf : buf;
220         /* if we want a smaller tag, we can extract the code from kref and manually
221          * set the release method in kfree. */
222         kref_get(&__get_km_tag(buf)->kref, 1);
223 }
224
225 int kmalloc_refcnt(void *buf)
226 {
227         void *orig_buf = __get_unaligned_orig_buf(buf);
228         buf = orig_buf ? orig_buf : buf;
229         return kref_refcnt(&__get_km_tag(buf)->kref);
230 }
231
232 static void __kfree_release(struct kref *kref)
233 {
234         struct kmalloc_tag *tag = container_of(kref, struct kmalloc_tag, kref);
235         if ((tag->flags & KMALLOC_FLAG_MASK) == KMALLOC_TAG_CACHE)
236                 kmem_cache_free(tag->my_cache, tag);
237         else if ((tag->flags & KMALLOC_FLAG_MASK) == KMALLOC_TAG_PAGES)
238                 free_cont_pages(tag, LOG2_UP(tag->num_pages));
239         else
240                 panic("Bad flag 0x%x in %s", tag->flags, __FUNCTION__);
241 }
242
243 void kfree(void *buf)
244 {
245         void *orig_buf;
246         if (buf == NULL)
247                 return;
248         orig_buf = __get_unaligned_orig_buf(buf);
249         buf = orig_buf ? orig_buf : buf;
250         kref_put(&__get_km_tag(buf)->kref);
251 }
252
253 void kmalloc_canary_check(char *str)
254 {
255         if (!debug_canary)
256                 return;
257         struct kmalloc_tag *tag = (struct kmalloc_tag*)(debug_canary -
258                                                         sizeof(struct kmalloc_tag));
259         if (tag->canary != KMALLOC_CANARY)
260                 panic("\t\t KMALLOC CANARY CHECK FAILED %s\n", str);
261 }