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