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