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                 static char buf[1028];
 225                 snprintf(buf, sizeof(buf), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
 226                          sm_state->nr_children, sm_state->name, show_state(sm_state->state));
 227                 implied_debug_msg = buf;
 228                 return;
 229         }
 230
 231         if (checked == NULL) {
 232                 checked = &checked_states;
 233                 free_checked = 1;
 234         }
 235         if (is_checked(*checked, sm_state))
 236                 return;
 237         add_ptr_list(checked, sm_state);
 238
 239         do_compare(sm_state, comparison, vals, lr, true_stack, false_stack);
 240
 241         separate_pools(sm_state->left, comparison, vals, lr, true_stack, false_stack, checked);
 242         separate_pools(sm_state->right, comparison, vals, lr, true_stack, false_stack, checked);
 243         if (free_checked)
 244                 free_slist(checked);
 245 }
 246
 247 struct sm_state *remove_pools(struct sm_state *sm,
 248                                 struct state_list_stack *pools, int *modified)
 249 {
 250         struct sm_state *ret = NULL;
 251         struct sm_state *left;
 252         struct sm_state *right;
 253         int removed = 0;
 254
 255         if (!sm)
 256                 return NULL;
 257
 258         if (sm->nr_children > 4000) {
 259                 static char buf[1028];
 260                 snprintf(buf, sizeof(buf), "debug: remove_pools: nr_children over 4000 (%d). (%s %s)",
 261                          sm->nr_children, sm->name, show_state(sm->state));
 262                 implied_debug_msg = buf;
 263                 return NULL;
 264         }
 265
 266         if (pool_in_pools(sm->pool, pools)) {
 267                 DIMPLIED("removed %s from %d\n", show_sm(sm), sm->line);
 268                 *modified = 1;
 269                 return NULL;
 270         }
 271
 272         if (!is_merged(sm)) {
 273                 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
 274                 return sm;
 275         }
 276
 277         DIMPLIED("checking %s from %d (%d)\n", show_sm(sm), sm->line, sm->nr_children);
 278         left = remove_pools(sm->left, pools, &removed);
 279         right = remove_pools(sm->right, pools, &removed);
 280         if (!removed) {
 281                 DIMPLIED("kept %s from %d\n", show_sm(sm), sm->line);
 282                 return sm;
 283         }
 284         *modified = 1;
 285         if (!left && !right) {
 286                 DIMPLIED("removed %s from %d <none>\n", show_sm(sm), sm->line);
 287                 return NULL;
 288         }
 289
 290         if (!left) {
 291                 ret = clone_sm(right);
 292                 ret->merged = 1;
 293                 ret->right = right;
 294                 ret->left = NULL;
 295                 ret->pool = sm->pool;
 296         } else if (!right) {
 297                 ret = clone_sm(left);
 298                 ret->merged = 1;
 299                 ret->left = left;
 300                 ret->right = NULL;
 301                 ret->pool = sm->pool;
 302         } else {
 303                 ret = merge_sm_states(left, right);
 304                 ret->pool = sm->pool;
 305         }
 306         ret->implied = 1;
 307         DIMPLIED("partial %s => ", show_sm(sm));
 308         DIMPLIED("%s from %d\n", show_sm(ret), sm->line);
 309         return ret;
 310 }
 311
 312 static int highest_slist_id(struct sm_state *sm)
 313 {
 314         int left = 0;
 315         int right = 0;
 316
 317         if (!sm->left && !sm->right)
 318                 return 0;
 319
 320         if (sm->left)
 321                 left = get_slist_id(sm->left->pool);
 322         if (sm->right)
 323                 right = get_slist_id(sm->right->pool);
 324
 325         if (right > left)
 326                 return right;
 327         return left;
 328 }
 329
 330 static struct state_list *filter_stack(struct sm_state *gate_sm,
 331                                        struct state_list *pre_list,
 332                                        struct state_list_stack *stack)
 333 {
 334         struct state_list *ret = NULL;
 335         struct sm_state *tmp;
 336         struct sm_state *filtered_sm;
 337         int modified;
 338
 339         if (!stack)
 340                 return NULL;
 341
 342         FOR_EACH_PTR(pre_list, tmp) {
 343                 if (highest_slist_id(tmp) < highest_slist_id(gate_sm)) {
 344                         DIMPLIED("skipping %s.  set before.  %d vs %d",
 345                                         tmp->name, highest_slist_id(tmp),
 346                                         highest_slist_id(gate_sm));
 347                         continue;
 348                 }
 349                 modified = 0;
 350                 filtered_sm = remove_pools(tmp, stack, &modified);
 351                 if (filtered_sm && modified) {
 352                         filtered_sm->name = tmp->name;
 353                         filtered_sm->sym = tmp->sym;
 354                         add_ptr_list(&ret, filtered_sm);
 355                         if (out_of_memory())
 356                                 return NULL;
 357
 358                 }
 359         } END_FOR_EACH_PTR(tmp);
 360         return ret;
 361 }
 362
 363 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
 364                 int lr,
 365                 struct state_list *pre_list,
 366                 struct state_list **true_states,
 367                 struct state_list **false_states)
 368 {
 369         struct state_list_stack *true_stack = NULL;
 370         struct state_list_stack *false_stack = NULL;
 371         struct timeval time_before;
 372         struct timeval time_after;
 373
 374         gettimeofday(&time_before, NULL);
 375
 376         if (!is_merged(sm_state)) {
 377                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
 378                 return;
 379         }
 380
 381         if (option_debug_implied || option_debug) {
 382                 if (lr == LEFT)
 383                         sm_msg("checking implications: (%s %s %s)",
 384                                 sm_state->name, show_special(comparison), show_ranges(vals));
 385                 else
 386                         sm_msg("checking implications: (%s %s %s)",
 387                                 show_ranges(vals), show_special(comparison), sm_state->name);
 388         }
 389
 390         separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
 391
 392         DIMPLIED("filtering true stack.\n");
 393         *true_states = filter_stack(sm_state, pre_list, false_stack);
 394         DIMPLIED("filtering false stack.\n");
 395         *false_states = filter_stack(sm_state, pre_list, true_stack);
 396         free_stack(&true_stack);
 397         free_stack(&false_stack);
 398         if (option_debug_implied || option_debug) {
 399                 printf("These are the implied states for the true path:\n");
 400                 __print_slist(*true_states);
 401                 printf("These are the implied states for the false path:\n");
 402                 __print_slist(*false_states);
 403         }
 404
 405         gettimeofday(&time_after, NULL);
 406         if (time_after.tv_sec - time_before.tv_sec > 7)
 407                 __bail_on_rest_of_function = 1;
 408 }
 409
 410 static struct expression *get_left_most_expr(struct expression *expr)
 411 {
 412         expr = strip_expr(expr);
 413         if (expr->type == EXPR_ASSIGNMENT)
 414                 return get_left_most_expr(expr->left);
 415         return expr;
 416 }
 417
 418 static int is_merged_expr(struct expression  *expr)
 419 {
 420         struct sm_state *sm;
 421         long long dummy;
 422
 423         if (get_value(expr, &dummy))
 424                 return 0;
 425         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 426         if (!sm)
 427                 return 0;
 428         if (is_merged(sm))
 429                 return 1;
 430         return 0;
 431 }
 432
 433 static void delete_equiv_slist(struct state_list **slist, const char *name, struct symbol *sym)
 434 {
 435         struct smatch_state *state;
 436         struct relation *rel;
 437
 438         state = get_state(SMATCH_EXTRA, name, sym);
 439         if (!estate_related(state)) {
 440                 delete_state_slist(slist, SMATCH_EXTRA, name, sym);
 441                 return;
 442         }
 443
 444         FOR_EACH_PTR(estate_related(state), rel) {
 445                 delete_state_slist(slist, SMATCH_EXTRA, rel->name, rel->sym);
 446         } END_FOR_EACH_PTR(rel);
 447 }
 448
 449 static void handle_comparison(struct expression *expr,
 450                               struct state_list **implied_true,
 451                               struct state_list **implied_false)
 452 {
 453         struct sm_state *sm = NULL;
 454         struct range_list *ranges = NULL;
 455         struct expression *left;
 456         struct expression *right;
 457         int lr;
 458
 459         left = get_left_most_expr(expr->left);
 460         right = get_left_most_expr(expr->right);
 461
 462         if (is_merged_expr(left)) {
 463                 lr = LEFT;
 464                 sm = get_sm_state_expr(SMATCH_EXTRA, left);
 465                 get_implied_range_list(right, &ranges);
 466         } else if (is_merged_expr(right)) {
 467                 lr = RIGHT;
 468                 sm = get_sm_state_expr(SMATCH_EXTRA, right);
 469                 get_implied_range_list(left, &ranges);
 470         }
 471
 472         if (!ranges || !sm) {
 473                 free_range_list(&ranges);
 474                 return;
 475         }
 476
 477         separate_and_filter(sm, expr->op, ranges, lr, __get_cur_slist(), implied_true, implied_false);
 478         free_range_list(&ranges);
 479         delete_equiv_slist(implied_true, sm->name, sm->sym);
 480         delete_equiv_slist(implied_false, sm->name, sm->sym);
 481 }
 482
 483 static void handle_zero_comparison(struct expression *expr,
 484                                 struct state_list **implied_true,
 485                                 struct state_list **implied_false)
 486 {
 487         struct symbol *sym;
 488         char *name;
 489         struct sm_state *sm;
 490
 491         if (expr->type == EXPR_POSTOP)
 492                 expr = strip_expr(expr->unop);
 493
 494         if (expr->type == EXPR_ASSIGNMENT) {
 495                 /* most of the time ->pools will be empty here because we
 496                    just set the state, but if have assigned a conditional
 497                    function there are implications. */
 498                 expr = expr->left;
 499         }
 500
 501         name = get_variable_from_expr(expr, &sym);
 502         if (!name || !sym)
 503                 goto free;
 504         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 505         if (!sm)
 506                 goto free;
 507
 508         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_slist(), implied_true, implied_false);
 509         delete_equiv_slist(implied_true, name, sym);
 510         delete_equiv_slist(implied_false, name, sym);
 511 free:
 512         free_string(name);
 513 }
 514
 515 static void get_tf_states(struct expression *expr,
 516                           struct state_list **implied_true,
 517                           struct state_list **implied_false)
 518 {
 519         if (expr->type == EXPR_COMPARE)
 520                 handle_comparison(expr, implied_true, implied_false);
 521         else
 522                 handle_zero_comparison(expr, implied_true, implied_false);
 523 }
 524
 525 static void implied_states_hook(struct expression *expr)
 526 {
 527         struct sm_state *sm;
 528         struct state_list *implied_true = NULL;
 529         struct state_list *implied_false = NULL;
 530
 531         if (option_no_implied)
 532                 return;
 533
 534         get_tf_states(expr, &implied_true, &implied_false);
 535
 536         FOR_EACH_PTR(implied_true, sm) {
 537                 __set_true_false_sm(sm, NULL);
 538         } END_FOR_EACH_PTR(sm);
 539         free_slist(&implied_true);
 540
 541         FOR_EACH_PTR(implied_false, sm) {
 542                 __set_true_false_sm(NULL, sm);
 543         } END_FOR_EACH_PTR(sm);
 544         free_slist(&implied_false);
 545 }
 546
 547 struct range_list *__get_implied_values(struct expression *switch_expr)
 548 {
 549         char *name;
 550         struct symbol *sym;
 551         struct smatch_state *state;
 552         struct range_list *ret = NULL;
 553
 554         name = get_variable_from_expr(switch_expr, &sym);
 555         if (!name || !sym)
 556                 goto free;
 557         state = get_state(SMATCH_EXTRA, name, sym);
 558         if (!state)
 559                 goto free;
 560         ret = clone_range_list(estate_ranges(state));
 561 free:
 562         free_string(name);
 563         if (!ret)
 564                 add_range(&ret, whole_range.min, whole_range.max);
 565         return ret;
 566 }
 567
 568 struct state_list *__implied_case_slist(struct expression *switch_expr,
 569                                         struct expression *case_expr,
 570                                         struct range_list_stack **remaining_cases,
 571                                         struct state_list **raw_slist)
 572 {
 573         char *name = NULL;
 574         struct symbol *sym;
 575         struct sm_state *sm;
 576         struct sm_state *true_sm;
 577         struct state_list *true_states = NULL;
 578         struct state_list *false_states = NULL;
 579         struct state_list *ret = clone_slist(*raw_slist);
 580         long long val;
 581         struct range_list *vals = NULL;
 582
 583         name = get_variable_from_expr(switch_expr, &sym);
 584         if (!name || !sym)
 585                 goto free;
 586         sm = get_sm_state_slist(*raw_slist, SMATCH_EXTRA, name, sym);
 587         if (!case_expr) {
 588                 vals = top_range_list(*remaining_cases);
 589         } else {
 590                 if (!get_value(case_expr, &val))
 591                         goto free;
 592
 593                 filter_top_range_list(remaining_cases, val);
 594                 add_range(&vals, val, val);
 595         }
 596         if (sm)
 597                 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_slist, &true_states, &false_states);
 598
 599         true_sm = get_sm_state_slist(true_states, SMATCH_EXTRA, name, sym);
 600         if (!true_sm)
 601                 set_state_slist(&true_states, SMATCH_EXTRA, name, sym, alloc_estate_range_list(vals));
 602         overwrite_slist(true_states, &ret);
 603         free_slist(&true_states);
 604         free_slist(&false_states);
 605 free:
 606         free_string(name);
 607         return ret;
 608 }
 609
 610 static void match_end_func(struct symbol *sym)
 611 {
 612         implied_debug_msg = NULL;
 613 }
 614
 615 /*
 616  * get_implications() can be called by check_ scripts.
 617  */
 618 void get_implications(char *name, struct symbol *sym, int comparison, long long num,
 619                       struct state_list **true_states,
 620                       struct state_list **false_states)
 621 {
 622         struct sm_state *sm;
 623
 624         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 625         if (!sm)
 626                 return;
 627         if (slist_has_state(sm->possible, &undefined))
 628                 return;
 629         separate_and_filter(sm, comparison, tmp_range_list(num), LEFT, __get_cur_slist(), true_states, false_states);
 630 }
 631
 632 void __extra_match_condition(struct expression *expr);
 633 void register_implications(int id)
 634 {
 635         add_hook(&implied_states_hook, CONDITION_HOOK);
 636         add_hook(&__extra_match_condition, CONDITION_HOOK);
 637         add_hook(&match_end_func, END_FUNC_HOOK);
 638 }