src/xbt/mmalloc/mm_diff.c

   1 /* mm_diff - Memory snapshooting and comparison                             */
   2
   3 /* Copyright (c) 2008-2014. The SimGrid Team.
   4  * All rights reserved.                                                     */
   5
   6 /* This program is free software; you can redistribute it and/or modify it
   7  * under the terms of the license (GNU LGPL) which comes with this package. */
   8
   9 #include "xbt/ex_interface.h" /* internals of backtrace setup */
  10 #include "xbt/str.h"
  11 #include "mc/mc.h"
  12 #include "xbt/mmalloc.h"
  13 #include "mc/datatypes.h"
  14 #include "mc/mc_private.h"
  15
  16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mm_diff, xbt,
  17                                 "Logging specific to mm_diff in mmalloc");
  18
  19 xbt_dynar_t mc_heap_comparison_ignore;
  20 xbt_dynar_t stacks_areas;
  21 void *maestro_stack_start, *maestro_stack_end;
  22
  23
  24 /********************************* Backtrace ***********************************/
  25 /******************************************************************************/
  26
  27 static void mmalloc_backtrace_block_display(void* heapinfo, int block){
  28
  29   /* xbt_ex_t e; */
  30
  31   /* if (((malloc_info *)heapinfo)[block].busy_block.bt_size == 0) { */
  32   /*   fprintf(stderr, "No backtrace available for that block, sorry.\n"); */
  33   /*   return; */
  34   /* } */
  35
  36   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_block.bt),sizeof(void*)*XBT_BACKTRACE_SIZE); */
  37   /* e.used = ((malloc_info *)heapinfo)[block].busy_block.bt_size; */
  38
  39   /* xbt_ex_setup_backtrace(&e); */
  40   /* if (e.used == 0) { */
  41   /*   fprintf(stderr, "(backtrace not set)\n"); */
  42   /* } else if (e.bt_strings == NULL) { */
  43   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
  44   /* } else { */
  45   /*   int i; */
  46
  47   /*   fprintf(stderr, "Backtrace of where the block %d was malloced (%d frames):\n", block ,e.used); */
  48   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
  49   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
  50   /*   } */
  51   /* } */
  52 }
  53
  54 static void mmalloc_backtrace_fragment_display(void* heapinfo, int block, int frag){
  55
  56   /* xbt_ex_t e; */
  57
  58   /* memcpy(&e.bt,&(((malloc_info *)heapinfo)[block].busy_frag.bt[frag]),sizeof(void*)*XBT_BACKTRACE_SIZE); */
  59   /* e.used = XBT_BACKTRACE_SIZE; */
  60
  61   /* xbt_ex_setup_backtrace(&e); */
  62   /* if (e.used == 0) { */
  63   /*   fprintf(stderr, "(backtrace not set)\n"); */
  64   /* } else if (e.bt_strings == NULL) { */
  65   /*   fprintf(stderr, "(backtrace not ready to be computed. %s)\n",xbt_binary_name?"Dunno why":"xbt_binary_name not setup yet"); */
  66   /* } else { */
  67   /*   int i; */
  68
  69   /*   fprintf(stderr, "Backtrace of where the fragment %d in block %d was malloced (%d frames):\n", frag, block ,e.used); */
  70   /*   for (i = 0; i < e.used; i++)       /\* no need to display "xbt_backtrace_display" *\/{ */
  71   /*     fprintf(stderr, "%d ---> %s\n",i, e.bt_strings[i] + 4); */
  72   /*   } */
  73   /* } */
  74
  75 }
  76
  77 static void mmalloc_backtrace_display(void *addr){
  78
  79   /* size_t block, frag_nb; */
  80   /* int type; */
  81
  82   /* xbt_mheap_t heap = __mmalloc_current_heap ?: (xbt_mheap_t) mmalloc_preinit(); */
  83
  84   /* block = (((char*) (addr) - (char*) heap -> heapbase) / BLOCKSIZE + 1); */
  85
  86   /* type = heap->heapinfo[block].type; */
  87
  88   /* switch(type){ */
  89   /* case -1 : /\* Free block *\/ */
  90   /*   fprintf(stderr, "Asked to display the backtrace of a block that is free. I'm puzzled\n"); */
  91   /*   xbt_abort(); */
  92   /*   break;  */
  93   /* case 0: /\* Large block *\/ */
  94   /*   mmalloc_backtrace_block_display(heap->heapinfo, block); */
  95   /*   break; */
  96   /* default: /\* Fragmented block *\/ */
  97   /*   frag_nb = RESIDUAL(addr, BLOCKSIZE) >> type; */
  98   /*   if(heap->heapinfo[block].busy_frag.frag_size[frag_nb] == -1){ */
  99   /*     fprintf(stderr , "Asked to display the backtrace of a fragment that is free. I'm puzzled\n"); */
 100   /*     xbt_abort(); */
 101   /*   } */
 102   /*   mmalloc_backtrace_fragment_display(heap->heapinfo, block, frag_nb); */
 103   /*   break; */
 104   /* } */
 105 }
 106
 107
 108 static int compare_backtrace(int b1, int f1, int b2, int f2){
 109   /*int i = 0;
 110   if(f1 != -1){
 111     for(i=0; i< XBT_BACKTRACE_SIZE; i++){
 112       if(heapinfo1[b1].busy_frag.bt[f1][i] != heapinfo2[b2].busy_frag.bt[f2][i]){
 113         //mmalloc_backtrace_fragment_display((void*)heapinfo1, b1, f1);
 114         //mmalloc_backtrace_fragment_display((void*)heapinfo2, b2, f2);
 115         return 1;
 116       }
 117     }
 118   }else{
 119     for(i=0; i< heapinfo1[b1].busy_block.bt_size; i++){
 120       if(heapinfo1[b1].busy_block.bt[i] != heapinfo2[b2].busy_block.bt[i]){
 121         //mmalloc_backtrace_block_display((void*)heapinfo1, b1);
 122         //mmalloc_backtrace_block_display((void*)heapinfo2, b2);
 123         return 1;
 124       }
 125     }
 126     }*/
 127   return 0;
 128 }
 129
 130
 131 /*********************************** Heap comparison ***********************************/
 132 /***************************************************************************************/
 133
 134 typedef char* type_name;
 135
 136 struct s_mm_diff {
 137   void *s_heap, *heapbase1, *heapbase2;
 138   malloc_info *heapinfo1, *heapinfo2;
 139   size_t heaplimit;
 140   // Number of blocks in the heaps:
 141   size_t heapsize1, heapsize2;
 142   xbt_dynar_t to_ignore1, to_ignore2;
 143   s_heap_area_t *equals_to1, *equals_to2;
 144   dw_type_t *types1, *types2;
 145   size_t available;
 146 };
 147
 148 #define equals_to1_(i,j) equals_to1[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 149 #define equals_to2_(i,j) equals_to2[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 150 #define types1_(i,j) types1[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 151 #define types2_(i,j) types2[ MAX_FRAGMENT_PER_BLOCK*(i) + (j)]
 152
 153 __thread struct s_mm_diff* mm_diff_info = NULL;
 154
 155 /*********************************** Free functions ************************************/
 156
 157 static void heap_area_pair_free(heap_area_pair_t pair){
 158   xbt_free(pair);
 159   pair = NULL;
 160 }
 161
 162 static void heap_area_pair_free_voidp(void *d){
 163   heap_area_pair_free((heap_area_pair_t) * (void **) d);
 164 }
 165
 166 static void heap_area_free(heap_area_t area){
 167   xbt_free(area);
 168   area = NULL;
 169 }
 170
 171 /************************************************************************************/
 172
 173 static s_heap_area_t make_heap_area(int block, int fragment){
 174   s_heap_area_t area;
 175   area.valid = 1;
 176   area.block = block;
 177   area.fragment = fragment;
 178   return area;
 179 }
 180
 181
 182 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
 183
 184   unsigned int cursor = 0;
 185   heap_area_pair_t current_pair;
 186
 187   xbt_dynar_foreach(list, cursor, current_pair){
 188     if(current_pair->block1 == block1 && current_pair->block2 == block2 && current_pair->fragment1 == fragment1 && current_pair->fragment2 == fragment2)
 189       return 0;
 190   }
 191
 192   return 1;
 193 }
 194
 195 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1, int block2, int fragment2){
 196
 197   if(is_new_heap_area_pair(list, block1, fragment1, block2, fragment2)){
 198     heap_area_pair_t pair = NULL;
 199     pair = xbt_new0(s_heap_area_pair_t, 1);
 200     pair->block1 = block1;
 201     pair->fragment1 = fragment1;
 202     pair->block2 = block2;
 203     pair->fragment2 = fragment2;
 204
 205     xbt_dynar_push(list, &pair);
 206
 207     return 1;
 208   }
 209
 210   return 0;
 211 }
 212
 213 static ssize_t heap_comparison_ignore_size(xbt_dynar_t ignore_list, void *address){
 214
 215   unsigned int cursor = 0;
 216   int start = 0;
 217   int end = xbt_dynar_length(ignore_list) - 1;
 218   mc_heap_ignore_region_t region;
 219
 220   while(start <= end){
 221     cursor = (start + end) / 2;
 222     region = (mc_heap_ignore_region_t)xbt_dynar_get_as(ignore_list, cursor, mc_heap_ignore_region_t);
 223     if(region->address == address)
 224       return region->size;
 225     if(region->address < address)
 226       start = cursor + 1;
 227     if(region->address > address)
 228       end = cursor - 1;
 229   }
 230
 231   return -1;
 232 }
 233
 234 static int is_stack(void *address){
 235   unsigned int cursor = 0;
 236   stack_region_t stack;
 237
 238   xbt_dynar_foreach(stacks_areas, cursor, stack){
 239     if(address == stack->address)
 240       return 1;
 241   }
 242
 243   return 0;
 244 }
 245
 246 static int is_block_stack(int block){
 247   unsigned int cursor = 0;
 248   stack_region_t stack;
 249
 250   xbt_dynar_foreach(stacks_areas, cursor, stack){
 251     if(block == stack->block)
 252       return 1;
 253   }
 254
 255   return 0;
 256 }
 257
 258 static void match_equals(struct s_mm_diff *state, xbt_dynar_t list){
 259
 260   unsigned int cursor = 0;
 261   heap_area_pair_t current_pair;
 262
 263   xbt_dynar_foreach(list, cursor, current_pair){
 264
 265     if(current_pair->fragment1 != -1){
 266
 267       state->equals_to1_(current_pair->block1,current_pair->fragment1) = make_heap_area(current_pair->block2, current_pair->fragment2);
 268       state->equals_to2_(current_pair->block2,current_pair->fragment2) = make_heap_area(current_pair->block1, current_pair->fragment1);
 269
 270     }else{
 271
 272       state->equals_to1_(current_pair->block1,0) = make_heap_area(current_pair->block2, current_pair->fragment2);
 273       state->equals_to2_(current_pair->block2,0) = make_heap_area(current_pair->block1, current_pair->fragment1);
 274
 275     }
 276
 277   }
 278 }
 279
 280 /** Check whether two blocks are known to be matching
 281  *
 282  *  @param state  State used
 283  *  @param b1     Block of state 1
 284  *  @param b2     Block of state 2
 285  *  @return       if the blocks are known to be matching
 286  */
 287 static int equal_blocks(struct s_mm_diff *state, int b1, int b2){
 288
 289   if(state->equals_to1_(b1,0).block == b2 && state->equals_to2_(b2,0).block == b1)
 290     return 1;
 291
 292   return 0;
 293 }
 294
 295 /** Check whether two fragments are known to be matching
 296  *
 297  *  @param state  State used
 298  *  @param b1     Block of state 1
 299  *  @param f1     Fragment of state 1
 300  *  @param b2     Block of state 2
 301  *  @param f2     Fragment of state 2
 302  *  @return       if the fragments are known to be matching
 303  */
 304 static int equal_fragments(struct s_mm_diff *state, int b1, int f1, int b2, int f2){
 305
 306   if(state->equals_to1_(b1,f1).block == b2
 307     && state->equals_to1_(b1,f1).fragment == f2
 308     && state->equals_to2_(b2,f2).block == b1
 309     && state->equals_to2_(b2,f2).fragment == f1)
 310     return 1;
 311
 312   return 0;
 313 }
 314
 315 int init_heap_information(xbt_mheap_t heap1, xbt_mheap_t heap2, xbt_dynar_t i1, xbt_dynar_t i2){
 316   if(mm_diff_info==NULL) {
 317     mm_diff_info = xbt_new0(struct s_mm_diff, 1);
 318     mm_diff_info->equals_to1 = NULL;
 319     mm_diff_info->equals_to2 = NULL;
 320     mm_diff_info->types1 = NULL;
 321     mm_diff_info->types2 = NULL;
 322   }
 323   struct s_mm_diff *state = mm_diff_info;
 324
 325   if((((struct mdesc *)heap1)->heaplimit != ((struct mdesc *)heap2)->heaplimit)
 326     || ((((struct mdesc *)heap1)->heapsize != ((struct mdesc *)heap2)->heapsize) ))
 327     return -1;
 328
 329   state->heaplimit = ((struct mdesc *)heap1)->heaplimit;
 330
 331   state->s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - xbt_pagesize;
 332
 333   state->heapbase1 = (char *)heap1 + BLOCKSIZE;
 334   state->heapbase2 = (char *)heap2 + BLOCKSIZE;
 335
 336   state->heapinfo1 = (malloc_info *)((char *)heap1 + ((uintptr_t)((char *)((struct mdesc *)heap1)->heapinfo - (char *)state->s_heap)));
 337   state->heapinfo2 = (malloc_info *)((char *)heap2 + ((uintptr_t)((char *)((struct mdesc *)heap2)->heapinfo - (char *)state->s_heap)));
 338
 339   state->heapsize1 = heap1->heapsize;
 340   state->heapsize2 = heap2->heapsize;
 341
 342   state->to_ignore1 = i1;
 343   state-> to_ignore2 = i2;
 344
 345   if(state->heaplimit > state->available) {
 346     state->equals_to1 = realloc(state->equals_to1, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(s_heap_area_t));
 347     state->types1 = realloc(state->types1, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(type_name *));
 348     state->equals_to2 = realloc(state->equals_to2, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(s_heap_area_t));
 349     state->types2 = realloc(state->types2, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(type_name *));
 350     state->available = state->heaplimit;
 351   }
 352
 353   memset(state->equals_to1, 0, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(s_heap_area_t));
 354   memset(state->equals_to2, 0, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(s_heap_area_t));
 355   memset(state->types1, 0, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(type_name *));
 356   memset(state->types2, 0, state->heaplimit * MAX_FRAGMENT_PER_BLOCK * sizeof(type_name *));
 357
 358   if(MC_is_active()){
 359     MC_ignore_global_variable("mm_diff_info");
 360   }
 361
 362   return 0;
 363
 364 }
 365
 366 void reset_heap_information(){
 367
 368 }
 369
 370 int mmalloc_compare_heap(mc_snapshot_t snapshot1, mc_snapshot_t snapshot2, xbt_mheap_t heap1, xbt_mheap_t heap2){
 371
 372   struct s_mm_diff *state = mm_diff_info;
 373
 374   if(heap1 == NULL && heap2 == NULL){
 375     XBT_DEBUG("Malloc descriptors null");
 376     return 0;
 377   }
 378
 379   /* Start comparison */
 380   size_t i1, i2, j1, j2, k;
 381   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
 382   int nb_diff1 = 0, nb_diff2 = 0;
 383
 384   xbt_dynar_t previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
 385
 386   int equal, res_compare = 0;
 387
 388   /* Check busy blocks*/
 389
 390   i1 = 1;
 391
 392   while(i1 <= state->heaplimit){
 393
 394     if(state->heapinfo1[i1].type == -1){ /* Free block */
 395       i1++;
 396       continue;
 397     }
 398
 399     addr_block1 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)state->s_heap)->heapbase));
 400
 401     if(state->heapinfo1[i1].type == 0){  /* Large block */
 402
 403       if(is_stack(addr_block1)){
 404         for(k=0; k < state->heapinfo1[i1].busy_block.size; k++)
 405           state->equals_to1_(i1+k,0) = make_heap_area(i1, -1);
 406         for(k=0; k < state->heapinfo2[i1].busy_block.size; k++)
 407           state->equals_to2_(i1+k,0) = make_heap_area(i1, -1);
 408         i1 += state->heapinfo1[i1].busy_block.size;
 409         continue;
 410       }
 411
 412       if(state->equals_to1_(i1,0).valid){
 413         i1++;
 414         continue;
 415       }
 416
 417       i2 = 1;
 418       equal = 0;
 419       res_compare = 0;
 420
 421       /* Try first to associate to same block in the other heap */
 422       if(state->heapinfo2[i1].type == state->heapinfo1[i1].type){
 423
 424         if(state->equals_to2_(i1,0).valid == 0){
 425
 426           addr_block2 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)state->s_heap)->heapbase));
 427
 428           res_compare = compare_heap_area(addr_block1, addr_block2, snapshot1, snapshot2, NULL, NULL, 0);
 429
 430           if(res_compare != 1){
 431             for(k=1; k < state->heapinfo2[i1].busy_block.size; k++)
 432               state->equals_to2_(i1+k,0) = make_heap_area(i1, -1);
 433             for(k=1; k < state->heapinfo1[i1].busy_block.size; k++)
 434               state->equals_to1_(i1+k,0) = make_heap_area(i1, -1);
 435             equal = 1;
 436             i1 += state->heapinfo1[i1].busy_block.size;
 437           }
 438
 439           xbt_dynar_reset(previous);
 440
 441         }
 442
 443       }
 444
 445       while(i2 <= state->heaplimit && !equal){
 446
 447         addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)state->s_heap)->heapbase));
 448
 449         if(i2 == i1){
 450           i2++;
 451           continue;
 452         }
 453
 454         if(state->heapinfo2[i2].type != 0){
 455           i2++;
 456           continue;
 457         }
 458
 459         if(state->equals_to2_(i2,0).valid){
 460           i2++;
 461           continue;
 462         }
 463
 464         res_compare = compare_heap_area(addr_block1, addr_block2, snapshot1, snapshot2, NULL, NULL, 0);
 465
 466         if(res_compare != 1 ){
 467           for(k=1; k < state->heapinfo2[i2].busy_block.size; k++)
 468             state->equals_to2_(i2+k,0) = make_heap_area(i1, -1);
 469           for(k=1; k < state->heapinfo1[i1].busy_block.size; k++)
 470             state->equals_to1_(i1+k,0) = make_heap_area(i2, -1);
 471           equal = 1;
 472           i1 += state->heapinfo1[i1].busy_block.size;
 473         }
 474
 475         xbt_dynar_reset(previous);
 476
 477         i2++;
 478
 479       }
 480
 481       if(!equal){
 482         XBT_DEBUG("Block %zu not found (size_used = %zu, addr = %p)", i1, state->heapinfo1[i1].busy_block.busy_size, addr_block1);
 483         i1 = state->heaplimit + 1;
 484         nb_diff1++;
 485           //i1++;
 486       }
 487
 488     }else{ /* Fragmented block */
 489
 490       for(j1=0; j1 < (size_t) (BLOCKSIZE >> state->heapinfo1[i1].type); j1++){
 491
 492         if(state->heapinfo1[i1].busy_frag.frag_size[j1] == -1) /* Free fragment */
 493           continue;
 494
 495         if(state->equals_to1_(i1,j1).valid)
 496           continue;
 497
 498         addr_frag1 = (void*) ((char *)addr_block1 + (j1 << state->heapinfo1[i1].type));
 499
 500         i2 = 1;
 501         equal = 0;
 502
 503         /* Try first to associate to same fragment in the other heap */
 504         if(state->heapinfo2[i1].type == state->heapinfo1[i1].type){
 505
 506           if(state->equals_to2_(i1,j1).valid == 0){
 507
 508             addr_block2 = ((void*) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)state->s_heap)->heapbase));
 509             addr_frag2 = (void*) ((char *)addr_block2 + (j1 << ((xbt_mheap_t)state->s_heap)->heapinfo[i1].type));
 510
 511             res_compare = compare_heap_area(addr_frag1, addr_frag2, snapshot1, snapshot2, NULL, NULL, 0);
 512
 513             if(res_compare !=  1)
 514               equal = 1;
 515
 516             xbt_dynar_reset(previous);
 517
 518           }
 519
 520         }
 521
 522         while(i2 <= state->heaplimit && !equal){
 523
 524           if(state->heapinfo2[i2].type <= 0){
 525             i2++;
 526             continue;
 527           }
 528
 529           for(j2=0; j2 < (size_t) (BLOCKSIZE >> state->heapinfo2[i2].type); j2++){
 530
 531             if(i2 == i1 && j2 == j1)
 532               continue;
 533
 534             if(state->equals_to2_(i2,j2).valid)
 535               continue;
 536
 537             addr_block2 = ((void*) (((ADDR2UINT(i2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)state->s_heap)->heapbase));
 538             addr_frag2 = (void*) ((char *)addr_block2 + (j2 <<((xbt_mheap_t)state->s_heap)->heapinfo[i2].type));
 539
 540             res_compare = compare_heap_area(addr_frag1, addr_frag2, snapshot2, snapshot2, NULL, NULL, 0);
 541
 542             if(res_compare != 1){
 543               equal = 1;
 544               xbt_dynar_reset(previous);
 545               break;
 546             }
 547
 548             xbt_dynar_reset(previous);
 549
 550           }
 551
 552           i2++;
 553
 554         }
 555
 556         if(!equal){
 557           XBT_DEBUG("Block %zu, fragment %zu not found (size_used = %zd, address = %p)\n", i1, j1, state->heapinfo1[i1].busy_frag.frag_size[j1], addr_frag1);
 558           i2 = state->heaplimit + 1;
 559           i1 = state->heaplimit + 1;
 560           nb_diff1++;
 561           break;
 562         }
 563
 564       }
 565
 566       i1++;
 567
 568     }
 569
 570   }
 571
 572   /* All blocks/fragments are equal to another block/fragment ? */
 573   size_t i = 1, j = 0;
 574   void *real_addr_frag1 = NULL, *real_addr_block1 = NULL, *real_addr_block2 = NULL, *real_addr_frag2 = NULL;
 575
 576   while(i<=state->heaplimit){
 577     if(state->heapinfo1[i].type == 0){
 578       if(i1 == state->heaplimit){
 579         if(state->heapinfo1[i].busy_block.busy_size > 0){
 580           if(state->equals_to1_(i,0).valid == 0){
 581             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 582               addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)state->heapbase1));
 583               XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block1, state->heapinfo1[i].busy_block.busy_size);
 584               //mmalloc_backtrace_block_display((void*)heapinfo1, i);
 585             }
 586             nb_diff1++;
 587           }
 588         }
 589       }
 590     }
 591     if(state->heapinfo1[i].type > 0){
 592       addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)state->heapbase1));
 593       real_addr_block1 =  ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)((struct mdesc *)state->s_heap)->heapbase));
 594       for(j=0; j < (size_t) (BLOCKSIZE >> state->heapinfo1[i].type); j++){
 595         if(i1== state->heaplimit){
 596           if(state->heapinfo1[i].busy_frag.frag_size[j] > 0){
 597             if(state->equals_to1_(i,j).valid == 0){
 598               if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 599                 addr_frag1 = (void*) ((char *)addr_block1 + (j << state->heapinfo1[i].type));
 600                 real_addr_frag1 = (void*) ((char *)real_addr_block1 + (j << ((struct mdesc *)state->s_heap)->heapinfo[i].type));
 601                 XBT_DEBUG("Block %zu, Fragment %zu (%p - %p) not found (size used = %zd)", i, j, addr_frag1, real_addr_frag1, state->heapinfo1[i].busy_frag.frag_size[j]);
 602                 //mmalloc_backtrace_fragment_display((void*)heapinfo1, i, j);
 603               }
 604               nb_diff1++;
 605             }
 606           }
 607         }
 608       }
 609     }
 610     i++;
 611   }
 612
 613   if(i1 == state->heaplimit)
 614     XBT_DEBUG("Number of blocks/fragments not found in heap1 : %d", nb_diff1);
 615
 616   i = 1;
 617
 618   while(i<=state->heaplimit){
 619     if(state->heapinfo2[i].type == 0){
 620       if(i1 == state->heaplimit){
 621         if(state->heapinfo2[i].busy_block.busy_size > 0){
 622           if(state->equals_to2_(i,0).valid == 0){
 623             if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 624               addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)state->heapbase2));
 625               XBT_DEBUG("Block %zu (%p) not found (size used = %zu)", i, addr_block2, state->heapinfo2[i].busy_block.busy_size);
 626               //mmalloc_backtrace_block_display((void*)heapinfo2, i);
 627             }
 628             nb_diff2++;
 629           }
 630         }
 631       }
 632     }
 633     if(state->heapinfo2[i].type > 0){
 634       addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)state->heapbase2));
 635       real_addr_block2 =  ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)((struct mdesc *)state->s_heap)->heapbase));
 636       for(j=0; j < (size_t) (BLOCKSIZE >> state->heapinfo2[i].type); j++){
 637         if(i1 == state->heaplimit){
 638           if(state->heapinfo2[i].busy_frag.frag_size[j] > 0){
 639             if(state->equals_to2_(i,j).valid == 0){
 640               if(XBT_LOG_ISENABLED(mm_diff, xbt_log_priority_debug)){
 641                 addr_frag2 = (void*) ((char *)addr_block2 + (j << state->heapinfo2[i].type));
 642                 real_addr_frag2 = (void*) ((char *)real_addr_block2 + (j << ((struct mdesc *)state->s_heap)->heapinfo[i].type));
 643                 XBT_DEBUG( "Block %zu, Fragment %zu (%p - %p) not found (size used = %zd)", i, j, addr_frag2, real_addr_frag2, state->heapinfo2[i].busy_frag.frag_size[j]);
 644                 //mmalloc_backtrace_fragment_display((void*)heapinfo2, i, j);
 645               }
 646               nb_diff2++;
 647             }
 648           }
 649         }
 650       }
 651     }
 652     i++;
 653   }
 654
 655   if(i1 == state->heaplimit)
 656     XBT_DEBUG("Number of blocks/fragments not found in heap2 : %d", nb_diff2);
 657
 658   xbt_dynar_free(&previous);
 659   real_addr_frag1 = NULL, real_addr_block1 = NULL, real_addr_block2 = NULL, real_addr_frag2 = NULL;
 660
 661   return ((nb_diff1 > 0) || (nb_diff2 > 0));
 662 }
 663
 664 /**
 665  *
 666  * @param state
 667  * @param real_area1     Process address for state 1
 668  * @param real_area2     Process address for state 2
 669  * @param area1          Snapshot address for state 1
 670  * @param area2          Snapshot address for state 2
 671  * @param snapshot1      Snapshot of state 1
 672  * @param snapshot2      Snapshot of state 2
 673  * @param previous
 674  * @param size
 675  * @param check_ignore
 676  */
 677 static int compare_heap_area_without_type(struct s_mm_diff *state, void *real_area1, void *real_area2, void *area1, void *area2, mc_snapshot_t snapshot1, mc_snapshot_t snapshot2, xbt_dynar_t previous, int size, int check_ignore){
 678
 679   int i = 0;
 680   void *addr_pointed1, *addr_pointed2;
 681   int pointer_align, res_compare;
 682   ssize_t ignore1, ignore2;
 683
 684   while(i<size){
 685
 686     if(check_ignore > 0){
 687       if((ignore1 = heap_comparison_ignore_size(state->to_ignore1, (char *)real_area1 + i)) != -1){
 688         if((ignore2 = heap_comparison_ignore_size(state->to_ignore2, (char *)real_area2 + i))  == ignore1){
 689           if(ignore1 == 0){
 690             check_ignore--;
 691             return 0;
 692           }else{
 693             i = i + ignore2;
 694             check_ignore--;
 695             continue;
 696           }
 697         }
 698       }
 699     }
 700
 701     if(memcmp(((char *)area1) + i, ((char *)area2) + i, 1) != 0){
 702
 703       pointer_align = (i / sizeof(void*)) * sizeof(void*);
 704       addr_pointed1 = *((void **)((char *)area1 + pointer_align));
 705       addr_pointed2 = *((void **)((char *)area2 + pointer_align));
 706
 707       if(addr_pointed1 > maestro_stack_start && addr_pointed1 < maestro_stack_end && addr_pointed2 > maestro_stack_start && addr_pointed2 < maestro_stack_end){
 708         i = pointer_align + sizeof(void *);
 709         continue;
 710       }else if((addr_pointed1 > state->s_heap) && ((char *)addr_pointed1 < (char *)state->s_heap + STD_HEAP_SIZE)
 711                && (addr_pointed2 > state->s_heap) && ((char *)addr_pointed2 < (char *)state->s_heap + STD_HEAP_SIZE)){
 712         res_compare = compare_heap_area(addr_pointed1, addr_pointed2, snapshot1, snapshot2, previous, NULL, 0);
 713         if(res_compare == 1){
 714           return res_compare;
 715         }
 716         i = pointer_align + sizeof(void *);
 717         continue;
 718       }else{
 719         return 1;
 720       }
 721
 722     }
 723
 724     i++;
 725
 726   }
 727
 728   return 0;
 729
 730 }
 731
 732 /**
 733  *
 734  * @param state
 735  * @param real_area1     Process address for state 1
 736  * @param real_area2     Process address for state 2
 737  * @param area1          Snapshot address for state 1
 738  * @param area2          Snapshot address for state 2
 739  * @param snapshot1      Snapshot of state 1
 740  * @param snapshot2      Snapshot of state 2
 741  * @param previous
 742  * @param type_id
 743  * @param area_size      either a byte_size or an elements_count (?)
 744  * @param check_ignore
 745  * @param pointer_level
 746  * @return               0 (same), 1 (different), -1 (unknown)
 747  */
 748 static int compare_heap_area_with_type(struct s_mm_diff *state, void *real_area1, void *real_area2, void *area1, void *area2,
 749                                        mc_snapshot_t snapshot1, mc_snapshot_t snapshot2,
 750                                        xbt_dynar_t previous, dw_type_t type,
 751                                        int area_size, int check_ignore, int pointer_level){
 752
 753   if(is_stack(real_area1) && is_stack(real_area2))
 754     return 0;
 755
 756   ssize_t ignore1, ignore2;
 757
 758   if((check_ignore > 0) && ((ignore1 = heap_comparison_ignore_size(state->to_ignore1, real_area1)) > 0) && ((ignore2 = heap_comparison_ignore_size(state->to_ignore2, real_area2))  == ignore1)){
 759     return 0;
 760   }
 761
 762   dw_type_t subtype, subsubtype;
 763   int res, elm_size, i;
 764   unsigned int cursor = 0;
 765   dw_type_t member;
 766   void *addr_pointed1, *addr_pointed2;;
 767
 768   switch(type->type){
 769   case DW_TAG_unspecified_type:
 770     return 1;
 771
 772   case DW_TAG_base_type:
 773     if(type->name!=NULL && strcmp(type->name, "char") == 0){ /* String, hence random (arbitrary ?) size */
 774       if(real_area1 == real_area2)
 775         return -1;
 776       else
 777         return (memcmp(area1, area2, area_size) != 0);
 778     }else{
 779       if(area_size != -1 && type->byte_size != area_size)
 780         return -1;
 781       else{
 782         return  (memcmp(area1, area2, type->byte_size) != 0);
 783       }
 784     }
 785     break;
 786   case DW_TAG_enumeration_type:
 787     if(area_size != -1 && type->byte_size != area_size)
 788       return -1;
 789     else
 790       return (memcmp(area1, area2, type->byte_size) != 0);
 791     break;
 792   case DW_TAG_typedef:
 793   case DW_TAG_const_type:
 794   case DW_TAG_volatile_type:
 795     return compare_heap_area_with_type(state, real_area1, real_area2, area1, area2, snapshot1, snapshot2, previous, type->subtype, area_size, check_ignore, pointer_level);
 796     break;
 797   case DW_TAG_array_type:
 798     subtype = type->subtype;
 799     switch(subtype->type){
 800     case DW_TAG_unspecified_type:
 801       return 1;
 802
 803     case DW_TAG_base_type:
 804     case DW_TAG_enumeration_type:
 805     case DW_TAG_pointer_type:
 806     case DW_TAG_reference_type:
 807     case DW_TAG_rvalue_reference_type:
 808     case DW_TAG_structure_type:
 809     case DW_TAG_class_type:
 810     case DW_TAG_union_type:
 811       if(subtype->full_type)
 812         subtype = subtype->full_type;
 813       elm_size = subtype->byte_size;
 814       break;
 815     // TODO, just remove the type indirection?
 816     case DW_TAG_const_type:
 817     case DW_TAG_typedef:
 818     case DW_TAG_volatile_type:
 819       subsubtype = subtype->subtype;
 820       if(subsubtype->full_type)
 821         subsubtype = subsubtype->full_type;
 822       elm_size = subsubtype->byte_size;
 823       break;
 824     default :
 825       return 0;
 826       break;
 827     }
 828     for(i=0; i<type->element_count; i++){
 829       // TODO, add support for variable stride (DW_AT_byte_stride)
 830       res = compare_heap_area_with_type(state, (char *)real_area1 + (i*elm_size), (char *)real_area2 + (i*elm_size), (char *)area1 + (i*elm_size), (char *)area2 + (i*elm_size), snapshot1, snapshot2, previous, type->subtype, subtype->byte_size, check_ignore, pointer_level);
 831       if(res == 1)
 832         return res;
 833     }
 834     break;
 835   case DW_TAG_reference_type:
 836   case DW_TAG_rvalue_reference_type:
 837   case DW_TAG_pointer_type:
 838     if(type->subtype && type->subtype->type == DW_TAG_subroutine_type){
 839       addr_pointed1 = *((void **)(area1));
 840       addr_pointed2 = *((void **)(area2));
 841       return (addr_pointed1 != addr_pointed2);;
 842     }else{
 843       pointer_level++;
 844       if(pointer_level > 1){ /* Array of pointers */
 845         for(i=0; i<(area_size/sizeof(void *)); i++){
 846           addr_pointed1 = *((void **)((char *)area1 + (i*sizeof(void *))));
 847           addr_pointed2 = *((void **)((char *)area2 + (i*sizeof(void *))));
 848           if(addr_pointed1 > state->s_heap && (char *)addr_pointed1 < (char*) state->s_heap + STD_HEAP_SIZE && addr_pointed2 > state->s_heap && (char *)addr_pointed2 < (char*) state->s_heap + STD_HEAP_SIZE)
 849             res =  compare_heap_area(addr_pointed1, addr_pointed2, snapshot1, snapshot2, previous, type->subtype, pointer_level);
 850           else
 851             res =  (addr_pointed1 != addr_pointed2);
 852           if(res == 1)
 853             return res;
 854         }
 855       }else{
 856         addr_pointed1 = *((void **)(area1));
 857         addr_pointed2 = *((void **)(area2));
 858         if(addr_pointed1 > state->s_heap && (char *)addr_pointed1 < (char*) state->s_heap + STD_HEAP_SIZE && addr_pointed2 > state->s_heap && (char *)addr_pointed2 < (char*) state->s_heap + STD_HEAP_SIZE)
 859           return compare_heap_area(addr_pointed1, addr_pointed2, snapshot1, snapshot2, previous, type->subtype, pointer_level);
 860         else
 861           return  (addr_pointed1 != addr_pointed2);
 862       }
 863     }
 864     break;
 865   case DW_TAG_structure_type:
 866   case DW_TAG_class_type:
 867     if(type->full_type)
 868       type = type->full_type;
 869     if(area_size != -1 && type->byte_size != area_size){
 870       if(area_size>type->byte_size && area_size%type->byte_size == 0){
 871         for(i=0; i<(area_size/type->byte_size); i++){
 872           res = compare_heap_area_with_type(state, (char *)real_area1 + (i*type->byte_size), (char *)real_area2 + (i*type->byte_size), (char *)area1 + (i*type->byte_size), (char *)area2 + (i*type->byte_size), snapshot1, snapshot2, previous, type, -1, check_ignore, 0);
 873           if(res == 1)
 874             return res;
 875         }
 876       }else{
 877         return -1;
 878       }
 879     }else{
 880       cursor = 0;
 881       xbt_dynar_foreach(type->members, cursor, member){
 882         // TODO, optimize this? (for the offset case)
 883         char* real_member1 = mc_member_resolve(real_area1, type, member, snapshot1);
 884         char* real_member2 = mc_member_resolve(real_area2, type, member, snapshot2);
 885         char* member1 = mc_translate_address((uintptr_t)real_member1, snapshot1);
 886         char* member2 = mc_translate_address((uintptr_t)real_member2, snapshot2);
 887         res = compare_heap_area_with_type(state, real_member1, real_member2, member1, member2, snapshot1, snapshot2, previous, member->subtype, -1, check_ignore, 0);
 888         if(res == 1){
 889           return res;
 890         }
 891       }
 892     }
 893     break;
 894   case DW_TAG_union_type:
 895     return compare_heap_area_without_type(state, real_area1, real_area2, area1, area2, snapshot1, snapshot2, previous, type->byte_size, check_ignore);
 896     break;
 897   default:
 898     break;
 899   }
 900
 901   return 0;
 902
 903 }
 904
 905 /** Infer the type of a part of the block from the type of the block
 906  *
 907  * TODO, handle DW_TAG_array_type as well as arrays of the object ((*p)[5], p[5])
 908  *
 909  * TODO, handle subfields ((*p).bar.foo, (*p)[5].bar…)
 910  *
 911  * @param  type_id            DWARF type ID of the root address
 912  * @param  area_size
 913  * @return                    DWARF type ID for given offset
 914  */
 915 static dw_type_t get_offset_type(void* real_base_address, dw_type_t type, int offset, int area_size, mc_snapshot_t snapshot){
 916
 917   // Beginning of the block, the infered variable type if the type of the block:
 918   if(offset==0)
 919     return type;
 920
 921   switch(type->type){
 922   case DW_TAG_structure_type :
 923   case DW_TAG_class_type:
 924     if(type->full_type)
 925       type = type->full_type;
 926
 927     if(area_size != -1 && type->byte_size != area_size){
 928       if(area_size>type->byte_size && area_size%type->byte_size == 0)
 929         return type;
 930       else
 931         return NULL;
 932     }else{
 933       unsigned int cursor = 0;
 934       dw_type_t member;
 935       xbt_dynar_foreach(type->members, cursor, member){
 936
 937         if(!member->location.size) {
 938           // We have the offset, use it directly (shortcut):
 939           if(member->offset == offset)
 940             return member->subtype;
 941         } else {
 942           char* real_member = mc_member_resolve(real_base_address, type, member, snapshot);
 943           if(real_member - (char*)real_base_address == offset)
 944             return member->subtype;
 945         }
 946
 947       }
 948       return NULL;
 949     }
 950     break;
 951   default:
 952     /* FIXME : other cases ? */
 953     return NULL;
 954     break;
 955   }
 956 }
 957
 958 /**
 959  *
 960  * @param area1          Process address for state 1
 961  * @param area2          Process address for state 2
 962  * @param snapshot1      Snapshot of state 1
 963  * @param snapshot2      Snapshot of state 2
 964  * @param previous       Pairs of blocks already compared on the current path (or NULL)
 965  * @param type_id        Type of variable
 966  * @param pointer_level
 967  * @return 0 (same), 1 (different), -1
 968  */
 969 int compare_heap_area(void *area1, void* area2, mc_snapshot_t snapshot1, mc_snapshot_t snapshot2, xbt_dynar_t previous, dw_type_t type, int pointer_level){
 970
 971   struct s_mm_diff* state = mm_diff_info;
 972
 973   int res_compare;
 974   ssize_t block1, frag1, block2, frag2;
 975   ssize_t size;
 976   int check_ignore = 0;
 977
 978   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2, *real_addr_block1, *real_addr_block2,  *real_addr_frag1, *real_addr_frag2;
 979   void *area1_to_compare, *area2_to_compare;
 980   int type_size = -1;
 981   int offset1 =0, offset2 = 0;
 982   int new_size1 = -1, new_size2 = -1;
 983   dw_type_t new_type1 = NULL, new_type2 = NULL;
 984
 985   int match_pairs = 0;
 986
 987   if(previous == NULL){
 988     previous = xbt_dynar_new(sizeof(heap_area_pair_t), heap_area_pair_free_voidp);
 989     match_pairs = 1;
 990   }
 991
 992   // Get block number:
 993   block1 = ((char*)area1 - (char*)((xbt_mheap_t)state->s_heap)->heapbase) / BLOCKSIZE + 1;
 994   block2 = ((char*)area2 - (char*)((xbt_mheap_t)state->s_heap)->heapbase) / BLOCKSIZE + 1;
 995
 996   // If either block is a stack block:
 997   if(is_block_stack((int)block1) && is_block_stack((int)block2)){
 998     add_heap_area_pair(previous, block1, -1, block2, -1);
 999     if(match_pairs){
1000       match_equals(state, previous);
1001       xbt_dynar_free(&previous);
1002     }
1003     return 0;
1004   }
1005
1006   // If either block is not in the expected area of memory:
1007   if(((char *)area1 < (char*)((xbt_mheap_t)state->s_heap)->heapbase)  || (block1 > state->heapsize1) || (block1 < 1)
1008     || ((char *)area2 < (char*)((xbt_mheap_t)state->s_heap)->heapbase) || (block2 > state->heapsize2) || (block2 < 1)){
1009     if(match_pairs){
1010       xbt_dynar_free(&previous);
1011     }
1012     return 1;
1013   }
1014
1015   // Snapshot address of the block:
1016   addr_block1 = ((void*) (((ADDR2UINT(block1)) - 1) * BLOCKSIZE + (char*)state->heapbase1));
1017   addr_block2 = ((void*) (((ADDR2UINT(block2)) - 1) * BLOCKSIZE + (char*)state->heapbase2));
1018
1019   // Process address of the block:
1020   real_addr_block1 = ((void*) (((ADDR2UINT(block1)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)state->s_heap)->heapbase));
1021   real_addr_block2 = ((void*) (((ADDR2UINT(block2)) - 1) * BLOCKSIZE + (char*)((xbt_mheap_t)state->s_heap)->heapbase));
1022
1023   if(type){
1024
1025     if(type->full_type)
1026       type = type->full_type;
1027
1028     // This assume that for "boring" types (volatile ...) byte_size is absent:
1029     while(type->byte_size == 0 && type->subtype!=NULL)
1030       type = type->subtype;
1031
1032     // Find type_size:
1033     if((type->type == DW_TAG_pointer_type) || ((type->type == DW_TAG_base_type) && type->name!=NULL && (!strcmp(type->name, "char"))))
1034       type_size = -1;
1035     else
1036       type_size = type->byte_size;
1037
1038   }
1039
1040   if((state->heapinfo1[block1].type == -1) && (state->heapinfo2[block2].type == -1)){  /* Free block */
1041
1042     if(match_pairs){
1043       match_equals(state, previous);
1044       xbt_dynar_free(&previous);
1045     }
1046     return 0;
1047
1048   }else if((state->heapinfo1[block1].type == 0) && (state->heapinfo2[block2].type == 0)){ /* Complete block */
1049
1050     // TODO, lookup variable type from block type as done for fragmented blocks
1051
1052     if(state->equals_to1_(block1,0).valid && state->equals_to2_(block2,0).valid){
1053       if(equal_blocks(state, block1, block2)){
1054         if(match_pairs){
1055           match_equals(state, previous);
1056           xbt_dynar_free(&previous);
1057         }
1058         return 0;
1059       }
1060     }
1061
1062     if(type_size != -1){
1063       if(type_size != state->heapinfo1[block1].busy_block.busy_size
1064         && type_size != state->heapinfo2[block2].busy_block.busy_size
1065         && type->name!=NULL && !strcmp(type->name, "s_smx_context")){
1066         if(match_pairs){
1067           match_equals(state, previous);
1068           xbt_dynar_free(&previous);
1069         }
1070         return -1;
1071       }
1072     }
1073
1074     if(state->heapinfo1[block1].busy_block.size != state->heapinfo2[block2].busy_block.size){
1075       if(match_pairs){
1076         xbt_dynar_free(&previous);
1077       }
1078       return 1;
1079     }
1080
1081     if(state->heapinfo1[block1].busy_block.busy_size != state->heapinfo2[block2].busy_block.busy_size){
1082       if(match_pairs){
1083         xbt_dynar_free(&previous);
1084       }
1085       return 1;
1086     }
1087
1088     if(!add_heap_area_pair(previous, block1, -1, block2, -1)){
1089       if(match_pairs){
1090         match_equals(state, previous);
1091         xbt_dynar_free(&previous);
1092       }
1093       return 0;
1094     }
1095
1096     size = state->heapinfo1[block1].busy_block.busy_size;
1097
1098     // Remember (basic) type inference.
1099     // The current data structure only allows us to do this for the whole block.
1100     if (type != NULL && area1==real_addr_block1) {
1101       state->types1_(block1,0) = type;
1102     }
1103     if (type != NULL && area2==real_addr_block2) {
1104       state->types2_(block2,0) = type;
1105     }
1106
1107     if(size <= 0){
1108       if(match_pairs){
1109         match_equals(state, previous);
1110         xbt_dynar_free(&previous);
1111       }
1112       return 0;
1113     }
1114
1115     frag1 = -1;
1116     frag2 = -1;
1117
1118     area1_to_compare = addr_block1;
1119     area2_to_compare = addr_block2;
1120
1121     if((state->heapinfo1[block1].busy_block.ignore > 0) && (state->heapinfo2[block2].busy_block.ignore == state->heapinfo1[block1].busy_block.ignore))
1122       check_ignore = state->heapinfo1[block1].busy_block.ignore;
1123
1124   }else if((state->heapinfo1[block1].type > 0) && (state->heapinfo2[block2].type > 0)){ /* Fragmented block */
1125
1126     // Fragment number:
1127     frag1 = ((uintptr_t) (ADDR2UINT (area1) % (BLOCKSIZE))) >> state->heapinfo1[block1].type;
1128     frag2 = ((uintptr_t) (ADDR2UINT (area2) % (BLOCKSIZE))) >> state->heapinfo2[block2].type;
1129
1130     // Snapshot address of the fragment:
1131     addr_frag1 = (void*) ((char *)addr_block1 + (frag1 << state->heapinfo1[block1].type));
1132     addr_frag2 = (void*) ((char *)addr_block2 + (frag2 << state->heapinfo2[block2].type));
1133
1134     // Process address of the fragment:
1135     real_addr_frag1 = (void*) ((char *)real_addr_block1 + (frag1 << ((xbt_mheap_t)state->s_heap)->heapinfo[block1].type));
1136     real_addr_frag2 = (void*) ((char *)real_addr_block2 + (frag2 << ((xbt_mheap_t)state->s_heap)->heapinfo[block2].type));
1137
1138     // Check the size of the fragments against the size of the type:
1139     if(type_size != -1){
1140       if(state->heapinfo1[block1].busy_frag.frag_size[frag1] == -1 || state->heapinfo2[block2].busy_frag.frag_size[frag2] == -1){
1141         if(match_pairs){
1142           match_equals(state, previous);
1143           xbt_dynar_free(&previous);
1144         }
1145         return -1;
1146       }
1147       if(type_size != state->heapinfo1[block1].busy_frag.frag_size[frag1]|| type_size !=  state->heapinfo2[block2].busy_frag.frag_size[frag2]){
1148         if(match_pairs){
1149           match_equals(state, previous);
1150           xbt_dynar_free(&previous);
1151         }
1152         return -1;
1153       }
1154     }
1155
1156     // Check if the blocks are already matched together:
1157     if(state->equals_to1_(block1,frag1).valid && state->equals_to2_(block2,frag2).valid){
1158       if(equal_fragments(state, block1, frag1, block2, frag2)){
1159         if(match_pairs){
1160           match_equals(state, previous);
1161           xbt_dynar_free(&previous);
1162         }
1163         return 0;
1164       }
1165     }
1166
1167     // Compare the size of both fragments:
1168     if(state->heapinfo1[block1].busy_frag.frag_size[frag1] != state->heapinfo2[block2].busy_frag.frag_size[frag2]){
1169       if(type_size == -1){
1170          if(match_pairs){
1171           match_equals(state, previous);
1172           xbt_dynar_free(&previous);
1173         }
1174         return -1;
1175       }else{
1176         if(match_pairs){
1177           xbt_dynar_free(&previous);
1178         }
1179         return 1;
1180       }
1181     }
1182
1183     // Size of the fragment:
1184     size = state->heapinfo1[block1].busy_frag.frag_size[frag1];
1185
1186     // Remember (basic) type inference.
1187     // The current data structure only allows us to do this for the whole block.
1188     if(type != NULL && area1==real_addr_frag1){
1189       state->types1_(block1,frag1) = type;
1190     }
1191     if(type != NULL && area2==real_addr_frag2) {
1192       state->types2_(block2,frag2) = type;
1193     }
1194
1195     // The type of the variable is already known:
1196     if(type) {
1197       new_type1 = type;
1198       new_type2 = type;
1199     }
1200
1201     // Type inference from the block type.
1202     else if(state->types1_(block1,frag1) != NULL || state->types2_(block2,frag2) != NULL) {
1203
1204       offset1 = (char *)area1 - (char *)real_addr_frag1;
1205       offset2 = (char *)area2 - (char *)real_addr_frag2;
1206
1207       if(state->types1_(block1,frag1) != NULL && state->types2_(block2,frag2) != NULL){
1208         new_type1 = get_offset_type(real_addr_frag1, state->types1_(block1,frag1), offset1, size, snapshot1);
1209         new_type2 = get_offset_type(real_addr_frag2, state->types2_(block2,frag2), offset1, size, snapshot2);
1210       }else if(state->types1_(block1,frag1) != NULL){
1211         new_type1 = get_offset_type(real_addr_frag1, state->types1_(block1,frag1), offset1, size, snapshot1);
1212         new_type2 = get_offset_type(real_addr_frag2, state->types1_(block1,frag1), offset2, size, snapshot2);
1213       }else if(state->types2_(block2,frag2) != NULL){
1214         new_type1 = get_offset_type(real_addr_frag1, state->types2_(block2,frag2), offset1, size, snapshot1);
1215         new_type2 = get_offset_type(real_addr_frag2, state->types2_(block2,frag2), offset2, size, snapshot2);
1216       }else{
1217         if(match_pairs){
1218           match_equals(state, previous);
1219           xbt_dynar_free(&previous);
1220         }
1221         return -1;
1222       }
1223
1224       if(new_type1 !=  NULL && new_type2 !=  NULL && new_type1!=new_type2){
1225
1226           type = new_type1;
1227           while(type->byte_size == 0 && type->subtype != NULL)
1228             type = type->subtype;
1229           new_size1 = type->byte_size;
1230
1231           type = new_type2;
1232           while(type->byte_size == 0 && type->subtype != NULL)
1233             type = type->subtype;
1234           new_size2 = type->byte_size;
1235
1236       }else{
1237         if(match_pairs){
1238           match_equals(state, previous);
1239           xbt_dynar_free(&previous);
1240         }
1241         return -1;
1242       }
1243     }
1244
1245     area1_to_compare = (char *)addr_frag1 + offset1;
1246     area2_to_compare = (char *)addr_frag2 + offset2;
1247
1248     if(new_size1 > 0 && new_size1 == new_size2){
1249       type = new_type1;
1250       size = new_size1;
1251     }
1252
1253     if(offset1 == 0 && offset2 == 0){
1254       if(!add_heap_area_pair(previous, block1, frag1, block2, frag2)){
1255         if(match_pairs){
1256           match_equals(state, previous);
1257           xbt_dynar_free(&previous);
1258         }
1259         return 0;
1260       }
1261     }
1262
1263     if(size <= 0){
1264       if(match_pairs){
1265         match_equals(state, previous);
1266         xbt_dynar_free(&previous);
1267       }
1268       return 0;
1269     }
1270
1271     if((state->heapinfo1[block1].busy_frag.ignore[frag1] > 0) && ( state->heapinfo2[block2].busy_frag.ignore[frag2] == state->heapinfo1[block1].busy_frag.ignore[frag1]))
1272       check_ignore = state->heapinfo1[block1].busy_frag.ignore[frag1];
1273
1274   }else{
1275
1276     if(match_pairs){
1277       xbt_dynar_free(&previous);
1278     }
1279     return 1;
1280
1281   }
1282
1283
1284   /* Start comparison*/
1285   if(type){
1286     res_compare = compare_heap_area_with_type(state, area1, area2, area1_to_compare, area2_to_compare, snapshot1, snapshot2, previous, type, size, check_ignore, pointer_level);
1287   }else{
1288     res_compare = compare_heap_area_without_type(state, area1, area2, area1_to_compare, area2_to_compare, snapshot1, snapshot2, previous, size, check_ignore);
1289   }
1290   if(res_compare == 1){
1291     if(match_pairs)
1292       xbt_dynar_free(&previous);
1293     return res_compare;
1294   }
1295
1296   if(match_pairs){
1297     match_equals(state, previous);
1298     xbt_dynar_free(&previous);
1299   }
1300
1301   return 0;
1302 }
1303
1304 /*********************************************** Miscellaneous ***************************************************/
1305 /****************************************************************************************************************/
1306
1307 // Not used:
1308 static int get_pointed_area_size(void *area, int heap){
1309
1310   struct s_mm_diff *state = mm_diff_info;
1311
1312   int block, frag;
1313   malloc_info *heapinfo;
1314
1315   if(heap == 1)
1316     heapinfo = state->heapinfo1;
1317   else
1318     heapinfo = state->heapinfo2;
1319
1320   block = ((char*)area - (char*)((xbt_mheap_t)state->s_heap)->heapbase) / BLOCKSIZE + 1;
1321
1322   if(((char *)area < (char*)((xbt_mheap_t)state->s_heap)->heapbase)  || (block > state->heapsize1) || (block < 1))
1323     return -1;
1324
1325   if(heapinfo[block].type == -1){ /* Free block */
1326     return -1;
1327   }else if(heapinfo[block].type == 0){ /* Complete block */
1328     return (int)heapinfo[block].busy_block.busy_size;
1329   }else{
1330     frag = ((uintptr_t) (ADDR2UINT (area) % (BLOCKSIZE))) >> heapinfo[block].type;
1331     return (int)heapinfo[block].busy_frag.frag_size[frag];
1332   }
1333
1334 }
1335
1336 // Not used:
1337 char *get_type_description(mc_object_info_t info, char *type_name){
1338
1339   xbt_dict_cursor_t dict_cursor;
1340   char *type_origin;
1341   dw_type_t type;
1342
1343   xbt_dict_foreach(info->types, dict_cursor, type_origin, type){
1344     if(type->name && (strcmp(type->name, type_name) == 0) && type->byte_size > 0){
1345       xbt_dict_cursor_free(&dict_cursor);
1346       return type_origin;
1347     }
1348   }
1349
1350   xbt_dict_cursor_free(&dict_cursor);
1351   return NULL;
1352 }
1353
1354
1355 #ifndef max
1356 #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
1357 #endif
1358
1359 // Not used:
1360 int mmalloc_linear_compare_heap(xbt_mheap_t heap1, xbt_mheap_t heap2){
1361
1362   struct s_mm_diff *state = mm_diff_info;
1363
1364   if(heap1 == NULL && heap1 == NULL){
1365     XBT_DEBUG("Malloc descriptors null");
1366     return 0;
1367   }
1368
1369   if(heap1->heaplimit != heap2->heaplimit){
1370     XBT_DEBUG("Different limit of valid info table indices");
1371     return 1;
1372   }
1373
1374   /* Heap information */
1375   state->heaplimit = ((struct mdesc *)heap1)->heaplimit;
1376
1377   state->s_heap = (char *)mmalloc_get_current_heap() - STD_HEAP_SIZE - xbt_pagesize;
1378
1379   state->heapbase1 = (char *)heap1 + BLOCKSIZE;
1380   state->heapbase2 = (char *)heap2 + BLOCKSIZE;
1381
1382   state->heapinfo1 = (malloc_info *)((char *)heap1 + ((uintptr_t)((char *)heap1->heapinfo - (char *)state->s_heap)));
1383   state->heapinfo2 = (malloc_info *)((char *)heap2 + ((uintptr_t)((char *)heap2->heapinfo - (char *)state->s_heap)));
1384
1385   state->heapsize1 = heap1->heapsize;
1386   state->heapsize2 = heap2->heapsize;
1387
1388   /* Start comparison */
1389   size_t i, j, k;
1390   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
1391
1392   int distance = 0;
1393
1394   /* Check busy blocks*/
1395
1396   i = 1;
1397
1398   while(i <= state->heaplimit){
1399
1400     addr_block1 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)state->heapbase1));
1401     addr_block2 = ((void*) (((ADDR2UINT(i)) - 1) * BLOCKSIZE + (char*)state->heapbase2));
1402
1403     if(state->heapinfo1[i].type != state->heapinfo2[i].type){
1404
1405       distance += BLOCKSIZE;
1406       XBT_DEBUG("Different type of blocks (%zu) : %d - %d -> distance = %d", i, state->heapinfo1[i].type, state->heapinfo2[i].type, distance);
1407       i++;
1408
1409     }else{
1410
1411       if(state->heapinfo1[i].type == -1){ /* Free block */
1412         i++;
1413         continue;
1414       }
1415
1416       if(state->heapinfo1[i].type == 0){ /* Large block */
1417
1418         if(state->heapinfo1[i].busy_block.size != state->heapinfo2[i].busy_block.size){
1419           distance += BLOCKSIZE * max(state->heapinfo1[i].busy_block.size, state->heapinfo2[i].busy_block.size);
1420           i += max(state->heapinfo1[i].busy_block.size, state->heapinfo2[i].busy_block.size);
1421           XBT_DEBUG("Different larger of cluster at block %zu : %zu - %zu -> distance = %d", i, state->heapinfo1[i].busy_block.size, state->heapinfo2[i].busy_block.size, distance);
1422           continue;
1423         }
1424
1425         /*if(heapinfo1[i].busy_block.busy_size != heapinfo2[i].busy_block.busy_size){
1426           distance += max(heapinfo1[i].busy_block.busy_size, heapinfo2[i].busy_block.busy_size);
1427           i += max(heapinfo1[i].busy_block.size, heapinfo2[i].busy_block.size);
1428           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);
1429           continue;
1430           }*/
1431
1432         k = 0;
1433
1434         //while(k < (heapinfo1[i].busy_block.busy_size)){
1435         while(k < state->heapinfo1[i].busy_block.size * BLOCKSIZE){
1436           if(memcmp((char *)addr_block1 + k, (char *)addr_block2 + k, 1) != 0){
1437             distance ++;
1438           }
1439           k++;
1440         }
1441
1442         i++;
1443
1444       }else { /* Fragmented block */
1445
1446         for(j=0; j < (size_t) (BLOCKSIZE >> state->heapinfo1[i].type); j++){
1447
1448           addr_frag1 = (void*) ((char *)addr_block1 + (j << state->heapinfo1[i].type));
1449           addr_frag2 = (void*) ((char *)addr_block2 + (j << state->heapinfo2[i].type));
1450
1451           if(state->heapinfo1[i].busy_frag.frag_size[j] == 0 && state->heapinfo2[i].busy_frag.frag_size[j] == 0){
1452             continue;
1453           }
1454
1455
1456           /*if(heapinfo1[i].busy_frag.frag_size[j] != heapinfo2[i].busy_frag.frag_size[j]){
1457             distance += max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j]);
1458             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);
1459             continue;
1460             }*/
1461
1462           k=0;
1463
1464           //while(k < max(heapinfo1[i].busy_frag.frag_size[j], heapinfo2[i].busy_frag.frag_size[j])){
1465           while(k < (BLOCKSIZE / (BLOCKSIZE >> state->heapinfo1[i].type))){
1466             if(memcmp((char *)addr_frag1 + k, (char *)addr_frag2 + k, 1) != 0){
1467               distance ++;
1468             }
1469             k++;
1470           }
1471
1472         }
1473
1474         i++;
1475
1476       }
1477
1478     }
1479
1480   }
1481
1482   return distance;
1483
1484 }
1485