smatch_extra.c

   1 /*
   2  * sparse/smatch_extra.c
   3  *
   4  * Copyright (C) 2008 Dan Carpenter.
   5  *
   6  * Licensed under the Open Software License version 1.1
   7  *
   8  */
   9
  10 /*
  11  * smatch_extra.c is supposed to track the value of every variable.
  12  */
  13
  14 #include <stdlib.h>
  15 #define __USE_ISOC99
  16 #include <limits.h>
  17 #include "parse.h"
  18 #include "smatch.h"
  19 #include "smatch_slist.h"
  20 #include "smatch_extra.h"
  21
  22 static int my_id;
  23
  24 static struct symbol *cur_func;
  25
  26 struct data_range whole_range = {
  27         .min = LLONG_MIN,
  28         .max = LLONG_MAX,
  29 };
  30
  31 static struct smatch_state *alloc_extra_state_empty()
  32 {
  33         struct smatch_state *state;
  34         struct data_info *dinfo;
  35
  36         dinfo = __alloc_data_info(0);
  37         dinfo->type = DATA_RANGE;
  38         dinfo->value_ranges = NULL;
  39         state = __alloc_smatch_state(0);
  40         state->data = dinfo;
  41         return state;
  42 }
  43
  44 static struct smatch_state *alloc_extra_state_no_name(int val)
  45 {
  46         struct smatch_state *state;
  47
  48         state = __alloc_smatch_state(0);
  49         if (val == UNDEFINED)
  50                 state->data = (void *)alloc_dinfo_range(whole_range.min, whole_range.max);
  51         else
  52                 state->data = (void *)alloc_dinfo_range(val, val);
  53         return state;
  54 }
  55
  56 /* We do this because ->value_ranges is a list */
  57 struct smatch_state *extra_undefined()
  58 {
  59         struct data_info *dinfo;
  60         static struct smatch_state *ret;
  61         static struct symbol *prev_func;
  62
  63         if  (prev_func == cur_func)
  64                 return ret;
  65         prev_func = cur_func;
  66
  67         dinfo = alloc_dinfo_range(whole_range.min, whole_range.max);
  68         ret = __alloc_smatch_state(0);
  69         ret->name = "unknown";
  70         ret->data = dinfo;
  71         return ret;
  72 }
  73
  74 struct smatch_state *alloc_extra_state(int val)
  75 {
  76         struct smatch_state *state;
  77
  78         if (val == UNDEFINED)
  79                 return extra_undefined();
  80         state = alloc_extra_state_no_name(val);
  81         state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
  82         return state;
  83 }
  84
  85 struct smatch_state *alloc_extra_state_range(long long min, long long max)
  86 {
  87         struct smatch_state *state;
  88
  89         if (min == whole_range.min && max == whole_range.max)
  90                 return extra_undefined();
  91         state = __alloc_smatch_state(0);
  92         state->data = (void *)alloc_dinfo_range(min, max);
  93         state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
  94         return state;
  95 }
  96
  97 struct smatch_state *alloc_extra_state_range_list(struct range_list *rl)
  98 {
  99         struct smatch_state *state;
 100
 101         state = __alloc_smatch_state(0);
 102         state->data = (void *)alloc_dinfo_range_list(rl);
 103         state->name = show_ranges(((struct data_info *)state->data)->value_ranges);
 104         return state;
 105 }
 106
 107 struct smatch_state *filter_range(struct smatch_state *orig,
 108                                  long long filter_min, long long filter_max)
 109 {
 110         struct smatch_state *ret;
 111         struct data_info *orig_info;
 112         struct data_info *ret_info;
 113
 114         if (!orig)
 115                 orig = extra_undefined();
 116         orig_info = (struct data_info *)orig->data;
 117         ret = alloc_extra_state_empty();
 118         ret_info = (struct data_info *)ret->data;
 119         ret_info->value_ranges = remove_range(orig_info->value_ranges, filter_min, filter_max);
 120         ret->name = show_ranges(ret_info->value_ranges);
 121         return ret;
 122 }
 123
 124 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
 125 {
 126         return filter_range(orig, num, num);
 127 }
 128
 129 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
 130                                        struct smatch_state *s1,
 131                                        struct smatch_state *s2)
 132 {
 133         struct data_info *info1 = (struct data_info *)s1->data;
 134         struct data_info *info2 = (struct data_info *)s2->data;
 135         struct data_info *ret_info;
 136         struct smatch_state *tmp;
 137         struct range_list *value_ranges;
 138
 139         value_ranges = range_list_union(info1->value_ranges, info2->value_ranges);
 140         tmp = alloc_extra_state_empty();
 141         ret_info = (struct data_info *)tmp->data;
 142         ret_info->value_ranges = value_ranges;
 143         tmp->name = show_ranges(ret_info->value_ranges);
 144         return tmp;
 145 }
 146
 147 struct sm_state *__extra_pre_loop_hook_before(struct statement *iterator_pre_statement)
 148 {
 149         struct expression *expr;
 150         char *name;
 151         struct symbol *sym;
 152         struct sm_state *ret = NULL;
 153
 154         if (!iterator_pre_statement)
 155                 return NULL;
 156         if (iterator_pre_statement->type != STMT_EXPRESSION)
 157                 return NULL;
 158         expr = iterator_pre_statement->expression;
 159         if (expr->type != EXPR_ASSIGNMENT)
 160                 return NULL;
 161         name = get_variable_from_expr(expr->left, &sym);
 162         if (!name || !sym)
 163                 goto free;
 164         ret = get_sm_state(my_id, name, sym);
 165 free:
 166         free_string(name);
 167         return ret;
 168 }
 169
 170 static const char *get_iter_op(struct expression *expr)
 171 {
 172         if (expr->type != EXPR_POSTOP && expr->type != EXPR_PREOP)
 173                 return NULL;
 174         return show_special(expr->op);
 175 }
 176
 177 int __iterator_unchanged(struct sm_state *sm, struct statement *iterator)
 178 {
 179         struct expression *iter_expr;
 180         const char *op;
 181         char *name;
 182         struct symbol *sym;
 183         int ret = 0;
 184
 185         if (!iterator)
 186                 return 0;
 187         if (iterator->type != STMT_EXPRESSION)
 188                 return 0;
 189         iter_expr = iterator->expression;
 190         op = get_iter_op(iter_expr);
 191         if (!op || (strcmp(op, "--") && strcmp(op, "++")))
 192                 return 0;
 193         name = get_variable_from_expr(iter_expr->unop, &sym);
 194         if (!name || !sym)
 195                 goto free;
 196         if (get_sm_state(my_id, name, sym) == sm)
 197                 ret = 1;
 198 free:
 199         free_string(name);
 200         return ret;
 201 }
 202
 203 void __extra_pre_loop_hook_after(struct sm_state *sm,
 204                                 struct statement *iterator,
 205                                 struct expression *condition)
 206 {
 207         struct expression *iter_expr;
 208         char *name;
 209         struct symbol *sym;
 210         long long value;
 211         int left = 0;
 212         const char *op;
 213         struct smatch_state *state;
 214         struct data_info *dinfo;
 215         long long min, max;
 216
 217         iter_expr = iterator->expression;
 218
 219         if (condition->type != EXPR_COMPARE)
 220                 return;
 221         value = get_value(condition->left);
 222         if (value == UNDEFINED) {
 223                 value = get_value(condition->right);
 224                 if (value == UNDEFINED)
 225                         return;
 226                 left = 1;
 227         }
 228         if (left)
 229                 name = get_variable_from_expr(condition->left, &sym);
 230         else
 231                 name = get_variable_from_expr(condition->right, &sym);
 232         if (!name || !sym)
 233                 goto free;
 234         if (sym != sm->sym || strcmp(name, sm->name))
 235                 goto free;
 236         op = get_iter_op(iter_expr);
 237         state = get_state(my_id, name, sym);
 238         dinfo = (struct data_info *)state->data;
 239         min = get_dinfo_min(dinfo);
 240         max = get_dinfo_max(dinfo);
 241         if (!strcmp(op, "++") && min != whole_range.min && max == whole_range.max) {
 242                 set_state(my_id, name, sym, alloc_extra_state(min));
 243         } else if (min == whole_range.min && max != whole_range.max) {
 244                 set_state(my_id, name, sym, alloc_extra_state(max));
 245         }
 246 free:
 247         free_string(name);
 248         return;
 249 }
 250
 251 static struct smatch_state *unmatched_state(struct sm_state *sm)
 252 {
 253         return extra_undefined();
 254 }
 255
 256 static void match_function_call(struct expression *expr)
 257 {
 258         struct expression *tmp;
 259         struct symbol *sym;
 260         char *name;
 261         int i = 0;
 262
 263         FOR_EACH_PTR(expr->args, tmp) {
 264                 if (tmp->op == '&') {
 265                         name = get_variable_from_expr(tmp->unop, &sym);
 266                         if (name) {
 267                                 set_state(my_id, name, sym, extra_undefined());
 268                         }
 269                         free_string(name);
 270                 }
 271                 i++;
 272         } END_FOR_EACH_PTR(tmp);
 273 }
 274
 275 static void match_assign(struct expression *expr)
 276 {
 277         struct expression *left;
 278         struct symbol *sym;
 279         char *name;
 280
 281         left = strip_expr(expr->left);
 282         name = get_variable_from_expr(left, &sym);
 283         if (!name)
 284                 return;
 285         set_state(my_id, name, sym, alloc_extra_state(get_value(expr->right)));
 286         free_string(name);
 287 }
 288
 289 static void undef_expr(struct expression *expr)
 290 {
 291         struct symbol *sym;
 292         char *name;
 293         long long min = whole_range.min;
 294         long long max = whole_range.max;
 295         long long val;
 296
 297         if (expr->op == '*')
 298                 return;
 299         if (expr->op == '(')
 300                 return;
 301
 302         name = get_variable_from_expr(expr->unop, &sym);
 303         if (!name)
 304                 goto free;
 305         if (!strcmp("++", show_special(expr->op))) {
 306                 if (get_implied_min(expr->unop, &val))
 307                         min = val + 1;
 308         }
 309         if (!strcmp("--", show_special(expr->op))) {
 310                 if (get_implied_max(expr->unop, &val))
 311                         max = val - 1;
 312         }
 313         set_state(my_id, name, sym, alloc_extra_state_range(min, max));
 314 free:
 315         free_string(name);
 316 }
 317
 318 static void match_declarations(struct symbol *sym)
 319 {
 320         const char *name;
 321
 322         if (sym->ident) {
 323                 name = sym->ident->name;
 324                 if (sym->initializer) {
 325                         set_state(my_id, name, sym, alloc_extra_state(get_value(sym->initializer)));
 326                         scoped_state(name, my_id, sym);
 327                 } else {
 328                         set_state(my_id, name, sym, extra_undefined());
 329                         scoped_state(name, my_id, sym);
 330                 }
 331         }
 332 }
 333
 334 static void match_function_def(struct symbol *sym)
 335 {
 336         struct symbol *arg;
 337
 338         cur_func = sym;
 339         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 340                 if (!arg->ident) {
 341                         continue;
 342                 }
 343                 set_state(my_id, arg->ident->name, arg, extra_undefined());
 344         } END_FOR_EACH_PTR(arg);
 345 }
 346
 347 #define VAL_SINGLE 0
 348 #define VAL_MAX    1
 349 #define VAL_MIN    2
 350
 351 static int get_implied_value_helper(struct expression *expr, long long *val, int what)
 352 {
 353         struct smatch_state *state;
 354         struct symbol *sym;
 355         char *name;
 356
 357         *val = get_value(expr);
 358         if (*val != UNDEFINED)
 359                 return 1;
 360
 361         name = get_variable_from_expr(expr, &sym);
 362         if (!name)
 363                 return 0;
 364         state = get_state(my_id, name, sym);
 365         free_string(name);
 366         if (!state || !state->data)
 367                 return 0;
 368         if (what == VAL_SINGLE)
 369                 return get_single_value_from_range((struct data_info *)state->data, val);
 370         if (what == VAL_MAX) {
 371                 *val = get_dinfo_max((struct data_info *)state->data);
 372                 if (*val == whole_range.max) /* this means just guessing */
 373                         return 0;
 374                 return 1;
 375         }
 376         *val = get_dinfo_min((struct data_info *)state->data);
 377         if (*val == whole_range.min)
 378                 return 0;
 379         return 1;
 380 }
 381
 382 int get_implied_single_val(struct expression *expr, long long *val)
 383 {
 384         return get_implied_value_helper(expr, val, VAL_SINGLE);
 385 }
 386
 387 int get_implied_max(struct expression *expr, long long *val)
 388 {
 389         return get_implied_value_helper(expr, val, VAL_MAX);
 390 }
 391
 392 int get_implied_min(struct expression *expr, long long *val)
 393 {
 394         return get_implied_value_helper(expr, val, VAL_MIN);
 395 }
 396
 397 static int last_stmt_val(struct statement *stmt, long long *val)
 398 {
 399         struct expression *expr;
 400
 401         if (!stmt)
 402                 return 0;
 403
 404         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 405         if (stmt->type != STMT_EXPRESSION)
 406                 return 0;
 407         expr = stmt->expression;
 408         *val = get_value(expr);
 409         if (*val == UNDEFINED)
 410                 return 0;
 411         return 1;
 412 }
 413
 414 static void match_comparison(struct expression *expr)
 415 {
 416         long long fixed;
 417         char *name = NULL;
 418         struct symbol *sym;
 419         struct smatch_state *one_state;
 420         struct smatch_state *two_state;
 421         struct smatch_state *orig;
 422         int left = 0;
 423         int comparison = expr->op;
 424         struct expression *varies = expr->right;
 425
 426         fixed = get_value(expr->left);
 427         if (fixed == UNDEFINED) {
 428                 fixed = get_value(expr->right);
 429                 if (fixed == UNDEFINED)
 430                         return;
 431                 varies = expr->left;
 432                 left = 1;
 433         }
 434         if (varies->type == EXPR_PREOP || varies->type == EXPR_POSTOP) {
 435                 varies = varies->unop;
 436         }
 437         if (varies->type == EXPR_CALL) {
 438                 function_comparison(comparison, varies, fixed, left);
 439                 return;
 440         }
 441         name = get_variable_from_expr(varies, &sym);
 442         if (!name || !sym)
 443                 goto free;
 444
 445         orig = get_state(my_id, name, sym);
 446         if (!orig)
 447                 orig = extra_undefined();
 448
 449         switch(comparison){
 450         case '<':
 451         case SPECIAL_UNSIGNED_LT:
 452                 one_state = filter_range(orig, whole_range.min, fixed - 1);
 453                 two_state = filter_range(orig, fixed, whole_range.max);
 454                 if (left)
 455                         set_true_false_states(my_id, name, sym, two_state, one_state);
 456                 else
 457                         set_true_false_states(my_id, name, sym, one_state, two_state);
 458                 return;
 459         case SPECIAL_UNSIGNED_LTE:
 460         case SPECIAL_LTE:
 461                 one_state = filter_range(orig, whole_range.min, fixed);
 462                 two_state = filter_range(orig, fixed + 1, whole_range.max);
 463                 if (left)
 464                         set_true_false_states(my_id, name, sym, two_state, one_state);
 465                 else
 466                         set_true_false_states(my_id, name, sym, one_state, two_state);
 467                 return;
 468         case SPECIAL_EQUAL:
 469                 // todo.  print a warning here for impossible conditions.
 470                 one_state = alloc_extra_state(fixed);
 471                 two_state = filter_range(orig, fixed, fixed);
 472                 set_true_false_states(my_id, name, sym, one_state, two_state);
 473                 return;
 474         case SPECIAL_UNSIGNED_GTE:
 475         case SPECIAL_GTE:
 476                 one_state = filter_range(orig, whole_range.min, fixed - 1);
 477                 two_state = filter_range(orig, fixed, whole_range.max);
 478                 if (left)
 479                         set_true_false_states(my_id, name, sym, one_state, two_state);
 480                 else
 481                         set_true_false_states(my_id, name, sym, two_state, one_state);
 482                 return;
 483         case '>':
 484         case SPECIAL_UNSIGNED_GT:
 485                 one_state = filter_range(orig, whole_range.min, fixed);
 486                 two_state = filter_range(orig, fixed + 1, whole_range.max);
 487                 if (left)
 488                         set_true_false_states(my_id, name, sym, one_state, two_state);
 489                 else
 490                         set_true_false_states(my_id, name, sym, two_state, one_state);
 491                 return;
 492         case SPECIAL_NOTEQUAL:
 493                 one_state = alloc_extra_state(fixed);
 494                 two_state = filter_range(orig, fixed, fixed);
 495                 set_true_false_states(my_id, name, sym, two_state, one_state);
 496                 return;
 497         default:
 498                 sm_msg("unhandled comparison %d\n", comparison);
 499                 return;
 500         }
 501         return;
 502 free:
 503         free_string(name);
 504 }
 505
 506 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 507 void __extra_match_condition(struct expression *expr)
 508 {
 509         struct symbol *sym;
 510         char *name;
 511         struct smatch_state *pre_state;
 512         struct smatch_state *true_state;
 513         struct smatch_state *false_state;
 514
 515         expr = strip_expr(expr);
 516         switch(expr->type) {
 517         case EXPR_CALL:
 518                 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
 519                 return;
 520         case EXPR_PREOP:
 521         case EXPR_SYMBOL:
 522         case EXPR_DEREF:
 523                 name = get_variable_from_expr(expr, &sym);
 524                 if (!name)
 525                         return;
 526                 pre_state = get_state(my_id, name, sym);
 527                 true_state = add_filter(pre_state, 0);
 528                 false_state = alloc_extra_state(0);
 529                 set_true_false_states(my_id, name, sym, true_state, false_state);
 530                 free_string(name);
 531                 return;
 532         case EXPR_COMPARE:
 533                 match_comparison(expr);
 534                 return;
 535         case EXPR_ASSIGNMENT:
 536                 __extra_match_condition(expr->right);
 537                 __extra_match_condition(expr->left);
 538                 return;
 539         }
 540 }
 541
 542 static int variable_non_zero(struct expression *expr)
 543 {
 544         char *name;
 545         struct symbol *sym;
 546         struct smatch_state *state;
 547         int ret = UNDEFINED;
 548
 549         name = get_variable_from_expr(expr, &sym);
 550         if (!name || !sym)
 551                 goto exit;
 552         state = get_state(my_id, name, sym);
 553         if (!state || !state->data)
 554                 goto exit;
 555         ret = !possibly_false(SPECIAL_NOTEQUAL, (struct data_info *)state->data, 0, 1);
 556 exit:
 557         free_string(name);
 558         return ret;
 559 }
 560
 561 int known_condition_true(struct expression *expr)
 562 {
 563         int tmp;
 564
 565         if (!expr)
 566                 return 0;
 567
 568         tmp = get_value(expr);
 569         if (tmp && tmp != UNDEFINED)
 570                 return 1;
 571
 572         expr = strip_expr(expr);
 573         switch(expr->type) {
 574         case EXPR_PREOP:
 575                 if (expr->op == '!') {
 576                         if (known_condition_false(expr->unop))
 577                                 return 1;
 578                         break;
 579                 }
 580                 break;
 581         default:
 582                 break;
 583         }
 584         return 0;
 585 }
 586
 587 int known_condition_false(struct expression *expr)
 588 {
 589         if (!expr)
 590                 return 0;
 591
 592         if (is_zero(expr))
 593                 return 1;
 594
 595         switch(expr->type) {
 596         case EXPR_PREOP:
 597                 if (expr->op == '!') {
 598                         if (known_condition_true(expr->unop))
 599                                 return 1;
 600                         break;
 601                 }
 602                 break;
 603         default:
 604                 break;
 605         }
 606         return 0;
 607 }
 608
 609 static int do_comparison_range(struct expression *expr)
 610 {
 611         struct symbol *sym;
 612         char *name;
 613         struct smatch_state *state;
 614         long long value;
 615         int left = 0;
 616         int poss_true, poss_false;
 617
 618         value = get_value(expr->left);
 619         if (value == UNDEFINED) {
 620                 value = get_value(expr->right);
 621                 if (value == UNDEFINED)
 622                         return 3;
 623                 left = 1;
 624         }
 625         if (left)
 626                 name = get_variable_from_expr(expr->left, &sym);
 627         else
 628                 name = get_variable_from_expr(expr->right, &sym);
 629         if (!name || !sym)
 630                 goto free;
 631         state = get_state(SMATCH_EXTRA, name, sym);
 632         if (!state)
 633                 goto free;
 634         poss_true = possibly_true(expr->op, (struct data_info *)state->data, value, left);
 635         poss_false = possibly_false(expr->op, (struct data_info *)state->data, value, left);
 636         if (!poss_true && !poss_false)
 637                 return 0;
 638         if (poss_true && !poss_false)
 639                 return 1;
 640         if (!poss_true && poss_false)
 641                 return 2;
 642         if (poss_true && poss_false)
 643                 return 3;
 644 free:
 645         free_string(name);
 646         return 3;
 647 }
 648
 649 int implied_condition_true(struct expression *expr)
 650 {
 651         struct statement *stmt;
 652         int tmp;
 653         long long val;
 654
 655         if (!expr)
 656                 return 0;
 657
 658         tmp = get_value(expr);
 659         if (tmp && tmp != UNDEFINED)
 660                 return 1;
 661
 662         expr = strip_expr(expr);
 663         switch(expr->type) {
 664         case EXPR_COMPARE:
 665                 if (do_comparison_range(expr) == 1)
 666                         return 1;
 667                 break;
 668         case EXPR_PREOP:
 669                 if (expr->op == '!') {
 670                         if (implied_condition_false(expr->unop))
 671                                 return 1;
 672                         break;
 673                 }
 674                 stmt = get_block_thing(expr);
 675                 if (last_stmt_val(stmt, &val) && val == 1)
 676                         return 1;
 677                 break;
 678         default:
 679                 if (variable_non_zero(expr) == 1)
 680                         return 1;
 681                 break;
 682         }
 683         return 0;
 684 }
 685
 686 int implied_condition_false(struct expression *expr)
 687 {
 688         struct statement *stmt;
 689         struct expression *tmp;
 690         long long val;
 691
 692         if (!expr)
 693                 return 0;
 694
 695         if (is_zero(expr))
 696                 return 1;
 697
 698         switch(expr->type) {
 699         case EXPR_COMPARE:
 700                 if (do_comparison_range(expr) == 2)
 701                         return 1;
 702         case EXPR_PREOP:
 703                 if (expr->op == '!') {
 704                         if (implied_condition_true(expr->unop))
 705                                 return 1;
 706                         break;
 707                 }
 708                 stmt = get_block_thing(expr);
 709                 if (last_stmt_val(stmt, &val) && val == 0)
 710                         return 1;
 711                 tmp = strip_expr(expr);
 712                 if (tmp != expr)
 713                         return implied_condition_false(tmp);
 714                 break;
 715         default:
 716                 if (variable_non_zero(expr) == 0)
 717                         return 1;
 718                 break;
 719         }
 720         return 0;
 721 }
 722
 723 void register_smatch_extra(int id)
 724 {
 725         my_id = id;
 726         add_merge_hook(my_id, &merge_func);
 727         add_unmatched_state_hook(my_id, &unmatched_state);
 728         add_hook(&undef_expr, OP_HOOK);
 729         add_hook(&match_function_def, FUNC_DEF_HOOK);
 730         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 731         add_hook(&match_assign, ASSIGNMENT_HOOK);
 732         add_hook(&match_declarations, DECLARATION_HOOK);
 733
 734         if (option_project == PROJ_KERNEL) {
 735                 /* I don't know how to test for the ATTRIB_NORET attribute. :( */
 736                 add_function_hook("panic", &__match_nullify_path_hook, NULL);
 737                 add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
 738                 add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
 739                 add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
 740                 add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);
 741         }
 742 }