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 int get_param_from_container_of(struct expression *expr)
  26 {
  27         struct expression *param_expr;
  28         struct symbol *type;
  29         sval_t sval;
  30         int param;
  31
  32
  33         type = get_type(expr);
  34         if (!type || type->type != SYM_PTR)
  35                 return -1;
  36
  37         expr = strip_expr(expr);
  38         if (expr->type != EXPR_BINOP || expr->op != '-')
  39                 return -1;
  40
  41         if (!get_value(expr->right, &sval))
  42                 return -1;
  43         if (sval.value < 0 || sval.value > 4096)
  44                 return -1;
  45
  46         param_expr = get_assigned_expr(expr->left);
  47         if (!param_expr)
  48                 return -1;
  49         param = get_param_num(param_expr);
  50         if (param < 0)
  51                 return -1;
  52
  53         return param;
  54 }
  55
  56 int get_offset_from_container_of(struct expression *expr)
  57 {
  58         struct expression *param_expr;
  59         struct symbol *type;
  60         sval_t sval;
  61
  62         type = get_type(expr);
  63         if (!type || type->type != SYM_PTR)
  64                 return -1;
  65
  66         expr = strip_expr(expr);
  67         if (expr->type != EXPR_BINOP || expr->op != '-')
  68                 return -1;
  69
  70         if (!get_value(expr->right, &sval))
  71                 return -1;
  72         if (sval.value < 0 || sval.value > 4096)
  73                 return -1;
  74
  75         param_expr = get_assigned_expr(expr->left);
  76         if (!param_expr)
  77                 return -1;
  78
  79         return sval.value;
  80 }
  81
  82 static void print_returns_container_of(int return_id, char *return_ranges, struct expression *expr)
  83 {
  84         int offset;
  85         int param;
  86         char key[64];
  87         char value[64];
  88
  89         param = get_param_from_container_of(expr);
  90         if (param < 0)
  91                 return;
  92         offset = get_offset_from_container_of(expr);
  93         if (offset < 0)
  94                 return;
  95
  96         snprintf(key, sizeof(key), "%d", param);
  97         snprintf(value, sizeof(value), "-%d", offset);
  98
  99         /* no need to add it to return_implies because it's not really param_used */
 100         sql_insert_return_states(return_id, return_ranges, CONTAINER, -1,
 101                         key, value);
 102 }
 103
 104 static int get_deref_count(struct expression *expr)
 105 {
 106         int cnt = 0;
 107
 108         while (expr && expr->type == EXPR_DEREF) {
 109                 expr = expr->deref;
 110                 if (expr->type == EXPR_PREOP && expr->op == '*')
 111                         expr = expr->unop;
 112                 cnt++;
 113                 if (cnt > 100)
 114                         return -1;
 115         }
 116         return cnt;
 117 }
 118
 119 static struct expression *get_partial_deref(struct expression *expr, int cnt)
 120 {
 121         while (--cnt >= 0) {
 122                 if (!expr || expr->type != EXPR_DEREF)
 123                         return expr;
 124                 expr = expr->deref;
 125                 if (expr->type == EXPR_PREOP && expr->op == '*')
 126                         expr = expr->unop;
 127         }
 128         return expr;
 129 }
 130
 131 static int partial_deref_to_offset_str(struct expression *expr, int cnt, char op, char *buf, int size)
 132 {
 133         int n, offset;
 134
 135         if (cnt == 0)
 136                 return snprintf(buf, size, "%c0", op);
 137
 138         n = 0;
 139         while (--cnt >= 0) {
 140                 offset = get_member_offset_from_deref(expr);
 141                 if (offset < 0)
 142                         return -1;
 143                 n += snprintf(buf + n, size - n, "%c%d", op, offset);
 144                 if (expr->type != EXPR_DEREF)
 145                         return -1;
 146                 expr = expr->deref;
 147                 if (expr->type == EXPR_PREOP && expr->op == '*')
 148                         expr = expr->unop;
 149         }
 150
 151         return n;
 152 }
 153
 154 static char *get_shared_str(struct expression *expr, struct expression *container)
 155 {
 156         struct expression *one, *two;
 157         int exp, cont, min, ret, n;
 158         static char buf[48];
 159
 160         exp = get_deref_count(expr);
 161         cont = get_deref_count(container);
 162         if (exp < 0 || cont < 0)
 163                 return NULL;
 164
 165         min = (exp < cont) ? exp : cont;
 166         while (min >= 0) {
 167                 one = get_partial_deref(expr, exp - min);
 168                 two = get_partial_deref(container, cont - min);
 169                 if (expr_equiv(one, two))
 170                         goto found;
 171                 min--;
 172         }
 173
 174         return NULL;
 175
 176 found:
 177         ret = partial_deref_to_offset_str(expr, exp - min, '-', buf, sizeof(buf));
 178         if (ret < 0)
 179                 return NULL;
 180         n = ret;
 181         ret = partial_deref_to_offset_str(container, cont - min, '+', buf + ret, sizeof(buf) - ret);
 182         if (ret < 0)
 183                 return NULL;
 184         n += ret;
 185         if (n >= sizeof(buf))
 186                 return NULL;
 187
 188         return buf;
 189 }
 190
 191 static char *get_stored_container_name(struct expression *container,
 192                                        struct expression *expr)
 193 {
 194         struct smatch_state *state;
 195         static char buf[64];
 196         char *p;
 197         int param;
 198
 199         if (!container || container->type != EXPR_SYMBOL)
 200                 return NULL;
 201         if (!expr || expr->type != EXPR_SYMBOL)
 202                 return NULL;
 203         state = get_state_expr(param_id, expr);
 204         if (!state)
 205                 return NULL;
 206
 207         snprintf(buf, sizeof(buf), "%s", state->name);
 208         p = strchr(buf, '|');
 209         if (!p)
 210                 return NULL;
 211         *p = '\0';
 212         param = atoi(p + 2);
 213         if (get_param_sym_from_num(param) == container->symbol)
 214                 return buf;
 215         return NULL;
 216 }
 217
 218 static char *get_container_name_helper(struct expression *container, struct expression *expr)
 219 {
 220         struct symbol *container_sym, *sym;
 221         static char buf[64];
 222         char *ret, *shared;
 223         bool star;
 224
 225         expr = strip_expr(expr);
 226         container = strip_expr(container);
 227         if (!expr || !container)
 228                 return NULL;
 229
 230         ret = get_stored_container_name(container, expr);
 231         if (ret)
 232                 return ret;
 233
 234         sym = expr_to_sym(expr);
 235         container_sym = expr_to_sym(container);
 236         if (!sym || !container_sym)
 237                 return NULL;
 238         if (sym != container_sym)
 239                 return NULL;
 240
 241         if (container->type == EXPR_DEREF)
 242                 star = true;
 243         else
 244                 star = false;
 245
 246         if (container->type == EXPR_PREOP && container->op == '&')
 247                 container = strip_expr(container->unop);
 248         if (expr->type == EXPR_PREOP && expr->op == '&')
 249                 expr = strip_expr(expr->unop);
 250
 251         shared = get_shared_str(expr, container);
 252         if (!shared)
 253                 return NULL;
 254         if (star)
 255                 snprintf(buf, sizeof(buf), "*(%s)", shared);
 256         else
 257                 snprintf(buf, sizeof(buf), "%s", shared);
 258
 259         return buf;
 260 }
 261
 262 char *get_container_name(struct expression *container, struct expression *expr)
 263 {
 264         char *ret;
 265
 266         ret = get_container_name_helper(container, expr);
 267         if (ret)
 268                 return ret;
 269
 270         ret = get_container_name_helper(get_assigned_expr(container), expr);
 271         if (ret)
 272                 return ret;
 273
 274         ret = get_container_name_helper(container, get_assigned_expr(expr));
 275         if (ret)
 276                 return ret;
 277
 278         ret = get_container_name_helper(get_assigned_expr(container),
 279                                         get_assigned_expr(expr));
 280         if (ret)
 281                 return ret;
 282
 283         return NULL;
 284 }
 285
 286 static bool is_fn_ptr(struct expression *expr)
 287 {
 288         struct symbol *type;
 289
 290         if (!expr)
 291                 return false;
 292         if (expr->type != EXPR_SYMBOL && expr->type != EXPR_DEREF)
 293                 return false;
 294
 295         type = get_type(expr);
 296         if (!type || type->type != SYM_PTR)
 297                 return false;
 298         type = get_real_base_type(type);
 299         if (!type || type->type != SYM_FN)
 300                 return false;
 301         return true;
 302 }
 303
 304 static void match_call(struct expression *call)
 305 {
 306         struct expression *fn, *arg, *tmp;
 307         bool found = false;
 308         int fn_param, param;
 309         char buf[32];
 310         char *name;
 311
 312         /*
 313          * We're trying to link the function with the parameter.  There are a
 314          * couple ways this can be passed:
 315          * foo->func(foo, ...);
 316          * foo->func(foo->x, ...);
 317          * foo->bar.func(&foo->bar, ...);
 318          * foo->bar->baz->func(foo, ...);
 319          *
 320          * So the method is basically to subtract the offsets until we get to
 321          * the common bit, then add the member offsets to get the parameter.
 322          *
 323          * If we're taking an address then the offset math is not stared,
 324          * otherwise it is.  Starred means dereferenced.
 325          */
 326         fn = strip_expr(call->fn);
 327
 328         param = -1;
 329         FOR_EACH_PTR(call->args, arg) {
 330                 param++;
 331
 332                 name = get_container_name(arg, fn);
 333                 if (!name)
 334                         continue;
 335
 336                 found = true;
 337                 sql_insert_caller_info(call, CONTAINER, param, name, "$(-1)");
 338         } END_FOR_EACH_PTR(arg);
 339
 340         if (found)
 341                 return;
 342
 343         fn_param = -1;
 344         FOR_EACH_PTR(call->args, arg) {
 345                 fn_param++;
 346                 if (!is_fn_ptr(arg))
 347                         continue;
 348                 param = -1;
 349                 FOR_EACH_PTR(call->args, tmp) {
 350                         param++;
 351
 352                         /* the function isn't it's own container */
 353                         if (arg == tmp)
 354                                 continue;
 355
 356                         name = get_container_name(tmp, arg);
 357                         if (!name)
 358                                 continue;
 359
 360                         snprintf(buf, sizeof(buf), "$%d", param);
 361                         sql_insert_caller_info(call, CONTAINER, fn_param, name, buf);
 362                         return;
 363                 } END_FOR_EACH_PTR(tmp);
 364         } END_FOR_EACH_PTR(arg);
 365 }
 366
 367 static void db_passed_container(const char *name, struct symbol *sym, char *key, char *value)
 368 {
 369         char buf[64];
 370
 371         snprintf(buf, sizeof(buf), "%s|%s", key, value);
 372         set_state(param_id, name, sym, alloc_state_str(buf));
 373 }
 374
 375 struct db_info {
 376         struct symbol *arg;
 377         int prev_offset;
 378         struct range_list *rl;
 379         int star;
 380         struct stree *stree;
 381 };
 382
 383 static struct symbol *get_member_from_offset(struct symbol *sym, int offset)
 384 {
 385         struct symbol *type, *tmp;
 386         int cur;
 387
 388         type = get_real_base_type(sym);
 389         if (!type || type->type != SYM_PTR)
 390                 return NULL;
 391         type = get_real_base_type(type);
 392         if (!type || type->type != SYM_STRUCT)
 393                 return NULL;
 394
 395         cur = 0;
 396         FOR_EACH_PTR(type->symbol_list, tmp) {
 397                 cur = ALIGN(cur, tmp->ctype.alignment);
 398                 if (offset == cur)
 399                         return tmp;
 400                 cur += type_bytes(tmp);
 401         } END_FOR_EACH_PTR(tmp);
 402         return NULL;
 403 }
 404
 405 static struct symbol *get_member_type_from_offset(struct symbol *sym, int offset)
 406 {
 407         struct symbol *base_type;
 408         struct symbol *member;
 409
 410         base_type = get_real_base_type(sym);
 411         if (base_type && base_type->type == SYM_PTR)
 412                 base_type = get_real_base_type(base_type);
 413         if (offset == 0 && base_type && base_type->type == SYM_BASETYPE)
 414                 return base_type;
 415
 416         member = get_member_from_offset(sym, offset);
 417         if (!member)
 418                 return NULL;
 419         return get_real_base_type(member);
 420 }
 421
 422 static const char *get_name_from_offset(struct symbol *arg, int offset)
 423 {
 424         struct symbol *member, *type;
 425         const char *name;
 426         static char fullname[256];
 427
 428         name = arg->ident->name;
 429
 430         type = get_real_base_type(arg);
 431         if (!type || type->type != SYM_PTR)
 432                 return name;
 433
 434         type = get_real_base_type(type);
 435         if (!type)
 436                 return NULL;
 437         if (type->type != SYM_STRUCT) {
 438                 snprintf(fullname, sizeof(fullname), "*%s", name);
 439                 return fullname;
 440         }
 441
 442         member = get_member_from_offset(arg, offset);
 443         if (!member || !member->ident)
 444                 return NULL;
 445
 446         snprintf(fullname, sizeof(fullname), "%s->%s", name, member->ident->name);
 447         return fullname;
 448 }
 449
 450 static void set_param_value(struct stree **stree, struct symbol *arg, int offset, struct range_list *rl)
 451 {
 452         const char *name;
 453
 454         name = get_name_from_offset(arg, offset);
 455         if (!name)
 456                 return;
 457         set_state_stree(stree, SMATCH_EXTRA, name, arg, alloc_estate_rl(rl));
 458 }
 459
 460 static int save_vals(void *_db_info, int argc, char **argv, char **azColName)
 461 {
 462         struct db_info *db_info = _db_info;
 463         struct symbol *type;
 464         struct range_list *rl;
 465         int offset = 0;
 466         const char *value;
 467
 468         if (argc == 2) {
 469                 offset = atoi(argv[0]);
 470                 value = argv[1];
 471         } else {
 472                 value = argv[0];
 473         }
 474
 475         if (db_info->prev_offset != -1 &&
 476             db_info->prev_offset != offset) {
 477                 set_param_value(&db_info->stree, db_info->arg, db_info->prev_offset, db_info->rl);
 478                 db_info->rl = NULL;
 479         }
 480
 481         db_info->prev_offset = offset;
 482
 483         type = get_real_base_type(db_info->arg);
 484         if (db_info->star)
 485                 goto found_type;
 486         if (type->type != SYM_PTR)
 487                 return 0;
 488         type = get_real_base_type(type);
 489         if (type->type == SYM_BASETYPE)
 490                 goto found_type;
 491         type = get_member_type_from_offset(db_info->arg, offset);
 492 found_type:
 493         str_to_rl(type, (char *)value, &rl);
 494         if (db_info->rl)
 495                 db_info->rl = rl_union(db_info->rl, rl);
 496         else
 497                 db_info->rl = rl;
 498
 499         return 0;
 500 }
 501
 502 static struct stree *load_tag_info_sym(mtag_t tag, struct symbol *arg, int arg_offset, int star)
 503 {
 504         struct db_info db_info = {
 505                 .arg = arg,
 506                 .prev_offset = -1,
 507                 .star = star,
 508         };
 509         struct symbol *type;
 510
 511         if (!tag || !arg->ident)
 512                 return NULL;
 513
 514         type = get_real_base_type(arg);
 515         if (!type)
 516                 return NULL;
 517         if (!star) {
 518                 if (type->type != SYM_PTR)
 519                         return NULL;
 520                 type = get_real_base_type(type);
 521                 if (!type)
 522                         return NULL;
 523         }
 524
 525         if (star || type->type == SYM_BASETYPE) {
 526                 run_sql(save_vals, &db_info,
 527                         "select value from mtag_data where tag = %lld and offset = %d and type = %d;",
 528                         tag, arg_offset, DATA_VALUE);
 529         } else {  /* presumably the parameter is a struct pointer */
 530                 run_sql(save_vals, &db_info,
 531                         "select offset, value from mtag_data where tag = %lld and type = %d order by offset;",
 532                         tag, DATA_VALUE);
 533         }
 534
 535         if (db_info.prev_offset != -1)
 536                 set_param_value(&db_info.stree, arg, db_info.prev_offset, db_info.rl);
 537
 538         // FIXME: handle an offset correctly
 539         if (!star && !arg_offset) {
 540                 sval_t sval;
 541
 542                 sval.type = get_real_base_type(arg);
 543                 sval.uvalue = tag;
 544                 set_state_stree(&db_info.stree, SMATCH_EXTRA, arg->ident->name, arg, alloc_estate_sval(sval));
 545         }
 546         return db_info.stree;
 547 }
 548
 549 static void load_container_data(struct symbol *arg, const char *info)
 550 {
 551         mtag_t cur_tag, container_tag, arg_tag;
 552         int container_offset, arg_offset;
 553         struct sm_state *sm;
 554         struct stree *stree;
 555         char *p, *cont;
 556         char copy[64];
 557         bool star = 0;
 558
 559         snprintf(copy, sizeof(copy), "%s", info);
 560         p = strchr(copy, '|');
 561         if (!p)
 562                 return;
 563         *p = '\0';
 564         cont = p + 1;
 565         p = copy;
 566         if (p[0] == '*') {
 567                 star = 1;
 568                 p += 2;
 569         }
 570
 571         if (strcmp(cont, "$(-1)") != 0)
 572                 return;
 573
 574         if (!get_toplevel_mtag(cur_func_sym, &cur_tag))
 575                 return;
 576
 577         while (true) {
 578                 container_offset = strtoul(p, &p, 0);
 579                 if (local_debug)
 580                         sm_msg("%s: cur_tag = %llu container_offset = %d",
 581                                __func__, cur_tag, container_offset);
 582                 if (!mtag_map_select_container(cur_tag, -container_offset, &container_tag))
 583                         return;
 584                 cur_tag = container_tag;
 585                 if (local_debug)
 586                         sm_msg("%s: container_tag = %llu p = '%s'",
 587                                __func__, container_tag, p);
 588                 if (!p)
 589                         return;
 590                 if (p[0] != '-')
 591                         break;
 592                 p++;
 593         }
 594
 595         if (p[0] != '+')
 596                 return;
 597
 598         p++;
 599         arg_offset = strtoul(p, &p, 0);
 600         if (p && *p && *p != ')')
 601                 return;
 602
 603         if (!arg_offset || star) {
 604                 arg_tag = container_tag;
 605         } else {
 606                 if (!mtag_map_select_tag(container_tag, arg_offset, &arg_tag))
 607                         return;
 608         }
 609
 610         stree = load_tag_info_sym(arg_tag, arg, arg_offset, star);
 611         FOR_EACH_SM(stree, sm) {
 612                 set_state(sm->owner, sm->name, sm->sym, sm->state);
 613         } END_FOR_EACH_SM(sm);
 614         free_stree(&stree);
 615 }
 616
 617 static void handle_passed_container(struct symbol *sym)
 618 {
 619         struct symbol *arg;
 620         struct smatch_state *state;
 621
 622         FOR_EACH_PTR(cur_func_sym->ctype.base_type->arguments, arg) {
 623                 state = get_state(param_id, arg->ident->name, arg);
 624                 if (!state || state == &merged)
 625                         continue;
 626                 load_container_data(arg, state->name);
 627         } END_FOR_EACH_PTR(arg);
 628 }
 629
 630 void register_container_of(int id)
 631 {
 632         my_id = id;
 633
 634         add_split_return_callback(&print_returns_container_of);
 635         add_hook(&match_call, FUNCTION_CALL_HOOK);
 636 }
 637
 638 void register_container_of2(int id)
 639 {
 640         param_id = id;
 641
 642         set_dynamic_states(param_id);
 643         select_caller_info_hook(db_passed_container, CONTAINER);
 644         add_merge_hook(param_id, &merge_str_state);
 645         add_hook(&handle_passed_container, AFTER_DEF_HOOK);
 646 }
 647