Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
cut some more includes
[simgrid.git] / src / mc / compare.cpp
index d2a3001..bdc2339 100644 (file)
@@ -1,20 +1,20 @@
-/* Copyright (c) 2008-2016. The SimGrid Team.
- * All rights reserved.                                                     */
+/* Copyright (c) 2008-2017. The SimGrid Team. All rights reserved.          */
 
 /* This program is free software; you can redistribute it and/or modify it
  * under the terms of the license (GNU LGPL) which comes with this package. */
 
-/** \file mc_compare.cpp Memory snapshooting and comparison                 */
+/** \file compare.cpp Memory snapshooting and comparison                    */
 
 #include <cinttypes>
 
 #include <array>
 #include <memory>
+#include <set>
 #include <utility>
 #include <unordered_set>
 
-#include <xbt/sysdep.h>
-#include <xbt/dynar.h>
+#include "xbt/dynar.h"
+#include "xbt/sysdep.h"
 #include <xbt/mmalloc.h>
 
 #include <mc/mc.h>
 #include "src/internal_config.h"
 
 #include "src/xbt/mmalloc/mmprivate.h"
-#include "src/xbt/ex_interface.h"
 
 #if HAVE_SMPI
 #include "src/smpi/private.h"
 #endif
 
 #include "src/mc/mc_forward.hpp"
-#include "src/mc/mc_safety.h"
 #include "src/mc/mc_private.h"
 #include "src/mc/mc_smx.h"
 #include "src/mc/mc_dwarf.hpp"
 #include "src/mc/mc_dwarf.hpp"
 #include "src/mc/Type.hpp"
 
-XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt,
-                                "Logging specific to mc_compare in mc");
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt, "Logging specific to mc_compare in mc");
 
 namespace simgrid {
 namespace mc {
 
+struct HeapLocation;
+typedef std::array<HeapLocation, 2> HeapLocationPair;
+typedef std::set<HeapLocationPair> HeapLocationPairs;
+struct HeapArea;
 struct ProcessComparisonState;
 struct StateComparator;
 
 static int compare_heap_area(
+  StateComparator& state,
   int process_index, const void *area1, const void* area2,
   Snapshot* snapshot1, Snapshot* snapshot2,
-  xbt_dynar_t previous, Type* type, int pointer_level);
-
-static void reset_heap_information(void);
+  HeapLocationPairs* previous, Type* type, int pointer_level);
 
 }
 }
