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