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