1 /* 2 * Copyright (C) 2012 Oracle. 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 /* 19 * Basically the point of sval is that it can hold both ULLONG_MAX and 20 * LLONG_MIN. If it is an unsigned type then we use sval.uvalue or if it is 21 * signed we use sval.value. 22 * 23 * I considered just using one bit to store whether the value was signed vs 24 * unsigned but I think it might help to have the type information so we know 25 * how to do type promotion. 26 * 27 */ 28 29 #include "smatch.h" 30 #include "smatch_slist.h" 31 #include "smatch_extra.h" 32 33 __ALLOCATOR(sval_t, "svals", sval); 34 35 sval_t *sval_alloc(sval_t sval) 36 { 37 sval_t *ret; 38 39 ret = __alloc_sval(0); 40 *ret = sval; 41 return ret; 42 } 43 44 sval_t *sval_alloc_permanent(sval_t sval) 45 { 46 sval_t *ret; 47 48 ret = malloc(sizeof(*ret)); 49 *ret = sval; 50 return ret; 51 } 52 53 sval_t sval_blank(struct expression *expr) 54 { 55 sval_t ret; 56 57 ret.type = get_type(expr); 58 if (!ret.type) 59 ret.type = &int_ctype; 60 ret.value = 123456789; 61 62 return ret; 63 } 64 65 sval_t sval_type_val(struct symbol *type, long long val) 66 { 67 sval_t ret; 68 69 if (!type) 70 type = &llong_ctype; 71 72 ret.type = type; 73 ret.value = val; 74 return ret; 75 } 76 77 sval_t sval_from_val(struct expression *expr, long long val) 78 { 79 sval_t ret; 80 81 ret = sval_blank(expr); 82 ret.value = val; 83 ret = sval_cast(get_type(expr), ret); 84 85 return ret; 86 } 87 88 int sval_is_ptr(sval_t sval) 89 { 90 if (!sval.type) 91 return 0; 92 return (sval.type->type == SYM_PTR || sval.type->type == SYM_ARRAY); 93 } 94 95 int sval_unsigned(sval_t sval) 96 { 97 if (is_ptr_type(sval.type)) 98 return true; 99 return type_unsigned(sval.type); 100 } 101 102 int sval_signed(sval_t sval) 103 { 104 return !type_unsigned(sval.type); 105 } 106 107 int sval_bits(sval_t sval) 108 { 109 return type_bits(sval.type); 110 } 111 112 int sval_bits_used(sval_t sval) 113 { 114 int i; 115 116 for (i = 64; i >= 1; i--) { 117 if (sval.uvalue & (1ULL << (i - 1))) 118 return i; 119 } 120 return 0; 121 } 122 123 int sval_is_negative(sval_t sval) 124 { 125 if (type_unsigned(sval.type)) 126 return 0; 127 if (sval.value < 0) 128 return 1; 129 return 0; 130 } 131 132 int sval_is_positive(sval_t sval) 133 { 134 return !sval_is_negative(sval); 135 } 136 137 int sval_is_min(sval_t sval) 138 { 139 sval_t min = sval_type_min(sval.type); 140 141 if (sval_unsigned(sval)) { 142 if (sval.uvalue == 0) 143 return 1; 144 return 0; 145 } 146 /* return true for less than min as well */ 147 return (sval.value <= min.value); 148 } 149 150 int sval_is_max(sval_t sval) 151 { 152 sval_t max = sval_type_max(sval.type); 153 154 if (sval_unsigned(sval)) 155 return (sval.uvalue >= max.value); 156 return (sval.value >= max.value); 157 } 158 159 int sval_is_a_min(sval_t sval) 160 { 161 if (sval_is_min(sval)) 162 return 1; 163 if (sval_signed(sval) && sval.value == SHRT_MIN) 164 return 1; 165 if (sval_signed(sval) && sval.value == INT_MIN) 166 return 1; 167 if (sval_signed(sval) && sval.value == LLONG_MIN) 168 return 1; 169 return 0; 170 } 171 172 int sval_is_a_max(sval_t sval) 173 { 174 if (sval_is_max(sval)) 175 return 1; 176 if (sval.uvalue == SHRT_MAX) 177 return 1; 178 if (sval.uvalue == INT_MAX) 179 return 1; 180 if (sval.uvalue == LLONG_MAX) 181 return 1; 182 if (sval.uvalue == USHRT_MAX) 183 return 1; 184 if (sval.uvalue == UINT_MAX) 185 return 1; 186 if (sval_unsigned(sval) && sval.uvalue == ULLONG_MAX) 187 return 1; 188 if (sval.value > valid_ptr_max - 1000 && 189 sval.value < valid_ptr_max + 1000) 190 return 1; 191 return 0; 192 } 193 194 int sval_is_negative_min(sval_t sval) 195 { 196 if (!sval_is_negative(sval)) 197 return 0; 198 return sval_is_min(sval); 199 } 200 201 int sval_cmp_t(struct symbol *type, sval_t one, sval_t two) 202 { 203 sval_t one_cast, two_cast; 204 205 one_cast = sval_cast(type, one); 206 two_cast = sval_cast(type, two); 207 return sval_cmp(one_cast, two_cast); 208 } 209 210 int sval_cmp_val(sval_t one, long long val) 211 { 212 sval_t sval; 213 214 sval = sval_type_val(&llong_ctype, val); 215 return sval_cmp(one, sval); 216 } 217 218 sval_t sval_min(sval_t one, sval_t two) 219 { 220 if (sval_cmp(one, two) > 0) 221 return two; 222 return one; 223 } 224 225 sval_t sval_max(sval_t one, sval_t two) 226 { 227 if (sval_cmp(one, two) < 0) 228 return two; 229 return one; 230 } 231 232 int sval_too_low(struct symbol *type, sval_t sval) 233 { 234 if (sval_is_negative(sval) && type_unsigned(type)) 235 return 1; 236 if (type_signed(type) && sval_unsigned(sval)) 237 return 0; 238 if (type_signed(sval.type) && 239 sval.value < sval_type_min(type).value) 240 return 1; 241 if (sval_cmp(sval, sval_type_min(type)) < 0) 242 return 1; 243 return 0; 244 } 245 246 int sval_too_high(struct symbol *type, sval_t sval) 247 { 248 if (sval_is_negative(sval)) 249 return 0; 250 if (sval.uvalue > sval_type_max(type).uvalue) 251 return 1; 252 return 0; 253 } 254 255 int sval_fits(struct symbol *type, sval_t sval) 256 { 257 if (sval_too_low(type, sval)) 258 return 0; 259 if (sval_too_high(type, sval)) 260 return 0; 261 return 1; 262 } 263 264 sval_t sval_cast(struct symbol *type, sval_t sval) 265 { 266 sval_t ret; 267 268 if (!type) 269 type = &int_ctype; 270 271 ret.type = type; 272 switch (sval_bits(ret)) { 273 case 1: 274 ret.value = !!sval.value; 275 break; 276 case 8: 277 if (sval_unsigned(ret)) 278 ret.value = (long long)(unsigned char)sval.value; 279 else 280 ret.value = (long long)(char)sval.value; 281 break; 282 case 16: 283 if (sval_unsigned(ret)) 284 ret.value = (long long)(unsigned short)sval.value; 285 else 286 ret.value = (long long)(short)sval.value; 287 break; 288 case 32: 289 if (sval_unsigned(ret)) 290 ret.value = (long long)(unsigned int)sval.value; 291 else 292 ret.value = (long long)(int)sval.value; 293 break; 294 default: 295 ret.value = sval.value; 296 } 297 return ret; 298 299 } 300 301 sval_t sval_preop(sval_t sval, int op) 302 { 303 switch (op) { 304 case '!': 305 sval.value = !sval.value; 306 break; 307 case '~': 308 sval.value = ~sval.value; 309 sval = sval_cast(sval.type, sval); 310 break; 311 case '-': 312 sval.value = -sval.value; 313 sval = sval_cast(sval.type, sval); 314 break; 315 } 316 return sval; 317 } 318 319 static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right) 320 { 321 sval_t ret; 322 323 ret.type = type; 324 switch (op) { 325 case '*': 326 ret.uvalue = left.uvalue * right.uvalue; 327 break; 328 case '/': 329 if (right.uvalue == 0) { 330 sm_debug("%s: divide by zero", __func__); 331 ret.uvalue = 123456789; 332 } else { 333 ret.uvalue = left.uvalue / right.uvalue; 334 } 335 break; 336 case '+': 337 ret.uvalue = left.uvalue + right.uvalue; 338 break; 339 case '-': 340 ret.uvalue = left.uvalue - right.uvalue; 341 break; 342 case '%': 343 if (right.uvalue == 0) { 344 sm_perror(" %s: MOD by zero", __func__); 345 ret.uvalue = 123456789; 346 } else { 347 ret.uvalue = left.uvalue % right.uvalue; 348 } 349 break; 350 case '|': 351 ret.uvalue = left.uvalue | right.uvalue; 352 break; 353 case '&': 354 ret.uvalue = left.uvalue & right.uvalue; 355 break; 356 case SPECIAL_RIGHTSHIFT: 357 ret.uvalue = left.uvalue >> right.uvalue; 358 break; 359 case SPECIAL_LEFTSHIFT: 360 ret.uvalue = left.uvalue << right.uvalue; 361 break; 362 case '^': 363 ret.uvalue = left.uvalue ^ right.uvalue; 364 break; 365 default: 366 sm_perror(" %s: unhandled binop %s", __func__, 367 show_special(op)); 368 ret.uvalue = 1234567; 369 } 370 return ret; 371 } 372 373 374 static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right) 375 { 376 sval_t ret; 377 378 ret.type = type; 379 switch (op) { 380 case '*': 381 ret.value = left.value * right.value; 382 break; 383 case '/': 384 if (right.value == 0) { 385 sm_debug("%s: divide by zero", __func__); 386 ret.value = 123456789; 387 } else if (left.value == LLONG_MIN && right.value == -1) { 388 sm_debug("%s: invalid divide LLONG_MIN/-1", __func__); 389 ret.value = 12345678; 390 } else { 391 ret.value = left.value / right.value; 392 } 393 break; 394 case '+': 395 ret.value = left.value + right.value; 396 break; 397 case '-': 398 ret.value = left.value - right.value; 399 break; 400 case '%': 401 if (right.value == 0) { 402 sm_perror(" %s: MOD by zero", __func__); 403 ret.value = 123456789; 404 } else { 405 ret.value = left.value % right.value; 406 } 407 break; 408 case '|': 409 ret.value = left.value | right.value; 410 break; 411 case '&': 412 ret.value = left.value & right.value; 413 break; 414 case SPECIAL_RIGHTSHIFT: 415 ret.value = left.value >> right.value; 416 break; 417 case SPECIAL_LEFTSHIFT: 418 ret.value = left.value << right.value; 419 break; 420 case '^': 421 ret.value = left.value ^ right.value; 422 break; 423 default: 424 sm_perror(" %s: unhandled binop %s", __func__, 425 show_special(op)); 426 ret.value = 1234567; 427 } 428 return ret; 429 } 430 431 static sval_t ptr_binop(struct symbol *type, sval_t left, int op, sval_t right) 432 { 433 sval_t ret; 434 int align; 435 436 if (op != '+' && op != '-') 437 return sval_binop_unsigned(type, left, op, right); 438 439 ret.type = type; 440 if (type->type == SYM_PTR) 441 type = get_real_base_type(type); 442 align = type->ctype.alignment; 443 if (align <= 0) 444 align = 1; 445 446 if (op == '+') { 447 if (type_is_ptr(left.type)) 448 ret.value = left.value + right.value * align; 449 else 450 ret.value = left.value * align + right.value; 451 } else { 452 if (!type_is_ptr(left.type)) { 453 left.value = -left.value; 454 ret = ptr_binop(type, left, '+', right); 455 } else if (!type_is_ptr(right.type)) { 456 right.value = -right.value; 457 ret = ptr_binop(type, left, '+', right); 458 } else { 459 ret.value = (left.value - right.value) / align; 460 } 461 } 462 463 if (op == '-') 464 ret.type = ssize_t_ctype; 465 return ret; 466 } 467 468 sval_t sval_binop(sval_t left, int op, sval_t right) 469 { 470 struct symbol *type; 471 sval_t ret; 472 473 type = get_promoted_type(left.type, right.type); 474 475 if (type_is_ptr(type)) 476 ret = ptr_binop(type, left, op, right); 477 else if (type_unsigned(type)) 478 ret = sval_binop_unsigned(type, left, op, right); 479 else 480 ret = sval_binop_signed(type, left, op, right); 481 return sval_cast(type, ret); 482 } 483 484 int sval_unop_overflows(sval_t sval, int op) 485 { 486 if (op != '-') 487 return 0; 488 if (sval_positive_bits(sval) == 32 && sval.value == INT_MIN) 489 return 1; 490 if (sval_positive_bits(sval) == 64 && sval.value == LLONG_MIN) 491 return 1; 492 if (sval_is_negative(sval)) 493 return 0; 494 if (sval_signed(sval)) 495 return 0; 496 if (sval_bits(sval) == 32 && sval.uvalue > INT_MAX) 497 return 1; 498 if (sval_bits(sval) == 64 && sval.uvalue > LLONG_MAX) 499 return 1; 500 return 0; 501 } 502 503 int sval_binop_overflows(sval_t left, int op, sval_t right) 504 { 505 struct symbol *type; 506 sval_t max, min; 507 508 type = left.type; 509 if (type_positive_bits(right.type) > type_positive_bits(left.type)) 510 type = right.type; 511 if (type_positive_bits(type) < 31) 512 type = &int_ctype; 513 514 max = sval_type_max(type); 515 min = sval_type_min(type); 516 517 switch (op) { 518 case '+': 519 if (sval_is_negative(left) && sval_is_negative(right)) { 520 if (left.value < min.value + right.value) 521 return 1; 522 return 0; 523 } 524 if (sval_is_negative(left) || sval_is_negative(right)) 525 return 0; 526 if (left.uvalue > max.uvalue - right.uvalue) 527 return 1; 528 return 0; 529 case '*': 530 if (type_signed(type)) { 531 if (left.value == 0 || right.value == 0) 532 return 0; 533 if (left.value > max.value / right.value) 534 return 1; 535 if (left.value == -1 || right.value == -1) 536 return 0; 537 return left.value != left.value * right.value / right.value; 538 539 } 540 return right.uvalue != 0 && left.uvalue > max.uvalue / right.uvalue; 541 case '-': 542 if (type_unsigned(type)) { 543 if (sval_cmp(left, right) < 0) 544 return 1; 545 return 0; 546 } 547 if (sval_is_negative(left) && sval_is_negative(right)) 548 return 0; 549 550 if (sval_is_negative(left)) { 551 if (left.value < min.value + right.value) 552 return 1; 553 return 0; 554 } 555 if (sval_is_negative(right)) { 556 if (right.value == min.value) 557 return 1; 558 right = sval_preop(right, '-'); 559 if (sval_binop_overflows(left, '+', right)) 560 return 1; 561 return 0; 562 } 563 return 0; 564 case SPECIAL_LEFTSHIFT: 565 if (sval_cmp(left, sval_binop(max, invert_op(op), right)) > 0) 566 return 1; 567 return 0; 568 } 569 return 0; 570 } 571 572 int sval_binop_overflows_no_sign(sval_t left, int op, sval_t right) 573 { 574 575 struct symbol *type; 576 577 type = left.type; 578 if (type_positive_bits(right.type) > type_positive_bits(left.type)) 579 type = right.type; 580 if (type_positive_bits(type) <= 31) 581 type = &uint_ctype; 582 else 583 type = &ullong_ctype; 584 585 left = sval_cast(type, left); 586 right = sval_cast(type, right); 587 return sval_binop_overflows(left, op, right); 588 } 589 590 int find_first_zero_bit(unsigned long long uvalue) 591 { 592 int i; 593 594 for (i = 0; i < 64; i++) { 595 if (!(uvalue & (1ULL << i))) 596 return i; 597 } 598 return i; 599 } 600 601 int sm_fls64(unsigned long long uvalue) 602 { 603 int high_bit = 0; 604 605 while (uvalue) { 606 uvalue >>= 1; 607 high_bit++; 608 } 609 610 return high_bit; 611 } 612 613 unsigned long long fls_mask(unsigned long long uvalue) 614 { 615 int high_bit = 0; 616 617 high_bit = sm_fls64(uvalue); 618 if (high_bit == 0) 619 return 0; 620 621 return ((unsigned long long)-1) >> (64 - high_bit); 622 } 623 624 unsigned long long sval_fls_mask(sval_t sval) 625 { 626 return fls_mask(sval.uvalue); 627 } 628 629 const char *sval_to_str(sval_t sval) 630 { 631 char buf[30]; 632 633 if (sval_is_ptr(sval) && sval.value == valid_ptr_max) 634 return "ptr_max"; 635 if (sval_unsigned(sval) && sval.value == ULLONG_MAX) 636 return "u64max"; 637 if (sval_unsigned(sval) && sval.value == UINT_MAX) 638 return "u32max"; 639 if (sval.value == USHRT_MAX) 640 return "u16max"; 641 642 if (sval_signed(sval) && sval.value == LLONG_MAX) 643 return "s64max"; 644 if (sval.value == INT_MAX) 645 return "s32max"; 646 if (sval.value == SHRT_MAX) 647 return "s16max"; 648 649 if (sval_signed(sval) && sval.value == SHRT_MIN) 650 return "s16min"; 651 if (sval_signed(sval) && sval.value == INT_MIN) 652 return "s32min"; 653 if (sval_signed(sval) && sval.value == LLONG_MIN) 654 return "s64min"; 655 656 if (sval_unsigned(sval)) 657 snprintf(buf, sizeof(buf), "%llu", sval.value); 658 else if (sval.value < 0) 659 snprintf(buf, sizeof(buf), "(%lld)", sval.value); 660 else 661 snprintf(buf, sizeof(buf), "%lld", sval.value); 662 663 return alloc_sname(buf); 664 } 665 666 const char *sval_to_str_or_err_ptr(sval_t sval) 667 { 668 char buf[12]; 669 670 if (option_project != PROJ_KERNEL || 671 !is_ptr_type(sval.type)) 672 return sval_to_str(sval); 673 674 if (sval.uvalue >= -4905ULL) { 675 snprintf(buf, sizeof(buf), "(%lld)", sval.value); 676 return alloc_sname(buf); 677 } 678 679 return sval_to_str(sval); 680 } 681 682 const char *sval_to_numstr(sval_t sval) 683 { 684 char buf[30]; 685 686 if (sval_unsigned(sval)) 687 snprintf(buf, sizeof(buf), "%llu", sval.value); 688 else if (sval.value < 0) 689 snprintf(buf, sizeof(buf), "(%lld)", sval.value); 690 else 691 snprintf(buf, sizeof(buf), "%lld", sval.value); 692 693 return alloc_sname(buf); 694 } 695 696 sval_t ll_to_sval(long long val) 697 { 698 sval_t ret; 699 700 ret.type = &llong_ctype; 701 ret.value = val; 702 return ret; 703 } 704 705 static void free_svals(struct symbol *sym) 706 { 707 if (__inline_fn) 708 return; 709 clear_sval_alloc(); 710 } 711 712 void register_sval(int my_id) 713 { 714 add_hook(&free_svals, AFTER_FUNC_HOOK); 715 } 716