1 /*
   2  * Copyright (C) 2008 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 /*
  19  * smatch_extra.c is supposed to track the value of every variable.
  20  *
  21  */
  22 
  23 #define _GNU_SOURCE
  24 #include <string.h>
  25 
  26 #include <stdlib.h>
  27 #include <errno.h>
  28 #ifndef __USE_ISOC99
  29 #define __USE_ISOC99
  30 #endif
  31 #include <limits.h>
  32 #include "parse.h"
  33 #include "smatch.h"
  34 #include "smatch_slist.h"
  35 #include "smatch_extra.h"
  36 
  37 static int my_id;
  38 static int link_id;
  39 extern int check_assigned_expr_id;
  40 
  41 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr);
  42 
  43 struct string_list *__ignored_macros = NULL;
  44 int in_warn_on_macro(void)
  45 {
  46         struct statement *stmt;
  47         char *tmp;
  48         char *macro;
  49 
  50         stmt = get_current_statement();
  51         if (!stmt)
  52                 return 0;
  53         macro = get_macro_name(stmt->pos);
  54         if (!macro)
  55                 return 0;
  56 
  57         FOR_EACH_PTR(__ignored_macros, tmp) {
  58                 if (!strcmp(tmp, macro))
  59                         return 1;
  60         } END_FOR_EACH_PTR(tmp);
  61         return 0;
  62 }
  63 
  64 typedef void (mod_hook)(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state);
  65 DECLARE_PTR_LIST(void_fn_list, mod_hook *);
  66 static struct void_fn_list *extra_mod_hooks;
  67 static struct void_fn_list *extra_nomod_hooks;
  68 
  69 void add_extra_mod_hook(mod_hook *fn)
  70 {
  71         mod_hook **p = malloc(sizeof(mod_hook *));
  72         *p = fn;
  73         add_ptr_list(&extra_mod_hooks, p);
  74 }
  75 
  76 void add_extra_nomod_hook(mod_hook *fn)
  77 {
  78         mod_hook **p = malloc(sizeof(mod_hook *));
  79         *p = fn;
  80         add_ptr_list(&extra_nomod_hooks, p);
  81 }
  82 
  83 void call_extra_hooks(struct void_fn_list *hooks, const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
  84 {
  85         mod_hook **fn;
  86 
  87         FOR_EACH_PTR(hooks, fn) {
  88                 (*fn)(name, sym, expr, state);
  89         } END_FOR_EACH_PTR(fn);
  90 }
  91 
  92 void call_extra_mod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
  93 {
  94         call_extra_hooks(extra_mod_hooks, name, sym, expr, state);
  95 }
  96 
  97 void call_extra_nomod_hooks(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
  98 {
  99         call_extra_hooks(extra_nomod_hooks, name, sym, expr, state);
 100 }
 101 
 102 static void set_union_info(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 103 {
 104         struct symbol *type, *tmp, *inner_type, *inner, *new_type;
 105         struct expression *deref, *member_expr;
 106         struct smatch_state *new;
 107         int offset, inner_offset;
 108         static bool in_recurse;
 109         char *member_name;
 110 
 111         if (__in_fake_assign)
 112                 return;
 113 
 114         if (in_recurse)
 115                 return;
 116         in_recurse = true;
 117 
 118         if (!expr || expr->type != EXPR_DEREF || !expr->member)
 119                 goto done;
 120         offset = get_member_offset_from_deref(expr);
 121         if (offset < 0)
 122                 goto done;
 123 
 124         deref = strip_expr(expr->deref);
 125         type = get_type(deref);
 126         if (type_is_ptr(type))
 127                 type = get_real_base_type(type);
 128         if (!type || type->type != SYM_STRUCT)
 129                 goto done;
 130 
 131         FOR_EACH_PTR(type->symbol_list, tmp) {
 132                 inner_type = get_real_base_type(tmp);
 133                 if (!inner_type || inner_type->type != SYM_UNION)
 134                         continue;
 135 
 136                 inner = first_ptr_list((struct ptr_list *)inner_type->symbol_list);
 137                 if (!inner || !inner->ident)
 138                         continue;
 139 
 140                 inner_offset = get_member_offset(type, inner->ident->name);
 141                 if (inner_offset < offset)
 142                         continue;
 143                 if (inner_offset > offset)
 144                         goto done;
 145 
 146                 FOR_EACH_PTR(inner_type->symbol_list, inner) {
 147                         struct symbol *tmp_type;
 148 
 149                         if (!inner->ident || inner->ident == expr->member)
 150                                 continue;
 151                         tmp_type = get_real_base_type(inner);
 152                         if (tmp_type && tmp_type->type == SYM_STRUCT)
 153                                 continue;
 154                         member_expr = deref;
 155                         if (tmp->ident)
 156                                 member_expr = member_expression(member_expr, '.', tmp->ident);
 157                         member_expr = member_expression(member_expr, expr->op, inner->ident);
 158                         member_name = expr_to_var(member_expr);
 159                         if (!member_name)
 160                                 continue;
 161                         new_type = get_real_base_type(inner);
 162                         new = alloc_estate_rl(cast_rl(new_type, estate_rl(state)));
 163                         set_extra_mod_helper(member_name, sym, member_expr, new);
 164                         free_string(member_name);
 165                 } END_FOR_EACH_PTR(inner);
 166         } END_FOR_EACH_PTR(tmp);
 167 
 168 done:
 169         in_recurse = false;
 170 }
 171 
 172 static bool in_param_set;
 173 void set_extra_mod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 174 {
 175         if (!expr)
 176                 expr = gen_expression_from_name_sym(name, sym);
 177         remove_from_equiv(name, sym);
 178         set_union_info(name, sym, expr, state);
 179         call_extra_mod_hooks(name, sym, expr, state);
 180         update_mtag_data(expr, state);
 181         if (in_param_set &&
 182             estate_is_unknown(state) && !get_state(SMATCH_EXTRA, name, sym))
 183                 return;
 184         set_state(SMATCH_EXTRA, name, sym, state);
 185 }
 186 
 187 static void set_extra_nomod_helper(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 188 {
 189         call_extra_nomod_hooks(name, sym, expr, state);
 190         set_state(SMATCH_EXTRA, name, sym, state);
 191 }
 192 
 193 static char *get_pointed_at(const char *name, struct symbol *sym, struct symbol **new_sym)
 194 {
 195         struct expression *assigned;
 196 
 197         /*
 198          * Imagine we have an assignment: "foo = &addr;" then the other name
 199          * of "*foo" is addr.
 200          */
 201 
 202         if (name[0] != '*')
 203                 return NULL;
 204         if (strcmp(name + 1, sym->ident->name) != 0)
 205                 return NULL;
 206 
 207         assigned = get_assigned_expr_name_sym(sym->ident->name, sym);
 208         if (!assigned)
 209                 return NULL;
 210         assigned = strip_parens(assigned);
 211         if (assigned->type != EXPR_PREOP || assigned->op != '&')
 212                 return NULL;
 213 
 214         return expr_to_var_sym(assigned->unop, new_sym);
 215 }
 216 
 217 char *get_other_name_sym_from_chunk(const char *name, const char *chunk, int len, struct symbol *sym, struct symbol **new_sym)
 218 {
 219         struct expression *assigned;
 220         char *orig_name = NULL;
 221         char buf[256];
 222         char *ret;
 223 
 224         assigned = get_assigned_expr_name_sym(chunk, sym);
 225         if (!assigned)
 226                 return NULL;
 227         if (assigned->type == EXPR_CALL)
 228                 return map_call_to_other_name_sym(name, sym, new_sym);
 229         if (assigned->type == EXPR_PREOP && assigned->op == '&') {
 230 
 231                 orig_name = expr_to_var_sym(assigned, new_sym);
 232                 if (!orig_name || !*new_sym)
 233                         goto free;
 234 
 235                 snprintf(buf, sizeof(buf), "%s.%s", orig_name + 1, name + len);
 236                 ret = alloc_string(buf);
 237                 free_string(orig_name);
 238                 return ret;
 239         }
 240 
 241         orig_name = expr_to_var_sym(assigned, new_sym);
 242         if (!orig_name || !*new_sym)
 243                 goto free;
 244 
 245         snprintf(buf, sizeof(buf), "%s->%s", orig_name, name + len);
 246         ret = alloc_string(buf);
 247         free_string(orig_name);
 248         return ret;
 249 free:
 250         free_string(orig_name);
 251         return NULL;
 252 }
 253 
 254 static char *get_long_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
 255 {
 256         struct expression *tmp;
 257         struct sm_state *sm;
 258         char buf[256];
 259 
 260         /*
 261          * Just prepend the name with a different name/sym and return that.
 262          * For example, if we set "foo->bar = bar;" then the other name
 263          * for "bar->baz" is "foo->bar->baz".  Or if we have "foo = bar;" then
 264          * the other name for "bar" is "foo".  A third option is if we have
 265          * "foo = bar;" then another name for "*bar" is "*foo".
 266          */
 267 
 268         FOR_EACH_MY_SM(check_assigned_expr_id, __get_cur_stree(), sm) {
 269                 tmp = sm->state->data;
 270                 if (!tmp || tmp->type != EXPR_SYMBOL)
 271                         continue;
 272                 if (tmp->symbol == sym)
 273                         goto found;
 274         } END_FOR_EACH_SM(sm);
 275 
 276         return NULL;
 277 
 278 found:
 279         if (!use_stack && name[tmp->symbol->ident->len] != '-')
 280                 return NULL;
 281 
 282         if (name[0] == '*' && strcmp(name + 1, tmp->symbol_name->name) == 0)
 283                 snprintf(buf, sizeof(buf), "*%s", sm->name);
 284         else if (name[tmp->symbol->ident->len] == '-' ||
 285                  name[tmp->symbol->ident->len] == '.')
 286                 snprintf(buf, sizeof(buf), "%s%s", sm->name, name + tmp->symbol->ident->len);
 287         else if (strcmp(name, tmp->symbol_name->name) == 0)
 288                 snprintf(buf, sizeof(buf), "%s", sm->name);
 289         else
 290                 return NULL;
 291 
 292         *new_sym = sm->sym;
 293         return alloc_string(buf);
 294 }
 295 
 296 char *get_other_name_sym_helper(const char *name, struct symbol *sym, struct symbol **new_sym, bool use_stack)
 297 {
 298         char buf[256];
 299         char *ret;
 300         int len;
 301 
 302         *new_sym = NULL;
 303 
 304         if (!sym || !sym->ident)
 305                 return NULL;
 306 
 307         ret = get_pointed_at(name, sym, new_sym);
 308         if (ret)
 309                 return ret;
 310 
 311         ret = map_long_to_short_name_sym(name, sym, new_sym, use_stack);
 312         if (ret)
 313                 return ret;
 314 
 315         len = snprintf(buf, sizeof(buf), "%s", name);
 316         if (len >= sizeof(buf) - 2)
 317                 return NULL;
 318 
 319         while (use_stack && len >= 1) {
 320                 if (buf[len] == '>' && buf[len - 1] == '-') {
 321                         len--;
 322                         buf[len] = '\0';
 323                         ret = get_other_name_sym_from_chunk(name, buf, len + 2, sym, new_sym);
 324                         if (ret)
 325                                 return ret;
 326                 }
 327                 len--;
 328         }
 329 
 330         ret = get_long_name_sym(name, sym, new_sym, use_stack);
 331         if (ret)
 332                 return ret;
 333 
 334         return NULL;
 335 }
 336 
 337 char *get_other_name_sym(const char *name, struct symbol *sym, struct symbol **new_sym)
 338 {
 339         return get_other_name_sym_helper(name, sym, new_sym, true);
 340 }
 341 
 342 char *get_other_name_sym_nostack(const char *name, struct symbol *sym, struct symbol **new_sym)
 343 {
 344         return get_other_name_sym_helper(name, sym, new_sym, false);
 345 }
 346 
 347 void set_extra_mod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 348 {
 349         char *new_name;
 350         struct symbol *new_sym;
 351 
 352         set_extra_mod_helper(name, sym, expr, state);
 353         new_name = get_other_name_sym_nostack(name, sym, &new_sym);
 354         if (new_name && new_sym)
 355                 set_extra_mod_helper(new_name, new_sym, NULL, state);
 356         free_string(new_name);
 357 }
 358 
 359 static struct expression *chunk_get_array_base(struct expression *expr)
 360 {
 361         /*
 362          * The problem with is_array() is that it only returns true for things
 363          * like foo[1] but not for foo[1].bar.
 364          *
 365          */
 366         expr = strip_expr(expr);
 367         while (expr && expr->type == EXPR_DEREF)
 368                 expr = strip_expr(expr->deref);
 369         return get_array_base(expr);
 370 }
 371 
 372 static int chunk_has_array(struct expression *expr)
 373 {
 374         return !!chunk_get_array_base(expr);
 375 }
 376 
 377 static void clear_array_states(struct expression *array)
 378 {
 379         struct sm_state *sm;
 380 
 381         sm = get_sm_state_expr(link_id, array);
 382         if (sm)
 383                 match_link_modify(sm, NULL);
 384 }
 385 
 386 static void set_extra_array_mod(struct expression *expr, struct smatch_state *state)
 387 {
 388         struct expression *array;
 389         struct var_sym_list *vsl;
 390         struct var_sym *vs;
 391         char *name;
 392         struct symbol *sym;
 393 
 394         array = chunk_get_array_base(expr);
 395 
 396         name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
 397         if (!name || !vsl) {
 398                 clear_array_states(array);
 399                 goto free;
 400         }
 401 
 402         FOR_EACH_PTR(vsl, vs) {
 403                 store_link(link_id, vs->var, vs->sym, name, sym);
 404         } END_FOR_EACH_PTR(vs);
 405 
 406         call_extra_mod_hooks(name, sym, expr, state);
 407         set_state(SMATCH_EXTRA, name, sym, state);
 408 free:
 409         free_string(name);
 410 }
 411 
 412 void set_extra_expr_mod(struct expression *expr, struct smatch_state *state)
 413 {
 414         struct symbol *sym;
 415         char *name;
 416 
 417         if (chunk_has_array(expr)) {
 418                 set_extra_array_mod(expr, state);
 419                 return;
 420         }
 421 
 422         expr = strip_expr(expr);
 423         name = expr_to_var_sym(expr, &sym);
 424         if (!name || !sym)
 425                 goto free;
 426         set_extra_mod(name, sym, expr, state);
 427 free:
 428         free_string(name);
 429 }
 430 
 431 void set_extra_nomod(const char *name, struct symbol *sym, struct expression *expr, struct smatch_state *state)
 432 {
 433         char *new_name;
 434         struct symbol *new_sym;
 435         struct relation *rel;
 436         struct smatch_state *orig_state;
 437 
 438         orig_state = get_state(SMATCH_EXTRA, name, sym);
 439 
 440         /* don't save unknown states if leaving it blank is the same */
 441         if (!orig_state && estate_is_unknown(state))
 442                 return;
 443 
 444         new_name = get_other_name_sym(name, sym, &new_sym);
 445         if (new_name && new_sym)
 446                 set_extra_nomod_helper(new_name, new_sym, expr, state);
 447         free_string(new_name);
 448 
 449         if (!estate_related(orig_state)) {
 450                 set_extra_nomod_helper(name, sym, expr, state);
 451                 return;
 452         }
 453 
 454         set_related(state, estate_related(orig_state));
 455         FOR_EACH_PTR(estate_related(orig_state), rel) {
 456                 struct smatch_state *estate;
 457 
 458                 estate = get_state(SMATCH_EXTRA, rel->name, rel->sym);
 459                 if (!estate)
 460                         continue;
 461                 set_extra_nomod_helper(rel->name, rel->sym, expr, clone_estate_cast(estate_type(estate), state));
 462         } END_FOR_EACH_PTR(rel);
 463 }
 464 
 465 void set_extra_nomod_vsl(const char *name, struct symbol *sym, struct var_sym_list *vsl, struct expression *expr, struct smatch_state *state)
 466 {
 467         struct var_sym *vs;
 468 
 469         FOR_EACH_PTR(vsl, vs) {
 470                 store_link(link_id, vs->var, vs->sym, name, sym);
 471         } END_FOR_EACH_PTR(vs);
 472 
 473         set_extra_nomod(name, sym, expr, state);
 474 }
 475 
 476 /*
 477  * This is for return_implies_state() hooks which modify a SMATCH_EXTRA state
 478  */
 479 void set_extra_expr_nomod(struct expression *expr, struct smatch_state *state)
 480 {
 481         struct var_sym_list *vsl;
 482         struct var_sym *vs;
 483         char *name;
 484         struct symbol *sym;
 485 
 486         name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
 487         if (!name || !vsl)
 488                 goto free;
 489         FOR_EACH_PTR(vsl, vs) {
 490                 store_link(link_id, vs->var, vs->sym, name, sym);
 491         } END_FOR_EACH_PTR(vs);
 492 
 493         set_extra_nomod(name, sym, expr, state);
 494 free:
 495         free_string(name);
 496 }
 497 
 498 static void set_extra_true_false(const char *name, struct symbol *sym,
 499                         struct smatch_state *true_state,
 500                         struct smatch_state *false_state)
 501 {
 502         char *new_name;
 503         struct symbol *new_sym;
 504         struct relation *rel;
 505         struct smatch_state *orig_state;
 506 
 507         if (!true_state && !false_state)
 508                 return;
 509 
 510         if (in_warn_on_macro())
 511                 return;
 512 
 513         new_name = get_other_name_sym(name, sym, &new_sym);
 514         if (new_name && new_sym)
 515                 set_true_false_states(SMATCH_EXTRA, new_name, new_sym, true_state, false_state);
 516         free_string(new_name);
 517 
 518         orig_state = get_state(SMATCH_EXTRA, name, sym);
 519 
 520         if (!estate_related(orig_state)) {
 521                 set_true_false_states(SMATCH_EXTRA, name, sym, true_state, false_state);
 522                 return;
 523         }
 524 
 525         if (true_state)
 526                 set_related(true_state, estate_related(orig_state));
 527         if (false_state)
 528                 set_related(false_state, estate_related(orig_state));
 529 
 530         FOR_EACH_PTR(estate_related(orig_state), rel) {
 531                 set_true_false_states(SMATCH_EXTRA, rel->name, rel->sym,
 532                                 true_state, false_state);
 533         } END_FOR_EACH_PTR(rel);
 534 }
 535 
 536 static void set_extra_chunk_true_false(struct expression *expr,
 537                                        struct smatch_state *true_state,
 538                                        struct smatch_state *false_state)
 539 {
 540         struct var_sym_list *vsl;
 541         struct var_sym *vs;
 542         struct symbol *type;
 543         char *name;
 544         struct symbol *sym;
 545 
 546         if (in_warn_on_macro())
 547                 return;
 548 
 549         type = get_type(expr);
 550         if (!type)
 551                 return;
 552 
 553         name = expr_to_chunk_sym_vsl(expr, &sym, &vsl);
 554         if (!name || !vsl)
 555                 goto free;
 556         FOR_EACH_PTR(vsl, vs) {
 557                 store_link(link_id, vs->var, vs->sym, name, sym);
 558         } END_FOR_EACH_PTR(vs);
 559 
 560         set_true_false_states(SMATCH_EXTRA, name, sym,
 561                               clone_estate(true_state),
 562                               clone_estate(false_state));
 563 free:
 564         free_string(name);
 565 }
 566 
 567 static void set_extra_expr_true_false(struct expression *expr,
 568                 struct smatch_state *true_state,
 569                 struct smatch_state *false_state)
 570 {
 571         char *name;
 572         struct symbol *sym;
 573         sval_t sval;
 574 
 575         if (!true_state && !false_state)
 576                 return;
 577 
 578         if (get_value(expr, &sval))
 579                 return;
 580 
 581         expr = strip_expr(expr);
 582         name = expr_to_var_sym(expr, &sym);
 583         if (!name || !sym) {
 584                 free_string(name);
 585                 set_extra_chunk_true_false(expr, true_state, false_state);
 586                 return;
 587         }
 588         set_extra_true_false(name, sym, true_state, false_state);
 589         free_string(name);
 590 }
 591 
 592 static int get_countdown_info(struct expression *condition, struct expression **unop, int *op, sval_t *right)
 593 {
 594         struct expression *unop_expr;
 595         int comparison;
 596         sval_t limit;
 597 
 598         right->type = &int_ctype;
 599         right->value = 0;
 600 
 601         condition = strip_expr(condition);
 602 
 603         if (condition->type == EXPR_COMPARE) {
 604                 comparison = remove_unsigned_from_comparison(condition->op);
 605 
 606                 if (comparison != SPECIAL_GTE && comparison != '>')
 607                         return 0;
 608                 if (!get_value(condition->right, &limit))
 609                         return 0;
 610 
 611                 unop_expr = condition->left;
 612                 if (unop_expr->type != EXPR_PREOP && unop_expr->type != EXPR_POSTOP)
 613                         return 0;
 614                 if (unop_expr->op != SPECIAL_DECREMENT)
 615                         return 0;
 616 
 617                 *unop = unop_expr;
 618                 *op = comparison;
 619                 *right = limit;
 620 
 621                 return 1;
 622         }
 623 
 624         if (condition->type != EXPR_PREOP && condition->type != EXPR_POSTOP)
 625                 return 0;
 626         if (condition->op != SPECIAL_DECREMENT)
 627                 return 0;
 628 
 629         *unop = condition;
 630         *op = '>';
 631 
 632         return 1;
 633 }
 634 
 635 static struct sm_state *handle_canonical_while_count_down(struct statement *loop)
 636 {
 637         struct expression *iter_var;
 638         struct expression *condition, *unop;
 639         struct symbol *type;
 640         struct sm_state *sm;
 641         struct smatch_state *estate;
 642         int op;
 643         sval_t start, right;
 644 
 645         right.type = &int_ctype;
 646         right.value = 0;
 647 
 648         condition = strip_expr(loop->iterator_pre_condition);
 649         if (!condition)
 650                 return NULL;
 651 
 652         if (!get_countdown_info(condition, &unop, &op, &right))
 653                 return NULL;
 654 
 655         iter_var = unop->unop;
 656 
 657         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 658         if (!sm)
 659                 return NULL;
 660         if (sval_cmp(estate_min(sm->state), right) < 0)
 661                 return NULL;
 662         start = estate_max(sm->state);
 663 
 664         type = get_type(iter_var);
 665         right = sval_cast(type, right);
 666         start = sval_cast(type, start);
 667 
 668         if  (sval_cmp(start, right) <= 0)
 669                 return NULL;
 670         if (!sval_is_max(start))
 671                 start.value--;
 672 
 673         if (op == SPECIAL_GTE)
 674                 right.value--;
 675 
 676         if (unop->type == EXPR_PREOP) {
 677                 right.value++;
 678                 estate = alloc_estate_range(right, start);
 679                 if (estate_has_hard_max(sm->state))
 680                         estate_set_hard_max(estate);
 681                 estate_copy_fuzzy_max(estate, sm->state);
 682                 set_extra_expr_mod(iter_var, estate);
 683         }
 684         if (unop->type == EXPR_POSTOP) {
 685                 estate = alloc_estate_range(right, start);
 686                 if (estate_has_hard_max(sm->state))
 687                         estate_set_hard_max(estate);
 688                 estate_copy_fuzzy_max(estate, sm->state);
 689                 set_extra_expr_mod(iter_var, estate);
 690         }
 691         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 692 }
 693 
 694 static struct sm_state *handle_canonical_for_inc(struct expression *iter_expr,
 695                                                 struct expression *condition)
 696 {
 697         struct expression *iter_var;
 698         struct sm_state *sm;
 699         struct smatch_state *estate;
 700         sval_t start, end, max;
 701         struct symbol *type;
 702 
 703         iter_var = iter_expr->unop;
 704         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 705         if (!sm)
 706                 return NULL;
 707         if (!estate_get_single_value(sm->state, &start))
 708                 return NULL;
 709         if (!get_implied_value(condition->right, &end))
 710                 return NULL;
 711 
 712         if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
 713                 return NULL;
 714 
 715         switch (condition->op) {
 716         case SPECIAL_UNSIGNED_LT:
 717         case SPECIAL_NOTEQUAL:
 718         case '<':
 719                 if (!sval_is_min(end))
 720                         end.value--;
 721                 break;
 722         case SPECIAL_UNSIGNED_LTE:
 723         case SPECIAL_LTE:
 724                 break;
 725         default:
 726                 return NULL;
 727         }
 728         if (sval_cmp(end, start) < 0)
 729                 return NULL;
 730         type = get_type(iter_var);
 731         start = sval_cast(type, start);
 732         end = sval_cast(type, end);
 733         estate = alloc_estate_range(start, end);
 734         if (get_hard_max(condition->right, &max)) {
 735                 if (!get_macro_name(condition->pos))
 736                         estate_set_hard_max(estate);
 737                 if (condition->op == '<' ||
 738                     condition->op == SPECIAL_UNSIGNED_LT ||
 739                     condition->op == SPECIAL_NOTEQUAL)
 740                         max.value--;
 741                 max = sval_cast(type, max);
 742                 estate_set_fuzzy_max(estate, max);
 743         }
 744         set_extra_expr_mod(iter_var, estate);
 745         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 746 }
 747 
 748 static struct sm_state *handle_canonical_for_dec(struct expression *iter_expr,
 749                                                 struct expression *condition)
 750 {
 751         struct expression *iter_var;
 752         struct sm_state *sm;
 753         struct smatch_state *estate;
 754         sval_t start, end;
 755 
 756         iter_var = iter_expr->unop;
 757         sm = get_sm_state_expr(SMATCH_EXTRA, iter_var);
 758         if (!sm)
 759                 return NULL;
 760         if (!estate_get_single_value(sm->state, &start))
 761                 return NULL;
 762         if (!get_implied_min(condition->right, &end))
 763                 end = sval_type_min(get_type(iter_var));
 764         end = sval_cast(estate_type(sm->state), end);
 765         if (get_sm_state_expr(SMATCH_EXTRA, condition->left) != sm)
 766                 return NULL;
 767 
 768         switch (condition->op) {
 769         case SPECIAL_NOTEQUAL:
 770         case '>':
 771                 if (!sval_is_max(end))
 772                         end.value++;
 773                 break;
 774         case SPECIAL_GTE:
 775                 break;
 776         default:
 777                 return NULL;
 778         }
 779         if (sval_cmp(end, start) > 0)
 780                 return NULL;
 781         estate = alloc_estate_range(end, start);
 782         estate_set_hard_max(estate);
 783         estate_set_fuzzy_max(estate, estate_get_fuzzy_max(estate));
 784         set_extra_expr_mod(iter_var, estate);
 785         return get_sm_state_expr(SMATCH_EXTRA, iter_var);
 786 }
 787 
 788 static struct sm_state *handle_canonical_for_loops(struct statement *loop)
 789 {
 790         struct expression *iter_expr;
 791         struct expression *condition;
 792 
 793         if (!loop->iterator_post_statement)
 794                 return NULL;
 795         if (loop->iterator_post_statement->type != STMT_EXPRESSION)
 796                 return NULL;
 797         iter_expr = loop->iterator_post_statement->expression;
 798         if (!loop->iterator_pre_condition)
 799                 return NULL;
 800         if (loop->iterator_pre_condition->type != EXPR_COMPARE)
 801                 return NULL;
 802         condition = loop->iterator_pre_condition;
 803 
 804         if (iter_expr->op == SPECIAL_INCREMENT)
 805                 return handle_canonical_for_inc(iter_expr, condition);
 806         if (iter_expr->op == SPECIAL_DECREMENT)
 807                 return handle_canonical_for_dec(iter_expr, condition);
 808         return NULL;
 809 }
 810 
 811 struct sm_state *__extra_handle_canonical_loops(struct statement *loop, struct stree **stree)
 812 {
 813         struct sm_state *ret;
 814 
 815         /*
 816          * Canonical loops are a hack.  The proper way to handle this is to
 817          * use two passes, but unfortunately, doing two passes makes parsing
 818          * code twice as slow.
 819          *
 820          * What we do is we set the inside state here, which overwrites whatever
 821          * __extra_match_condition() does.  Then we set the outside state in
 822          * __extra_pre_loop_hook_after().
 823          *
 824          */
 825         __push_fake_cur_stree();
 826         if (!loop->iterator_post_statement)
 827                 ret = handle_canonical_while_count_down(loop);
 828         else
 829                 ret = handle_canonical_for_loops(loop);
 830         *stree = __pop_fake_cur_stree();
 831         return ret;
 832 }
 833 
 834 int __iterator_unchanged(struct sm_state *sm)
 835 {
 836         if (!sm)
 837                 return 0;
 838         if (get_sm_state(my_id, sm->name, sm->sym) == sm)
 839                 return 1;
 840         return 0;
 841 }
 842 
 843 static void while_count_down_after(struct sm_state *sm, struct expression *condition)
 844 {
 845         struct expression *unop;
 846         int op;
 847         sval_t limit, after_value;
 848 
 849         if (!get_countdown_info(condition, &unop, &op, &limit))
 850                 return;
 851         after_value = estate_min(sm->state);
 852         after_value.value--;
 853         set_extra_mod(sm->name, sm->sym, condition->unop, alloc_estate_sval(after_value));
 854 }
 855 
 856 void __extra_pre_loop_hook_after(struct sm_state *sm,
 857                                 struct statement *iterator,
 858                                 struct expression *condition)
 859 {
 860         struct expression *iter_expr;
 861         sval_t limit;
 862         struct smatch_state *state;
 863 
 864         if (!iterator) {
 865                 while_count_down_after(sm, condition);
 866                 return;
 867         }
 868 
 869         iter_expr = iterator->expression;
 870 
 871         if (condition->type != EXPR_COMPARE)
 872                 return;
 873         if (iter_expr->op == SPECIAL_INCREMENT) {
 874                 limit = sval_binop(estate_max(sm->state), '+',
 875                                    sval_type_val(estate_type(sm->state), 1));
 876         } else {
 877                 limit = sval_binop(estate_min(sm->state), '-',
 878                                    sval_type_val(estate_type(sm->state), 1));
 879         }
 880         limit = sval_cast(estate_type(sm->state), limit);
 881         if (!estate_has_hard_max(sm->state) && !__has_breaks()) {
 882                 if (iter_expr->op == SPECIAL_INCREMENT)
 883                         state = alloc_estate_range(estate_min(sm->state), limit);
 884                 else
 885                         state = alloc_estate_range(limit, estate_max(sm->state));
 886         } else {
 887                 state = alloc_estate_sval(limit);
 888         }
 889         if (!estate_has_hard_max(sm->state)) {
 890                 estate_clear_hard_max(state);
 891         }
 892         if (estate_has_fuzzy_max(sm->state)) {
 893                 sval_t hmax = estate_get_fuzzy_max(sm->state);
 894                 sval_t max = estate_max(sm->state);
 895 
 896                 if (sval_cmp(hmax, max) != 0)
 897                         estate_clear_fuzzy_max(state);
 898         } else if (!estate_has_fuzzy_max(sm->state)) {
 899                 estate_clear_fuzzy_max(state);
 900         }
 901 
 902         set_extra_mod(sm->name, sm->sym, iter_expr, state);
 903 }
 904 
 905 static bool get_global_rl(const char *name, struct symbol *sym, struct range_list **rl)
 906 {
 907         struct expression *expr;
 908 
 909         if (!sym || !(sym->ctype.modifiers & MOD_TOPLEVEL) || !sym->ident)
 910                 return false;
 911         if (strcmp(sym->ident->name, name) != 0)
 912                 return false;
 913 
 914         expr = symbol_expression(sym);
 915         return get_implied_rl(expr, rl);
 916 }
 917 
 918 static struct stree *unmatched_stree;
 919 static struct smatch_state *unmatched_state(struct sm_state *sm)
 920 {
 921         struct smatch_state *state;
 922         struct range_list *rl;
 923 
 924         if (unmatched_stree) {
 925                 state = get_state_stree(unmatched_stree, SMATCH_EXTRA, sm->name, sm->sym);
 926                 if (state)
 927                         return state;
 928         }
 929         if (parent_is_gone_var_sym(sm->name, sm->sym))
 930                 return alloc_estate_empty();
 931         if (get_global_rl(sm->name, sm->sym, &rl))
 932                 return alloc_estate_rl(rl);
 933         return alloc_estate_whole(estate_type(sm->state));
 934 }
 935 
 936 static void clear_the_pointed_at(struct expression *expr)
 937 {
 938         struct stree *stree;
 939         char *name;
 940         struct symbol *sym;
 941         struct sm_state *tmp;
 942 
 943         name = expr_to_var_sym(expr, &sym);
 944         if (!name || !sym)
 945                 goto free;
 946 
 947         stree = __get_cur_stree();
 948         FOR_EACH_MY_SM(SMATCH_EXTRA, stree, tmp) {
 949                 if (tmp->name[0] != '*')
 950                         continue;
 951                 if (tmp->sym != sym)
 952                         continue;
 953                 if (strcmp(tmp->name + 1, name) != 0)
 954                         continue;
 955                 set_extra_mod(tmp->name, tmp->sym, expr, alloc_estate_whole(estate_type(tmp->state)));
 956         } END_FOR_EACH_SM(tmp);
 957 
 958 free:
 959         free_string(name);
 960 }
 961 
 962 static int is_const_param(struct expression *expr, int param)
 963 {
 964         struct symbol *type;
 965 
 966         type = get_arg_type(expr, param);
 967         if (!type)
 968                 return 0;
 969         if (type->ctype.modifiers & MOD_CONST)
 970                 return 1;
 971         return 0;
 972 }
 973 
 974 static void match_function_call(struct expression *expr)
 975 {
 976         struct expression *arg;
 977         struct expression *tmp;
 978         int param = -1;
 979 
 980         /* if we have the db this is handled in smatch_function_hooks.c */
 981         if (!option_no_db)
 982                 return;
 983         if (inlinable(expr->fn))
 984                 return;
 985 
 986         FOR_EACH_PTR(expr->args, arg) {
 987                 param++;
 988                 if (is_const_param(expr->fn, param))
 989                         continue;
 990                 tmp = strip_expr(arg);
 991                 if (tmp->type == EXPR_PREOP && tmp->op == '&')
 992                         set_extra_expr_mod(tmp->unop, alloc_estate_whole(get_type(tmp->unop)));
 993                 else
 994                         clear_the_pointed_at(tmp);
 995         } END_FOR_EACH_PTR(arg);
 996 }
 997 
 998 int values_fit_type(struct expression *left, struct expression *right)
 999 {
1000         struct range_list *rl;
1001         struct symbol *type;
1002 
1003         type = get_type(left);
1004         if (!type)
1005                 return 0;
1006         get_absolute_rl(right, &rl);
1007         if (type == rl_type(rl))
1008                 return 1;
1009         if (type_unsigned(type) && sval_is_negative(rl_min(rl)))
1010                 return 0;
1011         if (sval_cmp(sval_type_min(type), rl_min(rl)) > 0)
1012                 return 0;
1013         if (sval_cmp(sval_type_max(type), rl_max(rl)) < 0)
1014                 return 0;
1015         return 1;
1016 }
1017 
1018 static void save_chunk_info(struct expression *left, struct expression *right)
1019 {
1020         struct var_sym_list *vsl;
1021         struct var_sym *vs;
1022         struct expression *add_expr;
1023         struct symbol *type;
1024         sval_t sval;
1025         char *name;
1026         struct symbol *sym;
1027 
1028         if (right->type != EXPR_BINOP || right->op != '-')
1029                 return;
1030         if (!get_value(right->left, &sval))
1031                 return;
1032         if (!expr_to_sym(right->right))
1033                 return;
1034 
1035         add_expr = binop_expression(left, '+', right->right);
1036         type = get_type(add_expr);
1037         if (!type)
1038                 return;
1039         name = expr_to_chunk_sym_vsl(add_expr, &sym, &vsl);
1040         if (!name || !vsl)
1041                 goto free;
1042         FOR_EACH_PTR(vsl, vs) {
1043                 store_link(link_id, vs->var, vs->sym, name, sym);
1044         } END_FOR_EACH_PTR(vs);
1045 
1046         set_state(SMATCH_EXTRA, name, sym, alloc_estate_sval(sval_cast(type, sval)));
1047 free:
1048         free_string(name);
1049 }
1050 
1051 static void do_array_assign(struct expression *left, int op, struct expression *right)
1052 {
1053         struct range_list *rl;
1054 
1055         if (op == '=') {
1056                 get_absolute_rl(right, &rl);
1057                 rl = cast_rl(get_type(left), rl);
1058         } else {
1059                 rl = alloc_whole_rl(get_type(left));
1060         }
1061 
1062         set_extra_array_mod(left, alloc_estate_rl(rl));
1063 }
1064 
1065 static void match_vanilla_assign(struct expression *left, struct expression *right)
1066 {
1067         struct range_list *orig_rl = NULL;
1068         struct range_list *rl = NULL;
1069         struct symbol *right_sym;
1070         struct symbol *left_type;
1071         struct symbol *right_type;
1072         char *right_name = NULL;
1073         struct symbol *sym;
1074         char *name;
1075         sval_t sval, max;
1076         struct smatch_state *state;
1077         int comparison;
1078 
1079         if (is_struct(left))
1080                 return;
1081 
1082         save_chunk_info(left, right);
1083 
1084         name = expr_to_var_sym(left, &sym);
1085         if (!name) {
1086                 if (chunk_has_array(left))
1087                         do_array_assign(left, '=', right);
1088                 return;
1089         }
1090 
1091         left_type = get_type(left);
1092         right_type = get_type(right);
1093 
1094         right_name = expr_to_var_sym(right, &right_sym);
1095 
1096         if (!__in_fake_assign &&
1097             !(right->type == EXPR_PREOP && right->op == '&') &&
1098             right_name && right_sym &&
1099             values_fit_type(left, strip_expr(right)) &&
1100             !has_symbol(right, sym)) {
1101                 set_equiv(left, right);
1102                 goto free;
1103         }
1104 
1105         if (get_implied_value(right, &sval)) {
1106                 state = alloc_estate_sval(sval_cast(left_type, sval));
1107                 goto done;
1108         }
1109 
1110         if (__in_fake_assign) {
1111                 struct smatch_state *right_state;
1112                 sval_t sval;
1113 
1114                 if (get_value(right, &sval)) {
1115                         sval = sval_cast(left_type, sval);
1116                         state = alloc_estate_sval(sval);
1117                         goto done;
1118                 }
1119 
1120                 right_state = get_state(SMATCH_EXTRA, right_name, right_sym);
1121                 if (right_state) {
1122                         /* simple assignment */
1123                         state = clone_estate(right_state);
1124                         goto done;
1125                 }
1126 
1127                 state = alloc_estate_rl(alloc_whole_rl(left_type));
1128                 goto done;
1129         }
1130 
1131         comparison = get_comparison_no_extra(left, right);
1132         if (comparison) {
1133                 comparison = flip_comparison(comparison);
1134                 get_implied_rl(left, &orig_rl);
1135         }
1136 
1137         if (get_implied_rl(right, &rl)) {
1138                 rl = cast_rl(left_type, rl);
1139                 if (orig_rl)
1140                         filter_by_comparison(&rl, comparison, orig_rl);
1141                 state = alloc_estate_rl(rl);
1142                 if (get_hard_max(right, &max)) {
1143                         estate_set_hard_max(state);
1144                         estate_set_fuzzy_max(state, max);
1145                 }
1146         } else {
1147                 rl = alloc_whole_rl(right_type);
1148                 rl = cast_rl(left_type, rl);
1149                 if (orig_rl)
1150                         filter_by_comparison(&rl, comparison, orig_rl);
1151                 state = alloc_estate_rl(rl);
1152         }
1153 
1154 done:
1155         set_extra_mod(name, sym, left, state);
1156 free:
1157         free_string(right_name);
1158 }
1159 
1160 static void match_assign(struct expression *expr)
1161 {
1162         struct range_list *rl = NULL;
1163         struct expression *left;
1164         struct expression *right;
1165         struct expression *binop_expr;
1166         struct symbol *left_type;
1167         struct symbol *sym;
1168         char *name;
1169 
1170         left = strip_expr(expr->left);
1171 
1172         right = strip_parens(expr->right);
1173         if (right->type == EXPR_CALL && sym_name_is("__builtin_expect", right->fn))
1174                 right = get_argument_from_call_expr(right->args, 0);
1175         while (right->type == EXPR_ASSIGNMENT && right->op == '=')
1176                 right = strip_parens(right->left);
1177 
1178         if (expr->op == '=' && is_condition(expr->right))
1179                 return; /* handled in smatch_condition.c */
1180         if (expr->op == '=' && right->type == EXPR_CALL)
1181                 return; /* handled in smatch_function_hooks.c */
1182         if (expr->op == '=') {
1183                 match_vanilla_assign(left, right);
1184                 return;
1185         }
1186 
1187         name = expr_to_var_sym(left, &sym);
1188         if (!name)
1189                 return;
1190 
1191         left_type = get_type(left);
1192 
1193         switch (expr->op) {
1194         case SPECIAL_ADD_ASSIGN:
1195         case SPECIAL_SUB_ASSIGN:
1196         case SPECIAL_AND_ASSIGN:
1197         case SPECIAL_MOD_ASSIGN:
1198         case SPECIAL_SHL_ASSIGN:
1199         case SPECIAL_SHR_ASSIGN:
1200         case SPECIAL_OR_ASSIGN:
1201         case SPECIAL_XOR_ASSIGN:
1202         case SPECIAL_MUL_ASSIGN:
1203         case SPECIAL_DIV_ASSIGN:
1204                 binop_expr = binop_expression(expr->left,
1205                                               op_remove_assign(expr->op),
1206                                               expr->right);
1207                 get_absolute_rl(binop_expr, &rl);
1208                 rl = cast_rl(left_type, rl);
1209                 if (inside_loop()) {
1210                         if (expr->op == SPECIAL_ADD_ASSIGN)
1211                                 add_range(&rl, rl_max(rl), sval_type_max(rl_type(rl)));
1212 
1213                         if (expr->op == SPECIAL_SUB_ASSIGN &&
1214                             !sval_is_negative(rl_min(rl))) {
1215                                 sval_t zero = { .type = rl_type(rl) };
1216 
1217                                 add_range(&rl, rl_min(rl), zero);
1218                         }
1219                 }
1220                 set_extra_mod(name, sym, left, alloc_estate_rl(rl));
1221                 goto free;
1222         }
1223         set_extra_mod(name, sym, left, alloc_estate_whole(left_type));
1224 free:
1225         free_string(name);
1226 }
1227 
1228 static struct smatch_state *increment_state(struct smatch_state *state)
1229 {
1230         sval_t min = estate_min(state);
1231         sval_t max = estate_max(state);
1232 
1233         if (!estate_rl(state))
1234                 return NULL;
1235 
1236         if (inside_loop())
1237                 max = sval_type_max(max.type);
1238 
1239         if (!sval_is_min(min) && !sval_is_max(min))
1240                 min.value++;
1241         if (!sval_is_min(max) && !sval_is_max(max))
1242                 max.value++;
1243         return alloc_estate_range(min, max);
1244 }
1245 
1246 static struct smatch_state *decrement_state(struct smatch_state *state)
1247 {
1248         sval_t min = estate_min(state);
1249         sval_t max = estate_max(state);
1250 
1251         if (!estate_rl(state))
1252                 return NULL;
1253 
1254         if (inside_loop())
1255                 min = sval_type_min(min.type);
1256 
1257         if (!sval_is_min(min) && !sval_is_max(min))
1258                 min.value--;
1259         if (!sval_is_min(max) && !sval_is_max(max))
1260                 max.value--;
1261         return alloc_estate_range(min, max);
1262 }
1263 
1264 static void clear_pointed_at_state(struct expression *expr)
1265 {
1266         struct symbol *type;
1267 
1268         /*
1269          * ALERT: This is sort of a mess.  If it's is a struct assigment like
1270          * "foo = bar;", then that's handled by smatch_struct_assignment.c.
1271          * the same thing for p++ where "p" is a struct.  Most modifications
1272          * are handled by the assignment hook or the db.  Smatch_extra.c doesn't
1273          * use smatch_modification.c because we have to get the ordering right
1274          * or something.  So if you have p++ where p is a pointer to a standard
1275          * c type then we handle that here.  What a mess.
1276          */
1277         expr = strip_expr(expr);
1278         type = get_type(expr);
1279         if (!type || type->type != SYM_PTR)
1280                 return;
1281         type = get_real_base_type(type);
1282         if (!type || type->type != SYM_BASETYPE)
1283                 return;
1284         set_extra_expr_nomod(deref_expression(expr), alloc_estate_whole(type));
1285 }
1286 
1287 static void unop_expr(struct expression *expr)
1288 {
1289         struct smatch_state *state;
1290 
1291         if (expr->smatch_flags & Handled)
1292                 return;
1293 
1294         switch (expr->op) {
1295         case SPECIAL_INCREMENT:
1296                 state = get_state_expr(SMATCH_EXTRA, expr->unop);
1297                 state = increment_state(state);
1298                 if (!state)
1299                         state = alloc_estate_whole(get_type(expr));
1300                 set_extra_expr_mod(expr->unop, state);
1301                 clear_pointed_at_state(expr->unop);
1302                 break;
1303         case SPECIAL_DECREMENT:
1304                 state = get_state_expr(SMATCH_EXTRA, expr->unop);
1305                 state = decrement_state(state);
1306                 if (!state)
1307                         state = alloc_estate_whole(get_type(expr));
1308                 set_extra_expr_mod(expr->unop, state);
1309                 clear_pointed_at_state(expr->unop);
1310                 break;
1311         default:
1312                 return;
1313         }
1314 }
1315 
1316 static void asm_expr(struct statement *stmt)
1317 {
1318 
1319         struct expression *expr;
1320         struct symbol *type;
1321 
1322         FOR_EACH_PTR(stmt->asm_outputs, expr) {
1323                 if (expr->type != EXPR_ASM_OPERAND) {
1324                         sm_perror("unexpected asm param type %d", expr->type);
1325                         continue;
1326                 }
1327                 type = get_type(strip_expr(expr->expr));
1328                 set_extra_expr_mod(expr->expr, alloc_estate_whole(type));
1329         } END_FOR_EACH_PTR(expr);
1330 }
1331 
1332 static void check_dereference(struct expression *expr)
1333 {
1334         struct smatch_state *state;
1335 
1336         if (__in_fake_assign)
1337                 return;
1338         if (outside_of_function())
1339                 return;
1340         state = get_extra_state(expr);
1341         if (state) {
1342                 struct range_list *rl;
1343 
1344                 rl = rl_intersection(estate_rl(state), valid_ptr_rl);
1345                 if (rl_equiv(rl, estate_rl(state)))
1346                         return;
1347                 set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1348         } else {
1349                 struct range_list *rl;
1350 
1351                 if (get_mtag_rl(expr, &rl))
1352                         rl = rl_intersection(rl, valid_ptr_rl);
1353                 else
1354                         rl = clone_rl(valid_ptr_rl);
1355 
1356                 set_extra_expr_nomod(expr, alloc_estate_rl(rl));
1357         }
1358 }
1359 
1360 static void match_dereferences(struct expression *expr)
1361 {
1362         if (expr->type != EXPR_PREOP)
1363                 return;
1364         if (getting_address(expr))
1365                 return;
1366         /* it's saying that foo[1] = bar dereferences foo[1] */
1367         if (is_array(expr))
1368                 return;
1369         check_dereference(expr->unop);
1370 }
1371 
1372 static void match_pointer_as_array(struct expression *expr)
1373 {
1374         if (!is_array(expr))
1375                 return;
1376         check_dereference(get_array_base(expr));
1377 }
1378 
1379 static void find_dereferences(struct expression *expr)
1380 {
1381         while (expr->type == EXPR_PREOP) {
1382                 if (expr->op == '*')
1383                         check_dereference(expr->unop);
1384                 expr = strip_expr(expr->unop);
1385         }
1386 }
1387 
1388 static void set_param_dereferenced(struct expression *call, struct expression *arg, char *key, char *unused)
1389 {
1390         struct symbol *sym;
1391         char *name;
1392 
1393         name = get_variable_from_key(arg, key, &sym);
1394         if (name && sym) {
1395                 struct smatch_state *orig, *new;
1396                 struct range_list *rl;
1397 
1398                 orig = get_state(SMATCH_EXTRA, name, sym);
1399                 if (orig) {
1400                         rl = rl_intersection(estate_rl(orig),
1401                                              alloc_rl(valid_ptr_min_sval,
1402                                                       valid_ptr_max_sval));
1403                         new = alloc_estate_rl(rl);
1404                 } else {
1405                         new = alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval);
1406                 }
1407 
1408                 set_extra_nomod(name, sym, NULL, new);
1409         }
1410         free_string(name);
1411 
1412         find_dereferences(arg);
1413 }
1414 
1415 static sval_t add_one(sval_t sval)
1416 {
1417         sval.value++;
1418         return sval;
1419 }
1420 
1421 static int handle_postop_inc(struct expression *left, int op, struct expression *right)
1422 {
1423         struct statement *stmt;
1424         struct expression *cond;
1425         struct smatch_state *true_state, *false_state;
1426         struct symbol *type;
1427         sval_t start;
1428         sval_t limit;
1429 
1430         /*
1431          * If we're decrementing here then that's a canonical while count down
1432          * so it's handled already.  We're only handling loops like:
1433          * i = 0;
1434          * do { ... } while (i++ < 3);
1435          */
1436 
1437         if (left->type != EXPR_POSTOP || left->op != SPECIAL_INCREMENT)
1438                 return 0;
1439 
1440         stmt = __cur_stmt->parent;
1441         if (!stmt)
1442                 return 0;
1443         if (stmt->type == STMT_COMPOUND)
1444                 stmt = stmt->parent;
1445         if (!stmt || stmt->type != STMT_ITERATOR || !stmt->iterator_post_condition)
1446                 return 0;
1447 
1448         cond = strip_expr(stmt->iterator_post_condition);
1449         if (cond->type != EXPR_COMPARE || cond->op != op)
1450                 return 0;
1451         if (left != strip_expr(cond->left) || right != strip_expr(cond->right))
1452                 return 0;
1453 
1454         if (!get_implied_value(left->unop, &start))
1455                 return 0;
1456         if (!get_implied_value(right, &limit))
1457                 return 0;
1458         type = get_type(left->unop);
1459         limit = sval_cast(type, limit);
1460         if (sval_cmp(start, limit) > 0)
1461                 return 0;
1462 
1463         switch (op) {
1464         case '<':
1465         case SPECIAL_UNSIGNED_LT:
1466                 break;
1467         case SPECIAL_LTE:
1468         case SPECIAL_UNSIGNED_LTE:
1469                 limit = add_one(limit);
1470         default:
1471                 return 0;
1472 
1473         }
1474 
1475         true_state = alloc_estate_range(add_one(start), limit);
1476         false_state = alloc_estate_range(add_one(limit), add_one(limit));
1477 
1478         /* Currently we just discard the false state but when two passes is
1479          * implimented correctly then it will use it.
1480          */
1481 
1482         set_extra_expr_true_false(left->unop, true_state, false_state);
1483 
1484         return 1;
1485 }
1486 
1487 bool is_impossible_variable(struct expression *expr)
1488 {
1489         struct smatch_state *state;
1490 
1491         state = get_extra_state(expr);
1492         if (state && !estate_rl(state))
1493                 return true;
1494         return false;
1495 }
1496 
1497 static bool in_macro(struct expression *left, struct expression *right)
1498 {
1499         if (!left || !right)
1500                 return 0;
1501         if (left->pos.line != right->pos.line || left->pos.pos != right->pos.pos)
1502                 return 0;
1503         if (get_macro_name(left->pos))
1504                 return 1;
1505         return 0;
1506 }
1507 
1508 static void handle_comparison(struct symbol *type, struct expression *left, int op, struct expression *right)
1509 {
1510         struct range_list *left_orig;
1511         struct range_list *left_true;
1512         struct range_list *left_false;
1513         struct range_list *right_orig;
1514         struct range_list *right_true;
1515         struct range_list *right_false;
1516         struct smatch_state *left_true_state;
1517         struct smatch_state *left_false_state;
1518         struct smatch_state *right_true_state;
1519         struct smatch_state *right_false_state;
1520         sval_t dummy, hard_max;
1521         int left_postop = 0;
1522         int right_postop = 0;
1523 
1524         if (left->op == SPECIAL_INCREMENT || left->op == SPECIAL_DECREMENT) {
1525                 if (left->type == EXPR_POSTOP) {
1526                         left->smatch_flags |= Handled;
1527                         left_postop = left->op;
1528                         if (handle_postop_inc(left, op, right))
1529                                 return;
1530                 }
1531                 left = strip_parens(left->unop);
1532         }
1533         while (left->type == EXPR_ASSIGNMENT)
1534                 left = strip_parens(left->left);
1535 
1536         if (right->op == SPECIAL_INCREMENT || right->op == SPECIAL_DECREMENT) {
1537                 if (right->type == EXPR_POSTOP) {
1538                         right->smatch_flags |= Handled;
1539                         right_postop = right->op;
1540                 }
1541                 right = strip_parens(right->unop);
1542         }
1543 
1544         if (is_impossible_variable(left) || is_impossible_variable(right))
1545                 return;
1546 
1547         get_real_absolute_rl(left, &left_orig);
1548         left_orig = cast_rl(type, left_orig);
1549 
1550         get_real_absolute_rl(right, &right_orig);
1551         right_orig = cast_rl(type, right_orig);
1552 
1553         split_comparison_rl(left_orig, op, right_orig, &left_true, &left_false, &right_true, &right_false);
1554 
1555         left_true = rl_truncate_cast(get_type(strip_expr(left)), left_true);
1556         left_false = rl_truncate_cast(get_type(strip_expr(left)), left_false);
1557         right_true = rl_truncate_cast(get_type(strip_expr(right)), right_true);
1558         right_false = rl_truncate_cast(get_type(strip_expr(right)), right_false);
1559 
1560         if (!left_true || !left_false) {
1561                 struct range_list *tmp_true, *tmp_false;
1562 
1563                 split_comparison_rl(alloc_whole_rl(type), op, right_orig, &tmp_true, &tmp_false, NULL, NULL);
1564                 tmp_true = rl_truncate_cast(get_type(strip_expr(left)), tmp_true);
1565                 tmp_false = rl_truncate_cast(get_type(strip_expr(left)), tmp_false);
1566                 if (tmp_true && tmp_false)
1567                         __save_imaginary_state(left, tmp_true, tmp_false);
1568         }
1569 
1570         if (!right_true || !right_false) {
1571                 struct range_list *tmp_true, *tmp_false;
1572 
1573                 split_comparison_rl(alloc_whole_rl(type), op, right_orig, NULL, NULL, &tmp_true, &tmp_false);
1574                 tmp_true = rl_truncate_cast(get_type(strip_expr(right)), tmp_true);
1575                 tmp_false = rl_truncate_cast(get_type(strip_expr(right)), tmp_false);
1576                 if (tmp_true && tmp_false)
1577                         __save_imaginary_state(right, tmp_true, tmp_false);
1578         }
1579 
1580         left_true_state = alloc_estate_rl(left_true);
1581         left_false_state = alloc_estate_rl(left_false);
1582         right_true_state = alloc_estate_rl(right_true);
1583         right_false_state = alloc_estate_rl(right_false);
1584 
1585         switch (op) {
1586         case '<':
1587         case SPECIAL_UNSIGNED_LT:
1588         case SPECIAL_UNSIGNED_LTE:
1589         case SPECIAL_LTE:
1590                 if (get_implied_value(right, &dummy) && !in_macro(left, right))
1591                         estate_set_hard_max(left_true_state);
1592                 if (get_implied_value(left, &dummy) && !in_macro(left, right))
1593                         estate_set_hard_max(right_false_state);
1594                 break;
1595         case '>':
1596         case SPECIAL_UNSIGNED_GT:
1597         case SPECIAL_UNSIGNED_GTE:
1598         case SPECIAL_GTE:
1599                 if (get_implied_value(left, &dummy) && !in_macro(left, right))
1600                         estate_set_hard_max(right_true_state);
1601                 if (get_implied_value(right, &dummy) && !in_macro(left, right))
1602                         estate_set_hard_max(left_false_state);
1603                 break;
1604         }
1605 
1606         switch (op) {
1607         case '<':
1608         case SPECIAL_UNSIGNED_LT:
1609         case SPECIAL_UNSIGNED_LTE:
1610         case SPECIAL_LTE:
1611                 if (get_hard_max(right, &hard_max)) {
1612                         if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1613                                 hard_max.value--;
1614                         estate_set_fuzzy_max(left_true_state, hard_max);
1615                 }
1616                 if (get_implied_value(right, &hard_max)) {
1617                         if (op == SPECIAL_UNSIGNED_LTE ||
1618                             op == SPECIAL_LTE)
1619                                 hard_max.value++;
1620                         estate_set_fuzzy_max(left_false_state, hard_max);
1621                 }
1622                 if (get_hard_max(left, &hard_max)) {
1623                         if (op == SPECIAL_UNSIGNED_LTE ||
1624                             op == SPECIAL_LTE)
1625                                 hard_max.value--;
1626                         estate_set_fuzzy_max(right_false_state, hard_max);
1627                 }
1628                 if (get_implied_value(left, &hard_max)) {
1629                         if (op == '<' || op == SPECIAL_UNSIGNED_LT)
1630                                 hard_max.value++;
1631                         estate_set_fuzzy_max(right_true_state, hard_max);
1632                 }
1633                 break;
1634         case '>':
1635         case SPECIAL_UNSIGNED_GT:
1636         case SPECIAL_UNSIGNED_GTE:
1637         case SPECIAL_GTE:
1638                 if (get_hard_max(left, &hard_max)) {
1639                         if (op == '>' || op == SPECIAL_UNSIGNED_GT)
1640                                 hard_max.value--;
1641                         estate_set_fuzzy_max(right_true_state, hard_max);
1642                 }
1643                 if (get_implied_value(left, &hard_max)) {
1644                         if (op == SPECIAL_UNSIGNED_GTE ||
1645                             op == SPECIAL_GTE)
1646                                 hard_max.value++;
1647                         estate_set_fuzzy_max(right_false_state, hard_max);
1648                 }
1649                 if (get_hard_max(right, &hard_max)) {
1650                         if (op == SPECIAL_UNSIGNED_LTE ||
1651                             op == SPECIAL_LTE)
1652                                 hard_max.value--;
1653                         estate_set_fuzzy_max(left_false_state, hard_max);
1654                 }
1655                 if (get_implied_value(right, &hard_max)) {
1656                         if (op == '>' ||
1657                             op == SPECIAL_UNSIGNED_GT)
1658                                 hard_max.value++;
1659                         estate_set_fuzzy_max(left_true_state, hard_max);
1660                 }
1661                 break;
1662         case SPECIAL_EQUAL:
1663                 if (get_hard_max(left, &hard_max))
1664                         estate_set_fuzzy_max(right_true_state, hard_max);
1665                 if (get_hard_max(right, &hard_max))
1666                         estate_set_fuzzy_max(left_true_state, hard_max);
1667                 break;
1668         }
1669 
1670         if (get_hard_max(left, &hard_max)) {
1671                 estate_set_hard_max(left_true_state);
1672                 estate_set_hard_max(left_false_state);
1673         }
1674         if (get_hard_max(right, &hard_max)) {
1675                 estate_set_hard_max(right_true_state);
1676                 estate_set_hard_max(right_false_state);
1677         }
1678 
1679         if (left_postop == SPECIAL_INCREMENT) {
1680                 left_true_state = increment_state(left_true_state);
1681                 left_false_state = increment_state(left_false_state);
1682         }
1683         if (left_postop == SPECIAL_DECREMENT) {
1684                 left_true_state = decrement_state(left_true_state);
1685                 left_false_state = decrement_state(left_false_state);
1686         }
1687         if (right_postop == SPECIAL_INCREMENT) {
1688                 right_true_state = increment_state(right_true_state);
1689                 right_false_state = increment_state(right_false_state);
1690         }
1691         if (right_postop == SPECIAL_DECREMENT) {
1692                 right_true_state = decrement_state(right_true_state);
1693                 right_false_state = decrement_state(right_false_state);
1694         }
1695 
1696         if (estate_rl(left_true_state) && estates_equiv(left_true_state, left_false_state)) {
1697                 left_true_state = NULL;
1698                 left_false_state = NULL;
1699         }
1700 
1701         if (estate_rl(right_true_state) && estates_equiv(right_true_state, right_false_state)) {
1702                 right_true_state = NULL;
1703                 right_false_state = NULL;
1704         }
1705 
1706         /* Don't introduce new states for known true/false conditions */
1707         if (rl_equiv(left_orig, estate_rl(left_true_state)))
1708                 left_true_state = NULL;
1709         if (rl_equiv(left_orig, estate_rl(left_false_state)))
1710                 left_false_state = NULL;
1711         if (rl_equiv(right_orig, estate_rl(right_true_state)))
1712                 right_true_state = NULL;
1713         if (rl_equiv(right_orig, estate_rl(right_false_state)))
1714                 right_false_state = NULL;
1715 
1716         set_extra_expr_true_false(left, left_true_state, left_false_state);
1717         set_extra_expr_true_false(right, right_true_state, right_false_state);
1718 }
1719 
1720 static int is_simple_math(struct expression *expr)
1721 {
1722         if (!expr)
1723                 return 0;
1724         if (expr->type != EXPR_BINOP)
1725                 return 0;
1726         switch (expr->op) {
1727         case '+':
1728         case '-':
1729         case '*':
1730                 return 1;
1731         }
1732         return 0;
1733 }
1734 
1735 static int flip_op(int op)
1736 {
1737         /* We only care about simple math */
1738         switch (op) {
1739         case '+':
1740                 return '-';
1741         case '-':
1742                 return '+';
1743         case '*':
1744                 return '/';
1745         }
1746         return 0;
1747 }
1748 
1749 static void move_known_to_rl(struct expression **expr_p, struct range_list **rl_p)
1750 {
1751         struct expression *expr = *expr_p;
1752         struct range_list *rl = *rl_p;
1753         sval_t sval;
1754 
1755         if (!is_simple_math(expr))
1756                 return;
1757 
1758         if (get_implied_value(expr->right, &sval)) {
1759                 *expr_p = expr->left;
1760                 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1761                 move_known_to_rl(expr_p, rl_p);
1762                 return;
1763         }
1764         if (expr->op == '-')
1765                 return;
1766         if (get_implied_value(expr->left, &sval)) {
1767                 *expr_p = expr->right;
1768                 *rl_p = rl_binop(rl, flip_op(expr->op), alloc_rl(sval, sval));
1769                 move_known_to_rl(expr_p, rl_p);
1770                 return;
1771         }
1772 }
1773 
1774 static void move_known_values(struct expression **left_p, struct expression **right_p)
1775 {
1776         struct expression *left = *left_p;
1777         struct expression *right = *right_p;
1778         sval_t sval, dummy;
1779 
1780         if (get_implied_value(left, &sval)) {
1781                 if (!is_simple_math(right))
1782                         return;
1783                 if (get_implied_value(right, &dummy))
1784                         return;
1785                 if (right->op == '*') {
1786                         sval_t divisor;
1787 
1788                         if (!get_value(right->right, &divisor))
1789                                 return;
1790                         if (divisor.value == 0)
1791                                 return;
1792                         *left_p = binop_expression(left, invert_op(right->op), right->right);
1793                         *right_p = right->left;
1794                         return;
1795                 }
1796                 if (right->op == '+' && get_value(right->left, &sval)) {
1797                         *left_p = binop_expression(left, invert_op(right->op), right->left);
1798                         *right_p = right->right;
1799                         return;
1800                 }
1801                 if (get_value(right->right, &sval)) {
1802                         *left_p = binop_expression(left, invert_op(right->op), right->right);
1803                         *right_p = right->left;
1804                         return;
1805                 }
1806                 return;
1807         }
1808         if (get_implied_value(right, &sval)) {
1809                 if (!is_simple_math(left))
1810                         return;
1811                 if (get_implied_value(left, &dummy))
1812                         return;
1813                 if (left->op == '*') {
1814                         sval_t divisor;
1815 
1816                         if (!get_value(left->right, &divisor))
1817                                 return;
1818                         if (divisor.value == 0)
1819                                 return;
1820                         *right_p = binop_expression(right, invert_op(left->op), left->right);
1821                         *left_p = left->left;
1822                         return;
1823                 }
1824                 if (left->op == '+' && get_value(left->left, &sval)) {
1825                         *right_p = binop_expression(right, invert_op(left->op), left->left);
1826                         *left_p = left->right;
1827                         return;
1828                 }
1829 
1830                 if (get_value(left->right, &sval)) {
1831                         *right_p = binop_expression(right, invert_op(left->op), left->right);
1832                         *left_p = left->left;
1833                         return;
1834                 }
1835                 return;
1836         }
1837 }
1838 
1839 /*
1840  * The reason for do_simple_algebra() is to solve things like:
1841  * if (foo > 66 || foo + bar > 64) {
1842  * "foo" is not really a known variable so it won't be handled by
1843  * move_known_variables() but it's a super common idiom.
1844  *
1845  */
1846 static int do_simple_algebra(struct expression **left_p, struct expression **right_p)
1847 {
1848         struct expression *left = *left_p;
1849         struct expression *right = *right_p;
1850         struct range_list *rl;
1851         sval_t tmp;
1852 
1853         if (left->type != EXPR_BINOP || left->op != '+')
1854                 return 0;
1855         if (can_integer_overflow(get_type(left), left))
1856                 return 0;
1857         if (!get_implied_value(right, &tmp))
1858                 return 0;
1859 
1860         if (!get_implied_value(left->left, &tmp) &&
1861             get_implied_rl(left->left, &rl) &&
1862             !is_whole_rl(rl)) {
1863                 *right_p = binop_expression(right, '-', left->left);
1864                 *left_p = left->right;
1865                 return 1;
1866         }
1867         if (!get_implied_value(left->right, &tmp) &&
1868             get_implied_rl(left->right, &rl) &&
1869             !is_whole_rl(rl)) {
1870                 *right_p = binop_expression(right, '-', left->right);
1871                 *left_p = left->left;
1872                 return 1;
1873         }
1874 
1875         return 0;
1876 }
1877 
1878 static int match_func_comparison(struct expression *expr)
1879 {
1880         struct expression *left = strip_expr(expr->left);
1881         struct expression *right = strip_expr(expr->right);
1882 
1883         if (left->type == EXPR_CALL || right->type == EXPR_CALL) {
1884                 function_comparison(left, expr->op, right);
1885                 return 1;
1886         }
1887 
1888         return 0;
1889 }
1890 
1891 /* Handle conditions like "if (foo + bar < foo) {" */
1892 static int handle_integer_overflow_test(struct expression *expr)
1893 {
1894         struct expression *left, *right;
1895         struct symbol *type;
1896         sval_t left_min, right_min, min, max;
1897 
1898         if (expr->op != '<' && expr->op != SPECIAL_UNSIGNED_LT)
1899                 return 0;
1900 
1901         left = strip_parens(expr->left);
1902         right = strip_parens(expr->right);
1903 
1904         if (left->op != '+')
1905                 return 0;
1906 
1907         type = get_type(expr);
1908         if (!type)
1909                 return 0;
1910         if (type_positive_bits(type) == 32) {
1911                 max.type = &uint_ctype;
1912                 max.uvalue = (unsigned int)-1;
1913         } else if (type_positive_bits(type) == 64) {
1914                 max.type = &ulong_ctype;
1915                 max.value = (unsigned long long)-1;
1916         } else {
1917                 return 0;
1918         }
1919 
1920         if (!expr_equiv(left->left, right) && !expr_equiv(left->right, right))
1921                 return 0;
1922 
1923         get_absolute_min(left->left, &left_min);
1924         get_absolute_min(left->right, &right_min);
1925         min = sval_binop(left_min, '+', right_min);
1926 
1927         type = get_type(left);
1928         min = sval_cast(type, min);
1929         max = sval_cast(type, max);
1930 
1931         set_extra_chunk_true_false(left, NULL, alloc_estate_range(min, max));
1932         return 1;
1933 }
1934 
1935 static void match_comparison(struct expression *expr)
1936 {
1937         struct expression *left_orig = strip_parens(expr->left);
1938         struct expression *right_orig = strip_parens(expr->right);
1939         struct expression *left, *right, *tmp;
1940         struct expression *prev;
1941         struct symbol *type;
1942         int redo, count;
1943 
1944         if (match_func_comparison(expr))
1945                 return;
1946 
1947         type = get_type(expr);
1948         if (!type)
1949                 type = &llong_ctype;
1950 
1951         if (handle_integer_overflow_test(expr))
1952                 return;
1953 
1954         left = left_orig;
1955         right = right_orig;
1956         move_known_values(&left, &right);
1957         handle_comparison(type, left, expr->op, right);
1958 
1959         left = left_orig;
1960         right = right_orig;
1961         if (do_simple_algebra(&left, &right))
1962                 handle_comparison(type, left, expr->op, right);
1963 
1964         prev = get_assigned_expr(left_orig);
1965         if (is_simple_math(prev) && has_variable(prev, left_orig) == 0) {
1966                 left = prev;
1967                 right = right_orig;
1968                 move_known_values(&left, &right);
1969                 handle_comparison(type, left, expr->op, right);
1970         }
1971 
1972         prev = get_assigned_expr(right_orig);
1973         if (is_simple_math(prev) && has_variable(prev, right_orig) == 0) {
1974                 left = left_orig;
1975                 right = prev;
1976                 move_known_values(&left, &right);
1977                 handle_comparison(type, left, expr->op, right);
1978         }
1979 
1980         redo = 0;
1981         left = left_orig;
1982         right = right_orig;
1983         if (get_last_expr_from_expression_stmt(left_orig)) {
1984                 left = get_last_expr_from_expression_stmt(left_orig);
1985                 redo = 1;
1986         }
1987         if (get_last_expr_from_expression_stmt(right_orig)) {
1988                 right = get_last_expr_from_expression_stmt(right_orig);
1989                 redo = 1;
1990         }
1991 
1992         if (!redo)
1993                 return;
1994 
1995         count = 0;
1996         while ((tmp = get_assigned_expr(left))) {
1997                 if (count++ > 3)
1998                         break;
1999                 left = strip_expr(tmp);
2000         }
2001         count = 0;
2002         while ((tmp = get_assigned_expr(right))) {
2003                 if (count++ > 3)
2004                         break;
2005                 right = strip_expr(tmp);
2006         }
2007 
2008         handle_comparison(type, left, expr->op, right);
2009 }
2010 
2011 static sval_t get_high_mask(sval_t known)
2012 {
2013         sval_t ret;
2014         int i;
2015 
2016         ret = known;
2017         ret.value = 0;
2018 
2019         for (i = type_bits(known.type) - 1; i >= 0; i--) {
2020                 if (known.uvalue & (1ULL << i))
2021                         ret.uvalue |= (1ULL << i);
2022                 else
2023                         return ret;
2024 
2025         }
2026         return ret;
2027 }
2028 
2029 static bool handle_bit_test(struct expression *expr)
2030 {
2031         struct range_list *orig_rl, *rl;
2032         struct expression *shift, *mask, *var;
2033         struct bit_info *bit_info;
2034         sval_t sval;
2035         sval_t high = { .type = &int_ctype };
2036         sval_t low = { .type = &int_ctype };
2037 
2038         shift = strip_expr(expr->right);
2039         mask = strip_expr(expr->left);
2040         if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT) {
2041                 shift = strip_expr(expr->left);
2042                 mask = strip_expr(expr->right);
2043                 if (shift->type != EXPR_BINOP || shift->op != SPECIAL_LEFTSHIFT)
2044                         return false;
2045         }
2046         if (!get_implied_value(shift->left, &sval) || sval.value != 1)
2047                 return false;
2048         var = strip_expr(shift->right);
2049 
2050         bit_info = get_bit_info(mask);
2051         if (!bit_info)
2052                 return false;
2053         if (!bit_info->possible)
2054                 return false;
2055 
2056         get_absolute_rl(var, &orig_rl);
2057         if (sval_is_negative(rl_min(orig_rl)) ||
2058             rl_max(orig_rl).uvalue > type_bits(get_type(shift->left)))
2059                 return false;
2060 
2061         low.value = ffsll(bit_info->possible);
2062         high.value = sm_fls64(bit_info->possible);
2063         rl = alloc_rl(low, high);
2064         rl = cast_rl(get_type(var), rl);
2065         rl = rl_intersection(orig_rl, rl);
2066         if (!rl)
2067                 return false;
2068 
2069         set_extra_expr_true_false(shift->right, alloc_estate_rl(rl), NULL);
2070 
2071         return true;
2072 }
2073 
2074 static void handle_AND_op(struct expression *var, sval_t known)
2075 {
2076         struct range_list *orig_rl;
2077         struct range_list *true_rl = NULL;
2078         struct range_list *false_rl = NULL;
2079         int bit;
2080         sval_t low_mask = known;
2081         sval_t high_mask;
2082         sval_t max;
2083 
2084         get_absolute_rl(var, &orig_rl);
2085 
2086         if (known.value > 0) {
2087                 bit = ffsll(known.value) - 1;
2088                 low_mask.uvalue = (1ULL << bit) - 1;
2089                 true_rl = remove_range(orig_rl, sval_type_val(known.type, 0), low_mask);
2090         }
2091         high_mask = get_high_mask(known);
2092         if (high_mask.value) {
2093                 bit = ffsll(high_mask.value) - 1;
2094                 low_mask.uvalue = (1ULL << bit) - 1;
2095 
2096                 false_rl = orig_rl;
2097                 if (sval_is_negative(rl_min(orig_rl)))
2098                         false_rl = remove_range(false_rl, sval_type_min(known.type), sval_type_val(known.type, -1));
2099                 false_rl = remove_range(false_rl, low_mask, sval_type_max(known.type));
2100                 if (type_signed(high_mask.type) && type_unsigned(rl_type(false_rl))) {
2101                         false_rl = remove_range(false_rl,
2102                                                 sval_type_val(rl_type(false_rl), sval_type_max(known.type).uvalue),
2103                                         sval_type_val(rl_type(false_rl), -1));
2104                 }
2105         } else if (known.value == 1 &&
2106                    get_hard_max(var, &max) &&
2107                    sval_cmp(max, rl_max(orig_rl)) == 0 &&
2108                    max.value & 1) {
2109                 false_rl = remove_range(orig_rl, max, max);
2110         }
2111         set_extra_expr_true_false(var,
2112                                   true_rl ? alloc_estate_rl(true_rl) : NULL,
2113                                   false_rl ? alloc_estate_rl(false_rl) : NULL);
2114 }
2115 
2116 static void handle_AND_condition(struct expression *expr)
2117 {
2118         sval_t known;
2119 
2120         if (handle_bit_test(expr))
2121                 return;
2122 
2123         if (get_implied_value(expr->left, &known))
2124                 handle_AND_op(expr->right, known);
2125         else if (get_implied_value(expr->right, &known))
2126                 handle_AND_op(expr->left, known);
2127 }
2128 
2129 static void handle_MOD_condition(struct expression *expr)
2130 {
2131         struct range_list *orig_rl;
2132         struct range_list *true_rl;
2133         struct range_list *false_rl = NULL;
2134         sval_t right;
2135         sval_t zero = { 0, };
2136 
2137         if (!get_implied_value(expr->right, &right) || right.value == 0)
2138                 return;
2139         get_absolute_rl(expr->left, &orig_rl);
2140 
2141         zero.value = 0;
2142         zero.type = rl_type(orig_rl);
2143 
2144         /* We're basically dorking around the min and max here */
2145         true_rl = remove_range(orig_rl, zero, zero);
2146         if (!sval_is_max(rl_max(true_rl)) &&
2147             !(rl_max(true_rl).value % right.value))
2148                 true_rl = remove_range(true_rl, rl_max(true_rl), rl_max(true_rl));
2149 
2150         if (rl_equiv(true_rl, orig_rl))
2151                 true_rl = NULL;
2152 
2153         if (sval_is_positive(rl_min(orig_rl)) &&
2154             (rl_max(orig_rl).value - rl_min(orig_rl).value) / right.value < 5) {
2155                 sval_t add;
2156                 int i;
2157 
2158                 add = rl_min(orig_rl);
2159                 add.value += right.value - (add.value % right.value);
2160                 add.value -= right.value;
2161 
2162                 for (i = 0; i < 5; i++) {
2163                         add.value += right.value;
2164                         if (add.value > rl_max(orig_rl).value)
2165                                 break;
2166                         add_range(&false_rl, add, add);
2167                 }
2168         } else {
2169                 if (rl_min(orig_rl).uvalue != 0 &&
2170                     rl_min(orig_rl).uvalue < right.uvalue) {
2171                         sval_t chop = right;
2172                         chop.value--;
2173                         false_rl = remove_range(orig_rl, zero, chop);
2174                 }
2175 
2176                 if (!sval_is_max(rl_max(orig_rl)) &&
2177                     (rl_max(orig_rl).value % right.value)) {
2178                         sval_t chop = rl_max(orig_rl);
2179                         chop.value -= chop.value % right.value;
2180                         chop.value++;
2181                         if (!false_rl)
2182                                 false_rl = clone_rl(orig_rl);
2183                         false_rl = remove_range(false_rl, chop, rl_max(orig_rl));
2184                 }
2185         }
2186 
2187         set_extra_expr_true_false(expr->left,
2188                                   true_rl ? alloc_estate_rl(true_rl) : NULL,
2189                                   false_rl ? alloc_estate_rl(false_rl) : NULL);
2190 }
2191 
2192 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
2193 void __extra_match_condition(struct expression *expr)
2194 {
2195         expr = strip_expr(expr);
2196         switch (expr->type) {
2197         case EXPR_CALL:
2198                 function_comparison(expr, SPECIAL_NOTEQUAL, zero_expr());
2199                 return;
2200         case EXPR_PREOP:
2201         case EXPR_SYMBOL:
2202         case EXPR_DEREF:
2203                 handle_comparison(get_type(expr), expr, SPECIAL_NOTEQUAL, zero_expr());
2204                 return;
2205         case EXPR_COMPARE:
2206                 match_comparison(expr);
2207                 return;
2208         case EXPR_ASSIGNMENT:
2209                 __extra_match_condition(expr->left);
2210                 return;
2211         case EXPR_BINOP:
2212                 if (expr->op == '&')
2213                         handle_AND_condition(expr);
2214                 if (expr->op == '%')
2215                         handle_MOD_condition(expr);
2216                 return;
2217         }
2218 }
2219 
2220 static void assume_indexes_are_valid(struct expression *expr)
2221 {
2222         struct expression *array_expr;
2223         int array_size;
2224         struct expression *offset;
2225         struct symbol *offset_type;
2226         struct range_list *rl_before;
2227         struct range_list *rl_after;
2228         struct range_list *filter = NULL;
2229         sval_t size;
2230 
2231         expr = strip_expr(expr);
2232         if (!is_array(expr))
2233                 return;
2234 
2235         offset = get_array_offset(expr);
2236         offset_type = get_type(offset);
2237         if (offset_type && type_signed(offset_type)) {
2238                 filter = alloc_rl(sval_type_min(offset_type),
2239                                   sval_type_val(offset_type, -1));
2240         }
2241 
2242         array_expr = get_array_base(expr);
2243         array_size = get_real_array_size(array_expr);
2244         if (array_size > 1) {
2245                 size = sval_type_val(offset_type, array_size);
2246                 add_range(&filter, size, sval_type_max(offset_type));
2247         }
2248 
2249         if (!filter)
2250                 return;
2251         get_absolute_rl(offset, &rl_before);
2252         rl_after = rl_filter(rl_before, filter);
2253         if (rl_equiv(rl_before, rl_after))
2254                 return;
2255         set_extra_expr_nomod(offset, alloc_estate_rl(rl_after));
2256 }
2257 
2258 /* returns 1 if it is not possible for expr to be value, otherwise returns 0 */
2259 int implied_not_equal(struct expression *expr, long long val)
2260 {
2261         return !possibly_false(expr, SPECIAL_NOTEQUAL, value_expr(val));
2262 }
2263 
2264 int implied_not_equal_name_sym(char *name, struct symbol *sym, long long val)
2265 {
2266         struct smatch_state *estate;
2267 
2268         estate = get_state(SMATCH_EXTRA, name, sym);
2269         if (!estate)
2270                 return 0;
2271         if (!rl_has_sval(estate_rl(estate), sval_type_val(estate_type(estate), 0)))
2272                 return 1;
2273         return 0;
2274 }
2275 
2276 int parent_is_null_var_sym(const char *name, struct symbol *sym)
2277 {
2278         char buf[256];
2279         char *start;
2280         char *end;
2281         struct smatch_state *state;
2282 
2283         strncpy(buf, name, sizeof(buf) - 1);
2284         buf[sizeof(buf) - 1] = '\0';
2285 
2286         start = &buf[0];
2287         while (*start == '*') {
2288                 start++;
2289                 state = __get_state(SMATCH_EXTRA, start, sym);
2290                 if (!state)
2291                         continue;
2292                 if (!estate_rl(state))
2293                         return 1;
2294                 if (estate_min(state).value == 0 &&
2295                     estate_max(state).value == 0)
2296                         return 1;
2297         }
2298 
2299         start = &buf[0];
2300         while (*start == '&')
2301                 start++;
2302 
2303         while ((end = strrchr(start, '-'))) {
2304                 *end = '\0';
2305                 state = __get_state(SMATCH_EXTRA, start, sym);
2306                 if (!state)
2307                         continue;
2308                 if (estate_min(state).value == 0 &&
2309                     estate_max(state).value == 0)
2310                         return 1;
2311         }
2312         return 0;
2313 }
2314 
2315 int parent_is_null(struct expression *expr)
2316 {
2317         struct symbol *sym;
2318         char *var;
2319         int ret = 0;
2320 
2321         expr = strip_expr(expr);
2322         var = expr_to_var_sym(expr, &sym);
2323         if (!var || !sym)
2324                 goto free;
2325         ret = parent_is_null_var_sym(var, sym);
2326 free:
2327         free_string(var);
2328         return ret;
2329 }
2330 
2331 static int param_used_callback(void *found, int argc, char **argv, char **azColName)
2332 {
2333         *(int *)found = 1;
2334         return 0;
2335 }
2336 
2337 static int is_kzalloc_info(struct sm_state *sm)
2338 {
2339         sval_t sval;
2340 
2341         /*
2342          * kzalloc() information is treated as special because so there is just
2343          * a lot of stuff initialized to zero and it makes building the database
2344          * take hours and hours.
2345          *
2346          * In theory, we should just remove this line and not pass any unused
2347          * information, but I'm not sure enough that this code works so I want
2348          * to hold off on that for now.
2349          */
2350         if (!estate_get_single_value(sm->state, &sval))
2351                 return 0;
2352         if (sval.value != 0)
2353                 return 0;
2354         return 1;
2355 }
2356 
2357 static int is_really_long(struct sm_state *sm)
2358 {
2359         const char *p;
2360         int cnt = 0;
2361 
2362         p = sm->name;
2363         while ((p = strstr(p, "->"))) {
2364                 p += 2;
2365                 cnt++;
2366         }
2367 
2368         if (cnt < 3 ||
2369             strlen(sm->name) < 40)
2370                 return 0;
2371         return 1;
2372 }
2373 
2374 static int filter_unused_param_value_info(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2375 {
2376         int found = 0;
2377 
2378         /* for function pointers assume everything is used */
2379         if (call->fn->type != EXPR_SYMBOL)
2380                 return 0;
2381 
2382         /*
2383          * This is to handle __builtin_mul_overflow().  In an ideal world we
2384          * would only need this for invalid code.
2385          *
2386          */
2387         if (!call->fn->symbol)
2388                 return 0;
2389 
2390         if (!is_kzalloc_info(sm) && !is_really_long(sm))
2391                 return 0;
2392 
2393         run_sql(&param_used_callback, &found,
2394                 "select * from return_implies where %s and type = %d and parameter = %d and key = '%s';",
2395                 get_static_filter(call->fn->symbol), PARAM_USED, param, printed_name);
2396         if (found)
2397                 return 0;
2398 
2399         /* If the database is not built yet, then assume everything is used */
2400         run_sql(&param_used_callback, &found,
2401                 "select * from return_implies where %s and type = %d;",
2402                 get_static_filter(call->fn->symbol), PARAM_USED);
2403         if (!found)
2404                 return 0;
2405 
2406         return 1;
2407 }
2408 
2409 struct range_list *intersect_with_real_abs_var_sym(const char *name, struct symbol *sym, struct range_list *start)
2410 {
2411         struct smatch_state *state;
2412 
2413         /*
2414          * Here is the difference between implied value and real absolute, say
2415          * you have:
2416          *
2417          *      int a = (u8)x;
2418          *
2419          * Then you know that a is 0-255.  That's real absolute.  But you don't
2420          * know for sure that it actually goes up to 255.  So it's not implied.
2421          * Implied indicates a degree of certainty.
2422          *
2423          * But then say you cap "a" at 8.  That means you know it goes up to
2424          * 8.  So now the implied value is s32min-8.  But you can combine it
2425          * with the real absolute to say that actually it's 0-8.
2426          *
2427          * We are combining it here.  But now that I think about it, this is
2428          * probably not the ideal place to combine it because it should proably
2429          * be done earlier.  Oh well, this is an improvement on what was there
2430          * before so I'm going to commit this code.
2431          *
2432          */
2433 
2434         state = get_real_absolute_state_var_sym(name, sym);
2435         if (!state || !estate_rl(state))
2436                 return start;
2437 
2438         return rl_intersection(estate_rl(state), start);
2439 }
2440 
2441 struct range_list *intersect_with_real_abs_expr(struct expression *expr, struct range_list *start)
2442 {
2443         struct smatch_state *state;
2444         struct range_list *abs_rl;
2445 
2446         state = get_real_absolute_state(expr);
2447         if (!state || !estate_rl(state))
2448                 return start;
2449 
2450         abs_rl = cast_rl(rl_type(start), estate_rl(state));
2451         return rl_intersection(abs_rl, start);
2452 }
2453 
2454 static void struct_member_callback(struct expression *call, int param, char *printed_name, struct sm_state *sm)
2455 {
2456         struct range_list *rl;
2457         sval_t dummy;
2458 
2459         if (estate_is_whole(sm->state) || !estate_rl(sm->state))
2460                 return;
2461         if (filter_unused_param_value_info(call, param, printed_name, sm))
2462                 return;
2463         rl = estate_rl(sm->state);
2464         rl = intersect_with_real_abs_var_sym(sm->name, sm->sym, rl);
2465         if (!rl)
2466                 return;
2467         sql_insert_caller_info(call, PARAM_VALUE, param, printed_name, show_rl(rl));
2468         if (!estate_get_single_value(sm->state, &dummy)) {
2469                 if (estate_has_hard_max(sm->state))
2470                         sql_insert_caller_info(call, HARD_MAX, param, printed_name,
2471                                                sval_to_str(estate_max(sm->state)));
2472                 if (estate_has_fuzzy_max(sm->state))
2473                         sql_insert_caller_info(call, FUZZY_MAX, param, printed_name,
2474                                                sval_to_str(estate_get_fuzzy_max(sm->state)));
2475         }
2476 }
2477 
2478 static void returned_struct_members(int return_id, char *return_ranges, struct expression *expr)
2479 {
2480         struct symbol *returned_sym;
2481         char *returned_name;
2482         struct sm_state *sm;
2483         char *compare_str;
2484         char name_buf[256];
2485         char val_buf[256];
2486         int len;
2487 
2488         // FIXME handle *$
2489 
2490         if (!is_pointer(expr))
2491                 return;
2492 
2493         returned_name = expr_to_var_sym(expr, &returned_sym);
2494         if (!returned_name || !returned_sym)
2495                 goto free;
2496         len = strlen(returned_name);
2497 
2498         FOR_EACH_MY_SM(my_id, __get_cur_stree(), sm) {
2499                 if (!estate_rl(sm->state))
2500                         continue;
2501                 if (returned_sym != sm->sym)
2502                         continue;
2503                 if (strncmp(returned_name, sm->name, len) != 0)
2504                         continue;
2505                 if (sm->name[len] != '-')
2506                         continue;
2507 
2508                 snprintf(name_buf, sizeof(name_buf), "$%s", sm->name + len);
2509 
2510                 compare_str = name_sym_to_param_comparison(sm->name, sm->sym);
2511                 if (!compare_str && estate_is_whole(sm->state))
2512                         continue;
2513                 snprintf(val_buf, sizeof(val_buf), "%s%s", sm->state->name, compare_str ?: "");
2514 
2515                 sql_insert_return_states(return_id, return_ranges, PARAM_VALUE,
2516                                          -1, name_buf, val_buf);
2517         } END_FOR_EACH_SM(sm);
2518 
2519 free:
2520         free_string(returned_name);
2521 }
2522 
2523 static void db_limited_before(void)
2524 {
2525         unmatched_stree = clone_stree(__get_cur_stree());
2526 }
2527 
2528 static void db_limited_after(void)
2529 {
2530         free_stree(&unmatched_stree);
2531 }
2532 
2533 static int basically_the_same(struct range_list *orig, struct range_list *new)
2534 {
2535         if (rl_equiv(orig, new))
2536                 return 1;
2537 
2538         /*
2539          * The whole range is essentially the same as 0,4096-27777777777 so
2540          * don't overwrite the implications just to store that.
2541          *
2542          */
2543         if (rl_type(orig)->type == SYM_PTR &&
2544             is_whole_rl(orig) &&
2545             rl_min(new).value == 0 &&
2546             rl_max(new).value == valid_ptr_max)
2547                 return 1;
2548         return 0;
2549 }
2550 
2551 static void db_param_limit_binops(struct expression *arg, char *key, struct range_list *rl)
2552 {
2553         struct range_list *left_rl;
2554         sval_t zero = { .type = rl_type(rl), };
2555         sval_t sval;
2556 
2557         if (arg->op != '*')
2558                 return;
2559         if (!get_implied_value(arg->right, &sval))
2560                 return;
2561         if (can_integer_overflow(get_type(arg), arg))
2562                 return;
2563 
2564         left_rl = rl_binop(rl, '/', alloc_rl(sval, sval));
2565         if (!rl_has_sval(rl, zero))
2566                 left_rl = remove_range(left_rl, zero, zero);
2567 
2568         set_extra_expr_nomod(arg->left, alloc_estate_rl(left_rl));
2569 }
2570 
2571 static void db_param_limit_filter(struct expression *expr, int param, char *key, char *value, enum info_type op)
2572 {
2573         struct expression *arg;
2574         char *name;
2575         struct symbol *sym;
2576         struct var_sym_list *vsl = NULL;
2577         struct sm_state *sm;
2578         struct symbol *compare_type, *var_type;
2579         struct range_list *rl;
2580         struct range_list *limit;
2581         struct range_list *new;
2582         char *other_name;
2583         struct symbol *other_sym;
2584 
2585         while (expr->type == EXPR_ASSIGNMENT)
2586                 expr = strip_expr(expr->right);
2587         if (expr->type != EXPR_CALL)
2588                 return;
2589 
2590         arg = get_argument_from_call_expr(expr->args, param);
2591         if (!arg)
2592                 return;
2593 
2594         if (strcmp(key, "$") == 0)
2595                 compare_type = get_arg_type(expr->fn, param);
2596         else
2597                 compare_type = get_member_type_from_key(arg, key);
2598 
2599         call_results_to_rl(expr, compare_type, value, &limit);
2600         if (strcmp(key, "$") == 0)
2601                 move_known_to_rl(&arg, &limit);
2602         name = get_chunk_from_key(arg, key, &sym, &vsl);
2603         if (!name)
2604                 return;
2605         if (op != PARAM_LIMIT && !sym)
2606                 goto free;
2607 
2608         sm = get_sm_state(SMATCH_EXTRA, name, sym);
2609         if (sm)
2610                 rl = estate_rl(sm->state);
2611         else
2612                 rl = alloc_whole_rl(compare_type);
2613 
2614         if (op == PARAM_LIMIT && !rl_fits_in_type(rl, compare_type))
2615                 goto free;
2616 
2617         new = rl_intersection(rl, limit);
2618 
2619         var_type = get_member_type_from_key(arg, key);
2620         new = cast_rl(var_type, new);
2621 
2622         /* We want to preserve the implications here */
2623         if (sm && basically_the_same(rl, new))
2624                 goto free;
2625         other_name = get_other_name_sym(name, sym, &other_sym);
2626 
2627         if (op == PARAM_LIMIT)
2628                 set_extra_nomod_vsl(name, sym, vsl, NULL, alloc_estate_rl(new));
2629         else
2630                 set_extra_mod(name, sym, NULL, alloc_estate_rl(new));
2631 
2632         if (other_name && other_sym) {
2633                 if (op == PARAM_LIMIT)
2634                         set_extra_nomod_vsl(other_name, other_sym, vsl, NULL, alloc_estate_rl(new));
2635                 else
2636                         set_extra_mod(other_name, other_sym, NULL, alloc_estate_rl(new));
2637         }
2638 
2639         if (op == PARAM_LIMIT && arg->type == EXPR_BINOP)
2640                 db_param_limit_binops(arg, key, new);
2641 free:
2642         free_string(name);
2643 }
2644 
2645 static void db_param_limit(struct expression *expr, int param, char *key, char *value)
2646 {
2647         db_param_limit_filter(expr, param, key, value, PARAM_LIMIT);
2648 }
2649 
2650 static void db_param_filter(struct expression *expr, int param, char *key, char *value)
2651 {
2652         db_param_limit_filter(expr, param, key, value, PARAM_FILTER);
2653 }
2654 
2655 static void db_param_add_set(struct expression *expr, int param, char *key, char *value, enum info_type op)
2656 {
2657         struct expression *arg, *gen_expr;
2658         char *name;
2659         char *other_name = NULL;
2660         struct symbol *sym, *other_sym;
2661         struct symbol *param_type, *arg_type;
2662         struct smatch_state *state;
2663         struct range_list *new = NULL;
2664         struct range_list *added = NULL;
2665 
2666         while (expr->type == EXPR_ASSIGNMENT)
2667                 expr = strip_expr(expr->right);
2668         if (expr->type != EXPR_CALL)
2669                 return;
2670 
2671         arg = get_argument_from_call_expr(expr->args, param);
2672         if (!arg)
2673                 return;
2674 
2675         arg_type = get_arg_type_from_key(expr->fn, param, arg, key);
2676         param_type = get_member_type_from_key(arg, key);
2677         if (param_type && param_type->type == SYM_STRUCT)
2678                 return;
2679         name = get_variable_from_key(arg, key, &sym);
2680         if (!name || !sym)
2681                 goto free;
2682         gen_expr = gen_expression_from_key(arg, key);
2683 
2684         state = get_state(SMATCH_EXTRA, name, sym);
2685         if (state)
2686                 new = estate_rl(state);
2687 
2688         call_results_to_rl(expr, arg_type, value, &added);
2689         added = cast_rl(param_type, added);
2690         if (op == PARAM_SET)
2691                 new = added;
2692         else
2693                 new = rl_union(new, added);
2694 
2695         other_name = get_other_name_sym_nostack(name, sym, &other_sym);
2696         set_extra_mod(name, sym, gen_expr, alloc_estate_rl(new));
2697         if (other_name && other_sym)
2698                 set_extra_mod(other_name, other_sym, gen_expr, alloc_estate_rl(new));
2699 free:
2700         free_string(other_name);
2701         free_string(name);
2702 }
2703 
2704 static void db_param_add(struct expression *expr, int param, char *key, char *value)
2705 {
2706         in_param_set = true;
2707         db_param_add_set(expr, param, key, value, PARAM_ADD);
2708         in_param_set = false;
2709 }
2710 
2711 static void db_param_set(struct expression *expr, int param, char *key, char *value)
2712 {
2713         in_param_set = true;
2714         db_param_add_set(expr, param, key, value, PARAM_SET);
2715         in_param_set = false;
2716 }
2717 
2718 static void match_lost_param(struct expression *call, int param)
2719 {
2720         struct expression *arg;
2721 
2722         if (is_const_param(call->fn, param))
2723                 return;
2724 
2725         arg = get_argument_from_call_expr(call->args, param);
2726         if (!arg)
2727                 return;
2728 
2729         arg = strip_expr(arg);
2730         if (arg->type == EXPR_PREOP && arg->op == '&')
2731                 set_extra_expr_mod(arg->unop, alloc_estate_whole(get_type(arg->unop)));
2732         else
2733                 ; /* if pointer then set struct members, maybe?*/
2734 }
2735 
2736 static void db_param_value(struct expression *expr, int param, char *key, char *value)
2737 {
2738         struct expression *call;
2739         char *name;
2740         struct symbol *sym;
2741         struct symbol *type;
2742         struct range_list *rl = NULL;
2743 
2744         if (param != -1)
2745                 return;
2746 
2747         call = expr;
2748         while (call->type == EXPR_ASSIGNMENT)
2749                 call = strip_expr(call->right);
2750         if (call->type != EXPR_CALL)
2751                 return;
2752 
2753         type = get_member_type_from_key(expr->left, key);
2754         name = get_variable_from_key(expr->left, key, &sym);
2755         if (!name || !sym)
2756                 goto free;
2757 
2758         call_results_to_rl(call, type, value, &rl);
2759 
2760         set_extra_mod(name, sym, NULL, alloc_estate_rl(rl));
2761 free:
2762         free_string(name);
2763 }
2764 
2765 static void match_call_info(struct expression *expr)
2766 {
2767         struct smatch_state *state;
2768         struct range_list *rl = NULL;
2769         struct expression *arg;
2770         struct symbol *type;
2771         sval_t dummy;
2772         int i = 0;
2773 
2774         FOR_EACH_PTR(expr->args, arg) {
2775                 type = get_arg_type(expr->fn, i);
2776 
2777                 get_absolute_rl(arg, &rl);
2778                 rl = cast_rl(type, rl);
2779 
2780                 if (!is_whole_rl(rl)) {
2781                         rl = intersect_with_real_abs_expr(arg, rl);
2782                         sql_insert_caller_info(expr, PARAM_VALUE, i, "$", show_rl(rl));
2783                 }
2784                 state = get_state_expr(SMATCH_EXTRA, arg);
2785                 if (!estate_get_single_value(state, &dummy) && estate_has_hard_max(state)) {
2786                         sql_insert_caller_info(expr, HARD_MAX, i, "$",
2787                                                sval_to_str(estate_max(state)));
2788                 }
2789                 if (estate_has_fuzzy_max(state)) {
2790                         sql_insert_caller_info(expr, FUZZY_MAX, i, "$",
2791                                                sval_to_str(estate_get_fuzzy_max(state)));
2792                 }
2793                 i++;
2794         } END_FOR_EACH_PTR(arg);
2795 }
2796 
2797 static void set_param_value(const char *name, struct symbol *sym, char *key, char *value)
2798 {
2799         struct expression *expr;
2800         struct range_list *rl = NULL;
2801         struct smatch_state *state;
2802         struct symbol *type;
2803         char fullname[256];
2804         char *key_orig = key;
2805         bool add_star = false;
2806         sval_t dummy;
2807 
2808         if (key[0] == '*') {
2809                 add_star = true;
2810                 key++;
2811         }
2812 
2813         snprintf(fullname, 256, "%s%s%s", add_star ? "*" : "", name, key + 1);
2814 
2815         expr = symbol_expression(sym);
2816         type = get_member_type_from_key(expr, key_orig);
2817         str_to_rl(type, value, &rl);
2818         state = alloc_estate_rl(rl);
2819         if (estate_get_single_value(state, &dummy))
2820                 estate_set_hard_max(state);
2821         set_state(SMATCH_EXTRA, fullname, sym, state);
2822 }
2823 
2824 static void set_param_fuzzy_max(const char *name, struct symbol *sym, char *key, char *value)
2825 {
2826         struct range_list *rl = NULL;
2827         struct smatch_state *state;
2828         struct symbol *type;
2829         char fullname[256];
2830         sval_t max;
2831 
2832         if (strcmp(key, "*$") == 0)
2833                 snprintf(fullname, sizeof(fullname), "*%s", name);
2834         else if (strncmp(key, "$", 1) == 0)
2835                 snprintf(fullname, 256, "%s%s", name, key + 1);
2836         else
2837                 return;
2838 
2839         state = get_state(SMATCH_EXTRA, fullname, sym);
2840         if (!state)
2841                 return;
2842         type = estate_type(state);
2843         str_to_rl(type, value, &rl);
2844         if (!rl_to_sval(rl, &max))
2845                 return;
2846         estate_set_fuzzy_max(state, max);
2847 }
2848 
2849 static void set_param_hard_max(const char *name, struct symbol *sym, char *key, char *value)
2850 {
2851         struct smatch_state *state;
2852         char fullname[256];
2853 
2854         if (strcmp(key, "*$") == 0)
2855                 snprintf(fullname, sizeof(fullname), "*%s", name);
2856         else if (strncmp(key, "$", 1) == 0)
2857                 snprintf(fullname, 256, "%s%s", name, key + 1);
2858         else
2859                 return;
2860 
2861         state = get_state(SMATCH_EXTRA, fullname, sym);
2862         if (!state)
2863                 return;
2864         estate_set_hard_max(state);
2865 }
2866 
2867 struct sm_state *get_extra_sm_state(struct expression *expr)
2868 {
2869         char *name;
2870         struct symbol *sym;
2871         struct sm_state *ret = NULL;
2872 
2873         name = expr_to_known_chunk_sym(expr, &sym);
2874         if (!name)
2875                 goto free;
2876 
2877         ret = get_sm_state(SMATCH_EXTRA, name, sym);
2878 free:
2879         free_string(name);
2880         return ret;
2881 }
2882 
2883 struct smatch_state *get_extra_state(struct expression *expr)
2884 {
2885         struct sm_state *sm;
2886 
2887         sm = get_extra_sm_state(expr);
2888         if (!sm)
2889                 return NULL;
2890         return sm->state;
2891 }
2892 
2893 void register_smatch_extra(int id)
2894 {
2895         my_id = id;
2896 
2897         set_dynamic_states(my_id);
2898         add_merge_hook(my_id, &merge_estates);
2899         add_unmatched_state_hook(my_id, &unmatched_state);
2900         select_caller_info_hook(set_param_value, PARAM_VALUE);
2901         select_caller_info_hook(set_param_fuzzy_max, FUZZY_MAX);
2902         select_caller_info_hook(set_param_hard_max, HARD_MAX);
2903         select_return_states_before(&db_limited_before);
2904         select_return_states_hook(PARAM_LIMIT, &db_param_limit);
2905         select_return_states_hook(PARAM_FILTER, &db_param_filter);
2906         select_return_states_hook(PARAM_ADD, &db_param_add);
2907         select_return_states_hook(PARAM_SET, &db_param_set);
2908         add_lost_param_hook(&match_lost_param);
2909         select_return_states_hook(PARAM_VALUE, &db_param_value);
2910         select_return_states_after(&db_limited_after);
2911 }
2912 
2913 static void match_link_modify(struct sm_state *sm, struct expression *mod_expr)
2914 {
2915         struct var_sym_list *links;
2916         struct var_sym *tmp;
2917         struct smatch_state *state;
2918 
2919         links = sm->state->data;
2920 
2921         FOR_EACH_PTR(links, tmp) {
2922                 if (sm->sym == tmp->sym &&
2923                     strcmp(sm->name, tmp->var) == 0)
2924                         continue;
2925                 state = get_state(SMATCH_EXTRA, tmp->var, tmp->sym);
2926                 if (!state)
2927                         continue;
2928                 set_state(SMATCH_EXTRA, tmp->var, tmp->sym, alloc_estate_whole(estate_type(state)));
2929         } END_FOR_EACH_PTR(tmp);
2930         set_state(link_id, sm->name, sm->sym, &undefined);
2931 }
2932 
2933 void register_smatch_extra_links(int id)
2934 {
2935         link_id = id;
2936         set_dynamic_states(link_id);
2937 }
2938 
2939 void register_smatch_extra_late(int id)
2940 {
2941         add_merge_hook(link_id, &merge_link_states);
2942         add_modification_hook(link_id, &match_link_modify);
2943         add_hook(&match_dereferences, DEREF_HOOK);
2944         add_hook(&match_pointer_as_array, OP_HOOK);
2945         select_return_implies_hook(DEREFERENCE, &set_param_dereferenced);
2946         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
2947         add_hook(&match_assign, ASSIGNMENT_HOOK);
2948         add_hook(&match_assign, GLOBAL_ASSIGNMENT_HOOK);
2949         add_hook(&unop_expr, OP_HOOK);
2950         add_hook(&asm_expr, ASM_HOOK);
2951 
2952         add_hook(&match_call_info, FUNCTION_CALL_HOOK);
2953         add_member_info_callback(my_id, struct_member_callback);
2954         add_split_return_callback(&returned_struct_members);
2955 
2956 //      add_hook(&assume_indexes_are_valid, OP_HOOK);
2957 }