capped: fix handling of assignments
[smatch.git] / smatch_struct_assignment.c
blob99f2b85c805c6f4243d965b01bae8c4c23f2a506
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;
369 if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
370 set_inner_struct_members(mode, faked, left, right, tmp,
371 care_left, care_right,
372 assign_handler, data);
373 continue;
376 if (!tmp->ident)
377 continue;
379 left_member = member_expression(left, '.', tmp->ident);
380 right_expr = NULL;
382 if (mode == COPY_NORMAL && right)
383 right_expr = member_expression(right, '.', tmp->ident);
384 if (mode == COPY_ZERO)
385 right_expr = zero_expr();
386 if (!right_expr)
387 right_expr = unknown_value_expression(left_member);
389 assign = assign_expression(left_member, '=', right_expr);
390 assign_handler(assign, data);
391 } END_FOR_EACH_PTR(tmp);
393 free_stree(&care_left);
394 free_stree(&care_right);
395 done:
396 faked_expression = NULL;
399 static struct expression *zero_allocation;
400 static void match_allocation(struct expression *expr,
401 const char *name, struct symbol *sym,
402 struct allocation_info *info)
404 if (!info->zeroed)
405 return;
407 while (expr && expr->type == EXPR_ASSIGNMENT)
408 expr = strip_expr(expr->right);
410 zero_allocation = expr;
413 static int returns_zeroed_mem(struct expression *expr)
415 struct expression *tmp;
417 tmp = get_assigned_expr(expr);
418 if (tmp)
419 expr = tmp;
421 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
422 return 0;
424 if (is_fake_call(expr)) {
425 tmp = get_faked_expression();
426 if (!tmp || tmp->type != EXPR_ASSIGNMENT || tmp->op != '=')
427 return 0;
428 expr = tmp->right;
429 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
430 return 0;
433 return expr == zero_allocation;
436 static int copy_containter_states(struct expression *left, struct expression *right, int offset)
438 char *left_name = NULL, *right_name = NULL;
439 struct symbol *left_sym, *right_sym;
440 struct sm_state *sm, *new_sm;
441 int ret = 0;
442 int len;
443 char buf[64];
444 char new_name[128];
446 right_name = expr_to_var_sym(right, &right_sym);
447 if (!right_name || !right_sym)
448 goto free;
449 left_name = expr_to_var_sym(left, &left_sym);
450 if (!left_name || !left_sym)
451 goto free;
453 len = snprintf(buf, sizeof(buf), "%s(-%d)", right_name, offset);
454 if (len >= sizeof(buf))
455 goto free;
457 FOR_EACH_SM_SAFE(__get_cur_stree(), sm) {
458 if (sm->sym != right_sym)
459 continue;
460 if (strncmp(sm->name, buf, len) != 0)
461 continue;
462 snprintf(new_name, sizeof(new_name), "%s%s", left_name, sm->name + len);
463 new_sm = clone_sm(sm);
464 new_sm->name = alloc_sname(new_name);
465 new_sm->sym = left_sym;
466 __set_sm(new_sm);
467 ret = 1;
468 } END_FOR_EACH_SM_SAFE(sm);
469 free:
470 free_string(left_name);
471 free_string(right_name);
472 return ret;
475 static int handle_param_offsets(struct expression *expr)
477 struct expression *right;
478 sval_t sval;
480 right = strip_expr(expr->right);
482 if (right->type != EXPR_BINOP || right->op != '-')
483 return 0;
485 if (!get_value(right->right, &sval))
486 return 0;
488 right = get_assigned_expr(right->left);
489 if (!right)
490 return 0;
491 return copy_containter_states(expr->left, right, sval.value);
494 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
496 struct expression *call, *arg;
497 int offset;
499 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
500 return;
501 call = strip_expr(expr->right);
502 if (call->type != EXPR_CALL)
503 return;
504 if (param != -1)
505 return;
506 param = atoi(key);
507 offset = atoi(value);
509 arg = get_argument_from_call_expr(call->args, param);
510 if (!arg)
511 return;
513 copy_containter_states(expr->left, arg, -offset);
516 void __fake_struct_member_assignments(struct expression *expr)
518 struct expression *left, *right;
519 struct symbol *type;
520 int mode;
522 if (expr->op != '=')
523 return;
525 if (is_noderef_ptr(expr->right))
526 return;
528 type = get_type(expr->left);
529 if (!type)
530 return;
531 if (type->type != SYM_PTR && type->type != SYM_STRUCT)
532 return;
534 if (handle_param_offsets(expr))
535 return;
537 left = expr->left;
538 right = expr->right;
540 if (type->type == SYM_PTR) {
541 /* Convert "p = q;" to "*p = *q;" */
542 left = add_dereference(left);
543 right = add_dereference(right);
546 if (returns_zeroed_mem(expr->right))
547 mode = COPY_ZERO;
548 else if (types_equiv(get_type(left), get_type(right)))
549 mode = COPY_NORMAL;
550 else
551 mode = COPY_UNKNOWN;
553 if (is_pointer(left)) {
554 struct expression *assign;
556 assign = assign_expression(left, '=', right);
557 split_fake_expr(assign, 0);
560 __struct_members_copy(mode, expr, left, right, split_fake_expr, NULL);
563 static void match_memset(const char *fn, struct expression *expr, void *_size_arg)
565 struct expression *buf;
566 struct expression *val;
567 int mode;
569 buf = get_argument_from_call_expr(expr->args, 0);
570 val = get_argument_from_call_expr(expr->args, 1);
572 buf = strip_expr(buf);
573 if (expr_is_zero(val))
574 mode = COPY_ZERO;
575 else
576 mode = COPY_UNKNOWN;
577 __struct_members_copy(mode, expr, add_dereference(buf), NULL, split_fake_expr, NULL);
580 static void match_memcpy(const char *fn, struct expression *expr, void *_arg)
582 struct expression *dest;
583 struct expression *src;
584 int mode;
586 dest = get_argument_from_call_expr(expr->args, 0);
587 src = get_argument_from_call_expr(expr->args, 1);
589 if (types_equiv(get_type(src), get_type(dest)))
590 mode = COPY_NORMAL;
591 else
592 mode = COPY_UNKNOWN;
594 __struct_members_copy(mode, expr, add_dereference(dest), add_dereference(src), split_fake_expr, NULL);
597 static void match_memdup(const char *fn, struct expression *call_expr,
598 struct expression *expr, void *_unused)
600 struct expression *left, *right, *arg;
601 int mode;
603 if (!expr || expr->type != EXPR_ASSIGNMENT)
604 return;
606 left = strip_expr(expr->left);
607 right = strip_expr(expr->right);
609 if (right->type != EXPR_CALL)
610 return;
611 arg = get_argument_from_call_expr(right->args, 0);
613 if (types_equiv(get_type(left), get_type(right)))
614 mode = COPY_NORMAL;
615 else
616 mode = COPY_UNKNOWN;
618 __struct_members_copy(mode, expr, add_dereference(left), add_dereference(arg), split_fake_expr, NULL);
621 static void match_memcpy_unknown(const char *fn, struct expression *expr, void *_arg)
623 struct expression *dest;
625 dest = get_argument_from_call_expr(expr->args, 0);
626 __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(dest), NULL, split_fake_expr, NULL);
629 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
631 struct expression *arg;
632 int i;
634 i = -1;
635 FOR_EACH_PTR(expr->args, arg) {
636 if (++i < 2)
637 continue;
638 __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(arg), NULL, split_fake_expr, NULL);
639 } END_FOR_EACH_PTR(arg);
642 static void unop_expr(struct expression *expr)
644 if (expr->op != SPECIAL_INCREMENT &&
645 expr->op != SPECIAL_DECREMENT)
646 return;
648 if (!is_pointer(expr))
649 return;
650 faked_expression = expr;
651 __struct_members_copy(COPY_UNKNOWN, expr, expr->unop, NULL, split_fake_expr, NULL);
652 faked_expression = NULL;
655 static void register_clears_param(void)
657 struct token *token;
658 char name[256];
659 const char *function;
660 int param;
662 if (option_project == PROJ_NONE)
663 return;
665 snprintf(name, 256, "%s.clears_argument", option_project_str);
667 token = get_tokens_file(name);
668 if (!token)
669 return;
670 if (token_type(token) != TOKEN_STREAMBEGIN)
671 return;
672 token = token->next;
673 while (token_type(token) != TOKEN_STREAMEND) {
674 if (token_type(token) != TOKEN_IDENT)
675 return;
676 function = show_ident(token->ident);
677 token = token->next;
678 if (token_type(token) != TOKEN_NUMBER)
679 return;
680 param = atoi(token->number);
681 add_function_hook(function, &match_memcpy_unknown, INT_PTR(param));
682 token = token->next;
684 clear_token_alloc();
687 void create_recursive_fake_assignments(struct expression *expr,
688 void (*assign_handler)(struct expression *expr, void *data),
689 void *data)
691 __struct_members_copy(COPY_UNKNOWN, expr, expr, NULL, assign_handler, data);
694 static void db_buf_cleared(struct expression *expr, int param, char *key, char *value)
696 struct expression *arg;
698 arg = gen_expr_from_param_key(expr, param, key);
699 if (!arg)
700 return;
702 __in_buf_clear++;
703 if (strcmp(value, "0") == 0)
704 __struct_members_copy(COPY_ZERO, expr, arg, NULL, split_fake_expr, NULL);
705 else
706 __struct_members_copy(COPY_UNKNOWN, expr, arg, NULL, split_fake_expr, NULL);
707 __in_buf_clear--;
710 void register_struct_assignment(int id)
712 my_id = id;
714 add_function_data((unsigned long *)&faked_expression);
716 add_function_hook("memset", &match_memset, NULL);
717 add_function_hook("__memset", &match_memset, NULL);
718 add_function_hook("__builtin_memset", &match_memset, NULL);
720 add_function_hook("memcpy", &match_memcpy, INT_PTR(0));
721 add_function_hook("memmove", &match_memcpy, INT_PTR(0));
722 add_function_hook("__memcpy", &match_memcpy, INT_PTR(0));
723 add_function_hook("__memmove", &match_memcpy, INT_PTR(0));
724 add_function_hook("__builtin_memcpy", &match_memcpy, INT_PTR(0));
725 add_function_hook("__builtin_memmove", &match_memcpy, INT_PTR(0));
727 if (option_project == PROJ_KERNEL) {
728 return_implies_state_sval("kmemdup", valid_ptr_min_sval, valid_ptr_max_sval, &match_memdup, NULL);
729 add_function_hook("copy_from_user", &match_memcpy, INT_PTR(0));
730 add_function_hook("_copy_from_user", &match_memcpy, INT_PTR(0));
731 add_function_hook("memcpy_fromio", &match_memcpy, INT_PTR(0));
732 add_function_hook("__memcpy_fromio", &match_memcpy, INT_PTR(0));
735 add_function_hook("sscanf", &match_sscanf, NULL);
736 add_allocation_hook_early(&match_allocation);
738 add_hook(&unop_expr, OP_HOOK);
739 register_clears_param();
740 select_return_states_hook(BUF_CLEARED, &db_buf_cleared);
741 select_return_states_hook(BUF_ADD, &db_buf_cleared);
743 select_return_states_hook(CONTAINER, &returns_container_of);