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