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 struct state_list_stack
*implied_pools
;
60 void __print_cur_slist(void)
62 __print_slist(cur_slist
);
65 static int in_declarations_bit(void)
67 struct statement
*tmp
;
69 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
70 if (tmp
->type
== STMT_DECLARATION
)
73 } END_FOR_EACH_PTR_REVERSE(tmp
);
79 static int reset_warnings
= 1;
86 if (in_declarations_bit())
89 /* option spammy turns on a noisier version of this */
90 if (reset_warnings
&& !option_spammy
)
91 sm_msg("info: ignoring unreachable code.");
96 struct sm_state
*set_state(int owner
, const char *name
, struct symbol
*sym
, struct smatch_state
*state
)
104 struct smatch_state
*s
;
106 s
= get_state(owner
, name
, sym
);
108 printf("%d new state. name='%s' [%s] %s\n",
109 get_lineno(), name
, check_name(owner
), show_state(state
));
111 printf("%d state change name='%s' [%s] %s => %s\n",
112 get_lineno(), name
, check_name(owner
), show_state(s
),
116 if (owner
!= -1 && unreachable())
119 if (fake_cur_slist_stack
)
120 set_state_stack(&fake_cur_slist_stack
, owner
, name
, sym
, state
);
122 ret
= set_state_slist(&cur_slist
, owner
, name
, sym
, state
);
124 if (cond_true_stack
) {
125 set_state_stack(&cond_true_stack
, owner
, name
, sym
, state
);
126 set_state_stack(&cond_false_stack
, owner
, name
, sym
, state
);
131 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
135 struct sm_state
*ret
= NULL
;
137 expr
= strip_expr(expr
);
138 name
= expr_to_var_sym(expr
, &sym
);
141 ret
= set_state(owner
, name
, sym
, state
);
147 void __push_fake_cur_slist()
149 push_slist(&fake_cur_slist_stack
, NULL
);
150 __save_pre_cond_states();
153 struct state_list
*__pop_fake_cur_slist()
155 __use_pre_cond_states();
156 return pop_slist(&fake_cur_slist_stack
);
159 void __merge_slist_into_cur(struct state_list
*slist
)
162 struct sm_state
*orig
;
163 struct sm_state
*merged
;
165 FOR_EACH_PTR(slist
, sm
) {
166 orig
= get_sm_state(sm
->owner
, sm
->name
, sm
->sym
);
168 merged
= merge_sm_states(orig
, sm
);
172 } END_FOR_EACH_PTR(sm
);
175 void __set_sm(struct sm_state
*sm
)
178 struct smatch_state
*s
;
180 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
182 printf("%d new state. name='%s' [%s] %s\n",
183 get_lineno(), sm
->name
, check_name(sm
->owner
),
184 show_state(sm
->state
));
186 printf("%d state change name='%s' [%s] %s => %s\n",
187 get_lineno(), sm
->name
, check_name(sm
->owner
), show_state(s
),
188 show_state(sm
->state
));
194 if (fake_cur_slist_stack
)
195 overwrite_sm_state_stack(&fake_cur_slist_stack
, sm
);
197 overwrite_sm_state(&cur_slist
, sm
);
199 if (cond_true_stack
) {
200 overwrite_sm_state_stack(&cond_true_stack
, sm
);
201 overwrite_sm_state_stack(&cond_false_stack
, sm
);
205 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
207 return get_state_slist(cur_slist
, owner
, name
, sym
);
210 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
214 struct smatch_state
*ret
= NULL
;
216 expr
= strip_expr(expr
);
217 name
= expr_to_var_sym(expr
, &sym
);
220 ret
= get_state(owner
, name
, sym
);
226 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
228 struct sm_state
*sms
;
230 sms
= get_sm_state_slist(cur_slist
, owner
, name
, sym
);
232 return sms
->possible
;
236 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
240 struct state_list
*ret
= NULL
;
242 expr
= strip_expr(expr
);
243 name
= expr_to_var_sym(expr
, &sym
);
246 ret
= get_possible_states(owner
, name
, sym
);
252 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
254 return get_sm_state_slist(cur_slist
, owner
, name
, sym
);
257 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
261 struct sm_state
*ret
= NULL
;
263 expr
= strip_expr(expr
);
264 name
= expr_to_var_sym(expr
, &sym
);
267 ret
= get_sm_state(owner
, name
, sym
);
273 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
275 delete_state_slist(&cur_slist
, owner
, name
, sym
);
276 if (cond_true_stack
) {
277 delete_state_stack(&pre_cond_stack
, owner
, name
, sym
);
278 delete_state_stack(&cond_true_stack
, owner
, name
, sym
);
279 delete_state_stack(&cond_false_stack
, owner
, name
, sym
);
283 void delete_state_expr(int owner
, struct expression
*expr
)
288 expr
= strip_expr(expr
);
289 name
= expr_to_var_sym(expr
, &sym
);
292 delete_state(owner
, name
, sym
);
297 struct state_list
*get_all_states_slist(int owner
, struct state_list
*source
)
299 struct state_list
*slist
= NULL
;
300 struct sm_state
*tmp
;
302 FOR_EACH_PTR(source
, tmp
) {
303 if (tmp
->owner
== owner
)
304 add_ptr_list(&slist
, tmp
);
305 } END_FOR_EACH_PTR(tmp
);
310 struct state_list
*get_all_states(int owner
)
312 struct state_list
*slist
= NULL
;
313 struct sm_state
*tmp
;
315 FOR_EACH_PTR(cur_slist
, tmp
) {
316 if (tmp
->owner
== owner
)
317 add_ptr_list(&slist
, tmp
);
318 } END_FOR_EACH_PTR(tmp
);
323 int is_reachable(void)
330 struct state_list
*__get_cur_slist(void)
335 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
336 struct smatch_state
*true_state
,
337 struct smatch_state
*false_state
)
340 struct smatch_state
*tmp
;
342 tmp
= get_state(owner
, name
, sym
);
343 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
344 get_lineno(), name
, show_state(tmp
),
345 show_state(true_state
), show_state(false_state
));
351 if (!cond_false_stack
|| !cond_true_stack
) {
352 printf("Error: missing true/false stacks\n");
357 set_state_slist(&cur_slist
, owner
, name
, sym
, true_state
);
358 set_state_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
361 set_state_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
364 void set_true_false_states_expr(int owner
, struct expression
*expr
,
365 struct smatch_state
*true_state
,
366 struct smatch_state
*false_state
)
371 expr
= strip_expr(expr
);
372 name
= expr_to_var_sym(expr
, &sym
);
375 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
380 void __set_true_false_sm(struct sm_state
*true_sm
, struct sm_state
*false_sm
)
385 if (!cond_false_stack
|| !cond_true_stack
) {
386 printf("Error: missing true/false stacks\n");
391 overwrite_sm_state(&cur_slist
, true_sm
);
392 overwrite_sm_state_stack(&cond_true_stack
, true_sm
);
395 overwrite_sm_state_stack(&cond_false_stack
, false_sm
);
398 void nullify_path(void)
400 free_slist(&cur_slist
);
403 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
410 * At the start of every function we mark the path
411 * as unnull. That way there is always at least one state
412 * in the cur_slist until nullify_path is called. This
413 * is used in merge_slist() for the first null check.
415 void __unnullify_path(void)
417 set_state(-1, "unnull_path", NULL
, &true_state
);
420 int __path_is_null(void)
427 static void check_stack_free(struct state_list_stack
**stack
)
430 sm_msg("smatch internal error: stack not empty");
431 free_stack_and_slists(stack
);
435 void clear_all_states(void)
437 struct named_slist
*named_slist
;
440 check_stack_free(&true_stack
);
441 check_stack_free(&false_stack
);
442 check_stack_free(&pre_cond_stack
);
443 check_stack_free(&cond_true_stack
);
444 check_stack_free(&cond_false_stack
);
445 check_stack_free(&break_stack
);
446 check_stack_free(&switch_stack
);
447 check_stack_free(&continue_stack
);
448 free_stack_and_slists(&implied_pools
);
450 FOR_EACH_PTR(goto_stack
, named_slist
) {
451 free_slist(&named_slist
->slist
);
452 } END_FOR_EACH_PTR(named_slist
);
453 __free_ptr_list((struct ptr_list
**)&goto_stack
);
454 free_every_single_sm_state();
457 void __push_cond_stacks(void)
459 push_slist(&cond_true_stack
, NULL
);
460 push_slist(&cond_false_stack
, NULL
);
463 struct state_list
*__copy_cond_true_states(void)
465 struct state_list
*ret
;
467 ret
= pop_slist(&cond_true_stack
);
468 push_slist(&cond_true_stack
, clone_slist(ret
));
472 struct state_list
*__copy_cond_false_states(void)
474 struct state_list
*ret
;
476 ret
= pop_slist(&cond_false_stack
);
477 push_slist(&cond_false_stack
, clone_slist(ret
));
481 struct state_list
*__pop_cond_true_stack(void)
483 return pop_slist(&cond_true_stack
);
486 struct state_list
*__pop_cond_false_stack(void)
488 return pop_slist(&cond_false_stack
);
492 * This combines the pre cond states with either the true or false states.
494 * a = kmalloc() ; if (a !! foo(a)
495 * In the pre state a is possibly null. In the true state it is non null.
496 * In the false state it is null. Combine the pre and the false to get
497 * that when we call 'foo', 'a' is null.
499 static void __use_cond_stack(struct state_list_stack
**stack
)
501 struct state_list
*slist
;
503 free_slist(&cur_slist
);
505 cur_slist
= pop_slist(&pre_cond_stack
);
506 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
508 slist
= pop_slist(stack
);
509 overwrite_slist(slist
, &cur_slist
);
510 push_slist(stack
, slist
);
513 void __use_pre_cond_states(void)
515 free_slist(&cur_slist
);
516 cur_slist
= pop_slist(&pre_cond_stack
);
519 void __use_cond_true_states(void)
521 __use_cond_stack(&cond_true_stack
);
524 void __use_cond_false_states(void)
526 __use_cond_stack(&cond_false_stack
);
529 void __negate_cond_stacks(void)
531 struct state_list
*old_false
, *old_true
;
533 __use_cond_stack(&cond_false_stack
);
534 old_false
= pop_slist(&cond_false_stack
);
535 old_true
= pop_slist(&cond_true_stack
);
536 push_slist(&cond_false_stack
, old_true
);
537 push_slist(&cond_true_stack
, old_false
);
540 void __and_cond_states(void)
542 and_slist_stack(&cond_true_stack
);
543 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_false_stack
);
546 void __or_cond_states(void)
548 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_true_stack
);
549 and_slist_stack(&cond_false_stack
);
552 void __save_pre_cond_states(void)
554 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
557 void __discard_pre_cond_states(void)
559 struct state_list
*tmp
;
561 tmp
= pop_slist(&pre_cond_stack
);
565 void __use_cond_states(void)
567 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
569 pre
= pop_slist(&pre_cond_stack
);
570 pre_clone
= clone_slist(pre
);
572 true_states
= pop_slist(&cond_true_stack
);
573 overwrite_slist(true_states
, &pre
);
574 /* we use the true states right away */
575 free_slist(&cur_slist
);
578 false_states
= pop_slist(&cond_false_stack
);
579 overwrite_slist(false_states
, &pre_clone
);
580 push_slist(&false_stack
, pre_clone
);
583 void __push_true_states(void)
585 push_slist(&true_stack
, clone_slist(cur_slist
));
588 void __use_false_states(void)
590 free_slist(&cur_slist
);
591 cur_slist
= pop_slist(&false_stack
);
594 void __discard_false_states(void)
596 struct state_list
*slist
;
598 slist
= pop_slist(&false_stack
);
602 void __merge_false_states(void)
604 struct state_list
*slist
;
606 slist
= pop_slist(&false_stack
);
607 merge_slist(&cur_slist
, slist
);
611 void __merge_true_states(void)
613 struct state_list
*slist
;
615 slist
= pop_slist(&true_stack
);
616 merge_slist(&cur_slist
, slist
);
620 void __push_continues(void)
622 push_slist(&continue_stack
, NULL
);
625 void __discard_continues(void)
627 struct state_list
*slist
;
629 slist
= pop_slist(&continue_stack
);
633 void __process_continues(void)
635 struct state_list
*slist
;
637 slist
= pop_slist(&continue_stack
);
639 slist
= clone_slist(cur_slist
);
641 merge_slist(&slist
, cur_slist
);
643 push_slist(&continue_stack
, slist
);
646 static int top_slist_empty(struct state_list_stack
**stack
)
648 struct state_list
*tmp
;
651 tmp
= pop_slist(stack
);
654 push_slist(stack
, tmp
);
658 /* a silly loop does this: while(i--) { return; } */
659 void __warn_on_silly_pre_loops(void)
661 if (!__path_is_null())
663 if (!top_slist_empty(&continue_stack
))
665 if (!top_slist_empty(&break_stack
))
667 /* if the path was nullified before the loop, then we already
668 printed an error earlier */
669 if (top_slist_empty(&false_stack
))
671 sm_msg("info: loop could be replaced with if statement.");
674 void __merge_continues(void)
676 struct state_list
*slist
;
678 slist
= pop_slist(&continue_stack
);
679 merge_slist(&cur_slist
, slist
);
683 void __push_breaks(void)
685 push_slist(&break_stack
, NULL
);
688 void __process_breaks(void)
690 struct state_list
*slist
;
692 slist
= pop_slist(&break_stack
);
694 slist
= clone_slist(cur_slist
);
696 merge_slist(&slist
, cur_slist
);
698 push_slist(&break_stack
, slist
);
701 int __has_breaks(void)
703 struct state_list
*slist
;
706 slist
= pop_slist(&break_stack
);
708 push_slist(&break_stack
, slist
);
712 void __merge_breaks(void)
714 struct state_list
*slist
;
716 slist
= pop_slist(&break_stack
);
717 merge_slist(&cur_slist
, slist
);
721 void __use_breaks(void)
723 free_slist(&cur_slist
);
724 cur_slist
= pop_slist(&break_stack
);
727 void __save_switch_states(struct expression
*switch_expr
)
729 push_rl(&remaining_cases
, __get_implied_values(switch_expr
));
730 push_slist(&switch_stack
, clone_slist(cur_slist
));
733 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
735 struct state_list
*slist
;
736 struct state_list
*implied_slist
;
738 slist
= pop_slist(&switch_stack
);
739 implied_slist
= __implied_case_slist(switch_expr
, case_expr
, &remaining_cases
, &slist
);
740 merge_slist(&cur_slist
, implied_slist
);
741 free_slist(&implied_slist
);
742 push_slist(&switch_stack
, slist
);
745 void __discard_switches(void)
747 struct state_list
*slist
;
749 pop_rl(&remaining_cases
);
750 slist
= pop_slist(&switch_stack
);
754 void __push_default(void)
756 push_slist(&default_stack
, NULL
);
759 void __set_default(void)
761 set_state_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
764 int __pop_default(void)
766 struct state_list
*slist
;
768 slist
= pop_slist(&default_stack
);
776 static struct named_slist
*alloc_named_slist(const char *name
, struct state_list
*slist
)
778 struct named_slist
*named_slist
= __alloc_named_slist(0);
780 named_slist
->name
= (char *)name
;
781 named_slist
->slist
= slist
;
785 void __save_gotos(const char *name
)
787 struct state_list
**slist
;
788 struct state_list
*clone
;
790 slist
= get_slist_from_named_stack(goto_stack
, name
);
792 clone
= clone_slist(cur_slist
);
793 merge_slist(slist
, clone
);
797 struct named_slist
*named_slist
;
799 clone
= clone_slist(cur_slist
);
800 named_slist
= alloc_named_slist(name
, clone
);
801 add_ptr_list(&goto_stack
, named_slist
);
805 void __merge_gotos(const char *name
)
807 struct state_list
**slist
;
809 slist
= get_slist_from_named_stack(goto_stack
, name
);
811 merge_slist(&cur_slist
, *slist
);