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   const 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, const 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   r->class = NULL;
 167   xfree(r);
 168 }
 169
 170 /**
 171  * rdump - dump a resource
 172  * @res: resource
 173  *
 174  * This function prints out all available information about the given
 175  * resource to the debugging output.
 176  *
 177  * It works by calling a class-specific dump function.
 178  */
 179 void
 180 rdump(void *res)
 181 {
 182   char x[16];
 183   resource *r = res;
 184
 185   bsprintf(x, "%%%ds%%p ", indent);
 186   debug(x, "", r);
 187   if (r)
 188     {
 189       debug("%s ", r->class->name);
 190       r->class->dump(r);
 191     }
 192   else
 193     debug("NULL\n");
 194 }
 195
 196 size_t
 197 rmemsize(void *res)
 198 {
 199   resource *r = res;
 200   if (!r)
 201     return 0;
 202   if (!r->class->memsize)
 203     return r->class->size + ALLOC_OVERHEAD;
 204   return r->class->memsize(r);
 205 }
 206
 207 /**
 208  * ralloc - create a resource
 209  * @p: pool to create the resource in
 210  * @c: class of the new resource
 211  *
 212  * This function is called by the resource classes to create a new
 213  * resource of the specified class and link it to the given pool.
 214  * Allocated memory is zeroed. Size of the resource structure is taken
 215  * from the @size field of the &resclass.
 216  */
 217 void *
 218 ralloc(pool *p, struct resclass *c)
 219 {
 220   resource *r = xmalloc(c->size);
 221   bzero(r, c->size);
 222
 223   r->class = c;
 224   if (p)
 225     add_tail(&p->inside, &r->n);
 226   return r;
 227 }
 228
 229 /**
 230  * rlookup - look up a memory location
 231  * @a: memory address
 232  *
 233  * This function examines all existing resources to see whether
 234  * the address @a is inside any resource. It's used for debugging
 235  * purposes only.
 236  *
 237  * It works by calling a class-specific lookup function for each
 238  * resource.
 239  */
 240 void
 241 rlookup(unsigned long a)
 242 {
 243   resource *r;
 244
 245   debug("Looking up %08lx\n", a);
 246   if (r = pool_lookup(&root_pool.r, a))
 247     rdump(r);
 248   else
 249     debug("Not found.\n");
 250 }
 251
 252 /**
 253  * resource_init - initialize the resource manager
 254  *
 255  * This function is called during BIRD startup. It initializes
 256  * all data structures of the resource manager and creates the
 257  * root pool.
 258  */
 259 void
 260 resource_init(void)
 261 {
 262   root_pool.r.class = &pool_class;
 263   root_pool.name = "Root";
 264   init_list(&root_pool.inside);
 265 }
 266
 267 /**
 268  * DOC: Memory blocks
 269  *
 270  * Memory blocks are pieces of contiguous allocated memory.
 271  * They are a bit non-standard since they are represented not by a pointer
 272  * to &resource, but by a void pointer to the start of data of the
 273  * memory block. All memory block functions know how to locate the header
 274  * given the data pointer.
 275  *
 276  * Example: All "unique" data structures such as hash tables are allocated
 277  * as memory blocks.
 278  */
 279
 280 struct mblock {
 281   resource r;
 282   unsigned size;
 283   uintptr_t data_align[0];
 284   byte data[0];
 285 };
 286
 287 static void mbl_free(resource *r UNUSED)
 288 {
 289 }
 290
 291 static void mbl_debug(resource *r)
 292 {
 293   struct mblock *m = (struct mblock *) r;
 294
 295   debug("(size=%d)\n", m->size);
 296 }
 297
 298 static resource *
 299 mbl_lookup(resource *r, unsigned long a)
 300 {
 301   struct mblock *m = (struct mblock *) r;
 302
 303   if ((unsigned long) m->data <= a && (unsigned long) m->data + m->size > a)
 304     return r;
 305   return NULL;
 306 }
 307
 308 static size_t
 309 mbl_memsize(resource *r)
 310 {
 311   struct mblock *m = (struct mblock *) r;
 312   return ALLOC_OVERHEAD + sizeof(struct mblock) + m->size;
 313 }
 314
 315 static struct resclass mb_class = {
 316   "Memory",
 317   0,
 318   mbl_free,
 319   mbl_debug,
 320   mbl_lookup,
 321   mbl_memsize
 322 };
 323
 324 /**
 325  * mb_alloc - allocate a memory block
 326  * @p: pool
 327  * @size: size of the block
 328  *
 329  * mb_alloc() allocates memory of a given size and creates
 330  * a memory block resource representing this memory chunk
 331  * in the pool @p.
 332  *
 333  * Please note that mb_alloc() returns a pointer to the memory
 334  * chunk, not to the resource, hence you have to free it using
 335  * mb_free(), not rfree().
 336  */
 337 void *
 338 mb_alloc(pool *p, unsigned size)
 339 {
 340   struct mblock *b = xmalloc(sizeof(struct mblock) + size);
 341
 342   b->r.class = &mb_class;
 343   b->r.n = (node) {};
 344   add_tail(&p->inside, &b->r.n);
 345   b->size = size;
 346   return b->data;
 347 }
 348
 349 /**
 350  * mb_allocz - allocate and clear a memory block
 351  * @p: pool
 352  * @size: size of the block
 353  *
 354  * mb_allocz() allocates memory of a given size, initializes it to
 355  * zeroes and creates a memory block resource representing this memory
 356  * chunk in the pool @p.
 357  *
 358  * Please note that mb_allocz() returns a pointer to the memory
 359  * chunk, not to the resource, hence you have to free it using
 360  * mb_free(), not rfree().
 361  */
 362 void *
 363 mb_allocz(pool *p, unsigned size)
 364 {
 365   void *x = mb_alloc(p, size);
 366   bzero(x, size);
 367   return x;
 368 }
 369
 370 /**
 371  * mb_realloc - reallocate a memory block
 372  * @m: memory block
 373  * @size: new size of the block
 374  *
 375  * mb_realloc() changes the size of the memory block @m to a given size.
 376  * The contents will be unchanged to the minimum of the old and new sizes;
 377  * newly allocated memory will be uninitialized. Contrary to realloc()
 378  * behavior, @m must be non-NULL, because the resource pool is inherited
 379  * from it.
 380  *
 381  * Like mb_alloc(), mb_realloc() also returns a pointer to the memory
 382  * chunk, not to the resource, hence you have to free it using
 383  * mb_free(), not rfree().
 384  */
 385 void *
 386 mb_realloc(void *m, unsigned size)
 387 {
 388   struct mblock *b = SKIP_BACK(struct mblock, data, m);
 389
 390   b = xrealloc(b, sizeof(struct mblock) + size);
 391   update_node(&b->r.n);
 392   b->size = size;
 393   return b->data;
 394 }
 395
 396
 397 /**
 398  * mb_free - free a memory block
 399  * @m: memory block
 400  *
 401  * mb_free() frees all memory associated with the block @m.
 402  */
 403 void
 404 mb_free(void *m)
 405 {
 406   if (!m)
 407     return;
 408
 409   struct mblock *b = SKIP_BACK(struct mblock, data, m);
 410   rfree(b);
 411 }
 412
 413
 414
 415 #define STEP_UP(x) ((x) + (x)/2 + 4)
 416
 417 void
 418 buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size)
 419 {
 420   unsigned nsize = MIN(*size, need);
 421
 422   while (nsize < need)
 423     nsize = STEP_UP(nsize);
 424
 425   *buf = mb_realloc(*buf, nsize * item_size);
 426   *size = nsize;
 427 }