libseven/balloc.c

   1 /* {{{ irc-seven: Cows like it.
   2  *
   3  * Copyright (C) 1990 Jarkko Oikarinen and University of Oulu, Co Center
   4  * Copyright (C) 1996-2002 Hybrid Development Team
   5  * Copyright (C) 2002-2005 ircd-ratbox development team
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to:
  19  *
  20  *      Free Software Foundation, Inc.
  21  *      51 Franklin St - Fifth Floor
  22  *      Boston, MA 02110-1301
  23  *      USA
  24  *
  25  * }}} */
  26
  27 /* {{{ ircd-seven block allocator (balloc)
  28  *
  29  * The block allocator, funnily enough, allocates blocks of memory of variable
  30  * size from the operating system.  There are two ways we can do this, and they
  31  * are:
  32  *
  33  *      1) by mapping in an anonymous page of memory with mmap(), or
  34  *      2) increasing the size of the data segment thereby allocating memory for
  35  *         use with sbrk() [actually done with malloc() and friends].
  36  *
  37  * The advantage of using mmap()-based allocation is that, unlike the sbrk()
  38  * method, allocated pages can be returned to the operating system (freed),
  39  * whereas memory allocated from the data segment cannot be (because the data
  40  * segment cannot be shrunk).
  41  *
  42  * }}} */
  43
  44 #include "stdinc.h"
  45 #include "libseven.h"
  46
  47 #define WE_ARE_MEMORY_C
  48 #include "setup.h"
  49 #include "balloc.h"
  50 #ifndef NOBALLOC
  51
  52 #include "ircd_defs.h"          /* DEBUG_BLOCK_ALLOCATOR */
  53 #include "ircd.h"
  54 #include "memory.h"
  55 #include "irc_string.h"
  56 #include "tools.h"
  57 #include "s_log.h"
  58 #include "client.h"
  59 #include "event.h"
  60
  61 #ifdef HAVE_MMAP                /* We've got mmap() that is good */
  62 #include <sys/mman.h>
  63 /* HP-UX sucks */
  64 #ifdef MAP_ANONYMOUS
  65 #ifndef MAP_ANON
  66 #define MAP_ANON MAP_ANONYMOUS
  67 #endif
  68 #endif
  69 #endif
  70
  71 static int newblock(BlockHeap * bh);
  72 static int BlockHeapGarbageCollect(BlockHeap *);
  73 static void block_heap_gc(void *unused);
  74 static dlink_list heap_lists;
  75
  76 #if defined(HAVE_MMAP) && !defined(MAP_ANON)
  77 static int zero_fd = -1;
  78 #endif
  79
  80 #define blockheap_fail(x) _blockheap_fail(x, __FILE__, __LINE__)
  81
  82 static void
  83 _blockheap_fail(const char *reason, const char *file, int line)
  84 {
  85         libseven_log("Blockheap failure: %s (%s:%d)", reason, file, line);
  86         abort();
  87 }
  88
  89
  90 /*
  91  * static inline void free_block(void *ptr, size_t size)
  92  *
  93  * Inputs: The block and its size
  94  * Output: None
  95  * Side Effects: Returns memory for the block back to the OS
  96  */
  97 static inline void
  98 free_block(void *ptr, size_t size)
  99 {
 100 #ifdef HAVE_MMAP
 101         munmap(ptr, size);
 102 #else
 103         free(ptr);
 104 #endif
 105 }
 106
 107 #ifdef DEBUG_BALLOC
 108 /* Check the list length the very slow way */
 109 static unsigned long
 110 slow_list_length(dlink_list *list)
 111 {
 112         dlink_node *ptr;
 113         unsigned long count = 0;
 114
 115         for (ptr = list->head; ptr; ptr = ptr->next)
 116         {
 117                 count++;
 118                 if(count > list->length * 2)
 119                 {
 120                         blockheap_fail("count > list->length * 2 - I give up");
 121                 }
 122         }
 123         return count;
 124 }
 125
 126 static void
 127 bh_sanity_check_block(BlockHeap *bh, Block *block)
 128 {
 129         unsigned long s_used, s_free;
 130         s_used = slow_list_length(&block->used_list);
 131         s_free = slow_list_length(&block->free_list);
 132         if(s_used != dlink_list_length(&block->used_list))
 133                 blockheap_fail("used link count doesn't match head count");
 134         if(s_free != dlink_list_length(&block->free_list))
 135                 blockheap_fail("free link count doesn't match head count");
 136
 137         if(dlink_list_length(&block->used_list) + dlink_list_length(&block->free_list) != bh->elemsPerBlock)
 138                 blockheap_fail("used_list + free_list != elemsPerBlock");
 139 }
 140
 141 #if 0
 142 /* See how confused we are */
 143 static void
 144 bh_sanity_check(BlockHeap *bh)
 145 {
 146         Block *walker;
 147         unsigned long real_alloc = 0;
 148         unsigned long s_used, s_free;
 149         unsigned long blockcount = 0;
 150         unsigned long allocated;
 151         if(bh == NULL)
 152                 blockheap_fail("Trying to sanity check a NULL block");
 153
 154         allocated = bh->blocksAllocated * bh->elemsPerBlock;
 155
 156         for(walker = bh->base; walker != NULL; walker = walker->next)
 157         {
 158                 blockcount++;
 159                 s_used = slow_list_length(&walker->used_list);
 160                 s_free = slow_list_length(&walker->free_list);
 161
 162                 if(s_used != dlink_list_length(&walker->used_list))
 163                         blockheap_fail("used link count doesn't match head count");
 164                 if(s_free != dlink_list_length(&walker->free_list))
 165                         blockheap_fail("free link count doesn't match head count");
 166
 167                 if(dlink_list_length(&walker->used_list) + dlink_list_length(&walker->free_list) != bh->elemsPerBlock)
 168                         blockheap_fail("used_list + free_list != elemsPerBlock");
 169
 170                 real_alloc += dlink_list_length(&walker->used_list);
 171                 real_alloc += dlink_list_length(&walker->free_list);
 172         }
 173
 174         if(allocated != real_alloc)
 175                 blockheap_fail("block allocations don't match heap");
 176
 177         if(bh->blocksAllocated != blockcount)
 178                 blockheap_fail("blocksAllocated don't match blockcount");
 179
 180
 181 }
 182
 183 static void
 184 bh_sanity_check_all(void *unused)
 185 {
 186         dlink_node *ptr;
 187         DLINK_FOREACH(ptr, heap_lists.head)
 188         {
 189                 bh_sanity_check(ptr->data);
 190         }
 191 }
 192 #endif
 193
 194 #endif
 195
 196
 197
 198 /*
 199  * void initBlockHeap(void)
 200  *
 201  * Inputs: None
 202  * Outputs: None
 203  * Side Effects: Initializes the block heap
 204  */
 205
 206 void
 207 initBlockHeap(void)
 208 {
 209 #if defined(HAVE_MMAP) && !defined(MAP_ANON)
 210         zero_fd = open("/dev/zero", O_RDWR);
 211
 212         if(zero_fd < 0)
 213                 blockheap_fail("Failed opening /dev/zero");
 214         comm_socket(zero_fd, FD_FILE, "Anonymous mmap()");
 215 #endif
 216         eventAddIsh("block_heap_gc", block_heap_gc, NULL, 30);
 217 }
 218
 219 /*
 220  * static inline void *get_block(size_t size)
 221  *
 222  * Input: Size of block to allocate
 223  * Output: Pointer to new block
 224  * Side Effects: None
 225  */
 226 static inline void *
 227 get_block(size_t size)
 228 {
 229         void *ptr;
 230 #ifdef HAVE_MMAP
 231 #ifdef MAP_ANON
 232         ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
 233 #else
 234         ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, zero_fd, 0);
 235 #endif
 236         if(ptr == MAP_FAILED)
 237         {
 238                 ptr = NULL;
 239         }
 240 #else
 241         ptr = malloc(size);
 242 #endif
 243         return (ptr);
 244 }
 245
 246
 247 static void
 248 block_heap_gc(void *unused)
 249 {
 250         dlink_node *ptr;
 251         DLINK_FOREACH(ptr, heap_lists.head)
 252         {
 253                 BlockHeapGarbageCollect(ptr->data);
 254         }
 255 }
 256
 257 /* ************************************************************************ */
 258 /* FUNCTION DOCUMENTATION:                                                  */
 259 /*    newblock                                                              */
 260 /* Description:                                                             */
 261 /*    Allocates a new block for addition to a blockheap                     */
 262 /* Parameters:                                                              */
 263 /*    bh (IN): Pointer to parent blockheap.                                 */
 264 /* Returns:                                                                 */
 265 /*    0 if successful, 1 if not                                             */
 266 /* ************************************************************************ */
 267
 268 static int
 269 newblock(BlockHeap * bh)
 270 {
 271         MemBlock *newblk;
 272         Block *b;
 273         unsigned long i;
 274         void *offset;
 275
 276         /* Setup the initial data structure. */
 277         b = (Block *) calloc(1, sizeof(Block));
 278         if(b == NULL)
 279         {
 280                 return (1);
 281         }
 282         b->free_list.head = b->free_list.tail = NULL;
 283         b->used_list.head = b->used_list.tail = NULL;
 284         b->next = bh->base;
 285
 286         b->alloc_size = (bh->elemsPerBlock + 1) * (bh->elemSize + sizeof(MemBlock));
 287
 288         b->elems = get_block(b->alloc_size);
 289         if(b->elems == NULL)
 290         {
 291                 return (1);
 292         }
 293         offset = b->elems;
 294         /* Setup our blocks now */
 295         for (i = 0; i < bh->elemsPerBlock; i++)
 296         {
 297                 void *data;
 298                 newblk = (void *) offset;
 299                 newblk->block = b;
 300 #ifdef DEBUG_BALLOC
 301                 newblk->magic = BALLOC_MAGIC;
 302 #endif
 303                 data = (void *) ((size_t) offset + sizeof(MemBlock));
 304                 newblk->block = b;
 305                 dlinkAdd(data, &newblk->self, &b->free_list);
 306                 offset = (unsigned char *) ((unsigned char *) offset +
 307                                             bh->elemSize + sizeof(MemBlock));
 308         }
 309
 310         ++bh->blocksAllocated;
 311         bh->freeElems += bh->elemsPerBlock;
 312         bh->base = b;
 313
 314         return (0);
 315 }
 316
 317
 318 /* ************************************************************************ */
 319 /* FUNCTION DOCUMENTATION:                                                  */
 320 /*    BlockHeapCreate                                                       */
 321 /* Description:                                                             */
 322 /*   Creates a new blockheap from which smaller blocks can be allocated.    */
 323 /*   Intended to be used instead of multiple calls to malloc() when         */
 324 /*   performance is an issue.                                               */
 325 /* Parameters:                                                              */
 326 /*   elemsize (IN):  Size of the basic element to be stored                 */
 327 /*   elemsperblock (IN):  Number of elements to be stored in a single block */
 328 /*         of memory.  When the blockheap runs out of free memory, it will  */
 329 /*         allocate elemsize * elemsperblock more.                          */
 330 /* Returns:                                                                 */
 331 /*   Pointer to new BlockHeap, or NULL if unsuccessful                      */
 332 /* ************************************************************************ */
 333 BlockHeap *
 334 BlockHeapCreate(size_t elemsize, int elemsperblock)
 335 {
 336         BlockHeap *bh;
 337         s_assert(elemsize > 0 && elemsperblock > 0);
 338
 339         /* Catch idiotic requests up front */
 340         if((elemsize <= 0) || (elemsperblock <= 0))
 341         {
 342                 blockheap_fail("Attempting to BlockHeapCreate idiotic sizes");
 343         }
 344
 345         /* Allocate our new BlockHeap */
 346         bh = (BlockHeap *) calloc(1, sizeof(BlockHeap));
 347         if(bh == NULL)
 348         {
 349                 blockheap_fail("Attempt to calloc() failed");
 350                 outofmemory();  /* die.. out of memory */
 351         }
 352
 353         if((elemsize % sizeof(void *)) != 0)
 354         {
 355                 /* Pad to even pointer boundary */
 356                 elemsize += sizeof(void *);
 357                 elemsize &= ~(sizeof(void *) - 1);
 358         }
 359
 360         bh->elemSize = elemsize;
 361         bh->elemsPerBlock = elemsperblock;
 362         bh->blocksAllocated = 0;
 363         bh->freeElems = 0;
 364         bh->base = NULL;
 365
 366         /* Be sure our malloc was successful */
 367         if(newblock(bh))
 368         {
 369                 if(bh != NULL)
 370                         free(bh);
 371                 libseven_restart("Aiee! -- newblock() failed!!!");
 372         }
 373
 374         if(bh == NULL)
 375         {
 376                 blockheap_fail("bh == NULL when it shouldn't be");
 377         }
 378         dlinkAdd(bh, &bh->hlist, &heap_lists);
 379         return (bh);
 380 }
 381
 382 /* ************************************************************************ */
 383 /* FUNCTION DOCUMENTATION:                                                  */
 384 /*    BlockHeapAlloc                                                        */
 385 /* Description:                                                             */
 386 /*    Returns a pointer to a struct within our BlockHeap that's free for    */
 387 /*    the taking.                                                           */
 388 /* Parameters:                                                              */
 389 /*    bh (IN):  Pointer to the Blockheap.                                   */
 390 /* Returns:                                                                 */
 391 /*    Pointer to a structure (void *), or NULL if unsuccessful.             */
 392 /* ************************************************************************ */
 393
 394 void *
 395 BlockHeapAlloc(BlockHeap * bh)
 396 {
 397         Block *walker;
 398         dlink_node *new_node;
 399
 400         s_assert(bh != NULL);
 401         if(bh == NULL)
 402         {
 403                 blockheap_fail("Cannot allocate if bh == NULL");
 404         }
 405
 406         if(bh->freeElems == 0)
 407         {
 408                 /* Allocate new block and assign */
 409                 /* newblock returns 1 if unsuccessful, 0 if not */
 410
 411                 if(newblock(bh))
 412                 {
 413                         /* That didn't work..try to garbage collect */
 414                         BlockHeapGarbageCollect(bh);
 415                         if(bh->freeElems == 0)
 416                         {
 417                                 libseven_restart("newblock() failed and garbage collection didn't help");
 418                         }
 419                 }
 420         }
 421
 422         for (walker = bh->base; walker != NULL; walker = walker->next)
 423         {
 424                 if(dlink_list_length(&walker->free_list) > 0)
 425                 {
 426 #ifdef DEBUG_BALLOC
 427                         bh_sanity_check_block(bh, walker);
 428 #endif
 429                         bh->freeElems--;
 430                         new_node = walker->free_list.head;
 431                         dlinkMoveNode(new_node, &walker->free_list, &walker->used_list);
 432                         s_assert(new_node->data != NULL);
 433                         if(new_node->data == NULL)
 434                                 blockheap_fail("new_node->data is NULL and that shouldn't happen!!!");
 435                         memset(new_node->data, 0, bh->elemSize);
 436 #ifdef DEBUG_BALLOC
 437                         do
 438                         {
 439                                 struct MemBlock *memblock = (void *) ((size_t) new_node->data - sizeof(MemBlock));
 440                                 if(memblock->magic == BALLOC_FREE_MAGIC)
 441                                         memblock->magic = BALLOC_MAGIC;
 442
 443                         } while(0);
 444                         bh_sanity_check_block(bh, walker);
 445 #endif
 446                         return (new_node->data);
 447                 }
 448         }
 449         blockheap_fail("BlockHeapAlloc failed, giving up");
 450         return NULL;
 451 }
 452
 453
 454 /* ************************************************************************ */
 455 /* FUNCTION DOCUMENTATION:                                                  */
 456 /*    BlockHeapFree                                                         */
 457 /* Description:                                                             */
 458 /*    Returns an element to the free pool, does not free()                  */
 459 /* Parameters:                                                              */
 460 /*    bh (IN): Pointer to BlockHeap containing element                      */
 461 /*    ptr (in):  Pointer to element to be "freed"                           */
 462 /* Returns:                                                                 */
 463 /*    0 if successful, 1 if element not contained within BlockHeap.         */
 464 /* ************************************************************************ */
 465 int
 466 BlockHeapFree(BlockHeap * bh, void *ptr)
 467 {
 468         Block *block;
 469         struct MemBlock *memblock;
 470
 471         s_assert(bh != NULL);
 472         s_assert(ptr != NULL);
 473
 474         if(bh == NULL)
 475         {
 476                 libseven_restart("balloc.c:BlockHeapFree() bh == NULL");
 477                 return (1);
 478         }
 479
 480         if(ptr == NULL)
 481         {
 482                 libseven_restart("balloc.BlockHeapFree() ptr == NULL");
 483                 return (1);
 484         }
 485
 486         memblock = (void *) ((size_t) ptr - sizeof(MemBlock));
 487 #ifdef DEBUG_BALLOC
 488         if(memblock->magic == BALLOC_FREE_MAGIC)
 489         {
 490                 blockheap_fail("double free of a block");
 491                 outofmemory();
 492         } else
 493         if(memblock->magic != BALLOC_MAGIC)
 494         {
 495                 blockheap_fail("memblock->magic != BALLOC_MAGIC");
 496                 outofmemory();
 497         }
 498 #endif
 499         s_assert(memblock->block != NULL);
 500         if(memblock->block == NULL)
 501         {
 502                 blockheap_fail("memblock->block == NULL, not a valid block?");
 503                 outofmemory();
 504         }
 505
 506         block = memblock->block;
 507 #ifdef DEBUG_BALLOC
 508         bh_sanity_check_block(bh, block);
 509 #endif
 510         bh->freeElems++;
 511         mem_frob(ptr, bh->elemSize);
 512         dlinkMoveNode(&memblock->self, &block->used_list, &block->free_list);
 513 #ifdef DEBUG_BALLOC
 514         bh_sanity_check_block(bh, block);
 515 #endif
 516         return (0);
 517 }
 518
 519 /* ************************************************************************ */
 520 /* FUNCTION DOCUMENTATION:                                                  */
 521 /*    BlockHeapGarbageCollect                                               */
 522 /* Description:                                                             */
 523 /*    Performs garbage collection on the block heap.  Any blocks that are   */
 524 /*    completely unallocated are removed from the heap.  Garbage collection */
 525 /*    will never remove the root node of the heap.                          */
 526 /* Parameters:                                                              */
 527 /*    bh (IN):  Pointer to the BlockHeap to be cleaned up                   */
 528 /* Returns:                                                                 */
 529 /*   0 if successful, 1 if bh == NULL                                       */
 530 /* ************************************************************************ */
 531 static int
 532 BlockHeapGarbageCollect(BlockHeap * bh)
 533 {
 534         Block *walker, *last;
 535         if(bh == NULL)
 536         {
 537                 return (1);
 538         }
 539
 540         if(bh->freeElems < bh->elemsPerBlock || bh->blocksAllocated == 1)
 541         {
 542                 /* There couldn't possibly be an entire free block.  Return. */
 543                 return (0);
 544         }
 545
 546         last = NULL;
 547         walker = bh->base;
 548
 549         while (walker != NULL)
 550         {
 551                 if((dlink_list_length(&walker->free_list) == bh->elemsPerBlock) != 0)
 552                 {
 553                         free_block(walker->elems, walker->alloc_size);
 554                         if(last != NULL)
 555                         {
 556                                 last->next = walker->next;
 557                                 if(walker != NULL)
 558                                         free(walker);
 559                                 walker = last->next;
 560                         }
 561                         else
 562                         {
 563                                 bh->base = walker->next;
 564                                 if(walker != NULL)
 565                                         free(walker);
 566                                 walker = bh->base;
 567                         }
 568                         bh->blocksAllocated--;
 569                         bh->freeElems -= bh->elemsPerBlock;
 570                 }
 571                 else
 572                 {
 573                         last = walker;
 574                         walker = walker->next;
 575                 }
 576         }
 577         return (0);
 578 }
 579
 580 /* ************************************************************************ */
 581 /* FUNCTION DOCUMENTATION:                                                  */
 582 /*    BlockHeapDestroy                                                      */
 583 /* Description:                                                             */
 584 /*    Completely free()s a BlockHeap.  Use for cleanup.                     */
 585 /* Parameters:                                                              */
 586 /*    bh (IN):  Pointer to the BlockHeap to be destroyed.                   */
 587 /* Returns:                                                                 */
 588 /*   0 if successful, 1 if bh == NULL                                       */
 589 /* ************************************************************************ */
 590 int
 591 BlockHeapDestroy(BlockHeap * bh)
 592 {
 593         Block *walker, *next;
 594
 595         if(bh == NULL)
 596         {
 597                 return (1);
 598         }
 599
 600         for (walker = bh->base; walker != NULL; walker = next)
 601         {
 602                 next = walker->next;
 603                 free_block(walker->elems, walker->alloc_size);
 604                 if(walker != NULL)
 605                         free(walker);
 606         }
 607         dlinkDelete(&bh->hlist, &heap_lists);
 608         free(bh);
 609         return (0);
 610 }
 611
 612 void
 613 BlockHeapUsage(BlockHeap * bh, size_t * bused, size_t * bfree, size_t * bmemusage)
 614 {
 615         size_t used;
 616         size_t freem;
 617         size_t memusage;
 618         if(bh == NULL)
 619         {
 620                 return;
 621         }
 622
 623         freem = bh->freeElems;
 624         used = (bh->blocksAllocated * bh->elemsPerBlock) - bh->freeElems;
 625         memusage = used * (bh->elemSize + sizeof(MemBlock));
 626
 627         if(bused != NULL)
 628                 *bused = used;
 629         if(bfree != NULL)
 630                 *bfree = freem;
 631         if(bmemusage != NULL)
 632                 *bmemusage = memusage;
 633 }
 634
 635 #endif /* NOBALLOC */
 636