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
;
48 static struct state_list_stack
*break_stack
;
49 static struct state_list_stack
*switch_stack
;
50 static struct range_list_stack
*remaining_cases
;
51 static struct state_list_stack
*default_stack
;
52 static struct state_list_stack
*continue_stack
;
54 static struct named_stack
*goto_stack
;
56 static struct ptr_list
*backup
;
58 struct state_list_stack
*implied_pools
;
62 void __print_cur_slist(void)
64 __print_slist(cur_slist
);
67 static int in_declarations_bit(void)
69 struct statement
*tmp
;
71 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
72 if (tmp
->type
== STMT_DECLARATION
)
75 } END_FOR_EACH_PTR_REVERSE(tmp
);
81 static int reset_warnings
= 1;
89 if (in_declarations_bit())
92 /* option spammy turns on a noisier version of this */
93 if (reset_warnings
&& !option_spammy
)
94 sm_msg("info: ignoring unreachable code.");
100 struct sm_state
*set_state(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
102 struct sm_state
*ret
;
108 struct smatch_state
*s
;
110 s
= get_state(owner
, name
, sym
);
112 printf("%d new state. name='%s' [%s] %s\n",
113 get_lineno(), name
, check_name(owner
), show_state(state
));
115 printf("%d state change name='%s' [%s] %s => %s\n",
116 get_lineno(), name
, check_name(owner
), show_state(s
),
120 if (owner
!= -1 && unreachable())
123 if (fake_cur_slist_stack
)
124 set_state_stack(&fake_cur_slist_stack
, owner
, name
, sym
, state
);
126 ret
= set_state_slist(&cur_slist
, owner
, name
, sym
, state
);
128 if (cond_true_stack
) {
129 set_state_stack(&cond_true_stack
, owner
, name
, sym
, state
);
130 set_state_stack(&cond_false_stack
, owner
, name
, sym
, state
);
135 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
139 struct sm_state
*ret
= NULL
;
141 expr
= strip_expr(expr
);
142 name
= expr_to_var_sym(expr
, &sym
);
145 ret
= set_state(owner
, name
, sym
, state
);
151 void __push_fake_cur_slist()
153 push_slist(&fake_cur_slist_stack
, NULL
);
154 __save_pre_cond_states();
157 void __set_fake_cur_slist(struct state_list
*slist
)
159 push_slist(&fake_cur_slist_stack
, NULL
);
160 __save_pre_cond_states();
161 cur_slist
= clone_slist(slist
);
164 struct state_list
*__pop_fake_cur_slist()
166 __use_pre_cond_states();
167 return pop_slist(&fake_cur_slist_stack
);
170 void __free_fake_cur_slist()
172 struct state_list
*slist
;
174 __use_pre_cond_states();
175 slist
= pop_slist(&fake_cur_slist_stack
);
179 void __merge_slist_into_cur(struct state_list
*slist
)
182 struct sm_state
*orig
;
183 struct sm_state
*merged
;
185 FOR_EACH_PTR(slist
, sm
) {
186 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
188 merged
= merge_sm_states(orig
, sm
);
192 } END_FOR_EACH_PTR(sm
);
195 void __set_sm(struct sm_state
*sm
)
198 struct smatch_state
*s
;
200 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
202 printf("%d new state. name='%s' [%s] %s\n",
203 get_lineno(), sm
->name
, check_name(sm
->owner
),
204 show_state(sm
->state
));
206 printf("%d state change name='%s' [%s] %s => %s\n",
207 get_lineno(), sm
->name
, check_name(sm
->owner
), show_state(s
),
208 show_state(sm
->state
));
214 if (fake_cur_slist_stack
)
215 overwrite_sm_state_stack(&fake_cur_slist_stack
, sm
);
217 overwrite_sm_state(&cur_slist
, sm
);
219 if (cond_true_stack
) {
220 overwrite_sm_state_stack(&cond_true_stack
, sm
);
221 overwrite_sm_state_stack(&cond_false_stack
, sm
);
225 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
227 return get_state_slist(cur_slist
, owner
, name
, sym
);
230 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
234 struct smatch_state
*ret
= NULL
;
236 expr
= strip_expr(expr
);
237 name
= expr_to_var_sym(expr
, &sym
);
240 ret
= get_state(owner
, name
, sym
);
246 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
248 struct sm_state
*sms
;
250 sms
= get_sm_state_slist(cur_slist
, owner
, name
, sym
);
252 return sms
->possible
;
256 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
260 struct state_list
*ret
= NULL
;
262 expr
= strip_expr(expr
);
263 name
= expr_to_var_sym(expr
, &sym
);
266 ret
= get_possible_states(owner
, name
, sym
);
272 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
274 return get_sm_state_slist(cur_slist
, owner
, name
, sym
);
277 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
281 struct sm_state
*ret
= NULL
;
283 expr
= strip_expr(expr
);
284 name
= expr_to_var_sym(expr
, &sym
);
287 ret
= get_sm_state(owner
, name
, sym
);
293 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
295 delete_state_slist(&cur_slist
, owner
, name
, sym
);
296 if (cond_true_stack
) {
297 delete_state_stack(&pre_cond_stack
, owner
, name
, sym
);
298 delete_state_stack(&cond_true_stack
, owner
, name
, sym
);
299 delete_state_stack(&cond_false_stack
, owner
, name
, sym
);
303 void delete_state_expr(int owner
, struct expression
*expr
)
308 expr
= strip_expr(expr
);
309 name
= expr_to_var_sym(expr
, &sym
);
312 delete_state(owner
, name
, sym
);
317 struct state_list
*get_all_states_slist(int owner
, struct state_list
*source
)
319 struct state_list
*slist
= NULL
;
320 struct sm_state
*tmp
;
322 FOR_EACH_PTR(source
, tmp
) {
323 if (tmp
->owner
== owner
)
324 add_ptr_list(&slist
, tmp
);
325 } END_FOR_EACH_PTR(tmp
);
330 struct state_list
*get_all_states(int owner
)
332 struct state_list
*slist
= NULL
;
333 struct sm_state
*tmp
;
335 FOR_EACH_PTR(cur_slist
, tmp
) {
336 if (tmp
->owner
== owner
)
337 add_ptr_list(&slist
, tmp
);
338 } END_FOR_EACH_PTR(tmp
);
343 int is_reachable(void)
350 struct state_list
*__get_cur_slist(void)
355 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
356 struct smatch_state
*true_state
,
357 struct smatch_state
*false_state
)
360 struct smatch_state
*tmp
;
362 tmp
= get_state(owner
, name
, sym
);
363 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
364 get_lineno(), name
, show_state(tmp
),
365 show_state(true_state
), show_state(false_state
));
371 if (!cond_false_stack
|| !cond_true_stack
) {
372 printf("Error: missing true/false stacks\n");
377 set_state_slist(&cur_slist
, owner
, name
, sym
, true_state
);
378 set_state_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
381 set_state_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
384 void set_true_false_states_expr(int owner
, struct expression
*expr
,
385 struct smatch_state
*true_state
,
386 struct smatch_state
*false_state
)
391 expr
= strip_expr(expr
);
392 name
= expr_to_var_sym(expr
, &sym
);
395 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
400 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
405 if (!cond_false_stack
|| !cond_true_stack
) {
406 printf("Error: missing true/false stacks\n");
411 overwrite_sm_state(&cur_slist
, true_sm
);
412 overwrite_sm_state_stack(&cond_true_stack
, true_sm
);
415 overwrite_sm_state_stack(&cond_false_stack
, false_sm
);
418 void nullify_path(void)
420 free_slist(&cur_slist
);
423 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
430 * At the start of every function we mark the path
431 * as unnull. That way there is always at least one state
432 * in the cur_slist until nullify_path is called. This
433 * is used in merge_slist() for the first null check.
435 void __unnullify_path(void)
437 set_state(-1, "unnull_path", NULL
, &true_state
);
440 int __path_is_null(void)
447 static void check_stack_free(struct state_list_stack
**stack
)
450 sm_msg("smatch internal error: stack not empty");
451 free_stack_and_slists(stack
);
455 void save_all_states(void)
457 __add_ptr_list(&backup
, cur_slist
, 0);
459 __add_ptr_list(&backup
, true_stack
, 0);
460 __add_ptr_list(&backup
, false_stack
, 0);
461 __add_ptr_list(&backup
, pre_cond_stack
, 0);
463 __add_ptr_list(&backup
, cond_true_stack
, 0);
464 __add_ptr_list(&backup
, cond_false_stack
, 0);
466 __add_ptr_list(&backup
, fake_cur_slist_stack
, 0);
468 __add_ptr_list(&backup
, break_stack
, 0);
469 __add_ptr_list(&backup
, switch_stack
, 0);
470 __add_ptr_list(&backup
, remaining_cases
, 0);
471 __add_ptr_list(&backup
, default_stack
, 0);
472 __add_ptr_list(&backup
, continue_stack
, 0);
474 __add_ptr_list(&backup
, goto_stack
, 0);
477 void nullify_all_states(void)
483 pre_cond_stack
= NULL
;
485 cond_true_stack
= NULL
;
486 cond_false_stack
= NULL
;
488 fake_cur_slist_stack
= NULL
;
492 remaining_cases
= NULL
;
493 default_stack
= NULL
;
494 continue_stack
= NULL
;
499 static void *pop_backup(void)
503 ret
= last_ptr_list(backup
);
504 delete_ptr_list_last(&backup
);
508 void restore_all_states(void)
510 goto_stack
= pop_backup();
512 continue_stack
= pop_backup();
513 default_stack
= pop_backup();
514 remaining_cases
= pop_backup();
515 switch_stack
= pop_backup();
516 break_stack
= pop_backup();
518 fake_cur_slist_stack
= pop_backup();
520 cond_false_stack
= pop_backup();
521 cond_true_stack
= pop_backup();
523 pre_cond_stack
= pop_backup();
524 false_stack
= pop_backup();
525 true_stack
= pop_backup();
527 cur_slist
= pop_backup();
530 void clear_all_states(void)
532 struct named_slist
*named_slist
;
535 check_stack_free(&true_stack
);
536 check_stack_free(&false_stack
);
537 check_stack_free(&pre_cond_stack
);
538 check_stack_free(&cond_true_stack
);
539 check_stack_free(&cond_false_stack
);
540 check_stack_free(&break_stack
);
541 check_stack_free(&switch_stack
);
542 check_stack_free(&continue_stack
);
543 free_stack_and_slists(&implied_pools
);
545 FOR_EACH_PTR(goto_stack
, named_slist
) {
546 free_slist(&named_slist
->slist
);
547 } END_FOR_EACH_PTR(named_slist
);
548 __free_ptr_list((struct ptr_list
**)&goto_stack
);
549 free_every_single_sm_state();
552 void __push_cond_stacks(void)
554 push_slist(&cond_true_stack
, NULL
);
555 push_slist(&cond_false_stack
, NULL
);
558 struct state_list
*__copy_cond_true_states(void)
560 struct state_list
*ret
;
562 ret
= pop_slist(&cond_true_stack
);
563 push_slist(&cond_true_stack
, clone_slist(ret
));
567 struct state_list
*__copy_cond_false_states(void)
569 struct state_list
*ret
;
571 ret
= pop_slist(&cond_false_stack
);
572 push_slist(&cond_false_stack
, clone_slist(ret
));
576 struct state_list
*__pop_cond_true_stack(void)
578 return pop_slist(&cond_true_stack
);
581 struct state_list
*__pop_cond_false_stack(void)
583 return pop_slist(&cond_false_stack
);
587 * This combines the pre cond states with either the true or false states.
589 * a = kmalloc() ; if (a !! foo(a)
590 * In the pre state a is possibly null. In the true state it is non null.
591 * In the false state it is null. Combine the pre and the false to get
592 * that when we call 'foo', 'a' is null.
594 static void __use_cond_stack(struct state_list_stack
**stack
)
596 struct state_list
*slist
;
598 free_slist(&cur_slist
);
600 cur_slist
= pop_slist(&pre_cond_stack
);
601 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
603 slist
= pop_slist(stack
);
604 overwrite_slist(slist
, &cur_slist
);
605 push_slist(stack
, slist
);
608 void __use_pre_cond_states(void)
610 free_slist(&cur_slist
);
611 cur_slist
= pop_slist(&pre_cond_stack
);
614 void __use_cond_true_states(void)
616 __use_cond_stack(&cond_true_stack
);
619 void __use_cond_false_states(void)
621 __use_cond_stack(&cond_false_stack
);
624 void __negate_cond_stacks(void)
626 struct state_list
*old_false
, *old_true
;
628 __use_cond_stack(&cond_false_stack
);
629 old_false
= pop_slist(&cond_false_stack
);
630 old_true
= pop_slist(&cond_true_stack
);
631 push_slist(&cond_false_stack
, old_true
);
632 push_slist(&cond_true_stack
, old_false
);
635 void __and_cond_states(void)
637 and_slist_stack(&cond_true_stack
);
638 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_false_stack
);
641 void __or_cond_states(void)
643 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_true_stack
);
644 and_slist_stack(&cond_false_stack
);
647 void __save_pre_cond_states(void)
649 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
652 void __discard_pre_cond_states(void)
654 struct state_list
*tmp
;
656 tmp
= pop_slist(&pre_cond_stack
);
660 void __use_cond_states(void)
662 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
664 pre
= pop_slist(&pre_cond_stack
);
665 pre_clone
= clone_slist(pre
);
667 true_states
= pop_slist(&cond_true_stack
);
668 overwrite_slist(true_states
, &pre
);
669 /* we use the true states right away */
670 free_slist(&cur_slist
);
673 false_states
= pop_slist(&cond_false_stack
);
674 overwrite_slist(false_states
, &pre_clone
);
675 push_slist(&false_stack
, pre_clone
);
678 void __push_true_states(void)
680 push_slist(&true_stack
, clone_slist(cur_slist
));
683 void __use_false_states(void)
685 free_slist(&cur_slist
);
686 cur_slist
= pop_slist(&false_stack
);
689 void __discard_false_states(void)
691 struct state_list
*slist
;
693 slist
= pop_slist(&false_stack
);
697 void __merge_false_states(void)
699 struct state_list
*slist
;
701 slist
= pop_slist(&false_stack
);
702 merge_slist(&cur_slist
, slist
);
706 void __merge_true_states(void)
708 struct state_list
*slist
;
710 slist
= pop_slist(&true_stack
);
711 merge_slist(&cur_slist
, slist
);
715 void __push_continues(void)
717 push_slist(&continue_stack
, NULL
);
720 void __discard_continues(void)
722 struct state_list
*slist
;
724 slist
= pop_slist(&continue_stack
);
728 void __process_continues(void)
730 struct state_list
*slist
;
732 slist
= pop_slist(&continue_stack
);
734 slist
= clone_slist(cur_slist
);
736 merge_slist(&slist
, cur_slist
);
738 push_slist(&continue_stack
, slist
);
741 static int top_slist_empty(struct state_list_stack
**stack
)
743 struct state_list
*tmp
;
746 tmp
= pop_slist(stack
);
749 push_slist(stack
, tmp
);
753 /* a silly loop does this: while(i--) { return; } */
754 void __warn_on_silly_pre_loops(void)
756 if (!__path_is_null())
758 if (!top_slist_empty(&continue_stack
))
760 if (!top_slist_empty(&break_stack
))
762 /* if the path was nullified before the loop, then we already
763 printed an error earlier */
764 if (top_slist_empty(&false_stack
))
766 sm_msg("info: loop could be replaced with if statement.");
769 void __merge_continues(void)
771 struct state_list
*slist
;
773 slist
= pop_slist(&continue_stack
);
774 merge_slist(&cur_slist
, slist
);
778 void __push_breaks(void)
780 push_slist(&break_stack
, NULL
);
783 void __process_breaks(void)
785 struct state_list
*slist
;
787 slist
= pop_slist(&break_stack
);
789 slist
= clone_slist(cur_slist
);
791 merge_slist(&slist
, cur_slist
);
793 push_slist(&break_stack
, slist
);
796 int __has_breaks(void)
798 struct state_list
*slist
;
801 slist
= pop_slist(&break_stack
);
803 push_slist(&break_stack
, slist
);
807 void __merge_breaks(void)
809 struct state_list
*slist
;
811 slist
= pop_slist(&break_stack
);
812 merge_slist(&cur_slist
, slist
);
816 void __use_breaks(void)
818 free_slist(&cur_slist
);
819 cur_slist
= pop_slist(&break_stack
);
822 void __save_switch_states(struct expression
*switch_expr
)
824 push_rl(&remaining_cases
, __get_implied_values(switch_expr
));
825 push_slist(&switch_stack
, clone_slist(cur_slist
));
828 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
830 struct state_list
*slist
;
831 struct state_list
*implied_slist
;
833 slist
= pop_slist(&switch_stack
);
834 implied_slist
= __implied_case_slist(switch_expr
, case_expr
, &remaining_cases
, &slist
);
835 merge_slist(&cur_slist
, implied_slist
);
836 free_slist(&implied_slist
);
837 push_slist(&switch_stack
, slist
);
840 void __discard_switches(void)
842 struct state_list
*slist
;
844 pop_rl(&remaining_cases
);
845 slist
= pop_slist(&switch_stack
);
849 void __push_default(void)
851 push_slist(&default_stack
, NULL
);
854 void __set_default(void)
856 set_state_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
859 int __pop_default(void)
861 struct state_list
*slist
;
863 slist
= pop_slist(&default_stack
);
871 static struct named_slist
*alloc_named_slist(const char *name
, struct state_list
*slist
)
873 struct named_slist
*named_slist
= __alloc_named_slist(0);
875 named_slist
->name
= (char *)name
;
876 named_slist
->slist
= slist
;
880 void __save_gotos(const char *name
)
882 struct state_list
**slist
;
883 struct state_list
*clone
;
885 slist
= get_slist_from_named_stack(goto_stack
, name
);
887 clone
= clone_slist(cur_slist
);
888 merge_slist(slist
, clone
);
892 struct named_slist
*named_slist
;
894 clone
= clone_slist(cur_slist
);
895 named_slist
= alloc_named_slist(name
, clone
);
896 add_ptr_list(&goto_stack
, named_slist
);
900 void __merge_gotos(const char *name
)
902 struct state_list
**slist
;
904 slist
= get_slist_from_named_stack(goto_stack
, name
);
906 merge_slist(&cur_slist
, *slist
);