1 /* 2 * Copyright (C) 2012 Oracle. 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 /* 19 * The point here is to store the relationships between two variables. 20 * Ie: y > x. 21 * To do that we create a state with the two variables in alphabetical order: 22 * ->name = "x vs y" and the state would be "<". On the false path the state 23 * would be ">=". 24 * 25 * Part of the trick of it is that if x or y is modified then we need to reset 26 * the state. We need to keep a list of all the states which depend on x and 27 * all the states which depend on y. The link_id code handles this. 28 * 29 */ 30 31 #include "smatch.h" 32 #include "smatch_extra.h" 33 #include "smatch_slist.h" 34 35 static int compare_id; 36 static int link_id; 37 static int inc_dec_id; 38 static int inc_dec_link_id; 39 40 static void add_comparison(struct expression *left, int comparison, struct expression *right); 41 42 /* for handling for loops */ 43 STATE(start); 44 STATE(incremented); 45 46 ALLOCATOR(compare_data, "compare data"); 47 48 static struct symbol *vsl_to_sym(struct var_sym_list *vsl) 49 { 50 struct var_sym *vs; 51 52 if (!vsl) 53 return NULL; 54 if (ptr_list_size((struct ptr_list *)vsl) != 1) 55 return NULL; 56 vs = first_ptr_list((struct ptr_list *)vsl); 57 return vs->sym; 58 } 59 60 static const char *show_comparison(int comparison) 61 { 62 if (comparison == IMPOSSIBLE_COMPARISON) 63 return "impossible"; 64 if (comparison == UNKNOWN_COMPARISON) 65 return "unknown"; 66 return show_special(comparison); 67 } 68 69 struct smatch_state *alloc_compare_state( 70 struct expression *left, 71 const char *left_var, struct var_sym_list *left_vsl, 72 int comparison, 73 struct expression *right, 74 const char *right_var, struct var_sym_list *right_vsl) 75 { 76 struct smatch_state *state; 77 struct compare_data *data; 78 79 state = __alloc_smatch_state(0); 80 state->name = alloc_sname(show_comparison(comparison)); 81 data = __alloc_compare_data(0); 82 data->left = left; 83 data->left_var = alloc_sname(left_var); 84 data->left_vsl = clone_var_sym_list(left_vsl); 85 data->comparison = comparison; 86 data->right = right; 87 data->right_var = alloc_sname(right_var); 88 data->right_vsl = clone_var_sym_list(right_vsl); 89 state->data = data; 90 return state; 91 } 92 93 int state_to_comparison(struct smatch_state *state) 94 { 95 if (!state || !state->data) 96 return UNKNOWN_COMPARISON; 97 return ((struct compare_data *)state->data)->comparison; 98 } 99 100 /* 101 * flip_comparison() reverses the op left and right. So "x >= y" becomes "y <= x". 102 */ 103 int flip_comparison(int op) 104 { 105 switch (op) { 106 case UNKNOWN_COMPARISON: 107 return UNKNOWN_COMPARISON; 108 case '<': 109 return '>'; 110 case SPECIAL_UNSIGNED_LT: 111 return SPECIAL_UNSIGNED_GT; 112 case SPECIAL_LTE: 113 return SPECIAL_GTE; 114 case SPECIAL_UNSIGNED_LTE: 115 return SPECIAL_UNSIGNED_GTE; 116 case SPECIAL_EQUAL: 117 return SPECIAL_EQUAL; 118 case SPECIAL_NOTEQUAL: 119 return SPECIAL_NOTEQUAL; 120 case SPECIAL_GTE: 121 return SPECIAL_LTE; 122 case SPECIAL_UNSIGNED_GTE: 123 return SPECIAL_UNSIGNED_LTE; 124 case '>': 125 return '<'; 126 case SPECIAL_UNSIGNED_GT: 127 return SPECIAL_UNSIGNED_LT; 128 case IMPOSSIBLE_COMPARISON: 129 return UNKNOWN_COMPARISON; 130 default: 131 sm_perror("unhandled comparison %d", op); 132 return op; 133 } 134 } 135 136 int negate_comparison(int op) 137 { 138 switch (op) { 139 case UNKNOWN_COMPARISON: 140 return UNKNOWN_COMPARISON; 141 case '<': 142 return SPECIAL_GTE; 143 case SPECIAL_UNSIGNED_LT: 144 return SPECIAL_UNSIGNED_GTE; 145 case SPECIAL_LTE: 146 return '>'; 147 case SPECIAL_UNSIGNED_LTE: 148 return SPECIAL_UNSIGNED_GT; 149 case SPECIAL_EQUAL: 150 return SPECIAL_NOTEQUAL; 151 case SPECIAL_NOTEQUAL: 152 return SPECIAL_EQUAL; 153 case SPECIAL_GTE: 154 return '<'; 155 case SPECIAL_UNSIGNED_GTE: 156 return SPECIAL_UNSIGNED_LT; 157 case '>': 158 return SPECIAL_LTE; 159 case SPECIAL_UNSIGNED_GT: 160 return SPECIAL_UNSIGNED_LTE; 161 case IMPOSSIBLE_COMPARISON: 162 return UNKNOWN_COMPARISON; 163 default: 164 sm_perror("unhandled comparison %d", op); 165 return op; 166 } 167 } 168 169 static int rl_comparison(struct range_list *left_rl, struct range_list *right_rl) 170 { 171 sval_t left_min, left_max, right_min, right_max; 172 struct symbol *type = &int_ctype; 173 174 if (!left_rl || !right_rl) 175 return UNKNOWN_COMPARISON; 176 177 if (type_positive_bits(rl_type(left_rl)) > type_positive_bits(type)) 178 type = rl_type(left_rl); 179 if (type_positive_bits(rl_type(right_rl)) > type_positive_bits(type)) 180 type = rl_type(right_rl); 181 182 left_rl = cast_rl(type, left_rl); 183 right_rl = cast_rl(type, right_rl); 184 185 left_min = rl_min(left_rl); 186 left_max = rl_max(left_rl); 187 right_min = rl_min(right_rl); 188 right_max = rl_max(right_rl); 189 190 if (left_min.value == left_max.value && 191 right_min.value == right_max.value && 192 left_min.value == right_min.value) 193 return SPECIAL_EQUAL; 194 195 if (sval_cmp(left_max, right_min) < 0) 196 return '<'; 197 if (sval_cmp(left_max, right_min) == 0) 198 return SPECIAL_LTE; 199 if (sval_cmp(left_min, right_max) > 0) 200 return '>'; 201 if (sval_cmp(left_min, right_max) == 0) 202 return SPECIAL_GTE; 203 204 return UNKNOWN_COMPARISON; 205 } 206 207 static int comparison_from_extra(struct expression *a, struct expression *b) 208 { 209 struct range_list *left, *right; 210 211 if (!get_implied_rl(a, &left)) 212 return UNKNOWN_COMPARISON; 213 if (!get_implied_rl(b, &right)) 214 return UNKNOWN_COMPARISON; 215 216 return rl_comparison(left, right); 217 } 218 219 static struct range_list *get_orig_rl(struct var_sym_list *vsl) 220 { 221 struct symbol *sym; 222 struct smatch_state *state; 223 224 if (!vsl) 225 return NULL; 226 sym = vsl_to_sym(vsl); 227 if (!sym || !sym->ident) 228 return NULL; 229 state = get_orig_estate(sym->ident->name, sym); 230 return estate_rl(state); 231 } 232 233 static struct smatch_state *unmatched_comparison(struct sm_state *sm) 234 { 235 struct compare_data *data = sm->state->data; 236 struct range_list *left_rl, *right_rl; 237 int op = UNKNOWN_COMPARISON; 238 239 if (!data) 240 return &undefined; 241 242 if (is_impossible_path()) { 243 op = IMPOSSIBLE_COMPARISON; 244 goto alloc; 245 } 246 247 if (strstr(data->left_var, " orig")) 248 left_rl = get_orig_rl(data->left_vsl); 249 else if (!get_implied_rl_var_sym(data->left_var, vsl_to_sym(data->left_vsl), &left_rl)) 250 goto alloc; 251 252 if (strstr(data->right_var, " orig")) 253 right_rl = get_orig_rl(data->right_vsl); 254 else if (!get_implied_rl_var_sym(data->right_var, vsl_to_sym(data->right_vsl), &right_rl)) 255 goto alloc; 256 257 op = rl_comparison(left_rl, right_rl); 258 259 alloc: 260 return alloc_compare_state(data->left, data->left_var, data->left_vsl, 261 op, 262 data->right, data->right_var, data->right_vsl); 263 } 264 265 /* remove_unsigned_from_comparison() is obviously a hack. */ 266 int remove_unsigned_from_comparison(int op) 267 { 268 switch (op) { 269 case SPECIAL_UNSIGNED_LT: 270 return '<'; 271 case SPECIAL_UNSIGNED_LTE: 272 return SPECIAL_LTE; 273 case SPECIAL_UNSIGNED_GTE: 274 return SPECIAL_GTE; 275 case SPECIAL_UNSIGNED_GT: 276 return '>'; 277 default: 278 return op; 279 } 280 } 281 282 /* 283 * This is for when you merge states "a < b" and "a == b", the result is that 284 * we can say for sure, "a <= b" after the merge. 285 */ 286 int merge_comparisons(int one, int two) 287 { 288 int LT, EQ, GT; 289 290 if (one == UNKNOWN_COMPARISON || two == UNKNOWN_COMPARISON) 291 return UNKNOWN_COMPARISON; 292 293 if (one == IMPOSSIBLE_COMPARISON) 294 return two; 295 if (two == IMPOSSIBLE_COMPARISON) 296 return one; 297 298 one = remove_unsigned_from_comparison(one); 299 two = remove_unsigned_from_comparison(two); 300 301 if (one == two) 302 return one; 303 304 LT = EQ = GT = 0; 305 306 switch (one) { 307 case '<': 308 LT = 1; 309 break; 310 case SPECIAL_LTE: 311 LT = 1; 312 EQ = 1; 313 break; 314 case SPECIAL_EQUAL: 315 EQ = 1; 316 break; 317 case SPECIAL_GTE: 318 GT = 1; 319 EQ = 1; 320 break; 321 case '>': 322 GT = 1; 323 } 324 325 switch (two) { 326 case '<': 327 LT = 1; 328 break; 329 case SPECIAL_LTE: 330 LT = 1; 331 EQ = 1; 332 break; 333 case SPECIAL_EQUAL: 334 EQ = 1; 335 break; 336 case SPECIAL_GTE: 337 GT = 1; 338 EQ = 1; 339 break; 340 case '>': 341 GT = 1; 342 } 343 344 if (LT && EQ && GT) 345 return UNKNOWN_COMPARISON; 346 if (LT && EQ) 347 return SPECIAL_LTE; 348 if (LT && GT) 349 return SPECIAL_NOTEQUAL; 350 if (LT) 351 return '<'; 352 if (EQ && GT) 353 return SPECIAL_GTE; 354 if (GT) 355 return '>'; 356 return UNKNOWN_COMPARISON; 357 } 358 359 /* 360 * This is for if you have "a < b" and "b <= c" and you want to see how "a 361 * compares to c". You would call this like get_combined_comparison('<', '<='). 362 * The return comparison would be '<'. 363 */ 364 int combine_comparisons(int left_compare, int right_compare) 365 { 366 int LT, EQ, GT; 367 368 left_compare = remove_unsigned_from_comparison(left_compare); 369 right_compare = remove_unsigned_from_comparison(right_compare); 370 371 LT = EQ = GT = 0; 372 373 switch (left_compare) { 374 case '<': 375 LT++; 376 break; 377 case SPECIAL_LTE: 378 LT++; 379 EQ++; 380 break; 381 case SPECIAL_EQUAL: 382 return right_compare; 383 case SPECIAL_GTE: 384 GT++; 385 EQ++; 386 break; 387 case '>': 388 GT++; 389 } 390 391 switch (right_compare) { 392 case '<': 393 LT++; 394 break; 395 case SPECIAL_LTE: 396 LT++; 397 EQ++; 398 break; 399 case SPECIAL_EQUAL: 400 return left_compare; 401 case SPECIAL_GTE: 402 GT++; 403 EQ++; 404 break; 405 case '>': 406 GT++; 407 } 408 409 if (LT == 2) { 410 if (EQ == 2) 411 return SPECIAL_LTE; 412 return '<'; 413 } 414 415 if (GT == 2) { 416 if (EQ == 2) 417 return SPECIAL_GTE; 418 return '>'; 419 } 420 return UNKNOWN_COMPARISON; 421 } 422 423 /* 424 * This is mostly used when you know from extra state that a <= b but you 425 * know from comparisons that a != b so then if take the intersection then 426 * we know that a < b. The name is taken from the fact that the intersection 427 * of < and <= is <. 428 */ 429 int comparison_intersection(int left_compare, int right_compare) 430 { 431 int LT, GT, EQ, NE, total; 432 433 if (left_compare == IMPOSSIBLE_COMPARISON || 434 right_compare == IMPOSSIBLE_COMPARISON) 435 return IMPOSSIBLE_COMPARISON; 436 437 left_compare = remove_unsigned_from_comparison(left_compare); 438 right_compare = remove_unsigned_from_comparison(right_compare); 439 440 LT = GT = EQ = NE = total = 0; 441 442 /* Only one side is known. */ 443 if (!left_compare) 444 return right_compare; 445 if (!right_compare) 446 return left_compare; 447 448 switch (left_compare) { 449 case '<': 450 LT++; 451 total += 1; 452 break; 453 case SPECIAL_LTE: 454 LT++; 455 EQ++; 456 total += 2; 457 break; 458 case SPECIAL_EQUAL: 459 EQ++; 460 total += 1; 461 break; 462 case SPECIAL_NOTEQUAL: 463 NE++; 464 total += 1; 465 break; 466 case SPECIAL_GTE: 467 GT++; 468 EQ++; 469 total += 2; 470 break; 471 case '>': 472 GT++; 473 total += 1; 474 break; 475 default: 476 return UNKNOWN_COMPARISON; 477 } 478 479 switch (right_compare) { 480 case '<': 481 LT++; 482 total += 1; 483 break; 484 case SPECIAL_LTE: 485 LT++; 486 EQ++; 487 total += 2; 488 break; 489 case SPECIAL_EQUAL: 490 EQ++; 491 total += 1; 492 break; 493 case SPECIAL_NOTEQUAL: 494 NE++; 495 total += 1; 496 break; 497 case SPECIAL_GTE: 498 GT++; 499 EQ++; 500 total += 2; 501 break; 502 case '>': 503 GT++; 504 total += 1; 505 break; 506 default: 507 return UNKNOWN_COMPARISON; 508 } 509 510 if (LT == 2) { 511 if (EQ == 2) 512 return SPECIAL_LTE; 513 return '<'; 514 } 515 516 if (GT == 2) { 517 if (EQ == 2) 518 return SPECIAL_GTE; 519 return '>'; 520 } 521 if (EQ == 2) 522 return SPECIAL_EQUAL; 523 if (total == 2 && EQ && NE) 524 return IMPOSSIBLE_COMPARISON; 525 if (GT && LT) 526 return IMPOSSIBLE_COMPARISON; 527 if (GT && NE) 528 return '>'; 529 if (LT && NE) 530 return '<'; 531 if (NE == 2) 532 return SPECIAL_NOTEQUAL; 533 if (total == 2 && (LT || GT) && EQ) 534 return IMPOSSIBLE_COMPARISON; 535 536 return UNKNOWN_COMPARISON; 537 } 538 539 static void pre_merge_hook(struct sm_state *cur, struct sm_state *other) 540 { 541 struct compare_data *data = cur->state->data; 542 int extra, new; 543 static bool in_recurse; 544 545 if (!data) 546 return; 547 548 if (in_recurse) 549 return; 550 in_recurse = true; 551 extra = comparison_from_extra(data->left, data->right); 552 in_recurse = false; 553 if (!extra) 554 return; 555 new = comparison_intersection(extra, data->comparison); 556 if (new == data->comparison) 557 return; 558 559 set_state(compare_id, cur->name, NULL, 560 alloc_compare_state(data->left, data->left_var, data->left_vsl, 561 new, 562 data->right, data->right_var, data->right_vsl)); 563 } 564 565 struct smatch_state *merge_compare_states(struct smatch_state *s1, struct smatch_state *s2) 566 { 567 struct compare_data *data = s1->data; 568 int op; 569 570 if (!data) 571 return &undefined; 572 573 op = merge_comparisons(state_to_comparison(s1), state_to_comparison(s2)); 574 return alloc_compare_state( 575 data->left, data->left_var, data->left_vsl, 576 op, 577 data->right, data->right_var, data->right_vsl); 578 } 579 580 static struct smatch_state *alloc_link_state(struct string_list *links) 581 { 582 struct smatch_state *state; 583 static char buf[256]; 584 char *tmp; 585 int i; 586 587 state = __alloc_smatch_state(0); 588 589 i = 0; 590 FOR_EACH_PTR(links, tmp) { 591 if (!i++) { 592 snprintf(buf, sizeof(buf), "%s", tmp); 593 } else { 594 append(buf, ", ", sizeof(buf)); 595 append(buf, tmp, sizeof(buf)); 596 } 597 } END_FOR_EACH_PTR(tmp); 598 599 state->name = alloc_sname(buf); 600 state->data = links; 601 return state; 602 } 603 604 static void save_start_states(struct statement *stmt) 605 { 606 struct symbol *param; 607 char orig[64]; 608 char state_name[128]; 609 struct smatch_state *state; 610 struct string_list *links; 611 char *link; 612 613 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 614 struct var_sym_list *left_vsl = NULL; 615 struct var_sym_list *right_vsl = NULL; 616 617 if (!param->ident) 618 continue; 619 snprintf(orig, sizeof(orig), "%s orig", param->ident->name); 620 snprintf(state_name, sizeof(state_name), "%s vs %s", param->ident->name, orig); 621 add_var_sym(&left_vsl, param->ident->name, param); 622 add_var_sym(&right_vsl, orig, param); 623 state = alloc_compare_state( 624 NULL, param->ident->name, left_vsl, 625 SPECIAL_EQUAL, 626 NULL, alloc_sname(orig), right_vsl); 627 set_state(compare_id, state_name, NULL, state); 628 629 link = alloc_sname(state_name); 630 links = NULL; 631 insert_string(&links, link); 632 state = alloc_link_state(links); 633 set_state(link_id, param->ident->name, param, state); 634 } END_FOR_EACH_PTR(param); 635 } 636 637 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2) 638 { 639 struct smatch_state *ret; 640 struct string_list *links; 641 642 links = combine_string_lists(s1->data, s2->data); 643 ret = alloc_link_state(links); 644 return ret; 645 } 646 647 static void save_link_var_sym(const char *var, struct symbol *sym, const char *link) 648 { 649 struct smatch_state *old_state, *new_state; 650 struct string_list *links; 651 char *new; 652 653 old_state = get_state(link_id, var, sym); 654 if (old_state) 655 links = clone_str_list(old_state->data); 656 else 657 links = NULL; 658 659 new = alloc_sname(link); 660 insert_string(&links, new); 661 662 new_state = alloc_link_state(links); 663 set_state(link_id, var, sym, new_state); 664 } 665 666 static void match_inc(struct sm_state *sm, bool preserve) 667 { 668 struct string_list *links; 669 struct smatch_state *state, *new; 670 struct compare_data *data; 671 char *tmp; 672 int flip; 673 int op; 674 675 links = sm->state->data; 676 677 FOR_EACH_PTR(links, tmp) { 678 state = get_state(compare_id, tmp, NULL); 679 if (!state) 680 continue; 681 data = state->data; 682 if (!data) 683 continue; 684 685 flip = 0; 686 if (strncmp(sm->name, tmp, strlen(sm->name)) != 0 || 687 tmp[strlen(sm->name)] != ' ') 688 flip = 1; 689 690 op = state_to_comparison(state); 691 692 switch (flip ? flip_comparison(op) : op) { 693 case SPECIAL_EQUAL: 694 case SPECIAL_GTE: 695 case SPECIAL_UNSIGNED_GTE: 696 case '>': 697 case SPECIAL_UNSIGNED_GT: 698 if (preserve) 699 break; 700 new = alloc_compare_state( 701 data->left, data->left_var, data->left_vsl, 702 flip ? '<' : '>', 703 data->right, data->right_var, data->right_vsl); 704 set_state(compare_id, tmp, NULL, new); 705 break; 706 case '<': 707 case SPECIAL_UNSIGNED_LT: 708 new = alloc_compare_state( 709 data->left, data->left_var, data->left_vsl, 710 flip ? SPECIAL_GTE : SPECIAL_LTE, 711 data->right, data->right_var, data->right_vsl); 712 set_state(compare_id, tmp, NULL, new); 713 break; 714 default: 715 new = alloc_compare_state( 716 data->left, data->left_var, data->left_vsl, 717 UNKNOWN_COMPARISON, 718 data->right, data->right_var, data->right_vsl); 719 set_state(compare_id, tmp, NULL, new); 720 } 721 } END_FOR_EACH_PTR(tmp); 722 } 723 724 static void match_dec(struct sm_state *sm, bool preserve) 725 { 726 struct string_list *links; 727 struct smatch_state *state; 728 char *tmp; 729 730 links = sm->state->data; 731 732 FOR_EACH_PTR(links, tmp) { 733 struct compare_data *data; 734 struct smatch_state *new; 735 736 state = get_state(compare_id, tmp, NULL); 737 if (!state || !state->data) 738 continue; 739 740 data = state->data; 741 742 switch (state_to_comparison(state)) { 743 case SPECIAL_EQUAL: 744 case SPECIAL_LTE: 745 case SPECIAL_UNSIGNED_LTE: 746 case '<': 747 case SPECIAL_UNSIGNED_LT: { 748 if (preserve) 749 break; 750 751 new = alloc_compare_state( 752 data->left, data->left_var, data->left_vsl, 753 '<', 754 data->right, data->right_var, data->right_vsl); 755 set_state(compare_id, tmp, NULL, new); 756 break; 757 } 758 default: 759 new = alloc_compare_state( 760 data->left, data->left_var, data->left_vsl, 761 UNKNOWN_COMPARISON, 762 data->right, data->right_var, data->right_vsl); 763 set_state(compare_id, tmp, NULL, new); 764 } 765 } END_FOR_EACH_PTR(tmp); 766 } 767 768 static void reset_sm(struct sm_state *sm) 769 { 770 struct string_list *links; 771 char *tmp; 772 773 links = sm->state->data; 774 775 FOR_EACH_PTR(links, tmp) { 776 struct smatch_state *old, *new; 777 778 old = get_state(compare_id, tmp, NULL); 779 if (!old || !old->data) { 780 new = &undefined; 781 } else { 782 struct compare_data *data = old->data; 783 784 new = alloc_compare_state( 785 data->left, data->left_var, data->left_vsl, 786 UNKNOWN_COMPARISON, 787 data->right, data->right_var, data->right_vsl); 788 } 789 set_state(compare_id, tmp, NULL, new); 790 } END_FOR_EACH_PTR(tmp); 791 set_state(link_id, sm->name, sm->sym, &undefined); 792 } 793 794 static bool match_add_sub_assign(struct sm_state *sm, struct expression *expr) 795 { 796 struct range_list *rl; 797 sval_t zero = { .type = &int_ctype }; 798 799 if (!expr || expr->type != EXPR_ASSIGNMENT) 800 return false; 801 if (expr->op != SPECIAL_ADD_ASSIGN && expr->op != SPECIAL_SUB_ASSIGN) 802 return false; 803 804 get_absolute_rl(expr->right, &rl); 805 if (sval_is_negative(rl_min(rl))) { 806 reset_sm(sm); 807 return false; 808 } 809 810 if (expr->op == SPECIAL_ADD_ASSIGN) 811 match_inc(sm, rl_has_sval(rl, zero)); 812 else 813 match_dec(sm, rl_has_sval(rl, zero)); 814 return true; 815 } 816 817 static void match_inc_dec(struct sm_state *sm, struct expression *mod_expr) 818 { 819 /* 820 * if (foo > bar) then ++foo is also > bar. 821 */ 822 if (!mod_expr) 823 return; 824 if (match_add_sub_assign(sm, mod_expr)) 825 return; 826 if (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) 827 return; 828 829 if (mod_expr->op == SPECIAL_INCREMENT) 830 match_inc(sm, false); 831 else if (mod_expr->op == SPECIAL_DECREMENT) 832 match_dec(sm, false); 833 } 834 835 static int is_self_assign(struct expression *expr) 836 { 837 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=') 838 return 0; 839 return expr_equiv(expr->left, expr->right); 840 } 841 842 static void match_modify(struct sm_state *sm, struct expression *mod_expr) 843 { 844 if (mod_expr && is_self_assign(mod_expr)) 845 return; 846 847 /* handled by match_inc_dec() */ 848 if (mod_expr && 849 ((mod_expr->type == EXPR_PREOP || mod_expr->type == EXPR_POSTOP) && 850 (mod_expr->op == SPECIAL_INCREMENT || mod_expr->op == SPECIAL_DECREMENT))) 851 return; 852 if (mod_expr && mod_expr->type == EXPR_ASSIGNMENT && 853 (mod_expr->op == SPECIAL_ADD_ASSIGN || mod_expr->op == SPECIAL_SUB_ASSIGN)) 854 return; 855 856 reset_sm(sm); 857 } 858 859 static void match_preop(struct expression *expr) 860 { 861 struct expression *parent; 862 struct range_list *left, *right; 863 int op; 864 865 /* 866 * This is an important special case. Say you have: 867 * 868 * if (++j == limit) 869 * 870 * Assume that we know the range of limit is higher than the start 871 * value for "j". Then the first thing that we process is the ++j. We 872 * have not comparison states set up so it doesn't get caught by the 873 * modification hook. But it does get caught by smatch_extra which sets 874 * j to unknown then we parse the "j == limit" and sets false to != but 875 * really we want false to be <. 876 * 877 * So what we do is we set j < limit here, then the match_modify catches 878 * it and we do a match_inc_dec(). 879 * 880 */ 881 882 if (expr->type != EXPR_PREOP || 883 (expr->op != SPECIAL_INCREMENT && expr->op != SPECIAL_DECREMENT)) 884 return; 885 886 parent = expr_get_parent_expr(expr); 887 if (!parent) 888 return; 889 if (parent->type != EXPR_COMPARE || parent->op != SPECIAL_EQUAL) 890 return; 891 if (parent->left != expr) 892 return; 893 894 if (!get_implied_rl(expr->unop, &left) || 895 !get_implied_rl(parent->right, &right)) 896 return; 897 898 op = rl_comparison(left, right); 899 if (op == UNKNOWN_COMPARISON) 900 return; 901 902 add_comparison(expr->unop, op, parent->right); 903 } 904 905 static char *chunk_to_var_sym(struct expression *expr, struct symbol **sym) 906 { 907 expr = strip_expr(expr); 908 if (!expr) 909 return NULL; 910 if (sym) 911 *sym = NULL; 912 913 if (expr->type == EXPR_PREOP && 914 (expr->op == SPECIAL_INCREMENT || 915 expr->op == SPECIAL_DECREMENT)) 916 expr = strip_expr(expr->unop); 917 918 if (expr->type == EXPR_CALL) { 919 char buf[64]; 920 921 snprintf(buf, sizeof(buf), "return %p", expr); 922 return alloc_string(buf); 923 } 924 925 return expr_to_chunk_sym_vsl(expr, sym, NULL); 926 } 927 928 static char *chunk_to_var(struct expression *expr) 929 { 930 return chunk_to_var_sym(expr, NULL); 931 } 932 933 static struct smatch_state *get_state_chunk(int owner, struct expression *expr) 934 { 935 char *name; 936 struct symbol *sym; 937 struct smatch_state *ret; 938 939 name = chunk_to_var_sym(expr, &sym); 940 if (!name) 941 return NULL; 942 943 ret = get_state(owner, name, sym); 944 free_string(name); 945 return ret; 946 } 947 948 static void save_link(struct expression *expr, char *link) 949 { 950 char *var; 951 struct symbol *sym; 952 953 expr = strip_expr(expr); 954 if (expr->type == EXPR_BINOP) { 955 char *chunk; 956 957 chunk = chunk_to_var(expr); 958 if (!chunk) 959 return; 960 961 save_link(expr->left, link); 962 save_link(expr->right, link); 963 save_link_var_sym(chunk, NULL, link); 964 return; 965 } 966 967 var = chunk_to_var_sym(expr, &sym); 968 if (!var) 969 return; 970 971 save_link_var_sym(var, sym, link); 972 free_string(var); 973 } 974 975 static int get_orig_comparison(struct stree *pre_stree, const char *left, const char *right) 976 { 977 struct smatch_state *state; 978 struct compare_data *data; 979 int flip = 0; 980 char state_name[256]; 981 982 if (strcmp(left, right) > 0) { 983 const char *tmp = right; 984 985 flip = 1; 986 right = left; 987 left = tmp; 988 } 989 990 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right); 991 state = get_state_stree(pre_stree, compare_id, state_name, NULL); 992 if (!state || !state->data) 993 return 0; 994 data = state->data; 995 if (flip) 996 return flip_comparison(data->comparison); 997 return data->comparison; 998 999 } 1000 1001 static int have_common_var_sym(struct var_sym_list *left_vsl, struct var_sym_list *right_vsl) 1002 { 1003 struct var_sym *tmp; 1004 1005 FOR_EACH_PTR(left_vsl, tmp) { 1006 if (in_var_sym_list(right_vsl, tmp->var, tmp->sym)) 1007 return 1; 1008 } END_FOR_EACH_PTR(tmp); 1009 1010 return 0; 1011 } 1012 1013 /* 1014 * The idea here is that we take a comparison "a < b" and then we look at all 1015 * the things which "b" is compared against "b < c" and we say that that implies 1016 * a relationship "a < c". 1017 * 1018 * The names here about because the comparisons are organized like this 1019 * "a < b < c". 1020 * 1021 */ 1022 static void update_tf_links(struct stree *pre_stree, 1023 struct expression *left_expr, 1024 const char *left_var, struct var_sym_list *left_vsl, 1025 int left_comparison, int left_false_comparison, 1026 const char *mid_var, struct var_sym_list *mid_vsl, 1027 struct string_list *links) 1028 { 1029 struct smatch_state *state; 1030 struct smatch_state *true_state, *false_state; 1031 struct compare_data *data; 1032 struct expression *right_expr; 1033 const char *right_var; 1034 struct var_sym_list *right_vsl; 1035 int orig_comparison; 1036 int right_comparison; 1037 int true_comparison; 1038 int false_comparison; 1039 char *tmp; 1040 char state_name[256]; 1041 struct var_sym *vs; 1042 1043 FOR_EACH_PTR(links, tmp) { 1044 state = get_state_stree(pre_stree, compare_id, tmp, NULL); 1045 if (!state || !state->data) 1046 continue; 1047 data = state->data; 1048 right_comparison = data->comparison; 1049 right_expr = data->right; 1050 right_var = data->right_var; 1051 right_vsl = data->right_vsl; 1052 if (strcmp(mid_var, right_var) == 0) { 1053 right_expr = data->left; 1054 right_var = data->left_var; 1055 right_vsl = data->left_vsl; 1056 right_comparison = flip_comparison(right_comparison); 1057 } 1058 if (have_common_var_sym(left_vsl, right_vsl)) 1059 continue; 1060 1061 orig_comparison = get_orig_comparison(pre_stree, left_var, right_var); 1062 1063 true_comparison = combine_comparisons(left_comparison, right_comparison); 1064 false_comparison = combine_comparisons(left_false_comparison, right_comparison); 1065 1066 true_comparison = comparison_intersection(orig_comparison, true_comparison); 1067 false_comparison = comparison_intersection(orig_comparison, false_comparison); 1068 1069 if (strcmp(left_var, right_var) > 0) { 1070 struct expression *tmp_expr = left_expr; 1071 const char *tmp_var = left_var; 1072 struct var_sym_list *tmp_vsl = left_vsl; 1073 1074 left_expr = right_expr; 1075 left_var = right_var; 1076 left_vsl = right_vsl; 1077 right_expr = tmp_expr; 1078 right_var = tmp_var; 1079 right_vsl = tmp_vsl; 1080 true_comparison = flip_comparison(true_comparison); 1081 false_comparison = flip_comparison(false_comparison); 1082 } 1083 1084 if (!true_comparison && !false_comparison) 1085 continue; 1086 1087 if (true_comparison) 1088 true_state = alloc_compare_state( 1089 left_expr, left_var, left_vsl, 1090 true_comparison, 1091 right_expr, right_var, right_vsl); 1092 else 1093 true_state = NULL; 1094 if (false_comparison) 1095 false_state = alloc_compare_state( 1096 left_expr, left_var, left_vsl, 1097 false_comparison, 1098 right_expr, right_var, right_vsl); 1099 else 1100 false_state = NULL; 1101 1102 snprintf(state_name, sizeof(state_name), "%s vs %s", left_var, right_var); 1103 set_true_false_states(compare_id, state_name, NULL, true_state, false_state); 1104 FOR_EACH_PTR(left_vsl, vs) { 1105 save_link_var_sym(vs->var, vs->sym, state_name); 1106 } END_FOR_EACH_PTR(vs); 1107 FOR_EACH_PTR(right_vsl, vs) { 1108 save_link_var_sym(vs->var, vs->sym, state_name); 1109 } END_FOR_EACH_PTR(vs); 1110 if (!vsl_to_sym(left_vsl)) 1111 save_link_var_sym(left_var, NULL, state_name); 1112 if (!vsl_to_sym(right_vsl)) 1113 save_link_var_sym(right_var, NULL, state_name); 1114 } END_FOR_EACH_PTR(tmp); 1115 } 1116 1117 static void update_tf_data(struct stree *pre_stree, 1118 struct expression *left_expr, 1119 const char *left_name, struct var_sym_list *left_vsl, 1120 struct expression *right_expr, 1121 const char *right_name, struct var_sym_list *right_vsl, 1122 int true_comparison, int false_comparison) 1123 { 1124 struct smatch_state *state; 1125 1126 state = get_state_stree(pre_stree, link_id, right_name, vsl_to_sym(right_vsl)); 1127 if (state) 1128 update_tf_links(pre_stree, left_expr, left_name, left_vsl, true_comparison, false_comparison, right_name, right_vsl, state->data); 1129 1130 state = get_state_stree(pre_stree, link_id, left_name, vsl_to_sym(left_vsl)); 1131 if (state) 1132 update_tf_links(pre_stree, right_expr, right_name, right_vsl, flip_comparison(true_comparison), flip_comparison(false_comparison), left_name, left_vsl, state->data); 1133 } 1134 1135 static void iter_modify(struct sm_state *sm, struct expression *mod_expr) 1136 { 1137 if (sm->state != &start || 1138 !mod_expr || 1139 (mod_expr->type != EXPR_PREOP && mod_expr->type != EXPR_POSTOP) || 1140 mod_expr->op != SPECIAL_INCREMENT) 1141 set_state(inc_dec_id, sm->name, sm->sym, &undefined); 1142 else 1143 set_state(inc_dec_id, sm->name, sm->sym, &incremented); 1144 } 1145 1146 static void handle_for_loops(struct expression *expr, char *state_name, struct smatch_state *false_state) 1147 { 1148 sval_t sval; 1149 char *iter_name, *cap_name; 1150 struct symbol *iter_sym, *cap_sym; 1151 struct compare_data *data; 1152 1153 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT) 1154 return; 1155 1156 if (!__cur_stmt || !__prev_stmt) 1157 return; 1158 if (__cur_stmt->type != STMT_ITERATOR) 1159 return; 1160 if (__cur_stmt->iterator_pre_condition != expr) 1161 return; 1162 1163 /* literals are handled in smatch_extra.c */ 1164 if (get_value(expr->right, &sval)) 1165 return; 1166 1167 /* First time checking the condition */ 1168 if (__prev_stmt == __cur_stmt->iterator_pre_statement) { 1169 if (!get_implied_value(expr->left, &sval) || 1170 sval.value != 0) 1171 return; 1172 1173 iter_name = expr_to_var_sym(expr->left, &iter_sym); 1174 cap_name = expr_to_var_sym(expr->right, &cap_sym); 1175 if (!iter_name || !cap_name || !iter_sym || !cap_sym) { 1176 free_string(iter_name); 1177 free_string(cap_name); 1178 return; 1179 } 1180 1181 set_state(inc_dec_id, iter_name, iter_sym, &start); 1182 store_link(inc_dec_link_id, cap_name, cap_sym, iter_name, iter_sym); 1183 1184 free_string(iter_name); 1185 free_string(cap_name); 1186 return; 1187 } 1188 1189 /* Second time checking the condtion */ 1190 if (__prev_stmt != __cur_stmt->iterator_post_statement) 1191 return; 1192 1193 if (get_state_chunk(inc_dec_id, expr->left) != &incremented) 1194 return; 1195 1196 data = false_state->data; 1197 false_state = alloc_compare_state( 1198 data->left, data->left_var, data->left_vsl, 1199 SPECIAL_EQUAL, 1200 data->right, data->right_var, data->right_vsl); 1201 1202 set_true_false_states(compare_id, state_name, NULL, NULL, false_state); 1203 } 1204 1205 static int is_plus_one(struct expression *expr) 1206 { 1207 sval_t sval; 1208 1209 if (expr->type != EXPR_BINOP || expr->op != '+') 1210 return 0; 1211 if (!get_implied_value(expr->right, &sval) || sval.value != 1) 1212 return 0; 1213 return 1; 1214 } 1215 1216 static int is_minus_one(struct expression *expr) 1217 { 1218 sval_t sval; 1219 1220 if (expr->type != EXPR_BINOP || expr->op != '-') 1221 return 0; 1222 if (!get_implied_value(expr->right, &sval) || sval.value != 1) 1223 return 0; 1224 return 1; 1225 } 1226 1227 static void move_plus_to_minus_helper(struct expression **left_p, struct expression **right_p) 1228 { 1229 struct expression *left = *left_p; 1230 struct expression *right = *right_p; 1231 1232 /* 1233 * These two are basically equivalent: "foo + 1 != bar" and 1234 * "foo != bar - 1". There are issues with signedness and integer 1235 * overflows. There are also issues with type as well. But let's 1236 * pretend we can ignore all that stuff for now. 1237 * 1238 */ 1239 1240 if (!is_plus_one(left)) 1241 return; 1242 1243 *left_p = left->left; 1244 *right_p = binop_expression(right, '-', left->right); 1245 } 1246 1247 static void move_plus_to_minus(struct expression **left_p, struct expression **right_p) 1248 { 1249 if (is_plus_one(*left_p) && is_plus_one(*right_p)) 1250 return; 1251 1252 move_plus_to_minus_helper(left_p, right_p); 1253 move_plus_to_minus_helper(right_p, left_p); 1254 } 1255 1256 static void handle_comparison(struct expression *left_expr, int op, struct expression *right_expr, char **_state_name, struct smatch_state **_false_state) 1257 { 1258 char *left = NULL; 1259 char *right = NULL; 1260 struct symbol *left_sym, *right_sym; 1261 struct var_sym_list *left_vsl = NULL; 1262 struct var_sym_list *right_vsl = NULL; 1263 int false_op; 1264 int orig_comparison; 1265 struct smatch_state *true_state, *false_state; 1266 static char state_name[256]; 1267 struct stree *pre_stree; 1268 sval_t sval; 1269 1270 if (!left_expr || !right_expr) 1271 return; 1272 1273 left_expr = strip_parens(left_expr); 1274 right_expr = strip_parens(right_expr); 1275 1276 while (left_expr->type == EXPR_ASSIGNMENT) 1277 left_expr = strip_parens(left_expr->left); 1278 while (right_expr->type == EXPR_ASSIGNMENT) 1279 right_expr = strip_parens(right_expr->left); 1280 1281 false_op = negate_comparison(op); 1282 1283 move_plus_to_minus(&left_expr, &right_expr); 1284 1285 if (op == SPECIAL_UNSIGNED_LT && 1286 get_implied_value(left_expr, &sval) && 1287 sval.value == 0) 1288 false_op = SPECIAL_EQUAL; 1289 1290 if (op == SPECIAL_UNSIGNED_GT && 1291 get_implied_value(right_expr, &sval) && 1292 sval.value == 0) 1293 false_op = SPECIAL_EQUAL; 1294 1295 left = chunk_to_var_sym(left_expr, &left_sym); 1296 if (!left) 1297 goto free; 1298 if (left_sym) 1299 add_var_sym(&left_vsl, left, left_sym); 1300 else 1301 left_vsl = expr_to_vsl(left_expr); 1302 right = chunk_to_var_sym(right_expr, &right_sym); 1303 if (!right) 1304 goto free; 1305 if (right_sym) 1306 add_var_sym(&right_vsl, right, right_sym); 1307 else 1308 right_vsl = expr_to_vsl(right_expr); 1309 1310 if (strcmp(left, right) > 0) { 1311 char *tmp_name = left; 1312 struct var_sym_list *tmp_vsl = left_vsl; 1313 struct expression *tmp_expr = left_expr; 1314 1315 left = right; 1316 left_vsl = right_vsl; 1317 left_expr = right_expr; 1318 right = tmp_name; 1319 right_vsl = tmp_vsl; 1320 right_expr = tmp_expr; 1321 op = flip_comparison(op); 1322 false_op = flip_comparison(false_op); 1323 } 1324 1325 orig_comparison = get_comparison(left_expr, right_expr); 1326 op = comparison_intersection(orig_comparison, op); 1327 false_op = comparison_intersection(orig_comparison, false_op); 1328 1329 snprintf(state_name, sizeof(state_name), "%s vs %s", left, right); 1330 true_state = alloc_compare_state( 1331 left_expr, left, left_vsl, 1332 op, 1333 right_expr, right, right_vsl); 1334 false_state = alloc_compare_state( 1335 left_expr, left, left_vsl, 1336 false_op, 1337 right_expr, right, right_vsl); 1338 1339 pre_stree = clone_stree(__get_cur_stree()); 1340 update_tf_data(pre_stree, left_expr, left, left_vsl, right_expr, right, right_vsl, op, false_op); 1341 free_stree(&pre_stree); 1342 1343 set_true_false_states(compare_id, state_name, NULL, true_state, false_state); 1344 __compare_param_limit_hook(left_expr, right_expr, state_name, true_state, false_state); 1345 save_link(left_expr, state_name); 1346 save_link(right_expr, state_name); 1347 1348 if (_false_state) 1349 *_false_state = false_state; 1350 if (_state_name) 1351 *_state_name = state_name; 1352 free: 1353 free_string(left); 1354 free_string(right); 1355 } 1356 1357 void __comparison_match_condition(struct expression *expr) 1358 { 1359 struct expression *left, *right, *new_left, *new_right, *tmp; 1360 struct smatch_state *false_state = NULL; 1361 char *state_name = NULL; 1362 int redo, count; 1363 1364 if (expr->type != EXPR_COMPARE) 1365 return; 1366 1367 handle_comparison(expr->left, expr->op, expr->right, &state_name, &false_state); 1368 if (false_state && state_name) 1369 handle_for_loops(expr, state_name, false_state); 1370 1371 left = strip_parens(expr->left); 1372 right = strip_parens(expr->right); 1373 1374 if (left->type == EXPR_BINOP && left->op == '+') { 1375 new_left = left->left; 1376 new_right = binop_expression(right, '-', left->right); 1377 handle_comparison(new_left, expr->op, new_right, NULL, NULL); 1378 1379 new_left = left->right; 1380 new_right = binop_expression(right, '-', left->left); 1381 handle_comparison(new_left, expr->op, new_right, NULL, NULL); 1382 } 1383 1384 redo = 0; 1385 left = strip_parens(expr->left); 1386 right = strip_parens(expr->right); 1387 if (get_last_expr_from_expression_stmt(expr->left)) { 1388 left = get_last_expr_from_expression_stmt(expr->left); 1389 redo = 1; 1390 } 1391 if (get_last_expr_from_expression_stmt(expr->right)) { 1392 right = get_last_expr_from_expression_stmt(expr->right); 1393 redo = 1; 1394 } 1395 1396 if (!redo) 1397 return; 1398 1399 count = 0; 1400 while ((tmp = get_assigned_expr(left))) { 1401 if (count++ > 3) 1402 break; 1403 left = strip_expr(tmp); 1404 } 1405 count = 0; 1406 while ((tmp = get_assigned_expr(right))) { 1407 if (count++ > 3) 1408 break; 1409 right = strip_expr(tmp); 1410 } 1411 1412 handle_comparison(left, expr->op, right, NULL, NULL); 1413 } 1414 1415 static void add_comparison_var_sym( 1416 struct expression *left_expr, 1417 const char *left_name, struct var_sym_list *left_vsl, 1418 int comparison, 1419 struct expression *right_expr, 1420 const char *right_name, struct var_sym_list *right_vsl) 1421 { 1422 struct smatch_state *state; 1423 struct var_sym *vs; 1424 char state_name[256]; 1425 1426 if (strcmp(left_name, right_name) > 0) { 1427 struct expression *tmp_expr = left_expr; 1428 const char *tmp_name = left_name; 1429 struct var_sym_list *tmp_vsl = left_vsl; 1430 1431 left_expr = right_expr; 1432 left_name = right_name; 1433 left_vsl = right_vsl; 1434 right_expr = tmp_expr; 1435 right_name = tmp_name; 1436 right_vsl = tmp_vsl; 1437 comparison = flip_comparison(comparison); 1438 } 1439 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name); 1440 state = alloc_compare_state( 1441 left_expr, left_name, left_vsl, 1442 comparison, 1443 right_expr, right_name, right_vsl); 1444 1445 set_state(compare_id, state_name, NULL, state); 1446 1447 FOR_EACH_PTR(left_vsl, vs) { 1448 save_link_var_sym(vs->var, vs->sym, state_name); 1449 } END_FOR_EACH_PTR(vs); 1450 FOR_EACH_PTR(right_vsl, vs) { 1451 save_link_var_sym(vs->var, vs->sym, state_name); 1452 } END_FOR_EACH_PTR(vs); 1453 } 1454 1455 static void add_comparison(struct expression *left, int comparison, struct expression *right) 1456 { 1457 char *left_name = NULL; 1458 char *right_name = NULL; 1459 struct symbol *left_sym, *right_sym; 1460 struct var_sym_list *left_vsl, *right_vsl; 1461 struct smatch_state *state; 1462 char state_name[256]; 1463 1464 left_name = chunk_to_var_sym(left, &left_sym); 1465 if (!left_name) 1466 goto free; 1467 left_vsl = expr_to_vsl(left); 1468 right_name = chunk_to_var_sym(right, &right_sym); 1469 if (!right_name) 1470 goto free; 1471 right_vsl = expr_to_vsl(right); 1472 1473 if (strcmp(left_name, right_name) > 0) { 1474 struct expression *tmp_expr = left; 1475 struct symbol *tmp_sym = left_sym; 1476 char *tmp_name = left_name; 1477 struct var_sym_list *tmp_vsl = left_vsl; 1478 1479 left = right; 1480 left_name = right_name; 1481 left_sym = right_sym; 1482 left_vsl = right_vsl; 1483 right = tmp_expr; 1484 right_name = tmp_name; 1485 right_sym = tmp_sym; 1486 right_vsl = tmp_vsl; 1487 comparison = flip_comparison(comparison); 1488 } 1489 snprintf(state_name, sizeof(state_name), "%s vs %s", left_name, right_name); 1490 state = alloc_compare_state( 1491 left, left_name, left_vsl, 1492 comparison, 1493 right, right_name, right_vsl); 1494 1495 set_state(compare_id, state_name, NULL, state); 1496 save_link(left, state_name); 1497 save_link(right, state_name); 1498 1499 free: 1500 free_string(left_name); 1501 free_string(right_name); 1502 } 1503 1504 static void match_assign_add(struct expression *expr) 1505 { 1506 struct expression *right; 1507 struct expression *r_left, *r_right; 1508 sval_t left_tmp, right_tmp; 1509 1510 right = strip_expr(expr->right); 1511 r_left = strip_expr(right->left); 1512 r_right = strip_expr(right->right); 1513 1514 get_absolute_min(r_left, &left_tmp); 1515 get_absolute_min(r_right, &right_tmp); 1516 1517 if (left_tmp.value > 0) 1518 add_comparison(expr->left, '>', r_right); 1519 else if (left_tmp.value == 0) 1520 add_comparison(expr->left, SPECIAL_GTE, r_right); 1521 1522 if (right_tmp.value > 0) 1523 add_comparison(expr->left, '>', r_left); 1524 else if (right_tmp.value == 0) 1525 add_comparison(expr->left, SPECIAL_GTE, r_left); 1526 } 1527 1528 static void match_assign_sub(struct expression *expr) 1529 { 1530 struct expression *right; 1531 struct expression *r_left, *r_right; 1532 int comparison; 1533 sval_t min; 1534 1535 right = strip_expr(expr->right); 1536 r_left = strip_expr(right->left); 1537 r_right = strip_expr(right->right); 1538 1539 if (get_absolute_min(r_right, &min) && sval_is_negative(min)) 1540 return; 1541 1542 comparison = get_comparison(r_left, r_right); 1543 1544 switch (comparison) { 1545 case '>': 1546 case SPECIAL_GTE: 1547 if (implied_not_equal(r_right, 0)) 1548 add_comparison(expr->left, '>', r_left); 1549 else 1550 add_comparison(expr->left, SPECIAL_GTE, r_left); 1551 return; 1552 } 1553 } 1554 1555 static void match_assign_divide(struct expression *expr) 1556 { 1557 struct expression *right; 1558 struct expression *r_left, *r_right; 1559 sval_t min; 1560 1561 right = strip_expr(expr->right); 1562 r_left = strip_expr(right->left); 1563 r_right = strip_expr(right->right); 1564 if (!get_implied_min(r_right, &min) || min.value <= 1) 1565 return; 1566 1567 add_comparison(expr->left, '<', r_left); 1568 } 1569 1570 static void match_binop_assign(struct expression *expr) 1571 { 1572 struct expression *right; 1573 1574 right = strip_expr(expr->right); 1575 if (right->op == '+') 1576 match_assign_add(expr); 1577 if (right->op == '-') 1578 match_assign_sub(expr); 1579 if (right->op == '/') 1580 match_assign_divide(expr); 1581 } 1582 1583 static void copy_comparisons(struct expression *left, struct expression *right) 1584 { 1585 struct string_list *links; 1586 struct smatch_state *state; 1587 struct compare_data *data; 1588 struct symbol *left_sym, *right_sym; 1589 char *left_var = NULL; 1590 char *right_var = NULL; 1591 struct var_sym_list *left_vsl; 1592 struct expression *expr; 1593 const char *var; 1594 struct var_sym_list *vsl; 1595 int comparison; 1596 char *tmp; 1597 1598 left_var = chunk_to_var_sym(left, &left_sym); 1599 if (!left_var) 1600 goto done; 1601 left_vsl = expr_to_vsl(left); 1602 right_var = chunk_to_var_sym(right, &right_sym); 1603 if (!right_var) 1604 goto done; 1605 1606 state = get_state(link_id, right_var, right_sym); 1607 if (!state) 1608 return; 1609 links = state->data; 1610 1611 FOR_EACH_PTR(links, tmp) { 1612 state = get_state(compare_id, tmp, NULL); 1613 if (!state || !state->data) 1614 continue; 1615 data = state->data; 1616 comparison = data->comparison; 1617 expr = data->right; 1618 var = data->right_var; 1619 vsl = data->right_vsl; 1620 if (strcmp(var, right_var) == 0) { 1621 expr = data->left; 1622 var = data->left_var; 1623 vsl = data->left_vsl; 1624 comparison = flip_comparison(comparison); 1625 } 1626 /* n = copy_from_user(dest, src, n); leads to n <= n which is nonsense */ 1627 if (strcmp(left_var, var) == 0) 1628 continue; 1629 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl); 1630 } END_FOR_EACH_PTR(tmp); 1631 1632 done: 1633 free_string(right_var); 1634 } 1635 1636 static void match_assign(struct expression *expr) 1637 { 1638 struct expression *right; 1639 1640 if (expr->op != '=') 1641 return; 1642 if (__in_fake_assign || outside_of_function()) 1643 return; 1644 1645 if (is_struct(expr->left)) 1646 return; 1647 1648 if (is_self_assign(expr)) 1649 return; 1650 1651 copy_comparisons(expr->left, expr->right); 1652 add_comparison(expr->left, SPECIAL_EQUAL, expr->right); 1653 1654 right = strip_expr(expr->right); 1655 if (right->type == EXPR_BINOP) 1656 match_binop_assign(expr); 1657 } 1658 1659 int get_comparison_strings(const char *one, const char *two) 1660 { 1661 char buf[256]; 1662 struct smatch_state *state; 1663 int invert = 0; 1664 int ret = 0; 1665 1666 if (!one || !two) 1667 return UNKNOWN_COMPARISON; 1668 1669 if (strcmp(one, two) == 0) 1670 return SPECIAL_EQUAL; 1671 1672 if (strcmp(one, two) > 0) { 1673 const char *tmp = one; 1674 1675 one = two; 1676 two = tmp; 1677 invert = 1; 1678 } 1679 1680 snprintf(buf, sizeof(buf), "%s vs %s", one, two); 1681 state = get_state(compare_id, buf, NULL); 1682 if (state) 1683 ret = state_to_comparison(state); 1684 1685 if (invert) 1686 ret = flip_comparison(ret); 1687 1688 return ret; 1689 } 1690 1691 static int get_comparison_helper(struct expression *a, struct expression *b, bool use_extra) 1692 { 1693 char *one = NULL; 1694 char *two = NULL; 1695 int ret = UNKNOWN_COMPARISON; 1696 int extra = UNKNOWN_COMPARISON; 1697 1698 if (a == UNKNOWN_COMPARISON || 1699 b == UNKNOWN_COMPARISON) 1700 return UNKNOWN_COMPARISON; 1701 1702 a = strip_parens(a); 1703 b = strip_parens(b); 1704 1705 move_plus_to_minus(&a, &b); 1706 1707 one = chunk_to_var(a); 1708 if (!one) 1709 goto free; 1710 two = chunk_to_var(b); 1711 if (!two) 1712 goto free; 1713 1714 ret = get_comparison_strings(one, two); 1715 if (ret) 1716 goto free; 1717 1718 if (is_plus_one(a) || is_minus_one(a)) { 1719 free_string(one); 1720 one = chunk_to_var(a->left); 1721 ret = get_comparison_strings(one, two); 1722 } else if (is_plus_one(b) || is_minus_one(b)) { 1723 free_string(two); 1724 two = chunk_to_var(b->left); 1725 ret = get_comparison_strings(one, two); 1726 } 1727 1728 if (ret == UNKNOWN_COMPARISON) 1729 goto free; 1730 1731 if ((is_plus_one(a) || is_minus_one(b)) && ret == '<') 1732 ret = SPECIAL_LTE; 1733 else if ((is_minus_one(a) || is_plus_one(b)) && ret == '>') 1734 ret = SPECIAL_GTE; 1735 else 1736 ret = UNKNOWN_COMPARISON; 1737 1738 free: 1739 free_string(one); 1740 free_string(two); 1741 1742 extra = comparison_from_extra(a, b); 1743 return comparison_intersection(ret, extra); 1744 } 1745 1746 int get_comparison(struct expression *a, struct expression *b) 1747 { 1748 return get_comparison_helper(a, b, true); 1749 } 1750 1751 int get_comparison_no_extra(struct expression *a, struct expression *b) 1752 { 1753 return get_comparison_helper(a, b, false); 1754 } 1755 1756 int possible_comparison(struct expression *a, int comparison, struct expression *b) 1757 { 1758 char *one = NULL; 1759 char *two = NULL; 1760 int ret = 0; 1761 char buf[256]; 1762 struct sm_state *sm; 1763 int saved; 1764 1765 one = chunk_to_var(a); 1766 if (!one) 1767 goto free; 1768 two = chunk_to_var(b); 1769 if (!two) 1770 goto free; 1771 1772 1773 if (strcmp(one, two) == 0 && comparison == SPECIAL_EQUAL) { 1774 ret = 1; 1775 goto free; 1776 } 1777 1778 if (strcmp(one, two) > 0) { 1779 char *tmp = one; 1780 1781 one = two; 1782 two = tmp; 1783 comparison = flip_comparison(comparison); 1784 } 1785 1786 snprintf(buf, sizeof(buf), "%s vs %s", one, two); 1787 sm = get_sm_state(compare_id, buf, NULL); 1788 if (!sm) 1789 goto free; 1790 1791 FOR_EACH_PTR(sm->possible, sm) { 1792 if (!sm->state->data) 1793 continue; 1794 saved = ((struct compare_data *)sm->state->data)->comparison; 1795 if (saved == comparison) 1796 ret = 1; 1797 if (comparison == SPECIAL_EQUAL && 1798 (saved == SPECIAL_LTE || 1799 saved == SPECIAL_GTE || 1800 saved == SPECIAL_UNSIGNED_LTE || 1801 saved == SPECIAL_UNSIGNED_GTE)) 1802 ret = 1; 1803 if (ret == 1) 1804 goto free; 1805 } END_FOR_EACH_PTR(sm); 1806 1807 return ret; 1808 free: 1809 free_string(one); 1810 free_string(two); 1811 return ret; 1812 } 1813 1814 struct state_list *get_all_comparisons(struct expression *expr) 1815 { 1816 struct smatch_state *state; 1817 struct string_list *links; 1818 struct state_list *ret = NULL; 1819 struct sm_state *sm; 1820 char *tmp; 1821 1822 state = get_state_chunk(link_id, expr); 1823 if (!state) 1824 return NULL; 1825 links = state->data; 1826 1827 FOR_EACH_PTR(links, tmp) { 1828 sm = get_sm_state(compare_id, tmp, NULL); 1829 if (!sm) 1830 continue; 1831 // FIXME have to compare name with vsl 1832 add_ptr_list(&ret, sm); 1833 } END_FOR_EACH_PTR(tmp); 1834 1835 return ret; 1836 } 1837 1838 struct state_list *get_all_possible_equal_comparisons(struct expression *expr) 1839 { 1840 struct smatch_state *state; 1841 struct string_list *links; 1842 struct state_list *ret = NULL; 1843 struct sm_state *sm; 1844 char *tmp; 1845 1846 state = get_state_chunk(link_id, expr); 1847 if (!state) 1848 return NULL; 1849 links = state->data; 1850 1851 FOR_EACH_PTR(links, tmp) { 1852 sm = get_sm_state(compare_id, tmp, NULL); 1853 if (!sm) 1854 continue; 1855 if (!strchr(sm->state->name, '=')) 1856 continue; 1857 if (strcmp(sm->state->name, "!=") == 0) 1858 continue; 1859 add_ptr_list(&ret, sm); 1860 } END_FOR_EACH_PTR(tmp); 1861 1862 return ret; 1863 } 1864 1865 struct state_list *get_all_possible_not_equal_comparisons(struct expression *expr) 1866 { 1867 struct smatch_state *state; 1868 struct string_list *links; 1869 struct state_list *ret = NULL; 1870 struct sm_state *sm; 1871 struct sm_state *possible; 1872 char *link; 1873 1874 return NULL; 1875 1876 state = get_state_chunk(link_id, expr); 1877 if (!state) 1878 return NULL; 1879 links = state->data; 1880 1881 FOR_EACH_PTR(links, link) { 1882 sm = get_sm_state(compare_id, link, NULL); 1883 if (!sm) 1884 continue; 1885 FOR_EACH_PTR(sm->possible, possible) { 1886 if (strcmp(possible->state->name, "!=") != 0) 1887 continue; 1888 add_ptr_list(&ret, sm); 1889 break; 1890 } END_FOR_EACH_PTR(link); 1891 } END_FOR_EACH_PTR(link); 1892 1893 return ret; 1894 } 1895 1896 static void update_links_from_call(struct expression *left, 1897 int left_compare, 1898 struct expression *right) 1899 { 1900 struct string_list *links; 1901 struct smatch_state *state; 1902 struct compare_data *data; 1903 struct symbol *left_sym, *right_sym; 1904 char *left_var = NULL; 1905 char *right_var = NULL; 1906 struct var_sym_list *left_vsl; 1907 struct expression *expr; 1908 const char *var; 1909 struct var_sym_list *vsl; 1910 int comparison; 1911 char *tmp; 1912 1913 left_var = chunk_to_var_sym(left, &left_sym); 1914 if (!left_var) 1915 goto done; 1916 left_vsl = expr_to_vsl(left); 1917 right_var = chunk_to_var_sym(right, &right_sym); 1918 if (!right_var) 1919 goto done; 1920 1921 state = get_state(link_id, right_var, right_sym); 1922 if (!state) 1923 return; 1924 links = state->data; 1925 1926 FOR_EACH_PTR(links, tmp) { 1927 state = get_state(compare_id, tmp, NULL); 1928 if (!state || !state->data) 1929 continue; 1930 data = state->data; 1931 comparison = data->comparison; 1932 expr = data->right; 1933 var = data->right_var; 1934 vsl = data->right_vsl; 1935 if (strcmp(var, right_var) == 0) { 1936 expr = data->left; 1937 var = data->left_var; 1938 vsl = data->left_vsl; 1939 comparison = flip_comparison(comparison); 1940 } 1941 comparison = combine_comparisons(left_compare, comparison); 1942 if (!comparison) 1943 continue; 1944 add_comparison_var_sym(left, left_var, left_vsl, comparison, expr, var, vsl); 1945 } END_FOR_EACH_PTR(tmp); 1946 1947 done: 1948 free_string(right_var); 1949 } 1950 1951 void __add_return_comparison(struct expression *call, const char *range) 1952 { 1953 struct expression *arg; 1954 int comparison; 1955 char buf[16]; 1956 1957 if (!str_to_comparison_arg(range, call, &comparison, &arg)) 1958 return; 1959 snprintf(buf, sizeof(buf), "%s", show_comparison(comparison)); 1960 update_links_from_call(call, comparison, arg); 1961 add_comparison(call, comparison, arg); 1962 } 1963 1964 void __add_comparison_info(struct expression *expr, struct expression *call, const char *range) 1965 { 1966 copy_comparisons(expr, call); 1967 } 1968 1969 static char *get_mask_comparison(struct expression *expr, int ignore) 1970 { 1971 struct expression *tmp, *right; 1972 int count, param; 1973 char buf[256]; 1974 1975 /* The return value for "return foo & param;" is <= param */ 1976 1977 count = 0; 1978 while ((tmp = get_assigned_expr(expr))) { 1979 expr = strip_expr(tmp); 1980 if (count++ > 4) 1981 break; 1982 } 1983 1984 if (expr->type != EXPR_BINOP || expr->op != '&') 1985 return NULL; 1986 1987 right = strip_expr(expr->right); 1988 param = get_param_num(right); 1989 if (param < 0 || param == ignore) 1990 return NULL; 1991 1992 snprintf(buf, sizeof(buf), "[<=$%d]", param); 1993 return alloc_sname(buf); 1994 } 1995 1996 static char *range_comparison_to_param_helper(struct expression *expr, char starts_with, int ignore) 1997 { 1998 struct symbol *param; 1999 char *var = NULL; 2000 char buf[256]; 2001 char *ret_str = NULL; 2002 int compare; 2003 int i; 2004 2005 if (!expr) 2006 return NULL; 2007 2008 var = chunk_to_var(expr); 2009 if (!var) 2010 goto try_mask; 2011 2012 i = -1; 2013 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 2014 i++; 2015 if (i == ignore) 2016 continue; 2017 if (!param->ident) 2018 continue; 2019 snprintf(buf, sizeof(buf), "%s orig", param->ident->name); 2020 compare = get_comparison_strings(var, buf); 2021 if (compare == UNKNOWN_COMPARISON || 2022 compare == IMPOSSIBLE_COMPARISON) 2023 continue; 2024 if (show_comparison(compare)[0] != starts_with) 2025 continue; 2026 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i); 2027 ret_str = alloc_sname(buf); 2028 break; 2029 } END_FOR_EACH_PTR(param); 2030 2031 free_string(var); 2032 if (!ret_str) 2033 goto try_mask; 2034 2035 return ret_str; 2036 2037 try_mask: 2038 if (starts_with == '<') 2039 ret_str = get_mask_comparison(expr, ignore); 2040 return ret_str; 2041 } 2042 2043 char *name_sym_to_param_comparison(const char *name, struct symbol *sym) 2044 { 2045 struct symbol *param; 2046 char buf[256]; 2047 int compare; 2048 int i; 2049 2050 i = -1; 2051 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 2052 i++; 2053 if (!param->ident) 2054 continue; 2055 snprintf(buf, sizeof(buf), "%s orig", param->ident->name); 2056 compare = get_comparison_strings(name, buf); 2057 if (compare == UNKNOWN_COMPARISON || 2058 compare == IMPOSSIBLE_COMPARISON) 2059 continue; 2060 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i); 2061 return alloc_sname(buf); 2062 } END_FOR_EACH_PTR(param); 2063 2064 return NULL; 2065 } 2066 2067 char *expr_equal_to_param(struct expression *expr, int ignore) 2068 { 2069 return range_comparison_to_param_helper(expr, '=', ignore); 2070 } 2071 2072 char *expr_lte_to_param(struct expression *expr, int ignore) 2073 { 2074 return range_comparison_to_param_helper(expr, '<', ignore); 2075 } 2076 2077 char *expr_param_comparison(struct expression *expr, int ignore) 2078 { 2079 struct symbol *param; 2080 char *var = NULL; 2081 char buf[256]; 2082 char *ret_str = NULL; 2083 int compare; 2084 int i; 2085 2086 var = chunk_to_var(expr); 2087 if (!var) 2088 goto free; 2089 2090 i = -1; 2091 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, param) { 2092 i++; 2093 if (i == ignore) 2094 continue; 2095 if (!param->ident) 2096 continue; 2097 snprintf(buf, sizeof(buf), "%s orig", param->ident->name); 2098 compare = get_comparison_strings(var, buf); 2099 if (!compare) 2100 continue; 2101 snprintf(buf, sizeof(buf), "[%s$%d]", show_comparison(compare), i); 2102 ret_str = alloc_sname(buf); 2103 break; 2104 } END_FOR_EACH_PTR(param); 2105 2106 free: 2107 free_string(var); 2108 return ret_str; 2109 } 2110 2111 char *get_printed_param_name(struct expression *call, const char *param_name, struct symbol *param_sym) 2112 { 2113 struct expression *arg; 2114 char *name; 2115 struct symbol *sym; 2116 static char buf[256]; 2117 int len; 2118 int i; 2119 2120 i = -1; 2121 FOR_EACH_PTR(call->args, arg) { 2122 i++; 2123 2124 name = expr_to_var_sym(arg, &sym); 2125 if (!name || !sym) 2126 continue; 2127 if (sym != param_sym) 2128 continue; 2129 2130 len = strlen(name); 2131 if (strncmp(name, param_name, len) != 0) 2132 continue; 2133 if (param_name[len] == '\0') { 2134 snprintf(buf, sizeof(buf), "$%d", i); 2135 return buf; 2136 } 2137 if (param_name[len] != '-') 2138 continue; 2139 snprintf(buf, sizeof(buf), "$%d%s", i, param_name + len); 2140 return buf; 2141 } END_FOR_EACH_PTR(arg); 2142 2143 return NULL; 2144 } 2145 2146 static void match_call_info(struct expression *expr) 2147 { 2148 struct expression *arg; 2149 struct smatch_state *state; 2150 struct sm_state *sm; 2151 struct compare_data *data; 2152 int comparison; 2153 struct string_list *links; 2154 char *arg_name; 2155 const char *right_name; 2156 char *link; 2157 char info_buf[256]; 2158 int i; 2159 2160 i = -1; 2161 FOR_EACH_PTR(expr->args, arg) { 2162 i++; 2163 2164 state = get_state_chunk(link_id, arg); 2165 if (!state) 2166 continue; 2167 2168 links = state->data; 2169 FOR_EACH_PTR(links, link) { 2170 struct var_sym_list *right_vsl; 2171 struct var_sym *right_vs; 2172 2173 2174 if (strstr(link, " orig")) 2175 continue; 2176 sm = get_sm_state(compare_id, link, NULL); 2177 if (!sm) 2178 continue; 2179 data = sm->state->data; 2180 if (!data || 2181 data->comparison == UNKNOWN_COMPARISON || 2182 data->comparison == IMPOSSIBLE_COMPARISON) 2183 continue; 2184 arg_name = expr_to_var(arg); 2185 if (!arg_name) 2186 continue; 2187 2188 right_vsl = NULL; 2189 if (strcmp(data->left_var, arg_name) == 0) { 2190 comparison = data->comparison; 2191 right_name = data->right_var; 2192 right_vsl = data->right_vsl; 2193 } else if (strcmp(data->right_var, arg_name) == 0) { 2194 comparison = flip_comparison(data->comparison); 2195 right_name = data->left_var; 2196 right_vsl = data->left_vsl; 2197 } 2198 if (!right_vsl || ptr_list_size((struct ptr_list *)right_vsl) != 1) 2199 goto free; 2200 2201 right_vs = first_ptr_list((struct ptr_list *)right_vsl); 2202 if (strcmp(right_vs->var, right_name) != 0) 2203 goto free; 2204 right_name = get_printed_param_name(expr, right_vs->var, right_vs->sym); 2205 if (!right_name) 2206 goto free; 2207 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(comparison), right_name); 2208 sql_insert_caller_info(expr, PARAM_COMPARE, i, "$", info_buf); 2209 2210 free: 2211 free_string(arg_name); 2212 } END_FOR_EACH_PTR(link); 2213 } END_FOR_EACH_PTR(arg); 2214 } 2215 2216 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *link_sm) 2217 { 2218 struct sm_state *compare_sm; 2219 struct string_list *links; 2220 char *link; 2221 struct compare_data *data; 2222 struct var_sym *left, *right; 2223 static char info_buf[256]; 2224 const char *right_name; 2225 2226 if (strstr(printed_name, " orig")) 2227 return; 2228 2229 links = link_sm->state->data; 2230 FOR_EACH_PTR(links, link) { 2231 compare_sm = get_sm_state(compare_id, link, NULL); 2232 if (!compare_sm) 2233 continue; 2234 data = compare_sm->state->data; 2235 if (!data || !data->comparison) 2236 continue; 2237 2238 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 || 2239 ptr_list_size((struct ptr_list *)data->right_vsl) != 1) 2240 continue; 2241 left = first_ptr_list((struct ptr_list *)data->left_vsl); 2242 right = first_ptr_list((struct ptr_list *)data->right_vsl); 2243 if (left->sym == right->sym && 2244 strcmp(left->var, right->var) == 0) 2245 continue; 2246 /* 2247 * Both parameters link to this comparison so only 2248 * record the first one. 2249 */ 2250 if (left->sym != link_sm->sym || 2251 strcmp(left->var, link_sm->name) != 0) 2252 continue; 2253 2254 right_name = get_printed_param_name(call, right->var, right->sym); 2255 if (!right_name) 2256 continue; 2257 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_name); 2258 sql_insert_caller_info(call, PARAM_COMPARE, param, printed_name, info_buf); 2259 } END_FOR_EACH_PTR(link); 2260 } 2261 2262 static void print_return_value_comparison(int return_id, char *return_ranges, struct expression *expr) 2263 { 2264 char *name; 2265 const char *tmp_name; 2266 struct symbol *sym; 2267 int param; 2268 char info_buf[256]; 2269 2270 /* 2271 * TODO: This only prints == comparisons. That's probably the most 2272 * useful comparison because == max has lots of implications. But it 2273 * would be good to capture the rest as well. 2274 * 2275 * This information is already in the DB but it's in the parameter math 2276 * bits and it's awkward to use it. This is is the simpler, possibly 2277 * cleaner way, but not necessarily the best, I don't know. 2278 */ 2279 2280 if (!expr) 2281 return; 2282 name = expr_to_var_sym(expr, &sym); 2283 if (!name || !sym) 2284 goto free; 2285 2286 param = get_param_num_from_sym(sym); 2287 if (param < 0) 2288 goto free; 2289 if (param_was_set_var_sym(name, sym)) 2290 goto free; 2291 2292 tmp_name = get_param_name_var_sym(name, sym); 2293 if (!tmp_name) 2294 goto free; 2295 2296 snprintf(info_buf, sizeof(info_buf), "== $%d%s", param, tmp_name + 1); 2297 sql_insert_return_states(return_id, return_ranges, 2298 PARAM_COMPARE, -1, "$", info_buf); 2299 free: 2300 free_string(name); 2301 } 2302 2303 static void print_return_comparison(int return_id, char *return_ranges, struct expression *expr) 2304 { 2305 struct sm_state *tmp; 2306 struct string_list *links; 2307 char *link; 2308 struct sm_state *sm; 2309 struct compare_data *data; 2310 struct var_sym *left, *right; 2311 int left_param, right_param; 2312 char left_buf[256]; 2313 char right_buf[256]; 2314 char info_buf[258]; 2315 const char *tmp_name; 2316 2317 print_return_value_comparison(return_id, return_ranges, expr); 2318 2319 FOR_EACH_MY_SM(link_id, __get_cur_stree(), tmp) { 2320 if (get_param_num_from_sym(tmp->sym) < 0) 2321 continue; 2322 links = tmp->state->data; 2323 FOR_EACH_PTR(links, link) { 2324 sm = get_sm_state(compare_id, link, NULL); 2325 if (!sm) 2326 continue; 2327 data = sm->state->data; 2328 if (!data || 2329 data->comparison == UNKNOWN_COMPARISON || 2330 data->comparison == IMPOSSIBLE_COMPARISON) 2331 continue; 2332 if (ptr_list_size((struct ptr_list *)data->left_vsl) != 1 || 2333 ptr_list_size((struct ptr_list *)data->right_vsl) != 1) 2334 continue; 2335 left = first_ptr_list((struct ptr_list *)data->left_vsl); 2336 right = first_ptr_list((struct ptr_list *)data->right_vsl); 2337 if (left->sym == right->sym && 2338 strcmp(left->var, right->var) == 0) 2339 continue; 2340 /* 2341 * Both parameters link to this comparison so only 2342 * record the first one. 2343 */ 2344 if (left->sym != tmp->sym || 2345 strcmp(left->var, tmp->name) != 0) 2346 continue; 2347 2348 if (strstr(right->var, " orig")) 2349 continue; 2350 2351 left_param = get_param_num_from_sym(left->sym); 2352 right_param = get_param_num_from_sym(right->sym); 2353 if (left_param < 0 || right_param < 0) 2354 continue; 2355 2356 tmp_name = get_param_name_var_sym(left->var, left->sym); 2357 if (!tmp_name) 2358 continue; 2359 snprintf(left_buf, sizeof(left_buf), "%s", tmp_name); 2360 2361 tmp_name = get_param_name_var_sym(right->var, right->sym); 2362 if (!tmp_name || tmp_name[0] != '$') 2363 continue; 2364 snprintf(right_buf, sizeof(right_buf), "$%d%s", right_param, tmp_name + 1); 2365 2366 /* 2367 * FIXME: this should reject $ type variables (as 2368 * opposed to $->foo type). Those should come from 2369 * smatch_param_compare_limit.c. 2370 */ 2371 2372 snprintf(info_buf, sizeof(info_buf), "%s %s", show_comparison(data->comparison), right_buf); 2373 sql_insert_return_states(return_id, return_ranges, 2374 PARAM_COMPARE, left_param, left_buf, info_buf); 2375 } END_FOR_EACH_PTR(link); 2376 2377 } END_FOR_EACH_SM(tmp); 2378 } 2379 2380 static int parse_comparison(char **value, int *op) 2381 { 2382 2383 *op = **value; 2384 2385 switch (*op) { 2386 case '<': 2387 (*value)++; 2388 if (**value == '=') { 2389 (*value)++; 2390 *op = SPECIAL_LTE; 2391 } 2392 break; 2393 case '=': 2394 (*value)++; 2395 (*value)++; 2396 *op = SPECIAL_EQUAL; 2397 break; 2398 case '!': 2399 (*value)++; 2400 (*value)++; 2401 *op = SPECIAL_NOTEQUAL; 2402 break; 2403 case '>': 2404 (*value)++; 2405 if (**value == '=') { 2406 (*value)++; 2407 *op = SPECIAL_GTE; 2408 } 2409 break; 2410 default: 2411 return 0; 2412 } 2413 2414 if (**value != ' ') { 2415 sm_perror("parsing comparison. %s", *value); 2416 return 0; 2417 } 2418 2419 (*value)++; 2420 return 1; 2421 } 2422 2423 static int split_op_param_key(char *value, int *op, int *param, char **key) 2424 { 2425 static char buf[256]; 2426 char *p; 2427 2428 if (!parse_comparison(&value, op)) 2429 return 0; 2430 2431 snprintf(buf, sizeof(buf), "%s", value); 2432 2433 p = buf; 2434 if (*p++ != '$') 2435 return 0; 2436 2437 *param = atoi(p); 2438 if (*param < 0 || *param > 99) 2439 return 0; 2440 p++; 2441 if (*param > 9) 2442 p++; 2443 p--; 2444 *p = '$'; 2445 *key = p; 2446 2447 return 1; 2448 } 2449 2450 static void db_return_comparison(struct expression *expr, int left_param, char *key, char *value) 2451 { 2452 struct expression *left_arg, *right_arg; 2453 char *left_name = NULL; 2454 struct symbol *left_sym; 2455 char *right_name = NULL; 2456 struct symbol *right_sym; 2457 int op; 2458 int right_param; 2459 char *right_key; 2460 struct var_sym_list *left_vsl = NULL, *right_vsl = NULL; 2461 2462 if (left_param == -1) { 2463 if (expr->type != EXPR_ASSIGNMENT) 2464 return; 2465 left_arg = strip_expr(expr->left); 2466 2467 while (expr->type == EXPR_ASSIGNMENT) 2468 expr = strip_expr(expr->right); 2469 if (expr->type != EXPR_CALL) 2470 return; 2471 } else { 2472 while (expr->type == EXPR_ASSIGNMENT) 2473 expr = strip_expr(expr->right); 2474 if (expr->type != EXPR_CALL) 2475 return; 2476 2477 left_arg = get_argument_from_call_expr(expr->args, left_param); 2478 if (!left_arg) 2479 return; 2480 } 2481 2482 if (!split_op_param_key(value, &op, &right_param, &right_key)) 2483 return; 2484 2485 right_arg = get_argument_from_call_expr(expr->args, right_param); 2486 if (!right_arg) 2487 return; 2488 2489 left_name = get_variable_from_key(left_arg, key, &left_sym); 2490 if (!left_name || !left_sym) 2491 goto free; 2492 2493 right_name = get_variable_from_key(right_arg, right_key, &right_sym); 2494 if (!right_name || !right_sym) 2495 goto free; 2496 2497 add_var_sym(&left_vsl, left_name, left_sym); 2498 add_var_sym(&right_vsl, right_name, right_sym); 2499 2500 add_comparison_var_sym(NULL, left_name, left_vsl, op, NULL, right_name, right_vsl); 2501 2502 free: 2503 free_string(left_name); 2504 free_string(right_name); 2505 } 2506 2507 int param_compare_limit_is_impossible(struct expression *expr, int left_param, char *left_key, char *value) 2508 { 2509 struct smatch_state *state; 2510 char *left_name = NULL; 2511 char *right_name = NULL; 2512 struct symbol *left_sym, *right_sym; 2513 struct expression *left_arg, *right_arg; 2514 int op, state_op; 2515 int right_param; 2516 char *right_key; 2517 int ret = 0; 2518 char buf[256]; 2519 2520 while (expr->type == EXPR_ASSIGNMENT) 2521 expr = strip_expr(expr->right); 2522 if (expr->type != EXPR_CALL) 2523 return 0; 2524 2525 if (!split_op_param_key(value, &op, &right_param, &right_key)) 2526 return 0; 2527 2528 left_arg = get_argument_from_call_expr(expr->args, left_param); 2529 if (!left_arg) 2530 return 0; 2531 2532 right_arg = get_argument_from_call_expr(expr->args, right_param); 2533 if (!right_arg) 2534 return 0; 2535 2536 left_name = get_variable_from_key(left_arg, left_key, &left_sym); 2537 right_name = get_variable_from_key(right_arg, right_key, &right_sym); 2538 if (!left_name || !right_name) 2539 goto free; 2540 2541 snprintf(buf, sizeof(buf), "%s vs %s", left_name, right_name); 2542 state = get_state(compare_id, buf, NULL); 2543 if (!state) 2544 goto free; 2545 state_op = state_to_comparison(state); 2546 if (!state_op) 2547 goto free; 2548 2549 if (!comparison_intersection(remove_unsigned_from_comparison(state_op), op)) 2550 ret = 1; 2551 free: 2552 free_string(left_name); 2553 free_string(right_name); 2554 return ret; 2555 } 2556 2557 int impossibly_high_comparison(struct expression *expr) 2558 { 2559 struct smatch_state *link_state; 2560 struct sm_state *sm; 2561 struct string_list *links; 2562 char *link; 2563 struct compare_data *data; 2564 2565 link_state = get_state_expr(link_id, expr); 2566 if (!link_state) { 2567 if (expr->type == EXPR_BINOP && 2568 (impossibly_high_comparison(expr->left) || 2569 impossibly_high_comparison(expr->right))) 2570 return 1; 2571 return 0; 2572 } 2573 2574 links = link_state->data; 2575 FOR_EACH_PTR(links, link) { 2576 sm = get_sm_state(compare_id, link, NULL); 2577 if (!sm) 2578 continue; 2579 data = sm->state->data; 2580 if (!data) 2581 continue; 2582 if (!possibly_true(data->left, data->comparison, data->right)) 2583 return 1; 2584 } END_FOR_EACH_PTR(link); 2585 2586 return 0; 2587 } 2588 2589 static void free_data(struct symbol *sym) 2590 { 2591 if (__inline_fn) 2592 return; 2593 clear_compare_data_alloc(); 2594 } 2595 2596 void register_comparison(int id) 2597 { 2598 compare_id = id; 2599 set_dynamic_states(compare_id); 2600 add_hook(&save_start_states, AFTER_DEF_HOOK); 2601 add_unmatched_state_hook(compare_id, unmatched_comparison); 2602 add_pre_merge_hook(compare_id, &pre_merge_hook); 2603 add_merge_hook(compare_id, &merge_compare_states); 2604 add_hook(&free_data, AFTER_FUNC_HOOK); 2605 add_hook(&match_call_info, FUNCTION_CALL_HOOK); 2606 add_split_return_callback(&print_return_comparison); 2607 2608 select_return_states_hook(PARAM_COMPARE, &db_return_comparison); 2609 add_hook(&match_preop, OP_HOOK); 2610 } 2611 2612 void register_comparison_late(int id) 2613 { 2614 add_hook(&match_assign, ASSIGNMENT_HOOK); 2615 } 2616 2617 void register_comparison_links(int id) 2618 { 2619 link_id = id; 2620 db_ignore_states(link_id); 2621 set_dynamic_states(link_id); 2622 add_merge_hook(link_id, &merge_links); 2623 add_modification_hook(link_id, &match_modify); 2624 add_modification_hook_late(link_id, match_inc_dec); 2625 2626 add_member_info_callback(link_id, struct_member_callback); 2627 } 2628 2629 void register_comparison_inc_dec(int id) 2630 { 2631 inc_dec_id = id; 2632 add_modification_hook_late(inc_dec_id, &iter_modify); 2633 } 2634 2635 void register_comparison_inc_dec_links(int id) 2636 { 2637 inc_dec_link_id = id; 2638 set_dynamic_states(inc_dec_link_id); 2639 set_up_link_functions(inc_dec_id, inc_dec_link_id); 2640 } 2641 2642 static void filter_by_sm(struct sm_state *sm, int op, 2643 struct state_list **true_stack, 2644 struct state_list **false_stack) 2645 { 2646 struct compare_data *data; 2647 int is_true = 0; 2648 int is_false = 0; 2649 2650 if (!sm) 2651 return; 2652 data = sm->state->data; 2653 if (!data || data->comparison == UNKNOWN_COMPARISON) 2654 goto split; 2655 if (data->comparison == IMPOSSIBLE_COMPARISON) 2656 return; 2657 2658 /* 2659 * We want to check that "data->comparison" is totally inside "op". So 2660 * if data->comparison is < and op is <= then that's true. Or if 2661 * data->comparison is == and op is <= then that's true. But if 2662 * data->comparison is <= and op is < than that's neither true nor 2663 * false. 2664 */ 2665 if (data->comparison == comparison_intersection(data->comparison, op)) 2666 is_true = 1; 2667 if (data->comparison == comparison_intersection(data->comparison, negate_comparison(op))) 2668 is_false = 1; 2669 2670 if (debug_implied()) { 2671 sm_msg("%s: %s: op = '%s' negated '%s'. true_intersect = '%s' false_insersect = '%s' sm = '%s'", 2672 __func__, 2673 sm->state->name, 2674 alloc_sname(show_comparison(op)), 2675 alloc_sname(show_comparison(negate_comparison(op))), 2676 alloc_sname(show_comparison(comparison_intersection(data->comparison, op))), 2677 alloc_sname(show_comparison(comparison_intersection(data->comparison, negate_comparison(op)))), 2678 show_sm(sm)); 2679 } 2680 2681 if (is_true) 2682 add_ptr_list(true_stack, sm); 2683 if (is_false) 2684 add_ptr_list(false_stack, sm); 2685 split: 2686 filter_by_sm(sm->left, op, true_stack, false_stack); 2687 filter_by_sm(sm->right, op, true_stack, false_stack); 2688 } 2689 2690 struct sm_state *comparison_implication_hook(struct expression *expr, 2691 struct state_list **true_stack, 2692 struct state_list **false_stack) 2693 { 2694 struct sm_state *sm; 2695 char *left, *right; 2696 int op; 2697 static char buf[256]; 2698 2699 if (expr->type != EXPR_COMPARE) 2700 return NULL; 2701 2702 op = expr->op; 2703 2704 left = expr_to_var(expr->left); 2705 right = expr_to_var(expr->right); 2706 if (!left || !right) { 2707 free_string(left); 2708 free_string(right); 2709 return NULL; 2710 } 2711 2712 if (strcmp(left, right) > 0) { 2713 char *tmp = left; 2714 2715 left = right; 2716 right = tmp; 2717 op = flip_comparison(op); 2718 } 2719 2720 snprintf(buf, sizeof(buf), "%s vs %s", left, right); 2721 sm = get_sm_state(compare_id, buf, NULL); 2722 if (!sm) 2723 return NULL; 2724 if (!sm->merged) 2725 return NULL; 2726 2727 filter_by_sm(sm, op, true_stack, false_stack); 2728 if (!*true_stack && !*false_stack) 2729 return NULL; 2730 2731 if (debug_implied()) 2732 sm_msg("implications from comparison: (%s)", show_sm(sm)); 2733 2734 return sm; 2735 } 2736