smatch_container_of.c

   1 /*
   2  * Copyright (C) 2017 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 #include "smatch.h"
  19 #include "smatch_slist.h"
  20 #include "smatch_extra.h"
  21
  22 static int my_id;
  23 static int param_id;
  24
  25 static struct stree *used_stree;
  26 static struct stree_stack *saved_stack;
  27
  28 STATE(used);
  29
  30 int get_param_from_container_of(struct expression *expr)
  31 {
  32         struct expression *param_expr;
  33         struct symbol *type;
  34         sval_t sval;
  35         int param;
  36
  37
  38         type = get_type(expr);
  39         if (!type || type->type != SYM_PTR)
  40                 return -1;
  41
  42         expr = strip_expr(expr);
  43         if (expr->type != EXPR_BINOP || expr->op != '-')
  44                 return -1;
  45
  46         if (!get_value(expr->right, &sval))
  47                 return -1;
  48         if (sval.value < 0 || sval.value > 4096)
  49                 return -1;
  50
  51         param_expr = get_assigned_expr(expr->left);
  52         if (!param_expr)
  53                 return -1;
  54         param = get_param_num(param_expr);
  55         if (param < 0)
  56                 return -1;
  57
  58         return param;
  59 }
  60
  61 int get_offset_from_container_of(struct expression *expr)
  62 {
  63         struct expression *param_expr;
  64         struct symbol *type;
  65         sval_t sval;
  66
  67         type = get_type(expr);
  68         if (!type || type->type != SYM_PTR)
  69                 return -1;
  70
  71         expr = strip_expr(expr);
  72         if (expr->type != EXPR_BINOP || expr->op != '-')
  73                 return -1;
  74
  75         if (!get_value(expr->right, &sval))
  76                 return -1;
  77         if (sval.value < 0 || sval.value > 4096)
  78                 return -1;
  79
  80         param_expr = get_assigned_expr(expr->left);
  81         if (!param_expr)
  82                 return -1;
  83
  84         return sval.value;
  85 }
  86
  87 static int get_container_arg(struct symbol *sym)
  88 {
  89         struct expression *__mptr;
  90         int param;
  91
  92         if (!sym || !sym->ident)
  93                 return -1;
  94
  95         __mptr = get_assigned_expr_name_sym(sym->ident->name, sym);
  96         param = get_param_from_container_of(__mptr);
  97
  98         return param;
  99 }
 100
 101 static int get_container_offset(struct symbol *sym)
 102 {
 103         struct expression *__mptr;
 104         int offset;
 105
 106         if (!sym || !sym->ident)
 107                 return -1;
 108
 109         __mptr = get_assigned_expr_name_sym(sym->ident->name, sym);
 110         offset = get_offset_from_container_of(__mptr);
 111
 112         return offset;
 113 }
 114
 115 static char *get_container_name(struct sm_state *sm, int offset)
 116 {
 117         static char buf[256];
 118         const char *name;
 119
 120         name = get_param_name(sm);
 121         if (!name)
 122                 return NULL;
 123
 124         if (name[0] == '$')
 125                 snprintf(buf, sizeof(buf), "$(-%d)%s", offset, name + 1);
 126         else if (name[0] == '*' || name[1] == '$')
 127                 snprintf(buf, sizeof(buf), "*$(-%d)%s", offset, name + 2);
 128         else
 129                 return NULL;
 130
 131         return buf;
 132 }
 133
 134 static void get_state_hook(int owner, const char *name, struct symbol *sym)
 135 {
 136         int arg;
 137
 138         if (!option_info)
 139                 return;
 140         if (__in_fake_assign)
 141                 return;
 142
 143         arg = get_container_arg(sym);
 144         if (arg >= 0)
 145                 set_state_stree(&used_stree, my_id, name, sym, &used);
 146 }
 147
 148 static void set_param_used(struct expression *call, struct expression *arg, char *key, char *unused)
 149 {
 150         struct symbol *sym;
 151         char *name;
 152         int arg_nr;
 153
 154         name = get_variable_from_key(arg, key, &sym);
 155         if (!name || !sym)
 156                 goto free;
 157
 158         arg_nr = get_container_arg(sym);
 159         if (arg_nr >= 0)
 160                 set_state(my_id, name, sym, &used);
 161 free:
 162         free_string(name);
 163 }
 164
 165 static void process_states(void)
 166 {
 167         struct sm_state *tmp;
 168         int arg, offset;
 169         const char *name;
 170
 171         FOR_EACH_SM(used_stree, tmp) {
 172                 arg = get_container_arg(tmp->sym);
 173                 offset = get_container_offset(tmp->sym);
 174                 if (arg < 0 || offset < 0)
 175                         continue;
 176                 name = get_container_name(tmp, offset);
 177                 if (!name)
 178                         continue;
 179                 sql_insert_call_implies(CONTAINER, arg, name, "");
 180         } END_FOR_EACH_SM(tmp);
 181
 182         free_stree(&used_stree);
 183 }
 184
 185 static void match_function_def(struct symbol *sym)
 186 {
 187         free_stree(&used_stree);
 188 }
 189
 190 static void match_save_states(struct expression *expr)
 191 {
 192         push_stree(&saved_stack, used_stree);
 193         used_stree = NULL;
 194 }
 195
 196 static void match_restore_states(struct expression *expr)
 197 {
 198         free_stree(&used_stree);
 199         used_stree = pop_stree(&saved_stack);
 200 }
 201
 202 static void print_returns_container_of(int return_id, char *return_ranges, struct expression *expr)
 203 {
 204         int offset;
 205         int param;
 206         char key[64];
 207         char value[64];
 208
 209         param = get_param_from_container_of(expr);
 210         if (param < 0)
 211                 return;
 212         offset = get_offset_from_container_of(expr);
 213         if (offset < 0)
 214                 return;
 215
 216         snprintf(key, sizeof(key), "%d", param);
 217         snprintf(value, sizeof(value), "-%d", offset);
 218
 219         /* no need to add it to call_implies because it's not really param_used */
 220         sql_insert_return_states(return_id, return_ranges, CONTAINER, -1,
 221                         key, value);
 222 }
 223
 224 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
 225 {
 226         struct expression *call, *arg;
 227         int offset;
 228         char buf[64];
 229
 230         if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 231                 return;
 232         call = strip_expr(expr->right);
 233         if (call->type != EXPR_CALL)
 234                 return;
 235         if (param != -1)
 236                 return;
 237         param = atoi(key);
 238         offset = atoi(value);
 239
 240         arg = get_argument_from_call_expr(call->args, param);
 241         if (!arg)
 242                 return;
 243         if (arg->type != EXPR_SYMBOL)
 244                 return;
 245         param = get_param_num(arg);
 246         if (param < 0)
 247                 return;
 248         snprintf(buf, sizeof(buf), "$(%d)", offset);
 249         sql_insert_call_implies(CONTAINER, param, buf, "");
 250 }
 251
 252 static struct expression *get_outer_struct(struct expression *expr)
 253 {
 254         expr = strip_expr(expr);
 255
 256         if (expr->type != EXPR_DEREF)
 257                 return NULL;
 258         expr = strip_expr(expr->deref);
 259         if (expr->type == EXPR_SYMBOL)
 260                 return expr;
 261         if (expr->type == EXPR_PREOP && expr->op == '*')
 262                 return strip_expr(expr->unop);
 263         return expr;
 264 }
 265
 266 static void match_call(struct expression *call)
 267 {
 268         struct expression *fn_ptr, *fn_parent, *arg, *arg_parent;
 269         struct symbol *fn_sym, *arg_sym;
 270         struct symbol *type;
 271         int i, offset;
 272         int arg_offset = 0;
 273         char parent_str[64];
 274         char offset_str[64];
 275         char param_str[64];
 276         char *p;
 277         bool star = 0;
 278
 279         /*
 280          * We're trying to link the function with the parameter.  There are a
 281          * couple ways this can be passed:
 282          * foo->func(foo, ...);
 283          * foo->func(foo->x, ...);
 284          * foo->bar.func(&foo->bar, ...);
 285          * foo->bar->baz->func(foo, ...);
 286          *
 287          * So the method is basically to subtract the offsets until we get to
 288          * the common bit, then the member offsets for the parameter.
 289          *
 290          * If the argument is not a pointer then we star it.  This is perhaps
 291          * not right.  We should probably be treating addresses of a pointer
 292          * different from the pointer value.
 293          *
 294          */
 295         fn_ptr = strip_expr(call->fn);
 296         fn_parent = get_outer_struct(fn_ptr);
 297         if (!fn_parent)
 298                 return;
 299         fn_sym = expr_to_sym(fn_parent);
 300         if (!fn_sym)
 301                 return;
 302
 303         type = get_type(fn_parent);
 304         if (type && type->type == SYM_PTR)
 305                 type = get_real_base_type(type);
 306         offset = get_member_offset(type, fn_ptr->member->name);
 307         if (offset < 0)
 308                 return;
 309
 310         i = -1;
 311         FOR_EACH_PTR(call->args, arg) {
 312                 i++;
 313
 314 #if 0
 315                 /*
 316                  * This doesn't work because of things like:
 317                  * foo = bar;
 318                  * foo->func(foo, ...);
 319                  * We don't want to use "bar" here.  But also perhaps I should
 320                  * be changing the short names to long names or something?
 321                  *
 322                  */
 323                 count = 0;
 324                 while ((tmp = get_assigned_expr(arg))) {
 325                         arg = strip_expr(tmp);
 326                         if (count++ > 4)
 327                                 break;
 328                 }
 329 #endif
 330                 arg_sym = expr_to_sym(arg);
 331                 if (!arg_sym)
 332                         continue;
 333                 if (arg_sym != fn_sym)
 334                         continue;
 335
 336                 /*
 337                  * We know these are related because arg_sym == fn_sym.
 338                  * If we don't record something in the DB, that is a failure.
 339                  *
 340                  */
 341
 342                 if (arg->type == EXPR_PREOP && arg->op == '&')
 343                         arg = strip_expr(arg->unop);
 344
 345                 if (expr_equiv(arg, fn_parent)) {
 346                         snprintf(parent_str, sizeof(parent_str), "-%d", offset);
 347                         goto found;
 348                 }
 349
 350                 p = parent_str;
 351                 while ((arg_parent = get_outer_struct(arg))) {
 352                         arg = arg_parent;
 353
 354                         p += snprintf(p, parent_str + sizeof(parent_str) - p, "-%d", offset);
 355
 356                         if (!expr_equiv(arg, fn_parent))
 357                                 continue;
 358                         arg_offset = get_member_offset_from_deref(arg);
 359                         if (arg_offset < 0)
 360                                 continue;
 361                         if (!is_pointer(arg))
 362                                 star = 1;
 363                         goto found;
 364                 }
 365         } END_FOR_EACH_PTR(arg);
 366
 367         return;
 368
 369 found:
 370         if (star)
 371                 snprintf(offset_str, sizeof(offset_str), "*(%s+%d)", parent_str, arg_offset);
 372         else
 373                 snprintf(offset_str, sizeof(offset_str), "%s+%d", parent_str, arg_offset);
 374         snprintf(param_str, sizeof(param_str), "$%d", i);
 375         sql_insert_caller_info(call, CONTAINER, -1, offset_str, param_str);
 376 }
 377
 378 static void db_passed_container(const char *name, struct symbol *sym, char *key, char *value)
 379 {
 380         sval_t offset = {
 381                 .type = &int_ctype,
 382         };
 383         const char *arg_offset;
 384         struct symbol *arg;
 385         int star = 0;
 386         int param;
 387         int val;
 388         int i;
 389
 390         if (name || sym)
 391                 return;
 392         if (key[0] == '*') {
 393                 star = 1;
 394                 key += 2;
 395         }
 396
 397         val = atoi(key);
 398         if (val < -4095 || val >= 0)
 399                 return;
 400         offset.value = -val;
 401         arg_offset = strchr(key, '+');
 402         if (!arg_offset)
 403                 return;
 404         val = atoi(arg_offset + 1);
 405         if (val > 4095 || val < 0)
 406                 return;
 407         offset.value |= val << 16;
 408         if (star)
 409                 offset.value |= 1ULL << 31;
 410
 411         if (value[0] != '$')
 412                 return;
 413
 414         param = atoi(value + 1);
 415
 416         i = -1;
 417         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 418                 i++;
 419                 if (param == i)
 420                         set_state(param_id, arg->ident->name, arg, alloc_estate_sval(offset));
 421         } END_FOR_EACH_PTR(arg);
 422 }
 423
 424 struct db_info {
 425         struct symbol *param_sym;
 426         int prev_offset;
 427         struct range_list *rl;
 428 };
 429
 430 static struct symbol *get_member_from_offset(struct symbol *sym, int offset)
 431 {
 432         struct symbol *type, *tmp;
 433         int cur;
 434
 435         type = get_real_base_type(sym);
 436         if (!type || type->type != SYM_PTR)
 437                 return NULL;
 438         type = get_real_base_type(type);
 439         if (!type || type->type != SYM_STRUCT)
 440                 return NULL;
 441
 442         cur = 0;
 443         FOR_EACH_PTR(type->symbol_list, tmp) {
 444                 cur = ALIGN(cur, tmp->ctype.alignment);
 445                 if (offset == cur)
 446                         return tmp;
 447                 cur += type_bytes(tmp);
 448         } END_FOR_EACH_PTR(tmp);
 449         return NULL;
 450 }
 451
 452 static struct symbol *get_member_type_from_offset(struct symbol *sym, int offset)
 453 {
 454         struct symbol *member;
 455
 456         member = get_member_from_offset(sym, offset);
 457         if (!member)
 458                 return NULL;
 459         return get_real_base_type(member);
 460 }
 461
 462 static void set_param_value(struct symbol *sym, int offset, struct range_list *rl)
 463 {
 464         struct symbol *member;
 465         const char *name;
 466         char fullname[256];
 467
 468         if (!sym || !sym->ident)
 469                 return;
 470         name = sym->ident->name;
 471
 472         member = get_member_from_offset(sym, offset);
 473         if (!member) {
 474                 if (offset == 0)
 475                         snprintf(fullname, sizeof(fullname), "%s", name);
 476                 else
 477                         return;
 478         } else {
 479                 snprintf(fullname, sizeof(fullname), "%s->%s", name, member->ident->name);
 480         }
 481
 482         set_state(SMATCH_EXTRA, fullname, sym, alloc_estate_rl(rl));
 483 }
 484
 485 static int save_vals(void *_db_info, int argc, char **argv, char **azColName)
 486 {
 487         struct db_info *db_info = _db_info;
 488         struct symbol *type;
 489         struct range_list *rl;
 490         int offset = 0;
 491         const char *value;
 492
 493         if (argc == 2) {
 494                 offset = atoi(argv[0]);
 495                 value = argv[1];
 496         } else {
 497                 value = argv[0];
 498         }
 499
 500         if (db_info->prev_offset != -1 &&
 501             db_info->prev_offset != offset) {
 502                 set_param_value(db_info->param_sym, db_info->prev_offset, db_info->rl);
 503                 db_info->rl = NULL;
 504         }
 505
 506         db_info->prev_offset = offset;
 507
 508         type = get_member_type_from_offset(db_info->param_sym, offset);
 509         str_to_rl(type, (char *)value, &rl);
 510         if (db_info->rl)
 511                 db_info->rl = rl_union(db_info->rl, rl);
 512         else
 513                 db_info->rl = rl;
 514
 515         return 0;
 516 }
 517
 518 static void load_tag_info_sym(mtag_t tag, struct symbol *sym, int arg_offset, int star)
 519 {
 520         struct db_info db_info = {
 521                 .param_sym = sym,
 522                 .prev_offset = -1,
 523         };
 524
 525         if (!tag)
 526                 return;
 527
 528         if (star) {
 529                 run_sql(save_vals, &db_info,
 530                         "select value from mtag_data where tag = %lld and offset = %d and type = %d;",
 531                         tag, arg_offset, DATA_VALUE);
 532         } else {
 533                 run_sql(save_vals, &db_info,
 534                         "select offset, value from mtag_data where tag = %lld and type = %d;",
 535                         tag, DATA_VALUE);
 536         }
 537
 538         if (db_info.prev_offset != -1)
 539                 set_param_value(db_info.param_sym, db_info.prev_offset, db_info.rl);
 540 }
 541
 542 static void handle_passed_container(struct symbol *sym)
 543 {
 544         struct symbol *arg;
 545         struct smatch_state *state;
 546         mtag_t fn_tag, container_tag, arg_tag;
 547         sval_t offset;
 548         int container_offset, arg_offset;
 549         int star;
 550
 551         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 552                 state = get_state(param_id, arg->ident->name, arg);
 553                 if (state)
 554                         goto found;
 555         } END_FOR_EACH_PTR(arg);
 556
 557         return;
 558 found:
 559         if (!estate_get_single_value(state, &offset))
 560                 return;
 561         container_offset = -(offset.value & 0xffff);
 562         arg_offset = -((offset.value & 0xfff0000) >> 16);
 563         star = !!(offset.value & (1ULL << 31));
 564
 565         if (!get_toplevel_mtag(cur_func_sym, &fn_tag))
 566                 return;
 567         if (!mtag_map_select_container(fn_tag, container_offset, &container_tag))
 568                 return;
 569         if (!arg_offset || star) {
 570                 arg_tag = container_tag;
 571         } else {
 572                 if (!mtag_map_select_tag(container_tag, arg_offset, &arg_tag))
 573                         return;
 574
 575         }
 576         load_tag_info_sym(arg_tag, arg, -arg_offset, star);
 577 }
 578
 579 void register_container_of(int id)
 580 {
 581         my_id = id;
 582
 583         add_hook(&match_function_def, FUNC_DEF_HOOK);
 584
 585         add_get_state_hook(&get_state_hook);
 586
 587         add_hook(&match_save_states, INLINE_FN_START);
 588         add_hook(&match_restore_states, INLINE_FN_END);
 589
 590         select_call_implies_hook(CONTAINER, &set_param_used);
 591         all_return_states_hook(&process_states);
 592
 593         add_split_return_callback(&print_returns_container_of);
 594         select_return_states_hook(CONTAINER, &returns_container_of);
 595
 596         add_hook(&match_call, FUNCTION_CALL_HOOK);
 597 }
 598
 599 static struct smatch_state *unmatched_state(struct sm_state *sm)
 600 {
 601         return alloc_estate_whole(estate_type(sm->state));
 602 }
 603
 604 void register_container_of2(int id)
 605 {
 606         param_id = id;
 607
 608         select_caller_info_hook(db_passed_container, CONTAINER);
 609         add_hook(&handle_passed_container, AFTER_DEF_HOOK);
 610         add_unmatched_state_hook(param_id, &unmatched_state);
 611         add_merge_hook(param_id, &merge_estates);
 612 }
 613