1 /*
2  * Copyright (C) 2008,2009 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 #include <stdlib.h>
19 #include <stdio.h>
20 #include "smatch.h"
21 #include "smatch_slist.h"
22 
23 #undef CHECKORDER
24 
25 ALLOCATOR(smatch_state, "smatch state");
26 ALLOCATOR(sm_state, "sm state");
27 ALLOCATOR(named_stree, "named slist");
28 __DO_ALLOCATOR(char, 1, 4, "state names", sname);
29 
30 int sm_state_counter;
31 
32 static struct stree_stack *all_pools;
33 
show_sm(struct sm_state * sm)34 const char *show_sm(struct sm_state *sm)
35 {
36 	static char buf[256];
37 	struct sm_state *tmp;
38 	int pos;
39 	int i;
40 
41 	if (!sm)
42 		return "<none>";
43 
44 	pos = snprintf(buf, sizeof(buf), "[%s] %s = '%s'%s",
45 		       check_name(sm->owner), sm->name, show_state(sm->state),
46 		       sm->merged ? " [merged]" : "");
47 	if (pos > sizeof(buf))
48 		goto truncate;
49 
50 	if (ptr_list_size((struct ptr_list *)sm->possible) == 1)
51 		return buf;
52 
53 	pos += snprintf(buf + pos, sizeof(buf) - pos, " (");
54 	if (pos > sizeof(buf))
55 		goto truncate;
56 	i = 0;
57 	FOR_EACH_PTR(sm->possible, tmp) {
58 		if (i++)
59 			pos += snprintf(buf + pos, sizeof(buf) - pos, ", ");
60 		if (pos > sizeof(buf))
61 			goto truncate;
62 		pos += snprintf(buf + pos, sizeof(buf) - pos, "%s",
63 			       show_state(tmp->state));
64 		if (pos > sizeof(buf))
65 			goto truncate;
66 	} END_FOR_EACH_PTR(tmp);
67 	snprintf(buf + pos, sizeof(buf) - pos, ")");
68 
69 	return buf;
70 
71 truncate:
72 	for (i = 0; i < 3; i++)
73 		buf[sizeof(buf) - 2 - i] = '.';
74 	return buf;
75 }
76 
__print_stree(struct stree * stree)77 void __print_stree(struct stree *stree)
78 {
79 	struct sm_state *sm;
80 
81 	option_debug++;
82 	sm_msg("dumping stree [%ld states]", stree_count(stree));
83 	FOR_EACH_SM(stree, sm) {
84 		sm_printf("%s\n", show_sm(sm));
85 	} END_FOR_EACH_SM(sm);
86 	sm_printf("---\n");
87 	option_debug--;
88 }
89 
90 /* NULL states go at the end to simplify merge_slist */
cmp_tracker(const struct sm_state * a,const struct sm_state * b)91 int cmp_tracker(const struct sm_state *a, const struct sm_state *b)
92 {
93 	int ret;
94 
95 	if (a == b)
96 		return 0;
97 	if (!b)
98 		return -1;
99 	if (!a)
100 		return 1;
101 
102 	if (a->owner < b->owner)
103 		return -1;
104 	if (a->owner > b->owner)
105 		return 1;
106 
107 	ret = strcmp(a->name, b->name);
108 	if (ret < 0)
109 		return -1;
110 	if (ret > 0)
111 		return 1;
112 
113 	if (!b->sym && a->sym)
114 		return -1;
115 	if (!a->sym && b->sym)
116 		return 1;
117 	if (a->sym < b->sym)
118 		return -1;
119 	if (a->sym > b->sym)
120 		return 1;
121 
122 	return 0;
123 }
124 
125 int *dynamic_states;
allocate_dynamic_states_array(int num_checks)126 void allocate_dynamic_states_array(int num_checks)
127 {
128 	dynamic_states = calloc(num_checks + 1, sizeof(int));
129 }
130 
set_dynamic_states(unsigned short owner)131 void set_dynamic_states(unsigned short owner)
132 {
133 	dynamic_states[owner] = true;
134 }
135 
has_dynamic_states(unsigned short owner)136 bool has_dynamic_states(unsigned short owner)
137 {
138 	if (owner >= num_checks)
139 		return false;
140 	return dynamic_states[owner];
141 }
142 
cmp_possible_sm(const struct sm_state * a,const struct sm_state * b,int preserve)143 static int cmp_possible_sm(const struct sm_state *a, const struct sm_state *b, int preserve)
144 {
145 	int ret;
146 
147 	if (a == b)
148 		return 0;
149 
150 	if (!has_dynamic_states(a->owner)) {
151 		if (a->state > b->state)
152 			return -1;
153 		if (a->state < b->state)
154 			return 1;
155 		return 0;
156 	}
157 
158 	if (a->owner == SMATCH_EXTRA) {
159 		/*
160 		 * In Smatch extra you can have borrowed implications.
161 		 *
162 		 * FIXME: review how borrowed implications work and if they
163 		 * are the best way.  See also smatch_implied.c.
164 		 *
165 		 */
166 		ret = cmp_tracker(a, b);
167 		if (ret)
168 			return ret;
169 
170 		/*
171 		 * We want to preserve leaf states.  They're use to split
172 		 * returns in smatch_db.c.
173 		 *
174 		 */
175 		if (preserve) {
176 			if (a->merged && !b->merged)
177 				return -1;
178 			if (!a->merged)
179 				return 1;
180 		}
181 	}
182 	if (!a->state->name || !b->state->name)
183 		return 0;
184 
185 	return strcmp(a->state->name, b->state->name);
186 }
187 
alloc_sm_state(int owner,const char * name,struct symbol * sym,struct smatch_state * state)188 struct sm_state *alloc_sm_state(int owner, const char *name,
189 				struct symbol *sym, struct smatch_state *state)
190 {
191 	struct sm_state *sm_state = __alloc_sm_state(0);
192 
193 	sm_state_counter++;
194 
195 	sm_state->name = alloc_sname(name);
196 	sm_state->owner = owner;
197 	sm_state->sym = sym;
198 	sm_state->state = state;
199 	sm_state->line = get_lineno();
200 	sm_state->merged = 0;
201 	sm_state->pool = NULL;
202 	sm_state->left = NULL;
203 	sm_state->right = NULL;
204 	sm_state->possible = NULL;
205 	add_ptr_list(&sm_state->possible, sm_state);
206 	return sm_state;
207 }
208 
alloc_state_no_name(int owner,const char * name,struct symbol * sym,struct smatch_state * state)209 static struct sm_state *alloc_state_no_name(int owner, const char *name,
210 				     struct symbol *sym,
211 				     struct smatch_state *state)
212 {
213 	struct sm_state *tmp;
214 
215 	tmp = alloc_sm_state(owner, NULL, sym, state);
216 	tmp->name = name;
217 	return tmp;
218 }
219 
too_many_possible(struct sm_state * sm)220 int too_many_possible(struct sm_state *sm)
221 {
222 	if (ptr_list_size((struct ptr_list *)sm->possible) >= 100)
223 		return 1;
224 	return 0;
225 }
226 
add_possible_sm(struct sm_state * to,struct sm_state * new)227 void add_possible_sm(struct sm_state *to, struct sm_state *new)
228 {
229 	struct sm_state *tmp;
230 	int preserve = 1;
231 	int cmp;
232 
233 	if (too_many_possible(to))
234 		preserve = 0;
235 
236 	FOR_EACH_PTR(to->possible, tmp) {
237 		cmp = cmp_possible_sm(tmp, new, preserve);
238 		if (cmp < 0)
239 			continue;
240 		else if (cmp == 0) {
241 			return;
242 		} else {
243 			INSERT_CURRENT(new, tmp);
244 			return;
245 		}
246 	} END_FOR_EACH_PTR(tmp);
247 	add_ptr_list(&to->possible, new);
248 }
249 
copy_possibles(struct sm_state * to,struct sm_state * one,struct sm_state * two)250 static void copy_possibles(struct sm_state *to, struct sm_state *one, struct sm_state *two)
251 {
252 	struct sm_state *large = one;
253 	struct sm_state *small = two;
254 	struct sm_state *tmp;
255 
256 	/*
257 	 * We spend a lot of time copying the possible lists.  I've tried to
258 	 * optimize the process a bit.
259 	 *
260 	 */
261 
262 	if (ptr_list_size((struct ptr_list *)two->possible) >
263 	    ptr_list_size((struct ptr_list *)one->possible)) {
264 		large = two;
265 		small = one;
266 	}
267 
268 	to->possible = clone_slist(large->possible);
269 	add_possible_sm(to, to);
270 	FOR_EACH_PTR(small->possible, tmp) {
271 		add_possible_sm(to, tmp);
272 	} END_FOR_EACH_PTR(tmp);
273 }
274 
alloc_sname(const char * str)275 char *alloc_sname(const char *str)
276 {
277 	char *tmp;
278 
279 	if (!str)
280 		return NULL;
281 	tmp = __alloc_sname(strlen(str) + 1);
282 	strcpy(tmp, str);
283 	return tmp;
284 }
285 
286 static struct symbol *oom_func;
287 static int oom_limit = 3000000;  /* Start with a 3GB limit */
out_of_memory(void)288 int out_of_memory(void)
289 {
290 	if (oom_func)
291 		return 1;
292 
293 	/*
294 	 * I decided to use 50M here based on trial and error.
295 	 * It works out OK for the kernel and so it should work
296 	 * for most other projects as well.
297 	 */
298 	if (sm_state_counter * sizeof(struct sm_state) >= 100000000)
299 		return 1;
300 
301 	/*
302 	 * We're reading from statm to figure out how much memory we
303 	 * are using.  The problem is that at the end of the function
304 	 * we release the memory, so that it can be re-used but it
305 	 * stays in cache, it's not released to the OS.  So then if
306 	 * we allocate memory for different purposes we can easily
307 	 * hit the 3GB limit on the next function, so that's why I give
308 	 * the next function an extra 100MB to work with.
309 	 *
310 	 */
311 	if (get_mem_kb() > oom_limit) {
312 		oom_func = cur_func_sym;
313 		final_pass++;
314 		sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter);
315 		final_pass--;
316 		return 1;
317 	}
318 
319 	return 0;
320 }
321 
low_on_memory(void)322 int low_on_memory(void)
323 {
324 	if (sm_state_counter * sizeof(struct sm_state) >= 25000000)
325 		return 1;
326 	return 0;
327 }
328 
free_sm_state(struct sm_state * sm)329 static void free_sm_state(struct sm_state *sm)
330 {
331 	free_slist(&sm->possible);
332 	/*
333 	 * fixme.  Free the actual state.
334 	 * Right now we leave it until the end of the function
335 	 * because we don't want to double free it.
336 	 * Use the freelist to not double free things
337 	 */
338 }
339 
free_all_sm_states(struct allocation_blob * blob)340 static void free_all_sm_states(struct allocation_blob *blob)
341 {
342 	unsigned int size = sizeof(struct sm_state);
343 	unsigned int offset = 0;
344 
345 	while (offset < blob->offset) {
346 		free_sm_state((struct sm_state *)(blob->data + offset));
347 		offset += size;
348 	}
349 }
350 
351 /* At the end of every function we free all the sm_states */
free_every_single_sm_state(void)352 void free_every_single_sm_state(void)
353 {
354 	struct allocator_struct *desc = &sm_state_allocator;
355 	struct allocation_blob *blob = desc->blobs;
356 
357 	desc->blobs = NULL;
358 	desc->allocations = 0;
359 	desc->total_bytes = 0;
360 	desc->useful_bytes = 0;
361 	desc->freelist = NULL;
362 	while (blob) {
363 		struct allocation_blob *next = blob->next;
364 		free_all_sm_states(blob);
365 		blob_free(blob, desc->chunking);
366 		blob = next;
367 	}
368 	clear_sname_alloc();
369 	clear_smatch_state_alloc();
370 
371 	free_stack_and_strees(&all_pools);
372 	sm_state_counter = 0;
373 	if (oom_func) {
374 		oom_limit += 100000;
375 		oom_func = NULL;
376 	}
377 }
378 
get_pool_count(void)379 unsigned long get_pool_count(void)
380 {
381 	return ptr_list_size((struct ptr_list *)all_pools);
382 }
383 
clone_sm(struct sm_state * s)384 struct sm_state *clone_sm(struct sm_state *s)
385 {
386 	struct sm_state *ret;
387 
388 	ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state);
389 	ret->merged = s->merged;
390 	ret->line = s->line;
391 	/* clone_sm() doesn't copy the pools.  Each state needs to have
392 	   only one pool. */
393 	ret->possible = clone_slist(s->possible);
394 	ret->left = s->left;
395 	ret->right = s->right;
396 	return ret;
397 }
398 
is_merged(struct sm_state * sm)399 int is_merged(struct sm_state *sm)
400 {
401 	return sm->merged;
402 }
403 
is_leaf(struct sm_state * sm)404 int is_leaf(struct sm_state *sm)
405 {
406 	return !sm->merged;
407 }
408 
slist_has_state(struct state_list * slist,struct smatch_state * state)409 int slist_has_state(struct state_list *slist, struct smatch_state *state)
410 {
411 	struct sm_state *tmp;
412 
413 	FOR_EACH_PTR(slist, tmp) {
414 		if (tmp->state == state)
415 			return 1;
416 	} END_FOR_EACH_PTR(tmp);
417 	return 0;
418 }
419 
clone_slist(struct state_list * from_slist)420 struct state_list *clone_slist(struct state_list *from_slist)
421 {
422 	struct sm_state *sm;
423 	struct state_list *to_slist = NULL;
424 
425 	FOR_EACH_PTR(from_slist, sm) {
426 		add_ptr_list(&to_slist, sm);
427 	} END_FOR_EACH_PTR(sm);
428 	return to_slist;
429 }
430 
merge_states(int owner,const char * name,struct symbol * sym,struct smatch_state * state1,struct smatch_state * state2)431 static struct smatch_state *merge_states(int owner, const char *name,
432 					 struct symbol *sym,
433 					 struct smatch_state *state1,
434 					 struct smatch_state *state2)
435 {
436 	struct smatch_state *ret;
437 
438 	if (state1 == state2)
439 		ret = state1;
440 	else if (__has_merge_function(owner))
441 		ret = __client_merge_function(owner, state1, state2);
442 	else if (state1 == &ghost)
443 		ret = state2;
444 	else if (state2 == &ghost)
445 		ret = state1;
446 	else if (!state1 || !state2)
447 		ret = &undefined;
448 	else
449 		ret = &merged;
450 	return ret;
451 }
452 
merge_sm_states(struct sm_state * one,struct sm_state * two)453 struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two)
454 {
455 	struct smatch_state *s;
456 	struct sm_state *result;
457 	static int warned;
458 
459 	if (one->state->data && !has_dynamic_states(one->owner))
460 		sm_msg("dynamic state: %s", show_sm(one));
461 
462 	if (one == two)
463 		return one;
464 	if (out_of_memory()) {
465 		if (!warned)
466 			sm_warning("Function too hairy.  No more merges.");
467 		warned = 1;
468 		return one;
469 	}
470 	warned = 0;
471 	s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
472 	result = alloc_state_no_name(one->owner, one->name, one->sym, s);
473 	result->merged = 1;
474 	result->left = one;
475 	result->right = two;
476 
477 	copy_possibles(result, one, two);
478 
479 	/*
480 	 * The ->line information is used by deref_check where we complain about
481 	 * checking pointers that have already been dereferenced.  Let's say we
482 	 * dereference a pointer on both the true and false paths and then merge
483 	 * the states here.  The result state is &derefed, but the ->line number
484 	 * is on the line where the pointer is merged not where it was
485 	 * dereferenced..
486 	 *
487 	 * So in that case, let's just pick one dereference and set the ->line
488 	 * to point at it.
489 	 *
490 	 */
491 
492 	if (result->state == one->state)
493 		result->line = one->line;
494 	if (result->state == two->state)
495 		result->line = two->line;
496 
497 	if (option_debug ||
498 	    strcmp(check_name(one->owner), option_debug_check) == 0) {
499 		struct sm_state *tmp;
500 		int i = 0;
501 
502 		printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
503 			get_filename(), get_lineno(), get_function(),
504 			check_name(one->owner), one->name,
505 			show_state(one->state), one->line,
506 			show_state(two->state), two->line,
507 			show_state(s));
508 
509 		FOR_EACH_PTR(result->possible, tmp) {
510 			if (i++)
511 				printf(", ");
512 			printf("%s", show_state(tmp->state));
513 		} END_FOR_EACH_PTR(tmp);
514 		printf(")\n");
515 	}
516 
517 	return result;
518 }
519 
get_sm_state_stree(struct stree * stree,int owner,const char * name,struct symbol * sym)520 struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
521 				struct symbol *sym)
522 {
523 	struct tracker tracker = {
524 		.owner = owner,
525 		.name = (char *)name,
526 		.sym = sym,
527 	};
528 
529 	if (!name)
530 		return NULL;
531 
532 
533 	return avl_lookup(stree, (struct sm_state *)&tracker);
534 }
535 
get_state_stree(struct stree * stree,int owner,const char * name,struct symbol * sym)536 struct smatch_state *get_state_stree(struct stree *stree,
537 				int owner, const char *name,
538 				struct symbol *sym)
539 {
540 	struct sm_state *sm;
541 
542 	sm = get_sm_state_stree(stree, owner, name, sym);
543 	if (sm)
544 		return sm->state;
545 	return NULL;
546 }
547 
548 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
overwrite_sm_state_stree(struct stree ** stree,struct sm_state * new)549 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
550 {
551 	avl_insert(stree, new);
552 }
553 
overwrite_sm_state_stree_stack(struct stree_stack ** stack,struct sm_state * sm)554 void overwrite_sm_state_stree_stack(struct stree_stack **stack,
555 			struct sm_state *sm)
556 {
557 	struct stree *stree;
558 
559 	stree = pop_stree(stack);
560 	overwrite_sm_state_stree(&stree, sm);
561 	push_stree(stack, stree);
562 }
563 
set_state_stree(struct stree ** stree,int owner,const char * name,struct symbol * sym,struct smatch_state * state)564 struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
565 		     struct symbol *sym, struct smatch_state *state)
566 {
567 	struct sm_state *new = alloc_sm_state(owner, name, sym, state);
568 
569 	avl_insert(stree, new);
570 	return new;
571 }
572 
set_state_stree_perm(struct stree ** stree,int owner,const char * name,struct symbol * sym,struct smatch_state * state)573 void set_state_stree_perm(struct stree **stree, int owner, const char *name,
574 		     struct symbol *sym, struct smatch_state *state)
575 {
576 	struct sm_state *sm;
577 
578 	sm = malloc(sizeof(*sm) + strlen(name) + 1);
579 	memset(sm, 0, sizeof(*sm));
580 	sm->owner = owner;
581 	sm->name = (char *)(sm + 1);
582 	strcpy((char *)sm->name, name);
583 	sm->sym = sym;
584 	sm->state = state;
585 
586 	overwrite_sm_state_stree(stree, sm);
587 }
588 
delete_state_stree(struct stree ** stree,int owner,const char * name,struct symbol * sym)589 void delete_state_stree(struct stree **stree, int owner, const char *name,
590 			struct symbol *sym)
591 {
592 	struct tracker tracker = {
593 		.owner = owner,
594 		.name = (char *)name,
595 		.sym = sym,
596 	};
597 
598 	avl_remove(stree, (struct sm_state *)&tracker);
599 }
600 
delete_state_stree_stack(struct stree_stack ** stack,int owner,const char * name,struct symbol * sym)601 void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
602 			struct symbol *sym)
603 {
604 	struct stree *stree;
605 
606 	stree = pop_stree(stack);
607 	delete_state_stree(&stree, owner, name, sym);
608 	push_stree(stack, stree);
609 }
610 
push_stree(struct stree_stack ** stack,struct stree * stree)611 void push_stree(struct stree_stack **stack, struct stree *stree)
612 {
613 	add_ptr_list(stack, stree);
614 }
615 
pop_stree(struct stree_stack ** stack)616 struct stree *pop_stree(struct stree_stack **stack)
617 {
618 	struct stree *stree;
619 
620 	stree = last_ptr_list((struct ptr_list *)*stack);
621 	delete_ptr_list_last((struct ptr_list **)stack);
622 	return stree;
623 }
624 
top_stree(struct stree_stack * stack)625 struct stree *top_stree(struct stree_stack *stack)
626 {
627 	return last_ptr_list((struct ptr_list *)stack);
628 }
629 
free_slist(struct state_list ** slist)630 void free_slist(struct state_list **slist)
631 {
632 	__free_ptr_list((struct ptr_list **)slist);
633 }
634 
free_stree_stack(struct stree_stack ** stack)635 void free_stree_stack(struct stree_stack **stack)
636 {
637 	__free_ptr_list((struct ptr_list **)stack);
638 }
639 
free_stack_and_strees(struct stree_stack ** stree_stack)640 void free_stack_and_strees(struct stree_stack **stree_stack)
641 {
642 	struct stree *stree;
643 
644 	FOR_EACH_PTR(*stree_stack, stree) {
645 		free_stree(&stree);
646 	} END_FOR_EACH_PTR(stree);
647 	free_stree_stack(stree_stack);
648 }
649 
set_state_stree_stack(struct stree_stack ** stack,int owner,const char * name,struct symbol * sym,struct smatch_state * state)650 struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
651 				struct symbol *sym, struct smatch_state *state)
652 {
653 	struct stree *stree;
654 	struct sm_state *sm;
655 
656 	stree = pop_stree(stack);
657 	sm = set_state_stree(&stree, owner, name, sym, state);
658 	push_stree(stack, stree);
659 
660 	return sm;
661 }
662 
663 /*
664  * get_sm_state_stack() gets the state for the top slist on the stack.
665  */
get_sm_state_stree_stack(struct stree_stack * stack,int owner,const char * name,struct symbol * sym)666 struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
667 				int owner, const char *name,
668 				struct symbol *sym)
669 {
670 	struct stree *stree;
671 	struct sm_state *ret;
672 
673 	stree = pop_stree(&stack);
674 	ret = get_sm_state_stree(stree, owner, name, sym);
675 	push_stree(&stack, stree);
676 	return ret;
677 }
678 
get_state_stree_stack(struct stree_stack * stack,int owner,const char * name,struct symbol * sym)679 struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
680 				int owner, const char *name,
681 				struct symbol *sym)
682 {
683 	struct sm_state *sm;
684 
685 	sm = get_sm_state_stree_stack(stack, owner, name, sym);
686 	if (sm)
687 		return sm->state;
688 	return NULL;
689 }
690 
match_states_stree(struct stree ** one,struct stree ** two)691 static void match_states_stree(struct stree **one, struct stree **two)
692 {
693 	struct smatch_state *tmp_state;
694 	struct sm_state *sm;
695 	struct state_list *add_to_one = NULL;
696 	struct state_list *add_to_two = NULL;
697 	AvlIter one_iter;
698 	AvlIter two_iter;
699 
700 	__set_cur_stree_readonly();
701 
702 	avl_iter_begin(&one_iter, *one, FORWARD);
703 	avl_iter_begin(&two_iter, *two, FORWARD);
704 
705 	for (;;) {
706 		if (!one_iter.sm && !two_iter.sm)
707 			break;
708 		if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
709 			__set_fake_cur_stree_fast(*two);
710 			__in_unmatched_hook++;
711 			tmp_state = __client_unmatched_state_function(one_iter.sm);
712 			__in_unmatched_hook--;
713 			__pop_fake_cur_stree_fast();
714 			sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
715 						  one_iter.sm->sym, tmp_state);
716 			add_ptr_list(&add_to_two, sm);
717 			avl_iter_next(&one_iter);
718 		} else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
719 			avl_iter_next(&one_iter);
720 			avl_iter_next(&two_iter);
721 		} else {
722 			__set_fake_cur_stree_fast(*one);
723 			__in_unmatched_hook++;
724 			tmp_state = __client_unmatched_state_function(two_iter.sm);
725 			__in_unmatched_hook--;
726 			__pop_fake_cur_stree_fast();
727 			sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
728 						  two_iter.sm->sym, tmp_state);
729 			add_ptr_list(&add_to_one, sm);
730 			avl_iter_next(&two_iter);
731 		}
732 	}
733 
734 	__set_cur_stree_writable();
735 
736 	FOR_EACH_PTR(add_to_one, sm) {
737 		avl_insert(one, sm);
738 	} END_FOR_EACH_PTR(sm);
739 
740 	FOR_EACH_PTR(add_to_two, sm) {
741 		avl_insert(two, sm);
742 	} END_FOR_EACH_PTR(sm);
743 
744 	free_slist(&add_to_one);
745 	free_slist(&add_to_two);
746 }
747 
call_pre_merge_hooks(struct stree ** one,struct stree ** two)748 static void call_pre_merge_hooks(struct stree **one, struct stree **two)
749 {
750 	struct sm_state *sm, *cur;
751 	struct stree *new;
752 
753 	__in_unmatched_hook++;
754 
755 	__set_fake_cur_stree_fast(*one);
756 	__push_fake_cur_stree();
757 	FOR_EACH_SM(*two, sm) {
758 		cur = get_sm_state(sm->owner, sm->name, sm->sym);
759 		if (cur == sm)
760 			continue;
761 		call_pre_merge_hook(cur, sm);
762 	} END_FOR_EACH_SM(sm);
763 	new = __pop_fake_cur_stree();
764 	overwrite_stree(new, one);
765 	free_stree(&new);
766 	__pop_fake_cur_stree_fast();
767 
768 	__set_fake_cur_stree_fast(*two);
769 	__push_fake_cur_stree();
770 	FOR_EACH_SM(*one, sm) {
771 		cur = get_sm_state(sm->owner, sm->name, sm->sym);
772 		if (cur == sm)
773 			continue;
774 		call_pre_merge_hook(cur, sm);
775 	} END_FOR_EACH_SM(sm);
776 	new = __pop_fake_cur_stree();
777 	overwrite_stree(new, two);
778 	free_stree(&new);
779 	__pop_fake_cur_stree_fast();
780 
781 	__in_unmatched_hook--;
782 }
783 
clone_pool_havers_stree(struct stree ** stree)784 static void clone_pool_havers_stree(struct stree **stree)
785 {
786 	struct sm_state *sm, *tmp;
787 	struct state_list *slist = NULL;
788 
789 	FOR_EACH_SM(*stree, sm) {
790 		if (sm->pool) {
791 			tmp = clone_sm(sm);
792 			add_ptr_list(&slist, tmp);
793 		}
794 	} END_FOR_EACH_SM(sm);
795 
796 	FOR_EACH_PTR(slist, sm) {
797 		avl_insert(stree, sm);
798 	} END_FOR_EACH_PTR(sm);
799 
800 	free_slist(&slist);
801 }
802 
803 int __stree_id;
804 
805 /*
806  * merge_slist() is called whenever paths merge, such as after
807  * an if statement.  It takes the two slists and creates one.
808  */
__merge_stree(struct stree ** to,struct stree * stree,int add_pool)809 static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
810 {
811 	struct stree *results = NULL;
812 	struct stree *implied_one = NULL;
813 	struct stree *implied_two = NULL;
814 	AvlIter one_iter;
815 	AvlIter two_iter;
816 	struct sm_state *one, *two, *res;
817 
818 	if (out_of_memory())
819 		return;
820 
821 	/* merging a null and nonnull path gives you only the nonnull path */
822 	if (!stree)
823 		return;
824 	if (*to == stree)
825 		return;
826 
827 	if (!*to) {
828 		*to = clone_stree(stree);
829 		return;
830 	}
831 
832 	implied_one = clone_stree(*to);
833 	implied_two = clone_stree(stree);
834 
835 	match_states_stree(&implied_one, &implied_two);
836 	call_pre_merge_hooks(&implied_one, &implied_two);
837 
838 	if (add_pool) {
839 		clone_pool_havers_stree(&implied_one);
840 		clone_pool_havers_stree(&implied_two);
841 
842 		set_stree_id(&implied_one, ++__stree_id);
843 		set_stree_id(&implied_two, ++__stree_id);
844 		if (implied_one->base_stree)
845 			set_stree_id(&implied_one->base_stree, ++__stree_id);
846 		if (implied_two->base_stree)
847 			set_stree_id(&implied_two->base_stree, ++__stree_id);
848 	}
849 
850 	push_stree(&all_pools, implied_one);
851 	push_stree(&all_pools, implied_two);
852 
853 	avl_iter_begin(&one_iter, implied_one, FORWARD);
854 	avl_iter_begin(&two_iter, implied_two, FORWARD);
855 
856 	for (;;) {
857 		if (!one_iter.sm || !two_iter.sm)
858 			break;
859 
860 		one = one_iter.sm;
861 		two = two_iter.sm;
862 
863 		if (one == two) {
864 			avl_insert(&results, one);
865 			goto next;
866 		}
867 
868 		if (add_pool) {
869 			one->pool = implied_one;
870 			if (implied_one->base_stree)
871 				one->pool = implied_one->base_stree;
872 			two->pool = implied_two;
873 			if (implied_two->base_stree)
874 				two->pool = implied_two->base_stree;
875 		}
876 		res = merge_sm_states(one, two);
877 		add_possible_sm(res, one);
878 		add_possible_sm(res, two);
879 		avl_insert(&results, res);
880 next:
881 		avl_iter_next(&one_iter);
882 		avl_iter_next(&two_iter);
883 	}
884 
885 	free_stree(to);
886 	*to = results;
887 }
888 
merge_stree(struct stree ** to,struct stree * stree)889 void merge_stree(struct stree **to, struct stree *stree)
890 {
891 	__merge_stree(to, stree, 1);
892 }
893 
merge_stree_no_pools(struct stree ** to,struct stree * stree)894 void merge_stree_no_pools(struct stree **to, struct stree *stree)
895 {
896 	__merge_stree(to, stree, 0);
897 }
898 
899 /*
900  * This is unfortunately a bit subtle...  The problem is that if a
901  * state is set on one fake stree but not the other then we should
902  * look up the the original state and use that as the unset state.
903  * Fortunately, after you pop your fake stree then the cur_slist should
904  * reflect the original state.
905  */
merge_fake_stree(struct stree ** to,struct stree * stree)906 void merge_fake_stree(struct stree **to, struct stree *stree)
907 {
908 	struct stree *one = *to;
909 	struct stree *two = stree;
910 	struct sm_state *sm;
911 	struct state_list *add_to_one = NULL;
912 	struct state_list *add_to_two = NULL;
913 	AvlIter one_iter;
914 	AvlIter two_iter;
915 
916 	if (!stree)
917 		return;
918 	if (*to == stree)
919 		return;
920 	if (!*to) {
921 		*to = clone_stree(stree);
922 		return;
923 	}
924 
925 	avl_iter_begin(&one_iter, one, FORWARD);
926 	avl_iter_begin(&two_iter, two, FORWARD);
927 
928 	for (;;) {
929 		if (!one_iter.sm && !two_iter.sm)
930 			break;
931 		if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
932 			sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name,
933 					  one_iter.sm->sym);
934 			if (sm)
935 				add_ptr_list(&add_to_two, sm);
936 			avl_iter_next(&one_iter);
937 		} else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
938 			avl_iter_next(&one_iter);
939 			avl_iter_next(&two_iter);
940 		} else {
941 			sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name,
942 					  two_iter.sm->sym);
943 			if (sm)
944 				add_ptr_list(&add_to_one, sm);
945 			avl_iter_next(&two_iter);
946 		}
947 	}
948 
949 	FOR_EACH_PTR(add_to_one, sm) {
950 		avl_insert(&one, sm);
951 	} END_FOR_EACH_PTR(sm);
952 
953 	FOR_EACH_PTR(add_to_two, sm) {
954 		avl_insert(&two, sm);
955 	} END_FOR_EACH_PTR(sm);
956 
957 	one->base_stree = clone_stree(__get_cur_stree());
958 	FOR_EACH_SM(one, sm) {
959 		avl_insert(&one->base_stree, sm);
960 	} END_FOR_EACH_SM(sm);
961 
962 	two->base_stree = clone_stree(__get_cur_stree());
963 	FOR_EACH_SM(two, sm) {
964 		avl_insert(&two->base_stree, sm);
965 	} END_FOR_EACH_SM(sm);
966 
967 	free_slist(&add_to_one);
968 	free_slist(&add_to_two);
969 
970 	__merge_stree(&one, two, 1);
971 
972 	*to = one;
973 }
974 
975 /*
976  * filter_slist() removes any sm states "slist" holds in common with "filter"
977  */
filter_stree(struct stree ** stree,struct stree * filter)978 void filter_stree(struct stree **stree, struct stree *filter)
979 {
980 	struct stree *results = NULL;
981 	AvlIter one_iter;
982 	AvlIter two_iter;
983 
984 	avl_iter_begin(&one_iter, *stree, FORWARD);
985 	avl_iter_begin(&two_iter, filter, FORWARD);
986 
987 	/* FIXME: This should probably be re-written with trees in mind */
988 
989 	for (;;) {
990 		if (!one_iter.sm && !two_iter.sm)
991 			break;
992 		if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
993 			avl_insert(&results, one_iter.sm);
994 			avl_iter_next(&one_iter);
995 		} else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
996 			if (one_iter.sm != two_iter.sm)
997 				avl_insert(&results, one_iter.sm);
998 			avl_iter_next(&one_iter);
999 			avl_iter_next(&two_iter);
1000 		} else {
1001 			avl_iter_next(&two_iter);
1002 		}
1003 	}
1004 
1005 	free_stree(stree);
1006 	*stree = results;
1007 }
1008 
1009 
1010 /*
1011  * and_slist_stack() pops the top two slists, overwriting the one with
1012  * the other and pushing it back on the stack.
1013  */
and_stree_stack(struct stree_stack ** stack)1014 void and_stree_stack(struct stree_stack **stack)
1015 {
1016 	struct sm_state *tmp;
1017 	struct stree *right_stree = pop_stree(stack);
1018 
1019 	FOR_EACH_SM(right_stree, tmp) {
1020 		overwrite_sm_state_stree_stack(stack, tmp);
1021 	} END_FOR_EACH_SM(tmp);
1022 	free_stree(&right_stree);
1023 }
1024 
1025 /*
1026  * or_slist_stack() is for if we have:  if (foo || bar) { foo->baz;
1027  * It pops the two slists from the top of the stack and merges them
1028  * together in a way that preserves the things they have in common
1029  * but creates a merged state for most of the rest.
1030  * You could have code that had:  if (foo || foo) { foo->baz;
1031  * It's this function which ensures smatch does the right thing.
1032  */
or_stree_stack(struct stree_stack ** pre_conds,struct stree * cur_stree,struct stree_stack ** stack)1033 void or_stree_stack(struct stree_stack **pre_conds,
1034 		    struct stree *cur_stree,
1035 		    struct stree_stack **stack)
1036 {
1037 	struct stree *new;
1038 	struct stree *old;
1039 	struct stree *pre_stree;
1040 	struct stree *res;
1041 	struct stree *tmp_stree;
1042 
1043 	new = pop_stree(stack);
1044 	old = pop_stree(stack);
1045 
1046 	pre_stree = pop_stree(pre_conds);
1047 	push_stree(pre_conds, clone_stree(pre_stree));
1048 
1049 	res = clone_stree(pre_stree);
1050 	overwrite_stree(old, &res);
1051 
1052 	tmp_stree = clone_stree(cur_stree);
1053 	overwrite_stree(new, &tmp_stree);
1054 
1055 	merge_stree(&res, tmp_stree);
1056 	filter_stree(&res, pre_stree);
1057 
1058 	push_stree(stack, res);
1059 	free_stree(&tmp_stree);
1060 	free_stree(&pre_stree);
1061 	free_stree(&new);
1062 	free_stree(&old);
1063 }
1064 
1065 /*
1066  * get_named_stree() is only used for gotos.
1067  */
get_named_stree(struct named_stree_stack * stack,const char * name,struct symbol * sym)1068 struct stree **get_named_stree(struct named_stree_stack *stack,
1069 			       const char *name,
1070 			       struct symbol *sym)
1071 {
1072 	struct named_stree *tmp;
1073 
1074 	FOR_EACH_PTR(stack, tmp) {
1075 		if (tmp->sym == sym &&
1076 		    strcmp(tmp->name, name) == 0)
1077 			return &tmp->stree;
1078 	} END_FOR_EACH_PTR(tmp);
1079 	return NULL;
1080 }
1081 
1082 /* FIXME:  These parameters are in a different order from expected */
overwrite_stree(struct stree * from,struct stree ** to)1083 void overwrite_stree(struct stree *from, struct stree **to)
1084 {
1085 	struct sm_state *tmp;
1086 
1087 	FOR_EACH_SM(from, tmp) {
1088 		overwrite_sm_state_stree(to, tmp);
1089 	} END_FOR_EACH_SM(tmp);
1090 }
1091 
1092