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