smatch_buf_size.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 #include <stdlib.h>
  19 #include <errno.h>
  20 #include "parse.h"
  21 #include "smatch.h"
  22 #include "smatch_slist.h"
  23 #include "smatch_extra.h"
  24 #include "smatch_function_hashtable.h"
  25
  26 #define UNKNOWN_SIZE -1
  27
  28 static int my_size_id;
  29
  30 static DEFINE_HASHTABLE_INSERT(insert_func, char, int);
  31 static DEFINE_HASHTABLE_SEARCH(search_func, char, int);
  32 static struct hashtable *allocation_funcs;
  33
  34 static char *get_fn_name(struct expression *expr)
  35 {
  36         if (expr->type != EXPR_CALL)
  37                 return NULL;
  38         if (expr->fn->type != EXPR_SYMBOL)
  39                 return NULL;
  40         return expr_to_var(expr->fn);
  41 }
  42
  43 static int is_allocation_function(struct expression *expr)
  44 {
  45         char *func;
  46         int ret = 0;
  47
  48         func = get_fn_name(expr);
  49         if (!func)
  50                 return 0;
  51         if (search_func(allocation_funcs, func))
  52                 ret = 1;
  53         free_string(func);
  54         return ret;
  55 }
  56
  57 static void add_allocation_function(const char *func, void *call_back, int param)
  58 {
  59         insert_func(allocation_funcs, (char *)func, (int *)1);
  60         add_function_assign_hook(func, call_back, INT_PTR(param));
  61 }
  62
  63 static struct smatch_state *size_to_estate(int size)
  64 {
  65         sval_t sval;
  66
  67         sval.type = &int_ctype;
  68         sval.value = size;
  69
  70         return alloc_estate_sval(sval);
  71 }
  72
  73 static struct range_list *size_to_rl(int size)
  74 {
  75         sval_t sval;
  76
  77         sval.type = &int_ctype;
  78         sval.value = size;
  79
  80         return alloc_rl(sval, sval);
  81 }
  82
  83 static struct smatch_state *unmatched_size_state(struct sm_state *sm)
  84 {
  85         return size_to_estate(UNKNOWN_SIZE);
  86 }
  87
  88 static void set_size_undefined(struct sm_state *sm, struct expression *mod_expr)
  89 {
  90         set_state(sm->owner, sm->name, sm->sym, size_to_estate(UNKNOWN_SIZE));
  91 }
  92
  93 static struct smatch_state *merge_size_func(struct smatch_state *s1, struct smatch_state *s2)
  94 {
  95         return merge_estates(s1, s2);
  96 }
  97
  98 void set_param_buf_size(const char *name, struct symbol *sym, char *key, char *value)
  99 {
 100         struct range_list *rl = NULL;
 101         struct smatch_state *state;
 102         char fullname[256];
 103
 104         if (strncmp(key, "$", 1) != 0)
 105                 return;
 106
 107         snprintf(fullname, 256, "%s%s", name, key + 1);
 108
 109         str_to_rl(&int_ctype, value, &rl);
 110         if (!rl || is_whole_rl(rl))
 111                 return;
 112         state = alloc_estate_rl(rl);
 113         set_state(my_size_id, fullname, sym, state);
 114 }
 115
 116 static int bytes_per_element(struct expression *expr)
 117 {
 118         struct symbol *type;
 119
 120         if (!expr)
 121                 return 0;
 122         if (expr->type == EXPR_STRING)
 123                 return expr->wide + 1;
 124         if (expr->type == EXPR_PREOP && expr->op == '&') {
 125                 type = get_type(expr->unop);
 126                 if (type && type->type == SYM_ARRAY)
 127                         expr = expr->unop;
 128         }
 129         type = get_type(expr);
 130         if (!type)
 131                 return 0;
 132
 133         if (type->type != SYM_PTR && type->type != SYM_ARRAY)
 134                 return 0;
 135
 136         type = get_base_type(type);
 137         return type_bytes(type);
 138 }
 139
 140 int bytes_to_elements(struct expression *expr, int bytes)
 141 {
 142         int bpe;
 143
 144         bpe = bytes_per_element(expr);
 145         if (bpe == 0)
 146                 return 0;
 147         return bytes / bpe;
 148 }
 149
 150 static int elements_to_bytes(struct expression *expr, int elements)
 151 {
 152         int bpe;
 153
 154         bpe = bytes_per_element(expr);
 155         return elements * bpe;
 156 }
 157
 158 static int get_initializer_size(struct expression *expr)
 159 {
 160         switch (expr->type) {
 161         case EXPR_STRING:
 162                 return expr->string->length * (expr->wide + 1);
 163         case EXPR_INITIALIZER: {
 164                 struct expression *tmp;
 165                 int i = 0;
 166
 167                 FOR_EACH_PTR(expr->expr_list, tmp) {
 168                         if (tmp->type == EXPR_INDEX) {
 169                                 if (tmp->idx_to >= i)
 170                                         i = tmp->idx_to;
 171                                 else
 172                                         continue;
 173                         }
 174
 175                         i++;
 176                 } END_FOR_EACH_PTR(tmp);
 177                 return i;
 178         }
 179         case EXPR_SYMBOL:
 180                 return get_array_size(expr);
 181         }
 182         return 0;
 183 }
 184
 185 static struct range_list *db_size_rl;
 186 static int db_size_callback(void *unused, int argc, char **argv, char **azColName)
 187 {
 188         struct range_list *tmp = NULL;
 189
 190         if (!db_size_rl) {
 191                 str_to_rl(&int_ctype, argv[0], &db_size_rl);
 192         } else {
 193                 str_to_rl(&int_ctype, argv[0], &tmp);
 194                 db_size_rl = rl_union(db_size_rl, tmp);
 195         }
 196         return 0;
 197 }
 198
 199 static struct expression *cached_type_expr, *cached_sym_expr;
 200 static struct range_list *cached_type_rl, *cached_sym_rl;
 201
 202 static void match_clear_cache(struct symbol *sym)
 203 {
 204         cached_type_expr = NULL;
 205         cached_type_rl = NULL;
 206         cached_sym_expr = NULL;
 207         cached_sym_rl = NULL;
 208 }
 209
 210 static char *get_stored_buffer_name(struct expression *buffer, bool *add_static)
 211 {
 212         struct expression *array;
 213         char buf[64];
 214         char *name;
 215
 216         *add_static = false;
 217
 218         name = get_member_name(buffer);
 219         if (name)
 220                 return alloc_string(name);
 221
 222         if (is_static(buffer)) {
 223                 name = expr_to_var(buffer);
 224                 if (!name)
 225                         return NULL;
 226                 *add_static = 1;
 227                 return name;
 228         }
 229
 230         array = get_array_base(buffer);
 231         if (array) {
 232                 name = get_member_name(array);
 233                 if (!name)
 234                         return NULL;
 235                 snprintf(buf, sizeof(buf), "%s[]", name);
 236                 return alloc_string(buf);
 237         }
 238
 239         return NULL;
 240 }
 241
 242 static struct range_list *size_from_db_type(struct expression *expr)
 243 {
 244         bool this_file_only;
 245         char *name;
 246
 247         name = get_stored_buffer_name(expr, &this_file_only);
 248         if (!name)
 249                 return NULL;
 250
 251         if (expr == cached_type_expr)
 252                 return clone_rl(cached_type_rl);
 253         cached_type_expr = expr;
 254         cached_type_rl = NULL;
 255
 256         if (this_file_only) {
 257                 db_size_rl = NULL;
 258                 run_sql(db_size_callback, NULL,
 259                         "select size from function_type_size where type = '%s' and file = %d;",
 260                         name, get_file_id());
 261                 cached_type_rl = clone_rl(db_size_rl);
 262                 return db_size_rl;
 263         }
 264
 265         db_size_rl = NULL;
 266         run_sql(db_size_callback, NULL,
 267                 "select size from type_size where type = '%s';",
 268                 name);
 269         cached_type_rl = clone_rl(db_size_rl);
 270         return db_size_rl;
 271 }
 272
 273 static struct range_list *size_from_db_symbol(struct expression *expr)
 274 {
 275         struct symbol *sym;
 276
 277         if (expr->type != EXPR_SYMBOL)
 278                 return NULL;
 279         sym = expr->symbol;
 280         if (!sym || !sym->ident ||
 281             !(sym->ctype.modifiers & MOD_TOPLEVEL) ||
 282             sym->ctype.modifiers & MOD_STATIC)
 283                 return NULL;
 284
 285         if (expr == cached_sym_expr)
 286                 return clone_rl(cached_sym_rl);
 287         cached_sym_expr = expr;
 288         cached_sym_rl = NULL;
 289
 290         db_size_rl = NULL;
 291         run_sql(db_size_callback, NULL,
 292                 "select value from data_info where file = 0 and data = '%s' and type = %d;",
 293                 sym->ident->name, BUF_SIZE);
 294         cached_sym_rl = clone_rl(db_size_rl);
 295         return db_size_rl;
 296 }
 297
 298 static struct range_list *size_from_db(struct expression *expr)
 299 {
 300         struct range_list *rl;
 301
 302         rl = size_from_db_symbol(expr);
 303         if (rl)
 304                 return rl;
 305         return size_from_db_type(expr);
 306 }
 307
 308 static void db_returns_buf_size(struct expression *expr, int param, char *unused, char *math)
 309 {
 310         struct expression *call;
 311         struct range_list *rl;
 312         sval_t sval;
 313
 314         if (expr->type != EXPR_ASSIGNMENT)
 315                 return;
 316         call = strip_expr(expr->right);
 317
 318         call_results_to_rl(call, &int_ctype, math, &rl);
 319         rl = cast_rl(&int_ctype, rl);
 320         if (rl_to_sval(rl, &sval) && sval.value == 0)
 321                 return;
 322         set_state_expr(my_size_id, expr->left, alloc_estate_rl(rl));
 323 }
 324
 325 static int get_real_array_size_from_type(struct symbol *type)
 326 {
 327         sval_t sval;
 328
 329         if (!type)
 330                 return 0;
 331         if (!type || type->type != SYM_ARRAY)
 332                 return 0;
 333
 334         if (!get_implied_value(type->array_size, &sval))
 335                 return 0;
 336
 337         return sval.value;
 338 }
 339
 340 int get_real_array_size(struct expression *expr)
 341 {
 342         if (!expr)
 343                 return 0;
 344         if (expr->type == EXPR_PREOP && expr->op == '&')
 345                 expr = expr->unop;
 346         if (expr->type == EXPR_BINOP) /* array elements foo[5] */
 347                 return 0;
 348         return get_real_array_size_from_type(get_type(expr));
 349 }
 350
 351 static int get_size_from_initializer(struct expression *expr)
 352 {
 353         if (expr->type != EXPR_SYMBOL || !expr->symbol || !expr->symbol->initializer)
 354                 return 0;
 355         if (expr->symbol->initializer == expr) /* int a = a; */
 356                 return 0;
 357         return get_initializer_size(expr->symbol->initializer);
 358 }
 359
 360 static struct range_list *get_stored_size_bytes(struct expression *expr)
 361 {
 362         struct smatch_state *state;
 363
 364         state = get_state_expr(my_size_id, expr);
 365         if (!state)
 366                 return NULL;
 367         return estate_rl(state);
 368 }
 369
 370 static int get_bytes_from_address(struct expression *expr)
 371 {
 372         struct symbol *type;
 373         int ret;
 374
 375         if (expr->type != EXPR_PREOP || expr->op != '&')
 376                 return 0;
 377         type = get_type(expr);
 378         if (!type)
 379                 return 0;
 380
 381         if (type->type == SYM_PTR)
 382                 type = get_base_type(type);
 383
 384         ret = type_bytes(type);
 385         if (ret == 1)
 386                 return 0;  /* ignore char pointers */
 387
 388         return ret;
 389 }
 390
 391 static struct expression *remove_addr_fluff(struct expression *expr)
 392 {
 393         struct expression *tmp;
 394         sval_t sval;
 395
 396         expr = strip_expr(expr);
 397
 398         /* remove '&' and '*' operations that cancel */
 399         while (expr && expr->type == EXPR_PREOP && expr->op == '&') {
 400                 tmp = strip_expr(expr->unop);
 401                 if (tmp->type != EXPR_PREOP)
 402                         break;
 403                 if (tmp->op != '*')
 404                         break;
 405                 expr = strip_expr(tmp->unop);
 406         }
 407
 408         if (!expr)
 409                 return NULL;
 410
 411         /* "foo + 0" is just "foo" */
 412         if (expr->type == EXPR_BINOP && expr->op == '+' &&
 413             get_value(expr->right, &sval) && sval.value == 0)
 414                 return expr->left;
 415
 416         return expr;
 417 }
 418
 419 static int is_last_member_of_struct(struct symbol *sym, struct ident *member)
 420 {
 421         struct symbol *tmp;
 422         int i;
 423
 424         if (sym->type != SYM_STRUCT)
 425                 return false;
 426
 427         i = 0;
 428         FOR_EACH_PTR_REVERSE(sym->symbol_list, tmp) {
 429                 if (i++ || !tmp->ident)
 430                         return 0;
 431                 if (tmp->ident == member)
 432                         return 1;
 433                 return 0;
 434         } END_FOR_EACH_PTR_REVERSE(tmp);
 435
 436         return 0;
 437 }
 438
 439 int last_member_is_resizable(struct symbol *sym)
 440 {
 441         struct symbol *last_member;
 442         struct symbol *type;
 443         sval_t sval;
 444
 445         if (!sym || sym->type != SYM_STRUCT)
 446                 return 0;
 447
 448         last_member = last_ptr_list((struct ptr_list *)sym->symbol_list);
 449         if (!last_member || !last_member->ident)
 450                 return 0;
 451
 452         type = get_real_base_type(last_member);
 453         if (type->type == SYM_STRUCT)
 454                 return last_member_is_resizable(type);
 455         if (type->type != SYM_ARRAY)
 456                 return 0;
 457
 458         if (!type->array_size)
 459                 return 1;
 460
 461         if (!get_implied_value(type->array_size, &sval))
 462                 return 0;
 463
 464         if (sval.value != 0 && sval.value != 1)
 465                 return 0;
 466
 467         return 1;
 468 }
 469
 470 static struct range_list *get_stored_size_end_struct_bytes(struct expression *expr)
 471 {
 472         struct symbol *sym;
 473         struct symbol *base_sym;
 474         struct smatch_state *state;
 475         sval_t base_size = {
 476                 .type = &int_ctype,
 477         };
 478
 479         if (expr->type == EXPR_BINOP) /* array elements foo[5] */
 480                 return NULL;
 481
 482         if (expr->type == EXPR_PREOP && expr->op == '&')
 483                 expr = strip_parens(expr->unop);
 484
 485         sym = expr_to_sym(expr);
 486         if (!sym || !sym->ident)
 487                 return NULL;
 488         if (!type_bytes(sym))
 489                 return NULL;
 490         if (sym->type != SYM_NODE)
 491                 return NULL;
 492
 493         base_sym = get_real_base_type(sym);
 494         if (!base_sym || base_sym->type != SYM_PTR)
 495                 return NULL;
 496         base_sym = get_real_base_type(base_sym);
 497         if (!base_sym || base_sym->type != SYM_STRUCT)
 498                 return NULL;
 499
 500         if (!is_last_member_of_struct(base_sym, expr->member))
 501                 return NULL;
 502         if (!last_member_is_resizable(base_sym))
 503                 return NULL;
 504
 505         state = get_state(my_size_id, sym->ident->name, sym);
 506         if (!estate_rl(state))
 507                 return NULL;
 508         base_size.value = type_bytes(base_sym) - type_bytes(get_type(expr));
 509         if (sval_cmp(estate_min(state), base_size) < 0)
 510                 return NULL;
 511
 512         return rl_binop(estate_rl(state), '-', alloc_rl(base_size, base_size));
 513 }
 514
 515 static int get_last_element_bytes(struct expression *expr)
 516 {
 517         struct symbol *type, *member, *member_type;
 518
 519         type = get_type(expr);
 520         if (!type || type->type != SYM_STRUCT)
 521                 return 0;
 522         member = last_ptr_list((struct ptr_list *)type->symbol_list);
 523         if (!member)
 524                 return 0;
 525         member_type = get_real_base_type(member);
 526         if (!member_type)
 527                 return 0;
 528         return type_bytes(member_type);
 529 }
 530
 531 static struct range_list *get_outer_end_struct_bytes(struct expression *expr)
 532 {
 533         struct expression *outer;
 534         int last_element_size;
 535         struct symbol *type;
 536         sval_t bytes = {
 537                 .type = &int_ctype,
 538         };
 539
 540         /*
 541          * What we're checking here is for when "u.bar.baz" is a zero element
 542          * array and "u" has a buffer to determine the space for baz.  Like
 543          * this:
 544          * struct { struct bar bar; char buf[256]; } u;
 545          *
 546          */
 547
 548         if (expr->type == EXPR_PREOP && expr->op == '&')
 549                 expr = strip_parens(expr->unop);
 550         if (expr->type != EXPR_DEREF)
 551                 return NULL;
 552         outer = expr->deref;
 553         if (outer->type != EXPR_DEREF)
 554                 return NULL;
 555         type = get_type(outer);
 556         if (!type)
 557                 return NULL;
 558
 559         if (!is_last_member_of_struct(type, expr->member))
 560                 return NULL;
 561         if (!last_member_is_resizable(type))
 562                 return NULL;
 563
 564         last_element_size = get_last_element_bytes(outer->deref);
 565         if (last_element_size == 0)
 566                 return NULL;
 567         if (type_bytes(get_type(outer)) + last_element_size !=
 568             type_bytes(get_type(outer->deref)))
 569                 return NULL;
 570
 571         bytes.value = last_element_size;
 572         return alloc_rl(bytes, bytes);
 573 }
 574
 575 static struct range_list *alloc_int_rl(int value)
 576 {
 577         sval_t sval = {
 578                 .type = &int_ctype,
 579                 {.value = value},
 580         };
 581
 582         return alloc_rl(sval, sval);
 583 }
 584
 585 struct range_list *filter_size_rl(struct range_list *rl)
 586 {
 587         sval_t minus_one = {
 588                 .type = &int_ctype,
 589                 { .value = -1 },
 590         };
 591
 592         sval_t zero = {
 593                 .type = &int_ctype,
 594                 { .value = 0 },
 595         };
 596
 597         return remove_range(rl, minus_one, zero);
 598 }
 599
 600 struct range_list *get_array_size_bytes_rl(struct expression *expr)
 601 {
 602         struct range_list *ret = NULL;
 603         sval_t sval;
 604         int size;
 605
 606         if (is_fake_call(expr))
 607                 return NULL;
 608
 609         expr = remove_addr_fluff(expr);
 610         if (!expr)
 611                 return NULL;
 612
 613         /* "BAR" */
 614         if (expr->type == EXPR_STRING)
 615                 return alloc_int_rl(expr->string->length * (expr->wide + 1));
 616
 617         if (expr->type == EXPR_BINOP && expr->op == '+') {
 618                 sval_t offset;
 619                 struct symbol *type;
 620                 int bytes;
 621
 622                 if (!get_implied_value(expr->right, &offset))
 623                         return NULL;
 624                 type = get_type(expr->left);
 625                 if (!type)
 626                         return NULL;
 627                 if (type->type != SYM_ARRAY && type->type != SYM_PTR)
 628                         return NULL;
 629                 type = get_real_base_type(type);
 630                 bytes = type_bytes(type);
 631                 if (bytes == 0)
 632                         return NULL;
 633                 offset.value *= bytes;
 634                 size = get_array_size_bytes(expr->left);
 635                 if (size <= 0)
 636                         return NULL;
 637                 return alloc_int_rl(size - offset.value);
 638         }
 639
 640         /* buf = malloc(1024); */
 641         ret = get_stored_size_bytes(expr);
 642         if (ret)
 643                 return ret;
 644
 645         ret = get_stored_size_end_struct_bytes(expr);
 646         if (ret)
 647                 return ret;
 648
 649         ret = get_outer_end_struct_bytes(expr);
 650         if (ret)
 651                 return ret;
 652
 653         /* buf[4] */
 654         size = get_real_array_size(expr);
 655         if (size)
 656                 return alloc_int_rl(elements_to_bytes(expr, size));
 657
 658         /* char *foo = "BAR" */
 659         size = get_size_from_initializer(expr);
 660         if (size)
 661                 return alloc_int_rl(elements_to_bytes(expr, size));
 662
 663         size = get_bytes_from_address(expr);
 664         if (size)
 665                 return alloc_int_rl(size);
 666
 667         ret = size_from_db(expr);
 668         return filter_size_rl(ret);
 669
 670         if (rl_to_sval(ret, &sval) && sval.value == -1)
 671                 return NULL;
 672         if (ret)
 673                 return ret;
 674
 675         return NULL;
 676 }
 677
 678 int get_array_size_bytes(struct expression *expr)
 679 {
 680         struct range_list *rl;
 681         sval_t sval;
 682
 683         rl = get_array_size_bytes_rl(expr);
 684         if (!rl_to_sval(rl, &sval))
 685                 return 0;
 686         if (sval.uvalue >= INT_MAX)
 687                 return 0;
 688         return sval.value;
 689 }
 690
 691 int get_array_size_bytes_max(struct expression *expr)
 692 {
 693         struct range_list *rl;
 694         sval_t bytes;
 695
 696         rl = get_array_size_bytes_rl(expr);
 697         if (!rl)
 698                 return 0;
 699         bytes = rl_min(rl);
 700         if (bytes.value < 0)
 701                 return 0;
 702         bytes = rl_max(rl);
 703         if (bytes.uvalue >= INT_MAX)
 704                 return 0;
 705         return bytes.value;
 706 }
 707
 708 int get_array_size_bytes_min(struct expression *expr)
 709 {
 710         struct range_list *rl;
 711         struct data_range *range;
 712
 713         rl = get_array_size_bytes_rl(expr);
 714         if (!rl)
 715                 return 0;
 716
 717         FOR_EACH_PTR(rl, range) {
 718                 if (range->min.value <= 0)
 719                         return 0;
 720                 if (range->max.value <= 0)
 721                         return 0;
 722                 if (range->min.uvalue >= INT_MAX)
 723                         return 0;
 724                 return range->min.value;
 725         } END_FOR_EACH_PTR(range);
 726
 727         return 0;
 728 }
 729
 730 int get_array_size(struct expression *expr)
 731 {
 732         if (!expr)
 733                 return 0;
 734         return bytes_to_elements(expr, get_array_size_bytes_max(expr));
 735 }
 736
 737 static struct expression *strip_ampersands(struct expression *expr)
 738 {
 739         struct symbol *type;
 740
 741         if (expr->type != EXPR_PREOP)
 742                 return expr;
 743         if (expr->op != '&')
 744                 return expr;
 745         type = get_type(expr->unop);
 746         if (!type || type->type != SYM_ARRAY)
 747                 return expr;
 748         return expr->unop;
 749 }
 750
 751 static void info_record_alloction(struct expression *buffer, struct range_list *rl)
 752 {
 753         bool add_static;
 754         char *name;
 755
 756         name = get_stored_buffer_name(buffer, &add_static);
 757         if (!name)
 758                 return;
 759         if (rl && !is_whole_rl(rl))
 760                 sql_insert_function_type_size(name, show_rl(rl));
 761         else
 762                 sql_insert_function_type_size(name, "(-1)");
 763
 764         free_string(name);
 765 }
 766
 767 static void store_alloc(struct expression *expr, struct range_list *rl)
 768 {
 769         struct symbol *type;
 770
 771         rl = clone_rl(rl); // FIXME!!!
 772         if (!rl)
 773                 rl = size_to_rl(UNKNOWN_SIZE);
 774
 775         if (rl_min(rl).value != UNKNOWN_SIZE ||
 776             rl_max(rl).value != UNKNOWN_SIZE ||
 777             get_state_expr(my_size_id, expr))
 778                 set_state_expr(my_size_id, expr, alloc_estate_rl(rl));
 779
 780         type = get_type(expr);
 781         if (!type)
 782                 return;
 783         if (type->type != SYM_PTR &&
 784             type->type != SYM_ARRAY)
 785                 return;
 786         type = get_real_base_type(type);
 787         if (!type)
 788                 return;
 789 // Why not store the size for void pointers?
 790         if (type == &void_ctype)
 791                 return;
 792 // Because of 4 files that produce 30 warnings like this:
 793 // arch/x86/crypto/des3_ede_glue.c:145 __cbc_encrypt() warn: potential memory corrupting cast 8 vs 1 bytes
 794         if (type->type != SYM_BASETYPE &&
 795             type->type != SYM_PTR &&
 796             type->type != SYM_ARRAY)
 797                 return;
 798
 799         info_record_alloction(expr, rl);
 800 }
 801
 802 static bool is_array_base(struct expression *expr)
 803 {
 804         struct symbol *type;
 805
 806         type = get_type(expr);
 807         if (type && type->type == SYM_ARRAY)
 808                 return true;
 809         return false;
 810 }
 811
 812 static void match_array_assignment(struct expression *expr)
 813 {
 814         struct expression *left;
 815         struct expression *right;
 816         char *left_member, *right_member;
 817         struct range_list *rl;
 818         sval_t sval;
 819
 820         if (expr->op != '=')
 821                 return;
 822
 823         left = strip_expr(expr->left);
 824         right = strip_expr(expr->right);
 825         right = strip_ampersands(right);
 826
 827         if (!is_pointer(left) && !get_state_expr(my_size_id, expr))
 828                 return;
 829
 830         /* char buf[24] = "str"; */
 831         if (is_array_base(left))
 832                 return;
 833         if (is_allocation_function(right))
 834                 return;
 835
 836         left_member = get_member_name(left);
 837         right_member = get_member_name(right);
 838         if (left_member && right_member && strcmp(left_member, right_member) == 0)
 839                 return;
 840
 841         if (get_implied_value(right, &sval) && sval.value == 0) {
 842                 rl = alloc_int_rl(0);
 843                 goto store;
 844         }
 845
 846         rl = get_array_size_bytes_rl(right);
 847         if (!rl && __in_fake_assign)
 848                 return;
 849
 850 store:
 851         store_alloc(left, rl);
 852 }
 853
 854 static struct expression *get_variable_struct_member(struct expression *expr)
 855 {
 856         struct symbol *type, *last_member;
 857         sval_t sval;
 858
 859         /*
 860          * This is a hack.  It should look at how the size is calculated instead
 861          * of just assuming that it's the last element.  However, ugly hacks are
 862          * easier to write.
 863          */
 864
 865         type = get_type(expr);
 866         if (!type || type->type != SYM_PTR)
 867                 return NULL;
 868         type = get_real_base_type(type);
 869         if (!type || type->type != SYM_STRUCT)
 870                 return NULL;
 871         last_member = last_ptr_list((struct ptr_list *)type->symbol_list);
 872         if (!last_member || !last_member->ident)
 873                 return NULL;
 874         type = get_real_base_type(last_member);
 875         if (!type || type->type != SYM_ARRAY)
 876                 return NULL;
 877         /* Is non-zero array size */
 878         if (type->array_size) {
 879                 if (!get_implied_value(type->array_size, &sval) ||
 880                     sval.value != 0)
 881                         return NULL;
 882         }
 883
 884         return member_expression(expr, '*', last_member->ident);
 885 }
 886
 887 static void match_struct_size_helper(struct expression *pointer, struct range_list *rl)
 888 {
 889         struct range_list *buf_size;
 890         struct expression *member;
 891         sval_t sval = { .type = &ulong_ctype };
 892
 893         member = get_variable_struct_member(pointer);
 894         if (!member)
 895                 return;
 896         sval.value = bytes_per_element(pointer);
 897         if (!sval.value)
 898                 return;
 899         buf_size = rl_binop(rl, '-', alloc_rl(sval, sval));
 900         store_alloc(member, buf_size);
 901 }
 902
 903 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 904 {
 905         int size_arg = PTR_INT(_size_arg);
 906         struct expression *pointer, *right, *arg;
 907         struct range_list *rl;
 908
 909         pointer = strip_expr(expr->left);
 910         right = strip_expr(expr->right);
 911         arg = get_argument_from_call_expr(right->args, size_arg);
 912         get_absolute_rl(arg, &rl);
 913         rl = cast_rl(&ulong_ctype, rl);
 914         store_alloc(pointer, rl);
 915         match_struct_size_helper(pointer, rl);
 916 }
 917
 918 static void match_calloc(const char *fn, struct expression *expr, void *_param)
 919 {
 920         struct expression *right;
 921         struct expression *size, *nr, *mult;
 922         struct range_list *rl;
 923         int param = PTR_INT(_param);
 924
 925         right = strip_expr(expr->right);
 926         nr = get_argument_from_call_expr(right->args, param);
 927         size = get_argument_from_call_expr(right->args, param + 1);
 928         mult = binop_expression(nr, '*', size);
 929         if (get_implied_rl(mult, &rl))
 930                 store_alloc(expr->left, rl);
 931         else
 932                 store_alloc(expr->left, size_to_rl(UNKNOWN_SIZE));
 933 }
 934
 935 static void match_page(const char *fn, struct expression *expr, void *_unused)
 936 {
 937         sval_t page_size = {
 938                 .type = &int_ctype,
 939                 {.value = 4096},
 940         };
 941
 942         store_alloc(expr->left, alloc_rl(page_size, page_size));
 943 }
 944
 945 static void match_bitmap_alloc(const char *fn, struct expression *expr, void *_size_arg)
 946 {
 947         int size_arg = PTR_INT(_size_arg);
 948         struct expression *right;
 949         struct expression *arg;
 950         struct range_list *rl;
 951         sval_t int_8 = {
 952                 .type = &int_ctype,
 953                 .value = 8,
 954         };
 955
 956         right = strip_expr(expr->right);
 957         arg = get_argument_from_call_expr(right->args, size_arg);
 958         get_absolute_rl(arg, &rl);
 959         if (rl_max(rl).uvalue <= SHRT_MAX && rl_max(rl).uvalue % 8) {
 960                 sval_t max = rl_max(rl);
 961                 /* round up */
 962                 max.uvalue += 7;
 963                 rl = alloc_rl(rl_min(rl), max);
 964         }
 965         rl = rl_binop(rl, '/', alloc_rl(int_8, int_8));
 966         rl = cast_rl(&ulong_ctype, rl);
 967         store_alloc(expr->left, rl);
 968 }
 969
 970 static void match_strndup(const char *fn, struct expression *expr, void *unused)
 971 {
 972         struct expression *fn_expr;
 973         struct expression *size_expr;
 974         sval_t size;
 975
 976         fn_expr = strip_expr(expr->right);
 977         size_expr = get_argument_from_call_expr(fn_expr->args, 1);
 978         if (get_implied_max(size_expr, &size)) {
 979                 size.value++;
 980                 store_alloc(expr->left, size_to_rl(size.value));
 981         } else {
 982                 store_alloc(expr->left, size_to_rl(UNKNOWN_SIZE));
 983         }
 984 }
 985
 986 static void match_alloc_pages(const char *fn, struct expression *expr, void *_order_arg)
 987 {
 988         int order_arg = PTR_INT(_order_arg);
 989         struct expression *right;
 990         struct expression *arg;
 991         sval_t sval;
 992
 993         right = strip_expr(expr->right);
 994         arg = get_argument_from_call_expr(right->args, order_arg);
 995         if (!get_implied_value(arg, &sval))
 996                 return;
 997         if (sval.value < 0 || sval.value > 10)
 998                 return;
 999
1000         sval.type = &int_ctype;
1001         sval.value = (1 << sval.value) * 4096;
1002
1003         store_alloc(expr->left, alloc_rl(sval, sval));
1004 }
1005
1006 static int is_type_bytes(struct range_list *rl, struct expression *call, int nr)
1007 {
1008         struct symbol *type;
1009         sval_t sval;
1010
1011         if (!rl_to_sval(rl, &sval))
1012                 return 0;
1013
1014         type = get_arg_type(call->fn, nr);
1015         if (!type)
1016                 return 0;
1017         if (type->type != SYM_PTR)
1018                 return 0;
1019         type = get_real_base_type(type);
1020         if (sval.value != type_bytes(type))
1021                 return 0;
1022         return 1;
1023 }
1024
1025 static void match_call(struct expression *expr)
1026 {
1027         struct expression *arg;
1028         struct symbol *type;
1029         struct range_list *rl;
1030         int i;
1031
1032         i = -1;
1033         FOR_EACH_PTR(expr->args, arg) {
1034                 i++;
1035                 type = get_type(arg);
1036                 if (!type || (type->type != SYM_PTR && type->type != SYM_ARRAY))
1037                         continue;
1038                 rl = get_array_size_bytes_rl(arg);
1039                 if (!rl)
1040                         continue;
1041                 if (rl_min(rl).value == UNKNOWN_SIZE &&
1042                     rl_max(rl).value == UNKNOWN_SIZE)
1043                         continue;
1044                 if (is_whole_rl(rl))
1045                         continue;
1046                 if (is_type_bytes(rl, expr, i))
1047                         continue;
1048                 sql_insert_caller_info(expr, BUF_SIZE, i, "$", show_rl(rl));
1049         } END_FOR_EACH_PTR(arg);
1050 }
1051
1052 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
1053 {
1054         sval_t sval;
1055
1056         if (!estate_rl(sm->state) ||
1057             (estate_get_single_value(sm->state, &sval) &&
1058              (sval.value == -1 || sval.value == 0)))
1059                 return;
1060
1061         sql_insert_caller_info(call, BUF_SIZE, param, printed_name, sm->state->name);
1062 }
1063
1064 /*
1065  * This is slightly (very) weird because half of this stuff is handled in
1066  * smatch_parse_call_math.c which is poorly named.  But anyway, add some buf
1067  * sizes here.
1068  *
1069  */
1070 static void print_returned_allocations(int return_id, char *return_ranges, struct expression *expr)
1071 {
1072         const char *param_math;
1073         struct range_list *rl;
1074         char buf[64];
1075         sval_t sval;
1076
1077         rl = get_array_size_bytes_rl(expr);
1078         param_math = get_allocation_math(expr);
1079         if (!rl && !param_math)
1080                 return;
1081
1082         if (!param_math &&
1083             rl_to_sval(rl, &sval) &&
1084             (sval.value == -1 || sval.value == 0))
1085                 return;
1086
1087         if (param_math)
1088                 snprintf(buf, sizeof(buf), "%s[%s]", show_rl(rl), param_math);
1089         else
1090                 snprintf(buf, sizeof(buf), "%s", show_rl(rl));
1091
1092         // FIXME: don't store if you can guess the size from the type
1093         // FIXME: return if we allocate a parameter $0->bar
1094         sql_insert_return_states(return_id, return_ranges, BUF_SIZE, -1, "", buf);
1095 }
1096
1097 static void record_global_size(struct symbol *sym)
1098 {
1099         int bytes;
1100         char buf[16];
1101
1102         if (!sym->ident)
1103                 return;
1104
1105         if (!(sym->ctype.modifiers & MOD_TOPLEVEL) ||
1106             sym->ctype.modifiers & MOD_STATIC)
1107                 return;
1108
1109         bytes = get_array_size_bytes(symbol_expression(sym));
1110         if (bytes <= 1)
1111                 return;
1112
1113         snprintf(buf, sizeof(buf), "%d", bytes);
1114         sql_insert_data_info_var_sym(sym->ident->name, sym, BUF_SIZE, buf);
1115 }
1116
1117 void register_buf_size(int id)
1118 {
1119         my_size_id = id;
1120
1121         set_dynamic_states(my_size_id);
1122
1123         add_unmatched_state_hook(my_size_id, &unmatched_size_state);
1124         add_merge_hook(my_size_id, &merge_estates);
1125
1126         select_caller_info_hook(set_param_buf_size, BUF_SIZE);
1127         select_return_states_hook(BUF_SIZE, &db_returns_buf_size);
1128         add_split_return_callback(print_returned_allocations);
1129
1130         allocation_funcs = create_function_hashtable(100);
1131         add_allocation_function("malloc", &match_alloc, 0);
1132         add_allocation_function("calloc", &match_calloc, 0);
1133         add_allocation_function("memdup", &match_alloc, 1);
1134         add_allocation_function("realloc", &match_alloc, 1);
1135         if (option_project == PROJ_KERNEL) {
1136                 add_allocation_function("kmalloc", &match_alloc, 0);
1137                 add_allocation_function("kmalloc_node", &match_alloc, 0);
1138                 add_allocation_function("kmalloc_noprof", &match_alloc, 0);
1139                 add_allocation_function("kzalloc", &match_alloc, 0);
1140                 add_allocation_function("kzalloc_node", &match_alloc, 0);
1141                 add_allocation_function("kzalloc_noprof", &match_alloc, 0);
1142                 add_allocation_function("vmalloc", &match_alloc, 0);
1143                 add_allocation_function("vzalloc", &match_alloc, 0);
1144                 add_allocation_function("__vmalloc", &match_alloc, 0);
1145                 add_allocation_function("kvmalloc", &match_alloc, 0);
1146                 add_allocation_function("kcalloc", &match_calloc, 0);
1147                 add_allocation_function("kvcalloc", &match_calloc, 0);
1148                 add_allocation_function("kmalloc_array", &match_calloc, 0);
1149                 add_allocation_function("devm_kmalloc_array", &match_calloc, 1);
1150                 add_allocation_function("sock_kmalloc", &match_alloc, 1);
1151                 add_allocation_function("kmemdup", &match_alloc, 1);
1152                 add_allocation_function("memdup_user", &match_alloc, 1);
1153                 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
1154                 add_allocation_function("devm_kmalloc", &match_alloc, 1);
1155                 add_allocation_function("devm_kzalloc", &match_alloc, 1);
1156                 add_allocation_function("krealloc", &match_alloc, 1);
1157                 add_allocation_function("__alloc_bootmem", &match_alloc, 0);
1158                 add_allocation_function("alloc_bootmem", &match_alloc, 0);
1159                 add_allocation_function("kmap", &match_page, 0);
1160                 add_allocation_function("kmap_atomic", &match_page, 0);
1161                 add_allocation_function("get_zeroed_page", &match_page, 0);
1162                 add_allocation_function("alloc_page", &match_page, 0);
1163                 add_allocation_function("alloc_pages", &match_alloc_pages, 1);
1164                 add_allocation_function("alloc_pages_current", &match_alloc_pages, 1);
1165                 add_allocation_function("__get_free_pages", &match_alloc_pages, 1);
1166                 add_allocation_function("dma_alloc_contiguous", &match_alloc, 1);
1167                 add_allocation_function("dma_alloc_coherent", &match_alloc, 1);
1168                 add_allocation_function("bitmap_alloc", &match_bitmap_alloc, 0);
1169                 add_allocation_function("bitmap_alloc_node", &match_bitmap_alloc, 0);
1170                 add_allocation_function("bitmap_zalloc", &match_bitmap_alloc, 0);
1171                 add_allocation_function("devm_bitmap_alloc", &match_bitmap_alloc, 1);
1172                 add_allocation_function("devm_bitmap_zalloc", &match_bitmap_alloc, 1);
1173         }
1174
1175         add_allocation_function("strndup", match_strndup, 0);
1176         if (option_project == PROJ_KERNEL)
1177                 add_allocation_function("kstrndup", match_strndup, 0);
1178
1179         add_modification_hook(my_size_id, &set_size_undefined);
1180
1181         add_merge_hook(my_size_id, &merge_size_func);
1182
1183         if (option_info)
1184                 add_hook(record_global_size, BASE_HOOK);
1185
1186         add_hook(&match_clear_cache, AFTER_FUNC_HOOK);
1187 }
1188
1189 void register_buf_size_late(int id)
1190 {
1191         /* has to happen after match_alloc() */
1192         add_hook(&match_array_assignment, ASSIGNMENT_HOOK);
1193
1194         add_hook(&match_call, FUNCTION_CALL_HOOK);
1195         add_member_info_callback(my_size_id, struct_member_callback);
1196 }