src/mc/mc_diff.c

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