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