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