Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
[mc] Remove C typedefs (mc_foobar_t) and mc_forward.h
[simgrid.git] / src / mc / mc_compare.cpp
1 /* Copyright (c) 2012-2015. The SimGrid Team.
2  * All rights reserved.                                                     */
3
4 /* This program is free software; you can redistribute it and/or modify it
5  * under the terms of the license (GNU LGPL) which comes with this package. */
6
7 #define __STDC_FORMAT_MACROS
8 #include <cinttypes>
9
10 #include <utility>
11 #include <unordered_set>
12
13 #include <xbt/sysdep.h>
14
15 #include "src/internal_config.h"
16 #include "src/mc/mc_forward.hpp"
17 #include "src/mc/mc_safety.h"
18 #include "src/mc/mc_liveness.h"
19 #include "src/mc/mc_private.h"
20 #include "src/mc/mc_smx.h"
21 #include "src/mc/mc_dwarf.hpp"
22 #include "src/mc/malloc.hpp"
23 #include "src/mc/Frame.hpp"
24 #include "src/mc/ObjectInformation.hpp"
25 #include "src/mc/Variable.hpp"
26
27 #if HAVE_SMPI
28 #include "src/smpi/private.h"
29 #endif
30
31 #include "xbt/mmalloc.h"
32 #include "src/xbt/mmalloc/mmprivate.h"
33
34 using simgrid::mc::remote;
35
36 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt,
37                                 "Logging specific to mc_compare in mc");
38
39 namespace simgrid {
40 namespace mc {
41
42 /** A hash which works with more stuff
43  *
44  *  It can hash pairs: the standard hash currently doesn't include this.
45  */
46 template<class X> struct hash : public std::hash<X> {};
47
48 template<class X, class Y>
49 struct hash<std::pair<X,Y>> {
50   std::size_t operator()(std::pair<X,Y>const& x) const
51   {
52     struct hash<X> h1;
53     struct hash<X> h2;
54     return h1(x.first) ^ h2(x.second);
55   }
56 };
57
58 struct ComparisonState {
59   std::unordered_set<std::pair<void*, void*>, hash<std::pair<void*, void*>>> compared_pointers;
60 };
61
62 }
63 }
64
65 using simgrid::mc::ComparisonState;
66
67 extern "C" {
68
69 /************************** Snapshot comparison *******************************/
70 /******************************************************************************/
71
72 static int compare_areas_with_type(ComparisonState& state,
73                                    int process_index,
74                                    void* real_area1, simgrid::mc::Snapshot* snapshot1, mc_mem_region_t region1,
75                                    void* real_area2, simgrid::mc::Snapshot* snapshot2, mc_mem_region_t region2,
76                                    simgrid::mc::Type* type, int pointer_level)
77 {
78   simgrid::mc::Process* process = &mc_model_checker->process();
79
80   simgrid::mc::Type* subtype;
81   simgrid::mc::Type* subsubtype;
82   int elm_size, i, res;
83
84   top:
85   switch (type->type) {
86   case DW_TAG_unspecified_type:
87     return 1;
88
89   case DW_TAG_base_type:
90   case DW_TAG_enumeration_type:
91   case DW_TAG_union_type:
92   {
93     return MC_snapshot_region_memcmp(
94       real_area1, region1, real_area2, region2,
95       type->byte_size) != 0;
96   }
97   case DW_TAG_typedef:
98   case DW_TAG_volatile_type:
99   case DW_TAG_const_type:
100     // Poor man's TCO:
101     type = type->subtype;
102     goto top;
103   case DW_TAG_array_type:
104     subtype = type->subtype;
105     switch (subtype->type) {
106     case DW_TAG_unspecified_type:
107       return 1;
108
109     case DW_TAG_base_type:
110     case DW_TAG_enumeration_type:
111     case DW_TAG_pointer_type:
112     case DW_TAG_reference_type:
113     case DW_TAG_rvalue_reference_type:
114     case DW_TAG_structure_type:
115     case DW_TAG_class_type:
116     case DW_TAG_union_type:
117       if (subtype->full_type)
118         subtype = subtype->full_type;
119       elm_size = subtype->byte_size;
120       break;
121     case DW_TAG_const_type:
122     case DW_TAG_typedef:
123     case DW_TAG_volatile_type:
124       subsubtype = subtype->subtype;
125       if (subsubtype->full_type)
126         subsubtype = subsubtype->full_type;
127       elm_size = subsubtype->byte_size;
128       break;
129     default:
130       return 0;
131       break;
132     }
133     for (i = 0; i < type->element_count; i++) {
134       size_t off = i * elm_size;
135       res = compare_areas_with_type(state, process_index,
136             (char*) real_area1 + off, snapshot1, region1,
137             (char*) real_area2 + off, snapshot2, region2,
138             type->subtype, pointer_level);
139       if (res == 1)
140         return res;
141     }
142     break;
143   case DW_TAG_pointer_type:
144   case DW_TAG_reference_type:
145   case DW_TAG_rvalue_reference_type:
146   {
147     void* addr_pointed1 = MC_region_read_pointer(region1, real_area1);
148     void* addr_pointed2 = MC_region_read_pointer(region2, real_area2);
149
150     if (type->subtype && type->subtype->type == DW_TAG_subroutine_type)
151       return (addr_pointed1 != addr_pointed2);
152     if (addr_pointed1 == nullptr && addr_pointed2 == NULL)
153       return 0;
154     if (addr_pointed1 == nullptr || addr_pointed2 == NULL)
155       return 1;
156     if (!state.compared_pointers.insert(
157         std::make_pair(addr_pointed1, addr_pointed2)).second)
158       return 0;
159
160     pointer_level++;
161
162       // Some cases are not handled here:
163       // * the pointers lead to different areas (one to the heap, the other to the RW segment ...);
164       // * a pointer leads to the read-only segment of the current object;
165       // * a pointer lead to a different ELF object.
166
167       if (addr_pointed1 > process->heap_address
168           && addr_pointed1 < mc_snapshot_get_heap_end(snapshot1)) {
169         if (!
170             (addr_pointed2 > process->heap_address
171              && addr_pointed2 < mc_snapshot_get_heap_end(snapshot2)))
172           return 1;
173         // The pointers are both in the heap:
174         return simgrid::mc::compare_heap_area(process_index, addr_pointed1, addr_pointed2, snapshot1,
175                                  snapshot2, nullptr, type->subtype, pointer_level);
176       }
177
178       // The pointers are both in the current object R/W segment:
179       else if (region1->contain(simgrid::mc::remote(addr_pointed1))) {
180         if (!region2->contain(simgrid::mc::remote(addr_pointed2)))
181           return 1;
182         if (!type->type_id)
183           return (addr_pointed1 != addr_pointed2);
184         else
185           return compare_areas_with_type(state, process_index,
186                                          addr_pointed1, snapshot1, region1,
187                                          addr_pointed2, snapshot2, region2,
188                                          type->subtype, pointer_level);
189       }
190
191       // TODO, We do not handle very well the case where
192       // it belongs to a different (non-heap) region from the current one.
193
194       else
195         return (addr_pointed1 != addr_pointed2);
196
197     break;
198   }
199   case DW_TAG_structure_type:
200   case DW_TAG_class_type:
201     for(simgrid::mc::Member& member : type->members) {
202       void *member1 = simgrid::dwarf::resolve_member(
203         real_area1, type, &member, snapshot1, process_index);
204       void *member2 = simgrid::dwarf::resolve_member(
205         real_area2, type, &member, snapshot2, process_index);
206       mc_mem_region_t subregion1 = mc_get_region_hinted(member1, snapshot1, process_index, region1);
207       mc_mem_region_t subregion2 = mc_get_region_hinted(member2, snapshot2, process_index, region2);
208       res =
209           compare_areas_with_type(state, process_index,
210                                   member1, snapshot1, subregion1,
211                                   member2, snapshot2, subregion2,
212                                   member.type, pointer_level);
213       if (res == 1)
214         return res;
215     }
216     break;
217   case DW_TAG_subroutine_type:
218     return -1;
219     break;
220   default:
221     XBT_VERB("Unknown case : %d", type->type);
222     break;
223   }
224
225   return 0;
226 }
227
228 static int compare_global_variables(simgrid::mc::ObjectInformation* object_info,
229                                     int process_index,
230                                     mc_mem_region_t r1,
231                                     mc_mem_region_t r2, simgrid::mc::Snapshot* snapshot1,
232                                     simgrid::mc::Snapshot* snapshot2)
233 {
234   xbt_assert(r1 && r2, "Missing region.");
235
236 #if HAVE_SMPI
237   if (r1->storage_type() == simgrid::mc::StorageType::Privatized) {
238     xbt_assert(process_index >= 0);
239     if (r2->storage_type() != simgrid::mc::StorageType::Privatized)
240       return 1;
241
242     size_t process_count = MC_smpi_process_count();
243     xbt_assert(process_count == r1->privatized_data().size()
244       && process_count == r2->privatized_data().size());
245
246     // Compare the global variables separately for each simulates process:
247     for (size_t process_index = 0; process_index < process_count; process_index++) {
248       int is_diff = compare_global_variables(object_info, process_index,
249         &r1->privatized_data()[process_index],
250         &r2->privatized_data()[process_index],
251         snapshot1, snapshot2);
252       if (is_diff) return 1;
253     }
254     return 0;
255   }
256 #else
257   xbt_assert(r1->storage_type() != simgrid::mc::StorageType::Privatized);
258 #endif
259   xbt_assert(r2->storage_type() != simgrid::mc::StorageType::Privatized);
260
261   ComparisonState state;
262
263   std::vector<simgrid::mc::Variable>& variables = object_info->global_variables;
264
265   for (simgrid::mc::Variable& current_var : variables) {
266
267     // If the variable is not in this object, skip it:
268     // We do not expect to find a pointer to something which is not reachable
269     // by the global variables.
270     if ((char *) current_var.address < (char *) object_info->start_rw
271         || (char *) current_var.address > (char *) object_info->end_rw)
272       continue;
273
274     simgrid::mc::Type* bvariable_type = current_var.type;
275     int res =
276         compare_areas_with_type(state, process_index,
277                                 (char *) current_var.address, snapshot1, r1,
278                                 (char *) current_var.address, snapshot2, r2,
279                                 bvariable_type, 0);
280     if (res == 1) {
281       XBT_VERB("Global variable %s (%p) is different between snapshots",
282                current_var.name.c_str(),
283                (char *) current_var.address);
284       return 1;
285     }
286
287   }
288
289   return 0;
290
291 }
292
293 static int compare_local_variables(int process_index,
294                                    simgrid::mc::Snapshot* snapshot1,
295                                    simgrid::mc::Snapshot* snapshot2,
296                                    mc_snapshot_stack_t stack1,
297                                    mc_snapshot_stack_t stack2)
298 {
299   ComparisonState state;
300
301   if (stack1->local_variables.size() != stack2->local_variables.size()) {
302     XBT_VERB("Different number of local variables");
303     return 1;
304   }
305
306     unsigned int cursor = 0;
307     local_variable_t current_var1, current_var2;
308     int res;
309     while (cursor < stack1->local_variables.size()) {
310       current_var1 = &stack1->local_variables[cursor];
311       current_var2 = &stack1->local_variables[cursor];
312       if (current_var1->name != current_var2->name
313           || current_var1->subprogram != current_var2->subprogram
314           || current_var1->ip != current_var2->ip) {
315         // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram
316         XBT_VERB
317             ("Different name of variable (%s - %s) "
318              "or frame (%s - %s) or ip (%lu - %lu)",
319              current_var1->name.c_str(),
320              current_var2->name.c_str(),
321              current_var1->subprogram->name.c_str(),
322              current_var2->subprogram->name.c_str(),
323              current_var1->ip, current_var2->ip);
324         return 1;
325       }
326       // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram
327
328         simgrid::mc::Type* subtype = current_var1->type;
329         res =
330             compare_areas_with_type(state, process_index,
331                                     current_var1->address, snapshot1, mc_get_snapshot_region(current_var1->address, snapshot1, process_index),
332                                     current_var2->address, snapshot2, mc_get_snapshot_region(current_var2->address, snapshot2, process_index),
333                                     subtype, 0);
334
335       if (res == 1) {
336         // TODO, fix current_varX->subprogram->name to include name if DW_TAG_inlined_subprogram
337         XBT_VERB
338             ("Local variable %s (%p - %p) in frame %s "
339              "is different between snapshots",
340              current_var1->name.c_str(),
341              current_var1->address,
342              current_var2->address,
343              current_var1->subprogram->name.c_str());
344         return res;
345       }
346       cursor++;
347     }
348     return 0;
349 }
350
351 int snapshot_compare(void *state1, void *state2)
352 {
353   simgrid::mc::Process* process = &mc_model_checker->process();
354
355   simgrid::mc::Snapshot* s1;
356   simgrid::mc::Snapshot* s2;
357   int num1, num2;
358
359   if (_sg_mc_liveness) {        /* Liveness MC */
360     s1 = ((simgrid::mc::VisitedPair*) state1)->graph_state->system_state;
361     s2 = ((simgrid::mc::VisitedPair*) state2)->graph_state->system_state;
362     num1 = ((simgrid::mc::VisitedPair*) state1)->num;
363     num2 = ((simgrid::mc::VisitedPair*) state2)->num;
364   }else if (_sg_mc_termination) { /* Non-progressive cycle MC */
365     s1 = ((mc_state_t) state1)->system_state;
366     s2 = ((mc_state_t) state2)->system_state;
367     num1 = ((mc_state_t) state1)->num;
368     num2 = ((mc_state_t) state2)->num;
369   } else {                      /* Safety or comm determinism MC */
370     s1 = ((simgrid::mc::VisitedState*) state1)->system_state;
371     s2 = ((simgrid::mc::VisitedState*) state2)->system_state;
372     num1 = ((simgrid::mc::VisitedState*) state1)->num;
373     num2 = ((simgrid::mc::VisitedState*) state2)->num;
374   }
375
376   int errors = 0;
377   int res_init;
378
379   int hash_result = 0;
380   if (_sg_mc_hash) {
381     hash_result = (s1->hash != s2->hash);
382     if (hash_result) {
383       XBT_VERB("(%d - %d) Different hash : 0x%" PRIx64 "--0x%" PRIx64, num1,
384                num2, s1->hash, s2->hash);
385 #ifndef MC_DEBUG
386       return 1;
387 #endif
388     } else
389       XBT_VERB("(%d - %d) Same hash : 0x%" PRIx64, num1, num2, s1->hash);
390   }
391
392   /* Compare enabled processes */
393   if (s1->enabled_processes != s2->enabled_processes) {
394       XBT_VERB("(%d - %d) Different enabled processes", num1, num2);
395       // return 1; ??
396   }
397
398   unsigned long i = 0;
399   size_t size_used1, size_used2;
400   int is_diff = 0;
401
402   /* Compare size of stacks */
403   while (i < s1->stacks.size()) {
404     size_used1 = s1->stack_sizes[i];
405     size_used2 = s2->stack_sizes[i];
406     if (size_used1 != size_used2) {
407 #ifdef MC_DEBUG
408       XBT_DEBUG("(%d - %d) Different size used in stacks : %zu - %zu", num1,
409                 num2, size_used1, size_used2);
410       errors++;
411       is_diff = 1;
412 #else
413 #ifdef MC_VERBOSE
414       XBT_VERB("(%d - %d) Different size used in stacks : %zu - %zu", num1,
415                num2, size_used1, size_used2);
416 #endif
417       return 1;
418 #endif
419     }
420     i++;
421   }
422
423   /* Init heap information used in heap comparison algorithm */
424   xbt_mheap_t heap1 = (xbt_mheap_t)s1->read_bytes(
425     alloca(sizeof(struct mdesc)), sizeof(struct mdesc),
426     remote(process->heap_address),
427     simgrid::mc::ProcessIndexMissing, simgrid::mc::ReadOptions::lazy());
428   xbt_mheap_t heap2 = (xbt_mheap_t)s2->read_bytes(
429     alloca(sizeof(struct mdesc)), sizeof(struct mdesc),
430     remote(process->heap_address),
431     simgrid::mc::ProcessIndexMissing, simgrid::mc::ReadOptions::lazy());
432   res_init = simgrid::mc::init_heap_information(heap1, heap2, &s1->to_ignore, &s2->to_ignore);
433   if (res_init == -1) {
434 #ifdef MC_DEBUG
435     XBT_DEBUG("(%d - %d) Different heap information", num1, num2);
436     errors++;
437 #else
438 #ifdef MC_VERBOSE
439     XBT_VERB("(%d - %d) Different heap information", num1, num2);
440 #endif
441
442     return 1;
443 #endif
444   }
445
446   /* Stacks comparison */
447   unsigned cursor = 0;
448   int diff_local = 0;
449 #ifdef MC_DEBUG
450   is_diff = 0;
451 #endif
452   mc_snapshot_stack_t stack1, stack2;
453   while (cursor < s1->stacks.size()) {
454     stack1 = &s1->stacks[cursor];
455     stack2 = &s2->stacks[cursor];
456
457     if (stack1->process_index != stack2->process_index) {
458       diff_local = 1;
459       XBT_DEBUG("(%d - %d) Stacks with different process index (%i vs %i)", num1, num2,
460         stack1->process_index, stack2->process_index);
461     }
462     else diff_local =
463         compare_local_variables(stack1->process_index, s1, s2, stack1, stack2);
464     if (diff_local > 0) {
465 #ifdef MC_DEBUG
466       XBT_DEBUG("(%d - %d) Different local variables between stacks %d", num1,
467                 num2, cursor + 1);
468       errors++;
469       is_diff = 1;
470 #else
471
472 #ifdef MC_VERBOSE
473       XBT_VERB("(%d - %d) Different local variables between stacks %d", num1,
474                num2, cursor + 1);
475 #endif
476
477       simgrid::mc::reset_heap_information();
478
479       return 1;
480 #endif
481     }
482     cursor++;
483   }
484
485   size_t regions_count = s1->snapshot_regions.size();
486   // TODO, raise a difference instead?
487   xbt_assert(regions_count == s2->snapshot_regions.size());
488
489   for (size_t k = 0; k != regions_count; ++k) {
490     mc_mem_region_t region1 = s1->snapshot_regions[k].get();
491     mc_mem_region_t region2 = s2->snapshot_regions[k].get();
492
493     // Preconditions:
494     if (region1->region_type() != simgrid::mc::RegionType::Data)
495       continue;
496
497     xbt_assert(region1->region_type() == region2->region_type());
498     xbt_assert(region1->object_info() == region2->object_info());
499     xbt_assert(region1->object_info());
500
501     std::string const& name = region1->object_info()->file_name;
502
503     /* Compare global variables */
504     is_diff =
505       compare_global_variables(region1->object_info(),
506         simgrid::mc::ProcessIndexDisabled,
507         region1, region2,
508         s1, s2);
509
510     if (is_diff != 0) {
511 #ifdef MC_DEBUG
512       XBT_DEBUG("(%d - %d) Different global variables in %s",
513         num1, num2, name.c_str());
514       errors++;
515 #else
516 #ifdef MC_VERBOSE
517       XBT_VERB("(%d - %d) Different global variables in %s",
518         num1, num2, name.c_str());
519 #endif
520
521       return 1;
522 #endif
523     }
524   }
525
526   /* Compare heap */
527   if (simgrid::mc::mmalloc_compare_heap(s1, s2) > 0) {
528
529 #ifdef MC_DEBUG
530     XBT_DEBUG("(%d - %d) Different heap (mmalloc_compare)", num1, num2);
531     errors++;
532 #else
533
534 #ifdef MC_VERBOSE
535     XBT_VERB("(%d - %d) Different heap (mmalloc_compare)", num1, num2);
536 #endif
537
538     return 1;
539 #endif
540   }
541
542   simgrid::mc::reset_heap_information();
543
544 #ifdef MC_VERBOSE
545   if (errors || hash_result)
546     XBT_VERB("(%d - %d) Difference found", num1, num2);
547   else
548     XBT_VERB("(%d - %d) No difference found", num1, num2);
549 #endif
550
551 #if defined(MC_DEBUG) && defined(MC_VERBOSE)
552   if (_sg_mc_hash) {
553     // * false positive SHOULD be avoided.
554     // * There MUST not be any false negative.
555
556     XBT_VERB("(%d - %d) State equality hash test is %s %s", num1, num2,
557              (hash_result != 0) == (errors != 0) ? "true" : "false",
558              !hash_result ? "positive" : "negative");
559   }
560 #endif
561
562   return errors > 0 || hash_result;
563
564 }
565
566 }