1 /* 2 * Copyright (C) 2014 Oracle. 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 /* 19 * Keep a record of all the things we have tested for so that we know when we 20 * test for it again. For example, if we have code like this: 21 * 22 * if (foo & FLAG) 23 * lock(); 24 * 25 * ... 26 * 27 * if (foo & FLAG) 28 * unlock(); 29 * 30 * That's the end goal at least. But actually implementing the flow of that 31 * requires quite a bit of work because if "foo" changes the condition needs to 32 * be retested and smatch_implications.c needs to be updated. 33 * 34 * For now, I just record the conditions and use it to see if we test for NULL 35 * twice. 36 * 37 */ 38 39 #include "smatch.h" 40 #include "smatch_slist.h" 41 42 static int my_id; 43 static int link_id; 44 45 static struct smatch_state *alloc_link_state(struct expression_list *expr_list) 46 { 47 struct expression *tmp; 48 struct smatch_state *state; 49 static char buf[256]; 50 char *name; 51 int i; 52 53 state = __alloc_smatch_state(0); 54 55 i = 0; 56 FOR_EACH_PTR(expr_list, tmp) { 57 name = expr_to_str(tmp); 58 if (!i++) { 59 snprintf(buf, sizeof(buf), "%s", name); 60 } else { 61 append(buf, ", ", sizeof(buf)); 62 append(buf, name, sizeof(buf)); 63 } 64 free_string(name); 65 } END_FOR_EACH_PTR(tmp); 66 67 state->name = alloc_sname(buf); 68 state->data = expr_list; 69 return state; 70 } 71 72 static struct expression_list *clone_expression_list(struct expression_list *list) 73 { 74 struct expression_list *ret = NULL; 75 struct expression *expr; 76 77 FOR_EACH_PTR(list, expr) { 78 add_ptr_list(&ret, expr); 79 } END_FOR_EACH_PTR(expr); 80 81 return ret; 82 } 83 84 static void insert_expression(struct expression_list **list, struct expression *expr) 85 { 86 struct expression *tmp; 87 88 FOR_EACH_PTR(*list, tmp) { 89 if (tmp == expr) 90 return; 91 } END_FOR_EACH_PTR(tmp); 92 93 add_ptr_list(list, expr); 94 } 95 96 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2) 97 { 98 struct expression_list *list, *expr_list; 99 struct expression *expr; 100 101 expr_list = clone_expression_list(s1->data); 102 103 list = s2->data; 104 FOR_EACH_PTR(list, expr) { 105 insert_expression(&expr_list, expr); 106 } END_FOR_EACH_PTR(expr); 107 108 return alloc_link_state(expr_list); 109 } 110 111 static void save_link_var_sym(const char *var, struct symbol *sym, struct expression *condition) 112 { 113 struct smatch_state *old_state, *new_state; 114 struct expression_list *expr_list; 115 116 old_state = get_state(link_id, var, sym); 117 expr_list = clone_expression_list(old_state ? old_state->data : NULL); 118 119 insert_expression(&expr_list, condition); 120 121 new_state = alloc_link_state(expr_list); 122 set_state(link_id, var, sym, new_state); 123 } 124 125 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr) 126 { 127 struct expression_list *expr_list; 128 struct expression *tmp; 129 char *name; 130 131 expr_list = sm->state->data; 132 133 FOR_EACH_PTR(expr_list, tmp) { 134 name = expr_to_str(tmp); 135 set_state(my_id, name, NULL, &undefined); 136 free_string(name); 137 } END_FOR_EACH_PTR(tmp); 138 set_state(link_id, sm->name, sm->sym, &undefined); 139 } 140 141 static struct smatch_state *alloc_state(struct expression *expr, int is_true) 142 { 143 struct smatch_state *state; 144 145 state = __alloc_smatch_state(0); 146 if (is_true) 147 state->name = alloc_sname("true"); 148 else 149 state->name = alloc_sname("false"); 150 state->data = expr; 151 return state; 152 } 153 154 static void store_all_links(struct expression *expr, struct expression *condition) 155 { 156 char *var; 157 struct symbol *sym; 158 159 expr = strip_expr(expr); 160 161 if (is_array(expr)) { 162 var = expr_to_known_chunk_sym(expr, &sym); 163 if (var) 164 save_link_var_sym(var, sym, condition); 165 } 166 167 switch (expr->type) { 168 case EXPR_COMPARE: 169 case EXPR_BINOP: 170 store_all_links(expr->left, condition); 171 store_all_links(expr->right, condition); 172 return; 173 case EXPR_VALUE: 174 return; 175 } 176 177 var = expr_to_var_sym(expr, &sym); 178 if (!var || !sym) 179 goto free; 180 save_link_var_sym(var, sym, condition); 181 free: 182 free_string(var); 183 } 184 185 static int condition_too_complicated(struct expression *expr) 186 { 187 if (get_complication_score(expr) > 2) 188 return 1; 189 return 0; 190 } 191 192 void __stored_condition(struct expression *expr) 193 { 194 struct smatch_state *true_state, *false_state; 195 char *name; 196 sval_t val; 197 198 if (get_value(expr, &val)) 199 return; 200 201 if (condition_too_complicated(expr)) 202 return; 203 204 name = expr_to_str(expr); 205 if (!name) 206 return; 207 true_state = alloc_state(expr, TRUE); 208 false_state = alloc_state(expr, FALSE); 209 set_true_false_states(my_id, name, NULL, true_state, false_state); 210 store_all_links(expr, expr); 211 free_string(name); 212 } 213 214 struct smatch_state *get_stored_condition(struct expression *expr) 215 { 216 struct smatch_state *state; 217 char *name; 218 219 name = expr_to_str(expr); 220 if (!name) 221 return NULL; 222 223 state = get_state(my_id, name, NULL); 224 free_string(name); 225 return state; 226 } 227 228 struct expression_list *get_conditions(struct expression *expr) 229 { 230 struct smatch_state *state; 231 232 state = get_state_expr(link_id, expr); 233 if (!state) 234 return NULL; 235 return state->data; 236 } 237 238 void register_stored_conditions(int id) 239 { 240 my_id = id; 241 set_dynamic_states(my_id); 242 } 243 244 void register_stored_conditions_links(int id) 245 { 246 link_id = id; 247 db_ignore_states(link_id); 248 set_dynamic_states(link_id); 249 add_merge_hook(link_id, &merge_links); 250 add_modification_hook(link_id, &match_link_modify); 251 } 252 253 #define RECURSE_LIMIT 50 254 255 static void filter_by_sm(struct sm_state *sm, 256 struct state_list **true_stack, 257 struct state_list **false_stack, 258 int *recurse_cnt) 259 { 260 if (!sm) 261 return; 262 263 if ((*recurse_cnt)++ > RECURSE_LIMIT) 264 return; 265 266 if (strcmp(sm->state->name, "true") == 0) { 267 add_ptr_list(true_stack, sm); 268 } else if (strcmp(sm->state->name, "false") == 0) { 269 add_ptr_list(false_stack, sm); 270 } 271 272 if (sm->merged) { 273 filter_by_sm(sm->left, true_stack, false_stack, recurse_cnt); 274 filter_by_sm(sm->right, true_stack, false_stack, recurse_cnt); 275 } 276 } 277 278 struct sm_state *stored_condition_implication_hook(struct expression *expr, 279 struct state_list **true_stack, 280 struct state_list **false_stack) 281 { 282 struct sm_state *sm; 283 char *name; 284 int recurse_cnt = 0; 285 struct state_list *tmp_true = NULL; 286 struct state_list *tmp_false = NULL; 287 struct sm_state *tmp; 288 289 expr = strip_expr(expr); 290 291 name = expr_to_str(expr); 292 if (!name) 293 return NULL; 294 295 sm = get_sm_state(my_id, name, NULL); 296 free_string(name); 297 if (!sm) 298 return NULL; 299 if (!sm->merged) 300 return NULL; 301 302 filter_by_sm(sm, &tmp_true, &tmp_false, &recurse_cnt); 303 if (!tmp_true && !tmp_false) 304 return NULL; 305 if (recurse_cnt > RECURSE_LIMIT) { 306 sm = NULL; 307 goto free; 308 } 309 310 FOR_EACH_PTR(tmp_true, tmp) { 311 add_ptr_list(true_stack, tmp); 312 } END_FOR_EACH_PTR(tmp); 313 314 FOR_EACH_PTR(tmp_false, tmp) { 315 add_ptr_list(false_stack, tmp); 316 } END_FOR_EACH_PTR(tmp); 317 318 free: 319 free_slist(&tmp_true); 320 free_slist(&tmp_false); 321 return sm; 322 } 323 324