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