xref: /illumos-gate/usr/src/tools/smatch/src/smatch_ranges.c (revision 5a0e240f87295cfc13c53236f30ccace0d5412c7)
1 /*
2  * Copyright (C) 2009 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 #include "parse.h"
19 #include "smatch.h"
20 #include "smatch_extra.h"
21 #include "smatch_slist.h"
22 
23 ALLOCATOR(data_info, "smatch extra data");
24 ALLOCATOR(data_range, "data range");
25 __DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
26 			 "permanent ranges", perm_data_range);
27 __DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
28 
is_err_ptr(sval_t sval)29 bool is_err_ptr(sval_t sval)
30 {
31 	if (option_project != PROJ_KERNEL)
32 		return false;
33 	if (!type_is_ptr(sval.type))
34 		return false;
35 	if (sval.uvalue < -4095ULL)
36 		return false;
37 	return true;
38 }
39 
get_err_pointer_str(struct data_range * drange)40 static char *get_err_pointer_str(struct data_range *drange)
41 {
42 	static char buf[20];
43 
44 	/*
45 	 * The kernel has error pointers where you do essentially:
46 	 *
47 	 * return (void *)(unsigned long)-12;
48 	 *
49 	 * But what I want here is to print -12 instead of the unsigned version
50 	 * of that.
51 	 *
52 	 */
53 	if (!is_err_ptr(drange->min))
54 		return NULL;
55 
56 	if (drange->min.value == drange->max.value)
57 		snprintf(buf, sizeof(buf), "(%lld)", drange->min.value);
58 	else
59 		snprintf(buf, sizeof(buf), "(%lld)-(%lld)", drange->min.value, drange->max.value);
60 	return buf;
61 }
62 
show_rl(struct range_list * list)63 char *show_rl(struct range_list *list)
64 {
65 	struct data_range *prev_drange = NULL;
66 	struct data_range *tmp;
67 	char full[255];
68 	char *p = full;
69 	char *prev = full;
70 	char *err_ptr;
71 	int remain;
72 	int i = 0;
73 
74 	full[0] = '\0';
75 
76 	FOR_EACH_PTR(list, tmp) {
77 		remain = full + sizeof(full) - p;
78 		if (remain < 48) {
79 			snprintf(prev, full + sizeof(full) - prev, ",%s-%s",
80 				 sval_to_str(prev_drange->min),
81 				 sval_to_str(sval_type_max(prev_drange->min.type)));
82 			break;
83 		}
84 		prev_drange = tmp;
85 		prev = p;
86 
87 		err_ptr = get_err_pointer_str(tmp);
88 		if (err_ptr) {
89 			p += snprintf(p, remain, "%s%s", i++ ? "," : "", err_ptr);
90 		} else if (sval_cmp(tmp->min, tmp->max) == 0) {
91 			p += snprintf(p, remain, "%s%s", i++ ? "," : "",
92 				      sval_to_str(tmp->min));
93 		} else {
94 			p += snprintf(p, remain, "%s%s-%s", i++ ? "," : "",
95 				      sval_to_str(tmp->min),
96 				      sval_to_str(tmp->max));
97 		}
98 	} END_FOR_EACH_PTR(tmp);
99 
100 	return alloc_sname(full);
101 }
102 
free_all_rl(void)103 void free_all_rl(void)
104 {
105 	clear_rl_ptrlist_alloc();
106 }
107 
sval_too_big(struct symbol * type,sval_t sval)108 static int sval_too_big(struct symbol *type, sval_t sval)
109 {
110 	if (type_bits(type) >= 32 &&
111 	    type_bits(sval.type) <= type_bits(type))
112 		return 0;
113 	if (sval.uvalue <= ((1ULL << type_bits(type)) - 1))
114 		return 0;
115 	if (type_signed(sval.type)) {
116 		if (type_unsigned(type)) {
117 			unsigned long long neg = ~sval.uvalue;
118 			if (neg <= sval_type_max(type).uvalue)
119 				return 0;
120 		}
121 		if (sval.value < sval_type_min(type).value)
122 			return 1;
123 		if (sval.value > sval_type_max(type).value)
124 			return 1;
125 		return 0;
126 	}
127 	if (sval.uvalue > sval_type_max(type).uvalue)
128 		return 1;
129 	return 0;
130 }
131 
truncates_nicely(struct symbol * type,sval_t min,sval_t max)132 static int truncates_nicely(struct symbol *type, sval_t min, sval_t max)
133 {
134 	unsigned long long mask;
135 	int bits = type_bits(type);
136 
137 	if (type_is_fp(min.type) && !type_is_fp(type))
138 		return 0;
139 
140 	if (bits >= type_bits(min.type))
141 		return 0;
142 
143 	mask = -1ULL << bits;
144 	return (min.uvalue & mask) == (max.uvalue & mask);
145 }
146 
add_range_t(struct symbol * type,struct range_list ** rl,sval_t min,sval_t max)147 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
148 {
149 	/* If we're just adding a number, cast it and add it */
150 	if (sval_cmp(min, max) == 0) {
151 		add_range(rl, sval_cast(type, min), sval_cast(type, max));
152 		return;
153 	}
154 
155 	/* If the range is within the type range then add it */
156 	if (sval_fits(type, min) && sval_fits(type, max)) {
157 		add_range(rl, sval_cast(type, min), sval_cast(type, max));
158 		return;
159 	}
160 
161 	if (truncates_nicely(type, min, max)) {
162 		add_range(rl, sval_cast(type, min), sval_cast(type, max));
163 		return;
164 	}
165 
166 	/*
167 	 * If the range we are adding has more bits than the range type then
168 	 * add the whole range type.  Eg:
169 	 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
170 	 *
171 	 */
172 	if (sval_too_big(type, min) || sval_too_big(type, max)) {
173 		add_range(rl, sval_type_min(type), sval_type_max(type));
174 		return;
175 	}
176 
177 	/* Cast negative values to high positive values */
178 	if (sval_is_negative(min) && type_unsigned(type)) {
179 		if (sval_is_positive(max)) {
180 			if (sval_too_high(type, max)) {
181 				add_range(rl, sval_type_min(type), sval_type_max(type));
182 				return;
183 			}
184 			add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
185 			max = sval_type_max(type);
186 		} else {
187 			max = sval_cast(type, max);
188 		}
189 		min = sval_cast(type, min);
190 		add_range(rl, min, max);
191 	}
192 
193 	/* Cast high positive numbers to negative */
194 	if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
195 		if (!sval_is_negative(sval_cast(type, min))) {
196 			add_range(rl, sval_cast(type, min), sval_type_max(type));
197 			min = sval_type_min(type);
198 		} else {
199 			min = sval_cast(type, min);
200 		}
201 		max = sval_cast(type, max);
202 		add_range(rl, min, max);
203 	}
204 
205 	add_range(rl, sval_cast(type, min), sval_cast(type, max));
206 	return;
207 }
208 
str_to_comparison_arg_helper(const char * str,struct expression * call,int * comparison,struct expression ** arg,const char ** endp)209 static int str_to_comparison_arg_helper(const char *str,
210 		struct expression *call, int *comparison,
211 		struct expression **arg, const char **endp)
212 {
213 	int param;
214 	const char *c = str;
215 
216 	if (*c != '[')
217 		return 0;
218 	c++;
219 
220 	if (*c == '<') {
221 		c++;
222 		if (*c == '=') {
223 			*comparison = SPECIAL_LTE;
224 			c++;
225 		} else {
226 			*comparison = '<';
227 		}
228 	} else if (*c == '=') {
229 		c++;
230 		c++;
231 		*comparison = SPECIAL_EQUAL;
232 	} else if (*c == '>') {
233 		c++;
234 		if (*c == '=') {
235 			*comparison = SPECIAL_GTE;
236 			c++;
237 		} else {
238 			*comparison = '>';
239 		}
240 	} else if (*c == '!') {
241 		c++;
242 		c++;
243 		*comparison = SPECIAL_NOTEQUAL;
244 	} else if (*c == '$') {
245 		*comparison = SPECIAL_EQUAL;
246 	} else {
247 		return 0;
248 	}
249 
250 	if (*c != '$')
251 		return 0;
252 	c++;
253 
254 	param = strtoll(c, (char **)&c, 10);
255 	/*
256 	 * FIXME: handle parameter math.  [==$1 + 100]
257 	 *
258 	 */
259 	if (*c == ' ')
260 		return 0;
261 
262 	if (*c == ',' || *c == ']')
263 		c++; /* skip the ']' character */
264 	if (endp)
265 		*endp = (char *)c;
266 
267 	if (!call)
268 		return 0;
269 	*arg = get_argument_from_call_expr(call->args, param);
270 	if (!*arg)
271 		return 0;
272 	if (*c == '-' && *(c + 1) == '>') {
273 		char buf[256];
274 		int n;
275 
276 		n = snprintf(buf, sizeof(buf), "$%s", c);
277 		if (n >= sizeof(buf))
278 			return 0;
279 		if (buf[n - 1] == ']')
280 			buf[n - 1] = '\0';
281 		*arg = gen_expression_from_key(*arg, buf);
282 		while (*c && *c != ']')
283 			c++;
284 	}
285 	return 1;
286 }
287 
str_to_comparison_arg(const char * str,struct expression * call,int * comparison,struct expression ** arg)288 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
289 {
290 	while (1) {
291 		if (!*str)
292 			return 0;
293 		if (*str == '[')
294 			break;
295 		str++;
296 	}
297 	return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
298 }
299 
get_val_from_key(int use_max,struct symbol * type,const char * c,struct expression * call,const char ** endp,sval_t * sval)300 static int get_val_from_key(int use_max, struct symbol *type, const char *c, struct expression *call, const char **endp, sval_t *sval)
301 {
302 	struct expression *arg;
303 	int comparison;
304 	sval_t ret, tmp;
305 
306 	if (use_max)
307 		ret = sval_type_max(type);
308 	else
309 		ret = sval_type_min(type);
310 
311 	if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
312 		*sval = ret;
313 		return 0;
314 	}
315 
316 	if (use_max && get_implied_max(arg, &tmp)) {
317 		ret = tmp;
318 		if (comparison == '<') {
319 			tmp.value = 1;
320 			ret = sval_binop(ret, '-', tmp);
321 		}
322 	}
323 	if (!use_max && get_implied_min(arg, &tmp)) {
324 		ret = tmp;
325 		if (comparison == '>') {
326 			tmp.value = 1;
327 			ret = sval_binop(ret, '+', tmp);
328 		}
329 	}
330 
331 	*sval = ret;
332 	return 1;
333 }
334 
add_one(sval_t sval)335 static sval_t add_one(sval_t sval)
336 {
337 	sval.value++;
338 	return sval;
339 }
340 
sub_one(sval_t sval)341 static sval_t sub_one(sval_t sval)
342 {
343 	sval.value--;
344 	return sval;
345 }
346 
filter_by_comparison(struct range_list ** rl,int comparison,struct range_list * right)347 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
348 {
349 	struct range_list *left_orig = *rl;
350 	struct range_list *right_orig = right;
351 	struct range_list *ret_rl = *rl;
352 	struct symbol *cast_type;
353 	sval_t min, max;
354 
355 	if (comparison == UNKNOWN_COMPARISON)
356 		return;
357 
358 	cast_type = rl_type(left_orig);
359 	if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
360 		cast_type = rl_type(right_orig);
361 	if (sval_type_max(cast_type).uvalue < INT_MAX)
362 		cast_type = &int_ctype;
363 
364 	min = sval_type_min(cast_type);
365 	max = sval_type_max(cast_type);
366 	left_orig = cast_rl(cast_type, left_orig);
367 	right_orig = cast_rl(cast_type, right_orig);
368 
369 	switch (comparison) {
370 	case '<':
371 	case SPECIAL_UNSIGNED_LT:
372 		ret_rl = remove_range(left_orig, rl_max(right_orig), max);
373 		break;
374 	case SPECIAL_LTE:
375 	case SPECIAL_UNSIGNED_LTE:
376 		if (!sval_is_max(rl_max(right_orig)))
377 			ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
378 		break;
379 	case SPECIAL_EQUAL:
380 		ret_rl = rl_intersection(left_orig, right_orig);
381 		break;
382 	case SPECIAL_GTE:
383 	case SPECIAL_UNSIGNED_GTE:
384 		if (!sval_is_min(rl_min(right_orig)))
385 			ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
386 		break;
387 	case '>':
388 	case SPECIAL_UNSIGNED_GT:
389 		ret_rl = remove_range(left_orig, min, rl_min(right_orig));
390 		break;
391 	case SPECIAL_NOTEQUAL:
392 		if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
393 			ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
394 		break;
395 	default:
396 		sm_perror("unhandled comparison %s", show_special(comparison));
397 		return;
398 	}
399 
400 	*rl = cast_rl(rl_type(*rl), ret_rl);
401 }
402 
filter_by_comparison_call(const char * c,struct expression * call,const char ** endp,struct range_list * start_rl)403 static struct range_list *filter_by_comparison_call(const char *c, struct expression *call, const char **endp, struct range_list *start_rl)
404 {
405 	struct symbol *type;
406 	struct expression *arg;
407 	struct range_list *casted_start, *right_orig;
408 	int comparison;
409 
410 	/* For when we have a function that takes a function pointer. */
411 	if (!call || call->type != EXPR_CALL)
412 		return start_rl;
413 
414 	if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
415 		return start_rl;
416 
417 	if (!get_implied_rl(arg, &right_orig))
418 		return start_rl;
419 
420 	type = &int_ctype;
421 	if (type_positive_bits(rl_type(start_rl)) > type_positive_bits(type))
422 		type = rl_type(start_rl);
423 	if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
424 		type = rl_type(right_orig);
425 
426 	casted_start = cast_rl(type, start_rl);
427 	right_orig = cast_rl(type, right_orig);
428 
429 	filter_by_comparison(&casted_start, comparison, right_orig);
430 	return cast_rl(rl_type(start_rl), casted_start);
431 }
432 
parse_val(int use_max,struct expression * call,struct symbol * type,const char * c,const char ** endp)433 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, const char *c, const char **endp)
434 {
435 	const char *start = c;
436 	sval_t ret;
437 
438 	if (type == &float_ctype)
439 		return sval_type_fval(type, strtof(start, (char **)endp));
440 	else if (type == &double_ctype)
441 		return sval_type_fval(type, strtod(start, (char **)endp));
442 	else if (type == &ldouble_ctype)
443 		return sval_type_fval(type, strtold(start, (char **)endp));
444 
445 	if (!strncmp(start, "max", 3)) {
446 		ret = sval_type_max(type);
447 		c += 3;
448 	} else if (!strncmp(start, "u64max", 6)) {
449 		ret = sval_type_val(type, ULLONG_MAX);
450 		c += 6;
451 	} else if (!strncmp(start, "s64max", 6)) {
452 		ret = sval_type_val(type, LLONG_MAX);
453 		c += 6;
454 	} else if (!strncmp(start, "u32max", 6)) {
455 		ret = sval_type_val(type, UINT_MAX);
456 		c += 6;
457 	} else if (!strncmp(start, "s32max", 6)) {
458 		ret = sval_type_val(type, INT_MAX);
459 		c += 6;
460 	} else if (!strncmp(start, "u16max", 6)) {
461 		ret = sval_type_val(type, USHRT_MAX);
462 		c += 6;
463 	} else if (!strncmp(start, "s16max", 6)) {
464 		ret = sval_type_val(type, SHRT_MAX);
465 		c += 6;
466 	} else if (!strncmp(start, "min", 3)) {
467 		ret = sval_type_min(type);
468 		c += 3;
469 	} else if (!strncmp(start, "s64min", 6)) {
470 		ret = sval_type_val(type, LLONG_MIN);
471 		c += 6;
472 	} else if (!strncmp(start, "s32min", 6)) {
473 		ret = sval_type_val(type, INT_MIN);
474 		c += 6;
475 	} else if (!strncmp(start, "s16min", 6)) {
476 		ret = sval_type_val(type, SHRT_MIN);
477 		c += 6;
478 	} else if (!strncmp(start, "long_min", 8)) {
479 		ret = sval_type_val(type, LONG_MIN);
480 		c += 8;
481 	} else if (!strncmp(start, "long_max", 8)) {
482 		ret = sval_type_val(type, LONG_MAX);
483 		c += 8;
484 	} else if (!strncmp(start, "ulong_max", 9)) {
485 		ret = sval_type_val(type, ULONG_MAX);
486 		c += 9;
487 	} else if (!strncmp(start, "ptr_max", 7)) {
488 		ret = sval_type_val(type, valid_ptr_max);
489 		c += 7;
490 	} else if (start[0] == '[') {
491 		/* this parses [==p0] comparisons */
492 		get_val_from_key(1, type, start, call, &c, &ret);
493 	} else if (type_positive_bits(type) == 64) {
494 		ret = sval_type_val(type, strtoull(start, (char **)&c, 0));
495 	} else {
496 		ret = sval_type_val(type, strtoll(start, (char **)&c, 0));
497 	}
498 	*endp = c;
499 	return ret;
500 }
501 
jump_to_call_math(const char * value)502 static const char *jump_to_call_math(const char *value)
503 {
504 	const char *c = value;
505 
506 	while (*c && *c != '[')
507 		c++;
508 
509 	if (!*c)
510 		return NULL;
511 	c++;
512 	if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
513 		return NULL;
514 
515 	return c;
516 }
517 
get_param_return_rl(struct expression * call,const char * call_math)518 static struct range_list *get_param_return_rl(struct expression *call, const char *call_math)
519 {
520 	struct expression *arg;
521 	int param;
522 
523 	call_math += 3;
524 	param = atoi(call_math);
525 
526 	arg = get_argument_from_call_expr(call->args, param);
527 	if (!arg)
528 		return NULL;
529 
530 	return db_return_vals_no_args(arg);
531 }
532 
str_to_rl_helper(struct expression * call,struct symbol * type,const char * str,const char ** endp,struct range_list ** rl)533 static void str_to_rl_helper(struct expression *call, struct symbol *type, const char *str, const char **endp, struct range_list **rl)
534 {
535 	struct range_list *rl_tmp = NULL;
536 	sval_t prev_min, min, max;
537 	const char *c;
538 
539 	prev_min = sval_type_min(type);
540 	min = sval_type_min(type);
541 	max = sval_type_max(type);
542 	c = str;
543 	while (*c != '\0' && *c != '[') {
544 		if (*c == '+') {
545 			if (sval_cmp(min, sval_type_min(type)) != 0)
546 				min = max;
547 			max = sval_type_max(type);
548 			add_range_t(type, &rl_tmp, min, max);
549 			break;
550 		}
551 		if (*c == '(')
552 			c++;
553 		min = parse_val(0, call, type, c, &c);
554 		if (!sval_fits(type, min))
555 			min = sval_type_min(type);
556 		max = min;
557 		if (*c == ')')
558 			c++;
559 		if (*c == '\0' || *c == '[') {
560 			add_range_t(type, &rl_tmp, min, min);
561 			break;
562 		}
563 		if (*c == ',') {
564 			add_range_t(type, &rl_tmp, min, min);
565 			c++;
566 			continue;
567 		}
568 		if (*c == '+') {
569 			min = prev_min;
570 			max = sval_type_max(type);
571 			add_range_t(type, &rl_tmp, min, max);
572 			c++;
573 			if (*c == '[' || *c == '\0')
574 				break;
575 		}
576 		if (*c != '-') {
577 			sm_debug("XXX: trouble parsing %s c = %s", str, c);
578 			break;
579 		}
580 		c++;
581 		if (*c == '(')
582 			c++;
583 		max = parse_val(1, call, type, c, &c);
584 		if (!sval_fits(type, max))
585 			max = sval_type_max(type);
586 		if (*c == '+') {
587 			max = sval_type_max(type);
588 			add_range_t(type, &rl_tmp, min, max);
589 			c++;
590 			if (*c == '[' || *c == '\0')
591 				break;
592 		}
593 		prev_min = max;
594 		add_range_t(type, &rl_tmp, min, max);
595 		if (*c == ')')
596 			c++;
597 		if (*c == ',')
598 			c++;
599 	}
600 
601 	*rl = rl_tmp;
602 	*endp = c;
603 }
604 
str_to_dinfo(struct expression * call,struct symbol * type,const char * value,struct data_info * dinfo)605 static void str_to_dinfo(struct expression *call, struct symbol *type, const char *value, struct data_info *dinfo)
606 {
607 	struct range_list *math_rl;
608 	const char *call_math;
609 	const char *c;
610 	struct range_list *rl = NULL;
611 
612 	if (!type)
613 		type = &llong_ctype;
614 
615 	if (strcmp(value, "empty") == 0)
616 		return;
617 
618 	if (strncmp(value, "[==$", 4) == 0) {
619 		struct expression *arg;
620 		int comparison;
621 
622 		if (!str_to_comparison_arg(value, call, &comparison, &arg))
623 			return;
624 		if (!get_implied_rl(arg, &rl))
625 			return;
626 		goto cast;
627 	}
628 
629 	str_to_rl_helper(call, type, value, &c, &rl);
630 	if (*c == '\0')
631 		goto cast;
632 
633 	call_math = jump_to_call_math(value);
634 	if (call_math && call_math[0] == 'r') {
635 		math_rl = get_param_return_rl(call, call_math);
636 		if (math_rl)
637 			rl = rl_intersection(rl, math_rl);
638 		goto cast;
639 	}
640 	if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
641 		rl = rl_intersection(rl, math_rl);
642 		goto cast;
643 	}
644 
645 	/*
646 	 * For now if we already tried to handle the call math and couldn't
647 	 * figure it out then bail.
648 	 */
649 	if (jump_to_call_math(c) == c + 1)
650 		goto cast;
651 
652 	rl = filter_by_comparison_call(c, call, &c, rl);
653 
654 cast:
655 	rl = cast_rl(type, rl);
656 	dinfo->value_ranges = rl;
657 }
658 
rl_is_sane(struct range_list * rl)659 static int rl_is_sane(struct range_list *rl)
660 {
661 	struct data_range *tmp;
662 	struct symbol *type;
663 
664 	type = rl_type(rl);
665 	FOR_EACH_PTR(rl, tmp) {
666 		if (!sval_fits(type, tmp->min))
667 			return 0;
668 		if (!sval_fits(type, tmp->max))
669 			return 0;
670 		if (sval_cmp(tmp->min, tmp->max) > 0)
671 			return 0;
672 	} END_FOR_EACH_PTR(tmp);
673 
674 	return 1;
675 }
676 
str_to_rl(struct symbol * type,char * value,struct range_list ** rl)677 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
678 {
679 	struct data_info dinfo = {};
680 
681 	str_to_dinfo(NULL, type, value, &dinfo);
682 	if (!rl_is_sane(dinfo.value_ranges))
683 		dinfo.value_ranges = alloc_whole_rl(type);
684 	*rl = dinfo.value_ranges;
685 }
686 
call_results_to_rl(struct expression * expr,struct symbol * type,const char * value,struct range_list ** rl)687 void call_results_to_rl(struct expression *expr, struct symbol *type, const char *value, struct range_list **rl)
688 {
689 	struct data_info dinfo = {};
690 
691 	str_to_dinfo(strip_expr(expr), type, value, &dinfo);
692 	*rl = dinfo.value_ranges;
693 }
694 
is_whole_rl(struct range_list * rl)695 int is_whole_rl(struct range_list *rl)
696 {
697 	struct data_range *drange;
698 
699 	if (ptr_list_empty((struct ptr_list *)rl))
700 		return 0;
701 	drange = first_ptr_list((struct ptr_list *)rl);
702 	if (sval_is_min(drange->min) && sval_is_max(drange->max))
703 		return 1;
704 	return 0;
705 }
706 
is_unknown_ptr(struct range_list * rl)707 int is_unknown_ptr(struct range_list *rl)
708 {
709 	struct data_range *drange;
710 	int cnt = 0;
711 
712 	if (is_whole_rl(rl))
713 		return 1;
714 
715 	FOR_EACH_PTR(rl, drange) {
716 		if (++cnt >= 3)
717 			return 0;
718 		if (sval_cmp(drange->min, valid_ptr_min_sval) == 0 &&
719 		    sval_cmp(drange->max, valid_ptr_max_sval) == 0)
720 			return 1;
721 	} END_FOR_EACH_PTR(drange);
722 
723 	return 0;
724 }
725 
is_whole_rl_non_zero(struct range_list * rl)726 int is_whole_rl_non_zero(struct range_list *rl)
727 {
728 	struct data_range *drange;
729 
730 	if (ptr_list_empty((struct ptr_list *)rl))
731 		return 0;
732 	drange = first_ptr_list((struct ptr_list *)rl);
733 	if (sval_unsigned(drange->min) &&
734 	    drange->min.value == 1 &&
735 	    sval_is_max(drange->max))
736 		return 1;
737 	if (!sval_is_min(drange->min) || drange->max.value != -1)
738 		return 0;
739 	drange = last_ptr_list((struct ptr_list *)rl);
740 	if (drange->min.value != 1 || !sval_is_max(drange->max))
741 		return 0;
742 	return 1;
743 }
744 
rl_min(struct range_list * rl)745 sval_t rl_min(struct range_list *rl)
746 {
747 	struct data_range *drange;
748 	sval_t ret;
749 
750 	ret.type = &llong_ctype;
751 	ret.value = LLONG_MIN;
752 	if (ptr_list_empty((struct ptr_list *)rl))
753 		return ret;
754 	drange = first_ptr_list((struct ptr_list *)rl);
755 	return drange->min;
756 }
757 
rl_max(struct range_list * rl)758 sval_t rl_max(struct range_list *rl)
759 {
760 	struct data_range *drange;
761 	sval_t ret;
762 
763 	ret.type = &llong_ctype;
764 	ret.value = LLONG_MAX;
765 	if (ptr_list_empty((struct ptr_list *)rl))
766 		return ret;
767 	drange = last_ptr_list((struct ptr_list *)rl);
768 	return drange->max;
769 }
770 
rl_to_sval(struct range_list * rl,sval_t * sval)771 int rl_to_sval(struct range_list *rl, sval_t *sval)
772 {
773 	sval_t min, max;
774 
775 	if (!rl)
776 		return 0;
777 
778 	min = rl_min(rl);
779 	max = rl_max(rl);
780 	if (sval_cmp(min, max) != 0)
781 		return 0;
782 	*sval = min;
783 	return 1;
784 }
785 
rl_type(struct range_list * rl)786 struct symbol *rl_type(struct range_list *rl)
787 {
788 	if (!rl)
789 		return NULL;
790 	return rl_min(rl).type;
791 }
792 
alloc_range_helper_sval(sval_t min,sval_t max,int perm)793 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
794 {
795 	struct data_range *ret;
796 
797 	if (perm)
798 		ret = __alloc_perm_data_range(0);
799 	else
800 		ret = __alloc_data_range(0);
801 	ret->min = min;
802 	ret->max = max;
803 	return ret;
804 }
805 
alloc_range(sval_t min,sval_t max)806 struct data_range *alloc_range(sval_t min, sval_t max)
807 {
808 	return alloc_range_helper_sval(min, max, 0);
809 }
810 
alloc_range_perm(sval_t min,sval_t max)811 struct data_range *alloc_range_perm(sval_t min, sval_t max)
812 {
813 	return alloc_range_helper_sval(min, max, 1);
814 }
815 
alloc_rl(sval_t min,sval_t max)816 struct range_list *alloc_rl(sval_t min, sval_t max)
817 {
818 	struct range_list *rl = NULL;
819 
820 	if (sval_cmp(min, max) > 0)
821 		return alloc_whole_rl(min.type);
822 
823 	add_range(&rl, min, max);
824 	return rl;
825 }
826 
alloc_whole_rl(struct symbol * type)827 struct range_list *alloc_whole_rl(struct symbol *type)
828 {
829 	if (!type || type_positive_bits(type) < 0)
830 		type = &llong_ctype;
831 	if (type->type == SYM_ARRAY)
832 		type = &ptr_ctype;
833 
834 	return alloc_rl(sval_type_min(type), sval_type_max(type));
835 }
836 
collapse_pointer_rl(struct range_list ** rl,sval_t min,sval_t max)837 static bool collapse_pointer_rl(struct range_list **rl, sval_t min, sval_t max)
838 {
839 	struct range_list *new_rl = NULL;
840 	struct data_range *tmp;
841 	static bool recurse;
842 	bool ret = false;
843 	int cnt = 0;
844 
845 	/*
846 	 * With the mtag work, then we end up getting huge lists of mtags.
847 	 * That seems cool, but the problem is that we can only store about
848 	 * 8-10 mtags in the DB before we truncate the list.  Also the mtags
849 	 * aren't really used at all so it's a waste of resources for now...
850 	 * In the future, we maybe will revisit this code.
851 	 *
852 	 */
853 
854 	if (recurse)
855 		return false;
856 	recurse = true;
857 	if (!type_is_ptr(min.type))
858 		goto out;
859 
860 	if (ptr_list_size((struct ptr_list *)*rl) < 8)
861 		goto out;
862 	FOR_EACH_PTR(*rl, tmp) {
863 		if (!is_err_ptr(tmp->min))
864 			cnt++;
865 	} END_FOR_EACH_PTR(tmp);
866 	if (cnt < 8)
867 		goto out;
868 
869 	FOR_EACH_PTR(*rl, tmp) {
870 		if (sval_cmp(tmp->min, valid_ptr_min_sval) >= 0 &&
871 		    sval_cmp(tmp->max, valid_ptr_max_sval) <= 0)
872 			add_range(&new_rl, valid_ptr_min_sval, valid_ptr_max_sval);
873 		else
874 			add_range(&new_rl, tmp->min, tmp->max);
875 	} END_FOR_EACH_PTR(tmp);
876 
877 	add_range(&new_rl, min, max);
878 
879 	*rl = new_rl;
880 	ret = true;
881 out:
882 	recurse = false;
883 	return ret;
884 }
885 
886 extern int rl_ptrlist_hack;
add_range(struct range_list ** list,sval_t min,sval_t max)887 void add_range(struct range_list **list, sval_t min, sval_t max)
888 {
889 	struct data_range *tmp;
890 	struct data_range *new = NULL;
891 	int check_next = 0;
892 
893 	/*
894 	 * There is at least on valid reason why the types might be confusing
895 	 * and that's when you have a void pointer and on some paths you treat
896 	 * it as a u8 pointer and on other paths you treat it as a u16 pointer.
897 	 * This case is hard to deal with.
898 	 *
899 	 * There are other cases where we probably should be more specific about
900 	 * the types than we are.  For example, we end up merging a lot of ulong
901 	 * with pointers and I have not figured out why we do that.
902 	 *
903 	 * But this hack works for both cases, I think.  We cast it to pointers
904 	 * or we use the bigger size.
905 	 *
906 	 */
907 	if (*list && rl_type(*list) != min.type) {
908 		if (rl_type(*list)->type == SYM_PTR) {
909 			min = sval_cast(rl_type(*list), min);
910 			max = sval_cast(rl_type(*list), max);
911 		} else if (min.type->type == SYM_PTR) {
912 			*list = cast_rl(min.type, *list);
913 		} else if (type_bits(rl_type(*list)) >= type_bits(min.type)) {
914 			min = sval_cast(rl_type(*list), min);
915 			max = sval_cast(rl_type(*list), max);
916 		} else {
917 			*list = cast_rl(min.type, *list);
918 		}
919 	}
920 
921 	if (sval_cmp(min, max) > 0) {
922 		min = sval_type_min(min.type);
923 		max = sval_type_max(min.type);
924 	}
925 
926 	if (collapse_pointer_rl(list, min, max))
927 		return;
928 
929 	/*
930 	 * FIXME:  This has a problem merging a range_list like: min-0,3-max
931 	 * with a range like 1-2.  You end up with min-2,3-max instead of
932 	 * just min-max.
933 	 */
934 	FOR_EACH_PTR(*list, tmp) {
935 		if (check_next) {
936 			/* Sometimes we overlap with more than one range
937 			   so we have to delete or modify the next range. */
938 			if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
939 				/* join 2 ranges here */
940 				new->max = tmp->max;
941 				DELETE_CURRENT_PTR(tmp);
942 				return;
943 			}
944 
945 			/* Doesn't overlap with the next one. */
946 			if (sval_cmp(max, tmp->min) < 0)
947 				return;
948 
949 			if (sval_cmp(max, tmp->max) <= 0) {
950 				/* Partially overlaps the next one. */
951 				new->max = tmp->max;
952 				DELETE_CURRENT_PTR(tmp);
953 				return;
954 			} else {
955 				/* Completely overlaps the next one. */
956 				DELETE_CURRENT_PTR(tmp);
957 				/* there could be more ranges to delete */
958 				continue;
959 			}
960 		}
961 		if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
962 			/* join 2 ranges into a big range */
963 			new = alloc_range(min, tmp->max);
964 			REPLACE_CURRENT_PTR(tmp, new);
965 			return;
966 		}
967 		if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
968 			new = alloc_range(min, max);
969 			INSERT_CURRENT(new, tmp);
970 			return;
971 		}
972 		if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
973 			if (sval_cmp(max, tmp->max) < 0)
974 				max = tmp->max;
975 			else
976 				check_next = 1;
977 			new = alloc_range(min, max);
978 			REPLACE_CURRENT_PTR(tmp, new);
979 			if (!check_next)
980 				return;
981 			continue;
982 		}
983 		if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
984 			return;
985 		if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
986 			min = tmp->min;
987 			new = alloc_range(min, max);
988 			REPLACE_CURRENT_PTR(tmp, new);
989 			check_next = 1;
990 			continue;
991 		}
992 		if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
993 			/* join 2 ranges into a big range */
994 			new = alloc_range(tmp->min, max);
995 			REPLACE_CURRENT_PTR(tmp, new);
996 			check_next = 1;
997 			continue;
998 		}
999 		/* the new range is entirely above the existing ranges */
1000 	} END_FOR_EACH_PTR(tmp);
1001 	if (check_next)
1002 		return;
1003 	new = alloc_range(min, max);
1004 
1005 	rl_ptrlist_hack = 1;
1006 	add_ptr_list(list, new);
1007 	rl_ptrlist_hack = 0;
1008 }
1009 
clone_rl(struct range_list * list)1010 struct range_list *clone_rl(struct range_list *list)
1011 {
1012 	struct data_range *tmp;
1013 	struct range_list *ret = NULL;
1014 
1015 	FOR_EACH_PTR(list, tmp) {
1016 		add_ptr_list(&ret, tmp);
1017 	} END_FOR_EACH_PTR(tmp);
1018 	return ret;
1019 }
1020 
clone_rl_permanent(struct range_list * list)1021 struct range_list *clone_rl_permanent(struct range_list *list)
1022 {
1023 	struct data_range *tmp;
1024 	struct data_range *new;
1025 	struct range_list *ret = NULL;
1026 
1027 	FOR_EACH_PTR(list, tmp) {
1028 		new = alloc_range_perm(tmp->min, tmp->max);
1029 		add_ptr_list(&ret, new);
1030 	} END_FOR_EACH_PTR(tmp);
1031 	return ret;
1032 }
1033 
rl_union(struct range_list * one,struct range_list * two)1034 struct range_list *rl_union(struct range_list *one, struct range_list *two)
1035 {
1036 	struct data_range *tmp;
1037 	struct range_list *ret = NULL;
1038 
1039 	FOR_EACH_PTR(one, tmp) {
1040 		add_range(&ret, tmp->min, tmp->max);
1041 	} END_FOR_EACH_PTR(tmp);
1042 	FOR_EACH_PTR(two, tmp) {
1043 		add_range(&ret, tmp->min, tmp->max);
1044 	} END_FOR_EACH_PTR(tmp);
1045 	return ret;
1046 }
1047 
remove_range(struct range_list * list,sval_t min,sval_t max)1048 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
1049 {
1050 	struct data_range *tmp;
1051 	struct range_list *ret = NULL;
1052 
1053 	if (!list)
1054 		return NULL;
1055 
1056 	min = sval_cast(rl_type(list), min);
1057 	max = sval_cast(rl_type(list), max);
1058 	if (sval_cmp(min, max) > 0) {
1059 		sval_t tmp = min;
1060 		min = max;
1061 		max = tmp;
1062 	}
1063 
1064 	FOR_EACH_PTR(list, tmp) {
1065 		if (sval_cmp(tmp->max, min) < 0) {
1066 			add_range(&ret, tmp->min, tmp->max);
1067 			continue;
1068 		}
1069 		if (sval_cmp(tmp->min, max) > 0) {
1070 			add_range(&ret, tmp->min, tmp->max);
1071 			continue;
1072 		}
1073 		if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
1074 			continue;
1075 		if (sval_cmp(tmp->min, min) >= 0) {
1076 			max.value++;
1077 			add_range(&ret, max, tmp->max);
1078 		} else if (sval_cmp(tmp->max, max) <= 0) {
1079 			min.value--;
1080 			add_range(&ret, tmp->min, min);
1081 		} else {
1082 			min.value--;
1083 			max.value++;
1084 			add_range(&ret, tmp->min, min);
1085 			add_range(&ret, max, tmp->max);
1086 		}
1087 	} END_FOR_EACH_PTR(tmp);
1088 	return ret;
1089 }
1090 
ranges_equiv(struct data_range * one,struct data_range * two)1091 int ranges_equiv(struct data_range *one, struct data_range *two)
1092 {
1093 	if (!one && !two)
1094 		return 1;
1095 	if (!one || !two)
1096 		return 0;
1097 	if (sval_cmp(one->min, two->min) != 0)
1098 		return 0;
1099 	if (sval_cmp(one->max, two->max) != 0)
1100 		return 0;
1101 	return 1;
1102 }
1103 
rl_equiv(struct range_list * one,struct range_list * two)1104 int rl_equiv(struct range_list *one, struct range_list *two)
1105 {
1106 	struct data_range *one_range;
1107 	struct data_range *two_range;
1108 
1109 	if (one == two)
1110 		return 1;
1111 
1112 	PREPARE_PTR_LIST(one, one_range);
1113 	PREPARE_PTR_LIST(two, two_range);
1114 	for (;;) {
1115 		if (!one_range && !two_range)
1116 			return 1;
1117 		if (!ranges_equiv(one_range, two_range))
1118 			return 0;
1119 		NEXT_PTR_LIST(one_range);
1120 		NEXT_PTR_LIST(two_range);
1121 	}
1122 	FINISH_PTR_LIST(two_range);
1123 	FINISH_PTR_LIST(one_range);
1124 
1125 	return 1;
1126 }
1127 
true_comparison_range(struct data_range * left,int comparison,struct data_range * right)1128 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
1129 {
1130 	switch (comparison) {
1131 	case '<':
1132 	case SPECIAL_UNSIGNED_LT:
1133 		if (sval_cmp(left->min, right->max) < 0)
1134 			return 1;
1135 		return 0;
1136 	case SPECIAL_UNSIGNED_LTE:
1137 	case SPECIAL_LTE:
1138 		if (sval_cmp(left->min, right->max) <= 0)
1139 			return 1;
1140 		return 0;
1141 	case SPECIAL_EQUAL:
1142 		if (sval_cmp(left->max, right->min) < 0)
1143 			return 0;
1144 		if (sval_cmp(left->min, right->max) > 0)
1145 			return 0;
1146 		return 1;
1147 	case SPECIAL_UNSIGNED_GTE:
1148 	case SPECIAL_GTE:
1149 		if (sval_cmp(left->max, right->min) >= 0)
1150 			return 1;
1151 		return 0;
1152 	case '>':
1153 	case SPECIAL_UNSIGNED_GT:
1154 		if (sval_cmp(left->max, right->min) > 0)
1155 			return 1;
1156 		return 0;
1157 	case SPECIAL_NOTEQUAL:
1158 		if (sval_cmp(left->min, left->max) != 0)
1159 			return 1;
1160 		if (sval_cmp(right->min, right->max) != 0)
1161 			return 1;
1162 		if (sval_cmp(left->min, right->min) != 0)
1163 			return 1;
1164 		return 0;
1165 	default:
1166 		sm_perror("unhandled comparison %d", comparison);
1167 		return 0;
1168 	}
1169 	return 0;
1170 }
1171 
true_comparison_range_LR(int comparison,struct data_range * var,struct data_range * val,int left)1172 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1173 {
1174 	if (left)
1175 		return true_comparison_range(var, comparison, val);
1176 	else
1177 		return true_comparison_range(val, comparison, var);
1178 }
1179 
false_comparison_range_sval(struct data_range * left,int comparison,struct data_range * right)1180 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
1181 {
1182 	switch (comparison) {
1183 	case '<':
1184 	case SPECIAL_UNSIGNED_LT:
1185 		if (sval_cmp(left->max, right->min) >= 0)
1186 			return 1;
1187 		return 0;
1188 	case SPECIAL_UNSIGNED_LTE:
1189 	case SPECIAL_LTE:
1190 		if (sval_cmp(left->max, right->min) > 0)
1191 			return 1;
1192 		return 0;
1193 	case SPECIAL_EQUAL:
1194 		if (sval_cmp(left->min, left->max) != 0)
1195 			return 1;
1196 		if (sval_cmp(right->min, right->max) != 0)
1197 			return 1;
1198 		if (sval_cmp(left->min, right->min) != 0)
1199 			return 1;
1200 		return 0;
1201 	case SPECIAL_UNSIGNED_GTE:
1202 	case SPECIAL_GTE:
1203 		if (sval_cmp(left->min, right->max) < 0)
1204 			return 1;
1205 		return 0;
1206 	case '>':
1207 	case SPECIAL_UNSIGNED_GT:
1208 		if (sval_cmp(left->min, right->max) <= 0)
1209 			return 1;
1210 		return 0;
1211 	case SPECIAL_NOTEQUAL:
1212 		if (sval_cmp(left->max, right->min) < 0)
1213 			return 0;
1214 		if (sval_cmp(left->min, right->max) > 0)
1215 			return 0;
1216 		return 1;
1217 	default:
1218 		sm_perror("unhandled comparison %d", comparison);
1219 		return 0;
1220 	}
1221 	return 0;
1222 }
1223 
false_comparison_range_LR(int comparison,struct data_range * var,struct data_range * val,int left)1224 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1225 {
1226 	if (left)
1227 		return false_comparison_range_sval(var, comparison, val);
1228 	else
1229 		return false_comparison_range_sval(val, comparison, var);
1230 }
1231 
possibly_true(struct expression * left,int comparison,struct expression * right)1232 int possibly_true(struct expression *left, int comparison, struct expression *right)
1233 {
1234 	struct range_list *rl_left, *rl_right;
1235 	struct data_range *tmp_left, *tmp_right;
1236 	struct symbol *type;
1237 
1238 	if (comparison == UNKNOWN_COMPARISON)
1239 		return 1;
1240 	if (!get_implied_rl(left, &rl_left))
1241 		return 1;
1242 	if (!get_implied_rl(right, &rl_right))
1243 		return 1;
1244 
1245 	type = rl_type(rl_left);
1246 	if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1247 		type = rl_type(rl_right);
1248 	if (type_positive_bits(type) < 31)
1249 		type = &int_ctype;
1250 
1251 	rl_left = cast_rl(type, rl_left);
1252 	rl_right = cast_rl(type, rl_right);
1253 
1254 	FOR_EACH_PTR(rl_left, tmp_left) {
1255 		FOR_EACH_PTR(rl_right, tmp_right) {
1256 			if (true_comparison_range(tmp_left, comparison, tmp_right))
1257 				return 1;
1258 		} END_FOR_EACH_PTR(tmp_right);
1259 	} END_FOR_EACH_PTR(tmp_left);
1260 	return 0;
1261 }
1262 
possibly_false(struct expression * left,int comparison,struct expression * right)1263 int possibly_false(struct expression *left, int comparison, struct expression *right)
1264 {
1265 	struct range_list *rl_left, *rl_right;
1266 	struct data_range *tmp_left, *tmp_right;
1267 	struct symbol *type;
1268 
1269 	if (!get_implied_rl(left, &rl_left))
1270 		return 1;
1271 	if (!get_implied_rl(right, &rl_right))
1272 		return 1;
1273 
1274 	type = rl_type(rl_left);
1275 	if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1276 		type = rl_type(rl_right);
1277 	if (type_positive_bits(type) < 31)
1278 		type = &int_ctype;
1279 
1280 	rl_left = cast_rl(type, rl_left);
1281 	rl_right = cast_rl(type, rl_right);
1282 
1283 	FOR_EACH_PTR(rl_left, tmp_left) {
1284 		FOR_EACH_PTR(rl_right, tmp_right) {
1285 			if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1286 				return 1;
1287 		} END_FOR_EACH_PTR(tmp_right);
1288 	} END_FOR_EACH_PTR(tmp_left);
1289 	return 0;
1290 }
1291 
possibly_true_rl(struct range_list * left_ranges,int comparison,struct range_list * right_ranges)1292 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1293 {
1294 	struct data_range *left_tmp, *right_tmp;
1295 	struct symbol *type;
1296 
1297 	if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1298 		return 1;
1299 
1300 	type = rl_type(left_ranges);
1301 	if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1302 		type = rl_type(right_ranges);
1303 	if (type_positive_bits(type) < 31)
1304 		type = &int_ctype;
1305 
1306 	left_ranges = cast_rl(type, left_ranges);
1307 	right_ranges = cast_rl(type, right_ranges);
1308 
1309 	FOR_EACH_PTR(left_ranges, left_tmp) {
1310 		FOR_EACH_PTR(right_ranges, right_tmp) {
1311 			if (true_comparison_range(left_tmp, comparison, right_tmp))
1312 				return 1;
1313 		} END_FOR_EACH_PTR(right_tmp);
1314 	} END_FOR_EACH_PTR(left_tmp);
1315 	return 0;
1316 }
1317 
possibly_false_rl(struct range_list * left_ranges,int comparison,struct range_list * right_ranges)1318 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1319 {
1320 	struct data_range *left_tmp, *right_tmp;
1321 	struct symbol *type;
1322 
1323 	if (!left_ranges || !right_ranges || comparison == UNKNOWN_COMPARISON)
1324 		return 1;
1325 
1326 	type = rl_type(left_ranges);
1327 	if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1328 		type = rl_type(right_ranges);
1329 	if (type_positive_bits(type) < 31)
1330 		type = &int_ctype;
1331 
1332 	left_ranges = cast_rl(type, left_ranges);
1333 	right_ranges = cast_rl(type, right_ranges);
1334 
1335 	FOR_EACH_PTR(left_ranges, left_tmp) {
1336 		FOR_EACH_PTR(right_ranges, right_tmp) {
1337 			if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1338 				return 1;
1339 		} END_FOR_EACH_PTR(right_tmp);
1340 	} END_FOR_EACH_PTR(left_tmp);
1341 	return 0;
1342 }
1343 
1344 /* FIXME: the _rl here stands for right left so really it should be _lr */
possibly_true_rl_LR(int comparison,struct range_list * a,struct range_list * b,int left)1345 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1346 {
1347 	if (left)
1348 		return possibly_true_rl(a, comparison, b);
1349 	else
1350 		return possibly_true_rl(b, comparison, a);
1351 }
1352 
possibly_false_rl_LR(int comparison,struct range_list * a,struct range_list * b,int left)1353 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1354 {
1355 	if (left)
1356 		return possibly_false_rl(a, comparison, b);
1357 	else
1358 		return possibly_false_rl(b, comparison, a);
1359 }
1360 
rl_has_sval(struct range_list * rl,sval_t sval)1361 int rl_has_sval(struct range_list *rl, sval_t sval)
1362 {
1363 	struct data_range *tmp;
1364 
1365 	FOR_EACH_PTR(rl, tmp) {
1366 		if (sval_cmp(tmp->min, sval) <= 0 &&
1367 		    sval_cmp(tmp->max, sval) >= 0)
1368 			return 1;
1369 	} END_FOR_EACH_PTR(tmp);
1370 	return 0;
1371 }
1372 
tack_on(struct range_list ** list,struct data_range * drange)1373 void tack_on(struct range_list **list, struct data_range *drange)
1374 {
1375 	add_ptr_list(list, drange);
1376 }
1377 
push_rl(struct range_list_stack ** rl_stack,struct range_list * rl)1378 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1379 {
1380 	add_ptr_list(rl_stack, rl);
1381 }
1382 
pop_rl(struct range_list_stack ** rl_stack)1383 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1384 {
1385 	struct range_list *rl;
1386 
1387 	rl = last_ptr_list((struct ptr_list *)*rl_stack);
1388 	delete_ptr_list_last((struct ptr_list **)rl_stack);
1389 	return rl;
1390 }
1391 
top_rl(struct range_list_stack * rl_stack)1392 struct range_list *top_rl(struct range_list_stack *rl_stack)
1393 {
1394 	struct range_list *rl;
1395 
1396 	rl = last_ptr_list((struct ptr_list *)rl_stack);
1397 	return rl;
1398 }
1399 
filter_top_rl(struct range_list_stack ** rl_stack,struct range_list * filter)1400 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1401 {
1402 	struct range_list *rl;
1403 
1404 	rl = pop_rl(rl_stack);
1405 	rl = rl_filter(rl, filter);
1406 	push_rl(rl_stack, rl);
1407 }
1408 
rl_truncate_cast(struct symbol * type,struct range_list * rl)1409 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1410 {
1411 	struct data_range *tmp;
1412 	struct range_list *ret = NULL;
1413 	sval_t min, max;
1414 
1415 	if (!rl)
1416 		return NULL;
1417 
1418 	if (!type || type == rl_type(rl))
1419 		return rl;
1420 
1421 	FOR_EACH_PTR(rl, tmp) {
1422 		min = tmp->min;
1423 		max = tmp->max;
1424 		if (type_bits(type) < type_bits(rl_type(rl))) {
1425 			min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1426 			max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1427 		}
1428 		if (sval_cmp(min, max) > 0) {
1429 			min = sval_cast(type, min);
1430 			max = sval_cast(type, max);
1431 		}
1432 		add_range_t(type, &ret, min, max);
1433 	} END_FOR_EACH_PTR(tmp);
1434 
1435 	return ret;
1436 }
1437 
rl_fits_in_type(struct range_list * rl,struct symbol * type)1438 int rl_fits_in_type(struct range_list *rl, struct symbol *type)
1439 {
1440 	if (type_bits(rl_type(rl)) <= type_bits(type))
1441 		return 1;
1442 	if (sval_cmp(rl_max(rl), sval_type_max(type)) > 0)
1443 		return 0;
1444 	if (sval_is_negative(rl_min(rl)) &&
1445 	    sval_cmp(rl_min(rl), sval_type_min(type)) < 0)
1446 		return 0;
1447 	return 1;
1448 }
1449 
rl_type_consistent(struct range_list * rl)1450 static int rl_type_consistent(struct range_list *rl)
1451 {
1452 	struct data_range *tmp;
1453 	struct symbol *type;
1454 
1455 	type = rl_type(rl);
1456 	FOR_EACH_PTR(rl, tmp) {
1457 		if (type != tmp->min.type || type != tmp->max.type)
1458 			return 0;
1459 	} END_FOR_EACH_PTR(tmp);
1460 	return 1;
1461 }
1462 
cast_to_bool(struct range_list * rl)1463 static struct range_list *cast_to_bool(struct range_list *rl)
1464 {
1465 	struct data_range *tmp;
1466 	struct range_list *ret = NULL;
1467 	int has_one = 0;
1468 	int has_zero = 0;
1469 	sval_t min = { .type = &bool_ctype };
1470 	sval_t max = { .type = &bool_ctype };
1471 
1472 	FOR_EACH_PTR(rl, tmp) {
1473 		if (tmp->min.value || tmp->max.value)
1474 			has_one = 1;
1475 		if (sval_is_negative(tmp->min) &&
1476 		    sval_is_negative(tmp->max))
1477 			continue;
1478 		if (tmp->min.value == 0 ||
1479 		    tmp->max.value == 0)
1480 			has_zero = 1;
1481 		if (sval_is_negative(tmp->min) &&
1482 		    tmp->max.value > 0)
1483 			has_zero = 1;
1484 	} END_FOR_EACH_PTR(tmp);
1485 
1486 	if (!has_zero)
1487 		min.value = 1;
1488 	if (has_one)
1489 		max.value = 1;
1490 
1491 	add_range(&ret, min, max);
1492 	return ret;
1493 }
1494 
cast_rl(struct symbol * type,struct range_list * rl)1495 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1496 {
1497 	struct data_range *tmp;
1498 	struct range_list *ret = NULL;
1499 
1500 	if (!rl)
1501 		return NULL;
1502 
1503 	if (!type)
1504 		return rl;
1505 	if (!rl_is_sane(rl))
1506 		return alloc_whole_rl(type);
1507 	if (type == rl_type(rl) && rl_type_consistent(rl))
1508 		return rl;
1509 
1510 	if (type == &bool_ctype)
1511 		return cast_to_bool(rl);
1512 
1513 	FOR_EACH_PTR(rl, tmp) {
1514 		add_range_t(type, &ret, tmp->min, tmp->max);
1515 	} END_FOR_EACH_PTR(tmp);
1516 
1517 	if (!ret)
1518 		return alloc_whole_rl(type);
1519 
1520 	return ret;
1521 }
1522 
rl_filter(struct range_list * rl,struct range_list * filter)1523 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1524 {
1525 	struct data_range *tmp;
1526 
1527 	FOR_EACH_PTR(filter, tmp) {
1528 		rl = remove_range(rl, tmp->min, tmp->max);
1529 	} END_FOR_EACH_PTR(tmp);
1530 
1531 	return rl;
1532 }
1533 
do_intersection(struct range_list * one_rl,struct range_list * two_rl)1534 struct range_list *do_intersection(struct range_list *one_rl, struct range_list *two_rl)
1535 {
1536 	struct data_range *one, *two;
1537 	struct range_list *ret = NULL;
1538 
1539 
1540 	PREPARE_PTR_LIST(one_rl, one);
1541 	PREPARE_PTR_LIST(two_rl, two);
1542 
1543 	while (true) {
1544 		if (!one || !two)
1545 			break;
1546 		if (sval_cmp(one->max, two->min) < 0) {
1547 			NEXT_PTR_LIST(one);
1548 			continue;
1549 		}
1550 		if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) <= 0) {
1551 			add_range(&ret, two->min, one->max);
1552 			NEXT_PTR_LIST(one);
1553 			continue;
1554 		}
1555 		if (sval_cmp(one->min, two->min) >= 0 && sval_cmp(one->max, two->max) <= 0) {
1556 			add_range(&ret, one->min, one->max);
1557 			NEXT_PTR_LIST(one);
1558 			continue;
1559 		}
1560 		if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) > 0) {
1561 			add_range(&ret, two->min, two->max);
1562 			NEXT_PTR_LIST(two);
1563 			continue;
1564 		}
1565 		if (sval_cmp(one->min, two->max) <= 0 && sval_cmp(one->max, two->max) > 0) {
1566 			add_range(&ret, one->min, two->max);
1567 			NEXT_PTR_LIST(two);
1568 			continue;
1569 		}
1570 		if (sval_cmp(one->min, two->max) <= 0) {
1571 			sm_fatal("error calculating intersection of '%s' and '%s'", show_rl(one_rl), show_rl(two_rl));
1572 			return NULL;
1573 		}
1574 		NEXT_PTR_LIST(two);
1575 	}
1576 
1577 	FINISH_PTR_LIST(two);
1578 	FINISH_PTR_LIST(one);
1579 
1580 	return ret;
1581 }
1582 
rl_intersection(struct range_list * one,struct range_list * two)1583 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1584 {
1585 	struct range_list *ret;
1586 	struct symbol *ret_type;
1587 	struct symbol *small_type;
1588 	struct symbol *large_type;
1589 
1590 	if (!one || !two)
1591 		return NULL;
1592 
1593 	ret_type = rl_type(one);
1594 	small_type = rl_type(one);
1595 	large_type = rl_type(two);
1596 
1597 	if (type_bits(rl_type(two)) < type_bits(small_type)) {
1598 		small_type = rl_type(two);
1599 		large_type = rl_type(one);
1600 	}
1601 
1602 	one = cast_rl(large_type, one);
1603 	two = cast_rl(large_type, two);
1604 
1605 	ret = do_intersection(one, two);
1606 	return cast_rl(ret_type, ret);
1607 }
1608 
handle_mod_rl(struct range_list * left,struct range_list * right)1609 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1610 {
1611 	sval_t zero;
1612 	sval_t max;
1613 
1614 	max = rl_max(right);
1615 	if (sval_is_max(max))
1616 		return left;
1617 	if (max.value == 0)
1618 		return NULL;
1619 	max.value--;
1620 	if (sval_is_negative(max))
1621 		return NULL;
1622 	if (sval_cmp(rl_max(left), max) < 0)
1623 		return left;
1624 	zero = max;
1625 	zero.value = 0;
1626 	return alloc_rl(zero, max);
1627 }
1628 
get_neg_rl(struct range_list * rl)1629 static struct range_list *get_neg_rl(struct range_list *rl)
1630 {
1631 	struct data_range *tmp;
1632 	struct data_range *new;
1633 	struct range_list *ret = NULL;
1634 
1635 	if (!rl)
1636 		return NULL;
1637 	if (sval_is_positive(rl_min(rl)))
1638 		return NULL;
1639 
1640 	FOR_EACH_PTR(rl, tmp) {
1641 		if (sval_is_positive(tmp->min))
1642 			break;
1643 		if (sval_is_positive(tmp->max)) {
1644 			new = alloc_range(tmp->min, tmp->max);
1645 			new->max.value = -1;
1646 			add_range(&ret, new->min, new->max);
1647 			break;
1648 		}
1649 		add_range(&ret, tmp->min, tmp->max);
1650 	} END_FOR_EACH_PTR(tmp);
1651 
1652 	return ret;
1653 }
1654 
get_pos_rl(struct range_list * rl)1655 static struct range_list *get_pos_rl(struct range_list *rl)
1656 {
1657 	struct data_range *tmp;
1658 	struct data_range *new;
1659 	struct range_list *ret = NULL;
1660 
1661 	if (!rl)
1662 		return NULL;
1663 	if (sval_is_negative(rl_max(rl)))
1664 		return NULL;
1665 
1666 	FOR_EACH_PTR(rl, tmp) {
1667 		if (sval_is_negative(tmp->max))
1668 			continue;
1669 		if (sval_is_positive(tmp->min)) {
1670 			add_range(&ret, tmp->min, tmp->max);
1671 			continue;
1672 		}
1673 		new = alloc_range(tmp->min, tmp->max);
1674 		new->min.value = 0;
1675 		add_range(&ret, new->min, new->max);
1676 	} END_FOR_EACH_PTR(tmp);
1677 
1678 	return ret;
1679 }
1680 
divide_rl_helper(struct range_list * left,struct range_list * right)1681 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1682 {
1683 	sval_t right_min, right_max;
1684 	sval_t min, max;
1685 
1686 	if (!left || !right)
1687 		return NULL;
1688 
1689 	/* let's assume we never divide by zero */
1690 	right_min = rl_min(right);
1691 	right_max = rl_max(right);
1692 	if (right_min.value == 0 && right_max.value == 0)
1693 		return NULL;
1694 	if (right_min.value == 0)
1695 		right_min.value = 1;
1696 	if (right_max.value == 0)
1697 		right_max.value = -1;
1698 
1699 	max = sval_binop(rl_max(left), '/', right_min);
1700 	min = sval_binop(rl_min(left), '/', right_max);
1701 
1702 	return alloc_rl(min, max);
1703 }
1704 
handle_divide_rl(struct range_list * left,struct range_list * right)1705 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1706 {
1707 	struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1708 	struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1709 	struct range_list *ret;
1710 
1711 	if (is_whole_rl(right))
1712 		return NULL;
1713 
1714 	left_neg = get_neg_rl(left);
1715 	left_pos = get_pos_rl(left);
1716 	right_neg = get_neg_rl(right);
1717 	right_pos = get_pos_rl(right);
1718 
1719 	neg_neg = divide_rl_helper(left_neg, right_neg);
1720 	neg_pos = divide_rl_helper(left_neg, right_pos);
1721 	pos_neg = divide_rl_helper(left_pos, right_neg);
1722 	pos_pos = divide_rl_helper(left_pos, right_pos);
1723 
1724 	ret = rl_union(neg_neg, neg_pos);
1725 	ret = rl_union(ret, pos_neg);
1726 	return rl_union(ret, pos_pos);
1727 }
1728 
ptr_add_mult(struct range_list * left,int op,struct range_list * right)1729 static struct range_list *ptr_add_mult(struct range_list *left, int op, struct range_list *right)
1730 {
1731 	struct range_list *ret;
1732 	sval_t l_sval, r_sval, res;
1733 
1734 	/*
1735 	 * This function is sort of the wrong API because it takes two pointer
1736 	 * and adds them together.  The caller is expected to figure out
1737 	 * alignment.  Neither of those are the correct things to do.
1738 	 *
1739 	 * Really this function is quite bogus...
1740 	 */
1741 
1742 	if (rl_to_sval(left, &l_sval) && rl_to_sval(right, &r_sval)) {
1743 		res = sval_binop(l_sval, op, r_sval);
1744 		return alloc_rl(res, res);
1745 	}
1746 
1747 	if (rl_min(left).value != 0 || rl_max(right).value != 0) {
1748 		ret = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1749 		return cast_rl(rl_type(left), ret);
1750 	}
1751 
1752 	return alloc_whole_rl(rl_type(left));
1753 }
1754 
handle_add_mult_rl(struct range_list * left,int op,struct range_list * right)1755 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1756 {
1757 	sval_t min, max;
1758 
1759 	if (type_is_ptr(rl_type(left)) || type_is_ptr(rl_type(right)))
1760 		return ptr_add_mult(left, op, right);
1761 
1762 	if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1763 		return NULL;
1764 	min = sval_binop(rl_min(left), op, rl_min(right));
1765 
1766 	if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1767 		return NULL;
1768 	max = sval_binop(rl_max(left), op, rl_max(right));
1769 
1770 	return alloc_rl(min, max);
1771 }
1772 
handle_sub_rl(struct range_list * left_orig,struct range_list * right_orig)1773 static struct range_list *handle_sub_rl(struct range_list *left_orig, struct range_list *right_orig)
1774 {
1775 	struct range_list *left_rl, *right_rl;
1776 	struct symbol *type;
1777 	sval_t min, max;
1778 	sval_t min_ll, max_ll, res_ll;
1779 	sval_t tmp;
1780 
1781 	/* TODO:  These things should totally be using dranges where possible */
1782 
1783 	if (!left_orig || !right_orig)
1784 		return NULL;
1785 
1786 	type = &int_ctype;
1787 	if (type_positive_bits(rl_type(left_orig)) > type_positive_bits(type))
1788 		type = rl_type(left_orig);
1789 	if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
1790 		type = rl_type(right_orig);
1791 
1792 	left_rl = cast_rl(type, left_orig);
1793 	right_rl = cast_rl(type, right_orig);
1794 
1795 	max = rl_max(left_rl);
1796 	min = sval_type_min(type);
1797 
1798 	min_ll = rl_min(left_rl);
1799 	min_ll.type = &llong_ctype;
1800 	max_ll = rl_max(right_rl);
1801 	max_ll.type = &llong_ctype;
1802 	res_ll = min_ll;
1803 	res_ll.value = min_ll.value - max_ll.value;
1804 
1805 	if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
1806 		tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
1807 		if (sval_cmp(tmp, min) > 0)
1808 			min = tmp;
1809 	} else if (type_positive_bits(type) < 63 &&
1810 		   !sval_binop_overflows(min_ll, '-', max_ll) &&
1811 		   (min.value != 0 && sval_cmp(res_ll, min) >= 0)) {
1812 		struct range_list *left_casted, *right_casted, *result;
1813 
1814 		left_casted = cast_rl(&llong_ctype, left_orig);
1815 		right_casted = cast_rl(&llong_ctype, right_orig);
1816 		result = handle_sub_rl(left_casted, right_casted);
1817 		return cast_rl(type, result);
1818 	}
1819 
1820 	if (!sval_is_max(rl_max(left_rl))) {
1821 		tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
1822 		if (sval_cmp(tmp, max) < 0)
1823 			max = tmp;
1824 	}
1825 
1826 	if (sval_is_min(min) && sval_is_max(max))
1827 		return NULL;
1828 
1829 	return alloc_rl(min, max);
1830 }
1831 
rl_bits_always_set(struct range_list * rl)1832 static unsigned long long rl_bits_always_set(struct range_list *rl)
1833 {
1834 	return sval_fls_mask(rl_min(rl));
1835 }
1836 
rl_bits_maybe_set(struct range_list * rl)1837 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1838 {
1839 	return sval_fls_mask(rl_max(rl));
1840 }
1841 
handle_OR_rl(struct range_list * left,struct range_list * right)1842 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1843 {
1844 	unsigned long long left_min, left_max, right_min, right_max;
1845 	sval_t min, max;
1846 	sval_t sval;
1847 
1848 	if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1849 	    !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1850 		return rl_binop(left, '+', right);
1851 
1852 	left_min = rl_bits_always_set(left);
1853 	left_max = rl_bits_maybe_set(left);
1854 	right_min = rl_bits_always_set(right);
1855 	right_max = rl_bits_maybe_set(right);
1856 
1857 	min.type = max.type = &ullong_ctype;
1858 	min.uvalue = left_min | right_min;
1859 	max.uvalue = left_max | right_max;
1860 
1861 	return cast_rl(rl_type(left), alloc_rl(min, max));
1862 }
1863 
handle_XOR_rl(struct range_list * left,struct range_list * right)1864 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1865 {
1866 	unsigned long long left_set, left_maybe;
1867 	unsigned long long right_set, right_maybe;
1868 	sval_t zero, max;
1869 
1870 	left_set = rl_bits_always_set(left);
1871 	left_maybe = rl_bits_maybe_set(left);
1872 
1873 	right_set = rl_bits_always_set(right);
1874 	right_maybe = rl_bits_maybe_set(right);
1875 
1876 	zero = max = rl_min(left);
1877 	zero.uvalue = 0;
1878 	max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1879 
1880 	return cast_rl(rl_type(left), alloc_rl(zero, max));
1881 }
1882 
sval_lowest_set_bit(sval_t sval)1883 static sval_t sval_lowest_set_bit(sval_t sval)
1884 {
1885 	sval_t ret = { .type = sval.type };
1886 	int i;
1887 
1888 	for (i = 0; i < 64; i++) {
1889 		if (sval.uvalue & 1ULL << i) {
1890 			ret.uvalue = (1ULL << i);
1891 			return ret;
1892 		}
1893 	}
1894 	return ret;
1895 }
1896 
handle_AND_rl(struct range_list * left,struct range_list * right)1897 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1898 {
1899 	struct bit_info *one, *two;
1900 	struct range_list *rl;
1901 	sval_t min, max, zero;
1902 	unsigned long long bits;
1903 
1904 	one = rl_to_binfo(left);
1905 	two = rl_to_binfo(right);
1906 	bits = one->possible & two->possible;
1907 
1908 	max = rl_max(left);
1909 	max.uvalue = bits;
1910 	min = sval_lowest_set_bit(max);
1911 
1912 	rl = alloc_rl(min, max);
1913 
1914 	zero = rl_min(rl);
1915 	zero.value = 0;
1916 	add_range(&rl, zero, zero);
1917 
1918 	return rl;
1919 }
1920 
handle_lshift(struct range_list * left_orig,struct range_list * right_orig)1921 static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
1922 {
1923 	struct range_list *left;
1924 	struct data_range *tmp;
1925 	struct range_list *ret = NULL;
1926 	sval_t zero = { .type = rl_type(left_orig), };
1927 	sval_t shift, min, max;
1928 	bool add_zero = false;
1929 
1930 	if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1931 		return NULL;
1932 	if (shift.value == 0)
1933 		return left_orig;
1934 
1935 	/* Cast to unsigned for easier left shift math */
1936 	if (type_positive_bits(rl_type(left_orig)) < 32)
1937 		left = cast_rl(&uint_ctype, left_orig);
1938 	else if(type_positive_bits(rl_type(left_orig)) == 63)
1939 		left = cast_rl(&ullong_ctype, left_orig);
1940 	else
1941 		left = left_orig;
1942 
1943 	FOR_EACH_PTR(left, tmp) {
1944 		min = tmp->min;
1945 		max = tmp->max;
1946 
1947 		if (min.value == 0 || max.value > sval_type_max(max.type).uvalue >> shift.uvalue)
1948 			add_zero = true;
1949 		if (min.value == 0 && max.value == 0)
1950 			continue;
1951 		if (min.value == 0)
1952 			min.value = 1;
1953 		min = sval_binop(min, SPECIAL_LEFTSHIFT, shift);
1954 		max = sval_binop(max, SPECIAL_LEFTSHIFT, shift);
1955 		add_range(&ret, min, max);
1956 	} END_FOR_EACH_PTR(tmp);
1957 
1958 	if (!rl_fits_in_type(ret, rl_type(left_orig)))
1959 		add_zero = true;
1960 	ret = cast_rl(rl_type(left_orig), ret);
1961 	if (add_zero)
1962 		add_range(&ret, zero, zero);
1963 
1964 	return ret;
1965 }
1966 
handle_rshift(struct range_list * left_orig,struct range_list * right_orig)1967 static struct range_list *handle_rshift(struct range_list *left_orig, struct range_list *right_orig)
1968 {
1969 	struct data_range *tmp;
1970 	struct range_list *ret = NULL;
1971 	sval_t shift, min, max;
1972 
1973 	if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1974 		return NULL;
1975 	if (shift.value == 0)
1976 		return left_orig;
1977 
1978 	FOR_EACH_PTR(left_orig, tmp) {
1979 		min = sval_binop(tmp->min, SPECIAL_RIGHTSHIFT, shift);
1980 		max = sval_binop(tmp->max, SPECIAL_RIGHTSHIFT, shift);
1981 		add_range(&ret, min, max);
1982 	} END_FOR_EACH_PTR(tmp);
1983 
1984 	return ret;
1985 }
1986 
rl_binop(struct range_list * left,int op,struct range_list * right)1987 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1988 {
1989 	struct symbol *cast_type;
1990 	sval_t left_sval, right_sval;
1991 	struct range_list *ret = NULL;
1992 
1993 	cast_type = rl_type(left);
1994 	if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1995 		cast_type = rl_type(right);
1996 	if (sval_type_max(cast_type).uvalue < INT_MAX)
1997 		cast_type = &int_ctype;
1998 
1999 	left = cast_rl(cast_type, left);
2000 	right = cast_rl(cast_type, right);
2001 
2002 	if (!left && !right)
2003 		return NULL;
2004 
2005 	if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
2006 		sval_t val = sval_binop(left_sval, op, right_sval);
2007 		return alloc_rl(val, val);
2008 	}
2009 
2010 	switch (op) {
2011 	case '%':
2012 		ret = handle_mod_rl(left, right);
2013 		break;
2014 	case '/':
2015 		ret = handle_divide_rl(left, right);
2016 		break;
2017 	case '*':
2018 	case '+':
2019 		ret = handle_add_mult_rl(left, op, right);
2020 		break;
2021 	case '|':
2022 		ret = handle_OR_rl(left, right);
2023 		break;
2024 	case '^':
2025 		ret = handle_XOR_rl(left, right);
2026 		break;
2027 	case '&':
2028 		ret = handle_AND_rl(left, right);
2029 		break;
2030 	case '-':
2031 		ret = handle_sub_rl(left, right);
2032 		break;
2033 	case SPECIAL_RIGHTSHIFT:
2034 		return handle_rshift(left, right);
2035 	case SPECIAL_LEFTSHIFT:
2036 		return handle_lshift(left, right);
2037 	}
2038 
2039 	return ret;
2040 }
2041 
free_data_info_allocs(void)2042 void free_data_info_allocs(void)
2043 {
2044 	struct allocator_struct *desc = &data_info_allocator;
2045 	struct allocation_blob *blob = desc->blobs;
2046 
2047 	free_all_rl();
2048 	clear_math_cache();
2049 
2050 	desc->blobs = NULL;
2051 	desc->allocations = 0;
2052 	desc->total_bytes = 0;
2053 	desc->useful_bytes = 0;
2054 	desc->freelist = NULL;
2055 	while (blob) {
2056 		struct allocation_blob *next = blob->next;
2057 		blob_free(blob, desc->chunking);
2058 		blob = next;
2059 	}
2060 	clear_data_range_alloc();
2061 }
2062 
split_comparison_rl(struct range_list * left_orig,int op,struct range_list * right_orig,struct range_list ** left_true_rl,struct range_list ** left_false_rl,struct range_list ** right_true_rl,struct range_list ** right_false_rl)2063 void split_comparison_rl(struct range_list *left_orig, int op, struct range_list *right_orig,
2064 		struct range_list **left_true_rl, struct range_list **left_false_rl,
2065 		struct range_list **right_true_rl, struct range_list **right_false_rl)
2066 {
2067 	struct range_list *left_true, *left_false;
2068 	struct range_list *right_true, *right_false;
2069 	sval_t min, max;
2070 
2071 	min = sval_type_min(rl_type(left_orig));
2072 	max = sval_type_max(rl_type(left_orig));
2073 
2074 	left_true = clone_rl(left_orig);
2075 	left_false = clone_rl(left_orig);
2076 	right_true = clone_rl(right_orig);
2077 	right_false = clone_rl(right_orig);
2078 
2079 	switch (op) {
2080 	case '<':
2081 	case SPECIAL_UNSIGNED_LT:
2082 		left_true = remove_range(left_orig, rl_max(right_orig), max);
2083 		if (!sval_is_min(rl_min(right_orig))) {
2084 			left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2085 		}
2086 
2087 		right_true = remove_range(right_orig, min, rl_min(left_orig));
2088 		if (!sval_is_max(rl_max(left_orig)))
2089 			right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2090 		break;
2091 	case SPECIAL_UNSIGNED_LTE:
2092 	case SPECIAL_LTE:
2093 		if (!sval_is_max(rl_max(right_orig)))
2094 			left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2095 		left_false = remove_range(left_orig, min, rl_min(right_orig));
2096 
2097 		if (!sval_is_min(rl_min(left_orig)))
2098 			right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2099 		right_false = remove_range(right_orig, rl_max(left_orig), max);
2100 
2101 		if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2102 			left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
2103 		if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2104 			right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
2105 		break;
2106 	case SPECIAL_EQUAL:
2107 		left_true = rl_intersection(left_orig, right_orig);
2108 		right_true = clone_rl(left_true);
2109 
2110 		if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2111 			left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2112 		if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2113 			right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2114 		break;
2115 	case SPECIAL_UNSIGNED_GTE:
2116 	case SPECIAL_GTE:
2117 		if (!sval_is_min(rl_min(right_orig)))
2118 			left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2119 		left_false = remove_range(left_orig, rl_max(right_orig), max);
2120 
2121 		if (!sval_is_max(rl_max(left_orig)))
2122 			right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2123 		right_false = remove_range(right_orig, min, rl_min(left_orig));
2124 
2125 		if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2126 			right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
2127 		if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2128 			left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
2129 		break;
2130 	case '>':
2131 	case SPECIAL_UNSIGNED_GT:
2132 		left_true = remove_range(left_orig, min, rl_min(right_orig));
2133 		if (!sval_is_max(rl_max(right_orig)))
2134 			left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2135 
2136 		right_true = remove_range(right_orig, rl_max(left_orig), max);
2137 		if (!sval_is_min(rl_min(left_orig)))
2138 			right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2139 		break;
2140 	case SPECIAL_NOTEQUAL:
2141 		left_false = rl_intersection(left_orig, right_orig);
2142 		right_false = clone_rl(left_false);
2143 
2144 		if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2145 			left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2146 		if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2147 			right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2148 		break;
2149 	default:
2150 		sm_perror(" unhandled comparison %d", op);
2151 	}
2152 
2153 	if (left_true_rl) {
2154 		*left_true_rl = left_true;
2155 		*left_false_rl = left_false;
2156 	}
2157 	if (right_true_rl) {
2158 		*right_true_rl = right_true;
2159 		*right_false_rl = right_false;
2160 	}
2161 }
2162