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