common/memory.c

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