1 /* 2 * Copyright (C) 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 * smatch_extra.c is supposed to track the value of every variable. 20 * 21 */ 22 23 #define _GNU_SOURCE 24 #include <string.h> 25 26 #include <stdlib.h> 27 #include <errno.h> 28 #ifndef __USE_ISOC99 29 #define __USE_ISOC99 30 #endif 31 #include <limits.h> 32 #include "parse.h" 33 #include "smatch.h" 34 #include "smatch_slist.h" 35 #include "smatch_extra.h" 36 37 static int my_id; 38 static int link_id; 39 extern int check_assigned_expr_id; 40 41 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr); 42 43 struct string_list *__ignored_macros = NULL; 44 int in_warn_on_macro(void) 45 { 46 struct statement *stmt; 47 char *tmp; 48 char *macro; 49 50 stmt = get_current_statement(); 51 if (!stmt) 52 return 0; 53 macro = get_macro_name(stmt->pos); 54 if (!macro) 55 return 0; 56 57 FOR_EACH_PTR(__ignored_macros, tmp) { 58 if (!strcmp(tmp, macro)) 59 return 1; 60 } END_FOR_EACH_PTR(tmp); 61 return 0; 62 } 63 64 typedef void (mod_hook)(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state); 65 DECLARE_PTR_LIST(void_fn_list, mod_hook *); 66 static struct void_fn_list *extra_mod_hooks; 67 static struct void_fn_list *extra_nomod_hooks; 68 69 void add_extra_mod_hook(mod_hook *fn) 70 { 71 mod_hook **p = malloc(sizeof(mod_hook *)); 72 *p = fn; 73 add_ptr_list(&extra_mod_hooks, p); 74 } 75 76 void add_extra_nomod_hook(mod_hook *fn) 77 { 78 mod_hook **p = malloc(sizeof(mod_hook *)); 79 *p = fn; 80 add_ptr_list(&extra_nomod_hooks, p); 81 } 82 83 void call_extra_hooks(struct void_fn_list *hooks, const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 84 { 85 mod_hook **fn; 86 87 FOR_EACH_PTR(hooks, fn) { 88 (*fn)(name, sym, expr, state); 89 } END_FOR_EACH_PTR(fn); 90 } 91 92 void call_extra_mod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 93 { 94 call_extra_hooks(extra_mod_hooks, name, sym, expr, state); 95 } 96 97 void call_extra_nomod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 98 { 99 call_extra_hooks(extra_nomod_hooks, name, sym, expr, state); 100 } 101 102 static bool in_param_set; 103 void set_extra_mod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 104 { 105 remove_from_equiv(name, sym); 106 call_extra_mod_hooks(name, sym, expr, state); 107 if ((__in_fake_assign || in_param_set) && 108 estate_is_unknown(state) && !get_state(SMATCH_EXTRA, name, sym)) 109 return; 110 set_state(SMATCH_EXTRA, name, sym, state); 111 } 112 113 static void set_extra_nomod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 114 { 115 call_extra_nomod_hooks(name, sym, expr, state); 116 set_state(SMATCH_EXTRA, name, sym, state); 117 } 118 119 static char *get_pointed_at(const char *name, struct symbol *sym, struct symbol **new_sym) 120 { 121 struct expression *assigned; 122 123 if (name[0] != '*') 124 return NULL; 125 if (strcmp(name + 1, sym->ident->name) != 0) 126 return NULL; 127 128 assigned = get_assigned_expr_name_sym(sym->ident->name, sym); 129 if (!assigned) 130 return NULL; 131 assigned = strip_parens(assigned); 132 if (assigned->type != EXPR_PREOP || assigned->op != '&') 133 return NULL; 134 135 return expr_to_var_sym(assigned->unop, new_sym); 136 } 137 138 char *get_other_name_sym_from_chunk(const char *name, const char *chunk, int len, struct symbol *sym, struct symbol **new_sym) 139 { 140 struct expression *assigned; 141 char *orig_name = NULL; 142 char buf[256]; 143 char *ret; 144 145 assigned = get_assigned_expr_name_sym(chunk, sym); 146 if (!assigned) 147 return NULL; 148 if (assigned->type == EXPR_CALL) 149 return map_call_to_other_name_sym(name, sym, new_sym); 150 if (assigned->type == EXPR_PREOP && assigned->op == '&') { 151 152 orig_name = expr_to_var_sym(assigned, new_sym); 153 if (!orig_name || !*new_sym) 154 goto free; 155 156 snprintf(buf, sizeof(buf), "%s.%s", orig_name + 1, name + len); 157 ret = alloc_string(buf); 158 free_string(orig_name); 159 return ret; 160 } 161 162 orig_name = expr_to_var_sym(assigned, new_sym); 163 if (!orig_name || !*new_sym) 164 goto free; 165 166 snprintf(buf, sizeof(buf), "%s->%s", orig_name, name + len); 167 ret = alloc_string(buf); 168 free_string(orig_name); 169 return ret; 170 free: 171 free_string(orig_name); 172 return NULL; 173 } 174 175 static char *get_long_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym) 176 { 177 struct expression *tmp; 178 struct sm_state *sm; 179 char buf[256]; 180 181 /* 182 * Just prepend the name with a different name/sym and return that. 183 * For example, if we set "foo->bar = bar;" then we clamp "bar->baz", 184 * that also clamps "foo->bar->baz". 185 * 186 */ 187 188 FOR_EACH_MY_SM(check_assigned_expr_id, __get_cur_stree(), sm) { 189 tmp = sm->state->data; 190 if (!tmp || tmp->type != EXPR_SYMBOL) 191 continue; 192 if (tmp->symbol == sym) 193 goto found; 194 } END_FOR_EACH_SM(sm); 195 196 return NULL; 197 198 found: 199 snprintf(buf, sizeof(buf), "%s%s", sm->name, name + tmp->symbol->ident->len); 200 *new_sym = sm->sym; 201 return alloc_string(buf); 202 } 203 204 char *get_other_name_sym_helper(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack) 205 { 206 char buf[256]; 207 char *ret; 208 int len; 209 210 *new_sym = NULL; 211 212 if (!sym || !sym->ident) 213 return NULL; 214 215 ret = get_pointed_at(name, sym, new_sym); 216 if (ret) 217 return ret; 218 219 ret = map_long_to_short_name_sym(name, sym, new_sym, use_stack); 220 if (ret) 221 return ret; 222 223 len = snprintf(buf, sizeof(buf), "%s", name); 224 if (len >= sizeof(buf) - 2) 225 return NULL; 226 227 while (len >= 1) { 228 if (buf[len] == '>' && buf[len - 1] == '-') { 229 len--; 230 buf[len] = '\0'; 231 ret = get_other_name_sym_from_chunk(name, buf, len + 2, sym, new_sym); 232 if (ret) 233 return ret; 234 } 235 len--; 236 } 237 238 ret = get_long_name_sym(name, sym, new_sym); 239 if (ret) 240 return ret; 241 242 return NULL; 243 } 244 245 char *get_other_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym) 246 { 247 return get_other_name_sym_helper(name, sym, new_sym, true); 248 } 249 250 char *get_other_name_sym_nostack(const char *name, struct symbol *sym, struct symbol **new_sym) 251 { 252 return get_other_name_sym_helper(name, sym, new_sym, false); 253 } 254 255 void set_extra_mod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 256 { 257 char *new_name; 258 struct symbol *new_sym; 259 260 set_extra_mod_helper(name, sym, expr, state); 261 new_name = get_other_name_sym(name, sym, &new_sym); 262 if (new_name && new_sym) 263 set_extra_mod_helper(new_name, new_sym, expr, state); 264 free_string(new_name); 265 } 266 267 static struct expression *chunk_get_array_base(struct expression *expr) 268 { 269 /* 270 * The problem with is_array() is that it only returns true for things 271 * like foo[1] but not for foo[1].bar. 272 * 273 */ 274 expr = strip_expr(expr); 275 while (expr && expr->type == EXPR_DEREF) 276 expr = strip_expr(expr->deref); 277 return get_array_base(expr); 278 } 279 280 static int chunk_has_array(struct expression *expr) 281 { 282 return !!chunk_get_array_base(expr); 283 } 284 285 static void clear_array_states(struct expression *array) 286 { 287 struct sm_state *sm; 288 289 sm = get_sm_state_expr(link_id, array); 290 if (sm) 291 match_link_modify(sm, NULL); 292 } 293 294 static void set_extra_array_mod(struct expression *expr, struct smatch_state *state) 295 { 296 struct expression *array; 297 struct var_sym_list *vsl; 298 struct var_sym *vs; 299 char *name; 300 struct symbol *sym; 301 302 array = chunk_get_array_base(expr); 303 304 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl); 305 if (!name || !vsl) { 306 clear_array_states(array); 307 goto free; 308 } 309 310 FOR_EACH_PTR(vsl, vs) { 311 store_link(link_id, vs->var, vs->sym, name, sym); 312 } END_FOR_EACH_PTR(vs); 313 314 call_extra_mod_hooks(name, sym, expr, state); 315 set_state(SMATCH_EXTRA, name, sym, state); 316 free: 317 free_string(name); 318 } 319 320 void set_extra_expr_mod(struct expression *expr, struct smatch_state *state) 321 { 322 struct symbol *sym; 323 char *name; 324 325 if (chunk_has_array(expr)) { 326 set_extra_array_mod(expr, state); 327 return; 328 } 329 330 expr = strip_expr(expr); 331 name = expr_to_var_sym(expr, &sym); 332 if (!name || !sym) 333 goto free; 334 set_extra_mod(name, sym, expr, state); 335 free: 336 free_string(name); 337 } 338 339 void set_extra_nomod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state) 340 { 341 char *new_name; 342 struct symbol *new_sym; 343 struct relation *rel; 344 struct smatch_state *orig_state; 345 346 orig_state = get_state(SMATCH_EXTRA, name, sym); 347 348 /* don't save unknown states if leaving it blank is the same */ 349 if (!orig_state && estate_is_unknown(state)) 350 return; 351 352 new_name = get_other_name_sym(name, sym, &new_sym); 353 if (new_name && new_sym) 354 set_extra_nomod_helper(new_name, new_sym, expr, state); 355 free_string(new_name); 356 357 if (!estate_related(orig_state)) { 358 set_extra_nomod_helper(name, sym, expr, state); 359 return; 360 } 361 362 set_related(state, estate_related(orig_state)); 363 FOR_EACH_PTR(estate_related(orig_state), rel) { 364 struct smatch_state *estate; 365 366 estate = get_state(SMATCH_EXTRA, rel->name, rel->sym); 367 if (!estate) 368 continue; 369 set_extra_nomod_helper(rel->name, rel->sym, expr, clone_estate_cast(estate_type(estate), state)); 370 } END_FOR_EACH_PTR(rel); 371 } 372 373 void set_extra_nomod_vsl(const char *name, struct symbol *sym, struct var_sym_list *vsl, struct expression *expr, struct smatch_state *state) 374 { 375 struct var_sym *vs; 376 377 FOR_EACH_PTR(vsl, vs) { 378 store_link(link_id, vs->var, vs->sym, name, sym); 379 } END_FOR_EACH_PTR(vs); 380 381 set_extra_nomod(name, sym, expr, state); 382 } 383 384 /* 385 * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state 386 */ 387 void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state) 388 { 389 struct var_sym_list *vsl; 390 struct var_sym *vs; 391 char *name; 392 struct symbol *sym; 393 394 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl); 395 if (!name || !vsl) 396 goto free; 397 FOR_EACH_PTR(vsl, vs) { 398 store_link(link_id, vs->var, vs->sym, name, sym); 399 } END_FOR_EACH_PTR(vs); 400 401 set_extra_nomod(name, sym, expr, state); 402 free: 403 free_string(name); 404 } 405 406 static void set_extra_true_false(const char *name, struct symbol *sym, 407 struct smatch_state *true_state, 408 struct smatch_state *false_state) 409 { 410 char *new_name; 411 struct symbol *new_sym; 412 struct relation *rel; 413 struct smatch_state *orig_state; 414 415 if (!true_state && !false_state) 416 return; 417 418 if (in_warn_on_macro()) 419 return; 420 421 new_name = get_other_name_sym(name, sym, &new_sym); 422 if (new_name && new_sym) 423 set_true_false_states(SMATCH_EXTRA, new_name, new_sym, true_state, false_state); 424 free_string(new_name); 425 426 orig_state = get_state(SMATCH_EXTRA, name, sym); 427 428 if (!estate_related(orig_state)) { 429 set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state); 430 return; 431 } 432 433 if (true_state) 434 set_related(true_state, estate_related(orig_state)); 435 if (false_state) 436 set_related(false_state, estate_related(orig_state)); 437 438 FOR_EACH_PTR(estate_related(orig_state), rel) { 439 set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym, 440 true_state, false_state); 441 } END_FOR_EACH_PTR(rel); 442 } 443 444 static void set_extra_chunk_true_false(struct expression *expr, 445 struct smatch_state *true_state, 446 struct smatch_state *false_state) 447 { 448 struct var_sym_list *vsl; 449 struct var_sym *vs; 450 struct symbol *type; 451 char *name; 452 struct symbol *sym; 453 454 if (in_warn_on_macro()) 455 return; 456 457 type = get_type(expr); 458 if (!type) 459 return; 460 461 name = expr_to_chunk_sym_vsl(expr, &sym, &vsl); 462 if (!name || !vsl) 463 goto free; 464 FOR_EACH_PTR(vsl, vs) { 465 store_link(link_id, vs->var, vs->sym, name, sym); 466 } END_FOR_EACH_PTR(vs); 467 468 set_true_false_states(SMATCH_EXTRA, name, sym, 469 clone_estate(true_state), 470 clone_estate(false_state)); 471 free: 472 free_string(name); 473 } 474 475 static void set_extra_expr_true_false(struct expression *expr, 476 struct smatch_state *true_state, 477 struct smatch_state *false_state) 478 { 479 char *name; 480 struct symbol *sym; 481 sval_t sval; 482 483 if (!true_state && !false_state) 484 return; 485 486 if (get_value(expr, &sval)) 487 return; 488 489 expr = strip_expr(expr); 490 name = expr_to_var_sym(expr, &sym); 491 if (!name || !sym) { 492 free_string(name); 493 set_extra_chunk_true_false(expr, true_state, false_state); 494 return; 495 } 496 set_extra_true_false(name, sym, true_state, false_state); 497 free_string(name); 498 } 499 500 static int get_countdown_info(struct expression *condition, struct expression **unop, int *op, sval_t *right) 501 { 502 struct expression *unop_expr; 503 int comparison; 504 sval_t limit; 505 506 right->type = &int_ctype; 507 right->value = 0; 508 509 condition = strip_expr(condition); 510 511 if (condition->type == EXPR_COMPARE) { 512 comparison = remove_unsigned_from_comparison(condition->op); 513 514 if (comparison != SPECIAL_GTE && comparison != '>') 515 return 0; 516 if (!get_value(condition->right, &limit)) 517 return 0; 518 519 unop_expr = condition->left; 520 if (unop_expr->type != EXPR_PREOP && unop_expr->type != EXPR_POSTOP) 521 return 0; 522 if (unop_expr->op != SPECIAL_DECREMENT) 523 return 0; 524 525 *unop = unop_expr; 526 *op = comparison; 527 *right = limit; 528 529 return 1; 530 } 531 532 if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP) 533 return 0; 534 if (condition->op != SPECIAL_DECREMENT) 535 return 0; 536 537 *unop = condition; 538 *op = '>'; 539 540 return 1; 541 } 542 543 static struct sm_state *handle_canonical_while_count_down(struct statement *loop) 544 { 545 struct expression *iter_var; 546 struct expression *condition, *unop; 547 struct symbol *type; 548 struct sm_state *sm; 549 struct smatch_state *estate; 550 int op; 551 sval_t start, right; 552 553 right.type = &int_ctype; 554 right.value = 0; 555 556 condition = strip_expr(loop->iterator_pre_condition); 557 if (!condition) 558 return NULL; 559 560 if (!get_countdown_info(condition, &unop, &op, &right)) 561 return NULL; 562 563 iter_var = unop->unop; 564 565 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var); 566 if (!sm) 567 return NULL; 568 if (sval_cmp(estate_min(sm->state), right) < 0) 569 return NULL; 570 start = estate_max(sm->state); 571 572 type = get_type(iter_var); 573 right = sval_cast(type, right); 574 start = sval_cast(type, start); 575 576 if (sval_cmp(start, right) <= 0) 577 return NULL; 578 if (!sval_is_max(start)) 579 start.value--; 580 581 if (op == SPECIAL_GTE) 582 right.value--; 583 584 if (unop->type == EXPR_PREOP) { 585 right.value++; 586 estate = alloc_estate_range(right, start); 587 if (estate_has_hard_max(sm->state)) 588 estate_set_hard_max(estate); 589 estate_copy_fuzzy_max(estate, sm->state); 590 set_extra_expr_mod(iter_var, estate); 591 } 592 if (unop->type == EXPR_POSTOP) { 593 estate = alloc_estate_range(right, start); 594 if (estate_has_hard_max(sm->state)) 595 estate_set_hard_max(estate); 596 estate_copy_fuzzy_max(estate, sm->state); 597 set_extra_expr_mod(iter_var, estate); 598 } 599 return get_sm_state_expr(SMATCH_EXTRA, iter_var); 600 } 601 602 static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr, 603 struct expression *condition) 604 { 605 struct expression *iter_var; 606 struct sm_state *sm; 607 struct smatch_state *estate; 608 sval_t start, end, max; 609 struct symbol *type; 610 611 iter_var = iter_expr->unop; 612 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var); 613 if (!sm) 614 return NULL; 615 if (!estate_get_single_value(sm->state, &start)) 616 return NULL; 617 if (!get_implied_value(condition->right, &end)) 618 return NULL; 619 620 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm) 621 return NULL; 622 623 switch (condition->op) { 624 case SPECIAL_UNSIGNED_LT: 625 case SPECIAL_NOTEQUAL: 626 case '<': 627 if (!sval_is_min(end)) 628 end.value--; 629 break; 630 case SPECIAL_UNSIGNED_LTE: 631 case SPECIAL_LTE: 632 break; 633 default: 634 return NULL; 635 } 636 if (sval_cmp(end, start) < 0) 637 return NULL; 638 type = get_type(iter_var); 639 start = sval_cast(type, start); 640 end = sval_cast(type, end); 641 estate = alloc_estate_range(start, end); 642 if (get_hard_max(condition->right, &max)) { 643 if (!get_macro_name(condition->pos)) 644 estate_set_hard_max(estate); 645 if (condition->op == '<' || 646 condition->op == SPECIAL_UNSIGNED_LT || 647 condition->op == SPECIAL_NOTEQUAL) 648 max.value--; 649 max = sval_cast(type, max); 650 estate_set_fuzzy_max(estate, max); 651 } 652 set_extra_expr_mod(iter_var, estate); 653 return get_sm_state_expr(SMATCH_EXTRA, iter_var); 654 } 655 656 static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr, 657 struct expression *condition) 658 { 659 struct expression *iter_var; 660 struct sm_state *sm; 661 struct smatch_state *estate; 662 sval_t start, end; 663 664 iter_var = iter_expr->unop; 665 sm = get_sm_state_expr(SMATCH_EXTRA, iter_var); 666 if (!sm) 667 return NULL; 668 if (!estate_get_single_value(sm->state, &start)) 669 return NULL; 670 if (!get_implied_min(condition->right, &end)) 671 end = sval_type_min(get_type(iter_var)); 672 end = sval_cast(estate_type(sm->state), end); 673 if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm) 674 return NULL; 675 676 switch (condition->op) { 677 case SPECIAL_NOTEQUAL: 678 case '>': 679 if (!sval_is_max(end)) 680 end.value++; 681 break; 682 case SPECIAL_GTE: 683 break; 684 default: 685 return NULL; 686 } 687 if (sval_cmp(end, start) > 0) 688 return NULL; 689 estate = alloc_estate_range(end, start); 690 estate_set_hard_max(estate); 691 estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate)); 692 set_extra_expr_mod(iter_var, estate); 693 return get_sm_state_expr(SMATCH_EXTRA, iter_var); 694 } 695 696 static struct sm_state *handle_canonical_for_loops(struct statement *loop) 697 { 698 struct expression *iter_expr; 699 struct expression *condition; 700 701 if (!loop->iterator_post_statement) 702 return NULL; 703 if (loop->iterator_post_statement->type != STMT_EXPRESSION) 704 return NULL; 705 iter_expr = loop->iterator_post_statement->expression; 706 if (!loop->iterator_pre_condition) 707 return NULL; 708 if (loop->iterator_pre_condition->type != EXPR_COMPARE) 709 return NULL; 710 condition = loop->iterator_pre_condition; 711 712 if (iter_expr->op == SPECIAL_INCREMENT) 713 return handle_canonical_for_inc(iter_expr, condition); 714 if (iter_expr->op == SPECIAL_DECREMENT) 715 return handle_canonical_for_dec(iter_expr, condition); 716 return NULL; 717 } 718 719 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree) 720 { 721 struct sm_state *ret; 722 723 /* 724 * Canonical loops are a hack. The proper way to handle this is to 725 * use two passes, but unfortunately, doing two passes makes parsing 726 * code twice as slow. 727 * 728 * What we do is we set the inside state here, which overwrites whatever 729 * __extra_match_condition() does. Then we set the outside state in 730 * __extra_pre_loop_hook_after(). 731 * 732 */ 733 __push_fake_cur_stree(); 734 if (!loop->iterator_post_statement) 735 ret = handle_canonical_while_count_down(loop); 736 else 737 ret = handle_canonical_for_loops(loop); 738 *stree = __pop_fake_cur_stree(); 739 return ret; 740 } 741 742 int __iterator_unchanged(struct sm_state *sm) 743 { 744 if (!sm) 745 return 0; 746 if (get_sm_state(my_id, sm->name, sm->sym) == sm) 747 return 1; 748 return 0; 749 } 750 751 static void while_count_down_after(struct sm_state *sm, struct expression *condition) 752 { 753 struct expression *unop; 754 int op; 755 sval_t limit, after_value; 756 757 if (!get_countdown_info(condition, &unop, &op, &limit)) 758 return; 759 after_value = estate_min(sm->state); 760 after_value.value--; 761 set_extra_mod(sm->name, sm->sym, condition->unop, alloc_estate_sval(after_value)); 762 } 763 764 void __extra_pre_loop_hook_after(struct sm_state *sm, 765 struct statement *iterator, 766 struct expression *condition) 767 { 768 struct expression *iter_expr; 769 sval_t limit; 770 struct smatch_state *state; 771 772 if (!iterator) { 773 while_count_down_after(sm, condition); 774 return; 775 } 776 777 iter_expr = iterator->expression; 778 779 if (condition->type != EXPR_COMPARE) 780 return; 781 if (iter_expr->op == SPECIAL_INCREMENT) { 782 limit = sval_binop(estate_max(sm->state), '+', 783 sval_type_val(estate_type(sm->state), 1)); 784 } else { 785 limit = sval_binop(estate_min(sm->state), '-', 786 sval_type_val(estate_type(sm->state), 1)); 787 } 788 limit = sval_cast(estate_type(sm->state), limit); 789 if (!estate_has_hard_max(sm->state) && !__has_breaks()) { 790 if (iter_expr->op == SPECIAL_INCREMENT) 791 state = alloc_estate_range(estate_min(sm->state), limit); 792 else 793 state = alloc_estate_range(limit, estate_max(sm->state)); 794 } else { 795 state = alloc_estate_sval(limit); 796 } 797 if (!estate_has_hard_max(sm->state)) { 798 estate_clear_hard_max(state); 799 } 800 if (estate_has_fuzzy_max(sm->state)) { 801 sval_t hmax = estate_get_fuzzy_max(sm->state); 802 sval_t max = estate_max(sm->state); 803 804 if (sval_cmp(hmax, max) != 0) 805 estate_clear_fuzzy_max(state); 806 } else if (!estate_has_fuzzy_max(sm->state)) { 807 estate_clear_fuzzy_max(state); 808 } 809 810 set_extra_mod(sm->name, sm->sym, iter_expr, state); 811 } 812 813 static bool get_global_rl(const char *name, struct symbol *sym, struct range_list **rl) 814 { 815 struct expression *expr; 816 817 if (!sym || !(sym->ctype.modifiers & MOD_TOPLEVEL) || !sym->ident) 818 return false; 819 if (strcmp(sym->ident->name, name) != 0) 820 return false; 821 822 expr = symbol_expression(sym); 823 return get_implied_rl(expr, rl); 824 } 825 826 static struct stree *unmatched_stree; 827 static struct smatch_state *unmatched_state(struct sm_state *sm) 828 { 829 struct smatch_state *state; 830 struct range_list *rl; 831 832 if (unmatched_stree) { 833 state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym); 834 if (state) 835 return state; 836 } 837 if (parent_is_gone_var_sym(sm->name, sm->sym)) 838 return alloc_estate_empty(); 839 if (get_global_rl(sm->name, sm->sym, &rl)) 840 return alloc_estate_rl(rl); 841 return alloc_estate_whole(estate_type(sm->state)); 842 } 843 844 static void clear_the_pointed_at(struct expression *expr) 845 { 846 struct stree *stree; 847 char *name; 848 struct symbol *sym; 849 struct sm_state *tmp; 850 851 name = expr_to_var_sym(expr, &sym); 852 if (!name || !sym) 853 goto free; 854 855 stree = __get_cur_stree(); 856 FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) { 857 if (tmp->name[0] != '*') 858 continue; 859 if (tmp->sym != sym) 860 continue; 861 if (strcmp(tmp->name + 1, name) != 0) 862 continue; 863 set_extra_mod(tmp->name, tmp->sym, expr, alloc_estate_whole(estate_type(tmp->state))); 864 } END_FOR_EACH_SM(tmp); 865 866 free: 867 free_string(name); 868 } 869 870 static int is_const_param(struct expression *expr, int param) 871 { 872 struct symbol *type; 873 874 type = get_arg_type(expr, param); 875 if (!type) 876 return 0; 877 if (type->ctype.modifiers & MOD_CONST) 878 return 1; 879 return 0; 880 } 881 882 static void match_function_call(struct expression *expr) 883 { 884 struct expression *arg; 885 struct expression *tmp; 886 int param = -1; 887 888 /* if we have the db this is handled in smatch_function_hooks.c */ 889 if (!option_no_db) 890 return; 891 if (inlinable(expr->fn)) 892 return; 893 894 FOR_EACH_PTR(expr->args, arg) { 895 param++; 896 if (is_const_param(expr->fn, param)) 897 continue; 898 tmp = strip_expr(arg); 899 if (tmp->type == EXPR_PREOP && tmp->op == '&') 900 set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop))); 901 else 902 clear_the_pointed_at(tmp); 903 } END_FOR_EACH_PTR(arg); 904 } 905 906 int values_fit_type(struct expression *left, struct expression *right) 907 { 908 struct range_list *rl; 909 struct symbol *type; 910 911 type = get_type(left); 912 if (!type) 913 return 0; 914 get_absolute_rl(right, &rl); 915 if (type == rl_type(rl)) 916 return 1; 917 if (type_unsigned(type) && sval_is_negative(rl_min(rl))) 918 return 0; 919 if (sval_cmp(sval_type_min(type), rl_min(rl)) > 0) 920 return 0; 921 if (sval_cmp(sval_type_max(type), rl_max(rl)) < 0) 922 return 0; 923 return 1; 924 } 925 926 static void save_chunk_info(struct expression *left, struct expression *right) 927 { 928 struct var_sym_list *vsl; 929 struct var_sym *vs; 930 struct expression *add_expr; 931 struct symbol *type; 932 sval_t sval; 933 char *name; 934 struct symbol *sym; 935 936 if (right->type != EXPR_BINOP || right->op != '-') 937 return; 938 if (!get_value(right->left, &sval)) 939 return; 940 if (!expr_to_sym(right->right)) 941 return; 942 943 add_expr = binop_expression(left, '+', right->right); 944 type = get_type(add_expr); 945 if (!type) 946 return; 947 name = expr_to_chunk_sym_vsl(add_expr, &sym, &vsl); 948 if (!name || !vsl) 949 goto free; 950 FOR_EACH_PTR(vsl, vs) { 951 store_link(link_id, vs->var, vs->sym, name, sym); 952 } END_FOR_EACH_PTR(vs); 953 954 set_state(SMATCH_EXTRA, name, sym, alloc_estate_sval(sval_cast(type, sval))); 955 free: 956 free_string(name); 957 } 958 959 static void do_array_assign(struct expression *left, int op, struct expression *right) 960 { 961 struct range_list *rl; 962 963 if (op == '=') { 964 get_absolute_rl(right, &rl); 965 rl = cast_rl(get_type(left), rl); 966 } else { 967 rl = alloc_whole_rl(get_type(left)); 968 } 969 970 set_extra_array_mod(left, alloc_estate_rl(rl)); 971 } 972 973 static void match_vanilla_assign(struct expression *left, struct expression *right) 974 { 975 struct range_list *orig_rl = NULL; 976 struct range_list *rl = NULL; 977 struct symbol *right_sym; 978 struct symbol *left_type; 979 struct symbol *right_type; 980 char *right_name = NULL; 981 struct symbol *sym; 982 char *name; 983 sval_t sval, max; 984 struct smatch_state *state; 985 int comparison; 986 987 if (is_struct(left)) 988 return; 989 990 save_chunk_info(left, right); 991 992 name = expr_to_var_sym(left, &sym); 993 if (!name) { 994 if (chunk_has_array(left)) 995 do_array_assign(left, '=', right); 996 return; 997 } 998 999 left_type = get_type(left); 1000 right_type = get_type(right); 1001 1002 right_name = expr_to_var_sym(right, &right_sym); 1003 1004 if (!__in_fake_assign && 1005 !(right->type == EXPR_PREOP && right->op == '&') && 1006 right_name && right_sym && 1007 values_fit_type(left, strip_expr(right)) && 1008 !has_symbol(right, sym)) { 1009 set_equiv(left, right); 1010 goto free; 1011 } 1012 1013 if (is_pointer(right) && get_address_rl(right, &rl)) { 1014 state = alloc_estate_rl(rl); 1015 goto done; 1016 } 1017 1018 if (get_implied_value(right, &sval)) { 1019 state = alloc_estate_sval(sval_cast(left_type, sval)); 1020 goto done; 1021 } 1022 1023 if (__in_fake_assign) { 1024 struct smatch_state *right_state; 1025 sval_t sval; 1026 1027 if (get_value(right, &sval)) { 1028 sval = sval_cast(left_type, sval); 1029 state = alloc_estate_sval(sval); 1030 goto done; 1031 } 1032 1033 right_state = get_state(SMATCH_EXTRA, right_name, right_sym); 1034 if (right_state) { 1035 /* simple assignment */ 1036 state = clone_estate(right_state); 1037 goto done; 1038 } 1039 1040 state = alloc_estate_rl(alloc_whole_rl(left_type)); 1041 goto done; 1042 } 1043 1044 comparison = get_comparison_no_extra(left, right); 1045 if (comparison) { 1046 comparison = flip_comparison(comparison); 1047 get_implied_rl(left, &orig_rl); 1048 } 1049 1050 if (get_implied_rl(right, &rl)) { 1051 rl = cast_rl(left_type, rl); 1052 if (orig_rl) 1053 filter_by_comparison(&rl, comparison, orig_rl); 1054 state = alloc_estate_rl(rl); 1055 if (get_hard_max(right, &max)) { 1056 estate_set_hard_max(state); 1057 estate_set_fuzzy_max(state, max); 1058 } 1059 } else { 1060 rl = alloc_whole_rl(right_type); 1061 rl = cast_rl(left_type, rl); 1062 if (orig_rl) 1063 filter_by_comparison(&rl, comparison, orig_rl); 1064 state = alloc_estate_rl(rl); 1065 } 1066 1067 done: 1068 set_extra_mod(name, sym, left, state); 1069 free: 1070 free_string(right_name); 1071 } 1072 1073 static void match_assign(struct expression *expr) 1074 { 1075 struct range_list *rl = NULL; 1076 struct expression *left; 1077 struct expression *right; 1078 struct expression *binop_expr; 1079 struct symbol *left_type; 1080 struct symbol *sym; 1081 char *name; 1082 1083 left = strip_expr(expr->left); 1084 1085 right = strip_parens(expr->right); 1086 if (right->type == EXPR_CALL && sym_name_is("__builtin_expect", right->fn)) 1087 right = get_argument_from_call_expr(right->args, 0); 1088 while (right->type == EXPR_ASSIGNMENT && right->op == '=') 1089 right = strip_parens(right->left); 1090 1091 if (expr->op == '=' && is_condition(expr->right)) 1092 return; /* handled in smatch_condition.c */ 1093 if (expr->op == '=' && right->type == EXPR_CALL) 1094 return; /* handled in smatch_function_hooks.c */ 1095 if (expr->op == '=') { 1096 match_vanilla_assign(left, right); 1097 return; 1098 } 1099 1100 name = expr_to_var_sym(left, &sym); 1101 if (!name) 1102 return; 1103 1104 left_type = get_type(left); 1105 1106 switch (expr->op) { 1107 case SPECIAL_ADD_ASSIGN: 1108 case SPECIAL_SUB_ASSIGN: 1109 case SPECIAL_AND_ASSIGN: 1110 case SPECIAL_MOD_ASSIGN: 1111 case SPECIAL_SHL_ASSIGN: 1112 case SPECIAL_SHR_ASSIGN: 1113 case SPECIAL_OR_ASSIGN: 1114 case SPECIAL_XOR_ASSIGN: 1115 case SPECIAL_MUL_ASSIGN: 1116 case SPECIAL_DIV_ASSIGN: 1117 binop_expr = binop_expression(expr->left, 1118 op_remove_assign(expr->op), 1119 expr->right); 1120 get_absolute_rl(binop_expr, &rl); 1121 rl = cast_rl(left_type, rl); 1122 if (inside_loop()) { 1123 if (expr->op == SPECIAL_ADD_ASSIGN) 1124 add_range(&rl, rl_max(rl), sval_type_max(rl_type(rl))); 1125 1126 if (expr->op == SPECIAL_SUB_ASSIGN && 1127 !sval_is_negative(rl_min(rl))) { 1128 sval_t zero = { .type = rl_type(rl) }; 1129 1130 add_range(&rl, rl_min(rl), zero); 1131 } 1132 } 1133 set_extra_mod(name, sym, left, alloc_estate_rl(rl)); 1134 goto free; 1135 } 1136 set_extra_mod(name, sym, left, alloc_estate_whole(left_type)); 1137 free: 1138 free_string(name); 1139 } 1140 1141 static struct smatch_state *increment_state(struct smatch_state *state) 1142 { 1143 sval_t min = estate_min(state); 1144 sval_t max = estate_max(state); 1145 1146 if (!estate_rl(state)) 1147 return NULL; 1148 1149 if (inside_loop()) 1150 max = sval_type_max(max.type); 1151 1152 if (!sval_is_min(min) && !sval_is_max(min)) 1153 min.value++; 1154 if (!sval_is_min(max) && !sval_is_max(max)) 1155 max.value++; 1156 return alloc_estate_range(min, max); 1157 } 1158 1159 static struct smatch_state *decrement_state(struct smatch_state *state) 1160 { 1161 sval_t min = estate_min(state); 1162 sval_t max = estate_max(state); 1163 1164 if (!estate_rl(state)) 1165 return NULL; 1166 1167 if (inside_loop()) 1168 min = sval_type_min(min.type); 1169 1170 if (!sval_is_min(min) && !sval_is_max(min)) 1171 min.value--; 1172 if (!sval_is_min(max) && !sval_is_max(max)) 1173 max.value--; 1174 return alloc_estate_range(min, max); 1175 } 1176 1177 static void clear_pointed_at_state(struct expression *expr) 1178 { 1179 struct symbol *type; 1180 1181 /* 1182 * ALERT: This is sort of a mess. If it's is a struct assigment like 1183 * "foo = bar;", then that's handled by smatch_struct_assignment.c. 1184 * the same thing for p++ where "p" is a struct. Most modifications 1185 * are handled by the assignment hook or the db. Smatch_extra.c doesn't 1186 * use smatch_modification.c because we have to get the ordering right 1187 * or something. So if you have p++ where p is a pointer to a standard 1188 * c type then we handle that here. What a mess. 1189 */ 1190 expr = strip_expr(expr); 1191 type = get_type(expr); 1192 if (!type || type->type != SYM_PTR) 1193 return; 1194 type = get_real_base_type(type); 1195 if (!type || type->type != SYM_BASETYPE) 1196 return; 1197 set_extra_expr_nomod(deref_expression(expr), alloc_estate_whole(type)); 1198 } 1199 1200 static void unop_expr(struct expression *expr) 1201 { 1202 struct smatch_state *state; 1203 1204 if (expr->smatch_flags & Handled) 1205 return; 1206 1207 switch (expr->op) { 1208 case SPECIAL_INCREMENT: 1209 state = get_state_expr(SMATCH_EXTRA, expr->unop); 1210 state = increment_state(state); 1211 if (!state) 1212 state = alloc_estate_whole(get_type(expr)); 1213 set_extra_expr_mod(expr->unop, state); 1214 clear_pointed_at_state(expr->unop); 1215 break; 1216 case SPECIAL_DECREMENT: 1217 state = get_state_expr(SMATCH_EXTRA, expr->unop); 1218 state = decrement_state(state); 1219 if (!state) 1220 state = alloc_estate_whole(get_type(expr)); 1221 set_extra_expr_mod(expr->unop, state); 1222 clear_pointed_at_state(expr->unop); 1223 break; 1224 default: 1225 return; 1226 } 1227 } 1228 1229 static void asm_expr(struct statement *stmt) 1230 { 1231 1232 struct expression *expr; 1233 struct symbol *type; 1234 int state = 0; 1235 1236 FOR_EACH_PTR(stmt->asm_outputs, expr) { 1237 switch (state) { 1238 case 0: /* identifier */ 1239 case 1: /* constraint */ 1240 state++; 1241 continue; 1242 case 2: /* expression */ 1243 state = 0; 1244 type = get_type(strip_expr(expr)); 1245 set_extra_expr_mod(expr, alloc_estate_whole(type)); 1246 continue; 1247 } 1248 } END_FOR_EACH_PTR(expr); 1249 } 1250 1251 static void check_dereference(struct expression *expr) 1252 { 1253 struct smatch_state *state; 1254 1255 if (__in_fake_assign) 1256 return; 1257 if (outside_of_function()) 1258 return; 1259 state = get_extra_state(expr); 1260 if (state) { 1261 struct range_list *rl; 1262 1263 rl = rl_intersection(estate_rl(state), valid_ptr_rl); 1264 if (rl_equiv(rl, estate_rl(state))) 1265 return; 1266 set_extra_expr_nomod(expr, alloc_estate_rl(rl)); 1267 } else { 1268 struct range_list *rl; 1269 1270 if (get_mtag_rl(expr, &rl)) 1271 rl = rl_intersection(rl, valid_ptr_rl); 1272 else 1273 rl = clone_rl(valid_ptr_rl); 1274 1275 set_extra_expr_nomod(expr, alloc_estate_rl(rl)); 1276 } 1277 } 1278 1279 static void match_dereferences(struct expression *expr) 1280 { 1281 if (expr->type != EXPR_PREOP) 1282 return; 1283 /* it's saying that foo[1] = bar dereferences foo[1] */ 1284 if (is_array(expr)) 1285 return; 1286 check_dereference(expr->unop); 1287 } 1288 1289 static void match_pointer_as_array(struct expression *expr) 1290 { 1291 if (!is_array(expr)) 1292 return; 1293 check_dereference(get_array_base(expr)); 1294 } 1295 1296 static void find_dereferences(struct expression *expr) 1297 { 1298 while (expr->type == EXPR_PREOP) { 1299 if (expr->op == '*') 1300 check_dereference(expr->unop); 1301 expr = strip_expr(expr->unop); 1302 } 1303 } 1304 1305 static void set_param_dereferenced(struct expression *call, struct expression *arg, char *key, char *unused) 1306 { 1307 struct symbol *sym; 1308 char *name; 1309 1310 name = get_variable_from_key(arg, key, &sym); 1311 if (name && sym) { 1312 struct smatch_state *orig, *new; 1313 struct range_list *rl; 1314 1315 orig = get_state(SMATCH_EXTRA, name, sym); 1316 if (orig) { 1317 rl = rl_intersection(estate_rl(orig), 1318 alloc_rl(valid_ptr_min_sval, 1319 valid_ptr_max_sval)); 1320 new = alloc_estate_rl(rl); 1321 } else { 1322 new = alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval); 1323 } 1324 1325 set_extra_nomod(name, sym, NULL, new); 1326 } 1327 free_string(name); 1328 1329 find_dereferences(arg); 1330 } 1331 1332 static sval_t add_one(sval_t sval) 1333 { 1334 sval.value++; 1335 return sval; 1336 } 1337 1338 static int handle_postop_inc(struct expression *left, int op, struct expression *right) 1339 { 1340 struct statement *stmt; 1341 struct expression *cond; 1342 struct smatch_state *true_state, *false_state; 1343 struct symbol *type; 1344 sval_t start; 1345 sval_t limit; 1346 1347 /* 1348 * If we're decrementing here then that's a canonical while count down 1349 * so it's handled already. We're only handling loops like: 1350 * i = 0; 1351 * do { ... } while (i++ < 3); 1352 */ 1353 1354 if (left->type != EXPR_POSTOP || left->op != SPECIAL_INCREMENT) 1355 return 0; 1356 1357 stmt = __cur_stmt->parent; 1358 if (!stmt) 1359 return 0; 1360 if (stmt->type == STMT_COMPOUND) 1361 stmt = stmt->parent; 1362 if (!stmt || stmt->type != STMT_ITERATOR || !stmt->iterator_post_condition) 1363 return 0; 1364 1365 cond = strip_expr(stmt->iterator_post_condition); 1366 if (cond->type != EXPR_COMPARE || cond->op != op) 1367 return 0; 1368 if (left != strip_expr(cond->left) || right != strip_expr(cond->right)) 1369 return 0; 1370 1371 if (!get_implied_value(left->unop, &start)) 1372 return 0; 1373 if (!get_implied_value(right, &limit)) 1374 return 0; 1375 type = get_type(left->unop); 1376 limit = sval_cast(type, limit); 1377 if (sval_cmp(start, limit) > 0) 1378 return 0; 1379 1380 switch (op) { 1381 case '<': 1382 case SPECIAL_UNSIGNED_LT: 1383 break; 1384 case SPECIAL_LTE: 1385 case SPECIAL_UNSIGNED_LTE: 1386 limit = add_one(limit); 1387 default: 1388 return 0; 1389 1390 } 1391 1392 true_state = alloc_estate_range(add_one(start), limit); 1393 false_state = alloc_estate_range(add_one(limit), add_one(limit)); 1394 1395 /* Currently we just discard the false state but when two passes is 1396 * implimented correctly then it will use it. 1397 */ 1398 1399 set_extra_expr_true_false(left->unop, true_state, false_state); 1400 1401 return 1; 1402 } 1403 1404 bool is_impossible_variable(struct expression *expr) 1405 { 1406 struct smatch_state *state; 1407 1408 state = get_extra_state(expr); 1409 if (state && !estate_rl(state)) 1410 return true; 1411 return false; 1412 } 1413 1414 static bool in_macro(struct expression *left, struct expression *right) 1415 { 1416 if (!left || !right) 1417 return 0; 1418 if (left->pos.line != right->pos.line || left->pos.pos != right->pos.pos) 1419 return 0; 1420 if (get_macro_name(left->pos)) 1421 return 1; 1422 return 0; 1423 } 1424 1425 static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right) 1426 { 1427 struct range_list *left_orig; 1428 struct range_list *left_true; 1429 struct range_list *left_false; 1430 struct range_list *right_orig; 1431 struct range_list *right_true; 1432 struct range_list *right_false; 1433 struct smatch_state *left_true_state; 1434 struct smatch_state *left_false_state; 1435 struct smatch_state *right_true_state; 1436 struct smatch_state *right_false_state; 1437 sval_t dummy, hard_max; 1438 int left_postop = 0; 1439 int right_postop = 0; 1440 1441 if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) { 1442 if (left->type == EXPR_POSTOP) { 1443 left->smatch_flags |= Handled; 1444 left_postop = left->op; 1445 if (handle_postop_inc(left, op, right)) 1446 return; 1447 } 1448 left = strip_parens(left->unop); 1449 } 1450 while (left->type == EXPR_ASSIGNMENT) 1451 left = strip_parens(left->left); 1452 1453 if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) { 1454 if (right->type == EXPR_POSTOP) { 1455 right->smatch_flags |= Handled; 1456 right_postop = right->op; 1457 } 1458 right = strip_parens(right->unop); 1459 } 1460 1461 if (is_impossible_variable(left) || is_impossible_variable(right)) 1462 return; 1463 1464 get_real_absolute_rl(left, &left_orig); 1465 left_orig = cast_rl(type, left_orig); 1466 1467 get_real_absolute_rl(right, &right_orig); 1468 right_orig = cast_rl(type, right_orig); 1469 1470 split_comparison_rl(left_orig, op, right_orig, &left_true, &left_false, &right_true, &right_false); 1471 1472 left_true = rl_truncate_cast(get_type(strip_expr(left)), left_true); 1473 left_false = rl_truncate_cast(get_type(strip_expr(left)), left_false); 1474 right_true = rl_truncate_cast(get_type(strip_expr(right)), right_true); 1475 right_false = rl_truncate_cast(get_type(strip_expr(right)), right_false); 1476 1477 if (!left_true || !left_false) { 1478 struct range_list *tmp_true, *tmp_false; 1479 1480 split_comparison_rl(alloc_whole_rl(type), op, right_orig, &tmp_true, &tmp_false, NULL, NULL); 1481 tmp_true = rl_truncate_cast(get_type(strip_expr(left)), tmp_true); 1482 tmp_false = rl_truncate_cast(get_type(strip_expr(left)), tmp_false); 1483 if (tmp_true && tmp_false) 1484 __save_imaginary_state(left, tmp_true, tmp_false); 1485 } 1486 1487 if (!right_true || !right_false) { 1488 struct range_list *tmp_true, *tmp_false; 1489 1490 split_comparison_rl(alloc_whole_rl(type), op, right_orig, NULL, NULL, &tmp_true, &tmp_false); 1491 tmp_true = rl_truncate_cast(get_type(strip_expr(right)), tmp_true); 1492 tmp_false = rl_truncate_cast(get_type(strip_expr(right)), tmp_false); 1493 if (tmp_true && tmp_false) 1494 __save_imaginary_state(right, tmp_true, tmp_false); 1495 } 1496 1497 left_true_state = alloc_estate_rl(left_true); 1498 left_false_state = alloc_estate_rl(left_false); 1499 right_true_state = alloc_estate_rl(right_true); 1500 right_false_state = alloc_estate_rl(right_false); 1501 1502 switch (op) { 1503 case '<': 1504 case SPECIAL_UNSIGNED_LT: 1505 case SPECIAL_UNSIGNED_LTE: 1506 case SPECIAL_LTE: 1507 if (get_implied_value(right, &dummy) && !in_macro(left, right)) 1508 estate_set_hard_max(left_true_state); 1509 if (get_implied_value(left, &dummy) && !in_macro(left, right)) 1510 estate_set_hard_max(right_false_state); 1511 break; 1512 case '>': 1513 case SPECIAL_UNSIGNED_GT: 1514 case SPECIAL_UNSIGNED_GTE: 1515 case SPECIAL_GTE: 1516 if (get_implied_value(left, &dummy) && !in_macro(left, right)) 1517 estate_set_hard_max(right_true_state); 1518 if (get_implied_value(right, &dummy) && !in_macro(left, right)) 1519 estate_set_hard_max(left_false_state); 1520 break; 1521 } 1522 1523 switch (op) { 1524 case '<': 1525 case SPECIAL_UNSIGNED_LT: 1526 case SPECIAL_UNSIGNED_LTE: 1527 case SPECIAL_LTE: 1528 if (get_hard_max(right, &hard_max)) { 1529 if (op == '<' || op == SPECIAL_UNSIGNED_LT) 1530 hard_max.value--; 1531 estate_set_fuzzy_max(left_true_state, hard_max); 1532 } 1533 if (get_implied_value(right, &hard_max)) { 1534 if (op == SPECIAL_UNSIGNED_LTE || 1535 op == SPECIAL_LTE) 1536 hard_max.value++; 1537 estate_set_fuzzy_max(left_false_state, hard_max); 1538 } 1539 if (get_hard_max(left, &hard_max)) { 1540 if (op == SPECIAL_UNSIGNED_LTE || 1541 op == SPECIAL_LTE) 1542 hard_max.value--; 1543 estate_set_fuzzy_max(right_false_state, hard_max); 1544 } 1545 if (get_implied_value(left, &hard_max)) { 1546 if (op == '<' || op == SPECIAL_UNSIGNED_LT) 1547 hard_max.value++; 1548 estate_set_fuzzy_max(right_true_state, hard_max); 1549 } 1550 break; 1551 case '>': 1552 case SPECIAL_UNSIGNED_GT: 1553 case SPECIAL_UNSIGNED_GTE: 1554 case SPECIAL_GTE: 1555 if (get_hard_max(left, &hard_max)) { 1556 if (op == '>' || op == SPECIAL_UNSIGNED_GT) 1557 hard_max.value--; 1558 estate_set_fuzzy_max(right_true_state, hard_max); 1559 } 1560 if (get_implied_value(left, &hard_max)) { 1561 if (op == SPECIAL_UNSIGNED_GTE || 1562 op == SPECIAL_GTE) 1563 hard_max.value++; 1564 estate_set_fuzzy_max(right_false_state, hard_max); 1565 } 1566 if (get_hard_max(right, &hard_max)) { 1567 if (op == SPECIAL_UNSIGNED_LTE || 1568 op == SPECIAL_LTE) 1569 hard_max.value--; 1570 estate_set_fuzzy_max(left_false_state, hard_max); 1571 } 1572 if (get_implied_value(right, &hard_max)) { 1573 if (op == '>' || 1574 op == SPECIAL_UNSIGNED_GT) 1575 hard_max.value++; 1576 estate_set_fuzzy_max(left_true_state, hard_max); 1577 } 1578 break; 1579 case SPECIAL_EQUAL: 1580 if (get_hard_max(left, &hard_max)) 1581 estate_set_fuzzy_max(right_true_state, hard_max); 1582 if (get_hard_max(right, &hard_max)) 1583 estate_set_fuzzy_max(left_true_state, hard_max); 1584 break; 1585 } 1586 1587 if (get_hard_max(left, &hard_max)) { 1588 estate_set_hard_max(left_true_state); 1589 estate_set_hard_max(left_false_state); 1590 } 1591 if (get_hard_max(right, &hard_max)) { 1592 estate_set_hard_max(right_true_state); 1593 estate_set_hard_max(right_false_state); 1594 } 1595 1596 if (left_postop == SPECIAL_INCREMENT) { 1597 left_true_state = increment_state(left_true_state); 1598 left_false_state = increment_state(left_false_state); 1599 } 1600 if (left_postop == SPECIAL_DECREMENT) { 1601 left_true_state = decrement_state(left_true_state); 1602 left_false_state = decrement_state(left_false_state); 1603 } 1604 if (right_postop == SPECIAL_INCREMENT) { 1605 right_true_state = increment_state(right_true_state); 1606 right_false_state = increment_state(right_false_state); 1607 } 1608 if (right_postop == SPECIAL_DECREMENT) { 1609 right_true_state = decrement_state(right_true_state); 1610 right_false_state = decrement_state(right_false_state); 1611 } 1612 1613 if (estate_rl(left_true_state) && estates_equiv(left_true_state, left_false_state)) { 1614 left_true_state = NULL; 1615 left_false_state = NULL; 1616 } 1617 1618 if (estate_rl(right_true_state) && estates_equiv(right_true_state, right_false_state)) { 1619 right_true_state = NULL; 1620 right_false_state = NULL; 1621 } 1622 1623 /* Don't introduce new states for known true/false conditions */ 1624 if (rl_equiv(left_orig, estate_rl(left_true_state))) 1625 left_true_state = NULL; 1626 if (rl_equiv(left_orig, estate_rl(left_false_state))) 1627 left_false_state = NULL; 1628 if (rl_equiv(right_orig, estate_rl(right_true_state))) 1629 right_true_state = NULL; 1630 if (rl_equiv(right_orig, estate_rl(right_false_state))) 1631 right_false_state = NULL; 1632 1633 set_extra_expr_true_false(left, left_true_state, left_false_state); 1634 set_extra_expr_true_false(right, right_true_state, right_false_state); 1635 } 1636 1637 static int is_simple_math(struct expression *expr) 1638 { 1639 if (!expr) 1640 return 0; 1641 if (expr->type != EXPR_BINOP) 1642 return 0; 1643 switch (expr->op) { 1644 case '+': 1645 case '-': 1646 case '*': 1647 return 1; 1648 } 1649 return 0; 1650 } 1651 1652 static int flip_op(int op) 1653 { 1654 /* We only care about simple math */ 1655 switch (op) { 1656 case '+': 1657 return '-'; 1658 case '-': 1659 return '+'; 1660 case '*': 1661 return '/'; 1662 } 1663 return 0; 1664 } 1665 1666 static void move_known_to_rl(struct expression **expr_p, struct range_list **rl_p) 1667 { 1668 struct expression *expr = *expr_p; 1669 struct range_list *rl = *rl_p; 1670 sval_t sval; 1671 1672 if (!is_simple_math(expr)) 1673 return; 1674 1675 if (get_implied_value(expr->right, &sval)) { 1676 *expr_p = expr->left; 1677 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval)); 1678 move_known_to_rl(expr_p, rl_p); 1679 return; 1680 } 1681 if (expr->op == '-') 1682 return; 1683 if (get_implied_value(expr->left, &sval)) { 1684 *expr_p = expr->right; 1685 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval)); 1686 move_known_to_rl(expr_p, rl_p); 1687 return; 1688 } 1689 } 1690 1691 static void move_known_values(struct expression **left_p, struct expression **right_p) 1692 { 1693 struct expression *left = *left_p; 1694 struct expression *right = *right_p; 1695 sval_t sval, dummy; 1696 1697 if (get_implied_value(left, &sval)) { 1698 if (!is_simple_math(right)) 1699 return; 1700 if (get_implied_value(right, &dummy)) 1701 return; 1702 if (right->op == '*') { 1703 sval_t divisor; 1704 1705 if (!get_value(right->right, &divisor)) 1706 return; 1707 if (divisor.value == 0) 1708 return; 1709 *left_p = binop_expression(left, invert_op(right->op), right->right); 1710 *right_p = right->left; 1711 return; 1712 } 1713 if (right->op == '+' && get_value(right->left, &sval)) { 1714 *left_p = binop_expression(left, invert_op(right->op), right->left); 1715 *right_p = right->right; 1716 return; 1717 } 1718 if (get_value(right->right, &sval)) { 1719 *left_p = binop_expression(left, invert_op(right->op), right->right); 1720 *right_p = right->left; 1721 return; 1722 } 1723 return; 1724 } 1725 if (get_implied_value(right, &sval)) { 1726 if (!is_simple_math(left)) 1727 return; 1728 if (get_implied_value(left, &dummy)) 1729 return; 1730 if (left->op == '*') { 1731 sval_t divisor; 1732 1733 if (!get_value(left->right, &divisor)) 1734 return; 1735 if (divisor.value == 0) 1736 return; 1737 *right_p = binop_expression(right, invert_op(left->op), left->right); 1738 *left_p = left->left; 1739 return; 1740 } 1741 if (left->op == '+' && get_value(left->left, &sval)) { 1742 *right_p = binop_expression(right, invert_op(left->op), left->left); 1743 *left_p = left->right; 1744 return; 1745 } 1746 1747 if (get_value(left->right, &sval)) { 1748 *right_p = binop_expression(right, invert_op(left->op), left->right); 1749 *left_p = left->left; 1750 return; 1751 } 1752 return; 1753 } 1754 } 1755 1756 /* 1757 * The reason for do_simple_algebra() is to solve things like: 1758 * if (foo > 66 || foo + bar > 64) { 1759 * "foo" is not really a known variable so it won't be handled by 1760 * move_known_variables() but it's a super common idiom. 1761 * 1762 */ 1763 static int do_simple_algebra(struct expression **left_p, struct expression **right_p) 1764 { 1765 struct expression *left = *left_p; 1766 struct expression *right = *right_p; 1767 struct range_list *rl; 1768 sval_t tmp; 1769 1770 if (left->type != EXPR_BINOP || left->op != '+') 1771 return 0; 1772 if (can_integer_overflow(get_type(left), left)) 1773 return 0; 1774 if (!get_implied_value(right, &tmp)) 1775 return 0; 1776 1777 if (!get_implied_value(left->left, &tmp) && 1778 get_implied_rl(left->left, &rl) && 1779 !is_whole_rl(rl)) { 1780 *right_p = binop_expression(right, '-', left->left); 1781 *left_p = left->right; 1782 return 1; 1783 } 1784 if (!get_implied_value(left->right, &tmp) && 1785 get_implied_rl(left->right, &rl) && 1786 !is_whole_rl(rl)) { 1787 *right_p = binop_expression(right, '-', left->right); 1788 *left_p = left->left; 1789 return 1; 1790 } 1791 1792 return 0; 1793 } 1794 1795 static int match_func_comparison(struct expression *expr) 1796 { 1797 struct expression *left = strip_expr(expr->left); 1798 struct expression *right = strip_expr(expr->right); 1799 1800 if (left->type == EXPR_CALL || right->type == EXPR_CALL) { 1801 function_comparison(left, expr->op, right); 1802 return 1; 1803 } 1804 1805 return 0; 1806 } 1807 1808 /* Handle conditions like "if (foo + bar < foo) {" */ 1809 static int handle_integer_overflow_test(struct expression *expr) 1810 { 1811 struct expression *left, *right; 1812 struct symbol *type; 1813 sval_t left_min, right_min, min, max; 1814 1815 if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT) 1816 return 0; 1817 1818 left = strip_parens(expr->left); 1819 right = strip_parens(expr->right); 1820 1821 if (left->op != '+') 1822 return 0; 1823 1824 type = get_type(expr); 1825 if (!type) 1826 return 0; 1827 if (type_positive_bits(type) == 32) { 1828 max.type = &uint_ctype; 1829 max.uvalue = (unsigned int)-1; 1830 } else if (type_positive_bits(type) == 64) { 1831 max.type = &ulong_ctype; 1832 max.value = (unsigned long long)-1; 1833 } else { 1834 return 0; 1835 } 1836 1837 if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right)) 1838 return 0; 1839 1840 get_absolute_min(left->left, &left_min); 1841 get_absolute_min(left->right, &right_min); 1842 min = sval_binop(left_min, '+', right_min); 1843 1844 type = get_type(left); 1845 min = sval_cast(type, min); 1846 max = sval_cast(type, max); 1847 1848 set_extra_chunk_true_false(left, NULL, alloc_estate_range(min, max)); 1849 return 1; 1850 } 1851 1852 static void match_comparison(struct expression *expr) 1853 { 1854 struct expression *left_orig = strip_parens(expr->left); 1855 struct expression *right_orig = strip_parens(expr->right); 1856 struct expression *left, *right, *tmp; 1857 struct expression *prev; 1858 struct symbol *type; 1859 int redo, count; 1860 1861 if (match_func_comparison(expr)) 1862 return; 1863 1864 type = get_type(expr); 1865 if (!type) 1866 type = &llong_ctype; 1867 1868 if (handle_integer_overflow_test(expr)) 1869 return; 1870 1871 left = left_orig; 1872 right = right_orig; 1873 move_known_values(&left, &right); 1874 handle_comparison(type, left, expr->op, right); 1875 1876 left = left_orig; 1877 right = right_orig; 1878 if (do_simple_algebra(&left, &right)) 1879 handle_comparison(type, left, expr->op, right); 1880 1881 prev = get_assigned_expr(left_orig); 1882 if (is_simple_math(prev) && has_variable(prev, left_orig) == 0) { 1883 left = prev; 1884 right = right_orig; 1885 move_known_values(&left, &right); 1886 handle_comparison(type, left, expr->op, right); 1887 } 1888 1889 prev = get_assigned_expr(right_orig); 1890 if (is_simple_math(prev) && has_variable(prev, right_orig) == 0) { 1891 left = left_orig; 1892 right = prev; 1893 move_known_values(&left, &right); 1894 handle_comparison(type, left, expr->op, right); 1895 } 1896 1897 redo = 0; 1898 left = left_orig; 1899 right = right_orig; 1900 if (get_last_expr_from_expression_stmt(left_orig)) { 1901 left = get_last_expr_from_expression_stmt(left_orig); 1902 redo = 1; 1903 } 1904 if (get_last_expr_from_expression_stmt(right_orig)) { 1905 right = get_last_expr_from_expression_stmt(right_orig); 1906 redo = 1; 1907 } 1908 1909 if (!redo) 1910 return; 1911 1912 count = 0; 1913 while ((tmp = get_assigned_expr(left))) { 1914 if (count++ > 3) 1915 break; 1916 left = strip_expr(tmp); 1917 } 1918 count = 0; 1919 while ((tmp = get_assigned_expr(right))) { 1920 if (count++ > 3) 1921 break; 1922 right = strip_expr(tmp); 1923 } 1924 1925 handle_comparison(type, left, expr->op, right); 1926 } 1927 1928 static sval_t get_high_mask(sval_t known) 1929 { 1930 sval_t ret; 1931 int i; 1932 1933 ret = known; 1934 ret.value = 0; 1935 1936 for (i = type_bits(known.type) - 1; i >= 0; i--) { 1937 if (known.uvalue & (1ULL << i)) 1938 ret.uvalue |= (1ULL << i); 1939 else 1940 return ret; 1941 1942 } 1943 return ret; 1944 } 1945 1946 static bool handle_bit_test(struct expression *expr) 1947 { 1948 struct range_list *orig_rl, *rl; 1949 struct expression *shift, *mask, *var; 1950 struct bit_info *bit_info; 1951 sval_t sval; 1952 sval_t high = { .type = &int_ctype }; 1953 sval_t low = { .type = &int_ctype }; 1954 1955 shift = strip_expr(expr->right); 1956 mask = strip_expr(expr->left); 1957 if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT) { 1958 shift = strip_expr(expr->left); 1959 mask = strip_expr(expr->right); 1960 if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT) 1961 return false; 1962 } 1963 if (!get_implied_value(shift->left, &sval) || sval.value != 1) 1964 return false; 1965 var = strip_expr(shift->right); 1966 1967 bit_info = get_bit_info(mask); 1968 if (!bit_info) 1969 return false; 1970 if (!bit_info->possible) 1971 return false; 1972 1973 get_absolute_rl(var, &orig_rl); 1974 if (sval_is_negative(rl_min(orig_rl)) || 1975 rl_max(orig_rl).uvalue > type_bits(get_type(shift->left))) 1976 return false; 1977 1978 low.value = ffsll(bit_info->possible); 1979 high.value = sm_fls64(bit_info->possible); 1980 rl = alloc_rl(low, high); 1981 rl = cast_rl(get_type(var), rl); 1982 rl = rl_intersection(orig_rl, rl); 1983 if (!rl) 1984 return false; 1985 1986 set_extra_expr_true_false(shift->right, alloc_estate_rl(rl), NULL); 1987 1988 return true; 1989 } 1990 1991 static void handle_AND_op(struct expression *var, sval_t known) 1992 { 1993 struct range_list *orig_rl; 1994 struct range_list *true_rl = NULL; 1995 struct range_list *false_rl = NULL; 1996 int bit; 1997 sval_t low_mask = known; 1998 sval_t high_mask; 1999 sval_t max; 2000 2001 get_absolute_rl(var, &orig_rl); 2002 2003 if (known.value > 0) { 2004 bit = ffsll(known.value) - 1; 2005 low_mask.uvalue = (1ULL << bit) - 1; 2006 true_rl = remove_range(orig_rl, sval_type_val(known.type, 0), low_mask); 2007 } 2008 high_mask = get_high_mask(known); 2009 if (high_mask.value) { 2010 bit = ffsll(high_mask.value) - 1; 2011 low_mask.uvalue = (1ULL << bit) - 1; 2012 2013 false_rl = orig_rl; 2014 if (sval_is_negative(rl_min(orig_rl))) 2015 false_rl = remove_range(false_rl, sval_type_min(known.type), sval_type_val(known.type, -1)); 2016 false_rl = remove_range(false_rl, low_mask, sval_type_max(known.type)); 2017 if (type_signed(high_mask.type) && type_unsigned(rl_type(false_rl))) { 2018 false_rl = remove_range(false_rl, 2019 sval_type_val(rl_type(false_rl), sval_type_max(known.type).uvalue), 2020 sval_type_val(rl_type(false_rl), -1)); 2021 } 2022 } else if (known.value == 1 && 2023 get_hard_max(var, &max) && 2024 sval_cmp(max, rl_max(orig_rl)) == 0 && 2025 max.value & 1) { 2026 false_rl = remove_range(orig_rl, max, max); 2027 } 2028 set_extra_expr_true_false(var, 2029 true_rl ? alloc_estate_rl(true_rl) : NULL, 2030 false_rl ? alloc_estate_rl(false_rl) : NULL); 2031 } 2032 2033 static void handle_AND_condition(struct expression *expr) 2034 { 2035 sval_t known; 2036 2037 if (handle_bit_test(expr)) 2038 return; 2039 2040 if (get_implied_value(expr->left, &known)) 2041 handle_AND_op(expr->right, known); 2042 else if (get_implied_value(expr->right, &known)) 2043 handle_AND_op(expr->left, known); 2044 } 2045 2046 static void handle_MOD_condition(struct expression *expr) 2047 { 2048 struct range_list *orig_rl; 2049 struct range_list *true_rl; 2050 struct range_list *false_rl = NULL; 2051 sval_t right; 2052 sval_t zero = { 0, }; 2053 2054 if (!get_implied_value(expr->right, &right) || right.value == 0) 2055 return; 2056 get_absolute_rl(expr->left, &orig_rl); 2057 2058 zero.value = 0; 2059 zero.type = rl_type(orig_rl); 2060 2061 /* We're basically dorking around the min and max here */ 2062 true_rl = remove_range(orig_rl, zero, zero); 2063 if (!sval_is_max(rl_max(true_rl)) && 2064 !(rl_max(true_rl).value % right.value)) 2065 true_rl = remove_range(true_rl, rl_max(true_rl), rl_max(true_rl)); 2066 2067 if (rl_equiv(true_rl, orig_rl)) 2068 true_rl = NULL; 2069 2070 if (sval_is_positive(rl_min(orig_rl)) && 2071 (rl_max(orig_rl).value - rl_min(orig_rl).value) / right.value < 5) { 2072 sval_t add; 2073 int i; 2074 2075 add = rl_min(orig_rl); 2076 add.value += right.value - (add.value % right.value); 2077 add.value -= right.value; 2078 2079 for (i = 0; i < 5; i++) { 2080 add.value += right.value; 2081 if (add.value > rl_max(orig_rl).value) 2082 break; 2083 add_range(&false_rl, add, add); 2084 } 2085 } else { 2086 if (rl_min(orig_rl).uvalue != 0 && 2087 rl_min(orig_rl).uvalue < right.uvalue) { 2088 sval_t chop = right; 2089 chop.value--; 2090 false_rl = remove_range(orig_rl, zero, chop); 2091 } 2092 2093 if (!sval_is_max(rl_max(orig_rl)) && 2094 (rl_max(orig_rl).value % right.value)) { 2095 sval_t chop = rl_max(orig_rl); 2096 chop.value -= chop.value % right.value; 2097 chop.value++; 2098 if (!false_rl) 2099 false_rl = clone_rl(orig_rl); 2100 false_rl = remove_range(false_rl, chop, rl_max(orig_rl)); 2101 } 2102 } 2103 2104 set_extra_expr_true_false(expr->left, 2105 true_rl ? alloc_estate_rl(true_rl) : NULL, 2106 false_rl ? alloc_estate_rl(false_rl) : NULL); 2107 } 2108 2109 /* this is actually hooked from smatch_implied.c... it's hacky, yes */ 2110 void __extra_match_condition(struct expression *expr) 2111 { 2112 expr = strip_expr(expr); 2113 switch (expr->type) { 2114 case EXPR_CALL: 2115 function_comparison(expr, SPECIAL_NOTEQUAL, zero_expr()); 2116 return; 2117 case EXPR_PREOP: 2118 case EXPR_SYMBOL: 2119 case EXPR_DEREF: 2120 handle_comparison(get_type(expr), expr, SPECIAL_NOTEQUAL, zero_expr()); 2121 return; 2122 case EXPR_COMPARE: 2123 match_comparison(expr); 2124 return; 2125 case EXPR_ASSIGNMENT: 2126 __extra_match_condition(expr->left); 2127 return; 2128 case EXPR_BINOP: 2129 if (expr->op == '&') 2130 handle_AND_condition(expr); 2131 if (expr->op == '%') 2132 handle_MOD_condition(expr); 2133 return; 2134 } 2135 } 2136 2137 static void assume_indexes_are_valid(struct expression *expr) 2138 { 2139 struct expression *array_expr; 2140 int array_size; 2141 struct expression *offset; 2142 struct symbol *offset_type; 2143 struct range_list *rl_before; 2144 struct range_list *rl_after; 2145 struct range_list *filter = NULL; 2146 sval_t size; 2147 2148 expr = strip_expr(expr); 2149 if (!is_array(expr)) 2150 return; 2151 2152 offset = get_array_offset(expr); 2153 offset_type = get_type(offset); 2154 if (offset_type && type_signed(offset_type)) { 2155 filter = alloc_rl(sval_type_min(offset_type), 2156 sval_type_val(offset_type, -1)); 2157 } 2158 2159 array_expr = get_array_base(expr); 2160 array_size = get_real_array_size(array_expr); 2161 if (array_size > 1) { 2162 size = sval_type_val(offset_type, array_size); 2163 add_range(&filter, size, sval_type_max(offset_type)); 2164 } 2165 2166 if (!filter) 2167 return; 2168 get_absolute_rl(offset, &rl_before); 2169 rl_after = rl_filter(rl_before, filter); 2170 if (rl_equiv(rl_before, rl_after)) 2171 return; 2172 set_extra_expr_nomod(offset, alloc_estate_rl(rl_after)); 2173 } 2174 2175 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */ 2176 int implied_not_equal(struct expression *expr, long long val) 2177 { 2178 return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val)); 2179 } 2180 2181 int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val) 2182 { 2183 struct smatch_state *estate; 2184 2185 estate = get_state(SMATCH_EXTRA, name, sym); 2186 if (!estate) 2187 return 0; 2188 if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0))) 2189 return 1; 2190 return 0; 2191 } 2192 2193 int parent_is_null_var_sym(const char *name, struct symbol *sym) 2194 { 2195 char buf[256]; 2196 char *start; 2197 char *end; 2198 struct smatch_state *state; 2199 2200 strncpy(buf, name, sizeof(buf) - 1); 2201 buf[sizeof(buf) - 1] = '\0'; 2202 2203 start = &buf[0]; 2204 while (*start == '*') { 2205 start++; 2206 state = get_state(SMATCH_EXTRA, start, sym); 2207 if (!state) 2208 continue; 2209 if (!estate_rl(state)) 2210 return 1; 2211 if (estate_min(state).value == 0 && 2212 estate_max(state).value == 0) 2213 return 1; 2214 } 2215 2216 start = &buf[0]; 2217 while (*start == '&') 2218 start++; 2219 2220 while ((end = strrchr(start, '-'))) { 2221 *end = '\0'; 2222 state = __get_state(SMATCH_EXTRA, start, sym); 2223 if (!state) 2224 continue; 2225 if (estate_min(state).value == 0 && 2226 estate_max(state).value == 0) 2227 return 1; 2228 } 2229 return 0; 2230 } 2231 2232 int parent_is_null(struct expression *expr) 2233 { 2234 struct symbol *sym; 2235 char *var; 2236 int ret = 0; 2237 2238 expr = strip_expr(expr); 2239 var = expr_to_var_sym(expr, &sym); 2240 if (!var || !sym) 2241 goto free; 2242 ret = parent_is_null_var_sym(var, sym); 2243 free: 2244 free_string(var); 2245 return ret; 2246 } 2247 2248 static int param_used_callback(void *found, int argc, char **argv, char **azColName) 2249 { 2250 *(int *)found = 1; 2251 return 0; 2252 } 2253 2254 static int is_kzalloc_info(struct sm_state *sm) 2255 { 2256 sval_t sval; 2257 2258 /* 2259 * kzalloc() information is treated as special because so there is just 2260 * a lot of stuff initialized to zero and it makes building the database 2261 * take hours and hours. 2262 * 2263 * In theory, we should just remove this line and not pass any unused 2264 * information, but I'm not sure enough that this code works so I want 2265 * to hold off on that for now. 2266 */ 2267 if (!estate_get_single_value(sm->state, &sval)) 2268 return 0; 2269 if (sval.value != 0) 2270 return 0; 2271 return 1; 2272 } 2273 2274 static int is_really_long(struct sm_state *sm) 2275 { 2276 const char *p; 2277 int cnt = 0; 2278 2279 p = sm->name; 2280 while ((p = strstr(p, "->"))) { 2281 p += 2; 2282 cnt++; 2283 } 2284 2285 if (cnt < 3 || 2286 strlen(sm->name) < 40) 2287 return 0; 2288 return 1; 2289 } 2290 2291 static int filter_unused_param_value_info(struct expression *call, int param, char *printed_name, struct sm_state *sm) 2292 { 2293 int found = 0; 2294 2295 /* for function pointers assume everything is used */ 2296 if (call->fn->type != EXPR_SYMBOL) 2297 return 0; 2298 2299 /* 2300 * This is to handle __builtin_mul_overflow(). In an ideal world we 2301 * would only need this for invalid code. 2302 * 2303 */ 2304 if (!call->fn->symbol) 2305 return 0; 2306 2307 if (!is_kzalloc_info(sm) && !is_really_long(sm)) 2308 return 0; 2309 2310 run_sql(¶m_used_callback, &found, 2311 "select * from return_implies where %s and type = %d and parameter = %d and key = '%s';", 2312 get_static_filter(call->fn->symbol), PARAM_USED, param, printed_name); 2313 if (found) 2314 return 0; 2315 2316 /* If the database is not built yet, then assume everything is used */ 2317 run_sql(¶m_used_callback, &found, 2318 "select * from return_implies where %s and type = %d;", 2319 get_static_filter(call->fn->symbol), PARAM_USED); 2320 if (!found) 2321 return 0; 2322 2323 return 1; 2324 } 2325 2326 struct range_list *intersect_with_real_abs_var_sym(const char *name, struct symbol *sym, struct range_list *start) 2327 { 2328 struct smatch_state *state; 2329 2330 /* 2331 * Here is the difference between implied value and real absolute, say 2332 * you have: 2333 * 2334 * int a = (u8)x; 2335 * 2336 * Then you know that a is 0-255. That's real absolute. But you don't 2337 * know for sure that it actually goes up to 255. So it's not implied. 2338 * Implied indicates a degree of certainty. 2339 * 2340 * But then say you cap "a" at 8. That means you know it goes up to 2341 * 8. So now the implied value is s32min-8. But you can combine it 2342 * with the real absolute to say that actually it's 0-8. 2343 * 2344 * We are combining it here. But now that I think about it, this is 2345 * probably not the ideal place to combine it because it should proably 2346 * be done earlier. Oh well, this is an improvement on what was there 2347 * before so I'm going to commit this code. 2348 * 2349 */ 2350 2351 state = get_real_absolute_state_var_sym(name, sym); 2352 if (!state || !estate_rl(state)) 2353 return start; 2354 2355 return rl_intersection(estate_rl(state), start); 2356 } 2357 2358 struct range_list *intersect_with_real_abs_expr(struct expression *expr, struct range_list *start) 2359 { 2360 struct smatch_state *state; 2361 struct range_list *abs_rl; 2362 2363 state = get_real_absolute_state(expr); 2364 if (!state || !estate_rl(state)) 2365 return start; 2366 2367 abs_rl = cast_rl(rl_type(start), estate_rl(state)); 2368 return rl_intersection(abs_rl, start); 2369 } 2370 2371 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm) 2372 { 2373 struct range_list *rl; 2374 sval_t dummy; 2375 2376 if (estate_is_whole(sm->state)) 2377 return; 2378 if (filter_unused_param_value_info(call, param, printed_name, sm)) 2379 return; 2380 rl = estate_rl(sm->state); 2381 rl = intersect_with_real_abs_var_sym(sm->name, sm->sym, rl); 2382 sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, show_rl(rl)); 2383 if (!estate_get_single_value(sm->state, &dummy)) { 2384 if (estate_has_hard_max(sm->state)) 2385 sql_insert_caller_info(call, HARD_MAX, param, printed_name, 2386 sval_to_str(estate_max(sm->state))); 2387 if (estate_has_fuzzy_max(sm->state)) 2388 sql_insert_caller_info(call, FUZZY_MAX, param, printed_name, 2389 sval_to_str(estate_get_fuzzy_max(sm->state))); 2390 } 2391 } 2392 2393 static void returned_struct_members(int return_id, char *return_ranges, struct expression *expr) 2394 { 2395 struct symbol *returned_sym; 2396 char *returned_name; 2397 struct sm_state *sm; 2398 char *compare_str; 2399 char name_buf[256]; 2400 char val_buf[256]; 2401 int len; 2402 2403 // FIXME handle *$ 2404 2405 if (!is_pointer(expr)) 2406 return; 2407 2408 returned_name = expr_to_var_sym(expr, &returned_sym); 2409 if (!returned_name || !returned_sym) 2410 goto free; 2411 len = strlen(returned_name); 2412 2413 FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) { 2414 if (!estate_rl(sm->state)) 2415 continue; 2416 if (returned_sym != sm->sym) 2417 continue; 2418 if (strncmp(returned_name, sm->name, len) != 0) 2419 continue; 2420 if (sm->name[len] != '-') 2421 continue; 2422 2423 snprintf(name_buf, sizeof(name_buf), "$%s", sm->name + len); 2424 2425 compare_str = name_sym_to_param_comparison(sm->name, sm->sym); 2426 if (!compare_str && estate_is_whole(sm->state)) 2427 continue; 2428 snprintf(val_buf, sizeof(val_buf), "%s%s", sm->state->name, compare_str ?: ""); 2429 2430 sql_insert_return_states(return_id, return_ranges, PARAM_VALUE, 2431 -1, name_buf, val_buf); 2432 } END_FOR_EACH_SM(sm); 2433 2434 free: 2435 free_string(returned_name); 2436 } 2437 2438 static void db_limited_before(void) 2439 { 2440 unmatched_stree = clone_stree(__get_cur_stree()); 2441 } 2442 2443 static void db_limited_after(void) 2444 { 2445 free_stree(&unmatched_stree); 2446 } 2447 2448 static int basically_the_same(struct range_list *orig, struct range_list *new) 2449 { 2450 if (rl_equiv(orig, new)) 2451 return 1; 2452 2453 /* 2454 * The whole range is essentially the same as 0,4096-27777777777 so 2455 * don't overwrite the implications just to store that. 2456 * 2457 */ 2458 if (rl_type(orig)->type == SYM_PTR && 2459 is_whole_rl(orig) && 2460 rl_min(new).value == 0 && 2461 rl_max(new).value == valid_ptr_max) 2462 return 1; 2463 return 0; 2464 } 2465 2466 static void db_param_limit_binops(struct expression *arg, char *key, struct range_list *rl) 2467 { 2468 struct range_list *left_rl; 2469 sval_t zero = { .type = rl_type(rl), }; 2470 sval_t sval; 2471 2472 if (arg->op != '*') 2473 return; 2474 if (!get_implied_value(arg->right, &sval)) 2475 return; 2476 if (can_integer_overflow(get_type(arg), arg)) 2477 return; 2478 2479 left_rl = rl_binop(rl, '/', alloc_rl(sval, sval)); 2480 if (!rl_has_sval(rl, zero)) 2481 left_rl = remove_range(left_rl, zero, zero); 2482 2483 set_extra_expr_nomod(arg->left, alloc_estate_rl(left_rl)); 2484 } 2485 2486 static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, enum info_type op) 2487 { 2488 struct expression *arg; 2489 char *name; 2490 struct symbol *sym; 2491 struct var_sym_list *vsl = NULL; 2492 struct sm_state *sm; 2493 struct symbol *compare_type, *var_type; 2494 struct range_list *rl; 2495 struct range_list *limit; 2496 struct range_list *new; 2497 char *other_name; 2498 struct symbol *other_sym; 2499 2500 while (expr->type == EXPR_ASSIGNMENT) 2501 expr = strip_expr(expr->right); 2502 if (expr->type != EXPR_CALL) 2503 return; 2504 2505 arg = get_argument_from_call_expr(expr->args, param); 2506 if (!arg) 2507 return; 2508 2509 if (strcmp(key, "$") == 0) 2510 compare_type = get_arg_type(expr->fn, param); 2511 else 2512 compare_type = get_member_type_from_key(arg, key); 2513 2514 call_results_to_rl(expr, compare_type, value, &limit); 2515 if (strcmp(key, "$") == 0) 2516 move_known_to_rl(&arg, &limit); 2517 name = get_chunk_from_key(arg, key, &sym, &vsl); 2518 if (!name) 2519 return; 2520 if (op != PARAM_LIMIT && !sym) 2521 goto free; 2522 2523 sm = get_sm_state(SMATCH_EXTRA, name, sym); 2524 if (sm) 2525 rl = estate_rl(sm->state); 2526 else 2527 rl = alloc_whole_rl(compare_type); 2528 2529 if (op == PARAM_LIMIT && !rl_fits_in_type(rl, compare_type)) 2530 goto free; 2531 2532 new = rl_intersection(rl, limit); 2533 2534 var_type = get_member_type_from_key(arg, key); 2535 new = cast_rl(var_type, new); 2536 2537 /* We want to preserve the implications here */ 2538 if (sm && basically_the_same(rl, new)) 2539 goto free; 2540 other_name = get_other_name_sym(name, sym, &other_sym); 2541 2542 if (op == PARAM_LIMIT) 2543 set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(new)); 2544 else 2545 set_extra_mod(name, sym, NULL, alloc_estate_rl(new)); 2546 2547 if (other_name && other_sym) { 2548 if (op == PARAM_LIMIT) 2549 set_extra_nomod_vsl(other_name, other_sym, vsl, NULL, alloc_estate_rl(new)); 2550 else 2551 set_extra_mod(other_name, other_sym, NULL, alloc_estate_rl(new)); 2552 } 2553 2554 if (op == PARAM_LIMIT && arg->type == EXPR_BINOP) 2555 db_param_limit_binops(arg, key, new); 2556 free: 2557 free_string(name); 2558 } 2559 2560 static void db_param_limit(struct expression *expr, int param, char *key, char *value) 2561 { 2562 db_param_limit_filter(expr, param, key, value, PARAM_LIMIT); 2563 } 2564 2565 static void db_param_filter(struct expression *expr, int param, char *key, char *value) 2566 { 2567 db_param_limit_filter(expr, param, key, value, PARAM_FILTER); 2568 } 2569 2570 static void db_param_add_set(struct expression *expr, int param, char *key, char *value, enum info_type op) 2571 { 2572 struct expression *arg; 2573 char *name; 2574 char *other_name = NULL; 2575 struct symbol *sym, *other_sym; 2576 struct symbol *param_type, *arg_type; 2577 struct smatch_state *state; 2578 struct range_list *new = NULL; 2579 struct range_list *added = NULL; 2580 2581 while (expr->type == EXPR_ASSIGNMENT) 2582 expr = strip_expr(expr->right); 2583 if (expr->type != EXPR_CALL) 2584 return; 2585 2586 arg = get_argument_from_call_expr(expr->args, param); 2587 if (!arg) 2588 return; 2589 2590 arg_type = get_arg_type_from_key(expr->fn, param, arg, key); 2591 param_type = get_member_type_from_key(arg, key); 2592 name = get_variable_from_key(arg, key, &sym); 2593 if (!name || !sym) 2594 goto free; 2595 2596 state = get_state(SMATCH_EXTRA, name, sym); 2597 if (state) 2598 new = estate_rl(state); 2599 2600 call_results_to_rl(expr, arg_type, value, &added); 2601 added = cast_rl(param_type, added); 2602 if (op == PARAM_SET) 2603 new = added; 2604 else 2605 new = rl_union(new, added); 2606 2607 other_name = get_other_name_sym_nostack(name, sym, &other_sym); 2608 set_extra_mod(name, sym, NULL, alloc_estate_rl(new)); 2609 if (other_name && other_sym) 2610 set_extra_mod(other_name, other_sym, NULL, alloc_estate_rl(new)); 2611 free: 2612 free_string(other_name); 2613 free_string(name); 2614 } 2615 2616 static void db_param_add(struct expression *expr, int param, char *key, char *value) 2617 { 2618 in_param_set = true; 2619 db_param_add_set(expr, param, key, value, PARAM_ADD); 2620 in_param_set = false; 2621 } 2622 2623 static void db_param_set(struct expression *expr, int param, char *key, char *value) 2624 { 2625 in_param_set = true; 2626 db_param_add_set(expr, param, key, value, PARAM_SET); 2627 in_param_set = false; 2628 } 2629 2630 static void match_lost_param(struct expression *call, int param) 2631 { 2632 struct expression *arg; 2633 2634 if (is_const_param(call->fn, param)) 2635 return; 2636 2637 arg = get_argument_from_call_expr(call->args, param); 2638 if (!arg) 2639 return; 2640 2641 arg = strip_expr(arg); 2642 if (arg->type == EXPR_PREOP && arg->op == '&') 2643 set_extra_expr_mod(arg->unop, alloc_estate_whole(get_type(arg->unop))); 2644 else 2645 ; /* if pointer then set struct members, maybe?*/ 2646 } 2647 2648 static void db_param_value(struct expression *expr, int param, char *key, char *value) 2649 { 2650 struct expression *call; 2651 char *name; 2652 struct symbol *sym; 2653 struct symbol *type; 2654 struct range_list *rl = NULL; 2655 2656 if (param != -1) 2657 return; 2658 2659 call = expr; 2660 while (call->type == EXPR_ASSIGNMENT) 2661 call = strip_expr(call->right); 2662 if (call->type != EXPR_CALL) 2663 return; 2664 2665 type = get_member_type_from_key(expr->left, key); 2666 name = get_variable_from_key(expr->left, key, &sym); 2667 if (!name || !sym) 2668 goto free; 2669 2670 call_results_to_rl(call, type, value, &rl); 2671 2672 set_extra_mod(name, sym, NULL, alloc_estate_rl(rl)); 2673 free: 2674 free_string(name); 2675 } 2676 2677 static void match_call_info(struct expression *expr) 2678 { 2679 struct smatch_state *state; 2680 struct range_list *rl = NULL; 2681 struct expression *arg; 2682 struct symbol *type; 2683 sval_t dummy; 2684 int i = 0; 2685 2686 FOR_EACH_PTR(expr->args, arg) { 2687 type = get_arg_type(expr->fn, i); 2688 2689 get_absolute_rl(arg, &rl); 2690 rl = cast_rl(type, rl); 2691 2692 if (!is_whole_rl(rl)) { 2693 rl = intersect_with_real_abs_expr(arg, rl); 2694 sql_insert_caller_info(expr, PARAM_VALUE, i, "$", show_rl(rl)); 2695 } 2696 state = get_state_expr(SMATCH_EXTRA, arg); 2697 if (!estate_get_single_value(state, &dummy) && estate_has_hard_max(state)) { 2698 sql_insert_caller_info(expr, HARD_MAX, i, "$", 2699 sval_to_str(estate_max(state))); 2700 } 2701 if (estate_has_fuzzy_max(state)) { 2702 sql_insert_caller_info(expr, FUZZY_MAX, i, "$", 2703 sval_to_str(estate_get_fuzzy_max(state))); 2704 } 2705 i++; 2706 } END_FOR_EACH_PTR(arg); 2707 } 2708 2709 static void set_param_value(const char *name, struct symbol *sym, char *key, char *value) 2710 { 2711 struct expression *expr; 2712 struct range_list *rl = NULL; 2713 struct smatch_state *state; 2714 struct symbol *type; 2715 char fullname[256]; 2716 char *key_orig = key; 2717 bool add_star = false; 2718 sval_t dummy; 2719 2720 if (key[0] == '*') { 2721 add_star = true; 2722 key++; 2723 } 2724 2725 snprintf(fullname, 256, "%s%s%s", add_star ? "*" : "", name, key + 1); 2726 2727 expr = symbol_expression(sym); 2728 type = get_member_type_from_key(expr, key_orig); 2729 str_to_rl(type, value, &rl); 2730 state = alloc_estate_rl(rl); 2731 if (estate_get_single_value(state, &dummy)) 2732 estate_set_hard_max(state); 2733 set_state(SMATCH_EXTRA, fullname, sym, state); 2734 } 2735 2736 static void set_param_fuzzy_max(const char *name, struct symbol *sym, char *key, char *value) 2737 { 2738 struct range_list *rl = NULL; 2739 struct smatch_state *state; 2740 struct symbol *type; 2741 char fullname[256]; 2742 sval_t max; 2743 2744 if (strcmp(key, "*$") == 0) 2745 snprintf(fullname, sizeof(fullname), "*%s", name); 2746 else if (strncmp(key, "$", 1) == 0) 2747 snprintf(fullname, 256, "%s%s", name, key + 1); 2748 else 2749 return; 2750 2751 state = get_state(SMATCH_EXTRA, fullname, sym); 2752 if (!state) 2753 return; 2754 type = estate_type(state); 2755 str_to_rl(type, value, &rl); 2756 if (!rl_to_sval(rl, &max)) 2757 return; 2758 estate_set_fuzzy_max(state, max); 2759 } 2760 2761 static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value) 2762 { 2763 struct smatch_state *state; 2764 char fullname[256]; 2765 2766 if (strcmp(key, "*$") == 0) 2767 snprintf(fullname, sizeof(fullname), "*%s", name); 2768 else if (strncmp(key, "$", 1) == 0) 2769 snprintf(fullname, 256, "%s%s", name, key + 1); 2770 else 2771 return; 2772 2773 state = get_state(SMATCH_EXTRA, fullname, sym); 2774 if (!state) 2775 return; 2776 estate_set_hard_max(state); 2777 } 2778 2779 struct sm_state *get_extra_sm_state(struct expression *expr) 2780 { 2781 char *name; 2782 struct symbol *sym; 2783 struct sm_state *ret = NULL; 2784 2785 name = expr_to_known_chunk_sym(expr, &sym); 2786 if (!name) 2787 goto free; 2788 2789 ret = get_sm_state(SMATCH_EXTRA, name, sym); 2790 free: 2791 free_string(name); 2792 return ret; 2793 } 2794 2795 struct smatch_state *get_extra_state(struct expression *expr) 2796 { 2797 struct sm_state *sm; 2798 2799 sm = get_extra_sm_state(expr); 2800 if (!sm) 2801 return NULL; 2802 return sm->state; 2803 } 2804 2805 void register_smatch_extra(int id) 2806 { 2807 my_id = id; 2808 2809 set_dynamic_states(my_id); 2810 add_merge_hook(my_id, &merge_estates); 2811 add_unmatched_state_hook(my_id, &unmatched_state); 2812 select_caller_info_hook(set_param_value, PARAM_VALUE); 2813 select_caller_info_hook(set_param_fuzzy_max, FUZZY_MAX); 2814 select_caller_info_hook(set_param_hard_max, HARD_MAX); 2815 select_return_states_before(&db_limited_before); 2816 select_return_states_hook(PARAM_LIMIT, &db_param_limit); 2817 select_return_states_hook(PARAM_FILTER, &db_param_filter); 2818 select_return_states_hook(PARAM_ADD, &db_param_add); 2819 select_return_states_hook(PARAM_SET, &db_param_set); 2820 add_lost_param_hook(&match_lost_param); 2821 select_return_states_hook(PARAM_VALUE, &db_param_value); 2822 select_return_states_after(&db_limited_after); 2823 } 2824 2825 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr) 2826 { 2827 struct var_sym_list *links; 2828 struct var_sym *tmp; 2829 struct smatch_state *state; 2830 2831 links = sm->state->data; 2832 2833 FOR_EACH_PTR(links, tmp) { 2834 if (sm->sym == tmp->sym && 2835 strcmp(sm->name, tmp->var) == 0) 2836 continue; 2837 state = get_state(SMATCH_EXTRA, tmp->var, tmp->sym); 2838 if (!state) 2839 continue; 2840 set_state(SMATCH_EXTRA, tmp->var, tmp->sym, alloc_estate_whole(estate_type(state))); 2841 } END_FOR_EACH_PTR(tmp); 2842 set_state(link_id, sm->name, sm->sym, &undefined); 2843 } 2844 2845 void register_smatch_extra_links(int id) 2846 { 2847 link_id = id; 2848 set_dynamic_states(link_id); 2849 } 2850 2851 void register_smatch_extra_late(int id) 2852 { 2853 add_merge_hook(link_id, &merge_link_states); 2854 add_modification_hook(link_id, &match_link_modify); 2855 add_hook(&match_dereferences, DEREF_HOOK); 2856 add_hook(&match_pointer_as_array, OP_HOOK); 2857 select_return_implies_hook(DEREFERENCE, &set_param_dereferenced); 2858 add_hook(&match_function_call, FUNCTION_CALL_HOOK); 2859 add_hook(&match_assign, ASSIGNMENT_HOOK); 2860 add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK); 2861 add_hook(&unop_expr, OP_HOOK); 2862 add_hook(&asm_expr, ASM_HOOK); 2863 2864 add_hook(&match_call_info, FUNCTION_CALL_HOOK); 2865 add_member_info_callback(my_id, struct_member_callback); 2866 add_split_return_callback(&returned_struct_members); 2867 2868 // add_hook(&assume_indexes_are_valid, OP_HOOK); 2869 }