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