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