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  * We need this for code which does:
  33  *
  34  *     if (size)
  35  *         foo = malloc(size);
  36  *
  37  * We want to record that the size of "foo" is "size" even after the merge.
  38  *
  39  */
  40 static struct smatch_state *unmatched_state(struct sm_state *sm)
  41 {
  42         struct expression *size_expr;
  43         sval_t sval;
  44
  45         if (!sm->state->data)
  46                 return &undefined;
  47         size_expr = sm->state->data;
  48         if (!get_implied_value(size_expr, &sval) || sval.value != 0)
  49                 return &undefined;
  50         return sm->state;
  51 }
  52
  53 static struct smatch_state *merge_links(struct smatch_state *s1, struct smatch_state *s2)
  54 {
  55         struct expression *expr1, *expr2;
  56
  57         expr1 = s1->data;
  58         expr2 = s2->data;
  59
  60         if (expr1 && expr2 && expr_equiv(expr1, expr2))
  61                 return s1;
  62         return &merged;
  63 }
  64
  65 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
  66 {
  67         struct expression *expr;
  68         struct sm_state *tmp;
  69
  70         expr = sm->state->data;
  71         if (expr) {
  72                 set_state_expr(size_id, expr, &undefined);
  73                 set_state(link_id, sm->name, sm->sym, &undefined);
  74                 return;
  75         }
  76
  77         FOR_EACH_PTR(sm->possible, tmp) {
  78                 expr = tmp->state->data;
  79                 if (expr)
  80                         set_state_expr(size_id, expr, &undefined);
  81         } END_FOR_EACH_PTR(tmp);
  82         set_state(link_id, sm->name, sm->sym, &undefined);
  83 }
  84
  85 static struct smatch_state *alloc_expr_state(struct expression *expr)
  86 {
  87         struct smatch_state *state;
  88         char *name;
  89
  90         state = __alloc_smatch_state(0);
  91         expr = strip_expr(expr);
  92         name = expr_to_str(expr);
  93         state->name = alloc_sname(name);
  94         free_string(name);
  95         state->data = expr;
  96         return state;
  97 }
  98
  99 static int bytes_per_element(struct expression *expr)
 100 {
 101         struct symbol *type;
 102
 103         type = get_type(expr);
 104         if (!type)
 105                 return 0;
 106
 107         if (type->type != SYM_PTR && type->type != SYM_ARRAY)
 108                 return 0;
 109
 110         type = get_base_type(type);
 111         return type_bytes(type);
 112 }
 113
 114 static void db_save_type_links(struct expression *array, struct expression *size)
 115 {
 116         const char *array_name;
 117
 118         array_name = get_data_info_name(array);
 119         if (!array_name)
 120                 array_name = "";
 121         sql_insert_data_info(size, ARRAY_LEN, array_name);
 122 }
 123
 124 static void match_alloc_helper(struct expression *pointer, struct expression *size)
 125 {
 126         struct expression *tmp;
 127         struct sm_state *sm;
 128         sval_t sval;
 129         int cnt = 0;
 130
 131         pointer = strip_expr(pointer);
 132         size = strip_expr(size);
 133         if (!size || !pointer)
 134                 return;
 135
 136         while ((tmp = get_assigned_expr(size))) {
 137                 size = strip_expr(tmp);
 138                 if (cnt++ > 5)
 139                         break;
 140         }
 141
 142         if (size->type == EXPR_BINOP && size->op == '*') {
 143                 struct expression *mult_left, *mult_right;
 144
 145                 mult_left = strip_expr(size->left);
 146                 mult_right = strip_expr(size->right);
 147
 148                 if (get_implied_value(mult_left, &sval) &&
 149                     sval.value == bytes_per_element(pointer))
 150                         size = mult_right;
 151                 else if (get_implied_value(mult_right, &sval) &&
 152                     sval.value == bytes_per_element(pointer))
 153                         size = mult_left;
 154                 else
 155                         return;
 156         }
 157
 158         /* Only save links to variables, not fixed sizes */
 159         if (get_value(size, &sval))
 160                 return;
 161
 162         db_save_type_links(pointer, size);
 163         sm = set_state_expr(size_id, pointer, alloc_expr_state(size));
 164         if (!sm)
 165                 return;
 166         set_state_expr(link_id, size, alloc_expr_state(pointer));
 167 }
 168
 169 static void match_alloc(const char *fn, struct expression *expr, void *_size_arg)
 170 {
 171         int size_arg = PTR_INT(_size_arg);
 172         struct expression *pointer, *call, *arg;
 173
 174         pointer = strip_expr(expr->left);
 175         call = strip_expr(expr->right);
 176         arg = get_argument_from_call_expr(call->args, size_arg);
 177         match_alloc_helper(pointer, arg);
 178 }
 179
 180 static void match_calloc(const char *fn, struct expression *expr, void *_start_arg)
 181 {
 182         int start_arg = PTR_INT(_start_arg);
 183         struct expression *pointer, *call, *arg;
 184         struct sm_state *tmp;
 185         sval_t sval;
 186
 187         pointer = strip_expr(expr->left);
 188         call = strip_expr(expr->right);
 189         arg = get_argument_from_call_expr(call->args, start_arg);
 190         if (get_implied_value(arg, &sval) &&
 191             sval.value == bytes_per_element(pointer))
 192                 arg = get_argument_from_call_expr(call->args, start_arg + 1);
 193
 194         db_save_type_links(pointer, arg);
 195         tmp = set_state_expr(size_id, pointer, alloc_expr_state(arg));
 196         if (!tmp)
 197                 return;
 198         set_state_expr(link_id, arg, alloc_expr_state(pointer));
 199 }
 200
 201 struct expression *get_size_variable(struct expression *buf)
 202 {
 203         struct smatch_state *state;
 204
 205         state = get_state_expr(size_id, buf);
 206         if (state)
 207                 return state->data;
 208         return NULL;
 209 }
 210
 211 struct expression *get_array_variable(struct expression *size)
 212 {
 213         struct smatch_state *state;
 214
 215         state = get_state_expr(link_id, size);
 216         if (state)
 217                 return state->data;
 218         return NULL;
 219 }
 220
 221 static void array_check(struct expression *expr)
 222 {
 223         struct expression *array;
 224         struct expression *size;
 225         struct expression *offset;
 226         char *array_str, *offset_str;
 227
 228         expr = strip_expr(expr);
 229         if (!is_array(expr))
 230                 return;
 231
 232         array = get_array_base(expr);
 233         size = get_size_variable(array);
 234         if (!size)
 235                 return;
 236         offset = get_array_offset(expr);
 237         if (!possible_comparison(size, SPECIAL_EQUAL, offset))
 238                 return;
 239
 240         array_str = expr_to_str(array);
 241         offset_str = expr_to_str(offset);
 242         sm_warning("potentially one past the end of array '%s[%s]'", array_str, offset_str);
 243         free_string(array_str);
 244         free_string(offset_str);
 245 }
 246
 247 struct db_info {
 248         char *name;
 249         int ret;
 250 };
 251
 252 static int db_limitter_callback(void *_info, int argc, char **argv, char **azColName)
 253 {
 254         struct db_info *info = _info;
 255
 256         /*
 257          * If possible the limitters are tied to the struct they limit.  If we
 258          * aren't sure which struct they limit then we use them as limitters for
 259          * everything.
 260          */
 261         if (!info->name || argv[0][0] == '\0' || strcmp(info->name, argv[0]) == 0)
 262                 info->ret = 1;
 263         return 0;
 264 }
 265
 266 static char *vsl_to_data_info_name(const char *name, struct var_sym_list *vsl)
 267 {
 268         struct var_sym *vs;
 269         struct symbol *type;
 270         static char buf[80];
 271         const char *p;
 272
 273         if (ptr_list_size((struct ptr_list *)vsl) != 1)
 274                 return NULL;
 275         vs = first_ptr_list((struct ptr_list *)vsl);
 276
 277         type = get_real_base_type(vs->sym);
 278         if (!type || type->type != SYM_PTR)
 279                 goto top_level_name;
 280         type = get_real_base_type(type);
 281         if (!type || type->type != SYM_STRUCT)
 282                 goto top_level_name;
 283         if (!type->ident)
 284                 goto top_level_name;
 285
 286         p = name;
 287         while ((name = strstr(p, "->")))
 288                 p = name + 2;
 289
 290         snprintf(buf, sizeof(buf),"(struct %s)->%s", type->ident->name, p);
 291         return alloc_sname(buf);
 292
 293 top_level_name:
 294         if (!(vs->sym->ctype.modifiers & MOD_TOPLEVEL))
 295                 return NULL;
 296         if (vs->sym->ctype.modifiers & MOD_STATIC)
 297                 snprintf(buf, sizeof(buf),"static %s", name);
 298         else
 299                 snprintf(buf, sizeof(buf),"global %s", name);
 300         return alloc_sname(buf);
 301 }
 302
 303 int db_var_is_array_limit(struct expression *array, const char *name, struct var_sym_list *vsl)
 304 {
 305         char *size_name;
 306         char *array_name = get_data_info_name(array);
 307         struct db_info db_info = {.name = array_name,};
 308
 309         size_name = vsl_to_data_info_name(name, vsl);
 310         if (!size_name)
 311                 return 0;
 312
 313         run_sql(db_limitter_callback, &db_info,
 314                 "select value from data_info where type = %d and data = '%s';",
 315                 ARRAY_LEN, size_name);
 316
 317         return db_info.ret;
 318 }
 319
 320 static int known_access_ok_comparison(struct expression *expr)
 321 {
 322         struct expression *array;
 323         struct expression *size;
 324         struct expression *offset;
 325         int comparison;
 326
 327         array = get_array_base(expr);
 328         size = get_size_variable(array);
 329         if (!size)
 330                 return 0;
 331         offset = get_array_offset(expr);
 332         comparison = get_comparison(size, offset);
 333         if (comparison == '>' || comparison == SPECIAL_UNSIGNED_GT)
 334                 return 1;
 335
 336         return 0;
 337 }
 338
 339 static int known_access_ok_numbers(struct expression *expr)
 340 {
 341         struct expression *array;
 342         struct expression *offset;
 343         sval_t max;
 344         int size;
 345
 346         array = get_array_base(expr);
 347         offset = get_array_offset(expr);
 348
 349         size = get_array_size(array);
 350         if (size <= 0)
 351                 return 0;
 352
 353         get_absolute_max(offset, &max);
 354         if (max.uvalue < size)
 355                 return 1;
 356         return 0;
 357 }
 358
 359 static void array_check_data_info(struct expression *expr)
 360 {
 361         struct expression *array;
 362         struct expression *offset;
 363         struct state_list *slist;
 364         struct sm_state *sm;
 365         struct compare_data *comp;
 366         char *offset_name;
 367         const char *equal_name = NULL;
 368
 369         expr = strip_expr(expr);
 370         if (!is_array(expr))
 371                 return;
 372
 373         if (known_access_ok_numbers(expr))
 374                 return;
 375         if (known_access_ok_comparison(expr))
 376                 return;
 377
 378         array = get_array_base(expr);
 379         offset = get_array_offset(expr);
 380         offset_name = expr_to_var(offset);
 381         if (!offset_name)
 382                 return;
 383         slist = get_all_possible_equal_comparisons(offset);
 384         if (!slist)
 385                 goto free;
 386
 387         FOR_EACH_PTR(slist, sm) {
 388                 comp = sm->state->data;
 389                 if (strcmp(comp->left_var, offset_name) == 0) {
 390                         if (db_var_is_array_limit(array, comp->right_var, comp->right_vsl)) {
 391                                 equal_name = comp->right_var;
 392                                 break;
 393                         }
 394                 } else if (strcmp(comp->right_var, offset_name) == 0) {
 395                         if (db_var_is_array_limit(array, comp->left_var, comp->left_vsl)) {
 396                                 equal_name = comp->left_var;
 397                                 break;
 398                         }
 399                 }
 400         } END_FOR_EACH_PTR(sm);
 401
 402         if (equal_name) {
 403                 char *array_name = expr_to_str(array);
 404
 405                 sm_warning("potential off by one '%s[]' limit '%s'", array_name, equal_name);
 406                 free_string(array_name);
 407         }
 408
 409 free:
 410         free_slist(&slist);
 411         free_string(offset_name);
 412 }
 413
 414 static void add_allocation_function(const char *func, void *call_back, int param)
 415 {
 416         add_function_assign_hook(func, call_back, INT_PTR(param));
 417 }
 418
 419 static char *buf_size_param_comparison(struct expression *array, struct expression_list *args)
 420 {
 421         struct expression *arg;
 422         struct expression *size;
 423         static char buf[32];
 424         int i;
 425
 426         size = get_size_variable(array);
 427         if (!size)
 428                 return NULL;
 429
 430         i = -1;
 431         FOR_EACH_PTR(args, arg) {
 432                 i++;
 433                 if (arg == array)
 434                         continue;
 435                 if (!expr_equiv(arg, size))
 436                         continue;
 437                 snprintf(buf, sizeof(buf), "==$%d", i);
 438                 return buf;
 439         } END_FOR_EACH_PTR(arg);
 440
 441         return NULL;
 442 }
 443
 444 static void match_call(struct expression *call)
 445 {
 446         struct expression *arg;
 447         char *compare;
 448         int param;
 449
 450         param = -1;
 451         FOR_EACH_PTR(call->args, arg) {
 452                 param++;
 453                 if (!is_pointer(arg))
 454                         continue;
 455                 compare = buf_size_param_comparison(arg, call->args);
 456                 if (!compare)
 457                         continue;
 458                 sql_insert_caller_info(call, ARRAY_LEN, param, "$", compare);
 459         } END_FOR_EACH_PTR(arg);
 460 }
 461
 462 static int get_param(int param, char **name, struct symbol **sym)
 463 {
 464         struct symbol *arg;
 465         int i;
 466
 467         i = 0;
 468         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 469                 /*
 470                  * this is a temporary hack to work around a bug (I think in sparse?)
 471                  * 2.6.37-rc1:fs/reiserfs/journal.o
 472                  * If there is a function definition without parameter name found
 473                  * after a function implementation then it causes a crash.
 474                  * int foo() {}
 475                  * int bar(char *);
 476                  */
 477                 if (arg->ident->name < (char *)100)
 478                         continue;
 479                 if (i == param) {
 480                         *name = arg->ident->name;
 481                         *sym = arg;
 482                         return TRUE;
 483                 }
 484                 i++;
 485         } END_FOR_EACH_PTR(arg);
 486
 487         return FALSE;
 488 }
 489
 490 static void set_param_compare(const char *array_name, struct symbol *array_sym, char *key, char *value)
 491 {
 492         struct expression *array_expr;
 493         struct expression *size_expr;
 494         struct symbol *size_sym;
 495         char *size_name;
 496         long param;
 497         struct sm_state *tmp;
 498
 499         if (strncmp(value, "==$", 3) != 0)
 500                 return;
 501         param = strtol(value + 3, NULL, 10);
 502         if (!get_param(param, &size_name, &size_sym))
 503                 return;
 504         array_expr = symbol_expression(array_sym);
 505         size_expr = symbol_expression(size_sym);
 506
 507         tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
 508         if (!tmp)
 509                 return;
 510         set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
 511 }
 512
 513 static void set_arraysize_arg(const char *array_name, struct symbol *array_sym, char *key, char *value)
 514 {
 515         struct expression *array_expr;
 516         struct expression *size_expr;
 517         struct symbol *size_sym;
 518         char *size_name;
 519         long param;
 520         struct sm_state *tmp;
 521
 522         param = strtol(key, NULL, 10);
 523         if (!get_param(param, &size_name, &size_sym))
 524                 return;
 525         array_expr = symbol_expression(array_sym);
 526         size_expr = symbol_expression(size_sym);
 527
 528         tmp = set_state_expr(size_id, array_expr, alloc_expr_state(size_expr));
 529         if (!tmp)
 530                 return;
 531         set_state_expr(link_id, size_expr, alloc_expr_state(array_expr));
 532 }
 533
 534 static void munge_start_states(struct statement *stmt)
 535 {
 536         struct state_list *slist = NULL;
 537         struct sm_state *sm;
 538         struct sm_state *poss;
 539
 540         FOR_EACH_MY_SM(size_id, __get_cur_stree(), sm) {
 541                 if (sm->state != &merged)
 542                         continue;
 543                 /*
 544                  * screw it.  let's just assume that if one caller passes the
 545                  * size then they all do.
 546                  */
 547                 FOR_EACH_PTR(sm->possible, poss) {
 548                         if (poss->state != &merged &&
 549                             poss->state != &undefined) {
 550                                 add_ptr_list(&slist, poss);
 551                                 break;
 552                         }
 553                 } END_FOR_EACH_PTR(poss);
 554         } END_FOR_EACH_SM(sm);
 555
 556         FOR_EACH_PTR(slist, sm) {
 557                 set_state(size_id, sm->name, sm->sym, sm->state);
 558         } END_FOR_EACH_PTR(sm);
 559
 560         free_slist(&slist);
 561 }
 562
 563 void register_buf_comparison(int id)
 564 {
 565         size_id = id;
 566
 567         add_unmatched_state_hook(size_id, &unmatched_state);
 568
 569         add_allocation_function("malloc", &match_alloc, 0);
 570         add_allocation_function("memdup", &match_alloc, 1);
 571         add_allocation_function("realloc", &match_alloc, 1);
 572         if (option_project == PROJ_KERNEL) {
 573                 add_allocation_function("kmalloc", &match_alloc, 0);
 574                 add_allocation_function("kzalloc", &match_alloc, 0);
 575                 add_allocation_function("vmalloc", &match_alloc, 0);
 576                 add_allocation_function("__vmalloc", &match_alloc, 0);
 577                 add_allocation_function("sock_kmalloc", &match_alloc, 1);
 578                 add_allocation_function("kmemdup", &match_alloc, 1);
 579                 add_allocation_function("kmemdup_user", &match_alloc, 1);
 580                 add_allocation_function("dma_alloc_attrs", &match_alloc, 1);
 581                 add_allocation_function("pci_alloc_consistent", &match_alloc, 1);
 582                 add_allocation_function("pci_alloc_coherent", &match_alloc, 1);
 583                 add_allocation_function("devm_kmalloc", &match_alloc, 1);
 584                 add_allocation_function("devm_kzalloc", &match_alloc, 1);
 585                 add_allocation_function("kcalloc", &match_calloc, 0);
 586                 add_allocation_function("devm_kcalloc", &match_calloc, 1);
 587                 add_allocation_function("kmalloc_array", &match_calloc, 0);
 588                 add_allocation_function("krealloc", &match_alloc, 1);
 589         }
 590
 591         add_hook(&array_check, OP_HOOK);
 592         add_hook(&array_check_data_info, OP_HOOK);
 593
 594         add_hook(&match_call, FUNCTION_CALL_HOOK);
 595         select_caller_info_hook(set_param_compare, ARRAY_LEN);
 596         select_caller_info_hook(set_arraysize_arg, ARRAYSIZE_ARG);
 597         add_hook(&munge_start_states, AFTER_DEF_HOOK);
 598 }
 599
 600 void register_buf_comparison_links(int id)
 601 {
 602         link_id = id;
 603         add_merge_hook(link_id, &merge_links);
 604         add_modification_hook(link_id, &match_link_modify);
 605 }