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