ircd/fda.c

   1 /*
   2  * fda.c - Free Debug Allocator
   3  * Copyright (C) 1997 Thomas Helvey <tomh@inxpress.net>
   4  *
   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)
   8  * any later version.
   9  *
  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.
  14  *
  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.
  18  */
  19 /*
  20  * NOTE: Do not include fda.h here
  21  */
  22 #include "config.h"
  23
  24 #include <assert.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <time.h>
  28
  29 #if defined(MDEBUG)
  30
  31 #ifndef HTABLE_SIZE
  32 #define HTABLE_SIZE 65539
  33 /* #define HTABLE_SIZE 16339 */ /* prime around 16K */
  34 /* #define HTABLE_SIZE 251 */
  35 #endif
  36
  37 #define SHRED_BYTE 0xcd
  38 #if 0
  39 #if defined(_i386)
  40 #define SHRED_BYTE 0xcd
  41 #else
  42 #define SHRED_BYTE 0xa3
  43 #endif /* !_i386 */
  44 #endif /* 0 */
  45
  46 #define SHRED_MEM(a,s)  memset((a), SHRED_BYTE, (s))
  47
  48 #define S_SIZE sizeof(size_t)
  49 #define BYTE_PTR(x) (unsigned char*)((x))
  50
  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)
  53
  54 struct Location {
  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 */
  60 };
  61
  62 struct BlkHdr {
  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 */
  69 };
  70
  71 typedef struct BlkHdr   BlkHdr;
  72 typedef struct Location Location;
  73
  74 /*
  75  * lowmem_fn - default low memory handler
  76  */
  77 static void lowmem_fn(void)
  78 {
  79   return;
  80 }
  81
  82 /*
  83  * nomem_fn - default no memory handler
  84  */
  85 static void nomem_fn(void)
  86 {
  87   exit(2);
  88 }
  89
  90 static void (*lowMemFn)(void) = lowmem_fn;  /* default low memory handler */
  91 static void (*noMemFn)(void)  = nomem_fn;   /* default no memory handler */
  92
  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 */
 100
 101 /*
 102  * fda_set_lowmem_handler - set handler for low memory conditions
 103  *  this will be called if malloc fails once
 104  */
 105 void fda_set_lowmem_handler(void (*fn)(void))
 106 {
 107   lowMemFn = (fn) ? fn : lowmem_fn;
 108 }
 109
 110 /*
 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
 114  */
 115 void fda_set_nomem_handler(void (*fn)(void))
 116 {
 117   noMemFn = (fn) ? fn : nomem_fn;
 118 }
 119
 120 /*
 121  * fda_get_byte_count - returns the client memory allocated in bytes
 122  */
 123 size_t fda_get_byte_count(void)
 124 {
 125   return byteCount;
 126 }
 127
 128 /*
 129  * fda_get_block_count - returns the number of blocks allocated
 130  */
 131 size_t fda_get_block_count(void)
 132 {
 133   return blockCount;
 134 }
 135
 136 /*
 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.
 140  */
 141 static Location* findLocation(const char* file, int line)
 142 {
 143   Location* location = locationList;
 144   for ( ; location; location = location->next) {
 145     if (file == location->file && line == location->line)
 146       return location;
 147   }
 148   return 0;
 149 }
 150
 151 /*
 152  * addLocation - adds a allocation location to the list
 153  * returns a pointer to the new location
 154  */
 155 static Location* addLocation(const char* file, int line)
 156 {
 157   Location* location;
 158   assert(0 != file);
 159   if ((location = (Location*) malloc(sizeof(Location))) != 0) {
 160     location->next = locationList;
 161     location->prev = 0;
 162     location->file = file;
 163     location->line = line;
 164     location->count = 0;
 165     if (location->next)
 166       location->next->prev = location;
 167     locationList = location;
 168   }
 169   return location;
 170 }
 171
 172 /*
 173  * freeLocation - frees a file/line info location
 174  */
 175 static void freeLocation(Location* location)
 176 {
 177   assert(0 != location);
 178   assert(0 == location->count);
 179
 180   if (0 != location->next)
 181     location->next->prev = location->prev;
 182   if (0 != location->prev)
 183     location->prev->next = location->next;
 184   else
 185     locationList = location->next;
 186   free(location);
 187 }
 188
 189 /*
 190  * hash_ptr - simple pointer hash function
 191  */
 192 static unsigned long hash_ptr(const void* p)
 193 {
 194   return ((unsigned long) p >> 3) % HTABLE_SIZE;
 195 #if 0
 196   return (((unsigned long) p >> 3) ^ ~((unsigned long) p)) % HTABLE_SIZE;
 197   return (((unsigned long) p >> 3) | ((unsigned long) p) << 3) % HTABLE_SIZE;
 198 #endif
 199 }
 200
 201 /*
 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.
 205  */
 206 static BlkHdr* find_blk_exhaustive(const void* p)
 207 {
 208   int i;
 209   BlkHdr* bh;
 210
 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))
 214         return bh;
 215     }
 216   }
 217   return 0;
 218 }
 219
 220 /*
 221  * fda_dump_hash - enumerate hash table link counts
 222  */
 223 void fda_dump_hash(void (*enumfn)(int, int))
 224 {
 225   int i = 0;
 226   BlkHdr* bh;
 227   for (i = 0; i < HTABLE_SIZE; ++i) {
 228     int count = 0;
 229     for (bh = bhTab[i]; bh; bh = bh->next)
 230       ++count;
 231     (*enumfn)(i, count);
 232   }
 233 }
 234
 235 /*
 236  * find_blk - return the block struct associated with the
 237  * pointer p.
 238  */
 239 static BlkHdr* find_blk(const void* p)
 240 {
 241   BlkHdr* bh = bhTab[hash_ptr(p)];
 242   for ( ; bh; bh = bh->next) {
 243     if (p == bh->buf)
 244       return bh;
 245   }
 246   return find_blk_exhaustive(p);
 247 }
 248
 249 /*
 250  * make_blk - create a block header and add it to the hash table
 251  */
 252 static int make_blk(unsigned char* p, size_t size, Location* loc)
 253 {
 254   BlkHdr* bh;
 255
 256   assert(0 != p);
 257   assert(0 < size);
 258   assert(0 != loc);
 259
 260   if ((bh = (BlkHdr*) malloc(sizeof(BlkHdr))) != 0) {
 261     unsigned long h = hash_ptr(p);
 262     bh->ref       = 0;
 263     bh->buf       = p;
 264     bh->size      = size;
 265     bh->location  = loc;
 266     bh->timestamp = time(0);
 267     bh->next      = bhTab[h];
 268     bhTab[h]      = bh;
 269     ++bh->location->count;
 270     byteCount += size;
 271     ++blockCount;
 272   }
 273   return (0 != bh);
 274 }
 275
 276 /*
 277  * free_blk - remove a block header and free it
 278  */
 279 static void free_blk(const void* p)
 280 {
 281   BlkHdr* bh_prev = 0;
 282   BlkHdr* bh;
 283   unsigned long h = hash_ptr(p);
 284
 285   for (bh = bhTab[h]; bh; bh = bh->next) {
 286     if (p == bh->buf) {
 287       if (0 == bh_prev)
 288         bhTab[h] = bh->next;
 289       else
 290         bh_prev->next = bh->next;
 291       break;
 292     }
 293     bh_prev = bh;
 294   }
 295   /*
 296    * if bh is NULL p was not allocated here
 297    */
 298   assert(0 != bh);
 299   assert(bh->location->count > 0);
 300   if (--bh->location->count == 0)
 301     freeLocation(bh->location);
 302
 303   byteCount -= bh->size;
 304   --blockCount;
 305
 306   SHRED_MEM(bh, sizeof(BlkHdr));
 307   free(bh);
 308 }
 309
 310 /*
 311  * update_blk - update block info, rehash if pointers are different,
 312  * update location info if needed
 313  */
 314 static void update_blk(void* p, void* np, size_t size, const char* file, int line)
 315 {
 316   BlkHdr* bh;
 317   if (p != np) {
 318     BlkHdr* bh_prev = 0;
 319     unsigned long h = hash_ptr(p);
 320
 321     /*
 322      * remove the old entry from the hash table
 323      */
 324     for (bh = bhTab[h]; bh; bh = bh->next) {
 325       if (p == bh->buf) {
 326         if (0 == bh_prev)
 327           bhTab[h] = bh->next;
 328         else
 329           bh_prev->next = bh->next;
 330         /*
 331          * put it back in the hash table at hash(np)
 332          */
 333         h = hash_ptr(np);
 334         bh->next = bhTab[h];
 335         bhTab[h] = bh;
 336         break;
 337       }
 338       bh_prev = bh;
 339     }
 340   }
 341   else
 342     bh = find_blk(p);
 343   /*
 344    * invalid ptr?
 345    */
 346   assert(0 != bh);
 347   byteCount -= bh->size;
 348   byteCount += size;
 349   bh->buf = np;
 350   bh->size = size;
 351   /*
 352    * update location info
 353    */
 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)
 359         noMemFn();
 360     }
 361     assert(0 != bh->location);
 362     ++bh->location->count;
 363   }
 364 }
 365
 366 /*
 367  * fda_sizeof - returns the size of block of memory pointed to by p
 368  */
 369 size_t fda_sizeof(const void* p)
 370 {
 371   BlkHdr* bh = find_blk(p);
 372   assert(0 != bh);
 373   assert(p == bh->buf);
 374   return bh->size;
 375 }
 376
 377 void fda_set_byte_limit(size_t limit)
 378 {
 379   byteLimit = limit;
 380 }
 381
 382 /*
 383  * fda_clear_refs - clear referenced markers on all blocks
 384  */
 385 void fda_clear_refs(void)
 386 {
 387   int i;
 388   BlkHdr* bh;
 389
 390   for (i = 0; i < HTABLE_SIZE; ++i) {
 391     for (bh = bhTab[i]; bh; bh = bh->next)
 392       bh->ref = 0;
 393   }
 394 }
 395
 396 /*
 397  * fda_set_ref - mark block as referenced
 398  */
 399 void fda_set_ref(const void* p)
 400 {
 401   BlkHdr* bh = find_blk(p);
 402   assert(0 != bh);
 403   bh->ref = 1;
 404 }
 405
 406 /*
 407  * fda_assert_refs - scan for all blocks and check for null
 408  * ptrs and unreferenced (lost) blocks
 409  */
 410 void fda_assert_refs(void)
 411 {
 412   int i;
 413   BlkHdr* bh;
 414
 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);
 419     }
 420   }
 421 }
 422
 423 /*
 424  * valid_ptr - returns true if p points to allocated memory and
 425  * has at least size available
 426  */
 427 int valid_ptr(const void* p, size_t size)
 428 {
 429   BlkHdr* bh;
 430   assert(0 != p);
 431   assert(0 < size);
 432
 433   bh = find_blk(p);
 434   /*
 435    * check that there are at least size bytes available from p
 436    */
 437   assert((BYTE_PTR(p) + size) <= (BYTE_PTR(bh->buf) + bh->size));
 438   return 1;
 439 }
 440
 441 /*
 442  * fda_enum_locations - calls enumfn to list file, line, and count
 443  * info for allocations, returns the number of locations found
 444  */
 445 int fda_enum_locations(void (*enumfn)(const char*, int, int))
 446 {
 447   int count = 0;
 448   Location* location;
 449   assert(0 != enumfn);
 450   for (location = locationList; location; location = location->next) {
 451     (*enumfn)(location->file, location->line, location->count);
 452     ++count;
 453   }
 454   return count;
 455 }
 456
 457 /*
 458  * fda_enum_leaks - scan hash table for leaks and call enumfn to
 459  * report them.
 460  */
 461 int fda_enum_leaks(void (*enumfn)(const char*, int, size_t, void*))
 462 {
 463   int count = 0;
 464   BlkHdr* bh;
 465   int i;
 466   for (i = 0; i < HTABLE_SIZE; ++i) {
 467     for (bh = bhTab[i]; bh; bh = bh->next) {
 468       if (0 == bh->ref) {
 469         (*enumfn)(bh->location->file, bh->location->line, bh->size, bh->buf);
 470         ++count;
 471       }
 472     }
 473   }
 474   return count;
 475 }
 476
 477 /*
 478  * fda_malloc - allocate size chunk of memory and create debug
 479  * records for it.
 480  */
 481 void* fda_malloc(size_t size, const char* file, int line)
 482 {
 483   void* p;
 484   size_t blk_size;
 485   Location* location;
 486
 487   assert(0 < size);
 488   assert(0 != file);
 489   assert(sizeof(void*) == sizeof(size_t));
 490
 491   /*
 492    * memory limiter do not allocate more than byteLimit
 493    */
 494   if ((size + byteCount) > byteLimit)
 495     return 0;
 496
 497   /*
 498    * Make sure that there is enough room for prefix/postfix
 499    * and we get an aligned buffer
 500    */
 501   blk_size = BASE_SIZE(size);
 502
 503   if ((p = malloc(blk_size)) == 0) {
 504     lowMemFn();
 505     if ((p = malloc(blk_size)) == 0)
 506       noMemFn();
 507   }
 508   /*
 509    * don't allow malloc to fail
 510    */
 511   assert(0 != p);
 512   /*
 513    * shred the memory and set bounds markers
 514    */
 515   SHRED_MEM(p, blk_size);
 516   *((size_t*) p) = DEADBEEF;
 517   *((size_t*) (BYTE_PTR(p) + blk_size - S_SIZE)) = DEADBEEF;
 518
 519   /*
 520    * find the location or create a new one
 521    */
 522   if (0 == (location = findLocation(file, line))) {
 523     if (0 == (location = addLocation(file, line))) {
 524       free(p);
 525       noMemFn();
 526     }
 527   }
 528   /*
 529    * don't allow noMemFn to return
 530    */
 531   assert(0 != location);
 532   if (!make_blk(BYTE_PTR(p) + S_SIZE, size, location)) {
 533     if (0 == location->count)
 534       freeLocation(location);
 535     free(p);
 536     p = 0;
 537     noMemFn();
 538   }
 539   /*
 540    * don't allow noMemFn to return
 541    */
 542   assert(0 != p);
 543   return (BYTE_PTR(p) + S_SIZE);
 544 }
 545
 546 /*
 547  * fda_free - check chunk of memory for overruns and free it
 548  */
 549 void fda_free(void* p)
 550 {
 551   if (p) {
 552     size_t size;
 553     BlkHdr* bh = find_blk(p);
 554     void*   bp;
 555
 556     /* p already freed or not allocated? */
 557     assert(0 != bh);
 558     assert(p == bh->buf);
 559
 560     bp = BASE_PTR(p);
 561     /* buffer underflow? */
 562     assert(DEADBEEF == *((size_t*) bp));
 563     /*
 564      * buffer overflow?
 565      * Note: it's possible to have up to 3 bytes of unchecked space
 566      * between size and DEADBEEF
 567      */
 568     size = BASE_SIZE(bh->size);
 569     assert(DEADBEEF == *((size_t*)(BYTE_PTR(bp) + size - S_SIZE)));
 570     SHRED_MEM(bp, size);
 571
 572     free_blk(p);
 573     free(bp);
 574   }
 575 }
 576
 577 /*
 578  * fda_realloc - resize a buffer, force reallocation if new size is
 579  * larger than old size
 580  */
 581 void* fda_realloc(void* p, size_t size, const char* file, int line)
 582 {
 583   void* np;
 584   size_t old_size;
 585   size_t blk_size;
 586   /*
 587    * don't allow malloc or free through realloc
 588    */
 589   assert(0 != p);
 590   assert(0 < size);
 591   old_size = fda_sizeof(p);
 592
 593   if (size < old_size)
 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);
 598     fda_free(p);
 599     p = t;
 600   }
 601   blk_size = BASE_SIZE(size);
 602
 603   if ((np = realloc(BASE_PTR(p), blk_size)) == 0) {
 604     lowMemFn();
 605     if ((np = realloc(BASE_PTR(p), blk_size)) == 0)
 606       noMemFn();
 607   }
 608   /*
 609    * don't allow noMemFn to return
 610    */
 611   assert(0 != np);
 612
 613   *((size_t*)(BYTE_PTR(np) + blk_size - S_SIZE)) = DEADBEEF;
 614
 615   np = BYTE_PTR(np) + S_SIZE;
 616   update_blk(p, np, size, file, line);
 617   /*
 618    * shred tail
 619    */
 620   if (size > old_size)
 621     SHRED_MEM(BYTE_PTR(np) + old_size, size - old_size);
 622
 623   return np;
 624 }
 625
 626 /*
 627  * fda_calloc - allocate 0 initialized buffer nelems * size length
 628  */
 629 void* fda_calloc(size_t nelems, size_t size, const char* file, int line)
 630 {
 631   void* p;
 632   assert(0 < nelems);
 633   assert(0 < size);
 634   assert(0 != file);
 635   size *= nelems;
 636   p = fda_malloc(size, file, line);
 637   memset(p, 0, size);
 638   return p;
 639 }
 640
 641 /*
 642  * fda_strdup - duplicates a string returns newly allocated string
 643  */
 644 char* fda_strdup(const char* src, const char* file, int line)
 645 {
 646   char* p;
 647   assert(0 != src);
 648   p = (char*) fda_malloc(strlen(src) + 1, file, line);
 649   strcpy(p, src);
 650   return p;
 651 }
 652
 653 #endif /* defined(MDEBUG) */
 654