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