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