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