Logo AND Algorithmique Numérique Distribuée

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