From a55b4e5fd2e2e3acc9f9ea9a9d064f7001541bf6 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Sat, 6 Sep 2008 19:57:51 +0300 Subject: [PATCH] This is the start of the smatch_extra stuff. The eventual goal is to try track the possible values of all the variables. Currently the only use is to tell when we know a pre-loop condition is true the first time. Sometimes it is easy. for (i = 0 ; i < 100 ; i++) { ... We know that i < 100 the first time through the loop. Signed-off-by: Dan Carpenter --- check_overflow.c | 41 +------------ smatch.h | 6 +- smatch_extra.c | 176 +++++++++++++++++++++++++++++++++++++++++++++++++------ smatch_flow.c | 11 +++- smatch_helper.c | 8 +-- smatch_hooks.c | 3 + 6 files changed, 182 insertions(+), 63 deletions(-) rewrite smatch_extra.c (70%) diff --git a/check_overflow.c b/check_overflow.c index d3a2a085..242c9e91 100644 --- a/check_overflow.c +++ b/check_overflow.c @@ -13,43 +13,6 @@ static int my_id; -static int get_value(struct expression *expr, int *discard) -{ - int dis = 0; - int ret = 0; - - if (!expr) - return 0; - if (!discard) - discard = &dis; - if (*discard) - return 0; - - switch (expr->type){ - case EXPR_VALUE: - ret = expr->value; - break; - case EXPR_BINOP: - if (show_special(expr->op) && - !strcmp("*", show_special(expr->op))) - ret = get_value(expr->left, discard) - * get_value(expr->right, discard); - break; - case EXPR_SIZEOF: - if (expr->cast_type && get_base_type(expr->cast_type)) - ret = (get_base_type(expr->cast_type))->bit_size / 8; - if (expr->cast_expression) - ;//printf("debugs %d\n", expr->cast_expression->type); - break; - default: - //printf("ouchies-->%d\n", expr->type); - *discard = 1; - } - if (*discard) - return 0; - return ret; -} - static int malloc_size(struct expression *expr) { char *name; @@ -86,7 +49,7 @@ static void match_declaration(struct symbol *sym) set_state(name, my_id, NULL, base_type->bit_size / 8); else { size = malloc_size(sym->initializer); - if (size) + if (size > 0) set_state(name, my_id, NULL, size); } } @@ -98,7 +61,7 @@ static void match_assignment(struct expression *expr) name = alloc_string(name); if (!name) return; - if (malloc_size(expr->right)) + if (malloc_size(expr->right) > 0) set_state(name, my_id, NULL, malloc_size(expr->right)); } diff --git a/smatch.h b/smatch.h index 892b6f8a..225be97e 100644 --- a/smatch.h +++ b/smatch.h @@ -45,6 +45,7 @@ enum hook_type { WHOLE_CONDITION_HOOK, FUNCTION_CALL_HOOK, FUNCTION_CALL_AFTER_HOOK, + OP_HOOK, DEREF_HOOK, BASE_HOOK, FUNC_DEF_HOOK, @@ -66,8 +67,8 @@ do { \ #define SM_DEBUG(msg...) do { if (debug_states) printf(msg); } while (0) -#define NOTFOUND -2 -#define UNDEFINED -1 +#define NOTFOUND INT_MIN +#define UNDEFINED INT_MIN + 1 int get_state(const char *name, int owner, struct symbol *sym); void add_state(const char *name, int owner, struct symbol *sym, int state); @@ -121,6 +122,7 @@ extern int debug_states; void __prep_false_only_stack(); void __use_false_only_stack(); +void __pop_false_only_stack(); void __use_true_states(); void __use_false_states(); void __pop_false_states(); diff --git a/smatch_extra.c b/smatch_extra.c dissimilarity index 70% index eb156359..4def7972 100644 --- a/smatch_extra.c +++ b/smatch_extra.c @@ -1,17 +1,159 @@ -/* - -1) Name every path - Child paths? -2) Save the path number in the state history -3) Possible value ranges -4) Binary, int, equal to another variable -5) When can we use this data? - -*/ - -static int my_id; - -void register_smatch_extra(int id) -{ - my_id = id; -} +/* + * sparse/smatch_extra.c + * + * Copyright (C) 2008 Dan Carpenter. + * + * Licensed under the Open Software License version 1.1 + * + */ + +#include +#include "parse.h" +#include "smatch.h" + +static int my_id; + +static int merge_func(const char *name, struct symbol *sym, int s1, int s2) +{ + return UNDEFINED; +} + +static void match_function_call_after(struct expression *expr) +{ + struct expression *tmp; + struct symbol *sym; + char *name; + int i = 0; + + FOR_EACH_PTR(expr->args, tmp) { + if (tmp->op == '&') { + name = get_variable_from_expr_simple(tmp->unop, &sym); + if (name) { + name = alloc_string(name); + set_state(name, my_id, sym, UNDEFINED); + } + } + i++; + } END_FOR_EACH_PTR(tmp); +} + +static void match_assign(struct expression *expr) +{ + struct symbol *sym; + char *name; + + name = get_variable_from_expr_simple(expr->left, &sym); + if (!name) + return; + name = alloc_string(name); + set_state(name, my_id, sym, get_value(expr->right, NULL)); +} + +static void undef_expr(struct expression *expr) +{ + struct symbol *sym; + char *name; + + name = get_variable_from_expr_simple(expr->unop, &sym); + if (!name) + return; + if (get_state(name, my_id, sym) == NOTFOUND) + return; + name = alloc_string(name); + set_state(name, my_id, sym, UNDEFINED); +} + +static void match_declarations(struct symbol *sym) +{ + const char *name; + + if (sym->ident) { + name = sym->ident->name; + if (sym->initializer) { + set_state(name, my_id, sym, get_value(sym->initializer, NULL)); + } + } +} + +void register_smatch_extra(int id) +{ + my_id = id; + add_merge_hook(my_id, &merge_func); + add_hook(&undef_expr, OP_HOOK); + add_hook(&match_function_call_after, FUNCTION_CALL_AFTER_HOOK); + add_hook(&match_assign, ASSIGNMENT_AFTER_HOOK); + add_hook(&match_declarations, DECLARATION_HOOK); +} + +static int expr_to_val(struct expression *expr) +{ + int val; + struct symbol *sym; + char *name; + + val = get_value(expr, NULL); + if (val != UNDEFINED) + return val; + + name = get_variable_from_expr_simple(expr, &sym); + if (!name) + return UNDEFINED; + val = get_state(name, my_id, sym); + if (val == NOTFOUND) + val = UNDEFINED; + return val; +} + +static int true_comparison(int left, int comparison, int right) +{ + switch(comparison){ + case '<': + case SPECIAL_UNSIGNED_LT: + if (left < right) + return 1; + return 0; + case SPECIAL_UNSIGNED_LTE: + case SPECIAL_LTE: + if (left < right) + return 1; + case SPECIAL_EQUAL: + if (left == right) + return 1; + return 0; + case SPECIAL_UNSIGNED_GTE: + case SPECIAL_GTE: + if (left == right) + return 1; + case '>': + case SPECIAL_UNSIGNED_GT: + if (left > right) + return 1; + return 0; + case SPECIAL_NOTEQUAL: + if (left != right) + return 1; + return 0; + default: + smatch_msg("unhandled comparison %d\n", comparison); + } + return 0; +} + +int known_condition_true(struct expression *expr) +{ + int left, right, ret; + + if (!expr || expr->type != EXPR_COMPARE) + return 0; + + if ((left = expr_to_val(expr->left)) == UNDEFINED) + return 0; + + if ((right = expr_to_val(expr->right)) == UNDEFINED) + return 0; + + ret = true_comparison(left, expr->op, right); + smatch_msg("known condition: %d & %d => %s", left, right, (ret?"true":"false")); + + return ret; +} diff --git a/smatch_flow.c b/smatch_flow.c index 74f7ce58..f59f3d0a 100644 --- a/smatch_flow.c +++ b/smatch_flow.c @@ -39,6 +39,7 @@ void __split_expr(struct expression *expr) switch (expr->type) { case EXPR_PREOP: case EXPR_POSTOP: + __pass_to_client(expr, OP_HOOK); if (expr->op == '*') __pass_to_client(expr, DEREF_HOOK); __split_expr(expr->unop); @@ -117,7 +118,7 @@ static int is_forever_loop(struct statement *stmt) if (!expr) expr = stmt->iterator_post_condition; if (!expr) { - // this is a for(;;) loop... + /* this is a for(;;) loop... */ return 1; } @@ -134,8 +135,12 @@ static int is_forever_loop(struct statement *stmt) static void handle_pre_loop(struct statement *stmt) { + int once_through; /* we go through the loop at least once */ + split_statements(stmt->iterator_pre_statement); + once_through = known_condition_true(stmt->iterator_pre_condition); + __push_continues(); __push_breaks(); __prep_false_only_stack(); @@ -150,6 +155,10 @@ static void handle_pre_loop(struct statement *stmt) __pop_continues(); __pop_false_states(); nullify_path(); + } else if (once_through) { + __merge_continues(); + __pop_false_states(); + __use_false_only_stack(); } else { __merge_continues(); __merge_false_states(); diff --git a/smatch_helper.c b/smatch_helper.c index e803e7f8..94b48a42 100644 --- a/smatch_helper.c +++ b/smatch_helper.c @@ -268,14 +268,14 @@ int sym_name_is(const char *name, struct expression *expr) int get_value(struct expression *expr, int *discard) { int dis = 0; - int ret = 0; + int ret = UNDEFINED; if (!expr) - return 0; + return UNDEFINED; if (!discard) discard = &dis; if (*discard) - return 0; + return UNDEFINED; switch (expr->type){ case EXPR_VALUE: @@ -298,7 +298,7 @@ int get_value(struct expression *expr, int *discard) *discard = 1; } if (*discard) - return 0; + return UNDEFINED; return ret; } diff --git a/smatch_hooks.c b/smatch_hooks.c index 4c7ebe49..faa66c71 100644 --- a/smatch_hooks.c +++ b/smatch_hooks.c @@ -40,6 +40,9 @@ void add_hook(void *func, enum hook_type type) case ASSIGNMENT_HOOK: container->data_type = EXPR_HOOK; break; + case OP_HOOK: + container->data_type = EXPR_HOOK; + break; case ASSIGNMENT_AFTER_HOOK: container->data_type = EXPR_HOOK; break; -- 2.11.4.GIT