src/core/balloc.c

   1 /*  praxis: services for TSora IRC networks.
   2  *  src/balloc.c: Block memory allocator.
   3  *
   4  *  Copyright (c) 2004 Eric Will <rakaur@malkier.net>
   5  *  Copyright (c) 2003-2004 shrike development team.
   6  *  Copyright (c) 2002-2004 ircd-ratbox development team.
   7  *
   8  *  $Id$
   9  */
  10
  11 #include "praxis.h"
  12 #include "dlink.h"
  13 #include "ilog.h"
  14 #include "imem.h"
  15 #include "timer.h"
  16 #include "balloc.h"
  17
  18 /* HP-UX apparently defines MAP_ANONYMOUS instead of MAP_ANON. */
  19 #ifdef HAVE_MMAP
  20 #ifdef MAP_ANONYMOUS
  21 #ifndef MAP_ANON
  22 #define MAP_ANON MAP_ANONYMOUS
  23 #endif
  24 #endif
  25 #endif
  26
  27 /* If we have mmap() but we don't have MAP_ANON we'll have to improvise. */
  28 #ifdef HAVE_MMAP
  29 #ifndef MAP_ANON
  30 static int zero_fd = -1;
  31 #endif
  32 #endif
  33
  34 static void ballocGarbage(void *);
  35
  36 static DLinkList heap_lists;
  37
  38 /* _ballocFail()
  39  *     Logs an error message and exits.
  40  *
  41  * inputs     - message, file, line
  42  * outputs    - none
  43  */
  44 static void
  45 _ballocFail(const char *reason, const char *file, int line)
  46 {
  47     ilog(L_INFO, "%s:%d: Block allocator failure: %s", file, line, reason);
  48     abort();
  49 }
  50
  51 #define ballocFail(x) _ballocFail(x, __FILE__, __LINE__)
  52
  53 /* ballocInit()
  54  *     Initialises the block allocator.
  55  *
  56  * inputs     - none
  57  * outputs    - none
  58  */
  59 void
  60 ballocInit(void)
  61 {
  62 #ifdef HAVE_MMAP
  63 #ifndef MAP_ANON
  64     zero_fd = open("/dev/zero", O_RDWR);
  65
  66     if (zero_fd < 0)
  67         ballocFail("couldn't open /dev/zero");
  68 #endif
  69 #endif
  70
  71     /* Garbage collection every five minutes. */
  72     timerAdd("ballocGarbage", ballocGarbage, NULL, 300);
  73 }
  74
  75 /* balloc()
  76  *     Allocates a new block of memory.
  77  *
  78  * inputs     - size to allocate
  79  * outputs    - pointer to new memory or NULL on failure.
  80  */
  81 void *
  82 balloc(size_t size)
  83 {
  84     void *memory;
  85
  86 #ifdef HAVE_MMAP
  87 #ifdef MAP_ANON
  88     memory = mmap(NULL, size, (PROT_READ | PROT_WRITE),
  89                   (MAP_PRIVATE | MAP_ANON), -1, 0);
  90 #else
  91     memory = mmap(NULL, size, (PROT_READ | PROT_WRITE), MAP_PRIVATE,
  92                   zero_fd, 0);
  93 #endif
  94     if (memory == MAP_FAILED)
  95         memory = NULL;
  96 #else
  97     memory = malloc(size);
  98 #endif
  99     return memory;
 100 }
 101
 102 /* ballocFree()
 103  *     free()'s our memory.
 104  *
 105  * inputs     - pointer to memory, size to free
 106  * outputs    - none
 107  */
 108 void
 109 ballocFree(void *memory, size_t size)
 110 {
 111 #ifdef HAVE_MMAP
 112     munmap(memory, size);
 113 #else
 114     free(memory);
 115 #endif
 116 }
 117
 118 /* ballocBlockCreate()
 119  *     Allocates a new Block for addition to a Heap.
 120  *
 121  * inputs     - Heap to add to
 122  * outputs    - 1 on success, 0 on failure
 123  */
 124 uchar
 125 ballocBlockCreate(Heap *heap_p)
 126 {
 127     MemBlock *memblock_p;
 128     Block *block_p;
 129     ulong i;
 130     void *offset;
 131
 132     iassert(heap_p != NULL);
 133
 134     /* Set up initial data structure. */
 135     block_p = calloc(1, sizeof(Block));
 136
 137     if (block_p == NULL)
 138         return 0;
 139
 140     block_p->next = heap_p->block_p;
 141     block_p->alloc_size = ((heap_p->elems_per_block + 1) *
 142                            (heap_p->elem_size + sizeof(MemBlock)));
 143
 144     block_p->elems = balloc(block_p->alloc_size);
 145
 146     if (block_p->elems == NULL)
 147         return 0;
 148
 149     offset = block_p->elems;
 150
 151     /* Set up our MemBlocks now. */
 152     for (i = 0; i < heap_p->elems_per_block; i++)
 153     {
 154         void *data;
 155
 156         memblock_p = offset;
 157         memblock_p->block_p = block_p;
 158 #ifdef DEBUG_BALLOC
 159         memblock_p->magic = BALLOC_MAGIC;
 160 #endif
 161         data = (void *)((size_t) offset + sizeof(MemBlock));
 162
 163         dlinkAdd(data, &memblock_p->self, &block_p->free_list);
 164
 165         offset = (uchar *)((uchar *)offset + heap_p->elem_size +
 166                            sizeof(MemBlock));
 167     }
 168
 169     heap_p->blocks_allocated++;
 170     heap_p->elems_free += heap_p->elems_per_block;
 171     heap_p->block_p = block_p;
 172
 173     return 1;
 174 }
 175
 176 /* ballocHeapCreate()
 177  *     Creates a new Heap for Blocks.
 178  *
 179  * inputs     - element size, elements per Block
 180  * outputs    - pointer to Heap or NULL on failure
 181  */
 182 Heap *
 183 ballocHeapCreate(size_t elem_size, uint elems_per_block)
 184 {
 185     Heap *heap_p;
 186
 187     iassert(elem_size > 0);
 188     iassert(elems_per_block > 0);
 189
 190     /* Set up our initial data structure. */
 191     heap_p = calloc(1, sizeof(Heap));
 192
 193     if (heap_p == NULL)
 194         return NULL;
 195
 196     /* Some systems want pointers that are multiples of void *. */
 197     if ((elem_size % sizeof(void *)) != 0)
 198     {
 199         elem_size += sizeof(void *);
 200         elem_size &= ~(sizeof(void *) - 1);
 201     }
 202
 203     heap_p->elem_size = elem_size;
 204     heap_p->elems_per_block = elems_per_block;
 205
 206     /* Now get some Blocks for it. */
 207     if (ballocBlockCreate(heap_p) == 0)
 208     {
 209         if (heap_p != NULL)
 210             free(heap_p);
 211
 212         ballocFail("ballocBlockCreate() failed.");
 213     }
 214
 215     if (heap_p == NULL)
 216         ballocFail("heap_p == NULL");
 217
 218     dlinkAdd(heap_p, &heap_p->hlist, &heap_lists);
 219
 220     return heap_p;
 221 }
 222
 223 /* ballocHeapDestroy()
 224  *     Completely frees a Heap.
 225  *
 226  * inputs     - Heap to destroy
 227  * outputs    - 1 on success or 0 on failure
 228  */
 229 uchar
 230 ballocHeapDestroy(Heap *heap_p)
 231 {
 232     Block *walker, *next;
 233
 234     iassert(heap_p != NULL);
 235
 236     for (walker = heap_p->block_p; walker != NULL; walker = next)
 237     {
 238         next = walker->next;
 239
 240         ballocFree(walker->elems, walker->alloc_size);
 241
 242         if (walker != NULL)
 243             free(walker);
 244     }
 245
 246     dlinkDelete(&heap_p->hlist, &heap_lists);
 247
 248     free(heap_p);
 249
 250     return 1;
 251 }
 252
 253 /* ballocHeapAlloc()
 254  *     Finds a structure that's free for the taking.
 255  *
 256  * inputs     - Heap to use for memory
 257  * outputs    - pointer to a structure or NULL on failure
 258  */
 259 void *
 260 ballocHeapAlloc(Heap *heap_p)
 261 {
 262     Block *walker;
 263     DLinkNode *node_p;
 264
 265     iassert(heap_p != NULL);
 266
 267     /* Check to see if we have any free elements. */
 268     if (heap_p->elems_free == 0)
 269     {
 270         /* We're out of free elements.  Let's allocate a new Block. */
 271         if (ballocBlockCreate(heap_p) == 0)
 272         {
 273             /* We couldn't get a new Block.  Let's try garbage collection. */
 274             ballocHeapGarbage(heap_p);
 275
 276             if (heap_p->elems_free == 0)
 277             {
 278                 /* That didn't work either, so we're out of memory. */
 279                 ballocFail("couldn't allocate a new Block");
 280             }
 281         }
 282     }
 283
 284     /* Find a free element. */
 285     for (walker = heap_p->block_p; walker != NULL; walker = walker->next)
 286     {
 287         if (dlinkLength(&walker->free_list) > 0)
 288         {
 289             /* We have a free element. */
 290             heap_p->elems_free--;
 291
 292             node_p = walker->free_list.head;
 293             dlinkNodeMove(node_p, &walker->free_list, &walker->used_list);
 294
 295             iassert(node_p->data != NULL);
 296
 297             memset(node_p->data, 0, heap_p->elem_size);
 298
 299             return node_p->data;
 300         }
 301     }
 302
 303     /* If we get here then we couldn't get a free element. */
 304     ballocFail("couldn't get a free element");
 305
 306     return NULL;
 307 }
 308
 309 /* ballocHeapFree()
 310  *     Returns an element to the free pool.
 311  *
 312  * inputs     - Heap containing element, element
 313  * outputs    - 1 on success, 0 on failure
 314  */
 315 uchar
 316 ballocHeapFree(Heap *heap_p, void *element)
 317 {
 318     Block *block_p;
 319     MemBlock *memblock_p;
 320
 321     iassert(heap_p != NULL);
 322     iassert(element != NULL);
 323
 324     memblock_p = (void *)((size_t) element - sizeof(MemBlock));
 325
 326 #ifdef DEBUG_BALLOC
 327     if (memblock_p->magic != BALLOC_MAGIC)
 328         ballocFail("magics do not match");
 329 #endif
 330
 331     iassert(memblock_p->block_p != NULL);
 332
 333     block_p = memblock_p->block_p;
 334     heap_p->elems_free++;
 335
 336     dlinkNodeMove(&memblock_p->self, &block_p->used_list, &block_p->free_list);
 337
 338     return 1;
 339 }
 340
 341 /* ballocGarbage()
 342  *     Performs garbage collection on all Heaps.
 343  *
 344  * inputs     - Timer argument
 345  * outputs    - none
 346  */
 347 static void
 348 ballocGarbage(void *arg)
 349 {
 350     DLinkNode *node_p;
 351
 352     DLINK_FOREACH(node_p, heap_lists.head) ballocHeapGarbage(node_p->data);
 353 }
 354
 355 /* ballocHeapGarbage()
 356  *     Performs garbage collection on specified Heap.
 357  *
 358  * inputs     - Heap to clean
 359  * outputs    - none
 360  */
 361 void
 362 ballocHeapGarbage(Heap *heap_p)
 363 {
 364     Block *walker, *last;
 365
 366     iassert(heap_p != NULL);
 367
 368     /* Check for entirely free Blocks. */
 369     if ((heap_p->elems_free < heap_p->elems_per_block) ||
 370         (heap_p->blocks_allocated == 1))
 371         return;
 372
 373     last = NULL;
 374     walker = heap_p->block_p;
 375
 376     while (walker != NULL)
 377     {
 378         if (dlinkLength(&walker->free_list) == heap_p->elems_per_block)
 379         {
 380             ballocFree(walker->elems, walker->alloc_size);
 381
 382             if (last != NULL)
 383             {
 384                 last->next = walker->next;
 385
 386                 if (walker != NULL)
 387                     free(walker);
 388
 389                 walker = last->next;
 390             }
 391             else
 392             {
 393                 heap_p->block_p = walker->next;
 394
 395                 if (walker != NULL)
 396                     free(walker);
 397
 398                 walker = heap_p->block_p;
 399             }
 400
 401             heap_p->blocks_allocated--;
 402             heap_p->elems_free -= heap_p->elems_per_block;
 403         }
 404         else
 405         {
 406             last = walker;
 407             walker = walker->next;
 408         }
 409     }
 410 }