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 __DECLARE_ALLOCATOR(struct ptr_list, rl_ptrlist);
  28 
  29 static bool is_err_ptr(sval_t sval)
  30 {
  31         if (option_project != PROJ_KERNEL)
  32                 return false;
  33         if (!type_is_ptr(sval.type))
  34                 return false;
  35         if (sval.uvalue < -4095ULL)
  36                 return false;
  37         return true;
  38 }
  39 
  40 static char *get_err_pointer_str(struct data_range *drange)
  41 {
  42         static char buf[20];
  43 
  44         /*
  45          * The kernel has error pointers where you do essentially:
  46          *
  47          * return (void *)(unsigned long)-12;
  48          *
  49          * But what I want here is to print -12 instead of the unsigned version
  50          * of that.
  51          *
  52          */
  53         if (!is_err_ptr(drange->min))
  54                 return NULL;
  55 
  56         if (drange->min.value == drange->max.value)
  57                 snprintf(buf, sizeof(buf), "(%lld)", drange->min.value);
  58         else
  59                 snprintf(buf, sizeof(buf), "(%lld)-(%lld)", drange->min.value, drange->max.value);
  60         return buf;
  61 }
  62 
  63 char *show_rl(struct range_list *list)
  64 {
  65         struct data_range *prev_drange = NULL;
  66         struct data_range *tmp;
  67         char full[255];
  68         char *p = full;
  69         char *prev = full;
  70         char *err_ptr;
  71         int remain;
  72         int i = 0;
  73 
  74         full[0] = '\0';
  75 
  76         FOR_EACH_PTR(list, tmp) {
  77                 remain = full + sizeof(full) - p;
  78                 if (remain < 48) {
  79                         snprintf(prev, full + sizeof(full) - prev, ",%s-%s",
  80                                  sval_to_str(prev_drange->min),
  81                                  sval_to_str(sval_type_max(prev_drange->min.type)));
  82                         break;
  83                 }
  84                 prev_drange = tmp;
  85                 prev = p;
  86 
  87                 err_ptr = get_err_pointer_str(tmp);
  88                 if (err_ptr) {
  89                         p += snprintf(p, remain, "%s%s", i++ ? "," : "", err_ptr);
  90                 } else if (sval_cmp(tmp->min, tmp->max) == 0) {
  91                         p += snprintf(p, remain, "%s%s", i++ ? "," : "",
  92                                       sval_to_str(tmp->min));
  93                 } else {
  94                         p += snprintf(p, remain, "%s%s-%s", i++ ? "," : "",
  95                                       sval_to_str(tmp->min),
  96                                       sval_to_str(tmp->max));
  97                 }
  98         } END_FOR_EACH_PTR(tmp);
  99 
 100         return alloc_sname(full);
 101 }
 102 
 103 void free_all_rl(void)
 104 {
 105         clear_rl_ptrlist_alloc();
 106 }
 107 
 108 static int sval_too_big(struct symbol *type, sval_t sval)
 109 {
 110         if (type_bits(type) >= 32 &&
 111             type_bits(sval.type) <= type_bits(type))
 112                 return 0;
 113         if (sval.uvalue <= ((1ULL << type_bits(type)) - 1))
 114                 return 0;
 115         if (type_signed(sval.type)) {
 116                 if (type_unsigned(type)) {
 117                         unsigned long long neg = ~sval.uvalue;
 118                         if (neg <= sval_type_max(type).uvalue)
 119                                 return 0;
 120                 }
 121                 if (sval.value < sval_type_min(type).value)
 122                         return 1;
 123                 if (sval.value > sval_type_max(type).value)
 124                         return 1;
 125                 return 0;
 126         }
 127         if (sval.uvalue > sval_type_max(type).uvalue)
 128                 return 1;
 129         return 0;
 130 }
 131 
 132 static int truncates_nicely(struct symbol *type, sval_t min, sval_t max)
 133 {
 134         unsigned long long mask;
 135         int bits = type_bits(type);
 136 
 137         if (bits >= type_bits(min.type))
 138                 return 0;
 139 
 140         mask = -1ULL << bits;
 141         return (min.uvalue & mask) == (max.uvalue & mask);
 142 }
 143 
 144 static void add_range_t(struct symbol *type, struct range_list **rl, sval_t min, sval_t max)
 145 {
 146         /* If we're just adding a number, cast it and add it */
 147         if (sval_cmp(min, max) == 0) {
 148                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 149                 return;
 150         }
 151 
 152         /* If the range is within the type range then add it */
 153         if (sval_fits(type, min) && sval_fits(type, max)) {
 154                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 155                 return;
 156         }
 157 
 158         if (truncates_nicely(type, min, max)) {
 159                 add_range(rl, sval_cast(type, min), sval_cast(type, max));
 160                 return;
 161         }
 162 
 163         /*
 164          * If the range we are adding has more bits than the range type then
 165          * add the whole range type.  Eg:
 166          * 0x8000000000000000 - 0xf000000000000000 -> cast to int
 167          *
 168          */
 169         if (sval_too_big(type, min) || sval_too_big(type, max)) {
 170                 add_range(rl, sval_type_min(type), sval_type_max(type));
 171                 return;
 172         }
 173 
 174         /* Cast negative values to high positive values */
 175         if (sval_is_negative(min) && type_unsigned(type)) {
 176                 if (sval_is_positive(max)) {
 177                         if (sval_too_high(type, max)) {
 178                                 add_range(rl, sval_type_min(type), sval_type_max(type));
 179                                 return;
 180                         }
 181                         add_range(rl, sval_type_val(type, 0), sval_cast(type, max));
 182                         max = sval_type_max(type);
 183                 } else {
 184                         max = sval_cast(type, max);
 185                 }
 186                 min = sval_cast(type, min);
 187                 add_range(rl, min, max);
 188         }
 189 
 190         /* Cast high positive numbers to negative */
 191         if (sval_unsigned(max) && sval_is_negative(sval_cast(type, max))) {
 192                 if (!sval_is_negative(sval_cast(type, min))) {
 193                         add_range(rl, sval_cast(type, min), sval_type_max(type));
 194                         min = sval_type_min(type);
 195                 } else {
 196                         min = sval_cast(type, min);
 197                 }
 198                 max = sval_cast(type, max);
 199                 add_range(rl, min, max);
 200         }
 201 
 202         add_range(rl, sval_cast(type, min), sval_cast(type, max));
 203         return;
 204 }
 205 
 206 static int str_to_comparison_arg_helper(const char *str,
 207                 struct expression *call, int *comparison,
 208                 struct expression **arg, const char **endp)
 209 {
 210         int param;
 211         const char *c = str;
 212 
 213         if (*c != '[')
 214                 return 0;
 215         c++;
 216 
 217         if (*c == '<') {
 218                 c++;
 219                 if (*c == '=') {
 220                         *comparison = SPECIAL_LTE;
 221                         c++;
 222                 } else {
 223                         *comparison = '<';
 224                 }
 225         } else if (*c == '=') {
 226                 c++;
 227                 c++;
 228                 *comparison = SPECIAL_EQUAL;
 229         } else if (*c == '>') {
 230                 c++;
 231                 if (*c == '=') {
 232                         *comparison = SPECIAL_GTE;
 233                         c++;
 234                 } else {
 235                         *comparison = '>';
 236                 }
 237         } else if (*c == '!') {
 238                 c++;
 239                 c++;
 240                 *comparison = SPECIAL_NOTEQUAL;
 241         } else if (*c == '$') {
 242                 *comparison = SPECIAL_EQUAL;
 243         } else {
 244                 return 0;
 245         }
 246 
 247         if (*c != '$')
 248                 return 0;
 249         c++;
 250 
 251         param = strtoll(c, (char **)&c, 10);
 252         if (*c == ',' || *c == ']')
 253                 c++; /* skip the ']' character */
 254         if (endp)
 255                 *endp = (char *)c;
 256 
 257         if (!call)
 258                 return 0;
 259         *arg = get_argument_from_call_expr(call->args, param);
 260         if (!*arg)
 261                 return 0;
 262         if (*c == '-' && *(c + 1) == '>') {
 263                 char buf[256];
 264                 int n;
 265 
 266                 n = snprintf(buf, sizeof(buf), "$%s", c);
 267                 if (n >= sizeof(buf))
 268                         return 0;
 269                 if (buf[n - 1] == ']')
 270                         buf[n - 1] = '\0';
 271                 *arg = gen_expression_from_key(*arg, buf);
 272                 while (*c && *c != ']')
 273                         c++;
 274         }
 275         return 1;
 276 }
 277 
 278 int str_to_comparison_arg(const char *str, struct expression *call, int *comparison, struct expression **arg)
 279 {
 280         while (1) {
 281                 if (!*str)
 282                         return 0;
 283                 if (*str == '[')
 284                         break;
 285                 str++;
 286         }
 287         return str_to_comparison_arg_helper(str, call, comparison, arg, NULL);
 288 }
 289 
 290 static int get_val_from_key(int use_max, struct symbol *type, const char *c, struct expression *call, const char **endp, sval_t *sval)
 291 {
 292         struct expression *arg;
 293         int comparison;
 294         sval_t ret, tmp;
 295 
 296         if (use_max)
 297                 ret = sval_type_max(type);
 298         else
 299                 ret = sval_type_min(type);
 300 
 301         if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp)) {
 302                 *sval = ret;
 303                 return 0;
 304         }
 305 
 306         if (use_max && get_implied_max(arg, &tmp)) {
 307                 ret = tmp;
 308                 if (comparison == '<') {
 309                         tmp.value = 1;
 310                         ret = sval_binop(ret, '-', tmp);
 311                 }
 312         }
 313         if (!use_max && get_implied_min(arg, &tmp)) {
 314                 ret = tmp;
 315                 if (comparison == '>') {
 316                         tmp.value = 1;
 317                         ret = sval_binop(ret, '+', tmp);
 318                 }
 319         }
 320 
 321         *sval = ret;
 322         return 1;
 323 }
 324 
 325 static sval_t add_one(sval_t sval)
 326 {
 327         sval.value++;
 328         return sval;
 329 }
 330 
 331 static sval_t sub_one(sval_t sval)
 332 {
 333         sval.value--;
 334         return sval;
 335 }
 336 
 337 void filter_by_comparison(struct range_list **rl, int comparison, struct range_list *right)
 338 {
 339         struct range_list *left_orig = *rl;
 340         struct range_list *right_orig = right;
 341         struct range_list *ret_rl = *rl;
 342         struct symbol *cast_type;
 343         sval_t min, max;
 344 
 345         cast_type = rl_type(left_orig);
 346         if (sval_type_max(rl_type(left_orig)).uvalue < sval_type_max(rl_type(right_orig)).uvalue)
 347                 cast_type = rl_type(right_orig);
 348         if (sval_type_max(cast_type).uvalue < INT_MAX)
 349                 cast_type = &int_ctype;
 350 
 351         min = sval_type_min(cast_type);
 352         max = sval_type_max(cast_type);
 353         left_orig = cast_rl(cast_type, left_orig);
 354         right_orig = cast_rl(cast_type, right_orig);
 355 
 356         switch (comparison) {
 357         case '<':
 358         case SPECIAL_UNSIGNED_LT:
 359                 ret_rl = remove_range(left_orig, rl_max(right_orig), max);
 360                 break;
 361         case SPECIAL_LTE:
 362         case SPECIAL_UNSIGNED_LTE:
 363                 if (!sval_is_max(rl_max(right_orig)))
 364                         ret_rl = remove_range(left_orig, add_one(rl_max(right_orig)), max);
 365                 break;
 366         case SPECIAL_EQUAL:
 367                 ret_rl = rl_intersection(left_orig, right_orig);
 368                 break;
 369         case SPECIAL_GTE:
 370         case SPECIAL_UNSIGNED_GTE:
 371                 if (!sval_is_min(rl_min(right_orig)))
 372                         ret_rl = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
 373                 break;
 374         case '>':
 375         case SPECIAL_UNSIGNED_GT:
 376                 ret_rl = remove_range(left_orig, min, rl_min(right_orig));
 377                 break;
 378         case SPECIAL_NOTEQUAL:
 379                 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
 380                         ret_rl = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
 381                 break;
 382         default:
 383                 sm_perror("unhandled comparison %s", show_special(comparison));
 384                 return;
 385         }
 386 
 387         *rl = cast_rl(rl_type(*rl), ret_rl);
 388 }
 389 
 390 static struct range_list *filter_by_comparison_call(const char *c, struct expression *call, const char **endp, struct range_list *start_rl)
 391 {
 392         struct symbol *type;
 393         struct expression *arg;
 394         struct range_list *casted_start, *right_orig;
 395         int comparison;
 396 
 397         if (!str_to_comparison_arg_helper(c, call, &comparison, &arg, endp))
 398                 return start_rl;
 399 
 400         if (!get_implied_rl(arg, &right_orig))
 401                 return start_rl;
 402 
 403         type = &int_ctype;
 404         if (type_positive_bits(rl_type(start_rl)) > type_positive_bits(type))
 405                 type = rl_type(start_rl);
 406         if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
 407                 type = rl_type(right_orig);
 408 
 409         casted_start = cast_rl(type, start_rl);
 410         right_orig = cast_rl(type, right_orig);
 411 
 412         filter_by_comparison(&casted_start, comparison, right_orig);
 413         return cast_rl(rl_type(start_rl), casted_start);
 414 }
 415 
 416 static sval_t parse_val(int use_max, struct expression *call, struct symbol *type, const char *c, const char **endp)
 417 {
 418         const char *start = c;
 419         sval_t ret;
 420 
 421         if (!strncmp(start, "max", 3)) {
 422                 ret = sval_type_max(type);
 423                 c += 3;
 424         } else if (!strncmp(start, "u64max", 6)) {
 425                 ret = sval_type_val(type, ULLONG_MAX);
 426                 c += 6;
 427         } else if (!strncmp(start, "s64max", 6)) {
 428                 ret = sval_type_val(type, LLONG_MAX);
 429                 c += 6;
 430         } else if (!strncmp(start, "u32max", 6)) {
 431                 ret = sval_type_val(type, UINT_MAX);
 432                 c += 6;
 433         } else if (!strncmp(start, "s32max", 6)) {
 434                 ret = sval_type_val(type, INT_MAX);
 435                 c += 6;
 436         } else if (!strncmp(start, "u16max", 6)) {
 437                 ret = sval_type_val(type, USHRT_MAX);
 438                 c += 6;
 439         } else if (!strncmp(start, "s16max", 6)) {
 440                 ret = sval_type_val(type, SHRT_MAX);
 441                 c += 6;
 442         } else if (!strncmp(start, "min", 3)) {
 443                 ret = sval_type_min(type);
 444                 c += 3;
 445         } else if (!strncmp(start, "s64min", 6)) {
 446                 ret = sval_type_val(type, LLONG_MIN);
 447                 c += 6;
 448         } else if (!strncmp(start, "s32min", 6)) {
 449                 ret = sval_type_val(type, INT_MIN);
 450                 c += 6;
 451         } else if (!strncmp(start, "s16min", 6)) {
 452                 ret = sval_type_val(type, SHRT_MIN);
 453                 c += 6;
 454         } else if (!strncmp(start, "long_min", 8)) {
 455                 ret = sval_type_val(type, LONG_MIN);
 456                 c += 8;
 457         } else if (!strncmp(start, "long_max", 8)) {
 458                 ret = sval_type_val(type, LONG_MAX);
 459                 c += 8;
 460         } else if (!strncmp(start, "ulong_max", 9)) {
 461                 ret = sval_type_val(type, ULONG_MAX);
 462                 c += 9;
 463         } else if (!strncmp(start, "ptr_max", 7)) {
 464                 ret = sval_type_val(type, valid_ptr_max);
 465                 c += 7;
 466         } else if (start[0] == '[') {
 467                 /* this parses [==p0] comparisons */
 468                 get_val_from_key(1, type, start, call, &c, &ret);
 469         } else if (type_positive_bits(type) == 64) {
 470                 ret = sval_type_val(type, strtoull(start, (char **)&c, 0));
 471         } else {
 472                 ret = sval_type_val(type, strtoll(start, (char **)&c, 0));
 473         }
 474         *endp = c;
 475         return ret;
 476 }
 477 
 478 static const char *jump_to_call_math(const char *value)
 479 {
 480         const char *c = value;
 481 
 482         while (*c && *c != '[')
 483                 c++;
 484 
 485         if (!*c)
 486                 return NULL;
 487         c++;
 488         if (*c == '<' || *c == '=' || *c == '>' || *c == '!')
 489                 return NULL;
 490 
 491         return c;
 492 }
 493 
 494 static void str_to_rl_helper(struct expression *call, struct symbol *type, const char *str, const char **endp, struct range_list **rl)
 495 {
 496         struct range_list *rl_tmp = NULL;
 497         sval_t prev_min, min, max;
 498         const char *c;
 499 
 500         prev_min = sval_type_min(type);
 501         min = sval_type_min(type);
 502         max = sval_type_max(type);
 503         c = str;
 504         while (*c != '\0' && *c != '[') {
 505                 if (*c == '+') {
 506                         if (sval_cmp(min, sval_type_min(type)) != 0)
 507                                 min = max;
 508                         max = sval_type_max(type);
 509                         add_range_t(type, &rl_tmp, min, max);
 510                         break;
 511                 }
 512                 if (*c == '(')
 513                         c++;
 514                 min = parse_val(0, call, type, c, &c);
 515                 if (!sval_fits(type, min))
 516                         min = sval_type_min(type);
 517                 max = min;
 518                 if (*c == ')')
 519                         c++;
 520                 if (*c == '\0' || *c == '[') {
 521                         add_range_t(type, &rl_tmp, min, min);
 522                         break;
 523                 }
 524                 if (*c == ',') {
 525                         add_range_t(type, &rl_tmp, min, min);
 526                         c++;
 527                         continue;
 528                 }
 529                 if (*c == '+') {
 530                         min = prev_min;
 531                         max = sval_type_max(type);
 532                         add_range_t(type, &rl_tmp, min, max);
 533                         c++;
 534                         if (*c == '[' || *c == '\0')
 535                                 break;
 536                 }
 537                 if (*c != '-') {
 538                         sm_msg("debug XXX: trouble parsing %s c = %s", str, c);
 539                         break;
 540                 }
 541                 c++;
 542                 if (*c == '(')
 543                         c++;
 544                 max = parse_val(1, call, type, c, &c);
 545                 if (!sval_fits(type, max))
 546                         max = sval_type_max(type);
 547                 if (*c == '+') {
 548                         max = sval_type_max(type);
 549                         add_range_t(type, &rl_tmp, min, max);
 550                         c++;
 551                         if (*c == '[' || *c == '\0')
 552                                 break;
 553                 }
 554                 prev_min = max;
 555                 add_range_t(type, &rl_tmp, min, max);
 556                 if (*c == ')')
 557                         c++;
 558                 if (*c == ',')
 559                         c++;
 560         }
 561 
 562         *rl = rl_tmp;
 563         *endp = c;
 564 }
 565 
 566 static void str_to_dinfo(struct expression *call, struct symbol *type, const char *value, struct data_info *dinfo)
 567 {
 568         struct range_list *math_rl;
 569         const char *call_math;
 570         const char *c;
 571         struct range_list *rl = NULL;
 572 
 573         if (!type)
 574                 type = &llong_ctype;
 575 
 576         if (strcmp(value, "empty") == 0)
 577                 return;
 578 
 579         if (strncmp(value, "[==$", 4) == 0) {
 580                 struct expression *arg;
 581                 int comparison;
 582 
 583                 if (!str_to_comparison_arg(value, call, &comparison, &arg))
 584                         return;
 585                 if (!get_implied_rl(arg, &rl))
 586                         return;
 587                 goto cast;
 588         }
 589 
 590         str_to_rl_helper(call, type, value, &c, &rl);
 591         if (*c == '\0')
 592                 goto cast;
 593 
 594         call_math = jump_to_call_math(value);
 595         if (call_math && parse_call_math_rl(call, call_math, &math_rl)) {
 596                 rl = rl_intersection(rl, math_rl);
 597                 goto cast;
 598         }
 599 
 600         /*
 601          * For now if we already tried to handle the call math and couldn't
 602          * figure it out then bail.
 603          */
 604         if (jump_to_call_math(c) == c + 1)
 605                 goto cast;
 606 
 607         rl = filter_by_comparison_call(c, call, &c, rl);
 608 
 609 cast:
 610         rl = cast_rl(type, rl);
 611         dinfo->value_ranges = rl;
 612 }
 613 
 614 static int rl_is_sane(struct range_list *rl)
 615 {
 616         struct data_range *tmp;
 617         struct symbol *type;
 618 
 619         type = rl_type(rl);
 620         FOR_EACH_PTR(rl, tmp) {
 621                 if (!sval_fits(type, tmp->min))
 622                         return 0;
 623                 if (!sval_fits(type, tmp->max))
 624                         return 0;
 625                 if (sval_cmp(tmp->min, tmp->max) > 0)
 626                         return 0;
 627         } END_FOR_EACH_PTR(tmp);
 628 
 629         return 1;
 630 }
 631 
 632 void str_to_rl(struct symbol *type, char *value, struct range_list **rl)
 633 {
 634         struct data_info dinfo = {};
 635 
 636         str_to_dinfo(NULL, type, value, &dinfo);
 637         if (!rl_is_sane(dinfo.value_ranges))
 638                 dinfo.value_ranges = alloc_whole_rl(type);
 639         *rl = dinfo.value_ranges;
 640 }
 641 
 642 void call_results_to_rl(struct expression *expr, struct symbol *type, const char *value, struct range_list **rl)
 643 {
 644         struct data_info dinfo = {};
 645 
 646         str_to_dinfo(strip_expr(expr), type, value, &dinfo);
 647         *rl = dinfo.value_ranges;
 648 }
 649 
 650 int is_whole_rl(struct range_list *rl)
 651 {
 652         struct data_range *drange;
 653 
 654         if (ptr_list_empty(rl))
 655                 return 0;
 656         drange = first_ptr_list((struct ptr_list *)rl);
 657         if (sval_is_min(drange->min) && sval_is_max(drange->max))
 658                 return 1;
 659         return 0;
 660 }
 661 
 662 int is_unknown_ptr(struct range_list *rl)
 663 {
 664         struct data_range *drange;
 665         int cnt = 0;
 666 
 667         if (is_whole_rl(rl))
 668                 return 1;
 669 
 670         FOR_EACH_PTR(rl, drange) {
 671                 if (++cnt >= 3)
 672                         return 0;
 673                 if (sval_cmp(drange->min, valid_ptr_min_sval) == 0 &&
 674                     sval_cmp(drange->max, valid_ptr_max_sval) == 0)
 675                         return 1;
 676         } END_FOR_EACH_PTR(drange);
 677 
 678         return 0;
 679 }
 680 
 681 int is_whole_rl_non_zero(struct range_list *rl)
 682 {
 683         struct data_range *drange;
 684 
 685         if (ptr_list_empty(rl))
 686                 return 0;
 687         drange = first_ptr_list((struct ptr_list *)rl);
 688         if (sval_unsigned(drange->min) &&
 689             drange->min.value == 1 &&
 690             sval_is_max(drange->max))
 691                 return 1;
 692         if (!sval_is_min(drange->min) || drange->max.value != -1)
 693                 return 0;
 694         drange = last_ptr_list((struct ptr_list *)rl);
 695         if (drange->min.value != 1 || !sval_is_max(drange->max))
 696                 return 0;
 697         return 1;
 698 }
 699 
 700 sval_t rl_min(struct range_list *rl)
 701 {
 702         struct data_range *drange;
 703         sval_t ret;
 704 
 705         ret.type = &llong_ctype;
 706         ret.value = LLONG_MIN;
 707         if (ptr_list_empty(rl))
 708                 return ret;
 709         drange = first_ptr_list((struct ptr_list *)rl);
 710         return drange->min;
 711 }
 712 
 713 sval_t rl_max(struct range_list *rl)
 714 {
 715         struct data_range *drange;
 716         sval_t ret;
 717 
 718         ret.type = &llong_ctype;
 719         ret.value = LLONG_MAX;
 720         if (ptr_list_empty(rl))
 721                 return ret;
 722         drange = last_ptr_list((struct ptr_list *)rl);
 723         return drange->max;
 724 }
 725 
 726 int rl_to_sval(struct range_list *rl, sval_t *sval)
 727 {
 728         sval_t min, max;
 729 
 730         if (!rl)
 731                 return 0;
 732 
 733         min = rl_min(rl);
 734         max = rl_max(rl);
 735         if (sval_cmp(min, max) != 0)
 736                 return 0;
 737         *sval = min;
 738         return 1;
 739 }
 740 
 741 struct symbol *rl_type(struct range_list *rl)
 742 {
 743         if (!rl)
 744                 return NULL;
 745         return rl_min(rl).type;
 746 }
 747 
 748 static struct data_range *alloc_range_helper_sval(sval_t min, sval_t max, int perm)
 749 {
 750         struct data_range *ret;
 751 
 752         if (perm)
 753                 ret = __alloc_perm_data_range(0);
 754         else
 755                 ret = __alloc_data_range(0);
 756         ret->min = min;
 757         ret->max = max;
 758         return ret;
 759 }
 760 
 761 struct data_range *alloc_range(sval_t min, sval_t max)
 762 {
 763         return alloc_range_helper_sval(min, max, 0);
 764 }
 765 
 766 struct data_range *alloc_range_perm(sval_t min, sval_t max)
 767 {
 768         return alloc_range_helper_sval(min, max, 1);
 769 }
 770 
 771 struct range_list *alloc_rl(sval_t min, sval_t max)
 772 {
 773         struct range_list *rl = NULL;
 774 
 775         if (sval_cmp(min, max) > 0)
 776                 return alloc_whole_rl(min.type);
 777 
 778         add_range(&rl, min, max);
 779         return rl;
 780 }
 781 
 782 struct range_list *alloc_whole_rl(struct symbol *type)
 783 {
 784         if (!type || type_positive_bits(type) < 0)
 785                 type = &llong_ctype;
 786         if (type->type == SYM_ARRAY)
 787                 type = &ptr_ctype;
 788 
 789         return alloc_rl(sval_type_min(type), sval_type_max(type));
 790 }
 791 
 792 static bool collapse_pointer_rl(struct range_list **rl, sval_t min, sval_t max)
 793 {
 794         struct range_list *new_rl = NULL;
 795         struct data_range *tmp;
 796         static bool recurse;
 797         bool ret = false;
 798         int cnt = 0;
 799 
 800         /*
 801          * With the mtag work, then we end up getting huge lists of mtags.
 802          * That seems cool, but the problem is that we can only store about
 803          * 8-10 mtags in the DB before we truncate the list.  Also the mtags
 804          * aren't really used at all so it's a waste of resources for now...
 805          * In the future, we maybe will revisit this code.
 806          *
 807          */
 808 
 809         if (recurse)
 810                 return false;
 811         recurse = true;
 812         if (!type_is_ptr(min.type))
 813                 goto out;
 814 
 815         if (ptr_list_size((struct ptr_list *)*rl) < 8)
 816                 goto out;
 817         FOR_EACH_PTR(*rl, tmp) {
 818                 if (!is_err_ptr(tmp->min))
 819                         cnt++;
 820         } END_FOR_EACH_PTR(tmp);
 821         if (cnt < 8)
 822                 goto out;
 823 
 824         FOR_EACH_PTR(*rl, tmp) {
 825                 if (sval_cmp(tmp->min, valid_ptr_min_sval) >= 0 &&
 826                     sval_cmp(tmp->max, valid_ptr_max_sval) <= 0)
 827                         add_range(&new_rl, valid_ptr_min_sval, valid_ptr_max_sval);
 828                 else
 829                         add_range(&new_rl, tmp->min, tmp->max);
 830         } END_FOR_EACH_PTR(tmp);
 831 
 832         add_range(&new_rl, min, max);
 833 
 834         *rl = new_rl;
 835         ret = true;
 836 out:
 837         recurse = false;
 838         return ret;
 839 }
 840 
 841 extern int rl_ptrlist_hack;
 842 void add_range(struct range_list **list, sval_t min, sval_t max)
 843 {
 844         struct data_range *tmp;
 845         struct data_range *new = NULL;
 846         int check_next = 0;
 847 
 848         /*
 849          * There is at least on valid reason why the types might be confusing
 850          * and that's when you have a void pointer and on some paths you treat
 851          * it as a u8 pointer and on other paths you treat it as a u16 pointer.
 852          * This case is hard to deal with.
 853          *
 854          * There are other cases where we probably should be more specific about
 855          * the types than we are.  For example, we end up merging a lot of ulong
 856          * with pointers and I have not figured out why we do that.
 857          *
 858          * But this hack works for both cases, I think.  We cast it to pointers
 859          * or we use the bigger size.
 860          *
 861          */
 862         if (*list && rl_type(*list) != min.type) {
 863                 if (rl_type(*list)->type == SYM_PTR) {
 864                         min = sval_cast(rl_type(*list), min);
 865                         max = sval_cast(rl_type(*list), max);
 866                 } else if (min.type->type == SYM_PTR) {
 867                         *list = cast_rl(min.type, *list);
 868                 } else if (type_bits(rl_type(*list)) >= type_bits(min.type)) {
 869                         min = sval_cast(rl_type(*list), min);
 870                         max = sval_cast(rl_type(*list), max);
 871                 } else {
 872                         *list = cast_rl(min.type, *list);
 873                 }
 874         }
 875 
 876         if (sval_cmp(min, max) > 0) {
 877                 min = sval_type_min(min.type);
 878                 max = sval_type_max(min.type);
 879         }
 880 
 881         if (collapse_pointer_rl(list, min, max))
 882                 return;
 883 
 884         /*
 885          * FIXME:  This has a problem merging a range_list like: min-0,3-max
 886          * with a range like 1-2.  You end up with min-2,3-max instead of
 887          * just min-max.
 888          */
 889         FOR_EACH_PTR(*list, tmp) {
 890                 if (check_next) {
 891                         /* Sometimes we overlap with more than one range
 892                            so we have to delete or modify the next range. */
 893                         if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
 894                                 /* join 2 ranges here */
 895                                 new->max = tmp->max;
 896                                 DELETE_CURRENT_PTR(tmp);
 897                                 return;
 898                         }
 899 
 900                         /* Doesn't overlap with the next one. */
 901                         if (sval_cmp(max, tmp->min) < 0)
 902                                 return;
 903 
 904                         if (sval_cmp(max, tmp->max) <= 0) {
 905                                 /* Partially overlaps the next one. */
 906                                 new->max = tmp->max;
 907                                 DELETE_CURRENT_PTR(tmp);
 908                                 return;
 909                         } else {
 910                                 /* Completely overlaps the next one. */
 911                                 DELETE_CURRENT_PTR(tmp);
 912                                 /* there could be more ranges to delete */
 913                                 continue;
 914                         }
 915                 }
 916                 if (!sval_is_max(max) && max.value + 1 == tmp->min.value) {
 917                         /* join 2 ranges into a big range */
 918                         new = alloc_range(min, tmp->max);
 919                         REPLACE_CURRENT_PTR(tmp, new);
 920                         return;
 921                 }
 922                 if (sval_cmp(max, tmp->min) < 0) { /* new range entirely below */
 923                         new = alloc_range(min, max);
 924                         INSERT_CURRENT(new, tmp);
 925                         return;
 926                 }
 927                 if (sval_cmp(min, tmp->min) < 0) { /* new range partially below */
 928                         if (sval_cmp(max, tmp->max) < 0)
 929                                 max = tmp->max;
 930                         else
 931                                 check_next = 1;
 932                         new = alloc_range(min, max);
 933                         REPLACE_CURRENT_PTR(tmp, new);
 934                         if (!check_next)
 935                                 return;
 936                         continue;
 937                 }
 938                 if (sval_cmp(max, tmp->max) <= 0) /* new range already included */
 939                         return;
 940                 if (sval_cmp(min, tmp->max) <= 0) { /* new range partially above */
 941                         min = tmp->min;
 942                         new = alloc_range(min, max);
 943                         REPLACE_CURRENT_PTR(tmp, new);
 944                         check_next = 1;
 945                         continue;
 946                 }
 947                 if (!sval_is_min(min) && min.value - 1 == tmp->max.value) {
 948                         /* join 2 ranges into a big range */
 949                         new = alloc_range(tmp->min, max);
 950                         REPLACE_CURRENT_PTR(tmp, new);
 951                         check_next = 1;
 952                         continue;
 953                 }
 954                 /* the new range is entirely above the existing ranges */
 955         } END_FOR_EACH_PTR(tmp);
 956         if (check_next)
 957                 return;
 958         new = alloc_range(min, max);
 959 
 960         rl_ptrlist_hack = 1;
 961         add_ptr_list(list, new);
 962         rl_ptrlist_hack = 0;
 963 }
 964 
 965 struct range_list *clone_rl(struct range_list *list)
 966 {
 967         struct data_range *tmp;
 968         struct range_list *ret = NULL;
 969 
 970         FOR_EACH_PTR(list, tmp) {
 971                 add_ptr_list(&ret, tmp);
 972         } END_FOR_EACH_PTR(tmp);
 973         return ret;
 974 }
 975 
 976 struct range_list *clone_rl_permanent(struct range_list *list)
 977 {
 978         struct data_range *tmp;
 979         struct data_range *new;
 980         struct range_list *ret = NULL;
 981 
 982         FOR_EACH_PTR(list, tmp) {
 983                 new = alloc_range_perm(tmp->min, tmp->max);
 984                 add_ptr_list(&ret, new);
 985         } END_FOR_EACH_PTR(tmp);
 986         return ret;
 987 }
 988 
 989 struct range_list *rl_union(struct range_list *one, struct range_list *two)
 990 {
 991         struct data_range *tmp;
 992         struct range_list *ret = NULL;
 993 
 994         FOR_EACH_PTR(one, tmp) {
 995                 add_range(&ret, tmp->min, tmp->max);
 996         } END_FOR_EACH_PTR(tmp);
 997         FOR_EACH_PTR(two, tmp) {
 998                 add_range(&ret, tmp->min, tmp->max);
 999         } END_FOR_EACH_PTR(tmp);
1000         return ret;
1001 }
1002 
1003 struct range_list *remove_range(struct range_list *list, sval_t min, sval_t max)
1004 {
1005         struct data_range *tmp;
1006         struct range_list *ret = NULL;
1007 
1008         if (!list)
1009                 return NULL;
1010 
1011         min = sval_cast(rl_type(list), min);
1012         max = sval_cast(rl_type(list), max);
1013         if (sval_cmp(min, max) > 0) {
1014                 sval_t tmp = min;
1015                 min = max;
1016                 max = tmp;
1017         }
1018 
1019         FOR_EACH_PTR(list, tmp) {
1020                 if (sval_cmp(tmp->max, min) < 0) {
1021                         add_range(&ret, tmp->min, tmp->max);
1022                         continue;
1023                 }
1024                 if (sval_cmp(tmp->min, max) > 0) {
1025                         add_range(&ret, tmp->min, tmp->max);
1026                         continue;
1027                 }
1028                 if (sval_cmp(tmp->min, min) >= 0 && sval_cmp(tmp->max, max) <= 0)
1029                         continue;
1030                 if (sval_cmp(tmp->min, min) >= 0) {
1031                         max.value++;
1032                         add_range(&ret, max, tmp->max);
1033                 } else if (sval_cmp(tmp->max, max) <= 0) {
1034                         min.value--;
1035                         add_range(&ret, tmp->min, min);
1036                 } else {
1037                         min.value--;
1038                         max.value++;
1039                         add_range(&ret, tmp->min, min);
1040                         add_range(&ret, max, tmp->max);
1041                 }
1042         } END_FOR_EACH_PTR(tmp);
1043         return ret;
1044 }
1045 
1046 int ranges_equiv(struct data_range *one, struct data_range *two)
1047 {
1048         if (!one && !two)
1049                 return 1;
1050         if (!one || !two)
1051                 return 0;
1052         if (sval_cmp(one->min, two->min) != 0)
1053                 return 0;
1054         if (sval_cmp(one->max, two->max) != 0)
1055                 return 0;
1056         return 1;
1057 }
1058 
1059 int rl_equiv(struct range_list *one, struct range_list *two)
1060 {
1061         struct data_range *one_range;
1062         struct data_range *two_range;
1063 
1064         if (one == two)
1065                 return 1;
1066 
1067         PREPARE_PTR_LIST(one, one_range);
1068         PREPARE_PTR_LIST(two, two_range);
1069         for (;;) {
1070                 if (!one_range && !two_range)
1071                         return 1;
1072                 if (!ranges_equiv(one_range, two_range))
1073                         return 0;
1074                 NEXT_PTR_LIST(one_range);
1075                 NEXT_PTR_LIST(two_range);
1076         }
1077         FINISH_PTR_LIST(two_range);
1078         FINISH_PTR_LIST(one_range);
1079 
1080         return 1;
1081 }
1082 
1083 int true_comparison_range(struct data_range *left, int comparison, struct data_range *right)
1084 {
1085         switch (comparison) {
1086         case '<':
1087         case SPECIAL_UNSIGNED_LT:
1088                 if (sval_cmp(left->min, right->max) < 0)
1089                         return 1;
1090                 return 0;
1091         case SPECIAL_UNSIGNED_LTE:
1092         case SPECIAL_LTE:
1093                 if (sval_cmp(left->min, right->max) <= 0)
1094                         return 1;
1095                 return 0;
1096         case SPECIAL_EQUAL:
1097                 if (sval_cmp(left->max, right->min) < 0)
1098                         return 0;
1099                 if (sval_cmp(left->min, right->max) > 0)
1100                         return 0;
1101                 return 1;
1102         case SPECIAL_UNSIGNED_GTE:
1103         case SPECIAL_GTE:
1104                 if (sval_cmp(left->max, right->min) >= 0)
1105                         return 1;
1106                 return 0;
1107         case '>':
1108         case SPECIAL_UNSIGNED_GT:
1109                 if (sval_cmp(left->max, right->min) > 0)
1110                         return 1;
1111                 return 0;
1112         case SPECIAL_NOTEQUAL:
1113                 if (sval_cmp(left->min, left->max) != 0)
1114                         return 1;
1115                 if (sval_cmp(right->min, right->max) != 0)
1116                         return 1;
1117                 if (sval_cmp(left->min, right->min) != 0)
1118                         return 1;
1119                 return 0;
1120         default:
1121                 sm_perror("unhandled comparison %d", comparison);
1122                 return 0;
1123         }
1124         return 0;
1125 }
1126 
1127 int true_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1128 {
1129         if (left)
1130                 return true_comparison_range(var, comparison, val);
1131         else
1132                 return true_comparison_range(val, comparison, var);
1133 }
1134 
1135 static int false_comparison_range_sval(struct data_range *left, int comparison, struct data_range *right)
1136 {
1137         switch (comparison) {
1138         case '<':
1139         case SPECIAL_UNSIGNED_LT:
1140                 if (sval_cmp(left->max, right->min) >= 0)
1141                         return 1;
1142                 return 0;
1143         case SPECIAL_UNSIGNED_LTE:
1144         case SPECIAL_LTE:
1145                 if (sval_cmp(left->max, right->min) > 0)
1146                         return 1;
1147                 return 0;
1148         case SPECIAL_EQUAL:
1149                 if (sval_cmp(left->min, left->max) != 0)
1150                         return 1;
1151                 if (sval_cmp(right->min, right->max) != 0)
1152                         return 1;
1153                 if (sval_cmp(left->min, right->min) != 0)
1154                         return 1;
1155                 return 0;
1156         case SPECIAL_UNSIGNED_GTE:
1157         case SPECIAL_GTE:
1158                 if (sval_cmp(left->min, right->max) < 0)
1159                         return 1;
1160                 return 0;
1161         case '>':
1162         case SPECIAL_UNSIGNED_GT:
1163                 if (sval_cmp(left->min, right->max) <= 0)
1164                         return 1;
1165                 return 0;
1166         case SPECIAL_NOTEQUAL:
1167                 if (sval_cmp(left->max, right->min) < 0)
1168                         return 0;
1169                 if (sval_cmp(left->min, right->max) > 0)
1170                         return 0;
1171                 return 1;
1172         default:
1173                 sm_perror("unhandled comparison %d", comparison);
1174                 return 0;
1175         }
1176         return 0;
1177 }
1178 
1179 int false_comparison_range_LR(int comparison, struct data_range *var, struct data_range *val, int left)
1180 {
1181         if (left)
1182                 return false_comparison_range_sval(var, comparison, val);
1183         else
1184                 return false_comparison_range_sval(val, comparison, var);
1185 }
1186 
1187 int possibly_true(struct expression *left, int comparison, struct expression *right)
1188 {
1189         struct range_list *rl_left, *rl_right;
1190         struct data_range *tmp_left, *tmp_right;
1191         struct symbol *type;
1192 
1193         if (!get_implied_rl(left, &rl_left))
1194                 return 1;
1195         if (!get_implied_rl(right, &rl_right))
1196                 return 1;
1197 
1198         type = rl_type(rl_left);
1199         if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1200                 type = rl_type(rl_right);
1201         if (type_positive_bits(type) < 31)
1202                 type = &int_ctype;
1203 
1204         rl_left = cast_rl(type, rl_left);
1205         rl_right = cast_rl(type, rl_right);
1206 
1207         FOR_EACH_PTR(rl_left, tmp_left) {
1208                 FOR_EACH_PTR(rl_right, tmp_right) {
1209                         if (true_comparison_range(tmp_left, comparison, tmp_right))
1210                                 return 1;
1211                 } END_FOR_EACH_PTR(tmp_right);
1212         } END_FOR_EACH_PTR(tmp_left);
1213         return 0;
1214 }
1215 
1216 int possibly_false(struct expression *left, int comparison, struct expression *right)
1217 {
1218         struct range_list *rl_left, *rl_right;
1219         struct data_range *tmp_left, *tmp_right;
1220         struct symbol *type;
1221 
1222         if (!get_implied_rl(left, &rl_left))
1223                 return 1;
1224         if (!get_implied_rl(right, &rl_right))
1225                 return 1;
1226 
1227         type = rl_type(rl_left);
1228         if (type_positive_bits(type) < type_positive_bits(rl_type(rl_right)))
1229                 type = rl_type(rl_right);
1230         if (type_positive_bits(type) < 31)
1231                 type = &int_ctype;
1232 
1233         rl_left = cast_rl(type, rl_left);
1234         rl_right = cast_rl(type, rl_right);
1235 
1236         FOR_EACH_PTR(rl_left, tmp_left) {
1237                 FOR_EACH_PTR(rl_right, tmp_right) {
1238                         if (false_comparison_range_sval(tmp_left, comparison, tmp_right))
1239                                 return 1;
1240                 } END_FOR_EACH_PTR(tmp_right);
1241         } END_FOR_EACH_PTR(tmp_left);
1242         return 0;
1243 }
1244 
1245 int possibly_true_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1246 {
1247         struct data_range *left_tmp, *right_tmp;
1248         struct symbol *type;
1249 
1250         if (!left_ranges || !right_ranges)
1251                 return 1;
1252 
1253         type = rl_type(left_ranges);
1254         if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1255                 type = rl_type(right_ranges);
1256         if (type_positive_bits(type) < 31)
1257                 type = &int_ctype;
1258 
1259         left_ranges = cast_rl(type, left_ranges);
1260         right_ranges = cast_rl(type, right_ranges);
1261 
1262         FOR_EACH_PTR(left_ranges, left_tmp) {
1263                 FOR_EACH_PTR(right_ranges, right_tmp) {
1264                         if (true_comparison_range(left_tmp, comparison, right_tmp))
1265                                 return 1;
1266                 } END_FOR_EACH_PTR(right_tmp);
1267         } END_FOR_EACH_PTR(left_tmp);
1268         return 0;
1269 }
1270 
1271 int possibly_false_rl(struct range_list *left_ranges, int comparison, struct range_list *right_ranges)
1272 {
1273         struct data_range *left_tmp, *right_tmp;
1274         struct symbol *type;
1275 
1276         if (!left_ranges || !right_ranges)
1277                 return 1;
1278 
1279         type = rl_type(left_ranges);
1280         if (type_positive_bits(type) < type_positive_bits(rl_type(right_ranges)))
1281                 type = rl_type(right_ranges);
1282         if (type_positive_bits(type) < 31)
1283                 type = &int_ctype;
1284 
1285         left_ranges = cast_rl(type, left_ranges);
1286         right_ranges = cast_rl(type, right_ranges);
1287 
1288         FOR_EACH_PTR(left_ranges, left_tmp) {
1289                 FOR_EACH_PTR(right_ranges, right_tmp) {
1290                         if (false_comparison_range_sval(left_tmp, comparison, right_tmp))
1291                                 return 1;
1292                 } END_FOR_EACH_PTR(right_tmp);
1293         } END_FOR_EACH_PTR(left_tmp);
1294         return 0;
1295 }
1296 
1297 /* FIXME: the _rl here stands for right left so really it should be _lr */
1298 int possibly_true_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1299 {
1300         if (left)
1301                 return possibly_true_rl(a, comparison, b);
1302         else
1303                 return possibly_true_rl(b, comparison, a);
1304 }
1305 
1306 int possibly_false_rl_LR(int comparison, struct range_list *a, struct range_list *b, int left)
1307 {
1308         if (left)
1309                 return possibly_false_rl(a, comparison, b);
1310         else
1311                 return possibly_false_rl(b, comparison, a);
1312 }
1313 
1314 int rl_has_sval(struct range_list *rl, sval_t sval)
1315 {
1316         struct data_range *tmp;
1317 
1318         FOR_EACH_PTR(rl, tmp) {
1319                 if (sval_cmp(tmp->min, sval) <= 0 &&
1320                     sval_cmp(tmp->max, sval) >= 0)
1321                         return 1;
1322         } END_FOR_EACH_PTR(tmp);
1323         return 0;
1324 }
1325 
1326 void tack_on(struct range_list **list, struct data_range *drange)
1327 {
1328         add_ptr_list(list, drange);
1329 }
1330 
1331 void push_rl(struct range_list_stack **rl_stack, struct range_list *rl)
1332 {
1333         add_ptr_list(rl_stack, rl);
1334 }
1335 
1336 struct range_list *pop_rl(struct range_list_stack **rl_stack)
1337 {
1338         struct range_list *rl;
1339 
1340         rl = last_ptr_list((struct ptr_list *)*rl_stack);
1341         delete_ptr_list_last((struct ptr_list **)rl_stack);
1342         return rl;
1343 }
1344 
1345 struct range_list *top_rl(struct range_list_stack *rl_stack)
1346 {
1347         struct range_list *rl;
1348 
1349         rl = last_ptr_list((struct ptr_list *)rl_stack);
1350         return rl;
1351 }
1352 
1353 void filter_top_rl(struct range_list_stack **rl_stack, struct range_list *filter)
1354 {
1355         struct range_list *rl;
1356 
1357         rl = pop_rl(rl_stack);
1358         rl = rl_filter(rl, filter);
1359         push_rl(rl_stack, rl);
1360 }
1361 
1362 struct range_list *rl_truncate_cast(struct symbol *type, struct range_list *rl)
1363 {
1364         struct data_range *tmp;
1365         struct range_list *ret = NULL;
1366         sval_t min, max;
1367 
1368         if (!rl)
1369                 return NULL;
1370 
1371         if (!type || type == rl_type(rl))
1372                 return rl;
1373 
1374         FOR_EACH_PTR(rl, tmp) {
1375                 min = tmp->min;
1376                 max = tmp->max;
1377                 if (type_bits(type) < type_bits(rl_type(rl))) {
1378                         min.uvalue = tmp->min.uvalue & ((1ULL << type_bits(type)) - 1);
1379                         max.uvalue = tmp->max.uvalue & ((1ULL << type_bits(type)) - 1);
1380                 }
1381                 if (sval_cmp(min, max) > 0) {
1382                         min = sval_cast(type, min);
1383                         max = sval_cast(type, max);
1384                 }
1385                 add_range_t(type, &ret, min, max);
1386         } END_FOR_EACH_PTR(tmp);
1387 
1388         return ret;
1389 }
1390 
1391 int rl_fits_in_type(struct range_list *rl, struct symbol *type)
1392 {
1393         if (type_bits(rl_type(rl)) <= type_bits(type))
1394                 return 1;
1395         if (sval_cmp(rl_max(rl), sval_type_max(type)) > 0)
1396                 return 0;
1397         if (sval_is_negative(rl_min(rl)) &&
1398             sval_cmp(rl_min(rl), sval_type_min(type)) < 0)
1399                 return 0;
1400         return 1;
1401 }
1402 
1403 static int rl_type_consistent(struct range_list *rl)
1404 {
1405         struct data_range *tmp;
1406         struct symbol *type;
1407 
1408         type = rl_type(rl);
1409         FOR_EACH_PTR(rl, tmp) {
1410                 if (type != tmp->min.type || type != tmp->max.type)
1411                         return 0;
1412         } END_FOR_EACH_PTR(tmp);
1413         return 1;
1414 }
1415 
1416 static struct range_list *cast_to_bool(struct range_list *rl)
1417 {
1418         struct data_range *tmp;
1419         struct range_list *ret = NULL;
1420         int has_one = 0;
1421         int has_zero = 0;
1422         sval_t min = { .type = &bool_ctype };
1423         sval_t max = { .type = &bool_ctype };
1424 
1425         FOR_EACH_PTR(rl, tmp) {
1426                 if (tmp->min.value || tmp->max.value)
1427                         has_one = 1;
1428                 if (sval_is_negative(tmp->min) &&
1429                     sval_is_negative(tmp->max))
1430                         continue;
1431                 if (tmp->min.value == 0 ||
1432                     tmp->max.value == 0)
1433                         has_zero = 1;
1434                 if (sval_is_negative(tmp->min) &&
1435                     tmp->max.value > 0)
1436                         has_zero = 1;
1437         } END_FOR_EACH_PTR(tmp);
1438 
1439         if (!has_zero)
1440                 min.value = 1;
1441         if (has_one)
1442                 max.value = 1;
1443 
1444         add_range(&ret, min, max);
1445         return ret;
1446 }
1447 
1448 struct range_list *cast_rl(struct symbol *type, struct range_list *rl)
1449 {
1450         struct data_range *tmp;
1451         struct range_list *ret = NULL;
1452 
1453         if (!rl)
1454                 return NULL;
1455 
1456         if (!type)
1457                 return rl;
1458         if (!rl_is_sane(rl))
1459                 return alloc_whole_rl(type);
1460         if (type == rl_type(rl) && rl_type_consistent(rl))
1461                 return rl;
1462 
1463         if (type == &bool_ctype)
1464                 return cast_to_bool(rl);
1465 
1466         FOR_EACH_PTR(rl, tmp) {
1467                 add_range_t(type, &ret, tmp->min, tmp->max);
1468         } END_FOR_EACH_PTR(tmp);
1469 
1470         if (!ret)
1471                 return alloc_whole_rl(type);
1472 
1473         return ret;
1474 }
1475 
1476 struct range_list *rl_filter(struct range_list *rl, struct range_list *filter)
1477 {
1478         struct data_range *tmp;
1479 
1480         FOR_EACH_PTR(filter, tmp) {
1481                 rl = remove_range(rl, tmp->min, tmp->max);
1482         } END_FOR_EACH_PTR(tmp);
1483 
1484         return rl;
1485 }
1486 
1487 struct range_list *do_intersection(struct range_list *one_rl, struct range_list *two_rl)
1488 {
1489         struct data_range *one, *two;
1490         struct range_list *ret = NULL;
1491 
1492 
1493         PREPARE_PTR_LIST(one_rl, one);
1494         PREPARE_PTR_LIST(two_rl, two);
1495 
1496         while (true) {
1497                 if (!one || !two)
1498                         break;
1499                 if (sval_cmp(one->max, two->min) < 0) {
1500                         NEXT_PTR_LIST(one);
1501                         continue;
1502                 }
1503                 if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) <= 0) {
1504                         add_range(&ret, two->min, one->max);
1505                         NEXT_PTR_LIST(one);
1506                         continue;
1507                 }
1508                 if (sval_cmp(one->min, two->min) >= 0 && sval_cmp(one->max, two->max) <= 0) {
1509                         add_range(&ret, one->min, one->max);
1510                         NEXT_PTR_LIST(one);
1511                         continue;
1512                 }
1513                 if (sval_cmp(one->min, two->min) < 0 && sval_cmp(one->max, two->max) > 0) {
1514                         add_range(&ret, two->min, two->max);
1515                         NEXT_PTR_LIST(two);
1516                         continue;
1517                 }
1518                 if (sval_cmp(one->min, two->max) <= 0 && sval_cmp(one->max, two->max) > 0) {
1519                         add_range(&ret, one->min, two->max);
1520                         NEXT_PTR_LIST(two);
1521                         continue;
1522                 }
1523                 if (sval_cmp(one->min, two->max) <= 0) {
1524                         sm_fatal("error calculating intersection of '%s' and '%s'", show_rl(one_rl), show_rl(two_rl));
1525                         return NULL;
1526                 }
1527                 NEXT_PTR_LIST(two);
1528         }
1529 
1530         FINISH_PTR_LIST(two);
1531         FINISH_PTR_LIST(one);
1532 
1533         return ret;
1534 }
1535 
1536 struct range_list *rl_intersection(struct range_list *one, struct range_list *two)
1537 {
1538         struct range_list *ret;
1539         struct symbol *ret_type;
1540         struct symbol *small_type;
1541         struct symbol *large_type;
1542 
1543         if (!one || !two)
1544                 return NULL;
1545 
1546         ret_type = rl_type(one);
1547         small_type = rl_type(one);
1548         large_type = rl_type(two);
1549 
1550         if (type_bits(rl_type(two)) < type_bits(small_type)) {
1551                 small_type = rl_type(two);
1552                 large_type = rl_type(one);
1553         }
1554 
1555         one = cast_rl(large_type, one);
1556         two = cast_rl(large_type, two);
1557 
1558         ret = do_intersection(one, two);
1559         return cast_rl(ret_type, ret);
1560 }
1561 
1562 static struct range_list *handle_mod_rl(struct range_list *left, struct range_list *right)
1563 {
1564         sval_t zero;
1565         sval_t max;
1566 
1567         max = rl_max(right);
1568         if (sval_is_max(max))
1569                 return left;
1570         if (max.value == 0)
1571                 return NULL;
1572         max.value--;
1573         if (sval_is_negative(max))
1574                 return NULL;
1575         if (sval_cmp(rl_max(left), max) < 0)
1576                 return left;
1577         zero = max;
1578         zero.value = 0;
1579         return alloc_rl(zero, max);
1580 }
1581 
1582 static struct range_list *get_neg_rl(struct range_list *rl)
1583 {
1584         struct data_range *tmp;
1585         struct data_range *new;
1586         struct range_list *ret = NULL;
1587 
1588         if (!rl)
1589                 return NULL;
1590         if (sval_is_positive(rl_min(rl)))
1591                 return NULL;
1592 
1593         FOR_EACH_PTR(rl, tmp) {
1594                 if (sval_is_positive(tmp->min))
1595                         break;
1596                 if (sval_is_positive(tmp->max)) {
1597                         new = alloc_range(tmp->min, tmp->max);
1598                         new->max.value = -1;
1599                         add_range(&ret, new->min, new->max);
1600                         break;
1601                 }
1602                 add_range(&ret, tmp->min, tmp->max);
1603         } END_FOR_EACH_PTR(tmp);
1604 
1605         return ret;
1606 }
1607 
1608 static struct range_list *get_pos_rl(struct range_list *rl)
1609 {
1610         struct data_range *tmp;
1611         struct data_range *new;
1612         struct range_list *ret = NULL;
1613 
1614         if (!rl)
1615                 return NULL;
1616         if (sval_is_negative(rl_max(rl)))
1617                 return NULL;
1618 
1619         FOR_EACH_PTR(rl, tmp) {
1620                 if (sval_is_negative(tmp->max))
1621                         continue;
1622                 if (sval_is_positive(tmp->min)) {
1623                         add_range(&ret, tmp->min, tmp->max);
1624                         continue;
1625                 }
1626                 new = alloc_range(tmp->min, tmp->max);
1627                 new->min.value = 0;
1628                 add_range(&ret, new->min, new->max);
1629         } END_FOR_EACH_PTR(tmp);
1630 
1631         return ret;
1632 }
1633 
1634 static struct range_list *divide_rl_helper(struct range_list *left, struct range_list *right)
1635 {
1636         sval_t right_min, right_max;
1637         sval_t min, max;
1638 
1639         if (!left || !right)
1640                 return NULL;
1641 
1642         /* let's assume we never divide by zero */
1643         right_min = rl_min(right);
1644         right_max = rl_max(right);
1645         if (right_min.value == 0 && right_max.value == 0)
1646                 return NULL;
1647         if (right_min.value == 0)
1648                 right_min.value = 1;
1649         if (right_max.value == 0)
1650                 right_max.value = -1;
1651 
1652         max = sval_binop(rl_max(left), '/', right_min);
1653         min = sval_binop(rl_min(left), '/', right_max);
1654 
1655         return alloc_rl(min, max);
1656 }
1657 
1658 static struct range_list *handle_divide_rl(struct range_list *left, struct range_list *right)
1659 {
1660         struct range_list *left_neg, *left_pos, *right_neg, *right_pos;
1661         struct range_list *neg_neg, *neg_pos, *pos_neg, *pos_pos;
1662         struct range_list *ret;
1663 
1664         if (is_whole_rl(right))
1665                 return NULL;
1666 
1667         left_neg = get_neg_rl(left);
1668         left_pos = get_pos_rl(left);
1669         right_neg = get_neg_rl(right);
1670         right_pos = get_pos_rl(right);
1671 
1672         neg_neg = divide_rl_helper(left_neg, right_neg);
1673         neg_pos = divide_rl_helper(left_neg, right_pos);
1674         pos_neg = divide_rl_helper(left_pos, right_neg);
1675         pos_pos = divide_rl_helper(left_pos, right_pos);
1676 
1677         ret = rl_union(neg_neg, neg_pos);
1678         ret = rl_union(ret, pos_neg);
1679         return rl_union(ret, pos_pos);
1680 }
1681 
1682 static struct range_list *ptr_add_mult(struct range_list *left, int op, struct range_list *right)
1683 {
1684         struct range_list *ret;
1685         sval_t l_sval, r_sval, res;
1686 
1687         /*
1688          * This function is sort of the wrong API because it takes two pointer
1689          * and adds them together.  The caller is expected to figure out
1690          * alignment.  Neither of those are the correct things to do.
1691          *
1692          * Really this function is quite bogus...
1693          */
1694 
1695         if (rl_to_sval(left, &l_sval) && rl_to_sval(right, &r_sval)) {
1696                 res = sval_binop(l_sval, op, r_sval);
1697                 return alloc_rl(res, res);
1698         }
1699 
1700         if (rl_min(left).value != 0 || rl_max(right).value != 0) {
1701                 ret = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1702                 return cast_rl(rl_type(left), ret);
1703         }
1704 
1705         return alloc_whole_rl(rl_type(left));
1706 }
1707 
1708 static struct range_list *handle_add_mult_rl(struct range_list *left, int op, struct range_list *right)
1709 {
1710         sval_t min, max;
1711 
1712         if (type_is_ptr(rl_type(left)) || type_is_ptr(rl_type(right)))
1713                 return ptr_add_mult(left, op, right);
1714 
1715         if (sval_binop_overflows(rl_min(left), op, rl_min(right)))
1716                 return NULL;
1717         min = sval_binop(rl_min(left), op, rl_min(right));
1718 
1719         if (sval_binop_overflows(rl_max(left), op, rl_max(right)))
1720                 return NULL;
1721         max = sval_binop(rl_max(left), op, rl_max(right));
1722 
1723         return alloc_rl(min, max);
1724 }
1725 
1726 static struct range_list *handle_sub_rl(struct range_list *left_orig, struct range_list *right_orig)
1727 {
1728         struct range_list *left_rl, *right_rl;
1729         struct symbol *type;
1730         sval_t min, max;
1731         sval_t min_ll, max_ll, res_ll;
1732         sval_t tmp;
1733 
1734         /* TODO:  These things should totally be using dranges where possible */
1735 
1736         if (!left_orig || !right_orig)
1737                 return NULL;
1738 
1739         type = &int_ctype;
1740         if (type_positive_bits(rl_type(left_orig)) > type_positive_bits(type))
1741                 type = rl_type(left_orig);
1742         if (type_positive_bits(rl_type(right_orig)) > type_positive_bits(type))
1743                 type = rl_type(right_orig);
1744 
1745         left_rl = cast_rl(type, left_orig);
1746         right_rl = cast_rl(type, right_orig);
1747 
1748         max = rl_max(left_rl);
1749         min = sval_type_min(type);
1750 
1751         min_ll = rl_min(left_rl);
1752         min_ll.type = &llong_ctype;
1753         max_ll = rl_max(right_rl);
1754         max_ll.type = &llong_ctype;
1755         res_ll = min_ll;
1756         res_ll.value = min_ll.value - max_ll.value;
1757 
1758         if (!sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
1759                 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
1760                 if (sval_cmp(tmp, min) > 0)
1761                         min = tmp;
1762         } else if (type_positive_bits(type) < 63 &&
1763                    !sval_binop_overflows(min_ll, '-', max_ll) &&
1764                    (min.value != 0 && sval_cmp(res_ll, min) >= 0)) {
1765                 struct range_list *left_casted, *right_casted, *result;
1766 
1767                 left_casted = cast_rl(&llong_ctype, left_orig);
1768                 right_casted = cast_rl(&llong_ctype, right_orig);
1769                 result = handle_sub_rl(left_casted, right_casted);
1770                 return cast_rl(type, result);
1771         }
1772 
1773         if (!sval_is_max(rl_max(left_rl))) {
1774                 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
1775                 if (sval_cmp(tmp, max) < 0)
1776                         max = tmp;
1777         }
1778 
1779         if (sval_is_min(min) && sval_is_max(max))
1780                 return NULL;
1781 
1782         return alloc_rl(min, max);
1783 }
1784 
1785 static unsigned long long rl_bits_always_set(struct range_list *rl)
1786 {
1787         return sval_fls_mask(rl_min(rl));
1788 }
1789 
1790 static unsigned long long rl_bits_maybe_set(struct range_list *rl)
1791 {
1792         return sval_fls_mask(rl_max(rl));
1793 }
1794 
1795 static struct range_list *handle_OR_rl(struct range_list *left, struct range_list *right)
1796 {
1797         unsigned long long left_min, left_max, right_min, right_max;
1798         sval_t min, max;
1799         sval_t sval;
1800 
1801         if ((rl_to_sval(left, &sval) || rl_to_sval(right, &sval)) &&
1802             !sval_binop_overflows(rl_max(left), '+', rl_max(right)))
1803                 return rl_binop(left, '+', right);
1804 
1805         left_min = rl_bits_always_set(left);
1806         left_max = rl_bits_maybe_set(left);
1807         right_min = rl_bits_always_set(right);
1808         right_max = rl_bits_maybe_set(right);
1809 
1810         min.type = max.type = &ullong_ctype;
1811         min.uvalue = left_min | right_min;
1812         max.uvalue = left_max | right_max;
1813 
1814         return cast_rl(rl_type(left), alloc_rl(min, max));
1815 }
1816 
1817 static struct range_list *handle_XOR_rl(struct range_list *left, struct range_list *right)
1818 {
1819         unsigned long long left_set, left_maybe;
1820         unsigned long long right_set, right_maybe;
1821         sval_t zero, max;
1822 
1823         left_set = rl_bits_always_set(left);
1824         left_maybe = rl_bits_maybe_set(left);
1825 
1826         right_set = rl_bits_always_set(right);
1827         right_maybe = rl_bits_maybe_set(right);
1828 
1829         zero = max = rl_min(left);
1830         zero.uvalue = 0;
1831         max.uvalue = fls_mask((left_maybe | right_maybe) ^ (left_set & right_set));
1832 
1833         return cast_rl(rl_type(left), alloc_rl(zero, max));
1834 }
1835 
1836 static sval_t sval_lowest_set_bit(sval_t sval)
1837 {
1838         sval_t ret = { .type = sval.type };
1839         int i;
1840 
1841         for (i = 0; i < 64; i++) {
1842                 if (sval.uvalue & 1ULL << i) {
1843                         ret.uvalue = (1ULL << i);
1844                         return ret;
1845                 }
1846         }
1847         return ret;
1848 }
1849 
1850 static struct range_list *handle_AND_rl_sval(struct range_list *rl, sval_t sval)
1851 {
1852         struct range_list *known_rl;
1853         sval_t zero = { 0 };
1854         sval_t min;
1855 
1856         zero.type = sval.type;
1857         zero.value = 0;
1858 
1859         if (sm_fls64(rl_max(rl).uvalue) < find_first_zero_bit(sval.uvalue) &&
1860             sm_fls64(rl_min(rl).uvalue) < find_first_zero_bit(sval.uvalue))
1861                 return rl;
1862 
1863         min = sval_lowest_set_bit(sval);
1864 
1865         if (min.value != 0) {
1866                 sval_t max, mod;
1867 
1868                 max = rl_max(rl);
1869                 mod = sval_binop(max, '%', min);
1870                 if (mod.value) {
1871                         max = sval_binop(max, '-', mod);
1872                         max.value++;
1873                         if (max.value > 0 && sval_cmp(max, rl_max(rl)) < 0)
1874                                 rl = remove_range(rl, max, rl_max(rl));
1875                 }
1876         }
1877 
1878         known_rl = alloc_rl(min, sval);
1879 
1880         rl = rl_intersection(rl, known_rl);
1881         zero = rl_min(rl);
1882         zero.value = 0;
1883         add_range(&rl, zero, zero);
1884 
1885         return rl;
1886 }
1887 
1888 static struct range_list *fudge_AND_rl(struct range_list *rl)
1889 {
1890         struct range_list *ret;
1891         sval_t min;
1892 
1893         min = sval_lowest_set_bit(rl_min(rl));
1894         ret = clone_rl(rl);
1895         add_range(&ret, min, rl_min(rl));
1896 
1897         return ret;
1898 }
1899 
1900 static struct range_list *handle_AND_rl(struct range_list *left, struct range_list *right)
1901 {
1902         sval_t sval, zero;
1903         struct range_list *rl;
1904 
1905         if (rl_to_sval(left, &sval))
1906                 return handle_AND_rl_sval(right, sval);
1907         if (rl_to_sval(right, &sval))
1908                 return handle_AND_rl_sval(left, sval);
1909 
1910         left = fudge_AND_rl(left);
1911         right = fudge_AND_rl(right);
1912 
1913         rl = rl_intersection(left, right);
1914         zero = rl_min(rl);
1915         zero.value = 0;
1916         add_range(&rl, zero, zero);
1917 
1918         return rl;
1919 }
1920 
1921 static struct range_list *handle_lshift(struct range_list *left_orig, struct range_list *right_orig)
1922 {
1923         struct range_list *left;
1924         struct data_range *tmp;
1925         struct range_list *ret = NULL;
1926         sval_t zero = { .type = rl_type(left_orig), };
1927         sval_t shift, min, max;
1928         bool add_zero = false;
1929 
1930         if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1931                 return NULL;
1932         if (shift.value == 0)
1933                 return left_orig;
1934 
1935         /* Cast to unsigned for easier left shift math */
1936         if (type_positive_bits(rl_type(left_orig)) < 32)
1937                 left = cast_rl(&uint_ctype, left_orig);
1938         else if(type_positive_bits(rl_type(left_orig)) == 63)
1939                 left = cast_rl(&ullong_ctype, left_orig);
1940         else
1941                 left = left_orig;
1942 
1943         FOR_EACH_PTR(left, tmp) {
1944                 min = tmp->min;
1945                 max = tmp->max;
1946 
1947                 if (min.value == 0 || max.value > sval_type_max(max.type).uvalue >> shift.uvalue)
1948                         add_zero = true;
1949                 if (min.value == 0 && max.value == 0)
1950                         continue;
1951                 if (min.value == 0)
1952                         min.value = 1;
1953                 min = sval_binop(min, SPECIAL_LEFTSHIFT, shift);
1954                 max = sval_binop(max, SPECIAL_LEFTSHIFT, shift);
1955                 add_range(&ret, min, max);
1956         } END_FOR_EACH_PTR(tmp);
1957 
1958         if (!rl_fits_in_type(ret, rl_type(left_orig)))
1959                 add_zero = true;
1960         ret = cast_rl(rl_type(left_orig), ret);
1961         if (add_zero)
1962                 add_range(&ret, zero, zero);
1963 
1964         return ret;
1965 }
1966 
1967 static struct range_list *handle_rshift(struct range_list *left_orig, struct range_list *right_orig)
1968 {
1969         struct data_range *tmp;
1970         struct range_list *ret = NULL;
1971         sval_t shift, min, max;
1972 
1973         if (!rl_to_sval(right_orig, &shift) || sval_is_negative(shift))
1974                 return NULL;
1975         if (shift.value == 0)
1976                 return left_orig;
1977 
1978         FOR_EACH_PTR(left_orig, tmp) {
1979                 min = sval_binop(tmp->min, SPECIAL_RIGHTSHIFT, shift);
1980                 max = sval_binop(tmp->max, SPECIAL_RIGHTSHIFT, shift);
1981                 add_range(&ret, min, max);
1982         } END_FOR_EACH_PTR(tmp);
1983 
1984         return ret;
1985 }
1986 
1987 struct range_list *rl_binop(struct range_list *left, int op, struct range_list *right)
1988 {
1989         struct symbol *cast_type;
1990         sval_t left_sval, right_sval;
1991         struct range_list *ret = NULL;
1992 
1993         cast_type = rl_type(left);
1994         if (sval_type_max(rl_type(left)).uvalue < sval_type_max(rl_type(right)).uvalue)
1995                 cast_type = rl_type(right);
1996         if (sval_type_max(cast_type).uvalue < INT_MAX)
1997                 cast_type = &int_ctype;
1998 
1999         left = cast_rl(cast_type, left);
2000         right = cast_rl(cast_type, right);
2001 
2002         if (!left && !right)
2003                 return NULL;
2004 
2005         if (rl_to_sval(left, &left_sval) && rl_to_sval(right, &right_sval)) {
2006                 sval_t val = sval_binop(left_sval, op, right_sval);
2007                 return alloc_rl(val, val);
2008         }
2009 
2010         switch (op) {
2011         case '%':
2012                 ret = handle_mod_rl(left, right);
2013                 break;
2014         case '/':
2015                 ret = handle_divide_rl(left, right);
2016                 break;
2017         case '*':
2018         case '+':
2019                 ret = handle_add_mult_rl(left, op, right);
2020                 break;
2021         case '|':
2022                 ret = handle_OR_rl(left, right);
2023                 break;
2024         case '^':
2025                 ret = handle_XOR_rl(left, right);
2026                 break;
2027         case '&':
2028                 ret = handle_AND_rl(left, right);
2029                 break;
2030         case '-':
2031                 ret = handle_sub_rl(left, right);
2032                 break;
2033         case SPECIAL_RIGHTSHIFT:
2034                 return handle_rshift(left, right);
2035         case SPECIAL_LEFTSHIFT:
2036                 return handle_lshift(left, right);
2037         }
2038 
2039         return ret;
2040 }
2041 
2042 void free_data_info_allocs(void)
2043 {
2044         struct allocator_struct *desc = &data_info_allocator;
2045         struct allocation_blob *blob = desc->blobs;
2046 
2047         free_all_rl();
2048         clear_math_cache();
2049 
2050         desc->blobs = NULL;
2051         desc->allocations = 0;
2052         desc->total_bytes = 0;
2053         desc->useful_bytes = 0;
2054         desc->freelist = NULL;
2055         while (blob) {
2056                 struct allocation_blob *next = blob->next;
2057                 blob_free(blob, desc->chunking);
2058                 blob = next;
2059         }
2060         clear_data_range_alloc();
2061 }
2062 
2063 void split_comparison_rl(struct range_list *left_orig, int op, struct range_list *right_orig,
2064                 struct range_list **left_true_rl, struct range_list **left_false_rl,
2065                 struct range_list **right_true_rl, struct range_list **right_false_rl)
2066 {
2067         struct range_list *left_true, *left_false;
2068         struct range_list *right_true, *right_false;
2069         sval_t min, max;
2070 
2071         min = sval_type_min(rl_type(left_orig));
2072         max = sval_type_max(rl_type(left_orig));
2073 
2074         left_true = clone_rl(left_orig);
2075         left_false = clone_rl(left_orig);
2076         right_true = clone_rl(right_orig);
2077         right_false = clone_rl(right_orig);
2078 
2079         switch (op) {
2080         case '<':
2081         case SPECIAL_UNSIGNED_LT:
2082                 left_true = remove_range(left_orig, rl_max(right_orig), max);
2083                 if (!sval_is_min(rl_min(right_orig))) {
2084                         left_false = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2085                 }
2086 
2087                 right_true = remove_range(right_orig, min, rl_min(left_orig));
2088                 if (!sval_is_max(rl_max(left_orig)))
2089                         right_false = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2090                 break;
2091         case SPECIAL_UNSIGNED_LTE:
2092         case SPECIAL_LTE:
2093                 if (!sval_is_max(rl_max(right_orig)))
2094                         left_true = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2095                 left_false = remove_range(left_orig, min, rl_min(right_orig));
2096 
2097                 if (!sval_is_min(rl_min(left_orig)))
2098                         right_true = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2099                 right_false = remove_range(right_orig, rl_max(left_orig), max);
2100 
2101                 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2102                         left_false = remove_range(left_false, rl_min(left_orig), rl_min(left_orig));
2103                 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2104                         right_false = remove_range(right_false, rl_max(left_orig), rl_max(left_orig));
2105                 break;
2106         case SPECIAL_EQUAL:
2107                 left_true = rl_intersection(left_orig, right_orig);
2108                 right_true = clone_rl(left_true);
2109 
2110                 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2111                         left_false = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2112                 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2113                         right_false = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2114                 break;
2115         case SPECIAL_UNSIGNED_GTE:
2116         case SPECIAL_GTE:
2117                 if (!sval_is_min(rl_min(right_orig)))
2118                         left_true = remove_range(left_orig, min, sub_one(rl_min(right_orig)));
2119                 left_false = remove_range(left_orig, rl_max(right_orig), max);
2120 
2121                 if (!sval_is_max(rl_max(left_orig)))
2122                         right_true = remove_range(right_orig, add_one(rl_max(left_orig)), max);
2123                 right_false = remove_range(right_orig, min, rl_min(left_orig));
2124 
2125                 if (sval_cmp(rl_min(left_orig), rl_min(right_orig)) == 0)
2126                         right_false = remove_range(right_false, rl_min(left_orig), rl_min(left_orig));
2127                 if (sval_cmp(rl_max(left_orig), rl_max(right_orig)) == 0)
2128                         left_false = remove_range(left_false, rl_max(left_orig), rl_max(left_orig));
2129                 break;
2130         case '>':
2131         case SPECIAL_UNSIGNED_GT:
2132                 left_true = remove_range(left_orig, min, rl_min(right_orig));
2133                 if (!sval_is_max(rl_max(right_orig)))
2134                         left_false = remove_range(left_orig, add_one(rl_max(right_orig)), max);
2135 
2136                 right_true = remove_range(right_orig, rl_max(left_orig), max);
2137                 if (!sval_is_min(rl_min(left_orig)))
2138                         right_false = remove_range(right_orig, min, sub_one(rl_min(left_orig)));
2139                 break;
2140         case SPECIAL_NOTEQUAL:
2141                 left_false = rl_intersection(left_orig, right_orig);
2142                 right_false = clone_rl(left_false);
2143 
2144                 if (sval_cmp(rl_min(right_orig), rl_max(right_orig)) == 0)
2145                         left_true = remove_range(left_orig, rl_min(right_orig), rl_min(right_orig));
2146                 if (sval_cmp(rl_min(left_orig), rl_max(left_orig)) == 0)
2147                         right_true = remove_range(right_orig, rl_min(left_orig), rl_min(left_orig));
2148                 break;
2149         default:
2150                 sm_perror(" unhandled comparison %d", op);
2151                 return;
2152         }
2153 
2154         if (left_true_rl) {
2155                 *left_true_rl = left_true;
2156                 *left_false_rl = left_false;
2157         }
2158         if (right_true_rl) {
2159                 *right_true_rl = right_true;
2160                 *right_false_rl = right_false;
2161         }
2162 }