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