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