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 #include "parse.h"
  12 #include "smatch.h"
  13 #include "smatch_slist.h"
  14 #include "smatch_extra.h"
  15
  16 static int my_id;
  17
  18 struct data_info unknown_num = {
  19         .type = DATA_NUM,
  20         .merged = 0,
  21         .values = NULL,
  22 };
  23
  24 static struct smatch_state extra_undefined = {
  25         .name = "unknown",
  26         .data = &unknown_num,
  27 };
  28
  29 static struct smatch_state *alloc_extra_state_no_name(int val)
  30 {
  31         struct smatch_state *state;
  32
  33         state = __alloc_smatch_state(0);
  34         state->data = (void *)alloc_data_info(val);
  35         return state;
  36 }
  37
  38 struct smatch_state *alloc_extra_state(int val)
  39 {
  40         struct smatch_state *state;
  41         static char name[20];
  42
  43         if (val == UNDEFINED)
  44                 return &extra_undefined;
  45
  46         state = alloc_extra_state_no_name(val);
  47         snprintf(name, 20, "%d", val);
  48         state->name = alloc_sname(name);
  49         return state;
  50 }
  51
  52 struct smatch_state *add_filter(struct smatch_state *orig, long long num)
  53 {
  54
  55         struct smatch_state *ret;
  56         struct data_info *orig_info = NULL;
  57         struct data_info *ret_info;
  58         char buf[256];
  59
  60         if (orig)
  61                 orig_info = (struct data_info *)orig->data;
  62         ret = alloc_extra_state_no_name(UNDEFINED);
  63         snprintf(buf, 254, "%s f%lld", orig?orig->name:"any", num);
  64         buf[255] = '\0';
  65         ret->name = alloc_sname(buf);
  66         ret_info = (struct data_info *)ret->data;
  67         ret_info->values = NULL;
  68         if (orig)
  69                 ret_info->values = clone_num_list(orig_info->values);
  70         ret_info->filter = NULL;
  71         if (orig)
  72                 ret_info->filter = clone_num_list(orig_info->filter);
  73         add_num(&ret_info->filter, num);
  74         return ret;
  75 }
  76
  77 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
  78                                        struct smatch_state *s1,
  79                                        struct smatch_state *s2)
  80 {
  81         struct data_info *info1 = (struct data_info *)s1->data;
  82         struct data_info *info2 = (struct data_info *)s2->data;
  83         struct data_info *ret_info;
  84         struct smatch_state *tmp;
  85
  86         tmp = alloc_extra_state_no_name(UNDEFINED);
  87         tmp->name = "extra_merged";
  88         ret_info = (struct data_info *)tmp->data;
  89         ret_info->merged = 1;
  90         ret_info->values = num_list_union(info1->values, info2->values);
  91         ret_info->filter = num_list_intersection(info1->values, info2->values);
  92         return tmp;
  93 }
  94
  95 struct sm_state *__extra_merge(struct sm_state *one, struct state_list *slist1,
  96                                struct sm_state *two, struct state_list *slist2)
  97 {
  98         struct data_info *info1;
  99         struct data_info *info2;
 100
 101         if (!one->state->data || !two->state->data) {
 102                 smatch_msg("internal error in smatch extra '%s = %s or %s'",
 103                            one->name, show_state(one->state),
 104                            show_state(two->state));
 105                 return alloc_state(one->name, one->owner, one->sym,
 106                                    &extra_undefined);
 107         }
 108
 109         info1 = (struct data_info *)one->state->data;
 110         info2 = (struct data_info *)two->state->data;
 111
 112         if (!info1->merged)
 113                 free_stack(&one->my_pools);
 114         if (!info2->merged)
 115                 free_stack(&two->my_pools);
 116
 117         if (one == two && !one->my_pools) {
 118                 add_pool(&one->my_pools, slist1);
 119                 add_pool(&one->my_pools, slist2);
 120         } else {
 121                 if (!one->my_pools)
 122                         add_pool(&one->my_pools, slist1);
 123                 if (!two->my_pools)
 124                         add_pool(&two->my_pools, slist2);
 125         }
 126
 127         add_pool(&one->all_pools, slist1);
 128         add_pool(&two->all_pools, slist2);
 129         return merge_sm_states(one, two);
 130 }
 131
 132 struct sm_state *__extra_and_merge(struct sm_state *sm,
 133                                      struct state_list_stack *stack)
 134 {
 135         struct state_list *slist;
 136         struct sm_state *ret = NULL;
 137         struct sm_state *tmp;
 138         int i = 0;
 139
 140         FOR_EACH_PTR(stack, slist) {
 141                 if (!i++) {
 142                         ret = get_sm_state_slist(slist, sm->name, sm->owner,
 143                                                  sm->sym);
 144                 } else {
 145                         tmp = get_sm_state_slist(slist, sm->name, sm->owner,
 146                                                  sm->sym);
 147                         ret = merge_sm_states(ret, tmp);
 148                 }
 149         } END_FOR_EACH_PTR(slist);
 150         if (!ret) {
 151                 smatch_msg("Internal error in __extra_and_merge");
 152                 return NULL;
 153         }
 154         ret->my_pools = stack;
 155         ret->all_pools = clone_stack(stack);
 156         return ret;
 157 }
 158
 159 static struct smatch_state *unmatched_state(struct sm_state *sm)
 160 {
 161         return &extra_undefined;
 162 }
 163
 164 static void match_function_call(struct expression *expr)
 165 {
 166         struct expression *tmp;
 167         struct symbol *sym;
 168         char *name;
 169         int i = 0;
 170
 171         FOR_EACH_PTR(expr->args, tmp) {
 172                 if (tmp->op == '&') {
 173                         name = get_variable_from_expr(tmp->unop, &sym);
 174                         if (name) {
 175                                 set_state(name, my_id, sym, &extra_undefined);
 176                         }
 177                         free_string(name);
 178                 }
 179                 i++;
 180         } END_FOR_EACH_PTR(tmp);
 181 }
 182
 183 static void match_assign(struct expression *expr)
 184 {
 185         struct expression *left;
 186         struct symbol *sym;
 187         char *name;
 188
 189         left = strip_expr(expr->left);
 190         name = get_variable_from_expr(left, &sym);
 191         if (!name)
 192                 return;
 193         set_state(name, my_id, sym, alloc_extra_state(get_value(expr->right)));
 194         free_string(name);
 195 }
 196
 197 static void undef_expr(struct expression *expr)
 198 {
 199         struct symbol *sym;
 200         char *name;
 201
 202         name = get_variable_from_expr(expr->unop, &sym);
 203         if (!name)
 204                 return;
 205         if (!get_state(name, my_id, sym)) {
 206                 free_string(name);
 207                 return;
 208         }
 209         set_state(name, my_id, sym, &extra_undefined);
 210         free_string(name);
 211 }
 212
 213 static void match_declarations(struct symbol *sym)
 214 {
 215         const char *name;
 216
 217         if (sym->ident) {
 218                 name = sym->ident->name;
 219                 if (sym->initializer) {
 220                         set_state(name, my_id, sym, alloc_extra_state(get_value(sym->initializer)));
 221                 } else {
 222                         set_state(name, my_id, sym, &extra_undefined);
 223                 }
 224         }
 225 }
 226
 227 static void match_function_def(struct symbol *sym)
 228 {
 229         struct symbol *arg;
 230
 231         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 232                 if (!arg->ident) {
 233                         continue;
 234                 }
 235                 set_state(arg->ident->name, my_id, arg, &extra_undefined);
 236         } END_FOR_EACH_PTR(arg);
 237 }
 238
 239 static void match_unop(struct expression *expr)
 240 {
 241         struct symbol *sym;
 242         char *name;
 243         const char *tmp;
 244
 245
 246         name = get_variable_from_expr(expr->unop, &sym);
 247         if (!name)
 248                 return;
 249
 250         tmp = show_special(expr->op);
 251         if ((!strcmp(tmp, "--")) || (!strcmp(tmp, "++")))
 252                 set_state(name, my_id, sym, &extra_undefined);
 253         free_string(name);
 254 }
 255
 256 int get_implied_value(struct expression *expr)
 257 {
 258         struct smatch_state *state;
 259         int val;
 260         struct symbol *sym;
 261         char *name;
 262
 263         val = get_value(expr);
 264         if (val != UNDEFINED)
 265                 return val;
 266
 267         name = get_variable_from_expr(expr, &sym);
 268         if (!name)
 269                 return UNDEFINED;
 270         state = get_state(name, my_id, sym);
 271         free_string(name);
 272         if (!state || !state->data)
 273                 return UNDEFINED;
 274         return get_single_value((struct data_info *)state->data);
 275 }
 276
 277 int true_comparison(int left, int comparison, int right)
 278 {
 279         switch(comparison){
 280         case '<':
 281         case SPECIAL_UNSIGNED_LT:
 282                 if (left < right)
 283                         return 1;
 284                 return 0;
 285         case SPECIAL_UNSIGNED_LTE:
 286         case SPECIAL_LTE:
 287                 if (left < right)
 288                         return 1;
 289         case SPECIAL_EQUAL:
 290                 if (left == right)
 291                         return 1;
 292                 return 0;
 293         case SPECIAL_UNSIGNED_GTE:
 294         case SPECIAL_GTE:
 295                 if (left == right)
 296                         return 1;
 297         case '>':
 298         case SPECIAL_UNSIGNED_GT:
 299                 if (left > right)
 300                         return 1;
 301                 return 0;
 302         case SPECIAL_NOTEQUAL:
 303                 if (left != right)
 304                         return 1;
 305                 return 0;
 306         default:
 307                 smatch_msg("unhandled comparison %d\n", comparison);
 308                 return UNDEFINED;
 309         }
 310         return 0;
 311 }
 312
 313 static int do_comparison(struct expression *expr)
 314 {
 315         int left, right, ret;
 316
 317         if ((left = get_implied_value(expr->left)) == UNDEFINED)
 318                 return UNDEFINED;
 319
 320         if ((right = get_implied_value(expr->right)) == UNDEFINED)
 321                 return UNDEFINED;
 322
 323         ret = true_comparison(left, expr->op, right);
 324         if (ret == 1) {
 325                 SM_DEBUG("%d known condition: %d %s %d => true\n",
 326                         get_lineno(), left, show_special(expr->op), right);
 327         } else if (ret == 0) {
 328                 SM_DEBUG("%d known condition: %d %s %d => false\n",
 329                         get_lineno(), left, show_special(expr->op), right);
 330         }
 331         return ret;
 332 }
 333
 334 int last_stmt_val(struct statement *stmt)
 335 {
 336         struct expression *expr;
 337
 338         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 339         if (stmt->type != STMT_EXPRESSION)
 340                 return UNDEFINED;
 341         expr = stmt->expression;
 342         return get_value(expr);
 343 }
 344
 345 static void match_comparison(struct expression *expr)
 346 {
 347         int value;
 348         char *name = NULL;
 349         struct symbol *sym;
 350         struct smatch_state *eq_state;
 351         struct smatch_state *neq_state;
 352
 353         if (expr->op != SPECIAL_EQUAL && expr->op != SPECIAL_NOTEQUAL)
 354                 return;
 355         value = get_value(expr->left);
 356         if (value != UNDEFINED) {
 357                 name = get_variable_from_expr(expr->right, &sym);
 358         } else {
 359                 value = get_value(expr->right);
 360                 name = get_variable_from_expr(expr->left, &sym);
 361         }
 362         if (value == UNDEFINED || !name || !sym)
 363                 goto free;
 364         eq_state =  alloc_extra_state(value);
 365         neq_state = alloc_extra_state(UNDEFINED);
 366         neq_state = add_filter(neq_state, value);
 367         if (expr->op == SPECIAL_EQUAL)
 368                 set_true_false_states(name, my_id, sym, eq_state, neq_state);
 369         else
 370                 set_true_false_states(name, my_id, sym, neq_state, eq_state);
 371 free:
 372         free_string(name);
 373 }
 374
 375 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 376 void __extra_match_condition(struct expression *expr)
 377 {
 378         struct symbol *sym;
 379         char *name;
 380         struct smatch_state *pre_state;
 381         struct smatch_state *true_state;
 382         struct smatch_state *false_state;
 383
 384         expr = strip_expr(expr);
 385         switch(expr->type) {
 386         case EXPR_PREOP:
 387         case EXPR_SYMBOL:
 388         case EXPR_DEREF:
 389                 name = get_variable_from_expr(expr, &sym);
 390                 if (!name)
 391                         return;
 392                 pre_state = get_state(name, my_id, sym);
 393                 true_state = add_filter(pre_state, 0);
 394                 false_state = alloc_extra_state(0);
 395                 set_true_false_states(name, my_id, sym, true_state, false_state);
 396                 free_string(name);
 397                 return;
 398         case EXPR_COMPARE:
 399                 match_comparison(expr);
 400                 return;
 401         }
 402 }
 403
 404 static int variable_non_zero(struct expression *expr)
 405 {
 406         char *name;
 407         struct symbol *sym;
 408         struct smatch_state *state;
 409         int ret = UNDEFINED;
 410
 411         name = get_variable_from_expr(expr, &sym);
 412         if (!name || !sym)
 413                 goto exit;
 414         state = get_state(name, my_id, sym);
 415         if (!state || !state->data)
 416                 goto exit;
 417         ret = true_comparison(get_single_value((struct data_info *)state->data),
 418                               SPECIAL_NOTEQUAL, 0);
 419 exit:
 420         free_string(name);
 421         return ret;
 422 }
 423
 424 int known_condition_true(struct expression *expr)
 425 {
 426         int tmp;
 427
 428         if (!expr)
 429                 return 0;
 430
 431         tmp = get_value(expr);
 432         if (tmp && tmp != UNDEFINED)
 433                 return 1;
 434
 435         expr = strip_expr(expr);
 436         switch(expr->type) {
 437         case EXPR_PREOP:
 438                 if (expr->op == '!') {
 439                         if (known_condition_false(expr->unop))
 440                                 return 1;
 441                         break;
 442                 }
 443                 break;
 444         default:
 445                 break;
 446         }
 447         return 0;
 448 }
 449
 450 int known_condition_false(struct expression *expr)
 451 {
 452         if (!expr)
 453                 return 0;
 454
 455         if (is_zero(expr))
 456                 return 1;
 457
 458         switch(expr->type) {
 459         case EXPR_PREOP:
 460                 if (expr->op == '!') {
 461                         if (known_condition_true(expr->unop))
 462                                 return 1;
 463                         break;
 464                 }
 465                 break;
 466         default:
 467                 break;
 468         }
 469         return 0;
 470 }
 471
 472 int implied_condition_true(struct expression *expr)
 473 {
 474         struct statement *stmt;
 475         int tmp;
 476
 477         if (!expr)
 478                 return 0;
 479
 480         tmp = get_value(expr);
 481         if (tmp && tmp != UNDEFINED)
 482                 return 1;
 483
 484         expr = strip_expr(expr);
 485         switch(expr->type) {
 486         case EXPR_COMPARE:
 487                 if (do_comparison(expr) == 1)
 488                         return 1;
 489                 break;
 490         case EXPR_PREOP:
 491                 if (expr->op == '!') {
 492                         if (implied_condition_false(expr->unop))
 493                                 return 1;
 494                         break;
 495                 }
 496                 stmt = get_block_thing(expr);
 497                 if (stmt && (last_stmt_val(stmt) == 1))
 498                         return 1;
 499                 break;
 500         default:
 501                 if (variable_non_zero(expr) == 1)
 502                         return 1;
 503                 break;
 504         }
 505         return 0;
 506 }
 507
 508 int implied_condition_false(struct expression *expr)
 509 {
 510         struct statement *stmt;
 511         struct expression *tmp;
 512
 513         if (!expr)
 514                 return 0;
 515
 516         if (is_zero(expr))
 517                 return 1;
 518
 519         switch(expr->type) {
 520         case EXPR_COMPARE:
 521                 if (do_comparison(expr) == 0)
 522                         return 1;
 523         case EXPR_PREOP:
 524                 if (expr->op == '!') {
 525                         if (implied_condition_true(expr->unop))
 526                                 return 1;
 527                         break;
 528                 }
 529                 stmt = get_block_thing(expr);
 530                 if (stmt && (last_stmt_val(stmt) == 0))
 531                         return 1;
 532                 tmp = strip_expr(expr);
 533                 if (tmp != expr)
 534                         return implied_condition_false(tmp);
 535                 break;
 536         default:
 537                 if (variable_non_zero(expr) == 0)
 538                         return 1;
 539                 break;
 540         }
 541         return 0;
 542 }
 543
 544 void register_smatch_extra(int id)
 545 {
 546         my_id = id;
 547         add_merge_hook(my_id, &merge_func);
 548         add_unmatched_state_hook(my_id, &unmatched_state);
 549         add_hook(&undef_expr, OP_HOOK);
 550         add_hook(&match_function_def, FUNC_DEF_HOOK);
 551         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 552         add_hook(&match_assign, ASSIGNMENT_HOOK);
 553         add_hook(&match_declarations, DECLARATION_HOOK);
 554         add_hook(&match_unop, OP_HOOK);
 555         add_hook(&free_data_info_allocs, END_FUNC_HOOK);
 556
 557 #ifdef KERNEL
 558         /* I don't know how to test for the ATTRIB_NORET attribute. :( */
 559         add_function_hook("panic", &__match_nullify_path_hook, NULL);
 560         add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
 561         add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
 562         add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
 563         add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);
 564 #endif
 565 }