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