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 = 1;
  13  * if (bar)
  14  *         foo = 99;
  15  * else
  16  *         frob();
  17  *                   //  <-- point #1
  18  * if (foo == 99)    //  <-- point #2
  19  *         bar->baz; //  <-- point #3
  20  *
  21  *
  22  * At point #3 bar is non null and can be dereferenced.
  23  *
  24  * It's smatch_implied.c which sets bar to non null at point #2.
  25  *
  26  * At point #1 merge_slist() stores the list of states from both
  27  * the true and false paths.  On the true path foo == 99 and on
  28  * the false path foo == 1.  merge_slist() sets their my_pool
  29  * list to show the other states which were there when foo == 99.
  30  *
  31  * When it comes to the if (foo == 99) the smatch implied hook
  32  * looks for all the pools where foo was not 99.  It makes a list
  33  * of those.
  34  *
  35  * Then for bar (and all the other states) it says, ok bar is a
  36  * merged state that came from these previous states.  We'll
  37  * chop out all the states where it came from a pool where
  38  * foo != 99 and merge it all back together.
  39  *
  40  * That is the implied state of bar.
  41  *
  42  * merge_slist() sets up ->my_pool.  An sm_state only has one ->my_pool and
  43  *    that is the pool where it was first set.  Implied states sometimes have a
  44  *    my_pool to reflect that the code flowed through that path.
  45  * merge_sm_state() sets ->left and ->right.  (These are the states which were
  46  *    merged to form the current state.)
  47  * If an sm_state is not the same on both sides of a merge, it
  48  *    gets a ->my_pool set for both sides.  The result is a merged
  49  *    state that has it's ->left and ->right pointers set.  Merged states
  50  *    do not immediately have any my_pool set, but maybe will later
  51  *    when they themselves are merged.
  52  * A pool is a list of all the states that were set at the time.
  53  */
  54
  55 #include "smatch.h"
  56 #include "smatch_slist.h"
  57 #include "smatch_extra.h"
  58
  59 int debug_implied_states = 0;
  60 int option_no_implied = 0;
  61
  62 static int print_once = 0;
  63
  64 static int pool_in_pools(struct state_list *pool,
  65                         struct state_list_stack *pools)
  66 {
  67         struct state_list *tmp;
  68
  69         FOR_EACH_PTR(pools, tmp) {
  70                 if (tmp == pool)
  71                         return 1;
  72                 if (tmp > pool)
  73                         return 0;
  74         } END_FOR_EACH_PTR(tmp);
  75         return 0;
  76 }
  77
  78 struct sm_state *remove_my_pools(struct sm_state *sm,
  79                                 struct state_list_stack *pools, int *modified)
  80 {
  81         struct sm_state *ret = NULL;
  82         struct sm_state *left;
  83         struct sm_state *right;
  84         int removed = 0;
  85
  86         if (!sm)
  87                 return NULL;
  88
  89         if (sm->nr_children > 5000) {
  90                 if (!print_once++) {
  91                         smatch_msg("debug: remove_my_pools %s nr_children %d",
  92                                 sm->name, sm->nr_children);
  93                 }
  94                 return NULL;
  95         }
  96
  97         if (pool_in_pools(sm->my_pool, pools)) {
  98                 DIMPLIED("removed %s = %s from %d\n", sm->name,
  99                         show_state(sm->state), sm->line);
 100                 *modified = 1;
 101                 return NULL;
 102         }
 103
 104         if (!is_merged(sm)) {
 105                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state),
 106                         sm->line);
 107                 return sm;
 108         }
 109
 110         DIMPLIED("checking %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 111         left = remove_my_pools(sm->left, pools, &removed);
 112         right = remove_my_pools(sm->right, pools, &removed);
 113         if (!removed) {
 114                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 115                 return sm;
 116         }
 117         *modified = 1;
 118         if (!left && !right) {
 119                 DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 120                 return NULL;
 121         }
 122
 123         if (!left) {
 124                 ret = clone_state(right);
 125                 ret->merged = 1;
 126                 ret->right = right;
 127                 ret->left = NULL;
 128                 ret->my_pool = sm->my_pool;
 129         } else if (!right) {
 130                 ret = clone_state(left);
 131                 ret->merged = 1;
 132                 ret->left = left;
 133                 ret->right = NULL;
 134                 ret->my_pool = sm->my_pool;
 135         } else {
 136                 ret = merge_sm_states(left, right);
 137                 ret->my_pool = sm->my_pool;
 138         }
 139         ret->implied = 1;
 140         DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 141         return ret;
 142 }
 143
 144 static struct state_list *filter_stack(struct state_list *pre_list,
 145                                 struct state_list_stack *stack)
 146 {
 147         struct state_list *ret = NULL;
 148         struct sm_state *tmp;
 149         struct sm_state *filtered_state;
 150         int modified;
 151         int counter = 0;
 152
 153         if (!stack)
 154                 return NULL;
 155
 156         FOR_EACH_PTR(pre_list, tmp) {
 157                 modified = 0;
 158                 filtered_state = remove_my_pools(tmp, stack, &modified);
 159                 if (filtered_state && modified) {
 160                         add_ptr_list(&ret, filtered_state);
 161                         if ((counter++)%10 && out_of_memory())
 162                                 return NULL;
 163
 164                 }
 165         } END_FOR_EACH_PTR(tmp);
 166         return ret;
 167 }
 168
 169 static int is_checked(struct state_list *checked, struct sm_state *sm)
 170 {
 171         struct sm_state *tmp;
 172
 173         FOR_EACH_PTR(checked, tmp) {
 174                 if (tmp == sm)
 175                         return 1;
 176         } END_FOR_EACH_PTR(tmp);
 177         return 0;
 178 }
 179
 180 static void separate_pools(struct sm_state *sm_state, int comparison, int num,
 181                         int left,
 182                         struct state_list_stack **true_stack,
 183                         struct state_list_stack **false_stack,
 184                         struct state_list **checked)
 185 {
 186         struct sm_state *s;
 187         int istrue, isfalse;
 188         int free_checked = 0;
 189         struct state_list *checked_states = NULL;
 190
 191         if (!sm_state)
 192                 return;
 193
 194         /*
 195            Sometimes the implications are just too big to deal with
 196            so we bail.  Theoretically, implications only get rid of
 197            false positives and don't affect actual bugs.
 198         */
 199         if (sm_state->nr_children > 5000) {
 200                 if (!print_once) {
 201                         smatch_msg("debug: seperate_pools %s nr_children %d",
 202                                 sm_state->name, sm_state->nr_children);
 203                 }
 204                 return;
 205         }
 206
 207         if (checked == NULL) {
 208                 checked = &checked_states;
 209                 free_checked = 1;
 210         }
 211         if (is_checked(*checked, sm_state)) {
 212                 return;
 213         }
 214         add_ptr_list(checked, sm_state);
 215
 216         if (sm_state->my_pool) {
 217                 if (is_implied(sm_state)) {
 218                         s = get_sm_state_slist(sm_state->my_pool,
 219                                         sm_state->name, sm_state->owner,
 220                                         sm_state->sym);
 221                 } else {
 222                         s = sm_state;
 223                 }
 224
 225                 istrue = !possibly_false(comparison,
 226                                         (struct data_info *)s->state->data, num,
 227                                         left);
 228                 isfalse = !possibly_true(comparison,
 229                                         (struct data_info *)s->state->data,
 230                                         num, left);
 231
 232                 if (debug_implied_states || debug_states) {
 233                         if (istrue && isfalse) {
 234                                 printf("'%s = %s' from %d does not exist.\n",
 235                                         s->name, show_state(s->state),
 236                                         s->line);
 237                         } else if (istrue) {
 238                                 printf("'%s = %s' from %d is true.\n",
 239                                         s->name, show_state(s->state),
 240                                         s->line);
 241                         } else if (isfalse) {
 242                                 printf("'%s = %s' from %d is false.\n",
 243                                         s->name, show_state(s->state),
 244                                         s->line);
 245                         } else {
 246                                 printf("'%s = %s' from %d could be true or "
 247                                         "false.\n", s->name,
 248                                         show_state(s->state), s->line);
 249                         }
 250                 }
 251                 if (istrue) {
 252                         add_pool(true_stack, s->my_pool);
 253                 }
 254                 if (isfalse) {
 255                         add_pool(false_stack, s->my_pool);
 256                 }
 257         }
 258         separate_pools(sm_state->left, comparison, num, left, true_stack, false_stack, checked);
 259         separate_pools(sm_state->right, comparison, num, left, true_stack, false_stack, checked);
 260         if (free_checked)
 261                 free_slist(checked);
 262 }
 263
 264 static void get_eq_neq(struct sm_state *sm_state, int comparison, int num,
 265                 int left,
 266                 struct state_list *pre_list,
 267                 struct state_list **true_states,
 268                 struct state_list **false_states)
 269 {
 270         struct state_list_stack *true_stack = NULL;
 271         struct state_list_stack *false_stack = NULL;
 272
 273         if (debug_implied_states || debug_states) {
 274                 if (left)
 275                         smatch_msg("checking implications: (%s %s %d)",
 276                                 sm_state->name, show_special(comparison), num);
 277                 else
 278                         smatch_msg("checking implications: (%d %s %s)",
 279                                 num, show_special(comparison), sm_state->name);
 280         }
 281
 282         separate_pools(sm_state, comparison, num, left, &true_stack, &false_stack, NULL);
 283
 284         DIMPLIED("filtering true stack.\n");
 285         *true_states = filter_stack(pre_list, false_stack);
 286         DIMPLIED("filtering false stack.\n");
 287         *false_states = filter_stack(pre_list, true_stack);
 288         free_stack(&true_stack);
 289         free_stack(&false_stack);
 290         if (debug_implied_states || debug_states) {
 291                 printf("These are the implied states for the true path:\n");
 292                 __print_slist(*true_states);
 293                 printf("These are the implied states for the false path:\n");
 294                 __print_slist(*false_states);
 295         }
 296 }
 297
 298 static char *get_implication_variable(struct expression *expr, struct symbol **symp)
 299 {
 300         expr = strip_expr(expr);
 301         if (expr->type == EXPR_ASSIGNMENT)
 302                 return get_implication_variable(expr->left, symp);
 303         return get_variable_from_expr(expr, symp);
 304 }
 305
 306 static void handle_comparison(struct expression *expr,
 307                               struct state_list **implied_true,
 308                               struct state_list **implied_false)
 309 {
 310         struct symbol *sym;
 311         char *name;
 312         struct sm_state *state;
 313         int value;
 314         int left = 0;
 315
 316         value = get_value(expr->left);
 317         if (value == UNDEFINED) {
 318                 value = get_value(expr->right);
 319                 if (value == UNDEFINED)
 320                         return;
 321                 left = 1;
 322         }
 323         if (left)
 324                 name = get_implication_variable(expr->left, &sym);
 325         else
 326                 name = get_implication_variable(expr->right, &sym);
 327         if (!name || !sym)
 328                 goto free;
 329         state = get_sm_state(name, SMATCH_EXTRA, sym);
 330         if (!state)
 331                 goto free;
 332         if (!is_merged(state)) {
 333                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state->name);
 334                 goto free;
 335         }
 336         get_eq_neq(state, expr->op, value, left, __get_cur_slist(), implied_true, implied_false);
 337         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 338         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 339 free:
 340         free_string(name);
 341 }
 342
 343 static void get_tf_states(struct expression *expr,
 344                           struct state_list **implied_true,
 345                           struct state_list **implied_false)
 346 {
 347         struct symbol *sym;
 348         char *name;
 349         struct sm_state *state;
 350
 351         if (expr->type == EXPR_COMPARE) {
 352                 handle_comparison(expr, implied_true, implied_false);
 353                 return;
 354         }
 355         if (expr->type == EXPR_ASSIGNMENT) {
 356                 /* most of the time ->my_pools will be empty here because we
 357                    just set the state, but if have assigned a conditional
 358                    function there are implications. */
 359                 expr = expr->left;
 360         }
 361
 362         name = get_variable_from_expr(expr, &sym);
 363         if (!name || !sym)
 364                 goto free;
 365         state = get_sm_state(name, SMATCH_EXTRA, sym);
 366         if (!state)
 367                 goto free;
 368         if (!is_merged(state)) {
 369                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 370                 goto free;
 371         }
 372         get_eq_neq(state, SPECIAL_NOTEQUAL, 0, 1, __get_cur_slist(), implied_true, implied_false);
 373         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 374         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 375 free:
 376         free_string(name);
 377 }
 378
 379 static void implied_states_hook(struct expression *expr)
 380 {
 381         struct sm_state *state;
 382         struct state_list *implied_true = NULL;
 383         struct state_list *implied_false = NULL;
 384
 385         if (option_no_implied)
 386                 return;
 387
 388         get_tf_states(expr, &implied_true, &implied_false);
 389
 390         FOR_EACH_PTR(implied_true, state) {
 391                 __set_true_false_sm(state, NULL);
 392         } END_FOR_EACH_PTR(state);
 393         free_slist(&implied_true);
 394
 395         FOR_EACH_PTR(implied_false, state) {
 396                 __set_true_false_sm(NULL, state);
 397         } END_FOR_EACH_PTR(state);
 398         free_slist(&implied_false);
 399 }
 400
 401 void get_implications(char *name, struct symbol *sym, int comparison, int num,
 402                       struct state_list **true_states,
 403                       struct state_list **false_states)
 404 {
 405         struct sm_state *sm;
 406
 407         sm = get_sm_state(name, SMATCH_EXTRA, sym);
 408         if (!sm)
 409                 return;
 410         if (slist_has_state(sm->possible, &undefined))
 411                 return;
 412         get_eq_neq(sm, comparison, num, 1, __get_cur_slist(), true_states, false_states);
 413 }
 414
 415 struct state_list *__implied_case_slist(struct expression *switch_expr,
 416                                         struct expression *case_expr,
 417                                         struct state_list **raw_slist)
 418 {
 419         char *name = NULL;
 420         struct symbol *sym;
 421         struct sm_state *sm;
 422         struct sm_state *true_sm;
 423         struct sm_state *false_sm;
 424         struct state_list *true_states = NULL;
 425         struct state_list *false_states = NULL;
 426         struct state_list *ret = clone_slist(*raw_slist);
 427         long long val;
 428
 429         if (!case_expr)
 430                 return ret;
 431         name = get_variable_from_expr(switch_expr, &sym);
 432         if (!name || !sym)
 433                 goto free;
 434         sm = get_sm_state_slist(*raw_slist, name, SMATCH_EXTRA, sym);
 435         val = get_value(case_expr);
 436         if (val == UNDEFINED)
 437                 goto free;
 438         if (sm) {
 439                 get_eq_neq(sm, SPECIAL_EQUAL, val, 1, *raw_slist, &true_states, &false_states);
 440         }
 441
 442         true_sm = get_sm_state_slist(true_states, name, SMATCH_EXTRA, sym);
 443         if (!true_sm)
 444                 set_state_slist(&true_states, name, SMATCH_EXTRA, sym, alloc_extra_state(val));
 445         false_sm = get_sm_state_slist(false_states, name, SMATCH_EXTRA, sym);
 446         if (!false_sm)
 447                 set_state_slist(&false_states, name, SMATCH_EXTRA, sym, add_filter(sm?sm->state:NULL, val));
 448         overwrite_slist(false_states, raw_slist);
 449         overwrite_slist(true_states, &ret);
 450         free_slist(&true_states);
 451         free_slist(&false_states);
 452 free:
 453         free_string(name);
 454         return ret;
 455 }
 456
 457 static void clear_print_once(struct symbol *sym)
 458 {
 459         print_once = 0;
 460 }
 461
 462 void __extra_match_condition(struct expression *expr);
 463 void register_implications(int id)
 464 {
 465         add_hook(&implied_states_hook, CONDITION_HOOK);
 466         add_hook(&__extra_match_condition, CONDITION_HOOK);
 467         add_hook(&clear_print_once, END_FUNC_HOOK);
 468 }