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