src/mc/mc_diff.cpp

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