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