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 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 ->pool.  An sm_state only has one ->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 ->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 static void print_debug_tf(struct sm_state *s, int istrue, int isfalse)
  85 {
  86         if (!option_debug_implied && !option_debug)
  87                 return;
  88
  89         if (istrue && isfalse) {
  90                 printf("'%s = %s' from %d does not exist.\n", s->name,
  91                         show_state(s->state), s->line);
  92         } else if (istrue) {
  93                 printf("'%s = %s' from %d is true.\n", s->name, show_state(s->state),
  94                         s->line);
  95         } else if (isfalse) {
  96                 printf("'%s = %s' from %d is false.\n", s->name, show_state(s->state),
  97                         s->line);
  98         } else {
  99                 printf("'%s = %s' from %d could be true or false.\n", s->name,
 100                         show_state(s->state), s->line);
 101         }
 102 }
 103
 104 /*
 105  * add_pool() adds a slist to *pools. If the slist has already been
 106  * added earlier then it doesn't get added a second time.
 107  */
 108 static void add_pool(struct state_list_stack **pools, struct state_list *new)
 109 {
 110         struct state_list *tmp;
 111
 112         FOR_EACH_PTR(*pools, tmp) {
 113                 if (tmp < new)
 114                         continue;
 115                 else if (tmp == new) {
 116                         return;
 117                 } else {
 118                         INSERT_CURRENT(new, tmp);
 119                         return;
 120                 }
 121         } END_FOR_EACH_PTR(tmp);
 122         add_ptr_list(pools, new);
 123 }
 124
 125 /*
 126  * If 'foo' == 99 add it that pool to the true pools.  If it's false, add it to
 127  * the false pools.  If we're not sure, then we don't add it to either.
 128  */
 129 static void do_compare(struct sm_state *sm_state, int comparison, struct range_list *vals,
 130                         int lr,
 131                         struct state_list_stack **true_stack,
 132                         struct state_list_stack **false_stack)
 133 {
 134         struct sm_state *s;
 135         int istrue;
 136         int isfalse;
 137
 138         if (!sm_state->pool)
 139                 return;
 140
 141         if (is_implied(sm_state)) {
 142                 s = get_sm_state_slist(sm_state->pool,
 143                                 sm_state->owner, sm_state->name,
 144                                 sm_state->sym);
 145         } else {
 146                 s = sm_state;
 147         }
 148
 149         if (!s) {
 150                 if (option_debug_implied || option_debug)
 151                         sm_msg("%s from %d, has borrowed implications.",
 152                                 sm_state->name, sm_state->line);
 153                 return;
 154         }
 155
 156         if (lr == LEFT) {
 157                 istrue = !possibly_false_range_lists(estate_ranges(s->state), comparison, vals);
 158                 isfalse = !possibly_true_range_lists(estate_ranges(s->state), comparison, vals);
 159         } else {
 160                 istrue = !possibly_false_range_lists(vals, comparison, estate_ranges(s->state));
 161                 isfalse = !possibly_true_range_lists(vals, comparison, estate_ranges(s->state));
 162         }
 163
 164         print_debug_tf(s, istrue, isfalse);
 165
 166         if (istrue)
 167                 add_pool(true_stack, s->pool);
 168
 169         if (isfalse)
 170                 add_pool(false_stack, s->pool);
 171 }
 172
 173 static int pool_in_pools(struct state_list *pool,
 174                         struct state_list_stack *pools)
 175 {
 176         struct state_list *tmp;
 177
 178         FOR_EACH_PTR(pools, tmp) {
 179                 if (tmp == pool)
 180                         return 1;
 181                 if (tmp > pool)
 182                         return 0;
 183         } END_FOR_EACH_PTR(tmp);
 184         return 0;
 185 }
 186
 187 static int is_checked(struct state_list *checked, struct sm_state *sm)
 188 {
 189         struct sm_state *tmp;
 190
 191         FOR_EACH_PTR(checked, tmp) {
 192                 if (tmp == sm)
 193                         return 1;
 194         } END_FOR_EACH_PTR(tmp);
 195         return 0;
 196 }
 197
 198 /*
 199  * separate_pools():
 200  * Example code:  if (foo == 99) {
 201  *
 202  * Say 'foo' is a merged state that has many possible values.  It is the combination
 203  * of merges.  separate_pools() iterates through the pools recursively and calls
 204  * do_compare() for each time 'foo' was set.
 205  */
 206 static void separate_pools(struct sm_state *sm_state, int comparison, struct range_list *vals,
 207                         int lr,
 208                         struct state_list_stack **true_stack,
 209                         struct state_list_stack **false_stack,
 210                         struct state_list **checked)
 211 {
 212         int free_checked = 0;
 213         struct state_list *checked_states = NULL;
 214
 215         if (!sm_state)
 216                 return;
 217
 218         /*
 219            Sometimes the implications are just too big to deal with
 220            so we bail.  Theoretically, bailing out here can cause more false
 221            positives but won't hide actual bugs.
 222         */
 223         if (sm_state->nr_children > 4000) {
 224                 implied_debug_msg =
 225                         (char *) "debug: seperate_pools: nr_children over 4000.";
 226                 return;
 227         }
 228
 229         if (checked == NULL) {
 230                 checked = &checked_states;
 231                 free_checked = 1;
 232         }
 233         if (is_checked(*checked, sm_state))
 234                 return;
 235         add_ptr_list(checked, sm_state);
 236
 237         do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
 238
 239         separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
 240         separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
 241         if (free_checked)
 242                 free_slist(checked);
 243 }
 244
 245 struct sm_state *remove_pools(struct sm_state *sm,
 246                                 struct state_list_stack *pools, int *modified)
 247 {
 248         struct sm_state *ret = NULL;
 249         struct sm_state *left;
 250         struct sm_state *right;
 251         int removed = 0;
 252
 253         if (!sm)
 254                 return NULL;
 255
 256         if (sm->nr_children > 4000) {
 257                 implied_debug_msg =
 258                         (char *) "debug: remove_pools: nr_children over 4000";
 259                 return NULL;
 260         }
 261
 262         if (pool_in_pools(sm->pool, pools)) {
 263                 DIMPLIED("removed %s from %d\n", show_sm(sm), sm->line);
 264                 *modified = 1;
 265                 return NULL;
 266         }
 267
 268         if (!is_merged(sm)) {
 269                 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
 270                 return sm;
 271         }
 272
 273         DIMPLIED("checking %s from %d\n", show_sm(sm), sm->line);
 274         left = remove_pools(sm->left, pools, &removed);
 275         right = remove_pools(sm->right, pools, &removed);
 276         if (!removed) {
 277                 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
 278                 return sm;
 279         }
 280         *modified = 1;
 281         if (!left && !right) {
 282                 DIMPLIED("removed %s from %d <none>\n", show_sm(sm), sm->line);
 283                 return NULL;
 284         }
 285
 286         if (!left) {
 287                 ret = clone_sm(right);
 288                 ret->merged = 1;
 289                 ret->right = right;
 290                 ret->left = NULL;
 291                 ret->pool = sm->pool;
 292         } else if (!right) {
 293                 ret = clone_sm(left);
 294                 ret->merged = 1;
 295                 ret->left = left;
 296                 ret->right = NULL;
 297                 ret->pool = sm->pool;
 298         } else {
 299                 ret = merge_sm_states(left, right);
 300                 ret->pool = sm->pool;
 301         }
 302         ret->implied = 1;
 303         DIMPLIED("partial %s => ", show_sm(sm));
 304         DIMPLIED("%s from %d\n", show_sm(ret), sm->line);
 305         return ret;
 306 }
 307
 308 static int highest_slist_id(struct sm_state *sm)
 309 {
 310         int left = 0;
 311         int right = 0;
 312
 313         if (!sm->left && !sm->right)
 314                 return 0;
 315
 316         if (sm->left)
 317                 left = get_slist_id(sm->left->pool);
 318         if (sm->right)
 319                 right = get_slist_id(sm->right->pool);
 320
 321         if (right > left)
 322                 return right;
 323         return left;
 324 }
 325
 326 static int in_last_base_slist(struct sm_state *sm)
 327 {
 328         struct sm_state *tmp;
 329
 330         tmp = get_sm_state_slist(__last_base_slist, sm->owner, sm->name, sm->sym);
 331         if (tmp == sm)
 332                 return 1;
 333         return 0;
 334 }
 335
 336 static struct state_list *filter_stack(struct sm_state *gate_sm,
 337                                        struct state_list *pre_list,
 338                                        struct state_list_stack *stack)
 339 {
 340         struct state_list *ret = NULL;
 341         struct sm_state *tmp;
 342         struct sm_state *filtered_sm;
 343         int modified;
 344
 345         if (!stack)
 346                 return NULL;
 347
 348         FOR_EACH_PTR(pre_list, tmp) {
 349                 if (in_last_base_slist(tmp) &&
 350                                 (highest_slist_id(tmp) < highest_slist_id(gate_sm)))
 351                         continue;
 352                 modified = 0;
 353                 filtered_sm = remove_pools(tmp, stack, &modified);
 354                 if (filtered_sm && modified) {
 355                         filtered_sm->name = tmp->name;
 356                         filtered_sm->sym = tmp->sym;
 357                         add_ptr_list(&ret, filtered_sm);
 358                         if (out_of_memory())
 359                                 return NULL;
 360
 361                 }
 362         } END_FOR_EACH_PTR(tmp);
 363         return ret;
 364 }
 365
 366 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
 367                 int lr,
 368                 struct state_list *pre_list,
 369                 struct state_list **true_states,
 370                 struct state_list **false_states)
 371 {
 372         struct state_list_stack *true_stack = NULL;
 373         struct state_list_stack *false_stack = NULL;
 374         struct timeval time_before;
 375         struct timeval time_after;
 376
 377         gettimeofday(&time_before, NULL);
 378
 379         if (!is_merged(sm_state)) {
 380                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
 381                 return;
 382         }
 383
 384         if (option_debug_implied || option_debug) {
 385                 if (lr == LEFT)
 386                         sm_msg("checking implications: (%s %s %s)",
 387                                 sm_state->name, show_special(comparison), show_ranges(vals));
 388                 else
 389                         sm_msg("checking implications: (%s %s %s)",
 390                                 show_ranges(vals), show_special(comparison), sm_state->name);
 391         }
 392
 393         separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
 394
 395         DIMPLIED("filtering true stack.\n");
 396         *true_states = filter_stack(sm_state, pre_list, false_stack);
 397         DIMPLIED("filtering false stack.\n");
 398         *false_states = filter_stack(sm_state, pre_list, true_stack);
 399         free_stack(&true_stack);
 400         free_stack(&false_stack);
 401         if (option_debug_implied || option_debug) {
 402                 printf("These are the implied states for the true path:\n");
 403                 __print_slist(*true_states);
 404                 printf("These are the implied states for the false path:\n");
 405                 __print_slist(*false_states);
 406         }
 407
 408         gettimeofday(&time_after, NULL);
 409         if (time_after.tv_sec - time_before.tv_sec > 7)
 410                 __bail_on_rest_of_function = 1;
 411 }
 412
 413 static struct expression *get_left_most_expr(struct expression *expr)
 414 {
 415         expr = strip_expr(expr);
 416         if (expr->type == EXPR_ASSIGNMENT)
 417                 return get_left_most_expr(expr->left);
 418         return expr;
 419 }
 420
 421 static int is_merged_expr(struct expression  *expr)
 422 {
 423         struct sm_state *sm;
 424         long long dummy;
 425
 426         if (get_value(expr, &dummy))
 427                 return 0;
 428         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 429         if (!sm)
 430                 return 0;
 431         if (is_merged(sm))
 432                 return 1;
 433         return 0;
 434 }
 435
 436 static void delete_equiv_slist(struct state_list **slist, const char *name, struct symbol *sym)
 437 {
 438         struct smatch_state *state;
 439         struct relation *rel;
 440
 441         state = get_state(SMATCH_EXTRA, name, sym);
 442         if (!estate_related(state)) {
 443                 delete_state_slist(slist, SMATCH_EXTRA, name, sym);
 444                 return;
 445         }
 446
 447         FOR_EACH_PTR(estate_related(state), rel) {
 448                 delete_state_slist(slist, SMATCH_EXTRA, rel->name, rel->sym);
 449         } END_FOR_EACH_PTR(rel);
 450 }
 451
 452 static void handle_comparison(struct expression *expr,
 453                               struct state_list **implied_true,
 454                               struct state_list **implied_false)
 455 {
 456         struct sm_state *sm = NULL;
 457         struct range_list *ranges = NULL;
 458         struct expression *left;
 459         struct expression *right;
 460         int lr;
 461
 462         left = get_left_most_expr(expr->left);
 463         right = get_left_most_expr(expr->right);
 464
 465         if (is_merged_expr(left)) {
 466                 lr = LEFT;
 467                 sm = get_sm_state_expr(SMATCH_EXTRA, left);
 468                 get_implied_range_list(right, &ranges);
 469         } else if (is_merged_expr(right)) {
 470                 lr = RIGHT;
 471                 sm = get_sm_state_expr(SMATCH_EXTRA, right);
 472                 get_implied_range_list(left, &ranges);
 473         }
 474
 475         if (!ranges || !sm) {
 476                 free_range_list(&ranges);
 477                 return;
 478         }
 479
 480         separate_and_filter(sm, expr->op, ranges, lr, __get_cur_slist(), implied_true, implied_false);
 481         free_range_list(&ranges);
 482         delete_equiv_slist(implied_true, sm->name, sm->sym);
 483         delete_equiv_slist(implied_false, sm->name, sm->sym);
 484 }
 485
 486 static void handle_zero_comparison(struct expression *expr,
 487                                 struct state_list **implied_true,
 488                                 struct state_list **implied_false)
 489 {
 490         struct symbol *sym;
 491         char *name;
 492         struct sm_state *sm;
 493
 494         if (expr->type == EXPR_POSTOP)
 495                 expr = strip_expr(expr->unop);
 496
 497         if (expr->type == EXPR_ASSIGNMENT) {
 498                 /* most of the time ->pools will be empty here because we
 499                    just set the state, but if have assigned a conditional
 500                    function there are implications. */
 501                 expr = expr->left;
 502         }
 503
 504         name = get_variable_from_expr(expr, &sym);
 505         if (!name || !sym)
 506                 goto free;
 507         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 508         if (!sm)
 509                 goto free;
 510
 511         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_slist(), implied_true, implied_false);
 512         delete_equiv_slist(implied_true, name, sym);
 513         delete_equiv_slist(implied_false, name, sym);
 514 free:
 515         free_string(name);
 516 }
 517
 518 static void get_tf_states(struct expression *expr,
 519                           struct state_list **implied_true,
 520                           struct state_list **implied_false)
 521 {
 522         if (expr->type == EXPR_COMPARE)
 523                 handle_comparison(expr, implied_true, implied_false);
 524         else
 525                 handle_zero_comparison(expr, implied_true, implied_false);
 526 }
 527
 528 static void implied_states_hook(struct expression *expr)
 529 {
 530         struct sm_state *sm;
 531         struct state_list *implied_true = NULL;
 532         struct state_list *implied_false = NULL;
 533
 534         if (option_no_implied)
 535                 return;
 536
 537         get_tf_states(expr, &implied_true, &implied_false);
 538
 539         FOR_EACH_PTR(implied_true, sm) {
 540                 __set_true_false_sm(sm, NULL);
 541         } END_FOR_EACH_PTR(sm);
 542         free_slist(&implied_true);
 543
 544         FOR_EACH_PTR(implied_false, sm) {
 545                 __set_true_false_sm(NULL, sm);
 546         } END_FOR_EACH_PTR(sm);
 547         free_slist(&implied_false);
 548 }
 549
 550 struct range_list *__get_implied_values(struct expression *switch_expr)
 551 {
 552         char *name;
 553         struct symbol *sym;
 554         struct smatch_state *state;
 555         struct range_list *ret = NULL;
 556
 557         name = get_variable_from_expr(switch_expr, &sym);
 558         if (!name || !sym)
 559                 goto free;
 560         state = get_state(SMATCH_EXTRA, name, sym);
 561         if (!state)
 562                 goto free;
 563         ret = clone_range_list(estate_ranges(state));
 564 free:
 565         free_string(name);
 566         if (!ret)
 567                 add_range(&ret, whole_range.min, whole_range.max);
 568         return ret;
 569 }
 570
 571 struct state_list *__implied_case_slist(struct expression *switch_expr,
 572                                         struct expression *case_expr,
 573                                         struct range_list_stack **remaining_cases,
 574                                         struct state_list **raw_slist)
 575 {
 576         char *name = NULL;
 577         struct symbol *sym;
 578         struct sm_state *sm;
 579         struct sm_state *true_sm;
 580         struct state_list *true_states = NULL;
 581         struct state_list *false_states = NULL;
 582         struct state_list *ret = clone_slist(*raw_slist);
 583         long long val;
 584         struct range_list *vals = NULL;
 585
 586         name = get_variable_from_expr(switch_expr, &sym);
 587         if (!name || !sym)
 588                 goto free;
 589         sm = get_sm_state_slist(*raw_slist, SMATCH_EXTRA, name, sym);
 590         if (!case_expr) {
 591                 vals = top_range_list(*remaining_cases);
 592         } else {
 593                 if (!get_value(case_expr, &val))
 594                         goto free;
 595
 596                 filter_top_range_list(remaining_cases, val);
 597                 add_range(&vals, val, val);
 598         }
 599         if (sm)
 600                 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_slist, &true_states, &false_states);
 601
 602         true_sm = get_sm_state_slist(true_states, SMATCH_EXTRA, name, sym);
 603         if (!true_sm)
 604                 set_state_slist(&true_states, SMATCH_EXTRA, name, sym, alloc_estate_range_list(vals));
 605         overwrite_slist(true_states, &ret);
 606         free_slist(&true_states);
 607         free_slist(&false_states);
 608 free:
 609         free_string(name);
 610         return ret;
 611 }
 612
 613 static void match_end_func(struct symbol *sym)
 614 {
 615         implied_debug_msg = NULL;
 616 }
 617
 618 /*
 619  * get_implications() can be called by check_ scripts.
 620  */
 621 void get_implications(char *name, struct symbol *sym, int comparison, long long num,
 622                       struct state_list **true_states,
 623                       struct state_list **false_states)
 624 {
 625         struct sm_state *sm;
 626
 627         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 628         if (!sm)
 629                 return;
 630         if (slist_has_state(sm->possible, &undefined))
 631                 return;
 632         separate_and_filter(sm, comparison, tmp_range_list(num), LEFT, __get_cur_slist(), true_states, false_states);
 633 }
 634
 635 void __extra_match_condition(struct expression *expr);
 636 void register_implications(int id)
 637 {
 638         add_hook(&implied_states_hook, CONDITION_HOOK);
 639         add_hook(&__extra_match_condition, CONDITION_HOOK);
 640         add_hook(&match_end_func, END_FUNC_HOOK);
 641 }