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/*
19 * This is to track when variables are masked away.
20 *
21 */
22
23#include "smatch.h"
24#include "smatch_extra.h"
25#include "smatch_slist.h"
26
27static int my_id;
28
29static const struct bit_info unknown_bit_info = {
30	.possible = -1ULL,
31};
32
33ALLOCATOR(bit_info, "bit data");
34static struct bit_info *alloc_bit_info(unsigned long long set, unsigned long long possible)
35{
36	struct bit_info *bit_info = __alloc_bit_info(0);
37
38	bit_info->set = set;
39	bit_info->possible = possible;
40
41	return bit_info;
42}
43
44static struct smatch_state *alloc_bstate(unsigned long long set, unsigned long long possible)
45{
46	struct smatch_state *state;
47	char buf[64];
48
49	state = __alloc_smatch_state(0);
50	snprintf(buf, sizeof(buf), "0x%llx + 0x%llx", set, possible);
51	state->name = alloc_sname(buf);
52	state->data = alloc_bit_info(set, possible);
53
54	return state;
55}
56
57struct bit_info *rl_to_binfo(struct range_list *rl)
58{
59	struct bit_info *ret = __alloc_bit_info(0);
60	sval_t sval;
61
62	if (rl_to_sval(rl, &sval)) {
63		ret->set = sval.uvalue;
64		ret->possible = sval.uvalue;
65
66		return ret;
67	}
68
69	ret->set = 0;
70	ret->possible = sval_fls_mask(rl_max(rl));
71	// FIXME: what about negatives?
72
73	return ret;
74}
75
76static int is_unknown_binfo(struct symbol *type, struct bit_info *binfo)
77{
78	if (!type)
79		type = &ullong_ctype;
80
81	if (binfo->set != 0)
82		return 0;
83	if (binfo->possible < (-1ULL >> (64 - type_bits(type))))
84		return 0;
85
86	return 1;
87}
88
89static struct smatch_state *unmatched_state(struct sm_state *sm)
90{
91	struct smatch_state *estate;
92	struct symbol *type;
93	unsigned long long possible;
94	struct bit_info *p;
95
96	estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
97	if (estate_rl(estate)) {
98		p = rl_to_binfo(estate_rl(estate));
99		return alloc_bstate(p->set, p->possible);
100	}
101
102	type = estate_type(estate);
103	if (!type)
104		return alloc_bstate(0, -1ULL);
105
106	if (type_bits(type) == 64)
107		possible = -1ULL;
108	else
109		possible = (1ULL << type_bits(type)) - 1;
110
111	return alloc_bstate(0, possible);
112}
113
114static void match_modify(struct sm_state *sm, struct expression *mod_expr)
115{
116	// FIXME: we really need to store the type
117
118	set_state(my_id, sm->name, sm->sym, alloc_bstate(0, -1ULL));
119}
120
121static int binfo_equiv(struct bit_info *one, struct bit_info *two)
122{
123	if (one->set == two->set &&
124	    one->possible == two->possible)
125		return 1;
126	return 0;
127}
128
129static struct smatch_state *merge_bstates(struct smatch_state *one_state, struct smatch_state *two_state)
130{
131	struct bit_info *one, *two;
132
133	one = one_state->data;
134	two = two_state->data;
135
136	if (binfo_equiv(one, two))
137		return one_state;
138
139	return alloc_bstate(one->set & two->set, one->possible | two->possible);
140}
141
142/*
143 * The combine_bit_info() takes two bit_infos and takes creates the most
144 * accurate picture we can assuming both are true.  Or it returns unknown if
145 * the information is logically impossible.
146 *
147 * Which means that it takes the | of the ->set bits and the & of the possibly
148 * set bits, which is the opposite of what merge_bstates() does.
149 *
150 */
151static struct bit_info *combine_bit_info(struct bit_info *one, struct bit_info *two)
152{
153	struct bit_info *ret = __alloc_bit_info(0);
154
155	if ((one->set & two->possible) != one->set)
156		return alloc_bit_info(0, -1ULL);
157	if ((two->set & one->possible) != two->set)
158		return alloc_bit_info(0, -1ULL);
159
160	ret->set = one->set | two->set;
161	ret->possible = one->possible & two->possible;
162
163	return ret;
164}
165
166static struct bit_info *binfo_AND(struct bit_info *left, struct bit_info *right)
167{
168	unsigned long long set = 0;
169	unsigned long long possible = -1ULL;
170
171	if (!left && !right) {
172		/* nothing */
173	} else if (!left) {
174		possible = right->possible;
175	} else if (!right) {
176		possible = left->possible;
177	} else {
178		set = left->set & right->set;
179		possible = left->possible & right->possible;
180	}
181
182	return alloc_bit_info(set, possible);
183}
184
185static struct bit_info *binfo_OR(struct bit_info *left, struct bit_info *right)
186{
187	unsigned long long set = 0;
188	unsigned long long possible = -1ULL;
189
190	if (!left && !right) {
191		/* nothing */
192	} else if (!left) {
193		set = right->set;
194	} else if (!right) {
195		set = left->set;
196	} else {
197		set = left->set | right->set;
198		possible = left->possible | right->possible;
199	}
200
201	return alloc_bit_info(set, possible);
202}
203
204struct bit_info *get_bit_info(struct expression *expr)
205{
206	struct range_list *rl;
207	struct smatch_state *bstate;
208	struct bit_info tmp;
209	struct bit_info *extra_info;
210	struct bit_info *bit_info;
211	sval_t known;
212
213	expr = strip_parens(expr);
214
215	if (get_implied_value(expr, &known))
216		return alloc_bit_info(known.value, known.value);
217
218	if (expr->type == EXPR_BINOP) {
219		if (expr->op == '&')
220			return binfo_AND(get_bit_info(expr->left),
221					 get_bit_info(expr->right));
222		if (expr->op == '|')
223			return binfo_OR(get_bit_info(expr->left),
224					get_bit_info(expr->right));
225	}
226
227	if (get_implied_rl(expr, &rl))
228		extra_info = rl_to_binfo(rl);
229	else {
230		struct symbol *type;
231
232		tmp = unknown_bit_info;
233		extra_info = &tmp;
234
235		type = get_type(expr);
236		if (!type)
237			type = &ullong_ctype;
238		if (type_bits(type) == 64)
239			extra_info->possible = -1ULL;
240		else
241			extra_info->possible = (1ULL << type_bits(type)) - 1;
242	}
243
244	bstate = get_state_expr(my_id, expr);
245	if (bstate)
246		bit_info = bstate->data;
247	else
248		bit_info = (struct bit_info *)&unknown_bit_info;
249
250	return combine_bit_info(extra_info, bit_info);
251}
252
253static int is_single_bit(sval_t sval)
254{
255	int i;
256	int count = 0;
257
258	for (i = 0; i < 64; i++) {
259		if (sval.uvalue & 1ULL << i &&
260		    count++)
261			return 0;
262	}
263	if (count == 1)
264		return 1;
265	return 0;
266}
267
268static void match_compare(struct expression *expr)
269{
270	sval_t val;
271
272	if (expr->type != EXPR_COMPARE)
273		return;
274	if (expr->op != SPECIAL_EQUAL &&
275	    expr->op != SPECIAL_NOTEQUAL)
276		return;
277
278	if (!get_implied_value(expr->right, &val))
279		return;
280
281	set_true_false_states_expr(my_id, expr->left,
282			(expr->op == SPECIAL_EQUAL) ? alloc_bstate(val.uvalue, val.uvalue) : NULL,
283			(expr->op == SPECIAL_EQUAL) ? NULL : alloc_bstate(val.uvalue, val.uvalue));
284}
285
286static bool is_loop_iterator(struct expression *expr)
287{
288	struct statement *pre_stmt, *loop_stmt;
289
290	pre_stmt = expr_get_parent_stmt(expr);
291	if (!pre_stmt || pre_stmt->type != STMT_EXPRESSION)
292		return false;
293
294	loop_stmt = stmt_get_parent_stmt(pre_stmt);
295	if (!loop_stmt || loop_stmt->type != STMT_ITERATOR)
296		return false;
297	if (loop_stmt->iterator_pre_statement != pre_stmt)
298		return false;
299
300	return true;
301}
302
303static void match_assign(struct expression *expr)
304{
305	struct bit_info *binfo;
306
307	if (expr->op != '=')
308		return;
309	if (__in_fake_assign)
310		return;
311	if (is_loop_iterator(expr))
312		return;
313
314	binfo = get_bit_info(expr->right);
315	if (!binfo)
316		return;
317	if (is_unknown_binfo(get_type(expr->left), binfo))
318		return;
319	set_state_expr(my_id, expr->left, alloc_bstate(binfo->set, binfo->possible));
320}
321
322static void match_condition(struct expression *expr)
323{
324	struct bit_info *orig;
325	struct bit_info true_info;
326	struct bit_info false_info;
327	sval_t right;
328
329	if (expr->type != EXPR_BINOP ||
330	    expr->op != '&')
331		return;
332
333	if (!get_value(expr->right, &right))
334		return;
335
336	orig = get_bit_info(expr->left);
337	true_info = *orig;
338	false_info = *orig;
339
340	if (right.uvalue == 0 || is_single_bit(right))
341		true_info.set &= right.uvalue;
342
343	true_info.possible &= right.uvalue;
344	false_info.possible &= ~right.uvalue;
345
346	set_true_false_states_expr(my_id, expr->left,
347				   alloc_bstate(true_info.set, true_info.possible),
348				   alloc_bstate(false_info.set, false_info.possible));
349}
350
351static void match_call_info(struct expression *expr)
352{
353	struct bit_info *binfo, *rl_binfo;
354	struct expression *arg;
355	struct range_list *rl;
356	char buf[64];
357	int i;
358
359	i = -1;
360	FOR_EACH_PTR(expr->args, arg) {
361		i++;
362		binfo = get_bit_info(arg);
363		if (!binfo)
364			continue;
365		if (is_unknown_binfo(get_type(arg), binfo))
366			continue;
367		if (get_implied_rl(arg, &rl)) {
368			rl_binfo = rl_to_binfo(rl);
369			if (binfo_equiv(rl_binfo, binfo))
370				continue;
371		}
372		// If is just non-negative continue
373		// If ->set == ->possible continue
374		snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
375		sql_insert_caller_info(expr, BIT_INFO, i, "$", buf);
376	} END_FOR_EACH_PTR(arg);
377}
378
379static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
380{
381	struct bit_info *binfo = sm->state->data;
382	struct smatch_state *estate;
383	struct bit_info *implied_binfo;
384	char buf[64];
385
386	if (!binfo)
387		return;
388
389	/* This means it can only be one value, so it's handled by smatch_extra. */
390	if (binfo->set == binfo->possible)
391		return;
392
393	estate = get_state(SMATCH_EXTRA, sm->name, sm->sym);
394	if (is_unknown_binfo(estate_type(estate), binfo))
395		return;
396
397	if (estate_rl(estate)) {
398		sval_t sval;
399
400		if (estate_get_single_value(estate, &sval))
401			return;
402
403		implied_binfo = rl_to_binfo(estate_rl(estate));
404		if (binfo_equiv(implied_binfo, binfo))
405			return;
406	}
407
408	snprintf(buf, sizeof(buf), "0x%llx,0x%llx", binfo->set, binfo->possible);
409	sql_insert_caller_info(call, BIT_INFO, param, printed_name, buf);
410}
411
412static void set_param_bits(const char *name, struct symbol *sym, char *key, char *value)
413{
414	char fullname[256];
415	unsigned long long set, possible;
416
417	if (strcmp(key, "*$") == 0)
418		snprintf(fullname, sizeof(fullname), "*%s", name);
419	else if (strncmp(key, "$", 1) == 0)
420		snprintf(fullname, 256, "%s%s", name, key + 1);
421	else
422		return;
423
424	set = strtoull(value, &value, 16);
425	if (*value != ',')
426		return;
427	value++;
428	possible = strtoull(value, &value, 16);
429
430	set_state(my_id, fullname, sym, alloc_bstate(set, possible));
431}
432
433void register_bits(int id)
434{
435	my_id = id;
436
437	set_dynamic_states(my_id);
438
439	add_unmatched_state_hook(my_id, &unmatched_state);
440	add_merge_hook(my_id, &merge_bstates);
441
442	add_hook(&match_condition, CONDITION_HOOK);
443	add_hook(&match_compare, CONDITION_HOOK);
444	add_hook(&match_assign, ASSIGNMENT_HOOK);
445	add_modification_hook(my_id, &match_modify);
446
447	add_hook(&match_call_info, FUNCTION_CALL_HOOK);
448	add_member_info_callback(my_id, struct_member_callback);
449	select_caller_info_hook(set_param_bits, BIT_INFO);
450}
451