2 * sparse/smatch_states.c
4 * Copyright (C) 2006 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
11 * You have a lists of states. kernel = locked, foo = NULL, ...
12 * When you hit an if {} else {} statement then you swap the list
13 * of states for a different list of states. The lists are stored
16 * At the beginning of this file there are list of the stacks that
17 * we use. Each function in this file does something to one of
20 * So the smatch_flow.c understands code but it doesn't understand states.
21 * smatch_flow calls functions in this file. This file calls functions
22 * in smatch_slist.c which just has boring generic plumbing for handling
23 * state lists. But really it's this file where all the magic happens.
29 #include "smatch_slist.h"
30 #include "smatch_extra.h"
32 struct smatch_state undefined
= { .name
= "undefined" };
33 struct smatch_state merged
= { .name
= "merged" };
34 struct smatch_state true_state
= { .name
= "true" };
35 struct smatch_state false_state
= { .name
= "false" };
37 static struct state_list
*cur_slist
; /* current states */
39 static struct state_list_stack
*true_stack
; /* states after a t/f branch */
40 static struct state_list_stack
*false_stack
;
41 static struct state_list_stack
*pre_cond_stack
; /* states before a t/f branch */
43 static struct state_list_stack
*cond_true_stack
; /* states affected by a branch */
44 static struct state_list_stack
*cond_false_stack
;
46 static struct state_list_stack
*fake_cur_slist_stack
;
49 static struct state_list_stack
*break_stack
;
50 static struct state_list_stack
*switch_stack
;
51 static struct range_list_stack
*remaining_cases
;
52 static struct state_list_stack
*default_stack
;
53 static struct state_list_stack
*continue_stack
;
55 static struct named_stack
*goto_stack
;
57 static struct ptr_list
*backup
;
59 struct state_list_stack
*implied_pools
;
63 void __print_cur_slist(void)
65 __print_slist(cur_slist
);
68 static int in_declarations_bit(void)
70 struct statement
*tmp
;
72 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
73 if (tmp
->type
== STMT_DECLARATION
)
76 } END_FOR_EACH_PTR_REVERSE(tmp
);
82 static int reset_warnings
= 1;
90 if (in_declarations_bit())
93 /* option spammy turns on a noisier version of this */
94 if (reset_warnings
&& !option_spammy
)
95 sm_msg("info: ignoring unreachable code.");
101 struct sm_state
*set_state(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
103 struct sm_state
*ret
;
109 sm_msg("Smatch Internal Error: cur_slist is read only.");
112 struct smatch_state
*s
;
114 s
= get_state(owner
, name
, sym
);
116 printf("%d new state. name='%s' [%s] %s\n",
117 get_lineno(), name
, check_name(owner
), show_state(state
));
119 printf("%d state change name='%s' [%s] %s => %s\n",
120 get_lineno(), name
, check_name(owner
), show_state(s
),
124 if (owner
!= -1 && unreachable())
127 if (fake_cur_slist_stack
)
128 set_state_stack(&fake_cur_slist_stack
, owner
, name
, sym
, state
);
130 ret
= set_state_slist(&cur_slist
, owner
, name
, sym
, state
);
132 if (cond_true_stack
) {
133 set_state_stack(&cond_true_stack
, owner
, name
, sym
, state
);
134 set_state_stack(&cond_false_stack
, owner
, name
, sym
, state
);
139 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
143 struct sm_state
*ret
= NULL
;
145 expr
= strip_expr(expr
);
146 name
= expr_to_var_sym(expr
, &sym
);
149 ret
= set_state(owner
, name
, sym
, state
);
155 void __push_fake_cur_slist()
157 push_slist(&fake_cur_slist_stack
, NULL
);
158 __save_pre_cond_states();
161 struct state_list
*__pop_fake_cur_slist()
163 __use_pre_cond_states();
164 return pop_slist(&fake_cur_slist_stack
);
167 void __free_fake_cur_slist()
169 struct state_list
*slist
;
171 __use_pre_cond_states();
172 slist
= pop_slist(&fake_cur_slist_stack
);
176 void __set_fake_cur_slist_fast(struct state_list
*slist
)
178 push_slist(&pre_cond_stack
, cur_slist
);
183 void __pop_fake_cur_slist_fast()
185 cur_slist
= pop_slist(&pre_cond_stack
);
189 void __merge_slist_into_cur(struct state_list
*slist
)
192 struct sm_state
*orig
;
193 struct sm_state
*merged
;
195 FOR_EACH_PTR(slist
, sm
) {
196 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
198 merged
= merge_sm_states(orig
, sm
);
202 } END_FOR_EACH_PTR(sm
);
205 void __set_sm(struct sm_state
*sm
)
208 sm_msg("Smatch Internal Error: cur_slist is read only.");
211 struct smatch_state
*s
;
213 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
215 printf("%d new state. name='%s' [%s] %s\n",
216 get_lineno(), sm
->name
, check_name(sm
->owner
),
217 show_state(sm
->state
));
219 printf("%d state change name='%s' [%s] %s => %s\n",
220 get_lineno(), sm
->name
, check_name(sm
->owner
), show_state(s
),
221 show_state(sm
->state
));
227 if (fake_cur_slist_stack
)
228 overwrite_sm_state_stack(&fake_cur_slist_stack
, sm
);
230 overwrite_sm_state(&cur_slist
, sm
);
232 if (cond_true_stack
) {
233 overwrite_sm_state_stack(&cond_true_stack
, sm
);
234 overwrite_sm_state_stack(&cond_false_stack
, sm
);
238 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
240 return get_state_slist(cur_slist
, owner
, name
, sym
);
243 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
247 struct smatch_state
*ret
= NULL
;
249 expr
= strip_expr(expr
);
250 name
= expr_to_var_sym(expr
, &sym
);
253 ret
= get_state(owner
, name
, sym
);
259 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
261 struct sm_state
*sms
;
263 sms
= get_sm_state_slist(cur_slist
, owner
, name
, sym
);
265 return sms
->possible
;
269 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
273 struct state_list
*ret
= NULL
;
275 expr
= strip_expr(expr
);
276 name
= expr_to_var_sym(expr
, &sym
);
279 ret
= get_possible_states(owner
, name
, sym
);
285 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
287 return get_sm_state_slist(cur_slist
, owner
, name
, sym
);
290 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
294 struct sm_state
*ret
= NULL
;
296 expr
= strip_expr(expr
);
297 name
= expr_to_var_sym(expr
, &sym
);
300 ret
= get_sm_state(owner
, name
, sym
);
306 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
308 delete_state_slist(&cur_slist
, owner
, name
, sym
);
309 if (cond_true_stack
) {
310 delete_state_stack(&pre_cond_stack
, owner
, name
, sym
);
311 delete_state_stack(&cond_true_stack
, owner
, name
, sym
);
312 delete_state_stack(&cond_false_stack
, owner
, name
, sym
);
316 void delete_state_expr(int owner
, struct expression
*expr
)
321 expr
= strip_expr(expr
);
322 name
= expr_to_var_sym(expr
, &sym
);
325 delete_state(owner
, name
, sym
);
330 struct state_list
*get_all_states_slist(int owner
, struct state_list
*source
)
332 struct state_list
*slist
= NULL
;
333 struct sm_state
*tmp
;
335 FOR_EACH_PTR(source
, tmp
) {
336 if (tmp
->owner
== owner
)
337 add_ptr_list(&slist
, tmp
);
338 } END_FOR_EACH_PTR(tmp
);
343 struct state_list
*get_all_states(int owner
)
345 struct state_list
*slist
= NULL
;
346 struct sm_state
*tmp
;
348 FOR_EACH_PTR(cur_slist
, tmp
) {
349 if (tmp
->owner
== owner
)
350 add_ptr_list(&slist
, tmp
);
351 } END_FOR_EACH_PTR(tmp
);
356 int is_reachable(void)
363 struct state_list
*__get_cur_slist(void)
368 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
369 struct smatch_state
*true_state
,
370 struct smatch_state
*false_state
)
373 struct smatch_state
*tmp
;
375 tmp
= get_state(owner
, name
, sym
);
376 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
377 get_lineno(), name
, show_state(tmp
),
378 show_state(true_state
), show_state(false_state
));
384 if (!cond_false_stack
|| !cond_true_stack
) {
385 printf("Error: missing true/false stacks\n");
390 set_state_slist(&cur_slist
, owner
, name
, sym
, true_state
);
391 set_state_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
394 set_state_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
397 void set_true_false_states_expr(int owner
, struct expression
*expr
,
398 struct smatch_state
*true_state
,
399 struct smatch_state
*false_state
)
404 expr
= strip_expr(expr
);
405 name
= expr_to_var_sym(expr
, &sym
);
408 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
413 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
418 if (!cond_false_stack
|| !cond_true_stack
) {
419 printf("Error: missing true/false stacks\n");
424 overwrite_sm_state(&cur_slist
, true_sm
);
425 overwrite_sm_state_stack(&cond_true_stack
, true_sm
);
428 overwrite_sm_state_stack(&cond_false_stack
, false_sm
);
431 void nullify_path(void)
433 free_slist(&cur_slist
);
436 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
443 * At the start of every function we mark the path
444 * as unnull. That way there is always at least one state
445 * in the cur_slist until nullify_path is called. This
446 * is used in merge_slist() for the first null check.
448 void __unnullify_path(void)
450 set_state(-1, "unnull_path", NULL
, &true_state
);
453 int __path_is_null(void)
460 static void check_stack_free(struct state_list_stack
**stack
)
463 sm_msg("smatch internal error: stack not empty");
464 free_stack_and_slists(stack
);
468 void save_all_states(void)
470 __add_ptr_list(&backup
, cur_slist
, 0);
472 __add_ptr_list(&backup
, true_stack
, 0);
473 __add_ptr_list(&backup
, false_stack
, 0);
474 __add_ptr_list(&backup
, pre_cond_stack
, 0);
476 __add_ptr_list(&backup
, cond_true_stack
, 0);
477 __add_ptr_list(&backup
, cond_false_stack
, 0);
479 __add_ptr_list(&backup
, fake_cur_slist_stack
, 0);
481 __add_ptr_list(&backup
, break_stack
, 0);
482 __add_ptr_list(&backup
, switch_stack
, 0);
483 __add_ptr_list(&backup
, remaining_cases
, 0);
484 __add_ptr_list(&backup
, default_stack
, 0);
485 __add_ptr_list(&backup
, continue_stack
, 0);
487 __add_ptr_list(&backup
, goto_stack
, 0);
490 void nullify_all_states(void)
496 pre_cond_stack
= NULL
;
498 cond_true_stack
= NULL
;
499 cond_false_stack
= NULL
;
501 fake_cur_slist_stack
= NULL
;
505 remaining_cases
= NULL
;
506 default_stack
= NULL
;
507 continue_stack
= NULL
;
512 static void *pop_backup(void)
516 ret
= last_ptr_list(backup
);
517 delete_ptr_list_last(&backup
);
521 void restore_all_states(void)
523 goto_stack
= pop_backup();
525 continue_stack
= pop_backup();
526 default_stack
= pop_backup();
527 remaining_cases
= pop_backup();
528 switch_stack
= pop_backup();
529 break_stack
= pop_backup();
531 fake_cur_slist_stack
= pop_backup();
533 cond_false_stack
= pop_backup();
534 cond_true_stack
= pop_backup();
536 pre_cond_stack
= pop_backup();
537 false_stack
= pop_backup();
538 true_stack
= pop_backup();
540 cur_slist
= pop_backup();
543 void clear_all_states(void)
545 struct named_slist
*named_slist
;
548 check_stack_free(&true_stack
);
549 check_stack_free(&false_stack
);
550 check_stack_free(&pre_cond_stack
);
551 check_stack_free(&cond_true_stack
);
552 check_stack_free(&cond_false_stack
);
553 check_stack_free(&break_stack
);
554 check_stack_free(&switch_stack
);
555 check_stack_free(&continue_stack
);
556 free_stack_and_slists(&implied_pools
);
558 FOR_EACH_PTR(goto_stack
, named_slist
) {
559 free_slist(&named_slist
->slist
);
560 } END_FOR_EACH_PTR(named_slist
);
561 __free_ptr_list((struct ptr_list
**)&goto_stack
);
562 free_every_single_sm_state();
565 void __push_cond_stacks(void)
567 push_slist(&cond_true_stack
, NULL
);
568 push_slist(&cond_false_stack
, NULL
);
571 struct state_list
*__copy_cond_true_states(void)
573 struct state_list
*ret
;
575 ret
= pop_slist(&cond_true_stack
);
576 push_slist(&cond_true_stack
, clone_slist(ret
));
580 struct state_list
*__copy_cond_false_states(void)
582 struct state_list
*ret
;
584 ret
= pop_slist(&cond_false_stack
);
585 push_slist(&cond_false_stack
, clone_slist(ret
));
589 struct state_list
*__pop_cond_true_stack(void)
591 return pop_slist(&cond_true_stack
);
594 struct state_list
*__pop_cond_false_stack(void)
596 return pop_slist(&cond_false_stack
);
600 * This combines the pre cond states with either the true or false states.
602 * a = kmalloc() ; if (a !! foo(a)
603 * In the pre state a is possibly null. In the true state it is non null.
604 * In the false state it is null. Combine the pre and the false to get
605 * that when we call 'foo', 'a' is null.
607 static void __use_cond_stack(struct state_list_stack
**stack
)
609 struct state_list
*slist
;
611 free_slist(&cur_slist
);
613 cur_slist
= pop_slist(&pre_cond_stack
);
614 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
616 slist
= pop_slist(stack
);
617 overwrite_slist(slist
, &cur_slist
);
618 push_slist(stack
, slist
);
621 void __use_pre_cond_states(void)
623 free_slist(&cur_slist
);
624 cur_slist
= pop_slist(&pre_cond_stack
);
627 void __use_cond_true_states(void)
629 __use_cond_stack(&cond_true_stack
);
632 void __use_cond_false_states(void)
634 __use_cond_stack(&cond_false_stack
);
637 void __negate_cond_stacks(void)
639 struct state_list
*old_false
, *old_true
;
641 __use_cond_stack(&cond_false_stack
);
642 old_false
= pop_slist(&cond_false_stack
);
643 old_true
= pop_slist(&cond_true_stack
);
644 push_slist(&cond_false_stack
, old_true
);
645 push_slist(&cond_true_stack
, old_false
);
648 void __and_cond_states(void)
650 and_slist_stack(&cond_true_stack
);
651 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_false_stack
);
654 void __or_cond_states(void)
656 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_true_stack
);
657 and_slist_stack(&cond_false_stack
);
660 void __save_pre_cond_states(void)
662 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
665 void __discard_pre_cond_states(void)
667 struct state_list
*tmp
;
669 tmp
= pop_slist(&pre_cond_stack
);
673 void __use_cond_states(void)
675 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
677 pre
= pop_slist(&pre_cond_stack
);
678 pre_clone
= clone_slist(pre
);
680 true_states
= pop_slist(&cond_true_stack
);
681 overwrite_slist(true_states
, &pre
);
682 /* we use the true states right away */
683 free_slist(&cur_slist
);
686 false_states
= pop_slist(&cond_false_stack
);
687 overwrite_slist(false_states
, &pre_clone
);
688 push_slist(&false_stack
, pre_clone
);
691 void __push_true_states(void)
693 push_slist(&true_stack
, clone_slist(cur_slist
));
696 void __use_false_states(void)
698 free_slist(&cur_slist
);
699 cur_slist
= pop_slist(&false_stack
);
702 void __discard_false_states(void)
704 struct state_list
*slist
;
706 slist
= pop_slist(&false_stack
);
710 void __merge_false_states(void)
712 struct state_list
*slist
;
714 slist
= pop_slist(&false_stack
);
715 merge_slist(&cur_slist
, slist
);
719 void __merge_true_states(void)
721 struct state_list
*slist
;
723 slist
= pop_slist(&true_stack
);
724 merge_slist(&cur_slist
, slist
);
728 void __push_continues(void)
730 push_slist(&continue_stack
, NULL
);
733 void __discard_continues(void)
735 struct state_list
*slist
;
737 slist
= pop_slist(&continue_stack
);
741 void __process_continues(void)
743 struct state_list
*slist
;
745 slist
= pop_slist(&continue_stack
);
747 slist
= clone_slist(cur_slist
);
749 merge_slist(&slist
, cur_slist
);
751 push_slist(&continue_stack
, slist
);
754 static int top_slist_empty(struct state_list_stack
**stack
)
756 struct state_list
*tmp
;
759 tmp
= pop_slist(stack
);
762 push_slist(stack
, tmp
);
766 /* a silly loop does this: while(i--) { return; } */
767 void __warn_on_silly_pre_loops(void)
769 if (!__path_is_null())
771 if (!top_slist_empty(&continue_stack
))
773 if (!top_slist_empty(&break_stack
))
775 /* if the path was nullified before the loop, then we already
776 printed an error earlier */
777 if (top_slist_empty(&false_stack
))
779 sm_msg("info: loop could be replaced with if statement.");
782 void __merge_continues(void)
784 struct state_list
*slist
;
786 slist
= pop_slist(&continue_stack
);
787 merge_slist(&cur_slist
, slist
);
791 void __push_breaks(void)
793 push_slist(&break_stack
, NULL
);
796 void __process_breaks(void)
798 struct state_list
*slist
;
800 slist
= pop_slist(&break_stack
);
802 slist
= clone_slist(cur_slist
);
804 merge_slist(&slist
, cur_slist
);
806 push_slist(&break_stack
, slist
);
809 int __has_breaks(void)
811 struct state_list
*slist
;
814 slist
= pop_slist(&break_stack
);
816 push_slist(&break_stack
, slist
);
820 void __merge_breaks(void)
822 struct state_list
*slist
;
824 slist
= pop_slist(&break_stack
);
825 merge_slist(&cur_slist
, slist
);
829 void __use_breaks(void)
831 free_slist(&cur_slist
);
832 cur_slist
= pop_slist(&break_stack
);
835 void __save_switch_states(struct expression
*switch_expr
)
837 push_rl(&remaining_cases
, __get_implied_values(switch_expr
));
838 push_slist(&switch_stack
, clone_slist(cur_slist
));
841 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
843 struct state_list
*slist
;
844 struct state_list
*implied_slist
;
846 slist
= pop_slist(&switch_stack
);
847 implied_slist
= __implied_case_slist(switch_expr
, case_expr
, &remaining_cases
, &slist
);
848 merge_slist(&cur_slist
, implied_slist
);
849 free_slist(&implied_slist
);
850 push_slist(&switch_stack
, slist
);
853 void __discard_switches(void)
855 struct state_list
*slist
;
857 pop_rl(&remaining_cases
);
858 slist
= pop_slist(&switch_stack
);
862 void __push_default(void)
864 push_slist(&default_stack
, NULL
);
867 void __set_default(void)
869 set_state_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
872 int __pop_default(void)
874 struct state_list
*slist
;
876 slist
= pop_slist(&default_stack
);
884 static struct named_slist
*alloc_named_slist(const char *name
, struct state_list
*slist
)
886 struct named_slist
*named_slist
= __alloc_named_slist(0);
888 named_slist
->name
= (char *)name
;
889 named_slist
->slist
= slist
;
893 void __save_gotos(const char *name
)
895 struct state_list
**slist
;
896 struct state_list
*clone
;
898 slist
= get_slist_from_named_stack(goto_stack
, name
);
900 clone
= clone_slist(cur_slist
);
901 merge_slist(slist
, clone
);
905 struct named_slist
*named_slist
;
907 clone
= clone_slist(cur_slist
);
908 named_slist
= alloc_named_slist(name
, clone
);
909 add_ptr_list(&goto_stack
, named_slist
);
913 void __merge_gotos(const char *name
)
915 struct state_list
**slist
;
917 slist
= get_slist_from_named_stack(goto_stack
, name
);
919 merge_slist(&cur_slist
, *slist
);