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