xref: /illumos-gate/usr/src/tools/smatch/src/smatch_address.c (revision 5a0e240f87295cfc13c53236f30ccace0d5412c7)
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 
is_non_null_array(struct expression * expr)22 static bool is_non_null_array(struct expression *expr)
23 {
24 	struct symbol *type;
25 	struct symbol *sym;
26 	struct symbol *tmp;
27 	int i;
28 
29 	type = get_type(expr);
30 	if (!type || type->type != SYM_ARRAY)
31 		return 0;
32 	if (expr->type == EXPR_SYMBOL)
33 		return 1;
34 	if (implied_not_equal(expr, 0))
35 		return 1;
36 
37 	/* verify that it's not the first member of the struct */
38 	if (expr->type != EXPR_DEREF || !expr->member)
39 		return 0;
40 	sym = expr_to_sym(expr);
41 	if (!sym)
42 		return 0;
43 	type = get_real_base_type(sym);
44 	if (!type || type->type != SYM_PTR)
45 		return 0;
46 	type = get_real_base_type(type);
47 	if (type->type != SYM_STRUCT)
48 		return 0;
49 
50 	i = 0;
51 	FOR_EACH_PTR(type->symbol_list, tmp) {
52 		i++;
53 		if (!tmp->ident)
54 			continue;
55 		if (strcmp(expr->member->name, tmp->ident->name) == 0) {
56 			if (i == 1)
57 				return 0;
58 			return 1;
59 		}
60 	} END_FOR_EACH_PTR(tmp);
61 
62 	return 0;
63 }
64 
matches_anonymous_union(struct symbol * sym,const char * member_name)65 static bool matches_anonymous_union(struct symbol *sym, const char *member_name)
66 {
67 	struct symbol *type, *tmp;
68 
69 	if (sym->ident)
70 		return false;
71 	type = get_real_base_type(sym);
72 	if (!type || type->type != SYM_UNION)
73 		return false;
74 
75 	FOR_EACH_PTR(type->symbol_list, tmp) {
76 		if (tmp->ident &&
77 		    strcmp(member_name, tmp->ident->name) == 0) {
78 			return true;
79 		}
80 	} END_FOR_EACH_PTR(tmp);
81 
82 	return false;
83 }
84 
get_member_offset(struct symbol * type,const char * member_name)85 int get_member_offset(struct symbol *type, const char *member_name)
86 {
87 	struct symbol *tmp;
88 	int offset;
89 	int bits;
90 
91 	if (!type || type->type != SYM_STRUCT)
92 		return -1;
93 
94 	bits = 0;
95 	offset = 0;
96 	FOR_EACH_PTR(type->symbol_list, tmp) {
97 		if (bits_to_bytes(bits + type_bits(tmp)) > tmp->ctype.alignment) {
98 			offset += bits_to_bytes(bits);
99 			bits = 0;
100 		}
101 		offset = ALIGN(offset, tmp->ctype.alignment);
102 		if (tmp->ident &&
103 		    strcmp(member_name, tmp->ident->name) == 0) {
104 			return offset;
105 		}
106 		if (matches_anonymous_union(tmp, member_name))
107 			return offset;
108 		if (!(type_bits(tmp) % 8) && type_bits(tmp) / 8 == type_bytes(tmp))
109 			offset += type_bytes(tmp);
110 		else
111 			bits += type_bits(tmp);
112 	} END_FOR_EACH_PTR(tmp);
113 	return -1;
114 }
115 
get_member_offset_from_deref(struct expression * expr)116 int get_member_offset_from_deref(struct expression *expr)
117 {
118 	struct symbol *type;
119 	struct ident *member;
120 	int offset;
121 
122 	/*
123 	 * FIXME: This doesn't handle foo.u.bar correctly.
124 	 *
125 	 */
126 
127 	if (expr->type != EXPR_DEREF)  /* hopefully, this doesn't happen */
128 		return -1;
129 
130 	if (expr->member_offset >= 0)
131 		return expr->member_offset;
132 
133 	member = expr->member;
134 	if (!member)
135 		return -1;
136 
137 	type = get_type(expr->deref);
138 	if (type_is_ptr(type))
139 		type = get_real_base_type(type);
140 	if (!type || type->type != SYM_STRUCT)
141 		return -1;
142 
143 	offset = get_member_offset(type, member->name);
144 	if (offset >= 0)
145 		expr->member_offset = offset;
146 	return offset;
147 }
148 
add_offset_to_pointer(struct range_list ** rl,int offset)149 static void add_offset_to_pointer(struct range_list **rl, int offset)
150 {
151 	sval_t min, max, remove, sval;
152 	struct range_list *orig = *rl;
153 
154 	/*
155 	 * Ha ha.  Treating zero as a special case means I'm correct at least a
156 	 * tiny fraction of the time.  Which is better than nothing.
157 	 *
158 	 */
159 	if (offset == 0)
160 		return;
161 
162 	if (is_unknown_ptr(orig))
163 		return;
164 
165 	/*
166 	 * This function doesn't necessarily work how you might expect...
167 	 *
168 	 * Say you have s64min-(-1),1-s64max and you add 8 then I guess what
169 	 * we want to say is maybe something like 9-s64max.  This shows that the
170 	 * min it could be is 9 which is potentially useful information.  But
171 	 * if we start with (-12),5000000-57777777 and we add 8 then we'd want
172 	 * the result to be (-4),5000008-57777777 but (-4),5000000-57777777 is
173 	 * also probably acceptable.  If you start with s64min-s64max then the
174 	 * result should be 8-s64max.
175 	 *
176 	 */
177 
178 	/* We do the math on void pointer type, because this isn't "&v + 16" it
179 	 * is &v->sixteenth_byte.
180 	 */
181 	orig = cast_rl(&ptr_ctype, orig);
182 	min = sval_type_min(&ptr_ctype);
183 	min.value = offset;
184 	max = sval_type_max(&ptr_ctype);
185 
186 	if (!orig || is_whole_rl(orig)) {
187 		*rl = alloc_rl(min, max);
188 		return;
189 	}
190 
191 	/* no wrap around */
192 	max.uvalue = rl_max(orig).uvalue;
193 	if (max.uvalue > sval_type_max(&ptr_ctype).uvalue - offset) {
194 		remove = sval_type_max(&ptr_ctype);
195 		remove.uvalue -= offset;
196 		orig = remove_range(orig, remove, max);
197 	}
198 
199 	sval.type = &int_ctype;
200 	sval.value = offset;
201 
202 	*rl = rl_binop(orig, '+', alloc_rl(sval, sval));
203 }
204 
where_allocated_rl(struct symbol * sym)205 static struct range_list *where_allocated_rl(struct symbol *sym)
206 {
207 	if (!sym)
208 		return NULL;
209 
210 	/* This should just be the mtag if it's not on the stack */
211 	return alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
212 }
213 
handle_fn_address(struct expression * expr,struct range_list ** rl)214 static bool handle_fn_address(struct expression *expr, struct range_list **rl)
215 {
216 	struct symbol *type;
217 
218 	if (expr->type == EXPR_PREOP && expr->op == '&')
219 		expr = strip_expr(expr->unop);
220 
221 	if (expr->type != EXPR_SYMBOL)
222 		return false;
223 
224 	type = get_type(expr);
225 	if (!type || type->type != SYM_FN)
226 		return false;
227 
228 	*rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
229 	return true;
230 }
231 
get_address_rl(struct expression * expr,struct range_list ** rl)232 int get_address_rl(struct expression *expr, struct range_list **rl)
233 {
234 	struct expression *unop;
235 
236 	/*
237 	 * Ugh...  This function is bad.  It doesn't work where it's supposed to
238 	 * and it does more than it really should.  It shouldn't handle string
239 	 * literals I think...
240 	 *
241 	 * There are several complications.  For arrays and functions the "&foo"
242 	 * "foo" are equivalent.  But the problem is that we're also passing in
243 	 * foo->array[] and foo->fn.
244 	 *
245 	 * Then, when we have foo->bar.baz.one.two; that needs to be handled
246 	 * correctly but right now, it is not.
247 	 *
248 	 */
249 
250 	expr = strip_expr(expr);
251 	if (!expr)
252 		return 0;
253 
254 	/*
255 	 * For functions &fn and fn are equivalent.  I don't know if this is
256 	 * really the right place to handle it, but let's just get it out of the
257 	 * way for now.
258 	 *
259 	 */
260 	if (handle_fn_address(expr, rl))
261 		return 1;
262 
263 	/*
264 	 * For arrays, &foo->array and foo->array are equivalent.
265 	 *
266 	 */
267 	if (expr->type == EXPR_PREOP && expr->op == '&') {
268 		expr = strip_expr(expr->unop);
269 	} else {
270 		struct symbol *type;
271 
272 		type = get_type(expr);
273 		if (!type || type->type != SYM_ARRAY)
274 			return 0;
275 	}
276 
277 	if (expr->type == EXPR_SYMBOL) {
278 		*rl = where_allocated_rl(expr->symbol);
279 		return 1;
280 	}
281 
282 	if (is_array(expr)) {
283 		struct expression *array;
284 		struct expression *offset_expr;
285 		struct range_list *array_rl, *offset_rl, *bytes_rl, *res;
286 		struct symbol *type;
287 		sval_t bytes;
288 
289 		array = get_array_base(expr);
290 		offset_expr = get_array_offset(expr);
291 
292 		type = get_type(array);
293 		type = get_real_base_type(type);
294 		bytes.type = ssize_t_ctype;
295 		bytes.uvalue = type_bytes(type);
296 		bytes_rl = alloc_rl(bytes, bytes);
297 
298 		get_absolute_rl(array, &array_rl);
299 		get_absolute_rl(offset_expr, &offset_rl);
300 
301 		if (type_bytes(type)) {
302 			res = rl_binop(offset_rl, '*', bytes_rl);
303 			res = rl_binop(res, '+', array_rl);
304 			*rl = res;
305 			return true;
306 		}
307 
308 		if (implied_not_equal(array, 0) ||
309 		    implied_not_equal(offset_expr, 0)) {
310 			*rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
311 			return 1;
312 		}
313 
314 		return 0;
315 	}
316 
317 	if (expr->type == EXPR_DEREF && expr->member) {
318 		struct range_list *unop_rl;
319 		int offset;
320 
321 		offset = get_member_offset_from_deref(expr);
322 		unop = strip_expr(expr->unop);
323 		if (unop->type == EXPR_PREOP && unop->op == '*')
324 			unop = strip_expr(unop->unop);
325 
326 		if (offset >= 0 &&
327 		    get_implied_rl(unop, &unop_rl) &&
328 		    !is_whole_rl(unop_rl)) {
329 			*rl = unop_rl;
330 			add_offset_to_pointer(rl, offset);
331 			return 1;
332 		}
333 
334 		if (implied_not_equal(unop, 0) || offset > 0) {
335 			*rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
336 			return 1;
337 		}
338 
339 		return 0;
340 	}
341 
342 	if (is_non_null_array(expr)) {
343 		*rl = alloc_rl(array_min_sval, array_max_sval);
344 		return 1;
345 	}
346 
347 	return 0;
348 }
349