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.  The my pool gets set when
  44  *    code paths merge.  States that have been set since the last merge do
  45  *    not have a ->my_pool.
  46  * merge_sm_state() sets ->left and ->right.  (These are the states which were
  47  *    merged to form the current state.)
  48  * a pool:  a pool is an slist that has been merged with another slist.
  49  */
  50
  51 #include <sys/time.h>
  52 #include <time.h>
  53 #include "smatch.h"
  54 #include "smatch_slist.h"
  55 #include "smatch_extra.h"
  56
  57 char *implied_debug_msg;
  58 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
  59
  60 int option_debug_implied = 0;
  61 int option_no_implied = 0;
  62
  63 #define RIGHT 0
  64 #define LEFT  1
  65
  66 /*
  67  * tmp_range_list():
  68  * It messes things up to free range list allocations.  This helper fuction
  69  * lets us reuse memory instead of doing new allocations.
  70  */
  71 static struct range_list *tmp_range_list(long long num)
  72 {
  73         static struct range_list *my_list = NULL;
  74         static struct data_range *my_range;
  75
  76         __free_ptr_list((struct ptr_list **)&my_list);
  77         my_range = alloc_range(num, num);
  78         my_range->min = num;
  79         my_range->max = num;
  80         add_ptr_list(&my_list, my_range);
  81         return my_list;
  82 }
  83
  84 /*
  85  * If 'foo' == 99 add it that pool to the true pools.  If it's false, add it to
  86  * the false pools.  If we're not sure, then we don't add it to either.
  87  */
  88 static void do_compare(struct sm_state *sm_state, int comparison, struct range_list *vals,
  89                         int lr,
  90                         struct state_list_stack **true_stack,
  91                         struct state_list_stack **false_stack)
  92 {
  93         struct sm_state *s;
  94         int istrue;
  95         int isfalse;
  96
  97         if (!sm_state->my_pool)
  98                 return;
  99
 100         if (is_implied(sm_state)) {
 101                 s = get_sm_state_slist(sm_state->my_pool,
 102                                 sm_state->owner, sm_state->name,
 103                                 sm_state->sym);
 104         } else {
 105                 s = sm_state;
 106         }
 107
 108         if (!s) {
 109                 if (option_debug_implied || option_debug)
 110                         sm_msg("%s from %d, has borrowed implications.",
 111                                 sm_state->name, sm_state->line);
 112                 return;
 113         }
 114
 115         istrue = !possibly_false_range_list_lr(comparison,      get_dinfo(s->state), vals, lr);
 116         isfalse = !possibly_true_range_list_lr(comparison, get_dinfo(s->state), vals, lr);
 117
 118         if (option_debug_implied || option_debug) {
 119                 if (istrue && isfalse) {
 120                         printf("'%s = %s' from %d does not exist.\n", s->name,
 121                                 show_state(s->state), s->line);
 122                 } else if (istrue) {
 123                         printf("'%s = %s' from %d is true.\n", s->name, show_state(s->state),
 124                                 s->line);
 125                 } else if (isfalse) {
 126                         printf("'%s = %s' from %d is false.\n", s->name, show_state(s->state),
 127                                 s->line);
 128                 } else {
 129                         printf("'%s = %s' from %d could be true or false.\n", s->name,
 130                                 show_state(s->state), s->line);
 131                 }
 132         }
 133         if (istrue)
 134                 add_pool(true_stack, s->my_pool);
 135
 136         if (isfalse)
 137                 add_pool(false_stack, s->my_pool);
 138 }
 139
 140 static int pool_in_pools(struct state_list *pool,
 141                         struct state_list_stack *pools)
 142 {
 143         struct state_list *tmp;
 144
 145         FOR_EACH_PTR(pools, tmp) {
 146                 if (tmp == pool)
 147                         return 1;
 148                 if (tmp > pool)
 149                         return 0;
 150         } END_FOR_EACH_PTR(tmp);
 151         return 0;
 152 }
 153
 154 static int is_checked(struct state_list *checked, struct sm_state *sm)
 155 {
 156         struct sm_state *tmp;
 157
 158         FOR_EACH_PTR(checked, tmp) {
 159                 if (tmp == sm)
 160                         return 1;
 161         } END_FOR_EACH_PTR(tmp);
 162         return 0;
 163 }
 164
 165 /*
 166  * separate_pools():
 167  * Example code:  if (foo == 99) {
 168  *
 169  * Say 'foo' is a merged state that has many possible values.  It is the combination
 170  * of merges.  separate_pools() iterates through the pools recursively and calls
 171  * do_compare() for each time 'foo' was set.
 172  */
 173 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list *vals,
 174                         int lr,
 175                         struct state_list_stack **true_stack,
 176                         struct state_list_stack **false_stack,
 177                         struct state_list **checked)
 178 {
 179         int free_checked = 0;
 180         struct state_list *checked_states = NULL;
 181
 182         if (!sm_state)
 183                 return;
 184
 185         /*
 186            Sometimes the implications are just too big to deal with
 187            so we bail.  Theoretically, bailing out here can cause more false
 188            positives but won't hide actual bugs.
 189         */
 190         if (sm_state->nr_children > 4000) {
 191                 implied_debug_msg =
 192                         (char *) "debug: seperate_pools: nr_children over 4000.";
 193                 return;
 194         }
 195
 196         if (checked == NULL) {
 197                 checked = &checked_states;
 198                 free_checked = 1;
 199         }
 200         if (is_checked(*checked, sm_state))
 201                 return;
 202         add_ptr_list(checked, sm_state);
 203
 204         do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
 205
 206         separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
 207         separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
 208         if (free_checked)
 209                 free_slist(checked);
 210 }
 211
 212 struct sm_state *remove_my_pools(struct sm_state *sm,
 213                                 struct state_list_stack *pools, int *modified)
 214 {
 215         struct sm_state *ret = NULL;
 216         struct sm_state *left;
 217         struct sm_state *right;
 218         int removed = 0;
 219
 220         if (!sm)
 221                 return NULL;
 222
 223         if (sm->nr_children > 4000) {
 224                 implied_debug_msg =
 225                         (char *) "debug: remove_my_pools: nr_children over 4000";
 226                 return NULL;
 227         }
 228
 229         if (pool_in_pools(sm->my_pool, pools)) {
 230                 DIMPLIED("removed %s = %s from %d\n", sm->name,
 231                         show_state(sm->state), sm->line);
 232                 *modified = 1;
 233                 return NULL;
 234         }
 235
 236         if (!is_merged(sm)) {
 237                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state),
 238                         sm->line);
 239                 return sm;
 240         }
 241
 242         DIMPLIED("checking %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 243         left = remove_my_pools(sm->left, pools, &removed);
 244         right = remove_my_pools(sm->right, pools, &removed);
 245         if (!removed) {
 246                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 247                 return sm;
 248         }
 249         *modified = 1;
 250         if (!left && !right) {
 251                 DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 252                 return NULL;
 253         }
 254
 255         if (!left) {
 256                 ret = clone_sm(right);
 257                 ret->merged = 1;
 258                 ret->right = right;
 259                 ret->left = NULL;
 260                 ret->my_pool = sm->my_pool;
 261         } else if (!right) {
 262                 ret = clone_sm(left);
 263                 ret->merged = 1;
 264                 ret->left = left;
 265                 ret->right = NULL;
 266                 ret->my_pool = sm->my_pool;
 267         } else {
 268                 ret = merge_sm_states(left, right);
 269                 ret->my_pool = sm->my_pool;
 270         }
 271         ret->implied = 1;
 272         DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 273         return ret;
 274 }
 275
 276 static struct state_list *filter_stack(struct state_list *pre_list,
 277                                 struct state_list_stack *stack)
 278 {
 279         struct state_list *ret = NULL;
 280         struct sm_state *tmp;
 281         struct sm_state *filtered_sm;
 282         int modified;
 283
 284         if (!stack)
 285                 return NULL;
 286
 287         FOR_EACH_PTR(pre_list, tmp) {
 288                 modified = 0;
 289                 filtered_sm = remove_my_pools(tmp, stack, &modified);
 290                 if (filtered_sm && modified) {
 291                         filtered_sm->name = tmp->name;
 292                         filtered_sm->sym = tmp->sym;
 293                         add_ptr_list(&ret, filtered_sm);
 294                         if (out_of_memory())
 295                                 return NULL;
 296
 297                 }
 298         } END_FOR_EACH_PTR(tmp);
 299         return ret;
 300 }
 301
 302 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
 303                 int lr,
 304                 struct state_list *pre_list,
 305                 struct state_list **true_states,
 306                 struct state_list **false_states)
 307 {
 308         struct state_list_stack *true_stack = NULL;
 309         struct state_list_stack *false_stack = NULL;
 310         struct timeval time_before;
 311         struct timeval time_after;
 312
 313         gettimeofday(&time_before, NULL);
 314
 315         if (!is_merged(sm_state)) {
 316                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
 317                 return;
 318         }
 319
 320         if (option_debug_implied || option_debug) {
 321                 if (lr == LEFT)
 322                         sm_msg("checking implications: (%s %s %s)",
 323                                 sm_state->name, show_special(comparison), show_ranges(vals));
 324                 else
 325                         sm_msg("checking implications: (%s %s %s)",
 326                                 show_ranges(vals), show_special(comparison), sm_state->name);
 327         }
 328
 329         separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
 330
 331         DIMPLIED("filtering true stack.\n");
 332         *true_states = filter_stack(pre_list, false_stack);
 333         DIMPLIED("filtering false stack.\n");
 334         *false_states = filter_stack(pre_list, true_stack);
 335         free_stack(&true_stack);
 336         free_stack(&false_stack);
 337         if (option_debug_implied || option_debug) {
 338                 printf("These are the implied states for the true path:\n");
 339                 __print_slist(*true_states);
 340                 printf("These are the implied states for the false path:\n");
 341                 __print_slist(*false_states);
 342         }
 343
 344         gettimeofday(&time_after, NULL);
 345         if (time_after.tv_sec - time_before.tv_sec > 7)
 346                 __bail_on_rest_of_function = 1;
 347 }
 348
 349 static struct sm_state *get_left_most_sm(struct expression *expr)
 350 {
 351         expr = strip_expr(expr);
 352         if (expr->type == EXPR_ASSIGNMENT)
 353                 return get_left_most_sm(expr->left);
 354         return get_sm_state_expr(SMATCH_EXTRA, expr);
 355 }
 356
 357 static int is_merged_expr(struct expression  *expr)
 358 {
 359         struct sm_state *sm;
 360         long long dummy;
 361
 362         if (get_value(expr, &dummy))
 363                 return 0;
 364         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 365         if (!sm)
 366                 return 0;
 367         if (is_merged(sm))
 368                 return 1;
 369         return 0;
 370 }
 371
 372 static void delete_equiv_slist(struct state_list **slist, const char *name, struct symbol *sym)
 373 {
 374         struct smatch_state *state;
 375         struct data_info *dinfo;
 376         struct relation *rel;
 377
 378         state = get_state(SMATCH_EXTRA, name, sym);
 379         dinfo = get_dinfo(state);
 380         if (!dinfo->related) {
 381                 delete_state_slist(slist, SMATCH_EXTRA, name, sym);
 382                 return;
 383         }
 384
 385         FOR_EACH_PTR(dinfo->related, rel) {
 386                 delete_state_slist(slist, SMATCH_EXTRA, rel->name, rel->sym);
 387         } END_FOR_EACH_PTR(rel);
 388 }
 389
 390 static void handle_comparison(struct expression *expr,
 391                               struct state_list **implied_true,
 392                               struct state_list **implied_false)
 393 {
 394         struct sm_state *sm = NULL;
 395         struct range_list *ranges = NULL;
 396         int lr;
 397
 398         if (is_merged_expr(expr->left)) {
 399                 lr = LEFT;
 400                 sm = get_left_most_sm(expr->left);
 401                 ranges = get_range_list(expr->right);
 402         } else if (is_merged_expr(expr->right)) {
 403                 lr = RIGHT;
 404                 sm = get_left_most_sm(expr->right);
 405                 ranges = get_range_list(expr->left);
 406         }
 407
 408         if (!ranges || !sm) {
 409                 free_range_list(&ranges);
 410                 return;
 411         }
 412
 413         separate_and_filter(sm, expr->op, ranges, lr, __get_cur_slist(), implied_true, implied_false);
 414         free_range_list(&ranges);
 415         delete_equiv_slist(implied_true, sm->name, sm->sym);
 416         delete_equiv_slist(implied_false, sm->name, sm->sym);
 417 }
 418
 419 static void handle_zero_comparison(struct expression *expr,
 420                                 struct state_list **implied_true,
 421                                 struct state_list **implied_false)
 422 {
 423         struct symbol *sym;
 424         char *name;
 425         struct sm_state *sm;
 426
 427         if (expr->type == EXPR_POSTOP)
 428                 expr = strip_expr(expr->unop);
 429
 430         if (expr->type == EXPR_ASSIGNMENT) {
 431                 /* most of the time ->my_pools will be empty here because we
 432                    just set the state, but if have assigned a conditional
 433                    function there are implications. */
 434                 expr = expr->left;
 435         }
 436
 437         name = get_variable_from_expr(expr, &sym);
 438         if (!name || !sym)
 439                 goto free;
 440         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 441         if (!sm)
 442                 goto free;
 443
 444         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_slist(), implied_true, implied_false);
 445         delete_equiv_slist(implied_true, name, sym);
 446         delete_equiv_slist(implied_false, name, sym);
 447 free:
 448         free_string(name);
 449 }
 450
 451 static void get_tf_states(struct expression *expr,
 452                           struct state_list **implied_true,
 453                           struct state_list **implied_false)
 454 {
 455         if (expr->type == EXPR_COMPARE)
 456                 handle_comparison(expr, implied_true, implied_false);
 457         else
 458                 handle_zero_comparison(expr, implied_true, implied_false);
 459 }
 460
 461 static void implied_states_hook(struct expression *expr)
 462 {
 463         struct sm_state *sm;
 464         struct state_list *implied_true = NULL;
 465         struct state_list *implied_false = NULL;
 466
 467         if (option_no_implied)
 468                 return;
 469
 470         get_tf_states(expr, &implied_true, &implied_false);
 471
 472         FOR_EACH_PTR(implied_true, sm) {
 473                 __set_true_false_sm(sm, NULL);
 474         } END_FOR_EACH_PTR(sm);
 475         free_slist(&implied_true);
 476
 477         FOR_EACH_PTR(implied_false, sm) {
 478                 __set_true_false_sm(NULL, sm);
 479         } END_FOR_EACH_PTR(sm);
 480         free_slist(&implied_false);
 481 }
 482
 483 struct range_list *__get_implied_values(struct expression *switch_expr)
 484 {
 485         char *name;
 486         struct symbol *sym;
 487         struct smatch_state *state;
 488         struct range_list *ret = NULL;
 489
 490         name = get_variable_from_expr(switch_expr, &sym);
 491         if (!name || !sym)
 492                 goto free;
 493         state = get_state(SMATCH_EXTRA, name, sym);
 494         if (!state)
 495                 goto free;
 496         ret = clone_range_list(get_dinfo(state)->value_ranges);
 497 free:
 498         free_string(name);
 499         if (!ret)
 500                 add_range(&ret, whole_range.min, whole_range.max);
 501         return ret;
 502 }
 503
 504 struct state_list *__implied_case_slist(struct expression *switch_expr,
 505                                         struct expression *case_expr,
 506                                         struct range_list_stack **remaining_cases,
 507                                         struct state_list **raw_slist)
 508 {
 509         char *name = NULL;
 510         struct symbol *sym;
 511         struct sm_state *sm;
 512         struct sm_state *true_sm;
 513         struct state_list *true_states = NULL;
 514         struct state_list *false_states = NULL;
 515         struct state_list *ret = clone_slist(*raw_slist);
 516         long long val;
 517         struct data_range *range;
 518         struct range_list *vals = NULL;
 519
 520         name = get_variable_from_expr(switch_expr, &sym);
 521         if (!name || !sym)
 522                 goto free;
 523         sm = get_sm_state_slist(*raw_slist, SMATCH_EXTRA, name, sym);
 524         if (!case_expr) {
 525                 vals = top_range_list(*remaining_cases);
 526         } else {
 527                 if (!get_value(case_expr, &val)) {
 528                         goto free;
 529                 } else {
 530                         filter_top_range_list(remaining_cases, val);
 531                         range = alloc_range(val, val);
 532                         add_ptr_list(&vals, range);
 533                 }
 534         }
 535         if (sm)
 536                 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_slist, &true_states, &false_states);
 537
 538         true_sm = get_sm_state_slist(true_states, SMATCH_EXTRA, name, sym);
 539         if (!true_sm)
 540                 set_state_slist(&true_states, SMATCH_EXTRA, name, sym, alloc_extra_state_range_list(vals));
 541         overwrite_slist(true_states, &ret);
 542         free_slist(&true_states);
 543         free_slist(&false_states);
 544 free:
 545         free_string(name);
 546         return ret;
 547 }
 548
 549 static void match_end_func(struct symbol *sym)
 550 {
 551         implied_debug_msg = NULL;
 552 }
 553
 554 /*
 555  * get_implications() can be called by check_ scripts.
 556  */
 557 void get_implications(char *name, struct symbol *sym, int comparison, long long num,
 558                       struct state_list **true_states,
 559                       struct state_list **false_states)
 560 {
 561         struct sm_state *sm;
 562
 563         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 564         if (!sm)
 565                 return;
 566         if (slist_has_state(sm->possible, &undefined))
 567                 return;
 568         separate_and_filter(sm, comparison, tmp_range_list(num), LEFT, __get_cur_slist(), true_states, false_states);
 569 }
 570
 571 void __extra_match_condition(struct expression *expr);
 572 void register_implications(int id)
 573 {
 574         add_hook(&implied_states_hook, CONDITION_HOOK);
 575         add_hook(&__extra_match_condition, CONDITION_HOOK);
 576         add_hook(&match_end_func, END_FUNC_HOOK);
 577 }