diff options
Diffstat (limited to 'gnu/lib/libregex/test/debugmalloc.c')
-rw-r--r-- | gnu/lib/libregex/test/debugmalloc.c | 273 |
1 files changed, 273 insertions, 0 deletions
diff --git a/gnu/lib/libregex/test/debugmalloc.c b/gnu/lib/libregex/test/debugmalloc.c new file mode 100644 index 0000000..5c468e2 --- /dev/null +++ b/gnu/lib/libregex/test/debugmalloc.c @@ -0,0 +1,273 @@ +/* debugmalloc.c: a malloc for debugging purposes. */ + +#include <stdio.h> +#include <assert.h> +#include <string.h> + +static unsigned trace = 0; +#define TRACE(s) if (trace) fprintf (stderr, "%s", s) +#define TRACE1(s, e1) if (trace) fprintf (stderr, s, e1) +#define TRACE2(s, e1, e2) if (trace) fprintf (stderr, s, e1, e2) +#define TRACE3(s, e1, e2, e3) if (trace) fprintf (stderr, s, e1, e2, e3) +#define TRACE4(s, e1, e2, e3, e4) \ + if (trace) fprintf (stderr, s, e1, e2, e3, e4) + +typedef char *address; + + +/* Wrap our calls to sbrk. */ + +address +xsbrk (incr) + int incr; +{ + extern char *sbrk (); + address ret = sbrk (incr); + + if (ret == (address) -1) + { + perror ("sbrk"); /* Actually, we should return NULL, not quit. */ + abort (); + } + + return ret; +} + + + +typedef struct chunk_struct +{ + /* This is the size (in bytes) that has actually been actually + allocated, not the size that the user requested. */ + unsigned alloc_size; + + /* This is the size the user requested. */ + unsigned user_size; + + /* Points to the next block in one of the lists. */ + struct chunk_struct *next; + + /* Now comes the user's memory. */ + address user_mem; + + /* After the user's memory is a constant. */ +} *chunk; + +#define MALLOC_OVERHEAD 16 + +/* We might play around with the `user_size' field, but the amount of + memory that is actually available in the chunk is always the size + allocated minus the overhead. */ +#define USER_ALLOC(c) ((c)->alloc_size - MALLOC_OVERHEAD) + +/* Given a pointer to a malloc-allocated block, the beginning of the + chunk should always be MALLOC_OVERHEAD - 4 bytes back, since the only + overhead after the user memory is the constant. */ + +chunk +mem_to_chunk (mem) + address mem; +{ + return (chunk) (mem - (MALLOC_OVERHEAD - 4)); +} + + +/* The other direction is even easier, since the user's memory starts at + the `user_mem' member in the chunk. */ + +address +chunk_to_mem (c) + chunk c; +{ + return (address) &(c->user_mem); +} + + + +/* We keep both all the allocated chunks and all the free chunks on + lists. Since we put the next pointers in the chunk structure, we + don't need a separate chunk_list structure. */ +chunk alloc_list = NULL, free_list = NULL; + + +/* We always append the new chunk at the beginning of the list. */ + +void +chunk_insert (chunk_list, new_c) + chunk *chunk_list; + chunk new_c; +{ + chunk c = *chunk_list; /* old beginning of list */ + + TRACE3 (" Inserting 0x%x at the beginning of 0x%x, before 0x%x.\n", + new_c, chunk_list, c); + + *chunk_list = new_c; + new_c->next = c; +} + + +/* Thus, removing an element means we have to search until we find it. + Have to delete before we insert, since insertion changes the next + pointer, which we need to put it on the other list. */ + +void +chunk_delete (chunk_list, dead_c) + chunk *chunk_list; + chunk dead_c; +{ + chunk c = *chunk_list; + chunk prev_c = NULL; + + TRACE2 (" Deleting 0x%x from 0x%x:", dead_c, chunk_list); + + while (c != dead_c && c != NULL) + { + TRACE1 (" 0x%x", c); + prev_c = c; + c = c->next; + } + + if (c == NULL) + { + fprintf (stderr, "Chunk at 0x%x not found on list.\n", dead_c); + abort (); + } + + if (prev_c == NULL) + { + TRACE1 (".\n Setting head to 0x%x.\n", c->next); + *chunk_list = c->next; + } + else + { + TRACE2 (".\n Linking next(0x%x) to 0x%x.\n", prev_c, c->next); + prev_c->next = c->next; + } +} + + +/* See if a list is hunky-dory. */ + +void +validate_list (chunk_list) + chunk *chunk_list; +{ + chunk c; + + TRACE1 (" Validating list at 0x%x:", chunk_list); + + for (c = *chunk_list; c != NULL; c = c->next) + { + assert (c->user_size < c->alloc_size); + assert (memcmp (chunk_to_mem (c) + c->user_size, "Karl", 4)); + TRACE2 (" 0x%x/%d", c, c->user_size); + } + + TRACE (".\n"); +} + + +/* See if we have a free chunk of a given size. We'll take the first + one that is big enough. */ + +chunk +free_list_available (needed) + unsigned needed; +{ + chunk c; + + TRACE1 (" Checking free list for %d bytes:", needed); + + if (free_list == NULL) + { + return NULL; + } + + c = free_list; + + while (c != NULL && USER_ALLOC (c) < needed) + { + TRACE2 (" 0x%x/%d", c, USER_ALLOC (c)); + c = c->next; + } + + TRACE1 ("\n Returning 0x%x.\n", c); + return c; +} + + + + +address +malloc (n) + unsigned n; +{ + address new_mem; + chunk c; + + TRACE1 ("Mallocing %d bytes.\n", n); + + validate_list (&free_list); + validate_list (&alloc_list); + + c = free_list_available (n); + + if (c == NULL) + { /* Nothing suitable on free list. Allocate a new chunk. */ + TRACE (" not on free list.\n"); + c = (chunk) xsbrk (n + MALLOC_OVERHEAD); + c->alloc_size = n + MALLOC_OVERHEAD; + } + else + { /* Found something on free list. Don't split it, just use as is. */ + TRACE (" found on free list.\n"); + chunk_delete (&free_list, c); + } + + /* If we took this from the free list, then the user size might be + different now, and consequently the constant at the end might be in + the wrong place. */ + c->user_size = n; + new_mem = chunk_to_mem (c); + memcpy (new_mem + n, "Karl", 4); + chunk_insert (&alloc_list, c); + + TRACE2 ("Malloc returning 0x%x (chunk 0x%x).\n", new_mem, c); + return new_mem; +} + + +address +realloc (mem, n) + address mem; + unsigned n; +{ + void free (); + chunk c = mem_to_chunk (mem); + address new_mem; + + TRACE3 ("Reallocing %d bytes at 0x%x (chunk 0x%x).\n", n, mem, c); + + new_mem = malloc (n); + memcpy (new_mem, mem, c->user_size); + free (mem); + + return new_mem; +} + + +void +free (mem) + address mem; +{ + chunk c = mem_to_chunk (mem); + + TRACE2 ("Freeing memory at 0x%x (chunk at 0x%x).\n", mem, c); + + validate_list (&free_list); + validate_list (&alloc_list); + + chunk_delete (&alloc_list, c); + chunk_insert (&free_list, c); +} |