home *** CD-ROM | disk | FTP | other *** search
/ Big Green CD 8 / BGCD_8_Dev.iso / NEXTSTEP / UNIX / Mail / appnmail-1.8-Solaris / regex-0.12 / test / debugmalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-02  |  5.7 KB  |  274 lines
  1. /* debugmalloc.c: a malloc for debugging purposes.  */
  2.  
  3. #include <stdio.h>
  4. #include <assert.h>
  5. #include <string.h>
  6.  
  7. static unsigned trace = 0;
  8. #define TRACE(s) if (trace) fprintf (stderr, "%s", s)
  9. #define TRACE1(s, e1) if (trace) fprintf (stderr, s, e1)
  10. #define TRACE2(s, e1, e2) if (trace) fprintf (stderr, s, e1, e2)
  11. #define TRACE3(s, e1, e2, e3) if (trace) fprintf (stderr, s, e1, e2, e3)
  12. #define TRACE4(s, e1, e2, e3, e4) \
  13.   if (trace) fprintf (stderr, s, e1, e2, e3, e4)
  14.   
  15. typedef char *address;
  16.  
  17.  
  18. /* Wrap our calls to sbrk.  */
  19.  
  20. address
  21. xsbrk (incr)
  22.   int incr;
  23. {
  24.   extern char *sbrk ();
  25.   address ret = sbrk (incr);
  26.   
  27.   if (ret == (address) -1)
  28.     {
  29.       perror ("sbrk"); /* Actually, we should return NULL, not quit.  */
  30.       abort ();
  31.     }
  32.   
  33.   return ret;
  34. }
  35.  
  36.  
  37.  
  38. typedef struct chunk_struct
  39. {
  40.   /* This is the size (in bytes) that has actually been actually
  41.      allocated, not the size that the user requested.  */
  42.   unsigned alloc_size;
  43.   
  44.   /* This is the size the user requested.  */
  45.   unsigned user_size;
  46.   
  47.   /* Points to the next block in one of the lists.  */
  48.   struct chunk_struct *next;
  49.   
  50.   /* Now comes the user's memory.  */
  51.   address user_mem;
  52.   
  53.   /* After the user's memory is a constant.  */
  54. } *chunk;
  55.  
  56. #define MALLOC_OVERHEAD 16
  57.  
  58. /* We might play around with the `user_size' field, but the amount of
  59.    memory that is actually available in the chunk is always the size
  60.    allocated minus the overhead.  */
  61. #define USER_ALLOC(c) ((c)->alloc_size - MALLOC_OVERHEAD)
  62.  
  63. /* Given a pointer to a malloc-allocated block, the beginning of the
  64.    chunk should always be MALLOC_OVERHEAD - 4 bytes back, since the only
  65.    overhead after the user memory is the constant.  */
  66.  
  67. chunk
  68. mem_to_chunk (mem)
  69.   address mem;
  70. {
  71.   return (chunk) (mem - (MALLOC_OVERHEAD - 4));
  72. }
  73.  
  74.  
  75. /* The other direction is even easier, since the user's memory starts at
  76.    the `user_mem' member in the chunk.  */
  77.  
  78. address
  79. chunk_to_mem (c)
  80.   chunk c;
  81. {
  82.   return (address) &(c->user_mem);
  83. }
  84.  
  85.  
  86.  
  87. /* We keep both all the allocated chunks and all the free chunks on
  88.    lists.  Since we put the next pointers in the chunk structure, we
  89.    don't need a separate chunk_list structure.  */
  90. chunk alloc_list = NULL, free_list = NULL;
  91.  
  92.  
  93. /* We always append the new chunk at the beginning of the list.  */
  94.  
  95. void
  96. chunk_insert (chunk_list, new_c)
  97.   chunk *chunk_list;
  98.   chunk new_c;
  99. {
  100.   chunk c = *chunk_list; /* old beginning of list */
  101.   
  102.   TRACE3 ("  Inserting 0x%x at the beginning of 0x%x, before 0x%x.\n",
  103.           new_c, chunk_list, c);
  104.  
  105.   *chunk_list = new_c;
  106.   new_c->next = c;
  107. }
  108.  
  109.  
  110. /* Thus, removing an element means we have to search until we find it.
  111.    Have to delete before we insert, since insertion changes the next
  112.    pointer, which we need to put it on the other list.  */
  113.  
  114. void
  115. chunk_delete (chunk_list, dead_c)
  116.   chunk *chunk_list;
  117.   chunk dead_c;
  118. {
  119.   chunk c = *chunk_list;
  120.   chunk prev_c = NULL;
  121.  
  122.   TRACE2 ("  Deleting 0x%x from 0x%x:", dead_c, chunk_list);
  123.   
  124.   while (c != dead_c && c != NULL)
  125.     {
  126.       TRACE1 (" 0x%x", c);
  127.       prev_c = c;
  128.       c = c->next;
  129.     }
  130.  
  131.   if (c == NULL)
  132.     {
  133.       fprintf (stderr, "Chunk at 0x%x not found on list.\n", dead_c);
  134.       abort ();
  135.     }
  136.   
  137.   if (prev_c == NULL)
  138.     {
  139.       TRACE1 (".\n  Setting head to 0x%x.\n", c->next);
  140.       *chunk_list = c->next;
  141.     }
  142.   else
  143.     {
  144.       TRACE2 (".\n  Linking next(0x%x) to 0x%x.\n", prev_c, c->next);
  145.       prev_c->next = c->next;
  146.     }
  147. }
  148.  
  149.  
  150. /* See if a list is hunky-dory.  */
  151.  
  152. void
  153. validate_list (chunk_list)
  154.   chunk *chunk_list;
  155. {
  156.   chunk c;
  157.   
  158.   TRACE1 ("  Validating list at 0x%x:", chunk_list);
  159.   
  160.   for (c = *chunk_list; c != NULL; c = c->next)
  161.     {
  162.       assert (c->user_size < c->alloc_size);
  163.       assert (memcmp (chunk_to_mem (c) + c->user_size, "Karl", 4));
  164.       TRACE2 (" 0x%x/%d", c, c->user_size);
  165.     }
  166.   
  167.   TRACE (".\n");
  168. }
  169.  
  170.  
  171. /* See if we have a free chunk of a given size.  We'll take the first
  172.    one that is big enough.  */
  173.  
  174. chunk
  175. free_list_available (needed)
  176.   unsigned needed;
  177. {
  178.   chunk c;
  179.   
  180.   TRACE1 ("  Checking free list for %d bytes:", needed);
  181.   
  182.   if (free_list == NULL)
  183.     {
  184.       return NULL;
  185.     }
  186.   
  187.   c = free_list;
  188.   
  189.   while (c != NULL && USER_ALLOC (c) < needed)
  190.     {
  191.       TRACE2 (" 0x%x/%d", c, USER_ALLOC (c));
  192.       c = c->next;
  193.     }
  194.   
  195.   TRACE1 ("\n  Returning 0x%x.\n", c);
  196.   return c;
  197. }
  198.  
  199.  
  200.  
  201.  
  202. address
  203. malloc (n)
  204.   unsigned n;
  205. {
  206.   address new_mem;
  207.   chunk c;
  208.   
  209.   TRACE1 ("Mallocing %d bytes.\n", n);
  210.  
  211.   validate_list (&free_list);
  212.   validate_list (&alloc_list);
  213.  
  214.   c = free_list_available (n); 
  215.   
  216.   if (c == NULL)
  217.     { /* Nothing suitable on free list.  Allocate a new chunk.  */
  218.       TRACE ("  not on free list.\n");
  219.       c = (chunk) xsbrk (n + MALLOC_OVERHEAD);
  220.       c->alloc_size = n + MALLOC_OVERHEAD;
  221.     }
  222.   else
  223.     { /* Found something on free list.  Don't split it, just use as is.  */
  224.       TRACE ("  found on free list.\n");
  225.       chunk_delete (&free_list, c);
  226.     }
  227.  
  228.   /* If we took this from the free list, then the user size might be
  229.      different now, and consequently the constant at the end might be in
  230.      the wrong place.  */
  231.   c->user_size = n;
  232.   new_mem = chunk_to_mem (c);
  233.   memcpy (new_mem + n, "Karl", 4);
  234.   chunk_insert (&alloc_list, c);
  235.   
  236.   TRACE2 ("Malloc returning 0x%x (chunk 0x%x).\n", new_mem, c);
  237.   return new_mem;
  238. }
  239.  
  240.  
  241. address
  242. realloc (mem, n)
  243.   address mem;
  244.   unsigned n;
  245. {
  246.   void free ();
  247.   chunk c = mem_to_chunk (mem);
  248.   address new_mem;
  249.   
  250.   TRACE3 ("Reallocing %d bytes at 0x%x (chunk 0x%x).\n", n, mem, c);
  251.  
  252.   new_mem = malloc (n);
  253.   memcpy (new_mem, mem, c->user_size);
  254.   free (mem);
  255.   
  256.   return new_mem;
  257. }
  258.  
  259.  
  260. void
  261. free (mem)
  262.   address mem;
  263. {
  264.   chunk c = mem_to_chunk (mem);
  265.   
  266.   TRACE2 ("Freeing memory at 0x%x (chunk at 0x%x).\n", mem, c);
  267.  
  268.   validate_list (&free_list);
  269.   validate_list (&alloc_list);
  270.   
  271.   chunk_delete (&alloc_list, c);
  272.   chunk_insert (&free_list, c);
  273. }
  274.