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 8:
 272                 if (sval_unsigned(ret))
 273                         ret.value = (long long)(unsigned char)sval.value;
 274                 else
 275                         ret.value = (long long)(char)sval.value;
 276                 break;
 277         case 16:
 278                 if (sval_unsigned(ret))
 279                         ret.value = (long long)(unsigned short)sval.value;
 280                 else
 281                         ret.value = (long long)(short)sval.value;
 282                 break;
 283         case 32:
 284                 if (sval_unsigned(ret))
 285                         ret.value = (long long)(unsigned int)sval.value;
 286                 else
 287                         ret.value = (long long)(int)sval.value;
 288                 break;
 289         default:
 290                 ret.value = sval.value;
 291         }
 292         return ret;
 293
 294 }
 295
 296 sval_t sval_preop(sval_t sval, int op)
 297 {
 298         switch (op) {
 299         case '!':
 300                 sval.value = !sval.value;
 301                 break;
 302         case '~':
 303                 sval.value = ~sval.value;
 304                 sval = sval_cast(sval.type, sval);
 305                 break;
 306         case '-':
 307                 sval.value = -sval.value;
 308                 sval = sval_cast(sval.type, sval);
 309                 break;
 310         }
 311         return sval;
 312 }
 313
 314 static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right)
 315 {
 316         sval_t ret;
 317
 318         ret.type = type;
 319         switch (op) {
 320         case '*':
 321                 ret.uvalue =  left.uvalue * right.uvalue;
 322                 break;
 323         case '/':
 324                 if (right.uvalue == 0) {
 325                         sm_msg("debug: %s: divide by zero", __func__);
 326                         ret.uvalue = 123456789;
 327                 } else {
 328                         ret.uvalue = left.uvalue / right.uvalue;
 329                 }
 330                 break;
 331         case '+':
 332                 ret.uvalue = left.uvalue + right.uvalue;
 333                 break;
 334         case '-':
 335                 ret.uvalue = left.uvalue - right.uvalue;
 336                 break;
 337         case '%':
 338                 if (right.uvalue == 0) {
 339                         sm_msg("internal error: %s: MOD by zero", __func__);
 340                         ret.uvalue = 123456789;
 341                 } else {
 342                         ret.uvalue = left.uvalue % right.uvalue;
 343                 }
 344                 break;
 345         case '|':
 346                 ret.uvalue = left.uvalue | right.uvalue;
 347                 break;
 348         case '&':
 349                 ret.uvalue = left.uvalue & right.uvalue;
 350                 break;
 351         case SPECIAL_RIGHTSHIFT:
 352                 ret.uvalue = left.uvalue >> right.uvalue;
 353                 break;
 354         case SPECIAL_LEFTSHIFT:
 355                 ret.uvalue = left.uvalue << right.uvalue;
 356                 break;
 357         case '^':
 358                 ret.uvalue = left.uvalue ^ right.uvalue;
 359                 break;
 360         default:
 361                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 362                        show_special(op));
 363                 ret.uvalue = 1234567;
 364         }
 365         return ret;
 366 }
 367
 368
 369 static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right)
 370 {
 371         sval_t ret;
 372
 373         ret.type = type;
 374         switch (op) {
 375         case '*':
 376                 ret.value =  left.value * right.value;
 377                 break;
 378         case '/':
 379                 if (right.value == 0) {
 380                         sm_msg("debug: %s: divide by zero", __func__);
 381                         ret.value = 123456789;
 382                 } else if (left.value == LLONG_MIN && right.value == -1) {
 383                         sm_msg("debug: %s: invalid divide LLONG_MIN/-1", __func__);
 384                         ret.value = 12345678;
 385                 } else {
 386                         ret.value = left.value / right.value;
 387                 }
 388                 break;
 389         case '+':
 390                 ret.value = left.value + right.value;
 391                 break;
 392         case '-':
 393                 ret.value = left.value - right.value;
 394                 break;
 395         case '%':
 396                 if (right.value == 0) {
 397                         sm_msg("internal error: %s: MOD by zero", __func__);
 398                         ret.value = 123456789;
 399                 } else {
 400                         ret.value = left.value % right.value;
 401                 }
 402                 break;
 403         case '|':
 404                 ret.value = left.value | right.value;
 405                 break;
 406         case '&':
 407                 ret.value = left.value & right.value;
 408                 break;
 409         case SPECIAL_RIGHTSHIFT:
 410                 ret.value = left.value >> right.value;
 411                 break;
 412         case SPECIAL_LEFTSHIFT:
 413                 ret.value = left.value << right.value;
 414                 break;
 415         case '^':
 416                 ret.value = left.value ^ right.value;
 417                 break;
 418         default:
 419                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 420                        show_special(op));
 421                 ret.value = 1234567;
 422         }
 423         return ret;
 424 }
 425
 426 static sval_t ptr_binop(struct symbol *type, sval_t left, int op, sval_t right)
 427 {
 428         sval_t ret;
 429         int align;
 430
 431         if (op != '+' && op != '-')
 432                 return sval_binop_unsigned(type, left, op, right);
 433
 434         ret.type = type;
 435         if (type->type == SYM_PTR)
 436                 type = get_real_base_type(type);
 437         align = type->ctype.alignment;
 438         if (align <= 0)
 439                 align = 1;
 440
 441         if (op == '+') {
 442                 if (type_is_ptr(left.type))
 443                         ret.value = left.value + right.value * align;
 444                 else
 445                         ret.value = left.value * align + right.value;
 446         } else {
 447                 if (!type_is_ptr(left.type)) {
 448                         left.value = -left.value;
 449                         ret = ptr_binop(type, left, '+', right);
 450                 } else if (!type_is_ptr(right.type)) {
 451                         right.value = -right.value;
 452                         ret = ptr_binop(type, left, '+', right);
 453                 } else {
 454                         ret.value = (left.value - right.value) / align;
 455                 }
 456         }
 457
 458         return ret;
 459 }
 460
 461 sval_t sval_binop(sval_t left, int op, sval_t right)
 462 {
 463         struct symbol *type;
 464         sval_t ret;
 465
 466         type = get_promoted_type(left.type, right.type);
 467
 468         if (type_is_ptr(type))
 469                 ret = ptr_binop(type, left, op, right);
 470         else if (type_unsigned(type))
 471                 ret = sval_binop_unsigned(type, left, op, right);
 472         else
 473                 ret = sval_binop_signed(type, left, op, right);
 474         return sval_cast(type, ret);
 475 }
 476
 477 int sval_unop_overflows(sval_t sval, int op)
 478 {
 479         if (op != '-')
 480                 return 0;
 481         if (sval_positive_bits(sval) == 32 && sval.value == INT_MIN)
 482                 return 1;
 483         if (sval_positive_bits(sval) == 64 && sval.value == LLONG_MIN)
 484                 return 1;
 485         if (sval_is_negative(sval))
 486                 return 0;
 487         if (sval_signed(sval))
 488                 return 0;
 489         if (sval_bits(sval) == 32 && sval.uvalue > INT_MAX)
 490                 return 1;
 491         if (sval_bits(sval) == 64 && sval.uvalue > LLONG_MAX)
 492                 return 1;
 493         return 0;
 494 }
 495
 496 int sval_binop_overflows(sval_t left, int op, sval_t right)
 497 {
 498         struct symbol *type;
 499         sval_t max, min;
 500
 501         type = left.type;
 502         if (type_positive_bits(right.type) > type_positive_bits(left.type))
 503                 type = right.type;
 504         if (type_positive_bits(type) < 31)
 505                 type = &int_ctype;
 506
 507         max = sval_type_max(type);
 508         min = sval_type_min(type);
 509
 510         switch (op) {
 511         case '+':
 512                 if (sval_is_negative(left) && sval_is_negative(right)) {
 513                         if (left.value < min.value + right.value)
 514                                 return 1;
 515                         return 0;
 516                 }
 517                 if (sval_is_negative(left) || sval_is_negative(right))
 518                         return 0;
 519                 if (left.uvalue > max.uvalue - right.uvalue)
 520                                 return 1;
 521                 return 0;
 522         case '*':
 523                 if (type_signed(type)) {
 524                         if (left.value == 0 || right.value == 0)
 525                                 return 0;
 526                         if (left.value > max.value / right.value)
 527                                 return 1;
 528                         if (left.value == -1 || right.value == -1)
 529                                 return 0;
 530                         return left.value != left.value * right.value / right.value;
 531
 532                 }
 533                 return right.uvalue != 0 && left.uvalue > max.uvalue / right.uvalue;
 534         case '-':
 535                 if (type_unsigned(type)) {
 536                         if (sval_cmp(left, right) < 0)
 537                                 return 1;
 538                         return 0;
 539                 }
 540                 if (sval_is_negative(left) && sval_is_negative(right))
 541                         return 0;
 542
 543                 if (sval_is_negative(left)) {
 544                         if (left.value < min.value + right.value)
 545                                 return 1;
 546                         return 0;
 547                 }
 548                 if (sval_is_negative(right)) {
 549                         if (right.value == min.value)
 550                                 return 1;
 551                         right = sval_preop(right, '-');
 552                         if (sval_binop_overflows(left, '+', right))
 553                                 return 1;
 554                         return 0;
 555                 }
 556                 return 0;
 557         case SPECIAL_LEFTSHIFT:
 558                 if (sval_cmp(left, sval_binop(max, invert_op(op), right)) > 0)
 559                         return 1;
 560                 return 0;
 561         }
 562         return 0;
 563 }
 564
 565 unsigned long long fls_mask(unsigned long long uvalue)
 566 {
 567         unsigned long long high_bit = 0;
 568
 569         while (uvalue) {
 570                 uvalue >>= 1;
 571                 high_bit++;
 572         }
 573
 574         if (high_bit == 0)
 575                 return 0;
 576
 577         return ((unsigned long long)-1) >> (64 - high_bit);
 578 }
 579
 580 unsigned long long sval_fls_mask(sval_t sval)
 581 {
 582         return fls_mask(sval.uvalue);
 583 }
 584
 585 const char *sval_to_str(sval_t sval)
 586 {
 587         char buf[30];
 588
 589         if (sval_unsigned(sval) && sval.value == ULLONG_MAX)
 590                 return "u64max";
 591         if (sval_unsigned(sval) && sval.value == UINT_MAX)
 592                 return "u32max";
 593         if (sval.value == USHRT_MAX)
 594                 return "u16max";
 595
 596         if (sval_signed(sval) && sval.value == LLONG_MAX)
 597                 return "s64max";
 598         if (sval.value == INT_MAX)
 599                 return "s32max";
 600         if (sval.value == SHRT_MAX)
 601                 return "s16max";
 602
 603         if (sval_signed(sval) && sval.value == SHRT_MIN)
 604                 return "s16min";
 605         if (sval_signed(sval) && sval.value == INT_MIN)
 606                 return "s32min";
 607         if (sval_signed(sval) && sval.value == LLONG_MIN)
 608                 return "s64min";
 609
 610         if (sval_unsigned(sval))
 611                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 612         else if (sval.value < 0)
 613                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 614         else
 615                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 616
 617         return alloc_sname(buf);
 618 }
 619
 620 const char *sval_to_numstr(sval_t sval)
 621 {
 622         char buf[30];
 623
 624         if (sval_unsigned(sval))
 625                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 626         else if (sval.value < 0)
 627                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 628         else
 629                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 630
 631         return alloc_sname(buf);
 632 }
 633
 634 sval_t ll_to_sval(long long val)
 635 {
 636         sval_t ret;
 637
 638         ret.type = &llong_ctype;
 639         ret.value = val;
 640         return ret;
 641 }
 642
 643 static void free_svals(struct symbol *sym)
 644 {
 645         if (__inline_fn)
 646                 return;
 647         clear_sval_alloc();
 648 }
 649
 650 void register_sval(int my_id)
 651 {
 652         add_hook(&free_svals, AFTER_FUNC_HOOK);
 653 }