11f5207b7SJohn Levon /* 21f5207b7SJohn Levon * Copyright (C) 2008,2009 Dan Carpenter. 31f5207b7SJohn Levon * 41f5207b7SJohn Levon * This program is free software; you can redistribute it and/or 51f5207b7SJohn Levon * modify it under the terms of the GNU General Public License 61f5207b7SJohn Levon * as published by the Free Software Foundation; either version 2 71f5207b7SJohn Levon * of the License, or (at your option) any later version. 81f5207b7SJohn Levon * 91f5207b7SJohn Levon * This program is distributed in the hope that it will be useful, 101f5207b7SJohn Levon * but WITHOUT ANY WARRANTY; without even the implied warranty of 111f5207b7SJohn Levon * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 121f5207b7SJohn Levon * GNU General Public License for more details. 131f5207b7SJohn Levon * 141f5207b7SJohn Levon * You should have received a copy of the GNU General Public License 151f5207b7SJohn Levon * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 161f5207b7SJohn Levon */ 171f5207b7SJohn Levon 181f5207b7SJohn Levon #include <stdlib.h> 191f5207b7SJohn Levon #include <stdio.h> 201f5207b7SJohn Levon #include "smatch.h" 211f5207b7SJohn Levon #include "smatch_slist.h" 221f5207b7SJohn Levon 231f5207b7SJohn Levon #undef CHECKORDER 241f5207b7SJohn Levon 251f5207b7SJohn Levon ALLOCATOR(smatch_state, "smatch state"); 261f5207b7SJohn Levon ALLOCATOR(sm_state, "sm state"); 271f5207b7SJohn Levon ALLOCATOR(named_stree, "named slist"); 281f5207b7SJohn Levon __DO_ALLOCATOR(char, 1, 4, "state names", sname); 291f5207b7SJohn Levon 301f5207b7SJohn Levon int sm_state_counter; 311f5207b7SJohn Levon 321f5207b7SJohn Levon static struct stree_stack *all_pools; 331f5207b7SJohn Levon 341f5207b7SJohn Levon const char *show_sm(struct sm_state *sm) 351f5207b7SJohn Levon { 361f5207b7SJohn Levon static char buf[256]; 371f5207b7SJohn Levon struct sm_state *tmp; 381f5207b7SJohn Levon int pos; 391f5207b7SJohn Levon int i; 401f5207b7SJohn Levon 411f5207b7SJohn Levon if (!sm) 421f5207b7SJohn Levon return "<none>"; 431f5207b7SJohn Levon 441f5207b7SJohn Levon pos = snprintf(buf, sizeof(buf), "[%s] '%s' = '%s'", 451f5207b7SJohn Levon check_name(sm->owner), sm->name, show_state(sm->state)); 461f5207b7SJohn Levon if (pos > sizeof(buf)) 471f5207b7SJohn Levon goto truncate; 481f5207b7SJohn Levon 491f5207b7SJohn Levon if (ptr_list_size((struct ptr_list *)sm->possible) == 1) 501f5207b7SJohn Levon return buf; 511f5207b7SJohn Levon 521f5207b7SJohn Levon pos += snprintf(buf + pos, sizeof(buf) - pos, " ("); 531f5207b7SJohn Levon if (pos > sizeof(buf)) 541f5207b7SJohn Levon goto truncate; 551f5207b7SJohn Levon i = 0; 561f5207b7SJohn Levon FOR_EACH_PTR(sm->possible, tmp) { 571f5207b7SJohn Levon if (i++) 581f5207b7SJohn Levon pos += snprintf(buf + pos, sizeof(buf) - pos, ", "); 591f5207b7SJohn Levon if (pos > sizeof(buf)) 601f5207b7SJohn Levon goto truncate; 611f5207b7SJohn Levon pos += snprintf(buf + pos, sizeof(buf) - pos, "%s", 621f5207b7SJohn Levon show_state(tmp->state)); 631f5207b7SJohn Levon if (pos > sizeof(buf)) 641f5207b7SJohn Levon goto truncate; 651f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 661f5207b7SJohn Levon snprintf(buf + pos, sizeof(buf) - pos, ")"); 671f5207b7SJohn Levon 681f5207b7SJohn Levon return buf; 691f5207b7SJohn Levon 701f5207b7SJohn Levon truncate: 711f5207b7SJohn Levon for (i = 0; i < 3; i++) 721f5207b7SJohn Levon buf[sizeof(buf) - 2 - i] = '.'; 731f5207b7SJohn Levon return buf; 741f5207b7SJohn Levon } 751f5207b7SJohn Levon 761f5207b7SJohn Levon void __print_stree(struct stree *stree) 771f5207b7SJohn Levon { 781f5207b7SJohn Levon struct sm_state *sm; 791f5207b7SJohn Levon 801f5207b7SJohn Levon printf("dumping stree at %d [%ld states]\n", get_lineno(), stree_count(stree)); 811f5207b7SJohn Levon FOR_EACH_SM(stree, sm) { 821f5207b7SJohn Levon printf("%s\n", show_sm(sm)); 831f5207b7SJohn Levon } END_FOR_EACH_SM(sm); 841f5207b7SJohn Levon printf("---\n"); 851f5207b7SJohn Levon } 861f5207b7SJohn Levon 871f5207b7SJohn Levon /* NULL states go at the end to simplify merge_slist */ 881f5207b7SJohn Levon int cmp_tracker(const struct sm_state *a, const struct sm_state *b) 891f5207b7SJohn Levon { 901f5207b7SJohn Levon int ret; 911f5207b7SJohn Levon 921f5207b7SJohn Levon if (a == b) 931f5207b7SJohn Levon return 0; 941f5207b7SJohn Levon if (!b) 951f5207b7SJohn Levon return -1; 961f5207b7SJohn Levon if (!a) 971f5207b7SJohn Levon return 1; 981f5207b7SJohn Levon 991f5207b7SJohn Levon if (a->owner < b->owner) 100*efe51d0cSJohn Levon return -1; 101*efe51d0cSJohn Levon if (a->owner > b->owner) 1021f5207b7SJohn Levon return 1; 1031f5207b7SJohn Levon 1041f5207b7SJohn Levon ret = strcmp(a->name, b->name); 1051f5207b7SJohn Levon if (ret < 0) 1061f5207b7SJohn Levon return -1; 1071f5207b7SJohn Levon if (ret > 0) 1081f5207b7SJohn Levon return 1; 1091f5207b7SJohn Levon 1101f5207b7SJohn Levon if (!b->sym && a->sym) 1111f5207b7SJohn Levon return -1; 1121f5207b7SJohn Levon if (!a->sym && b->sym) 1131f5207b7SJohn Levon return 1; 1141f5207b7SJohn Levon if (a->sym < b->sym) 1151f5207b7SJohn Levon return -1; 1161f5207b7SJohn Levon if (a->sym > b->sym) 1171f5207b7SJohn Levon return 1; 1181f5207b7SJohn Levon 1191f5207b7SJohn Levon return 0; 1201f5207b7SJohn Levon } 1211f5207b7SJohn Levon 122*efe51d0cSJohn Levon int *dynamic_states; 123*efe51d0cSJohn Levon void allocate_dynamic_states_array(int num_checks) 124*efe51d0cSJohn Levon { 125*efe51d0cSJohn Levon dynamic_states = calloc(num_checks + 1, sizeof(int)); 126*efe51d0cSJohn Levon } 127*efe51d0cSJohn Levon 128*efe51d0cSJohn Levon void set_dynamic_states(unsigned short owner) 129*efe51d0cSJohn Levon { 130*efe51d0cSJohn Levon dynamic_states[owner] = true; 131*efe51d0cSJohn Levon } 132*efe51d0cSJohn Levon 133*efe51d0cSJohn Levon bool has_dynamic_states(unsigned short owner) 134*efe51d0cSJohn Levon { 135*efe51d0cSJohn Levon if (owner >= num_checks) 136*efe51d0cSJohn Levon return false; 137*efe51d0cSJohn Levon return dynamic_states[owner]; 138*efe51d0cSJohn Levon } 139*efe51d0cSJohn Levon 140*efe51d0cSJohn Levon static int cmp_possible_sm(const struct sm_state *a, const struct sm_state *b, int preserve) 1411f5207b7SJohn Levon { 1421f5207b7SJohn Levon int ret; 1431f5207b7SJohn Levon 144*efe51d0cSJohn Levon if (a == b) 145*efe51d0cSJohn Levon return 0; 1461f5207b7SJohn Levon 147*efe51d0cSJohn Levon if (!has_dynamic_states(a->owner)) { 148*efe51d0cSJohn Levon if (a->state > b->state) 1491f5207b7SJohn Levon return -1; 150*efe51d0cSJohn Levon if (a->state < b->state) 1511f5207b7SJohn Levon return 1; 152*efe51d0cSJohn Levon return 0; 1531f5207b7SJohn Levon } 1541f5207b7SJohn Levon 155*efe51d0cSJohn Levon if (a->owner == SMATCH_EXTRA) { 156*efe51d0cSJohn Levon /* 157*efe51d0cSJohn Levon * In Smatch extra you can have borrowed implications. 158*efe51d0cSJohn Levon * 159*efe51d0cSJohn Levon * FIXME: review how borrowed implications work and if they 160*efe51d0cSJohn Levon * are the best way. See also smatch_implied.c. 161*efe51d0cSJohn Levon * 162*efe51d0cSJohn Levon */ 163*efe51d0cSJohn Levon ret = cmp_tracker(a, b); 164*efe51d0cSJohn Levon if (ret) 165*efe51d0cSJohn Levon return ret; 166*efe51d0cSJohn Levon 167*efe51d0cSJohn Levon /* 168*efe51d0cSJohn Levon * We want to preserve leaf states. They're use to split 169*efe51d0cSJohn Levon * returns in smatch_db.c. 170*efe51d0cSJohn Levon * 171*efe51d0cSJohn Levon */ 172*efe51d0cSJohn Levon if (preserve) { 173*efe51d0cSJohn Levon if (a->merged && !b->merged) 174*efe51d0cSJohn Levon return -1; 175*efe51d0cSJohn Levon if (!a->merged) 176*efe51d0cSJohn Levon return 1; 177*efe51d0cSJohn Levon } 178*efe51d0cSJohn Levon } 179*efe51d0cSJohn Levon if (!a->state->name || !b->state->name) 180*efe51d0cSJohn Levon return 0; 181*efe51d0cSJohn Levon 182*efe51d0cSJohn Levon return strcmp(a->state->name, b->state->name); 1831f5207b7SJohn Levon } 1841f5207b7SJohn Levon 1851f5207b7SJohn Levon struct sm_state *alloc_sm_state(int owner, const char *name, 1861f5207b7SJohn Levon struct symbol *sym, struct smatch_state *state) 1871f5207b7SJohn Levon { 1881f5207b7SJohn Levon struct sm_state *sm_state = __alloc_sm_state(0); 1891f5207b7SJohn Levon 1901f5207b7SJohn Levon sm_state_counter++; 1911f5207b7SJohn Levon 1921f5207b7SJohn Levon sm_state->name = alloc_sname(name); 1931f5207b7SJohn Levon sm_state->owner = owner; 1941f5207b7SJohn Levon sm_state->sym = sym; 1951f5207b7SJohn Levon sm_state->state = state; 1961f5207b7SJohn Levon sm_state->line = get_lineno(); 1971f5207b7SJohn Levon sm_state->merged = 0; 1981f5207b7SJohn Levon sm_state->pool = NULL; 1991f5207b7SJohn Levon sm_state->left = NULL; 2001f5207b7SJohn Levon sm_state->right = NULL; 2011f5207b7SJohn Levon sm_state->possible = NULL; 2021f5207b7SJohn Levon add_ptr_list(&sm_state->possible, sm_state); 2031f5207b7SJohn Levon return sm_state; 2041f5207b7SJohn Levon } 2051f5207b7SJohn Levon 2061f5207b7SJohn Levon static struct sm_state *alloc_state_no_name(int owner, const char *name, 2071f5207b7SJohn Levon struct symbol *sym, 2081f5207b7SJohn Levon struct smatch_state *state) 2091f5207b7SJohn Levon { 2101f5207b7SJohn Levon struct sm_state *tmp; 2111f5207b7SJohn Levon 2121f5207b7SJohn Levon tmp = alloc_sm_state(owner, NULL, sym, state); 2131f5207b7SJohn Levon tmp->name = name; 2141f5207b7SJohn Levon return tmp; 2151f5207b7SJohn Levon } 2161f5207b7SJohn Levon 2171f5207b7SJohn Levon int too_many_possible(struct sm_state *sm) 2181f5207b7SJohn Levon { 2191f5207b7SJohn Levon if (ptr_list_size((struct ptr_list *)sm->possible) >= 100) 2201f5207b7SJohn Levon return 1; 2211f5207b7SJohn Levon return 0; 2221f5207b7SJohn Levon } 2231f5207b7SJohn Levon 2241f5207b7SJohn Levon void add_possible_sm(struct sm_state *to, struct sm_state *new) 2251f5207b7SJohn Levon { 2261f5207b7SJohn Levon struct sm_state *tmp; 2271f5207b7SJohn Levon int preserve = 1; 228*efe51d0cSJohn Levon int cmp; 2291f5207b7SJohn Levon 2301f5207b7SJohn Levon if (too_many_possible(to)) 2311f5207b7SJohn Levon preserve = 0; 2321f5207b7SJohn Levon 2331f5207b7SJohn Levon FOR_EACH_PTR(to->possible, tmp) { 234*efe51d0cSJohn Levon cmp = cmp_possible_sm(tmp, new, preserve); 235*efe51d0cSJohn Levon if (cmp < 0) 2361f5207b7SJohn Levon continue; 237*efe51d0cSJohn Levon else if (cmp == 0) { 2381f5207b7SJohn Levon return; 2391f5207b7SJohn Levon } else { 2401f5207b7SJohn Levon INSERT_CURRENT(new, tmp); 2411f5207b7SJohn Levon return; 2421f5207b7SJohn Levon } 2431f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 2441f5207b7SJohn Levon add_ptr_list(&to->possible, new); 2451f5207b7SJohn Levon } 2461f5207b7SJohn Levon 247*efe51d0cSJohn Levon static void copy_possibles(struct sm_state *to, struct sm_state *one, struct sm_state *two) 2481f5207b7SJohn Levon { 249*efe51d0cSJohn Levon struct sm_state *large = one; 250*efe51d0cSJohn Levon struct sm_state *small = two; 2511f5207b7SJohn Levon struct sm_state *tmp; 2521f5207b7SJohn Levon 253*efe51d0cSJohn Levon /* 254*efe51d0cSJohn Levon * We spend a lot of time copying the possible lists. I've tried to 255*efe51d0cSJohn Levon * optimize the process a bit. 256*efe51d0cSJohn Levon * 257*efe51d0cSJohn Levon */ 258*efe51d0cSJohn Levon 259*efe51d0cSJohn Levon if (ptr_list_size((struct ptr_list *)two->possible) > 260*efe51d0cSJohn Levon ptr_list_size((struct ptr_list *)one->possible)) { 261*efe51d0cSJohn Levon large = two; 262*efe51d0cSJohn Levon small = one; 263*efe51d0cSJohn Levon } 264*efe51d0cSJohn Levon 265*efe51d0cSJohn Levon to->possible = clone_slist(large->possible); 266*efe51d0cSJohn Levon add_possible_sm(to, to); 267*efe51d0cSJohn Levon FOR_EACH_PTR(small->possible, tmp) { 2681f5207b7SJohn Levon add_possible_sm(to, tmp); 2691f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 2701f5207b7SJohn Levon } 2711f5207b7SJohn Levon 2721f5207b7SJohn Levon char *alloc_sname(const char *str) 2731f5207b7SJohn Levon { 2741f5207b7SJohn Levon char *tmp; 2751f5207b7SJohn Levon 2761f5207b7SJohn Levon if (!str) 2771f5207b7SJohn Levon return NULL; 2781f5207b7SJohn Levon tmp = __alloc_sname(strlen(str) + 1); 2791f5207b7SJohn Levon strcpy(tmp, str); 2801f5207b7SJohn Levon return tmp; 2811f5207b7SJohn Levon } 2821f5207b7SJohn Levon 283*efe51d0cSJohn Levon static struct symbol *oom_func; 284*efe51d0cSJohn Levon static int oom_limit = 3000000; /* Start with a 3GB limit */ 2851f5207b7SJohn Levon int out_of_memory(void) 2861f5207b7SJohn Levon { 287*efe51d0cSJohn Levon if (oom_func) 288*efe51d0cSJohn Levon return 1; 289*efe51d0cSJohn Levon 2901f5207b7SJohn Levon /* 2911f5207b7SJohn Levon * I decided to use 50M here based on trial and error. 2921f5207b7SJohn Levon * It works out OK for the kernel and so it should work 2931f5207b7SJohn Levon * for most other projects as well. 2941f5207b7SJohn Levon */ 2951f5207b7SJohn Levon if (sm_state_counter * sizeof(struct sm_state) >= 100000000) 2961f5207b7SJohn Levon return 1; 297*efe51d0cSJohn Levon 298*efe51d0cSJohn Levon /* 299*efe51d0cSJohn Levon * We're reading from statm to figure out how much memory we 300*efe51d0cSJohn Levon * are using. The problem is that at the end of the function 301*efe51d0cSJohn Levon * we release the memory, so that it can be re-used but it 302*efe51d0cSJohn Levon * stays in cache, it's not released to the OS. So then if 303*efe51d0cSJohn Levon * we allocate memory for different purposes we can easily 304*efe51d0cSJohn Levon * hit the 3GB limit on the next function, so that's why I give 305*efe51d0cSJohn Levon * the next function an extra 100MB to work with. 306*efe51d0cSJohn Levon * 307*efe51d0cSJohn Levon */ 308*efe51d0cSJohn Levon if (get_mem_kb() > oom_limit) { 309*efe51d0cSJohn Levon oom_func = cur_func_sym; 310*efe51d0cSJohn Levon final_pass++; 311*efe51d0cSJohn Levon sm_perror("OOM: %luKb sm_state_count = %d", get_mem_kb(), sm_state_counter); 312*efe51d0cSJohn Levon final_pass--; 313*efe51d0cSJohn Levon return 1; 314*efe51d0cSJohn Levon } 315*efe51d0cSJohn Levon 3161f5207b7SJohn Levon return 0; 3171f5207b7SJohn Levon } 3181f5207b7SJohn Levon 3191f5207b7SJohn Levon int low_on_memory(void) 3201f5207b7SJohn Levon { 3211f5207b7SJohn Levon if (sm_state_counter * sizeof(struct sm_state) >= 25000000) 3221f5207b7SJohn Levon return 1; 3231f5207b7SJohn Levon return 0; 3241f5207b7SJohn Levon } 3251f5207b7SJohn Levon 3261f5207b7SJohn Levon static void free_sm_state(struct sm_state *sm) 3271f5207b7SJohn Levon { 3281f5207b7SJohn Levon free_slist(&sm->possible); 3291f5207b7SJohn Levon /* 3301f5207b7SJohn Levon * fixme. Free the actual state. 3311f5207b7SJohn Levon * Right now we leave it until the end of the function 3321f5207b7SJohn Levon * because we don't want to double free it. 3331f5207b7SJohn Levon * Use the freelist to not double free things 3341f5207b7SJohn Levon */ 3351f5207b7SJohn Levon } 3361f5207b7SJohn Levon 3371f5207b7SJohn Levon static void free_all_sm_states(struct allocation_blob *blob) 3381f5207b7SJohn Levon { 3391f5207b7SJohn Levon unsigned int size = sizeof(struct sm_state); 3401f5207b7SJohn Levon unsigned int offset = 0; 3411f5207b7SJohn Levon 3421f5207b7SJohn Levon while (offset < blob->offset) { 3431f5207b7SJohn Levon free_sm_state((struct sm_state *)(blob->data + offset)); 3441f5207b7SJohn Levon offset += size; 3451f5207b7SJohn Levon } 3461f5207b7SJohn Levon } 3471f5207b7SJohn Levon 3481f5207b7SJohn Levon /* At the end of every function we free all the sm_states */ 3491f5207b7SJohn Levon void free_every_single_sm_state(void) 3501f5207b7SJohn Levon { 3511f5207b7SJohn Levon struct allocator_struct *desc = &sm_state_allocator; 3521f5207b7SJohn Levon struct allocation_blob *blob = desc->blobs; 3531f5207b7SJohn Levon 3541f5207b7SJohn Levon desc->blobs = NULL; 3551f5207b7SJohn Levon desc->allocations = 0; 3561f5207b7SJohn Levon desc->total_bytes = 0; 3571f5207b7SJohn Levon desc->useful_bytes = 0; 3581f5207b7SJohn Levon desc->freelist = NULL; 3591f5207b7SJohn Levon while (blob) { 3601f5207b7SJohn Levon struct allocation_blob *next = blob->next; 3611f5207b7SJohn Levon free_all_sm_states(blob); 3621f5207b7SJohn Levon blob_free(blob, desc->chunking); 3631f5207b7SJohn Levon blob = next; 3641f5207b7SJohn Levon } 3651f5207b7SJohn Levon clear_sname_alloc(); 3661f5207b7SJohn Levon clear_smatch_state_alloc(); 3671f5207b7SJohn Levon 3681f5207b7SJohn Levon free_stack_and_strees(&all_pools); 3691f5207b7SJohn Levon sm_state_counter = 0; 370*efe51d0cSJohn Levon if (oom_func) { 371*efe51d0cSJohn Levon oom_limit += 100000; 372*efe51d0cSJohn Levon oom_func = NULL; 373*efe51d0cSJohn Levon } 3741f5207b7SJohn Levon } 3751f5207b7SJohn Levon 3761f5207b7SJohn Levon unsigned long get_pool_count(void) 3771f5207b7SJohn Levon { 3781f5207b7SJohn Levon return ptr_list_size((struct ptr_list *)all_pools); 3791f5207b7SJohn Levon } 3801f5207b7SJohn Levon 3811f5207b7SJohn Levon struct sm_state *clone_sm(struct sm_state *s) 3821f5207b7SJohn Levon { 3831f5207b7SJohn Levon struct sm_state *ret; 3841f5207b7SJohn Levon 3851f5207b7SJohn Levon ret = alloc_state_no_name(s->owner, s->name, s->sym, s->state); 3861f5207b7SJohn Levon ret->merged = s->merged; 3871f5207b7SJohn Levon ret->line = s->line; 3881f5207b7SJohn Levon /* clone_sm() doesn't copy the pools. Each state needs to have 3891f5207b7SJohn Levon only one pool. */ 3901f5207b7SJohn Levon ret->possible = clone_slist(s->possible); 3911f5207b7SJohn Levon ret->left = s->left; 3921f5207b7SJohn Levon ret->right = s->right; 3931f5207b7SJohn Levon return ret; 3941f5207b7SJohn Levon } 3951f5207b7SJohn Levon 3961f5207b7SJohn Levon int is_merged(struct sm_state *sm) 3971f5207b7SJohn Levon { 3981f5207b7SJohn Levon return sm->merged; 3991f5207b7SJohn Levon } 4001f5207b7SJohn Levon 4011f5207b7SJohn Levon int is_leaf(struct sm_state *sm) 4021f5207b7SJohn Levon { 4031f5207b7SJohn Levon return !sm->merged; 4041f5207b7SJohn Levon } 4051f5207b7SJohn Levon 4061f5207b7SJohn Levon int slist_has_state(struct state_list *slist, struct smatch_state *state) 4071f5207b7SJohn Levon { 4081f5207b7SJohn Levon struct sm_state *tmp; 4091f5207b7SJohn Levon 4101f5207b7SJohn Levon FOR_EACH_PTR(slist, tmp) { 4111f5207b7SJohn Levon if (tmp->state == state) 4121f5207b7SJohn Levon return 1; 4131f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 4141f5207b7SJohn Levon return 0; 4151f5207b7SJohn Levon } 4161f5207b7SJohn Levon 4171f5207b7SJohn Levon struct state_list *clone_slist(struct state_list *from_slist) 4181f5207b7SJohn Levon { 4191f5207b7SJohn Levon struct sm_state *sm; 4201f5207b7SJohn Levon struct state_list *to_slist = NULL; 4211f5207b7SJohn Levon 4221f5207b7SJohn Levon FOR_EACH_PTR(from_slist, sm) { 4231f5207b7SJohn Levon add_ptr_list(&to_slist, sm); 4241f5207b7SJohn Levon } END_FOR_EACH_PTR(sm); 4251f5207b7SJohn Levon return to_slist; 4261f5207b7SJohn Levon } 4271f5207b7SJohn Levon 4281f5207b7SJohn Levon static struct smatch_state *merge_states(int owner, const char *name, 4291f5207b7SJohn Levon struct symbol *sym, 4301f5207b7SJohn Levon struct smatch_state *state1, 4311f5207b7SJohn Levon struct smatch_state *state2) 4321f5207b7SJohn Levon { 4331f5207b7SJohn Levon struct smatch_state *ret; 4341f5207b7SJohn Levon 4351f5207b7SJohn Levon if (state1 == state2) 4361f5207b7SJohn Levon ret = state1; 4371f5207b7SJohn Levon else if (__has_merge_function(owner)) 4381f5207b7SJohn Levon ret = __client_merge_function(owner, state1, state2); 4391f5207b7SJohn Levon else if (state1 == &ghost) 4401f5207b7SJohn Levon ret = state2; 4411f5207b7SJohn Levon else if (state2 == &ghost) 4421f5207b7SJohn Levon ret = state1; 4431f5207b7SJohn Levon else if (!state1 || !state2) 4441f5207b7SJohn Levon ret = &undefined; 4451f5207b7SJohn Levon else 4461f5207b7SJohn Levon ret = &merged; 4471f5207b7SJohn Levon return ret; 4481f5207b7SJohn Levon } 4491f5207b7SJohn Levon 4501f5207b7SJohn Levon struct sm_state *merge_sm_states(struct sm_state *one, struct sm_state *two) 4511f5207b7SJohn Levon { 4521f5207b7SJohn Levon struct smatch_state *s; 4531f5207b7SJohn Levon struct sm_state *result; 4541f5207b7SJohn Levon static int warned; 4551f5207b7SJohn Levon 4561f5207b7SJohn Levon if (one == two) 4571f5207b7SJohn Levon return one; 4581f5207b7SJohn Levon if (out_of_memory()) { 4591f5207b7SJohn Levon if (!warned) 4601f5207b7SJohn Levon sm_warning("Function too hairy. No more merges."); 4611f5207b7SJohn Levon warned = 1; 4621f5207b7SJohn Levon return one; 4631f5207b7SJohn Levon } 4641f5207b7SJohn Levon warned = 0; 4651f5207b7SJohn Levon s = merge_states(one->owner, one->name, one->sym, one->state, two->state); 4661f5207b7SJohn Levon result = alloc_state_no_name(one->owner, one->name, one->sym, s); 4671f5207b7SJohn Levon result->merged = 1; 4681f5207b7SJohn Levon result->left = one; 4691f5207b7SJohn Levon result->right = two; 470*efe51d0cSJohn Levon 471*efe51d0cSJohn Levon copy_possibles(result, one, two); 4721f5207b7SJohn Levon 4731f5207b7SJohn Levon /* 4741f5207b7SJohn Levon * The ->line information is used by deref_check where we complain about 4751f5207b7SJohn Levon * checking pointers that have already been dereferenced. Let's say we 4761f5207b7SJohn Levon * dereference a pointer on both the true and false paths and then merge 4771f5207b7SJohn Levon * the states here. The result state is &derefed, but the ->line number 4781f5207b7SJohn Levon * is on the line where the pointer is merged not where it was 4791f5207b7SJohn Levon * dereferenced.. 4801f5207b7SJohn Levon * 4811f5207b7SJohn Levon * So in that case, let's just pick one dereference and set the ->line 4821f5207b7SJohn Levon * to point at it. 4831f5207b7SJohn Levon * 4841f5207b7SJohn Levon */ 4851f5207b7SJohn Levon 4861f5207b7SJohn Levon if (result->state == one->state) 4871f5207b7SJohn Levon result->line = one->line; 4881f5207b7SJohn Levon if (result->state == two->state) 4891f5207b7SJohn Levon result->line = two->line; 4901f5207b7SJohn Levon 4911f5207b7SJohn Levon if (option_debug || 4921f5207b7SJohn Levon strcmp(check_name(one->owner), option_debug_check) == 0) { 4931f5207b7SJohn Levon struct sm_state *tmp; 4941f5207b7SJohn Levon int i = 0; 4951f5207b7SJohn Levon 4961f5207b7SJohn Levon printf("%s:%d %s() merge [%s] '%s' %s(L %d) + %s(L %d) => %s (", 4971f5207b7SJohn Levon get_filename(), get_lineno(), get_function(), 4981f5207b7SJohn Levon check_name(one->owner), one->name, 4991f5207b7SJohn Levon show_state(one->state), one->line, 5001f5207b7SJohn Levon show_state(two->state), two->line, 5011f5207b7SJohn Levon show_state(s)); 5021f5207b7SJohn Levon 5031f5207b7SJohn Levon FOR_EACH_PTR(result->possible, tmp) { 5041f5207b7SJohn Levon if (i++) 5051f5207b7SJohn Levon printf(", "); 5061f5207b7SJohn Levon printf("%s", show_state(tmp->state)); 5071f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 5081f5207b7SJohn Levon printf(")\n"); 5091f5207b7SJohn Levon } 5101f5207b7SJohn Levon 5111f5207b7SJohn Levon return result; 5121f5207b7SJohn Levon } 5131f5207b7SJohn Levon 5141f5207b7SJohn Levon struct sm_state *get_sm_state_stree(struct stree *stree, int owner, const char *name, 5151f5207b7SJohn Levon struct symbol *sym) 5161f5207b7SJohn Levon { 5171f5207b7SJohn Levon struct tracker tracker = { 5181f5207b7SJohn Levon .owner = owner, 5191f5207b7SJohn Levon .name = (char *)name, 5201f5207b7SJohn Levon .sym = sym, 5211f5207b7SJohn Levon }; 5221f5207b7SJohn Levon 5231f5207b7SJohn Levon if (!name) 5241f5207b7SJohn Levon return NULL; 5251f5207b7SJohn Levon 5261f5207b7SJohn Levon 5271f5207b7SJohn Levon return avl_lookup(stree, (struct sm_state *)&tracker); 5281f5207b7SJohn Levon } 5291f5207b7SJohn Levon 5301f5207b7SJohn Levon struct smatch_state *get_state_stree(struct stree *stree, 5311f5207b7SJohn Levon int owner, const char *name, 5321f5207b7SJohn Levon struct symbol *sym) 5331f5207b7SJohn Levon { 5341f5207b7SJohn Levon struct sm_state *sm; 5351f5207b7SJohn Levon 5361f5207b7SJohn Levon sm = get_sm_state_stree(stree, owner, name, sym); 5371f5207b7SJohn Levon if (sm) 5381f5207b7SJohn Levon return sm->state; 5391f5207b7SJohn Levon return NULL; 5401f5207b7SJohn Levon } 5411f5207b7SJohn Levon 5421f5207b7SJohn Levon /* FIXME: this is almost exactly the same as set_sm_state_slist() */ 5431f5207b7SJohn Levon void overwrite_sm_state_stree(struct stree **stree, struct sm_state *new) 5441f5207b7SJohn Levon { 5451f5207b7SJohn Levon avl_insert(stree, new); 5461f5207b7SJohn Levon } 5471f5207b7SJohn Levon 5481f5207b7SJohn Levon void overwrite_sm_state_stree_stack(struct stree_stack **stack, 5491f5207b7SJohn Levon struct sm_state *sm) 5501f5207b7SJohn Levon { 5511f5207b7SJohn Levon struct stree *stree; 5521f5207b7SJohn Levon 5531f5207b7SJohn Levon stree = pop_stree(stack); 5541f5207b7SJohn Levon overwrite_sm_state_stree(&stree, sm); 5551f5207b7SJohn Levon push_stree(stack, stree); 5561f5207b7SJohn Levon } 5571f5207b7SJohn Levon 5581f5207b7SJohn Levon struct sm_state *set_state_stree(struct stree **stree, int owner, const char *name, 5591f5207b7SJohn Levon struct symbol *sym, struct smatch_state *state) 5601f5207b7SJohn Levon { 5611f5207b7SJohn Levon struct sm_state *new = alloc_sm_state(owner, name, sym, state); 5621f5207b7SJohn Levon 5631f5207b7SJohn Levon avl_insert(stree, new); 5641f5207b7SJohn Levon return new; 5651f5207b7SJohn Levon } 5661f5207b7SJohn Levon 5671f5207b7SJohn Levon void set_state_stree_perm(struct stree **stree, int owner, const char *name, 5681f5207b7SJohn Levon struct symbol *sym, struct smatch_state *state) 5691f5207b7SJohn Levon { 5701f5207b7SJohn Levon struct sm_state *sm; 5711f5207b7SJohn Levon 5721f5207b7SJohn Levon sm = malloc(sizeof(*sm) + strlen(name) + 1); 5731f5207b7SJohn Levon memset(sm, 0, sizeof(*sm)); 5741f5207b7SJohn Levon sm->owner = owner; 5751f5207b7SJohn Levon sm->name = (char *)(sm + 1); 5761f5207b7SJohn Levon strcpy((char *)sm->name, name); 5771f5207b7SJohn Levon sm->sym = sym; 5781f5207b7SJohn Levon sm->state = state; 5791f5207b7SJohn Levon 5801f5207b7SJohn Levon overwrite_sm_state_stree(stree, sm); 5811f5207b7SJohn Levon } 5821f5207b7SJohn Levon 5831f5207b7SJohn Levon void delete_state_stree(struct stree **stree, int owner, const char *name, 5841f5207b7SJohn Levon struct symbol *sym) 5851f5207b7SJohn Levon { 5861f5207b7SJohn Levon struct tracker tracker = { 5871f5207b7SJohn Levon .owner = owner, 5881f5207b7SJohn Levon .name = (char *)name, 5891f5207b7SJohn Levon .sym = sym, 5901f5207b7SJohn Levon }; 5911f5207b7SJohn Levon 5921f5207b7SJohn Levon avl_remove(stree, (struct sm_state *)&tracker); 5931f5207b7SJohn Levon } 5941f5207b7SJohn Levon 5951f5207b7SJohn Levon void delete_state_stree_stack(struct stree_stack **stack, int owner, const char *name, 5961f5207b7SJohn Levon struct symbol *sym) 5971f5207b7SJohn Levon { 5981f5207b7SJohn Levon struct stree *stree; 5991f5207b7SJohn Levon 6001f5207b7SJohn Levon stree = pop_stree(stack); 6011f5207b7SJohn Levon delete_state_stree(&stree, owner, name, sym); 6021f5207b7SJohn Levon push_stree(stack, stree); 6031f5207b7SJohn Levon } 6041f5207b7SJohn Levon 6051f5207b7SJohn Levon void push_stree(struct stree_stack **stack, struct stree *stree) 6061f5207b7SJohn Levon { 6071f5207b7SJohn Levon add_ptr_list(stack, stree); 6081f5207b7SJohn Levon } 6091f5207b7SJohn Levon 6101f5207b7SJohn Levon struct stree *pop_stree(struct stree_stack **stack) 6111f5207b7SJohn Levon { 6121f5207b7SJohn Levon struct stree *stree; 6131f5207b7SJohn Levon 6141f5207b7SJohn Levon stree = last_ptr_list((struct ptr_list *)*stack); 6151f5207b7SJohn Levon delete_ptr_list_last((struct ptr_list **)stack); 6161f5207b7SJohn Levon return stree; 6171f5207b7SJohn Levon } 6181f5207b7SJohn Levon 6191f5207b7SJohn Levon struct stree *top_stree(struct stree_stack *stack) 6201f5207b7SJohn Levon { 6211f5207b7SJohn Levon return last_ptr_list((struct ptr_list *)stack); 6221f5207b7SJohn Levon } 6231f5207b7SJohn Levon 6241f5207b7SJohn Levon void free_slist(struct state_list **slist) 6251f5207b7SJohn Levon { 6261f5207b7SJohn Levon __free_ptr_list((struct ptr_list **)slist); 6271f5207b7SJohn Levon } 6281f5207b7SJohn Levon 6291f5207b7SJohn Levon void free_stree_stack(struct stree_stack **stack) 6301f5207b7SJohn Levon { 6311f5207b7SJohn Levon __free_ptr_list((struct ptr_list **)stack); 6321f5207b7SJohn Levon } 6331f5207b7SJohn Levon 6341f5207b7SJohn Levon void free_stack_and_strees(struct stree_stack **stree_stack) 6351f5207b7SJohn Levon { 6361f5207b7SJohn Levon struct stree *stree; 6371f5207b7SJohn Levon 6381f5207b7SJohn Levon FOR_EACH_PTR(*stree_stack, stree) { 6391f5207b7SJohn Levon free_stree(&stree); 6401f5207b7SJohn Levon } END_FOR_EACH_PTR(stree); 6411f5207b7SJohn Levon free_stree_stack(stree_stack); 6421f5207b7SJohn Levon } 6431f5207b7SJohn Levon 6441f5207b7SJohn Levon struct sm_state *set_state_stree_stack(struct stree_stack **stack, int owner, const char *name, 6451f5207b7SJohn Levon struct symbol *sym, struct smatch_state *state) 6461f5207b7SJohn Levon { 6471f5207b7SJohn Levon struct stree *stree; 6481f5207b7SJohn Levon struct sm_state *sm; 6491f5207b7SJohn Levon 6501f5207b7SJohn Levon stree = pop_stree(stack); 6511f5207b7SJohn Levon sm = set_state_stree(&stree, owner, name, sym, state); 6521f5207b7SJohn Levon push_stree(stack, stree); 6531f5207b7SJohn Levon 6541f5207b7SJohn Levon return sm; 6551f5207b7SJohn Levon } 6561f5207b7SJohn Levon 6571f5207b7SJohn Levon /* 6581f5207b7SJohn Levon * get_sm_state_stack() gets the state for the top slist on the stack. 6591f5207b7SJohn Levon */ 6601f5207b7SJohn Levon struct sm_state *get_sm_state_stree_stack(struct stree_stack *stack, 6611f5207b7SJohn Levon int owner, const char *name, 6621f5207b7SJohn Levon struct symbol *sym) 6631f5207b7SJohn Levon { 6641f5207b7SJohn Levon struct stree *stree; 6651f5207b7SJohn Levon struct sm_state *ret; 6661f5207b7SJohn Levon 6671f5207b7SJohn Levon stree = pop_stree(&stack); 6681f5207b7SJohn Levon ret = get_sm_state_stree(stree, owner, name, sym); 6691f5207b7SJohn Levon push_stree(&stack, stree); 6701f5207b7SJohn Levon return ret; 6711f5207b7SJohn Levon } 6721f5207b7SJohn Levon 6731f5207b7SJohn Levon struct smatch_state *get_state_stree_stack(struct stree_stack *stack, 6741f5207b7SJohn Levon int owner, const char *name, 6751f5207b7SJohn Levon struct symbol *sym) 6761f5207b7SJohn Levon { 6771f5207b7SJohn Levon struct sm_state *sm; 6781f5207b7SJohn Levon 6791f5207b7SJohn Levon sm = get_sm_state_stree_stack(stack, owner, name, sym); 6801f5207b7SJohn Levon if (sm) 6811f5207b7SJohn Levon return sm->state; 6821f5207b7SJohn Levon return NULL; 6831f5207b7SJohn Levon } 6841f5207b7SJohn Levon 6851f5207b7SJohn Levon static void match_states_stree(struct stree **one, struct stree **two) 6861f5207b7SJohn Levon { 6871f5207b7SJohn Levon struct smatch_state *tmp_state; 6881f5207b7SJohn Levon struct sm_state *sm; 6891f5207b7SJohn Levon struct state_list *add_to_one = NULL; 6901f5207b7SJohn Levon struct state_list *add_to_two = NULL; 6911f5207b7SJohn Levon AvlIter one_iter; 6921f5207b7SJohn Levon AvlIter two_iter; 6931f5207b7SJohn Levon 6941f5207b7SJohn Levon avl_iter_begin(&one_iter, *one, FORWARD); 6951f5207b7SJohn Levon avl_iter_begin(&two_iter, *two, FORWARD); 6961f5207b7SJohn Levon 6971f5207b7SJohn Levon for (;;) { 6981f5207b7SJohn Levon if (!one_iter.sm && !two_iter.sm) 6991f5207b7SJohn Levon break; 7001f5207b7SJohn Levon if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) { 7011f5207b7SJohn Levon __set_fake_cur_stree_fast(*two); 7021f5207b7SJohn Levon tmp_state = __client_unmatched_state_function(one_iter.sm); 7031f5207b7SJohn Levon __pop_fake_cur_stree_fast(); 7041f5207b7SJohn Levon sm = alloc_state_no_name(one_iter.sm->owner, one_iter.sm->name, 7051f5207b7SJohn Levon one_iter.sm->sym, tmp_state); 7061f5207b7SJohn Levon add_ptr_list(&add_to_two, sm); 7071f5207b7SJohn Levon avl_iter_next(&one_iter); 7081f5207b7SJohn Levon } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) { 7091f5207b7SJohn Levon avl_iter_next(&one_iter); 7101f5207b7SJohn Levon avl_iter_next(&two_iter); 7111f5207b7SJohn Levon } else { 7121f5207b7SJohn Levon __set_fake_cur_stree_fast(*one); 7131f5207b7SJohn Levon tmp_state = __client_unmatched_state_function(two_iter.sm); 7141f5207b7SJohn Levon __pop_fake_cur_stree_fast(); 7151f5207b7SJohn Levon sm = alloc_state_no_name(two_iter.sm->owner, two_iter.sm->name, 7161f5207b7SJohn Levon two_iter.sm->sym, tmp_state); 7171f5207b7SJohn Levon add_ptr_list(&add_to_one, sm); 7181f5207b7SJohn Levon avl_iter_next(&two_iter); 7191f5207b7SJohn Levon } 7201f5207b7SJohn Levon } 7211f5207b7SJohn Levon 7221f5207b7SJohn Levon FOR_EACH_PTR(add_to_one, sm) { 7231f5207b7SJohn Levon avl_insert(one, sm); 7241f5207b7SJohn Levon } END_FOR_EACH_PTR(sm); 7251f5207b7SJohn Levon 7261f5207b7SJohn Levon FOR_EACH_PTR(add_to_two, sm) { 7271f5207b7SJohn Levon avl_insert(two, sm); 7281f5207b7SJohn Levon } END_FOR_EACH_PTR(sm); 7291f5207b7SJohn Levon 7301f5207b7SJohn Levon free_slist(&add_to_one); 7311f5207b7SJohn Levon free_slist(&add_to_two); 7321f5207b7SJohn Levon } 7331f5207b7SJohn Levon 7341f5207b7SJohn Levon static void call_pre_merge_hooks(struct stree **one, struct stree **two) 7351f5207b7SJohn Levon { 7361f5207b7SJohn Levon struct sm_state *sm, *other; 7371f5207b7SJohn Levon 7381f5207b7SJohn Levon save_all_states(); 7391f5207b7SJohn Levon 7401f5207b7SJohn Levon __swap_cur_stree(*one); 7411f5207b7SJohn Levon FOR_EACH_SM(*two, sm) { 7421f5207b7SJohn Levon other = get_sm_state(sm->owner, sm->name, sm->sym); 7431f5207b7SJohn Levon if (other == sm) 7441f5207b7SJohn Levon continue; 7451f5207b7SJohn Levon call_pre_merge_hook(sm); 7461f5207b7SJohn Levon } END_FOR_EACH_SM(sm); 7471f5207b7SJohn Levon *one = clone_stree(__get_cur_stree()); 7481f5207b7SJohn Levon 7491f5207b7SJohn Levon __swap_cur_stree(*two); 7501f5207b7SJohn Levon FOR_EACH_SM(*one, sm) { 7511f5207b7SJohn Levon other = get_sm_state(sm->owner, sm->name, sm->sym); 7521f5207b7SJohn Levon if (other == sm) 7531f5207b7SJohn Levon continue; 7541f5207b7SJohn Levon call_pre_merge_hook(sm); 7551f5207b7SJohn Levon } END_FOR_EACH_SM(sm); 7561f5207b7SJohn Levon *two = clone_stree(__get_cur_stree()); 7571f5207b7SJohn Levon 7581f5207b7SJohn Levon restore_all_states(); 7591f5207b7SJohn Levon } 7601f5207b7SJohn Levon 7611f5207b7SJohn Levon static void clone_pool_havers_stree(struct stree **stree) 7621f5207b7SJohn Levon { 7631f5207b7SJohn Levon struct sm_state *sm, *tmp; 7641f5207b7SJohn Levon struct state_list *slist = NULL; 7651f5207b7SJohn Levon 7661f5207b7SJohn Levon FOR_EACH_SM(*stree, sm) { 7671f5207b7SJohn Levon if (sm->pool) { 7681f5207b7SJohn Levon tmp = clone_sm(sm); 7691f5207b7SJohn Levon add_ptr_list(&slist, tmp); 7701f5207b7SJohn Levon } 7711f5207b7SJohn Levon } END_FOR_EACH_SM(sm); 7721f5207b7SJohn Levon 7731f5207b7SJohn Levon FOR_EACH_PTR(slist, sm) { 7741f5207b7SJohn Levon avl_insert(stree, sm); 7751f5207b7SJohn Levon } END_FOR_EACH_PTR(sm); 7761f5207b7SJohn Levon 7771f5207b7SJohn Levon free_slist(&slist); 7781f5207b7SJohn Levon } 7791f5207b7SJohn Levon 7801f5207b7SJohn Levon int __stree_id; 7811f5207b7SJohn Levon 7821f5207b7SJohn Levon /* 7831f5207b7SJohn Levon * merge_slist() is called whenever paths merge, such as after 7841f5207b7SJohn Levon * an if statement. It takes the two slists and creates one. 7851f5207b7SJohn Levon */ 7861f5207b7SJohn Levon static void __merge_stree(struct stree **to, struct stree *stree, int add_pool) 7871f5207b7SJohn Levon { 7881f5207b7SJohn Levon struct stree *results = NULL; 7891f5207b7SJohn Levon struct stree *implied_one = NULL; 7901f5207b7SJohn Levon struct stree *implied_two = NULL; 7911f5207b7SJohn Levon AvlIter one_iter; 7921f5207b7SJohn Levon AvlIter two_iter; 793*efe51d0cSJohn Levon struct sm_state *one, *two, *res; 7941f5207b7SJohn Levon 7951f5207b7SJohn Levon if (out_of_memory()) 7961f5207b7SJohn Levon return; 7971f5207b7SJohn Levon 7981f5207b7SJohn Levon /* merging a null and nonnull path gives you only the nonnull path */ 7991f5207b7SJohn Levon if (!stree) 8001f5207b7SJohn Levon return; 8011f5207b7SJohn Levon if (*to == stree) 8021f5207b7SJohn Levon return; 8031f5207b7SJohn Levon 8041f5207b7SJohn Levon if (!*to) { 8051f5207b7SJohn Levon *to = clone_stree(stree); 8061f5207b7SJohn Levon return; 8071f5207b7SJohn Levon } 8081f5207b7SJohn Levon 8091f5207b7SJohn Levon implied_one = clone_stree(*to); 8101f5207b7SJohn Levon implied_two = clone_stree(stree); 8111f5207b7SJohn Levon 8121f5207b7SJohn Levon match_states_stree(&implied_one, &implied_two); 8131f5207b7SJohn Levon call_pre_merge_hooks(&implied_one, &implied_two); 8141f5207b7SJohn Levon 8151f5207b7SJohn Levon if (add_pool) { 8161f5207b7SJohn Levon clone_pool_havers_stree(&implied_one); 8171f5207b7SJohn Levon clone_pool_havers_stree(&implied_two); 8181f5207b7SJohn Levon 8191f5207b7SJohn Levon set_stree_id(&implied_one, ++__stree_id); 8201f5207b7SJohn Levon set_stree_id(&implied_two, ++__stree_id); 8211f5207b7SJohn Levon if (implied_one->base_stree) 8221f5207b7SJohn Levon set_stree_id(&implied_one->base_stree, ++__stree_id); 8231f5207b7SJohn Levon if (implied_two->base_stree) 8241f5207b7SJohn Levon set_stree_id(&implied_two->base_stree, ++__stree_id); 8251f5207b7SJohn Levon } 8261f5207b7SJohn Levon 8271f5207b7SJohn Levon push_stree(&all_pools, implied_one); 8281f5207b7SJohn Levon push_stree(&all_pools, implied_two); 8291f5207b7SJohn Levon 8301f5207b7SJohn Levon avl_iter_begin(&one_iter, implied_one, FORWARD); 8311f5207b7SJohn Levon avl_iter_begin(&two_iter, implied_two, FORWARD); 8321f5207b7SJohn Levon 8331f5207b7SJohn Levon for (;;) { 8341f5207b7SJohn Levon if (!one_iter.sm || !two_iter.sm) 8351f5207b7SJohn Levon break; 836*efe51d0cSJohn Levon 837*efe51d0cSJohn Levon one = one_iter.sm; 838*efe51d0cSJohn Levon two = two_iter.sm; 839*efe51d0cSJohn Levon 840*efe51d0cSJohn Levon if (one == two) { 841*efe51d0cSJohn Levon avl_insert(&results, one); 842*efe51d0cSJohn Levon goto next; 843*efe51d0cSJohn Levon } 844*efe51d0cSJohn Levon 845*efe51d0cSJohn Levon if (add_pool) { 846*efe51d0cSJohn Levon one->pool = implied_one; 847*efe51d0cSJohn Levon if (implied_one->base_stree) 848*efe51d0cSJohn Levon one->pool = implied_one->base_stree; 849*efe51d0cSJohn Levon two->pool = implied_two; 850*efe51d0cSJohn Levon if (implied_two->base_stree) 851*efe51d0cSJohn Levon two->pool = implied_two->base_stree; 8521f5207b7SJohn Levon } 853*efe51d0cSJohn Levon res = merge_sm_states(one, two); 854*efe51d0cSJohn Levon add_possible_sm(res, one); 855*efe51d0cSJohn Levon add_possible_sm(res, two); 856*efe51d0cSJohn Levon avl_insert(&results, res); 857*efe51d0cSJohn Levon next: 858*efe51d0cSJohn Levon avl_iter_next(&one_iter); 859*efe51d0cSJohn Levon avl_iter_next(&two_iter); 8601f5207b7SJohn Levon } 8611f5207b7SJohn Levon 8621f5207b7SJohn Levon free_stree(to); 8631f5207b7SJohn Levon *to = results; 8641f5207b7SJohn Levon } 8651f5207b7SJohn Levon 8661f5207b7SJohn Levon void merge_stree(struct stree **to, struct stree *stree) 8671f5207b7SJohn Levon { 8681f5207b7SJohn Levon __merge_stree(to, stree, 1); 8691f5207b7SJohn Levon } 8701f5207b7SJohn Levon 8711f5207b7SJohn Levon void merge_stree_no_pools(struct stree **to, struct stree *stree) 8721f5207b7SJohn Levon { 8731f5207b7SJohn Levon __merge_stree(to, stree, 0); 8741f5207b7SJohn Levon } 8751f5207b7SJohn Levon 8761f5207b7SJohn Levon /* 8771f5207b7SJohn Levon * This is unfortunately a bit subtle... The problem is that if a 8781f5207b7SJohn Levon * state is set on one fake stree but not the other then we should 8791f5207b7SJohn Levon * look up the the original state and use that as the unset state. 8801f5207b7SJohn Levon * Fortunately, after you pop your fake stree then the cur_slist should 8811f5207b7SJohn Levon * reflect the original state. 8821f5207b7SJohn Levon */ 8831f5207b7SJohn Levon void merge_fake_stree(struct stree **to, struct stree *stree) 8841f5207b7SJohn Levon { 8851f5207b7SJohn Levon struct stree *one = *to; 8861f5207b7SJohn Levon struct stree *two = stree; 8871f5207b7SJohn Levon struct sm_state *sm; 8881f5207b7SJohn Levon struct state_list *add_to_one = NULL; 8891f5207b7SJohn Levon struct state_list *add_to_two = NULL; 8901f5207b7SJohn Levon AvlIter one_iter; 8911f5207b7SJohn Levon AvlIter two_iter; 8921f5207b7SJohn Levon 8931f5207b7SJohn Levon if (!stree) 8941f5207b7SJohn Levon return; 8951f5207b7SJohn Levon if (*to == stree) 8961f5207b7SJohn Levon return; 8971f5207b7SJohn Levon if (!*to) { 8981f5207b7SJohn Levon *to = clone_stree(stree); 8991f5207b7SJohn Levon return; 9001f5207b7SJohn Levon } 9011f5207b7SJohn Levon 9021f5207b7SJohn Levon avl_iter_begin(&one_iter, one, FORWARD); 9031f5207b7SJohn Levon avl_iter_begin(&two_iter, two, FORWARD); 9041f5207b7SJohn Levon 9051f5207b7SJohn Levon for (;;) { 9061f5207b7SJohn Levon if (!one_iter.sm && !two_iter.sm) 9071f5207b7SJohn Levon break; 9081f5207b7SJohn Levon if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) { 9091f5207b7SJohn Levon sm = get_sm_state(one_iter.sm->owner, one_iter.sm->name, 9101f5207b7SJohn Levon one_iter.sm->sym); 9111f5207b7SJohn Levon if (sm) 9121f5207b7SJohn Levon add_ptr_list(&add_to_two, sm); 9131f5207b7SJohn Levon avl_iter_next(&one_iter); 9141f5207b7SJohn Levon } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) { 9151f5207b7SJohn Levon avl_iter_next(&one_iter); 9161f5207b7SJohn Levon avl_iter_next(&two_iter); 9171f5207b7SJohn Levon } else { 9181f5207b7SJohn Levon sm = get_sm_state(two_iter.sm->owner, two_iter.sm->name, 9191f5207b7SJohn Levon two_iter.sm->sym); 9201f5207b7SJohn Levon if (sm) 9211f5207b7SJohn Levon add_ptr_list(&add_to_one, sm); 9221f5207b7SJohn Levon avl_iter_next(&two_iter); 9231f5207b7SJohn Levon } 9241f5207b7SJohn Levon } 9251f5207b7SJohn Levon 9261f5207b7SJohn Levon FOR_EACH_PTR(add_to_one, sm) { 9271f5207b7SJohn Levon avl_insert(&one, sm); 9281f5207b7SJohn Levon } END_FOR_EACH_PTR(sm); 9291f5207b7SJohn Levon 9301f5207b7SJohn Levon FOR_EACH_PTR(add_to_two, sm) { 9311f5207b7SJohn Levon avl_insert(&two, sm); 9321f5207b7SJohn Levon } END_FOR_EACH_PTR(sm); 9331f5207b7SJohn Levon 9341f5207b7SJohn Levon one->base_stree = clone_stree(__get_cur_stree()); 9351f5207b7SJohn Levon FOR_EACH_SM(one, sm) { 9361f5207b7SJohn Levon avl_insert(&one->base_stree, sm); 9371f5207b7SJohn Levon } END_FOR_EACH_SM(sm); 9381f5207b7SJohn Levon 9391f5207b7SJohn Levon two->base_stree = clone_stree(__get_cur_stree()); 9401f5207b7SJohn Levon FOR_EACH_SM(two, sm) { 9411f5207b7SJohn Levon avl_insert(&two->base_stree, sm); 9421f5207b7SJohn Levon } END_FOR_EACH_SM(sm); 9431f5207b7SJohn Levon 9441f5207b7SJohn Levon free_slist(&add_to_one); 9451f5207b7SJohn Levon free_slist(&add_to_two); 9461f5207b7SJohn Levon 9471f5207b7SJohn Levon __merge_stree(&one, two, 1); 9481f5207b7SJohn Levon 9491f5207b7SJohn Levon *to = one; 9501f5207b7SJohn Levon } 9511f5207b7SJohn Levon 9521f5207b7SJohn Levon /* 9531f5207b7SJohn Levon * filter_slist() removes any sm states "slist" holds in common with "filter" 9541f5207b7SJohn Levon */ 9551f5207b7SJohn Levon void filter_stree(struct stree **stree, struct stree *filter) 9561f5207b7SJohn Levon { 9571f5207b7SJohn Levon struct stree *results = NULL; 9581f5207b7SJohn Levon AvlIter one_iter; 9591f5207b7SJohn Levon AvlIter two_iter; 9601f5207b7SJohn Levon 9611f5207b7SJohn Levon avl_iter_begin(&one_iter, *stree, FORWARD); 9621f5207b7SJohn Levon avl_iter_begin(&two_iter, filter, FORWARD); 9631f5207b7SJohn Levon 9641f5207b7SJohn Levon /* FIXME: This should probably be re-written with trees in mind */ 9651f5207b7SJohn Levon 9661f5207b7SJohn Levon for (;;) { 9671f5207b7SJohn Levon if (!one_iter.sm && !two_iter.sm) 9681f5207b7SJohn Levon break; 9691f5207b7SJohn Levon if (cmp_tracker(one_iter.sm, two_iter.sm) < 0) { 9701f5207b7SJohn Levon avl_insert(&results, one_iter.sm); 9711f5207b7SJohn Levon avl_iter_next(&one_iter); 9721f5207b7SJohn Levon } else if (cmp_tracker(one_iter.sm, two_iter.sm) == 0) { 9731f5207b7SJohn Levon if (one_iter.sm != two_iter.sm) 9741f5207b7SJohn Levon avl_insert(&results, one_iter.sm); 9751f5207b7SJohn Levon avl_iter_next(&one_iter); 9761f5207b7SJohn Levon avl_iter_next(&two_iter); 9771f5207b7SJohn Levon } else { 9781f5207b7SJohn Levon avl_iter_next(&two_iter); 9791f5207b7SJohn Levon } 9801f5207b7SJohn Levon } 9811f5207b7SJohn Levon 9821f5207b7SJohn Levon free_stree(stree); 9831f5207b7SJohn Levon *stree = results; 9841f5207b7SJohn Levon } 9851f5207b7SJohn Levon 9861f5207b7SJohn Levon 9871f5207b7SJohn Levon /* 9881f5207b7SJohn Levon * and_slist_stack() pops the top two slists, overwriting the one with 9891f5207b7SJohn Levon * the other and pushing it back on the stack. 9901f5207b7SJohn Levon */ 9911f5207b7SJohn Levon void and_stree_stack(struct stree_stack **stack) 9921f5207b7SJohn Levon { 9931f5207b7SJohn Levon struct sm_state *tmp; 9941f5207b7SJohn Levon struct stree *right_stree = pop_stree(stack); 9951f5207b7SJohn Levon 9961f5207b7SJohn Levon FOR_EACH_SM(right_stree, tmp) { 9971f5207b7SJohn Levon overwrite_sm_state_stree_stack(stack, tmp); 9981f5207b7SJohn Levon } END_FOR_EACH_SM(tmp); 9991f5207b7SJohn Levon free_stree(&right_stree); 10001f5207b7SJohn Levon } 10011f5207b7SJohn Levon 10021f5207b7SJohn Levon /* 10031f5207b7SJohn Levon * or_slist_stack() is for if we have: if (foo || bar) { foo->baz; 10041f5207b7SJohn Levon * It pops the two slists from the top of the stack and merges them 10051f5207b7SJohn Levon * together in a way that preserves the things they have in common 10061f5207b7SJohn Levon * but creates a merged state for most of the rest. 10071f5207b7SJohn Levon * You could have code that had: if (foo || foo) { foo->baz; 10081f5207b7SJohn Levon * It's this function which ensures smatch does the right thing. 10091f5207b7SJohn Levon */ 10101f5207b7SJohn Levon void or_stree_stack(struct stree_stack **pre_conds, 10111f5207b7SJohn Levon struct stree *cur_stree, 10121f5207b7SJohn Levon struct stree_stack **stack) 10131f5207b7SJohn Levon { 10141f5207b7SJohn Levon struct stree *new; 10151f5207b7SJohn Levon struct stree *old; 10161f5207b7SJohn Levon struct stree *pre_stree; 10171f5207b7SJohn Levon struct stree *res; 10181f5207b7SJohn Levon struct stree *tmp_stree; 10191f5207b7SJohn Levon 10201f5207b7SJohn Levon new = pop_stree(stack); 10211f5207b7SJohn Levon old = pop_stree(stack); 10221f5207b7SJohn Levon 10231f5207b7SJohn Levon pre_stree = pop_stree(pre_conds); 10241f5207b7SJohn Levon push_stree(pre_conds, clone_stree(pre_stree)); 10251f5207b7SJohn Levon 10261f5207b7SJohn Levon res = clone_stree(pre_stree); 10271f5207b7SJohn Levon overwrite_stree(old, &res); 10281f5207b7SJohn Levon 10291f5207b7SJohn Levon tmp_stree = clone_stree(cur_stree); 10301f5207b7SJohn Levon overwrite_stree(new, &tmp_stree); 10311f5207b7SJohn Levon 10321f5207b7SJohn Levon merge_stree(&res, tmp_stree); 10331f5207b7SJohn Levon filter_stree(&res, pre_stree); 10341f5207b7SJohn Levon 10351f5207b7SJohn Levon push_stree(stack, res); 10361f5207b7SJohn Levon free_stree(&tmp_stree); 10371f5207b7SJohn Levon free_stree(&pre_stree); 10381f5207b7SJohn Levon free_stree(&new); 10391f5207b7SJohn Levon free_stree(&old); 10401f5207b7SJohn Levon } 10411f5207b7SJohn Levon 10421f5207b7SJohn Levon /* 10431f5207b7SJohn Levon * get_named_stree() is only used for gotos. 10441f5207b7SJohn Levon */ 10451f5207b7SJohn Levon struct stree **get_named_stree(struct named_stree_stack *stack, 10461f5207b7SJohn Levon const char *name, 10471f5207b7SJohn Levon struct symbol *sym) 10481f5207b7SJohn Levon { 10491f5207b7SJohn Levon struct named_stree *tmp; 10501f5207b7SJohn Levon 10511f5207b7SJohn Levon FOR_EACH_PTR(stack, tmp) { 10521f5207b7SJohn Levon if (tmp->sym == sym && 10531f5207b7SJohn Levon strcmp(tmp->name, name) == 0) 10541f5207b7SJohn Levon return &tmp->stree; 10551f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp); 10561f5207b7SJohn Levon return NULL; 10571f5207b7SJohn Levon } 10581f5207b7SJohn Levon 10591f5207b7SJohn Levon /* FIXME: These parameters are in a different order from expected */ 10601f5207b7SJohn Levon void overwrite_stree(struct stree *from, struct stree **to) 10611f5207b7SJohn Levon { 10621f5207b7SJohn Levon struct sm_state *tmp; 10631f5207b7SJohn Levon 10641f5207b7SJohn Levon FOR_EACH_SM(from, tmp) { 10651f5207b7SJohn Levon overwrite_sm_state_stree(to, tmp); 10661f5207b7SJohn Levon } END_FOR_EACH_SM(tmp); 10671f5207b7SJohn Levon } 10681f5207b7SJohn Levon 1069