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