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
)
147 if (is_implied(sm_state
)) {
148 s
= get_sm_state_stree(sm_state
->pool
,
149 sm_state
->owner
, sm_state
->name
,
156 if (option_debug_implied
|| option_debug
)
157 sm_msg("%s from %d, has borrowed implications.",
158 sm_state
->name
, sm_state
->line
);
163 istrue
= !possibly_false_rl(estate_rl(s
->state
), comparison
, vals
);
164 isfalse
= !possibly_true_rl(estate_rl(s
->state
), comparison
, vals
);
166 istrue
= !possibly_false_rl(vals
, comparison
, estate_rl(s
->state
));
167 isfalse
= !possibly_true_rl(vals
, comparison
, estate_rl(s
->state
));
170 print_debug_tf(s
, istrue
, isfalse
);
173 add_pool(true_stack
, s
->pool
);
176 add_pool(false_stack
, s
->pool
);
179 static int pool_in_pools(struct stree
*pool
,
180 struct stree_stack
*pools
)
184 FOR_EACH_PTR(pools
, tmp
) {
189 } END_FOR_EACH_PTR(tmp
);
193 static int is_checked(struct state_list
*checked
, struct sm_state
*sm
)
195 struct sm_state
*tmp
;
197 FOR_EACH_PTR(checked
, tmp
) {
200 } END_FOR_EACH_PTR(tmp
);
206 * Example code: if (foo == 99) {
208 * Say 'foo' is a merged state that has many possible values. It is the combination
209 * of merges. separate_pools() iterates through the pools recursively and calls
210 * do_compare() for each time 'foo' was set.
212 static void separate_pools(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
214 struct stree_stack
**true_stack
,
215 struct stree_stack
**false_stack
,
216 struct state_list
**checked
)
218 int free_checked
= 0;
219 struct state_list
*checked_states
= NULL
;
225 Sometimes the implications are just too big to deal with
226 so we bail. Theoretically, bailing out here can cause more false
227 positives but won't hide actual bugs.
229 if (sm_state
->nr_children
> 4000) {
230 if (option_debug
|| option_debug_implied
) {
231 static char buf
[1028];
232 snprintf(buf
, sizeof(buf
), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
233 sm_state
->nr_children
, sm_state
->name
, show_state(sm_state
->state
));
234 implied_debug_msg
= buf
;
239 if (checked
== NULL
) {
240 checked
= &checked_states
;
243 if (is_checked(*checked
, sm_state
))
245 add_ptr_list(checked
, sm_state
);
247 do_compare(sm_state
, comparison
, vals
, lr
, true_stack
, false_stack
);
249 separate_pools(sm_state
->left
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
250 separate_pools(sm_state
->right
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
255 struct sm_state
*filter_pools(struct sm_state
*sm
,
256 struct stree_stack
*remove_stack
,
257 struct stree_stack
*keep_stack
,
260 struct sm_state
*ret
= NULL
;
261 struct sm_state
*left
;
262 struct sm_state
*right
;
268 if (sm
->nr_children
> 4000) {
269 if (option_debug
|| option_debug_implied
) {
270 static char buf
[1028];
271 snprintf(buf
, sizeof(buf
), "debug: %s: nr_children over 4000 (%d). (%s %s)",
272 __func__
, sm
->nr_children
, sm
->name
, show_state(sm
->state
));
273 implied_debug_msg
= buf
;
278 if (pool_in_pools(sm
->pool
, remove_stack
)) {
279 DIMPLIED("removed %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
284 if (!is_merged(sm
) || pool_in_pools(sm
->pool
, keep_stack
)) {
285 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
289 DIMPLIED("checking %s from %d (%d) [stree %d] left = %s [stree %d] right = %s [stree %d]\n",
290 show_sm(sm
), sm
->line
, sm
->nr_children
, get_stree_id(sm
->pool
),
291 sm
->left
? show_sm(sm
->left
) : "<none>", sm
->left
? get_stree_id(sm
->left
->pool
) : -1,
292 sm
->right
? show_sm(sm
->right
) : "<none>", sm
->right
? get_stree_id(sm
->right
->pool
) : -1);
293 left
= filter_pools(sm
->left
, remove_stack
, keep_stack
, &removed
);
294 right
= filter_pools(sm
->right
, remove_stack
, keep_stack
, &removed
);
296 DIMPLIED("kept %s from %d [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
300 if (!left
&& !right
) {
301 DIMPLIED("removed %s from %d <none> [stree %d]\n", show_sm(sm
), sm
->line
, get_stree_id(sm
->pool
));
306 ret
= clone_sm(right
);
310 ret
->pool
= sm
->pool
;
312 ret
= clone_sm(left
);
316 ret
->pool
= sm
->pool
;
318 ret
= merge_sm_states(left
, right
);
319 ret
->pool
= sm
->pool
;
322 DIMPLIED("partial %s => ", show_sm(sm
));
323 DIMPLIED("%s from %d [stree %d]\n", show_sm(ret
), sm
->line
, get_stree_id(sm
->pool
));
327 static int highest_stree_id(struct sm_state
*sm
)
332 if (!sm
->left
&& !sm
->right
)
336 left
= get_stree_id(sm
->left
->pool
);
338 right
= get_stree_id(sm
->right
->pool
);
345 static struct stree
*filter_stack(struct sm_state
*gate_sm
,
346 struct stree
*pre_stree
,
347 struct stree_stack
*remove_stack
,
348 struct stree_stack
*keep_stack
)
350 struct stree
*ret
= NULL
;
351 struct sm_state
*tmp
;
352 struct sm_state
*filtered_sm
;
358 FOR_EACH_SM(pre_stree
, tmp
) {
359 if (highest_stree_id(tmp
) < highest_stree_id(gate_sm
)) {
360 DIMPLIED("skipping %s. set before. %d vs %d\n",
361 tmp
->name
, highest_stree_id(tmp
),
362 highest_stree_id(gate_sm
));
366 filtered_sm
= filter_pools(tmp
, remove_stack
, keep_stack
, &modified
);
367 if (filtered_sm
&& modified
) {
368 /* the assignments here are for borrowed implications */
369 filtered_sm
->name
= tmp
->name
;
370 filtered_sm
->sym
= tmp
->sym
;
371 avl_insert(&ret
, filtered_sm
);
376 } END_FOR_EACH_SM(tmp
);
380 static void separate_and_filter(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
382 struct stree
*pre_stree
,
383 struct stree
**true_states
,
384 struct stree
**false_states
)
386 struct stree_stack
*true_stack
= NULL
;
387 struct stree_stack
*false_stack
= NULL
;
388 struct timeval time_before
;
389 struct timeval time_after
;
391 gettimeofday(&time_before
, NULL
);
393 if (!is_merged(sm_state
)) {
394 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state
->name
);
398 if (option_debug_implied
|| option_debug
) {
400 sm_msg("checking implications: (%s %s %s)",
401 sm_state
->name
, show_special(comparison
), show_rl(vals
));
403 sm_msg("checking implications: (%s %s %s)",
404 show_rl(vals
), show_special(comparison
), sm_state
->name
);
407 separate_pools(sm_state
, comparison
, vals
, lr
, &true_stack
, &false_stack
, NULL
);
409 DIMPLIED("filtering true stack.\n");
410 *true_states
= filter_stack(sm_state
, pre_stree
, false_stack
, true_stack
);
411 DIMPLIED("filtering false stack.\n");
412 *false_states
= filter_stack(sm_state
, pre_stree
, true_stack
, false_stack
);
413 free_stree_stack(&true_stack
);
414 free_stree_stack(&false_stack
);
415 if (option_debug_implied
|| option_debug
) {
416 printf("These are the implied states for the true path:\n");
417 __print_stree(*true_states
);
418 printf("These are the implied states for the false path:\n");
419 __print_stree(*false_states
);
422 gettimeofday(&time_after
, NULL
);
423 if (time_after
.tv_sec
- time_before
.tv_sec
> 7)
424 __bail_on_rest_of_function
= 1;
427 static struct expression
*get_left_most_expr(struct expression
*expr
)
429 expr
= strip_expr(expr
);
430 if (expr
->type
== EXPR_ASSIGNMENT
)
431 return get_left_most_expr(expr
->left
);
435 static int is_merged_expr(struct expression
*expr
)
440 if (get_value(expr
, &dummy
))
442 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
450 static void delete_equiv_stree(struct stree
**stree
, const char *name
, struct symbol
*sym
)
452 struct smatch_state
*state
;
453 struct relation
*rel
;
455 state
= get_state(SMATCH_EXTRA
, name
, sym
);
456 if (!estate_related(state
)) {
457 delete_state_stree(stree
, SMATCH_EXTRA
, name
, sym
);
461 FOR_EACH_PTR(estate_related(state
), rel
) {
462 delete_state_stree(stree
, SMATCH_EXTRA
, rel
->name
, rel
->sym
);
463 } END_FOR_EACH_PTR(rel
);
466 static void handle_comparison(struct expression
*expr
,
467 struct stree
**implied_true
,
468 struct stree
**implied_false
)
470 struct sm_state
*sm
= NULL
;
471 struct range_list
*ranges
= NULL
;
472 struct expression
*left
;
473 struct expression
*right
;
476 left
= get_left_most_expr(expr
->left
);
477 right
= get_left_most_expr(expr
->right
);
479 if (is_merged_expr(left
)) {
481 sm
= get_sm_state_expr(SMATCH_EXTRA
, left
);
482 get_implied_rl(right
, &ranges
);
483 } else if (is_merged_expr(right
)) {
485 sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
486 get_implied_rl(left
, &ranges
);
489 if (!ranges
|| !sm
) {
494 separate_and_filter(sm
, expr
->op
, ranges
, lr
, __get_cur_stree(), implied_true
, implied_false
);
496 delete_equiv_stree(implied_true
, sm
->name
, sm
->sym
);
497 delete_equiv_stree(implied_false
, sm
->name
, sm
->sym
);
500 static void handle_zero_comparison(struct expression
*expr
,
501 struct stree
**implied_true
,
502 struct stree
**implied_false
)
508 if (expr
->type
== EXPR_POSTOP
)
509 expr
= strip_expr(expr
->unop
);
511 if (expr
->type
== EXPR_ASSIGNMENT
) {
512 /* most of the time ->pools will be empty here because we
513 just set the state, but if have assigned a conditional
514 function there are implications. */
518 name
= expr_to_var_sym(expr
, &sym
);
521 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
525 separate_and_filter(sm
, SPECIAL_NOTEQUAL
, tmp_range_list(0), LEFT
, __get_cur_stree(), implied_true
, implied_false
);
526 delete_equiv_stree(implied_true
, name
, sym
);
527 delete_equiv_stree(implied_false
, name
, sym
);
532 static int handled_by_implied_hook(struct expression
*expr
,
533 struct stree
**implied_true
,
534 struct stree
**implied_false
)
536 struct stree_stack
*true_stack
= NULL
;
537 struct stree_stack
*false_stack
= NULL
;
538 struct stree
*pre_stree
;
541 sm
= comparison_implication_hook(expr
, &true_stack
, &false_stack
);
545 pre_stree
= clone_stree(__get_cur_stree());
547 *implied_true
= filter_stack(sm
, pre_stree
, false_stack
, true_stack
);
548 *implied_false
= filter_stack(sm
, pre_stree
, true_stack
, false_stack
);
550 free_stree(&pre_stree
);
551 free_stree_stack(&true_stack
);
552 free_stree_stack(&false_stack
);
557 static void get_tf_states(struct expression
*expr
,
558 struct stree
**implied_true
,
559 struct stree
**implied_false
)
561 if (handled_by_implied_hook(expr
, implied_true
, implied_false
))
564 if (expr
->type
== EXPR_COMPARE
)
565 handle_comparison(expr
, implied_true
, implied_false
);
567 handle_zero_comparison(expr
, implied_true
, implied_false
);
570 static struct stree
*saved_implied_true
;
571 static struct stree
*saved_implied_false
;
573 static void save_implications_hook(struct expression
*expr
)
575 if (option_no_implied
)
577 get_tf_states(expr
, &saved_implied_true
, &saved_implied_false
);
580 static void set_implied_states(struct expression
*expr
)
584 FOR_EACH_SM(saved_implied_true
, sm
) {
586 * Setting the true sm means setting the cur_stree. If we are
587 * not also setting the false_stree then it causes problems.
589 if (!get_state_stree(saved_implied_false
, sm
->owner
, sm
->name
, sm
->sym
)) {
590 struct sm_state
*orig
;
592 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
594 set_state_stree(&saved_implied_false
, sm
->owner
, sm
->name
, sm
->sym
, orig
->state
);
596 __set_true_false_sm(sm
, NULL
);
597 } END_FOR_EACH_SM(sm
);
598 free_stree(&saved_implied_true
);
600 FOR_EACH_SM(saved_implied_false
, sm
) {
601 __set_true_false_sm(NULL
, sm
);
602 } END_FOR_EACH_SM(sm
);
603 free_stree(&saved_implied_false
);
606 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
610 struct smatch_state
*state
;
611 struct range_list
*ret
= NULL
;
613 name
= expr_to_var_sym(switch_expr
, &sym
);
616 state
= get_state(SMATCH_EXTRA
, name
, sym
);
619 ret
= clone_rl(estate_rl(state
));
625 type
= get_type(switch_expr
);
626 ret
= alloc_rl(sval_type_min(type
), sval_type_max(type
));
631 struct stree
*__implied_case_stree(struct expression
*switch_expr
,
632 struct expression
*case_expr
,
633 struct range_list_stack
**remaining_cases
,
634 struct stree
**raw_stree
)
639 struct stree
*true_states
= NULL
;
640 struct stree
*false_states
= NULL
;
641 struct stree
*extra_states
= NULL
;
642 struct stree
*ret
= clone_stree(*raw_stree
);
644 struct range_list
*vals
= NULL
;
646 name
= expr_to_var_sym(switch_expr
, &sym
);
649 sm
= get_sm_state_stree(*raw_stree
, SMATCH_EXTRA
, name
, sym
);
652 if (get_value(case_expr
, &sval
)) {
653 filter_top_rl(remaining_cases
, sval
);
654 add_range(&vals
, sval
, sval
);
656 vals
= clone_rl(top_rl(*remaining_cases
));
659 vals
= top_rl(*remaining_cases
);
663 separate_and_filter(sm
, SPECIAL_EQUAL
, vals
, LEFT
, *raw_stree
, &true_states
, &false_states
);
665 __push_fake_cur_stree();
667 set_extra_nomod(name
, sym
, alloc_estate_rl(vals
));
668 extra_states
= __pop_fake_cur_stree();
669 overwrite_stree(extra_states
, &true_states
);
670 overwrite_stree(true_states
, &ret
);
671 free_stree(&extra_states
);
672 free_stree(&true_states
);
673 free_stree(&false_states
);
679 static void match_end_func(struct symbol
*sym
)
683 implied_debug_msg
= NULL
;
686 static int sm_state_in_slist(struct sm_state
*sm
, struct state_list
*slist
)
688 struct sm_state
*tmp
;
690 FOR_EACH_PTR(slist
, tmp
) {
693 } END_FOR_EACH_PTR(tmp
);
698 * The situation is we have a SMATCH_EXTRA state and we want to break it into
699 * each of the ->possible states and find the implications of each. The caller
700 * has to use __push_fake_cur_stree() to preserve the correct states so they
701 * can be restored later.
703 void overwrite_states_using_pool(struct sm_state
*sm
)
705 struct sm_state
*old
;
706 struct sm_state
*new;
711 FOR_EACH_SM(sm
->pool
, old
) {
712 new = get_sm_state(old
->owner
, old
->name
, old
->sym
);
713 if (!new) /* the variable went out of scope */
715 if (sm_state_in_slist(old
, new->possible
))
716 set_state(old
->owner
, old
->name
, old
->sym
, old
->state
);
717 } END_FOR_EACH_SM(old
);
720 void __extra_match_condition(struct expression
*expr
);
721 void __comparison_match_condition(struct expression
*expr
);
722 void register_implications(int id
)
724 add_hook(&save_implications_hook
, CONDITION_HOOK
);
725 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
726 add_hook(&__comparison_match_condition
, CONDITION_HOOK
);
727 add_hook(&set_implied_states
, CONDITION_HOOK
);
728 add_hook(&match_end_func
, END_FUNC_HOOK
);