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