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