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 } 2163