1/*
2 * Copyright (C) 2015 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#include "smatch.h"
19#include "smatch_slist.h"
20#include "smatch_extra.h"
21
22static int my_id;
23static int link_id;
24
25static struct smatch_state *safe_state(struct expression *expr)
26{
27	struct smatch_state *state;
28
29	state = __alloc_smatch_state(0);
30	expr = strip_expr(expr);
31	state->name = alloc_sname("safe");
32	state->data = expr;
33	return state;
34}
35
36static char *save_links(struct expression *expr, struct symbol **sym, struct var_sym_list **vsl)
37{
38	struct var_sym *vs;
39	char *name;
40
41	name = expr_to_chunk_sym_vsl(expr, sym, vsl);
42	if (!name || !*vsl) {
43		free_string(name);
44		return NULL;
45	}
46
47	FOR_EACH_PTR(*vsl, vs) {
48		store_link(link_id, vs->var, vs->sym, name, *sym);
49	} END_FOR_EACH_PTR(vs);
50
51	return name;
52}
53
54static void match_divide(struct expression *expr)
55{
56	struct expression *left, *right, *binop;
57	struct symbol *type;
58	char *name;
59	struct symbol *sym;
60	struct var_sym_list *vsl;
61	sval_t max;
62
63	if (expr->type != EXPR_COMPARE)
64		return;
65	if (expr->op != '>' && expr->op != SPECIAL_UNSIGNED_GT &&
66	    expr->op != SPECIAL_GTE && expr->op != SPECIAL_UNSIGNED_GTE)
67		return;
68
69	left = strip_parens(expr->left);
70	right = strip_parens(expr->right);
71
72	if (right->type != EXPR_BINOP || right->op != '/')
73		return;
74	if (!get_value(right->left, &max))
75		return;
76	if (max.value != INT_MAX && max.value != UINT_MAX &&
77	    max.value != LLONG_MAX && max.uvalue != ULLONG_MAX)
78		return;
79
80	type = get_type(expr);
81	if (!type)
82		return;
83	if (type_bits(type) != 32 && type_bits(type) != 64)
84		return;
85
86
87	binop = binop_expression(left, '*', right->right);
88
89	name = save_links(binop, &sym, &vsl);
90	if (!name)
91		return;
92	set_true_false_states(my_id, name, sym, NULL, safe_state(binop));
93	free_string(name);
94}
95
96static void match_overflow_to_less_than(struct expression *expr)
97{
98	struct expression *left, *right;
99	struct symbol *type;
100	char *name;
101	struct symbol *sym;
102	struct var_sym_list *vsl;
103
104	if (expr->type != EXPR_COMPARE)
105		return;
106	if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
107		return;
108
109	left = strip_parens(expr->left);
110	right = strip_parens(expr->right);
111
112	if (left->op != '+')
113		return;
114
115	type = get_type(expr);
116	if (!type)
117		return;
118	if (type_bits(type) != 32 && type_bits(type) != 64)
119		return;
120
121	if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right))
122		return;
123
124	name = save_links(left, &sym, &vsl);
125	if (!name)
126		return;
127	set_true_false_states(my_id, name, sym, NULL, safe_state(left));
128	free_string(name);
129}
130
131static void match_condition(struct expression *expr)
132{
133	match_overflow_to_less_than(expr);
134	match_divide(expr);
135}
136
137int can_integer_overflow(struct symbol *type, struct expression *expr)
138{
139	int op;
140	sval_t lmax, rmax, res;
141
142	if (!type)
143		type = &int_ctype;
144
145	expr = strip_expr(expr);
146
147	if (expr->type == EXPR_ASSIGNMENT) {
148		switch(expr->op) {
149		case SPECIAL_MUL_ASSIGN:
150			op = '*';
151			break;
152		case SPECIAL_ADD_ASSIGN:
153			op = '+';
154			break;
155		case SPECIAL_SHL_ASSIGN:
156			op = SPECIAL_LEFTSHIFT;
157			break;
158		default:
159			return 0;
160		}
161	} else if (expr->type == EXPR_BINOP) {
162		if (expr->op != '*' && expr->op != '+' && expr->op != SPECIAL_LEFTSHIFT)
163			return 0;
164		op = expr->op;
165	} else {
166		return 0;
167	}
168
169	get_absolute_max(expr->left, &lmax);
170	get_absolute_max(expr->right, &rmax);
171
172	if (sval_binop_overflows(lmax, op, rmax))
173		return 1;
174
175	res = sval_binop(lmax, op, rmax);
176	if (sval_cmp(res, sval_type_max(type)) > 0)
177		return 1;
178	return 0;
179}
180
181int can_integer_overflow_expr(struct expression *expr)
182{
183	struct symbol *type;
184	struct smatch_state *state;
185	char *name;
186	struct symbol *sym;
187	int ret = 1;
188
189	type = get_type(expr);
190	if (!type)
191		return 0;
192
193	if (!can_integer_overflow(type, expr))
194		return 0;
195
196	name = expr_to_known_chunk_sym(expr, &sym);
197	if (!name || !sym)
198		goto free;
199
200	state = get_state(my_id, name, sym);
201	if (state && state->data)
202		ret = 0;
203free:
204	free_string(name);
205	return ret;
206}
207
208static int get_arg_nr(struct expression *call, struct expression *expr)
209{
210	struct expression *arg;
211	int i;
212
213	i = -1;
214	FOR_EACH_PTR(call->args, arg) {
215		i++;
216		if (expr_equiv(arg, expr))
217			return i;
218	} END_FOR_EACH_PTR(arg);
219
220	return -1;
221}
222
223static void check_links(struct expression *call, struct expression *arg, int nr, struct sm_state *sm, void *_vsl)
224{
225	struct var_sym_list *vsl = _vsl;
226	struct var_sym *vs;
227	struct smatch_state *state;
228	struct expression *expr;
229	int left = -1;
230	int right = -1;
231
232	FOR_EACH_PTR(vsl, vs) {
233		state = get_state(my_id, vs->var, vs->sym);
234		if (!state || !state->data)
235			continue;
236
237		expr = state->data;
238
239		if (expr_equiv(arg, expr->left)) {
240			left = nr;
241			right = get_arg_nr(call, expr->right);
242		} else if (expr_equiv(arg, expr->right)) {
243			left = get_arg_nr(call, expr->left);
244			right = nr;
245		}
246
247		if (left == -1 || right == -1)
248			continue;
249
250		left = -1;
251		right = -1;
252	} END_FOR_EACH_PTR(vs);
253}
254
255static void match_call_info(struct expression *call)
256{
257	struct expression *arg;
258	struct sm_state *link;
259	struct stree *done = NULL;
260	int i;
261
262	i = -1;
263	FOR_EACH_PTR(call->args, arg) {
264		i++;
265
266		link = get_sm_state_expr(link_id, arg);
267		if (!link)
268			continue;
269
270		if (get_state_stree(done, my_id, link->state->name, NULL))
271			continue;
272//		set_state_stree(&done, my_id, link->state->name, NULL, &undefined);
273
274		check_links(call, arg, i, link, link->state->data);
275	} END_FOR_EACH_PTR(arg);
276
277	free_stree(&done);
278}
279
280void register_integer_overflow(int id)
281{
282	my_id = id;
283	set_dynamic_states(my_id);
284	add_hook(&match_condition, CONDITION_HOOK);
285	add_hook(&match_call_info, FUNCTION_CALL_HOOK);
286}
287
288void register_integer_overflow_links(int id)
289{
290	link_id = id;
291	set_up_link_functions(my_id, link_id);
292}
293