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, 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 (__in_fake_struct_assign)
 437                 return;
 438         if (expr->op != '=')
 439                 return;
 440
 441         type = get_type(expr->left);
 442         if (!type || type->type != SYM_BASETYPE)
 443                 return;
 444
 445         left = get_constraint_str(expr->left);
 446         if (!left)
 447                 return;
 448         right = get_constraint_str(expr->right);
 449         if (!right)
 450                 goto free;
 451         if (!has_constraint(expr->right, right))
 452                 return;
 453         sql_copy_constraint_required(left, right);
 454 free:
 455         free_string(right);
 456         free_string(left);
 457 }
 458
 459 void register_constraints_required(int id)
 460 {
 461         my_id = id;
 462
 463         set_dynamic_states(my_id);
 464         add_hook(&match_assign_size, ASSIGNMENT_HOOK);
 465         add_hook(&match_assign_data, ASSIGNMENT_HOOK);
 466         add_hook(&match_assign_has_buf_comparison, ASSIGNMENT_HOOK);
 467
 468         add_hook(&match_assign_ARRAY_SIZE, ASSIGNMENT_HOOK);
 469         add_hook(&match_assign_ARRAY_SIZE, GLOBAL_ASSIGNMENT_HOOK);
 470         add_hook(&match_assign_buf_comparison, ASSIGNMENT_HOOK);
 471         add_hook(&match_assign_constraint, ASSIGNMENT_HOOK);
 472
 473         add_allocation_function("malloc", &match_alloc, 0);
 474         add_allocation_function("memdup", &match_alloc, 1);
 475         add_allocation_function("realloc", &match_alloc, 1);
 476         add_allocation_function("realloc", &match_calloc, 0);
 477         if (option_project == PROJ_KERNEL) {
 478                 add_allocation_function("kmalloc", &match_alloc, 0);
 479                 add_allocation_function("kzalloc", &match_alloc, 0);
 480                 add_allocation_function("vmalloc", &match_alloc, 0);
 481                 add_allocation_function("__vmalloc", &match_alloc, 0);
 482                 add_allocation_function("vzalloc", &match_alloc, 0);
 483                 add_allocation_function("sock_kmalloc", &match_alloc, 1);
 484                 add_allocation_function("kmemdup", &match_alloc, 1);
 485                 add_allocation_function("kmemdup_user", &match_alloc, 1);
 486                 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
 487                 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
 488                 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
 489                 add_allocation_function("devm_kmalloc", &match_alloc, 1);
 490                 add_allocation_function("devm_kzalloc", &match_alloc, 1);
 491                 add_allocation_function("kcalloc", &match_calloc, 0);
 492                 add_allocation_function("kmalloc_array", &match_calloc, 0);
 493                 add_allocation_function("devm_kcalloc", &match_calloc, 1);
 494                 add_allocation_function("krealloc", &match_alloc, 1);
 495         }
 496 }