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, const char *p, const 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, (char **)&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, const char *p, const 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, (char **)end, 10); 180 if (*end == p) 181 return 0; 182 *rl = alloc_rl(sval, sval); 183 return 1; 184 } 185 186 static const char *read_op(const 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, const char *math, struct range_list **rl) 203 { 204 struct range_list *tmp; 205 const char *c; 206 207 /* try to implement shunting yard algorithm. */ 208 209 c = 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 is_mtag_sval(sval_t sval) 348 { 349 if (!is_ptr_type(sval.type)) 350 return 0; 351 if (sval_cmp(sval, valid_ptr_min_sval) >= 0 && 352 sval_cmp(sval, valid_ptr_max_sval) <= 0) 353 return 1; 354 return 0; 355 } 356 357 static int format_expr_helper(char *buf, int remaining, struct expression *expr) 358 { 359 sval_t sval; 360 int ret; 361 char *cur; 362 363 if (!expr) 364 return 0; 365 366 cur = buf; 367 368 if (expr->type == EXPR_BINOP) { 369 ret = format_expr_helper(cur, remaining, expr->left); 370 if (ret == 0) 371 return 0; 372 remaining -= ret; 373 if (remaining <= 0) 374 return 0; 375 cur += ret; 376 377 ret = snprintf(cur, remaining, " %s ", show_special(expr->op)); 378 remaining -= ret; 379 if (remaining <= 0) 380 return 0; 381 cur += ret; 382 383 ret = format_expr_helper(cur, remaining, expr->right); 384 if (ret == 0) 385 return 0; 386 remaining -= ret; 387 if (remaining <= 0) 388 return 0; 389 cur += ret; 390 return cur - buf; 391 } 392 393 if (!param_was_set(expr) && get_implied_value(expr, &sval) && !is_mtag_sval(sval)) { 394 ret = snprintf(cur, remaining, "%s", sval_to_str(sval)); 395 remaining -= ret; 396 if (remaining <= 0) 397 return 0; 398 return ret; 399 } 400 401 if (expr->type == EXPR_CALL) 402 return format_call_to_param_mapping(cur, remaining, expr); 403 404 return format_variable_helper(cur, remaining, expr); 405 } 406 407 static char *format_expr(struct expression *expr) 408 { 409 char buf[256] = ""; 410 int ret; 411 412 ret = format_expr_helper(buf, sizeof(buf), expr); 413 if (ret == 0) 414 return NULL; 415 416 return alloc_sname(buf); 417 } 418 419 char *get_value_in_terms_of_parameter_math(struct expression *expr) 420 { 421 struct expression *tmp; 422 char buf[256] = ""; 423 sval_t dummy; 424 int ret; 425 426 tmp = get_assigned_expr(expr); 427 if (tmp) 428 expr = tmp; 429 if (param_was_set(expr)) 430 return NULL; 431 432 if (get_implied_value(expr, &dummy)) 433 return NULL; 434 435 ret = format_expr_helper(buf, sizeof(buf), expr); 436 if (ret == 0) 437 return NULL; 438 439 return alloc_sname(buf); 440 } 441 442 char *get_value_in_terms_of_parameter_math_var_sym(const char *name, struct symbol *sym) 443 { 444 struct expression *tmp, *expr; 445 char buf[256] = ""; 446 int ret; 447 int cnt = 0; 448 sval_t sval; 449 450 expr = get_assigned_expr_name_sym(name, sym); 451 if (!expr) 452 return NULL; 453 while ((tmp = get_assigned_expr(expr))) { 454 expr = strip_expr(tmp); 455 if (++cnt > 3) 456 break; 457 } 458 459 if (get_implied_value(expr, &sval)) 460 return NULL; 461 462 ret = format_expr_helper(buf, sizeof(buf), expr); 463 if (ret == 0) 464 return NULL; 465 466 return alloc_sname(buf); 467 468 } 469 470 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg) 471 { 472 int size_arg = PTR_INT(_size_arg); 473 struct expression *right; 474 struct expression *size_expr; 475 char *sname; 476 477 right = strip_expr(expr->right); 478 size_expr = get_argument_from_call_expr(right->args, size_arg); 479 480 sname = format_expr(size_expr); 481 if (!sname) 482 return; 483 set_state_expr(my_id, expr->left, alloc_state_sname(sname)); 484 } 485 486 static char *swap_format(struct expression *call, char *format) 487 { 488 char buf[256]; 489 sval_t sval; 490 long param; 491 struct expression *arg; 492 char *p; 493 char *out; 494 int ret; 495 496 if (format[0] == '$' && format[2] == '\0') { 497 param = strtol(format + 1, NULL, 10); 498 arg = get_argument_from_call_expr(call->args, param); 499 if (!arg) 500 return NULL; 501 return format_expr(arg); 502 } 503 504 buf[0] = '\0'; 505 p = format; 506 out = buf; 507 while (*p) { 508 if (*p == '$') { 509 p++; 510 param = strtol(p, (char **)&p, 10); 511 arg = get_argument_from_call_expr(call->args, param); 512 if (!arg) 513 return NULL; 514 param = get_arg_number(arg); 515 if (param >= 0) { 516 ret = snprintf(out, buf + sizeof(buf) - out, "$%ld", param); 517 out += ret; 518 if (out >= buf + sizeof(buf)) 519 return NULL; 520 } else if (get_implied_value(arg, &sval)) { 521 ret = snprintf(out, buf + sizeof(buf) - out, "%s", sval_to_str(sval)); 522 out += ret; 523 if (out >= buf + sizeof(buf)) 524 return NULL; 525 } else { 526 return NULL; 527 } 528 } 529 *out = *p; 530 p++; 531 out++; 532 } 533 if (buf[0] == '\0') 534 return NULL; 535 *out = '\0'; 536 return alloc_sname(buf); 537 } 538 539 static char *buf_size_recipe; 540 static int db_buf_size_callback(void *unused, int argc, char **argv, char **azColName) 541 { 542 if (argc != 1) 543 return 0; 544 545 if (!buf_size_recipe) 546 buf_size_recipe = alloc_sname(argv[0]); 547 else if (strcmp(buf_size_recipe, argv[0]) != 0) 548 buf_size_recipe = alloc_sname("invalid"); 549 return 0; 550 } 551 552 static char *get_allocation_recipe_from_call(struct expression *expr) 553 { 554 struct symbol *sym; 555 static char sql_filter[1024]; 556 int i; 557 558 if (is_fake_call(expr)) 559 return NULL; 560 expr = strip_expr(expr); 561 if (expr->fn->type != EXPR_SYMBOL) 562 return NULL; 563 sym = expr->fn->symbol; 564 if (!sym) 565 return NULL; 566 567 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) { 568 if (strcmp(sym->ident->name, alloc_functions[i].func) == 0) { 569 char buf[32]; 570 571 snprintf(buf, sizeof(buf), "$%d", alloc_functions[i].param); 572 buf_size_recipe = alloc_sname(buf); 573 return swap_format(expr, buf_size_recipe); 574 } 575 } 576 577 if (sym->ctype.modifiers & MOD_STATIC) { 578 snprintf(sql_filter, 1024, "file = '%s' and function = '%s';", 579 get_filename(), sym->ident->name); 580 } else { 581 snprintf(sql_filter, 1024, "function = '%s' and static = 0;", 582 sym->ident->name); 583 } 584 585 buf_size_recipe = NULL; 586 run_sql(db_buf_size_callback, NULL, 587 "select value from return_states where type=%d and %s", 588 BUF_SIZE, sql_filter); 589 if (!buf_size_recipe || strcmp(buf_size_recipe, "invalid") == 0) 590 return NULL; 591 /* Known sizes should be handled in smatch_buf_size.c */ 592 if (!strchr(buf_size_recipe, '$')) 593 return NULL; 594 return swap_format(expr, buf_size_recipe); 595 } 596 597 static void match_call_assignment(struct expression *expr) 598 { 599 char *sname; 600 601 sname = get_allocation_recipe_from_call(expr->right); 602 if (!sname) 603 return; 604 set_state_expr(my_id, expr->left, alloc_state_sname(sname)); 605 } 606 607 const char *get_allocation_math(struct expression *expr) 608 { 609 struct expression *tmp; 610 struct smatch_state *state; 611 int cnt = 0; 612 613 expr = strip_expr(expr); 614 while ((tmp = get_assigned_expr(expr))) { 615 if (cnt++ > 5) /* assignments to self cause infinite loops */ 616 break; 617 expr = strip_expr(tmp); 618 } 619 if (!expr) 620 return NULL; 621 622 if (expr->type == EXPR_CALL) 623 return get_allocation_recipe_from_call(expr); 624 625 state = get_state_expr(my_id, expr); 626 if (!state || !state->data) 627 return NULL; 628 629 return state->name; 630 } 631 632 void register_parse_call_math(int id) 633 { 634 int i; 635 636 my_id = id; 637 638 set_dynamic_states(my_id); 639 640 for (i = 0; i < ARRAY_SIZE(alloc_functions); i++) 641 add_function_assign_hook(alloc_functions[i].func, &match_alloc, 642 INT_PTR(alloc_functions[i].param)); 643 add_hook(&match_call_assignment, CALL_ASSIGNMENT_HOOK); 644 } 645 646