src/mc/mc_diff.cpp

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