intern/guardedalloc/intern/mallocn_guarded_impl.c

   1 /*
   2  * This program is free software; you can redistribute it and/or
   3  * modify it under the terms of the GNU General Public License
   4  * as published by the Free Software Foundation; either version 2
   5  * of the License, or (at your option) any later version.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program; if not, write to the Free Software Foundation,
  14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  15  *
  16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  17  * All rights reserved.
  18  */
  19
  20 /** \file
  21  * \ingroup MEM
  22  *
  23  * Guarded memory allocation, and boundary-write detection.
  24  */
  25
  26 #include <stdarg.h>
  27 #include <stdlib.h>
  28 #include <string.h> /* memcpy */
  29 #include <sys/types.h>
  30
  31 #include "MEM_guardedalloc.h"
  32
  33 /* to ensure strict conversions */
  34 #include "../../source/blender/blenlib/BLI_strict_flags.h"
  35
  36 #include "atomic_ops.h"
  37 #include "mallocn_intern.h"
  38
  39 /* Only for debugging:
  40  * store original buffer's name when doing MEM_dupallocN
  41  * helpful to profile issues with non-freed "dup_alloc" buffers,
  42  * but this introduces some overhead to memory header and makes
  43  * things slower a bit, so better to keep disabled by default
  44  */
  45 //#define DEBUG_MEMDUPLINAME
  46
  47 /* Only for debugging:
  48  * lets you count the allocations so as to find the allocator of unfreed memory
  49  * in situations where the leak is predictable */
  50
  51 //#define DEBUG_MEMCOUNTER
  52
  53 /* Only for debugging:
  54  * defining DEBUG_THREADS will enable check whether memory manager
  55  * is locked with a mutex when allocation is called from non-main
  56  * thread.
  57  *
  58  * This helps troubleshooting memory issues caused by the fact
  59  * guarded allocator is not thread-safe, however this check will
  60  * fail to check allocations from openmp threads.
  61  */
  62 //#define DEBUG_THREADS
  63
  64 /* Only for debugging:
  65  * Defining DEBUG_BACKTRACE will store a backtrace from where
  66  * memory block was allocated and print this trace for all
  67  * unfreed blocks.
  68  */
  69 //#define DEBUG_BACKTRACE
  70
  71 #ifdef DEBUG_BACKTRACE
  72 #  define BACKTRACE_SIZE 100
  73 #endif
  74
  75 #ifdef DEBUG_MEMCOUNTER
  76 /* set this to the value that isn't being freed */
  77 #  define DEBUG_MEMCOUNTER_ERROR_VAL 0
  78 static int _mallocn_count = 0;
  79
  80 /* breakpoint here */
  81 static void memcount_raise(const char *name)
  82 {
  83   fprintf(stderr, "%s: memcount-leak, %d\n", name, _mallocn_count);
  84 }
  85 #endif
  86
  87 /* --------------------------------------------------------------------- */
  88 /* Data definition                                                       */
  89 /* --------------------------------------------------------------------- */
  90 /* all memory chunks are put in linked lists */
  91 typedef struct localLink {
  92   struct localLink *next, *prev;
  93 } localLink;
  94
  95 typedef struct localListBase {
  96   void *first, *last;
  97 } localListBase;
  98
  99 /* note: keep this struct aligned (e.g., irix/gcc) - Hos */
 100 typedef struct MemHead {
 101   int tag1;
 102   size_t len;
 103   struct MemHead *next, *prev;
 104   const char *name;
 105   const char *nextname;
 106   int tag2;
 107   short mmap;      /* if true, memory was mmapped */
 108   short alignment; /* if non-zero aligned alloc was used
 109                     * and alignment is stored here.
 110                     */
 111 #ifdef DEBUG_MEMCOUNTER
 112   int _count;
 113 #endif
 114
 115 #ifdef DEBUG_MEMDUPLINAME
 116   int need_free_name, pad;
 117 #endif
 118
 119 #ifdef DEBUG_BACKTRACE
 120   void *backtrace[BACKTRACE_SIZE];
 121   int backtrace_size;
 122 #endif
 123 } MemHead;
 124
 125 typedef MemHead MemHeadAligned;
 126
 127 /* for openmp threading asserts, saves time troubleshooting
 128  * we may need to extend this if blender code starts using MEM_
 129  * functions inside OpenMP correctly with omp_set_lock() */
 130
 131 #if 0 /* disable for now, only use to debug openmp code which doesn lock threads for malloc */
 132 #  if defined(_OPENMP) && defined(DEBUG)
 133 #    include <assert.h>
 134 #    include <omp.h>
 135 #    define DEBUG_OMP_MALLOC
 136 #  endif
 137 #endif
 138
 139 #ifdef DEBUG_THREADS
 140 #  include <assert.h>
 141 #  include <pthread.h>
 142 static pthread_t mainid;
 143 #endif
 144
 145 #ifdef DEBUG_BACKTRACE
 146 #  if defined(__linux__) || defined(__APPLE__)
 147 #    include <execinfo.h>
 148 // Windows is not supported yet.
 149 //#  elif defined(_MSV_VER)
 150 //#    include <DbgHelp.h>
 151 #  endif
 152 #endif
 153
 154 typedef struct MemTail {
 155   int tag3, pad;
 156 } MemTail;
 157
 158 /* --------------------------------------------------------------------- */
 159 /* local functions                                                       */
 160 /* --------------------------------------------------------------------- */
 161
 162 static void addtail(volatile localListBase *listbase, void *vlink);
 163 static void remlink(volatile localListBase *listbase, void *vlink);
 164 static void rem_memblock(MemHead *memh);
 165 static void MemorY_ErroR(const char *block, const char *error);
 166 static const char *check_memlist(MemHead *memh);
 167
 168 /* --------------------------------------------------------------------- */
 169 /* locally used defines                                                  */
 170 /* --------------------------------------------------------------------- */
 171
 172 #ifdef __BIG_ENDIAN__
 173 #  define MAKE_ID(a, b, c, d) ((int)(a) << 24 | (int)(b) << 16 | (c) << 8 | (d))
 174 #else
 175 #  define MAKE_ID(a, b, c, d) ((int)(d) << 24 | (int)(c) << 16 | (b) << 8 | (a))
 176 #endif
 177
 178 #define MEMTAG1 MAKE_ID('M', 'E', 'M', 'O')
 179 #define MEMTAG2 MAKE_ID('R', 'Y', 'B', 'L')
 180 #define MEMTAG3 MAKE_ID('O', 'C', 'K', '!')
 181 #define MEMFREE MAKE_ID('F', 'R', 'E', 'E')
 182
 183 #define MEMNEXT(x) ((MemHead *)(((char *)x) - ((char *)&(((MemHead *)0)->next))))
 184
 185 /* --------------------------------------------------------------------- */
 186 /* vars                                                                  */
 187 /* --------------------------------------------------------------------- */
 188
 189 static unsigned int totblock = 0;
 190 static size_t mem_in_use = 0, mmap_in_use = 0, peak_mem = 0;
 191
 192 static volatile struct localListBase _membase;
 193 static volatile struct localListBase *membase = &_membase;
 194 static void (*error_callback)(const char *) = NULL;
 195 static void (*thread_lock_callback)(void) = NULL;
 196 static void (*thread_unlock_callback)(void) = NULL;
 197
 198 static bool malloc_debug_memset = false;
 199
 200 #ifdef malloc
 201 #  undef malloc
 202 #endif
 203
 204 #ifdef calloc
 205 #  undef calloc
 206 #endif
 207
 208 #ifdef free
 209 #  undef free
 210 #endif
 211
 212 /* --------------------------------------------------------------------- */
 213 /* implementation                                                        */
 214 /* --------------------------------------------------------------------- */
 215
 216 #ifdef __GNUC__
 217 __attribute__((format(printf, 1, 2)))
 218 #endif
 219 static void
 220 print_error(const char *str, ...)
 221 {
 222   char buf[1024];
 223   va_list ap;
 224
 225   va_start(ap, str);
 226   vsnprintf(buf, sizeof(buf), str, ap);
 227   va_end(ap);
 228   buf[sizeof(buf) - 1] = '\0';
 229
 230   if (error_callback)
 231     error_callback(buf);
 232   else
 233     fputs(buf, stderr);
 234 }
 235
 236 static void mem_lock_thread(void)
 237 {
 238 #ifdef DEBUG_THREADS
 239   static int initialized = 0;
 240
 241   if (initialized == 0) {
 242     /* assume first allocation happens from main thread */
 243     mainid = pthread_self();
 244     initialized = 1;
 245   }
 246
 247   if (!pthread_equal(pthread_self(), mainid) && thread_lock_callback == NULL) {
 248     assert(!"Memory function is called from non-main thread without lock");
 249   }
 250 #endif
 251
 252 #ifdef DEBUG_OMP_MALLOC
 253   assert(omp_in_parallel() == 0);
 254 #endif
 255
 256   if (thread_lock_callback)
 257     thread_lock_callback();
 258 }
 259
 260 static void mem_unlock_thread(void)
 261 {
 262 #ifdef DEBUG_THREADS
 263   if (!pthread_equal(pthread_self(), mainid) && thread_lock_callback == NULL) {
 264     assert(!"Thread lock was removed while allocation from thread is in progress");
 265   }
 266 #endif
 267
 268   if (thread_unlock_callback)
 269     thread_unlock_callback();
 270 }
 271
 272 bool MEM_guarded_consistency_check(void)
 273 {
 274   const char *err_val = NULL;
 275   MemHead *listend;
 276   /* check_memlist starts from the front, and runs until it finds
 277    * the requested chunk. For this test, that's the last one. */
 278   listend = membase->last;
 279
 280   err_val = check_memlist(listend);
 281
 282   return (err_val == NULL);
 283 }
 284
 285 void MEM_guarded_set_error_callback(void (*func)(const char *))
 286 {
 287   error_callback = func;
 288 }
 289
 290 void MEM_guarded_set_lock_callback(void (*lock)(void), void (*unlock)(void))
 291 {
 292   thread_lock_callback = lock;
 293   thread_unlock_callback = unlock;
 294 }
 295
 296 void MEM_guarded_set_memory_debug(void)
 297 {
 298   malloc_debug_memset = true;
 299 }
 300
 301 size_t MEM_guarded_allocN_len(const void *vmemh)
 302 {
 303   if (vmemh) {
 304     const MemHead *memh = vmemh;
 305
 306     memh--;
 307     return memh->len;
 308   }
 309   else {
 310     return 0;
 311   }
 312 }
 313
 314 void *MEM_guarded_dupallocN(const void *vmemh)
 315 {
 316   void *newp = NULL;
 317
 318   if (vmemh) {
 319     const MemHead *memh = vmemh;
 320     memh--;
 321
 322 #ifndef DEBUG_MEMDUPLINAME
 323     if (UNLIKELY(memh->mmap))
 324       newp = MEM_guarded_mapallocN(memh->len, "dupli_mapalloc");
 325     else if (LIKELY(memh->alignment == 0))
 326       newp = MEM_guarded_mapallocN(memh->len, "dupli_mapalloc");
 327     else
 328       newp = MEM_guarded_mallocN_aligned(memh->len, (size_t)memh->alignment, "dupli_alloc");
 329
 330     if (newp == NULL)
 331       return NULL;
 332 #else
 333     {
 334       MemHead *nmemh;
 335       char *name = malloc(strlen(memh->name) + 24);
 336
 337       if (UNLIKELY(memh->mmap)) {
 338         sprintf(name, "%s %s", "dupli_mapalloc", memh->name);
 339         newp = MEM_guarded_mapallocN(memh->len, name);
 340       }
 341       else if (LIKELY(memh->alignment == 0)) {
 342         sprintf(name, "%s %s", "dupli_alloc", memh->name);
 343         newp = MEM_guarded_mallocN(memh->len, name);
 344       }
 345       else {
 346         sprintf(name, "%s %s", "dupli_alloc", memh->name);
 347         newp = MEM_guarded_mallocN_aligned(memh->len, (size_t)memh->alignment, name);
 348       }
 349
 350       if (newp == NULL)
 351         return NULL;
 352
 353       nmemh = newp;
 354       nmemh--;
 355
 356       nmemh->need_free_name = 1;
 357     }
 358 #endif
 359
 360     memcpy(newp, vmemh, memh->len);
 361   }
 362
 363   return newp;
 364 }
 365
 366 void *MEM_guarded_reallocN_id(void *vmemh, size_t len, const char *str)
 367 {
 368   void *newp = NULL;
 369
 370   if (vmemh) {
 371     MemHead *memh = vmemh;
 372     memh--;
 373
 374     if (LIKELY(memh->alignment == 0)) {
 375       newp = MEM_guarded_mallocN(len, memh->name);
 376     }
 377     else {
 378       newp = MEM_guarded_mallocN_aligned(len, (size_t)memh->alignment, memh->name);
 379     }
 380
 381     if (newp) {
 382       if (len < memh->len) {
 383         /* shrink */
 384         memcpy(newp, vmemh, len);
 385       }
 386       else {
 387         /* grow (or remain same size) */
 388         memcpy(newp, vmemh, memh->len);
 389       }
 390     }
 391
 392     MEM_guarded_freeN(vmemh);
 393   }
 394   else {
 395     newp = MEM_guarded_mallocN(len, str);
 396   }
 397
 398   return newp;
 399 }
 400
 401 void *MEM_guarded_recallocN_id(void *vmemh, size_t len, const char *str)
 402 {
 403   void *newp = NULL;
 404
 405   if (vmemh) {
 406     MemHead *memh = vmemh;
 407     memh--;
 408
 409     if (LIKELY(memh->alignment == 0)) {
 410       newp = MEM_guarded_mallocN(len, memh->name);
 411     }
 412     else {
 413       newp = MEM_guarded_mallocN_aligned(len, (size_t)memh->alignment, memh->name);
 414     }
 415
 416     if (newp) {
 417       if (len < memh->len) {
 418         /* shrink */
 419         memcpy(newp, vmemh, len);
 420       }
 421       else {
 422         memcpy(newp, vmemh, memh->len);
 423
 424         if (len > memh->len) {
 425           /* grow */
 426           /* zero new bytes */
 427           memset(((char *)newp) + memh->len, 0, len - memh->len);
 428         }
 429       }
 430     }
 431
 432     MEM_guarded_freeN(vmemh);
 433   }
 434   else {
 435     newp = MEM_guarded_callocN(len, str);
 436   }
 437
 438   return newp;
 439 }
 440
 441 #ifdef DEBUG_BACKTRACE
 442 #  if defined(__linux__) || defined(__APPLE__)
 443 static void make_memhead_backtrace(MemHead *memh)
 444 {
 445   memh->backtrace_size = backtrace(memh->backtrace, BACKTRACE_SIZE);
 446 }
 447
 448 static void print_memhead_backtrace(MemHead *memh)
 449 {
 450   char **strings;
 451   int i;
 452
 453   strings = backtrace_symbols(memh->backtrace, memh->backtrace_size);
 454   for (i = 0; i < memh->backtrace_size; i++) {
 455     print_error("  %s\n", strings[i]);
 456   }
 457
 458   free(strings);
 459 }
 460 #  else
 461 static void make_memhead_backtrace(MemHead *memh)
 462 {
 463   (void)memh; /* Ignored. */
 464 }
 465
 466 static void print_memhead_backtrace(MemHead *memh)
 467 {
 468   (void)memh; /* Ignored. */
 469 }
 470 #  endif /* defined(__linux__) || defined(__APPLE__) */
 471 #endif   /* DEBUG_BACKTRACE */
 472
 473 static void make_memhead_header(MemHead *memh, size_t len, const char *str)
 474 {
 475   MemTail *memt;
 476
 477   memh->tag1 = MEMTAG1;
 478   memh->name = str;
 479   memh->nextname = NULL;
 480   memh->len = len;
 481   memh->mmap = 0;
 482   memh->alignment = 0;
 483   memh->tag2 = MEMTAG2;
 484
 485 #ifdef DEBUG_MEMDUPLINAME
 486   memh->need_free_name = 0;
 487 #endif
 488
 489 #ifdef DEBUG_BACKTRACE
 490   make_memhead_backtrace(memh);
 491 #endif
 492
 493   memt = (MemTail *)(((char *)memh) + sizeof(MemHead) + len);
 494   memt->tag3 = MEMTAG3;
 495
 496   atomic_add_and_fetch_u(&totblock, 1);
 497   atomic_add_and_fetch_z(&mem_in_use, len);
 498
 499   mem_lock_thread();
 500   addtail(membase, &memh->next);
 501   if (memh->next) {
 502     memh->nextname = MEMNEXT(memh->next)->name;
 503   }
 504   peak_mem = mem_in_use > peak_mem ? mem_in_use : peak_mem;
 505   mem_unlock_thread();
 506 }
 507
 508 void *MEM_guarded_mallocN(size_t len, const char *str)
 509 {
 510   MemHead *memh;
 511
 512   len = SIZET_ALIGN_4(len);
 513
 514   memh = (MemHead *)malloc(len + sizeof(MemHead) + sizeof(MemTail));
 515
 516   if (LIKELY(memh)) {
 517     make_memhead_header(memh, len, str);
 518     if (UNLIKELY(malloc_debug_memset && len))
 519       memset(memh + 1, 255, len);
 520
 521 #ifdef DEBUG_MEMCOUNTER
 522     if (_mallocn_count == DEBUG_MEMCOUNTER_ERROR_VAL)
 523       memcount_raise(__func__);
 524     memh->_count = _mallocn_count++;
 525 #endif
 526     return (++memh);
 527   }
 528   print_error("Malloc returns null: len=" SIZET_FORMAT " in %s, total %u\n",
 529               SIZET_ARG(len),
 530               str,
 531               (unsigned int)mem_in_use);
 532   return NULL;
 533 }
 534
 535 void *MEM_guarded_malloc_arrayN(size_t len, size_t size, const char *str)
 536 {
 537   size_t total_size;
 538   if (UNLIKELY(!MEM_size_safe_multiply(len, size, &total_size))) {
 539     print_error(
 540         "Malloc array aborted due to integer overflow: "
 541         "len=" SIZET_FORMAT "x" SIZET_FORMAT " in %s, total %u\n",
 542         SIZET_ARG(len),
 543         SIZET_ARG(size),
 544         str,
 545         (unsigned int)mem_in_use);
 546     abort();
 547     return NULL;
 548   }
 549
 550   return MEM_guarded_mallocN(total_size, str);
 551 }
 552
 553 void *MEM_guarded_mallocN_aligned(size_t len, size_t alignment, const char *str)
 554 {
 555   /* We only support alignment to a power of two. */
 556   assert(IS_POW2(alignment));
 557
 558   /* Use a minimal alignment of 8. Otherwise MEM_guarded_freeN thinks it is an illegal pointer. */
 559   if (alignment < 8) {
 560     alignment = 8;
 561   }
 562
 563   /* It's possible that MemHead's size is not properly aligned,
 564    * do extra padding to deal with this.
 565    *
 566    * We only support small alignments which fits into short in
 567    * order to save some bits in MemHead structure.
 568    */
 569   size_t extra_padding = MEMHEAD_ALIGN_PADDING(alignment);
 570
 571   /* Huge alignment values doesn't make sense and they
 572    * wouldn't fit into 'short' used in the MemHead.
 573    */
 574   assert(alignment < 1024);
 575
 576   len = SIZET_ALIGN_4(len);
 577
 578   MemHead *memh = (MemHead *)aligned_malloc(
 579       len + extra_padding + sizeof(MemHead) + sizeof(MemTail), alignment);
 580
 581   if (LIKELY(memh)) {
 582     /* We keep padding in the beginning of MemHead,
 583      * this way it's always possible to get MemHead
 584      * from the data pointer.
 585      */
 586     memh = (MemHead *)((char *)memh + extra_padding);
 587
 588     make_memhead_header(memh, len, str);
 589     memh->alignment = (short)alignment;
 590     if (UNLIKELY(malloc_debug_memset && len))
 591       memset(memh + 1, 255, len);
 592
 593 #ifdef DEBUG_MEMCOUNTER
 594     if (_mallocn_count == DEBUG_MEMCOUNTER_ERROR_VAL)
 595       memcount_raise(__func__);
 596     memh->_count = _mallocn_count++;
 597 #endif
 598     return (++memh);
 599   }
 600   print_error("aligned_malloc returns null: len=" SIZET_FORMAT " in %s, total %u\n",
 601               SIZET_ARG(len),
 602               str,
 603               (unsigned int)mem_in_use);
 604   return NULL;
 605 }
 606
 607 void *MEM_guarded_callocN(size_t len, const char *str)
 608 {
 609   MemHead *memh;
 610
 611   len = SIZET_ALIGN_4(len);
 612
 613   memh = (MemHead *)calloc(len + sizeof(MemHead) + sizeof(MemTail), 1);
 614
 615   if (memh) {
 616     make_memhead_header(memh, len, str);
 617 #ifdef DEBUG_MEMCOUNTER
 618     if (_mallocn_count == DEBUG_MEMCOUNTER_ERROR_VAL)
 619       memcount_raise(__func__);
 620     memh->_count = _mallocn_count++;
 621 #endif
 622     return (++memh);
 623   }
 624   print_error("Calloc returns null: len=" SIZET_FORMAT " in %s, total %u\n",
 625               SIZET_ARG(len),
 626               str,
 627               (unsigned int)mem_in_use);
 628   return NULL;
 629 }
 630
 631 void *MEM_guarded_calloc_arrayN(size_t len, size_t size, const char *str)
 632 {
 633   size_t total_size;
 634   if (UNLIKELY(!MEM_size_safe_multiply(len, size, &total_size))) {
 635     print_error(
 636         "Calloc array aborted due to integer overflow: "
 637         "len=" SIZET_FORMAT "x" SIZET_FORMAT " in %s, total %u\n",
 638         SIZET_ARG(len),
 639         SIZET_ARG(size),
 640         str,
 641         (unsigned int)mem_in_use);
 642     abort();
 643     return NULL;
 644   }
 645
 646   return MEM_guarded_callocN(total_size, str);
 647 }
 648
 649 /* note; mmap returns zero'd memory */
 650 void *MEM_guarded_mapallocN(size_t len, const char *str)
 651 {
 652   MemHead *memh;
 653
 654   /* on 64 bit, simply use calloc instead, as mmap does not support
 655    * allocating > 4 GB on Windows. the only reason mapalloc exists
 656    * is to get around address space limitations in 32 bit OSes. */
 657   if (sizeof(void *) >= 8)
 658     return MEM_guarded_callocN(len, str);
 659
 660   len = SIZET_ALIGN_4(len);
 661
 662 #if defined(WIN32)
 663   /* our windows mmap implementation is not thread safe */
 664   mem_lock_thread();
 665 #endif
 666   memh = mmap(NULL,
 667               len + sizeof(MemHead) + sizeof(MemTail),
 668               PROT_READ | PROT_WRITE,
 669               MAP_SHARED | MAP_ANON,
 670               -1,
 671               0);
 672 #if defined(WIN32)
 673   mem_unlock_thread();
 674 #endif
 675
 676   if (memh != (MemHead *)-1) {
 677     make_memhead_header(memh, len, str);
 678     memh->mmap = 1;
 679     atomic_add_and_fetch_z(&mmap_in_use, len);
 680     mem_lock_thread();
 681     peak_mem = mmap_in_use > peak_mem ? mmap_in_use : peak_mem;
 682     mem_unlock_thread();
 683 #ifdef DEBUG_MEMCOUNTER
 684     if (_mallocn_count == DEBUG_MEMCOUNTER_ERROR_VAL)
 685       memcount_raise(__func__);
 686     memh->_count = _mallocn_count++;
 687 #endif
 688     return (++memh);
 689   }
 690   else {
 691     print_error(
 692         "Mapalloc returns null, fallback to regular malloc: "
 693         "len=" SIZET_FORMAT " in %s, total %u\n",
 694         SIZET_ARG(len),
 695         str,
 696         (unsigned int)mmap_in_use);
 697     return MEM_guarded_callocN(len, str);
 698   }
 699 }
 700
 701 /* Memory statistics print */
 702 typedef struct MemPrintBlock {
 703   const char *name;
 704   uintptr_t len;
 705   int items;
 706 } MemPrintBlock;
 707
 708 static int compare_name(const void *p1, const void *p2)
 709 {
 710   const MemPrintBlock *pb1 = (const MemPrintBlock *)p1;
 711   const MemPrintBlock *pb2 = (const MemPrintBlock *)p2;
 712
 713   return strcmp(pb1->name, pb2->name);
 714 }
 715
 716 static int compare_len(const void *p1, const void *p2)
 717 {
 718   const MemPrintBlock *pb1 = (const MemPrintBlock *)p1;
 719   const MemPrintBlock *pb2 = (const MemPrintBlock *)p2;
 720
 721   if (pb1->len < pb2->len)
 722     return 1;
 723   else if (pb1->len == pb2->len)
 724     return 0;
 725   else
 726     return -1;
 727 }
 728
 729 void MEM_guarded_printmemlist_stats(void)
 730 {
 731   MemHead *membl;
 732   MemPrintBlock *pb, *printblock;
 733   unsigned int totpb, a, b;
 734   size_t mem_in_use_slop = 0;
 735
 736   mem_lock_thread();
 737
 738   if (totblock != 0) {
 739     /* put memory blocks into array */
 740     printblock = malloc(sizeof(MemPrintBlock) * totblock);
 741
 742     if (UNLIKELY(!printblock)) {
 743       mem_unlock_thread();
 744       print_error("malloc returned null while generating stats");
 745       return;
 746     }
 747   }
 748   else {
 749     printblock = NULL;
 750   }
 751
 752   pb = printblock;
 753   totpb = 0;
 754
 755   membl = membase->first;
 756   if (membl)
 757     membl = MEMNEXT(membl);
 758
 759   while (membl && pb) {
 760     pb->name = membl->name;
 761     pb->len = membl->len;
 762     pb->items = 1;
 763
 764     totpb++;
 765     pb++;
 766
 767 #ifdef USE_MALLOC_USABLE_SIZE
 768     if (!membl->mmap && membl->alignment == 0) {
 769       mem_in_use_slop += (sizeof(MemHead) + sizeof(MemTail) + malloc_usable_size((void *)membl)) -
 770                          membl->len;
 771     }
 772 #endif
 773
 774     if (membl->next)
 775       membl = MEMNEXT(membl->next);
 776     else
 777       break;
 778   }
 779
 780   /* sort by name and add together blocks with the same name */
 781   if (totpb > 1) {
 782     qsort(printblock, totpb, sizeof(MemPrintBlock), compare_name);
 783   }
 784
 785   for (a = 0, b = 0; a < totpb; a++) {
 786     if (a == b) {
 787       continue;
 788     }
 789     else if (strcmp(printblock[a].name, printblock[b].name) == 0) {
 790       printblock[b].len += printblock[a].len;
 791       printblock[b].items++;
 792     }
 793     else {
 794       b++;
 795       memcpy(&printblock[b], &printblock[a], sizeof(MemPrintBlock));
 796     }
 797   }
 798   totpb = b + 1;
 799
 800   /* sort by length and print */
 801   if (totpb > 1) {
 802     qsort(printblock, totpb, sizeof(MemPrintBlock), compare_len);
 803   }
 804
 805   printf("\ntotal memory len: %.3f MB\n", (double)mem_in_use / (double)(1024 * 1024));
 806   printf("peak memory len: %.3f MB\n", (double)peak_mem / (double)(1024 * 1024));
 807   printf("slop memory len: %.3f MB\n", (double)mem_in_use_slop / (double)(1024 * 1024));
 808   printf(" ITEMS TOTAL-MiB AVERAGE-KiB TYPE\n");
 809   for (a = 0, pb = printblock; a < totpb; a++, pb++) {
 810     printf("%6d (%8.3f  %8.3f) %s\n",
 811            pb->items,
 812            (double)pb->len / (double)(1024 * 1024),
 813            (double)pb->len / 1024.0 / (double)pb->items,
 814            pb->name);
 815   }
 816
 817   if (printblock != NULL) {
 818     free(printblock);
 819   }
 820
 821   mem_unlock_thread();
 822
 823 #ifdef HAVE_MALLOC_STATS
 824   printf("System Statistics:\n");
 825   malloc_stats();
 826 #endif
 827 }
 828
 829 static const char mem_printmemlist_pydict_script[] =
 830     "mb_userinfo = {}\n"
 831     "totmem = 0\n"
 832     "for mb_item in membase:\n"
 833     "    mb_item_user_size = mb_userinfo.setdefault(mb_item['name'], [0,0])\n"
 834     "    mb_item_user_size[0] += 1 # Add a user\n"
 835     "    mb_item_user_size[1] += mb_item['len'] # Increment the size\n"
 836     "    totmem += mb_item['len']\n"
 837     "print('(membase) items:', len(membase), '| unique-names:',\n"
 838     "      len(mb_userinfo), '| total-mem:', totmem)\n"
 839     "mb_userinfo_sort = list(mb_userinfo.items())\n"
 840     "for sort_name, sort_func in (('size', lambda a: -a[1][1]),\n"
 841     "                             ('users', lambda a: -a[1][0]),\n"
 842     "                             ('name', lambda a: a[0])):\n"
 843     "    print('\\nSorting by:', sort_name)\n"
 844     "    mb_userinfo_sort.sort(key = sort_func)\n"
 845     "    for item in mb_userinfo_sort:\n"
 846     "        print('name:%%s, users:%%i, len:%%i' %%\n"
 847     "              (item[0], item[1][0], item[1][1]))\n";
 848
 849 /* Prints in python syntax for easy */
 850 static void MEM_guarded_printmemlist_internal(int pydict)
 851 {
 852   MemHead *membl;
 853
 854   mem_lock_thread();
 855
 856   membl = membase->first;
 857   if (membl)
 858     membl = MEMNEXT(membl);
 859
 860   if (pydict) {
 861     print_error("# membase_debug.py\n");
 862     print_error("membase = [\n");
 863   }
 864   while (membl) {
 865     if (pydict) {
 866       print_error("    {'len':" SIZET_FORMAT
 867                   ", "
 868                   "'name':'''%s''', "
 869                   "'pointer':'%p'},\n",
 870                   SIZET_ARG(membl->len),
 871                   membl->name,
 872                   (void *)(membl + 1));
 873     }
 874     else {
 875 #ifdef DEBUG_MEMCOUNTER
 876       print_error("%s len: " SIZET_FORMAT " %p, count: %d\n",
 877                   membl->name,
 878                   SIZET_ARG(membl->len),
 879                   membl + 1,
 880                   membl->_count);
 881 #else
 882       print_error("%s len: " SIZET_FORMAT " %p\n",
 883                   membl->name,
 884                   SIZET_ARG(membl->len),
 885                   (void *)(membl + 1));
 886 #endif
 887 #ifdef DEBUG_BACKTRACE
 888       print_memhead_backtrace(membl);
 889 #endif
 890     }
 891     if (membl->next)
 892       membl = MEMNEXT(membl->next);
 893     else
 894       break;
 895   }
 896   if (pydict) {
 897     print_error("]\n\n");
 898     print_error(mem_printmemlist_pydict_script);
 899   }
 900
 901   mem_unlock_thread();
 902 }
 903
 904 void MEM_guarded_callbackmemlist(void (*func)(void *))
 905 {
 906   MemHead *membl;
 907
 908   mem_lock_thread();
 909
 910   membl = membase->first;
 911   if (membl)
 912     membl = MEMNEXT(membl);
 913
 914   while (membl) {
 915     func(membl + 1);
 916     if (membl->next)
 917       membl = MEMNEXT(membl->next);
 918     else
 919       break;
 920   }
 921
 922   mem_unlock_thread();
 923 }
 924
 925 #if 0
 926 short MEM_guarded_testN(void *vmemh)
 927 {
 928   MemHead *membl;
 929
 930   mem_lock_thread();
 931
 932   membl = membase->first;
 933   if (membl)
 934     membl = MEMNEXT(membl);
 935
 936   while (membl) {
 937     if (vmemh == membl + 1) {
 938       mem_unlock_thread();
 939       return 1;
 940     }
 941
 942     if (membl->next)
 943       membl = MEMNEXT(membl->next);
 944     else
 945       break;
 946   }
 947
 948   mem_unlock_thread();
 949
 950   print_error("Memoryblock %p: pointer not in memlist\n", vmemh);
 951   return 0;
 952 }
 953 #endif
 954
 955 void MEM_guarded_printmemlist(void)
 956 {
 957   MEM_guarded_printmemlist_internal(0);
 958 }
 959 void MEM_guarded_printmemlist_pydict(void)
 960 {
 961   MEM_guarded_printmemlist_internal(1);
 962 }
 963
 964 void MEM_guarded_freeN(void *vmemh)
 965 {
 966   MemTail *memt;
 967   MemHead *memh = vmemh;
 968   const char *name;
 969
 970   if (memh == NULL) {
 971     MemorY_ErroR("free", "attempt to free NULL pointer");
 972     /* print_error(err_stream, "%d\n", (memh+4000)->tag1); */
 973     return;
 974   }
 975
 976   if (sizeof(intptr_t) == 8) {
 977     if (((intptr_t)memh) & 0x7) {
 978       MemorY_ErroR("free", "attempt to free illegal pointer");
 979       return;
 980     }
 981   }
 982   else {
 983     if (((intptr_t)memh) & 0x3) {
 984       MemorY_ErroR("free", "attempt to free illegal pointer");
 985       return;
 986     }
 987   }
 988
 989   memh--;
 990   if (memh->tag1 == MEMFREE && memh->tag2 == MEMFREE) {
 991     MemorY_ErroR(memh->name, "double free");
 992     return;
 993   }
 994
 995   if ((memh->tag1 == MEMTAG1) && (memh->tag2 == MEMTAG2) && ((memh->len & 0x3) == 0)) {
 996     memt = (MemTail *)(((char *)memh) + sizeof(MemHead) + memh->len);
 997     if (memt->tag3 == MEMTAG3) {
 998
 999       memh->tag1 = MEMFREE;
1000       memh->tag2 = MEMFREE;
1001       memt->tag3 = MEMFREE;
1002       /* after tags !!! */
1003       rem_memblock(memh);
1004
1005       return;
1006     }
1007     MemorY_ErroR(memh->name, "end corrupt");
1008     name = check_memlist(memh);
1009     if (name != NULL) {
1010       if (name != memh->name)
1011         MemorY_ErroR(name, "is also corrupt");
1012     }
1013   }
1014   else {
1015     mem_lock_thread();
1016     name = check_memlist(memh);
1017     mem_unlock_thread();
1018     if (name == NULL)
1019       MemorY_ErroR("free", "pointer not in memlist");
1020     else
1021       MemorY_ErroR(name, "error in header");
1022   }
1023
1024   totblock--;
1025   /* here a DUMP should happen */
1026
1027   return;
1028 }
1029
1030 /* --------------------------------------------------------------------- */
1031 /* local functions                                                       */
1032 /* --------------------------------------------------------------------- */
1033
1034 static void addtail(volatile localListBase *listbase, void *vlink)
1035 {
1036   struct localLink *link = vlink;
1037
1038   /* for a generic API error checks here is fine but
1039    * the limited use here they will never be NULL */
1040 #if 0
1041   if (link == NULL)
1042     return;
1043   if (listbase == NULL)
1044     return;
1045 #endif
1046
1047   link->next = NULL;
1048   link->prev = listbase->last;
1049
1050   if (listbase->last)
1051     ((struct localLink *)listbase->last)->next = link;
1052   if (listbase->first == NULL)
1053     listbase->first = link;
1054   listbase->last = link;
1055 }
1056
1057 static void remlink(volatile localListBase *listbase, void *vlink)
1058 {
1059   struct localLink *link = vlink;
1060
1061   /* for a generic API error checks here is fine but
1062    * the limited use here they will never be NULL */
1063 #if 0
1064   if (link == NULL)
1065     return;
1066   if (listbase == NULL)
1067     return;
1068 #endif
1069
1070   if (link->next)
1071     link->next->prev = link->prev;
1072   if (link->prev)
1073     link->prev->next = link->next;
1074
1075   if (listbase->last == link)
1076     listbase->last = link->prev;
1077   if (listbase->first == link)
1078     listbase->first = link->next;
1079 }
1080
1081 static void rem_memblock(MemHead *memh)
1082 {
1083   mem_lock_thread();
1084   remlink(membase, &memh->next);
1085   if (memh->prev) {
1086     if (memh->next)
1087       MEMNEXT(memh->prev)->nextname = MEMNEXT(memh->next)->name;
1088     else
1089       MEMNEXT(memh->prev)->nextname = NULL;
1090   }
1091   mem_unlock_thread();
1092
1093   atomic_sub_and_fetch_u(&totblock, 1);
1094   atomic_sub_and_fetch_z(&mem_in_use, memh->len);
1095
1096 #ifdef DEBUG_MEMDUPLINAME
1097   if (memh->need_free_name)
1098     free((char *)memh->name);
1099 #endif
1100
1101   if (memh->mmap) {
1102     atomic_sub_and_fetch_z(&mmap_in_use, memh->len);
1103 #if defined(WIN32)
1104     /* our windows mmap implementation is not thread safe */
1105     mem_lock_thread();
1106 #endif
1107     if (munmap(memh, memh->len + sizeof(MemHead) + sizeof(MemTail)))
1108       printf("Couldn't unmap memory %s\n", memh->name);
1109 #if defined(WIN32)
1110     mem_unlock_thread();
1111 #endif
1112   }
1113   else {
1114     if (UNLIKELY(malloc_debug_memset && memh->len))
1115       memset(memh + 1, 255, memh->len);
1116     if (LIKELY(memh->alignment == 0)) {
1117       free(memh);
1118     }
1119     else {
1120       aligned_free(MEMHEAD_REAL_PTR(memh));
1121     }
1122   }
1123 }
1124
1125 static void MemorY_ErroR(const char *block, const char *error)
1126 {
1127   print_error("Memoryblock %s: %s\n", block, error);
1128
1129 #ifdef WITH_ASSERT_ABORT
1130   abort();
1131 #endif
1132 }
1133
1134 static const char *check_memlist(MemHead *memh)
1135 {
1136   MemHead *forw, *back, *forwok, *backok;
1137   const char *name;
1138
1139   forw = membase->first;
1140   if (forw)
1141     forw = MEMNEXT(forw);
1142   forwok = NULL;
1143   while (forw) {
1144     if (forw->tag1 != MEMTAG1 || forw->tag2 != MEMTAG2)
1145       break;
1146     forwok = forw;
1147     if (forw->next)
1148       forw = MEMNEXT(forw->next);
1149     else
1150       forw = NULL;
1151   }
1152
1153   back = (MemHead *)membase->last;
1154   if (back)
1155     back = MEMNEXT(back);
1156   backok = NULL;
1157   while (back) {
1158     if (back->tag1 != MEMTAG1 || back->tag2 != MEMTAG2)
1159       break;
1160     backok = back;
1161     if (back->prev)
1162       back = MEMNEXT(back->prev);
1163     else
1164       back = NULL;
1165   }
1166
1167   if (forw != back)
1168     return ("MORE THAN 1 MEMORYBLOCK CORRUPT");
1169
1170   if (forw == NULL && back == NULL) {
1171     /* no wrong headers found then but in search of memblock */
1172
1173     forw = membase->first;
1174     if (forw)
1175       forw = MEMNEXT(forw);
1176     forwok = NULL;
1177     while (forw) {
1178       if (forw == memh)
1179         break;
1180       if (forw->tag1 != MEMTAG1 || forw->tag2 != MEMTAG2)
1181         break;
1182       forwok = forw;
1183       if (forw->next)
1184         forw = MEMNEXT(forw->next);
1185       else
1186         forw = NULL;
1187     }
1188     if (forw == NULL)
1189       return NULL;
1190
1191     back = (MemHead *)membase->last;
1192     if (back)
1193       back = MEMNEXT(back);
1194     backok = NULL;
1195     while (back) {
1196       if (back == memh)
1197         break;
1198       if (back->tag1 != MEMTAG1 || back->tag2 != MEMTAG2)
1199         break;
1200       backok = back;
1201       if (back->prev)
1202         back = MEMNEXT(back->prev);
1203       else
1204         back = NULL;
1205     }
1206   }
1207
1208   if (forwok)
1209     name = forwok->nextname;
1210   else
1211     name = "No name found";
1212
1213   if (forw == memh) {
1214     /* to be sure but this block is removed from the list */
1215     if (forwok) {
1216       if (backok) {
1217         forwok->next = (MemHead *)&backok->next;
1218         backok->prev = (MemHead *)&forwok->next;
1219         forwok->nextname = backok->name;
1220       }
1221       else {
1222         forwok->next = NULL;
1223         membase->last = (struct localLink *)&forwok->next;
1224       }
1225     }
1226     else {
1227       if (backok) {
1228         backok->prev = NULL;
1229         membase->first = &backok->next;
1230       }
1231       else {
1232         membase->first = membase->last = NULL;
1233       }
1234     }
1235   }
1236   else {
1237     MemorY_ErroR(name, "Additional error in header");
1238     return ("Additional error in header");
1239   }
1240
1241   return (name);
1242 }
1243
1244 size_t MEM_guarded_get_peak_memory(void)
1245 {
1246   size_t _peak_mem;
1247
1248   mem_lock_thread();
1249   _peak_mem = peak_mem;
1250   mem_unlock_thread();
1251
1252   return _peak_mem;
1253 }
1254
1255 void MEM_guarded_reset_peak_memory(void)
1256 {
1257   mem_lock_thread();
1258   peak_mem = mem_in_use;
1259   mem_unlock_thread();
1260 }
1261
1262 size_t MEM_guarded_get_memory_in_use(void)
1263 {
1264   size_t _mem_in_use;
1265
1266   mem_lock_thread();
1267   _mem_in_use = mem_in_use;
1268   mem_unlock_thread();
1269
1270   return _mem_in_use;
1271 }
1272
1273 size_t MEM_guarded_get_mapped_memory_in_use(void)
1274 {
1275   size_t _mmap_in_use;
1276
1277   mem_lock_thread();
1278   _mmap_in_use = mmap_in_use;
1279   mem_unlock_thread();
1280
1281   return _mmap_in_use;
1282 }
1283
1284 unsigned int MEM_guarded_get_memory_blocks_in_use(void)
1285 {
1286   unsigned int _totblock;
1287
1288   mem_lock_thread();
1289   _totblock = totblock;
1290   mem_unlock_thread();
1291
1292   return _totblock;
1293 }
1294
1295 #ifndef NDEBUG
1296 const char *MEM_guarded_name_ptr(void *vmemh)
1297 {
1298   if (vmemh) {
1299     MemHead *memh = vmemh;
1300     memh--;
1301     return memh->name;
1302   }
1303   else {
1304     return "MEM_guarded_name_ptr(NULL)";
1305   }
1306 }
1307 #endif /* NDEBUG */