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