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
 294         if (expr->op == '*')
 295                 return;
 296         if (expr->op == '(')
 297                 return;
 298
 299         name = get_variable_from_expr(expr->unop, &sym);
 300         if (!name)
 301                 return;
 302         if (!get_state(my_id, name, sym)) {
 303                 free_string(name);
 304                 return;
 305         }
 306         set_state(my_id, name, sym, extra_undefined());
 307         free_string(name);
 308 }
 309
 310 static void match_declarations(struct symbol *sym)
 311 {
 312         const char *name;
 313
 314         if (sym->ident) {
 315                 name = sym->ident->name;
 316                 if (sym->initializer) {
 317                         set_state(my_id, name, sym, alloc_extra_state(get_value(sym->initializer)));
 318                         scoped_state(name, my_id, sym);
 319                 } else {
 320                         set_state(my_id, name, sym, extra_undefined());
 321                         scoped_state(name, my_id, sym);
 322                 }
 323         }
 324 }
 325
 326 static void match_function_def(struct symbol *sym)
 327 {
 328         struct symbol *arg;
 329
 330         cur_func = sym;
 331         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 332                 if (!arg->ident) {
 333                         continue;
 334                 }
 335                 set_state(my_id, arg->ident->name, arg, extra_undefined());
 336         } END_FOR_EACH_PTR(arg);
 337 }
 338
 339 #define VAL_SINGLE 0
 340 #define VAL_MAX    1
 341 #define VAL_MIN    2
 342
 343 static long long get_implied_value_helper(struct expression *expr, int what)
 344 {
 345         struct smatch_state *state;
 346         int val;
 347         struct symbol *sym;
 348         char *name;
 349
 350         val = get_value(expr);
 351         if (val != UNDEFINED)
 352                 return val;
 353
 354         name = get_variable_from_expr(expr, &sym);
 355         if (!name)
 356                 return UNDEFINED;
 357         state = get_state(my_id, name, sym);
 358         free_string(name);
 359         if (!state || !state->data)
 360                 return UNDEFINED;
 361         if (what == VAL_SINGLE)
 362                 return get_single_value_from_range((struct data_info *)state->data);
 363         if (what == VAL_MAX)
 364                 return get_dinfo_max((struct data_info *)state->data);
 365         return get_dinfo_min((struct data_info *)state->data);
 366 }
 367
 368 int get_implied_single_val(struct expression *expr)
 369 {
 370         return get_implied_value_helper(expr, VAL_SINGLE);
 371 }
 372
 373 int get_implied_max(struct expression *expr)
 374 {
 375         long long ret;
 376
 377         ret = get_implied_value_helper(expr, VAL_MAX);
 378         if (ret == whole_range.max)
 379                 return UNDEFINED;
 380         return ret;
 381 }
 382
 383 int get_implied_min(struct expression *expr)
 384 {
 385         long long ret;
 386
 387         ret = get_implied_value_helper(expr, VAL_MIN);
 388         if (ret == whole_range.min)
 389                 return UNDEFINED;
 390         return ret;
 391 }
 392
 393 int last_stmt_val(struct statement *stmt)
 394 {
 395         struct expression *expr;
 396
 397         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 398         if (stmt->type != STMT_EXPRESSION)
 399                 return UNDEFINED;
 400         expr = stmt->expression;
 401         return get_value(expr);
 402 }
 403
 404 static void match_comparison(struct expression *expr)
 405 {
 406         long long value;
 407         char *name = NULL;
 408         struct symbol *sym;
 409         struct smatch_state *one_state;
 410         struct smatch_state *two_state;
 411         struct smatch_state *orig;
 412         int left = 0;
 413         int comparison = expr->op;
 414
 415         value = get_value(expr->left);
 416         if (value == UNDEFINED) {
 417                 value = get_value(expr->right);
 418                 if (value == UNDEFINED)
 419                         return;
 420                 left = 1;
 421         }
 422         if (left && expr->left->type == EXPR_CALL) {
 423                 function_comparison(comparison, expr->left, value, left);
 424                 return;
 425         }
 426         if (!left && expr->right->type == EXPR_CALL) {
 427                 function_comparison(comparison, expr->right, value, left);
 428                 return;
 429         }
 430         if (left)
 431                 name = get_variable_from_expr(expr->left, &sym);
 432         else
 433                 name = get_variable_from_expr(expr->right, &sym);
 434         if (!name || !sym)
 435                 goto free;
 436
 437         orig = get_state(my_id, name, sym);
 438         if (!orig)
 439                 orig = extra_undefined();
 440
 441         switch(comparison){
 442         case '<':
 443         case SPECIAL_UNSIGNED_LT:
 444                 one_state = filter_range(orig, whole_range.min, value - 1);
 445                 two_state = filter_range(orig, value, whole_range.max);
 446                 if (left)
 447                         set_true_false_states(my_id, name, sym, two_state, one_state);
 448                 else
 449                         set_true_false_states(my_id, name, sym, one_state, two_state);
 450                 return;
 451         case SPECIAL_UNSIGNED_LTE:
 452         case SPECIAL_LTE:
 453                 one_state = filter_range(orig, whole_range.min, value);
 454                 two_state = filter_range(orig, value + 1, whole_range.max);
 455                 if (left)
 456                         set_true_false_states(my_id, name, sym, two_state, one_state);
 457                 else
 458                         set_true_false_states(my_id, name, sym, one_state, two_state);
 459                 return;
 460         case SPECIAL_EQUAL:
 461                 // todo.  print a warning here for impossible conditions.
 462                 one_state = alloc_extra_state(value);
 463                 two_state = filter_range(orig, value, value);
 464                 set_true_false_states(my_id, name, sym, one_state, two_state);
 465                 return;
 466         case SPECIAL_UNSIGNED_GTE:
 467         case SPECIAL_GTE:
 468                 one_state = filter_range(orig, whole_range.min, value - 1);
 469                 two_state = filter_range(orig, value, whole_range.max);
 470                 if (left)
 471                         set_true_false_states(my_id, name, sym, one_state, two_state);
 472                 else
 473                         set_true_false_states(my_id, name, sym, two_state, one_state);
 474                 return;
 475         case '>':
 476         case SPECIAL_UNSIGNED_GT:
 477                 one_state = filter_range(orig, whole_range.min, value);
 478                 two_state = filter_range(orig, value + 1, whole_range.max);
 479                 if (left)
 480                         set_true_false_states(my_id, name, sym, one_state, two_state);
 481                 else
 482                         set_true_false_states(my_id, name, sym, two_state, one_state);
 483                 return;
 484         case SPECIAL_NOTEQUAL:
 485                 one_state = alloc_extra_state(value);
 486                 two_state = filter_range(orig, value, value);
 487                 set_true_false_states(my_id, name, sym, two_state, one_state);
 488                 return;
 489         default:
 490                 sm_msg("unhandled comparison %d\n", comparison);
 491                 return;
 492         }
 493         return;
 494 free:
 495         free_string(name);
 496 }
 497
 498 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 499 void __extra_match_condition(struct expression *expr)
 500 {
 501         struct symbol *sym;
 502         char *name;
 503         struct smatch_state *pre_state;
 504         struct smatch_state *true_state;
 505         struct smatch_state *false_state;
 506
 507         expr = strip_expr(expr);
 508         switch(expr->type) {
 509         case EXPR_CALL:
 510                 function_comparison(SPECIAL_NOTEQUAL, expr, 0, 1);
 511                 return;
 512         case EXPR_PREOP:
 513         case EXPR_SYMBOL:
 514         case EXPR_DEREF:
 515                 name = get_variable_from_expr(expr, &sym);
 516                 if (!name)
 517                         return;
 518                 pre_state = get_state(my_id, name, sym);
 519                 true_state = add_filter(pre_state, 0);
 520                 false_state = alloc_extra_state(0);
 521                 set_true_false_states(my_id, name, sym, true_state, false_state);
 522                 free_string(name);
 523                 return;
 524         case EXPR_COMPARE:
 525                 match_comparison(expr);
 526                 return;
 527         case EXPR_ASSIGNMENT:
 528                 __extra_match_condition(expr->right);
 529                 __extra_match_condition(expr->left);
 530                 return;
 531         }
 532 }
 533
 534 static int variable_non_zero(struct expression *expr)
 535 {
 536         char *name;
 537         struct symbol *sym;
 538         struct smatch_state *state;
 539         int ret = UNDEFINED;
 540
 541         name = get_variable_from_expr(expr, &sym);
 542         if (!name || !sym)
 543                 goto exit;
 544         state = get_state(my_id, name, sym);
 545         if (!state || !state->data)
 546                 goto exit;
 547         ret = !possibly_false(SPECIAL_NOTEQUAL, (struct data_info *)state->data, 0, 1);
 548 exit:
 549         free_string(name);
 550         return ret;
 551 }
 552
 553 int known_condition_true(struct expression *expr)
 554 {
 555         int tmp;
 556
 557         if (!expr)
 558                 return 0;
 559
 560         tmp = get_value(expr);
 561         if (tmp && tmp != UNDEFINED)
 562                 return 1;
 563
 564         expr = strip_expr(expr);
 565         switch(expr->type) {
 566         case EXPR_PREOP:
 567                 if (expr->op == '!') {
 568                         if (known_condition_false(expr->unop))
 569                                 return 1;
 570                         break;
 571                 }
 572                 break;
 573         default:
 574                 break;
 575         }
 576         return 0;
 577 }
 578
 579 int known_condition_false(struct expression *expr)
 580 {
 581         if (!expr)
 582                 return 0;
 583
 584         if (is_zero(expr))
 585                 return 1;
 586
 587         switch(expr->type) {
 588         case EXPR_PREOP:
 589                 if (expr->op == '!') {
 590                         if (known_condition_true(expr->unop))
 591                                 return 1;
 592                         break;
 593                 }
 594                 break;
 595         default:
 596                 break;
 597         }
 598         return 0;
 599 }
 600
 601 static int do_comparison_range(struct expression *expr)
 602 {
 603         struct symbol *sym;
 604         char *name;
 605         struct smatch_state *state;
 606         long long value;
 607         int left = 0;
 608         int poss_true, poss_false;
 609
 610         value = get_value(expr->left);
 611         if (value == UNDEFINED) {
 612                 value = get_value(expr->right);
 613                 if (value == UNDEFINED)
 614                         return 3;
 615                 left = 1;
 616         }
 617         if (left)
 618                 name = get_variable_from_expr(expr->left, &sym);
 619         else
 620                 name = get_variable_from_expr(expr->right, &sym);
 621         if (!name || !sym)
 622                 goto free;
 623         state = get_state(SMATCH_EXTRA, name, sym);
 624         if (!state)
 625                 goto free;
 626         poss_true = possibly_true(expr->op, (struct data_info *)state->data, value, left);
 627         poss_false = possibly_false(expr->op, (struct data_info *)state->data, value, left);
 628         if (!poss_true && !poss_false)
 629                 return 0;
 630         if (poss_true && !poss_false)
 631                 return 1;
 632         if (!poss_true && poss_false)
 633                 return 2;
 634         if (poss_true && poss_false)
 635                 return 3;
 636 free:
 637         free_string(name);
 638         return 3;
 639 }
 640
 641 int implied_condition_true(struct expression *expr)
 642 {
 643         struct statement *stmt;
 644         int tmp;
 645
 646         if (!expr)
 647                 return 0;
 648
 649         tmp = get_value(expr);
 650         if (tmp && tmp != UNDEFINED)
 651                 return 1;
 652
 653         expr = strip_expr(expr);
 654         switch(expr->type) {
 655         case EXPR_COMPARE:
 656                 if (do_comparison_range(expr) == 1)
 657                         return 1;
 658                 break;
 659         case EXPR_PREOP:
 660                 if (expr->op == '!') {
 661                         if (implied_condition_false(expr->unop))
 662                                 return 1;
 663                         break;
 664                 }
 665                 stmt = get_block_thing(expr);
 666                 if (stmt && (last_stmt_val(stmt) == 1))
 667                         return 1;
 668                 break;
 669         default:
 670                 if (variable_non_zero(expr) == 1)
 671                         return 1;
 672                 break;
 673         }
 674         return 0;
 675 }
 676
 677 int implied_condition_false(struct expression *expr)
 678 {
 679         struct statement *stmt;
 680         struct expression *tmp;
 681
 682         if (!expr)
 683                 return 0;
 684
 685         if (is_zero(expr))
 686                 return 1;
 687
 688         switch(expr->type) {
 689         case EXPR_COMPARE:
 690                 if (do_comparison_range(expr) == 2)
 691                         return 1;
 692         case EXPR_PREOP:
 693                 if (expr->op == '!') {
 694                         if (implied_condition_true(expr->unop))
 695                                 return 1;
 696                         break;
 697                 }
 698                 stmt = get_block_thing(expr);
 699                 if (stmt && (last_stmt_val(stmt) == 0))
 700                         return 1;
 701                 tmp = strip_expr(expr);
 702                 if (tmp != expr)
 703                         return implied_condition_false(tmp);
 704                 break;
 705         default:
 706                 if (variable_non_zero(expr) == 0)
 707                         return 1;
 708                 break;
 709         }
 710         return 0;
 711 }
 712
 713 void register_smatch_extra(int id)
 714 {
 715         my_id = id;
 716         add_merge_hook(my_id, &merge_func);
 717         add_unmatched_state_hook(my_id, &unmatched_state);
 718         add_hook(&undef_expr, OP_HOOK);
 719         add_hook(&match_function_def, FUNC_DEF_HOOK);
 720         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 721         add_hook(&match_assign, ASSIGNMENT_HOOK);
 722         add_hook(&match_declarations, DECLARATION_HOOK);
 723
 724 #ifdef KERNEL
 725         /* I don't know how to test for the ATTRIB_NORET attribute. :( */
 726         add_function_hook("panic", &__match_nullify_path_hook, NULL);
 727         add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
 728         add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
 729         add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
 730         add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);
 731 #endif
 732 }