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 void set_undefined(struct sm_state *sm, struct expression *mod_expr)
  33 {
  34         if (sm->state != &undefined)
  35                 set_state(sm->owner, sm->name, sm->sym, &undefined);
  36 }
  37
  38 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
  39 {
  40         if (PTR_INT(s1->data) == PTR_INT(s2->data))
  41                 return s1;
  42         return &undefined;
  43 }
  44
  45 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
  46 {
  47         char fullname[256];
  48         unsigned int size;
  49
  50         if (strncmp(key, "$$", 2))
  51                 return;
  52
  53         snprintf(fullname, 256, "%s%s", name, key + 2);
  54
  55         errno = 0;
  56         size = strtoul(value, NULL, 10);
  57         if (errno)
  58                 return;
  59
  60         set_state(my_size_id, fullname, sym, alloc_state_num(size));
  61 }
  62
  63 static int bytes_per_element(struct expression *expr)
  64 {
  65         struct symbol *type;
  66         int bpe;
  67
  68         if (expr->type == EXPR_STRING)
  69                 return 1;
  70         type = get_type(expr);
  71         if (!type)
  72                 return 0;
  73
  74         if (type->type != SYM_PTR && type->type != SYM_ARRAY)
  75                 return 0;
  76
  77         type = get_base_type(type);
  78         bpe = bits_to_bytes(type->bit_size);
  79
  80         if (bpe == -1) /* void pointer */
  81                 bpe = 1;
  82
  83         return bpe;
  84 }
  85
  86 static int bytes_to_elements(struct expression *expr, int bytes)
  87 {
  88         int bpe;
  89
  90         bpe = bytes_per_element(expr);
  91         if (bpe == 0)
  92                 return 0;
  93         return bytes / bpe;
  94 }
  95
  96 static int elements_to_bytes(struct expression *expr, int elements)
  97 {
  98         int bpe;
  99
 100         bpe = bytes_per_element(expr);
 101         return elements * bpe;
 102 }
 103
 104 static int get_initializer_size(struct expression *expr)
 105 {
 106         switch (expr->type) {
 107         case EXPR_STRING:
 108                 return expr->string->length;
 109         case EXPR_INITIALIZER: {
 110                 struct expression *tmp;
 111                 int i = 0;
 112
 113                 FOR_EACH_PTR(expr->expr_list, tmp) {
 114                         if (tmp->type == EXPR_INDEX) {
 115                                 if (tmp->idx_to >= i)
 116                                         i = tmp->idx_to;
 117                                 else
 118                                         continue;
 119                         }
 120
 121                         i++;
 122                 } END_FOR_EACH_PTR(tmp);
 123                 return i;
 124         }
 125         case EXPR_SYMBOL:
 126                 return get_array_size(expr);
 127         }
 128         return 0;
 129 }
 130
 131 static int db_size;
 132 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
 133 {
 134         if (db_size == 0)
 135                 db_size = atoi(argv[0]);
 136         else
 137                 db_size = -1;
 138         return 0;
 139 }
 140
 141 static int size_from_db(struct expression *expr)
 142 {
 143         int this_file_only = 0;
 144         char *name;
 145
 146         if (!option_spammy)
 147                 return 0;
 148
 149         name = get_member_name(expr);
 150         if (!name && is_static(expr)) {
 151                 name = expr_to_var(expr);
 152                 this_file_only = 1;
 153         }
 154         if (!name)
 155                 return 0;
 156
 157         db_size = 0;
 158         run_sql(db_size_callback, "select size from type_size where type = '%s' and file = '%s'",
 159                         name, get_filename());
 160         if (db_size < 0)
 161                 return 0;
 162         if (db_size != 0)
 163                 return db_size;
 164         if (this_file_only)
 165                 return 0;
 166
 167         run_sql(db_size_callback, "select size from type_size where type = '%s'",
 168                         name);
 169
 170         if (db_size < 0)
 171                 db_size = 0;
 172
 173         return db_size;
 174 }
 175
 176 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
 177 {
 178         struct expression *call;
 179         sval_t sval;
 180
 181         if (expr->type != EXPR_ASSIGNMENT)
 182                 return;
 183         call = strip_expr(expr->right);
 184
 185         if (!parse_call_math(call, math, &sval))
 186                 return;
 187         set_state_expr(my_size_id, expr->left, alloc_state_num(sval.value));
 188 }
 189
 190 int get_real_array_size(struct expression *expr)
 191 {
 192         struct symbol *type;
 193         sval_t sval;
 194
 195         if (expr->type == EXPR_BINOP) /* array elements foo[5] */
 196                 return 0;
 197
 198         type = get_type(expr);
 199         if (!type || type->type != SYM_ARRAY)
 200                 return 0;
 201
 202         if (!get_implied_value(type->array_size, &sval))
 203                 return 0;
 204
 205         /* People put one element arrays on the end of structs */
 206         if (sval.value == 1)
 207                 return 0;
 208
 209         return sval.value;
 210 }
 211
 212 static int get_size_from_initializer(struct expression *expr)
 213 {
 214         if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
 215                 return 0;
 216         if (expr->symbol->initializer == expr) /* int a = a; */
 217                 return 0;
 218         return get_initializer_size(expr->symbol->initializer);
 219 }
 220
 221 static int get_stored_size_bytes(struct expression *expr)
 222 {
 223         struct smatch_state *state;
 224
 225         state = get_state_expr(my_size_id, expr);
 226         if (!state)
 227                 return 0;
 228         return PTR_INT(state->data);
 229 }
 230
 231 static int get_stored_size_bytes_min(struct expression *expr)
 232 {
 233         struct sm_state *sm, *tmp;
 234         int min = 0;
 235
 236         sm = get_sm_state_expr(my_size_id, expr);
 237         if (!sm)
 238                 return 0;
 239         FOR_EACH_PTR(sm->possible, tmp) {
 240                 if (PTR_INT(tmp->state->data) <= 0)
 241                         continue;
 242                 if (PTR_INT(tmp->state->data) < min)
 243                         min = PTR_INT(tmp->state->data);
 244         } END_FOR_EACH_PTR(tmp);
 245
 246         return min;
 247 }
 248
 249 static int get_bytes_from_address(struct expression *expr)
 250 {
 251         struct symbol *type;
 252         int ret;
 253
 254         if (!option_spammy)
 255                 return 0;
 256         if (expr->type != EXPR_PREOP || expr->op != '&')
 257                 return 0;
 258         type = get_type(expr);
 259         if (!type)
 260                 return 0;
 261
 262         if (type->type == SYM_PTR)
 263                 type = get_base_type(type);
 264
 265         ret = bits_to_bytes(type->bit_size);
 266         if (ret == -1)
 267                 return 0;
 268         if (ret == 1)
 269                 return 0;  /* ignore char pointers */
 270
 271         return ret;
 272 }
 273
 274 static int get_size_from_strlen(struct expression *expr)
 275 {
 276         struct smatch_state *state;
 277         sval_t len;
 278
 279         state = get_state_expr(my_strlen_id, expr);
 280         if (!state || !state->data)
 281                 return 0;
 282         if (!get_implied_max((struct expression *)state->data, &len))
 283                 return 0;
 284         if (sval_is_max(len))
 285                 return 0;
 286         if (len.uvalue > INT_MAX - 1 || len.value < 0)
 287                 return 0;
 288         return len.value + 1; /* add one because strlen doesn't include the NULL */
 289 }
 290
 291 static struct expression *remove_addr_fluff(struct expression *expr)
 292 {
 293         struct expression *tmp;
 294         sval_t sval;
 295
 296         expr = strip_expr(expr);
 297
 298         /* remove '&' and '*' operations that cancel */
 299         while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
 300                 tmp = strip_expr(expr->unop);
 301                 if (tmp->type != EXPR_PREOP)
 302                         break;
 303                 if (tmp->op != '*')
 304                         break;
 305                 expr = strip_expr(tmp->unop);
 306         }
 307
 308         if (!expr)
 309                 return NULL;
 310
 311         /* "foo + 0" is just "foo" */
 312         if (expr->type == EXPR_BINOP && expr->op == '+' &&
 313             get_value(expr->right, &sval) && sval.value == 0)
 314                 return expr->left;
 315
 316         return expr;
 317 }
 318
 319 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
 320 {
 321         struct symbol *tmp;
 322         int i;
 323
 324         i = 0;
 325         FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
 326                 if (i++ || !tmp->ident)
 327                         return 0;
 328                 if (tmp->ident == member)
 329                         return 1;
 330                 return 0;
 331         } END_FOR_EACH_PTR_REVERSE(tmp);
 332
 333         return 0;
 334 }
 335
 336 static int get_stored_size_end_struct_bytes(struct expression *expr)
 337 {
 338         struct symbol *type;
 339         char *name;
 340         struct symbol *sym;
 341         struct smatch_state *state;
 342         sval_t sval;
 343
 344         if (expr->type == EXPR_BINOP) /* array elements foo[5] */
 345                 return 0;
 346
 347         type = get_type(expr);
 348         if (!type || type->type != SYM_ARRAY)
 349                 return 0;
 350
 351         if (!get_implied_value(type->array_size, &sval))
 352                 return 0;
 353
 354         if (sval.value != 0 && sval.value != 1)
 355                 return 0;
 356
 357         name = expr_to_var_sym(expr, &sym);
 358         free_string(name);
 359         if (!sym || !sym->ident || !sym->ident->name)
 360                 return 0;
 361         if (!sym->bit_size)
 362                 return 0;
 363
 364         if (sym->type != SYM_NODE)
 365                 return 0;
 366
 367         state = get_state(my_size_id, sym->ident->name, sym);
 368         if (!state || !state->data)
 369                 return 0;
 370
 371         sym = get_real_base_type(sym);
 372         if (!sym || sym->type != SYM_PTR)
 373                 return 0;
 374         sym = get_real_base_type(sym);
 375         if (!sym || sym->type != SYM_STRUCT)
 376                 return 0;
 377         if (!is_last_member_of_struct(sym, expr->member))
 378                 return 0;
 379
 380         return PTR_INT(state->data) - bits_to_bytes(sym->bit_size) +
 381                 bits_to_bytes(type->bit_size);
 382 }
 383
 384 int get_array_size_bytes(struct expression *expr)
 385 {
 386         int size;
 387
 388         expr = remove_addr_fluff(expr);
 389         if (!expr)
 390                 return 0;
 391
 392         /* strcpy(foo, "BAR"); */
 393         if (expr->type == EXPR_STRING)
 394                 return expr->string->length;
 395
 396         /* buf[4] */
 397         size = get_real_array_size(expr);
 398         if (size)
 399                 return elements_to_bytes(expr, size);
 400
 401         /* buf = malloc(1024); */
 402         size = get_stored_size_bytes(expr);
 403         if (size)
 404                 return size;
 405
 406         size = get_stored_size_end_struct_bytes(expr);
 407         if (size)
 408                 return size;
 409
 410         /* char *foo = "BAR" */
 411         size = get_size_from_initializer(expr);
 412         if (size)
 413                 return elements_to_bytes(expr, size);
 414
 415         size = get_bytes_from_address(expr);
 416         if (size)
 417                 return size;
 418
 419         /* if (strlen(foo) > 4) */
 420         size = get_size_from_strlen(expr);
 421         if (size)
 422                 return size;
 423
 424         return size_from_db(expr);
 425 }
 426
 427 int get_array_size_bytes_min(struct expression *expr)
 428 {
 429         int size;
 430         int tmp;
 431
 432         size = get_array_size_bytes(expr);
 433
 434         tmp = get_stored_size_bytes_min(expr);
 435         if (size <= 0 || (tmp >= 1 && tmp < size))
 436                 size = tmp;
 437         return size;
 438 }
 439
 440 int get_array_size(struct expression *expr)
 441 {
 442         int bytes;
 443
 444         bytes = get_array_size_bytes(expr);
 445         return bytes_to_elements(expr, bytes);
 446 }
 447
 448 static void match_strlen_condition(struct expression *expr)
 449 {
 450         struct expression *left;
 451         struct expression *right;
 452         struct expression *str = NULL;
 453         int strlen_left = 0;
 454         int strlen_right = 0;
 455         sval_t sval;
 456         struct smatch_state *true_state = NULL;
 457         struct smatch_state *false_state = NULL;
 458
 459         if (expr->type != EXPR_COMPARE)
 460                 return;
 461         left = strip_expr(expr->left);
 462         right = strip_expr(expr->right);
 463
 464         if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
 465                 str = get_argument_from_call_expr(left->args, 0);
 466                 strlen_left = 1;
 467         }
 468         if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
 469                 str = get_argument_from_call_expr(right->args, 0);
 470                 strlen_right = 1;
 471         }
 472
 473         if (!strlen_left && !strlen_right)
 474                 return;
 475         if (strlen_left && strlen_right)
 476                 return;
 477
 478         if (strlen_left) {
 479                 if (!get_value(right, &sval))
 480                         return;
 481         }
 482         if (strlen_right) {
 483                 if (!get_value(left, &sval))
 484                         return;
 485         }
 486
 487         if (expr->op == SPECIAL_EQUAL) {
 488                 set_true_false_states_expr(my_size_id, str, alloc_state_num(sval.value + 1), NULL);
 489                 return;
 490         }
 491         if (expr->op == SPECIAL_NOTEQUAL) {
 492                 set_true_false_states_expr(my_size_id, str, NULL, alloc_state_num(sval.value + 1));
 493                 return;
 494         }
 495
 496         switch (expr->op) {
 497         case '<':
 498         case SPECIAL_UNSIGNED_LT:
 499                 if (strlen_left)
 500                         true_state = alloc_state_num(sval.value);
 501                 else
 502                         false_state = alloc_state_num(sval.value + 1);
 503                 break;
 504         case SPECIAL_LTE:
 505         case SPECIAL_UNSIGNED_LTE:
 506                 if (strlen_left)
 507                         true_state = alloc_state_num(sval.value + 1);
 508                 else
 509                         false_state = alloc_state_num(sval.value);
 510                 break;
 511         case SPECIAL_GTE:
 512         case SPECIAL_UNSIGNED_GTE:
 513                 if (strlen_left)
 514                         false_state = alloc_state_num(sval.value);
 515                 else
 516                         true_state = alloc_state_num(sval.value + 1);
 517                 break;
 518         case '>':
 519         case SPECIAL_UNSIGNED_GT:
 520                 if (strlen_left)
 521                         false_state = alloc_state_num(sval.value + 1);
 522                 else
 523                         true_state = alloc_state_num(sval.value);
 524                 break;
 525         }
 526         set_true_false_states_expr(my_size_id, str, true_state, false_state);
 527 }
 528
 529 static struct expression *strip_ampersands(struct expression *expr)
 530 {
 531         struct symbol *type;
 532
 533         if (expr->type != EXPR_PREOP)
 534                 return expr;
 535         if (expr->op != '&')
 536                 return expr;
 537         type = get_type(expr->unop);
 538         if (!type || type->type != SYM_ARRAY)
 539                 return expr;
 540         return expr->unop;
 541 }
 542
 543 static void match_array_assignment(struct expression *expr)
 544 {
 545         struct expression *left;
 546         struct expression *right;
 547         int array_size;
 548
 549         if (expr->op != '=')
 550                 return;
 551         left = strip_expr(expr->left);
 552         right = strip_expr(expr->right);
 553         right = strip_ampersands(right);
 554         array_size = get_array_size_bytes(right);
 555         if (array_size)
 556                 set_state_expr(my_size_id, left, alloc_state_num(array_size));
 557 }
 558
 559 static void info_record_alloction(struct expression *buffer, struct expression *size)
 560 {
 561         char *name;
 562         sval_t sval;
 563
 564         if (!option_info)
 565                 return;
 566
 567         name = get_member_name(buffer);
 568         if (!name && is_static(buffer))
 569                 name = expr_to_var(buffer);
 570         if (!name)
 571                 return;
 572         if (get_implied_value(size, &sval))
 573                 sql_insert_type_size(name, sval.value);
 574         else
 575                 sql_insert_type_size(name, -1);
 576
 577         free_string(name);
 578 }
 579
 580 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 581 {
 582         int size_arg = PTR_INT(_size_arg);
 583         struct expression *right;
 584         struct expression *arg;
 585         sval_t bytes;
 586
 587         right = strip_expr(expr->right);
 588         arg = get_argument_from_call_expr(right->args, size_arg);
 589
 590         info_record_alloction(expr->left, arg);
 591
 592         if (!get_implied_value(arg, &bytes))
 593                 return;
 594         set_state_expr(my_size_id, expr->left, alloc_state_num(bytes.value));
 595 }
 596
 597 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 598 {
 599         struct expression *right;
 600         struct expression *arg;
 601         sval_t elements;
 602         sval_t size;
 603
 604         right = strip_expr(expr->right);
 605         arg = get_argument_from_call_expr(right->args, 0);
 606         if (!get_implied_value(arg, &elements))
 607                 return;
 608         arg = get_argument_from_call_expr(right->args, 1);
 609         if (!get_implied_value(arg, &size))
 610                 return;
 611         set_state_expr(my_size_id, expr->left, alloc_state_num(elements.value * size.value));
 612 }
 613
 614 static void match_strlen(const char *fn, struct expression *expr, void *unused)
 615 {
 616         struct expression *right;
 617         struct expression *str;
 618         struct expression *len_expr;
 619         char *len_name;
 620         struct smatch_state *state;
 621
 622         right = strip_expr(expr->right);
 623         str = get_argument_from_call_expr(right->args, 0);
 624         len_expr = strip_expr(expr->left);
 625
 626         len_name = expr_to_var(len_expr);
 627         if (!len_name)
 628                 return;
 629
 630         state = __alloc_smatch_state(0);
 631         state->name = len_name;
 632         state->data = len_expr;
 633         set_state_expr(my_strlen_id, str, state);
 634 }
 635
 636 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 637 {
 638         struct limiter *limiter = (struct limiter *)_limiter;
 639         struct expression *dest;
 640         struct expression *size_expr;
 641         sval_t size;
 642
 643         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 644         size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 645         if (!get_implied_max(size_expr, &size))
 646                 return;
 647         set_state_expr(my_size_id, dest, alloc_state_num(size.value));
 648 }
 649
 650 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 651 {
 652         struct expression fake_assign;
 653
 654         fake_assign.op = '=';
 655         fake_assign.left = get_argument_from_call_expr(expr->args, 0);
 656         fake_assign.right = get_argument_from_call_expr(expr->args, 1);
 657         match_array_assignment(&fake_assign);
 658 }
 659
 660 static void match_strndup(const char *fn, struct expression *expr, void *unused)
 661 {
 662         struct expression *fn_expr;
 663         struct expression *size_expr;
 664         sval_t size;
 665
 666         fn_expr = strip_expr(expr->right);
 667         size_expr = get_argument_from_call_expr(fn_expr->args, 1);
 668         if (!get_implied_max(size_expr, &size))
 669                 return;
 670
 671         /* It's easy to forget space for the NUL char */
 672         size.value++;
 673         set_state_expr(my_size_id, expr->left, alloc_state_num(size.value));
 674 }
 675
 676 static void match_call(struct expression *expr)
 677 {
 678         struct expression *arg;
 679         int bytes;
 680         int i;
 681
 682         i = 0;
 683         FOR_EACH_PTR(expr->args, arg) {
 684                 bytes = get_array_size_bytes(arg);
 685                 if (bytes > 1) {
 686                         char buf[11];
 687
 688                         snprintf(buf, sizeof(buf), "%d", bytes);
 689                         sql_insert_caller_info(expr, BUF_SIZE, i, "$$", buf);
 690                 }
 691                 i++;
 692         } END_FOR_EACH_PTR(arg);
 693 }
 694
 695 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct smatch_state *state)
 696 {
 697         if (state == &merged)
 698                 return;
 699         sql_insert_caller_info(call, BUF_SIZE, param, printed_name, state->name);
 700 }
 701
 702 void register_buf_size(int id)
 703 {
 704         my_size_id = id;
 705
 706         select_caller_info_hook(set_param_buf_size, BUF_SIZE);
 707         select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
 708
 709         add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
 710         add_function_assign_hook("calloc", &match_calloc, NULL);
 711         add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
 712         if (option_project == PROJ_KERNEL) {
 713                 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
 714                 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
 715                 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
 716                 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
 717                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 718                 add_function_assign_hook("kmalloc_array", &match_calloc, NULL);
 719                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 720                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 721                 add_function_assign_hook("sock_kmalloc", &match_alloc, INT_PTR(1));
 722                 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
 723                 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
 724                 add_function_assign_hook("dma_alloc_attrs", &match_alloc, INT_PTR(1));
 725         }
 726         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 727         add_hook(&match_strlen_condition, CONDITION_HOOK);
 728         add_function_assign_hook("strlen", &match_strlen, NULL);
 729
 730         add_function_assign_hook("strndup", match_strndup, NULL);
 731         if (option_project == PROJ_KERNEL)
 732                 add_function_assign_hook("kstrndup", match_strndup, NULL);
 733
 734         add_modification_hook(my_size_id, &set_undefined);
 735
 736         add_merge_hook(my_size_id, &merge_func);
 737 }
 738
 739 void register_strlen(int id)
 740 {
 741         my_strlen_id = id;
 742         add_modification_hook(my_strlen_id, &set_undefined);
 743         add_merge_hook(my_strlen_id, &merge_func);
 744 }
 745
 746 void register_buf_size_late(int id)
 747 {
 748         add_function_hook("strlcpy", &match_limited, &b0_l2);
 749         add_function_hook("strlcat", &match_limited, &b0_l2);
 750         add_function_hook("memscan", &match_limited, &b0_l2);
 751
 752         add_function_hook("strcpy", &match_strcpy, NULL);
 753
 754         add_hook(&match_call, FUNCTION_CALL_HOOK);
 755         add_member_info_callback(my_size_id, struct_member_callback);
 756 }