smatch_implied.c

   1 /*
   2  * sparse/smatch_implied.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  *  Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * Imagine we have this code:
  12  * foo = 0;
  13  * if (bar)
  14  *         foo = 1;
  15  *                   //  <-- point #1
  16  * else
  17  *         frob();
  18  *                   //  <-- point #2
  19  * if (foo == 1)     //  <-- point #3
  20  *         bar->baz; //  <-- point #4
  21  *
  22  * Currently (Oct 2008) in smatch when we merge bar states
  23  * null and nonnull, at point #2, the state becomes undefined.
  24  * As a result we get an error at point #3.
  25  *
  26  * The idea behind "implied state pools" is to fix that.
  27  *
  28  * The implied pools get created in merge_slist().  Whatever
  29  * is unique to one slist being merged gets put into a pool.
  30  *
  31  * If we set a state that removes it from all pools.
  32  *
  33  * When we come to an if statement where "foo" has some pools
  34  * associated we take all the pools where "foo == 1" and keep
  35  * all the states that are consistent across those pools.
  36  *
  37  * The point of doing this is to turn an undefined state into
  38  * a defined state.  This hopefully gets rid of some false positives.
  39  * What it doesn't do is find new errors that were
  40  * missed before.
  41  *
  42  * There are quite a few implementation details I haven't figured
  43  * out.  How do you create implied state pools inside a
  44  * complex condition?  How do you determine what is implied
  45  * from a complex condition?  The initial patch is extremely rudimentary...
  46  */
  47
  48 #include "smatch.h"
  49 #include "smatch_slist.h"
  50
  51 #define EQUALS 0
  52 #define NOTEQUALS 1
  53
  54 int debug_implied_states = 0;
  55 int option_no_implied = 0;
  56
  57 /*
  58  * We want to find which states have been modified inside a branch.
  59  * If you have 2 &merged states they could be different states really
  60  * and maybe one or both were modified.  We say it is unchanged if
  61  * the ->state pointers are the same and they belong to the same pools.
  62  * If they have been modified on both sides of a branch to the same thing,
  63  * it's still OK to say they are the same, because that means they won't
  64  * belong to any pools.
  65  */
  66 static int is_really_same(struct sm_state *one, struct sm_state *two)
  67 {
  68         struct state_list *tmp1;
  69         struct state_list *tmp2;
  70
  71         if (one->state != two->state)
  72                 return 0;
  73
  74         PREPARE_PTR_LIST(one->my_pools, tmp1);
  75         PREPARE_PTR_LIST(two->my_pools, tmp2);
  76         for (;;) {
  77                 if (!tmp1 && !tmp2)
  78                         return 1;
  79                 if (tmp1 < tmp2) {
  80                         return 0;
  81                 } else if (tmp1 == tmp2) {
  82                         NEXT_PTR_LIST(tmp1);
  83                         NEXT_PTR_LIST(tmp2);
  84                 } else {
  85                         return 0;
  86                 }
  87         }
  88         FINISH_PTR_LIST(tmp2);
  89         FINISH_PTR_LIST(tmp1);
  90         return 1;
  91 }
  92
  93 static int pool_in_pools(struct state_list_stack *pools,
  94                         struct state_list *pool)
  95 {
  96         struct state_list *tmp;
  97
  98         FOR_EACH_PTR(pools, tmp) {
  99                 if (tmp == pool)
 100                         return 1;
 101         } END_FOR_EACH_PTR(tmp);
 102         return 0;
 103 }
 104
 105 static struct state_list *clone_states_in_pool(struct state_list *pool,
 106                                                struct state_list *cur_slist)
 107 {
 108         struct sm_state *state;
 109         struct sm_state *cur_state;
 110         struct sm_state *tmp;
 111         struct state_list *to_slist = NULL;
 112
 113         FOR_EACH_PTR(pool, state) {
 114                 cur_state = get_sm_state_slist(cur_slist, state->name,
 115                                         state->owner, state->sym);
 116                 if (!cur_state)
 117                         continue;
 118                 if (is_really_same(state, cur_state))
 119                         continue;
 120                 if (pool_in_pools(cur_state->all_pools, pool)) {
 121                         tmp = clone_state(state);
 122                         add_ptr_list(&to_slist, tmp);
 123                 }
 124         } END_FOR_EACH_PTR(state);
 125         return to_slist;
 126 }
 127
 128 /*
 129  * merge_implied() takes an implied state and another possibly implied state
 130  * from another pool.  It checks that the second pool is reachable from
 131  * cur_slist then merges the two states and returns the result.
 132  */
 133 static struct sm_state *merge_implied(struct sm_state *one,
 134                                       struct sm_state *two,
 135                                       struct state_list *pool,
 136                                       struct state_list *cur_slist)
 137 {
 138         struct sm_state *cur_state;
 139
 140         cur_state = get_sm_state_slist(cur_slist, two->name, two->owner,
 141                                 two->sym);
 142         if (!cur_state)
 143                 return NULL;  /* this can't actually happen */
 144         if (!pool_in_pools(cur_state->all_pools, pool))
 145                 return NULL;
 146         return merge_sm_states(one, two);
 147 }
 148
 149 /*
 150  * filter() is used to find what states are the same across
 151  * a series of slists.
 152  * It takes a **slist and a *filter.
 153  * It removes everything from **slist that isn't in *filter.
 154  * The reason you would want to do this is if you want to
 155  * know what other states are true if one state is true.  (smatch_implied).
 156  */
 157 static void filter(struct state_list **slist, struct state_list *filter,
 158                    struct state_list *cur_slist)
 159 {
 160         struct sm_state *s_one, *s_two;
 161         struct state_list *results = NULL;
 162         struct sm_state *tmp;
 163
 164         PREPARE_PTR_LIST(*slist, s_one);
 165         PREPARE_PTR_LIST(filter, s_two);
 166         for (;;) {
 167                 if (!s_one || !s_two)
 168                         break;
 169                 if (cmp_tracker(s_one, s_two) < 0) {
 170                         DIMPLIED("removed %s\n", s_one->name);
 171                         NEXT_PTR_LIST(s_one);
 172                 } else if (cmp_tracker(s_one, s_two) == 0) {
 173                         tmp = merge_implied(s_one, s_two, filter, cur_slist);
 174                         if (tmp)
 175                                 add_ptr_list(&results, tmp);
 176                         else
 177                                 DIMPLIED("removed %s\n", s_one->name);
 178                         NEXT_PTR_LIST(s_one);
 179                         NEXT_PTR_LIST(s_two);
 180                 } else {
 181                         NEXT_PTR_LIST(s_two);
 182                 }
 183         }
 184         FINISH_PTR_LIST(s_two);
 185         FINISH_PTR_LIST(s_one);
 186
 187         free_slist(slist);
 188         *slist = results;
 189 }
 190
 191 static struct state_list *filter_stack(struct state_list_stack *stack)
 192 {
 193         struct state_list *tmp;
 194         struct state_list *ret = NULL;
 195         int i = 0;
 196
 197         FOR_EACH_PTR(stack, tmp) {
 198                 if (!i++) {
 199                         ret = clone_states_in_pool(tmp, __get_cur_slist());
 200                         if (debug_implied_states) {
 201                                 printf("The first implied pool is:\n");
 202                                 __print_slist(ret);
 203                         }
 204                 } else {
 205                         filter(&ret, tmp, __get_cur_slist());
 206                         DIMPLIED("filtered\n");
 207                 }
 208         } END_FOR_EACH_PTR(tmp);
 209         return ret;
 210 }
 211
 212 static int is_true(int comparison, int num, int var, int left)
 213 {
 214         if (left)
 215                 return true_comparison(var, comparison, num);
 216         else
 217                 return true_comparison(num,  comparison, var);
 218 }
 219
 220 static void get_eq_neq(struct sm_state *sm_state, int comparison, int num,
 221                        int left, struct state_list **true_states,
 222                        struct state_list **false_states)
 223 {
 224         struct state_list *list;
 225         struct sm_state *s;
 226         struct state_list_stack *true_stack = NULL;
 227         struct state_list_stack *false_stack = NULL;
 228
 229         if (left)
 230                 DIMPLIED("%d checking implications: (%s %s %d)\n", get_lineno(),
 231                          sm_state->name, show_special(comparison), num);
 232         else
 233                 DIMPLIED("%d checking implications: (%d %s %s)\n", get_lineno(),
 234                          num, show_special(comparison), sm_state->name);
 235
 236         FOR_EACH_PTR(sm_state->my_pools, list) {
 237                 s = get_sm_state_slist(list, sm_state->name, sm_state->owner,
 238                                     sm_state->sym);
 239                 if (s->state == &undefined || s->state == &merged) {
 240                         DIMPLIED("'%s' from %d is %s.\n", s->name, s->line,
 241                                  show_state(s->state));
 242                         push_slist(&false_stack, list);
 243                         push_slist(&true_stack, list);
 244                         continue;
 245                 }
 246                 if (is_true(comparison, num, *(int *)s->state->data, left)) {
 247                         DIMPLIED("'%s' from %d is true.\n", s->name, s->line);
 248                         push_slist(&true_stack, list);
 249                 } else {
 250                         DIMPLIED("'%s' from %d is false.\n", s->name, s->line);
 251                         push_slist(&false_stack, list);
 252                 }
 253         } END_FOR_EACH_PTR(list);
 254         DIMPLIED("filtering true stack.\n");
 255         *true_states = filter_stack(true_stack);
 256         DIMPLIED("filtering false stack.\n");
 257         *false_states = filter_stack(false_stack);
 258         free_stack(&true_stack);
 259         free_stack(&false_stack);
 260         if (debug_implied_states || debug_states) {
 261                 printf("These are the implied states for the true path:\n");
 262                 __print_slist(*true_states);
 263                 printf("These are the implied states for the false path:\n");
 264                 __print_slist(*false_states);
 265         }
 266 }
 267
 268 static void handle_comparison(struct expression *expr,
 269                               struct state_list **implied_true,
 270                               struct state_list **implied_false)
 271 {
 272         struct symbol *sym;
 273         char *name;
 274         struct sm_state *state;
 275         int value;
 276         int left = 0;
 277
 278         value = get_value(expr->left);
 279         if (value == UNDEFINED) {
 280                 value = get_value(expr->right);
 281                 if (value == UNDEFINED)
 282                         return;
 283                 left = 1;
 284         }
 285         if (left)
 286                 name = get_variable_from_expr(expr->left, &sym);
 287         else
 288                 name = get_variable_from_expr(expr->right, &sym);
 289         if (!name || !sym) {
 290                 free_string(name);
 291                 return;
 292         }
 293         state = get_sm_state(name, SMATCH_EXTRA, sym);
 294         free_string(name);
 295         if (!state)
 296                 return;
 297         if (!state->my_pools) {
 298                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 299                 return;
 300         }
 301         get_eq_neq(state, expr->op, value, left, implied_true, implied_false);
 302 }
 303
 304 static void get_tf_states(struct expression *expr,
 305                           struct state_list **implied_true,
 306                           struct state_list **implied_false)
 307 {
 308         struct symbol *sym;
 309         char *name;
 310         struct sm_state *state;
 311
 312         if (expr->type == EXPR_COMPARE) {
 313                 handle_comparison(expr, implied_true, implied_false);
 314                 return;
 315         }
 316
 317         name = get_variable_from_expr(expr, &sym);
 318         if (!name || !sym) {
 319                 free_string(name);
 320                 return;
 321         }
 322         state = get_sm_state(name, SMATCH_EXTRA, sym);
 323         free_string(name);
 324         if (!state)
 325                 return;
 326         if (!state->my_pools) {
 327                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 328                 return;
 329         }
 330         get_eq_neq(state, SPECIAL_NOTEQUAL, 0, 1, implied_true, implied_false);
 331 }
 332
 333 static void implied_states_hook(struct expression *expr)
 334 {
 335         struct sm_state *state;
 336         struct state_list *implied_true = NULL;
 337         struct state_list *implied_false = NULL;
 338
 339         if (option_no_implied)
 340                 return;
 341
 342         get_tf_states(expr, &implied_true, &implied_false);
 343
 344         FOR_EACH_PTR(implied_true, state) {
 345                 __set_true_false_sm(state, NULL);
 346         } END_FOR_EACH_PTR(state);
 347         free_slist(&implied_true);
 348
 349         FOR_EACH_PTR(implied_false, state) {
 350                 __set_true_false_sm(NULL, state);
 351         } END_FOR_EACH_PTR(state);
 352         free_slist(&implied_false);
 353 }
 354
 355 void get_implications(char *name, struct symbol *sym, int comparison, int num,
 356                       struct state_list **true_states,
 357                       struct state_list **false_states)
 358 {
 359         struct sm_state *sm;
 360
 361         sm = get_sm_state(name, SMATCH_EXTRA, sym);
 362         if (!sm)
 363                 return;
 364         if (slist_has_state(sm->possible, &undefined))
 365                 return;
 366         get_eq_neq(sm, comparison, num, 1, true_states, false_states);
 367 }
 368
 369 void register_implications(int id)
 370 {
 371         add_hook(&implied_states_hook, CONDITION_HOOK);
 372 }