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