libseven/balloc.c

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