?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fixup_kernel.sh: fix the rtlwifi hack
[smatch.git] / smatch_ranges.c
blob2092fcc77b8afcbf7b623c3e4ffbd5feaf8adaab
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 (!sval_is_max(max) && 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
551 if (sval_cmp(max, tmp->max) <= 0) {
552 /* Partially overlaps the next one. */
553 new->max = tmp->max;
554 DELETE_CURRENT_PTR(tmp);
555 return;
556 } else {
557 /* Completely overlaps the next one. */
558 DELETE_CURRENT_PTR(tmp);
559 /* there could be more ranges to delete */
560 continue;
561 }
562 }
563 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
564 /* join 2 ranges into a big range */
565 new = alloc_range(min, tmp->max);
566 REPLACE_CURRENT_PTR(tmp, new);
567 return;
568 }
569 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
570 new = alloc_range(min, max);
571 INSERT_CURRENT(new, tmp);
572 return;
573 }
574 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
575 if (sval_cmp(max, tmp->max) < 0)
576 max = tmp->max;
577 else
578 check_next = 1;
579 new = alloc_range(min, max);
580 REPLACE_CURRENT_PTR(tmp, new);
581 if (!check_next)
582 return;
583 continue;
584 }
585 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
586 return;
587 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
588 min = tmp->min;
589 new = alloc_range(min, max);
590 REPLACE_CURRENT_PTR(tmp, new);
591 check_next = 1;
592 continue;
593 }
594 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
595 /* join 2 ranges into a big range */
596 new = alloc_range(tmp->min, max);
597 REPLACE_CURRENT_PTR(tmp, new);
598 check_next = 1;
599 continue;
600 }
601 /* the new range is entirely above the existing ranges */
602 } END_FOR_EACH_PTR(tmp);
603 if (check_next)
604 return;
605 new = alloc_range(min, max);
606 add_ptr_list(list, new);
607 }
608
609 struct range_list *clone_rl(struct range_list *list)
610 {
611 struct data_range *tmp;
612 struct range_list *ret = NULL;
613
614 FOR_EACH_PTR(list, tmp) {
615 add_ptr_list(&ret, tmp);
616 } END_FOR_EACH_PTR(tmp);
617 return ret;
618 }
619
620 struct range_list *clone_rl_permanent(struct range_list *list)
621 {
622 struct data_range *tmp;
623 struct data_range *new;
624 struct range_list *ret = NULL;
625
626 FOR_EACH_PTR(list, tmp) {
627 new = alloc_range_perm(tmp->min, tmp->max);
628 add_ptr_list(&ret, new);
629 } END_FOR_EACH_PTR(tmp);
630 return ret;
631 }
632
633 struct range_list *rl_union(struct range_list *one, struct range_list *two)
634 {
635 struct data_range *tmp;
636 struct range_list *ret = NULL;
637
638 FOR_EACH_PTR(one, tmp) {
639 add_range(&ret, tmp->min, tmp->max);
640 } END_FOR_EACH_PTR(tmp);
641 FOR_EACH_PTR(two, tmp) {
642 add_range(&ret, tmp->min, tmp->max);
643 } END_FOR_EACH_PTR(tmp);
644 return ret;
645 }
646
647 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
648 {
649 struct data_range *tmp;
650 struct range_list *ret = NULL;
651
652 FOR_EACH_PTR(list, tmp) {
653 if (sval_cmp(tmp->max, min) < 0) {
654 add_range(&ret, tmp->min, tmp->max);
655 continue;
656 }
657 if (sval_cmp(tmp->min, max) > 0) {
658 add_range(&ret, tmp->min, tmp->max);
659 continue;
660 }
661 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
662 continue;
663 if (sval_cmp(tmp->min, min) >= 0) {
664 max.value++;
665 add_range(&ret, max, tmp->max);
666 } else if (sval_cmp(tmp->max, max) <= 0) {
667 min.value--;
668 add_range(&ret, tmp->min, min);
669 } else {
670 min.value--;
671 max.value++;
672 add_range(&ret, tmp->min, min);
673 add_range(&ret, max, tmp->max);
674 }
675 } END_FOR_EACH_PTR(tmp);
676 return ret;
677 }
678
679 int ranges_equiv(struct data_range *one, struct data_range *two)
680 {
681 if (!one && !two)
682 return 1;
683 if (!one || !two)
684 return 0;
685 if (sval_cmp(one->min, two->min) != 0)
686 return 0;
687 if (sval_cmp(one->max, two->max) != 0)
688 return 0;
689 return 1;
690 }
691
692 int rl_equiv(struct range_list *one, struct range_list *two)
693 {
694 struct data_range *one_range;
695 struct data_range *two_range;
696
697 if (one == two)
698 return 1;
699
700 PREPARE_PTR_LIST(one, one_range);
701 PREPARE_PTR_LIST(two, two_range);
702 for (;;) {
703 if (!one_range && !two_range)
704 return 1;
705 if (!ranges_equiv(one_range, two_range))
706 return 0;
707 NEXT_PTR_LIST(one_range);
708 NEXT_PTR_LIST(two_range);
709 }
710 FINISH_PTR_LIST(two_range);
711 FINISH_PTR_LIST(one_range);
712
713 return 1;
714 }
715
716 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
717 {
718 switch (comparison) {
719 case '<':
720 case SPECIAL_UNSIGNED_LT:
721 if (sval_cmp(left->min, right->max) < 0)
722 return 1;
723 return 0;
724 case SPECIAL_UNSIGNED_LTE:
725 case SPECIAL_LTE:
726 if (sval_cmp(left->min, right->max) <= 0)
727 return 1;
728 return 0;
729 case SPECIAL_EQUAL:
730 if (sval_cmp(left->max, right->min) < 0)
731 return 0;
732 if (sval_cmp(left->min, right->max) > 0)
733 return 0;
734 return 1;
735 case SPECIAL_UNSIGNED_GTE:
736 case SPECIAL_GTE:
737 if (sval_cmp(left->max, right->min) >= 0)
738 return 1;
739 return 0;
740 case '>':
741 case SPECIAL_UNSIGNED_GT:
742 if (sval_cmp(left->max, right->min) > 0)
743 return 1;
744 return 0;
745 case SPECIAL_NOTEQUAL:
746 if (sval_cmp(left->min, left->max) != 0)
747 return 1;
748 if (sval_cmp(right->min, right->max) != 0)
749 return 1;
750 if (sval_cmp(left->min, right->min) != 0)
751 return 1;
752 return 0;
753 default:
754 sm_msg("unhandled comparison %d\n", comparison);
755 return 0;
756 }
757 return 0;
758 }
759
760 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
761 {
762 if (left)
763 return true_comparison_range(var, comparison, val);
764 else
765 return true_comparison_range(val, comparison, var);
766 }
767
768 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
769 {
770 switch (comparison) {
771 case '<':
772 case SPECIAL_UNSIGNED_LT:
773 if (sval_cmp(left->max, right->min) >= 0)
774 return 1;
775 return 0;
776 case SPECIAL_UNSIGNED_LTE:
777 case SPECIAL_LTE:
778 if (sval_cmp(left->max, right->min) > 0)
779 return 1;
780 return 0;
781 case SPECIAL_EQUAL:
782 if (sval_cmp(left->min, left->max) != 0)
783 return 1;
784 if (sval_cmp(right->min, right->max) != 0)
785 return 1;
786 if (sval_cmp(left->min, right->min) != 0)
787 return 1;
788 return 0;
789 case SPECIAL_UNSIGNED_GTE:
790 case SPECIAL_GTE:
791 if (sval_cmp(left->min, right->max) < 0)
792 return 1;
793 return 0;
794 case '>':
795 case SPECIAL_UNSIGNED_GT:
796 if (sval_cmp(left->min, right->max) <= 0)
797 return 1;
798 return 0;
799 case SPECIAL_NOTEQUAL:
800 if (sval_cmp(left->max, right->min) < 0)
801 return 0;
802 if (sval_cmp(left->min, right->max) > 0)
803 return 0;
804 return 1;
805 default:
806 sm_msg("unhandled comparison %d\n", comparison);
807 return 0;
808 }
809 return 0;
810 }
811
812 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
813 {
814 if (left)
815 return false_comparison_range_sval(var, comparison, val);
816 else
817 return false_comparison_range_sval(val, comparison, var);
818 }
819
820 int possibly_true(struct expression *left, int comparison, struct expression *right)
821 {
822 struct range_list *rl_left, *rl_right;
823 struct data_range *tmp_left, *tmp_right;
824 struct symbol *type;
825
826 if (!get_implied_rl(left, &rl_left))
827 return 1;
828 if (!get_implied_rl(right, &rl_right))
829 return 1;
830
831 type = rl_type(rl_left);
832 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
833 type = rl_type(rl_right);
834 if (type_positive_bits(type) < 31)
835 type = &int_ctype;
836
837 rl_left = cast_rl(type, rl_left);
838 rl_right = cast_rl(type, rl_right);
839
840 FOR_EACH_PTR(rl_left, tmp_left) {
841 FOR_EACH_PTR(rl_right, tmp_right) {
842 if (true_comparison_range(tmp_left, comparison, tmp_right))
843 return 1;
844 } END_FOR_EACH_PTR(tmp_right);
845 } END_FOR_EACH_PTR(tmp_left);
846 return 0;
847 }
848
849 int possibly_false(struct expression *left, int comparison, struct expression *right)
850 {
851 struct range_list *rl_left, *rl_right;
852 struct data_range *tmp_left, *tmp_right;
853 struct symbol *type;
854
855 if (!get_implied_rl(left, &rl_left))
856 return 1;
857 if (!get_implied_rl(right, &rl_right))
858 return 1;
859
860 type = rl_type(rl_left);
861 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
862 type = rl_type(rl_right);
863 if (type_positive_bits(type) < 31)
864 type = &int_ctype;
865
866 rl_left = cast_rl(type, rl_left);
867 rl_right = cast_rl(type, rl_right);
868
869 FOR_EACH_PTR(rl_left, tmp_left) {
870 FOR_EACH_PTR(rl_right, tmp_right) {
871 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
872 return 1;
873 } END_FOR_EACH_PTR(tmp_right);
874 } END_FOR_EACH_PTR(tmp_left);
875 return 0;
876 }
877
878 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
879 {
880 struct data_range *left_tmp, *right_tmp;
881
882 if (!left_ranges || !right_ranges)
883 return 1;
884
885 FOR_EACH_PTR(left_ranges, left_tmp) {
886 FOR_EACH_PTR(right_ranges, right_tmp) {
887 if (true_comparison_range(left_tmp, comparison, right_tmp))
888 return 1;
889 } END_FOR_EACH_PTR(right_tmp);
890 } END_FOR_EACH_PTR(left_tmp);
891 return 0;
892 }
893
894 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
895 {
896 struct data_range *left_tmp, *right_tmp;
897
898 if (!left_ranges || !right_ranges)
899 return 1;
900
901 FOR_EACH_PTR(left_ranges, left_tmp) {
902 FOR_EACH_PTR(right_ranges, right_tmp) {
903 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
904 return 1;
905 } END_FOR_EACH_PTR(right_tmp);
906 } END_FOR_EACH_PTR(left_tmp);
907 return 0;
908 }
909
910 /* FIXME: the _rl here stands for right left so really it should be _lr */
911 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
912 {
913 if (left)
914 return possibly_true_rl(a, comparison, b);
915 else
916 return possibly_true_rl(b, comparison, a);
917 }
918
919 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
920 {
921 if (left)
922 return possibly_false_rl(a, comparison, b);
923 else
924 return possibly_false_rl(b, comparison, a);
925 }
926
927 int rl_has_sval(struct range_list *rl, sval_t sval)
928 {
929 struct data_range *tmp;
930
931 FOR_EACH_PTR(rl, tmp) {
932 if (sval_cmp(tmp->min, sval) <= 0 &&
933 sval_cmp(tmp->max, sval) >= 0)
934 return 1;
935 } END_FOR_EACH_PTR(tmp);
936 return 0;
937 }
938
939 void tack_on(struct range_list **list, struct data_range *drange)
940 {
941 add_ptr_list(list, drange);
942 }
943
944 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
945 {
946 add_ptr_list(rl_stack, rl);
947 }
948
949 struct range_list *pop_rl(struct range_list_stack **rl_stack)
950 {
951 struct range_list *rl;
952
953 rl = last_ptr_list((struct ptr_list *)*rl_stack);
954 delete_ptr_list_last((struct ptr_list **)rl_stack);
955 return rl;
956 }
957
958 struct range_list *top_rl(struct range_list_stack *rl_stack)
959 {
960 struct range_list *rl;
961
962 rl = last_ptr_list((struct ptr_list *)rl_stack);
963 return rl;
964 }
965
966 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
967 {
968 struct range_list *rl;
969
970 rl = pop_rl(rl_stack);
971 rl = remove_range(rl, sval, sval);
972 push_rl(rl_stack, rl);
973 }
974
975 static int sval_too_big(struct symbol *type, sval_t sval)
976 {
977 if (type_bits(type) == 64)
978 return 0;
979 if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
980 return 1;
981 return 0;
982 }
983
984 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
985 {
986 /* If we're just adding a number, cast it and add it */
987 if (sval_cmp(min, max) == 0) {
988 add_range(rl, sval_cast(type, min), sval_cast(type, max));
989 return;
990 }
991
992 /* If the range is within the type range then add it */
993 if (sval_fits(type, min) && sval_fits(type, max)) {
994 add_range(rl, sval_cast(type, min), sval_cast(type, max));
995 return;
996 }
997
998 /*
999 * If the range we are adding has more bits than the range type then
1000 * add the whole range type. Eg:
1001 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
1002 * This isn't totally the right thing to do. We could be more granular.
1003 */
1004 if (sval_too_big(type, min) || sval_too_big(type, max)) {
1005 add_range(rl, sval_type_min(type), sval_type_max(type));
1006 return;
1007 }
1008
1009 /* Cast negative values to high positive values */
1010 if (sval_is_negative(min) && type_unsigned(type)) {
1011 if (sval_is_positive(max)) {
1012 if (sval_too_high(type, max)) {
1013 add_range(rl, sval_type_min(type), sval_type_max(type));
1014 return;
1015 }
1016 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
1017 max = sval_type_max(type);
1018 } else {
1019 max = sval_cast(type, max);
1020 }
1021 min = sval_cast(type, min);
1022 add_range(rl, min, max);
1023 }
1024
1025 /* Cast high positive numbers to negative */
1026 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
1027 if (!sval_is_negative(sval_cast(type, min))) {
1028 add_range(rl, sval_cast(type, min), sval_type_max(type));
1029 min = sval_type_min(type);
1030 } else {
1031 min = sval_cast(type, min);
1032 }
1033 max = sval_cast(type, max);
1034 add_range(rl, min, max);
1035 }
1036
1037 add_range(rl, min, max);
1038 return;
1039 }
1040
1041 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1042 {
1043 struct data_range *tmp;
1044 struct range_list *ret = NULL;
1045 sval_t min, max;
1046
1047 if (!rl)
1048 return NULL;
1049
1050 if (!type || type == rl_type(rl))
1051 return rl;
1052
1053 FOR_EACH_PTR(rl, tmp) {
1054 min = tmp->min;
1055 max = tmp->max;
1056 if (type_bits(type) < type_bits(rl_type(rl))) {
1057 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1058 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1059 }
1060 if (sval_cmp(min, max) > 0) {
1061 min = sval_cast(type, min);
1062 max = sval_cast(type, max);
1063 }
1064 add_range_t(type, &ret, min, max);
1065 } END_FOR_EACH_PTR(tmp);
1066
1067 return ret;
1068 }
1069
1070 static int rl_is_sane(struct range_list *rl)
1071 {
1072 struct data_range *tmp;
1073 struct symbol *type;
1074
1075 type = rl_type(rl);
1076 FOR_EACH_PTR(rl, tmp) {
1077 if (!sval_fits(type, tmp->min))
1078 return 0;
1079 if (!sval_fits(type, tmp->max))
1080 return 0;
1081 if (sval_cmp(tmp->min, tmp->max) > 0)
1082 return 0;
1083 } END_FOR_EACH_PTR(tmp);
1084
1085 return 1;
1086 }
1087
1088 static int rl_type_consistent(struct range_list *rl)
1089 {
1090 struct data_range *tmp;
1091 struct symbol *type;
1092
1093 type = rl_type(rl);
1094 FOR_EACH_PTR(rl, tmp) {
1095 if (type != tmp->min.type || type != tmp->max.type)
1096 return 0;
1097 } END_FOR_EACH_PTR(tmp);
1098 return 1;
1099 }
1100
1101 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1102 {
1103 struct data_range *tmp;
1104 struct range_list *ret = NULL;
1105
1106 if (!rl)
1107 return NULL;
1108
1109 if (!type)
1110 return rl;
1111 if (!rl_is_sane(rl))
1112 return alloc_whole_rl(type);
1113 if (type == rl_type(rl) && rl_type_consistent(rl))
1114 return rl;
1115
1116 FOR_EACH_PTR(rl, tmp) {
1117 add_range_t(type, &ret, tmp->min, tmp->max);
1118 } END_FOR_EACH_PTR(tmp);
1119
1120 if (!ret)
1121 return alloc_whole_rl(type);
1122
1123 return ret;
1124 }
1125
1126 struct range_list *rl_invert(struct range_list *orig)
1127 {
1128 struct range_list *ret = NULL;
1129 struct data_range *tmp;
1130 sval_t gap_min, abs_max, sval;
1131
1132 if (!orig)
1133 return NULL;
1134
1135 gap_min = sval_type_min(rl_min(orig).type);
1136 abs_max = sval_type_max(rl_max(orig).type);
1137
1138 FOR_EACH_PTR(orig, tmp) {
1139 if (sval_cmp(tmp->min, gap_min) > 0) {
1140 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1141 add_range(&ret, gap_min, sval);
1142 }
1143 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1144 if (sval_cmp(tmp->max, abs_max) == 0)
1145 gap_min = abs_max;
1146 } END_FOR_EACH_PTR(tmp);
1147
1148 if (sval_cmp(gap_min, abs_max) < 0)
1149 add_range(&ret, gap_min, abs_max);
1150
1151 return ret;
1152 }
1153
1154 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1155 {
1156 struct data_range *tmp;
1157
1158 FOR_EACH_PTR(filter, tmp) {
1159 rl = remove_range(rl, tmp->min, tmp->max);
1160 } END_FOR_EACH_PTR(tmp);
1161
1162 return rl;
1163 }
1164
1165 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1166 {
1167 struct range_list *one_orig;
1168 struct range_list *two_orig;
1169 struct range_list *ret;
1170 struct symbol *ret_type;
1171 struct symbol *small_type;
1172 struct symbol *large_type;
1173
1174 if (!two)
1175 return NULL;
1176 if (!one)
1177 return NULL;
1178
1179 one_orig = one;
1180 two_orig = two;
1181
1182 ret_type = rl_type(one);
1183 small_type = rl_type(one);
1184 large_type = rl_type(two);
1185
1186 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1187 small_type = rl_type(two);
1188 large_type = rl_type(one);
1189 }
1190
1191 one = cast_rl(large_type, one);
1192 two = cast_rl(large_type, two);
1193
1194 ret = one;
1195 one = rl_invert(one);
1196 two = rl_invert(two);
1197
1198 ret = rl_filter(ret, one);
1199 ret = rl_filter(ret, two);
1200
1201 one = cast_rl(small_type, one_orig);
1202 two = cast_rl(small_type, two_orig);
1203
1204 one = rl_invert(one);
1205 two = rl_invert(two);
1206
1207 ret = cast_rl(small_type, ret);
1208 ret = rl_filter(ret, one);
1209 ret = rl_filter(ret, two);
1210
1211 return cast_rl(ret_type, ret);
1212 }
1213
1214 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1215 {
1216 sval_t zero;
1217 sval_t max;
1218
1219 max = rl_max(right);
1220 if (sval_is_max(max))
1221 return left;
1222 if (max.value == 0)
1223 return NULL;
1224 max.value--;
1225 if (sval_is_negative(max))
1226 return NULL;
1227 if (sval_cmp(rl_max(left), max) < 0)
1228 return left;
1229 zero = max;
1230 zero.value = 0;
1231 return alloc_rl(zero, max);
1232 }
1233
1234 static struct range_list *get_neg_rl(struct range_list *rl)
1235 {
1236 struct data_range *tmp;
1237 struct range_list *ret = NULL;
1238
1239 if (!rl)
1240 return NULL;
1241 if (sval_is_positive(rl_min(rl)))
1242 return NULL;
1243
1244 FOR_EACH_PTR(rl, tmp) {
1245 if (sval_is_positive(tmp->min))
1246 return ret;
1247 if (sval_is_positive(tmp->max)) {
1248 tmp->max.value = -1;
1249 add_range(&ret, tmp->min, tmp->max);
1250 return ret;
1251 }
1252 add_range(&ret, tmp->min, tmp->max);
1253 } END_FOR_EACH_PTR(tmp);
1254
1255 return ret;
1256 }
1257
1258 static struct range_list *get_pos_rl(struct range_list *rl)
1259 {
1260 struct data_range *tmp;
1261 struct range_list *ret = NULL;
1262
1263 if (!rl)
1264 return NULL;
1265 if (sval_is_negative(rl_max(rl)))
1266 return NULL;
1267
1268 FOR_EACH_PTR(rl, tmp) {
1269 if (sval_is_negative(tmp->max))
1270 continue;
1271 if (sval_is_positive(tmp->min)) {
1272 add_range(&ret, tmp->min, tmp->max);
1273 continue;
1274 }
1275 tmp->min.value = 0;
1276 add_range(&ret, tmp->min, tmp->max);
1277 } END_FOR_EACH_PTR(tmp);
1278
1279 return ret;
1280 }
1281
1282 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1283 {
1284 sval_t right_min, right_max;
1285 sval_t min, max;
1286
1287 if (!left || !right)
1288 return NULL;
1289
1290 /* let's assume we never divide by zero */
1291 right_min = rl_min(right);
1292 right_max = rl_max(right);
1293 if (right_min.value == 0 && right_max.value == 0)
1294 return NULL;
1295 if (right_min.value == 0)
1296 right_min.value = 1;
1297 if (right_max.value == 0)
1298 right_max.value = -1;
1299
1300 max = sval_binop(rl_max(left), '/', right_min);
1301 min = sval_binop(rl_min(left), '/', right_max);
1302
1303 return alloc_rl(min, max);
1304 }
1305
1306 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1307 {
1308 struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1309 struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1310 struct range_list *ret;
1311
1312 if (is_whole_rl(left) || is_whole_rl(right))
1313 return NULL;
1314
1315 left_neg = get_neg_rl(left);
1316 left_pos = get_pos_rl(left);
1317 right_neg = get_neg_rl(right);
1318 right_pos = get_pos_rl(right);
1319
1320 neg_neg = divide_rl_helper(left_neg, right_neg);
1321 neg_pos = divide_rl_helper(left_neg, right_pos);
1322 pos_neg = divide_rl_helper(left_pos, right_neg);
1323 pos_pos = divide_rl_helper(left_pos, right_pos);
1324
1325 ret = rl_union(neg_neg, neg_pos);
1326 ret = rl_union(ret, pos_neg);
1327 return rl_union(ret, pos_pos);
1328 }
1329
1330 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1331 {
1332 sval_t min, max;
1333
1334 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1335 return NULL;
1336 min = sval_binop(rl_min(left), op, rl_min(right));
1337
1338 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1339 return NULL;
1340 max = sval_binop(rl_max(left), op, rl_max(right));
1341
1342 return alloc_rl(min, max);
1343 }
1344
1345 static unsigned long long sval_fls_mask(sval_t sval)
1346 {
1347 unsigned long long uvalue = sval.uvalue;
1348 unsigned long long high_bit = 0;
1349
1350 while (uvalue) {
1351 uvalue >>= 1;
1352 high_bit++;
1353 }
1354
1355 if (high_bit == 0)
1356 return 0;
1357
1358 return ((unsigned long long)-1) >> (64 - high_bit);
1359 }
1360
1361 static unsigned long long rl_bits_always_set(struct range_list *rl)
1362 {
1363 return sval_fls_mask(rl_min(rl));
1364 }
1365
1366 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1367 {
1368 return sval_fls_mask(rl_max(rl));
1369 }
1370
1371 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1372 {
1373 unsigned long long left_min, left_max, right_min, right_max;
1374 sval_t min, max;
1375 sval_t sval;
1376
1377 if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1378 !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1379 return rl_binop(left, '+', right);
1380
1381 left_min = rl_bits_always_set(left);
1382 left_max = rl_bits_maybe_set(left);
1383 right_min = rl_bits_always_set(right);
1384 right_max = rl_bits_maybe_set(right);
1385
1386 min.type = max.type = &ullong_ctype;
1387 min.uvalue = left_min | right_min;
1388 max.uvalue = left_max | right_max;
1389
1390 return cast_rl(rl_type(left), alloc_rl(min, max));
1391 }
1392
1393 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1394 {
1395 struct symbol *cast_type;
1396 sval_t left_sval, right_sval;
1397 struct range_list *ret = NULL;
1398
1399 cast_type = rl_type(left);
1400 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1401 cast_type = rl_type(right);
1402 if (sval_type_max(cast_type).uvalue < INT_MAX)
1403 cast_type = &int_ctype;
1404
1405 left = cast_rl(cast_type, left);
1406 right = cast_rl(cast_type, right);
1407
1408 if (!left || !right)
1409 return alloc_whole_rl(cast_type);
1410
1411 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1412 sval_t val = sval_binop(left_sval, op, right_sval);
1413 return alloc_rl(val, val);
1414 }
1415
1416 switch (op) {
1417 case '%':
1418 ret = handle_mod_rl(left, right);
1419 break;
1420 case '/':
1421 ret = handle_divide_rl(left, right);
1422 break;
1423 case '*':
1424 case '+':
1425 ret = handle_add_mult_rl(left, op, right);
1426 break;
1427 case '|':
1428 ret = handle_OR_rl(left, right);
1429 break;
1430
1431 /* FIXME: Do the rest as well */
1432 case '-':
1433 case '&':
1434 case SPECIAL_RIGHTSHIFT:
1435 case SPECIAL_LEFTSHIFT:
1436 case '^':
1437 break;
1438 }
1439
1440 if (!ret)
1441 ret = alloc_whole_rl(cast_type);
1442 return ret;
1443 }
1444
1445 void free_rl(struct range_list **rlist)
1446 {
1447 __free_ptr_list((struct ptr_list **)rlist);
1448 }
1449
1450 static void free_single_dinfo(struct data_info *dinfo)
1451 {
1452 free_rl(&dinfo->value_ranges);
1453 }
1454
1455 static void free_dinfos(struct allocation_blob *blob)
1456 {
1457 unsigned int size = sizeof(struct data_info);
1458 unsigned int offset = 0;
1459
1460 while (offset < blob->offset) {
1461 free_single_dinfo((struct data_info *)(blob->data + offset));
1462 offset += size;
1463 }
1464 }
1465
1466 void free_data_info_allocs(void)
1467 {
1468 struct allocator_struct *desc = &data_info_allocator;
1469 struct allocation_blob *blob = desc->blobs;
1470
1471 desc->blobs = NULL;
1472 desc->allocations = 0;
1473 desc->total_bytes = 0;
1474 desc->useful_bytes = 0;
1475 desc->freelist = NULL;
1476 while (blob) {
1477 struct allocation_blob *next = blob->next;
1478 free_dinfos(blob);
1479 blob_free(blob, desc->chunking);
1480 blob = next;
1481 }
1482 clear_data_range_alloc();
1483 }
1484
Static analysis for C