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