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 string_list *links)
  46 {
  47         struct smatch_state *state;
  48         static char buf[256];
  49         char *tmp;
  50         int i;
  51
  52         state = __alloc_smatch_state(0);
  53
  54         i = 0;
  55         FOR_EACH_PTR(links, tmp) {
  56                 if (!i++) {
  57                         snprintf(buf, sizeof(buf), "%s", tmp);
  58                 } else {
  59                         append(buf, ", ", sizeof(buf));
  60                         append(buf, tmp, sizeof(buf));
  61                 }
  62         } END_FOR_EACH_PTR(tmp);
  63
  64         state->name = alloc_sname(buf);
  65         state->data = links;
  66         return state;
  67 }
  68
  69 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
  70 {
  71         struct smatch_state *ret;
  72         struct string_list *links;
  73
  74         links = combine_string_lists(s1->data, s2->data);
  75         ret = alloc_link_state(links);
  76         return ret;
  77 }
  78
  79 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link)
  80 {
  81         struct smatch_state *old_state, *new_state;
  82         struct string_list *links;
  83         char *new;
  84
  85         old_state = get_state(link_id, var, sym);
  86         if (old_state)
  87                 links = clone_str_list(old_state->data);
  88         else
  89                 links = NULL;
  90
  91         new = alloc_sname(link);
  92         insert_string(&links, new);
  93
  94         new_state = alloc_link_state(links);
  95         set_state(link_id, var, sym, new_state);
  96 }
  97
  98 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
  99 {
 100         struct string_list *links;
 101         char *tmp;
 102
 103         links = sm->state->data;
 104
 105         FOR_EACH_PTR(links, tmp) {
 106                 set_state(my_id, tmp, NULL, &undefined);
 107         } END_FOR_EACH_PTR(tmp);
 108         set_state(link_id, sm->name, sm->sym, &undefined);
 109 }
 110
 111 static struct smatch_state *alloc_state(struct expression *expr, int is_true)
 112 {
 113         struct smatch_state *state;
 114
 115         state = __alloc_smatch_state(0);
 116         if (is_true)
 117                 state->name = alloc_sname("true");
 118         else
 119                 state->name = alloc_sname("false");
 120         state->data = expr;
 121         return state;
 122 }
 123
 124 static void store_all_links(struct expression *expr, const char *condition)
 125 {
 126         char *var;
 127         struct symbol *sym;
 128
 129         expr = strip_expr(expr);
 130
 131         if (is_array(expr)) {
 132                 var = expr_to_known_chunk_sym(expr, &sym);
 133                 if (var)
 134                         save_link_var_sym(var, sym, condition);
 135         }
 136
 137         switch (expr->type) {
 138         case EXPR_COMPARE:
 139         case EXPR_BINOP:
 140                 store_all_links(expr->left, condition);
 141                 store_all_links(expr->right, condition);
 142                 return;
 143         case EXPR_VALUE:
 144                 return;
 145         }
 146
 147         var = expr_to_var_sym(expr, &sym);
 148         if (!var || !sym)
 149                 goto free;
 150         save_link_var_sym(var, sym, condition);
 151 free:
 152         free_string(var);
 153 }
 154
 155 static int condition_too_complicated(struct expression *expr)
 156 {
 157         if (get_complication_score(expr) > 2)
 158                 return 1;
 159         return 0;
 160
 161 }
 162
 163 void __stored_condition(struct expression *expr)
 164 {
 165         struct smatch_state *true_state, *false_state;
 166         char *name;
 167         sval_t val;
 168
 169         if (get_implied_value(expr, &val))
 170                 return;
 171
 172         if (condition_too_complicated(expr))
 173                 return;
 174
 175         name = expr_to_str(expr);
 176         if (!name)
 177                 return;
 178         true_state = alloc_state(expr, TRUE);
 179         false_state = alloc_state(expr, FALSE);
 180         set_true_false_states(my_id, name, NULL, true_state, false_state);
 181         store_all_links(expr, alloc_sname(name));
 182         free_string(name);
 183 }
 184
 185 struct smatch_state *get_stored_condition(struct expression *expr)
 186 {
 187         struct smatch_state *state;
 188         char *name;
 189
 190         name = expr_to_str(expr);
 191         if (!name)
 192                 return NULL;
 193
 194         state = get_state(my_id, name, NULL);
 195         free_string(name);
 196         return state;
 197 }
 198
 199 void register_stored_conditions(int id)
 200 {
 201         my_id = id;
 202 }
 203
 204 void register_stored_conditions_links(int id)
 205 {
 206         link_id = id;
 207         add_merge_hook(link_id, &merge_links);
 208         add_modification_hook(link_id, &match_link_modify);
 209 }
 210
 211 #define RECURSE_LIMIT 50
 212
 213 static void filter_by_sm(struct sm_state *sm,
 214                        struct stree_stack **true_stack,
 215                        struct stree_stack **false_stack,
 216                        int *recurse_cnt)
 217 {
 218         if (!sm)
 219                 return;
 220
 221         if ((*recurse_cnt)++ > RECURSE_LIMIT)
 222                 return;
 223
 224         if (strcmp(sm->state->name, "true") == 0) {
 225                 add_pool(true_stack, sm->pool);
 226         } else if (strcmp(sm->state->name, "false") == 0) {
 227                 add_pool(false_stack, sm->pool);
 228         }
 229
 230         if (sm->merged) {
 231                 filter_by_sm(sm->left, true_stack, false_stack, recurse_cnt);
 232                 filter_by_sm(sm->right, true_stack, false_stack, recurse_cnt);
 233         }
 234 }
 235
 236 struct sm_state *stored_condition_implication_hook(struct expression *expr,
 237                                 struct stree_stack **true_stack,
 238                                 struct stree_stack **false_stack)
 239 {
 240         struct sm_state *sm;
 241         char *name;
 242         int recurse_cnt = 0;
 243         struct stree_stack *tmp_true = NULL;
 244         struct stree_stack *tmp_false = NULL;
 245         struct stree *stree;
 246
 247         expr = strip_expr(expr);
 248
 249         /*
 250          * We only look at BINOP here because smatch_extra.c and
 251          * smatch_compare.c handle everything else.
 252          */
 253         if (expr->type != EXPR_BINOP)
 254                 return NULL;
 255
 256         name = expr_to_str(expr);
 257         if (!name)
 258                 return NULL;
 259
 260         sm = get_sm_state(my_id, name, NULL);
 261         free_string(name);
 262         if (!sm)
 263                 return NULL;
 264         if (!sm->merged)
 265                 return NULL;
 266
 267         filter_by_sm(sm, &tmp_true, &tmp_false, &recurse_cnt);
 268         if (!tmp_true && !tmp_false)
 269                 return NULL;
 270         if (recurse_cnt > RECURSE_LIMIT) {
 271                 sm = NULL;
 272                 goto free;
 273         }
 274
 275         FOR_EACH_PTR(tmp_true, stree) {
 276                 add_pool(true_stack, stree);
 277         } END_FOR_EACH_PTR(stree);
 278
 279         FOR_EACH_PTR(tmp_false, stree) {
 280                 add_pool(false_stack, stree);
 281         } END_FOR_EACH_PTR(stree);
 282
 283 free:
 284         free_stree_stack(&tmp_true);
 285         free_stree_stack(&tmp_false);
 286         return sm;
 287 }
 288