1 /* debugmalloc.c: a malloc for debugging purposes. */
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)
15 typedef char *address;
18 /* Wrap our calls to sbrk. */
25 address ret = sbrk (incr);
27 if (ret == (address) -1)
29 perror ("sbrk"); /* Actually, we should return NULL, not quit. */
38 typedef struct chunk_struct
40 /* This is the size (in bytes) that has actually been actually
41 allocated, not the size that the user requested. */
44 /* This is the size the user requested. */
47 /* Points to the next block in one of the lists. */
48 struct chunk_struct *next;
50 /* Now comes the user's memory. */
53 /* After the user's memory is a constant. */
56 #define MALLOC_OVERHEAD 16
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)
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. */
71 return (chunk) (mem - (MALLOC_OVERHEAD - 4));
75 /* The other direction is even easier, since the user's memory starts at
76 the `user_mem' member in the chunk. */
82 return (address) &(c->user_mem);
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;
93 /* We always append the new chunk at the beginning of the list. */
96 chunk_insert (chunk_list, new_c)
100 chunk c = *chunk_list; /* old beginning of list */
102 TRACE3 (" Inserting 0x%x at the beginning of 0x%x, before 0x%x.\n",
103 new_c, chunk_list, c);
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. */
115 chunk_delete (chunk_list, dead_c)
119 chunk c = *chunk_list;
122 TRACE2 (" Deleting 0x%x from 0x%x:", dead_c, chunk_list);
124 while (c != dead_c && c != NULL)
133 fprintf (stderr, "Chunk at 0x%x not found on list.\n", dead_c);
139 TRACE1 (".\n Setting head to 0x%x.\n", c->next);
140 *chunk_list = c->next;
144 TRACE2 (".\n Linking next(0x%x) to 0x%x.\n", prev_c, c->next);
145 prev_c->next = c->next;
150 /* See if a list is hunky-dory. */
153 validate_list (chunk_list)
158 TRACE1 (" Validating list at 0x%x:", chunk_list);
160 for (c = *chunk_list; c != NULL; c = c->next)
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);
171 /* See if we have a free chunk of a given size. We'll take the first
172 one that is big enough. */
175 free_list_available (needed)
180 TRACE1 (" Checking free list for %d bytes:", needed);
182 if (free_list == NULL)
189 while (c != NULL && USER_ALLOC (c) < needed)
191 TRACE2 (" 0x%x/%d", c, USER_ALLOC (c));
195 TRACE1 ("\n Returning 0x%x.\n", c);
209 TRACE1 ("Mallocing %d bytes.\n", n);
211 validate_list (&free_list);
212 validate_list (&alloc_list);
214 c = free_list_available (n);
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;
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);
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
232 new_mem = chunk_to_mem (c);
233 memcpy (new_mem + n, "Karl", 4);
234 chunk_insert (&alloc_list, c);
236 TRACE2 ("Malloc returning 0x%x (chunk 0x%x).\n", new_mem, c);
247 chunk c = mem_to_chunk (mem);
250 TRACE3 ("Reallocing %d bytes at 0x%x (chunk 0x%x).\n", n, mem, c);
252 new_mem = malloc (n);
253 memcpy (new_mem, mem, c->user_size);
264 chunk c = mem_to_chunk (mem);
266 TRACE2 ("Freeing memory at 0x%x (chunk at 0x%x).\n", mem, c);
268 validate_list (&free_list);
269 validate_list (&alloc_list);
271 chunk_delete (&alloc_list, c);
272 chunk_insert (&free_list, c);