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