Print this page
11506 smatch resync
*** 63,76 ****
#include "smatch.h"
#include "smatch_slist.h"
#include "smatch_extra.h"
char *implied_debug_msg;
- #define DIMPLIED(msg...) do { if (option_debug_implied || option_debug) printf(msg); } while (0)
! int option_debug_implied = 0;
/*
* tmp_range_list():
* It messes things up to free range list allocations. This helper fuction
* lets us reuse memory instead of doing new allocations.
*/
--- 63,78 ----
#include "smatch.h"
#include "smatch_slist.h"
#include "smatch_extra.h"
char *implied_debug_msg;
! bool implications_off;
+ #define implied_debug 0
+ #define DIMPLIED(msg...) do { if (implied_debug) printf(msg); } while (0)
+
/*
* tmp_range_list():
* It messes things up to free range list allocations. This helper fuction
* lets us reuse memory instead of doing new allocations.
*/
*** 85,95 ****
return my_list;
}
static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
{
! if (!option_debug_implied && !option_debug)
return;
if (istrue && isfalse) {
printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
} else if (istrue) {
--- 87,97 ----
return my_list;
}
static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
{
! if (!implied_debug && !option_debug)
return;
if (istrue && isfalse) {
printf("%s: %d: does not exist.\n", show_sm(sm), sm->line);
} else if (istrue) {
*** 141,162 ****
sm_msg("true_rl = %s false_rl = %s intersection = %s",
show_rl(true_rl), show_rl(false_rl), show_rl(rl_intersection(true_rl, false_rl)));
return 0;
}
! if (option_debug)
! sm_info("fake_history: %s vs %s. %s %s %s. --> T: %s F: %s",
sm->name, show_rl(rl), sm->state->name, show_special(comparison), show_rl(rl),
show_rl(true_rl), show_rl(false_rl));
true_sm = clone_sm(sm);
false_sm = clone_sm(sm);
! true_sm->state = alloc_estate_rl(cast_rl(estate_type(sm->state), true_rl));
free_slist(&true_sm->possible);
add_possible_sm(true_sm, true_sm);
! false_sm->state = alloc_estate_rl(cast_rl(estate_type(sm->state), false_rl));
free_slist(&false_sm->possible);
add_possible_sm(false_sm, false_sm);
true_stree = clone_stree(sm->pool);
false_stree = clone_stree(sm->pool);
--- 143,164 ----
sm_msg("true_rl = %s false_rl = %s intersection = %s",
show_rl(true_rl), show_rl(false_rl), show_rl(rl_intersection(true_rl, false_rl)));
return 0;
}
! if (implied_debug)
! sm_msg("fake_history: %s vs %s. %s %s %s. --> T: %s F: %s",
sm->name, show_rl(rl), sm->state->name, show_special(comparison), show_rl(rl),
show_rl(true_rl), show_rl(false_rl));
true_sm = clone_sm(sm);
false_sm = clone_sm(sm);
! true_sm->state = clone_partial_estate(sm->state, true_rl);
free_slist(&true_sm->possible);
add_possible_sm(true_sm, true_sm);
! false_sm->state = clone_partial_estate(sm->state, false_rl);
free_slist(&false_sm->possible);
add_possible_sm(false_sm, false_sm);
true_stree = clone_stree(sm->pool);
false_stree = clone_stree(sm->pool);
*** 264,274 ****
add_pool(true_stack, sm);
else if (isfalse)
add_pool(false_stack, sm);
else
add_pool(maybe_stack, sm);
-
}
static int is_checked(struct state_list *checked, struct sm_state *sm)
{
struct sm_state *tmp;
--- 266,275 ----
*** 290,328 ****
*/
static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
struct state_list **true_stack,
struct state_list **maybe_stack,
struct state_list **false_stack,
! struct state_list **checked, int *mixed, struct sm_state *gate_sm)
{
int free_checked = 0;
struct state_list *checked_states = NULL;
if (!sm)
return;
! /*
! * If it looks like this is going to take too long as-is, then don't
! * create even more fake history.
! */
! if (mixed && sm->nr_children > 100)
*mixed = 1;
-
- /*
- Sometimes the implications are just too big to deal with
- so we bail. Theoretically, bailing out here can cause more false
- positives but won't hide actual bugs.
- */
- if (sm->nr_children > 4000) {
- if (option_debug || option_debug_implied) {
- static char buf[1028];
- snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
- __func__, sm->nr_children, sm->name, show_state(sm->state));
- implied_debug_msg = buf;
}
- return;
- }
if (checked == NULL) {
checked = &checked_states;
free_checked = 1;
}
--- 291,319 ----
*/
static void __separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
struct state_list **true_stack,
struct state_list **maybe_stack,
struct state_list **false_stack,
! struct state_list **checked, int *mixed, struct sm_state *gate_sm,
! struct timeval *start_time)
{
int free_checked = 0;
struct state_list *checked_states = NULL;
+ struct timeval now;
if (!sm)
return;
! gettimeofday(&now, NULL);
! if (now.tv_usec - start_time->tv_usec > 1000000) {
! if (implied_debug) {
! sm_msg("debug: %s: implications taking too long. (%s %s %s)",
! __func__, sm->state->name, show_special(comparison), show_rl(rl));
! }
! if (mixed)
*mixed = 1;
}
if (checked == NULL) {
checked = &checked_states;
free_checked = 1;
}
*** 330,341 ****
return;
add_ptr_list(checked, sm);
do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
! __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm);
! __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm);
if (free_checked)
free_slist(checked);
}
static void separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
--- 321,332 ----
return;
add_ptr_list(checked, sm);
do_compare(sm, comparison, rl, true_stack, maybe_stack, false_stack, mixed, gate_sm);
! __separate_pools(sm->left, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
! __separate_pools(sm->right, comparison, rl, true_stack, maybe_stack, false_stack, checked, mixed, gate_sm, start_time);
if (free_checked)
free_slist(checked);
}
static void separate_pools(struct sm_state *sm, int comparison, struct range_list *rl,
*** 343,364 ****
struct state_list **false_stack,
struct state_list **checked, int *mixed)
{
struct state_list *maybe_stack = NULL;
struct sm_state *tmp;
- __separate_pools(sm, comparison, rl, true_stack, &maybe_stack, false_stack, checked, mixed, sm);
! if (option_debug) {
struct sm_state *sm;
FOR_EACH_PTR(*true_stack, sm) {
sm_msg("TRUE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
} END_FOR_EACH_PTR(sm);
FOR_EACH_PTR(maybe_stack, sm) {
! sm_msg("MAYBE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
} END_FOR_EACH_PTR(sm);
FOR_EACH_PTR(*false_stack, sm) {
sm_msg("FALSE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
} END_FOR_EACH_PTR(sm);
--- 334,359 ----
struct state_list **false_stack,
struct state_list **checked, int *mixed)
{
struct state_list *maybe_stack = NULL;
struct sm_state *tmp;
+ struct timeval start_time;
! gettimeofday(&start_time, NULL);
! __separate_pools(sm, comparison, rl, true_stack, &maybe_stack, false_stack, checked, mixed, sm, &start_time);
!
! if (implied_debug) {
struct sm_state *sm;
FOR_EACH_PTR(*true_stack, sm) {
sm_msg("TRUE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
} END_FOR_EACH_PTR(sm);
FOR_EACH_PTR(maybe_stack, sm) {
! sm_msg("MAYBE %s %s[stree %d]",
! show_sm(sm), sm->merged ? "(merged) ": "", get_stree_id(sm->pool));
} END_FOR_EACH_PTR(sm);
FOR_EACH_PTR(*false_stack, sm) {
sm_msg("FALSE %s [stree %d]", show_sm(sm), get_stree_id(sm->pool));
} END_FOR_EACH_PTR(sm);
*** 390,483 ****
return 1;
} END_FOR_EACH_PTR(tmp);
return 0;
}
! static int taking_too_long(void)
{
static void *printed;
! if (out_of_memory())
return 1;
! if (time_parsing_function() < option_timeout)
return 0;
if (!__inline_fn && printed != cur_func_sym) {
if (!is_skipped_function())
! sm_perror("turning off implications after 60 seconds");
printed = cur_func_sym;
}
return 1;
}
/*
* NOTE: If a state is in both the keep stack and the remove stack then that is
* a bug. Only add states which are definitely true or definitely false. If
* you have a leaf state that could be both true and false, then create a fake
* split history where one side is true and one side is false. Otherwise, if
* you can't do that, then don't add it to either list.
*/
struct sm_state *filter_pools(struct sm_state *sm,
const struct state_list *remove_stack,
const struct state_list *keep_stack,
int *modified, int *recurse_cnt,
! struct timeval *start)
{
struct sm_state *ret = NULL;
struct sm_state *left;
struct sm_state *right;
int removed = 0;
struct timeval now;
if (!sm)
return NULL;
! if (sm->skip_implications)
! return sm;
! if (taking_too_long())
! return sm;
!
gettimeofday(&now, NULL);
! if ((*recurse_cnt)++ > 1000 || now.tv_sec - start->tv_sec > 5) {
! if (local_debug || option_debug_implied) {
! static char buf[1028];
! snprintf(buf, sizeof(buf), "debug: %s: nr_children over 4000 (%d). (%s %s)",
! __func__, sm->nr_children, sm->name, show_state(sm->state));
! implied_debug_msg = buf;
}
! sm->skip_implications = 1;
! return sm;
}
if (pool_in_pools(sm->pool, remove_stack)) {
! DIMPLIED("removed [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
*modified = 1;
return NULL;
}
if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
! DIMPLIED("kept [stree %d] %s from %d. %s. %s. %s.\n", get_stree_id(sm->pool), show_sm(sm), sm->line,
is_merged(sm) ? "merged" : "not merged",
pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
! sm_in_keep_leafs(sm, keep_stack) ? "reachable keep leaf" : "no keep leaf");
return sm;
}
! DIMPLIED("checking [stree %d] %s from %d (%d) left = %s [stree %d] right = %s [stree %d]\n",
! get_stree_id(sm->pool),
! show_sm(sm), sm->line, sm->nr_children,
! sm->left ? sm->left->state->name : "<none>", sm->left ? get_stree_id(sm->left->pool) : -1,
! sm->right ? sm->right->state->name : "<none>", sm->right ? get_stree_id(sm->right->pool) : -1);
! left = filter_pools(sm->left, remove_stack, keep_stack, &removed, recurse_cnt, start);
! right = filter_pools(sm->right, remove_stack, keep_stack, &removed, recurse_cnt, start);
if (!removed) {
! DIMPLIED("kept [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
return sm;
}
*modified = 1;
if (!left && !right) {
! DIMPLIED("removed [stree %d] %s from %d <none>\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
return NULL;
}
if (!left) {
ret = clone_sm(right);
--- 385,502 ----
return 1;
} END_FOR_EACH_PTR(tmp);
return 0;
}
! static int going_too_slow(void)
{
static void *printed;
! if (out_of_memory()) {
! implications_off = true;
return 1;
+ }
! if (!option_timeout || time_parsing_function() < option_timeout) {
! implications_off = false;
return 0;
+ }
if (!__inline_fn && printed != cur_func_sym) {
if (!is_skipped_function())
! sm_perror("turning off implications after %d seconds", option_timeout);
printed = cur_func_sym;
}
+ implications_off = true;
return 1;
}
+ static char *sm_state_info(struct sm_state *sm)
+ {
+ static char buf[512];
+ int n = 0;
+
+ n += snprintf(buf + n, sizeof(buf) - n, "[stree %d line %d] ",
+ get_stree_id(sm->pool), sm->line);
+ if (n >= sizeof(buf))
+ return buf;
+ n += snprintf(buf + n, sizeof(buf) - n, "%s ", show_sm(sm));
+ if (n >= sizeof(buf))
+ return buf;
+ n += snprintf(buf + n, sizeof(buf) - n, "left = %s [stree %d] ",
+ sm->left ? sm->left->state->name : "<none>",
+ sm->left ? get_stree_id(sm->left->pool) : -1);
+ if (n >= sizeof(buf))
+ return buf;
+ n += snprintf(buf + n, sizeof(buf) - n, "right = %s [stree %d]",
+ sm->right ? sm->right->state->name : "<none>",
+ sm->right ? get_stree_id(sm->right->pool) : -1);
+ return buf;
+ }
+
/*
* NOTE: If a state is in both the keep stack and the remove stack then that is
* a bug. Only add states which are definitely true or definitely false. If
* you have a leaf state that could be both true and false, then create a fake
* split history where one side is true and one side is false. Otherwise, if
* you can't do that, then don't add it to either list.
*/
+ #define RECURSE_LIMIT 300
struct sm_state *filter_pools(struct sm_state *sm,
const struct state_list *remove_stack,
const struct state_list *keep_stack,
int *modified, int *recurse_cnt,
! struct timeval *start, int *skip, int *bail)
{
struct sm_state *ret = NULL;
struct sm_state *left;
struct sm_state *right;
int removed = 0;
struct timeval now;
if (!sm)
return NULL;
! if (*bail)
! return NULL;
gettimeofday(&now, NULL);
! if (now.tv_usec - start->tv_usec > 3000000) {
! DIMPLIED("%s: implications taking too long: %s\n", __func__, sm_state_info(sm));
! *bail = 1;
! return NULL;
}
! if ((*recurse_cnt)++ > RECURSE_LIMIT) {
! DIMPLIED("%s: recursed too far: %s\n", __func__, sm_state_info(sm));
! *skip = 1;
! return NULL;
}
if (pool_in_pools(sm->pool, remove_stack)) {
! DIMPLIED("%s: remove: %s\n", __func__, sm_state_info(sm));
*modified = 1;
return NULL;
}
if (!is_merged(sm) || pool_in_pools(sm->pool, keep_stack) || sm_in_keep_leafs(sm, keep_stack)) {
! DIMPLIED("%s: keep %s (%s, %s, %s): %s\n", __func__, sm->state->name,
is_merged(sm) ? "merged" : "not merged",
pool_in_pools(sm->pool, keep_stack) ? "not in keep pools" : "in keep pools",
! sm_in_keep_leafs(sm, keep_stack) ? "reachable keep leaf" : "no keep leaf",
! sm_state_info(sm));
return sm;
}
! left = filter_pools(sm->left, remove_stack, keep_stack, &removed, recurse_cnt, start, skip, bail);
! right = filter_pools(sm->right, remove_stack, keep_stack, &removed, recurse_cnt, start, skip, bail);
! if (*bail || *skip)
! return NULL;
if (!removed) {
! DIMPLIED("%s: kept all: %s\n", __func__, sm_state_info(sm));
return sm;
}
*modified = 1;
if (!left && !right) {
! DIMPLIED("%s: removed all: %s\n", __func__, sm_state_info(sm));
return NULL;
}
if (!left) {
ret = clone_sm(right);
*** 503,514 ****
ret = merge_sm_states(left, right);
}
ret->pool = sm->pool;
! DIMPLIED("partial %s => ", show_sm(sm));
! DIMPLIED("%s from %d [stree %d]\n", show_sm(ret), sm->line, get_stree_id(sm->pool));
return ret;
}
static struct stree *filter_stack(struct sm_state *gate_sm,
struct stree *pre_stree,
--- 522,532 ----
ret = merge_sm_states(left, right);
}
ret->pool = sm->pool;
! DIMPLIED("%s: partial: %s\n", __func__, sm_state_info(sm));
return ret;
}
static struct stree *filter_stack(struct sm_state *gate_sm,
struct stree *pre_stree,
*** 519,555 ****
struct sm_state *tmp;
struct sm_state *filtered_sm;
int modified;
int recurse_cnt;
struct timeval start;
if (!remove_stack)
return NULL;
! if (taking_too_long())
! return NULL;
!
FOR_EACH_SM(pre_stree, tmp) {
! if (option_debug)
! sm_msg("%s: %s", __func__, show_sm(tmp));
! if (!tmp->merged)
continue;
- if (sm_in_keep_leafs(tmp, keep_stack))
- continue;
modified = 0;
recurse_cnt = 0;
! gettimeofday(&start, NULL);
! filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified, &recurse_cnt, &start);
! if (!filtered_sm || !modified)
continue;
/* the assignments here are for borrowed implications */
filtered_sm->name = tmp->name;
filtered_sm->sym = tmp->sym;
avl_insert(&ret, filtered_sm);
- if (out_of_memory() || taking_too_long())
- return NULL;
-
} END_FOR_EACH_SM(tmp);
return ret;
}
static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
--- 537,572 ----
struct sm_state *tmp;
struct sm_state *filtered_sm;
int modified;
int recurse_cnt;
struct timeval start;
+ int skip;
+ int bail = 0;
if (!remove_stack)
return NULL;
! gettimeofday(&start, NULL);
FOR_EACH_SM(pre_stree, tmp) {
! if (!tmp->merged || sm_in_keep_leafs(tmp, keep_stack))
continue;
modified = 0;
recurse_cnt = 0;
! skip = 0;
! filtered_sm = filter_pools(tmp, remove_stack, keep_stack, &modified, &recurse_cnt, &start, &skip, &bail);
! if (going_too_slow())
! return NULL;
! if (bail)
! return ret; /* Return the implications we figured out before time ran out. */
!
!
! if (skip || !filtered_sm || !modified)
continue;
/* the assignments here are for borrowed implications */
filtered_sm->name = tmp->name;
filtered_sm->sym = tmp->sym;
avl_insert(&ret, filtered_sm);
} END_FOR_EACH_SM(tmp);
return ret;
}
static void separate_and_filter(struct sm_state *sm, int comparison, struct range_list *rl,
*** 564,604 ****
struct timeval time_after;
int sec;
gettimeofday(&time_before, NULL);
if (!is_merged(sm)) {
! DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm->name);
return;
}
- if (option_debug_implied || option_debug) {
- sm_msg("checking implications: (%s %s %s)",
- sm->name, show_special(comparison), show_rl(rl));
- }
-
separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
DIMPLIED("filtering true stack.\n");
*true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
DIMPLIED("filtering false stack.\n");
*false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
free_slist(&true_stack);
free_slist(&false_stack);
! if (option_debug_implied || option_debug) {
! printf("These are the implied states for the true path: (%s %s %s)\n",
! sm->name, show_special(comparison), show_rl(rl));
__print_stree(*true_states);
! printf("These are the implied states for the false path: (%s %s %s)\n",
! sm->name, show_special(comparison), show_rl(rl));
__print_stree(*false_states);
}
gettimeofday(&time_after, NULL);
sec = time_after.tv_sec - time_before.tv_sec;
! if (sec > option_timeout) {
! sm->nr_children = 4000;
sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
}
}
static struct expression *get_last_expr(struct statement *stmt)
--- 581,618 ----
struct timeval time_after;
int sec;
gettimeofday(&time_before, NULL);
+ DIMPLIED("checking implications: (%s (%s) %s %s)\n",
+ sm->name, sm->state->name, show_special(comparison), show_rl(rl));
+
if (!is_merged(sm)) {
! DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
return;
}
separate_pools(sm, comparison, rl, &true_stack, &false_stack, NULL, mixed);
DIMPLIED("filtering true stack.\n");
*true_states = filter_stack(sm, pre_stree, false_stack, true_stack);
DIMPLIED("filtering false stack.\n");
*false_states = filter_stack(sm, pre_stree, true_stack, false_stack);
free_slist(&true_stack);
free_slist(&false_stack);
! if (implied_debug) {
! printf("These are the implied states for the true path: (%s (%s) %s %s)\n",
! sm->name, sm->state->name, show_special(comparison), show_rl(rl));
__print_stree(*true_states);
! printf("These are the implied states for the false path: (%s (%s) %s %s)\n",
! sm->name, sm->state->name, show_special(comparison), show_rl(rl));
__print_stree(*false_states);
}
gettimeofday(&time_after, NULL);
sec = time_after.tv_sec - time_before.tv_sec;
! if (option_timeout && sec > option_timeout) {
sm_perror("Function too hairy. Ignoring implications after %d seconds.", sec);
}
}
static struct expression *get_last_expr(struct statement *stmt)
*** 812,822 ****
free_slist(&false_stack);
return 1;
}
- static int found_implications;
static struct stree *saved_implied_true;
static struct stree *saved_implied_false;
static struct stree *extra_saved_implied_true;
static struct stree *extra_saved_implied_false;
--- 826,835 ----
*** 846,873 ****
static void get_tf_states(struct expression *expr,
struct stree **implied_true,
struct stree **implied_false)
{
if (handled_by_comparison_hook(expr, implied_true, implied_false))
! goto found;
if (handled_by_extra_states(expr, implied_true, implied_false)) {
separate_extra_states(implied_true, implied_false);
! goto found;
}
if (handled_by_stored_conditions(expr, implied_true, implied_false))
- goto found;
-
return;
- found:
- found_implications = 1;
}
static void save_implications_hook(struct expression *expr)
{
! if (taking_too_long())
return;
get_tf_states(expr, &saved_implied_true, &saved_implied_false);
}
static void set_implied_states(struct expression *expr)
--- 859,882 ----
static void get_tf_states(struct expression *expr,
struct stree **implied_true,
struct stree **implied_false)
{
if (handled_by_comparison_hook(expr, implied_true, implied_false))
! return;
if (handled_by_extra_states(expr, implied_true, implied_false)) {
separate_extra_states(implied_true, implied_false);
! return;
}
if (handled_by_stored_conditions(expr, implied_true, implied_false))
return;
}
static void save_implications_hook(struct expression *expr)
{
! if (going_too_slow())
return;
get_tf_states(expr, &saved_implied_true, &saved_implied_false);
}
static void set_implied_states(struct expression *expr)
*** 904,913 ****
--- 913,925 ----
struct sm_state *tmp;
struct stree *implied_true = NULL;
struct stree *implied_false = NULL;
struct range_list *orig, *limit;
+ if (time_parsing_function() > 40)
+ return;
+
while (expr->type == EXPR_ASSIGNMENT)
expr = strip_expr(expr->right);
if (expr->type != EXPR_CALL)
return;
*** 1070,1080 ****
int orig_final_pass = final_pass;
in_fake_env++;
final_pass = 0;
__push_fake_cur_stree();
- found_implications = 0;
__split_whole_condition(expr);
final_pass = orig_final_pass;
in_fake_env--;
return 1;
--- 1082,1091 ----