xref: /illumos-gate/usr/src/tools/smatch/src/smatch_estate.c (revision e982f11fb2fc266a3d04a69ea3edcf51f44b1e0f) 
1 /*
2  * Copyright (C) 2010 Dan Carpenter.
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  * smatch_dinfo.c has helper functions for handling data_info structs
20  *
21  */
22 
23 #include <stdlib.h>
24 #ifndef __USE_ISOC99
25 #define __USE_ISOC99
26 #endif
27 #include <limits.h>
28 #include "parse.h"
29 #include "smatch.h"
30 #include "smatch_slist.h"
31 #include "smatch_extra.h"
32 
33 struct smatch_state *merge_estates(struct smatch_state *s1, struct smatch_state *s2)
34 {
35 	struct smatch_state *tmp;
36 	struct range_list *value_ranges;
37 	struct related_list *rlist;
38 
39 	if (estates_equiv(s1, s2))
40 		return s1;
41 
42 	value_ranges = rl_union(estate_rl(s1), estate_rl(s2));
43 	tmp = alloc_estate_rl(value_ranges);
44 	rlist = get_shared_relations(estate_related(s1), estate_related(s2));
45 	set_related(tmp, rlist);
46 
47 	if ((estate_has_hard_max(s1) && (!estate_rl(s2) || estate_has_hard_max(s2))) ||
48 	    (estate_has_hard_max(s2) && (!estate_rl(s1) || estate_has_hard_max(s1))))
49 		estate_set_hard_max(tmp);
50 
51 	estate_set_fuzzy_max(tmp, sval_max(estate_get_fuzzy_max(s1), estate_get_fuzzy_max(s2)));
52 
53 	if (estate_capped(s1) && estate_capped(s2))
54 		estate_set_capped(tmp);
55 
56 	return tmp;
57 }
58 
59 struct data_info *get_dinfo(struct smatch_state *state)
60 {
61 	if (!state)
62 		return NULL;
63 	return (struct data_info *)state->data;
64 }
65 
66 struct range_list *estate_rl(struct smatch_state *state)
67 {
68 	if (!state)
69 		return NULL;
70 	return get_dinfo(state)->value_ranges;
71 }
72 
73 struct related_list *estate_related(struct smatch_state *state)
74 {
75 	if (!state)
76 		return NULL;
77 	return get_dinfo(state)->related;
78 }
79 
80 sval_t estate_get_fuzzy_max(struct smatch_state *state)
81 {
82 	sval_t empty = {};
83 
84 	if (!state || !get_dinfo(state))
85 		return empty;
86 	return get_dinfo(state)->fuzzy_max;
87 }
88 
89 int estate_has_fuzzy_max(struct smatch_state *state)
90 {
91 	if (estate_get_fuzzy_max(state).type)
92 		return 1;
93 	return 0;
94 }
95 
96 void estate_set_fuzzy_max(struct smatch_state *state, sval_t fuzzy_max)
97 {
98 	if (!rl_has_sval(estate_rl(state), fuzzy_max))
99 		return;
100 	get_dinfo(state)->fuzzy_max = fuzzy_max;
101 }
102 
103 void estate_copy_fuzzy_max(struct smatch_state *new, struct smatch_state *old)
104 {
105 	if (!estate_has_fuzzy_max(old))
106 		return;
107 	estate_set_fuzzy_max(new, estate_get_fuzzy_max(old));
108 }
109 
110 void estate_clear_fuzzy_max(struct smatch_state *state)
111 {
112 	sval_t empty = {};
113 
114 	get_dinfo(state)->fuzzy_max = empty;
115 }
116 
117 int estate_has_hard_max(struct smatch_state *state)
118 {
119 	if (!state)
120 		return 0;
121 	return get_dinfo(state)->hard_max;
122 }
123 
124 void estate_set_hard_max(struct smatch_state *state)
125 {
126 	get_dinfo(state)->hard_max = 1;
127 }
128 
129 void estate_clear_hard_max(struct smatch_state *state)
130 {
131 	get_dinfo(state)->hard_max = 0;
132 }
133 
134 int estate_get_hard_max(struct smatch_state *state, sval_t *sval)
135 {
136 	if (!state || !get_dinfo(state)->hard_max || !estate_rl(state))
137 		return 0;
138 	*sval = rl_max(estate_rl(state));
139 	return 1;
140 }
141 
142 bool estate_capped(struct smatch_state *state)
143 {
144 	if (!state)
145 		return false;
146 	/* impossible states are capped */
147 	if (!estate_rl(state))
148 		return true;
149 	return get_dinfo(state)->capped;
150 }
151 
152 void estate_set_capped(struct smatch_state *state)
153 {
154 	get_dinfo(state)->capped = true;
155 }
156 
157 sval_t estate_min(struct smatch_state *state)
158 {
159 	return rl_min(estate_rl(state));
160 }
161 
162 sval_t estate_max(struct smatch_state *state)
163 {
164 	return rl_max(estate_rl(state));
165 }
166 
167 struct symbol *estate_type(struct smatch_state *state)
168 {
169 	return rl_max(estate_rl(state)).type;
170 }
171 
172 static int rlists_equiv(struct related_list *one, struct related_list *two)
173 {
174 	struct relation *one_rel;
175 	struct relation *two_rel;
176 
177 	PREPARE_PTR_LIST(one, one_rel);
178 	PREPARE_PTR_LIST(two, two_rel);
179 	for (;;) {
180 		if (!one_rel && !two_rel)
181 			return 1;
182 		if (!one_rel || !two_rel)
183 			return 0;
184 		if (one_rel->sym != two_rel->sym)
185 			return 0;
186 		if (strcmp(one_rel->name, two_rel->name))
187 			return 0;
188 		NEXT_PTR_LIST(one_rel);
189 		NEXT_PTR_LIST(two_rel);
190 	}
191 	FINISH_PTR_LIST(two_rel);
192 	FINISH_PTR_LIST(one_rel);
193 
194 	return 1;
195 }
196 
197 int estates_equiv(struct smatch_state *one, struct smatch_state *two)
198 {
199 	if (!one || !two)
200 		return 0;
201 	if (one == two)
202 		return 1;
203 	if (!rlists_equiv(estate_related(one), estate_related(two)))
204 		return 0;
205 	if (estate_capped(one) != estate_capped(two))
206 		return 0;
207 	if (strcmp(one->name, two->name) == 0)
208 		return 1;
209 	return 0;
210 }
211 
212 int estate_is_whole(struct smatch_state *state)
213 {
214 	return is_whole_rl(estate_rl(state));
215 }
216 
217 int estate_is_empty(struct smatch_state *state)
218 {
219 	return state && !estate_rl(state);
220 }
221 
222 int estate_is_unknown(struct smatch_state *state)
223 {
224 	if (!estate_is_whole(state))
225 		return 0;
226 	if (estate_related(state))
227 		return 0;
228 	if (estate_has_fuzzy_max(state))
229 		return 0;
230 	return 1;
231 }
232 
233 int estate_get_single_value(struct smatch_state *state, sval_t *sval)
234 {
235 	sval_t min, max;
236 
237 	min = rl_min(estate_rl(state));
238 	max = rl_max(estate_rl(state));
239 	if (sval_cmp(min, max) != 0)
240 		return 0;
241 	*sval = min;
242 	return 1;
243 }
244 
245 static struct data_info *alloc_dinfo(void)
246 {
247 	struct data_info *ret;
248 
249 	ret = __alloc_data_info(0);
250 	memset(ret, 0, sizeof(*ret));
251 	return ret;
252 }
253 
254 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max)
255 {
256 	struct data_info *ret;
257 
258 	ret = alloc_dinfo();
259 	add_range(&ret->value_ranges, min, max);
260 	return ret;
261 }
262 
263 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
264 {
265 	struct data_info *ret;
266 
267 	ret = alloc_dinfo();
268 	ret->value_ranges = rl;
269 	return ret;
270 }
271 
272 static struct data_info *clone_dinfo(struct data_info *dinfo)
273 {
274 	struct data_info *ret;
275 
276 	ret = alloc_dinfo();
277 	ret->related = clone_related_list(dinfo->related);
278 	ret->value_ranges = clone_rl(dinfo->value_ranges);
279 	ret->hard_max = dinfo->hard_max;
280 	ret->fuzzy_max = dinfo->fuzzy_max;
281 	return ret;
282 }
283 
284 struct smatch_state *clone_estate(struct smatch_state *state)
285 {
286 	struct smatch_state *ret;
287 
288 	if (!state)
289 		return NULL;
290 
291 	ret = __alloc_smatch_state(0);
292 	ret->name = state->name;
293 	ret->data = clone_dinfo(get_dinfo(state));
294 	return ret;
295 }
296 
297 struct smatch_state *clone_partial_estate(struct smatch_state *state, struct range_list *rl)
298 {
299 	struct smatch_state *ret;
300 
301 	if (!state)
302 		return NULL;
303 
304 	rl = cast_rl(estate_type(state), rl);
305 
306 	ret = alloc_estate_rl(rl);
307 	set_related(ret, clone_related_list(estate_related(state)));
308 	if (estate_has_hard_max(state))
309 		estate_set_hard_max(ret);
310 	if (estate_has_fuzzy_max(state))
311 		estate_set_fuzzy_max(ret, estate_get_fuzzy_max(state));
312 
313 	return ret;
314 }
315 
316 struct smatch_state *alloc_estate_empty(void)
317 {
318 	struct smatch_state *state;
319 	struct data_info *dinfo;
320 
321 	dinfo = alloc_dinfo();
322 	state = __alloc_smatch_state(0);
323 	state->data = dinfo;
324 	state->name = "";
325 	return state;
326 }
327 
328 struct smatch_state *alloc_estate_whole(struct symbol *type)
329 {
330 	return alloc_estate_rl(alloc_whole_rl(type));
331 }
332 
333 struct smatch_state *extra_empty(void)
334 {
335 	struct smatch_state *ret;
336 
337 	ret = __alloc_smatch_state(0);
338 	ret->name = "empty";
339 	ret->data = alloc_dinfo();
340 	return ret;
341 }
342 
343 struct smatch_state *alloc_estate_sval(sval_t sval)
344 {
345 	struct smatch_state *state;
346 
347 	state = __alloc_smatch_state(0);
348 	state->data = alloc_dinfo_range(sval, sval);
349 	state->name = show_rl(get_dinfo(state)->value_ranges);
350 	estate_set_hard_max(state);
351 	estate_set_fuzzy_max(state, sval);
352 	return state;
353 }
354 
355 struct smatch_state *alloc_estate_range(sval_t min, sval_t max)
356 {
357 	struct smatch_state *state;
358 
359 	state = __alloc_smatch_state(0);
360 	state->data = alloc_dinfo_range(min, max);
361 	state->name = show_rl(get_dinfo(state)->value_ranges);
362 	return state;
363 }
364 
365 struct smatch_state *alloc_estate_rl(struct range_list *rl)
366 {
367 	struct smatch_state *state;
368 
369 	if (!rl)
370 		return extra_empty();
371 
372 	state = __alloc_smatch_state(0);
373 	state->data = alloc_dinfo_range_list(rl);
374 	state->name = show_rl(rl);
375 	return state;
376 }
377 
378 struct smatch_state *clone_estate_cast(struct symbol *type, struct smatch_state *state)
379 {
380 	struct smatch_state *ret;
381 	struct data_info *dinfo;
382 
383 	if (!state)
384 		return NULL;
385 
386 	dinfo = alloc_dinfo();
387 	dinfo->value_ranges = clone_rl(cast_rl(type, estate_rl(state)));
388 
389 	ret = __alloc_smatch_state(0);
390 	ret->name = show_rl(dinfo->value_ranges);
391 	ret->data = dinfo;
392 
393 	return ret;
394 }
395 
396 struct smatch_state *get_implied_estate(struct expression *expr)
397 {
398 	struct smatch_state *state;
399 	struct range_list *rl;
400 
401 	state = get_state_expr(SMATCH_EXTRA, expr);
402 	if (state)
403 		return state;
404 	if (!get_implied_rl(expr, &rl))
405 		rl = alloc_whole_rl(get_type(expr));
406 	return alloc_estate_rl(rl);
407 }
408 
409 /*
410  * One of the complications is that smatch tries to free a bunch of data at the
411  * end of every function.
412  */
413 struct data_info *clone_dinfo_perm(struct data_info *dinfo)
414 {
415 	struct data_info *ret;
416 
417 	ret = malloc(sizeof(*ret));
418 	memset(ret, 0, sizeof(*ret));
419 	ret->related = NULL;
420 	ret->value_ranges = clone_rl_permanent(dinfo->value_ranges);
421 	ret->hard_max = 0;
422 	ret->fuzzy_max = dinfo->fuzzy_max;
423 	return ret;
424 }
425 
426 struct smatch_state *clone_estate_perm(struct smatch_state *state)
427 {
428 	struct smatch_state *ret;
429 
430 	ret = malloc(sizeof(*ret));
431 	ret->name = alloc_string(state->name);
432 	ret->data = clone_dinfo_perm(get_dinfo(state));
433 	return ret;
434 }
435 
436 
437