1 /* 2 * Copyright (C) 2012 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 24 struct { 25 const char *func; 26 int param; 27 } alloc_functions[] = { 28 {"kmalloc", 0}, 29 {"kzalloc", 0}, 30 {"__kmalloc", 0}, 31 {"vmalloc", 0}, 32 {"__vmalloc", 0}, 33 {"__vmalloc_node", 0}, 34 }; 35 36 static struct range_list_stack *rl_stack; 37 static struct string_list *op_list; 38 39 static void push_op(char c) 40 { 41 char *p; 42 43 p = malloc(1); 44 p[0] = c; 45 add_ptr_list(&op_list, p); 46 } 47 48 static char pop_op(void) 49 { 50 char *p; 51 char c; 52 53 if (!op_list) { 54 sm_perror("%s: no op_list", __func__); 55 return '\0'; 56 } 57 58 p = last_ptr_list((struct ptr_list *)op_list); 59 60 delete_ptr_list_last((struct ptr_list **)&op_list); 61 c = p[0]; 62 free(p); 63 64 return c; 65 } 66 67 static int op_precedence(char c) 68 { 69 switch (c) { 70 case '+': 71 case '-': 72 return 1; 73 case '*': 74 case '/': 75 return 2; 76 default: 77 return 0; 78 } 79 } 80 81 static int top_op_precedence(void) 82 { 83 char *p; 84 85 if (!op_list) 86 return 0; 87 88 p = last_ptr_list((struct ptr_list *)op_list); 89 return op_precedence(p[0]); 90 } 91 92 static void rl_pop_until(char c) 93 { 94 char op; 95 struct range_list *left, *right; 96 struct range_list *res; 97 98 while (top_op_precedence() && op_precedence(c) <= top_op_precedence()) { 99 op = pop_op(); 100 right = pop_rl(&rl_stack); 101 left = pop_rl(&rl_stack); 102 res = rl_binop(left, op, right); 103 if (!res) 104 res = alloc_whole_rl(&llong_ctype); 105 push_rl(&rl_stack, res); 106 } 107 } 108 109 static void rl_discard_stacks(void) 110 { 111 while (op_list) 112 pop_op(); 113 while (rl_stack) 114 pop_rl(&rl_stack); 115 } 116 117 static int read_rl_from_var(struct expression *call, char *p, char **end, struct range_list **rl) 118 { 119 struct expression *arg; 120 struct smatch_state *state; 121 long param; 122 char *name; 123 struct symbol *sym; 124 char buf[256]; 125 int star; 126 127 p++; 128 param = strtol(p, &p, 10); 129 130 arg = get_argument_from_call_expr(call->args, param); 131 if (!arg) 132 return 0; 133 134 if (*p != '-' && *p != '.') { 135 get_absolute_rl(arg, rl); 136 *end = p; 137 return 1; 138 } 139 140 *end = strchr(p, ' '); 141 142 if (arg->type == EXPR_PREOP && arg->op == '&') { 143 arg = strip_expr(arg->unop); 144 star = 0; 145 p++; 146 } else { 147 star = 1; 148 p += 2; 149 } 150 151 name = expr_to_var_sym(arg, &sym); 152 if (!name) 153 return 0; 154 snprintf(buf, sizeof(buf), "%s%s", name, star ? "->" : "."); 155 free_string(name); 156 157 if (*end - p + strlen(buf) >= sizeof(buf)) 158 return 0; 159 strncat(buf, p, *end - p); 160 161 state = get_state(SMATCH_EXTRA, buf, sym); 162 if (!state) 163 return 0; 164 *rl = estate_rl(state); 165 return 1; 166 } 167 168 static int read_var_num(struct expression *call, char *p, char **end, struct range_list **rl) 169 { 170 sval_t sval; 171 172 while (*p == ' ') 173 p++; 174 175 if (*p == '$') 176 return read_rl_from_var(call, p, end, rl); 177 178 sval.type = &llong_ctype; 179 sval.value = strtoll(p, end, 10); 180 if (*end == p) 181 return 0; 182 *rl = alloc_rl(sval, sval); 183 return 1; 184 } 185 186 static char *read_op(char *p) 187 { 188 while (*p == ' ') 189 p++; 190 191 switch (*p) { 192 case '+': 193 case '-': 194 case '*': 195 case '/': 196 return p; 197 default: 198 return NULL; 199 } 200 } 201 202 int parse_call_math_rl(struct expression *call, char *math, struct range_list **rl) 203 { 204 struct range_list *tmp; 205 char *c; 206 207 /* try to implement shunting yard algorithm. */ 208 209 c = (char *)math; 210 while (1) { 211 if (option_debug) 212 sm_msg("parsing %s", c); 213 214 /* read a number and push it onto the number stack */ 215 if (!read_var_num(call, c, &c, &tmp)) 216 goto fail; 217 push_rl(&rl_stack, tmp); 218 219 if (option_debug) 220 sm_msg("val = %s remaining = %s", show_rl(tmp), c); 221 222 if (!*c) 223 break; 224 if (*c == ']' && *(c + 1) == '\0') 225 break; 226 227 c = read_op(c); 228 if (!c) 229 goto fail; 230 231 if (option_debug) 232 sm_msg("op = %c remaining = %s", *c, c); 233 234 rl_pop_until(*c); 235 push_op(*c); 236 c++; 237 } 238 239 rl_pop_until(0); 240 *rl = pop_rl(&rl_stack); 241 return 1; 242 fail: 243 rl_discard_stacks(); 244 return 0; 245 } 246 247 int parse_call_math(struct expression *call, char *math, sval_t *sval) 248 { 249 struct range_list *rl; 250 251 if (!parse_call_math_rl(call, math, &rl)) 252 return 0; 253 if (!rl_to_sval(rl, sval)) 254 return 0; 255 return 1; 256 } 257 258 static struct smatch_state *alloc_state_sname(char *sname) 259 { 260 struct smatch_state *state; 261 262 state = __alloc_smatch_state(0); 263 state->name = sname; 264 state->data = INT_PTR(1); 265 return state; 266 } 267 268 static int get_arg_number(struct expression *expr) 269 { 270 struct symbol *sym; 271 struct symbol *arg; 272 int i; 273 274 expr = strip_expr(expr); 275 if (expr->type != EXPR_SYMBOL) 276 return -1; 277 sym = expr->symbol; 278 279 i = 0; 280 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) { 281 if (arg == sym) 282 return i; 283 i++; 284 } END_FOR_EACH_PTR(arg); 285 286 return -1; 287 } 288 289 static int format_name_sym_helper(char *buf, int remaining, char *name, struct symbol *sym) 290 { 291 int ret = 0; 292 int arg; 293 char *param_name; 294 int name_len; 295 296 if (!name || !sym || !sym->ident) 297 goto free; 298 arg = get_param_num_from_sym(sym); 299 if (arg < 0) 300 goto free; 301 if (param_was_set_var_sym(name, sym)) 302 goto free; 303 304 param_name = sym->ident->name; 305 name_len = strlen(param_name); 306 307 if (name[name_len] == '\0') 308 ret = snprintf(buf, remaining, "$%d", arg); 309 else if (name[name_len] == '-') 310 ret = snprintf(buf, remaining, "$%d%s", arg, name + name_len); 311 else 312 goto free; 313 314 remaining -= ret; 315 if (remaining <= 0) 316 ret = 0; 317 318 free: 319 free_string(name); 320 321 return ret; 322 323 } 324 325 static int format_variable_helper(char *buf, int remaining, struct expression *expr) 326 { 327 char *name; 328 struct symbol *sym; 329 330 name = expr_to_var_sym(expr, &sym); 331 if (param_was_set_var_sym(name, sym)) 332 return 0; 333 return format_name_sym_helper(buf, remaining, name, sym); 334 } 335 336 static int format_call_to_param_mapping(char *buf, int remaining, struct expression *expr) 337 { 338 char *name; 339 struct symbol *sym; 340 341 name = map_call_to_param_name_sym(expr, &sym); 342 if (param_was_set_var_sym(name, sym)) 343 return 0; 344 return format_name_sym_helper(buf, remaining, name, sym); 345 } 346 347 static int format_expr_helper(char *buf, int remaining, struct expression *expr) 348 { 349 sval_t sval; 350 int ret; 351 char *cur; 352 353 if (!expr) 354 return 0; 355 356 cur = buf; 357 358 if (expr->type == EXPR_BINOP) { 359 ret = format_expr_helper(cur, remaining, expr->left); 360 if (ret == 0) 361 return 0; 362 remaining -= ret; 363 if (remaining <= 0) 364 return 0; 365 cur += ret; 366 367 ret = snprintf(cur, remaining, " %s ", show_special(expr->op)); 368 remaining -= ret; 369 if (remaining <= 0) 370 return 0; 371 cur += ret; 372 373 ret = format_expr_helper(cur, remaining, expr->right); 374 if (ret == 0) 375 return 0; 376 remaining -= ret; 377 if (remaining <= 0) 378 return 0; 379 cur += ret; 380 return cur - buf; 381 } 382 383 if (get_implied_value(expr, &sval)) { 384 ret = snprintf(cur, remaining, "%s", sval_to_str(sval)); 385 remaining -= ret; 386 if (remaining <= 0) 387 return 0; 388 return ret; 389 } 390 391 if (expr->type == EXPR_CALL) 392 return format_call_to_param_mapping(cur, remaining, expr); 393 394 return format_variable_helper(cur, remaining, expr); 395 } 396 397 static char *format_expr(struct expression *expr) 398 { 399 char buf[256] = ""; 400 int ret; 401 402 ret = format_expr_helper(buf, sizeof(buf), expr); 403 if (ret == 0) 404 return NULL; 405 406 return alloc_sname(buf); 407 } 408 409 char *get_value_in_terms_of_parameter_math(struct expression *expr) 410 { 411 struct expression *tmp; 412 char buf[256] = ""; 413 sval_t dummy; 414 int ret; 415 416 tmp = get_assigned_expr(expr); 417 if (tmp) 418 expr = tmp; 419 if (param_was_set(expr)) 420 return NULL; 421 422 if (get_implied_value(expr, &dummy)) 423 return NULL; 424 425 ret = format_expr_helper(buf, sizeof(buf), expr); 426 if (ret == 0) 427 return NULL; 428 429 return alloc_sname(buf); 430 } 431 432 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym) 433 { 434 struct expression *tmp, *expr; 435 char buf[256] = ""; 436 int ret; 437 int cnt = 0; 438 439 expr = get_assigned_expr_name_sym(name, sym); 440 if (!expr) 441 return NULL; 442 while ((tmp = get_assigned_expr(expr))) { 443 expr = strip_expr(tmp); 444 if (++cnt > 3) 445 break; 446 } 447 448 ret = format_expr_helper(buf, sizeof(buf), expr); 449 if (ret == 0) 450 return NULL; 451 452 return alloc_sname(buf); 453 454 } 455 456 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg) 457 { 458 int size_arg = PTR_INT(_size_arg); 459 struct expression *right; 460 struct expression *size_expr; 461 char *sname; 462 463 right = strip_expr(expr->right); 464 size_expr = get_argument_from_call_expr(right->args, size_arg); 465 466 sname = format_expr(size_expr); 467 if (!sname) 468 return; 469 set_state_expr(my_id, expr->left, alloc_state_sname(sname)); 470 } 471 472 static char *swap_format(struct expression *call, char *format) 473 { 474 char buf[256]; 475 sval_t sval; 476 long param; 477 struct expression *arg; 478 char *p; 479 char *out; 480 int ret; 481 482 if (format[0] == '$' && format[2] == '\0') { 483 param = strtol(format + 1, NULL, 10); 484 arg = get_argument_from_call_expr(call->args, param); 485 if (!arg) 486 return NULL; 487 return format_expr(arg); 488 } 489 490 buf[0] = '\0'; 491 p = format; 492 out = buf; 493 while (*p) { 494 if (*p == '$') { 495 p++; 496 param = strtol(p, &p, 10); 497 arg = get_argument_from_call_expr(call->args, param); 498 if (!arg) 499 return NULL; 500 param = get_arg_number(arg); 501 if (param >= 0) { 502 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param); 503 out += ret; 504 if (out >= buf + sizeof(buf)) 505 return NULL; 506 } else if (get_implied_value(arg, &sval)) { 507 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval)); 508 out += ret; 509 if (out >= buf + sizeof(buf)) 510 return NULL; 511 } else { 512 return NULL; 513 } 514 } 515 *out = *p; 516 p++; 517 out++; 518 } 519 if (buf[0] == '\0') 520 return NULL; 521 *out = '\0'; 522 return alloc_sname(buf); 523 } 524 525 static char *buf_size_recipe; 526 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName) 527 { 528 if (argc != 1) 529 return 0; 530 531 if (!buf_size_recipe) 532 buf_size_recipe = alloc_sname(argv[0]); 533 else if (strcmp(buf_size_recipe, argv[0]) != 0) 534 buf_size_recipe = alloc_sname("invalid"); 535 return 0; 536 } 537 538 static char *get_allocation_recipe_from_call(struct expression *expr) 539 { 540 struct symbol *sym; 541 static char sql_filter[1024]; 542 int i; 543 544 if (is_fake_call(expr)) 545 return NULL; 546 expr = strip_expr(expr); 547 if (expr->fn->type != EXPR_SYMBOL) 548 return NULL; 549 sym = expr->fn->symbol; 550 if (!sym) 551 return NULL; 552 553 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) { 554 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) { 555 char buf[32]; 556 557 snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param); 558 buf_size_recipe = alloc_sname(buf); 559 return swap_format(expr, buf_size_recipe); 560 } 561 } 562 563 if (sym->ctype.modifiers & MOD_STATIC) { 564 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';", 565 get_filename(), sym->ident->name); 566 } else { 567 snprintf(sql_filter, 1024, "function = '%s' and static = 0;", 568 sym->ident->name); 569 } 570 571 buf_size_recipe = NULL; 572 run_sql(db_buf_size_callback, NULL, 573 "select value from return_states where type=%d and %s", 574 BUF_SIZE, sql_filter); 575 if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0) 576 return NULL; 577 return swap_format(expr, buf_size_recipe); 578 } 579 580 static void match_call_assignment(struct expression *expr) 581 { 582 char *sname; 583 584 sname = get_allocation_recipe_from_call(expr->right); 585 if (!sname) 586 return; 587 set_state_expr(my_id, expr->left, alloc_state_sname(sname)); 588 } 589 590 static void match_returns_call(int return_id, char *return_ranges, struct expression *call) 591 { 592 char *sname; 593 594 sname = get_allocation_recipe_from_call(call); 595 if (option_debug) 596 sm_msg("sname = %s", sname); 597 if (!sname) 598 return; 599 600 sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "", 601 sname); 602 } 603 604 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr) 605 { 606 struct expression *tmp; 607 struct smatch_state *state; 608 struct symbol *sym; 609 char *name; 610 int cnt = 0; 611 612 expr = strip_expr(expr); 613 while ((tmp = get_assigned_expr(expr))) { 614 if (cnt++ > 5) /* assignments to self cause infinite loops */ 615 break; 616 expr = strip_expr(tmp); 617 } 618 if (!expr) 619 return; 620 621 if (expr->type == EXPR_CALL) { 622 match_returns_call(return_id, return_ranges, expr); 623 return; 624 } 625 626 name = expr_to_var_sym(expr, &sym); 627 if (!name || !sym) 628 goto free; 629 630 state = get_state(my_id, name, sym); 631 if (!state || !state->data) 632 goto free; 633 634 sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "", 635 state->name); 636 free: 637 free_string(name); 638 } 639 640 void register_parse_call_math(int id) 641 { 642 int i; 643 644 my_id = id; 645 646 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) 647 add_function_assign_hook(alloc_functions[i].func, &match_alloc, 648 INT_PTR(alloc_functions[i].param)); 649 add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK); 650 add_split_return_callback(print_returned_allocations); 651 } 652 653