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;
25 * That's equivalent to saying:
30 * Turning an assignment like that into a bunch of small fake assignments is
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:
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
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.
63 #include "smatch_slist.h"
64 #include "smatch_extra.h"
74 static struct symbol
*get_struct_type(struct expression
*expr
)
78 type
= get_type(expr
);
81 if (type
->type
== SYM_PTR
) {
82 type
= get_real_base_type(type
);
86 if (type
->type
== SYM_STRUCT
)
88 if (type
->type
== SYM_UNION
)
93 static struct expression
*get_right_base_expr(struct symbol
*left_type
, struct expression
*right
)
95 struct symbol
*struct_type
;
100 struct_type
= get_struct_type(right
);
103 if (struct_type
!= left_type
)
106 if (right
->type
== EXPR_PREOP
&& right
->op
== '&')
107 right
= strip_expr(right
->unop
);
109 if (right
->type
== EXPR_CALL
)
115 static struct expression
*add_dereference(struct expression
*expr
)
120 * We want to re-write "memcpy(foo, bar, sizeof(*foo));" as
124 expr
= strip_expr(expr
);
128 if (expr
->type
== EXPR_PREOP
&& expr
->op
== '&')
129 return strip_expr(expr
->unop
);
130 type
= get_type(expr
);
133 if (type
->type
!= SYM_PTR
&& type
->type
!= SYM_ARRAY
)
136 return deref_expression(expr
);
139 static struct expression
*faked_expression
;
140 struct expression
*get_faked_expression(void)
142 if (!__in_fake_assign
)
144 return faked_expression
;
147 static void split_fake_expr(struct expression
*expr
, void *unused
)
150 __in_fake_struct_assign
++;
152 __in_fake_struct_assign
--;
156 static void handle_non_struct_assignments(struct expression
*left
, struct expression
*right
,
157 void (*assign_handler
)(struct expression
*expr
, 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
);
167 right
= unknown_value_expression(left
);
169 left_type
= get_type(left
);
170 right_type
= get_type(right
);
171 if (!left_type
|| !right_type
)
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
);
183 if (left_type
->type
!= SYM_BASETYPE
)
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
;
200 if (mode
== COPY_ZERO
)
203 left_name
= expr_to_str_sym(left
, &left_sym
);
204 if (left_name
&& !strstr(left_name
, "->"))
207 left_len
= strlen(left_name
);
210 FOR_EACH_SM(left_care
, sm
) {
211 len
= strlen(sm
->name
);
212 if (left_name
&& left_sym
== sm
->sym
&&
214 strncmp(sm
->name
, left_name
, len
)) {
218 } END_FOR_EACH_SM(sm
);
220 right_name
= expr_to_str_sym(right
, &right_sym
);
222 right_len
= strlen(right_name
);
223 if (!right_sym
|| left_sym
== right_sym
)
226 FOR_EACH_SM(right_care
, sm
) {
227 len
= strlen(sm
->name
);
228 if (right_name
&& right_sym
== sm
->sym
&&
230 strncmp(sm
->name
, right_name
, len
)) {
234 } END_FOR_EACH_SM(sm
);
237 free_string(left_name
);
238 free_string(right_name
);
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
),
248 struct expression
*left_member
;
249 struct expression
*right_expr
;
250 struct expression
*assign
;
251 struct symbol
*base
= get_real_base_type(member
);
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
))
263 FOR_EACH_PTR(base
->symbol_list
, tmp
) {
266 type
= get_real_base_type(tmp
);
270 if (type
->type
== SYM_ARRAY
)
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
);
279 left_member
= member_expression(left
, '.', tmp
->ident
);
282 if (mode
== COPY_NORMAL
&& right
)
283 right_expr
= member_expression(right
, '.', tmp
->ident
);
284 if (mode
== COPY_ZERO
)
285 right_expr
= zero_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
;
303 left_sym
= expr_to_sym(left
);
304 right_sym
= expr_to_sym(right
);
306 FOR_EACH_SM(__get_cur_stree(), sm
) {
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
)
316 FOR_EACH_SM(__get_cur_stree(), sm
) {
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
),
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
)
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
);
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
355 handle_non_struct_assignments(left
, right
, assign_handler
, data
);
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
);
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
);
379 left_member
= member_expression(left
, '.', tmp
->ident
);
382 if (mode
== COPY_NORMAL
&& right
)
383 right_expr
= member_expression(right
, '.', tmp
->ident
);
384 if (mode
== COPY_ZERO
)
385 right_expr
= zero_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
);
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
)
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
);
421 if (expr
->type
!= EXPR_CALL
|| expr
->fn
->type
!= EXPR_SYMBOL
)
424 if (is_fake_call(expr
)) {
425 tmp
= get_faked_expression();
426 if (!tmp
|| tmp
->type
!= EXPR_ASSIGNMENT
|| tmp
->op
!= '=')
429 if (expr
->type
!= EXPR_CALL
|| expr
->fn
->type
!= EXPR_SYMBOL
)
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
;
446 right_name
= expr_to_var_sym(right
, &right_sym
);
447 if (!right_name
|| !right_sym
)
449 left_name
= expr_to_var_sym(left
, &left_sym
);
450 if (!left_name
|| !left_sym
)
453 len
= snprintf(buf
, sizeof(buf
), "%s(-%d)", right_name
, offset
);
454 if (len
>= sizeof(buf
))
457 FOR_EACH_SM_SAFE(__get_cur_stree(), sm
) {
458 if (sm
->sym
!= right_sym
)
460 if (strncmp(sm
->name
, buf
, len
) != 0)
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
;
468 } END_FOR_EACH_SM_SAFE(sm
);
470 free_string(left_name
);
471 free_string(right_name
);
475 static int handle_param_offsets(struct expression
*expr
)
477 struct expression
*right
;
480 right
= strip_expr(expr
->right
);
482 if (right
->type
!= EXPR_BINOP
|| right
->op
!= '-')
485 if (!get_value(right
->right
, &sval
))
488 right
= get_assigned_expr(right
->left
);
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
;
499 if (expr
->type
!= EXPR_ASSIGNMENT
|| expr
->op
!= '=')
501 call
= strip_expr(expr
->right
);
502 if (call
->type
!= EXPR_CALL
)
507 offset
= atoi(value
);
509 arg
= get_argument_from_call_expr(call
->args
, param
);
513 copy_containter_states(expr
->left
, arg
, -offset
);
516 void __fake_struct_member_assignments(struct expression
*expr
)
518 struct expression
*left
, *right
;
525 if (is_noderef_ptr(expr
->right
))
528 type
= get_type(expr
->left
);
531 if (type
->type
!= SYM_PTR
&& type
->type
!= SYM_STRUCT
)
534 if (handle_param_offsets(expr
))
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
))
548 else if (types_equiv(get_type(left
), get_type(right
)))
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
;
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
))
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
;
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
)))
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
;
603 if (!expr
|| expr
->type
!= EXPR_ASSIGNMENT
)
606 left
= strip_expr(expr
->left
);
607 right
= strip_expr(expr
->right
);
609 if (right
->type
!= EXPR_CALL
)
611 arg
= get_argument_from_call_expr(right
->args
, 0);
613 if (types_equiv(get_type(left
), get_type(right
)))
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
;
635 FOR_EACH_PTR(expr
->args
, arg
) {
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
)
648 if (!is_pointer(expr
))
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)
659 const char *function
;
662 if (option_project
== PROJ_NONE
)
665 snprintf(name
, 256, "%s.clears_argument", option_project_str
);
667 token
= get_tokens_file(name
);
670 if (token_type(token
) != TOKEN_STREAMBEGIN
)
673 while (token_type(token
) != TOKEN_STREAMEND
) {
674 if (token_type(token
) != TOKEN_IDENT
)
676 function
= show_ident(token
->ident
);
678 if (token_type(token
) != TOKEN_NUMBER
)
680 param
= atoi(token
->number
);
681 add_function_hook(function
, &match_memcpy_unknown
, INT_PTR(param
));
687 void create_recursive_fake_assignments(struct expression
*expr
,
688 void (*assign_handler
)(struct expression
*expr
, 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
);
703 if (strcmp(value
, "0") == 0)
704 __struct_members_copy(COPY_ZERO
, expr
, arg
, NULL
, split_fake_expr
, NULL
);
706 __struct_members_copy(COPY_UNKNOWN
, expr
, arg
, NULL
, split_fake_expr
, NULL
);
710 void register_struct_assignment(int 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
);