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 #define DIMPLIED(msg...) do { if (debug_implied_states) printf(msg); } while (0)
  60
  61 int debug_implied_states = 0;
  62 int option_no_implied = 0;
  63
  64 static int print_once = 0;
  65
  66 static struct range_list *my_list = NULL;
  67 static struct data_range *my_range;
  68
  69 static struct range_list *tmp_range_list(long num)
  70 {
  71         __free_ptr_list((struct ptr_list **)&my_list);
  72         my_range = alloc_range(num, num);
  73         my_range->min = num;
  74         my_range->max = num;
  75         add_ptr_list(&my_list, my_range);
  76         return my_list;
  77 }
  78
  79 static int pool_in_pools(struct state_list *pool,
  80                         struct state_list_stack *pools)
  81 {
  82         struct state_list *tmp;
  83
  84         FOR_EACH_PTR(pools, tmp) {
  85                 if (tmp == pool)
  86                         return 1;
  87                 if (tmp > pool)
  88                         return 0;
  89         } END_FOR_EACH_PTR(tmp);
  90         return 0;
  91 }
  92
  93 struct sm_state *remove_my_pools(struct sm_state *sm,
  94                                 struct state_list_stack *pools, int *modified)
  95 {
  96         struct sm_state *ret = NULL;
  97         struct sm_state *left;
  98         struct sm_state *right;
  99         int removed = 0;
 100
 101         if (!sm)
 102                 return NULL;
 103
 104         if (sm->nr_children > 5000) {
 105                 if (!print_once++) {
 106                         sm_msg("debug: remove_my_pools %s nr_children %d",
 107                                 sm->name, sm->nr_children);
 108                 }
 109                 return NULL;
 110         }
 111
 112         if (pool_in_pools(sm->my_pool, pools)) {
 113                 DIMPLIED("removed %s = %s from %d\n", sm->name,
 114                         show_state(sm->state), sm->line);
 115                 *modified = 1;
 116                 return NULL;
 117         }
 118
 119         if (!is_merged(sm)) {
 120                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state),
 121                         sm->line);
 122                 return sm;
 123         }
 124
 125         DIMPLIED("checking %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 126         left = remove_my_pools(sm->left, pools, &removed);
 127         right = remove_my_pools(sm->right, pools, &removed);
 128         if (!removed) {
 129                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 130                 return sm;
 131         }
 132         *modified = 1;
 133         if (!left && !right) {
 134                 DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 135                 return NULL;
 136         }
 137
 138         if (!left) {
 139                 ret = clone_state(right);
 140                 ret->merged = 1;
 141                 ret->right = right;
 142                 ret->left = NULL;
 143                 ret->my_pool = sm->my_pool;
 144         } else if (!right) {
 145                 ret = clone_state(left);
 146                 ret->merged = 1;
 147                 ret->left = left;
 148                 ret->right = NULL;
 149                 ret->my_pool = sm->my_pool;
 150         } else {
 151                 ret = merge_sm_states(left, right);
 152                 ret->my_pool = sm->my_pool;
 153         }
 154         ret->implied = 1;
 155         DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 156         return ret;
 157 }
 158
 159 static struct state_list *filter_stack(struct state_list *pre_list,
 160                                 struct state_list_stack *stack)
 161 {
 162         struct state_list *ret = NULL;
 163         struct sm_state *tmp;
 164         struct sm_state *filtered_state;
 165         int modified;
 166         int counter = 0;
 167
 168         if (!stack)
 169                 return NULL;
 170
 171         FOR_EACH_PTR(pre_list, tmp) {
 172                 modified = 0;
 173                 filtered_state = remove_my_pools(tmp, stack, &modified);
 174                 if (filtered_state && modified) {
 175                         add_ptr_list(&ret, filtered_state);
 176                         if ((counter++)%10 && out_of_memory())
 177                                 return NULL;
 178
 179                 }
 180         } END_FOR_EACH_PTR(tmp);
 181         return ret;
 182 }
 183
 184 static int is_checked(struct state_list *checked, struct sm_state *sm)
 185 {
 186         struct sm_state *tmp;
 187
 188         FOR_EACH_PTR(checked, tmp) {
 189                 if (tmp == sm)
 190                         return 1;
 191         } END_FOR_EACH_PTR(tmp);
 192         return 0;
 193 }
 194
 195 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list *vals,
 196                         int left,
 197                         struct state_list_stack **true_stack,
 198                         struct state_list_stack **false_stack,
 199                         struct state_list **checked)
 200 {
 201         struct sm_state *s;
 202         int istrue, isfalse;
 203         int free_checked = 0;
 204         struct state_list *checked_states = NULL;
 205
 206         if (!sm_state)
 207                 return;
 208
 209         /*
 210            Sometimes the implications are just too big to deal with
 211            so we bail.  Theoretically, implications only get rid of
 212            false positives and don't affect actual bugs.
 213         */
 214         if (sm_state->nr_children > 5000) {
 215                 if (!print_once++) {
 216                         sm_msg("debug: seperate_pools %s nr_children %d",
 217                                 sm_state->name, sm_state->nr_children);
 218                 }
 219                 return;
 220         }
 221
 222         if (checked == NULL) {
 223                 checked = &checked_states;
 224                 free_checked = 1;
 225         }
 226         if (is_checked(*checked, sm_state)) {
 227                 return;
 228         }
 229         add_ptr_list(checked, sm_state);
 230
 231         if (sm_state->my_pool) {
 232                 if (is_implied(sm_state)) {
 233                         s = get_sm_state_slist(sm_state->my_pool,
 234                                         sm_state->owner, sm_state->name,
 235                                         sm_state->sym);
 236                 } else {
 237                         s = sm_state;
 238                 }
 239
 240                 istrue = !possibly_false_range_list(comparison,
 241                                                 (struct data_info *)s->state->data,
 242                                                 vals, left);
 243                 isfalse = !possibly_true_range_list(comparison,
 244                                                 (struct data_info *)s->state->data,
 245                                                 vals, left);
 246
 247                 if (debug_implied_states || debug_states) {
 248                         if (istrue && isfalse) {
 249                                 printf("'%s = %s' from %d does not exist.\n",
 250                                         s->name, show_state(s->state),
 251                                         s->line);
 252                         } else if (istrue) {
 253                                 printf("'%s = %s' from %d is true.\n",
 254                                         s->name, show_state(s->state),
 255                                         s->line);
 256                         } else if (isfalse) {
 257                                 printf("'%s = %s' from %d is false.\n",
 258                                         s->name, show_state(s->state),
 259                                         s->line);
 260                         } else {
 261                                 printf("'%s = %s' from %d could be true or "
 262                                         "false.\n", s->name,
 263                                         show_state(s->state), s->line);
 264                         }
 265                 }
 266                 if (istrue) {
 267                         add_pool(true_stack, s->my_pool);
 268                 }
 269                 if (isfalse) {
 270                         add_pool(false_stack, s->my_pool);
 271                 }
 272         }
 273         separate_pools(sm_state->left, comparison, vals, left, true_stack, false_stack, checked);
 274         separate_pools(sm_state->right, comparison, vals, left, true_stack, false_stack, checked);
 275         if (free_checked)
 276                 free_slist(checked);
 277 }
 278
 279 static void get_eq_neq(struct sm_state *sm_state, int comparison, struct range_list *vals,
 280                 int left,
 281                 struct state_list *pre_list,
 282                 struct state_list **true_states,
 283                 struct state_list **false_states)
 284 {
 285         struct state_list_stack *true_stack = NULL;
 286         struct state_list_stack *false_stack = NULL;
 287
 288         if (debug_implied_states || debug_states) {
 289                 if (left)
 290                         sm_msg("checking implications: (%s %s %s)",
 291                                 sm_state->name, show_special(comparison), show_ranges(vals));
 292                 else
 293                         sm_msg("checking implications: (%s %s %s)",
 294                                 show_ranges(vals), show_special(comparison), sm_state->name);
 295         }
 296
 297         separate_pools(sm_state, comparison, vals, left, &true_stack, &false_stack, NULL);
 298
 299         DIMPLIED("filtering true stack.\n");
 300         *true_states = filter_stack(pre_list, false_stack);
 301         DIMPLIED("filtering false stack.\n");
 302         *false_states = filter_stack(pre_list, true_stack);
 303         free_stack(&true_stack);
 304         free_stack(&false_stack);
 305         if (debug_implied_states || debug_states) {
 306                 printf("These are the implied states for the true path:\n");
 307                 __print_slist(*true_states);
 308                 printf("These are the implied states for the false path:\n");
 309                 __print_slist(*false_states);
 310         }
 311 }
 312
 313 static char *get_implication_variable(struct expression *expr, struct symbol **symp)
 314 {
 315         expr = strip_expr(expr);
 316         if (expr->type == EXPR_ASSIGNMENT)
 317                 return get_implication_variable(expr->left, symp);
 318         return get_variable_from_expr(expr, symp);
 319 }
 320
 321 static void handle_comparison(struct expression *expr,
 322                               struct state_list **implied_true,
 323                               struct state_list **implied_false)
 324 {
 325         struct symbol *sym;
 326         char *name;
 327         struct sm_state *state;
 328         long long value;
 329         int left = 0;
 330
 331         if (!get_value(expr->left, &value)) {
 332                 if (!get_value(expr->right, &value))
 333                         return;
 334                 left = 1;
 335         }
 336         if (left)
 337                 name = get_implication_variable(expr->left, &sym);
 338         else
 339                 name = get_implication_variable(expr->right, &sym);
 340         if (!name || !sym)
 341                 goto free;
 342         state = get_sm_state(SMATCH_EXTRA, name, sym);
 343         if (!state)
 344                 goto free;
 345         if (!is_merged(state)) {
 346                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state->name);
 347                 goto free;
 348         }
 349         get_eq_neq(state, expr->op, tmp_range_list(value), left, __get_cur_slist(), implied_true, implied_false);
 350         delete_state_slist(implied_true, SMATCH_EXTRA, name, sym);
 351         delete_state_slist(implied_false, SMATCH_EXTRA, name, sym);
 352 free:
 353         free_string(name);
 354 }
 355
 356 static void get_tf_states(struct expression *expr,
 357                           struct state_list **implied_true,
 358                           struct state_list **implied_false)
 359 {
 360         struct symbol *sym;
 361         char *name;
 362         struct sm_state *state;
 363
 364         if (expr->type == EXPR_COMPARE) {
 365                 handle_comparison(expr, implied_true, implied_false);
 366                 return;
 367         }
 368         if (expr->type == EXPR_ASSIGNMENT) {
 369                 /* most of the time ->my_pools will be empty here because we
 370                    just set the state, but if have assigned a conditional
 371                    function there are implications. */
 372                 expr = expr->left;
 373         }
 374
 375         name = get_variable_from_expr(expr, &sym);
 376         if (!name || !sym)
 377                 goto free;
 378         state = get_sm_state(SMATCH_EXTRA, name, sym);
 379         if (!state)
 380                 goto free;
 381         if (!is_merged(state)) {
 382                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 383                 goto free;
 384         }
 385         get_eq_neq(state, SPECIAL_NOTEQUAL, tmp_range_list(0), 1, __get_cur_slist(), implied_true, implied_false);
 386         delete_state_slist(implied_true, SMATCH_EXTRA, name, sym);
 387         delete_state_slist(implied_false, SMATCH_EXTRA, name, sym);
 388 free:
 389         free_string(name);
 390 }
 391
 392 static void implied_states_hook(struct expression *expr)
 393 {
 394         struct sm_state *state;
 395         struct state_list *implied_true = NULL;
 396         struct state_list *implied_false = NULL;
 397
 398         if (option_no_implied)
 399                 return;
 400
 401         get_tf_states(expr, &implied_true, &implied_false);
 402
 403         FOR_EACH_PTR(implied_true, state) {
 404                 __set_true_false_sm(state, NULL);
 405         } END_FOR_EACH_PTR(state);
 406         free_slist(&implied_true);
 407
 408         FOR_EACH_PTR(implied_false, state) {
 409                 __set_true_false_sm(NULL, state);
 410         } END_FOR_EACH_PTR(state);
 411         free_slist(&implied_false);
 412 }
 413
 414 struct range_list *__get_implied_values(struct expression *switch_expr)
 415 {
 416         char *name;
 417         struct symbol *sym;
 418         struct smatch_state *state;
 419         struct range_list *ret = NULL;
 420
 421         name = get_variable_from_expr(switch_expr, &sym);
 422         if (!name || !sym)
 423                 goto free;
 424         state = get_state(SMATCH_EXTRA, name, sym);
 425         if (!state)
 426                 goto free;
 427         ret = clone_range_list(((struct data_info *)state->data)->value_ranges);
 428 free:
 429         free_string(name);
 430         if (!ret)
 431                 add_range(&ret, whole_range.min, whole_range.max);
 432         return ret;
 433 }
 434
 435 void get_implications(char *name, struct symbol *sym, int comparison, int num,
 436                       struct state_list **true_states,
 437                       struct state_list **false_states)
 438 {
 439         struct sm_state *sm;
 440
 441         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 442         if (!sm)
 443                 return;
 444         if (slist_has_state(sm->possible, &undefined))
 445                 return;
 446         get_eq_neq(sm, comparison, tmp_range_list(num), 1, __get_cur_slist(), true_states, false_states);
 447 }
 448
 449 struct state_list *__implied_case_slist(struct expression *switch_expr,
 450                                         struct expression *case_expr,
 451                                         struct range_list_stack **remaining_cases,
 452                                         struct state_list **raw_slist)
 453 {
 454         char *name = NULL;
 455         struct symbol *sym;
 456         struct sm_state *sm;
 457         struct sm_state *true_sm;
 458         struct state_list *true_states = NULL;
 459         struct state_list *false_states = NULL;
 460         struct state_list *ret = clone_slist(*raw_slist);
 461         long long val;
 462         struct data_range *range;
 463         struct range_list *vals = NULL;
 464
 465         name = get_variable_from_expr(switch_expr, &sym);
 466         if (!name || !sym)
 467                 goto free;
 468         sm = get_sm_state_slist(*raw_slist, SMATCH_EXTRA, name, sym);
 469         if (!case_expr) {
 470                 vals = top_range_list(*remaining_cases);
 471         } else {
 472                 if (!get_value(case_expr, &val)) {
 473                         goto free;
 474                 } else {
 475                         filter_top_range_list(remaining_cases, val);
 476                         range = alloc_range(val, val);
 477                         add_ptr_list(&vals, range);
 478                 }
 479         }
 480         if (sm) {
 481                 get_eq_neq(sm, SPECIAL_EQUAL, vals, 1, *raw_slist, &true_states, &false_states);
 482         }
 483
 484         true_sm = get_sm_state_slist(true_states, SMATCH_EXTRA, name, sym);
 485         if (!true_sm)
 486                 set_state_slist(&true_states, SMATCH_EXTRA, name, sym, alloc_extra_state_range_list(vals));
 487         overwrite_slist(true_states, &ret);
 488         free_slist(&true_states);
 489         free_slist(&false_states);
 490 free:
 491         free_string(name);
 492         return ret;
 493 }
 494
 495 static void match_end_func(struct symbol *sym)
 496 {
 497         print_once = 0;
 498 }
 499
 500 void __extra_match_condition(struct expression *expr);
 501 void register_implications(int id)
 502 {
 503         add_hook(&implied_states_hook, CONDITION_HOOK);
 504         add_hook(&__extra_match_condition, CONDITION_HOOK);
 505         add_hook(&match_end_func, END_FUNC_HOOK);
 506 }