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