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 static 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_string(name);
  49         return state;
  50 }
  51
  52 static struct smatch_state *merge_func(const char *name, struct symbol *sym,
  53                                        struct smatch_state *s1,
  54                                        struct smatch_state *s2)
  55 {
  56         struct data_info *info1 = (struct data_info *)s1->data;
  57         struct data_info *info2 = (struct data_info *)s2->data;
  58         struct smatch_state *tmp;
  59
  60         tmp = alloc_extra_state_no_name(UNDEFINED);
  61         tmp->name = "extra_merged";
  62         ((struct data_info *)tmp->data)->merged = 1;
  63         ((struct data_info *)tmp->data)->values =
  64                 num_list_union(info1->values, info2->values);
  65         return tmp;
  66 }
  67
  68 struct sm_state *__extra_merge(struct sm_state *one, struct state_list *slist1,
  69                                struct sm_state *two, struct state_list *slist2)
  70 {
  71         struct data_info *info1;
  72         struct data_info *info2;
  73
  74         if (!one->state->data || !two->state->data) {
  75                 smatch_msg("internal error in smatch extra '%s = %s or %s'",
  76                            one->name, show_state(one->state),
  77                            show_state(two->state));
  78                 return alloc_state(one->name, one->owner, one->sym,
  79                                    &extra_undefined);
  80         }
  81
  82         info1 = (struct data_info *)one->state->data;
  83         info2 = (struct data_info *)two->state->data;
  84
  85         if (!info1->merged)
  86                 free_stack(&one->my_pools);
  87         if (!info2->merged)
  88                 free_stack(&two->my_pools);
  89
  90         if (one == two && !one->my_pools) {
  91                 add_pool(&one->my_pools, slist1);
  92                 add_pool(&one->my_pools, slist2);
  93         } else {
  94                 if (!one->my_pools)
  95                         add_pool(&one->my_pools, slist1);
  96                 if (!two->my_pools)
  97                         add_pool(&two->my_pools, slist2);
  98         }
  99
 100         add_pool(&one->all_pools, slist1);
 101         add_pool(&two->all_pools, slist2);
 102         return merge_sm_states(one, two);
 103 }
 104
 105 struct sm_state *__extra_and_merge(struct sm_state *sm,
 106                                      struct state_list_stack *stack)
 107 {
 108         struct state_list *slist;
 109         struct sm_state *ret = NULL;
 110         struct sm_state *tmp;
 111         int i = 0;
 112
 113         FOR_EACH_PTR(stack, slist) {
 114                 if (!i++) {
 115                         ret = get_sm_state_slist(slist, sm->name, sm->owner,
 116                                                  sm->sym);
 117                 } else {
 118                         tmp = get_sm_state_slist(slist, sm->name, sm->owner,
 119                                                  sm->sym);
 120                         ret = merge_sm_states(ret, tmp);
 121                 }
 122         } END_FOR_EACH_PTR(slist);
 123         if (!ret) {
 124                 smatch_msg("Internal error in __extra_and_merge");
 125                 return NULL;
 126         }
 127         ret->my_pools = stack;
 128         ret->all_pools = clone_stack(stack);
 129         return ret;
 130 }
 131
 132 static struct smatch_state *unmatched_state(struct sm_state *sm)
 133 {
 134         return &extra_undefined;
 135 }
 136
 137 static void match_function_call(struct expression *expr)
 138 {
 139         struct expression *tmp;
 140         struct symbol *sym;
 141         char *name;
 142         int i = 0;
 143
 144         FOR_EACH_PTR(expr->args, tmp) {
 145                 if (tmp->op == '&') {
 146                         name = get_variable_from_expr(tmp->unop, &sym);
 147                         if (name) {
 148                                 set_state(name, my_id, sym, &extra_undefined);
 149                         }
 150                         free_string(name);
 151                 }
 152                 i++;
 153         } END_FOR_EACH_PTR(tmp);
 154 }
 155
 156 static void match_assign(struct expression *expr)
 157 {
 158         struct expression *left;
 159         struct symbol *sym;
 160         char *name;
 161
 162         left = strip_expr(expr->left);
 163         name = get_variable_from_expr(left, &sym);
 164         if (!name)
 165                 return;
 166         set_state(name, my_id, sym, alloc_extra_state(get_value(expr->right)));
 167         free_string(name);
 168 }
 169
 170 static void undef_expr(struct expression *expr)
 171 {
 172         struct symbol *sym;
 173         char *name;
 174
 175         name = get_variable_from_expr(expr->unop, &sym);
 176         if (!name)
 177                 return;
 178         if (!get_state(name, my_id, sym)) {
 179                 free_string(name);
 180                 return;
 181         }
 182         set_state(name, my_id, sym, &extra_undefined);
 183         free_string(name);
 184 }
 185
 186 static void match_declarations(struct symbol *sym)
 187 {
 188         const char *name;
 189
 190         if (sym->ident) {
 191                 name = sym->ident->name;
 192                 if (sym->initializer) {
 193                         set_state(name, my_id, sym, alloc_extra_state(get_value(sym->initializer)));
 194                 } else {
 195                         set_state(name, my_id, sym, &extra_undefined);
 196                 }
 197         }
 198 }
 199
 200 static void match_function_def(struct symbol *sym)
 201 {
 202         struct symbol *arg;
 203
 204         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 205                 if (!arg->ident) {
 206                         continue;
 207                 }
 208                 set_state(arg->ident->name, my_id, arg, &extra_undefined);
 209         } END_FOR_EACH_PTR(arg);
 210 }
 211
 212 static void match_unop(struct expression *expr)
 213 {
 214         struct symbol *sym;
 215         char *name;
 216         const char *tmp;
 217
 218
 219         name = get_variable_from_expr(expr->unop, &sym);
 220         if (!name)
 221                 return;
 222
 223         tmp = show_special(expr->op);
 224         if ((!strcmp(tmp, "--")) || (!strcmp(tmp, "++")))
 225                 set_state(name, my_id, sym, &extra_undefined);
 226         free_string(name);
 227 }
 228
 229 static int expr_to_val(struct expression *expr)
 230 {
 231         struct smatch_state *state;
 232         int val;
 233         struct symbol *sym;
 234         char *name;
 235
 236         val = get_value(expr);
 237         if (val != UNDEFINED)
 238                 return val;
 239
 240         name = get_variable_from_expr(expr, &sym);
 241         if (!name)
 242                 return UNDEFINED;
 243         state = get_state(name, my_id, sym);
 244         free_string(name);
 245         if (!state || !state->data)
 246                 return UNDEFINED;
 247         return get_single_value((struct data_info *)state->data);
 248 }
 249
 250 int true_comparison(int left, int comparison, int right)
 251 {
 252         switch(comparison){
 253         case '<':
 254         case SPECIAL_UNSIGNED_LT:
 255                 if (left < right)
 256                         return 1;
 257                 return 0;
 258         case SPECIAL_UNSIGNED_LTE:
 259         case SPECIAL_LTE:
 260                 if (left < right)
 261                         return 1;
 262         case SPECIAL_EQUAL:
 263                 if (left == right)
 264                         return 1;
 265                 return 0;
 266         case SPECIAL_UNSIGNED_GTE:
 267         case SPECIAL_GTE:
 268                 if (left == right)
 269                         return 1;
 270         case '>':
 271         case SPECIAL_UNSIGNED_GT:
 272                 if (left > right)
 273                         return 1;
 274                 return 0;
 275         case SPECIAL_NOTEQUAL:
 276                 if (left != right)
 277                         return 1;
 278                 return 0;
 279         default:
 280                 smatch_msg("unhandled comparison %d\n", comparison);
 281                 return UNDEFINED;
 282         }
 283         return 0;
 284 }
 285
 286 static int do_comparison(struct expression *expr)
 287 {
 288         int left, right, ret;
 289
 290         if ((left = expr_to_val(expr->left)) == UNDEFINED)
 291                 return UNDEFINED;
 292
 293         if ((right = expr_to_val(expr->right)) == UNDEFINED)
 294                 return UNDEFINED;
 295
 296         ret = true_comparison(left, expr->op, right);
 297         if (ret == 1) {
 298                 SM_DEBUG("%d known condition: %d %s %d => true\n",
 299                         get_lineno(), left, show_special(expr->op), right);
 300         } else if (ret == 0) {
 301                 SM_DEBUG("%d known condition: %d %s %d => false\n",
 302                         get_lineno(), left, show_special(expr->op), right);
 303         }
 304         return ret;
 305 }
 306
 307 int last_stmt_val(struct statement *stmt)
 308 {
 309         struct expression *expr;
 310
 311         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 312         if (stmt->type != STMT_EXPRESSION)
 313                 return UNDEFINED;
 314         expr = stmt->expression;
 315         return get_value(expr);
 316 }
 317
 318 static int variable_non_zero(struct expression *expr)
 319 {
 320         char *name;
 321         struct symbol *sym;
 322         struct smatch_state *state;
 323         int ret = UNDEFINED;
 324
 325         name = get_variable_from_expr(expr, &sym);
 326         if (!name || !sym)
 327                 goto exit;
 328         state = get_state(name, my_id, sym);
 329         if (!state || !state->data)
 330                 goto exit;
 331         ret = true_comparison(get_single_value((struct data_info *)state->data),
 332                               SPECIAL_NOTEQUAL, 0);
 333 exit:
 334         free_string(name);
 335         return ret;
 336 }
 337
 338 int known_condition_true(struct expression *expr)
 339 {
 340         struct statement *stmt;
 341         int tmp;
 342
 343         if (!expr)
 344                 return 0;
 345
 346         tmp = get_value(expr);
 347         if (tmp && tmp != UNDEFINED)
 348                 return 1;
 349
 350         expr = strip_expr(expr);
 351         switch(expr->type) {
 352         case EXPR_COMPARE:
 353                 if (do_comparison(expr) == 1)
 354                         return 1;
 355                 break;
 356         case EXPR_PREOP:
 357                 if (expr->op == '!') {
 358                         if (known_condition_false(expr->unop))
 359                                 return 1;
 360                         break;
 361                 }
 362                 stmt = get_block_thing(expr);
 363                 if (stmt && (last_stmt_val(stmt) == 1))
 364                         return 1;
 365                 break;
 366         default:
 367                 if (variable_non_zero(expr) == 1)
 368                         return 1;
 369                 break;
 370         }
 371         return 0;
 372 }
 373
 374 int known_condition_false(struct expression *expr)
 375 {
 376         struct statement *stmt;
 377         struct expression *tmp;
 378
 379         if (!expr)
 380                 return 0;
 381
 382         if (is_zero(expr))
 383                 return 1;
 384
 385         switch(expr->type) {
 386         case EXPR_COMPARE:
 387                 if (do_comparison(expr) == 0)
 388                         return 1;
 389         case EXPR_PREOP:
 390                 if (expr->op == '!') {
 391                         if (known_condition_true(expr->unop))
 392                                 return 1;
 393                         break;
 394                 }
 395                 stmt = get_block_thing(expr);
 396                 if (stmt && (last_stmt_val(stmt) == 0))
 397                         return 1;
 398                 tmp = strip_expr(expr);
 399                 if (tmp != expr)
 400                         return known_condition_false(tmp);
 401                 break;
 402         default:
 403                 if (variable_non_zero(expr) == 0)
 404                         return 1;
 405                 break;
 406         }
 407         return 0;
 408 }
 409
 410 void register_smatch_extra(int id)
 411 {
 412         my_id = id;
 413         add_merge_hook(my_id, &merge_func);
 414         add_unmatched_state_hook(my_id, &unmatched_state);
 415         add_hook(&undef_expr, OP_HOOK);
 416         add_hook(&match_function_def, FUNC_DEF_HOOK);
 417         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 418         add_hook(&match_assign, ASSIGNMENT_HOOK);
 419         add_hook(&match_declarations, DECLARATION_HOOK);
 420         add_hook(&match_unop, OP_HOOK);
 421 #ifdef KERNEL
 422         /* I don't know how to test for the ATTRIB_NORET attribute. :( */
 423         add_function_hook("panic", &__match_nullify_path_hook, NULL);
 424         add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
 425         add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
 426         add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);
 427 #endif
 428 }