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 
merge_estates(struct smatch_state * s1,struct smatch_state * s2)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 	if (estate_treat_untagged(s1) && estate_treat_untagged(s2))
57 		estate_set_treat_untagged(tmp);
58 
59 	if (estate_new(s1) || estate_new(s2))
60 		estate_set_new(tmp);
61 
62 	return tmp;
63 }
64 
get_dinfo(struct smatch_state * state)65 struct data_info *get_dinfo(struct smatch_state *state)
66 {
67 	if (!state)
68 		return NULL;
69 	return (struct data_info *)state->data;
70 }
71 
estate_rl(struct smatch_state * state)72 struct range_list *estate_rl(struct smatch_state *state)
73 {
74 	if (!state)
75 		return NULL;
76 	return get_dinfo(state)->value_ranges;
77 }
78 
estate_related(struct smatch_state * state)79 struct related_list *estate_related(struct smatch_state *state)
80 {
81 	if (!state)
82 		return NULL;
83 	return get_dinfo(state)->related;
84 }
85 
estate_get_fuzzy_max(struct smatch_state * state)86 sval_t estate_get_fuzzy_max(struct smatch_state *state)
87 {
88 	sval_t empty = {};
89 
90 	if (!state || !get_dinfo(state))
91 		return empty;
92 	return get_dinfo(state)->fuzzy_max;
93 }
94 
estate_has_fuzzy_max(struct smatch_state * state)95 int estate_has_fuzzy_max(struct smatch_state *state)
96 {
97 	if (estate_get_fuzzy_max(state).type)
98 		return 1;
99 	return 0;
100 }
101 
estate_set_fuzzy_max(struct smatch_state * state,sval_t fuzzy_max)102 void estate_set_fuzzy_max(struct smatch_state *state, sval_t fuzzy_max)
103 {
104 	if (!rl_has_sval(estate_rl(state), fuzzy_max))
105 		return;
106 	get_dinfo(state)->fuzzy_max = fuzzy_max;
107 }
108 
estate_copy_fuzzy_max(struct smatch_state * new,struct smatch_state * old)109 void estate_copy_fuzzy_max(struct smatch_state *new, struct smatch_state *old)
110 {
111 	if (!estate_has_fuzzy_max(old))
112 		return;
113 	estate_set_fuzzy_max(new, estate_get_fuzzy_max(old));
114 }
115 
estate_clear_fuzzy_max(struct smatch_state * state)116 void estate_clear_fuzzy_max(struct smatch_state *state)
117 {
118 	sval_t empty = {};
119 
120 	get_dinfo(state)->fuzzy_max = empty;
121 }
122 
estate_has_hard_max(struct smatch_state * state)123 int estate_has_hard_max(struct smatch_state *state)
124 {
125 	if (!state || !estate_rl(state))
126 		return 0;
127 	return get_dinfo(state)->hard_max;
128 }
129 
estate_set_hard_max(struct smatch_state * state)130 void estate_set_hard_max(struct smatch_state *state)
131 {
132 	/* pointers don't have a hard max */
133 	if (is_ptr_type(estate_type(state)))
134 		return;
135 	get_dinfo(state)->hard_max = 1;
136 }
137 
estate_clear_hard_max(struct smatch_state * state)138 void estate_clear_hard_max(struct smatch_state *state)
139 {
140 	get_dinfo(state)->hard_max = 0;
141 }
142 
estate_get_hard_max(struct smatch_state * state,sval_t * sval)143 int estate_get_hard_max(struct smatch_state *state, sval_t *sval)
144 {
145 	if (!state || !get_dinfo(state)->hard_max || !estate_rl(state))
146 		return 0;
147 	*sval = rl_max(estate_rl(state));
148 	return 1;
149 }
150 
estate_capped(struct smatch_state * state)151 bool estate_capped(struct smatch_state *state)
152 {
153 	if (!state)
154 		return false;
155 	/* impossible states are capped */
156 	if (!estate_rl(state))
157 		return true;
158 	return get_dinfo(state)->capped;
159 }
160 
estate_set_capped(struct smatch_state * state)161 void estate_set_capped(struct smatch_state *state)
162 {
163 	get_dinfo(state)->capped = true;
164 }
165 
estate_treat_untagged(struct smatch_state * state)166 bool estate_treat_untagged(struct smatch_state *state)
167 {
168 	if (!state)
169 		return false;
170 
171 	/* impossible states are capped */
172 	if (!estate_rl(state))
173 		return true;
174 
175 	return get_dinfo(state)->treat_untagged;
176 }
177 
estate_set_treat_untagged(struct smatch_state * state)178 void estate_set_treat_untagged(struct smatch_state *state)
179 {
180 	get_dinfo(state)->treat_untagged = true;
181 }
182 
estate_new(struct smatch_state * state)183 bool estate_new(struct smatch_state *state)
184 {
185 	if (!estate_rl(state))
186 		return false;
187 	return get_dinfo(state)->set;
188 }
189 
estate_set_new(struct smatch_state * state)190 void estate_set_new(struct smatch_state *state)
191 {
192 	get_dinfo(state)->set = true;
193 }
194 
estate_min(struct smatch_state * state)195 sval_t estate_min(struct smatch_state *state)
196 {
197 	return rl_min(estate_rl(state));
198 }
199 
estate_max(struct smatch_state * state)200 sval_t estate_max(struct smatch_state *state)
201 {
202 	return rl_max(estate_rl(state));
203 }
204 
estate_type(struct smatch_state * state)205 struct symbol *estate_type(struct smatch_state *state)
206 {
207 	return rl_max(estate_rl(state)).type;
208 }
209 
rlists_equiv(struct related_list * one,struct related_list * two)210 static int rlists_equiv(struct related_list *one, struct related_list *two)
211 {
212 	struct relation *one_rel;
213 	struct relation *two_rel;
214 
215 	PREPARE_PTR_LIST(one, one_rel);
216 	PREPARE_PTR_LIST(two, two_rel);
217 	for (;;) {
218 		if (!one_rel && !two_rel)
219 			return 1;
220 		if (!one_rel || !two_rel)
221 			return 0;
222 		if (one_rel->sym != two_rel->sym)
223 			return 0;
224 		if (strcmp(one_rel->name, two_rel->name))
225 			return 0;
226 		NEXT_PTR_LIST(one_rel);
227 		NEXT_PTR_LIST(two_rel);
228 	}
229 	FINISH_PTR_LIST(two_rel);
230 	FINISH_PTR_LIST(one_rel);
231 
232 	return 1;
233 }
234 
estates_equiv(struct smatch_state * one,struct smatch_state * two)235 int estates_equiv(struct smatch_state *one, struct smatch_state *two)
236 {
237 	if (!one || !two)
238 		return 0;
239 	if (one == two)
240 		return 1;
241 	if (!rlists_equiv(estate_related(one), estate_related(two)))
242 		return 0;
243 	if (estate_capped(one) != estate_capped(two))
244 		return 0;
245 	if (estate_treat_untagged(one) != estate_treat_untagged(two))
246 		return 0;
247 	if (estate_has_hard_max(one) != estate_has_hard_max(two))
248 		return 0;
249 	if (estate_new(one) != estate_new(two))
250 		return 0;
251 	if (strcmp(one->name, two->name) == 0)
252 		return 1;
253 	return 0;
254 }
255 
estate_is_whole(struct smatch_state * state)256 int estate_is_whole(struct smatch_state *state)
257 {
258 	return is_whole_rl(estate_rl(state));
259 }
260 
estate_is_empty(struct smatch_state * state)261 int estate_is_empty(struct smatch_state *state)
262 {
263 	return state && !estate_rl(state);
264 }
265 
estate_is_unknown(struct smatch_state * state)266 int estate_is_unknown(struct smatch_state *state)
267 {
268 	if (!estate_is_whole(state))
269 		return 0;
270 	if (estate_related(state))
271 		return 0;
272 	if (estate_has_fuzzy_max(state))
273 		return 0;
274 	return 1;
275 }
276 
estate_get_single_value(struct smatch_state * state,sval_t * sval)277 int estate_get_single_value(struct smatch_state *state, sval_t *sval)
278 {
279 	sval_t min, max;
280 
281 	if (!estate_rl(state))
282 		return 0;
283 	min = rl_min(estate_rl(state));
284 	max = rl_max(estate_rl(state));
285 	if (sval_cmp(min, max) != 0)
286 		return 0;
287 	*sval = min;
288 	return 1;
289 }
290 
alloc_dinfo(void)291 static struct data_info *alloc_dinfo(void)
292 {
293 	struct data_info *ret;
294 
295 	ret = __alloc_data_info(0);
296 	memset(ret, 0, sizeof(*ret));
297 	return ret;
298 }
299 
alloc_dinfo_range(sval_t min,sval_t max)300 static struct data_info *alloc_dinfo_range(sval_t min, sval_t max)
301 {
302 	struct data_info *ret;
303 
304 	ret = alloc_dinfo();
305 	add_range(&ret->value_ranges, min, max);
306 	return ret;
307 }
308 
alloc_dinfo_range_list(struct range_list * rl)309 static struct data_info *alloc_dinfo_range_list(struct range_list *rl)
310 {
311 	struct data_info *ret;
312 
313 	ret = alloc_dinfo();
314 	ret->value_ranges = rl;
315 	return ret;
316 }
317 
clone_dinfo(struct data_info * dinfo)318 static struct data_info *clone_dinfo(struct data_info *dinfo)
319 {
320 	struct data_info *ret;
321 
322 	ret = alloc_dinfo();
323 	ret->related = clone_related_list(dinfo->related);
324 	ret->value_ranges = clone_rl(dinfo->value_ranges);
325 	ret->hard_max = dinfo->hard_max;
326 	ret->fuzzy_max = dinfo->fuzzy_max;
327 	return ret;
328 }
329 
clone_estate(struct smatch_state * state)330 struct smatch_state *clone_estate(struct smatch_state *state)
331 {
332 	struct smatch_state *ret;
333 
334 	if (!state)
335 		return NULL;
336 
337 	ret = __alloc_smatch_state(0);
338 	ret->name = state->name;
339 	ret->data = clone_dinfo(get_dinfo(state));
340 	return ret;
341 }
342 
clone_partial_estate(struct smatch_state * state,struct range_list * rl)343 struct smatch_state *clone_partial_estate(struct smatch_state *state, struct range_list *rl)
344 {
345 	struct smatch_state *ret;
346 
347 	if (!state)
348 		return NULL;
349 
350 	rl = cast_rl(estate_type(state), rl);
351 
352 	ret = alloc_estate_rl(rl);
353 	set_related(ret, clone_related_list(estate_related(state)));
354 	if (estate_has_hard_max(state))
355 		estate_set_hard_max(ret);
356 	if (estate_has_fuzzy_max(state))
357 		estate_set_fuzzy_max(ret, estate_get_fuzzy_max(state));
358 
359 	return ret;
360 }
361 
alloc_estate_empty(void)362 struct smatch_state *alloc_estate_empty(void)
363 {
364 	struct smatch_state *state;
365 	struct data_info *dinfo;
366 
367 	dinfo = alloc_dinfo();
368 	state = __alloc_smatch_state(0);
369 	state->data = dinfo;
370 	state->name = "";
371 	return state;
372 }
373 
alloc_estate_whole(struct symbol * type)374 struct smatch_state *alloc_estate_whole(struct symbol *type)
375 {
376 	return alloc_estate_rl(alloc_whole_rl(type));
377 }
378 
extra_empty(void)379 struct smatch_state *extra_empty(void)
380 {
381 	struct smatch_state *ret;
382 
383 	ret = __alloc_smatch_state(0);
384 	ret->name = "empty";
385 	ret->data = alloc_dinfo();
386 	return ret;
387 }
388 
alloc_estate_sval(sval_t sval)389 struct smatch_state *alloc_estate_sval(sval_t sval)
390 {
391 	struct smatch_state *state;
392 
393 	state = __alloc_smatch_state(0);
394 	state->data = alloc_dinfo_range(sval, sval);
395 	state->name = show_rl(get_dinfo(state)->value_ranges);
396 	estate_set_hard_max(state);
397 	estate_set_fuzzy_max(state, sval);
398 	return state;
399 }
400 
alloc_estate_range(sval_t min,sval_t max)401 struct smatch_state *alloc_estate_range(sval_t min, sval_t max)
402 {
403 	struct smatch_state *state;
404 
405 	state = __alloc_smatch_state(0);
406 	state->data = alloc_dinfo_range(min, max);
407 	state->name = show_rl(get_dinfo(state)->value_ranges);
408 	return state;
409 }
410 
alloc_estate_rl(struct range_list * rl)411 struct smatch_state *alloc_estate_rl(struct range_list *rl)
412 {
413 	struct smatch_state *state;
414 
415 	if (!rl)
416 		return extra_empty();
417 
418 	state = __alloc_smatch_state(0);
419 	state->data = alloc_dinfo_range_list(rl);
420 	state->name = show_rl(rl);
421 	return state;
422 }
423 
clone_estate_cast(struct symbol * type,struct smatch_state * state)424 struct smatch_state *clone_estate_cast(struct symbol *type, struct smatch_state *state)
425 {
426 	struct smatch_state *ret;
427 	struct data_info *dinfo;
428 
429 	if (!state)
430 		return NULL;
431 
432 	dinfo = alloc_dinfo();
433 	dinfo->value_ranges = clone_rl(cast_rl(type, estate_rl(state)));
434 
435 	ret = __alloc_smatch_state(0);
436 	ret->name = show_rl(dinfo->value_ranges);
437 	ret->data = dinfo;
438 
439 	return ret;
440 }
441 
get_implied_estate(struct expression * expr)442 struct smatch_state *get_implied_estate(struct expression *expr)
443 {
444 	struct smatch_state *state;
445 	struct range_list *rl;
446 
447 	state = get_state_expr(SMATCH_EXTRA, expr);
448 	if (state)
449 		return state;
450 	if (!get_implied_rl(expr, &rl))
451 		rl = alloc_whole_rl(get_type(expr));
452 	return alloc_estate_rl(rl);
453 }
454 
455 /*
456  * One of the complications is that smatch tries to free a bunch of data at the
457  * end of every function.
458  */
clone_dinfo_perm(struct data_info * dinfo)459 struct data_info *clone_dinfo_perm(struct data_info *dinfo)
460 {
461 	struct data_info *ret;
462 
463 	ret = malloc(sizeof(*ret));
464 	memset(ret, 0, sizeof(*ret));
465 	ret->related = NULL;
466 	ret->value_ranges = clone_rl_permanent(dinfo->value_ranges);
467 	ret->hard_max = 0;
468 	ret->fuzzy_max = dinfo->fuzzy_max;
469 	return ret;
470 }
471 
clone_estate_perm(struct smatch_state * state)472 struct smatch_state *clone_estate_perm(struct smatch_state *state)
473 {
474 	struct smatch_state *ret;
475 
476 	ret = malloc(sizeof(*ret));
477 	ret->name = alloc_string(state->name);
478 	ret->data = clone_dinfo_perm(get_dinfo(state));
479 	return ret;
480 }
481 
482 
483