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 /* 19 * The point here is to store that a buffer has x bytes even if we don't know 20 * the value of x. 21 * 22 */ 23 24 #include "smatch.h" 25 #include "smatch_extra.h" 26 #include "smatch_slist.h" 27 28 static int size_id; 29 static int link_id; 30 31 /* 32 * We need this for code which does: 33 * 34 * if (size) 35 * foo = malloc(size); 36 * 37 * We want to record that the size of "foo" is "size" even after the merge. 38 * 39 */ 40 static struct smatch_state *unmatched_state(struct sm_state *sm) 41 { 42 struct expression *size_expr; 43 sval_t sval; 44 45 if (!sm->state->data) 46 return &undefined; 47 size_expr = sm->state->data; 48 if (!get_implied_value(size_expr, &sval) || sval.value != 0) 49 return &undefined; 50 return sm->state; 51 } 52 53 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2) 54 { 55 struct expression *expr1, *expr2; 56 57 expr1 = s1->data; 58 expr2 = s2->data; 59 60 if (expr1 && expr2 && expr_equiv(expr1, expr2)) 61 return s1; 62 return &merged; 63 } 64 65 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr) 66 { 67 struct expression *expr; 68 struct sm_state *tmp; 69 70 expr = sm->state->data; 71 if (expr) { 72 set_state_expr(size_id, expr, &undefined); 73 set_state(link_id, sm->name, sm->sym, &undefined); 74 return; 75 } 76 77 FOR_EACH_PTR(sm->possible, tmp) { 78 expr = tmp->state->data; 79 if (expr) 80 set_state_expr(size_id, expr, &undefined); 81 } END_FOR_EACH_PTR(tmp); 82 set_state(link_id, sm->name, sm->sym, &undefined); 83 } 84 85 static struct smatch_state *alloc_expr_state(struct expression *expr) 86 { 87 struct smatch_state *state; 88 char *name; 89 90 state = __alloc_smatch_state(0); 91 expr = strip_expr(expr); 92 name = expr_to_str(expr); 93 state->name = alloc_sname(name); 94 free_string(name); 95 state->data = expr; 96 return state; 97 } 98 99 static int bytes_per_element(struct expression *expr) 100 { 101 struct symbol *type; 102 103 type = get_type(expr); 104 if (!type) 105 return 0; 106 107 if (type->type != SYM_PTR && type->type != SYM_ARRAY) 108 return 0; 109 110 type = get_base_type(type); 111 return type_bytes(type); 112 } 113 114 static void db_save_type_links(struct expression *array, struct expression *size) 115 { 116 const char *array_name; 117 118 array_name = get_data_info_name(array); 119 if (!array_name) 120 array_name = ""; 121 sql_insert_data_info(size, ARRAY_LEN, array_name); 122 } 123 124 static void match_alloc_helper(struct expression *pointer, struct expression *size) 125 { 126 struct expression *tmp; 127 struct sm_state *sm; 128 sval_t sval; 129 int cnt = 0; 130 131 pointer = strip_expr(pointer); 132 size = strip_expr(size); 133 if (!size || !pointer) 134 return; 135 136 while ((tmp = get_assigned_expr(size))) { 137 size = strip_expr(tmp); 138 if (cnt++ > 5) 139 break; 140 } 141 142 if (size->type == EXPR_BINOP && size->op == '*') { 143 struct expression *mult_left, *mult_right; 144 145 mult_left = strip_expr(size->left); 146 mult_right = strip_expr(size->right); 147 148 if (get_implied_value(mult_left, &sval) && 149 sval.value == bytes_per_element(pointer)) 150 size = mult_right; 151 else if (get_implied_value(mult_right, &sval) && 152 sval.value == bytes_per_element(pointer)) 153 size = mult_left; 154 else 155 return; 156 } 157 158 /* Only save links to variables, not fixed sizes */ 159 if (get_value(size, &sval)) 160 return; 161 162 db_save_type_links(pointer, size); 163 sm = set_state_expr(size_id, pointer, alloc_expr_state(size)); 164 if (!sm) 165 return; 166 set_state_expr(link_id, size, alloc_expr_state(pointer)); 167 } 168 169 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg) 170 { 171 int size_arg = PTR_INT(_size_arg); 172 struct expression *pointer, *call, *arg; 173 174 pointer = strip_expr(expr->left); 175 call = strip_expr(expr->right); 176 arg = get_argument_from_call_expr(call->args, size_arg); 177 match_alloc_helper(pointer, arg); 178 } 179 180 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg) 181 { 182 int start_arg = PTR_INT(_start_arg); 183 struct expression *pointer, *call, *arg; 184 struct sm_state *tmp; 185 sval_t sval; 186 187 pointer = strip_expr(expr->left); 188 call = strip_expr(expr->right); 189 arg = get_argument_from_call_expr(call->args, start_arg); 190 if (get_implied_value(arg, &sval) && 191 sval.value == bytes_per_element(pointer)) 192 arg = get_argument_from_call_expr(call->args, start_arg + 1); 193 194 db_save_type_links(pointer, arg); 195 tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg)); 196 if (!tmp) 197 return; 198 set_state_expr(link_id, arg, alloc_expr_state(pointer)); 199 } 200 201 struct expression *get_size_variable(struct expression *buf) 202 { 203 struct smatch_state *state; 204 205 state = get_state_expr(size_id, buf); 206 if (state) 207 return state->data; 208 return NULL; 209 } 210 211 struct expression *get_array_variable(struct expression *size) 212 { 213 struct smatch_state *state; 214 215 state = get_state_expr(link_id, size); 216 if (state) 217 return state->data; 218 return NULL; 219 } 220 221 static void array_check(struct expression *expr) 222 { 223 struct expression *array; 224 struct expression *size; 225 struct expression *offset; 226 char *array_str, *offset_str; 227 228 expr = strip_expr(expr); 229 if (!is_array(expr)) 230 return; 231 232 array = get_array_base(expr); 233 size = get_size_variable(array); 234 if (!size) 235 return; 236 offset = get_array_offset(expr); 237 if (!possible_comparison(size, SPECIAL_EQUAL, offset)) 238 return; 239 240 array_str = expr_to_str(array); 241 offset_str = expr_to_str(offset); 242 sm_warning("potentially one past the end of array '%s[%s]'", array_str, offset_str); 243 free_string(array_str); 244 free_string(offset_str); 245 } 246 247 struct db_info { 248 char *name; 249 int ret; 250 }; 251 252 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName) 253 { 254 struct db_info *info = _info; 255 256 /* 257 * If possible the limitters are tied to the struct they limit. If we 258 * aren't sure which struct they limit then we use them as limitters for 259 * everything. 260 */ 261 if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0) 262 info->ret = 1; 263 return 0; 264 } 265 266 static char *vsl_to_data_info_name(const char *name, struct var_sym_list *vsl) 267 { 268 struct var_sym *vs; 269 struct symbol *type; 270 static char buf[80]; 271 const char *p; 272 273 if (ptr_list_size((struct ptr_list *)vsl) != 1) 274 return NULL; 275 vs = first_ptr_list((struct ptr_list *)vsl); 276 277 type = get_real_base_type(vs->sym); 278 if (!type || type->type != SYM_PTR) 279 goto top_level_name; 280 type = get_real_base_type(type); 281 if (!type || type->type != SYM_STRUCT) 282 goto top_level_name; 283 if (!type->ident) 284 goto top_level_name; 285 286 p = name; 287 while ((name = strstr(p, "->"))) 288 p = name + 2; 289 290 snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p); 291 return alloc_sname(buf); 292 293 top_level_name: 294 if (!(vs->sym->ctype.modifiers & MOD_TOPLEVEL)) 295 return NULL; 296 if (vs->sym->ctype.modifiers & MOD_STATIC) 297 snprintf(buf, sizeof(buf),"static %s", name); 298 else 299 snprintf(buf, sizeof(buf),"global %s", name); 300 return alloc_sname(buf); 301 } 302 303 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl) 304 { 305 char *size_name; 306 char *array_name = get_data_info_name(array); 307 struct db_info db_info = {.name = array_name,}; 308 309 size_name = vsl_to_data_info_name(name, vsl); 310 if (!size_name) 311 return 0; 312 313 run_sql(db_limitter_callback, &db_info, 314 "select value from data_info where type = %d and data = '%s';", 315 ARRAY_LEN, size_name); 316 317 return db_info.ret; 318 } 319 320 static int known_access_ok_comparison(struct expression *expr) 321 { 322 struct expression *array; 323 struct expression *size; 324 struct expression *offset; 325 int comparison; 326 327 array = get_array_base(expr); 328 size = get_size_variable(array); 329 if (!size) 330 return 0; 331 offset = get_array_offset(expr); 332 comparison = get_comparison(size, offset); 333 if (comparison == '>' || comparison == SPECIAL_UNSIGNED_GT) 334 return 1; 335 336 return 0; 337 } 338 339 static int known_access_ok_numbers(struct expression *expr) 340 { 341 struct expression *array; 342 struct expression *offset; 343 sval_t max; 344 int size; 345 346 array = get_array_base(expr); 347 offset = get_array_offset(expr); 348 349 size = get_array_size(array); 350 if (size <= 0) 351 return 0; 352 353 get_absolute_max(offset, &max); 354 if (max.uvalue < size) 355 return 1; 356 return 0; 357 } 358 359 static void array_check_data_info(struct expression *expr) 360 { 361 struct expression *array; 362 struct expression *offset; 363 struct state_list *slist; 364 struct sm_state *sm; 365 struct compare_data *comp; 366 char *offset_name; 367 const char *equal_name = NULL; 368 369 expr = strip_expr(expr); 370 if (!is_array(expr)) 371 return; 372 373 if (known_access_ok_numbers(expr)) 374 return; 375 if (known_access_ok_comparison(expr)) 376 return; 377 378 array = get_array_base(expr); 379 offset = get_array_offset(expr); 380 offset_name = expr_to_var(offset); 381 if (!offset_name) 382 return; 383 slist = get_all_possible_equal_comparisons(offset); 384 if (!slist) 385 goto free; 386 387 FOR_EACH_PTR(slist, sm) { 388 comp = sm->state->data; 389 if (strcmp(comp->left_var, offset_name) == 0) { 390 if (db_var_is_array_limit(array, comp->right_var, comp->right_vsl)) { 391 equal_name = comp->right_var; 392 break; 393 } 394 } else if (strcmp(comp->right_var, offset_name) == 0) { 395 if (db_var_is_array_limit(array, comp->left_var, comp->left_vsl)) { 396 equal_name = comp->left_var; 397 break; 398 } 399 } 400 } END_FOR_EACH_PTR(sm); 401 402 if (equal_name) { 403 char *array_name = expr_to_str(array); 404 405 sm_warning("potential off by one '%s[]' limit '%s'", array_name, equal_name); 406 free_string(array_name); 407 } 408 409 free: 410 free_slist(&slist); 411 free_string(offset_name); 412 } 413 414 static void add_allocation_function(const char *func, void *call_back, int param) 415 { 416 add_function_assign_hook(func, call_back, INT_PTR(param)); 417 } 418 419 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args) 420 { 421 struct expression *arg; 422 struct expression *size; 423 static char buf[32]; 424 int i; 425 426 size = get_size_variable(array); 427 if (!size) 428 return NULL; 429 430 i = -1; 431 FOR_EACH_PTR(args, arg) { 432 i++; 433 if (arg == array) 434 continue; 435 if (!expr_equiv(arg, size)) 436 continue; 437 snprintf(buf, sizeof(buf), "==$%d", i); 438 return buf; 439 } END_FOR_EACH_PTR(arg); 440 441 return NULL; 442 } 443 444 static void match_call(struct expression *call) 445 { 446 struct expression *arg; 447 char *compare; 448 int param; 449 450 param = -1; 451 FOR_EACH_PTR(call->args, arg) { 452 param++; 453 if (!is_pointer(arg)) 454 continue; 455 compare = buf_size_param_comparison(arg, call->args); 456 if (!compare) 457 continue; 458 sql_insert_caller_info(call, ARRAY_LEN, param, "$", compare); 459 } END_FOR_EACH_PTR(arg); 460 } 461 462 static int get_param(int param, char **name, struct symbol **sym) 463 { 464 struct symbol *arg; 465 int i; 466 467 i = 0; 468 FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) { 469 /* 470 * this is a temporary hack to work around a bug (I think in sparse?) 471 * 2.6.37-rc1:fs/reiserfs/journal.o 472 * If there is a function definition without parameter name found 473 * after a function implementation then it causes a crash. 474 * int foo() {} 475 * int bar(char *); 476 */ 477 if (arg->ident->name < (char *)100) 478 continue; 479 if (i == param) { 480 *name = arg->ident->name; 481 *sym = arg; 482 return TRUE; 483 } 484 i++; 485 } END_FOR_EACH_PTR(arg); 486 487 return FALSE; 488 } 489 490 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value) 491 { 492 struct expression *array_expr; 493 struct expression *size_expr; 494 struct symbol *size_sym; 495 char *size_name; 496 long param; 497 struct sm_state *tmp; 498 499 if (strncmp(value, "==$", 3) != 0) 500 return; 501 param = strtol(value + 3, NULL, 10); 502 if (!get_param(param, &size_name, &size_sym)) 503 return; 504 array_expr = symbol_expression(array_sym); 505 size_expr = symbol_expression(size_sym); 506 507 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr)); 508 if (!tmp) 509 return; 510 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr)); 511 } 512 513 static void set_arraysize_arg(const char *array_name, struct symbol *array_sym, char *key, char *value) 514 { 515 struct expression *array_expr; 516 struct expression *size_expr; 517 struct symbol *size_sym; 518 char *size_name; 519 long param; 520 struct sm_state *tmp; 521 522 param = strtol(key, NULL, 10); 523 if (!get_param(param, &size_name, &size_sym)) 524 return; 525 array_expr = symbol_expression(array_sym); 526 size_expr = symbol_expression(size_sym); 527 528 tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr)); 529 if (!tmp) 530 return; 531 set_state_expr(link_id, size_expr, alloc_expr_state(array_expr)); 532 } 533 534 static void munge_start_states(struct statement *stmt) 535 { 536 struct state_list *slist = NULL; 537 struct sm_state *sm; 538 struct sm_state *poss; 539 540 FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) { 541 if (sm->state != &merged) 542 continue; 543 /* 544 * screw it. let's just assume that if one caller passes the 545 * size then they all do. 546 */ 547 FOR_EACH_PTR(sm->possible, poss) { 548 if (poss->state != &merged && 549 poss->state != &undefined) { 550 add_ptr_list(&slist, poss); 551 break; 552 } 553 } END_FOR_EACH_PTR(poss); 554 } END_FOR_EACH_SM(sm); 555 556 FOR_EACH_PTR(slist, sm) { 557 set_state(size_id, sm->name, sm->sym, sm->state); 558 } END_FOR_EACH_PTR(sm); 559 560 free_slist(&slist); 561 } 562 563 void register_buf_comparison(int id) 564 { 565 size_id = id; 566 567 add_unmatched_state_hook(size_id, &unmatched_state); 568 569 add_allocation_function("malloc", &match_alloc, 0); 570 add_allocation_function("memdup", &match_alloc, 1); 571 add_allocation_function("realloc", &match_alloc, 1); 572 if (option_project == PROJ_KERNEL) { 573 add_allocation_function("kmalloc", &match_alloc, 0); 574 add_allocation_function("kzalloc", &match_alloc, 0); 575 add_allocation_function("vmalloc", &match_alloc, 0); 576 add_allocation_function("__vmalloc", &match_alloc, 0); 577 add_allocation_function("sock_kmalloc", &match_alloc, 1); 578 add_allocation_function("kmemdup", &match_alloc, 1); 579 add_allocation_function("kmemdup_user", &match_alloc, 1); 580 add_allocation_function("dma_alloc_attrs", &match_alloc, 1); 581 add_allocation_function("pci_alloc_consistent", &match_alloc, 1); 582 add_allocation_function("pci_alloc_coherent", &match_alloc, 1); 583 add_allocation_function("devm_kmalloc", &match_alloc, 1); 584 add_allocation_function("devm_kzalloc", &match_alloc, 1); 585 add_allocation_function("kcalloc", &match_calloc, 0); 586 add_allocation_function("devm_kcalloc", &match_calloc, 1); 587 add_allocation_function("kmalloc_array", &match_calloc, 0); 588 add_allocation_function("krealloc", &match_alloc, 1); 589 } 590 591 add_hook(&array_check, OP_HOOK); 592 add_hook(&array_check_data_info, OP_HOOK); 593 594 add_hook(&match_call, FUNCTION_CALL_HOOK); 595 select_caller_info_hook(set_param_compare, ARRAY_LEN); 596 select_caller_info_hook(set_arraysize_arg, ARRAYSIZE_ARG); 597 add_hook(&munge_start_states, AFTER_DEF_HOOK); 598 } 599 600 void register_buf_comparison_links(int id) 601 { 602 link_id = id; 603 add_merge_hook(link_id, &merge_links); 604 add_modification_hook(link_id, &match_link_modify); 605 } 606