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
63enum {
64	COPY_NORMAL,
65	COPY_MEMCPY,
66	COPY_MEMSET,
67};
68
69static 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
88static 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
113static 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
132static struct expression *faked_expression;
133struct expression *get_faked_expression(void)
134{
135	if (!__in_fake_assign)
136		return NULL;
137	return faked_expression;
138}
139
140static 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
149static 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
180static 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
230static 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
306done:
307	faked_expression = NULL;
308}
309
310static 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
326static 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);
359free:
360	free_string(left_name);
361	free_string(right_name);
362	return ret;
363}
364
365static 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
384static 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
406void __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
431static 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
443static 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
454static 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
471static 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
479static 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
492static 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
505static 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
537static 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
564void 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