smatch_sval.c

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