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_extra.h" 20 21 static int my_id; 22 23 struct allocator { 24 const char *func; 25 int param; 26 int param2; 27 }; 28 29 static struct allocator generic_allocator_table[] = { 30 {"malloc", 0}, 31 {"memdup", 1}, 32 {"realloc", 1}, 33 }; 34 35 static struct allocator kernel_allocator_table[] = { 36 {"kmalloc", 0}, 37 {"kzalloc", 0}, 38 {"vmalloc", 0}, 39 {"__vmalloc", 0}, 40 {"vzalloc", 0}, 41 {"sock_kmalloc", 1}, 42 {"kmemdup", 1}, 43 {"kmemdup_user", 1}, 44 {"dma_alloc_attrs", 1}, 45 {"pci_alloc_consistent", 1}, 46 {"pci_alloc_coherent", 1}, 47 {"devm_kmalloc", 1}, 48 {"devm_kzalloc", 1}, 49 {"krealloc", 1}, 50 }; 51 52 static struct allocator calloc_table[] = { 53 {"calloc", 0, 1}, 54 {"kcalloc", 0, 1}, 55 {"kmalloc_array", 0, 1}, 56 {"devm_kcalloc", 1, 2}, 57 }; 58 59 static int bytes_per_element(struct expression *expr) 60 { 61 struct symbol *type; 62 63 type = get_type(expr); 64 if (!type) 65 return 0; 66 67 if (type->type != SYM_PTR && type->type != SYM_ARRAY) 68 return 0; 69 70 type = get_base_type(type); 71 return type_bytes(type); 72 } 73 74 static void save_constraint_required(struct expression *pointer, int op, struct expression *constraint) 75 { 76 char *data, *limit; 77 78 data = get_constraint_str(pointer); 79 if (!data) 80 return; 81 82 limit = get_constraint_str(constraint); 83 if (!limit) { 84 // FIXME deal with <= also 85 if (op == '<') 86 set_state_expr(my_id, constraint, alloc_state_expr(pointer)); 87 goto free_data; 88 } 89 90 sql_save_constraint_required(data, op, limit); 91 92 free_string(limit); 93 free_data: 94 free_string(data); 95 } 96 97 static int handle_zero_size_arrays(struct expression *pointer, struct expression *size) 98 { 99 struct expression *left, *right; 100 struct symbol *type, *array, *array_type; 101 sval_t struct_size; 102 char *limit; 103 char data[128]; 104 105 if (size->type != EXPR_BINOP || size->op != '+') 106 return 0; 107 108 type = get_type(pointer); 109 if (!type || type->type != SYM_PTR) 110 return 0; 111 type = get_real_base_type(type); 112 if (!type || !type->ident || type->type != SYM_STRUCT) 113 return 0; 114 if (!last_member_is_resizable(type)) 115 return 0; 116 array = last_ptr_list((struct ptr_list *)type->symbol_list); 117 if (!array || !array->ident) 118 return 0; 119 array_type = get_real_base_type(array); 120 if (!array_type || array_type->type != SYM_ARRAY) 121 return 0; 122 array_type = get_real_base_type(array_type); 123 124 left = strip_expr(size->left); 125 right = strip_expr(size->right); 126 127 if (!get_implied_value(left, &struct_size)) 128 return 0; 129 if (struct_size.value != type_bytes(type)) 130 return 0; 131 132 if (right->type == EXPR_BINOP && right->op == '*') { 133 struct expression *mult_left, *mult_right; 134 sval_t sval; 135 136 mult_left = strip_expr(right->left); 137 mult_right = strip_expr(right->right); 138 139 if (get_implied_value(mult_left, &sval) && 140 sval.value == type_bytes(array_type)) 141 size = mult_right; 142 else if (get_implied_value(mult_right, &sval) && 143 sval.value == type_bytes(array_type)) 144 size = mult_left; 145 else 146 return 0; 147 } 148 149 snprintf(data, sizeof(data), "(struct %s)->%s", type->ident->name, array->ident->name); 150 limit = get_constraint_str(size); 151 if (!limit) { 152 set_state_expr(my_id, size, alloc_state_expr( 153 member_expression(deref_expression(pointer), '*', array->ident))); 154 return 1; 155 } 156 157 sql_save_constraint_required(data, '<', limit); 158 159 free_string(limit); 160 return 1; 161 } 162 163 static void match_alloc_helper(struct expression *pointer, struct expression *size, int recurse) 164 { 165 struct expression *size_orig, *tmp; 166 sval_t sval; 167 int cnt = 0; 168 169 pointer = strip_expr(pointer); 170 size = strip_expr(size); 171 if (!size || !pointer) 172 return; 173 174 size_orig = size; 175 if (recurse) { 176 while ((tmp = get_assigned_expr(size))) { 177 size = strip_expr(tmp); 178 if (cnt++ > 5) 179 break; 180 } 181 if (size != size_orig) { 182 match_alloc_helper(pointer, size, 0); 183 size = size_orig; 184 } 185 } 186 187 if (handle_zero_size_arrays(pointer, size)) 188 return; 189 190 if (size->type == EXPR_BINOP && size->op == '*') { 191 struct expression *mult_left, *mult_right; 192 193 mult_left = strip_expr(size->left); 194 mult_right = strip_expr(size->right); 195 196 if (get_implied_value(mult_left, &sval) && 197 sval.value == bytes_per_element(pointer)) 198 size = mult_right; 199 else if (get_implied_value(mult_right, &sval) && 200 sval.value == bytes_per_element(pointer)) 201 size = mult_left; 202 else 203 return; 204 } 205 206 if (size->type == EXPR_BINOP && size->op == '+' && 207 get_implied_value(size->right, &sval) && 208 sval.value == 1) 209 save_constraint_required(pointer, SPECIAL_LTE, size->left); 210 else 211 save_constraint_required(pointer, '<', size); 212 } 213 214 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg) 215 { 216 int size_arg = PTR_INT(_size_arg); 217 struct expression *call, *arg; 218 219 call = strip_expr(expr->right); 220 arg = get_argument_from_call_expr(call->args, size_arg); 221 222 match_alloc_helper(expr->left, arg, 1); 223 } 224 225 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg) 226 { 227 struct expression *pointer, *call, *size; 228 struct expression *count = NULL; 229 int start_arg = PTR_INT(_start_arg); 230 sval_t sval; 231 232 pointer = strip_expr(expr->left); 233 call = strip_expr(expr->right); 234 235 size = get_argument_from_call_expr(call->args, start_arg); 236 if (get_implied_value(size, &sval) && 237 sval.value == bytes_per_element(pointer)) 238 count = get_argument_from_call_expr(call->args, start_arg + 1); 239 else { 240 size = get_argument_from_call_expr(call->args, start_arg + 1); 241 if (get_implied_value(size, &sval) && 242 sval.value == bytes_per_element(pointer)) 243 count = get_argument_from_call_expr(call->args, start_arg); 244 } 245 246 if (!count) 247 return; 248 249 save_constraint_required(pointer, '<', count); 250 } 251 252 static void add_allocation_function(const char *func, void *call_back, int param) 253 { 254 add_function_assign_hook(func, call_back, INT_PTR(param)); 255 } 256 257 static void match_assign_size(struct expression *expr) 258 { 259 struct smatch_state *state; 260 char *data, *limit; 261 262 state = get_state_expr(my_id, expr->right); 263 if (!state || !state->data) 264 return; 265 266 data = get_constraint_str(state->data); 267 if (!data) 268 return; 269 270 limit = get_constraint_str(expr->left); 271 if (!limit) 272 goto free_data; 273 274 sql_save_constraint_required(data, '<', limit); 275 276 free_string(limit); 277 free_data: 278 free_string(data); 279 } 280 281 static void match_assign_has_buf_comparison(struct expression *expr) 282 { 283 struct expression *size; 284 int limit_type; 285 286 if (expr->op != '=') 287 return; 288 if (expr->right->type == EXPR_CALL) 289 return; 290 size = get_size_variable(expr->right, &limit_type); 291 if (!size) 292 return; 293 if (limit_type != ELEM_COUNT) 294 return; 295 match_alloc_helper(expr->left, size, 1); 296 } 297 298 static void match_assign_data(struct expression *expr) 299 { 300 struct expression *right, *arg, *tmp; 301 int i; 302 int size_arg; 303 int size_arg2 = -1; 304 305 if (expr->op != '=') 306 return; 307 308 /* Direct calls are handled else where (for now at least) */ 309 tmp = get_assigned_expr(expr->right); 310 if (!tmp) 311 return; 312 313 right = strip_expr(tmp); 314 if (right->type != EXPR_CALL) 315 return; 316 317 if (right->fn->type != EXPR_SYMBOL || 318 !right->fn->symbol || 319 !right->fn->symbol->ident) 320 return; 321 322 for (i = 0; i < ARRAY_SIZE(generic_allocator_table); i++) { 323 if (strcmp(right->fn->symbol->ident->name, 324 generic_allocator_table[i].func) == 0) { 325 size_arg = generic_allocator_table[i].param; 326 goto found; 327 } 328 } 329 330 if (option_project != PROJ_KERNEL) 331 return; 332 333 for (i = 0; i < ARRAY_SIZE(kernel_allocator_table); i++) { 334 if (strcmp(right->fn->symbol->ident->name, 335 kernel_allocator_table[i].func) == 0) { 336 size_arg = kernel_allocator_table[i].param; 337 goto found; 338 } 339 } 340 341 for (i = 0; i < ARRAY_SIZE(calloc_table); i++) { 342 if (strcmp(right->fn->symbol->ident->name, 343 calloc_table[i].func) == 0) { 344 size_arg = calloc_table[i].param; 345 size_arg2 = calloc_table[i].param2; 346 goto found; 347 } 348 } 349 350 return; 351 352 found: 353 arg = get_argument_from_call_expr(right->args, size_arg); 354 match_alloc_helper(expr->left, arg, 1); 355 if (size_arg2 == -1) 356 return; 357 arg = get_argument_from_call_expr(right->args, size_arg2); 358 match_alloc_helper(expr->left, arg, 1); 359 } 360 361 static void match_assign_ARRAY_SIZE(struct expression *expr) 362 { 363 struct expression *array; 364 char *data, *limit; 365 const char *macro; 366 367 macro = get_macro_name(expr->right->pos); 368 if (!macro || strcmp(macro, "ARRAY_SIZE") != 0) 369 return; 370 array = strip_expr(expr->right); 371 if (array->type != EXPR_BINOP || array->op != '+') 372 return; 373 array = strip_expr(array->left); 374 if (array->type != EXPR_BINOP || array->op != '/') 375 return; 376 array = strip_expr(array->left); 377 if (array->type != EXPR_SIZEOF) 378 return; 379 array = strip_expr(array->cast_expression); 380 if (array->type != EXPR_PREOP || array->op != '*') 381 return; 382 array = strip_expr(array->unop); 383 384 data = get_constraint_str(array); 385 limit = get_constraint_str(expr->left); 386 if (!data || !limit) 387 goto free; 388 389 sql_save_constraint_required(data, '<', limit); 390 391 free: 392 free_string(data); 393 free_string(limit); 394 } 395 396 static void match_assign_buf_comparison(struct expression *expr) 397 { 398 struct expression *pointer; 399 400 if (expr->op != '=') 401 return; 402 pointer = get_array_variable(expr->right); 403 if (!pointer) 404 return; 405 406 match_alloc_helper(pointer, expr->right, 1); 407 } 408 409 static int constraint_found(void *_found, int argc, char **argv, char **azColName) 410 { 411 int *found = _found; 412 413 *found = 1; 414 return 0; 415 } 416 417 static int has_constraint(struct expression *expr, const char *constraint) 418 { 419 int found = 0; 420 421 if (get_state_expr(my_id, expr)) 422 return 1; 423 424 run_sql(constraint_found, &found, 425 "select data from constraints_required where bound = '%q' limit 1", 426 escape_newlines(constraint)); 427 428 return found; 429 } 430 431 static void match_assign_constraint(struct expression *expr) 432 { 433 struct symbol *type; 434 char *left, *right; 435 436 if (expr->op != '=') 437 return; 438 439 type = get_type(expr->left); 440 if (!type || type->type != SYM_BASETYPE) 441 return; 442 443 left = get_constraint_str(expr->left); 444 if (!left) 445 return; 446 right = get_constraint_str(expr->right); 447 if (!right) 448 goto free; 449 if (!has_constraint(expr->right, right)) 450 return; 451 sql_copy_constraint_required(left, right); 452 free: 453 free_string(right); 454 free_string(left); 455 } 456 457 void register_constraints_required(int id) 458 { 459 my_id = id; 460 461 set_dynamic_states(my_id); 462 add_hook(&match_assign_size, ASSIGNMENT_HOOK); 463 add_hook(&match_assign_data, ASSIGNMENT_HOOK); 464 add_hook(&match_assign_has_buf_comparison, ASSIGNMENT_HOOK); 465 466 add_hook(&match_assign_ARRAY_SIZE, ASSIGNMENT_HOOK); 467 add_hook(&match_assign_ARRAY_SIZE, GLOBAL_ASSIGNMENT_HOOK); 468 add_hook(&match_assign_buf_comparison, ASSIGNMENT_HOOK); 469 add_hook(&match_assign_constraint, ASSIGNMENT_HOOK); 470 471 add_allocation_function("malloc", &match_alloc, 0); 472 add_allocation_function("memdup", &match_alloc, 1); 473 add_allocation_function("realloc", &match_alloc, 1); 474 add_allocation_function("realloc", &match_calloc, 0); 475 if (option_project == PROJ_KERNEL) { 476 add_allocation_function("kmalloc", &match_alloc, 0); 477 add_allocation_function("kzalloc", &match_alloc, 0); 478 add_allocation_function("vmalloc", &match_alloc, 0); 479 add_allocation_function("__vmalloc", &match_alloc, 0); 480 add_allocation_function("vzalloc", &match_alloc, 0); 481 add_allocation_function("sock_kmalloc", &match_alloc, 1); 482 add_allocation_function("kmemdup", &match_alloc, 1); 483 add_allocation_function("kmemdup_user", &match_alloc, 1); 484 add_allocation_function("dma_alloc_attrs", &match_alloc, 1); 485 add_allocation_function("pci_alloc_consistent", &match_alloc, 1); 486 add_allocation_function("pci_alloc_coherent", &match_alloc, 1); 487 add_allocation_function("devm_kmalloc", &match_alloc, 1); 488 add_allocation_function("devm_kzalloc", &match_alloc, 1); 489 add_allocation_function("kcalloc", &match_calloc, 0); 490 add_allocation_function("kmalloc_array", &match_calloc, 0); 491 add_allocation_function("devm_kcalloc", &match_calloc, 1); 492 add_allocation_function("krealloc", &match_alloc, 1); 493 } 494 } 495