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
;
46 static struct state_list_stack
*break_stack
;
47 static struct state_list_stack
*switch_stack
;
48 static struct state_list_stack
*default_stack
;
49 static struct state_list_stack
*continue_stack
;
50 static struct state_list_stack
*false_only_stack
;
52 static struct named_stack
*goto_stack
;
54 struct state_list_stack
*implied_pools
;
58 void __print_cur_slist()
60 __print_slist(cur_slist
);
63 static int unreachable()
65 static int reset_warnings
= 1;
72 if (reset_warnings
|| debug_states
)
73 smatch_msg("info: ignoring unreachable code.");
78 void set_state(const char *name
, int owner
, struct symbol
*sym
,
79 struct smatch_state
*state
)
85 struct smatch_state
*s
;
87 s
= get_state(name
, owner
, sym
);
89 printf("%d new state. name='%s' owner=%d: %s\n",
90 get_lineno(), name
, owner
, show_state(state
));
92 printf("%d state change name='%s' owner=%d: %s => %s\n",
93 get_lineno(), name
, owner
, show_state(s
),
97 if (owner
!= -1 && unreachable())
100 set_state_slist(&cur_slist
, name
, owner
, sym
, state
);
102 if (cond_true_stack
) {
103 set_state_stack(&cond_true_stack
, name
, owner
, sym
, state
);
104 set_state_stack(&cond_false_stack
, name
, owner
, sym
, state
);
108 struct smatch_state
*get_state(const char *name
, int owner
, struct symbol
*sym
)
110 return get_state_slist(cur_slist
, name
, owner
, sym
);
113 struct state_list
*get_possible_states(const char *name
, int owner
,
116 struct sm_state
*sms
;
118 sms
= get_sm_state_slist(cur_slist
, name
, owner
, sym
);
120 return sms
->possible
;
124 struct sm_state
*get_sm_state(const char *name
, int owner
, struct symbol
*sym
)
126 return get_sm_state_slist(cur_slist
, name
, owner
, sym
);
129 void delete_state(const char *name
, int owner
, struct symbol
*sym
)
131 delete_state_slist(&cur_slist
, name
, owner
, sym
);
134 struct state_list
*get_all_states(int owner
)
136 struct state_list
*slist
= NULL
;
137 struct sm_state
*tmp
;
139 FOR_EACH_PTR(cur_slist
, tmp
) {
140 if (tmp
->owner
== owner
) {
141 add_ptr_list(&slist
, tmp
);
143 } END_FOR_EACH_PTR(tmp
);
155 struct state_list
*__get_cur_slist()
160 void set_true_false_states(const char *name
, int owner
, struct symbol
*sym
,
161 struct smatch_state
*true_state
,
162 struct smatch_state
*false_state
)
165 struct smatch_state
*tmp
;
167 tmp
= get_state(name
, owner
, sym
);
168 SM_DEBUG("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
169 get_lineno(), name
, show_state(tmp
),
170 show_state(true_state
), show_state(false_state
));
176 if (!cond_false_stack
|| !cond_true_stack
) {
177 printf("Error: missing true/false stacks\n");
182 set_state_slist(&cur_slist
, name
, owner
, sym
, true_state
);
183 set_state_stack(&cond_true_stack
, name
, owner
, sym
, true_state
);
186 set_state_stack(&cond_false_stack
, name
, owner
, sym
, false_state
);
189 void __set_true_false_sm(struct sm_state
*true_state
,
190 struct sm_state
*false_state
)
195 if (!cond_false_stack
|| !cond_true_stack
) {
196 printf("Error: missing true/false stacks\n");
201 overwrite_sm_state(&cur_slist
, true_state
);
202 overwrite_sm_state_stack(&cond_true_stack
, true_state
);
205 overwrite_sm_state_stack(&cond_false_stack
, false_state
);
210 free_slist(&cur_slist
);
214 * At the start of every function we mark the path
215 * as unnull. That there is always at least one state
216 * in the cur_slist until nullify_path is called. This
217 * is used in merge_slist() for the first null check.
220 void __unnullify_path()
222 set_state("unnull_path", -1, NULL
, &true_state
);
232 void clear_all_states()
234 struct named_slist
*named_slist
;
237 free_stack_and_slists(&true_stack
);
238 free_stack_and_slists(&false_stack
);
239 free_stack_and_slists(&false_only_stack
);
240 free_stack_and_slists(&pre_cond_stack
);
241 free_stack_and_slists(&cond_true_stack
);
242 free_stack_and_slists(&cond_false_stack
);
243 free_stack_and_slists(&break_stack
);
244 free_stack_and_slists(&switch_stack
);
245 free_stack_and_slists(&continue_stack
);
246 free_stack_and_slists(&implied_pools
);
248 FOR_EACH_PTR(goto_stack
, named_slist
) {
249 free_slist(&named_slist
->slist
);
250 } END_FOR_EACH_PTR(named_slist
);
251 __free_ptr_list((struct ptr_list
**)&goto_stack
);
252 free_every_single_sm_state();
256 void __push_cond_stacks()
258 push_slist(&cond_true_stack
, NULL
);
259 push_slist(&cond_false_stack
, NULL
);
263 * This combines the pre cond states with either the true or false states.
265 * a = kmalloc() ; if (a !! foo(a)
266 * In the pre state a is possibly null. In the true state it is non null.
267 * In the false state it is null. Combine the pre and the false to get
268 * that when we call 'foo', 'a' is null.
271 static void __use_cond_stack(struct state_list_stack
**stack
)
273 struct state_list
*slist
;
275 free_slist(&cur_slist
);
277 cur_slist
= pop_slist(&pre_cond_stack
);
278 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
280 slist
= pop_slist(stack
);
281 overwrite_slist(slist
, &cur_slist
);
282 push_slist(stack
, slist
);
285 void __save_false_states_for_later()
287 struct state_list
*pre_conditions
;
288 struct state_list
*false_states
;
289 struct state_list
*tmp
;
291 pre_conditions
= pop_slist(&pre_cond_stack
);
292 false_states
= pop_slist(&cond_false_stack
);
293 tmp
= clone_slist(pre_conditions
);
295 overwrite_slist(false_states
, &tmp
);
297 push_slist(&pre_cond_stack
, tmp
);
298 push_slist(&pre_cond_stack
, pre_conditions
);
299 push_slist(&cond_false_stack
, false_states
);
302 void __use_previously_stored_false_states()
304 free_slist(&cur_slist
);
305 cur_slist
= pop_slist(&pre_cond_stack
);
308 void __use_cond_true_states()
310 __use_cond_stack(&cond_true_stack
);
313 void __use_cond_false_states()
315 __use_cond_stack(&cond_false_stack
);
318 void __negate_cond_stacks()
320 struct state_list
*old_false
, *old_true
;
322 old_false
= pop_slist(&cond_false_stack
);
323 old_true
= pop_slist(&cond_true_stack
);
325 overwrite_slist(old_false
, &cur_slist
);
327 push_slist(&cond_false_stack
, old_true
);
328 push_slist(&cond_true_stack
, old_false
);
331 void __and_cond_states()
333 and_slist_stack(&cond_true_stack
);
334 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_false_stack
);
337 void __or_cond_states()
339 or_slist_stack(&pre_cond_stack
, cur_slist
, &cond_true_stack
);
340 and_slist_stack(&cond_false_stack
);
343 void __save_pre_cond_states()
345 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
348 void __pop_pre_cond_states()
350 struct state_list
*tmp
;
352 tmp
= pop_slist(&pre_cond_stack
);
356 void __use_false_only_stack()
358 struct state_list
*slist
;
360 slist
= pop_slist(&false_only_stack
);
361 overwrite_slist(slist
, &cur_slist
);
365 void __pop_false_only_stack()
367 struct state_list
*slist
;
369 slist
= pop_slist(&false_only_stack
);
373 void __use_cond_states()
375 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
377 pre
= pop_slist(&pre_cond_stack
);
378 pre_clone
= clone_slist(pre
);
380 true_states
= pop_slist(&cond_true_stack
);
381 overwrite_slist(true_states
, &pre
);
382 /* we use the true states right away */
383 free_slist(&cur_slist
);
387 false_states
= pop_slist(&cond_false_stack
);
388 push_slist(&false_only_stack
, clone_slist(false_states
));
389 overwrite_slist(false_states
, &pre_clone
);
390 push_slist(&false_stack
, pre_clone
);
393 void __push_true_states()
395 push_slist(&true_stack
, clone_slist(cur_slist
));
398 void __use_false_states()
400 free_slist(&cur_slist
);
401 cur_slist
= pop_slist(&false_stack
);
404 void __pop_false_states()
406 struct state_list
*slist
;
408 slist
= pop_slist(&false_stack
);
412 void __merge_false_states()
414 struct state_list
*slist
;
416 slist
= pop_slist(&false_stack
);
417 merge_slist(&cur_slist
, slist
);
421 void __merge_true_states()
423 struct state_list
*slist
;
425 slist
= pop_slist(&true_stack
);
426 merge_slist(&cur_slist
, slist
);
430 void __push_continues()
432 push_slist(&continue_stack
, NULL
);
435 void __pop_continues()
437 struct state_list
*slist
;
439 slist
= pop_slist(&continue_stack
);
443 void __process_continues()
445 struct state_list
*slist
;
447 slist
= pop_slist(&continue_stack
);
449 slist
= clone_slist(cur_slist
);
451 merge_slist(&slist
, cur_slist
);
453 push_slist(&continue_stack
, slist
);
456 static int top_slist_empty(struct state_list_stack
**stack
)
458 struct state_list
*tmp
;
461 tmp
= pop_slist(stack
);
464 push_slist(stack
, tmp
);
468 /* a silly loop does this: while(i--) { return; } */
469 void __warn_on_silly_pre_loops()
471 if (!__path_is_null())
473 if (!top_slist_empty(&continue_stack
))
475 if (!top_slist_empty(&break_stack
))
477 /* if the path was nullified before the loop, then we already
478 printed an error earlier */
479 if (top_slist_empty(&false_stack
))
481 smatch_msg("info: loop could be replaced with if statement.");
484 void __merge_continues()
486 struct state_list
*slist
;
488 slist
= pop_slist(&continue_stack
);
489 merge_slist(&cur_slist
, slist
);
495 push_slist(&break_stack
, NULL
);
498 void __process_breaks()
500 struct state_list
*slist
;
502 slist
= pop_slist(&break_stack
);
504 slist
= clone_slist(cur_slist
);
506 merge_slist(&slist
, cur_slist
);
508 push_slist(&break_stack
, slist
);
511 void __merge_breaks()
513 struct state_list
*slist
;
515 slist
= pop_slist(&break_stack
);
516 merge_slist(&cur_slist
, slist
);
522 free_slist(&cur_slist
);
523 cur_slist
= pop_slist(&break_stack
);
526 void __save_switch_states()
528 push_slist(&switch_stack
, clone_slist(cur_slist
));
531 void __merge_switches()
533 struct state_list
*slist
;
535 slist
= pop_slist(&switch_stack
);
536 merge_slist(&cur_slist
, slist
);
537 push_slist(&switch_stack
, slist
);
540 void __pop_switches()
542 struct state_list
*slist
;
544 slist
= pop_slist(&switch_stack
);
548 void __push_default()
550 push_slist(&default_stack
, NULL
);
555 set_state_stack(&default_stack
, "has_default", 0, NULL
, &true_state
);
560 struct state_list
*slist
;
562 slist
= pop_slist(&default_stack
);
570 static struct named_slist
*alloc_named_slist(const char *name
,
571 struct state_list
*slist
)
573 struct named_slist
*named_slist
= __alloc_named_slist(0);
575 named_slist
->name
= (char *)name
;
576 named_slist
->slist
= slist
;
580 void __save_gotos(const char *name
)
582 struct state_list
**slist
;
584 slist
= get_slist_from_named_stack(goto_stack
, name
);
586 merge_slist(slist
, cur_slist
);
589 struct state_list
*slist
;
590 struct named_slist
*named_slist
;
592 slist
= clone_slist(cur_slist
);
593 named_slist
= alloc_named_slist(name
, slist
);
594 add_ptr_list(&goto_stack
, named_slist
);
598 void __merge_gotos(const char *name
)
600 struct state_list
**slist
;
602 slist
= get_slist_from_named_stack(goto_stack
, name
);
604 merge_slist(&cur_slist
, *slist
);