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 } 242 243 void register_stored_conditions_links(int id) 244 { 245 link_id = id; 246 add_merge_hook(link_id, &merge_links); 247 add_modification_hook(link_id, &match_link_modify); 248 } 249 250 #define RECURSE_LIMIT 50 251 252 static void filter_by_sm(struct sm_state *sm, 253 struct state_list **true_stack, 254 struct state_list **false_stack, 255 int *recurse_cnt) 256 { 257 if (!sm) 258 return; 259 260 if ((*recurse_cnt)++ > RECURSE_LIMIT) 261 return; 262 263 if (strcmp(sm->state->name, "true") == 0) { 264 add_ptr_list(true_stack, sm); 265 } else if (strcmp(sm->state->name, "false") == 0) { 266 add_ptr_list(false_stack, sm); 267 } 268 269 if (sm->merged) { 270 filter_by_sm(sm->left, true_stack, false_stack, recurse_cnt); 271 filter_by_sm(sm->right, true_stack, false_stack, recurse_cnt); 272 } 273 } 274 275 struct sm_state *stored_condition_implication_hook(struct expression *expr, 276 struct state_list **true_stack, 277 struct state_list **false_stack) 278 { 279 struct sm_state *sm; 280 char *name; 281 int recurse_cnt = 0; 282 struct state_list *tmp_true = NULL; 283 struct state_list *tmp_false = NULL; 284 struct sm_state *tmp; 285 286 expr = strip_expr(expr); 287 288 name = expr_to_str(expr); 289 if (!name) 290 return NULL; 291 292 sm = get_sm_state(my_id, name, NULL); 293 free_string(name); 294 if (!sm) 295 return NULL; 296 if (!sm->merged) 297 return NULL; 298 299 filter_by_sm(sm, &tmp_true, &tmp_false, &recurse_cnt); 300 if (!tmp_true && !tmp_false) 301 return NULL; 302 if (recurse_cnt > RECURSE_LIMIT) { 303 sm = NULL; 304 goto free; 305 } 306 307 FOR_EACH_PTR(tmp_true, tmp) { 308 add_ptr_list(true_stack, tmp); 309 } END_FOR_EACH_PTR(tmp); 310 311 FOR_EACH_PTR(tmp_false, tmp) { 312 add_ptr_list(false_stack, tmp); 313 } END_FOR_EACH_PTR(tmp); 314 315 free: 316 free_slist(&tmp_true); 317 free_slist(&tmp_false); 318 return sm; 319 } 320 321