smatch_buf_size.c

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