Add the Inferno license to files we got from Inferno
[akaros.git] / kern / src / ns / allocb.c
1 /* Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
2  * Portions Copyright © 1997-1999 Vita Nuova Limited
3  * Portions Copyright © 2000-2007 Vita Nuova Holdings Limited
4  *                                (www.vitanuova.com)
5  * Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
6  *
7  * Modified for the Akaros operating system:
8  * Copyright (c) 2013-2014 The Regents of the University of California
9  * Copyright (c) 2013-2015 Google Inc.
10  *
11  * Permission is hereby granted, free of charge, to any person obtaining a copy
12  * of this software and associated documentation files (the "Software"), to deal
13  * in the Software without restriction, including without limitation the rights
14  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15  * copies of the Software, and to permit persons to whom the Software is
16  * furnished to do so, subject to the following conditions:
17  *
18  * The above copyright notice and this permission notice shall be included in
19  * all copies or substantial portions of the Software.
20  *
21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
24  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
27  * SOFTWARE. */
28
29 #include <vfs.h>
30 #include <kfs.h>
31 #include <slab.h>
32 #include <kmalloc.h>
33 #include <kref.h>
34 #include <string.h>
35 #include <stdio.h>
36 #include <assert.h>
37 #include <error.h>
38 #include <cpio.h>
39 #include <pmap.h>
40 #include <smp.h>
41 #include <ip.h>
42 #include <process.h>
43
44 /* Note that Hdrspc is only available via padblock (to the 'left' of the rp). */
45 enum {
46         Hdrspc = 128,           /* leave room for high-level headers */
47         Bdead = 0x51494F42,     /* "QIOB" */
48         BLOCKALIGN = 32,        /* was the old BY2V in inferno, which was 8 */
49 };
50
51 static atomic_t ialloc_bytes = 0;
52
53 /*
54  *  allocate blocks (round data base address to 64 bit boundary).
55  *  if mallocz gives us more than we asked for, leave room at the front
56  *  for header.
57  */
58 static struct block *_allocb(int size, int mem_flags)
59 {
60         struct block *b;
61         uintptr_t addr;
62         int n;
63
64         b = kmalloc(sizeof(struct block) + size + Hdrspc + (BLOCKALIGN - 1),
65                                 mem_flags);
66         if (b == NULL)
67                 return NULL;
68
69         b->next = NULL;
70         b->list = NULL;
71         b->free = NULL;
72         b->flag = 0;
73         b->extra_len = 0;
74         b->nr_extra_bufs = 0;
75         b->extra_data = 0;
76
77         addr = (uintptr_t) b;
78         addr = ROUNDUP(addr + sizeof(struct block), BLOCKALIGN);
79         b->base = (uint8_t *) addr;
80         /* TODO: support this */
81         /* interesting. We can ask the allocator, after allocating,
82          * the *real* size of the block we got. Very nice.
83          * Not on akaros yet.
84          b->lim = ((uint8_t*)b) + msize(b);
85          */
86         b->lim =
87                 ((uint8_t *) b) + sizeof(struct block) + size + Hdrspc + (BLOCKALIGN -
88                                                                                                                                   1);
89         b->rp = b->base;
90         n = b->lim - b->base - size;
91         b->rp += n & ~(BLOCKALIGN - 1);
92         b->wp = b->rp;
93         /* b->base is aligned, rounded up from b
94          * b->lim is the upper bound on our malloc
95          * b->rp is advanced by some aligned amount, based on how much extra we
96          * received from kmalloc and the Hdrspc. */
97         return b;
98 }
99
100 struct block *allocb(int size)
101 {
102         return _allocb(size, KMALLOC_WAIT);
103 }
104
105 /* Makes sure b has nr_bufs extra_data.  Will grow, but not shrink, an existing
106  * extra_data array.  When growing, it'll copy over the old entries.  All new
107  * entries will be zeroed.  mem_flags determines if we'll block on kmallocs.
108  *
109  * Return 0 on success or -1 on error.
110  * Caller is responsible for concurrent access to the block's metadata. */
111 int block_add_extd(struct block *b, unsigned int nr_bufs, int mem_flags)
112 {
113         unsigned int old_nr_bufs = b->nr_extra_bufs;
114         size_t old_amt = sizeof(struct extra_bdata) * old_nr_bufs;
115         size_t new_amt = sizeof(struct extra_bdata) * nr_bufs;
116         void *new_bdata;
117
118         if (old_nr_bufs >= nr_bufs)
119                 return 0;
120         if (b->extra_data) {
121                 new_bdata = krealloc(b->extra_data, new_amt, mem_flags);
122                 if (!new_bdata)
123                         return -1;
124                 memset(new_bdata + old_amt, 0, new_amt - old_amt);
125         } else {
126                 new_bdata = kzmalloc(new_amt, mem_flags);
127                 if (!new_bdata)
128                         return - 1;
129         }
130         b->extra_data = new_bdata;
131         b->nr_extra_bufs = nr_bufs;
132         return 0;
133 }
134
135 /* Go backwards from the end of the list, remember the last unused slot, and
136  * stop when a used slot is encountered. */
137 static struct extra_bdata *next_unused_slot(struct block *b)
138 {
139         struct extra_bdata *ebd = NULL;
140
141         for (int i = b->nr_extra_bufs - 1; i >= 0; i--) {
142                 if (b->extra_data[i].base)
143                         break;
144                 ebd = &b->extra_data[i];
145         }
146         return ebd;
147 }
148
149 /* Append a zero-filled extra data buffer of length @len to block @b.
150  * Reuse an unused extra data slot if there's any.
151  * Return 0 on success or -1 on error. */
152 int block_append_extra(struct block *b, int len, int mem_flags)
153 {
154         unsigned int nr_bufs = b->nr_extra_bufs + 1;
155         struct extra_bdata *ebd;
156
157         ebd = next_unused_slot(b);
158         if (!ebd) {
159                 if (block_add_extd(b, nr_bufs, mem_flags) != 0)
160                         return -1;
161                 ebd = next_unused_slot(b);
162                 assert(ebd);
163         }
164         ebd->base = (uintptr_t)kzmalloc(len, mem_flags);
165         if (!ebd->base)
166                 return -1;
167         ebd->off = 0;
168         ebd->len = len;
169         b->extra_len += ebd->len;
170         return 0;
171 }
172
173 /*
174  *  interrupt time allocation
175  */
176 struct block *iallocb(int size)
177 {
178         struct block *b;
179
180 #if 0   /* conf is some inferno global config */
181         if (atomic_read(&ialloc_bytes) > conf.ialloc) {
182                 //printk("iallocb: limited %lu/%lu\n", atomic_read(&ialloc_bytes),
183                 //       conf.ialloc);
184                 return NULL;
185         }
186 #endif
187
188         b = _allocb(size, 0);   /* no KMALLOC_WAIT */
189         if (b == NULL) {
190                 //printk("iallocb: no memory %lu/%lu\n", atomic_read(&ialloc_bytes),
191                 //       conf.ialloc);
192                 return NULL;
193         }
194         b->flag = BINTR;
195
196         atomic_add(&ialloc_bytes, b->lim - b->base);
197
198         return b;
199 }
200
201 void free_block_extra(struct block *b)
202 {
203         struct extra_bdata *ebd;
204
205         /* assuming our release method is kfree, which will change when we support
206          * user buffers */
207         for (int i = 0; i < b->nr_extra_bufs; i++) {
208                 ebd = &b->extra_data[i];
209                 if (ebd->base)
210                         kfree((void*)ebd->base);
211         }
212         b->extra_len = 0;
213         b->nr_extra_bufs = 0;
214         kfree(b->extra_data);   /* harmless if it is 0 */
215         b->extra_data = 0;              /* in case the block is reused by a free override */
216 }
217
218 void freeb(struct block *b)
219 {
220         void *dead = (void *)Bdead;
221
222         if (b == NULL)
223                 return;
224
225         free_block_extra(b);
226         /*
227          * drivers which perform non cache coherent DMA manage their own buffer
228          * pool of uncached buffers and provide their own free routine.
229          */
230         if (b->free) {
231                 b->free(b);
232                 return;
233         }
234         if (b->flag & BINTR) {
235                 /* subtracting the size of b */
236                 atomic_add(&ialloc_bytes, -(b->lim - b->base));
237         }
238
239         /* poison the block in case someone is still holding onto it */
240         b->next = dead;
241         b->rp = dead;
242         b->wp = dead;
243         b->lim = dead;
244         b->base = dead;
245
246         kfree(b);
247 }
248
249 void checkb(struct block *b, char *msg)
250 {
251         void *dead = (void *)Bdead;
252         struct extra_bdata *ebd;
253
254         if (b == dead)
255                 panic("checkb b %s 0x%lx", msg, b);
256         if (b->base == dead || b->lim == dead || b->next == dead
257                 || b->rp == dead || b->wp == dead) {
258                 printd("checkb: base 0x%8.8lx lim 0x%8.8lx next 0x%8.8lx\n",
259                            b->base, b->lim, b->next);
260                 printd("checkb: rp 0x%8.8lx wp 0x%8.8lx\n", b->rp, b->wp);
261                 panic("checkb dead: %s\n", msg);
262         }
263
264         if (b->base > b->lim)
265                 panic("checkb 0 %s 0x%lx 0x%lx", msg, b->base, b->lim);
266         if (b->rp < b->base)
267                 panic("checkb 1 %s 0x%lx 0x%lx", msg, b->base, b->rp);
268         if (b->wp < b->base)
269                 panic("checkb 2 %s 0x%lx 0x%lx", msg, b->base, b->wp);
270         if (b->rp > b->lim)
271                 panic("checkb 3 %s 0x%lx 0x%lx", msg, b->rp, b->lim);
272         if (b->wp > b->lim)
273                 panic("checkb 4 %s 0x%lx 0x%lx", msg, b->wp, b->lim);
274         if (b->nr_extra_bufs && !b->extra_data)
275                 panic("checkb 5 %s missing extra_data", msg);
276
277         for (int i = 0; i < b->nr_extra_bufs; i++) {
278                 ebd = &b->extra_data[i];
279                 if (ebd->base) {
280                         if (!kmalloc_refcnt((void*)ebd->base))
281                                 panic("checkb buf %d, base %p has no refcnt!\n", i, ebd->base);
282                 }
283         }
284
285 }
286
287 void iallocsummary(void)
288 {
289         printd("ialloc %lu/%lu\n", atomic_read(&ialloc_bytes), 0 /*conf.ialloc */ );
290 }
291
292 void printblock(struct block *b)
293 {
294         unsigned char *c;
295         unsigned int off, elen;
296         struct extra_bdata *e;
297
298         if (b == NULL) {
299                 printk("block is null\n");
300                 return;
301         }
302
303         printk("block of BLEN = %d, with %d header and %d data in %d extras\n",
304                BLEN(b), BHLEN(b), b->extra_len, b->nr_extra_bufs);
305
306         printk("header:\n");
307         printk("%2x:\t", 0);
308         off = 0;
309         for (c = b->rp; c < b->wp; c++) {
310                 printk("  %02x", *c & 0xff);
311                 off++;
312                 if (off % 8 == 0) {
313                         printk("\n");
314                         printk("%2x:\t", off);
315                 }
316         }
317         printk("\n");
318         elen = b->extra_len;
319         for (int i = 0; (i < b->nr_extra_bufs) && elen; i++) {
320                 e = &b->extra_data[i];
321                 if (e->len == 0)
322                         continue;
323                 elen -= e->len;
324                 printk("data %d:\n", i);
325                 printk("%2x:\t", 0);
326                 for (off = 0; off < e->len; off++) {
327                         c = (unsigned char *)e->base + e->off + off;
328                         printk("  %02x", *c & 0xff);
329                         if ((off + 1) % 8 == 0 && off +1 < e->len) {
330                                 printk("\n");
331                                 printk("%2x:\t", off + 1);
332                         }
333                 }
334         }
335         printk("\n");
336 }