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