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