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