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
32 #define HTABLE_SIZE 65539
33 /* #define HTABLE_SIZE 16339 */ /* prime around 16K */
34 /* #define HTABLE_SIZE 251 */
37 #define SHRED_BYTE 0xcd
40 #define SHRED_BYTE 0xcd
42 #define SHRED_BYTE 0xa3
46 #define SHRED_MEM(a,s) memset((a), SHRED_BYTE, (s))
48 #define S_SIZE sizeof(size_t)
49 #define BYTE_PTR(x) (unsigned char*)((x))
51 #define BASE_PTR(p) (BYTE_PTR(p) - S_SIZE)
52 #define BASE_SIZE(s) ((((s) + (S_SIZE - 1) + 2 * S_SIZE) / S_SIZE) * S_SIZE)
55 struct Location* next; /* list next pointer */
56 struct Location* prev; /* list prev pointer */
57 const char* file; /* file name for allocation */
58 int line; /* line allocated on */
59 int count; /* number of allocations for this location */
63 struct BlkHdr* next; /* Next block in list */
64 void* buf; /* Allocated buffer */
65 size_t size; /* Size of allocated buffer */
66 int ref; /* Buffer referenced flag */
67 time_t timestamp; /* Time memory was allocated */
68 struct Location* location; /* Where the allocation took place */
71 typedef struct BlkHdr BlkHdr;
72 typedef struct Location Location;
75 * lowmem_fn - default low memory handler
77 static void lowmem_fn(void)
83 * nomem_fn - default no memory handler
85 static void nomem_fn(void)
90 static void (*lowMemFn)(void) = lowmem_fn; /* default low memory handler */
91 static void (*noMemFn)(void) = nomem_fn; /* default no memory handler */
93 /* begin/end marker signature */
94 static const size_t DEADBEEF = 0xdeadbeef;
95 static size_t byteCount = 0; /* count of currently allocated bytes */
96 static size_t blockCount = 0; /* count of allocated blocks */
97 static size_t byteLimit = 0xffffffff; /* memory size limiter */
98 static BlkHdr* bhTab[HTABLE_SIZE]; /* hash table for allocated blocks */
99 static Location* locationList = 0; /* linked list of memory locations */
102 * fda_set_lowmem_handler - set handler for low memory conditions
103 * this will be called if malloc fails once
105 void fda_set_lowmem_handler(void (*fn)(void))
107 lowMemFn = (fn) ? fn : lowmem_fn;
111 * set_nomem_handler - set handler for no memory conditions
112 * The nomem_handler is called if lowMemFn returns and malloc fails a second
113 * time, the library will assert if lowMemFn is allowed to return
115 void fda_set_nomem_handler(void (*fn)(void))
117 noMemFn = (fn) ? fn : nomem_fn;
121 * fda_get_byte_count - returns the client memory allocated in bytes
123 size_t fda_get_byte_count(void)
129 * fda_get_block_count - returns the number of blocks allocated
131 size_t fda_get_block_count(void)
137 * findLocation - finds a location on the list, this
138 * only compares pointers so it should only be used with
139 * ANSI __FILE__ and __LINE__ macros.
141 static Location* findLocation(const char* file, int line)
143 Location* location = locationList;
144 for ( ; location; location = location->next) {
145 if (file == location->file && line == location->line)
152 * addLocation - adds a allocation location to the list
153 * returns a pointer to the new location
155 static Location* addLocation(const char* file, int line)
159 if ((location = (Location*) malloc(sizeof(Location))) != 0) {
160 location->next = locationList;
162 location->file = file;
163 location->line = line;
166 location->next->prev = location;
167 locationList = location;
173 * freeLocation - frees a file/line info location
175 static void freeLocation(Location* location)
177 assert(0 != location);
178 assert(0 == location->count);
180 if (0 != location->next)
181 location->next->prev = location->prev;
182 if (0 != location->prev)
183 location->prev->next = location->next;
185 locationList = location->next;
190 * hash_ptr - simple pointer hash function
192 static unsigned long hash_ptr(const void* p)
194 return ((unsigned long) p >> 3) % HTABLE_SIZE;
196 return (((unsigned long) p >> 3) ^ ~((unsigned long) p)) % HTABLE_SIZE;
197 return (((unsigned long) p >> 3) | ((unsigned long) p) << 3) % HTABLE_SIZE;
202 * find_blk_exhaustive - find a block by scanning the
203 * entire hash table. This function finds blocks that do not
204 * start at the pointer returned from Malloc.
206 static BlkHdr* find_blk_exhaustive(const void* p)
211 for (i = 0; i < HTABLE_SIZE; ++i) {
212 for (bh = bhTab[i]; bh; bh = bh->next) {
213 if (bh->buf <= p && BYTE_PTR(p) < (BYTE_PTR(bh->buf) + bh->size))
221 * fda_dump_hash - enumerate hash table link counts
223 void fda_dump_hash(void (*enumfn)(int, int))
227 for (i = 0; i < HTABLE_SIZE; ++i) {
229 for (bh = bhTab[i]; bh; bh = bh->next)
236 * find_blk - return the block struct associated with the
239 static BlkHdr* find_blk(const void* p)
241 BlkHdr* bh = bhTab[hash_ptr(p)];
242 for ( ; bh; bh = bh->next) {
246 return find_blk_exhaustive(p);
250 * make_blk - create a block header and add it to the hash table
252 static int make_blk(unsigned char* p, size_t size, Location* loc)
260 if ((bh = (BlkHdr*) malloc(sizeof(BlkHdr))) != 0) {
261 unsigned long h = hash_ptr(p);
266 bh->timestamp = time(0);
269 ++bh->location->count;
277 * free_blk - remove a block header and free it
279 static void free_blk(const void* p)
283 unsigned long h = hash_ptr(p);
285 for (bh = bhTab[h]; bh; bh = bh->next) {
290 bh_prev->next = bh->next;
296 * if bh is NULL p was not allocated here
299 assert(bh->location->count > 0);
300 if (--bh->location->count == 0)
301 freeLocation(bh->location);
303 byteCount -= bh->size;
306 SHRED_MEM(bh, sizeof(BlkHdr));
311 * update_blk - update block info, rehash if pointers are different,
312 * update location info if needed
314 static void update_blk(void* p, void* np, size_t size, const char* file, int line)
319 unsigned long h = hash_ptr(p);
322 * remove the old entry from the hash table
324 for (bh = bhTab[h]; bh; bh = bh->next) {
329 bh_prev->next = bh->next;
331 * put it back in the hash table at hash(np)
347 byteCount -= bh->size;
352 * update location info
354 if (bh->location->file != file || bh->location->line != line) {
355 if (--bh->location->count == 0)
356 freeLocation(bh->location);
357 if ((bh->location = findLocation(file, line)) == 0) {
358 if ((bh->location = addLocation(file, line)) == 0)
361 assert(0 != bh->location);
362 ++bh->location->count;
367 * fda_sizeof - returns the size of block of memory pointed to by p
369 size_t fda_sizeof(const void* p)
371 BlkHdr* bh = find_blk(p);
373 assert(p == bh->buf);
377 void fda_set_byte_limit(size_t limit)
383 * fda_clear_refs - clear referenced markers on all blocks
385 void fda_clear_refs(void)
390 for (i = 0; i < HTABLE_SIZE; ++i) {
391 for (bh = bhTab[i]; bh; bh = bh->next)
397 * fda_set_ref - mark block as referenced
399 void fda_set_ref(const void* p)
401 BlkHdr* bh = find_blk(p);
407 * fda_assert_refs - scan for all blocks and check for null
408 * ptrs and unreferenced (lost) blocks
410 void fda_assert_refs(void)
415 for (i = 0; i < HTABLE_SIZE; ++i) {
416 for (bh = bhTab[i]; bh; bh = bh->next) {
417 assert(0 != bh->buf && 0 < bh->size);
418 assert(1 == bh->ref);
424 * valid_ptr - returns true if p points to allocated memory and
425 * has at least size available
427 int valid_ptr(const void* p, size_t size)
435 * check that there are at least size bytes available from p
437 assert((BYTE_PTR(p) + size) <= (BYTE_PTR(bh->buf) + bh->size));
442 * fda_enum_locations - calls enumfn to list file, line, and count
443 * info for allocations, returns the number of locations found
445 int fda_enum_locations(void (*enumfn)(const char*, int, int))
450 for (location = locationList; location; location = location->next) {
451 (*enumfn)(location->file, location->line, location->count);
458 * fda_enum_leaks - scan hash table for leaks and call enumfn to
461 int fda_enum_leaks(void (*enumfn)(const char*, int, size_t, void*))
466 for (i = 0; i < HTABLE_SIZE; ++i) {
467 for (bh = bhTab[i]; bh; bh = bh->next) {
469 (*enumfn)(bh->location->file, bh->location->line, bh->size, bh->buf);
478 * fda_malloc - allocate size chunk of memory and create debug
481 void* fda_malloc(size_t size, const char* file, int line)
489 assert(sizeof(void*) == sizeof(size_t));
492 * memory limiter do not allocate more than byteLimit
494 if ((size + byteCount) > byteLimit)
498 * Make sure that there is enough room for prefix/postfix
499 * and we get an aligned buffer
501 blk_size = BASE_SIZE(size);
503 if ((p = malloc(blk_size)) == 0) {
505 if ((p = malloc(blk_size)) == 0)
509 * don't allow malloc to fail
513 * shred the memory and set bounds markers
515 SHRED_MEM(p, blk_size);
516 *((size_t*) p) = DEADBEEF;
517 *((size_t*) (BYTE_PTR(p) + blk_size - S_SIZE)) = DEADBEEF;
520 * find the location or create a new one
522 if (0 == (location = findLocation(file, line))) {
523 if (0 == (location = addLocation(file, line))) {
529 * don't allow noMemFn to return
531 assert(0 != location);
532 if (!make_blk(BYTE_PTR(p) + S_SIZE, size, location)) {
533 if (0 == location->count)
534 freeLocation(location);
540 * don't allow noMemFn to return
543 return (BYTE_PTR(p) + S_SIZE);
547 * fda_free - check chunk of memory for overruns and free it
549 void fda_free(void* p)
553 BlkHdr* bh = find_blk(p);
556 /* p already freed or not allocated? */
558 assert(p == bh->buf);
561 /* buffer underflow? */
562 assert(DEADBEEF == *((size_t*) bp));
565 * Note: it's possible to have up to 3 bytes of unchecked space
566 * between size and DEADBEEF
568 size = BASE_SIZE(bh->size);
569 assert(DEADBEEF == *((size_t*)(BYTE_PTR(bp) + size - S_SIZE)));
578 * fda_realloc - resize a buffer, force reallocation if new size is
579 * larger than old size
581 void* fda_realloc(void* p, size_t size, const char* file, int line)
587 * don't allow malloc or free through realloc
591 old_size = fda_sizeof(p);
594 SHRED_MEM(BYTE_PTR(p) + size, old_size - size);
595 else if (size > old_size) {
596 void* t = fda_malloc(size, __FILE__, __LINE__);
597 memmove(t, p, old_size);
601 blk_size = BASE_SIZE(size);
603 if ((np = realloc(BASE_PTR(p), blk_size)) == 0) {
605 if ((np = realloc(BASE_PTR(p), blk_size)) == 0)
609 * don't allow noMemFn to return
613 *((size_t*)(BYTE_PTR(np) + blk_size - S_SIZE)) = DEADBEEF;
615 np = BYTE_PTR(np) + S_SIZE;
616 update_blk(p, np, size, file, line);
621 SHRED_MEM(BYTE_PTR(np) + old_size, size - old_size);
627 * fda_calloc - allocate 0 initialized buffer nelems * size length
629 void* fda_calloc(size_t nelems, size_t size, const char* file, int line)
636 p = fda_malloc(size, file, line);
642 * fda_strdup - duplicates a string returns newly allocated string
644 char* fda_strdup(const char* src, const char* file, int line)
648 p = (char*) fda_malloc(strlen(src) + 1, file, line);
653 #endif /* !defined(NDEBUG) */