From a8ea1f4ce8d40f80c59607f72aaa9c45539621b7 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Wed, 15 Apr 2009 11:52:23 +0300 Subject: [PATCH] Add: return_implies_state() There are some functions like down_trylock() where the return value implies whether the lock is state unlocked or state locked. This is like conditional functions except those can only handle 0 and non-zero ranges while this one can handle more complex ranges. Signed-off-by: Dan Carpenter --- check_locking.c | 57 ++++++++++++++++++++++++++++-------------- smatch.h | 13 ++++++++++ smatch_extra.c | 8 ++++++ smatch_extra.h | 15 +++++------ smatch_function_hooks.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++-- smatch_ranges.c | 41 +++++++++++++++++++++++++++++- smatch_states.c | 7 ++++++ 7 files changed, 178 insertions(+), 29 deletions(-) diff --git a/check_locking.c b/check_locking.c index 899821f4..683662f3 100644 --- a/check_locking.c +++ b/check_locking.c @@ -77,7 +77,7 @@ static const char *conditional_funcs[] = { NULL, }; -/* These functions return 0 on success */ +/* These functions return 0 on success and negative on failure */ static const char *reverse_cond_funcs[] = { "down_trylock", "down_interruptible", @@ -186,6 +186,38 @@ static void match_unlock_func(const char *fn, struct expression *expr, free_string(lock_name); } +static void match_lock_failed(const char *fn, struct expression *expr, void *data) +{ + char *lock_name; + struct sm_state *sm; + + lock_name = get_lock_name(expr, data); + if (!lock_name) + return; + sm = get_sm_state(lock_name, my_id, NULL); + if (!sm) + add_tracker(&starts_unlocked, lock_name, my_id, NULL); + set_state(lock_name, my_id, NULL, &unlocked); + free_string(lock_name); +} + +static void match_lock_aquired(const char *fn, struct expression *expr, void *data) +{ + char *lock_name; + struct sm_state *sm; + + lock_name = get_lock_name(expr, data); + if (!lock_name) + return; + sm = get_sm_state(lock_name, my_id, NULL); + if (!sm) + add_tracker(&starts_unlocked, lock_name, my_id, NULL); + if (sm && slist_has_state(sm->possible, &locked)) + smatch_msg("error: double lock '%s'", lock_name); + set_state(lock_name, my_id, NULL, &locked); + free_string(lock_name); +} + static void match_lock_needed(const char *fn, struct expression *expr, void *data) { @@ -205,22 +237,6 @@ static void match_lock_needed(const char *fn, struct expression *expr, free_string(fn_name); } -static void match_locks_on_zero(const char *fn, struct expression *expr, - void *data) -{ - char *lock_name; - struct sm_state *sm; - - lock_name = get_lock_name(expr, data); - if (!lock_name) - return; - sm = get_sm_state(lock_name, my_id, NULL); - if (!sm) - add_tracker(&starts_unlocked, lock_name, my_id, NULL); - set_true_false_states(lock_name, my_id, NULL, &unlocked, &locked); - free_string(lock_name); -} - static void match_locks_on_non_zero(const char *fn, struct expression *expr, void *data) { @@ -459,7 +475,10 @@ void check_locking(int id) } for (i = 0; reverse_cond_funcs[i]; i++) { - add_conditional_hook(reverse_cond_funcs[i], - &match_locks_on_zero, NULL); + return_implies_state(reverse_cond_funcs[i], whole_range.min, -1, + &match_lock_failed, NULL); + return_implies_state(reverse_cond_funcs[i], 0, 0, + &match_lock_aquired, NULL); + } } diff --git a/smatch.h b/smatch.h index 570c3e7a..65574376 100644 --- a/smatch.h +++ b/smatch.h @@ -85,6 +85,8 @@ void add_function_hook(const char *lock_for, func_hook *call_back, void *data); void add_conditional_hook(const char *look_for, func_hook *call_back, void *data); void add_function_assign_hook(const char *look_for, func_hook *call_back, void *info); +void return_implies_state(const char *look_for, long long start, long long end, + func_hook *call_back, void *info); #define smatch_msg(msg...) \ do { \ @@ -182,6 +184,13 @@ void get_implications(char *name, struct symbol *sym, int comparison, int num, /* smatch_extras.c */ #define SMATCH_EXTRA 1 /* this is my_id from smatch extra set in smatch.c */ + +struct data_range { + long long min; + long long max; +}; +extern struct data_range whole_range; + int get_implied_value(struct expression *expr); int true_comparison(int left, int comparison, int right); int known_condition_true(struct expression *expr); @@ -191,6 +200,9 @@ int implied_condition_false(struct expression *expr); /* smatch_states.c */ extern int debug_states; + +extern int __fake_cur; +extern struct state_list *__fake_cur_slist; extern int __fake_conditions; extern struct state_list *__fake_cond_true; extern struct state_list *__fake_cond_false; @@ -271,6 +283,7 @@ struct smatch_state *__client_unmatched_state_function(struct sm_state *sm); /* smatch_function_hooks.c */ struct fcall_back { int type; + struct data_range *range; func_hook *call_back; void *info; }; diff --git a/smatch_extra.c b/smatch_extra.c index a2c751bb..8ae83fbb 100644 --- a/smatch_extra.c +++ b/smatch_extra.c @@ -470,6 +470,14 @@ static void match_comparison(struct expression *expr) return; left = 1; } + if (left && expr->left->type == EXPR_CALL) { + function_comparison(comparison, expr->left, value, left); + return; + } + if (!left && expr->right->type == EXPR_CALL) { + function_comparison(comparison, expr->right, value, left); + return; + } if (left) name = get_variable_from_expr(expr->left, &sym); else diff --git a/smatch_extra.h b/smatch_extra.h index 0d90f467..25b21b4d 100644 --- a/smatch_extra.h +++ b/smatch_extra.h @@ -11,11 +11,6 @@ enum data_type { DATA_RANGE, }; -struct data_range { - long long min; - long long max; -}; - DECLARE_PTR_LIST(range_list, struct data_range); struct data_info { @@ -25,10 +20,10 @@ struct data_info { }; DECLARE_ALLOCATOR(data_info); -extern struct data_range whole_range; - /* these are implimented in smatch_extra_helper.c */ +struct data_range *alloc_range_perm(long long min, long long max); void add_range(struct range_list **list, long long min, long long max); +int true_comparison_range(struct data_range *left, int comparison, struct data_range *right); int possibly_true(int comparison, struct data_info *dinfo, int num, int left); int possibly_false(int comparison, struct data_info *dinfo, int num, int left); void free_data_info_allocs(void); @@ -58,3 +53,9 @@ long long get_dinfo_min(struct data_info *dinfo); long long get_dinfo_max(struct data_info *dinfo); int is_whole_range(struct range_list *ranges); long long get_single_value_from_range(struct data_info *dinfo); + +void function_comparison(int comparison, struct expression *expr, long long value, int left); + +int true_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left); +int false_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left); +struct data_range *alloc_range(long long min, long long max); diff --git a/smatch_function_hooks.c b/smatch_function_hooks.c index cc675425..655a4563 100644 --- a/smatch_function_hooks.c +++ b/smatch_function_hooks.c @@ -10,9 +10,10 @@ ALLOCATOR(fcall_back, "call backs"); static struct hsearch_data func_hash; -#define REGULAR_CALL 0 +#define REGULAR_CALL 0 #define CONDITIONAL_CALL 1 -#define ASSIGN_CALL 2 +#define ASSIGN_CALL 2 +#define RANGED_CALL 3 static struct fcall_back *alloc_fcall_back(int type, func_hook *call_back, void *info) @@ -88,6 +89,16 @@ void add_function_assign_hook(const char *look_for, func_hook *call_back, add_cb_hook(look_for, cb); } +void return_implies_state(const char *look_for, long long start, long long end, + func_hook *call_back, void *info) +{ + struct fcall_back *cb; + + cb = alloc_fcall_back(RANGED_CALL, call_back, info); + cb->range = alloc_range_perm(start, end); + add_cb_hook(look_for, cb); +} + static void call_call_backs(struct call_back_list *list, int type, const char *fn, struct expression *expr) { @@ -156,6 +167,57 @@ free: } +void function_comparison(int comparison, struct expression *expr, long long value, int left) +{ + struct call_back_list *call_backs; + struct fcall_back *tmp; + const char *fn; + struct data_range *value_range; + struct state_list *true_states = NULL; + struct state_list *false_states = NULL; + struct sm_state *sm; + + if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol) + return; + fn = expr->fn->symbol->ident->name; + call_backs = get_call_backs(expr->fn->symbol->ident->name); + if (!call_backs) + return; + value_range = alloc_range(value, value); + + __fake_cur = 1; + FOR_EACH_PTR(call_backs, tmp) { + if (tmp->type == RANGED_CALL && + true_comparison_range_lr(comparison, tmp->range, value_range, left)) + (tmp->call_back)(fn, expr, tmp->info); + merge_slist(&true_states, __fake_cur_slist); + free_slist(&__fake_cur_slist); + } END_FOR_EACH_PTR(tmp); + + FOR_EACH_PTR(call_backs, tmp) { + if (tmp->type == RANGED_CALL && + false_comparison_range_lr(comparison, tmp->range, value_range, left)) + (tmp->call_back)(fn, expr, tmp->info); + merge_slist(&false_states, __fake_cur_slist); + free_slist(&__fake_cur_slist); + } END_FOR_EACH_PTR(tmp); + __fake_cur = 0; + + FOR_EACH_PTR(true_states, sm) { + __set_true_false_sm(sm, NULL); + } END_FOR_EACH_PTR(sm); + FOR_EACH_PTR(false_states, sm) { + __set_true_false_sm(NULL, sm); + } END_FOR_EACH_PTR(sm); + + if (true_states && !false_states) + smatch_msg("warning: unhandled false condition."); + if (!true_states && false_states) + smatch_msg("warning: unhandled true condition."); + free_slist(&true_states); + free_slist(&false_states); +} + void __match_initializer_call(struct symbol *sym) { struct call_back_list *call_backs; diff --git a/smatch_ranges.c b/smatch_ranges.c index 07c04c36..1c225d4b 100644 --- a/smatch_ranges.c +++ b/smatch_ranges.c @@ -14,6 +14,8 @@ ALLOCATOR(data_info, "smatch extra data"); ALLOCATOR(data_range, "data range"); +__DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range), + "permanent ranges", perm_data_range); static char *show_num(long long num) { @@ -83,6 +85,25 @@ struct data_range *alloc_range(long long min, long long max) return ret; } +struct data_range *alloc_range_perm(long long min, long long max) +{ + struct data_range *ret; + + if (min > max) { + printf("Error invalid range %lld to %lld\n", min, max); + } + if (min == whole_range.min && max == whole_range.max) + return &whole_range; + if (min == 0 && max == 0) + return &range_zero; + if (min == 1 && max == 1) + return &range_one; + ret = __alloc_perm_data_range(0); + ret->min = min; + ret->max = max; + return ret; +} + struct data_info *alloc_dinfo_range(long long min, long long max) { struct data_info *ret; @@ -251,7 +272,7 @@ long long get_single_value_from_range(struct data_info *dinfo) return ret; } -static int true_comparison_range(struct data_range *left, int comparison, struct data_range *right) +int true_comparison_range(struct data_range *left, int comparison, struct data_range *right) { switch(comparison){ case '<': @@ -295,6 +316,14 @@ static int true_comparison_range(struct data_range *left, int comparison, struct return 0; } +int true_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left) +{ + if (left) + return true_comparison_range(var, comparison, val); + else + return true_comparison_range(val, comparison, var); +} + static int false_comparison_range(struct data_range *left, int comparison, struct data_range *right) { switch(comparison){ @@ -339,6 +368,16 @@ static int false_comparison_range(struct data_range *left, int comparison, struc return 0; } +int false_comparison_range_lr(int comparison, struct data_range *var, struct data_range *val, int left) +{ + if (left) + return false_comparison_range(var, comparison, val); + else + return false_comparison_range(val, comparison, var); +} + + + int possibly_true(int comparison, struct data_info *dinfo, int num, int left) { struct data_range *tmp; diff --git a/smatch_states.c b/smatch_states.c index a6db6ebf..01ad9110 100644 --- a/smatch_states.c +++ b/smatch_states.c @@ -43,6 +43,8 @@ static struct state_list_stack *pre_cond_stack; /* states before a t/f branch */ static struct state_list_stack *cond_true_stack; /* states affected by a branch */ static struct state_list_stack *cond_false_stack; +int __fake_cur = 0; +struct state_list *__fake_cur_slist = NULL; int __fake_conditions = 0; struct state_list *__fake_cond_true = NULL; struct state_list *__fake_cond_false = NULL; @@ -100,6 +102,11 @@ void set_state(const char *name, int owner, struct symbol *sym, if (owner != -1 && unreachable()) return; + + if (__fake_cur) { + set_state_slist(&__fake_cur_slist, name, owner, sym, state); + return; + } set_state_slist(&cur_slist, name, owner, sym, state); -- 2.11.4.GIT