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