?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
db/fixup_kernel.sh: fix clear_user() handling
[smatch.git] / smatch_math.c
blob26515861850907d572bd22338b23d1aae5d47996
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 (is_fake_call(expr))
1400 return false;
1401
1402 if (sym_name_is("__builtin_constant_p", expr->fn))
1403 return handle_builtin_constant_p(expr, implied, recurse_cnt, res_sval);
1404
1405 if (sym_name_is("__builtin_choose_expr", expr->fn))
1406 return handle__builtin_choose_expr(expr, implied, recurse_cnt, res, res_sval);
1407
1408 if (sym_name_is("__builtin_expect", expr->fn) ||
1409 sym_name_is("__builtin_bswap16", expr->fn) ||
1410 sym_name_is("__builtin_bswap32", expr->fn) ||
1411 sym_name_is("__builtin_bswap64", expr->fn)) {
1412 struct expression *arg;
1413
1414 arg = get_argument_from_call_expr(expr->args, 0);
1415 return get_rl_sval(arg, implied, recurse_cnt, res, res_sval);
1416 }
1417
1418 if (sym_name_is("__builtin_ffs", expr->fn) ||
1419 sym_name_is("__builtin_ffsl", expr->fn) ||
1420 sym_name_is("__builtin_ffsll", expr->fn) ||
1421 sym_name_is("__ffs", expr->fn))
1422 return handle_ffs(expr, implied, recurse_cnt, res, res_sval);
1423
1424 if (is_strlen(expr))
1425 return handle_strlen(expr, implied, recurse_cnt, res, res_sval);
1426
1427 if (implied == RL_EXACT || implied == RL_HARD)
1428 return false;
1429
1430 if (custom_handle_variable) {
1431 rl = custom_handle_variable(expr);
1432 if (rl) {
1433 *res = rl;
1434 return true;
1435 }
1436 }
1437
1438 /* Ugh... get_implied_return() sets *rl to NULL on failure */
1439 if (get_implied_return(expr, &rl)) {
1440 *res = rl;
1441 return true;
1442 }
1443 rl = db_return_vals(expr);
1444 if (rl) {
1445 *res = rl;
1446 return true;
1447 }
1448 return false;
1449 }
1450
1451 static bool handle_cast(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1452 {
1453 struct range_list *rl;
1454 struct symbol *type;
1455 sval_t sval = {};
1456
1457 type = get_type(expr);
1458 if (get_rl_sval(expr->cast_expression, implied, recurse_cnt, &rl, &sval)) {
1459 if (sval.type)
1460 *res_sval = sval_cast(type, sval);
1461 else
1462 *res = cast_rl(type, rl);
1463 return true;
1464 }
1465 if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) {
1466 *res = alloc_whole_rl(type);
1467 return true;
1468 }
1469 if (implied == RL_IMPLIED && type &&
1470 type_bits(type) > 0 && type_bits(type) < 32) {
1471 *res = alloc_whole_rl(type);
1472 return true;
1473 }
1474 return false;
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 struct expression *down = expr->down;
1480 struct range_list *offset_rl = NULL, *down_rl = NULL;
1481 sval_t sval = { .type = ssize_t_ctype };
1482 struct symbol *type;
1483
1484 type = get_real_base_type(expr->in);
1485 if (!type)
1486 return false;
1487
1488 if (expr->op == '.') {
1489 struct symbol *field;
1490 int offset = 0;
1491
1492 field = find_identifier(expr->ident, type->symbol_list, &offset);
1493 if (!field)
1494 return false;
1495
1496 sval.value = offset;
1497 offset_rl = alloc_rl(sval, sval);
1498 type = field;
1499 } else {
1500 if (!expr->index) {
1501 sval.value = 0;
1502 offset_rl = alloc_rl(sval, sval);
1503 } else {
1504 struct range_list *idx_rl = NULL, *bytes_rl;
1505
1506 if (get_rl_internal(expr->index, implied, recurse_cnt, &idx_rl))
1507 return false;
1508
1509 sval.value = type_bytes(type);
1510 if (sval.value <= 0)
1511 return false;
1512 bytes_rl = alloc_rl(sval, sval);
1513
1514 offset_rl = rl_binop(idx_rl, '*', bytes_rl);
1515 }
1516 }
1517
1518 if (down) {
1519 if (down->type == EXPR_OFFSETOF && !down->in)
1520 down->in = type;
1521 if (!get_rl_internal(down, implied, recurse_cnt, &down_rl))
1522 return false;
1523
1524 *res = rl_binop(offset_rl, '+', down_rl);
1525 } else {
1526 *res = offset_rl;
1527 }
1528
1529 return true;
1530 }
1531
1532 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res)
1533 {
1534 struct range_list *rl = (void *)-1UL;
1535 struct symbol *type;
1536 sval_t sval = {};
1537
1538 type = get_type(expr);
1539 expr = strip_parens(expr);
1540 if (!expr)
1541 return false;
1542
1543 if (++(*recurse_cnt) >= 200)
1544 return false;
1545
1546 switch(expr->type) {
1547 case EXPR_CAST:
1548 case EXPR_FORCE_CAST:
1549 case EXPR_IMPLIED_CAST:
1550 handle_cast(expr, implied, recurse_cnt, &rl, &sval);
1551 goto out_cast;
1552 }
1553
1554 expr = strip_expr(expr);
1555 if (!expr)
1556 return false;
1557
1558 switch (expr->type) {
1559 case EXPR_VALUE:
1560 sval = sval_from_val(expr, expr->value);
1561 break;
1562 case EXPR_FVALUE:
1563 sval = sval_from_fval(expr, expr->fvalue);
1564 break;
1565 case EXPR_PREOP:
1566 handle_preop_rl(expr, implied, recurse_cnt, &rl, &sval);
1567 break;
1568 case EXPR_POSTOP:
1569 get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval);
1570 break;
1571 case EXPR_BINOP:
1572 handle_binop_rl(expr, implied, recurse_cnt, &rl, &sval);
1573 break;
1574 case EXPR_COMPARE:
1575 handle_comparison_rl(expr, implied, recurse_cnt, &rl, &sval);
1576 break;
1577 case EXPR_LOGICAL:
1578 handle_logical_rl(expr, implied, recurse_cnt, &rl, &sval);
1579 break;
1580 case EXPR_PTRSIZEOF:
1581 case EXPR_SIZEOF:
1582 sval = handle_sizeof(expr);
1583 break;
1584 case EXPR_SELECT:
1585 case EXPR_CONDITIONAL:
1586 handle_conditional_rl(expr, implied, recurse_cnt, &rl, &sval);
1587 break;
1588 case EXPR_CALL:
1589 handle_call_rl(expr, implied, recurse_cnt, &rl, &sval);
1590 break;
1591 case EXPR_STRING:
1592 if (get_mtag_sval(expr, &sval))
1593 break;
1594 if (implied == RL_EXACT)
1595 break;
1596 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1597 break;
1598 case EXPR_OFFSETOF:
1599 handle_offsetof_rl(expr, implied, recurse_cnt, &rl, &sval);
1600 break;
1601 case EXPR_ALIGNOF:
1602 evaluate_expression(expr);
1603 if (expr->type == EXPR_VALUE)
1604 sval = sval_from_val(expr, expr->value);
1605 break;
1606 default:
1607 handle_variable(expr, implied, recurse_cnt, &rl, &sval);
1608 }
1609
1610 out_cast:
1611 if (rl == (void *)-1UL)
1612 rl = NULL;
1613
1614 if (sval.type || (rl && rl_to_sval(rl, &sval))) {
1615 *sval_res = sval;
1616 return true;
1617 }
1618 if (implied == RL_EXACT)
1619 return false;
1620
1621 if (rl) {
1622 *res = rl;
1623 return true;
1624 }
1625 if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) &&
1626 !custom_handle_variable) {
1627 *res = alloc_whole_rl(type);
1628 return true;
1629 }
1630 return false;
1631 }
1632
1633 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
1634 {
1635 struct range_list *rl = NULL;
1636 sval_t sval = {};
1637
1638 if (!get_rl_sval(expr, implied, recurse_cnt, &rl, &sval))
1639 return false;
1640
1641 if (sval.type)
1642 *res = alloc_rl(sval, sval);
1643 else
1644 *res = rl;
1645 return true;
1646 }
1647
1648 static bool get_rl_helper(struct expression *expr, int implied, struct range_list **res)
1649 {
1650 struct range_list *rl = NULL;
1651 sval_t sval = {};
1652 int recurse_cnt = 0;
1653
1654 if (get_value(expr, &sval)) {
1655 if (implied == RL_HARD) {
1656 if (sval.uvalue == INT_MAX ||
1657 sval.uvalue == UINT_MAX ||
1658 sval.uvalue == LONG_MAX ||
1659 sval.uvalue == ULONG_MAX)
1660 return false;
1661 }
1662 *res = alloc_rl(sval, sval);
1663 return true;
1664 }
1665
1666 if (!get_rl_sval(expr, implied, &recurse_cnt, &rl, &sval))
1667 return false;
1668
1669 if (sval.type)
1670 *res = alloc_rl(sval, sval);
1671 else
1672 *res = rl;
1673 return true;
1674 }
1675
1676 static struct {
1677 struct expression *expr;
1678 sval_t sval;
1679 } cached_results[24];
1680 static int cache_idx;
1681
1682 void clear_math_cache(void)
1683 {
1684 memset(cached_results, 0, sizeof(cached_results));
1685 }
1686
1687 void set_fast_math_only(void)
1688 {
1689 fast_math_only++;
1690 }
1691
1692 void clear_fast_math_only(void)
1693 {
1694 fast_math_only--;
1695 }
1696
1697 /*
1698 * Don't cache EXPR_VALUE because values are fast already.
1699 *
1700 */
1701 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1702 {
1703 struct expression *tmp;
1704 int recurse_cnt = 0;
1705
1706 tmp = strip_expr(expr);
1707 if (!tmp || tmp->type != EXPR_VALUE)
1708 return false;
1709
1710 return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1711 }
1712
1713 /* returns 1 if it can get a value literal or else returns 0 */
1714 int get_value(struct expression *expr, sval_t *res_sval)
1715 {
1716 struct range_list *(*orig_custom_fn)(struct expression *expr);
1717 int recurse_cnt = 0;
1718 sval_t sval = {};
1719 int i;
1720
1721 if (get_value_literal(expr, res_sval))
1722 return 1;
1723
1724 /*
1725 * This only handles RL_EXACT because other expr statements can be
1726 * different at different points. Like the list iterator, for example.
1727 */
1728 for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1729 if (expr == cached_results[i].expr) {
1730 if (cached_results[i].sval.type) {
1731 *res_sval = cached_results[i].sval;
1732 return true;
1733 }
1734 return false;
1735 }
1736 }
1737
1738 orig_custom_fn = custom_handle_variable;
1739 custom_handle_variable = NULL;
1740 get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, &sval);
1741
1742 custom_handle_variable = orig_custom_fn;
1743
1744 cached_results[cache_idx].expr = expr;
1745 cached_results[cache_idx].sval = sval;
1746 cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1747
1748 if (!sval.type)
1749 return 0;
1750
1751 *res_sval = sval;
1752 return 1;
1753 }
1754
1755 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval)
1756 {
1757 struct range_list *rl;
1758
1759 res_sval->type = NULL;
1760
1761 if (!get_rl_sval(expr, RL_IMPLIED, recurse_cnt, &rl, res_sval))
1762 return false;
1763 if (!res_sval->type && !rl_to_sval(rl, res_sval))
1764 return false;
1765 return true;
1766 }
1767
1768 int get_implied_value(struct expression *expr, sval_t *sval)
1769 {
1770 struct range_list *rl;
1771
1772 if (!get_rl_helper(expr, RL_IMPLIED, &rl) ||
1773 !rl_to_sval(rl, sval))
1774 return 0;
1775 return 1;
1776 }
1777
1778 int get_implied_value_fast(struct expression *expr, sval_t *sval)
1779 {
1780 struct range_list *rl;
1781 static int recurse;
1782 int ret = 0;
1783
1784 if (recurse)
1785 return 0;
1786
1787 recurse = 1;
1788 set_fast_math_only();
1789 if (get_rl_helper(expr, RL_IMPLIED, &rl) &&
1790 rl_to_sval(rl, sval))
1791 ret = 1;
1792 clear_fast_math_only();
1793 recurse = 0;
1794
1795 return ret;
1796 }
1797
1798 int get_implied_min(struct expression *expr, sval_t *sval)
1799 {
1800 struct range_list *rl;
1801
1802 if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1803 return 0;
1804 *sval = rl_min(rl);
1805 return 1;
1806 }
1807
1808 int get_implied_max(struct expression *expr, sval_t *sval)
1809 {
1810 struct range_list *rl;
1811
1812 if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1813 return 0;
1814 *sval = rl_max(rl);
1815 return 1;
1816 }
1817
1818 int get_implied_rl(struct expression *expr, struct range_list **rl)
1819 {
1820 if (!get_rl_helper(expr, RL_IMPLIED, rl) || !*rl)
1821 return 0;
1822 return 1;
1823 }
1824
1825 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1826 {
1827 *rl = NULL;
1828 get_rl_internal(expr, RL_ABSOLUTE, recurse_cnt, rl);
1829 if (!*rl)
1830 *rl = alloc_whole_rl(get_type(expr));
1831 return 1;
1832 }
1833
1834 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1835 {
1836 *rl = NULL;
1837 get_rl_helper(expr, RL_ABSOLUTE, rl);
1838 if (!*rl)
1839 *rl = alloc_whole_rl(get_type(expr));
1840 return 1;
1841 }
1842
1843 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1844 {
1845 *rl = NULL;
1846 get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1847 if (!*rl)
1848 *rl = alloc_whole_rl(get_type(expr));
1849 return 1;
1850 }
1851
1852 int custom_get_absolute_rl(struct expression *expr,
1853 struct range_list *(*fn)(struct expression *expr),
1854 struct range_list **rl)
1855 {
1856 struct range_list *(*orig_fn)(struct expression *expr);
1857 int ret;
1858
1859 *rl = NULL;
1860 orig_fn = custom_handle_variable;
1861 custom_handle_variable = fn;
1862 ret = get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1863 custom_handle_variable = orig_fn;
1864 return ret;
1865 }
1866
1867 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1868 {
1869 struct smatch_state *state;
1870
1871 state = get_state(SMATCH_EXTRA, var, sym);
1872 *rl = estate_rl(state);
1873 if (*rl)
1874 return 1;
1875 return 0;
1876 }
1877
1878 int get_hard_max(struct expression *expr, sval_t *sval)
1879 {
1880 struct range_list *rl;
1881
1882 if (!get_rl_helper(expr, RL_HARD, &rl) || !rl)
1883 return 0;
1884 *sval = rl_max(rl);
1885 return 1;
1886 }
1887
1888 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1889 {
1890 struct range_list *rl;
1891 sval_t tmp;
1892
1893 if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1894 return 0;
1895 tmp = rl_min(rl);
1896 if (sval_is_negative(tmp) && sval_is_min(tmp))
1897 return 0;
1898 *sval = tmp;
1899 return 1;
1900 }
1901
1902 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1903 {
1904 struct range_list *rl;
1905 sval_t max;
1906
1907 if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1908 return 0;
1909 max = rl_max(rl);
1910 if (max.uvalue > INT_MAX - 10000)
1911 return 0;
1912 *sval = max;
1913 return 1;
1914 }
1915
1916 int get_absolute_min(struct expression *expr, sval_t *sval)
1917 {
1918 struct range_list *rl;
1919 struct symbol *type;
1920
1921 type = get_type(expr);
1922 if (!type)
1923 type = &llong_ctype; // FIXME: this is wrong but places assume get type can't fail.
1924 rl = NULL;
1925 get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1926 if (rl)
1927 *sval = rl_min(rl);
1928 else
1929 *sval = sval_type_min(type);
1930
1931 if (sval_cmp(*sval, sval_type_min(type)) < 0)
1932 *sval = sval_type_min(type);
1933 return 1;
1934 }
1935
1936 int get_absolute_max(struct expression *expr, sval_t *sval)
1937 {
1938 struct range_list *rl;
1939 struct symbol *type;
1940
1941 type = get_type(expr);
1942 if (!type)
1943 type = &llong_ctype;
1944 rl = NULL;
1945 get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1946 if (rl)
1947 *sval = rl_max(rl);
1948 else
1949 *sval = sval_type_max(type);
1950
1951 if (sval_cmp(sval_type_max(type), *sval) < 0)
1952 *sval = sval_type_max(type);
1953 return 1;
1954 }
1955
1956 int known_condition_true(struct expression *expr)
1957 {
1958 sval_t tmp;
1959
1960 if (!expr)
1961 return 0;
1962
1963 if (__inline_fn && get_param_num(expr) >= 0) {
1964 if (get_implied_value(expr, &tmp) && tmp.value)
1965 return 1;
1966 return 0;
1967 }
1968
1969 if (get_value(expr, &tmp) && tmp.value)
1970 return 1;
1971
1972 return 0;
1973 }
1974
1975 int known_condition_false(struct expression *expr)
1976 {
1977 sval_t tmp;
1978
1979 if (!expr)
1980 return 0;
1981
1982 if (__inline_fn && get_param_num(expr) >= 0) {
1983 if (get_implied_value(expr, &tmp) && tmp.value == 0)
1984 return 1;
1985 return 0;
1986 }
1987
1988 if (expr_is_zero(expr))
1989 return 1;
1990
1991 return 0;
1992 }
1993
1994 int implied_condition_true(struct expression *expr)
1995 {
1996 sval_t tmp;
1997
1998 if (!expr)
1999 return 0;
2000
2001 if (known_condition_true(expr))
2002 return 1;
2003 if (get_implied_value(expr, &tmp) && tmp.value)
2004 return 1;
2005
2006 if (expr->type == EXPR_POSTOP)
2007 return implied_condition_true(expr->unop);
2008
2009 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
2010 return implied_not_equal(expr->unop, 1);
2011 if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
2012 return implied_not_equal(expr->unop, -1);
2013
2014 expr = strip_expr(expr);
2015 switch (expr->type) {
2016 case EXPR_COMPARE:
2017 if (do_comparison(expr) == 1)
2018 return 1;
2019 break;
2020 case EXPR_PREOP:
2021 if (expr->op == '!') {
2022 if (implied_condition_false(expr->unop))
2023 return 1;
2024 break;
2025 }
2026 break;
2027 default:
2028 if (implied_not_equal(expr, 0) == 1)
2029 return 1;
2030 break;
2031 }
2032 return 0;
2033 }
2034
2035 int implied_condition_false(struct expression *expr)
2036 {
2037 struct expression *tmp;
2038 sval_t sval;
2039
2040 if (!expr)
2041 return 0;
2042
2043 if (known_condition_false(expr))
2044 return 1;
2045
2046 switch (expr->type) {
2047 case EXPR_COMPARE:
2048 if (do_comparison(expr) == 2)
2049 return 1;
2050 case EXPR_PREOP:
2051 if (expr->op == '!') {
2052 if (implied_condition_true(expr->unop))
2053 return 1;
2054 break;
2055 }
2056 tmp = strip_expr(expr);
2057 if (tmp != expr)
2058 return implied_condition_false(tmp);
2059 break;
2060 default:
2061 if (get_implied_value(expr, &sval) && sval.value == 0)
2062 return 1;
2063 break;
2064 }
2065 return 0;
2066 }
2067
2068
Static analysis for C