smatch_type_val.c

   1 /*
   2  * Copyright (C) 2013 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 plan here is to save all the possible values store to a given struct
  20  * member.
  21  *
  22  * We will load all the values in to the function_type_val table first then
  23  * run a script on that and load all the resulting values into the type_val
  24  * table.
  25  *
  26  * So in this file we want to take the union of everything assigned to the
  27  * struct member and insert it into the function_type_val at the end.
  28  *
  29  * You would think that we could use smatch_modification_hooks.c or
  30  * extra_modification_hook() here to get the information here but in the end we
  31  * need to code everything again a third time.
  32  *
  33  */
  34
  35 #include "smatch.h"
  36 #include "smatch_slist.h"
  37 #include "smatch_extra.h"
  38
  39 static int my_id;
  40
  41 static int no_type_vals;
  42
  43 struct stree *fn_type_val;
  44 struct stree *global_type_val;
  45
  46 void disable_type_val_lookups(void)
  47 {
  48         no_type_vals++;
  49 }
  50
  51 void enable_type_val_lookups(void)
  52 {
  53         no_type_vals--;
  54 }
  55
  56 static int get_vals(void *_db_vals, int argc, char **argv, char **azColName)
  57 {
  58         char **db_vals = _db_vals;
  59
  60         *db_vals = alloc_string(argv[0]);
  61         return 0;
  62 }
  63
  64 struct expr_rl {
  65         struct expression *expr;
  66         struct range_list *rl;
  67 };
  68 static struct expr_rl cached_results[24];
  69 static int res_idx;
  70
  71 static int get_cached(struct expression *expr, struct range_list **rl, int *ret)
  72 {
  73         int i;
  74
  75         *ret = 0;
  76
  77         for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
  78                 if (expr == cached_results[i].expr) {
  79                         if (cached_results[i].rl) {
  80                                 *rl = clone_rl(cached_results[i].rl);
  81                                 *ret = 1;
  82                         }
  83                         return 1;
  84                 }
  85         }
  86
  87         return 0;
  88 }
  89
  90 int get_db_type_rl(struct expression *expr, struct range_list **rl)
  91 {
  92         char *db_vals = NULL;
  93         char *member;
  94         struct range_list *tmp;
  95         struct symbol *type;
  96         int ret;
  97
  98         if (get_cached(expr, rl, &ret))
  99                 return ret;
 100
 101         if (no_type_vals)
 102                 return 0;
 103
 104         member = get_member_name(expr);
 105         if (!member)
 106                 return 0;
 107
 108         res_idx = (res_idx + 1) % ARRAY_SIZE(cached_results);
 109         cached_results[res_idx].expr = expr;
 110         cached_results[res_idx].rl = NULL;
 111
 112         run_sql(get_vals, &db_vals,
 113                 "select value from type_value where type = '%s';", member);
 114         if (!db_vals)
 115                 return 0;
 116         type = get_type(expr);
 117         str_to_rl(type, db_vals, &tmp);
 118         free_string(db_vals);
 119         if (is_whole_rl(tmp))
 120                 return 0;
 121
 122         *rl = tmp;
 123         cached_results[res_idx].rl = clone_rl(tmp);
 124
 125         return 1;
 126 }
 127
 128 static void add_type_val(char *member, struct range_list *rl)
 129 {
 130         struct smatch_state *old, *add, *new;
 131
 132         member = alloc_string(member);
 133         old = get_state_stree(fn_type_val, my_id, member, NULL);
 134         add = alloc_estate_rl(rl);
 135         if (old)
 136                 new = merge_estates(old, add);
 137         else
 138                 new = add;
 139         set_state_stree(&fn_type_val, my_id, member, NULL, new);
 140 }
 141
 142 static void add_fake_type_val(char *member, struct range_list *rl, int ignore)
 143 {
 144         struct smatch_state *old, *add, *new;
 145
 146         member = alloc_string(member);
 147         old = get_state_stree(fn_type_val, my_id, member, NULL);
 148         if (old && strcmp(old->name, "min-max") == 0)
 149                 return;
 150         if (ignore && old && strcmp(old->name, "ignore") == 0)
 151                 return;
 152         add = alloc_estate_rl(rl);
 153         if (old) {
 154                 new = merge_estates(old, add);
 155         } else {
 156                 new = add;
 157                 if (ignore)
 158                         new->name = alloc_string("ignore");
 159                 else
 160                         new->name = alloc_string("min-max");
 161         }
 162         set_state_stree(&fn_type_val, my_id, member, NULL, new);
 163 }
 164
 165 static void add_global_type_val(char *member, struct range_list *rl)
 166 {
 167         struct smatch_state *old, *add, *new;
 168
 169         member = alloc_string(member);
 170         old = get_state_stree(global_type_val, my_id, member, NULL);
 171         add = alloc_estate_rl(rl);
 172         if (old)
 173                 new = merge_estates(old, add);
 174         else
 175                 new = add;
 176         new = clone_estate_perm(new);
 177         set_state_stree_perm(&global_type_val, my_id, member, NULL, new);
 178 }
 179
 180 static int has_link_cb(void *has_link, int argc, char **argv, char **azColName)
 181 {
 182         *(int *)has_link = 1;
 183         return 0;
 184 }
 185
 186 static int is_ignored_fake_assignment(void)
 187 {
 188         struct expression *expr;
 189         struct symbol *type;
 190         char *member_name;
 191         int has_link = 0;
 192
 193         expr = get_faked_expression();
 194         if (!expr || expr->type != EXPR_ASSIGNMENT)
 195                 return 0;
 196         if (!is_void_pointer(expr->right))
 197                 return 0;
 198         member_name = get_member_name(expr->right);
 199         if (!member_name)
 200                 return 0;
 201
 202         type = get_type(expr->left);
 203         if (!type || type->type != SYM_PTR)
 204                 return 0;
 205         type = get_real_base_type(type);
 206         if (!type || type->type != SYM_STRUCT)
 207                 return 0;
 208
 209         run_sql(has_link_cb, &has_link,
 210                 "select * from data_info where type = %d and data = '%s' and value = '%s';",
 211                 TYPE_LINK, member_name, type_to_str(type));
 212         return has_link;
 213 }
 214
 215 static int is_container_of(void)
 216 {
 217         /* We already check the macro name in is_ignored_macro() */
 218         struct expression *expr;
 219         int offset;
 220
 221         expr = get_faked_expression();
 222         if (!expr || expr->type != EXPR_ASSIGNMENT)
 223                 return 0;
 224
 225         offset = get_offset_from_container_of(expr->right);
 226         if (offset < 0)
 227                 return 0;
 228         return 1;
 229 }
 230
 231 static bool is_driver_data(void)
 232 {
 233         static struct expression *prev_expr;
 234         struct expression *expr;
 235         char *name;
 236         static bool prev_ret;
 237         bool ret = false;
 238
 239         expr = get_faked_expression();
 240         if (!expr || expr->type != EXPR_ASSIGNMENT)
 241                 return false;
 242
 243         if (expr == prev_expr)
 244                 return prev_ret;
 245         prev_expr = expr;
 246
 247         name = expr_to_str(expr->right);
 248         if (!name) {
 249                 prev_ret = false;
 250                 return false;
 251         }
 252
 253         if (strstr(name, "get_drvdata(") ||
 254             strstr(name, "dev.driver_data") ||
 255             strstr(name, "dev->driver_data"))
 256                 ret = true;
 257
 258         free_string(name);
 259
 260         prev_ret = ret;
 261         return ret;
 262 }
 263
 264 static int is_ignored_macro(void)
 265 {
 266         struct expression *expr;
 267         char *name;
 268
 269         expr = get_faked_expression();
 270         if (!expr || expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 271                 return 0;
 272         name = get_macro_name(expr->right->pos);
 273         if (!name)
 274                 return 0;
 275         if (strcmp(name, "container_of") == 0)
 276                 return 1;
 277         if (strcmp(name, "rb_entry") == 0)
 278                 return 1;
 279         if (strcmp(name, "list_entry") == 0)
 280                 return 1;
 281         if (strcmp(name, "list_first_entry") == 0)
 282                 return 1;
 283         if (strcmp(name, "hlist_entry") == 0)
 284                 return 1;
 285         if (strcmp(name, "per_cpu_ptr") == 0)
 286                 return 1;
 287         if (strcmp(name, "raw_cpu_ptr") == 0)
 288                 return 1;
 289         if (strcmp(name, "this_cpu_ptr") == 0)
 290                 return 1;
 291
 292         if (strcmp(name, "TRACE_EVENT") == 0)
 293                 return 1;
 294         if (strcmp(name, "DECLARE_EVENT_CLASS") == 0)
 295                 return 1;
 296         if (strcmp(name, "DEFINE_EVENT") == 0)
 297                 return 1;
 298
 299         if (strstr(name, "for_each"))
 300                 return 1;
 301         return 0;
 302 }
 303
 304 static int is_ignored_function(void)
 305 {
 306         struct expression *expr;
 307
 308         expr = get_faked_expression();
 309         if (!expr || expr->type != EXPR_ASSIGNMENT)
 310                 return 0;
 311         expr = strip_expr(expr->right);
 312         if (!expr || expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
 313                 return 0;
 314
 315         if (sym_name_is("kmalloc", expr->fn))
 316                 return 1;
 317         if (sym_name_is("vmalloc", expr->fn))
 318                 return 1;
 319         if (sym_name_is("kvmalloc", expr->fn))
 320                 return 1;
 321         if (sym_name_is("kmalloc_array", expr->fn))
 322                 return 1;
 323         if (sym_name_is("vmalloc_array", expr->fn))
 324                 return 1;
 325         if (sym_name_is("kvmalloc_array", expr->fn))
 326                 return 1;
 327
 328         if (sym_name_is("mmu_memory_cache_alloc", expr->fn))
 329                 return 1;
 330         if (sym_name_is("kmem_alloc", expr->fn))
 331                 return 1;
 332         if (sym_name_is("alloc_pages", expr->fn))
 333                 return 1;
 334
 335         if (sym_name_is("netdev_priv", expr->fn))
 336                 return 1;
 337         if (sym_name_is("dev_get_drvdata", expr->fn))
 338                 return 1;
 339         if (sym_name_is("i2c_get_clientdata", expr->fn))
 340                 return 1;
 341         if (sym_name_is("idr_find", expr->fn))
 342                 return 1;
 343
 344         return 0;
 345 }
 346
 347 static int is_uncasted_pointer_assign(void)
 348 {
 349         struct expression *expr;
 350         struct symbol *left_type, *right_type;
 351
 352         expr = get_faked_expression();
 353         if (!expr)
 354                 return 0;
 355         if (expr->type == EXPR_PREOP || expr->type == EXPR_POSTOP) {
 356                 if (expr->op == SPECIAL_INCREMENT || expr->op == SPECIAL_DECREMENT)
 357                         return 1;
 358         }
 359         if (expr->type != EXPR_ASSIGNMENT)
 360                 return 0;
 361         left_type = get_type(expr->left);
 362         right_type = get_type(expr->right);
 363
 364         if (!left_type || !right_type)
 365                 return 0;
 366
 367         if (left_type->type == SYM_STRUCT && left_type == right_type)
 368                 return 1;
 369
 370         if (left_type->type != SYM_PTR &&
 371             left_type->type != SYM_ARRAY)
 372                 return 0;
 373         if (right_type->type != SYM_PTR &&
 374             right_type->type != SYM_ARRAY)
 375                 return 0;
 376         left_type = get_real_base_type(left_type);
 377         right_type = get_real_base_type(right_type);
 378
 379         if (left_type == right_type)
 380                 return 1;
 381         return 0;
 382 }
 383
 384 static int set_param_type(void *_type_str, int argc, char **argv, char **azColName)
 385 {
 386         char **type_str = _type_str;
 387         static char type_buf[128];
 388
 389         if (*type_str) {
 390                 if (strcmp(*type_str, argv[0]) == 0)
 391                         return 0;
 392                 strncpy(type_buf, "unknown", sizeof(type_buf));
 393                 return 0;
 394         }
 395         strncpy(type_buf, argv[0], sizeof(type_buf));
 396         *type_str = type_buf;
 397
 398         return 0;
 399 }
 400
 401 static char *db_get_parameter_type(int param)
 402 {
 403         char *ret = NULL;
 404
 405         if (!cur_func_sym)
 406                 return NULL;
 407
 408         run_sql(set_param_type, &ret,
 409                 "select value from fn_data_link where "
 410                 "file = 0x%llx and function = '%s' and static = %d and type = %d and parameter = %d and key = '$';",
 411                 (cur_func_sym->ctype.modifiers & MOD_STATIC) ? get_base_file_id() : 0,
 412                 cur_func_sym->ident->name,
 413                 !!(cur_func_sym->ctype.modifiers & MOD_STATIC),
 414                 PASSES_TYPE, param);
 415
 416         return ret;
 417 }
 418
 419 static int is_uncasted_fn_param_from_db(void)
 420 {
 421         struct expression *expr, *right;
 422         struct symbol *left_type;
 423         char left_type_name[128];
 424         int param;
 425         char *right_type_name;
 426         static struct expression *prev_expr;
 427         static int prev_ans;
 428
 429         expr = get_faked_expression();
 430
 431         if (expr == prev_expr)
 432                 return prev_ans;
 433         prev_expr = expr;
 434         prev_ans = 0;
 435
 436         if (!expr || expr->type != EXPR_ASSIGNMENT)
 437                 return 0;
 438         left_type = get_type(expr->left);
 439         if (!left_type || left_type->type != SYM_PTR)
 440                 return 0;
 441         left_type = get_real_base_type(left_type);
 442         if (!left_type || left_type->type != SYM_STRUCT)
 443                 return 0;
 444         snprintf(left_type_name, sizeof(left_type_name), "%s", type_to_str(left_type));
 445
 446         right = strip_expr(expr->right);
 447         param = get_param_num(right);
 448         if (param < 0)
 449                 return 0;
 450         right_type_name = db_get_parameter_type(param);
 451         if (!right_type_name)
 452                 return 0;
 453
 454         if (strcmp(right_type_name, left_type_name) == 0) {
 455                 prev_ans = 1;
 456                 return 1;
 457         }
 458
 459         return 0;
 460 }
 461
 462 static void match_assign_value(struct expression *expr)
 463 {
 464         char *member, *right_member;
 465         struct range_list *rl;
 466         struct symbol *type;
 467
 468         if (!cur_func_sym)
 469                 return;
 470
 471         type = get_type(expr->left);
 472         if (type && type->type == SYM_STRUCT)
 473                 return;
 474         member = get_member_name(expr->left);
 475         if (!member)
 476                 return;
 477
 478         /* if we're saying foo->mtu = bar->mtu then that doesn't add information */
 479         right_member = get_member_name(expr->right);
 480         if (right_member && strcmp(right_member, member) == 0)
 481                 return;
 482
 483         if (is_fake_call(expr->right)) {
 484                 if (is_ignored_macro())
 485                         return;
 486                 if (is_ignored_function())
 487                         return;
 488                 if (is_uncasted_pointer_assign())
 489                         return;
 490                 if (is_uncasted_fn_param_from_db())
 491                         return;
 492                 if (is_container_of())
 493                         return;
 494                 if (is_driver_data())
 495                         return;
 496                 add_fake_type_val(member, alloc_whole_rl(get_type(expr->left)), is_ignored_fake_assignment());
 497                 return;
 498         }
 499
 500         if (expr->op == '=') {
 501                 get_absolute_rl(expr->right, &rl);
 502                 rl = cast_rl(type, rl);
 503         } else {
 504                 /*
 505                  * This is a bit cheating.  We order it so this will already be set
 506                  * by smatch_extra.c and we just look up the value.
 507                  */
 508                 get_absolute_rl(expr->left, &rl);
 509         }
 510         add_type_val(member, rl);
 511 }
 512
 513 /*
 514  * If we too:  int *p = &my_struct->member then abandon all hope of tracking
 515  * my_struct->member.
 516  */
 517 static void match_assign_pointer(struct expression *expr)
 518 {
 519         struct expression *right;
 520         char *member;
 521         struct range_list *rl;
 522         struct symbol *type;
 523
 524         right = strip_expr(expr->right);
 525         if (right->type != EXPR_PREOP || right->op != '&')
 526                 return;
 527         right = strip_expr(right->unop);
 528
 529         member = get_member_name(right);
 530         if (!member)
 531                 return;
 532         type = get_type(right);
 533         rl = alloc_whole_rl(type);
 534         add_type_val(member, rl);
 535 }
 536
 537 static void match_global_assign(struct expression *expr)
 538 {
 539         char *member;
 540         struct range_list *rl;
 541         struct symbol *type;
 542
 543         type = get_type(expr->left);
 544         if (type && (type->type == SYM_ARRAY || type->type == SYM_STRUCT))
 545                 return;
 546         member = get_member_name(expr->left);
 547         if (!member)
 548                 return;
 549         get_absolute_rl(expr->right, &rl);
 550         rl = cast_rl(type, rl);
 551         add_global_type_val(member, rl);
 552 }
 553
 554 static void unop_expr(struct expression *expr)
 555 {
 556         struct range_list *rl;
 557         char *member;
 558
 559         if (expr->op != SPECIAL_DECREMENT && expr->op != SPECIAL_INCREMENT)
 560                 return;
 561
 562         expr = strip_expr(expr->unop);
 563         member = get_member_name(expr);
 564         if (!member)
 565                 return;
 566         rl = alloc_whole_rl(get_type(expr));
 567         add_type_val(member, rl);
 568 }
 569
 570 static void asm_expr(struct statement *stmt)
 571 {
 572         struct asm_operand *op;
 573         struct range_list *rl;
 574         char *member;
 575
 576         FOR_EACH_PTR(stmt->asm_outputs, op) {
 577                 member = get_member_name(op->expr);
 578                 if (!member)
 579                         continue;
 580                 rl = alloc_whole_rl(get_type(op->expr));
 581                 add_type_val(member, rl);
 582         } END_FOR_EACH_PTR(op);
 583 }
 584
 585 static void db_param_add(struct expression *expr, int param, char *key, char *value)
 586 {
 587         struct expression *arg;
 588         struct symbol *type;
 589         struct range_list *rl;
 590         char *member;
 591
 592         if (strcmp(key, "*$") != 0)
 593                 return;
 594
 595         while (expr->type == EXPR_ASSIGNMENT)
 596                 expr = strip_expr(expr->right);
 597         if (expr->type != EXPR_CALL)
 598                 return;
 599
 600         arg = get_argument_from_call_expr(expr->args, param);
 601         arg = strip_expr(arg);
 602         if (!arg)
 603                 return;
 604         type = get_member_type_from_key(arg, key);
 605         /*
 606          * The situation here is that say we memset() a void pointer to zero
 607          * then that's returned to the called as "*$ = 0;" but on the caller's
 608          * side it's not void, it's a struct.
 609          *
 610          * So the question is should we be passing that slightly bogus
 611          * information back to the caller?  Maybe, maybe not, but either way we
 612          * are not going to record it here because a struct can't be zero.
 613          *
 614          */
 615         if (type && type->type == SYM_STRUCT)
 616                 return;
 617
 618         if (arg->type != EXPR_PREOP || arg->op != '&')
 619                 return;
 620         arg = strip_expr(arg->unop);
 621
 622         member = get_member_name(arg);
 623         if (!member)
 624                 return;
 625         call_results_to_rl(expr, type, value, &rl);
 626         add_type_val(member, rl);
 627 }
 628
 629 static void match_end_func_info(struct symbol *sym)
 630 {
 631         struct sm_state *sm;
 632
 633         FOR_EACH_SM(fn_type_val, sm) {
 634                 sql_insert_function_type_value(sm->name, sm->state->name);
 635         } END_FOR_EACH_SM(sm);
 636 }
 637
 638 void clear_type_value_cache(void)
 639 {
 640         memset(cached_results, 0, sizeof(cached_results));
 641 }
 642
 643 static void match_after_func(struct symbol *sym)
 644 {
 645         free_stree(&fn_type_val);
 646 }
 647
 648 static void match_end_file(struct symbol_list *sym_list)
 649 {
 650         struct sm_state *sm;
 651
 652         FOR_EACH_SM(global_type_val, sm) {
 653                 sql_insert_function_type_value(sm->name, sm->state->name);
 654         } END_FOR_EACH_SM(sm);
 655 }
 656
 657 void register_type_val(int id)
 658 {
 659         my_id = id;
 660
 661         if (!option_info)
 662                 return;
 663
 664         add_hook(&match_assign_value, ASSIGNMENT_HOOK_AFTER);
 665         add_hook(&match_assign_pointer, ASSIGNMENT_HOOK);
 666         add_hook(&unop_expr, OP_HOOK);
 667         add_hook(&asm_expr, ASM_HOOK);
 668         select_return_states_hook(PARAM_ADD, &db_param_add);
 669         select_return_states_hook(PARAM_SET, &db_param_add);
 670
 671
 672         add_function_data((unsigned long *)&fn_type_val);
 673
 674         add_hook(&match_end_func_info, END_FUNC_HOOK);
 675         add_hook(&match_after_func, AFTER_FUNC_HOOK);
 676
 677         add_hook(&match_global_assign, GLOBAL_ASSIGNMENT_HOOK);
 678         add_hook(&match_end_file, END_FILE_HOOK);
 679 }