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