libratbox/src/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-2006 ircd-ratbox development team
   8  *
   9  *  Below are the orignal headers from the old blalloc.c
  10  *
  11  *  File:   blalloc.c
  12  *  Owner:  Wohali (Joan Touzet)
  13  *
  14  *  Modified 2001/11/29 for mmap() support by Aaron Sethman <androsyn@ratbox.org>
  15  *
  16  *  This program is free software; you can redistribute it and/or modify
  17  *  it under the terms of the GNU General Public License as published by
  18  *  the Free Software Foundation; either version 2 of the License, or
  19  *  (at your option) any later version.
  20  *
  21  *  This program is distributed in the hope that it will be useful,
  22  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24  *  GNU General Public License for more details.
  25  *
  26  *  You should have received a copy of the GNU General Public License
  27  *  along with this program; if not, write to the Free Software
  28  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
  29  *  USA
  30  *
  31  */
  32
  33 /*
  34  * About the block allocator
  35  *
  36  * Basically we have three ways of getting memory off of the operating
  37  * system. Below are this list of methods and the order of preference.
  38  *
  39  * 1. mmap() anonymous pages with the MMAP_ANON flag.
  40  * 2. mmap() via the /dev/zero trick.
  41  * 3. HeapCreate/HeapAlloc (on win32)
  42  * 4. malloc()
  43  *
  44  * The advantages of 1 and 2 are this.  We can munmap() the pages which will
  45  * return the pages back to the operating system, thus reducing the size
  46  * of the process as the memory is unused.  malloc() on many systems just keeps
  47  * a heap of memory to itself, which never gets given back to the OS, except on
  48  * exit.  This of course is bad, if say we have an event that causes us to allocate
  49  * say, 200MB of memory, while our normal memory consumption would be 15MB.  In the
  50  * malloc() case, the amount of memory allocated to our process never goes down, as
  51  * malloc() has it locked up in its heap.  With the mmap() method, we can munmap()
  52  * the block and return it back to the OS, thus causing our memory consumption to go
  53  * down after we no longer need it.
  54  *
  55  *
  56  *
  57  */
  58 #include <libratbox_config.h>
  59 #include <ratbox_lib.h>
  60
  61 #ifndef NOBALLOC
  62 #ifdef HAVE_MMAP                /* We've got mmap() that is good */
  63 #include <sys/mman.h>
  64 /* HP-UX sucks */
  65 #ifdef MAP_ANONYMOUS
  66 #ifndef MAP_ANON
  67 #define MAP_ANON MAP_ANONYMOUS
  68 #endif
  69 #endif
  70 #endif
  71 #endif
  72
  73 static uintptr_t offset_pad;
  74
  75 /* status information for an allocated block in heap */
  76 struct rb_heap_block
  77 {
  78         size_t alloc_size;
  79         rb_dlink_node node;
  80         unsigned long free_count;
  81         void *elems;            /* Points to allocated memory */
  82 };
  83 typedef struct rb_heap_block rb_heap_block;
  84
  85 /* information for the root node of the heap */
  86 struct rb_bh
  87 {
  88         rb_dlink_node hlist;
  89         size_t elemSize;        /* Size of each element to be stored */
  90         unsigned long elemsPerBlock;    /* Number of elements per block */
  91         rb_dlink_list block_list;
  92         rb_dlink_list free_list;
  93         char *desc;
  94 };
  95
  96 #ifndef NOBALLOC
  97 static int newblock(rb_bh *bh);
  98 static void rb_bh_gc_event(void *unused);
  99 #endif /* !NOBALLOC */
 100 static rb_dlink_list *heap_lists;
 101
 102 #if defined(WIN32)
 103 static HANDLE block_heap;
 104 #endif
 105
 106 #define rb_bh_fail(x) _rb_bh_fail(x, __FILE__, __LINE__)
 107
 108 static void
 109 _rb_bh_fail(const char *reason, const char *file, int line)
 110 {
 111         rb_lib_log("rb_heap_blockheap failure: %s (%s:%d)", reason, file, line);
 112         abort();
 113 }
 114
 115 #ifndef NOBALLOC
 116 /*
 117  * static inline void free_block(void *ptr, size_t size)
 118  *
 119  * Inputs: The block and its size
 120  * Output: None
 121  * Side Effects: Returns memory for the block back to the OS
 122  */
 123 static inline void
 124 free_block(void *ptr, size_t size)
 125 {
 126 #ifdef HAVE_MMAP
 127         munmap(ptr, size);
 128 #else
 129 #ifdef _WIN32
 130         HeapFree(block_heap, 0, ptr);
 131 #else
 132         free(ptr);
 133 #endif
 134 #endif
 135 }
 136 #endif /* !NOBALLOC */
 137
 138 /*
 139  * void rb_init_bh(void)
 140  *
 141  * Inputs: None
 142  * Outputs: None
 143  * Side Effects: Initializes the block heap
 144  */
 145
 146 void
 147 rb_init_bh(void)
 148 {
 149         heap_lists = rb_malloc(sizeof(rb_dlink_list));
 150         offset_pad = sizeof(void *);
 151         /* XXX if you get SIGBUS when trying to use a long long..here is where you need to
 152          * fix your shit
 153          */
 154 #ifdef __sparc__
 155         if((offset_pad % __alignof__(long long)) != 0)
 156         {
 157                 offset_pad += __alignof__(long long);
 158                 offset_pad &= ~(__alignof__(long long) - 1);
 159         }
 160 #endif
 161
 162 #ifndef NOBALLOC
 163 #ifdef _WIN32
 164         block_heap = HeapCreate(HEAP_NO_SERIALIZE, 0, 0);
 165 #endif
 166         rb_event_addish("rb_bh_gc_event", rb_bh_gc_event, NULL, 300);
 167 #endif /* !NOBALLOC */
 168 }
 169
 170 #ifndef NOBALLOC
 171 /*
 172  * static inline void *get_block(size_t size)
 173  *
 174  * Input: Size of block to allocate
 175  * Output: Pointer to new block
 176  * Side Effects: None
 177  */
 178 static inline void *
 179 get_block(size_t size)
 180 {
 181         void *ptr;
 182 #ifdef HAVE_MMAP
 183 #ifdef MAP_ANON
 184         ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
 185 #else
 186         int zero_fd;
 187         zero_fd = open("/dev/zero", O_RDWR);
 188         if(zero_fd < 0)
 189                 rb_bh_fail("Failed opening /dev/zero");
 190         ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE, zero_fd, 0);
 191         close(zero_fd);
 192 #endif /* MAP_ANON */
 193         if(ptr == MAP_FAILED)
 194                 ptr = NULL;
 195 #else
 196 #ifdef _WIN32
 197         ptr = HeapAlloc(block_heap, 0, size);
 198 #else
 199         ptr = malloc(size);
 200 #endif
 201 #endif
 202         return (ptr);
 203 }
 204
 205
 206 static void
 207 rb_bh_gc_event(void *unused)
 208 {
 209         rb_dlink_node *ptr;
 210         RB_DLINK_FOREACH(ptr, heap_lists->head)
 211         {
 212                 rb_bh_gc(ptr->data);
 213         }
 214 }
 215
 216 /* ************************************************************************ */
 217 /* FUNCTION DOCUMENTATION:                                                  */
 218 /*    newblock                                                              */
 219 /* Description:                                                             */
 220 /*    Allocates a new block for addition to a blockheap                     */
 221 /* Parameters:                                                              */
 222 /*    bh (IN): Pointer to parent blockheap.                                 */
 223 /* Returns:                                                                 */
 224 /*    0 if successful, 1 if not                                             */
 225 /* ************************************************************************ */
 226
 227 static int
 228 newblock(rb_bh *bh)
 229 {
 230         rb_heap_block *b;
 231         unsigned long i;
 232         uintptr_t offset;
 233         rb_dlink_node *node;
 234         /* Setup the initial data structure. */
 235         b = rb_malloc(sizeof(rb_heap_block));
 236
 237         b->alloc_size = bh->elemsPerBlock * bh->elemSize;
 238
 239         b->elems = get_block(b->alloc_size);
 240         if(rb_unlikely(b->elems == NULL))
 241         {
 242                 return (1);
 243         }
 244         offset = (uintptr_t)b->elems;
 245         /* Setup our blocks now */
 246         for(i = 0; i < bh->elemsPerBlock; i++, offset += bh->elemSize)
 247         {
 248                 *((void **)offset) = b;
 249                 node = (void *)(offset + offset_pad);
 250                 rb_dlinkAdd((void *)offset, node, &bh->free_list);
 251         }
 252         rb_dlinkAdd(b, &b->node, &bh->block_list);
 253         b->free_count = bh->elemsPerBlock;
 254         return (0);
 255 }
 256 #endif /* !NOBALLOC */
 257
 258 /* ************************************************************************ */
 259 /* FUNCTION DOCUMENTATION:                                                  */
 260 /*    rb_bh_create                                                       */
 261 /* Description:                                                             */
 262 /*   Creates a new blockheap from which smaller blocks can be allocated.    */
 263 /*   Intended to be used instead of multiple calls to malloc() when         */
 264 /*   performance is an issue.                                               */
 265 /* Parameters:                                                              */
 266 /*   elemsize (IN):  Size of the basic element to be stored                 */
 267 /*   elemsperblock (IN):  Number of elements to be stored in a single block */
 268 /*         of memory.  When the blockheap runs out of free memory, it will  */
 269 /*         allocate elemsize * elemsperblock more.                          */
 270 /* Returns:                                                                 */
 271 /*   Pointer to new rb_bh, or NULL if unsuccessful                      */
 272 /* ************************************************************************ */
 273 rb_bh *
 274 rb_bh_create(size_t elemsize, int elemsperblock, const char *desc)
 275 {
 276         rb_bh *bh;
 277         lrb_assert(elemsize > 0 && elemsperblock > 0);
 278         lrb_assert(elemsize >= sizeof(rb_dlink_node));
 279
 280         /* Catch idiotic requests up front */
 281         if((elemsize == 0) || (elemsperblock <= 0))
 282         {
 283                 rb_bh_fail("Attempting to rb_bh_create idiotic sizes");
 284         }
 285
 286         if(elemsize < sizeof(rb_dlink_node))
 287                 rb_bh_fail("Attempt to rb_bh_create smaller than sizeof(rb_dlink_node)");
 288
 289         /* Allocate our new rb_bh */
 290         bh = rb_malloc(sizeof(rb_bh));
 291 #ifndef NOBALLOC
 292         elemsize += offset_pad;
 293         if((elemsize % sizeof(void *)) != 0)
 294         {
 295                 /* Pad to even pointer boundary */
 296                 elemsize += sizeof(void *);
 297                 elemsize &= ~(sizeof(void *) - 1);
 298         }
 299 #endif
 300
 301         bh->elemSize = elemsize;
 302         bh->elemsPerBlock = elemsperblock;
 303         if(desc != NULL)
 304                 bh->desc = rb_strdup(desc);
 305
 306 #ifndef NOBALLOC
 307         /* Be sure our malloc was successful */
 308         if(newblock(bh))
 309         {
 310                 if(bh != NULL)
 311                         free(bh);
 312                 rb_lib_log("newblock() failed");
 313                 rb_outofmemory();       /* die.. out of memory */
 314         }
 315 #endif /* !NOBALLOC */
 316
 317         if(bh == NULL)
 318         {
 319                 rb_bh_fail("bh == NULL when it shouldn't be");
 320         }
 321         rb_dlinkAdd(bh, &bh->hlist, heap_lists);
 322         return (bh);
 323 }
 324
 325 /* ************************************************************************ */
 326 /* FUNCTION DOCUMENTATION:                                                  */
 327 /*    rb_bh_alloc                                                        */
 328 /* Description:                                                             */
 329 /*    Returns a pointer to a struct within our rb_bh that's free for    */
 330 /*    the taking.                                                           */
 331 /* Parameters:                                                              */
 332 /*    bh (IN):  Pointer to the Blockheap.                                   */
 333 /* Returns:                                                                 */
 334 /*    Pointer to a structure (void *), or NULL if unsuccessful.             */
 335 /* ************************************************************************ */
 336
 337 void *
 338 rb_bh_alloc(rb_bh *bh)
 339 {
 340 #ifndef NOBALLOC
 341         rb_dlink_node *new_node;
 342         rb_heap_block **block;
 343         void *ptr;
 344 #endif
 345         lrb_assert(bh != NULL);
 346         if(rb_unlikely(bh == NULL))
 347         {
 348                 rb_bh_fail("Cannot allocate if bh == NULL");
 349         }
 350
 351 #ifdef NOBALLOC
 352         return (rb_malloc(bh->elemSize));
 353 #else
 354         if(bh->free_list.head == NULL)
 355         {
 356                 /* Allocate new block and assign */
 357                 /* newblock returns 1 if unsuccessful, 0 if not */
 358
 359                 if(rb_unlikely(newblock(bh)))
 360                 {
 361                         rb_lib_log("newblock() failed");
 362                         rb_outofmemory();       /* Well that didn't work either...bail */
 363                 }
 364                 if(bh->free_list.head == NULL)
 365                 {
 366                         rb_lib_log("out of memory after newblock()...");
 367                         rb_outofmemory();
 368                 }
 369         }
 370
 371         new_node = bh->free_list.head;
 372         block = (rb_heap_block **) new_node->data;
 373         ptr = (void *)((uintptr_t)new_node->data + (uintptr_t)offset_pad);
 374         rb_dlinkDelete(new_node, &bh->free_list);
 375         (*block)->free_count--;
 376         memset(ptr, 0, bh->elemSize - offset_pad);
 377         return (ptr);
 378 #endif
 379 }
 380
 381
 382 /* ************************************************************************ */
 383 /* FUNCTION DOCUMENTATION:                                                  */
 384 /*    rb_bh_free                                                          */
 385 /* Description:                                                             */
 386 /*    Returns an element to the free pool, does not free()                  */
 387 /* Parameters:                                                              */
 388 /*    bh (IN): Pointer to rb_bh containing element                        */
 389 /*    ptr (in):  Pointer to element to be "freed"                           */
 390 /* Returns:                                                                 */
 391 /*    0 if successful, 1 if element not contained within rb_bh.           */
 392 /* ************************************************************************ */
 393 int
 394 rb_bh_free(rb_bh *bh, void *ptr)
 395 {
 396 #ifndef NOBALLOC
 397         rb_heap_block *block;
 398         void *data;
 399 #endif
 400         lrb_assert(bh != NULL);
 401         lrb_assert(ptr != NULL);
 402
 403         if(rb_unlikely(bh == NULL))
 404         {
 405                 rb_lib_log("balloc.c:rb_bhFree() bh == NULL");
 406                 return (1);
 407         }
 408
 409         if(rb_unlikely(ptr == NULL))
 410         {
 411                 rb_lib_log("balloc.rb_bhFree() ptr == NULL");
 412                 return (1);
 413         }
 414
 415 #ifdef NOBALLOC
 416         rb_free(ptr);
 417 #else
 418         data = (void *)((uintptr_t)ptr - (uintptr_t)offset_pad);
 419         block = *(rb_heap_block **) data;
 420         /* XXX */
 421         if(rb_unlikely
 422            (!((uintptr_t)ptr >= (uintptr_t)block->elems
 423               && (uintptr_t)ptr < (uintptr_t)block->elems + (uintptr_t)block->alloc_size)))
 424         {
 425                 rb_bh_fail("rb_bh_free() bogus pointer");
 426         }
 427         block->free_count++;
 428
 429         rb_dlinkAdd(data, (rb_dlink_node *)ptr, &bh->free_list);
 430 #endif /* !NOBALLOC */
 431         return (0);
 432 }
 433
 434
 435 /* ************************************************************************ */
 436 /* FUNCTION DOCUMENTATION:                                                  */
 437 /*    rb_bhDestroy                                                      */
 438 /* Description:                                                             */
 439 /*    Completely free()s a rb_bh.  Use for cleanup.                     */
 440 /* Parameters:                                                              */
 441 /*    bh (IN):  Pointer to the rb_bh to be destroyed.                   */
 442 /* Returns:                                                                 */
 443 /*   0 if successful, 1 if bh == NULL                                       */
 444 /* ************************************************************************ */
 445 int
 446 rb_bh_destroy(rb_bh *bh)
 447 {
 448 #ifndef NOBALLOC
 449         rb_dlink_node *ptr, *next;
 450         rb_heap_block *b;
 451 #endif
 452         if(bh == NULL)
 453                 return (1);
 454
 455 #ifndef NOBALLOC
 456         RB_DLINK_FOREACH_SAFE(ptr, next, bh->block_list.head)
 457         {
 458                 b = ptr->data;
 459                 free_block(b->elems, b->alloc_size);
 460                 rb_free(b);
 461         }
 462 #endif /* !NOBALLOC */
 463
 464         rb_dlinkDelete(&bh->hlist, heap_lists);
 465         rb_free(bh->desc);
 466         rb_free(bh);
 467
 468         return (0);
 469 }
 470
 471 void
 472 rb_bh_usage(rb_bh *bh, size_t *bused, size_t *bfree, size_t *bmemusage, const char **desc)
 473 {
 474 #ifndef NOBALLOC
 475         size_t used, freem, memusage;
 476
 477         if(bh == NULL)
 478         {
 479                 return;
 480         }
 481
 482         freem = rb_dlink_list_length(&bh->free_list);
 483         used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
 484         memusage = used * bh->elemSize;
 485         if(bused != NULL)
 486                 *bused = used;
 487         if(bfree != NULL)
 488                 *bfree = freem;
 489         if(bmemusage != NULL)
 490                 *bmemusage = memusage;
 491         if(desc != NULL)
 492                 *desc = bh->desc;
 493 #else
 494         if(bused != NULL)
 495                 *bused = 0;
 496         if(bfree != NULL)
 497                 *bfree = 0;
 498         if(bmemusage != NULL)
 499                 *bmemusage = 0;
 500         if(desc != NULL)
 501                 *desc = "no blockheap";
 502 #endif
 503 }
 504
 505 void
 506 rb_bh_usage_all(rb_bh_usage_cb *cb, void *data)
 507 {
 508         rb_dlink_node *ptr;
 509         rb_bh *bh;
 510         size_t used, freem, memusage, heapalloc;
 511         static const char *unnamed = "(unnamed_heap)";
 512         const char *desc = unnamed;
 513
 514         if(cb == NULL)
 515                 return;
 516
 517         RB_DLINK_FOREACH(ptr, heap_lists->head)
 518         {
 519                 bh = (rb_bh *)ptr->data;
 520                 freem = rb_dlink_list_length(&bh->free_list);
 521                 used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
 522                 memusage = used * bh->elemSize;
 523                 heapalloc = (freem + used) * bh->elemSize;
 524                 if(bh->desc != NULL)
 525                         desc = bh->desc;
 526                 cb(used, freem, memusage, heapalloc, desc, data);
 527         }
 528         return;
 529 }
 530
 531 void
 532 rb_bh_total_usage(size_t *total_alloc, size_t *total_used)
 533 {
 534         rb_dlink_node *ptr;
 535         size_t total_memory = 0, used_memory = 0, used, freem;
 536         rb_bh *bh;
 537
 538         RB_DLINK_FOREACH(ptr, heap_lists->head)
 539         {
 540                 bh = (rb_bh *)ptr->data;
 541                 freem = rb_dlink_list_length(&bh->free_list);
 542                 used = (rb_dlink_list_length(&bh->block_list) * bh->elemsPerBlock) - freem;
 543                 used_memory += used * bh->elemSize;
 544                 total_memory += (freem + used) * bh->elemSize;
 545         }
 546
 547         if(total_alloc != NULL)
 548                 *total_alloc = total_memory;
 549         if(total_used != NULL)
 550                 *total_used = used_memory;
 551 }
 552
 553 #ifndef NOBALLOC
 554 int
 555 rb_bh_gc(rb_bh *bh)
 556 {
 557         rb_heap_block *b;
 558         rb_dlink_node *ptr, *next;
 559         unsigned long i;
 560         uintptr_t offset;
 561
 562         if(bh == NULL)
 563         {
 564                 /* somebody is smoking some craq..(probably lee, but don't tell him that) */
 565                 return (1);
 566         }
 567
 568         if((rb_dlink_list_length(&bh->free_list) < bh->elemsPerBlock)
 569            || rb_dlink_list_length(&bh->block_list) == 1)
 570         {
 571                 /* There couldn't possibly be an entire free block.  Return. */
 572                 return (0);
 573         }
 574
 575         RB_DLINK_FOREACH_SAFE(ptr, next, bh->block_list.head)
 576         {
 577                 b = ptr->data;
 578                 if(rb_dlink_list_length(&bh->block_list) == 1)
 579                         return (0);
 580
 581                 if(b->free_count == bh->elemsPerBlock)
 582                 {
 583                         /* i'm seriously going to hell for this.. */
 584
 585                         offset = (uintptr_t)b->elems;
 586                         for(i = 0; i < bh->elemsPerBlock; i++, offset += (uintptr_t)bh->elemSize)
 587                         {
 588                                 rb_dlinkDelete((rb_dlink_node *)(offset + offset_pad),
 589                                                &bh->free_list);
 590                         }
 591                         rb_dlinkDelete(&b->node, &bh->block_list);
 592                         free_block(b->elems, b->alloc_size);
 593                         rb_free(b);
 594                 }
 595
 596         }
 597         return (0);
 598 }
 599 #endif /* !NOBALLOC */