Print this page
11506 smatch resync
*** 24,54 ****
ALLOCATOR(data_range, "data range");
__DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
"permanent ranges", perm_data_range);
__DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
char *show_rl(struct range_list *list)
{
struct data_range *tmp;
! char full[512];
int i = 0;
full[0] = '\0';
! full[sizeof(full) - 1] = '\0';
FOR_EACH_PTR(list, tmp) {
! if (i++)
! strncat(full, ",", 254 - strlen(full));
! if (sval_cmp(tmp->min, tmp->max) == 0) {
! strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
! continue;
}
! strncat(full, sval_to_str(tmp->min), 254 - strlen(full));
! strncat(full, "-", 254 - strlen(full));
! strncat(full, sval_to_str(tmp->max), 254 - strlen(full));
} END_FOR_EACH_PTR(tmp);
! if (strlen(full) == sizeof(full) - 1)
! full[sizeof(full) - 2] = '+';
return alloc_sname(full);
}
void free_all_rl(void)
{
--- 24,104 ----
ALLOCATOR(data_range, "data range");
__DO_ALLOCATOR(struct data_range, sizeof(struct data_range), __alignof__(struct data_range),
"permanent ranges", perm_data_range);
__DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
+ static bool is_err_ptr(sval_t sval)
+ {
+ if (option_project != PROJ_KERNEL)
+ return false;
+ if (!type_is_ptr(sval.type))
+ return false;
+ if (sval.uvalue < -4095ULL)
+ return false;
+ return true;
+ }
+
+ static char *get_err_pointer_str(struct data_range *drange)
+ {
+ static char buf[20];
+
+ /*
+ * The kernel has error pointers where you do essentially:
+ *
+ * return (void *)(unsigned long)-12;
+ *
+ * But what I want here is to print -12 instead of the unsigned version
+ * of that.
+ *
+ */
+ if (!is_err_ptr(drange->min))
+ return NULL;
+
+ if (drange->min.value == drange->max.value)
+ snprintf(buf, sizeof(buf), "(%lld)", drange->min.value);
+ else
+ snprintf(buf, sizeof(buf), "(%lld)-(%lld)", drange->min.value, drange->max.value);
+ return buf;
+ }
+
char *show_rl(struct range_list *list)
{
+ struct data_range *prev_drange = NULL;
struct data_range *tmp;
! char full[255];
! char *p = full;
! char *prev = full;
! char *err_ptr;
! int remain;
int i = 0;
full[0] = '\0';
!
FOR_EACH_PTR(list, tmp) {
! remain = full + sizeof(full) - p;
! if (remain < 48) {
! snprintf(prev, full + sizeof(full) - prev, ",%s-%s",
! sval_to_str(prev_drange->min),
! sval_to_str(sval_type_max(prev_drange->min.type)));
! break;
}
! prev_drange = tmp;
! prev = p;
!
! err_ptr = get_err_pointer_str(tmp);
! if (err_ptr) {
! p += snprintf(p, remain, "%s%s", i++ ? "," : "", err_ptr);
! } else if (sval_cmp(tmp->min, tmp->max) == 0) {
! p += snprintf(p, remain, "%s%s", i++ ? "," : "",
! sval_to_str(tmp->min));
! } else {
! p += snprintf(p, remain, "%s%s-%s", i++ ? "," : "",
! sval_to_str(tmp->min),
! sval_to_str(tmp->max));
! }
} END_FOR_EACH_PTR(tmp);
!
return alloc_sname(full);
}
void free_all_rl(void)
{
*** 77,86 ****
--- 127,148 ----
if (sval.uvalue > sval_type_max(type).uvalue)
return 1;
return 0;
}
+ static int truncates_nicely(struct symbol *type, sval_t min, sval_t max)
+ {
+ unsigned long long mask;
+ int bits = type_bits(type);
+
+ if (bits >= type_bits(min.type))
+ return 0;
+
+ mask = -1ULL << bits;
+ return (min.uvalue & mask) == (max.uvalue & mask);
+ }
+
static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
{
/* If we're just adding a number, cast it and add it */
if (sval_cmp(min, max) == 0) {
add_range(rl, sval_cast(type, min), sval_cast(type, max));
*** 91,105 ****
if (sval_fits(type, min) && sval_fits(type, max)) {
add_range(rl, sval_cast(type, min), sval_cast(type, max));
return;
}
/*
* If the range we are adding has more bits than the range type then
* add the whole range type. Eg:
* 0x8000000000000000 - 0xf000000000000000 -> cast to int
! * This isn't totally the right thing to do. We could be more granular.
*/
if (sval_too_big(type, min) || sval_too_big(type, max)) {
add_range(rl, sval_type_min(type), sval_type_max(type));
return;
}
--- 153,172 ----
if (sval_fits(type, min) && sval_fits(type, max)) {
add_range(rl, sval_cast(type, min), sval_cast(type, max));
return;
}
+ if (truncates_nicely(type, min, max)) {
+ add_range(rl, sval_cast(type, min), sval_cast(type, max));
+ return;
+ }
+
/*
* If the range we are adding has more bits than the range type then
* add the whole range type. Eg:
* 0x8000000000000000 - 0xf000000000000000 -> cast to int
! *
*/
if (sval_too_big(type, min) || sval_too_big(type, max)) {
add_range(rl, sval_type_min(type), sval_type_max(type));
return;
}
*** 136,149 ****
return;
}
static int str_to_comparison_arg_helper(const char *str,
struct expression *call, int *comparison,
! struct expression **arg, char **endp)
{
int param;
! char *c = (char *)str;
if (*c != '[')
return 0;
c++;
--- 203,216 ----
return;
}
static int str_to_comparison_arg_helper(const char *str,
struct expression *call, int *comparison,
! struct expression **arg, const char **endp)
{
int param;
! const char *c = str;
if (*c != '[')
return 0;
c++;
*** 169,188 ****
}
} else if (*c == '!') {
c++;
c++;
*comparison = SPECIAL_NOTEQUAL;
} else {
return 0;
}
if (*c != '$')
return 0;
c++;
! param = strtoll(c, &c, 10);
! if (*c == ']')
c++; /* skip the ']' character */
if (endp)
*endp = (char *)c;
if (!call)
--- 236,257 ----
}
} else if (*c == '!') {
c++;
c++;
*comparison = SPECIAL_NOTEQUAL;
+ } else if (*c == '$') {
+ *comparison = SPECIAL_EQUAL;
} else {
return 0;
}
if (*c != '$')
return 0;
c++;
! param = strtoll(c, (char **)&c, 10);
! if (*c == ',' || *c == ']')
c++; /* skip the ']' character */
if (endp)
*endp = (char *)c;
if (!call)
*** 216,226 ****
str++;
}
return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
}
! static int get_val_from_key(int use_max, struct symbol *type, char *c, struct expression *call, char **endp, sval_t *sval)
{
struct expression *arg;
int comparison;
sval_t ret, tmp;
--- 285,295 ----
str++;
}
return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
}
! static int get_val_from_key(int use_max, struct symbol *type, const char *c, struct expression *call, const char **endp, sval_t *sval)
{
struct expression *arg;
int comparison;
sval_t ret, tmp;
*** 316,326 ****
}
*rl = cast_rl(rl_type(*rl), ret_rl);
}
! static struct range_list *filter_by_comparison_call(char *c, struct expression *call, char **endp, struct range_list *start_rl)
{
struct symbol *type;
struct expression *arg;
struct range_list *casted_start, *right_orig;
int comparison;
--- 385,395 ----
}
*rl = cast_rl(rl_type(*rl), ret_rl);
}
! static struct range_list *filter_by_comparison_call(const char *c, struct expression *call, const char **endp, struct range_list *start_rl)
{
struct symbol *type;
struct expression *arg;
struct range_list *casted_start, *right_orig;
int comparison;
*** 342,354 ****
filter_by_comparison(&casted_start, comparison, right_orig);
return cast_rl(rl_type(start_rl), casted_start);
}
! static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, char *c, char **endp)
{
! char *start = c;
sval_t ret;
if (!strncmp(start, "max", 3)) {
ret = sval_type_max(type);
c += 3;
--- 411,423 ----
filter_by_comparison(&casted_start, comparison, right_orig);
return cast_rl(rl_type(start_rl), casted_start);
}
! static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, const char *c, const char **endp)
{
! const char *start = c;
sval_t ret;
if (!strncmp(start, "max", 3)) {
ret = sval_type_max(type);
c += 3;
*** 396,416 ****
c += 7;
} else if (start[0] == '[') {
/* this parses [==p0] comparisons */
get_val_from_key(1, type, start, call, &c, &ret);
} else if (type_positive_bits(type) == 64) {
! ret = sval_type_val(type, strtoull(start, &c, 0));
} else {
! ret = sval_type_val(type, strtoll(start, &c, 0));
}
*endp = c;
return ret;
}
! static char *jump_to_call_math(char *value)
{
! char *c = value;
while (*c && *c != '[')
c++;
if (!*c)
--- 465,485 ----
c += 7;
} else if (start[0] == '[') {
/* this parses [==p0] comparisons */
get_val_from_key(1, type, start, call, &c, &ret);
} else if (type_positive_bits(type) == 64) {
! ret = sval_type_val(type, strtoull(start, (char **)&c, 0));
} else {
! ret = sval_type_val(type, strtoll(start, (char **)&c, 0));
}
*endp = c;
return ret;
}
! static const char *jump_to_call_math(const char *value)
{
! const char *c = value;
while (*c && *c != '[')
c++;
if (!*c)
*** 420,435 ****
return NULL;
return c;
}
! static void str_to_rl_helper(struct expression *call, struct symbol *type, char *str, char **endp, struct range_list **rl)
{
struct range_list *rl_tmp = NULL;
! sval_t min, max;
! char *c;
min = sval_type_min(type);
max = sval_type_max(type);
c = str;
while (*c != '\0' && *c != '[') {
if (*c == '+') {
--- 489,505 ----
return NULL;
return c;
}
! static void str_to_rl_helper(struct expression *call, struct symbol *type, const char *str, const char **endp, struct range_list **rl)
{
struct range_list *rl_tmp = NULL;
! sval_t prev_min, min, max;
! const char *c;
+ prev_min = sval_type_min(type);
min = sval_type_min(type);
max = sval_type_max(type);
c = str;
while (*c != '\0' && *c != '[') {
if (*c == '+') {
*** 455,466 ****
add_range_t(type, &rl_tmp, min, min);
c++;
continue;
}
if (*c == '+') {
! min = sval_type_max(type);
c++;
}
if (*c != '-') {
sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
break;
}
--- 525,540 ----
add_range_t(type, &rl_tmp, min, min);
c++;
continue;
}
if (*c == '+') {
! min = prev_min;
! max = sval_type_max(type);
! add_range_t(type, &rl_tmp, min, max);
c++;
+ if (*c == '[' || *c == '\0')
+ break;
}
if (*c != '-') {
sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
break;
}
*** 470,481 ****
--- 544,559 ----
max = parse_val(1, call, type, c, &c);
if (!sval_fits(type, max))
max = sval_type_max(type);
if (*c == '+') {
max = sval_type_max(type);
+ add_range_t(type, &rl_tmp, min, max);
c++;
+ if (*c == '[' || *c == '\0')
+ break;
}
+ prev_min = max;
add_range_t(type, &rl_tmp, min, max);
if (*c == ')')
c++;
if (*c == ',')
c++;
*** 483,497 ****
*rl = rl_tmp;
*endp = c;
}
! static void str_to_dinfo(struct expression *call, struct symbol *type, char *value, struct data_info *dinfo)
{
struct range_list *math_rl;
! char *call_math;
! char *c;
struct range_list *rl = NULL;
if (!type)
type = &llong_ctype;
--- 561,575 ----
*rl = rl_tmp;
*endp = c;
}
! static void str_to_dinfo(struct expression *call, struct symbol *type, const char *value, struct data_info *dinfo)
{
struct range_list *math_rl;
! const char *call_math;
! const char *c;
struct range_list *rl = NULL;
if (!type)
type = &llong_ctype;
*** 531,549 ****
cast:
rl = cast_rl(type, rl);
dinfo->value_ranges = rl;
}
void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
{
struct data_info dinfo = {};
str_to_dinfo(NULL, type, value, &dinfo);
*rl = dinfo.value_ranges;
}
! void call_results_to_rl(struct expression *expr, struct symbol *type, char *value, struct range_list **rl)
{
struct data_info dinfo = {};
str_to_dinfo(strip_expr(expr), type, value, &dinfo);
*rl = dinfo.value_ranges;
--- 609,647 ----
cast:
rl = cast_rl(type, rl);
dinfo->value_ranges = rl;
}
+ static int rl_is_sane(struct range_list *rl)
+ {
+ struct data_range *tmp;
+ struct symbol *type;
+
+ type = rl_type(rl);
+ FOR_EACH_PTR(rl, tmp) {
+ if (!sval_fits(type, tmp->min))
+ return 0;
+ if (!sval_fits(type, tmp->max))
+ return 0;
+ if (sval_cmp(tmp->min, tmp->max) > 0)
+ return 0;
+ } END_FOR_EACH_PTR(tmp);
+
+ return 1;
+ }
+
void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
{
struct data_info dinfo = {};
str_to_dinfo(NULL, type, value, &dinfo);
+ if (!rl_is_sane(dinfo.value_ranges))
+ dinfo.value_ranges = alloc_whole_rl(type);
*rl = dinfo.value_ranges;
}
! void call_results_to_rl(struct expression *expr, struct symbol *type, const char *value, struct range_list **rl)
{
struct data_info dinfo = {};
str_to_dinfo(strip_expr(expr), type, value, &dinfo);
*rl = dinfo.value_ranges;
*** 559,568 ****
--- 657,685 ----
if (sval_is_min(drange->min) && sval_is_max(drange->max))
return 1;
return 0;
}
+ int is_unknown_ptr(struct range_list *rl)
+ {
+ struct data_range *drange;
+ int cnt = 0;
+
+ if (is_whole_rl(rl))
+ return 1;
+
+ FOR_EACH_PTR(rl, drange) {
+ if (++cnt >= 3)
+ return 0;
+ if (sval_cmp(drange->min, valid_ptr_min_sval) == 0 &&
+ sval_cmp(drange->max, valid_ptr_max_sval) == 0)
+ return 1;
+ } END_FOR_EACH_PTR(drange);
+
+ return 0;
+ }
+
int is_whole_rl_non_zero(struct range_list *rl)
{
struct data_range *drange;
if (ptr_list_empty(rl))
*** 670,679 ****
--- 787,845 ----
type = &ptr_ctype;
return alloc_rl(sval_type_min(type), sval_type_max(type));
}
+ static bool collapse_pointer_rl(struct range_list **rl, sval_t min, sval_t max)
+ {
+ struct range_list *new_rl = NULL;
+ struct data_range *tmp;
+ static bool recurse;
+ bool ret = false;
+ int cnt = 0;
+
+ /*
+ * With the mtag work, then we end up getting huge lists of mtags.
+ * That seems cool, but the problem is that we can only store about
+ * 8-10 mtags in the DB before we truncate the list. Also the mtags
+ * aren't really used at all so it's a waste of resources for now...
+ * In the future, we maybe will revisit this code.
+ *
+ */
+
+ if (recurse)
+ return false;
+ recurse = true;
+ if (!type_is_ptr(min.type))
+ goto out;
+
+ if (ptr_list_size((struct ptr_list *)*rl) < 8)
+ goto out;
+ FOR_EACH_PTR(*rl, tmp) {
+ if (!is_err_ptr(tmp->min))
+ cnt++;
+ } END_FOR_EACH_PTR(tmp);
+ if (cnt < 8)
+ goto out;
+
+ FOR_EACH_PTR(*rl, tmp) {
+ if (sval_cmp(tmp->min, valid_ptr_min_sval) >= 0 &&
+ sval_cmp(tmp->max, valid_ptr_max_sval) <= 0)
+ add_range(&new_rl, valid_ptr_min_sval, valid_ptr_max_sval);
+ else
+ add_range(&new_rl, tmp->min, tmp->max);
+ } END_FOR_EACH_PTR(tmp);
+
+ add_range(&new_rl, min, max);
+
+ *rl = new_rl;
+ ret = true;
+ out:
+ recurse = false;
+ return ret;
+ }
+
extern int rl_ptrlist_hack;
void add_range(struct range_list **list, sval_t min, sval_t max)
{
struct data_range *tmp;
struct data_range *new = NULL;
*** 710,719 ****
--- 876,888 ----
if (sval_cmp(min, max) > 0) {
min = sval_type_min(min.type);
max = sval_type_max(min.type);
}
+ if (collapse_pointer_rl(list, min, max))
+ return;
+
/*
* FIXME: This has a problem merging a range_list like: min-0,3-max
* with a range like 1-2. You end up with min-2,3-max instead of
* just min-max.
*/
*** 1217,1241 ****
} END_FOR_EACH_PTR(tmp);
return ret;
}
! static int rl_is_sane(struct range_list *rl)
{
! struct data_range *tmp;
! struct symbol *type;
!
! type = rl_type(rl);
! FOR_EACH_PTR(rl, tmp) {
! if (!sval_fits(type, tmp->min))
return 0;
! if (!sval_fits(type, tmp->max))
return 0;
- if (sval_cmp(tmp->min, tmp->max) > 0)
- return 0;
- } END_FOR_EACH_PTR(tmp);
-
return 1;
}
static int rl_type_consistent(struct range_list *rl)
{
--- 1386,1404 ----
} END_FOR_EACH_PTR(tmp);
return ret;
}
! int rl_fits_in_type(struct range_list *rl, struct symbol *type)
{
! if (type_bits(rl_type(rl)) <= type_bits(type))
! return 1;
! if (sval_cmp(rl_max(rl), sval_type_max(type)) > 0)
return 0;
! if (sval_is_negative(rl_min(rl)) &&
! sval_cmp(rl_min(rl), sval_type_min(type)) < 0)
return 0;
return 1;
}
static int rl_type_consistent(struct range_list *rl)
{
*** 1308,1375 ****
return alloc_whole_rl(type);
return ret;
}
! struct range_list *rl_invert(struct range_list *orig)
{
- struct range_list *ret = NULL;
struct data_range *tmp;
- sval_t gap_min, abs_max, sval;
! if (!orig)
! return NULL;
! if (type_bits(rl_type(orig)) < 0) /* void type mostly */
! return NULL;
!
! gap_min = sval_type_min(rl_min(orig).type);
! abs_max = sval_type_max(rl_max(orig).type);
!
! FOR_EACH_PTR(orig, tmp) {
! if (sval_cmp(tmp->min, gap_min) > 0) {
! sval = sval_type_val(tmp->min.type, tmp->min.value - 1);
! add_range(&ret, gap_min, sval);
! }
! if (sval_cmp(tmp->max, abs_max) == 0)
! return ret;
! gap_min = sval_type_val(tmp->max.type, tmp->max.value + 1);
} END_FOR_EACH_PTR(tmp);
! if (sval_cmp(gap_min, abs_max) <= 0)
! add_range(&ret, gap_min, abs_max);
!
! return ret;
}
! struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
{
! struct data_range *tmp;
- FOR_EACH_PTR(filter, tmp) {
- rl = remove_range(rl, tmp->min, tmp->max);
- } END_FOR_EACH_PTR(tmp);
! return rl;
}
struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
{
- struct range_list *one_orig;
- struct range_list *two_orig;
struct range_list *ret;
struct symbol *ret_type;
struct symbol *small_type;
struct symbol *large_type;
! if (!two)
return NULL;
- if (!one)
- return NULL;
- one_orig = one;
- two_orig = two;
-
ret_type = rl_type(one);
small_type = rl_type(one);
large_type = rl_type(two);
if (type_bits(rl_type(two)) < type_bits(small_type)) {
--- 1471,1550 ----
return alloc_whole_rl(type);
return ret;
}
! struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
{
struct data_range *tmp;
! FOR_EACH_PTR(filter, tmp) {
! rl = remove_range(rl, tmp->min, tmp->max);
} END_FOR_EACH_PTR(tmp);
! return rl;
}
! struct range_list *do_intersection(struct range_list *one_rl, struct range_list *two_rl)
{
! struct data_range *one, *two;
! struct range_list *ret = NULL;
! PREPARE_PTR_LIST(one_rl, one);
! PREPARE_PTR_LIST(two_rl, two);
!
! while (true) {
! if (!one || !two)
! break;
! if (sval_cmp(one->max, two->min) < 0) {
! NEXT_PTR_LIST(one);
! continue;
! }
! if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) <= 0) {
! add_range(&ret, two->min, one->max);
! NEXT_PTR_LIST(one);
! continue;
! }
! if (sval_cmp(one->min, two->min) >= 0 && sval_cmp(one->max, two->max) <= 0) {
! add_range(&ret, one->min, one->max);
! NEXT_PTR_LIST(one);
! continue;
! }
! if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) > 0) {
! add_range(&ret, two->min, two->max);
! NEXT_PTR_LIST(two);
! continue;
! }
! if (sval_cmp(one->min, two->max) <= 0 && sval_cmp(one->max, two->max) > 0) {
! add_range(&ret, one->min, two->max);
! NEXT_PTR_LIST(two);
! continue;
! }
! if (sval_cmp(one->min, two->max) <= 0) {
! sm_fatal("error calculating intersection of '%s' and '%s'", show_rl(one_rl), show_rl(two_rl));
! return NULL;
! }
! NEXT_PTR_LIST(two);
! }
!
! FINISH_PTR_LIST(two);
! FINISH_PTR_LIST(one);
!
! return ret;
}
struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
{
struct range_list *ret;
struct symbol *ret_type;
struct symbol *small_type;
struct symbol *large_type;
! if (!one || !two)
return NULL;
ret_type = rl_type(one);
small_type = rl_type(one);
large_type = rl_type(two);
if (type_bits(rl_type(two)) < type_bits(small_type)) {
*** 1378,1404 ****
}
one = cast_rl(large_type, one);
two = cast_rl(large_type, two);
! ret = one;
! one = rl_invert(one);
! two = rl_invert(two);
!
! ret = rl_filter(ret, one);
! ret = rl_filter(ret, two);
!
! one = cast_rl(small_type, one_orig);
! two = cast_rl(small_type, two_orig);
!
! one = rl_invert(one);
! two = rl_invert(two);
!
! ret = cast_rl(small_type, ret);
! ret = rl_filter(ret, one);
! ret = rl_filter(ret, two);
!
return cast_rl(ret_type, ret);
}
static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
{
--- 1553,1563 ----
}
one = cast_rl(large_type, one);
two = cast_rl(large_type, two);
! ret = do_intersection(one, two);
return cast_rl(ret_type, ret);
}
static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
{
*** 1518,1531 ****
--- 1677,1719 ----
ret = rl_union(neg_neg, neg_pos);
ret = rl_union(ret, pos_neg);
return rl_union(ret, pos_pos);
}
+ static struct range_list *ptr_add_mult(struct range_list *left, int op, struct range_list *right)
+ {
+ struct range_list *ret;
+ sval_t l_sval, r_sval, res;
+
+ /*
+ * This function is sort of the wrong API because it takes two pointer
+ * and adds them together. The caller is expected to figure out
+ * alignment. Neither of those are the correct things to do.
+ *
+ * Really this function is quite bogus...
+ */
+
+ if (rl_to_sval(left, &l_sval) && rl_to_sval(right, &r_sval)) {
+ res = sval_binop(l_sval, op, r_sval);
+ return alloc_rl(res, res);
+ }
+
+ if (rl_min(left).value != 0 || rl_max(right).value != 0) {
+ ret = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
+ return cast_rl(rl_type(left), ret);
+ }
+
+ return alloc_whole_rl(rl_type(left));
+ }
+
static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
{
sval_t min, max;
+ if (type_is_ptr(rl_type(left)) || type_is_ptr(rl_type(right)))
+ return ptr_add_mult(left, op, right);
+
if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
return NULL;
min = sval_binop(rl_min(left), op, rl_min(right));
if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
*** 1643,1673 ****
max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
return cast_rl(rl_type(left), alloc_rl(zero, max));
}
static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
{
! unsigned long long left_set, left_maybe;
! unsigned long long right_set, right_maybe;
! sval_t zero, max;
return NULL;
! left_set = rl_bits_always_set(left);
! left_maybe = rl_bits_maybe_set(left);
! right_set = rl_bits_always_set(right);
! right_maybe = rl_bits_maybe_set(right);
! zero = max = rl_min(left);
! zero.uvalue = 0;
! max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
! return cast_rl(rl_type(left), alloc_rl(zero, max));
}
struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
{
struct symbol *cast_type;
sval_t left_sval, right_sval;
struct range_list *ret = NULL;
--- 1831,1991 ----
max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
return cast_rl(rl_type(left), alloc_rl(zero, max));
}
+ static sval_t sval_lowest_set_bit(sval_t sval)
+ {
+ sval_t ret = { .type = sval.type };
+ int i;
+
+ for (i = 0; i < 64; i++) {
+ if (sval.uvalue & 1ULL << i) {
+ ret.uvalue = (1ULL << i);
+ return ret;
+ }
+ }
+ return ret;
+ }
+
+ static struct range_list *handle_AND_rl_sval(struct range_list *rl, sval_t sval)
+ {
+ struct range_list *known_rl;
+ sval_t zero = { 0 };
+ sval_t min;
+
+ zero.type = sval.type;
+ zero.value = 0;
+
+ if (sm_fls64(rl_max(rl).uvalue) < find_first_zero_bit(sval.uvalue) &&
+ sm_fls64(rl_min(rl).uvalue) < find_first_zero_bit(sval.uvalue))
+ return rl;
+
+ min = sval_lowest_set_bit(sval);
+
+ if (min.value != 0) {
+ sval_t max, mod;
+
+ max = rl_max(rl);
+ mod = sval_binop(max, '%', min);
+ if (mod.value) {
+ max = sval_binop(max, '-', mod);
+ max.value++;
+ if (max.value > 0 && sval_cmp(max, rl_max(rl)) < 0)
+ rl = remove_range(rl, max, rl_max(rl));
+ }
+ }
+
+ known_rl = alloc_rl(min, sval);
+
+ rl = rl_intersection(rl, known_rl);
+ zero = rl_min(rl);
+ zero.value = 0;
+ add_range(&rl, zero, zero);
+
+ return rl;
+ }
+
+ static struct range_list *fudge_AND_rl(struct range_list *rl)
+ {
+ struct range_list *ret;
+ sval_t min;
+
+ min = sval_lowest_set_bit(rl_min(rl));
+ ret = clone_rl(rl);
+ add_range(&ret, min, rl_min(rl));
+
+ return ret;
+ }
+
static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
{
! sval_t sval, zero;
! struct range_list *rl;
+ if (rl_to_sval(left, &sval))
+ return handle_AND_rl_sval(right, sval);
+ if (rl_to_sval(right, &sval))
+ return handle_AND_rl_sval(left, sval);
+
+ left = fudge_AND_rl(left);
+ right = fudge_AND_rl(right);
+
+ rl = rl_intersection(left, right);
+ zero = rl_min(rl);
+ zero.value = 0;
+ add_range(&rl, zero, zero);
+
+ return rl;
+ }
+
+ static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
+ {
+ struct range_list *left;
+ struct data_range *tmp;
+ struct range_list *ret = NULL;
+ sval_t zero = { .type = rl_type(left_orig), };
+ sval_t shift, min, max;
+ bool add_zero = false;
+
+ if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
return NULL;
+ if (shift.value == 0)
+ return left_orig;
! /* Cast to unsigned for easier left shift math */
! if (type_positive_bits(rl_type(left_orig)) < 32)
! left = cast_rl(&uint_ctype, left_orig);
! else if(type_positive_bits(rl_type(left_orig)) == 63)
! left = cast_rl(&ullong_ctype, left_orig);
! else
! left = left_orig;
! FOR_EACH_PTR(left, tmp) {
! min = tmp->min;
! max = tmp->max;
! if (min.value == 0 || max.value > sval_type_max(max.type).uvalue >> shift.uvalue)
! add_zero = true;
! if (min.value == 0 && max.value == 0)
! continue;
! if (min.value == 0)
! min.value = 1;
! min = sval_binop(min, SPECIAL_LEFTSHIFT, shift);
! max = sval_binop(max, SPECIAL_LEFTSHIFT, shift);
! add_range(&ret, min, max);
! } END_FOR_EACH_PTR(tmp);
! if (!rl_fits_in_type(ret, rl_type(left_orig)))
! add_zero = true;
! ret = cast_rl(rl_type(left_orig), ret);
! if (add_zero)
! add_range(&ret, zero, zero);
!
! return ret;
}
+ static struct range_list *handle_rshift(struct range_list *left_orig, struct range_list *right_orig)
+ {
+ struct data_range *tmp;
+ struct range_list *ret = NULL;
+ sval_t shift, min, max;
+
+ if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
+ return NULL;
+ if (shift.value == 0)
+ return left_orig;
+
+ FOR_EACH_PTR(left_orig, tmp) {
+ min = sval_binop(tmp->min, SPECIAL_RIGHTSHIFT, shift);
+ max = sval_binop(tmp->max, SPECIAL_RIGHTSHIFT, shift);
+ add_range(&ret, min, max);
+ } END_FOR_EACH_PTR(tmp);
+
+ return ret;
+ }
+
struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
{
struct symbol *cast_type;
sval_t left_sval, right_sval;
struct range_list *ret = NULL;
*** 1710,1723 ****
ret = handle_AND_rl(left, right);
break;
case '-':
ret = handle_sub_rl(left, right);
break;
- /* FIXME: Do the rest as well */
case SPECIAL_RIGHTSHIFT:
case SPECIAL_LEFTSHIFT:
! break;
}
return ret;
}
--- 2028,2041 ----
ret = handle_AND_rl(left, right);
break;
case '-':
ret = handle_sub_rl(left, right);
break;
case SPECIAL_RIGHTSHIFT:
+ return handle_rshift(left, right);
case SPECIAL_LEFTSHIFT:
! return handle_lshift(left, right);
}
return ret;
}