Fix for key map python file export and load
[blender.git] / intern / guardedalloc / intern / mallocn.c
1 /**
2  * $Id$
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
18  *
19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): none yet.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /**
30
31  * $Id$
32  * Copyright (C) 2001 NaN Technologies B.V.
33  * Guarded memory allocation, and boundary-write detection.
34  */
35
36 #include <stdlib.h>
37 #include <string.h>     /* memcpy */
38 #include <stdarg.h>
39
40 /* mmap exception */
41 #if defined(WIN32)
42 #include <sys/types.h>
43 #include "mmap_win.h"
44 #else
45 #include <sys/types.h>
46 #include <sys/mman.h>
47 #endif
48
49 #include "MEM_guardedalloc.h"
50
51 /* --------------------------------------------------------------------- */
52 /* Data definition                                                       */
53 /* --------------------------------------------------------------------- */
54 /* all memory chunks are put in linked lists */
55 typedef struct localLink
56 {
57         struct localLink *next,*prev;
58 } localLink;
59
60 typedef struct localListBase 
61 {
62         void *first, *last;
63 } localListBase;
64
65         /* note: keep this struct aligned (e.g., irix/gcc) - Hos */
66 typedef struct MemHead {
67         int tag1;
68         int len;
69         struct MemHead *next,*prev;
70         const char * name;
71         const char * nextname;
72         int tag2;
73         int mmap;       /* if true, memory was mmapped */
74 } MemHead;
75
76 typedef struct MemTail {
77         int tag3, pad;
78 } MemTail;
79
80
81 /* --------------------------------------------------------------------- */
82 /* local functions                                                       */
83 /* --------------------------------------------------------------------- */
84
85 static void addtail(volatile localListBase *listbase, void *vlink);
86 static void remlink(volatile localListBase *listbase, void *vlink);
87 static void rem_memblock(MemHead *memh);
88 static void MemorY_ErroR(const char *block, const char *error);
89 static const char *check_memlist(MemHead *memh);
90
91 /* --------------------------------------------------------------------- */
92 /* locally used defines                                                  */
93 /* --------------------------------------------------------------------- */
94
95 #if defined( __sgi) || defined (__sun) || defined (__sun__) || defined (__sparc) || defined (__sparc__) || defined (__PPC__) || (defined (__APPLE__) && !defined(__LITTLE_ENDIAN__))
96 #define MAKE_ID(a,b,c,d) ( (int)(a)<<24 | (int)(b)<<16 | (c)<<8 | (d) )
97 #else
98 #define MAKE_ID(a,b,c,d) ( (int)(d)<<24 | (int)(c)<<16 | (b)<<8 | (a) )
99 #endif
100
101 #define MEMTAG1 MAKE_ID('M', 'E', 'M', 'O')
102 #define MEMTAG2 MAKE_ID('R', 'Y', 'B', 'L')
103 #define MEMTAG3 MAKE_ID('O', 'C', 'K', '!')
104 #define MEMFREE MAKE_ID('F', 'R', 'E', 'E')
105
106 #define MEMNEXT(x) ((MemHead *)(((char *) x) - ((char *) & (((MemHead *)0)->next))))
107         
108 /* --------------------------------------------------------------------- */
109 /* vars                                                                  */
110 /* --------------------------------------------------------------------- */
111         
112
113 static volatile int totblock= 0;
114 static volatile uintptr_t mem_in_use= 0, mmap_in_use= 0;
115
116 static volatile struct localListBase _membase;
117 static volatile struct localListBase *membase = &_membase;
118 static void (*error_callback)(char *) = NULL;
119 static void (*thread_lock_callback)(void) = NULL;
120 static void (*thread_unlock_callback)(void) = NULL;
121
122 static int malloc_debug_memset= 0;
123
124 #ifdef malloc
125 #undef malloc
126 #endif
127
128 #ifdef calloc
129 #undef calloc
130 #endif
131
132 #ifdef free
133 #undef free
134 #endif
135
136
137 /* --------------------------------------------------------------------- */
138 /* implementation                                                        */
139 /* --------------------------------------------------------------------- */
140
141 static void print_error(const char *str, ...)
142 {
143         char buf[1024];
144         va_list ap;
145
146         va_start(ap, str);
147         vsprintf(buf, str, ap);
148         va_end(ap);
149
150         if (error_callback) error_callback(buf);
151 }
152
153 static void mem_lock_thread()
154 {
155         if (thread_lock_callback)
156                 thread_lock_callback();
157 }
158
159 static void mem_unlock_thread()
160 {
161         if (thread_unlock_callback)
162                 thread_unlock_callback();
163 }
164
165 int MEM_check_memory_integrity()
166 {
167         const char* err_val = NULL;
168         MemHead* listend;
169         /* check_memlist starts from the front, and runs until it finds
170          * the requested chunk. For this test, that's the last one. */
171         listend = membase->last;
172         
173         err_val = check_memlist(listend);
174
175         if (err_val == 0) return 0;
176         return 1;
177 }
178
179
180 void MEM_set_error_callback(void (*func)(char *))
181 {
182         error_callback = func;
183 }
184
185 void MEM_set_lock_callback(void (*lock)(void), void (*unlock)(void))
186 {
187         thread_lock_callback = lock;
188         thread_unlock_callback = unlock;
189 }
190
191 void MEM_set_memory_debug(void)
192 {
193         malloc_debug_memset= 1;
194 }
195
196 int MEM_allocN_len(void *vmemh)
197 {
198         if (vmemh) {
199                 MemHead *memh= vmemh;
200         
201                 memh--;
202                 return memh->len;
203         } else
204                 return 0;
205 }
206
207 void *MEM_dupallocN(void *vmemh)
208 {
209         void *newp= NULL;
210         
211         if (vmemh) {
212                 MemHead *memh= vmemh;
213                 memh--;
214                 
215                 if(memh->mmap)
216                         newp= MEM_mapallocN(memh->len, "dupli_mapalloc");
217                 else
218                         newp= MEM_mallocN(memh->len, "dupli_alloc");
219
220                 if (newp == NULL) return NULL;
221
222                 memcpy(newp, vmemh, memh->len);
223         }
224
225         return newp;
226 }
227
228 static void make_memhead_header(MemHead *memh, unsigned int len, const char *str)
229 {
230         MemTail *memt;
231         
232         memh->tag1 = MEMTAG1;
233         memh->name = str;
234         memh->nextname = 0;
235         memh->len = len;
236         memh->mmap = 0;
237         memh->tag2 = MEMTAG2;
238         
239         memt = (MemTail *)(((char *) memh) + sizeof(MemHead) + len);
240         memt->tag3 = MEMTAG3;
241         
242         addtail(membase,&memh->next);
243         if (memh->next) memh->nextname = MEMNEXT(memh->next)->name;
244         
245         totblock++;
246         mem_in_use += len;
247 }
248
249 void *MEM_mallocN(unsigned int len, const char *str)
250 {
251         MemHead *memh;
252
253         mem_lock_thread();
254
255         len = (len + 3 ) & ~3;  /* allocate in units of 4 */
256         
257         memh= (MemHead *)malloc(len+sizeof(MemHead)+sizeof(MemTail));
258
259         if(memh) {
260                 make_memhead_header(memh, len, str);
261                 mem_unlock_thread();
262                 if(malloc_debug_memset && len)
263                         memset(memh+1, 255, len);
264                 return (++memh);
265         }
266         mem_unlock_thread();
267         print_error("Malloc returns nill: len=%d in %s, total %u\n",len, str, mem_in_use);
268         return NULL;
269 }
270
271 void *MEM_callocN(unsigned int len, const char *str)
272 {
273         MemHead *memh;
274
275         mem_lock_thread();
276
277         len = (len + 3 ) & ~3;  /* allocate in units of 4 */
278
279         memh= (MemHead *)calloc(len+sizeof(MemHead)+sizeof(MemTail),1);
280
281         if(memh) {
282                 make_memhead_header(memh, len, str);
283                 mem_unlock_thread();
284                 return (++memh);
285         }
286         mem_unlock_thread();
287         print_error("Calloc returns nill: len=%d in %s, total %u\n",len, str, mem_in_use);
288         return 0;
289 }
290
291 /* note; mmap returns zero'd memory */
292 void *MEM_mapallocN(unsigned int len, const char *str)
293 {
294         MemHead *memh;
295
296         mem_lock_thread();
297         
298         len = (len + 3 ) & ~3;  /* allocate in units of 4 */
299         
300 #ifdef __sgi
301         {
302 #include <fcntl.h>
303
304           int fd;
305           fd = open("/dev/zero", O_RDWR);
306
307           memh= mmap(0, len+sizeof(MemHead)+sizeof(MemTail),
308                      PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
309           close(fd);
310         }
311 #else
312         memh= mmap(0, len+sizeof(MemHead)+sizeof(MemTail),
313                    PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANON, -1, 0);
314 #endif
315
316         if(memh!=(MemHead *)-1) {
317                 make_memhead_header(memh, len, str);
318                 memh->mmap= 1;
319                 mmap_in_use += len;
320                 mem_unlock_thread();
321                 return (++memh);
322         }
323         else {
324                 mem_unlock_thread();
325                 print_error("Mapalloc returns nill, fallback to regular malloc: len=%d in %s, total %u\n",len, str, mmap_in_use);
326                 return MEM_callocN(len, str);
327         }
328 }
329
330 /* Memory statistics print */
331 typedef struct MemPrintBlock {
332         const char *name;
333         uintptr_t len;
334         int items;
335 } MemPrintBlock;
336
337 static int compare_name(const void *p1, const void *p2)
338 {
339         const MemPrintBlock *pb1= (const MemPrintBlock*)p1;
340         const MemPrintBlock *pb2= (const MemPrintBlock*)p2;
341
342         return strcmp(pb1->name, pb2->name);
343 }
344
345 static int compare_len(const void *p1, const void *p2)
346 {
347         const MemPrintBlock *pb1= (const MemPrintBlock*)p1;
348         const MemPrintBlock *pb2= (const MemPrintBlock*)p2;
349
350         if(pb1->len < pb2->len)
351                 return 1;
352         else if(pb1->len == pb2->len)
353                 return 0;
354         else
355                 return -1;
356 }
357
358 void MEM_printmemlist_stats()
359 {
360         MemHead *membl;
361         MemPrintBlock *pb, *printblock;
362         int totpb, a, b;
363
364         mem_lock_thread();
365
366         /* put memory blocks into array */
367         printblock= malloc(sizeof(MemPrintBlock)*totblock);
368
369         pb= printblock;
370         totpb= 0;
371
372         membl = membase->first;
373         if (membl) membl = MEMNEXT(membl);
374
375         while(membl) {
376                 pb->name= membl->name;
377                 pb->len= membl->len;
378                 pb->items= 1;
379
380                 totpb++;
381                 pb++;
382
383                 if(membl->next)
384                         membl= MEMNEXT(membl->next);
385                 else break;
386         }
387
388         /* sort by name and add together blocks with the same name */
389         qsort(printblock, totpb, sizeof(MemPrintBlock), compare_name);
390         for(a=0, b=0; a<totpb; a++) {
391                 if(a == b) {
392                         continue;
393                 }
394                 else if(strcmp(printblock[a].name, printblock[b].name) == 0) {
395                         printblock[b].len += printblock[a].len;
396                         printblock[b].items++;
397                 }
398                 else {
399                         b++;
400                         memcpy(&printblock[b], &printblock[a], sizeof(MemPrintBlock));
401                 }
402         }
403         totpb= b+1;
404
405         /* sort by length and print */
406         qsort(printblock, totpb, sizeof(MemPrintBlock), compare_len);
407         printf("\ntotal memory len: %.3f MB\n", (double)mem_in_use/(double)(1024*1024));
408         for(a=0, pb=printblock; a<totpb; a++, pb++)
409                 printf("%s items: %d, len: %.3f MB\n", pb->name, pb->items, (double)pb->len/(double)(1024*1024));
410
411         free(printblock);
412         
413         mem_unlock_thread();
414 }
415
416 /* Prints in python syntax for easy */
417 static void MEM_printmemlist_internal( int pydict )
418 {
419         MemHead *membl;
420
421         mem_lock_thread();
422
423         membl = membase->first;
424         if (membl) membl = MEMNEXT(membl);
425         
426         if (pydict) {
427                 print_error("# membase_debug.py\n");
428                 print_error("membase = [\\\n");
429         }
430         while(membl) {
431                 if (pydict) {
432                         fprintf(stderr, "{'len':%i, 'name':'''%s''', 'pointer':'%p'},\\\n", membl->len, membl->name, membl+1);
433                 } else {
434                         print_error("%s len: %d %p\n",membl->name,membl->len, membl+1);
435                 }
436                 if(membl->next)
437                         membl= MEMNEXT(membl->next);
438                 else break;
439         }
440         if (pydict) {
441                 fprintf(stderr, "]\n\n");
442                 fprintf(stderr,
443 "mb_userinfo = {}\n"
444 "totmem = 0\n"
445 "for mb_item in membase:\n"
446 "\tmb_item_user_size = mb_userinfo.setdefault(mb_item['name'], [0,0])\n"
447 "\tmb_item_user_size[0] += 1 # Add a user\n"
448 "\tmb_item_user_size[1] += mb_item['len'] # Increment the size\n"
449 "\ttotmem += mb_item['len']\n"
450 "print '(membase) items:', len(membase), '| unique-names:', len(mb_userinfo), '| total-mem:', totmem\n"
451 "mb_userinfo_sort = mb_userinfo.items()\n"
452 "for sort_name, sort_func in (('size', lambda a: -a[1][1]), ('users', lambda a: -a[1][0]), ('name', lambda a: a[0])):\n"
453 "\tprint '\\nSorting by:', sort_name\n"
454 "\tmb_userinfo_sort.sort(key = sort_func)\n"
455 "\tfor item in mb_userinfo_sort:\n"
456 "\t\tprint 'name:%%s, users:%%i, len:%%i' %% (item[0], item[1][0], item[1][1])\n"
457                 );
458         }
459         
460         mem_unlock_thread();
461 }
462
463 void MEM_callbackmemlist(void (*func)(void*)) {
464         MemHead *membl;
465
466         mem_lock_thread();
467
468         membl = membase->first;
469         if (membl) membl = MEMNEXT(membl);
470
471         while(membl) {
472                 func(membl+1);
473                 if(membl->next)
474                         membl= MEMNEXT(membl->next);
475                 else break;
476         }
477
478         mem_unlock_thread();
479 }
480
481 short MEM_testN(void *vmemh) {
482         MemHead *membl;
483
484         mem_lock_thread();
485
486         membl = membase->first;
487         if (membl) membl = MEMNEXT(membl);
488
489         while(membl) {
490                 if (vmemh == membl+1)
491                         return 1;
492
493                 if(membl->next)
494                         membl= MEMNEXT(membl->next);
495                 else break;
496         }
497
498         mem_unlock_thread();
499
500         print_error("Memoryblock %p: pointer not in memlist\n", vmemh);
501         return 0;
502 }
503
504 void MEM_printmemlist( void ) {
505         MEM_printmemlist_internal(0);
506 }
507 void MEM_printmemlist_pydict( void ) {
508         MEM_printmemlist_internal(1);
509 }
510
511 short MEM_freeN(void *vmemh)            /* anders compileertie niet meer */
512 {
513         short error = 0;
514         MemTail *memt;
515         MemHead *memh= vmemh;
516         const char *name;
517
518         if (memh == NULL){
519                 MemorY_ErroR("free","attempt to free NULL pointer");
520                 /* print_error(err_stream, "%d\n", (memh+4000)->tag1); */
521                 return(-1);
522         }
523
524         if(sizeof(intptr_t)==8) {
525                 if (((intptr_t) memh) & 0x7) {
526                         MemorY_ErroR("free","attempt to free illegal pointer");
527                         return(-1);
528                 }
529         }
530         else {
531                 if (((intptr_t) memh) & 0x3) {
532                         MemorY_ErroR("free","attempt to free illegal pointer");
533                         return(-1);
534                 }
535         }
536         
537         memh--;
538         if(memh->tag1 == MEMFREE && memh->tag2 == MEMFREE) {
539                 MemorY_ErroR(memh->name,"double free");
540                 return(-1);
541         }
542
543         mem_lock_thread();
544         if ((memh->tag1 == MEMTAG1) && (memh->tag2 == MEMTAG2) && ((memh->len & 0x3) == 0)) {
545                 memt = (MemTail *)(((char *) memh) + sizeof(MemHead) + memh->len);
546                 if (memt->tag3 == MEMTAG3){
547                         
548                         memh->tag1 = MEMFREE;
549                         memh->tag2 = MEMFREE;
550                         memt->tag3 = MEMFREE;
551                         /* after tags !!! */
552                         rem_memblock(memh);
553
554                         mem_unlock_thread();
555                         
556                         return(0);
557                 }
558                 error = 2;
559                 MemorY_ErroR(memh->name,"end corrupt");
560                 name = check_memlist(memh);
561                 if (name != 0){
562                         if (name != memh->name) MemorY_ErroR(name,"is also corrupt");
563                 }
564         } else{
565                 error = -1;
566                 name = check_memlist(memh);
567                 if (name == 0)
568                         MemorY_ErroR("free","pointer not in memlist");
569                 else
570                         MemorY_ErroR(name,"error in header");
571         }
572
573         totblock--;
574         /* here a DUMP should happen */
575
576         mem_unlock_thread();
577
578         return(error);
579 }
580
581 /* --------------------------------------------------------------------- */
582 /* local functions                                                       */
583 /* --------------------------------------------------------------------- */
584
585 static void addtail(volatile localListBase *listbase, void *vlink)
586 {
587         struct localLink *link= vlink;
588
589         if (link == 0) return;
590         if (listbase == 0) return;
591
592         link->next = 0;
593         link->prev = listbase->last;
594
595         if (listbase->last) ((struct localLink *)listbase->last)->next = link;
596         if (listbase->first == 0) listbase->first = link;
597         listbase->last = link;
598 }
599
600 static void remlink(volatile localListBase *listbase, void *vlink)
601 {
602         struct localLink *link= vlink;
603
604         if (link == 0) return;
605         if (listbase == 0) return;
606
607         if (link->next) link->next->prev = link->prev;
608         if (link->prev) link->prev->next = link->next;
609
610         if (listbase->last == link) listbase->last = link->prev;
611         if (listbase->first == link) listbase->first = link->next;
612 }
613
614 static void rem_memblock(MemHead *memh)
615 {
616     remlink(membase,&memh->next);
617     if (memh->prev) {
618         if (memh->next) 
619                         MEMNEXT(memh->prev)->nextname = MEMNEXT(memh->next)->name;
620         else 
621                         MEMNEXT(memh->prev)->nextname = NULL;
622     }
623
624     totblock--;
625     mem_in_use -= memh->len;
626    
627     if(memh->mmap) {
628         mmap_in_use -= memh->len;
629         if (munmap(memh, memh->len + sizeof(MemHead) + sizeof(MemTail)))
630             printf("Couldn't unmap memory %s\n", memh->name);
631     }
632     else {
633                 if(malloc_debug_memset && memh->len)
634                         memset(memh+1, 255, memh->len);
635         free(memh);
636         }
637 }
638
639 static void MemorY_ErroR(const char *block, const char *error)
640 {
641         print_error("Memoryblock %s: %s\n",block, error);
642 }
643
644 static const char *check_memlist(MemHead *memh)
645 {
646         MemHead *forw,*back,*forwok,*backok;
647         const char *name;
648
649         forw = membase->first;
650         if (forw) forw = MEMNEXT(forw);
651         forwok = 0;
652         while(forw){
653                 if (forw->tag1 != MEMTAG1 || forw->tag2 != MEMTAG2) break;
654                 forwok = forw;
655                 if (forw->next) forw = MEMNEXT(forw->next);
656                 else forw = 0;
657         }
658
659         back = (MemHead *) membase->last;
660         if (back) back = MEMNEXT(back);
661         backok = 0;
662         while(back){
663                 if (back->tag1 != MEMTAG1 || back->tag2 != MEMTAG2) break;
664                 backok = back;
665                 if (back->prev) back = MEMNEXT(back->prev);
666                 else back = 0;
667         }
668
669         if (forw != back) return ("MORE THAN 1 MEMORYBLOCK CORRUPT");
670
671         if (forw == 0 && back == 0){
672                 /* geen foute headers gevonden dan maar op zoek naar memblock*/
673
674                 forw = membase->first;
675                 if (forw) forw = MEMNEXT(forw);
676                 forwok = 0;
677                 while(forw){
678                         if (forw == memh) break;
679                         if (forw->tag1 != MEMTAG1 || forw->tag2 != MEMTAG2) break;
680                         forwok = forw;
681                         if (forw->next) forw = MEMNEXT(forw->next);
682                         else forw = 0;
683                 }
684                 if (forw == 0) return (0);
685
686                 back = (MemHead *) membase->last;
687                 if (back) back = MEMNEXT(back);
688                 backok = 0;
689                 while(back){
690                         if (back == memh) break;
691                         if (back->tag1 != MEMTAG1 || back->tag2 != MEMTAG2) break;
692                         backok = back;
693                         if (back->prev) back = MEMNEXT(back->prev);
694                         else back = 0;
695                 }
696         }
697
698         if (forwok) name = forwok->nextname;
699         else name = "No name found";
700
701         if (forw == memh){
702                 /* voor alle zekerheid wordt dit block maar uit de lijst gehaald */
703                 if (forwok){
704                         if (backok){
705                                 forwok->next = (MemHead *)&backok->next;
706                                 backok->prev = (MemHead *)&forwok->next;
707                                 forwok->nextname = backok->name;
708                         } else{
709                                 forwok->next = 0;
710                                 membase->last = (struct localLink *) &forwok->next; 
711 /*                              membase->last = (struct Link *) &forwok->next; */
712                         }
713                 } else{
714                         if (backok){
715                                 backok->prev = 0;
716                                 membase->first = &backok->next;
717                         } else{
718                                 membase->first = membase->last = 0;
719                         }
720                 }
721         } else{
722                 MemorY_ErroR(name,"Additional error in header");
723                 return("Additional error in header");
724         }
725
726         return(name);
727 }
728
729 uintptr_t MEM_get_memory_in_use(void)
730 {
731         uintptr_t _mem_in_use;
732
733         mem_lock_thread();
734         _mem_in_use= mem_in_use;
735         mem_unlock_thread();
736
737         return _mem_in_use;
738 }
739
740 uintptr_t MEM_get_mapped_memory_in_use(void)
741 {
742         uintptr_t _mmap_in_use;
743
744         mem_lock_thread();
745         _mmap_in_use= mmap_in_use;
746         mem_unlock_thread();
747
748         return _mmap_in_use;
749 }
750
751 int MEM_get_memory_blocks_in_use(void)
752 {
753         int _totblock;
754
755         mem_lock_thread();
756         _totblock= totblock;
757         mem_unlock_thread();
758
759         return _totblock;
760 }
761
762 /* eof */