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->type == 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 struct expression *get_struct_size_count(struct expression *expr)
 217 {
 218         /*
 219          * There are three ways that struct_size() can be implemented but
 220          * we can ignore build time constants so really there are two ways we
 221          * care about:
 222          * 1) Using __ab_c_size()
 223          * 2) Using size_add(struct_size, size_mul(elem_count, elem_size))
 224          *
 225          */
 226
 227         if (expr->type != EXPR_CALL)
 228                 return NULL;
 229
 230         if (sym_name_is("__ab_c_size", expr->fn))
 231                 return get_argument_from_call_expr(expr->args, 0);
 232
 233         if (!sym_name_is("size_add", expr->fn))
 234                 return NULL;
 235         expr = get_argument_from_call_expr(expr->args, 1);
 236         expr = strip_expr(expr);
 237         if (!expr || expr->type != EXPR_CALL ||
 238             !sym_name_is("size_mul", expr->fn))
 239                 return NULL;
 240
 241         return get_argument_from_call_expr(expr->args, 0);
 242 }
 243
 244 static struct expression *get_variable_struct_member(struct expression *expr)
 245 {
 246         struct symbol *type, *last_member;
 247         sval_t sval;
 248
 249         /*
 250          * This is a hack.  It should look at how the size is calculated instead
 251          * of just assuming that it's the last element.  However, ugly hacks are
 252          * easier to write.
 253          */
 254
 255         type = get_type(expr);
 256         if (!type || type->type != SYM_PTR)
 257                 return NULL;
 258         type = get_real_base_type(type);
 259         if (!type || type->type != SYM_STRUCT)
 260                 return NULL;
 261         last_member = last_ptr_list((struct ptr_list *)type->symbol_list);
 262         if (!last_member || !last_member->ident)
 263                 return NULL;
 264         type = get_real_base_type(last_member);
 265         if (!type || type->type != SYM_ARRAY)
 266                 return NULL;
 267         /* Is non-zero array size */
 268         if (type->array_size) {
 269                 if (!get_implied_value(type->array_size, &sval) ||
 270                     sval.value != 0)
 271                         return NULL;
 272         }
 273
 274         return member_expression(expr, '*', last_member->ident);
 275 }
 276
 277 static void match_struct_size_helper(struct expression *pointer, struct expression *size, struct expression *mod_expr)
 278 {
 279         struct expression *tmp, *count, *member;
 280         struct smatch_state *state;
 281         struct sm_state *sm;
 282
 283         if (option_project != PROJ_KERNEL)
 284                 return;
 285
 286         pointer = strip_expr(pointer);
 287         tmp = get_assigned_expr_recurse(size);
 288         if (tmp)
 289                 size = tmp;
 290         size = strip_expr(size);
 291         if (!size || !pointer)
 292                 return;
 293         count = get_struct_size_count(size);
 294         if (!count)
 295                 return;
 296         member = get_variable_struct_member(pointer);
 297
 298         db_save_type_links(member, ELEM_COUNT, count);
 299         state = alloc_compare_size(ELEM_COUNT, count);
 300         sm = set_state_expr(size_id, member, state);
 301         if (!sm)
 302                 return;
 303         add_link(count, member, mod_expr);
 304 }
 305
 306 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 307 {
 308         int size_arg = PTR_INT(_size_arg);
 309         struct expression *pointer, *call, *arg;
 310
 311         pointer = strip_expr(expr->left);
 312         call = strip_expr(expr->right);
 313         arg = get_argument_from_call_expr(call->args, size_arg);
 314         match_alloc_helper(pointer, arg, expr);
 315         match_struct_size_helper(pointer, arg, expr);
 316 }
 317
 318 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
 319 {
 320         struct smatch_state *state;
 321         int start_arg = PTR_INT(_start_arg);
 322         struct expression *pointer, *call, *arg;
 323         struct sm_state *tmp;
 324         int limit_type = ELEM_COUNT;
 325         sval_t sval;
 326
 327         pointer = strip_expr(expr->left);
 328         call = strip_expr(expr->right);
 329         arg = get_argument_from_call_expr(call->args, start_arg);
 330         if (get_implied_value(arg, &sval) &&
 331             sval.value == bytes_per_element(pointer))
 332                 arg = get_argument_from_call_expr(call->args, start_arg + 1);
 333
 334         if (arg->type == EXPR_BINOP && arg->op == '+' &&
 335             get_value(arg->right, &sval) && sval.value == 1) {
 336                 arg = arg->left;
 337                 limit_type = ELEM_LAST;
 338         }
 339
 340         state = alloc_compare_size(limit_type, arg);
 341         db_save_type_links(pointer, limit_type, arg);
 342         tmp = set_state_expr(size_id, pointer, state);
 343         if (!tmp)
 344                 return;
 345         add_link(arg, pointer, expr);
 346 }
 347
 348 static struct expression *get_size_variable_from_binop(struct expression *expr, int *limit_type)
 349 {
 350         struct smatch_state *state;
 351         struct expression *ret;
 352         struct symbol *type;
 353         sval_t orig_fixed;
 354         int offset_bytes;
 355         sval_t offset;
 356
 357         if (!get_value(expr->right, &offset))
 358                 return NULL;
 359         state = get_state_expr(size_id, expr->left);
 360         if (!state || !state->data)
 361                 return NULL;
 362
 363         type = get_type(expr->left);
 364         if (!type_is_ptr(type))
 365                 return NULL;
 366         type = get_real_base_type(type);
 367         if (!type_bytes(type))
 368                 return NULL;
 369         offset_bytes = offset.value * type_bytes(type);
 370
 371         ret = state->data;
 372         if (ret->type != EXPR_BINOP || ret->op != '+')
 373                 return NULL;
 374
 375         *limit_type = state_to_limit(state);
 376
 377         if (get_value(ret->left, &orig_fixed) && orig_fixed.value == offset_bytes)
 378                 return ret->right;
 379         if (get_value(ret->right, &orig_fixed) && orig_fixed.value == offset_bytes)
 380                 return ret->left;
 381
 382         return NULL;
 383 }
 384
 385 struct expression *get_size_variable(struct expression *buf, int *limit_type)
 386 {
 387         struct smatch_state *state;
 388         struct expression *ret;
 389
 390         buf = strip_expr(buf);
 391         if (!buf)
 392                 return NULL;
 393         if (buf->type == EXPR_BINOP && buf->op == '+') {
 394                 ret = get_size_variable_from_binop(buf, limit_type);
 395                 if (ret)
 396                         return ret;
 397         }
 398
 399         state = get_state_expr(size_id, buf);
 400         if (!state)
 401                 return NULL;
 402         *limit_type = state_to_limit(state);
 403         return state->data;
 404 }
 405
 406 struct expression *get_array_variable(struct expression *size)
 407 {
 408         struct smatch_state *state;
 409
 410         state = get_state_expr(link_id, size);
 411         if (state)
 412                 return state->data;
 413         return NULL;
 414 }
 415
 416 static void array_check(struct expression *expr)
 417 {
 418         struct expression *array;
 419         struct expression *size;
 420         struct expression *offset;
 421         char *array_str, *offset_str;
 422         int limit_type;
 423
 424         expr = strip_expr(expr);
 425         if (!is_array(expr))
 426                 return;
 427
 428         array = get_array_base(expr);
 429         size = get_size_variable(array, &limit_type);
 430         if (!size)
 431                 return;
 432         if (limit_type != ELEM_COUNT)
 433                 return;
 434         offset = get_array_offset(expr);
 435         if (!possible_comparison(size, SPECIAL_EQUAL, offset))
 436                 return;
 437         if (getting_address(expr))
 438                 return;
 439
 440         array_str = expr_to_str(array);
 441         offset_str = expr_to_str(offset);
 442         sm_warning("potentially one past the end of array '%s[%s]'", array_str, offset_str);
 443         free_string(array_str);
 444         free_string(offset_str);
 445 }
 446
 447 struct db_info {
 448         char *name;
 449         int ret;
 450 };
 451
 452 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
 453 {
 454         struct db_info *info = _info;
 455
 456         /*
 457          * If possible the limitters are tied to the struct they limit.  If we
 458          * aren't sure which struct they limit then we use them as limitters for
 459          * everything.
 460          */
 461         if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0)
 462                 info->ret = 1;
 463         return 0;
 464 }
 465
 466 static char *vsl_to_data_info_name(const char *name, struct var_sym_list *vsl)
 467 {
 468         struct var_sym *vs;
 469         struct symbol *type;
 470         static char buf[80];
 471         const char *p;
 472
 473         if (ptr_list_size((struct ptr_list *)vsl) != 1)
 474                 return NULL;
 475         vs = first_ptr_list((struct ptr_list *)vsl);
 476
 477         type = get_real_base_type(vs->sym);
 478         if (!type || type->type != SYM_PTR)
 479                 goto top_level_name;
 480         type = get_real_base_type(type);
 481         if (!type || type->type != SYM_STRUCT)
 482                 goto top_level_name;
 483         if (!type->ident)
 484                 goto top_level_name;
 485
 486         p = name;
 487         while ((name = strstr(p, "->")))
 488                 p = name + 2;
 489
 490         snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p);
 491         return alloc_sname(buf);
 492
 493 top_level_name:
 494         if (!(vs->sym->ctype.modifiers & MOD_TOPLEVEL))
 495                 return NULL;
 496         if (vs->sym->ctype.modifiers & MOD_STATIC)
 497                 snprintf(buf, sizeof(buf),"static %s", name);
 498         else
 499                 snprintf(buf, sizeof(buf),"global %s", name);
 500         return alloc_sname(buf);
 501 }
 502
 503 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
 504 {
 505         char *size_name;
 506         char *array_name = get_data_info_name(array);
 507         struct db_info db_info = {.name = array_name,};
 508
 509         size_name = vsl_to_data_info_name(name, vsl);
 510         if (!size_name)
 511                 return 0;
 512
 513         run_sql(db_limitter_callback, &db_info,
 514                 "select value from data_info where type = %d and data = '%s';",
 515                 ARRAY_LEN, size_name);
 516
 517         return db_info.ret;
 518 }
 519
 520 int buf_comparison_index_ok(struct expression *expr)
 521 {
 522         struct expression *array;
 523         struct expression *size;
 524         struct expression *offset;
 525         int limit_type;
 526         int comparison;
 527
 528         array = get_array_base(expr);
 529         size = get_size_variable(array, &limit_type);
 530         if (!size)
 531                 return 0;
 532         offset = get_array_offset(expr);
 533         comparison = get_comparison(offset, size);
 534         if (!comparison)
 535                 return 0;
 536
 537         if ((limit_type == ELEM_COUNT || limit_type == ELEM_LAST) &&
 538             (comparison == '<' || comparison == SPECIAL_UNSIGNED_LT))
 539                 return 1;
 540
 541         if (limit_type == BYTE_COUNT && bytes_per_element(array) == 1 &&
 542             (comparison == '<' || comparison == SPECIAL_UNSIGNED_LT))
 543                 return 1;
 544
 545         if (limit_type == ELEM_LAST &&
 546             (comparison == SPECIAL_LTE ||
 547              comparison == SPECIAL_UNSIGNED_LTE ||
 548              comparison == SPECIAL_EQUAL))
 549                 return 1;
 550
 551         return 0;
 552 }
 553
 554 bool buf_comp_has_bytes(struct expression *buf, struct expression *var)
 555 {
 556         struct expression *size;
 557         int limit_type;
 558         int comparison;
 559
 560         if (buf_comp2_has_bytes(buf, var))
 561                 return true;
 562
 563         size = get_size_variable(buf, &limit_type);
 564         if (!size)
 565                 return false;
 566         comparison = get_comparison(size, var);
 567         if (comparison == UNKNOWN_COMPARISON ||
 568             comparison == IMPOSSIBLE_COMPARISON)
 569                 return false;
 570
 571         if (show_special(comparison)[0] == '<' ||
 572             show_special(comparison)[0] == '=')
 573                 return true;
 574
 575         return false;
 576 }
 577
 578 bool buf_has_bytes(struct expression *buf, struct expression *var)
 579 {
 580         struct range_list *rl;
 581         int size;
 582
 583         size = get_array_size_bytes_max(buf);
 584         get_absolute_rl(var, &rl);
 585         if (size > 0 &&
 586             get_implied_rl(var, &rl) &&
 587             rl_min(rl).value <= size)
 588                 return true;
 589
 590         return buf_comp_has_bytes(buf, var);
 591 }
 592
 593 static int known_access_ok_numbers(struct expression *expr)
 594 {
 595         struct expression *array;
 596         struct expression *offset;
 597         sval_t max;
 598         int size;
 599
 600         array = get_array_base(expr);
 601         offset = get_array_offset(expr);
 602
 603         size = get_array_size(array);
 604         if (size <= 0)
 605                 return 0;
 606
 607         get_absolute_max(offset, &max);
 608         if (max.uvalue < size)
 609                 return 1;
 610         return 0;
 611 }
 612
 613 static void array_check_data_info(struct expression *expr)
 614 {
 615         struct expression *array;
 616         struct expression *offset;
 617         struct state_list *slist;
 618         struct sm_state *sm;
 619         struct compare_data *comp;
 620         char *offset_name;
 621         const char *equal_name = NULL;
 622
 623         expr = strip_expr(expr);
 624         if (!is_array(expr))
 625                 return;
 626
 627         if (known_access_ok_numbers(expr))
 628                 return;
 629         if (buf_comparison_index_ok(expr))
 630                 return;
 631
 632         array = get_array_base(expr);
 633         offset = get_array_offset(expr);
 634         offset_name = expr_to_var(offset);
 635         if (!offset_name)
 636                 return;
 637         slist = get_all_possible_equal_comparisons(offset);
 638         if (!slist)
 639                 goto free;
 640
 641         FOR_EACH_PTR(slist, sm) {
 642                 comp = sm->state->data;
 643                 if (strcmp(comp->left_var, offset_name) == 0) {
 644                         if (db_var_is_array_limit(array, comp->right_var, comp->right_vsl)) {
 645                                 equal_name = comp->right_var;
 646                                 break;
 647                         }
 648                 } else if (strcmp(comp->right_var, offset_name) == 0) {
 649                         if (db_var_is_array_limit(array, comp->left_var, comp->left_vsl)) {
 650                                 equal_name = comp->left_var;
 651                                 break;
 652                         }
 653                 }
 654         } END_FOR_EACH_PTR(sm);
 655
 656         if (equal_name) {
 657                 char *array_name = expr_to_str(array);
 658
 659                 sm_warning("potential off by one '%s[]' limit '%s'", array_name, equal_name);
 660                 free_string(array_name);
 661         }
 662
 663 free:
 664         free_slist(&slist);
 665         free_string(offset_name);
 666 }
 667
 668 static void add_allocation_function(const char *func, void *call_back, int param)
 669 {
 670         add_function_assign_hook(func, call_back, INT_PTR(param));
 671 }
 672
 673 static int is_sizeof(struct expression *expr)
 674 {
 675         const char *name;
 676
 677         if (expr->type == EXPR_SIZEOF)
 678                 return 1;
 679         name = pos_ident(expr->pos);
 680         if (name && strcmp(name, "sizeof") == 0)
 681                 return 1;
 682         return 0;
 683 }
 684
 685 static int match_size_binop(struct expression *size, struct expression *expr, int *limit_type)
 686 {
 687         int orig_type = *limit_type;
 688         struct expression *left;
 689         sval_t sval;
 690
 691         left = expr->left;
 692         if (!expr_equiv(size, left))
 693                 return 0;
 694
 695         if (expr->op == '-' &&
 696             get_value(expr->right, &sval) &&
 697             sval.value == 1 &&
 698             orig_type == ELEM_COUNT) {
 699                 *limit_type = ELEM_LAST;
 700                 return 1;
 701         }
 702
 703         if (expr->op == '+' &&
 704             get_value(expr->right, &sval) &&
 705             sval.value == 1 &&
 706             orig_type == ELEM_LAST) {
 707                 *limit_type = ELEM_COUNT;
 708                 return 1;
 709         }
 710
 711         if (expr->op == '*' &&
 712             is_sizeof(expr->right) &&
 713             orig_type == ELEM_COUNT) {
 714                 *limit_type = BYTE_COUNT;
 715                 return 1;
 716         }
 717
 718         if (expr->op == '/' &&
 719             is_sizeof(expr->right) &&
 720             orig_type == BYTE_COUNT) {
 721                 *limit_type = ELEM_COUNT;
 722                 return 1;
 723         }
 724
 725         return 0;
 726 }
 727
 728 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args, int *limit_type)
 729 {
 730         struct expression *tmp, *arg;
 731         struct expression *size;
 732         static char buf[32];
 733         int i;
 734
 735         size = get_size_variable(array, limit_type);
 736         if (!size)
 737                 return NULL;
 738
 739         if (*limit_type == USED_LAST)
 740                 *limit_type = ELEM_LAST;
 741         if (*limit_type == USED_COUNT)
 742                 *limit_type = ELEM_COUNT;
 743
 744         i = -1;
 745         FOR_EACH_PTR(args, tmp) {
 746                 i++;
 747                 arg = tmp;
 748                 if (arg == array)
 749                         continue;
 750                 if (expr_equiv(arg, size) ||
 751                     (arg->type == EXPR_BINOP &&
 752                      match_size_binop(size, arg, limit_type))) {
 753                         snprintf(buf, sizeof(buf), "==$%d", i);
 754                         return buf;
 755                 }
 756         } END_FOR_EACH_PTR(tmp);
 757
 758         return NULL;
 759 }
 760
 761 static void match_call(struct expression *call)
 762 {
 763         struct expression *arg;
 764         char *compare;
 765         int param;
 766         char buf[5];
 767         int limit_type;
 768
 769         param = -1;
 770         FOR_EACH_PTR(call->args, arg) {
 771                 param++;
 772                 if (!is_pointer(arg))
 773                         continue;
 774                 compare = buf_size_param_comparison(arg, call->args, &limit_type);
 775                 if (!compare)
 776                         continue;
 777                 snprintf(buf, sizeof(buf), "%d", limit_type);
 778                 sql_insert_caller_info(call, limit_type, param, compare, buf);
 779         } END_FOR_EACH_PTR(arg);
 780 }
 781
 782 static int get_param(int param, char **name, struct symbol **sym)
 783 {
 784         struct symbol *arg;
 785         int i;
 786
 787         i = 0;
 788         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 789                 /*
 790                  * this is a temporary hack to work around a bug (I think in sparse?)
 791                  * 2.6.37-rc1:fs/reiserfs/journal.o
 792                  * If there is a function definition without parameter name found
 793                  * after a function implementation then it causes a crash.
 794                  * int foo() {}
 795                  * int bar(char *);
 796                  */
 797                 if (arg->ident->name < (char *)100)
 798                         continue;
 799                 if (i == param) {
 800                         *name = arg->ident->name;
 801                         *sym = arg;
 802                         return TRUE;
 803                 }
 804                 i++;
 805         } END_FOR_EACH_PTR(arg);
 806
 807         return FALSE;
 808 }
 809
 810 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
 811 {
 812         struct smatch_state *state;
 813         struct expression *array_expr;
 814         struct expression *size_expr;
 815         struct symbol *size_sym;
 816         char *size_name;
 817         long param;
 818         struct sm_state *tmp;
 819         int limit_type;
 820
 821         if (strncmp(key, "==$", 3) != 0)
 822                 return;
 823         param = strtol(key + 3, NULL, 10);
 824         if (!get_param(param, &size_name, &size_sym))
 825                 return;
 826         array_expr = symbol_expression(array_sym);
 827         size_expr = symbol_expression(size_sym);
 828         limit_type = strtol(value, NULL, 10);
 829
 830         state = alloc_compare_size(limit_type, size_expr);
 831         tmp = set_state_expr(size_id, array_expr, state);
 832         if (!tmp)
 833                 return;
 834         add_link(size_expr, array_expr, NULL);
 835 }
 836
 837 static void set_implied(struct expression *call, struct expression *array_expr, char *key, char *value)
 838 {
 839         struct expression *size_expr;
 840         struct symbol *size_sym;
 841         char *size_name;
 842         long param;
 843         struct sm_state *tmp;
 844         int limit_type;
 845
 846         if (strncmp(key, "==$", 3) != 0)
 847                 return;
 848         param = strtol(key + 3, NULL, 10);
 849         if (!get_param(param, &size_name, &size_sym))
 850                 return;
 851         size_expr = symbol_expression(size_sym);
 852
 853         limit_type = strtol(value, NULL, 10);
 854         tmp = set_state_expr(size_id, array_expr, alloc_compare_size(limit_type, size_expr));
 855         if (!tmp)
 856                 return;
 857         add_link(size_expr, array_expr, call);
 858 }
 859
 860 static void munge_start_states(struct statement *stmt)
 861 {
 862         struct state_list *slist = NULL;
 863         struct sm_state *sm;
 864         struct sm_state *poss;
 865
 866         FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
 867                 if (sm->state != &merged)
 868                         continue;
 869                 /*
 870                  * screw it.  let's just assume that if one caller passes the
 871                  * size then they all do.
 872                  */
 873                 FOR_EACH_PTR(sm->possible, poss) {
 874                         if (poss->state != &merged &&
 875                             poss->state != &undefined) {
 876                                 add_ptr_list(&slist, poss);
 877                                 break;
 878                         }
 879                 } END_FOR_EACH_PTR(poss);
 880         } END_FOR_EACH_SM(sm);
 881
 882         FOR_EACH_PTR(slist, sm) {
 883                 set_state(size_id, sm->name, sm->sym, sm->state);
 884         } END_FOR_EACH_PTR(sm);
 885
 886         free_slist(&slist);
 887 }
 888
 889 static void set_used(struct expression *expr)
 890 {
 891         struct expression *parent;
 892         struct expression *array;
 893         struct expression *offset;
 894         struct sm_state *tmp;
 895         int limit_type;
 896
 897         if (expr->op != SPECIAL_INCREMENT)
 898                 return;
 899
 900         limit_type = USED_LAST;
 901         if (expr->type == EXPR_POSTOP)
 902                 limit_type = USED_COUNT;
 903
 904         parent = expr_get_parent_expr(expr);
 905         if (!parent || parent->type != EXPR_BINOP)
 906                 return;
 907         parent = expr_get_parent_expr(parent);
 908         if (!parent || !is_array(parent))
 909                 return;
 910
 911         array = get_array_base(parent);
 912         offset = get_array_offset(parent);
 913         if (offset != expr)
 914                 return;
 915
 916         tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, offset->unop));
 917         if (!tmp)
 918                 return;
 919         add_link(offset->unop, array, expr);
 920 }
 921
 922 static int match_assign_array(struct expression *expr)
 923 {
 924         // FIXME: implement
 925         return 0;
 926 }
 927
 928 static int match_assign_size(struct expression *expr)
 929 {
 930         struct expression *right, *size, *array;
 931         struct smatch_state *state;
 932         struct sm_state *tmp;
 933         int limit_type;
 934
 935         right = expr->right;
 936         size = right;
 937         if (size->type == EXPR_BINOP)
 938                 size = size->left;
 939
 940         array = get_array_variable(size);
 941         if (!array)
 942                 return 0;
 943         state = get_state_expr(size_id, array);
 944         if (!state || !state->data)
 945                 return 0;
 946
 947         limit_type = state_to_limit(state);
 948         if (limit_type < 0)
 949                 return 0;
 950
 951         if (right->type == EXPR_BINOP && !match_size_binop(size, right, &limit_type))
 952                 return 0;
 953
 954         tmp = set_state_expr(size_id, array, alloc_compare_size(limit_type, expr->left));
 955         if (!tmp)
 956                 return 0;
 957         add_link(expr->left, array, expr);
 958         return 1;
 959 }
 960
 961 static bool match_assign_smaller(struct expression *expr)
 962 {
 963         struct expression *array;
 964         int comparison;
 965         sval_t sval;
 966
 967         array = get_array_variable(expr->left);
 968         if (!array)
 969                 return false;
 970
 971         if (get_value(expr->right, &sval))
 972                 return false;
 973
 974         comparison = get_comparison(expr->left, expr->right);
 975         if (comparison == UNKNOWN_COMPARISON ||
 976             comparison == IMPOSSIBLE_COMPARISON)
 977                 return false;
 978
 979         /* This is assigning a smaller value to the variable than what it was. */
 980         if (show_special(comparison)[0] != '>')
 981                 return false;
 982
 983         /*
 984          * This module doesn't have a way to say that it's less than the limit
 985          * only that it *is* the limit.  So you might expect to set a state here
 986          * but there is already a state so all we can do is ignore the
 987          * assignment.
 988          */
 989         ignore_link_mod = expr;
 990         return true;
 991 }
 992
 993 static void match_assign(struct expression *expr)
 994 {
 995         if (expr->op != '=')
 996                 return;
 997
 998         if (is_fake_var_assign(expr))
 999                 return;
1000
1001         if (match_assign_array(expr))
1002                 return;
1003         if (match_assign_size(expr))
1004                 return;
1005         if (match_assign_smaller(expr))
1006                 return;
1007 }
1008
1009 static void match_copy(const char *fn, struct expression *expr, void *unused)
1010 {
1011         struct expression *src, *size;
1012         int src_param, size_param;
1013
1014         src = get_argument_from_call_expr(expr->args, 1);
1015         size = get_argument_from_call_expr(expr->args, 2);
1016         src = strip_expr(src);
1017         size = strip_expr(size);
1018         if (!src || !size)
1019                 return;
1020         if (src->type != EXPR_SYMBOL || size->type != EXPR_SYMBOL)
1021                 return;
1022
1023         src_param = get_param_num_from_sym(src->symbol);
1024         size_param = get_param_num_from_sym(size->symbol);
1025         if (src_param < 0 || size_param < 0)
1026                 return;
1027
1028         sql_insert_cache(call_implies, "'%s', '%s', 0, %d, %d, %d, '==$%d', '%d'",
1029                          get_base_file(), get_function(), fn_static(),
1030                          BYTE_COUNT, src_param, size_param, BYTE_COUNT);
1031 }
1032
1033 void register_buf_comparison(int id)
1034 {
1035         int i;
1036
1037         size_id = id;
1038
1039         set_dynamic_states(size_id);
1040
1041         add_unmatched_state_hook(size_id, &unmatched_state);
1042
1043         add_allocation_function("malloc", &match_alloc, 0);
1044         add_allocation_function("memdup", &match_alloc, 1);
1045         add_allocation_function("realloc", &match_alloc, 1);
1046         if (option_project == PROJ_KERNEL) {
1047                 add_allocation_function("kmalloc", &match_alloc, 0);
1048                 add_allocation_function("kzalloc", &match_alloc, 0);
1049                 add_allocation_function("vmalloc", &match_alloc, 0);
1050                 add_allocation_function("__vmalloc", &match_alloc, 0);
1051                 add_allocation_function("sock_kmalloc", &match_alloc, 1);
1052                 add_allocation_function("kmemdup", &match_alloc, 1);
1053                 add_allocation_function("memdup_user", &match_alloc, 1);
1054                 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
1055                 add_allocation_function("dma_alloc_coherent", &match_alloc, 1);
1056                 add_allocation_function("devm_kmalloc", &match_alloc, 1);
1057                 add_allocation_function("devm_kzalloc", &match_alloc, 1);
1058                 add_allocation_function("kcalloc", &match_calloc, 0);
1059                 add_allocation_function("devm_kcalloc", &match_calloc, 1);
1060                 add_allocation_function("kmalloc_array", &match_calloc, 0);
1061                 add_allocation_function("krealloc", &match_alloc, 1);
1062
1063                 add_function_hook("copy_from_user", &match_copy, NULL);
1064                 add_function_hook("__copy_from_user", &match_copy, NULL);
1065         }
1066
1067         add_hook(&array_check, OP_HOOK);
1068         add_hook(&array_check_data_info, OP_HOOK);
1069         add_hook(&set_used, OP_HOOK);
1070
1071         add_hook(&match_call, FUNCTION_CALL_HOOK);
1072         add_hook(&munge_start_states, AFTER_DEF_HOOK);
1073
1074         add_hook(&match_assign, ASSIGNMENT_HOOK);
1075
1076         for (i = BYTE_COUNT; i <= USED_COUNT; i++) {
1077                 select_call_implies_hook(i, &set_implied);
1078                 select_caller_info_hook(set_param_compare, i);
1079                 select_return_implies_hook(i, &set_implied);
1080         }
1081 }
1082
1083 void register_buf_comparison_links(int id)
1084 {
1085         link_id = id;
1086         set_dynamic_states(link_id);
1087         add_merge_hook(link_id, &merge_links);
1088         add_modification_hook_late(link_id, &match_link_modify);
1089 }