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