smatch_buf_comparison.c

   1 /*
   2  * Copyright (C) 2012 Oracle.
   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 /*
  19  * The point here is to store that a buffer has x bytes even if we don't know
  20  * the value of x.
  21  *
  22  */
  23
  24 #include "smatch.h"
  25 #include "smatch_extra.h"
  26 #include "smatch_slist.h"
  27
  28 static int size_id;
  29 static int link_id;
  30
  31 /*
  32  * There is a bunch of code which does this:
  33  *
  34  *     if (size)
  35  *         foo = malloc(size);
  36  *
  37  * So if "size" is non-zero then the size of "foo" is size.  But really it's
  38  * also true if size is zero.  It's just better to assume to not trample over
  39  * the data that we have by merging &undefined states.
  40  *
  41  */
  42 static struct smatch_state *unmatched_state(struct sm_state *sm)
  43 {
  44         return sm->state;
  45 }
  46
  47 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
  48 {
  49         struct expression *expr1, *expr2;
  50
  51         expr1 = s1->data;
  52         expr2 = s2->data;
  53
  54         if (expr1 && expr2 && expr_equiv(expr1, expr2))
  55                 return s1;
  56         return &merged;
  57 }
  58
  59 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
  60 {
  61         struct expression *expr;
  62         struct sm_state *tmp;
  63
  64         expr = sm->state->data;
  65         if (expr) {
  66                 set_state_expr(size_id, expr, &undefined);
  67                 set_state(link_id, sm->name, sm->sym, &undefined);
  68                 return;
  69         }
  70
  71         FOR_EACH_PTR(sm->possible, tmp) {
  72                 expr = tmp->state->data;
  73                 if (expr)
  74                         set_state_expr(size_id, expr, &undefined);
  75         } END_FOR_EACH_PTR(tmp);
  76         set_state(link_id, sm->name, sm->sym, &undefined);
  77 }
  78
  79 static const char *limit_map[] = {
  80         "byte_count",
  81         "elem_count",
  82         "elem_last",
  83         "used_count",
  84         "used_last",
  85 };
  86
  87 int state_to_limit(struct smatch_state *state)
  88 {
  89         int i;
  90
  91         if (!state || !state->data)
  92                 return -1;
  93
  94         for (i = 0; i < ARRAY_SIZE(limit_map); i++) {
  95                 if (strncmp(state->name, limit_map[i], strlen(limit_map[i])) == 0)
  96                         return i + BYTE_COUNT;
  97         }
  98
  99         return -1;
 100 }
 101
 102 const char *limit_type_str(unsigned int limit_type)
 103 {
 104         if (limit_type - BYTE_COUNT >= ARRAY_SIZE(limit_map)) {
 105                 sm_msg("internal: wrong size type %u", limit_type);
 106                 return "unknown";
 107         }
 108
 109         return limit_map[limit_type - BYTE_COUNT];
 110 }
 111
 112 static struct smatch_state *alloc_compare_size(int limit_type, struct expression *expr)
 113 {
 114         struct smatch_state *state;
 115         char *name;
 116         char buf[256];
 117
 118         state = __alloc_smatch_state(0);
 119         expr = strip_expr(expr);
 120         name = expr_to_str(expr);
 121         snprintf(buf, sizeof(buf), "%s %s", limit_type_str(limit_type), name);
 122         state->name = alloc_sname(buf);
 123         free_string(name);
 124         state->data = expr;
 125         return state;
 126 }
 127
 128 static int bytes_per_element(struct expression *expr)
 129 {
 130         struct symbol *type;
 131
 132         type = get_type(expr);
 133         if (!type)
 134                 return 0;
 135
 136         if (type->type != SYM_PTR && type->type != SYM_ARRAY)
 137                 return 0;
 138
 139         type = get_base_type(type);
 140         return type_bytes(type);
 141 }
 142
 143 static void db_save_type_links(struct expression *array, int type_limit, struct expression *size)
 144 {
 145         const char *array_name;
 146
 147         array_name = get_data_info_name(array);
 148         if (!array_name)
 149                 array_name = "";
 150         sql_insert_data_info(size, type_limit, array_name);
 151 }
 152
 153 static void match_alloc_helper(struct expression *pointer, struct expression *size)
 154 {
 155         struct smatch_state *state;
 156         struct expression *tmp;
 157         struct sm_state *sm;
 158         int limit_type = ELEM_COUNT;
 159         sval_t sval;
 160         int cnt = 0;
 161
 162         pointer = strip_expr(pointer);
 163         size = strip_expr(size);
 164         if (!size || !pointer)
 165                 return;
 166
 167         while ((tmp = get_assigned_expr(size))) {
 168                 size = strip_expr(tmp);
 169                 if (cnt++ > 5)
 170                         break;
 171         }
 172
 173         if (size->type == EXPR_BINOP && size->op == '*') {
 174                 struct expression *mult_left, *mult_right;
 175
 176                 mult_left = strip_expr(size->left);
 177                 mult_right = strip_expr(size->right);
 178
 179                 if (get_implied_value(mult_left, &sval) &&
 180                     sval.value == bytes_per_element(pointer))
 181                         size = mult_right;
 182                 else if (get_implied_value(mult_right, &sval) &&
 183                     sval.value == bytes_per_element(pointer))
 184                         size = mult_left;
 185                 else
 186                         return;
 187         }
 188
 189         /* Only save links to variables, not fixed sizes */
 190         if (get_value(size, &sval))
 191                 return;
 192
 193         if (size->type == EXPR_BINOP && size->op == '+' &&
 194             get_value(size->right, &sval) && sval.value == 1) {
 195                 size = size->left;
 196                 limit_type = ELEM_LAST;
 197         }
 198
 199         db_save_type_links(pointer, limit_type, size);
 200         state = alloc_compare_size(limit_type, size);
 201         sm = set_state_expr(size_id, pointer, state);
 202         if (!sm)
 203                 return;
 204         set_state_expr(link_id, size, alloc_state_expr(pointer));
 205 }
 206
 207 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 208 {
 209         int size_arg = PTR_INT(_size_arg);
 210         struct expression *pointer, *call, *arg;
 211
 212         pointer = strip_expr(expr->left);
 213         call = strip_expr(expr->right);
 214         arg = get_argument_from_call_expr(call->args, size_arg);
 215         match_alloc_helper(pointer, arg);
 216 }
 217
 218 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
 219 {
 220         struct smatch_state *state;
 221         int start_arg = PTR_INT(_start_arg);
 222         struct expression *pointer, *call, *arg;
 223         struct sm_state *tmp;
 224         int limit_type = ELEM_COUNT;
 225         sval_t sval;
 226
 227         pointer = strip_expr(expr->left);
 228         call = strip_expr(expr->right);
 229         arg = get_argument_from_call_expr(call->args, start_arg);
 230         if (get_implied_value(arg, &sval) &&
 231             sval.value == bytes_per_element(pointer))
 232                 arg = get_argument_from_call_expr(call->args, start_arg + 1);
 233
 234         if (arg->type == EXPR_BINOP && arg->op == '+' &&
 235             get_value(arg->right, &sval) && sval.value == 1) {
 236                 arg = arg->left;
 237                 limit_type = ELEM_LAST;
 238         }
 239
 240         state = alloc_compare_size(limit_type, arg);
 241         db_save_type_links(pointer, limit_type, arg);
 242         tmp = set_state_expr(size_id, pointer, state);
 243         if (!tmp)
 244                 return;
 245         set_state_expr(link_id, arg, alloc_state_expr(pointer));
 246 }
 247
 248 static struct expression *get_size_variable_from_binop(struct expression *expr, int *limit_type)
 249 {
 250         struct smatch_state *state;
 251         struct expression *ret;
 252         struct symbol *type;
 253         sval_t orig_fixed;
 254         int offset_bytes;
 255         sval_t offset;
 256
 257         if (!get_value(expr->right, &offset))
 258                 return NULL;
 259         state = get_state_expr(size_id, expr->left);
 260         if (!state || !state->data)
 261                 return NULL;
 262
 263         type = get_type(expr->left);
 264         if (!type_is_ptr(type))
 265                 return NULL;
 266         type = get_real_base_type(type);
 267         if (!type_bytes(type))
 268                 return NULL;
 269         offset_bytes = offset.value * type_bytes(type);
 270
 271         ret = state->data;
 272         if (ret->type != EXPR_BINOP || ret->op != '+')
 273                 return NULL;
 274
 275         *limit_type = state_to_limit(state);
 276
 277         if (get_value(ret->left, &orig_fixed) && orig_fixed.value == offset_bytes)
 278                 return ret->right;
 279         if (get_value(ret->right, &orig_fixed) && orig_fixed.value == offset_bytes)
 280                 return ret->left;
 281
 282         return NULL;
 283 }
 284
 285 struct expression *get_size_variable(struct expression *buf, int *limit_type)
 286 {
 287         struct smatch_state *state;
 288         struct expression *ret;
 289
 290         buf = strip_expr(buf);
 291         if (!buf)
 292                 return NULL;
 293         if (buf->type == EXPR_BINOP && buf->op == '+') {
 294                 ret = get_size_variable_from_binop(buf, limit_type);
 295                 if (ret)
 296                         return ret;
 297         }
 298
 299         state = get_state_expr(size_id, buf);
 300         if (!state)
 301                 return NULL;
 302         *limit_type = state_to_limit(state);
 303         return state->data;
 304 }
 305
 306 struct expression *get_array_variable(struct expression *size)
 307 {
 308         struct smatch_state *state;
 309
 310         state = get_state_expr(link_id, size);
 311         if (state)
 312                 return state->data;
 313         return NULL;
 314 }
 315
 316 static void array_check(struct expression *expr)
 317 {
 318         struct expression *array;
 319         struct expression *size;
 320         struct expression *offset;
 321         char *array_str, *offset_str;
 322         int limit_type;
 323
 324         expr = strip_expr(expr);
 325         if (!is_array(expr))
 326                 return;
 327
 328         array = get_array_base(expr);
 329         size = get_size_variable(array, &limit_type);
 330         if (!size)
 331                 return;
 332         if (limit_type != ELEM_COUNT)
 333                 return;
 334         offset = get_array_offset(expr);
 335         if (!possible_comparison(size, SPECIAL_EQUAL, offset))
 336                 return;
 337         if (getting_address(expr))
 338                 return;
 339
 340         array_str = expr_to_str(array);
 341         offset_str = expr_to_str(offset);
 342         sm_warning("potentially one past the end of array '%s[%s]'", array_str, offset_str);
 343         free_string(array_str);
 344         free_string(offset_str);
 345 }
 346
 347 struct db_info {
 348         char *name;
 349         int ret;
 350 };
 351
 352 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
 353 {
 354         struct db_info *info = _info;
 355
 356         /*
 357          * If possible the limitters are tied to the struct they limit.  If we
 358          * aren't sure which struct they limit then we use them as limitters for
 359          * everything.
 360          */
 361         if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0)
 362                 info->ret = 1;
 363         return 0;
 364 }
 365
 366 static char *vsl_to_data_info_name(const char *name, struct var_sym_list *vsl)
 367 {
 368         struct var_sym *vs;
 369         struct symbol *type;
 370         static char buf[80];
 371         const char *p;
 372
 373         if (ptr_list_size((struct ptr_list *)vsl) != 1)
 374                 return NULL;
 375         vs = first_ptr_list((struct ptr_list *)vsl);
 376
 377         type = get_real_base_type(vs->sym);
 378         if (!type || type->type != SYM_PTR)
 379                 goto top_level_name;
 380         type = get_real_base_type(type);
 381         if (!type || type->type != SYM_STRUCT)
 382                 goto top_level_name;
 383         if (!type->ident)
 384                 goto top_level_name;
 385
 386         p = name;
 387         while ((name = strstr(p, "->")))
 388                 p = name + 2;
 389
 390         snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p);
 391         return alloc_sname(buf);
 392
 393 top_level_name:
 394         if (!(vs->sym->ctype.modifiers & MOD_TOPLEVEL))
 395                 return NULL;
 396         if (vs->sym->ctype.modifiers & MOD_STATIC)
 397                 snprintf(buf, sizeof(buf),"static %s", name);
 398         else
 399                 snprintf(buf, sizeof(buf),"global %s", name);
 400         return alloc_sname(buf);
 401 }
 402
 403 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
 404 {
 405         char *size_name;
 406         char *array_name = get_data_info_name(array);
 407         struct db_info db_info = {.name = array_name,};
 408
 409         size_name = vsl_to_data_info_name(name, vsl);
 410         if (!size_name)
 411                 return 0;
 412
 413         run_sql(db_limitter_callback, &db_info,
 414                 "select value from data_info where type = %d and data = '%s';",
 415                 ARRAY_LEN, size_name);
 416
 417         return db_info.ret;
 418 }
 419
 420 int buf_comparison_index_ok(struct expression *expr)
 421 {
 422         struct expression *array;
 423         struct expression *size;
 424         struct expression *offset;
 425         int limit_type;
 426         int comparison;
 427
 428         array = get_array_base(expr);
 429         size = get_size_variable(array, &limit_type);
 430         if (!size)
 431                 return 0;
 432         offset = get_array_offset(expr);
 433         comparison = get_comparison(offset, size);
 434         if (!comparison)
 435                 return 0;
 436
 437         if ((limit_type == ELEM_COUNT || limit_type == ELEM_LAST) &&
 438             (comparison == '<' || comparison == SPECIAL_UNSIGNED_LT))
 439                 return 1;
 440         if (limit_type == ELEM_LAST &&
 441             (comparison == SPECIAL_LTE ||
 442              comparison == SPECIAL_UNSIGNED_LTE ||
 443              comparison == SPECIAL_EQUAL))
 444                 return 1;
 445
 446         return 0;
 447 }
 448
 449 static int known_access_ok_numbers(struct expression *expr)
 450 {
 451         struct expression *array;
 452         struct expression *offset;
 453         sval_t max;
 454         int size;
 455
 456         array = get_array_base(expr);
 457         offset = get_array_offset(expr);
 458
 459         size = get_array_size(array);
 460         if (size <= 0)
 461                 return 0;
 462
 463         get_absolute_max(offset, &max);
 464         if (max.uvalue < size)
 465                 return 1;
 466         return 0;
 467 }
 468
 469 static void array_check_data_info(struct expression *expr)
 470 {
 471         struct expression *array;
 472         struct expression *offset;
 473         struct state_list *slist;
 474         struct sm_state *sm;
 475         struct compare_data *comp;
 476         char *offset_name;
 477         const char *equal_name = NULL;
 478
 479         expr = strip_expr(expr);
 480         if (!is_array(expr))
 481                 return;
 482
 483         if (known_access_ok_numbers(expr))
 484                 return;
 485         if (buf_comparison_index_ok(expr))
 486                 return;
 487
 488         array = get_array_base(expr);
 489         offset = get_array_offset(expr);
 490         offset_name = expr_to_var(offset);
 491         if (!offset_name)
 492                 return;
 493         slist = get_all_possible_equal_comparisons(offset);
 494         if (!slist)
 495                 goto free;
 496
 497         FOR_EACH_PTR(slist, sm) {
 498                 comp = sm->state->data;
 499                 if (strcmp(comp->left_var, offset_name) == 0) {
 500                         if (db_var_is_array_limit(array, comp->right_var, comp->right_vsl)) {
 501                                 equal_name = comp->right_var;
 502                                 break;
 503                         }
 504                 } else if (strcmp(comp->right_var, offset_name) == 0) {
 505                         if (db_var_is_array_limit(array, comp->left_var, comp->left_vsl)) {
 506                                 equal_name = comp->left_var;
 507                                 break;
 508                         }
 509                 }
 510         } END_FOR_EACH_PTR(sm);
 511
 512         if (equal_name) {
 513                 char *array_name = expr_to_str(array);
 514
 515                 sm_warning("potential off by one '%s[]' limit '%s'", array_name, equal_name);
 516                 free_string(array_name);
 517         }
 518
 519 free:
 520         free_slist(&slist);
 521         free_string(offset_name);
 522 }
 523
 524 static void add_allocation_function(const char *func, void *call_back, int param)
 525 {
 526         add_function_assign_hook(func, call_back, INT_PTR(param));
 527 }
 528
 529 static int is_sizeof(struct expression *expr)
 530 {
 531         const char *name;
 532
 533         if (expr->type == EXPR_SIZEOF)
 534                 return 1;
 535         name = pos_ident(expr->pos);
 536         if (name && strcmp(name, "sizeof") == 0)
 537                 return 1;
 538         return 0;
 539 }
 540
 541 static int match_size_binop(struct expression *size, struct expression *expr, int *limit_type)
 542 {
 543         int orig_type = *limit_type;
 544         struct expression *left;
 545         sval_t sval;
 546
 547         left = expr->left;
 548         if (!expr_equiv(size, left))
 549                 return 0;
 550
 551         if (expr->op == '-' &&
 552             get_value(expr->right, &sval) &&
 553             sval.value == 1 &&
 554             orig_type == ELEM_COUNT) {
 555                 *limit_type = ELEM_LAST;
 556                 return 1;
 557         }
 558
 559         if (expr->op == '+' &&
 560             get_value(expr->right, &sval) &&
 561             sval.value == 1 &&
 562             orig_type == ELEM_LAST) {
 563                 *limit_type = ELEM_COUNT;
 564                 return 1;
 565         }
 566
 567         if (expr->op == '*' &&
 568             is_sizeof(expr->right) &&
 569             orig_type == ELEM_COUNT) {
 570                 *limit_type = BYTE_COUNT;
 571                 return 1;
 572         }
 573
 574         if (expr->op == '/' &&
 575             is_sizeof(expr->right) &&
 576             orig_type == BYTE_COUNT) {
 577                 *limit_type = ELEM_COUNT;
 578                 return 1;
 579         }
 580
 581         return 0;
 582 }
 583
 584 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args, int *limit_type)
 585 {
 586         struct expression *tmp, *arg;
 587         struct expression *size;
 588         static char buf[32];
 589         int i;
 590
 591         size = get_size_variable(array, limit_type);
 592         if (!size)
 593                 return NULL;
 594
 595         if (*limit_type == USED_LAST)
 596                 *limit_type = ELEM_LAST;
 597         if (*limit_type == USED_COUNT)
 598                 *limit_type = ELEM_COUNT;
 599
 600         i = -1;
 601         FOR_EACH_PTR(args, tmp) {
 602                 i++;
 603                 arg = tmp;
 604                 if (arg == array)
 605                         continue;
 606                 if (expr_equiv(arg, size) ||
 607                     (arg->type == EXPR_BINOP &&
 608                      match_size_binop(size, arg, limit_type))) {
 609                         snprintf(buf, sizeof(buf), "==$%d", i);
 610                         return buf;
 611                 }
 612         } END_FOR_EACH_PTR(tmp);
 613
 614         return NULL;
 615 }
 616
 617 static void match_call(struct expression *call)
 618 {
 619         struct expression *arg;
 620         char *compare;
 621         int param;
 622         char buf[5];
 623         int limit_type;
 624
 625         param = -1;
 626         FOR_EACH_PTR(call->args, arg) {
 627                 param++;
 628                 if (!is_pointer(arg))
 629                         continue;
 630                 compare = buf_size_param_comparison(arg, call->args, &limit_type);
 631                 if (!compare)
 632                         continue;
 633                 snprintf(buf, sizeof(buf), "%d", limit_type);
 634                 sql_insert_caller_info(call, limit_type, param, compare, buf);
 635         } END_FOR_EACH_PTR(arg);
 636 }
 637
 638 static int get_param(int param, char **name, struct symbol **sym)
 639 {
 640         struct symbol *arg;
 641         int i;
 642
 643         i = 0;
 644         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 645                 /*
 646                  * this is a temporary hack to work around a bug (I think in sparse?)
 647                  * 2.6.37-rc1:fs/reiserfs/journal.o
 648                  * If there is a function definition without parameter name found
 649                  * after a function implementation then it causes a crash.
 650                  * int foo() {}
 651                  * int bar(char *);
 652                  */
 653                 if (arg->ident->name < (char *)100)
 654                         continue;
 655                 if (i == param) {
 656                         *name = arg->ident->name;
 657                         *sym = arg;
 658                         return TRUE;
 659                 }
 660                 i++;
 661         } END_FOR_EACH_PTR(arg);
 662
 663         return FALSE;
 664 }
 665
 666 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
 667 {
 668         struct smatch_state *state;
 669         struct expression *array_expr;
 670         struct expression *size_expr;
 671         struct symbol *size_sym;
 672         char *size_name;
 673         long param;
 674         struct sm_state *tmp;
 675         int limit_type;
 676
 677         if (strncmp(key, "==$", 3) != 0)
 678                 return;
 679         param = strtol(key + 3, NULL, 10);
 680         if (!get_param(param, &size_name, &size_sym))
 681                 return;
 682         array_expr = symbol_expression(array_sym);
 683         size_expr = symbol_expression(size_sym);
 684         limit_type = strtol(value, NULL, 10);
 685
 686         state = alloc_compare_size(limit_type, size_expr);
 687         tmp = set_state_expr(size_id, array_expr, state);
 688         if (!tmp)
 689                 return;
 690         set_state_expr(link_id, size_expr, alloc_state_expr(array_expr));
 691 }
 692
 693 static void set_implied(struct expression *call, struct expression *array_expr, char *key, char *value)
 694 {
 695         struct expression *size_expr;
 696         struct symbol *size_sym;
 697         char *size_name;
 698         long param;
 699         struct sm_state *tmp;
 700         int limit_type;
 701
 702         if (strncmp(key, "==$", 3) != 0)
 703                 return;
 704         param = strtol(key + 3, NULL, 10);
 705         if (!get_param(param, &size_name, &size_sym))
 706                 return;
 707         size_expr = symbol_expression(size_sym);
 708
 709         limit_type = strtol(value, NULL, 10);
 710         tmp = set_state_expr(size_id, array_expr, alloc_compare_size(limit_type, size_expr));
 711         if (!tmp)
 712                 return;
 713         set_state_expr(link_id, size_expr, alloc_state_expr(array_expr));
 714 }
 715
 716 static void munge_start_states(struct statement *stmt)
 717 {
 718         struct state_list *slist = NULL;
 719         struct sm_state *sm;
 720         struct sm_state *poss;
 721
 722         FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
 723                 if (sm->state != &merged)
 724                         continue;
 725                 /*
 726                  * screw it.  let's just assume that if one caller passes the
 727                  * size then they all do.
 728                  */
 729                 FOR_EACH_PTR(sm->possible, poss) {
 730                         if (poss->state != &merged &&
 731                             poss->state != &undefined) {
 732                                 add_ptr_list(&slist, poss);
 733                                 break;
 734                         }
 735                 } END_FOR_EACH_PTR(poss);
 736         } END_FOR_EACH_SM(sm);
 737
 738         FOR_EACH_PTR(slist, sm) {
 739                 set_state(size_id, sm->name, sm->sym, sm->state);
 740         } END_FOR_EACH_PTR(sm);
 741
 742         free_slist(&slist);
 743 }
 744
 745 static void set_used(struct expression *expr)
 746 {
 747         struct expression *parent;
 748         struct expression *array;
 749         struct expression *offset;
 750         struct sm_state *tmp;
 751         int limit_type;
 752
 753         if (expr->op != SPECIAL_INCREMENT)
 754                 return;
 755
 756         limit_type = USED_LAST;
 757         if (expr->type == EXPR_POSTOP)
 758                 limit_type = USED_COUNT;
 759
 760         parent = expr_get_parent_expr(expr);
 761         if (!parent || parent->type != EXPR_BINOP)
 762                 return;
 763         parent = expr_get_parent_expr(parent);
 764         if (!parent || !is_array(parent))
 765                 return;
 766
 767         array = get_array_base(parent);
 768         offset = get_array_offset(parent);
 769         if (offset != expr)
 770                 return;
 771
 772         tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, offset->unop));
 773         if (!tmp)
 774                 return;
 775         set_state_expr(link_id, offset->unop, alloc_state_expr(array));
 776 }
 777
 778 static int match_assign_array(struct expression *expr)
 779 {
 780         // FIXME: implement
 781         return 0;
 782 }
 783
 784 static int match_assign_size(struct expression *expr)
 785 {
 786         struct expression *right, *size, *array;
 787         struct smatch_state *state;
 788         struct sm_state *tmp;
 789         int limit_type;
 790
 791         right = expr->right;
 792         size = right;
 793         if (size->type == EXPR_BINOP)
 794                 size = size->left;
 795
 796         array = get_array_variable(size);
 797         if (!array)
 798                 return 0;
 799         state = get_state_expr(size_id, array);
 800         if (!state || !state->data)
 801                 return 0;
 802
 803         limit_type = state_to_limit(state);
 804         if (limit_type < 0)
 805                 return 0;
 806
 807         if (right->type == EXPR_BINOP && !match_size_binop(size, right, &limit_type))
 808                 return 0;
 809
 810         tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, expr->left));
 811         if (!tmp)
 812                 return 0;
 813         set_state_expr(link_id, expr->left, alloc_state_expr(array));
 814         return 1;
 815 }
 816
 817 static void match_assign(struct expression *expr)
 818 {
 819         if (expr->op != '=')
 820                 return;
 821
 822         if (match_assign_array(expr))
 823                 return;
 824         match_assign_size(expr);
 825 }
 826
 827 static void match_copy(const char *fn, struct expression *expr, void *unused)
 828 {
 829         struct expression *src, *size;
 830         int src_param, size_param;
 831
 832         src = get_argument_from_call_expr(expr->args, 1);
 833         size = get_argument_from_call_expr(expr->args, 2);
 834         src = strip_expr(src);
 835         size = strip_expr(size);
 836         if (!src || !size)
 837                 return;
 838         if (src->type != EXPR_SYMBOL || size->type != EXPR_SYMBOL)
 839                 return;
 840
 841         src_param = get_param_num_from_sym(src->symbol);
 842         size_param = get_param_num_from_sym(size->symbol);
 843         if (src_param < 0 || size_param < 0)
 844                 return;
 845
 846         sql_insert_cache(call_implies, "'%s', '%s', 0, %d, %d, %d, '==$%d', '%d'",
 847                          get_base_file(), get_function(), fn_static(),
 848                          BYTE_COUNT, src_param, size_param, BYTE_COUNT);
 849 }
 850
 851 void register_buf_comparison(int id)
 852 {
 853         int i;
 854
 855         size_id = id;
 856
 857         set_dynamic_states(size_id);
 858
 859         add_unmatched_state_hook(size_id, &unmatched_state);
 860
 861         add_allocation_function("malloc", &match_alloc, 0);
 862         add_allocation_function("memdup", &match_alloc, 1);
 863         add_allocation_function("realloc", &match_alloc, 1);
 864         if (option_project == PROJ_KERNEL) {
 865                 add_allocation_function("kmalloc", &match_alloc, 0);
 866                 add_allocation_function("kzalloc", &match_alloc, 0);
 867                 add_allocation_function("vmalloc", &match_alloc, 0);
 868                 add_allocation_function("__vmalloc", &match_alloc, 0);
 869                 add_allocation_function("sock_kmalloc", &match_alloc, 1);
 870                 add_allocation_function("kmemdup", &match_alloc, 1);
 871                 add_allocation_function("memdup_user", &match_alloc, 1);
 872                 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
 873                 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
 874                 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
 875                 add_allocation_function("devm_kmalloc", &match_alloc, 1);
 876                 add_allocation_function("devm_kzalloc", &match_alloc, 1);
 877                 add_allocation_function("kcalloc", &match_calloc, 0);
 878                 add_allocation_function("devm_kcalloc", &match_calloc, 1);
 879                 add_allocation_function("kmalloc_array", &match_calloc, 0);
 880                 add_allocation_function("krealloc", &match_alloc, 1);
 881
 882                 add_function_hook("copy_from_user", &match_copy, NULL);
 883                 add_function_hook("__copy_from_user", &match_copy, NULL);
 884         }
 885
 886         add_hook(&array_check, OP_HOOK);
 887         add_hook(&array_check_data_info, OP_HOOK);
 888         add_hook(&set_used, OP_HOOK);
 889
 890         add_hook(&match_call, FUNCTION_CALL_HOOK);
 891         add_hook(&munge_start_states, AFTER_DEF_HOOK);
 892
 893         add_hook(&match_assign, ASSIGNMENT_HOOK);
 894
 895         for (i = BYTE_COUNT; i <= USED_COUNT; i++) {
 896                 select_call_implies_hook(i, &set_implied);
 897                 select_caller_info_hook(set_param_compare, i);
 898                 select_return_implies_hook(i, &set_implied);
 899         }
 900 }
 901
 902 void register_buf_comparison_links(int id)
 903 {
 904         link_id = id;
 905         set_dynamic_states(link_id);
 906         add_merge_hook(link_id, &merge_links);
 907         add_modification_hook(link_id, &match_link_modify);
 908 }