2 * sparse/smatch_ranges.c
4 * Copyright (C) 2009 Dan Carpenter.
6 * Licensed under the Open Software License version 1.1
12 #include "smatch_extra.h"
13 #include "smatch_slist.h"
15 ALLOCATOR(data_info
, "smatch extra data");
16 ALLOCATOR(data_range_sval
, "data range sval");
17 __DO_ALLOCATOR(struct data_range_sval
, sizeof(struct data_range_sval
), __alignof__(struct data_range_sval
),
18 "permanent ranges sval", perm_data_range_sval
);
20 char *show_ranges_sval(struct range_list_sval
*list
)
22 struct data_range_sval
*tmp
;
28 FOR_EACH_PTR(list
, tmp
) {
30 strncat(full
, ",", 254 - strlen(full
));
31 if (sval_cmp(tmp
->min
, tmp
->max
) == 0) {
32 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
35 strncat(full
, sval_to_str(tmp
->min
), 254 - strlen(full
));
36 strncat(full
, "-", 254 - strlen(full
));
37 strncat(full
, sval_to_str(tmp
->max
), 254 - strlen(full
));
38 } END_FOR_EACH_PTR(tmp
);
39 return alloc_sname(full
);
42 void get_value_ranges_sval(char *value
, struct range_list_sval
**rl
)
56 if (!strncmp(start
, "max", 3)) {
59 } else if (!strncmp(start
, "u64max", 6)) {
60 val1
= LLONG_MAX
; // FIXME
62 } else if (!strncmp(start
, "s64max", 6)) {
65 } else if (!strncmp(start
, "u32max", 6)) {
68 } else if (!strncmp(start
, "s32max", 6)) {
71 } else if (!strncmp(start
, "u16max", 6)) {
74 } else if (!strncmp(start
, "s16max", 6)) {
77 } else if (!strncmp(start
, "min", 3)) {
80 } else if (!strncmp(start
, "s64min", 6)) {
83 } else if (!strncmp(start
, "s32min", 6)) {
86 } else if (!strncmp(start
, "s16min", 6)) {
90 while (*c
&& *c
!= ',' && *c
!= '-')
92 val1
= strtoll(start
, &c
, 10);
97 add_range_sval(rl
, ll_to_sval(val1
), ll_to_sval(val1
));
101 add_range_sval(rl
, ll_to_sval(val1
), ll_to_sval(val1
));
106 c
++; /* skip the dash in eg. 4-5 */
110 if (!strncmp(start
, "max", 3)) {
115 while (*c
&& *c
!= ',' && *c
!= '-')
117 val2
= strtoll(start
, &c
, 10);
119 add_range_sval(rl
, ll_to_sval(val1
), ll_to_sval(val2
));
124 c
++; /* skip the comma in eg: 4-5,7 */
128 int is_whole_range_rl_sval(struct range_list_sval
*rl
)
130 struct data_range_sval
*drange
;
132 if (ptr_list_empty(rl
))
134 drange
= first_ptr_list((struct ptr_list
*)rl
);
135 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
140 sval_t
rl_min_sval(struct range_list_sval
*rl
)
142 struct data_range_sval
*drange
;
145 ret
.type
= &llong_ctype
;
146 ret
.value
= LLONG_MIN
;
147 if (ptr_list_empty(rl
))
149 drange
= first_ptr_list((struct ptr_list
*)rl
);
153 sval_t
rl_max_sval(struct range_list_sval
*rl
)
155 struct data_range_sval
*drange
;
158 ret
.type
= &llong_ctype
;
159 ret
.value
= LLONG_MAX
;
160 if (ptr_list_empty(rl
))
162 drange
= last_ptr_list((struct ptr_list
*)rl
);
166 static struct data_range_sval
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
168 struct data_range_sval
*ret
;
170 if (sval_cmp(min
, max
) > 0) {
171 // sm_msg("debug invalid range %lld to %lld", min, max);
172 min
.value
= LLONG_MIN
; /* fixme: need a way to represent unknown svals */
173 max
.value
= LLONG_MAX
;
177 ret
= __alloc_perm_data_range_sval(0);
179 ret
= __alloc_data_range_sval(0);
185 struct data_range_sval
*alloc_range_sval(sval_t min
, sval_t max
)
187 return alloc_range_helper_sval(min
, max
, 0);
190 struct data_range_sval
*alloc_range_perm_sval(sval_t min
, sval_t max
)
192 return alloc_range_helper_sval(min
, max
, 1);
195 struct range_list_sval
*alloc_range_list_sval(sval_t min
, sval_t max
)
197 struct range_list_sval
*rl
= NULL
;
199 add_range_sval(&rl
, min
, max
);
203 struct range_list_sval
*whole_range_list_sval(struct symbol
*type
)
208 return alloc_range_list_sval(sval_type_min(type
), sval_type_max(type
));
211 void add_range_sval(struct range_list_sval
**list
, sval_t min
, sval_t max
)
213 struct data_range_sval
*tmp
= NULL
;
214 struct data_range_sval
*new = NULL
;
218 * FIXME: This has a problem merging a range_list like: min-0,3-max
219 * with a range like 1-2. You end up with min-2,3-max instead of
222 FOR_EACH_PTR(*list
, tmp
) {
224 /* Sometimes we overlap with more than one range
225 so we have to delete or modify the next range. */
226 if (max
.value
+ 1 == tmp
->min
.value
) {
227 /* join 2 ranges here */
229 DELETE_CURRENT_PTR(tmp
);
233 /* Doesn't overlap with the next one. */
234 if (sval_cmp(max
, tmp
->min
) < 0)
236 /* Partially overlaps with the next one. */
237 if (sval_cmp(max
, tmp
->max
) < 0) {
238 tmp
->min
.value
= max
.value
+ 1;
241 /* Completely overlaps with the next one. */
242 if (sval_cmp(max
, tmp
->max
) >= 0) {
243 DELETE_CURRENT_PTR(tmp
);
244 /* there could be more ranges to delete */
248 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
249 /* join 2 ranges into a big range */
250 new = alloc_range_sval(min
, tmp
->max
);
251 REPLACE_CURRENT_PTR(tmp
, new);
254 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
255 new = alloc_range_sval(min
, max
);
256 INSERT_CURRENT(new, tmp
);
259 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
260 if (sval_cmp(max
, tmp
->max
) < 0)
264 new = alloc_range_sval(min
, max
);
265 REPLACE_CURRENT_PTR(tmp
, new);
270 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
272 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
274 new = alloc_range_sval(min
, max
);
275 REPLACE_CURRENT_PTR(tmp
, new);
279 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
280 /* join 2 ranges into a big range */
281 new = alloc_range_sval(tmp
->min
, max
);
282 REPLACE_CURRENT_PTR(tmp
, new);
286 /* the new range is entirely above the existing ranges */
287 } END_FOR_EACH_PTR(tmp
);
290 new = alloc_range_sval(min
, max
);
291 add_ptr_list(list
, new);
294 struct range_list_sval
*clone_range_list_sval(struct range_list_sval
*list
)
296 struct data_range_sval
*tmp
;
297 struct range_list_sval
*ret
= NULL
;
299 FOR_EACH_PTR(list
, tmp
) {
300 add_ptr_list(&ret
, tmp
);
301 } END_FOR_EACH_PTR(tmp
);
305 struct range_list_sval
*clone_permanent_sval(struct range_list_sval
*list
)
307 struct data_range_sval
*tmp
;
308 struct data_range_sval
*new;
309 struct range_list_sval
*ret
= NULL
;
311 FOR_EACH_PTR(list
, tmp
) {
312 new = alloc_range_perm_sval(tmp
->min
, tmp
->max
);
313 add_ptr_list(&ret
, new);
314 } END_FOR_EACH_PTR(tmp
);
318 struct range_list_sval
*range_list_union_sval(struct range_list_sval
*one
, struct range_list_sval
*two
)
320 struct data_range_sval
*tmp
;
321 struct range_list_sval
*ret
= NULL
;
323 FOR_EACH_PTR(one
, tmp
) {
324 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
325 } END_FOR_EACH_PTR(tmp
);
326 FOR_EACH_PTR(two
, tmp
) {
327 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
328 } END_FOR_EACH_PTR(tmp
);
332 struct range_list_sval
*remove_range_sval(struct range_list_sval
*list
, sval_t min
, sval_t max
)
334 struct data_range_sval
*tmp
;
335 struct range_list_sval
*ret
= NULL
;
337 FOR_EACH_PTR(list
, tmp
) {
338 if (sval_cmp(tmp
->max
, min
) < 0) {
339 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
342 if (sval_cmp(tmp
->min
, max
) > 0) {
343 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
346 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
348 if (sval_cmp(tmp
->min
, min
) >= 0) {
350 add_range_sval(&ret
, max
, tmp
->max
);
351 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
353 add_range_sval(&ret
, tmp
->min
, min
);
357 add_range_sval(&ret
, tmp
->min
, min
);
358 add_range_sval(&ret
, max
, tmp
->max
);
360 } END_FOR_EACH_PTR(tmp
);
364 int estate_get_single_value_sval(struct smatch_state
*state
, sval_t
*sval
)
368 min
= rl_min_sval(estate_ranges_sval(state
));
369 max
= rl_max_sval(estate_ranges_sval(state
));
370 if (sval_cmp(min
, max
) != 0)
376 int ranges_equiv_sval(struct data_range_sval
*one
, struct data_range_sval
*two
)
382 if (sval_cmp(one
->min
, two
->min
) != 0)
384 if (sval_cmp(one
->max
, two
->max
) != 0)
389 int range_lists_equiv_sval(struct range_list_sval
*one
, struct range_list_sval
*two
)
391 struct data_range_sval
*one_range
;
392 struct data_range_sval
*two_range
;
394 PREPARE_PTR_LIST(one
, one_range
);
395 PREPARE_PTR_LIST(two
, two_range
);
397 if (!one_range
&& !two_range
)
399 if (!ranges_equiv_sval(one_range
, two_range
))
401 NEXT_PTR_LIST(one_range
);
402 NEXT_PTR_LIST(two_range
);
404 FINISH_PTR_LIST(two_range
);
405 FINISH_PTR_LIST(one_range
);
410 int true_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
412 switch (comparison
) {
414 case SPECIAL_UNSIGNED_LT
:
415 if (sval_cmp(left
->min
, right
->max
) < 0)
418 case SPECIAL_UNSIGNED_LTE
:
420 if (sval_cmp(left
->min
, right
->max
) <= 0)
424 if (sval_cmp(left
->max
, right
->min
) < 0)
426 if (sval_cmp(left
->min
, right
->max
) > 0)
429 case SPECIAL_UNSIGNED_GTE
:
431 if (sval_cmp(left
->max
, right
->min
) >= 0)
435 case SPECIAL_UNSIGNED_GT
:
436 if (sval_cmp(left
->max
, right
->min
) > 0)
439 case SPECIAL_NOTEQUAL
:
440 if (sval_cmp(left
->min
, left
->max
) != 0)
442 if (sval_cmp(right
->min
, right
->max
) != 0)
444 if (sval_cmp(left
->min
, right
->min
) != 0)
448 sm_msg("unhandled comparison %d\n", comparison
);
454 int true_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
457 return true_comparison_range_sval(var
, comparison
, val
);
459 return true_comparison_range_sval(val
, comparison
, var
);
462 static int false_comparison_range_sval(struct data_range_sval
*left
, int comparison
, struct data_range_sval
*right
)
464 switch (comparison
) {
466 case SPECIAL_UNSIGNED_LT
:
467 if (sval_cmp(left
->max
, right
->min
) >= 0)
470 case SPECIAL_UNSIGNED_LTE
:
472 if (sval_cmp(left
->max
, right
->min
) > 0)
476 if (sval_cmp(left
->min
, left
->max
) != 0)
478 if (sval_cmp(right
->min
, right
->max
) != 0)
480 if (sval_cmp(left
->min
, right
->min
) != 0)
483 case SPECIAL_UNSIGNED_GTE
:
485 if (sval_cmp(left
->min
, right
->max
) < 0)
489 case SPECIAL_UNSIGNED_GT
:
490 if (sval_cmp(left
->min
, right
->max
) <= 0)
493 case SPECIAL_NOTEQUAL
:
494 if (sval_cmp(left
->max
, right
->min
) < 0)
496 if (sval_cmp(left
->min
, right
->max
) > 0)
500 sm_msg("unhandled comparison %d\n", comparison
);
506 int false_comparison_range_lr_sval(int comparison
, struct data_range_sval
*var
, struct data_range_sval
*val
, int left
)
509 return false_comparison_range_sval(var
, comparison
, val
);
511 return false_comparison_range_sval(val
, comparison
, var
);
514 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
516 struct range_list_sval
*rl_left
, *rl_right
;
517 struct data_range_sval
*tmp_left
, *tmp_right
;
519 if (!get_implied_range_list_sval(left
, &rl_left
))
521 if (!get_implied_range_list_sval(right
, &rl_right
))
524 FOR_EACH_PTR(rl_left
, tmp_left
) {
525 FOR_EACH_PTR(rl_right
, tmp_right
) {
526 if (true_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
528 } END_FOR_EACH_PTR(tmp_right
);
529 } END_FOR_EACH_PTR(tmp_left
);
533 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
535 struct range_list_sval
*rl_left
, *rl_right
;
536 struct data_range_sval
*tmp_left
, *tmp_right
;
538 if (!get_implied_range_list_sval(left
, &rl_left
))
540 if (!get_implied_range_list_sval(right
, &rl_right
))
543 FOR_EACH_PTR(rl_left
, tmp_left
) {
544 FOR_EACH_PTR(rl_right
, tmp_right
) {
545 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
547 } END_FOR_EACH_PTR(tmp_right
);
548 } END_FOR_EACH_PTR(tmp_left
);
552 int possibly_true_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
554 struct data_range_sval
*left_tmp
, *right_tmp
;
556 if (!left_ranges
|| !right_ranges
)
559 FOR_EACH_PTR(left_ranges
, left_tmp
) {
560 FOR_EACH_PTR(right_ranges
, right_tmp
) {
561 if (true_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
563 } END_FOR_EACH_PTR(right_tmp
);
564 } END_FOR_EACH_PTR(left_tmp
);
568 int possibly_false_range_lists_sval(struct range_list_sval
*left_ranges
, int comparison
, struct range_list_sval
*right_ranges
)
570 struct data_range_sval
*left_tmp
, *right_tmp
;
572 if (!left_ranges
|| !right_ranges
)
575 FOR_EACH_PTR(left_ranges
, left_tmp
) {
576 FOR_EACH_PTR(right_ranges
, right_tmp
) {
577 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
579 } END_FOR_EACH_PTR(right_tmp
);
580 } END_FOR_EACH_PTR(left_tmp
);
584 /* FIXME: the _rl here stands for right left so really it should be _lr */
585 int possibly_true_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
588 return possibly_true_range_lists_sval(a
, comparison
, b
);
590 return possibly_true_range_lists_sval(b
, comparison
, a
);
593 int possibly_false_range_lists_rl_sval(int comparison
, struct range_list_sval
*a
, struct range_list_sval
*b
, int left
)
596 return possibly_false_range_lists_sval(a
, comparison
, b
);
598 return possibly_false_range_lists_sval(b
, comparison
, a
);
601 void tack_on_sval(struct range_list_sval
**list
, struct data_range_sval
*drange
)
603 add_ptr_list(list
, drange
);
606 void push_range_list_sval(struct range_list_stack_sval
**rl_stack
, struct range_list_sval
*rl
)
608 add_ptr_list(rl_stack
, rl
);
611 struct range_list_sval
*pop_range_list_sval(struct range_list_stack_sval
**rl_stack
)
613 struct range_list_sval
*rl
;
615 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
616 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
620 struct range_list_sval
*top_range_list_sval(struct range_list_stack_sval
*rl_stack
)
622 struct range_list_sval
*rl
;
624 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
628 void filter_top_range_list_sval(struct range_list_stack_sval
**rl_stack
, sval_t sval
)
630 struct range_list_sval
*rl
;
632 rl
= pop_range_list_sval(rl_stack
);
633 rl
= remove_range_sval(rl
, sval
, sval
);
634 push_range_list_sval(rl_stack
, rl
);
637 struct range_list_sval
*cast_rl(struct range_list_sval
*rl
, struct symbol
*type
)
639 struct data_range_sval
*tmp
;
640 struct data_range_sval
*new;
641 struct range_list_sval
*ret
= NULL
;
642 int set_min
, set_max
;
648 return clone_range_list_sval(rl
);
650 if (sval_cmp(rl_min_sval(rl
), rl_max_sval(rl
)) == 0) {
651 sval_t sval
= sval_cast(rl_min_sval(rl
), type
);
652 return alloc_range_list_sval(sval
, sval
);
656 if (type_unsigned(type
) && sval_cmp_val(rl_min_sval(rl
), 0) < 0)
660 if (type_signed(type
) && sval_cmp(rl_max_sval(rl
), sval_type_max(type
)) > 0)
663 FOR_EACH_PTR(rl
, tmp
) {
669 if (sval_cmp_t(type
, max
, sval_type_min(type
)) < 0)
671 if (sval_cmp_t(type
, min
, sval_type_max(type
)) > 0)
673 if (sval_cmp_val(min
, 0) < 0 && type_unsigned(type
))
675 new = alloc_range_sval(sval_cast(min
, type
), sval_cast(max
, type
));
676 add_ptr_list(&ret
, new);
677 } END_FOR_EACH_PTR(tmp
);
680 return whole_range_list_sval(type
);
683 tmp
= first_ptr_list((struct ptr_list
*)ret
);
684 tmp
->min
= sval_type_min(type
);
687 tmp
= last_ptr_list((struct ptr_list
*)ret
);
688 tmp
->max
= sval_type_max(type
);
694 void free_range_list_sval(struct range_list_sval
**rlist
)
696 __free_ptr_list((struct ptr_list
**)rlist
);
699 static void free_single_dinfo(struct data_info
*dinfo
)
701 if (dinfo
->type
== DATA_RANGE
)
702 free_range_list_sval(&dinfo
->value_ranges
);
705 static void free_dinfos(struct allocation_blob
*blob
)
707 unsigned int size
= sizeof(struct data_info
);
708 unsigned int offset
= 0;
710 while (offset
< blob
->offset
) {
711 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
716 void free_data_info_allocs(void)
718 struct allocator_struct
*desc
= &data_info_allocator
;
719 struct allocation_blob
*blob
= desc
->blobs
;
722 desc
->allocations
= 0;
723 desc
->total_bytes
= 0;
724 desc
->useful_bytes
= 0;
725 desc
->freelist
= NULL
;
727 struct allocation_blob
*next
= blob
->next
;
729 blob_free(blob
, desc
->chunking
);
732 clear_data_range_sval_alloc();