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