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
, "data range");
17 __DO_ALLOCATOR(struct data_range
, sizeof(struct data_range
), __alignof__(struct data_range
),
18 "permanent ranges", perm_data_range
);
20 struct data_range whole_range
= {
25 static char *show_num(long long num
)
27 static char buff
[256];
29 if (num
== whole_range
.min
)
30 snprintf(buff
, 255, "min");
31 else if (num
== whole_range
.max
)
32 snprintf(buff
, 255, "max");
34 snprintf(buff
, 255, "(%lld)", num
);
36 snprintf(buff
, 255, "%lld", num
);
42 char *show_ranges(struct range_list
*list
)
44 struct data_range
*tmp
;
50 FOR_EACH_PTR(list
, tmp
) {
52 strncat(full
, ",", 254 - strlen(full
));
53 if (tmp
->min
== tmp
->max
) {
54 strncat(full
, show_num(tmp
->min
), 254 - strlen(full
));
57 strncat(full
, show_num(tmp
->min
), 254 - strlen(full
));
58 strncat(full
, "-", 254 - strlen(full
));
59 strncat(full
, show_num(tmp
->max
), 254 - strlen(full
));
60 } END_FOR_EACH_PTR(tmp
);
61 return alloc_sname(full
);
64 void get_value_ranges(char *value
, struct range_list
**rl
)
78 if (!strncmp(start
, "max", 3)) {
81 } else if (!strncmp(start
, "u64max", 6)) {
82 val1
= LLONG_MAX
; // FIXME
84 } else if (!strncmp(start
, "s64max", 6)) {
87 } else if (!strncmp(start
, "u32max", 6)) {
90 } else if (!strncmp(start
, "s32max", 6)) {
93 } else if (!strncmp(start
, "u16max", 6)) {
96 } else if (!strncmp(start
, "s16max", 6)) {
99 } else if (!strncmp(start
, "min", 3)) {
102 } else if (!strncmp(start
, "s64min", 6)) {
105 } else if (!strncmp(start
, "s32min", 6)) {
108 } else if (!strncmp(start
, "s16min", 6)) {
112 while (*c
&& *c
!= ',' && *c
!= '-')
114 val1
= strtoll(start
, &c
, 10);
119 add_range(rl
, val1
, val1
);
123 add_range(rl
, val1
, val1
);
128 c
++; /* skip the dash in eg. 4-5 */
132 if (!strncmp(start
, "max", 3)) {
137 while (*c
&& *c
!= ',' && *c
!= '-')
139 val2
= strtoll(start
, &c
, 10);
141 add_range(rl
, val1
, val2
);
146 c
++; /* skip the comma in eg: 4-5,7 */
150 static struct data_range range_zero
= {
155 static struct data_range range_one
= {
160 int is_whole_range_rl(struct range_list
*rl
)
162 struct data_range
*drange
;
164 if (ptr_list_empty(rl
))
166 drange
= first_ptr_list((struct ptr_list
*)rl
);
167 if (drange
->min
== whole_range
.min
&& drange
->max
== whole_range
.max
)
172 int rl_contiguous(struct range_list
*rl
)
174 if (first_ptr_list((struct ptr_list
*)rl
) == last_ptr_list((struct ptr_list
*)rl
))
179 long long rl_min(struct range_list
*rl
)
181 struct data_range
*drange
;
183 if (ptr_list_empty(rl
))
184 return whole_range
.min
;
185 drange
= first_ptr_list((struct ptr_list
*)rl
);
189 long long rl_max(struct range_list
*rl
)
191 struct data_range
*drange
;
193 if (ptr_list_empty(rl
))
194 return whole_range
.max
;
195 drange
= last_ptr_list((struct ptr_list
*)rl
);
199 static struct data_range
*alloc_range_helper(long long min
, long long max
, int perm
)
201 struct data_range
*ret
;
204 // sm_msg("debug invalid range %lld to %lld", min, max);
205 min
= whole_range
.min
;
206 max
= whole_range
.max
;
208 if (min
== whole_range
.min
&& max
== whole_range
.max
)
210 if (min
== 0 && max
== 0)
212 if (min
== 1 && max
== 1)
216 ret
= __alloc_perm_data_range(0);
218 ret
= __alloc_data_range(0);
224 struct data_range
*alloc_range(long long min
, long long max
)
226 return alloc_range_helper(min
, max
, 0);
229 struct data_range
*alloc_range_perm(long long min
, long long max
)
231 return alloc_range_helper(min
, max
, 1);
234 struct range_list
*alloc_range_list(long long min
, long long max
)
236 struct range_list
*rl
= NULL
;
238 add_range(&rl
, min
, max
);
242 struct range_list
*whole_range_list(void)
244 return alloc_range_list(whole_range
.min
, whole_range
.max
);
247 void add_range(struct range_list
**list
, long long min
, long long max
)
249 struct data_range
*tmp
= NULL
;
250 struct data_range
*new = NULL
;
254 * FIXME: This has a problem merging a range_list like: min-0,3-max
255 * with a range like 1-2. You end up with min-2,3-max instead of
258 FOR_EACH_PTR(*list
, tmp
) {
260 /* Sometimes we overlap with more than one range
261 so we have to delete or modify the next range. */
262 if (max
+ 1 == tmp
->min
) {
263 /* join 2 ranges here */
265 DELETE_CURRENT_PTR(tmp
);
269 /* Doesn't overlap with the next one. */
272 /* Partially overlaps with the next one. */
273 if (max
< tmp
->max
) {
277 /* Completely overlaps with the next one. */
278 if (max
>= tmp
->max
) {
279 DELETE_CURRENT_PTR(tmp
);
280 /* there could be more ranges to delete */
284 if (max
!= whole_range
.max
&& max
+ 1 == tmp
->min
) {
285 /* join 2 ranges into a big range */
286 new = alloc_range(min
, tmp
->max
);
287 REPLACE_CURRENT_PTR(tmp
, new);
290 if (max
< tmp
->min
) { /* new range entirely below */
291 new = alloc_range(min
, max
);
292 INSERT_CURRENT(new, tmp
);
295 if (min
< tmp
->min
) { /* new range partially below */
300 new = alloc_range(min
, max
);
301 REPLACE_CURRENT_PTR(tmp
, new);
306 if (max
<= tmp
->max
) /* new range already included */
308 if (min
<= tmp
->max
) { /* new range partially above */
310 new = alloc_range(min
, max
);
311 REPLACE_CURRENT_PTR(tmp
, new);
315 if (min
!= whole_range
.min
&& min
- 1 == tmp
->max
) {
316 /* join 2 ranges into a big range */
317 new = alloc_range(tmp
->min
, max
);
318 REPLACE_CURRENT_PTR(tmp
, new);
322 /* the new range is entirely above the existing ranges */
323 } END_FOR_EACH_PTR(tmp
);
326 new = alloc_range(min
, max
);
327 add_ptr_list(list
, new);
330 struct range_list
*clone_range_list(struct range_list
*list
)
332 struct data_range
*tmp
;
333 struct range_list
*ret
= NULL
;
335 FOR_EACH_PTR(list
, tmp
) {
336 add_ptr_list(&ret
, tmp
);
337 } END_FOR_EACH_PTR(tmp
);
341 struct range_list
*clone_permanent(struct range_list
*list
)
343 struct data_range
*tmp
;
344 struct data_range
*new;
345 struct range_list
*ret
= NULL
;
347 FOR_EACH_PTR(list
, tmp
) {
348 new = alloc_range_perm(tmp
->min
, tmp
->max
);
349 add_ptr_list(&ret
, new);
350 } END_FOR_EACH_PTR(tmp
);
354 struct range_list
*range_list_union(struct range_list
*one
, struct range_list
*two
)
356 struct data_range
*tmp
;
357 struct range_list
*ret
= NULL
;
359 FOR_EACH_PTR(one
, tmp
) {
360 add_range(&ret
, tmp
->min
, tmp
->max
);
361 } END_FOR_EACH_PTR(tmp
);
362 FOR_EACH_PTR(two
, tmp
) {
363 add_range(&ret
, tmp
->min
, tmp
->max
);
364 } END_FOR_EACH_PTR(tmp
);
368 struct range_list
*remove_range(struct range_list
*list
, long long min
, long long max
)
370 struct data_range
*tmp
;
371 struct range_list
*ret
= NULL
;
373 FOR_EACH_PTR(list
, tmp
) {
374 if (tmp
->max
< min
) {
375 add_range(&ret
, tmp
->min
, tmp
->max
);
378 if (tmp
->min
> max
) {
379 add_range(&ret
, tmp
->min
, tmp
->max
);
382 if (tmp
->min
>= min
&& tmp
->max
<= max
)
384 if (tmp
->min
>= min
) {
385 add_range(&ret
, max
+ 1, tmp
->max
);
386 } else if (tmp
->max
<= max
) {
387 add_range(&ret
, tmp
->min
, min
- 1);
389 add_range(&ret
, tmp
->min
, min
- 1);
390 add_range(&ret
, max
+ 1, tmp
->max
);
392 } END_FOR_EACH_PTR(tmp
);
396 struct range_list
*invert_range_list(struct range_list
*orig
)
398 struct range_list
*ret
= NULL
;
399 struct data_range
*tmp
;
405 gap_min
= whole_range
.min
;
406 FOR_EACH_PTR(orig
, tmp
) {
407 if (tmp
->min
> gap_min
)
408 add_range(&ret
, gap_min
, tmp
->min
- 1);
409 gap_min
= tmp
->max
+ 1;
410 if (tmp
->max
== whole_range
.max
)
411 gap_min
= whole_range
.max
;
412 } END_FOR_EACH_PTR(tmp
);
414 if (gap_min
!= whole_range
.max
)
415 add_range(&ret
, gap_min
, whole_range
.max
);
421 * if it can be only one and only value return 1, else return 0
423 int estate_get_single_value(struct smatch_state
*state
, long long *val
)
425 struct data_info
*dinfo
;
426 struct data_range
*tmp
;
429 dinfo
= get_dinfo(state
);
430 if (!dinfo
|| dinfo
->type
!= DATA_RANGE
)
433 FOR_EACH_PTR(dinfo
->value_ranges
, tmp
) {
435 if (tmp
->min
!= tmp
->max
)
441 } END_FOR_EACH_PTR(tmp
);
445 int range_lists_equiv(struct range_list
*one
, struct range_list
*two
)
447 struct data_range
*one_range
;
448 struct data_range
*two_range
;
450 PREPARE_PTR_LIST(one
, one_range
);
451 PREPARE_PTR_LIST(two
, two_range
);
453 if (!one_range
&& !two_range
)
455 if (!one_range
|| !two_range
)
457 if (one_range
->min
!= two_range
->min
)
459 if (one_range
->max
!= two_range
->max
)
461 NEXT_PTR_LIST(one_range
);
462 NEXT_PTR_LIST(two_range
);
464 FINISH_PTR_LIST(two_range
);
465 FINISH_PTR_LIST(one_range
);
470 int true_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
472 switch (comparison
) {
474 case SPECIAL_UNSIGNED_LT
:
475 if (left
->min
< right
->max
)
478 case SPECIAL_UNSIGNED_LTE
:
480 if (left
->min
<= right
->max
)
484 if (left
->max
< right
->min
)
486 if (left
->min
> right
->max
)
489 case SPECIAL_UNSIGNED_GTE
:
491 if (left
->max
>= right
->min
)
495 case SPECIAL_UNSIGNED_GT
:
496 if (left
->max
> right
->min
)
499 case SPECIAL_NOTEQUAL
:
500 if (left
->min
!= left
->max
)
502 if (right
->min
!= right
->max
)
504 if (left
->min
!= right
->min
)
508 sm_msg("unhandled comparison %d\n", comparison
);
514 int true_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
517 return true_comparison_range(var
, comparison
, val
);
519 return true_comparison_range(val
, comparison
, var
);
522 static int false_comparison_range(struct data_range
*left
, int comparison
, struct data_range
*right
)
524 switch (comparison
) {
526 case SPECIAL_UNSIGNED_LT
:
527 if (left
->max
>= right
->min
)
530 case SPECIAL_UNSIGNED_LTE
:
532 if (left
->max
> right
->min
)
536 if (left
->min
!= left
->max
)
538 if (right
->min
!= right
->max
)
540 if (left
->min
!= right
->min
)
543 case SPECIAL_UNSIGNED_GTE
:
545 if (left
->min
< right
->max
)
549 case SPECIAL_UNSIGNED_GT
:
550 if (left
->min
<= right
->max
)
553 case SPECIAL_NOTEQUAL
:
554 if (left
->max
< right
->min
)
556 if (left
->min
> right
->max
)
560 sm_msg("unhandled comparison %d\n", comparison
);
566 int false_comparison_range_lr(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
569 return false_comparison_range(var
, comparison
, val
);
571 return false_comparison_range(val
, comparison
, var
);
574 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
576 struct range_list
*rl_left
, *rl_right
;
577 struct data_range
*tmp_left
, *tmp_right
;
579 if (!get_implied_range_list(left
, &rl_left
))
581 if (!get_implied_range_list(right
, &rl_right
))
584 FOR_EACH_PTR(rl_left
, tmp_left
) {
585 FOR_EACH_PTR(rl_right
, tmp_right
) {
586 if (true_comparison_range(tmp_left
, comparison
, tmp_right
))
588 } END_FOR_EACH_PTR(tmp_right
);
589 } END_FOR_EACH_PTR(tmp_left
);
593 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
595 struct range_list
*rl_left
, *rl_right
;
596 struct data_range
*tmp_left
, *tmp_right
;
598 if (!get_implied_range_list(left
, &rl_left
))
600 if (!get_implied_range_list(right
, &rl_right
))
603 FOR_EACH_PTR(rl_left
, tmp_left
) {
604 FOR_EACH_PTR(rl_right
, tmp_right
) {
605 if (false_comparison_range(tmp_left
, comparison
, tmp_right
))
607 } END_FOR_EACH_PTR(tmp_right
);
608 } END_FOR_EACH_PTR(tmp_left
);
612 int possibly_true_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
614 struct data_range
*left_tmp
, *right_tmp
;
616 if (!left_ranges
|| !right_ranges
)
619 FOR_EACH_PTR(left_ranges
, left_tmp
) {
620 FOR_EACH_PTR(right_ranges
, right_tmp
) {
621 if (true_comparison_range(left_tmp
, comparison
, right_tmp
))
623 } END_FOR_EACH_PTR(right_tmp
);
624 } END_FOR_EACH_PTR(left_tmp
);
628 int possibly_false_range_lists(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
630 struct data_range
*left_tmp
, *right_tmp
;
632 if (!left_ranges
|| !right_ranges
)
635 FOR_EACH_PTR(left_ranges
, left_tmp
) {
636 FOR_EACH_PTR(right_ranges
, right_tmp
) {
637 if (false_comparison_range(left_tmp
, comparison
, right_tmp
))
639 } END_FOR_EACH_PTR(right_tmp
);
640 } END_FOR_EACH_PTR(left_tmp
);
644 int possibly_true_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
647 return possibly_true_range_lists(a
, comparison
, b
);
649 return possibly_true_range_lists(b
, comparison
, a
);
652 int possibly_false_range_lists_rl(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
655 return possibly_false_range_lists(a
, comparison
, b
);
657 return possibly_false_range_lists(b
, comparison
, a
);
660 void tack_on(struct range_list
**list
, struct data_range
*drange
)
662 add_ptr_list(list
, drange
);
665 int in_list_exact(struct range_list
*list
, struct data_range
*drange
)
667 struct data_range
*tmp
;
669 FOR_EACH_PTR(list
, tmp
) {
670 if (tmp
->min
== drange
->min
&& tmp
->max
== drange
->max
)
672 } END_FOR_EACH_PTR(tmp
);
676 void push_range_list(struct range_list_stack
**rl_stack
, struct range_list
*rl
)
678 add_ptr_list(rl_stack
, rl
);
681 struct range_list
*pop_range_list(struct range_list_stack
**rl_stack
)
683 struct range_list
*rl
;
685 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
686 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
690 struct range_list
*top_range_list(struct range_list_stack
*rl_stack
)
692 struct range_list
*rl
;
694 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
698 void filter_top_range_list(struct range_list_stack
**rl_stack
, long long num
)
700 struct range_list
*rl
;
702 rl
= pop_range_list(rl_stack
);
703 rl
= remove_range(rl
, num
, num
);
704 push_range_list(rl_stack
, rl
);
707 void free_range_list(struct range_list
**rlist
)
709 __free_ptr_list((struct ptr_list
**)rlist
);
712 static void free_single_dinfo(struct data_info
*dinfo
)
714 if (dinfo
->type
== DATA_RANGE
)
715 free_range_list(&dinfo
->value_ranges
);
718 static void free_dinfos(struct allocation_blob
*blob
)
720 unsigned int size
= sizeof(struct data_info
);
721 unsigned int offset
= 0;
723 while (offset
< blob
->offset
) {
724 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
729 void free_data_info_allocs(void)
731 struct allocator_struct
*desc
= &data_info_allocator
;
732 struct allocation_blob
*blob
= desc
->blobs
;
735 desc
->allocations
= 0;
736 desc
->total_bytes
= 0;
737 desc
->useful_bytes
= 0;
738 desc
->freelist
= NULL
;
740 struct allocation_blob
*next
= blob
->next
;
742 blob_free(blob
, desc
->chunking
);
745 clear_data_range_alloc();