?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Documentation: make me less confused
[smatch.git] / smatch_ranges.c
blob4cf7fae1105afb32b64c3b9ee025dc663c1b0c89
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
28 char *show_rl(struct range_list *list)
29 {
30 struct data_range *tmp;
31 char full[256];
32 int i = 0;
33
34 full[0] = '\0';
35 full[255] = '\0';
36 FOR_EACH_PTR(list, tmp) {
37 if (i++)
38 strncat(full, ",", 254 - strlen(full));
39 if (sval_cmp(tmp->min, tmp->max) == 0) {
40 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
41 continue;
42 }
43 strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
44 strncat(full, "-", 254 - strlen(full));
45 strncat(full, sval_to_str(tmp->max), 254 - strlen(full));
46 } END_FOR_EACH_PTR(tmp);
47 return alloc_sname(full);
48 }
49
50 static int str_to_comparison_arg_helper(const char *str,
51 struct expression *call, int *comparison,
52 struct expression **arg, char **endp)
53 {
54 int param;
55 char *c = (char *)str;
56
57 if (*c != '[')
58 return 0;
59 c++;
60
61 if (*c == '<') {
62 c++;
63 if (*c == '=') {
64 *comparison = SPECIAL_LTE;
65 c++;
66 } else {
67 *comparison = '<';
68 }
69 } else if (*c == '=') {
70 c++;
71 c++;
72 *comparison = SPECIAL_EQUAL;
73 } else if (*c == '>') {
74 c++;
75 if (*c == '=') {
76 *comparison = SPECIAL_GTE;
77 c++;
78 } else {
79 *comparison = '>';
80 }
81 } else if (*c == '!') {
82 c++;
83 c++;
84 *comparison = SPECIAL_NOTEQUAL;
85 } else {
86 return 0;
87 }
88
89 if (*c != '$')
90 return 0;
91 c++;
92
93 param = strtoll(c, &c, 10);
94 c++; /* skip the ']' character */
95 if (endp)
96 *endp = (char *)c;
97
98 if (!call)
99 return 0;
100 *arg = get_argument_from_call_expr(call->args, param);
101 if (!*arg)
102 return 0;
103 return 1;
104 }
105
106 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
107 {
108 while (1) {
109 if (!*str)
110 return 0;
111 if (*str == '[')
112 break;
113 str++;
114 }
115 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
116 }
117
118 static int get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp, sval_t *sval)
119 {
120 struct expression *arg;
121 int comparison;
122 sval_t ret, tmp;
123
124 if (use_max)
125 ret = sval_type_max(type);
126 else
127 ret = sval_type_min(type);
128
129 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
130 *sval = ret;
131 return 0;
132 }
133
134 if (use_max && get_implied_max(arg, &tmp)) {
135 ret = tmp;
136 if (comparison == '<') {
137 tmp.value = 1;
138 ret = sval_binop(ret, '-', tmp);
139 }
140 }
141 if (!use_max && get_implied_min(arg, &tmp)) {
142 ret = tmp;
143 if (comparison == '>') {
144 tmp.value = 1;
145 ret = sval_binop(ret, '+', tmp);
146 }
147 }
148
149 *sval = ret;
150 return 1;
151 }
152
153 static sval_t add_one(sval_t sval)
154 {
155 sval.value++;
156 return sval;
157 }
158
159 static sval_t sub_one(sval_t sval)
160 {
161 sval.value--;
162 return sval;
163 }
164
165 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
166 {
167 struct range_list *left_orig = *rl;
168 struct range_list *right_orig = right;
169 struct range_list *ret_rl = *rl;
170 struct symbol *cast_type;
171 sval_t min, max;
172
173 cast_type = rl_type(left_orig);
174 if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
175 cast_type = rl_type(right_orig);
176 if (sval_type_max(cast_type).uvalue < INT_MAX)
177 cast_type = &int_ctype;
178
179 min = sval_type_min(cast_type);
180 max = sval_type_max(cast_type);
181 left_orig = cast_rl(cast_type, left_orig);
182 right_orig = cast_rl(cast_type, right_orig);
183
184 switch (comparison) {
185 case '<':
186 case SPECIAL_UNSIGNED_LT:
187 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
188 break;
189 case SPECIAL_LTE:
190 case SPECIAL_UNSIGNED_LTE:
191 if (!sval_is_max(rl_max(right_orig)))
192 ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
193 break;
194 case SPECIAL_EQUAL:
195 if (!sval_is_max(rl_max(right_orig)))
196 ret_rl = remove_range(ret_rl, add_one(rl_max(right_orig)), max);
197 if (!sval_is_min(rl_min(right_orig)))
198 ret_rl = remove_range(ret_rl, min, sub_one(rl_min(right_orig)));
199 break;
200 case SPECIAL_GTE:
201 case SPECIAL_UNSIGNED_GTE:
202 if (!sval_is_min(rl_min(right_orig)))
203 ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
204 break;
205 case '>':
206 case SPECIAL_UNSIGNED_GT:
207 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
208 break;
209 case SPECIAL_NOTEQUAL:
210 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
211 ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
212 break;
213 default:
214 sm_msg("internal error: unhandled comparison %s", show_special(comparison));
215 return;
216 }
217
218 *rl = cast_rl(rl_type(*rl), ret_rl);
219 }
220
221 static struct range_list *filter_by_comparison_call(char *c, struct expression *call, char **endp, struct range_list *start_rl)
222 {
223 struct expression *arg;
224 struct range_list *right_orig;
225 int comparison;
226
227 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
228 return 0;
229
230 if (!get_implied_rl(arg, &right_orig))
231 return 0;
232
233 filter_by_comparison(&start_rl, comparison, right_orig);
234 return start_rl;
235 }
236
237 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
238 {
239 char *start = c;
240 sval_t ret;
241
242 if (!strncmp(start, "max", 3)) {
243 ret = sval_type_max(type);
244 c += 3;
245 } else if (!strncmp(start, "u64max", 6)) {
246 ret = sval_type_val(type, ULLONG_MAX);
247 c += 6;
248 } else if (!strncmp(start, "s64max", 6)) {
249 ret = sval_type_val(type, LLONG_MAX);
250 c += 6;
251 } else if (!strncmp(start, "u32max", 6)) {
252 ret = sval_type_val(type, UINT_MAX);
253 c += 6;
254 } else if (!strncmp(start, "s32max", 6)) {
255 ret = sval_type_val(type, INT_MAX);
256 c += 6;
257 } else if (!strncmp(start, "u16max", 6)) {
258 ret = sval_type_val(type, USHRT_MAX);
259 c += 6;
260 } else if (!strncmp(start, "s16max", 6)) {
261 ret = sval_type_val(type, SHRT_MAX);
262 c += 6;
263 } else if (!strncmp(start, "min", 3)) {
264 ret = sval_type_min(type);
265 c += 3;
266 } else if (!strncmp(start, "s64min", 6)) {
267 ret = sval_type_val(type, LLONG_MIN);
268 c += 6;
269 } else if (!strncmp(start, "s32min", 6)) {
270 ret = sval_type_val(type, INT_MIN);
271 c += 6;
272 } else if (!strncmp(start, "s16min", 6)) {
273 ret = sval_type_val(type, SHRT_MIN);
274 c += 6;
275 } else if (!strncmp(start, "long_min", 8)) {
276 ret = sval_type_val(type, LONG_MIN);
277 c += 8;
278 } else if (!strncmp(start, "long_max", 8)) {
279 ret = sval_type_val(type, LONG_MAX);
280 c += 8;
281 } else if (!strncmp(start, "ulong_max", 9)) {
282 ret = sval_type_val(type, ULONG_MAX);
283 c += 8;
284 } else if (!strncmp(start, "ptr_max", 7)) {
285 ret = sval_type_val(type, valid_ptr_max);
286 c += 8;
287 } else if (start[0] == '[') {
288 /* this parses [==p0] comparisons */
289 get_val_from_key(1, type, start, call, &c, &ret);
290 } else {
291 ret = sval_type_val(type, strtoll(start, &c, 10));
292 }
293 *endp = c;
294 return ret;
295 }
296
297 static char *jump_to_call_math(char *value)
298 {
299 char *c = value;
300
301 while (*c && *c != '[')
302 c++;
303
304 if (!*c)
305 return NULL;
306 c++;
307 if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
308 return NULL;
309
310 return c;
311 }
312
313 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *str, char **endp, struct range_list **rl)
314 {
315 struct range_list *rl_tmp = NULL;
316 sval_t min, max;
317 char *c;
318
319 min = sval_type_min(type);
320 max = sval_type_max(type);
321 c = str;
322 while (*c != '\0' && *c != '[') {
323 if (*c == '(')
324 c++;
325 min = parse_val(0, call, type, c, &c);
326 max = min;
327 if (*c == ')')
328 c++;
329 if (*c == '\0' || *c == '[') {
330 add_range(&rl_tmp, min, min);
331 break;
332 }
333 if (*c == ',') {
334 add_range(&rl_tmp, min, min);
335 c++;
336 continue;
337 }
338 if (*c != '-') {
339 sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
340 break;
341 }
342 c++;
343 if (*c == '(')
344 c++;
345 max = parse_val(1, call, type, c, &c);
346 add_range(&rl_tmp, min, max);
347 if (*c == ')')
348 c++;
349 if (*c == ',')
350 c++;
351 }
352
353 *rl = rl_tmp;
354 *endp = c;
355 }
356
357 static void str_to_dinfo(struct expression *call, struct symbol *type, char *value, struct data_info *dinfo)
358 {
359 struct range_list *math_rl;
360 char *call_math;
361 char *c;
362 struct range_list *rl = NULL;
363
364 if (!type)
365 type = &llong_ctype;
366
367 if (strcmp(value, "empty") == 0)
368 return;
369
370 if (strncmp(value, "[==$", 4) == 0) {
371 struct expression *arg;
372 int comparison;
373
374 if (!str_to_comparison_arg(value, call, &comparison, &arg))
375 return;
376 if (!get_implied_rl(arg, &rl))
377 return;
378 goto cast;
379 }
380
381 str_to_rl_helper(call, type, value, &c, &rl);
382 if (*c == '\0')
383 goto cast;
384
385 call_math = jump_to_call_math(value);
386 if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
387 rl = rl_intersection(rl, math_rl);
388 goto cast;
389 }
390
391 /*
392 * For now if we already tried to handle the call math and couldn't
393 * figure it out then bail.
394 */
395 if (jump_to_call_math(c) == c + 1)
396 goto cast;
397
398 rl = filter_by_comparison_call(c, call, &c, rl);
399
400 cast:
401 rl = cast_rl(type, rl);
402 dinfo->value_ranges = rl;
403 }
404
405 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
406 {
407 struct data_info dinfo = {};
408
409 str_to_dinfo(NULL, type, value, &dinfo);
410 *rl = dinfo.value_ranges;
411 }
412
413 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
414 {
415 struct data_info dinfo = {};
416
417 str_to_dinfo(strip_expr(expr), type, value, &dinfo);
418 *rl = dinfo.value_ranges;
419 }
420
421 int is_whole_rl(struct range_list *rl)
422 {
423 struct data_range *drange;
424
425 if (ptr_list_empty(rl))
426 return 0;
427 drange = first_ptr_list((struct ptr_list *)rl);
428 if (sval_is_min(drange->min) && sval_is_max(drange->max))
429 return 1;
430 return 0;
431 }
432
433 sval_t rl_min(struct range_list *rl)
434 {
435 struct data_range *drange;
436 sval_t ret;
437
438 ret.type = &llong_ctype;
439 ret.value = LLONG_MIN;
440 if (ptr_list_empty(rl))
441 return ret;
442 drange = first_ptr_list((struct ptr_list *)rl);
443 return drange->min;
444 }
445
446 sval_t rl_max(struct range_list *rl)
447 {
448 struct data_range *drange;
449 sval_t ret;
450
451 ret.type = &llong_ctype;
452 ret.value = LLONG_MAX;
453 if (ptr_list_empty(rl))
454 return ret;
455 drange = last_ptr_list((struct ptr_list *)rl);
456 return drange->max;
457 }
458
459 int rl_to_sval(struct range_list *rl, sval_t *sval)
460 {
461 sval_t min, max;
462
463 if (!rl)
464 return 0;
465
466 min = rl_min(rl);
467 max = rl_max(rl);
468 if (sval_cmp(min, max) != 0)
469 return 0;
470 *sval = min;
471 return 1;
472 }
473
474 struct symbol *rl_type(struct range_list *rl)
475 {
476 if (!rl)
477 return NULL;
478 return rl_min(rl).type;
479 }
480
481 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
482 {
483 struct data_range *ret;
484
485 if (perm)
486 ret = __alloc_perm_data_range(0);
487 else
488 ret = __alloc_data_range(0);
489 ret->min = min;
490 ret->max = max;
491 return ret;
492 }
493
494 struct data_range *alloc_range(sval_t min, sval_t max)
495 {
496 return alloc_range_helper_sval(min, max, 0);
497 }
498
499 struct data_range *alloc_range_perm(sval_t min, sval_t max)
500 {
501 return alloc_range_helper_sval(min, max, 1);
502 }
503
504 struct range_list *alloc_rl(sval_t min, sval_t max)
505 {
506 struct range_list *rl = NULL;
507
508 if (sval_cmp(min, max) > 0)
509 return alloc_whole_rl(min.type);
510
511 add_range(&rl, min, max);
512 return rl;
513 }
514
515 struct range_list *alloc_whole_rl(struct symbol *type)
516 {
517 if (!type || type_positive_bits(type) < 0)
518 type = &llong_ctype;
519 if (type->type == SYM_ARRAY)
520 type = &ptr_ctype;
521
522 return alloc_rl(sval_type_min(type), sval_type_max(type));
523 }
524
525 void add_range(struct range_list **list, sval_t min, sval_t max)
526 {
527 struct data_range *tmp = NULL;
528 struct data_range *new = NULL;
529 int check_next = 0;
530
531 /*
532 * FIXME: This has a problem merging a range_list like: min-0,3-max
533 * with a range like 1-2. You end up with min-2,3-max instead of
534 * just min-max.
535 */
536 FOR_EACH_PTR(*list, tmp) {
537 if (check_next) {
538 /* Sometimes we overlap with more than one range
539 so we have to delete or modify the next range. */
540 if (max.value + 1 == tmp->min.value) {
541 /* join 2 ranges here */
542 new->max = tmp->max;
543 DELETE_CURRENT_PTR(tmp);
544 return;
545 }
546
547 /* Doesn't overlap with the next one. */
548 if (sval_cmp(max, tmp->min) < 0)
549 return;
550 /* Partially overlaps with the next one. */
551 if (sval_cmp(max, tmp->max) < 0) {
552 tmp->min.value = max.value + 1;
553 return;
554 }
555 /* Completely overlaps with the next one. */
556 if (sval_cmp(max, tmp->max) >= 0) {
557 DELETE_CURRENT_PTR(tmp);
558 /* there could be more ranges to delete */
559 continue;
560 }
561 }
562 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
563 /* join 2 ranges into a big range */
564 new = alloc_range(min, tmp->max);
565 REPLACE_CURRENT_PTR(tmp, new);
566 return;
567 }
568 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
569 new = alloc_range(min, max);
570 INSERT_CURRENT(new, tmp);
571 return;
572 }
573 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
574 if (sval_cmp(max, tmp->max) < 0)
575 max = tmp->max;
576 else
577 check_next = 1;
578 new = alloc_range(min, max);
579 REPLACE_CURRENT_PTR(tmp, new);
580 if (!check_next)
581 return;
582 continue;
583 }
584 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
585 return;
586 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
587 min = tmp->min;
588 new = alloc_range(min, max);
589 REPLACE_CURRENT_PTR(tmp, new);
590 check_next = 1;
591 continue;
592 }
593 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
594 /* join 2 ranges into a big range */
595 new = alloc_range(tmp->min, max);
596 REPLACE_CURRENT_PTR(tmp, new);
597 check_next = 1;
598 continue;
599 }
600 /* the new range is entirely above the existing ranges */
601 } END_FOR_EACH_PTR(tmp);
602 if (check_next)
603 return;
604 new = alloc_range(min, max);
605 add_ptr_list(list, new);
606 }
607
608 struct range_list *clone_rl(struct range_list *list)
609 {
610 struct data_range *tmp;
611 struct range_list *ret = NULL;
612
613 FOR_EACH_PTR(list, tmp) {
614 add_ptr_list(&ret, tmp);
615 } END_FOR_EACH_PTR(tmp);
616 return ret;
617 }
618
619 struct range_list *clone_rl_permanent(struct range_list *list)
620 {
621 struct data_range *tmp;
622 struct data_range *new;
623 struct range_list *ret = NULL;
624
625 FOR_EACH_PTR(list, tmp) {
626 new = alloc_range_perm(tmp->min, tmp->max);
627 add_ptr_list(&ret, new);
628 } END_FOR_EACH_PTR(tmp);
629 return ret;
630 }
631
632 struct range_list *rl_union(struct range_list *one, struct range_list *two)
633 {
634 struct data_range *tmp;
635 struct range_list *ret = NULL;
636
637 FOR_EACH_PTR(one, tmp) {
638 add_range(&ret, tmp->min, tmp->max);
639 } END_FOR_EACH_PTR(tmp);
640 FOR_EACH_PTR(two, tmp) {
641 add_range(&ret, tmp->min, tmp->max);
642 } END_FOR_EACH_PTR(tmp);
643 return ret;
644 }
645
646 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
647 {
648 struct data_range *tmp;
649 struct range_list *ret = NULL;
650
651 FOR_EACH_PTR(list, tmp) {
652 if (sval_cmp(tmp->max, min) < 0) {
653 add_range(&ret, tmp->min, tmp->max);
654 continue;
655 }
656 if (sval_cmp(tmp->min, max) > 0) {
657 add_range(&ret, tmp->min, tmp->max);
658 continue;
659 }
660 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
661 continue;
662 if (sval_cmp(tmp->min, min) >= 0) {
663 max.value++;
664 add_range(&ret, max, tmp->max);
665 } else if (sval_cmp(tmp->max, max) <= 0) {
666 min.value--;
667 add_range(&ret, tmp->min, min);
668 } else {
669 min.value--;
670 max.value++;
671 add_range(&ret, tmp->min, min);
672 add_range(&ret, max, tmp->max);
673 }
674 } END_FOR_EACH_PTR(tmp);
675 return ret;
676 }
677
678 int ranges_equiv(struct data_range *one, struct data_range *two)
679 {
680 if (!one && !two)
681 return 1;
682 if (!one || !two)
683 return 0;
684 if (sval_cmp(one->min, two->min) != 0)
685 return 0;
686 if (sval_cmp(one->max, two->max) != 0)
687 return 0;
688 return 1;
689 }
690
691 int rl_equiv(struct range_list *one, struct range_list *two)
692 {
693 struct data_range *one_range;
694 struct data_range *two_range;
695
696 if (one == two)
697 return 1;
698
699 PREPARE_PTR_LIST(one, one_range);
700 PREPARE_PTR_LIST(two, two_range);
701 for (;;) {
702 if (!one_range && !two_range)
703 return 1;
704 if (!ranges_equiv(one_range, two_range))
705 return 0;
706 NEXT_PTR_LIST(one_range);
707 NEXT_PTR_LIST(two_range);
708 }
709 FINISH_PTR_LIST(two_range);
710 FINISH_PTR_LIST(one_range);
711
712 return 1;
713 }
714
715 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
716 {
717 switch (comparison) {
718 case '<':
719 case SPECIAL_UNSIGNED_LT:
720 if (sval_cmp(left->min, right->max) < 0)
721 return 1;
722 return 0;
723 case SPECIAL_UNSIGNED_LTE:
724 case SPECIAL_LTE:
725 if (sval_cmp(left->min, right->max) <= 0)
726 return 1;
727 return 0;
728 case SPECIAL_EQUAL:
729 if (sval_cmp(left->max, right->min) < 0)
730 return 0;
731 if (sval_cmp(left->min, right->max) > 0)
732 return 0;
733 return 1;
734 case SPECIAL_UNSIGNED_GTE:
735 case SPECIAL_GTE:
736 if (sval_cmp(left->max, right->min) >= 0)
737 return 1;
738 return 0;
739 case '>':
740 case SPECIAL_UNSIGNED_GT:
741 if (sval_cmp(left->max, right->min) > 0)
742 return 1;
743 return 0;
744 case SPECIAL_NOTEQUAL:
745 if (sval_cmp(left->min, left->max) != 0)
746 return 1;
747 if (sval_cmp(right->min, right->max) != 0)
748 return 1;
749 if (sval_cmp(left->min, right->min) != 0)
750 return 1;
751 return 0;
752 default:
753 sm_msg("unhandled comparison %d\n", comparison);
754 return 0;
755 }
756 return 0;
757 }
758
759 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
760 {
761 if (left)
762 return true_comparison_range(var, comparison, val);
763 else
764 return true_comparison_range(val, comparison, var);
765 }
766
767 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
768 {
769 switch (comparison) {
770 case '<':
771 case SPECIAL_UNSIGNED_LT:
772 if (sval_cmp(left->max, right->min) >= 0)
773 return 1;
774 return 0;
775 case SPECIAL_UNSIGNED_LTE:
776 case SPECIAL_LTE:
777 if (sval_cmp(left->max, right->min) > 0)
778 return 1;
779 return 0;
780 case SPECIAL_EQUAL:
781 if (sval_cmp(left->min, left->max) != 0)
782 return 1;
783 if (sval_cmp(right->min, right->max) != 0)
784 return 1;
785 if (sval_cmp(left->min, right->min) != 0)
786 return 1;
787 return 0;
788 case SPECIAL_UNSIGNED_GTE:
789 case SPECIAL_GTE:
790 if (sval_cmp(left->min, right->max) < 0)
791 return 1;
792 return 0;
793 case '>':
794 case SPECIAL_UNSIGNED_GT:
795 if (sval_cmp(left->min, right->max) <= 0)
796 return 1;
797 return 0;
798 case SPECIAL_NOTEQUAL:
799 if (sval_cmp(left->max, right->min) < 0)
800 return 0;
801 if (sval_cmp(left->min, right->max) > 0)
802 return 0;
803 return 1;
804 default:
805 sm_msg("unhandled comparison %d\n", comparison);
806 return 0;
807 }
808 return 0;
809 }
810
811 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
812 {
813 if (left)
814 return false_comparison_range_sval(var, comparison, val);
815 else
816 return false_comparison_range_sval(val, comparison, var);
817 }
818
819 int possibly_true(struct expression *left, int comparison, struct expression *right)
820 {
821 struct range_list *rl_left, *rl_right;
822 struct data_range *tmp_left, *tmp_right;
823 struct symbol *type;
824
825 if (!get_implied_rl(left, &rl_left))
826 return 1;
827 if (!get_implied_rl(right, &rl_right))
828 return 1;
829
830 type = rl_type(rl_left);
831 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
832 type = rl_type(rl_right);
833 if (type_positive_bits(type) < 31)
834 type = &int_ctype;
835
836 rl_left = cast_rl(type, rl_left);
837 rl_right = cast_rl(type, rl_right);
838
839 FOR_EACH_PTR(rl_left, tmp_left) {
840 FOR_EACH_PTR(rl_right, tmp_right) {
841 if (true_comparison_range(tmp_left, comparison, tmp_right))
842 return 1;
843 } END_FOR_EACH_PTR(tmp_right);
844 } END_FOR_EACH_PTR(tmp_left);
845 return 0;
846 }
847
848 int possibly_false(struct expression *left, int comparison, struct expression *right)
849 {
850 struct range_list *rl_left, *rl_right;
851 struct data_range *tmp_left, *tmp_right;
852 struct symbol *type;
853
854 if (!get_implied_rl(left, &rl_left))
855 return 1;
856 if (!get_implied_rl(right, &rl_right))
857 return 1;
858
859 type = rl_type(rl_left);
860 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
861 type = rl_type(rl_right);
862 if (type_positive_bits(type) < 31)
863 type = &int_ctype;
864
865 rl_left = cast_rl(type, rl_left);
866 rl_right = cast_rl(type, rl_right);
867
868 FOR_EACH_PTR(rl_left, tmp_left) {
869 FOR_EACH_PTR(rl_right, tmp_right) {
870 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
871 return 1;
872 } END_FOR_EACH_PTR(tmp_right);
873 } END_FOR_EACH_PTR(tmp_left);
874 return 0;
875 }
876
877 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
878 {
879 struct data_range *left_tmp, *right_tmp;
880
881 if (!left_ranges || !right_ranges)
882 return 1;
883
884 FOR_EACH_PTR(left_ranges, left_tmp) {
885 FOR_EACH_PTR(right_ranges, right_tmp) {
886 if (true_comparison_range(left_tmp, comparison, right_tmp))
887 return 1;
888 } END_FOR_EACH_PTR(right_tmp);
889 } END_FOR_EACH_PTR(left_tmp);
890 return 0;
891 }
892
893 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
894 {
895 struct data_range *left_tmp, *right_tmp;
896
897 if (!left_ranges || !right_ranges)
898 return 1;
899
900 FOR_EACH_PTR(left_ranges, left_tmp) {
901 FOR_EACH_PTR(right_ranges, right_tmp) {
902 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
903 return 1;
904 } END_FOR_EACH_PTR(right_tmp);
905 } END_FOR_EACH_PTR(left_tmp);
906 return 0;
907 }
908
909 /* FIXME: the _rl here stands for right left so really it should be _lr */
910 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
911 {
912 if (left)
913 return possibly_true_rl(a, comparison, b);
914 else
915 return possibly_true_rl(b, comparison, a);
916 }
917
918 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
919 {
920 if (left)
921 return possibly_false_rl(a, comparison, b);
922 else
923 return possibly_false_rl(b, comparison, a);
924 }
925
926 int rl_has_sval(struct range_list *rl, sval_t sval)
927 {
928 struct data_range *tmp;
929
930 FOR_EACH_PTR(rl, tmp) {
931 if (sval_cmp(tmp->min, sval) <= 0 &&
932 sval_cmp(tmp->max, sval) >= 0)
933 return 1;
934 } END_FOR_EACH_PTR(tmp);
935 return 0;
936 }
937
938 void tack_on(struct range_list **list, struct data_range *drange)
939 {
940 add_ptr_list(list, drange);
941 }
942
943 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
944 {
945 add_ptr_list(rl_stack, rl);
946 }
947
948 struct range_list *pop_rl(struct range_list_stack **rl_stack)
949 {
950 struct range_list *rl;
951
952 rl = last_ptr_list((struct ptr_list *)*rl_stack);
953 delete_ptr_list_last((struct ptr_list **)rl_stack);
954 return rl;
955 }
956
957 struct range_list *top_rl(struct range_list_stack *rl_stack)
958 {
959 struct range_list *rl;
960
961 rl = last_ptr_list((struct ptr_list *)rl_stack);
962 return rl;
963 }
964
965 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
966 {
967 struct range_list *rl;
968
969 rl = pop_rl(rl_stack);
970 rl = remove_range(rl, sval, sval);
971 push_rl(rl_stack, rl);
972 }
973
974 static int sval_too_big(struct symbol *type, sval_t sval)
975 {
976 if (type_bits(type) == 64)
977 return 0;
978 if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
979 return 1;
980 return 0;
981 }
982
983 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
984 {
985 /* If we're just adding a number, cast it and add it */
986 if (sval_cmp(min, max) == 0) {
987 add_range(rl, sval_cast(type, min), sval_cast(type, max));
988 return;
989 }
990
991 /* If the range is within the type range then add it */
992 if (sval_fits(type, min) && sval_fits(type, max)) {
993 add_range(rl, sval_cast(type, min), sval_cast(type, max));
994 return;
995 }
996
997 /*
998 * If the range we are adding has more bits than the range type then
999 * add the whole range type. Eg:
1000 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
1001 * This isn't totally the right thing to do. We could be more granular.
1002 */
1003 if (sval_too_big(type, min) || sval_too_big(type, max)) {
1004 add_range(rl, sval_type_min(type), sval_type_max(type));
1005 return;
1006 }
1007
1008 /* Cast negative values to high positive values */
1009 if (sval_is_negative(min) && type_unsigned(type)) {
1010 if (sval_is_positive(max)) {
1011 if (sval_too_high(type, max)) {
1012 add_range(rl, sval_type_min(type), sval_type_max(type));
1013 return;
1014 }
1015 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
1016 max = sval_type_max(type);
1017 } else {
1018 max = sval_cast(type, max);
1019 }
1020 min = sval_cast(type, min);
1021 add_range(rl, min, max);
1022 }
1023
1024 /* Cast high positive numbers to negative */
1025 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
1026 if (!sval_is_negative(sval_cast(type, min))) {
1027 add_range(rl, sval_cast(type, min), sval_type_max(type));
1028 min = sval_type_min(type);
1029 } else {
1030 min = sval_cast(type, min);
1031 }
1032 max = sval_cast(type, max);
1033 add_range(rl, min, max);
1034 }
1035
1036 add_range(rl, min, max);
1037 return;
1038 }
1039
1040 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1041 {
1042 struct data_range *tmp;
1043 struct range_list *ret = NULL;
1044 sval_t min, max;
1045
1046 if (!rl)
1047 return NULL;
1048
1049 if (!type || type == rl_type(rl))
1050 return rl;
1051
1052 FOR_EACH_PTR(rl, tmp) {
1053 min = tmp->min;
1054 max = tmp->max;
1055 if (type_bits(type) < type_bits(rl_type(rl))) {
1056 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1057 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1058 }
1059 if (sval_cmp(min, max) > 0) {
1060 min = sval_cast(type, min);
1061 max = sval_cast(type, max);
1062 }
1063 add_range_t(type, &ret, min, max);
1064 } END_FOR_EACH_PTR(tmp);
1065
1066 return ret;
1067 }
1068
1069 static int rl_is_sane(struct range_list *rl)
1070 {
1071 struct data_range *tmp;
1072 struct symbol *type;
1073
1074 type = rl_type(rl);
1075 FOR_EACH_PTR(rl, tmp) {
1076 if (!sval_fits(type, tmp->min))
1077 return 0;
1078 if (!sval_fits(type, tmp->max))
1079 return 0;
1080 if (sval_cmp(tmp->min, tmp->max) > 0)
1081 return 0;
1082 } END_FOR_EACH_PTR(tmp);
1083
1084 return 1;
1085 }
1086
1087 static int rl_type_consistent(struct range_list *rl)
1088 {
1089 struct data_range *tmp;
1090 struct symbol *type;
1091
1092 type = rl_type(rl);
1093 FOR_EACH_PTR(rl, tmp) {
1094 if (type != tmp->min.type || type != tmp->max.type)
1095 return 0;
1096 } END_FOR_EACH_PTR(tmp);
1097 return 1;
1098 }
1099
1100 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1101 {
1102 struct data_range *tmp;
1103 struct range_list *ret = NULL;
1104
1105 if (!rl)
1106 return NULL;
1107
1108 if (!type)
1109 return rl;
1110 if (!rl_is_sane(rl))
1111 return alloc_whole_rl(type);
1112 if (type == rl_type(rl) && rl_type_consistent(rl))
1113 return rl;
1114
1115 FOR_EACH_PTR(rl, tmp) {
1116 add_range_t(type, &ret, tmp->min, tmp->max);
1117 } END_FOR_EACH_PTR(tmp);
1118
1119 if (!ret)
1120 return alloc_whole_rl(type);
1121
1122 return ret;
1123 }
1124
1125 struct range_list *rl_invert(struct range_list *orig)
1126 {
1127 struct range_list *ret = NULL;
1128 struct data_range *tmp;
1129 sval_t gap_min, abs_max, sval;
1130
1131 if (!orig)
1132 return NULL;
1133
1134 gap_min = sval_type_min(rl_min(orig).type);
1135 abs_max = sval_type_max(rl_max(orig).type);
1136
1137 FOR_EACH_PTR(orig, tmp) {
1138 if (sval_cmp(tmp->min, gap_min) > 0) {
1139 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1140 add_range(&ret, gap_min, sval);
1141 }
1142 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1143 if (sval_cmp(tmp->max, abs_max) == 0)
1144 gap_min = abs_max;
1145 } END_FOR_EACH_PTR(tmp);
1146
1147 if (sval_cmp(gap_min, abs_max) < 0)
1148 add_range(&ret, gap_min, abs_max);
1149
1150 return ret;
1151 }
1152
1153 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1154 {
1155 struct data_range *tmp;
1156
1157 FOR_EACH_PTR(filter, tmp) {
1158 rl = remove_range(rl, tmp->min, tmp->max);
1159 } END_FOR_EACH_PTR(tmp);
1160
1161 return rl;
1162 }
1163
1164 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1165 {
1166 struct range_list *one_orig;
1167 struct range_list *two_orig;
1168 struct range_list *ret;
1169 struct symbol *ret_type;
1170 struct symbol *small_type;
1171 struct symbol *large_type;
1172
1173 if (!two)
1174 return NULL;
1175 if (!one)
1176 return NULL;
1177
1178 one_orig = one;
1179 two_orig = two;
1180
1181 ret_type = rl_type(one);
1182 small_type = rl_type(one);
1183 large_type = rl_type(two);
1184
1185 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1186 small_type = rl_type(two);
1187 large_type = rl_type(one);
1188 }
1189
1190 one = cast_rl(large_type, one);
1191 two = cast_rl(large_type, two);
1192
1193 ret = one;
1194 one = rl_invert(one);
1195 two = rl_invert(two);
1196
1197 ret = rl_filter(ret, one);
1198 ret = rl_filter(ret, two);
1199
1200 one = cast_rl(small_type, one_orig);
1201 two = cast_rl(small_type, two_orig);
1202
1203 one = rl_invert(one);
1204 two = rl_invert(two);
1205
1206 ret = cast_rl(small_type, ret);
1207 ret = rl_filter(ret, one);
1208 ret = rl_filter(ret, two);
1209
1210 return cast_rl(ret_type, ret);
1211 }
1212
1213 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1214 {
1215 sval_t zero;
1216 sval_t max;
1217
1218 max = rl_max(right);
1219 if (sval_is_max(max))
1220 return left;
1221 if (max.value == 0)
1222 return NULL;
1223 max.value--;
1224 if (sval_is_negative(max))
1225 return NULL;
1226 if (sval_cmp(rl_max(left), max) < 0)
1227 return left;
1228 zero = max;
1229 zero.value = 0;
1230 return alloc_rl(zero, max);
1231 }
1232
1233 static struct range_list *get_neg_rl(struct range_list *rl)
1234 {
1235 struct data_range *tmp;
1236 struct range_list *ret = NULL;
1237
1238 if (!rl)
1239 return NULL;
1240 if (sval_is_positive(rl_min(rl)))
1241 return NULL;
1242
1243 FOR_EACH_PTR(rl, tmp) {
1244 if (sval_is_positive(tmp->min))
1245 return ret;
1246 if (sval_is_positive(tmp->max)) {
1247 tmp->max.value = -1;
1248 add_range(&ret, tmp->min, tmp->max);
1249 return ret;
1250 }
1251 add_range(&ret, tmp->min, tmp->max);
1252 } END_FOR_EACH_PTR(tmp);
1253
1254 return ret;
1255 }
1256
1257 static struct range_list *get_pos_rl(struct range_list *rl)
1258 {
1259 struct data_range *tmp;
1260 struct range_list *ret = NULL;
1261
1262 if (!rl)
1263 return NULL;
1264 if (sval_is_negative(rl_max(rl)))
1265 return NULL;
1266
1267 FOR_EACH_PTR(rl, tmp) {
1268 if (sval_is_negative(tmp->max))
1269 continue;
1270 if (sval_is_positive(tmp->min)) {
1271 add_range(&ret, tmp->min, tmp->max);
1272 continue;
1273 }
1274 tmp->min.value = 0;
1275 add_range(&ret, tmp->min, tmp->max);
1276 } END_FOR_EACH_PTR(tmp);
1277
1278 return ret;
1279 }
1280
1281 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1282 {
1283 sval_t right_min, right_max;
1284 sval_t min, max;
1285
1286 if (!left || !right)
1287 return NULL;
1288
1289 /* let's assume we never divide by zero */
1290 right_min = rl_min(right);
1291 right_max = rl_max(right);
1292 if (right_min.value == 0 && right_max.value == 0)
1293 return NULL;
1294 if (right_min.value == 0)
1295 right_min.value = 1;
1296 if (right_max.value == 0)
1297 right_max.value = -1;
1298
1299 max = sval_binop(rl_max(left), '/', right_min);
1300 min = sval_binop(rl_min(left), '/', right_max);
1301
1302 return alloc_rl(min, max);
1303 }
1304
1305 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1306 {
1307 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1308 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1309 struct range_list *ret;
1310
1311 if (is_whole_rl(left) || is_whole_rl(right))
1312 return NULL;
1313
1314 left_neg = get_neg_rl(left);
1315 left_pos = get_pos_rl(left);
1316 right_neg = get_neg_rl(right);
1317 right_pos = get_pos_rl(right);
1318
1319 neg_neg = divide_rl_helper(left_neg, right_neg);
1320 neg_pos = divide_rl_helper(left_neg, right_pos);
1321 pos_neg = divide_rl_helper(left_pos, right_neg);
1322 pos_pos = divide_rl_helper(left_pos, right_pos);
1323
1324 ret = rl_union(neg_neg, neg_pos);
1325 ret = rl_union(ret, pos_neg);
1326 return rl_union(ret, pos_pos);
1327 }
1328
1329 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1330 {
1331 sval_t min, max;
1332
1333 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1334 return NULL;
1335 min = sval_binop(rl_min(left), op, rl_min(right));
1336
1337 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1338 return NULL;
1339 max = sval_binop(rl_max(left), op, rl_max(right));
1340
1341 return alloc_rl(min, max);
1342 }
1343
1344 static unsigned long long sval_fls_mask(sval_t sval)
1345 {
1346 unsigned long long uvalue = sval.uvalue;
1347 unsigned long long high_bit = 0;
1348
1349 while (uvalue) {
1350 uvalue >>= 1;
1351 high_bit++;
1352 }
1353
1354 if (high_bit == 0)
1355 return 0;
1356
1357 return ((unsigned long long)-1) >> (64 - high_bit);
1358 }
1359
1360 static unsigned long long rl_bits_always_set(struct range_list *rl)
1361 {
1362 return sval_fls_mask(rl_min(rl));
1363 }
1364
1365 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1366 {
1367 return sval_fls_mask(rl_max(rl));
1368 }
1369
1370 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1371 {
1372 unsigned long long left_min, left_max, right_min, right_max;
1373 sval_t min, max;
1374 sval_t sval;
1375
1376 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1377 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1378 return rl_binop(left, '+', right);
1379
1380 left_min = rl_bits_always_set(left);
1381 left_max = rl_bits_maybe_set(left);
1382 right_min = rl_bits_always_set(right);
1383 right_max = rl_bits_maybe_set(right);
1384
1385 min.type = max.type = &ullong_ctype;
1386 min.uvalue = left_min | right_min;
1387 max.uvalue = left_max | right_max;
1388
1389 return cast_rl(rl_type(left), alloc_rl(min, max));
1390 }
1391
1392 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1393 {
1394 struct symbol *cast_type;
1395 sval_t left_sval, right_sval;
1396 struct range_list *ret = NULL;
1397
1398 cast_type = rl_type(left);
1399 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1400 cast_type = rl_type(right);
1401 if (sval_type_max(cast_type).uvalue < INT_MAX)
1402 cast_type = &int_ctype;
1403
1404 left = cast_rl(cast_type, left);
1405 right = cast_rl(cast_type, right);
1406
1407 if (!left || !right)
1408 return alloc_whole_rl(cast_type);
1409
1410 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1411 sval_t val = sval_binop(left_sval, op, right_sval);
1412 return alloc_rl(val, val);
1413 }
1414
1415 switch (op) {
1416 case '%':
1417 ret = handle_mod_rl(left, right);
1418 break;
1419 case '/':
1420 ret = handle_divide_rl(left, right);
1421 break;
1422 case '*':
1423 case '+':
1424 ret = handle_add_mult_rl(left, op, right);
1425 break;
1426 case '|':
1427 ret = handle_OR_rl(left, right);
1428 break;
1429
1430 /* FIXME: Do the rest as well */
1431 case '-':
1432 case '&':
1433 case SPECIAL_RIGHTSHIFT:
1434 case SPECIAL_LEFTSHIFT:
1435 case '^':
1436 break;
1437 }
1438
1439 if (!ret)
1440 ret = alloc_whole_rl(cast_type);
1441 return ret;
1442 }
1443
1444 void free_rl(struct range_list **rlist)
1445 {
1446 __free_ptr_list((struct ptr_list **)rlist);
1447 }
1448
1449 static void free_single_dinfo(struct data_info *dinfo)
1450 {
1451 free_rl(&dinfo->value_ranges);
1452 }
1453
1454 static void free_dinfos(struct allocation_blob *blob)
1455 {
1456 unsigned int size = sizeof(struct data_info);
1457 unsigned int offset = 0;
1458
1459 while (offset < blob->offset) {
1460 free_single_dinfo((struct data_info *)(blob->data + offset));
1461 offset += size;
1462 }
1463 }
1464
1465 void free_data_info_allocs(void)
1466 {
1467 struct allocator_struct *desc = &data_info_allocator;
1468 struct allocation_blob *blob = desc->blobs;
1469
1470 desc->blobs = NULL;
1471 desc->allocations = 0;
1472 desc->total_bytes = 0;
1473 desc->useful_bytes = 0;
1474 desc->freelist = NULL;
1475 while (blob) {
1476 struct allocation_blob *next = blob->next;
1477 free_dinfos(blob);
1478 blob_free(blob, desc->chunking);
1479 blob = next;
1480 }
1481 clear_data_range_alloc();
1482 }
1483
Static analysis for C