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 db_implies_list *callbacks; 361 int prev_return_id; 362 int cull; 363 int has_states; 364 char *ret_str; 365 struct smatch_state *ret_state; 366 struct expression *var_expr; 367 int handled; 368 }; 369 370 static void store_return_state(struct db_callback_info *db_info, const char *ret_str, struct smatch_state *state) 371 { 372 db_info->ret_str = alloc_sname(ret_str), 373 db_info->ret_state = state; 374 } 375 376 static bool fake_a_param_assignment(struct expression *expr, const char *return_str) 377 { 378 struct expression *arg, *left, *right, *tmp, *fake_assign; 379 char *p; 380 int param; 381 char buf[256]; 382 char *str; 383 384 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=') 385 return false; 386 left = expr->left; 387 right = expr->right; 388 389 while (right->type == EXPR_ASSIGNMENT) 390 right = strip_expr(right->right); 391 if (!right || right->type != EXPR_CALL) 392 return false; 393 394 p = strchr(return_str, '['); 395 if (!p) 396 return false; 397 398 p++; 399 if (p[0] == '=' && p[1] == '=') 400 p += 2; 401 if (p[0] != '$') 402 return false; 403 404 snprintf(buf, sizeof(buf), "%s", p); 405 406 p = buf; 407 p += 1; 408 param = strtol(p, &p, 10); 409 410 p = strchr(p, ']'); 411 if (!p || *p != ']') 412 return false; 413 *p = '\0'; 414 415 arg = get_argument_from_call_expr(right->args, param); 416 if (!arg) 417 return false; 418 419 /* There should be a get_other_name() function which returns an expr */ 420 tmp = get_assigned_expr(arg); 421 if (tmp) 422 arg = tmp; 423 424 /* 425 * This is a sanity check to prevent side effects from evaluating stuff 426 * twice. 427 */ 428 str = expr_to_chunk_sym_vsl(arg, NULL, NULL); 429 if (!str) 430 return false; 431 free_string(str); 432 433 right = gen_expression_from_key(arg, buf); 434 if (!right) /* Mostly fails for binops like [$0 + 4032] */ 435 return false; 436 fake_assign = assign_expression(left, '=', right); 437 __in_fake_parameter_assign++; 438 __split_expr(fake_assign); 439 __in_fake_parameter_assign--; 440 return true; 441 } 442 443 static void set_return_assign_state(struct db_callback_info *db_info) 444 { 445 struct expression *expr = db_info->expr->left; 446 struct smatch_state *state; 447 448 if (!db_info->ret_state) 449 return; 450 451 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state)))); 452 set_extra_expr_mod(expr, state); 453 db_info->ret_state = NULL; 454 fake_a_param_assignment(db_info->expr, db_info->ret_str); 455 db_info->ret_str = NULL; 456 } 457 458 static void set_other_side_state(struct db_callback_info *db_info) 459 { 460 struct expression *expr = db_info->var_expr; 461 struct smatch_state *state; 462 463 if (!db_info->ret_state) 464 return; 465 466 state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state)))); 467 set_extra_expr_nomod(expr, state); 468 db_info->ret_state = NULL; 469 db_info->ret_str = NULL; 470 } 471 472 static void handle_ret_equals_param(char *ret_string, struct range_list *rl, struct expression *call) 473 { 474 char *str; 475 long long param; 476 struct expression *arg; 477 struct range_list *orig; 478 479 str = strstr(ret_string, "==$"); 480 if (!str) 481 return; 482 str += 3; 483 param = strtoll(str, NULL, 10); 484 arg = get_argument_from_call_expr(call->args, param); 485 if (!arg) 486 return; 487 get_absolute_rl(arg, &orig); 488 rl = rl_intersection(orig, rl); 489 if (!rl) 490 return; 491 set_extra_expr_nomod(arg, alloc_estate_rl(rl)); 492 } 493 494 static int impossible_limit(struct expression *expr, int param, char *key, char *value) 495 { 496 struct expression *arg; 497 struct smatch_state *state; 498 struct range_list *passed; 499 struct range_list *limit; 500 struct symbol *compare_type; 501 502 while (expr->type == EXPR_ASSIGNMENT) 503 expr = strip_expr(expr->right); 504 if (expr->type != EXPR_CALL) 505 return 0; 506 507 arg = get_argument_from_call_expr(expr->args, param); 508 if (!arg) 509 return 0; 510 511 if (strcmp(key, "$") == 0) { 512 if (!get_implied_rl(arg, &passed)) 513 return 0; 514 515 compare_type = get_arg_type(expr->fn, param); 516 } else { 517 char *name; 518 struct symbol *sym; 519 520 name = get_variable_from_key(arg, key, &sym); 521 if (!name || !sym) 522 return 0; 523 524 state = get_state(SMATCH_EXTRA, name, sym); 525 if (!state) { 526 free_string(name); 527 return 0; 528 } 529 passed = estate_rl(state); 530 if (!passed || is_whole_rl(passed)) { 531 free_string(name); 532 return 0; 533 } 534 535 compare_type = get_member_type_from_key(arg, key); 536 } 537 538 passed = cast_rl(compare_type, passed); 539 call_results_to_rl(expr, compare_type, value, &limit); 540 if (!limit || is_whole_rl(limit)) 541 return 0; 542 if (possibly_true_rl(passed, SPECIAL_EQUAL, limit)) 543 return 0; 544 if (option_debug || local_debug) 545 sm_msg("impossible: %d '%s' limit '%s' == '%s'", param, key, show_rl(passed), value); 546 return 1; 547 } 548 549 static int is_impossible_data(int type, struct expression *expr, int param, char *key, char *value) 550 { 551 if (type == PARAM_LIMIT && impossible_limit(expr, param, key, value)) 552 return 1; 553 if (type == COMPARE_LIMIT && param_compare_limit_is_impossible(expr, param, key, value)) { 554 if (local_debug) 555 sm_msg("param_compare_limit_is_impossible: %d %s %s", param, key, value); 556 return 1; 557 } 558 return 0; 559 } 560 561 static int func_type_mismatch(struct expression *expr, const char *value) 562 { 563 struct symbol *type; 564 565 /* This makes faking returns easier */ 566 if (!value || value[0] == '\0') 567 return 0; 568 569 while (expr->type == EXPR_ASSIGNMENT) 570 expr = strip_expr(expr->right); 571 572 /* 573 * Short cut: We only care about function pointers that are struct 574 * members. 575 * 576 */ 577 if (expr->fn->type == EXPR_SYMBOL) 578 return 0; 579 580 type = get_type(expr->fn); 581 if (!type) 582 return 0; 583 if (type->type == SYM_PTR) 584 type = get_real_base_type(type); 585 586 if (strcmp(type_to_str(type), value) == 0) 587 return 0; 588 589 return 1; 590 } 591 592 static int db_compare_callback(void *_info, int argc, char **argv, char **azColName) 593 { 594 struct db_callback_info *db_info = _info; 595 struct range_list *var_rl = db_info->rl; 596 struct range_list *ret_range; 597 int type, param; 598 char *ret_str, *key, *value; 599 struct return_implies_callback *tmp; 600 struct stree *stree; 601 int return_id; 602 int comparison; 603 604 if (argc != 6) 605 return 0; 606 607 return_id = atoi(argv[0]); 608 ret_str = argv[1]; 609 type = atoi(argv[2]); 610 param = atoi(argv[3]); 611 key = argv[4]; 612 value = argv[5]; 613 614 db_info->has_states = 1; 615 if (db_info->prev_return_id != -1 && type == INTERNAL) { 616 set_other_side_state(db_info); 617 stree = __pop_fake_cur_stree(); 618 619 if (!db_info->cull) 620 merge_fake_stree(&db_info->stree, stree); 621 free_stree(&stree); 622 __push_fake_cur_stree(); 623 db_info->cull = 0; 624 } 625 db_info->prev_return_id = return_id; 626 627 if (type == INTERNAL && func_type_mismatch(db_info->expr, value)) 628 db_info->cull = 1; 629 if (db_info->cull) 630 return 0; 631 if (type == CULL_PATH) { 632 db_info->cull = 1; 633 return 0; 634 } 635 636 if (is_impossible_data(type, db_info->expr, param, key, value)) { 637 db_info->cull = 1; 638 return 0; 639 } 640 641 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range); 642 ret_range = cast_rl(get_type(db_info->expr), ret_range); 643 if (!ret_range) 644 ret_range = alloc_whole_rl(get_type(db_info->expr)); 645 646 comparison = db_info->comparison; 647 if (db_info->left) 648 comparison = flip_comparison(comparison); 649 650 if (db_info->true_side) { 651 if (!possibly_true_rl(var_rl, comparison, ret_range)) 652 return 0; 653 if (type == PARAM_LIMIT) 654 param_limit_implications(db_info->expr, param, key, value); 655 filter_by_comparison(&var_rl, comparison, ret_range); 656 filter_by_comparison(&ret_range, flip_comparison(comparison), var_rl); 657 } else { 658 if (!possibly_false_rl(var_rl, comparison, ret_range)) 659 return 0; 660 if (type == PARAM_LIMIT) 661 param_limit_implications(db_info->expr, param, key, value); 662 filter_by_comparison(&var_rl, negate_comparison(comparison), ret_range); 663 filter_by_comparison(&ret_range, flip_comparison(negate_comparison(comparison)), var_rl); 664 } 665 666 handle_ret_equals_param(ret_str, ret_range, db_info->expr); 667 668 if (type == INTERNAL) { 669 set_state(-1, "unnull_path", NULL, &true_state); 670 __add_return_comparison(strip_expr(db_info->expr), ret_str); 671 __add_return_to_param_mapping(db_info->expr, ret_str); 672 store_return_state(db_info, ret_str, alloc_estate_rl(clone_rl(var_rl))); 673 } 674 675 FOR_EACH_PTR(db_info->callbacks, tmp) { 676 if (tmp->type == type) 677 tmp->callback(db_info->expr, param, key, value); 678 } END_FOR_EACH_PTR(tmp); 679 680 return 0; 681 } 682 683 static void compare_db_return_states_callbacks(struct expression *left, int comparison, struct expression *right, struct stree *implied_true, struct stree *implied_false) 684 { 685 struct stree *orig_states; 686 struct stree *stree; 687 struct stree *true_states; 688 struct stree *false_states; 689 struct sm_state *sm; 690 struct db_callback_info db_info = {}; 691 struct expression *var_expr; 692 struct expression *call_expr; 693 struct range_list *rl; 694 int call_on_left; 695 696 orig_states = clone_stree(__get_cur_stree()); 697 698 /* legacy cruft. need to fix call_implies_callbacks(). */ 699 call_on_left = 1; 700 call_expr = left; 701 var_expr = right; 702 if (left->type != EXPR_CALL) { 703 call_on_left = 0; 704 call_expr = right; 705 var_expr = left; 706 } 707 708 get_absolute_rl(var_expr, &rl); 709 710 db_info.comparison = comparison; 711 db_info.expr = call_expr; 712 db_info.rl = rl; 713 db_info.left = call_on_left; 714 db_info.callbacks = db_return_states_list; 715 db_info.var_expr = var_expr; 716 717 call_return_states_before_hooks(); 718 719 db_info.true_side = 1; 720 db_info.stree = NULL; 721 db_info.prev_return_id = -1; 722 __push_fake_cur_stree(); 723 sql_select_return_states("return_id, return, type, parameter, key, value", 724 call_expr, db_compare_callback, &db_info); 725 set_other_side_state(&db_info); 726 stree = __pop_fake_cur_stree(); 727 if (!db_info.cull) 728 merge_fake_stree(&db_info.stree, stree); 729 free_stree(&stree); 730 true_states = db_info.stree; 731 if (!true_states && db_info.has_states) { 732 __push_fake_cur_stree(); 733 set_path_impossible(); 734 true_states = __pop_fake_cur_stree(); 735 } 736 737 nullify_path(); 738 __unnullify_path(); 739 FOR_EACH_SM(orig_states, sm) { 740 __set_sm_cur_stree(sm); 741 } END_FOR_EACH_SM(sm); 742 743 db_info.true_side = 0; 744 db_info.stree = NULL; 745 db_info.prev_return_id = -1; 746 db_info.cull = 0; 747 __push_fake_cur_stree(); 748 sql_select_return_states("return_id, return, type, parameter, key, value", call_expr, 749 db_compare_callback, &db_info); 750 set_other_side_state(&db_info); 751 stree = __pop_fake_cur_stree(); 752 if (!db_info.cull) 753 merge_fake_stree(&db_info.stree, stree); 754 free_stree(&stree); 755 false_states = db_info.stree; 756 if (!false_states && db_info.has_states) { 757 __push_fake_cur_stree(); 758 set_path_impossible(); 759 false_states = __pop_fake_cur_stree(); 760 } 761 762 nullify_path(); 763 __unnullify_path(); 764 FOR_EACH_SM(orig_states, sm) { 765 __set_sm_cur_stree(sm); 766 } END_FOR_EACH_SM(sm); 767 768 free_stree(&orig_states); 769 770 FOR_EACH_SM(true_states, sm) { 771 __set_true_false_sm(sm, NULL); 772 } END_FOR_EACH_SM(sm); 773 FOR_EACH_SM(false_states, sm) { 774 __set_true_false_sm(NULL, sm); 775 } END_FOR_EACH_SM(sm); 776 777 free_stree(&true_states); 778 free_stree(&false_states); 779 780 call_return_states_after_hooks(call_expr); 781 782 FOR_EACH_SM(implied_true, sm) { 783 __set_true_false_sm(sm, NULL); 784 } END_FOR_EACH_SM(sm); 785 FOR_EACH_SM(implied_false, sm) { 786 __set_true_false_sm(NULL, sm); 787 } END_FOR_EACH_SM(sm); 788 } 789 790 void function_comparison(struct expression *left, int comparison, struct expression *right) 791 { 792 struct expression *var_expr; 793 struct expression *call_expr; 794 struct stree *implied_true = NULL; 795 struct stree *implied_false = NULL; 796 struct range_list *rl; 797 sval_t sval; 798 int call_on_left; 799 800 if (unreachable()) 801 return; 802 803 /* legacy cruft. need to fix call_implies_callbacks(). */ 804 call_on_left = 1; 805 call_expr = left; 806 var_expr = right; 807 if (left->type != EXPR_CALL) { 808 call_on_left = 0; 809 call_expr = right; 810 var_expr = left; 811 } 812 813 get_absolute_rl(var_expr, &rl); 814 815 if (rl_to_sval(rl, &sval)) 816 call_implies_callbacks(comparison, call_expr, sval, call_on_left, &implied_true, &implied_false); 817 818 compare_db_return_states_callbacks(left, comparison, right, implied_true, implied_false); 819 free_stree(&implied_true); 820 free_stree(&implied_false); 821 } 822 823 static void call_ranged_return_hooks(struct db_callback_info *db_info) 824 { 825 struct call_back_list *call_backs; 826 struct expression *expr; 827 struct fcall_back *tmp; 828 char *fn; 829 830 expr = strip_expr(db_info->expr); 831 while (expr->type == EXPR_ASSIGNMENT) 832 expr = strip_expr(expr->right); 833 if (expr->type != EXPR_CALL || 834 expr->fn->type != EXPR_SYMBOL) 835 return; 836 837 fn = expr->fn->symbol_name->name; 838 839 call_backs = search_callback(func_hash, fn); 840 FOR_EACH_PTR(call_backs, tmp) { 841 struct range_list *range_rl; 842 843 if (tmp->type != RANGED_CALL) 844 continue; 845 range_rl = alloc_rl(tmp->range->min, tmp->range->max); 846 range_rl = cast_rl(estate_type(db_info->ret_state), range_rl); 847 if (possibly_true_rl(range_rl, SPECIAL_EQUAL, estate_rl(db_info->ret_state))) 848 (tmp->u.ranged)(fn, expr, db_info->expr, tmp->info); 849 } END_FOR_EACH_PTR(tmp); 850 } 851 852 static int db_assign_return_states_callback(void *_info, int argc, char **argv, char **azColName) 853 { 854 struct db_callback_info *db_info = _info; 855 struct range_list *ret_range; 856 int type, param; 857 char *ret_str, *key, *value; 858 struct return_implies_callback *tmp; 859 struct stree *stree; 860 int return_id; 861 862 if (argc != 6) 863 return 0; 864 865 return_id = atoi(argv[0]); 866 ret_str = argv[1]; 867 type = atoi(argv[2]); 868 param = atoi(argv[3]); 869 key = argv[4]; 870 value = argv[5]; 871 872 if (db_info->prev_return_id != -1 && type == INTERNAL) { 873 call_ranged_return_hooks(db_info); 874 set_return_assign_state(db_info); 875 stree = __pop_fake_cur_stree(); 876 if (!db_info->cull) 877 merge_fake_stree(&db_info->stree, stree); 878 free_stree(&stree); 879 __push_fake_cur_stree(); 880 db_info->cull = 0; 881 } 882 db_info->prev_return_id = return_id; 883 884 if (type == INTERNAL && func_type_mismatch(db_info->expr, value)) 885 db_info->cull = 1; 886 if (db_info->cull) 887 return 0; 888 if (type == CULL_PATH) { 889 db_info->cull = 1; 890 return 0; 891 } 892 if (is_impossible_data(type, db_info->expr, param, key, value)) { 893 db_info->cull = 1; 894 return 0; 895 } 896 897 if (type == PARAM_LIMIT) 898 param_limit_implications(db_info->expr, param, key, value); 899 900 db_info->handled = 1; 901 call_results_to_rl(db_info->expr->right, get_type(strip_expr(db_info->expr->right)), ret_str, &ret_range); 902 if (!ret_range) 903 ret_range = alloc_whole_rl(get_type(strip_expr(db_info->expr->right))); 904 ret_range = cast_rl(get_type(db_info->expr->right), ret_range); 905 906 if (type == INTERNAL) { 907 set_state(-1, "unnull_path", NULL, &true_state); 908 __add_return_comparison(strip_expr(db_info->expr->right), ret_str); 909 __add_comparison_info(db_info->expr->left, strip_expr(db_info->expr->right), ret_str); 910 __add_return_to_param_mapping(db_info->expr, ret_str); 911 store_return_state(db_info, ret_str, alloc_estate_rl(ret_range)); 912 } 913 914 FOR_EACH_PTR(db_return_states_list, tmp) { 915 if (tmp->type == type) 916 tmp->callback(db_info->expr, param, key, value); 917 } END_FOR_EACH_PTR(tmp); 918 919 return 0; 920 } 921 922 static int db_return_states_assign(struct expression *expr) 923 { 924 struct expression *right; 925 struct sm_state *sm; 926 struct stree *stree; 927 struct db_callback_info db_info = {}; 928 929 right = strip_expr(expr->right); 930 931 db_info.prev_return_id = -1; 932 db_info.expr = expr; 933 db_info.stree = NULL; 934 db_info.handled = 0; 935 936 call_return_states_before_hooks(); 937 938 __push_fake_cur_stree(); 939 sql_select_return_states("return_id, return, type, parameter, key, value", 940 right, db_assign_return_states_callback, &db_info); 941 if (option_debug) { 942 sm_msg("%s return_id %d return_ranges %s", 943 db_info.cull ? "culled" : "merging", 944 db_info.prev_return_id, 945 db_info.ret_state ? db_info.ret_state->name : "'<empty>'"); 946 } 947 if (db_info.handled) 948 call_ranged_return_hooks(&db_info); 949 set_return_assign_state(&db_info); 950 stree = __pop_fake_cur_stree(); 951 if (!db_info.cull) 952 merge_fake_stree(&db_info.stree, stree); 953 free_stree(&stree); 954 955 if (!db_info.stree && db_info.cull) { /* this means we culled everything */ 956 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left))); 957 set_path_impossible(); 958 } 959 FOR_EACH_SM(db_info.stree, sm) { 960 __set_sm(sm); 961 } END_FOR_EACH_SM(sm); 962 963 free_stree(&db_info.stree); 964 call_return_states_after_hooks(right); 965 966 return db_info.handled; 967 } 968 969 static int handle_implied_return(struct expression *expr) 970 { 971 struct range_list *rl; 972 973 if (!get_implied_return(expr->right, &rl)) 974 return 0; 975 rl = cast_rl(get_type(expr->left), rl); 976 set_extra_expr_mod(expr->left, alloc_estate_rl(rl)); 977 return 1; 978 } 979 980 static void match_assign_call(struct expression *expr) 981 { 982 struct call_back_list *call_backs; 983 const char *fn; 984 struct expression *right; 985 int handled = 0; 986 struct range_list *rl; 987 988 if (expr->op != '=') 989 return; 990 991 right = strip_expr(expr->right); 992 if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol) { 993 handled |= db_return_states_assign(expr); 994 if (!handled) 995 goto assigned_unknown; 996 return; 997 } 998 if (is_fake_call(right)) { 999 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left))); 1000 return; 1001 } 1002 1003 fn = right->fn->symbol->ident->name; 1004 call_backs = search_callback(func_hash, (char *)fn); 1005 1006 /* 1007 * The ordering here is sort of important. 1008 * One example, of how this matters is that when we do: 1009 * 1010 * len = strlen(str); 1011 * 1012 * That is handled by smatch_common_functions.c and smatch_strlen.c. 1013 * They use implied_return and function_assign_hook respectively. 1014 * We want to get the implied return first before we do the function 1015 * assignment hook otherwise we end up writing the wrong thing for len 1016 * in smatch_extra.c because we assume that it already holds the 1017 * strlen() when we haven't set it yet. 1018 */ 1019 1020 if (db_return_states_assign(expr) == 1) 1021 handled = 1; 1022 else 1023 handled = assign_ranged_funcs(fn, expr, call_backs); 1024 handled |= handle_implied_return(expr); 1025 1026 1027 call_call_backs(call_backs, ASSIGN_CALL, fn, expr); 1028 1029 if (handled) 1030 return; 1031 1032 assigned_unknown: 1033 get_absolute_rl(expr->right, &rl); 1034 rl = cast_rl(get_type(expr->left), rl); 1035 set_extra_expr_mod(expr->left, alloc_estate_rl(rl)); 1036 } 1037 1038 static int db_return_states_callback(void *_info, int argc, char **argv, char **azColName) 1039 { 1040 struct db_callback_info *db_info = _info; 1041 struct range_list *ret_range; 1042 int type, param; 1043 char *ret_str, *key, *value; 1044 struct return_implies_callback *tmp; 1045 struct stree *stree; 1046 int return_id; 1047 char buf[64]; 1048 1049 if (argc != 6) 1050 return 0; 1051 1052 return_id = atoi(argv[0]); 1053 ret_str = argv[1]; 1054 type = atoi(argv[2]); 1055 param = atoi(argv[3]); 1056 key = argv[4]; 1057 value = argv[5]; 1058 1059 if (db_info->prev_return_id != -1 && type == INTERNAL) { 1060 stree = __pop_fake_cur_stree(); 1061 if (!db_info->cull) 1062 merge_fake_stree(&db_info->stree, stree); 1063 free_stree(&stree); 1064 __push_fake_cur_stree(); 1065 __unnullify_path(); 1066 db_info->cull = 0; 1067 } 1068 db_info->prev_return_id = return_id; 1069 1070 if (type == INTERNAL && func_type_mismatch(db_info->expr, value)) 1071 db_info->cull = 1; 1072 if (db_info->cull) 1073 return 0; 1074 if (type == CULL_PATH) { 1075 db_info->cull = 1; 1076 return 0; 1077 } 1078 if (is_impossible_data(type, db_info->expr, param, key, value)) { 1079 db_info->cull = 1; 1080 return 0; 1081 } 1082 1083 if (type == PARAM_LIMIT) 1084 param_limit_implications(db_info->expr, param, key, value); 1085 1086 call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), ret_str, &ret_range); 1087 ret_range = cast_rl(get_type(db_info->expr), ret_range); 1088 1089 if (type == INTERNAL) { 1090 set_state(-1, "unnull_path", NULL, &true_state); 1091 __add_return_comparison(strip_expr(db_info->expr), ret_str); 1092 __add_return_to_param_mapping(db_info->expr, ret_str); 1093 } 1094 1095 1096 FOR_EACH_PTR(db_return_states_list, tmp) { 1097 if (tmp->type == type) 1098 tmp->callback(db_info->expr, param, key, value); 1099 } END_FOR_EACH_PTR(tmp); 1100 1101 /* 1102 * We want to store the return values so that we can split the strees 1103 * in smatch_db.c. This uses set_state() directly because it's not a 1104 * real smatch_extra state. 1105 */ 1106 snprintf(buf, sizeof(buf), "return %p", db_info->expr); 1107 set_state(SMATCH_EXTRA, buf, NULL, alloc_estate_rl(ret_range)); 1108 1109 return 0; 1110 } 1111 1112 static void db_return_states(struct expression *expr) 1113 { 1114 struct sm_state *sm; 1115 struct stree *stree; 1116 struct db_callback_info db_info = {}; 1117 1118 if (!__get_cur_stree()) /* no return functions */ 1119 return; 1120 1121 db_info.prev_return_id = -1; 1122 db_info.expr = expr; 1123 db_info.stree = NULL; 1124 1125 call_return_states_before_hooks(); 1126 1127 __push_fake_cur_stree(); 1128 __unnullify_path(); 1129 sql_select_return_states("return_id, return, type, parameter, key, value", 1130 expr, db_return_states_callback, &db_info); 1131 stree = __pop_fake_cur_stree(); 1132 if (!db_info.cull) 1133 merge_fake_stree(&db_info.stree, stree); 1134 free_stree(&stree); 1135 1136 FOR_EACH_SM(db_info.stree, sm) { 1137 __set_sm(sm); 1138 } END_FOR_EACH_SM(sm); 1139 1140 free_stree(&db_info.stree); 1141 call_return_states_after_hooks(expr); 1142 } 1143 1144 static int is_condition_call(struct expression *expr) 1145 { 1146 struct expression *tmp; 1147 1148 FOR_EACH_PTR_REVERSE(big_condition_stack, tmp) { 1149 if (expr == tmp || expr_get_parent_expr(expr) == tmp) 1150 return 1; 1151 if (tmp->pos.line < expr->pos.line) 1152 return 0; 1153 } END_FOR_EACH_PTR_REVERSE(tmp); 1154 1155 return 0; 1156 } 1157 1158 static void db_return_states_call(struct expression *expr) 1159 { 1160 if (unreachable()) 1161 return; 1162 1163 if (is_assigned_call(expr)) 1164 return; 1165 if (is_condition_call(expr)) 1166 return; 1167 db_return_states(expr); 1168 } 1169 1170 static void match_function_call(struct expression *expr) 1171 { 1172 struct call_back_list *call_backs; 1173 1174 if (expr->fn->type == EXPR_SYMBOL && expr->fn->symbol) { 1175 call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name); 1176 if (call_backs) 1177 call_call_backs(call_backs, REGULAR_CALL, 1178 expr->fn->symbol->ident->name, expr); 1179 } 1180 db_return_states_call(expr); 1181 } 1182 1183 static void match_macro_assign(struct expression *expr) 1184 { 1185 struct call_back_list *call_backs; 1186 const char *macro; 1187 struct expression *right; 1188 1189 right = strip_expr(expr->right); 1190 macro = get_macro_name(right->pos); 1191 call_backs = search_callback(func_hash, (char *)macro); 1192 if (!call_backs) 1193 return; 1194 call_call_backs(call_backs, MACRO_ASSIGN, macro, expr); 1195 call_call_backs(call_backs, MACRO_ASSIGN_EXTRA, macro, expr); 1196 } 1197 1198 int get_implied_return(struct expression *expr, struct range_list **rl) 1199 { 1200 struct call_back_list *call_backs; 1201 struct fcall_back *tmp; 1202 int handled = 0; 1203 char *fn; 1204 1205 *rl = NULL; 1206 1207 expr = strip_expr(expr); 1208 fn = expr_to_var(expr->fn); 1209 if (!fn) 1210 goto out; 1211 1212 call_backs = search_callback(func_hash, fn); 1213 1214 FOR_EACH_PTR(call_backs, tmp) { 1215 if (tmp->type == IMPLIED_RETURN) { 1216 (tmp->u.implied_return)(expr, tmp->info, rl); 1217 handled = 1; 1218 } 1219 } END_FOR_EACH_PTR(tmp); 1220 1221 out: 1222 free_string(fn); 1223 return handled; 1224 } 1225 1226 void create_function_hook_hash(void) 1227 { 1228 func_hash = create_function_hashtable(5000); 1229 } 1230 1231 void register_function_hooks(int id) 1232 { 1233 add_hook(&match_function_call, CALL_HOOK_AFTER_INLINE); 1234 add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK); 1235 add_hook(&match_macro_assign, MACRO_ASSIGNMENT_HOOK); 1236 }