Logo AND Algorithmique Numérique Distribuée

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