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 /*
  52  *  allocate blocks (round data base address to 64 bit boundary).
  53  *  if mallocz gives us more than we asked for, leave room at the front
  54  *  for header.
  55  */
  56 struct block *block_alloc(size_t size, int mem_flags)
  57 {
  58         struct block *b;
  59         uintptr_t addr;
  60         int n;
  61
  62         /* If Hdrspc is not block aligned it will cause issues. */
  63         static_assert(Hdrspc % BLOCKALIGN == 0);
  64
  65         b = kmalloc(sizeof(struct block) + size + Hdrspc + (BLOCKALIGN - 1),
  66                                 mem_flags);
  67         if (b == NULL)
  68                 return NULL;
  69
  70         b->next = NULL;
  71         b->list = NULL;
  72         b->free = NULL;
  73         b->flag = 0;
  74         b->extra_len = 0;
  75         b->nr_extra_bufs = 0;
  76         b->extra_data = 0;
  77
  78         addr = (uintptr_t) b;
  79         addr = ROUNDUP(addr + sizeof(struct block), BLOCKALIGN);
  80         b->base = (uint8_t *) addr;
  81         /* TODO: support this */
  82         /* interesting. We can ask the allocator, after allocating,
  83          * the *real* size of the block we got. Very nice.
  84          * Not on akaros yet.
  85          b->lim = ((uint8_t*)b) + msize(b);
  86          * See use of n in commented code below
  87          */
  88         b->lim =
  89                 ((uint8_t *) b) + sizeof(struct block) + size + Hdrspc + (BLOCKALIGN -
  90                                                                                                                                   1);
  91         b->rp = b->base;
  92         /* TODO: support this */
  93         /* n is supposed to be Hdrspc + rear padding + extra reserved memory, but
  94          * since we don't currently support checking how much memory was actually
  95          * reserved, this is always Hdrspc + rear padding. After rounding that down
  96          * to BLOCKALIGN, it's always Hdrpsc since the padding is < BLOCKALIGN.
  97          n = b->lim - b->base - size;
  98          b->rp += n & ~(BLOCKALIGN - 1);
  99          */
 100         b->rp += Hdrspc;
 101         b->wp = b->rp;
 102         /* b->base is aligned, rounded up from b
 103          * b->lim is the upper bound on our malloc
 104          * b->rp is advanced by some aligned amount, based on how much extra we
 105          * received from kmalloc and the Hdrspc. */
 106         return b;
 107 }
 108
 109 /* Makes sure b has nr_bufs extra_data.  Will grow, but not shrink, an existing
 110  * extra_data array.  When growing, it'll copy over the old entries.  All new
 111  * entries will be zeroed.  mem_flags determines if we'll block on kmallocs.
 112  *
 113  * Return 0 on success or -1 on error.
 114  * Caller is responsible for concurrent access to the block's metadata. */
 115 int block_add_extd(struct block *b, unsigned int nr_bufs, int mem_flags)
 116 {
 117         unsigned int old_nr_bufs = b->nr_extra_bufs;
 118         size_t old_amt = sizeof(struct extra_bdata) * old_nr_bufs;
 119         size_t new_amt = sizeof(struct extra_bdata) * nr_bufs;
 120         void *new_bdata;
 121
 122         if (old_nr_bufs >= nr_bufs)
 123                 return 0;
 124         if (b->extra_data) {
 125                 new_bdata = krealloc(b->extra_data, new_amt, mem_flags);
 126                 if (!new_bdata)
 127                         return -1;
 128                 memset(new_bdata + old_amt, 0, new_amt - old_amt);
 129         } else {
 130                 new_bdata = kzmalloc(new_amt, mem_flags);
 131                 if (!new_bdata)
 132                         return - 1;
 133         }
 134         b->extra_data = new_bdata;
 135         b->nr_extra_bufs = nr_bufs;
 136         return 0;
 137 }
 138
 139 /* Go backwards from the end of the list, remember the last unused slot, and
 140  * stop when a used slot is encountered. */
 141 static struct extra_bdata *next_unused_slot(struct block *b)
 142 {
 143         struct extra_bdata *ebd = NULL;
 144
 145         for (int i = b->nr_extra_bufs - 1; i >= 0; i--) {
 146                 if (b->extra_data[i].base)
 147                         break;
 148                 ebd = &b->extra_data[i];
 149         }
 150         return ebd;
 151 }
 152
 153 /* Append an extra data buffer @base with offset @off of length @len to block
 154  * @b.  Reuse an unused extra data slot if there's any.
 155  * Return 0 on success or -1 on error. */
 156 int block_append_extra(struct block *b, uintptr_t base, uint32_t off,
 157                        uint32_t len, int mem_flags)
 158 {
 159         unsigned int nr_bufs = b->nr_extra_bufs + 1;
 160         struct extra_bdata *ebd;
 161
 162         ebd = next_unused_slot(b);
 163         if (!ebd) {
 164                 if (block_add_extd(b, nr_bufs, mem_flags) != 0)
 165                         return -1;
 166                 ebd = next_unused_slot(b);
 167                 assert(ebd);
 168         }
 169         ebd->base = base;
 170         ebd->off = off;
 171         ebd->len = len;
 172         b->extra_len += ebd->len;
 173         return 0;
 174 }
 175
 176 void free_block_extra(struct block *b)
 177 {
 178         struct extra_bdata *ebd;
 179
 180         /* assuming our release method is kfree, which will change when we support
 181          * user buffers */
 182         for (int i = 0; i < b->nr_extra_bufs; i++) {
 183                 ebd = &b->extra_data[i];
 184                 if (ebd->base)
 185                         kfree((void*)ebd->base);
 186         }
 187         b->extra_len = 0;
 188         b->nr_extra_bufs = 0;
 189         kfree(b->extra_data);   /* harmless if it is 0 */
 190         b->extra_data = 0;              /* in case the block is reused by a free override */
 191 }
 192
 193 /* Frees a block, returning its size (len, not alloc) */
 194 size_t freeb(struct block *b)
 195 {
 196         void *dead = (void *)Bdead;
 197         size_t ret;
 198
 199         if (b == NULL)
 200                 return 0;
 201         ret = BLEN(b);
 202         free_block_extra(b);
 203         /*
 204          * drivers which perform non cache coherent DMA manage their own buffer
 205          * pool of uncached buffers and provide their own free routine.
 206          */
 207         if (b->free) {
 208                 b->free(b);
 209                 return ret;
 210         }
 211         /* poison the block in case someone is still holding onto it */
 212         b->next = dead;
 213         b->rp = dead;
 214         b->wp = dead;
 215         b->lim = dead;
 216         b->base = dead;
 217         kfree(b);
 218         return ret;
 219 }
 220
 221 /* Free a list of blocks, returning their total size. */
 222 size_t freeblist(struct block *b)
 223 {
 224         struct block *next;
 225         size_t ret = 0;
 226
 227         for (; b != 0; b = next) {
 228                 next = b->next;
 229                 b->next = 0;
 230                 ret += freeb(b);
 231         }
 232         return ret;
 233 }
 234
 235 void checkb(struct block *b, char *msg)
 236 {
 237         void *dead = (void *)Bdead;
 238         struct extra_bdata *ebd;
 239         size_t extra_len = 0;
 240
 241         if (b == dead)
 242                 panic("checkb b %s 0x%lx", msg, b);
 243         if (b->base == dead || b->lim == dead || b->next == dead
 244                 || b->rp == dead || b->wp == dead) {
 245                 printd("checkb: base 0x%8.8lx lim 0x%8.8lx next 0x%8.8lx\n",
 246                            b->base, b->lim, b->next);
 247                 printd("checkb: rp 0x%8.8lx wp 0x%8.8lx\n", b->rp, b->wp);
 248                 panic("checkb dead: %s\n", msg);
 249         }
 250
 251         if (b->base > b->lim)
 252                 panic("checkb 0 %s 0x%lx 0x%lx", msg, b->base, b->lim);
 253         if (b->rp < b->base)
 254                 panic("checkb 1 %s 0x%lx 0x%lx", msg, b->base, b->rp);
 255         if (b->wp < b->base)
 256                 panic("checkb 2 %s 0x%lx 0x%lx", msg, b->base, b->wp);
 257         if (b->rp > b->lim)
 258                 panic("checkb 3 %s 0x%lx 0x%lx", msg, b->rp, b->lim);
 259         if (b->wp > b->lim)
 260                 panic("checkb 4 %s 0x%lx 0x%lx", msg, b->wp, b->lim);
 261         if (b->nr_extra_bufs && !b->extra_data)
 262                 panic("checkb 5 %s missing extra_data", msg);
 263
 264         for (int i = 0; i < b->nr_extra_bufs; i++) {
 265                 ebd = &b->extra_data[i];
 266                 if (!ebd->base && (ebd->off || ebd->len))
 267                         panic("checkb %s: ebd %d has no base, but has off %d and len %d",
 268                               msg, i, ebd->off, ebd->len);
 269                 if (ebd->base) {
 270                         if (!kmalloc_refcnt((void*)ebd->base))
 271                                 panic("checkb %s: buf %d, base %p has no refcnt!\n", msg, i,
 272                                       ebd->base);
 273                         extra_len += ebd->len;
 274                 }
 275         }
 276         if (extra_len != b->extra_len)
 277                 panic("checkb %s: block extra_len %d differs from sum of ebd len %d",
 278                       msg, b->extra_len, extra_len);
 279 }
 280
 281 void printblock(struct block *b)
 282 {
 283         unsigned char *c;
 284         unsigned int off, elen;
 285         struct extra_bdata *e;
 286
 287         if (b == NULL) {
 288                 printk("block is null\n");
 289                 return;
 290         }
 291
 292         printk("block of BLEN = %d, with %d header and %d data in %d extras\n",
 293                BLEN(b), BHLEN(b), b->extra_len, b->nr_extra_bufs);
 294
 295         printk("header:\n");
 296         printk("%2x:\t", 0);
 297         off = 0;
 298         for (c = b->rp; c < b->wp; c++) {
 299                 printk("  %02x", *c & 0xff);
 300                 off++;
 301                 if (off % 8 == 0) {
 302                         printk("\n");
 303                         printk("%2x:\t", off);
 304                 }
 305         }
 306         printk("\n");
 307         elen = b->extra_len;
 308         for (int i = 0; (i < b->nr_extra_bufs) && elen; i++) {
 309                 e = &b->extra_data[i];
 310                 if (e->len == 0)
 311                         continue;
 312                 elen -= e->len;
 313                 printk("data %d:\n", i);
 314                 printk("%2x:\t", 0);
 315                 for (off = 0; off < e->len; off++) {
 316                         c = (unsigned char *)e->base + e->off + off;
 317                         printk("  %02x", *c & 0xff);
 318                         if ((off + 1) % 8 == 0 && off +1 < e->len) {
 319                                 printk("\n");
 320                                 printk("%2x:\t", off + 1);
 321                         }
 322                 }
 323         }
 324         printk("\n");
 325 }