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