1 /*
2  * Copyright (C) 2006 Dan Carpenter.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
16  */
17 
18 /*
19  * You have a lists of states.  kernel = locked, foo = NULL, ...
20  * When you hit an if {} else {} statement then you swap the list
21  * of states for a different list of states.  The lists are stored
22  * on stacks.
23  *
24  * At the beginning of this file there are list of the stacks that
25  * we use.  Each function in this file does something to one of
26  * of the stacks.
27  *
28  * So the smatch_flow.c understands code but it doesn't understand states.
29  * smatch_flow calls functions in this file.  This file calls functions
30  * in smatch_slist.c which just has boring generic plumbing for handling
31  * state lists.  But really it's this file where all the magic happens.
32  */
33 
34 #include <stdlib.h>
35 #include <stdio.h>
36 #include "smatch.h"
37 #include "smatch_slist.h"
38 #include "smatch_extra.h"
39 
40 struct smatch_state undefined = { .name = "undefined" };
41 struct smatch_state ghost = { .name = "ghost" };
42 struct smatch_state merged = { .name = "merged" };
43 struct smatch_state true_state = { .name = "true" };
44 struct smatch_state false_state = { .name = "false" };
45 
46 static struct stree *cur_stree; /* current states */
47 static struct stree *fast_overlay;
48 
49 static struct stree_stack *true_stack; /* states after a t/f branch */
50 static struct stree_stack *false_stack;
51 static struct stree_stack *pre_cond_stack; /* states before a t/f branch */
52 
53 static struct stree_stack *cond_true_stack; /* states affected by a branch */
54 static struct stree_stack *cond_false_stack;
55 
56 static struct stree_stack *fake_cur_stree_stack;
57 static int read_only;
58 
59 static struct stree_stack *break_stack;
60 static struct stree_stack *fake_break_stack;
61 static struct stree_stack *switch_stack;
62 static struct range_list_stack *remaining_cases;
63 static struct stree_stack *default_stack;
64 static struct stree_stack *continue_stack;
65 
66 static struct named_stree_stack *goto_stack;
67 
68 static struct ptr_list *backup;
69 
70 int option_debug;
71 
__print_cur_stree(void)72 void __print_cur_stree(void)
73 {
74 	__print_stree(cur_stree);
75 }
76 
__print_states(const char * owner)77 bool __print_states(const char *owner)
78 {
79 	struct sm_state *sm;
80 	bool found = false;
81 
82 	if (!owner)
83 		return false;
84 
85 	FOR_EACH_SM(__get_cur_stree(), sm) {
86 		if (!strstr(check_name(sm->owner), owner))
87 			continue;
88 		sm_msg("%s", show_sm(sm));
89 		found = true;
90 	} END_FOR_EACH_SM(sm);
91 
92 	return found;
93 }
94 
unreachable(void)95 int unreachable(void)
96 {
97 	if (!cur_stree)
98 		return 1;
99 	return 0;
100 }
101 
__set_cur_stree_readonly(void)102 void __set_cur_stree_readonly(void)
103 {
104 	read_only++;
105 }
106 
__set_cur_stree_writable(void)107 void __set_cur_stree_writable(void)
108 {
109 	read_only--;
110 }
111 
112 DECLARE_PTR_LIST(check_tracker_list, check_tracker_hook *);
113 static struct check_tracker_list **tracker_hooks;
114 
add_check_tracker(const char * check_name,check_tracker_hook * fn)115 void add_check_tracker(const char *check_name, check_tracker_hook *fn)
116 {
117 	check_tracker_hook **p;
118 	int owner;
119 
120 	owner = id_from_name(check_name);
121 	if (!owner) {
122 		printf("check not found.  '%s'\n", check_name);
123 		return;
124 	}
125 
126 	p = malloc(sizeof(check_tracker_hook *));
127 	*p = fn;
128 	add_ptr_list(&tracker_hooks[owner], p);
129 }
130 
call_tracker_hooks(int owner,const char * name,struct symbol * sym,struct smatch_state * state)131 static void call_tracker_hooks(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
132 {
133 	struct check_tracker_list *hooks;
134 	check_tracker_hook **fn;
135 
136 	if ((unsigned short)owner == USHRT_MAX)
137 		return;
138 
139 	hooks = tracker_hooks[owner];
140 	FOR_EACH_PTR(hooks, fn) {
141 		(*fn)(owner, name, sym, state);
142 	} END_FOR_EACH_PTR(fn);
143 }
144 
allocate_tracker_array(int num_checks)145 void allocate_tracker_array(int num_checks)
146 {
147 	tracker_hooks = malloc(num_checks * sizeof(void *));
148 	memset(tracker_hooks, 0, num_checks * sizeof(void *));
149 }
150 
set_state(int owner,const char * name,struct symbol * sym,struct smatch_state * state)151 struct sm_state *set_state(int owner, const char *name, struct symbol *sym, struct smatch_state *state)
152 {
153 	struct sm_state *ret;
154 
155 	if (!name || !state)
156 		return NULL;
157 
158 	if (read_only)
159 		sm_perror("cur_stree is read only.");
160 
161 	if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
162 		struct smatch_state *s;
163 
164 		s = __get_state(owner, name, sym);
165 		if (!s)
166 			sm_msg("%s new [%s] '%s' %s", __func__,
167 			       check_name(owner), name, show_state(state));
168 		else
169 			sm_msg("%s change [%s] '%s' %s => %s",
170 				__func__, check_name(owner), name, show_state(s),
171 				show_state(state));
172 	}
173 
174 	call_tracker_hooks(owner, name, sym, state);
175 
176 	if (owner != -1 && unreachable())
177 		return NULL;
178 
179 	if (fake_cur_stree_stack)
180 		set_state_stree_stack(&fake_cur_stree_stack, owner, name, sym, state);
181 
182 	ret = set_state_stree(&cur_stree, owner, name, sym, state);
183 
184 	return ret;
185 }
186 
set_state_expr(int owner,struct expression * expr,struct smatch_state * state)187 struct sm_state *set_state_expr(int owner, struct expression *expr, struct smatch_state *state)
188 {
189 	char *name;
190 	struct symbol *sym;
191 	struct sm_state *ret = NULL;
192 
193 	expr = strip_expr(expr);
194 	name = expr_to_var_sym(expr, &sym);
195 	if (!name || !sym)
196 		goto free;
197 	ret = set_state(owner, name, sym, state);
198 free:
199 	free_string(name);
200 	return ret;
201 }
202 
__swap_cur_stree(struct stree * stree)203 struct stree *__swap_cur_stree(struct stree *stree)
204 {
205 	struct stree *orig = cur_stree;
206 
207 	cur_stree = stree;
208 	return orig;
209 }
210 
__push_fake_cur_stree(void)211 void __push_fake_cur_stree(void)
212 {
213 	push_stree(&fake_cur_stree_stack, NULL);
214 	__save_pre_cond_states();
215 }
216 
__pop_fake_cur_stree(void)217 struct stree *__pop_fake_cur_stree(void)
218 {
219 	if (!fake_cur_stree_stack)
220 		sm_perror("popping too many fake cur strees.");
221 	__use_pre_cond_states();
222 	return pop_stree(&fake_cur_stree_stack);
223 }
224 
__free_fake_cur_stree(void)225 void __free_fake_cur_stree(void)
226 {
227 	struct stree *stree;
228 
229 	stree = __pop_fake_cur_stree();
230 	free_stree(&stree);
231 }
232 
__set_fake_cur_stree_fast(struct stree * stree)233 void __set_fake_cur_stree_fast(struct stree *stree)
234 {
235 	if (fast_overlay) {
236 		sm_perror("cannot nest fast overlay");
237 		return;
238 	}
239 	fast_overlay = stree;
240 	set_fast_math_only();
241 }
242 
__pop_fake_cur_stree_fast(void)243 void __pop_fake_cur_stree_fast(void)
244 {
245 	fast_overlay = NULL;
246 	clear_fast_math_only();
247 }
248 
__merge_stree_into_cur(struct stree * stree)249 void __merge_stree_into_cur(struct stree *stree)
250 {
251 	struct sm_state *sm;
252 	struct sm_state *orig;
253 	struct sm_state *merged;
254 
255 	FOR_EACH_SM(stree, sm) {
256 		orig = get_sm_state(sm->owner, sm->name, sm->sym);
257 		if (orig)
258 			merged = merge_sm_states(orig, sm);
259 		else
260 			merged = sm;
261 		__set_sm(merged);
262 	} END_FOR_EACH_SM(sm);
263 }
264 
__set_sm(struct sm_state * sm)265 void __set_sm(struct sm_state *sm)
266 {
267 	if (read_only)
268 		sm_perror("cur_stree is read only.");
269 
270 	if (option_debug ||
271 	    strcmp(check_name(sm->owner), option_debug_check) == 0) {
272 		struct smatch_state *s;
273 
274 		s = __get_state(sm->owner, sm->name, sm->sym);
275 		if (!s)
276 			sm_msg("%s new %s", __func__, show_sm(sm));
277 		else
278 			sm_msg("%s change %s (was %s)",	__func__, show_sm(sm),
279 			       show_state(s));
280 	}
281 
282 	if (unreachable())
283 		return;
284 
285 	if (fake_cur_stree_stack)
286 		overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
287 
288 	overwrite_sm_state_stree(&cur_stree, sm);
289 }
290 
__set_sm_cur_stree(struct sm_state * sm)291 void __set_sm_cur_stree(struct sm_state *sm)
292 {
293 	if (read_only)
294 		sm_perror("cur_stree is read only.");
295 
296 	if (option_debug ||
297 	    strcmp(check_name(sm->owner), option_debug_check) == 0) {
298 		struct smatch_state *s;
299 
300 		s = __get_state(sm->owner, sm->name, sm->sym);
301 		if (!s)
302 			sm_msg("%s new %s", __func__, show_sm(sm));
303 		else
304 			sm_msg("%s change %s (was %s)",
305 				__func__, show_sm(sm), show_state(s));
306 	}
307 
308 	if (unreachable())
309 		return;
310 
311 	overwrite_sm_state_stree(&cur_stree, sm);
312 }
313 
__set_sm_fake_stree(struct sm_state * sm)314 void __set_sm_fake_stree(struct sm_state *sm)
315 {
316 	if (read_only)
317 		sm_perror("cur_stree is read only.");
318 
319 	if (option_debug ||
320 	    strcmp(check_name(sm->owner), option_debug_check) == 0) {
321 		struct smatch_state *s;
322 
323 		s = __get_state(sm->owner, sm->name, sm->sym);
324 		if (!s)
325 			sm_msg("%s new %s", __func__, show_sm(sm));
326 		else
327 			sm_msg("%s change %s (was %s)",
328 				__func__, show_sm(sm), show_state(s));
329 	}
330 
331 	if (unreachable())
332 		return;
333 
334 	overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
335 }
336 
337 
338 typedef void (get_state_hook)(int owner, const char *name, struct symbol *sym);
339 DECLARE_PTR_LIST(fn_list, get_state_hook *);
340 static struct fn_list *get_state_hooks;
341 
add_get_state_hook(get_state_hook * fn)342 void add_get_state_hook(get_state_hook *fn)
343 {
344 	get_state_hook **p = malloc(sizeof(get_state_hook *));
345 	*p = fn;
346 	add_ptr_list(&get_state_hooks, p);
347 }
348 
call_get_state_hooks(int owner,const char * name,struct symbol * sym)349 static void call_get_state_hooks(int owner, const char *name, struct symbol *sym)
350 {
351 	static int recursion;
352 	get_state_hook **fn;
353 
354 	if (recursion)
355 		return;
356 	recursion = 1;
357 
358 	FOR_EACH_PTR(get_state_hooks, fn) {
359 		(*fn)(owner, name, sym);
360 	} END_FOR_EACH_PTR(fn);
361 
362 	recursion = 0;
363 }
364 
__get_state(int owner,const char * name,struct symbol * sym)365 struct smatch_state *__get_state(int owner, const char *name, struct symbol *sym)
366 {
367 	struct sm_state *sm;
368 
369 	sm = get_sm_state(owner, name, sym);
370 	if (!sm)
371 		return NULL;
372 	return sm->state;
373 }
374 
get_state(int owner,const char * name,struct symbol * sym)375 struct smatch_state *get_state(int owner, const char *name, struct symbol *sym)
376 {
377 	call_get_state_hooks(owner, name, sym);
378 
379 	return __get_state(owner, name, sym);
380 }
381 
get_state_expr(int owner,struct expression * expr)382 struct smatch_state *get_state_expr(int owner, struct expression *expr)
383 {
384 	char *name;
385 	struct symbol *sym;
386 	struct smatch_state *ret = NULL;
387 
388 	expr = strip_expr(expr);
389 	name = expr_to_var_sym(expr, &sym);
390 	if (!name || !sym)
391 		goto free;
392 	ret = get_state(owner, name, sym);
393 free:
394 	free_string(name);
395 	return ret;
396 }
397 
get_possible_states(int owner,const char * name,struct symbol * sym)398 struct state_list *get_possible_states(int owner, const char *name, struct symbol *sym)
399 {
400 	struct sm_state *sms;
401 
402 	sms = get_sm_state_stree(cur_stree, owner, name, sym);
403 	if (sms)
404 		return sms->possible;
405 	return NULL;
406 }
407 
get_possible_states_expr(int owner,struct expression * expr)408 struct state_list *get_possible_states_expr(int owner, struct expression *expr)
409 {
410 	char *name;
411 	struct symbol *sym;
412 	struct state_list *ret = NULL;
413 
414 	expr = strip_expr(expr);
415 	name = expr_to_var_sym(expr, &sym);
416 	if (!name || !sym)
417 		goto free;
418 	ret = get_possible_states(owner, name, sym);
419 free:
420 	free_string(name);
421 	return ret;
422 }
423 
get_sm_state(int owner,const char * name,struct symbol * sym)424 struct sm_state *get_sm_state(int owner, const char *name, struct symbol *sym)
425 {
426 	struct sm_state *ret;
427 
428 	ret = get_sm_state_stree(fast_overlay, owner, name, sym);
429 	if (ret)
430 		return ret;
431 
432 	return get_sm_state_stree(cur_stree, owner, name, sym);
433 }
434 
get_sm_state_expr(int owner,struct expression * expr)435 struct sm_state *get_sm_state_expr(int owner, struct expression *expr)
436 {
437 	char *name;
438 	struct symbol *sym;
439 	struct sm_state *ret = NULL;
440 
441 	expr = strip_expr(expr);
442 	name = expr_to_var_sym(expr, &sym);
443 	if (!name || !sym)
444 		goto free;
445 	ret = get_sm_state(owner, name, sym);
446 free:
447 	free_string(name);
448 	return ret;
449 }
450 
delete_state(int owner,const char * name,struct symbol * sym)451 void delete_state(int owner, const char *name, struct symbol *sym)
452 {
453 	delete_state_stree(&cur_stree, owner, name, sym);
454 	if (cond_true_stack) {
455 		delete_state_stree_stack(&pre_cond_stack, owner, name, sym);
456 		delete_state_stree_stack(&cond_true_stack, owner, name, sym);
457 		delete_state_stree_stack(&cond_false_stack, owner, name, sym);
458 	}
459 }
460 
delete_state_expr(int owner,struct expression * expr)461 void delete_state_expr(int owner, struct expression *expr)
462 {
463 	char *name;
464 	struct symbol *sym;
465 
466 	expr = strip_expr(expr);
467 	name = expr_to_var_sym(expr, &sym);
468 	if (!name || !sym)
469 		goto free;
470 	delete_state(owner, name, sym);
471 free:
472 	free_string(name);
473 }
474 
delete_all_states_stree_sym(struct stree ** stree,struct symbol * sym)475 static void delete_all_states_stree_sym(struct stree **stree, struct symbol *sym)
476 {
477 	struct state_list *slist = NULL;
478 	struct sm_state *sm;
479 
480 	FOR_EACH_SM(*stree, sm) {
481 		if (sm->sym == sym)
482 			add_ptr_list(&slist, sm);
483 	} END_FOR_EACH_SM(sm);
484 
485 	FOR_EACH_PTR(slist, sm) {
486 		delete_state_stree(stree, sm->owner, sm->name, sm->sym);
487 	} END_FOR_EACH_PTR(sm);
488 
489 	free_slist(&slist);
490 }
491 
delete_all_states_stree_stack_sym(struct stree_stack ** stack,struct symbol * sym)492 static void delete_all_states_stree_stack_sym(struct stree_stack **stack, struct symbol *sym)
493 {
494 	struct stree *stree;
495 
496 	if (!*stack)
497 		return;
498 
499 	stree = pop_stree(stack);
500 	delete_all_states_stree_sym(&stree, sym);
501 	push_stree(stack, stree);
502 }
503 
__delete_all_states_sym(struct symbol * sym)504 void __delete_all_states_sym(struct symbol *sym)
505 {
506 	delete_all_states_stree_sym(&cur_stree, sym);
507 
508 	delete_all_states_stree_stack_sym(&true_stack, sym);
509 	delete_all_states_stree_stack_sym(&true_stack, sym);
510 	delete_all_states_stree_stack_sym(&false_stack, sym);
511 	delete_all_states_stree_stack_sym(&pre_cond_stack, sym);
512 	delete_all_states_stree_stack_sym(&cond_true_stack, sym);
513 	delete_all_states_stree_stack_sym(&cond_false_stack, sym);
514 	delete_all_states_stree_stack_sym(&fake_cur_stree_stack, sym);
515 	delete_all_states_stree_stack_sym(&break_stack, sym);
516 	delete_all_states_stree_stack_sym(&fake_break_stack, sym);
517 	delete_all_states_stree_stack_sym(&switch_stack, sym);
518 	delete_all_states_stree_stack_sym(&continue_stack, sym);
519 
520 	/*
521 	 * deleting from the goto stack is problematic because we don't know
522 	 * if the label is in scope and also we need the value for --two-passes.
523 	 */
524 }
525 
get_all_states_from_stree(int owner,struct stree * source)526 struct stree *get_all_states_from_stree(int owner, struct stree *source)
527 {
528 	struct stree *ret = NULL;
529 	struct sm_state *tmp;
530 
531 	FOR_EACH_SM(source, tmp) {
532 		if (tmp->owner == owner)
533 			avl_insert(&ret, tmp);
534 	} END_FOR_EACH_SM(tmp);
535 
536 	return ret;
537 }
538 
get_all_states_stree(int owner)539 struct stree *get_all_states_stree(int owner)
540 {
541 	return get_all_states_from_stree(owner, cur_stree);
542 }
543 
__get_cur_stree(void)544 struct stree *__get_cur_stree(void)
545 {
546 	return cur_stree;
547 }
548 
is_reachable(void)549 int is_reachable(void)
550 {
551 	if (cur_stree)
552 		return 1;
553 	return 0;
554 }
555 
set_true_false_states(int owner,const char * name,struct symbol * sym,struct smatch_state * true_state,struct smatch_state * false_state)556 void set_true_false_states(int owner, const char *name, struct symbol *sym,
557 			   struct smatch_state *true_state,
558 			   struct smatch_state *false_state)
559 {
560 	if (read_only)
561 		sm_perror("cur_stree is read only.");
562 
563 	if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
564 		struct smatch_state *tmp;
565 
566 		tmp = __get_state(owner, name, sym);
567 		sm_msg("%s [%s] '%s'.  Was %s.  Now T:%s F:%s", __func__,
568 		       check_name(owner),  name, show_state(tmp),
569 		       show_state(true_state), show_state(false_state));
570 	}
571 
572 	if (unreachable())
573 		return;
574 
575 	if (!cond_false_stack || !cond_true_stack) {
576 		sm_perror("missing true/false stacks");
577 		return;
578 	}
579 
580 	if (true_state)
581 		set_state_stree_stack(&cond_true_stack, owner, name, sym, true_state);
582 	if (false_state)
583 		set_state_stree_stack(&cond_false_stack, owner, name, sym, false_state);
584 }
585 
set_true_false_states_expr(int owner,struct expression * expr,struct smatch_state * true_state,struct smatch_state * false_state)586 void set_true_false_states_expr(int owner, struct expression *expr,
587 			   struct smatch_state *true_state,
588 			   struct smatch_state *false_state)
589 {
590 	char *name;
591 	struct symbol *sym;
592 
593 	expr = strip_expr(expr);
594 	name = expr_to_var_sym(expr, &sym);
595 	if (!name || !sym)
596 		goto free;
597 	set_true_false_states(owner, name, sym, true_state, false_state);
598 free:
599 	free_string(name);
600 }
601 
__set_true_false_sm(struct sm_state * true_sm,struct sm_state * false_sm)602 void __set_true_false_sm(struct sm_state *true_sm, struct sm_state *false_sm)
603 {
604 	int owner;
605 	const char *name;
606 	struct symbol *sym;
607 
608 	if (!true_sm && !false_sm)
609 		return;
610 
611 	if (unreachable())
612 		return;
613 
614 	owner = true_sm ? true_sm->owner : false_sm->owner;
615 	name = true_sm ? true_sm->name : false_sm->name;
616 	sym = true_sm ? true_sm->sym : false_sm->sym;
617 	if (option_debug || strcmp(check_name(owner), option_debug_check) == 0) {
618 		struct smatch_state *tmp;
619 
620 		tmp = __get_state(owner, name, sym);
621 		sm_msg("%s [%s] '%s'.  Was %s.  Now T:%s F:%s", __func__,
622 		       check_name(owner),  name, show_state(tmp),
623 		       show_state(true_sm ? true_sm->state : NULL),
624 		       show_state(false_sm ? false_sm->state : NULL));
625 	}
626 
627 	if (!cond_false_stack || !cond_true_stack) {
628 		sm_perror("missing true/false stacks");
629 		return;
630 	}
631 
632 	if (true_sm)
633 		overwrite_sm_state_stree_stack(&cond_true_stack, true_sm);
634 	if (false_sm)
635 		overwrite_sm_state_stree_stack(&cond_false_stack, false_sm);
636 }
637 
nullify_path(void)638 void nullify_path(void)
639 {
640 	if (fake_cur_stree_stack) {
641 		__free_fake_cur_stree();
642 		__push_fake_cur_stree();
643 	}
644 	free_stree(&cur_stree);
645 }
646 
__match_nullify_path_hook(const char * fn,struct expression * expr,void * unused)647 void __match_nullify_path_hook(const char *fn, struct expression *expr,
648 			       void *unused)
649 {
650 	nullify_path();
651 }
652 
653 /*
654  * At the start of every function we mark the path
655  * as unnull.  That way there is always at least one state
656  * in the cur_stree until nullify_path is called.  This
657  * is used in merge_slist() for the first null check.
658  */
__unnullify_path(void)659 void __unnullify_path(void)
660 {
661 	if (!cur_stree)
662 		set_state(-1, "unnull_path", NULL, &true_state);
663 }
664 
__path_is_null(void)665 int __path_is_null(void)
666 {
667 	if (cur_stree)
668 		return 0;
669 	return 1;
670 }
671 
check_stree_stack_free(struct stree_stack ** stack)672 static void check_stree_stack_free(struct stree_stack **stack)
673 {
674 	if (*stack) {
675 		sm_perror("stack not empty");
676 		free_stack_and_strees(stack);
677 	}
678 }
679 
save_all_states(void)680 void save_all_states(void)
681 {
682 	__add_ptr_list(&backup, cur_stree);
683 	cur_stree = NULL;
684 
685 	__add_ptr_list(&backup, true_stack);
686 	true_stack = NULL;
687 	__add_ptr_list(&backup, false_stack);
688 	false_stack = NULL;
689 	__add_ptr_list(&backup, pre_cond_stack);
690 	pre_cond_stack = NULL;
691 
692 	__add_ptr_list(&backup, cond_true_stack);
693 	cond_true_stack = NULL;
694 	__add_ptr_list(&backup, cond_false_stack);
695 	cond_false_stack = NULL;
696 
697 	__add_ptr_list(&backup, fake_cur_stree_stack);
698 	fake_cur_stree_stack = NULL;
699 
700 	__add_ptr_list(&backup, break_stack);
701 	break_stack = NULL;
702 	__add_ptr_list(&backup, fake_break_stack);
703 	fake_break_stack = NULL;
704 
705 	__add_ptr_list(&backup, switch_stack);
706 	switch_stack = NULL;
707 	__add_ptr_list(&backup, remaining_cases);
708 	remaining_cases = NULL;
709 	__add_ptr_list(&backup, default_stack);
710 	default_stack = NULL;
711 	__add_ptr_list(&backup, continue_stack);
712 	continue_stack = NULL;
713 
714 	__add_ptr_list(&backup, goto_stack);
715 	goto_stack = NULL;
716 }
717 
pop_backup(void)718 static void *pop_backup(void)
719 {
720 	void *ret;
721 
722 	ret = last_ptr_list(backup);
723 	delete_ptr_list_last(&backup);
724 	return ret;
725 }
726 
restore_all_states(void)727 void restore_all_states(void)
728 {
729 	goto_stack = pop_backup();
730 
731 	continue_stack = pop_backup();
732 	default_stack = pop_backup();
733 	remaining_cases = pop_backup();
734 	switch_stack = pop_backup();
735 	fake_break_stack = pop_backup();
736 	break_stack = pop_backup();
737 
738 	fake_cur_stree_stack = pop_backup();
739 
740 	cond_false_stack = pop_backup();
741 	cond_true_stack = pop_backup();
742 
743 	pre_cond_stack = pop_backup();
744 	false_stack = pop_backup();
745 	true_stack = pop_backup();
746 
747 	cur_stree = pop_backup();
748 }
749 
free_goto_stack(void)750 void free_goto_stack(void)
751 {
752 	struct named_stree *named_stree;
753 
754 	FOR_EACH_PTR(goto_stack, named_stree) {
755 		free_stree(&named_stree->stree);
756 	} END_FOR_EACH_PTR(named_stree);
757 	__free_ptr_list((struct ptr_list **)&goto_stack);
758 }
759 
clear_all_states(void)760 void clear_all_states(void)
761 {
762 	nullify_path();
763 	check_stree_stack_free(&true_stack);
764 	check_stree_stack_free(&false_stack);
765 	check_stree_stack_free(&pre_cond_stack);
766 	check_stree_stack_free(&cond_true_stack);
767 	check_stree_stack_free(&cond_false_stack);
768 	check_stree_stack_free(&break_stack);
769 	check_stree_stack_free(&fake_break_stack);
770 	check_stree_stack_free(&switch_stack);
771 	check_stree_stack_free(&continue_stack);
772 	check_stree_stack_free(&fake_cur_stree_stack);
773 
774 	free_goto_stack();
775 
776 	free_every_single_sm_state();
777 	free_tmp_expressions();
778 }
779 
__push_cond_stacks(void)780 void __push_cond_stacks(void)
781 {
782 	push_stree(&cond_true_stack, NULL);
783 	push_stree(&cond_false_stack, NULL);
784 	__push_fake_cur_stree();
785 }
786 
__fold_in_set_states(void)787 void __fold_in_set_states(void)
788 {
789 	struct stree *new_states;
790 	struct sm_state *sm;
791 
792 	new_states = __pop_fake_cur_stree();
793 	FOR_EACH_SM(new_states, sm) {
794 		__set_sm(sm);
795 		__set_true_false_sm(sm, sm);
796 	} END_FOR_EACH_SM(sm);
797 	free_stree(&new_states);
798 }
799 
__free_set_states(void)800 void __free_set_states(void)
801 {
802 	struct stree *new_states;
803 
804 	new_states = __pop_fake_cur_stree();
805 	free_stree(&new_states);
806 }
807 
__copy_cond_true_states(void)808 struct stree *__copy_cond_true_states(void)
809 {
810 	struct stree *ret;
811 
812 	ret = pop_stree(&cond_true_stack);
813 	push_stree(&cond_true_stack, clone_stree(ret));
814 	return ret;
815 }
816 
__copy_cond_false_states(void)817 struct stree *__copy_cond_false_states(void)
818 {
819 	struct stree *ret;
820 
821 	ret = pop_stree(&cond_false_stack);
822 	push_stree(&cond_false_stack, clone_stree(ret));
823 	return ret;
824 }
825 
__pop_cond_true_stack(void)826 struct stree *__pop_cond_true_stack(void)
827 {
828 	return pop_stree(&cond_true_stack);
829 }
830 
__pop_cond_false_stack(void)831 struct stree *__pop_cond_false_stack(void)
832 {
833 	return pop_stree(&cond_false_stack);
834 }
835 
836 /*
837  * This combines the pre cond states with either the true or false states.
838  * For example:
839  * a = kmalloc() ; if (a !! foo(a)
840  * In the pre state a is possibly null.  In the true state it is non null.
841  * In the false state it is null.  Combine the pre and the false to get
842  * that when we call 'foo', 'a' is null.
843  */
__use_cond_stack(struct stree_stack ** stack)844 static void __use_cond_stack(struct stree_stack **stack)
845 {
846 	struct stree *stree;
847 
848 	free_stree(&cur_stree);
849 
850 	cur_stree = pop_stree(&pre_cond_stack);
851 	push_stree(&pre_cond_stack, clone_stree(cur_stree));
852 
853 	stree = pop_stree(stack);
854 	overwrite_stree(stree, &cur_stree);
855 	push_stree(stack, stree);
856 }
857 
__use_pre_cond_states(void)858 void __use_pre_cond_states(void)
859 {
860 	free_stree(&cur_stree);
861 	cur_stree = pop_stree(&pre_cond_stack);
862 }
863 
__use_cond_true_states(void)864 void __use_cond_true_states(void)
865 {
866 	__use_cond_stack(&cond_true_stack);
867 }
868 
__use_cond_false_states(void)869 void __use_cond_false_states(void)
870 {
871 	__use_cond_stack(&cond_false_stack);
872 }
873 
__negate_cond_stacks(void)874 void __negate_cond_stacks(void)
875 {
876 	struct stree *old_false, *old_true;
877 
878 	old_false = pop_stree(&cond_false_stack);
879 	old_true = pop_stree(&cond_true_stack);
880 	push_stree(&cond_false_stack, old_true);
881 	push_stree(&cond_true_stack, old_false);
882 }
883 
__and_cond_states(void)884 void __and_cond_states(void)
885 {
886 	and_stree_stack(&cond_true_stack);
887 	or_stree_stack(&pre_cond_stack, cur_stree, &cond_false_stack);
888 }
889 
__or_cond_states(void)890 void __or_cond_states(void)
891 {
892 	or_stree_stack(&pre_cond_stack, cur_stree, &cond_true_stack);
893 	and_stree_stack(&cond_false_stack);
894 }
895 
__save_pre_cond_states(void)896 void __save_pre_cond_states(void)
897 {
898 	push_stree(&pre_cond_stack, clone_stree(cur_stree));
899 }
900 
__discard_pre_cond_states(void)901 void __discard_pre_cond_states(void)
902 {
903 	struct stree *tmp;
904 
905 	tmp = pop_stree(&pre_cond_stack);
906 	free_stree(&tmp);
907 }
908 
__get_true_states(void)909 struct stree *__get_true_states(void)
910 {
911 	return clone_stree(top_stree(cond_true_stack));
912 }
913 
__get_false_states(void)914 struct stree *__get_false_states(void)
915 {
916 	return clone_stree(top_stree(cond_false_stack));
917 }
918 
__use_cond_states(void)919 void __use_cond_states(void)
920 {
921 	struct stree *pre, *pre_clone, *true_states, *false_states;
922 
923 	pre = pop_stree(&pre_cond_stack);
924 	pre_clone = clone_stree(pre);
925 
926 	true_states = pop_stree(&cond_true_stack);
927 	overwrite_stree(true_states, &pre);
928 	free_stree(&true_states);
929 	/* we use the true states right away */
930 	free_stree(&cur_stree);
931 	cur_stree = pre;
932 
933 	false_states = pop_stree(&cond_false_stack);
934 	overwrite_stree(false_states, &pre_clone);
935 	free_stree(&false_states);
936 	push_stree(&false_stack, pre_clone);
937 }
938 
__push_true_states(void)939 void __push_true_states(void)
940 {
941 	push_stree(&true_stack, clone_stree(cur_stree));
942 }
943 
__use_false_states(void)944 void __use_false_states(void)
945 {
946 	free_stree(&cur_stree);
947 	cur_stree = pop_stree(&false_stack);
948 }
949 
__discard_false_states(void)950 void __discard_false_states(void)
951 {
952 	struct stree *stree;
953 
954 	stree = pop_stree(&false_stack);
955 	free_stree(&stree);
956 }
957 
__merge_false_states(void)958 void __merge_false_states(void)
959 {
960 	struct stree *stree;
961 
962 	stree = pop_stree(&false_stack);
963 	merge_stree(&cur_stree, stree);
964 	free_stree(&stree);
965 }
966 
967 /*
968  * This function probably seemed common sensical when I wrote it but, oh wow,
969  * does it look subtle in retrospect.  Say we set a state on one side of the if
970  * else path but not on the other, then what we should record in the fake stree
971  * is the merged state.
972  *
973  * This function relies on the fact that the we always set the cur_stree as well
974  * and we already have the infrastructure to merge things correctly into the
975  * cur_stree.
976  *
977  * So instead of merging fake strees together which is probably a lot of work,
978  * we just use it as a list of set states and look up the actual current values
979  * in the cur_stree.
980  *
981  */
update_stree_with_merged(struct stree ** stree)982 static void update_stree_with_merged(struct stree **stree)
983 {
984 	struct state_list *slist = NULL;
985 	struct sm_state *sm, *new;
986 
987 	FOR_EACH_SM(*stree, sm) {
988 		new = get_sm_state(sm->owner, sm->name, sm->sym);
989 		if (!new)  /* This can happen if we go out of scope */
990 			continue;
991 		add_ptr_list(&slist, new);
992 	} END_FOR_EACH_SM(sm);
993 
994 	FOR_EACH_PTR(slist, sm) {
995 		overwrite_sm_state_stree(stree, sm);
996 	} END_FOR_EACH_PTR(sm);
997 
998 	free_slist(&slist);
999 }
1000 
update_fake_stree_with_merged(void)1001 static void update_fake_stree_with_merged(void)
1002 {
1003 	struct stree *stree;
1004 
1005 	if (!fake_cur_stree_stack)
1006 		return;
1007 	stree = pop_stree(&fake_cur_stree_stack);
1008 	update_stree_with_merged(&stree);
1009 	push_stree(&fake_cur_stree_stack, stree);
1010 }
1011 
__merge_true_states(void)1012 void __merge_true_states(void)
1013 {
1014 	struct stree *stree;
1015 
1016 	stree = pop_stree(&true_stack);
1017 	merge_stree(&cur_stree, stree);
1018 	update_fake_stree_with_merged();
1019 	free_stree(&stree);
1020 }
1021 
__push_continues(void)1022 void __push_continues(void)
1023 {
1024 	push_stree(&continue_stack, NULL);
1025 }
1026 
__discard_continues(void)1027 void __discard_continues(void)
1028 {
1029 	struct stree *stree;
1030 
1031 	stree = pop_stree(&continue_stack);
1032 	free_stree(&stree);
1033 }
1034 
__process_continues(void)1035 void __process_continues(void)
1036 {
1037 	struct stree *stree;
1038 
1039 	stree = pop_stree(&continue_stack);
1040 	if (!stree)
1041 		stree = clone_stree(cur_stree);
1042 	else
1043 		merge_stree(&stree, cur_stree);
1044 
1045 	push_stree(&continue_stack, stree);
1046 }
1047 
__merge_continues(void)1048 void __merge_continues(void)
1049 {
1050 	struct stree *stree;
1051 
1052 	stree = pop_stree(&continue_stack);
1053 	merge_stree(&cur_stree, stree);
1054 	free_stree(&stree);
1055 }
1056 
__push_breaks(void)1057 void __push_breaks(void)
1058 {
1059 	push_stree(&break_stack, NULL);
1060 	if (fake_cur_stree_stack)
1061 		push_stree(&fake_break_stack, NULL);
1062 }
1063 
__process_breaks(void)1064 void __process_breaks(void)
1065 {
1066 	struct stree *stree;
1067 
1068 	stree = pop_stree(&break_stack);
1069 	if (!stree)
1070 		stree = clone_stree(cur_stree);
1071 	else
1072 		merge_stree(&stree, cur_stree);
1073 	push_stree(&break_stack, stree);
1074 
1075 	if (!fake_cur_stree_stack)
1076 		return;
1077 
1078 	stree = pop_stree(&fake_break_stack);
1079 	if (!stree)
1080 		stree = clone_stree(top_stree(fake_cur_stree_stack));
1081 	else
1082 		merge_stree(&stree, top_stree(fake_cur_stree_stack));
1083 	push_stree(&fake_break_stack, stree);
1084 }
1085 
__has_breaks(void)1086 int __has_breaks(void)
1087 {
1088 	struct stree *stree;
1089 	int ret;
1090 
1091 	stree = pop_stree(&break_stack);
1092 	ret = !!stree;
1093 	push_stree(&break_stack, stree);
1094 	return ret;
1095 }
1096 
__merge_breaks(void)1097 void __merge_breaks(void)
1098 {
1099 	struct stree *stree;
1100 	struct sm_state *sm;
1101 
1102 	stree = pop_stree(&break_stack);
1103 	merge_stree(&cur_stree, stree);
1104 	free_stree(&stree);
1105 
1106 	if (!fake_cur_stree_stack)
1107 		return;
1108 
1109 	stree = pop_stree(&fake_break_stack);
1110 	update_stree_with_merged(&stree);
1111 	FOR_EACH_SM(stree, sm) {
1112 		overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1113 	} END_FOR_EACH_SM(sm);
1114 	free_stree(&stree);
1115 }
1116 
__use_breaks(void)1117 void __use_breaks(void)
1118 {
1119 	struct stree *stree;
1120 	struct sm_state *sm;
1121 
1122 	free_stree(&cur_stree);
1123 	cur_stree = pop_stree(&break_stack);
1124 
1125 	if (!fake_cur_stree_stack)
1126 		return;
1127 	stree = pop_stree(&fake_break_stack);
1128 	FOR_EACH_SM(stree, sm) {
1129 		overwrite_sm_state_stree_stack(&fake_cur_stree_stack, sm);
1130 	} END_FOR_EACH_SM(sm);
1131 	free_stree(&stree);
1132 
1133 
1134 }
1135 
__save_switch_states(struct expression * switch_expr)1136 void __save_switch_states(struct expression *switch_expr)
1137 {
1138 	struct range_list *rl;
1139 
1140 	get_absolute_rl(switch_expr, &rl);
1141 
1142 	push_rl(&remaining_cases, rl);
1143 	push_stree(&switch_stack, clone_stree(cur_stree));
1144 }
1145 
have_remaining_cases(void)1146 int have_remaining_cases(void)
1147 {
1148 	return !!top_rl(remaining_cases);
1149 }
1150 
__merge_switches(struct expression * switch_expr,struct range_list * case_rl)1151 void __merge_switches(struct expression *switch_expr, struct range_list *case_rl)
1152 {
1153 	struct stree *stree;
1154 	struct stree *implied_stree;
1155 
1156 	stree = pop_stree(&switch_stack);
1157 	if (!stree) {
1158 		/*
1159 		 * If the cur_stree was NULL before the start of the switch
1160 		 * statement then we don't want to unnullify it.
1161 		 *
1162 		 */
1163 		push_stree(&switch_stack, stree);
1164 		return;
1165 	}
1166 	implied_stree = __implied_case_stree(switch_expr, case_rl, &remaining_cases, &stree);
1167 	merge_stree(&cur_stree, implied_stree);
1168 	free_stree(&implied_stree);
1169 	push_stree(&switch_stack, stree);
1170 }
1171 
__discard_switches(void)1172 void __discard_switches(void)
1173 {
1174 	struct stree *stree;
1175 
1176 	pop_rl(&remaining_cases);
1177 	stree = pop_stree(&switch_stack);
1178 	free_stree(&stree);
1179 }
1180 
__push_default(void)1181 void __push_default(void)
1182 {
1183 	push_stree(&default_stack, NULL);
1184 }
1185 
__set_default(void)1186 void __set_default(void)
1187 {
1188 	set_state_stree_stack(&default_stack, 0, "has_default", NULL, &true_state);
1189 }
1190 
__pop_default(void)1191 int __pop_default(void)
1192 {
1193 	struct stree *stree;
1194 
1195 	stree = pop_stree(&default_stack);
1196 	if (stree) {
1197 		free_stree(&stree);
1198 		return 1;
1199 	}
1200 	return 0;
1201 }
1202 
alloc_named_stree(const char * name,struct symbol * sym,struct stree * stree)1203 static struct named_stree *alloc_named_stree(const char *name, struct symbol *sym, struct stree *stree)
1204 {
1205 	struct named_stree *named_stree = __alloc_named_stree(0);
1206 
1207 	named_stree->name = (char *)name;
1208 	named_stree->stree = stree;
1209 	named_stree->sym = sym;
1210 	return named_stree;
1211 }
1212 
__save_gotos(const char * name,struct symbol * sym)1213 void __save_gotos(const char *name, struct symbol *sym)
1214 {
1215 	struct stree **stree;
1216 	struct stree *clone;
1217 
1218 	stree = get_named_stree(goto_stack, name, sym);
1219 	if (stree) {
1220 		merge_stree(stree, cur_stree);
1221 		return;
1222 	} else {
1223 		struct named_stree *named_stree;
1224 
1225 		clone = clone_stree(cur_stree);
1226 		named_stree = alloc_named_stree(name, sym, clone);
1227 		add_ptr_list(&goto_stack, named_stree);
1228 	}
1229 }
1230 
__merge_gotos(const char * name,struct symbol * sym)1231 void __merge_gotos(const char *name, struct symbol *sym)
1232 {
1233 	struct stree **stree;
1234 
1235 	stree = get_named_stree(goto_stack, name, sym);
1236 	if (stree)
1237 		merge_stree(&cur_stree, *stree);
1238 }
1239