smatch_stored_conditions.c

   1 /*
   2  * sparse/smatch_stored_conditions.c
   3  *
   4  * Copyright (C) 2014 Oracle.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * Keep a record of all the things we have tested for so that we know when we
  12  * test for it again.  For example, if we have code like this:
  13  *
  14  *      if (foo & FLAG)
  15  *              lock();
  16  *
  17  *      ...
  18  *
  19  *      if (foo & FLAG)
  20  *              unlock();
  21  *
  22  * That's the end goal at least.  But actually implementing the flow of that
  23  * requires quite a bit of work because if "foo" changes the condition needs to
  24  * be retested and smatch_implications.c needs to be updated.
  25  *
  26  * For now, I just record the conditions and use it to see if we test for NULL
  27  * twice.
  28  *
  29  */
  30
  31 #include "smatch.h"
  32 #include "smatch_slist.h"
  33
  34 static int my_id;
  35 static int link_id;
  36
  37 static struct smatch_state *alloc_link_state(struct string_list *links)
  38 {
  39         struct smatch_state *state;
  40         static char buf[256];
  41         char *tmp;
  42         int i;
  43
  44         state = __alloc_smatch_state(0);
  45
  46         i = 0;
  47         FOR_EACH_PTR(links, tmp) {
  48                 if (!i++) {
  49                         snprintf(buf, sizeof(buf), "%s", tmp);
  50                 } else {
  51                         append(buf, ", ", sizeof(buf));
  52                         append(buf, tmp, sizeof(buf));
  53                 }
  54         } END_FOR_EACH_PTR(tmp);
  55
  56         state->name = alloc_sname(buf);
  57         state->data = links;
  58         return state;
  59 }
  60
  61 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
  62 {
  63         struct smatch_state *ret;
  64         struct string_list *links;
  65
  66         links = combine_string_lists(s1->data, s2->data);
  67         ret = alloc_link_state(links);
  68         return ret;
  69 }
  70
  71 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
  72 {
  73         struct smatch_state *old_state, *new_state;
  74         struct string_list *links;
  75         char *new;
  76
  77         old_state = get_state(link_id, var, sym);
  78         if (old_state)
  79                 links = clone_str_list(old_state->data);
  80         else
  81                 links = NULL;
  82
  83         new = alloc_sname(link);
  84         insert_string(&links, new);
  85
  86         new_state = alloc_link_state(links);
  87         set_state(link_id, var, sym, new_state);
  88 }
  89
  90 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
  91 {
  92         struct string_list *links;
  93         char *tmp;
  94
  95         links = sm->state->data;
  96
  97         FOR_EACH_PTR(links, tmp) {
  98                 set_state(my_id, tmp, NULL, &undefined);
  99         } END_FOR_EACH_PTR(tmp);
 100         set_state(link_id, sm->name, sm->sym, &undefined);
 101 }
 102
 103 static struct smatch_state *alloc_state(struct expression *expr, int is_true)
 104 {
 105         struct smatch_state *state;
 106
 107         state = __alloc_smatch_state(0);
 108         if (is_true)
 109                 state->name = alloc_sname("true");
 110         else
 111                 state->name = alloc_sname("false");
 112         state->data = expr;
 113         return state;
 114 }
 115
 116 static int is_local_variable(struct expression *expr)
 117 {
 118         struct symbol *sym;
 119         char *name;
 120
 121         name = expr_to_var_sym(expr, &sym);
 122         free_string(name);
 123         if (!sym || !sym->scope || !sym->scope->token)
 124                 return 0;
 125         if (cmp_pos(sym->scope->token->pos, cur_func_sym->pos) < 0)
 126                 return 0;
 127         if (is_static(expr))
 128                 return 0;
 129         return 1;
 130 }
 131
 132 static int get_complication_score(struct expression *expr)
 133 {
 134         int score = 0;
 135
 136         expr = strip_expr(expr);
 137
 138         switch (expr->type) {
 139         case EXPR_CALL:
 140                 return 999;
 141         case EXPR_LOGICAL:
 142         case EXPR_BINOP:
 143                 score += get_complication_score(expr->left);
 144                 score += get_complication_score(expr->right);
 145                 return score;
 146         case EXPR_SYMBOL:
 147                 if (is_local_variable(expr))
 148                         return 1;
 149                 return 999;
 150         case EXPR_VALUE:
 151                 return 0;
 152 #if 0
 153         case EXPR_PREOP:
 154                 if (expr->op == SPECIAL_INCREMENT ||
 155                     expr->op == SPECIAL_DECREMENT)
 156                         return 999;
 157                 return get_complication_score(expr->unop);
 158 #endif
 159         default:
 160                 return 999;
 161         }
 162 }
 163
 164 static int condition_too_complicated(struct expression *expr)
 165 {
 166         if (get_complication_score(expr) > 2)
 167                 return 1;
 168         return 0;
 169
 170 }
 171
 172 static void store_all_links(struct expression *expr, const char *condition)
 173 {
 174         char *var;
 175         struct symbol *sym;
 176
 177         expr = strip_expr(expr);
 178
 179         switch (expr->type) {
 180         case EXPR_BINOP:
 181                 store_all_links(expr->left, condition);
 182                 store_all_links(expr->right, condition);
 183                 return;
 184         case EXPR_VALUE:
 185                 return;
 186         }
 187
 188         var = expr_to_var_sym(expr, &sym);
 189         if (!var || !sym)
 190                 goto free;
 191         save_link_var_sym(var, sym, condition);
 192 free:
 193         free_string(var);
 194 }
 195
 196 static void match_condition(struct expression *expr)
 197 {
 198         struct smatch_state *true_state, *false_state;
 199         char *name;
 200
 201         if (condition_too_complicated(expr))
 202                 return;
 203
 204         name = expr_to_str(expr);
 205         if (!name)
 206                 return;
 207         true_state = alloc_state(expr, TRUE);
 208         false_state = alloc_state(expr, FALSE);
 209         set_true_false_states(my_id, name, NULL, true_state, false_state);
 210         store_all_links(expr, alloc_sname(name));
 211         free_string(name);
 212 }
 213
 214 struct smatch_state *get_stored_condition(struct expression *expr)
 215 {
 216         struct smatch_state *state;
 217         char *name;
 218
 219         name = expr_to_str(expr);
 220         if (!name)
 221                 return NULL;
 222
 223         state = get_state(my_id, name, NULL);
 224         free_string(name);
 225         return state;
 226 }
 227
 228 void register_stored_conditions(int id)
 229 {
 230         my_id = id;
 231
 232         add_hook(&match_condition, CONDITION_HOOK);
 233 }
 234
 235 void register_stored_conditions_links(int id)
 236 {
 237         link_id = id;
 238         add_merge_hook(link_id, &merge_links);
 239         add_modification_hook(link_id, &match_modify);
 240 }
 241