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