common/memory.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Copyright (c) 2000-2014 Ericsson Telecom AB
   3 // All rights reserved. This program and the accompanying materials
   4 // are made available under the terms of the Eclipse Public License v1.0
   5 // which accompanies this distribution, and is available at
   6 // http://www.eclipse.org/legal/epl-v10.html
   7 ///////////////////////////////////////////////////////////////////////////////
   8 #include "memory.h"
   9
  10 #undef Malloc
  11 #undef Realloc
  12 #undef Free
  13 #undef mprintf
  14 #undef mprintf_va_list
  15 #undef mputprintf
  16 #undef mputprintf_va_list
  17 #undef memptystr
  18 #undef mcopystr
  19 #undef mcopystrn
  20 #undef mputstr
  21 #undef mputc
  22
  23
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <stdarg.h>
  27 #include <string.h>
  28 #include <errno.h>
  29 #include <ctype.h>
  30 #include <unistd.h>
  31
  32 /** @def va_copy
  33  * work-around for missing va_copy() in GCC
  34  */
  35 #if defined(__GNUC__) && !defined(va_copy)
  36 # ifdef __va_copy
  37 #  define va_copy(dest, src) __va_copy(dest, src)
  38 # else
  39 #  define va_copy(dest, src) (dest) = (src)
  40 # endif
  41 #endif
  42
  43 /** Initial buffer size for mprintf */
  44 #define BUFSIZE 1024
  45
  46 /** @def MEMORY_DEBUG_ADDRESS
  47  *
  48  * If you want to catch memory management functions (malloc, realloc,
  49  * free) which operate on a given address, define this macro and set
  50  * memory_debug_address to the address you want to monitor.
  51  *
  52  * @note This macro has no effect if \c MEMORY_DEBUG is not defined
  53  */
  54 #ifdef DOXYGEN_SPECIAL
  55 /* Make the macro visible to Doxygen */
  56 #define MEMORY_DEBUG_ADDRESS
  57 #endif
  58
  59 #ifdef MEMORY_DEBUG_ADDRESS
  60 /** @brief Memory checkpoint address. */
  61 void *memory_debug_address = NULL;
  62
  63 /** @brief Memory checkpoint ordinal. */
  64 size_t memory_debug_ordinal = (size_t)-1;
  65 #endif
  66
  67 /**
  68  *  @name Number of memory allocations and frees performed.
  69  *  @{
  70  *  @note These are tracked even without MEMORY_DEBUG.
  71  */
  72 static size_t malloc_count = 0, free_count = 0;
  73 /** @} */
  74
  75 /**
  76  * If preprocessor symbol \c MEMORY_DEBUG is defined the memory
  77  * management routines do some self-checks against improper use. This
  78  * implies extra memory usage and significant performance penalty.
  79  */
  80 #ifdef MEMORY_DEBUG
  81
  82 #define FILENAME_FORMAT "%s:%d: "
  83
  84 /* Currently allocated memory amount, peak, and number of allocations */
  85 static size_t allocated_size = 0, peak_size = 0;
  86 static unsigned int alloc_count = 0;
  87 /* Sum of all the allocated amounts */
  88 static unsigned long long total_allocated = 0;
  89
  90 typedef struct memory_block_struct {
  91     size_t size;
  92     struct memory_block_struct *prev, *next;
  93     const char *filename; /* pointer to string literal */
  94     int lineno;
  95     unsigned int ordinal; /* The ordinal which uniquely identifies this allocation */
  96     void *magic; /* only to reserve some place for the magic guard */
  97     double begin; /* beginning of useful memory with proper alignment */
  98 } memory_block;
  99
 100 static memory_block *list_head = NULL, *list_tail = NULL;
 101
 102 static void add_to_list(memory_block *block_ptr)
 103 {
 104     block_ptr->prev = list_tail;
 105     block_ptr->next = NULL;
 106     if (list_tail != NULL) list_tail->next = block_ptr;
 107     else list_head = block_ptr;
 108     list_tail = block_ptr;
 109 }
 110
 111 static void remove_from_list(memory_block *block_ptr)
 112 {
 113     if (block_ptr->prev != NULL)
 114         block_ptr->prev->next = block_ptr->next;
 115     else list_head = block_ptr->next;
 116     if (block_ptr->next != NULL)
 117         block_ptr->next->prev = block_ptr->prev;
 118     else list_tail = block_ptr->prev;
 119 }
 120
 121 /* Layout of memory (allocated in one chunk)
 122  * +----------+ <--- block_ptr
 123  * | size     |
 124  * +----------+
 125  * | prev     |
 126  * +----------+
 127  * | next     |
 128  * +----------+
 129  * | filename |
 130  * +----------+
 131  * | ordinal  |
 132  * +----------+
 133  * | magic    |
 134  * +----------+  +-----------+
 135  * | begin    |  | user data |
 136  * +----------+  |           |
 137  *                ...........
 138  *               |           |
 139  * +-----------+ +-----------+
 140  * | end magic |
 141  * +-----------+
 142  *
 143  *
 144  * The magic values initially contain the value of block_ptr.
 145  * When the block is freed, a bit-flipped value is written instead.
 146  * During realloc and free, the magic values are checked to match block_ptr.
 147  * If they don't, the a memory overrun or underrun has occurred
 148  * (except if the magic value happens to match the bit-flipped block_ptr,
 149  * in which case it's likely a double-free).
 150  */
 151
 152 static void set_magic_values(memory_block *block_ptr)
 153 {
 154     unsigned char *ptr = (unsigned char*)&block_ptr->begin;
 155     memcpy(&block_ptr->magic, &block_ptr, sizeof(block_ptr));
 156     memcpy(ptr + block_ptr->size, &block_ptr, sizeof(block_ptr));
 157 }
 158
 159 static void check_magic_values(const char *filename, int line,
 160   memory_block *block_ptr, int is_realloc)
 161 {
 162     void *inv_ptr = (void*)(~(size_t)block_ptr);
 163     unsigned char *ptr = (unsigned char*)&block_ptr->begin;
 164     /* compare the magic */
 165     if (memcmp(&block_ptr->magic, &block_ptr, sizeof(block_ptr))) {
 166         /* mismatch! */
 167         const char *err_str;
 168         if (memcmp(&block_ptr->magic, &inv_ptr, sizeof(inv_ptr)))
 169             err_str = "memory corruption";
 170         else err_str = "duplicate free/realloc";
 171         if (filename) {
 172             fprintf(stderr, FILENAME_FORMAT, filename, line);
 173         }
 174         fprintf(stderr, "Fatal error: %s detected at block begin when %s "
 175             "pointer %p.\n", err_str, is_realloc ? "reallocating" : "freeing",
 176             ptr);
 177         if (block_ptr->filename) fprintf(stderr,
 178           FILENAME_FORMAT "Last freed here.\n", block_ptr->filename, block_ptr->lineno);
 179         abort();
 180     }
 181     memcpy(&block_ptr->magic, &inv_ptr, sizeof(inv_ptr));/*invert magic*/
 182     if (memcmp(ptr + block_ptr->size, &block_ptr, sizeof(block_ptr))) {
 183         if (filename) {
 184             fprintf(stderr, FILENAME_FORMAT, filename, line);
 185         }
 186         fprintf(stderr, "Fatal error: memory corruption detected "
 187             "at block end when %s pointer %p.\n",
 188             is_realloc ? "reallocating" : "freeing", ptr);
 189         if (block_ptr->filename) fprintf(stderr,
 190           FILENAME_FORMAT "Last freed here.\n", block_ptr->filename, block_ptr->lineno);
 191         abort();
 192     }
 193     memcpy(ptr + block_ptr->size, &inv_ptr, sizeof(inv_ptr));
 194     block_ptr->filename = filename;
 195     block_ptr->lineno   = line;
 196 }
 197
 198 /** @def MEMORY_DEBUG_FREE
 199  *  @brief Enable checking for uses of unallocated/deallocated memory areas.
 200  *
 201  * If preprocessor symbol \c MEMORY_DEBUG_FREE is defined the memory
 202  * management routines can verify that unused and deallocated memory areas
 203  * are not written accidentally by the program after calling \a Free().
 204  * This verification can be done using functions \a check_mem_leak() or
 205  * \a check_mem_corrupt().
 206  *
 207  * Note: This functionality can significantly increase the memory requirements
 208  * of the program since the deallocated blocks cannot be recycled. They are
 209  * not returned to the system using \a free() until the end of the program run.
 210  */
 211 #ifdef DOXYGEN_SPECIAL
 212 /* Make the macro visible to Doxygen */
 213 #define MEMORY_DEBUG_FREE
 214 #endif
 215
 216 #ifdef MEMORY_DEBUG_FREE
 217
 218 static memory_block *free_list_head = NULL, *free_list_tail = NULL;
 219
 220 static void add_to_free_list(memory_block *block_ptr)
 221 {
 222     block_ptr->prev = free_list_tail;
 223     block_ptr->next = NULL;
 224     if (free_list_tail != NULL) free_list_tail->next = block_ptr;
 225     else free_list_head = block_ptr;
 226     free_list_tail = block_ptr;
 227 }
 228
 229 static void check_free_list(void)
 230 {
 231     memory_block *block_ptr = free_list_head;
 232     size_t counter = 0;
 233     while (block_ptr != NULL) {
 234         void *inv_ptr = (void*)(~(size_t)block_ptr);
 235         unsigned char *ptr = (unsigned char*)&block_ptr->begin;
 236         size_t i;
 237         if (memcmp(&block_ptr->magic, &inv_ptr, sizeof(inv_ptr))) {
 238             fprintf(stderr, "Fatal error: memory corruption detected in front "
 239                 "of freed pointer %p\n", ptr);
 240             abort();
 241         }
 242         for (i = 0; i < block_ptr->size; i++) {
 243             if (ptr[i] != 0xAA) {
 244                 fprintf(stderr, "Fatal error: memory overwriting detected in "
 245                     "deallocated area: base pointer: %p, offset: %u, data "
 246                     "written: %02X\n", ptr, i, ptr[i]);
 247                 abort();
 248             }
 249         }
 250         if (memcmp(ptr + block_ptr->size, &inv_ptr, sizeof(inv_ptr))) {
 251             fprintf(stderr, "Fatal error: memory corruption detected at the "
 252                 "end of freed pointer %p\n", ptr);
 253             abort();
 254         }
 255         block_ptr = block_ptr->next;
 256         counter++;
 257     }
 258     fprintf(stderr, "%u deallocated memory block%s OK\n", counter,
 259         counter > 1 ? "s are" : " is");
 260 }
 261
 262 static void release_free_blocks(void)
 263 {
 264     memory_block *block_ptr = free_list_head;
 265     while (block_ptr != NULL) {
 266         memory_block *next_ptr = block_ptr->next;
 267         free(block_ptr);
 268         block_ptr = next_ptr;
 269     }
 270     free_list_head = NULL;
 271     free_list_tail = NULL;
 272 }
 273 #endif
 274 /* MEMORY_DEBUG_FREE */
 275
 276 #ifdef MEMORY_DEBUG_ADDRESS
 277 /** Check the address and the ordinal of the allocation against the checkpoints
 278  *
 279  * If the address or the ordinal matches, a line is printed to the standard
 280  * error. Breakpoints can be set on the printf to trigger when the watched
 281  * allocation happens.
 282  *
 283  * @param block_ptr pointer to a memory block structure which is being
 284  * allocated/reallocated/freed
 285  * @param oper the actual operation: 0=Malloc, 1=Realloc, 2=Free
 286  */
 287 static void check_memory_address(memory_block *block_ptr, int oper)
 288 {
 289   void *ptr = (unsigned char*)&block_ptr->begin;
 290   if (ptr == memory_debug_address)
 291   {
 292     if (block_ptr->filename) {
 293       fprintf(stderr, FILENAME_FORMAT, block_ptr->filename, block_ptr->lineno);
 294     }
 295     fprintf(stderr, "MEMDEBUG: returning pointer %p while %sing memory.\n",
 296             ptr, oper==0?"allocat":oper==1?"reallocat":"free");
 297   }
 298   if (block_ptr->ordinal == memory_debug_ordinal) {
 299     if (block_ptr->filename) {
 300       fprintf(stderr, FILENAME_FORMAT, block_ptr->filename, block_ptr->lineno);
 301     }
 302     fprintf(stderr, "MEMDEBUG: returning ordinal %lu while %sing memory.\n",
 303             (unsigned long)block_ptr->ordinal,
 304             oper==0 ? "allocat" : (oper==1 ? "reallocat" : "free"));
 305   }
 306 }
 307 #endif
 308 /* MEMORY_DEBUG_ADDRESS */
 309
 310 /*#define FATAL_ERROR_INTERNAL(f,l,s) fatal_error(f,l,s)*/
 311 #define MALLOC_INTERNAL(f,l,s) Malloc_dbg(f,l,s)
 312 #define MEMPTYSTR_INTERNAL(f,l) memptystr_dbg(f,l)
 313 #define MCOPYSTR_INTERNAL(f,l,s) mcopystr_dbg(f,l,s)
 314 #define REALLOC_INTERNAL(f,l,p,s) Realloc_dbg(f,l,p,s)
 315 #define FREE_INTERNAL(f,l,p) Free_dbg(f,l,p)
 316 #define MPRINTF_VA_LIST_INTERNAL(f,l,s,p) mprintf_va_list_dbg(f,l,s,p)
 317
 318 static const size_t offset = (unsigned char*)&(((memory_block*)NULL)->begin)
 319   - (unsigned char*)NULL;
 320
 321 static void extract_location(void *p, const char **fn, int *ln)
 322 {
 323     memory_block *block_ptr = NULL;
 324     block_ptr = (memory_block*)(void*)((unsigned char*)p - offset);
 325     *fn = block_ptr->filename;
 326     *ln = block_ptr->lineno;
 327 }
 328
 329 #else
 330 /* not MEMORY_DEBUG */
 331
 332 #define FATAL_ERROR_INTERNAL(f,l,s) fatal_error(s)
 333 #define MALLOC_INTERNAL(f,l,s) Malloc(s)
 334 #define MEMPTYSTR_INTERNAL(f,l) memptystr()
 335 #define MCOPYSTR_INTERNAL(f,l,s) mcopystr(s)
 336 #define REALLOC_INTERNAL(f,l,p,s) Realloc(p,s)
 337 #define FREE_INTERNAL(f,l,p) Free(p)
 338 #define MPRINTF_VA_LIST_INTERNAL(f,l,s,p) mprintf_va_list(s,p)
 339
 340 #define extract_location(p,f,l) ((void)p,(void)f,(void)l)
 341 #endif
 342
 343 /** Report a fatal error.
 344  *
 345  * @param size the number of bytes that could not be allocated
 346  *
 347  * This function does not return.
 348  */
 349 __attribute__ ((__noreturn__))
 350 static void fatal_error(
 351 #ifdef MEMORY_DEBUG
 352   const char *filename, int line,
 353 #endif
 354   size_t size)
 355 {
 356     const char *err_msg = strerror(errno);
 357 #ifdef MEMORY_DEBUG
 358     fprintf(stderr, FILENAME_FORMAT "Fatal error: cannot allocate %lu bytes"
 359         " of memory after allocating %lu bytes: ", filename, line,
 360         (unsigned long) size, (unsigned long) allocated_size);
 361 #else
 362     fprintf(stderr, "Fatal error: cannot allocate %lu bytes of memory: ",
 363         (unsigned long) size);
 364 #endif
 365     if (err_msg != NULL) fprintf(stderr, "%s. Exiting.\n", err_msg);
 366     else fprintf(stderr, "Unknown error (errno: %d). Exiting.\n", errno);
 367     exit(EXIT_FAILURE);
 368 }
 369
 370 #ifdef MEMORY_DEBUG
 371 void *Malloc(size_t size)
 372 {
 373   return Malloc_dbg(0,0,size);
 374 }
 375
 376 void *Malloc_dbg(const char *filename, int line, size_t size)
 377 #else
 378 void *Malloc(size_t size)
 379 #endif
 380 {
 381     if (size > 0) {
 382         void *ptr;
 383 #ifdef MEMORY_DEBUG
 384         memory_block *block_ptr;
 385         block_ptr = (memory_block*)malloc(sizeof(*block_ptr) -
 386             sizeof(block_ptr->begin) + size + sizeof(block_ptr));
 387         if (block_ptr == NULL) fatal_error(filename, line, size);
 388         block_ptr->filename = filename;
 389         block_ptr->lineno = line;
 390         block_ptr->size = size;
 391         add_to_list(block_ptr);
 392         set_magic_values(block_ptr);
 393         ptr = &block_ptr->begin;
 394         total_allocated += size;
 395         block_ptr->ordinal = alloc_count++;
 396         allocated_size += size;
 397 #ifdef MEMORY_DEBUG_ADDRESS
 398         check_memory_address(block_ptr, 0);
 399 #endif
 400         if (peak_size < allocated_size) peak_size = allocated_size;
 401 #else
 402         ptr = malloc(size);
 403         if (ptr == NULL) fatal_error(size);
 404 #endif
 405         malloc_count++;
 406         return ptr;
 407     } else return NULL;
 408 }
 409
 410 #ifdef MEMORY_DEBUG
 411
 412 void *Realloc(void *ptr, size_t size)
 413 {
 414   return Realloc_dbg(0,0,ptr,size);
 415 }
 416
 417 void *Realloc_dbg(const char *filename, int line, void *ptr, size_t size)
 418 #else
 419 void *Realloc(void *ptr, size_t size)
 420 #endif
 421 {
 422     if (ptr == NULL) return MALLOC_INTERNAL(filename, line, size);
 423     else if (size == 0) {
 424         FREE_INTERNAL(filename, line, ptr);
 425         return NULL;
 426     } else {
 427         void *new_ptr;
 428 #ifdef MEMORY_DEBUG
 429         memory_block *block_ptr = NULL;
 430         block_ptr = (memory_block*)(void*)((unsigned char*)ptr - offset);
 431         check_magic_values(filename, line, block_ptr, 1);
 432         remove_from_list(block_ptr);
 433         allocated_size -= block_ptr->size;
 434         if (size < block_ptr->size)
 435             memset((unsigned char*)ptr + size, 0x55, block_ptr->size - size);
 436         block_ptr = (memory_block*)realloc(block_ptr, sizeof(*block_ptr) -
 437             sizeof(block_ptr->begin) + sizeof(block_ptr) + size);
 438         if (block_ptr == NULL) fatal_error(filename, line, size);
 439 #ifdef MEMORY_DEBUG_ADDRESS
 440         check_memory_address(block_ptr, 1);
 441 #endif
 442         block_ptr->filename = filename;
 443         block_ptr->lineno = line;
 444         block_ptr->size = size;
 445         add_to_list(block_ptr);
 446         set_magic_values(block_ptr);
 447         new_ptr = &block_ptr->begin;
 448         total_allocated += size;
 449         alloc_count++;
 450         allocated_size += size;
 451         if (peak_size < allocated_size) peak_size = allocated_size;
 452 #else
 453         new_ptr = realloc(ptr, size);
 454         if (new_ptr == NULL) FATAL_ERROR_INTERNAL(filename, line, size);
 455 #endif
 456         return new_ptr;
 457     }
 458 }
 459
 460 #ifdef MEMORY_DEBUG
 461 void Free(void *ptr)
 462 {
 463   Free_dbg(0,0,ptr);
 464 }
 465
 466 extern void Free_dbg(const char *filename, int line, void *ptr)
 467 #else
 468 void Free(void *ptr)
 469 #endif
 470 {
 471     if (ptr != NULL) {
 472 #ifdef MEMORY_DEBUG
 473         memory_block *block_ptr = NULL;
 474         block_ptr = (memory_block*)(void*)((unsigned char*)ptr - offset);
 475 #ifdef MEMORY_DEBUG_ADDRESS
 476         check_memory_address(block_ptr, 2);
 477 #endif
 478         check_magic_values(filename, line, block_ptr, 0);
 479         remove_from_list(block_ptr);
 480         allocated_size -= block_ptr->size;
 481         memset(ptr, 0xAA, block_ptr->size);
 482 #ifdef MEMORY_DEBUG_FREE
 483         add_to_free_list(block_ptr);
 484 #else
 485         free(block_ptr);
 486 #endif
 487 #else
 488         free(ptr);
 489 #endif
 490         free_count++;
 491     }
 492 }
 493
 494 static const size_t maxprint = 32;
 495
 496 void check_mem_leak(const char *program_name)
 497 {
 498 #ifdef MEMORY_DEBUG
 499     fprintf(stderr, "%s(%d): memory usage statistics:\n"
 500         "total allocations: %lu\n"
 501         "malloc/new  calls: %lu\n"
 502         "free/delete calls: %lu\n"
 503         "peak memory usage: %lu bytes\n"
 504         "average block size: %g bytes\n",
 505         program_name, (int)getpid(),
 506         (unsigned long)alloc_count, (unsigned long)malloc_count,
 507         (unsigned long) free_count, (unsigned long) peak_size,
 508         (double)total_allocated / (double)alloc_count);
 509     if (list_head != NULL) {
 510         memory_block *block_ptr = list_head;
 511         size_t counter = 0;
 512         fprintf(stderr, "unallocated blocks:\n");
 513         do {
 514             if (block_ptr->filename != 0) {
 515                 fprintf(stderr, FILENAME_FORMAT,
 516                     block_ptr->filename, block_ptr->lineno);
 517             }
 518             fprintf(stderr, "\tMemory leak at %p, size %lu, ord %lu: ",
 519                 (void*)&block_ptr->begin, (unsigned long)block_ptr->size,
 520                 (unsigned long)block_ptr->ordinal);
 521             {
 522               const unsigned char * mm = (const unsigned char*)&block_ptr->begin;
 523               size_t x, limit = (block_ptr->size > maxprint) ? maxprint
 524                 : block_ptr->size;
 525               for (x = 0; x < limit; ++x) {
 526                 fputc( isprint(mm[x]) ? mm[x] : '.', stderr );
 527               }
 528               fputc(10, stderr);
 529             }
 530             block_ptr = block_ptr->next;
 531             counter++;
 532         } while (block_ptr != NULL);
 533         fprintf(stderr, "total unallocated: %lu bytes in %lu blocks\n",
 534             (unsigned long) allocated_size, (unsigned long) counter);
 535     }
 536 #ifdef MEMORY_DEBUG_FREE
 537     check_free_list();
 538     release_free_blocks();
 539 #endif
 540 #else
 541     if (malloc_count != free_count) {
 542         fprintf(stderr, "%s: warning: memory leakage detected.\n"
 543             "Total malloc calls: %lu, free calls: %lu\n"
 544             "Please submit a bug report including the current input file(s).\n",
 545             program_name,
 546             (unsigned long) malloc_count, (unsigned long) free_count);
 547     }
 548 #endif
 549 }
 550
 551 #ifdef MEMORY_DEBUG
 552 void check_mem_corrupt(const char *program_name)
 553 {
 554     size_t counter = 0;
 555     memory_block *block_ptr;
 556     fprintf(stderr, "%s: checking memory blocks for corruption\n",
 557         program_name);
 558     for (block_ptr = list_head; block_ptr != NULL; block_ptr = block_ptr->next)
 559     {
 560         unsigned char *ptr = (unsigned char*)&block_ptr->begin;
 561         if (memcmp(ptr - sizeof(block_ptr), &block_ptr, sizeof(block_ptr))) {
 562             fprintf(stderr, "Fatal error: memory corruption detected in front "
 563                 "of pointer %p\n", ptr);
 564             abort();
 565         }
 566         if (memcmp(ptr + block_ptr->size, &block_ptr, sizeof(block_ptr))) {
 567             fprintf(stderr, "Fatal error: memory corruption detected at the "
 568                 "end of pointer %p\n", ptr);
 569             abort();
 570         }
 571         counter++;
 572     }
 573     fprintf(stderr, "%s: %lu memory block%s OK\n", program_name,
 574         (unsigned long) counter, counter > 1 ? "s are" : " is");
 575 #ifdef MEMORY_DEBUG_FREE
 576     check_free_list();
 577 #endif
 578 }
 579 #endif
 580
 581 /** @brief Find the string length of an expstring_t
 582
 583 Finds the length of the C string pointed at by \p str, using some assumptions
 584 satisfied by an expstring_t.
 585
 586 @pre There is an offset from the beginning of the string which is a power
 587      of two, is within the buffer allocated for \p str and it contains '\\0'
 588 @pre The allocated buffer is at most twice as long as strlen(str)
 589 @pre \p bufsize is a valid pointer
 590
 591 @param [in]  str an expstring_t, must not be null
 592 @param [out] bufsize pointer to a location where the minimum buffer size
 593              (always a power of two) is deposited.
 594 @return      the length of \p str as a C string
 595 */
 596 static size_t fast_strlen(const expstring_t str, size_t *bufsize)
 597 {
 598     size_t size, min, max;
 599     /* Find the 0 byte at the end of the allocated buffer */
 600     for (size = 1; str[size - 1] != '\0'; size *= 2) {}
 601     *bufsize = size;
 602     if (size == 1) return 0;
 603     /* Binary search the second half of the buffer */
 604     min = size / 2 - 1;
 605     max = size - 1;
 606     while (max - min > 1) {
 607         size_t med = (min + max) / 2;
 608         if (str[med] != '\0') min = med;
 609         else max = med;
 610     }
 611     return max;
 612 }
 613
 614 /** @brief Find the first power of two which is greater than \p len
 615  *
 616  *  @param len the desired length
 617  *  @return a power of 2 greater than \p len
 618  *
 619  *  \p len is taken to be the number of characters needed. The returned value
 620  *  will always be greater than \p len to accommodate the null terminator.
 621  */
 622 static size_t roundup_size(size_t len)
 623 {
 624     size_t size;
 625     for (size = 1; len >= size; size *= 2);
 626     return size;
 627 }
 628
 629 #ifdef MEMORY_DEBUG
 630 expstring_t mprintf_va_list(const char *fmt, va_list pvar)
 631 {
 632   return mprintf_va_list_dbg(0,0,fmt,pvar);
 633 }
 634
 635 expstring_t mprintf_va_list_dbg(const char *filename, int line, const char *fmt, va_list pvar)
 636 #else
 637 expstring_t mprintf_va_list(const char *fmt, va_list pvar)
 638 #endif
 639 {
 640     char buf[BUFSIZE];
 641     expstring_t ptr;
 642     int len;
 643     size_t size, slen;
 644     va_list pvar2;
 645     va_copy(pvar2, pvar);
 646     len = vsnprintf(buf, BUFSIZE, fmt, pvar2);
 647     va_end(pvar2);
 648     if (len < 0) {
 649         /* The result does not fit in buf and we have no idea how many bytes
 650          * are needed (only old versions of libc may return -1).
 651          * Try to double the buffer size until it is large enough. */
 652         for (size = 2 * BUFSIZE; ; size *= 2) {
 653             ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 654             va_copy(pvar2, pvar);
 655             len = vsnprintf(ptr, size, fmt, pvar2);
 656             va_end(pvar2);
 657             if (len >= 0 && (size_t)len < size) break;
 658             FREE_INTERNAL(filename, line, ptr);
 659         }
 660         slen = (size_t)len;
 661     } else if (len >= BUFSIZE) {
 662         /* The result does not fit in buf, but we know how many bytes we need.
 663          * Allocate a buffer that is large enough and repeat vsnprintf() */
 664         slen = (size_t)len;
 665         size = roundup_size(slen);
 666         ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 667         /* use the original pvar since this is the last try */
 668         if (vsnprintf(ptr, size, fmt, pvar) != len) {
 669             perror("Fatal error: unexpected vsnprintf() return value");
 670             exit(EXIT_FAILURE);
 671         }
 672     } else {
 673         /* the complete result is in buf */
 674         slen = (size_t)len;
 675         size = roundup_size(slen);
 676         ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 677         memcpy(ptr, buf, slen);
 678     }
 679     memset(ptr + slen, '\0', size - slen);
 680     return ptr;
 681 }
 682
 683 #ifdef MEMORY_DEBUG
 684 expstring_t mprintf_dbg(const char *filename, int line, const char *fmt, ...)
 685 {
 686     expstring_t ptr;
 687     va_list pvar;
 688     va_start(pvar, fmt);
 689     ptr = mprintf_va_list_dbg(filename, line, fmt, pvar);
 690     va_end(pvar);
 691     return ptr;
 692 }
 693 #endif
 694
 695 expstring_t mprintf(const char *fmt, ...)
 696 {
 697     expstring_t ptr;
 698     va_list pvar;
 699     va_start(pvar, fmt);
 700     ptr = mprintf_va_list(fmt, pvar);
 701     va_end(pvar);
 702     return ptr;
 703 }
 704
 705 /* Tracking the origin: extracts the filename/line from the original allocation
 706  * of the expstring_t. */
 707 expstring_t mputprintf_va_list(expstring_t str, const char *fmt, va_list pvar)
 708 {
 709     const char *filename = NULL;
 710     int line = 0;
 711     if (str != NULL) {
 712         size_t size;
 713         size_t len = fast_strlen(str, &size);
 714         size_t rest = size - len;
 715         int len2;
 716         va_list pvar2;
 717         /* make a copy of pvar to allow re-use later */
 718         va_copy(pvar2, pvar);
 719         len2 = vsnprintf(str + len, rest, fmt, pvar2);
 720         va_end(pvar2);
 721         extract_location(str, &filename, &line);
 722         if (len2 < 0) {
 723             /* the result does not fit in buf and we have no idea how many
 724              * bytes are needed (only old versions of libc may return -1)
 725              * try to double the buffer size until it is large enough */
 726             size_t newlen;
 727             do {
 728                 size *= 2;
 729                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, size);
 730                 rest = size - len;
 731                 va_copy(pvar2, pvar);
 732                 len2 = vsnprintf(str + len, rest, fmt, pvar2);
 733                 va_end(pvar2);
 734             } while (len2 < 0 || (size_t)len2 >= rest);
 735             newlen = len + (size_t)len2;
 736             memset(str + newlen, '\0', size - newlen);
 737         } else if ((size_t)len2 >= rest) {
 738             /* there isn't enough space in buffer, but we know how many bytes
 739              * we need: reallocate the buffer to be large enough and repeat
 740              * vsnprintf() */
 741             size_t newlen = len + (size_t)len2;
 742             size = roundup_size(newlen);
 743             str = (expstring_t)REALLOC_INTERNAL(filename, line, str, size);
 744             /* use the original pvar since this is the last try */
 745             if (vsnprintf(str + len, size - len, fmt, pvar) != len2) {
 746                 perror("Fatal error: unexpected vsnprintf() return value");
 747                 exit(EXIT_FAILURE);
 748             }
 749             memset(str + newlen, '\0', size - newlen);
 750         }
 751     } else str = MPRINTF_VA_LIST_INTERNAL(filename, line, fmt, pvar);
 752     return str;
 753 }
 754
 755 expstring_t mputprintf(expstring_t str, const char *fmt, ...)
 756 {
 757     va_list pvar;
 758     va_start(pvar, fmt);
 759     str = mputprintf_va_list(str, fmt, pvar);
 760     va_end(pvar);
 761     return str;
 762 }
 763
 764 #ifdef MEMORY_DEBUG
 765 expstring_t memptystr(void)
 766 {
 767   return memptystr_dbg(0,0);
 768 }
 769
 770 expstring_t memptystr_dbg(const char *filename, int line)
 771 #else
 772 expstring_t memptystr(void)
 773 #endif
 774 {
 775     expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, 1);
 776     ptr[0] = '\0';
 777     return ptr;
 778 }
 779
 780 #ifdef MEMORY_DEBUG
 781 expstring_t mcopystr(const char *str)
 782 {
 783   return mcopystr_dbg(0,0,str);
 784 }
 785
 786 expstring_t mcopystr_dbg(const char *filename, int line, const char *str)
 787 #else
 788 expstring_t mcopystr(const char *str)
 789 #endif
 790 {
 791     if (str != NULL) {
 792         size_t len = strlen(str);
 793         size_t size = roundup_size(len);
 794         expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 795         memcpy(ptr, str, len);
 796         memset(ptr + len, '\0', size - len);
 797         return ptr;
 798     } else return MEMPTYSTR_INTERNAL(filename, line);
 799 }
 800
 801 #ifdef MEMORY_DEBUG
 802 expstring_t mcopystrn(const char *str, size_t len)
 803 {
 804   return mcopystrn_dbg(0,0,str, len);
 805 }
 806
 807 expstring_t mcopystrn_dbg(const char *filename, int line, const char *str,
 808   size_t len)
 809 #else
 810 expstring_t mcopystrn(const char *str, size_t len)
 811 #endif
 812 {
 813     if (len != 0 && str != NULL) {
 814         size_t size = roundup_size(len);
 815         expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 816         memcpy(ptr, str, len);
 817         memset(ptr + len, '\0', size - len);
 818         return ptr;
 819     } else return MEMPTYSTR_INTERNAL(filename, line);
 820 }
 821
 822 /* Tracking the origin: extracts the filename/line from the original allocation
 823  * of the expstring_t. */
 824 expstring_t mputstr(expstring_t str, const char *str2)
 825 {
 826     const char *filename = NULL;
 827     int line = 0;
 828     if (str2 != NULL) {
 829         if (str != NULL) {
 830             size_t size;
 831             size_t len = fast_strlen(str, &size);
 832             size_t len2 = strlen(str2);
 833             size_t newlen = len + len2;
 834             if (size <= newlen) {
 835                 size_t newsize = roundup_size(newlen);
 836                 extract_location(str, &filename, &line);
 837                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 838                 memset(str + newlen, '\0', newsize - newlen);
 839             }
 840             memcpy(str + len, str2, len2);
 841         } else str = MCOPYSTR_INTERNAL(filename, line, str2);
 842     }
 843     return str;
 844 }
 845
 846 /* Tracking the origin: extracts the filename/line from the original allocation
 847  * of the expstring_t. */
 848 expstring_t mputstrn(expstring_t str, const char *str2, size_t len2)
 849 {
 850     const char *filename = NULL;
 851     int line = 0;
 852     if (len2 != 0 && str2 != NULL) {
 853         if (str != NULL) {
 854             size_t size;
 855             size_t len = fast_strlen(str, &size);
 856             size_t newlen = len + len2;
 857             if (size <= newlen) {
 858                 size_t newsize = roundup_size(newlen);
 859                 extract_location(str, &filename, &line);
 860                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 861                 memset(str + newlen, '\0', newsize - newlen);
 862             }
 863             memcpy(str + len, str2, len2);
 864         } else str = MCOPYSTR_INTERNAL(filename, line, str2);
 865     }
 866     return str;
 867 }
 868
 869 /* Tracking the origin: extracts the filename/line from the original allocation
 870  * of the expstring_t. */
 871 expstring_t mputc(expstring_t str, char c)
 872 {
 873     const char *filename = NULL;
 874     int line = 0;
 875     if (str != NULL) {
 876         if (c != '\0') {
 877             size_t size;
 878             size_t len = fast_strlen(str, &size);
 879             if (size <= len + 1) {
 880                 extract_location(str, &filename, &line);
 881                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, 2 * size);
 882                 memset(str + size, '\0', size);
 883             }
 884             str[len] = c;
 885         }
 886     } else {
 887         if (c != '\0') {
 888             str = (expstring_t)MALLOC_INTERNAL(filename, line, 2);
 889             str[0] = c;
 890             str[1] = '\0';
 891         } else str = MEMPTYSTR_INTERNAL(filename, line);
 892     }
 893     return str;
 894 }
 895
 896 /* Tracking the origin: extracts the filename/line from the original allocation
 897  * of the expstring_t. */
 898 expstring_t mtruncstr(expstring_t str, size_t newlen)
 899 {
 900   const char *filename = NULL;
 901   int line = 0;
 902   if (str != NULL) {
 903     size_t size;
 904     size_t len = fast_strlen(str, &size);
 905     if (newlen < len) {
 906       size_t newsize = roundup_size(newlen);
 907       if (newsize < size) {
 908         extract_location(str, &filename, &line);
 909         str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 910       }
 911       memset(str + newlen, '\0', newsize - newlen);
 912     }
 913   }
 914   return str;
 915 }
 916
 917 size_t mstrlen(const expstring_t str)
 918 {
 919   if (str != NULL) {
 920     size_t size;
 921     return fast_strlen(str, &size);
 922   } else return 0;
 923 }
 924
 925 char * buildstr(int b) {
 926   if (b < 0 || b > 99) return NULL; /* invalid */
 927   if (b == 99) return memptystr(); /* empty string for full version */
 928   return mprintf("%02d", b);
 929 }