Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
1df6abea1271e4bb45c2b21769a257e8bba0786d
[simgrid.git] / src / mc / mc_global.cpp
1 /* Copyright (c) 2008-2014. 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 #include <cinttypes>
8
9 #include <assert.h>
10 #include <string.h>
11 #include <stdint.h>
12
13 #include "mc_base.h"
14
15 #ifndef _XBT_WIN32
16 #include <unistd.h>
17 #include <sys/wait.h>
18 #include <sys/time.h>
19 #endif
20
21 #include "simgrid/sg_config.h"
22 #include "../surf/surf_private.h"
23 #include "../simix/smx_private.h"
24 #include "xbt/fifo.h"
25 #include "xbt/automaton.h"
26 #include "xbt/dict.h"
27 #include "mc_record.h"
28
29 #ifdef HAVE_MC
30 #include "mc_server.h"
31 #include <libunwind.h>
32 #include <xbt/mmalloc.h>
33 #include "../xbt/mmalloc/mmprivate.h"
34 #include "mc_object_info.h"
35 #include "mc_comm_pattern.h"
36 #include "mc_request.h"
37 #include "mc_safety.h"
38 #include "mc_memory_map.h"
39 #include "mc_snapshot.h"
40 #include "mc_liveness.h"
41 #include "mc_private.h"
42 #include "mc_unw.h"
43 #include "mc_smx.h"
44 #include "mcer_ignore.h"
45 #endif
46 #include "mc_record.h"
47 #include "mc_protocol.h"
48 #include "mc_client.h"
49
50 extern "C" {
51
52 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_global, mc,
53                                 "Logging specific to MC (global)");
54
55 e_mc_mode_t mc_mode;
56
57 double *mc_time = NULL;
58
59 #ifdef HAVE_MC
60 int user_max_depth_reached = 0;
61
62 /* MC global data structures */
63 mc_state_t mc_current_state = NULL;
64 char mc_replay_mode = FALSE;
65
66 __thread mc_comparison_times_t mc_comp_times = NULL;
67 __thread double mc_snapshot_comparison_time;
68 mc_stats_t mc_stats = NULL;
69 mc_global_t initial_global_state = NULL;
70 xbt_fifo_t mc_stack = NULL;
71
72 /* Liveness */
73 xbt_automaton_t _mc_property_automaton = NULL;
74
75 /* Dot output */
76 FILE *dot_output = NULL;
77 const char *colors[13];
78
79
80 /*******************************  Initialisation of MC *******************************/
81 /*********************************************************************************/
82
83 static void MC_init_dot_output()
84 {                               /* FIXME : more colors */
85
86   colors[0] = "blue";
87   colors[1] = "red";
88   colors[2] = "green3";
89   colors[3] = "goldenrod";
90   colors[4] = "brown";
91   colors[5] = "purple";
92   colors[6] = "magenta";
93   colors[7] = "turquoise4";
94   colors[8] = "gray25";
95   colors[9] = "forestgreen";
96   colors[10] = "hotpink";
97   colors[11] = "lightblue";
98   colors[12] = "tan";
99
100   dot_output = fopen(_sg_mc_dot_output_file, "w");
101
102   if (dot_output == NULL) {
103     perror("Error open dot output file");
104     xbt_abort();
105   }
106
107   fprintf(dot_output,
108           "digraph graphname{\n fixedsize=true; rankdir=TB; ranksep=.25; edge [fontsize=12]; node [fontsize=10, shape=circle,width=.5 ]; graph [resolution=20, fontsize=10];\n");
109
110 }
111
112 #ifdef HAVE_MC
113 void MC_init()
114 {
115   mc_time = xbt_new0(double, simix_process_maxpid);
116
117   if (_sg_mc_visited > 0 || _sg_mc_liveness  || _sg_mc_termination || mc_mode == MC_MODE_SERVER) {
118     /* Those requests are handled on the client side and propagated by message
119      * to the server: */
120
121     MC_ignore_heap(mc_time, simix_process_maxpid * sizeof(double));
122
123     smx_process_t process;
124     xbt_swag_foreach(process, simix_global->process_list) {
125       MC_ignore_heap(&(process->process_hookup), sizeof(process->process_hookup));
126     }
127   }
128 }
129
130 void MC_init_model_checker(pid_t pid, int socket)
131 {
132   mc_model_checker = new simgrid::mc::ModelChecker(pid, socket);
133
134   mc_comp_times = xbt_new0(s_mc_comparison_times_t, 1);
135
136   /* Initialize statistics */
137   mc_stats = xbt_new0(s_mc_stats_t, 1);
138   mc_stats->state_size = 1;
139
140   if ((_sg_mc_dot_output_file != NULL) && (_sg_mc_dot_output_file[0] != '\0'))
141     MC_init_dot_output();
142
143   /* Init parmap */
144   //parmap = xbt_parmap_mc_new(xbt_os_get_numcores(), XBT_PARMAP_DEFAULT);
145
146   /* Ignore some variables from xbt/ex.h used by exception e for stacks comparison */
147   MC_ignore_local_variable("e", "*");
148   MC_ignore_local_variable("__ex_cleanup", "*");
149   MC_ignore_local_variable("__ex_mctx_en", "*");
150   MC_ignore_local_variable("__ex_mctx_me", "*");
151   MC_ignore_local_variable("__xbt_ex_ctx_ptr", "*");
152   MC_ignore_local_variable("_log_ev", "*");
153   MC_ignore_local_variable("_throw_ctx", "*");
154   MC_ignore_local_variable("ctx", "*");
155
156   MC_ignore_local_variable("self", "simcall_BODY_mc_snapshot");
157   MC_ignore_local_variable("next_cont"
158     "ext", "smx_ctx_sysv_suspend_serial");
159   MC_ignore_local_variable("i", "smx_ctx_sysv_suspend_serial");
160
161   /* Ignore local variable about time used for tracing */
162   MC_ignore_local_variable("start_time", "*");
163
164   /* Static variable used for tracing */
165   MCer_ignore_global_variable("counter");
166
167   /* SIMIX */
168   MCer_ignore_global_variable("smx_total_comms");
169 }
170 #endif
171
172 /*******************************  Core of MC *******************************/
173 /**************************************************************************/
174
175 void MC_run()
176 {
177   mc_mode = MC_MODE_CLIENT;
178   MC_init();
179   MC_client_main_loop();
180 }
181
182 void MC_exit(void)
183 {
184   xbt_free(mc_time);
185
186   MC_memory_exit();
187   //xbt_abort();
188 }
189
190 #ifdef HAVE_MC
191 int MC_deadlock_check()
192 {
193   if (mc_mode == MC_MODE_SERVER) {
194     int res;
195     if ((res = mc_model_checker->process().send_message(MC_MESSAGE_DEADLOCK_CHECK)))
196       xbt_die("Could not check deadlock state");
197     s_mc_int_message_t message;
198     ssize_t s = mc_model_checker->process().receive_message(message);
199     if (s == -1)
200       xbt_die("Could not receive message");
201     else if (s != sizeof(message) || message.type != MC_MESSAGE_DEADLOCK_CHECK_REPLY) {
202       xbt_die("%s received unexpected message %s (%i, size=%i) "
203         "expected MC_MESSAGE_DEADLOCK_CHECK_REPLY (%i, size=%i)",
204         MC_mode_name(mc_mode),
205         MC_message_type_name(message.type), (int) message.type, (int) s,
206         (int) MC_MESSAGE_DEADLOCK_CHECK_REPLY, (int) sizeof(message)
207         );
208     }
209     else
210       return message.value;
211   }
212
213   int deadlock = FALSE;
214   smx_process_t process;
215   if (xbt_swag_size(simix_global->process_list)) {
216     deadlock = TRUE;
217     xbt_swag_foreach(process, simix_global->process_list) {
218       if (MC_process_is_enabled(process)) {
219         deadlock = FALSE;
220         break;
221       }
222     }
223   }
224   return deadlock;
225 }
226 #endif
227
228 /**
229  * \brief Re-executes from the state at position start all the transitions indicated by
230  *        a given model-checker stack.
231  * \param stack The stack with the transitions to execute.
232  * \param start Start index to begin the re-execution.
233  */
234 void MC_replay(xbt_fifo_t stack)
235 {
236   int value, count = 1;
237   char *req_str;
238   smx_simcall_t req = NULL, saved_req = NULL;
239   xbt_fifo_item_t item, start_item;
240   mc_state_t state;
241   
242   XBT_DEBUG("**** Begin Replay ****");
243
244   /* Intermediate backtracking */
245   if(_sg_mc_checkpoint > 0 || _sg_mc_termination || _sg_mc_visited > 0) {
246     start_item = xbt_fifo_get_first_item(stack);
247     state = (mc_state_t)xbt_fifo_get_item_content(start_item);
248     if(state->system_state){
249       MC_restore_snapshot(state->system_state);
250       if(_sg_mc_comms_determinism || _sg_mc_send_determinism) 
251         MC_restore_communications_pattern(state);
252       return;
253     }
254   }
255
256
257   /* Restore the initial state */
258   MC_restore_snapshot(initial_global_state->snapshot);
259   /* At the moment of taking the snapshot the raw heap was set, so restoring
260    * it will set it back again, we have to unset it to continue  */
261
262   start_item = xbt_fifo_get_last_item(stack);
263
264   if (_sg_mc_comms_determinism || _sg_mc_send_determinism) {
265     // int n = xbt_dynar_length(incomplete_communications_pattern);
266     unsigned n = MC_smx_get_maxpid();
267     assert(n == xbt_dynar_length(incomplete_communications_pattern));
268     assert(n == xbt_dynar_length(initial_communications_pattern));
269     for (unsigned j=0; j < n ; j++) {
270       xbt_dynar_reset((xbt_dynar_t)xbt_dynar_get_as(incomplete_communications_pattern, j, xbt_dynar_t));
271       xbt_dynar_get_as(initial_communications_pattern, j, mc_list_comm_pattern_t)->index_comm = 0;
272     }
273   }
274
275   /* Traverse the stack from the state at position start and re-execute the transitions */
276   for (item = start_item;
277        item != xbt_fifo_get_first_item(stack);
278        item = xbt_fifo_get_prev_item(item)) {
279
280     state = (mc_state_t) xbt_fifo_get_item_content(item);
281     saved_req = MC_state_get_executed_request(state, &value);
282     
283     if (saved_req) {
284       /* because we got a copy of the executed request, we have to fetch the  
285          real one, pointed by the request field of the issuer process */
286
287       const smx_process_t issuer = MC_smx_simcall_get_issuer(saved_req);
288       req = &issuer->simcall;
289
290       /* Debug information */
291       if (XBT_LOG_ISENABLED(mc_global, xbt_log_priority_debug)) {
292         req_str = MC_request_to_string(req, value, MC_REQUEST_SIMIX);
293         XBT_DEBUG("Replay: %s (%p)", req_str, state);
294         xbt_free(req_str);
295       }
296
297       /* TODO : handle test and testany simcalls */
298       e_mc_call_type_t call = MC_CALL_TYPE_NONE;
299       if (_sg_mc_comms_determinism || _sg_mc_send_determinism)
300         call = MC_get_call_type(req);
301
302       MC_simcall_handle(req, value);
303
304       if (_sg_mc_comms_determinism || _sg_mc_send_determinism)
305         MC_handle_comm_pattern(call, req, value, NULL, 1);
306
307       MC_wait_for_requests();
308
309       count++;
310     }
311
312     /* Update statistics */
313     mc_stats->visited_states++;
314     mc_stats->executed_transitions++;
315
316   }
317
318   XBT_DEBUG("**** End Replay ****");
319 }
320
321 void MC_replay_liveness(xbt_fifo_t stack)
322 {
323   xbt_fifo_item_t item;
324   mc_pair_t pair = NULL;
325   mc_state_t state = NULL;
326   smx_simcall_t req = NULL, saved_req = NULL;
327   int value, depth = 1;
328   char *req_str;
329
330   XBT_DEBUG("**** Begin Replay ****");
331
332   /* Intermediate backtracking */
333   if(_sg_mc_checkpoint > 0) {
334     item = xbt_fifo_get_first_item(stack);
335     pair = (mc_pair_t) xbt_fifo_get_item_content(item);
336     if(pair->graph_state->system_state){
337       MC_restore_snapshot(pair->graph_state->system_state);
338       return;
339     }
340   }
341
342   /* Restore the initial state */
343   MC_restore_snapshot(initial_global_state->snapshot);
344
345     /* Traverse the stack from the initial state and re-execute the transitions */
346     for (item = xbt_fifo_get_last_item(stack);
347          item != xbt_fifo_get_first_item(stack);
348          item = xbt_fifo_get_prev_item(item)) {
349
350       pair = (mc_pair_t) xbt_fifo_get_item_content(item);
351
352       state = (mc_state_t) pair->graph_state;
353
354       if (pair->exploration_started) {
355
356         saved_req = MC_state_get_executed_request(state, &value);
357
358         if (saved_req != NULL) {
359           /* because we got a copy of the executed request, we have to fetch the
360              real one, pointed by the request field of the issuer process */
361           const smx_process_t issuer = MC_smx_simcall_get_issuer(saved_req);
362           req = &issuer->simcall;
363
364           /* Debug information */
365           if (XBT_LOG_ISENABLED(mc_global, xbt_log_priority_debug)) {
366             req_str = MC_request_to_string(req, value, MC_REQUEST_SIMIX);
367             XBT_DEBUG("Replay (depth = %d) : %s (%p)", depth, req_str, state);
368             xbt_free(req_str);
369           }
370
371         }
372
373         MC_simcall_handle(req, value);
374         MC_wait_for_requests();
375       }
376
377       /* Update statistics */
378       mc_stats->visited_pairs++;
379       mc_stats->executed_transitions++;
380
381       depth++;
382       
383     }
384
385   XBT_DEBUG("**** End Replay ****");
386 }
387
388 /**
389  * \brief Dumps the contents of a model-checker's stack and shows the actual
390  *        execution trace
391  * \param stack The stack to dump
392  */
393 void MC_dump_stack_safety(xbt_fifo_t stack)
394 {
395   MC_show_stack_safety(stack);
396   
397   mc_state_t state;
398
399   while ((state = (mc_state_t) xbt_fifo_pop(stack)) != NULL)
400     MC_state_delete(state, !state->in_visited_states ? 1 : 0);
401 }
402
403
404 void MC_show_stack_safety(xbt_fifo_t stack)
405 {
406   int value;
407   mc_state_t state;
408   xbt_fifo_item_t item;
409   smx_simcall_t req;
410   char *req_str = NULL;
411
412   for (item = xbt_fifo_get_last_item(stack);
413        item; item = xbt_fifo_get_prev_item(item)) {
414     state = (mc_state_t)xbt_fifo_get_item_content(item);
415     req = MC_state_get_executed_request(state, &value);
416     if (req) {
417       req_str = MC_request_to_string(req, value, MC_REQUEST_EXECUTED);
418       XBT_INFO("%s", req_str);
419       xbt_free(req_str);
420     }
421   }
422 }
423
424 void MC_show_deadlock(smx_simcall_t req)
425 {
426   /*char *req_str = NULL; */
427   XBT_INFO("**************************");
428   XBT_INFO("*** DEAD-LOCK DETECTED ***");
429   XBT_INFO("**************************");
430   XBT_INFO("Locked request:");
431   /*req_str = MC_request_to_string(req);
432      XBT_INFO("%s", req_str);
433      xbt_free(req_str); */
434   XBT_INFO("Counter-example execution trace:");
435   MC_dump_stack_safety(mc_stack);
436   MC_print_statistics(mc_stats);
437 }
438
439 void MC_show_non_termination(void){
440   XBT_INFO("******************************************");
441   XBT_INFO("*** NON-PROGRESSIVE CYCLE DETECTED ***");
442   XBT_INFO("******************************************");
443   XBT_INFO("Counter-example execution trace:");
444   MC_dump_stack_safety(mc_stack);
445   MC_print_statistics(mc_stats);
446 }
447
448
449 void MC_show_stack_liveness(xbt_fifo_t stack)
450 {
451   int value;
452   mc_pair_t pair;
453   xbt_fifo_item_t item;
454   smx_simcall_t req;
455   char *req_str = NULL;
456
457   for (item = xbt_fifo_get_last_item(stack);
458        item; item = xbt_fifo_get_prev_item(item)) {
459     pair = (mc_pair_t) xbt_fifo_get_item_content(item);
460     req = MC_state_get_executed_request(pair->graph_state, &value);
461     if (req && req->call != SIMCALL_NONE) {
462       req_str = MC_request_to_string(req, value, MC_REQUEST_EXECUTED);
463       XBT_INFO("%s", req_str);
464       xbt_free(req_str);
465     }
466   }
467 }
468
469
470 void MC_dump_stack_liveness(xbt_fifo_t stack)
471 {
472   mc_pair_t pair;
473   while ((pair = (mc_pair_t) xbt_fifo_pop(stack)) != NULL)
474     MC_pair_delete(pair);
475 }
476
477 void MC_print_statistics(mc_stats_t stats)
478 {
479   if(_sg_mc_comms_determinism) {
480     if (!initial_global_state->recv_deterministic && initial_global_state->send_deterministic){
481       XBT_INFO("******************************************************");
482       XBT_INFO("**** Only-send-deterministic communication pattern ****");
483       XBT_INFO("******************************************************");
484       XBT_INFO("%s", initial_global_state->recv_diff);
485     }else if(!initial_global_state->send_deterministic && initial_global_state->recv_deterministic) {
486       XBT_INFO("******************************************************");
487       XBT_INFO("**** Only-recv-deterministic communication pattern ****");
488       XBT_INFO("******************************************************");
489       XBT_INFO("%s", initial_global_state->send_diff);
490     }
491   }
492
493   if (stats->expanded_pairs == 0) {
494     XBT_INFO("Expanded states = %lu", stats->expanded_states);
495     XBT_INFO("Visited states = %lu", stats->visited_states);
496   } else {
497     XBT_INFO("Expanded pairs = %lu", stats->expanded_pairs);
498     XBT_INFO("Visited pairs = %lu", stats->visited_pairs);
499   }
500   XBT_INFO("Executed transitions = %lu", stats->executed_transitions);
501   if ((_sg_mc_dot_output_file != NULL) && (_sg_mc_dot_output_file[0] != '\0')) {
502     fprintf(dot_output, "}\n");
503     fclose(dot_output);
504   }
505   if (initial_global_state != NULL && (_sg_mc_comms_determinism || _sg_mc_send_determinism)) {
506     XBT_INFO("Send-deterministic : %s", !initial_global_state->send_deterministic ? "No" : "Yes");
507     if (_sg_mc_comms_determinism)
508       XBT_INFO("Recv-deterministic : %s", !initial_global_state->recv_deterministic ? "No" : "Yes");
509   }
510 }
511
512 void MC_automaton_load(const char *file)
513 {
514   if (_mc_property_automaton == NULL)
515     _mc_property_automaton = xbt_automaton_new();
516
517   xbt_automaton_load(_mc_property_automaton, file);
518 }
519
520 static void register_symbol(xbt_automaton_propositional_symbol_t symbol)
521 {
522   if (mc_mode != MC_MODE_CLIENT)
523     return;
524   s_mc_register_symbol_message_t message;
525   message.type = MC_MESSAGE_REGISTER_SYMBOL;
526   const char* name = xbt_automaton_propositional_symbol_get_name(symbol);
527   if (strlen(name) + 1 > sizeof(message.name))
528     xbt_die("Symbol is too long");
529   strncpy(message.name, name, sizeof(message.name));
530   message.callback = xbt_automaton_propositional_symbol_get_callback(symbol);
531   message.data = xbt_automaton_propositional_symbol_get_data(symbol);
532   MC_client_send_message(&message, sizeof(message));
533 }
534
535 void MC_automaton_new_propositional_symbol(const char *id, int(*fct)(void))
536 {
537   if (_mc_property_automaton == NULL)
538     _mc_property_automaton = xbt_automaton_new();
539
540   xbt_automaton_propositional_symbol_t symbol = xbt_automaton_propositional_symbol_new(_mc_property_automaton, id, fct);
541   register_symbol(symbol);
542 }
543
544 void MC_automaton_new_propositional_symbol_pointer(const char *id, int* value)
545 {
546   if (_mc_property_automaton == NULL)
547     _mc_property_automaton = xbt_automaton_new();
548   xbt_automaton_propositional_symbol_t symbol = xbt_automaton_propositional_symbol_new_pointer(_mc_property_automaton, id, value);
549   register_symbol(symbol);
550 }
551
552 void MC_automaton_new_propositional_symbol_callback(const char* id,
553   xbt_automaton_propositional_symbol_callback_type callback,
554   void* data, xbt_automaton_propositional_symbol_free_function_type free_function)
555 {
556   if (_mc_property_automaton == NULL)
557     _mc_property_automaton = xbt_automaton_new();
558   xbt_automaton_propositional_symbol_t symbol = xbt_automaton_propositional_symbol_new_callback(
559     _mc_property_automaton, id, callback, data, free_function);
560   register_symbol(symbol);
561 }
562
563 // TODO, fix cross-process access (this function is not used)
564 void MC_dump_stacks(FILE* file)
565 {
566   int nstack = 0;
567   stack_region_t current_stack;
568   unsigned cursor;
569   xbt_dynar_foreach(stacks_areas, cursor, current_stack) {
570     unw_context_t * context = (unw_context_t *)current_stack->context;
571     fprintf(file, "Stack %i:\n", nstack);
572
573     int nframe = 0;
574     char buffer[100];
575     unw_cursor_t c;
576     unw_init_local (&c, context);
577     unw_word_t off;
578     do {
579       const char * name = !unw_get_proc_name(&c, buffer, 100, &off) ? buffer : "?";
580 #if defined(__x86_64__)
581       unw_word_t rip = 0;
582       unw_word_t rsp = 0;
583       unw_get_reg(&c, UNW_X86_64_RIP, &rip);
584       unw_get_reg(&c, UNW_X86_64_RSP, &rsp);
585       fprintf(file, "  %i: %s (RIP=0x%" PRIx64 " RSP=0x%" PRIx64 ")\n",
586         nframe, name, rip, rsp);
587 #else
588       fprintf(file, "  %i: %s\n", nframe, name);
589 #endif
590       ++nframe;
591     } while(unw_step(&c));
592
593     ++nstack;
594   }
595 }
596 #endif
597
598 double MC_process_clock_get(smx_process_t process)
599 {
600   if (mc_time) {
601     if (process != NULL)
602       return mc_time[process->pid];
603     else
604       return -1;
605   } else {
606     return 0;
607   }
608 }
609
610 void MC_process_clock_add(smx_process_t process, double amount)
611 {
612   mc_time[process->pid] += amount;
613 }
614
615 #ifdef HAVE_MC
616 void MC_report_assertion_error(void)
617 {
618   XBT_INFO("**************************");
619   XBT_INFO("*** PROPERTY NOT VALID ***");
620   XBT_INFO("**************************");
621   XBT_INFO("Counter-example execution trace:");
622   MC_record_dump_path(mc_stack);
623   MC_dump_stack_safety(mc_stack);
624   MC_print_statistics(mc_stats);
625 }
626
627 void MC_invalidate_cache(void)
628 {
629   if (mc_model_checker)
630     mc_model_checker->process().cache_flags = 0;
631 }
632 #endif
633
634 }