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_ignored_macro(void)
 179 {
 180         struct expression *expr;
 181         char *name;
 182
 183         expr = get_faked_expression();
 184         if (!expr || expr->type != EXPR_ASSIGNMENT)
 185                 return 0;
 186         name = get_macro_name(expr->right->pos);
 187         if (!name)
 188                 return 0;
 189         if (strcmp(name, "container_of") == 0)
 190                 return 1;
 191         if (strcmp(name, "rb_entry") == 0)
 192                 return 1;
 193         if (strcmp(name, "list_entry") == 0)
 194                 return 1;
 195         if (strcmp(name, "list_first_entry") == 0)
 196                 return 1;
 197         if (strcmp(name, "hlist_entry") == 0)
 198                 return 1;
 199         if (strstr(name, "for_each"))
 200                 return 1;
 201         return 0;
 202 }
 203
 204 static int is_ignored_function(void)
 205 {
 206         struct expression *expr;
 207
 208         expr = get_faked_expression();
 209         if (!expr || expr->type != EXPR_ASSIGNMENT)
 210                 return 0;
 211         expr = strip_expr(expr->right);
 212         if (!expr || expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
 213                 return 0;
 214
 215         if (sym_name_is("kmalloc", expr->fn))
 216                 return 1;
 217         if (sym_name_is("netdev_priv", expr->fn))
 218                 return 1;
 219
 220         return 0;
 221 }
 222
 223 static int is_uncasted_function(void)
 224 {
 225         struct expression *expr;
 226         struct symbol *left_type, *right_type;
 227
 228         expr = get_faked_expression();
 229         if (!expr || expr->type != EXPR_ASSIGNMENT)
 230                 return 0;
 231         if (expr->right->type != EXPR_CALL)
 232                 return 0;
 233         left_type = get_type(expr->left);
 234         right_type = get_type(expr->right);
 235
 236         if (!left_type || !right_type)
 237                 return 0;
 238         if (left_type->type != SYM_PTR || right_type->type != SYM_PTR)
 239                 return 0;
 240         left_type = get_real_base_type(left_type);
 241         right_type = get_real_base_type(right_type);
 242
 243         if (left_type == right_type)
 244                 return 1;
 245         return 0;
 246 }
 247
 248 static int set_param_type(void *_type_str, int argc, char **argv, char **azColName)
 249 {
 250         char **type_str = _type_str;
 251         static char type_buf[128];
 252
 253         if (*type_str) {
 254                 if (strcmp(*type_str, argv[0]) == 0)
 255                         return 0;
 256                 strncpy(type_buf, "unknown", sizeof(type_buf));
 257                 return 0;
 258         }
 259         strncpy(type_buf, argv[0], sizeof(type_buf));
 260         *type_str = type_buf;
 261
 262         return 0;
 263 }
 264
 265 static char *db_get_parameter_type(int param)
 266 {
 267         char *ret = NULL;
 268
 269         if (!cur_func_sym)
 270                 return NULL;
 271
 272         run_sql(set_param_type, &ret,
 273                 "select value from fn_data_link where "
 274                 "file = '%s' and function = '%s' and static = %d and type = %d and parameter = %d and key = '$';",
 275                 (cur_func_sym->ctype.modifiers & MOD_STATIC) ? get_base_file() : "extern",
 276                 cur_func_sym->ident->name,
 277                 !!(cur_func_sym->ctype.modifiers & MOD_STATIC),
 278                 PASSES_TYPE, param);
 279
 280         return ret;
 281 }
 282
 283 static int is_uncasted_fn_param_from_db(void)
 284 {
 285         struct expression *expr, *right;
 286         struct symbol *left_type;
 287         char left_type_name[128];
 288         int param;
 289         char *right_type_name;
 290         static struct expression *prev_expr;
 291         static int prev_ans;
 292
 293         expr = get_faked_expression();
 294
 295         if (expr == prev_expr)
 296                 return prev_ans;
 297         prev_expr = expr;
 298         prev_ans = 0;
 299
 300         if (!expr || expr->type != EXPR_ASSIGNMENT)
 301                 return 0;
 302         left_type = get_type(expr->left);
 303         if (!left_type || left_type->type != SYM_PTR)
 304                 return 0;
 305         left_type = get_real_base_type(left_type);
 306         if (!left_type || left_type->type != SYM_STRUCT)
 307                 return 0;
 308         snprintf(left_type_name, sizeof(left_type_name), "%s", type_to_str(left_type));
 309
 310         right = strip_expr(expr->right);
 311         param = get_param_num(right);
 312         if (param < 0)
 313                 return 0;
 314         right_type_name = db_get_parameter_type(param);
 315         if (!right_type_name)
 316                 return 0;
 317
 318         if (strcmp(right_type_name, left_type_name) == 0) {
 319                 prev_ans = 1;
 320                 return 1;
 321         }
 322
 323         return 0;
 324 }
 325
 326 static void match_assign_value(struct expression *expr)
 327 {
 328         char *member, *right_member;
 329         struct range_list *rl;
 330         struct symbol *type;
 331
 332         type = get_type(expr->left);
 333         if (type && type->type == SYM_STRUCT)
 334                 return;
 335
 336         member = get_member_name(expr->left);
 337         if (!member)
 338                 return;
 339
 340         /* if we're saying foo->mtu = bar->mtu then that doesn't add information */
 341         right_member = get_member_name(expr->right);
 342         if (right_member && strcmp(right_member, member) == 0)
 343                 goto free;
 344
 345         if (is_fake_call(expr->right)) {
 346                 if (is_ignored_macro())
 347                         goto free;
 348                 if (is_ignored_function())
 349                         goto free;
 350                 if (is_uncasted_function())
 351                         goto free;
 352                 if (is_uncasted_fn_param_from_db())
 353                         goto free;
 354                 add_fake_type_val(member, alloc_whole_rl(get_type(expr->left)), is_ignored_fake_assignment());
 355                 goto free;
 356         }
 357
 358         if (expr->op == '=') {
 359                 get_absolute_rl(expr->right, &rl);
 360                 rl = cast_rl(type, rl);
 361         } else {
 362                 /*
 363                  * This is a bit cheating.  We order it so this will already be set
 364                  * by smatch_extra.c and we just look up the value.
 365                  */
 366                 get_absolute_rl(expr->left, &rl);
 367         }
 368         add_type_val(member, rl);
 369 free:
 370         free_string(right_member);
 371         free_string(member);
 372 }
 373
 374 /*
 375  * If we too:  int *p = &my_struct->member then abandon all hope of tracking
 376  * my_struct->member.
 377  */
 378 static void match_assign_pointer(struct expression *expr)
 379 {
 380         struct expression *right;
 381         char *member;
 382         struct range_list *rl;
 383         struct symbol *type;
 384
 385         right = strip_expr(expr->right);
 386         if (right->type != EXPR_PREOP || right->op != '&')
 387                 return;
 388         right = strip_expr(right->unop);
 389
 390         member = get_member_name(right);
 391         if (!member)
 392                 return;
 393         type = get_type(right);
 394         rl = alloc_whole_rl(type);
 395         add_type_val(member, rl);
 396         free_string(member);
 397 }
 398
 399 static void match_global_assign(struct expression *expr)
 400 {
 401         char *member;
 402         struct range_list *rl;
 403         struct symbol *type;
 404
 405         type = get_type(expr->left);
 406         if (type && (type->type == SYM_ARRAY || type->type == SYM_STRUCT))
 407                 return;
 408         member = get_member_name(expr->left);
 409         if (!member)
 410                 return;
 411         get_absolute_rl(expr->right, &rl);
 412         rl = cast_rl(type, rl);
 413         add_global_type_val(member, rl);
 414         free_string(member);
 415 }
 416
 417 static void unop_expr(struct expression *expr)
 418 {
 419         struct range_list *rl;
 420         char *member;
 421
 422         if (expr->op != SPECIAL_DECREMENT && expr->op != SPECIAL_INCREMENT)
 423                 return;
 424
 425         expr = strip_expr(expr->unop);
 426         member = get_member_name(expr);
 427         if (!member)
 428                 return;
 429         rl = alloc_whole_rl(get_type(expr));
 430         add_type_val(member, rl);
 431         free_string(member);
 432 }
 433
 434 static void asm_expr(struct statement *stmt)
 435 {
 436         struct expression *expr;
 437         struct range_list *rl;
 438         char *member;
 439         int state = 0;
 440
 441         FOR_EACH_PTR(stmt->asm_outputs, expr) {
 442                 switch (state) {
 443                 case 0: /* identifier */
 444                 case 1: /* constraint */
 445                         state++;
 446                         continue;
 447                 case 2: /* expression */
 448                         state = 0;
 449                         member = get_member_name(expr);
 450                         if (!member)
 451                                 continue;
 452                         rl = alloc_whole_rl(get_type(expr));
 453                         add_type_val(member, rl);
 454                         free_string(member);
 455                         continue;
 456                 }
 457         } END_FOR_EACH_PTR(expr);
 458 }
 459
 460 static void db_param_add(struct expression *expr, int param, char *key, char *value)
 461 {
 462         struct expression *arg;
 463         struct symbol *type;
 464         struct range_list *rl;
 465         char *member;
 466
 467         if (strcmp(key, "*$") != 0)
 468                 return;
 469
 470         while (expr->type == EXPR_ASSIGNMENT)
 471                 expr = strip_expr(expr->right);
 472         if (expr->type != EXPR_CALL)
 473                 return;
 474
 475         arg = get_argument_from_call_expr(expr->args, param);
 476         arg = strip_expr(arg);
 477         if (!arg)
 478                 return;
 479         type = get_member_type_from_key(arg, key);
 480         if (arg->type != EXPR_PREOP || arg->op != '&')
 481                 return;
 482         arg = strip_expr(arg->unop);
 483
 484         member = get_member_name(arg);
 485         if (!member)
 486                 return;
 487         call_results_to_rl(expr, type, value, &rl);
 488         add_type_val(member, rl);
 489         free_string(member);
 490 }
 491
 492 static void match_end_func_info(struct symbol *sym)
 493 {
 494         struct sm_state *sm;
 495
 496         FOR_EACH_SM(fn_type_val, sm) {
 497                 sql_insert_function_type_value(sm->name, sm->state->name);
 498         } END_FOR_EACH_SM(sm);
 499 }
 500
 501 static void match_after_func(struct symbol *sym)
 502 {
 503         free_stree(&fn_type_val);
 504 }
 505
 506 static void match_end_file(struct symbol_list *sym_list)
 507 {
 508         struct sm_state *sm;
 509
 510         FOR_EACH_SM(global_type_val, sm) {
 511                 sql_insert_function_type_value(sm->name, sm->state->name);
 512         } END_FOR_EACH_SM(sm);
 513 }
 514
 515 void register_type_val(int id)
 516 {
 517         if (!option_info)
 518                 return;
 519
 520         my_id = id;
 521
 522         add_hook(&match_assign_value, ASSIGNMENT_HOOK_AFTER);
 523         add_hook(&match_assign_pointer, ASSIGNMENT_HOOK);
 524         add_hook(&unop_expr, OP_HOOK);
 525         add_hook(&asm_expr, ASM_HOOK);
 526         select_return_states_hook(PARAM_ADD, &db_param_add);
 527         select_return_states_hook(PARAM_SET, &db_param_add);
 528
 529
 530         add_hook(&match_inline_start, INLINE_FN_START);
 531         add_hook(&match_inline_end, INLINE_FN_END);
 532
 533         add_hook(&match_end_func_info, END_FUNC_HOOK);
 534         add_hook(&match_after_func, AFTER_FUNC_HOOK);
 535
 536         add_hook(&match_global_assign, GLOBAL_ASSIGNMENT_HOOK);
 537         add_hook(&match_end_file, END_FILE_HOOK);
 538 }