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