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_pools
  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_pools.
  43  * merge_sm_state() sets ->pre_merge.
  44  * If an sm_state is not the same on both sides of a merge, it
  45  *    gets a ->my_pool set for both sides.  The result is a merged
  46  *    state that has it's ->pre_merge pointers set.  Merged states
  47  *    do not immediately have any my_pools set, but maybe will later
  48  *    when they themselves are merged.
  49  * A pool is a list of all the states that were set at the time.
  50  */
  51
  52 #include "smatch.h"
  53 #include "smatch_slist.h"
  54 #include "smatch_extra.h"
  55
  56 int debug_implied_states = 0;
  57 int option_no_implied = 0;
  58
  59 static int print_once = 0;
  60
  61 static int pool_in_pools(struct state_list *pool,
  62                         struct state_list_stack *pools)
  63 {
  64         struct state_list *tmp;
  65
  66         FOR_EACH_PTR(pools, tmp) {
  67                 if (tmp == pool)
  68                         return 1;
  69                 if (tmp > pool)
  70                         return 0;
  71         } END_FOR_EACH_PTR(tmp);
  72         return 0;
  73 }
  74
  75 struct sm_state *remove_my_pools(struct sm_state *sm,
  76                                 struct state_list_stack *pools, int *modified)
  77 {
  78         struct sm_state *ret = NULL;
  79         struct sm_state *left;
  80         struct sm_state *right;
  81         int removed = 0;
  82
  83         if (!sm)
  84                 return NULL;
  85
  86         if (sm->nr_children > 5000) {
  87                 if (!print_once++) {
  88                         smatch_msg("debug: remove_my_pools %s nr_children %d",
  89                                 sm->name, sm->nr_children);
  90                 }
  91                 return NULL;
  92         }
  93
  94         if (pool_in_pools(sm->my_pool, pools)) {
  95                 DIMPLIED("removed %s = %s from %d\n", sm->name,
  96                         show_state(sm->state), sm->line);
  97                 *modified = 1;
  98                 return NULL;
  99         }
 100
 101         if (!is_merged(sm)) {
 102                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state),
 103                         sm->line);
 104                 return sm;
 105         }
 106
 107         DIMPLIED("checking %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 108         left = remove_my_pools(sm->pre_left, pools, &removed);
 109         right = remove_my_pools(sm->pre_right, pools, &removed);
 110         if (!removed) {
 111                 DIMPLIED("kept %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 112                 return sm;
 113         }
 114         *modified = 1;
 115         if (!left && !right) {
 116                 DIMPLIED("removed %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 117                 return NULL;
 118         }
 119
 120         if (!left) {
 121                 ret = clone_state(right);
 122                 ret->merged = 1;
 123                 ret->pre_right = right;
 124                 ret->pre_left = NULL;
 125                 ret->my_pool = sm->my_pool;
 126         } else if (!right) {
 127                 ret = clone_state(left);
 128                 ret->merged = 1;
 129                 ret->pre_left = left;
 130                 ret->pre_right = NULL;
 131                 ret->my_pool = sm->my_pool;
 132         } else {
 133                 ret = merge_sm_states(left, right);
 134                 ret->my_pool = sm->my_pool;
 135         }
 136         ret->implied = 1;
 137         DIMPLIED("partial %s = %s from %d\n", sm->name, show_state(sm->state), sm->line);
 138         return ret;
 139 }
 140
 141 static struct state_list *filter_stack(struct state_list *pre_list,
 142                                 struct state_list_stack *stack)
 143 {
 144         struct state_list *ret = NULL;
 145         struct sm_state *tmp;
 146         struct sm_state *filtered_state;
 147         int modified;
 148         int counter = 0;
 149
 150         if (!stack)
 151                 return NULL;
 152
 153         FOR_EACH_PTR(pre_list, tmp) {
 154                 modified = 0;
 155                 filtered_state = remove_my_pools(tmp, stack, &modified);
 156                 if (filtered_state && modified) {
 157                         add_ptr_list(&ret, filtered_state);
 158                         if ((counter++)%10 && out_of_memory())
 159                                 return NULL;
 160
 161                 }
 162         } END_FOR_EACH_PTR(tmp);
 163         return ret;
 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 static void separate_pools(struct sm_state *sm_state, int comparison, int num,
 178                         int left,
 179                         struct state_list_stack **true_stack,
 180                         struct state_list_stack **false_stack,
 181                         struct state_list **checked)
 182 {
 183         struct sm_state *s;
 184         int istrue, isfalse;
 185         int free_checked = 0;
 186         struct state_list *checked_states = NULL;
 187
 188         if (!sm_state)
 189                 return;
 190
 191         /*
 192            Sometimes the implications are just too big to deal with
 193            so we bail.  Theoretically, implications only get rid of
 194            false positives and don't affect actual bugs.
 195         */
 196         if (sm_state->nr_children > 5000) {
 197                 if (!print_once) {
 198                         smatch_msg("debug: seperate_pools %s nr_children %d",
 199                                 sm_state->name, sm_state->nr_children);
 200                 }
 201                 return;
 202         }
 203
 204         if (checked == NULL) {
 205                 checked = &checked_states;
 206                 free_checked = 1;
 207         }
 208         if (is_checked(*checked, sm_state)) {
 209                 return;
 210         }
 211         add_ptr_list(checked, sm_state);
 212
 213         if (sm_state->my_pool) {
 214                 if (is_implied(sm_state)) {
 215                         s = get_sm_state_slist(sm_state->my_pool,
 216                                         sm_state->name, sm_state->owner,
 217                                         sm_state->sym);
 218                 } else {
 219                         s = sm_state;
 220                 }
 221
 222                 istrue = !possibly_false(comparison,
 223                                         (struct data_info *)s->state->data, num,
 224                                         left);
 225                 isfalse = !possibly_true(comparison,
 226                                         (struct data_info *)s->state->data,
 227                                         num, left);
 228
 229                 if (debug_implied_states || debug_states) {
 230                         if (istrue && isfalse) {
 231                                 printf("'%s = %s' from %d does not exist.\n",
 232                                         s->name, show_state(s->state),
 233                                         s->line);
 234                         } else if (istrue) {
 235                                 printf("'%s = %s' from %d is true.\n",
 236                                         s->name, show_state(s->state),
 237                                         s->line);
 238                         } else if (isfalse) {
 239                                 printf("'%s = %s' from %d is false.\n",
 240                                         s->name, show_state(s->state),
 241                                         s->line);
 242                         } else {
 243                                 printf("'%s = %s' from %d could be true or "
 244                                         "false.\n", s->name,
 245                                         show_state(s->state), s->line);
 246                         }
 247                 }
 248                 if (istrue) {
 249                         add_pool(true_stack, s->my_pool);
 250                 }
 251                 if (isfalse) {
 252                         add_pool(false_stack, s->my_pool);
 253                 }
 254         }
 255         separate_pools(sm_state->pre_left, comparison, num, left, true_stack, false_stack, checked);
 256         separate_pools(sm_state->pre_right, comparison, num, left, true_stack, false_stack, checked);
 257         if (free_checked)
 258                 free_slist(checked);
 259 }
 260
 261 static void get_eq_neq(struct sm_state *sm_state, int comparison, int num,
 262                 int left,
 263                 struct state_list *pre_list,
 264                 struct state_list **true_states,
 265                 struct state_list **false_states)
 266 {
 267         struct state_list_stack *true_stack = NULL;
 268         struct state_list_stack *false_stack = NULL;
 269
 270         if (debug_implied_states || debug_states) {
 271                 if (left)
 272                         smatch_msg("checking implications: (%s %s %d)",
 273                                 sm_state->name, show_special(comparison), num);
 274                 else
 275                         smatch_msg("checking implications: (%d %s %s)",
 276                                 num, show_special(comparison), sm_state->name);
 277         }
 278
 279         separate_pools(sm_state, comparison, num, left, &true_stack, &false_stack, NULL);
 280
 281         DIMPLIED("filtering true stack.\n");
 282         *true_states = filter_stack(pre_list, false_stack);
 283         DIMPLIED("filtering false stack.\n");
 284         *false_states = filter_stack(pre_list, true_stack);
 285         free_stack(&true_stack);
 286         free_stack(&false_stack);
 287         if (debug_implied_states || debug_states) {
 288                 printf("These are the implied states for the true path:\n");
 289                 __print_slist(*true_states);
 290                 printf("These are the implied states for the false path:\n");
 291                 __print_slist(*false_states);
 292         }
 293 }
 294
 295 static char *get_implication_variable(struct expression *expr, struct symbol **symp)
 296 {
 297         expr = strip_expr(expr);
 298         if (expr->type == EXPR_ASSIGNMENT)
 299                 return get_implication_variable(expr->left, symp);
 300         return get_variable_from_expr(expr, symp);
 301 }
 302
 303 static void handle_comparison(struct expression *expr,
 304                               struct state_list **implied_true,
 305                               struct state_list **implied_false)
 306 {
 307         struct symbol *sym;
 308         char *name;
 309         struct sm_state *state;
 310         int value;
 311         int left = 0;
 312
 313         value = get_value(expr->left);
 314         if (value == UNDEFINED) {
 315                 value = get_value(expr->right);
 316                 if (value == UNDEFINED)
 317                         return;
 318                 left = 1;
 319         }
 320         if (left)
 321                 name = get_implication_variable(expr->left, &sym);
 322         else
 323                 name = get_implication_variable(expr->right, &sym);
 324         if (!name || !sym)
 325                 goto free;
 326         state = get_sm_state(name, SMATCH_EXTRA, sym);
 327         if (!state)
 328                 goto free;
 329         if (!is_merged(state)) {
 330                 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), state->name);
 331                 goto free;
 332         }
 333         get_eq_neq(state, expr->op, value, left, __get_cur_slist(), implied_true, implied_false);
 334         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 335         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 336 free:
 337         free_string(name);
 338 }
 339
 340 static void get_tf_states(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 *state;
 347
 348         if (expr->type == EXPR_COMPARE) {
 349                 handle_comparison(expr, implied_true, implied_false);
 350                 return;
 351         }
 352         if (expr->type == EXPR_ASSIGNMENT) {
 353                 /* most of the time ->my_pools will be empty here because we
 354                    just set the state, but if have assigned a conditional
 355                    function there are implications. */
 356                 expr = expr->left;
 357         }
 358
 359         name = get_variable_from_expr(expr, &sym);
 360         if (!name || !sym)
 361                 goto free;
 362         state = get_sm_state(name, SMATCH_EXTRA, sym);
 363         if (!state)
 364                 goto free;
 365         if (!is_merged(state)) {
 366                 DIMPLIED("%d '%s' has no pools.\n", get_lineno(), state->name);
 367                 goto free;
 368         }
 369         get_eq_neq(state, SPECIAL_NOTEQUAL, 0, 1, __get_cur_slist(), implied_true, implied_false);
 370         delete_state_slist(implied_true, name, SMATCH_EXTRA, sym);
 371         delete_state_slist(implied_false, name, SMATCH_EXTRA, sym);
 372 free:
 373         free_string(name);
 374 }
 375
 376 static void implied_states_hook(struct expression *expr)
 377 {
 378         struct sm_state *state;
 379         struct state_list *implied_true = NULL;
 380         struct state_list *implied_false = NULL;
 381
 382         if (option_no_implied)
 383                 return;
 384
 385         get_tf_states(expr, &implied_true, &implied_false);
 386
 387         FOR_EACH_PTR(implied_true, state) {
 388                 __set_true_false_sm(state, NULL);
 389         } END_FOR_EACH_PTR(state);
 390         free_slist(&implied_true);
 391
 392         FOR_EACH_PTR(implied_false, state) {
 393                 __set_true_false_sm(NULL, state);
 394         } END_FOR_EACH_PTR(state);
 395         free_slist(&implied_false);
 396 }
 397
 398 void get_implications(char *name, struct symbol *sym, int comparison, int num,
 399                       struct state_list **true_states,
 400                       struct state_list **false_states)
 401 {
 402         struct sm_state *sm;
 403
 404         sm = get_sm_state(name, SMATCH_EXTRA, sym);
 405         if (!sm)
 406                 return;
 407         if (slist_has_state(sm->possible, &undefined))
 408                 return;
 409         get_eq_neq(sm, comparison, num, 1, __get_cur_slist(), true_states, false_states);
 410 }
 411
 412 struct state_list *__implied_case_slist(struct expression *switch_expr,
 413                                         struct expression *case_expr,
 414                                         struct state_list **raw_slist)
 415 {
 416         char *name = NULL;
 417         struct symbol *sym;
 418         struct sm_state *sm;
 419         struct sm_state *true_sm;
 420         struct sm_state *false_sm;
 421         struct state_list *true_states = NULL;
 422         struct state_list *false_states = NULL;
 423         struct state_list *ret = clone_slist(*raw_slist);
 424         long long val;
 425
 426         if (!case_expr)
 427                 return ret;
 428         name = get_variable_from_expr(switch_expr, &sym);
 429         if (!name || !sym)
 430                 goto free;
 431         sm = get_sm_state_slist(*raw_slist, name, SMATCH_EXTRA, sym);
 432         val = get_value(case_expr);
 433         if (val == UNDEFINED)
 434                 goto free;
 435         if (sm) {
 436                 get_eq_neq(sm, SPECIAL_EQUAL, val, 1, *raw_slist, &true_states, &false_states);
 437         }
 438
 439         true_sm = get_sm_state_slist(true_states, name, SMATCH_EXTRA, sym);
 440         if (!true_sm)
 441                 set_state_slist(&true_states, name, SMATCH_EXTRA, sym, alloc_extra_state(val));
 442         false_sm = get_sm_state_slist(false_states, name, SMATCH_EXTRA, sym);
 443         if (!false_sm)
 444                 set_state_slist(&false_states, name, SMATCH_EXTRA, sym, add_filter(sm?sm->state:NULL, val));
 445         overwrite_slist(false_states, raw_slist);
 446         overwrite_slist(true_states, &ret);
 447         free_slist(&true_states);
 448         free_slist(&false_states);
 449 free:
 450         free_string(name);
 451         return ret;
 452 }
 453
 454 static void clear_print_once(struct symbol *sym)
 455 {
 456         print_once = 0;
 457 }
 458
 459 void __extra_match_condition(struct expression *expr);
 460 void register_implications(int id)
 461 {
 462         add_hook(&implied_states_hook, CONDITION_HOOK);
 463         add_hook(&__extra_match_condition, CONDITION_HOOK);
 464         add_hook(&clear_print_once, END_FUNC_HOOK);
 465 }