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 285 if (expr->op != '=') 286 return; 287 if (expr->right->type == EXPR_CALL) 288 return; 289 size = get_size_variable(expr->right); 290 if (!size) 291 return; 292 match_alloc_helper(expr->left, size, 1); 293 } 294 295 static void match_assign_data(struct expression *expr) 296 { 297 struct expression *right, *arg, *tmp; 298 int i; 299 int size_arg; 300 int size_arg2 = -1; 301 302 if (expr->op != '=') 303 return; 304 305 /* Direct calls are handled else where (for now at least) */ 306 tmp = get_assigned_expr(expr->right); 307 if (!tmp) 308 return; 309 310 right = strip_expr(tmp); 311 if (right->type != EXPR_CALL) 312 return; 313 314 if (right->fn->type != EXPR_SYMBOL || 315 !right->fn->symbol || 316 !right->fn->symbol->ident) 317 return; 318 319 for (i = 0; i < ARRAY_SIZE(generic_allocator_table); i++) { 320 if (strcmp(right->fn->symbol->ident->name, 321 generic_allocator_table[i].func) == 0) { 322 size_arg = generic_allocator_table[i].param; 323 goto found; 324 } 325 } 326 327 if (option_project != PROJ_KERNEL) 328 return; 329 330 for (i = 0; i < ARRAY_SIZE(kernel_allocator_table); i++) { 331 if (strcmp(right->fn->symbol->ident->name, 332 kernel_allocator_table[i].func) == 0) { 333 size_arg = kernel_allocator_table[i].param; 334 goto found; 335 } 336 } 337 338 for (i = 0; i < ARRAY_SIZE(calloc_table); i++) { 339 if (strcmp(right->fn->symbol->ident->name, 340 calloc_table[i].func) == 0) { 341 size_arg = calloc_table[i].param; 342 size_arg2 = calloc_table[i].param2; 343 goto found; 344 } 345 } 346 347 return; 348 349 found: 350 arg = get_argument_from_call_expr(right->args, size_arg); 351 match_alloc_helper(expr->left, arg, 1); 352 if (size_arg2 == -1) 353 return; 354 arg = get_argument_from_call_expr(right->args, size_arg2); 355 match_alloc_helper(expr->left, arg, 1); 356 } 357 358 static void match_assign_ARRAY_SIZE(struct expression *expr) 359 { 360 struct expression *array; 361 char *data, *limit; 362 const char *macro; 363 364 macro = get_macro_name(expr->right->pos); 365 if (!macro || strcmp(macro, "ARRAY_SIZE") != 0) 366 return; 367 array = strip_expr(expr->right); 368 if (array->type != EXPR_BINOP || array->op != '+') 369 return; 370 array = strip_expr(array->left); 371 if (array->type != EXPR_BINOP || array->op != '/') 372 return; 373 array = strip_expr(array->left); 374 if (array->type != EXPR_SIZEOF) 375 return; 376 array = strip_expr(array->cast_expression); 377 if (array->type != EXPR_PREOP || array->op != '*') 378 return; 379 array = strip_expr(array->unop); 380 381 data = get_constraint_str(array); 382 limit = get_constraint_str(expr->left); 383 if (!data || !limit) 384 goto free; 385 386 sql_save_constraint_required(data, '<', limit); 387 388 free: 389 free_string(data); 390 free_string(limit); 391 } 392 393 static void match_assign_buf_comparison(struct expression *expr) 394 { 395 struct expression *pointer; 396 397 if (expr->op != '=') 398 return; 399 pointer = get_array_variable(expr->right); 400 if (!pointer) 401 return; 402 403 match_alloc_helper(pointer, expr->right, 1); 404 } 405 406 static int constraint_found(void *_found, int argc, char **argv, char **azColName) 407 { 408 int *found = _found; 409 410 *found = 1; 411 return 0; 412 } 413 414 static int has_constraint(struct expression *expr, const char *constraint) 415 { 416 int found = 0; 417 418 if (get_state_expr(my_id, expr)) 419 return 1; 420 421 run_sql(constraint_found, &found, 422 "select data from constraints_required where bound = '%q' limit 1", 423 escape_newlines(constraint)); 424 425 return found; 426 } 427 428 static void match_assign_constraint(struct expression *expr) 429 { 430 struct symbol *type; 431 char *left, *right; 432 433 if (expr->op != '=') 434 return; 435 436 type = get_type(expr->left); 437 if (!type || type->type != SYM_BASETYPE) 438 return; 439 440 left = get_constraint_str(expr->left); 441 if (!left) 442 return; 443 right = get_constraint_str(expr->right); 444 if (!right) 445 goto free; 446 if (!has_constraint(expr->right, right)) 447 return; 448 sql_copy_constraint_required(left, right); 449 free: 450 free_string(right); 451 free_string(left); 452 } 453 454 void register_constraints_required(int id) 455 { 456 my_id = id; 457 458 add_hook(&match_assign_size, ASSIGNMENT_HOOK); 459 add_hook(&match_assign_data, ASSIGNMENT_HOOK); 460 add_hook(&match_assign_has_buf_comparison, ASSIGNMENT_HOOK); 461 462 add_hook(&match_assign_ARRAY_SIZE, ASSIGNMENT_HOOK); 463 add_hook(&match_assign_ARRAY_SIZE, GLOBAL_ASSIGNMENT_HOOK); 464 add_hook(&match_assign_buf_comparison, ASSIGNMENT_HOOK); 465 add_hook(&match_assign_constraint, ASSIGNMENT_HOOK); 466 467 add_allocation_function("malloc", &match_alloc, 0); 468 add_allocation_function("memdup", &match_alloc, 1); 469 add_allocation_function("realloc", &match_alloc, 1); 470 add_allocation_function("realloc", &match_calloc, 0); 471 if (option_project == PROJ_KERNEL) { 472 add_allocation_function("kmalloc", &match_alloc, 0); 473 add_allocation_function("kzalloc", &match_alloc, 0); 474 add_allocation_function("vmalloc", &match_alloc, 0); 475 add_allocation_function("__vmalloc", &match_alloc, 0); 476 add_allocation_function("vzalloc", &match_alloc, 0); 477 add_allocation_function("sock_kmalloc", &match_alloc, 1); 478 add_allocation_function("kmemdup", &match_alloc, 1); 479 add_allocation_function("kmemdup_user", &match_alloc, 1); 480 add_allocation_function("dma_alloc_attrs", &match_alloc, 1); 481 add_allocation_function("pci_alloc_consistent", &match_alloc, 1); 482 add_allocation_function("pci_alloc_coherent", &match_alloc, 1); 483 add_allocation_function("devm_kmalloc", &match_alloc, 1); 484 add_allocation_function("devm_kzalloc", &match_alloc, 1); 485 add_allocation_function("kcalloc", &match_calloc, 0); 486 add_allocation_function("kmalloc_array", &match_calloc, 0); 487 add_allocation_function("devm_kcalloc", &match_calloc, 1); 488 add_allocation_function("krealloc", &match_alloc, 1); 489 } 490 } 491