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