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