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 == two)
460 return one;
461 if (out_of_memory()) {
462 if (!warned)
463 sm_warning("Function too hairy. No more merges.");
464 warned = 1;
465 return one;
466 }
467 warned = 0;
468 s = merge_states(one->owner, one->name, one->sym, one->state, two->state);
469 result = alloc_state_no_name(one->owner, one->name, one->sym, s);
470 result->merged = 1;
471 result->left = one;
472 result->right = two;
473
474 copy_possibles(result, one, two);
475
476 /*
477 * The ->line information is used by deref_check where we complain about
478 * checking pointers that have already been dereferenced. Let's say we
479 * dereference a pointer on both the true and false paths and then merge
480 * the states here. The result state is &derefed, but the ->line number
481 * is on the line where the pointer is merged not where it was
482 * dereferenced..
483 *
484 * So in that case, let's just pick one dereference and set the ->line
485 * to point at it.
486 *
487 */
488
489 if (result->state == one->state)
490 result->line = one->line;
491 if (result->state == two->state)
492 result->line = two->line;
493
494 if (option_debug ||
495 strcmp(check_name(one->owner), option_debug_check) == 0) {
496 struct sm_state *tmp;
497 int i = 0;
498
499 printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (",
500 get_filename(), get_lineno(), get_function(),
501 check_name(one->owner), one->name,
502 show_state(one->state), one->line,
503 show_state(two->state), two->line,
504 show_state(s));
505
506 FOR_EACH_PTR(result->possible, tmp) {
507 if (i++)
508 printf(", ");
509 printf("%s", show_state(tmp->state));
510 } END_FOR_EACH_PTR(tmp);
511 printf(")\n");
512 }
513
514 return result;
515 }
516
517 struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name,
518 struct symbol *sym)
519 {
520 struct tracker tracker = {
521 .owner = owner,
522 .name = (char *)name,
523 .sym = sym,
524 };
525
526 if (!name)
527 return NULL;
528
529
530 return avl_lookup(stree, (struct sm_state *)&tracker);
531 }
532
533 struct smatch_state *get_state_stree(struct stree *stree,
534 int owner, const char *name,
535 struct symbol *sym)
536 {
537 struct sm_state *sm;
538
539 sm = get_sm_state_stree(stree, owner, name, sym);
540 if (sm)
541 return sm->state;
542 return NULL;
543 }
544
545 /* FIXME: this is almost exactly the same as set_sm_state_slist() */
546 void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new)
547 {
548 avl_insert(stree, new);
549 }
550
551 void overwrite_sm_state_stree_stack(struct stree_stack **stack,
552 struct sm_state *sm)
553 {
554 struct stree *stree;
555
556 stree = pop_stree(stack);
557 overwrite_sm_state_stree(&stree, sm);
558 push_stree(stack, stree);
559 }
560
561 struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name,
562 struct symbol *sym, struct smatch_state *state)
563 {
564 struct sm_state *new = alloc_sm_state(owner, name, sym, state);
565
566 avl_insert(stree, new);
567 return new;
568 }
569
570 void set_state_stree_perm(struct stree **stree, int owner, const char *name,
571 struct symbol *sym, struct smatch_state *state)
572 {
573 struct sm_state *sm;
574
575 sm = malloc(sizeof(*sm) + strlen(name) + 1);
576 memset(sm, 0, sizeof(*sm));
577 sm->owner = owner;
578 sm->name = (char *)(sm + 1);
579 strcpy((char *)sm->name, name);
580 sm->sym = sym;
581 sm->state = state;
582
583 overwrite_sm_state_stree(stree, sm);
584 }
585
586 void delete_state_stree(struct stree **stree, int owner, const char *name,
587 struct symbol *sym)
588 {
589 struct tracker tracker = {
590 .owner = owner,
591 .name = (char *)name,
592 .sym = sym,
593 };
594
595 avl_remove(stree, (struct sm_state *)&tracker);
596 }
597
598 void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
599 struct symbol *sym)
600 {
601 struct stree *stree;
602
603 stree = pop_stree(stack);
604 delete_state_stree(&stree, owner, name, sym);
605 push_stree(stack, stree);
606 }
607
608 void push_stree(struct stree_stack **stack, struct stree *stree)
609 {
610 add_ptr_list(stack, stree);
611 }
612
613 struct stree *pop_stree(struct stree_stack **stack)
614 {
615 struct stree *stree;
616
617 stree = last_ptr_list((struct ptr_list *)*stack);
618 delete_ptr_list_last((struct ptr_list **)stack);
619 return stree;
620 }
621
622 struct stree *top_stree(struct stree_stack *stack)
623 {
624 return last_ptr_list((struct ptr_list *)stack);
625 }
626
627 void free_slist(struct state_list **slist)
628 {
629 __free_ptr_list((struct ptr_list **)slist);
630 }
631
632 void free_stree_stack(struct stree_stack **stack)
633 {
634 __free_ptr_list((struct ptr_list **)stack);
635 }
636
637 void free_stack_and_strees(struct stree_stack **stree_stack)
638 {
639 struct stree *stree;
640
641 FOR_EACH_PTR(*stree_stack, stree) {
642 free_stree(&stree);
643 } END_FOR_EACH_PTR(stree);
644 free_stree_stack(stree_stack);
645 }
646
647 struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name,
648 struct symbol *sym, struct smatch_state *state)
649 {
650 struct stree *stree;
651 struct sm_state *sm;
652
653 stree = pop_stree(stack);
654 sm = set_state_stree(&stree, owner, name, sym, state);
655 push_stree(stack, stree);
656
657 return sm;
658 }
659
660 /*
661 * get_sm_state_stack() gets the state for the top slist on the stack.
662 */
663 struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack,
664 int owner, const char *name,
665 struct symbol *sym)
666 {
667 struct stree *stree;
668 struct sm_state *ret;
669
670 stree = pop_stree(&stack);
671 ret = get_sm_state_stree(stree, owner, name, sym);
672 push_stree(&stack, stree);
673 return ret;
674 }
675
676 struct smatch_state *get_state_stree_stack(struct stree_stack *stack,
677 int owner, const char *name,
678 struct symbol *sym)
679 {
680 struct sm_state *sm;
681
682 sm = get_sm_state_stree_stack(stack, owner, name, sym);
683 if (sm)
684 return sm->state;
685 return NULL;
686 }
687
688 static void match_states_stree(struct stree **one, struct stree **two)
689 {
690 struct smatch_state *tmp_state;
691 struct sm_state *sm;
692 struct state_list *add_to_one = NULL;
693 struct state_list *add_to_two = NULL;
694 AvlIter one_iter;
695 AvlIter two_iter;
696
697 __set_cur_stree_readonly();
698
699 avl_iter_begin(&one_iter, *one, FORWARD);
700 avl_iter_begin(&two_iter, *two, FORWARD);
701
702 for (;;) {
703 if (!one_iter.sm && !two_iter.sm)
704 break;
705 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
706 __set_fake_cur_stree_fast(*two);
707 __in_unmatched_hook++;
708 tmp_state = __client_unmatched_state_function(one_iter.sm);
709 __in_unmatched_hook--;
710 __pop_fake_cur_stree_fast();
711 sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name,
712 one_iter.sm->sym, tmp_state);
713 add_ptr_list(&add_to_two, sm);
714 avl_iter_next(&one_iter);
715 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
716 avl_iter_next(&one_iter);
717 avl_iter_next(&two_iter);
718 } else {
719 __set_fake_cur_stree_fast(*one);
720 __in_unmatched_hook++;
721 tmp_state = __client_unmatched_state_function(two_iter.sm);
722 __in_unmatched_hook--;
723 __pop_fake_cur_stree_fast();
724 sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name,
725 two_iter.sm->sym, tmp_state);
726 add_ptr_list(&add_to_one, sm);
727 avl_iter_next(&two_iter);
728 }
729 }
730
731 __set_cur_stree_writable();
732
733 FOR_EACH_PTR(add_to_one, sm) {
734 avl_insert(one, sm);
735 } END_FOR_EACH_PTR(sm);
736
737 FOR_EACH_PTR(add_to_two, sm) {
738 avl_insert(two, sm);
739 } END_FOR_EACH_PTR(sm);
740
741 free_slist(&add_to_one);
742 free_slist(&add_to_two);
743 }
744
745 static void call_pre_merge_hooks(struct stree **one, struct stree **two)
746 {
747 struct sm_state *sm, *cur;
748 struct stree *new;
749
750 __in_unmatched_hook++;
751
752 __set_fake_cur_stree_fast(*one);
753 __push_fake_cur_stree();
754 FOR_EACH_SM(*two, sm) {
755 cur = get_sm_state(sm->owner, sm->name, sm->sym);
756 if (cur == sm)
757 continue;
758 call_pre_merge_hook(cur, sm);
759 } END_FOR_EACH_SM(sm);
760 new = __pop_fake_cur_stree();
761 overwrite_stree(new, one);
762 free_stree(&new);
763 __pop_fake_cur_stree_fast();
764
765 __set_fake_cur_stree_fast(*two);
766 __push_fake_cur_stree();
767 FOR_EACH_SM(*one, sm) {
768 cur = get_sm_state(sm->owner, sm->name, sm->sym);
769 if (cur == sm)
770 continue;
771 call_pre_merge_hook(cur, sm);
772 } END_FOR_EACH_SM(sm);
773 new = __pop_fake_cur_stree();
774 overwrite_stree(new, two);
775 free_stree(&new);
776 __pop_fake_cur_stree_fast();
777
778 __in_unmatched_hook--;
779 }
780
781 static void clone_pool_havers_stree(struct stree **stree)
782 {
783 struct sm_state *sm, *tmp;
784 struct state_list *slist = NULL;
785
786 FOR_EACH_SM(*stree, sm) {
787 if (sm->pool) {
788 tmp = clone_sm(sm);
789 add_ptr_list(&slist, tmp);
790 }
791 } END_FOR_EACH_SM(sm);
792
793 FOR_EACH_PTR(slist, sm) {
794 avl_insert(stree, sm);
795 } END_FOR_EACH_PTR(sm);
796
797 free_slist(&slist);
798 }
799
800 int __stree_id;
801
802 /*
803 * merge_slist() is called whenever paths merge, such as after
804 * an if statement. It takes the two slists and creates one.
805 */
806 static void __merge_stree(struct stree **to, struct stree *stree, int add_pool)
807 {
808 struct stree *results = NULL;
809 struct stree *implied_one = NULL;
810 struct stree *implied_two = NULL;
811 AvlIter one_iter;
812 AvlIter two_iter;
813 struct sm_state *one, *two, *res;
814
815 if (out_of_memory())
816 return;
817
818 /* merging a null and nonnull path gives you only the nonnull path */
819 if (!stree)
820 return;
821 if (*to == stree)
822 return;
823
824 if (!*to) {
825 *to = clone_stree(stree);
826 return;
827 }
828
829 implied_one = clone_stree(*to);
830 implied_two = clone_stree(stree);
831
832 match_states_stree(&implied_one, &implied_two);
833 call_pre_merge_hooks(&implied_one, &implied_two);
834
835 if (add_pool) {
836 clone_pool_havers_stree(&implied_one);
837 clone_pool_havers_stree(&implied_two);
838
839 set_stree_id(&implied_one, ++__stree_id);
840 set_stree_id(&implied_two, ++__stree_id);
841 if (implied_one->base_stree)
842 set_stree_id(&implied_one->base_stree, ++__stree_id);
843 if (implied_two->base_stree)
844 set_stree_id(&implied_two->base_stree, ++__stree_id);
845 }
846
847 push_stree(&all_pools, implied_one);
848 push_stree(&all_pools, implied_two);
849
850 avl_iter_begin(&one_iter, implied_one, FORWARD);
851 avl_iter_begin(&two_iter, implied_two, FORWARD);
852
853 for (;;) {
854 if (!one_iter.sm || !two_iter.sm)
855 break;
856
857 one = one_iter.sm;
858 two = two_iter.sm;
859
860 if (one == two) {
861 avl_insert(&results, one);
862 goto next;
863 }
864
865 if (add_pool) {
866 one->pool = implied_one;
867 if (implied_one->base_stree)
868 one->pool = implied_one->base_stree;
869 two->pool = implied_two;
870 if (implied_two->base_stree)
871 two->pool = implied_two->base_stree;
872 }
873 res = merge_sm_states(one, two);
874 add_possible_sm(res, one);
875 add_possible_sm(res, two);
876 avl_insert(&results, res);
877 next:
878 avl_iter_next(&one_iter);
879 avl_iter_next(&two_iter);
880 }
881
882 free_stree(to);
883 *to = results;
884 }
885
886 void merge_stree(struct stree **to, struct stree *stree)
887 {
888 __merge_stree(to, stree, 1);
889 }
890
891 void merge_stree_no_pools(struct stree **to, struct stree *stree)
892 {
893 __merge_stree(to, stree, 0);
894 }
895
896 /*
897 * This is unfortunately a bit subtle... The problem is that if a
898 * state is set on one fake stree but not the other then we should
899 * look up the the original state and use that as the unset state.
900 * Fortunately, after you pop your fake stree then the cur_slist should
901 * reflect the original state.
902 */
903 void merge_fake_stree(struct stree **to, struct stree *stree)
904 {
905 struct stree *one = *to;
906 struct stree *two = stree;
907 struct sm_state *sm;
908 struct state_list *add_to_one = NULL;
909 struct state_list *add_to_two = NULL;
910 AvlIter one_iter;
911 AvlIter two_iter;
912
913 if (!stree)
914 return;
915 if (*to == stree)
916 return;
917 if (!*to) {
918 *to = clone_stree(stree);
919 return;
920 }
921
922 avl_iter_begin(&one_iter, one, FORWARD);
923 avl_iter_begin(&two_iter, two, FORWARD);
924
925 for (;;) {
926 if (!one_iter.sm && !two_iter.sm)
927 break;
928 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
929 sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name,
930 one_iter.sm->sym);
931 if (sm)
932 add_ptr_list(&add_to_two, sm);
933 avl_iter_next(&one_iter);
934 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
935 avl_iter_next(&one_iter);
936 avl_iter_next(&two_iter);
937 } else {
938 sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name,
939 two_iter.sm->sym);
940 if (sm)
941 add_ptr_list(&add_to_one, sm);
942 avl_iter_next(&two_iter);
943 }
944 }
945
946 FOR_EACH_PTR(add_to_one, sm) {
947 avl_insert(&one, sm);
948 } END_FOR_EACH_PTR(sm);
949
950 FOR_EACH_PTR(add_to_two, sm) {
951 avl_insert(&two, sm);
952 } END_FOR_EACH_PTR(sm);
953
954 one->base_stree = clone_stree(__get_cur_stree());
955 FOR_EACH_SM(one, sm) {
956 avl_insert(&one->base_stree, sm);
957 } END_FOR_EACH_SM(sm);
958
959 two->base_stree = clone_stree(__get_cur_stree());
960 FOR_EACH_SM(two, sm) {
961 avl_insert(&two->base_stree, sm);
962 } END_FOR_EACH_SM(sm);
963
964 free_slist(&add_to_one);
965 free_slist(&add_to_two);
966
967 __merge_stree(&one, two, 1);
968
969 *to = one;
970 }
971
972 /*
973 * filter_slist() removes any sm states "slist" holds in common with "filter"
974 */
975 void filter_stree(struct stree **stree, struct stree *filter)
976 {
977 struct stree *results = NULL;
978 AvlIter one_iter;
979 AvlIter two_iter;
980
981 avl_iter_begin(&one_iter, *stree, FORWARD);
982 avl_iter_begin(&two_iter, filter, FORWARD);
983
984 /* FIXME: This should probably be re-written with trees in mind */
985
986 for (;;) {
987 if (!one_iter.sm && !two_iter.sm)
988 break;
989 if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) {
990 avl_insert(&results, one_iter.sm);
991 avl_iter_next(&one_iter);
992 } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) {
993 if (one_iter.sm != two_iter.sm)
994 avl_insert(&results, one_iter.sm);
995 avl_iter_next(&one_iter);
996 avl_iter_next(&two_iter);
997 } else {
998 avl_iter_next(&two_iter);
999 }
1000 }
1001
1002 free_stree(stree);
1003 *stree = results;
1004 }
1005
1006
1007 /*
1008 * and_slist_stack() pops the top two slists, overwriting the one with
1009 * the other and pushing it back on the stack.
1010 */
1011 void and_stree_stack(struct stree_stack **stack)
1012 {
1013 struct sm_state *tmp;
1014 struct stree *right_stree = pop_stree(stack);
1015
1016 FOR_EACH_SM(right_stree, tmp) {
1017 overwrite_sm_state_stree_stack(stack, tmp);
1018 } END_FOR_EACH_SM(tmp);
1019 free_stree(&right_stree);
1020 }
1021
1022 /*
1023 * or_slist_stack() is for if we have: if (foo || bar) { foo->baz;
1024 * It pops the two slists from the top of the stack and merges them
1025 * together in a way that preserves the things they have in common
1026 * but creates a merged state for most of the rest.
1027 * You could have code that had: if (foo || foo) { foo->baz;
1028 * It's this function which ensures smatch does the right thing.
1029 */
1030 void or_stree_stack(struct stree_stack **pre_conds,
1031 struct stree *cur_stree,
1032 struct stree_stack **stack)
1033 {
1034 struct stree *new;
1035 struct stree *old;
1036 struct stree *pre_stree;
1037 struct stree *res;
1038 struct stree *tmp_stree;
1039
1040 new = pop_stree(stack);
1041 old = pop_stree(stack);
1042
1043 pre_stree = pop_stree(pre_conds);
1044 push_stree(pre_conds, clone_stree(pre_stree));
1045
1046 res = clone_stree(pre_stree);
1047 overwrite_stree(old, &res);
1048
1049 tmp_stree = clone_stree(cur_stree);
1050 overwrite_stree(new, &tmp_stree);
1051
1052 merge_stree(&res, tmp_stree);
1053 filter_stree(&res, pre_stree);
1054
1055 push_stree(stack, res);
1056 free_stree(&tmp_stree);
1057 free_stree(&pre_stree);
1058 free_stree(&new);
1059 free_stree(&old);
1060 }
1061
1062 /*
1063 * get_named_stree() is only used for gotos.
1064 */
1065 struct stree **get_named_stree(struct named_stree_stack *stack,
1066 const char *name,
1067 struct symbol *sym)
1068 {
1069 struct named_stree *tmp;
1070
1071 FOR_EACH_PTR(stack, tmp) {
1072 if (tmp->sym == sym &&
1073 strcmp(tmp->name, name) == 0)
1074 return &tmp->stree;
1075 } END_FOR_EACH_PTR(tmp);
1076 return NULL;
1077 }
1078
1079 /* FIXME: These parameters are in a different order from expected */
1080 void overwrite_stree(struct stree *from, struct stree **to)
1081 {
1082 struct sm_state *tmp;
1083
1084 FOR_EACH_SM(from, tmp) {
1085 overwrite_sm_state_stree(to, tmp);
1086 } END_FOR_EACH_SM(tmp);
1087 }
1088