11f5207b7SJohn Levon /*
21f5207b7SJohn Levon * Copyright (C) 2014 Oracle.
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 /*
191f5207b7SJohn Levon * Keep a record of all the things we have tested for so that we know when we
201f5207b7SJohn Levon * test for it again. For example, if we have code like this:
211f5207b7SJohn Levon *
221f5207b7SJohn Levon * if (foo & FLAG)
231f5207b7SJohn Levon * lock();
241f5207b7SJohn Levon *
251f5207b7SJohn Levon * ...
261f5207b7SJohn Levon *
271f5207b7SJohn Levon * if (foo & FLAG)
281f5207b7SJohn Levon * unlock();
291f5207b7SJohn Levon *
301f5207b7SJohn Levon * That's the end goal at least. But actually implementing the flow of that
311f5207b7SJohn Levon * requires quite a bit of work because if "foo" changes the condition needs to
321f5207b7SJohn Levon * be retested and smatch_implications.c needs to be updated.
331f5207b7SJohn Levon *
341f5207b7SJohn Levon * For now, I just record the conditions and use it to see if we test for NULL
351f5207b7SJohn Levon * twice.
361f5207b7SJohn Levon *
371f5207b7SJohn Levon */
381f5207b7SJohn Levon
391f5207b7SJohn Levon #include "smatch.h"
401f5207b7SJohn Levon #include "smatch_slist.h"
411f5207b7SJohn Levon
421f5207b7SJohn Levon static int my_id;
431f5207b7SJohn Levon static int link_id;
441f5207b7SJohn Levon
alloc_link_state(struct expression_list * expr_list)451f5207b7SJohn Levon static struct smatch_state *alloc_link_state(struct expression_list *expr_list)
461f5207b7SJohn Levon {
471f5207b7SJohn Levon struct expression *tmp;
481f5207b7SJohn Levon struct smatch_state *state;
491f5207b7SJohn Levon static char buf[256];
501f5207b7SJohn Levon char *name;
511f5207b7SJohn Levon int i;
521f5207b7SJohn Levon
531f5207b7SJohn Levon state = __alloc_smatch_state(0);
541f5207b7SJohn Levon
551f5207b7SJohn Levon i = 0;
561f5207b7SJohn Levon FOR_EACH_PTR(expr_list, tmp) {
571f5207b7SJohn Levon name = expr_to_str(tmp);
581f5207b7SJohn Levon if (!i++) {
591f5207b7SJohn Levon snprintf(buf, sizeof(buf), "%s", name);
601f5207b7SJohn Levon } else {
611f5207b7SJohn Levon append(buf, ", ", sizeof(buf));
621f5207b7SJohn Levon append(buf, name, sizeof(buf));
631f5207b7SJohn Levon }
641f5207b7SJohn Levon free_string(name);
651f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
661f5207b7SJohn Levon
671f5207b7SJohn Levon state->name = alloc_sname(buf);
681f5207b7SJohn Levon state->data = expr_list;
691f5207b7SJohn Levon return state;
701f5207b7SJohn Levon }
711f5207b7SJohn Levon
clone_expression_list(struct expression_list * list)721f5207b7SJohn Levon static struct expression_list *clone_expression_list(struct expression_list *list)
731f5207b7SJohn Levon {
741f5207b7SJohn Levon struct expression_list *ret = NULL;
751f5207b7SJohn Levon struct expression *expr;
761f5207b7SJohn Levon
771f5207b7SJohn Levon FOR_EACH_PTR(list, expr) {
781f5207b7SJohn Levon add_ptr_list(&ret, expr);
791f5207b7SJohn Levon } END_FOR_EACH_PTR(expr);
801f5207b7SJohn Levon
811f5207b7SJohn Levon return ret;
821f5207b7SJohn Levon }
831f5207b7SJohn Levon
insert_expression(struct expression_list ** list,struct expression * expr)841f5207b7SJohn Levon static void insert_expression(struct expression_list **list, struct expression *expr)
851f5207b7SJohn Levon {
861f5207b7SJohn Levon struct expression *tmp;
871f5207b7SJohn Levon
881f5207b7SJohn Levon FOR_EACH_PTR(*list, tmp) {
891f5207b7SJohn Levon if (tmp == expr)
901f5207b7SJohn Levon return;
911f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
921f5207b7SJohn Levon
931f5207b7SJohn Levon add_ptr_list(list, expr);
941f5207b7SJohn Levon }
951f5207b7SJohn Levon
merge_links(struct smatch_state * s1,struct smatch_state * s2)961f5207b7SJohn Levon static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
971f5207b7SJohn Levon {
981f5207b7SJohn Levon struct expression_list *list, *expr_list;
991f5207b7SJohn Levon struct expression *expr;
1001f5207b7SJohn Levon
1011f5207b7SJohn Levon expr_list = clone_expression_list(s1->data);
1021f5207b7SJohn Levon
1031f5207b7SJohn Levon list = s2->data;
1041f5207b7SJohn Levon FOR_EACH_PTR(list, expr) {
1051f5207b7SJohn Levon insert_expression(&expr_list, expr);
1061f5207b7SJohn Levon } END_FOR_EACH_PTR(expr);
1071f5207b7SJohn Levon
1081f5207b7SJohn Levon return alloc_link_state(expr_list);
1091f5207b7SJohn Levon }
1101f5207b7SJohn Levon
save_link_var_sym(const char * var,struct symbol * sym,struct expression * condition)1111f5207b7SJohn Levon static void save_link_var_sym(const char *var, struct symbol *sym, struct expression *condition)
1121f5207b7SJohn Levon {
1131f5207b7SJohn Levon struct smatch_state *old_state, *new_state;
1141f5207b7SJohn Levon struct expression_list *expr_list;
1151f5207b7SJohn Levon
1161f5207b7SJohn Levon old_state = get_state(link_id, var, sym);
1171f5207b7SJohn Levon expr_list = clone_expression_list(old_state ? old_state->data : NULL);
1181f5207b7SJohn Levon
1191f5207b7SJohn Levon insert_expression(&expr_list, condition);
1201f5207b7SJohn Levon
1211f5207b7SJohn Levon new_state = alloc_link_state(expr_list);
1221f5207b7SJohn Levon set_state(link_id, var, sym, new_state);
1231f5207b7SJohn Levon }
1241f5207b7SJohn Levon
match_link_modify(struct sm_state * sm,struct expression * mod_expr)1251f5207b7SJohn Levon static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
1261f5207b7SJohn Levon {
1271f5207b7SJohn Levon struct expression_list *expr_list;
1281f5207b7SJohn Levon struct expression *tmp;
1291f5207b7SJohn Levon char *name;
1301f5207b7SJohn Levon
1311f5207b7SJohn Levon expr_list = sm->state->data;
1321f5207b7SJohn Levon
1331f5207b7SJohn Levon FOR_EACH_PTR(expr_list, tmp) {
1341f5207b7SJohn Levon name = expr_to_str(tmp);
1351f5207b7SJohn Levon set_state(my_id, name, NULL, &undefined);
1361f5207b7SJohn Levon free_string(name);
1371f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
1381f5207b7SJohn Levon set_state(link_id, sm->name, sm->sym, &undefined);
1391f5207b7SJohn Levon }
1401f5207b7SJohn Levon
alloc_state(struct expression * expr,int is_true)1411f5207b7SJohn Levon static struct smatch_state *alloc_state(struct expression *expr, int is_true)
1421f5207b7SJohn Levon {
1431f5207b7SJohn Levon struct smatch_state *state;
1441f5207b7SJohn Levon
1451f5207b7SJohn Levon state = __alloc_smatch_state(0);
1461f5207b7SJohn Levon if (is_true)
1471f5207b7SJohn Levon state->name = alloc_sname("true");
1481f5207b7SJohn Levon else
1491f5207b7SJohn Levon state->name = alloc_sname("false");
1501f5207b7SJohn Levon state->data = expr;
1511f5207b7SJohn Levon return state;
1521f5207b7SJohn Levon }
1531f5207b7SJohn Levon
store_all_links(struct expression * expr,struct expression * condition)1541f5207b7SJohn Levon static void store_all_links(struct expression *expr, struct expression *condition)
1551f5207b7SJohn Levon {
1561f5207b7SJohn Levon char *var;
1571f5207b7SJohn Levon struct symbol *sym;
1581f5207b7SJohn Levon
1591f5207b7SJohn Levon expr = strip_expr(expr);
1601f5207b7SJohn Levon
1611f5207b7SJohn Levon if (is_array(expr)) {
1621f5207b7SJohn Levon var = expr_to_known_chunk_sym(expr, &sym);
1631f5207b7SJohn Levon if (var)
1641f5207b7SJohn Levon save_link_var_sym(var, sym, condition);
1651f5207b7SJohn Levon }
1661f5207b7SJohn Levon
1671f5207b7SJohn Levon switch (expr->type) {
1681f5207b7SJohn Levon case EXPR_COMPARE:
1691f5207b7SJohn Levon case EXPR_BINOP:
1701f5207b7SJohn Levon store_all_links(expr->left, condition);
1711f5207b7SJohn Levon store_all_links(expr->right, condition);
1721f5207b7SJohn Levon return;
1731f5207b7SJohn Levon case EXPR_VALUE:
1741f5207b7SJohn Levon return;
1751f5207b7SJohn Levon }
1761f5207b7SJohn Levon
1771f5207b7SJohn Levon var = expr_to_var_sym(expr, &sym);
1781f5207b7SJohn Levon if (!var || !sym)
1791f5207b7SJohn Levon goto free;
1801f5207b7SJohn Levon save_link_var_sym(var, sym, condition);
1811f5207b7SJohn Levon free:
1821f5207b7SJohn Levon free_string(var);
1831f5207b7SJohn Levon }
1841f5207b7SJohn Levon
condition_too_complicated(struct expression * expr)1851f5207b7SJohn Levon static int condition_too_complicated(struct expression *expr)
1861f5207b7SJohn Levon {
1871f5207b7SJohn Levon if (get_complication_score(expr) > 2)
1881f5207b7SJohn Levon return 1;
1891f5207b7SJohn Levon return 0;
1901f5207b7SJohn Levon }
1911f5207b7SJohn Levon
__stored_condition(struct expression * expr)1921f5207b7SJohn Levon void __stored_condition(struct expression *expr)
1931f5207b7SJohn Levon {
1941f5207b7SJohn Levon struct smatch_state *true_state, *false_state;
1951f5207b7SJohn Levon char *name;
1961f5207b7SJohn Levon sval_t val;
1971f5207b7SJohn Levon
1981f5207b7SJohn Levon if (get_value(expr, &val))
1991f5207b7SJohn Levon return;
2001f5207b7SJohn Levon
2011f5207b7SJohn Levon if (condition_too_complicated(expr))
2021f5207b7SJohn Levon return;
2031f5207b7SJohn Levon
2041f5207b7SJohn Levon name = expr_to_str(expr);
2051f5207b7SJohn Levon if (!name)
2061f5207b7SJohn Levon return;
2071f5207b7SJohn Levon true_state = alloc_state(expr, TRUE);
2081f5207b7SJohn Levon false_state = alloc_state(expr, FALSE);
2091f5207b7SJohn Levon set_true_false_states(my_id, name, NULL, true_state, false_state);
2101f5207b7SJohn Levon store_all_links(expr, expr);
2111f5207b7SJohn Levon free_string(name);
2121f5207b7SJohn Levon }
2131f5207b7SJohn Levon
get_stored_condition(struct expression * expr)2141f5207b7SJohn Levon struct smatch_state *get_stored_condition(struct expression *expr)
2151f5207b7SJohn Levon {
2161f5207b7SJohn Levon struct smatch_state *state;
2171f5207b7SJohn Levon char *name;
2181f5207b7SJohn Levon
2191f5207b7SJohn Levon name = expr_to_str(expr);
2201f5207b7SJohn Levon if (!name)
2211f5207b7SJohn Levon return NULL;
2221f5207b7SJohn Levon
2231f5207b7SJohn Levon state = get_state(my_id, name, NULL);
2241f5207b7SJohn Levon free_string(name);
2251f5207b7SJohn Levon return state;
2261f5207b7SJohn Levon }
2271f5207b7SJohn Levon
get_conditions(struct expression * expr)2281f5207b7SJohn Levon struct expression_list *get_conditions(struct expression *expr)
2291f5207b7SJohn Levon {
2301f5207b7SJohn Levon struct smatch_state *state;
2311f5207b7SJohn Levon
2321f5207b7SJohn Levon state = get_state_expr(link_id, expr);
2331f5207b7SJohn Levon if (!state)
2341f5207b7SJohn Levon return NULL;
2351f5207b7SJohn Levon return state->data;
2361f5207b7SJohn Levon }
2371f5207b7SJohn Levon
register_stored_conditions(int id)2381f5207b7SJohn Levon void register_stored_conditions(int id)
2391f5207b7SJohn Levon {
2401f5207b7SJohn Levon my_id = id;
241*efe51d0cSJohn Levon set_dynamic_states(my_id);
2421f5207b7SJohn Levon }
2431f5207b7SJohn Levon
register_stored_conditions_links(int id)2441f5207b7SJohn Levon void register_stored_conditions_links(int id)
2451f5207b7SJohn Levon {
2461f5207b7SJohn Levon link_id = id;
247*efe51d0cSJohn Levon db_ignore_states(link_id);
248*efe51d0cSJohn Levon set_dynamic_states(link_id);
2491f5207b7SJohn Levon add_merge_hook(link_id, &merge_links);
2501f5207b7SJohn Levon add_modification_hook(link_id, &match_link_modify);
2511f5207b7SJohn Levon }
2521f5207b7SJohn Levon
2531f5207b7SJohn Levon #define RECURSE_LIMIT 50
2541f5207b7SJohn Levon
filter_by_sm(struct sm_state * sm,struct state_list ** true_stack,struct state_list ** false_stack,int * recurse_cnt)2551f5207b7SJohn Levon static void filter_by_sm(struct sm_state *sm,
2561f5207b7SJohn Levon struct state_list **true_stack,
2571f5207b7SJohn Levon struct state_list **false_stack,
2581f5207b7SJohn Levon int *recurse_cnt)
2591f5207b7SJohn Levon {
2601f5207b7SJohn Levon if (!sm)
2611f5207b7SJohn Levon return;
2621f5207b7SJohn Levon
2631f5207b7SJohn Levon if ((*recurse_cnt)++ > RECURSE_LIMIT)
2641f5207b7SJohn Levon return;
2651f5207b7SJohn Levon
2661f5207b7SJohn Levon if (strcmp(sm->state->name, "true") == 0) {
2671f5207b7SJohn Levon add_ptr_list(true_stack, sm);
2681f5207b7SJohn Levon } else if (strcmp(sm->state->name, "false") == 0) {
2691f5207b7SJohn Levon add_ptr_list(false_stack, sm);
2701f5207b7SJohn Levon }
2711f5207b7SJohn Levon
2721f5207b7SJohn Levon if (sm->merged) {
2731f5207b7SJohn Levon filter_by_sm(sm->left, true_stack, false_stack, recurse_cnt);
2741f5207b7SJohn Levon filter_by_sm(sm->right, true_stack, false_stack, recurse_cnt);
2751f5207b7SJohn Levon }
2761f5207b7SJohn Levon }
2771f5207b7SJohn Levon
stored_condition_implication_hook(struct expression * expr,struct state_list ** true_stack,struct state_list ** false_stack)2781f5207b7SJohn Levon struct sm_state *stored_condition_implication_hook(struct expression *expr,
2791f5207b7SJohn Levon struct state_list **true_stack,
2801f5207b7SJohn Levon struct state_list **false_stack)
2811f5207b7SJohn Levon {
2821f5207b7SJohn Levon struct sm_state *sm;
2831f5207b7SJohn Levon char *name;
2841f5207b7SJohn Levon int recurse_cnt = 0;
2851f5207b7SJohn Levon struct state_list *tmp_true = NULL;
2861f5207b7SJohn Levon struct state_list *tmp_false = NULL;
2871f5207b7SJohn Levon struct sm_state *tmp;
2881f5207b7SJohn Levon
2891f5207b7SJohn Levon expr = strip_expr(expr);
2901f5207b7SJohn Levon
2911f5207b7SJohn Levon name = expr_to_str(expr);
2921f5207b7SJohn Levon if (!name)
2931f5207b7SJohn Levon return NULL;
2941f5207b7SJohn Levon
2951f5207b7SJohn Levon sm = get_sm_state(my_id, name, NULL);
2961f5207b7SJohn Levon free_string(name);
2971f5207b7SJohn Levon if (!sm)
2981f5207b7SJohn Levon return NULL;
2991f5207b7SJohn Levon if (!sm->merged)
3001f5207b7SJohn Levon return NULL;
3011f5207b7SJohn Levon
3021f5207b7SJohn Levon filter_by_sm(sm, &tmp_true, &tmp_false, &recurse_cnt);
3031f5207b7SJohn Levon if (!tmp_true && !tmp_false)
3041f5207b7SJohn Levon return NULL;
3051f5207b7SJohn Levon if (recurse_cnt > RECURSE_LIMIT) {
3061f5207b7SJohn Levon sm = NULL;
3071f5207b7SJohn Levon goto free;
3081f5207b7SJohn Levon }
3091f5207b7SJohn Levon
3101f5207b7SJohn Levon FOR_EACH_PTR(tmp_true, tmp) {
3111f5207b7SJohn Levon add_ptr_list(true_stack, tmp);
3121f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
3131f5207b7SJohn Levon
3141f5207b7SJohn Levon FOR_EACH_PTR(tmp_false, tmp) {
3151f5207b7SJohn Levon add_ptr_list(false_stack, tmp);
3161f5207b7SJohn Levon } END_FOR_EACH_PTR(tmp);
3171f5207b7SJohn Levon
3181f5207b7SJohn Levon free:
3191f5207b7SJohn Levon free_slist(&tmp_true);
3201f5207b7SJohn Levon free_slist(&tmp_false);
3211f5207b7SJohn Levon return sm;
3221f5207b7SJohn Levon }
3231f5207b7SJohn Levon
324