1 /* 2 * Copyright (C) 2009 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 * There are several types of function hooks: 20 * add_function_hook() - For any time a function is called. 21 * add_function_assign_hook() - foo = the_function(). 22 * add_implied_return_hook() - Calculates the implied return value. 23 * add_macro_assign_hook() - foo = the_macro(). 24 * return_implies_state() - For when a return value of 1 implies locked 25 * and 0 implies unlocked. etc. etc. 26 * 27 */ 28 29 #include <stdlib.h> 30 #include <stdio.h> 31 #include "smatch.h" 32 #include "smatch_slist.h" 33 #include "smatch_extra.h" 34 #include "smatch_function_hashtable.h" 35 36 struct fcall_back { 37 int type; 38 struct data_range *range; 39 union { 40 func_hook *call_back; 41 implication_hook *ranged; 42 implied_return_hook *implied_return; 43 } u; 44 void *info; 45 }; 46 47 ALLOCATOR(fcall_back, "call backs"); 48 DECLARE_PTR_LIST(call_back_list, struct fcall_back); 49 50 DEFINE_FUNCTION_HASHTABLE_STATIC(callback, struct fcall_back, struct call_back_list); 51 static struct hashtable *func_hash; 52 53 int __in_fake_parameter_assign; 54 55 #define REGULAR_CALL 0 56 #define RANGED_CALL 1 57 #define ASSIGN_CALL 2 58 #define IMPLIED_RETURN 3 59 #define MACRO_ASSIGN 4 60 #define MACRO_ASSIGN_EXTRA 5 61 62 struct return_implies_callback { 63 int type; 64 return_implies_hook *callback; 65 }; 66 ALLOCATOR(return_implies_callback, "return_implies callbacks"); 67 DECLARE_PTR_LIST(db_implies_list, struct return_implies_callback); 68 static struct db_implies_list *db_return_states_list; 69 70 typedef void (void_fn)(void); 71 DECLARE_PTR_LIST(void_fn_list, void_fn *); 72 static struct void_fn_list *return_states_before; 73 static struct void_fn_list *return_states_after; 74 75 static struct fcall_back *alloc_fcall_back(int type, void *call_back, 76 void *info) 77 { 78 struct fcall_back *cb; 79 80 cb = __alloc_fcall_back(0); 81 cb->type = type; 82 cb->u.call_back = call_back; 83 cb->info = info; 84 return cb; 85 } 86 87 void add_function_hook(const char *look_for, func_hook *call_back, void *info) 88 { 89 struct fcall_back *cb; 90 91 cb = alloc_fcall_back(REGULAR_CALL, call_back, info); 92 add_callback(func_hash, look_for, cb); 93 } 94 95 void add_function_assign_hook(const char *look_for, func_hook *call_back, 96 void *info) 97 { 98 struct fcall_back *cb; 99 100 cb = alloc_fcall_back(ASSIGN_CALL, call_back, info); 101 add_callback(func_hash, look_for, cb); 102 } 103 104 void add_implied_return_hook(const char *look_for, 105 implied_return_hook *call_back, 106 void *info) 107 { 108 struct fcall_back *cb; 109 110 cb = alloc_fcall_back(IMPLIED_RETURN, call_back, info); 111 add_callback(func_hash, look_for, cb); 112 } 113 114 void add_macro_assign_hook(const char *look_for, func_hook *call_back, 115 void *info) 116 { 117 struct fcall_back *cb; 118 119 cb = alloc_fcall_back(MACRO_ASSIGN, call_back, info); 120 add_callback(func_hash, look_for, cb); 121 } 122 123 void add_macro_assign_hook_extra(const char *look_for, func_hook *call_back, 124 void *info) 125 { 126 struct fcall_back *cb; 127 128 cb = alloc_fcall_back(MACRO_ASSIGN_EXTRA, call_back, info); 129 add_callback(func_hash, look_for, cb); 130 } 131 132 void return_implies_state(const char *look_for, long long start, long long end, 133 implication_hook *call_back, void *info) 134 { 135 struct fcall_back *cb; 136 137 cb = alloc_fcall_back(RANGED_CALL, call_back, info); 138 cb->range = alloc_range_perm(ll_to_sval(start), ll_to_sval(end)); 139 add_callback(func_hash, look_for, cb); 140 } 141 142 void return_implies_state_sval(const char *look_for, sval_t start, sval_t end, 143 implication_hook *call_back, void *info) 144 { 145 struct fcall_back *cb; 146 147 cb = alloc_fcall_back(RANGED_CALL, call_back, info); 148 cb->range = alloc_range_perm(start, end); 149 add_callback(func_hash, look_for, cb); 150 } 151 152 void select_return_states_hook(int type, return_implies_hook *callback) 153 { 154 struct return_implies_callback *cb = __alloc_return_implies_callback(0); 155 156 cb->type = type; 157 cb->callback = callback; 158 add_ptr_list(&db_return_states_list, cb); 159 } 160 161 void select_return_states_before(void_fn *fn) 162 { 163 void_fn **p = malloc(sizeof(void_fn *)); 164 *p = fn; 165 add_ptr_list(&return_states_before, p); 166 } 167 168 void select_return_states_after(void_fn *fn) 169 { 170 void_fn **p = malloc(sizeof(void_fn *)); 171 *p = fn; 172 add_ptr_list(&return_states_after, p); 173 } 174 175 static void call_return_states_before_hooks(void) 176 { 177 void_fn **fn; 178 179 FOR_EACH_PTR(return_states_before, fn) { 180 (*fn)(); 181 } END_FOR_EACH_PTR(fn); 182 } 183 184 static void call_return_states_after_hooks(struct expression *expr) 185 { 186 void_fn **fn; 187 188 FOR_EACH_PTR(return_states_after, fn) { 189 (*fn)(); 190 } END_FOR_EACH_PTR(fn); 191 __pass_to_client(expr, FUNCTION_CALL_HOOK_AFTER_DB); 192 } 193 194 static int call_call_backs(struct call_back_list *list, int type, 195 const char *fn, struct expression *expr) 196 { 197 struct fcall_back *tmp; 198 int handled = 0; 199 200 FOR_EACH_PTR(list, tmp) { 201 if (tmp->type == type) { 202 (tmp->u.call_back)(fn, expr, tmp->info); 203 handled = 1; 204 } 205 } END_FOR_EACH_PTR(tmp); 206 207 return handled; 208 } 209 210 static void call_ranged_call_backs(struct call_back_list *list, 211 const char *fn, struct expression *call_expr, 212 struct expression *assign_expr) 213 { 214 struct fcall_back *tmp; 215 216 FOR_EACH_PTR(list, tmp) { 217 (tmp->u.ranged)(fn, call_expr, assign_expr, tmp->info); 218 } END_FOR_EACH_PTR(tmp); 219 } 220 221 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list, 222 struct data_range *drange) 223 { 224 struct call_back_list *ret = NULL; 225 struct fcall_back *tmp; 226 227 FOR_EACH_PTR(list, tmp) { 228 if (tmp->type != RANGED_CALL) 229 continue; 230 if (ranges_equiv(tmp->range, drange)) 231 add_ptr_list(&ret, tmp); 232 } END_FOR_EACH_PTR(tmp); 233 return ret; 234 } 235 236 static int in_list_exact_sval(struct range_list *list, struct data_range *drange) 237 { 238 struct data_range *tmp; 239 240 FOR_EACH_PTR(list, tmp) { 241 if (ranges_equiv(tmp, drange)) 242 return 1; 243 } END_FOR_EACH_PTR(tmp); 244 return 0; 245 } 246 247 static int assign_ranged_funcs(const char *fn, struct expression *expr, 248 struct call_back_list *call_backs) 249 { 250 struct fcall_back *tmp; 251 struct sm_state *sm; 252 char *var_name; 253 struct symbol *sym; 254 struct smatch_state *estate; 255 struct stree *tmp_stree; 256 struct stree *final_states = NULL; 257 struct range_list *handled_ranges = NULL; 258 struct call_back_list *same_range_call_backs = NULL; 259 struct range_list *rl; 260 int handled = 0; 261 262 if (!call_backs) 263 return 0; 264 265 var_name = expr_to_var_sym(expr->left, &sym); 266 if (!var_name || !sym) 267 goto free; 268 269 FOR_EACH_PTR(call_backs, tmp) { 270 if (tmp->type != RANGED_CALL) 271 continue; 272 273 if (in_list_exact_sval(handled_ranges, tmp->range)) 274 continue; 275 __push_fake_cur_stree(); 276 tack_on(&handled_ranges, tmp->range); 277 278 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range); 279 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr); 280 __free_ptr_list((struct ptr_list **)&same_range_call_backs); 281 282 rl = alloc_rl(tmp->range->min, tmp->range->max); 283 rl = cast_rl(get_type(expr->left), rl); 284 estate = alloc_estate_rl(rl); 285 set_extra_mod(var_name, sym, expr->left, estate); 286 287 tmp_stree = __pop_fake_cur_stree(); 288 merge_fake_stree(&final_states, tmp_stree); 289 free_stree(&tmp_stree); 290 handled = 1; 291 } END_FOR_EACH_PTR(tmp); 292 293 FOR_EACH_SM(final_states, sm) { 294 __set_sm(sm); 295 } END_FOR_EACH_SM(sm); 296 297 free_stree(&final_states); 298 free: 299 free_string(var_name); 300 return handled; 301 } 302 303 static void call_implies_callbacks(int comparison, struct expression *expr, sval_t sval, int left, struct stree **implied_true, struct stree **implied_false) 304 { 305 struct call_back_list *call_backs; 306 struct fcall_back *tmp; 307 const char *fn; 308 struct data_range *value_range; 309 struct stree *true_states = NULL; 310 struct stree *false_states = NULL; 311 struct stree *tmp_stree; 312 313 *implied_true = NULL; 314 *implied_false = NULL; 315 if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol) 316 return; 317 fn = expr->fn->symbol->ident->name; 318 call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name); 319 if (!call_backs) 320 return; 321 value_range = alloc_range(sval, sval); 322 323 /* set true states */ 324 __push_fake_cur_stree(); 325 FOR_EACH_PTR(call_backs, tmp) { 326 if (tmp->type != RANGED_CALL) 327 continue; 328 if (!true_comparison_range_LR(comparison, tmp->range, value_range, left)) 329 continue; 330 (tmp->u.ranged)(fn, expr, NULL, tmp->info); 331 } END_FOR_EACH_PTR(tmp); 332 tmp_stree = __pop_fake_cur_stree(); 333 merge_fake_stree(&true_states, tmp_stree); 334 free_stree(&tmp_stree); 335 336 /* set false states */ 337 __push_fake_cur_stree(); 338 FOR_EACH_PTR(call_backs, tmp) { 339 if (tmp->type != RANGED_CALL) 340 continue; 341 if (!false_comparison_range_LR(comparison, tmp->range, value_range, left)) 342 continue; 343 (tmp->u.ranged)(fn, expr, NULL, tmp->info); 344 } END_FOR_EACH_PTR(tmp); 345 tmp_stree = __pop_fake_cur_stree(); 346 merge_fake_stree(&false_states, tmp_stree); 347 free_stree(&tmp_stree); 348 349 *implied_true = true_states; 350 *implied_false = false_states; 351 } 352 353 struct db_callback_info { 354 int true_side; 355 int comparison; 356 struct expression *expr; 357 struct range_list *rl; 358 int left; 359 struct stree *stree; 360 struct stree *implied; 361 struct db_implies_list *callbacks; 362 int prev_return_id; 363 int cull; 364 int has_states; 365 char *ret_str; 366 struct smatch_state *ret_state; 367 struct expression *var_expr; 368 int handled; 369 }; 370 371 static void set_implied_states(struct db_callback_info *db_info) 372 { 373 struct sm_state *sm; 374 375 FOR_EACH_SM(db_info->implied, sm) { 376 __set_sm(sm); 377 } END_FOR_EACH_SM(sm); 378 379 free_stree(&db_info->implied); 380 } 381 382 static void store_return_state(struct db_callback_info *db_info, const char *ret_str, struct smatch_state *state) 383 { 384 db_info->ret_str = alloc_sname(ret_str), 385 db_info->ret_state = state; 386 } 387 388 static bool fake_a_param_assignment(struct expression *expr, const char *return_str, struct smatch_state *orig) 389 { 390 struct expression *arg, *left, *right, *tmp, *fake_assign; 391 char *p; 392 int param; 393 char buf[256]; 394 char *str; 395 396 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=') 397 return false; 398 left = expr->left; 399 right = expr->right; 400 401 while (right->type == EXPR_ASSIGNMENT) 402 right = strip_expr(right->right); 403 if (!right || right->type != EXPR_CALL) 404 return false; 405 406 p = strchr(return_str, '['); 407 if (!p) 408 return false; 409 410 p++; 411 if (p[0] == '=' && p[1] == '=') 412 p += 2; 413 if (p[0] != '$') 414 return false; 415 416 snprintf(buf, sizeof(buf), "%s", p); 417 418 p = buf; 419 p += 1; 420 param = strtol(p, &p, 10); 421 422 p = strchr(p, ']'); 423 if (!p || *p != ']') 424 return false; 425 *p = '\0'; 426 427 arg = get_argument_from_call_expr(right->args, param); 428 if (!arg) 429 return false; 430 431 /* There should be a get_other_name() function which returns an expr */ 432 tmp = get_assigned_expr(arg); 433 if (tmp) 434 arg = tmp; 435 436 /* 437 * This is a sanity check to prevent side effects from evaluating stuff 438 * twice. 439 */ 440 str = expr_to_chunk_sym_vsl(arg, NULL, NULL); 441 if (!str) 442 return false; 443 free_string(str); 444 445 right = gen_expression_from_key(arg, buf); 446 if (!right) /* Mostly fails for binops like [$0 + 4032] */ 447 return false; 448 fake_assign = assign_expression(left, '=', right); 449 __in_fake_parameter_assign++; 450 __split_expr(fake_assign); 451 __in_fake_parameter_assign--; 452 453 /* 454 * If the return is "0-65531[$0->nla_len - 4]" the faked expression 455 * is maybe (-4)-65531 but we know it is in the 0-65531 range so both 456 * parts have to be considered. We use _nomod() because it's not really 457 * another modification, it's just a clarification. 458 * 459 */ 460 if (estate_rl(orig)) { 461 struct smatch_state *faked; 462 struct range_list *rl; 463 464 faked = get_extra_state(left); 465 if (estate_rl(faked)) { 466 rl = rl_intersection(estate_rl(faked), estate_rl(orig)); 467 if (rl) 468 set_extra_expr_nomod(expr, alloc_estate_rl(rl)); 469 } 470 } 471 472 return true; 473 } 474 475 static void set_fresh_mtag_returns(struct db_callback_info *db_info) 476 { 477 struct expression *expr = db_info->expr->left; 478 struct smatch_state *state; 479 480 if (!db_info->ret_state) 481 return; 482 483 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state)))); 484 state = get_mtag_return(db_info->expr, state); 485 if (!state) 486 return; 487 488 set_real_absolute(expr, state); 489 set_extra_expr_mod(expr, state); 490 491 db_info->ret_state = NULL; 492 db_info->ret_str = NULL; 493 } 494 495 static void set_return_assign_state(struct db_callback_info *db_info) 496 { 497 struct expression *expr = db_info->expr->left; 498 struct smatch_state *state; 499 500 if (!db_info->ret_state) 501 return; 502 503 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state)))); 504 if (!fake_a_param_assignment(db_info->expr, db_info->ret_str, state)) 505 set_extra_expr_mod(expr, state); 506 507 db_info->ret_state = NULL; 508 db_info->ret_str = NULL; 509 } 510 511 static void set_other_side_state(struct db_callback_info *db_info) 512 { 513 struct expression *expr = db_info->var_expr; 514 struct smatch_state *state; 515 516 if (!db_info->ret_state) 517 return; 518 519 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state)))); 520 set_extra_expr_nomod(expr, state); 521 db_info->ret_state = NULL; 522 db_info->ret_str = NULL; 523 } 524 525 static void handle_ret_equals_param(char *ret_string, struct range_list *rl, struct expression *call) 526 { 527 char *str; 528 long long param; 529 struct expression *arg; 530 struct range_list *orig; 531 532 str = strstr(ret_string, "==$"); 533 if (!str) 534 return; 535 str += 3; 536 param = strtoll(str, NULL, 10); 537 arg = get_argument_from_call_expr(call->args, param); 538 if (!arg) 539 return; 540 get_absolute_rl(arg, &orig); 541 rl = rl_intersection(orig, rl); 542 if (!rl) 543 return; 544 set_extra_expr_nomod(arg, alloc_estate_rl(rl)); 545 } 546 547 static int impossible_limit(struct expression *expr, int param, char *key, char *value) 548 { 549 struct expression *arg; 550 struct smatch_state *state; 551 struct range_list *passed; 552 struct range_list *limit; 553 struct symbol *compare_type; 554 555 while (expr->type == EXPR_ASSIGNMENT) 556 expr = strip_expr(expr->right); 557 if (expr->type != EXPR_CALL) 558 return 0; 559 560 arg = get_argument_from_call_expr(expr->args, param); 561 if (!arg) 562 return 0; 563 564 if (strcmp(key, "$") == 0) { 565 if (!get_implied_rl(arg, &passed)) 566 return 0; 567 568 compare_type = get_arg_type(expr->fn, param); 569 } else { 570 char *name; 571 struct symbol *sym; 572 573 name = get_variable_from_key(arg, key, &sym); 574 if (!name || !sym) 575 return 0; 576 577 state = get_state(SMATCH_EXTRA, name, sym); 578 if (!state) { 579 free_string(name); 580 return 0; 581 } 582 passed = estate_rl(state); 583 if (!passed || is_whole_rl(passed)) { 584 free_string(name); 585 return 0; 586 } 587 588 compare_type = get_member_type_from_key(arg, key); 589 } 590 591 passed = cast_rl(compare_type, passed); 592 call_results_to_rl(expr, compare_type, value, &limit); 593 if (!limit || is_whole_rl(limit)) 594 return 0; 595 if (possibly_true_rl(passed, SPECIAL_EQUAL, limit)) 596 return 0; 597 if (option_debug || local_debug) 598 sm_msg("impossible: %d '%s' limit '%s' == '%s'", param, key, show_rl(passed), value); 599 return 1; 600 } 601 602 static int is_impossible_data(int type, struct expression *expr, int param, char *key, char *value) 603 { 604 if (type == PARAM_LIMIT && impossible_limit(expr, param, key, value)) 605 return 1; 606 if (type == COMPARE_LIMIT && param_compare_limit_is_impossible(expr, param, key, value)) { 607 if (local_debug) 608 sm_msg("param_compare_limit_is_impossible: %d %s %s", param, key, value); 609 return 1; 610 } 611 return 0; 612 } 613 614 static int func_type_mismatch(struct expression *expr, const char *value) 615 { 616 struct symbol *type; 617 618 /* This makes faking returns easier */ 619 if (!value || value[0] == '\0') 620 return 0; 621 622 while (expr->type == EXPR_ASSIGNMENT) 623 expr = strip_expr(expr->right); 624 625 /* 626 * Short cut: We only care about function pointers that are struct 627 * members. 628 * 629 */ 630 if (expr->fn->type == EXPR_SYMBOL) 631 return 0; 632 633 type = get_type(expr->fn); 634 if (!type) 635 return 0; 636 if (type->type == SYM_PTR) 637 type = get_real_base_type(type); 638 639 if (strcmp(type_to_str(type), value) == 0) 640 return 0; 641 642 return 1; 643 } 644 645 static int db_compare_callback(void *_info, int argc, char **argv, char **azColName) 646 { 647 struct db_callback_info *db_info = _info; 648 struct range_list *var_rl = db_info->rl; 649 struct range_list *ret_range; 650 int type, param; 651 char *ret_str, *key, *value; 652 struct return_implies_callback *tmp; 653 struct stree *stree; 654 int return_id; 655 int comparison; 656 657 if (argc != 6) 658 return 0; 659 660 return_id = atoi(argv[0]); 661 ret_str = argv[1]; 662 type = atoi(argv[2]); 663 param = atoi(argv[3]); 664 key = argv[4]; 665 value = argv[5]; 666 667 db_info->has_states = 1; 668 if (db_info->prev_return_id != -1 && type == INTERNAL) { 669 set_other_side_state(db_info); 670 set_implied_states(db_info); 671 stree = __pop_fake_cur_stree(); 672 if (!db_info->cull) 673 merge_fake_stree(&db_info->stree, stree); 674 free_stree(&stree); 675 __push_fake_cur_stree(); 676 db_info->cull = 0; 677 } 678 db_info->prev_return_id = return_id; 679 680 if (type == INTERNAL && func_type_mismatch(db_info->expr, value)) 681 db_info->cull = 1; 682 if (db_info->cull) 683 return 0; 684 if (type == CULL_PATH) { 685 db_info->cull = 1; 686 return 0; 687 } 688 689 if (is_impossible_data(type, db_info->expr, param, key, value)) { 690 db_info->cull = 1; 691 return 0; 692 } 693 694 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range); 695 ret_range = cast_rl(get_type(db_info->expr), ret_range); 696 if (!ret_range) 697 ret_range = alloc_whole_rl(get_type(db_info->expr)); 698 699 comparison = db_info->comparison; 700 if (db_info->left) 701 comparison = flip_comparison(comparison); 702 703 if (db_info->true_side) { 704 if (!possibly_true_rl(var_rl, comparison, ret_range)) 705 return 0; 706 if (type == PARAM_LIMIT) 707 param_limit_implications(db_info->expr, param, key, value, &db_info->implied); 708 filter_by_comparison(&var_rl, comparison, ret_range); 709 filter_by_comparison(&ret_range, flip_comparison(comparison), var_rl); 710 } else { 711 if (!possibly_false_rl(var_rl, comparison, ret_range)) 712 return 0; 713 if (type == PARAM_LIMIT) 714 param_limit_implications(db_info->expr, param, key, value, &db_info->implied); 715 filter_by_comparison(&var_rl, negate_comparison(comparison), ret_range); 716 filter_by_comparison(&ret_range, flip_comparison(negate_comparison(comparison)), var_rl); 717 } 718 719 handle_ret_equals_param(ret_str, ret_range, db_info->expr); 720 721 if (type == INTERNAL) { 722 set_state(-1, "unnull_path", NULL, &true_state); 723 __add_return_comparison(strip_expr(db_info->expr), ret_str); 724 __add_return_to_param_mapping(db_info->expr, ret_str); 725 store_return_state(db_info, ret_str, alloc_estate_rl(clone_rl(var_rl))); 726 } 727 728 FOR_EACH_PTR(db_info->callbacks, tmp) { 729 if (tmp->type == type) 730 tmp->callback(db_info->expr, param, key, value); 731 } END_FOR_EACH_PTR(tmp); 732 733 return 0; 734 } 735 736 static void compare_db_return_states_callbacks(struct expression *left, int comparison, struct expression *right, struct stree *implied_true, struct stree *implied_false) 737 { 738 struct stree *orig_states; 739 struct stree *stree; 740 struct stree *true_states; 741 struct stree *false_states; 742 struct sm_state *sm; 743 struct db_callback_info db_info = {}; 744 struct expression *var_expr; 745 struct expression *call_expr; 746 struct range_list *rl; 747 int call_on_left; 748 749 orig_states = clone_stree(__get_cur_stree()); 750 751 /* legacy cruft. need to fix call_implies_callbacks(). */ 752 call_on_left = 1; 753 call_expr = left; 754 var_expr = right; 755 if (left->type != EXPR_CALL) { 756 call_on_left = 0; 757 call_expr = right; 758 var_expr = left; 759 } 760 761 get_absolute_rl(var_expr, &rl); 762 763 db_info.comparison = comparison; 764 db_info.expr = call_expr; 765 db_info.rl = rl; 766 db_info.left = call_on_left; 767 db_info.callbacks = db_return_states_list; 768 db_info.var_expr = var_expr; 769 770 call_return_states_before_hooks(); 771 772 db_info.true_side = 1; 773 db_info.stree = NULL; 774 db_info.prev_return_id = -1; 775 __push_fake_cur_stree(); 776 sql_select_return_states("return_id, return, type, parameter, key, value", 777 call_expr, db_compare_callback, &db_info); 778 set_other_side_state(&db_info); 779 set_implied_states(&db_info); 780 stree = __pop_fake_cur_stree(); 781 if (!db_info.cull) 782 merge_fake_stree(&db_info.stree, stree); 783 free_stree(&stree); 784 true_states = db_info.stree; 785 if (!true_states && db_info.has_states) { 786 __push_fake_cur_stree(); 787 set_path_impossible(); 788 true_states = __pop_fake_cur_stree(); 789 } 790 791 nullify_path(); 792 __unnullify_path(); 793 FOR_EACH_SM(orig_states, sm) { 794 __set_sm_cur_stree(sm); 795 } END_FOR_EACH_SM(sm); 796 797 db_info.true_side = 0; 798 db_info.stree = NULL; 799 db_info.prev_return_id = -1; 800 db_info.cull = 0; 801 __push_fake_cur_stree(); 802 sql_select_return_states("return_id, return, type, parameter, key, value", call_expr, 803 db_compare_callback, &db_info); 804 set_other_side_state(&db_info); 805 set_implied_states(&db_info); 806 stree = __pop_fake_cur_stree(); 807 if (!db_info.cull) 808 merge_fake_stree(&db_info.stree, stree); 809 free_stree(&stree); 810 false_states = db_info.stree; 811 if (!false_states && db_info.has_states) { 812 __push_fake_cur_stree(); 813 set_path_impossible(); 814 false_states = __pop_fake_cur_stree(); 815 } 816 817 nullify_path(); 818 __unnullify_path(); 819 FOR_EACH_SM(orig_states, sm) { 820 __set_sm_cur_stree(sm); 821 } END_FOR_EACH_SM(sm); 822 823 free_stree(&orig_states); 824 825 FOR_EACH_SM(true_states, sm) { 826 __set_true_false_sm(sm, NULL); 827 } END_FOR_EACH_SM(sm); 828 FOR_EACH_SM(false_states, sm) { 829 __set_true_false_sm(NULL, sm); 830 } END_FOR_EACH_SM(sm); 831 832 free_stree(&true_states); 833 free_stree(&false_states); 834 835 call_return_states_after_hooks(call_expr); 836 837 FOR_EACH_SM(implied_true, sm) { 838 __set_true_false_sm(sm, NULL); 839 } END_FOR_EACH_SM(sm); 840 FOR_EACH_SM(implied_false, sm) { 841 __set_true_false_sm(NULL, sm); 842 } END_FOR_EACH_SM(sm); 843 } 844 845 void function_comparison(struct expression *left, int comparison, struct expression *right) 846 { 847 struct expression *var_expr; 848 struct expression *call_expr; 849 struct stree *implied_true = NULL; 850 struct stree *implied_false = NULL; 851 struct range_list *rl; 852 sval_t sval; 853 int call_on_left; 854 855 if (unreachable()) 856 return; 857 858 /* legacy cruft. need to fix call_implies_callbacks(). */ 859 call_on_left = 1; 860 call_expr = left; 861 var_expr = right; 862 if (left->type != EXPR_CALL) { 863 call_on_left = 0; 864 call_expr = right; 865 var_expr = left; 866 } 867 868 get_absolute_rl(var_expr, &rl); 869 870 if (rl_to_sval(rl, &sval)) 871 call_implies_callbacks(comparison, call_expr, sval, call_on_left, &implied_true, &implied_false); 872 873 compare_db_return_states_callbacks(left, comparison, right, implied_true, implied_false); 874 free_stree(&implied_true); 875 free_stree(&implied_false); 876 } 877 878 static void call_ranged_return_hooks(struct db_callback_info *db_info) 879 { 880 struct call_back_list *call_backs; 881 struct expression *expr; 882 struct fcall_back *tmp; 883 char *fn; 884 885 expr = strip_expr(db_info->expr); 886 while (expr->type == EXPR_ASSIGNMENT) 887 expr = strip_expr(expr->right); 888 if (expr->type != EXPR_CALL || 889 expr->fn->type != EXPR_SYMBOL) 890 return; 891 892 fn = expr->fn->symbol_name->name; 893 894 call_backs = search_callback(func_hash, fn); 895 FOR_EACH_PTR(call_backs, tmp) { 896 struct range_list *range_rl; 897 898 if (tmp->type != RANGED_CALL) 899 continue; 900 range_rl = alloc_rl(tmp->range->min, tmp->range->max); 901 range_rl = cast_rl(estate_type(db_info->ret_state), range_rl); 902 if (possibly_true_rl(range_rl, SPECIAL_EQUAL, estate_rl(db_info->ret_state))) 903 (tmp->u.ranged)(fn, expr, db_info->expr, tmp->info); 904 } END_FOR_EACH_PTR(tmp); 905 } 906 907 static int db_assign_return_states_callback(void *_info, int argc, char **argv, char **azColName) 908 { 909 struct db_callback_info *db_info = _info; 910 struct range_list *ret_range; 911 int type, param; 912 char *ret_str, *key, *value; 913 struct return_implies_callback *tmp; 914 struct stree *stree; 915 int return_id; 916 917 if (argc != 6) 918 return 0; 919 920 return_id = atoi(argv[0]); 921 ret_str = argv[1]; 922 type = atoi(argv[2]); 923 param = atoi(argv[3]); 924 key = argv[4]; 925 value = argv[5]; 926 927 if (db_info->prev_return_id != -1 && type == INTERNAL) { 928 call_ranged_return_hooks(db_info); 929 set_return_assign_state(db_info); 930 set_implied_states(db_info); 931 stree = __pop_fake_cur_stree(); 932 if (!db_info->cull) 933 merge_fake_stree(&db_info->stree, stree); 934 free_stree(&stree); 935 __push_fake_cur_stree(); 936 db_info->cull = 0; 937 } 938 db_info->prev_return_id = return_id; 939 940 if (type == INTERNAL && func_type_mismatch(db_info->expr, value)) 941 db_info->cull = 1; 942 if (db_info->cull) 943 return 0; 944 if (type == CULL_PATH) { 945 db_info->cull = 1; 946 return 0; 947 } 948 if (is_impossible_data(type, db_info->expr, param, key, value)) { 949 db_info->cull = 1; 950 return 0; 951 } 952 953 if (type == PARAM_LIMIT) 954 param_limit_implications(db_info->expr, param, key, value, &db_info->implied); 955 956 db_info->handled = 1; 957 call_results_to_rl(db_info->expr->right, get_type(strip_expr(db_info->expr->right)), ret_str, &ret_range); 958 if (!ret_range) 959 ret_range = alloc_whole_rl(get_type(strip_expr(db_info->expr->right))); 960 ret_range = cast_rl(get_type(db_info->expr->right), ret_range); 961 962 if (type == INTERNAL) { 963 set_state(-1, "unnull_path", NULL, &true_state); 964 __add_return_comparison(strip_expr(db_info->expr->right), ret_str); 965 __add_comparison_info(db_info->expr->left, strip_expr(db_info->expr->right), ret_str); 966 __add_return_to_param_mapping(db_info->expr, ret_str); 967 store_return_state(db_info, ret_str, alloc_estate_rl(ret_range)); 968 set_fresh_mtag_returns(db_info); 969 } 970 971 FOR_EACH_PTR(db_return_states_list, tmp) { 972 if (tmp->type == type) 973 tmp->callback(db_info->expr, param, key, value); 974 } END_FOR_EACH_PTR(tmp); 975 976 return 0; 977 } 978 979 static int db_return_states_assign(struct expression *expr) 980 { 981 struct expression *right; 982 struct sm_state *sm; 983 struct stree *stree; 984 struct db_callback_info db_info = {}; 985 986 right = strip_expr(expr->right); 987 988 db_info.prev_return_id = -1; 989 db_info.expr = expr; 990 db_info.stree = NULL; 991 db_info.handled = 0; 992 993 call_return_states_before_hooks(); 994 995 __push_fake_cur_stree(); 996 sql_select_return_states("return_id, return, type, parameter, key, value", 997 right, db_assign_return_states_callback, &db_info); 998 if (option_debug) { 999 sm_msg("%s return_id %d return_ranges %s", 1000 db_info.cull ? "culled" : "merging", 1001 db_info.prev_return_id, 1002 db_info.ret_state ? db_info.ret_state->name : "'<empty>'"); 1003 } 1004 if (db_info.handled) 1005 call_ranged_return_hooks(&db_info); 1006 set_return_assign_state(&db_info); 1007 set_implied_states(&db_info); 1008 stree = __pop_fake_cur_stree(); 1009 if (!db_info.cull) 1010 merge_fake_stree(&db_info.stree, stree); 1011 free_stree(&stree); 1012 1013 if (!db_info.stree && db_info.cull) { /* this means we culled everything */ 1014 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left))); 1015 set_path_impossible(); 1016 } 1017 FOR_EACH_SM(db_info.stree, sm) { 1018 __set_sm(sm); 1019 } END_FOR_EACH_SM(sm); 1020 1021 free_stree(&db_info.stree); 1022 call_return_states_after_hooks(right); 1023 1024 return db_info.handled; 1025 } 1026 1027 static int handle_implied_return(struct expression *expr) 1028 { 1029 struct range_list *rl; 1030 1031 if (!get_implied_return(expr->right, &rl)) 1032 return 0; 1033 rl = cast_rl(get_type(expr->left), rl); 1034 set_extra_expr_mod(expr->left, alloc_estate_rl(rl)); 1035 return 1; 1036 } 1037 1038 static void match_assign_call(struct expression *expr) 1039 { 1040 struct call_back_list *call_backs; 1041 const char *fn; 1042 struct expression *right; 1043 int handled = 0; 1044 struct range_list *rl; 1045 1046 if (expr->op != '=') 1047 return; 1048 1049 right = strip_expr(expr->right); 1050 if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol) { 1051 handled |= db_return_states_assign(expr); 1052 if (!handled) 1053 goto assigned_unknown; 1054 return; 1055 } 1056 if (is_fake_call(right)) { 1057 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left))); 1058 return; 1059 } 1060 1061 fn = right->fn->symbol->ident->name; 1062 call_backs = search_callback(func_hash, (char *)fn); 1063 1064 /* 1065 * The ordering here is sort of important. 1066 * One example, of how this matters is that when we do: 1067 * 1068 * len = strlen(str); 1069 * 1070 * That is handled by smatch_common_functions.c and smatch_strlen.c. 1071 * They use implied_return and function_assign_hook respectively. 1072 * We want to get the implied return first before we do the function 1073 * assignment hook otherwise we end up writing the wrong thing for len 1074 * in smatch_extra.c because we assume that it already holds the 1075 * strlen() when we haven't set it yet. 1076 */ 1077 1078 if (db_return_states_assign(expr) == 1) 1079 handled = 1; 1080 else 1081 handled = assign_ranged_funcs(fn, expr, call_backs); 1082 handled |= handle_implied_return(expr); 1083 1084 1085 call_call_backs(call_backs, ASSIGN_CALL, fn, expr); 1086 1087 if (handled) 1088 return; 1089 1090 assigned_unknown: 1091 get_absolute_rl(expr->right, &rl); 1092 rl = cast_rl(get_type(expr->left), rl); 1093 set_extra_expr_mod(expr->left, alloc_estate_rl(rl)); 1094 } 1095 1096 static int db_return_states_callback(void *_info, int argc, char **argv, char **azColName) 1097 { 1098 struct db_callback_info *db_info = _info; 1099 struct range_list *ret_range; 1100 int type, param; 1101 char *ret_str, *key, *value; 1102 struct return_implies_callback *tmp; 1103 struct stree *stree; 1104 int return_id; 1105 char buf[64]; 1106 1107 if (argc != 6) 1108 return 0; 1109 1110 return_id = atoi(argv[0]); 1111 ret_str = argv[1]; 1112 type = atoi(argv[2]); 1113 param = atoi(argv[3]); 1114 key = argv[4]; 1115 value = argv[5]; 1116 1117 if (db_info->prev_return_id != -1 && type == INTERNAL) { 1118 call_ranged_return_hooks(db_info); 1119 set_implied_states(db_info); 1120 stree = __pop_fake_cur_stree(); 1121 if (!db_info->cull) 1122 merge_fake_stree(&db_info->stree, stree); 1123 free_stree(&stree); 1124 __push_fake_cur_stree(); 1125 __unnullify_path(); 1126 db_info->cull = 0; 1127 } 1128 db_info->prev_return_id = return_id; 1129 1130 if (type == INTERNAL && func_type_mismatch(db_info->expr, value)) 1131 db_info->cull = 1; 1132 if (db_info->cull) 1133 return 0; 1134 if (type == CULL_PATH) { 1135 db_info->cull = 1; 1136 return 0; 1137 } 1138 if (is_impossible_data(type, db_info->expr, param, key, value)) { 1139 db_info->cull = 1; 1140 return 0; 1141 } 1142 1143 if (type == PARAM_LIMIT) 1144 param_limit_implications(db_info->expr, param, key, value, &db_info->implied); 1145 1146 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range); 1147 ret_range = cast_rl(get_type(db_info->expr), ret_range); 1148 1149 if (type == INTERNAL) { 1150 struct smatch_state *state; 1151 1152 set_state(-1, "unnull_path", NULL, &true_state); 1153 __add_return_comparison(strip_expr(db_info->expr), ret_str); 1154 __add_return_to_param_mapping(db_info->expr, ret_str); 1155 /* 1156 * We want to store the return values so that we can split the strees 1157 * in smatch_db.c. This uses set_state() directly because it's not a 1158 * real smatch_extra state. 1159 */ 1160 snprintf(buf, sizeof(buf), "return %p", db_info->expr); 1161 state = alloc_estate_rl(ret_range); 1162 set_state(SMATCH_EXTRA, buf, NULL, state); 1163 store_return_state(db_info, ret_str, state); 1164 } 1165 1166 FOR_EACH_PTR(db_return_states_list, tmp) { 1167 if (tmp->type == type) 1168 tmp->callback(db_info->expr, param, key, value); 1169 } END_FOR_EACH_PTR(tmp); 1170 1171 1172 return 0; 1173 } 1174 1175 static void db_return_states(struct expression *expr) 1176 { 1177 struct sm_state *sm; 1178 struct stree *stree; 1179 struct db_callback_info db_info = {}; 1180 1181 if (!__get_cur_stree()) /* no return functions */ 1182 return; 1183 1184 db_info.prev_return_id = -1; 1185 db_info.expr = expr; 1186 db_info.stree = NULL; 1187 1188 call_return_states_before_hooks(); 1189 1190 __push_fake_cur_stree(); 1191 __unnullify_path(); 1192 sql_select_return_states("return_id, return, type, parameter, key, value", 1193 expr, db_return_states_callback, &db_info); 1194 call_ranged_return_hooks(&db_info); 1195 set_implied_states(&db_info); 1196 stree = __pop_fake_cur_stree(); 1197 if (!db_info.cull) 1198 merge_fake_stree(&db_info.stree, stree); 1199 free_stree(&stree); 1200 1201 FOR_EACH_SM(db_info.stree, sm) { 1202 __set_sm(sm); 1203 } END_FOR_EACH_SM(sm); 1204 1205 free_stree(&db_info.stree); 1206 call_return_states_after_hooks(expr); 1207 } 1208 1209 static int is_condition_call(struct expression *expr) 1210 { 1211 struct expression *tmp; 1212 1213 FOR_EACH_PTR_REVERSE(big_condition_stack, tmp) { 1214 if (expr == tmp || expr_get_parent_expr(expr) == tmp) 1215 return 1; 1216 if (tmp->pos.line < expr->pos.line) 1217 return 0; 1218 } END_FOR_EACH_PTR_REVERSE(tmp); 1219 1220 return 0; 1221 } 1222 1223 static void db_return_states_call(struct expression *expr) 1224 { 1225 if (unreachable()) 1226 return; 1227 1228 if (is_assigned_call(expr)) 1229 return; 1230 if (is_condition_call(expr)) 1231 return; 1232 db_return_states(expr); 1233 } 1234 1235 static void match_function_call(struct expression *expr) 1236 { 1237 struct call_back_list *call_backs; 1238 struct expression *fn; 1239 1240 fn = strip_expr(expr->fn); 1241 if (fn->type == EXPR_SYMBOL && fn->symbol) { 1242 call_backs = search_callback(func_hash, (char *)fn->symbol->ident->name); 1243 if (call_backs) 1244 call_call_backs(call_backs, REGULAR_CALL, 1245 fn->symbol->ident->name, expr); 1246 } 1247 db_return_states_call(expr); 1248 } 1249 1250 static void match_macro_assign(struct expression *expr) 1251 { 1252 struct call_back_list *call_backs; 1253 const char *macro; 1254 struct expression *right; 1255 1256 right = strip_expr(expr->right); 1257 macro = get_macro_name(right->pos); 1258 call_backs = search_callback(func_hash, (char *)macro); 1259 if (!call_backs) 1260 return; 1261 call_call_backs(call_backs, MACRO_ASSIGN, macro, expr); 1262 call_call_backs(call_backs, MACRO_ASSIGN_EXTRA, macro, expr); 1263 } 1264 1265 int get_implied_return(struct expression *expr, struct range_list **rl) 1266 { 1267 struct call_back_list *call_backs; 1268 struct fcall_back *tmp; 1269 int handled = 0; 1270 char *fn; 1271 1272 *rl = NULL; 1273 1274 expr = strip_expr(expr); 1275 fn = expr_to_var(expr->fn); 1276 if (!fn) 1277 goto out; 1278 1279 call_backs = search_callback(func_hash, fn); 1280 1281 FOR_EACH_PTR(call_backs, tmp) { 1282 if (tmp->type == IMPLIED_RETURN) { 1283 (tmp->u.implied_return)(expr, tmp->info, rl); 1284 handled = 1; 1285 } 1286 } END_FOR_EACH_PTR(tmp); 1287 1288 out: 1289 free_string(fn); 1290 return handled; 1291 } 1292 1293 void create_function_hook_hash(void) 1294 { 1295 func_hash = create_function_hashtable(5000); 1296 } 1297 1298 void register_function_hooks(int id) 1299 { 1300 add_hook(&match_function_call, CALL_HOOK_AFTER_INLINE); 1301 add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK); 1302 add_hook(&match_macro_assign, MACRO_ASSIGNMENT_HOOK); 1303 } 1304