[project @ 1996-01-08 20:28:12 by partain]

Initial revision

1 files changed, 273 insertions, 0 deletions

diff --git a/ghc/runtime/regex/test/debugmalloc.c b/ghc/runtime/regex/test/debugmalloc.c
new file mode 100644
index 0000000000..5c468e2124
--- /dev/null
+++ b/ghc/runtime/regex/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);
+}