Changeset 631
- Timestamp:
- 11/27/05 15:29:26 (6 years ago)
- Location:
- trunk/ithildin
- Files:
-
- 2 edited
-
include/ithildin/malloc.h (modified) (1 diff)
-
source/malloc.c (modified) (28 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/ithildin/include/ithildin/malloc.h
r578 r631 27 27 #endif 28 28 29 extern struct _malloc_statistics { 30 uint64_t malloc_calls; /* Number of calls to malloc/calloc */ 31 uint64_t realloc_calls; /* Number of callcs to realloc */ 32 uint64_t free_calls; /* Number of calls to free() */ 33 34 uint64_t heaps; /* Number of 'performance managed' heaps */ 35 36 uint64_t palloc_calls; /* Number of calls to page allocator */ 37 uint64_t pfree_calls; /* Number of calls to page freer */ 38 39 size_t pagesize; /* Size (in bytes) of allocated blocks */ 40 uint64_t pages_inuse; /* Current count of blocks in-use */ 41 } malloc_statistics; 42 43 /* Use the MALLOC_STATISTICS macro to easily test whether or not allocator 44 * statistics are available for consumption. The thing it is using to 45 * determine this may change over time. */ 46 #define MALLOC_STATISTICS malloc_statistics.pagesize 47 29 48 #endif 30 49 -
trunk/ithildin/source/malloc.c
r589 r631 2 2 * malloc.c: optimised memory allocation routines 3 3 * 4 * Copyright 2003 the Ithildin Project.4 * Copyright 2003-2005 the Ithildin Project. 5 5 * See the COPYING file for more information on licensing and use. 6 6 * … … 9 9 * decisions about how to allocate chunks of memory. it is optimised for the 10 10 * "thousands or more allocations of same-sized memory" case. 11 * 12 * In brief: As allocations of same-sized memory continue, the allocator 13 * begins asking for more hunks of memory at once to fill requests for that 14 * "same size." It caps out at a certain point. Additionally, at periodic 15 * intervals, a check is performed to determine how well things are going 16 * and to "reap" memory that has been pre-allocated and is not (apparently) 17 * in use. A sliding scale is used to determine how aggressively we should 18 * turn back the dial on fresh allocations. 11 19 */ 12 20 13 21 #include <ithildin/stand.h> 22 23 /* Keep the statistics structure here so it is always available, macros in 24 * malloc.h will provide a simple test for its usability. */ 25 26 struct _malloc_statistics malloc_statistics; 27 14 28 #ifdef USE_INTERNAL_MALLOC 15 29 … … 32 46 * than this will always be one page or more because at this size it becomes 33 47 * inefficient to try and wrangle these allocations into being any less 34 * wasteful than that */ 35 #define MALLOC_MAX_SIZE (MALLOC_PAGESIZE / 2) 48 * wasteful than that. That is, at a size larger than this we are unable to 49 * keep more than one allocation and a block structure within a single page, 50 * so there is a lot of waste. */ 51 #define MALLOC_MAX_SIZE ((MALLOC_PAGESIZE - sizeof(struct block)) / 2) 36 52 /* number of blocks to 'cache' in the system. if more blocks than this are 37 53 * free the library will return the pages to the system. */ 38 54 #define MALLOC_CACHE_BLOCKS 1 55 /* number of calls (total) to malloc/calloc/realloc/free before we "retune." 56 * Note that retuning is only done if we are optimizing. */ 57 #define MALLOC_RETUNE_AFTER 65536 58 39 59 /* location of the configuration file we use. */ 40 60 #define MALLOC_CONFIG_FILE "/etc/malloc.conf" … … 46 66 * the options in his allocator map to the options in this allocator. */ 47 67 static struct { 48 bool wfatal; 49 bool fill; 68 bool wfatal; /* warnings become fatal */ 69 bool fill; /* fill memory with 'fbyte' when allocated and 50 70 freed. */ 51 71 char fbyte; 52 bool force_realloc; 72 bool force_realloc; /* force a memory re-allocation even if the 53 73 memory's current area is large enough to 54 74 hold the new data without one */ 55 75 bool sysv_compat; /* 0-byte allocation returns NULL? */ 56 76 bool nomem_fatal; /* abort() if no memory is available. */ 57 int page_cache;/* number of pages to cache at the end of77 unsigned int page_cache; /* number of pages to cache at the end of 58 78 memory before returning memory to the 59 79 system. */ 60 int block_cache;/* number of empty blocks to cache for each80 unsigned int block_cache; /* number of empty blocks to cache for each 61 81 heap. <1 forces immediate return of these 62 82 blocks to the system. */ 63 bool sanity; 83 bool sanity; /* do extra sanity checking to better handle 64 84 corrupted memory */ 65 85 bool optimize; /* optimize with "look-ahead" allocations */ 86 unsigned int retune; /* Number of calls between retuning */ 66 87 } options; 67 88 … … 71 92 72 93 /***************************************************************************** 73 * low-level memory management code 94 * low-level memory management code * 74 95 *****************************************************************************/ 75 96 /* this is the low-level malloc system code. this code is used to track pages … … 87 108 * mmap. we also store the offset of the first free page in the count so that 88 109 * we can find free pages somewhat more quickly. */ 89 #define MALLOC_PAGE_OTHER 110 #define MALLOC_PAGE_OTHER 0 90 111 #define MALLOC_PAGE_FREE 0x01 91 #define MALLOC_PAGE_BALLOC 92 #define MALLOC_PAGE_ALLOC 93 #define MALLOC_PAGE_START 94 #define MALLOC_PAGE_CONTINUED 112 #define MALLOC_PAGE_BALLOC 0x02 113 #define MALLOC_PAGE_ALLOC 0x04 114 #define MALLOC_PAGE_START (MALLOC_PAGE_BALLOC | MALLOC_PAGE_ALLOC) 115 #define MALLOC_PAGE_CONTINUED 0x08 95 116 static struct { 96 117 char *start; /* start of memory */ … … 153 174 memset(s, MALLOC_PAGE_FREE, count); 154 175 176 malloc_statistics.pages_inuse += count; 177 155 178 return true; 156 179 } … … 181 204 while (--count != 0) 182 205 page_desc.parray[idx + count] = MALLOC_PAGE_CONTINUED; 206 207 /* Increment here because we may call ourself recursively */ 208 malloc_statistics.palloc_calls++; 183 209 return page_desc.start + (MALLOC_PAGESIZE * idx); 184 210 } … … 198 224 static void free_pages(void *mem) { 199 225 unsigned int idx, eidx; 226 227 malloc_statistics.pfree_calls++; 200 228 201 229 if ((long)mem % MALLOC_PAGESIZE != 0) { … … 211 239 eidx++; 212 240 memset(page_desc.parray + idx, MALLOC_PAGE_FREE, eidx - idx); 241 malloc_statistics.pages_inuse -= (eidx - idx); 213 242 214 243 /* see if there are pages at the end of the cache that can be given back to … … 232 261 233 262 /***************************************************************************** 234 * actual malloc code 263 * actual malloc code * 235 264 *****************************************************************************/ 236 265 /* the heap structure. these are the top-level memory sources. there is one 237 266 * for each allocation size available. using the defaults from above this 238 267 * yields 47 separate heaps. */ 239 #define MALLOC_HEAP_COUNT \240 (((MALLOC_MAX_SIZE - MALLOC_MIN_SIZE) / MALLOC_FUZZ) + 1)241 268 struct heap { 242 269 size_t size; /* size allocated to the heap */ 243 int etotal;/* total element count */244 int ealloc;/* allocated element count */245 246 int blocks;/* 'blocks' of memory allocated */247 int bpages;/* number of pages we're using for blocks, will270 uint64_t etotal; /* total element count */ 271 uint64_t ealloc; /* allocated element count */ 272 273 uint32_t blocks; /* 'blocks' of memory allocated */ 274 uint32_t bpages; /* number of pages we're using for blocks, will 248 275 increase until bpages > MALLOC_MAX_PAGES or 249 276 the number of elements in a block would be > 250 277 MALLOC_MAX_ELEMS */ 251 int bempty;/* blocks which are empty */252 int bfull;/* blockx which are full */253 254 int allocs;/* 'alloc' calls */255 int frees;/* 'free' calls */278 uint32_t bempty; /* blocks which are empty */ 279 uint32_t bfull; /* blockx which are full */ 280 281 uint64_t allocs; /* 'alloc' calls */ 282 uint64_t frees; /* 'free' calls */ 256 283 257 284 LIST_HEAD(, block) blist; /* list of allocated blocks */ 258 285 LIST_HEAD(, block) oblist; /* list of blocks with some free memory */ 259 } heaps[MALLOC_HEAP_COUNT];286 }; 260 287 261 288 /* a block is a region of contiguous memory. the size of a block may vary from … … 286 313 }; 287 314 315 /* 316 * We keep a static grouping of the heaps structures here. We declare this 317 * last in order to understand the sizes of things (note the use of 318 * MALLOC_MAX_SIZE). 319 */ 320 #define MALLOC_HEAP_COUNT \ 321 (((MALLOC_MAX_SIZE - MALLOC_MIN_SIZE) / MALLOC_FUZZ) + 1) 322 struct heap heaps[MALLOC_HEAP_COUNT]; 323 288 324 /***************************************************************************** 289 * initialization code 325 * initialization code * 290 326 *****************************************************************************/ 291 327 const char *_malloc_options = NULL; … … 296 332 while (*buf != '\0') { 297 333 switch (*buf) { 298 case '>': options.page_cache <<= 1; break;299 case '<': options.page_cache >>= 1; break;300 case 'a': options.wfatal = false; break;301 case 'A': options.wfatal = true; break;302 case 'b': options.block_cache--; break;303 case 'B': options.block_cache++; break;304 case 'j': options.fill = false; 334 case '>': options.page_cache <<= 1; break; 335 case '<': options.page_cache >>= 1; break; 336 case 'a': options.wfatal = false; break; 337 case 'A': options.wfatal = true; break; 338 case 'b': options.block_cache--; break; 339 case 'B': options.block_cache++; break; 340 case 'j': options.fill = false; break; 305 341 case 'J': options.fill = true; options.fbyte = 0xd0; break; 306 case 'l': options.optimize = false; break; 307 case 'L': options.optimize = true; break; 308 case 'r': options.force_realloc = false; break; 309 case 'R': options.force_realloc = true; break; 310 case 's': options.sanity = false; break; 311 case 'S': options.sanity = true; break; 312 case 'v': options.sysv_compat = false; break; 313 case 'V': options.sysv_compat = true; break; 314 case 'z': options.fill = false; break; 315 case 'Z': options.fill = true; options.fbyte = 0x0; break; 342 case 'l': options.optimize = false; break; 343 case 'L': options.optimize = true; break; 344 case 'r': options.force_realloc = false; break; 345 case 'R': options.force_realloc = true; break; 346 case 's': options.sanity = false; break; 347 case 'S': options.sanity = true; break; 348 case 't': options.retune /= 2; break; 349 case 'T': options.retune *= 2; break; 350 case 'v': options.sysv_compat = false; break; 351 case 'V': options.sysv_compat = true; break; 352 case 'z': options.fill = false; break; 353 case 'Z': options.fill = true; options.fbyte = 0x0; break; 316 354 } 317 355 buf++; … … 362 400 static bool malloc_initialized = false; 363 401 static void malloc_init(void) { 364 int i;402 unsigned int i; 365 403 size_t sz; 366 404 #define BUFSIZE 64 … … 370 408 options.page_cache = MALLOC_PAGE_CACHE; 371 409 options.block_cache = MALLOC_CACHE_BLOCKS; 410 options.retune = MALLOC_RETUNE_AFTER; 372 411 options.optimize = true; 373 412 … … 396 435 heaps[i].bpages = 1; 397 436 } 437 438 malloc_statistics.heaps = MALLOC_HEAP_COUNT; 439 malloc_statistics.pagesize = MALLOC_PAGESIZE; 440 398 441 malloc_initialized = true; 399 442 } … … 432 475 static struct block *create_block(struct heap *hp) { 433 476 struct block *bp; 434 struct block_elem *ep ;477 struct block_elem *ep, *ep2; 435 478 int elems; 436 479 char *mem; … … 451 494 452 495 SLIST_INIT(&bp->elist); 496 /* Create the list in the order of memory. We hope to use retuning code 497 * later to see if we can reclaim chunks of a block that are not in use. */ 498 ep2 = NULL; 453 499 while (mem < bp->end) { 454 500 ep = (struct block_elem *)mem; 455 501 ep->magic = MALLOC_MAGIC; 456 SLIST_INSERT_HEAD(&bp->elist, ep, lp); 502 if (ep2 == NULL) 503 SLIST_INSERT_HEAD(&bp->elist, ep, lp); 504 else 505 SLIST_INSERT_AFTER(ep2, ep, lp); 506 507 ep2 = ep; 457 508 458 509 mem += hp->size; … … 521 572 bp->heap->bfull++; 522 573 } 574 bp->heap->ealloc++; 523 575 ep->magic = 0; /* wipe the magic number */ 524 576 return ep; … … 540 592 memset(mem, options.fbyte, bp->heap->size); 541 593 594 bp->heap->ealloc--; 542 595 ep->magic = MALLOC_MAGIC; 543 596 SLIST_INSERT_HEAD(&bp->elist, ep, lp); … … 592 645 } 593 646 647 /* Retuning function. Walk the heap list, looking for heaps that are in 648 * need of "down-tuning" and do so. */ 649 #define HEAP_PCT_FREE_REDUCE 0.10 650 static void retune_blocks(void) { 651 unsigned int i; 652 struct block *bp, *bp2; 653 654 for (i = 0;i < MALLOC_HEAP_COUNT;i++) { 655 /* Pretty simple, if the heap is HEAP_PCT_FREE_REDUCE % full or 656 * less, we reduce its future allocations unless they are already at 657 * the lowest possible (1). We also go ahead and free up any 658 * completely empty blocks in the heap. XXX: We should also try and 659 * reduce the size of mostly underused blocks when possible. */ 660 if ((float)(heaps[i].etotal - heaps[i].ealloc) >= 661 (float)heaps[i].etotal * HEAP_PCT_FREE_REDUCE) { 662 if (heaps[i].bpages > 1) 663 heaps[i].bpages /= 2; /* Reduce! */ 664 if (heaps[i].bempty) { 665 /* Walk the list and return any empty blocks */ 666 bp = LIST_FIRST(&heaps[i].oblist); 667 668 while (bp != NULL) { 669 bp2 = LIST_NEXT(bp, lp); 670 671 if (bp->used == 0) 672 destroy_block(bp); 673 } 674 } 675 } 676 } 677 } 678 594 679 /* these are the four allocator functions. in general they pass off work to 595 680 * subsystem functions declared below. */ 681 682 static unsigned int call_counter; 683 #define CHECK_RETUNE(x) do { \ 684 (x)++; \ 685 if ((x) > options.retune) { \ 686 (x) = 0; \ 687 retune_blocks(); \ 688 } \ 689 } while (0) 690 691 596 692 void *calloc(size_t count, size_t size) { 597 693 void *mem; … … 606 702 size_t size; 607 703 704 malloc_statistics.free_calls++; 705 608 706 if (recursing) { 609 707 malloc_warn("free(%p): recursing in allocator", mem); … … 625 723 626 724 if (bp == NULL) { 627 if (options.fill)628 memset(mem, options.fbyte, size);725 if (options.fill) 726 memset(mem, options.fbyte, size); 629 727 free_pages(mem); 630 } else 728 } else { 631 729 free_block(bp, mem); 730 CHECK_RETUNE(call_counter); 731 } 632 732 633 733 recursing--; … … 637 737 struct block *bp; 638 738 void *mem; 739 740 malloc_statistics.malloc_calls++; 639 741 640 742 if (recursing) { … … 689 791 690 792 recursing--; 793 CHECK_RETUNE(call_counter); 691 794 return mem; /* huzzah! */ 692 795 } … … 700 803 void *newmem; 701 804 805 malloc_statistics.realloc_calls++; 806 702 807 if (recursing) { 703 808 malloc_warn("realloc(%p, %d): recursing in allocator", mem, newsize); … … 718 823 if (newsize == 0) 719 824 return NULL; 825 malloc_statistics.malloc_calls--; /* this will be an artificially 826 generated call */ 720 827 return malloc(newsize); 721 828 } … … 730 837 /* unset recursing so we can manually call malloc.. */ 731 838 recursing--; 732 if (!options.force_realloc && size >= newsize) 839 if (!options.force_realloc && size >= newsize) { 840 CHECK_RETUNE(call_counter); 733 841 return mem; /* no need to move any memory ... */ 734 842 } 843 844 malloc_statistics.malloc_calls--; /* this will be an artificially 845 generated call */ 735 846 if ((newmem = malloc(newsize)) == NULL) 736 847 return NULL; /* oops.. */
Note: See TracChangeset
for help on using the changeset viewer.
