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