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