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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
1535 void clear_math_cache(void)
1536 {
1537 memset(cached_results, 0, sizeof(cached_results));
1538 }
1539
1540 void set_fast_math_only(void)
1541 {
1542 fast_math_only++;
1543 }
1544
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 */
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 */
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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