Logo AND Algorithmique Numérique Distribuée

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