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