xref: /illumos-gate/usr/src/tools/smatch/src/smatch_bits.c (revision 6523a3aa7f325d64841382707603be7a86e68147)
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");
alloc_bit_info(unsigned long long set,unsigned long long possible)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 
alloc_bstate(unsigned long long set,unsigned long long possible)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 
rl_to_binfo(struct range_list * rl)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 
is_unknown_binfo(struct symbol * type,struct bit_info * binfo)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 
unmatched_state(struct sm_state * sm)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 
is_loop_iterator(struct expression * expr)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 
handled_by_assign_hook(struct expression * expr)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 
match_modify(struct sm_state * sm,struct expression * mod_expr)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 
binfo_equiv(struct bit_info * one,struct bit_info * two)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 
merge_bstates(struct smatch_state * one_state,struct smatch_state * two_state)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  */
combine_bit_info(struct bit_info * one,struct bit_info * two)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 
binfo_AND(struct bit_info * left,struct bit_info * right)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 
binfo_OR(struct bit_info * left,struct bit_info * right)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 
get_bit_info(struct expression * expr)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 
is_single_bit(sval_t sval)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 
match_compare(struct expression * expr)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 
match_assign(struct expression * expr)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 
match_condition(struct expression * expr)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 
match_call_info(struct expression * expr)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 
struct_member_callback(struct expression * call,int param,char * printed_name,struct sm_state * sm)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 
set_param_bits(const char * name,struct symbol * sym,char * key,char * value)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 
register_bits(int id)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 }
478