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