1/* $FreeBSD$ */
2
3/*
4  xmalloc.c - Simple malloc debugging library implementation
5
6  This software is released under a BSD-style license.
7  See the file LICENSE for details and copyright.
8
9*/
10
11/*
12  TODO:
13   - red zones
14   - group dumps by source location
15*/
16
17#include <stdlib.h>
18#include <assert.h>
19#include <stdio.h>
20#define XMALLOC_INTERNAL 1
21#include "xmalloc.h"
22
23
24/*
25  Internal stuff.
26*/
27
28typedef struct hashTableItemRec {
29  void *ptr;
30  int bytes;
31  const char *file;
32  int line;
33  const char *func;
34  struct hashTableItemRec *next;
35} hashTableItem;
36
37typedef struct {
38  hashTableItem **table;
39} hashTable;
40
41static int xmalloc_peak;
42int xmalloc_current;
43static int xmalloc_peak_blocks;
44int xmalloc_current_blocks;
45static int xmalloc_fail_after;
46
47#define TABLE_BITS 8
48#define TABLE_MASK ((1 << TABLE_BITS) - 1)
49#define TABLE_SIZE (1 << TABLE_BITS)
50
51static hashTable *
52hash_table_new(void)
53{
54  hashTable *tbl;
55
56  tbl = malloc(sizeof(*tbl));
57
58  if (tbl != NULL)
59    {
60      tbl->table = calloc(TABLE_SIZE, sizeof(*tbl->table));
61
62      if (tbl->table == NULL)
63	{
64	  free(tbl);
65	  return NULL;
66	}
67    }
68
69  return tbl;
70}
71
72static int
73hash_void_ptr(void *ptr)
74{
75  int hash;
76  int i;
77
78  /* I took this hash function just off the top of my head, I have
79     no idea whether it is bad or very bad. */
80  hash = 0;
81  for (i = 0; i < (int)sizeof(ptr)*8 / TABLE_BITS; i++)
82    {
83      hash ^= (unsigned long)ptr >> i*8;
84      hash += i * 17;
85      hash &= TABLE_MASK;
86    }
87  return hash;
88}
89
90static void
91hash_table_add(hashTable *tbl, void *ptr, int bytes,
92	       const char *file, int line, const char *func)
93{
94  int i;
95  hashTableItem *item, *new;
96
97  i = hash_void_ptr(ptr);
98
99  item = tbl->table[i];
100  if (item != NULL)
101    while (item->next != NULL)
102      item = item->next;
103
104  new = malloc(sizeof(*new));
105  assert(new != NULL);
106  new->ptr = ptr;
107  new->bytes = bytes;
108  new->file = file;
109  new->line = line;
110  new->func = func;
111  new->next = NULL;
112  if (item != NULL)
113    item->next = new;
114  else
115    tbl->table[i] = new;
116
117  xmalloc_current += bytes;
118  if (xmalloc_current > xmalloc_peak)
119    xmalloc_peak = xmalloc_current;
120  xmalloc_current_blocks++;
121  if (xmalloc_current_blocks > xmalloc_peak_blocks)
122    xmalloc_peak_blocks = xmalloc_current_blocks;
123}
124
125static void
126hash_table_del(hashTable *tbl, void *ptr)
127{
128  int i;
129  hashTableItem *item, *prev;
130
131  i = hash_void_ptr(ptr);
132
133  item = tbl->table[i];
134  if (item == NULL)
135    {
136      printf("xfree: invalid ptr %p\n", ptr);
137      abort();
138    }
139  prev = NULL;
140  while (item->ptr != ptr)
141    {
142      prev = item;
143      item = item->next;
144    }
145  if (item->ptr != ptr)
146    {
147      printf("xfree: invalid ptr %p\n", ptr);
148      abort();
149    }
150
151  xmalloc_current -= item->bytes;
152  xmalloc_current_blocks--;
153
154  if (prev != NULL)
155    {
156      prev->next = item->next;
157      free(item);
158    }
159  else
160    {
161      tbl->table[i] = item->next;
162      free(item);
163    }
164}
165
166static hashTable *xmalloc_table = NULL;
167
168static void
169xmalloc_init(void)
170{
171  if (xmalloc_table == NULL)
172    {
173      xmalloc_table = hash_table_new();
174      xmalloc_peak = 0;
175      xmalloc_peak_blocks = 0;
176      xmalloc_current = 0;
177      xmalloc_current_blocks = 0;
178      xmalloc_fail_after = -1;
179    }
180  assert(xmalloc_table != NULL);
181  assert(xmalloc_table->table != NULL);
182}
183
184
185
186/*
187  Public API.
188*/
189
190void
191xmalloc_configure(int fail_after)
192{
193  xmalloc_init();
194  xmalloc_fail_after = fail_after;
195}
196
197int
198xmalloc_dump_leaks(void)
199{
200  int i;
201  int num_leaks = 0;
202  int leaked_bytes = 0;
203  hashTableItem *item;
204
205  xmalloc_init();
206
207  for (i = 0; i < TABLE_SIZE; i++)
208    {
209      item = xmalloc_table->table[i];
210      while (item != NULL)
211	{
212	  printf("%s:%d: %s: %d bytes at %p not freed\n",
213		 item->file, item->line, item->func, item->bytes, item->ptr);
214	  num_leaks++;
215	  leaked_bytes += item->bytes;
216	  item = item->next;
217	}
218    }
219  if (num_leaks == 0)
220    printf("No memory leaks.\n");
221  else
222    printf("%d unfreed memory chuncks, total %d unfreed bytes.\n",
223	   num_leaks, leaked_bytes);
224  printf("Peak memory consumption %d bytes (%.1f kB, %.1f MB) in %d blocks ",
225	 xmalloc_peak, (double)xmalloc_peak / 1024,
226	 (double)xmalloc_peak / (1024*1024), xmalloc_peak_blocks);
227  printf("(average ");
228  if (xmalloc_peak_blocks)
229    printf("%d", ((xmalloc_peak + xmalloc_peak_blocks / 2)
230		  / xmalloc_peak_blocks));
231  else
232    printf("N/A");
233  printf(" bytes per block).\n");
234
235  return num_leaks;
236}
237
238void *
239xmalloc_impl(size_t size, const char *file, int line, const char *func)
240{
241  void *ptr;
242
243  xmalloc_init();
244  assert(size > 0);
245
246  if (xmalloc_fail_after == 0)
247    {
248      xmalloc_fail_after = -2;
249#if 0
250      printf("xmalloc: forced failure %s:%d: %s\n", file, line, func);
251#endif
252      return NULL;
253    }
254  else if (xmalloc_fail_after == -2)
255    {
256      printf("xmalloc: called after failure from %s:%d: %s\n",
257	     file, line, func);
258      assert(0);
259    }
260  else if (xmalloc_fail_after > 0)
261    xmalloc_fail_after--;
262
263  ptr = malloc(size);
264  if (ptr != NULL)
265    hash_table_add(xmalloc_table, ptr, (int)size, file, line, func);
266  return ptr;
267}
268
269void *
270xcalloc_impl(size_t nmemb, size_t size, const char *file, int line,
271	     const char *func)
272{
273  void *ptr;
274
275  xmalloc_init();
276  assert(size > 0);
277
278  if (xmalloc_fail_after == 0)
279    {
280      xmalloc_fail_after = -2;
281#if 0
282      printf("xcalloc: forced failure %s:%d: %s\n", file, line, func);
283#endif
284      return NULL;
285    }
286  else if (xmalloc_fail_after == -2)
287    {
288      printf("xcalloc: called after failure from %s:%d: %s\n",
289	     file, line, func);
290      assert(0);
291    }
292  else if (xmalloc_fail_after > 0)
293    xmalloc_fail_after--;
294
295  ptr = calloc(nmemb, size);
296  if (ptr != NULL)
297    hash_table_add(xmalloc_table, ptr, (int)(nmemb * size), file, line, func);
298  return ptr;
299}
300
301void
302xfree_impl(void *ptr, const char *file, int line, const char *func)
303{
304  /*LINTED*/(void)&file;
305  /*LINTED*/(void)&line;
306  /*LINTED*/(void)&func;
307  xmalloc_init();
308
309  if (ptr != NULL)
310    hash_table_del(xmalloc_table, ptr);
311  free(ptr);
312}
313
314void *
315xrealloc_impl(void *ptr, size_t new_size, const char *file, int line,
316	      const char *func)
317{
318  void *new_ptr;
319
320  xmalloc_init();
321  assert(ptr != NULL);
322  assert(new_size > 0);
323
324  if (xmalloc_fail_after == 0)
325    {
326      xmalloc_fail_after = -2;
327      return NULL;
328    }
329  else if (xmalloc_fail_after == -2)
330    {
331      printf("xrealloc: called after failure from %s:%d: %s\n",
332	     file, line, func);
333      assert(0);
334    }
335  else if (xmalloc_fail_after > 0)
336    xmalloc_fail_after--;
337
338  new_ptr = realloc(ptr, new_size);
339  if (new_ptr != NULL)
340    {
341      hash_table_del(xmalloc_table, ptr);
342      hash_table_add(xmalloc_table, new_ptr, (int)new_size, file, line, func);
343    }
344  return new_ptr;
345}
346
347
348
349/* EOF */
350