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