2 * Copyright (C) 2008 Dan Carpenter.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
19 * Imagine we have this code:
26 * if (foo == 99) // <-- point #2
27 * bar->baz; // <-- point #3
30 * At point #3 bar is non null and can be dereferenced.
32 * It's smatch_implied.c which sets bar to non null at point #2.
34 * At point #1 merge_slist() stores the list of states from both
35 * the true and false paths. On the true path foo == 99 and on
36 * the false path foo == 1. merge_slist() sets their pool
37 * list to show the other states which were there when foo == 99.
39 * When it comes to the if (foo == 99) the smatch implied hook
40 * looks for all the pools where foo was not 99. It makes a list
43 * Then for bar (and all the other states) it says, ok bar is a
44 * merged state that came from these previous states. We'll
45 * chop out all the states where it came from a pool where
46 * foo != 99 and merge it all back together.
48 * That is the implied state of bar.
50 * merge_slist() sets up ->pool. An sm_state only has one ->pool and
51 * that is the pool where it was first set. The my pool gets set when
52 * code paths merge. States that have been set since the last merge do
54 * merge_sm_state() sets ->left and ->right. (These are the states which were
55 * merged to form the current state.)
56 * a pool: a pool is an slist that has been merged with another slist.
62 #include "smatch_slist.h"
63 #include "smatch_extra.h"
65 char *implied_debug_msg
;
66 #define DIMPLIED(msg...) do { if (option_debug_implied) printf(msg); } while (0)
68 int option_debug_implied
= 0;
69 int option_no_implied
= 0;
76 * It messes things up to free range list allocations. This helper fuction
77 * lets us reuse memory instead of doing new allocations.
79 static struct range_list
*tmp_range_list(long long num
)
81 static struct range_list
*my_list
= NULL
;
82 static struct data_range
*my_range
;
84 __free_ptr_list((struct ptr_list
**)&my_list
);
85 my_range
= alloc_range(ll_to_sval(num
), ll_to_sval(num
));
86 add_ptr_list(&my_list
, my_range
);
90 static void print_debug_tf(struct sm_state
*s
, int istrue
, int isfalse
)
92 if (!option_debug_implied
&& !option_debug
)
95 if (istrue
&& isfalse
) {
96 printf("'%s = %s' from %d does not exist.\n", s
->name
,
97 show_state(s
->state
), s
->line
);
99 printf("'%s = %s' from %d is true. [stree %d]\n", s
->name
, show_state(s
->state
),
100 s
->line
, get_stree_id(s
->pool
));
101 } else if (isfalse
) {
102 printf("'%s = %s' from %d is false. [stree %d]\n", s
->name
, show_state(s
->state
),
103 s
->line
, get_stree_id(s
->pool
));
105 printf("'%s = %s' from %d could be true or false. [stree %d]\n", s
->name
,
106 show_state(s
->state
), s
->line
, get_stree_id(s
->pool
));
111 * add_pool() adds a slist to *pools. If the slist has already been
112 * added earlier then it doesn't get added a second time.
114 void add_pool(struct stree_stack
**pools
, struct stree
*new)
118 FOR_EACH_PTR(*pools
, tmp
) {
121 else if (tmp
== new) {
124 INSERT_CURRENT(new, tmp
);
127 } END_FOR_EACH_PTR(tmp
);
128 add_ptr_list(pools
, new);
132 * If 'foo' == 99 add it that pool to the true pools. If it's false, add it to
133 * the false pools. If we're not sure, then we don't add it to either.
135 static void do_compare(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
137 struct stree_stack
**true_stack
,
138 struct stree_stack
**false_stack
)
144 struct range_list
*var_rl
;
149 if (is_implied(sm_state
)) {
150 s
= get_sm_state_stree(sm_state
->pool
,
151 sm_state
->owner
, sm_state
->name
,
158 if (option_debug_implied
|| option_debug
)
159 sm_msg("%s from %d, has borrowed implications.",
160 sm_state
->name
, sm_state
->line
);
164 type
= estate_type(sm_state
->state
);
165 if (type_positive_bits(rl_type(vals
)) > type_positive_bits(type
))
166 type
= rl_type(vals
);
167 if (type_positive_bits(type
) < 31)
169 var_rl
= cast_rl(type
, estate_rl(s
->state
));
170 vals
= cast_rl(type
, vals
);
173 istrue
= !possibly_false_rl(var_rl
, comparison
, vals
);
174 isfalse
= !possibly_true_rl(var_rl
, comparison
, vals
);
176 istrue
= !possibly_false_rl(vals
, comparison
, var_rl
);
177 isfalse
= !possibly_true_rl(vals
, comparison
, var_rl
);
180 print_debug_tf(s
, istrue
, isfalse
);
183 add_pool(true_stack
, s
->pool
);
186 add_pool(false_stack
, s
->pool
);
189 static int pool_in_pools(struct stree
*pool
,
190 const struct stree_stack
*pools
)
194 FOR_EACH_PTR(pools
, tmp
) {
199 } END_FOR_EACH_PTR(tmp
);
203 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
205 struct sm_state
*tmp
;
207 FOR_EACH_PTR(checked
, tmp
) {
210 } END_FOR_EACH_PTR(tmp
);
216 * Example code: if (foo == 99) {
218 * Say 'foo' is a merged state that has many possible values. It is the combination
219 * of merges. separate_pools() iterates through the pools recursively and calls
220 * do_compare() for each time 'foo' was set.
222 static void separate_pools(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
224 struct stree_stack
**true_stack
,
225 struct stree_stack
**false_stack
,
226 struct state_list
**checked
)
228 int free_checked
= 0;
229 struct state_list
*checked_states
= NULL
;
235 Sometimes the implications are just too big to deal with
236 so we bail. Theoretically, bailing out here can cause more false
237 positives but won't hide actual bugs.
239 if (sm_state
->nr_children
> 4000) {
240 if (option_debug
|| option_debug_implied
) {
241 static char buf
[1028];
242 snprintf(buf
, sizeof(buf
), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
243 sm_state
->nr_children
, sm_state
->name
, show_state(sm_state
->state
));
244 implied_debug_msg
= buf
;
249 if (checked
== NULL
) {
250 checked
= &checked_states
;
253 if (is_checked(*checked
, sm_state
))
255 add_ptr_list(checked
, sm_state
);
257 do_compare(sm_state
, comparison
, vals
, lr
, true_stack
, false_stack
);
259 separate_pools(sm_state
->left
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
260 separate_pools(sm_state
->right
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
265 struct sm_state
*filter_pools(struct sm_state
*sm
,
266 const struct stree_stack
*remove_stack
,
267 const struct stree_stack
*keep_stack
,
270 struct sm_state
*ret
= NULL
;
271 struct sm_state
*left
;
272 struct sm_state
*right
;
278 if (sm
->nr_children
> 4000) {
279 if (option_debug
|| option_debug_implied
) {
280 static char buf
[1028];
281 snprintf(buf
, sizeof(buf
), "debug: %s: nr_children over 4000 (%d). (%s %s)",
282 __func__
, sm
->nr_children
, sm
->name
, show_state(sm
->state
));
283 implied_debug_msg
= buf
;
288 if (pool_in_pools(sm
->pool
, remove_stack
)) {
289 DIMPLIED("removed %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
294 if (!is_merged(sm
) || pool_in_pools(sm
->pool
, keep_stack
)) {
295 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
299 DIMPLIED("checking %s from %d (%d) [stree %d] left = %s [stree %d] right = %s [stree %d]\n",
300 show_sm(sm
), sm
->line
, sm
->nr_children
, get_stree_id(sm
->pool
),
301 sm
->left
? show_sm(sm
->left
) : "<none>", sm
->left
? get_stree_id(sm
->left
->pool
) : -1,
302 sm
->right
? show_sm(sm
->right
) : "<none>", sm
->right
? get_stree_id(sm
->right
->pool
) : -1);
303 left
= filter_pools(sm
->left
, remove_stack
, keep_stack
, &removed
);
304 right
= filter_pools(sm
->right
, remove_stack
, keep_stack
, &removed
);
306 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
310 if (!left
&& !right
) {
311 DIMPLIED("removed %s from %d <none> [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
316 ret
= clone_sm(right
);
320 ret
->pool
= sm
->pool
;
322 ret
= clone_sm(left
);
326 ret
->pool
= sm
->pool
;
328 ret
= merge_sm_states(left
, right
);
329 ret
->pool
= sm
->pool
;
332 DIMPLIED("partial %s => ", show_sm(sm
));
333 DIMPLIED("%s from %d [stree %d]\n", show_sm(ret
), sm
->line
, get_stree_id(sm
->pool
));
337 static int highest_stree_id(struct sm_state
*sm
)
342 if (!sm
->left
&& !sm
->right
)
346 left
= get_stree_id(sm
->left
->pool
);
348 right
= get_stree_id(sm
->right
->pool
);
355 static struct stree
*filter_stack(struct sm_state
*gate_sm
,
356 struct stree
*pre_stree
,
357 const struct stree_stack
*remove_stack
,
358 const struct stree_stack
*keep_stack
)
360 struct stree
*ret
= NULL
;
361 struct sm_state
*tmp
;
362 struct sm_state
*filtered_sm
;
368 FOR_EACH_SM(pre_stree
, tmp
) {
371 if (highest_stree_id(tmp
) < highest_stree_id(gate_sm
)) {
372 DIMPLIED("skipping %s. set before. %d vs %d\n",
373 tmp
->name
, highest_stree_id(tmp
),
374 highest_stree_id(gate_sm
));
378 filtered_sm
= filter_pools(tmp
, remove_stack
, keep_stack
, &modified
);
379 if (filtered_sm
&& modified
) {
380 /* the assignments here are for borrowed implications */
381 filtered_sm
->name
= tmp
->name
;
382 filtered_sm
->sym
= tmp
->sym
;
383 avl_insert(&ret
, filtered_sm
);
388 } END_FOR_EACH_SM(tmp
);
392 static void separate_and_filter(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
394 struct stree
*pre_stree
,
395 struct stree
**true_states
,
396 struct stree
**false_states
)
398 struct stree_stack
*true_stack
= NULL
;
399 struct stree_stack
*false_stack
= NULL
;
400 struct timeval time_before
;
401 struct timeval time_after
;
403 gettimeofday(&time_before
, NULL
);
405 if (!is_merged(sm_state
)) {
406 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state
->name
);
410 if (option_debug_implied
|| option_debug
) {
412 sm_msg("checking implications: (%s %s %s)",
413 sm_state
->name
, show_special(comparison
), show_rl(vals
));
415 sm_msg("checking implications: (%s %s %s)",
416 show_rl(vals
), show_special(comparison
), sm_state
->name
);
419 separate_pools(sm_state
, comparison
, vals
, lr
, &true_stack
, &false_stack
, NULL
);
421 DIMPLIED("filtering true stack.\n");
422 *true_states
= filter_stack(sm_state
, pre_stree
, false_stack
, true_stack
);
423 DIMPLIED("filtering false stack.\n");
424 *false_states
= filter_stack(sm_state
, pre_stree
, true_stack
, false_stack
);
425 free_stree_stack(&true_stack
);
426 free_stree_stack(&false_stack
);
427 if (option_debug_implied
|| option_debug
) {
428 printf("These are the implied states for the true path:\n");
429 __print_stree(*true_states
);
430 printf("These are the implied states for the false path:\n");
431 __print_stree(*false_states
);
434 gettimeofday(&time_after
, NULL
);
435 if (time_after
.tv_sec
- time_before
.tv_sec
> 7)
436 __bail_on_rest_of_function
= 1;
439 static struct expression
*get_left_most_expr(struct expression
*expr
)
441 expr
= strip_expr(expr
);
442 if (expr
->type
== EXPR_ASSIGNMENT
)
443 return get_left_most_expr(expr
->left
);
447 static int is_merged_expr(struct expression
*expr
)
452 if (get_value(expr
, &dummy
))
454 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
462 static void delete_equiv_stree(struct stree
**stree
, const char *name
, struct symbol
*sym
)
464 struct smatch_state
*state
;
465 struct relation
*rel
;
467 state
= get_state(SMATCH_EXTRA
, name
, sym
);
468 if (!estate_related(state
)) {
469 delete_state_stree(stree
, SMATCH_EXTRA
, name
, sym
);
473 FOR_EACH_PTR(estate_related(state
), rel
) {
474 delete_state_stree(stree
, SMATCH_EXTRA
, rel
->name
, rel
->sym
);
475 } END_FOR_EACH_PTR(rel
);
478 static void handle_comparison(struct expression
*expr
,
479 struct stree
**implied_true
,
480 struct stree
**implied_false
)
482 struct sm_state
*sm
= NULL
;
483 struct range_list
*ranges
= NULL
;
484 struct expression
*left
;
485 struct expression
*right
;
488 left
= get_left_most_expr(expr
->left
);
489 right
= get_left_most_expr(expr
->right
);
491 if (is_merged_expr(left
)) {
493 sm
= get_sm_state_expr(SMATCH_EXTRA
, left
);
494 get_implied_rl(right
, &ranges
);
495 } else if (is_merged_expr(right
)) {
497 sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
498 get_implied_rl(left
, &ranges
);
501 if (!ranges
|| !sm
) {
506 separate_and_filter(sm
, expr
->op
, ranges
, lr
, __get_cur_stree(), implied_true
, implied_false
);
508 delete_equiv_stree(implied_true
, sm
->name
, sm
->sym
);
509 delete_equiv_stree(implied_false
, sm
->name
, sm
->sym
);
512 static void handle_zero_comparison(struct expression
*expr
,
513 struct stree
**implied_true
,
514 struct stree
**implied_false
)
520 if (expr
->type
== EXPR_POSTOP
)
521 expr
= strip_expr(expr
->unop
);
523 if (expr
->type
== EXPR_ASSIGNMENT
) {
524 /* most of the time ->pools will be empty here because we
525 just set the state, but if have assigned a conditional
526 function there are implications. */
530 name
= expr_to_var_sym(expr
, &sym
);
533 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
537 separate_and_filter(sm
, SPECIAL_NOTEQUAL
, tmp_range_list(0), LEFT
, __get_cur_stree(), implied_true
, implied_false
);
538 delete_equiv_stree(implied_true
, name
, sym
);
539 delete_equiv_stree(implied_false
, name
, sym
);
544 static int handled_by_implied_hook(struct expression
*expr
,
545 struct stree
**implied_true
,
546 struct stree
**implied_false
)
548 struct stree_stack
*true_stack
= NULL
;
549 struct stree_stack
*false_stack
= NULL
;
550 struct stree
*pre_stree
;
553 sm
= comparison_implication_hook(expr
, &true_stack
, &false_stack
);
555 sm
= stored_condition_implication_hook(expr
, &true_stack
, &false_stack
);
559 pre_stree
= clone_stree(__get_cur_stree());
561 *implied_true
= filter_stack(sm
, pre_stree
, false_stack
, true_stack
);
562 *implied_false
= filter_stack(sm
, pre_stree
, true_stack
, false_stack
);
564 free_stree(&pre_stree
);
565 free_stree_stack(&true_stack
);
566 free_stree_stack(&false_stack
);
571 static void get_tf_states(struct expression
*expr
,
572 struct stree
**implied_true
,
573 struct stree
**implied_false
)
575 if (handled_by_implied_hook(expr
, implied_true
, implied_false
))
578 if (expr
->type
== EXPR_COMPARE
)
579 handle_comparison(expr
, implied_true
, implied_false
);
581 handle_zero_comparison(expr
, implied_true
, implied_false
);
584 static struct stree
*saved_implied_true
;
585 static struct stree
*saved_implied_false
;
587 static void save_implications_hook(struct expression
*expr
)
589 if (option_no_implied
)
591 get_tf_states(expr
, &saved_implied_true
, &saved_implied_false
);
594 static void set_implied_states(struct expression
*expr
)
598 FOR_EACH_SM(saved_implied_true
, sm
) {
599 if (!get_state_stree(saved_implied_false
, sm
->owner
, sm
->name
, sm
->sym
)) {
600 struct sm_state
*orig
;
602 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
603 set_state_stree(&saved_implied_false
, sm
->owner
, sm
->name
, sm
->sym
, orig
->state
);
605 } END_FOR_EACH_SM(sm
);
607 FOR_EACH_SM(saved_implied_false
, sm
) {
608 if (!get_state_stree(saved_implied_true
, sm
->owner
, sm
->name
, sm
->sym
)) {
609 struct sm_state
*orig
;
611 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
612 set_state_stree(&saved_implied_true
, sm
->owner
, sm
->name
, sm
->sym
, orig
->state
);
614 } END_FOR_EACH_SM(sm
);
616 FOR_EACH_SM(saved_implied_true
, sm
) {
617 __set_true_false_sm(sm
, NULL
);
618 } END_FOR_EACH_SM(sm
);
619 free_stree(&saved_implied_true
);
621 FOR_EACH_SM(saved_implied_false
, sm
) {
622 __set_true_false_sm(NULL
, sm
);
623 } END_FOR_EACH_SM(sm
);
624 free_stree(&saved_implied_false
);
627 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
631 struct smatch_state
*state
;
632 struct range_list
*ret
= NULL
;
634 name
= expr_to_var_sym(switch_expr
, &sym
);
637 state
= get_state(SMATCH_EXTRA
, name
, sym
);
640 ret
= clone_rl(estate_rl(state
));
646 type
= get_type(switch_expr
);
647 ret
= alloc_rl(sval_type_min(type
), sval_type_max(type
));
652 struct stree
*__implied_case_stree(struct expression
*switch_expr
,
653 struct expression
*case_expr
,
654 struct range_list_stack
**remaining_cases
,
655 struct stree
**raw_stree
)
660 struct stree
*true_states
= NULL
;
661 struct stree
*false_states
= NULL
;
662 struct stree
*extra_states
= NULL
;
663 struct stree
*ret
= clone_stree(*raw_stree
);
665 struct range_list
*vals
= NULL
;
667 name
= expr_to_var_sym(switch_expr
, &sym
);
670 sm
= get_sm_state_stree(*raw_stree
, SMATCH_EXTRA
, name
, sym
);
673 if (get_value(case_expr
, &sval
)) {
674 filter_top_rl(remaining_cases
, sval
);
675 add_range(&vals
, sval
, sval
);
677 vals
= clone_rl(top_rl(*remaining_cases
));
680 vals
= top_rl(*remaining_cases
);
684 separate_and_filter(sm
, SPECIAL_EQUAL
, vals
, LEFT
, *raw_stree
, &true_states
, &false_states
);
686 __push_fake_cur_stree();
688 set_extra_nomod(name
, sym
, alloc_estate_rl(vals
));
689 extra_states
= __pop_fake_cur_stree();
690 overwrite_stree(extra_states
, &true_states
);
691 overwrite_stree(true_states
, &ret
);
692 free_stree(&extra_states
);
693 free_stree(&true_states
);
694 free_stree(&false_states
);
700 static void match_end_func(struct symbol
*sym
)
704 implied_debug_msg
= NULL
;
707 static int sm_state_in_slist(struct sm_state
*sm
, struct state_list
*slist
)
709 struct sm_state
*tmp
;
711 FOR_EACH_PTR(slist
, tmp
) {
714 } END_FOR_EACH_PTR(tmp
);
719 * The situation is we have a SMATCH_EXTRA state and we want to break it into
720 * each of the ->possible states and find the implications of each. The caller
721 * has to use __push_fake_cur_stree() to preserve the correct states so they
722 * can be restored later.
724 void overwrite_states_using_pool(struct sm_state
*sm
)
726 struct sm_state
*old
;
727 struct sm_state
*new;
732 FOR_EACH_SM(sm
->pool
, old
) {
733 new = get_sm_state(old
->owner
, old
->name
, old
->sym
);
734 if (!new) /* the variable went out of scope */
736 if (sm_state_in_slist(old
, new->possible
))
737 set_state(old
->owner
, old
->name
, old
->sym
, old
->state
);
738 } END_FOR_EACH_SM(old
);
741 void __extra_match_condition(struct expression
*expr
);
742 void __comparison_match_condition(struct expression
*expr
);
743 void __stored_condition(struct expression
*expr
);
744 void register_implications(int id
)
746 add_hook(&save_implications_hook
, CONDITION_HOOK
);
747 add_hook(&set_implied_states
, CONDITION_HOOK
);
748 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
749 add_hook(&__comparison_match_condition
, CONDITION_HOOK
);
750 add_hook(&__stored_condition
, CONDITION_HOOK
);
751 add_hook(&match_end_func
, END_FUNC_HOOK
);