struct_assignment: delete some dead code
[smatch.git] / smatch_struct_assignment.c
blob0cd7ecc7fd3ee86cfedd62ec0db43a4e3044adbc
1 /*
2 * Copyright (C) 2014 Oracle.
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.
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.
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
19 * This file started out by saying that if you have:
21 * struct foo one, two;
22 * ...
23 * one = two;
25 * That's equivalent to saying:
27 * one.x = two.x;
28 * one.y = two.y;
30 * Turning an assignment like that into a bunch of small fake assignments is
31 * really useful.
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:
37 * p1 = p2;
39 * Is the same as:
41 * p1->x = p2->x;
42 * p1->y = p2->y;
44 * The problem is that you can go a bit crazy with pointers to pointers.
46 * p1->x->y->z->one->two->three = p2->x->y->z->one->two->three;
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.
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.
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.
62 #include "smatch.h"
63 #include "smatch_slist.h"
64 #include "smatch_extra.h"
66 static int my_id;
68 enum {
69 COPY_NORMAL,
70 COPY_UNKNOWN,
71 COPY_ZERO,
74 static struct symbol *get_struct_type(struct expression *expr)
76 struct symbol *type;
78 type = get_type(expr);
79 if (!type)
80 return NULL;
81 if (type->type == SYM_PTR) {
82 type = get_real_base_type(type);
83 if (!type)
84 return NULL;
86 if (type->type == SYM_STRUCT)
87 return type;
88 if (type->type == SYM_UNION)
89 return type;
90 return NULL;
93 static struct expression *get_right_base_expr(struct symbol *left_type, struct expression *right)
95 struct symbol *struct_type;
97 if (!right)
98 return NULL;
100 struct_type = get_struct_type(right);
101 if (!struct_type)
102 return NULL;
103 if (struct_type != left_type)
104 return NULL;
106 if (right->type == EXPR_PREOP && right->op == '&')
107 right = strip_expr(right->unop);
109 if (right->type == EXPR_CALL)
110 return NULL;
112 return right;
115 static struct expression *add_dereference(struct expression *expr)
117 struct symbol *type;
120 * We want to re-write "memcpy(foo, bar, sizeof(*foo));" as
121 * "*foo = *bar;".
124 expr = strip_expr(expr);
125 if (!expr)
126 return NULL;
128 if (expr->type == EXPR_PREOP && expr->op == '&')
129 return strip_expr(expr->unop);
130 type = get_type(expr);
131 if (!type)
132 return NULL;
133 if (type->type != SYM_PTR && type->type != SYM_ARRAY)
134 return NULL;
136 return deref_expression(expr);
139 static struct expression *faked_expression;
140 struct expression *get_faked_expression(void)
142 if (!__in_fake_assign)
143 return NULL;
144 return faked_expression;
147 static void split_fake_expr(struct expression *expr, void *unused)
149 __in_fake_assign++;
150 __in_fake_struct_assign++;
151 __split_expr(expr);
152 __in_fake_struct_assign--;
153 __in_fake_assign--;
156 static void handle_non_struct_assignments(struct expression *left, struct expression *right,
157 void (*assign_handler)(struct expression *expr, void *data),
158 void *data)
160 struct symbol *left_type, *right_type;
161 struct expression *assign;
163 while (right && right->type == EXPR_ASSIGNMENT)
164 right = strip_parens(right->left);
166 if (!right)
167 right = unknown_value_expression(left);
169 left_type = get_type(left);
170 right_type = get_type(right);
171 if (!left_type || !right_type)
172 return;
174 if (right_type->type == SYM_ARRAY)
175 right = unknown_value_expression(left);
177 if (left_type->type == SYM_PTR) {
178 left = deref_expression(left);
179 assign = assign_expression(left, '=', right);
180 assign_handler(assign, data);
181 return;
183 if (left_type->type != SYM_BASETYPE)
184 return;
185 assign = assign_expression(left, '=', right);
186 assign_handler(assign, data);
189 static bool dont_care(int mode, struct stree *left_care, struct stree *right_care,
190 struct expression *left, struct expression *right)
192 struct symbol *left_sym, *right_sym;
193 int left_len = 0, right_len = 0;
194 char *left_name = NULL;
195 char *right_name = NULL;
196 struct sm_state *sm;
197 int ret = false;
198 int len;
200 if (mode == COPY_ZERO)
201 return false;
203 left_name = expr_to_str_sym(left, &left_sym);
204 if (left_name && !strstr(left_name, "->"))
205 goto free;
206 if (left_name)
207 left_len = strlen(left_name);
209 ret = true;
210 FOR_EACH_SM(left_care, sm) {
211 len = strlen(sm->name);
212 if (left_name && left_sym == sm->sym &&
213 len >= left_len &&
214 strncmp(sm->name, left_name, len)) {
215 ret = false;
216 goto free;
218 } END_FOR_EACH_SM(sm);
220 right_name = expr_to_str_sym(right, &right_sym);
221 if (right_name)
222 right_len = strlen(right_name);
223 if (!right_sym || left_sym == right_sym)
224 goto free;
226 FOR_EACH_SM(right_care, sm) {
227 len = strlen(sm->name);
228 if (right_name && right_sym == sm->sym &&
229 len >= right_len &&
230 strncmp(sm->name, right_name, len)) {
231 ret = false;
232 goto free;
234 } END_FOR_EACH_SM(sm);
236 free:
237 free_string(left_name);
238 free_string(right_name);
239 return ret;
242 static void set_inner_struct_members(int mode, struct expression *faked,
243 struct expression *left, struct expression *right, struct symbol *member,
244 struct stree *care_left, struct stree *care_right,
245 void (*assign_handler)(struct expression *expr, void *data),
246 void *data)
248 struct expression *left_member;
249 struct expression *right_expr;
250 struct expression *assign;
251 struct symbol *base = get_real_base_type(member);
252 struct symbol *tmp;
254 if (member->ident) {
255 left = member_expression(left, '.', member->ident);
256 if (mode == COPY_NORMAL && right)
257 right = member_expression(right, '.', member->ident);
260 if (dont_care(mode, care_left, care_right, left, right))
261 return;
263 FOR_EACH_PTR(base->symbol_list, tmp) {
264 struct symbol *type;
266 type = get_real_base_type(tmp);
267 if (!type)
268 continue;
270 if (type->type == SYM_ARRAY)
271 continue;
272 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
273 set_inner_struct_members(mode, faked, left, right, tmp, care_left, care_right, assign_handler, data);
274 continue;
276 if (!tmp->ident)
277 continue;
279 left_member = member_expression(left, '.', tmp->ident);
281 right_expr = NULL;
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);
289 assign = assign_expression(left_member, '=', right_expr);
290 assign_handler(assign, data);
291 } END_FOR_EACH_PTR(tmp);
294 static void get_care_stree(struct expression *left, struct stree **left_care,
295 struct expression *right, struct stree **right_care)
297 struct symbol *left_sym, *right_sym;
298 struct sm_state *sm;
300 *left_care = NULL;
301 *right_care = NULL;
303 left_sym = expr_to_sym(left);
304 right_sym = expr_to_sym(right);
306 FOR_EACH_SM(__get_cur_stree(), sm) {
307 if (!sm->sym)
308 continue;
309 if (sm->sym == left_sym)
310 overwrite_sm_state_stree(left_care, sm);
311 } END_FOR_EACH_SM(sm);
313 if (!right_sym || left_sym == right_sym)
314 return;
316 FOR_EACH_SM(__get_cur_stree(), sm) {
317 if (!sm->sym)
318 continue;
319 if (sm->sym == right_sym)
320 overwrite_sm_state_stree(right_care, sm);
321 } END_FOR_EACH_SM(sm);
324 static void __struct_members_copy(int mode, struct expression *faked,
325 struct expression *left,
326 struct expression *right,
327 void (*assign_handler)(struct expression *expr, void *data),
328 void *data)
330 struct symbol *struct_type, *tmp, *type;
331 struct stree *care_left = NULL;
332 struct stree *care_right = NULL;
333 struct expression *left_member;
334 struct expression *right_expr;
335 struct expression *assign;
337 if (__in_fake_assign || !left)
338 return;
340 faked_expression = faked;
342 left = strip_expr(left);
343 right = strip_expr(right);
345 if (left->type == EXPR_PREOP && left->op == '*' && is_pointer(left))
346 left = preop_expression(left, '(');
348 struct_type = get_struct_type(left);
349 if (!struct_type) {
351 * This is not a struct assignment obviously. But this is where
352 * memcpy() is handled so it feels like a good place to add this
353 * code.
355 handle_non_struct_assignments(left, right, assign_handler, data);
356 goto done;
359 if (mode == COPY_NORMAL)
360 right = get_right_base_expr(struct_type, right);
362 if (mode != COPY_ZERO)
363 get_care_stree(left, &care_left, right, &care_right);
364 FOR_EACH_PTR(struct_type->symbol_list, tmp) {
365 type = get_real_base_type(tmp);
366 if (!type)
367 continue;
368 if (type->type == SYM_ARRAY)
369 continue;
371 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
372 set_inner_struct_members(mode, faked, left, right, tmp,
373 care_left, care_right,
374 assign_handler, data);
375 continue;
378 if (!tmp->ident)
379 continue;
381 left_member = member_expression(left, '.', tmp->ident);
382 right_expr = NULL;
384 if (mode == COPY_NORMAL && right)
385 right_expr = member_expression(right, '.', tmp->ident);
386 if (mode == COPY_ZERO)
387 right_expr = zero_expr();
388 if (!right_expr)
389 right_expr = unknown_value_expression(left_member);
391 assign = assign_expression(left_member, '=', right_expr);
392 assign_handler(assign, data);
393 } END_FOR_EACH_PTR(tmp);
395 free_stree(&care_left);
396 free_stree(&care_right);
397 done:
398 faked_expression = NULL;
401 static int returns_zeroed_mem(struct expression *expr)
403 struct expression *tmp;
404 char *fn;
406 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
407 return 0;
409 if (is_fake_call(expr)) {
410 tmp = get_faked_expression();
411 if (!tmp || tmp->type != EXPR_ASSIGNMENT || tmp->op != '=')
412 return 0;
413 expr = tmp->right;
414 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
415 return 0;
418 fn = expr_to_var(expr->fn);
419 if (!fn)
420 return 0;
421 if (strcmp(fn, "kcalloc") == 0)
422 return 1;
423 if (option_project == PROJ_KERNEL && strstr(fn, "zalloc"))
424 return 1;
425 return 0;
428 static int copy_containter_states(struct expression *left, struct expression *right, int offset)
430 char *left_name = NULL, *right_name = NULL;
431 struct symbol *left_sym, *right_sym;
432 struct sm_state *sm, *new_sm;
433 int ret = 0;
434 int len;
435 char buf[64];
436 char new_name[128];
438 right_name = expr_to_var_sym(right, &right_sym);
439 if (!right_name || !right_sym)
440 goto free;
441 left_name = expr_to_var_sym(left, &left_sym);
442 if (!left_name || !left_sym)
443 goto free;
445 len = snprintf(buf, sizeof(buf), "%s(-%d)", right_name, offset);
446 if (len >= sizeof(buf))
447 goto free;
449 FOR_EACH_SM_SAFE(__get_cur_stree(), sm) {
450 if (sm->sym != right_sym)
451 continue;
452 if (strncmp(sm->name, buf, len) != 0)
453 continue;
454 snprintf(new_name, sizeof(new_name), "%s%s", left_name, sm->name + len);
455 new_sm = clone_sm(sm);
456 new_sm->name = alloc_sname(new_name);
457 new_sm->sym = left_sym;
458 __set_sm(new_sm);
459 ret = 1;
460 } END_FOR_EACH_SM_SAFE(sm);
461 free:
462 free_string(left_name);
463 free_string(right_name);
464 return ret;
467 static int handle_param_offsets(struct expression *expr)
469 struct expression *right;
470 sval_t sval;
472 right = strip_expr(expr->right);
474 if (right->type != EXPR_BINOP || right->op != '-')
475 return 0;
477 if (!get_value(right->right, &sval))
478 return 0;
480 right = get_assigned_expr(right->left);
481 if (!right)
482 return 0;
483 return copy_containter_states(expr->left, right, sval.value);
486 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
488 struct expression *call, *arg;
489 int offset;
491 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
492 return;
493 call = strip_expr(expr->right);
494 if (call->type != EXPR_CALL)
495 return;
496 if (param != -1)
497 return;
498 param = atoi(key);
499 offset = atoi(value);
501 arg = get_argument_from_call_expr(call->args, param);
502 if (!arg)
503 return;
505 copy_containter_states(expr->left, arg, -offset);
508 void __fake_struct_member_assignments(struct expression *expr)
510 struct expression *left, *right;
511 struct symbol *type;
512 int mode;
514 if (expr->op != '=')
515 return;
517 if (is_noderef_ptr(expr->right))
518 return;
520 type = get_type(expr->left);
521 if (!type)
522 return;
523 if (type->type != SYM_PTR && type->type != SYM_STRUCT)
524 return;
526 if (handle_param_offsets(expr))
527 return;
529 left = expr->left;
530 right = expr->right;
532 if (type->type == SYM_PTR) {
533 /* Convert "p = q;" to "*p = *q;" */
534 left = add_dereference(left);
535 right = add_dereference(right);
538 if (returns_zeroed_mem(expr->right))
539 mode = COPY_ZERO;
540 else if (types_equiv(get_type(left), get_type(right)))
541 mode = COPY_NORMAL;
542 else
543 mode = COPY_UNKNOWN;
545 __struct_members_copy(mode, expr, left, right, split_fake_expr, NULL);
548 static void match_memset(const char *fn, struct expression *expr, void *_size_arg)
550 struct expression *buf;
551 struct expression *val;
552 int mode;
554 buf = get_argument_from_call_expr(expr->args, 0);
555 val = get_argument_from_call_expr(expr->args, 1);
557 buf = strip_expr(buf);
558 if (expr_is_zero(val))
559 mode = COPY_ZERO;
560 else
561 mode = COPY_UNKNOWN;
562 __struct_members_copy(mode, expr, add_dereference(buf), NULL, split_fake_expr, NULL);
565 static void match_memcpy(const char *fn, struct expression *expr, void *_arg)
567 struct expression *dest;
568 struct expression *src;
569 int mode;
571 dest = get_argument_from_call_expr(expr->args, 0);
572 src = get_argument_from_call_expr(expr->args, 1);
574 if (types_equiv(get_type(src), get_type(dest)))
575 mode = COPY_NORMAL;
576 else
577 mode = COPY_UNKNOWN;
579 __struct_members_copy(mode, expr, add_dereference(dest), add_dereference(src), split_fake_expr, NULL);
582 static void match_memdup(const char *fn, struct expression *call_expr,
583 struct expression *expr, void *_unused)
585 struct expression *left, *right, *arg;
586 int mode;
588 if (!expr || expr->type != EXPR_ASSIGNMENT)
589 return;
591 left = strip_expr(expr->left);
592 right = strip_expr(expr->right);
594 if (right->type != EXPR_CALL)
595 return;
596 arg = get_argument_from_call_expr(right->args, 0);
598 if (types_equiv(get_type(left), get_type(right)))
599 mode = COPY_NORMAL;
600 else
601 mode = COPY_UNKNOWN;
603 __struct_members_copy(mode, expr, add_dereference(left), add_dereference(arg), split_fake_expr, NULL);
606 static void match_memcpy_unknown(const char *fn, struct expression *expr, void *_arg)
608 struct expression *dest;
610 dest = get_argument_from_call_expr(expr->args, 0);
611 __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(dest), NULL, split_fake_expr, NULL);
614 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
616 struct expression *arg;
617 int i;
619 i = -1;
620 FOR_EACH_PTR(expr->args, arg) {
621 if (++i < 2)
622 continue;
623 __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(arg), NULL, split_fake_expr, NULL);
624 } END_FOR_EACH_PTR(arg);
627 static void unop_expr(struct expression *expr)
629 if (expr->op != SPECIAL_INCREMENT &&
630 expr->op != SPECIAL_DECREMENT)
631 return;
633 if (!is_pointer(expr))
634 return;
635 faked_expression = expr;
636 __struct_members_copy(COPY_UNKNOWN, expr, expr->unop, NULL, split_fake_expr, NULL);
637 faked_expression = NULL;
640 static void register_clears_param(void)
642 struct token *token;
643 char name[256];
644 const char *function;
645 int param;
647 if (option_project == PROJ_NONE)
648 return;
650 snprintf(name, 256, "%s.clears_argument", option_project_str);
652 token = get_tokens_file(name);
653 if (!token)
654 return;
655 if (token_type(token) != TOKEN_STREAMBEGIN)
656 return;
657 token = token->next;
658 while (token_type(token) != TOKEN_STREAMEND) {
659 if (token_type(token) != TOKEN_IDENT)
660 return;
661 function = show_ident(token->ident);
662 token = token->next;
663 if (token_type(token) != TOKEN_NUMBER)
664 return;
665 param = atoi(token->number);
666 add_function_hook(function, &match_memcpy_unknown, INT_PTR(param));
667 token = token->next;
669 clear_token_alloc();
672 void create_recursive_fake_assignments(struct expression *expr,
673 void (*assign_handler)(struct expression *expr, void *data),
674 void *data)
676 __struct_members_copy(COPY_UNKNOWN, expr, expr, NULL, assign_handler, data);
679 static void db_buf_cleared(struct expression *expr, int param, char *key, char *value)
681 struct expression *arg;
683 arg = gen_expr_from_param_key(expr, param, key);
684 if (!arg)
685 return;
687 __in_buf_clear++;
688 if (strcmp(value, "0") == 0)
689 __struct_members_copy(COPY_ZERO, expr, arg, NULL, split_fake_expr, NULL);
690 else
691 __struct_members_copy(COPY_UNKNOWN, expr, arg, NULL, split_fake_expr, NULL);
692 __in_buf_clear--;
695 void register_struct_assignment(int id)
697 my_id = id;
699 add_function_data((unsigned long *)&faked_expression);
701 add_function_hook("memset", &match_memset, NULL);
702 add_function_hook("__memset", &match_memset, NULL);
703 add_function_hook("__builtin_memset", &match_memset, NULL);
705 add_function_hook("memcpy", &match_memcpy, INT_PTR(0));
706 add_function_hook("memmove", &match_memcpy, INT_PTR(0));
707 add_function_hook("__memcpy", &match_memcpy, INT_PTR(0));
708 add_function_hook("__memmove", &match_memcpy, INT_PTR(0));
709 add_function_hook("__builtin_memcpy", &match_memcpy, INT_PTR(0));
710 add_function_hook("__builtin_memmove", &match_memcpy, INT_PTR(0));
712 if (option_project == PROJ_KERNEL) {
713 return_implies_state_sval("kmemdup", valid_ptr_min_sval, valid_ptr_max_sval, &match_memdup, NULL);
714 add_function_hook("copy_from_user", &match_memcpy, INT_PTR(0));
715 add_function_hook("_copy_from_user", &match_memcpy, INT_PTR(0));
716 add_function_hook("memcpy_fromio", &match_memcpy, INT_PTR(0));
717 add_function_hook("__memcpy_fromio", &match_memcpy, INT_PTR(0));
720 add_function_hook("sscanf", &match_sscanf, NULL);
722 add_hook(&unop_expr, OP_HOOK);
723 register_clears_param();
724 select_return_states_hook(BUF_CLEARED, &db_buf_cleared);
725 select_return_states_hook(BUF_ADD, &db_buf_cleared);
727 select_return_states_hook(CONTAINER, &returns_container_of);