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 int get_db_type_rl(struct expression *expr, struct range_list **rl)
  66 {
  67         char *db_vals = NULL;
  68         char *member;
  69         struct range_list *tmp;
  70         struct symbol *type;
  71
  72         member = get_member_name(expr);
  73         if (!member)
  74                 return 0;
  75
  76         run_sql(get_vals, &db_vals,
  77                 "select value from type_value where type = '%s';", member);
  78         free_string(member);
  79         if (!db_vals)
  80                 return 0;
  81         type = get_type(expr);
  82         str_to_rl(type, db_vals, &tmp);
  83         free_string(db_vals);
  84         if (is_whole_rl(tmp))
  85                 return 0;
  86         *rl = tmp;
  87
  88         return 1;
  89 }
  90
  91 static void add_type_val(char *member, struct range_list *rl)
  92 {
  93         struct smatch_state *old, *add, *new;
  94
  95         member = alloc_string(member);
  96         old = get_state_stree(fn_type_val, my_id, member, NULL);
  97         add = alloc_estate_rl(rl);
  98         if (old)
  99                 new = merge_estates(old, add);
 100         else
 101                 new = add;
 102         set_state_stree(&fn_type_val, my_id, member, NULL, new);
 103 }
 104
 105 static void add_fake_type_val(char *member, struct range_list *rl, int ignore)
 106 {
 107         struct smatch_state *old, *add, *new;
 108
 109         member = alloc_string(member);
 110         old = get_state_stree(fn_type_val, my_id, member, NULL);
 111         if (old && strcmp(old->name, "min-max") == 0)
 112                 return;
 113         if (ignore && old && strcmp(old->name, "ignore") == 0)
 114                 return;
 115         add = alloc_estate_rl(rl);
 116         if (old) {
 117                 new = merge_estates(old, add);
 118         } else {
 119                 new = add;
 120                 if (ignore)
 121                         new->name = alloc_string("ignore");
 122                 else
 123                         new->name = alloc_string("min-max");
 124         }
 125         set_state_stree(&fn_type_val, my_id, member, NULL, new);
 126 }
 127
 128 static void add_global_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(global_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         new = clone_estate_perm(new);
 140         set_state_stree_perm(&global_type_val, my_id, member, NULL, new);
 141 }
 142
 143 static int has_link_cb(void *has_link, int argc, char **argv, char **azColName)
 144 {
 145         *(int *)has_link = 1;
 146         return 0;
 147 }
 148
 149 static int is_ignored_fake_assignment(void)
 150 {
 151         struct expression *expr;
 152         struct symbol *type;
 153         char *member_name;
 154         int has_link = 0;
 155
 156         expr = get_faked_expression();
 157         if (!expr || expr->type != EXPR_ASSIGNMENT)
 158                 return 0;
 159         if (!is_void_pointer(expr->right))
 160                 return 0;
 161         member_name = get_member_name(expr->right);
 162         if (!member_name)
 163                 return 0;
 164
 165         type = get_type(expr->left);
 166         if (!type || type->type != SYM_PTR)
 167                 return 0;
 168         type = get_real_base_type(type);
 169         if (!type || type->type != SYM_STRUCT)
 170                 return 0;
 171
 172         run_sql(has_link_cb, &has_link,
 173                 "select * from data_info where type = %d and data = '%s' and value = '%s';",
 174                 TYPE_LINK, member_name, type_to_str(type));
 175         return has_link;
 176 }
 177
 178 static int is_container_of(void)
 179 {
 180         /* We already check the macro name in is_ignored_macro() */
 181         struct expression *expr;
 182         int offset;
 183
 184         expr = get_faked_expression();
 185         if (!expr || expr->type != EXPR_ASSIGNMENT)
 186                 return 0;
 187
 188         offset = get_offset_from_container_of(expr->right);
 189         if (offset < 0)
 190                 return 0;
 191         return 1;
 192 }
 193
 194 static int is_ignored_macro(void)
 195 {
 196         struct expression *expr;
 197         char *name;
 198
 199         expr = get_faked_expression();
 200         if (!expr || expr->type != EXPR_ASSIGNMENT)
 201                 return 0;
 202         name = get_macro_name(expr->right->pos);
 203         if (!name)
 204                 return 0;
 205         if (strcmp(name, "container_of") == 0)
 206                 return 1;
 207         if (strcmp(name, "rb_entry") == 0)
 208                 return 1;
 209         if (strcmp(name, "list_entry") == 0)
 210                 return 1;
 211         if (strcmp(name, "list_first_entry") == 0)
 212                 return 1;
 213         if (strcmp(name, "hlist_entry") == 0)
 214                 return 1;
 215         if (strstr(name, "for_each"))
 216                 return 1;
 217         return 0;
 218 }
 219
 220 static int is_ignored_function(void)
 221 {
 222         struct expression *expr;
 223
 224         expr = get_faked_expression();
 225         if (!expr || expr->type != EXPR_ASSIGNMENT)
 226                 return 0;
 227         expr = strip_expr(expr->right);
 228         if (!expr || expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
 229                 return 0;
 230
 231         if (sym_name_is("kmalloc", expr->fn))
 232                 return 1;
 233         if (sym_name_is("netdev_priv", expr->fn))
 234                 return 1;
 235
 236         return 0;
 237 }
 238
 239 static int is_uncasted_function(void)
 240 {
 241         struct expression *expr;
 242         struct symbol *left_type, *right_type;
 243
 244         expr = get_faked_expression();
 245         if (!expr || expr->type != EXPR_ASSIGNMENT)
 246                 return 0;
 247         if (expr->right->type != EXPR_CALL)
 248                 return 0;
 249         left_type = get_type(expr->left);
 250         right_type = get_type(expr->right);
 251
 252         if (!left_type || !right_type)
 253                 return 0;
 254         if (left_type->type != SYM_PTR || right_type->type != SYM_PTR)
 255                 return 0;
 256         left_type = get_real_base_type(left_type);
 257         right_type = get_real_base_type(right_type);
 258
 259         if (left_type == right_type)
 260                 return 1;
 261         return 0;
 262 }
 263
 264 static int set_param_type(void *_type_str, int argc, char **argv, char **azColName)
 265 {
 266         char **type_str = _type_str;
 267         static char type_buf[128];
 268
 269         if (*type_str) {
 270                 if (strcmp(*type_str, argv[0]) == 0)
 271                         return 0;
 272                 strncpy(type_buf, "unknown", sizeof(type_buf));
 273                 return 0;
 274         }
 275         strncpy(type_buf, argv[0], sizeof(type_buf));
 276         *type_str = type_buf;
 277
 278         return 0;
 279 }
 280
 281 static char *db_get_parameter_type(int param)
 282 {
 283         char *ret = NULL;
 284
 285         if (!cur_func_sym)
 286                 return NULL;
 287
 288         run_sql(set_param_type, &ret,
 289                 "select value from fn_data_link where "
 290                 "file = '%s' and function = '%s' and static = %d and type = %d and parameter = %d and key = '$';",
 291                 (cur_func_sym->ctype.modifiers & MOD_STATIC) ? get_base_file() : "extern",
 292                 cur_func_sym->ident->name,
 293                 !!(cur_func_sym->ctype.modifiers & MOD_STATIC),
 294                 PASSES_TYPE, param);
 295
 296         return ret;
 297 }
 298
 299 static int is_uncasted_fn_param_from_db(void)
 300 {
 301         struct expression *expr, *right;
 302         struct symbol *left_type;
 303         char left_type_name[128];
 304         int param;
 305         char *right_type_name;
 306         static struct expression *prev_expr;
 307         static int prev_ans;
 308
 309         expr = get_faked_expression();
 310
 311         if (expr == prev_expr)
 312                 return prev_ans;
 313         prev_expr = expr;
 314         prev_ans = 0;
 315
 316         if (!expr || expr->type != EXPR_ASSIGNMENT)
 317                 return 0;
 318         left_type = get_type(expr->left);
 319         if (!left_type || left_type->type != SYM_PTR)
 320                 return 0;
 321         left_type = get_real_base_type(left_type);
 322         if (!left_type || left_type->type != SYM_STRUCT)
 323                 return 0;
 324         snprintf(left_type_name, sizeof(left_type_name), "%s", type_to_str(left_type));
 325
 326         right = strip_expr(expr->right);
 327         param = get_param_num(right);
 328         if (param < 0)
 329                 return 0;
 330         right_type_name = db_get_parameter_type(param);
 331         if (!right_type_name)
 332                 return 0;
 333
 334         if (strcmp(right_type_name, left_type_name) == 0) {
 335                 prev_ans = 1;
 336                 return 1;
 337         }
 338
 339         return 0;
 340 }
 341
 342 static void match_assign_value(struct expression *expr)
 343 {
 344         char *member, *right_member;
 345         struct range_list *rl;
 346         struct symbol *type;
 347
 348         type = get_type(expr->left);
 349         if (type && type->type == SYM_STRUCT)
 350                 return;
 351
 352         member = get_member_name(expr->left);
 353         if (!member)
 354                 return;
 355
 356         /* if we're saying foo->mtu = bar->mtu then that doesn't add information */
 357         right_member = get_member_name(expr->right);
 358         if (right_member && strcmp(right_member, member) == 0)
 359                 goto free;
 360
 361         if (is_fake_call(expr->right)) {
 362                 if (is_ignored_macro())
 363                         goto free;
 364                 if (is_ignored_function())
 365                         goto free;
 366                 if (is_uncasted_function())
 367                         goto free;
 368                 if (is_uncasted_fn_param_from_db())
 369                         goto free;
 370                 if (is_container_of())
 371                         goto free;
 372                 add_fake_type_val(member, alloc_whole_rl(get_type(expr->left)), is_ignored_fake_assignment());
 373                 goto free;
 374         }
 375
 376         if (expr->op == '=') {
 377                 get_absolute_rl(expr->right, &rl);
 378                 rl = cast_rl(type, rl);
 379         } else {
 380                 /*
 381                  * This is a bit cheating.  We order it so this will already be set
 382                  * by smatch_extra.c and we just look up the value.
 383                  */
 384                 get_absolute_rl(expr->left, &rl);
 385         }
 386         add_type_val(member, rl);
 387 free:
 388         free_string(right_member);
 389         free_string(member);
 390 }
 391
 392 /*
 393  * If we too:  int *p = &my_struct->member then abandon all hope of tracking
 394  * my_struct->member.
 395  */
 396 static void match_assign_pointer(struct expression *expr)
 397 {
 398         struct expression *right;
 399         char *member;
 400         struct range_list *rl;
 401         struct symbol *type;
 402
 403         right = strip_expr(expr->right);
 404         if (right->type != EXPR_PREOP || right->op != '&')
 405                 return;
 406         right = strip_expr(right->unop);
 407
 408         member = get_member_name(right);
 409         if (!member)
 410                 return;
 411         type = get_type(right);
 412         rl = alloc_whole_rl(type);
 413         add_type_val(member, rl);
 414         free_string(member);
 415 }
 416
 417 static void match_global_assign(struct expression *expr)
 418 {
 419         char *member;
 420         struct range_list *rl;
 421         struct symbol *type;
 422
 423         type = get_type(expr->left);
 424         if (type && (type->type == SYM_ARRAY || type->type == SYM_STRUCT))
 425                 return;
 426         member = get_member_name(expr->left);
 427         if (!member)
 428                 return;
 429         get_absolute_rl(expr->right, &rl);
 430         rl = cast_rl(type, rl);
 431         add_global_type_val(member, rl);
 432         free_string(member);
 433 }
 434
 435 static void unop_expr(struct expression *expr)
 436 {
 437         struct range_list *rl;
 438         char *member;
 439
 440         if (expr->op != SPECIAL_DECREMENT && expr->op != SPECIAL_INCREMENT)
 441                 return;
 442
 443         expr = strip_expr(expr->unop);
 444         member = get_member_name(expr);
 445         if (!member)
 446                 return;
 447         rl = alloc_whole_rl(get_type(expr));
 448         add_type_val(member, rl);
 449         free_string(member);
 450 }
 451
 452 static void asm_expr(struct statement *stmt)
 453 {
 454         struct expression *expr;
 455         struct range_list *rl;
 456         char *member;
 457         int state = 0;
 458
 459         FOR_EACH_PTR(stmt->asm_outputs, expr) {
 460                 switch (state) {
 461                 case 0: /* identifier */
 462                 case 1: /* constraint */
 463                         state++;
 464                         continue;
 465                 case 2: /* expression */
 466                         state = 0;
 467                         member = get_member_name(expr);
 468                         if (!member)
 469                                 continue;
 470                         rl = alloc_whole_rl(get_type(expr));
 471                         add_type_val(member, rl);
 472                         free_string(member);
 473                         continue;
 474                 }
 475         } END_FOR_EACH_PTR(expr);
 476 }
 477
 478 static void db_param_add(struct expression *expr, int param, char *key, char *value)
 479 {
 480         struct expression *arg;
 481         struct symbol *type;
 482         struct range_list *rl;
 483         char *member;
 484
 485         if (strcmp(key, "*$") != 0)
 486                 return;
 487
 488         while (expr->type == EXPR_ASSIGNMENT)
 489                 expr = strip_expr(expr->right);
 490         if (expr->type != EXPR_CALL)
 491                 return;
 492
 493         arg = get_argument_from_call_expr(expr->args, param);
 494         arg = strip_expr(arg);
 495         if (!arg)
 496                 return;
 497         type = get_member_type_from_key(arg, key);
 498         if (arg->type != EXPR_PREOP || arg->op != '&')
 499                 return;
 500         arg = strip_expr(arg->unop);
 501
 502         member = get_member_name(arg);
 503         if (!member)
 504                 return;
 505         call_results_to_rl(expr, type, value, &rl);
 506         add_type_val(member, rl);
 507         free_string(member);
 508 }
 509
 510 static void match_end_func_info(struct symbol *sym)
 511 {
 512         struct sm_state *sm;
 513
 514         FOR_EACH_SM(fn_type_val, sm) {
 515                 sql_insert_function_type_value(sm->name, sm->state->name);
 516         } END_FOR_EACH_SM(sm);
 517 }
 518
 519 static void match_after_func(struct symbol *sym)
 520 {
 521         free_stree(&fn_type_val);
 522 }
 523
 524 static void match_end_file(struct symbol_list *sym_list)
 525 {
 526         struct sm_state *sm;
 527
 528         FOR_EACH_SM(global_type_val, sm) {
 529                 sql_insert_function_type_value(sm->name, sm->state->name);
 530         } END_FOR_EACH_SM(sm);
 531 }
 532
 533 void register_type_val(int id)
 534 {
 535         if (!option_info)
 536                 return;
 537
 538         my_id = id;
 539
 540         add_hook(&match_assign_value, ASSIGNMENT_HOOK_AFTER);
 541         add_hook(&match_assign_pointer, ASSIGNMENT_HOOK);
 542         add_hook(&unop_expr, OP_HOOK);
 543         add_hook(&asm_expr, ASM_HOOK);
 544         select_return_states_hook(PARAM_ADD, &db_param_add);
 545         select_return_states_hook(PARAM_SET, &db_param_add);
 546
 547
 548         add_hook(&match_inline_start, INLINE_FN_START);
 549         add_hook(&match_inline_end, INLINE_FN_END);
 550
 551         add_hook(&match_end_func_info, END_FUNC_HOOK);
 552         add_hook(&match_after_func, AFTER_FUNC_HOOK);
 553
 554         add_hook(&match_global_assign, GLOBAL_ASSIGNMENT_HOOK);
 555         add_hook(&match_end_file, END_FILE_HOOK);
 556 }