smatch_buf_size.c

   1 /*
   2  * smatch/smatch_buf_size.c
   3  *
   4  * Copyright (C) 2010 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 #include <stdlib.h>
  11 #include <errno.h>
  12 #include "parse.h"
  13 #include "smatch.h"
  14 #include "smatch_slist.h"
  15 #include "smatch_extra.h"
  16
  17 /*
  18  * This check has two smatch IDs.
  19  * my_size_id - used to store the size of arrays.
  20  * my_strlen_id - track the strlen() of buffers.
  21  */
  22
  23 static int my_size_id;
  24 static int my_strlen_id;
  25
  26 struct limiter {
  27         int buf_arg;
  28         int limit_arg;
  29 };
  30 static struct limiter b0_l2 = {0, 2};
  31
  32 static _Bool params_set[32];
  33
  34 static void set_undefined(struct sm_state *sm)
  35 {
  36         if (sm->state != &undefined)
  37                 set_state(sm->owner, sm->name, sm->sym, &undefined);
  38 }
  39
  40 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
  41 {
  42         char fullname[256];
  43         unsigned int size;
  44
  45         if (strncmp(key, "$$", 2))
  46                 return;
  47
  48         snprintf(fullname, 256, "%s%s", name, key + 2);
  49
  50         errno = 0;
  51         size = strtoul(value, NULL, 10);
  52         if (errno)
  53                 return;
  54
  55         set_state(my_size_id, fullname, sym, alloc_state_num(size));
  56 }
  57
  58 static int bytes_per_element(struct expression *expr)
  59 {
  60         struct symbol *type;
  61         int bpe;
  62
  63         if (expr->type == EXPR_STRING)
  64                 return 1;
  65         type = get_type(expr);
  66         if (!type)
  67                 return 0;
  68
  69         if (type->type != SYM_PTR && type->type != SYM_ARRAY)
  70                 return 0;
  71
  72         type = get_base_type(type);
  73         bpe = bits_to_bytes(type->bit_size);
  74
  75         if (bpe == -1) /* void pointer */
  76                 bpe = 1;
  77
  78         return bpe;
  79 }
  80
  81 static int bytes_to_elements(struct expression *expr, int bytes)
  82 {
  83         int bpe;
  84
  85         bpe = bytes_per_element(expr);
  86         if (bpe == 0)
  87                 return 0;
  88         return bytes / bpe;
  89 }
  90
  91 static int elements_to_bytes(struct expression *expr, int elements)
  92 {
  93         int bpe;
  94
  95         bpe = bytes_per_element(expr);
  96         return elements * bpe;
  97 }
  98
  99 static int get_initializer_size(struct expression *expr)
 100 {
 101         switch (expr->type) {
 102         case EXPR_STRING:
 103                 return expr->string->length;
 104         case EXPR_INITIALIZER: {
 105                 struct expression *tmp;
 106                 int i = 0;
 107                 int max = 0;
 108
 109                 FOR_EACH_PTR(expr->expr_list, tmp) {
 110                         if (tmp->type == EXPR_INDEX && tmp->idx_to > max)
 111                                 max = tmp->idx_to;
 112                         i++;
 113                 } END_FOR_EACH_PTR(tmp);
 114                 if (max)
 115                         return max + 1;
 116                 return i;
 117         }
 118         case EXPR_SYMBOL:
 119                 return get_array_size(expr);
 120         }
 121         return 0;
 122 }
 123
 124 static int db_size;
 125 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
 126 {
 127         if (db_size == 0)
 128                 db_size = atoi(argv[0]);
 129         else
 130                 db_size = -1;
 131         return 0;
 132 }
 133
 134 static int size_from_db(struct expression *expr)
 135 {
 136         int this_file_only = 0;
 137         char *name;
 138
 139         if (!option_spammy)
 140                 return 0;
 141
 142         name = get_member_name(expr);
 143         if (!name && is_static(expr)) {
 144                 name = get_variable_from_expr(expr, NULL);
 145                 this_file_only = 1;
 146         }
 147         if (!name)
 148                 return 0;
 149
 150         db_size = 0;
 151         run_sql(db_size_callback, "select size from type_size where type = '%s' and file = '%s'",
 152                         name, get_filename());
 153         if (db_size == -1)
 154                 return 0;
 155         if (db_size != 0)
 156                 return db_size;
 157         if (this_file_only)
 158                 return 0;
 159
 160         run_sql(db_size_callback, "select size from type_size where type = '%s'",
 161                         name);
 162
 163         if (db_size == -1)
 164                 db_size = 0;
 165
 166         return db_size;
 167 }
 168
 169 static int get_real_array_size(struct expression *expr)
 170 {
 171         struct symbol *type;
 172         int ret;
 173
 174         if (expr->type == EXPR_BINOP) /* array elements foo[5] */
 175                 return 0;
 176
 177         type = get_type(expr);
 178         if (!type || type->type != SYM_ARRAY)
 179                 return 0;
 180
 181         ret = get_expression_value(type->array_size);
 182         /* Dynamically sized array are -1 in sparse */
 183         if (ret <= 0)
 184                 return 0;
 185         /* People put one element arrays on the end of structs */
 186         if (ret == 1)
 187                 return 0;
 188
 189         return ret;
 190 }
 191
 192 static int get_size_from_initializer(struct expression *expr)
 193 {
 194         if (expr->type != EXPR_SYMBOL || !expr->symbol->initializer)
 195                 return 0;
 196         if (expr->symbol->initializer == expr) /* int a = a; */
 197                 return 0;
 198         return get_initializer_size(expr->symbol->initializer);
 199 }
 200
 201 static int get_stored_size_bytes(struct expression *expr)
 202 {
 203         struct smatch_state *state;
 204
 205         state = get_state_expr(my_size_id, expr);
 206         if (!state)
 207                 return 0;
 208         return PTR_INT(state->data);
 209 }
 210
 211 static int get_bytes_from_address(struct expression *expr)
 212 {
 213         struct symbol *type;
 214         int ret;
 215
 216         if (!option_spammy)
 217                 return 0;
 218         if (expr->type != EXPR_PREOP || expr->op != '&')
 219                 return 0;
 220         type = get_type(expr);
 221         if (!type)
 222                 return 0;
 223
 224         if (type->type == SYM_PTR)
 225                 type = get_base_type(type);
 226
 227         ret = bits_to_bytes(type->bit_size);
 228         if (ret == -1)
 229                 return 0;
 230         if (ret == 1)
 231                 return 0;  /* ignore char pointers */
 232
 233         return ret;
 234 }
 235
 236 static int get_size_from_strlen(struct expression *expr)
 237 {
 238         struct smatch_state *state;
 239         long long len;
 240
 241         state = get_state_expr(my_strlen_id, expr);
 242         if (!state || !state->data)
 243                 return 0;
 244         if (get_implied_max((struct expression *)state->data, &len))
 245                 return len + 1; /* add one because strlen doesn't include the NULL */
 246         return 0;
 247 }
 248
 249 static struct expression *remove_addr_fluff(struct expression *expr)
 250 {
 251         struct expression *tmp;
 252         long long val;
 253
 254         expr = strip_expr(expr);
 255
 256         /* remove '&' and '*' operations that cancel */
 257         while (expr->type == EXPR_PREOP && expr->op == '&') {
 258                 tmp = strip_expr(expr->unop);
 259                 if (tmp->type != EXPR_PREOP)
 260                         break;
 261                 if (tmp->op != '*')
 262                         break;
 263                 expr = strip_expr(tmp->unop);
 264         }
 265
 266         /* "foo + 0" is just "foo" */
 267         if (expr->type == EXPR_BINOP && expr->op == '+' &&
 268             get_value(expr->right, &val) && val == 0)
 269                 return expr->left;
 270
 271         return expr;
 272 }
 273
 274 int get_array_size_bytes(struct expression *expr)
 275 {
 276         int size;
 277
 278         expr = remove_addr_fluff(expr);
 279         if (!expr)
 280                 return 0;
 281
 282         /* strcpy(foo, "BAR"); */
 283         if (expr->type == EXPR_STRING)
 284                 return expr->string->length;
 285
 286         /* buf[4] */
 287         size = get_real_array_size(expr);
 288         if (size)
 289                 return elements_to_bytes(expr, size);
 290
 291         /* buf = malloc(1024); */
 292         size = get_stored_size_bytes(expr);
 293         if (size)
 294                 return size;
 295
 296         /* char *foo = "BAR" */
 297         size = get_size_from_initializer(expr);
 298         if (size)
 299                 return elements_to_bytes(expr, size);
 300
 301         size = get_bytes_from_address(expr);
 302         if (size)
 303                 return size;
 304
 305         /* if (strlen(foo) > 4) */
 306         size = get_size_from_strlen(expr);
 307         if (size)
 308                 return size;
 309
 310         return size_from_db(expr);
 311 }
 312
 313 int get_array_size(struct expression *expr)
 314 {
 315         int bytes;
 316
 317         bytes = get_array_size_bytes(expr);
 318         return bytes_to_elements(expr, bytes);
 319 }
 320
 321 static void match_strlen_condition(struct expression *expr)
 322 {
 323         struct expression *left;
 324         struct expression *right;
 325         struct expression *str = NULL;
 326         int strlen_left = 0;
 327         int strlen_right = 0;
 328         long long val;
 329         struct smatch_state *true_state = NULL;
 330         struct smatch_state *false_state = NULL;
 331
 332         if (expr->type != EXPR_COMPARE)
 333                 return;
 334         left = strip_expr(expr->left);
 335         right = strip_expr(expr->right);
 336
 337         if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
 338                 str = get_argument_from_call_expr(left->args, 0);
 339                 strlen_left = 1;
 340         }
 341         if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
 342                 str = get_argument_from_call_expr(right->args, 0);
 343                 strlen_right = 1;
 344         }
 345
 346         if (!strlen_left && !strlen_right)
 347                 return;
 348         if (strlen_left && strlen_right)
 349                 return;
 350
 351         if (strlen_left) {
 352                 if (!get_value(right, &val))
 353                         return;
 354         }
 355         if (strlen_right) {
 356                 if (!get_value(left, &val))
 357                         return;
 358         }
 359
 360         if (expr->op == SPECIAL_EQUAL) {
 361                 set_true_false_states_expr(my_size_id, str, alloc_state_num(val + 1), NULL);
 362                 return;
 363         }
 364         if (expr->op == SPECIAL_NOTEQUAL) {
 365                 set_true_false_states_expr(my_size_id, str, NULL, alloc_state_num(val + 1));
 366                 return;
 367         }
 368
 369         switch (expr->op) {
 370         case '<':
 371         case SPECIAL_UNSIGNED_LT:
 372                 if (strlen_left)
 373                         true_state = alloc_state_num(val);
 374                 else
 375                         false_state = alloc_state_num(val + 1);
 376                 break;
 377         case SPECIAL_LTE:
 378         case SPECIAL_UNSIGNED_LTE:
 379                 if (strlen_left)
 380                         true_state = alloc_state_num(val + 1);
 381                 else
 382                         false_state = alloc_state_num(val);
 383                 break;
 384         case SPECIAL_GTE:
 385         case SPECIAL_UNSIGNED_GTE:
 386                 if (strlen_left)
 387                         false_state = alloc_state_num(val);
 388                 else
 389                         true_state = alloc_state_num(val + 1);
 390                 break;
 391         case '>':
 392         case SPECIAL_UNSIGNED_GT:
 393                 if (strlen_left)
 394                         false_state = alloc_state_num(val + 1);
 395                 else
 396                         true_state = alloc_state_num(val);
 397                 break;
 398         }
 399         set_true_false_states_expr(my_size_id, str, true_state, false_state);
 400 }
 401
 402 static struct expression *strip_ampersands(struct expression *expr)
 403 {
 404         struct symbol *type;
 405
 406         if (expr->type != EXPR_PREOP)
 407                 return expr;
 408         if (expr->op != '&')
 409                 return expr;
 410         type = get_type(expr->unop);
 411         if (!type || type->type != SYM_ARRAY)
 412                 return expr;
 413         return expr->unop;
 414 }
 415
 416 static void match_array_assignment(struct expression *expr)
 417 {
 418         struct expression *left;
 419         struct expression *right;
 420         int array_size;
 421
 422         if (expr->op != '=')
 423                 return;
 424         left = strip_expr(expr->left);
 425         right = strip_expr(expr->right);
 426         right = strip_ampersands(right);
 427         array_size = get_array_size_bytes(right);
 428         if (array_size)
 429                 set_state_expr(my_size_id, left, alloc_state_num(array_size));
 430 }
 431
 432 static void info_record_alloction(struct expression *buffer, struct expression *size)
 433 {
 434         char *name;
 435         long long val;
 436
 437         if (!option_info)
 438                 return;
 439
 440         name = get_member_name(buffer);
 441         if (!name && is_static(buffer))
 442                 name = get_variable_from_expr(buffer, NULL);
 443         if (!name)
 444                 return;
 445         if (!get_implied_value(size, &val))
 446                 val = -1;
 447         sm_msg("info: '%s' allocated_buf_size %lld", name, val);
 448         free_string(name);
 449 }
 450
 451 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 452 {
 453         int size_arg = PTR_INT(_size_arg);
 454         struct expression *right;
 455         struct expression *arg;
 456         long long bytes;
 457
 458         right = strip_expr(expr->right);
 459         arg = get_argument_from_call_expr(right->args, size_arg);
 460
 461         info_record_alloction(expr->left, arg);
 462
 463         if (!get_implied_value(arg, &bytes))
 464                 return;
 465         set_state_expr(my_size_id, expr->left, alloc_state_num(bytes));
 466 }
 467
 468 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 469 {
 470         struct expression *right;
 471         struct expression *arg;
 472         long long elements;
 473         long long size;
 474
 475         right = strip_expr(expr->right);
 476         arg = get_argument_from_call_expr(right->args, 0);
 477         if (!get_implied_value(arg, &elements))
 478                 return;
 479         arg = get_argument_from_call_expr(right->args, 1);
 480         if (!get_implied_value(arg, &size))
 481                 return;
 482         set_state_expr(my_size_id, expr->left, alloc_state_num(elements * size));
 483 }
 484
 485 static void match_strlen(const char *fn, struct expression *expr, void *unused)
 486 {
 487         struct expression *right;
 488         struct expression *str;
 489         struct expression *len_expr;
 490         char *len_name;
 491         struct smatch_state *state;
 492
 493         right = strip_expr(expr->right);
 494         str = get_argument_from_call_expr(right->args, 0);
 495         len_expr = strip_expr(expr->left);
 496
 497         len_name = get_variable_from_expr(len_expr, NULL);
 498         if (!len_name)
 499                 return;
 500
 501         state = __alloc_smatch_state(0);
 502         state->name = len_name;
 503         state->data = len_expr;
 504         set_state_expr(my_strlen_id, str, state);
 505 }
 506
 507 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 508 {
 509         struct limiter *limiter = (struct limiter *)_limiter;
 510         struct expression *dest;
 511         struct expression *size_expr;
 512         long long size;
 513
 514         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 515         size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 516         if (!get_implied_max(size_expr, &size))
 517                 return;
 518         set_state_expr(my_size_id, dest, alloc_state_num(size));
 519 }
 520
 521 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 522 {
 523         struct expression fake_assign;
 524
 525         fake_assign.op = '=';
 526         fake_assign.left = get_argument_from_call_expr(expr->args, 0);
 527         fake_assign.right = get_argument_from_call_expr(expr->args, 1);
 528         match_array_assignment(&fake_assign);
 529 }
 530
 531 static void match_strndup(const char *fn, struct expression *expr, void *unused)
 532 {
 533         struct expression *fn_expr;
 534         struct expression *size_expr;
 535         long long size;
 536
 537         fn_expr = strip_expr(expr->right);
 538         size_expr = get_argument_from_call_expr(fn_expr->args, 1);
 539         if (!get_implied_max(size_expr, &size))
 540                 return;
 541
 542         /* It's easy to forget space for the NUL char */
 543         size++;
 544         set_state_expr(my_size_id, expr->left, alloc_state_num(size));
 545 }
 546
 547 static void match_call(struct expression *expr)
 548 {
 549         char *name;
 550         struct expression *arg;
 551         int bytes;
 552         int i;
 553
 554         name = get_fnptr_name(expr->fn);
 555         if (!name)
 556                 return;
 557
 558         i = 0;
 559         FOR_EACH_PTR(expr->args, arg) {
 560                 bytes = get_array_size_bytes(arg);
 561                 if (bytes > 1)
 562                         sm_msg("info: passes_buffer '%s' %d '$$' %d %s",
 563                                 name, i, bytes,
 564                                 is_static(expr->fn) ? "static" : "global");
 565                 i++;
 566         } END_FOR_EACH_PTR(arg);
 567
 568         free_string(name);
 569 }
 570
 571 static void struct_member_callback(char *fn, char *global_static, int param, char *printed_name, struct smatch_state *state)
 572 {
 573         if (state == &merged)
 574                 return;
 575         sm_msg("info: passes_buffer '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static);
 576 }
 577
 578 static void match_func_end(struct symbol *sym)
 579 {
 580         memset(params_set, 0, sizeof(params_set));
 581 }
 582
 583 void register_buf_size(int id)
 584 {
 585         my_size_id = id;
 586
 587         add_definition_db_callback(set_param_buf_size, BUF_SIZE);
 588
 589         add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
 590         add_function_assign_hook("calloc", &match_calloc, NULL);
 591         add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
 592         if (option_project == PROJ_KERNEL) {
 593                 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
 594                 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
 595                 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
 596                 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
 597                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 598                 add_function_assign_hook("kmalloc_array", &match_calloc, NULL);
 599                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 600                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 601                 add_function_assign_hook("sock_kmalloc", &match_alloc, INT_PTR(1));
 602                 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
 603                 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
 604         }
 605         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 606         add_hook(&match_strlen_condition, CONDITION_HOOK);
 607         add_function_assign_hook("strlen", &match_strlen, NULL);
 608
 609         add_function_assign_hook("strndup", match_strndup, NULL);
 610         if (option_project == PROJ_KERNEL)
 611                 add_function_assign_hook("kstrndup", match_strndup, NULL);
 612
 613         add_hook(&match_func_end, END_FUNC_HOOK);
 614         add_modification_hook(my_size_id, &set_undefined);
 615 }
 616
 617 void register_strlen(int id)
 618 {
 619         my_strlen_id = id;
 620         add_modification_hook(my_strlen_id, &set_undefined);
 621 }
 622
 623 void register_buf_size_late(int id)
 624 {
 625         add_function_hook("strlcpy", &match_limited, &b0_l2);
 626         add_function_hook("strlcat", &match_limited, &b0_l2);
 627         add_function_hook("memscan", &match_limited, &b0_l2);
 628
 629         add_function_hook("strcpy", &match_strcpy, NULL);
 630
 631         if (option_info) {
 632                 add_hook(&match_call, FUNCTION_CALL_HOOK);
 633                 add_member_info_callback(my_size_id, struct_member_callback);
 634         }
 635 }