src/mc/compare.cpp

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