Added flag "-debug" to charmc for usage with charmdebug.
[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 /* Use Gnumalloc as meta-meta malloc fallbacks (mm_*) */
16 #include "memory-gnu.c"
17 #include "tracec.h"
18
19 /* Utilities needed by the code */
20 #include "ckhashtable.h"
21
22 /*#include "pup_c.h" */
23
24 typedef struct _Slot Slot;
25 typedef struct _SlotStack SlotStack;
26
27 int nextChareID;
28 int memory_chare_id;
29
30 /**
31  * Struct Slot contains all of the information about a malloc buffer except
32  * for the contents of its memory.
33  */
34 struct _Slot {
35   /*Doubly-linked allocated block list*/
36   Slot *next;
37   Slot *prev;
38         
39   /*The number of bytes of user data*/
40   int userSize;
41
42 #define FLAGS_MASK        0xF
43 #define LEAK_FLAG         0x8
44 #define UNKNOWN_TYPE      0x0
45 #define SYSTEM_TYPE       0x1
46 #define USER_TYPE         0x2
47 #define CHARE_TYPE        0x3
48 #define MESSAGE_TYPE      0x4
49   /* A magic number field, to verify this is an actual malloc'd buffer, and what
50      type of allocation it is. The last 4 bits of the magic number are used to
51      define a classification of mallocs. */
52 #define SLOTMAGIC            0x8402a5e0
53 #define SLOTMAGIC_VALLOC     0x7402a5e0
54 #define SLOTMAGIC_FREED      0xDEADBEEF
55   int magic;
56
57   int chareID;
58   /* Controls the number of stack frames to print out. Should be always odd, so
59      the total size of this struct becomes multiple of 8 bytes everywhere */
60 //#define STACK_LEN 15
61   int stackLen;
62   void **from;
63
64   /* Pointer to extra stacktrace, when the user requested more trace */
65   SlotStack *extraStack;
66 };
67
68 struct _SlotStack {
69   char *protectedMemory;
70   int protectedMemoryLength;
71   /* empty for the moment, to be filled when needed */
72 };
73
74 /*Convert a slot to a user address*/
75 static char *SlotToUser(Slot *s) {
76   return ((char *)s)+sizeof(Slot);
77 }
78
79
80 /*Convert a user address to a slot*/
81 static Slot *UserToSlot(void *user) {
82   char *cu=(char *)user;
83   Slot *s=(Slot *)(cu-sizeof(Slot));
84   return s;
85 }
86
87 static int isLeakSlot(Slot *s) {
88   return s->magic & LEAK_FLAG;
89 }
90
91 static void printSlot(Slot *s) {
92   CmiPrintf("[%d] Leaked block of %d bytes at %p:\n",
93             CmiMyPe(), s->userSize, SlotToUser(s));
94   CmiBacktracePrint(s->from,s->stackLen);
95 }
96
97 /********* Circural list of allocated memory *********/
98
99 /* First memory slot */
100 Slot slot_first_storage = {&slot_first_storage, &slot_first_storage};
101 Slot *slot_first = &slot_first_storage;
102
103 int memory_allocated_user_total;
104 int get_memory_allocated_user_total() {return memory_allocated_user_total;}
105
106 /********* Cpd routines for pupping data to the debugger *********/
107
108 int cpd_memory_length(void *lenParam) {
109   int n=0;
110   Slot *cur = slot_first->next;
111   while (cur != slot_first) {
112     n++;
113     cur = cur->next;
114   }
115   return n;
116 }
117
118 void cpd_memory_single_pup(Slot* list, pup_er p) {
119   Slot *cur = list->next;
120   /* Stupid hack to avoid sending the memory we just allocated for this packing,
121      otherwise the lenghts will mismatch */
122   if (pup_isPacking(p)) cur = cur->next;
123   while (cur != list) {
124     int i;
125     int flags;
126     void *loc = (void*)(cur+1);
127     CpdListBeginItem(p, 0);
128     pup_comment(p, "loc");
129     pup_pointer(p, &loc);
130     pup_comment(p, "size");
131     pup_int(p, &cur->userSize);
132     pup_comment(p, "flags");
133     flags = cur->magic & FLAGS_MASK;
134     pup_int(p, &flags);
135     pup_comment(p, "chare");
136     pup_int(p, &cur->chareID);
137     pup_comment(p, "stack");
138     //for (i=0; i<STACK_LEN; ++i) {
139     //  if (cur->from[i] <= 0) break;
140       //      if (cur->from[i] > 0) pup_uint(p, (unsigned int*)&cur->from[i]);
141       //      else break;
142     //}
143     pup_pointers(p, cur->from, cur->stackLen);
144     cur = cur->next;
145   }
146 }
147
148 void cpd_memory_pup(void *itemParam, pup_er p, CpdListItemsRequest *req) {
149   CpdListBeginItem(p, 0);
150   pup_comment(p, "name");
151   pup_chars(p, "memory", strlen("memory"));
152   pup_comment(p, "slots");
153   pup_syncComment(p, pup_sync_begin_array, 0);
154   cpd_memory_single_pup(slot_first, p);
155   pup_syncComment(p, pup_sync_end_array, 0);
156 }
157
158 void check_memory_leaks(CpdListItemsRequest *);
159 void cpd_memory_leak(void *iterParam, pup_er p, CpdListItemsRequest *req) {
160   if (pup_isSizing(p)) {
161     // let's perform the memory leak checking. This is the first step in the
162     // packing, where we size, in the second step we pack and we avoid doing
163     // this check again.
164     check_memory_leaks(req);
165   }
166   cpd_memory_pup(iterParam, p, req);
167 }
168
169 int cpd_memory_getLength(void *lenParam) { return 1; }
170 void cpd_memory_get(void *iterParam, pup_er p, CpdListItemsRequest *req) {
171   void *userData = (void*)(((unsigned int)req->lo) + (((unsigned long)req->hi)<<32));
172   Slot *sl = ((Slot*)userData)-1;
173   CpdListBeginItem(p, 0);
174   pup_comment(p, "size");
175   //printf("value: %x %x %x %d\n",sl->magic, sl->magic&~FLAGS_MASK, SLOTMAGIC, ((sl->magic&~FLAGS_MASK) != SLOTMAGIC));
176   if ((sl->magic&~FLAGS_MASK) != SLOTMAGIC) {
177     int zero = 0;
178     pup_int(p, &zero);
179   } else {
180     pup_int(p, &sl->userSize);
181     pup_comment(p, "value");
182     pup_bytes(p, userData, sl->userSize);
183   }
184 }
185
186 /********* Heap Checking ***********/
187
188 int charmEnvelopeSize = 0;
189
190 // FIXME: this function assumes that all memory is allocated in slot_unknown!
191 void check_memory_leaks(CpdListItemsRequest *req) {
192   FILE* fd=fopen("check_memory_leaks", "w");
193   // Step 1)
194   // index all memory into a CkHashtable, with a scan of 4 bytes.
195   CkHashtable_c table;
196   Slot leaking, inProgress;
197   Slot *sl, **fnd, *found;
198   char *scanner;
199   char *begin_stack, *end_stack;
200   char *begin_data, *end_data;
201   char *begin_bss, *end_bss;
202   int growing_dimension = 0;
203
204   // copy all the memory from "slot_first" to "leaking"
205   slot_first->next->prev = &leaking;
206   slot_first->prev->next = &leaking;
207   leaking.prev = slot_first->prev;
208   leaking.next = slot_first->next;
209   slot_first->next = slot_first;
210   slot_first->prev = slot_first;
211
212   table = CkCreateHashtable_pointer(sizeof(char *), 10000);
213   for (sl = leaking.next; sl != &leaking; sl = sl->next) {
214     // index the i-th memory slot
215     char *ptr;
216     sl->magic |= LEAK_FLAG;
217     if (req->lo > 0) {
218       //CmiPrintf("checking memory fast\n");
219       // means index only specific offsets of the memory region
220       ptr = ((char*)sl)+sizeof(Slot);
221       char **object = (char**)CkHashtablePut(table, &ptr);
222       *object = (char*)sl;
223       ptr += 4;
224       object = (char**)CkHashtablePut(table, &ptr);
225       *object = (char*)sl;
226       // beginning of converse header
227       ptr += sizeof(CmiChunkHeader) - 4;
228       if (ptr < ((char*)sl)+2*sizeof(Slot)+sl->userSize) {
229         object = (char**)CkHashtablePut(table, &ptr);
230         *object = (char*)sl;
231       }
232       // beginning of charm header
233       ptr += CmiReservedHeaderSize;
234       if (ptr < ((char*)sl)+2*sizeof(Slot)+sl->userSize) {
235         object = (char**)CkHashtablePut(table, &ptr);
236         *object = (char*)sl;
237       }
238       // beginning of ampi header
239       ptr += charmEnvelopeSize - CmiReservedHeaderSize;
240       if (ptr < ((char*)sl)+2*sizeof(Slot)+sl->userSize) {
241         object = (char**)CkHashtablePut(table, &ptr);
242         *object = (char*)sl;
243       }
244     } else {
245       //CmiPrintf("checking memory extensively\n");
246       // means index every fourth byte of the memory region
247       for (ptr = ((char*)sl)+sizeof(Slot); ptr < ((char*)sl)+sizeof(Slot)+sl->userSize; ptr+=sizeof(char*)) {
248         //printf("memory %p\n",ptr);
249         //growing_dimension++;
250         //if ((growing_dimension&0xFF) == 0) printf("inserted %d objects\n",growing_dimension);
251         char **object = (char**)CkHashtablePut(table, &ptr);
252         *object = (char*)sl;
253       }
254     }
255   }
256
257   // Step 2)
258   // start the check with the stack and the global data. The stack is found
259   // through the current pointer, going up until 16 bits filling (considering
260   // the stack grows toward decreasing addresses). The pointers to the global
261   // data (segments .data and .bss) are passed in with "req" as the "extra"
262   // field, with the structure "begin .data", "end .data", "begin .bss", "end .bss".
263   inProgress.prev = &inProgress;
264   inProgress.next = &inProgress;
265   begin_stack = (char*)&table;
266   end_stack = memory_stack_top;
267   if (req->extraLen != 4*4/*sizeof(char*) FIXME: assumes 64 bit addresses of .data and .bss are small enough*/) {
268     CmiPrintf("requested for a memory leak check with wrong information! %d bytes\n",req->extraLen);
269   }
270   //if (sizeof(char*) == 4) {
271     /* 32 bit addresses; for 64 bit machines it assumes the following addresses were small enough */
272     begin_data = (char*)ntohl(((int*)(req->extra))[0]);
273     end_data = (char*)ntohl(((int*)(req->extra))[1]) - sizeof(char*) + 1;
274     begin_bss = (char*)ntohl(((int*)(req->extra))[2]);
275     end_bss = (char*)ntohl(((int*)(req->extra))[3]) - sizeof(char*) + 1;
276   /*} else {
277     CmiAbort("not ready yet");
278     begin_data = ntohl(((char**)(req->extra))[0]);
279     end_data = ntohl(((char**)(req->extra))[1]) - sizeof(char*) + 1;
280     begin_bss = ntohl(((char**)(req->extra))[2]);
281     end_bss = ntohl(((char**)(req->extra))[3]) - sizeof(char*) + 1;
282   }*/
283   printf("scanning stack from %p (%d) to %p (%d)\n",begin_stack,begin_stack,end_stack,end_stack);
284   for (scanner = begin_stack; scanner < end_stack; scanner+=sizeof(char*)) {
285     fnd = (Slot**)CkHashtableGet(table, scanner);
286     //if (fnd != NULL) printf("scanning stack %p, %d\n",*fnd,isLeakSlot(*fnd));
287     if (fnd != NULL && isLeakSlot(*fnd)) {
288       found = *fnd;
289       /* mark slot as not leak */
290       //printf("stack pointing to %p\n",found+1);
291       found->magic &= ~LEAK_FLAG;
292       /* move the slot a inProgress */
293       found->next->prev = found->prev;
294       found->prev->next = found->next;
295       found->next = inProgress.next;
296       found->prev = &inProgress;
297       found->next->prev = found;
298       found->prev->next = found;
299     }
300   }
301   printf("scanning data from %p (%d) to %p (%d)\n",begin_data,begin_data,end_data,end_data);
302   for (scanner = begin_data; scanner < end_data; scanner+=sizeof(char*)) {
303     //fprintf(fd, "scanner = %p\n",scanner);
304     fflush(fd);
305     fnd = (Slot**)CkHashtableGet(table, scanner);
306     //if (fnd != NULL) printf("scanning data %p, %d\n",*fnd,isLeakSlot(*fnd));
307     if (fnd != NULL && isLeakSlot(*fnd)) {
308       found = *fnd;
309       /* mark slot as not leak */
310       //printf("data pointing to %p\n",found+1);
311       found->magic &= ~LEAK_FLAG;
312       /* move the slot a inProgress */
313       found->next->prev = found->prev;
314       found->prev->next = found->next;
315       found->next = inProgress.next;
316       found->prev = &inProgress;
317       found->next->prev = found;
318       found->prev->next = found;
319     }
320   }
321   printf("scanning bss from %p (%d) to %p (%d)\n",begin_bss,begin_bss,end_bss,end_bss);
322   for (scanner = begin_bss; scanner < end_bss; scanner+=sizeof(char*)) {
323     //printf("bss: %p %p\n",scanner,*(char**)scanner);
324     fnd = (Slot**)CkHashtableGet(table, scanner);
325     //if (fnd != NULL) printf("scanning bss %p, %d\n",*fnd,isLeakSlot(*fnd));
326     if (fnd != NULL && isLeakSlot(*fnd)) {
327       found = *fnd;
328       /* mark slot as not leak */
329       //printf("bss pointing to %p\n",found+1);
330       found->magic &= ~LEAK_FLAG;
331       /* move the slot a inProgress */
332       found->next->prev = found->prev;
333       found->prev->next = found->next;
334       found->next = inProgress.next;
335       found->prev = &inProgress;
336       found->next->prev = found;
337       found->prev->next = found;
338     }
339   }
340
341   // Step 3)
342   // continue iteratively to check the memory by sweeping it with the
343   // "inProcess" list
344   while (inProgress.next != &inProgress) {
345     sl = inProgress.next;
346     printf("scanning memory %p of size %d\n",sl,sl->userSize);
347     /* move slot back to the main list (slot_first) */
348     sl->next->prev = sl->prev;
349     sl->prev->next = sl->next;
350     sl->next = slot_first->next;
351     sl->prev = slot_first;
352     sl->next->prev = sl;
353     sl->prev->next = sl;
354     /* scan through this memory and pick all the slots which are still leaking
355        and add them to the inProgress list */
356     if (sl->extraStack != NULL && sl->extraStack->protectedMemory != NULL) mprotect(sl->extraStack->protectedMemory, sl->extraStack->protectedMemoryLength, PROT_READ);
357     for (scanner = ((char*)sl)+sizeof(Slot); scanner < ((char*)sl)+sizeof(Slot)+sl->userSize-sizeof(char*)+1; scanner+=sizeof(char*)) {
358       fnd = (Slot**)CkHashtableGet(table, scanner);
359       //if (fnd != NULL) printf("scanning heap %p, %d\n",*fnd,isLeakSlot(*fnd));
360       if (fnd != NULL && isLeakSlot(*fnd)) {
361         found = *fnd;
362         /* mark slot as not leak */
363         //printf("heap pointing to %p\n",found+1);
364         found->magic &= ~LEAK_FLAG;
365         /* move the slot a inProgress */
366         found->next->prev = found->prev;
367         found->prev->next = found->next;
368         found->next = inProgress.next;
369         found->prev = &inProgress;
370         found->next->prev = found;
371         found->prev->next = found;
372       }
373     }
374     if (sl->extraStack != NULL && sl->extraStack->protectedMemory != NULL) mprotect(sl->extraStack->protectedMemory, sl->extraStack->protectedMemoryLength, PROT_NONE);
375   }
376
377   // Step 4)
378   // move back all the entries in leaking to slot_first
379   if (leaking.next != &leaking) {
380     leaking.next->prev = slot_first;
381     leaking.prev->next = slot_first->next;
382     slot_first->next->prev = leaking.prev;
383     slot_first->next = leaking.next;
384   }
385
386
387   // mark all the entries in the leaking list as leak, and put them back
388   // into the main list
389   /*sl = leaking.next;
390   while (sl != &leaking) {
391     sl->magic | LEAK_FLAG;
392   }
393   if (leaking.next != &leaking) {
394     slot_first->next->prev = leaking.prev;
395     leaking.prev->next = slot_first->next;
396     leaking.next->prev = slot_first;
397     slot_first->next = leaking.next;
398   }  
399   */
400
401   CkDeleteHashtable(table);
402 }
403
404 /****************** memory allocation tree ******************/
405
406 /* This allows the representation and creation of a tree where each node
407  * represents a line in the code part of a stack trace of a malloc. The node
408  * contains how much data has been allocated starting from that line of code,
409  * down the stack.
410  */
411
412 typedef struct _AllocationPoint AllocationPoint;
413
414 struct _AllocationPoint {
415   /* The stack pointer this allocation refers to */
416   void * key;
417   /* Pointer to the parent AllocationPoint of this AllocationPoint in the tree */
418   AllocationPoint * parent;
419   /* Pointer to the first child AllocationPoint in the tree */
420   AllocationPoint * firstChild;
421   /* Pointer to the sibling of this AllocationPoint (i.e the next child of the parent) */
422   AllocationPoint * sibling;
423   /* Pointer to the next AllocationPoint with the same key.
424    * There can be more than one AllocationPoint with the same key because the
425    * parent can be different. Used only in the hashtable. */
426   AllocationPoint * next;
427   /* Size of the memory allocate */
428   int size;
429   /* How many blocks have been allocated from this point */
430   int count;
431   /* Flags pertaining to the allocation point, currently only LEAK_FLAG */
432   char flags;
433 };
434
435 // pup a single AllocationPoint. The data structure must be already allocated
436 void pupAllocationPointSingle(pup_er p, AllocationPoint *node, int *numChildren) {
437   pup_pointer(p, &node->key);
438   pup_int(p, &node->size);
439   pup_int(p, &node->count);
440   pup_char(p, &node->flags);
441   if (pup_isUnpacking(p)) {
442     node->parent = NULL;
443     node->firstChild = NULL;
444     node->sibling = NULL;
445     node->next = NULL;
446   }
447   *numChildren = 0;
448   AllocationPoint *child;
449   for (child = node->firstChild; child != NULL; child = child->sibling) (*numChildren) ++;
450   pup_int(p, numChildren);
451  
452 }
453
454 // TODO: the following pup does not work for unpacking!
455 void pupAllocationPoint(pup_er p, void *data) {
456   AllocationPoint *node = (AllocationPoint*)data;
457   int numChildren;
458   pupAllocationPointSingle(p, node, &numChildren);
459   AllocationPoint *child;
460   for (child = node->firstChild; child != NULL; child = child->sibling) {
461     pupAllocationPoint(p, child);
462   }
463 }
464
465 void deleteAllocationPoint(void *ptr) {
466   AllocationPoint *node = (AllocationPoint*)ptr;
467   AllocationPoint *child;
468   for (child = node->firstChild; child != NULL; child = child->sibling) deleteAllocationPoint(child);
469   mm_free(node);
470 }
471
472 void printAllocationTree(AllocationPoint *node, FILE *fd, int depth) {
473   int i;
474   if (node==NULL) return;
475   int numChildren = 0;
476   AllocationPoint *child;
477   for (child = node->firstChild; child != NULL; child = child->sibling) numChildren ++; 
478   for (i=0; i<depth; ++i) fprintf(fd, " ");
479   fprintf(fd, "node %p: bytes=%d, count=%d, child=%d\n",node->key,node->size,node->count,numChildren);
480   printAllocationTree(node->sibling, fd, depth);
481   printAllocationTree(node->firstChild, fd, depth+2);
482 }
483
484 AllocationPoint * CreateAllocationTree(int *nodesCount) {
485   Slot *scanner;
486   CkHashtable_c table;
487   int i, new;
488   AllocationPoint *parent, **start, *cur;
489   AllocationPoint *root = NULL;
490   int numNodes = 0;
491   
492   scanner=slot_first->next;
493   table = CkCreateHashtable_pointer(sizeof(char *), 10000);
494
495   for ( ; scanner!=slot_first; scanner=scanner->next) {
496     parent = NULL;
497     for (i=scanner->stackLen-1; i>=0; --i) {
498       new = 0;
499       start = CkHashtableGet(table, &scanner->from[i]);
500       if (start == NULL) {
501         cur = (AllocationPoint*) mm_malloc(sizeof(AllocationPoint));
502         numNodes ++;
503         new = 1;
504         cur->next = cur;
505         *(AllocationPoint**)CkHashtablePut(table, &scanner->from[i]) = cur;
506       } else {
507         for (cur = (*start)->next; cur != *start && cur->parent != parent; cur = cur->next);
508         if (cur->parent != parent) {
509           cur = (AllocationPoint*) mm_malloc(sizeof(AllocationPoint));
510           numNodes ++;
511           new = 1;
512           cur->next = (*start)->next;
513           (*start)->next = cur;
514         }
515       }
516       // here "cur" points to the correct AllocationPoint for this stack frame
517       if (new) {
518         cur->key = scanner->from[i];
519         cur->parent = parent;
520         cur->size = 0;
521         cur->count = 0;
522         cur->flags = 0;
523         cur->firstChild = NULL;
524         if (parent == NULL) {
525           cur->sibling = NULL;
526           CmiAssert(root == NULL);
527           root = cur;
528         } else {
529           cur->sibling = parent->firstChild;
530           parent->firstChild = cur;
531         }
532       }
533       cur->size += scanner->userSize;
534       cur->count ++;
535       cur->flags |= isLeakSlot(scanner);
536       parent = cur;
537     }
538   }
539   
540   char filename[100];
541   sprintf(filename, "allocationTree_%d", CmiMyPe());
542   FILE *fd = fopen(filename, "w");
543   fprintf(fd, "digraph %s {\n", filename);
544   CkHashtableIterator_c it = CkHashtableGetIterator(table);
545   AllocationPoint **startscan, *scan;
546   while ((startscan=CkHashtableIteratorNext(it,NULL))!=NULL) {
547     fprintf(fd, "\t\"n%p\" [label=\"%p\\nsize=%d\\ncount=%d\"];\n",*startscan,(*startscan)->key,
548           (*startscan)->size,(*startscan)->count);
549     for (scan = (*startscan)->next; scan != *startscan; scan = scan->next) {
550       fprintf(fd, "\t\"n%p\" [label=\"%p\\nsize=%d\\ncount=%d\"];\n",scan,scan->key,scan->size,scan->count);
551     }
552   }
553   CkHashtableIteratorSeekStart(it);
554   while ((startscan=CkHashtableIteratorNext(it,NULL))!=NULL) {
555     fprintf(fd, "\t\"n%p\" -> \"n%p\";\n",(*startscan)->parent,(*startscan));
556     for (scan = (*startscan)->next; scan != *startscan; scan = scan->next) {
557       fprintf(fd, "\t\"n%p\" -> \"n%p\";\n",scan->parent,scan);
558     }
559   }
560   fprintf(fd, "}\n");
561   fclose(fd);
562   
563   sprintf(filename, "allocationTree_%d.tree", CmiMyPe());
564   fd = fopen(filename, "w");
565   printAllocationTree(root, fd, 0);
566   fclose(fd);
567  
568   CkDeleteHashtable(table);
569   if (nodesCount != NULL) *nodesCount = numNodes;
570   return root;
571 }
572
573 void MergeAllocationTreeSingle(AllocationPoint *node, AllocationPoint *remote, int numChildren, pup_er p) {
574   AllocationPoint child;
575   int numChildChildren;
576   int i;
577   //pupAllocationPointSingle(p, &remote, &numChildren);
578   /* Update the node with the information coming from remote */
579   node->size += remote->size;
580   node->count += remote->count;
581   node->flags |= remote->flags;
582   /* Recursively merge the children */
583   for (i=0; i<numChildren; ++i) {
584     AllocationPoint *localChild;
585     pupAllocationPointSingle(p, &child, &numChildChildren);
586     /* Find the child in the local tree */
587     for (localChild = node->firstChild; localChild != NULL; localChild = localChild->sibling) {
588       if (localChild->key == child.key) {
589         break;
590       }
591     }
592     if (localChild == NULL) {
593       /* This child did not exist locally, allocate it */
594       localChild = (AllocationPoint*) mm_malloc(sizeof(AllocationPoint));
595       localChild->key = child.key;
596       localChild->flags = 0;
597       localChild->count = 0;
598       localChild->size = 0;
599       localChild->firstChild = NULL;
600       localChild->next = NULL;
601       localChild->parent = node;
602       localChild->sibling = node->firstChild;
603       node->firstChild = localChild;
604     }
605     MergeAllocationTreeSingle(localChild, &child, numChildChildren, p);
606   }
607 }
608
609 void * MergeAllocationTree(void *data, void **remoteData, int numRemote) {
610   int i;
611   for (i=0; i<numRemote; ++i) {
612     pup_er p = pup_new_fromMem(remoteData[i]);
613     AllocationPoint root;
614     int numChildren;
615     pupAllocationPointSingle(p, &root, &numChildren);
616     MergeAllocationTreeSingle((AllocationPoint*)data, &root, numChildren, p);
617   }
618   return data;
619 }
620
621 /*
622
623 / *Head of the current circular allocated block list* /
624 Slot slot_first_storage={&slot_first_storage,&slot_first_storage};
625 Slot *slot_first=&slot_first_storage;
626
627 #define CMI_MEMORY_ROUTINES 1
628
629 / * Mark all allocated memory as being OK * /
630 void CmiMemoryMark(void) {
631         CmiMemLock();
632         / * Just make a new linked list of slots * /
633         slot_first=(Slot *)mm_malloc(sizeof(Slot));
634         slot_first->next=slot_first->prev=slot_first;
635         CmiMemUnlock();
636 }
637
638 / * Mark this allocated block as being OK * /
639 void CmiMemoryMarkBlock(void *blk) {
640         Slot *s=Slot_fmUser(blk);
641         CmiMemLock();
642         if (s->magic!=SLOTMAGIC) CmiAbort("CmiMemoryMarkBlock called on non-malloc'd block!\n");
643         / * Splice us out of the current linked list * /
644         s->next->prev=s->prev;
645         s->prev->next=s->next;
646         s->prev=s->next=s; / * put us in our own list * /
647         CmiMemUnlock();
648 }
649
650 / * Print out all allocated memory * /
651 void CmiMemorySweep(const char *where) {
652         Slot *cur;
653         int nBlocks=0,nBytes=0;
654         CmiMemLock();
655         cur=slot_first->next;
656         CmiPrintf("[%d] ------- LEAK CHECK: %s -----\n",CmiMyPe(), where);
657         while (cur!=slot_first) {
658                 printSlot(cur);
659                 nBlocks++; nBytes+=cur->userSize;
660                 cur=cur->next;
661         }
662         if (nBlocks) {
663                 CmiPrintf("[%d] Total leaked memory: %d blocks, %d bytes\n",
664                         CmiMyPe(),nBlocks,nBytes);
665                 / * CmiAbort("Memory leaks detected!\n"); * /
666         }
667         CmiMemUnlock();
668         CmiMemoryMark();
669 }
670 void CmiMemoryCheck(void) {}
671 */
672
673
674 /********** Allocation/Free ***********/
675
676 static int memoryTraceDisabled = 0;
677 #define MAX_STACK_FRAMES   2048
678 static int numStackFrames; // the number of frames presetn in stackFrames - 4 (this number is trimmed at 0
679 static void *stackFrames[MAX_STACK_FRAMES];
680
681 /* Write a valid slot to this field */
682 static void *setSlot(Slot *s,int userSize) {
683   char *user=SlotToUser(s);
684   
685   /* Splice into the slot list just past the head */
686   s->next=slot_first->next;
687   s->prev=slot_first;
688   s->next->prev=s;
689   s->prev->next=s;
690   
691   /* Set the last 4 bits of magic to classify the memory together with the magic */
692   s->magic=SLOTMAGIC + (memory_status_info>0? USER_TYPE : SYSTEM_TYPE);
693   //if (memory_status_info>0) printf("user allocation\n");
694   s->chareID = memory_chare_id;
695   s->userSize=userSize;
696   s->extraStack=(SlotStack *)0;
697
698   /* Set the stack frames */
699   s->stackLen=numStackFrames;
700   s->from=(void**)(user+userSize);
701   memcpy(s->from, &stackFrames[4], numStackFrames*sizeof(void*));
702   
703   return (void *)user;
704 }
705
706 /* Delete this slot structure */
707 static void freeSlot(Slot *s) {
708   /* Splice out of the slot list */
709   s->next->prev=s->prev;
710   s->prev->next=s->next;
711   s->prev=s->next=(Slot *)0;//0x0F00; why was it not 0?
712
713   s->magic=SLOTMAGIC_FREED;
714   s->userSize=-1;
715 }
716
717 void dumpStackFrames() {
718   numStackFrames=MAX_STACK_FRAMES;
719   if (memoryTraceDisabled==0) {
720     memoryTraceDisabled = 1;
721     CmiBacktraceRecordHuge(stackFrames,&numStackFrames);
722     memoryTraceDisabled = 0;
723     numStackFrames-=4;
724     if (numStackFrames < 0) numStackFrames = 0;
725   } else {
726     numStackFrames=0;
727     stackFrames[0] = (void*)0;
728   }
729 }
730
731 /********** meta_ routines ***********/
732
733 /* Return the system page size */
734 static int meta_getpagesize(void) {
735   static int cache=0;
736 #if defined(CMK_GETPAGESIZE_AVAILABLE)
737   if (cache==0) cache=getpagesize();
738 #else
739   if (cache==0) cache=8192;
740 #endif
741   return cache;
742 }
743
744 /* Only display startup status messages from processor 0 */
745 static void status(char *msg) {
746   if (CmiMyPe()==0 && !CmiArgGivingUsage()) {
747     CmiPrintf("%s",msg);
748   }
749 }
750
751 extern int getCharmEnvelopeSize();
752
753 static void meta_init(char **argv) {
754   status("Converse -memory mode: charmdebug\n");
755   char buf[100];
756   sprintf(buf,"slot size %d\n",sizeof(Slot));
757   status(buf);
758   charmEnvelopeSize = getCharmEnvelopeSize();
759   CpdDebugGetAllocationTree = CreateAllocationTree;
760   CpdDebug_pupAllocationPoint = pupAllocationPoint;
761   CpdDebug_deleteAllocationPoint = deleteAllocationPoint;
762   CpdDebug_MergeAllocationTree = MergeAllocationTree;
763   memory_allocated_user_total = 0;
764   nextChareID = 1;
765 }
766
767 static void *meta_malloc(size_t size) {
768   dumpStackFrames();
769   Slot *s=(Slot *)mm_malloc(sizeof(Slot)+size+numStackFrames*sizeof(void*));
770   char *user = (char*)s;
771   if (s!=NULL) user = setSlot(s,size);
772   memory_allocated_user_total += size;
773   traceMalloc_c(user, size, s->from, s->stackLen);
774   return user;
775 }
776
777 static void meta_free(void *mem) {
778   Slot *s;
779   int memSize = 0;
780   if (mem!=NULL) memSize = (((Slot*)mem)-1)->userSize;
781   memory_allocated_user_total -= memSize;
782   traceFree_c(mem, memSize);
783   if (mem==NULL) return; /*Legal, but misleading*/
784
785   s=((Slot *)mem)-1;
786   if ((s->magic&~FLAGS_MASK)==SLOTMAGIC_VALLOC)
787   { /*Allocated with special alignment*/
788     freeSlot(s);
789     mm_free(s->extraStack);
790     /*mm_free(((char *)mem)-meta_getpagesize());*/
791   }
792   else if ((s->magic&~FLAGS_MASK)==SLOTMAGIC) 
793   { /*Ordinary allocated block */
794     freeSlot(s);
795     mm_free(s);
796   }
797   else if (s->magic==SLOTMAGIC_FREED)
798     CmiAbort("Free'd block twice");
799   else /*Unknown magic number*/
800     CmiAbort("Free'd non-malloc'd block");
801 }
802
803 static void *meta_calloc(size_t nelem, size_t size) {
804   void *area=meta_malloc(nelem*size);
805   memset(area,0,nelem*size);
806   return area;
807 }
808
809 static void meta_cfree(void *mem) {
810   meta_free(mem);
811 }
812
813 static void *meta_realloc(void *oldBuffer, size_t newSize) {
814   void *newBuffer = meta_malloc(newSize);
815   if ( newBuffer && oldBuffer ) {
816     /*Preserve old buffer contents*/
817     Slot *o=UserToSlot(oldBuffer);
818     size_t size=o->userSize;
819     if (size>newSize) size=newSize;
820     if (size > 0)
821       memcpy(newBuffer, oldBuffer, size);
822
823     meta_free(oldBuffer);
824   }
825   return newBuffer;
826 }
827
828 static void *meta_memalign(size_t align, size_t size) {
829   int overhead = align;
830   while (overhead < sizeof(Slot)+sizeof(SlotStack)) overhead += align;
831   /* Allocate the required size + the overhead needed to keep the user alignment */
832   dumpStackFrames();
833   
834   char *alloc=(char *)mm_memalign(align,overhead+size+numStackFrames*sizeof(void*));
835   Slot *s=(Slot *)(alloc+overhead-sizeof(Slot));  
836   void *user=setSlot(s,size);
837   s->magic = SLOTMAGIC_VALLOC + (s->magic&0xF);
838   s->extraStack = (SlotStack *)alloc; /* use the extra space as stack */
839   s->extraStack->protectedMemory = NULL;
840   s->extraStack->protectedMemoryLength = 0;
841   memory_allocated_user_total += size;
842   traceMalloc_c(user, size, s->from, s->stackLen);
843   return user;  
844 }
845
846 static void *meta_valloc(size_t size) {
847   return meta_memalign(meta_getpagesize(),size);
848 }
849
850 void setProtection(char* mem, char *ptr, int len, int flag) {
851   Slot *sl = (Slot*)(mem-sizeof(Slot));
852   if (sl->extraStack == NULL) CmiAbort("Tried to protect memory not memaligned\n");
853   if (flag != 0) {
854     sl->extraStack->protectedMemory = ptr;
855     sl->extraStack->protectedMemoryLength = len;
856   } else {
857     sl->extraStack->protectedMemory = NULL;
858     sl->extraStack->protectedMemoryLength = 0;
859   }
860 }
861
862 void setMemoryTypeChare(void *ptr) {
863   Slot *sl = UserToSlot(ptr);
864   sl->magic = (sl->magic & ~FLAGS_MASK) | CHARE_TYPE;
865   sl->chareID = nextChareID;
866   nextChareID ++;
867 }
868
869 /* The input parameter is the pointer to the envelope, after the CmiChunkHeader */
870 void setMemoryTypeMessage(void *ptr) {
871   void *realptr = (char*)ptr - sizeof(CmiChunkHeader);
872   Slot *sl = UserToSlot(realptr);
873   if ((sl->magic&~FLAGS_MASK) == SLOTMAGIC || (sl->magic&~FLAGS_MASK) == SLOTMAGIC_VALLOC) {
874     sl->magic = (sl->magic & ~FLAGS_MASK) | MESSAGE_TYPE;
875   }
876 }
877
878 void setMemoryChareID(void *ptr) {
879   if (ptr == NULL || ptr == 0) memory_chare_id = 0;
880   else memory_chare_id = UserToSlot(ptr)->chareID;
881 }