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