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"
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 state_list_stack
*is_switch_stack
;
55 static struct state_list_stack
*default_stack
;
56 static struct state_list_stack
*continue_stack
;
57 static struct state_list_stack
*false_only_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
);
70 static int unreachable()
72 static int reset_warnings
= 1;
79 if (reset_warnings
|| debug_states
)
80 smatch_msg("info: ignoring unreachable code.");
85 void set_state(const char *name
, int owner
, struct symbol
*sym
,
86 struct smatch_state
*state
)
92 struct smatch_state
*s
;
94 s
= get_state(name
, owner
, sym
);
96 printf("%d new state. name='%s' owner=%d: %s\n",
97 get_lineno(), name
, owner
, show_state(state
));
99 printf("%d state change name='%s' owner=%d: %s => %s\n",
100 get_lineno(), name
, owner
, show_state(s
),
104 if (owner
!= -1 && unreachable())
108 set_state_slist(&__fake_cur_slist
, name
, owner
, sym
, state
);
112 set_state_slist(&cur_slist
, name
, owner
, sym
, state
);
114 if (cond_true_stack
) {
115 set_state_stack(&cond_true_stack
, name
, owner
, sym
, state
);
116 set_state_stack(&cond_false_stack
, name
, owner
, sym
, state
);
120 void __set_state(struct sm_state
*sm
)
123 struct smatch_state
*s
;
125 s
= get_state(sm
->name
, sm
->owner
, sm
->sym
);
127 printf("%d new state. name='%s' owner=%d: %s\n",
128 get_lineno(), sm
->name
, sm
->owner
, show_state(sm
->state
));
130 printf("%d state change name='%s' owner=%d: %s => %s\n",
131 get_lineno(), sm
->name
, sm
->owner
, show_state(s
),
132 show_state(sm
->state
));
138 overwrite_sm_state(&cur_slist
, sm
);
140 if (cond_true_stack
) {
141 overwrite_sm_state_stack(&cond_true_stack
, sm
);
142 overwrite_sm_state_stack(&cond_false_stack
, sm
);
146 struct smatch_state
*get_state(const char *name
, int owner
, struct symbol
*sym
)
148 return get_state_slist(cur_slist
, name
, owner
, sym
);
151 struct state_list
*get_possible_states(const char *name
, int owner
,
154 struct sm_state
*sms
;
156 sms
= get_sm_state_slist(cur_slist
, name
, owner
, sym
);
158 return sms
->possible
;
162 struct sm_state
*get_sm_state(const char *name
, int owner
, struct symbol
*sym
)
164 return get_sm_state_slist(cur_slist
, name
, owner
, sym
);
167 void delete_state(const char *name
, int owner
, struct symbol
*sym
)
169 delete_state_slist(&cur_slist
, name
, owner
, sym
);
172 struct state_list
*get_all_states(int owner
)
174 struct state_list
*slist
= NULL
;
175 struct sm_state
*tmp
;
177 FOR_EACH_PTR(cur_slist
, tmp
) {
178 if (tmp
->owner
== owner
) {
179 add_ptr_list(&slist
, tmp
);
181 } END_FOR_EACH_PTR(tmp
);
193 struct state_list
*__get_cur_slist()
198 void set_true_false_states(const char *name
, int owner
, struct symbol
*sym
,
199 struct smatch_state
*true_state
,
200 struct smatch_state
*false_state
)
203 struct smatch_state
*tmp
;
205 tmp
= get_state(name
, owner
, sym
);
206 SM_DEBUG("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
207 get_lineno(), name
, show_state(tmp
),
208 show_state(true_state
), show_state(false_state
));
214 if (__fake_conditions
) {
216 set_state_slist(&__fake_cond_true
, name
, owner
, sym
, true_state
);
218 set_state_slist(&__fake_cond_false
, name
, owner
, sym
, false_state
);
222 if (!cond_false_stack
|| !cond_true_stack
) {
223 printf("Error: missing true/false stacks\n");
228 set_state_slist(&cur_slist
, name
, owner
, sym
, true_state
);
229 set_state_stack(&cond_true_stack
, name
, owner
, sym
, true_state
);
232 set_state_stack(&cond_false_stack
, name
, owner
, sym
, false_state
);
235 void __set_true_false_sm(struct sm_state
*true_state
,
236 struct sm_state
*false_state
)
241 if (!cond_false_stack
|| !cond_true_stack
) {
242 printf("Error: missing true/false stacks\n");
247 overwrite_sm_state(&cur_slist
, true_state
);
248 overwrite_sm_state_stack(&cond_true_stack
, true_state
);
251 overwrite_sm_state_stack(&cond_false_stack
, false_state
);
256 free_slist(&cur_slist
);
259 void __match_nullify_path_hook(const char *fn
, struct expression
*expr
,
265 * At the start of every function we mark the path
266 * as unnull. That there is always at least one state
267 * in the cur_slist until nullify_path is called. This
268 * is used in merge_slist() for the first null check.
271 void __unnullify_path()
273 set_state("unnull_path", -1, NULL
, &true_state
);
283 void clear_all_states()
285 struct named_slist
*named_slist
;
288 free_stack_and_slists(&true_stack
);
289 free_stack_and_slists(&false_stack
);
290 free_stack_and_slists(&false_only_stack
);
291 free_stack_and_slists(&pre_cond_stack
);
292 free_stack_and_slists(&cond_true_stack
);
293 free_stack_and_slists(&cond_false_stack
);
294 free_stack_and_slists(&break_stack
);
295 free_stack_and_slists(&switch_stack
);
296 free_stack_and_slists(&continue_stack
);
297 free_stack_and_slists(&implied_pools
);
299 FOR_EACH_PTR(goto_stack
, named_slist
) {
300 free_slist(&named_slist
->slist
);
301 } END_FOR_EACH_PTR(named_slist
);
302 __free_ptr_list((struct ptr_list
**)&goto_stack
);
303 free_every_single_sm_state();
307 void __push_cond_stacks()
309 push_slist(&cond_true_stack
, NULL
);
310 push_slist(&cond_false_stack
, NULL
);
314 * This combines the pre cond states with either the true or false states.
316 * a = kmalloc() ; if (a !! foo(a)
317 * In the pre state a is possibly null. In the true state it is non null.
318 * In the false state it is null. Combine the pre and the false to get
319 * that when we call 'foo', 'a' is null.
322 static void __use_cond_stack(struct state_list_stack
**stack
)
324 struct state_list
*slist
;
326 free_slist(&cur_slist
);
328 cur_slist
= pop_slist(&pre_cond_stack
);
329 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
331 slist
= pop_slist(stack
);
332 overwrite_slist(slist
, &cur_slist
);
333 push_slist(stack
, slist
);
336 void __save_false_states_for_later()
338 struct state_list
*pre_conditions
;
339 struct state_list
*false_states
;
340 struct state_list
*tmp
;
342 pre_conditions
= pop_slist(&pre_cond_stack
);
343 false_states
= pop_slist(&cond_false_stack
);
344 tmp
= clone_slist(pre_conditions
);
346 overwrite_slist(false_states
, &tmp
);
348 push_slist(&pre_cond_stack
, tmp
);
349 push_slist(&pre_cond_stack
, pre_conditions
);
350 push_slist(&cond_false_stack
, false_states
);
353 void __use_previously_stored_false_states()
355 free_slist(&cur_slist
);
356 cur_slist
= pop_slist(&pre_cond_stack
);
359 void __use_cond_true_states()
361 __use_cond_stack(&cond_true_stack
);
364 void __use_cond_false_states()
366 __use_cond_stack(&cond_false_stack
);
369 void __negate_cond_stacks()
371 struct state_list
*old_false
, *old_true
;
373 old_false
= pop_slist(&cond_false_stack
);
374 old_true
= pop_slist(&cond_true_stack
);
376 overwrite_slist(old_false
, &cur_slist
);
378 push_slist(&cond_false_stack
, old_true
);
379 push_slist(&cond_true_stack
, old_false
);
382 void __and_cond_states()
384 and_slist_stack(&cond_true_stack
);
385 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_false_stack
);
388 void __or_cond_states()
390 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_true_stack
);
391 and_slist_stack(&cond_false_stack
);
394 void __save_pre_cond_states()
396 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
399 void __pop_pre_cond_states()
401 struct state_list
*tmp
;
403 tmp
= pop_slist(&pre_cond_stack
);
407 void __use_false_only_stack()
409 struct state_list
*slist
;
411 slist
= pop_slist(&false_only_stack
);
412 overwrite_slist(slist
, &cur_slist
);
416 void __pop_false_only_stack()
418 struct state_list
*slist
;
420 slist
= pop_slist(&false_only_stack
);
424 void __use_cond_states()
426 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
428 pre
= pop_slist(&pre_cond_stack
);
429 pre_clone
= clone_slist(pre
);
431 true_states
= pop_slist(&cond_true_stack
);
432 overwrite_slist(true_states
, &pre
);
433 /* we use the true states right away */
434 free_slist(&cur_slist
);
438 false_states
= pop_slist(&cond_false_stack
);
439 push_slist(&false_only_stack
, clone_slist(false_states
));
440 overwrite_slist(false_states
, &pre_clone
);
441 push_slist(&false_stack
, pre_clone
);
444 void __push_true_states()
446 push_slist(&true_stack
, clone_slist(cur_slist
));
449 void __use_false_states()
451 free_slist(&cur_slist
);
452 cur_slist
= pop_slist(&false_stack
);
455 void __pop_false_states()
457 struct state_list
*slist
;
459 slist
= pop_slist(&false_stack
);
463 void __merge_false_states()
465 struct state_list
*slist
;
467 slist
= pop_slist(&false_stack
);
468 merge_slist(&cur_slist
, slist
);
472 void __merge_true_states()
474 struct state_list
*slist
;
476 slist
= pop_slist(&true_stack
);
477 merge_slist(&cur_slist
, slist
);
481 void __push_continues()
483 push_slist(&continue_stack
, NULL
);
486 void __pop_continues()
488 struct state_list
*slist
;
490 slist
= pop_slist(&continue_stack
);
494 void __process_continues()
496 struct state_list
*slist
;
498 slist
= pop_slist(&continue_stack
);
500 slist
= clone_slist(cur_slist
);
502 merge_slist(&slist
, cur_slist
);
504 push_slist(&continue_stack
, slist
);
507 static int top_slist_empty(struct state_list_stack
**stack
)
509 struct state_list
*tmp
;
512 tmp
= pop_slist(stack
);
515 push_slist(stack
, tmp
);
519 /* a silly loop does this: while(i--) { return; } */
520 void __warn_on_silly_pre_loops()
522 if (!__path_is_null())
524 if (!top_slist_empty(&continue_stack
))
526 if (!top_slist_empty(&break_stack
))
528 /* if the path was nullified before the loop, then we already
529 printed an error earlier */
530 if (top_slist_empty(&false_stack
))
532 smatch_msg("info: loop could be replaced with if statement.");
535 void __merge_continues()
537 struct state_list
*slist
;
539 slist
= pop_slist(&continue_stack
);
540 merge_slist(&cur_slist
, slist
);
544 void __push_switch_info(struct smatch_state
*state
)
546 push_slist(&is_switch_stack
, NULL
);
547 if (state
== &true_state
)
548 set_state_stack(&is_switch_stack
, "is_switch", 0, NULL
, &true_state
);
551 static int is_switch()
553 if (last_ptr_list((struct ptr_list
*)is_switch_stack
))
558 void __pop_switch_info()
560 struct state_list
*slist
;
562 slist
= pop_slist(&is_switch_stack
);
568 push_slist(&break_stack
, NULL
);
571 void __process_breaks()
573 struct state_list
*slist
;
575 slist
= pop_slist(&break_stack
);
577 slist
= clone_slist(cur_slist
);
580 merge_slist_clone(&slist
, cur_slist
);
582 merge_slist(&slist
, cur_slist
);
584 push_slist(&break_stack
, slist
);
587 void __merge_breaks()
589 struct state_list
*slist
;
591 slist
= pop_slist(&break_stack
);
592 merge_slist(&cur_slist
, slist
);
598 free_slist(&cur_slist
);
599 cur_slist
= pop_slist(&break_stack
);
602 void __save_switch_states()
604 push_slist(&switch_stack
, clone_slist(cur_slist
));
607 void __merge_switches(struct expression
*switch_expr
, struct expression
*case_expr
)
609 struct state_list
*slist
;
610 struct state_list
*implied_slist
;
612 slist
= pop_slist(&switch_stack
);
613 implied_slist
= __implied_case_slist(switch_expr
, case_expr
, &slist
);
614 merge_slist_clone(&cur_slist
, implied_slist
);
615 free_slist(&implied_slist
);
616 push_slist(&switch_stack
, slist
);
619 void __pop_switches()
621 struct state_list
*slist
;
623 slist
= pop_slist(&switch_stack
);
627 void __push_default()
629 push_slist(&default_stack
, NULL
);
634 set_state_stack(&default_stack
, "has_default", 0, NULL
, &true_state
);
639 struct state_list
*slist
;
641 slist
= pop_slist(&default_stack
);
649 static struct named_slist
*alloc_named_slist(const char *name
,
650 struct state_list
*slist
)
652 struct named_slist
*named_slist
= __alloc_named_slist(0);
654 named_slist
->name
= (char *)name
;
655 named_slist
->slist
= slist
;
659 void __save_gotos(const char *name
)
661 struct state_list
**slist
;
662 struct state_list
*clone
;
664 slist
= get_slist_from_named_stack(goto_stack
, name
);
666 clone
= clone_slist_and_states(cur_slist
);
667 merge_slist(slist
, clone
);
671 struct named_slist
*named_slist
;
673 clone
= clone_slist(cur_slist
);
674 named_slist
= alloc_named_slist(name
, clone
);
675 add_ptr_list(&goto_stack
, named_slist
);
679 void __merge_gotos(const char *name
)
681 struct state_list
**slist
;
683 slist
= get_slist_from_named_stack(goto_stack
, name
);
685 merge_slist(&cur_slist
, *slist
);