db/fixup_kernel.sh: fix clear_user() handling
[smatch.git] / smatch_struct_assignment.c
blob99867770a1d376bb8f00d269acc066d82885a7e8
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 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
418 return 0;
420 if (is_fake_call(expr)) {
421 tmp = get_faked_expression();
422 if (!tmp || tmp->type != EXPR_ASSIGNMENT || tmp->op != '=')
423 return 0;
424 expr = tmp->right;
425 if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
426 return 0;
429 return expr == zero_allocation;
432 static int copy_containter_states(struct expression *left, struct expression *right, int offset)
434 char *left_name = NULL, *right_name = NULL;
435 struct symbol *left_sym, *right_sym;
436 struct sm_state *sm, *new_sm;
437 int ret = 0;
438 int len;
439 char buf[64];
440 char new_name[128];
442 right_name = expr_to_var_sym(right, &right_sym);
443 if (!right_name || !right_sym)
444 goto free;
445 left_name = expr_to_var_sym(left, &left_sym);
446 if (!left_name || !left_sym)
447 goto free;
449 len = snprintf(buf, sizeof(buf), "%s(-%d)", right_name, offset);
450 if (len >= sizeof(buf))
451 goto free;
453 FOR_EACH_SM_SAFE(__get_cur_stree(), sm) {
454 if (sm->sym != right_sym)
455 continue;
456 if (strncmp(sm->name, buf, len) != 0)
457 continue;
458 snprintf(new_name, sizeof(new_name), "%s%s", left_name, sm->name + len);
459 new_sm = clone_sm(sm);
460 new_sm->name = alloc_sname(new_name);
461 new_sm->sym = left_sym;
462 __set_sm(new_sm);
463 ret = 1;
464 } END_FOR_EACH_SM_SAFE(sm);
465 free:
466 free_string(left_name);
467 free_string(right_name);
468 return ret;
471 static int handle_param_offsets(struct expression *expr)
473 struct expression *right;
474 sval_t sval;
476 right = strip_expr(expr->right);
478 if (right->type != EXPR_BINOP || right->op != '-')
479 return 0;
481 if (!get_value(right->right, &sval))
482 return 0;
484 right = get_assigned_expr(right->left);
485 if (!right)
486 return 0;
487 return copy_containter_states(expr->left, right, sval.value);
490 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
492 struct expression *call, *arg;
493 int offset;
495 if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
496 return;
497 call = strip_expr(expr->right);
498 if (call->type != EXPR_CALL)
499 return;
500 if (param != -1)
501 return;
502 param = atoi(key);
503 offset = atoi(value);
505 arg = get_argument_from_call_expr(call->args, param);
506 if (!arg)
507 return;
509 copy_containter_states(expr->left, arg, -offset);
512 void __fake_struct_member_assignments(struct expression *expr)
514 struct expression *left, *right;
515 struct symbol *type;
516 int mode;
518 if (expr->op != '=')
519 return;
521 if (is_noderef_ptr(expr->right))
522 return;
524 type = get_type(expr->left);
525 if (!type)
526 return;
527 if (type->type != SYM_PTR && type->type != SYM_STRUCT)
528 return;
530 if (handle_param_offsets(expr))
531 return;
533 left = expr->left;
534 right = expr->right;
536 if (type->type == SYM_PTR) {
537 /* Convert "p = q;" to "*p = *q;" */
538 left = add_dereference(left);
539 right = add_dereference(right);
542 if (returns_zeroed_mem(expr->right))
543 mode = COPY_ZERO;
544 else if (types_equiv(get_type(left), get_type(right)))
545 mode = COPY_NORMAL;
546 else
547 mode = COPY_UNKNOWN;
549 if (is_pointer(left)) {
550 struct expression *assign;
552 assign = assign_expression(left, '=', right);
553 split_fake_expr(assign, 0);
556 __struct_members_copy(mode, expr, left, right, split_fake_expr, NULL);
559 static void match_memset(const char *fn, struct expression *expr, void *_size_arg)
561 struct expression *buf;
562 struct expression *val;
563 int mode;
565 buf = get_argument_from_call_expr(expr->args, 0);
566 val = get_argument_from_call_expr(expr->args, 1);
568 buf = strip_expr(buf);
569 if (expr_is_zero(val))
570 mode = COPY_ZERO;
571 else
572 mode = COPY_UNKNOWN;
573 __struct_members_copy(mode, expr, add_dereference(buf), NULL, split_fake_expr, NULL);
576 static void match_memcpy(const char *fn, struct expression *expr, void *_arg)
578 struct expression *dest;
579 struct expression *src;
580 int mode;
582 dest = get_argument_from_call_expr(expr->args, 0);
583 src = get_argument_from_call_expr(expr->args, 1);
585 if (types_equiv(get_type(src), get_type(dest)))
586 mode = COPY_NORMAL;
587 else
588 mode = COPY_UNKNOWN;
590 __struct_members_copy(mode, expr, add_dereference(dest), add_dereference(src), split_fake_expr, NULL);
593 static void match_memdup(const char *fn, struct expression *call_expr,
594 struct expression *expr, void *_unused)
596 struct expression *left, *right, *arg;
597 int mode;
599 if (!expr || expr->type != EXPR_ASSIGNMENT)
600 return;
602 left = strip_expr(expr->left);
603 right = strip_expr(expr->right);
605 if (right->type != EXPR_CALL)
606 return;
607 arg = get_argument_from_call_expr(right->args, 0);
609 if (types_equiv(get_type(left), get_type(right)))
610 mode = COPY_NORMAL;
611 else
612 mode = COPY_UNKNOWN;
614 __struct_members_copy(mode, expr, add_dereference(left), add_dereference(arg), split_fake_expr, NULL);
617 static void match_memcpy_unknown(const char *fn, struct expression *expr, void *_arg)
619 struct expression *dest;
621 dest = get_argument_from_call_expr(expr->args, 0);
622 __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(dest), NULL, split_fake_expr, NULL);
625 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
627 struct expression *arg;
628 int i;
630 i = -1;
631 FOR_EACH_PTR(expr->args, arg) {
632 if (++i < 2)
633 continue;
634 __struct_members_copy(COPY_UNKNOWN, expr, add_dereference(arg), NULL, split_fake_expr, NULL);
635 } END_FOR_EACH_PTR(arg);
638 static void unop_expr(struct expression *expr)
640 if (expr->op != SPECIAL_INCREMENT &&
641 expr->op != SPECIAL_DECREMENT)
642 return;
644 if (!is_pointer(expr))
645 return;
646 faked_expression = expr;
647 __struct_members_copy(COPY_UNKNOWN, expr, expr->unop, NULL, split_fake_expr, NULL);
648 faked_expression = NULL;
651 static void register_clears_param(void)
653 struct token *token;
654 char name[256];
655 const char *function;
656 int param;
658 if (option_project == PROJ_NONE)
659 return;
661 snprintf(name, 256, "%s.clears_argument", option_project_str);
663 token = get_tokens_file(name);
664 if (!token)
665 return;
666 if (token_type(token) != TOKEN_STREAMBEGIN)
667 return;
668 token = token->next;
669 while (token_type(token) != TOKEN_STREAMEND) {
670 if (token_type(token) != TOKEN_IDENT)
671 return;
672 function = show_ident(token->ident);
673 token = token->next;
674 if (token_type(token) != TOKEN_NUMBER)
675 return;
676 param = atoi(token->number);
677 add_function_hook(function, &match_memcpy_unknown, INT_PTR(param));
678 token = token->next;
680 clear_token_alloc();
683 void create_recursive_fake_assignments(struct expression *expr,
684 void (*assign_handler)(struct expression *expr, void *data),
685 void *data)
687 __struct_members_copy(COPY_UNKNOWN, expr, expr, NULL, assign_handler, data);
690 static void db_buf_cleared(struct expression *expr, int param, char *key, char *value)
692 struct expression *arg;
694 arg = gen_expr_from_param_key(expr, param, key);
695 if (!arg)
696 return;
698 __in_buf_clear++;
699 if (strcmp(value, "0") == 0)
700 __struct_members_copy(COPY_ZERO, expr, arg, NULL, split_fake_expr, NULL);
701 else
702 __struct_members_copy(COPY_UNKNOWN, expr, arg, NULL, split_fake_expr, NULL);
703 __in_buf_clear--;
706 void register_struct_assignment(int id)
708 my_id = id;
710 add_function_data((unsigned long *)&faked_expression);
712 add_function_hook("memset", &match_memset, NULL);
713 add_function_hook("__memset", &match_memset, NULL);
714 add_function_hook("__builtin_memset", &match_memset, NULL);
716 add_function_hook("memcpy", &match_memcpy, INT_PTR(0));
717 add_function_hook("memmove", &match_memcpy, INT_PTR(0));
718 add_function_hook("__memcpy", &match_memcpy, INT_PTR(0));
719 add_function_hook("__memmove", &match_memcpy, INT_PTR(0));
720 add_function_hook("__builtin_memcpy", &match_memcpy, INT_PTR(0));
721 add_function_hook("__builtin_memmove", &match_memcpy, INT_PTR(0));
723 if (option_project == PROJ_KERNEL) {
724 return_implies_state_sval("kmemdup", valid_ptr_min_sval, valid_ptr_max_sval, &match_memdup, NULL);
725 add_function_hook("copy_from_user", &match_memcpy, INT_PTR(0));
726 add_function_hook("_copy_from_user", &match_memcpy, INT_PTR(0));
727 add_function_hook("memcpy_fromio", &match_memcpy, INT_PTR(0));
728 add_function_hook("__memcpy_fromio", &match_memcpy, INT_PTR(0));
731 add_function_hook("sscanf", &match_sscanf, NULL);
732 add_allocation_hook_early(&match_allocation);
734 add_hook(&unop_expr, OP_HOOK);
735 register_clears_param();
736 select_return_states_hook(BUF_CLEARED, &db_buf_cleared);
737 select_return_states_hook(BUF_ADD, &db_buf_cleared);
739 select_return_states_hook(CONTAINER, &returns_container_of);