smatch_stored_conditions.c

   1 /*
   2  * Copyright (C) 2014 Oracle.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * Keep a record of all the things we have tested for so that we know when we
  20  * test for it again.  For example, if we have code like this:
  21  *
  22  *      if (foo & FLAG)
  23  *              lock();
  24  *
  25  *      ...
  26  *
  27  *      if (foo & FLAG)
  28  *              unlock();
  29  *
  30  * That's the end goal at least.  But actually implementing the flow of that
  31  * requires quite a bit of work because if "foo" changes the condition needs to
  32  * be retested and smatch_implications.c needs to be updated.
  33  *
  34  * For now, I just record the conditions and use it to see if we test for NULL
  35  * twice.
  36  *
  37  */
  38
  39 #include "smatch.h"
  40 #include "smatch_slist.h"
  41
  42 static int my_id;
  43 static int link_id;
  44
  45 static struct smatch_state *alloc_link_state(struct expression_list *expr_list)
  46 {
  47         struct expression *tmp;
  48         struct smatch_state *state;
  49         static char buf[256];
  50         char *name;
  51         int i;
  52
  53         state = __alloc_smatch_state(0);
  54
  55         i = 0;
  56         FOR_EACH_PTR(expr_list, tmp) {
  57                 name = expr_to_str(tmp);
  58                 if (!i++) {
  59                         snprintf(buf, sizeof(buf), "%s", name);
  60                 } else {
  61                         append(buf, ", ", sizeof(buf));
  62                         append(buf, name, sizeof(buf));
  63                 }
  64                 free_string(name);
  65         } END_FOR_EACH_PTR(tmp);
  66
  67         state->name = alloc_sname(buf);
  68         state->data = expr_list;
  69         return state;
  70 }
  71
  72 static struct expression_list *clone_expression_list(struct expression_list *list)
  73 {
  74         struct expression_list *ret = NULL;
  75         struct expression *expr;
  76
  77         FOR_EACH_PTR(list, expr) {
  78                 add_ptr_list(&ret, expr);
  79         } END_FOR_EACH_PTR(expr);
  80
  81         return ret;
  82 }
  83
  84 static void insert_expression(struct expression_list **list, struct expression *expr)
  85 {
  86         struct expression *tmp;
  87
  88         FOR_EACH_PTR(*list, tmp) {
  89                 if (tmp == expr)
  90                         return;
  91         } END_FOR_EACH_PTR(tmp);
  92
  93         add_ptr_list(list, expr);
  94 }
  95
  96 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
  97 {
  98         struct expression_list *list, *expr_list;
  99         struct expression *expr;
 100
 101         expr_list = clone_expression_list(s1->data);
 102
 103         list = s2->data;
 104         FOR_EACH_PTR(list, expr) {
 105                 insert_expression(&expr_list, expr);
 106         } END_FOR_EACH_PTR(expr);
 107
 108         return alloc_link_state(expr_list);
 109 }
 110
 111 static void save_link_var_sym(const char *var, struct symbol *sym, struct expression *condition)
 112 {
 113         struct smatch_state *old_state, *new_state;
 114         struct expression_list *expr_list;
 115
 116         old_state = get_state(link_id, var, sym);
 117         expr_list = clone_expression_list(old_state ? old_state->data : NULL);
 118
 119         insert_expression(&expr_list, condition);
 120
 121         new_state = alloc_link_state(expr_list);
 122         set_state(link_id, var, sym, new_state);
 123 }
 124
 125 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
 126 {
 127         struct expression_list *expr_list;
 128         struct expression *tmp;
 129         char *name;
 130
 131         expr_list = sm->state->data;
 132
 133         FOR_EACH_PTR(expr_list, tmp) {
 134                 name = expr_to_str(tmp);
 135                 set_state(my_id, name, NULL, &undefined);
 136                 free_string(name);
 137         } END_FOR_EACH_PTR(tmp);
 138         set_state(link_id, sm->name, sm->sym, &undefined);
 139 }
 140
 141 static struct smatch_state *alloc_state(struct expression *expr, int is_true)
 142 {
 143         struct smatch_state *state;
 144
 145         state = __alloc_smatch_state(0);
 146         if (is_true)
 147                 state->name = alloc_sname("true");
 148         else
 149                 state->name = alloc_sname("false");
 150         state->data = expr;
 151         return state;
 152 }
 153
 154 static void store_all_links(struct expression *expr, struct expression *condition)
 155 {
 156         char *var;
 157         struct symbol *sym;
 158
 159         expr = strip_expr(expr);
 160
 161         if (is_array(expr)) {
 162                 var = expr_to_known_chunk_sym(expr, &sym);
 163                 if (var)
 164                         save_link_var_sym(var, sym, condition);
 165         }
 166
 167         switch (expr->type) {
 168         case EXPR_COMPARE:
 169         case EXPR_BINOP:
 170                 store_all_links(expr->left, condition);
 171                 store_all_links(expr->right, condition);
 172                 return;
 173         case EXPR_VALUE:
 174                 return;
 175         }
 176
 177         var = expr_to_var_sym(expr, &sym);
 178         if (!var || !sym)
 179                 goto free;
 180         save_link_var_sym(var, sym, condition);
 181 free:
 182         free_string(var);
 183 }
 184
 185 static int condition_too_complicated(struct expression *expr)
 186 {
 187         if (get_complication_score(expr) > 2)
 188                 return 1;
 189         return 0;
 190 }
 191
 192 void __stored_condition(struct expression *expr)
 193 {
 194         struct smatch_state *true_state, *false_state;
 195         char *name;
 196         sval_t val;
 197
 198         if (get_value(expr, &val))
 199                 return;
 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, expr);
 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 struct expression_list *get_conditions(struct expression *expr)
 229 {
 230         struct smatch_state *state;
 231
 232         state = get_state_expr(link_id, expr);
 233         if (!state)
 234                 return NULL;
 235         return state->data;
 236 }
 237
 238 void register_stored_conditions(int id)
 239 {
 240         my_id = id;
 241         set_dynamic_states(my_id);
 242 }
 243
 244 void register_stored_conditions_links(int id)
 245 {
 246         link_id = id;
 247         db_ignore_states(link_id);
 248         set_dynamic_states(link_id);
 249         add_merge_hook(link_id, &merge_links);
 250         add_modification_hook(link_id, &match_link_modify);
 251 }
 252
 253 #define RECURSE_LIMIT 50
 254
 255 static void filter_by_sm(struct sm_state *sm,
 256                        struct state_list **true_stack,
 257                        struct state_list **false_stack,
 258                        int *recurse_cnt)
 259 {
 260         if (!sm)
 261                 return;
 262
 263         if ((*recurse_cnt)++ > RECURSE_LIMIT)
 264                 return;
 265
 266         if (strcmp(sm->state->name, "true") == 0) {
 267                 add_ptr_list(true_stack, sm);
 268         } else if (strcmp(sm->state->name, "false") == 0) {
 269                 add_ptr_list(false_stack, sm);
 270         }
 271
 272         if (sm->merged) {
 273                 filter_by_sm(sm->left, true_stack, false_stack, recurse_cnt);
 274                 filter_by_sm(sm->right, true_stack, false_stack, recurse_cnt);
 275         }
 276 }
 277
 278 struct sm_state *stored_condition_implication_hook(struct expression *expr,
 279                                 struct state_list **true_stack,
 280                                 struct state_list **false_stack)
 281 {
 282         struct sm_state *sm;
 283         char *name;
 284         int recurse_cnt = 0;
 285         struct state_list *tmp_true = NULL;
 286         struct state_list *tmp_false = NULL;
 287         struct sm_state *tmp;
 288
 289         expr = strip_expr(expr);
 290
 291         name = expr_to_str(expr);
 292         if (!name)
 293                 return NULL;
 294
 295         sm = get_sm_state(my_id, name, NULL);
 296         free_string(name);
 297         if (!sm)
 298                 return NULL;
 299         if (!sm->merged)
 300                 return NULL;
 301
 302         filter_by_sm(sm, &tmp_true, &tmp_false, &recurse_cnt);
 303         if (!tmp_true && !tmp_false)
 304                 return NULL;
 305         if (recurse_cnt > RECURSE_LIMIT) {
 306                 sm = NULL;
 307                 goto free;
 308         }
 309
 310         FOR_EACH_PTR(tmp_true, tmp) {
 311                 add_ptr_list(true_stack, tmp);
 312         } END_FOR_EACH_PTR(tmp);
 313
 314         FOR_EACH_PTR(tmp_false, tmp) {
 315                 add_ptr_list(false_stack, tmp);
 316         } END_FOR_EACH_PTR(tmp);
 317
 318 free:
 319         free_slist(&tmp_true);
 320         free_slist(&tmp_false);
 321         return sm;
 322 }
 323