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