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