11f5207b7SJohn Levon /*
21f5207b7SJohn Levon  * Copyright (C) 2015 Oracle.
31f5207b7SJohn Levon  *
41f5207b7SJohn Levon  * This program is free software; you can redistribute it and/or
51f5207b7SJohn Levon  * modify it under the terms of the GNU General Public License
61f5207b7SJohn Levon  * as published by the Free Software Foundation; either version 2
71f5207b7SJohn Levon  * of the License, or (at your option) any later version.
81f5207b7SJohn Levon  *
91f5207b7SJohn Levon  * This program is distributed in the hope that it will be useful,
101f5207b7SJohn Levon  * but WITHOUT ANY WARRANTY; without even the implied warranty of
111f5207b7SJohn Levon  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
121f5207b7SJohn Levon  * GNU General Public License for more details.
131f5207b7SJohn Levon  *
141f5207b7SJohn Levon  * You should have received a copy of the GNU General Public License
151f5207b7SJohn Levon  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
161f5207b7SJohn Levon  */
171f5207b7SJohn Levon 
181f5207b7SJohn Levon #include "smatch.h"
191f5207b7SJohn Levon #include "smatch_slist.h"
201f5207b7SJohn Levon #include "smatch_extra.h"
211f5207b7SJohn Levon 
is_non_null_array(struct expression * expr)221f5207b7SJohn Levon static bool is_non_null_array(struct expression *expr)
231f5207b7SJohn Levon {
241f5207b7SJohn Levon 	struct symbol *type;
251f5207b7SJohn Levon 	struct symbol *sym;
261f5207b7SJohn Levon 	struct symbol *tmp;
271f5207b7SJohn Levon 	int i;
281f5207b7SJohn Levon 
291f5207b7SJohn Levon 	type = get_type(expr);
301f5207b7SJohn Levon 	if (!type || type->type != SYM_ARRAY)
311f5207b7SJohn Levon 		return 0;
321f5207b7SJohn Levon 	if (expr->type == EXPR_SYMBOL)
331f5207b7SJohn Levon 		return 1;
341f5207b7SJohn Levon 	if (implied_not_equal(expr, 0))
351f5207b7SJohn Levon 		return 1;
361f5207b7SJohn Levon 
371f5207b7SJohn Levon 	/* verify that it's not the first member of the struct */
381f5207b7SJohn Levon 	if (expr->type != EXPR_DEREF || !expr->member)
391f5207b7SJohn Levon 		return 0;
401f5207b7SJohn Levon 	sym = expr_to_sym(expr);
411f5207b7SJohn Levon 	if (!sym)
421f5207b7SJohn Levon 		return 0;
431f5207b7SJohn Levon 	type = get_real_base_type(sym);
441f5207b7SJohn Levon 	if (!type || type->type != SYM_PTR)
451f5207b7SJohn Levon 		return 0;
461f5207b7SJohn Levon 	type = get_real_base_type(type);
471f5207b7SJohn Levon 	if (type->type != SYM_STRUCT)
481f5207b7SJohn Levon 		return 0;
491f5207b7SJohn Levon 
501f5207b7SJohn Levon 	i = 0;
511f5207b7SJohn Levon 	FOR_EACH_PTR(type->symbol_list, tmp) {
521f5207b7SJohn Levon 		i++;
531f5207b7SJohn Levon 		if (!tmp->ident)
541f5207b7SJohn Levon 			continue;
551f5207b7SJohn Levon 		if (strcmp(expr->member->name, tmp->ident->name) == 0) {
561f5207b7SJohn Levon 			if (i == 1)
571f5207b7SJohn Levon 				return 0;
581f5207b7SJohn Levon 			return 1;
591f5207b7SJohn Levon 		}
601f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
611f5207b7SJohn Levon 
621f5207b7SJohn Levon 	return 0;
631f5207b7SJohn Levon }
641f5207b7SJohn Levon 
matches_anonymous_union(struct symbol * sym,const char * member_name)65efe51d0cSJohn Levon static bool matches_anonymous_union(struct symbol *sym, const char *member_name)
66efe51d0cSJohn Levon {
67efe51d0cSJohn Levon 	struct symbol *type, *tmp;
68efe51d0cSJohn Levon 
69efe51d0cSJohn Levon 	if (sym->ident)
70efe51d0cSJohn Levon 		return false;
71efe51d0cSJohn Levon 	type = get_real_base_type(sym);
72efe51d0cSJohn Levon 	if (!type || type->type != SYM_UNION)
73efe51d0cSJohn Levon 		return false;
74efe51d0cSJohn Levon 
75efe51d0cSJohn Levon 	FOR_EACH_PTR(type->symbol_list, tmp) {
76efe51d0cSJohn Levon 		if (tmp->ident &&
77efe51d0cSJohn Levon 		    strcmp(member_name, tmp->ident->name) == 0) {
78efe51d0cSJohn Levon 			return true;
79efe51d0cSJohn Levon 		}
80efe51d0cSJohn Levon 	} END_FOR_EACH_PTR(tmp);
81efe51d0cSJohn Levon 
82efe51d0cSJohn Levon 	return false;
83efe51d0cSJohn Levon }
84efe51d0cSJohn Levon 
get_member_offset(struct symbol * type,const char * member_name)851f5207b7SJohn Levon int get_member_offset(struct symbol *type, const char *member_name)
861f5207b7SJohn Levon {
871f5207b7SJohn Levon 	struct symbol *tmp;
881f5207b7SJohn Levon 	int offset;
89efe51d0cSJohn Levon 	int bits;
901f5207b7SJohn Levon 
911f5207b7SJohn Levon 	if (!type || type->type != SYM_STRUCT)
921f5207b7SJohn Levon 		return -1;
931f5207b7SJohn Levon 
94efe51d0cSJohn Levon 	bits = 0;
951f5207b7SJohn Levon 	offset = 0;
961f5207b7SJohn Levon 	FOR_EACH_PTR(type->symbol_list, tmp) {
97efe51d0cSJohn Levon 		if (bits_to_bytes(bits + type_bits(tmp)) > tmp->ctype.alignment) {
98efe51d0cSJohn Levon 			offset += bits_to_bytes(bits);
99efe51d0cSJohn Levon 			bits = 0;
100efe51d0cSJohn Levon 		}
1011f5207b7SJohn Levon 		offset = ALIGN(offset, tmp->ctype.alignment);
1021f5207b7SJohn Levon 		if (tmp->ident &&
1031f5207b7SJohn Levon 		    strcmp(member_name, tmp->ident->name) == 0) {
1041f5207b7SJohn Levon 			return offset;
1051f5207b7SJohn Levon 		}
106efe51d0cSJohn Levon 		if (matches_anonymous_union(tmp, member_name))
107efe51d0cSJohn Levon 			return offset;
108efe51d0cSJohn Levon 		if (!(type_bits(tmp) % 8) && type_bits(tmp) / 8 == type_bytes(tmp))
109efe51d0cSJohn Levon 			offset += type_bytes(tmp);
110efe51d0cSJohn Levon 		else
111efe51d0cSJohn Levon 			bits += type_bits(tmp);
1121f5207b7SJohn Levon 	} END_FOR_EACH_PTR(tmp);
1131f5207b7SJohn Levon 	return -1;
1141f5207b7SJohn Levon }
1151f5207b7SJohn Levon 
get_member_offset_from_deref(struct expression * expr)1161f5207b7SJohn Levon int get_member_offset_from_deref(struct expression *expr)
1171f5207b7SJohn Levon {
1181f5207b7SJohn Levon 	struct symbol *type;
1191f5207b7SJohn Levon 	struct ident *member;
1201f5207b7SJohn Levon 	int offset;
1211f5207b7SJohn Levon 
122*5a0e240fSJohn Levon 	/*
123*5a0e240fSJohn Levon 	 * FIXME: This doesn't handle foo.u.bar correctly.
124*5a0e240fSJohn Levon 	 *
125*5a0e240fSJohn Levon 	 */
126*5a0e240fSJohn Levon 
1271f5207b7SJohn Levon 	if (expr->type != EXPR_DEREF)  /* hopefully, this doesn't happen */
1281f5207b7SJohn Levon 		return -1;
1291f5207b7SJohn Levon 
1301f5207b7SJohn Levon 	if (expr->member_offset >= 0)
1311f5207b7SJohn Levon 		return expr->member_offset;
1321f5207b7SJohn Levon 
1331f5207b7SJohn Levon 	member = expr->member;
1341f5207b7SJohn Levon 	if (!member)
1351f5207b7SJohn Levon 		return -1;
1361f5207b7SJohn Levon 
1371f5207b7SJohn Levon 	type = get_type(expr->deref);
138efe51d0cSJohn Levon 	if (type_is_ptr(type))
139efe51d0cSJohn Levon 		type = get_real_base_type(type);
1401f5207b7SJohn Levon 	if (!type || type->type != SYM_STRUCT)
1411f5207b7SJohn Levon 		return -1;
1421f5207b7SJohn Levon 
1431f5207b7SJohn Levon 	offset = get_member_offset(type, member->name);
1441f5207b7SJohn Levon 	if (offset >= 0)
1451f5207b7SJohn Levon 		expr->member_offset = offset;
1461f5207b7SJohn Levon 	return offset;
1471f5207b7SJohn Levon }
1481f5207b7SJohn Levon 
add_offset_to_pointer(struct range_list ** rl,int offset)1491f5207b7SJohn Levon static void add_offset_to_pointer(struct range_list **rl, int offset)
1501f5207b7SJohn Levon {
1511f5207b7SJohn Levon 	sval_t min, max, remove, sval;
1521f5207b7SJohn Levon 	struct range_list *orig = *rl;
1531f5207b7SJohn Levon 
1541f5207b7SJohn Levon 	/*
1551f5207b7SJohn Levon 	 * Ha ha.  Treating zero as a special case means I'm correct at least a
1561f5207b7SJohn Levon 	 * tiny fraction of the time.  Which is better than nothing.
1571f5207b7SJohn Levon 	 *
1581f5207b7SJohn Levon 	 */
1591f5207b7SJohn Levon 	if (offset == 0)
1601f5207b7SJohn Levon 		return;
1611f5207b7SJohn Levon 
162efe51d0cSJohn Levon 	if (is_unknown_ptr(orig))
163efe51d0cSJohn Levon 		return;
164efe51d0cSJohn Levon 
1651f5207b7SJohn Levon 	/*
1661f5207b7SJohn Levon 	 * This function doesn't necessarily work how you might expect...
1671f5207b7SJohn Levon 	 *
1681f5207b7SJohn Levon 	 * Say you have s64min-(-1),1-s64max and you add 8 then I guess what
1691f5207b7SJohn Levon 	 * we want to say is maybe something like 9-s64max.  This shows that the
1701f5207b7SJohn Levon 	 * min it could be is 9 which is potentially useful information.  But
1711f5207b7SJohn Levon 	 * if we start with (-12),5000000-57777777 and we add 8 then we'd want
1721f5207b7SJohn Levon 	 * the result to be (-4),5000008-57777777 but (-4),5000000-57777777 is
1731f5207b7SJohn Levon 	 * also probably acceptable.  If you start with s64min-s64max then the
1741f5207b7SJohn Levon 	 * result should be 8-s64max.
1751f5207b7SJohn Levon 	 *
1761f5207b7SJohn Levon 	 */
1771f5207b7SJohn Levon 
1781f5207b7SJohn Levon 	/* We do the math on void pointer type, because this isn't "&v + 16" it
1791f5207b7SJohn Levon 	 * is &v->sixteenth_byte.
1801f5207b7SJohn Levon 	 */
1811f5207b7SJohn Levon 	orig = cast_rl(&ptr_ctype, orig);
1821f5207b7SJohn Levon 	min = sval_type_min(&ptr_ctype);
1831f5207b7SJohn Levon 	min.value = offset;
1841f5207b7SJohn Levon 	max = sval_type_max(&ptr_ctype);
1851f5207b7SJohn Levon 
1861f5207b7SJohn Levon 	if (!orig || is_whole_rl(orig)) {
1871f5207b7SJohn Levon 		*rl = alloc_rl(min, max);
1881f5207b7SJohn Levon 		return;
1891f5207b7SJohn Levon 	}
1901f5207b7SJohn Levon 
1911f5207b7SJohn Levon 	/* no wrap around */
1921f5207b7SJohn Levon 	max.uvalue = rl_max(orig).uvalue;
1931f5207b7SJohn Levon 	if (max.uvalue > sval_type_max(&ptr_ctype).uvalue - offset) {
1941f5207b7SJohn Levon 		remove = sval_type_max(&ptr_ctype);
1951f5207b7SJohn Levon 		remove.uvalue -= offset;
1961f5207b7SJohn Levon 		orig = remove_range(orig, remove, max);
1971f5207b7SJohn Levon 	}
1981f5207b7SJohn Levon 
1991f5207b7SJohn Levon 	sval.type = &int_ctype;
2001f5207b7SJohn Levon 	sval.value = offset;
2011f5207b7SJohn Levon 
2021f5207b7SJohn Levon 	*rl = rl_binop(orig, '+', alloc_rl(sval, sval));
2031f5207b7SJohn Levon }
2041f5207b7SJohn Levon 
where_allocated_rl(struct symbol * sym)2051f5207b7SJohn Levon static struct range_list *where_allocated_rl(struct symbol *sym)
2061f5207b7SJohn Levon {
2071f5207b7SJohn Levon 	if (!sym)
2081f5207b7SJohn Levon 		return NULL;
2091f5207b7SJohn Levon 
210*5a0e240fSJohn Levon 	/* This should just be the mtag if it's not on the stack */
211efe51d0cSJohn Levon 	return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
2121f5207b7SJohn Levon }
2131f5207b7SJohn Levon 
handle_fn_address(struct expression * expr,struct range_list ** rl)214*5a0e240fSJohn Levon static bool handle_fn_address(struct expression *expr, struct range_list **rl)
215*5a0e240fSJohn Levon {
216*5a0e240fSJohn Levon 	struct symbol *type;
217*5a0e240fSJohn Levon 
218*5a0e240fSJohn Levon 	if (expr->type == EXPR_PREOP && expr->op == '&')
219*5a0e240fSJohn Levon 		expr = strip_expr(expr->unop);
220*5a0e240fSJohn Levon 
221*5a0e240fSJohn Levon 	if (expr->type != EXPR_SYMBOL)
222*5a0e240fSJohn Levon 		return false;
223*5a0e240fSJohn Levon 
224*5a0e240fSJohn Levon 	type = get_type(expr);
225*5a0e240fSJohn Levon 	if (!type || type->type != SYM_FN)
226*5a0e240fSJohn Levon 		return false;
227*5a0e240fSJohn Levon 
228*5a0e240fSJohn Levon 	*rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
229*5a0e240fSJohn Levon 	return true;
230*5a0e240fSJohn Levon }
231*5a0e240fSJohn Levon 
get_address_rl(struct expression * expr,struct range_list ** rl)2321f5207b7SJohn Levon int get_address_rl(struct expression *expr, struct range_list **rl)
2331f5207b7SJohn Levon {
234efe51d0cSJohn Levon 	struct expression *unop;
235efe51d0cSJohn Levon 
236*5a0e240fSJohn Levon 	/*
237*5a0e240fSJohn Levon 	 * Ugh...  This function is bad.  It doesn't work where it's supposed to
238*5a0e240fSJohn Levon 	 * and it does more than it really should.  It shouldn't handle string
239*5a0e240fSJohn Levon 	 * literals I think...
240*5a0e240fSJohn Levon 	 *
241*5a0e240fSJohn Levon 	 * There are several complications.  For arrays and functions the "&foo"
242*5a0e240fSJohn Levon 	 * "foo" are equivalent.  But the problem is that we're also passing in
243*5a0e240fSJohn Levon 	 * foo->array[] and foo->fn.
244*5a0e240fSJohn Levon 	 *
245*5a0e240fSJohn Levon 	 * Then, when we have foo->bar.baz.one.two; that needs to be handled
246*5a0e240fSJohn Levon 	 * correctly but right now, it is not.
247*5a0e240fSJohn Levon 	 *
248*5a0e240fSJohn Levon 	 */
249*5a0e240fSJohn Levon 
2501f5207b7SJohn Levon 	expr = strip_expr(expr);
2511f5207b7SJohn Levon 	if (!expr)
2521f5207b7SJohn Levon 		return 0;
2531f5207b7SJohn Levon 
254*5a0e240fSJohn Levon 	/*
255*5a0e240fSJohn Levon 	 * For functions &fn and fn are equivalent.  I don't know if this is
256*5a0e240fSJohn Levon 	 * really the right place to handle it, but let's just get it out of the
257*5a0e240fSJohn Levon 	 * way for now.
258*5a0e240fSJohn Levon 	 *
259*5a0e240fSJohn Levon 	 */
260*5a0e240fSJohn Levon 	if (handle_fn_address(expr, rl))
2611f5207b7SJohn Levon 		return 1;
2621f5207b7SJohn Levon 
263*5a0e240fSJohn Levon 	/*
264*5a0e240fSJohn Levon 	 * For arrays, &foo->array and foo->array are equivalent.
265*5a0e240fSJohn Levon 	 *
266*5a0e240fSJohn Levon 	 */
267*5a0e240fSJohn Levon 	if (expr->type == EXPR_PREOP && expr->op == '&') {
268efe51d0cSJohn Levon 		expr = strip_expr(expr->unop);
269*5a0e240fSJohn Levon 	} else {
270efe51d0cSJohn Levon 		struct symbol *type;
2711f5207b7SJohn Levon 
272efe51d0cSJohn Levon 		type = get_type(expr);
273efe51d0cSJohn Levon 		if (!type || type->type != SYM_ARRAY)
274efe51d0cSJohn Levon 			return 0;
275efe51d0cSJohn Levon 	}
276efe51d0cSJohn Levon 
277efe51d0cSJohn Levon 	if (expr->type == EXPR_SYMBOL) {
278efe51d0cSJohn Levon 		*rl = where_allocated_rl(expr->symbol);
279efe51d0cSJohn Levon 		return 1;
280efe51d0cSJohn Levon 	}
281efe51d0cSJohn Levon 
282efe51d0cSJohn Levon 	if (is_array(expr)) {
283efe51d0cSJohn Levon 		struct expression *array;
284efe51d0cSJohn Levon 		struct expression *offset_expr;
285efe51d0cSJohn Levon 		struct range_list *array_rl, *offset_rl, *bytes_rl, *res;
286efe51d0cSJohn Levon 		struct symbol *type;
287efe51d0cSJohn Levon 		sval_t bytes;
288efe51d0cSJohn Levon 
289efe51d0cSJohn Levon 		array = get_array_base(expr);
290efe51d0cSJohn Levon 		offset_expr = get_array_offset(expr);
291efe51d0cSJohn Levon 
292efe51d0cSJohn Levon 		type = get_type(array);
293efe51d0cSJohn Levon 		type = get_real_base_type(type);
294efe51d0cSJohn Levon 		bytes.type = ssize_t_ctype;
295efe51d0cSJohn Levon 		bytes.uvalue = type_bytes(type);
296efe51d0cSJohn Levon 		bytes_rl = alloc_rl(bytes, bytes);
297efe51d0cSJohn Levon 
298efe51d0cSJohn Levon 		get_absolute_rl(array, &array_rl);
299efe51d0cSJohn Levon 		get_absolute_rl(offset_expr, &offset_rl);
300efe51d0cSJohn Levon 
301efe51d0cSJohn Levon 		if (type_bytes(type)) {
302efe51d0cSJohn Levon 			res = rl_binop(offset_rl, '*', bytes_rl);
303efe51d0cSJohn Levon 			res = rl_binop(res, '+', array_rl);
304efe51d0cSJohn Levon 			*rl = res;
305efe51d0cSJohn Levon 			return true;
306efe51d0cSJohn Levon 		}
307efe51d0cSJohn Levon 
308efe51d0cSJohn Levon 		if (implied_not_equal(array, 0) ||
309efe51d0cSJohn Levon 		    implied_not_equal(offset_expr, 0)) {
310efe51d0cSJohn Levon 			*rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
3111f5207b7SJohn Levon 			return 1;
3121f5207b7SJohn Levon 		}
3131f5207b7SJohn Levon 
314efe51d0cSJohn Levon 		return 0;
315efe51d0cSJohn Levon 	}
316efe51d0cSJohn Levon 
317efe51d0cSJohn Levon 	if (expr->type == EXPR_DEREF && expr->member) {
318efe51d0cSJohn Levon 		struct range_list *unop_rl;
319efe51d0cSJohn Levon 		int offset;
3201f5207b7SJohn Levon 
321efe51d0cSJohn Levon 		offset = get_member_offset_from_deref(expr);
322efe51d0cSJohn Levon 		unop = strip_expr(expr->unop);
323efe51d0cSJohn Levon 		if (unop->type == EXPR_PREOP && unop->op == '*')
3241f5207b7SJohn Levon 			unop = strip_expr(unop->unop);
3251f5207b7SJohn Levon 
326efe51d0cSJohn Levon 		if (offset >= 0 &&
327efe51d0cSJohn Levon 		    get_implied_rl(unop, &unop_rl) &&
328efe51d0cSJohn Levon 		    !is_whole_rl(unop_rl)) {
329efe51d0cSJohn Levon 			*rl = unop_rl;
3301f5207b7SJohn Levon 			add_offset_to_pointer(rl, offset);
3311f5207b7SJohn Levon 			return 1;
3321f5207b7SJohn Levon 		}
3331f5207b7SJohn Levon 
334efe51d0cSJohn Levon 		if (implied_not_equal(unop, 0) || offset > 0) {
335efe51d0cSJohn Levon 			*rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
336efe51d0cSJohn Levon 			return 1;
337efe51d0cSJohn Levon 		}
338efe51d0cSJohn Levon 
3391f5207b7SJohn Levon 		return 0;
3401f5207b7SJohn Levon 	}
3411f5207b7SJohn Levon 
3421f5207b7SJohn Levon 	if (is_non_null_array(expr)) {
3431f5207b7SJohn Levon 		*rl = alloc_rl(array_min_sval, array_max_sval);
3441f5207b7SJohn Levon 		return 1;
3451f5207b7SJohn Levon 	}
3461f5207b7SJohn Levon 
3471f5207b7SJohn Levon 	return 0;
3481f5207b7SJohn Levon }
349