1 /*
2 * Copyright (C) 2015 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 * This is to track when variables are masked away.
20 *
21 */
22
23 #include "smatch.h"
24 #include "smatch_extra.h"
25 #include "smatch_slist.h"
26
27 static int my_id;
28
29 static const struct bit_info unknown_bit_info = {
30 .possible = -1ULL,
31 };
32
33 ALLOCATOR(bit_info, "bit data");
34 static struct bit_info *alloc_bit_info(unsigned long long set, unsigned long long possible)
35 {
36 struct bit_info *bit_info = __alloc_bit_info(0);
37
38 bit_info->set = set;
39 bit_info->possible = possible;
40
41 return bit_info;
42 }
43
44 static struct smatch_state *alloc_bstate(unsigned long long set, unsigned long long possible)
45 {
46 struct smatch_state *state;
47 char buf[64];
48
49 state = __alloc_smatch_state(0);
50 snprintf(buf, sizeof(buf), "0x%llx + 0x%llx", set, possible);
51 state->name = alloc_sname(buf);
52 state->data = alloc_bit_info(set, possible);
53
54 return state;
55 }
56
57 struct bit_info *rl_to_binfo(struct range_list *rl)
58 {
59 struct bit_info *ret = __alloc_bit_info(0);
60 sval_t sval;
61
62 if (rl_to_sval(rl, &sval)) {
63 ret->set = sval.uvalue;
64 ret->possible = sval.uvalue;
65
66 return ret;
67 }
68
69 ret->set = 0;
70 ret->possible = sval_fls_mask(rl_max(rl));
71 // FIXME: what about negatives?
72
73 return ret;
74 }
75
76 static int is_unknown_binfo(struct symbol *type, struct bit_info *binfo)
77 {
78 if (!type)
79 type = &ullong_ctype;
80
81 if (binfo->set != 0)
82 return 0;
83 if (binfo->possible < (-1ULL >> (64 - type_bits(type))))
84 return 0;
85
86 return 1;
87 }
88
89 static struct smatch_state *unmatched_state(struct sm_state *sm)
90 {
91 struct smatch_state *estate;
92 struct symbol *type;
93 unsigned long long possible;
94 struct bit_info *p;
95
96 estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
97 if (estate_rl(estate)) {
98 p = rl_to_binfo(estate_rl(estate));
99 return alloc_bstate(p->set, p->possible);
100 }
101
102 type = estate_type(estate);
103 if (!type)
104 return alloc_bstate(0, -1ULL);
105
106 if (type_bits(type) == 64)
107 possible = -1ULL;
108 else
109 possible = (1ULL << type_bits(type)) - 1;
110
111 return alloc_bstate(0, possible);
112 }
113
114 static bool is_loop_iterator(struct expression *expr)
115 {
116 struct statement *pre_stmt, *loop_stmt;
117
118 pre_stmt = expr_get_parent_stmt(expr);
119 if (!pre_stmt || pre_stmt->type != STMT_EXPRESSION)
120 return false;
121
122 loop_stmt = stmt_get_parent_stmt(pre_stmt);
123 if (!loop_stmt || loop_stmt->type != STMT_ITERATOR)
124 return false;
125 if (loop_stmt->iterator_pre_statement != pre_stmt)
126 return false;
127
128 return true;
129 }
130
131 static bool handled_by_assign_hook(struct expression *expr)
132 {
133 if (!expr || expr->type != EXPR_ASSIGNMENT)
134 return false;
135 if (__in_fake_assign)
136 return false;
137 if (is_loop_iterator(expr))
138 return false;
139
140 if (expr->op == '=' ||
141 expr->op == SPECIAL_OR_ASSIGN ||
142 expr->op == SPECIAL_AND_ASSIGN)
143 return true;
144
145 return false;
146 }
147
148 static void match_modify(struct sm_state *sm, struct expression *mod_expr)
149 {
150 // FIXME: we really need to store the type
151
152 if (handled_by_assign_hook(mod_expr))
153 return;
154 set_state(my_id, sm->name, sm->sym, alloc_bstate(0, -1ULL));
155 }
156
157 static int binfo_equiv(struct bit_info *one, struct bit_info *two)
158 {
159 if (one->set == two->set &&
160 one->possible == two->possible)
161 return 1;
162 return 0;
163 }
164
165 static struct smatch_state *merge_bstates(struct smatch_state *one_state, struct smatch_state *two_state)
166 {
167 struct bit_info *one, *two;
168
169 one = one_state->data;
170 two = two_state->data;
171
172 if (binfo_equiv(one, two))
173 return one_state;
174
175 return alloc_bstate(one->set & two->set, one->possible | two->possible);
176 }
177
178 /*
179 * The combine_bit_info() takes two bit_infos and takes creates the most
180 * accurate picture we can assuming both are true. Or it returns unknown if
181 * the information is logically impossible.
182 *
183 * Which means that it takes the | of the ->set bits and the & of the possibly
184 * set bits, which is the opposite of what merge_bstates() does.
185 *
186 */
187 static struct bit_info *combine_bit_info(struct bit_info *one, struct bit_info *two)
188 {
189 struct bit_info *ret = __alloc_bit_info(0);
190
191 if ((one->set & two->possible) != one->set)
192 return alloc_bit_info(0, -1ULL);
193 if ((two->set & one->possible) != two->set)
194 return alloc_bit_info(0, -1ULL);
195
196 ret->set = one->set | two->set;
197 ret->possible = one->possible & two->possible;
198
199 return ret;
200 }
201
202 static struct bit_info *binfo_AND(struct bit_info *left, struct bit_info *right)
203 {
204 unsigned long long set = 0;
205 unsigned long long possible = -1ULL;
206
207 if (!left && !right) {
208 /* nothing */
209 } else if (!left) {
210 possible = right->possible;
211 } else if (!right) {
212 possible = left->possible;
213 } else {
214 set = left->set & right->set;
215 possible = left->possible & right->possible;
216 }
217
218 return alloc_bit_info(set, possible);
219 }
220
221 static struct bit_info *binfo_OR(struct bit_info *left, struct bit_info *right)
222 {
223 unsigned long long set = 0;
224 unsigned long long possible = -1ULL;
225
226 if (!left && !right) {
227 /* nothing */
228 } else if (!left) {
229 set = right->set;
230 } else if (!right) {
231 set = left->set;
232 } else {
233 set = left->set | right->set;
234 possible = left->possible | right->possible;
235 }
236
237 return alloc_bit_info(set, possible);
238 }
239
240 struct bit_info *get_bit_info(struct expression *expr)
241 {
242 struct range_list *rl;
243 struct smatch_state *bstate;
244 struct bit_info tmp;
245 struct bit_info *extra_info;
246 struct bit_info *bit_info;
247 sval_t known;
248
249 expr = strip_parens(expr);
250
251 if (get_implied_value(expr, &known))
252 return alloc_bit_info(known.value, known.value);
253
254 if (expr->type == EXPR_BINOP) {
255 if (expr->op == '&')
256 return binfo_AND(get_bit_info(expr->left),
257 get_bit_info(expr->right));
258 if (expr->op == '|')
259 return binfo_OR(get_bit_info(expr->left),
260 get_bit_info(expr->right));
261 }
262
263 if (get_implied_rl(expr, &rl))
264 extra_info = rl_to_binfo(rl);
265 else {
266 struct symbol *type;
267
268 tmp = unknown_bit_info;
269 extra_info = &tmp;
270
271 type = get_type(expr);
272 if (!type)
273 type = &ullong_ctype;
274 if (type_bits(type) == 64)
275 extra_info->possible = -1ULL;
276 else
277 extra_info->possible = (1ULL << type_bits(type)) - 1;
278 }
279
280 bstate = get_state_expr(my_id, expr);
281 if (bstate)
282 bit_info = bstate->data;
283 else
284 bit_info = (struct bit_info *)&unknown_bit_info;
285
286 return combine_bit_info(extra_info, bit_info);
287 }
288
289 static int is_single_bit(sval_t sval)
290 {
291 int i;
292 int count = 0;
293
294 for (i = 0; i < 64; i++) {
295 if (sval.uvalue & 1ULL << i &&
296 count++)
297 return 0;
298 }
299 if (count == 1)
300 return 1;
301 return 0;
302 }
303
304 static void match_compare(struct expression *expr)
305 {
306 sval_t val;
307
308 if (expr->type != EXPR_COMPARE)
309 return;
310 if (expr->op != SPECIAL_EQUAL &&
311 expr->op != SPECIAL_NOTEQUAL)
312 return;
313
314 if (!get_implied_value(expr->right, &val))
315 return;
316
317 set_true_false_states_expr(my_id, expr->left,
318 (expr->op == SPECIAL_EQUAL) ? alloc_bstate(val.uvalue, val.uvalue) : NULL,
319 (expr->op == SPECIAL_EQUAL) ? NULL : alloc_bstate(val.uvalue, val.uvalue));
320 }
321
322 static void match_assign(struct expression *expr)
323 {
324 struct bit_info *start, *binfo;
325 struct smatch_state *new;
326
327 if (!handled_by_assign_hook(expr))
328 return;
329
330 binfo = get_bit_info(expr->right);
331 if (!binfo)
332 return;
333 if (expr->op == '=') {
334 if (is_unknown_binfo(get_type(expr->left), binfo))
335 return;
336
337 set_state_expr(my_id, expr->left, alloc_bstate(binfo->set, binfo->possible));
338 } else if (expr->op == SPECIAL_OR_ASSIGN) {
339 start = get_bit_info(expr->left);
340 new = alloc_bstate(start->set | binfo->set, start->possible | binfo->possible);
341 set_state_expr(my_id, expr->left, new);
342 } else if (expr->op == SPECIAL_AND_ASSIGN) {
343 start = get_bit_info(expr->left);
344 new = alloc_bstate(start->set & binfo->set, start->possible & binfo->possible);
345 set_state_expr(my_id, expr->left, new);
346 }
347 }
348
349 static void match_condition(struct expression *expr)
350 {
351 struct bit_info *orig;
352 struct bit_info true_info;
353 struct bit_info false_info;
354 sval_t right;
355
356 if (expr->type != EXPR_BINOP ||
357 expr->op != '&')
358 return;
359
360 if (!get_value(expr->right, &right))
361 return;
362
363 orig = get_bit_info(expr->left);
364 true_info = *orig;
365 false_info = *orig;
366
367 if (right.uvalue == 0 || is_single_bit(right))
368 true_info.set &= right.uvalue;
369
370 true_info.possible &= right.uvalue;
371 false_info.possible &= ~right.uvalue;
372
373 set_true_false_states_expr(my_id, expr->left,
374 alloc_bstate(true_info.set, true_info.possible),
375 alloc_bstate(false_info.set, false_info.possible));
376 }
377
378 static void match_call_info(struct expression *expr)
379 {
380 struct bit_info *binfo, *rl_binfo;
381 struct expression *arg;
382 struct range_list *rl;
383 char buf[64];
384 int i;
385
386 i = -1;
387 FOR_EACH_PTR(expr->args, arg) {
388 i++;
389 binfo = get_bit_info(arg);
390 if (!binfo)
391 continue;
392 if (is_unknown_binfo(get_type(arg), binfo))
393 continue;
394 if (get_implied_rl(arg, &rl)) {
395 rl_binfo = rl_to_binfo(rl);
396 if (binfo_equiv(rl_binfo, binfo))
397 continue;
398 }
399 // If is just non-negative continue
400 // If ->set == ->possible continue
401 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
402 sql_insert_caller_info(expr, BIT_INFO, i, "$", buf);
403 } END_FOR_EACH_PTR(arg);
404 }
405
406 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
407 {
408 struct bit_info *binfo = sm->state->data;
409 struct smatch_state *estate;
410 struct bit_info *implied_binfo;
411 char buf[64];
412
413 if (!binfo)
414 return;
415
416 /* This means it can only be one value, so it's handled by smatch_extra. */
417 if (binfo->set == binfo->possible)
418 return;
419
420 estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
421 if (is_unknown_binfo(estate_type(estate), binfo))
422 return;
423
424 if (estate_rl(estate)) {
425 sval_t sval;
426
427 if (estate_get_single_value(estate, &sval))
428 return;
429
430 implied_binfo = rl_to_binfo(estate_rl(estate));
431 if (binfo_equiv(implied_binfo, binfo))
432 return;
433 }
434
435 snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
436 sql_insert_caller_info(call, BIT_INFO, param, printed_name, buf);
437 }
438
439 static void set_param_bits(const char *name, struct symbol *sym, char *key, char *value)
440 {
441 char fullname[256];
442 unsigned long long set, possible;
443
444 if (strcmp(key, "*$") == 0)
445 snprintf(fullname, sizeof(fullname), "*%s", name);
446 else if (strncmp(key, "$", 1) == 0)
447 snprintf(fullname, 256, "%s%s", name, key + 1);
448 else
449 return;
450
451 set = strtoull(value, &value, 16);
452 if (*value != ',')
453 return;
454 value++;
455 possible = strtoull(value, &value, 16);
456
457 set_state(my_id, fullname, sym, alloc_bstate(set, possible));
458 }
459
460 void register_bits(int id)
461 {
462 my_id = id;
463
464 set_dynamic_states(my_id);
465
466 add_unmatched_state_hook(my_id, &unmatched_state);
467 add_merge_hook(my_id, &merge_bstates);
468
469 add_hook(&match_condition, CONDITION_HOOK);
470 add_hook(&match_compare, CONDITION_HOOK);
471 add_hook(&match_assign, ASSIGNMENT_HOOK);
472 add_modification_hook(my_id, &match_modify);
473
474 add_hook(&match_call_info, FUNCTION_CALL_HOOK);
475 add_member_info_callback(my_id, struct_member_callback);
476 select_caller_info_hook(set_param_bits, BIT_INFO);
477 }