smatch_constraints_required.c

   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)
 164 {
 165         struct expression *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         while ((tmp = get_assigned_expr(size))) {
 175                 size = strip_expr(tmp);
 176                 if (cnt++ > 5)
 177                         break;
 178         }
 179
 180         if (handle_zero_size_arrays(pointer, size))
 181                 return;
 182
 183         if (size->type == EXPR_BINOP && size->op == '*') {
 184                 struct expression *mult_left, *mult_right;
 185
 186                 mult_left = strip_expr(size->left);
 187                 mult_right = strip_expr(size->right);
 188
 189                 if (get_implied_value(mult_left, &sval) &&
 190                     sval.value == bytes_per_element(pointer))
 191                         size = mult_right;
 192                 else if (get_implied_value(mult_right, &sval) &&
 193                     sval.value == bytes_per_element(pointer))
 194                         size = mult_left;
 195                 else
 196                         return;
 197         }
 198
 199         if (size->type == EXPR_BINOP && size->op == '+' &&
 200             get_implied_value(size->right, &sval) &&
 201             sval.value == 1)
 202                 save_constraint_required(pointer, SPECIAL_LTE, size->left);
 203         else
 204                 save_constraint_required(pointer, '<', size);
 205 }
 206
 207 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 208 {
 209         int size_arg = PTR_INT(_size_arg);
 210         struct expression *call, *arg;
 211
 212         call = strip_expr(expr->right);
 213         arg = get_argument_from_call_expr(call->args, size_arg);
 214
 215         match_alloc_helper(expr->left, arg);
 216 }
 217
 218 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
 219 {
 220         struct expression *pointer, *call, *size;
 221         struct expression *count = NULL;
 222         int start_arg = PTR_INT(_start_arg);
 223         sval_t sval;
 224
 225         pointer = strip_expr(expr->left);
 226         call = strip_expr(expr->right);
 227
 228         size = get_argument_from_call_expr(call->args, start_arg);
 229         if (get_implied_value(size, &sval) &&
 230             sval.value == bytes_per_element(pointer))
 231                 count = get_argument_from_call_expr(call->args, start_arg + 1);
 232         else {
 233                 size = get_argument_from_call_expr(call->args, start_arg + 1);
 234                 if (get_implied_value(size, &sval) &&
 235                     sval.value == bytes_per_element(pointer))
 236                         count = get_argument_from_call_expr(call->args, start_arg);
 237         }
 238
 239         if (!count)
 240                 return;
 241
 242         save_constraint_required(pointer, '<', count);
 243 }
 244
 245 static void add_allocation_function(const char *func, void *call_back, int param)
 246 {
 247         add_function_assign_hook(func, call_back, INT_PTR(param));
 248 }
 249
 250 static void match_assign_size(struct expression *expr)
 251 {
 252         struct smatch_state *state;
 253         char *data, *limit;
 254
 255         state = get_state_expr(my_id, expr->right);
 256         if (!state || !state->data)
 257                 return;
 258
 259         data = get_constraint_str(state->data);
 260         if (!data)
 261                 return;
 262
 263         limit = get_constraint_str(expr->left);
 264         if (!limit)
 265                 goto free_data;
 266
 267         sql_save_constraint_required(data, '<', limit);
 268
 269         free_string(limit);
 270 free_data:
 271         free_string(data);
 272 }
 273
 274 static void match_assign_has_buf_comparison(struct expression *expr)
 275 {
 276         struct expression *size;
 277
 278         if (expr->op != '=')
 279                 return;
 280         if (expr->right->type == EXPR_CALL)
 281                 return;
 282         size = get_size_variable(expr->right);
 283         if (!size)
 284                 return;
 285         match_alloc_helper(expr->left, size);
 286 }
 287
 288 static void match_assign_data(struct expression *expr)
 289 {
 290         struct expression *right, *arg, *tmp;
 291         int i;
 292         int size_arg;
 293         int size_arg2 = -1;
 294
 295         if (expr->op != '=')
 296                 return;
 297
 298         /* Direct calls are handled else where (for now at least) */
 299         tmp = get_assigned_expr(expr->right);
 300         if (!tmp)
 301                 return;
 302
 303         right = strip_expr(tmp);
 304         if (right->type != EXPR_CALL)
 305                 return;
 306
 307         if (right->fn->type != EXPR_SYMBOL ||
 308             !right->fn->symbol ||
 309             !right->fn->symbol->ident)
 310                 return;
 311
 312         for (i = 0; i < ARRAY_SIZE(generic_allocator_table); i++) {
 313                 if (strcmp(right->fn->symbol->ident->name,
 314                            generic_allocator_table[i].func) == 0) {
 315                         size_arg = generic_allocator_table[i].param;
 316                         goto found;
 317                 }
 318         }
 319
 320         if (option_project != PROJ_KERNEL)
 321                 return;
 322
 323         for (i = 0; i < ARRAY_SIZE(kernel_allocator_table); i++) {
 324                 if (strcmp(right->fn->symbol->ident->name,
 325                            kernel_allocator_table[i].func) == 0) {
 326                         size_arg = kernel_allocator_table[i].param;
 327                         goto found;
 328                 }
 329         }
 330
 331         for (i = 0; i < ARRAY_SIZE(calloc_table); i++) {
 332                 if (strcmp(right->fn->symbol->ident->name,
 333                            calloc_table[i].func) == 0) {
 334                         size_arg = calloc_table[i].param;
 335                         size_arg2 = calloc_table[i].param2;
 336                         goto found;
 337                 }
 338         }
 339
 340         return;
 341
 342 found:
 343         arg = get_argument_from_call_expr(right->args, size_arg);
 344         match_alloc_helper(expr->left, arg);
 345         if (size_arg2 == -1)
 346                 return;
 347         arg = get_argument_from_call_expr(right->args, size_arg2);
 348         match_alloc_helper(expr->left, arg);
 349 }
 350
 351 static void match_assign_ARRAY_SIZE(struct expression *expr)
 352 {
 353         struct expression *array;
 354         char *data, *limit;
 355         const char *macro;
 356
 357         macro = get_macro_name(expr->right->pos);
 358         if (!macro || strcmp(macro, "ARRAY_SIZE") != 0)
 359                 return;
 360         array = strip_expr(expr->right);
 361         if (array->type != EXPR_BINOP || array->op != '+')
 362                 return;
 363         array = strip_expr(array->left);
 364         if (array->type != EXPR_BINOP || array->op != '/')
 365                 return;
 366         array = strip_expr(array->left);
 367         if (array->type != EXPR_SIZEOF)
 368                 return;
 369         array = strip_expr(array->cast_expression);
 370         if (array->type != EXPR_PREOP || array->op != '*')
 371                 return;
 372         array = strip_expr(array->unop);
 373
 374         data = get_constraint_str(array);
 375         limit = get_constraint_str(expr->left);
 376         if (!data || !limit)
 377                 goto free;
 378
 379         sql_save_constraint_required(data, '<', limit);
 380
 381 free:
 382         free_string(data);
 383         free_string(limit);
 384 }
 385
 386 static void match_assign_buf_comparison(struct expression *expr)
 387 {
 388         struct expression *pointer;
 389
 390         if (expr->op != '=')
 391                 return;
 392         pointer = get_array_variable(expr->right);
 393         if (!pointer)
 394                 return;
 395
 396         match_alloc_helper(pointer, expr->right);
 397 }
 398
 399 static int constraint_found(void *_found, int argc, char **argv, char **azColName)
 400 {
 401         int *found = _found;
 402
 403         *found = 1;
 404         return 0;
 405 }
 406
 407 static int has_constraint(struct expression *expr, const char *constraint)
 408 {
 409         int found = 0;
 410
 411         if (get_state_expr(my_id, expr))
 412                 return 1;
 413
 414         run_sql(constraint_found, &found,
 415                 "select data from constraints_required where bound = '%s' limit 1",
 416                 constraint);
 417
 418         return found;
 419 }
 420
 421 static void match_assign_constraint(struct expression *expr)
 422 {
 423         struct symbol *type;
 424         char *left, *right;
 425
 426         if (expr->op != '=')
 427                 return;
 428
 429         type = get_type(expr->left);
 430         if (!type || type->type != SYM_BASETYPE)
 431                 return;
 432
 433         left = get_constraint_str(expr->left);
 434         if (!left)
 435                 return;
 436         right = get_constraint_str(expr->right);
 437         if (!right)
 438                 goto free;
 439         if (!has_constraint(expr->right, right))
 440                 return;
 441         sql_copy_constraint_required(left, right);
 442 free:
 443         free_string(right);
 444         free_string(left);
 445 }
 446
 447 void register_constraints_required(int id)
 448 {
 449         my_id = id;
 450
 451         add_hook(&match_assign_size, ASSIGNMENT_HOOK);
 452         add_hook(&match_assign_data, ASSIGNMENT_HOOK);
 453         add_hook(&match_assign_has_buf_comparison, ASSIGNMENT_HOOK);
 454
 455         add_hook(&match_assign_ARRAY_SIZE, ASSIGNMENT_HOOK);
 456         add_hook(&match_assign_ARRAY_SIZE, GLOBAL_ASSIGNMENT_HOOK);
 457         add_hook(&match_assign_buf_comparison, ASSIGNMENT_HOOK);
 458         add_hook(&match_assign_constraint, ASSIGNMENT_HOOK);
 459
 460         add_allocation_function("malloc", &match_alloc, 0);
 461         add_allocation_function("memdup", &match_alloc, 1);
 462         add_allocation_function("realloc", &match_alloc, 1);
 463         add_allocation_function("realloc", &match_calloc, 0);
 464         if (option_project == PROJ_KERNEL) {
 465                 add_allocation_function("kmalloc", &match_alloc, 0);
 466                 add_allocation_function("kzalloc", &match_alloc, 0);
 467                 add_allocation_function("vmalloc", &match_alloc, 0);
 468                 add_allocation_function("__vmalloc", &match_alloc, 0);
 469                 add_allocation_function("vzalloc", &match_alloc, 0);
 470                 add_allocation_function("sock_kmalloc", &match_alloc, 1);
 471                 add_allocation_function("kmemdup", &match_alloc, 1);
 472                 add_allocation_function("kmemdup_user", &match_alloc, 1);
 473                 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
 474                 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
 475                 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
 476                 add_allocation_function("devm_kmalloc", &match_alloc, 1);
 477                 add_allocation_function("devm_kzalloc", &match_alloc, 1);
 478                 add_allocation_function("kcalloc", &match_calloc, 0);
 479                 add_allocation_function("kmalloc_array", &match_calloc, 0);
 480                 add_allocation_function("devm_kcalloc", &match_calloc, 1);
 481                 add_allocation_function("krealloc", &match_alloc, 1);
 482         }
 483 }