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