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 expr_to_val(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 = expr_to_val(expr->left)) == UNDEFINED)
 318                 return UNDEFINED;
 319
 320         if ((right = expr_to_val(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 /* this is actually hooked from smatch_implied.c...  it's hacky, yes */
 346 void __extra_match_condition(struct expression *expr)
 347 {
 348         struct symbol *sym;
 349         char *name;
 350         struct smatch_state *pre_state;
 351         struct smatch_state *true_state;
 352         struct smatch_state *false_state;
 353
 354         expr = strip_expr(expr);
 355         switch(expr->type) {
 356         case EXPR_PREOP:
 357         case EXPR_SYMBOL:
 358         case EXPR_DEREF:
 359                 name = get_variable_from_expr(expr, &sym);
 360                 if (!name)
 361                         return;
 362                 pre_state = get_state(name, my_id, sym);
 363                 true_state = add_filter(pre_state, 0);
 364                 false_state = alloc_extra_state(0);
 365                 set_true_false_states(name, my_id, sym, true_state, false_state);
 366                 free_string(name);
 367                 return;
 368 //      case EXPR_COMPARE:  // later
 369         }
 370 }
 371
 372 static int variable_non_zero(struct expression *expr)
 373 {
 374         char *name;
 375         struct symbol *sym;
 376         struct smatch_state *state;
 377         int ret = UNDEFINED;
 378
 379         name = get_variable_from_expr(expr, &sym);
 380         if (!name || !sym)
 381                 goto exit;
 382         state = get_state(name, my_id, sym);
 383         if (!state || !state->data)
 384                 goto exit;
 385         ret = true_comparison(get_single_value((struct data_info *)state->data),
 386                               SPECIAL_NOTEQUAL, 0);
 387 exit:
 388         free_string(name);
 389         return ret;
 390 }
 391
 392 int known_condition_true(struct expression *expr)
 393 {
 394         int tmp;
 395
 396         if (!expr)
 397                 return 0;
 398
 399         tmp = get_value(expr);
 400         if (tmp && tmp != UNDEFINED)
 401                 return 1;
 402
 403         expr = strip_expr(expr);
 404         switch(expr->type) {
 405         case EXPR_PREOP:
 406                 if (expr->op == '!') {
 407                         if (known_condition_false(expr->unop))
 408                                 return 1;
 409                         break;
 410                 }
 411                 break;
 412         default:
 413                 break;
 414         }
 415         return 0;
 416 }
 417
 418 int known_condition_false(struct expression *expr)
 419 {
 420         if (!expr)
 421                 return 0;
 422
 423         if (is_zero(expr))
 424                 return 1;
 425
 426         switch(expr->type) {
 427         case EXPR_PREOP:
 428                 if (expr->op == '!') {
 429                         if (known_condition_true(expr->unop))
 430                                 return 1;
 431                         break;
 432                 }
 433                 break;
 434         default:
 435                 break;
 436         }
 437         return 0;
 438 }
 439
 440 int implied_condition_true(struct expression *expr)
 441 {
 442         struct statement *stmt;
 443         int tmp;
 444
 445         if (!expr)
 446                 return 0;
 447
 448         tmp = get_value(expr);
 449         if (tmp && tmp != UNDEFINED)
 450                 return 1;
 451
 452         expr = strip_expr(expr);
 453         switch(expr->type) {
 454         case EXPR_COMPARE:
 455                 if (do_comparison(expr) == 1)
 456                         return 1;
 457                 break;
 458         case EXPR_PREOP:
 459                 if (expr->op == '!') {
 460                         if (implied_condition_false(expr->unop))
 461                                 return 1;
 462                         break;
 463                 }
 464                 stmt = get_block_thing(expr);
 465                 if (stmt && (last_stmt_val(stmt) == 1))
 466                         return 1;
 467                 break;
 468         default:
 469                 if (variable_non_zero(expr) == 1)
 470                         return 1;
 471                 break;
 472         }
 473         return 0;
 474 }
 475
 476 int implied_condition_false(struct expression *expr)
 477 {
 478         struct statement *stmt;
 479         struct expression *tmp;
 480
 481         if (!expr)
 482                 return 0;
 483
 484         if (is_zero(expr))
 485                 return 1;
 486
 487         switch(expr->type) {
 488         case EXPR_COMPARE:
 489                 if (do_comparison(expr) == 0)
 490                         return 1;
 491         case EXPR_PREOP:
 492                 if (expr->op == '!') {
 493                         if (implied_condition_true(expr->unop))
 494                                 return 1;
 495                         break;
 496                 }
 497                 stmt = get_block_thing(expr);
 498                 if (stmt && (last_stmt_val(stmt) == 0))
 499                         return 1;
 500                 tmp = strip_expr(expr);
 501                 if (tmp != expr)
 502                         return implied_condition_false(tmp);
 503                 break;
 504         default:
 505                 if (variable_non_zero(expr) == 0)
 506                         return 1;
 507                 break;
 508         }
 509         return 0;
 510 }
 511
 512 void register_smatch_extra(int id)
 513 {
 514         my_id = id;
 515         add_merge_hook(my_id, &merge_func);
 516         add_unmatched_state_hook(my_id, &unmatched_state);
 517         add_hook(&undef_expr, OP_HOOK);
 518         add_hook(&match_function_def, FUNC_DEF_HOOK);
 519         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 520         add_hook(&match_assign, ASSIGNMENT_HOOK);
 521         add_hook(&match_declarations, DECLARATION_HOOK);
 522         add_hook(&match_unop, OP_HOOK);
 523         add_hook(&free_data_info_allocs, END_FUNC_HOOK);
 524
 525 #ifdef KERNEL
 526         /* I don't know how to test for the ATTRIB_NORET attribute. :( */
 527         add_function_hook("panic", &__match_nullify_path_hook, NULL);
 528         add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
 529         add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
 530         add_function_hook("__module_put_and_exit", &__match_nullify_path_hook, NULL);
 531         add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);
 532 #endif
 533 }