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
;
47 struct state_list
*__fake_cur_slist
= NULL
;
48 int __fake_conditions
= 0;
49 struct state_list
*__fake_cond_true
= NULL
;
50 struct state_list
*__fake_cond_false
= NULL
;
52 static struct state_list_stack
*break_stack
;
53 static struct state_list_stack
*switch_stack
;
54 static struct range_list_stack
*remaining_cases
;
55 static struct state_list_stack
*default_stack
;
56 static struct state_list_stack
*continue_stack
;
58 static struct named_stack
*goto_stack
;
60 struct state_list_stack
*implied_pools
;
64 void __print_cur_slist(void)
66 __print_slist(cur_slist
);
69 static int in_declarations_bit(void)
71 struct statement
*tmp
;
73 FOR_EACH_PTR_REVERSE(big_statement_stack
, tmp
) {
74 if (tmp
->type
== STMT_DECLARATION
)
77 } END_FOR_EACH_PTR_REVERSE(tmp
);
83 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.");
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 __use_default_modification_hook(owner
, name
);
126 return set_state_slist(&__fake_cur_slist
, owner
, name
, sym
, state
);
129 ret
= set_state_slist(&cur_slist
, owner
, name
, sym
, state
);
131 if (cond_true_stack
) {
132 set_state_stack(&cond_true_stack
, owner
, name
, sym
, state
);
133 set_state_stack(&cond_false_stack
, owner
, name
, sym
, state
);
138 struct sm_state
*set_state_expr(int owner
, struct expression
*expr
, struct smatch_state
*state
)
142 struct sm_state
*ret
= NULL
;
144 expr
= strip_expr(expr
);
145 name
= get_variable_from_expr(expr
, &sym
);
148 ret
= set_state(owner
, name
, sym
, state
);
154 void __set_state(struct sm_state
*sm
)
157 struct smatch_state
*s
;
159 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
161 printf("%d new state. name='%s' [%s] %s\n",
162 get_lineno(), sm
->name
, check_name(sm
->owner
),
163 show_state(sm
->state
));
165 printf("%d state change name='%s' [%s] %s => %s\n",
166 get_lineno(), sm
->name
, check_name(sm
->owner
), show_state(s
),
167 show_state(sm
->state
));
173 overwrite_sm_state(&cur_slist
, sm
);
175 if (cond_true_stack
) {
176 overwrite_sm_state_stack(&cond_true_stack
, sm
);
177 overwrite_sm_state_stack(&cond_false_stack
, sm
);
181 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
183 return get_state_slist(cur_slist
, owner
, name
, sym
);
186 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
190 struct smatch_state
*ret
= NULL
;
192 expr
= strip_expr(expr
);
193 name
= get_variable_from_expr(expr
, &sym
);
196 ret
= get_state(owner
, name
, sym
);
202 struct state_list
*get_possible_states(int owner
, const char *name
, struct symbol
*sym
)
204 struct sm_state
*sms
;
206 sms
= get_sm_state_slist(cur_slist
, owner
, name
, sym
);
208 return sms
->possible
;
212 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
216 struct state_list
*ret
= NULL
;
218 expr
= strip_expr(expr
);
219 name
= get_variable_from_expr(expr
, &sym
);
222 ret
= get_possible_states(owner
, name
, sym
);
228 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
230 return get_sm_state_slist(cur_slist
, owner
, name
, sym
);
233 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
237 struct sm_state
*ret
= NULL
;
239 expr
= strip_expr(expr
);
240 name
= get_variable_from_expr(expr
, &sym
);
243 ret
= get_sm_state(owner
, name
, sym
);
249 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
251 delete_state_slist(&cur_slist
, owner
, name
, sym
);
252 if (cond_true_stack
) {
253 delete_state_stack(&pre_cond_stack
, owner
, name
, sym
);
254 delete_state_stack(&cond_true_stack
, owner
, name
, sym
);
255 delete_state_stack(&cond_false_stack
, owner
, name
, sym
);
259 void delete_state_expr(int owner
, struct expression
*expr
)
264 expr
= strip_expr(expr
);
265 name
= get_variable_from_expr(expr
, &sym
);
268 delete_state(owner
, name
, sym
);
273 struct state_list
*get_all_states(int owner
)
275 struct state_list
*slist
= NULL
;
276 struct sm_state
*tmp
;
278 FOR_EACH_PTR(cur_slist
, tmp
) {
279 if (tmp
->owner
== owner
) {
280 add_ptr_list(&slist
, tmp
);
282 } END_FOR_EACH_PTR(tmp
);
287 int is_reachable(void)
294 struct state_list
*__get_cur_slist(void)
299 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
300 struct smatch_state
*true_state
,
301 struct smatch_state
*false_state
)
304 struct smatch_state
*tmp
;
306 tmp
= get_state(owner
, name
, sym
);
307 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
308 get_lineno(), name
, show_state(tmp
),
309 show_state(true_state
), show_state(false_state
));
315 if (__fake_conditions
) {
317 set_state_slist(&__fake_cond_true
, owner
, name
, sym
, true_state
);
319 set_state_slist(&__fake_cond_false
, owner
, name
, sym
, false_state
);
323 if (!cond_false_stack
|| !cond_true_stack
) {
324 printf("Error: missing true/false stacks\n");
329 set_state_slist(&cur_slist
, owner
, name
, sym
, true_state
);
330 set_state_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
333 set_state_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
336 void set_true_false_states_expr(int owner
, struct expression
*expr
,
337 struct smatch_state
*true_state
,
338 struct smatch_state
*false_state
)
343 expr
= strip_expr(expr
);
344 name
= get_variable_from_expr(expr
, &sym
);
347 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
352 void __set_true_false_sm(struct sm_state
*true_state
, struct sm_state
*false_state
)
357 if (!cond_false_stack
|| !cond_true_stack
) {
358 printf("Error: missing true/false stacks\n");
363 overwrite_sm_state(&cur_slist
, true_state
);
364 overwrite_sm_state_stack(&cond_true_stack
, true_state
);
367 overwrite_sm_state_stack(&cond_false_stack
, false_state
);
370 void nullify_path(void)
372 free_slist(&cur_slist
);
375 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
382 * At the start of every function we mark the path
383 * as unnull. That there is always at least one state
384 * in the cur_slist until nullify_path is called. This
385 * is used in merge_slist() for the first null check.
387 void __unnullify_path(void)
389 set_state(-1, "unnull_path", NULL
, &true_state
);
392 int __path_is_null(void)
399 void clear_all_states(void)
401 struct named_slist
*named_slist
;
404 free_stack_and_slists(&true_stack
);
405 free_stack_and_slists(&false_stack
);
406 free_stack_and_slists(&pre_cond_stack
);
407 free_stack_and_slists(&cond_true_stack
);
408 free_stack_and_slists(&cond_false_stack
);
409 free_stack_and_slists(&break_stack
);
410 free_stack_and_slists(&switch_stack
);
411 free_stack_and_slists(&continue_stack
);
412 free_stack_and_slists(&implied_pools
);
414 FOR_EACH_PTR(goto_stack
, named_slist
) {
415 free_slist(&named_slist
->slist
);
416 } END_FOR_EACH_PTR(named_slist
);
417 __free_ptr_list((struct ptr_list
**)&goto_stack
);
418 free_every_single_sm_state();
421 void __push_cond_stacks(void)
423 push_slist(&cond_true_stack
, NULL
);
424 push_slist(&cond_false_stack
, NULL
);
428 * This combines the pre cond states with either the true or false states.
430 * a = kmalloc() ; if (a !! foo(a)
431 * In the pre state a is possibly null. In the true state it is non null.
432 * In the false state it is null. Combine the pre and the false to get
433 * that when we call 'foo', 'a' is null.
435 static void __use_cond_stack(struct state_list_stack
**stack
)
437 struct state_list
*slist
;
439 free_slist(&cur_slist
);
441 cur_slist
= pop_slist(&pre_cond_stack
);
442 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
444 slist
= pop_slist(stack
);
445 overwrite_slist(slist
, &cur_slist
);
446 push_slist(stack
, slist
);
449 void __save_false_states_for_later(void)
451 struct state_list
*pre_conditions
;
452 struct state_list
*false_states
;
453 struct state_list
*tmp
;
455 pre_conditions
= pop_slist(&pre_cond_stack
);
456 false_states
= pop_slist(&cond_false_stack
);
457 tmp
= clone_slist(pre_conditions
);
459 overwrite_slist(false_states
, &tmp
);
461 push_slist(&pre_cond_stack
, tmp
);
462 push_slist(&pre_cond_stack
, pre_conditions
);
463 push_slist(&cond_false_stack
, false_states
);
466 void __use_previously_stored_false_states(void)
468 free_slist(&cur_slist
);
469 cur_slist
= pop_slist(&pre_cond_stack
);
472 void __use_cond_true_states(void)
474 __use_cond_stack(&cond_true_stack
);
477 void __use_cond_false_states(void)
479 __use_cond_stack(&cond_false_stack
);
482 void __negate_cond_stacks(void)
484 struct state_list
*old_false
, *old_true
;
486 __use_cond_stack(&cond_false_stack
);
487 old_false
= pop_slist(&cond_false_stack
);
488 old_true
= pop_slist(&cond_true_stack
);
489 push_slist(&cond_false_stack
, old_true
);
490 push_slist(&cond_true_stack
, old_false
);
493 void __and_cond_states(void)
495 and_slist_stack(&cond_true_stack
);
496 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_false_stack
);
499 void __or_cond_states(void)
501 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_true_stack
);
502 and_slist_stack(&cond_false_stack
);
505 void __save_pre_cond_states(void)
507 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
510 void __pop_pre_cond_states(void)
512 struct state_list
*tmp
;
514 tmp
= pop_slist(&pre_cond_stack
);
518 void __use_cond_states(void)
520 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
522 pre
= pop_slist(&pre_cond_stack
);
523 pre_clone
= clone_slist(pre
);
525 true_states
= pop_slist(&cond_true_stack
);
526 overwrite_slist(true_states
, &pre
);
527 /* we use the true states right away */
528 free_slist(&cur_slist
);
531 false_states
= pop_slist(&cond_false_stack
);
532 overwrite_slist(false_states
, &pre_clone
);
533 push_slist(&false_stack
, pre_clone
);
536 void __push_true_states(void)
538 push_slist(&true_stack
, clone_slist(cur_slist
));
541 void __use_false_states(void)
543 free_slist(&cur_slist
);
544 cur_slist
= pop_slist(&false_stack
);
547 void __pop_false_states(void)
549 struct state_list
*slist
;
551 slist
= pop_slist(&false_stack
);
555 void __merge_false_states(void)
557 struct state_list
*slist
;
559 slist
= pop_slist(&false_stack
);
560 merge_slist(&cur_slist
, slist
);
564 void __merge_true_states(void)
566 struct state_list
*slist
;
568 slist
= pop_slist(&true_stack
);
569 merge_slist(&cur_slist
, slist
);
573 void __push_continues(void)
575 push_slist(&continue_stack
, NULL
);
578 void __pop_continues(void)
580 struct state_list
*slist
;
582 slist
= pop_slist(&continue_stack
);
586 void __process_continues(void)
588 struct state_list
*slist
;
590 slist
= pop_slist(&continue_stack
);
592 slist
= clone_slist(cur_slist
);
594 merge_slist(&slist
, cur_slist
);
596 push_slist(&continue_stack
, slist
);
599 static int top_slist_empty(struct state_list_stack
**stack
)
601 struct state_list
*tmp
;
604 tmp
= pop_slist(stack
);
607 push_slist(stack
, tmp
);
611 /* a silly loop does this: while(i--) { return; } */
612 void __warn_on_silly_pre_loops(void)
614 if (!__path_is_null())
616 if (!top_slist_empty(&continue_stack
))
618 if (!top_slist_empty(&break_stack
))
620 /* if the path was nullified before the loop, then we already
621 printed an error earlier */
622 if (top_slist_empty(&false_stack
))
624 sm_msg("info: loop could be replaced with if statement.");
627 void __merge_continues(void)
629 struct state_list
*slist
;
631 slist
= pop_slist(&continue_stack
);
632 merge_slist(&cur_slist
, slist
);
636 void __push_breaks(void)
638 push_slist(&break_stack
, NULL
);
641 void __process_breaks(void)
643 struct state_list
*slist
;
645 slist
= pop_slist(&break_stack
);
647 slist
= clone_slist(cur_slist
);
649 merge_slist(&slist
, cur_slist
);
651 push_slist(&break_stack
, slist
);
654 void __merge_breaks(void)
656 struct state_list
*slist
;
658 slist
= pop_slist(&break_stack
);
659 merge_slist(&cur_slist
, slist
);
663 void __use_breaks(void)
665 free_slist(&cur_slist
);
666 cur_slist
= pop_slist(&break_stack
);
669 void __save_switch_states(struct expression
*switch_expr
)
671 push_range_list(&remaining_cases
, __get_implied_values(switch_expr
));
672 push_slist(&switch_stack
, clone_slist(cur_slist
));
675 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
677 struct state_list
*slist
;
678 struct state_list
*implied_slist
;
680 slist
= pop_slist(&switch_stack
);
681 implied_slist
= __implied_case_slist(switch_expr
, case_expr
, &remaining_cases
, &slist
);
682 merge_slist(&cur_slist
, implied_slist
);
683 free_slist(&implied_slist
);
684 push_slist(&switch_stack
, slist
);
687 void __pop_switches(void)
689 struct state_list
*slist
;
691 pop_range_list(&remaining_cases
);
692 slist
= pop_slist(&switch_stack
);
696 void __push_default(void)
698 push_slist(&default_stack
, NULL
);
701 void __set_default(void)
703 set_state_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
706 int __pop_default(void)
708 struct state_list
*slist
;
710 slist
= pop_slist(&default_stack
);
718 static struct named_slist
*alloc_named_slist(const char *name
, struct state_list
*slist
)
720 struct named_slist
*named_slist
= __alloc_named_slist(0);
722 named_slist
->name
= (char *)name
;
723 named_slist
->slist
= slist
;
727 void __save_gotos(const char *name
)
729 struct state_list
**slist
;
730 struct state_list
*clone
;
732 slist
= get_slist_from_named_stack(goto_stack
, name
);
734 clone
= clone_slist(cur_slist
);
735 merge_slist(slist
, clone
);
739 struct named_slist
*named_slist
;
741 clone
= clone_slist(cur_slist
);
742 named_slist
= alloc_named_slist(name
, clone
);
743 add_ptr_list(&goto_stack
, named_slist
);
747 void __merge_gotos(const char *name
)
749 struct state_list
**slist
;
751 slist
= get_slist_from_named_stack(goto_stack
, name
);
753 merge_slist(&cur_slist
, *slist
);