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