Logo AND Algorithmique Numérique Distribuée

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