2 * Copyright (C) 2006 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 * You have a lists of states. kernel = locked, foo = NULL, ...
20 * When you hit an if {} else {} statement then you swap the list
21 * of states for a different list of states. The lists are stored
24 * At the beginning of this file there are list of the stacks that
25 * we use. Each function in this file does something to one of
28 * So the smatch_flow.c understands code but it doesn't understand states.
29 * smatch_flow calls functions in this file. This file calls functions
30 * in smatch_slist.c which just has boring generic plumbing for handling
31 * state lists. But really it's this file where all the magic happens.
37 #include "smatch_slist.h"
38 #include "smatch_extra.h"
40 struct smatch_state undefined
= { .name
= "undefined" };
41 struct smatch_state merged
= { .name
= "merged" };
42 struct smatch_state true_state
= { .name
= "true" };
43 struct smatch_state false_state
= { .name
= "false" };
45 static struct stree
*cur_stree
; /* current states */
47 static struct stree_stack
*true_stack
; /* states after a t/f branch */
48 static struct stree_stack
*false_stack
;
49 static struct stree_stack
*pre_cond_stack
; /* states before a t/f branch */
51 static struct stree_stack
*cond_true_stack
; /* states affected by a branch */
52 static struct stree_stack
*cond_false_stack
;
54 static struct stree_stack
*fake_cur_stree_stack
;
57 static struct stree_stack
*break_stack
;
58 static struct stree_stack
*switch_stack
;
59 static struct range_list_stack
*remaining_cases
;
60 static struct stree_stack
*default_stack
;
61 static struct stree_stack
*continue_stack
;
63 static struct named_stree_stack
*goto_stack
;
65 static struct ptr_list
*backup
;
69 void __print_cur_stree(void)
71 __print_stree(cur_stree
);
74 static int in_declarations_bit(void)
76 struct statement
*tmp
;
78 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
79 if (tmp
->type
== STMT_DECLARATION
)
82 } END_FOR_EACH_PTR_REVERSE(tmp
);
88 static int reset_warnings
= 1;
96 if (in_declarations_bit())
99 /* option spammy turns on a noisier version of this */
100 if (reset_warnings
&& !option_spammy
)
101 sm_msg("info: ignoring unreachable code.");
107 struct sm_state
*set_state(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
109 struct sm_state
*ret
;
115 sm_msg("Smatch Internal Error: cur_stree is read only.");
117 if (option_debug
|| strcmp(check_name(owner
), option_debug_check
) == 0) {
118 struct smatch_state
*s
;
120 s
= get_state(owner
, name
, sym
);
122 printf("%d new state. name='%s' [%s] %s\n",
123 get_lineno(), name
, check_name(owner
), show_state(state
));
125 printf("%d state change name='%s' [%s] %s => %s\n",
126 get_lineno(), name
, check_name(owner
), show_state(s
),
130 if (owner
!= -1 && unreachable())
133 if (fake_cur_stree_stack
)
134 set_state_stree_stack(&fake_cur_stree_stack
, owner
, name
, sym
, state
);
136 ret
= set_state_stree(&cur_stree
, owner
, name
, sym
, state
);
138 if (cond_true_stack
) {
139 set_state_stree_stack(&cond_true_stack
, owner
, name
, sym
, state
);
140 set_state_stree_stack(&cond_false_stack
, owner
, name
, sym
, state
);
145 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
149 struct sm_state
*ret
= NULL
;
151 expr
= strip_expr(expr
);
152 name
= expr_to_var_sym(expr
, &sym
);
155 ret
= set_state(owner
, name
, sym
, state
);
161 void __push_fake_cur_slist()
163 push_stree(&fake_cur_stree_stack
, NULL
);
164 __save_pre_cond_states();
167 struct stree
*__pop_fake_cur_slist()
169 __use_pre_cond_states();
170 return pop_stree(&fake_cur_stree_stack
);
173 void __free_fake_cur_slist()
177 __use_pre_cond_states();
178 stree
= pop_stree(&fake_cur_stree_stack
);
182 void __set_fake_cur_stree_fast(struct stree
*stree
)
184 push_stree(&pre_cond_stack
, cur_stree
);
189 void __pop_fake_cur_slist_fast()
191 cur_stree
= pop_stree(&pre_cond_stack
);
195 void __pop_fake_cur_stree_fast()
197 cur_stree
= pop_stree(&pre_cond_stack
);
201 void __merge_stree_into_cur(struct stree
*stree
)
204 struct sm_state
*orig
;
205 struct sm_state
*merged
;
207 FOR_EACH_SM(stree
, sm
) {
208 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
210 merged
= merge_sm_states(orig
, sm
);
214 } END_FOR_EACH_SM(sm
);
217 void __set_sm(struct sm_state
*sm
)
220 sm_msg("Smatch Internal Error: cur_stree is read only.");
223 strcmp(check_name(sm
->owner
), option_debug_check
) == 0) {
224 struct smatch_state
*s
;
226 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
228 printf("%d new state. name='%s' [%s] %s\n",
229 get_lineno(), sm
->name
, check_name(sm
->owner
),
230 show_state(sm
->state
));
232 printf("%d state change name='%s' [%s] %s => %s\n",
233 get_lineno(), sm
->name
, check_name(sm
->owner
), show_state(s
),
234 show_state(sm
->state
));
240 if (fake_cur_stree_stack
)
241 overwrite_sm_state_stree_stack(&fake_cur_stree_stack
, sm
);
243 overwrite_sm_state_stree(&cur_stree
, sm
);
245 if (cond_true_stack
) {
246 overwrite_sm_state_stree_stack(&cond_true_stack
, sm
);
247 overwrite_sm_state_stree_stack(&cond_false_stack
, sm
);
251 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
253 return get_state_stree(cur_stree
, owner
, name
, sym
);
256 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
260 struct smatch_state
*ret
= NULL
;
262 expr
= strip_expr(expr
);
263 name
= expr_to_var_sym(expr
, &sym
);
266 ret
= get_state(owner
, name
, sym
);
272 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
274 struct sm_state
*sms
;
276 sms
= get_sm_state_stree(cur_stree
, owner
, name
, sym
);
278 return sms
->possible
;
282 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
286 struct state_list
*ret
= NULL
;
288 expr
= strip_expr(expr
);
289 name
= expr_to_var_sym(expr
, &sym
);
292 ret
= get_possible_states(owner
, name
, sym
);
298 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
300 return get_sm_state_stree(cur_stree
, owner
, name
, sym
);
303 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
307 struct sm_state
*ret
= NULL
;
309 expr
= strip_expr(expr
);
310 name
= expr_to_var_sym(expr
, &sym
);
313 ret
= get_sm_state(owner
, name
, sym
);
319 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
321 delete_state_stree(&cur_stree
, owner
, name
, sym
);
322 if (cond_true_stack
) {
323 delete_state_stree_stack(&pre_cond_stack
, owner
, name
, sym
);
324 delete_state_stree_stack(&cond_true_stack
, owner
, name
, sym
);
325 delete_state_stree_stack(&cond_false_stack
, owner
, name
, sym
);
329 void delete_state_expr(int owner
, struct expression
*expr
)
334 expr
= strip_expr(expr
);
335 name
= expr_to_var_sym(expr
, &sym
);
338 delete_state(owner
, name
, sym
);
343 struct stree
*get_all_states_from_stree(int owner
, struct stree
*source
)
345 struct stree
*ret
= NULL
;
346 struct sm_state
*tmp
;
348 FOR_EACH_SM(source
, tmp
) {
349 if (tmp
->owner
== owner
)
350 avl_insert(&ret
, tmp
);
351 } END_FOR_EACH_SM(tmp
);
356 struct stree
*get_all_states_stree(int owner
)
358 return get_all_states_from_stree(owner
, cur_stree
);
361 struct stree
*__get_cur_stree(void)
366 int is_reachable(void)
373 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
374 struct smatch_state
*true_state
,
375 struct smatch_state
*false_state
)
377 if (option_debug
|| strcmp(check_name(owner
), option_debug_check
) == 0) {
378 struct smatch_state
*tmp
;
380 tmp
= get_state(owner
, name
, sym
);
381 printf("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
382 get_lineno(), name
, show_state(tmp
),
383 show_state(true_state
), show_state(false_state
));
389 if (!cond_false_stack
|| !cond_true_stack
) {
390 printf("Error: missing true/false stacks\n");
395 set_state_stree(&cur_stree
, owner
, name
, sym
, true_state
);
396 set_state_stree_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
399 set_state_stree_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
402 void set_true_false_states_expr(int owner
, struct expression
*expr
,
403 struct smatch_state
*true_state
,
404 struct smatch_state
*false_state
)
409 expr
= strip_expr(expr
);
410 name
= expr_to_var_sym(expr
, &sym
);
413 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
418 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
423 if (!cond_false_stack
|| !cond_true_stack
) {
424 printf("Error: missing true/false stacks\n");
429 overwrite_sm_state_stree(&cur_stree
, true_sm
);
430 overwrite_sm_state_stree_stack(&cond_true_stack
, true_sm
);
433 overwrite_sm_state_stree_stack(&cond_false_stack
, false_sm
);
436 void nullify_path(void)
438 free_stree(&cur_stree
);
441 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
448 * At the start of every function we mark the path
449 * as unnull. That way there is always at least one state
450 * in the cur_stree until nullify_path is called. This
451 * is used in merge_slist() for the first null check.
453 void __unnullify_path(void)
455 set_state(-1, "unnull_path", NULL
, &true_state
);
458 int __path_is_null(void)
465 static void check_stree_stack_free(struct stree_stack
**stack
)
468 sm_msg("smatch internal error: stack not empty");
469 free_stack_and_strees(stack
);
473 void save_all_states(void)
475 __add_ptr_list(&backup
, cur_stree
, 0);
477 __add_ptr_list(&backup
, true_stack
, 0);
478 __add_ptr_list(&backup
, false_stack
, 0);
479 __add_ptr_list(&backup
, pre_cond_stack
, 0);
481 __add_ptr_list(&backup
, cond_true_stack
, 0);
482 __add_ptr_list(&backup
, cond_false_stack
, 0);
484 __add_ptr_list(&backup
, fake_cur_stree_stack
, 0);
486 __add_ptr_list(&backup
, break_stack
, 0);
487 __add_ptr_list(&backup
, switch_stack
, 0);
488 __add_ptr_list(&backup
, remaining_cases
, 0);
489 __add_ptr_list(&backup
, default_stack
, 0);
490 __add_ptr_list(&backup
, continue_stack
, 0);
492 __add_ptr_list(&backup
, goto_stack
, 0);
495 void nullify_all_states(void)
497 /* FIXME: These should call free_stree() */
502 pre_cond_stack
= NULL
;
504 cond_true_stack
= NULL
;
505 cond_false_stack
= NULL
;
507 fake_cur_stree_stack
= NULL
;
511 remaining_cases
= NULL
;
512 default_stack
= NULL
;
513 continue_stack
= NULL
;
518 static void *pop_backup(void)
522 ret
= last_ptr_list(backup
);
523 delete_ptr_list_last(&backup
);
527 void restore_all_states(void)
529 goto_stack
= pop_backup();
531 continue_stack
= pop_backup();
532 default_stack
= pop_backup();
533 remaining_cases
= pop_backup();
534 switch_stack
= pop_backup();
535 break_stack
= pop_backup();
537 fake_cur_stree_stack
= pop_backup();
539 cond_false_stack
= pop_backup();
540 cond_true_stack
= pop_backup();
542 pre_cond_stack
= pop_backup();
543 false_stack
= pop_backup();
544 true_stack
= pop_backup();
546 cur_stree
= pop_backup();
549 void clear_all_states(void)
551 struct named_stree
*named_stree
;
554 check_stree_stack_free(&true_stack
);
555 check_stree_stack_free(&false_stack
);
556 check_stree_stack_free(&pre_cond_stack
);
557 check_stree_stack_free(&cond_true_stack
);
558 check_stree_stack_free(&cond_false_stack
);
559 check_stree_stack_free(&break_stack
);
560 check_stree_stack_free(&switch_stack
);
561 check_stree_stack_free(&continue_stack
);
563 FOR_EACH_PTR(goto_stack
, named_stree
) {
564 free_stree(&named_stree
->stree
);
565 } END_FOR_EACH_PTR(named_stree
);
566 __free_ptr_list((struct ptr_list
**)&goto_stack
);
567 free_every_single_sm_state();
570 void __push_cond_stacks(void)
572 push_stree(&cond_true_stack
, NULL
);
573 push_stree(&cond_false_stack
, NULL
);
576 struct stree
*__copy_cond_true_states(void)
580 ret
= pop_stree(&cond_true_stack
);
581 push_stree(&cond_true_stack
, clone_stree(ret
));
585 struct stree
*__copy_cond_false_states(void)
589 ret
= pop_stree(&cond_false_stack
);
590 push_stree(&cond_false_stack
, clone_stree(ret
));
594 struct stree
*__pop_cond_true_stack(void)
596 return pop_stree(&cond_true_stack
);
599 struct stree
*__pop_cond_false_stack(void)
601 return pop_stree(&cond_false_stack
);
605 * This combines the pre cond states with either the true or false states.
607 * a = kmalloc() ; if (a !! foo(a)
608 * In the pre state a is possibly null. In the true state it is non null.
609 * In the false state it is null. Combine the pre and the false to get
610 * that when we call 'foo', 'a' is null.
612 static void __use_cond_stack(struct stree_stack
**stack
)
616 free_stree(&cur_stree
);
618 cur_stree
= pop_stree(&pre_cond_stack
);
619 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
621 stree
= pop_stree(stack
);
622 overwrite_stree(stree
, &cur_stree
);
623 push_stree(stack
, stree
);
626 void __use_pre_cond_states(void)
628 free_stree(&cur_stree
);
629 cur_stree
= pop_stree(&pre_cond_stack
);
632 void __use_cond_true_states(void)
634 __use_cond_stack(&cond_true_stack
);
637 void __use_cond_false_states(void)
639 __use_cond_stack(&cond_false_stack
);
642 void __negate_cond_stacks(void)
644 struct stree
*old_false
, *old_true
;
646 __use_cond_stack(&cond_false_stack
);
647 old_false
= pop_stree(&cond_false_stack
);
648 old_true
= pop_stree(&cond_true_stack
);
649 push_stree(&cond_false_stack
, old_true
);
650 push_stree(&cond_true_stack
, old_false
);
653 void __and_cond_states(void)
655 and_stree_stack(&cond_true_stack
);
656 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_false_stack
);
659 void __or_cond_states(void)
661 or_stree_stack(&pre_cond_stack
, cur_stree
, &cond_true_stack
);
662 and_stree_stack(&cond_false_stack
);
665 void __save_pre_cond_states(void)
667 push_stree(&pre_cond_stack
, clone_stree(cur_stree
));
670 void __discard_pre_cond_states(void)
674 tmp
= pop_stree(&pre_cond_stack
);
678 void __use_cond_states(void)
680 struct stree
*pre
, *pre_clone
, *true_states
, *false_states
;
682 pre
= pop_stree(&pre_cond_stack
);
683 pre_clone
= clone_stree(pre
);
685 true_states
= pop_stree(&cond_true_stack
);
686 overwrite_stree(true_states
, &pre
);
687 /* we use the true states right away */
688 free_stree(&cur_stree
);
691 false_states
= pop_stree(&cond_false_stack
);
692 overwrite_stree(false_states
, &pre_clone
);
693 push_stree(&false_stack
, pre_clone
);
696 void __push_true_states(void)
698 push_stree(&true_stack
, clone_stree(cur_stree
));
701 void __use_false_states(void)
703 free_stree(&cur_stree
);
704 cur_stree
= pop_stree(&false_stack
);
707 void __discard_false_states(void)
711 stree
= pop_stree(&false_stack
);
715 void __merge_false_states(void)
719 stree
= pop_stree(&false_stack
);
720 merge_stree(&cur_stree
, stree
);
724 void __merge_true_states(void)
728 stree
= pop_stree(&true_stack
);
729 merge_stree(&cur_stree
, stree
);
733 void __push_continues(void)
735 push_stree(&continue_stack
, NULL
);
738 void __discard_continues(void)
742 stree
= pop_stree(&continue_stack
);
746 void __process_continues(void)
750 stree
= pop_stree(&continue_stack
);
752 stree
= clone_stree(cur_stree
);
754 merge_stree(&stree
, cur_stree
);
756 push_stree(&continue_stack
, stree
);
759 static int top_stree_empty(struct stree_stack
**stack
)
764 tmp
= pop_stree(stack
);
767 push_stree(stack
, tmp
);
771 /* a silly loop does this: while(i--) { return; } */
772 void __warn_on_silly_pre_loops(void)
774 if (!__path_is_null())
776 if (!top_stree_empty(&continue_stack
))
778 if (!top_stree_empty(&break_stack
))
780 /* if the path was nullified before the loop, then we already
781 printed an error earlier */
782 if (top_stree_empty(&false_stack
))
784 sm_msg("info: loop could be replaced with if statement.");
787 void __merge_continues(void)
791 stree
= pop_stree(&continue_stack
);
792 merge_stree(&cur_stree
, stree
);
796 void __push_breaks(void)
798 push_stree(&break_stack
, NULL
);
801 void __process_breaks(void)
805 stree
= pop_stree(&break_stack
);
807 stree
= clone_stree(cur_stree
);
809 merge_stree(&stree
, cur_stree
);
811 push_stree(&break_stack
, stree
);
814 int __has_breaks(void)
819 stree
= pop_stree(&break_stack
);
821 push_stree(&break_stack
, stree
);
825 void __merge_breaks(void)
829 stree
= pop_stree(&break_stack
);
830 merge_stree(&cur_stree
, stree
);
834 void __use_breaks(void)
836 free_stree(&cur_stree
);
837 cur_stree
= pop_stree(&break_stack
);
840 void __save_switch_states(struct expression
*switch_expr
)
842 push_rl(&remaining_cases
, __get_implied_values(switch_expr
));
843 push_stree(&switch_stack
, clone_stree(cur_stree
));
846 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
849 struct stree
*implied_stree
;
851 stree
= pop_stree(&switch_stack
);
852 implied_stree
= __implied_case_stree(switch_expr
, case_expr
, &remaining_cases
, &stree
);
853 merge_stree(&cur_stree
, implied_stree
);
854 free_stree(&implied_stree
);
855 push_stree(&switch_stack
, stree
);
858 void __discard_switches(void)
862 pop_rl(&remaining_cases
);
863 stree
= pop_stree(&switch_stack
);
867 void __push_default(void)
869 push_stree(&default_stack
, NULL
);
872 void __set_default(void)
874 set_state_stree_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
877 int __pop_default(void)
881 stree
= pop_stree(&default_stack
);
889 static struct named_stree
*alloc_named_stree(const char *name
, struct stree
*stree
)
891 struct named_stree
*named_stree
= __alloc_named_stree(0);
893 named_stree
->name
= (char *)name
;
894 named_stree
->stree
= stree
;
898 void __save_gotos(const char *name
)
900 struct stree
**stree
;
903 stree
= get_named_stree(goto_stack
, name
);
905 merge_stree(stree
, cur_stree
);
908 struct named_stree
*named_stree
;
910 clone
= clone_stree(cur_stree
);
911 named_stree
= alloc_named_stree(name
, clone
);
912 add_ptr_list(&goto_stack
, named_stree
);
916 void __merge_gotos(const char *name
)
918 struct stree
**stree
;
920 stree
= get_named_stree(goto_stack
, name
);
922 merge_stree(&cur_stree
, *stree
);