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 static struct smatch_state *merge_func(struct smatch_state *s1, struct smatch_state *s2)
  41 {
  42         if (PTR_INT(s1->data) == PTR_INT(s2->data))
  43                 return s1;
  44         return &undefined;
  45 }
  46
  47 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
  48 {
  49         char fullname[256];
  50         unsigned int size;
  51
  52         if (strncmp(key, "$$", 2))
  53                 return;
  54
  55         snprintf(fullname, 256, "%s%s", name, key + 2);
  56
  57         errno = 0;
  58         size = strtoul(value, NULL, 10);
  59         if (errno)
  60                 return;
  61
  62         set_state(my_size_id, fullname, sym, alloc_state_num(size));
  63 }
  64
  65 static int bytes_per_element(struct expression *expr)
  66 {
  67         struct symbol *type;
  68         int bpe;
  69
  70         if (expr->type == EXPR_STRING)
  71                 return 1;
  72         type = get_type(expr);
  73         if (!type)
  74                 return 0;
  75
  76         if (type->type != SYM_PTR && type->type != SYM_ARRAY)
  77                 return 0;
  78
  79         type = get_base_type(type);
  80         bpe = bits_to_bytes(type->bit_size);
  81
  82         if (bpe == -1) /* void pointer */
  83                 bpe = 1;
  84
  85         return bpe;
  86 }
  87
  88 static int bytes_to_elements(struct expression *expr, int bytes)
  89 {
  90         int bpe;
  91
  92         bpe = bytes_per_element(expr);
  93         if (bpe == 0)
  94                 return 0;
  95         return bytes / bpe;
  96 }
  97
  98 static int elements_to_bytes(struct expression *expr, int elements)
  99 {
 100         int bpe;
 101
 102         bpe = bytes_per_element(expr);
 103         return elements * bpe;
 104 }
 105
 106 static int get_initializer_size(struct expression *expr)
 107 {
 108         switch (expr->type) {
 109         case EXPR_STRING:
 110                 return expr->string->length;
 111         case EXPR_INITIALIZER: {
 112                 struct expression *tmp;
 113                 int i = 0;
 114                 int max = 0;
 115
 116                 FOR_EACH_PTR(expr->expr_list, tmp) {
 117                         if (tmp->type == EXPR_INDEX && tmp->idx_to > max)
 118                                 max = tmp->idx_to;
 119                         i++;
 120                 } END_FOR_EACH_PTR(tmp);
 121                 if (max)
 122                         return max + 1;
 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 == -1)
 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 == -1)
 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 static 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         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->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         /* "foo + 0" is just "foo" */
 307         if (expr->type == EXPR_BINOP && expr->op == '+' &&
 308             get_value(expr->right, &sval) && sval.value == 0)
 309                 return expr->left;
 310
 311         return expr;
 312 }
 313
 314 int get_array_size_bytes(struct expression *expr)
 315 {
 316         int size;
 317
 318         expr = remove_addr_fluff(expr);
 319         if (!expr)
 320                 return 0;
 321
 322         /* strcpy(foo, "BAR"); */
 323         if (expr->type == EXPR_STRING)
 324                 return expr->string->length;
 325
 326         /* buf[4] */
 327         size = get_real_array_size(expr);
 328         if (size)
 329                 return elements_to_bytes(expr, size);
 330
 331         /* buf = malloc(1024); */
 332         size = get_stored_size_bytes(expr);
 333         if (size)
 334                 return size;
 335
 336         /* char *foo = "BAR" */
 337         size = get_size_from_initializer(expr);
 338         if (size)
 339                 return elements_to_bytes(expr, size);
 340
 341         size = get_bytes_from_address(expr);
 342         if (size)
 343                 return size;
 344
 345         /* if (strlen(foo) > 4) */
 346         size = get_size_from_strlen(expr);
 347         if (size)
 348                 return size;
 349
 350         return size_from_db(expr);
 351 }
 352
 353 int get_array_size_bytes_min(struct expression *expr)
 354 {
 355         int size;
 356         int tmp;
 357
 358         size = get_array_size_bytes(expr);
 359
 360         tmp = get_stored_size_bytes_min(expr);
 361         if (size <= 0 || (tmp >= 1 && tmp < size))
 362                 size = tmp;
 363         return size;
 364 }
 365
 366 int get_array_size(struct expression *expr)
 367 {
 368         int bytes;
 369
 370         bytes = get_array_size_bytes(expr);
 371         return bytes_to_elements(expr, bytes);
 372 }
 373
 374 static void match_strlen_condition(struct expression *expr)
 375 {
 376         struct expression *left;
 377         struct expression *right;
 378         struct expression *str = NULL;
 379         int strlen_left = 0;
 380         int strlen_right = 0;
 381         sval_t sval;
 382         struct smatch_state *true_state = NULL;
 383         struct smatch_state *false_state = NULL;
 384
 385         if (expr->type != EXPR_COMPARE)
 386                 return;
 387         left = strip_expr(expr->left);
 388         right = strip_expr(expr->right);
 389
 390         if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
 391                 str = get_argument_from_call_expr(left->args, 0);
 392                 strlen_left = 1;
 393         }
 394         if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
 395                 str = get_argument_from_call_expr(right->args, 0);
 396                 strlen_right = 1;
 397         }
 398
 399         if (!strlen_left && !strlen_right)
 400                 return;
 401         if (strlen_left && strlen_right)
 402                 return;
 403
 404         if (strlen_left) {
 405                 if (!get_value(right, &sval))
 406                         return;
 407         }
 408         if (strlen_right) {
 409                 if (!get_value(left, &sval))
 410                         return;
 411         }
 412
 413         if (expr->op == SPECIAL_EQUAL) {
 414                 set_true_false_states_expr(my_size_id, str, alloc_state_num(sval.value + 1), NULL);
 415                 return;
 416         }
 417         if (expr->op == SPECIAL_NOTEQUAL) {
 418                 set_true_false_states_expr(my_size_id, str, NULL, alloc_state_num(sval.value + 1));
 419                 return;
 420         }
 421
 422         switch (expr->op) {
 423         case '<':
 424         case SPECIAL_UNSIGNED_LT:
 425                 if (strlen_left)
 426                         true_state = alloc_state_num(sval.value);
 427                 else
 428                         false_state = alloc_state_num(sval.value + 1);
 429                 break;
 430         case SPECIAL_LTE:
 431         case SPECIAL_UNSIGNED_LTE:
 432                 if (strlen_left)
 433                         true_state = alloc_state_num(sval.value + 1);
 434                 else
 435                         false_state = alloc_state_num(sval.value);
 436                 break;
 437         case SPECIAL_GTE:
 438         case SPECIAL_UNSIGNED_GTE:
 439                 if (strlen_left)
 440                         false_state = alloc_state_num(sval.value);
 441                 else
 442                         true_state = alloc_state_num(sval.value + 1);
 443                 break;
 444         case '>':
 445         case SPECIAL_UNSIGNED_GT:
 446                 if (strlen_left)
 447                         false_state = alloc_state_num(sval.value + 1);
 448                 else
 449                         true_state = alloc_state_num(sval.value);
 450                 break;
 451         }
 452         set_true_false_states_expr(my_size_id, str, true_state, false_state);
 453 }
 454
 455 static struct expression *strip_ampersands(struct expression *expr)
 456 {
 457         struct symbol *type;
 458
 459         if (expr->type != EXPR_PREOP)
 460                 return expr;
 461         if (expr->op != '&')
 462                 return expr;
 463         type = get_type(expr->unop);
 464         if (!type || type->type != SYM_ARRAY)
 465                 return expr;
 466         return expr->unop;
 467 }
 468
 469 static void match_array_assignment(struct expression *expr)
 470 {
 471         struct expression *left;
 472         struct expression *right;
 473         int array_size;
 474
 475         if (expr->op != '=')
 476                 return;
 477         left = strip_expr(expr->left);
 478         right = strip_expr(expr->right);
 479         right = strip_ampersands(right);
 480         array_size = get_array_size_bytes(right);
 481         if (array_size)
 482                 set_state_expr(my_size_id, left, alloc_state_num(array_size));
 483 }
 484
 485 static void info_record_alloction(struct expression *buffer, struct expression *size)
 486 {
 487         char *name;
 488         sval_t sval;
 489
 490         if (!option_info)
 491                 return;
 492
 493         name = get_member_name(buffer);
 494         if (!name && is_static(buffer))
 495                 name = expr_to_var(buffer);
 496         if (!name)
 497                 return;
 498         if (get_implied_value(size, &sval))
 499                 sql_insert_type_size(name, sval.value);
 500         else
 501                 sql_insert_type_size(name, -1);
 502
 503         free_string(name);
 504 }
 505
 506 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 507 {
 508         int size_arg = PTR_INT(_size_arg);
 509         struct expression *right;
 510         struct expression *arg;
 511         sval_t bytes;
 512
 513         right = strip_expr(expr->right);
 514         arg = get_argument_from_call_expr(right->args, size_arg);
 515
 516         info_record_alloction(expr->left, arg);
 517
 518         if (!get_implied_value(arg, &bytes))
 519                 return;
 520         set_state_expr(my_size_id, expr->left, alloc_state_num(bytes.value));
 521 }
 522
 523 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 524 {
 525         struct expression *right;
 526         struct expression *arg;
 527         sval_t elements;
 528         sval_t size;
 529
 530         right = strip_expr(expr->right);
 531         arg = get_argument_from_call_expr(right->args, 0);
 532         if (!get_implied_value(arg, &elements))
 533                 return;
 534         arg = get_argument_from_call_expr(right->args, 1);
 535         if (!get_implied_value(arg, &size))
 536                 return;
 537         set_state_expr(my_size_id, expr->left, alloc_state_num(elements.value * size.value));
 538 }
 539
 540 static void match_strlen(const char *fn, struct expression *expr, void *unused)
 541 {
 542         struct expression *right;
 543         struct expression *str;
 544         struct expression *len_expr;
 545         char *len_name;
 546         struct smatch_state *state;
 547
 548         right = strip_expr(expr->right);
 549         str = get_argument_from_call_expr(right->args, 0);
 550         len_expr = strip_expr(expr->left);
 551
 552         len_name = expr_to_var(len_expr);
 553         if (!len_name)
 554                 return;
 555
 556         state = __alloc_smatch_state(0);
 557         state->name = len_name;
 558         state->data = len_expr;
 559         set_state_expr(my_strlen_id, str, state);
 560 }
 561
 562 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 563 {
 564         struct limiter *limiter = (struct limiter *)_limiter;
 565         struct expression *dest;
 566         struct expression *size_expr;
 567         sval_t size;
 568
 569         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 570         size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 571         if (!get_implied_max(size_expr, &size))
 572                 return;
 573         set_state_expr(my_size_id, dest, alloc_state_num(size.value));
 574 }
 575
 576 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 577 {
 578         struct expression fake_assign;
 579
 580         fake_assign.op = '=';
 581         fake_assign.left = get_argument_from_call_expr(expr->args, 0);
 582         fake_assign.right = get_argument_from_call_expr(expr->args, 1);
 583         match_array_assignment(&fake_assign);
 584 }
 585
 586 static void match_strndup(const char *fn, struct expression *expr, void *unused)
 587 {
 588         struct expression *fn_expr;
 589         struct expression *size_expr;
 590         sval_t size;
 591
 592         fn_expr = strip_expr(expr->right);
 593         size_expr = get_argument_from_call_expr(fn_expr->args, 1);
 594         if (!get_implied_max(size_expr, &size))
 595                 return;
 596
 597         /* It's easy to forget space for the NUL char */
 598         size.value++;
 599         set_state_expr(my_size_id, expr->left, alloc_state_num(size.value));
 600 }
 601
 602 static void match_call(struct expression *expr)
 603 {
 604         char *name;
 605         struct expression *arg;
 606         int bytes;
 607         int i;
 608
 609         name = get_fnptr_name(expr->fn);
 610         if (!name)
 611                 return;
 612
 613         i = 0;
 614         FOR_EACH_PTR(expr->args, arg) {
 615                 bytes = get_array_size_bytes(arg);
 616                 if (bytes > 1) {
 617                         char buf[11];
 618
 619                         snprintf(buf, sizeof(buf), "%d", bytes);
 620                         sql_insert_caller_info(name, is_static(expr->fn),
 621                                         BUF_SIZE, i, "$$", buf);
 622                 }
 623                 i++;
 624         } END_FOR_EACH_PTR(arg);
 625
 626         free_string(name);
 627 }
 628
 629 static void struct_member_callback(char *fn, int static_flag, int param, char *printed_name, struct smatch_state *state)
 630 {
 631         if (state == &merged)
 632                 return;
 633         sql_insert_caller_info(fn, static_flag, BUF_SIZE, param, printed_name, state->name);
 634 }
 635
 636 static void match_func_end(struct symbol *sym)
 637 {
 638         memset(params_set, 0, sizeof(params_set));
 639 }
 640
 641 void register_buf_size(int id)
 642 {
 643         my_size_id = id;
 644
 645         add_definition_db_callback(set_param_buf_size, BUF_SIZE);
 646         add_db_return_states_callback(BUF_SIZE, &db_returns_buf_size);
 647
 648         add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
 649         add_function_assign_hook("calloc", &match_calloc, NULL);
 650         add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
 651         if (option_project == PROJ_KERNEL) {
 652                 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
 653                 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
 654                 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
 655                 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
 656                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 657                 add_function_assign_hook("kmalloc_array", &match_calloc, NULL);
 658                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 659                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 660                 add_function_assign_hook("sock_kmalloc", &match_alloc, INT_PTR(1));
 661                 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
 662                 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
 663         }
 664         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 665         add_hook(&match_strlen_condition, CONDITION_HOOK);
 666         add_function_assign_hook("strlen", &match_strlen, NULL);
 667
 668         add_function_assign_hook("strndup", match_strndup, NULL);
 669         if (option_project == PROJ_KERNEL)
 670                 add_function_assign_hook("kstrndup", match_strndup, NULL);
 671
 672         add_hook(&match_func_end, END_FUNC_HOOK);
 673         add_modification_hook(my_size_id, &set_undefined);
 674
 675         add_merge_hook(my_size_id, &merge_func);
 676 }
 677
 678 void register_strlen(int id)
 679 {
 680         my_strlen_id = id;
 681         add_modification_hook(my_strlen_id, &set_undefined);
 682         add_merge_hook(my_strlen_id, &merge_func);
 683 }
 684
 685 void register_buf_size_late(int id)
 686 {
 687         add_function_hook("strlcpy", &match_limited, &b0_l2);
 688         add_function_hook("strlcat", &match_limited, &b0_l2);
 689         add_function_hook("memscan", &match_limited, &b0_l2);
 690
 691         add_function_hook("strcpy", &match_strcpy, NULL);
 692
 693         if (option_info) {
 694                 add_hook(&match_call, FUNCTION_CALL_HOOK);
 695                 add_member_info_callback(my_size_id, struct_member_callback);
 696         }
 697 }