From 7c6fe9d3bb7acc0e5b8fd8046017cf44988ed960 Mon Sep 17 00:00:00 2001 From: Dan Carpenter Date: Fri, 14 Dec 2012 16:17:40 +0300 Subject: [PATCH] smatch_param_limit: extra: store parameter implications in return_states This is a re-implementation of the stuff in check_param_range.c. The problem with that was that it added another table to the database and it conflicted with return_states. Sometimes they would both settings and it messed up the implications. Param_range was also sort of complicated. The new way is more powerful because it doesn't try to parse the code, it just uses smatch_extra.c. The problem with the new code is that it makes that database larger and it is a slow down. :( The new code saves the values of the parameters down each path. If we modify the parameter, then it preserves the original value and uses that instead. At the end of the path it prints out the parameter value together with the return value. I also made the code check if the function has side effects. I'm not ready to use that code just yet but it may be useful later... I should hold off committing that but I am a bad and lazy person. Signed-off-by: Dan Carpenter --- Makefile | 2 +- check_list.h | 2 + smatch.h | 1 + smatch_extra.c | 35 +++++ smatch_param_limit.c | 216 +++++++++++++++++++++++++++ smatch_scripts/db/fill_db_no_side_effects.pl | 41 +++++ smatch_scripts/db/fill_db_return_states.pl | 5 + smatch_scripts/db/no_side_effects.schema | 4 + 8 files changed, 305 insertions(+), 1 deletion(-) create mode 100644 smatch_param_limit.c create mode 100755 smatch_scripts/db/fill_db_no_side_effects.pl create mode 100644 smatch_scripts/db/no_side_effects.schema diff --git a/Makefile b/Makefile index 3a15f20e..51fdbec9 100644 --- a/Makefile +++ b/Makefile @@ -49,7 +49,7 @@ SMATCH_FILES=smatch_flow.o smatch_conditions.o smatch_slist.o smatch_states.o \ smatch_tracker.o smatch_files.o smatch_expression_stacks.o \ smatch_constraints.o smatch_buf_size.o smatch_capped.o smatch_db.o \ smatch_expressions.o smatch_returns.o smatch_parse_call_math.o \ - smatch_absolute.o + smatch_absolute.o smatch_param_limit.o SMATCH_CHECKS=$(shell ls check_*.c | sed -e 's/\.c/.o/') SMATCH_DATA=smatch_data/kernel.allocation_funcs smatch_data/kernel.balanced_funcs \ diff --git a/check_list.h b/check_list.h index 2086c17e..fb3cbb6b 100644 --- a/check_list.h +++ b/check_list.h @@ -14,6 +14,8 @@ CK(register_buf_size) CK(register_strlen) CK(register_capped) CK(register_parse_call_math) +CK(register_param_limit) +CK(register_param_limit2) CK(check_debug) CK(check_assigned_expr) diff --git a/smatch.h b/smatch.h index 274a23fe..b7b13af1 100644 --- a/smatch.h +++ b/smatch.h @@ -461,6 +461,7 @@ enum info_type { LOCK_HELD, LOCK_RELEASED, ABSOLUTE_LIMITS, + LIMITED_VALUE, }; void add_definition_db_callback(void (*callback)(const char *name, struct symbol *sym, char *key, char *value), int type); diff --git a/smatch_extra.c b/smatch_extra.c index 9529db72..060e4380 100644 --- a/smatch_extra.c +++ b/smatch_extra.c @@ -936,6 +936,40 @@ static void struct_member_callback(char *fn, char *global_static, int param, cha sm_msg("info: passes param_value '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static); } +static void db_limited_param(struct expression *expr, int param, char *key, char *value) +{ + struct expression *arg; + struct sm_state *sm; + struct symbol *type; + struct range_list *rl; + struct range_list *limit; + struct range_list *new; + + while (expr->type == EXPR_ASSIGNMENT) + expr = strip_expr(expr->right); + if (expr->type != EXPR_CALL) + return; + + arg = get_argument_from_call_expr(expr->args, param); + if (!arg) + return; + + sm = get_sm_state_expr(SMATCH_EXTRA, arg); + + type = get_type(arg); + if (!get_implied_range_list(arg, &rl)) + rl = whole_range_list(type); + + parse_value_ranges_type(type, value, &limit); + new = rl_intersection(rl, limit); + + /* We want to preserve the implications here */ + if (sm && range_lists_equiv(estate_ranges(sm->state), new)) + __set_sm(sm); + else + set_extra_expr_nomod(arg, alloc_estate_range_list(new)); +} + static void db_returned_states_param(struct expression *expr, int param, char *key, char *value) { struct expression *arg; @@ -1161,6 +1195,7 @@ void register_smatch_extra(int id) add_definition_db_callback(set_param_value, PARAM_VALUE); add_db_return_states_callback(RETURN_VALUE, &db_returned_member_info); add_db_return_states_callback(PARAM_VALUE, &db_returned_states_param); + add_db_return_states_callback(LIMITED_VALUE, &db_limited_param); } void register_smatch_extra_late(int id) diff --git a/smatch_param_limit.c b/smatch_param_limit.c new file mode 100644 index 00000000..778845e6 --- /dev/null +++ b/smatch_param_limit.c @@ -0,0 +1,216 @@ +/* + * sparse/smatch_param_limit.c + * + * Copyright (C) 2012 Oracle. + * + * Licensed under the Open Software License version 1.1 + * + */ + +#include "scope.h" +#include "smatch.h" +#include "smatch_extra.h" + +static int orig_id; +static int modify_id; +static int side_effects; + +STATE(modified); + +static struct smatch_state *unmatched_state(struct sm_state *sm) +{ + return extra_undefined(estate_type(sm->state)); +} + +int was_modified_sym(struct symbol *sym) +{ + if (!side_effects) + return 0; + if (!sym || !sym->ident) + return 1; /* safer to say it was modified? */ + if (get_state(modify_id, sym->ident->name, sym)) + return 1; + return 0; +} + +static int is_local(struct symbol *sym) +{ + if (!sym->scope || !sym->scope->token) + return 0; + return 1; +} + +static void check_expr(struct expression *expr) +{ + struct smatch_state *state; + struct symbol *sym; + char *name; + + name = get_variable_from_expr_complex(expr, &sym); + if (!sym) { + side_effects = 1; + goto free; + } + + if (!is_local(sym)) + side_effects = 1; + + /* + * Pointers are so tricky to handle just bail. + */ + if (get_real_base_type(sym)->type == SYM_PTR) + side_effects = 1; + + /* + * TODO: it should only do this if we modify something that's not on the + * stack. + */ + if (get_param_num_from_sym(sym) >= 0) { + side_effects = 1; + if (!get_state_expr(orig_id, expr)) { + state = get_implied_estate(expr); + set_state_expr(orig_id, expr, state); + } + } + + set_state_expr(modify_id, expr, &modified); +free: + free_string(name); +} + +static void match_assign(struct expression *expr) +{ + check_expr(expr->left); +} + +static void unop_expr(struct expression *expr) +{ + if (expr->op != SPECIAL_DECREMENT && expr->op != SPECIAL_INCREMENT) + return; + + expr = strip_expr(expr->unop); + check_expr(expr); +} + +static int no_effect_func; +static int db_no_effect_func(void *unused, int argc, char **argv, char **azColName) +{ + no_effect_func = 1; + return 0; +} + +static int is_no_side_effect_func(struct expression *fn) +{ + static char sql_filter[1024]; + + if (fn->type != EXPR_SYMBOL || !fn->symbol) + return 0; + + if (fn->symbol->ctype.modifiers & MOD_STATIC) { + snprintf(sql_filter, 1024, "file = '%s' and function = '%s';", + get_filename(), fn->symbol->ident->name); + } else { + snprintf(sql_filter, 1024, "function = '%s' and static = 0;", + fn->symbol->ident->name); + } + + no_effect_func = 0; + run_sql(db_no_effect_func, "select * from no_side_effects where %s", sql_filter); + + return no_effect_func; +} + +static void match_call(struct expression *expr) +{ + struct expression *arg, *tmp; + + if (!is_no_side_effect_func(expr->fn)) + side_effects = 1; + + FOR_EACH_PTR(expr->args, arg) { + tmp = strip_expr(arg); + if (tmp->type != EXPR_PREOP || tmp->op != '&') + continue; + tmp = strip_expr(tmp->unop); + check_expr(expr); + } END_FOR_EACH_PTR(arg); +} + +static void asm_expr(struct statement *stmt) +{ + + struct expression *expr; + int state = 0; + + FOR_EACH_PTR(stmt->asm_outputs, expr) { + switch (state) { + case 0: /* identifier */ + case 1: /* constraint */ + state++; + continue; + case 2: /* expression */ + state = 0; + check_expr(expr); + continue; + } + } END_FOR_EACH_PTR(expr); +} + +struct smatch_state *get_orig_estate(struct symbol *sym) +{ + struct smatch_state *state; + + if (!sym->ident || !sym->ident->name) + return NULL; + + state = get_state(orig_id, sym->ident->name, sym); + if (state) + return state; + + return get_state(SMATCH_EXTRA, sym->ident->name, sym); +} + +static void print_return_value_param(int return_id, char *return_ranges, struct expression *expr, struct state_list *slist) +{ + struct smatch_state *state; + struct symbol *tmp; + int param; + + param = -1; + FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, tmp) { + param++; + state = get_orig_estate(tmp); + if (!state) + continue; + sm_msg("info: return_limited_param %d %d '%s' '$$' '%s' %s", + return_id, param, return_ranges, + state->name, global_static()); + } END_FOR_EACH_PTR(tmp); +} + +static void match_end_func(struct symbol *sym) +{ + if (option_info && !side_effects) + sm_msg("info: no_side_effects %s", global_static()); + side_effects = 0; +} + +void register_param_limit(int id) +{ + modify_id = id; + + add_hook(&match_assign, ASSIGNMENT_HOOK); + add_hook(&unop_expr, OP_HOOK); + add_hook(&match_call, FUNCTION_CALL_HOOK); + add_hook(&asm_expr, ASM_HOOK); + add_hook(&match_end_func, END_FUNC_HOOK); + add_returned_state_callback(&print_return_value_param); +} + +void register_param_limit2(int id) +{ + orig_id = id; + add_merge_hook(orig_id, &merge_estates); + add_unmatched_state_hook(orig_id, &unmatched_state); +} + diff --git a/smatch_scripts/db/fill_db_no_side_effects.pl b/smatch_scripts/db/fill_db_no_side_effects.pl new file mode 100755 index 00000000..213ab238 --- /dev/null +++ b/smatch_scripts/db/fill_db_no_side_effects.pl @@ -0,0 +1,41 @@ +#!/usr/bin/perl -w + +use strict; +use DBI; + +my $warns = shift; + +if (!defined($warns)) { + print "usage: $0 \n"; + exit(1); +} + +my $db = DBI->connect("dbi:SQLite:smatch_db.sqlite", "", "", {AutoCommit => 0}); +$db->do("PRAGMA synchronous = OFF"); +$db->do("PRAGMA cache_size = 800000"); +$db->do("PRAGMA journal_mode = OFF"); + +$db->do("delete from no_side_effects;"); + +my ($file_and_line, $file, $func, $gs, $static, $dummy); + +open(WARNS, "<$warns"); +while () { + # info: no_side_effects + if (!($_ =~ /info: no_side_effects /)) { + next; + } + + ($file_and_line, $func, $dummy, $dummy, $gs) = split(/ /, $_); + ($file, $dummy) = split(/:/, $file_and_line); + $func =~ s/\(\)//; + + $static = 0; + if ($gs =~ /static/) { + $static = 1; + } + + $db->do("insert into no_side_effects values ('$file', '$func', $static)"); +} +$db->commit(); +$db->disconnect(); diff --git a/smatch_scripts/db/fill_db_return_states.pl b/smatch_scripts/db/fill_db_return_states.pl index 4be98364..be5cf8e8 100755 --- a/smatch_scripts/db/fill_db_return_states.pl +++ b/smatch_scripts/db/fill_db_return_states.pl @@ -69,6 +69,11 @@ while () { $type = 1; # PARAM_VALUE ($file_and_line, $func, $dummy, $dummy, $return_id, $param, $dummy) = split(/ /, $_); ($dummy, $return_value, $dummy, $key, $dummy, $value, $gs) = split(/'/, $_); + } elsif ($_ =~ /info: return_limited_param /) { + # test.c:11 set_int() info: return_value_param 0 0 '' '*$$' '1' global + $type = 11; # LIMITED_VALUE + ($file_and_line, $func, $dummy, $dummy, $return_id, $param, $dummy) = split(/ /, $_); + ($dummy, $return_value, $dummy, $key, $dummy, $value, $gs) = split(/'/, $_); } else { next; } diff --git a/smatch_scripts/db/no_side_effects.schema b/smatch_scripts/db/no_side_effects.schema new file mode 100644 index 00000000..938a08f2 --- /dev/null +++ b/smatch_scripts/db/no_side_effects.schema @@ -0,0 +1,4 @@ +CREATE TABLE no_side_effects (file varchar(256), function varchar(256), static integer); + +CREATE INDEX no_effects_idx on no_side_effects (file, function); + -- 2.11.4.GIT