?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
db: remove bogus parameter information from hook type functions
[smatch.git] / smatch_ranges.c
blob7b14ed47bd860467db23f7fec859583a335c8bb9
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 {
82 return 0;
83 }
84
85 if (*c != 'p')
86 return 0;
87 c++;
88
89 param = strtoll(c, &c, 10);
90 c++; /* skip the ']' character */
91 if (endp)
92 *endp = (char *)c;
93
94 if (!call)
95 return 0;
96 *arg = get_argument_from_call_expr(call->args, param);
97 if (!*arg)
98 return 0;
99 return 1;
100 }
101
102 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
103 {
104 while (1) {
105 if (!*str)
106 return 0;
107 if (*str == '[')
108 break;
109 str++;
110 }
111 return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
112 }
113
114 static sval_t get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp)
115 {
116 struct expression *arg;
117 int comparison;
118 sval_t ret, tmp;
119
120 if (use_max)
121 ret = sval_type_max(type);
122 else
123 ret = sval_type_min(type);
124
125 if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
126 return ret;
127
128 if (use_max && get_implied_max(arg, &tmp)) {
129 ret = tmp;
130 if (comparison == '<') {
131 tmp.value = 1;
132 ret = sval_binop(ret, '-', tmp);
133 }
134 }
135 if (!use_max && get_implied_min(arg, &tmp)) {
136 ret = tmp;
137 if (comparison == '>') {
138 tmp.value = 1;
139 ret = sval_binop(ret, '+', tmp);
140 }
141 }
142
143 return ret;
144 }
145
146 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
147 {
148 char *start = c;
149 sval_t ret;
150
151 if (!strncmp(start, "max", 3)) {
152 ret = sval_type_max(type);
153 c += 3;
154 } else if (!strncmp(start, "u64max", 6)) {
155 ret = sval_type_val(type, ULLONG_MAX);
156 c += 6;
157 } else if (!strncmp(start, "s64max", 6)) {
158 ret = sval_type_val(type, LLONG_MAX);
159 c += 6;
160 } else if (!strncmp(start, "u32max", 6)) {
161 ret = sval_type_val(type, UINT_MAX);
162 c += 6;
163 } else if (!strncmp(start, "s32max", 6)) {
164 ret = sval_type_val(type, INT_MAX);
165 c += 6;
166 } else if (!strncmp(start, "u16max", 6)) {
167 ret = sval_type_val(type, USHRT_MAX);
168 c += 6;
169 } else if (!strncmp(start, "s16max", 6)) {
170 ret = sval_type_val(type, SHRT_MAX);
171 c += 6;
172 } else if (!strncmp(start, "min", 3)) {
173 ret = sval_type_min(type);
174 c += 3;
175 } else if (!strncmp(start, "s64min", 6)) {
176 ret = sval_type_val(type, LLONG_MIN);
177 c += 6;
178 } else if (!strncmp(start, "s32min", 6)) {
179 ret = sval_type_val(type, INT_MIN);
180 c += 6;
181 } else if (!strncmp(start, "s16min", 6)) {
182 ret = sval_type_val(type, SHRT_MIN);
183 c += 6;
184 } else if (start[0] == '[') {
185 /* this parses [==p0] comparisons */
186 ret = get_val_from_key(1, type, start, call, &c);
187 } else {
188 ret = sval_type_val(type, strtoll(start, &c, 10));
189 }
190 *endp = c;
191 return ret;
192 }
193
194 static void str_to_rl_helper(struct expression *call, struct symbol *type, char *value, struct range_list **rl)
195 {
196 sval_t min, max, arg_max;
197 char *c;
198
199 if (!type)
200 type = &llong_ctype;
201 *rl = NULL;
202
203 if (strcmp(value, "empty") == 0)
204 return;
205
206 if (strncmp(value, "[==p", 4) == 0) {
207 struct expression *arg;
208 int comparison;
209
210 if (!str_to_comparison_arg(value, call, &comparison, &arg))
211 goto out;
212 get_implied_rl(arg, rl);
213 goto out;
214 }
215
216 c = value;
217 while (*c) {
218 if (*c == '(')
219 c++;
220 min = parse_val(0, call, type, c, &c);
221 if (*c == ')')
222 c++;
223 if (*c == '\0' || *c == '[') {
224 add_range(rl, min, min);
225 break;
226 }
227 if (*c == ',') {
228 add_range(rl, min, min);
229 c++;
230 continue;
231 }
232 if (*c != '-') {
233 sm_msg("debug XXX: trouble parsing %s ", value);
234 break;
235 }
236 c++;
237 if (*c == '(')
238 c++;
239 max = parse_val(1, call, type, c, &c);
240 if (*c == ')')
241 c++;
242 if (*c == '[') {
243 arg_max = get_val_from_key(1, type, c, call, &c);
244 if (sval_cmp(arg_max, max) < 0)
245 max = arg_max;
246 }
247 add_range(rl, min, max);
248 if (!*c)
249 break;
250 if (*c != ',') {
251 sm_msg("debug YYY: trouble parsing %s %s", value, c);
252 break;
253 }
254 c++;
255 }
256
257 out:
258 *rl = cast_rl(type, *rl);
259 }
260
261 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
262 {
263 return str_to_rl_helper(NULL, type, value, rl);
264 }
265
266 void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
267 {
268 return str_to_rl_helper(strip_expr(expr), type, value, rl);
269 }
270
271 int is_whole_rl(struct range_list *rl)
272 {
273 struct data_range *drange;
274
275 if (ptr_list_empty(rl))
276 return 0;
277 drange = first_ptr_list((struct ptr_list *)rl);
278 if (sval_is_min(drange->min) && sval_is_max(drange->max))
279 return 1;
280 return 0;
281 }
282
283 sval_t rl_min(struct range_list *rl)
284 {
285 struct data_range *drange;
286 sval_t ret;
287
288 ret.type = &llong_ctype;
289 ret.value = LLONG_MIN;
290 if (ptr_list_empty(rl))
291 return ret;
292 drange = first_ptr_list((struct ptr_list *)rl);
293 return drange->min;
294 }
295
296 sval_t rl_max(struct range_list *rl)
297 {
298 struct data_range *drange;
299 sval_t ret;
300
301 ret.type = &llong_ctype;
302 ret.value = LLONG_MAX;
303 if (ptr_list_empty(rl))
304 return ret;
305 drange = last_ptr_list((struct ptr_list *)rl);
306 return drange->max;
307 }
308
309 int rl_to_sval(struct range_list *rl, sval_t *sval)
310 {
311 sval_t min, max;
312
313 if (!rl)
314 return 0;
315
316 min = rl_min(rl);
317 max = rl_max(rl);
318 if (sval_cmp(min, max) != 0)
319 return 0;
320 *sval = min;
321 return 1;
322 }
323
324 struct symbol *rl_type(struct range_list *rl)
325 {
326 if (!rl)
327 return NULL;
328 return rl_min(rl).type;
329 }
330
331 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
332 {
333 struct data_range *ret;
334
335 if (perm)
336 ret = __alloc_perm_data_range(0);
337 else
338 ret = __alloc_data_range(0);
339 ret->min = min;
340 ret->max = max;
341 return ret;
342 }
343
344 struct data_range *alloc_range(sval_t min, sval_t max)
345 {
346 return alloc_range_helper_sval(min, max, 0);
347 }
348
349 struct data_range *alloc_range_perm(sval_t min, sval_t max)
350 {
351 return alloc_range_helper_sval(min, max, 1);
352 }
353
354 struct range_list *alloc_rl(sval_t min, sval_t max)
355 {
356 struct range_list *rl = NULL;
357
358 if (sval_cmp(min, max) > 0)
359 return alloc_whole_rl(min.type);
360
361 add_range(&rl, min, max);
362 return rl;
363 }
364
365 struct range_list *alloc_whole_rl(struct symbol *type)
366 {
367 if (!type || type_positive_bits(type) < 0)
368 type = &llong_ctype;
369 if (type->type == SYM_ARRAY)
370 type = &ptr_ctype;
371
372 return alloc_rl(sval_type_min(type), sval_type_max(type));
373 }
374
375 void add_range(struct range_list **list, sval_t min, sval_t max)
376 {
377 struct data_range *tmp = NULL;
378 struct data_range *new = NULL;
379 int check_next = 0;
380
381 /*
382 * FIXME: This has a problem merging a range_list like: min-0,3-max
383 * with a range like 1-2. You end up with min-2,3-max instead of
384 * just min-max.
385 */
386 FOR_EACH_PTR(*list, tmp) {
387 if (check_next) {
388 /* Sometimes we overlap with more than one range
389 so we have to delete or modify the next range. */
390 if (max.value + 1 == tmp->min.value) {
391 /* join 2 ranges here */
392 new->max = tmp->max;
393 DELETE_CURRENT_PTR(tmp);
394 return;
395 }
396
397 /* Doesn't overlap with the next one. */
398 if (sval_cmp(max, tmp->min) < 0)
399 return;
400 /* Partially overlaps with the next one. */
401 if (sval_cmp(max, tmp->max) < 0) {
402 tmp->min.value = max.value + 1;
403 return;
404 }
405 /* Completely overlaps with the next one. */
406 if (sval_cmp(max, tmp->max) >= 0) {
407 DELETE_CURRENT_PTR(tmp);
408 /* there could be more ranges to delete */
409 continue;
410 }
411 }
412 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
413 /* join 2 ranges into a big range */
414 new = alloc_range(min, tmp->max);
415 REPLACE_CURRENT_PTR(tmp, new);
416 return;
417 }
418 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
419 new = alloc_range(min, max);
420 INSERT_CURRENT(new, tmp);
421 return;
422 }
423 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
424 if (sval_cmp(max, tmp->max) < 0)
425 max = tmp->max;
426 else
427 check_next = 1;
428 new = alloc_range(min, max);
429 REPLACE_CURRENT_PTR(tmp, new);
430 if (!check_next)
431 return;
432 continue;
433 }
434 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
435 return;
436 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
437 min = tmp->min;
438 new = alloc_range(min, max);
439 REPLACE_CURRENT_PTR(tmp, new);
440 check_next = 1;
441 continue;
442 }
443 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
444 /* join 2 ranges into a big range */
445 new = alloc_range(tmp->min, max);
446 REPLACE_CURRENT_PTR(tmp, new);
447 check_next = 1;
448 continue;
449 }
450 /* the new range is entirely above the existing ranges */
451 } END_FOR_EACH_PTR(tmp);
452 if (check_next)
453 return;
454 new = alloc_range(min, max);
455 add_ptr_list(list, new);
456 }
457
458 struct range_list *clone_rl(struct range_list *list)
459 {
460 struct data_range *tmp;
461 struct range_list *ret = NULL;
462
463 FOR_EACH_PTR(list, tmp) {
464 add_ptr_list(&ret, tmp);
465 } END_FOR_EACH_PTR(tmp);
466 return ret;
467 }
468
469 struct range_list *clone_rl_permanent(struct range_list *list)
470 {
471 struct data_range *tmp;
472 struct data_range *new;
473 struct range_list *ret = NULL;
474
475 FOR_EACH_PTR(list, tmp) {
476 new = alloc_range_perm(tmp->min, tmp->max);
477 add_ptr_list(&ret, new);
478 } END_FOR_EACH_PTR(tmp);
479 return ret;
480 }
481
482 struct range_list *rl_union(struct range_list *one, struct range_list *two)
483 {
484 struct data_range *tmp;
485 struct range_list *ret = NULL;
486
487 FOR_EACH_PTR(one, tmp) {
488 add_range(&ret, tmp->min, tmp->max);
489 } END_FOR_EACH_PTR(tmp);
490 FOR_EACH_PTR(two, tmp) {
491 add_range(&ret, tmp->min, tmp->max);
492 } END_FOR_EACH_PTR(tmp);
493 return ret;
494 }
495
496 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
497 {
498 struct data_range *tmp;
499 struct range_list *ret = NULL;
500
501 FOR_EACH_PTR(list, tmp) {
502 if (sval_cmp(tmp->max, min) < 0) {
503 add_range(&ret, tmp->min, tmp->max);
504 continue;
505 }
506 if (sval_cmp(tmp->min, max) > 0) {
507 add_range(&ret, tmp->min, tmp->max);
508 continue;
509 }
510 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
511 continue;
512 if (sval_cmp(tmp->min, min) >= 0) {
513 max.value++;
514 add_range(&ret, max, tmp->max);
515 } else if (sval_cmp(tmp->max, max) <= 0) {
516 min.value--;
517 add_range(&ret, tmp->min, min);
518 } else {
519 min.value--;
520 max.value++;
521 add_range(&ret, tmp->min, min);
522 add_range(&ret, max, tmp->max);
523 }
524 } END_FOR_EACH_PTR(tmp);
525 return ret;
526 }
527
528 int ranges_equiv(struct data_range *one, struct data_range *two)
529 {
530 if (!one && !two)
531 return 1;
532 if (!one || !two)
533 return 0;
534 if (sval_cmp(one->min, two->min) != 0)
535 return 0;
536 if (sval_cmp(one->max, two->max) != 0)
537 return 0;
538 return 1;
539 }
540
541 int rl_equiv(struct range_list *one, struct range_list *two)
542 {
543 struct data_range *one_range;
544 struct data_range *two_range;
545
546 if (one == two)
547 return 1;
548
549 PREPARE_PTR_LIST(one, one_range);
550 PREPARE_PTR_LIST(two, two_range);
551 for (;;) {
552 if (!one_range && !two_range)
553 return 1;
554 if (!ranges_equiv(one_range, two_range))
555 return 0;
556 NEXT_PTR_LIST(one_range);
557 NEXT_PTR_LIST(two_range);
558 }
559 FINISH_PTR_LIST(two_range);
560 FINISH_PTR_LIST(one_range);
561
562 return 1;
563 }
564
565 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
566 {
567 switch (comparison) {
568 case '<':
569 case SPECIAL_UNSIGNED_LT:
570 if (sval_cmp(left->min, right->max) < 0)
571 return 1;
572 return 0;
573 case SPECIAL_UNSIGNED_LTE:
574 case SPECIAL_LTE:
575 if (sval_cmp(left->min, right->max) <= 0)
576 return 1;
577 return 0;
578 case SPECIAL_EQUAL:
579 if (sval_cmp(left->max, right->min) < 0)
580 return 0;
581 if (sval_cmp(left->min, right->max) > 0)
582 return 0;
583 return 1;
584 case SPECIAL_UNSIGNED_GTE:
585 case SPECIAL_GTE:
586 if (sval_cmp(left->max, right->min) >= 0)
587 return 1;
588 return 0;
589 case '>':
590 case SPECIAL_UNSIGNED_GT:
591 if (sval_cmp(left->max, right->min) > 0)
592 return 1;
593 return 0;
594 case SPECIAL_NOTEQUAL:
595 if (sval_cmp(left->min, left->max) != 0)
596 return 1;
597 if (sval_cmp(right->min, right->max) != 0)
598 return 1;
599 if (sval_cmp(left->min, right->min) != 0)
600 return 1;
601 return 0;
602 default:
603 sm_msg("unhandled comparison %d\n", comparison);
604 return 0;
605 }
606 return 0;
607 }
608
609 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
610 {
611 if (left)
612 return true_comparison_range(var, comparison, val);
613 else
614 return true_comparison_range(val, comparison, var);
615 }
616
617 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
618 {
619 switch (comparison) {
620 case '<':
621 case SPECIAL_UNSIGNED_LT:
622 if (sval_cmp(left->max, right->min) >= 0)
623 return 1;
624 return 0;
625 case SPECIAL_UNSIGNED_LTE:
626 case SPECIAL_LTE:
627 if (sval_cmp(left->max, right->min) > 0)
628 return 1;
629 return 0;
630 case SPECIAL_EQUAL:
631 if (sval_cmp(left->min, left->max) != 0)
632 return 1;
633 if (sval_cmp(right->min, right->max) != 0)
634 return 1;
635 if (sval_cmp(left->min, right->min) != 0)
636 return 1;
637 return 0;
638 case SPECIAL_UNSIGNED_GTE:
639 case SPECIAL_GTE:
640 if (sval_cmp(left->min, right->max) < 0)
641 return 1;
642 return 0;
643 case '>':
644 case SPECIAL_UNSIGNED_GT:
645 if (sval_cmp(left->min, right->max) <= 0)
646 return 1;
647 return 0;
648 case SPECIAL_NOTEQUAL:
649 if (sval_cmp(left->max, right->min) < 0)
650 return 0;
651 if (sval_cmp(left->min, right->max) > 0)
652 return 0;
653 return 1;
654 default:
655 sm_msg("unhandled comparison %d\n", comparison);
656 return 0;
657 }
658 return 0;
659 }
660
661 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
662 {
663 if (left)
664 return false_comparison_range_sval(var, comparison, val);
665 else
666 return false_comparison_range_sval(val, comparison, var);
667 }
668
669 int possibly_true(struct expression *left, int comparison, struct expression *right)
670 {
671 struct range_list *rl_left, *rl_right;
672 struct data_range *tmp_left, *tmp_right;
673
674 if (!get_implied_rl(left, &rl_left))
675 return 1;
676 if (!get_implied_rl(right, &rl_right))
677 return 1;
678
679 FOR_EACH_PTR(rl_left, tmp_left) {
680 FOR_EACH_PTR(rl_right, tmp_right) {
681 if (true_comparison_range(tmp_left, comparison, tmp_right))
682 return 1;
683 } END_FOR_EACH_PTR(tmp_right);
684 } END_FOR_EACH_PTR(tmp_left);
685 return 0;
686 }
687
688 int possibly_false(struct expression *left, int comparison, struct expression *right)
689 {
690 struct range_list *rl_left, *rl_right;
691 struct data_range *tmp_left, *tmp_right;
692
693 if (!get_implied_rl(left, &rl_left))
694 return 1;
695 if (!get_implied_rl(right, &rl_right))
696 return 1;
697
698 FOR_EACH_PTR(rl_left, tmp_left) {
699 FOR_EACH_PTR(rl_right, tmp_right) {
700 if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
701 return 1;
702 } END_FOR_EACH_PTR(tmp_right);
703 } END_FOR_EACH_PTR(tmp_left);
704 return 0;
705 }
706
707 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
708 {
709 struct data_range *left_tmp, *right_tmp;
710
711 if (!left_ranges || !right_ranges)
712 return 1;
713
714 FOR_EACH_PTR(left_ranges, left_tmp) {
715 FOR_EACH_PTR(right_ranges, right_tmp) {
716 if (true_comparison_range(left_tmp, comparison, right_tmp))
717 return 1;
718 } END_FOR_EACH_PTR(right_tmp);
719 } END_FOR_EACH_PTR(left_tmp);
720 return 0;
721 }
722
723 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
724 {
725 struct data_range *left_tmp, *right_tmp;
726
727 if (!left_ranges || !right_ranges)
728 return 1;
729
730 FOR_EACH_PTR(left_ranges, left_tmp) {
731 FOR_EACH_PTR(right_ranges, right_tmp) {
732 if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
733 return 1;
734 } END_FOR_EACH_PTR(right_tmp);
735 } END_FOR_EACH_PTR(left_tmp);
736 return 0;
737 }
738
739 /* FIXME: the _rl here stands for right left so really it should be _lr */
740 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
741 {
742 if (left)
743 return possibly_true_rl(a, comparison, b);
744 else
745 return possibly_true_rl(b, comparison, a);
746 }
747
748 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
749 {
750 if (left)
751 return possibly_false_rl(a, comparison, b);
752 else
753 return possibly_false_rl(b, comparison, a);
754 }
755
756 int rl_has_sval(struct range_list *rl, sval_t sval)
757 {
758 struct data_range *tmp;
759
760 FOR_EACH_PTR(rl, tmp) {
761 if (sval_cmp(tmp->min, sval) <= 0 &&
762 sval_cmp(tmp->max, sval) >= 0)
763 return 1;
764 } END_FOR_EACH_PTR(tmp);
765 return 0;
766 }
767
768 void tack_on(struct range_list **list, struct data_range *drange)
769 {
770 add_ptr_list(list, drange);
771 }
772
773 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
774 {
775 add_ptr_list(rl_stack, rl);
776 }
777
778 struct range_list *pop_rl(struct range_list_stack **rl_stack)
779 {
780 struct range_list *rl;
781
782 rl = last_ptr_list((struct ptr_list *)*rl_stack);
783 delete_ptr_list_last((struct ptr_list **)rl_stack);
784 return rl;
785 }
786
787 struct range_list *top_rl(struct range_list_stack *rl_stack)
788 {
789 struct range_list *rl;
790
791 rl = last_ptr_list((struct ptr_list *)rl_stack);
792 return rl;
793 }
794
795 void filter_top_rl(struct range_list_stack **rl_stack, sval_t sval)
796 {
797 struct range_list *rl;
798
799 rl = pop_rl(rl_stack);
800 rl = remove_range(rl, sval, sval);
801 push_rl(rl_stack, rl);
802 }
803
804 static int sval_too_big(struct symbol *type, sval_t sval)
805 {
806 if (type_bits(type) == 64)
807 return 0;
808 if (sval.uvalue > ((1ULL << type_bits(type)) - 1))
809 return 1;
810 return 0;
811 }
812
813 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
814 {
815 /* If we're just adding a number, cast it and add it */
816 if (sval_cmp(min, max) == 0) {
817 add_range(rl, sval_cast(type, min), sval_cast(type, max));
818 return;
819 }
820
821 /* If the range is within the type range then add it */
822 if (sval_fits(type, min) && sval_fits(type, max)) {
823 add_range(rl, sval_cast(type, min), sval_cast(type, max));
824 return;
825 }
826
827 /*
828 * If the range we are adding has more bits than the range type then
829 * add the whole range type. Eg:
830 * 0x8000000000000000 - 0xf000000000000000 -> cast to int
831 * This isn't totally the right thing to do. We could be more granular.
832 */
833 if (sval_too_big(type, min) || sval_too_big(type, max)) {
834 add_range(rl, sval_type_min(type), sval_type_max(type));
835 return;
836 }
837
838 /* Cast negative values to high positive values */
839 if (sval_is_negative(min) && type_unsigned(type)) {
840 if (sval_is_positive(max)) {
841 if (sval_too_high(type, max)) {
842 add_range(rl, sval_type_min(type), sval_type_max(type));
843 return;
844 }
845 add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
846 max = sval_type_max(type);
847 } else {
848 max = sval_cast(type, max);
849 }
850 min = sval_cast(type, min);
851 add_range(rl, min, max);
852 }
853
854 /* Cast high positive numbers to negative */
855 if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
856 if (!sval_is_negative(sval_cast(type, min))) {
857 add_range(rl, sval_cast(type, min), sval_type_max(type));
858 min = sval_type_min(type);
859 } else {
860 min = sval_cast(type, min);
861 }
862 max = sval_cast(type, max);
863 add_range(rl, min, max);
864 }
865
866 return;
867 }
868
869 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
870 {
871 struct data_range *tmp;
872 struct range_list *ret = NULL;
873 sval_t min, max;
874
875 if (!rl)
876 return NULL;
877
878 if (!type || type == rl_type(rl))
879 return rl;
880
881 FOR_EACH_PTR(rl, tmp) {
882 min = tmp->min;
883 max = tmp->max;
884 if (type_bits(type) < type_bits(rl_type(rl))) {
885 min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
886 max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
887 }
888 if (sval_cmp(min, max) > 0) {
889 min = sval_cast(type, min);
890 max = sval_cast(type, max);
891 }
892 add_range_t(type, &ret, min, max);
893 } END_FOR_EACH_PTR(tmp);
894
895 return ret;
896 }
897
898 static int rl_is_sane(struct range_list *rl)
899 {
900 struct data_range *tmp;
901 struct symbol *type;
902
903 type = rl_type(rl);
904 FOR_EACH_PTR(rl, tmp) {
905 if (!sval_fits(type, tmp->min))
906 return 0;
907 if (!sval_fits(type, tmp->max))
908 return 0;
909 if (sval_cmp(tmp->min, tmp->max) > 0)
910 return 0;
911 } END_FOR_EACH_PTR(tmp);
912
913 return 1;
914 }
915
916 static int rl_type_consistent(struct range_list *rl)
917 {
918 struct data_range *tmp;
919 struct symbol *type;
920
921 type = rl_type(rl);
922 FOR_EACH_PTR(rl, tmp) {
923 if (type != tmp->min.type || type != tmp->max.type)
924 return 0;
925 } END_FOR_EACH_PTR(tmp);
926 return 1;
927 }
928
929 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
930 {
931 struct data_range *tmp;
932 struct range_list *ret = NULL;
933
934 if (!rl)
935 return NULL;
936
937 if (!type)
938 return rl;
939 if (!rl_is_sane(rl))
940 return alloc_whole_rl(type);
941 if (type == rl_type(rl) && rl_type_consistent(rl))
942 return rl;
943
944 FOR_EACH_PTR(rl, tmp) {
945 add_range_t(type, &ret, tmp->min, tmp->max);
946 } END_FOR_EACH_PTR(tmp);
947
948 if (!ret)
949 return alloc_whole_rl(type);
950
951 return ret;
952 }
953
954 struct range_list *rl_invert(struct range_list *orig)
955 {
956 struct range_list *ret = NULL;
957 struct data_range *tmp;
958 sval_t gap_min, abs_max, sval;
959
960 if (!orig)
961 return NULL;
962
963 gap_min = sval_type_min(rl_min(orig).type);
964 abs_max = sval_type_max(rl_max(orig).type);
965
966 FOR_EACH_PTR(orig, tmp) {
967 if (sval_cmp(tmp->min, gap_min) > 0) {
968 sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
969 add_range(&ret, gap_min, sval);
970 }
971 gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
972 if (sval_cmp(tmp->max, abs_max) == 0)
973 gap_min = abs_max;
974 } END_FOR_EACH_PTR(tmp);
975
976 if (sval_cmp(gap_min, abs_max) < 0)
977 add_range(&ret, gap_min, abs_max);
978
979 return ret;
980 }
981
982 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
983 {
984 struct data_range *tmp;
985
986 FOR_EACH_PTR(filter, tmp) {
987 rl = remove_range(rl, tmp->min, tmp->max);
988 } END_FOR_EACH_PTR(tmp);
989
990 return rl;
991 }
992
993 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
994 {
995 if (!two)
996 return NULL;
997 two = rl_invert(two);
998 return rl_filter(one, two);
999 }
1000
1001 void free_rl(struct range_list **rlist)
1002 {
1003 __free_ptr_list((struct ptr_list **)rlist);
1004 }
1005
1006 static void free_single_dinfo(struct data_info *dinfo)
1007 {
1008 free_rl(&dinfo->value_ranges);
1009 }
1010
1011 static void free_dinfos(struct allocation_blob *blob)
1012 {
1013 unsigned int size = sizeof(struct data_info);
1014 unsigned int offset = 0;
1015
1016 while (offset < blob->offset) {
1017 free_single_dinfo((struct data_info *)(blob->data + offset));
1018 offset += size;
1019 }
1020 }
1021
1022 void free_data_info_allocs(void)
1023 {
1024 struct allocator_struct *desc = &data_info_allocator;
1025 struct allocation_blob *blob = desc->blobs;
1026
1027 desc->blobs = NULL;
1028 desc->allocations = 0;
1029 desc->total_bytes = 0;
1030 desc->useful_bytes = 0;
1031 desc->freelist = NULL;
1032 while (blob) {
1033 struct allocation_blob *next = blob->next;
1034 free_dinfos(blob);
1035 blob_free(blob, desc->chunking);
1036 blob = next;
1037 }
1038 clear_data_range_alloc();
1039 }
1040
Static analysis for C