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 = get_variable_from_expr(expr, NULL);
 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 int get_real_array_size(struct expression *expr)
 177 {
 178         struct symbol *type;
 179         int ret;
 180
 181         if (expr->type == EXPR_BINOP) /* array elements foo[5] */
 182                 return 0;
 183
 184         type = get_type(expr);
 185         if (!type || type->type != SYM_ARRAY)
 186                 return 0;
 187
 188         ret = get_expression_value(type->array_size);
 189         /* Dynamically sized array are -1 in sparse */
 190         if (ret <= 0)
 191                 return 0;
 192         /* People put one element arrays on the end of structs */
 193         if (ret == 1)
 194                 return 0;
 195
 196         return ret;
 197 }
 198
 199 static int get_size_from_initializer(struct expression *expr)
 200 {
 201         if (expr->type != EXPR_SYMBOL || !expr->symbol->initializer)
 202                 return 0;
 203         if (expr->symbol->initializer == expr) /* int a = a; */
 204                 return 0;
 205         return get_initializer_size(expr->symbol->initializer);
 206 }
 207
 208 static int get_stored_size_bytes(struct expression *expr)
 209 {
 210         struct smatch_state *state;
 211
 212         state = get_state_expr(my_size_id, expr);
 213         if (!state)
 214                 return 0;
 215         return PTR_INT(state->data);
 216 }
 217
 218 static int get_bytes_from_address(struct expression *expr)
 219 {
 220         struct symbol *type;
 221         int ret;
 222
 223         if (!option_spammy)
 224                 return 0;
 225         if (expr->type != EXPR_PREOP || expr->op != '&')
 226                 return 0;
 227         type = get_type(expr);
 228         if (!type)
 229                 return 0;
 230
 231         if (type->type == SYM_PTR)
 232                 type = get_base_type(type);
 233
 234         ret = bits_to_bytes(type->bit_size);
 235         if (ret == -1)
 236                 return 0;
 237         if (ret == 1)
 238                 return 0;  /* ignore char pointers */
 239
 240         return ret;
 241 }
 242
 243 static int get_size_from_strlen(struct expression *expr)
 244 {
 245         struct smatch_state *state;
 246         long long len;
 247
 248         state = get_state_expr(my_strlen_id, expr);
 249         if (!state || !state->data)
 250                 return 0;
 251         if (get_implied_max((struct expression *)state->data, &len))
 252                 return len + 1; /* add one because strlen doesn't include the NULL */
 253         return 0;
 254 }
 255
 256 static struct expression *remove_addr_fluff(struct expression *expr)
 257 {
 258         struct expression *tmp;
 259         long long val;
 260
 261         expr = strip_expr(expr);
 262
 263         /* remove '&' and '*' operations that cancel */
 264         while (expr->type == EXPR_PREOP && expr->op == '&') {
 265                 tmp = strip_expr(expr->unop);
 266                 if (tmp->type != EXPR_PREOP)
 267                         break;
 268                 if (tmp->op != '*')
 269                         break;
 270                 expr = strip_expr(tmp->unop);
 271         }
 272
 273         /* "foo + 0" is just "foo" */
 274         if (expr->type == EXPR_BINOP && expr->op == '+' &&
 275             get_value(expr->right, &val) && val == 0)
 276                 return expr->left;
 277
 278         return expr;
 279 }
 280
 281 int get_array_size_bytes(struct expression *expr)
 282 {
 283         int size;
 284
 285         expr = remove_addr_fluff(expr);
 286         if (!expr)
 287                 return 0;
 288
 289         /* strcpy(foo, "BAR"); */
 290         if (expr->type == EXPR_STRING)
 291                 return expr->string->length;
 292
 293         /* buf[4] */
 294         size = get_real_array_size(expr);
 295         if (size)
 296                 return elements_to_bytes(expr, size);
 297
 298         /* buf = malloc(1024); */
 299         size = get_stored_size_bytes(expr);
 300         if (size)
 301                 return size;
 302
 303         /* char *foo = "BAR" */
 304         size = get_size_from_initializer(expr);
 305         if (size)
 306                 return elements_to_bytes(expr, size);
 307
 308         size = get_bytes_from_address(expr);
 309         if (size)
 310                 return size;
 311
 312         /* if (strlen(foo) > 4) */
 313         size = get_size_from_strlen(expr);
 314         if (size)
 315                 return size;
 316
 317         return size_from_db(expr);
 318 }
 319
 320 int get_array_size(struct expression *expr)
 321 {
 322         int bytes;
 323
 324         bytes = get_array_size_bytes(expr);
 325         return bytes_to_elements(expr, bytes);
 326 }
 327
 328 static void match_strlen_condition(struct expression *expr)
 329 {
 330         struct expression *left;
 331         struct expression *right;
 332         struct expression *str = NULL;
 333         int strlen_left = 0;
 334         int strlen_right = 0;
 335         long long val;
 336         struct smatch_state *true_state = NULL;
 337         struct smatch_state *false_state = NULL;
 338
 339         if (expr->type != EXPR_COMPARE)
 340                 return;
 341         left = strip_expr(expr->left);
 342         right = strip_expr(expr->right);
 343
 344         if (left->type == EXPR_CALL && sym_name_is("strlen", left->fn)) {
 345                 str = get_argument_from_call_expr(left->args, 0);
 346                 strlen_left = 1;
 347         }
 348         if (right->type == EXPR_CALL && sym_name_is("strlen", right->fn)) {
 349                 str = get_argument_from_call_expr(right->args, 0);
 350                 strlen_right = 1;
 351         }
 352
 353         if (!strlen_left && !strlen_right)
 354                 return;
 355         if (strlen_left && strlen_right)
 356                 return;
 357
 358         if (strlen_left) {
 359                 if (!get_value(right, &val))
 360                         return;
 361         }
 362         if (strlen_right) {
 363                 if (!get_value(left, &val))
 364                         return;
 365         }
 366
 367         if (expr->op == SPECIAL_EQUAL) {
 368                 set_true_false_states_expr(my_size_id, str, alloc_state_num(val + 1), NULL);
 369                 return;
 370         }
 371         if (expr->op == SPECIAL_NOTEQUAL) {
 372                 set_true_false_states_expr(my_size_id, str, NULL, alloc_state_num(val + 1));
 373                 return;
 374         }
 375
 376         switch (expr->op) {
 377         case '<':
 378         case SPECIAL_UNSIGNED_LT:
 379                 if (strlen_left)
 380                         true_state = alloc_state_num(val);
 381                 else
 382                         false_state = alloc_state_num(val + 1);
 383                 break;
 384         case SPECIAL_LTE:
 385         case SPECIAL_UNSIGNED_LTE:
 386                 if (strlen_left)
 387                         true_state = alloc_state_num(val + 1);
 388                 else
 389                         false_state = alloc_state_num(val);
 390                 break;
 391         case SPECIAL_GTE:
 392         case SPECIAL_UNSIGNED_GTE:
 393                 if (strlen_left)
 394                         false_state = alloc_state_num(val);
 395                 else
 396                         true_state = alloc_state_num(val + 1);
 397                 break;
 398         case '>':
 399         case SPECIAL_UNSIGNED_GT:
 400                 if (strlen_left)
 401                         false_state = alloc_state_num(val + 1);
 402                 else
 403                         true_state = alloc_state_num(val);
 404                 break;
 405         }
 406         set_true_false_states_expr(my_size_id, str, true_state, false_state);
 407 }
 408
 409 static struct expression *strip_ampersands(struct expression *expr)
 410 {
 411         struct symbol *type;
 412
 413         if (expr->type != EXPR_PREOP)
 414                 return expr;
 415         if (expr->op != '&')
 416                 return expr;
 417         type = get_type(expr->unop);
 418         if (!type || type->type != SYM_ARRAY)
 419                 return expr;
 420         return expr->unop;
 421 }
 422
 423 static void match_array_assignment(struct expression *expr)
 424 {
 425         struct expression *left;
 426         struct expression *right;
 427         int array_size;
 428
 429         if (expr->op != '=')
 430                 return;
 431         left = strip_expr(expr->left);
 432         right = strip_expr(expr->right);
 433         right = strip_ampersands(right);
 434         array_size = get_array_size_bytes(right);
 435         if (array_size)
 436                 set_state_expr(my_size_id, left, alloc_state_num(array_size));
 437 }
 438
 439 static void info_record_alloction(struct expression *buffer, struct expression *size)
 440 {
 441         char *name;
 442         long long val;
 443
 444         if (!option_info)
 445                 return;
 446
 447         name = get_member_name(buffer);
 448         if (!name && is_static(buffer))
 449                 name = get_variable_from_expr(buffer, NULL);
 450         if (!name)
 451                 return;
 452         if (!get_implied_value(size, &val))
 453                 val = -1;
 454         sm_msg("info: '%s' allocated_buf_size %lld", name, val);
 455         free_string(name);
 456 }
 457
 458 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 459 {
 460         int size_arg = PTR_INT(_size_arg);
 461         struct expression *right;
 462         struct expression *arg;
 463         long long bytes;
 464
 465         right = strip_expr(expr->right);
 466         arg = get_argument_from_call_expr(right->args, size_arg);
 467
 468         info_record_alloction(expr->left, arg);
 469
 470         if (!get_implied_value(arg, &bytes))
 471                 return;
 472         set_state_expr(my_size_id, expr->left, alloc_state_num(bytes));
 473 }
 474
 475 static void match_calloc(const char *fn, struct expression *expr, void *unused)
 476 {
 477         struct expression *right;
 478         struct expression *arg;
 479         long long elements;
 480         long long size;
 481
 482         right = strip_expr(expr->right);
 483         arg = get_argument_from_call_expr(right->args, 0);
 484         if (!get_implied_value(arg, &elements))
 485                 return;
 486         arg = get_argument_from_call_expr(right->args, 1);
 487         if (!get_implied_value(arg, &size))
 488                 return;
 489         set_state_expr(my_size_id, expr->left, alloc_state_num(elements * size));
 490 }
 491
 492 static void match_strlen(const char *fn, struct expression *expr, void *unused)
 493 {
 494         struct expression *right;
 495         struct expression *str;
 496         struct expression *len_expr;
 497         char *len_name;
 498         struct smatch_state *state;
 499
 500         right = strip_expr(expr->right);
 501         str = get_argument_from_call_expr(right->args, 0);
 502         len_expr = strip_expr(expr->left);
 503
 504         len_name = get_variable_from_expr(len_expr, NULL);
 505         if (!len_name)
 506                 return;
 507
 508         state = __alloc_smatch_state(0);
 509         state->name = len_name;
 510         state->data = len_expr;
 511         set_state_expr(my_strlen_id, str, state);
 512 }
 513
 514 static void match_limited(const char *fn, struct expression *expr, void *_limiter)
 515 {
 516         struct limiter *limiter = (struct limiter *)_limiter;
 517         struct expression *dest;
 518         struct expression *size_expr;
 519         long long size;
 520
 521         dest = get_argument_from_call_expr(expr->args, limiter->buf_arg);
 522         size_expr = get_argument_from_call_expr(expr->args, limiter->limit_arg);
 523         if (!get_implied_max(size_expr, &size))
 524                 return;
 525         set_state_expr(my_size_id, dest, alloc_state_num(size));
 526 }
 527
 528 static void match_strcpy(const char *fn, struct expression *expr, void *unused)
 529 {
 530         struct expression fake_assign;
 531
 532         fake_assign.op = '=';
 533         fake_assign.left = get_argument_from_call_expr(expr->args, 0);
 534         fake_assign.right = get_argument_from_call_expr(expr->args, 1);
 535         match_array_assignment(&fake_assign);
 536 }
 537
 538 static void match_strndup(const char *fn, struct expression *expr, void *unused)
 539 {
 540         struct expression *fn_expr;
 541         struct expression *size_expr;
 542         long long size;
 543
 544         fn_expr = strip_expr(expr->right);
 545         size_expr = get_argument_from_call_expr(fn_expr->args, 1);
 546         if (!get_implied_max(size_expr, &size))
 547                 return;
 548
 549         /* It's easy to forget space for the NUL char */
 550         size++;
 551         set_state_expr(my_size_id, expr->left, alloc_state_num(size));
 552 }
 553
 554 static void match_call(struct expression *expr)
 555 {
 556         char *name;
 557         struct expression *arg;
 558         int bytes;
 559         int i;
 560
 561         name = get_fnptr_name(expr->fn);
 562         if (!name)
 563                 return;
 564
 565         i = 0;
 566         FOR_EACH_PTR(expr->args, arg) {
 567                 bytes = get_array_size_bytes(arg);
 568                 if (bytes > 1)
 569                         sm_msg("info: passes_buffer '%s' %d '$$' %d %s",
 570                                 name, i, bytes,
 571                                 is_static(expr->fn) ? "static" : "global");
 572                 i++;
 573         } END_FOR_EACH_PTR(arg);
 574
 575         free_string(name);
 576 }
 577
 578 static void struct_member_callback(char *fn, char *global_static, int param, char *printed_name, struct smatch_state *state)
 579 {
 580         if (state == &merged)
 581                 return;
 582         sm_msg("info: passes_buffer '%s' %d '%s' %s %s", fn, param, printed_name, state->name, global_static);
 583 }
 584
 585 static void match_func_end(struct symbol *sym)
 586 {
 587         memset(params_set, 0, sizeof(params_set));
 588 }
 589
 590 void register_buf_size(int id)
 591 {
 592         my_size_id = id;
 593
 594         add_definition_db_callback(set_param_buf_size, BUF_SIZE);
 595
 596         add_function_assign_hook("malloc", &match_alloc, INT_PTR(0));
 597         add_function_assign_hook("calloc", &match_calloc, NULL);
 598         add_function_assign_hook("memdup", &match_alloc, INT_PTR(1));
 599         if (option_project == PROJ_KERNEL) {
 600                 add_function_assign_hook("kmalloc", &match_alloc, INT_PTR(0));
 601                 add_function_assign_hook("kzalloc", &match_alloc, INT_PTR(0));
 602                 add_function_assign_hook("vmalloc", &match_alloc, INT_PTR(0));
 603                 add_function_assign_hook("__vmalloc", &match_alloc, INT_PTR(0));
 604                 add_function_assign_hook("kcalloc", &match_calloc, NULL);
 605                 add_function_assign_hook("kmalloc_array", &match_calloc, NULL);
 606                 add_function_assign_hook("drm_malloc_ab", &match_calloc, NULL);
 607                 add_function_assign_hook("drm_calloc_large", &match_calloc, NULL);
 608                 add_function_assign_hook("sock_kmalloc", &match_alloc, INT_PTR(1));
 609                 add_function_assign_hook("kmemdup", &match_alloc, INT_PTR(1));
 610                 add_function_assign_hook("kmemdup_user", &match_alloc, INT_PTR(1));
 611         }
 612         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
 613         add_hook(&match_strlen_condition, CONDITION_HOOK);
 614         add_function_assign_hook("strlen", &match_strlen, NULL);
 615
 616         add_function_assign_hook("strndup", match_strndup, NULL);
 617         if (option_project == PROJ_KERNEL)
 618                 add_function_assign_hook("kstrndup", match_strndup, NULL);
 619
 620         add_hook(&match_func_end, END_FUNC_HOOK);
 621         add_modification_hook(my_size_id, &set_undefined);
 622
 623         add_merge_hook(my_size_id, &merge_func);
 624 }
 625
 626 void register_strlen(int id)
 627 {
 628         my_strlen_id = id;
 629         add_modification_hook(my_strlen_id, &set_undefined);
 630         add_merge_hook(my_strlen_id, &merge_func);
 631 }
 632
 633 void register_buf_size_late(int id)
 634 {
 635         add_function_hook("strlcpy", &match_limited, &b0_l2);
 636         add_function_hook("strlcat", &match_limited, &b0_l2);
 637         add_function_hook("memscan", &match_limited, &b0_l2);
 638
 639         add_function_hook("strcpy", &match_strcpy, NULL);
 640
 641         if (option_info) {
 642                 add_hook(&match_call, FUNCTION_CALL_HOOK);
 643                 add_member_info_callback(my_size_id, struct_member_callback);
 644         }
 645 }