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         if (sval.value > valid_ptr_max - 1000 &&
 178             sval.value < valid_ptr_max + 1000)
 179                 return 1;
 180         return 0;
 181 }
 182
 183 int sval_is_negative_min(sval_t sval)
 184 {
 185         if (!sval_is_negative(sval))
 186                 return 0;
 187         return sval_is_min(sval);
 188 }
 189
 190 /*
 191  * Returns -1 if one is smaller, 0 if they are the same and 1 if two is larger.
 192  */
 193 int sval_cmp(sval_t one, sval_t two)
 194 {
 195         struct symbol *type;
 196
 197         type = one.type;
 198         if (sval_positive_bits(two) > sval_positive_bits(one))
 199                 type = two.type;
 200         if (type_bits(type) < 31)
 201                 type = &int_ctype;
 202
 203         one = sval_cast(type, one);
 204         two = sval_cast(type, two);
 205
 206         if (type_unsigned(type)) {
 207                 if (one.uvalue < two.uvalue)
 208                         return -1;
 209                 if (one.uvalue == two.uvalue)
 210                         return 0;
 211                 return 1;
 212         }
 213         /* fix me handle type promotion and unsigned values */
 214         if (one.value < two.value)
 215                 return -1;
 216         if (one.value == two.value)
 217                 return 0;
 218         return 1;
 219 }
 220
 221 int sval_cmp_t(struct symbol *type, sval_t one, sval_t two)
 222 {
 223         sval_t one_cast, two_cast;
 224
 225         one_cast = sval_cast(type, one);
 226         two_cast = sval_cast(type, two);
 227         return sval_cmp(one_cast, two_cast);
 228 }
 229
 230 int sval_cmp_val(sval_t one, long long val)
 231 {
 232         sval_t sval;
 233
 234         sval = sval_type_val(&llong_ctype, val);
 235         return sval_cmp(one, sval);
 236 }
 237
 238 sval_t sval_min(sval_t one, sval_t two)
 239 {
 240         if (sval_cmp(one, two) > 0)
 241                 return two;
 242         return one;
 243 }
 244
 245 sval_t sval_max(sval_t one, sval_t two)
 246 {
 247         if (sval_cmp(one, two) < 0)
 248                 return two;
 249         return one;
 250 }
 251
 252 int sval_too_low(struct symbol *type, sval_t sval)
 253 {
 254         if (sval_is_negative(sval) && type_unsigned(type))
 255                 return 1;
 256         if (type_signed(type) &&  sval_unsigned(sval))
 257                 return 0;
 258         if (sval_cmp(sval, sval_type_min(type)) < 0)
 259                 return 1;
 260         return 0;
 261 }
 262
 263 int sval_too_high(struct symbol *type, sval_t sval)
 264 {
 265         if (sval_is_negative(sval))
 266                 return 0;
 267         if (sval.uvalue > sval_type_max(type).uvalue)
 268                 return 1;
 269         return 0;
 270 }
 271
 272 int sval_fits(struct symbol *type, sval_t sval)
 273 {
 274         if (sval_too_low(type, sval))
 275                 return 0;
 276         if (sval_too_high(type, sval))
 277                 return 0;
 278         return 1;
 279 }
 280
 281 sval_t sval_cast(struct symbol *type, sval_t sval)
 282 {
 283         sval_t ret;
 284
 285         if (!type)
 286                 type = &llong_ctype;
 287
 288         ret.type = type;
 289         switch (sval_bits(ret)) {
 290         case 8:
 291                 if (sval_unsigned(ret))
 292                         ret.value = (long long)(unsigned char)sval.value;
 293                 else
 294                         ret.value = (long long)(char)sval.value;
 295                 break;
 296         case 16:
 297                 if (sval_unsigned(ret))
 298                         ret.value = (long long)(unsigned short)sval.value;
 299                 else
 300                         ret.value = (long long)(short)sval.value;
 301                 break;
 302         case 32:
 303                 if (sval_unsigned(ret))
 304                         ret.value = (long long)(unsigned int)sval.value;
 305                 else
 306                         ret.value = (long long)(int)sval.value;
 307                 break;
 308         default:
 309                 ret.value = sval.value;
 310         }
 311         return ret;
 312
 313 }
 314
 315 sval_t sval_preop(sval_t sval, int op)
 316 {
 317         switch (op) {
 318         case '!':
 319                 sval.value = !sval.value;
 320                 break;
 321         case '~':
 322                 sval.value = ~sval.value;
 323                 sval = sval_cast(sval.type, sval);
 324                 break;
 325         case '-':
 326                 sval.value = -sval.value;
 327                 sval = sval_cast(sval.type, sval);
 328                 break;
 329         }
 330         return sval;
 331 }
 332
 333 static sval_t sval_binop_unsigned(struct symbol *type, sval_t left, int op, sval_t right)
 334 {
 335         sval_t ret;
 336
 337         ret.type = type;
 338         switch (op) {
 339         case '*':
 340                 ret.uvalue =  left.uvalue * right.uvalue;
 341                 break;
 342         case '/':
 343                 if (right.uvalue == 0) {
 344                         sm_msg("debug: %s: divide 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 '%':
 357                 if (right.uvalue == 0) {
 358                         sm_msg("internal error: %s: MOD by zero", __func__);
 359                         ret.uvalue = 123456789;
 360                 } else {
 361                         ret.uvalue = left.uvalue % right.uvalue;
 362                 }
 363                 break;
 364         case '|':
 365                 ret.uvalue = left.uvalue | right.uvalue;
 366                 break;
 367         case '&':
 368                 ret.uvalue = left.uvalue & right.uvalue;
 369                 break;
 370         case SPECIAL_RIGHTSHIFT:
 371                 ret.uvalue = left.uvalue >> right.uvalue;
 372                 break;
 373         case SPECIAL_LEFTSHIFT:
 374                 ret.uvalue = left.uvalue << right.uvalue;
 375                 break;
 376         case '^':
 377                 ret.uvalue = left.uvalue ^ right.uvalue;
 378                 break;
 379         default:
 380                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 381                        show_special(op));
 382                 ret.uvalue = 1234567;
 383         }
 384         return ret;
 385 }
 386
 387
 388 static sval_t sval_binop_signed(struct symbol *type, sval_t left, int op, sval_t right)
 389 {
 390         sval_t ret;
 391
 392         ret.type = type;
 393         switch (op) {
 394         case '*':
 395                 ret.value =  left.value * right.value;
 396                 break;
 397         case '/':
 398                 if (right.value == 0) {
 399                         sm_msg("debug: %s: divide by zero", __func__);
 400                         ret.value = 123456789;
 401                 } else if (left.value == LLONG_MIN && right.value == -1) {
 402                         sm_msg("debug: %s: invalid divide LLONG_MIN/-1", __func__);
 403                         ret.value = 12345678;
 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 '%':
 415                 if (right.value == 0) {
 416                         sm_msg("internal error: %s: MOD by zero", __func__);
 417                         ret.value = 123456789;
 418                 } else {
 419                         ret.value = left.value % right.value;
 420                 }
 421                 break;
 422         case '|':
 423                 ret.value = left.value | right.value;
 424                 break;
 425         case '&':
 426                 ret.value = left.value & right.value;
 427                 break;
 428         case SPECIAL_RIGHTSHIFT:
 429                 ret.value = left.value >> right.value;
 430                 break;
 431         case SPECIAL_LEFTSHIFT:
 432                 ret.value = left.value << right.value;
 433                 break;
 434         case '^':
 435                 ret.value = left.value ^ right.value;
 436                 break;
 437         default:
 438                 sm_msg("internal error: %s: unhandled binop %s", __func__,
 439                        show_special(op));
 440                 ret.value = 1234567;
 441         }
 442         return ret;
 443 }
 444
 445 sval_t sval_binop(sval_t left, int op, sval_t right)
 446 {
 447         struct symbol *type;
 448         sval_t ret;
 449
 450         type = left.type;
 451         if (sval_positive_bits(right) > sval_positive_bits(left))
 452                 type = right.type;
 453         if (type_positive_bits(type) < 31)
 454                 type = &int_ctype;
 455
 456         if (type_unsigned(type))
 457                 ret = sval_binop_unsigned(type, left, op, right);
 458         else
 459                 ret = sval_binop_signed(type, left, op, right);
 460         return ret;
 461 }
 462
 463 int sval_unop_overflows(sval_t sval, int op)
 464 {
 465         if (op != '-')
 466                 return 0;
 467         if (sval_positive_bits(sval) == 32 && sval.value == INT_MIN)
 468                 return 1;
 469         if (sval_positive_bits(sval) == 64 && sval.value == LLONG_MIN)
 470                 return 1;
 471         if (sval_is_negative(sval))
 472                 return 0;
 473         if (sval_signed(sval))
 474                 return 0;
 475         if (sval_bits(sval) == 32 && sval.uvalue > INT_MAX)
 476                 return 1;
 477         if (sval_bits(sval) == 64 && sval.uvalue > LLONG_MAX)
 478                 return 1;
 479         return 0;
 480 }
 481
 482 int sval_binop_overflows(sval_t left, int op, sval_t right)
 483 {
 484         struct symbol *type;
 485         sval_t max, min;
 486
 487         type = left.type;
 488         if (type_positive_bits(right.type) > type_positive_bits(left.type))
 489                 type = right.type;
 490         if (type_positive_bits(type) < 31)
 491                 return 0;
 492         max = sval_type_max(type);
 493         min = sval_type_min(type);
 494
 495         switch (op) {
 496         case '+':
 497                 if (sval_is_negative(right)) {
 498                         if (left.value < min.value - right.value)
 499                                 return 1;
 500                 } else {
 501                         if (left.uvalue > max.uvalue - right.uvalue)
 502                                 return 1;
 503                 }
 504                 return 0;
 505         case '*':
 506                 return right.uvalue != 0 && left.uvalue > max.uvalue / right.uvalue;
 507         case '-':
 508                 if (type_unsigned(type)) {
 509                         if (sval_cmp(left, right) < 0)
 510                                 return 1;
 511                         return 0;
 512                 }
 513
 514                 if (sval_unop_overflows(right, '-'))
 515                         return 1;
 516                 right = sval_preop(right, '-');
 517                 if (sval_binop_overflows(left, '+', right))
 518                         return 1;
 519                 return 0;
 520         }
 521         return 0;
 522 }
 523
 524 const char *sval_to_str(sval_t sval)
 525 {
 526         char buf[30];
 527
 528         if (sval_unsigned(sval) && sval.value == ULLONG_MAX)
 529                 return "u64max";
 530         if (sval_unsigned(sval) && sval.value == UINT_MAX)
 531                 return "u32max";
 532         if (sval_unsigned(sval) && sval.value == USHRT_MAX)
 533                 return "u16max";
 534
 535         if (sval_signed(sval) && sval.value == LLONG_MAX)
 536                 return "s64max";
 537         if (sval_signed(sval) && sval.value == INT_MAX)
 538                 return "s32max";
 539         if (sval_signed(sval) && sval.value == SHRT_MAX)
 540                 return "s16max";
 541
 542         if (sval_signed(sval) && sval.value == SHRT_MIN)
 543                 return "s16min";
 544         if (sval_signed(sval) && sval.value == INT_MIN)
 545                 return "s32min";
 546         if (sval_signed(sval) && sval.value == LLONG_MIN)
 547                 return "s64min";
 548
 549         if (sval_unsigned(sval))
 550                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 551         else if (sval.value < 0)
 552                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 553         else
 554                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 555
 556         return alloc_sname(buf);
 557 }
 558
 559 const char *sval_to_numstr(sval_t sval)
 560 {
 561         char buf[30];
 562
 563         if (sval_unsigned(sval))
 564                 snprintf(buf, sizeof(buf), "%llu", sval.value);
 565         else if (sval.value < 0)
 566                 snprintf(buf, sizeof(buf), "(%lld)", sval.value);
 567         else
 568                 snprintf(buf, sizeof(buf), "%lld", sval.value);
 569
 570         return alloc_sname(buf);
 571 }
 572
 573 sval_t ll_to_sval(long long val)
 574 {
 575         sval_t ret;
 576
 577         ret.type = &llong_ctype;
 578         ret.value = val;
 579         return ret;
 580 }
 581
 582 static void free_svals(struct symbol *sym)
 583 {
 584         if (__inline_fn)
 585                 return;
 586         clear_sval_alloc();
 587 }
 588
 589 void register_sval(int my_id)
 590 {
 591         add_hook(&free_svals, END_FUNC_HOOK);
 592 }