smatch_struct_assignment.c

   1 /*
   2  * Copyright (C) 2014 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  * This file started out by saying that if you have:
  20  *
  21  *      struct foo one, two;
  22  *      ...
  23  *      one = two;
  24  *
  25  * That's equivalent to saying:
  26  *
  27  *      one.x = two.x;
  28  *      one.y = two.y;
  29  *
  30  * Turning an assignment like that into a bunch of small fake assignments is
  31  * really useful.
  32  *
  33  * The call to memcpy(&one, &two, sizeof(foo)); is the same as "one = two;" so
  34  * we can re-use the code.  And we may as well use it for memset() too.
  35  * Assigning pointers is almost the same:
  36  *
  37  *      p1 = p2;
  38  *
  39  * Is the same as:
  40  *
  41  *      p1->x = p2->x;
  42  *      p1->y = p2->y;
  43  *
  44  * The problem is that you can go a bit crazy with pointers to pointers.
  45  *
  46  *      p1->x->y->z->one->two->three = p2->x->y->z->one->two->three;
  47  *
  48  * We probably want to distinguish between between shallow and deep copies so
  49  * that if we memset(p1, 0, sizeof(*p1)) then it just sets p1->x to zero and not
  50  * p1->x->y.
  51  *
  52  * I don't have a proper solution for this problem right now.  I just copy one
  53  * level and don't nest.  It should handle limitted nesting but intelligently.
  54  *
  55  * The other thing is that you end up with a lot of garbage assignments where
  56  * we record "x could be anything. x->y could be anything. x->y->z->a->b->c
  57  * could *also* be anything!".  There should be a better way to filter this
  58  * useless information.
  59  *
  60  */
  61
  62 #include "scope.h"
  63 #include "smatch.h"
  64 #include "smatch_slist.h"
  65 #include "smatch_extra.h"
  66
  67 enum {
  68         COPY_NORMAL,
  69         COPY_UNKNOWN,
  70         COPY_ZERO,
  71 };
  72
  73 static struct symbol *get_struct_type(struct expression *expr)
  74 {
  75         struct symbol *type;
  76
  77         type = get_type(expr);
  78         if (!type)
  79                 return NULL;
  80         if (type->type == SYM_PTR) {
  81                 type = get_real_base_type(type);
  82                 if (!type)
  83                         return NULL;
  84         }
  85         if (type->type == SYM_STRUCT)
  86                 return type;
  87         if (type->type == SYM_UNION)
  88                 return type;
  89         return NULL;
  90 }
  91
  92 static struct expression *get_right_base_expr(struct symbol *left_type, struct expression *right)
  93 {
  94         struct symbol *struct_type;
  95
  96         if (!right)
  97                 return NULL;
  98
  99         struct_type = get_struct_type(right);
 100         if (!struct_type)
 101                 return NULL;
 102         if (struct_type != left_type)
 103                 return NULL;
 104
 105         if (right->type == EXPR_PREOP && right->op == '&')
 106                 right = strip_expr(right->unop);
 107
 108         if (right->type == EXPR_CALL)
 109                 return NULL;
 110
 111         return right;
 112 }
 113
 114 static struct expression *add_dereference(struct expression *expr)
 115 {
 116         struct symbol *type;
 117
 118         /*
 119          * We want to re-write "memcpy(foo, bar, sizeof(*foo));" as
 120          * "*foo = *bar;".
 121          */
 122
 123         expr = strip_expr(expr);
 124         if (!expr)
 125                 return NULL;
 126
 127         if (expr->type == EXPR_PREOP && expr->op == '&')
 128                 return strip_expr(expr->unop);
 129         type = get_type(expr);
 130         if (!type)
 131                 return NULL;
 132         if (type->type != SYM_PTR && type->type != SYM_ARRAY)
 133                 return NULL;
 134
 135         return deref_expression(expr);
 136 }
 137
 138 static struct expression *faked_expression;
 139 struct expression *get_faked_expression(void)
 140 {
 141         if (!__in_fake_assign)
 142                 return NULL;
 143         return faked_expression;
 144 }
 145
 146 static void split_fake_expr(struct expression *expr)
 147 {
 148         __in_fake_assign++;
 149         __in_fake_struct_assign++;
 150         __split_expr(expr);
 151         __in_fake_struct_assign--;
 152         __in_fake_assign--;
 153 }
 154
 155 static void handle_non_struct_assignments(struct expression *left, struct expression *right)
 156 {
 157         struct symbol *left_type, *right_type;
 158         struct expression *assign;
 159
 160         while (right && right->type == EXPR_ASSIGNMENT)
 161                 right = strip_parens(right->left);
 162
 163         if (!right)
 164                 right = unknown_value_expression(left);
 165
 166         left_type = get_type(left);
 167         right_type = get_type(right);
 168         if (!left_type || !right_type)
 169                 return;
 170
 171         if (right_type->type == SYM_ARRAY)
 172                 right = unknown_value_expression(left);
 173
 174         if (left_type->type == SYM_PTR) {
 175                 left = deref_expression(left);
 176                 assign = assign_expression(left, '=', right);
 177                 split_fake_expr(assign);
 178                 return;
 179         }
 180         if (left_type->type != SYM_BASETYPE)
 181                 return;
 182         assign = assign_expression(left, '=', right);
 183         split_fake_expr(assign);
 184 }
 185
 186 static void set_inner_struct_members(int mode, struct expression *faked, struct expression *left, struct expression *right, struct symbol *member)
 187 {
 188         struct expression *left_member;
 189         struct expression *right_expr = NULL;  /* silence GCC */
 190         struct expression *assign;
 191         struct symbol *base = get_real_base_type(member);
 192         struct symbol *tmp;
 193
 194         if (member->ident) {
 195                 left = member_expression(left, '.', member->ident);
 196                 if (mode == COPY_NORMAL && right)
 197                         right = member_expression(right, '.', member->ident);
 198         }
 199
 200         FOR_EACH_PTR(base->symbol_list, tmp) {
 201                 struct symbol *type;
 202
 203                 type = get_real_base_type(tmp);
 204                 if (!type)
 205                         continue;
 206
 207                 if (type->type == SYM_ARRAY)
 208                         continue;
 209                 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
 210                         set_inner_struct_members(mode, faked, left, right, tmp);
 211                         continue;
 212                 }
 213                 if (!tmp->ident)
 214                         continue;
 215
 216                 left_member = member_expression(left, '.', tmp->ident);
 217
 218                 right_expr = NULL;
 219                 if (mode == COPY_NORMAL && right)
 220                         right_expr = member_expression(right, '.', tmp->ident);
 221                 if (mode == COPY_ZERO)
 222                         right_expr = zero_expr();
 223                 if (!right_expr)
 224                         right_expr = unknown_value_expression(left_member);
 225
 226                 assign = assign_expression(left_member, '=', right_expr);
 227                 split_fake_expr(assign);
 228         } END_FOR_EACH_PTR(tmp);
 229 }
 230
 231 static void __struct_members_copy(int mode, struct expression *faked,
 232                                   struct expression *left,
 233                                   struct expression *right)
 234 {
 235         struct symbol *struct_type, *tmp, *type;
 236         struct expression *left_member;
 237         struct expression *right_expr;
 238         struct expression *assign;
 239
 240         if (__in_fake_assign || !left)
 241                 return;
 242         faked_expression = faked;
 243
 244         left = strip_expr(left);
 245         right = strip_expr(right);
 246
 247         if (left->type == EXPR_PREOP && left->op == '*' && is_pointer(left))
 248                 left = preop_expression(left, '(');
 249
 250         struct_type = get_struct_type(left);
 251         if (!struct_type) {
 252                 /*
 253                  * This is not a struct assignment obviously.  But this is where
 254                  * memcpy() is handled so it feels like a good place to add this
 255                  * code.
 256                  */
 257                 handle_non_struct_assignments(left, right);
 258                 goto done;
 259         }
 260
 261         if (mode == COPY_NORMAL)
 262                 right = get_right_base_expr(struct_type, right);
 263
 264         FOR_EACH_PTR(struct_type->symbol_list, tmp) {
 265                 type = get_real_base_type(tmp);
 266                 if (!type)
 267                         continue;
 268                 if (type->type == SYM_ARRAY)
 269                         continue;
 270
 271                 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
 272                         set_inner_struct_members(mode, faked, left, right, tmp);
 273                         continue;
 274                 }
 275
 276                 if (!tmp->ident)
 277                         continue;
 278
 279                 left_member = member_expression(left, '.', tmp->ident);
 280                 right_expr = NULL;
 281
 282                 if (mode == COPY_NORMAL && right)
 283                         right_expr = member_expression(right, '.', tmp->ident);
 284                 if (mode == COPY_ZERO)
 285                         right_expr = zero_expr();
 286                 if (!right_expr)
 287                         right_expr = unknown_value_expression(left_member);
 288
 289                 assign = assign_expression(left_member, '=', right_expr);
 290                 split_fake_expr(assign);
 291         } END_FOR_EACH_PTR(tmp);
 292
 293 done:
 294         faked_expression = NULL;
 295 }
 296
 297 static int returns_zeroed_mem(struct expression *expr)
 298 {
 299         struct expression *tmp;
 300         char *fn;
 301
 302         if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
 303                 return 0;
 304
 305         if (is_fake_call(expr)) {
 306                 tmp = get_faked_expression();
 307                 if (!tmp || tmp->type != EXPR_ASSIGNMENT || tmp->op != '=')
 308                         return 0;
 309                 expr = tmp->right;
 310                 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
 311                         return 0;
 312         }
 313
 314         fn = expr_to_var(expr->fn);
 315         if (!fn)
 316                 return 0;
 317         if (strcmp(fn, "kcalloc") == 0)
 318                 return 1;
 319         if (option_project == PROJ_KERNEL && strstr(fn, "zalloc"))
 320                 return 1;
 321         return 0;
 322 }
 323
 324 static int copy_containter_states(struct expression *left, struct expression *right, int offset)
 325 {
 326         char *left_name = NULL, *right_name = NULL;
 327         struct symbol *left_sym, *right_sym;
 328         struct sm_state *sm, *new_sm;
 329         int ret = 0;
 330         int len;
 331         char buf[64];
 332         char new_name[128];
 333
 334         right_name = expr_to_var_sym(right, &right_sym);
 335         if (!right_name || !right_sym)
 336                 goto free;
 337         left_name = expr_to_var_sym(left, &left_sym);
 338         if (!left_name || !left_sym)
 339                 goto free;
 340
 341         len = snprintf(buf, sizeof(buf), "%s(-%d)", right_name, offset);
 342         if (len >= sizeof(buf))
 343                 goto free;
 344
 345         FOR_EACH_SM_SAFE(__get_cur_stree(), sm) {
 346                 if (sm->sym != right_sym)
 347                         continue;
 348                 if (strncmp(sm->name, buf, len) != 0)
 349                         continue;
 350                 snprintf(new_name, sizeof(new_name), "%s%s", left_name, sm->name + len);
 351                 new_sm = clone_sm(sm);
 352                 new_sm->name = alloc_sname(new_name);
 353                 new_sm->sym = left_sym;
 354                 __set_sm(new_sm);
 355                 ret = 1;
 356         } END_FOR_EACH_SM_SAFE(sm);
 357 free:
 358         free_string(left_name);
 359         free_string(right_name);
 360         return ret;
 361 }
 362
 363 static int handle_param_offsets(struct expression *expr)
 364 {
 365         struct expression *right;
 366         sval_t sval;
 367
 368         right = strip_expr(expr->right);
 369
 370         if (right->type != EXPR_BINOP || right->op != '-')
 371                 return 0;
 372
 373         if (!get_value(right->right, &sval))
 374                 return 0;
 375
 376         right = get_assigned_expr(right->left);
 377         if (!right)
 378                 return 0;
 379         return copy_containter_states(expr->left, right, sval.value);
 380 }
 381
 382 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
 383 {
 384         struct expression *call, *arg;
 385         int offset;
 386
 387         if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 388                 return;
 389         call = strip_expr(expr->right);
 390         if (call->type != EXPR_CALL)
 391                 return;
 392         if (param != -1)
 393                 return;
 394         param = atoi(key);
 395         offset = atoi(value);
 396
 397         arg = get_argument_from_call_expr(call->args, param);
 398         if (!arg)
 399                 return;
 400
 401         copy_containter_states(expr->left, arg, -offset);
 402 }
 403
 404 void __fake_struct_member_assignments(struct expression *expr)
 405 {
 406         struct expression *left, *right;
 407         struct symbol *type;
 408         int mode;
 409
 410         if (expr->op != '=')
 411                 return;
 412
 413         if (is_noderef_ptr(expr->right))
 414                 return;
 415
 416         type = get_type(expr->left);
 417         if (!type)
 418                 return;
 419         if (type->type != SYM_PTR && type->type != SYM_STRUCT)
 420                 return;
 421
 422         if (handle_param_offsets(expr))
 423                 return;
 424
 425         left = expr->left;
 426         right = expr->right;
 427
 428         if (type->type == SYM_PTR) {
 429                 /* Convert "p = q;" to "*p = *q;" */
 430                 left = add_dereference(left);
 431                 right = add_dereference(right);
 432         }
 433
 434         if (returns_zeroed_mem(expr->right))
 435                 mode = COPY_ZERO;
 436         else if (types_equiv(get_type(left), get_type(right)))
 437                 mode = COPY_NORMAL;
 438         else
 439                 mode = COPY_UNKNOWN;
 440
 441         __struct_members_copy(mode, expr, left, right);
 442 }
 443
 444 static void match_memset(const char *fn, struct expression *expr, void *_size_arg)
 445 {
 446         struct expression *buf;
 447         struct expression *val;
 448         int mode;
 449
 450         buf = get_argument_from_call_expr(expr->args, 0);
 451         val = get_argument_from_call_expr(expr->args, 1);
 452
 453         buf = strip_expr(buf);
 454         if (expr_is_zero(val))
 455                 mode = COPY_ZERO;
 456         else
 457                 mode = COPY_UNKNOWN;
 458         __struct_members_copy(mode, expr, add_dereference(buf), NULL);
 459 }
 460
 461 static void match_memcpy(const char *fn, struct expression *expr, void *_arg)
 462 {
 463         struct expression *dest;
 464         struct expression *src;
 465         int mode;
 466
 467         dest = get_argument_from_call_expr(expr->args, 0);
 468         src = get_argument_from_call_expr(expr->args, 1);
 469
 470         if (types_equiv(get_type(src), get_type(dest)))
 471                 mode = COPY_NORMAL;
 472         else
 473                 mode = COPY_UNKNOWN;
 474
 475         __struct_members_copy(mode, expr, add_dereference(dest), add_dereference(src));
 476 }
 477
 478 static void match_memdup(const char *fn, struct expression *call_expr,
 479                         struct expression *expr, void *_unused)
 480 {
 481         struct expression *left, *right, *arg;
 482         int mode;
 483
 484         if (!expr || expr->type != EXPR_ASSIGNMENT)
 485                 return;
 486
 487         left = strip_expr(expr->left);
 488         right = strip_expr(expr->right);
 489
 490         if (right->type != EXPR_CALL)
 491                 return;
 492         arg = get_argument_from_call_expr(right->args, 0);
 493
 494         if (types_equiv(get_type(left), get_type(right)))
 495                 mode = COPY_NORMAL;
 496         else
 497                 mode = COPY_UNKNOWN;
 498
 499         __struct_members_copy(mode, expr, add_dereference(left), add_dereference(arg));
 500 }
 501
 502 static void match_memcpy_unknown(const char *fn, struct expression *expr, void *_arg)
 503 {
 504         struct expression *dest;
 505
 506         dest = get_argument_from_call_expr(expr->args, 0);
 507         __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(dest), NULL);
 508 }
 509
 510 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
 511 {
 512         struct expression *arg;
 513         int i;
 514
 515         i = -1;
 516         FOR_EACH_PTR(expr->args, arg) {
 517                 if (++i < 2)
 518                         continue;
 519                 __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(arg), NULL);
 520         } END_FOR_EACH_PTR(arg);
 521 }
 522
 523 static void unop_expr(struct expression *expr)
 524 {
 525         if (expr->op != SPECIAL_INCREMENT &&
 526             expr->op != SPECIAL_DECREMENT)
 527                 return;
 528
 529         if (!is_pointer(expr))
 530                 return;
 531         faked_expression = expr;
 532         __struct_members_copy(COPY_UNKNOWN, expr, expr->unop, NULL);
 533         faked_expression = NULL;
 534 }
 535
 536 static void register_clears_param(void)
 537 {
 538         struct token *token;
 539         char name[256];
 540         const char *function;
 541         int param;
 542
 543         if (option_project == PROJ_NONE)
 544                 return;
 545
 546         snprintf(name, 256, "%s.clears_argument", option_project_str);
 547
 548         token = get_tokens_file(name);
 549         if (!token)
 550                 return;
 551         if (token_type(token) != TOKEN_STREAMBEGIN)
 552                 return;
 553         token = token->next;
 554         while (token_type(token) != TOKEN_STREAMEND) {
 555                 if (token_type(token) != TOKEN_IDENT)
 556                         return;
 557                 function = show_ident(token->ident);
 558                 token = token->next;
 559                 if (token_type(token) != TOKEN_NUMBER)
 560                         return;
 561                 param = atoi(token->number);
 562                 add_function_hook(function, &match_memcpy_unknown, INT_PTR(param));
 563                 token = token->next;
 564         }
 565         clear_token_alloc();
 566 }
 567
 568 static void db_buf_cleared(struct expression *expr, int param, char *key, char *value)
 569 {
 570         struct expression *arg;
 571
 572         arg = gen_expr_from_param_key(expr, param, key);
 573         if (!arg)
 574                 return;
 575
 576         if (strcmp(value, "0") == 0)
 577                 __struct_members_copy(COPY_ZERO, expr, arg, NULL);
 578         else
 579                 __struct_members_copy(COPY_UNKNOWN, expr, arg, NULL);
 580 }
 581
 582 static void db_param_add_set(struct expression *expr, int param, char *key, char *value)
 583 {
 584         struct expression *arg;
 585         struct symbol *type;
 586
 587         arg = gen_expr_from_param_key(expr, param, key);
 588         if (!arg)
 589                 return;
 590         type = get_type(arg);
 591         if (!type)
 592                 return;
 593         if (type->type != SYM_STRUCT && type->type != SYM_UNION)
 594                 return;
 595
 596         __struct_members_copy(COPY_UNKNOWN, expr, arg, NULL);
 597 }
 598
 599 void register_struct_assignment(int id)
 600 {
 601         add_function_hook("memset", &match_memset, NULL);
 602         add_function_hook("__memset", &match_memset, NULL);
 603         add_function_hook("__builtin_memset", &match_memset, NULL);
 604
 605         add_function_hook("memcpy", &match_memcpy, INT_PTR(0));
 606         add_function_hook("memmove", &match_memcpy, INT_PTR(0));
 607         add_function_hook("__memcpy", &match_memcpy, INT_PTR(0));
 608         add_function_hook("__memmove", &match_memcpy, INT_PTR(0));
 609         add_function_hook("__builtin_memcpy", &match_memcpy, INT_PTR(0));
 610         add_function_hook("__builtin_memmove", &match_memcpy, INT_PTR(0));
 611
 612         if (option_project == PROJ_KERNEL)
 613                 return_implies_state_sval("kmemdup", valid_ptr_min_sval, valid_ptr_max_sval, &match_memdup, NULL);
 614
 615         add_function_hook("sscanf", &match_sscanf, NULL);
 616
 617         add_hook(&unop_expr, OP_HOOK);
 618         register_clears_param();
 619         select_return_states_hook(BUF_CLEARED, &db_buf_cleared);
 620         select_return_states_hook(PARAM_ADD, &db_param_add_set);
 621         select_return_states_hook(PARAM_SET, &db_param_add_set);
 622
 623         select_return_states_hook(CONTAINER, &returns_container_of);
 624 }