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(comparison, get_dinfo(s->state), vals, lr);
 117         isfalse = !possibly_true_range_list(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 char *get_implication_variable(struct expression *expr, struct symbol **symp)
 352 {
 353         expr = strip_expr(expr);
 354         if (expr->type == EXPR_ASSIGNMENT)
 355                 return get_implication_variable(expr->left, symp);
 356         return get_variable_from_expr(expr, symp);
 357 }
 358
 359 static int get_known_value(struct expression *expr, long long *val)
 360 {
 361         struct sm_state *sm;
 362
 363         if (get_value(expr, val))
 364                 return 1;
 365         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 366         if (!sm)
 367                 return 0;
 368         if (!get_single_value_from_dinfo(get_dinfo(sm->state), val))
 369                 return 0;
 370         if (!is_implied(sm))
 371                 return 1;
 372         return 0;
 373 }
 374
 375 static void delete_equiv_slist(struct state_list **slist, const char *name, struct symbol *sym)
 376 {
 377         struct smatch_state *state;
 378         struct data_info *dinfo;
 379         struct tracker *tracker;
 380
 381         state = get_state(SMATCH_EXTRA, name, sym);
 382         dinfo = get_dinfo(state);
 383         if (!dinfo->equiv) {
 384                 delete_state_slist(slist, SMATCH_EXTRA, name, sym);
 385                 return;
 386         }
 387
 388         FOR_EACH_PTR(dinfo->equiv, tracker) {
 389                 delete_state_slist(slist, SMATCH_EXTRA, tracker->name, tracker->sym);
 390         } END_FOR_EACH_PTR(tracker);
 391 }
 392
 393 static void handle_comparison(struct expression *expr,
 394                               struct state_list **implied_true,
 395                               struct state_list **implied_false)
 396 {
 397         struct symbol *sym;
 398         char *name;
 399         struct sm_state *sm;
 400         long long value;
 401         int lr;
 402
 403         if (get_known_value(expr->right, &value))
 404                 lr = LEFT;
 405         else if (get_known_value(expr->left, &value))
 406                 lr = RIGHT;
 407         else
 408                 return;
 409
 410         if (lr == LEFT)
 411                 name = get_implication_variable(expr->left, &sym);
 412         else
 413                 name = get_implication_variable(expr->right, &sym);
 414         if (!name || !sym)
 415                 goto free;
 416
 417         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 418         if (!sm)
 419                 goto free;
 420
 421         separate_and_filter(sm, expr->op, tmp_range_list(value), lr, __get_cur_slist(), implied_true, implied_false);
 422         delete_equiv_slist(implied_true, name, sym);
 423         delete_equiv_slist(implied_false, name, sym);
 424 free:
 425         free_string(name);
 426 }
 427
 428 static void handle_zero_comparison(struct expression *expr,
 429                                 struct state_list **implied_true,
 430                                 struct state_list **implied_false)
 431 {
 432         struct symbol *sym;
 433         char *name;
 434         struct sm_state *sm;
 435
 436         if (expr->type == EXPR_POSTOP)
 437                 expr = strip_expr(expr->unop);
 438
 439         if (expr->type == EXPR_ASSIGNMENT) {
 440                 /* most of the time ->my_pools will be empty here because we
 441                    just set the state, but if have assigned a conditional
 442                    function there are implications. */
 443                 expr = expr->left;
 444         }
 445
 446         name = get_variable_from_expr(expr, &sym);
 447         if (!name || !sym)
 448                 goto free;
 449         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 450         if (!sm)
 451                 goto free;
 452
 453         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_slist(), implied_true, implied_false);
 454         delete_equiv_slist(implied_true, name, sym);
 455         delete_equiv_slist(implied_false, name, sym);
 456 free:
 457         free_string(name);
 458 }
 459
 460 static void get_tf_states(struct expression *expr,
 461                           struct state_list **implied_true,
 462                           struct state_list **implied_false)
 463 {
 464         if (expr->type == EXPR_COMPARE)
 465                 handle_comparison(expr, implied_true, implied_false);
 466         else
 467                 handle_zero_comparison(expr, implied_true, implied_false);
 468 }
 469
 470 static void implied_states_hook(struct expression *expr)
 471 {
 472         struct sm_state *sm;
 473         struct state_list *implied_true = NULL;
 474         struct state_list *implied_false = NULL;
 475
 476         if (option_no_implied)
 477                 return;
 478
 479         get_tf_states(expr, &implied_true, &implied_false);
 480
 481         FOR_EACH_PTR(implied_true, sm) {
 482                 __set_true_false_sm(sm, NULL);
 483         } END_FOR_EACH_PTR(sm);
 484         free_slist(&implied_true);
 485
 486         FOR_EACH_PTR(implied_false, sm) {
 487                 __set_true_false_sm(NULL, sm);
 488         } END_FOR_EACH_PTR(sm);
 489         free_slist(&implied_false);
 490 }
 491
 492 struct range_list *__get_implied_values(struct expression *switch_expr)
 493 {
 494         char *name;
 495         struct symbol *sym;
 496         struct smatch_state *state;
 497         struct range_list *ret = NULL;
 498
 499         name = get_variable_from_expr(switch_expr, &sym);
 500         if (!name || !sym)
 501                 goto free;
 502         state = get_state(SMATCH_EXTRA, name, sym);
 503         if (!state)
 504                 goto free;
 505         ret = clone_range_list(get_dinfo(state)->value_ranges);
 506 free:
 507         free_string(name);
 508         if (!ret)
 509                 add_range(&ret, whole_range.min, whole_range.max);
 510         return ret;
 511 }
 512
 513 struct state_list *__implied_case_slist(struct expression *switch_expr,
 514                                         struct expression *case_expr,
 515                                         struct range_list_stack **remaining_cases,
 516                                         struct state_list **raw_slist)
 517 {
 518         char *name = NULL;
 519         struct symbol *sym;
 520         struct sm_state *sm;
 521         struct sm_state *true_sm;
 522         struct state_list *true_states = NULL;
 523         struct state_list *false_states = NULL;
 524         struct state_list *ret = clone_slist(*raw_slist);
 525         long long val;
 526         struct data_range *range;
 527         struct range_list *vals = NULL;
 528
 529         name = get_variable_from_expr(switch_expr, &sym);
 530         if (!name || !sym)
 531                 goto free;
 532         sm = get_sm_state_slist(*raw_slist, SMATCH_EXTRA, name, sym);
 533         if (!case_expr) {
 534                 vals = top_range_list(*remaining_cases);
 535         } else {
 536                 if (!get_value(case_expr, &val)) {
 537                         goto free;
 538                 } else {
 539                         filter_top_range_list(remaining_cases, val);
 540                         range = alloc_range(val, val);
 541                         add_ptr_list(&vals, range);
 542                 }
 543         }
 544         if (sm)
 545                 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_slist, &true_states, &false_states);
 546
 547         true_sm = get_sm_state_slist(true_states, SMATCH_EXTRA, name, sym);
 548         if (!true_sm)
 549                 set_state_slist(&true_states, SMATCH_EXTRA, name, sym, alloc_extra_state_range_list(vals));
 550         overwrite_slist(true_states, &ret);
 551         free_slist(&true_states);
 552         free_slist(&false_states);
 553 free:
 554         free_string(name);
 555         return ret;
 556 }
 557
 558 static void match_end_func(struct symbol *sym)
 559 {
 560         print_count = 0;
 561 }
 562
 563 /*
 564  * get_implications() can be called by check_ scripts.
 565  */
 566 void get_implications(char *name, struct symbol *sym, int comparison, long long num,
 567                       struct state_list **true_states,
 568                       struct state_list **false_states)
 569 {
 570         struct sm_state *sm;
 571
 572         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 573         if (!sm)
 574                 return;
 575         if (slist_has_state(sm->possible, &undefined))
 576                 return;
 577         separate_and_filter(sm, comparison, tmp_range_list(num), LEFT, __get_cur_slist(), true_states, false_states);
 578 }
 579
 580 void __extra_match_condition(struct expression *expr);
 581 void register_implications(int id)
 582 {
 583         add_hook(&implied_states_hook, CONDITION_HOOK);
 584         add_hook(&__extra_match_condition, CONDITION_HOOK);
 585         add_hook(&match_end_func, END_FUNC_HOOK);
 586 }