?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
helper: || vs && typo leads to segfault in is_array()
[smatch.git] / smatch_ranges.c
blobf284682ac69dc73ad26eef2cbeaf8dd7019d9138
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 *value, struct range_list **rl)
314 {
315 sval_t min, max;
316 char *call_math;
317 char *c;
318
319 if (!type)
320 type = &llong_ctype;
321 *rl = NULL;
322
323 if (strcmp(value, "empty") == 0)
324 return;
325
326 if (strncmp(value, "[==$", 4) == 0) {
327 struct expression *arg;
328 int comparison;
329
330 if (!str_to_comparison_arg(value, call, &comparison, &arg))
331 return;
332 if (!get_implied_rl(arg, rl))
333 return;
334 goto cast;
335 }
336
337 call_math = jump_to_call_math(value);
338 if (call_math && parse_call_math_rl(call, call_math, rl))
339 goto cast;
340
341 min = sval_type_min(type);
342 max = sval_type_max(type);
343 c = value;
344 while (*c != '\0' && *c != '[') {
345 if (*c == '(')
346 c++;
347 min = parse_val(0, call, type, c, &c);
348 max = min;
349 if (*c == ')')
350 c++;
351 if (*c == '\0' || *c == '[') {
352 add_range(rl, min, min);
353 break;
354 }
355 if (*c == ',') {
356 add_range(rl, min, min);
357 c++;
358 continue;
359 }
360 if (*c != '-') {
361 sm_msg("debug XXX: trouble parsing %s c = %s", value, c);
362 break;
363 }
364 c++;
365 if (*c == '(')
366 c++;
367 max = parse_val(1, call, type, c, &c);
368 add_range(rl, min, max);
369 if (*c == ')')
370 c++;
371 if (*c == ',')
372 c++;
373 }
374
375 if (*c == '\0')
376 goto cast;
377
378 /*
379 * For now if we already tried to handle the call math and couldn't
380 * figure it out then bail.
381 */
382 if (jump_to_call_math(c) == c + 1)
383 goto cast;
384
385
386 *rl = filter_by_comparison_call(c, call, &c, *rl);
387
388 cast:
389 *rl = cast_rl(type, *rl);
390 }
391
392 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
393 {
394 return str_to_rl_helper(NULL, type, value, rl);
395 }
396
397 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
398 {
399 return str_to_rl_helper(strip_expr(expr), type, value, rl);
400 }
401
402 int is_whole_rl(struct range_list *rl)
403 {
404 struct data_range *drange;
405
406 if (ptr_list_empty(rl))
407 return 0;
408 drange = first_ptr_list((struct ptr_list *)rl);
409 if (sval_is_min(drange->min) && sval_is_max(drange->max))
410 return 1;
411 return 0;
412 }
413
414 sval_t rl_min(struct range_list *rl)
415 {
416 struct data_range *drange;
417 sval_t ret;
418
419 ret.type = &llong_ctype;
420 ret.value = LLONG_MIN;
421 if (ptr_list_empty(rl))
422 return ret;
423 drange = first_ptr_list((struct ptr_list *)rl);
424 return drange->min;
425 }
426
427 sval_t rl_max(struct range_list *rl)
428 {
429 struct data_range *drange;
430 sval_t ret;
431
432 ret.type = &llong_ctype;
433 ret.value = LLONG_MAX;
434 if (ptr_list_empty(rl))
435 return ret;
436 drange = last_ptr_list((struct ptr_list *)rl);
437 return drange->max;
438 }
439
440 int rl_to_sval(struct range_list *rl, sval_t *sval)
441 {
442 sval_t min, max;
443
444 if (!rl)
445 return 0;
446
447 min = rl_min(rl);
448 max = rl_max(rl);
449 if (sval_cmp(min, max) != 0)
450 return 0;
451 *sval = min;
452 return 1;
453 }
454
455 struct symbol *rl_type(struct range_list *rl)
456 {
457 if (!rl)
458 return NULL;
459 return rl_min(rl).type;
460 }
461
462 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
463 {
464 struct data_range *ret;
465
466 if (perm)
467 ret = __alloc_perm_data_range(0);
468 else
469 ret = __alloc_data_range(0);
470 ret->min = min;
471 ret->max = max;
472 return ret;
473 }
474
475 struct data_range *alloc_range(sval_t min, sval_t max)
476 {
477 return alloc_range_helper_sval(min, max, 0);
478 }
479
480 struct data_range *alloc_range_perm(sval_t min, sval_t max)
481 {
482 return alloc_range_helper_sval(min, max, 1);
483 }
484
485 struct range_list *alloc_rl(sval_t min, sval_t max)
486 {
487 struct range_list *rl = NULL;
488
489 if (sval_cmp(min, max) > 0)
490 return alloc_whole_rl(min.type);
491
492 add_range(&rl, min, max);
493 return rl;
494 }
495
496 struct range_list *alloc_whole_rl(struct symbol *type)
497 {
498 if (!type || type_positive_bits(type) < 0)
499 type = &llong_ctype;
500 if (type->type == SYM_ARRAY)
501 type = &ptr_ctype;
502
503 return alloc_rl(sval_type_min(type), sval_type_max(type));
504 }
505
506 void add_range(struct range_list **list, sval_t min, sval_t max)
507 {
508 struct data_range *tmp = NULL;
509 struct data_range *new = NULL;
510 int check_next = 0;
511
512 /*
513 * FIXME: This has a problem merging a range_list like: min-0,3-max
514 * with a range like 1-2. You end up with min-2,3-max instead of
515 * just min-max.
516 */
517 FOR_EACH_PTR(*list, tmp) {
518 if (check_next) {
519 /* Sometimes we overlap with more than one range
520 so we have to delete or modify the next range. */
521 if (max.value + 1 == tmp->min.value) {
522 /* join 2 ranges here */
523 new->max = tmp->max;
524 DELETE_CURRENT_PTR(tmp);
525 return;
526 }
527
528 /* Doesn't overlap with the next one. */
529 if (sval_cmp(max, tmp->min) < 0)
530 return;
531 /* Partially overlaps with the next one. */
532 if (sval_cmp(max, tmp->max) < 0) {
533 tmp->min.value = max.value + 1;
534 return;
535 }
536 /* Completely overlaps with the next one. */
537 if (sval_cmp(max, tmp->max) >= 0) {
538 DELETE_CURRENT_PTR(tmp);
539 /* there could be more ranges to delete */
540 continue;
541 }
542 }
543 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
544 /* join 2 ranges into a big range */
545 new = alloc_range(min, tmp->max);
546 REPLACE_CURRENT_PTR(tmp, new);
547 return;
548 }
549 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
550 new = alloc_range(min, max);
551 INSERT_CURRENT(new, tmp);
552 return;
553 }
554 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
555 if (sval_cmp(max, tmp->max) < 0)
556 max = tmp->max;
557 else
558 check_next = 1;
559 new = alloc_range(min, max);
560 REPLACE_CURRENT_PTR(tmp, new);
561 if (!check_next)
562 return;
563 continue;
564 }
565 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
566 return;
567 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
568 min = tmp->min;
569 new = alloc_range(min, max);
570 REPLACE_CURRENT_PTR(tmp, new);
571 check_next = 1;
572 continue;
573 }
574 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
575 /* join 2 ranges into a big range */
576 new = alloc_range(tmp->min, max);
577 REPLACE_CURRENT_PTR(tmp, new);
578 check_next = 1;
579 continue;
580 }
581 /* the new range is entirely above the existing ranges */
582 } END_FOR_EACH_PTR(tmp);
583 if (check_next)
584 return;
585 new = alloc_range(min, max);
586 add_ptr_list(list, new);
587 }
588
589 struct range_list *clone_rl(struct range_list *list)
590 {
591 struct data_range *tmp;
592 struct range_list *ret = NULL;
593
594 FOR_EACH_PTR(list, tmp) {
595 add_ptr_list(&ret, tmp);
596 } END_FOR_EACH_PTR(tmp);
597 return ret;
598 }
599
600 struct range_list *clone_rl_permanent(struct range_list *list)
601 {
602 struct data_range *tmp;
603 struct data_range *new;
604 struct range_list *ret = NULL;
605
606 FOR_EACH_PTR(list, tmp) {
607 new = alloc_range_perm(tmp->min, tmp->max);
608 add_ptr_list(&ret, new);
609 } END_FOR_EACH_PTR(tmp);
610 return ret;
611 }
612
613 struct range_list *rl_union(struct range_list *one, struct range_list *two)
614 {
615 struct data_range *tmp;
616 struct range_list *ret = NULL;
617
618 FOR_EACH_PTR(one, tmp) {
619 add_range(&ret, tmp->min, tmp->max);
620 } END_FOR_EACH_PTR(tmp);
621 FOR_EACH_PTR(two, tmp) {
622 add_range(&ret, tmp->min, tmp->max);
623 } END_FOR_EACH_PTR(tmp);
624 return ret;
625 }
626
627 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
628 {
629 struct data_range *tmp;
630 struct range_list *ret = NULL;
631
632 FOR_EACH_PTR(list, tmp) {
633 if (sval_cmp(tmp->max, min) < 0) {
634 add_range(&ret, tmp->min, tmp->max);
635 continue;
636 }
637 if (sval_cmp(tmp->min, max) > 0) {
638 add_range(&ret, tmp->min, tmp->max);
639 continue;
640 }
641 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
642 continue;
643 if (sval_cmp(tmp->min, min) >= 0) {
644 max.value++;
645 add_range(&ret, max, tmp->max);
646 } else if (sval_cmp(tmp->max, max) <= 0) {
647 min.value--;
648 add_range(&ret, tmp->min, min);
649 } else {
650 min.value--;
651 max.value++;
652 add_range(&ret, tmp->min, min);
653 add_range(&ret, max, tmp->max);
654 }
655 } END_FOR_EACH_PTR(tmp);
656 return ret;
657 }
658
659 int ranges_equiv(struct data_range *one, struct data_range *two)
660 {
661 if (!one && !two)
662 return 1;
663 if (!one || !two)
664 return 0;
665 if (sval_cmp(one->min, two->min) != 0)
666 return 0;
667 if (sval_cmp(one->max, two->max) != 0)
668 return 0;
669 return 1;
670 }
671
672 int rl_equiv(struct range_list *one, struct range_list *two)
673 {
674 struct data_range *one_range;
675 struct data_range *two_range;
676
677 if (one == two)
678 return 1;
679
680 PREPARE_PTR_LIST(one, one_range);
681 PREPARE_PTR_LIST(two, two_range);
682 for (;;) {
683 if (!one_range && !two_range)
684 return 1;
685 if (!ranges_equiv(one_range, two_range))
686 return 0;
687 NEXT_PTR_LIST(one_range);
688 NEXT_PTR_LIST(two_range);
689 }
690 FINISH_PTR_LIST(two_range);
691 FINISH_PTR_LIST(one_range);
692
693 return 1;
694 }
695
696 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
697 {
698 switch (comparison) {
699 case '<':
700 case SPECIAL_UNSIGNED_LT:
701 if (sval_cmp(left->min, right->max) < 0)
702 return 1;
703 return 0;
704 case SPECIAL_UNSIGNED_LTE:
705 case SPECIAL_LTE:
706 if (sval_cmp(left->min, right->max) <= 0)
707 return 1;
708 return 0;
709 case SPECIAL_EQUAL:
710 if (sval_cmp(left->max, right->min) < 0)
711 return 0;
712 if (sval_cmp(left->min, right->max) > 0)
713 return 0;
714 return 1;
715 case SPECIAL_UNSIGNED_GTE:
716 case SPECIAL_GTE:
717 if (sval_cmp(left->max, right->min) >= 0)
718 return 1;
719 return 0;
720 case '>':
721 case SPECIAL_UNSIGNED_GT:
722 if (sval_cmp(left->max, right->min) > 0)
723 return 1;
724 return 0;
725 case SPECIAL_NOTEQUAL:
726 if (sval_cmp(left->min, left->max) != 0)
727 return 1;
728 if (sval_cmp(right->min, right->max) != 0)
729 return 1;
730 if (sval_cmp(left->min, right->min) != 0)
731 return 1;
732 return 0;
733 default:
734 sm_msg("unhandled comparison %d\n", comparison);
735 return 0;
736 }
737 return 0;
738 }
739
740 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
741 {
742 if (left)
743 return true_comparison_range(var, comparison, val);
744 else
745 return true_comparison_range(val, comparison, var);
746 }
747
748 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
749 {
750 switch (comparison) {
751 case '<':
752 case SPECIAL_UNSIGNED_LT:
753 if (sval_cmp(left->max, right->min) >= 0)
754 return 1;
755 return 0;
756 case SPECIAL_UNSIGNED_LTE:
757 case SPECIAL_LTE:
758 if (sval_cmp(left->max, right->min) > 0)
759 return 1;
760 return 0;
761 case SPECIAL_EQUAL:
762 if (sval_cmp(left->min, left->max) != 0)
763 return 1;
764 if (sval_cmp(right->min, right->max) != 0)
765 return 1;
766 if (sval_cmp(left->min, right->min) != 0)
767 return 1;
768 return 0;
769 case SPECIAL_UNSIGNED_GTE:
770 case SPECIAL_GTE:
771 if (sval_cmp(left->min, right->max) < 0)
772 return 1;
773 return 0;
774 case '>':
775 case SPECIAL_UNSIGNED_GT:
776 if (sval_cmp(left->min, right->max) <= 0)
777 return 1;
778 return 0;
779 case SPECIAL_NOTEQUAL:
780 if (sval_cmp(left->max, right->min) < 0)
781 return 0;
782 if (sval_cmp(left->min, right->max) > 0)
783 return 0;
784 return 1;
785 default:
786 sm_msg("unhandled comparison %d\n", comparison);
787 return 0;
788 }
789 return 0;
790 }
791
792 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
793 {
794 if (left)
795 return false_comparison_range_sval(var, comparison, val);
796 else
797 return false_comparison_range_sval(val, comparison, var);
798 }
799
800 int possibly_true(struct expression *left, int comparison, struct expression *right)
801 {
802 struct range_list *rl_left, *rl_right;
803 struct data_range *tmp_left, *tmp_right;
804 struct symbol *type;
805
806 if (!get_implied_rl(left, &rl_left))
807 return 1;
808 if (!get_implied_rl(right, &rl_right))
809 return 1;
810
811 type = rl_type(rl_left);
812 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
813 type = rl_type(rl_right);
814 if (type_positive_bits(type) < 31)
815 type = &int_ctype;
816
817 rl_left = cast_rl(type, rl_left);
818 rl_right = cast_rl(type, rl_right);
819
820 FOR_EACH_PTR(rl_left, tmp_left) {
821 FOR_EACH_PTR(rl_right, tmp_right) {
822 if (true_comparison_range(tmp_left, comparison, tmp_right))
823 return 1;
824 } END_FOR_EACH_PTR(tmp_right);
825 } END_FOR_EACH_PTR(tmp_left);
826 return 0;
827 }
828
829 int possibly_false(struct expression *left, int comparison, struct expression *right)
830 {
831 struct range_list *rl_left, *rl_right;
832 struct data_range *tmp_left, *tmp_right;
833 struct symbol *type;
834
835 if (!get_implied_rl(left, &rl_left))
836 return 1;
837 if (!get_implied_rl(right, &rl_right))
838 return 1;
839
840 type = rl_type(rl_left);
841 if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
842 type = rl_type(rl_right);
843 if (type_positive_bits(type) < 31)
844 type = &int_ctype;
845
846 rl_left = cast_rl(type, rl_left);
847 rl_right = cast_rl(type, rl_right);
848
849 FOR_EACH_PTR(rl_left, tmp_left) {
850 FOR_EACH_PTR(rl_right, tmp_right) {
851 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
852 return 1;
853 } END_FOR_EACH_PTR(tmp_right);
854 } END_FOR_EACH_PTR(tmp_left);
855 return 0;
856 }
857
858 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
859 {
860 struct data_range *left_tmp, *right_tmp;
861
862 if (!left_ranges || !right_ranges)
863 return 1;
864
865 FOR_EACH_PTR(left_ranges, left_tmp) {
866 FOR_EACH_PTR(right_ranges, right_tmp) {
867 if (true_comparison_range(left_tmp, comparison, right_tmp))
868 return 1;
869 } END_FOR_EACH_PTR(right_tmp);
870 } END_FOR_EACH_PTR(left_tmp);
871 return 0;
872 }
873
874 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
875 {
876 struct data_range *left_tmp, *right_tmp;
877
878 if (!left_ranges || !right_ranges)
879 return 1;
880
881 FOR_EACH_PTR(left_ranges, left_tmp) {
882 FOR_EACH_PTR(right_ranges, right_tmp) {
883 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
884 return 1;
885 } END_FOR_EACH_PTR(right_tmp);
886 } END_FOR_EACH_PTR(left_tmp);
887 return 0;
888 }
889
890 /* FIXME: the _rl here stands for right left so really it should be _lr */
891 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
892 {
893 if (left)
894 return possibly_true_rl(a, comparison, b);
895 else
896 return possibly_true_rl(b, comparison, a);
897 }
898
899 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
900 {
901 if (left)
902 return possibly_false_rl(a, comparison, b);
903 else
904 return possibly_false_rl(b, comparison, a);
905 }
906
907 int rl_has_sval(struct range_list *rl, sval_t sval)
908 {
909 struct data_range *tmp;
910
911 FOR_EACH_PTR(rl, tmp) {
912 if (sval_cmp(tmp->min, sval) <= 0 &&
913 sval_cmp(tmp->max, sval) >= 0)
914 return 1;
915 } END_FOR_EACH_PTR(tmp);
916 return 0;
917 }
918
919 void tack_on(struct range_list **list, struct data_range *drange)
920 {
921 add_ptr_list(list, drange);
922 }
923
924 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
925 {
926 add_ptr_list(rl_stack, rl);
927 }
928
929 struct range_list *pop_rl(struct range_list_stack **rl_stack)
930 {
931 struct range_list *rl;
932
933 rl = last_ptr_list((struct ptr_list *)*rl_stack);
934 delete_ptr_list_last((struct ptr_list **)rl_stack);
935 return rl;
936 }
937
938 struct range_list *top_rl(struct range_list_stack *rl_stack)
939 {
940 struct range_list *rl;
941
942 rl = last_ptr_list((struct ptr_list *)rl_stack);
943 return rl;
944 }
945
946 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
947 {
948 struct range_list *rl;
949
950 rl = pop_rl(rl_stack);
951 rl = remove_range(rl, sval, sval);
952 push_rl(rl_stack, rl);
953 }
954
955 static int sval_too_big(struct symbol *type, sval_t sval)
956 {
957 if (type_bits(type) == 64)
958 return 0;
959 if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
960 return 1;
961 return 0;
962 }
963
964 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
965 {
966 /* If we're just adding a number, cast it and add it */
967 if (sval_cmp(min, max) == 0) {
968 add_range(rl, sval_cast(type, min), sval_cast(type, max));
969 return;
970 }
971
972 /* If the range is within the type range then add it */
973 if (sval_fits(type, min) && sval_fits(type, max)) {
974 add_range(rl, sval_cast(type, min), sval_cast(type, max));
975 return;
976 }
977
978 /*
979 * If the range we are adding has more bits than the range type then
980 * add the whole range type. Eg:
981 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
982 * This isn't totally the right thing to do. We could be more granular.
983 */
984 if (sval_too_big(type, min) || sval_too_big(type, max)) {
985 add_range(rl, sval_type_min(type), sval_type_max(type));
986 return;
987 }
988
989 /* Cast negative values to high positive values */
990 if (sval_is_negative(min) && type_unsigned(type)) {
991 if (sval_is_positive(max)) {
992 if (sval_too_high(type, max)) {
993 add_range(rl, sval_type_min(type), sval_type_max(type));
994 return;
995 }
996 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
997 max = sval_type_max(type);
998 } else {
999 max = sval_cast(type, max);
1000 }
1001 min = sval_cast(type, min);
1002 add_range(rl, min, max);
1003 }
1004
1005 /* Cast high positive numbers to negative */
1006 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
1007 if (!sval_is_negative(sval_cast(type, min))) {
1008 add_range(rl, sval_cast(type, min), sval_type_max(type));
1009 min = sval_type_min(type);
1010 } else {
1011 min = sval_cast(type, min);
1012 }
1013 max = sval_cast(type, max);
1014 add_range(rl, min, max);
1015 }
1016
1017 add_range(rl, min, max);
1018 return;
1019 }
1020
1021 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1022 {
1023 struct data_range *tmp;
1024 struct range_list *ret = NULL;
1025 sval_t min, max;
1026
1027 if (!rl)
1028 return NULL;
1029
1030 if (!type || type == rl_type(rl))
1031 return rl;
1032
1033 FOR_EACH_PTR(rl, tmp) {
1034 min = tmp->min;
1035 max = tmp->max;
1036 if (type_bits(type) < type_bits(rl_type(rl))) {
1037 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1038 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1039 }
1040 if (sval_cmp(min, max) > 0) {
1041 min = sval_cast(type, min);
1042 max = sval_cast(type, max);
1043 }
1044 add_range_t(type, &ret, min, max);
1045 } END_FOR_EACH_PTR(tmp);
1046
1047 return ret;
1048 }
1049
1050 static int rl_is_sane(struct range_list *rl)
1051 {
1052 struct data_range *tmp;
1053 struct symbol *type;
1054
1055 type = rl_type(rl);
1056 FOR_EACH_PTR(rl, tmp) {
1057 if (!sval_fits(type, tmp->min))
1058 return 0;
1059 if (!sval_fits(type, tmp->max))
1060 return 0;
1061 if (sval_cmp(tmp->min, tmp->max) > 0)
1062 return 0;
1063 } END_FOR_EACH_PTR(tmp);
1064
1065 return 1;
1066 }
1067
1068 static int rl_type_consistent(struct range_list *rl)
1069 {
1070 struct data_range *tmp;
1071 struct symbol *type;
1072
1073 type = rl_type(rl);
1074 FOR_EACH_PTR(rl, tmp) {
1075 if (type != tmp->min.type || type != tmp->max.type)
1076 return 0;
1077 } END_FOR_EACH_PTR(tmp);
1078 return 1;
1079 }
1080
1081 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1082 {
1083 struct data_range *tmp;
1084 struct range_list *ret = NULL;
1085
1086 if (!rl)
1087 return NULL;
1088
1089 if (!type)
1090 return rl;
1091 if (!rl_is_sane(rl))
1092 return alloc_whole_rl(type);
1093 if (type == rl_type(rl) && rl_type_consistent(rl))
1094 return rl;
1095
1096 FOR_EACH_PTR(rl, tmp) {
1097 add_range_t(type, &ret, tmp->min, tmp->max);
1098 } END_FOR_EACH_PTR(tmp);
1099
1100 if (!ret)
1101 return alloc_whole_rl(type);
1102
1103 return ret;
1104 }
1105
1106 struct range_list *rl_invert(struct range_list *orig)
1107 {
1108 struct range_list *ret = NULL;
1109 struct data_range *tmp;
1110 sval_t gap_min, abs_max, sval;
1111
1112 if (!orig)
1113 return NULL;
1114
1115 gap_min = sval_type_min(rl_min(orig).type);
1116 abs_max = sval_type_max(rl_max(orig).type);
1117
1118 FOR_EACH_PTR(orig, tmp) {
1119 if (sval_cmp(tmp->min, gap_min) > 0) {
1120 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
1121 add_range(&ret, gap_min, sval);
1122 }
1123 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
1124 if (sval_cmp(tmp->max, abs_max) == 0)
1125 gap_min = abs_max;
1126 } END_FOR_EACH_PTR(tmp);
1127
1128 if (sval_cmp(gap_min, abs_max) < 0)
1129 add_range(&ret, gap_min, abs_max);
1130
1131 return ret;
1132 }
1133
1134 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1135 {
1136 struct data_range *tmp;
1137
1138 FOR_EACH_PTR(filter, tmp) {
1139 rl = remove_range(rl, tmp->min, tmp->max);
1140 } END_FOR_EACH_PTR(tmp);
1141
1142 return rl;
1143 }
1144
1145 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1146 {
1147 struct range_list *one_orig;
1148 struct range_list *two_orig;
1149 struct range_list *ret;
1150 struct symbol *ret_type;
1151 struct symbol *small_type;
1152 struct symbol *large_type;
1153
1154 if (!two)
1155 return NULL;
1156 if (!one)
1157 return NULL;
1158
1159 one_orig = one;
1160 two_orig = two;
1161
1162 ret_type = rl_type(one);
1163 small_type = rl_type(one);
1164 large_type = rl_type(two);
1165
1166 if (type_bits(rl_type(two)) < type_bits(small_type)) {
1167 small_type = rl_type(two);
1168 large_type = rl_type(one);
1169 }
1170
1171 one = cast_rl(large_type, one);
1172 two = cast_rl(large_type, two);
1173
1174 ret = one;
1175 one = rl_invert(one);
1176 two = rl_invert(two);
1177
1178 ret = rl_filter(ret, one);
1179 ret = rl_filter(ret, two);
1180
1181 one = cast_rl(small_type, one_orig);
1182 two = cast_rl(small_type, two_orig);
1183
1184 one = rl_invert(one);
1185 two = rl_invert(two);
1186
1187 ret = cast_rl(small_type, ret);
1188 ret = rl_filter(ret, one);
1189 ret = rl_filter(ret, two);
1190
1191 return cast_rl(ret_type, ret);
1192 }
1193
1194 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1195 {
1196 sval_t zero;
1197 sval_t max;
1198
1199 max = rl_max(right);
1200 if (sval_is_max(max))
1201 return left;
1202 if (max.value == 0)
1203 return NULL;
1204 max.value--;
1205 if (sval_is_negative(max))
1206 return NULL;
1207 if (sval_cmp(rl_max(left), max) < 0)
1208 return left;
1209 zero = max;
1210 zero.value = 0;
1211 return alloc_rl(zero, max);
1212 }
1213
1214 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1215 {
1216 sval_t min, max;
1217
1218 if (sval_is_max(rl_max(left)))
1219 return NULL;
1220 if (sval_is_max(rl_max(right)))
1221 return NULL;
1222
1223 if (sval_is_negative(rl_min(left)))
1224 return NULL;
1225 if (sval_cmp_val(rl_min(right), 0) <= 0)
1226 return NULL;
1227
1228 max = sval_binop(rl_max(left), '/', rl_min(right));
1229 min = sval_binop(rl_min(left), '/', rl_max(right));
1230
1231 return alloc_rl(min, max);
1232 }
1233
1234 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1235 {
1236 sval_t min, max;
1237
1238 if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1239 return NULL;
1240 min = sval_binop(rl_min(left), op, rl_min(right));
1241
1242 if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1243 return NULL;
1244 max = sval_binop(rl_max(left), op, rl_max(right));
1245
1246 return alloc_rl(min, max);
1247 }
1248
1249 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1250 {
1251 struct symbol *cast_type;
1252 sval_t left_sval, right_sval;
1253 struct range_list *ret = NULL;
1254
1255 cast_type = rl_type(left);
1256 if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1257 cast_type = rl_type(right);
1258 if (sval_type_max(cast_type).uvalue < INT_MAX)
1259 cast_type = &int_ctype;
1260
1261 left = cast_rl(cast_type, left);
1262 right = cast_rl(cast_type, right);
1263
1264 if (!left || !right)
1265 return alloc_whole_rl(cast_type);
1266
1267 if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
1268 sval_t val = sval_binop(left_sval, op, right_sval);
1269 return alloc_rl(val, val);
1270 }
1271
1272 switch (op) {
1273 case '%':
1274 ret = handle_mod_rl(left, right);
1275 break;
1276 case '/':
1277 ret = handle_divide_rl(left, right);
1278 break;
1279 case '*':
1280 case '+':
1281 ret = handle_add_mult_rl(left, op, right);
1282 break;
1283
1284 /* FIXME: Do the rest as well */
1285 case '-':
1286 case '|':
1287 case '&':
1288 case SPECIAL_RIGHTSHIFT:
1289 case SPECIAL_LEFTSHIFT:
1290 case '^':
1291 break;
1292 }
1293
1294 if (!ret)
1295 ret = alloc_whole_rl(cast_type);
1296 return ret;
1297 }
1298
1299 void free_rl(struct range_list **rlist)
1300 {
1301 __free_ptr_list((struct ptr_list **)rlist);
1302 }
1303
1304 static void free_single_dinfo(struct data_info *dinfo)
1305 {
1306 free_rl(&dinfo->value_ranges);
1307 }
1308
1309 static void free_dinfos(struct allocation_blob *blob)
1310 {
1311 unsigned int size = sizeof(struct data_info);
1312 unsigned int offset = 0;
1313
1314 while (offset < blob->offset) {
1315 free_single_dinfo((struct data_info *)(blob->data + offset));
1316 offset += size;
1317 }
1318 }
1319
1320 void free_data_info_allocs(void)
1321 {
1322 struct allocator_struct *desc = &data_info_allocator;
1323 struct allocation_blob *blob = desc->blobs;
1324
1325 desc->blobs = NULL;
1326 desc->allocations = 0;
1327 desc->total_bytes = 0;
1328 desc->useful_bytes = 0;
1329 desc->freelist = NULL;
1330 while (blob) {
1331 struct allocation_blob *next = blob->next;
1332 free_dinfos(blob);
1333 blob_free(blob, desc->chunking);
1334 blob = next;
1335 }
1336 clear_data_range_alloc();
1337 }
1338
Static analysis for C