Logo AND Algorithmique Numérique Distribuée

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