2 * fda.c - Free Debug Allocator
3 * Copyright (C) 1997 Thomas Helvey <tomh@inxpress.net>
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2, or (at your option)
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 * NOTE: Do not include fda.h here
30 #define HTABLE_SIZE 65539
31 /* #define HTABLE_SIZE 16339 */ /* prime around 16K */
32 /* #define HTABLE_SIZE 251 */
35 #define SHRED_BYTE 0xcd
38 #define SHRED_BYTE 0xcd
40 #define SHRED_BYTE 0xa3
44 #define SHRED_MEM(a,s) memset((a), SHRED_BYTE, (s))
46 #define S_SIZE sizeof(size_t)
47 #define BYTE_PTR(x) (unsigned char*)((x))
49 #define BASE_PTR(p) (BYTE_PTR(p) - S_SIZE)
50 #define BASE_SIZE(s) ((((s) + (S_SIZE - 1) + 2 * S_SIZE) / S_SIZE) * S_SIZE)
53 struct Location* next; /* list next pointer */
54 struct Location* prev; /* list prev pointer */
55 const char* file; /* file name for allocation */
56 int line; /* line allocated on */
57 int count; /* number of allocations for this location */
61 struct BlkHdr* next; /* Next block in list */
62 void* buf; /* Allocated buffer */
63 size_t size; /* Size of allocated buffer */
64 int ref; /* Buffer referenced flag */
65 time_t timestamp; /* Time memory was allocated */
66 struct Location* location; /* Where the allocation took place */
69 typedef struct BlkHdr BlkHdr;
70 typedef struct Location Location;
73 * lowmem_fn - default low memory handler
75 static void lowmem_fn(void)
81 * nomem_fn - default no memory handler
83 static void nomem_fn(void)
88 static void (*lowMemFn)(void) = lowmem_fn; /* default low memory handler */
89 static void (*noMemFn)(void) = nomem_fn; /* default no memory handler */
91 /* begin/end marker signature */
92 static const size_t DEADBEEF = 0xdeadbeef;
93 static size_t byteCount = 0; /* count of currently allocated bytes */
94 static size_t blockCount = 0; /* count of allocated blocks */
95 static size_t byteLimit = 0xffffffff; /* memory size limiter */
96 static BlkHdr* bhTab[HTABLE_SIZE]; /* hash table for allocated blocks */
97 static Location* locationList = 0; /* linked list of memory locations */
100 * fda_set_lowmem_handler - set handler for low memory conditions
101 * this will be called if malloc fails once
103 void fda_set_lowmem_handler(void (*fn)(void))
105 lowMemFn = (fn) ? fn : lowmem_fn;
109 * set_nomem_handler - set handler for no memory conditions
110 * The nomem_handler is called if lowMemFn returns and malloc fails a second
111 * time, the library will assert if lowMemFn is allowed to return
113 void fda_set_nomem_handler(void (*fn)(void))
115 noMemFn = (fn) ? fn : nomem_fn;
119 * fda_get_byte_count - returns the client memory allocated in bytes
121 size_t fda_get_byte_count(void)
127 * fda_get_block_count - returns the number of blocks allocated
129 size_t fda_get_block_count(void)
135 * findLocation - finds a location on the list, this
136 * only compares pointers so it should only be used with
137 * ANSI __FILE__ and __LINE__ macros.
139 static Location* findLocation(const char* file, int line)
141 Location* location = locationList;
142 for ( ; location; location = location->next) {
143 if (file == location->file && line == location->line)
150 * addLocation - adds a allocation location to the list
151 * returns a pointer to the new location
153 static Location* addLocation(const char* file, int line)
157 if ((location = (Location*) malloc(sizeof(Location))) != 0) {
158 location->next = locationList;
160 location->file = file;
161 location->line = line;
164 location->next->prev = location;
165 locationList = location;
171 * freeLocation - frees a file/line info location
173 static void freeLocation(Location* location)
175 assert(0 != location);
176 assert(0 == location->count);
178 if (0 != location->next)
179 location->next->prev = location->prev;
180 if (0 != location->prev)
181 location->prev->next = location->next;
183 locationList = location->next;
188 * hash_ptr - simple pointer hash function
190 static unsigned long hash_ptr(const void* p)
192 return ((unsigned long) p >> 3) % HTABLE_SIZE;
194 return (((unsigned long) p >> 3) ^ ~((unsigned long) p)) % HTABLE_SIZE;
195 return (((unsigned long) p >> 3) | ((unsigned long) p) << 3) % HTABLE_SIZE;
200 * find_blk_exhaustive - find a block by scanning the
201 * entire hash table. This function finds blocks that do not
202 * start at the pointer returned from Malloc.
204 static BlkHdr* find_blk_exhaustive(const void* p)
209 for (i = 0; i < HTABLE_SIZE; ++i) {
210 for (bh = bhTab[i]; bh; bh = bh->next) {
211 if (bh->buf <= p && BYTE_PTR(p) < (BYTE_PTR(bh->buf) + bh->size))
219 * fda_dump_hash - enumerate hash table link counts
221 void fda_dump_hash(void (*enumfn)(int, int))
225 for (i = 0; i < HTABLE_SIZE; ++i) {
227 for (bh = bhTab[i]; bh; bh = bh->next)
234 * find_blk - return the block struct associated with the
237 static BlkHdr* find_blk(const void* p)
239 BlkHdr* bh = bhTab[hash_ptr(p)];
240 for ( ; bh; bh = bh->next) {
244 return find_blk_exhaustive(p);
248 * make_blk - create a block header and add it to the hash table
250 static int make_blk(unsigned char* p, size_t size, Location* loc)
258 if ((bh = (BlkHdr*) malloc(sizeof(BlkHdr))) != 0) {
259 unsigned long h = hash_ptr(p);
264 bh->timestamp = time(0);
267 ++bh->location->count;
275 * free_blk - remove a block header and free it
277 static void free_blk(const void* p)
281 unsigned long h = hash_ptr(p);
283 for (bh = bhTab[h]; bh; bh = bh->next) {
288 bh_prev->next = bh->next;
294 * if bh is NULL p was not allocated here
297 assert(bh->location->count > 0);
298 if (--bh->location->count == 0)
299 freeLocation(bh->location);
301 byteCount -= bh->size;
304 SHRED_MEM(bh, sizeof(BlkHdr));
309 * update_blk - update block info, rehash if pointers are different,
310 * update location info if needed
312 static void update_blk(void* p, void* np, size_t size, const char* file, int line)
317 unsigned long h = hash_ptr(p);
320 * remove the old entry from the hash table
322 for (bh = bhTab[h]; bh; bh = bh->next) {
327 bh_prev->next = bh->next;
329 * put it back in the hash table at hash(np)
345 byteCount -= bh->size;
350 * update location info
352 if (bh->location->file != file || bh->location->line != line) {
353 if (--bh->location->count == 0)
354 freeLocation(bh->location);
355 if ((bh->location = findLocation(file, line)) == 0) {
356 if ((bh->location = addLocation(file, line)) == 0)
359 assert(0 != bh->location);
360 ++bh->location->count;
365 * fda_sizeof - returns the size of block of memory pointed to by p
367 size_t fda_sizeof(const void* p)
369 BlkHdr* bh = find_blk(p);
371 assert(p == bh->buf);
375 void fda_set_byte_limit(size_t limit)
381 * fda_clear_refs - clear referenced markers on all blocks
383 void fda_clear_refs(void)
388 for (i = 0; i < HTABLE_SIZE; ++i) {
389 for (bh = bhTab[i]; bh; bh = bh->next)
395 * fda_set_ref - mark block as referenced
397 void fda_set_ref(const void* p)
399 BlkHdr* bh = find_blk(p);
405 * fda_assert_refs - scan for all blocks and check for null
406 * ptrs and unreferenced (lost) blocks
408 void fda_assert_refs(void)
413 for (i = 0; i < HTABLE_SIZE; ++i) {
414 for (bh = bhTab[i]; bh; bh = bh->next) {
415 assert(0 != bh->buf && 0 < bh->size);
416 assert(1 == bh->ref);
422 * valid_ptr - returns true if p points to allocated memory and
423 * has at least size available
425 int valid_ptr(const void* p, size_t size)
433 * check that there are at least size bytes available from p
435 assert((BYTE_PTR(p) + size) <= (BYTE_PTR(bh->buf) + bh->size));
440 * fda_enum_locations - calls enumfn to list file, line, and count
441 * info for allocations, returns the number of locations found
443 int fda_enum_locations(void (*enumfn)(const char*, int, int))
448 for (location = locationList; location; location = location->next) {
449 (*enumfn)(location->file, location->line, location->count);
456 * fda_enum_leaks - scan hash table for leaks and call enumfn to
459 int fda_enum_leaks(void (*enumfn)(const char*, int, size_t, void*))
464 for (i = 0; i < HTABLE_SIZE; ++i) {
465 for (bh = bhTab[i]; bh; bh = bh->next) {
467 (*enumfn)(bh->location->file, bh->location->line, bh->size, bh->buf);
476 * fda_malloc - allocate size chunk of memory and create debug
479 void* fda_malloc(size_t size, const char* file, int line)
487 assert(sizeof(void*) == sizeof(size_t));
490 * memory limiter do not allocate more than byteLimit
492 if ((size + byteCount) > byteLimit)
496 * Make sure that there is enough room for prefix/postfix
497 * and we get an aligned buffer
499 blk_size = BASE_SIZE(size);
501 if ((p = malloc(blk_size)) == 0) {
503 if ((p = malloc(blk_size)) == 0)
507 * don't allow malloc to fail
511 * shred the memory and set bounds markers
513 SHRED_MEM(p, blk_size);
514 *((size_t*) p) = DEADBEEF;
515 *((size_t*) (BYTE_PTR(p) + blk_size - S_SIZE)) = DEADBEEF;
518 * find the location or create a new one
520 if (0 == (location = findLocation(file, line))) {
521 if (0 == (location = addLocation(file, line))) {
527 * don't allow noMemFn to return
529 assert(0 != location);
530 if (!make_blk(BYTE_PTR(p) + S_SIZE, size, location)) {
531 if (0 == location->count)
532 freeLocation(location);
538 * don't allow noMemFn to return
541 return (BYTE_PTR(p) + S_SIZE);
545 * fda_free - check chunk of memory for overruns and free it
547 void fda_free(void* p)
551 BlkHdr* bh = find_blk(p);
554 /* p already freed or not allocated? */
556 assert(p == bh->buf);
559 /* buffer underflow? */
560 assert(DEADBEEF == *((size_t*) bp));
563 * Note: it's possible to have up to 3 bytes of unchecked space
564 * between size and DEADBEEF
566 size = BASE_SIZE(bh->size);
567 assert(DEADBEEF == *((size_t*)(BYTE_PTR(bp) + size - S_SIZE)));
576 * fda_realloc - resize a buffer, force reallocation if new size is
577 * larger than old size
579 void* fda_realloc(void* p, size_t size, const char* file, int line)
585 * don't allow malloc or free through realloc
589 old_size = fda_sizeof(p);
592 SHRED_MEM(BYTE_PTR(p) + size, old_size - size);
593 else if (size > old_size) {
594 void* t = fda_malloc(size, __FILE__, __LINE__);
595 memmove(t, p, old_size);
599 blk_size = BASE_SIZE(size);
601 if ((np = realloc(BASE_PTR(p), blk_size)) == 0) {
603 if ((np = realloc(BASE_PTR(p), blk_size)) == 0)
607 * don't allow noMemFn to return
611 *((size_t*)(BYTE_PTR(np) + blk_size - S_SIZE)) = DEADBEEF;
613 np = BYTE_PTR(np) + S_SIZE;
614 update_blk(p, np, size, file, line);
619 SHRED_MEM(BYTE_PTR(np) + old_size, size - old_size);
625 * fda_calloc - allocate 0 initialized buffer nelems * size length
627 void* fda_calloc(size_t nelems, size_t size, const char* file, int line)
634 p = fda_malloc(size, file, line);
640 * fda_strdup - duplicates a string returns newly allocated string
642 char* fda_strdup(const char* src, const char* file, int line)
646 p = (char*) fda_malloc(strlen(src) + 1, file, line);
651 #endif /* !defined(NDEBUG) */