home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume1 / 8707 / 59 < prev    next >
Encoding:
Internet Message Format  |  1990-07-13  |  13.5 KB
  1. From: allbery@ncoast.UUCP (Brandon S. Allbery)
  2. Newsgroups: comp.sources.misc
  3. Subject: malloc package with debugging
  4. Message-ID: <3268@ncoast.UUCP>
  5. Date: 21 Jul 87 01:32:07 GMT
  6. Sender: allbery@ncoast.UUCP
  7. Organization: Cleveland Public Access UN*X, Cleveland, Oh
  8. Lines: 501
  9. Approved: allbery@ncoast.UUCP
  10. X-Archive: comp.sources.misc/8707/59
  11.  
  12. This is my malloc() debugging package.  Response to my small note was rather
  13. startling, so I'm posting it.
  14.  
  15. The basic idea is that malloc'ed and free'd blocks are kept in doubly-linked
  16. lists.  Every time an allocation function (malloc, free, calloc, realloc,
  17. or _mallchk) is called, the lists are checked to make sure the pointers have
  18. not been overwritten and the sizes are valid.  They catch the majority of
  19. malloc'ed array overflows, and print dumps on segmentation and bus errors
  20. in order to determine if a memory overwrite was involved.  They aren't
  21. perfect (an interpreter or other form of full runtime checking of every
  22. assignment would be needed for that), but they're pretty good.
  23.  
  24. One warning:  you can't depend on a free()'d block still being available,
  25. it will sbrk() backwards if possible.  It also doesn't coalesce adjacent free
  26. blocks or do other kinds of "optimum" memory management; I consider this
  27. unimportant, since this is a debugging package rather than a full replacement
  28. for malloc.  It's also slower than the "real" malloc.
  29.  
  30. The code is included below; it's probably heavily 68000 dependent, but I've
  31. done my best to reduce such dependencies to a miminum.
  32.  
  33. (WARNING:  THIS IS NOT A "shar" FILE!  Cut below and save to the file malloc.c)
  34. ===============================================================================
  35. /*
  36.  * malloc for debugging -- allocates via sbrk and tracks stuff, does diag dump
  37.  * if things appear to be screwed up
  38.  */
  39.  
  40. #include <signal.h>
  41.  
  42. extern char *sbrk();
  43. extern char *memcpy();
  44. extern char *memset();
  45. extern char etext[];
  46. extern char edata[];
  47. extern char end[];
  48.  
  49. struct _Dmi {
  50.     struct _Dmi *m_next;
  51.     struct _Dmi *m_prev;
  52.     long m_size;
  53.     char m_blk[1];
  54. };
  55.  
  56. static struct _Dmi *_fab = (struct _Dmi *) 0;
  57. static struct _Dmi *_ffb = (struct _Dmi *) 0;
  58. static char *_xbrk = 0;
  59. static int _in_malloc = 0;
  60. static int _st_malloc = 0;
  61. int _mall_opt = 1;
  62.  
  63. /*
  64.  * initialize stuff, we want to _malldmp() on a bus/seg error
  65.  */
  66.  
  67. static _mall_sig(sig) {
  68.     if (sig == SIGSEGV)
  69.         _malldstr("\nsegmentation violation\n\n");
  70.     else if (sig == SIGBUS)
  71.         _malldstr("\nbus error\n\n");
  72.     else if (sig == SIGSYS)
  73.         _malldstr("\ninvalid syscall arg\n\n");
  74.     else {
  75.         _malldstr("\nsignal ");
  76.         _malldptr(sig);
  77.         _malldstr("\n\n");
  78.     }
  79.     _malldmp();
  80.     kill(getpid(), sig);
  81. }
  82.  
  83. static _mall_init() {
  84.     if (_st_malloc)
  85.         return;
  86.     signal(SIGSEGV, _mall_sig);
  87.     signal(SIGBUS, _mall_sig);
  88.     _st_malloc = 1;
  89. }
  90.  
  91. /*
  92.  * figure out which allocation block this pointer came from
  93.  * return NULL if none
  94.  */
  95.  
  96. static struct _Dmi *_mallgb(s)
  97. char *s; {
  98.     register struct _Dmi *blk;
  99.  
  100.     for (blk = _fab; blk != (struct _Dmi *) 0; blk = blk->m_next)
  101.         if (blk->m_blk == s)
  102.             break;
  103.     return blk;
  104. }
  105.  
  106. /*
  107.  * internal: write a pointer in hex without using stdio
  108.  */
  109.  
  110. static _malldptr(x)
  111. register long x; {
  112.     char buf[20];
  113.     static char hex[] = "0123456789abcdef";
  114.     register long dx;
  115.     register char *p;
  116.  
  117.     if (x == 0)
  118.         return _malldstr("0x0(0)");
  119.     _malldstr("0x");
  120.     p = buf;
  121.     dx = x;
  122.     while (x > 0)
  123.         *p++ = hex[x % 16], x = x / 16;
  124.     while (p != buf)
  125.         write(2, --p, 1);
  126.     _malldstr("(");
  127.     p = buf;
  128.     x = dx;
  129.     while (x > 0)
  130.         *p++ = hex[x % 10], x /= 10;
  131.     while (p != buf)
  132.         write(2, --p, 1);
  133.     _malldstr(")");
  134. }
  135.  
  136. /*
  137.  * internal: dump a string
  138.  */
  139.  
  140. static _malldstr(s)
  141. register char *s; {
  142.     register int len;
  143.  
  144.     for (len = 0; s[len] != '\0'; len++)
  145.         ;
  146.     write(2, s, len);
  147. }
  148.  
  149. /*
  150.  * dump arena; can be called externally, and is non-destructive
  151.  */
  152.  
  153. _malldmp() {
  154.     register struct _Dmi *blk;
  155.     int oldf;
  156.  
  157.     oldf = _in_malloc;
  158.     _in_malloc = 0;
  159.     _malldstr("brk = ");
  160.     _malldptr(sbrk(0));
  161.     _malldstr("  xbrk = ");
  162.     _malldptr(_xbrk);
  163.     _malldstr("\n_fab = ");
  164.     _malldptr(_fab);
  165.     _malldstr("  _ffb = ");
  166.     _malldptr(_ffb);
  167.     _malldstr("  blksiz = ");
  168.     _malldptr(sizeof (struct _Dmi));
  169.     _malldstr("\netext = ");
  170.     _malldptr(etext);
  171.     _malldstr("  edata = ");
  172.     _malldptr(edata);
  173.     _malldstr("  end = ");
  174.     _malldptr(end);
  175.     _malldstr("\n\nallocated blocks\n\n");
  176.     if (_fab == (struct _Dmi *) 0)
  177.         _malldstr("(none)\n");
  178.     else {
  179.         for (blk = _fab; blk != (struct _Dmi *) 0 && (char *) blk >= _xbrk && (char *) blk < sbrk(0); blk = blk->m_next) {
  180.             _malldstr("(");
  181.             _malldptr(blk);
  182.             _malldstr(")  ");
  183.             _malldptr(blk->m_prev);
  184.             _malldstr("<  ");
  185.             _malldptr(blk->m_size);
  186.             _malldstr("  >");
  187.             _malldptr(blk->m_next);
  188.             _malldstr("\n");
  189.         }
  190.         if (blk != (struct _Dmi *) 0)
  191.             _malldstr("(subsequent block pointers corrupted)\n");
  192.     }
  193.     _malldstr("\nfree blocks\n\n");
  194.     if (_ffb == (struct _Dmi *) 0)
  195.         _malldstr("(none)\n");
  196.     else {
  197.         for (blk = _ffb; blk != (struct _Dmi *) 0 && (char *) blk >= _xbrk && (char *) blk < sbrk(0); blk = blk->m_next) {
  198.             _malldstr("(");
  199.             _malldptr(blk);
  200.             _malldstr(")  ");
  201.             _malldptr(blk->m_prev);
  202.             _malldstr("<  ");
  203.             _malldptr(blk->m_size);
  204.             _malldstr("  >");
  205.             _malldptr(blk->m_next);
  206.             _malldstr("\n");
  207.         }
  208.         if (blk != (struct _Dmi *) 0)
  209.             _malldstr("(subsequent block pointers corrupted)\n");
  210.     }
  211.     _in_malloc = oldf;
  212. }
  213.  
  214. /*
  215.  * internal error routine: print error message (without using stdio) and
  216.  * drop core
  217.  */
  218.  
  219. static _mallerr(fn, s, ptr)
  220. char *fn, *s;
  221. long ptr; {
  222.     _malldstr(fn);
  223.     _malldstr(": ");
  224.     _malldstr(s);
  225.     _malldptr(ptr);
  226.     _malldstr("\n");
  227.     _malldmp();
  228.     signal(SIGQUIT, SIG_DFL);
  229.     kill(getpid(), SIGQUIT);
  230. }
  231.     
  232. char *malloc(n)
  233. register unsigned n; {
  234.     register struct _Dmi *blk;
  235.  
  236.     _in_malloc = 1;
  237.     _mall_init();
  238.     if (_mall_opt)
  239.         _malldstr("called malloc("), _malldptr(n), _malldstr(")\n");
  240.     _mallchk("malloc");
  241.     if (n == 0) {
  242.         _malldstr("malloc(0) is illegal!\n");
  243.         _mall_sig(SIGSYS);
  244.     }
  245.     for (blk = _ffb; blk != (struct _Dmi *) 0; blk = blk->m_next)
  246.         if (blk->m_size >= n) {
  247.             if (blk->m_next != (struct _Dmi *) 0)
  248.                 blk->m_next->m_prev = blk->m_prev;
  249.             if (blk->m_prev != (struct _Dmi *) 0)
  250.                 blk->m_prev->m_next = blk->m_next;
  251.             if (blk == _ffb)
  252.                 _ffb = blk->m_next;
  253.             blk->m_next = _fab;
  254.             blk->m_prev = (struct _Dmi *) 0;
  255.             if (_fab != (struct _Dmi *) 0)
  256.                 _fab->m_prev = blk;
  257.             _fab = blk;
  258.             _in_malloc = 0;
  259.             return blk->m_blk;
  260.         }
  261.     if ((blk = (struct _Dmi *) sbrk(sizeof (struct _Dmi) + n - 1)) == (struct _Dmi *) -1) {
  262.         _in_malloc = 0;
  263.         return (char *) 0;    /* no space */
  264.     }
  265.     if (_xbrk == (char *) 0)
  266.         _xbrk = (char *) blk;
  267.     blk->m_next = _fab;
  268.     blk->m_prev = (struct _Dmi *) 0;
  269.     if (_fab != (struct _Dmi *) 0)
  270.         _fab->m_prev = blk;
  271.     _fab = blk;
  272.     blk->m_size = n;
  273.     _in_malloc = 0;
  274.     return blk->m_blk;
  275. }
  276.  
  277. /* The free-block list is sorted in size order */
  278.  
  279. free(s)
  280. register char *s; {
  281.     register struct _Dmi *blk, *fblk;
  282.     int didit;
  283.  
  284.     _in_malloc = 1;
  285.     _mall_init();
  286.     if (_mall_opt)
  287.         _malldstr("called free("), _malldptr(s), _malldstr(")\n");
  288.     _mallchk("free");
  289.     if (s == (char *) 0) {
  290.         _malldstr("free((char *) 0) is illegal!\n");
  291.         _mall_sig(SIGSYS);
  292.     }
  293.     if ((blk = _mallgb(s)) == (struct _Dmi *) 0)
  294.         _mallerr("non-allocated pointer passed to free(): ", s);
  295.     if (blk->m_prev != (struct _Dmi *) 0)
  296.         blk->m_prev->m_next = blk->m_next;
  297.     if (blk->m_next != (struct _Dmi *) 0)
  298.         blk->m_next->m_prev = blk->m_prev;
  299.     if (blk == _fab)
  300.         _fab = blk->m_next;
  301.     if (_ffb == (struct _Dmi *) 0) {
  302.         _ffb = blk;
  303.         blk->m_next = (struct _Dmi *) 0;
  304.         blk->m_prev = (struct _Dmi *) 0;
  305.         goto crunch;
  306.     }
  307.     for (fblk = _ffb; fblk->m_next != (struct _Dmi *) 0; fblk = fblk->m_next)
  308.         if (fblk->m_next->m_size >= blk->m_size)
  309.             break;
  310.     blk->m_next = fblk->m_next;
  311.     if (fblk->m_next != (struct _Dmi *) 0)
  312.         fblk->m_next->m_prev = blk;
  313.     blk->m_prev = fblk;
  314.     fblk->m_next = blk;
  315.  
  316. /*
  317.  * crunch the free list by dropping consecutive end-of-brk until we hit xbrk
  318.  * or a "hole" (i.e. allocated block).  coalescing is possible but not supp-
  319.  * orted in malloc, so we don't bother here.
  320.  */
  321.  
  322. crunch:
  323.     didit = 1;
  324.     while (_ffb != (struct _Dmi *) 0 && didit) {
  325.         didit = 0;
  326.         for (fblk = _ffb; fblk != (struct _Dmi *) 0; fblk = fblk->m_next)
  327.             if ((char *) fblk + sizeof *fblk + fblk->m_size - 1 == sbrk(0)) {
  328.                 didit = 1;
  329.                 if (fblk->m_next != (struct _Dmi *) 0)
  330.                     fblk->m_next->m_prev = fblk->m_prev;
  331.                 if (fblk->m_prev != (struct _Dmi *) 0)
  332.                     fblk->m_prev->m_next = fblk->m_next;
  333.                 if (fblk == _ffb)
  334.                     _ffb = fblk->m_next;
  335.                 sbrk(- fblk->m_size);
  336.                 break;
  337.             }
  338.     }
  339.     _in_malloc = 0;
  340. }
  341.  
  342. char *realloc(s, n)
  343. register char *s;
  344. register unsigned n; {
  345.     register char *s1, *d, *d1;
  346.     register struct _Dmi *blk;
  347.  
  348.     if (_mall_opt)
  349.         _malldstr("called realloc("), _malldptr(s), _malldstr(", "), _malldptr(n), _malldstr(")\n");
  350.     _mallchk("realloc");
  351.     if (s == (char *) 0) {
  352.         _malldstr("realloc((char *) 0, size) is illegal!\n");
  353.         _mall_sig(SIGSYS);
  354.     }
  355.     if (n == 0) {
  356.         _malldstr("realloc(ptr, 0) is illegal!\n");
  357.         _mall_sig(SIGSYS);
  358.     }
  359.     if ((blk = _mallgb(s)) == (struct _Dmi *) 0)
  360.         _mallerr("non-allocated pointer passed to realloc(): ", s);
  361.     if ((s1 = malloc(n)) == (char *) 0)
  362.         return (char *) 0;
  363.     if (blk->m_size < n)
  364.         n = blk->m_size;
  365.     d1 = s1;
  366.     d = s;
  367.     while (n-- != 0)
  368.         *d1++ = *d++;
  369.     free(s);
  370.     return s1;
  371. }
  372.  
  373. /*
  374.  * _mallchk() is global, so external routines can do discreet checks on the
  375.  * arena.  If the arena is detectibly corrupted, it will abort().
  376.  */
  377.  
  378. _mallchk(fn)
  379. char *fn; {
  380.     register struct _Dmi *blk, *cblk;
  381.     register char *send;
  382.     register int cnt;
  383.  
  384.     send = sbrk(0);
  385.     cblk = (struct _Dmi *) 0;
  386.     for (blk = _fab; blk != (struct _Dmi *) 0; cblk = blk, blk = blk->m_next) {
  387.         if ((char *) blk < _xbrk || (char *) blk >= send)
  388.             _mallerr(fn, "allocated block list corrupted: blkptr = ", blk);
  389.         if (blk->m_prev != cblk)
  390.             _mallerr(fn, "allocated block list corrupted: back pointer incorrect blk ", blk);
  391.         if (blk->m_size < 0)
  392.             _mallerr(fn, "allocated block list corrupted: blk->m_size = ", blk->m_size);
  393.     }
  394.     cblk = (struct _Dmi *) 0;
  395.     for (blk = _ffb; blk != (struct _Dmi *) 0; cblk = blk, blk = blk->m_next) {
  396.         if ((char *) blk < _xbrk || (char *) blk >= sbrk(0))
  397.             _mallerr(fn, "free block list corrupted: blkptr = ", blk);
  398.         if (blk->m_prev != cblk)
  399.             _mallerr(fn, "free block list corrupted: back pointer incorrect blk ", blk);
  400.         if (blk->m_size < 0)
  401.             _mallerr(fn, "free block list corrupted: blk->m_size = ", blk->m_size);
  402.     }
  403.     for (blk = _fab; blk != (struct _Dmi *) 0; blk = blk->m_next) {
  404.         if ((char *) blk + sizeof *blk + blk->m_size - 1 > send) {
  405.             _malldstr("(brk = ");
  406.             _malldptr(send);
  407.             _malldstr(", eblk = ");
  408.             _malldptr((char *) blk + sizeof *blk + blk->m_size - 1);
  409.             _malldstr(")\n");
  410.             _mallerr(fn, "allocated block extends past brk: ", blk);
  411.         }
  412.         cnt = 0;
  413.         for (cblk = _fab; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
  414.             if (blk == cblk)
  415.                 if (cnt++ == 0)
  416.                     continue;
  417.                 else
  418.                     _mallerr(fn, "block allocated twice: ", blk);
  419.             if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
  420.                 _malldstr("(blk = ");
  421.                 _malldptr(blk);
  422.                 _malldstr(", cblk = ");
  423.                 _malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
  424.                 _malldstr(")\n");
  425.                 _mallerr(fn, "nested block in allocated list: ", blk);
  426.             }
  427.         }
  428.         for (cblk = _ffb; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
  429.             if (blk == cblk)
  430.                 _mallerr(fn, "block on allocated and free lists: ", blk);
  431.             if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
  432.                 _malldstr("(blk = ");
  433.                 _malldptr(blk);
  434.                 _malldstr(", cblk = ");
  435.                 _malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
  436.                 _malldstr(")\n");
  437.                 _mallerr(fn, "allocated block nested in free block: ", blk);
  438.             }
  439.         }
  440.     }
  441.     for (blk = _ffb; blk != (struct _Dmi *) 0; blk = blk->m_next) {
  442.         if ((char *) blk + sizeof *blk + blk->m_size - 1 > send) {
  443.             _malldstr("(brk = ");
  444.             _malldptr(send);
  445.             _malldstr(", eblk = ");
  446.             _malldptr((char *) blk + sizeof *blk + blk->m_size - 1);
  447.             _malldstr(")\n");
  448.             _mallerr(fn, "free block extends past brk: ", blk);
  449.         }
  450.         cnt = 0;
  451.         for (cblk = _ffb; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
  452.             if (blk == cblk)
  453.                 if (cnt++ == 0)
  454.                     continue;
  455.                 else
  456.                     _mallerr(fn, "block freed twice: ", blk);
  457.             if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
  458.                 _malldstr("(blk = ");
  459.                 _malldptr(blk);
  460.                 _malldstr(", cblk = ");
  461.                 _malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
  462.                 _malldstr(")\n");
  463.                 _mallerr(fn, "nested block in free list: ", blk);
  464.             }
  465.         }
  466.         for (cblk = _fab; cblk != (struct _Dmi *) 0; cblk = cblk->m_next) {
  467.             if (blk == cblk)
  468.                 _mallerr(fn, "block on allocated and free lists: ", blk);
  469.             if (blk > cblk && (char *) blk < (char *) cblk + sizeof *cblk + cblk->m_size - 1) {
  470.                 _malldstr("(blk = ");
  471.                 _malldptr(blk);
  472.                 _malldstr(", cblk = ");
  473.                 _malldptr((char *) cblk + sizeof *cblk + cblk->m_size - 1);
  474.                 _malldstr(")\n");
  475.                 _mallerr(fn, "free block nested in allocated block: ", blk);
  476.             }
  477.         }
  478.     }
  479. }
  480.  
  481. /*
  482.  * malloc objects and zero storage
  483.  */
  484.  
  485. char *calloc(n, size)
  486. register unsigned n, size; {
  487.     register char *s, *s1;
  488.  
  489.     if (_mall_opt)
  490.         _malldstr("called calloc("), _malldptr(n), _malldstr(", "), _malldptr(size), _malldstr(")\n");
  491.     n *= size;
  492.     if ((s = malloc(n)) == (char *) 0)
  493.         return (char *) 0;
  494.     for (s1 = s; n != 0; n--)
  495.         *s1++ = 0;
  496.     return s;
  497. }
  498.  
  499. /*
  500.  * for some reason this is in /lib/libc.a(calloc.o)
  501.  */
  502.  
  503. cfree(s)
  504. char *s; {
  505.     free(s);
  506. }
  507. -- 
  508.       [Copyright 1987 Brandon S. Allbery, all rights reserved]
  509.  [Redistribution permitted only if redistribution is subsequently permitted.]
  510. Brandon S. Allbery, moderator of comp.sources.misc and comp.binaries.ibm.pc
  511. {{harvard,mit-eddie}!necntc,well!hoptoad,sun!cwruecmp!hal,cbosgd}!ncoast!allbery
  512.    <<ncoast Public Access UNIX: +1 216 781 6201 24hrs. 300/1200/2400 baud>>
  513.