1 /* 2 * Copyright (C) 2006,2008 Dan Carpenter. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License 6 * as published by the Free Software Foundation; either version 2 7 * of the License, or (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt 16 */ 17 18 /* 19 * The simplest type of condition is 20 * if (a) { ... 21 * 22 * The next simplest kind of conditions is 23 * if (a && b) { c; 24 * In that case 'a' is true when we get to 'b' and both are true 25 * when we get to c. 26 * 27 * Or's are a little more complicated. 28 * if (a || b) { c; 29 * We know 'a' is not true when we get to 'b' but it may be true 30 * when we get to c. 31 * 32 * If we mix and's and or's that's even more complicated. 33 * if (a && b && c || a && d) { d ; 34 * 'a' is true when we evaluate 'b', and 'd'. 35 * 'b' is true when we evaluate 'c' but otherwise we don't. 36 * 37 * The other thing that complicates matters is if we negate 38 * some if conditions. 39 * if (!a) { ... 40 * Smatch has passes the un-negated version to the client and flip 41 * the true and false values internally. This makes it easier 42 * to write checks. 43 * 44 * And negations can be part of a compound. 45 * if (a && !(b || c)) { d; 46 * In that situation we multiply the negative through to simplify 47 * stuff so that we can remove the parens like this: 48 * if (a && !b && !c) { d; 49 * 50 * One other thing is that: 51 * if ((a) != 0){ ... 52 * that's basically the same as testing for just 'a' and we simplify 53 * comparisons with zero before passing it to the script. 54 * 55 */ 56 57 #include "smatch.h" 58 #include "smatch_slist.h" 59 #include "smatch_extra.h" 60 #include "smatch_expression_stacks.h" 61 62 extern int __expr_stmt_count; 63 64 struct expression_list *big_condition_stack; 65 66 static void split_conditions(struct expression *expr); 67 68 static int is_logical_and(struct expression *expr) 69 { 70 if (expr->op == SPECIAL_LOGICAL_AND) 71 return 1; 72 return 0; 73 } 74 75 static int handle_zero_comparisons(struct expression *expr) 76 { 77 struct expression *tmp = NULL; 78 struct expression *zero; 79 80 // if left is zero or right is zero 81 if (expr_is_zero(expr->left)) { 82 zero = strip_expr(expr->left); 83 if (zero->type != EXPR_VALUE) 84 __split_expr(expr->left); 85 tmp = expr->right; 86 } else if (expr_is_zero(expr->right)) { 87 zero = strip_expr(expr->left); 88 if (zero->type != EXPR_VALUE) 89 __split_expr(expr->right); 90 tmp = expr->left; 91 } else { 92 return 0; 93 } 94 95 // "if (foo != 0)" is the same as "if (foo)" 96 if (expr->op == SPECIAL_NOTEQUAL) { 97 split_conditions(tmp); 98 return 1; 99 } 100 101 // "if (foo == 0)" is the same as "if (!foo)" 102 if (expr->op == SPECIAL_EQUAL) { 103 split_conditions(tmp); 104 __negate_cond_stacks(); 105 return 1; 106 } 107 108 return 0; 109 } 110 111 /* 112 * This function is for handling calls to likely/unlikely 113 */ 114 115 static int ignore_builtin_expect(struct expression *expr) 116 { 117 if (sym_name_is("__builtin_expect", expr->fn)) { 118 split_conditions(first_ptr_list((struct ptr_list *) expr->args)); 119 return 1; 120 } 121 return 0; 122 } 123 124 /* 125 * handle_compound_stmt() is for: foo = ({blah; blah; blah; 1}) 126 */ 127 128 static void handle_compound_stmt(struct statement *stmt) 129 { 130 struct expression *expr = NULL; 131 struct statement *last; 132 struct statement *s; 133 134 last = last_ptr_list((struct ptr_list *)stmt->stmts); 135 if (last->type == STMT_LABEL) { 136 if (last->label_statement && 137 last->label_statement->type == STMT_EXPRESSION) 138 expr = last->label_statement->expression; 139 else 140 last = NULL; 141 } else if (last->type != STMT_EXPRESSION) { 142 last = NULL; 143 } else { 144 expr = last->expression; 145 } 146 147 FOR_EACH_PTR(stmt->stmts, s) { 148 if (s != last) 149 __split_stmt(s); 150 } END_FOR_EACH_PTR(s); 151 if (last && last->type == STMT_LABEL) 152 __split_label_stmt(last); 153 split_conditions(expr); 154 } 155 156 static int handle_preop(struct expression *expr) 157 { 158 struct statement *stmt; 159 160 if (expr->op == '!') { 161 split_conditions(expr->unop); 162 __negate_cond_stacks(); 163 return 1; 164 } 165 stmt = get_expression_statement(expr); 166 if (stmt) { 167 handle_compound_stmt(stmt); 168 return 1; 169 } 170 return 0; 171 } 172 173 static void handle_logical(struct expression *expr) 174 { 175 /* 176 * If we come to an "and" expr then: 177 * We split the left side. 178 * We keep all the current states. 179 * We split the right side. 180 * We keep all the states from both true sides. 181 * 182 * If it's an "or" expr then: 183 * We save the current slist. 184 * We split the left side. 185 * We use the false states for the right side. 186 * We split the right side. 187 * We save all the states that are the same on both sides. 188 */ 189 190 split_conditions(expr->left); 191 192 if (is_logical_and(expr)) 193 __use_cond_true_states(); 194 else 195 __use_cond_false_states(); 196 197 __push_cond_stacks(); 198 199 __save_pre_cond_states(); 200 split_conditions(expr->right); 201 __discard_pre_cond_states(); 202 203 if (is_logical_and(expr)) 204 __and_cond_states(); 205 else 206 __or_cond_states(); 207 208 __use_cond_true_states(); 209 } 210 211 static struct stree *combine_strees(struct stree *orig, struct stree *fake, struct stree *new) 212 { 213 struct stree *ret = NULL; 214 215 overwrite_stree(orig, &ret); 216 overwrite_stree(fake, &ret); 217 overwrite_stree(new, &ret); 218 free_stree(&new); 219 220 return ret; 221 } 222 223 /* 224 * handle_select() 225 * if ((aaa()?bbb():ccc())) { ... 226 * 227 * This is almost the same as: 228 * if ((aaa() && bbb()) || (!aaa() && ccc())) { ... 229 * 230 * It's a bit complicated because we shouldn't pass aaa() 231 * to the clients more than once. 232 */ 233 234 static void handle_select(struct expression *expr) 235 { 236 struct stree *a_T = NULL; 237 struct stree *a_F = NULL; 238 struct stree *a_T_b_T = NULL; 239 struct stree *a_T_b_F = NULL; 240 struct stree *a_T_b_fake = NULL; 241 struct stree *a_F_c_T = NULL; 242 struct stree *a_F_c_F = NULL; 243 struct stree *a_F_c_fake = NULL; 244 struct stree *tmp; 245 struct sm_state *sm; 246 247 /* 248 * Imagine we have this: if (a ? b : c) { ... 249 * 250 * The condition is true if "a" is true and "b" is true or 251 * "a" is false and "c" is true. It's false if "a" is true 252 * and "b" is false or "a" is false and "c" is false. 253 * 254 * The variable name "a_T_b_T" stands for "a true b true" etc. 255 * 256 * But if we know "b" is true then we can simpilify things. 257 * The condition is true if "a" is true or if "a" is false and 258 * "c" is true. The only way the condition can be false is if 259 * "a" is false and "c" is false. 260 * 261 * The remaining thing is the "a_T_b_fake". When we simplify 262 * the equations we have to take into consideration that other 263 * states may have changed that don't play into the true false 264 * equation. Take the following example: 265 * if ({ 266 * (flags) = __raw_local_irq_save(); 267 * _spin_trylock(lock) ? 1 : 268 * ({ raw_local_irq_restore(flags); 0; }); 269 * }) 270 * Smatch has to record that the irq flags were restored on the 271 * false path. 272 * 273 */ 274 275 __save_pre_cond_states(); 276 277 split_conditions(expr->conditional); 278 279 a_T = __copy_cond_true_states(); 280 a_F = __copy_cond_false_states(); 281 282 __use_cond_true_states(); 283 284 __push_cond_stacks(); 285 __push_fake_cur_stree(); 286 split_conditions(expr->cond_true); 287 __process_post_op_stack(); 288 a_T_b_fake = __pop_fake_cur_stree(); 289 a_T_b_T = combine_strees(a_T, a_T_b_fake, __pop_cond_true_stack()); 290 a_T_b_F = combine_strees(a_T, a_T_b_fake, __pop_cond_false_stack()); 291 292 __use_cond_false_states(); 293 294 __push_cond_stacks(); 295 __push_fake_cur_stree(); 296 split_conditions(expr->cond_false); 297 a_F_c_fake = __pop_fake_cur_stree(); 298 a_F_c_T = combine_strees(a_F, a_F_c_fake, __pop_cond_true_stack()); 299 a_F_c_F = combine_strees(a_F, a_F_c_fake, __pop_cond_false_stack()); 300 301 /* We have to restore the pre condition states so that 302 implied_condition_true() will use the right cur_stree */ 303 __use_pre_cond_states(); 304 305 if (implied_condition_true(expr->cond_true)) { 306 free_stree(&a_T_b_T); 307 free_stree(&a_T_b_F); 308 a_T_b_T = clone_stree(a_T); 309 overwrite_stree(a_T_b_fake, &a_T_b_T); 310 } 311 if (implied_condition_false(expr->cond_true)) { 312 free_stree(&a_T_b_T); 313 free_stree(&a_T_b_F); 314 a_T_b_F = clone_stree(a_T); 315 overwrite_stree(a_T_b_fake, &a_T_b_F); 316 } 317 if (implied_condition_true(expr->cond_false)) { 318 free_stree(&a_F_c_T); 319 free_stree(&a_F_c_F); 320 a_F_c_T = clone_stree(a_F); 321 overwrite_stree(a_F_c_fake, &a_F_c_T); 322 } 323 if (implied_condition_false(expr->cond_false)) { 324 free_stree(&a_F_c_T); 325 free_stree(&a_F_c_F); 326 a_F_c_F = clone_stree(a_F); 327 overwrite_stree(a_F_c_fake, &a_F_c_F); 328 } 329 330 merge_stree(&a_T_b_T, a_F_c_T); 331 merge_stree(&a_T_b_F, a_F_c_F); 332 333 tmp = __pop_cond_true_stack(); 334 free_stree(&tmp); 335 tmp = __pop_cond_false_stack(); 336 free_stree(&tmp); 337 338 __push_cond_stacks(); 339 FOR_EACH_SM(a_T_b_T, sm) { 340 __set_true_false_sm(sm, NULL); 341 } END_FOR_EACH_SM(sm); 342 FOR_EACH_SM(a_T_b_F, sm) { 343 __set_true_false_sm(NULL, sm); 344 } END_FOR_EACH_SM(sm); 345 __free_set_states(); 346 347 free_stree(&a_T_b_fake); 348 free_stree(&a_F_c_fake); 349 free_stree(&a_F_c_T); 350 free_stree(&a_F_c_F); 351 free_stree(&a_T_b_T); 352 free_stree(&a_T_b_F); 353 free_stree(&a_T); 354 free_stree(&a_F); 355 } 356 357 static void handle_comma(struct expression *expr) 358 { 359 __split_expr(expr->left); 360 split_conditions(expr->right); 361 } 362 363 static int make_op_unsigned(int op) 364 { 365 switch (op) { 366 case '<': 367 return SPECIAL_UNSIGNED_LT; 368 case SPECIAL_LTE: 369 return SPECIAL_UNSIGNED_LTE; 370 case '>': 371 return SPECIAL_UNSIGNED_GT; 372 case SPECIAL_GTE: 373 return SPECIAL_UNSIGNED_GTE; 374 } 375 return op; 376 } 377 378 static void hackup_unsigned_compares(struct expression *expr) 379 { 380 if (expr->type != EXPR_COMPARE) 381 return; 382 383 if (type_unsigned(get_type(expr))) 384 expr->op = make_op_unsigned(expr->op); 385 } 386 387 static void do_condition(struct expression *expr) 388 { 389 __fold_in_set_states(); 390 __push_fake_cur_stree(); 391 __pass_to_client(expr, CONDITION_HOOK); 392 __fold_in_set_states(); 393 } 394 395 static void split_conditions(struct expression *expr) 396 { 397 if (option_debug) { 398 char *cond = expr_to_str(expr); 399 400 sm_msg("%d in split_conditions (%s)", get_lineno(), cond); 401 free_string(cond); 402 } 403 404 expr = strip_expr_set_parent(expr); 405 if (!expr) { 406 __fold_in_set_states(); 407 return; 408 } 409 410 /* 411 * On fast paths (and also I guess some people think it's cool) people 412 * sometimes use | instead of ||. It works the same basically except 413 * that || implies a memory barrier between conditions. The easiest way 414 * to handle it is by pretending that | also has a barrier and re-using 415 * all the normal condition code. This potentially hides some bugs, but 416 * people who write code like this should just be careful or they 417 * deserve bugs. 418 * 419 * We could potentially treat boolean bitwise & this way but that seems 420 * too complicated to deal with. 421 */ 422 if (expr->type == EXPR_BINOP && expr->op == '|') { 423 expr_set_parent_expr(expr->left, expr); 424 expr_set_parent_expr(expr->right, expr); 425 handle_logical(expr); 426 return; 427 } 428 429 switch (expr->type) { 430 case EXPR_LOGICAL: 431 expr_set_parent_expr(expr->left, expr); 432 expr_set_parent_expr(expr->right, expr); 433 __pass_to_client(expr, LOGIC_HOOK); 434 handle_logical(expr); 435 return; 436 case EXPR_COMPARE: 437 expr_set_parent_expr(expr->left, expr); 438 expr_set_parent_expr(expr->right, expr); 439 hackup_unsigned_compares(expr); 440 if (handle_zero_comparisons(expr)) 441 return; 442 break; 443 case EXPR_CALL: 444 if (ignore_builtin_expect(expr)) 445 return; 446 break; 447 case EXPR_PREOP: 448 expr_set_parent_expr(expr->unop, expr); 449 if (handle_preop(expr)) 450 return; 451 break; 452 case EXPR_CONDITIONAL: 453 case EXPR_SELECT: 454 expr_set_parent_expr(expr->conditional, expr); 455 expr_set_parent_expr(expr->cond_true, expr); 456 expr_set_parent_expr(expr->cond_false, expr); 457 handle_select(expr); 458 return; 459 case EXPR_COMMA: 460 expr_set_parent_expr(expr->left, expr); 461 expr_set_parent_expr(expr->right, expr); 462 handle_comma(expr); 463 return; 464 } 465 466 /* fixme: this should be in smatch_flow.c 467 but because of the funny stuff we do with conditions 468 it's awkward to put it there. We would need to 469 call CONDITION_HOOK in smatch_flow as well. 470 */ 471 push_expression(&big_expression_stack, expr); 472 push_expression(&big_condition_stack, expr); 473 474 if (expr->type == EXPR_COMPARE) { 475 if (expr->left->type != EXPR_POSTOP) 476 __split_expr(expr->left); 477 if (expr->right->type != EXPR_POSTOP) 478 __split_expr(expr->right); 479 } else if (expr->type != EXPR_POSTOP) { 480 __split_expr(expr); 481 } 482 do_condition(expr); 483 if (expr->type == EXPR_COMPARE) { 484 if (expr->left->type == EXPR_POSTOP) 485 __split_expr(expr->left); 486 if (expr->right->type == EXPR_POSTOP) 487 __split_expr(expr->right); 488 } else if (expr->type == EXPR_POSTOP) { 489 __split_expr(expr); 490 } 491 __push_fake_cur_stree(); 492 __process_post_op_stack(); 493 __fold_in_set_states(); 494 pop_expression(&big_condition_stack); 495 pop_expression(&big_expression_stack); 496 } 497 498 static int inside_condition; 499 void __split_whole_condition(struct expression *expr) 500 { 501 sm_debug("%d in __split_whole_condition\n", get_lineno()); 502 inside_condition++; 503 __save_pre_cond_states(); 504 __push_cond_stacks(); 505 /* it's a hack, but it's sometimes handy to have this stuff 506 on the big_expression_stack. */ 507 push_expression(&big_expression_stack, expr); 508 split_conditions(expr); 509 __use_cond_states(); 510 __pass_to_client(expr, WHOLE_CONDITION_HOOK); 511 pop_expression(&big_expression_stack); 512 inside_condition--; 513 sm_debug("%d done __split_whole_condition\n", get_lineno()); 514 } 515 516 void __handle_logic(struct expression *expr) 517 { 518 sm_debug("%d in __handle_logic\n", get_lineno()); 519 inside_condition++; 520 __save_pre_cond_states(); 521 __push_cond_stacks(); 522 /* it's a hack, but it's sometimes handy to have this stuff 523 on the big_expression_stack. */ 524 push_expression(&big_expression_stack, expr); 525 if (expr) 526 split_conditions(expr); 527 __use_cond_states(); 528 __pass_to_client(expr, WHOLE_CONDITION_HOOK); 529 pop_expression(&big_expression_stack); 530 __merge_false_states(); 531 inside_condition--; 532 sm_debug("%d done __handle_logic\n", get_lineno()); 533 } 534 535 int is_condition(struct expression *expr) 536 { 537 538 expr = strip_expr(expr); 539 if (!expr) 540 return 0; 541 542 switch (expr->type) { 543 case EXPR_LOGICAL: 544 case EXPR_COMPARE: 545 return 1; 546 case EXPR_PREOP: 547 if (expr->op == '!') 548 return 1; 549 } 550 return 0; 551 } 552 553 int __handle_condition_assigns(struct expression *expr) 554 { 555 struct expression *right; 556 struct stree *true_stree, *false_stree, *fake_stree; 557 struct sm_state *sm; 558 559 if (expr->op != '=') 560 return 0; 561 right = strip_expr(expr->right); 562 if (!is_condition(expr->right)) 563 return 0; 564 565 sm_debug("%d in __handle_condition_assigns\n", get_lineno()); 566 inside_condition++; 567 __save_pre_cond_states(); 568 __push_cond_stacks(); 569 /* it's a hack, but it's sometimes handy to have this stuff 570 on the big_expression_stack. */ 571 push_expression(&big_expression_stack, right); 572 split_conditions(right); 573 true_stree = __get_true_states(); 574 false_stree = __get_false_states(); 575 __use_cond_states(); 576 __push_fake_cur_stree(); 577 set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 1))); 578 __pass_to_client(right, WHOLE_CONDITION_HOOK); 579 580 fake_stree = __pop_fake_cur_stree(); 581 FOR_EACH_SM(fake_stree, sm) { 582 overwrite_sm_state_stree(&true_stree, sm); 583 } END_FOR_EACH_SM(sm); 584 free_stree(&fake_stree); 585 586 pop_expression(&big_expression_stack); 587 inside_condition--; 588 589 __push_true_states(); 590 591 __use_false_states(); 592 __push_fake_cur_stree(); 593 set_extra_expr_mod(expr->left, alloc_estate_sval(sval_type_val(get_type(expr->left), 0))); 594 595 fake_stree = __pop_fake_cur_stree(); 596 FOR_EACH_SM(fake_stree, sm) { 597 overwrite_sm_state_stree(&false_stree, sm); 598 } END_FOR_EACH_SM(sm); 599 free_stree(&fake_stree); 600 601 __merge_true_states(); 602 merge_fake_stree(&true_stree, false_stree); 603 free_stree(&false_stree); 604 FOR_EACH_SM(true_stree, sm) { 605 __set_sm(sm); 606 } END_FOR_EACH_SM(sm); 607 608 __pass_to_client(expr, ASSIGNMENT_HOOK); 609 sm_debug("%d done __handle_condition_assigns\n", get_lineno()); 610 return 1; 611 } 612 613 static int is_select_assign(struct expression *expr) 614 { 615 struct expression *right; 616 617 if (expr->op != '=') 618 return 0; 619 right = strip_expr(expr->right); 620 if (right->type == EXPR_CONDITIONAL) 621 return 1; 622 if (right->type == EXPR_SELECT) 623 return 1; 624 return 0; 625 } 626 627 int __handle_select_assigns(struct expression *expr) 628 { 629 struct expression *right; 630 struct stree *final_states = NULL; 631 struct sm_state *sm; 632 int is_true; 633 int is_false; 634 635 if (!is_select_assign(expr)) 636 return 0; 637 sm_debug("%d in __handle_ternary_assigns\n", get_lineno()); 638 right = strip_expr(expr->right); 639 __pass_to_client(right, SELECT_HOOK); 640 641 is_true = implied_condition_true(right->conditional); 642 is_false = implied_condition_false(right->conditional); 643 644 /* hah hah. the ultra fake out */ 645 __save_pre_cond_states(); 646 __split_whole_condition(right->conditional); 647 648 if (!is_false) { 649 struct expression *fake_expr; 650 651 if (right->cond_true) 652 fake_expr = assign_expression(expr->left, expr->op, right->cond_true); 653 else 654 fake_expr = assign_expression(expr->left, expr->op, right->conditional); 655 __split_expr(fake_expr); 656 final_states = clone_stree(__get_cur_stree()); 657 } 658 659 __use_false_states(); 660 if (!is_true) { 661 struct expression *fake_expr; 662 663 fake_expr = assign_expression(expr->left, expr->op, right->cond_false); 664 __split_expr(fake_expr); 665 merge_stree(&final_states, __get_cur_stree()); 666 } 667 668 __use_pre_cond_states(); 669 670 FOR_EACH_SM(final_states, sm) { 671 __set_sm(sm); 672 } END_FOR_EACH_SM(sm); 673 674 free_stree(&final_states); 675 676 sm_debug("%d done __handle_ternary_assigns\n", get_lineno()); 677 678 return 1; 679 } 680 681 static struct statement *split_then_return_last(struct statement *stmt) 682 { 683 struct statement *tmp; 684 struct statement *last_stmt; 685 686 last_stmt = last_ptr_list((struct ptr_list *)stmt->stmts); 687 if (!last_stmt) 688 return NULL; 689 690 __push_scope_hooks(); 691 FOR_EACH_PTR(stmt->stmts, tmp) { 692 if (tmp == last_stmt) { 693 if (tmp->type == STMT_LABEL) { 694 __split_label_stmt(tmp); 695 return tmp->label_statement; 696 } 697 return last_stmt; 698 } 699 __split_stmt(tmp); 700 } END_FOR_EACH_PTR(tmp); 701 return NULL; 702 } 703 704 int __handle_expr_statement_assigns(struct expression *expr) 705 { 706 struct expression *right; 707 struct statement *stmt; 708 709 right = expr->right; 710 if (right->type == EXPR_PREOP && right->op == '(') 711 right = right->unop; 712 if (right->type != EXPR_STATEMENT) 713 return 0; 714 715 __expr_stmt_count++; 716 stmt = right->statement; 717 if (stmt->type == STMT_COMPOUND) { 718 struct statement *last_stmt; 719 struct expression *fake_assign; 720 struct expression fake_expr_stmt = { .smatch_flags = Fake, }; 721 722 last_stmt = split_then_return_last(stmt); 723 if (!last_stmt) { 724 __expr_stmt_count--; 725 return 0; 726 } 727 728 fake_expr_stmt.pos = last_stmt->pos; 729 fake_expr_stmt.type = EXPR_STATEMENT; 730 fake_expr_stmt.op = 0; 731 fake_expr_stmt.statement = last_stmt; 732 733 fake_assign = assign_expression(expr->left, expr->op, &fake_expr_stmt); 734 __split_expr(fake_assign); 735 736 __pass_to_client(stmt, STMT_HOOK_AFTER); 737 __call_scope_hooks(); 738 } else if (stmt->type == STMT_EXPRESSION) { 739 struct expression *fake_assign; 740 741 fake_assign = assign_expression(expr->left, expr->op, stmt->expression); 742 __split_expr(fake_assign); 743 744 } else { 745 __split_stmt(stmt); 746 } 747 __expr_stmt_count--; 748 return 1; 749 } 750 751 int in_condition(void) 752 { 753 return inside_condition; 754 }