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