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