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