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.\n", s
->name
, show_state(s
->state
),
101 } else if (isfalse
) {
102 printf("'%s = %s' from %d is false.\n", s
->name
, show_state(s
->state
),
105 printf("'%s = %s' from %d could be true or false.\n", s
->name
,
106 show_state(s
->state
), s
->line
);
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 static 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 static char buf
[1028];
231 snprintf(buf
, sizeof(buf
), "debug: separate_pools: nr_children over 4000 (%d). (%s %s)",
232 sm_state
->nr_children
, sm_state
->name
, show_state(sm_state
->state
));
233 implied_debug_msg
= buf
;
237 if (checked
== NULL
) {
238 checked
= &checked_states
;
241 if (is_checked(*checked
, sm_state
))
243 add_ptr_list(checked
, sm_state
);
245 do_compare(sm_state
, comparison
, vals
, lr
, true_stack
, false_stack
);
247 separate_pools(sm_state
->left
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
248 separate_pools(sm_state
->right
, comparison
, vals
, lr
, true_stack
, false_stack
, checked
);
253 struct sm_state
*remove_pools(struct sm_state
*sm
,
254 struct stree_stack
*pools
, int *modified
)
256 struct sm_state
*ret
= NULL
;
257 struct sm_state
*left
;
258 struct sm_state
*right
;
264 if (sm
->nr_children
> 4000) {
265 static char buf
[1028];
266 snprintf(buf
, sizeof(buf
), "debug: remove_pools: nr_children over 4000 (%d). (%s %s)",
267 sm
->nr_children
, sm
->name
, show_state(sm
->state
));
268 implied_debug_msg
= buf
;
272 if (pool_in_pools(sm
->pool
, pools
)) {
273 DIMPLIED("removed %s from %d\n", show_sm(sm
), sm
->line
);
278 if (!is_merged(sm
)) {
279 DIMPLIED("kept %s from %d\n", show_sm(sm
), sm
->line
);
283 DIMPLIED("checking %s from %d (%d)\n", show_sm(sm
), sm
->line
, sm
->nr_children
);
284 left
= remove_pools(sm
->left
, pools
, &removed
);
285 right
= remove_pools(sm
->right
, pools
, &removed
);
287 DIMPLIED("kept %s from %d\n", show_sm(sm
), sm
->line
);
291 if (!left
&& !right
) {
292 DIMPLIED("removed %s from %d <none>\n", show_sm(sm
), sm
->line
);
297 ret
= clone_sm(right
);
301 ret
->pool
= sm
->pool
;
303 ret
= clone_sm(left
);
307 ret
->pool
= sm
->pool
;
309 ret
= merge_sm_states(left
, right
);
310 ret
->pool
= sm
->pool
;
313 DIMPLIED("partial %s => ", show_sm(sm
));
314 DIMPLIED("%s from %d\n", show_sm(ret
), sm
->line
);
318 static int highest_slist_id(struct sm_state
*sm
)
323 if (!sm
->left
&& !sm
->right
)
327 left
= get_stree_id(sm
->left
->pool
);
329 right
= get_stree_id(sm
->right
->pool
);
336 static struct stree
*filter_stack(struct sm_state
*gate_sm
,
337 struct stree
*pre_stree
,
338 struct stree_stack
*stack
)
340 struct stree
*ret
= NULL
;
341 struct sm_state
*tmp
;
342 struct sm_state
*filtered_sm
;
348 FOR_EACH_SM(pre_stree
, tmp
) {
349 if (highest_slist_id(tmp
) < highest_slist_id(gate_sm
)) {
350 DIMPLIED("skipping %s. set before. %d vs %d\n",
351 tmp
->name
, highest_slist_id(tmp
),
352 highest_slist_id(gate_sm
));
356 filtered_sm
= remove_pools(tmp
, stack
, &modified
);
357 if (filtered_sm
&& modified
) {
358 /* the assignments here are for borrowed implications */
359 filtered_sm
->name
= tmp
->name
;
360 filtered_sm
->sym
= tmp
->sym
;
361 avl_insert(&ret
, filtered_sm
);
366 } END_FOR_EACH_SM(tmp
);
370 static void separate_and_filter(struct sm_state
*sm_state
, int comparison
, struct range_list
*vals
,
372 struct stree
*pre_stree
,
373 struct stree
**true_states
,
374 struct stree
**false_states
)
376 struct stree_stack
*true_stack
= NULL
;
377 struct stree_stack
*false_stack
= NULL
;
378 struct timeval time_before
;
379 struct timeval time_after
;
381 gettimeofday(&time_before
, NULL
);
383 if (!is_merged(sm_state
)) {
384 DIMPLIED("%d '%s' is not merged.\n", get_lineno(), sm_state
->name
);
388 if (option_debug_implied
|| option_debug
) {
390 sm_msg("checking implications: (%s %s %s)",
391 sm_state
->name
, show_special(comparison
), show_rl(vals
));
393 sm_msg("checking implications: (%s %s %s)",
394 show_rl(vals
), show_special(comparison
), sm_state
->name
);
397 separate_pools(sm_state
, comparison
, vals
, lr
, &true_stack
, &false_stack
, NULL
);
399 DIMPLIED("filtering true stack.\n");
400 *true_states
= filter_stack(sm_state
, pre_stree
, false_stack
);
401 DIMPLIED("filtering false stack.\n");
402 *false_states
= filter_stack(sm_state
, pre_stree
, true_stack
);
403 free_stree_stack(&true_stack
);
404 free_stree_stack(&false_stack
);
405 if (option_debug_implied
|| option_debug
) {
406 printf("These are the implied states for the true path:\n");
407 __print_stree(*true_states
);
408 printf("These are the implied states for the false path:\n");
409 __print_stree(*false_states
);
412 gettimeofday(&time_after
, NULL
);
413 if (time_after
.tv_sec
- time_before
.tv_sec
> 7)
414 __bail_on_rest_of_function
= 1;
417 static struct expression
*get_left_most_expr(struct expression
*expr
)
419 expr
= strip_expr(expr
);
420 if (expr
->type
== EXPR_ASSIGNMENT
)
421 return get_left_most_expr(expr
->left
);
425 static int is_merged_expr(struct expression
*expr
)
430 if (get_value(expr
, &dummy
))
432 sm
= get_sm_state_expr(SMATCH_EXTRA
, expr
);
440 static void delete_equiv_stree(struct stree
**stree
, const char *name
, struct symbol
*sym
)
442 struct smatch_state
*state
;
443 struct relation
*rel
;
445 state
= get_state(SMATCH_EXTRA
, name
, sym
);
446 if (!estate_related(state
)) {
447 delete_state_stree(stree
, SMATCH_EXTRA
, name
, sym
);
451 FOR_EACH_PTR(estate_related(state
), rel
) {
452 delete_state_stree(stree
, SMATCH_EXTRA
, rel
->name
, rel
->sym
);
453 } END_FOR_EACH_PTR(rel
);
456 static void handle_comparison(struct expression
*expr
,
457 struct stree
**implied_true
,
458 struct stree
**implied_false
)
460 struct sm_state
*sm
= NULL
;
461 struct range_list
*ranges
= NULL
;
462 struct expression
*left
;
463 struct expression
*right
;
466 left
= get_left_most_expr(expr
->left
);
467 right
= get_left_most_expr(expr
->right
);
469 if (is_merged_expr(left
)) {
471 sm
= get_sm_state_expr(SMATCH_EXTRA
, left
);
472 get_implied_rl(right
, &ranges
);
473 } else if (is_merged_expr(right
)) {
475 sm
= get_sm_state_expr(SMATCH_EXTRA
, right
);
476 get_implied_rl(left
, &ranges
);
479 if (!ranges
|| !sm
) {
484 separate_and_filter(sm
, expr
->op
, ranges
, lr
, __get_cur_stree(), implied_true
, implied_false
);
486 delete_equiv_stree(implied_true
, sm
->name
, sm
->sym
);
487 delete_equiv_stree(implied_false
, sm
->name
, sm
->sym
);
490 static void handle_zero_comparison(struct expression
*expr
,
491 struct stree
**implied_true
,
492 struct stree
**implied_false
)
498 if (expr
->type
== EXPR_POSTOP
)
499 expr
= strip_expr(expr
->unop
);
501 if (expr
->type
== EXPR_ASSIGNMENT
) {
502 /* most of the time ->pools will be empty here because we
503 just set the state, but if have assigned a conditional
504 function there are implications. */
508 name
= expr_to_var_sym(expr
, &sym
);
511 sm
= get_sm_state(SMATCH_EXTRA
, name
, sym
);
515 separate_and_filter(sm
, SPECIAL_NOTEQUAL
, tmp_range_list(0), LEFT
, __get_cur_stree(), implied_true
, implied_false
);
516 delete_equiv_stree(implied_true
, name
, sym
);
517 delete_equiv_stree(implied_false
, name
, sym
);
522 static void get_tf_states(struct expression
*expr
,
523 struct stree
**implied_true
,
524 struct stree
**implied_false
)
526 if (expr
->type
== EXPR_COMPARE
)
527 handle_comparison(expr
, implied_true
, implied_false
);
529 handle_zero_comparison(expr
, implied_true
, implied_false
);
532 static void implied_states_hook(struct expression
*expr
)
535 struct stree
*implied_true
= NULL
;
536 struct stree
*implied_false
= NULL
;
538 if (option_no_implied
)
541 get_tf_states(expr
, &implied_true
, &implied_false
);
543 FOR_EACH_SM(implied_true
, sm
) {
544 __set_true_false_sm(sm
, NULL
);
545 } END_FOR_EACH_SM(sm
);
546 free_stree(&implied_true
);
548 FOR_EACH_SM(implied_false
, sm
) {
549 __set_true_false_sm(NULL
, sm
);
550 } END_FOR_EACH_SM(sm
);
551 free_stree(&implied_false
);
554 struct range_list
*__get_implied_values(struct expression
*switch_expr
)
558 struct smatch_state
*state
;
559 struct range_list
*ret
= NULL
;
561 name
= expr_to_var_sym(switch_expr
, &sym
);
564 state
= get_state(SMATCH_EXTRA
, name
, sym
);
567 ret
= clone_rl(estate_rl(state
));
573 type
= get_type(switch_expr
);
574 ret
= alloc_rl(sval_type_min(type
), sval_type_max(type
));
579 struct stree
*__implied_case_stree(struct expression
*switch_expr
,
580 struct expression
*case_expr
,
581 struct range_list_stack
**remaining_cases
,
582 struct stree
**raw_stree
)
587 struct stree
*true_states
= NULL
;
588 struct stree
*false_states
= NULL
;
589 struct stree
*extra_states
= NULL
;
590 struct stree
*ret
= clone_stree(*raw_stree
);
592 struct range_list
*vals
= NULL
;
594 name
= expr_to_var_sym(switch_expr
, &sym
);
597 sm
= get_sm_state_stree(*raw_stree
, SMATCH_EXTRA
, name
, sym
);
600 if (get_value(case_expr
, &sval
)) {
601 filter_top_rl(remaining_cases
, sval
);
602 add_range(&vals
, sval
, sval
);
604 vals
= clone_rl(top_rl(*remaining_cases
));
607 vals
= top_rl(*remaining_cases
);
611 separate_and_filter(sm
, SPECIAL_EQUAL
, vals
, LEFT
, *raw_stree
, &true_states
, &false_states
);
613 __push_fake_cur_stree();
615 set_extra_nomod(name
, sym
, alloc_estate_rl(vals
));
616 extra_states
= __pop_fake_cur_stree();
617 overwrite_stree(extra_states
, &true_states
);
618 overwrite_stree(true_states
, &ret
);
619 free_stree(&extra_states
);
620 free_stree(&true_states
);
621 free_stree(&false_states
);
627 static void match_end_func(struct symbol
*sym
)
631 implied_debug_msg
= NULL
;
634 static int sm_state_in_slist(struct sm_state
*sm
, struct state_list
*slist
)
636 struct sm_state
*tmp
;
638 FOR_EACH_PTR(slist
, tmp
) {
641 } END_FOR_EACH_PTR(tmp
);
646 * The situation is we have a SMATCH_EXTRA state and we want to break it into
647 * each of the ->possible states and find the implications of each. The caller
648 * has to use __push_fake_cur_stree() to preserve the correct states so they
649 * can be restored later.
651 void overwrite_states_using_pool(struct sm_state
*sm
)
653 struct sm_state
*old
;
654 struct sm_state
*new;
659 FOR_EACH_SM(sm
->pool
, old
) {
660 new = get_sm_state(old
->owner
, old
->name
, old
->sym
);
661 if (!new) /* the variable went out of scope */
663 if (sm_state_in_slist(old
, new->possible
))
664 set_state(old
->owner
, old
->name
, old
->sym
, old
->state
);
665 } END_FOR_EACH_SM(old
);
668 void __extra_match_condition(struct expression
*expr
);
669 void register_implications(int id
)
671 add_hook(&implied_states_hook
, CONDITION_HOOK
);
672 add_hook(&__extra_match_condition
, CONDITION_HOOK
);
673 add_hook(&match_end_func
, END_FUNC_HOOK
);