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