CMake: add WITH_LINKER_LLD option for unix platforms
[blender-staging.git] / 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 */