Logo AND Algorithmique Numérique Distribuée

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