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