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
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
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 */
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;
126 void allocate_dynamic_states_array(int num_checks)
127 {
128 dynamic_states = calloc(num_checks + 1, sizeof(int));
129 }
130
131 void set_dynamic_states(unsigned short owner)
132 {
133 dynamic_states[owner] = true;
134 }
135
136 bool has_dynamic_states(unsigned short owner)
137 {
138 if (owner >= num_checks)
139 return false;
140 return dynamic_states[owner];
141 }
142
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
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
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
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
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
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
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 */
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
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
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
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 */
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
379 unsigned long get_pool_count(void)
380 {
381 return ptr_list_size((struct ptr_list *)all_pools);
382 }
383
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
399 int is_merged(struct sm_state *sm)
400 {
401 return sm->merged;
402 }
403
404 int is_leaf(struct sm_state *sm)
405 {
406 return !sm->merged;
407 }
408
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
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
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
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
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
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() */
549 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
550 {
551 avl_insert(stree, new);
552 }
553
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
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
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
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
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
611 void push_stree(struct stree_stack **stack, struct stree *stree)
612 {
613 add_ptr_list(stack, stree);
614 }
615
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
625 struct stree *top_stree(struct stree_stack *stack)
626 {
627 return last_ptr_list((struct ptr_list *)stack);
628 }
629
630 void free_slist(struct state_list **slist)
631 {
632 __free_ptr_list((struct ptr_list **)slist);
633 }
634
635 void free_stree_stack(struct stree_stack **stack)
636 {
637 __free_ptr_list((struct ptr_list **)stack);
638 }
639
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
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 */
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
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
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
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
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 */
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
889 void merge_stree(struct stree **to, struct stree *stree)
890 {
891 __merge_stree(to, stree, 1);
892 }
893
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 */
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 */
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 */
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 */
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 */
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 */
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