gnu/lib/libregex/test/debugmalloc.c

   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 \f
  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 \f
  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 \f
 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 }