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