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