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 }