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