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