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.
30 #include "smatch_slist.h"
31 #include "smatch_extra.h"
33 struct smatch_state undefined
= { .name
= "undefined" };
34 struct smatch_state merged
= { .name
= "merged" };
35 struct smatch_state true_state
= { .name
= "true" };
36 struct smatch_state false_state
= { .name
= "false" };
38 static struct state_list
*cur_slist
; /* current states */
40 static struct state_list_stack
*true_stack
; /* states after a t/f branch */
41 static struct state_list_stack
*false_stack
;
42 static struct state_list_stack
*pre_cond_stack
; /* states before a t/f branch */
44 static struct state_list_stack
*cond_true_stack
; /* states affected by a branch */
45 static struct state_list_stack
*cond_false_stack
;
48 struct state_list
*__fake_cur_slist
= NULL
;
49 int __fake_conditions
= 0;
50 struct state_list
*__fake_cond_true
= NULL
;
51 struct state_list
*__fake_cond_false
= NULL
;
53 static struct state_list_stack
*break_stack
;
54 static struct state_list_stack
*switch_stack
;
55 static struct range_list_stack
*remaining_cases
;
56 static struct state_list_stack
*default_stack
;
57 static struct state_list_stack
*continue_stack
;
59 static struct named_stack
*goto_stack
;
61 struct state_list_stack
*implied_pools
;
65 void __print_cur_slist()
67 __print_slist(cur_slist
);
72 static int reset_warnings
= 1;
79 if (reset_warnings
|| option_debug
)
80 sm_msg("info: ignoring unreachable code.");
85 void set_state(int owner
, const char *name
, struct symbol
*sym
,
86 struct smatch_state
*state
)
92 struct smatch_state
*s
;
94 s
= get_state(owner
, name
, sym
);
96 printf("%d new state. name='%s' [%s] %s\n",
97 get_lineno(), name
, check_name(owner
), show_state(state
));
99 printf("%d state change name='%s' [%s] %s => %s\n",
100 get_lineno(), name
, check_name(owner
), show_state(s
),
104 if (owner
!= -1 && unreachable())
108 set_state_slist(&__fake_cur_slist
, owner
, name
, sym
, state
);
112 set_state_slist(&cur_slist
, owner
, name
, sym
, state
);
114 if (cond_true_stack
) {
115 set_state_stack(&cond_true_stack
, owner
, name
, sym
, state
);
116 set_state_stack(&cond_false_stack
, owner
, name
, sym
, state
);
120 void set_state_expr(int owner
, struct expression
*expr
,
121 struct smatch_state
*state
)
126 expr
= strip_expr(expr
);
127 name
= get_variable_from_expr(expr
, &sym
);
130 reset_on_container_modified(owner
, expr
);
131 set_state(owner
, name
, sym
, state
);
137 void __set_state(struct sm_state
*sm
)
140 struct smatch_state
*s
;
142 s
= get_state(sm
->owner
, sm
->name
, sm
->sym
);
144 printf("%d new state. name='%s' [%s] %s\n",
145 get_lineno(), sm
->name
, check_name(sm
->owner
),
146 show_state(sm
->state
));
148 printf("%d state change name='%s' [%s] %s => %s\n",
149 get_lineno(), sm
->name
, check_name(sm
->owner
), show_state(s
),
150 show_state(sm
->state
));
156 overwrite_sm_state(&cur_slist
, sm
);
158 if (cond_true_stack
) {
159 overwrite_sm_state_stack(&cond_true_stack
, sm
);
160 overwrite_sm_state_stack(&cond_false_stack
, sm
);
164 struct smatch_state
*get_state(int owner
, const char *name
, struct symbol
*sym
)
166 return get_state_slist(cur_slist
, owner
, name
, sym
);
169 struct smatch_state
*get_state_expr(int owner
, struct expression
*expr
)
173 struct smatch_state
*ret
= NULL
;
175 expr
= strip_expr(expr
);
176 name
= get_variable_from_expr(expr
, &sym
);
179 ret
= get_state(owner
, name
, sym
);
185 struct state_list
*get_possible_states(int owner
, const char *name
,
188 struct sm_state
*sms
;
190 sms
= get_sm_state_slist(cur_slist
, owner
, name
, sym
);
192 return sms
->possible
;
196 struct state_list
*get_possible_states_expr(int owner
, struct expression
*expr
)
200 struct state_list
*ret
= NULL
;
202 expr
= strip_expr(expr
);
203 name
= get_variable_from_expr(expr
, &sym
);
206 ret
= get_possible_states(owner
, name
, sym
);
212 struct sm_state
*get_sm_state(int owner
, const char *name
, struct symbol
*sym
)
214 return get_sm_state_slist(cur_slist
, owner
, name
, sym
);
217 struct sm_state
*get_sm_state_expr(int owner
, struct expression
*expr
)
221 struct sm_state
*ret
= NULL
;
223 expr
= strip_expr(expr
);
224 name
= get_variable_from_expr(expr
, &sym
);
227 ret
= get_sm_state(owner
, name
, sym
);
233 void delete_state(int owner
, const char *name
, struct symbol
*sym
)
235 delete_state_slist(&cur_slist
, owner
, name
, sym
);
238 void delete_state_expr(int owner
, struct expression
*expr
)
243 expr
= strip_expr(expr
);
244 name
= get_variable_from_expr(expr
, &sym
);
247 delete_state(owner
, name
, sym
);
252 struct state_list
*get_all_states(int owner
)
254 struct state_list
*slist
= NULL
;
255 struct sm_state
*tmp
;
257 FOR_EACH_PTR(cur_slist
, tmp
) {
258 if (tmp
->owner
== owner
) {
259 add_ptr_list(&slist
, tmp
);
261 } END_FOR_EACH_PTR(tmp
);
273 struct state_list
*__get_cur_slist()
278 void set_true_false_states(int owner
, const char *name
, struct symbol
*sym
,
279 struct smatch_state
*true_state
,
280 struct smatch_state
*false_state
)
283 struct smatch_state
*tmp
;
285 tmp
= get_state(owner
, name
, sym
);
286 sm_debug("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
287 get_lineno(), name
, show_state(tmp
),
288 show_state(true_state
), show_state(false_state
));
294 if (__fake_conditions
) {
296 set_state_slist(&__fake_cond_true
, owner
, name
, sym
, true_state
);
298 set_state_slist(&__fake_cond_false
, owner
, name
, sym
, false_state
);
302 if (!cond_false_stack
|| !cond_true_stack
) {
303 printf("Error: missing true/false stacks\n");
308 set_state_slist(&cur_slist
, owner
, name
, sym
, true_state
);
309 set_state_stack(&cond_true_stack
, owner
, name
, sym
, true_state
);
312 set_state_stack(&cond_false_stack
, owner
, name
, sym
, false_state
);
315 void set_true_false_states_expr(int owner
, struct expression
*expr
,
316 struct smatch_state
*true_state
,
317 struct smatch_state
*false_state
)
322 expr
= strip_expr(expr
);
323 name
= get_variable_from_expr(expr
, &sym
);
326 reset_on_container_modified(owner
, expr
);
327 set_true_false_states(owner
, name
, sym
, true_state
, false_state
);
332 void __set_true_false_sm(struct sm_state
*true_state
,
333 struct sm_state
*false_state
)
338 if (!cond_false_stack
|| !cond_true_stack
) {
339 printf("Error: missing true/false stacks\n");
344 overwrite_sm_state(&cur_slist
, true_state
);
345 overwrite_sm_state_stack(&cond_true_stack
, true_state
);
348 overwrite_sm_state_stack(&cond_false_stack
, false_state
);
353 free_slist(&cur_slist
);
356 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
362 * At the start of every function we mark the path
363 * as unnull. That there is always at least one state
364 * in the cur_slist until nullify_path is called. This
365 * is used in merge_slist() for the first null check.
368 void __unnullify_path()
370 set_state(-1, "unnull_path", NULL
, &true_state
);
380 void clear_all_states()
382 struct named_slist
*named_slist
;
385 free_stack_and_slists(&true_stack
);
386 free_stack_and_slists(&false_stack
);
387 free_stack_and_slists(&pre_cond_stack
);
388 free_stack_and_slists(&cond_true_stack
);
389 free_stack_and_slists(&cond_false_stack
);
390 free_stack_and_slists(&break_stack
);
391 free_stack_and_slists(&switch_stack
);
392 free_stack_and_slists(&continue_stack
);
393 free_stack_and_slists(&implied_pools
);
395 FOR_EACH_PTR(goto_stack
, named_slist
) {
396 free_slist(&named_slist
->slist
);
397 } END_FOR_EACH_PTR(named_slist
);
398 __free_ptr_list((struct ptr_list
**)&goto_stack
);
399 free_every_single_sm_state();
403 void __push_cond_stacks()
405 push_slist(&cond_true_stack
, NULL
);
406 push_slist(&cond_false_stack
, NULL
);
410 * This combines the pre cond states with either the true or false states.
412 * a = kmalloc() ; if (a !! foo(a)
413 * In the pre state a is possibly null. In the true state it is non null.
414 * In the false state it is null. Combine the pre and the false to get
415 * that when we call 'foo', 'a' is null.
418 static void __use_cond_stack(struct state_list_stack
**stack
)
420 struct state_list
*slist
;
422 free_slist(&cur_slist
);
424 cur_slist
= pop_slist(&pre_cond_stack
);
425 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
427 slist
= pop_slist(stack
);
428 overwrite_slist(slist
, &cur_slist
);
429 push_slist(stack
, slist
);
432 void __save_false_states_for_later()
434 struct state_list
*pre_conditions
;
435 struct state_list
*false_states
;
436 struct state_list
*tmp
;
438 pre_conditions
= pop_slist(&pre_cond_stack
);
439 false_states
= pop_slist(&cond_false_stack
);
440 tmp
= clone_slist(pre_conditions
);
442 overwrite_slist(false_states
, &tmp
);
444 push_slist(&pre_cond_stack
, tmp
);
445 push_slist(&pre_cond_stack
, pre_conditions
);
446 push_slist(&cond_false_stack
, false_states
);
449 void __use_previously_stored_false_states()
451 free_slist(&cur_slist
);
452 cur_slist
= pop_slist(&pre_cond_stack
);
455 void __use_cond_true_states()
457 __use_cond_stack(&cond_true_stack
);
460 void __use_cond_false_states()
462 __use_cond_stack(&cond_false_stack
);
465 void __negate_cond_stacks()
467 struct state_list
*old_false
, *old_true
;
469 __use_cond_stack(&cond_false_stack
);
470 old_false
= pop_slist(&cond_false_stack
);
471 old_true
= pop_slist(&cond_true_stack
);
472 push_slist(&cond_false_stack
, old_true
);
473 push_slist(&cond_true_stack
, old_false
);
476 void __and_cond_states()
478 and_slist_stack(&cond_true_stack
);
479 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_false_stack
);
482 void __or_cond_states()
484 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_true_stack
);
485 and_slist_stack(&cond_false_stack
);
488 void __save_pre_cond_states()
490 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
493 void __pop_pre_cond_states()
495 struct state_list
*tmp
;
497 tmp
= pop_slist(&pre_cond_stack
);
501 void __use_cond_states()
503 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
505 pre
= pop_slist(&pre_cond_stack
);
506 pre_clone
= clone_slist(pre
);
508 true_states
= pop_slist(&cond_true_stack
);
509 overwrite_slist(true_states
, &pre
);
510 /* we use the true states right away */
511 free_slist(&cur_slist
);
515 false_states
= pop_slist(&cond_false_stack
);
516 overwrite_slist(false_states
, &pre_clone
);
517 push_slist(&false_stack
, pre_clone
);
520 void __push_true_states()
522 push_slist(&true_stack
, clone_slist(cur_slist
));
525 void __use_false_states()
527 free_slist(&cur_slist
);
528 cur_slist
= pop_slist(&false_stack
);
531 void __pop_false_states()
533 struct state_list
*slist
;
535 slist
= pop_slist(&false_stack
);
539 void __merge_false_states()
541 struct state_list
*slist
;
543 slist
= pop_slist(&false_stack
);
544 merge_slist(&cur_slist
, slist
);
548 void __merge_true_states()
550 struct state_list
*slist
;
552 slist
= pop_slist(&true_stack
);
553 merge_slist(&cur_slist
, slist
);
557 void __push_continues()
559 push_slist(&continue_stack
, NULL
);
562 void __pop_continues()
564 struct state_list
*slist
;
566 slist
= pop_slist(&continue_stack
);
570 void __process_continues()
572 struct state_list
*slist
;
574 slist
= pop_slist(&continue_stack
);
576 slist
= clone_slist(cur_slist
);
578 merge_slist(&slist
, cur_slist
);
580 push_slist(&continue_stack
, slist
);
583 static int top_slist_empty(struct state_list_stack
**stack
)
585 struct state_list
*tmp
;
588 tmp
= pop_slist(stack
);
591 push_slist(stack
, tmp
);
595 /* a silly loop does this: while(i--) { return; } */
596 void __warn_on_silly_pre_loops()
598 if (!__path_is_null())
600 if (!top_slist_empty(&continue_stack
))
602 if (!top_slist_empty(&break_stack
))
604 /* if the path was nullified before the loop, then we already
605 printed an error earlier */
606 if (top_slist_empty(&false_stack
))
608 sm_msg("info: loop could be replaced with if statement.");
611 void __merge_continues()
613 struct state_list
*slist
;
615 slist
= pop_slist(&continue_stack
);
616 merge_slist(&cur_slist
, slist
);
622 push_slist(&break_stack
, NULL
);
625 void __process_breaks()
627 struct state_list
*slist
;
629 slist
= pop_slist(&break_stack
);
631 slist
= clone_slist(cur_slist
);
633 merge_slist(&slist
, cur_slist
);
635 push_slist(&break_stack
, slist
);
638 void __merge_breaks()
640 struct state_list
*slist
;
642 slist
= pop_slist(&break_stack
);
643 merge_slist(&cur_slist
, slist
);
649 free_slist(&cur_slist
);
650 cur_slist
= pop_slist(&break_stack
);
653 void __save_switch_states(struct expression
*switch_expr
)
655 push_range_list(&remaining_cases
, __get_implied_values(switch_expr
));
656 push_slist(&switch_stack
, clone_slist(cur_slist
));
659 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
661 struct state_list
*slist
;
662 struct state_list
*implied_slist
;
664 slist
= pop_slist(&switch_stack
);
665 implied_slist
= __implied_case_slist(switch_expr
, case_expr
, &remaining_cases
, &slist
);
666 merge_slist(&cur_slist
, implied_slist
);
667 free_slist(&implied_slist
);
668 push_slist(&switch_stack
, slist
);
671 void __pop_switches()
673 struct state_list
*slist
;
675 pop_range_list(&remaining_cases
);
676 slist
= pop_slist(&switch_stack
);
680 void __push_default()
682 push_slist(&default_stack
, NULL
);
687 set_state_stack(&default_stack
, 0, "has_default", NULL
, &true_state
);
692 struct state_list
*slist
;
694 slist
= pop_slist(&default_stack
);
702 static struct named_slist
*alloc_named_slist(const char *name
,
703 struct state_list
*slist
)
705 struct named_slist
*named_slist
= __alloc_named_slist(0);
707 named_slist
->name
= (char *)name
;
708 named_slist
->slist
= slist
;
712 void __save_gotos(const char *name
)
714 struct state_list
**slist
;
715 struct state_list
*clone
;
717 slist
= get_slist_from_named_stack(goto_stack
, name
);
719 clone
= clone_slist(cur_slist
);
720 merge_slist(slist
, clone
);
724 struct named_slist
*named_slist
;
726 clone
= clone_slist(cur_slist
);
727 named_slist
= alloc_named_slist(name
, clone
);
728 add_ptr_list(&goto_stack
, named_slist
);
732 void __merge_gotos(const char *name
)
734 struct state_list
**slist
;
736 slist
= get_slist_from_named_stack(goto_stack
, name
);
738 merge_slist(&cur_slist
, *slist
);