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