lib/resource.c

   1 /*
   2  *      BIRD Resource Manager
   3  *
   4  *      (c) 1998--2000 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <stdint.h>
  12
  13 #include "nest/bird.h"
  14 #include "lib/resource.h"
  15 #include "lib/string.h"
  16
  17 /**
  18  * DOC: Resource pools
  19  *
  20  * Resource pools (&pool) are just containers holding a list of
  21  * other resources. Freeing a pool causes all the listed resources
  22  * to be freed as well. Each existing &resource is linked to some pool
  23  * except for a root pool which isn't linked anywhere, so all the
  24  * resources form a tree structure with internal nodes corresponding
  25  * to pools and leaves being the other resources.
  26  *
  27  * Example: Almost all modules of BIRD have their private pool which
  28  * is freed upon shutdown of the module.
  29  */
  30
  31 struct pool {
  32   resource r;
  33   list inside;
  34   char *name;
  35 };
  36
  37 static void pool_dump(resource *);
  38 static void pool_free(resource *);
  39 static resource *pool_lookup(resource *, unsigned long);
  40 static size_t pool_memsize(resource *P);
  41
  42 static struct resclass pool_class = {
  43   "Pool",
  44   sizeof(pool),
  45   pool_free,
  46   pool_dump,
  47   pool_lookup,
  48   pool_memsize
  49 };
  50
  51 pool root_pool;
  52
  53 static int indent;
  54
  55 /**
  56  * rp_new - create a resource pool
  57  * @p: parent pool
  58  * @name: pool name (to be included in debugging dumps)
  59  *
  60  * rp_new() creates a new resource pool inside the specified
  61  * parent pool.
  62  */
  63 pool *
  64 rp_new(pool *p, char *name)
  65 {
  66   pool *z = ralloc(p, &pool_class);
  67   z->name = name;
  68   init_list(&z->inside);
  69   return z;
  70 }
  71
  72 static void
  73 pool_free(resource *P)
  74 {
  75   pool *p = (pool *) P;
  76   resource *r, *rr;
  77
  78   r = HEAD(p->inside);
  79   while (rr = (resource *) r->n.next)
  80     {
  81       r->class->free(r);
  82       xfree(r);
  83       r = rr;
  84     }
  85 }
  86
  87 static void
  88 pool_dump(resource *P)
  89 {
  90   pool *p = (pool *) P;
  91   resource *r;
  92
  93   debug("%s\n", p->name);
  94   indent += 3;
  95   WALK_LIST(r, p->inside)
  96     rdump(r);
  97   indent -= 3;
  98 }
  99
 100 static size_t
 101 pool_memsize(resource *P)
 102 {
 103   pool *p = (pool *) P;
 104   resource *r;
 105   size_t sum = sizeof(pool) + ALLOC_OVERHEAD;
 106
 107   WALK_LIST(r, p->inside)
 108     sum += rmemsize(r);
 109
 110   return sum;
 111 }
 112
 113 static resource *
 114 pool_lookup(resource *P, unsigned long a)
 115 {
 116   pool *p = (pool *) P;
 117   resource *r, *q;
 118
 119   WALK_LIST(r, p->inside)
 120     if (r->class->lookup && (q = r->class->lookup(r, a)))
 121       return q;
 122   return NULL;
 123 }
 124
 125 /**
 126  * rmove - move a resource
 127  * @res: resource
 128  * @p: pool to move the resource to
 129  *
 130  * rmove() moves a resource from one pool to another.
 131  */
 132
 133 void rmove(void *res, pool *p)
 134 {
 135   resource *r = res;
 136
 137   if (r)
 138     {
 139       if (r->n.next)
 140         rem_node(&r->n);
 141       add_tail(&p->inside, &r->n);
 142     }
 143 }
 144
 145 /**
 146  * rfree - free a resource
 147  * @res: resource
 148  *
 149  * rfree() frees the given resource and all information associated
 150  * with it. In case it's a resource pool, it also frees all the objects
 151  * living inside the pool.
 152  *
 153  * It works by calling a class-specific freeing function.
 154  */
 155 void
 156 rfree(void *res)
 157 {
 158   resource *r = res;
 159
 160   if (!r)
 161     return;
 162
 163   if (r->n.next)
 164     rem_node(&r->n);
 165   r->class->free(r);
 166   xfree(r);
 167 }
 168
 169 /**
 170  * rdump - dump a resource
 171  * @res: resource
 172  *
 173  * This function prints out all available information about the given
 174  * resource to the debugging output.
 175  *
 176  * It works by calling a class-specific dump function.
 177  */
 178 void
 179 rdump(void *res)
 180 {
 181   char x[16];
 182   resource *r = res;
 183
 184   bsprintf(x, "%%%ds%%p ", indent);
 185   debug(x, "", r);
 186   if (r)
 187     {
 188       debug("%s ", r->class->name);
 189       r->class->dump(r);
 190     }
 191   else
 192     debug("NULL\n");
 193 }
 194
 195 size_t
 196 rmemsize(void *res)
 197 {
 198   resource *r = res;
 199   if (!r)
 200     return 0;
 201   if (!r->class->memsize)
 202     return r->class->size + ALLOC_OVERHEAD;
 203   return r->class->memsize(r);
 204 }
 205
 206 /**
 207  * ralloc - create a resource
 208  * @p: pool to create the resource in
 209  * @c: class of the new resource
 210  *
 211  * This function is called by the resource classes to create a new
 212  * resource of the specified class and link it to the given pool.
 213  * Allocated memory is zeroed. Size of the resource structure is taken
 214  * from the @size field of the &resclass.
 215  */
 216 void *
 217 ralloc(pool *p, struct resclass *c)
 218 {
 219   resource *r = xmalloc(c->size);
 220   bzero(r, c->size);
 221
 222   r->class = c;
 223   if (p)
 224     add_tail(&p->inside, &r->n);
 225   return r;
 226 }
 227
 228 /**
 229  * rlookup - look up a memory location
 230  * @a: memory address
 231  *
 232  * This function examines all existing resources to see whether
 233  * the address @a is inside any resource. It's used for debugging
 234  * purposes only.
 235  *
 236  * It works by calling a class-specific lookup function for each
 237  * resource.
 238  */
 239 void
 240 rlookup(unsigned long a)
 241 {
 242   resource *r;
 243
 244   debug("Looking up %08lx\n", a);
 245   if (r = pool_lookup(&root_pool.r, a))
 246     rdump(r);
 247   else
 248     debug("Not found.\n");
 249 }
 250
 251 /**
 252  * resource_init - initialize the resource manager
 253  *
 254  * This function is called during BIRD startup. It initializes
 255  * all data structures of the resource manager and creates the
 256  * root pool.
 257  */
 258 void
 259 resource_init(void)
 260 {
 261   root_pool.r.class = &pool_class;
 262   root_pool.name = "Root";
 263   init_list(&root_pool.inside);
 264 }
 265
 266 /**
 267  * DOC: Memory blocks
 268  *
 269  * Memory blocks are pieces of contiguous allocated memory.
 270  * They are a bit non-standard since they are represented not by a pointer
 271  * to &resource, but by a void pointer to the start of data of the
 272  * memory block. All memory block functions know how to locate the header
 273  * given the data pointer.
 274  *
 275  * Example: All "unique" data structures such as hash tables are allocated
 276  * as memory blocks.
 277  */
 278
 279 struct mblock {
 280   resource r;
 281   unsigned size;
 282   uintptr_t data_align[0];
 283   byte data[0];
 284 };
 285
 286 static void mbl_free(resource *r UNUSED)
 287 {
 288 }
 289
 290 static void mbl_debug(resource *r)
 291 {
 292   struct mblock *m = (struct mblock *) r;
 293
 294   debug("(size=%d)\n", m->size);
 295 }
 296
 297 static resource *
 298 mbl_lookup(resource *r, unsigned long a)
 299 {
 300   struct mblock *m = (struct mblock *) r;
 301
 302   if ((unsigned long) m->data <= a && (unsigned long) m->data + m->size > a)
 303     return r;
 304   return NULL;
 305 }
 306
 307 static size_t
 308 mbl_memsize(resource *r)
 309 {
 310   struct mblock *m = (struct mblock *) r;
 311   return ALLOC_OVERHEAD + sizeof(struct mblock) + m->size;
 312 }
 313
 314 static struct resclass mb_class = {
 315   "Memory",
 316   0,
 317   mbl_free,
 318   mbl_debug,
 319   mbl_lookup,
 320   mbl_memsize
 321 };
 322
 323 /**
 324  * mb_alloc - allocate a memory block
 325  * @p: pool
 326  * @size: size of the block
 327  *
 328  * mb_alloc() allocates memory of a given size and creates
 329  * a memory block resource representing this memory chunk
 330  * in the pool @p.
 331  *
 332  * Please note that mb_alloc() returns a pointer to the memory
 333  * chunk, not to the resource, hence you have to free it using
 334  * mb_free(), not rfree().
 335  */
 336 void *
 337 mb_alloc(pool *p, unsigned size)
 338 {
 339   struct mblock *b = xmalloc(sizeof(struct mblock) + size);
 340
 341   b->r.class = &mb_class;
 342   add_tail(&p->inside, &b->r.n);
 343   b->size = size;
 344   return b->data;
 345 }
 346
 347 /**
 348  * mb_allocz - allocate and clear a memory block
 349  * @p: pool
 350  * @size: size of the block
 351  *
 352  * mb_allocz() allocates memory of a given size, initializes it to
 353  * zeroes and creates a memory block resource representing this memory
 354  * chunk in the pool @p.
 355  *
 356  * Please note that mb_allocz() returns a pointer to the memory
 357  * chunk, not to the resource, hence you have to free it using
 358  * mb_free(), not rfree().
 359  */
 360 void *
 361 mb_allocz(pool *p, unsigned size)
 362 {
 363   void *x = mb_alloc(p, size);
 364   bzero(x, size);
 365   return x;
 366 }
 367
 368 /**
 369  * mb_realloc - reallocate a memory block
 370  * @m: memory block
 371  * @size: new size of the block
 372  *
 373  * mb_realloc() changes the size of the memory block @m to a given size.
 374  * The contents will be unchanged to the minimum of the old and new sizes;
 375  * newly allocated memory will be uninitialized. Contrary to realloc()
 376  * behavior, @m must be non-NULL, because the resource pool is inherited
 377  * from it.
 378  *
 379  * Like mb_alloc(), mb_realloc() also returns a pointer to the memory
 380  * chunk, not to the resource, hence you have to free it using
 381  * mb_free(), not rfree().
 382  */
 383 void *
 384 mb_realloc(void *m, unsigned size)
 385 {
 386   struct mblock *ob = NULL;
 387
 388   if (m)
 389     {
 390       ob = SKIP_BACK(struct mblock, data, m);
 391       if (ob->r.n.next)
 392         rem_node(&ob->r.n);
 393     }
 394
 395   struct mblock *b = xrealloc(ob, sizeof(struct mblock) + size);
 396   replace_node(&b->r.n, &b->r.n);
 397   b->size = size;
 398   return b->data;
 399 }
 400
 401
 402 /**
 403  * mb_free - free a memory block
 404  * @m: memory block
 405  *
 406  * mb_free() frees all memory associated with the block @m.
 407  */
 408 void
 409 mb_free(void *m)
 410 {
 411   if (!m)
 412     return;
 413
 414   struct mblock *b = SKIP_BACK(struct mblock, data, m);
 415   rfree(b);
 416 }
 417
 418
 419
 420 #define STEP_UP(x) ((x) + (x)/2 + 4)
 421
 422 void
 423 buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size)
 424 {
 425   unsigned nsize = MIN(*size, need);
 426
 427   while (nsize < need)
 428     nsize = STEP_UP(nsize);
 429
 430   *buf = mb_realloc(*buf, nsize * item_size);
 431   *size = nsize;
 432 }