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