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