smatch_function_hooks.c

   1 /*
   2  * Copyright (C) 2009 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  * There are several types of function hooks:
  20  * add_function_hook()        - For any time a function is called.
  21  * add_function_assign_hook() - foo = the_function().
  22  * add_implied_return_hook()  - Calculates the implied return value.
  23  * add_macro_assign_hook()    - foo = the_macro().
  24  * return_implies_state()     - For when a return value of 1 implies locked
  25  *                              and 0 implies unlocked. etc. etc.
  26  *
  27  */
  28
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include "smatch.h"
  32 #include "smatch_slist.h"
  33 #include "smatch_extra.h"
  34 #include "smatch_function_hashtable.h"
  35
  36 struct fcall_back {
  37         int type;
  38         struct data_range *range;
  39         union {
  40                 func_hook *call_back;
  41                 implication_hook *ranged;
  42                 implied_return_hook *implied_return;
  43         } u;
  44         void *info;
  45 };
  46
  47 ALLOCATOR(fcall_back, "call backs");
  48 DECLARE_PTR_LIST(call_back_list, struct fcall_back);
  49
  50 DEFINE_FUNCTION_HASHTABLE_STATIC(callback, struct fcall_back, struct call_back_list);
  51 static struct hashtable *func_hash;
  52
  53 int __in_fake_parameter_assign;
  54
  55 #define REGULAR_CALL       0
  56 #define RANGED_CALL        1
  57 #define ASSIGN_CALL        2
  58 #define IMPLIED_RETURN     3
  59 #define MACRO_ASSIGN       4
  60 #define MACRO_ASSIGN_EXTRA 5
  61
  62 struct return_implies_callback {
  63         int type;
  64         return_implies_hook *callback;
  65 };
  66 ALLOCATOR(return_implies_callback, "return_implies callbacks");
  67 DECLARE_PTR_LIST(db_implies_list, struct return_implies_callback);
  68 static struct db_implies_list *db_return_states_list;
  69
  70 typedef void (void_fn)(void);
  71 DECLARE_PTR_LIST(void_fn_list, void_fn *);
  72 static struct void_fn_list *return_states_before;
  73 static struct void_fn_list *return_states_after;
  74
  75 static struct fcall_back *alloc_fcall_back(int type, void *call_back,
  76                                            void *info)
  77 {
  78         struct fcall_back *cb;
  79
  80         cb = __alloc_fcall_back(0);
  81         cb->type = type;
  82         cb->u.call_back = call_back;
  83         cb->info = info;
  84         return cb;
  85 }
  86
  87 void add_function_hook(const char *look_for, func_hook *call_back, void *info)
  88 {
  89         struct fcall_back *cb;
  90
  91         cb = alloc_fcall_back(REGULAR_CALL, call_back, info);
  92         add_callback(func_hash, look_for, cb);
  93 }
  94
  95 void add_function_assign_hook(const char *look_for, func_hook *call_back,
  96                               void *info)
  97 {
  98         struct fcall_back *cb;
  99
 100         cb = alloc_fcall_back(ASSIGN_CALL, call_back, info);
 101         add_callback(func_hash, look_for, cb);
 102 }
 103
 104 void add_implied_return_hook(const char *look_for,
 105                              implied_return_hook *call_back,
 106                              void *info)
 107 {
 108         struct fcall_back *cb;
 109
 110         cb = alloc_fcall_back(IMPLIED_RETURN, call_back, info);
 111         add_callback(func_hash, look_for, cb);
 112 }
 113
 114 void add_macro_assign_hook(const char *look_for, func_hook *call_back,
 115                         void *info)
 116 {
 117         struct fcall_back *cb;
 118
 119         cb = alloc_fcall_back(MACRO_ASSIGN, call_back, info);
 120         add_callback(func_hash, look_for, cb);
 121 }
 122
 123 void add_macro_assign_hook_extra(const char *look_for, func_hook *call_back,
 124                         void *info)
 125 {
 126         struct fcall_back *cb;
 127
 128         cb = alloc_fcall_back(MACRO_ASSIGN_EXTRA, call_back, info);
 129         add_callback(func_hash, look_for, cb);
 130 }
 131
 132 void return_implies_state(const char *look_for, long long start, long long end,
 133                          implication_hook *call_back, void *info)
 134 {
 135         struct fcall_back *cb;
 136
 137         cb = alloc_fcall_back(RANGED_CALL, call_back, info);
 138         cb->range = alloc_range_perm(ll_to_sval(start), ll_to_sval(end));
 139         add_callback(func_hash, look_for, cb);
 140 }
 141
 142 void select_return_states_hook(int type, return_implies_hook *callback)
 143 {
 144         struct return_implies_callback *cb = __alloc_return_implies_callback(0);
 145
 146         cb->type = type;
 147         cb->callback = callback;
 148         add_ptr_list(&db_return_states_list, cb);
 149 }
 150
 151 void select_return_states_before(void_fn *fn)
 152 {
 153         void_fn **p = malloc(sizeof(void_fn *));
 154         *p = fn;
 155         add_ptr_list(&return_states_before, p);
 156 }
 157
 158 void select_return_states_after(void_fn *fn)
 159 {
 160         void_fn **p = malloc(sizeof(void_fn *));
 161         *p = fn;
 162         add_ptr_list(&return_states_after, p);
 163 }
 164
 165 static void call_return_states_before_hooks(void)
 166 {
 167         void_fn **fn;
 168
 169         FOR_EACH_PTR(return_states_before, fn) {
 170                 (*fn)();
 171         } END_FOR_EACH_PTR(fn);
 172 }
 173
 174 static void call_return_states_after_hooks(struct expression *expr)
 175 {
 176         void_fn **fn;
 177
 178         FOR_EACH_PTR(return_states_after, fn) {
 179                 (*fn)();
 180         } END_FOR_EACH_PTR(fn);
 181         __pass_to_client(expr, FUNCTION_CALL_HOOK_AFTER_DB);
 182 }
 183
 184 static int call_call_backs(struct call_back_list *list, int type,
 185                             const char *fn, struct expression *expr)
 186 {
 187         struct fcall_back *tmp;
 188         int handled = 0;
 189
 190         FOR_EACH_PTR(list, tmp) {
 191                 if (tmp->type == type) {
 192                         (tmp->u.call_back)(fn, expr, tmp->info);
 193                         handled = 1;
 194                 }
 195         } END_FOR_EACH_PTR(tmp);
 196
 197         return handled;
 198 }
 199
 200 static void call_ranged_call_backs(struct call_back_list *list,
 201                                 const char *fn, struct expression *call_expr,
 202                                 struct expression *assign_expr)
 203 {
 204         struct fcall_back *tmp;
 205
 206         FOR_EACH_PTR(list, tmp) {
 207                 (tmp->u.ranged)(fn, call_expr, assign_expr, tmp->info);
 208         } END_FOR_EACH_PTR(tmp);
 209 }
 210
 211 static struct call_back_list *get_same_ranged_call_backs(struct call_back_list *list,
 212                                                 struct data_range *drange)
 213 {
 214         struct call_back_list *ret = NULL;
 215         struct fcall_back *tmp;
 216
 217         FOR_EACH_PTR(list, tmp) {
 218                 if (tmp->type != RANGED_CALL)
 219                         continue;
 220                 if (ranges_equiv(tmp->range, drange))
 221                         add_ptr_list(&ret, tmp);
 222         } END_FOR_EACH_PTR(tmp);
 223         return ret;
 224 }
 225
 226 static int in_list_exact_sval(struct range_list *list, struct data_range *drange)
 227 {
 228         struct data_range *tmp;
 229
 230         FOR_EACH_PTR(list, tmp) {
 231                 if (ranges_equiv(tmp, drange))
 232                         return 1;
 233         } END_FOR_EACH_PTR(tmp);
 234         return 0;
 235 }
 236
 237 static int assign_ranged_funcs(const char *fn, struct expression *expr,
 238                                  struct call_back_list *call_backs)
 239 {
 240         struct fcall_back *tmp;
 241         struct sm_state *sm;
 242         char *var_name;
 243         struct symbol *sym;
 244         struct smatch_state *estate;
 245         struct stree *tmp_stree;
 246         struct stree *final_states = NULL;
 247         struct range_list *handled_ranges = NULL;
 248         struct call_back_list *same_range_call_backs = NULL;
 249         struct range_list *rl;
 250         int handled = 0;
 251
 252         if (!call_backs)
 253                 return 0;
 254
 255         var_name = expr_to_var_sym(expr->left, &sym);
 256         if (!var_name || !sym)
 257                 goto free;
 258
 259         FOR_EACH_PTR(call_backs, tmp) {
 260                 if (tmp->type != RANGED_CALL)
 261                         continue;
 262
 263                 if (in_list_exact_sval(handled_ranges, tmp->range))
 264                         continue;
 265                 __push_fake_cur_stree();
 266                 tack_on(&handled_ranges, tmp->range);
 267
 268                 same_range_call_backs = get_same_ranged_call_backs(call_backs, tmp->range);
 269                 call_ranged_call_backs(same_range_call_backs, fn, expr->right, expr);
 270                 __free_ptr_list((struct ptr_list **)&same_range_call_backs);
 271
 272                 rl = alloc_rl(tmp->range->min, tmp->range->max);
 273                 rl = cast_rl(get_type(expr->left), rl);
 274                 estate = alloc_estate_rl(rl);
 275                 set_extra_mod(var_name, sym, expr->left, estate);
 276
 277                 tmp_stree = __pop_fake_cur_stree();
 278                 merge_fake_stree(&final_states, tmp_stree);
 279                 free_stree(&tmp_stree);
 280                 handled = 1;
 281         } END_FOR_EACH_PTR(tmp);
 282
 283         FOR_EACH_SM(final_states, sm) {
 284                 __set_sm(sm);
 285         } END_FOR_EACH_SM(sm);
 286
 287         free_stree(&final_states);
 288 free:
 289         free_string(var_name);
 290         return handled;
 291 }
 292
 293 static void call_implies_callbacks(int comparison, struct expression *expr, sval_t sval, int left, struct stree **implied_true, struct stree **implied_false)
 294 {
 295         struct call_back_list *call_backs;
 296         struct fcall_back *tmp;
 297         const char *fn;
 298         struct data_range *value_range;
 299         struct stree *true_states = NULL;
 300         struct stree *false_states = NULL;
 301         struct stree *tmp_stree;
 302
 303         *implied_true = NULL;
 304         *implied_false = NULL;
 305         if (expr->fn->type != EXPR_SYMBOL || !expr->fn->symbol)
 306                 return;
 307         fn = expr->fn->symbol->ident->name;
 308         call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
 309         if (!call_backs)
 310                 return;
 311         value_range = alloc_range(sval, sval);
 312
 313         /* set true states */
 314         __push_fake_cur_stree();
 315         FOR_EACH_PTR(call_backs, tmp) {
 316                 if (tmp->type != RANGED_CALL)
 317                         continue;
 318                 if (!true_comparison_range_LR(comparison, tmp->range, value_range, left))
 319                         continue;
 320                 (tmp->u.ranged)(fn, expr, NULL, tmp->info);
 321         } END_FOR_EACH_PTR(tmp);
 322         tmp_stree = __pop_fake_cur_stree();
 323         merge_fake_stree(&true_states, tmp_stree);
 324         free_stree(&tmp_stree);
 325
 326         /* set false states */
 327         __push_fake_cur_stree();
 328         FOR_EACH_PTR(call_backs, tmp) {
 329                 if (tmp->type != RANGED_CALL)
 330                         continue;
 331                 if (!false_comparison_range_LR(comparison, tmp->range, value_range, left))
 332                         continue;
 333                 (tmp->u.ranged)(fn, expr, NULL, tmp->info);
 334         } END_FOR_EACH_PTR(tmp);
 335         tmp_stree = __pop_fake_cur_stree();
 336         merge_fake_stree(&false_states, tmp_stree);
 337         free_stree(&tmp_stree);
 338
 339         *implied_true = true_states;
 340         *implied_false = false_states;
 341 }
 342
 343 struct db_callback_info {
 344         int true_side;
 345         int comparison;
 346         struct expression *expr;
 347         struct range_list *rl;
 348         int left;
 349         struct stree *stree;
 350         struct db_implies_list *callbacks;
 351         int prev_return_id;
 352         int cull;
 353         int has_states;
 354         char *ret_str;
 355         struct smatch_state *ret_state;
 356         struct expression *var_expr;
 357         int handled;
 358 };
 359
 360 static void store_return_state(struct db_callback_info *db_info, const char *ret_str, struct smatch_state *state)
 361 {
 362         db_info->ret_str = alloc_sname(ret_str),
 363         db_info->ret_state = state;
 364 }
 365
 366 static bool fake_a_param_assignment(struct expression *expr, const char *return_str)
 367 {
 368         struct expression *arg, *left, *right, *fake_assign;
 369         char *p;
 370         int param;
 371         char buf[256];
 372         char *str;
 373
 374         if (expr->type != EXPR_ASSIGNMENT || expr->op != '=')
 375                 return false;
 376         left = expr->left;
 377         right = expr->right;
 378
 379         while (right->type == EXPR_ASSIGNMENT)
 380                 right = strip_expr(right->right);
 381         if (!right || right->type != EXPR_CALL)
 382                 return false;
 383
 384         p = strchr(return_str, '[');
 385         if (!p)
 386                 return false;
 387
 388         p++;
 389         if (p[0] == '=' && p[1] == '=')
 390                 p += 2;
 391         if (p[0] != '$')
 392                 return false;
 393
 394         snprintf(buf, sizeof(buf), "%s", p);
 395
 396         p = buf;
 397         p += 1;
 398         param = strtol(p, &p, 10);
 399
 400         p = strchr(p, ']');
 401         if (!p || *p != ']')
 402                 return false;
 403         *p = '\0';
 404
 405         arg = get_argument_from_call_expr(right->args, param);
 406         if (!arg)
 407                 return false;
 408         /*
 409          * This is a sanity check to prevent side effects from evaluating stuff
 410          * twice.
 411          */
 412         str = expr_to_chunk_sym_vsl(arg, NULL, NULL);
 413         if (!str)
 414                 return false;
 415         free_string(str);
 416
 417         right = gen_expression_from_key(arg, buf);
 418         if (!right)  /* Mostly fails for binops like [$0 + 4032] */
 419                 return false;
 420         fake_assign = assign_expression(left, '=', right);
 421         __in_fake_parameter_assign++;
 422         __split_expr(fake_assign);
 423         __in_fake_parameter_assign--;
 424         return true;
 425 }
 426
 427 static void set_return_assign_state(struct db_callback_info *db_info)
 428 {
 429         struct expression *expr = db_info->expr->left;
 430         struct smatch_state *state;
 431
 432         if (!db_info->ret_state)
 433                 return;
 434
 435         state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
 436         set_extra_expr_mod(expr, state);
 437         db_info->ret_state = NULL;
 438         fake_a_param_assignment(db_info->expr, db_info->ret_str);
 439         db_info->ret_str = NULL;
 440 }
 441
 442 static void set_other_side_state(struct db_callback_info *db_info)
 443 {
 444         struct expression *expr = db_info->var_expr;
 445         struct smatch_state *state;
 446
 447         if (!db_info->ret_state)
 448                 return;
 449
 450         state = alloc_estate_rl(cast_rl(get_type(expr), clone_rl(estate_rl(db_info->ret_state))));
 451         set_extra_expr_nomod(expr, state);
 452         db_info->ret_state = NULL;
 453         db_info->ret_str = NULL;
 454 }
 455
 456 static void handle_ret_equals_param(char *ret_string, struct range_list *rl, struct expression *call)
 457 {
 458         char *str;
 459         long long param;
 460         struct expression *arg;
 461         struct range_list *orig;
 462
 463         str = strstr(ret_string, "==$");
 464         if (!str)
 465                 return;
 466         str += 3;
 467         param = strtoll(str, NULL, 10);
 468         arg = get_argument_from_call_expr(call->args, param);
 469         if (!arg)
 470                 return;
 471         get_absolute_rl(arg, &orig);
 472         rl = rl_intersection(orig, rl);
 473         if (!rl)
 474                 return;
 475         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 476 }
 477
 478 static int impossible_limit(struct expression *expr, int param, char *key, char *value)
 479 {
 480         struct expression *arg;
 481         struct smatch_state *state;
 482         struct range_list *passed;
 483         struct range_list *limit;
 484         struct symbol *compare_type;
 485
 486         while (expr->type == EXPR_ASSIGNMENT)
 487                 expr = strip_expr(expr->right);
 488         if (expr->type != EXPR_CALL)
 489                 return 0;
 490
 491         arg = get_argument_from_call_expr(expr->args, param);
 492         if (!arg)
 493                 return 0;
 494
 495         if (strcmp(key, "$") == 0) {
 496                 if (!get_implied_rl(arg, &passed))
 497                         return 0;
 498
 499                 compare_type = get_arg_type(expr->fn, param);
 500         } else {
 501                 char *name;
 502                 struct symbol *sym;
 503
 504                 name = get_variable_from_key(arg, key, &sym);
 505                 if (!name || !sym)
 506                         return 0;
 507
 508                 state = get_state(SMATCH_EXTRA, name, sym);
 509                 if (!state) {
 510                         free_string(name);
 511                         return 0;
 512                 }
 513                 passed = estate_rl(state);
 514                 if (!passed || is_whole_rl(passed)) {
 515                         free_string(name);
 516                         return 0;
 517                 }
 518
 519                 compare_type = get_member_type_from_key(arg, key);
 520         }
 521
 522         passed = cast_rl(compare_type, passed);
 523         call_results_to_rl(expr, compare_type, value, &limit);
 524         if (!limit || is_whole_rl(limit))
 525                 return 0;
 526         if (possibly_true_rl(passed, SPECIAL_EQUAL, limit))
 527                 return 0;
 528         if (option_debug || local_debug)
 529                 sm_msg("impossible: %d '%s' limit '%s' == '%s'", param, key, show_rl(passed), value);
 530         return 1;
 531 }
 532
 533 static int is_impossible_data(int type, struct expression *expr, int param, char *key, char *value)
 534 {
 535         if (type == PARAM_LIMIT && impossible_limit(expr, param, key, value))
 536                 return 1;
 537         if (type == COMPARE_LIMIT && param_compare_limit_is_impossible(expr, param, key, value)) {
 538                 if (local_debug)
 539                         sm_msg("param_compare_limit_is_impossible: %d %s %s", param, key, value);
 540                 return 1;
 541         }
 542         return 0;
 543 }
 544
 545 static int func_type_mismatch(struct expression *expr, const char *value)
 546 {
 547         struct symbol *type;
 548
 549         /* This makes faking returns easier */
 550         if (!value || value[0] == '\0')
 551                 return 0;
 552
 553         while (expr->type == EXPR_ASSIGNMENT)
 554                 expr = strip_expr(expr->right);
 555
 556         /*
 557          * Short cut:  We only care about function pointers that are struct
 558          * members.
 559          *
 560          */
 561         if (expr->fn->type == EXPR_SYMBOL)
 562                 return 0;
 563
 564         type = get_type(expr->fn);
 565         if (!type)
 566                 return 0;
 567         if (type->type == SYM_PTR)
 568                 type = get_real_base_type(type);
 569
 570         if (strcmp(type_to_str(type), value) == 0)
 571                 return 0;
 572
 573         return 1;
 574 }
 575
 576 static int db_compare_callback(void *_info, int argc, char **argv, char **azColName)
 577 {
 578         struct db_callback_info *db_info = _info;
 579         struct range_list *var_rl = db_info->rl;
 580         struct range_list *ret_range;
 581         int type, param;
 582         char *key, *value;
 583         struct return_implies_callback *tmp;
 584         struct stree *stree;
 585         int return_id;
 586         int comparison;
 587
 588         if (argc != 6)
 589                 return 0;
 590
 591         return_id = atoi(argv[0]);
 592         type = atoi(argv[2]);
 593         param = atoi(argv[3]);
 594         key = argv[4];
 595         value = argv[5];
 596
 597         db_info->has_states = 1;
 598         if (db_info->prev_return_id != -1 && type == INTERNAL) {
 599                 set_other_side_state(db_info);
 600                 stree = __pop_fake_cur_stree();
 601
 602                 if (!db_info->cull)
 603                         merge_fake_stree(&db_info->stree, stree);
 604                 free_stree(&stree);
 605                 __push_fake_cur_stree();
 606                 db_info->cull = 0;
 607         }
 608         db_info->prev_return_id = return_id;
 609
 610         if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
 611                 db_info->cull = 1;
 612         if (db_info->cull)
 613                 return 0;
 614         if (type == CULL_PATH) {
 615                 db_info->cull = 1;
 616                 return 0;
 617         }
 618
 619         if (is_impossible_data(type, db_info->expr, param, key, value)) {
 620                 db_info->cull = 1;
 621                 return 0;
 622         }
 623
 624         call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), argv[1], &ret_range);
 625         ret_range = cast_rl(get_type(db_info->expr), ret_range);
 626         if (!ret_range)
 627                 ret_range = alloc_whole_rl(get_type(db_info->expr));
 628
 629         comparison = db_info->comparison;
 630         if (db_info->left)
 631                 comparison = flip_comparison(comparison);
 632
 633         if (db_info->true_side) {
 634                 if (!possibly_true_rl(var_rl, comparison, ret_range))
 635                         return 0;
 636                 if (type == PARAM_LIMIT)
 637                         param_limit_implications(db_info->expr, param, key, value);
 638                 filter_by_comparison(&var_rl, comparison, ret_range);
 639                 filter_by_comparison(&ret_range, flip_comparison(comparison), var_rl);
 640         } else {
 641                 if (!possibly_false_rl(var_rl, comparison, ret_range))
 642                         return 0;
 643                 if (type == PARAM_LIMIT)
 644                         param_limit_implications(db_info->expr, param, key, value);
 645                 filter_by_comparison(&var_rl, negate_comparison(comparison), ret_range);
 646                 filter_by_comparison(&ret_range, flip_comparison(negate_comparison(comparison)), var_rl);
 647         }
 648
 649         handle_ret_equals_param(argv[1], ret_range, db_info->expr);
 650
 651         if (type == INTERNAL) {
 652                 set_state(-1, "unnull_path", NULL, &true_state);
 653                 __add_return_comparison(strip_expr(db_info->expr), argv[1]);
 654                 __add_return_to_param_mapping(db_info->expr, argv[1]);
 655                 store_return_state(db_info, argv[1], alloc_estate_rl(clone_rl(var_rl)));
 656         }
 657
 658         FOR_EACH_PTR(db_info->callbacks, tmp) {
 659                 if (tmp->type == type)
 660                         tmp->callback(db_info->expr, param, key, value);
 661         } END_FOR_EACH_PTR(tmp);
 662
 663         return 0;
 664 }
 665
 666 static void compare_db_return_states_callbacks(struct expression *left, int comparison, struct expression *right, struct stree *implied_true, struct stree *implied_false)
 667 {
 668         struct stree *orig_states;
 669         struct stree *stree;
 670         struct stree *true_states;
 671         struct stree *false_states;
 672         struct sm_state *sm;
 673         struct db_callback_info db_info = {};
 674         struct expression *var_expr;
 675         struct expression *call_expr;
 676         struct range_list *rl;
 677         int call_on_left;
 678
 679         orig_states = clone_stree(__get_cur_stree());
 680
 681         /* legacy cruft.  need to fix call_implies_callbacks(). */
 682         call_on_left = 1;
 683         call_expr = left;
 684         var_expr = right;
 685         if (left->type != EXPR_CALL) {
 686                 call_on_left = 0;
 687                 call_expr = right;
 688                 var_expr = left;
 689         }
 690
 691         get_absolute_rl(var_expr, &rl);
 692
 693         db_info.comparison = comparison;
 694         db_info.expr = call_expr;
 695         db_info.rl = rl;
 696         db_info.left = call_on_left;
 697         db_info.callbacks = db_return_states_list;
 698         db_info.var_expr = var_expr;
 699
 700         call_return_states_before_hooks();
 701
 702         db_info.true_side = 1;
 703         db_info.stree = NULL;
 704         db_info.prev_return_id = -1;
 705         __push_fake_cur_stree();
 706         sql_select_return_states("return_id, return, type, parameter, key, value",
 707                                  call_expr, db_compare_callback, &db_info);
 708         set_other_side_state(&db_info);
 709         stree = __pop_fake_cur_stree();
 710         if (!db_info.cull)
 711                 merge_fake_stree(&db_info.stree, stree);
 712         free_stree(&stree);
 713         true_states = db_info.stree;
 714         if (!true_states && db_info.has_states) {
 715                 __push_fake_cur_stree();
 716                 set_path_impossible();
 717                 true_states = __pop_fake_cur_stree();
 718         }
 719
 720         nullify_path();
 721         __unnullify_path();
 722         FOR_EACH_SM(orig_states, sm) {
 723                 __set_sm_cur_stree(sm);
 724         } END_FOR_EACH_SM(sm);
 725
 726         db_info.true_side = 0;
 727         db_info.stree = NULL;
 728         db_info.prev_return_id = -1;
 729         db_info.cull = 0;
 730         __push_fake_cur_stree();
 731         sql_select_return_states("return_id, return, type, parameter, key, value", call_expr,
 732                         db_compare_callback, &db_info);
 733         set_other_side_state(&db_info);
 734         stree = __pop_fake_cur_stree();
 735         if (!db_info.cull)
 736                 merge_fake_stree(&db_info.stree, stree);
 737         free_stree(&stree);
 738         false_states = db_info.stree;
 739         if (!false_states && db_info.has_states) {
 740                 __push_fake_cur_stree();
 741                 set_path_impossible();
 742                 false_states = __pop_fake_cur_stree();
 743         }
 744
 745         nullify_path();
 746         __unnullify_path();
 747         FOR_EACH_SM(orig_states, sm) {
 748                 __set_sm_cur_stree(sm);
 749         } END_FOR_EACH_SM(sm);
 750
 751         free_stree(&orig_states);
 752
 753         FOR_EACH_SM(true_states, sm) {
 754                 __set_true_false_sm(sm, NULL);
 755         } END_FOR_EACH_SM(sm);
 756         FOR_EACH_SM(false_states, sm) {
 757                 __set_true_false_sm(NULL, sm);
 758         } END_FOR_EACH_SM(sm);
 759
 760         free_stree(&true_states);
 761         free_stree(&false_states);
 762
 763         call_return_states_after_hooks(call_expr);
 764
 765         FOR_EACH_SM(implied_true, sm) {
 766                 __set_true_false_sm(sm, NULL);
 767         } END_FOR_EACH_SM(sm);
 768         FOR_EACH_SM(implied_false, sm) {
 769                 __set_true_false_sm(NULL, sm);
 770         } END_FOR_EACH_SM(sm);
 771 }
 772
 773 void function_comparison(struct expression *left, int comparison, struct expression *right)
 774 {
 775         struct expression *var_expr;
 776         struct expression *call_expr;
 777         struct stree *implied_true = NULL;
 778         struct stree *implied_false = NULL;
 779         struct range_list *rl;
 780         sval_t sval;
 781         int call_on_left;
 782
 783         if (unreachable())
 784                 return;
 785
 786         /* legacy cruft.  need to fix call_implies_callbacks(). */
 787         call_on_left = 1;
 788         call_expr = left;
 789         var_expr = right;
 790         if (left->type != EXPR_CALL) {
 791                 call_on_left = 0;
 792                 call_expr = right;
 793                 var_expr = left;
 794         }
 795
 796         get_absolute_rl(var_expr, &rl);
 797
 798         if (rl_to_sval(rl, &sval))
 799                 call_implies_callbacks(comparison, call_expr, sval, call_on_left, &implied_true, &implied_false);
 800
 801         compare_db_return_states_callbacks(left, comparison, right, implied_true, implied_false);
 802         free_stree(&implied_true);
 803         free_stree(&implied_false);
 804 }
 805
 806 static void call_ranged_return_hooks(struct db_callback_info *db_info)
 807 {
 808         struct call_back_list *call_backs;
 809         struct expression *expr;
 810         struct fcall_back *tmp;
 811         char *fn;
 812
 813         expr = strip_expr(db_info->expr);
 814         while (expr->type == EXPR_ASSIGNMENT)
 815                 expr = strip_expr(expr->right);
 816         if (expr->type != EXPR_CALL ||
 817             expr->fn->type != EXPR_SYMBOL)
 818                 return;
 819
 820         fn = expr->fn->symbol_name->name;
 821
 822         call_backs = search_callback(func_hash, fn);
 823         FOR_EACH_PTR(call_backs, tmp) {
 824                 struct range_list *range_rl = NULL;
 825
 826                 if (tmp->type != RANGED_CALL)
 827                         continue;
 828                 add_range(&range_rl, tmp->range->min, tmp->range->max);
 829                 range_rl = cast_rl(estate_type(db_info->ret_state), range_rl);
 830                 if (possibly_true_rl(range_rl, SPECIAL_EQUAL, estate_rl(db_info->ret_state))) {
 831                         if (!possibly_true_rl(rl_invert(range_rl), SPECIAL_EQUAL, estate_rl(db_info->ret_state)))
 832                                 (tmp->u.ranged)(fn, expr, db_info->expr, tmp->info);
 833                         else
 834                                 db_info->handled = -1;
 835                 }
 836         } END_FOR_EACH_PTR(tmp);
 837 }
 838
 839 static int db_assign_return_states_callback(void *_info, int argc, char **argv, char **azColName)
 840 {
 841         struct db_callback_info *db_info = _info;
 842         struct range_list *ret_range;
 843         int type, param;
 844         char *key, *value;
 845         struct return_implies_callback *tmp;
 846         struct stree *stree;
 847         int return_id;
 848
 849         if (argc != 6)
 850                 return 0;
 851
 852         return_id = atoi(argv[0]);
 853         type = atoi(argv[2]);
 854         param = atoi(argv[3]);
 855         key = argv[4];
 856         value = argv[5];
 857
 858         if (db_info->prev_return_id != -1 && type == INTERNAL) {
 859                 call_ranged_return_hooks(db_info);
 860                 set_return_assign_state(db_info);
 861                 stree = __pop_fake_cur_stree();
 862                 if (!db_info->cull)
 863                         merge_fake_stree(&db_info->stree, stree);
 864                 free_stree(&stree);
 865                 __push_fake_cur_stree();
 866                 db_info->cull = 0;
 867         }
 868         db_info->prev_return_id = return_id;
 869
 870         if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
 871                 db_info->cull = 1;
 872         if (db_info->cull)
 873                 return 0;
 874         if (type == CULL_PATH) {
 875                 db_info->cull = 1;
 876                 return 0;
 877         }
 878         if (is_impossible_data(type, db_info->expr, param, key, value)) {
 879                 db_info->cull = 1;
 880                 return 0;
 881         }
 882
 883         if (type == PARAM_LIMIT)
 884                 param_limit_implications(db_info->expr, param, key, value);
 885
 886         db_info->handled = 1;
 887         call_results_to_rl(db_info->expr->right, get_type(strip_expr(db_info->expr->right)), argv[1], &ret_range);
 888         if (!ret_range)
 889                 ret_range = alloc_whole_rl(get_type(strip_expr(db_info->expr->right)));
 890         ret_range = cast_rl(get_type(db_info->expr->right), ret_range);
 891
 892         if (type == INTERNAL) {
 893                 set_state(-1, "unnull_path", NULL, &true_state);
 894                 __add_return_comparison(strip_expr(db_info->expr->right), argv[1]);
 895                 __add_comparison_info(db_info->expr->left, strip_expr(db_info->expr->right), argv[1]);
 896                 __add_return_to_param_mapping(db_info->expr, argv[1]);
 897                 store_return_state(db_info, argv[1], alloc_estate_rl(ret_range));
 898         }
 899
 900         FOR_EACH_PTR(db_return_states_list, tmp) {
 901                 if (tmp->type == type)
 902                         tmp->callback(db_info->expr, param, key, value);
 903         } END_FOR_EACH_PTR(tmp);
 904
 905         return 0;
 906 }
 907
 908 static int db_return_states_assign(struct expression *expr)
 909 {
 910         struct expression *right;
 911         struct sm_state *sm;
 912         struct stree *stree;
 913         struct db_callback_info db_info = {};
 914
 915         right = strip_expr(expr->right);
 916
 917         db_info.prev_return_id = -1;
 918         db_info.expr = expr;
 919         db_info.stree = NULL;
 920         db_info.handled = 0;
 921
 922         call_return_states_before_hooks();
 923
 924         __push_fake_cur_stree();
 925         sql_select_return_states("return_id, return, type, parameter, key, value",
 926                         right, db_assign_return_states_callback, &db_info);
 927         if (option_debug) {
 928                 sm_msg("%s return_id %d return_ranges %s",
 929                         db_info.cull ? "culled" : "merging",
 930                         db_info.prev_return_id,
 931                         db_info.ret_state ? db_info.ret_state->name : "'<empty>'");
 932         }
 933         if (db_info.handled)
 934                 call_ranged_return_hooks(&db_info);
 935         set_return_assign_state(&db_info);
 936         stree = __pop_fake_cur_stree();
 937         if (!db_info.cull)
 938                 merge_fake_stree(&db_info.stree, stree);
 939         free_stree(&stree);
 940
 941         if (!db_info.stree && db_info.cull) { /* this means we culled everything */
 942                 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left)));
 943                 set_path_impossible();
 944         }
 945         FOR_EACH_SM(db_info.stree, sm) {
 946                 __set_sm(sm);
 947         } END_FOR_EACH_SM(sm);
 948
 949         free_stree(&db_info.stree);
 950         call_return_states_after_hooks(right);
 951
 952         return db_info.handled;
 953 }
 954
 955 static int handle_implied_return(struct expression *expr)
 956 {
 957         struct range_list *rl;
 958
 959         if (!get_implied_return(expr->right, &rl))
 960                 return 0;
 961         rl = cast_rl(get_type(expr->left), rl);
 962         set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
 963         return 1;
 964 }
 965
 966 static void match_assign_call(struct expression *expr)
 967 {
 968         struct call_back_list *call_backs;
 969         const char *fn;
 970         struct expression *right;
 971         int handled = 0;
 972         struct range_list *rl;
 973
 974         if (expr->op != '=')
 975                 return;
 976
 977         right = strip_expr(expr->right);
 978         if (right->fn->type != EXPR_SYMBOL || !right->fn->symbol) {
 979                 handled |= db_return_states_assign(expr);
 980                 if (!handled)
 981                         goto assigned_unknown;
 982                 return;
 983         }
 984         if (is_fake_call(right)) {
 985                 set_extra_expr_mod(expr->left, alloc_estate_whole(get_type(expr->left)));
 986                 return;
 987         }
 988
 989         fn = right->fn->symbol->ident->name;
 990         call_backs = search_callback(func_hash, (char *)fn);
 991
 992         /*
 993          * The ordering here is sort of important.
 994          * One example, of how this matters is that when we do:
 995          *
 996          *      len = strlen(str);
 997          *
 998          * That is handled by smatch_common_functions.c and smatch_strlen.c.
 999          * They use implied_return and function_assign_hook respectively.
1000          * We want to get the implied return first before we do the function
1001          * assignment hook otherwise we end up writing the wrong thing for len
1002          * in smatch_extra.c because we assume that it already holds the
1003          * strlen() when we haven't set it yet.
1004          */
1005
1006         if (db_return_states_assign(expr) == 1)
1007                 handled = 1;
1008         else
1009                 handled = assign_ranged_funcs(fn, expr, call_backs);
1010         handled |= handle_implied_return(expr);
1011
1012
1013         call_call_backs(call_backs, ASSIGN_CALL, fn, expr);
1014
1015         if (handled)
1016                 return;
1017
1018 assigned_unknown:
1019         get_absolute_rl(expr->right, &rl);
1020         rl = cast_rl(get_type(expr->left), rl);
1021         set_extra_expr_mod(expr->left, alloc_estate_rl(rl));
1022 }
1023
1024 static int db_return_states_callback(void *_info, int argc, char **argv, char **azColName)
1025 {
1026         struct db_callback_info *db_info = _info;
1027         struct range_list *ret_range;
1028         int type, param;
1029         char *key, *value;
1030         struct return_implies_callback *tmp;
1031         struct stree *stree;
1032         int return_id;
1033         char buf[64];
1034
1035         if (argc != 6)
1036                 return 0;
1037
1038         return_id = atoi(argv[0]);
1039         type = atoi(argv[2]);
1040         param = atoi(argv[3]);
1041         key = argv[4];
1042         value = argv[5];
1043
1044         if (db_info->prev_return_id != -1 && type == INTERNAL) {
1045                 stree = __pop_fake_cur_stree();
1046                 if (!db_info->cull)
1047                         merge_fake_stree(&db_info->stree, stree);
1048                 free_stree(&stree);
1049                 __push_fake_cur_stree();
1050                 __unnullify_path();
1051                 db_info->cull = 0;
1052         }
1053         db_info->prev_return_id = return_id;
1054
1055         if (type == INTERNAL && func_type_mismatch(db_info->expr, value))
1056                 db_info->cull = 1;
1057         if (db_info->cull)
1058                 return 0;
1059         if (type == CULL_PATH) {
1060                 db_info->cull = 1;
1061                 return 0;
1062         }
1063         if (is_impossible_data(type, db_info->expr, param, key, value)) {
1064                 db_info->cull = 1;
1065                 return 0;
1066         }
1067
1068         if (type == PARAM_LIMIT)
1069                 param_limit_implications(db_info->expr, param, key, value);
1070
1071         call_results_to_rl(db_info->expr, get_type(strip_expr(db_info->expr)), argv[1], &ret_range);
1072         ret_range = cast_rl(get_type(db_info->expr), ret_range);
1073
1074         if (type == INTERNAL) {
1075                 set_state(-1, "unnull_path", NULL, &true_state);
1076                 __add_return_comparison(strip_expr(db_info->expr), argv[1]);
1077                 __add_return_to_param_mapping(db_info->expr, argv[1]);
1078         }
1079
1080
1081         FOR_EACH_PTR(db_return_states_list, tmp) {
1082                 if (tmp->type == type)
1083                         tmp->callback(db_info->expr, param, key, value);
1084         } END_FOR_EACH_PTR(tmp);
1085
1086         /*
1087          * We want to store the return values so that we can split the strees
1088          * in smatch_db.c.  This uses set_state() directly because it's not a
1089          * real smatch_extra state.
1090          */
1091         snprintf(buf, sizeof(buf), "return %p", db_info->expr);
1092         set_state(SMATCH_EXTRA, buf, NULL, alloc_estate_rl(ret_range));
1093
1094         return 0;
1095 }
1096
1097 static void db_return_states(struct expression *expr)
1098 {
1099         struct sm_state *sm;
1100         struct stree *stree;
1101         struct db_callback_info db_info = {};
1102
1103         if (!__get_cur_stree())  /* no return functions */
1104                 return;
1105
1106         db_info.prev_return_id = -1;
1107         db_info.expr = expr;
1108         db_info.stree = NULL;
1109
1110         call_return_states_before_hooks();
1111
1112         __push_fake_cur_stree();
1113         __unnullify_path();
1114         sql_select_return_states("return_id, return, type, parameter, key, value",
1115                         expr, db_return_states_callback, &db_info);
1116         stree = __pop_fake_cur_stree();
1117         if (!db_info.cull)
1118                 merge_fake_stree(&db_info.stree, stree);
1119         free_stree(&stree);
1120
1121         FOR_EACH_SM(db_info.stree, sm) {
1122                 __set_sm(sm);
1123         } END_FOR_EACH_SM(sm);
1124
1125         free_stree(&db_info.stree);
1126         call_return_states_after_hooks(expr);
1127 }
1128
1129 static int is_condition_call(struct expression *expr)
1130 {
1131         struct expression *tmp;
1132
1133         FOR_EACH_PTR_REVERSE(big_condition_stack, tmp) {
1134                 if (expr == tmp || expr_get_parent_expr(expr) == tmp)
1135                         return 1;
1136                 if (tmp->pos.line < expr->pos.line)
1137                         return 0;
1138         } END_FOR_EACH_PTR_REVERSE(tmp);
1139
1140         return 0;
1141 }
1142
1143 static void db_return_states_call(struct expression *expr)
1144 {
1145         if (unreachable())
1146                 return;
1147
1148         if (is_assigned_call(expr))
1149                 return;
1150         if (is_condition_call(expr))
1151                 return;
1152         db_return_states(expr);
1153 }
1154
1155 static void match_function_call(struct expression *expr)
1156 {
1157         struct call_back_list *call_backs;
1158
1159         if (expr->fn->type == EXPR_SYMBOL && expr->fn->symbol) {
1160                 call_backs = search_callback(func_hash, (char *)expr->fn->symbol->ident->name);
1161                 if (call_backs)
1162                         call_call_backs(call_backs, REGULAR_CALL,
1163                                         expr->fn->symbol->ident->name, expr);
1164         }
1165         db_return_states_call(expr);
1166 }
1167
1168 static void match_macro_assign(struct expression *expr)
1169 {
1170         struct call_back_list *call_backs;
1171         const char *macro;
1172         struct expression *right;
1173
1174         right = strip_expr(expr->right);
1175         macro = get_macro_name(right->pos);
1176         call_backs = search_callback(func_hash, (char *)macro);
1177         if (!call_backs)
1178                 return;
1179         call_call_backs(call_backs, MACRO_ASSIGN, macro, expr);
1180         call_call_backs(call_backs, MACRO_ASSIGN_EXTRA, macro, expr);
1181 }
1182
1183 int get_implied_return(struct expression *expr, struct range_list **rl)
1184 {
1185         struct call_back_list *call_backs;
1186         struct fcall_back *tmp;
1187         int handled = 0;
1188         char *fn;
1189
1190         *rl = NULL;
1191
1192         expr = strip_expr(expr);
1193         fn = expr_to_var(expr->fn);
1194         if (!fn)
1195                 goto out;
1196
1197         call_backs = search_callback(func_hash, fn);
1198
1199         FOR_EACH_PTR(call_backs, tmp) {
1200                 if (tmp->type == IMPLIED_RETURN) {
1201                         (tmp->u.implied_return)(expr, tmp->info, rl);
1202                         handled = 1;
1203                 }
1204         } END_FOR_EACH_PTR(tmp);
1205
1206 out:
1207         free_string(fn);
1208         return handled;
1209 }
1210
1211 void create_function_hook_hash(void)
1212 {
1213         func_hash = create_function_hashtable(5000);
1214 }
1215
1216 void register_function_hooks(int id)
1217 {
1218         add_hook(&match_function_call, CALL_HOOK_AFTER_INLINE);
1219         add_hook(&match_assign_call, CALL_ASSIGNMENT_HOOK);
1220         add_hook(&match_macro_assign, MACRO_ASSIGNMENT_HOOK);
1221 }