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