Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
1bf6f9b98edf7aced0670630e451ed4f65b0e967
[simgrid.git] / src / xbt / mmalloc / mm_diff.c
1 /* mm_diff - Memory snapshooting and comparison                             */
2
3 /* Copyright (c) 2008-2012. The SimGrid Team. All rights reserved.          */
4
5 /* This program is free software; you can redistribute it and/or modify it
6  * under the terms of the license (GNU LGPL) which comes with this package. */
7
8 #include "xbt/ex_interface.h" /* internals of backtrace setup */
9 #include "xbt/str.h"
10 #include "mc/mc.h"
11 #include "xbt/mmalloc.h"
12
13 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mm_diff, xbt,
14                                 "Logging specific to mm_diff in mmalloc");
15
16 xbt_dynar_t mc_heap_comparison_ignore;
17 xbt_dynar_t stacks_areas;
18
19 static void heap_area_pair_free(heap_area_pair_t pair);
20 static void heap_area_pair_free_voidp(void *d);
21 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2);
22 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2);
23 static heap_area_t new_heap_area(int block, int fragment);
24
25 static size_t heap_comparison_ignore_size(void *address);
26 static void add_heap_equality(xbt_dynar_t equals, void *a1, void *a2);
27 static void remove_heap_equality(xbt_dynar_t equals, int address, void *a);
28
29 static char* is_stack(void *address);
30
31 void mmalloc_backtrace_block_display(void* heapinfo, int block){
32
33   /* xbt_ex_t e; */
34
35   /* if (((malloc_info *)heapinfo)[block].busy_block.bt_size == 0) { */
36   /*   fprintf(stderr, "No backtrace available for that block, sorry.\n"); */
37   /*   return; */
38   /* } */
39
40   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_block.bt),sizeof(void*)*XBT_BACKTRACE_SIZE); */
41   /* e.used = ((malloc_info *)heapinfo)[block].busy_block.bt_size; */
42
43   /* xbt_ex_setup_backtrace(&e); */
44   /* if (e.used == 0) { */
45   /*   fprintf(stderr, "(backtrace not set)\n"); */
46   /* } else if (e.bt_strings == NULL) { */
47   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
48   /* } else { */
49   /*   int i; */
50
51   /*   fprintf(stderr, "Backtrace of where the block %d was malloced (%d frames):\n", block ,e.used); */
52   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
53   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
54   /*   } */
55   /* } */
56 }
57
58 void mmalloc_backtrace_fragment_display(void* heapinfo, int block, int frag){
59
60   /* xbt_ex_t e; */
61
62   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_frag.bt[frag]),sizeof(void*)*XBT_BACKTRACE_SIZE); */
63   /* e.used = XBT_BACKTRACE_SIZE; */
64
65   /* xbt_ex_setup_backtrace(&e); */
66   /* if (e.used == 0) { */
67   /*   fprintf(stderr, "(backtrace not set)\n"); */
68   /* } else if (e.bt_strings == NULL) { */
69   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
70   /* } else { */
71   /*   int i; */
72
73   /*   fprintf(stderr, "Backtrace of where the fragment %d in block %d was malloced (%d frames):\n", frag, block ,e.used); */
74   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
75   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
76   /*   } */
77   /* } */
78
79 }
80
81 void mmalloc_backtrace_display(void *addr){
82
83   /* size_t block, frag_nb; */
84   /* int type; */
85   
86   /* xbt_mheap_t heap = __mmalloc_current_heap ?: (xbt_mheap_t) mmalloc_preinit(); */
87
88   /* block = (((char*) (addr) - (char*) heap -> heapbase) / BLOCKSIZE + 1); */
89
90   /* type = heap->heapinfo[block].type; */
91
92   /* switch(type){ */
93   /* case -1 : /\* Free block *\/ */
94   /*   fprintf(stderr, "Asked to display the backtrace of a block that is free. I'm puzzled\n"); */
95   /*   xbt_abort(); */
96   /*   break;  */
97   /* case 0: /\* Large block *\/ */
98   /*   mmalloc_backtrace_block_display(heap->heapinfo, block); */
99   /*   break; */
100   /* default: /\* Fragmented block *\/ */
101   /*   frag_nb = RESIDUAL(addr, BLOCKSIZE) >> type; */
102   /*   if(heap->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){ */
103   /*     fprintf(stderr , "Asked to display the backtrace of a fragment that is free. I'm puzzled\n"); */
104   /*     xbt_abort(); */
105   /*   } */
106   /*   mmalloc_backtrace_fragment_display(heap->heapinfo, block, frag_nb); */
107   /*   break; */
108   /* } */
109 }
110
111
112 void *s_heap = NULL, *heapbase1 = NULL, *heapbase2 = NULL;
113 malloc_info *heapinfo1 = NULL, *heapinfo2 = NULL;
114 size_t heaplimit = 0, heapsize1 = 0, heapsize2 = 0;
115
116 int ignore_done = 0;
117
118 void init_heap_information(xbt_mheap_t heap1, xbt_mheap_t heap2){
119
120   heaplimit = ((struct mdesc *)heap1)->heaplimit;
121
122   s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
123
124   heapbase1 = (char *)heap1 + BLOCKSIZE;
125   heapbase2 = (char *)heap2 + BLOCKSIZE;
126
127   heapinfo1 = (malloc_info *)((char *)heap1 + ((uintptr_t)((char *)heap1->heapinfo - (char *)s_heap)));
128   heapinfo2 = (malloc_info *)((char *)heap2 + ((uintptr_t)((char *)heap2->heapinfo - (char *)s_heap)));
129
130   heapsize1 = heap1->heapsize;
131   heapsize2 = heap2->heapsize;
132   
133 }
134
135 int mmalloc_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t *stack1, xbt_dynar_t *stack2, xbt_dynar_t equals){
136
137   if(heap1 == NULL && heap1 == NULL){
138     XBT_DEBUG("Malloc descriptors null");
139     return 0;
140   }
141
142   if(heap1->heaplimit != heap2->heaplimit){
143     XBT_DEBUG("Different limit of valid info table indices");
144     return 1;
145   }
146
147   /* Start comparison */
148   size_t i1, i2, j1, j2, k, current_block, current_fragment;
149   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
150   void *snap_addr_block1, *snap_addr_block2;
151   char *stack_name;
152   int nb_diff1 = 0, nb_diff2 = 0;
153
154   xbt_dynar_t previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
155
156   int equal, res_compare = 0;
157
158   /* Check busy blocks*/
159
160   i1 = 1;
161
162   while(i1 <= heaplimit){
163
164     current_block = i1;
165
166     if(heapinfo1[i1].type == -1){ /* Free block */
167       i1++;
168       continue;
169     }
170
171     addr_block1 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
172     snap_addr_block1 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)heapbase1));
173
174     if(heapinfo1[i1].type == 0){  /* Large block */
175       
176       if((xbt_dynar_length(*stack1) < xbt_dynar_length(stacks_areas)) && ((stack_name = is_stack(addr_block1)) != NULL)){
177         stack_region_t stack = xbt_new0(s_stack_region_t, 1);
178         stack->address = snap_addr_block1;
179         stack->process_name = strdup(stack_name);
180         stack->size = heapinfo1[i1].busy_block.busy_size;
181         xbt_dynar_push(*stack1, &stack);
182         res_compare = -1;
183       }
184
185       if(heapinfo1[i1].busy_block.equal_to != NULL){
186         i1++;
187         continue;
188       }
189     
190       i2 = 1;
191       equal = 0;
192       res_compare = 0;
193   
194       /* Try first to associate to same block in the other heap */
195       if(heapinfo2[current_block].type == heapinfo1[current_block].type){
196
197         if(heapinfo2[current_block].busy_block.equal_to == NULL){  
198         
199           addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
200           snap_addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)heapbase2));
201           
202           if((xbt_dynar_length(*stack2) < xbt_dynar_length(stacks_areas)) && ((stack_name = is_stack(addr_block2)) != NULL)){
203             stack_region_t stack = xbt_new0(s_stack_region_t, 1);
204             stack->address = snap_addr_block2;
205             stack->process_name = strdup(stack_name);
206             stack->size = heapinfo2[current_block].busy_block.busy_size;
207             xbt_dynar_push(*stack2, &stack);
208             res_compare = -1;
209           }
210         
211           res_compare = compare_area(addr_block1, addr_block2, previous, equals);
212         
213           if(res_compare == 0 || res_compare == -1){
214             for(k=1; k < heapinfo2[current_block].busy_block.size; k++)
215               heapinfo2[current_block+k].busy_block.equal_to = new_heap_area(i1, -1);
216             for(k=1; k < heapinfo1[current_block].busy_block.size; k++)
217               heapinfo1[current_block+k].busy_block.equal_to = new_heap_area(i1, -1);
218             equal = 1;
219             match_equals(previous, equals);
220             i1 = i1 + heapinfo1[current_block].busy_block.size;
221           }
222         
223           xbt_dynar_reset(previous);
224         
225         }
226         
227       }
228
229       while(i2 <= heaplimit && !equal){
230
231         addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));        
232         snap_addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)heapbase2));
233         
234         if((xbt_dynar_length(*stack2) < xbt_dynar_length(stacks_areas)) && ((stack_name = is_stack(addr_block2)) != NULL)){
235           stack_region_t stack = xbt_new0(s_stack_region_t, 1);
236           stack->address = snap_addr_block2;
237           stack->process_name = strdup(stack_name);
238           stack->size = heapinfo2[i2].busy_block.busy_size;
239           xbt_dynar_push(*stack2, &stack);
240           res_compare = -1;
241         }
242            
243         if(i2 == current_block){
244           i2++;
245           continue;
246         }
247
248         if(heapinfo2[i2].type != 0){
249           i2++;
250           continue;
251         }
252
253         if(heapinfo2[i2].busy_block.equal_to != NULL){         
254           i2++;
255           continue;
256         }
257         
258         res_compare = compare_area(addr_block1, addr_block2, previous, equals);
259         
260         if(res_compare == 0 || res_compare == -1){
261           for(k=1; k < heapinfo2[i2].busy_block.size; k++)
262             heapinfo2[i2+k].busy_block.equal_to = new_heap_area(i1, -1);
263           for(k=1; k < heapinfo1[i1].busy_block.size; k++)
264             heapinfo1[i1+k].busy_block.equal_to = new_heap_area(i2, -1);
265           equal = 1;
266           match_equals(previous, equals);
267           i1 = i1 + heapinfo1[i1].busy_block.size;
268         }
269
270         xbt_dynar_reset(previous);
271
272         i2++;
273
274       }
275
276       if(!equal){
277         XBT_DEBUG("Block %zu not found (size_used = %zu)", i1, heapinfo1[i1].busy_block.busy_size);
278         i1 = heaplimit + 1;
279         nb_diff1++;
280       }
281       
282     }else{ /* Fragmented block */
283
284       for(j1=0; j1 < (size_t) (BLOCKSIZE >> heapinfo1[i1].type); j1++){
285
286         current_fragment = j1;
287
288         if(heapinfo1[i1].busy_frag.frag_size[j1] == -1) /* Free fragment */
289           continue;
290
291         if(heapinfo1[i1].busy_frag.equal_to[j1] != NULL)
292           continue;
293
294         addr_frag1 = (void*) ((char *)addr_block1 + (j1 << heapinfo1[i1].type));
295
296         i2 = 1;
297         equal = 0;
298         
299         /* Try first to associate to same fragment in the other heap */
300         if(heapinfo2[current_block].type == heapinfo1[current_block].type){
301
302           if(heapinfo2[current_block].busy_frag.equal_to[current_fragment] == NULL){  
303           
304             addr_block2 = ((void*) (((ADDR2UINT(current_block)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
305             addr_frag2 = (void*) ((char *)addr_block2 + (current_fragment << ((xbt_mheap_t)s_heap)->heapinfo[current_block].type));
306
307             res_compare = compare_area(addr_frag1, addr_frag2, previous, equals);
308
309             if(res_compare == 0){
310               equal = 1;
311               match_equals(previous, equals);
312             }
313         
314             xbt_dynar_reset(previous);
315
316             }
317         }
318
319         while(i2 <= heaplimit && !equal){
320
321           
322           if(heapinfo2[i2].type <= 0){
323             i2++;
324             continue;
325           }
326
327           for(j2=0; j2 < (size_t) (BLOCKSIZE >> heapinfo2[i2].type); j2++){
328
329             if(heapinfo2[i2].type == heapinfo1[i1].type && i2 == current_block && j2 == current_fragment)
330               continue;
331
332             if(heapinfo2[i2].busy_frag.equal_to[j2] != NULL)                
333               continue;              
334                           
335             addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
336             addr_frag2 = (void*) ((char *)addr_block2 + (j2 << ((xbt_mheap_t)s_heap)->heapinfo[i2].type));
337
338             res_compare = compare_area(addr_frag1, addr_frag2, previous, equals);
339             
340             if(res_compare == 0){
341               equal = 1;
342               match_equals(previous, equals);
343               xbt_dynar_reset(previous);
344               break;
345             }
346
347             xbt_dynar_reset(previous);
348
349           }
350
351           i2++;
352
353         }
354
355         if(heapinfo1[i1].busy_frag.equal_to[j1] == NULL){
356           XBT_DEBUG("Block %zu, fragment %zu not found (size_used = %d)", i1, j1, heapinfo1[i1].busy_frag.frag_size[j1]);
357           i2 = heaplimit + 1;
358           i1 = heaplimit + 1;
359           nb_diff1++;
360           break;
361         }
362
363       }
364
365       i1++;
366       
367     }
368
369   }
370
371   /* All blocks/fragments are equal to another block/fragment ? */
372   size_t i = 1, j = 0;
373  
374   while(i<=heaplimit){
375     if(heapinfo1[i].type == 0){
376       if(current_block == heaplimit){
377         if(heapinfo1[i].busy_block.busy_size > 0){
378           if(heapinfo1[i].busy_block.equal_to == NULL){
379             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
380               addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
381               XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block1, heapinfo1[i].busy_block.busy_size);
382               //mmalloc_backtrace_block_display((void*)heapinfo1, i);
383             }
384             nb_diff1++;
385           }
386         }
387       }
388       xbt_free(heapinfo1[i].busy_block.equal_to);
389       heapinfo1[i].busy_block.equal_to = NULL;
390     }
391     if(heapinfo1[i].type > 0){
392       addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
393       for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo1[i].type); j++){
394         if(current_block == heaplimit){
395           if(heapinfo1[i].busy_frag.frag_size[j] > 0){
396             if(heapinfo1[i].busy_frag.equal_to[j] == NULL){
397               if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
398                 addr_frag1 = (void*) ((char *)addr_block1 + (j << heapinfo1[i].type));
399                 XBT_DEBUG("Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag1, heapinfo1[i].busy_frag.frag_size[j]);
400                 //mmalloc_backtrace_fragment_display((void*)heapinfo1, i, j);
401               }
402               nb_diff1++;
403             }
404           }
405         }
406         xbt_free(heapinfo1[i].busy_frag.equal_to[j]);
407         heapinfo1[i].busy_frag.equal_to[j] = NULL;
408       }
409     }
410     i++; 
411   }
412
413   i = 1;
414
415   while(i<=heaplimit){
416     if(heapinfo2[i].type == 0){
417       if(current_block == heaplimit){
418         if(heapinfo2[i].busy_block.busy_size > 0){
419           if(heapinfo2[i].busy_block.equal_to == NULL){
420             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
421               addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
422               XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block2, heapinfo2[i].busy_block.busy_size);
423               //mmalloc_backtrace_block_display((void*)heapinfo2, i);
424             }
425             nb_diff2++;
426           }
427         }
428       }
429       xbt_free(heapinfo2[i].busy_block.equal_to);
430       heapinfo2[i].busy_block.equal_to = NULL;
431     }
432     if(heapinfo2[i].type > 0){
433       addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
434       for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo2[i].type); j++){
435         if(current_block == heaplimit){
436           if(heapinfo2[i].busy_frag.frag_size[j] > 0){
437             if(heapinfo2[i].busy_frag.equal_to[j] == NULL){
438               if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
439                 addr_frag2 = (void*) ((char *)addr_block2 + (j << heapinfo2[i].type));
440                 XBT_DEBUG( "Block %zu, Fragment %zu (%p) not found (size used = %d)", i, j, addr_frag2, heapinfo2[i].busy_frag.frag_size[j]);
441                 //mmalloc_backtrace_fragment_display((void*)heapinfo2, i, j);
442               }
443               nb_diff2++;
444             }
445           }
446         }
447         xbt_free(heapinfo2[i].busy_frag.equal_to[j]);
448         heapinfo2[i].busy_frag.equal_to[j] = NULL;
449       }
450     }
451     i++; 
452   }
453
454   xbt_dynar_free(&previous);
455   ignore_done = 0;
456   s_heap = NULL, heapbase1 = NULL, heapbase2 = NULL;
457   heapinfo1 = NULL, heapinfo2 = NULL;
458   heaplimit = 0, heapsize1 = 0, heapsize2 = 0;
459
460   return ((nb_diff1 > 0) || (nb_diff2 > 0));
461 }
462
463 static heap_area_t new_heap_area(int block, int fragment){
464   heap_area_t area = NULL;
465   area = xbt_new0(s_heap_area_t, 1);
466   area->block = block;
467   area->fragment = fragment;
468   return area;
469 }
470
471
472 static size_t heap_comparison_ignore_size(void *address){
473
474   unsigned int cursor = 0;
475   int start = 0;
476   int end = xbt_dynar_length(mc_heap_comparison_ignore) - 1;
477   mc_heap_ignore_region_t region;
478
479   while(start <= end){
480     cursor = (start + end) / 2;
481     region = (mc_heap_ignore_region_t)xbt_dynar_get_as(mc_heap_comparison_ignore, cursor, mc_heap_ignore_region_t);
482     if(region->address == address)
483       return region->size;
484     if(region->address < address)
485       start = cursor + 1;
486     if(region->address > address)
487       end = cursor - 1;   
488   }
489
490   return 0;
491 }
492
493
494 int compare_area(void *area1, void* area2, xbt_dynar_t previous, xbt_dynar_t equals){
495
496   size_t i = 0, pointer_align = 0, ignore1 = 0, ignore2 = 0;
497   void *address_pointed1, *address_pointed2;
498   int res_compare;
499   size_t block1, frag1, block2, frag2, size;
500   int check_ignore = 0;
501
502   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
503   void *area1_to_compare, *area2_to_compare;
504
505   int match_pairs = 0;
506
507   if(previous == NULL){
508     previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
509     match_pairs = 1;
510   }
511
512   block1 = ((char*)area1 - (char*)((xbt_mheap_t)s_heap)->heapbase) / BLOCKSIZE + 1;
513   block2 = ((char*)area2 - (char*)((xbt_mheap_t)s_heap)->heapbase) / BLOCKSIZE + 1;
514
515   if(((char *)area1 < (char*)((xbt_mheap_t)s_heap)->heapbase)  || (block1 > heapsize1) || (block1 < 1) || ((char *)area2 < (char*)((xbt_mheap_t)s_heap)->heapbase) || (block2 > heapsize2) || (block2 < 1))
516     return 1;
517
518   addr_block1 = ((void*) (((ADDR2UINT(block1)) - 1) * BLOCKSIZE + (char*)heapbase1));
519   addr_block2 = ((void*) (((ADDR2UINT(block2)) - 1) * BLOCKSIZE + (char*)heapbase2));
520   
521   if(heapinfo1[block1].type == heapinfo2[block2].type){
522     
523     if(heapinfo1[block1].type == -1){
524       return 0;
525     }else if(heapinfo1[block1].type == 0){
526       if(heapinfo1[block1].busy_block.size != heapinfo2[block2].busy_block.size)
527         return 1;
528       if(heapinfo1[block1].busy_block.busy_size != heapinfo2[block2].busy_block.busy_size)
529         return 1;
530       if(!add_heap_area_pair(previous, block1, -1, block2, -1))
531         return 0;
532
533       size = heapinfo1[block1].busy_block.busy_size;
534       frag1 = -1;
535       frag2 = -1;
536
537       area1_to_compare = addr_block1;
538       area2_to_compare = addr_block2;
539
540       if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && heapinfo1[block1].busy_block.ignore == 1)
541         check_ignore = 1;
542     }else{
543       frag1 = ((uintptr_t) (ADDR2UINT (area1) % (BLOCKSIZE))) >> heapinfo1[block1].type;
544       frag2 = ((uintptr_t) (ADDR2UINT (area2) % (BLOCKSIZE))) >> heapinfo2[block2].type;
545
546       if(heapinfo1[block1].busy_frag.frag_size[frag1] != heapinfo2[block2].busy_frag.frag_size[frag2])
547         return 1;  
548       if(!add_heap_area_pair(previous, block1, frag1, block2, frag2))
549         return 0;
550
551       addr_frag1 = (void*) ((char *)addr_block1 + (frag1 << heapinfo1[block1].type));
552       addr_frag2 = (void*) ((char *)addr_block2 + (frag2 << heapinfo2[block2].type));
553
554       area1_to_compare = addr_frag1;
555       area2_to_compare = addr_frag2;
556       
557       size = heapinfo1[block1].busy_frag.frag_size[frag1];
558
559       if(size == 0)
560         return 0;
561
562       if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && heapinfo1[block1].busy_frag.ignore[frag1] == 1)
563         check_ignore = 1;
564     }
565   }else if((heapinfo1[block1].type > 0) && (heapinfo2[block2].type > 0)){
566     frag1 = ((uintptr_t) (ADDR2UINT (area1) % (BLOCKSIZE))) >> heapinfo1[block1].type;
567     frag2 = ((uintptr_t) (ADDR2UINT (area2) % (BLOCKSIZE))) >> heapinfo2[block2].type;
568
569     if(heapinfo1[block1].busy_frag.frag_size[frag1] != heapinfo2[block2].busy_frag.frag_size[frag2])
570       return 1;       
571     if(!add_heap_area_pair(previous, block1, frag1, block2, frag2))
572       return 0;
573
574     addr_frag1 = (void*) ((char *)addr_block1 + (frag1 << heapinfo1[block1].type));
575     addr_frag2 = (void*) ((char *)addr_block2 + (frag2 << heapinfo2[block2].type));
576
577     area1_to_compare = addr_frag1;
578     area2_to_compare = addr_frag2;
579       
580     size = heapinfo1[block1].busy_frag.frag_size[frag1];
581
582     if(size == 0)
583       return 0;
584
585     if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && heapinfo1[block1].busy_frag.ignore[frag1] == 1)
586       check_ignore = 1;   
587   }else{
588     return 1;
589   }
590   
591   while(i<size){
592
593     if((ignore_done < xbt_dynar_length(mc_heap_comparison_ignore)) && check_ignore){
594
595       if((ignore1 = heap_comparison_ignore_size((char *)area1 + i)) > 0){
596         if((ignore2 = heap_comparison_ignore_size((char *)area2 + i))  == ignore1){
597           i = i + ignore2;
598           ignore_done++;
599           continue;
600         }
601       }
602     }
603    
604     if(memcmp(((char *)area1_to_compare) + i, ((char *)area2_to_compare) + i, 1) != 0){
605
606       /* Check pointer difference */
607       pointer_align = (i / sizeof(void*)) * sizeof(void*);
608       address_pointed1 = *((void **)((char *)area1_to_compare + pointer_align));
609       address_pointed2 = *((void **)((char *)area2_to_compare + pointer_align));
610
611       res_compare = compare_area(address_pointed1, address_pointed2, previous, equals);
612       
613       if(res_compare == 1)
614         return 1; 
615
616       i = pointer_align + sizeof(void *);
617       
618     }else{
619
620       i++;
621
622     }
623   }
624
625   if(match_pairs)
626     match_equals(previous, equals);
627
628   return 0;
629   
630
631 }
632
633 static void heap_area_pair_free(heap_area_pair_t pair){
634   if (pair){
635     xbt_free(pair);
636     pair = NULL;
637   }
638 }
639
640 static void heap_area_pair_free_voidp(void *d)
641 {
642   heap_area_pair_free((heap_area_pair_t) * (void **) d);
643 }
644
645 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
646
647   if(is_new_heap_area_pair(list, block1, fragment1, block2, fragment2)){
648     heap_area_pair_t pair = NULL;
649     pair = xbt_new0(s_heap_area_pair_t, 1);
650     pair->block1 = block1;
651     pair->fragment1 = fragment1;
652     pair->block2 = block2;
653     pair->fragment2 = fragment2;
654     
655     xbt_dynar_push(list, &pair); 
656
657     return 1;
658   }
659
660   return 0;
661 }
662  
663 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
664   
665   unsigned int cursor = 0;
666   heap_area_pair_t current_pair;
667
668   xbt_dynar_foreach(list, cursor, current_pair){
669     if(current_pair->block1 == block1 && current_pair->block2 == block2 && current_pair->fragment1 == fragment1 && current_pair->fragment2 == fragment2)
670       return 0; 
671   }
672   
673   return 1;
674 }
675
676 void match_equals(xbt_dynar_t list, xbt_dynar_t equals){
677
678   unsigned int cursor = 0;
679   heap_area_pair_t current_pair;
680   heap_area_t previous_area;
681
682   void *real_addr_block1, *real_addr_block2, *real_addr_frag1, *real_addr_frag2;
683
684   xbt_dynar_foreach(list, cursor, current_pair){
685
686     if(current_pair->fragment1 != -1){
687
688       real_addr_block1 = ((void*) (((ADDR2UINT((size_t)current_pair->block1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
689       real_addr_frag1 = (void*) ((char *)real_addr_block1 + (current_pair->fragment1 << heapinfo1[current_pair->block1].type));
690       real_addr_block2 = ((void*) (((ADDR2UINT((size_t)current_pair->block2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
691       real_addr_frag2 = (void*) ((char *)real_addr_block2 + (current_pair->fragment2 << heapinfo2[current_pair->block2].type));
692
693       if(heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] != NULL){    
694         remove_heap_equality(equals, 1, real_addr_frag1);
695         previous_area = heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1];
696         xbt_free(heapinfo2[previous_area->block].busy_frag.equal_to[previous_area->fragment]);
697         heapinfo2[previous_area->block].busy_frag.equal_to[previous_area->fragment] = NULL;
698         xbt_free(previous_area); 
699       }
700       if(heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] != NULL){        
701         remove_heap_equality(equals, 2, real_addr_frag2); 
702         previous_area = heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2];
703         xbt_free(heapinfo1[previous_area->block].busy_frag.equal_to[previous_area->fragment]);
704         heapinfo1[previous_area->block].busy_frag.equal_to[previous_area->fragment] = NULL;
705         xbt_free(previous_area);
706       }
707       
708       if(real_addr_frag1 != real_addr_frag2)
709         add_heap_equality(equals, real_addr_frag1, real_addr_frag2);
710
711       heapinfo1[current_pair->block1].busy_frag.equal_to[current_pair->fragment1] = new_heap_area(current_pair->block2, current_pair->fragment2);
712       heapinfo2[current_pair->block2].busy_frag.equal_to[current_pair->fragment2] = new_heap_area(current_pair->block1, current_pair->fragment1);
713
714     }else{
715
716       real_addr_block1 = ((void*) (((ADDR2UINT((size_t)current_pair->block1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
717       real_addr_block2 = ((void*) (((ADDR2UINT((size_t)current_pair->block2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)s_heap)->heapbase));
718
719       if(heapinfo1[current_pair->block1].busy_block.equal_to != NULL){
720         remove_heap_equality(equals, 1, real_addr_block1);
721         previous_area = heapinfo1[current_pair->block1].busy_block.equal_to;
722         xbt_free(heapinfo2[previous_area->block].busy_block.equal_to);
723         heapinfo2[previous_area->block].busy_block.equal_to = NULL; 
724         xbt_free(previous_area);
725       }
726       if(heapinfo2[current_pair->block2].busy_block.equal_to != NULL){
727         remove_heap_equality(equals, 2, real_addr_block2);
728         previous_area = heapinfo2[current_pair->block2].busy_block.equal_to;
729         xbt_free(heapinfo1[previous_area->block].busy_block.equal_to);
730         heapinfo1[previous_area->block].busy_block.equal_to = NULL;
731         xbt_free(previous_area);
732       }
733       
734       if(real_addr_block1 != real_addr_block2)
735         add_heap_equality(equals, real_addr_block1, real_addr_block2);
736
737       heapinfo1[current_pair->block1].busy_block.equal_to = new_heap_area(current_pair->block2, current_pair->fragment2);
738       heapinfo2[current_pair->block2].busy_block.equal_to = new_heap_area(current_pair->block1, current_pair->fragment1);
739
740     }
741   }
742
743
744 }
745
746 #ifndef max
747 #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
748 #endif
749
750 int mmalloc_linear_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2){
751
752   if(heap1 == NULL && heap1 == NULL){
753     XBT_DEBUG("Malloc descriptors null");
754     return 0;
755   }
756
757   if(heap1->heaplimit != heap2->heaplimit){
758     XBT_DEBUG("Different limit of valid info table indices");
759     return 1;
760   }
761
762   /* Heap information */
763   heaplimit = ((struct mdesc *)heap1)->heaplimit;
764
765   s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
766
767   heapbase1 = (char *)heap1 + BLOCKSIZE;
768   heapbase2 = (char *)heap2 + BLOCKSIZE;
769
770   heapinfo1 = (malloc_info *)((char *)heap1 + ((uintptr_t)((char *)heap1->heapinfo - (char *)s_heap)));
771   heapinfo2 = (malloc_info *)((char *)heap2 + ((uintptr_t)((char *)heap2->heapinfo - (char *)s_heap)));
772
773   heapsize1 = heap1->heapsize;
774   heapsize2 = heap2->heapsize;
775
776   /* Start comparison */
777   size_t i, j, k;
778   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
779
780   int distance = 0;
781
782   /* Check busy blocks*/
783
784   i = 1;
785
786   while(i <= heaplimit){
787
788     addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase1));
789     addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)heapbase2));
790
791     if(heapinfo1[i].type != heapinfo2[i].type){
792   
793       distance += BLOCKSIZE;
794       XBT_DEBUG("Different type of blocks (%zu) : %d - %d -> distance = %d", i, heapinfo1[i].type, heapinfo2[i].type, distance);
795       i++;
796     
797     }else{
798
799       if(heapinfo1[i].type == -1){ /* Free block */
800         i++;
801         continue;
802       }
803
804       if(heapinfo1[i].type == 0){ /* Large block */
805        
806         if(heapinfo1[i].busy_block.size != heapinfo2[i].busy_block.size){
807           distance += BLOCKSIZE * max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
808           i += max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
809           XBT_DEBUG("Different larger of cluster at block %zu : %zu - %zu -> distance = %d", i, heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size, distance);
810           continue;
811         }
812
813         /*if(heapinfo1[i].busy_block.busy_size != heapinfo2[i].busy_block.busy_size){
814           distance += max(heapinfo1[i].busy_block.busy_size, heapinfo2[i].busy_block.busy_size);
815           i += max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
816           XBT_DEBUG("Different size used oin large cluster at block %zu : %zu - %zu -> distance = %d", i, heapinfo1[i].busy_block.busy_size, heapinfo2[i].busy_block.busy_size, distance);
817           continue;
818           }*/
819
820         k = 0;
821
822         //while(k < (heapinfo1[i].busy_block.busy_size)){
823         while(k < heapinfo1[i].busy_block.size * BLOCKSIZE){
824           if(memcmp((char *)addr_block1 + k, (char *)addr_block2 + k, 1) != 0){
825             distance ++;
826           }
827           k++;
828         } 
829
830         i++;
831
832       }else { /* Fragmented block */
833
834         for(j=0; j < (size_t) (BLOCKSIZE >> heapinfo1[i].type); j++){
835
836           addr_frag1 = (void*) ((char *)addr_block1 + (j << heapinfo1[i].type));
837           addr_frag2 = (void*) ((char *)addr_block2 + (j << heapinfo2[i].type));
838
839           if(heapinfo1[i].busy_frag.frag_size[j] == 0 && heapinfo2[i].busy_frag.frag_size[j] == 0){
840             continue;
841           }
842           
843           
844           /*if(heapinfo1[i].busy_frag.frag_size[j] != heapinfo2[i].busy_frag.frag_size[j]){
845             distance += max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j]);
846             XBT_DEBUG("Different size used in fragment %zu in block %zu : %d - %d -> distance = %d", j, i, heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j], distance); 
847             continue;
848             }*/
849    
850           k=0;
851
852           //while(k < max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j])){
853           while(k < (BLOCKSIZE / (BLOCKSIZE >> heapinfo1[i].type))){
854             if(memcmp((char *)addr_frag1 + k, (char *)addr_frag2 + k, 1) != 0){
855               distance ++;
856             }
857             k++;
858           }
859
860         }
861
862         i++;
863
864       }
865       
866     }
867
868   }
869
870   return distance;
871   
872 }
873
874 static char* is_stack(void *address){
875   unsigned int cursor = 0;
876   stack_region_t stack;
877
878   xbt_dynar_foreach(stacks_areas, cursor, stack){
879     if(address == stack->address)
880       return stack->process_name;
881   }
882
883   return NULL;
884 }
885
886 static void add_heap_equality(xbt_dynar_t equals, void *a1, void *a2){
887   
888   if(xbt_dynar_is_empty(equals)){
889
890     heap_equality_t he = xbt_new0(s_heap_equality_t, 1);
891     he->address1 = a1;
892     he->address2 = a2;
893
894     xbt_dynar_insert_at(equals, 0, &he);
895   
896   }else{
897
898     unsigned int cursor = 0;
899     int start = 0;
900     int end = xbt_dynar_length(equals) - 1;
901     heap_equality_t current_equality = NULL;
902
903     while(start <= end){
904       cursor = (start + end) / 2;
905       current_equality = (heap_equality_t)xbt_dynar_get_as(equals, cursor, heap_equality_t);
906       if(current_equality->address1 == a1){
907         if(current_equality->address2 == a2)
908           return;
909         if(current_equality->address2 < a2)
910           start = cursor + 1;
911         if(current_equality->address2 > a2)
912           end = cursor - 1;
913       }
914       if(current_equality->address1 < a1)
915         start = cursor + 1;
916       if(current_equality->address1 > a1)
917         end = cursor - 1; 
918     }
919
920     heap_equality_t he = xbt_new0(s_heap_equality_t, 1);
921     he->address1 = a1;
922     he->address2 = a2;
923   
924     if(current_equality->address1 < a1)
925       xbt_dynar_insert_at(equals, cursor + 1 , &he);
926     else
927        xbt_dynar_insert_at(equals, cursor, &he); 
928
929   }
930
931 }
932
933 static void remove_heap_equality(xbt_dynar_t equals, int address, void *a){
934   
935   unsigned int cursor = 0;
936   heap_equality_t current_equality;
937   int found = 0;
938
939   if(address == 1){
940
941     int start = 0;
942     int end = xbt_dynar_length(equals) - 1;
943
944
945     while(start <= end && found == 0){
946       cursor = (start + end) / 2;
947       current_equality = (heap_equality_t)xbt_dynar_get_as(equals, cursor, heap_equality_t);
948       if(current_equality->address1 == a)
949         found = 1;
950       if(current_equality->address1 < a)
951         start = cursor + 1;
952       if(current_equality->address1 > a)
953         end = cursor - 1; 
954     }
955
956     if(found == 1)
957       xbt_dynar_remove_at(equals, cursor, NULL);
958   
959   }else{
960
961     xbt_dynar_foreach(equals, cursor, current_equality){
962       if(current_equality->address2 == a){
963         found = 1;
964         break;
965       }
966     }
967
968     if(found == 1)
969       xbt_dynar_remove_at(equals, cursor, NULL);
970
971   }
972   
973 }
974
975 int is_free_area(void *area, xbt_mheap_t heap){
976
977   void *sheap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - getpagesize();
978   malloc_info *heapinfo = (malloc_info *)((char *)heap + ((uintptr_t)((char *)heap->heapinfo - (char *)sheap)));
979   size_t heapsize = heap->heapsize;
980
981   /* Get block number */ 
982   size_t block = ((char*)area - (char*)((xbt_mheap_t)sheap)->heapbase) / BLOCKSIZE + 1;
983   size_t fragment;
984
985   /* Check if valid block number */
986   if((char *)area < (char*)((xbt_mheap_t)sheap)->heapbase || block > heapsize || block < 1)
987     return 0;
988
989   if(heapinfo[block].type < 0)
990     return 1;
991
992   if(heapinfo[block].type == 0)
993     return 0;
994
995   if(heapinfo[block].type > 0){
996     fragment = ((uintptr_t) (ADDR2UINT(area) % (BLOCKSIZE))) >> heapinfo[block].type;
997     if(heapinfo[block].busy_frag.frag_size[fragment] == 0)
998       return 1;  
999   }
1000
1001   return 0;
1002   
1003
1004
1005 }