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 true_state
= { .name
= "true" };
34 struct smatch_state false_state
= { .name
= "false" };
36 static struct state_list
*cur_slist
; /* current states */
38 static struct state_list_stack
*true_stack
; /* states after a t/f branch */
39 static struct state_list_stack
*false_stack
;
40 static struct state_list_stack
*pre_cond_stack
; /* states before a t/f branch */
42 static struct state_list_stack
*cond_true_stack
; /* states affected by a branch */
43 static struct state_list_stack
*cond_false_stack
;
45 static struct state_list_stack
*break_stack
;
46 static struct state_list_stack
*switch_stack
;
47 static struct state_list_stack
*default_stack
;
48 static struct state_list_stack
*continue_stack
;
49 static struct state_list_stack
*false_only_stack
;
51 struct slist_stack
*goto_stack
;
55 void __print_slist(struct state_list
*slist
)
57 struct sm_state
*state
;
59 printf("dumping slist at %d\n", get_lineno());
60 FOR_EACH_PTR(slist
, state
) {
61 printf("'%s'=%s\n", state
->name
, show_state(state
->state
));
62 } END_FOR_EACH_PTR(state
);
66 void __print_cur_slist()
68 __print_slist(cur_slist
);
71 void set_state(const char *name
, int owner
, struct symbol
*sym
,
72 struct smatch_state
*state
)
78 struct smatch_state
*s
;
80 s
= get_state(name
, owner
, sym
);
82 printf("%d new state. name='%s' owner=%d: %s\n",
83 get_lineno(), name
, owner
, show_state(state
));
85 printf("%d state change name='%s' owner=%d: %s => %s\n",
86 get_lineno(), name
, owner
, show_state(s
),
89 set_state_slist(&cur_slist
, name
, owner
, sym
, state
);
91 if (cond_true_stack
) {
92 set_state_stack(&cond_true_stack
, name
, owner
, sym
, state
);
93 set_state_stack(&cond_false_stack
, name
, owner
, sym
, state
);
97 struct smatch_state
*get_state(const char *name
, int owner
, struct symbol
*sym
)
99 return get_state_slist(cur_slist
, name
, owner
, sym
);
102 void delete_state(const char *name
, int owner
, struct symbol
*sym
)
104 delete_state_slist(&cur_slist
, name
, owner
, sym
);
107 struct state_list
*get_current_states(int owner
)
109 struct state_list
*slist
;
110 struct sm_state
*tmp
;
112 FOR_EACH_PTR(cur_slist
, tmp
) {
113 if (tmp
->owner
== owner
) {
114 add_ptr_list(&slist
, tmp
);
116 } END_FOR_EACH_PTR(tmp
);
121 void set_true_false_states(const char *name
, int owner
, struct symbol
*sym
,
122 struct smatch_state
*true_state
,
123 struct smatch_state
*false_state
)
125 /* fixme. save history */
128 struct smatch_state
*tmp
;
130 tmp
= get_state(name
, owner
, sym
);
131 SM_DEBUG("%d set_true_false %s. Was %s. Now T:%s F:%s\n",
132 get_lineno(), name
, show_state(tmp
),
133 show_state(true_state
), show_state(false_state
));
136 if (!cond_false_stack
|| !cond_true_stack
) {
137 printf("Error: missing true/false stacks\n");
142 set_state_slist(&cur_slist
, name
, owner
, sym
, true_state
);
143 set_state_stack(&cond_true_stack
, name
, owner
, sym
, true_state
);
146 set_state_stack(&cond_false_stack
, name
, owner
, sym
, false_state
);
151 del_slist(&cur_slist
);
155 * At the start of every function we mark the path
156 * as unnull. That there is always at least one state
157 * in the cur_slist until nullify_path is called. This
158 * is used in merge_slist() for the first null check.
161 void __unnullify_path()
163 set_state("unnull_path", 0, NULL
, &true_state
);
166 void clear_all_states()
168 struct named_slist
*named_slist
;
171 del_slist_stack(&true_stack
);
172 del_slist_stack(&false_stack
);
173 del_slist_stack(&false_only_stack
);
174 del_slist_stack(&pre_cond_stack
);
175 del_slist_stack(&cond_true_stack
);
176 del_slist_stack(&cond_false_stack
);
177 del_slist_stack(&break_stack
);
178 del_slist_stack(&switch_stack
);
179 del_slist_stack(&continue_stack
);
181 FOR_EACH_PTR(goto_stack
, named_slist
) {
182 del_slist(&named_slist
->slist
);
183 } END_FOR_EACH_PTR(named_slist
);
184 __free_ptr_list((struct ptr_list
**)&goto_stack
);
188 void __push_cond_stacks()
190 push_slist(&cond_true_stack
, NULL
);
191 push_slist(&cond_false_stack
, NULL
);
195 * This combines the pre cond states with either the true or false states.
197 * a = kmalloc() ; if (a !! foo(a)
198 * In the pre state a is possibly null. In the true state it is non null.
199 * In the false state it is null. Combine the pre and the false to get
200 * that when we call 'foo', 'a' is null.
203 static void __use_cond_stack(struct state_list_stack
**stack
)
205 struct state_list
*slist
;
207 del_slist(&cur_slist
);
209 cur_slist
= pop_slist(&pre_cond_stack
);
210 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
212 slist
= pop_slist(stack
);
213 overwrite_slist(slist
, &cur_slist
);
214 push_slist(stack
, slist
);
218 void __use_cond_true_states()
220 __use_cond_stack(&cond_true_stack
);
223 void __use_cond_false_states()
225 __use_cond_stack(&cond_false_stack
);
228 void __negate_cond_stacks()
230 struct state_list
*old_false
, *old_true
;
232 old_false
= pop_slist(&cond_false_stack
);
233 old_true
= pop_slist(&cond_true_stack
);
235 overwrite_slist(old_false
, &cur_slist
);
237 push_slist(&cond_false_stack
, old_true
);
238 push_slist(&cond_true_stack
, old_false
);
242 void __and_cond_states()
244 struct state_list
*tmp_slist
;
246 tmp_slist
= pop_slist(&cond_true_stack
);
247 and_slist_stack(&cond_true_stack
, tmp_slist
);
248 or_slist_stack(&cond_false_stack
);
251 void __or_cond_states()
253 struct state_list
*tmp_slist
;
255 or_slist_stack(&cond_true_stack
);
256 tmp_slist
= pop_slist(&cond_false_stack
);
257 and_slist_stack(&cond_false_stack
, tmp_slist
);
261 void __save_pre_cond_states()
263 push_slist(&pre_cond_stack
, clone_slist(cur_slist
));
266 void __pop_pre_cond_states()
268 struct state_list
*tmp
;
270 tmp
= pop_slist(&pre_cond_stack
);
274 void __use_false_only_stack()
276 struct state_list
*slist
;
278 slist
= pop_slist(&false_only_stack
);
279 overwrite_slist(slist
, &cur_slist
);
283 void __pop_false_only_stack()
285 struct state_list
*slist
;
287 slist
= pop_slist(&false_only_stack
);
291 void __use_cond_states()
293 struct state_list
*pre
, *pre_clone
, *true_states
, *false_states
;
295 pre
= pop_slist(&pre_cond_stack
);
296 pre_clone
= clone_slist(pre
);
298 true_states
= pop_slist(&cond_true_stack
);
299 overwrite_slist(true_states
, &pre
);
300 /* we use the true states right away */
301 del_slist(&cur_slist
);
304 false_states
= pop_slist(&cond_false_stack
);
305 push_slist(&false_only_stack
, clone_slist(false_states
));
306 overwrite_slist(false_states
, &pre_clone
);
307 push_slist(&false_stack
, pre_clone
);
310 void __push_true_states()
312 push_slist(&true_stack
, clone_slist(cur_slist
));
315 void __use_false_states()
317 del_slist(&cur_slist
);
318 cur_slist
= pop_slist(&false_stack
);
321 void __pop_false_states()
323 struct state_list
*slist
;
325 slist
= pop_slist(&false_stack
);
329 void __merge_false_states()
331 struct state_list
*slist
;
333 slist
= pop_slist(&false_stack
);
334 merge_slist(&cur_slist
, slist
);
338 void __merge_true_states()
340 struct state_list
*slist
;
342 slist
= pop_slist(&true_stack
);
343 merge_slist(&cur_slist
, slist
);
347 void __push_continues()
349 push_slist(&continue_stack
, NULL
);
352 void __pop_continues()
354 struct state_list
*slist
;
356 slist
= pop_slist(&continue_stack
);
360 void __process_continues()
362 struct state_list
*slist
;
364 slist
= pop_slist(&continue_stack
);
366 overwrite_slist(cur_slist
, &slist
);
368 merge_slist(&slist
, cur_slist
);
370 push_slist(&continue_stack
, slist
);
373 void __merge_continues()
375 struct state_list
*slist
;
377 slist
= pop_slist(&continue_stack
);
378 merge_slist(&cur_slist
, slist
);
384 push_slist(&break_stack
, NULL
);
387 void __process_breaks()
389 struct state_list
*slist
;
391 slist
= pop_slist(&break_stack
);
393 overwrite_slist(cur_slist
, &slist
);
395 merge_slist(&slist
, cur_slist
);
397 push_slist(&break_stack
, slist
);
400 void __merge_breaks()
402 struct state_list
*slist
;
404 slist
= pop_slist(&break_stack
);
405 merge_slist(&cur_slist
, slist
);
411 del_slist(&cur_slist
);
412 cur_slist
= pop_slist(&break_stack
);
415 void __save_switch_states()
417 push_slist(&switch_stack
, clone_slist(cur_slist
));
420 void __merge_switches()
422 struct state_list
*slist
;
424 slist
= pop_slist(&switch_stack
);
425 merge_slist(&cur_slist
, slist
);
426 push_slist(&switch_stack
, slist
);
429 void __pop_switches()
431 struct state_list
*slist
;
433 slist
= pop_slist(&switch_stack
);
437 void __push_default()
439 push_slist(&default_stack
, NULL
);
444 set_state_stack(&default_stack
, "has_default", 0, NULL
, &true_state
);
449 struct state_list
*slist
;
451 slist
= pop_slist(&default_stack
);
459 static struct named_slist
*alloc_named_slist(const char *name
,
460 struct state_list
*slist
)
462 struct named_slist
*named_slist
= __alloc_named_slist(0);
464 named_slist
->name
= (char *)name
;
465 named_slist
->slist
= slist
;
469 void __save_gotos(const char *name
)
471 struct state_list
*slist
;
473 slist
= get_slist_from_slist_stack(goto_stack
, name
);
475 merge_slist(&slist
, cur_slist
);
478 struct state_list
*slist
;
479 struct named_slist
*named_slist
;
481 slist
= clone_slist(cur_slist
);
482 named_slist
= alloc_named_slist(name
, slist
);
483 add_ptr_list(&goto_stack
, named_slist
);
487 void __merge_gotos(const char *name
)
489 struct state_list
*slist
;
491 slist
= get_slist_from_slist_stack(goto_stack
, name
);
493 merge_slist(&cur_slist
, slist
);