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