Print this page
11506 smatch resync
@@ -63,14 +63,16 @@
#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;
+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,11 +87,11 @@
return my_list;
}
static void print_debug_tf(struct sm_state *sm, int istrue, int isfalse)
{
- if (!option_debug_implied && !option_debug)
+ 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,22 +143,22 @@
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",
+ 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 = alloc_estate_rl(cast_rl(estate_type(sm->state), true_rl));
+ 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 = alloc_estate_rl(cast_rl(estate_type(sm->state), false_rl));
+ 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,11 +266,10 @@
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;
@@ -290,39 +291,29 @@
*/
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 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;
- /*
- * 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)
+ 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;
-
- /*
- 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;
}
@@ -330,12 +321,12 @@
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);
+ __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,22 +334,26 @@
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;
- __separate_pools(sm, comparison, rl, true_stack, &maybe_stack, false_stack, checked, mixed, sm);
- if (option_debug) {
+ 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 [stree %d]", show_sm(sm), get_stree_id(sm->pool));
+ 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,94 +385,118 @@
return 1;
} END_FOR_EACH_PTR(tmp);
return 0;
}
-static int taking_too_long(void)
+static int going_too_slow(void)
{
static void *printed;
- if (out_of_memory())
+ if (out_of_memory()) {
+ implications_off = true;
return 1;
+ }
- if (time_parsing_function() < option_timeout)
+ 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 60 seconds");
+ 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)
+ 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 (sm->skip_implications)
- return sm;
- if (taking_too_long())
- return sm;
-
+ if (*bail)
+ return NULL;
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;
+ 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;
}
- sm->skip_implications = 1;
- return sm;
+ 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("removed [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
+ 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("kept [stree %d] %s from %d. %s. %s. %s.\n", get_stree_id(sm->pool), show_sm(sm), sm->line,
+ 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_in_keep_leafs(sm, keep_stack) ? "reachable keep leaf" : "no keep leaf",
+ sm_state_info(sm));
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);
+ 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("kept [stree %d] %s from %d\n", get_stree_id(sm->pool), show_sm(sm), sm->line);
+ DIMPLIED("%s: kept all: %s\n", __func__, sm_state_info(sm));
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);
+ DIMPLIED("%s: removed all: %s\n", __func__, sm_state_info(sm));
return NULL;
}
if (!left) {
ret = clone_sm(right);
@@ -503,12 +522,11 @@
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));
+ 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,37 +537,36 @@
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;
- if (taking_too_long())
- return NULL;
-
+ gettimeofday(&start, NULL);
FOR_EACH_SM(pre_stree, tmp) {
- if (option_debug)
- sm_msg("%s: %s", __func__, show_sm(tmp));
- if (!tmp->merged)
+ if (!tmp->merged || sm_in_keep_leafs(tmp, keep_stack))
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)
+ 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);
- 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,
@@ -564,41 +581,38 @@
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' is not merged.\n", get_lineno(), sm->name);
+ DIMPLIED("%d '%s' from line %d is not merged.\n", get_lineno(), sm->name, sm->line);
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));
+ 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)\n",
- sm->name, show_special(comparison), show_rl(rl));
+ 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 (sec > option_timeout) {
- sm->nr_children = 4000;
+ 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,11 +826,10 @@
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;
@@ -846,28 +859,24 @@
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;
+ return;
if (handled_by_extra_states(expr, implied_true, implied_false)) {
separate_extra_states(implied_true, implied_false);
- goto found;
+ return;
}
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())
+ if (going_too_slow())
return;
get_tf_states(expr, &saved_implied_true, &saved_implied_false);
}
static void set_implied_states(struct expression *expr)
@@ -904,10 +913,13 @@
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,11 +1082,10 @@
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;