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 #ifdef MEMORY_DEBUG
 507 static const size_t maxprint = 32;
 508 #endif
 509
 510 void check_mem_leak(const char *program_name)
 511 {
 512 #ifdef MEMORY_DEBUG
 513     fprintf(stderr, "%s(%d): memory usage statistics:\n"
 514         "total allocations: %lu\n"
 515         "malloc/new  calls: %lu\n"
 516         "free/delete calls: %lu\n"
 517         "peak memory usage: %lu bytes\n"
 518         "average block size: %g bytes\n",
 519         program_name, (int)getpid(),
 520         (unsigned long)alloc_count, (unsigned long)malloc_count,
 521         (unsigned long) free_count, (unsigned long) peak_size,
 522         (double)total_allocated / (double)alloc_count);
 523     if (list_head != NULL) {
 524         memory_block *block_ptr = list_head;
 525         size_t counter = 0;
 526         fprintf(stderr, "unallocated blocks:\n");
 527         do {
 528             if (block_ptr->filename != 0) {
 529                 fprintf(stderr, FILENAME_FORMAT,
 530                     block_ptr->filename, block_ptr->lineno);
 531             }
 532             fprintf(stderr, "\tMemory leak at %p, size %lu, ord %lu: ",
 533                 (void*)&block_ptr->begin, (unsigned long)block_ptr->size,
 534                 (unsigned long)block_ptr->ordinal);
 535             {
 536               const unsigned char * mm = (const unsigned char*)&block_ptr->begin;
 537               size_t x, limit = (block_ptr->size > maxprint) ? maxprint
 538                 : block_ptr->size;
 539               for (x = 0; x < limit; ++x) {
 540                 fputc( isprint(mm[x]) ? mm[x] : '.', stderr );
 541               }
 542               fputc(10, stderr);
 543             }
 544             block_ptr = block_ptr->next;
 545             counter++;
 546         } while (block_ptr != NULL);
 547         fprintf(stderr, "total unallocated: %lu bytes in %lu blocks\n",
 548             (unsigned long) allocated_size, (unsigned long) counter);
 549     }
 550 #ifdef MEMORY_DEBUG_FREE
 551     check_free_list();
 552     release_free_blocks();
 553 #endif
 554 #else
 555     if (malloc_count != free_count) {
 556         fprintf(stderr, "%s: warning: memory leakage detected.\n"
 557             "Total malloc calls: %lu, free calls: %lu\n"
 558             "Please submit a bug report including the current input file(s).\n",
 559             program_name,
 560             (unsigned long) malloc_count, (unsigned long) free_count);
 561     }
 562 #endif
 563 }
 564
 565 #ifdef MEMORY_DEBUG
 566 void check_mem_corrupt(const char *program_name)
 567 {
 568     size_t counter = 0;
 569     memory_block *block_ptr;
 570     fprintf(stderr, "%s: checking memory blocks for corruption\n",
 571         program_name);
 572     for (block_ptr = list_head; block_ptr != NULL; block_ptr = block_ptr->next)
 573     {
 574         unsigned char *ptr = (unsigned char*)&block_ptr->begin;
 575         if (memcmp(ptr - sizeof(block_ptr), &block_ptr, sizeof(block_ptr))) {
 576             fprintf(stderr, "Fatal error: memory corruption detected in front "
 577                 "of pointer %p\n", ptr);
 578             abort();
 579         }
 580         if (memcmp(ptr + block_ptr->size, &block_ptr, sizeof(block_ptr))) {
 581             fprintf(stderr, "Fatal error: memory corruption detected at the "
 582                 "end of pointer %p\n", ptr);
 583             abort();
 584         }
 585         counter++;
 586     }
 587     fprintf(stderr, "%s: %lu memory block%s OK\n", program_name,
 588         (unsigned long) counter, counter > 1 ? "s are" : " is");
 589 #ifdef MEMORY_DEBUG_FREE
 590     check_free_list();
 591 #endif
 592 }
 593 #endif
 594
 595 /** @brief Find the string length of an expstring_t
 596
 597 Finds the length of the C string pointed at by \p str, using some assumptions
 598 satisfied by an expstring_t.
 599
 600 @pre There is an offset from the beginning of the string which is a power
 601      of two, is within the buffer allocated for \p str and it contains '\\0'
 602 @pre The allocated buffer is at most twice as long as strlen(str)
 603 @pre \p bufsize is a valid pointer
 604
 605 @param [in]  str an expstring_t, must not be null
 606 @param [out] bufsize pointer to a location where the minimum buffer size
 607              (always a power of two) is deposited.
 608 @return      the length of \p str as a C string
 609 */
 610 static size_t fast_strlen(const expstring_t str, size_t *bufsize)
 611 {
 612     size_t size, min, max;
 613     /* Find the 0 byte at the end of the allocated buffer */
 614     for (size = 1; str[size - 1] != '\0'; size *= 2) {}
 615     *bufsize = size;
 616     if (size == 1) return 0;
 617     /* Binary search the second half of the buffer */
 618     min = size / 2 - 1;
 619     max = size - 1;
 620     while (max - min > 1) {
 621         size_t med = (min + max) / 2;
 622         if (str[med] != '\0') min = med;
 623         else max = med;
 624     }
 625     return max;
 626 }
 627
 628 /** @brief Find the first power of two which is greater than \p len
 629  *
 630  *  @param len the desired length
 631  *  @return a power of 2 greater than \p len
 632  *
 633  *  \p len is taken to be the number of characters needed. The returned value
 634  *  will always be greater than \p len to accommodate the null terminator.
 635  */
 636 static size_t roundup_size(size_t len)
 637 {
 638     size_t size;
 639     for (size = 1; len >= size; size *= 2);
 640     return size;
 641 }
 642
 643 #ifdef MEMORY_DEBUG
 644 expstring_t mprintf_va_list(const char *fmt, va_list pvar)
 645 {
 646   return mprintf_va_list_dbg(0,0,fmt,pvar);
 647 }
 648
 649 expstring_t mprintf_va_list_dbg(const char *filename, int line, const char *fmt, va_list pvar)
 650 #else
 651 expstring_t mprintf_va_list(const char *fmt, va_list pvar)
 652 #endif
 653 {
 654     char buf[BUFSIZE];
 655     expstring_t ptr;
 656     int len;
 657     size_t size, slen;
 658     va_list pvar2;
 659     va_copy(pvar2, pvar);
 660     len = vsnprintf(buf, BUFSIZE, fmt, pvar2);
 661     va_end(pvar2);
 662     if (len < 0) {
 663         /* The result does not fit in buf and we have no idea how many bytes
 664          * are needed (only old versions of libc may return -1).
 665          * Try to double the buffer size until it is large enough. */
 666         for (size = 2 * BUFSIZE; ; size *= 2) {
 667             ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 668             va_copy(pvar2, pvar);
 669             len = vsnprintf(ptr, size, fmt, pvar2);
 670             va_end(pvar2);
 671             if (len >= 0 && (size_t)len < size) break;
 672             FREE_INTERNAL(filename, line, ptr);
 673         }
 674         slen = (size_t)len;
 675     } else if (len >= BUFSIZE) {
 676         /* The result does not fit in buf, but we know how many bytes we need.
 677          * Allocate a buffer that is large enough and repeat vsnprintf() */
 678         slen = (size_t)len;
 679         size = roundup_size(slen);
 680         ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 681         /* use the original pvar since this is the last try */
 682         if (vsnprintf(ptr, size, fmt, pvar) != len) {
 683             perror("Fatal error: unexpected vsnprintf() return value");
 684             exit(EXIT_FAILURE);
 685         }
 686     } else {
 687         /* the complete result is in buf */
 688         slen = (size_t)len;
 689         size = roundup_size(slen);
 690         ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 691         memcpy(ptr, buf, slen);
 692     }
 693     memset(ptr + slen, '\0', size - slen);
 694     return ptr;
 695 }
 696
 697 #ifdef MEMORY_DEBUG
 698 expstring_t mprintf_dbg(const char *filename, int line, const char *fmt, ...)
 699 {
 700     expstring_t ptr;
 701     va_list pvar;
 702     va_start(pvar, fmt);
 703     ptr = mprintf_va_list_dbg(filename, line, fmt, pvar);
 704     va_end(pvar);
 705     return ptr;
 706 }
 707 #endif
 708
 709 expstring_t mprintf(const char *fmt, ...)
 710 {
 711     expstring_t ptr;
 712     va_list pvar;
 713     va_start(pvar, fmt);
 714     ptr = mprintf_va_list(fmt, pvar);
 715     va_end(pvar);
 716     return ptr;
 717 }
 718
 719 /* Tracking the origin: extracts the filename/line from the original allocation
 720  * of the expstring_t. */
 721 expstring_t mputprintf_va_list(expstring_t str, const char *fmt, va_list pvar)
 722 {
 723     const char *filename = NULL;
 724     int line = 0;
 725     if (str != NULL) {
 726         size_t size;
 727         size_t len = fast_strlen(str, &size);
 728         size_t rest = size - len;
 729         int len2;
 730         va_list pvar2;
 731         /* make a copy of pvar to allow re-use later */
 732         va_copy(pvar2, pvar);
 733         len2 = vsnprintf(str + len, rest, fmt, pvar2);
 734         va_end(pvar2);
 735         extract_location(str, &filename, &line);
 736         if (len2 < 0) {
 737             /* the result does not fit in buf and we have no idea how many
 738              * bytes are needed (only old versions of libc may return -1)
 739              * try to double the buffer size until it is large enough */
 740             size_t newlen;
 741             do {
 742                 size *= 2;
 743                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, size);
 744                 rest = size - len;
 745                 va_copy(pvar2, pvar);
 746                 len2 = vsnprintf(str + len, rest, fmt, pvar2);
 747                 va_end(pvar2);
 748             } while (len2 < 0 || (size_t)len2 >= rest);
 749             newlen = len + (size_t)len2;
 750             memset(str + newlen, '\0', size - newlen);
 751         } else if ((size_t)len2 >= rest) {
 752             /* there isn't enough space in buffer, but we know how many bytes
 753              * we need: reallocate the buffer to be large enough and repeat
 754              * vsnprintf() */
 755             size_t newlen = len + (size_t)len2;
 756             size = roundup_size(newlen);
 757             str = (expstring_t)REALLOC_INTERNAL(filename, line, str, size);
 758             /* use the original pvar since this is the last try */
 759             if (vsnprintf(str + len, size - len, fmt, pvar) != len2) {
 760                 perror("Fatal error: unexpected vsnprintf() return value");
 761                 exit(EXIT_FAILURE);
 762             }
 763             memset(str + newlen, '\0', size - newlen);
 764         }
 765     } else str = MPRINTF_VA_LIST_INTERNAL(filename, line, fmt, pvar);
 766     return str;
 767 }
 768
 769 expstring_t mputprintf(expstring_t str, const char *fmt, ...)
 770 {
 771     va_list pvar;
 772     va_start(pvar, fmt);
 773     str = mputprintf_va_list(str, fmt, pvar);
 774     va_end(pvar);
 775     return str;
 776 }
 777
 778 #ifdef MEMORY_DEBUG
 779 expstring_t memptystr(void)
 780 {
 781   return memptystr_dbg(0,0);
 782 }
 783
 784 expstring_t memptystr_dbg(const char *filename, int line)
 785 #else
 786 expstring_t memptystr(void)
 787 #endif
 788 {
 789     expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, 1);
 790     ptr[0] = '\0';
 791     return ptr;
 792 }
 793
 794 #ifdef MEMORY_DEBUG
 795 expstring_t mcopystr(const char *str)
 796 {
 797   return mcopystr_dbg(0,0,str);
 798 }
 799
 800 expstring_t mcopystr_dbg(const char *filename, int line, const char *str)
 801 #else
 802 expstring_t mcopystr(const char *str)
 803 #endif
 804 {
 805     if (str != NULL) {
 806         size_t len = strlen(str);
 807         size_t size = roundup_size(len);
 808         expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 809         memcpy(ptr, str, len);
 810         memset(ptr + len, '\0', size - len);
 811         return ptr;
 812     } else return MEMPTYSTR_INTERNAL(filename, line);
 813 }
 814
 815 #ifdef MEMORY_DEBUG
 816 expstring_t mcopystrn(const char *str, size_t len)
 817 {
 818   return mcopystrn_dbg(0,0,str, len);
 819 }
 820
 821 expstring_t mcopystrn_dbg(const char *filename, int line, const char *str,
 822   size_t len)
 823 #else
 824 expstring_t mcopystrn(const char *str, size_t len)
 825 #endif
 826 {
 827     if (len != 0 && str != NULL) {
 828         size_t size = roundup_size(len);
 829         expstring_t ptr = (expstring_t)MALLOC_INTERNAL(filename, line, size);
 830         memcpy(ptr, str, len);
 831         memset(ptr + len, '\0', size - len);
 832         return ptr;
 833     } else return MEMPTYSTR_INTERNAL(filename, line);
 834 }
 835
 836 /* Tracking the origin: extracts the filename/line from the original allocation
 837  * of the expstring_t. */
 838 expstring_t mputstr(expstring_t str, const char *str2)
 839 {
 840     const char *filename = NULL;
 841     int line = 0;
 842     if (str2 != NULL) {
 843         if (str != NULL) {
 844             size_t size;
 845             size_t len = fast_strlen(str, &size);
 846             size_t len2 = strlen(str2);
 847             size_t newlen = len + len2;
 848             if (size <= newlen) {
 849                 size_t newsize = roundup_size(newlen);
 850                 extract_location(str, &filename, &line);
 851                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 852                 memset(str + newlen, '\0', newsize - newlen);
 853             }
 854             memcpy(str + len, str2, len2);
 855         } else str = MCOPYSTR_INTERNAL(filename, line, str2);
 856     }
 857     return str;
 858 }
 859
 860 /* Tracking the origin: extracts the filename/line from the original allocation
 861  * of the expstring_t. */
 862 expstring_t mputstrn(expstring_t str, const char *str2, size_t len2)
 863 {
 864     const char *filename = NULL;
 865     int line = 0;
 866     if (len2 != 0 && str2 != NULL) {
 867         if (str != NULL) {
 868             size_t size;
 869             size_t len = fast_strlen(str, &size);
 870             size_t newlen = len + len2;
 871             if (size <= newlen) {
 872                 size_t newsize = roundup_size(newlen);
 873                 extract_location(str, &filename, &line);
 874                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 875                 memset(str + newlen, '\0', newsize - newlen);
 876             }
 877             memcpy(str + len, str2, len2);
 878         } else str = MCOPYSTRN_INTERNAL(filename, line, str2, len2);
 879     }
 880     return str;
 881 }
 882
 883 /* Tracking the origin: extracts the filename/line from the original allocation
 884  * of the expstring_t. */
 885 expstring_t mputc(expstring_t str, char c)
 886 {
 887     const char *filename = NULL;
 888     int line = 0;
 889     if (str != NULL) {
 890         if (c != '\0') {
 891             size_t size;
 892             size_t len = fast_strlen(str, &size);
 893             if (size <= len + 1) {
 894                 extract_location(str, &filename, &line);
 895                 str = (expstring_t)REALLOC_INTERNAL(filename, line, str, 2 * size);
 896                 memset(str + size, '\0', size);
 897             }
 898             str[len] = c;
 899         }
 900     } else {
 901         if (c != '\0') {
 902             str = (expstring_t)MALLOC_INTERNAL(filename, line, 2);
 903             str[0] = c;
 904             str[1] = '\0';
 905         } else str = MEMPTYSTR_INTERNAL(filename, line);
 906     }
 907     return str;
 908 }
 909
 910 /* Tracking the origin: extracts the filename/line from the original allocation
 911  * of the expstring_t. */
 912 expstring_t mtruncstr(expstring_t str, size_t newlen)
 913 {
 914   const char *filename = NULL;
 915   int line = 0;
 916   if (str != NULL) {
 917     size_t size;
 918     size_t len = fast_strlen(str, &size);
 919     if (newlen < len) {
 920       size_t newsize = roundup_size(newlen);
 921       if (newsize < size) {
 922         extract_location(str, &filename, &line);
 923         str = (expstring_t)REALLOC_INTERNAL(filename, line, str, newsize);
 924       }
 925       memset(str + newlen, '\0', newsize - newlen);
 926     }
 927   }
 928   return str;
 929 }
 930
 931 size_t mstrlen(const expstring_t str)
 932 {
 933   if (str != NULL) {
 934     size_t size;
 935     return fast_strlen(str, &size);
 936   } else return 0;
 937 }
 938
 939 char * buildstr(int b) {
 940   if (b < 0 || b > 99) return NULL; /* invalid */
 941   if (b == 99) return memptystr(); /* empty string for full version */
 942   return mprintf("%02d", b);
 943 }