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
 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 = '%s' limit 1",
 423                 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 }