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