Logo AND Algorithmique Numérique Distribuée

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