1 /* 2 * Copyright (C) 2017 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 #include "smatch.h" 19 #include "smatch_slist.h" 20 #include "smatch_extra.h" 21 22 static int my_id; 23 static int param_id; 24 25 static struct stree *used_stree; 26 static struct stree_stack *saved_stack; 27 28 STATE(used); 29 30 int get_param_from_container_of(struct expression *expr) 31 { 32 struct expression *param_expr; 33 struct symbol *type; 34 sval_t sval; 35 int param; 36 37 38 type = get_type(expr); 39 if (!type || type->type != SYM_PTR) 40 return -1; 41 42 expr = strip_expr(expr); 43 if (expr->type != EXPR_BINOP || expr->op != '-') 44 return -1; 45 46 if (!get_value(expr->right, &sval)) 47 return -1; 48 if (sval.value < 0 || sval.value > 4096) 49 return -1; 50 51 param_expr = get_assigned_expr(expr->left); 52 if (!param_expr) 53 return -1; 54 param = get_param_num(param_expr); 55 if (param < 0) 56 return -1; 57 58 return param; 59 } 60 61 int get_offset_from_container_of(struct expression *expr) 62 { 63 struct expression *param_expr; 64 struct symbol *type; 65 sval_t sval; 66 67 type = get_type(expr); 68 if (!type || type->type != SYM_PTR) 69 return -1; 70 71 expr = strip_expr(expr); 72 if (expr->type != EXPR_BINOP || expr->op != '-') 73 return -1; 74 75 if (!get_value(expr->right, &sval)) 76 return -1; 77 if (sval.value < 0 || sval.value > 4096) 78 return -1; 79 80 param_expr = get_assigned_expr(expr->left); 81 if (!param_expr) 82 return -1; 83 84 return sval.value; 85 } 86 87 static int get_container_arg(struct symbol *sym) 88 { 89 struct expression *__mptr; 90 int param; 91 92 if (!sym || !sym->ident) 93 return -1; 94 95 __mptr = get_assigned_expr_name_sym(sym->ident->name, sym); 96 param = get_param_from_container_of(__mptr); 97 98 return param; 99 } 100 101 static int get_container_offset(struct symbol *sym) 102 { 103 struct expression *__mptr; 104 int offset; 105 106 if (!sym || !sym->ident) 107 return -1; 108 109 __mptr = get_assigned_expr_name_sym(sym->ident->name, sym); 110 offset = get_offset_from_container_of(__mptr); 111 112 return offset; 113 } 114 115 static char *get_container_name(struct sm_state *sm, int offset) 116 { 117 static char buf[256]; 118 const char *name; 119 120 name = get_param_name(sm); 121 if (!name) 122 return NULL; 123 124 if (name[0] == '$') 125 snprintf(buf, sizeof(buf), "$(-%d)%s", offset, name + 1); 126 else if (name[0] == '*' || name[1] == '$') 127 snprintf(buf, sizeof(buf), "*$(-%d)%s", offset, name + 2); 128 else 129 return NULL; 130 131 return buf; 132 } 133 134 static void get_state_hook(int owner, const char *name, struct symbol *sym) 135 { 136 int arg; 137 138 if (!option_info) 139 return; 140 if (__in_fake_assign) 141 return; 142 143 arg = get_container_arg(sym); 144 if (arg >= 0) 145 set_state_stree(&used_stree, my_id, name, sym, &used); 146 } 147 148 static void set_param_used(struct expression *call, struct expression *arg, char *key, char *unused) 149 { 150 struct symbol *sym; 151 char *name; 152 int arg_nr; 153 154 name = get_variable_from_key(arg, key, &sym); 155 if (!name || !sym) 156 goto free; 157 158 arg_nr = get_container_arg(sym); 159 if (arg_nr >= 0) 160 set_state(my_id, name, sym, &used); 161 free: 162 free_string(name); 163 } 164 165 static void process_states(void) 166 { 167 struct sm_state *tmp; 168 int arg, offset; 169 const char *name; 170 171 FOR_EACH_SM(used_stree, tmp) { 172 arg = get_container_arg(tmp->sym); 173 offset = get_container_offset(tmp->sym); 174 if (arg < 0 || offset < 0) 175 continue; 176 name = get_container_name(tmp, offset); 177 if (!name) 178 continue; 179 sql_insert_return_implies(CONTAINER, arg, name, ""); 180 } END_FOR_EACH_SM(tmp); 181 182 free_stree(&used_stree); 183 } 184 185 static void match_function_def(struct symbol *sym) 186 { 187 free_stree(&used_stree); 188 } 189 190 static void match_save_states(struct expression *expr) 191 { 192 push_stree(&saved_stack, used_stree); 193 used_stree = NULL; 194 } 195 196 static void match_restore_states(struct expression *expr) 197 { 198 free_stree(&used_stree); 199 used_stree = pop_stree(&saved_stack); 200 } 201 202 static void print_returns_container_of(int return_id, char *return_ranges, struct expression *expr) 203 { 204 int offset; 205 int param; 206 char key[64]; 207 char value[64]; 208 209 param = get_param_from_container_of(expr); 210 if (param < 0) 211 return; 212 offset = get_offset_from_container_of(expr); 213 if (offset < 0) 214 return; 215 216 snprintf(key, sizeof(key), "%d", param); 217 snprintf(value, sizeof(value), "-%d", offset); 218 219 /* no need to add it to return_implies because it's not really param_used */ 220 sql_insert_return_states(return_id, return_ranges, CONTAINER, -1, 221 key, value); 222 } 223 224 static void returns_container_of(struct expression *expr, int param, char *key, char *value) 225 { 226 struct expression *call, *arg; 227 int offset; 228 char buf[64]; 229 230 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=') 231 return; 232 call = strip_expr(expr->right); 233 if (call->type != EXPR_CALL) 234 return; 235 if (param != -1) 236 return; 237 param = atoi(key); 238 offset = atoi(value); 239 240 arg = get_argument_from_call_expr(call->args, param); 241 if (!arg) 242 return; 243 if (arg->type != EXPR_SYMBOL) 244 return; 245 param = get_param_num(arg); 246 if (param < 0) 247 return; 248 snprintf(buf, sizeof(buf), "$(%d)", offset); 249 sql_insert_return_implies(CONTAINER, param, buf, ""); 250 } 251 252 static int get_shared_cnt(const char *one, const char *two) 253 { 254 int i; 255 int on_end = false; 256 257 i = 0; 258 while (true) { 259 if (!one[i] || !two[i]) { 260 on_end = true; 261 break; 262 } 263 if (one[i] != two[i]) 264 break; 265 i++; 266 } 267 if (i == 0) 268 return 0; 269 i--; 270 while (i > 0 && (one[i] == '>' || one[i] == '-' || one[i] == '.')) { 271 on_end = true; 272 i--; 273 } 274 if (!on_end) 275 return 0; 276 277 return i + 1; 278 } 279 280 static int build_offset_str(struct expression *expr, const char *name, 281 int shared, char *buf, int size, int op) 282 { 283 int chop = 0; 284 int offset; 285 int i; 286 287 i = shared; 288 while (name[i]) { 289 if (name[i] == '.' || name[i] == '-') 290 chop++; 291 i++; 292 } 293 294 // FIXME: Handle more chops 295 if (chop > 1) 296 return 0; 297 298 if (chop == 0) { 299 offset = 0; 300 } else { 301 offset = get_member_offset_from_deref(expr); 302 if (offset < 0) 303 return 0; 304 } 305 306 snprintf(buf, size, "%c%d", (op == '+') ? '+' : '-', offset); 307 return 1; 308 } 309 310 static void match_call(struct expression *call) 311 { 312 struct expression *fn, *arg; 313 char *fn_name, *arg_name; 314 int param, shared; 315 char minus_str[64]; 316 char plus_str[64]; 317 char offset_str[64]; 318 bool star; 319 320 /* 321 * We're trying to link the function with the parameter. There are a 322 * couple ways this can be passed: 323 * foo->func(foo, ...); 324 * foo->func(foo->x, ...); 325 * foo->bar.func(&foo->bar, ...); 326 * foo->bar->baz->func(foo, ...); 327 * 328 * So the method is basically to subtract the offsets until we get to 329 * the common bit, then add the member offsets to get the parameter. 330 * 331 * If we're taking an address then the offset math is not stared, 332 * otherwise it is. Starred means dereferenced. 333 */ 334 fn = strip_expr(call->fn); 335 fn_name = expr_to_var(fn); 336 if (!fn_name) 337 return; 338 339 param = -1; 340 FOR_EACH_PTR(call->args, arg) { 341 param++; 342 343 arg = strip_expr(arg); 344 star = true; 345 if (arg->type == EXPR_PREOP && arg->op == '&') { 346 arg = strip_expr(arg->unop); 347 star = false; 348 } 349 350 arg_name = expr_to_var(arg); 351 if (!arg_name) 352 continue; 353 shared = get_shared_cnt(fn_name, arg_name); 354 if (!shared) 355 goto free_arg_name; 356 if (!build_offset_str(fn, fn_name, shared, minus_str, sizeof(minus_str), '-')) 357 goto free_arg_name; 358 if (!build_offset_str(arg, arg_name, shared, plus_str, sizeof(plus_str), '+')) 359 goto free_arg_name; 360 if (star) 361 snprintf(offset_str, sizeof(offset_str), "*(%s%s)", minus_str, plus_str); 362 else 363 snprintf(offset_str, sizeof(offset_str), "%s%s", minus_str, plus_str); 364 sql_insert_caller_info(call, CONTAINER, param, offset_str, "$(-1)"); 365 free_arg_name: 366 free_string(arg_name); 367 } END_FOR_EACH_PTR(arg); 368 369 free_string(fn_name); 370 } 371 372 static void db_passed_container(const char *name, struct symbol *sym, char *key, char *value) 373 { 374 sval_t offset = { 375 .type = &int_ctype, 376 }; 377 const char *arg_offset; 378 int star = 0; 379 int val; 380 381 if (key[0] == '*') { 382 star = 1; 383 key += 2; 384 } 385 386 val = atoi(key); 387 if (val < -4095 || val > 0) 388 return; 389 offset.value = -val; 390 arg_offset = strchr(key, '+'); 391 if (!arg_offset) 392 return; 393 val = atoi(arg_offset + 1); 394 if (val > 4095 || val < 0) 395 return; 396 offset.value |= val << 16; 397 if (star) 398 offset.value |= 1ULL << 31; 399 400 set_state(param_id, name, sym, alloc_estate_sval(offset)); 401 } 402 403 struct db_info { 404 struct symbol *arg; 405 int prev_offset; 406 struct range_list *rl; 407 int star; 408 struct stree *stree; 409 }; 410 411 static struct symbol *get_member_from_offset(struct symbol *sym, int offset) 412 { 413 struct symbol *type, *tmp; 414 int cur; 415 416 type = get_real_base_type(sym); 417 if (!type || type->type != SYM_PTR) 418 return NULL; 419 type = get_real_base_type(type); 420 if (!type || type->type != SYM_STRUCT) 421 return NULL; 422 423 cur = 0; 424 FOR_EACH_PTR(type->symbol_list, tmp) { 425 cur = ALIGN(cur, tmp->ctype.alignment); 426 if (offset == cur) 427 return tmp; 428 cur += type_bytes(tmp); 429 } END_FOR_EACH_PTR(tmp); 430 return NULL; 431 } 432 433 static struct symbol *get_member_type_from_offset(struct symbol *sym, int offset) 434 { 435 struct symbol *base_type; 436 struct symbol *member; 437 438 base_type = get_real_base_type(sym); 439 if (base_type && base_type->type == SYM_PTR) 440 base_type = get_real_base_type(base_type); 441 if (offset == 0 && base_type && base_type->type == SYM_BASETYPE) 442 return base_type; 443 444 member = get_member_from_offset(sym, offset); 445 if (!member) 446 return NULL; 447 return get_real_base_type(member); 448 } 449 450 static const char *get_name_from_offset(struct symbol *arg, int offset) 451 { 452 struct symbol *member, *type; 453 const char *name; 454 static char fullname[256]; 455 456 name = arg->ident->name; 457 458 type = get_real_base_type(arg); 459 if (!type || type->type != SYM_PTR) 460 return name; 461 462 type = get_real_base_type(type); 463 if (!type) 464 return NULL; 465 if (type->type != SYM_STRUCT) { 466 snprintf(fullname, sizeof(fullname), "*%s", name); 467 return fullname; 468 } 469 470 member = get_member_from_offset(arg, offset); 471 if (!member) 472 return NULL; 473 474 snprintf(fullname, sizeof(fullname), "%s->%s", name, member->ident->name); 475 return fullname; 476 } 477 478 static void set_param_value(struct stree **stree, struct symbol *arg, int offset, struct range_list *rl) 479 { 480 const char *name; 481 482 name = get_name_from_offset(arg, offset); 483 if (!name) 484 return; 485 set_state_stree(stree, SMATCH_EXTRA, name, arg, alloc_estate_rl(rl)); 486 } 487 488 static int save_vals(void *_db_info, int argc, char **argv, char **azColName) 489 { 490 struct db_info *db_info = _db_info; 491 struct symbol *type; 492 struct range_list *rl; 493 int offset = 0; 494 const char *value; 495 496 if (argc == 2) { 497 offset = atoi(argv[0]); 498 value = argv[1]; 499 } else { 500 value = argv[0]; 501 } 502 503 if (db_info->prev_offset != -1 && 504 db_info->prev_offset != offset) { 505 set_param_value(&db_info->stree, db_info->arg, db_info->prev_offset, db_info->rl); 506 db_info->rl = NULL; 507 } 508 509 db_info->prev_offset = offset; 510 511 type = get_real_base_type(db_info->arg); 512 if (db_info->star) 513 goto found_type; 514 if (type->type != SYM_PTR) 515 return 0; 516 type = get_real_base_type(type); 517 if (type->type == SYM_BASETYPE) 518 goto found_type; 519 type = get_member_type_from_offset(db_info->arg, offset); 520 found_type: 521 str_to_rl(type, (char *)value, &rl); 522 if (db_info->rl) 523 db_info->rl = rl_union(db_info->rl, rl); 524 else 525 db_info->rl = rl; 526 527 return 0; 528 } 529 530 static struct stree *load_tag_info_sym(mtag_t tag, struct symbol *arg, int arg_offset, int star) 531 { 532 struct db_info db_info = { 533 .arg = arg, 534 .prev_offset = -1, 535 .star = star, 536 }; 537 struct symbol *type; 538 539 if (!tag || !arg->ident) 540 return NULL; 541 542 type = get_real_base_type(arg); 543 if (!type) 544 return NULL; 545 if (!star) { 546 if (type->type != SYM_PTR) 547 return NULL; 548 type = get_real_base_type(type); 549 if (!type) 550 return NULL; 551 } 552 553 if (star || type->type == SYM_BASETYPE) { 554 run_sql(save_vals, &db_info, 555 "select value from mtag_data where tag = %lld and offset = %d and type = %d;", 556 tag, arg_offset, DATA_VALUE); 557 } else { /* presumably the parameter is a struct pointer */ 558 run_sql(save_vals, &db_info, 559 "select offset, value from mtag_data where tag = %lld and type = %d;", 560 tag, DATA_VALUE); 561 } 562 563 if (db_info.prev_offset != -1) 564 set_param_value(&db_info.stree, arg, db_info.prev_offset, db_info.rl); 565 566 // FIXME: handle an offset correctly 567 if (!star && !arg_offset) { 568 sval_t sval; 569 570 sval.type = get_real_base_type(arg); 571 sval.uvalue = tag; 572 set_state_stree(&db_info.stree, SMATCH_EXTRA, arg->ident->name, arg, alloc_estate_sval(sval)); 573 } 574 return db_info.stree; 575 } 576 577 static void handle_passed_container(struct symbol *sym) 578 { 579 struct symbol *arg; 580 struct smatch_state *state; 581 struct sm_state *sm; 582 struct stree *stree; 583 mtag_t fn_tag, container_tag, arg_tag; 584 sval_t offset; 585 int container_offset, arg_offset; 586 int star; 587 588 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) { 589 state = get_state(param_id, arg->ident->name, arg); 590 if (state) 591 goto found; 592 } END_FOR_EACH_PTR(arg); 593 594 return; 595 found: 596 if (!estate_get_single_value(state, &offset)) 597 return; 598 container_offset = -(offset.value & 0xffff); 599 arg_offset = (offset.value & 0xfff0000) >> 16; 600 star = !!(offset.value & (1ULL << 31)); 601 602 if (!get_toplevel_mtag(cur_func_sym, &fn_tag)) 603 return; 604 if (!mtag_map_select_container(fn_tag, container_offset, &container_tag)) 605 return; 606 if (!arg_offset || star) { 607 arg_tag = container_tag; 608 } else { 609 if (!mtag_map_select_tag(container_tag, -arg_offset, &arg_tag)) 610 return; 611 } 612 613 stree = load_tag_info_sym(arg_tag, arg, arg_offset, star); 614 FOR_EACH_SM(stree, sm) { 615 set_state(sm->owner, sm->name, sm->sym, sm->state); 616 } END_FOR_EACH_SM(sm); 617 free_stree(&stree); 618 } 619 620 void register_container_of(int id) 621 { 622 my_id = id; 623 624 add_hook(&match_function_def, FUNC_DEF_HOOK); 625 626 add_get_state_hook(&get_state_hook); 627 628 add_hook(&match_save_states, INLINE_FN_START); 629 add_hook(&match_restore_states, INLINE_FN_END); 630 631 select_return_implies_hook(CONTAINER, &set_param_used); 632 all_return_states_hook(&process_states); 633 634 add_split_return_callback(&print_returns_container_of); 635 select_return_states_hook(CONTAINER, &returns_container_of); 636 637 add_hook(&match_call, FUNCTION_CALL_HOOK); 638 } 639 640 static struct smatch_state *unmatched_state(struct sm_state *sm) 641 { 642 return alloc_estate_whole(estate_type(sm->state)); 643 } 644 645 void register_container_of2(int id) 646 { 647 param_id = id; 648 649 select_caller_info_hook(db_passed_container, CONTAINER); 650 add_hook(&handle_passed_container, AFTER_DEF_HOOK); 651 add_unmatched_state_hook(param_id, &unmatched_state); 652 add_merge_hook(param_id, &merge_estates); 653 } 654 655