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 slist_stack
*goto_stack
;
54 struct state_list_stack
*implied_pools
;
58 void __print_cur_slist()
60 __print_slist(cur_slist
);
63 void set_state(const char *name
, int owner
, struct symbol
*sym
,
64 struct smatch_state
*state
)
71 old
= __get_sm_state(name
, owner
, sym
);
75 printf("%d new state. name='%s' owner=%d: %s\n",
76 get_lineno(), name
, owner
, show_state(state
));
78 printf("%d state change name='%s' owner=%d: %s => %s\n",
79 get_lineno(), name
, owner
,
80 show_state(old
->state
), show_state(state
));
83 remove_from_pools(old
);
84 set_state_slist(&cur_slist
, name
, owner
, sym
, state
);
86 if (cond_true_stack
) {
87 set_state_stack(&cond_true_stack
, name
, owner
, sym
, state
);
88 set_state_stack(&cond_false_stack
, name
, owner
, sym
, state
);
92 struct smatch_state
*get_state(const char *name
, int owner
, struct symbol
*sym
)
94 return get_state_slist(cur_slist
, name
, owner
, sym
);
97 struct state_list
*get_possible_states(const char *name
, int owner
,
100 struct sm_state
*sms
;
102 sms
= get_sm_state_slist(cur_slist
, name
, owner
, sym
);
104 return sms
->possible
;
108 void __overwrite_cur_slist(struct state_list
*slist
)
110 overwrite_slist(slist
, &cur_slist
);
113 struct sm_state
*__get_sm_state(const char *name
, int owner
, struct symbol
*sym
)
115 return get_sm_state_slist(cur_slist
, name
, owner
, sym
);
118 void delete_state(const char *name
, int owner
, struct symbol
*sym
)
120 delete_state_slist(&cur_slist
, name
, owner
, sym
);
123 struct state_list
*get_all_states(int owner
)
125 struct state_list
*slist
= NULL
;
126 struct sm_state
*tmp
;
128 FOR_EACH_PTR(cur_slist
, tmp
) {
129 if (tmp
->owner
== owner
) {
130 add_ptr_list(&slist
, tmp
);
132 } END_FOR_EACH_PTR(tmp
);
137 void set_true_false_states(const char *name
, int owner
, struct symbol
*sym
,
138 struct smatch_state
*true_state
,
139 struct smatch_state
*false_state
)
141 struct sm_state
*old
;
142 /* fixme. save history */
144 old
= __get_sm_state(name
, owner
, sym
);
146 SM_DEBUG("%d set_true_false '%s'. Was %s. Now T:%s F:%s\n",
147 get_lineno(), name
, (old
?show_state(old
->state
):NULL
),
148 show_state(true_state
), show_state(false_state
));
151 if (!cond_false_stack
|| !cond_true_stack
) {
152 printf("Error: missing true/false stacks\n");
156 remove_from_pools(old
);
159 set_state_slist(&cur_slist
, name
, owner
, sym
, true_state
);
160 set_state_stack(&cond_true_stack
, name
, owner
, sym
, true_state
);
163 set_state_stack(&cond_false_stack
, name
, owner
, sym
, false_state
);
168 del_slist(&cur_slist
);
172 * At the start of every function we mark the path
173 * as unnull. That there is always at least one state
174 * in the cur_slist until nullify_path is called. This
175 * is used in merge_slist() for the first null check.
178 void __unnullify_path()
180 set_state("unnull_path", 0, NULL
, &true_state
);
190 void clear_all_states()
192 struct named_slist
*named_slist
;
195 del_slist_stack(&true_stack
);
196 del_slist_stack(&false_stack
);
197 del_slist_stack(&false_only_stack
);
198 del_slist_stack(&pre_cond_stack
);
199 del_slist_stack(&cond_true_stack
);
200 del_slist_stack(&cond_false_stack
);
201 del_slist_stack(&break_stack
);
202 del_slist_stack(&switch_stack
);
203 del_slist_stack(&continue_stack
);
204 del_slist_stack(&implied_pools
);
206 FOR_EACH_PTR(goto_stack
, named_slist
) {
207 del_slist(&named_slist
->slist
);
208 } END_FOR_EACH_PTR(named_slist
);
209 __free_ptr_list((struct ptr_list
**)&goto_stack
);
213 void __push_cond_stacks()
215 push_slist(&cond_true_stack
, NULL
);
216 push_slist(&cond_false_stack
, NULL
);
220 * This combines the pre cond states with either the true or false states.
222 * a = kmalloc() ; if (a !! foo(a)
223 * In the pre state a is possibly null. In the true state it is non null.
224 * In the false state it is null. Combine the pre and the false to get
225 * that when we call 'foo', 'a' is null.
228 static void __use_cond_stack(struct state_list_stack
**stack
)
230 struct state_list
*slist
;
232 del_slist(&cur_slist
);
234 cur_slist
= pop_slist(&pre_cond_stack
);
235 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
237 slist
= pop_slist(stack
);
238 overwrite_slist(slist
, &cur_slist
);
239 push_slist(stack
, slist
);
243 void __use_cond_true_states()
245 __use_cond_stack(&cond_true_stack
);
248 void __use_cond_false_states()
250 __use_cond_stack(&cond_false_stack
);
253 void __negate_cond_stacks()
255 struct state_list
*old_false
, *old_true
;
257 old_false
= pop_slist(&cond_false_stack
);
258 old_true
= pop_slist(&cond_true_stack
);
260 overwrite_slist(old_false
, &cur_slist
);
262 push_slist(&cond_false_stack
, old_true
);
263 push_slist(&cond_true_stack
, old_false
);
266 void __and_cond_states()
268 and_slist_stack(&cond_true_stack
);
269 or_slist_stack(&cond_false_stack
);
272 void __or_cond_states()
274 or_slist_stack(&cond_true_stack
);
275 and_slist_stack(&cond_false_stack
);
278 void __save_pre_cond_states()
280 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
283 void __pop_pre_cond_states()
285 struct state_list
*tmp
;
287 tmp
= pop_slist(&pre_cond_stack
);
291 void __use_false_only_stack()
293 struct state_list
*slist
;
295 slist
= pop_slist(&false_only_stack
);
296 overwrite_slist(slist
, &cur_slist
);
300 void __pop_false_only_stack()
302 struct state_list
*slist
;
304 slist
= pop_slist(&false_only_stack
);
308 void __use_cond_states()
310 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
312 pre
= pop_slist(&pre_cond_stack
);
313 pre_clone
= clone_slist(pre
);
315 true_states
= pop_slist(&cond_true_stack
);
316 overwrite_slist(true_states
, &pre
);
317 /* we use the true states right away */
318 del_slist(&cur_slist
);
322 false_states
= pop_slist(&cond_false_stack
);
323 push_slist(&false_only_stack
, clone_slist(false_states
));
324 overwrite_slist(false_states
, &pre_clone
);
325 push_slist(&false_stack
, pre_clone
);
328 void __push_true_states()
330 push_slist(&true_stack
, clone_slist(cur_slist
));
333 void __use_false_states()
335 del_slist(&cur_slist
);
336 cur_slist
= pop_slist(&false_stack
);
339 void __pop_false_states()
341 struct state_list
*slist
;
343 slist
= pop_slist(&false_stack
);
347 void __merge_false_states()
349 struct state_list
*slist
;
351 slist
= pop_slist(&false_stack
);
352 merge_slist(&cur_slist
, slist
);
356 void __merge_true_states()
358 struct state_list
*slist
;
360 slist
= pop_slist(&true_stack
);
361 merge_slist(&cur_slist
, slist
);
365 void __push_continues()
367 push_slist(&continue_stack
, NULL
);
370 void __pop_continues()
372 struct state_list
*slist
;
374 slist
= pop_slist(&continue_stack
);
378 void __process_continues()
380 struct state_list
*slist
;
382 slist
= pop_slist(&continue_stack
);
384 overwrite_slist(cur_slist
, &slist
);
386 merge_slist(&slist
, cur_slist
);
388 push_slist(&continue_stack
, slist
);
391 void __merge_continues()
393 struct state_list
*slist
;
395 slist
= pop_slist(&continue_stack
);
396 merge_slist(&cur_slist
, slist
);
402 push_slist(&break_stack
, NULL
);
405 void __process_breaks()
407 struct state_list
*slist
;
409 slist
= pop_slist(&break_stack
);
411 overwrite_slist(cur_slist
, &slist
);
413 merge_slist(&slist
, cur_slist
);
415 push_slist(&break_stack
, slist
);
418 void __merge_breaks()
420 struct state_list
*slist
;
422 slist
= pop_slist(&break_stack
);
423 merge_slist(&cur_slist
, slist
);
429 del_slist(&cur_slist
);
430 cur_slist
= pop_slist(&break_stack
);
433 void __save_switch_states()
435 push_slist(&switch_stack
, clone_slist(cur_slist
));
438 void __merge_switches()
440 struct state_list
*slist
;
442 slist
= pop_slist(&switch_stack
);
443 merge_slist(&cur_slist
, slist
);
444 push_slist(&switch_stack
, slist
);
447 void __pop_switches()
449 struct state_list
*slist
;
451 slist
= pop_slist(&switch_stack
);
455 void __push_default()
457 push_slist(&default_stack
, NULL
);
462 set_state_stack(&default_stack
, "has_default", 0, NULL
, &true_state
);
467 struct state_list
*slist
;
469 slist
= pop_slist(&default_stack
);
477 static struct named_slist
*alloc_named_slist(const char *name
,
478 struct state_list
*slist
)
480 struct named_slist
*named_slist
= __alloc_named_slist(0);
482 named_slist
->name
= (char *)name
;
483 named_slist
->slist
= slist
;
487 void __save_gotos(const char *name
)
489 struct state_list
**slist
;
491 slist
= get_slist_from_slist_stack(goto_stack
, name
);
493 merge_slist(slist
, cur_slist
);
496 struct state_list
*slist
;
497 struct named_slist
*named_slist
;
499 slist
= clone_slist(cur_slist
);
500 named_slist
= alloc_named_slist(name
, slist
);
501 add_ptr_list(&goto_stack
, named_slist
);
505 void __merge_gotos(const char *name
)
507 struct state_list
**slist
;
509 slist
= get_slist_from_slist_stack(goto_stack
, name
);
511 merge_slist(&cur_slist
, *slist
);