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