1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   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 #include "symbol.h"
  19 #include "smatch.h"
  20 #include "smatch_slist.h"
  21 #include "smatch_extra.h"
  22 
  23 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res);
  24 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res);
  25 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval);
  26 static struct range_list *(*custom_handle_variable)(struct expression *expr);
  27 
  28 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval);
  29 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt);
  30 
  31 static sval_t zero  = {.type = &int_ctype, {.value = 0} };
  32 static sval_t one   = {.type = &int_ctype, {.value = 1} };
  33 
  34 static int fast_math_only;
  35 
  36 struct range_list *rl_zero(void)
  37 {
  38         static struct range_list *zero_perm;
  39 
  40         if (!zero_perm)
  41                 zero_perm = clone_rl_permanent(alloc_rl(zero, zero));
  42         return zero_perm;
  43 }
  44 
  45 struct range_list *rl_one(void)
  46 {
  47         static struct range_list *one_perm;
  48 
  49         if (!one_perm)
  50                 one_perm = clone_rl_permanent(alloc_rl(one, one));
  51 
  52         return one_perm;
  53 }
  54 
  55 enum {
  56         RL_EXACT,
  57         RL_HARD,
  58         RL_FUZZY,
  59         RL_IMPLIED,
  60         RL_ABSOLUTE,
  61         RL_REAL_ABSOLUTE,
  62 };
  63 
  64 static bool last_stmt_rl(struct statement *stmt, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
  65 {
  66         struct expression *expr;
  67 
  68         if (!stmt)
  69                 return false;
  70 
  71         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
  72         if (stmt->type == STMT_LABEL) {
  73                 if (stmt->label_statement &&
  74                     stmt->label_statement->type == STMT_EXPRESSION)
  75                         expr = stmt->label_statement->expression;
  76                 else
  77                         return false;
  78         } else if (stmt->type == STMT_EXPRESSION) {
  79                 expr = stmt->expression;
  80         } else {
  81                 return false;
  82         }
  83         return get_rl_sval(expr, implied, recurse_cnt, res, res_sval);
  84 }
  85 
  86 static bool handle_expression_statement_rl(struct expression *expr, int implied,
  87                 int *recurse_cnt, struct range_list **res, sval_t *res_sval)
  88 {
  89         return last_stmt_rl(get_expression_statement(expr), implied, recurse_cnt, res, res_sval);
  90 }
  91 
  92 static bool handle_address(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
  93 {
  94         struct range_list *rl;
  95         static int recursed;
  96         sval_t sval;
  97 
  98         if (recursed > 10)
  99                 return false;
 100         if (implied == RL_EXACT)
 101                 return false;
 102 
 103         if (custom_handle_variable) {
 104                 rl = custom_handle_variable(expr);
 105                 if (rl) {
 106                         *res = rl;
 107                         return true;
 108                 }
 109         }
 110 
 111         recursed++;
 112         if (get_mtag_sval(expr, &sval)) {
 113                 recursed--;
 114                 *res_sval = sval;
 115                 return true;
 116         }
 117 
 118         if (get_address_rl(expr, res)) {
 119                 recursed--;
 120                 return true;
 121         }
 122         recursed--;
 123         return 0;
 124 }
 125 
 126 static bool handle_ampersand_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 127 {
 128         return handle_address(expr, implied, recurse_cnt, res, res_sval);
 129 }
 130 
 131 static bool handle_negate_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 132 {
 133         if (known_condition_true(expr->unop)) {
 134                 *res_sval = zero;
 135                 return true;
 136         }
 137         if (known_condition_false(expr->unop)) {
 138                 *res_sval = one;
 139                 return true;
 140         }
 141 
 142         if (implied == RL_EXACT)
 143                 return false;
 144 
 145         if (implied_condition_true(expr->unop)) {
 146                 *res_sval = zero;
 147                 return true;
 148         }
 149         if (implied_condition_false(expr->unop)) {
 150                 *res_sval = one;
 151                 return true;
 152         }
 153 
 154         *res = alloc_rl(zero, one);
 155         return true;
 156 }
 157 
 158 static bool handle_bitwise_negate(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
 159 {
 160         struct range_list *rl;
 161         sval_t sval = {};
 162 
 163         if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
 164                 return false;
 165         if (!sval.type && !rl_to_sval(rl, &sval))
 166                 return false;
 167         sval = sval_preop(sval, '~');
 168         sval_cast(get_type(expr->unop), sval);
 169         *res_sval = sval;
 170         return true;
 171 }
 172 
 173 static bool untrusted_type_min(struct expression *expr)
 174 {
 175         struct range_list *rl;
 176 
 177         rl = var_user_rl(expr);
 178         return rl && sval_is_min(rl_min(rl));
 179 }
 180 
 181 static bool handle_minus_preop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 182 {
 183         struct range_list *rl;
 184         struct range_list *ret = NULL;
 185         struct symbol *type;
 186         sval_t neg_one = { 0 };
 187         sval_t zero = { 0 };
 188         sval_t sval = {};
 189 
 190         neg_one.value = -1;
 191         zero.value = 0;
 192 
 193         if (!get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval))
 194                 return false;
 195         if (sval.type) {
 196                 *res_sval = sval_preop(sval, '-');
 197                 return true;
 198         }
 199         /*
 200          * One complication is that -INT_MIN is still INT_MIN because of integer
 201          * overflows...  But how many times do we set a time out to INT_MIN?
 202          * So normally when we call abs() then it does return a positive value.
 203          *
 204          */
 205         type = rl_type(rl);
 206         neg_one.type = zero.type = type;
 207 
 208         if (sval_is_negative(rl_min(rl))) {
 209                 struct range_list *neg;
 210                 struct data_range *drange;
 211                 sval_t new_min, new_max;
 212 
 213                 neg = alloc_rl(sval_type_min(type), neg_one);
 214                 neg = rl_intersection(rl, neg);
 215 
 216                 if (sval_is_min(rl_min(neg)) && !sval_is_min(rl_max(neg)))
 217                         neg = remove_range(neg, sval_type_min(type), sval_type_min(type));
 218 
 219                 FOR_EACH_PTR(neg, drange) {
 220                         new_min = drange->max;
 221                         new_min.value = -new_min.value;
 222                         new_max = drange->min;
 223                         new_max.value = -new_max.value;
 224                         add_range(&ret, new_min, new_max);
 225                 } END_FOR_EACH_PTR(drange);
 226 
 227                 if (untrusted_type_min(expr))
 228                         add_range(&ret, sval_type_min(type), sval_type_min(type));
 229         }
 230 
 231         if (!sval_is_negative(rl_max(rl))) {
 232                 struct range_list *pos;
 233                 struct data_range *drange;
 234                 sval_t new_min, new_max;
 235 
 236                 pos = alloc_rl(zero, sval_type_max(type));
 237                 pos = rl_intersection(rl, pos);
 238 
 239                 FOR_EACH_PTR(pos, drange) {
 240                         new_min = drange->max;
 241                         new_min.value = -new_min.value;
 242                         new_max = drange->min;
 243                         new_max.value = -new_max.value;
 244                         add_range(&ret, new_min, new_max);
 245                 } END_FOR_EACH_PTR(drange);
 246         }
 247 
 248         *res = ret;
 249         return true;
 250 }
 251 
 252 static bool handle_preop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 253 {
 254         switch (expr->op) {
 255         case '&':
 256                 return handle_ampersand_rl(expr, implied, recurse_cnt, res, res_sval);
 257         case '!':
 258                 return handle_negate_rl(expr, implied, recurse_cnt, res, res_sval);
 259         case '~':
 260                 return handle_bitwise_negate(expr, implied, recurse_cnt, res_sval);
 261         case '-':
 262                 return handle_minus_preop(expr, implied, recurse_cnt, res, res_sval);
 263         case '*':
 264                 return handle_variable(expr, implied, recurse_cnt, res, res_sval);
 265         case '(':
 266                 return handle_expression_statement_rl(expr, implied, recurse_cnt, res, res_sval);
 267         default:
 268                 return false;
 269         }
 270 }
 271 
 272 static bool handle_divide_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
 273 {
 274         struct range_list *left_rl = NULL;
 275         struct range_list *right_rl = NULL;
 276         struct symbol *type;
 277 
 278         type = get_type(expr);
 279 
 280         get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
 281         left_rl = cast_rl(type, left_rl);
 282         get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
 283         right_rl = cast_rl(type, right_rl);
 284 
 285         if (!left_rl || !right_rl)
 286                 return false;
 287 
 288         if (implied != RL_REAL_ABSOLUTE) {
 289                 if (is_whole_rl(left_rl) || is_whole_rl(right_rl))
 290                         return false;
 291         }
 292 
 293         *res = rl_binop(left_rl, '/', right_rl);
 294         return true;
 295 }
 296 
 297 static int handle_offset_subtraction(struct expression *expr)
 298 {
 299         struct expression *left, *right;
 300         struct symbol *left_sym, *right_sym;
 301         struct symbol *type;
 302         int left_offset, right_offset;
 303 
 304         type = get_type(expr);
 305         if (!type || type->type != SYM_PTR)
 306                 return -1;
 307         type = get_real_base_type(type);
 308         if (!type || (type_bits(type) != 8 && (type != &void_ctype)))
 309                 return -1;
 310 
 311         left = strip_expr(expr->left);
 312         right = strip_expr(expr->right);
 313 
 314         if (left->type != EXPR_PREOP || left->op != '&')
 315                 return -1;
 316         left = strip_expr(left->unop);
 317 
 318         left_sym = expr_to_sym(left);
 319         right_sym = expr_to_sym(right);
 320         if (!left_sym || left_sym != right_sym)
 321                 return -1;
 322 
 323         left_offset = get_member_offset_from_deref(left);
 324         if (right->type == EXPR_SYMBOL)
 325                 right_offset = 0;
 326         else {
 327                 if (right->type != EXPR_PREOP || right->op != '&')
 328                         return -1;
 329                 right = strip_expr(right->unop);
 330                 right_offset = get_member_offset_from_deref(right);
 331         }
 332         if (left_offset < 0 || right_offset < 0)
 333                 return -1;
 334 
 335         return left_offset - right_offset;
 336 }
 337 
 338 static bool max_is_unknown_max(struct range_list *rl)
 339 {
 340         /*
 341          * The issue with this code is that we had:
 342          * if (foo > 1) return 1 - foo;
 343          * Ideally we would say that returns s32min-(-1) but what Smatch
 344          * was saying was that the lowest possible value was "1 - INT_MAX"
 345          *
 346          * My solution is to ignore max values for int or larger.  I keep
 347          * the max for shorts etc, because those might be worthwhile.
 348          *
 349          * The problem with just returning 1 - INT_MAX is that that is
 350          * treated as useful information but s32min is treated as basically
 351          * unknown.
 352          */
 353 
 354         if (type_bits(rl_type(rl)) < 31)
 355                 return false;
 356         return sval_is_max(rl_max(rl));
 357 }
 358 
 359 static bool handle_subtract_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
 360 {
 361         struct symbol *type;
 362         struct range_list *left_orig, *right_orig;
 363         struct range_list *left_rl, *right_rl;
 364         sval_t min, max, tmp;
 365         int comparison;
 366         int offset;
 367 
 368         type = get_type(expr);
 369 
 370         offset = handle_offset_subtraction(expr);
 371         if (offset >= 0) {
 372                 tmp.type = type;
 373                 tmp.value = offset;
 374 
 375                 *res = alloc_rl(tmp, tmp);
 376                 return true;
 377         }
 378 
 379         comparison = get_comparison(expr->left, expr->right);
 380 
 381         left_orig = NULL;
 382         get_rl_internal(expr->left, implied, recurse_cnt, &left_orig);
 383         left_rl = cast_rl(type, left_orig);
 384         right_orig = NULL;
 385         get_rl_internal(expr->right, implied, recurse_cnt, &right_orig);
 386         right_rl = cast_rl(type, right_orig);
 387 
 388         if ((!left_rl || !right_rl) &&
 389             (implied == RL_EXACT || implied == RL_HARD || implied == RL_FUZZY))
 390                 return false;
 391 
 392         if (!left_rl)
 393                 left_rl = alloc_whole_rl(type);
 394         if (!right_rl)
 395                 right_rl = alloc_whole_rl(type);
 396 
 397         /* negative values complicate everything fix this later */
 398         if (sval_is_negative(rl_min(right_rl)))
 399                 return false;
 400         max = rl_max(left_rl);
 401         min = sval_type_min(type);
 402 
 403         switch (comparison) {
 404         case '>':
 405         case SPECIAL_UNSIGNED_GT:
 406                 min = sval_type_val(type, 1);
 407                 max = rl_max(left_rl);
 408                 break;
 409         case SPECIAL_GTE:
 410         case SPECIAL_UNSIGNED_GTE:
 411                 min = sval_type_val(type, 0);
 412                 max = rl_max(left_rl);
 413                 break;
 414         case SPECIAL_EQUAL:
 415                 min = sval_type_val(type, 0);
 416                 max = sval_type_val(type, 0);
 417                 break;
 418         case '<':
 419         case SPECIAL_UNSIGNED_LT:
 420                 max = sval_type_val(type, -1);
 421                 break;
 422         case SPECIAL_LTE:
 423         case SPECIAL_UNSIGNED_LTE:
 424                 max = sval_type_val(type, 0);
 425                 break;
 426         default:
 427                 if (!left_orig || !right_orig)
 428                         return false;
 429                 *res = rl_binop(left_rl, '-', right_rl);
 430                 return true;
 431         }
 432 
 433         if (!max_is_unknown_max(right_rl) &&
 434             !sval_binop_overflows(rl_min(left_rl), '-', rl_max(right_rl))) {
 435                 tmp = sval_binop(rl_min(left_rl), '-', rl_max(right_rl));
 436                 if (sval_cmp(tmp, min) > 0)
 437                         min = tmp;
 438         }
 439 
 440         if (!sval_is_max(rl_max(left_rl))) {
 441                 tmp = sval_binop(rl_max(left_rl), '-', rl_min(right_rl));
 442                 if (sval_cmp(tmp, max) < 0)
 443                         max = tmp;
 444         }
 445 
 446         if (sval_is_min(min) && sval_is_max(max))
 447                 return false;
 448 
 449         *res = cast_rl(type, alloc_rl(min, max));
 450         return true;
 451 }
 452 
 453 static bool handle_mod_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
 454 {
 455         struct range_list *rl;
 456         sval_t left, right, sval;
 457 
 458         if (implied == RL_EXACT) {
 459                 if (!get_implied_value(expr->right, &right))
 460                         return false;
 461                 if (!get_implied_value(expr->left, &left))
 462                         return false;
 463                 sval = sval_binop(left, '%', right);
 464                 *res = alloc_rl(sval, sval);
 465                 return true;
 466         }
 467         /* if we can't figure out the right side it's probably hopeless */
 468         if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
 469                 return false;
 470 
 471         right = sval_cast(get_type(expr), right);
 472         right.value--;
 473 
 474         if (get_rl_internal(expr->left, implied, recurse_cnt, &rl) && rl &&
 475             rl_max(rl).uvalue < right.uvalue)
 476                 right.uvalue = rl_max(rl).uvalue;
 477 
 478         *res = alloc_rl(sval_cast(right.type, zero), right);
 479         return true;
 480 }
 481 
 482 static bool handle_bitwise_AND(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
 483 {
 484         struct symbol *type;
 485         struct range_list *left_rl, *right_rl;
 486         int new_recurse;
 487 
 488         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 489                 return false;
 490 
 491         type = get_type(expr);
 492 
 493         if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl))
 494                 left_rl = alloc_whole_rl(type);
 495         left_rl = cast_rl(type, left_rl);
 496 
 497         new_recurse = *recurse_cnt;
 498         if (*recurse_cnt >= 200)
 499                 new_recurse = 100;  /* Let's try super hard to get the mask */
 500         if (!get_rl_internal(expr->right, implied, &new_recurse, &right_rl))
 501                 right_rl = alloc_whole_rl(type);
 502         right_rl = cast_rl(type, right_rl);
 503         *recurse_cnt = new_recurse;
 504 
 505         *res = rl_binop(left_rl, '&', right_rl);
 506         return true;
 507 }
 508 
 509 static bool use_rl_binop(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
 510 {
 511         struct symbol *type;
 512         struct range_list *left_rl, *right_rl;
 513 
 514         if (implied != RL_IMPLIED && implied != RL_ABSOLUTE && implied != RL_REAL_ABSOLUTE)
 515                 return false;
 516 
 517         type = get_type(expr);
 518 
 519         get_absolute_rl_internal(expr->left, &left_rl, recurse_cnt);
 520         get_absolute_rl_internal(expr->right, &right_rl, recurse_cnt);
 521         left_rl = cast_rl(type, left_rl);
 522         right_rl = cast_rl(type, right_rl);
 523         if (!left_rl || !right_rl)
 524                 return false;
 525 
 526         *res = rl_binop(left_rl, expr->op, right_rl);
 527         return true;
 528 }
 529 
 530 static bool handle_right_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
 531 {
 532         struct range_list *left_rl, *right_rl;
 533         sval_t min, max;
 534 
 535         if (implied == RL_EXACT || implied == RL_HARD)
 536                 return false;
 537 
 538         if (get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
 539                 max = rl_max(left_rl);
 540                 min = rl_min(left_rl);
 541         } else {
 542                 if (implied == RL_FUZZY)
 543                         return false;
 544                 max = sval_type_max(get_type(expr->left));
 545                 min = sval_type_val(get_type(expr->left), 0);
 546         }
 547 
 548         if (get_rl_internal(expr->right, implied, recurse_cnt, &right_rl) &&
 549             !sval_is_negative(rl_min(right_rl))) {
 550                 min = sval_binop(min, SPECIAL_RIGHTSHIFT, rl_max(right_rl));
 551                 max = sval_binop(max, SPECIAL_RIGHTSHIFT, rl_min(right_rl));
 552         } else if (!sval_is_negative(min)) {
 553                 min.value = 0;
 554                 max = sval_type_max(max.type);
 555         } else {
 556                 return false;
 557         }
 558 
 559         *res = alloc_rl(min, max);
 560         return true;
 561 }
 562 
 563 static bool handle_left_shift(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
 564 {
 565         struct range_list *left_rl, *rl;
 566         sval_t right;
 567 
 568         if (implied == RL_EXACT || implied == RL_HARD)
 569                 return false;
 570         /* this is hopeless without the right side */
 571         if (!get_implied_value_internal(expr->right, recurse_cnt, &right))
 572                 return false;
 573         if (!get_rl_internal(expr->left, implied, recurse_cnt, &left_rl)) {
 574                 if (implied == RL_FUZZY)
 575                         return false;
 576                 left_rl = alloc_whole_rl(get_type(expr->left));
 577         }
 578 
 579         rl = rl_binop(left_rl, SPECIAL_LEFTSHIFT, alloc_rl(right, right));
 580         if (!rl)
 581                 return false;
 582         *res = rl;
 583         return true;
 584 }
 585 
 586 static bool handle_known_binop(struct expression *expr, sval_t *res)
 587 {
 588         sval_t left, right;
 589 
 590         if (!get_value(expr->left, &left))
 591                 return false;
 592         if (!get_value(expr->right, &right))
 593                 return false;
 594         *res = sval_binop(left, expr->op, right);
 595         return true;
 596 }
 597 
 598 static int has_actual_ranges(struct range_list *rl)
 599 {
 600         struct data_range *tmp;
 601 
 602         FOR_EACH_PTR(rl, tmp) {
 603                 if (sval_cmp(tmp->min, tmp->max) != 0)
 604                         return 1;
 605         } END_FOR_EACH_PTR(tmp);
 606         return 0;
 607 }
 608 
 609 static struct range_list *handle_implied_binop(struct range_list *left_rl, int op, struct range_list *right_rl)
 610 {
 611         struct range_list *res_rl;
 612         struct data_range *left_drange, *right_drange;
 613         sval_t res;
 614 
 615         if (!left_rl || !right_rl)
 616                 return NULL;
 617         if (has_actual_ranges(left_rl))
 618                 return NULL;
 619         if (has_actual_ranges(right_rl))
 620                 return NULL;
 621 
 622         if (ptr_list_size((struct ptr_list *)left_rl) * ptr_list_size((struct ptr_list *)right_rl) > 20)
 623                 return NULL;
 624 
 625         res_rl = NULL;
 626 
 627         FOR_EACH_PTR(left_rl, left_drange) {
 628                 FOR_EACH_PTR(right_rl, right_drange) {
 629                         if ((op == '%' || op == '/') &&
 630                             right_drange->min.value == 0)
 631                                 return NULL;
 632                         res = sval_binop(left_drange->min, op, right_drange->min);
 633                         add_range(&res_rl, res, res);
 634                 } END_FOR_EACH_PTR(right_drange);
 635         } END_FOR_EACH_PTR(left_drange);
 636 
 637         return res_rl;
 638 }
 639 
 640 static bool handle_binop_rl_helper(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 641 {
 642         struct symbol *type;
 643         struct range_list *left_rl = NULL;
 644         struct range_list *right_rl = NULL;
 645         struct range_list *rl;
 646         sval_t min, max;
 647 
 648         type = get_promoted_type(get_type(expr->left), get_type(expr->right));
 649         get_rl_internal(expr->left, implied, recurse_cnt, &left_rl);
 650         left_rl = cast_rl(type, left_rl);
 651         get_rl_internal(expr->right, implied, recurse_cnt, &right_rl);
 652         right_rl = cast_rl(type, right_rl);
 653         if (!left_rl && !right_rl)
 654                 return false;
 655 
 656         rl = handle_implied_binop(left_rl, expr->op, right_rl);
 657         if (rl) {
 658                 *res = rl;
 659                 return true;
 660         }
 661 
 662         switch (expr->op) {
 663         case '%':
 664                 return handle_mod_rl(expr, implied, recurse_cnt, res);
 665         case '&':
 666                 return handle_bitwise_AND(expr, implied, recurse_cnt, res);
 667         case '|':
 668         case '^':
 669                 return use_rl_binop(expr, implied, recurse_cnt, res);
 670         case SPECIAL_RIGHTSHIFT:
 671                 return handle_right_shift(expr, implied, recurse_cnt, res);
 672         case SPECIAL_LEFTSHIFT:
 673                 return handle_left_shift(expr, implied, recurse_cnt, res);
 674         case '-':
 675                 return handle_subtract_rl(expr, implied, recurse_cnt, res);
 676         case '/':
 677                 return handle_divide_rl(expr, implied, recurse_cnt, res);
 678         }
 679 
 680         if (!left_rl || !right_rl)
 681                 return false;
 682 
 683         if (sval_binop_overflows(rl_min(left_rl), expr->op, rl_min(right_rl)))
 684                 return false;
 685         if (sval_binop_overflows(rl_max(left_rl), expr->op, rl_max(right_rl)))
 686                 return false;
 687 
 688         min = sval_binop(rl_min(left_rl), expr->op, rl_min(right_rl));
 689         max = sval_binop(rl_max(left_rl), expr->op, rl_max(right_rl));
 690 
 691         *res = alloc_rl(min, max);
 692         return true;
 693 
 694 }
 695 
 696 static bool handle_binop_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 697 {
 698         struct smatch_state *state;
 699         struct range_list *rl;
 700         sval_t val;
 701 
 702         if (handle_known_binop(expr, &val)) {
 703                 *res_sval = val;
 704                 return true;
 705         }
 706         if (implied == RL_EXACT)
 707                 return false;
 708 
 709         if (custom_handle_variable) {
 710                 rl = custom_handle_variable(expr);
 711                 if (rl) {
 712                         *res = rl;
 713                         return true;
 714                 }
 715         }
 716 
 717         state = get_extra_state(expr);
 718         if (state && !is_whole_rl(estate_rl(state))) {
 719                 if (implied != RL_HARD || estate_has_hard_max(state)) {
 720                         *res = clone_rl(estate_rl(state));
 721                         return true;
 722                 }
 723         }
 724 
 725         return handle_binop_rl_helper(expr, implied, recurse_cnt, res, res_sval);
 726 }
 727 
 728 static int do_comparison(struct expression *expr)
 729 {
 730         struct range_list *left_ranges = NULL;
 731         struct range_list *right_ranges = NULL;
 732         int poss_true, poss_false;
 733         struct symbol *type;
 734 
 735         type = get_type(expr);
 736         get_absolute_rl(expr->left, &left_ranges);
 737         get_absolute_rl(expr->right, &right_ranges);
 738 
 739         left_ranges = cast_rl(type, left_ranges);
 740         right_ranges = cast_rl(type, right_ranges);
 741 
 742         poss_true = possibly_true_rl(left_ranges, expr->op, right_ranges);
 743         poss_false = possibly_false_rl(left_ranges, expr->op, right_ranges);
 744 
 745         if (!poss_true && !poss_false)
 746                 return 0x0;
 747         if (poss_true && !poss_false)
 748                 return 0x1;
 749         if (!poss_true && poss_false)
 750                 return 0x2;
 751         return 0x3;
 752 }
 753 
 754 static bool handle_comparison_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 755 {
 756         sval_t left, right;
 757         int cmp;
 758 
 759         if (expr->op == SPECIAL_EQUAL && expr->left->type == EXPR_TYPE) {
 760                 struct symbol *left, *right;
 761 
 762                 if (expr->right->type != EXPR_TYPE)
 763                         return false;
 764 
 765                 left = get_real_base_type(expr->left->symbol);
 766                 right = get_real_base_type(expr->right->symbol);
 767                 if (type_bits(left) == type_bits(right) &&
 768                     type_positive_bits(left) == type_positive_bits(right))
 769                         *res_sval = one;
 770                 else
 771                         *res_sval = zero;
 772                 return true;
 773         }
 774 
 775         if (get_value(expr->left, &left) && get_value(expr->right, &right)) {
 776                 struct data_range tmp_left, tmp_right;
 777 
 778                 tmp_left.min = left;
 779                 tmp_left.max = left;
 780                 tmp_right.min = right;
 781                 tmp_right.max = right;
 782                 if (true_comparison_range(&tmp_left, expr->op, &tmp_right))
 783                         *res_sval = one;
 784                 else
 785                         *res_sval = zero;
 786                 return true;
 787         }
 788 
 789         if (implied == RL_EXACT)
 790                 return false;
 791 
 792         cmp = do_comparison(expr);
 793         if (cmp == 1) {
 794                 *res_sval = one;
 795                 return true;
 796         }
 797         if (cmp == 2) {
 798                 *res_sval = zero;
 799                 return true;
 800         }
 801 
 802         *res = alloc_rl(zero, one);
 803         return true;
 804 }
 805 
 806 static bool handle_logical_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 807 {
 808         sval_t left, right;
 809         int left_known = 0;
 810         int right_known = 0;
 811 
 812         if (implied == RL_EXACT) {
 813                 if (get_value(expr->left, &left))
 814                         left_known = 1;
 815                 if (get_value(expr->right, &right))
 816                         right_known = 1;
 817         } else {
 818                 if (get_implied_value_internal(expr->left, recurse_cnt, &left))
 819                         left_known = 1;
 820                 if (get_implied_value_internal(expr->right, recurse_cnt, &right))
 821                         right_known = 1;
 822         }
 823 
 824         switch (expr->op) {
 825         case SPECIAL_LOGICAL_OR:
 826                 if (left_known && left.value)
 827                         goto one;
 828                 if (right_known && right.value)
 829                         goto one;
 830                 if (left_known && right_known)
 831                         goto zero;
 832                 break;
 833         case SPECIAL_LOGICAL_AND:
 834                 if (left_known && right_known) {
 835                         if (left.value && right.value)
 836                                 goto one;
 837                         goto zero;
 838                 }
 839                 break;
 840         default:
 841                 return false;
 842         }
 843 
 844         if (implied == RL_EXACT)
 845                 return false;
 846 
 847         *res = alloc_rl(zero, one);
 848         return true;
 849 
 850 zero:
 851         *res_sval = zero;
 852         return true;
 853 one:
 854         *res_sval = one;
 855         return true;
 856 }
 857 
 858 static bool handle_conditional_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 859 {
 860         struct expression *cond_true;
 861         struct range_list *true_rl, *false_rl;
 862         struct symbol *type;
 863         int final_pass_orig = final_pass;
 864 
 865         cond_true = expr->cond_true;
 866         if (!cond_true)
 867                 cond_true = expr->conditional;
 868 
 869         if (known_condition_true(expr->conditional))
 870                 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
 871         if (known_condition_false(expr->conditional))
 872                 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
 873 
 874         if (implied == RL_EXACT)
 875                 return false;
 876 
 877         if (implied_condition_true(expr->conditional))
 878                 return get_rl_sval(cond_true, implied, recurse_cnt, res, res_sval);
 879         if (implied_condition_false(expr->conditional))
 880                 return get_rl_sval(expr->cond_false, implied, recurse_cnt, res, res_sval);
 881 
 882         /* this becomes a problem with deeply nested conditional statements */
 883         if (fast_math_only || low_on_memory())
 884                 return false;
 885 
 886         type = get_type(expr);
 887 
 888         __push_fake_cur_stree();
 889         final_pass = 0;
 890         __split_whole_condition(expr->conditional);
 891         true_rl = NULL;
 892         get_rl_internal(cond_true, implied, recurse_cnt, &true_rl);
 893         __push_true_states();
 894         __use_false_states();
 895         false_rl = NULL;
 896         get_rl_internal(expr->cond_false, implied, recurse_cnt, &false_rl);
 897         __merge_true_states();
 898         __free_fake_cur_stree();
 899         final_pass = final_pass_orig;
 900 
 901         if (!true_rl || !false_rl)
 902                 return false;
 903         true_rl = cast_rl(type, true_rl);
 904         false_rl = cast_rl(type, false_rl);
 905 
 906         *res = rl_union(true_rl, false_rl);
 907         return true;
 908 }
 909 
 910 static bool get_fuzzy_max_helper(struct expression *expr, sval_t *max)
 911 {
 912         struct smatch_state *state;
 913         sval_t sval;
 914 
 915         if (get_hard_max(expr, &sval)) {
 916                 *max = sval;
 917                 return true;
 918         }
 919 
 920         state = get_extra_state(expr);
 921         if (!state || !estate_has_fuzzy_max(state))
 922                 return false;
 923         *max = sval_cast(get_type(expr), estate_get_fuzzy_max(state));
 924         return true;
 925 }
 926 
 927 static bool get_fuzzy_min_helper(struct expression *expr, sval_t *min)
 928 {
 929         struct smatch_state *state;
 930         sval_t sval;
 931 
 932         state = get_extra_state(expr);
 933         if (!state || !estate_rl(state))
 934                 return false;
 935 
 936         sval = estate_min(state);
 937         if (sval_is_negative(sval) && sval_is_min(sval))
 938                 return false;
 939 
 940         if (sval_is_max(sval))
 941                 return false;
 942 
 943         *min = sval_cast(get_type(expr), sval);
 944         return true;
 945 }
 946 
 947 int get_const_value(struct expression *expr, sval_t *sval)
 948 {
 949         struct symbol *sym;
 950         sval_t right;
 951 
 952         if (expr->type != EXPR_SYMBOL || !expr->symbol)
 953                 return 0;
 954         sym = expr->symbol;
 955         if (!(sym->ctype.modifiers & MOD_CONST))
 956                 return 0;
 957         if (get_value(sym->initializer, &right)) {
 958                 *sval = sval_cast(get_type(expr), right);
 959                 return 1;
 960         }
 961         return 0;
 962 }
 963 
 964 struct range_list *var_to_absolute_rl(struct expression *expr)
 965 {
 966         struct smatch_state *state;
 967         struct range_list *rl;
 968 
 969         state = get_extra_state(expr);
 970         if (!state || is_whole_rl(estate_rl(state))) {
 971                 state = get_real_absolute_state(expr);
 972                 if (state && state->data && !estate_is_whole(state))
 973                         return clone_rl(estate_rl(state));
 974                 if (get_mtag_rl(expr, &rl))
 975                         return rl;
 976                 if (get_db_type_rl(expr, &rl) && !is_whole_rl(rl))
 977                         return rl;
 978                 return alloc_whole_rl(get_type(expr));
 979         }
 980         /* err on the side of saying things are possible */
 981         if (!estate_rl(state))
 982                 return alloc_whole_rl(get_type(expr));
 983         return clone_rl(estate_rl(state));
 984 }
 985 
 986 static bool handle_variable(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
 987 {
 988         struct smatch_state *state;
 989         struct range_list *rl;
 990         sval_t sval, min, max;
 991         struct symbol *type;
 992 
 993         if (get_const_value(expr, &sval)) {
 994                 *res_sval = sval;
 995                 return true;
 996         }
 997 
 998         if (implied == RL_EXACT)
 999                 return false;
1000 
1001         if (custom_handle_variable) {
1002                 rl = custom_handle_variable(expr);
1003                 if (rl) {
1004                         if (!rl_to_sval(rl, res_sval))
1005                                 *res = rl;
1006                 } else {
1007                         *res = var_to_absolute_rl(expr);
1008                 }
1009                 return true;
1010         }
1011 
1012         if (get_mtag_sval(expr, &sval)) {
1013                 *res_sval = sval;
1014                 return true;
1015         }
1016 
1017         type = get_type(expr);
1018         if (type &&
1019             (type->type == SYM_ARRAY ||
1020              type->type == SYM_FN))
1021                 return handle_address(expr, implied, recurse_cnt, res, res_sval);
1022 
1023         /* FIXME: call rl_to_sval() on the results */
1024 
1025         switch (implied) {
1026         case RL_HARD:
1027         case RL_IMPLIED:
1028         case RL_ABSOLUTE:
1029                 state = get_extra_state(expr);
1030                 if (!state) {
1031                         if (implied == RL_HARD)
1032                                 return false;
1033                         if (get_mtag_rl(expr, res))
1034                                 return true;
1035                         if (get_db_type_rl(expr, res))
1036                                 return true;
1037                         if (is_array(expr) && get_array_rl(expr, res))
1038                                 return true;
1039                         return false;
1040                 }
1041                 if (implied == RL_HARD && !estate_has_hard_max(state))
1042                         return false;
1043                 *res = clone_rl(estate_rl(state));
1044                 return true;
1045         case RL_REAL_ABSOLUTE: {
1046                 struct smatch_state *abs_state;
1047 
1048                 state = get_extra_state(expr);
1049                 abs_state = get_real_absolute_state(expr);
1050 
1051                 if (estate_rl(state) && estate_rl(abs_state)) {
1052                         *res = clone_rl(rl_intersection(estate_rl(state),
1053                                                         estate_rl(abs_state)));
1054                         return true;
1055                 } else if (estate_rl(state)) {
1056                         *res = clone_rl(estate_rl(state));
1057                         return true;
1058                 } else if (estate_is_empty(state)) {
1059                         /*
1060                          * FIXME: we don't handle empty extra states correctly.
1061                          *
1062                          * The real abs rl is supposed to be filtered by the
1063                          * extra state if there is one.  We don't bother keeping
1064                          * the abs state in sync all the time because we know it
1065                          * will be filtered later.
1066                          *
1067                          * It's not totally obvious to me how they should be
1068                          * handled.  Perhaps we should take the whole rl and
1069                          * filter by the imaginary states.  Perhaps we should
1070                          * just go with the empty state.
1071                          *
1072                          * Anyway what we currently do is return NULL here and
1073                          * that gets translated into the whole range in
1074                          * get_real_absolute_rl().
1075                          *
1076                          */
1077                         return false;
1078                 } else if (estate_rl(abs_state)) {
1079                         *res = clone_rl(estate_rl(abs_state));
1080                         return true;
1081                 }
1082 
1083                 if (get_mtag_rl(expr, res))
1084                         return true;
1085                 if (get_db_type_rl(expr, res))
1086                         return true;
1087                 if (is_array(expr) && get_array_rl(expr, res))
1088                         return true;
1089                 return false;
1090         }
1091         case RL_FUZZY:
1092                 if (!get_fuzzy_min_helper(expr, &min))
1093                         min = sval_type_min(get_type(expr));
1094                 if (!get_fuzzy_max_helper(expr, &max))
1095                         return false;
1096                 /* fuzzy ranges are often inverted */
1097                 if (sval_cmp(min, max) > 0) {
1098                         sval = min;
1099                         min = max;
1100                         max = sval;
1101                 }
1102                 *res = alloc_rl(min, max);
1103                 return true;
1104         }
1105         return false;
1106 }
1107 
1108 static sval_t handle_sizeof(struct expression *expr)
1109 {
1110         struct symbol *sym;
1111         sval_t ret;
1112 
1113         ret = sval_blank(expr);
1114         sym = expr->cast_type;
1115         if (!sym) {
1116                 sym = evaluate_expression(expr->cast_expression);
1117                 if (!sym) {
1118                         __silence_warnings_for_stmt = true;
1119                         sym = &int_ctype;
1120                 }
1121 #if 0
1122                 /*
1123                  * Expressions of restricted types will possibly get
1124                  * promoted - check that here.  I'm not sure how this works,
1125                  * the problem is that sizeof(le16) shouldn't be promoted and
1126                  * the original code did that...  Let's if zero this out and
1127                  * see what breaks.
1128                  */
1129 
1130                 if (is_restricted_type(sym)) {
1131                         if (type_bits(sym) < bits_in_int)
1132                                 sym = &int_ctype;
1133                 }
1134 #endif
1135                 if (is_fouled_type(sym))
1136                         sym = &int_ctype;
1137         }
1138         examine_symbol_type(sym);
1139 
1140         ret.type = size_t_ctype;
1141         if (type_bits(sym) <= 0) /* sizeof(void) */ {
1142                 if (get_real_base_type(sym) == &void_ctype)
1143                         ret.value = 1;
1144                 else
1145                         ret.value = 0;
1146         } else
1147                 ret.value = type_bytes(sym);
1148 
1149         return ret;
1150 }
1151 
1152 static bool handle_strlen(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1153 {
1154         struct expression *arg, *tmp;
1155         sval_t tag;
1156         sval_t ret = { .type = &ulong_ctype };
1157         struct range_list *rl;
1158 
1159         arg = get_argument_from_call_expr(expr->args, 0);
1160         if (!arg)
1161                 return false;
1162         if (arg->type == EXPR_STRING) {
1163                 ret.value = arg->string->length - 1;
1164                 *res_sval = ret;
1165                 return true;
1166         }
1167         if (implied == RL_EXACT)
1168                 return false;
1169         if (get_implied_value(arg, &tag) &&
1170             (tmp = fake_string_from_mtag(tag.uvalue))) {
1171                 ret.value = tmp->string->length - 1;
1172                 *res_sval = ret;
1173                 return true;
1174         }
1175 
1176         if (implied == RL_HARD || implied == RL_FUZZY)
1177                 return false;
1178 
1179         if (get_implied_return(expr, &rl)) {
1180                 *res = rl;
1181                 return true;
1182         }
1183 
1184         return false;
1185 }
1186 
1187 static bool handle_builtin_constant_p(struct expression *expr, int implied, int *recurse_cnt, sval_t *res_sval)
1188 {
1189         struct expression *arg;
1190         struct range_list *rl;
1191 
1192         arg = get_argument_from_call_expr(expr->args, 0);
1193         if (get_rl_internal(arg, RL_EXACT, recurse_cnt, &rl))
1194                 *res_sval = one;
1195         else
1196                 *res_sval = zero;
1197         return true;
1198 }
1199 
1200 static bool handle__builtin_choose_expr(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1201 {
1202         struct expression *const_expr, *expr1, *expr2;
1203         sval_t sval;
1204 
1205         const_expr = get_argument_from_call_expr(expr->args, 0);
1206         expr1 = get_argument_from_call_expr(expr->args, 1);
1207         expr2 = get_argument_from_call_expr(expr->args, 2);
1208 
1209         if (!get_value(const_expr, &sval) || !expr1 || !expr2)
1210                 return false;
1211         if (sval.value)
1212                 return get_rl_sval(expr1, implied, recurse_cnt, res, res_sval);
1213         else
1214                 return get_rl_sval(expr2, implied, recurse_cnt, res, res_sval);
1215 }
1216 
1217 static bool handle_call_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1218 {
1219         struct range_list *rl;
1220 
1221         if (sym_name_is("__builtin_constant_p", expr->fn))
1222                 return handle_builtin_constant_p(expr, implied, recurse_cnt, res_sval);
1223 
1224         if (sym_name_is("__builtin_choose_expr", expr->fn))
1225                 return handle__builtin_choose_expr(expr, implied, recurse_cnt, res, res_sval);
1226 
1227         if (sym_name_is("__builtin_expect", expr->fn) ||
1228             sym_name_is("__builtin_bswap16", expr->fn) ||
1229             sym_name_is("__builtin_bswap32", expr->fn) ||
1230             sym_name_is("__builtin_bswap64", expr->fn)) {
1231                 struct expression *arg;
1232 
1233                 arg = get_argument_from_call_expr(expr->args, 0);
1234                 return get_rl_sval(arg, implied, recurse_cnt, res, res_sval);
1235         }
1236 
1237         if (sym_name_is("strlen", expr->fn))
1238                 return handle_strlen(expr, implied, recurse_cnt, res, res_sval);
1239 
1240         if (implied == RL_EXACT || implied == RL_HARD)
1241                 return false;
1242 
1243         if (custom_handle_variable) {
1244                 rl = custom_handle_variable(expr);
1245                 if (rl) {
1246                         *res = rl;
1247                         return true;
1248                 }
1249         }
1250 
1251         /* Ugh...  get_implied_return() sets *rl to NULL on failure */
1252         if (get_implied_return(expr, &rl)) {
1253                 *res = rl;
1254                 return true;
1255         }
1256         rl = db_return_vals(expr);
1257         if (rl) {
1258                 *res = rl;
1259                 return true;
1260         }
1261         return false;
1262 }
1263 
1264 static bool handle_cast(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1265 {
1266         struct range_list *rl;
1267         struct symbol *type;
1268         sval_t sval = {};
1269 
1270         type = get_type(expr);
1271         if (get_rl_sval(expr->cast_expression, implied, recurse_cnt, &rl, &sval)) {
1272                 if (sval.type)
1273                         *res_sval = sval_cast(type, sval);
1274                 else
1275                         *res = cast_rl(type, rl);
1276                 return true;
1277         }
1278         if (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE) {
1279                 *res = alloc_whole_rl(type);
1280                 return true;
1281         }
1282         if (implied == RL_IMPLIED && type &&
1283             type_bits(type) > 0 && type_bits(type) < 32) {
1284                 *res = alloc_whole_rl(type);
1285                 return true;
1286         }
1287         return false;
1288 }
1289 
1290 static bool get_offset_from_down(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1291 {
1292         struct expression *index;
1293         struct symbol *type = expr->in;
1294         struct range_list *rl;
1295         struct symbol *field;
1296         int offset = 0;
1297         sval_t sval = { .type = ssize_t_ctype };
1298         sval_t tmp_sval = {};
1299 
1300         /*
1301          * FIXME:  I don't really know what I'm doing here.  I wish that I
1302          * could just get rid of the __builtin_offset() function and use:
1303          * "&((struct bpf_prog *)NULL)->insns[fprog->len]" instead...
1304          * Anyway, I have done the minimum ammount of work to get that
1305          * expression to work.
1306          *
1307          */
1308 
1309         if (expr->op != '.' || !expr->down ||
1310             expr->down->type != EXPR_OFFSETOF ||
1311             expr->down->op != '[' ||
1312             !expr->down->index)
1313                 return false;
1314 
1315         index = expr->down->index;
1316 
1317         examine_symbol_type(type);
1318         type = get_real_base_type(type);
1319         if (!type)
1320                 return false;
1321         field = find_identifier(expr->ident, type->symbol_list, &offset);
1322         if (!field)
1323                 return false;
1324 
1325         type = get_real_base_type(field);
1326         if (!type || type->type != SYM_ARRAY)
1327                 return false;
1328         type = get_real_base_type(type);
1329 
1330         if (get_implied_value_internal(index, recurse_cnt, &sval)) {
1331                 res_sval->type = ssize_t_ctype;
1332                 res_sval->value = offset + sval.value * type_bytes(type);
1333                 return true;
1334         }
1335 
1336         if (!get_rl_sval(index, implied, recurse_cnt, &rl, &tmp_sval))
1337                 return false;
1338 
1339         /*
1340          * I'm not sure why get_rl_sval() would return an sval when
1341          * get_implied_value_internal() failed but it does when I
1342          * parse drivers/net/ethernet/mellanox/mlx5/core/en/monitor_stats.c
1343          *
1344          */
1345         if (tmp_sval.type) {
1346                 res_sval->type = ssize_t_ctype;
1347                 res_sval->value = offset + sval.value * type_bytes(type);
1348                 return true;
1349         }
1350 
1351         sval.value = type_bytes(type);
1352         rl = rl_binop(rl, '*', alloc_rl(sval, sval));
1353         sval.value = offset;
1354         *res = rl_binop(rl, '+', alloc_rl(sval, sval));
1355         return true;
1356 }
1357 
1358 static bool get_offset_from_in(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1359 {
1360         struct symbol *type = get_real_base_type(expr->in);
1361         struct symbol *field;
1362         int offset = 0;
1363 
1364         if (expr->op != '.' || !type || !expr->ident)
1365                 return false;
1366 
1367         field = find_identifier(expr->ident, type->symbol_list, &offset);
1368         if (!field)
1369                 return false;
1370 
1371         res_sval->type = size_t_ctype;
1372         res_sval->value = offset;
1373 
1374         return true;
1375 }
1376 
1377 static bool handle_offsetof_rl(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *res_sval)
1378 {
1379         if (get_offset_from_down(expr, implied, recurse_cnt, res, res_sval))
1380                 return true;
1381 
1382         if (get_offset_from_in(expr, implied, recurse_cnt, res, res_sval))
1383                 return true;
1384 
1385         evaluate_expression(expr);
1386         if (expr->type == EXPR_VALUE) {
1387                 *res_sval = sval_from_val(expr, expr->value);
1388                 return true;
1389         }
1390         return false;
1391 }
1392 
1393 static bool get_rl_sval(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res, sval_t *sval_res)
1394 {
1395         struct range_list *rl = (void *)-1UL;
1396         struct symbol *type;
1397         sval_t sval = {};
1398 
1399         type = get_type(expr);
1400         expr = strip_parens(expr);
1401         if (!expr)
1402                 return false;
1403 
1404         if (++(*recurse_cnt) >= 200)
1405                 return false;
1406 
1407         switch(expr->type) {
1408         case EXPR_CAST:
1409         case EXPR_FORCE_CAST:
1410         case EXPR_IMPLIED_CAST:
1411                 handle_cast(expr, implied, recurse_cnt, &rl, &sval);
1412                 goto out_cast;
1413         }
1414 
1415         expr = strip_expr(expr);
1416         if (!expr)
1417                 return false;
1418 
1419         switch (expr->type) {
1420         case EXPR_VALUE:
1421                 sval = sval_from_val(expr, expr->value);
1422                 break;
1423         case EXPR_FVALUE:
1424                 sval = sval_from_fval(expr, expr->fvalue);
1425                 break;
1426         case EXPR_PREOP:
1427                 handle_preop_rl(expr, implied, recurse_cnt, &rl, &sval);
1428                 break;
1429         case EXPR_POSTOP:
1430                 get_rl_sval(expr->unop, implied, recurse_cnt, &rl, &sval);
1431                 break;
1432         case EXPR_BINOP:
1433                 handle_binop_rl(expr, implied, recurse_cnt, &rl, &sval);
1434                 break;
1435         case EXPR_COMPARE:
1436                 handle_comparison_rl(expr, implied, recurse_cnt, &rl, &sval);
1437                 break;
1438         case EXPR_LOGICAL:
1439                 handle_logical_rl(expr, implied, recurse_cnt, &rl, &sval);
1440                 break;
1441         case EXPR_PTRSIZEOF:
1442         case EXPR_SIZEOF:
1443                 sval = handle_sizeof(expr);
1444                 break;
1445         case EXPR_SELECT:
1446         case EXPR_CONDITIONAL:
1447                 handle_conditional_rl(expr, implied, recurse_cnt, &rl, &sval);
1448                 break;
1449         case EXPR_CALL:
1450                 handle_call_rl(expr, implied, recurse_cnt, &rl, &sval);
1451                 break;
1452         case EXPR_STRING:
1453                 if (get_mtag_sval(expr, &sval))
1454                         break;
1455                 if (implied == RL_EXACT)
1456                         break;
1457                 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
1458                 break;
1459         case EXPR_OFFSETOF:
1460                 handle_offsetof_rl(expr, implied, recurse_cnt, &rl, &sval);
1461                 break;
1462         case EXPR_ALIGNOF:
1463                 evaluate_expression(expr);
1464                 if (expr->type == EXPR_VALUE)
1465                         sval = sval_from_val(expr, expr->value);
1466                 break;
1467         default:
1468                 handle_variable(expr, implied, recurse_cnt, &rl, &sval);
1469         }
1470 
1471 out_cast:
1472         if (rl == (void *)-1UL)
1473                 rl = NULL;
1474 
1475         if (sval.type || (rl && rl_to_sval(rl, &sval))) {
1476                 *sval_res = sval;
1477                 return true;
1478         }
1479         if (implied == RL_EXACT)
1480                 return false;
1481 
1482         if (rl) {
1483                 *res = rl;
1484                 return true;
1485         }
1486         if (type && (implied == RL_ABSOLUTE || implied == RL_REAL_ABSOLUTE)) {
1487                 *res = alloc_whole_rl(type);
1488                 return true;
1489         }
1490         return false;
1491 }
1492 
1493 static bool get_rl_internal(struct expression *expr, int implied, int *recurse_cnt, struct range_list **res)
1494 {
1495         struct range_list *rl = NULL;
1496         sval_t sval = {};
1497 
1498         if (!get_rl_sval(expr, implied, recurse_cnt, &rl, &sval))
1499                 return false;
1500 
1501         if (sval.type)
1502                 *res = alloc_rl(sval, sval);
1503         else
1504                 *res = rl;
1505         return true;
1506 }
1507 
1508 static bool get_rl_helper(struct expression *expr, int implied, struct range_list **res)
1509 {
1510         struct range_list *rl = NULL;
1511         sval_t sval = {};
1512         int recurse_cnt = 0;
1513 
1514         if (get_value(expr, &sval)) {
1515                 *res = alloc_rl(sval, sval);
1516                 return true;
1517         }
1518 
1519         if (!get_rl_sval(expr, implied, &recurse_cnt, &rl, &sval))
1520                 return false;
1521 
1522         if (sval.type)
1523                 *res = alloc_rl(sval, sval);
1524         else
1525                 *res = rl;
1526         return true;
1527 }
1528 
1529 struct {
1530         struct expression *expr;
1531         sval_t sval;
1532 } cached_results[24];
1533 static int cache_idx;
1534 
1535 void clear_math_cache(void)
1536 {
1537         memset(cached_results, 0, sizeof(cached_results));
1538 }
1539 
1540 void set_fast_math_only(void)
1541 {
1542         fast_math_only++;
1543 }
1544 
1545 void clear_fast_math_only(void)
1546 {
1547         fast_math_only--;
1548 }
1549 
1550 /*
1551  * Don't cache EXPR_VALUE because values are fast already.
1552  *
1553  */
1554 static bool get_value_literal(struct expression *expr, sval_t *res_sval)
1555 {
1556         struct expression *tmp;
1557         int recurse_cnt = 0;
1558 
1559         tmp = strip_expr(expr);
1560         if (!tmp || tmp->type != EXPR_VALUE)
1561                 return false;
1562 
1563         return get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, res_sval);
1564 }
1565 
1566 /* returns 1 if it can get a value literal or else returns 0 */
1567 int get_value(struct expression *expr, sval_t *res_sval)
1568 {
1569         struct range_list *(*orig_custom_fn)(struct expression *expr);
1570         int recurse_cnt = 0;
1571         sval_t sval = {};
1572         int i;
1573 
1574         if (get_value_literal(expr, res_sval))
1575                 return 1;
1576 
1577         /*
1578          * This only handles RL_EXACT because other expr statements can be
1579          * different at different points.  Like the list iterator, for example.
1580          */
1581         for (i = 0; i < ARRAY_SIZE(cached_results); i++) {
1582                 if (expr == cached_results[i].expr) {
1583                         if (cached_results[i].sval.type) {
1584                                 *res_sval = cached_results[i].sval;
1585                                 return true;
1586                         }
1587                         return false;
1588                 }
1589         }
1590 
1591         orig_custom_fn = custom_handle_variable;
1592         custom_handle_variable = NULL;
1593         get_rl_sval(expr, RL_EXACT, &recurse_cnt, NULL, &sval);
1594 
1595         custom_handle_variable = orig_custom_fn;
1596 
1597         cached_results[cache_idx].expr = expr;
1598         cached_results[cache_idx].sval = sval;
1599         cache_idx = (cache_idx + 1) % ARRAY_SIZE(cached_results);
1600 
1601         if (!sval.type)
1602                 return 0;
1603 
1604         *res_sval = sval;
1605         return 1;
1606 }
1607 
1608 static bool get_implied_value_internal(struct expression *expr, int *recurse_cnt, sval_t *res_sval)
1609 {
1610         struct range_list *rl;
1611 
1612         res_sval->type = NULL;
1613 
1614         if (!get_rl_sval(expr, RL_IMPLIED, recurse_cnt, &rl, res_sval))
1615                 return false;
1616         if (!res_sval->type && !rl_to_sval(rl, res_sval))
1617                 return false;
1618         return true;
1619 }
1620 
1621 int get_implied_value(struct expression *expr, sval_t *sval)
1622 {
1623         struct range_list *rl;
1624 
1625         if (!get_rl_helper(expr, RL_IMPLIED, &rl) ||
1626             !rl_to_sval(rl, sval))
1627                 return 0;
1628         return 1;
1629 }
1630 
1631 int get_implied_value_fast(struct expression *expr, sval_t *sval)
1632 {
1633         struct range_list *rl;
1634         static int recurse;
1635         int ret = 0;
1636 
1637         if (recurse)
1638                 return 0;
1639 
1640         recurse = 1;
1641         set_fast_math_only();
1642         if (get_rl_helper(expr, RL_IMPLIED, &rl) &&
1643             rl_to_sval(rl, sval))
1644                 ret = 1;
1645         clear_fast_math_only();
1646         recurse = 0;
1647 
1648         return ret;
1649 }
1650 
1651 int get_implied_min(struct expression *expr, sval_t *sval)
1652 {
1653         struct range_list *rl;
1654 
1655         if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1656                 return 0;
1657         *sval = rl_min(rl);
1658         return 1;
1659 }
1660 
1661 int get_implied_max(struct expression *expr, sval_t *sval)
1662 {
1663         struct range_list *rl;
1664 
1665         if (!get_rl_helper(expr, RL_IMPLIED, &rl) || !rl)
1666                 return 0;
1667         *sval = rl_max(rl);
1668         return 1;
1669 }
1670 
1671 int get_implied_rl(struct expression *expr, struct range_list **rl)
1672 {
1673         if (!get_rl_helper(expr, RL_IMPLIED, rl) || !*rl)
1674                 return 0;
1675         return 1;
1676 }
1677 
1678 static int get_absolute_rl_internal(struct expression *expr, struct range_list **rl, int *recurse_cnt)
1679 {
1680         *rl = NULL;
1681         get_rl_internal(expr, RL_ABSOLUTE, recurse_cnt, rl);
1682         if (!*rl)
1683                 *rl = alloc_whole_rl(get_type(expr));
1684         return 1;
1685 }
1686 
1687 int get_absolute_rl(struct expression *expr, struct range_list **rl)
1688 {
1689         *rl = NULL;
1690          get_rl_helper(expr, RL_ABSOLUTE, rl);
1691         if (!*rl)
1692                 *rl = alloc_whole_rl(get_type(expr));
1693         return 1;
1694 }
1695 
1696 int get_real_absolute_rl(struct expression *expr, struct range_list **rl)
1697 {
1698         *rl = NULL;
1699         get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1700         if (!*rl)
1701                 *rl = alloc_whole_rl(get_type(expr));
1702         return 1;
1703 }
1704 
1705 int custom_get_absolute_rl(struct expression *expr,
1706                            struct range_list *(*fn)(struct expression *expr),
1707                            struct range_list **rl)
1708 {
1709         int ret;
1710 
1711         *rl = NULL;
1712         custom_handle_variable = fn;
1713         ret = get_rl_helper(expr, RL_REAL_ABSOLUTE, rl);
1714         custom_handle_variable = NULL;
1715         return ret;
1716 }
1717 
1718 int get_implied_rl_var_sym(const char *var, struct symbol *sym, struct range_list **rl)
1719 {
1720         struct smatch_state *state;
1721 
1722         state = get_state(SMATCH_EXTRA, var, sym);
1723         *rl = estate_rl(state);
1724         if (*rl)
1725                 return 1;
1726         return 0;
1727 }
1728 
1729 int get_hard_max(struct expression *expr, sval_t *sval)
1730 {
1731         struct range_list *rl;
1732 
1733         if (!get_rl_helper(expr, RL_HARD, &rl) || !rl)
1734                 return 0;
1735         *sval = rl_max(rl);
1736         return 1;
1737 }
1738 
1739 int get_fuzzy_min(struct expression *expr, sval_t *sval)
1740 {
1741         struct range_list *rl;
1742         sval_t tmp;
1743 
1744         if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1745                 return 0;
1746         tmp = rl_min(rl);
1747         if (sval_is_negative(tmp) && sval_is_min(tmp))
1748                 return 0;
1749         *sval = tmp;
1750         return 1;
1751 }
1752 
1753 int get_fuzzy_max(struct expression *expr, sval_t *sval)
1754 {
1755         struct range_list *rl;
1756         sval_t max;
1757 
1758         if (!get_rl_helper(expr, RL_FUZZY, &rl) || !rl)
1759                 return 0;
1760         max = rl_max(rl);
1761         if (max.uvalue > INT_MAX - 10000)
1762                 return 0;
1763         *sval = max;
1764         return 1;
1765 }
1766 
1767 int get_absolute_min(struct expression *expr, sval_t *sval)
1768 {
1769         struct range_list *rl;
1770         struct symbol *type;
1771 
1772         type = get_type(expr);
1773         if (!type)
1774                 type = &llong_ctype;  // FIXME: this is wrong but places assume get type can't fail.
1775         rl = NULL;
1776         get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1777         if (rl)
1778                 *sval = rl_min(rl);
1779         else
1780                 *sval = sval_type_min(type);
1781 
1782         if (sval_cmp(*sval, sval_type_min(type)) < 0)
1783                 *sval = sval_type_min(type);
1784         return 1;
1785 }
1786 
1787 int get_absolute_max(struct expression *expr, sval_t *sval)
1788 {
1789         struct range_list *rl;
1790         struct symbol *type;
1791 
1792         type = get_type(expr);
1793         if (!type)
1794                 type = &llong_ctype;
1795         rl = NULL;
1796         get_rl_helper(expr, RL_REAL_ABSOLUTE, &rl);
1797         if (rl)
1798                 *sval = rl_max(rl);
1799         else
1800                 *sval = sval_type_max(type);
1801 
1802         if (sval_cmp(sval_type_max(type), *sval) < 0)
1803                 *sval = sval_type_max(type);
1804         return 1;
1805 }
1806 
1807 int known_condition_true(struct expression *expr)
1808 {
1809         sval_t tmp;
1810 
1811         if (!expr)
1812                 return 0;
1813 
1814         if (__inline_fn && get_param_num(expr) >= 0) {
1815                 if (get_implied_value(expr, &tmp) && tmp.value)
1816                         return 1;
1817                 return 0;
1818         }
1819 
1820         if (get_value(expr, &tmp) && tmp.value)
1821                 return 1;
1822 
1823         return 0;
1824 }
1825 
1826 int known_condition_false(struct expression *expr)
1827 {
1828         sval_t tmp;
1829 
1830         if (!expr)
1831                 return 0;
1832 
1833         if (__inline_fn && get_param_num(expr) >= 0) {
1834                 if (get_implied_value(expr, &tmp) && tmp.value == 0)
1835                         return 1;
1836                 return 0;
1837         }
1838 
1839         if (expr_is_zero(expr))
1840                 return 1;
1841 
1842         return 0;
1843 }
1844 
1845 int implied_condition_true(struct expression *expr)
1846 {
1847         sval_t tmp;
1848 
1849         if (!expr)
1850                 return 0;
1851 
1852         if (known_condition_true(expr))
1853                 return 1;
1854         if (get_implied_value(expr, &tmp) && tmp.value)
1855                 return 1;
1856 
1857         if (expr->type == EXPR_POSTOP)
1858                 return implied_condition_true(expr->unop);
1859 
1860         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_DECREMENT)
1861                 return implied_not_equal(expr->unop, 1);
1862         if (expr->type == EXPR_PREOP && expr->op == SPECIAL_INCREMENT)
1863                 return implied_not_equal(expr->unop, -1);
1864 
1865         expr = strip_expr(expr);
1866         switch (expr->type) {
1867         case EXPR_COMPARE:
1868                 if (do_comparison(expr) == 1)
1869                         return 1;
1870                 break;
1871         case EXPR_PREOP:
1872                 if (expr->op == '!') {
1873                         if (implied_condition_false(expr->unop))
1874                                 return 1;
1875                         break;
1876                 }
1877                 break;
1878         default:
1879                 if (implied_not_equal(expr, 0) == 1)
1880                         return 1;
1881                 break;
1882         }
1883         return 0;
1884 }
1885 
1886 int implied_condition_false(struct expression *expr)
1887 {
1888         struct expression *tmp;
1889         sval_t sval;
1890 
1891         if (!expr)
1892                 return 0;
1893 
1894         if (known_condition_false(expr))
1895                 return 1;
1896 
1897         switch (expr->type) {
1898         case EXPR_COMPARE:
1899                 if (do_comparison(expr) == 2)
1900                         return 1;
1901         case EXPR_PREOP:
1902                 if (expr->op == '!') {
1903                         if (implied_condition_true(expr->unop))
1904                                 return 1;
1905                         break;
1906                 }
1907                 tmp = strip_expr(expr);
1908                 if (tmp != expr)
1909                         return implied_condition_false(tmp);
1910                 break;
1911         default:
1912                 if (get_implied_value(expr, &sval) && sval.value == 0)
1913                         return 1;
1914                 break;
1915         }
1916         return 0;
1917 }
1918 
1919