common/memory.c

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Copyright (c) 2000-2015 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 MCOPYSTRN_INTERNAL(f,l,s,l2) mcopystrn_dbg(f,l,s,l2)
 315 #define REALLOC_INTERNAL(f,l,p,s) Realloc_dbg(f,l,p,s)
 316 #define FREE_INTERNAL(f,l,p) Free_dbg(f,l,p)
 317 #define MPRINTF_VA_LIST_INTERNAL(f,l,s,p) mprintf_va_list_dbg(f,l,s,p)
 318
 319 static const size_t offset = (unsigned char*)&(((memory_block*)NULL)->begin)
 320   - (unsigned char*)NULL;
 321
 322 static void extract_location(void *p, const char **fn, int *ln)
 323 {
 324     memory_block *block_ptr = NULL;
 325     block_ptr = (memory_block*)(void*)((unsigned char*)p - offset);
 326     *fn = block_ptr->filename;
 327     *ln = block_ptr->lineno;
 328 }
 329
 330 #else
 331 /* not MEMORY_DEBUG */
 332
 333 #define FATAL_ERROR_INTERNAL(f,l,s) fatal_error(s)
 334 #define MALLOC_INTERNAL(f,l,s) Malloc(s)
 335 #define MEMPTYSTR_INTERNAL(f,l) memptystr()
 336 #define MCOPYSTR_INTERNAL(f,l,s) mcopystr(s)
 337 #define MCOPYSTRN_INTERNAL(f,l,s,l2) mcopystrn(s,l2)
 338 #define REALLOC_INTERNAL(f,l,p,s) Realloc(p,s)
 339 #define FREE_INTERNAL(f,l,p) Free(p)
 340 #define MPRINTF_VA_LIST_INTERNAL(f,l,s,p) mprintf_va_list(s,p)
 341
 342 #define extract_location(p,f,l) ((void)p,(void)f,(void)l)
 343 #endif
 344
 345 /** Report a fatal error.
 346  *
 347  * @param size the number of bytes that could not be allocated
 348  *
 349  * This function does not return.
 350  */
 351 __attribute__ ((__noreturn__))
 352 static void fatal_error(
 353 #ifdef MEMORY_DEBUG
 354   const char *filename, int line,
 355 #endif
 356   size_t size)
 357 {
 358     const char *err_msg = strerror(errno);
 359 #ifdef MEMORY_DEBUG
 360     fprintf(stderr, FILENAME_FORMAT "Fatal error: cannot allocate %lu bytes"
 361         " of memory after allocating %lu bytes: ", filename, line,
 362         (unsigned long) size, (unsigned long) allocated_size);
 363 #else
 364     fprintf(stderr, "Fatal error: cannot allocate %lu bytes of memory: ",
 365         (unsigned long) size);
 366 #endif
 367     if (err_msg != NULL) fprintf(stderr, "%s. Exiting.\n", err_msg);
 368     else fprintf(stderr, "Unknown error (errno: %d). Exiting.\n", errno);
 369     exit(EXIT_FAILURE);
 370 }
 371
 372 #ifdef MEMORY_DEBUG
 373 void *Malloc(size_t size)
 374 {
 375   return Malloc_dbg(0,0,size);
 376 }
 377
 378 void *Malloc_dbg(const char *filename, int line, size_t size)
 379 #else
 380 void *Malloc(size_t size)
 381 #endif
 382 {
 383     if (size > 0) {
 384         void *ptr;
 385 #ifdef MEMORY_DEBUG
 386         memory_block *block_ptr;
 387         block_ptr = (memory_block*)malloc(sizeof(*block_ptr) -
 388             sizeof(block_ptr->begin) + size + sizeof(block_ptr));
 389         if (block_ptr == NULL) fatal_error(filename, line, size);
 390         block_ptr->filename = filename;
 391         block_ptr->lineno = line;
 392         block_ptr->size = size;
 393         add_to_list(block_ptr);
 394         set_magic_values(block_ptr);
 395         ptr = &block_ptr->begin;
 396         total_allocated += size;
 397         block_ptr->ordinal = alloc_count++;
 398         allocated_size += size;
 399 #ifdef MEMORY_DEBUG_ADDRESS
 400         check_memory_address(block_ptr, 0);
 401 #endif
 402         if (peak_size < allocated_size) peak_size = allocated_size;
 403 #else
 404         ptr = malloc(size);
 405         if (ptr == NULL) fatal_error(size);
 406 #endif
 407         malloc_count++;
 408         return ptr;
 409     } else return NULL;
 410 }
 411
 412 #ifdef MEMORY_DEBUG
 413
 414 void *Realloc(void *ptr, size_t size)
 415 {
 416   return Realloc_dbg(0,0,ptr,size);
 417 }
 418
 419 void *Realloc_dbg(const char *filename, int line, void *ptr, size_t size)
 420 #else
 421 void *Realloc(void *ptr, size_t size)
 422 #endif
 423 {
 424     if (ptr == NULL) return MALLOC_INTERNAL(filename, line, size);
 425     else if (size == 0) {
 426         FREE_INTERNAL(filename, line, ptr);
 427         return NULL;
 428     } else {
 429         void *new_ptr;
 430 #ifdef MEMORY_DEBUG
 431         memory_block *block_ptr = NULL;
 432         block_ptr = (memory_block*)(void*)((unsigned char*)ptr - offset);
 433         check_magic_values(filename, line, block_ptr, 1);
 434         remove_from_list(block_ptr);
 435         allocated_size -= block_ptr->size;
 436         if (size < block_ptr->size)
 437             memset((unsigned char*)ptr + size, 0x55, block_ptr->size - size);
 438         block_ptr = (memory_block*)realloc(block_ptr, sizeof(*block_ptr) -
 439             sizeof(block_ptr->begin) + sizeof(block_ptr) + size);
 440         if (block_ptr == NULL) fatal_error(filename, line, size);
 441 #ifdef MEMORY_DEBUG_ADDRESS
 442         check_memory_address(block_ptr, 1);
 443 #endif
 444         block_ptr->filename = filename;
 445         block_ptr->lineno = line;
 446         block_ptr->size = size;
 447         add_to_list(block_ptr);
 448         set_magic_values(block_ptr);
 449         new_ptr = &block_ptr->begin;
 450         total_allocated += size;
 451         alloc_count++;
 452         allocated_size += size;
 453         if (peak_size < allocated_size) peak_size = allocated_size;
 454 #else
 455         new_ptr = realloc(ptr, size);
 456         if (new_ptr == NULL) FATAL_ERROR_INTERNAL(filename, line, size);
 457 #endif
 458         return new_ptr;
 459     }
 460 }
 461
 462 #ifdef MEMORY_DEBUG
 463 void Free(void *ptr)
 464 {
 465   Free_dbg(0,0,ptr);
 466 }
 467
 468 extern void Free_dbg(const char *filename, int line, void *ptr)
 469 #else
 470 void Free(void *ptr)
 471 #endif
 472 {
 473     if (ptr != NULL) {
 474 #ifdef MEMORY_DEBUG
 475         memory_block *block_ptr = NULL;
 476         block_ptr = (memory_block*)(void*)((unsigned char*)ptr - offset);
 477 #ifdef MEMORY_DEBUG_ADDRESS
 478         check_memory_address(block_ptr, 2);
 479 #endif
 480         check_magic_values(filename, line, block_ptr, 0);
 481         remove_from_list(block_ptr);
 482         allocated_size -= block_ptr->size;
 483         memset(ptr, 0xAA, block_ptr->size);
 484 #ifdef MEMORY_DEBUG_FREE
 485         add_to_free_list(block_ptr);
 486 #else
 487         free(block_ptr);
 488 #endif
 489 #else
 490         free(ptr);
 491 #endif
 492         free_count++;
 493     }
 494 }
 495
 496 static const size_t maxprint = 32;
 497
 498 void check_mem_leak(const char *program_name)
 499 {
 500 #ifdef MEMORY_DEBUG
 501     fprintf(stderr, "%s(%d): memory usage statistics:\n"
 502         "total allocations: %lu\n"
 503         "malloc/new  calls: %lu\n"
 504         "free/delete calls: %lu\n"
 505         "peak memory usage: %lu bytes\n"
 506         "average block size: %g bytes\n",
 507         program_name, (int)getpid(),
 508         (unsigned long)alloc_count, (unsigned long)malloc_count,
 509         (unsigned long) free_count, (unsigned long) peak_size,
 510         (double)total_allocated / (double)alloc_count);
 511     if (list_head != NULL) {
 512         memory_block *block_ptr = list_head;
 513         size_t counter = 0;
 514         fprintf(stderr, "unallocated blocks:\n");
 515         do {
 516             if (block_ptr->filename != 0) {
 517                 fprintf(stderr, FILENAME_FORMAT,
 518                     block_ptr->filename, block_ptr->lineno);
 519             }
 520             fprintf(stderr, "\tMemory leak at %p, size %lu, ord %lu: ",
 521                 (void*)&block_ptr->begin, (unsigned long)block_ptr->size,
 522                 (unsigned long)block_ptr->ordinal);
 523             {
 524               const unsigned char * mm = (const unsigned char*)&block_ptr->begin;
 525               size_t x, limit = (block_ptr->size > maxprint) ? maxprint
 526                 : block_ptr->size;
 527               for (x = 0; x < limit; ++x) {
 528                 fputc( isprint(mm[x]) ? mm[x] : '.', stderr );
 529               }
 530               fputc(10, stderr);
 531             }
 532             block_ptr = block_ptr->next;
 533             counter++;
 534         } while (block_ptr != NULL);
 535         fprintf(stderr, "total unallocated: %lu bytes in %lu blocks\n",
 536             (unsigned long) allocated_size, (unsigned long) counter);
 537     }
 538 #ifdef MEMORY_DEBUG_FREE
 539     check_free_list();
 540     release_free_blocks();
 541 #endif
 542 #else
 543     if (malloc_count != free_count) {
 544         fprintf(stderr, "%s: warning: memory leakage detected.\n"
 545             "Total malloc calls: %lu, free calls: %lu\n"
 546             "Please submit a bug report including the current input file(s).\n",
 547             program_name,
 548             (unsigned long) malloc_count, (unsigned long) free_count);
 549     }
 550 #endif
 551 }
 552
 553 #ifdef MEMORY_DEBUG
 554 void check_mem_corrupt(const char *program_name)
 555 {
 556     size_t counter = 0;
 557     memory_block *block_ptr;
 558     fprintf(stderr, "%s: checking memory blocks for corruption\n",
 559         program_name);
 560     for (block_ptr = list_head; block_ptr != NULL; block_ptr = block_ptr->next)
 561     {
 562         unsigned char *ptr = (unsigned char*)&block_ptr->begin;
 563         if (memcmp(ptr - sizeof(block_ptr), &block_ptr, sizeof(block_ptr))) {
 564             fprintf(stderr, "Fatal error: memory corruption detected in front "
 565                 "of pointer %p\n", ptr);
 566             abort();
 567         }
 568         if (memcmp(ptr + block_ptr->size, &block_ptr, sizeof(block_ptr))) {
 569             fprintf(stderr, "Fatal error: memory corruption detected at the "
 570                 "end of pointer %p\n", ptr);
 571             abort();
 572         }
 573         counter++;
 574     }
 575     fprintf(stderr, "%s: %lu memory block%s OK\n", program_name,
 576         (unsigned long) counter, counter > 1 ? "s are" : " is");
 577 #ifdef MEMORY_DEBUG_FREE
 578     check_free_list();
 579 #endif
 580 }
 581 #endif
 582
 583 /** @brief Find the string length of an expstring_t
 584
 585 Finds the length of the C string pointed at by \p str, using some assumptions
 586 satisfied by an expstring_t.
 587
 588 @pre There is an offset from the beginning of the string which is a power
 589      of two, is within the buffer allocated for \p str and it contains '\\0'
 590 @pre The allocated buffer is at most twice as long as strlen(str)
 591 @pre \p bufsize is a valid pointer
 592
 593 @param [in]  str an expstring_t, must not be null
 594 @param [out] bufsize pointer to a location where the minimum buffer size
 595              (always a power of two) is deposited.
 596 @return      the length of \p str as a C string
 597 */
 598 static size_t fast_strlen(const expstring_t str, size_t *bufsize)
 599 {
 600     size_t size, min, max;
 601     /* Find the 0 byte at the end of the allocated buffer */
 602     for (size = 1; str[size - 1] != '\0'; size *= 2) {}
 603     *bufsize = size;
 604     if (size == 1) return 0;
 605     /* Binary search the second half of the buffer */
 606     min = size / 2 - 1;
 607     max = size - 1;
 608     while (max - min > 1) {
 609         size_t med = (min + max) / 2;
 610         if (str[med] != '\0') min = med;
 611         else max = med;
 612     }
 613     return max;
 614 }
 615
 616 /** @brief Find the first power of two which is greater than \p len
 617  *
 618  *  @param len the desired length
 619  *  @return a power of 2 greater than \p len
 620  *
 621  *  \p len is taken to be the number of characters needed. The returned value
 622  *  will always be greater than \p len to accommodate the null terminator.
 623  */
 624 static size_t roundup_size(size_t len)
 625 {
 626     size_t size;
 627     for (size = 1; len >= size; size *= 2);
 628     return size;
 629 }
 630
 631 #ifdef MEMORY_DEBUG
 632 expstring_t mprintf_va_list(const char *fmt, va_list pvar)
 633 {
 634   return mprintf_va_list_dbg(0,0,fmt,pvar);
 635 }
 636
 637 expstring_t mprintf_va_list_dbg(const char *filename, int line, const char *fmt, va_list pvar)
 638 #else
 639 expstring_t mprintf_va_list(const char *fmt, va_list pvar)
 640 #endif
 641 {
 642     char buf[BUFSIZE];
 643     expstring_t ptr;
 644     int len;
 645     size_t size, slen;
 646     va_list pvar2;
 647     va_copy(pvar2, pvar);
 648     len = vsnprintf(buf, BUFSIZE, fmt, pvar2);
 649     va_end(pvar2);
 650     if (len < 0) {
 651         /* The result does not fit in buf and we have no idea how many bytes
 652          * are needed (only old versions of libc may return -1).
 653          * Try to double the buffer size until it is large enough. */
 654         for (size = 2 * BUFSIZE; ; size *= 2) {
 655             ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 656             va_copy(pvar2, pvar);
 657             len = vsnprintf(ptr, size, fmt, pvar2);
 658             va_end(pvar2);
 659             if (len >= 0 && (size_t)len < size) break;
 660             FREE_INTERNAL(filename, line, ptr);
 661         }
 662         slen = (size_t)len;
 663     } else if (len >= BUFSIZE) {
 664         /* The result does not fit in buf, but we know how many bytes we need.
 665          * Allocate a buffer that is large enough and repeat vsnprintf() */
 666         slen = (size_t)len;
 667         size = roundup_size(slen);
 668         ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 669         /* use the original pvar since this is the last try */
 670         if (vsnprintf(ptr, size, fmt, pvar) != len) {
 671             perror("Fatal error: unexpected vsnprintf() return value");
 672             exit(EXIT_FAILURE);
 673         }
 674     } else {
 675         /* the complete result is in buf */
 676         slen = (size_t)len;
 677         size = roundup_size(slen);
 678         ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 679         memcpy(ptr, buf, slen);
 680     }
 681     memset(ptr + slen, '\0', size - slen);
 682     return ptr;
 683 }
 684
 685 #ifdef MEMORY_DEBUG
 686 expstring_t mprintf_dbg(const char *filename, int line, const char *fmt, ...)
 687 {
 688     expstring_t ptr;
 689     va_list pvar;
 690     va_start(pvar, fmt);
 691     ptr = mprintf_va_list_dbg(filename, line, fmt, pvar);
 692     va_end(pvar);
 693     return ptr;
 694 }
 695 #endif
 696
 697 expstring_t mprintf(const char *fmt, ...)
 698 {
 699     expstring_t ptr;
 700     va_list pvar;
 701     va_start(pvar, fmt);
 702     ptr = mprintf_va_list(fmt, pvar);
 703     va_end(pvar);
 704     return ptr;
 705 }
 706
 707 /* Tracking the origin: extracts the filename/line from the original allocation
 708  * of the expstring_t. */
 709 expstring_t mputprintf_va_list(expstring_t str, const char *fmt, va_list pvar)
 710 {
 711     const char *filename = NULL;
 712     int line = 0;
 713     if (str != NULL) {
 714         size_t size;
 715         size_t len = fast_strlen(str, &size);
 716         size_t rest = size - len;
 717         int len2;
 718         va_list pvar2;
 719         /* make a copy of pvar to allow re-use later */
 720         va_copy(pvar2, pvar);
 721         len2 = vsnprintf(str + len, rest, fmt, pvar2);
 722         va_end(pvar2);
 723         extract_location(str, &filename, &line);
 724         if (len2 < 0) {
 725             /* the result does not fit in buf and we have no idea how many
 726              * bytes are needed (only old versions of libc may return -1)
 727              * try to double the buffer size until it is large enough */
 728             size_t newlen;
 729             do {
 730                 size *= 2;
 731                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, size);
 732                 rest = size - len;
 733                 va_copy(pvar2, pvar);
 734                 len2 = vsnprintf(str + len, rest, fmt, pvar2);
 735                 va_end(pvar2);
 736             } while (len2 < 0 || (size_t)len2 >= rest);
 737             newlen = len + (size_t)len2;
 738             memset(str + newlen, '\0', size - newlen);
 739         } else if ((size_t)len2 >= rest) {
 740             /* there isn't enough space in buffer, but we know how many bytes
 741              * we need: reallocate the buffer to be large enough and repeat
 742              * vsnprintf() */
 743             size_t newlen = len + (size_t)len2;
 744             size = roundup_size(newlen);
 745             str = (expstring_t)REALLOC_INTERNAL(filename, line, str, size);
 746             /* use the original pvar since this is the last try */
 747             if (vsnprintf(str + len, size - len, fmt, pvar) != len2) {
 748                 perror("Fatal error: unexpected vsnprintf() return value");
 749                 exit(EXIT_FAILURE);
 750             }
 751             memset(str + newlen, '\0', size - newlen);
 752         }
 753     } else str = MPRINTF_VA_LIST_INTERNAL(filename, line, fmt, pvar);
 754     return str;
 755 }
 756
 757 expstring_t mputprintf(expstring_t str, const char *fmt, ...)
 758 {
 759     va_list pvar;
 760     va_start(pvar, fmt);
 761     str = mputprintf_va_list(str, fmt, pvar);
 762     va_end(pvar);
 763     return str;
 764 }
 765
 766 #ifdef MEMORY_DEBUG
 767 expstring_t memptystr(void)
 768 {
 769   return memptystr_dbg(0,0);
 770 }
 771
 772 expstring_t memptystr_dbg(const char *filename, int line)
 773 #else
 774 expstring_t memptystr(void)
 775 #endif
 776 {
 777     expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, 1);
 778     ptr[0] = '\0';
 779     return ptr;
 780 }
 781
 782 #ifdef MEMORY_DEBUG
 783 expstring_t mcopystr(const char *str)
 784 {
 785   return mcopystr_dbg(0,0,str);
 786 }
 787
 788 expstring_t mcopystr_dbg(const char *filename, int line, const char *str)
 789 #else
 790 expstring_t mcopystr(const char *str)
 791 #endif
 792 {
 793     if (str != NULL) {
 794         size_t len = strlen(str);
 795         size_t size = roundup_size(len);
 796         expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 797         memcpy(ptr, str, len);
 798         memset(ptr + len, '\0', size - len);
 799         return ptr;
 800     } else return MEMPTYSTR_INTERNAL(filename, line);
 801 }
 802
 803 #ifdef MEMORY_DEBUG
 804 expstring_t mcopystrn(const char *str, size_t len)
 805 {
 806   return mcopystrn_dbg(0,0,str, len);
 807 }
 808
 809 expstring_t mcopystrn_dbg(const char *filename, int line, const char *str,
 810   size_t len)
 811 #else
 812 expstring_t mcopystrn(const char *str, size_t len)
 813 #endif
 814 {
 815     if (len != 0 && str != NULL) {
 816         size_t size = roundup_size(len);
 817         expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 818         memcpy(ptr, str, len);
 819         memset(ptr + len, '\0', size - len);
 820         return ptr;
 821     } else return MEMPTYSTR_INTERNAL(filename, line);
 822 }
 823
 824 /* Tracking the origin: extracts the filename/line from the original allocation
 825  * of the expstring_t. */
 826 expstring_t mputstr(expstring_t str, const char *str2)
 827 {
 828     const char *filename = NULL;
 829     int line = 0;
 830     if (str2 != NULL) {
 831         if (str != NULL) {
 832             size_t size;
 833             size_t len = fast_strlen(str, &size);
 834             size_t len2 = strlen(str2);
 835             size_t newlen = len + len2;
 836             if (size <= newlen) {
 837                 size_t newsize = roundup_size(newlen);
 838                 extract_location(str, &filename, &line);
 839                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 840                 memset(str + newlen, '\0', newsize - newlen);
 841             }
 842             memcpy(str + len, str2, len2);
 843         } else str = MCOPYSTR_INTERNAL(filename, line, str2);
 844     }
 845     return str;
 846 }
 847
 848 /* Tracking the origin: extracts the filename/line from the original allocation
 849  * of the expstring_t. */
 850 expstring_t mputstrn(expstring_t str, const char *str2, size_t len2)
 851 {
 852     const char *filename = NULL;
 853     int line = 0;
 854     if (len2 != 0 && str2 != NULL) {
 855         if (str != NULL) {
 856             size_t size;
 857             size_t len = fast_strlen(str, &size);
 858             size_t newlen = len + len2;
 859             if (size <= newlen) {
 860                 size_t newsize = roundup_size(newlen);
 861                 extract_location(str, &filename, &line);
 862                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 863                 memset(str + newlen, '\0', newsize - newlen);
 864             }
 865             memcpy(str + len, str2, len2);
 866         } else str = MCOPYSTRN_INTERNAL(filename, line, str2, len2);
 867     }
 868     return str;
 869 }
 870
 871 /* Tracking the origin: extracts the filename/line from the original allocation
 872  * of the expstring_t. */
 873 expstring_t mputc(expstring_t str, char c)
 874 {
 875     const char *filename = NULL;
 876     int line = 0;
 877     if (str != NULL) {
 878         if (c != '\0') {
 879             size_t size;
 880             size_t len = fast_strlen(str, &size);
 881             if (size <= len + 1) {
 882                 extract_location(str, &filename, &line);
 883                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, 2 * size);
 884                 memset(str + size, '\0', size);
 885             }
 886             str[len] = c;
 887         }
 888     } else {
 889         if (c != '\0') {
 890             str = (expstring_t)MALLOC_INTERNAL(filename, line, 2);
 891             str[0] = c;
 892             str[1] = '\0';
 893         } else str = MEMPTYSTR_INTERNAL(filename, line);
 894     }
 895     return str;
 896 }
 897
 898 /* Tracking the origin: extracts the filename/line from the original allocation
 899  * of the expstring_t. */
 900 expstring_t mtruncstr(expstring_t str, size_t newlen)
 901 {
 902   const char *filename = NULL;
 903   int line = 0;
 904   if (str != NULL) {
 905     size_t size;
 906     size_t len = fast_strlen(str, &size);
 907     if (newlen < len) {
 908       size_t newsize = roundup_size(newlen);
 909       if (newsize < size) {
 910         extract_location(str, &filename, &line);
 911         str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 912       }
 913       memset(str + newlen, '\0', newsize - newlen);
 914     }
 915   }
 916   return str;
 917 }
 918
 919 size_t mstrlen(const expstring_t str)
 920 {
 921   if (str != NULL) {
 922     size_t size;
 923     return fast_strlen(str, &size);
 924   } else return 0;
 925 }
 926
 927 char * buildstr(int b) {
 928   if (b < 0 || b > 99) return NULL; /* invalid */
 929   if (b == 99) return memptystr(); /* empty string for full version */
 930   return mprintf("%02d", b);
 931 }