smatch_param_limit: extra: store parameter implications in return_states
authorDan Carpenter <dan.carpenter@oracle.com>
Fri, 14 Dec 2012 13:17:40 +0000 (14 16:17 +0300)
committerDan Carpenter <dan.carpenter@oracle.com>
Fri, 14 Dec 2012 13:17:40 +0000 (14 16:17 +0300)
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 <dan.carpenter@oracle.com>
Makefile
check_list.h
smatch.h
smatch_extra.c
smatch_param_limit.c [new file with mode: 0644]
smatch_scripts/db/fill_db_no_side_effects.pl [new file with mode: 0755]
smatch_scripts/db/fill_db_return_states.pl
smatch_scripts/db/no_side_effects.schema [new file with mode: 0644]

index 3a15f20..51fdbec 100644 (file)
--- 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 \
index 2086c17..fb3cbb6 100644 (file)
@@ -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)
index 274a23f..b7b13af 100644 (file)
--- 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);
index 9529db7..060e438 100644 (file)
@@ -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 (file)
index 0000000..778845e
--- /dev/null
@@ -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 (executable)
index 0000000..213ab23
--- /dev/null
@@ -0,0 +1,41 @@
+#!/usr/bin/perl -w
+
+use strict;
+use DBI;
+
+my $warns = shift;
+
+if (!defined($warns)) {
+    print "usage:  $0 <warns.txt>\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 (<WARNS>) {
+    # 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();
index 4be9836..be5cf8e 100755 (executable)
@@ -69,6 +69,11 @@ while (<WARNS>) {
         $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 (file)
index 0000000..938a08f
--- /dev/null
@@ -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);
+