xref: /illumos-gate/usr/src/tools/smatch/src/smatch_math.c (revision 6523a3aa7f325d64841382707603be7a86e68147)
1 /*
2  * Copyright (C) 2010 Dan Carpenter.
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 #include "symbol.h"
19 #include "smatch.h"
20 #include "smatch_slist.h"
21 #include "smatch_extra.h"
22 
23 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
27 
28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
30 
31 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
32 static sval_t one   = {.type = &int_ctype, {.value = 1} };
33 
34 static int fast_math_only;
35 
rl_zero(void)36 struct range_list *rl_zero(void)
37 {
38 	static struct range_list *zero_perm;
39 
40 	if (!zero_perm)
41 		zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
42 	return zero_perm;
43 }
44 
rl_one(void)45 struct range_list *rl_one(void)
46 {
47 	static struct range_list *one_perm;
48 
49 	if (!one_perm)
50 		one_perm = clone_rl_permanent(alloc_rl(one, one));
51 
52 	return one_perm;
53 }
54 
55 enum {
56 	RL_EXACT,
57 	RL_HARD,
58 	RL_FUZZY,
59 	RL_IMPLIED,
60 	RL_ABSOLUTE,
61 	RL_REAL_ABSOLUTE,
62 };
63 
last_stmt_rl(struct statement * stmt,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)64 static bool last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
65 {
66 	struct expression *expr;
67 
68 	if (!stmt)
69 		return false;
70 
71 	stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
72 	if (stmt->type == STMT_LABEL) {
73 		if (stmt->label_statement &&
74 		    stmt->label_statement->type == STMT_EXPRESSION)
75 			expr = stmt->label_statement->expression;
76 		else
77 			return false;
78 	} else if (stmt->type == STMT_EXPRESSION) {
79 		expr = stmt->expression;
80 	} else {
81 		return false;
82 	}
83 	return get_rl_sval(expr, implied, recurse_cnt, res, res_sval);
84 }
85 
handle_expression_statement_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)86 static bool handle_expression_statement_rl(struct expression *expr, int implied,
87 		int *recurse_cnt, struct range_list **res, sval_t *res_sval)
88 {
89 	return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt, res, res_sval);
90 }
91 
handle_address(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)92 static bool handle_address(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
93 {
94 	struct range_list *rl;
95 	static int recursed;
96 	sval_t sval;
97 
98 	if (recursed > 10)
99 		return false;
100 	if (implied == RL_EXACT)
101 		return false;
102 
103 	if (custom_handle_variable) {
104 		rl = custom_handle_variable(expr);
105 		if (rl) {
106 			*res = rl;
107 			return true;
108 		}
109 	}
110 
111 	recursed++;
112 	if (get_mtag_sval(expr, &sval)) {
113 		recursed--;
114 		*res_sval = sval;
115 		return true;
116 	}
117 
118 	if (get_address_rl(expr, res)) {
119 		recursed--;
120 		return true;
121 	}
122 	recursed--;
123 	return 0;
124 }
125 
handle_ampersand_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)126 static bool handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
127 {
128 	return handle_address(expr, implied, recurse_cnt, res, res_sval);
129 }
130 
handle_negate_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)131 static bool handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
132 {
133 	if (known_condition_true(expr->unop)) {
134 		*res_sval = zero;
135 		return true;
136 	}
137 	if (known_condition_false(expr->unop)) {
138 		*res_sval = one;
139 		return true;
140 	}
141 
142 	if (implied == RL_EXACT)
143 		return false;
144 
145 	if (implied_condition_true(expr->unop)) {
146 		*res_sval = zero;
147 		return true;
148 	}
149 	if (implied_condition_false(expr->unop)) {
150 		*res_sval = one;
151 		return true;
152 	}
153 
154 	*res = alloc_rl(zero, one);
155 	return true;
156 }
157 
handle_bitwise_negate(struct expression * expr,int implied,int * recurse_cnt,sval_t * res_sval)158 static bool handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
159 {
160 	struct range_list *rl;
161 	sval_t sval = {};
162 
163 	if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
164 		return false;
165 	if (!sval.type && !rl_to_sval(rl, &sval))
166 		return false;
167 	sval = sval_preop(sval, '~');
168 	sval_cast(get_type(expr->unop), sval);
169 	*res_sval = sval;
170 	return true;
171 }
172 
untrusted_type_min(struct expression * expr)173 static bool untrusted_type_min(struct expression *expr)
174 {
175 	struct range_list *rl;
176 
177 	rl = var_user_rl(expr);
178 	return rl && sval_is_min(rl_min(rl));
179 }
180 
handle_minus_preop(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)181 static bool handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
182 {
183 	struct range_list *rl;
184 	struct range_list *ret = NULL;
185 	struct symbol *type;
186 	sval_t neg_one = { 0 };
187 	sval_t zero = { 0 };
188 	sval_t sval = {};
189 
190 	neg_one.value = -1;
191 	zero.value = 0;
192 
193 	if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
194 		return false;
195 	if (sval.type) {
196 		*res_sval = sval_preop(sval, '-');
197 		return true;
198 	}
199 	/*
200 	 * One complication is that -INT_MIN is still INT_MIN because of integer
201 	 * overflows...  But how many times do we set a time out to INT_MIN?
202 	 * So normally when we call abs() then it does return a positive value.
203 	 *
204 	 */
205 	type = rl_type(rl);
206 	neg_one.type = zero.type = type;
207 
208 	if (sval_is_negative(rl_min(rl))) {
209 		struct range_list *neg;
210 		struct data_range *drange;
211 		sval_t new_min, new_max;
212 
213 		neg = alloc_rl(sval_type_min(type), neg_one);
214 		neg = rl_intersection(rl, neg);
215 
216 		if (sval_is_min(rl_min(neg)) && !sval_is_min(rl_max(neg)))
217 			neg = remove_range(neg, sval_type_min(type), sval_type_min(type));
218 
219 		FOR_EACH_PTR(neg, drange) {
220 			new_min = drange->max;
221 			new_min.value = -new_min.value;
222 			new_max = drange->min;
223 			new_max.value = -new_max.value;
224 			add_range(&ret, new_min, new_max);
225 		} END_FOR_EACH_PTR(drange);
226 
227 		if (untrusted_type_min(expr))
228 			add_range(&ret, sval_type_min(type), sval_type_min(type));
229 	}
230 
231 	if (!sval_is_negative(rl_max(rl))) {
232 		struct range_list *pos;
233 		struct data_range *drange;
234 		sval_t new_min, new_max;
235 
236 		pos = alloc_rl(zero, sval_type_max(type));
237 		pos = rl_intersection(rl, pos);
238 
239 		FOR_EACH_PTR(pos, drange) {
240 			new_min = drange->max;
241 			new_min.value = -new_min.value;
242 			new_max = drange->min;
243 			new_max.value = -new_max.value;
244 			add_range(&ret, new_min, new_max);
245 		} END_FOR_EACH_PTR(drange);
246 	}
247 
248 	*res = ret;
249 	return true;
250 }
251 
handle_preop_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)252 static bool handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
253 {
254 	switch (expr->op) {
255 	case '&':
256 		return handle_ampersand_rl(expr, implied, recurse_cnt, res, res_sval);
257 	case '!':
258 		return handle_negate_rl(expr, implied, recurse_cnt, res, res_sval);
259 	case '~':
260 		return handle_bitwise_negate(expr, implied, recurse_cnt, res_sval);
261 	case '-':
262 		return handle_minus_preop(expr, implied, recurse_cnt, res, res_sval);
263 	case '*':
264 		return handle_variable(expr, implied, recurse_cnt, res, res_sval);
265 	case '(':
266 		return handle_expression_statement_rl(expr, implied, recurse_cnt, res, res_sval);
267 	default:
268 		return false;
269 	}
270 }
271 
handle_divide_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)272 static bool handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
273 {
274 	struct range_list *left_rl = NULL;
275 	struct range_list *right_rl = NULL;
276 	struct symbol *type;
277 
278 	type = get_type(expr);
279 
280 	get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
281 	left_rl = cast_rl(type, left_rl);
282 	get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
283 	right_rl = cast_rl(type, right_rl);
284 
285 	if (!left_rl || !right_rl)
286 		return false;
287 
288 	if (implied != RL_REAL_ABSOLUTE) {
289 		if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
290 			return false;
291 	}
292 
293 	*res = rl_binop(left_rl, '/', right_rl);
294 	return true;
295 }
296 
handle_offset_subtraction(struct expression * expr)297 static int handle_offset_subtraction(struct expression *expr)
298 {
299 	struct expression *left, *right;
300 	struct symbol *left_sym, *right_sym;
301 	struct symbol *type;
302 	int left_offset, right_offset;
303 
304 	type = get_type(expr);
305 	if (!type || type->type != SYM_PTR)
306 		return -1;
307 	type = get_real_base_type(type);
308 	if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
309 		return -1;
310 
311 	left = strip_expr(expr->left);
312 	right = strip_expr(expr->right);
313 
314 	if (left->type != EXPR_PREOP || left->op != '&')
315 		return -1;
316 	left = strip_expr(left->unop);
317 
318 	left_sym = expr_to_sym(left);
319 	right_sym = expr_to_sym(right);
320 	if (!left_sym || left_sym != right_sym)
321 		return -1;
322 
323 	left_offset = get_member_offset_from_deref(left);
324 	if (right->type == EXPR_SYMBOL)
325 		right_offset = 0;
326 	else {
327 		if (right->type != EXPR_PREOP || right->op != '&')
328 			return -1;
329 		right = strip_expr(right->unop);
330 		right_offset = get_member_offset_from_deref(right);
331 	}
332 	if (left_offset < 0 || right_offset < 0)
333 		return -1;
334 
335 	return left_offset - right_offset;
336 }
337 
max_is_unknown_max(struct range_list * rl)338 static bool max_is_unknown_max(struct range_list *rl)
339 {
340 	/*
341 	 * The issue with this code is that we had:
342 	 * if (foo > 1) return 1 - foo;
343 	 * Ideally we would say that returns s32min-(-1) but what Smatch
344 	 * was saying was that the lowest possible value was "1 - INT_MAX"
345 	 *
346 	 * My solution is to ignore max values for int or larger.  I keep
347 	 * the max for shorts etc, because those might be worthwhile.
348 	 *
349 	 * The problem with just returning 1 - INT_MAX is that that is
350 	 * treated as useful information but s32min is treated as basically
351 	 * unknown.
352 	 */
353 
354 	if (type_bits(rl_type(rl)) < 31)
355 		return false;
356 	return sval_is_max(rl_max(rl));
357 }
358 
handle_subtract_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)359 static bool handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
360 {
361 	struct symbol *type;
362 	struct range_list *left_orig, *right_orig;
363 	struct range_list *left_rl, *right_rl;
364 	sval_t min, max, tmp;
365 	int comparison;
366 	int offset;
367 
368 	type = get_type(expr);
369 
370 	offset = handle_offset_subtraction(expr);
371 	if (offset >= 0) {
372 		tmp.type = type;
373 		tmp.value = offset;
374 
375 		*res = alloc_rl(tmp, tmp);
376 		return true;
377 	}
378 
379 	comparison = get_comparison(expr->left, expr->right);
380 
381 	left_orig = NULL;
382 	get_rl_internal(expr->left, implied, recurse_cnt, &left_orig);
383 	left_rl = cast_rl(type, left_orig);
384 	right_orig = NULL;
385 	get_rl_internal(expr->right, implied, recurse_cnt, &right_orig);
386 	right_rl = cast_rl(type, right_orig);
387 
388 	if ((!left_rl || !right_rl) &&
389 	    (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
390 		return false;
391 
392 	if (!left_rl)
393 		left_rl = alloc_whole_rl(type);
394 	if (!right_rl)
395 		right_rl = alloc_whole_rl(type);
396 
397 	/* negative values complicate everything fix this later */
398 	if (sval_is_negative(rl_min(right_rl)))
399 		return false;
400 	max = rl_max(left_rl);
401 	min = sval_type_min(type);
402 
403 	switch (comparison) {
404 	case '>':
405 	case SPECIAL_UNSIGNED_GT:
406 		min = sval_type_val(type, 1);
407 		max = rl_max(left_rl);
408 		break;
409 	case SPECIAL_GTE:
410 	case SPECIAL_UNSIGNED_GTE:
411 		min = sval_type_val(type, 0);
412 		max = rl_max(left_rl);
413 		break;
414 	case SPECIAL_EQUAL:
415 		min = sval_type_val(type, 0);
416 		max = sval_type_val(type, 0);
417 		break;
418 	case '<':
419 	case SPECIAL_UNSIGNED_LT:
420 		max = sval_type_val(type, -1);
421 		break;
422 	case SPECIAL_LTE:
423 	case SPECIAL_UNSIGNED_LTE:
424 		max = sval_type_val(type, 0);
425 		break;
426 	default:
427 		if (!left_orig || !right_orig)
428 			return false;
429 		*res = rl_binop(left_rl, '-', right_rl);
430 		return true;
431 	}
432 
433 	if (!max_is_unknown_max(right_rl) &&
434 	    !sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
435 		tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
436 		if (sval_cmp(tmp, min) > 0)
437 			min = tmp;
438 	}
439 
440 	if (!sval_is_max(rl_max(left_rl))) {
441 		tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
442 		if (sval_cmp(tmp, max) < 0)
443 			max = tmp;
444 	}
445 
446 	if (sval_is_min(min) && sval_is_max(max))
447 		return false;
448 
449 	*res = cast_rl(type, alloc_rl(min, max));
450 	return true;
451 }
452 
handle_mod_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)453 static bool handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
454 {
455 	struct range_list *rl;
456 	sval_t left, right, sval;
457 
458 	if (implied == RL_EXACT) {
459 		if (!get_implied_value(expr->right, &right))
460 			return false;
461 		if (!get_implied_value(expr->left, &left))
462 			return false;
463 		sval = sval_binop(left, '%', right);
464 		*res = alloc_rl(sval, sval);
465 		return true;
466 	}
467 	/* if we can't figure out the right side it's probably hopeless */
468 	if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
469 		return false;
470 
471 	right = sval_cast(get_type(expr), right);
472 	right.value--;
473 
474 	if (get_rl_internal(expr->left, implied, recurse_cnt, &rl) && rl &&
475 	    rl_max(rl).uvalue < right.uvalue)
476 		right.uvalue = rl_max(rl).uvalue;
477 
478 	*res = alloc_rl(sval_cast(right.type, zero), right);
479 	return true;
480 }
481 
handle_bitwise_AND(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)482 static bool handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
483 {
484 	struct symbol *type;
485 	struct range_list *left_rl, *right_rl;
486 	int new_recurse;
487 
488 	if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
489 		return false;
490 
491 	type = get_type(expr);
492 
493 	if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl))
494 		left_rl = alloc_whole_rl(type);
495 	left_rl = cast_rl(type, left_rl);
496 
497 	new_recurse = *recurse_cnt;
498 	if (*recurse_cnt >= 200)
499 		new_recurse = 100;  /* Let's try super hard to get the mask */
500 	if (!get_rl_internal(expr->right, implied, &new_recurse, &right_rl))
501 		right_rl = alloc_whole_rl(type);
502 	right_rl = cast_rl(type, right_rl);
503 	*recurse_cnt = new_recurse;
504 
505 	*res = rl_binop(left_rl, '&', right_rl);
506 	return true;
507 }
508 
use_rl_binop(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)509 static bool use_rl_binop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
510 {
511 	struct symbol *type;
512 	struct range_list *left_rl, *right_rl;
513 
514 	if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
515 		return false;
516 
517 	type = get_type(expr);
518 
519 	get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
520 	get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
521 	left_rl = cast_rl(type, left_rl);
522 	right_rl = cast_rl(type, right_rl);
523 	if (!left_rl || !right_rl)
524 		return false;
525 
526 	*res = rl_binop(left_rl, expr->op, right_rl);
527 	return true;
528 }
529 
handle_right_shift(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)530 static bool handle_right_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
531 {
532 	struct range_list *left_rl, *right_rl;
533 	sval_t min, max;
534 
535 	if (implied == RL_EXACT || implied == RL_HARD)
536 		return false;
537 
538 	if (get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
539 		max = rl_max(left_rl);
540 		min = rl_min(left_rl);
541 	} else {
542 		if (implied == RL_FUZZY)
543 			return false;
544 		max = sval_type_max(get_type(expr->left));
545 		min = sval_type_val(get_type(expr->left), 0);
546 	}
547 
548 	if (get_rl_internal(expr->right, implied, recurse_cnt, &right_rl) &&
549 	    !sval_is_negative(rl_min(right_rl))) {
550 		min = sval_binop(min, SPECIAL_RIGHTSHIFT, rl_max(right_rl));
551 		max = sval_binop(max, SPECIAL_RIGHTSHIFT, rl_min(right_rl));
552 	} else if (!sval_is_negative(min)) {
553 		min.value = 0;
554 		max = sval_type_max(max.type);
555 	} else {
556 		return false;
557 	}
558 
559 	*res = alloc_rl(min, max);
560 	return true;
561 }
562 
handle_left_shift(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)563 static bool handle_left_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
564 {
565 	struct range_list *left_rl, *rl;
566 	sval_t right;
567 
568 	if (implied == RL_EXACT || implied == RL_HARD)
569 		return false;
570 	/* this is hopeless without the right side */
571 	if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
572 		return false;
573 	if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
574 		if (implied == RL_FUZZY)
575 			return false;
576 		left_rl = alloc_whole_rl(get_type(expr->left));
577 	}
578 
579 	rl = rl_binop(left_rl, SPECIAL_LEFTSHIFT, alloc_rl(right, right));
580 	if (!rl)
581 		return false;
582 	*res = rl;
583 	return true;
584 }
585 
handle_known_binop(struct expression * expr,sval_t * res)586 static bool handle_known_binop(struct expression *expr, sval_t *res)
587 {
588 	sval_t left, right;
589 
590 	if (!get_value(expr->left, &left))
591 		return false;
592 	if (!get_value(expr->right, &right))
593 		return false;
594 	*res = sval_binop(left, expr->op, right);
595 	return true;
596 }
597 
has_actual_ranges(struct range_list * rl)598 static int has_actual_ranges(struct range_list *rl)
599 {
600 	struct data_range *tmp;
601 
602 	FOR_EACH_PTR(rl, tmp) {
603 		if (sval_cmp(tmp->min, tmp->max) != 0)
604 			return 1;
605 	} END_FOR_EACH_PTR(tmp);
606 	return 0;
607 }
608 
handle_implied_binop(struct range_list * left_rl,int op,struct range_list * right_rl)609 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
610 {
611 	struct range_list *res_rl;
612 	struct data_range *left_drange, *right_drange;
613 	sval_t res;
614 
615 	if (!left_rl || !right_rl)
616 		return NULL;
617 	if (has_actual_ranges(left_rl))
618 		return NULL;
619 	if (has_actual_ranges(right_rl))
620 		return NULL;
621 
622 	if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
623 		return NULL;
624 
625 	res_rl = NULL;
626 
627 	FOR_EACH_PTR(left_rl, left_drange) {
628 		FOR_EACH_PTR(right_rl, right_drange) {
629 			if ((op == '%' || op == '/') &&
630 			    right_drange->min.value == 0)
631 				return NULL;
632 			res = sval_binop(left_drange->min, op, right_drange->min);
633 			add_range(&res_rl, res, res);
634 		} END_FOR_EACH_PTR(right_drange);
635 	} END_FOR_EACH_PTR(left_drange);
636 
637 	return res_rl;
638 }
639 
handle_binop_rl_helper(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)640 static bool handle_binop_rl_helper(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
641 {
642 	struct symbol *type;
643 	struct range_list *left_rl = NULL;
644 	struct range_list *right_rl = NULL;
645 	struct range_list *rl;
646 	sval_t min, max;
647 
648 	type = get_promoted_type(get_type(expr->left), get_type(expr->right));
649 	get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
650 	left_rl = cast_rl(type, left_rl);
651 	get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
652 	right_rl = cast_rl(type, right_rl);
653 	if (!left_rl && !right_rl)
654 		return false;
655 
656 	rl = handle_implied_binop(left_rl, expr->op, right_rl);
657 	if (rl) {
658 		*res = rl;
659 		return true;
660 	}
661 
662 	switch (expr->op) {
663 	case '%':
664 		return handle_mod_rl(expr, implied, recurse_cnt, res);
665 	case '&':
666 		return handle_bitwise_AND(expr, implied, recurse_cnt, res);
667 	case '|':
668 	case '^':
669 		return use_rl_binop(expr, implied, recurse_cnt, res);
670 	case SPECIAL_RIGHTSHIFT:
671 		return handle_right_shift(expr, implied, recurse_cnt, res);
672 	case SPECIAL_LEFTSHIFT:
673 		return handle_left_shift(expr, implied, recurse_cnt, res);
674 	case '-':
675 		return handle_subtract_rl(expr, implied, recurse_cnt, res);
676 	case '/':
677 		return handle_divide_rl(expr, implied, recurse_cnt, res);
678 	}
679 
680 	if (!left_rl || !right_rl)
681 		return false;
682 
683 	if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
684 		return false;
685 	if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
686 		return false;
687 
688 	min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
689 	max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
690 
691 	*res = alloc_rl(min, max);
692 	return true;
693 
694 }
695 
handle_binop_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)696 static bool handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
697 {
698 	struct smatch_state *state;
699 	struct range_list *rl;
700 	sval_t val;
701 
702 	if (handle_known_binop(expr, &val)) {
703 		*res_sval = val;
704 		return true;
705 	}
706 	if (implied == RL_EXACT)
707 		return false;
708 
709 	if (custom_handle_variable) {
710 		rl = custom_handle_variable(expr);
711 		if (rl) {
712 			*res = rl;
713 			return true;
714 		}
715 	}
716 
717 	state = get_extra_state(expr);
718 	if (state && !is_whole_rl(estate_rl(state))) {
719 		if (implied != RL_HARD || estate_has_hard_max(state)) {
720 			*res = clone_rl(estate_rl(state));
721 			return true;
722 		}
723 	}
724 
725 	return handle_binop_rl_helper(expr, implied, recurse_cnt, res, res_sval);
726 }
727 
do_comparison(struct expression * expr)728 static int do_comparison(struct expression *expr)
729 {
730 	struct range_list *left_ranges = NULL;
731 	struct range_list *right_ranges = NULL;
732 	int poss_true, poss_false;
733 	struct symbol *type;
734 
735 	type = get_type(expr);
736 	get_absolute_rl(expr->left, &left_ranges);
737 	get_absolute_rl(expr->right, &right_ranges);
738 
739 	left_ranges = cast_rl(type, left_ranges);
740 	right_ranges = cast_rl(type, right_ranges);
741 
742 	poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
743 	poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
744 
745 	if (!poss_true && !poss_false)
746 		return 0x0;
747 	if (poss_true && !poss_false)
748 		return 0x1;
749 	if (!poss_true && poss_false)
750 		return 0x2;
751 	return 0x3;
752 }
753 
handle_comparison_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)754 static bool handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
755 {
756 	sval_t left, right;
757 	int cmp;
758 
759 	if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
760 		struct symbol *left, *right;
761 
762 		if (expr->right->type != EXPR_TYPE)
763 			return false;
764 
765 		left = get_real_base_type(expr->left->symbol);
766 		right = get_real_base_type(expr->right->symbol);
767 		if (type_bits(left) == type_bits(right) &&
768 		    type_positive_bits(left) == type_positive_bits(right))
769 			*res_sval = one;
770 		else
771 			*res_sval = zero;
772 		return true;
773 	}
774 
775 	if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
776 		struct data_range tmp_left, tmp_right;
777 
778 		tmp_left.min = left;
779 		tmp_left.max = left;
780 		tmp_right.min = right;
781 		tmp_right.max = right;
782 		if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
783 			*res_sval = one;
784 		else
785 			*res_sval = zero;
786 		return true;
787 	}
788 
789 	if (implied == RL_EXACT)
790 		return false;
791 
792 	cmp = do_comparison(expr);
793 	if (cmp == 1) {
794 		*res_sval = one;
795 		return true;
796 	}
797 	if (cmp == 2) {
798 		*res_sval = zero;
799 		return true;
800 	}
801 
802 	*res = alloc_rl(zero, one);
803 	return true;
804 }
805 
handle_logical_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)806 static bool handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
807 {
808 	sval_t left, right;
809 	int left_known = 0;
810 	int right_known = 0;
811 
812 	if (implied == RL_EXACT) {
813 		if (get_value(expr->left, &left))
814 			left_known = 1;
815 		if (get_value(expr->right, &right))
816 			right_known = 1;
817 	} else {
818 		if (get_implied_value_internal(expr->left, recurse_cnt, &left))
819 			left_known = 1;
820 		if (get_implied_value_internal(expr->right, recurse_cnt, &right))
821 			right_known = 1;
822 	}
823 
824 	switch (expr->op) {
825 	case SPECIAL_LOGICAL_OR:
826 		if (left_known && left.value)
827 			goto one;
828 		if (right_known && right.value)
829 			goto one;
830 		if (left_known && right_known)
831 			goto zero;
832 		break;
833 	case SPECIAL_LOGICAL_AND:
834 		if (left_known && right_known) {
835 			if (left.value && right.value)
836 				goto one;
837 			goto zero;
838 		}
839 		break;
840 	default:
841 		return false;
842 	}
843 
844 	if (implied == RL_EXACT)
845 		return false;
846 
847 	*res = alloc_rl(zero, one);
848 	return true;
849 
850 zero:
851 	*res_sval = zero;
852 	return true;
853 one:
854 	*res_sval = one;
855 	return true;
856 }
857 
handle_conditional_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)858 static bool handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
859 {
860 	struct expression *cond_true;
861 	struct range_list *true_rl, *false_rl;
862 	struct symbol *type;
863 	int final_pass_orig = final_pass;
864 
865 	cond_true = expr->cond_true;
866 	if (!cond_true)
867 		cond_true = expr->conditional;
868 
869 	if (known_condition_true(expr->conditional))
870 		return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
871 	if (known_condition_false(expr->conditional))
872 		return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
873 
874 	if (implied == RL_EXACT)
875 		return false;
876 
877 	if (implied_condition_true(expr->conditional))
878 		return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
879 	if (implied_condition_false(expr->conditional))
880 		return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
881 
882 	/* this becomes a problem with deeply nested conditional statements */
883 	if (fast_math_only || low_on_memory())
884 		return false;
885 
886 	type = get_type(expr);
887 
888 	__push_fake_cur_stree();
889 	final_pass = 0;
890 	__split_whole_condition(expr->conditional);
891 	true_rl = NULL;
892 	get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
893 	__push_true_states();
894 	__use_false_states();
895 	false_rl = NULL;
896 	get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
897 	__merge_true_states();
898 	__free_fake_cur_stree();
899 	final_pass = final_pass_orig;
900 
901 	if (!true_rl || !false_rl)
902 		return false;
903 	true_rl = cast_rl(type, true_rl);
904 	false_rl = cast_rl(type, false_rl);
905 
906 	*res = rl_union(true_rl, false_rl);
907 	return true;
908 }
909 
get_fuzzy_max_helper(struct expression * expr,sval_t * max)910 static bool get_fuzzy_max_helper(struct expression *expr, sval_t *max)
911 {
912 	struct smatch_state *state;
913 	sval_t sval;
914 
915 	if (get_hard_max(expr, &sval)) {
916 		*max = sval;
917 		return true;
918 	}
919 
920 	state = get_extra_state(expr);
921 	if (!state || !estate_has_fuzzy_max(state))
922 		return false;
923 	*max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
924 	return true;
925 }
926 
get_fuzzy_min_helper(struct expression * expr,sval_t * min)927 static bool get_fuzzy_min_helper(struct expression *expr, sval_t *min)
928 {
929 	struct smatch_state *state;
930 	sval_t sval;
931 
932 	state = get_extra_state(expr);
933 	if (!state || !estate_rl(state))
934 		return false;
935 
936 	sval = estate_min(state);
937 	if (sval_is_negative(sval) && sval_is_min(sval))
938 		return false;
939 
940 	if (sval_is_max(sval))
941 		return false;
942 
943 	*min = sval_cast(get_type(expr), sval);
944 	return true;
945 }
946 
get_const_value(struct expression * expr,sval_t * sval)947 int get_const_value(struct expression *expr, sval_t *sval)
948 {
949 	struct symbol *sym;
950 	sval_t right;
951 
952 	if (expr->type != EXPR_SYMBOL || !expr->symbol)
953 		return 0;
954 	sym = expr->symbol;
955 	if (!(sym->ctype.modifiers & MOD_CONST))
956 		return 0;
957 	if (get_value(sym->initializer, &right)) {
958 		*sval = sval_cast(get_type(expr), right);
959 		return 1;
960 	}
961 	return 0;
962 }
963 
var_to_absolute_rl(struct expression * expr)964 struct range_list *var_to_absolute_rl(struct expression *expr)
965 {
966 	struct smatch_state *state;
967 	struct range_list *rl;
968 
969 	state = get_extra_state(expr);
970 	if (!state || is_whole_rl(estate_rl(state))) {
971 		state = get_real_absolute_state(expr);
972 		if (state && state->data && !estate_is_whole(state))
973 			return clone_rl(estate_rl(state));
974 		if (get_mtag_rl(expr, &rl))
975 			return rl;
976 		if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
977 			return rl;
978 		return alloc_whole_rl(get_type(expr));
979 	}
980 	/* err on the side of saying things are possible */
981 	if (!estate_rl(state))
982 		return alloc_whole_rl(get_type(expr));
983 	return clone_rl(estate_rl(state));
984 }
985 
handle_variable(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)986 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
987 {
988 	struct smatch_state *state;
989 	struct range_list *rl;
990 	sval_t sval, min, max;
991 	struct symbol *type;
992 
993 	if (get_const_value(expr, &sval)) {
994 		*res_sval = sval;
995 		return true;
996 	}
997 
998 	if (implied == RL_EXACT)
999 		return false;
1000 
1001 	if (custom_handle_variable) {
1002 		rl = custom_handle_variable(expr);
1003 		if (rl) {
1004 			if (!rl_to_sval(rl, res_sval))
1005 				*res = rl;
1006 		} else {
1007 			*res = var_to_absolute_rl(expr);
1008 		}
1009 		return true;
1010 	}
1011 
1012 	if (get_mtag_sval(expr, &sval)) {
1013 		*res_sval = sval;
1014 		return true;
1015 	}
1016 
1017 	type = get_type(expr);
1018 	if (type &&
1019 	    (type->type == SYM_ARRAY ||
1020 	     type->type == SYM_FN))
1021 		return handle_address(expr, implied, recurse_cnt, res, res_sval);
1022 
1023 	/* FIXME: call rl_to_sval() on the results */
1024 
1025 	switch (implied) {
1026 	case RL_HARD:
1027 	case RL_IMPLIED:
1028 	case RL_ABSOLUTE:
1029 		state = get_extra_state(expr);
1030 		if (!state) {
1031 			if (implied == RL_HARD)
1032 				return false;
1033 			if (get_mtag_rl(expr, res))
1034 				return true;
1035 			if (get_db_type_rl(expr, res))
1036 				return true;
1037 			if (is_array(expr) && get_array_rl(expr, res))
1038 				return true;
1039 			return false;
1040 		}
1041 		if (implied == RL_HARD && !estate_has_hard_max(state))
1042 			return false;
1043 		*res = clone_rl(estate_rl(state));
1044 		return true;
1045 	case RL_REAL_ABSOLUTE: {
1046 		struct smatch_state *abs_state;
1047 
1048 		state = get_extra_state(expr);
1049 		abs_state = get_real_absolute_state(expr);
1050 
1051 		if (estate_rl(state) && estate_rl(abs_state)) {
1052 			*res = clone_rl(rl_intersection(estate_rl(state),
1053 							estate_rl(abs_state)));
1054 			return true;
1055 		} else if (estate_rl(state)) {
1056 			*res = clone_rl(estate_rl(state));
1057 			return true;
1058 		} else if (estate_is_empty(state)) {
1059 			/*
1060 			 * FIXME: we don't handle empty extra states correctly.
1061 			 *
1062 			 * The real abs rl is supposed to be filtered by the
1063 			 * extra state if there is one.  We don't bother keeping
1064 			 * the abs state in sync all the time because we know it
1065 			 * will be filtered later.
1066 			 *
1067 			 * It's not totally obvious to me how they should be
1068 			 * handled.  Perhaps we should take the whole rl and
1069 			 * filter by the imaginary states.  Perhaps we should
1070 			 * just go with the empty state.
1071 			 *
1072 			 * Anyway what we currently do is return NULL here and
1073 			 * that gets translated into the whole range in
1074 			 * get_real_absolute_rl().
1075 			 *
1076 			 */
1077 			return false;
1078 		} else if (estate_rl(abs_state)) {
1079 			*res = clone_rl(estate_rl(abs_state));
1080 			return true;
1081 		}
1082 
1083 		if (get_mtag_rl(expr, res))
1084 			return true;
1085 		if (get_db_type_rl(expr, res))
1086 			return true;
1087 		if (is_array(expr) && get_array_rl(expr, res))
1088 			return true;
1089 		return false;
1090 	}
1091 	case RL_FUZZY:
1092 		if (!get_fuzzy_min_helper(expr, &min))
1093 			min = sval_type_min(get_type(expr));
1094 		if (!get_fuzzy_max_helper(expr, &max))
1095 			return false;
1096 		/* fuzzy ranges are often inverted */
1097 		if (sval_cmp(min, max) > 0) {
1098 			sval = min;
1099 			min = max;
1100 			max = sval;
1101 		}
1102 		*res = alloc_rl(min, max);
1103 		return true;
1104 	}
1105 	return false;
1106 }
1107 
handle_sizeof(struct expression * expr)1108 static sval_t handle_sizeof(struct expression *expr)
1109 {
1110 	struct symbol *sym;
1111 	sval_t ret;
1112 
1113 	ret = sval_blank(expr);
1114 	sym = expr->cast_type;
1115 	if (!sym) {
1116 		sym = evaluate_expression(expr->cast_expression);
1117 		if (!sym) {
1118 			__silence_warnings_for_stmt = true;
1119 			sym = &int_ctype;
1120 		}
1121 #if 0
1122 		/*
1123 		 * Expressions of restricted types will possibly get
1124 		 * promoted - check that here.  I'm not sure how this works,
1125 		 * the problem is that sizeof(le16) shouldn't be promoted and
1126 		 * the original code did that...  Let's if zero this out and
1127 		 * see what breaks.
1128 		 */
1129 
1130 		if (is_restricted_type(sym)) {
1131 			if (type_bits(sym) < bits_in_int)
1132 				sym = &int_ctype;
1133 		}
1134 #endif
1135 		if (is_fouled_type(sym))
1136 			sym = &int_ctype;
1137 	}
1138 	examine_symbol_type(sym);
1139 
1140 	ret.type = size_t_ctype;
1141 	if (type_bits(sym) <= 0) /* sizeof(void) */ {
1142 		if (get_real_base_type(sym) == &void_ctype)
1143 			ret.value = 1;
1144 		else
1145 			ret.value = 0;
1146 	} else
1147 		ret.value = type_bytes(sym);
1148 
1149 	return ret;
1150 }
1151 
handle_strlen(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)1152 static bool handle_strlen(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1153 {
1154 	struct expression *arg, *tmp;
1155 	sval_t tag;
1156 	sval_t ret = { .type = &ulong_ctype };
1157 	struct range_list *rl;
1158 
1159 	arg = get_argument_from_call_expr(expr->args, 0);
1160 	if (!arg)
1161 		return false;
1162 	if (arg->type == EXPR_STRING) {
1163 		ret.value = arg->string->length - 1;
1164 		*res_sval = ret;
1165 		return true;
1166 	}
1167 	if (implied == RL_EXACT)
1168 		return false;
1169 	if (get_implied_value(arg, &tag) &&
1170 	    (tmp = fake_string_from_mtag(tag.uvalue))) {
1171 		ret.value = tmp->string->length - 1;
1172 		*res_sval = ret;
1173 		return true;
1174 	}
1175 
1176 	if (implied == RL_HARD || implied == RL_FUZZY)
1177 		return false;
1178 
1179 	if (get_implied_return(expr, &rl)) {
1180 		*res = rl;
1181 		return true;
1182 	}
1183 
1184 	return false;
1185 }
1186 
handle_builtin_constant_p(struct expression * expr,int implied,int * recurse_cnt,sval_t * res_sval)1187 static bool handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
1188 {
1189 	struct expression *arg;
1190 	struct range_list *rl;
1191 
1192 	arg = get_argument_from_call_expr(expr->args, 0);
1193 	if (get_rl_internal(arg, RL_EXACT, recurse_cnt, &rl))
1194 		*res_sval = one;
1195 	else
1196 		*res_sval = zero;
1197 	return true;
1198 }
1199 
handle__builtin_choose_expr(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)1200 static bool handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1201 {
1202 	struct expression *const_expr, *expr1, *expr2;
1203 	sval_t sval;
1204 
1205 	const_expr = get_argument_from_call_expr(expr->args, 0);
1206 	expr1 = get_argument_from_call_expr(expr->args, 1);
1207 	expr2 = get_argument_from_call_expr(expr->args, 2);
1208 
1209 	if (!get_value(const_expr, &sval) || !expr1 || !expr2)
1210 		return false;
1211 	if (sval.value)
1212 		return get_rl_sval(expr1, implied, recurse_cnt, res, res_sval);
1213 	else
1214 		return get_rl_sval(expr2, implied, recurse_cnt, res, res_sval);
1215 }
1216 
handle_call_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)1217 static bool handle_call_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1218 {
1219 	struct range_list *rl;
1220 
1221 	if (sym_name_is("__builtin_constant_p", expr->fn))
1222 		return handle_builtin_constant_p(expr, implied, recurse_cnt, res_sval);
1223 
1224 	if (sym_name_is("__builtin_choose_expr", expr->fn))
1225 		return handle__builtin_choose_expr(expr, implied, recurse_cnt, res, res_sval);
1226 
1227 	if (sym_name_is("__builtin_expect", expr->fn) ||
1228 	    sym_name_is("__builtin_bswap16", expr->fn) ||
1229 	    sym_name_is("__builtin_bswap32", expr->fn) ||
1230 	    sym_name_is("__builtin_bswap64", expr->fn)) {
1231 		struct expression *arg;
1232 
1233 		arg = get_argument_from_call_expr(expr->args, 0);
1234 		return get_rl_sval(arg, implied, recurse_cnt, res, res_sval);
1235 	}
1236 
1237 	if (sym_name_is("strlen", expr->fn))
1238 		return handle_strlen(expr, implied, recurse_cnt, res, res_sval);
1239 
1240 	if (implied == RL_EXACT || implied == RL_HARD)
1241 		return false;
1242 
1243 	if (custom_handle_variable) {
1244 		rl = custom_handle_variable(expr);
1245 		if (rl) {
1246 			*res = rl;
1247 			return true;
1248 		}
1249 	}
1250 
1251 	/* Ugh...  get_implied_return() sets *rl to NULL on failure */
1252 	if (get_implied_return(expr, &rl)) {
1253 		*res = rl;
1254 		return true;
1255 	}
1256 	rl = db_return_vals(expr);
1257 	if (rl) {
1258 		*res = rl;
1259 		return true;
1260 	}
1261 	return false;
1262 }
1263 
handle_cast(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)1264 static bool handle_cast(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1265 {
1266 	struct range_list *rl;
1267 	struct symbol *type;
1268 	sval_t sval = {};
1269 
1270 	type = get_type(expr);
1271 	if (get_rl_sval(expr->cast_expression, implied, recurse_cnt, &rl, &sval)) {
1272 		if (sval.type)
1273 			*res_sval = sval_cast(type, sval);
1274 		else
1275 			*res = cast_rl(type, rl);
1276 		return true;
1277 	}
1278 	if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) {
1279 		*res = alloc_whole_rl(type);
1280 		return true;
1281 	}
1282 	if (implied == RL_IMPLIED && type &&
1283 	    type_bits(type) > 0 && type_bits(type) < 32) {
1284 		*res = alloc_whole_rl(type);
1285 		return true;
1286 	}
1287 	return false;
1288 }
1289 
get_offset_from_down(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)1290 static bool get_offset_from_down(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1291 {
1292 	struct expression *index;
1293 	struct symbol *type = expr->in;
1294 	struct range_list *rl;
1295 	struct symbol *field;
1296 	int offset = 0;
1297 	sval_t sval = { .type = ssize_t_ctype };
1298 	sval_t tmp_sval = {};
1299 
1300 	/*
1301 	 * FIXME:  I don't really know what I'm doing here.  I wish that I
1302 	 * could just get rid of the __builtin_offset() function and use:
1303 	 * "&((struct bpf_prog *)NULL)->insns[fprog->len]" instead...
1304 	 * Anyway, I have done the minimum ammount of work to get that
1305 	 * expression to work.
1306 	 *
1307 	 */
1308 
1309 	if (expr->op != '.' || !expr->down ||
1310 	    expr->down->type != EXPR_OFFSETOF ||
1311 	    expr->down->op != '[' ||
1312 	    !expr->down->index)
1313 		return false;
1314 
1315 	index = expr->down->index;
1316 
1317 	examine_symbol_type(type);
1318 	type = get_real_base_type(type);
1319 	if (!type)
1320 		return false;
1321 	field = find_identifier(expr->ident, type->symbol_list, &offset);
1322 	if (!field)
1323 		return false;
1324 
1325 	type = get_real_base_type(field);
1326 	if (!type || type->type != SYM_ARRAY)
1327 		return false;
1328 	type = get_real_base_type(type);
1329 
1330 	if (get_implied_value_internal(index, recurse_cnt, &sval)) {
1331 		res_sval->type = ssize_t_ctype;
1332 		res_sval->value = offset + sval.value * type_bytes(type);
1333 		return true;
1334 	}
1335 
1336 	if (!get_rl_sval(index, implied, recurse_cnt, &rl, &tmp_sval))
1337 		return false;
1338 
1339 	/*
1340 	 * I'm not sure why get_rl_sval() would return an sval when
1341 	 * get_implied_value_internal() failed but it does when I
1342 	 * parse drivers/net/ethernet/mellanox/mlx5/core/en/monitor_stats.c
1343 	 *
1344 	 */
1345 	if (tmp_sval.type) {
1346 		res_sval->type = ssize_t_ctype;
1347 		res_sval->value = offset + sval.value * type_bytes(type);
1348 		return true;
1349 	}
1350 
1351 	sval.value = type_bytes(type);
1352 	rl = rl_binop(rl, '*', alloc_rl(sval, sval));
1353 	sval.value = offset;
1354 	*res = rl_binop(rl, '+', alloc_rl(sval, sval));
1355 	return true;
1356 }
1357 
get_offset_from_in(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)1358 static bool get_offset_from_in(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1359 {
1360 	struct symbol *type = get_real_base_type(expr->in);
1361 	struct symbol *field;
1362 	int offset = 0;
1363 
1364 	if (expr->op != '.' || !type || !expr->ident)
1365 		return false;
1366 
1367 	field = find_identifier(expr->ident, type->symbol_list, &offset);
1368 	if (!field)
1369 		return false;
1370 
1371 	res_sval->type = size_t_ctype;
1372 	res_sval->value = offset;
1373 
1374 	return true;
1375 }
1376 
handle_offsetof_rl(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * res_sval)1377 static bool handle_offsetof_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1378 {
1379 	if (get_offset_from_down(expr, implied, recurse_cnt, res, res_sval))
1380 		return true;
1381 
1382 	if (get_offset_from_in(expr, implied, recurse_cnt, res, res_sval))
1383 		return true;
1384 
1385 	evaluate_expression(expr);
1386 	if (expr->type == EXPR_VALUE) {
1387 		*res_sval = sval_from_val(expr, expr->value);
1388 		return true;
1389 	}
1390 	return false;
1391 }
1392 
get_rl_sval(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res,sval_t * sval_res)1393 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res)
1394 {
1395 	struct range_list *rl = (void *)-1UL;
1396 	struct symbol *type;
1397 	sval_t sval = {};
1398 
1399 	type = get_type(expr);
1400 	expr = strip_parens(expr);
1401 	if (!expr)
1402 		return false;
1403 
1404 	if (++(*recurse_cnt) >= 200)
1405 		return false;
1406 
1407 	switch(expr->type) {
1408 	case EXPR_CAST:
1409 	case EXPR_FORCE_CAST:
1410 	case EXPR_IMPLIED_CAST:
1411 		handle_cast(expr, implied, recurse_cnt, &rl, &sval);
1412 		goto out_cast;
1413 	}
1414 
1415 	expr = strip_expr(expr);
1416 	if (!expr)
1417 		return false;
1418 
1419 	switch (expr->type) {
1420 	case EXPR_VALUE:
1421 		sval = sval_from_val(expr, expr->value);
1422 		break;
1423 	case EXPR_FVALUE:
1424 		sval = sval_from_fval(expr, expr->fvalue);
1425 		break;
1426 	case EXPR_PREOP:
1427 		handle_preop_rl(expr, implied, recurse_cnt, &rl, &sval);
1428 		break;
1429 	case EXPR_POSTOP:
1430 		get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval);
1431 		break;
1432 	case EXPR_BINOP:
1433 		handle_binop_rl(expr, implied, recurse_cnt, &rl, &sval);
1434 		break;
1435 	case EXPR_COMPARE:
1436 		handle_comparison_rl(expr, implied, recurse_cnt, &rl, &sval);
1437 		break;
1438 	case EXPR_LOGICAL:
1439 		handle_logical_rl(expr, implied, recurse_cnt, &rl, &sval);
1440 		break;
1441 	case EXPR_PTRSIZEOF:
1442 	case EXPR_SIZEOF:
1443 		sval = handle_sizeof(expr);
1444 		break;
1445 	case EXPR_SELECT:
1446 	case EXPR_CONDITIONAL:
1447 		handle_conditional_rl(expr, implied, recurse_cnt, &rl, &sval);
1448 		break;
1449 	case EXPR_CALL:
1450 		handle_call_rl(expr, implied, recurse_cnt, &rl, &sval);
1451 		break;
1452 	case EXPR_STRING:
1453 		if (get_mtag_sval(expr, &sval))
1454 			break;
1455 		if (implied == RL_EXACT)
1456 			break;
1457 		rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1458 		break;
1459 	case EXPR_OFFSETOF:
1460 		handle_offsetof_rl(expr, implied, recurse_cnt, &rl, &sval);
1461 		break;
1462 	case EXPR_ALIGNOF:
1463 		evaluate_expression(expr);
1464 		if (expr->type == EXPR_VALUE)
1465 			sval = sval_from_val(expr, expr->value);
1466 		break;
1467 	default:
1468 		handle_variable(expr, implied, recurse_cnt, &rl, &sval);
1469 	}
1470 
1471 out_cast:
1472 	if (rl == (void *)-1UL)
1473 		rl = NULL;
1474 
1475 	if (sval.type || (rl && rl_to_sval(rl, &sval))) {
1476 		*sval_res = sval;
1477 		return true;
1478 	}
1479 	if (implied == RL_EXACT)
1480 		return false;
1481 
1482 	if (rl) {
1483 		*res = rl;
1484 		return true;
1485 	}
1486 	if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) {
1487 		*res = alloc_whole_rl(type);
1488 		return true;
1489 	}
1490 	return false;
1491 }
1492 
get_rl_internal(struct expression * expr,int implied,int * recurse_cnt,struct range_list ** res)1493 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
1494 {
1495 	struct range_list *rl = NULL;
1496 	sval_t sval = {};
1497 
1498 	if (!get_rl_sval(expr, implied, recurse_cnt, &rl, &sval))
1499 		return false;
1500 
1501 	if (sval.type)
1502 		*res = alloc_rl(sval, sval);
1503 	else
1504 		*res = rl;
1505 	return true;
1506 }
1507 
get_rl_helper(struct expression * expr,int implied,struct range_list ** res)1508 static bool get_rl_helper(struct expression *expr, int implied, struct range_list **res)
1509 {
1510 	struct range_list *rl = NULL;
1511 	sval_t sval = {};
1512 	int recurse_cnt = 0;
1513 
1514 	if (get_value(expr, &sval)) {
1515 		*res = alloc_rl(sval, sval);
1516 		return true;
1517 	}
1518 
1519 	if (!get_rl_sval(expr, implied, &recurse_cnt, &rl, &sval))
1520 		return false;
1521 
1522 	if (sval.type)
1523 		*res = alloc_rl(sval, sval);
1524 	else
1525 		*res = rl;
1526 	return true;
1527 }
1528 
1529 struct {
1530 	struct expression *expr;
1531 	sval_t sval;
1532 } cached_results[24];
1533 static int cache_idx;
1534 
clear_math_cache(void)1535 void clear_math_cache(void)
1536 {
1537 	memset(cached_results, 0, sizeof(cached_results));
1538 }
1539 
set_fast_math_only(void)1540 void set_fast_math_only(void)
1541 {
1542 	fast_math_only++;
1543 }
1544 
clear_fast_math_only(void)1545 void clear_fast_math_only(void)
1546 {
1547 	fast_math_only--;
1548 }
1549 
1550 /*
1551  * Don't cache EXPR_VALUE because values are fast already.
1552  *
1553  */
get_value_literal(struct expression * expr,sval_t * res_sval)1554 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1555 {
1556 	struct expression *tmp;
1557 	int recurse_cnt = 0;
1558 
1559 	tmp = strip_expr(expr);
1560 	if (!tmp || tmp->type != EXPR_VALUE)
1561 		return false;
1562 
1563 	return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1564 }
1565 
1566 /* returns 1 if it can get a value literal or else returns 0 */
get_value(struct expression * expr,sval_t * res_sval)1567 int get_value(struct expression *expr, sval_t *res_sval)
1568 {
1569 	struct range_list *(*orig_custom_fn)(struct expression *expr);
1570 	int recurse_cnt = 0;
1571 	sval_t sval = {};
1572 	int i;
1573 
1574 	if (get_value_literal(expr, res_sval))
1575 		return 1;
1576 
1577 	/*
1578 	 * This only handles RL_EXACT because other expr statements can be
1579 	 * different at different points.  Like the list iterator, for example.
1580 	 */
1581 	for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1582 		if (expr == cached_results[i].expr) {
1583 			if (cached_results[i].sval.type) {
1584 				*res_sval = cached_results[i].sval;
1585 				return true;
1586 			}
1587 			return false;
1588 		}
1589 	}
1590 
1591 	orig_custom_fn = custom_handle_variable;
1592 	custom_handle_variable = NULL;
1593 	get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, &sval);
1594 
1595 	custom_handle_variable = orig_custom_fn;
1596 
1597 	cached_results[cache_idx].expr = expr;
1598 	cached_results[cache_idx].sval = sval;
1599 	cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1600 
1601 	if (!sval.type)
1602 		return 0;
1603 
1604 	*res_sval = sval;
1605 	return 1;
1606 }
1607 
get_implied_value_internal(struct expression * expr,int * recurse_cnt,sval_t * res_sval)1608 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval)
1609 {
1610 	struct range_list *rl;
1611 
1612 	res_sval->type = NULL;
1613 
1614 	if (!get_rl_sval(expr, RL_IMPLIED, recurse_cnt, &rl, res_sval))
1615 		return false;
1616 	if (!res_sval->type && !rl_to_sval(rl, res_sval))
1617 		return false;
1618 	return true;
1619 }
1620 
get_implied_value(struct expression * expr,sval_t * sval)1621 int get_implied_value(struct expression *expr, sval_t *sval)
1622 {
1623 	struct range_list *rl;
1624 
1625 	if (!get_rl_helper(expr, RL_IMPLIED, &rl) ||
1626 	    !rl_to_sval(rl, sval))
1627 		return 0;
1628 	return 1;
1629 }
1630 
get_implied_value_fast(struct expression * expr,sval_t * sval)1631 int get_implied_value_fast(struct expression *expr, sval_t *sval)
1632 {
1633 	struct range_list *rl;
1634 	static int recurse;
1635 	int ret = 0;
1636 
1637 	if (recurse)
1638 		return 0;
1639 
1640 	recurse = 1;
1641 	set_fast_math_only();
1642 	if (get_rl_helper(expr, RL_IMPLIED, &rl) &&
1643 	    rl_to_sval(rl, sval))
1644 		ret = 1;
1645 	clear_fast_math_only();
1646 	recurse = 0;
1647 
1648 	return ret;
1649 }
1650 
get_implied_min(struct expression * expr,sval_t * sval)1651 int get_implied_min(struct expression *expr, sval_t *sval)
1652 {
1653 	struct range_list *rl;
1654 
1655 	if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1656 		return 0;
1657 	*sval = rl_min(rl);
1658 	return 1;
1659 }
1660 
get_implied_max(struct expression * expr,sval_t * sval)1661 int get_implied_max(struct expression *expr, sval_t *sval)
1662 {
1663 	struct range_list *rl;
1664 
1665 	if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1666 		return 0;
1667 	*sval = rl_max(rl);
1668 	return 1;
1669 }
1670 
get_implied_rl(struct expression * expr,struct range_list ** rl)1671 int get_implied_rl(struct expression *expr, struct range_list **rl)
1672 {
1673 	if (!get_rl_helper(expr, RL_IMPLIED, rl) || !*rl)
1674 		return 0;
1675 	return 1;
1676 }
1677 
get_absolute_rl_internal(struct expression * expr,struct range_list ** rl,int * recurse_cnt)1678 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1679 {
1680 	*rl = NULL;
1681 	get_rl_internal(expr, RL_ABSOLUTE, recurse_cnt, rl);
1682 	if (!*rl)
1683 		*rl = alloc_whole_rl(get_type(expr));
1684 	return 1;
1685 }
1686 
get_absolute_rl(struct expression * expr,struct range_list ** rl)1687 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1688 {
1689 	*rl = NULL;
1690 	 get_rl_helper(expr, RL_ABSOLUTE, rl);
1691 	if (!*rl)
1692 		*rl = alloc_whole_rl(get_type(expr));
1693 	return 1;
1694 }
1695 
get_real_absolute_rl(struct expression * expr,struct range_list ** rl)1696 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1697 {
1698 	*rl = NULL;
1699 	get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1700 	if (!*rl)
1701 		*rl = alloc_whole_rl(get_type(expr));
1702 	return 1;
1703 }
1704 
custom_get_absolute_rl(struct expression * expr,struct range_list * (* fn)(struct expression * expr),struct range_list ** rl)1705 int custom_get_absolute_rl(struct expression *expr,
1706 			   struct range_list *(*fn)(struct expression *expr),
1707 			   struct range_list **rl)
1708 {
1709 	int ret;
1710 
1711 	*rl = NULL;
1712 	custom_handle_variable = fn;
1713 	ret = get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1714 	custom_handle_variable = NULL;
1715 	return ret;
1716 }
1717 
get_implied_rl_var_sym(const char * var,struct symbol * sym,struct range_list ** rl)1718 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1719 {
1720 	struct smatch_state *state;
1721 
1722 	state = get_state(SMATCH_EXTRA, var, sym);
1723 	*rl = estate_rl(state);
1724 	if (*rl)
1725 		return 1;
1726 	return 0;
1727 }
1728 
get_hard_max(struct expression * expr,sval_t * sval)1729 int get_hard_max(struct expression *expr, sval_t *sval)
1730 {
1731 	struct range_list *rl;
1732 
1733 	if (!get_rl_helper(expr, RL_HARD, &rl) || !rl)
1734 		return 0;
1735 	*sval = rl_max(rl);
1736 	return 1;
1737 }
1738 
get_fuzzy_min(struct expression * expr,sval_t * sval)1739 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1740 {
1741 	struct range_list *rl;
1742 	sval_t tmp;
1743 
1744 	if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1745 		return 0;
1746 	tmp = rl_min(rl);
1747 	if (sval_is_negative(tmp) && sval_is_min(tmp))
1748 		return 0;
1749 	*sval = tmp;
1750 	return 1;
1751 }
1752 
get_fuzzy_max(struct expression * expr,sval_t * sval)1753 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1754 {
1755 	struct range_list *rl;
1756 	sval_t max;
1757 
1758 	if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1759 		return 0;
1760 	max = rl_max(rl);
1761 	if (max.uvalue > INT_MAX - 10000)
1762 		return 0;
1763 	*sval = max;
1764 	return 1;
1765 }
1766 
get_absolute_min(struct expression * expr,sval_t * sval)1767 int get_absolute_min(struct expression *expr, sval_t *sval)
1768 {
1769 	struct range_list *rl;
1770 	struct symbol *type;
1771 
1772 	type = get_type(expr);
1773 	if (!type)
1774 		type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1775 	rl = NULL;
1776 	get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1777 	if (rl)
1778 		*sval = rl_min(rl);
1779 	else
1780 		*sval = sval_type_min(type);
1781 
1782 	if (sval_cmp(*sval, sval_type_min(type)) < 0)
1783 		*sval = sval_type_min(type);
1784 	return 1;
1785 }
1786 
get_absolute_max(struct expression * expr,sval_t * sval)1787 int get_absolute_max(struct expression *expr, sval_t *sval)
1788 {
1789 	struct range_list *rl;
1790 	struct symbol *type;
1791 
1792 	type = get_type(expr);
1793 	if (!type)
1794 		type = &llong_ctype;
1795 	rl = NULL;
1796 	get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1797 	if (rl)
1798 		*sval = rl_max(rl);
1799 	else
1800 		*sval = sval_type_max(type);
1801 
1802 	if (sval_cmp(sval_type_max(type), *sval) < 0)
1803 		*sval = sval_type_max(type);
1804 	return 1;
1805 }
1806 
known_condition_true(struct expression * expr)1807 int known_condition_true(struct expression *expr)
1808 {
1809 	sval_t tmp;
1810 
1811 	if (!expr)
1812 		return 0;
1813 
1814 	if (__inline_fn && get_param_num(expr) >= 0) {
1815 		if (get_implied_value(expr, &tmp) && tmp.value)
1816 			return 1;
1817 		return 0;
1818 	}
1819 
1820 	if (get_value(expr, &tmp) && tmp.value)
1821 		return 1;
1822 
1823 	return 0;
1824 }
1825 
known_condition_false(struct expression * expr)1826 int known_condition_false(struct expression *expr)
1827 {
1828 	sval_t tmp;
1829 
1830 	if (!expr)
1831 		return 0;
1832 
1833 	if (__inline_fn && get_param_num(expr) >= 0) {
1834 		if (get_implied_value(expr, &tmp) && tmp.value == 0)
1835 			return 1;
1836 		return 0;
1837 	}
1838 
1839 	if (expr_is_zero(expr))
1840 		return 1;
1841 
1842 	return 0;
1843 }
1844 
implied_condition_true(struct expression * expr)1845 int implied_condition_true(struct expression *expr)
1846 {
1847 	sval_t tmp;
1848 
1849 	if (!expr)
1850 		return 0;
1851 
1852 	if (known_condition_true(expr))
1853 		return 1;
1854 	if (get_implied_value(expr, &tmp) && tmp.value)
1855 		return 1;
1856 
1857 	if (expr->type == EXPR_POSTOP)
1858 		return implied_condition_true(expr->unop);
1859 
1860 	if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1861 		return implied_not_equal(expr->unop, 1);
1862 	if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1863 		return implied_not_equal(expr->unop, -1);
1864 
1865 	expr = strip_expr(expr);
1866 	switch (expr->type) {
1867 	case EXPR_COMPARE:
1868 		if (do_comparison(expr) == 1)
1869 			return 1;
1870 		break;
1871 	case EXPR_PREOP:
1872 		if (expr->op == '!') {
1873 			if (implied_condition_false(expr->unop))
1874 				return 1;
1875 			break;
1876 		}
1877 		break;
1878 	default:
1879 		if (implied_not_equal(expr, 0) == 1)
1880 			return 1;
1881 		break;
1882 	}
1883 	return 0;
1884 }
1885 
implied_condition_false(struct expression * expr)1886 int implied_condition_false(struct expression *expr)
1887 {
1888 	struct expression *tmp;
1889 	sval_t sval;
1890 
1891 	if (!expr)
1892 		return 0;
1893 
1894 	if (known_condition_false(expr))
1895 		return 1;
1896 
1897 	switch (expr->type) {
1898 	case EXPR_COMPARE:
1899 		if (do_comparison(expr) == 2)
1900 			return 1;
1901 	case EXPR_PREOP:
1902 		if (expr->op == '!') {
1903 			if (implied_condition_true(expr->unop))
1904 				return 1;
1905 			break;
1906 		}
1907 		tmp = strip_expr(expr);
1908 		if (tmp != expr)
1909 			return implied_condition_false(tmp);
1910 		break;
1911 	default:
1912 		if (get_implied_value(expr, &sval) && sval.value == 0)
1913 			return 1;
1914 		break;
1915 	}
1916 	return 0;
1917 }
1918 
1919 
1920