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