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