xref: /illumos-gate/usr/src/tools/smatch/src/smatch_struct_assignment.c (revision 6523a3aa7f325d64841382707603be7a86e68147)
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  * I don't have a proper solution for this problem right now.  I just copy one
49  * level and don't nest.  It should handle limitted nesting but intelligently.
50  *
51  * The other thing is that you end up with a lot of garbage assignments where
52  * we record "x could be anything. x->y could be anything. x->y->z->a->b->c
53  * could *also* be anything!".  There should be a better way to filter this
54  * useless information.
55  *
56  */
57 
58 #include "scope.h"
59 #include "smatch.h"
60 #include "smatch_slist.h"
61 #include "smatch_extra.h"
62 
63 enum {
64 	COPY_NORMAL,
65 	COPY_MEMCPY,
66 	COPY_MEMSET,
67 };
68 
get_struct_type(struct expression * expr)69 static struct symbol *get_struct_type(struct expression *expr)
70 {
71 	struct symbol *type;
72 
73 	type = get_type(expr);
74 	if (!type)
75 		return NULL;
76 	if (type->type == SYM_PTR) {
77 		type = get_real_base_type(type);
78 		if (!type)
79 			return NULL;
80 	}
81 	if (type->type == SYM_STRUCT)
82 		return type;
83 	if (type->type == SYM_UNION)
84 		return type;
85 	return NULL;
86 }
87 
get_right_base_expr(struct symbol * left_type,struct expression * right)88 static struct expression *get_right_base_expr(struct symbol *left_type, struct expression *right)
89 {
90 	struct symbol *struct_type;
91 
92 	if (!right)
93 		return NULL;
94 
95 	struct_type = get_struct_type(right);
96 	if (!struct_type)
97 		return NULL;
98 	if (struct_type != left_type)
99 		return NULL;
100 
101 	if (right->type == EXPR_PREOP && right->op == '&')
102 		right = strip_expr(right->unop);
103 
104 	if (right->type == EXPR_CALL)
105 		return NULL;
106 
107 	if (is_pointer(right))
108 		right = deref_expression(right);
109 
110 	return right;
111 }
112 
remove_addr(struct expression * expr)113 static struct expression *remove_addr(struct expression *expr)
114 {
115 	struct symbol *type;
116 
117 	expr = strip_expr(expr);
118 	if (!expr)
119 		return NULL;
120 
121 	if (expr->type == EXPR_PREOP && expr->op == '&')
122 		return strip_expr(expr->unop);
123 	type = get_type(expr);
124 	if (!type)
125 		return expr;
126 	if (type->type != SYM_PTR && type->type != SYM_ARRAY)
127 		return expr;
128 
129 	return deref_expression(expr);
130 }
131 
132 static struct expression *faked_expression;
get_faked_expression(void)133 struct expression *get_faked_expression(void)
134 {
135 	if (!__in_fake_assign)
136 		return NULL;
137 	return faked_expression;
138 }
139 
split_fake_expr(struct expression * expr)140 static void split_fake_expr(struct expression *expr)
141 {
142 	__in_fake_assign++;
143 	__in_fake_struct_assign++;
144 	__split_expr(expr);
145 	__in_fake_struct_assign--;
146 	__in_fake_assign--;
147 }
148 
handle_non_struct_assignments(struct expression * left,struct expression * right)149 static void handle_non_struct_assignments(struct expression *left, struct expression *right)
150 {
151 	struct symbol *type;
152 	struct expression *assign;
153 
154 	while (right && right->type == EXPR_ASSIGNMENT)
155 		right = strip_parens(right->left);
156 
157 	type = get_type(left);
158 	if (!type)
159 		return;
160 	if (type->type == SYM_PTR) {
161 		left = deref_expression(left);
162 		if (right)
163 			right = deref_expression(right);
164 		else
165 			right = unknown_value_expression(left);
166 		assign = assign_expression(left, '=', right);
167 		split_fake_expr(assign);
168 		return;
169 	}
170 	if (type->type != SYM_BASETYPE)
171 		return;
172 	right = strip_expr(right);
173 	type = get_type(right);
174 	if (!right || !type || type->type == SYM_ARRAY)
175 		right = unknown_value_expression(left);
176 	assign = assign_expression(left, '=', right);
177 	split_fake_expr(assign);
178 }
179 
set_inner_struct_members(int mode,struct expression * faked,struct expression * left,struct expression * right,struct symbol * member)180 static void set_inner_struct_members(int mode, struct expression *faked, struct expression *left, struct expression *right, struct symbol *member)
181 {
182 	struct expression *left_member;
183 	struct expression *right_member = NULL;  /* silence GCC */
184 	struct expression *assign;
185 	struct symbol *base = get_real_base_type(member);
186 	struct symbol *tmp;
187 
188 	if (member->ident) {
189 		left = member_expression(left, '.', member->ident);
190 		if (mode != COPY_MEMSET && right)
191 			right = member_expression(right, '.', member->ident);
192 	}
193 
194 	FOR_EACH_PTR(base->symbol_list, tmp) {
195 		struct symbol *type;
196 
197 		type = get_real_base_type(tmp);
198 		if (!type)
199 			continue;
200 
201 		if (type->type == SYM_ARRAY)
202 			continue;
203 		if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
204 			set_inner_struct_members(mode, faked, left, right, tmp);
205 			continue;
206 		}
207 		if (!tmp->ident)
208 			continue;
209 
210 		left_member = member_expression(left, '.', tmp->ident);
211 
212 		switch (mode) {
213 		case COPY_NORMAL:
214 		case COPY_MEMCPY:
215 			if (right)
216 				right_member = member_expression(right, '.', tmp->ident);
217 			else
218 				right_member = unknown_value_expression(left_member);
219 			break;
220 		case COPY_MEMSET:
221 			right_member = right;
222 			break;
223 		}
224 
225 		assign = assign_expression(left_member, '=', right_member);
226 		split_fake_expr(assign);
227 	} END_FOR_EACH_PTR(tmp);
228 }
229 
__struct_members_copy(int mode,struct expression * faked,struct expression * left,struct expression * right)230 static void __struct_members_copy(int mode, struct expression *faked,
231 				  struct expression *left,
232 				  struct expression *right)
233 {
234 	struct symbol *struct_type, *tmp, *type;
235 	struct expression *left_member;
236 	struct expression *right_member;
237 	struct expression *assign;
238 	int op = '.';
239 
240 	if (__in_fake_assign)
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 (is_pointer(left)) {
262 		left = deref_expression(left);
263 		op = '*';
264 	}
265 	if (mode != COPY_MEMSET)
266 		right = get_right_base_expr(struct_type, right);
267 
268 	FOR_EACH_PTR(struct_type->symbol_list, tmp) {
269 		type = get_real_base_type(tmp);
270 		if (!type)
271 			continue;
272 		if (type->type == SYM_ARRAY)
273 			continue;
274 
275 		if (type->type == SYM_UNION || type->type == SYM_STRUCT) {
276 			set_inner_struct_members(mode, faked, left, right, tmp);
277 			continue;
278 		}
279 
280 		if (!tmp->ident)
281 			continue;
282 
283 		left_member = member_expression(left, op, tmp->ident);
284 		right_member = NULL;
285 
286 		switch (mode) {
287 		case COPY_NORMAL:
288 		case COPY_MEMCPY:
289 			if (right)
290 				right_member = member_expression(right, op, tmp->ident);
291 			else
292 				right_member = unknown_value_expression(left_member);
293 			break;
294 		case COPY_MEMSET:
295 			right_member = right;
296 			break;
297 		}
298 		if (!right_member) {
299 			sm_perror("No right member");
300 			continue;
301 		}
302 		assign = assign_expression(left_member, '=', right_member);
303 		split_fake_expr(assign);
304 	} END_FOR_EACH_PTR(tmp);
305 
306 done:
307 	faked_expression = NULL;
308 }
309 
returns_zeroed_mem(struct expression * expr)310 static int returns_zeroed_mem(struct expression *expr)
311 {
312 	char *fn;
313 
314 	if (expr->type != EXPR_CALL || expr->fn->type != EXPR_SYMBOL)
315 		return 0;
316 	fn = expr_to_var(expr->fn);
317 	if (!fn)
318 		return 0;
319 	if (strcmp(fn, "kcalloc") == 0)
320 		return 1;
321 	if (option_project == PROJ_KERNEL && strstr(fn, "zalloc"))
322 		return 1;
323 	return 0;
324 }
325 
copy_containter_states(struct expression * left,struct expression * right,int offset)326 static int copy_containter_states(struct expression *left, struct expression *right, int offset)
327 {
328 	char *left_name = NULL, *right_name = NULL;
329 	struct symbol *left_sym, *right_sym;
330 	struct sm_state *sm, *new_sm;
331 	int ret = 0;
332 	int len;
333 	char buf[64];
334 	char new_name[128];
335 
336 	right_name = expr_to_var_sym(right, &right_sym);
337 	if (!right_name || !right_sym)
338 		goto free;
339 	left_name = expr_to_var_sym(left, &left_sym);
340 	if (!left_name || !left_sym)
341 		goto free;
342 
343 	len = snprintf(buf, sizeof(buf), "%s(-%d)", right_name, offset);
344 	if (len >= sizeof(buf))
345 		goto free;
346 
347 	FOR_EACH_SM(__get_cur_stree(), sm) {
348 		if (sm->sym != right_sym)
349 			continue;
350 		if (strncmp(sm->name, buf, len) != 0)
351 			continue;
352 		snprintf(new_name, sizeof(new_name), "%s%s", left_name, sm->name + len);
353 		new_sm = clone_sm(sm);
354 		new_sm->name = alloc_sname(new_name);
355 		new_sm->sym = left_sym;
356 		__set_sm(new_sm);
357 		ret = 1;
358 	} END_FOR_EACH_SM(sm);
359 free:
360 	free_string(left_name);
361 	free_string(right_name);
362 	return ret;
363 }
364 
handle_param_offsets(struct expression * expr)365 static int handle_param_offsets(struct expression *expr)
366 {
367 	struct expression *right;
368 	sval_t sval;
369 
370 	right = strip_expr(expr->right);
371 
372 	if (right->type != EXPR_BINOP || right->op != '-')
373 		return 0;
374 
375 	if (!get_value(right->right, &sval))
376 		return 0;
377 
378 	right = get_assigned_expr(right->left);
379 	if (!right)
380 		return 0;
381 	return copy_containter_states(expr->left, right, sval.value);
382 }
383 
returns_container_of(struct expression * expr,int param,char * key,char * value)384 static void returns_container_of(struct expression *expr, int param, char *key, char *value)
385 {
386 	struct expression *call, *arg;
387 	int offset;
388 
389 	if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
390 		return;
391 	call = strip_expr(expr->right);
392 	if (call->type != EXPR_CALL)
393 		return;
394 	if (param != -1)
395 		return;
396 	param = atoi(key);
397 	offset = atoi(value);
398 
399 	arg = get_argument_from_call_expr(call->args, param);
400 	if (!arg)
401 		return;
402 
403 	copy_containter_states(expr->left, arg, -offset);
404 }
405 
__fake_struct_member_assignments(struct expression * expr)406 void __fake_struct_member_assignments(struct expression *expr)
407 {
408 	struct symbol *left_type;
409 
410 	if (expr->op != '=')
411 		return;
412 
413 	if (expr_is_zero(expr->right))
414 		return;
415 
416 	left_type = get_type(expr->left);
417 	if (!left_type ||
418 	    (left_type->type != SYM_PTR &&
419 	     left_type->type != SYM_STRUCT))
420 		return;
421 
422 	if (handle_param_offsets(expr))
423 		return;
424 
425 	if (returns_zeroed_mem(expr->right))
426 		__struct_members_copy(COPY_MEMSET, expr, expr->left, zero_expr());
427 	else
428 		__struct_members_copy(COPY_NORMAL, expr, expr->left, expr->right);
429 }
430 
match_memset(const char * fn,struct expression * expr,void * _size_arg)431 static void match_memset(const char *fn, struct expression *expr, void *_size_arg)
432 {
433 	struct expression *buf;
434 	struct expression *val;
435 
436 	buf = get_argument_from_call_expr(expr->args, 0);
437 	val = get_argument_from_call_expr(expr->args, 1);
438 
439 	buf = strip_expr(buf);
440 	__struct_members_copy(COPY_MEMSET, expr, remove_addr(buf), val);
441 }
442 
match_memcpy(const char * fn,struct expression * expr,void * _arg)443 static void match_memcpy(const char *fn, struct expression *expr, void *_arg)
444 {
445 	struct expression *dest;
446 	struct expression *src;
447 
448 	dest = get_argument_from_call_expr(expr->args, 0);
449 	src = get_argument_from_call_expr(expr->args, 1);
450 
451 	__struct_members_copy(COPY_MEMCPY, expr, remove_addr(dest), remove_addr(src));
452 }
453 
match_memdup(const char * fn,struct expression * call_expr,struct expression * expr,void * _unused)454 static void match_memdup(const char *fn, struct expression *call_expr,
455 			struct expression *expr, void *_unused)
456 {
457 	struct expression *left, *right, *arg;
458 
459 	if (!expr || expr->type != EXPR_ASSIGNMENT)
460 		return;
461 
462 	left = strip_expr(expr->left);
463 	right = strip_expr(expr->right);
464 
465 	if (right->type != EXPR_CALL)
466 		return;
467 	arg = get_argument_from_call_expr(right->args, 0);
468 	__struct_members_copy(COPY_MEMCPY, expr, left, arg);
469 }
470 
match_memcpy_unknown(const char * fn,struct expression * expr,void * _arg)471 static void match_memcpy_unknown(const char *fn, struct expression *expr, void *_arg)
472 {
473 	struct expression *dest;
474 
475 	dest = get_argument_from_call_expr(expr->args, 0);
476 	__struct_members_copy(COPY_MEMCPY, expr, remove_addr(dest), NULL);
477 }
478 
match_sscanf(const char * fn,struct expression * expr,void * unused)479 static void match_sscanf(const char *fn, struct expression *expr, void *unused)
480 {
481 	struct expression *arg;
482 	int i;
483 
484 	i = -1;
485 	FOR_EACH_PTR(expr->args, arg) {
486 		if (++i < 2)
487 			continue;
488 		__struct_members_copy(COPY_MEMCPY, expr, remove_addr(arg), NULL);
489 	} END_FOR_EACH_PTR(arg);
490 }
491 
unop_expr(struct expression * expr)492 static void unop_expr(struct expression *expr)
493 {
494 	if (expr->op != SPECIAL_INCREMENT &&
495 	    expr->op != SPECIAL_DECREMENT)
496 		return;
497 
498 	if (!is_pointer(expr))
499 		return;
500 	faked_expression = expr;
501 	__struct_members_copy(COPY_MEMCPY, expr, expr->unop, NULL);
502 	faked_expression = NULL;
503 }
504 
register_clears_param(void)505 static void register_clears_param(void)
506 {
507 	struct token *token;
508 	char name[256];
509 	const char *function;
510 	int param;
511 
512 	if (option_project == PROJ_NONE)
513 		return;
514 
515 	snprintf(name, 256, "%s.clears_argument", option_project_str);
516 
517 	token = get_tokens_file(name);
518 	if (!token)
519 		return;
520 	if (token_type(token) != TOKEN_STREAMBEGIN)
521 		return;
522 	token = token->next;
523 	while (token_type(token) != TOKEN_STREAMEND) {
524 		if (token_type(token) != TOKEN_IDENT)
525 			return;
526 		function = show_ident(token->ident);
527 		token = token->next;
528 		if (token_type(token) != TOKEN_NUMBER)
529 			return;
530 		param = atoi(token->number);
531 		add_function_hook(function, &match_memcpy_unknown, INT_PTR(param));
532 		token = token->next;
533 	}
534 	clear_token_alloc();
535 }
536 
db_param_cleared(struct expression * expr,int param,char * key,char * value)537 static void db_param_cleared(struct expression *expr, int param, char *key, char *value)
538 {
539 	struct expression *arg;
540 
541 	while (expr->type == EXPR_ASSIGNMENT)
542 		expr = strip_expr(expr->right);
543 	if (expr->type != EXPR_CALL)
544 		return;
545 
546 	/*
547 	 * FIXME:  __struct_members_copy() requires an expression but
548 	 * get_variable_from_key() returns a name/sym pair so that doesn't
549 	 * work here.
550 	 */
551 	if (strcmp(key, "$") != 0)
552 		return;
553 
554 	arg = get_argument_from_call_expr(expr->args, param);
555 	if (!arg)
556 		return;
557 
558 	if (strcmp(value, "0") == 0)
559 		__struct_members_copy(COPY_MEMSET, expr, remove_addr(arg), zero_expr());
560 	else
561 		__struct_members_copy(COPY_MEMCPY, expr, remove_addr(arg), NULL);
562 }
563 
register_struct_assignment(int id)564 void register_struct_assignment(int id)
565 {
566 	add_function_hook("memset", &match_memset, NULL);
567 	add_function_hook("__memset", &match_memset, NULL);
568 
569 	add_function_hook("memcpy", &match_memcpy, INT_PTR(0));
570 	add_function_hook("memmove", &match_memcpy, INT_PTR(0));
571 	add_function_hook("__memcpy", &match_memcpy, INT_PTR(0));
572 	add_function_hook("__memmove", &match_memcpy, INT_PTR(0));
573 
574 	if (option_project == PROJ_KERNEL)
575 		return_implies_state_sval("kmemdup", valid_ptr_min_sval, valid_ptr_max_sval, &match_memdup, NULL);
576 
577 	add_function_hook("sscanf", &match_sscanf, NULL);
578 
579 	add_hook(&unop_expr, OP_HOOK);
580 	register_clears_param();
581 	select_return_states_hook(PARAM_CLEARED, &db_param_cleared);
582 
583 	select_return_states_hook(CONTAINER, &returns_container_of);
584 }
585