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
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
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
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
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
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
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
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
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 }