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_extra.h"
  41 #include "smatch_slist.h"
  42
  43 static int my_id;
  44 static int link_id;
  45
  46 static struct smatch_state *alloc_link_state(struct expression_list *expr_list)
  47 {
  48         struct expression *tmp;
  49         struct smatch_state *state;
  50         static char buf[256] = "";
  51         char *name;
  52         int cnt = 0;
  53
  54         state = __alloc_smatch_state(0);
  55
  56         FOR_EACH_PTR(expr_list, tmp) {
  57                 name = expr_to_str(tmp);
  58                 cnt += snprintf(buf + cnt, sizeof(buf) - cnt, "%s%s",
  59                                 cnt ? ", " : "", name);
  60                 free_string(name);
  61                 if (cnt >= sizeof(buf))
  62                         goto done;
  63         } END_FOR_EACH_PTR(tmp);
  64
  65 done:
  66         state->name = alloc_sname(buf);
  67         state->data = expr_list;
  68         return state;
  69 }
  70
  71 static struct expression_list *clone_expression_list(struct expression_list *list)
  72 {
  73         struct expression_list *ret = NULL;
  74         struct expression *expr;
  75
  76         FOR_EACH_PTR(list, expr) {
  77                 add_ptr_list(&ret, expr);
  78         } END_FOR_EACH_PTR(expr);
  79
  80         return ret;
  81 }
  82
  83 static void insert_expression(struct expression_list **list, struct expression *expr)
  84 {
  85         struct expression *tmp;
  86
  87         FOR_EACH_PTR(*list, tmp) {
  88                 if (tmp == expr)
  89                         return;
  90         } END_FOR_EACH_PTR(tmp);
  91
  92         add_ptr_list(list, expr);
  93 }
  94
  95 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
  96 {
  97         struct expression_list *list, *expr_list;
  98         struct expression *expr;
  99
 100         expr_list = clone_expression_list(s1->data);
 101
 102         list = s2->data;
 103         FOR_EACH_PTR(list, expr) {
 104                 insert_expression(&expr_list, expr);
 105         } END_FOR_EACH_PTR(expr);
 106
 107         return alloc_link_state(expr_list);
 108 }
 109
 110 static void save_link_var_sym(const char *var, struct symbol *sym, struct expression *condition)
 111 {
 112         struct smatch_state *old_state, *new_state;
 113         struct expression_list *expr_list;
 114
 115         old_state = get_state(link_id, var, sym);
 116         expr_list = clone_expression_list(old_state ? old_state->data : NULL);
 117
 118         insert_expression(&expr_list, condition);
 119
 120         new_state = alloc_link_state(expr_list);
 121         set_state(link_id, var, sym, new_state);
 122 }
 123
 124 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
 125 {
 126         struct expression_list *expr_list;
 127         struct expression *tmp;
 128         char *name;
 129
 130         expr_list = sm->state->data;
 131
 132         FOR_EACH_PTR(expr_list, tmp) {
 133                 name = expr_to_str(tmp);
 134                 set_state(my_id, name, NULL, &undefined);
 135                 free_string(name);
 136         } END_FOR_EACH_PTR(tmp);
 137         set_state(link_id, sm->name, sm->sym, &undefined);
 138 }
 139
 140 static void match_untracked(struct expression *call, int param)
 141 {
 142         struct expression *arg;
 143         struct sm_state *sm;
 144         struct symbol *sym;
 145
 146         /*
 147          * NOTE: I wrote this patch because of a misunderstanding.  The
 148          * untracked parameter wasn't a stored condition, it was something
 149          * in smatch_extra and then we get the stored implication via an
 150          * implication later...  Ugh.  That explanation is too complicated.
 151          * I should just delete this code, but it feels more correct than
 152          * the original code.  Plus it was a lot of work to write it.
 153          *
 154          */
 155
 156         arg = get_argument_from_call_expr(call->args, param);
 157         sym = expr_to_sym(arg);
 158         if (!sym)
 159                 return;
 160
 161         FOR_EACH_MY_SM(link_id, __get_cur_stree(), sm) {
 162                 if (sm->sym == sym)
 163                         match_link_modify(sm, NULL);
 164         } END_FOR_EACH_SM(sm);
 165 }
 166
 167 static struct smatch_state *alloc_state(struct expression *expr, int is_true)
 168 {
 169         struct smatch_state *state;
 170
 171         state = __alloc_smatch_state(0);
 172         if (is_true)
 173                 state->name = alloc_sname("true");
 174         else
 175                 state->name = alloc_sname("false");
 176         state->data = expr;
 177         return state;
 178 }
 179
 180 static void store_all_links(struct expression *expr, struct expression *condition)
 181 {
 182         struct var_sym_list *vsl;
 183         struct var_sym *vs;
 184         char *var;
 185         struct symbol *sym;
 186
 187         expr = strip_expr(expr);
 188         if (!expr)
 189                 return;
 190
 191         vsl = expr_to_vsl(expr);
 192         FOR_EACH_PTR(vsl, vs) {
 193                 save_link_var_sym(vs->var, vs->sym, condition);
 194         } END_FOR_EACH_PTR(vs);
 195
 196         /* This is used to store "array[0]" from "if (array[0] == 1) " */
 197         var = expr_to_known_chunk_sym(expr, &sym);
 198         if (!var && !sym)
 199                 goto free;
 200         save_link_var_sym(var, sym, condition);
 201 free:
 202         free_string(var);
 203 }
 204
 205 static int is_untracked_var_helper(struct expression *expr, void *unused)
 206 {
 207         if (expr->type == EXPR_SYMBOL)
 208                 return is_untracked(expr);
 209         return 0;
 210 }
 211
 212 static int condition_too_complicated(struct expression *expr)
 213 {
 214         if (get_complication_score(expr) > 2)
 215                 return 1;
 216         if (recurse(expr, is_untracked_var_helper, NULL, 0) == 1)
 217                 return 1;
 218         return 0;
 219 }
 220
 221 void __stored_condition(struct expression *expr)
 222 {
 223         struct smatch_state *true_state, *false_state;
 224         char *name;
 225
 226         if (implied_condition_true(expr) ||
 227             implied_condition_false(expr))
 228                 return;
 229
 230         if (condition_too_complicated(expr))
 231                 return;
 232
 233         name = expr_to_str(expr);
 234         if (!name)
 235                 return;
 236         true_state = alloc_state(expr, TRUE);
 237         false_state = alloc_state(expr, FALSE);
 238
 239         set_true_false_states(my_id, name, NULL, true_state, false_state);
 240         store_all_links(expr, expr);
 241         free_string(name);
 242 }
 243
 244 struct smatch_state *get_stored_condition(struct expression *expr)
 245 {
 246         struct smatch_state *state;
 247         char *name;
 248
 249         name = expr_to_str(expr);
 250         if (!name)
 251                 return NULL;
 252
 253         state = get_state(my_id, name, NULL);
 254         free_string(name);
 255         return state;
 256 }
 257
 258 struct expression_list *get_conditions(struct expression *expr)
 259 {
 260         struct smatch_state *state;
 261
 262         state = get_state_expr(link_id, expr);
 263         if (!state)
 264                 return NULL;
 265         return state->data;
 266 }
 267
 268 void register_stored_conditions(int id)
 269 {
 270         my_id = id;
 271         set_dynamic_states(my_id);
 272 }
 273
 274 void register_stored_conditions_links(int id)
 275 {
 276         link_id = id;
 277         db_ignore_states(link_id);
 278         set_dynamic_states(link_id);
 279         add_merge_hook(link_id, &merge_links);
 280         add_modification_hook(link_id, &match_link_modify);
 281         add_untracked_param_hook(&match_untracked);
 282 }
 283
 284 #define RECURSE_LIMIT 50
 285
 286 static void filter_by_sm(struct sm_state *sm,
 287                        struct state_list **true_stack,
 288                        struct state_list **false_stack,
 289                        int *recurse_cnt)
 290 {
 291         if (!sm)
 292                 return;
 293
 294         if ((*recurse_cnt)++ > RECURSE_LIMIT)
 295                 return;
 296
 297         if (strcmp(sm->state->name, "true") == 0) {
 298                 add_ptr_list(true_stack, sm);
 299         } else if (strcmp(sm->state->name, "false") == 0) {
 300                 add_ptr_list(false_stack, sm);
 301         }
 302
 303         if (sm->merged) {
 304                 filter_by_sm(sm->left, true_stack, false_stack, recurse_cnt);
 305                 filter_by_sm(sm->right, true_stack, false_stack, recurse_cnt);
 306         }
 307 }
 308
 309 struct sm_state *stored_condition_implication_hook(struct expression *expr,
 310                                 struct state_list **true_stack,
 311                                 struct state_list **false_stack)
 312 {
 313         struct sm_state *sm;
 314         char *name;
 315         int recurse_cnt = 0;
 316         struct state_list *tmp_true = NULL;
 317         struct state_list *tmp_false = NULL;
 318         struct sm_state *tmp;
 319
 320         expr = strip_expr(expr);
 321
 322         name = expr_to_str(expr);
 323         if (!name)
 324                 return NULL;
 325
 326         sm = get_sm_state(my_id, name, NULL);
 327         free_string(name);
 328         if (!sm)
 329                 return NULL;
 330         if (!sm->merged)
 331                 return NULL;
 332
 333         filter_by_sm(sm, &tmp_true, &tmp_false, &recurse_cnt);
 334         if (!tmp_true && !tmp_false)
 335                 return NULL;
 336         if (recurse_cnt > RECURSE_LIMIT) {
 337                 sm = NULL;
 338                 goto free;
 339         }
 340
 341         FOR_EACH_PTR(tmp_true, tmp) {
 342                 add_ptr_list(true_stack, tmp);
 343         } END_FOR_EACH_PTR(tmp);
 344
 345         FOR_EACH_PTR(tmp_false, tmp) {
 346                 add_ptr_list(false_stack, tmp);
 347         } END_FOR_EACH_PTR(tmp);
 348
 349 free:
 350         free_slist(&tmp_true);
 351         free_slist(&tmp_false);
 352         return sm;
 353 }
 354