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