2 * Copyright (c) 2000-2001, 2004 Sendmail, Inc. and its suppliers.
5 * By using this file, you agree to the terms and conditions set
6 * forth in the LICENSE file which can be found at the top level of
7 * the sendmail distribution.
11 SM_RCSID("@(#)$Id: heap.c,v 1.51 2004/08/03 20:32:00 ca Exp $")
14 ** debugging memory allocation package
15 ** See heap.html for documentation.
20 #include <sm/assert.h>
25 #include <sm/signal.h>
28 /* undef all macro versions of the "functions" so they can be specified here */
31 #undef sm_malloc_tagged
32 #undef sm_malloc_tagged_x
37 # undef sm_heap_register
38 # undef sm_heap_checkptr
39 # undef sm_heap_report
40 #endif /* SM_HEAP_CHECK */
43 SM_DEBUG_T SmHeapCheck = SM_DEBUG_INITIALIZER("sm_check_heap",
44 "@(#)$Debug: sm_check_heap - check sm_malloc, sm_realloc, sm_free calls $");
45 # define HEAP_CHECK sm_debug_active(&SmHeapCheck, 1)
46 static int ptrhash __P((void *p));
47 #endif /* SM_HEAP_CHECK */
49 const SM_EXC_TYPE_T SmHeapOutOfMemoryType =
58 SM_EXC_T SmHeapOutOfMemory = SM_EXC_INITIALIZER(&SmHeapOutOfMemoryType, NULL);
62 ** The behaviour of malloc with size==0 is platform dependent (it
63 ** says so in the C standard): it can return NULL or non-NULL. We
64 ** don't want sm_malloc_x(0) to raise an exception on some platforms
65 ** but not others, so this case requires special handling. We've got
66 ** two choices: "size = 1" or "return NULL". We use the former in the
68 ** If we had something like autoconf we could figure out the
69 ** behaviour of the platform and either use this hack or just
73 #define MALLOC_SIZE(size) ((size) == 0 ? 1 : (size))
76 ** SM_MALLOC_X -- wrapper around malloc(), raises an exception on error.
79 ** size -- size of requested memory.
82 ** Pointer to memory region.
85 ** sm_malloc_x only gets called from source files in which heap
86 ** debugging is disabled at compile time. Otherwise, a call to
87 ** sm_malloc_x is macro expanded to a call to sm_malloc_tagged_x.
90 ** F:sm_heap -- out of memory
100 ptr = malloc(MALLOC_SIZE(size));
103 sm_exc_raise_x(&SmHeapOutOfMemory);
110 ** SM_MALLOC -- wrapper around malloc()
113 ** size -- size of requested memory.
116 ** Pointer to memory region.
126 ptr = malloc(MALLOC_SIZE(size));
132 ** SM_REALLOC -- wrapper for realloc()
135 ** ptr -- pointer to old memory area.
136 ** size -- size of requested memory.
139 ** Pointer to new memory area, NULL on failure.
143 sm_realloc(ptr, size)
150 newptr = realloc(ptr, MALLOC_SIZE(size));
156 ** SM_REALLOC_X -- wrapper for realloc()
159 ** ptr -- pointer to old memory area.
160 ** size -- size of requested memory.
163 ** Pointer to new memory area.
166 ** F:sm_heap -- out of memory
170 sm_realloc_x(ptr, size)
177 newptr = realloc(ptr, MALLOC_SIZE(size));
180 sm_exc_raise_x(&SmHeapOutOfMemory);
184 ** SM_FREE -- wrapper around free()
187 ** ptr -- pointer to memory region.
205 #else /* !SM_HEAP_CHECK */
208 ** Each allocated block is assigned a "group number".
209 ** By default, all blocks are assigned to group #1.
210 ** By convention, group #0 is for memory that is never freed.
211 ** You can use group numbers any way you want, in order to help make
212 ** sense of sm_heap_report output.
216 int SmHeapMaxGroup = 1;
219 ** Total number of bytes allocated.
220 ** This is only maintained if the sm_check_heap debug category is active.
223 size_t SmHeapTotal = 0;
226 ** High water mark: the most that SmHeapTotal has ever been.
229 size_t SmHeapMaxTotal = 0;
232 ** Maximum number of bytes that may be allocated at any one time.
234 ** This is only honoured if sm_check_heap is active.
237 SM_DEBUG_T SmHeapLimit = SM_DEBUG_INITIALIZER("sm_heap_limit",
238 "@(#)$Debug: sm_heap_limit - max # of bytes permitted in heap $");
241 ** This is the data structure that keeps track of all currently
242 ** allocated blocks of memory known to the heap package.
245 typedef struct sm_heap_item SM_HEAP_ITEM_T;
253 SM_HEAP_ITEM_T *hi_next;
256 #define SM_HEAP_TABLE_SIZE 256
257 static SM_HEAP_ITEM_T *SmHeapTable[SM_HEAP_TABLE_SIZE];
260 ** This is a randomly generated table
261 ** which contains exactly one occurrence
262 ** of each of the numbers between 0 and 255.
263 ** It is used by ptrhash.
266 static unsigned char hashtab[SM_HEAP_TABLE_SIZE] =
268 161, 71, 77,187, 15,229, 9,176,221,119,239, 21, 85,138,203, 86,
269 102, 65, 80,199,235, 32,140, 96,224, 78,126,127,144, 0, 11,179,
270 64, 30,120, 23,225,226, 33, 50,205,167,130,240,174, 99,206, 73,
271 231,210,189,162, 48, 93,246, 54,213,141,135, 39, 41,192,236,193,
272 157, 88, 95,104,188, 63,133,177,234,110,158,214,238,131,233, 91,
273 125, 82, 94, 79, 66, 92,151, 45,252, 98, 26,183, 7,191,171,106,
274 145,154,251,100,113, 5, 74, 62, 76,124, 14,217,200, 75,115,190,
275 103, 28,198,196,169,219, 37,118,150, 18,152,175, 49,136, 6,142,
276 89, 19,243,254, 47,137, 24,166,180, 10, 40,186,202, 46,184, 67,
277 148,108,181, 81, 25,241, 13,139, 58, 38, 84,253,201, 12,116, 17,
278 195, 22,112, 69,255, 43,147,222,111, 56,194,216,149,244, 42,173,
279 232,220,249,105,207, 51,197,242, 72,211,208, 59,122,230,237,170,
280 165, 44, 68,123,129,245,143,101, 8,209,215,247,185, 57,218, 53,
281 114,121, 3,128, 4,204,212,146, 2,155, 83,250, 87, 29, 31,159,
282 60, 27,107,156,227,182, 1, 61, 36,160,109, 97, 90, 20,168,132,
283 223,248, 70,164, 55,172, 34, 52,163,117, 35,153,134, 16,178,228
287 ** PTRHASH -- hash a pointer value
295 ** ptrhash hashes a pointer value to a uniformly distributed random
296 ** number between 0 and 255.
298 ** This hash algorithm is based on Peter K. Pearson,
299 ** "Fast Hashing of Variable-Length Text Strings",
300 ** in Communications of the ACM, June 1990, vol 33 no 6.
309 if (sizeof(void*) == 4 && sizeof(unsigned long) == 4)
311 unsigned long n = (unsigned long)p;
313 h = hashtab[n & 0xFF];
314 h = hashtab[h ^ ((n >> 8) & 0xFF)];
315 h = hashtab[h ^ ((n >> 16) & 0xFF)];
316 h = hashtab[h ^ ((n >> 24) & 0xFF)];
319 else if (sizeof(void*) == 8 && sizeof(unsigned long) == 8)
321 unsigned long n = (unsigned long)p;
323 h = hashtab[n & 0xFF];
324 h = hashtab[h ^ ((n >> 8) & 0xFF)];
325 h = hashtab[h ^ ((n >> 16) & 0xFF)];
326 h = hashtab[h ^ ((n >> 24) & 0xFF)];
327 h = hashtab[h ^ ((n >> 32) & 0xFF)];
328 h = hashtab[h ^ ((n >> 40) & 0xFF)];
329 h = hashtab[h ^ ((n >> 48) & 0xFF)];
330 h = hashtab[h ^ ((n >> 56) & 0xFF)];
335 unsigned char *cp = (unsigned char *)&p;
339 for (i = 0; i < sizeof(void*); ++i)
340 h = hashtab[h ^ cp[i]];
346 ** SM_MALLOC_TAGGED -- wrapper around malloc(), debugging version.
349 ** size -- size of requested memory.
350 ** tag -- tag for debugging.
351 ** num -- additional value for debugging.
352 ** group -- heap group for debugging.
355 ** Pointer to memory region.
359 sm_malloc_tagged(size, tag, num, group)
370 ptr = malloc(MALLOC_SIZE(size));
375 if (sm_xtrap_check())
377 if (sm_debug_active(&SmHeapLimit, 1)
378 && sm_debug_level(&SmHeapLimit) < SmHeapTotal + size)
381 ptr = malloc(MALLOC_SIZE(size));
383 if (ptr != NULL && !sm_heap_register(ptr, size, tag, num, group))
391 if (SmHeapTotal > SmHeapMaxTotal)
392 SmHeapMaxTotal = SmHeapTotal;
397 ** SM_MALLOC_TAGGED_X -- wrapper around malloc(), debugging version.
400 ** size -- size of requested memory.
401 ** tag -- tag for debugging.
402 ** num -- additional value for debugging.
403 ** group -- heap group for debugging.
406 ** Pointer to memory region.
409 ** F:sm_heap -- out of memory
413 sm_malloc_tagged_x(size, tag, num, group)
424 ptr = malloc(MALLOC_SIZE(size));
427 sm_exc_raise_x(&SmHeapOutOfMemory);
431 sm_xtrap_raise_x(&SmHeapOutOfMemory);
432 if (sm_debug_active(&SmHeapLimit, 1)
433 && sm_debug_level(&SmHeapLimit) < SmHeapTotal + size)
435 sm_exc_raise_x(&SmHeapOutOfMemory);
438 ptr = malloc(MALLOC_SIZE(size));
440 if (ptr != NULL && !sm_heap_register(ptr, size, tag, num, group))
448 sm_exc_raise_x(&SmHeapOutOfMemory);
450 if (SmHeapTotal > SmHeapMaxTotal)
451 SmHeapMaxTotal = SmHeapTotal;
456 ** SM_HEAP_REGISTER -- register a pointer into the heap for debugging.
459 ** ptr -- pointer to register.
460 ** size -- size of requested memory.
461 ** tag -- tag for debugging.
462 ** num -- additional value for debugging.
463 ** group -- heap group for debugging.
466 ** true iff successfully registered (not yet in table).
470 sm_heap_register(ptr, size, tag, num, group)
482 SM_REQUIRE(ptr != NULL);
484 # if SM_CHECK_REQUIRE
487 ** We require that ptr is not already in SmHeapTable.
490 for (hi = SmHeapTable[i]; hi != NULL; hi = hi->hi_next)
492 if (hi->hi_ptr == ptr)
493 sm_abort("sm_heap_register: ptr %p is already registered (%s:%d)",
494 ptr, hi->hi_tag, hi->hi_num);
496 # endif /* SM_CHECK_REQUIRE */
498 hi = (SM_HEAP_ITEM_T *) malloc(sizeof(SM_HEAP_ITEM_T));
506 hi->hi_group = group;
507 hi->hi_next = SmHeapTable[i];
512 ** SM_REALLOC -- wrapper for realloc(), debugging version.
515 ** ptr -- pointer to old memory area.
516 ** size -- size of requested memory.
519 ** Pointer to new memory area, NULL on failure.
523 sm_realloc(ptr, size)
528 SM_HEAP_ITEM_T *hi, **hp;
533 newptr = realloc(ptr, MALLOC_SIZE(size));
539 return sm_malloc_tagged(size, "realloc", 0, SmHeapGroup);
541 for (hp = &SmHeapTable[ptrhash(ptr)]; *hp != NULL; hp = &(**hp).hi_next)
543 if ((**hp).hi_ptr == ptr)
545 if (sm_xtrap_check())
548 if (sm_debug_active(&SmHeapLimit, 1)
549 && sm_debug_level(&SmHeapLimit)
550 < SmHeapTotal - hi->hi_size + size)
555 newptr = realloc(ptr, MALLOC_SIZE(size));
559 SmHeapTotal = SmHeapTotal - hi->hi_size + size;
560 if (SmHeapTotal > SmHeapMaxTotal)
561 SmHeapMaxTotal = SmHeapTotal;
565 hp = &SmHeapTable[ptrhash(newptr)];
571 sm_abort("sm_realloc: bad argument (%p)", ptr);
573 return NULL; /* keep Irix compiler happy */
577 ** SM_REALLOC_X -- wrapper for realloc(), debugging version.
580 ** ptr -- pointer to old memory area.
581 ** size -- size of requested memory.
584 ** Pointer to new memory area.
587 ** F:sm_heap -- out of memory
591 sm_realloc_x(ptr, size)
596 SM_HEAP_ITEM_T *hi, **hp;
601 newptr = realloc(ptr, MALLOC_SIZE(size));
604 sm_exc_raise_x(&SmHeapOutOfMemory);
609 return sm_malloc_tagged_x(size, "realloc", 0, SmHeapGroup);
611 for (hp = &SmHeapTable[ptrhash(ptr)]; *hp != NULL; hp = &(**hp).hi_next)
613 if ((**hp).hi_ptr == ptr)
615 sm_xtrap_raise_x(&SmHeapOutOfMemory);
617 if (sm_debug_active(&SmHeapLimit, 1)
618 && sm_debug_level(&SmHeapLimit)
619 < SmHeapTotal - hi->hi_size + size)
621 sm_exc_raise_x(&SmHeapOutOfMemory);
624 newptr = realloc(ptr, MALLOC_SIZE(size));
627 sm_exc_raise_x(&SmHeapOutOfMemory);
628 SmHeapTotal = SmHeapTotal - hi->hi_size + size;
629 if (SmHeapTotal > SmHeapMaxTotal)
630 SmHeapMaxTotal = SmHeapTotal;
634 hp = &SmHeapTable[ptrhash(newptr)];
640 sm_abort("sm_realloc_x: bad argument (%p)", ptr);
642 return NULL; /* keep Irix compiler happy */
646 ** SM_FREE_TAGGED -- wrapper around free(), debugging version.
649 ** ptr -- pointer to memory region.
650 ** tag -- tag for debugging.
651 ** num -- additional value for debugging.
658 sm_free_tagged(ptr, tag, num)
674 for (hp = &SmHeapTable[ptrhash(ptr)]; *hp != NULL; hp = &(**hp).hi_next)
676 if ((**hp).hi_ptr == ptr)
678 SM_HEAP_ITEM_T *hi = *hp;
683 ** Fill the block with zeros before freeing.
684 ** This is intended to catch problems with
685 ** dangling pointers. The block is filled with
686 ** zeros, not with some non-zero value, because
687 ** it is common practice in some C code to store
688 ** a zero in a structure member before freeing the
689 ** structure, as a defense against dangling pointers.
692 (void) memset(ptr, 0, hi->hi_size);
693 SmHeapTotal -= hi->hi_size;
701 sm_abort("sm_free: bad argument (%p) (%s:%d)", ptr, tag, num);
705 ** SM_HEAP_CHECKPTR_TAGGED -- check whether ptr is a valid argument to sm_free
708 ** ptr -- pointer to memory region.
709 ** tag -- tag for debugging.
710 ** num -- additional value for debugging.
716 ** aborts if check fails.
720 sm_heap_checkptr_tagged(ptr, tag, num)
731 for (hp = SmHeapTable[ptrhash(ptr)]; hp != NULL; hp = hp->hi_next)
733 if (hp->hi_ptr == ptr)
736 sm_abort("sm_heap_checkptr(%p): bad ptr (%s:%d)", ptr, tag, num);
740 ** SM_HEAP_REPORT -- output "map" of used heap.
743 ** stream -- the file pointer to write to.
744 ** verbosity -- how much info?
751 sm_heap_report(stream, verbosity)
756 unsigned long group0total, group1total, otherstotal, grandtotal;
758 if (!HEAP_CHECK || verbosity <= 0)
760 group0total = group1total = otherstotal = grandtotal = 0;
761 for (i = 0; i < sizeof(SmHeapTable) / sizeof(SmHeapTable[0]); ++i)
763 SM_HEAP_ITEM_T *hi = SmHeapTable[i];
768 || (verbosity > 1 && hi->hi_group != 0))
770 sm_io_fprintf(stream, SM_TIME_DEFAULT,
771 "%4d %*lx %7lu bytes",
773 (int) sizeof(void *) * 2,
775 (unsigned long)hi->hi_size);
776 if (hi->hi_tag != NULL)
778 sm_io_fprintf(stream, SM_TIME_DEFAULT,
783 sm_io_fprintf(stream,
789 sm_io_fprintf(stream, SM_TIME_DEFAULT, "\n");
791 switch (hi->hi_group)
794 group0total += hi->hi_size;
797 group1total += hi->hi_size;
800 otherstotal += hi->hi_size;
803 grandtotal += hi->hi_size;
807 sm_io_fprintf(stream, SM_TIME_DEFAULT,
808 "heap max=%lu, total=%lu, ",
809 (unsigned long) SmHeapMaxTotal, grandtotal);
810 sm_io_fprintf(stream, SM_TIME_DEFAULT,
811 "group 0=%lu, group 1=%lu, others=%lu\n",
812 group0total, group1total, otherstotal);
813 if (grandtotal != SmHeapTotal)
815 sm_io_fprintf(stream, SM_TIME_DEFAULT,
816 "BUG => SmHeapTotal: got %lu, expected %lu\n",
817 (unsigned long) SmHeapTotal, grandtotal);
820 #endif /* !SM_HEAP_CHECK */