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 = %s from %d\n", sm->name,
 243                         show_state(sm->state), sm->line);
 244                 *modified = 1;
 245                 return NULL;
 246         }
 247
 248         if (!is_merged(sm)) {
 249                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state),
 250                         sm->line);
 251                 return sm;
 252         }
 253
 254         DIMPLIED("checking %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 255         left = remove_my_pools(sm->left, pools, &removed);
 256         right = remove_my_pools(sm->right, pools, &removed);
 257         if (!removed) {
 258                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 259                 return sm;
 260         }
 261         *modified = 1;
 262         if (!left && !right) {
 263                 DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 264                 return NULL;
 265         }
 266
 267         if (!left) {
 268                 ret = clone_sm(right);
 269                 ret->merged = 1;
 270                 ret->right = right;
 271                 ret->left = NULL;
 272                 ret->my_pool = sm->my_pool;
 273         } else if (!right) {
 274                 ret = clone_sm(left);
 275                 ret->merged = 1;
 276                 ret->left = left;
 277                 ret->right = NULL;
 278                 ret->my_pool = sm->my_pool;
 279         } else {
 280                 ret = merge_sm_states(left, right);
 281                 ret->my_pool = sm->my_pool;
 282         }
 283         ret->implied = 1;
 284         DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 285         return ret;
 286 }
 287
 288 static struct state_list *filter_stack(struct state_list *pre_list,
 289                                 struct state_list_stack *stack)
 290 {
 291         struct state_list *ret = NULL;
 292         struct sm_state *tmp;
 293         struct sm_state *filtered_sm;
 294         int modified;
 295
 296         if (!stack)
 297                 return NULL;
 298
 299         FOR_EACH_PTR(pre_list, tmp) {
 300                 modified = 0;
 301                 filtered_sm = remove_my_pools(tmp, stack, &modified);
 302                 if (filtered_sm && modified) {
 303                         filtered_sm->name = tmp->name;
 304                         filtered_sm->sym = tmp->sym;
 305                         add_ptr_list(&ret, filtered_sm);
 306                         if (out_of_memory())
 307                                 return NULL;
 308
 309                 }
 310         } END_FOR_EACH_PTR(tmp);
 311         return ret;
 312 }
 313
 314 static void separate_and_filter(struct sm_state *sm_state, int comparison, struct range_list *vals,
 315                 int lr,
 316                 struct state_list *pre_list,
 317                 struct state_list **true_states,
 318                 struct state_list **false_states)
 319 {
 320         struct state_list_stack *true_stack = NULL;
 321         struct state_list_stack *false_stack = NULL;
 322         struct timeval time_before;
 323         struct timeval time_after;
 324
 325         gettimeofday(&time_before, NULL);
 326
 327         if (!is_merged(sm_state)) {
 328                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state->name);
 329                 return;
 330         }
 331
 332         if (option_debug_implied || option_debug) {
 333                 if (lr == LEFT)
 334                         sm_msg("checking implications: (%s %s %s)",
 335                                 sm_state->name, show_special(comparison), show_ranges(vals));
 336                 else
 337                         sm_msg("checking implications: (%s %s %s)",
 338                                 show_ranges(vals), show_special(comparison), sm_state->name);
 339         }
 340
 341         separate_pools(sm_state, comparison, vals, lr, &true_stack, &false_stack, NULL);
 342
 343         DIMPLIED("filtering true stack.\n");
 344         *true_states = filter_stack(pre_list, false_stack);
 345         DIMPLIED("filtering false stack.\n");
 346         *false_states = filter_stack(pre_list, true_stack);
 347         free_stack(&true_stack);
 348         free_stack(&false_stack);
 349         if (option_debug_implied || option_debug) {
 350                 printf("These are the implied states for the true path:\n");
 351                 __print_slist(*true_states);
 352                 printf("These are the implied states for the false path:\n");
 353                 __print_slist(*false_states);
 354         }
 355
 356         gettimeofday(&time_after, NULL);
 357         if (time_after.tv_sec - time_before.tv_sec > 7)
 358                 __bail_on_rest_of_function = 1;
 359 }
 360
 361 static struct expression *get_left_most_expr(struct expression *expr)
 362 {
 363         expr = strip_expr(expr);
 364         if (expr->type == EXPR_ASSIGNMENT)
 365                 return get_left_most_expr(expr->left);
 366         return expr;
 367 }
 368
 369 static int is_merged_expr(struct expression  *expr)
 370 {
 371         struct sm_state *sm;
 372         long long dummy;
 373
 374         if (get_value(expr, &dummy))
 375                 return 0;
 376         sm = get_sm_state_expr(SMATCH_EXTRA, expr);
 377         if (!sm)
 378                 return 0;
 379         if (is_merged(sm))
 380                 return 1;
 381         return 0;
 382 }
 383
 384 static void delete_equiv_slist(struct state_list **slist, const char *name, struct symbol *sym)
 385 {
 386         struct smatch_state *state;
 387         struct relation *rel;
 388
 389         state = get_state(SMATCH_EXTRA, name, sym);
 390         if (!estate_related(state)) {
 391                 delete_state_slist(slist, SMATCH_EXTRA, name, sym);
 392                 return;
 393         }
 394
 395         FOR_EACH_PTR(estate_related(state), rel) {
 396                 delete_state_slist(slist, SMATCH_EXTRA, rel->name, rel->sym);
 397         } END_FOR_EACH_PTR(rel);
 398 }
 399
 400 static void handle_comparison(struct expression *expr,
 401                               struct state_list **implied_true,
 402                               struct state_list **implied_false)
 403 {
 404         struct sm_state *sm = NULL;
 405         struct range_list *ranges = NULL;
 406         struct expression *left;
 407         struct expression *right;
 408         int lr;
 409
 410         left = get_left_most_expr(expr->left);
 411         right = get_left_most_expr(expr->right);
 412
 413         if (is_merged_expr(left)) {
 414                 lr = LEFT;
 415                 sm = get_sm_state_expr(SMATCH_EXTRA, left);
 416                 get_implied_range_list(right, &ranges);
 417         } else if (is_merged_expr(right)) {
 418                 lr = RIGHT;
 419                 sm = get_sm_state_expr(SMATCH_EXTRA, right);
 420                 get_implied_range_list(left, &ranges);
 421         }
 422
 423         if (!ranges || !sm) {
 424                 free_range_list(&ranges);
 425                 return;
 426         }
 427
 428         separate_and_filter(sm, expr->op, ranges, lr, __get_cur_slist(), implied_true, implied_false);
 429         free_range_list(&ranges);
 430         delete_equiv_slist(implied_true, sm->name, sm->sym);
 431         delete_equiv_slist(implied_false, sm->name, sm->sym);
 432 }
 433
 434 static void handle_zero_comparison(struct expression *expr,
 435                                 struct state_list **implied_true,
 436                                 struct state_list **implied_false)
 437 {
 438         struct symbol *sym;
 439         char *name;
 440         struct sm_state *sm;
 441
 442         if (expr->type == EXPR_POSTOP)
 443                 expr = strip_expr(expr->unop);
 444
 445         if (expr->type == EXPR_ASSIGNMENT) {
 446                 /* most of the time ->my_pools will be empty here because we
 447                    just set the state, but if have assigned a conditional
 448                    function there are implications. */
 449                 expr = expr->left;
 450         }
 451
 452         name = get_variable_from_expr(expr, &sym);
 453         if (!name || !sym)
 454                 goto free;
 455         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 456         if (!sm)
 457                 goto free;
 458
 459         separate_and_filter(sm, SPECIAL_NOTEQUAL, tmp_range_list(0), LEFT, __get_cur_slist(), implied_true, implied_false);
 460         delete_equiv_slist(implied_true, name, sym);
 461         delete_equiv_slist(implied_false, name, sym);
 462 free:
 463         free_string(name);
 464 }
 465
 466 static void get_tf_states(struct expression *expr,
 467                           struct state_list **implied_true,
 468                           struct state_list **implied_false)
 469 {
 470         if (expr->type == EXPR_COMPARE)
 471                 handle_comparison(expr, implied_true, implied_false);
 472         else
 473                 handle_zero_comparison(expr, implied_true, implied_false);
 474 }
 475
 476 static void implied_states_hook(struct expression *expr)
 477 {
 478         struct sm_state *sm;
 479         struct state_list *implied_true = NULL;
 480         struct state_list *implied_false = NULL;
 481
 482         if (option_no_implied)
 483                 return;
 484
 485         get_tf_states(expr, &implied_true, &implied_false);
 486
 487         FOR_EACH_PTR(implied_true, sm) {
 488                 __set_true_false_sm(sm, NULL);
 489         } END_FOR_EACH_PTR(sm);
 490         free_slist(&implied_true);
 491
 492         FOR_EACH_PTR(implied_false, sm) {
 493                 __set_true_false_sm(NULL, sm);
 494         } END_FOR_EACH_PTR(sm);
 495         free_slist(&implied_false);
 496 }
 497
 498 struct range_list *__get_implied_values(struct expression *switch_expr)
 499 {
 500         char *name;
 501         struct symbol *sym;
 502         struct smatch_state *state;
 503         struct range_list *ret = NULL;
 504
 505         name = get_variable_from_expr(switch_expr, &sym);
 506         if (!name || !sym)
 507                 goto free;
 508         state = get_state(SMATCH_EXTRA, name, sym);
 509         if (!state)
 510                 goto free;
 511         ret = clone_range_list(estate_ranges(state));
 512 free:
 513         free_string(name);
 514         if (!ret)
 515                 add_range(&ret, whole_range.min, whole_range.max);
 516         return ret;
 517 }
 518
 519 struct state_list *__implied_case_slist(struct expression *switch_expr,
 520                                         struct expression *case_expr,
 521                                         struct range_list_stack **remaining_cases,
 522                                         struct state_list **raw_slist)
 523 {
 524         char *name = NULL;
 525         struct symbol *sym;
 526         struct sm_state *sm;
 527         struct sm_state *true_sm;
 528         struct state_list *true_states = NULL;
 529         struct state_list *false_states = NULL;
 530         struct state_list *ret = clone_slist(*raw_slist);
 531         long long val;
 532         struct range_list *vals = NULL;
 533
 534         name = get_variable_from_expr(switch_expr, &sym);
 535         if (!name || !sym)
 536                 goto free;
 537         sm = get_sm_state_slist(*raw_slist, SMATCH_EXTRA, name, sym);
 538         if (!case_expr) {
 539                 vals = top_range_list(*remaining_cases);
 540         } else {
 541                 if (!get_value(case_expr, &val))
 542                         goto free;
 543
 544                 filter_top_range_list(remaining_cases, val);
 545                 add_range(&vals, val, val);
 546         }
 547         if (sm)
 548                 separate_and_filter(sm, SPECIAL_EQUAL, vals, LEFT, *raw_slist, &true_states, &false_states);
 549
 550         true_sm = get_sm_state_slist(true_states, SMATCH_EXTRA, name, sym);
 551         if (!true_sm)
 552                 set_state_slist(&true_states, SMATCH_EXTRA, name, sym, alloc_estate_range_list(vals));
 553         overwrite_slist(true_states, &ret);
 554         free_slist(&true_states);
 555         free_slist(&false_states);
 556 free:
 557         free_string(name);
 558         return ret;
 559 }
 560
 561 static void match_end_func(struct symbol *sym)
 562 {
 563         implied_debug_msg = NULL;
 564 }
 565
 566 /*
 567  * get_implications() can be called by check_ scripts.
 568  */
 569 void get_implications(char *name, struct symbol *sym, int comparison, long long num,
 570                       struct state_list **true_states,
 571                       struct state_list **false_states)
 572 {
 573         struct sm_state *sm;
 574
 575         sm = get_sm_state(SMATCH_EXTRA, name, sym);
 576         if (!sm)
 577                 return;
 578         if (slist_has_state(sm->possible, &undefined))
 579                 return;
 580         separate_and_filter(sm, comparison, tmp_range_list(num), LEFT, __get_cur_slist(), true_states, false_states);
 581 }
 582
 583 void __extra_match_condition(struct expression *expr);
 584 void register_implications(int id)
 585 {
 586         add_hook(&implied_states_hook, CONDITION_HOOK);
 587         add_hook(&__extra_match_condition, CONDITION_HOOK);
 588         add_hook(&match_end_func, END_FUNC_HOOK);
 589 }