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