Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
d7c436effc1010589adcde7535fecce4483dba99
[simgrid.git] / src / mc / checker / CommunicationDeterminismChecker.cpp
1 /* Copyright (c) 2008-2020. The SimGrid Team. All rights reserved.          */
2
3 /* This program is free software; you can redistribute it and/or modify it
4  * under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include "src/mc/checker/CommunicationDeterminismChecker.hpp"
7 #include "src/kernel/activity/MailboxImpl.hpp"
8 #include "src/mc/Session.hpp"
9 #include "src/mc/mc_config.hpp"
10 #include "src/mc/mc_exit.hpp"
11 #include "src/mc/mc_private.hpp"
12 #include "src/mc/mc_request.hpp"
13 #include "src/mc/mc_smx.hpp"
14
15 #if HAVE_SMPI
16 #include "smpi_request.hpp"
17 #endif
18
19 #include <cstdint>
20
21 using simgrid::mc::remote;
22
23 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_comm_determinism, mc, "Logging specific to MC communication determinism detection");
24
25 /********** Global variables **********/
26
27 std::vector<simgrid::mc::PatternCommunicationList> initial_communications_pattern;
28 std::vector<std::vector<simgrid::mc::PatternCommunication*>> incomplete_communications_pattern;
29
30 /********** Static functions ***********/
31
32 static e_mc_comm_pattern_difference_t compare_comm_pattern(const simgrid::mc::PatternCommunication* comm1,
33                                                            const simgrid::mc::PatternCommunication* comm2)
34 {
35   if(comm1->type != comm2->type)
36     return TYPE_DIFF;
37   if (comm1->rdv != comm2->rdv)
38     return RDV_DIFF;
39   if (comm1->src_proc != comm2->src_proc)
40     return SRC_PROC_DIFF;
41   if (comm1->dst_proc != comm2->dst_proc)
42     return DST_PROC_DIFF;
43   if (comm1->tag != comm2->tag)
44     return TAG_DIFF;
45   if (comm1->data.size() != comm2->data.size())
46     return DATA_SIZE_DIFF;
47   if (comm1->data != comm2->data)
48     return DATA_DIFF;
49   return NONE_DIFF;
50 }
51
52 static char* print_determinism_result(e_mc_comm_pattern_difference_t diff, int process,
53                                       const simgrid::mc::PatternCommunication* comm, unsigned int cursor)
54 {
55   char* type;
56   char* res;
57
58   if (comm->type == simgrid::mc::PatternCommunicationType::send)
59     type = bprintf("The send communications pattern of the process %d is different!", process - 1);
60   else
61     type = bprintf("The recv communications pattern of the process %d is different!", process - 1);
62
63   switch(diff) {
64   case TYPE_DIFF:
65     res = bprintf("%s Different type for communication #%u", type, cursor);
66     break;
67   case RDV_DIFF:
68     res = bprintf("%s Different rdv for communication #%u", type, cursor);
69     break;
70   case TAG_DIFF:
71     res = bprintf("%s Different tag for communication #%u", type, cursor);
72     break;
73   case SRC_PROC_DIFF:
74     res = bprintf("%s Different source for communication #%u", type, cursor);
75     break;
76   case DST_PROC_DIFF:
77     res = bprintf("%s Different destination for communication #%u", type, cursor);
78     break;
79   case DATA_SIZE_DIFF:
80     res = bprintf("%s Different data size for communication #%u", type, cursor);
81     break;
82   case DATA_DIFF:
83     res = bprintf("%s Different data for communication #%u", type, cursor);
84     break;
85   default:
86     res = nullptr;
87     break;
88   }
89
90   return res;
91 }
92
93 static void update_comm_pattern(simgrid::mc::PatternCommunication* comm_pattern,
94                                 simgrid::mc::RemotePtr<simgrid::kernel::activity::CommImpl> comm_addr)
95 {
96   // HACK, type punning
97   simgrid::mc::Remote<simgrid::kernel::activity::CommImpl> temp_comm;
98   mc_model_checker->get_remote_simulation().read(temp_comm, comm_addr);
99   const simgrid::kernel::activity::CommImpl* comm = temp_comm.get_buffer();
100
101   smx_actor_t src_proc =
102       mc_model_checker->get_remote_simulation().resolve_actor(simgrid::mc::remote(comm->src_actor_.get()));
103   smx_actor_t dst_proc =
104       mc_model_checker->get_remote_simulation().resolve_actor(simgrid::mc::remote(comm->dst_actor_.get()));
105   comm_pattern->src_proc = src_proc->get_pid();
106   comm_pattern->dst_proc = dst_proc->get_pid();
107   comm_pattern->src_host = MC_smx_actor_get_host_name(src_proc);
108   comm_pattern->dst_host = MC_smx_actor_get_host_name(dst_proc);
109   if (comm_pattern->data.size() == 0 && comm->src_buff_ != nullptr) {
110     size_t buff_size;
111     mc_model_checker->get_remote_simulation().read(&buff_size, remote(comm->dst_buff_size_));
112     comm_pattern->data.resize(buff_size);
113     mc_model_checker->get_remote_simulation().read_bytes(comm_pattern->data.data(), comm_pattern->data.size(),
114                                                          remote(comm->src_buff_));
115   }
116 }
117
118 namespace simgrid {
119 namespace mc {
120
121 void CommunicationDeterminismChecker::deterministic_comm_pattern(int process, const PatternCommunication* comm,
122                                                                  int backtracking)
123 {
124   if (not backtracking) {
125     PatternCommunicationList& list      = initial_communications_pattern[process];
126     e_mc_comm_pattern_difference_t diff = compare_comm_pattern(list.list[list.index_comm].get(), comm);
127
128     if (diff != NONE_DIFF) {
129       if (comm->type == PatternCommunicationType::send) {
130         this->send_deterministic = 0;
131         if (this->send_diff != nullptr)
132           xbt_free(this->send_diff);
133         this->send_diff = print_determinism_result(diff, process, comm, list.index_comm + 1);
134       } else {
135         this->recv_deterministic = 0;
136         if (this->recv_diff != nullptr)
137           xbt_free(this->recv_diff);
138         this->recv_diff = print_determinism_result(diff, process, comm, list.index_comm + 1);
139       }
140       if (_sg_mc_send_determinism && not this->send_deterministic) {
141         XBT_INFO("*********************************************************");
142         XBT_INFO("***** Non-send-deterministic communications pattern *****");
143         XBT_INFO("*********************************************************");
144         XBT_INFO("%s", this->send_diff);
145         xbt_free(this->send_diff);
146         this->send_diff = nullptr;
147         mc::session->log_state();
148         mc_model_checker->exit(SIMGRID_MC_EXIT_NON_DETERMINISM);
149       } else if (_sg_mc_comms_determinism && (not this->send_deterministic && not this->recv_deterministic)) {
150         XBT_INFO("****************************************************");
151         XBT_INFO("***** Non-deterministic communications pattern *****");
152         XBT_INFO("****************************************************");
153         if (this->send_diff) {
154           XBT_INFO("%s", this->send_diff);
155           xbt_free(this->send_diff);
156           this->send_diff = nullptr;
157         }
158         if (this->recv_diff) {
159           XBT_INFO("%s", this->recv_diff);
160           xbt_free(this->recv_diff);
161           this->recv_diff = nullptr;
162         }
163         mc::session->log_state();
164         mc_model_checker->exit(SIMGRID_MC_EXIT_NON_DETERMINISM);
165       }
166     }
167   }
168 }
169
170 /********** Non Static functions ***********/
171
172 void CommunicationDeterminismChecker::get_comm_pattern(smx_simcall_t request, e_mc_call_type_t call_type,
173                                                        int backtracking)
174 {
175   const smx_actor_t issuer = MC_smx_simcall_get_issuer(request);
176   const mc::PatternCommunicationList& initial_pattern          = initial_communications_pattern[issuer->get_pid()];
177   const std::vector<PatternCommunication*>& incomplete_pattern = incomplete_communications_pattern[issuer->get_pid()];
178
179   std::unique_ptr<PatternCommunication> pattern(new PatternCommunication());
180   pattern->index = initial_pattern.index_comm + incomplete_pattern.size();
181
182   if (call_type == MC_CALL_TYPE_SEND) {
183     /* Create comm pattern */
184     pattern->type      = PatternCommunicationType::send;
185     pattern->comm_addr = static_cast<kernel::activity::CommImpl*>(simcall_comm_isend__getraw__result(request));
186
187     Remote<kernel::activity::CommImpl> temp_synchro;
188     mc_model_checker->get_remote_simulation().read(
189         temp_synchro, remote(static_cast<kernel::activity::CommImpl*>(pattern->comm_addr)));
190     const kernel::activity::CommImpl* synchro = static_cast<kernel::activity::CommImpl*>(temp_synchro.get_buffer());
191
192     char* remote_name = mc_model_checker->get_remote_simulation().read<char*>(RemotePtr<char*>(
193         (uint64_t)(synchro->get_mailbox() ? &synchro->get_mailbox()->name_ : &synchro->mbox_cpy->name_)));
194     pattern->rdv      = mc_model_checker->get_remote_simulation().read_string(RemotePtr<char>(remote_name));
195     pattern->src_proc =
196         mc_model_checker->get_remote_simulation().resolve_actor(mc::remote(synchro->src_actor_.get()))->get_pid();
197     pattern->src_host = MC_smx_actor_get_host_name(issuer);
198
199 #if HAVE_SMPI
200     simgrid::smpi::Request mpi_request;
201     mc_model_checker->get_remote_simulation().read(
202         &mpi_request, remote(static_cast<smpi::Request*>(simcall_comm_isend__get__data(request))));
203     pattern->tag = mpi_request.tag();
204 #endif
205
206     if (synchro->src_buff_ != nullptr) {
207       pattern->data.resize(synchro->src_buff_size_);
208       mc_model_checker->get_remote_simulation().read_bytes(pattern->data.data(), pattern->data.size(),
209                                                            remote(synchro->src_buff_));
210     }
211 #if HAVE_SMPI
212     if(mpi_request.detached()){
213       if (this->initial_communications_pattern_done) {
214         /* Evaluate comm determinism */
215         this->deterministic_comm_pattern(pattern->src_proc, pattern.get(), backtracking);
216         initial_communications_pattern[pattern->src_proc].index_comm++;
217       } else {
218         /* Store comm pattern */
219         initial_communications_pattern[pattern->src_proc].list.push_back(std::move(pattern));
220       }
221       return;
222     }
223 #endif
224   } else if (call_type == MC_CALL_TYPE_RECV) {
225     pattern->type      = PatternCommunicationType::receive;
226     pattern->comm_addr = static_cast<kernel::activity::CommImpl*>(simcall_comm_irecv__getraw__result(request));
227
228 #if HAVE_SMPI
229     smpi::Request mpi_request;
230     mc_model_checker->get_remote_simulation().read(
231         &mpi_request, remote(static_cast<smpi::Request*>(simcall_comm_irecv__get__data(request))));
232     pattern->tag = mpi_request.tag();
233 #endif
234
235     Remote<kernel::activity::CommImpl> temp_comm;
236     mc_model_checker->get_remote_simulation().read(
237         temp_comm, remote(static_cast<kernel::activity::CommImpl*>(pattern->comm_addr)));
238     const kernel::activity::CommImpl* comm = temp_comm.get_buffer();
239
240     char* remote_name;
241     mc_model_checker->get_remote_simulation().read(
242         &remote_name, remote(comm->get_mailbox() ? &xbt::string::to_string_data(comm->get_mailbox()->name_).data
243                                                  : &xbt::string::to_string_data(comm->mbox_cpy->name_).data));
244     pattern->rdv = mc_model_checker->get_remote_simulation().read_string(RemotePtr<char>(remote_name));
245     pattern->dst_proc =
246         mc_model_checker->get_remote_simulation().resolve_actor(mc::remote(comm->dst_actor_.get()))->get_pid();
247     pattern->dst_host = MC_smx_actor_get_host_name(issuer);
248   } else
249     xbt_die("Unexpected call_type %i", (int) call_type);
250
251   XBT_DEBUG("Insert incomplete comm pattern %p for process %ld", pattern.get(), issuer->get_pid());
252   incomplete_communications_pattern[issuer->get_pid()].push_back(pattern.release());
253 }
254
255 void CommunicationDeterminismChecker::complete_comm_pattern(RemotePtr<kernel::activity::CommImpl> comm_addr,
256                                                             unsigned int issuer, int backtracking)
257 {
258   /* Complete comm pattern */
259   std::vector<PatternCommunication*>& incomplete_pattern = incomplete_communications_pattern[issuer];
260   auto current_comm_pattern =
261       std::find_if(begin(incomplete_pattern), end(incomplete_pattern),
262                    [&comm_addr](const PatternCommunication* comm) { return remote(comm->comm_addr) == comm_addr; });
263   if (current_comm_pattern == std::end(incomplete_pattern))
264     xbt_die("Corresponding communication not found!");
265
266   update_comm_pattern(*current_comm_pattern, comm_addr);
267   std::unique_ptr<PatternCommunication> comm_pattern(*current_comm_pattern);
268   XBT_DEBUG("Remove incomplete comm pattern for process %u at cursor %zd", issuer,
269             std::distance(begin(incomplete_pattern), current_comm_pattern));
270   incomplete_pattern.erase(current_comm_pattern);
271
272   if (this->initial_communications_pattern_done) {
273     /* Evaluate comm determinism */
274     this->deterministic_comm_pattern(issuer, comm_pattern.get(), backtracking);
275     initial_communications_pattern[issuer].index_comm++;
276   } else {
277     /* Store comm pattern */
278     initial_communications_pattern[issuer].list.push_back(std::move(comm_pattern));
279   }
280 }
281
282 CommunicationDeterminismChecker::CommunicationDeterminismChecker(Session& s) : Checker(s)
283 {
284 }
285
286 CommunicationDeterminismChecker::~CommunicationDeterminismChecker() = default;
287
288 RecordTrace CommunicationDeterminismChecker::get_record_trace() // override
289 {
290   RecordTrace res;
291   for (auto const& state : stack_)
292     res.push_back(state->get_transition());
293   return res;
294 }
295
296 std::vector<std::string> CommunicationDeterminismChecker::get_textual_trace() // override
297 {
298   std::vector<std::string> trace;
299   for (auto const& state : stack_) {
300     smx_simcall_t req = &state->executed_req_;
301     if (req)
302       trace.push_back(request_to_string(req, state->transition_.argument_, RequestType::executed));
303   }
304   return trace;
305 }
306
307 void CommunicationDeterminismChecker::log_state() // override
308 {
309   if (_sg_mc_comms_determinism) {
310     if (this->send_deterministic && not this->recv_deterministic) {
311       XBT_INFO("*******************************************************");
312       XBT_INFO("**** Only-send-deterministic communication pattern ****");
313       XBT_INFO("*******************************************************");
314       XBT_INFO("%s", this->recv_diff);
315     }
316     if (not this->send_deterministic && this->recv_deterministic) {
317       XBT_INFO("*******************************************************");
318       XBT_INFO("**** Only-recv-deterministic communication pattern ****");
319       XBT_INFO("*******************************************************");
320       XBT_INFO("%s", this->send_diff);
321     }
322   }
323   XBT_INFO("Expanded states = %lu", expanded_states_count_);
324   XBT_INFO("Visited states = %lu", mc_model_checker->visited_states);
325   XBT_INFO("Executed transitions = %lu", mc_model_checker->executed_transitions);
326   XBT_INFO("Send-deterministic : %s", this->send_deterministic ? "Yes" : "No");
327   if (_sg_mc_comms_determinism)
328     XBT_INFO("Recv-deterministic : %s", this->recv_deterministic ? "Yes" : "No");
329 }
330
331 void CommunicationDeterminismChecker::prepare()
332 {
333   const int maxpid = MC_smx_get_maxpid();
334
335   initial_communications_pattern.resize(maxpid);
336   incomplete_communications_pattern.resize(maxpid);
337
338   std::unique_ptr<State> initial_state(new State(++expanded_states_count_));
339
340   XBT_DEBUG("********* Start communication determinism verification *********");
341
342   /* Get an enabled actor and insert it in the interleave set of the initial state */
343   for (auto& actor : mc_model_checker->get_remote_simulation().actors())
344     if (mc::actor_is_enabled(actor.copy.get_buffer()))
345       initial_state->add_interleaving_set(actor.copy.get_buffer());
346
347   stack_.push_back(std::move(initial_state));
348 }
349
350 static inline bool all_communications_are_finished()
351 {
352   for (size_t current_actor = 1; current_actor < MC_smx_get_maxpid(); current_actor++) {
353     if (not incomplete_communications_pattern[current_actor].empty()) {
354       XBT_DEBUG("Some communications are not finished, cannot stop the exploration! State not visited.");
355       return false;
356     }
357   }
358   return true;
359 }
360
361 void CommunicationDeterminismChecker::restoreState()
362 {
363   /* Intermediate backtracking */
364   State* last_state = stack_.back().get();
365   if (last_state->system_state_) {
366     last_state->system_state_->restore(&mc_model_checker->get_remote_simulation());
367     MC_restore_communications_pattern(last_state);
368     return;
369   }
370
371   /* Restore the initial state */
372   mc::session->restore_initial_state();
373
374   unsigned n = MC_smx_get_maxpid();
375   assert(n == incomplete_communications_pattern.size());
376   assert(n == initial_communications_pattern.size());
377   for (unsigned j=0; j < n ; j++) {
378     incomplete_communications_pattern[j].clear();
379     initial_communications_pattern[j].index_comm = 0;
380   }
381
382   /* Traverse the stack from the state at position start and re-execute the transitions */
383   for (std::unique_ptr<simgrid::mc::State> const& state : stack_) {
384     if (state == stack_.back())
385       break;
386
387     int req_num             = state->transition_.argument_;
388     const s_smx_simcall* saved_req = &state->executed_req_;
389     xbt_assert(saved_req);
390
391     /* because we got a copy of the executed request, we have to fetch the
392        real one, pointed by the request field of the issuer process */
393
394     const smx_actor_t issuer = MC_smx_simcall_get_issuer(saved_req);
395     smx_simcall_t req = &issuer->simcall;
396
397     /* TODO : handle test and testany simcalls */
398     e_mc_call_type_t call = MC_get_call_type(req);
399     mc_model_checker->handle_simcall(state->transition_);
400     MC_handle_comm_pattern(call, req, req_num, 1);
401     mc_model_checker->wait_for_requests();
402
403     /* Update statistics */
404     mc_model_checker->visited_states++;
405     mc_model_checker->executed_transitions++;
406   }
407 }
408
409 void CommunicationDeterminismChecker::real_run()
410 {
411   std::unique_ptr<VisitedState> visited_state = nullptr;
412   smx_simcall_t req = nullptr;
413
414   while (not stack_.empty()) {
415     /* Get current state */
416     State* cur_state = stack_.back().get();
417
418     XBT_DEBUG("**************************************************");
419     XBT_DEBUG("Exploration depth = %zu (state = %d, interleaved processes = %zu)", stack_.size(), cur_state->num_,
420               cur_state->interleave_size());
421
422     /* Update statistics */
423     mc_model_checker->visited_states++;
424
425     if (stack_.size() <= (std::size_t)_sg_mc_max_depth)
426       req = MC_state_choose_request(cur_state);
427     else
428       req = nullptr;
429
430     if (req != nullptr && visited_state == nullptr) {
431       int req_num = cur_state->transition_.argument_;
432
433       XBT_DEBUG("Execute: %s", request_to_string(req, req_num, RequestType::simix).c_str());
434
435       std::string req_str;
436       if (dot_output != nullptr)
437         req_str = request_get_dot_output(req, req_num);
438
439       mc_model_checker->executed_transitions++;
440
441       /* TODO : handle test and testany simcalls */
442       e_mc_call_type_t call = MC_CALL_TYPE_NONE;
443       if (_sg_mc_comms_determinism || _sg_mc_send_determinism)
444         call = MC_get_call_type(req);
445
446       /* Answer the request */
447       mc_model_checker->handle_simcall(cur_state->transition_);
448       /* After this call req is no longer useful */
449
450       MC_handle_comm_pattern(call, req, req_num, 0);
451
452       /* Wait for requests (schedules processes) */
453       mc_model_checker->wait_for_requests();
454
455       /* Create the new expanded state */
456       std::unique_ptr<State> next_state(new State(++expanded_states_count_));
457
458       /* If comm determinism verification, we cannot stop the exploration if some communications are not finished (at
459        * least, data are transferred). These communications  are incomplete and they cannot be analyzed and compared
460        * with the initial pattern. */
461       bool compare_snapshots = this->initial_communications_pattern_done && all_communications_are_finished();
462
463       if (_sg_mc_max_visited_states != 0)
464         visited_state = visited_states_.addVisitedState(expanded_states_count_, next_state.get(), compare_snapshots);
465       else
466         visited_state = nullptr;
467
468       if (visited_state == nullptr) {
469         /* Get enabled actors and insert them in the interleave set of the next state */
470         for (auto& actor : mc_model_checker->get_remote_simulation().actors())
471           if (simgrid::mc::actor_is_enabled(actor.copy.get_buffer()))
472             next_state->add_interleaving_set(actor.copy.get_buffer());
473
474         if (dot_output != nullptr)
475           fprintf(dot_output, "\"%d\" -> \"%d\" [%s];\n", cur_state->num_, next_state->num_, req_str.c_str());
476
477       } else if (dot_output != nullptr)
478         fprintf(dot_output, "\"%d\" -> \"%d\" [%s];\n", cur_state->num_,
479                 visited_state->original_num == -1 ? visited_state->num : visited_state->original_num, req_str.c_str());
480
481       stack_.push_back(std::move(next_state));
482     } else {
483       if (stack_.size() > (std::size_t) _sg_mc_max_depth)
484         XBT_WARN("/!\\ Max depth reached! /!\\ ");
485       else if (visited_state != nullptr)
486         XBT_DEBUG("State already visited (equal to state %d), exploration stopped on this path.",
487             visited_state->original_num == -1 ? visited_state->num : visited_state->original_num);
488       else
489         XBT_DEBUG("There are no more processes to interleave. (depth %zu)", stack_.size());
490
491       this->initial_communications_pattern_done = true;
492
493       /* Trash the current state, no longer needed */
494       XBT_DEBUG("Delete state %d at depth %zu", cur_state->num_, stack_.size());
495       stack_.pop_back();
496
497       visited_state = nullptr;
498
499       /* Check for deadlocks */
500       if (mc_model_checker->checkDeadlock()) {
501         MC_show_deadlock();
502         throw simgrid::mc::DeadlockError();
503       }
504
505       while (not stack_.empty()) {
506         std::unique_ptr<State> state(std::move(stack_.back()));
507         stack_.pop_back();
508         if (state->interleave_size() && stack_.size() < (std::size_t)_sg_mc_max_depth) {
509           /* We found a back-tracking point, let's loop */
510           XBT_DEBUG("Back-tracking to state %d at depth %zu", state->num_, stack_.size() + 1);
511           stack_.push_back(std::move(state));
512
513           this->restoreState();
514
515           XBT_DEBUG("Back-tracking to state %d at depth %zu done", stack_.back()->num_, stack_.size());
516
517           break;
518         } else {
519           XBT_DEBUG("Delete state %d at depth %zu", state->num_, stack_.size() + 1);
520         }
521       }
522     }
523   }
524
525   mc::session->log_state();
526 }
527
528 void CommunicationDeterminismChecker::run()
529 {
530   XBT_INFO("Check communication determinism");
531   mc::session->initialize();
532
533   this->prepare();
534   this->real_run();
535 }
536
537 Checker* createCommunicationDeterminismChecker(Session& s)
538 {
539   return new CommunicationDeterminismChecker(s);
540 }
541
542 } // namespace mc
543 } // namespace simgrid