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