smatch_sval.c

   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_msg("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_msg("internal error: %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_msg("internal error: %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_msg("debug: %s: divide by zero", __func__);
 384                         ret.value = 123456789;
 385                 } else if (left.value == LLONG_MIN && right.value == -1) {
 386                         sm_msg("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_msg("internal error: %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_msg("internal error: %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 }