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