X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/de2ba1766285962d449105925be099707e0102e6..03b941b5d37f891da6c5b00cb8b9ce4e348eb0df:/src/mc/mc_liveness.c diff --git a/src/mc/mc_liveness.c b/src/mc/mc_liveness.c index cb1b91b5ed..fa20959f6e 100644 --- a/src/mc/mc_liveness.c +++ b/src/mc/mc_liveness.c @@ -11,6 +11,7 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_liveness, mc, "Logging specific to algorithms for liveness properties verification"); xbt_dynar_t reached_pairs; +xbt_dynar_t visited_pairs; xbt_dynar_t successors; int create_dump(int pair) @@ -50,9 +51,144 @@ int create_dump(int pair) return 0; } +void MC_print_comparison_times_statistics(mc_comparison_times_t ct){ + + XBT_DEBUG("Comparisons done : %d", ct->nb_comparisons); + + double total, min, max; + unsigned int cursor; + + if(xbt_dynar_length(ct->chunks_used_comparison_times) > 0){ + cursor = 0; + total = 0.0; + max = 0.0; + min = xbt_dynar_get_as(ct->chunks_used_comparison_times, cursor, double); + while(cursor < xbt_dynar_length(ct->chunks_used_comparison_times) - 1){ + total += xbt_dynar_get_as(ct->chunks_used_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->chunks_used_comparison_times, cursor, double) > max) + max = xbt_dynar_get_as(ct->chunks_used_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->chunks_used_comparison_times, cursor, double) < min) + min = xbt_dynar_get_as(ct->chunks_used_comparison_times, cursor, double); + cursor++; + } + XBT_DEBUG("Chunks used comparison -- Different states : %lu/%d, time (in seconds) : average = %lf, max = %lf, min = %lf", xbt_dynar_length(ct->chunks_used_comparison_times), ct->nb_comparisons, total/xbt_dynar_length(ct->chunks_used_comparison_times), max, min); + } + + if(xbt_dynar_length(ct->stacks_sizes_comparison_times) > 0){ + cursor = 0; + total = 0.0; + max = 0.0; + min = xbt_dynar_get_as(ct->stacks_sizes_comparison_times, cursor, double); + while(cursor < xbt_dynar_length(ct->stacks_sizes_comparison_times) - 1){ + total += xbt_dynar_get_as(ct->stacks_sizes_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->stacks_sizes_comparison_times, cursor, double) > max) + max = xbt_dynar_get_as(ct->stacks_sizes_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->stacks_sizes_comparison_times, cursor, double) < min) + min = xbt_dynar_get_as(ct->stacks_sizes_comparison_times, cursor, double); + cursor++; + } + XBT_DEBUG("Stacks sizes comparison -- Different states : %lu/%d, time (in seconds) : average = %lf, max = %lf, min = %lf", xbt_dynar_length(ct->stacks_sizes_comparison_times), ct->nb_comparisons, total/xbt_dynar_length(ct->stacks_sizes_comparison_times), max, min); + } + + if(xbt_dynar_length(ct->program_data_segment_comparison_times) > 0){ + cursor = 0; + total = 0.0; + max = 0.0; + min = xbt_dynar_get_as(ct->program_data_segment_comparison_times, cursor, double); + while(cursor < xbt_dynar_length(ct->program_data_segment_comparison_times) - 1){ + total += xbt_dynar_get_as(ct->program_data_segment_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->program_data_segment_comparison_times, cursor, double) > max) + max = xbt_dynar_get_as(ct->program_data_segment_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->program_data_segment_comparison_times, cursor, double) < min) + min = xbt_dynar_get_as(ct->program_data_segment_comparison_times, cursor, double); + cursor++; + } + XBT_DEBUG("Program data/bss segments comparison -- Different states : %lu/%d, time (in seconds) : average = %lf, max = %lf, min = %lf", xbt_dynar_length(ct->program_data_segment_comparison_times), ct->nb_comparisons, total/xbt_dynar_length(ct->program_data_segment_comparison_times), max, min); + } + + if(xbt_dynar_length(ct->libsimgrid_data_segment_comparison_times) > 0){ + cursor = 0; + total = 0.0; + max = 0.0; + min = xbt_dynar_get_as(ct->libsimgrid_data_segment_comparison_times, cursor, double); + while(cursor < xbt_dynar_length(ct->libsimgrid_data_segment_comparison_times) - 1){ + total += xbt_dynar_get_as(ct->libsimgrid_data_segment_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->libsimgrid_data_segment_comparison_times, cursor, double) > max) + max = xbt_dynar_get_as(ct->libsimgrid_data_segment_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->libsimgrid_data_segment_comparison_times, cursor, double) < min) + min = xbt_dynar_get_as(ct->libsimgrid_data_segment_comparison_times, cursor, double); + cursor++; + } + XBT_DEBUG("Libsimgrid data/bss segments comparison -- Different states : %lu/%d, time (in seconds) : average = %lf, max = %lf, min = %lf", xbt_dynar_length(ct->libsimgrid_data_segment_comparison_times), ct->nb_comparisons, total/xbt_dynar_length(ct->libsimgrid_data_segment_comparison_times), max, min); + } + + if(xbt_dynar_length(ct->heap_comparison_times) > 0){ + cursor = 0; + total = 0.0; + max = 0.0; + min = xbt_dynar_get_as(ct->heap_comparison_times, cursor, double); + while(cursor < xbt_dynar_length(ct->heap_comparison_times) - 1){ + total += xbt_dynar_get_as(ct->heap_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->heap_comparison_times, cursor, double) > max) + max = xbt_dynar_get_as(ct->heap_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->heap_comparison_times, cursor, double) < min) + min = xbt_dynar_get_as(ct->heap_comparison_times, cursor, double); + cursor++; + } + XBT_DEBUG("Heap comparison -- Different states : %lu/%d, time (in seconds) : average = %lf, max = %lf, min = %lf", xbt_dynar_length(ct->heap_comparison_times), ct->nb_comparisons, total/xbt_dynar_length(ct->heap_comparison_times), max, min); + } + + if(xbt_dynar_length(ct->stacks_comparison_times) > 0){ + cursor = 0; + total = 0.0; + max = 0.0; + min = xbt_dynar_get_as(ct->stacks_comparison_times, cursor, double); + while(cursor < xbt_dynar_length(ct->stacks_comparison_times) - 1){ + total += xbt_dynar_get_as(ct->stacks_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->stacks_comparison_times, cursor, double) > max) + max = xbt_dynar_get_as(ct->stacks_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->stacks_comparison_times, cursor, double) < min) + min = xbt_dynar_get_as(ct->stacks_comparison_times, cursor, double); + cursor++; + } + XBT_DEBUG("Stacks comparison -- Different states : %lu/%d, time (in seconds) : average = %lf, max = %lf, min = %lf", xbt_dynar_length(ct->stacks_comparison_times), ct->nb_comparisons, total/xbt_dynar_length(ct->stacks_comparison_times), max, min); + } + + if(xbt_dynar_length(ct->snapshot_comparison_times) > 0){ + cursor = 0; + total = 0.0; + max = 0.0; + min = xbt_dynar_get_as(ct->snapshot_comparison_times, cursor, double); + while(cursor < xbt_dynar_length(ct->snapshot_comparison_times) - 1){ + total += xbt_dynar_get_as(ct->snapshot_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->snapshot_comparison_times, cursor, double) > max) + max = xbt_dynar_get_as(ct->snapshot_comparison_times, cursor, double); + if(xbt_dynar_get_as(ct->snapshot_comparison_times, cursor, double) < min) + min = xbt_dynar_get_as(ct->snapshot_comparison_times, cursor, double); + cursor++; + } + XBT_DEBUG("Snapshot comparison (Whole funnel) -- Different states : %lu/%d, time (in seconds) : average = %lf, max = %lf, min = %lf", xbt_dynar_length(ct->snapshot_comparison_times), ct->nb_comparisons, total/xbt_dynar_length(ct->snapshot_comparison_times), max, min); + } + +} + +mc_comparison_times_t new_comparison_times(){ + mc_comparison_times_t ct = NULL; + ct = xbt_new0(s_mc_comparison_times_t, 1); + ct->nb_comparisons = 0; + ct->snapshot_comparison_times = xbt_dynar_new(sizeof(double), NULL); + ct->chunks_used_comparison_times = xbt_dynar_new(sizeof(double), NULL); + ct->stacks_sizes_comparison_times = xbt_dynar_new(sizeof(double), NULL); + ct->program_data_segment_comparison_times = xbt_dynar_new(sizeof(double), NULL); + ct->libsimgrid_data_segment_comparison_times = xbt_dynar_new(sizeof(double), NULL); + ct->heap_comparison_times = xbt_dynar_new(sizeof(double), NULL); + ct->stacks_comparison_times = xbt_dynar_new(sizeof(double), NULL); + return ct; +} + int reached(xbt_state_t st){ - raw_mem_set = (mmalloc_get_current_heap() == raw_heap); + int raw_mem_set = (mmalloc_get_current_heap() == raw_heap); MC_SET_RAW_MEM; @@ -61,6 +197,7 @@ int reached(xbt_state_t st){ new_pair->nb = xbt_dynar_length(reached_pairs) + 1; new_pair->automaton_state = st; new_pair->prop_ato = xbt_dynar_new(sizeof(int), NULL); + new_pair->comparison_times = new_comparison_times(); new_pair->system_state = MC_take_snapshot_liveness(); /* Get values of propositional symbols */ @@ -96,10 +233,11 @@ int reached(xbt_state_t st){ mc_pair_reached_t pair_test = NULL; xbt_dynar_foreach(reached_pairs, cursor, pair_test){ - XBT_INFO("Pair reached #%d", pair_test->nb); + if(XBT_LOG_ISENABLED(mc_liveness, xbt_log_priority_debug)) + XBT_DEBUG("****** Pair reached #%d ******", pair_test->nb); if(automaton_state_compare(pair_test->automaton_state, st) == 0){ if(propositional_symbols_compare_value(pair_test->prop_ato, new_pair->prop_ato) == 0){ - if(snapshot_compare(new_pair->system_state, pair_test->system_state) == 0){ + if(snapshot_compare(new_pair->system_state, pair_test->system_state, new_pair->comparison_times, pair_test->comparison_times) == 0){ if(raw_mem_set) MC_SET_RAW_MEM; @@ -114,6 +252,10 @@ int reached(xbt_state_t st){ }else{ XBT_INFO("Different automaton state"); } + if(pair_test->comparison_times != NULL && XBT_LOG_ISENABLED(mc_liveness, xbt_log_priority_debug)){ + XBT_DEBUG("*** Comparison times statistics ***"); + MC_print_comparison_times_statistics(pair_test->comparison_times); + } } /* New pair reached */ @@ -134,7 +276,7 @@ int reached(xbt_state_t st){ void set_pair_reached(xbt_state_t st){ - raw_mem_set = (mmalloc_get_current_heap() == raw_heap); + int raw_mem_set = (mmalloc_get_current_heap() == raw_heap); MC_SET_RAW_MEM; @@ -143,6 +285,7 @@ void set_pair_reached(xbt_state_t st){ pair->nb = xbt_dynar_length(reached_pairs) + 1; pair->automaton_state = st; pair->prop_ato = xbt_dynar_new(sizeof(int), NULL); + pair->comparison_times = new_comparison_times(); pair->system_state = MC_take_snapshot_liveness(); /* Get values of propositional symbols */ @@ -166,6 +309,91 @@ void set_pair_reached(xbt_state_t st){ } +int visited(xbt_state_t st){ + + if(_surf_mc_stateful == 0) + return 0; + + int raw_mem_set = (mmalloc_get_current_heap() == raw_heap); + + MC_SET_RAW_MEM; + + mc_pair_visited_t new_pair = NULL; + new_pair = xbt_new0(s_mc_pair_visited_t, 1); + new_pair->automaton_state = st; + new_pair->prop_ato = xbt_dynar_new(sizeof(int), NULL); + new_pair->system_state = MC_take_snapshot_liveness(); + + /* Get values of propositional symbols */ + int res; + int_f_void_t f; + unsigned int cursor = 0; + xbt_propositional_symbol_t ps = NULL; + xbt_dynar_foreach(_mc_property_automaton->propositional_symbols, cursor, ps){ + f = (int_f_void_t)ps->function; + res = (*f)(); + xbt_dynar_push_as(new_pair->prop_ato, int, res); + } + + MC_UNSET_RAW_MEM; + + if(xbt_dynar_is_empty(visited_pairs)){ + + MC_SET_RAW_MEM; + /* New pair visited */ + xbt_dynar_push(visited_pairs, &new_pair); + MC_UNSET_RAW_MEM; + + if(raw_mem_set) + MC_SET_RAW_MEM; + + return 0; + + }else{ + + MC_SET_RAW_MEM; + + cursor = 0; + mc_pair_visited_t pair_test = NULL; + + xbt_dynar_foreach(visited_pairs, cursor, pair_test){ + if(XBT_LOG_ISENABLED(mc_liveness, xbt_log_priority_debug)) + XBT_DEBUG("****** Pair visited #%d ******", cursor + 1); + if(automaton_state_compare(pair_test->automaton_state, st) == 0){ + if(propositional_symbols_compare_value(pair_test->prop_ato, new_pair->prop_ato) == 0){ + if(snapshot_compare(new_pair->system_state, pair_test->system_state, NULL, NULL) == 0){ + if(raw_mem_set) + MC_SET_RAW_MEM; + else + MC_UNSET_RAW_MEM; + + return 1; + } + }else{ + XBT_INFO("Different values of propositional symbols"); + } + }else{ + XBT_INFO("Different automaton state"); + } + } + + if(xbt_dynar_length(visited_pairs) == _surf_mc_stateful){ + xbt_dynar_remove_at(visited_pairs, 0, NULL); + } + + /* New pair visited */ + xbt_dynar_push(visited_pairs, &new_pair); + + MC_UNSET_RAW_MEM; + + if(raw_mem_set) + MC_SET_RAW_MEM; + + return 0; + + } +} + void MC_pair_delete(mc_pair_t pair){ xbt_free(pair->graph_state->proc_status); xbt_free(pair->graph_state); @@ -214,6 +442,19 @@ int MC_automaton_evaluate_label(xbt_exp_label_t l){ /********************* Double-DFS stateless *******************/ +void pair_visited_free(mc_pair_visited_t pair){ + if(pair){ + pair->automaton_state = NULL; + xbt_dynar_free(&(pair->prop_ato)); + MC_free_snapshot(pair->system_state); + xbt_free(pair); + } +} + +void pair_visited_free_voidp(void *p){ + pair_visited_free((mc_pair_visited_t) * (void **) p); +} + void pair_stateless_free(mc_pair_stateless_t pair){ xbt_free(pair->graph_state->system_state); xbt_free(pair->graph_state->proc_status); @@ -239,6 +480,15 @@ void pair_reached_free(mc_pair_reached_t pair){ if(pair){ pair->automaton_state = NULL; xbt_dynar_free(&(pair->prop_ato)); + if(pair->comparison_times != NULL){ + xbt_dynar_free(&(pair->comparison_times->snapshot_comparison_times)); + xbt_dynar_free(&(pair->comparison_times->chunks_used_comparison_times)); + xbt_dynar_free(&(pair->comparison_times->stacks_sizes_comparison_times)); + xbt_dynar_free(&(pair->comparison_times->program_data_segment_comparison_times)); + xbt_dynar_free(&(pair->comparison_times->libsimgrid_data_segment_comparison_times)); + xbt_dynar_free(&(pair->comparison_times->heap_comparison_times)); + xbt_dynar_free(&(pair->comparison_times->stacks_comparison_times)); + } MC_free_snapshot(pair->system_state); xbt_free(pair); } @@ -250,7 +500,7 @@ void pair_reached_free_voidp(void *p){ void MC_ddfs_init(void){ - raw_mem_set = (mmalloc_get_current_heap() == raw_heap); + initial_state_liveness->raw_mem_set = (mmalloc_get_current_heap() == raw_heap); XBT_INFO("**************************************************"); XBT_INFO("Double-DFS init"); @@ -273,10 +523,11 @@ void MC_ddfs_init(void){ } reached_pairs = xbt_dynar_new(sizeof(mc_pair_reached_t), pair_reached_free_voidp); + visited_pairs = xbt_dynar_new(sizeof(mc_pair_visited_t), pair_visited_free_voidp); successors = xbt_dynar_new(sizeof(mc_pair_stateless_t), NULL); /* Save the initial state */ - initial_state_liveness->initial_snapshot = MC_take_snapshot_liveness(); + initial_state_liveness->snapshot = MC_take_snapshot_liveness(); MC_UNSET_RAW_MEM; @@ -292,7 +543,7 @@ void MC_ddfs_init(void){ MC_UNSET_RAW_MEM; if(cursor != 0){ - MC_restore_snapshot(initial_state_liveness->initial_snapshot); + MC_restore_snapshot(initial_state_liveness->snapshot); MC_UNSET_RAW_MEM; } @@ -309,7 +560,7 @@ void MC_ddfs_init(void){ set_pair_reached(state); if(cursor != 0){ - MC_restore_snapshot(initial_state_liveness->initial_snapshot); + MC_restore_snapshot(initial_state_liveness->snapshot); MC_UNSET_RAW_MEM; } @@ -319,7 +570,7 @@ void MC_ddfs_init(void){ } } - if(raw_mem_set) + if(initial_state_liveness->raw_mem_set) MC_SET_RAW_MEM; else MC_UNSET_RAW_MEM; @@ -330,7 +581,7 @@ void MC_ddfs_init(void){ void MC_ddfs(int search_cycle){ - raw_mem_set = (mmalloc_get_current_heap() == raw_heap); + //initial_state_liveness->raw_mem_set = (mmalloc_get_current_heap() == raw_heap); smx_process_t process; mc_pair_stateless_t current_pair = NULL; @@ -367,7 +618,7 @@ void MC_ddfs(int search_cycle){ mc_pair_stateless_t remove_pair; mc_pair_reached_t remove_pair_reached; - if(xbt_fifo_size(mc_stack_liveness) < MAX_DEPTH_LIVENESS){ + if(xbt_fifo_size(mc_stack_liveness) < _surf_mc_max_depth){ if(current_pair->requests > 0){ @@ -463,56 +714,80 @@ void MC_ddfs(int search_cycle){ }else{ - XBT_DEBUG("Next pair (depth =%d) -> Acceptance pair (%s)", xbt_fifo_size(mc_stack_liveness) + 1, pair_succ->automaton_state->id); + if(visited(pair_succ->automaton_state)){ - XBT_DEBUG("Reached pairs : %lu", xbt_dynar_length(reached_pairs)); + XBT_DEBUG("Next pair already visited !"); + break; + + }else{ - MC_SET_RAW_MEM; - xbt_fifo_unshift(mc_stack_liveness, pair_succ); - MC_UNSET_RAW_MEM; + XBT_DEBUG("Next pair (depth =%d) -> Acceptance pair (%s)", xbt_fifo_size(mc_stack_liveness) + 1, pair_succ->automaton_state->id); + + XBT_DEBUG("Reached pairs : %lu", xbt_dynar_length(reached_pairs)); + + MC_SET_RAW_MEM; + xbt_fifo_unshift(mc_stack_liveness, pair_succ); + MC_UNSET_RAW_MEM; - MC_ddfs(search_cycle); + MC_ddfs(search_cycle); + + } } }else{ - MC_SET_RAW_MEM; - xbt_fifo_unshift(mc_stack_liveness, pair_succ); - MC_UNSET_RAW_MEM; - - MC_ddfs(search_cycle); + if(visited(pair_succ->automaton_state)){ + + XBT_DEBUG("Next pair already visited !"); + break; + + }else{ + + MC_SET_RAW_MEM; + xbt_fifo_unshift(mc_stack_liveness, pair_succ); + MC_UNSET_RAW_MEM; + + MC_ddfs(search_cycle); + } } }else{ + + if(visited(pair_succ->automaton_state)){ + + XBT_DEBUG("Next pair already visited !"); + break; + + }else{ - if(((pair_succ->automaton_state->type == 1) || (pair_succ->automaton_state->type == 2))){ + if(((pair_succ->automaton_state->type == 1) || (pair_succ->automaton_state->type == 2))){ - XBT_DEBUG("Next pair (depth =%d) -> Acceptance pair (%s)", xbt_fifo_size(mc_stack_liveness) + 1, pair_succ->automaton_state->id); + XBT_DEBUG("Next pair (depth =%d) -> Acceptance pair (%s)", xbt_fifo_size(mc_stack_liveness) + 1, pair_succ->automaton_state->id); - set_pair_reached(pair_succ->automaton_state); + set_pair_reached(pair_succ->automaton_state); - search_cycle = 1; + search_cycle = 1; - XBT_DEBUG("Reached pairs : %lu", xbt_dynar_length(reached_pairs)); + XBT_DEBUG("Reached pairs : %lu", xbt_dynar_length(reached_pairs)); - } + } - MC_SET_RAW_MEM; - xbt_fifo_unshift(mc_stack_liveness, pair_succ); - MC_UNSET_RAW_MEM; + MC_SET_RAW_MEM; + xbt_fifo_unshift(mc_stack_liveness, pair_succ); + MC_UNSET_RAW_MEM; - MC_ddfs(search_cycle); + MC_ddfs(search_cycle); + + } } - /* Restore system before checking others successors */ if(cursor != (xbt_dynar_length(successors) - 1)) MC_replay_liveness(mc_stack_liveness, 1); - - + } if(MC_state_interleave_size(current_pair->graph_state) > 0){ @@ -645,7 +920,7 @@ void MC_ddfs(int search_cycle){ } - if(xbt_fifo_size(mc_stack_liveness) == MAX_DEPTH_LIVENESS ){ + if(xbt_fifo_size(mc_stack_liveness) == _surf_mc_max_depth ){ XBT_DEBUG("Pair (depth = %d) shifted in stack, maximum depth reached", xbt_fifo_size(mc_stack_liveness) ); }else{ XBT_DEBUG("Pair (depth = %d) shifted in stack", xbt_fifo_size(mc_stack_liveness) ); @@ -663,7 +938,7 @@ void MC_ddfs(int search_cycle){ } MC_UNSET_RAW_MEM; - if(raw_mem_set) - MC_SET_RAW_MEM; + /*if(initial_state_liveness->raw_mem_set) + MC_SET_RAW_MEM;*/ }