src/mc/compare.cpp

   1 /* Copyright (c) 2008-2016. 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 /** \file mc_compare.cpp Memory snapshooting and comparison                 */
   8
   9 #include <cinttypes>
  10
  11 #include <array>
  12 #include <memory>
  13 #include <utility>
  14 #include <unordered_set>
  15
  16 #include <xbt/sysdep.h>
  17 #include <xbt/dynar.h>
  18 #include <xbt/mmalloc.h>
  19
  20 #include <mc/mc.h>
  21 #include <mc/datatypes.h>
  22
  23 #include "src/internal_config.h"
  24
  25 #include "src/xbt/mmalloc/mmprivate.h"
  26 #include "src/xbt/ex_interface.h"
  27
  28 #if HAVE_SMPI
  29 #include "src/smpi/private.h"
  30 #endif
  31
  32 #include "src/mc/mc_forward.hpp"
  33 #include "src/mc/mc_safety.h"
  34 #include "src/mc/mc_private.h"
  35 #include "src/mc/mc_smx.h"
  36 #include "src/mc/mc_dwarf.hpp"
  37 #include "src/mc/Frame.hpp"
  38 #include "src/mc/ObjectInformation.hpp"
  39 #include "src/mc/Variable.hpp"
  40 #include "src/mc/mc_private.h"
  41 #include "src/mc/mc_snapshot.h"
  42 #include "src/mc/mc_dwarf.hpp"
  43 #include "src/mc/Type.hpp"
  44
  45 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt,
  46                                 "Logging specific to mc_compare in mc");
  47
  48 namespace simgrid {
  49 namespace mc {
  50
  51 struct ProcessComparisonState;
  52 struct StateComparator;
  53
  54 static int compare_heap_area(
  55   StateComparator& state,
  56   int process_index, const void *area1, const void* area2,
  57   Snapshot* snapshot1, Snapshot* snapshot2,
  58   xbt_dynar_t previous, Type* type, int pointer_level);
  59
  60 }
  61 }
  62
  63 using simgrid::mc::remote;
  64
  65 /*********************************** Heap comparison ***********************************/
  66 /***************************************************************************************/
  67
  68 namespace simgrid {
  69 namespace mc {
  70
  71 struct HeapLocation {
  72   int block = 0;
  73   int fragment = 0;
  74   HeapLocation() {}
  75   HeapLocation(int block, int fragment = 0) : block(block), fragment(fragment) {}
  76 };
  77
  78 typedef std::array<HeapLocation, 2> HeapLocationPair;
  79
  80 struct HeapArea : public HeapLocation {
  81   bool valid = false;
  82   int block = 0;
  83   int fragment = 0;
  84   HeapArea() {}
  85   HeapArea(int block)
  86     : valid(true), block(block) {}
  87   HeapArea(int block, int fragment = 0)
  88     : valid(true), block(block), fragment(fragment) {}
  89 };
  90
  91 struct ProcessComparisonState {
  92   std::vector<simgrid::mc::IgnoredHeapRegion>* to_ignore = nullptr;
  93   std::vector<HeapArea> equals_to;
  94   std::vector<simgrid::mc::Type*> types;
  95   std::size_t heapsize = 0;
  96
  97   void initHeapInformation(xbt_mheap_t heap,
  98                           std::vector<simgrid::mc::IgnoredHeapRegion>* i);
  99 };
 100
 101 namespace {
 102
 103 /** A hash which works with more stuff
 104  *
 105  *  It can hash pairs: the standard hash currently doesn't include this.
 106  */
 107 template<class X> struct hash : public std::hash<X> {};
 108
 109 template<class X, class Y>
 110 struct hash<std::pair<X,Y>> {
 111   std::size_t operator()(std::pair<X,Y>const& x) const
 112   {
 113     struct hash<X> h1;
 114     struct hash<X> h2;
 115     return h1(x.first) ^ h2(x.second);
 116   }
 117 };
 118
 119 }
 120
 121
 122 struct StateComparator {
 123   s_xbt_mheap_t std_heap_copy;
 124   std::size_t heaplimit;
 125   std::array<ProcessComparisonState, 2> processStates;
 126
 127   std::unordered_set<std::pair<void*, void*>, hash<std::pair<void*, void*>>> compared_pointers;
 128
 129   void clear()
 130   {
 131     compared_pointers.clear();
 132   }
 133
 134   int initHeapInformation(
 135     xbt_mheap_t heap1, xbt_mheap_t heap2,
 136     std::vector<simgrid::mc::IgnoredHeapRegion>* i1,
 137     std::vector<simgrid::mc::IgnoredHeapRegion>* i2);
 138
 139   HeapArea& equals_to1_(std::size_t i, std::size_t j)
 140   {
 141     return processStates[0].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j];
 142   }
 143   HeapArea& equals_to2_(std::size_t i, std::size_t j)
 144   {
 145     return processStates[1].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j];
 146   }
 147   Type*& types1_(std::size_t i, std::size_t j)
 148   {
 149     return processStates[0].types[ MAX_FRAGMENT_PER_BLOCK * i + j];
 150   }
 151   Type*& types2_(std::size_t i, std::size_t j)
 152   {
 153     return processStates[1].types[ MAX_FRAGMENT_PER_BLOCK * i + j];
 154   }
 155
 156   HeapArea const& equals_to1_(std::size_t i, std::size_t j) const
 157   {
 158     return processStates[0].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j];
 159   }
 160   HeapArea const& equals_to2_(std::size_t i, std::size_t j) const
 161   {
 162     return processStates[1].equals_to[ MAX_FRAGMENT_PER_BLOCK * i + j];
 163   }
 164   Type* const& types1_(std::size_t i, std::size_t j) const
 165   {
 166     return processStates[0].types[ MAX_FRAGMENT_PER_BLOCK * i + j];
 167   }
 168   Type* const& types2_(std::size_t i, std::size_t j) const
 169   {
 170     return processStates[1].types[ MAX_FRAGMENT_PER_BLOCK * i + j];
 171   }
 172
 173   /** Check whether two blocks are known to be matching
 174    *
 175    *  @param state  State used
 176    *  @param b1     Block of state 1
 177    *  @param b2     Block of state 2
 178    *  @return       if the blocks are known to be matching
 179    */
 180   bool blocksEqual(int b1, int b2) const
 181   {
 182     return this->equals_to1_(b1, 0).block == b2
 183         && this->equals_to2_(b2, 0).block == b1;
 184   }
 185
 186   /** Check whether two fragments are known to be matching
 187    *
 188    *  @param state  State used
 189    *  @param b1     Block of state 1
 190    *  @param f1     Fragment of state 1
 191    *  @param b2     Block of state 2
 192    *  @param f2     Fragment of state 2
 193    *  @return       if the fragments are known to be matching
 194    */
 195   int fragmentsEqual(int b1, int f1, int b2, int f2) const
 196   {
 197     return this->equals_to1_(b1, f1).block == b2
 198         && this->equals_to1_(b1, f1).fragment == f2
 199         && this->equals_to2_(b2, f2).block == b1
 200         && this->equals_to2_(b2, f2).fragment == f1;
 201   }
 202
 203   void match_equals(xbt_dynar_t list);
 204 };
 205
 206 }
 207 }
 208
 209 /************************************************************************************/
 210
 211 static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
 212                                  int block2, int fragment2)
 213 {
 214
 215   unsigned int cursor = 0;
 216   simgrid::mc::HeapLocationPair* current_pair;
 217   xbt_dynar_foreach(list, cursor, current_pair)
 218     if ((*current_pair)[0].block == block1
 219         && (*current_pair)[1].block == block2
 220         && (*current_pair)[0].fragment == fragment1
 221         && (*current_pair)[1].fragment == fragment2)
 222       return 0;
 223   return 1;
 224 }
 225
 226 static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
 227                               int block2, int fragment2)
 228 {
 229   if (!is_new_heap_area_pair(list, block1, fragment1, block2, fragment2))
 230     return 0;
 231   simgrid::mc::HeapLocationPair* pair = xbt_new0(simgrid::mc::HeapLocationPair, 1);
 232   (*pair)[0].block = block1;
 233   (*pair)[0].fragment = fragment1;
 234   (*pair)[1].block = block2;
 235   (*pair)[1].fragment = fragment2;
 236   xbt_dynar_push(list, &pair);
 237   return 1;
 238 }
 239
 240 static ssize_t heap_comparison_ignore_size(
 241   std::vector<simgrid::mc::IgnoredHeapRegion>* ignore_list,
 242   const void *address)
 243 {
 244   int start = 0;
 245   int end = ignore_list->size() - 1;
 246
 247   while (start <= end) {
 248     unsigned int cursor = (start + end) / 2;
 249     simgrid::mc::IgnoredHeapRegion const& region = (*ignore_list)[cursor];
 250     if (region.address == address)
 251       return region.size;
 252     if (region.address < address)
 253       start = cursor + 1;
 254     if (region.address > address)
 255       end = cursor - 1;
 256   }
 257
 258   return -1;
 259 }
 260
 261 static bool is_stack(const void *address)
 262 {
 263   for (auto const& stack : mc_model_checker->process().stack_areas())
 264     if (address == stack.address)
 265       return true;
 266   return false;
 267 }
 268
 269 // TODO, this should depend on the snapshot?
 270 static bool is_block_stack(int block)
 271 {
 272   for (auto const& stack : mc_model_checker->process().stack_areas())
 273     if (block == stack.block)
 274       return true;
 275   return false;
 276 }
 277
 278 namespace simgrid {
 279 namespace mc {
 280
 281 void StateComparator::match_equals(xbt_dynar_t list)
 282 {
 283   unsigned int cursor = 0;
 284   simgrid::mc::HeapLocationPair* current_pair;
 285
 286   xbt_dynar_foreach(list, cursor, current_pair) {
 287     if ((*current_pair)[0].fragment != -1) {
 288       this->equals_to1_((*current_pair)[0].block, (*current_pair)[0].fragment) =
 289           simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment);
 290       this->equals_to2_((*current_pair)[1].block, (*current_pair)[1].fragment) =
 291           simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment);
 292     } else {
 293       this->equals_to1_((*current_pair)[0].block, 0) =
 294           simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment);
 295       this->equals_to2_((*current_pair)[1].block, 0) =
 296           simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment);
 297     }
 298   }
 299 }
 300
 301 void ProcessComparisonState::initHeapInformation(xbt_mheap_t heap,
 302                         std::vector<simgrid::mc::IgnoredHeapRegion>* i)
 303 {
 304   auto heaplimit = ((struct mdesc *) heap)->heaplimit;
 305   this->heapsize = ((struct mdesc *) heap)->heapsize;
 306   this->to_ignore = i;
 307   this->equals_to.assign(heaplimit * MAX_FRAGMENT_PER_BLOCK, HeapArea());
 308   this->types.assign(heaplimit * MAX_FRAGMENT_PER_BLOCK, nullptr);
 309 }
 310
 311 int StateComparator::initHeapInformation(xbt_mheap_t heap1, xbt_mheap_t heap2,
 312                           std::vector<simgrid::mc::IgnoredHeapRegion>* i1,
 313                           std::vector<simgrid::mc::IgnoredHeapRegion>* i2)
 314 {
 315   if ((((struct mdesc *) heap1)->heaplimit !=
 316        ((struct mdesc *) heap2)->heaplimit)
 317       ||
 318       ((((struct mdesc *) heap1)->heapsize !=
 319         ((struct mdesc *) heap2)->heapsize)))
 320     return -1;
 321   this->heaplimit = ((struct mdesc *) heap1)->heaplimit;
 322   this->std_heap_copy = *mc_model_checker->process().get_heap();
 323   this->processStates[0].initHeapInformation(heap1, i1);
 324   this->processStates[1].initHeapInformation(heap2, i2);
 325   return 0;
 326 }
 327
 328 // TODO, have a robust way to find it in O(1)
 329 static inline
 330 mc_mem_region_t MC_get_heap_region(simgrid::mc::Snapshot* snapshot)
 331 {
 332   for (auto& region : snapshot->snapshot_regions)
 333     if (region->region_type() == simgrid::mc::RegionType::Heap)
 334       return region.get();
 335   xbt_die("No heap region");
 336 }
 337
 338 static
 339 int mmalloc_compare_heap(
 340   simgrid::mc::StateComparator& state, simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2)
 341 {
 342   simgrid::mc::Process* process = &mc_model_checker->process();
 343
 344   /* Start comparison */
 345   size_t i1, i2, j1, j2, k;
 346   void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
 347   int nb_diff1 = 0, nb_diff2 = 0;
 348
 349   int equal, res_compare = 0;
 350
 351   /* Check busy blocks */
 352
 353   i1 = 1;
 354
 355   malloc_info heapinfo_temp1, heapinfo_temp2;
 356   malloc_info heapinfo_temp2b;
 357
 358   mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1);
 359   mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2);
 360
 361   // This is the address of std_heap->heapinfo in the application process:
 362   void* heapinfo_address = &((xbt_mheap_t) process->heap_address)->heapinfo;
 363
 364   // This is in snapshot do not use them directly:
 365   const malloc_info* heapinfos1 = snapshot1->read<malloc_info*>(
 366     (std::uint64_t)heapinfo_address, simgrid::mc::ProcessIndexMissing);
 367   const malloc_info* heapinfos2 = snapshot2->read<malloc_info*>(
 368     (std::uint64_t)heapinfo_address, simgrid::mc::ProcessIndexMissing);
 369
 370   while (i1 < state.heaplimit) {
 371
 372     const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read(heap_region1, &heapinfo_temp1, &heapinfos1[i1], sizeof(malloc_info));
 373     const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read(heap_region2, &heapinfo_temp2, &heapinfos2[i1], sizeof(malloc_info));
 374
 375     if (heapinfo1->type == MMALLOC_TYPE_FREE || heapinfo1->type == MMALLOC_TYPE_HEAPINFO) {      /* Free block */
 376       i1 ++;
 377       continue;
 378     }
 379
 380     if (heapinfo1->type < 0) {
 381       fprintf(stderr, "Unkown mmalloc block type.\n");
 382       abort();
 383     }
 384
 385     addr_block1 =
 386         ((void *) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE +
 387                    (char *) state.std_heap_copy.heapbase));
 388
 389     if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED) {       /* Large block */
 390
 391       if (is_stack(addr_block1)) {
 392         for (k = 0; k < heapinfo1->busy_block.size; k++)
 393           state.equals_to1_(i1 + k, 0) = HeapArea(i1, -1);
 394         for (k = 0; k < heapinfo2->busy_block.size; k++)
 395           state.equals_to2_(i1 + k, 0) = HeapArea(i1, -1);
 396         i1 += heapinfo1->busy_block.size;
 397         continue;
 398       }
 399
 400       if (state.equals_to1_(i1, 0).valid) {
 401         i1++;
 402         continue;
 403       }
 404
 405       i2 = 1;
 406       equal = 0;
 407       res_compare = 0;
 408
 409       /* Try first to associate to same block in the other heap */
 410       if (heapinfo2->type == heapinfo1->type
 411         && state.equals_to2_(i1, 0).valid == 0) {
 412         addr_block2 = (ADDR2UINT(i1) - 1) * BLOCKSIZE +
 413                        (char *) state.std_heap_copy.heapbase;
 414         res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing,
 415             addr_block1, addr_block2, snapshot1, snapshot2,
 416             nullptr, nullptr, 0);
 417         if (res_compare != 1) {
 418           for (k = 1; k < heapinfo2->busy_block.size; k++)
 419             state.equals_to2_(i1 + k, 0) = HeapArea(i1, -1);
 420           for (k = 1; k < heapinfo1->busy_block.size; k++)
 421             state.equals_to1_(i1 + k, 0) = HeapArea(i1, -1);
 422           equal = 1;
 423           i1 += heapinfo1->busy_block.size;
 424         }
 425       }
 426
 427       while (i2 < state.heaplimit && !equal) {
 428
 429         addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE +
 430                        (char *) state.std_heap_copy.heapbase;
 431
 432         if (i2 == i1) {
 433           i2++;
 434           continue;
 435         }
 436
 437         const malloc_info* heapinfo2b = (const malloc_info*) MC_region_read(heap_region2, &heapinfo_temp2b, &heapinfos2[i2], sizeof(malloc_info));
 438
 439         if (heapinfo2b->type != MMALLOC_TYPE_UNFRAGMENTED) {
 440           i2++;
 441           continue;
 442         }
 443
 444         if (state.equals_to2_(i2, 0).valid) {
 445           i2++;
 446           continue;
 447         }
 448
 449         res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing,
 450             addr_block1, addr_block2, snapshot1, snapshot2,
 451             nullptr, nullptr, 0);
 452
 453         if (res_compare != 1) {
 454           for (k = 1; k < heapinfo2b->busy_block.size; k++)
 455             state.equals_to2_(i2 + k, 0) = HeapArea(i1, -1);
 456           for (k = 1; k < heapinfo1->busy_block.size; k++)
 457             state.equals_to1_(i1 + k, 0) = HeapArea(i2, -1);
 458           equal = 1;
 459           i1 += heapinfo1->busy_block.size;
 460         }
 461
 462         i2++;
 463
 464       }
 465
 466       if (!equal) {
 467         XBT_DEBUG("Block %zu not found (size_used = %zu, addr = %p)", i1,
 468                   heapinfo1->busy_block.busy_size, addr_block1);
 469         i1 = state.heaplimit + 1;
 470         nb_diff1++;
 471         //i1++;
 472       }
 473
 474     } else {                    /* Fragmented block */
 475
 476       for (j1 = 0; j1 < (size_t) (BLOCKSIZE >> heapinfo1->type); j1++) {
 477
 478         if (heapinfo1->busy_frag.frag_size[j1] == -1) /* Free fragment */
 479           continue;
 480
 481         if (state.equals_to1_(i1, j1).valid)
 482           continue;
 483
 484         addr_frag1 =
 485             (void *) ((char *) addr_block1 + (j1 << heapinfo1->type));
 486
 487         i2 = 1;
 488         equal = 0;
 489
 490         /* Try first to associate to same fragment in the other heap */
 491         if (heapinfo2->type == heapinfo1->type
 492             && !state.equals_to2_(i1, j1).valid) {
 493           addr_block2 = (ADDR2UINT(i1) - 1) * BLOCKSIZE +
 494                          (char *) state.std_heap_copy.heapbase;
 495           addr_frag2 =
 496               (void *) ((char *) addr_block2 +
 497                         (j1 << heapinfo2->type));
 498           res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing,
 499               addr_frag1, addr_frag2, snapshot1, snapshot2,
 500               nullptr, nullptr, 0);
 501           if (res_compare != 1)
 502             equal = 1;
 503         }
 504
 505
 506
 507         while (i2 < state.heaplimit && !equal) {
 508
 509           const malloc_info* heapinfo2b = (const malloc_info*) MC_region_read(
 510             heap_region2, &heapinfo_temp2b, &heapinfos2[i2],
 511             sizeof(malloc_info));
 512
 513           if (heapinfo2b->type == MMALLOC_TYPE_FREE || heapinfo2b->type == MMALLOC_TYPE_HEAPINFO) {
 514             i2 ++;
 515             continue;
 516           }
 517
 518           // We currently do not match fragments with unfragmented blocks (maybe we should).
 519           if (heapinfo2b->type == MMALLOC_TYPE_UNFRAGMENTED) {
 520             i2++;
 521             continue;
 522           }
 523
 524           if (heapinfo2b->type < 0) {
 525             fprintf(stderr, "Unkown mmalloc block type.\n");
 526             abort();
 527           }
 528
 529           for (j2 = 0; j2 < (size_t) (BLOCKSIZE >> heapinfo2b->type);
 530                j2++) {
 531
 532             if (i2 == i1 && j2 == j1)
 533               continue;
 534
 535             if (state.equals_to2_(i2, j2).valid)
 536               continue;
 537
 538             addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE +
 539                            (char *) state.std_heap_copy.heapbase;
 540             addr_frag2 =
 541                 (void *) ((char *) addr_block2 +
 542                           (j2 << heapinfo2b->type));
 543
 544             res_compare = compare_heap_area(
 545                 state, simgrid::mc::ProcessIndexMissing,
 546                 addr_frag1, addr_frag2, snapshot2, snapshot2,
 547                 nullptr, nullptr, 0);
 548             if (res_compare != 1) {
 549               equal = 1;
 550               break;
 551             }
 552
 553           }
 554
 555           i2++;
 556
 557         }
 558
 559         if (!equal) {
 560           XBT_DEBUG
 561               ("Block %zu, fragment %zu not found (size_used = %zd, address = %p)\n",
 562                i1, j1, heapinfo1->busy_frag.frag_size[j1],
 563                addr_frag1);
 564           i2 = state.heaplimit + 1;
 565           i1 = state.heaplimit + 1;
 566           nb_diff1++;
 567           break;
 568         }
 569
 570       }
 571
 572       i1++;
 573
 574     }
 575
 576   }
 577
 578   /* All blocks/fragments are equal to another block/fragment ? */
 579   size_t i = 1, j = 0;
 580
 581   for(i = 1; i < state.heaplimit; i++) {
 582     const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read(
 583       heap_region1, &heapinfo_temp1, &heapinfos1[i], sizeof(malloc_info));
 584
 585     if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED
 586         && i1 == state.heaplimit
 587         && heapinfo1->busy_block.busy_size > 0
 588         && !state.equals_to1_(i, 0).valid) {
 589       XBT_DEBUG("Block %zu not found (size used = %zu)", i,
 590                 heapinfo1->busy_block.busy_size);
 591       nb_diff1++;
 592     }
 593
 594     if (heapinfo1->type <= 0)
 595       continue;
 596     for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo1->type); j++)
 597       if (i1 == state.heaplimit
 598           && heapinfo1->busy_frag.frag_size[j] > 0
 599           && !state.equals_to1_(i, j).valid) {
 600         XBT_DEBUG("Block %zu, Fragment %zu not found (size used = %zd)",
 601           i, j, heapinfo1->busy_frag.frag_size[j]);
 602         nb_diff1++;
 603       }
 604   }
 605
 606   if (i1 == state.heaplimit)
 607     XBT_DEBUG("Number of blocks/fragments not found in heap1 : %d", nb_diff1);
 608
 609   for (i=1; i < state.heaplimit; i++) {
 610     const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read(
 611       heap_region2, &heapinfo_temp2, &heapinfos2[i], sizeof(malloc_info));
 612     if (heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED
 613         && i1 == state.heaplimit
 614         && heapinfo2->busy_block.busy_size > 0
 615         && !state.equals_to2_(i, 0).valid) {
 616       XBT_DEBUG("Block %zu not found (size used = %zu)", i,
 617                 heapinfo2->busy_block.busy_size);
 618       nb_diff2++;
 619     }
 620
 621     if (heapinfo2->type <= 0)
 622       continue;
 623
 624     for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo2->type); j++)
 625       if (i1 == state.heaplimit
 626           && heapinfo2->busy_frag.frag_size[j] > 0
 627           && !state.equals_to2_(i, j).valid) {
 628         XBT_DEBUG("Block %zu, Fragment %zu not found (size used = %zd)",
 629           i, j, heapinfo2->busy_frag.frag_size[j]);
 630         nb_diff2++;
 631       }
 632
 633   }
 634
 635   if (i1 == state.heaplimit)
 636     XBT_DEBUG("Number of blocks/fragments not found in heap2 : %d", nb_diff2);
 637
 638   return nb_diff1 > 0 || nb_diff2 > 0;
 639 }
 640
 641 /**
 642  *
 643  * @param state
 644  * @param real_area1     Process address for state 1
 645  * @param real_area2     Process address for state 2
 646  * @param snapshot1      Snapshot of state 1
 647  * @param snapshot2      Snapshot of state 2
 648  * @param previous
 649  * @param size
 650  * @param check_ignore
 651  */
 652 static int compare_heap_area_without_type(
 653   simgrid::mc::StateComparator& state, int process_index,
 654   const void *real_area1, const void *real_area2,
 655   simgrid::mc::Snapshot* snapshot1,
 656   simgrid::mc::Snapshot* snapshot2,
 657   xbt_dynar_t previous, int size,
 658   int check_ignore)
 659 {
 660   simgrid::mc::Process* process = &mc_model_checker->process();
 661   mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1);
 662   mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2);
 663
 664   for (int i = 0; i < size; ) {
 665
 666     if (check_ignore > 0) {
 667       ssize_t ignore1 = heap_comparison_ignore_size(
 668         state.processStates[0].to_ignore, (char *) real_area1 + i);
 669       if (ignore1 != -1) {
 670         ssize_t ignore2 = heap_comparison_ignore_size(
 671           state.processStates[1].to_ignore, (char *) real_area2 + i);
 672         if (ignore2 == ignore1) {
 673           if (ignore1 == 0) {
 674             check_ignore--;
 675             return 0;
 676           } else {
 677             i = i + ignore2;
 678             check_ignore--;
 679             continue;
 680           }
 681         }
 682       }
 683     }
 684
 685     if (MC_snapshot_region_memcmp(((char *) real_area1) + i, heap_region1, ((char *) real_area2) + i, heap_region2, 1) != 0) {
 686
 687       int pointer_align = (i / sizeof(void *)) * sizeof(void *);
 688       const void* addr_pointed1 = snapshot1->read(
 689         remote((void**)((char *) real_area1 + pointer_align)), process_index);
 690       const void* addr_pointed2 = snapshot2->read(
 691         remote((void**)((char *) real_area2 + pointer_align)), process_index);
 692
 693       if (process->in_maestro_stack(remote(addr_pointed1))
 694         && process->in_maestro_stack(remote(addr_pointed2))) {
 695         i = pointer_align + sizeof(void *);
 696         continue;
 697       }
 698
 699       if (addr_pointed1 > state.std_heap_copy.heapbase
 700            && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
 701            && addr_pointed2 > state.std_heap_copy.heapbase
 702            && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)) {
 703         // Both addreses are in the heap:
 704         int res_compare = compare_heap_area(state ,process_index,
 705           addr_pointed1, addr_pointed2,
 706           snapshot1, snapshot2, previous, nullptr, 0);
 707         if (res_compare == 1)
 708           return res_compare;
 709         i = pointer_align + sizeof(void *);
 710         continue;
 711       }
 712
 713       return 1;
 714     }
 715
 716     i++;
 717   }
 718
 719   return 0;
 720 }
 721
 722 /**
 723  *
 724  * @param state
 725  * @param real_area1     Process address for state 1
 726  * @param real_area2     Process address for state 2
 727  * @param snapshot1      Snapshot of state 1
 728  * @param snapshot2      Snapshot of state 2
 729  * @param previous
 730  * @param type_id
 731  * @param area_size      either a byte_size or an elements_count (?)
 732  * @param check_ignore
 733  * @param pointer_level
 734  * @return               0 (same), 1 (different), -1 (unknown)
 735  */
 736 static int compare_heap_area_with_type(
 737   simgrid::mc::StateComparator& state, int process_index,
 738   const void *real_area1, const void *real_area2,
 739   simgrid::mc::Snapshot* snapshot1,
 740   simgrid::mc::Snapshot* snapshot2,
 741   xbt_dynar_t previous, simgrid::mc::Type* type,
 742   int area_size, int check_ignore,
 743   int pointer_level)
 744 {
 745 top:
 746
 747   // HACK: This should not happen but in pratice, there are some
 748   // DW_TAG_typedef without an associated DW_AT_type:
 749   //<1><538832>: Abbrev Number: 111 (DW_TAG_typedef)
 750   //    <538833>   DW_AT_name        : (indirect string, offset: 0x2292f3): gregset_t
 751   //    <538837>   DW_AT_decl_file   : 98
 752   //    <538838>   DW_AT_decl_line   : 37
 753   if (type == nullptr)
 754     return 0;
 755
 756   if (is_stack(real_area1) && is_stack(real_area2))
 757     return 0;
 758
 759   if (check_ignore > 0) {
 760     ssize_t ignore1 = heap_comparison_ignore_size(
 761       state.processStates[0].to_ignore, real_area1);
 762     if (ignore1 > 0
 763         && heap_comparison_ignore_size(
 764           state.processStates[1].to_ignore, real_area2) == ignore1)
 765       return 0;
 766   }
 767
 768   simgrid::mc::Type *subtype, *subsubtype;
 769   int res, elm_size;
 770   const void *addr_pointed1, *addr_pointed2;
 771
 772   mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1);
 773   mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2);
 774
 775   switch (type->type) {
 776   case DW_TAG_unspecified_type:
 777     return 1;
 778
 779   case DW_TAG_base_type:
 780     if (!type->name.empty() && type->name == "char") {        /* String, hence random (arbitrary ?) size */
 781       if (real_area1 == real_area2)
 782         return -1;
 783       else
 784         return MC_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, area_size) != 0;
 785     } else {
 786       if (area_size != -1 && type->byte_size != area_size)
 787         return -1;
 788       else
 789         return MC_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, type->byte_size) != 0;
 790     }
 791     break;
 792
 793   case DW_TAG_enumeration_type:
 794     if (area_size != -1 && type->byte_size != area_size)
 795       return -1;
 796     return MC_snapshot_region_memcmp(real_area1, heap_region1, real_area2, heap_region2, type->byte_size) != 0;
 797
 798   case DW_TAG_typedef:
 799   case DW_TAG_const_type:
 800   case DW_TAG_volatile_type:
 801     // Poor man's TCO:
 802     type = type->subtype;
 803     goto top;
 804
 805   case DW_TAG_array_type:
 806     subtype = type->subtype;
 807     switch (subtype->type) {
 808     case DW_TAG_unspecified_type:
 809       return 1;
 810
 811     case DW_TAG_base_type:
 812     case DW_TAG_enumeration_type:
 813     case DW_TAG_pointer_type:
 814     case DW_TAG_reference_type:
 815     case DW_TAG_rvalue_reference_type:
 816     case DW_TAG_structure_type:
 817     case DW_TAG_class_type:
 818     case DW_TAG_union_type:
 819       if (subtype->full_type)
 820         subtype = subtype->full_type;
 821       elm_size = subtype->byte_size;
 822       break;
 823       // TODO, just remove the type indirection?
 824     case DW_TAG_const_type:
 825     case DW_TAG_typedef:
 826     case DW_TAG_volatile_type:
 827       subsubtype = subtype->subtype;
 828       if (subsubtype->full_type)
 829         subsubtype = subsubtype->full_type;
 830       elm_size = subsubtype->byte_size;
 831       break;
 832     default:
 833       return 0;
 834       break;
 835     }
 836     for (int i = 0; i < type->element_count; i++) {
 837       // TODO, add support for variable stride (DW_AT_byte_stride)
 838       res =
 839           compare_heap_area_with_type(state, process_index,
 840                                       (char *) real_area1 + (i * elm_size),
 841                                       (char *) real_area2 + (i * elm_size),
 842                                       snapshot1, snapshot2, previous,
 843                                       type->subtype, subtype->byte_size,
 844                                       check_ignore, pointer_level);
 845       if (res == 1)
 846         return res;
 847     }
 848     return 0;
 849
 850   case DW_TAG_reference_type:
 851   case DW_TAG_rvalue_reference_type:
 852   case DW_TAG_pointer_type:
 853     if (type->subtype && type->subtype->type == DW_TAG_subroutine_type) {
 854       addr_pointed1 = snapshot1->read(remote((void**)real_area1), process_index);
 855       addr_pointed2 = snapshot2->read(remote((void**)real_area2), process_index);
 856       return (addr_pointed1 != addr_pointed2);
 857     }
 858     pointer_level++;
 859     if (pointer_level <= 1) {
 860       addr_pointed1 = snapshot1->read(remote((void**)real_area1), process_index);
 861       addr_pointed2 = snapshot2->read(remote((void**)real_area2), process_index);
 862       if (addr_pointed1 > state.std_heap_copy.heapbase
 863           && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
 864           && addr_pointed2 > state.std_heap_copy.heapbase
 865           && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2))
 866         return compare_heap_area(state, process_index,
 867             addr_pointed1, addr_pointed2, snapshot1,
 868             snapshot2, previous, type->subtype,
 869             pointer_level);
 870       else
 871         return (addr_pointed1 != addr_pointed2);
 872     }
 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(state, process_index,
 886               addr_pointed1, addr_pointed2, snapshot1,
 887               snapshot2, previous, type->subtype,
 888               pointer_level);
 889       else
 890         res = (addr_pointed1 != addr_pointed2);
 891       if (res == 1)
 892         return res;
 893     }
 894     return 0;
 895
 896   case DW_TAG_structure_type:
 897   case DW_TAG_class_type:
 898     if (type->full_type)
 899       type = type->full_type;
 900     if (area_size != -1 && type->byte_size != area_size) {
 901       if (area_size <= type->byte_size || area_size % type->byte_size != 0)
 902         return -1;
 903       for (size_t i = 0; i < (size_t)(area_size / type->byte_size); i++) {
 904         int res = compare_heap_area_with_type(state, process_index,
 905                     (char *) real_area1 + i * type->byte_size,
 906                     (char *) real_area2 + i * type->byte_size,
 907                     snapshot1, snapshot2, previous, type, -1,
 908                     check_ignore, 0);
 909         if (res == 1)
 910           return res;
 911       }
 912     } else {
 913       for(simgrid::mc::Member& member : type->members) {
 914         // TODO, optimize this? (for the offset case)
 915         void *real_member1 = simgrid::dwarf::resolve_member(
 916           real_area1, type, &member, (simgrid::mc::AddressSpace*) snapshot1, process_index);
 917         void *real_member2 = simgrid::dwarf::resolve_member(
 918             real_area2, type, &member, (simgrid::mc::AddressSpace*) snapshot2, process_index);
 919         int res = compare_heap_area_with_type(
 920                     state, process_index, real_member1, real_member2,
 921                     snapshot1, snapshot2,
 922                     previous, member.type, -1,
 923                     check_ignore, 0);
 924         if (res == 1)
 925           return res;
 926       }
 927     }
 928     return 0;
 929
 930   case DW_TAG_union_type:
 931     return compare_heap_area_without_type(state, process_index, real_area1, real_area2,
 932                                           snapshot1, snapshot2, previous,
 933                                           type->byte_size, check_ignore);
 934     return 0;
 935
 936   default:
 937     return 0;
 938   }
 939
 940   xbt_die("Unreachable");
 941 }
 942
 943 /** Infer the type of a part of the block from the type of the block
 944  *
 945  * TODO, handle DW_TAG_array_type as well as arrays of the object ((*p)[5], p[5])
 946  *
 947  * TODO, handle subfields ((*p).bar.foo, (*p)[5].bar…)
 948  *
 949  * @param  type_id            DWARF type ID of the root address
 950  * @param  area_size
 951  * @return                    DWARF type ID for given offset
 952  */
 953 static simgrid::mc::Type* get_offset_type(void *real_base_address, simgrid::mc::Type* type,
 954                                  int offset, int area_size,
 955                                  simgrid::mc::Snapshot* snapshot, int process_index)
 956 {
 957
 958   // Beginning of the block, the infered variable type if the type of the block:
 959   if (offset == 0)
 960     return type;
 961
 962   switch (type->type) {
 963
 964   case DW_TAG_structure_type:
 965   case DW_TAG_class_type:
 966     if (type->full_type)
 967       type = type->full_type;
 968     if (area_size != -1 && type->byte_size != area_size) {
 969       if (area_size > type->byte_size && area_size % type->byte_size == 0)
 970         return type;
 971       else
 972         return nullptr;
 973     }
 974
 975     for(simgrid::mc::Member& member : type->members) {
 976       if (member.has_offset_location()) {
 977         // We have the offset, use it directly (shortcut):
 978         if (member.offset() == offset)
 979           return member.type;
 980       } else {
 981         void *real_member = simgrid::dwarf::resolve_member(
 982           real_base_address, type, &member, snapshot, process_index);
 983         if ((char*) real_member - (char *) real_base_address == offset)
 984           return member.type;
 985       }
 986     }
 987     return nullptr;
 988
 989   default:
 990     /* FIXME : other cases ? */
 991     return nullptr;
 992
 993   }
 994 }
 995
 996 /**
 997  *
 998  * @param area1          Process address for state 1
 999  * @param area2          Process address for state 2
1000  * @param snapshot1      Snapshot of state 1
1001  * @param snapshot2      Snapshot of state 2
1002  * @param previous       Pairs of blocks already compared on the current path (or nullptr)
1003  * @param type_id        Type of variable
1004  * @param pointer_level
1005  * @return 0 (same), 1 (different), -1
1006  */
1007 static
1008 int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
1009                       const void *area1, const void *area2,
1010                       simgrid::mc::Snapshot* snapshot1,
1011                       simgrid::mc::Snapshot* snapshot2,
1012                       xbt_dynar_t previous,
1013                       simgrid::mc::Type* type, int pointer_level)
1014 {
1015   simgrid::mc::Process* process = &mc_model_checker->process();
1016
1017   int res_compare;
1018   ssize_t block1, frag1, block2, frag2;
1019   ssize_t size;
1020   int check_ignore = 0;
1021
1022   void *real_addr_block1, *real_addr_block2, *real_addr_frag1, *real_addr_frag2;
1023   int type_size = -1;
1024   int offset1 = 0, offset2 = 0;
1025   int new_size1 = -1, new_size2 = -1;
1026   simgrid::mc::Type *new_type1 = nullptr, *new_type2 = nullptr;
1027
1028   int match_pairs = 0;
1029
1030   // This is the address of std_heap->heapinfo in the application process:
1031   void* heapinfo_address = &((xbt_mheap_t) process->heap_address)->heapinfo;
1032
1033   const malloc_info* heapinfos1 = snapshot1->read(
1034     remote((const malloc_info**)heapinfo_address), process_index);
1035   const malloc_info* heapinfos2 = snapshot2->read(
1036     remote((const malloc_info**)heapinfo_address), process_index);
1037
1038   malloc_info heapinfo_temp1, heapinfo_temp2;
1039
1040   if (previous == nullptr) {
1041     previous = xbt_dynar_new(sizeof(simgrid::mc::HeapLocationPair*), [](void *d) {
1042       xbt_free((simgrid::mc::HeapLocationPair*) * (void **) d); });
1043     match_pairs = 1;
1044   }
1045
1046   // Get block number:
1047   block1 =
1048       ((char *) area1 -
1049        (char *) state.std_heap_copy.heapbase) / BLOCKSIZE + 1;
1050   block2 =
1051       ((char *) area2 -
1052        (char *) state.std_heap_copy.heapbase) / BLOCKSIZE + 1;
1053
1054   // If either block is a stack block:
1055   if (is_block_stack((int) block1) && is_block_stack((int) block2)) {
1056     add_heap_area_pair(previous, block1, -1, block2, -1);
1057     if (match_pairs) {
1058       state.match_equals(previous);
1059       xbt_dynar_free(&previous);
1060     }
1061     return 0;
1062   }
1063
1064   // If either block is not in the expected area of memory:
1065   if (((char *) area1 < (char *) state.std_heap_copy.heapbase)
1066       || (block1 > (ssize_t) state.processStates[0].heapsize) || (block1 < 1)
1067       || ((char *) area2 < (char *) state.std_heap_copy.heapbase)
1068       || (block2 > (ssize_t) state.processStates[1].heapsize) || (block2 < 1)) {
1069     if (match_pairs)
1070       xbt_dynar_free(&previous);
1071     return 1;
1072   }
1073
1074   // Process address of the block:
1075   real_addr_block1 = (ADDR2UINT(block1) - 1) * BLOCKSIZE +
1076                  (char *) state.std_heap_copy.heapbase;
1077   real_addr_block2 = (ADDR2UINT(block2) - 1) * BLOCKSIZE +
1078                  (char *) state.std_heap_copy.heapbase;
1079
1080   if (type) {
1081
1082     if (type->full_type)
1083       type = type->full_type;
1084
1085     // This assume that for "boring" types (volatile ...) byte_size is absent:
1086     while (type->byte_size == 0 && type->subtype != nullptr)
1087       type = type->subtype;
1088
1089     // Find type_size:
1090     if (type->type == DW_TAG_pointer_type
1091         || (type->type == DW_TAG_base_type && !type->name.empty()
1092             && type->name == "char"))
1093       type_size = -1;
1094     else
1095       type_size = type->byte_size;
1096
1097   }
1098
1099   mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1);
1100   mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2);
1101
1102   const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read(
1103     heap_region1, &heapinfo_temp1, &heapinfos1[block1], sizeof(malloc_info));
1104   const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read(
1105     heap_region2, &heapinfo_temp2, &heapinfos2[block2], sizeof(malloc_info));
1106
1107   if ((heapinfo1->type == MMALLOC_TYPE_FREE || heapinfo1->type==MMALLOC_TYPE_HEAPINFO)
1108     && (heapinfo2->type == MMALLOC_TYPE_FREE || heapinfo2->type ==MMALLOC_TYPE_HEAPINFO)) {
1109     /* Free block */
1110     if (match_pairs) {
1111       state.match_equals(previous);
1112       xbt_dynar_free(&previous);
1113     }
1114     return 0;
1115   }
1116
1117   if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED
1118     && heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED) {
1119     /* Complete block */
1120
1121     // TODO, lookup variable type from block type as done for fragmented blocks
1122
1123     offset1 = (char *) area1 - (char *) real_addr_block1;
1124     offset2 = (char *) area2 - (char *) real_addr_block2;
1125
1126     if (state.equals_to1_(block1, 0).valid
1127         && state.equals_to2_(block2, 0).valid
1128         && state.blocksEqual(block1, block2)) {
1129       if (match_pairs) {
1130         state.match_equals(previous);
1131         xbt_dynar_free(&previous);
1132       }
1133       return 0;
1134     }
1135
1136     if (type_size != -1) {
1137       if (type_size != (ssize_t) heapinfo1->busy_block.busy_size
1138           && type_size != (ssize_t)   heapinfo2->busy_block.busy_size
1139           && (type->name.empty() || type->name == "struct s_smx_context")) {
1140         if (match_pairs) {
1141           state.match_equals(previous);
1142           xbt_dynar_free(&previous);
1143         }
1144         return -1;
1145       }
1146     }
1147
1148     if (heapinfo1->busy_block.size != heapinfo2->busy_block.size) {
1149       if (match_pairs)
1150         xbt_dynar_free(&previous);
1151       return 1;
1152     }
1153
1154     if (heapinfo1->busy_block.busy_size != heapinfo2->busy_block.busy_size) {
1155       if (match_pairs)
1156         xbt_dynar_free(&previous);
1157       return 1;
1158     }
1159
1160     if (!add_heap_area_pair(previous, block1, -1, block2, -1)) {
1161       if (match_pairs) {
1162         state.match_equals(previous);
1163         xbt_dynar_free(&previous);
1164       }
1165       return 0;
1166     }
1167
1168     size = heapinfo1->busy_block.busy_size;
1169
1170     // Remember (basic) type inference.
1171     // The current data structure only allows us to do this for the whole block.
1172     if (type != nullptr && area1 == real_addr_block1)
1173       state.types1_(block1, 0) = type;
1174     if (type != nullptr && area2 == real_addr_block2)
1175       state.types2_(block2, 0) = type;
1176
1177     if (size <= 0) {
1178       if (match_pairs) {
1179         state.match_equals(previous);
1180         xbt_dynar_free(&previous);
1181       }
1182       return 0;
1183     }
1184
1185     frag1 = -1;
1186     frag2 = -1;
1187
1188     if (heapinfo1->busy_block.ignore > 0
1189         && heapinfo2->busy_block.ignore == heapinfo1->busy_block.ignore)
1190       check_ignore = heapinfo1->busy_block.ignore;
1191
1192   } else if ((heapinfo1->type > 0) && (heapinfo2->type > 0)) {      /* Fragmented block */
1193
1194     // Fragment number:
1195     frag1 =
1196         ((uintptr_t) (ADDR2UINT(area1) % (BLOCKSIZE))) >> heapinfo1->type;
1197     frag2 =
1198         ((uintptr_t) (ADDR2UINT(area2) % (BLOCKSIZE))) >> heapinfo2->type;
1199
1200     // Process address of the fragment:
1201     real_addr_frag1 =
1202         (void *) ((char *) real_addr_block1 +
1203                   (frag1 << heapinfo1->type));
1204     real_addr_frag2 =
1205         (void *) ((char *) real_addr_block2 +
1206                   (frag2 << heapinfo2->type));
1207
1208     // Check the size of the fragments against the size of the type:
1209     if (type_size != -1) {
1210       if (heapinfo1->busy_frag.frag_size[frag1] == -1
1211           || heapinfo2->busy_frag.frag_size[frag2] == -1) {
1212         if (match_pairs) {
1213           state.match_equals(previous);
1214           xbt_dynar_free(&previous);
1215         }
1216         return -1;
1217       }
1218       // ?
1219       if (type_size != heapinfo1->busy_frag.frag_size[frag1]
1220           || type_size != heapinfo2->busy_frag.frag_size[frag2]) {
1221         if (match_pairs) {
1222           state.match_equals(previous);
1223           xbt_dynar_free(&previous);
1224         }
1225         return -1;
1226       }
1227     }
1228
1229     // Check if the blocks are already matched together:
1230     if (state.equals_to1_(block1, frag1).valid
1231         && state.equals_to2_(block2, frag2).valid) {
1232       if (offset1==offset2 && state.fragmentsEqual(block1, frag1, block2, frag2)) {
1233         if (match_pairs) {
1234           state.match_equals(previous);
1235           xbt_dynar_free(&previous);
1236         }
1237         return 0;
1238       }
1239     }
1240     // Compare the size of both fragments:
1241     if (heapinfo1->busy_frag.frag_size[frag1] !=
1242         heapinfo2->busy_frag.frag_size[frag2]) {
1243       if (type_size == -1) {
1244         if (match_pairs) {
1245           state.match_equals(previous);
1246           xbt_dynar_free(&previous);
1247         }
1248         return -1;
1249       } else {
1250         if (match_pairs)
1251           xbt_dynar_free(&previous);
1252         return 1;
1253       }
1254     }
1255
1256     // Size of the fragment:
1257     size = heapinfo1->busy_frag.frag_size[frag1];
1258
1259     // Remember (basic) type inference.
1260     // The current data structure only allows us to do this for the whole fragment.
1261     if (type != nullptr && area1 == real_addr_frag1)
1262       state.types1_(block1, frag1) = type;
1263     if (type != nullptr && area2 == real_addr_frag2)
1264       state.types2_(block2, frag2) = type;
1265
1266     // The type of the variable is already known:
1267     if (type) {
1268       new_type1 = type;
1269       new_type2 = type;
1270     }
1271     // Type inference from the block type.
1272     else if (state.types1_(block1, frag1) != nullptr
1273              || state.types2_(block2, frag2) != nullptr) {
1274
1275       offset1 = (char *) area1 - (char *) real_addr_frag1;
1276       offset2 = (char *) area2 - (char *) real_addr_frag2;
1277
1278       if (state.types1_(block1, frag1) != nullptr
1279           && state.types2_(block2, frag2) != nullptr) {
1280         new_type1 =
1281             get_offset_type(real_addr_frag1, state.types1_(block1, frag1),
1282                             offset1, size, snapshot1, process_index);
1283         new_type2 =
1284             get_offset_type(real_addr_frag2, state.types2_(block2, frag2),
1285                             offset1, size, snapshot2, process_index);
1286       } else if (state.types1_(block1, frag1) != nullptr) {
1287         new_type1 =
1288             get_offset_type(real_addr_frag1, state.types1_(block1, frag1),
1289                             offset1, size, snapshot1, process_index);
1290         new_type2 =
1291             get_offset_type(real_addr_frag2, state.types1_(block1, frag1),
1292                             offset2, size, snapshot2, process_index);
1293       } else if (state.types2_(block2, frag2) != nullptr) {
1294         new_type1 =
1295             get_offset_type(real_addr_frag1, state.types2_(block2, frag2),
1296                             offset1, size, snapshot1, process_index);
1297         new_type2 =
1298             get_offset_type(real_addr_frag2, state.types2_(block2, frag2),
1299                             offset2, size, snapshot2, process_index);
1300       } else {
1301         if (match_pairs) {
1302           state.match_equals(previous);
1303           xbt_dynar_free(&previous);
1304         }
1305         return -1;
1306       }
1307
1308       if (new_type1 != nullptr && new_type2 != nullptr && new_type1 != new_type2) {
1309
1310         type = new_type1;
1311         while (type->byte_size == 0 && type->subtype != nullptr)
1312           type = type->subtype;
1313         new_size1 = type->byte_size;
1314
1315         type = new_type2;
1316         while (type->byte_size == 0 && type->subtype != nullptr)
1317           type = type->subtype;
1318         new_size2 = type->byte_size;
1319
1320       } else {
1321         if (match_pairs) {
1322           state.match_equals(previous);
1323           xbt_dynar_free(&previous);
1324         }
1325         return -1;
1326       }
1327     }
1328
1329     if (new_size1 > 0 && new_size1 == new_size2) {
1330       type = new_type1;
1331       size = new_size1;
1332     }
1333
1334     if (offset1 == 0 && offset2 == 0
1335       && !add_heap_area_pair(previous, block1, frag1, block2, frag2)) {
1336         if (match_pairs) {
1337           state.match_equals(previous);
1338           xbt_dynar_free(&previous);
1339         }
1340         return 0;
1341       }
1342
1343     if (size <= 0) {
1344       if (match_pairs) {
1345         state.match_equals(previous);
1346         xbt_dynar_free(&previous);
1347       }
1348       return 0;
1349     }
1350
1351     if ((heapinfo1->busy_frag.ignore[frag1] > 0)
1352         && (heapinfo2->busy_frag.ignore[frag2] ==
1353             heapinfo1->busy_frag.ignore[frag1]))
1354       check_ignore = heapinfo1->busy_frag.ignore[frag1];
1355
1356   } else {
1357     if (match_pairs)
1358       xbt_dynar_free(&previous);
1359     return 1;
1360   }
1361
1362
1363   /* Start comparison */
1364   if (type)
1365     res_compare =
1366         compare_heap_area_with_type(state, process_index, area1, area2, snapshot1, snapshot2,
1367                                     previous, type, size, check_ignore,
1368                                     pointer_level);
1369   else
1370     res_compare =
1371         compare_heap_area_without_type(state, process_index, area1, area2, snapshot1, snapshot2,
1372                                        previous, size, check_ignore);
1373
1374   if (res_compare == 1) {
1375     if (match_pairs)
1376       xbt_dynar_free(&previous);
1377     return res_compare;
1378   }
1379
1380   if (match_pairs) {
1381     state.match_equals(previous);
1382     xbt_dynar_free(&previous);
1383   }
1384
1385   return 0;
1386 }
1387
1388 }
1389 }
1390
1391 /************************** Snapshot comparison *******************************/
1392 /******************************************************************************/
1393
1394 static int compare_areas_with_type(simgrid::mc::StateComparator& state,
1395                                    int process_index,
1396                                    void* real_area1, simgrid::mc::Snapshot* snapshot1, mc_mem_region_t region1,
1397                                    void* real_area2, simgrid::mc::Snapshot* snapshot2, mc_mem_region_t region2,
1398                                    simgrid::mc::Type* type, int pointer_level)
1399 {
1400   simgrid::mc::Process* process = &mc_model_checker->process();
1401
1402   simgrid::mc::Type* subtype;
1403   simgrid::mc::Type* subsubtype;
1404   int elm_size, i, res;
1405
1406   top:
1407   switch (type->type) {
1408   case DW_TAG_unspecified_type:
1409     return 1;
1410
1411   case DW_TAG_base_type:
1412   case DW_TAG_enumeration_type:
1413   case DW_TAG_union_type:
1414   {
1415     return MC_snapshot_region_memcmp(
1416       real_area1, region1, real_area2, region2,
1417       type->byte_size) != 0;
1418   }
1419   case DW_TAG_typedef:
1420   case DW_TAG_volatile_type:
1421   case DW_TAG_const_type:
1422     // Poor man's TCO:
1423     type = type->subtype;
1424     goto top;
1425   case DW_TAG_array_type:
1426     subtype = type->subtype;
1427     switch (subtype->type) {
1428     case DW_TAG_unspecified_type:
1429       return 1;
1430
1431     case DW_TAG_base_type:
1432     case DW_TAG_enumeration_type:
1433     case DW_TAG_pointer_type:
1434     case DW_TAG_reference_type:
1435     case DW_TAG_rvalue_reference_type:
1436     case DW_TAG_structure_type:
1437     case DW_TAG_class_type:
1438     case DW_TAG_union_type:
1439       if (subtype->full_type)
1440         subtype = subtype->full_type;
1441       elm_size = subtype->byte_size;
1442       break;
1443     case DW_TAG_const_type:
1444     case DW_TAG_typedef:
1445     case DW_TAG_volatile_type:
1446       subsubtype = subtype->subtype;
1447       if (subsubtype->full_type)
1448         subsubtype = subsubtype->full_type;
1449       elm_size = subsubtype->byte_size;
1450       break;
1451     default:
1452       return 0;
1453       break;
1454     }
1455     for (i = 0; i < type->element_count; i++) {
1456       size_t off = i * elm_size;
1457       res = compare_areas_with_type(state, process_index,
1458             (char*) real_area1 + off, snapshot1, region1,
1459             (char*) real_area2 + off, snapshot2, region2,
1460             type->subtype, pointer_level);
1461       if (res == 1)
1462         return res;
1463     }
1464     break;
1465   case DW_TAG_pointer_type:
1466   case DW_TAG_reference_type:
1467   case DW_TAG_rvalue_reference_type:
1468   {
1469     void* addr_pointed1 = MC_region_read_pointer(region1, real_area1);
1470     void* addr_pointed2 = MC_region_read_pointer(region2, real_area2);
1471
1472     if (type->subtype && type->subtype->type == DW_TAG_subroutine_type)
1473       return (addr_pointed1 != addr_pointed2);
1474     if (addr_pointed1 == nullptr && addr_pointed2 == nullptr)
1475       return 0;
1476     if (addr_pointed1 == nullptr || addr_pointed2 == nullptr)
1477       return 1;
1478     if (!state.compared_pointers.insert(
1479         std::make_pair(addr_pointed1, addr_pointed2)).second)
1480       return 0;
1481
1482     pointer_level++;
1483
1484       // Some cases are not handled here:
1485       // * the pointers lead to different areas (one to the heap, the other to the RW segment ...);
1486       // * a pointer leads to the read-only segment of the current object;
1487       // * a pointer lead to a different ELF object.
1488
1489       if (addr_pointed1 > process->heap_address
1490           && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)) {
1491         if (!
1492             (addr_pointed2 > process->heap_address
1493              && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)))
1494           return 1;
1495         // The pointers are both in the heap:
1496         return simgrid::mc::compare_heap_area(state,
1497           process_index, addr_pointed1, addr_pointed2, snapshot1,
1498           snapshot2, nullptr, type->subtype, pointer_level);
1499       }
1500
1501       // The pointers are both in the current object R/W segment:
1502       else if (region1->contain(simgrid::mc::remote(addr_pointed1))) {
1503         if (!region2->contain(simgrid::mc::remote(addr_pointed2)))
1504           return 1;
1505         if (!type->type_id)
1506           return (addr_pointed1 != addr_pointed2);
1507         else
1508           return compare_areas_with_type(state, process_index,
1509                                          addr_pointed1, snapshot1, region1,
1510                                          addr_pointed2, snapshot2, region2,
1511                                          type->subtype, pointer_level);
1512       }
1513
1514       // TODO, We do not handle very well the case where
1515       // it belongs to a different (non-heap) region from the current one.
1516
1517       else
1518         return (addr_pointed1 != addr_pointed2);
1519
1520     break;
1521   }
1522   case DW_TAG_structure_type:
1523   case DW_TAG_class_type:
1524     for(simgrid::mc::Member& member : type->members) {
1525       void *member1 = simgrid::dwarf::resolve_member(
1526         real_area1, type, &member, snapshot1, process_index);
1527       void *member2 = simgrid::dwarf::resolve_member(
1528         real_area2, type, &member, snapshot2, process_index);
1529       mc_mem_region_t subregion1 = mc_get_region_hinted(member1, snapshot1, process_index, region1);
1530       mc_mem_region_t subregion2 = mc_get_region_hinted(member2, snapshot2, process_index, region2);
1531       res =
1532           compare_areas_with_type(state, process_index,
1533                                   member1, snapshot1, subregion1,
1534                                   member2, snapshot2, subregion2,
1535                                   member.type, pointer_level);
1536       if (res == 1)
1537         return res;
1538     }
1539     break;
1540   case DW_TAG_subroutine_type:
1541     return -1;
1542     break;
1543   default:
1544     XBT_VERB("Unknown case : %d", type->type);
1545     break;
1546   }
1547
1548   return 0;
1549 }
1550
1551 static int compare_global_variables(
1552   simgrid::mc::StateComparator& state,
1553   simgrid::mc::ObjectInformation* object_info,
1554   int process_index,
1555   mc_mem_region_t r1, mc_mem_region_t r2,
1556   simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2)
1557 {
1558   xbt_assert(r1 && r2, "Missing region.");
1559
1560 #if HAVE_SMPI
1561   if (r1->storage_type() == simgrid::mc::StorageType::Privatized) {
1562     xbt_assert(process_index >= 0);
1563     if (r2->storage_type() != simgrid::mc::StorageType::Privatized)
1564       return 1;
1565
1566     size_t process_count = MC_smpi_process_count();
1567     xbt_assert(process_count == r1->privatized_data().size()
1568       && process_count == r2->privatized_data().size());
1569
1570     // Compare the global variables separately for each simulates process:
1571     for (size_t process_index = 0; process_index < process_count; process_index++) {
1572       int is_diff = compare_global_variables(state,
1573         object_info, process_index,
1574         &r1->privatized_data()[process_index],
1575         &r2->privatized_data()[process_index],
1576         snapshot1, snapshot2);
1577       if (is_diff) return 1;
1578     }
1579     return 0;
1580   }
1581 #else
1582   xbt_assert(r1->storage_type() != simgrid::mc::StorageType::Privatized);
1583 #endif
1584   xbt_assert(r2->storage_type() != simgrid::mc::StorageType::Privatized);
1585
1586   std::vector<simgrid::mc::Variable>& variables = object_info->global_variables;
1587
1588   for (simgrid::mc::Variable& current_var : variables) {
1589
1590     // If the variable is not in this object, skip it:
1591     // We do not expect to find a pointer to something which is not reachable
1592     // by the global variables.
1593     if ((char *) current_var.address < (char *) object_info->start_rw
1594         || (char *) current_var.address > (char *) object_info->end_rw)
1595       continue;
1596
1597     simgrid::mc::Type* bvariable_type = current_var.type;
1598     int res = compare_areas_with_type(state, process_index,
1599                                 (char *) current_var.address, snapshot1, r1,
1600                                 (char *) current_var.address, snapshot2, r2,
1601                                 bvariable_type, 0);
1602     if (res == 1) {
1603       XBT_VERB("Global variable %s (%p) is different between snapshots",
1604                current_var.name.c_str(),
1605                (char *) current_var.address);
1606       return 1;
1607     }
1608
1609   }
1610
1611   return 0;
1612
1613 }
1614
1615 static int compare_local_variables(simgrid::mc::StateComparator& state,
1616                                    int process_index,
1617                                    simgrid::mc::Snapshot* snapshot1,
1618                                    simgrid::mc::Snapshot* snapshot2,
1619                                    mc_snapshot_stack_t stack1,
1620                                    mc_snapshot_stack_t stack2)
1621 {
1622   if (stack1->local_variables.size() != stack2->local_variables.size()) {
1623     XBT_VERB("Different number of local variables");
1624     return 1;
1625   }
1626
1627     unsigned int cursor = 0;
1628     local_variable_t current_var1, current_var2;
1629     int res;
1630     while (cursor < stack1->local_variables.size()) {
1631       current_var1 = &stack1->local_variables[cursor];
1632       current_var2 = &stack1->local_variables[cursor];
1633       if (current_var1->name != current_var2->name
1634           || current_var1->subprogram != current_var2->subprogram
1635           || current_var1->ip != current_var2->ip) {
1636         // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram
1637         XBT_VERB
1638             ("Different name of variable (%s - %s) "
1639              "or frame (%s - %s) or ip (%lu - %lu)",
1640              current_var1->name.c_str(),
1641              current_var2->name.c_str(),
1642              current_var1->subprogram->name.c_str(),
1643              current_var2->subprogram->name.c_str(),
1644              current_var1->ip, current_var2->ip);
1645         return 1;
1646       }
1647       // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram
1648
1649         simgrid::mc::Type* subtype = current_var1->type;
1650         res =
1651             compare_areas_with_type(state, process_index,
1652                                     current_var1->address, snapshot1, mc_get_snapshot_region(current_var1->address, snapshot1, process_index),
1653                                     current_var2->address, snapshot2, mc_get_snapshot_region(current_var2->address, snapshot2, process_index),
1654                                     subtype, 0);
1655
1656       if (res == 1) {
1657         // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram
1658         XBT_VERB
1659             ("Local variable %s (%p - %p) in frame %s "
1660              "is different between snapshots",
1661              current_var1->name.c_str(),
1662              current_var1->address,
1663              current_var2->address,
1664              current_var1->subprogram->name.c_str());
1665         return res;
1666       }
1667       cursor++;
1668     }
1669     return 0;
1670 }
1671
1672 namespace simgrid {
1673 namespace mc {
1674
1675 static std::unique_ptr<simgrid::mc::StateComparator> state_comparator;
1676
1677 int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc::Snapshot* s2)
1678 {
1679   // TODO, make this a field of ModelChecker or something similar
1680
1681   if (state_comparator == nullptr)
1682     state_comparator = std::unique_ptr<StateComparator>(new StateComparator());
1683   else
1684     state_comparator->clear();
1685
1686   simgrid::mc::Process* process = &mc_model_checker->process();
1687
1688   int errors = 0;
1689   int res_init;
1690
1691   int hash_result = 0;
1692   if (_sg_mc_hash) {
1693     hash_result = (s1->hash != s2->hash);
1694     if (hash_result) {
1695       XBT_VERB("(%d - %d) Different hash : 0x%" PRIx64 "--0x%" PRIx64, num1,
1696                num2, s1->hash, s2->hash);
1697 #ifndef MC_DEBUG
1698       return 1;
1699 #endif
1700     } else
1701       XBT_VERB("(%d - %d) Same hash : 0x%" PRIx64, num1, num2, s1->hash);
1702   }
1703
1704   /* Compare enabled processes */
1705   if (s1->enabled_processes != s2->enabled_processes) {
1706       XBT_VERB("(%d - %d) Different enabled processes", num1, num2);
1707       // return 1; ??
1708   }
1709
1710   unsigned long i = 0;
1711   size_t size_used1, size_used2;
1712   int is_diff = 0;
1713
1714   /* Compare size of stacks */
1715   while (i < s1->stacks.size()) {
1716     size_used1 = s1->stack_sizes[i];
1717     size_used2 = s2->stack_sizes[i];
1718     if (size_used1 != size_used2) {
1719 #ifdef MC_DEBUG
1720       XBT_DEBUG("(%d - %d) Different size used in stacks : %zu - %zu", num1,
1721                 num2, size_used1, size_used2);
1722       errors++;
1723       is_diff = 1;
1724 #else
1725 #ifdef MC_VERBOSE
1726       XBT_VERB("(%d - %d) Different size used in stacks : %zu - %zu", num1,
1727                num2, size_used1, size_used2);
1728 #endif
1729       return 1;
1730 #endif
1731     }
1732     i++;
1733   }
1734
1735   /* Init heap information used in heap comparison algorithm */
1736   xbt_mheap_t heap1 = (xbt_mheap_t)s1->read_bytes(
1737     alloca(sizeof(struct mdesc)), sizeof(struct mdesc),
1738     remote(process->heap_address),
1739     simgrid::mc::ProcessIndexMissing, simgrid::mc::ReadOptions::lazy());
1740   xbt_mheap_t heap2 = (xbt_mheap_t)s2->read_bytes(
1741     alloca(sizeof(struct mdesc)), sizeof(struct mdesc),
1742     remote(process->heap_address),
1743     simgrid::mc::ProcessIndexMissing, simgrid::mc::ReadOptions::lazy());
1744   res_init = state_comparator->initHeapInformation(
1745     heap1, heap2, &s1->to_ignore, &s2->to_ignore);
1746
1747   if (res_init == -1) {
1748 #ifdef MC_DEBUG
1749     XBT_DEBUG("(%d - %d) Different heap information", num1, num2);
1750     errors++;
1751 #else
1752 #ifdef MC_VERBOSE
1753     XBT_VERB("(%d - %d) Different heap information", num1, num2);
1754 #endif
1755
1756     return 1;
1757 #endif
1758   }
1759
1760   /* Stacks comparison */
1761   unsigned cursor = 0;
1762   int diff_local = 0;
1763 #ifdef MC_DEBUG
1764   is_diff = 0;
1765 #endif
1766   mc_snapshot_stack_t stack1, stack2;
1767   while (cursor < s1->stacks.size()) {
1768     stack1 = &s1->stacks[cursor];
1769     stack2 = &s2->stacks[cursor];
1770
1771     if (stack1->process_index != stack2->process_index) {
1772       diff_local = 1;
1773       XBT_DEBUG("(%d - %d) Stacks with different process index (%i vs %i)", num1, num2,
1774         stack1->process_index, stack2->process_index);
1775     }
1776     else diff_local = compare_local_variables(*state_comparator,
1777       stack1->process_index, s1, s2, stack1, stack2);
1778     if (diff_local > 0) {
1779 #ifdef MC_DEBUG
1780       XBT_DEBUG("(%d - %d) Different local variables between stacks %d", num1,
1781                 num2, cursor + 1);
1782       errors++;
1783       is_diff = 1;
1784 #else
1785
1786 #ifdef MC_VERBOSE
1787       XBT_VERB("(%d - %d) Different local variables between stacks %d", num1,
1788                num2, cursor + 1);
1789 #endif
1790
1791       return 1;
1792 #endif
1793     }
1794     cursor++;
1795   }
1796
1797   size_t regions_count = s1->snapshot_regions.size();
1798   // TODO, raise a difference instead?
1799   xbt_assert(regions_count == s2->snapshot_regions.size());
1800
1801   for (size_t k = 0; k != regions_count; ++k) {
1802     mc_mem_region_t region1 = s1->snapshot_regions[k].get();
1803     mc_mem_region_t region2 = s2->snapshot_regions[k].get();
1804
1805     // Preconditions:
1806     if (region1->region_type() != simgrid::mc::RegionType::Data)
1807       continue;
1808
1809     xbt_assert(region1->region_type() == region2->region_type());
1810     xbt_assert(region1->object_info() == region2->object_info());
1811     xbt_assert(region1->object_info());
1812
1813     std::string const& name = region1->object_info()->file_name;
1814
1815     /* Compare global variables */
1816     is_diff =
1817       compare_global_variables(*state_comparator,
1818         region1->object_info(), simgrid::mc::ProcessIndexDisabled,
1819         region1, region2, s1, s2);
1820
1821     if (is_diff != 0) {
1822 #ifdef MC_DEBUG
1823       XBT_DEBUG("(%d - %d) Different global variables in %s",
1824         num1, num2, name.c_str());
1825       errors++;
1826 #else
1827 #ifdef MC_VERBOSE
1828       XBT_VERB("(%d - %d) Different global variables in %s",
1829         num1, num2, name.c_str());
1830 #endif
1831
1832       return 1;
1833 #endif
1834     }
1835   }
1836
1837   /* Compare heap */
1838   if (simgrid::mc::mmalloc_compare_heap(*state_comparator, s1, s2) > 0) {
1839
1840 #ifdef MC_DEBUG
1841     XBT_DEBUG("(%d - %d) Different heap (mmalloc_compare)", num1, num2);
1842     errors++;
1843 #else
1844
1845 #ifdef MC_VERBOSE
1846     XBT_VERB("(%d - %d) Different heap (mmalloc_compare)", num1, num2);
1847 #endif
1848
1849     return 1;
1850 #endif
1851   }
1852
1853 #ifdef MC_VERBOSE
1854   if (errors || hash_result)
1855     XBT_VERB("(%d - %d) Difference found", num1, num2);
1856   else
1857     XBT_VERB("(%d - %d) No difference found", num1, num2);
1858 #endif
1859
1860 #if defined(MC_DEBUG) && defined(MC_VERBOSE)
1861   if (_sg_mc_hash) {
1862     // * false positive SHOULD be avoided.
1863     // * There MUST not be any false negative.
1864
1865     XBT_VERB("(%d - %d) State equality hash test is %s %s", num1, num2,
1866              (hash_result != 0) == (errors != 0) ? "true" : "false",
1867              !hash_result ? "positive" : "negative");
1868   }
1869 #endif
1870
1871   return errors > 0 || hash_result;
1872 }
1873
1874 }
1875 }