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 char *show_ranges_sval(struct range_list
*list
)
22 struct data_range
*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_type(struct symbol
*type
, char *value
, struct range_list
**rl
)
57 if (!strncmp(start
, "max", 3)) {
58 tmp
= sval_type_max(type
);
61 } else if (!strncmp(start
, "u64max", 6)) {
62 val1
= LLONG_MAX
; // FIXME
64 } else if (!strncmp(start
, "s64max", 6)) {
67 } else if (!strncmp(start
, "u32max", 6)) {
70 } else if (!strncmp(start
, "s32max", 6)) {
73 } else if (!strncmp(start
, "u16max", 6)) {
76 } else if (!strncmp(start
, "s16max", 6)) {
79 } else if (!strncmp(start
, "min", 3)) {
80 tmp
= sval_type_min(type
);
83 } else if (!strncmp(start
, "s64min", 6)) {
86 } else if (!strncmp(start
, "s32min", 6)) {
89 } else if (!strncmp(start
, "s16min", 6)) {
93 while (*c
&& *c
!= ',' && *c
!= '-')
95 val1
= strtoll(start
, &c
, 10);
100 add_range_sval(rl
, sval_type_val(type
, val1
), sval_type_val(type
, val1
));
104 add_range_sval(rl
, sval_type_val(type
, val1
), sval_type_val(type
, val1
));
109 c
++; /* skip the dash in eg. 4-5 */
113 if (!strncmp(start
, "max", 3)) {
114 tmp
= sval_type_max(type
);
119 while (*c
&& *c
!= ',' && *c
!= '-')
121 val2
= strtoll(start
, &c
, 10);
123 add_range_sval(rl
, sval_type_val(type
, val1
), sval_type_val(type
, val2
));
128 c
++; /* skip the comma in eg: 4-5,7 */
132 void get_value_ranges_sval(char *value
, struct range_list
**rl
)
134 get_value_ranges_type(&llong_ctype
, value
, rl
);
137 int is_whole_range_rl_sval(struct range_list
*rl
)
139 struct data_range
*drange
;
141 if (ptr_list_empty(rl
))
143 drange
= first_ptr_list((struct ptr_list
*)rl
);
144 if (sval_is_min(drange
->min
) && sval_is_max(drange
->max
))
149 sval_t
rl_min_sval(struct range_list
*rl
)
151 struct data_range
*drange
;
154 ret
.type
= &llong_ctype
;
155 ret
.value
= LLONG_MIN
;
156 if (ptr_list_empty(rl
))
158 drange
= first_ptr_list((struct ptr_list
*)rl
);
162 sval_t
rl_max_sval(struct range_list
*rl
)
164 struct data_range
*drange
;
167 ret
.type
= &llong_ctype
;
168 ret
.value
= LLONG_MAX
;
169 if (ptr_list_empty(rl
))
171 drange
= last_ptr_list((struct ptr_list
*)rl
);
175 static struct data_range
*alloc_range_helper_sval(sval_t min
, sval_t max
, int perm
)
177 struct data_range
*ret
;
179 if (sval_cmp(min
, max
) > 0) {
180 // sm_msg("debug invalid range %lld to %lld", min, max);
181 min
.value
= LLONG_MIN
; /* fixme: need a way to represent unknown svals */
182 max
.value
= LLONG_MAX
;
186 ret
= __alloc_perm_data_range(0);
188 ret
= __alloc_data_range(0);
194 struct data_range
*alloc_range_sval(sval_t min
, sval_t max
)
196 return alloc_range_helper_sval(min
, max
, 0);
199 struct data_range
*alloc_range_perm_sval(sval_t min
, sval_t max
)
201 return alloc_range_helper_sval(min
, max
, 1);
204 struct range_list
*alloc_range_list(sval_t min
, sval_t max
)
206 struct range_list
*rl
= NULL
;
208 add_range_sval(&rl
, min
, max
);
212 struct range_list
*whole_range_list(struct symbol
*type
)
217 return alloc_range_list(sval_type_min(type
), sval_type_max(type
));
220 void add_range_sval(struct range_list
**list
, sval_t min
, sval_t max
)
222 struct data_range
*tmp
= NULL
;
223 struct data_range
*new = NULL
;
227 * FIXME: This has a problem merging a range_list like: min-0,3-max
228 * with a range like 1-2. You end up with min-2,3-max instead of
231 FOR_EACH_PTR(*list
, tmp
) {
233 /* Sometimes we overlap with more than one range
234 so we have to delete or modify the next range. */
235 if (max
.value
+ 1 == tmp
->min
.value
) {
236 /* join 2 ranges here */
238 DELETE_CURRENT_PTR(tmp
);
242 /* Doesn't overlap with the next one. */
243 if (sval_cmp(max
, tmp
->min
) < 0)
245 /* Partially overlaps with the next one. */
246 if (sval_cmp(max
, tmp
->max
) < 0) {
247 tmp
->min
.value
= max
.value
+ 1;
250 /* Completely overlaps with the next one. */
251 if (sval_cmp(max
, tmp
->max
) >= 0) {
252 DELETE_CURRENT_PTR(tmp
);
253 /* there could be more ranges to delete */
257 if (!sval_is_max(max
) && max
.value
+ 1 == tmp
->min
.value
) {
258 /* join 2 ranges into a big range */
259 new = alloc_range_sval(min
, tmp
->max
);
260 REPLACE_CURRENT_PTR(tmp
, new);
263 if (sval_cmp(max
, tmp
->min
) < 0) { /* new range entirely below */
264 new = alloc_range_sval(min
, max
);
265 INSERT_CURRENT(new, tmp
);
268 if (sval_cmp(min
, tmp
->min
) < 0) { /* new range partially below */
269 if (sval_cmp(max
, tmp
->max
) < 0)
273 new = alloc_range_sval(min
, max
);
274 REPLACE_CURRENT_PTR(tmp
, new);
279 if (sval_cmp(max
, tmp
->max
) <= 0) /* new range already included */
281 if (sval_cmp(min
, tmp
->max
) <= 0) { /* new range partially above */
283 new = alloc_range_sval(min
, max
);
284 REPLACE_CURRENT_PTR(tmp
, new);
288 if (!sval_is_min(min
) && min
.value
- 1 == tmp
->max
.value
) {
289 /* join 2 ranges into a big range */
290 new = alloc_range_sval(tmp
->min
, max
);
291 REPLACE_CURRENT_PTR(tmp
, new);
295 /* the new range is entirely above the existing ranges */
296 } END_FOR_EACH_PTR(tmp
);
299 new = alloc_range_sval(min
, max
);
300 add_ptr_list(list
, new);
303 struct range_list
*clone_range_list(struct range_list
*list
)
305 struct data_range
*tmp
;
306 struct range_list
*ret
= NULL
;
308 FOR_EACH_PTR(list
, tmp
) {
309 add_ptr_list(&ret
, tmp
);
310 } END_FOR_EACH_PTR(tmp
);
314 struct range_list
*clone_permanent_sval(struct range_list
*list
)
316 struct data_range
*tmp
;
317 struct data_range
*new;
318 struct range_list
*ret
= NULL
;
320 FOR_EACH_PTR(list
, tmp
) {
321 new = alloc_range_perm_sval(tmp
->min
, tmp
->max
);
322 add_ptr_list(&ret
, new);
323 } END_FOR_EACH_PTR(tmp
);
327 struct range_list
*range_list_union_sval(struct range_list
*one
, struct range_list
*two
)
329 struct data_range
*tmp
;
330 struct range_list
*ret
= NULL
;
332 FOR_EACH_PTR(one
, tmp
) {
333 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
334 } END_FOR_EACH_PTR(tmp
);
335 FOR_EACH_PTR(two
, tmp
) {
336 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
337 } END_FOR_EACH_PTR(tmp
);
341 struct range_list
*remove_range_sval(struct range_list
*list
, sval_t min
, sval_t max
)
343 struct data_range
*tmp
;
344 struct range_list
*ret
= NULL
;
346 FOR_EACH_PTR(list
, tmp
) {
347 if (sval_cmp(tmp
->max
, min
) < 0) {
348 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
351 if (sval_cmp(tmp
->min
, max
) > 0) {
352 add_range_sval(&ret
, tmp
->min
, tmp
->max
);
355 if (sval_cmp(tmp
->min
, min
) >= 0 && sval_cmp(tmp
->max
, max
) <= 0)
357 if (sval_cmp(tmp
->min
, min
) >= 0) {
359 add_range_sval(&ret
, max
, tmp
->max
);
360 } else if (sval_cmp(tmp
->max
, max
) <= 0) {
362 add_range_sval(&ret
, tmp
->min
, min
);
366 add_range_sval(&ret
, tmp
->min
, min
);
367 add_range_sval(&ret
, max
, tmp
->max
);
369 } END_FOR_EACH_PTR(tmp
);
373 int ranges_equiv_sval(struct data_range
*one
, struct data_range
*two
)
379 if (sval_cmp(one
->min
, two
->min
) != 0)
381 if (sval_cmp(one
->max
, two
->max
) != 0)
386 int range_lists_equiv_sval(struct range_list
*one
, struct range_list
*two
)
388 struct data_range
*one_range
;
389 struct data_range
*two_range
;
391 PREPARE_PTR_LIST(one
, one_range
);
392 PREPARE_PTR_LIST(two
, two_range
);
394 if (!one_range
&& !two_range
)
396 if (!ranges_equiv_sval(one_range
, two_range
))
398 NEXT_PTR_LIST(one_range
);
399 NEXT_PTR_LIST(two_range
);
401 FINISH_PTR_LIST(two_range
);
402 FINISH_PTR_LIST(one_range
);
407 int true_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
409 switch (comparison
) {
411 case SPECIAL_UNSIGNED_LT
:
412 if (sval_cmp(left
->min
, right
->max
) < 0)
415 case SPECIAL_UNSIGNED_LTE
:
417 if (sval_cmp(left
->min
, right
->max
) <= 0)
421 if (sval_cmp(left
->max
, right
->min
) < 0)
423 if (sval_cmp(left
->min
, right
->max
) > 0)
426 case SPECIAL_UNSIGNED_GTE
:
428 if (sval_cmp(left
->max
, right
->min
) >= 0)
432 case SPECIAL_UNSIGNED_GT
:
433 if (sval_cmp(left
->max
, right
->min
) > 0)
436 case SPECIAL_NOTEQUAL
:
437 if (sval_cmp(left
->min
, left
->max
) != 0)
439 if (sval_cmp(right
->min
, right
->max
) != 0)
441 if (sval_cmp(left
->min
, right
->min
) != 0)
445 sm_msg("unhandled comparison %d\n", comparison
);
451 int true_comparison_range_lr_sval(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
454 return true_comparison_range_sval(var
, comparison
, val
);
456 return true_comparison_range_sval(val
, comparison
, var
);
459 static int false_comparison_range_sval(struct data_range
*left
, int comparison
, struct data_range
*right
)
461 switch (comparison
) {
463 case SPECIAL_UNSIGNED_LT
:
464 if (sval_cmp(left
->max
, right
->min
) >= 0)
467 case SPECIAL_UNSIGNED_LTE
:
469 if (sval_cmp(left
->max
, right
->min
) > 0)
473 if (sval_cmp(left
->min
, left
->max
) != 0)
475 if (sval_cmp(right
->min
, right
->max
) != 0)
477 if (sval_cmp(left
->min
, right
->min
) != 0)
480 case SPECIAL_UNSIGNED_GTE
:
482 if (sval_cmp(left
->min
, right
->max
) < 0)
486 case SPECIAL_UNSIGNED_GT
:
487 if (sval_cmp(left
->min
, right
->max
) <= 0)
490 case SPECIAL_NOTEQUAL
:
491 if (sval_cmp(left
->max
, right
->min
) < 0)
493 if (sval_cmp(left
->min
, right
->max
) > 0)
497 sm_msg("unhandled comparison %d\n", comparison
);
503 int false_comparison_range_lr_sval(int comparison
, struct data_range
*var
, struct data_range
*val
, int left
)
506 return false_comparison_range_sval(var
, comparison
, val
);
508 return false_comparison_range_sval(val
, comparison
, var
);
511 int possibly_true(struct expression
*left
, int comparison
, struct expression
*right
)
513 struct range_list
*rl_left
, *rl_right
;
514 struct data_range
*tmp_left
, *tmp_right
;
516 if (!get_implied_range_list(left
, &rl_left
))
518 if (!get_implied_range_list(right
, &rl_right
))
521 FOR_EACH_PTR(rl_left
, tmp_left
) {
522 FOR_EACH_PTR(rl_right
, tmp_right
) {
523 if (true_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
525 } END_FOR_EACH_PTR(tmp_right
);
526 } END_FOR_EACH_PTR(tmp_left
);
530 int possibly_false(struct expression
*left
, int comparison
, struct expression
*right
)
532 struct range_list
*rl_left
, *rl_right
;
533 struct data_range
*tmp_left
, *tmp_right
;
535 if (!get_implied_range_list(left
, &rl_left
))
537 if (!get_implied_range_list(right
, &rl_right
))
540 FOR_EACH_PTR(rl_left
, tmp_left
) {
541 FOR_EACH_PTR(rl_right
, tmp_right
) {
542 if (false_comparison_range_sval(tmp_left
, comparison
, tmp_right
))
544 } END_FOR_EACH_PTR(tmp_right
);
545 } END_FOR_EACH_PTR(tmp_left
);
549 int possibly_true_range_lists_sval(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
551 struct data_range
*left_tmp
, *right_tmp
;
553 if (!left_ranges
|| !right_ranges
)
556 FOR_EACH_PTR(left_ranges
, left_tmp
) {
557 FOR_EACH_PTR(right_ranges
, right_tmp
) {
558 if (true_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
560 } END_FOR_EACH_PTR(right_tmp
);
561 } END_FOR_EACH_PTR(left_tmp
);
565 int possibly_false_range_lists_sval(struct range_list
*left_ranges
, int comparison
, struct range_list
*right_ranges
)
567 struct data_range
*left_tmp
, *right_tmp
;
569 if (!left_ranges
|| !right_ranges
)
572 FOR_EACH_PTR(left_ranges
, left_tmp
) {
573 FOR_EACH_PTR(right_ranges
, right_tmp
) {
574 if (false_comparison_range_sval(left_tmp
, comparison
, right_tmp
))
576 } END_FOR_EACH_PTR(right_tmp
);
577 } END_FOR_EACH_PTR(left_tmp
);
581 /* FIXME: the _rl here stands for right left so really it should be _lr */
582 int possibly_true_range_lists_rl_sval(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
585 return possibly_true_range_lists_sval(a
, comparison
, b
);
587 return possibly_true_range_lists_sval(b
, comparison
, a
);
590 int possibly_false_range_lists_rl_sval(int comparison
, struct range_list
*a
, struct range_list
*b
, int left
)
593 return possibly_false_range_lists_sval(a
, comparison
, b
);
595 return possibly_false_range_lists_sval(b
, comparison
, a
);
598 void tack_on_sval(struct range_list
**list
, struct data_range
*drange
)
600 add_ptr_list(list
, drange
);
603 void push_range_list(struct range_list_stack_sval
**rl_stack
, struct range_list
*rl
)
605 add_ptr_list(rl_stack
, rl
);
608 struct range_list
*pop_range_list(struct range_list_stack_sval
**rl_stack
)
610 struct range_list
*rl
;
612 rl
= last_ptr_list((struct ptr_list
*)*rl_stack
);
613 delete_ptr_list_last((struct ptr_list
**)rl_stack
);
617 struct range_list
*top_range_list(struct range_list_stack_sval
*rl_stack
)
619 struct range_list
*rl
;
621 rl
= last_ptr_list((struct ptr_list
*)rl_stack
);
625 void filter_top_range_list(struct range_list_stack_sval
**rl_stack
, sval_t sval
)
627 struct range_list
*rl
;
629 rl
= pop_range_list(rl_stack
);
630 rl
= remove_range_sval(rl
, sval
, sval
);
631 push_range_list(rl_stack
, rl
);
634 struct range_list
*cast_rl(struct range_list
*rl
, struct symbol
*type
)
636 struct data_range
*tmp
;
637 struct data_range
*new;
638 struct range_list
*ret
= NULL
;
639 int set_min
, set_max
;
645 return clone_range_list(rl
);
647 if (sval_cmp(rl_min_sval(rl
), rl_max_sval(rl
)) == 0) {
648 sval_t sval
= sval_cast(rl_min_sval(rl
), type
);
649 return alloc_range_list(sval
, sval
);
653 if (type_unsigned(type
) && sval_cmp_val(rl_min_sval(rl
), 0) < 0)
657 if (type_signed(type
) && sval_cmp(rl_max_sval(rl
), sval_type_max(type
)) > 0)
660 FOR_EACH_PTR(rl
, tmp
) {
666 if (sval_cmp_t(type
, max
, sval_type_min(type
)) < 0)
668 if (sval_cmp_t(type
, min
, sval_type_max(type
)) > 0)
670 if (sval_cmp_val(min
, 0) < 0 && type_unsigned(type
))
672 new = alloc_range_sval(sval_cast(min
, type
), sval_cast(max
, type
));
673 add_ptr_list(&ret
, new);
674 } END_FOR_EACH_PTR(tmp
);
677 return whole_range_list(type
);
680 tmp
= first_ptr_list((struct ptr_list
*)ret
);
681 tmp
->min
= sval_type_min(type
);
684 tmp
= last_ptr_list((struct ptr_list
*)ret
);
685 tmp
->max
= sval_type_max(type
);
691 void free_range_list(struct range_list
**rlist
)
693 __free_ptr_list((struct ptr_list
**)rlist
);
696 static void free_single_dinfo(struct data_info
*dinfo
)
698 if (dinfo
->type
== DATA_RANGE
)
699 free_range_list(&dinfo
->value_ranges
);
702 static void free_dinfos(struct allocation_blob
*blob
)
704 unsigned int size
= sizeof(struct data_info
);
705 unsigned int offset
= 0;
707 while (offset
< blob
->offset
) {
708 free_single_dinfo((struct data_info
*)(blob
->data
+ offset
));
713 void free_data_info_allocs(void)
715 struct allocator_struct
*desc
= &data_info_allocator
;
716 struct allocation_blob
*blob
= desc
->blobs
;
719 desc
->allocations
= 0;
720 desc
->total_bytes
= 0;
721 desc
->useful_bytes
= 0;
722 desc
->freelist
= NULL
;
724 struct allocation_blob
*next
= blob
->next
;
726 blob_free(blob
, desc
->chunking
);
729 clear_data_range_alloc();