doc: Add serial to list of ci file reserved words
[charm.git] / src / conv-core / memory-charmdebug.c
1 /*
2  * Filippo's charm debug memory module, gioachin@uiuc.edu, 2005/10
3  * based on Orion's memory-leak.c
4  *
5  * This special version of malloc() and company is meant to be used in
6  * conjunction with the parallel debugger CharmDebug.
7  *
8  * Functionalities provided:
9  * - detect multiple delete on a pointer
10  * - stacktrace for all memory allocated
11  * - division of the memory in differnt types of allocations
12  * - sweep of the memory searching for leaks
13  */
14
15 #if ! CMK_MEMORY_BUILD_OS
16 /* Use Gnumalloc as meta-meta malloc fallbacks (mm_*) */
17 #include "memory-gnu.c"
18 #endif
19 #include "tracec.h"
20 #include <sys/mman.h>
21
22 /* Utilities needed by the code */
23 #include "ckhashtable.h"
24
25 /*#include "pup_c.h" */
26
27 #include "crc32.h"
28
29 #if ! CMK_CHARMDEBUG
30 #error "charmdebug is not enabled (e.g. when building with-production)"
31 static void *meta_malloc(size_t size);
32 static void *meta_calloc(size_t nelem, size_t size);
33 static void *meta_realloc(void *oldBuffer, size_t newSize);
34 static void *meta_memalign(size_t align, size_t size);
35 static void *meta_valloc(size_t size);
36 #else
37
38 typedef struct _Slot Slot;
39 typedef struct _SlotStack SlotStack;
40
41 int nextChareID;
42 extern int memory_chare_id;
43
44 int memory_charmdebug_internal = 0;
45
46 /**
47  * Struct Slot contains all of the information about a malloc buffer except
48  * for the contents of its memory.
49  */
50 struct _Slot {
51 #ifdef CMK_SEPARATE_SLOT
52   char *userData;
53 #else
54   /*Doubly-linked allocated block list*/
55   Slot *next;
56   Slot *prev;
57 #endif
58
59   /*The number of bytes of user data*/
60   int userSize;
61
62 #define FLAGS_MASK        0xFF
63 #define BLOCK_PROTECTED   0x80
64 #define MODIFIED          0x40
65 #define NEW_BLOCK         0x20
66 #define LEAK_CLEAN        0x10
67 #define LEAK_FLAG         0x8
68 #define UNKNOWN_TYPE      0x0
69 #define SYSTEM_TYPE       0x1
70 #define USER_TYPE         0x2
71 #define CHARE_TYPE        0x3
72 #define MESSAGE_TYPE      0x4
73   /* A magic number field, to verify this is an actual malloc'd buffer, and what
74      type of allocation it is. The last 4 bits of the magic number are used to
75      define a classification of mallocs. */
76 #define SLOTMAGIC            0x8402a500
77 #define SLOTMAGIC_VALLOC     0x7402a500
78 #define SLOTMAGIC_FREED      0xDEADBEEF
79   int magic;
80
81   int chareID;
82   /* Controls the number of stack frames to print out. Should be always odd, so
83      the total size of this struct becomes multiple of 8 bytes everywhere */
84 //#define STACK_LEN 15
85   int stackLen;
86   void **from;
87
88   /* Pointer to extra stacktrace, when the user requested more trace */
89   SlotStack *extraStack;
90
91   /* CRC32 checksums */
92   unsigned int slotCRC;
93   unsigned int userCRC;
94 };
95
96 struct _SlotStack {
97   char *protectedMemory;
98   int protectedMemoryLength;
99   /* empty for the moment, to be filled when needed */
100 };
101
102 /********* List of allocated memory *********/
103
104 /* First memory slot */
105 #ifdef CMK_SEPARATE_SLOT
106 CkHashtable_c block_slots = NULL;
107 #else
108 Slot slot_first_storage = {&slot_first_storage, &slot_first_storage};
109 Slot *slot_first = &slot_first_storage;
110 #endif
111
112 int memory_allocated_user_total;
113 int get_memory_allocated_user_total() {return memory_allocated_user_total;}
114
115 void *lastMemoryAllocated = NULL;
116 Slot **allocatedSince = NULL;
117 int allocatedSinceSize = 0;
118 int allocatedSinceMaxSize = 0;
119 int saveAllocationHistory = 0;
120
121 /* Convert a slot to a user address */
122 static char *SlotToUser(Slot *s) {
123 #ifdef CMK_SEPARATE_SLOT
124   return s->userData;
125 #else
126   return ((char *)s)+sizeof(Slot);
127 #endif
128 }
129
130
131 /* Convert a user address to a slot. The parameter "user" must be at the
132  * beginning of the allocated block */
133 static Slot *UserToSlot(void *user) {
134 #ifdef CMK_SEPARATE_SLOT
135   return (Slot *)CkHashtableGet(block_slots, &user);
136 #else
137   char *cu=(char *)user;
138   Slot *s=(Slot *)(cu-sizeof(Slot));
139   return s;
140 #endif
141 }
142
143 static int isLeakSlot(Slot *s) {
144   return s->magic & LEAK_FLAG;
145 }
146
147 static int isProtected(Slot *s) {
148   return s->magic & BLOCK_PROTECTED;
149 }
150
151 int Slot_ChareOwner(void *s) {
152   return ((Slot*)s)->chareID;
153 }
154
155 int Slot_AllocatedSize(void *s) {
156   return ((Slot*)s)->userSize;
157 }
158
159 int Slot_StackTrace(void *s, void ***stack) {
160   *stack = ((Slot*)s)->from;
161   return ((Slot*)s)->stackLen;
162 }
163
164 static void printSlot(Slot *s) {
165   CmiPrintf("[%d] Leaked block of %d bytes at %p:\n",
166             CmiMyPe(), s->userSize, SlotToUser(s));
167   CmiBacktracePrint(s->from,s->stackLen);
168 }
169
170 /********* Cpd routines for pupping data to the debugger *********/
171
172 /** Returns the number of total blocks of memory allocated */
173 size_t cpd_memory_length(void *lenParam) {
174   size_t n=0;
175 #ifdef CMK_SEPARATE_SLOT
176   n = CkHashtableSize(block_slots) - 1;
177 #else
178   Slot *cur = slot_first->next;
179   while (cur != slot_first) {
180     n++;
181     cur = cur->next;
182   }
183 #endif
184   return n;
185 }
186
187 /** PUP a single slot of memory for the debugger. This includes the information
188  * about the slot (like size and location), but not the allocated data itself. */
189 #ifdef CMK_SEPARATE_SLOT
190 void cpd_memory_single_pup(CkHashtable_c h, pup_er p) {
191   memory_charmdebug_internal = 1;
192   CkHashtableIterator_c hashiter = CkHashtableGetIterator(h);
193   void *key;
194   Slot *cur;
195   //int counter=0;
196   while ((cur = (Slot *)CkHashtableIteratorNext(hashiter, &key)) != NULL) {
197     if (pup_isPacking(p) && cur->userData == lastMemoryAllocated) continue;
198     //counter++;
199 #else
200 void cpd_memory_single_pup(Slot* list, pup_er p) {
201   Slot *cur = list->next;
202   /* Stupid hack to avoid sending the memory we just allocated for this packing,
203      otherwise the lengths will mismatch */
204   if (pup_isPacking(p)) cur = cur->next;
205   for ( ; cur != list; cur = cur->next) {
206 #endif
207     int i;
208     int flags;
209     void *loc = SlotToUser(cur);
210     CpdListBeginItem(p, 0);
211     pup_comment(p, "loc");
212     pup_pointer(p, &loc);
213     pup_comment(p, "size");
214     pup_int(p, &cur->userSize);
215     pup_comment(p, "flags");
216     flags = cur->magic & FLAGS_MASK;
217     pup_int(p, &flags);
218     pup_comment(p, "chare");
219     pup_int(p, &cur->chareID);
220     pup_comment(p, "stack");
221     //for (i=0; i<STACK_LEN; ++i) {
222     //  if (cur->from[i] <= 0) break;
223       //      if (cur->from[i] > 0) pup_uint(p, (unsigned int*)&cur->from[i]);
224       //      else break;
225     //}
226     if (cur->from != NULL)
227       pup_pointers(p, cur->from, cur->stackLen);
228     else {
229       void *myNULL = NULL;
230       printf("Block %p has no stack!\n",cur);
231       pup_pointer(p, &myNULL);
232     }
233   }
234   /*CmiPrintf("counter=%d\n",counter);*/
235   memory_charmdebug_internal = 0;
236 }
237
238 /** PUP the entire information about the allocated memory to the debugger */
239 void cpd_memory_pup(void *itemParam, pup_er p, CpdListItemsRequest *req) {
240   CpdListBeginItem(p, 0);
241   pup_comment(p, "name");
242   pup_chars(p, "memory", strlen("memory"));
243   pup_comment(p, "slots");
244   pup_syncComment(p, pup_sync_begin_array, 0);
245 #ifdef CMK_SEPARATE_SLOT
246   cpd_memory_single_pup(block_slots, p);
247 #else
248   cpd_memory_single_pup(slot_first, p);
249 #endif
250   pup_syncComment(p, pup_sync_end_array, 0);
251 }
252
253 /*
254 void check_memory_leaks(CpdListItemsRequest *);
255 void cpd_memory_leak(void *iterParam, pup_er p, CpdListItemsRequest *req) {
256   if (pup_isSizing(p)) {
257     // let's perform the memory leak checking. This is the first step in the
258     // packing, where we size, in the second step we pack and we avoid doing
259     // this check again.
260     check_memory_leaks(req);
261   }
262   cpd_memory_pup(iterParam, p, req);
263 }
264 */
265
266 size_t cpd_memory_getLength(void *lenParam) { return 1; }
267 /** Returns the content of a block of memory (i.e the user data).
268     This request must always be at the beginning of an allocated block
269     (not for example an object part of an array) */
270 void cpd_memory_get(void *iterParam, pup_er p, CpdListItemsRequest *req) {
271   void *userData = (void*)(((unsigned int)req->lo) + (((unsigned long)req->hi)<<32));
272   Slot *sl = UserToSlot(userData);
273   CpdListBeginItem(p, 0);
274   pup_comment(p, "size");
275   //printf("value: %x %x %x %d\n",sl->magic, sl->magic&~FLAGS_MASK, SLOTMAGIC, ((sl->magic&~FLAGS_MASK) != SLOTMAGIC));
276   if ((sl->magic&~FLAGS_MASK) != SLOTMAGIC) {
277     int zero = 0;
278     pup_int(p, &zero);
279   } else {
280     pup_int(p, &sl->userSize);
281     pup_comment(p, "value");
282     pup_bytes(p, userData, sl->userSize);
283   }
284 }
285
286 /********* Heap Checking ***********/
287
288 int charmEnvelopeSize = 0;
289
290 #include "pcqueue.h"
291
292 #ifdef CMK_SEPARATE_SLOT
293 #define SLOTSPACE 0
294 #define SLOT_ITERATE_START(scanner) \
295   { \
296     CkHashtableIterator_c hashiter = CkHashtableGetIterator(block_slots); \
297     void *key; \
298     while ((scanner = (Slot *)CkHashtableIteratorNext(hashiter, &key)) != NULL) {
299 #define SLOT_ITERATE_END \
300     } \
301     CkHashtableDestroyIterator(hashiter); \
302   }
303 #else
304 #define SLOTSPACE sizeof(Slot)
305 #define SLOT_ITERATE_START(scanner) \
306   for (scanner=slot_first->next; scanner!=slot_first; scanner=scanner->next) {
307 #define SLOT_ITERATE_END   }
308 #endif
309
310 /** Perform a scan of all the memory to find all the memory that is reacheable
311  * from either the stack or the global variables. */
312 // FIXME: this function assumes that all memory is allocated in slot_unknown!
313 void check_memory_leaks(LeakSearchInfo *info) {
314   memory_charmdebug_internal = 1;
315   //FILE* fd=fopen("check_memory_leaks", "w");
316   // Step 1)
317   // index all memory into a CkHashtable, with a scan of 4 bytes.
318   CkHashtable_c table;
319   PCQueue inProgress = PCQueueCreate();
320   Slot *sl, **fnd, *found;
321   char *scanner;
322   char *begin_stack, *end_stack;
323   //char *begin_data, *end_data;
324   //char *begin_bss, *end_bss;
325   int growing_dimension = 0;
326
327   // copy all the memory from "slot_first" to "leaking"
328
329   Slot *slold1=0, *slold2=0, *slold3=0;
330   table = CkCreateHashtable_pointer(sizeof(char *), 10000);
331   SLOT_ITERATE_START(sl)
332     // index the i-th memory slot
333     //printf("hashing slot %p\n",sl);
334     char *ptr;
335     sl->magic |= LEAK_FLAG;
336     if (info->quick > 0) {
337       //CmiPrintf("checking memory fast\n");
338       // means index only specific offsets of the memory region
339       ptr = SlotToUser(sl);
340       char **object = (char**)CkHashtablePut(table, &ptr);
341       *object = (char*)sl;
342       ptr += 4;
343       object = (char**)CkHashtablePut(table, &ptr);
344       *object = (char*)sl;
345       // beginning of converse header
346       ptr += sizeof(CmiChunkHeader) - 4;
347       if (ptr < SlotToUser(sl)+sizeof(Slot)+sl->userSize) {
348         object = (char**)CkHashtablePut(table, &ptr);
349         *object = (char*)sl;
350       }
351       // beginning of charm header
352       ptr += CmiReservedHeaderSize;
353       if (ptr < SlotToUser(sl)+sizeof(Slot)+sl->userSize) {
354         object = (char**)CkHashtablePut(table, &ptr);
355         *object = (char*)sl;
356       }
357       // beginning of ampi header
358       ptr += charmEnvelopeSize - CmiReservedHeaderSize;
359       if (ptr < SlotToUser(sl)+sizeof(Slot)+sl->userSize) {
360         object = (char**)CkHashtablePut(table, &ptr);
361         *object = (char*)sl;
362       }
363     } else {
364       //CmiPrintf("checking memory extensively\n");
365       // means index every fourth byte of the memory region
366       for (ptr = SlotToUser(sl); ptr <= SlotToUser(sl)+sl->userSize; ptr+=sizeof(char*)) {
367         //printf("memory %p\n",ptr);
368         //growing_dimension++;
369         //if ((growing_dimension&0xFF) == 0) printf("inserted %d objects\n",growing_dimension);
370         char **object = (char**)CkHashtablePut(table, &ptr);
371         *object = (char*)sl;
372       }
373     }
374     slold3 = slold2;
375     slold2 = slold1;
376     slold1 = sl;
377   SLOT_ITERATE_END
378
379   // Step 2)
380   // start the check with the stack and the global data. The stack is found
381   // through the current pointer, going up until 16 bits filling (considering
382   // the stack grows toward decreasing addresses). The pointers to the global
383   // data (segments .data and .bss) are passed in with "req" as the "extra"
384   // field, with the structure "begin .data", "end .data", "begin .bss", "end .bss".
385   begin_stack = (char*)&table;
386   end_stack = (char*)memory_stack_top;
387   /*if (req->extraLen != 4*4 / *sizeof(char*) FIXME: assumes 64 bit addresses of .data and .bss are small enough * /) {
388     CmiPrintf("requested for a memory leak check with wrong information! %d bytes\n",req->extraLen);
389   }*/
390   /*if (sizeof(char*) == 4) {
391     / * 32 bit addresses; for 64 bit machines it assumes the following addresses were small enough * /
392     begin_data = (char*)ntohl(((int*)(req->extra))[0]);
393     end_data = (char*)ntohl(((int*)(req->extra))[1]) - sizeof(char*) + 1;
394     begin_bss = (char*)ntohl(((int*)(req->extra))[2]);
395     end_bss = (char*)ntohl(((int*)(req->extra))[3]) - sizeof(char*) + 1;
396   / *} else {
397     CmiAbort("not ready yet");
398     begin_data = ntohl(((char**)(req->extra))[0]);
399     end_data = ntohl(((char**)(req->extra))[1]) - sizeof(char*) + 1;
400     begin_bss = ntohl(((char**)(req->extra))[2]);
401     end_bss = ntohl(((char**)(req->extra))[3]) - sizeof(char*) + 1;
402   }*/
403   printf("scanning stack from %p to %p\n", begin_stack, end_stack);
404   for (scanner = begin_stack; scanner < end_stack; scanner+=sizeof(char*)) {
405     fnd = (Slot**)CkHashtableGet(table, scanner);
406     //if (fnd != NULL) printf("scanning stack %p, %d\n",*fnd,isLeakSlot(*fnd));
407     if (fnd != NULL && isLeakSlot(*fnd)) {
408       found = *fnd;
409       /* mark slot as not leak */
410       //printf("stack pointing to %p\n",found+1);
411       found->magic &= ~LEAK_FLAG;
412       /* move the slot into inProgress */
413       PCQueuePush(inProgress, (char*)found);
414     }
415   }
416   printf("scanning data from %p to %p\n", info->begin_data, info->end_data);
417   for (scanner = info->begin_data; scanner < info->end_data; scanner+=sizeof(char*)) {
418     //fprintf(fd, "scanner = %p\n",scanner);
419     //fflush(fd);
420     fnd = (Slot**)CkHashtableGet(table, scanner);
421     //if (fnd != NULL) printf("scanning data %p, %d\n",*fnd,isLeakSlot(*fnd));
422     if (fnd != NULL && isLeakSlot(*fnd)) {
423       found = *fnd;
424       /* mark slot as not leak */
425       //printf("data pointing to %p\n",found+1);
426       found->magic &= ~LEAK_FLAG;
427       /* move the slot into inProgress */
428       PCQueuePush(inProgress, (char*)found);
429     }
430   }
431   printf("scanning bss from %p to %p\n", info->begin_bss, info->end_bss);
432   for (scanner = info->begin_bss; scanner < info->end_bss; scanner+=sizeof(char*)) {
433     //printf("bss: %p %p\n",scanner,*(char**)scanner);
434     fnd = (Slot**)CkHashtableGet(table, scanner);
435     //if (fnd != NULL) printf("scanning bss %p, %d\n",*fnd,isLeakSlot(*fnd));
436     if (fnd != NULL && isLeakSlot(*fnd)) {
437       found = *fnd;
438       /* mark slot as not leak */
439       //printf("bss pointing to %p\n",found+1);
440       found->magic &= ~LEAK_FLAG;
441       /* move the slot into inProgress */
442       PCQueuePush(inProgress, (char*)found);
443     }
444   }
445
446   // Step 3)
447   // continue iteratively to check the memory by sweeping it with the
448   // "inProcess" list
449   while ((sl = (Slot *)PCQueuePop(inProgress)) != NULL) {
450     //printf("scanning memory %p of size %d\n",sl,sl->userSize);
451     /* scan through this memory and pick all the slots which are still leaking
452        and add them to the inProgress list */
453     if (sl->extraStack != NULL && sl->extraStack->protectedMemory != NULL) mprotect(sl->extraStack->protectedMemory, sl->extraStack->protectedMemoryLength, PROT_READ);
454     for (scanner = SlotToUser(sl); scanner < SlotToUser(sl)+sl->userSize-sizeof(char*)+1; scanner+=sizeof(char*)) {
455       fnd = (Slot**)CkHashtableGet(table, scanner);
456       //if (fnd != NULL) printf("scanning heap %p, %d\n",*fnd,isLeakSlot(*fnd));
457       if (fnd != NULL && isLeakSlot(*fnd)) {
458         found = *fnd;
459         /* mark slot as not leak */
460         //printf("heap pointing to %p\n",found+1);
461         found->magic &= ~LEAK_FLAG;
462         /* move the slot into inProgress */
463         PCQueuePush(inProgress, (char*)found);
464       }
465     }
466     if (sl->extraStack != NULL && sl->extraStack->protectedMemory != NULL) mprotect(sl->extraStack->protectedMemory, sl->extraStack->protectedMemoryLength, PROT_NONE);
467   }
468
469   // Step 4)
470   // move back all the entries in leaking to slot_first
471   /*if (leaking.next != &leaking) {
472     leaking.next->prev = slot_first;
473     leaking.prev->next = slot_first->next;
474     slot_first->next->prev = leaking.prev;
475     slot_first->next = leaking.next;
476   }*/
477
478
479   // mark all the entries in the leaking list as leak, and put them back
480   // into the main list
481   /*sl = leaking.next;
482   while (sl != &leaking) {
483     sl->magic | LEAK_FLAG;
484   }
485   if (leaking.next != &leaking) {
486     slot_first->next->prev = leaking.prev;
487     leaking.prev->next = slot_first->next;
488     leaking.next->prev = slot_first;
489     slot_first->next = leaking.next;
490   }
491   */
492
493   PCQueueDestroy(inProgress);
494   CkDeleteHashtable(table);
495
496   memory_charmdebug_internal = 0;
497 }
498
499 void CpdMemoryMarkClean(char *msg) {
500   Slot *sl;
501   /* The first byte of the data packet indicates if we want o mark or unmark */
502   if ((msg+CmiMsgHeaderSizeBytes)[0]) {
503     SLOT_ITERATE_START(sl)
504       sl->magic |= LEAK_CLEAN;
505     SLOT_ITERATE_END
506   } else {
507     SLOT_ITERATE_START(sl)
508       sl->magic &= ~LEAK_CLEAN;
509     SLOT_ITERATE_END
510   }
511   CmiFree(msg);
512 }
513
514 /****************** memory allocation tree ******************/
515
516 /* This allows the representation and creation of a tree where each node
517  * represents a line in the code part of a stack trace of a malloc. The node
518  * contains how much data has been allocated starting from that line of code,
519  * down the stack.
520  */
521
522 typedef struct _AllocationPoint AllocationPoint;
523
524 struct _AllocationPoint {
525   /* The stack pointer this allocation refers to */
526   void * key;
527   /* Pointer to the parent AllocationPoint of this AllocationPoint in the tree */
528   AllocationPoint * parent;
529   /* Pointer to the first child AllocationPoint in the tree */
530   AllocationPoint * firstChild;
531   /* Pointer to the sibling of this AllocationPoint (i.e the next child of the parent) */
532   AllocationPoint * sibling;
533   /* Pointer to the next AllocationPoint with the same key.
534    * There can be more than one AllocationPoint with the same key because the
535    * parent can be different. Used only in the hashtable. */
536   AllocationPoint * next;
537   /* Size of the memory allocate */
538   int size;
539   /* How many blocks have been allocated from this point */
540   int count;
541   /* Flags pertaining to the allocation point, currently only LEAK_FLAG */
542   char flags;
543 };
544
545 // pup a single AllocationPoint. The data structure must be already allocated
546 void pupAllocationPointSingle(pup_er p, AllocationPoint *node, int *numChildren) {
547   pup_pointer(p, &node->key);
548   pup_int(p, &node->size);
549   pup_int(p, &node->count);
550   pup_char(p, &node->flags);
551   if (pup_isUnpacking(p)) {
552     node->parent = NULL;
553     node->firstChild = NULL;
554     node->sibling = NULL;
555     node->next = NULL;
556   }
557   *numChildren = 0;
558   AllocationPoint *child;
559   for (child = node->firstChild; child != NULL; child = child->sibling) (*numChildren) ++;
560   pup_int(p, numChildren);
561
562 }
563
564 // TODO: the following pup does not work for unpacking!
565 void pupAllocationPoint(pup_er p, void *data) {
566   AllocationPoint *node = (AllocationPoint*)data;
567   int numChildren;
568   pupAllocationPointSingle(p, node, &numChildren);
569   AllocationPoint *child;
570   for (child = node->firstChild; child != NULL; child = child->sibling) {
571     pupAllocationPoint(p, child);
572   }
573 }
574
575 void deleteAllocationPoint(void *ptr) {
576   AllocationPoint *node = (AllocationPoint*)ptr;
577   AllocationPoint *child;
578   for (child = node->firstChild; child != NULL; child = child->sibling) deleteAllocationPoint(child);
579   BEFORE_MALLOC_CALL;
580   mm_free(node);
581   AFTER_MALLOC_CALL;
582 }
583
584 void printAllocationTree(AllocationPoint *node, FILE *fd, int depth) {
585   int i;
586   if (node==NULL) return;
587   int numChildren = 0;
588   AllocationPoint *child;
589   for (child = node->firstChild; child != NULL; child = child->sibling) numChildren ++;
590   for (i=0; i<depth; ++i) fprintf(fd, " ");
591   fprintf(fd, "node %p: bytes=%d, count=%d, child=%d\n",node->key,node->size,node->count,numChildren);
592   printAllocationTree(node->sibling, fd, depth);
593   printAllocationTree(node->firstChild, fd, depth+2);
594 }
595
596 AllocationPoint * CreateAllocationTree(int *nodesCount) {
597   Slot *scanner;
598   CkHashtable_c table;
599   int i, isnew;
600   AllocationPoint *parent, **start, *cur;
601   AllocationPoint *root = NULL;
602   int numNodes = 0;
603
604   table = CkCreateHashtable_pointer(sizeof(char *), 10000);
605
606   BEFORE_MALLOC_CALL;
607   root = (AllocationPoint*) mm_malloc(sizeof(AllocationPoint));
608   AFTER_MALLOC_CALL;
609   *(AllocationPoint**)CkHashtablePut(table, &numNodes) = root;
610   numNodes ++;
611   root->key = 0;
612   root->parent = NULL;
613   root->size = 0;
614   root->count = 0;
615   root->flags = 0;
616   root->firstChild = NULL;
617   root->sibling = NULL;
618   root->next = root;
619
620   SLOT_ITERATE_START(scanner)
621     parent = root;
622     for (i=scanner->stackLen-1; i>=0; --i) {
623       isnew = 0;
624       start = (AllocationPoint**)CkHashtableGet(table, &scanner->from[i]);
625       if (start == NULL) {
626         BEFORE_MALLOC_CALL;
627         cur = (AllocationPoint*) mm_malloc(sizeof(AllocationPoint));
628         AFTER_MALLOC_CALL;
629         numNodes ++;
630         isnew = 1;
631         cur->next = cur;
632         *(AllocationPoint**)CkHashtablePut(table, &scanner->from[i]) = cur;
633       } else {
634         for (cur = (*start)->next; cur != *start && cur->parent != parent; cur = cur->next);
635         if (cur->parent != parent) {
636           BEFORE_MALLOC_CALL;
637           cur = (AllocationPoint*) mm_malloc(sizeof(AllocationPoint));
638           AFTER_MALLOC_CALL;
639           numNodes ++;
640           isnew = 1;
641           cur->next = (*start)->next;
642           (*start)->next = cur;
643         }
644       }
645       // here "cur" points to the correct AllocationPoint for this stack frame
646       if (isnew) {
647         cur->key = scanner->from[i];
648         cur->parent = parent;
649         cur->size = 0;
650         cur->count = 0;
651         cur->flags = 0;
652         cur->firstChild = NULL;
653         //if (parent == NULL) {
654         //  cur->sibling = NULL;
655         //  CmiAssert(root == NULL);
656         //  root = cur;
657         //} else {
658           cur->sibling = parent->firstChild;
659           parent->firstChild = cur;
660         //}
661       }
662       cur->size += scanner->userSize;
663       cur->count ++;
664       cur->flags |= isLeakSlot(scanner);
665       parent = cur;
666     }
667   SLOT_ITERATE_END
668
669   char filename[100];
670   sprintf(filename, "allocationTree_%d", CmiMyPe());
671   FILE *fd = fopen(filename, "w");
672   fprintf(fd, "digraph %s {\n", filename);
673   CkHashtableIterator_c it = CkHashtableGetIterator(table);
674   AllocationPoint **startscan, *scan;
675   while ((startscan=(AllocationPoint**)CkHashtableIteratorNext(it,NULL))!=NULL) {
676     fprintf(fd, "\t\"n%p\" [label=\"%p\\nsize=%d\\ncount=%d\"];\n",*startscan,(*startscan)->key,
677           (*startscan)->size,(*startscan)->count);
678     for (scan = (*startscan)->next; scan != *startscan; scan = scan->next) {
679       fprintf(fd, "\t\"n%p\" [label=\"%p\\nsize=%d\\ncount=%d\"];\n",scan,scan->key,scan->size,scan->count);
680     }
681   }
682   CkHashtableIteratorSeekStart(it);
683   while ((startscan=(AllocationPoint**)CkHashtableIteratorNext(it,NULL))!=NULL) {
684     fprintf(fd, "\t\"n%p\" -> \"n%p\";\n",(*startscan)->parent,(*startscan));
685     for (scan = (*startscan)->next; scan != *startscan; scan = scan->next) {
686       fprintf(fd, "\t\"n%p\" -> \"n%p\";\n",scan->parent,scan);
687     }
688   }
689   fprintf(fd, "}\n");
690   fclose(fd);
691
692   sprintf(filename, "allocationTree_%d.tree", CmiMyPe());
693   fd = fopen(filename, "w");
694   printAllocationTree(root, fd, 0);
695   fclose(fd);
696
697   CkDeleteHashtable(table);
698   if (nodesCount != NULL) *nodesCount = numNodes;
699   return root;
700 }
701
702 void MergeAllocationTreeSingle(AllocationPoint *node, AllocationPoint *remote, int numChildren, pup_er p) {
703   AllocationPoint child;
704   int numChildChildren;
705   int i;
706   //pupAllocationPointSingle(p, &remote, &numChildren);
707   /* Update the node with the information coming from remote */
708   node->size += remote->size;
709   node->count += remote->count;
710   node->flags |= remote->flags;
711   /* Recursively merge the children */
712   for (i=0; i<numChildren; ++i) {
713     AllocationPoint *localChild;
714     pupAllocationPointSingle(p, &child, &numChildChildren);
715     /* Find the child in the local tree */
716     for (localChild = node->firstChild; localChild != NULL; localChild = localChild->sibling) {
717       if (localChild->key == child.key) {
718         break;
719       }
720     }
721     if (localChild == NULL) {
722       /* This child did not exist locally, allocate it */
723       BEFORE_MALLOC_CALL;
724       localChild = (AllocationPoint*) mm_malloc(sizeof(AllocationPoint));
725       AFTER_MALLOC_CALL;
726       localChild->key = child.key;
727       localChild->flags = 0;
728       localChild->count = 0;
729       localChild->size = 0;
730       localChild->firstChild = NULL;
731       localChild->next = NULL;
732       localChild->parent = node;
733       localChild->sibling = node->firstChild;
734       node->firstChild = localChild;
735     }
736     MergeAllocationTreeSingle(localChild, &child, numChildChildren, p);
737   }
738 }
739
740 void * MergeAllocationTree(int *size, void *data, void **remoteData, int numRemote) {
741   int i;
742   for (i=0; i<numRemote; ++i) {
743     pup_er p = pup_new_fromMem(remoteData[i]);
744     AllocationPoint root;
745     int numChildren;
746     pupAllocationPointSingle(p, &root, &numChildren);
747     MergeAllocationTreeSingle((AllocationPoint*)data, &root, numChildren, p);
748     pup_destroy(p);
749   }
750   return data;
751 }
752
753 /********************** Memory statistics ***********************/
754
755 /* Collect the statistics relative to the amount of memory allocated.
756  * Starts from the statistics of a single processor and combines them to contain
757  * all the processors in the application.
758  */
759
760 typedef struct MemStatSingle {
761   // [0] is total, [1] is the leaking part
762   int pe;
763   int sizes[2][5];
764   int counts[2][5];
765 } MemStatSingle;
766
767 typedef struct MemStat {
768   int count;
769   MemStatSingle array[1];
770 } MemStat;
771
772 void pupMemStat(pup_er p, void *st) {
773   int i;
774   MemStat *comb = (MemStat*)st;
775   pup_fmt_sync_begin_object(p);
776   pup_comment(p, "count");
777   pup_int(p, &comb->count);
778   pup_comment(p, "list");
779   pup_fmt_sync_begin_array(p);
780   for (i=0; i<comb->count; ++i) {
781     MemStatSingle *stat = &comb->array[i];
782     pup_fmt_sync_item(p);
783     pup_comment(p, "pe");
784     pup_int(p, &stat->pe);
785     pup_comment(p, "totalsize");
786     pup_ints(p, stat->sizes[0], 5);
787     pup_comment(p, "totalcount");
788     pup_ints(p, stat->counts[0], 5);
789     pup_comment(p, "leaksize");
790     pup_ints(p, stat->sizes[1], 5);
791     pup_comment(p, "leakcount");
792     pup_ints(p, stat->counts[1], 5);
793   }
794   pup_fmt_sync_end_array(p);
795   pup_fmt_sync_end_object(p);
796 }
797
798 void deleteMemStat(void *ptr) {
799   BEFORE_MALLOC_CALL;
800   mm_free(ptr);
801   AFTER_MALLOC_CALL;
802 }
803
804 static int memStatReturnOnlyOne = 1;
805 void * mergeMemStat(int *size, void *data, void **remoteData, int numRemote) {
806   int i,j,k;
807   if (memStatReturnOnlyOne) {
808     MemStatSingle *l = &((MemStat*) data)->array[0];
809     l->pe = -1;
810     MemStat r;
811     MemStatSingle *m = &r.array[0];
812     for (i=0; i<numRemote; ++i) {
813       pup_er p = pup_new_fromMem(remoteData[i]);
814       pupMemStat(p, &r);
815       for (j=0; j<2; ++j) {
816         for (k=0; k<5; ++k) {
817           l->sizes[j][k] += m->sizes[j][k];
818           l->counts[j][k] += m->counts[j][k];
819         }
820       }
821       pup_destroy(p);
822     }
823     return data;
824   } else {
825     MemStat *l = (MemStat*)data;
826     int count = l->count;
827     for (i=0; i<numRemote; ++i) count += ((MemStat*)remoteData[i])->count;
828     BEFORE_MALLOC_CALL;
829     MemStat *res = (MemStat*)mm_malloc(sizeof(MemStat) + (count-1)*sizeof(MemStatSingle));
830     AFTER_MALLOC_CALL;
831     memset(res, 0, sizeof(MemStat)+(count-1)*sizeof(MemStatSingle));
832     res->count = count;
833     memcpy(res->array, l->array, l->count*sizeof(MemStatSingle));
834     count = l->count;
835     MemStat r;
836     for (i=0; i<numRemote; ++i) {
837       pup_er p = pup_new_fromMem(remoteData[i]);
838       pupMemStat(p, &r);
839       memcpy(&res->array[count], r.array, r.count*sizeof(MemStatSingle));
840       count += r.count;
841       pup_destroy(p);
842     }
843     deleteMemStat(data);
844     return res;
845   }
846 }
847
848 MemStat * CreateMemStat() {
849   Slot *cur;
850   BEFORE_MALLOC_CALL;
851   MemStat *st = (MemStat*)mm_calloc(1, sizeof(MemStat));
852   AFTER_MALLOC_CALL;
853   st->count = 1;
854   MemStatSingle *stat = &st->array[0];
855   SLOT_ITERATE_START(cur)
856     stat->sizes[0][(cur->magic&0x7)] += cur->userSize;
857     stat->counts[0][(cur->magic&0x7)] ++;
858     if (cur->magic & 0x8) {
859       stat->sizes[1][(cur->magic&0x7)] += cur->userSize;
860       stat->counts[1][(cur->magic&0x7)] ++;
861     }
862   SLOT_ITERATE_END
863   stat->pe=CmiMyPe();
864   return st;
865 }
866
867
868 /*********************** Cross-chare corruption detection *******************/
869 static int reportMEM = 0;
870
871 /* This first method uses two fields (userCRC and slotCRC) of the Slot structure
872  * to store the CRC32 checksum of the user data and the slot itself. It compares
873  * the stored values against a new value recomputed after the entry method
874  * returned to detect cross-chare corruption.
875  */
876
877 static int CpdCRC32 = 0;
878
879 static int checkSlotCRC(void *userPtr) {
880   Slot *sl = UserToSlot(userPtr);
881   if (sl!=NULL) {
882     unsigned int crc = crc32_initial((unsigned char*)sl, sizeof(Slot)-2*sizeof(unsigned int));
883     crc = crc32_update((unsigned char*)sl->from, sl->stackLen*sizeof(void*), crc);
884     return sl->slotCRC == crc;
885   } else return 0;
886 }
887
888 static int checkUserCRC(void *userPtr) {
889   Slot *sl = UserToSlot(userPtr);
890   if (sl!=NULL) return sl->userCRC == crc32_initial((unsigned char*)userPtr, sl->userSize);
891   else return 0;
892 }
893
894 static void resetUserCRC(void *userPtr) {
895   Slot *sl = UserToSlot(userPtr);
896   if (sl!=NULL) sl->userCRC = crc32_initial((unsigned char*)userPtr, sl->userSize);
897 }
898
899 static void resetSlotCRC(void *userPtr) {
900   Slot *sl = UserToSlot(userPtr);
901   if (sl!=NULL) {
902     unsigned int crc = crc32_initial((unsigned char*)sl, sizeof(Slot)-2*sizeof(unsigned int));
903     crc = crc32_update((unsigned char*)sl->from, sl->stackLen*sizeof(void*), crc);
904     sl->slotCRC = crc;
905   }
906 }
907
908 static void ResetAllCRC() {
909   Slot *cur;
910   unsigned int crc1, crc2;
911
912   SLOT_ITERATE_START(cur)
913     crc1 = crc32_initial((unsigned char*)cur, sizeof(Slot)-2*sizeof(unsigned int));
914     crc1 = crc32_update((unsigned char*)cur->from, cur->stackLen*sizeof(void*), crc1);
915     crc2 = crc32_initial((unsigned char*)SlotToUser(cur), cur->userSize);
916     cur->slotCRC = crc1;
917     cur->userCRC = crc2;
918   SLOT_ITERATE_END
919 }
920
921 static void CheckAllCRC() {
922   Slot *cur;
923   unsigned int crc1, crc2;
924
925   SLOT_ITERATE_START(cur)
926     crc1 = crc32_initial((unsigned char*)cur, sizeof(Slot)-2*sizeof(unsigned int));
927     crc1 = crc32_update((unsigned char*)cur->from, cur->stackLen*sizeof(void*), crc1);
928     crc2 = crc32_initial((unsigned char*)SlotToUser(cur), cur->userSize);
929     /* Here we can check if a modification has occured */
930     if (reportMEM && cur->slotCRC != crc1) CmiPrintf("CRC: Object %d modified slot for %p\n",memory_chare_id,SlotToUser(cur));
931     cur->slotCRC = crc1;
932     if (reportMEM && cur->userCRC != crc2 && memory_chare_id != cur->chareID)
933       CmiPrintf("CRC: Object %d modified memory of object %d for %p\n",memory_chare_id,cur->chareID,SlotToUser(cur));
934     cur->userCRC = crc2;
935   SLOT_ITERATE_END
936 }
937
938 /* This second method requires all the memory in the processor to be copied
939  * into a safe region, and then compare it with the working copy after the
940  * entry method returned.
941  */
942
943 static int CpdMemBackup = 0;
944
945 static void backupMemory() {
946   Slot *cur;
947   if (*memoryBackup != NULL)
948     CmiAbort("memoryBackup != NULL\n");
949
950   int totalMemory = SLOTSPACE;
951   {
952     SLOT_ITERATE_START(cur)
953       totalMemory += sizeof(Slot) + cur->userSize + cur->stackLen*sizeof(void*);
954     SLOT_ITERATE_END
955   }
956   if (reportMEM) CmiPrintf("CPD: total memory in use (%d): %d\n",CmiMyPe(),totalMemory);
957   BEFORE_MALLOC_CALL;
958   *memoryBackup = mm_malloc(totalMemory);
959   AFTER_MALLOC_CALL;
960
961   char * ptr = *memoryBackup;
962 #ifndef CMK_SEPARATE_SLOT
963   memcpy(*memoryBackup, slot_first, sizeof(Slot));
964   ptr += sizeof(Slot);
965 #endif
966   SLOT_ITERATE_START(cur)
967     int tocopy = SLOTSPACE + cur->userSize + cur->stackLen*sizeof(void*);
968     char *data = (char *)cur;
969 #ifdef CMK_SEPARATE_SLOT
970     memcpy(ptr, cur, sizeof(Slot));
971     ptr += sizeof(Slot);
972     data = SlotToUser(cur);
973 #endif
974     memcpy(ptr, data, tocopy);
975     cur->magic &= ~ (NEW_BLOCK | MODIFIED);
976     ptr += tocopy;
977   SLOT_ITERATE_END
978   allocatedSinceSize = 0;
979 }
980
981 static void checkBackup() {
982 #ifndef CMK_SEPARATE_SLOT
983   Slot *cur = slot_first->next;
984   char *ptr = *memoryBackup + sizeof(Slot);
985
986   // skip over the new allocated blocks
987   //while (cur != ((Slot*)*memoryBackup)->next) cur = cur->next;
988   int idx = allocatedSinceSize-1;
989   while (idx >= 0) {
990     while (idx >= 0 && allocatedSince[idx] != cur) idx--;
991     if (idx >= 0) {
992       cur = cur->next;
993       idx --;
994     }
995   }
996
997   while (cur != slot_first) {
998     // ptr is the old copy of cur
999     if (memory_chare_id != cur->chareID) {
1000       int res = memcmp(ptr+sizeof(Slot), ((char*)cur)+sizeof(Slot), cur->userSize + cur->stackLen*sizeof(void*));
1001       if (res != 0) {
1002         cur->magic |= MODIFIED;
1003         if (reportMEM) CmiPrintf("CPD: Object %d modified memory of object %d for %p on pe %d\n",memory_chare_id,cur->chareID,cur+1,CmiMyPe());
1004       }
1005     }
1006
1007     // advance to next, skipping deleted memory blocks
1008     cur = cur->next;
1009     char *last;
1010     do {
1011       last = ptr;
1012       ptr += sizeof(Slot) + ((Slot*)ptr)->userSize + ((Slot*)ptr)->stackLen*sizeof(void*);
1013     } while (((Slot*)last)->next != cur);
1014   }
1015 #endif
1016
1017   BEFORE_MALLOC_CALL;
1018   mm_free(*memoryBackup);
1019   AFTER_MALLOC_CALL;
1020   *memoryBackup = NULL;
1021 }
1022
1023 /* Third method to detect cross-chare corruption. Use mprotect to change the
1024  * protection bits of each page, and a following segmentation fault to detect
1025  * the corruption. It is more accurate as it can provide the stack trace of the
1026  * first instruction that modified the memory.
1027  */
1028
1029 #include <signal.h>
1030
1031 static int meta_getpagesize(void);
1032
1033 static int CpdMprotect = 0;
1034
1035 static void** unProtectedPages = NULL;
1036 static int unProtectedPagesSize = 0;
1037 static int unProtectedPagesMaxSize = 0;
1038
1039 static void* lastAddressSegv;
1040 static void CpdMMAPhandler(int sig, siginfo_t *si, void *unused){
1041   if (lastAddressSegv == si->si_addr) {
1042     CmiPrintf("Second SIGSEGV at address 0x%lx\n", (long) si->si_addr);
1043     CpdFreeze();
1044   }
1045   lastAddressSegv = si->si_addr;
1046   void *pageToUnprotect = (void*)((CmiUInt8)si->si_addr & ~(meta_getpagesize()-1));
1047   mprotect(pageToUnprotect, 4, PROT_READ|PROT_WRITE);
1048   if (unProtectedPagesSize >= unProtectedPagesMaxSize) {
1049     unProtectedPagesMaxSize += 10;
1050     BEFORE_MALLOC_CALL;
1051     void **newUnProtectedPages = (void**)mm_malloc((unProtectedPagesMaxSize)*sizeof(void*));
1052     memcpy(newUnProtectedPages, unProtectedPages, unProtectedPagesSize*sizeof(void*));
1053     mm_free(unProtectedPages);
1054     AFTER_MALLOC_CALL;
1055     unProtectedPages = newUnProtectedPages;
1056   }
1057   unProtectedPages[unProtectedPagesSize++] = pageToUnprotect;
1058   if (reportMEM) CpdNotify(CPD_CROSSCORRUPTION, si->si_addr, memory_chare_id);
1059   //CmiPrintf("Got SIGSEGV at address: 0x%lx\n", (long) si->si_addr);
1060   //CmiPrintStackTrace(0);
1061 }
1062
1063 static void protectMemory() {
1064 #ifdef CPD_USE_MMAP
1065   Slot *cur;
1066   /*printf("protecting memory (chareid=%d)",memory_chare_id);*/
1067   SLOT_ITERATE_START(cur)
1068     if (cur->chareID != memory_chare_id && cur->chareID > 0) {
1069       /*printf(" %p",cur->userData);*/
1070 #ifdef CMK_SEPARATE_SLOT
1071       char * data = cur->userData;
1072 #else
1073       char * data = (char *)cur;
1074 #endif
1075       cur->magic |= BLOCK_PROTECTED;
1076       mprotect(data, cur->userSize+SLOTSPACE+cur->stackLen*sizeof(void*), PROT_READ);
1077     } /*else printf(" (%p)",cur->userData);*/
1078   SLOT_ITERATE_END
1079   /*printf("\n");*/
1080 #endif
1081 }
1082
1083 static void unProtectMemory() {
1084 #ifdef CPD_USE_MMAP
1085   Slot *cur;
1086   SLOT_ITERATE_START(cur)
1087 #ifdef CMK_SEPARATE_SLOT
1088       char * data = cur->userData;
1089 #else
1090       char * data = (char *)cur;
1091 #endif
1092     mprotect(data, cur->userSize+SLOTSPACE+cur->stackLen*sizeof(void*), PROT_READ|PROT_WRITE);
1093     cur->magic &= ~BLOCK_PROTECTED;
1094   SLOT_ITERATE_END
1095   /*printf("unprotecting memory\n");*/
1096 #endif
1097 }
1098
1099 /** Called before the entry method: resets all current memory for the chare
1100  * receiving the message.
1101  */
1102 void CpdResetMemory() {
1103   if (CpdMemBackup) backupMemory();
1104   if (CpdCRC32) ResetAllCRC();
1105   if (CpdMprotect) protectMemory();
1106 }
1107
1108 /** Called after the entry method to check if the chare that just received the
1109  * message has corrupted the memory of some other chare, or some system memory.
1110  */
1111 void CpdCheckMemory() {
1112   if (CpdMprotect) unProtectMemory();
1113   if (CpdCRC32) CheckAllCRC();
1114   if (CpdMemBackup) checkBackup();
1115   Slot *cur;
1116   SLOT_ITERATE_START(cur)
1117     if (cur->magic == SLOTMAGIC_FREED) CmiAbort("SLOT deallocate in list");
1118     if (cur->from == NULL) printf("SLOT %p has no stack\n",cur);
1119 #ifndef CMK_SEPARATE_SLOT
1120     if (cur->next == NULL) printf("SLOT %p has null next!\n",cur);
1121 #endif
1122   SLOT_ITERATE_END
1123 }
1124
1125 void CpdSystemEnter() {
1126 #ifdef CPD_USE_MMAP
1127   Slot *cur;
1128   if (++cpdInSystem == 1) {
1129     if (CpdMprotect) {
1130       int count=0;
1131       SLOT_ITERATE_START(cur)
1132         if (cur->chareID == 0) {
1133 #ifdef CMK_SEPARATE_SLOT
1134           char * data = cur->userData;
1135 #else
1136           char * data = (char *)cur;
1137 #endif
1138           mprotect(data, cur->userSize+SLOTSPACE+cur->stackLen*sizeof(void*), PROT_READ|PROT_WRITE);
1139           cur->magic &= ~BLOCK_PROTECTED;
1140           count++;
1141         }
1142       SLOT_ITERATE_END
1143       //printf("CpdSystemEnter: unprotected %d elements\n",count);
1144     }
1145   }
1146 #endif
1147 }
1148
1149 void CpdSystemExit() {
1150 #ifdef CPD_USE_MMAP
1151   Slot *cur;
1152   int i;
1153   if (--cpdInSystem == 0) {
1154     if (CpdMprotect) {
1155       int count=0;
1156       SLOT_ITERATE_START(cur)
1157         if (cur->chareID == 0) {
1158 #ifdef CMK_SEPARATE_SLOT
1159           char * data = cur->userData;
1160 #else
1161           char * data = (char *)cur;
1162 #endif
1163           cur->magic |= BLOCK_PROTECTED;
1164           mprotect(data, cur->userSize+SLOTSPACE+cur->stackLen*sizeof(void*), PROT_READ);
1165           count++;
1166         }
1167       SLOT_ITERATE_END
1168       //printf("CpdSystemExit: protected %d elements\n",count);
1169       /* unprotect the pages that have been unprotected by a signal SEGV */
1170       for (i=0; i<unProtectedPagesSize; ++i) {
1171         mprotect(unProtectedPages[i], 4, PROT_READ|PROT_WRITE);
1172       }
1173     }
1174   }
1175 #endif
1176 }
1177
1178
1179 /*
1180
1181 / *Head of the current circular allocated block list* /
1182 Slot slot_first_storage={&slot_first_storage,&slot_first_storage};
1183 Slot *slot_first=&slot_first_storage;
1184
1185 #define CMI_MEMORY_ROUTINES 1
1186
1187 / * Mark all allocated memory as being OK * /
1188 void CmiMemoryMark(void) {
1189         CmiMemLock();
1190         / * Just make a new linked list of slots * /
1191         slot_first=(Slot *)mm_malloc(sizeof(Slot));
1192         slot_first->next=slot_first->prev=slot_first;
1193         CmiMemUnlock();
1194 }
1195
1196 / * Mark this allocated block as being OK * /
1197 void CmiMemoryMarkBlock(void *blk) {
1198         Slot *s=Slot_fmUser(blk);
1199         CmiMemLock();
1200         if (s->magic!=SLOTMAGIC) CmiAbort("CmiMemoryMarkBlock called on non-malloc'd block!\n");
1201         / * Splice us out of the current linked list * /
1202         s->next->prev=s->prev;
1203         s->prev->next=s->next;
1204         s->prev=s->next=s; / * put us in our own list * /
1205         CmiMemUnlock();
1206 }
1207
1208 / * Print out all allocated memory * /
1209 void CmiMemorySweep(const char *where) {
1210         Slot *cur;
1211         int nBlocks=0,nBytes=0;
1212         CmiMemLock();
1213         cur=slot_first->next;
1214         CmiPrintf("[%d] ------- LEAK CHECK: %s -----\n",CmiMyPe(), where);
1215         while (cur!=slot_first) {
1216                 printSlot(cur);
1217                 nBlocks++; nBytes+=cur->userSize;
1218                 cur=cur->next;
1219         }
1220         if (nBlocks) {
1221                 CmiPrintf("[%d] Total leaked memory: %d blocks, %d bytes\n",
1222                         CmiMyPe(),nBlocks,nBytes);
1223                 / * CmiAbort("Memory leaks detected!\n"); * /
1224         }
1225         CmiMemUnlock();
1226         CmiMemoryMark();
1227 }
1228 void CmiMemoryCheck(void) {}
1229 */
1230
1231
1232 /********** Allocation/Free ***********/
1233
1234 static int stackTraceDisabled = 0;
1235 #define MAX_STACK_FRAMES   2048
1236 static int numStackFrames; // the number of frames presetn in stackFrames - 4 (this number is trimmed at 0
1237 static void *stackFrames[MAX_STACK_FRAMES];
1238
1239 static void dumpStackFrames() {
1240   numStackFrames=MAX_STACK_FRAMES;
1241   if (stackTraceDisabled==0) {
1242     stackTraceDisabled = 1;
1243     CmiBacktraceRecordHuge(stackFrames,&numStackFrames);
1244     stackTraceDisabled = 0;
1245     numStackFrames-=4;
1246     if (numStackFrames < 0) numStackFrames = 0;
1247   } else {
1248     numStackFrames=0;
1249     stackFrames[0] = (void*)0;
1250   }
1251 }
1252
1253 /* Write a valid slot to this field */
1254 static void *setSlot(Slot **sl,int userSize) {
1255 #ifdef CMK_SEPARATE_SLOT
1256   static int mallocFirstTime = 1;
1257   if (mallocFirstTime) {
1258     mallocFirstTime = 0;
1259     memory_charmdebug_internal = 1;
1260     block_slots = CkCreateHashtable_pointer(sizeof(Slot), 10000);
1261     memory_charmdebug_internal = 0;
1262   }
1263   
1264   char *user = (char *)*sl;
1265   memory_charmdebug_internal = 1;
1266   Slot *s = (Slot *)CkHashtablePut(block_slots, sl);
1267   memory_charmdebug_internal = 0;
1268   *sl = s;
1269
1270   s->userData = user;
1271 #else
1272   Slot *s = *sl;
1273   char *user=(char*)(s+1);
1274
1275   /* Splice into the slot list just past the head (part 1) */
1276   s->next=slot_first->next;
1277   s->prev=slot_first;
1278   /* Handle correctly memory protection while changing neighbor blocks */
1279   if (CpdMprotect) {
1280     mprotect(s->next, 4, PROT_READ | PROT_WRITE);
1281     mprotect(s->prev, 4, PROT_READ | PROT_WRITE);
1282   }
1283   /* Splice into the slot list just past the head (part 2) */
1284   s->next->prev=s;
1285   s->prev->next=s;
1286
1287   if (CpdCRC32) {
1288     /* fix crc for previous and next block */
1289     resetSlotCRC(s->next + 1);
1290     resetSlotCRC(s->prev + 1);
1291   }
1292   if (CpdMprotect) {
1293     if (isProtected(s->next)) mprotect(s->next, 4, PROT_READ);
1294     if (isProtected(s->prev)) mprotect(s->prev, 4, PROT_READ);
1295   }
1296 #endif
1297
1298   /* Set the last 4 bits of magic to classify the memory together with the magic */
1299   s->magic=SLOTMAGIC + NEW_BLOCK + (memory_status_info>0? USER_TYPE : SYSTEM_TYPE);
1300   //if (memory_status_info>0) printf("user allocation\n");
1301   s->chareID = memory_chare_id;
1302   s->userSize=userSize;
1303   s->extraStack=(SlotStack *)0;
1304   
1305   /* Set the stack frames */
1306   s->stackLen=numStackFrames;
1307   s->from=(void**)(user+userSize);
1308   memcpy(s->from, &stackFrames[4], numStackFrames*sizeof(void*));
1309
1310   if (CpdCRC32) {
1311     unsigned int crc = crc32_initial((unsigned char*)s, sizeof(Slot)-2*sizeof(unsigned int));
1312     s->slotCRC = crc32_update((unsigned char*)s->from, numStackFrames*sizeof(void*), crc);
1313     s->userCRC = crc32_initial((unsigned char*)user, userSize);
1314   }
1315   if (saveAllocationHistory) {
1316     if (allocatedSinceSize >= allocatedSinceMaxSize) {
1317       allocatedSinceMaxSize += 10;
1318       BEFORE_MALLOC_CALL;
1319       Slot **newAllocatedSince = (Slot**)mm_malloc((allocatedSinceMaxSize)*sizeof(Slot*));
1320       memcpy(newAllocatedSince, allocatedSince, allocatedSinceSize*sizeof(Slot*));
1321       mm_free(allocatedSince);
1322       AFTER_MALLOC_CALL;
1323       allocatedSince = newAllocatedSince;
1324     }
1325     allocatedSince[allocatedSinceSize++] = s;
1326   }
1327   lastMemoryAllocated = user;
1328
1329   return (void *)user;
1330 }
1331
1332 /* Delete this slot structure */
1333 static void freeSlot(Slot *s) {
1334 #ifdef CMK_SEPARATE_SLOT
1335   /* Don't delete it from the hash table, simply mark it as freed */
1336   int removed = CkHashtableRemove(block_slots, &s->userData);
1337   CmiAssert(removed);
1338   /* WARNING! After the slot has been removed from the hashtable,
1339    * the pointer "s" becomes invalid.
1340    */
1341 #else
1342   /* Handle correctly memory protection while changing neighbor blocks */
1343   if (CpdMprotect) {
1344     mprotect(s->next, 4, PROT_READ | PROT_WRITE);
1345     mprotect(s->prev, 4, PROT_READ | PROT_WRITE);
1346   }
1347   /* Splice out of the slot list */
1348   s->next->prev=s->prev;
1349   s->prev->next=s->next;
1350   if (CpdCRC32) {
1351     /* fix crc for previous and next block */
1352     resetSlotCRC(s->next + 1);
1353     resetSlotCRC(s->prev + 1);
1354   }
1355   if (CpdMprotect) {
1356     if (isProtected(s->next)) mprotect(s->next, 4, PROT_READ);
1357     if (isProtected(s->prev)) mprotect(s->prev, 4, PROT_READ);
1358   }
1359   s->prev=s->next=(Slot *)0;//0x0F00; why was it not 0?
1360
1361   s->magic=SLOTMAGIC_FREED;
1362   s->userSize=-1;
1363 #endif
1364 }
1365
1366 /********** meta_ routines ***********/
1367
1368 /* Return the system page size */
1369 static int meta_getpagesize(void) {
1370   static int cache=0;
1371 #if defined(CMK_GETPAGESIZE_AVAILABLE)
1372   if (cache==0) cache=getpagesize();
1373 #else
1374   if (cache==0) cache=8192;
1375 #endif
1376   return cache;
1377 }
1378
1379 /* Only display startup status messages from processor 0 */
1380 static void status(char *msg) {
1381   if (CmiMyPe()==0 && !CmiArgGivingUsage()) {
1382     CmiPrintf("%s",msg);
1383   }
1384 }
1385
1386 extern int getCharmEnvelopeSize();
1387
1388 static int disableVerbosity = 1;
1389 int cpdInitializeMemory;
1390 void CpdSetInitializeMemory(int v) { cpdInitializeMemory = v; }
1391
1392 static void meta_init(char **argv) {
1393   status("Converse -memory mode: charmdebug\n");
1394   char buf[100];
1395   sprintf(buf, "slot size %d\n", (int)sizeof(Slot));
1396   status(buf);
1397   CmiMemoryIs_flag|=CMI_MEMORY_IS_CHARMDEBUG;
1398   cpdInitializeMemory = 0;
1399   charmEnvelopeSize = getCharmEnvelopeSize();
1400   CpdDebugGetAllocationTree = (void* (*)(int*))CreateAllocationTree;
1401   CpdDebug_pupAllocationPoint = pupAllocationPoint;
1402   CpdDebug_deleteAllocationPoint = deleteAllocationPoint;
1403   CpdDebug_MergeAllocationTree = MergeAllocationTree;
1404   CpdDebugGetMemStat = (void* (*)(void))CreateMemStat;
1405   CpdDebug_pupMemStat = pupMemStat;
1406   CpdDebug_deleteMemStat = deleteMemStat;
1407   CpdDebug_mergeMemStat = mergeMemStat;
1408   memory_allocated_user_total = 0;
1409   nextChareID = 1;
1410 #ifndef CMK_SEPARATE_SLOT
1411   slot_first->userSize = 0;
1412   slot_first->stackLen = 0;
1413 #endif
1414   if (CmiGetArgFlagDesc(argv,"+memory_report", "Print all cross-object violations")) {
1415     reportMEM = 1;
1416   }
1417   if (CmiGetArgFlagDesc(argv,"+memory_backup", "Backup all memory at every entry method")) {
1418     CpdMemBackup = 1;
1419     saveAllocationHistory = 1;
1420   }
1421   if (CmiGetArgFlagDesc(argv,"+memory_crc", "Use CRC32 to detect memory changes")) {
1422     CpdCRC32 = 1;
1423   }
1424 #ifdef CPD_USE_MMAP
1425   if (CmiGetArgFlagDesc(argv,"+memory_mprotect", "Use mprotect to protect memory of other chares")) {
1426     CpdMprotect = 1;
1427     struct sigaction sa;
1428     sa.sa_flags = SA_SIGINFO | SA_NODEFER | SA_RESTART;
1429     sigemptyset(&sa.sa_mask);
1430     sa.sa_sigaction = CpdMMAPhandler;
1431     if (sigaction(SIGSEGV, &sa, NULL) == -1) CmiPrintf("failed to install signal handler\n");
1432   }
1433 #endif
1434   if (CmiGetArgFlagDesc(argv,"+memory_verbose", "Print all memory-related operations")) {
1435     disableVerbosity = 0;
1436   }
1437   if (CmiGetArgFlagDesc(argv,"+memory_nostack", "Do not collect stack traces for memory allocations")) {
1438     stackTraceDisabled = 1;
1439   }
1440 }
1441
1442 static void *meta_malloc(size_t size) {
1443   void *user;
1444   if (memory_charmdebug_internal==0) {
1445     dumpStackFrames();
1446     BEFORE_MALLOC_CALL;
1447 #if CPD_USE_MMAP
1448     Slot *s=(Slot *)mmap(NULL, SLOTSPACE+size+numStackFrames*sizeof(void*), PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
1449 #else
1450     Slot *s=(Slot *)mm_malloc(SLOTSPACE+size+numStackFrames*sizeof(void*));
1451 #endif
1452     AFTER_MALLOC_CALL;
1453     if (s!=NULL) {
1454       user = (char*)setSlot(&s,size);
1455       memory_allocated_user_total += size;
1456 #if ! CMK_BIGSIM_CHARM
1457       traceMalloc_c(user, size, s->from, s->stackLen);
1458 #endif
1459     }
1460     if (disableVerbosity == 0) {
1461       disableVerbosity = 1;
1462       CmiPrintf("allocating %p: %d bytes\n",s,size);
1463       disableVerbosity = 0;
1464     }
1465   } else {
1466     BEFORE_MALLOC_CALL;
1467     user = mm_malloc(size);
1468     AFTER_MALLOC_CALL;
1469   }
1470   if (cpdInitializeMemory) {
1471     bzero(user, size); // for Record-Replay must initialize all memory otherwise paddings may differ (screwing up the CRC)
1472   }
1473   return user;
1474 }
1475
1476 static void meta_free(void *mem) {
1477   if (memory_charmdebug_internal==0) {
1478     Slot *s;
1479     if (mem==NULL) return; /*Legal, but misleading*/
1480     s=UserToSlot(mem);
1481 #if CMK_MEMORY_BUILD_OS
1482     /* In this situation, we can have frees that were not allocated by our malloc...
1483      * for now simply skip over them. */
1484     if (s == NULL || ((s->magic&~FLAGS_MASK) != SLOTMAGIC_VALLOC &&
1485         (s->magic&~FLAGS_MASK) != SLOTMAGIC)) {
1486       BEFORE_MALLOC_CALL;
1487       mm_free(mem);
1488       AFTER_MALLOC_CALL;
1489       return;
1490     }
1491 #endif
1492
1493     /* Check that the memory is really allocated, and we can use its slot */
1494     /* TODO */
1495
1496     if (s == NULL ||
1497         ((s->magic&~FLAGS_MASK) != SLOTMAGIC &&
1498             (s->magic&~FLAGS_MASK) != SLOTMAGIC_FREED &&
1499             (s->magic&~FLAGS_MASK) != SLOTMAGIC_VALLOC)) {
1500       CmiAbort("Free'd non-malloc'd block");
1501     }
1502 #ifdef CMK_SEPARATE_SLOT
1503     CmiAssert(s->userData == mem);
1504 #endif
1505     
1506     int memSize = 0;
1507     if (mem!=NULL) memSize = s->userSize;
1508     memory_allocated_user_total -= memSize;
1509 #if ! CMK_BIGSIM_CHARM
1510     traceFree_c(mem, memSize);
1511 #endif
1512
1513     if (disableVerbosity == 0) {
1514       disableVerbosity = 1;
1515       CmiPrintf("freeing %p\n",mem);
1516       disableVerbosity = 0;
1517     }
1518
1519     /*Overwrite stack trace with the one of the free*/
1520     dumpStackFrames();
1521     if (s->stackLen > numStackFrames) s->stackLen=numStackFrames;
1522     memcpy(s->from, &stackFrames[4], s->stackLen*sizeof(void*));
1523
1524     if ((s->magic&~FLAGS_MASK)==SLOTMAGIC_VALLOC)
1525     { /*Allocated with special alignment*/
1526       void *ptr = s->extraStack;
1527       freeSlot(s);
1528       BEFORE_MALLOC_CALL;
1529       mm_free(ptr);
1530       /*mm_free(((char *)mem)-meta_getpagesize());*/
1531       AFTER_MALLOC_CALL;
1532     }
1533     else if ((s->magic&~FLAGS_MASK)==SLOTMAGIC)
1534     { /*Ordinary allocated block */
1535       int freeSize=SLOTSPACE+s->userSize+s->stackLen*sizeof(void*);
1536       freeSlot(s);
1537 #ifdef CMK_SEPARATE_SLOT
1538       void *ptr = mem;
1539 #else
1540       void *ptr = s;
1541 #endif
1542       BEFORE_MALLOC_CALL;
1543 #if CPD_USE_MMAP
1544       munmap(ptr, freeSize);
1545 #else
1546       mm_free(ptr);
1547 #endif
1548       AFTER_MALLOC_CALL;
1549     }
1550     else if (s->magic==SLOTMAGIC_FREED)
1551       CmiAbort("Free'd block twice");
1552     else /*Unknown magic number*/
1553       CmiAbort("Free'd non-malloc'd block");
1554   } else {
1555     BEFORE_MALLOC_CALL;
1556     mm_free(mem);
1557     AFTER_MALLOC_CALL;
1558   }
1559 }
1560
1561 static void *meta_calloc(size_t nelem, size_t size) {
1562   void *area=meta_malloc(nelem*size);
1563   if (area != NULL) memset(area,0,nelem*size);
1564   return area;
1565 }
1566
1567 static void meta_cfree(void *mem) {
1568   meta_free(mem);
1569 }
1570
1571 static void *meta_realloc(void *oldBuffer, size_t newSize) {
1572   void *newBuffer = meta_malloc(newSize);
1573   if ( newBuffer && oldBuffer ) {
1574     /*Preserve old buffer contents*/
1575     Slot *o=UserToSlot(oldBuffer);
1576     size_t size=o->userSize;
1577     if (size>newSize) size=newSize;
1578     if (size > 0)
1579       memcpy(newBuffer, oldBuffer, size);
1580
1581     meta_free(oldBuffer);
1582   }
1583   return newBuffer;
1584 }
1585
1586 static void *meta_memalign(size_t align, size_t size) {
1587   int overhead = align;
1588   while (overhead < SLOTSPACE+sizeof(SlotStack)) overhead += align;
1589   /* Allocate the required size + the overhead needed to keep the user alignment */
1590   dumpStackFrames();
1591
1592   BEFORE_MALLOC_CALL;
1593   char *alloc=(char *)mm_memalign(align,overhead+size+numStackFrames*sizeof(void*));
1594   AFTER_MALLOC_CALL;
1595   Slot *s=(Slot*)(alloc+overhead-SLOTSPACE);
1596   void *user=setSlot(&s,size);
1597   s->magic = SLOTMAGIC_VALLOC + (s->magic&0xF);
1598   s->extraStack = (SlotStack *)alloc; /* use the extra space as stack */
1599   s->extraStack->protectedMemory = NULL;
1600   s->extraStack->protectedMemoryLength = 0;
1601   memory_allocated_user_total += size;
1602 #if ! CMK_BIGSIM_CHARM
1603   traceMalloc_c(user, size, s->from, s->stackLen);
1604 #endif
1605   return user;
1606 }
1607
1608 static void *meta_valloc(size_t size) {
1609   return meta_memalign(meta_getpagesize(),size);
1610 }
1611
1612 void setProtection(char* mem, char *ptr, int len, int flag) {
1613   Slot *sl = UserToSlot(mem);
1614   if (sl->extraStack == NULL) CmiAbort("Tried to protect memory not memaligned\n");
1615   if (flag != 0) {
1616     sl->extraStack->protectedMemory = ptr;
1617     sl->extraStack->protectedMemoryLength = len;
1618   } else {
1619     sl->extraStack->protectedMemory = NULL;
1620     sl->extraStack->protectedMemoryLength = 0;
1621   }
1622 }
1623
1624 void **chareObjectMemory = NULL;
1625 int chareObjectMemorySize = 0;
1626
1627 void setMemoryTypeChare(void *ptr) {
1628   Slot *sl = UserToSlot(ptr);
1629   sl->magic = (sl->magic & ~FLAGS_MASK) | CHARE_TYPE;
1630   sl->chareID = nextChareID;
1631   if (nextChareID >= chareObjectMemorySize) {
1632     BEFORE_MALLOC_CALL;
1633     void **newChare = (void**)mm_malloc((nextChareID+100) * sizeof(void*));
1634     AFTER_MALLOC_CALL;
1635     memcpy(newChare, chareObjectMemory, chareObjectMemorySize*sizeof(void*));
1636     chareObjectMemorySize = nextChareID+100;
1637     BEFORE_MALLOC_CALL;
1638     mm_free(chareObjectMemory);
1639     AFTER_MALLOC_CALL;
1640     chareObjectMemory = newChare;
1641   }
1642   chareObjectMemory[nextChareID] = ptr;
1643   nextChareID ++;
1644 }
1645
1646 /* The input parameter is the pointer to the envelope, after the CmiChunkHeader */
1647 void setMemoryTypeMessage(void *ptr) {
1648   void *realptr = (char*)ptr - sizeof(CmiChunkHeader);
1649   Slot *sl = UserToSlot(realptr);
1650   if ((sl->magic&~FLAGS_MASK) == SLOTMAGIC || (sl->magic&~FLAGS_MASK) == SLOTMAGIC_VALLOC) {
1651     sl->magic = (sl->magic & ~FLAGS_MASK) | MESSAGE_TYPE;
1652   }
1653 }
1654
1655 int setMemoryChareIDFromPtr(void *ptr) {
1656   int tmp = memory_chare_id;
1657   if (ptr == NULL || ptr == 0) memory_chare_id = 0;
1658   else memory_chare_id = UserToSlot(ptr)->chareID;
1659   return tmp;
1660 }
1661
1662 void setMemoryChareID(int chareID) {
1663   memory_chare_id = chareID;
1664 }
1665
1666 void setMemoryOwnedBy(void *ptr, int chareID) {
1667   Slot *sl = UserToSlot(ptr);
1668   sl->chareID = chareID;
1669 }
1670
1671 void * MemoryToSlot(void *ptr) {
1672   Slot *sl;
1673   int i;
1674 #if defined(CPD_USE_MMAP) && defined(CMK_SEPARATE_SLOT)
1675   for (i=0; i<1000; ++i) {
1676     sl = UserToSlot((void*)(((CmiUInt8)ptr)-i*meta_getpagesize() & ~(meta_getpagesize()-1)));
1677     if (sl != NULL) return sl;
1678   }
1679 #endif
1680   return NULL;
1681 }
1682
1683 /*void PrintDebugStackTrace(void *ptr) {
1684   int i;
1685   Slot *sl = UserToSlot((void*)(((CmiUInt8)ptr) & ~(meta_getpagesize()-1)));
1686   if (sl != NULL) {
1687     CmiPrintf("%d %d ",sl->chareID,sl->stackLen);
1688     for (i=0; i<sl->stackLen; ++i) CmiPrintf("%p ",sl->from[i]);
1689   } else {
1690     CmiPrintf("%d 0 ",sl->chareID);
1691   }
1692 }*/
1693
1694
1695 #endif