1 /* 2 * Copyright (C) 2013 Oracle. 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 * The plan here is to save all the possible values store to a given struct 20 * member. 21 * 22 * We will load all the values in to the function_type_val table first then 23 * run a script on that and load all the resulting values into the type_val 24 * table. 25 * 26 * So in this file we want to take the union of everything assigned to the 27 * struct member and insert it into the function_type_val at the end. 28 * 29 * You would think that we could use smatch_modification_hooks.c or 30 * extra_modification_hook() here to get the information here but in the end we 31 * need to code everything again a third time. 32 * 33 */ 34 35 #include "smatch.h" 36 #include "smatch_slist.h" 37 #include "smatch_extra.h" 38 39 static int my_id; 40 41 struct stree_stack *fn_type_val_stack; 42 struct stree *fn_type_val; 43 struct stree *global_type_val; 44 45 static int get_vals(void *_db_vals, int argc, char **argv, char **azColName) 46 { 47 char **db_vals = _db_vals; 48 49 *db_vals = alloc_string(argv[0]); 50 return 0; 51 } 52 53 static void match_inline_start(struct expression *expr) 54 { 55 push_stree(&fn_type_val_stack, fn_type_val); 56 fn_type_val = NULL; 57 } 58 59 static void match_inline_end(struct expression *expr) 60 { 61 free_stree(&fn_type_val); 62 fn_type_val = pop_stree(&fn_type_val_stack); 63 } 64 65 struct expr_rl { 66 struct expression *expr; 67 struct range_list *rl; 68 }; 69 static struct expr_rl cached_results[10]; 70 static int res_idx; 71 72 static int get_cached(struct expression *expr, struct range_list **rl, int *ret) 73 { 74 int i; 75 76 *ret = 0; 77 78 for (i = 0; i < ARRAY_SIZE(cached_results); i++) { 79 if (expr == cached_results[i].expr) { 80 if (cached_results[i].rl) { 81 *rl = clone_rl(cached_results[i].rl); 82 *ret = 1; 83 } 84 return 1; 85 } 86 } 87 88 return 0; 89 } 90 91 int get_db_type_rl(struct expression *expr, struct range_list **rl) 92 { 93 char *db_vals = NULL; 94 char *member; 95 struct range_list *tmp; 96 struct symbol *type; 97 int ret; 98 99 if (get_cached(expr, rl, &ret)) 100 return ret; 101 102 member = get_member_name(expr); 103 if (!member) 104 return 0; 105 106 res_idx = (res_idx + 1) % ARRAY_SIZE(cached_results); 107 cached_results[res_idx].expr = expr; 108 cached_results[res_idx].rl = NULL; 109 110 run_sql(get_vals, &db_vals, 111 "select value from type_value where type = '%s';", member); 112 free_string(member); 113 if (!db_vals) 114 return 0; 115 type = get_type(expr); 116 str_to_rl(type, db_vals, &tmp); 117 free_string(db_vals); 118 if (is_whole_rl(tmp)) 119 return 0; 120 121 *rl = tmp; 122 cached_results[res_idx].rl = clone_rl(tmp); 123 124 return 1; 125 } 126 127 static void add_type_val(char *member, struct range_list *rl) 128 { 129 struct smatch_state *old, *add, *new; 130 131 member = alloc_string(member); 132 old = get_state_stree(fn_type_val, my_id, member, NULL); 133 add = alloc_estate_rl(rl); 134 if (old) 135 new = merge_estates(old, add); 136 else 137 new = add; 138 set_state_stree(&fn_type_val, my_id, member, NULL, new); 139 } 140 141 static void add_fake_type_val(char *member, struct range_list *rl, int ignore) 142 { 143 struct smatch_state *old, *add, *new; 144 145 member = alloc_string(member); 146 old = get_state_stree(fn_type_val, my_id, member, NULL); 147 if (old && strcmp(old->name, "min-max") == 0) 148 return; 149 if (ignore && old && strcmp(old->name, "ignore") == 0) 150 return; 151 add = alloc_estate_rl(rl); 152 if (old) { 153 new = merge_estates(old, add); 154 } else { 155 new = add; 156 if (ignore) 157 new->name = alloc_string("ignore"); 158 else 159 new->name = alloc_string("min-max"); 160 } 161 set_state_stree(&fn_type_val, my_id, member, NULL, new); 162 } 163 164 static void add_global_type_val(char *member, struct range_list *rl) 165 { 166 struct smatch_state *old, *add, *new; 167 168 member = alloc_string(member); 169 old = get_state_stree(global_type_val, my_id, member, NULL); 170 add = alloc_estate_rl(rl); 171 if (old) 172 new = merge_estates(old, add); 173 else 174 new = add; 175 new = clone_estate_perm(new); 176 set_state_stree_perm(&global_type_val, my_id, member, NULL, new); 177 } 178 179 static int has_link_cb(void *has_link, int argc, char **argv, char **azColName) 180 { 181 *(int *)has_link = 1; 182 return 0; 183 } 184 185 static int is_ignored_fake_assignment(void) 186 { 187 struct expression *expr; 188 struct symbol *type; 189 char *member_name; 190 int has_link = 0; 191 192 expr = get_faked_expression(); 193 if (!expr || expr->type != EXPR_ASSIGNMENT) 194 return 0; 195 if (!is_void_pointer(expr->right)) 196 return 0; 197 member_name = get_member_name(expr->right); 198 if (!member_name) 199 return 0; 200 201 type = get_type(expr->left); 202 if (!type || type->type != SYM_PTR) 203 return 0; 204 type = get_real_base_type(type); 205 if (!type || type->type != SYM_STRUCT) 206 return 0; 207 208 run_sql(has_link_cb, &has_link, 209 "select * from data_info where type = %d and data = '%s' and value = '%s';", 210 TYPE_LINK, member_name, type_to_str(type)); 211 return has_link; 212 } 213 214 static int is_container_of(void) 215 { 216 /* We already check the macro name in is_ignored_macro() */ 217 struct expression *expr; 218 int offset; 219 220 expr = get_faked_expression(); 221 if (!expr || expr->type != EXPR_ASSIGNMENT) 222 return 0; 223 224 offset = get_offset_from_container_of(expr->right); 225 if (offset < 0) 226 return 0; 227 return 1; 228 } 229 230 static bool is_driver_data(void) 231 { 232 static struct expression *prev_expr; 233 struct expression *expr; 234 char *name; 235 static bool prev_ret; 236 bool ret = false; 237 238 expr = get_faked_expression(); 239 if (!expr || expr->type != EXPR_ASSIGNMENT) 240 return false; 241 242 if (expr == prev_expr) 243 return prev_ret; 244 prev_expr = expr; 245 246 name = expr_to_str(expr->right); 247 if (!name) { 248 prev_ret = false; 249 return false; 250 } 251 252 if (strstr(name, "get_drvdata(") || 253 strstr(name, "dev.driver_data") || 254 strstr(name, "dev->driver_data")) 255 ret = true; 256 257 free_string(name); 258 259 prev_ret = ret; 260 return ret; 261 } 262 263 static int is_ignored_macro(void) 264 { 265 struct expression *expr; 266 char *name; 267 268 expr = get_faked_expression(); 269 if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=') 270 return 0; 271 name = get_macro_name(expr->right->pos); 272 if (!name) 273 return 0; 274 if (strcmp(name, "container_of") == 0) 275 return 1; 276 if (strcmp(name, "rb_entry") == 0) 277 return 1; 278 if (strcmp(name, "list_entry") == 0) 279 return 1; 280 if (strcmp(name, "list_first_entry") == 0) 281 return 1; 282 if (strcmp(name, "hlist_entry") == 0) 283 return 1; 284 if (strcmp(name, "per_cpu_ptr") == 0) 285 return 1; 286 if (strcmp(name, "raw_cpu_ptr") == 0) 287 return 1; 288 if (strcmp(name, "this_cpu_ptr") == 0) 289 return 1; 290 291 if (strcmp(name, "TRACE_EVENT") == 0) 292 return 1; 293 if (strcmp(name, "DECLARE_EVENT_CLASS") == 0) 294 return 1; 295 if (strcmp(name, "DEFINE_EVENT") == 0) 296 return 1; 297 298 if (strstr(name, "for_each")) 299 return 1; 300 return 0; 301 } 302 303 static int is_ignored_function(void) 304 { 305 struct expression *expr; 306 307 expr = get_faked_expression(); 308 if (!expr || expr->type != EXPR_ASSIGNMENT) 309 return 0; 310 expr = strip_expr(expr->right); 311 if (!expr || expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL) 312 return 0; 313 314 if (sym_name_is("kmalloc", expr->fn)) 315 return 1; 316 if (sym_name_is("vmalloc", expr->fn)) 317 return 1; 318 if (sym_name_is("kvmalloc", expr->fn)) 319 return 1; 320 if (sym_name_is("kmalloc_array", expr->fn)) 321 return 1; 322 if (sym_name_is("vmalloc_array", expr->fn)) 323 return 1; 324 if (sym_name_is("kvmalloc_array", expr->fn)) 325 return 1; 326 327 if (sym_name_is("mmu_memory_cache_alloc", expr->fn)) 328 return 1; 329 if (sym_name_is("kmem_alloc", expr->fn)) 330 return 1; 331 if (sym_name_is("alloc_pages", expr->fn)) 332 return 1; 333 334 if (sym_name_is("netdev_priv", expr->fn)) 335 return 1; 336 if (sym_name_is("dev_get_drvdata", expr->fn)) 337 return 1; 338 if (sym_name_is("i2c_get_clientdata", expr->fn)) 339 return 1; 340 if (sym_name_is("idr_find", expr->fn)) 341 return 1; 342 343 return 0; 344 } 345 346 static int is_uncasted_pointer_assign(void) 347 { 348 struct expression *expr; 349 struct symbol *left_type, *right_type; 350 351 expr = get_faked_expression(); 352 if (!expr) 353 return 0; 354 if (expr->type == EXPR_PREOP || expr->type == EXPR_POSTOP) { 355 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT) 356 return 1; 357 } 358 if (expr->type != EXPR_ASSIGNMENT) 359 return 0; 360 left_type = get_type(expr->left); 361 right_type = get_type(expr->right); 362 363 if (!left_type || !right_type) 364 return 0; 365 366 if (left_type->type == SYM_STRUCT && left_type == right_type) 367 return 1; 368 369 if (left_type->type != SYM_PTR && 370 left_type->type != SYM_ARRAY) 371 return 0; 372 if (right_type->type != SYM_PTR && 373 right_type->type != SYM_ARRAY) 374 return 0; 375 left_type = get_real_base_type(left_type); 376 right_type = get_real_base_type(right_type); 377 378 if (left_type == right_type) 379 return 1; 380 return 0; 381 } 382 383 static int set_param_type(void *_type_str, int argc, char **argv, char **azColName) 384 { 385 char **type_str = _type_str; 386 static char type_buf[128]; 387 388 if (*type_str) { 389 if (strcmp(*type_str, argv[0]) == 0) 390 return 0; 391 strncpy(type_buf, "unknown", sizeof(type_buf)); 392 return 0; 393 } 394 strncpy(type_buf, argv[0], sizeof(type_buf)); 395 *type_str = type_buf; 396 397 return 0; 398 } 399 400 static char *db_get_parameter_type(int param) 401 { 402 char *ret = NULL; 403 404 if (!cur_func_sym) 405 return NULL; 406 407 run_sql(set_param_type, &ret, 408 "select value from fn_data_link where " 409 "file = '%s' and function = '%s' and static = %d and type = %d and parameter = %d and key = '$';", 410 (cur_func_sym->ctype.modifiers & MOD_STATIC) ? get_base_file() : "extern", 411 cur_func_sym->ident->name, 412 !!(cur_func_sym->ctype.modifiers & MOD_STATIC), 413 PASSES_TYPE, param); 414 415 return ret; 416 } 417 418 static int is_uncasted_fn_param_from_db(void) 419 { 420 struct expression *expr, *right; 421 struct symbol *left_type; 422 char left_type_name[128]; 423 int param; 424 char *right_type_name; 425 static struct expression *prev_expr; 426 static int prev_ans; 427 428 expr = get_faked_expression(); 429 430 if (expr == prev_expr) 431 return prev_ans; 432 prev_expr = expr; 433 prev_ans = 0; 434 435 if (!expr || expr->type != EXPR_ASSIGNMENT) 436 return 0; 437 left_type = get_type(expr->left); 438 if (!left_type || left_type->type != SYM_PTR) 439 return 0; 440 left_type = get_real_base_type(left_type); 441 if (!left_type || left_type->type != SYM_STRUCT) 442 return 0; 443 snprintf(left_type_name, sizeof(left_type_name), "%s", type_to_str(left_type)); 444 445 right = strip_expr(expr->right); 446 param = get_param_num(right); 447 if (param < 0) 448 return 0; 449 right_type_name = db_get_parameter_type(param); 450 if (!right_type_name) 451 return 0; 452 453 if (strcmp(right_type_name, left_type_name) == 0) { 454 prev_ans = 1; 455 return 1; 456 } 457 458 return 0; 459 } 460 461 static void match_assign_value(struct expression *expr) 462 { 463 char *member, *right_member; 464 struct range_list *rl; 465 struct symbol *type; 466 467 if (!cur_func_sym) 468 return; 469 470 type = get_type(expr->left); 471 if (type && type->type == SYM_STRUCT) 472 return; 473 member = get_member_name(expr->left); 474 if (!member) 475 return; 476 477 /* if we're saying foo->mtu = bar->mtu then that doesn't add information */ 478 right_member = get_member_name(expr->right); 479 if (right_member && strcmp(right_member, member) == 0) 480 goto free; 481 482 if (is_fake_call(expr->right)) { 483 if (is_ignored_macro()) 484 goto free; 485 if (is_ignored_function()) 486 goto free; 487 if (is_uncasted_pointer_assign()) 488 goto free; 489 if (is_uncasted_fn_param_from_db()) 490 goto free; 491 if (is_container_of()) 492 goto free; 493 if (is_driver_data()) 494 goto free; 495 add_fake_type_val(member, alloc_whole_rl(get_type(expr->left)), is_ignored_fake_assignment()); 496 goto free; 497 } 498 499 if (expr->op == '=') { 500 get_absolute_rl(expr->right, &rl); 501 rl = cast_rl(type, rl); 502 } else { 503 /* 504 * This is a bit cheating. We order it so this will already be set 505 * by smatch_extra.c and we just look up the value. 506 */ 507 get_absolute_rl(expr->left, &rl); 508 } 509 add_type_val(member, rl); 510 free: 511 free_string(right_member); 512 free_string(member); 513 } 514 515 /* 516 * If we too: int *p = &my_struct->member then abandon all hope of tracking 517 * my_struct->member. 518 */ 519 static void match_assign_pointer(struct expression *expr) 520 { 521 struct expression *right; 522 char *member; 523 struct range_list *rl; 524 struct symbol *type; 525 526 right = strip_expr(expr->right); 527 if (right->type != EXPR_PREOP || right->op != '&') 528 return; 529 right = strip_expr(right->unop); 530 531 member = get_member_name(right); 532 if (!member) 533 return; 534 type = get_type(right); 535 rl = alloc_whole_rl(type); 536 add_type_val(member, rl); 537 free_string(member); 538 } 539 540 static void match_global_assign(struct expression *expr) 541 { 542 char *member; 543 struct range_list *rl; 544 struct symbol *type; 545 546 type = get_type(expr->left); 547 if (type && (type->type == SYM_ARRAY || type->type == SYM_STRUCT)) 548 return; 549 member = get_member_name(expr->left); 550 if (!member) 551 return; 552 get_absolute_rl(expr->right, &rl); 553 rl = cast_rl(type, rl); 554 add_global_type_val(member, rl); 555 free_string(member); 556 } 557 558 static void unop_expr(struct expression *expr) 559 { 560 struct range_list *rl; 561 char *member; 562 563 if (expr->op != SPECIAL_DECREMENT && expr->op != SPECIAL_INCREMENT) 564 return; 565 566 expr = strip_expr(expr->unop); 567 member = get_member_name(expr); 568 if (!member) 569 return; 570 rl = alloc_whole_rl(get_type(expr)); 571 add_type_val(member, rl); 572 free_string(member); 573 } 574 575 static void asm_expr(struct statement *stmt) 576 { 577 struct expression *expr; 578 struct range_list *rl; 579 char *member; 580 581 FOR_EACH_PTR(stmt->asm_outputs, expr) { 582 member = get_member_name(expr->expr); 583 if (!member) 584 continue; 585 rl = alloc_whole_rl(get_type(expr->expr)); 586 add_type_val(member, rl); 587 free_string(member); 588 } END_FOR_EACH_PTR(expr); 589 } 590 591 static void db_param_add(struct expression *expr, int param, char *key, char *value) 592 { 593 struct expression *arg; 594 struct symbol *type; 595 struct range_list *rl; 596 char *member; 597 598 if (strcmp(key, "*$") != 0) 599 return; 600 601 while (expr->type == EXPR_ASSIGNMENT) 602 expr = strip_expr(expr->right); 603 if (expr->type != EXPR_CALL) 604 return; 605 606 arg = get_argument_from_call_expr(expr->args, param); 607 arg = strip_expr(arg); 608 if (!arg) 609 return; 610 type = get_member_type_from_key(arg, key); 611 /* 612 * The situation here is that say we memset() a void pointer to zero 613 * then that's returned to the called as "*$ = 0;" but on the caller's 614 * side it's not void, it's a struct. 615 * 616 * So the question is should we be passing that slightly bogus 617 * information back to the caller? Maybe, maybe not, but either way we 618 * are not going to record it here because a struct can't be zero. 619 * 620 */ 621 if (type && type->type == SYM_STRUCT) 622 return; 623 624 if (arg->type != EXPR_PREOP || arg->op != '&') 625 return; 626 arg = strip_expr(arg->unop); 627 628 member = get_member_name(arg); 629 if (!member) 630 return; 631 call_results_to_rl(expr, type, value, &rl); 632 add_type_val(member, rl); 633 free_string(member); 634 } 635 636 static void match_end_func_info(struct symbol *sym) 637 { 638 struct sm_state *sm; 639 640 FOR_EACH_SM(fn_type_val, sm) { 641 sql_insert_function_type_value(sm->name, sm->state->name); 642 } END_FOR_EACH_SM(sm); 643 } 644 645 static void clear_cache(struct symbol *sym) 646 { 647 memset(cached_results, 0, sizeof(cached_results)); 648 } 649 650 static void match_after_func(struct symbol *sym) 651 { 652 free_stree(&fn_type_val); 653 } 654 655 static void match_end_file(struct symbol_list *sym_list) 656 { 657 struct sm_state *sm; 658 659 FOR_EACH_SM(global_type_val, sm) { 660 sql_insert_function_type_value(sm->name, sm->state->name); 661 } END_FOR_EACH_SM(sm); 662 } 663 664 void register_type_val(int id) 665 { 666 my_id = id; 667 add_hook(&clear_cache, AFTER_FUNC_HOOK); 668 669 if (!option_info) 670 return; 671 672 add_hook(&match_assign_value, ASSIGNMENT_HOOK_AFTER); 673 add_hook(&match_assign_pointer, ASSIGNMENT_HOOK); 674 add_hook(&unop_expr, OP_HOOK); 675 add_hook(&asm_expr, ASM_HOOK); 676 select_return_states_hook(PARAM_ADD, &db_param_add); 677 select_return_states_hook(PARAM_SET, &db_param_add); 678 679 680 add_hook(&match_inline_start, INLINE_FN_START); 681 add_hook(&match_inline_end, INLINE_FN_END); 682 683 add_hook(&match_end_func_info, END_FUNC_HOOK); 684 add_hook(&match_after_func, AFTER_FUNC_HOOK); 685 686 add_hook(&match_global_assign, GLOBAL_ASSIGNMENT_HOOK); 687 add_hook(&match_end_file, END_FILE_HOOK); 688 } 689