@@ -72,18 +72,37 @@ namespace mc {
 struct HeapLocation {
   int block = 0;
   int fragment = 0;
+
   HeapLocation() {}
   HeapLocation(int block, int fragment = 0) : block(block), fragment(fragment) {}
+
+  bool operator==(HeapLocation const& that) const
+  {
+    return block == that.block && fragment == that.fragment;
+  }
+  bool operator<(HeapLocation const& that) const
+  {
+    return std::make_pair(block, fragment)
+      < std::make_pair(that.block, that.fragment);
+  }
 };
 
-typedef std::array<HeapLocation, 2> HeapLocationPair;
+static inline
+HeapLocationPair makeHeapLocationPair(int block1, int fragment1, int block2, int fragment2)
+{
+  return simgrid::mc::HeapLocationPair{{
+    simgrid::mc::HeapLocation(block1, fragment1),
+    simgrid::mc::HeapLocation(block2, fragment2)
+  }};
+}
 
-struct HeapArea {
+struct HeapArea : public HeapLocation {
   bool valid = false;
   int block = 0;
   int fragment = 0;
-
   HeapArea() {}
+  HeapArea(int block)
+    : valid(true), block(block) {}
   HeapArea(int block, int fragment = 0)
     : valid(true), block(block), fragment(fragment) {}
 };
@@ -94,15 +113,42 @@ struct ProcessComparisonState {
   std::vector<simgrid::mc::Type*> types;
   std::size_t heapsize = 0;
 
-  void initHeapInformation(xbt_mheap_t heap,
-                          std::vector<simgrid::mc::IgnoredHeapRegion>* i);
+  void initHeapInformation(xbt_mheap_t heap, std::vector<simgrid::mc::IgnoredHeapRegion>* i);
+};
+
+namespace {
+
+/** A hash which works with more stuff
+ *
+ *  It can hash pairs: the standard hash currently doesn't include this.
+ */
+template<class X> struct hash : public std::hash<X> {};
+
+template<class X, class Y>
+struct hash<std::pair<X,Y>> {
+  std::size_t operator()(std::pair<X,Y>const& x) const
+  {
+    struct hash<X> h1;
+    struct hash<X> h2;
+    return h1(x.first) ^ h2(x.second);
+  }
 };
 
+}
+
+
 struct StateComparator {
   s_xbt_mheap_t std_heap_copy;
   std::size_t heaplimit;
   std::array<ProcessComparisonState, 2> processStates;
 
+  std::unordered_set<std::pair<void*, void*>, hash<std::pair<void*, void*>>> compared_pointers;
+
+  void clear()
+  {
+    compared_pointers.clear();
+  }
+
   int initHeapInformation(
     xbt_mheap_t heap1, xbt_mheap_t heap2,
     std::vector<simgrid::mc::IgnoredHeapRegion>* i1,
@@ -144,7 +190,6 @@ struct StateComparator {
 
   /** Check whether two blocks are known to be matching
    *
-   *  @param state  State used
    *  @param b1     Block of state 1
    *  @param b2     Block of state 2
    *  @return       if the blocks are known to be matching
@@ -157,7 +202,6 @@ struct StateComparator {
 
   /** Check whether two fragments are known to be matching
    *
-   *  @param state  State used
    *  @param b1     Block of state 1
    *  @param f1     Fragment of state 1
    *  @param b2     Block of state 2
@@ -172,46 +216,14 @@ struct StateComparator {
         && this->equals_to2_(b2, f2).fragment == f1;
   }
 
-  void match_equals(xbt_dynar_t list);
+  void match_equals(HeapLocationPairs* list);
 };
 
 }
 }
 
-// TODO, make this a field of ModelChecker or something similar
-static std::unique_ptr<simgrid::mc::StateComparator> mc_diff_info;
-
 /************************************************************************************/
 
-static int is_new_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
-                                 int block2, int fragment2)
-{
-
-  unsigned int cursor = 0;
-  simgrid::mc::HeapLocationPair* current_pair;
-  xbt_dynar_foreach(list, cursor, current_pair)
-    if ((*current_pair)[0].block == block1
-        && (*current_pair)[1].block == block2
-        && (*current_pair)[0].fragment == fragment1
-        && (*current_pair)[1].fragment == fragment2)
-      return 0;
-  return 1;
-}
-
-static int add_heap_area_pair(xbt_dynar_t list, int block1, int fragment1,
-                              int block2, int fragment2)
-{
-  if (!is_new_heap_area_pair(list, block1, fragment1, block2, fragment2))
-    return 0;
-  simgrid::mc::HeapLocationPair* pair = xbt_new0(simgrid::mc::HeapLocationPair, 1);
-  (*pair)[0].block = block1;
-  (*pair)[0].fragment = fragment1;
-  (*pair)[1].block = block2;
-  (*pair)[1].fragment = fragment2;
-  xbt_dynar_push(list, &pair);
-  return 1;
-}
-
 static ssize_t heap_comparison_ignore_size(
   std::vector<simgrid::mc::IgnoredHeapRegion>* ignore_list,
   const void *address)
@@ -253,22 +265,15 @@ static bool is_block_stack(int block)
 namespace simgrid {
 namespace mc {
 
-void StateComparator::match_equals(xbt_dynar_t list)
+void StateComparator::match_equals(HeapLocationPairs* list)
 {
-  unsigned int cursor = 0;
-  simgrid::mc::HeapLocationPair* current_pair;
-
-  xbt_dynar_foreach(list, cursor, current_pair) {
-    if ((*current_pair)[0].fragment != -1) {
-      this->equals_to1_((*current_pair)[0].block, (*current_pair)[0].fragment) =
-          simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment);
-      this->equals_to2_((*current_pair)[1].block, (*current_pair)[1].fragment) =
-          simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment);
+  for (auto const& pair : *list) {
+    if (pair[0].fragment != -1) {
+      this->equals_to1_(pair[0].block, pair[0].fragment) = simgrid::mc::HeapArea(pair[1].block, pair[1].fragment);
+      this->equals_to2_(pair[1].block, pair[1].fragment) = simgrid::mc::HeapArea(pair[0].block, pair[0].fragment);
     } else {
-      this->equals_to1_((*current_pair)[0].block, 0) =
-          simgrid::mc::HeapArea((*current_pair)[1].block, (*current_pair)[1].fragment);
-      this->equals_to2_((*current_pair)[1].block, 0) =
-          simgrid::mc::HeapArea((*current_pair)[0].block, (*current_pair)[0].fragment);
+      this->equals_to1_(pair[0].block, 0) = simgrid::mc::HeapArea(pair[1].block, pair[1].fragment);
+      this->equals_to2_(pair[1].block, 0) = simgrid::mc::HeapArea(pair[0].block, pair[0].fragment);
     }
   }
 }
@@ -276,8 +281,8 @@ void StateComparator::match_equals(xbt_dynar_t list)
 void ProcessComparisonState::initHeapInformation(xbt_mheap_t heap,
                         std::vector<simgrid::mc::IgnoredHeapRegion>* i)
 {
-  auto heaplimit = ((struct mdesc *) heap)->heaplimit;
-  this->heapsize = ((struct mdesc *) heap)->heapsize;
+  auto heaplimit  = heap->heaplimit;
+  this->heapsize  = heap->heapsize;
   this->to_ignore = i;
   this->equals_to.assign(heaplimit * MAX_FRAGMENT_PER_BLOCK, HeapArea());
   this->types.assign(heaplimit * MAX_FRAGMENT_PER_BLOCK, nullptr);
@@ -287,35 +292,15 @@ int StateComparator::initHeapInformation(xbt_mheap_t heap1, xbt_mheap_t heap2,
                           std::vector<simgrid::mc::IgnoredHeapRegion>* i1,
                           std::vector<simgrid::mc::IgnoredHeapRegion>* i2)
 {
-  if ((((struct mdesc *) heap1)->heaplimit !=
-       ((struct mdesc *) heap2)->heaplimit)
-      ||
-      ((((struct mdesc *) heap1)->heapsize !=
-        ((struct mdesc *) heap2)->heapsize)))
+  if ((heap1->heaplimit != heap2->heaplimit) || (heap1->heapsize != heap2->heapsize))
     return -1;
-  this->heaplimit = ((struct mdesc *) heap1)->heaplimit;
+  this->heaplimit     = heap1->heaplimit;
   this->std_heap_copy = *mc_model_checker->process().get_heap();
   this->processStates[0].initHeapInformation(heap1, i1);
   this->processStates[1].initHeapInformation(heap2, i2);
   return 0;
 }
 
-static
-int init_heap_information(xbt_mheap_t heap1, xbt_mheap_t heap2,
-                          std::vector<simgrid::mc::IgnoredHeapRegion>* i1,
-                          std::vector<simgrid::mc::IgnoredHeapRegion>* i2)
-{
-  if (mc_diff_info == nullptr)
-    mc_diff_info = std::unique_ptr<StateComparator>(new StateComparator());
-  return mc_diff_info->initHeapInformation(heap1, heap2, i1, i2);
-}
-
-static inline
-void reset_heap_information()
-{
-
-}
-
 // TODO, have a robust way to find it in O(1)
 static inline
 mc_mem_region_t MC_get_heap_region(simgrid::mc::Snapshot* snapshot)
@@ -327,23 +312,31 @@ mc_mem_region_t MC_get_heap_region(simgrid::mc::Snapshot* snapshot)
 }
 
 static
-int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2)
+int mmalloc_compare_heap(
+  simgrid::mc::StateComparator& state, simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2)
 {
   simgrid::mc::Process* process = &mc_model_checker->process();
-  simgrid::mc::StateComparator *state = mc_diff_info.get();
 
   /* Start comparison */
-  size_t i1, i2, j1, j2, k;
-  void *addr_block1, *addr_block2, *addr_frag1, *addr_frag2;
-  int nb_diff1 = 0, nb_diff2 = 0;
-
-  int equal, res_compare = 0;
+  size_t i1;
+  size_t i2;
+  size_t j1;
+  size_t j2;
+  size_t k;
+  void* addr_block1;
+  void* addr_block2;
+  void* addr_frag1;
+  void* addr_frag2;
+  int nb_diff1 = 0;
+  int nb_diff2 = 0;
+  int equal;
+  int res_compare = 0;
 
   /* Check busy blocks */
-
   i1 = 1;
 
-  malloc_info heapinfo_temp1, heapinfo_temp2;
+  malloc_info heapinfo_temp1;
+  malloc_info heapinfo_temp2;
   malloc_info heapinfo_temp2b;
 
   mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1);
@@ -358,7 +351,7 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
   const malloc_info* heapinfos2 = snapshot2->read<malloc_info*>(
     (std::uint64_t)heapinfo_address, simgrid::mc::ProcessIndexMissing);
 
-  while (i1 < state->heaplimit) {
+  while (i1 < state.heaplimit) {
 
     const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read(heap_region1, &heapinfo_temp1, &heapinfos1[i1], sizeof(malloc_info));
     const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read(heap_region2, &heapinfo_temp2, &heapinfos2[i1], sizeof(malloc_info));
@@ -373,52 +366,47 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
       abort();
     }
 
-    addr_block1 =
-        ((void *) (((ADDR2UINT(i1)) - 1) * BLOCKSIZE +
-                   (char *) state->std_heap_copy.heapbase));
+    addr_block1 = ((void*)(((ADDR2UINT(i1)) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase));
 
     if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED) {       /* Large block */
 
       if (is_stack(addr_block1)) {
         for (k = 0; k < heapinfo1->busy_block.size; k++)
-          state->equals_to1_(i1 + k, 0) = HeapArea(i1, -1);
+          state.equals_to1_(i1 + k, 0) = HeapArea(i1, -1);
         for (k = 0; k < heapinfo2->busy_block.size; k++)
-          state->equals_to2_(i1 + k, 0) = HeapArea(i1, -1);
+          state.equals_to2_(i1 + k, 0) = HeapArea(i1, -1);
         i1 += heapinfo1->busy_block.size;
         continue;
       }
 
-      if (state->equals_to1_(i1, 0).valid) {
+      if (state.equals_to1_(i1, 0).valid) {
         i1++;
         continue;
       }
 
-      i2 = 1;
-      equal = 0;
+      i2          = 1;
+      equal       = 0;
       res_compare = 0;
 
       /* Try first to associate to same block in the other heap */
       if (heapinfo2->type == heapinfo1->type
-        && state->equals_to2_(i1, 0).valid == 0) {
-        addr_block2 = (ADDR2UINT(i1) - 1) * BLOCKSIZE +
-                       (char *) state->std_heap_copy.heapbase;
-        res_compare =
-            compare_heap_area(simgrid::mc::ProcessIndexMissing, addr_block1, addr_block2, snapshot1, snapshot2,
-                              nullptr, nullptr, 0);
+        && state.equals_to2_(i1, 0).valid == 0) {
+        addr_block2 = (ADDR2UINT(i1) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase;
+        res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing, addr_block1, addr_block2, snapshot1,
+                                        snapshot2, nullptr, nullptr, 0);
         if (res_compare != 1) {
           for (k = 1; k < heapinfo2->busy_block.size; k++)
-            state->equals_to2_(i1 + k, 0) = HeapArea(i1, -1);
+            state.equals_to2_(i1 + k, 0) = HeapArea(i1, -1);
           for (k = 1; k < heapinfo1->busy_block.size; k++)
-            state->equals_to1_(i1 + k, 0) = HeapArea(i1, -1);
+            state.equals_to1_(i1 + k, 0) = HeapArea(i1, -1);
           equal = 1;
           i1 += heapinfo1->busy_block.size;
         }
       }
 
-      while (i2 < state->heaplimit && !equal) {
+      while (i2 < state.heaplimit && not equal) {
 
-        addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE +
-                       (char *) state->std_heap_copy.heapbase;
+        addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase;
 
         if (i2 == i1) {
           i2++;
@@ -432,32 +420,30 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
           continue;
         }
 
-        if (state->equals_to2_(i2, 0).valid) {
+        if (state.equals_to2_(i2, 0).valid) {
           i2++;
           continue;
         }
 
-        res_compare =
-            compare_heap_area(simgrid::mc::ProcessIndexMissing, addr_block1, addr_block2, snapshot1, snapshot2,
-                              nullptr, nullptr, 0);
+        res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing,
+            addr_block1, addr_block2, snapshot1, snapshot2,
+            nullptr, nullptr, 0);
 
         if (res_compare != 1) {
           for (k = 1; k < heapinfo2b->busy_block.size; k++)
-            state->equals_to2_(i2 + k, 0) = HeapArea(i1, -1);
+            state.equals_to2_(i2 + k, 0) = HeapArea(i1, -1);
           for (k = 1; k < heapinfo1->busy_block.size; k++)
-            state->equals_to1_(i1 + k, 0) = HeapArea(i2, -1);
+            state.equals_to1_(i1 + k, 0) = HeapArea(i2, -1);
           equal = 1;
           i1 += heapinfo1->busy_block.size;
         }
 
         i2++;
-
       }
 
-      if (!equal) {
-        XBT_DEBUG("Block %zu not found (size_used = %zu, addr = %p)", i1,
-                  heapinfo1->busy_block.busy_size, addr_block1);
-        i1 = state->heaplimit + 1;
+      if (not equal) {
+        XBT_DEBUG("Block %zu not found (size_used = %zu, addr = %p)", i1, heapinfo1->busy_block.busy_size, addr_block1);
+        i1 = state.heaplimit + 1;
         nb_diff1++;
         //i1++;
       }
@@ -469,33 +455,28 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
         if (heapinfo1->busy_frag.frag_size[j1] == -1) /* Free fragment */
           continue;
 
-        if (state->equals_to1_(i1, j1).valid)
+        if (state.equals_to1_(i1, j1).valid)
           continue;
 
-        addr_frag1 =
-            (void *) ((char *) addr_block1 + (j1 << heapinfo1->type));
+        addr_frag1 = (void*)((char*)addr_block1 + (j1 << heapinfo1->type));
 
         i2 = 1;
         equal = 0;
 
         /* Try first to associate to same fragment in the other heap */
-        if (heapinfo2->type == heapinfo1->type
-            && !state->equals_to2_(i1, j1).valid) {
+        if (heapinfo2->type == heapinfo1->type && not state.equals_to2_(i1, j1).valid) {
           addr_block2 = (ADDR2UINT(i1) - 1) * BLOCKSIZE +
-                         (char *) state->std_heap_copy.heapbase;
+                         (char *) state.std_heap_copy.heapbase;
           addr_frag2 =
               (void *) ((char *) addr_block2 +
                         (j1 << heapinfo2->type));
-          res_compare =
-              compare_heap_area(simgrid::mc::ProcessIndexMissing, addr_frag1, addr_frag2, snapshot1, snapshot2,
-                                nullptr, nullptr, 0);
+          res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing, addr_frag1, addr_frag2, snapshot1,
+                                          snapshot2, nullptr, nullptr, 0);
           if (res_compare != 1)
             equal = 1;
         }
 
-
-
-        while (i2 < state->heaplimit && !equal) {
+        while (i2 < state.heaplimit && not equal) {
 
           const malloc_info* heapinfo2b = (const malloc_info*) MC_region_read(
             heap_region2, &heapinfo_temp2b, &heapinfos2[i2],
@@ -513,7 +494,7 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
           }
 
           if (heapinfo2b->type < 0) {
-            fprintf(stderr, "Unkown mmalloc block type.\n");
+            fprintf(stderr, "Unknown mmalloc block type.\n");
             abort();
           }
 
@@ -523,87 +504,68 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
             if (i2 == i1 && j2 == j1)
               continue;
 
-            if (state->equals_to2_(i2, j2).valid)
+            if (state.equals_to2_(i2, j2).valid)
               continue;
 
-            addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE +
-                           (char *) state->std_heap_copy.heapbase;
-            addr_frag2 =
-                (void *) ((char *) addr_block2 +
-                          (j2 << heapinfo2b->type));
-
-            res_compare =
-                compare_heap_area(simgrid::mc::ProcessIndexMissing, addr_frag1, addr_frag2, snapshot2, snapshot2,
-                                  nullptr, nullptr, 0);
+            addr_block2 = (ADDR2UINT(i2) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase;
+            addr_frag2  = (void*)((char*)addr_block2 + (j2 << heapinfo2b->type));
 
+            res_compare = compare_heap_area(state, simgrid::mc::ProcessIndexMissing, addr_frag1, addr_frag2, snapshot2,
+                                            snapshot2, nullptr, nullptr, 0);
             if (res_compare != 1) {
               equal = 1;
               break;
             }
-
           }
 
           i2++;
-
         }
 
-        if (!equal) {
-          XBT_DEBUG
-              ("Block %zu, fragment %zu not found (size_used = %zd, address = %p)\n",
-               i1, j1, heapinfo1->busy_frag.frag_size[j1],
-               addr_frag1);
-          i2 = state->heaplimit + 1;
-          i1 = state->heaplimit + 1;
+        if (not equal) {
+          XBT_DEBUG("Block %zu, fragment %zu not found (size_used = %zd, address = %p)\n", i1, j1,
+                    heapinfo1->busy_frag.frag_size[j1], addr_frag1);
+          i2 = state.heaplimit + 1;
+          i1 = state.heaplimit + 1;
           nb_diff1++;
           break;
         }
-
       }
 
       i1++;
-
     }
-
   }
 
   /* All blocks/fragments are equal to another block/fragment ? */
-  size_t i = 1, j = 0;
+  size_t i = 1;
+  size_t j = 0;
 
-  for(i = 1; i < state->heaplimit; i++) {
+  for(i = 1; i < state.heaplimit; i++) {
     const malloc_info* heapinfo1 = (const malloc_info*) MC_region_read(
       heap_region1, &heapinfo_temp1, &heapinfos1[i], sizeof(malloc_info));
 
-    if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED
-        && i1 == state->heaplimit
-        && heapinfo1->busy_block.busy_size > 0
-        && !state->equals_to1_(i, 0).valid) {
-      XBT_DEBUG("Block %zu not found (size used = %zu)", i,
-                heapinfo1->busy_block.busy_size);
+    if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED && i1 == state.heaplimit && heapinfo1->busy_block.busy_size > 0 &&
+        not state.equals_to1_(i, 0).valid) {
+      XBT_DEBUG("Block %zu not found (size used = %zu)", i, heapinfo1->busy_block.busy_size);
       nb_diff1++;
     }
 
     if (heapinfo1->type <= 0)
       continue;
     for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo1->type); j++)
-      if (i1 == state->heaplimit
-          && heapinfo1->busy_frag.frag_size[j] > 0
-          && !state->equals_to1_(i, j).valid) {
-        XBT_DEBUG("Block %zu, Fragment %zu not found (size used = %zd)",
-          i, j, heapinfo1->busy_frag.frag_size[j]);
+      if (i1 == state.heaplimit && heapinfo1->busy_frag.frag_size[j] > 0 && not state.equals_to1_(i, j).valid) {
+        XBT_DEBUG("Block %zu, Fragment %zu not found (size used = %zd)", i, j, heapinfo1->busy_frag.frag_size[j]);
         nb_diff1++;
       }
   }
 
-  if (i1 == state->heaplimit)
-    XBT_DEBUG("Number of blocks/fragments not found in heap1 : %d", nb_diff1);
+  if (i1 == state.heaplimit)
+    XBT_DEBUG("Number of blocks/fragments not found in heap1: %d", nb_diff1);
 
-  for (i=1; i < state->heaplimit; i++) {
+  for (i=1; i < state.heaplimit; i++) {
     const malloc_info* heapinfo2 = (const malloc_info*) MC_region_read(
       heap_region2, &heapinfo_temp2, &heapinfos2[i], sizeof(malloc_info));
-    if (heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED
-        && i1 == state->heaplimit
-        && heapinfo2->busy_block.busy_size > 0
-        && !state->equals_to2_(i, 0).valid) {
+    if (heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED && i1 == state.heaplimit && heapinfo2->busy_block.busy_size > 0 &&
+        not state.equals_to2_(i, 0).valid) {
       XBT_DEBUG("Block %zu not found (size used = %zu)", i,
                 heapinfo2->busy_block.busy_size);
       nb_diff2++;
@@ -613,9 +575,7 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
       continue;
 
     for (j = 0; j < (size_t) (BLOCKSIZE >> heapinfo2->type); j++)
-      if (i1 == state->heaplimit
-          && heapinfo2->busy_frag.frag_size[j] > 0
-          && !state->equals_to2_(i, j).valid) {
+      if (i1 == state.heaplimit && heapinfo2->busy_frag.frag_size[j] > 0 && not state.equals_to2_(i, j).valid) {
         XBT_DEBUG("Block %zu, Fragment %zu not found (size used = %zd)",
           i, j, heapinfo2->busy_frag.frag_size[j]);
         nb_diff2++;
@@ -623,8 +583,8 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
 
   }
 
-  if (i1 == state->heaplimit)
-    XBT_DEBUG("Number of blocks/fragments not found in heap2 : %d", nb_diff2);
+  if (i1 == state.heaplimit)
+    XBT_DEBUG("Number of blocks/fragments not found in heap2: %d", nb_diff2);
 
   return nb_diff1 > 0 || nb_diff2 > 0;
 }
@@ -641,11 +601,11 @@ int mmalloc_compare_heap(simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot
  * @param check_ignore
  */
 static int compare_heap_area_without_type(
-  simgrid::mc::StateComparator *state, int process_index,
+  simgrid::mc::StateComparatorstate, int process_index,
   const void *real_area1, const void *real_area2,
   simgrid::mc::Snapshot* snapshot1,
   simgrid::mc::Snapshot* snapshot2,
-  xbt_dynar_t previous, int size,
+  HeapLocationPairs* previous, int size,
   int check_ignore)
 {
   simgrid::mc::Process* process = &mc_model_checker->process();
@@ -656,10 +616,10 @@ static int compare_heap_area_without_type(
 
     if (check_ignore > 0) {
       ssize_t ignore1 = heap_comparison_ignore_size(
-        state->processStates[0].to_ignore, (char *) real_area1 + i);
+        state.processStates[0].to_ignore, (char *) real_area1 + i);
       if (ignore1 != -1) {
         ssize_t ignore2 = heap_comparison_ignore_size(
-          state->processStates[1].to_ignore, (char *) real_area2 + i);
+          state.processStates[1].to_ignore, (char *) real_area2 + i);
         if (ignore2 == ignore1) {
           if (ignore1 == 0) {
             check_ignore--;
@@ -687,14 +647,14 @@ static int compare_heap_area_without_type(
         continue;
       }
 
-      if (addr_pointed1 > state->std_heap_copy.heapbase
+      if (addr_pointed1 > state.std_heap_copy.heapbase
            && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
-           && addr_pointed2 > state->std_heap_copy.heapbase
+           && addr_pointed2 > state.std_heap_copy.heapbase
            && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)) {
         // Both addreses are in the heap:
-        int res_compare =
-            compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
-                              snapshot2, previous, nullptr, 0);
+        int res_compare = compare_heap_area(state ,process_index,
+          addr_pointed1, addr_pointed2,
+          snapshot1, snapshot2, previous, nullptr, 0);
         if (res_compare == 1)
           return res_compare;
         i = pointer_align + sizeof(void *);
@@ -718,18 +678,18 @@ static int compare_heap_area_without_type(
  * @param snapshot1      Snapshot of state 1
  * @param snapshot2      Snapshot of state 2
  * @param previous
- * @param type_id
+ * @param type
  * @param area_size      either a byte_size or an elements_count (?)
  * @param check_ignore
  * @param pointer_level
  * @return               0 (same), 1 (different), -1 (unknown)
  */
 static int compare_heap_area_with_type(
-  simgrid::mc::StateComparator *state, int process_index,
+  simgrid::mc::StateComparatorstate, int process_index,
   const void *real_area1, const void *real_area2,
   simgrid::mc::Snapshot* snapshot1,
   simgrid::mc::Snapshot* snapshot2,
-  xbt_dynar_t previous, simgrid::mc::Type* type,
+  HeapLocationPairs* previous, simgrid::mc::Type* type,
   int area_size, int check_ignore,
   int pointer_level)
 {
@@ -749,16 +709,19 @@ top:
 
   if (check_ignore > 0) {
     ssize_t ignore1 = heap_comparison_ignore_size(
-      state->processStates[0].to_ignore, real_area1);
+      state.processStates[0].to_ignore, real_area1);
     if (ignore1 > 0
         && heap_comparison_ignore_size(
-          state->processStates[1].to_ignore, real_area2) == ignore1)
+          state.processStates[1].to_ignore, real_area2) == ignore1)
       return 0;
   }
 
-  simgrid::mc::Type *subtype, *subsubtype;
-  int res, elm_size;
-  const void *addr_pointed1, *addr_pointed2;
+  simgrid::mc::Type* subtype;
+  simgrid::mc::Type* subsubtype;
+  int res;
+  int elm_size;
+  const void* addr_pointed1;
+  const void* addr_pointed2;
 
   mc_mem_region_t heap_region1 = MC_get_heap_region(snapshot1);
   mc_mem_region_t heap_region2 = MC_get_heap_region(snapshot2);
@@ -768,7 +731,7 @@ top:
     return 1;
 
   case DW_TAG_base_type:
-    if (!type->name.empty() && type->name == "char") {        /* String, hence random (arbitrary ?) size */
+    if (not type->name.empty() && type->name == "char") { /* String, hence random (arbitrary ?) size */
       if (real_area1 == real_area2)
         return -1;
       else
@@ -850,13 +813,14 @@ top:
     if (pointer_level <= 1) {
       addr_pointed1 = snapshot1->read(remote((void**)real_area1), process_index);
       addr_pointed2 = snapshot2->read(remote((void**)real_area2), process_index);
-      if (addr_pointed1 > state->std_heap_copy.heapbase
+      if (addr_pointed1 > state.std_heap_copy.heapbase
           && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
-          && addr_pointed2 > state->std_heap_copy.heapbase
+          && addr_pointed2 > state.std_heap_copy.heapbase
           && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2))
-        return compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
-                                 snapshot2, previous, type->subtype,
-                                 pointer_level);
+        return compare_heap_area(state, process_index,
+            addr_pointed1, addr_pointed2, snapshot1,
+            snapshot2, previous, type->subtype,
+            pointer_level);
       else
         return (addr_pointed1 != addr_pointed2);
     }
@@ -867,14 +831,15 @@ top:
       addr_pointed2 = snapshot2->read(
         remote((void**)((char*) real_area2 + i * sizeof(void *))),
         process_index);
-      if (addr_pointed1 > state->std_heap_copy.heapbase
+      if (addr_pointed1 > state.std_heap_copy.heapbase
           && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)
-          && addr_pointed2 > state->std_heap_copy.heapbase
+          && addr_pointed2 > state.std_heap_copy.heapbase
           && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2))
         res =
-            compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
-                              snapshot2, previous, type->subtype,
-                              pointer_level);
+            compare_heap_area(state, process_index,
+              addr_pointed1, addr_pointed2, snapshot1,
+              snapshot2, previous, type->subtype,
+              pointer_level);
       else
         res = (addr_pointed1 != addr_pointed2);
       if (res == 1)
@@ -920,7 +885,6 @@ top:
     return compare_heap_area_without_type(state, process_index, real_area1, real_area2,
                                           snapshot1, snapshot2, previous,
                                           type->byte_size, check_ignore);
-    return 0;
 
   default:
     return 0;
@@ -935,7 +899,7 @@ top:
  *
  * TODO, handle subfields ((*p).bar.foo, (*p)[5].bar…)
  *
- * @param  type_id            DWARF type ID of the root address
+ * @param  type               DWARF type ID of the root address
  * @param  area_size
  * @return                    DWARF type ID for given offset
  */
@@ -967,16 +931,15 @@ static simgrid::mc::Type* get_offset_type(void *real_base_address, simgrid::mc::
         if (member.offset() == offset)
           return member.type;
       } else {
-        void *real_member = simgrid::dwarf::resolve_member(
-          real_base_address, type, &member, snapshot, process_index);
-        if ((char*) real_member - (char *) real_base_address == offset)
+        void* real_member = simgrid::dwarf::resolve_member(real_base_address, type, &member, snapshot, process_index);
+        if ((char*)real_member - (char*)real_base_address == offset)
           return member.type;
       }
     }
     return nullptr;
 
   default:
-    /* FIXME : other cases ? */
+    /* FIXME: other cases ? */
     return nullptr;
 
   }
@@ -994,79 +957,76 @@ static simgrid::mc::Type* get_offset_type(void *real_base_address, simgrid::mc::
  * @return 0 (same), 1 (different), -1
  */
 static
-int compare_heap_area(int process_index, const void *area1, const void *area2, simgrid::mc::Snapshot* snapshot1,
-                      simgrid::mc::Snapshot* snapshot2, xbt_dynar_t previous,
+int compare_heap_area(simgrid::mc::StateComparator& state, int process_index,
+                      const void *area1, const void *area2,
+                      simgrid::mc::Snapshot* snapshot1,
+                      simgrid::mc::Snapshot* snapshot2,
+                      HeapLocationPairs* previous,
                       simgrid::mc::Type* type, int pointer_level)
 {
   simgrid::mc::Process* process = &mc_model_checker->process();
 
-  simgrid::mc::StateComparator *state = mc_diff_info.get();
-
   int res_compare;
-  ssize_t block1, frag1, block2, frag2;
+  ssize_t block1;
+  ssize_t frag1;
+  ssize_t block2;
+  ssize_t frag2;
   ssize_t size;
   int check_ignore = 0;
 
-  void *real_addr_block1, *real_addr_block2, *real_addr_frag1, *real_addr_frag2;
+  void* real_addr_block1;
+  void* real_addr_block2;
+  void* real_addr_frag1;
+  void* real_addr_frag2;
   int type_size = -1;
-  int offset1 = 0, offset2 = 0;
-  int new_size1 = -1, new_size2 = -1;
-  simgrid::mc::Type *new_type1 = nullptr, *new_type2 = nullptr;
+  int offset1   = 0;
+  int offset2   = 0;
+  int new_size1 = -1;
+  int new_size2 = -1;
 
-  int match_pairs = 0;
+  simgrid::mc::Type* new_type1 = nullptr;
+  simgrid::mc::Type* new_type2 = nullptr;
+
+  bool match_pairs = false;
 
   // This is the address of std_heap->heapinfo in the application process:
   void* heapinfo_address = &((xbt_mheap_t) process->heap_address)->heapinfo;
 
-  const malloc_info* heapinfos1 = snapshot1->read(
-    remote((const malloc_info**)heapinfo_address), process_index);
-  const malloc_info* heapinfos2 = snapshot2->read(
-    remote((const malloc_info**)heapinfo_address), process_index);
+  const malloc_info* heapinfos1 = snapshot1->read(remote((const malloc_info**)heapinfo_address), process_index);
+  const malloc_info* heapinfos2 = snapshot2->read(remote((const malloc_info**)heapinfo_address), process_index);
 
   malloc_info heapinfo_temp1, heapinfo_temp2;
 
+  simgrid::mc::HeapLocationPairs current;
   if (previous == nullptr) {
-    previous = xbt_dynar_new(sizeof(simgrid::mc::HeapLocationPair*), [](void *d) {
-      xbt_free((simgrid::mc::HeapLocationPair*) * (void **) d); });
-    match_pairs = 1;
+    previous = &current;
+    match_pairs = true;
   }
 
   // Get block number:
-  block1 =
-      ((char *) area1 -
-       (char *) state->std_heap_copy.heapbase) / BLOCKSIZE + 1;
-  block2 =
-      ((char *) area2 -
-       (char *) state->std_heap_copy.heapbase) / BLOCKSIZE + 1;
+  block1 = ((char*)area1 - (char*)state.std_heap_copy.heapbase) / BLOCKSIZE + 1;
+  block2 = ((char*)area2 - (char*)state.std_heap_copy.heapbase) / BLOCKSIZE + 1;
 
   // If either block is a stack block:
   if (is_block_stack((int) block1) && is_block_stack((int) block2)) {
-    add_heap_area_pair(previous, block1, -1, block2, -1);
-    if (match_pairs) {
-      state->match_equals(previous);
-      xbt_dynar_free(&previous);
-    }
+    previous->insert(simgrid::mc::makeHeapLocationPair(block1, -1, block2, -1));
+    if (match_pairs)
+      state.match_equals(previous);
     return 0;
   }
 
   // If either block is not in the expected area of memory:
-  if (((char *) area1 < (char *) state->std_heap_copy.heapbase)
-      || (block1 > (ssize_t) state->processStates[0].heapsize) || (block1 < 1)
-      || ((char *) area2 < (char *) state->std_heap_copy.heapbase)
-      || (block2 > (ssize_t) state->processStates[1].heapsize) || (block2 < 1)) {
-    if (match_pairs)
-      xbt_dynar_free(&previous);
+  if (((char*)area1 < (char*)state.std_heap_copy.heapbase) || (block1 > (ssize_t)state.processStates[0].heapsize) ||
+      (block1 < 1) || ((char*)area2 < (char*)state.std_heap_copy.heapbase) ||
+      (block2 > (ssize_t)state.processStates[1].heapsize) || (block2 < 1)) {
     return 1;
   }
 
   // Process address of the block:
-  real_addr_block1 = (ADDR2UINT(block1) - 1) * BLOCKSIZE +
-                 (char *) state->std_heap_copy.heapbase;
-  real_addr_block2 = (ADDR2UINT(block2) - 1) * BLOCKSIZE +
-                 (char *) state->std_heap_copy.heapbase;
+  real_addr_block1 = (ADDR2UINT(block1) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase;
+  real_addr_block2 = (ADDR2UINT(block2) - 1) * BLOCKSIZE + (char*)state.std_heap_copy.heapbase;
 
   if (type) {
-
     if (type->full_type)
       type = type->full_type;
 
@@ -1075,9 +1035,8 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
       type = type->subtype;
 
     // Find type_size:
-    if (type->type == DW_TAG_pointer_type
-        || (type->type == DW_TAG_base_type && !type->name.empty()
-            && type->name == "char"))
+    if (type->type == DW_TAG_pointer_type ||
+        (type->type == DW_TAG_base_type && not type->name.empty() && type->name == "char"))
       type_size = -1;
     else
       type_size = type->byte_size;
@@ -1095,29 +1054,22 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
   if ((heapinfo1->type == MMALLOC_TYPE_FREE || heapinfo1->type==MMALLOC_TYPE_HEAPINFO)
     && (heapinfo2->type == MMALLOC_TYPE_FREE || heapinfo2->type ==MMALLOC_TYPE_HEAPINFO)) {
     /* Free block */
-    if (match_pairs) {
-      state->match_equals(previous);
-      xbt_dynar_free(&previous);
-    }
+    if (match_pairs)
+      state.match_equals(previous);
     return 0;
   }
 
-  if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED
-    && heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED) {
+  if (heapinfo1->type == MMALLOC_TYPE_UNFRAGMENTED && heapinfo2->type == MMALLOC_TYPE_UNFRAGMENTED) {
     /* Complete block */
 
     // TODO, lookup variable type from block type as done for fragmented blocks
 
-    offset1 = (char *) area1 - (char *) real_addr_block1;
-    offset2 = (char *) area2 - (char *) real_addr_block2;
+    offset1 = (char*)area1 - (char*)real_addr_block1;
+    offset2 = (char*)area2 - (char*)real_addr_block2;
 
-    if (state->equals_to1_(block1, 0).valid
-        && state->equals_to2_(block2, 0).valid
-        && state->blocksEqual(block1, block2)) {
-      if (match_pairs) {
-        state->match_equals(previous);
-        xbt_dynar_free(&previous);
-      }
+    if (state.equals_to1_(block1, 0).valid && state.equals_to2_(block2, 0).valid && state.blocksEqual(block1, block2)) {
+      if (match_pairs)
+        state.match_equals(previous);
       return 0;
     }
 
@@ -1125,31 +1077,20 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
       if (type_size != (ssize_t) heapinfo1->busy_block.busy_size
           && type_size != (ssize_t)   heapinfo2->busy_block.busy_size
           && (type->name.empty() || type->name == "struct s_smx_context")) {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
+        if (match_pairs)
+          state.match_equals(previous);
         return -1;
       }
     }
 
-    if (heapinfo1->busy_block.size != heapinfo2->busy_block.size) {
-      if (match_pairs)
-        xbt_dynar_free(&previous);
+    if (heapinfo1->busy_block.size != heapinfo2->busy_block.size)
       return 1;
-    }
-
-    if (heapinfo1->busy_block.busy_size != heapinfo2->busy_block.busy_size) {
-      if (match_pairs)
-        xbt_dynar_free(&previous);
+    if (heapinfo1->busy_block.busy_size != heapinfo2->busy_block.busy_size)
       return 1;
-    }
 
-    if (!add_heap_area_pair(previous, block1, -1, block2, -1)) {
-      if (match_pairs) {
-        state->match_equals(previous);
-        xbt_dynar_free(&previous);
-      }
+    if (not previous->insert(simgrid::mc::makeHeapLocationPair(block1, -1, block2, -1)).second) {
+      if (match_pairs)
+        state.match_equals(previous);
       return 0;
     }
 
@@ -1158,15 +1099,13 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
     // Remember (basic) type inference.
     // The current data structure only allows us to do this for the whole block.
     if (type != nullptr && area1 == real_addr_block1)
-      state->types1_(block1, 0) = type;
+      state.types1_(block1, 0) = type;
     if (type != nullptr && area2 == real_addr_block2)
-      state->types2_(block2, 0) = type;
+      state.types2_(block2, 0) = type;
 
     if (size <= 0) {
-      if (match_pairs) {
-        state->match_equals(previous);
-        xbt_dynar_free(&previous);
-      }
+      if (match_pairs)
+        state.match_equals(previous);
       return 0;
     }
 
@@ -1180,65 +1119,45 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
   } else if ((heapinfo1->type > 0) && (heapinfo2->type > 0)) {      /* Fragmented block */
 
     // Fragment number:
-    frag1 =
-        ((uintptr_t) (ADDR2UINT(area1) % (BLOCKSIZE))) >> heapinfo1->type;
-    frag2 =
-        ((uintptr_t) (ADDR2UINT(area2) % (BLOCKSIZE))) >> heapinfo2->type;
+    frag1 = ((uintptr_t)(ADDR2UINT(area1) % (BLOCKSIZE))) >> heapinfo1->type;
+    frag2 = ((uintptr_t)(ADDR2UINT(area2) % (BLOCKSIZE))) >> heapinfo2->type;
 
     // Process address of the fragment:
-    real_addr_frag1 =
-        (void *) ((char *) real_addr_block1 +
-                  (frag1 << heapinfo1->type));
-    real_addr_frag2 =
-        (void *) ((char *) real_addr_block2 +
-                  (frag2 << heapinfo2->type));
+    real_addr_frag1 = (void*)((char*)real_addr_block1 + (frag1 << heapinfo1->type));
+    real_addr_frag2 = (void*)((char*)real_addr_block2 + (frag2 << heapinfo2->type));
 
     // Check the size of the fragments against the size of the type:
     if (type_size != -1) {
-      if (heapinfo1->busy_frag.frag_size[frag1] == -1
-          || heapinfo2->busy_frag.frag_size[frag2] == -1) {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
+      if (heapinfo1->busy_frag.frag_size[frag1] == -1 || heapinfo2->busy_frag.frag_size[frag2] == -1) {
+        if (match_pairs)
+          state.match_equals(previous);
         return -1;
       }
       // ?
       if (type_size != heapinfo1->busy_frag.frag_size[frag1]
           || type_size != heapinfo2->busy_frag.frag_size[frag2]) {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
+        if (match_pairs)
+          state.match_equals(previous);
         return -1;
       }
     }
 
     // Check if the blocks are already matched together:
-    if (state->equals_to1_(block1, frag1).valid
-        && state->equals_to2_(block2, frag2).valid) {
-      if (offset1==offset2 && state->fragmentsEqual(block1, frag1, block2, frag2)) {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
+    if (state.equals_to1_(block1, frag1).valid && state.equals_to2_(block2, frag2).valid) {
+      if (offset1==offset2 && state.fragmentsEqual(block1, frag1, block2, frag2)) {
+        if (match_pairs)
+          state.match_equals(previous);
         return 0;
       }
     }
     // Compare the size of both fragments:
-    if (heapinfo1->busy_frag.frag_size[frag1] !=
-        heapinfo2->busy_frag.frag_size[frag2]) {
+    if (heapinfo1->busy_frag.frag_size[frag1] != heapinfo2->busy_frag.frag_size[frag2]) {
       if (type_size == -1) {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
-        return -1;
-      } else {
         if (match_pairs)
-          xbt_dynar_free(&previous);
+          state.match_equals(previous);
+        return -1;
+      } else
         return 1;
-      }
     }
 
     // Size of the fragment:
@@ -1247,9 +1166,9 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
     // Remember (basic) type inference.
     // The current data structure only allows us to do this for the whole fragment.
     if (type != nullptr && area1 == real_addr_frag1)
-      state->types1_(block1, frag1) = type;
+      state.types1_(block1, frag1) = type;
     if (type != nullptr && area2 == real_addr_frag2)
-      state->types2_(block2, frag2) = type;
+      state.types2_(block2, frag2) = type;
 
     // The type of the variable is already known:
     if (type) {
@@ -1257,39 +1176,29 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
       new_type2 = type;
     }
     // Type inference from the block type.
-    else if (state->types1_(block1, frag1) != nullptr
-             || state->types2_(block2, frag2) != nullptr) {
+    else if (state.types1_(block1, frag1) != nullptr || state.types2_(block2, frag2) != nullptr) {
 
-      offset1 = (char *) area1 - (char *) real_addr_frag1;
-      offset2 = (char *) area2 - (char *) real_addr_frag2;
+      offset1 = (char*)area1 - (char*)real_addr_frag1;
+      offset2 = (char*)area2 - (char*)real_addr_frag2;
 
-      if (state->types1_(block1, frag1) != nullptr
-          && state->types2_(block2, frag2) != nullptr) {
+      if (state.types1_(block1, frag1) != nullptr && state.types2_(block2, frag2) != nullptr) {
         new_type1 =
-            get_offset_type(real_addr_frag1, state->types1_(block1, frag1),
-                            offset1, size, snapshot1, process_index);
+            get_offset_type(real_addr_frag1, state.types1_(block1, frag1), offset1, size, snapshot1, process_index);
         new_type2 =
-            get_offset_type(real_addr_frag2, state->types2_(block2, frag2),
-                            offset1, size, snapshot2, process_index);
-      } else if (state->types1_(block1, frag1) != nullptr) {
+            get_offset_type(real_addr_frag2, state.types2_(block2, frag2), offset1, size, snapshot2, process_index);
+      } else if (state.types1_(block1, frag1) != nullptr) {
         new_type1 =
-            get_offset_type(real_addr_frag1, state->types1_(block1, frag1),
-                            offset1, size, snapshot1, process_index);
+            get_offset_type(real_addr_frag1, state.types1_(block1, frag1), offset1, size, snapshot1, process_index);
         new_type2 =
-            get_offset_type(real_addr_frag2, state->types1_(block1, frag1),
-                            offset2, size, snapshot2, process_index);
-      } else if (state->types2_(block2, frag2) != nullptr) {
+            get_offset_type(real_addr_frag2, state.types1_(block1, frag1), offset2, size, snapshot2, process_index);
+      } else if (state.types2_(block2, frag2) != nullptr) {
         new_type1 =
-            get_offset_type(real_addr_frag1, state->types2_(block2, frag2),
-                            offset1, size, snapshot1, process_index);
+            get_offset_type(real_addr_frag1, state.types2_(block2, frag2), offset1, size, snapshot1, process_index);
         new_type2 =
-            get_offset_type(real_addr_frag2, state->types2_(block2, frag2),
-                            offset2, size, snapshot2, process_index);
+            get_offset_type(real_addr_frag2, state.types2_(block2, frag2), offset2, size, snapshot2, process_index);
       } else {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
+        if (match_pairs)
+          state.match_equals(previous);
         return -1;
       }
 
@@ -1306,10 +1215,8 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
         new_size2 = type->byte_size;
 
       } else {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
+        if (match_pairs)
+          state.match_equals(previous);
         return -1;
       }
     }
@@ -1319,95 +1226,50 @@ int compare_heap_area(int process_index, const void *area1, const void *area2, s
       size = new_size1;
     }
 
-    if (offset1 == 0 && offset2 == 0
-      && !add_heap_area_pair(previous, block1, frag1, block2, frag2)) {
-        if (match_pairs) {
-          state->match_equals(previous);
-          xbt_dynar_free(&previous);
-        }
-        return 0;
-      }
+    if (offset1 == 0 && offset2 == 0 &&
+        not previous->insert(simgrid::mc::makeHeapLocationPair(block1, frag1, block2, frag2)).second) {
+      if (match_pairs)
+        state.match_equals(previous);
+      return 0;
+    }
 
     if (size <= 0) {
-      if (match_pairs) {
-        state->match_equals(previous);
-        xbt_dynar_free(&previous);
-      }
+      if (match_pairs)
+        state.match_equals(previous);
       return 0;
     }
 
-    if ((heapinfo1->busy_frag.ignore[frag1] > 0)
-        && (heapinfo2->busy_frag.ignore[frag2] ==
-            heapinfo1->busy_frag.ignore[frag1]))
+    if ((heapinfo1->busy_frag.ignore[frag1] > 0) &&
+        (heapinfo2->busy_frag.ignore[frag2] == heapinfo1->busy_frag.ignore[frag1]))
       check_ignore = heapinfo1->busy_frag.ignore[frag1];
 
-  } else {
-    if (match_pairs)
-      xbt_dynar_free(&previous);
+  } else
     return 1;
-  }
 
 
   /* Start comparison */
   if (type)
-    res_compare =
-        compare_heap_area_with_type(state, process_index, area1, area2, snapshot1, snapshot2,
-                                    previous, type, size, check_ignore,
-                                    pointer_level);
+    res_compare = compare_heap_area_with_type(state, process_index, area1, area2, snapshot1, snapshot2, previous, type,
+                                              size, check_ignore, pointer_level);
   else
-    res_compare =
-        compare_heap_area_without_type(state, process_index, area1, area2, snapshot1, snapshot2,
-                                       previous, size, check_ignore);
+    res_compare = compare_heap_area_without_type(state, process_index, area1, area2, snapshot1, snapshot2, previous,
+                                                 size, check_ignore);
 
-  if (res_compare == 1) {
-    if (match_pairs)
-      xbt_dynar_free(&previous);
+  if (res_compare == 1)
     return res_compare;
-  }
-
-  if (match_pairs) {
-    state->match_equals(previous);
-    xbt_dynar_free(&previous);
-  }
 
+  if (match_pairs)
+    state.match_equals(previous);
   return 0;
 }
 
 }
 }
 
-namespace simgrid {
-namespace mc {
-
-/** A hash which works with more stuff
- *
- *  It can hash pairs: the standard hash currently doesn't include this.
- */
-template<class X> struct hash : public std::hash<X> {};
-
-template<class X, class Y>
-struct hash<std::pair<X,Y>> {
-  std::size_t operator()(std::pair<X,Y>const& x) const
-  {
-    struct hash<X> h1;
-    struct hash<X> h2;
-    return h1(x.first) ^ h2(x.second);
-  }
-};
-
-struct ComparisonState {
-  std::unordered_set<std::pair<void*, void*>, hash<std::pair<void*, void*>>> compared_pointers;
-};
-
-}
-}
-
-using simgrid::mc::ComparisonState;
-
 /************************** Snapshot comparison *******************************/
 /******************************************************************************/
 
-static int compare_areas_with_type(ComparisonState& state,
+static int compare_areas_with_type(simgrid::mc::StateComparator& state,
                                    int process_index,
                                    void* real_area1, simgrid::mc::Snapshot* snapshot1, mc_mem_region_t region1,
                                    void* real_area2, simgrid::mc::Snapshot* snapshot2, mc_mem_region_t region2,
@@ -1417,7 +1279,9 @@ static int compare_areas_with_type(ComparisonState& state,
 
   simgrid::mc::Type* subtype;
   simgrid::mc::Type* subsubtype;
-  int elm_size, i, res;
+  int elm_size;
+  int i;
+  int res;
 
   top:
   switch (type->type) {
@@ -1427,11 +1291,7 @@ static int compare_areas_with_type(ComparisonState& state,
   case DW_TAG_base_type:
   case DW_TAG_enumeration_type:
   case DW_TAG_union_type:
-  {
-    return MC_snapshot_region_memcmp(
-      real_area1, region1, real_area2, region2,
-      type->byte_size) != 0;
-  }
+    return MC_snapshot_region_memcmp(real_area1, region1, real_area2, region2, type->byte_size) != 0;
   case DW_TAG_typedef:
   case DW_TAG_volatile_type:
   case DW_TAG_const_type:
@@ -1491,8 +1351,7 @@ static int compare_areas_with_type(ComparisonState& state,
       return 0;
     if (addr_pointed1 == nullptr || addr_pointed2 == nullptr)
       return 1;
-    if (!state.compared_pointers.insert(
-        std::make_pair(addr_pointed1, addr_pointed2)).second)
+    if (not state.compared_pointers.insert(std::make_pair(addr_pointed1, addr_pointed2)).second)
       return 0;
 
     pointer_level++;
@@ -1509,15 +1368,16 @@ static int compare_areas_with_type(ComparisonState& state,
              && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)))
           return 1;
         // The pointers are both in the heap:
-        return simgrid::mc::compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
-                                 snapshot2, nullptr, type->subtype, pointer_level);
+        return simgrid::mc::compare_heap_area(state,
+          process_index, addr_pointed1, addr_pointed2, snapshot1,
+          snapshot2, nullptr, type->subtype, pointer_level);
       }
 
       // The pointers are both in the current object R/W segment:
       else if (region1->contain(simgrid::mc::remote(addr_pointed1))) {
-        if (!region2->contain(simgrid::mc::remote(addr_pointed2)))
+        if (not region2->contain(simgrid::mc::remote(addr_pointed2)))
           return 1;
-        if (!type->type_id)
+        if (not type->type_id)
           return (addr_pointed1 != addr_pointed2);
         else
           return compare_areas_with_type(state, process_index,
@@ -1556,18 +1416,19 @@ static int compare_areas_with_type(ComparisonState& state,
     return -1;
     break;
   default:
-    XBT_VERB("Unknown case : %d", type->type);
+    XBT_VERB("Unknown case: %d", type->type);
     break;
   }
 
   return 0;
 }
 
-static int compare_global_variables(simgrid::mc::ObjectInformation* object_info,
-                                    int process_index,
-                                    mc_mem_region_t r1,
-                                    mc_mem_region_t r2, simgrid::mc::Snapshot* snapshot1,
-                                    simgrid::mc::Snapshot* snapshot2)
+static int compare_global_variables(
+  simgrid::mc::StateComparator& state,
+  simgrid::mc::ObjectInformation* object_info,
+  int process_index,
+  mc_mem_region_t r1, mc_mem_region_t r2,
+  simgrid::mc::Snapshot* snapshot1, simgrid::mc::Snapshot* snapshot2)
 {
   xbt_assert(r1 && r2, "Missing region.");
 
@@ -1583,11 +1444,12 @@ static int compare_global_variables(simgrid::mc::ObjectInformation* object_info,
 
     // Compare the global variables separately for each simulates process:
     for (size_t process_index = 0; process_index < process_count; process_index++) {
-      int is_diff = compare_global_variables(object_info, process_index,
-        &r1->privatized_data()[process_index],
-        &r2->privatized_data()[process_index],
-        snapshot1, snapshot2);
-      if (is_diff) return 1;
+      if (compare_global_variables(state,
+          object_info, process_index,
+          &r1->privatized_data()[process_index],
+          &r2->privatized_data()[process_index],
+          snapshot1, snapshot2))
+        return 1;
     }
     return 0;
   }
@@ -1596,8 +1458,6 @@ static int compare_global_variables(simgrid::mc::ObjectInformation* object_info,
 #endif
   xbt_assert(r2->storage_type() != simgrid::mc::StorageType::Privatized);
 
-  ComparisonState state;
-
   std::vector<simgrid::mc::Variable>& variables = object_info->global_variables;
 
   for (simgrid::mc::Variable& current_var : variables) {
@@ -1610,8 +1470,7 @@ static int compare_global_variables(simgrid::mc::ObjectInformation* object_info,
       continue;
 
     simgrid::mc::Type* bvariable_type = current_var.type;
-    int res =
-        compare_areas_with_type(state, process_index,
+    int res = compare_areas_with_type(state, process_index,
                                 (char *) current_var.address, snapshot1, r1,
                                 (char *) current_var.address, snapshot2, r2,
                                 bvariable_type, 0);
@@ -1628,14 +1487,13 @@ static int compare_global_variables(simgrid::mc::ObjectInformation* object_info,
 
 }
 
-static int compare_local_variables(int process_index,
+static int compare_local_variables(simgrid::mc::StateComparator& state,
+                                   int process_index,
                                    simgrid::mc::Snapshot* snapshot1,
                                    simgrid::mc::Snapshot* snapshot2,
                                    mc_snapshot_stack_t stack1,
                                    mc_snapshot_stack_t stack2)
 {
-  ComparisonState state;
-
   if (stack1->local_variables.size() != stack2->local_variables.size()) {
     XBT_VERB("Different number of local variables");
     return 1;
@@ -1689,56 +1547,59 @@ static int compare_local_variables(int process_index,
 namespace simgrid {
 namespace mc {
 
+static std::unique_ptr<simgrid::mc::StateComparator> state_comparator;
+
 int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc::Snapshot* s2)
 {
+  // TODO, make this a field of ModelChecker or something similar
+
+  if (state_comparator == nullptr)
+    state_comparator = std::unique_ptr<StateComparator>(new StateComparator());
+  else
+    state_comparator->clear();
+
   simgrid::mc::Process* process = &mc_model_checker->process();
 
   int errors = 0;
-  int res_init;
 
   int hash_result = 0;
   if (_sg_mc_hash) {
     hash_result = (s1->hash != s2->hash);
     if (hash_result) {
-      XBT_VERB("(%d - %d) Different hash : 0x%" PRIx64 "--0x%" PRIx64, num1,
-               num2, s1->hash, s2->hash);
+      XBT_VERB("(%d - %d) Different hash: 0x%" PRIx64 "--0x%" PRIx64, num1, num2, s1->hash, s2->hash);
 #ifndef MC_DEBUG
       return 1;
 #endif
     } else
-      XBT_VERB("(%d - %d) Same hash : 0x%" PRIx64, num1, num2, s1->hash);
+      XBT_VERB("(%d - %d) Same hash: 0x%" PRIx64, num1, num2, s1->hash);
   }
 
   /* Compare enabled processes */
   if (s1->enabled_processes != s2->enabled_processes) {
-      XBT_VERB("(%d - %d) Different enabled processes", num1, num2);
-      // return 1; ??
+    XBT_VERB("(%d - %d) Different amount of enabled processes", num1, num2);
+    return 1;
   }
 
-  unsigned long i = 0;
-  size_t size_used1, size_used2;
-  int is_diff = 0;
-
   /* Compare size of stacks */
-  while (i < s1->stacks.size()) {
-    size_used1 = s1->stack_sizes[i];
-    size_used2 = s2->stack_sizes[i];
+  int is_diff = 0;
+  for (unsigned long i = 0; i < s1->stacks.size(); i++) {
+    size_t size_used1 = s1->stack_sizes[i];
+    size_t size_used2 = s2->stack_sizes[i];
     if (size_used1 != size_used2) {
 #ifdef MC_DEBUG
-      XBT_DEBUG("(%d - %d) Different size used in stacks : %zu - %zu", num1,
-                num2, size_used1, size_used2);
+      XBT_DEBUG("(%d - %d) Different size used in stacks: %zu - %zu", num1, num2, size_used1, size_used2);
       errors++;
       is_diff = 1;
 #else
 #ifdef MC_VERBOSE
-      XBT_VERB("(%d - %d) Different size used in stacks : %zu - %zu", num1,
-               num2, size_used1, size_used2);
+      XBT_VERB("(%d - %d) Different size used in stacks: %zu - %zu", num1, num2, size_used1, size_used2);
 #endif
       return 1;
 #endif
     }
-    i++;
   }
+  if (is_diff) // do not proceed if there is any stacks that don't match
+    return 1;
 
   /* Init heap information used in heap comparison algorithm */
   xbt_mheap_t heap1 = (xbt_mheap_t)s1->read_bytes(
@@ -1749,7 +1610,8 @@ int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc:
     alloca(sizeof(struct mdesc)), sizeof(struct mdesc),
     remote(process->heap_address),
     simgrid::mc::ProcessIndexMissing, simgrid::mc::ReadOptions::lazy());
-  res_init = simgrid::mc::init_heap_information(heap1, heap2, &s1->to_ignore, &s2->to_ignore);
+  int res_init = state_comparator->initHeapInformation(heap1, heap2, &s1->to_ignore, &s2->to_ignore);
+
   if (res_init == -1) {
 #ifdef MC_DEBUG
     XBT_DEBUG("(%d - %d) Different heap information", num1, num2);
@@ -1764,23 +1626,18 @@ int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc:
   }
 
   /* Stacks comparison */
-  unsigned cursor = 0;
   int diff_local = 0;
-#ifdef MC_DEBUG
-  is_diff = 0;
-#endif
-  mc_snapshot_stack_t stack1, stack2;
-  while (cursor < s1->stacks.size()) {
-    stack1 = &s1->stacks[cursor];
-    stack2 = &s2->stacks[cursor];
+  for (unsigned int cursor = 0; cursor < s1->stacks.size(); cursor++) {
+    mc_snapshot_stack_t stack1 = &s1->stacks[cursor];
+    mc_snapshot_stack_t stack2 = &s2->stacks[cursor];
 
     if (stack1->process_index != stack2->process_index) {
       diff_local = 1;
       XBT_DEBUG("(%d - %d) Stacks with different process index (%i vs %i)", num1, num2,
         stack1->process_index, stack2->process_index);
     }
-    else diff_local =
-        compare_local_variables(stack1->process_index, s1, s2, stack1, stack2);
+    else diff_local = compare_local_variables(*state_comparator,
+      stack1->process_index, s1, s2, stack1, stack2);
     if (diff_local > 0) {
 #ifdef MC_DEBUG
       XBT_DEBUG("(%d - %d) Different local variables between stacks %d", num1,
@@ -1794,12 +1651,9 @@ int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc:
                num2, cursor + 1);
 #endif
 
-      simgrid::mc::reset_heap_information();
-
       return 1;
 #endif
     }
-    cursor++;
   }
 
   size_t regions_count = s1->snapshot_regions.size();
@@ -1821,13 +1675,9 @@ int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc:
     std::string const& name = region1->object_info()->file_name;
 
     /* Compare global variables */
-    is_diff =
-      compare_global_variables(region1->object_info(),
-        simgrid::mc::ProcessIndexDisabled,
-        region1, region2,
-        s1, s2);
+    if (compare_global_variables(*state_comparator, region1->object_info(), simgrid::mc::ProcessIndexDisabled, region1,
+                                 region2, s1, s2)) {
 
-    if (is_diff != 0) {
 #ifdef MC_DEBUG
       XBT_DEBUG("(%d - %d) Different global variables in %s",
         num1, num2, name.c_str());
@@ -1844,7 +1694,7 @@ int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc:
   }
 
   /* Compare heap */
-  if (simgrid::mc::mmalloc_compare_heap(s1, s2) > 0) {
+  if (simgrid::mc::mmalloc_compare_heap(*state_comparator, s1, s2) > 0) {
 
 #ifdef MC_DEBUG
     XBT_DEBUG("(%d - %d) Different heap (mmalloc_compare)", num1, num2);
@@ -1854,13 +1704,10 @@ int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc:
 #ifdef MC_VERBOSE
     XBT_VERB("(%d - %d) Different heap (mmalloc_compare)", num1, num2);
 #endif
-
     return 1;
 #endif
   }
 
-  simgrid::mc::reset_heap_information();
-
 #ifdef MC_VERBOSE
   if (errors || hash_result)
     XBT_VERB("(%d - %d) Difference found", num1, num2);
@@ -1874,8 +1721,7 @@ int snapshot_compare(int num1, simgrid::mc::Snapshot* s1, int num2, simgrid::mc:
     // * There MUST not be any false negative.
 
     XBT_VERB("(%d - %d) State equality hash test is %s %s", num1, num2,
-             (hash_result != 0) == (errors != 0) ? "true" : "false",
-             !hash_result ? "positive" : "negative");
+             (hash_result != 0) == (errors != 0) ? "true" : "false", not hash_result ? "positive" : "negative");
   }
 #endif