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