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 static struct smatch_state *unmatched_state(struct sm_state *sm)
 106 {
 107         return &extra_undefined;
 108 }
 109
 110 static void match_function_call(struct expression *expr)
 111 {
 112         struct expression *tmp;
 113         struct symbol *sym;
 114         char *name;
 115         int i = 0;
 116
 117         FOR_EACH_PTR(expr->args, tmp) {
 118                 if (tmp->op == '&') {
 119                         name = get_variable_from_expr(tmp->unop, &sym);
 120                         if (name) {
 121                                 set_state(name, my_id, sym, &extra_undefined);
 122                         }
 123                         free_string(name);
 124                 }
 125                 i++;
 126         } END_FOR_EACH_PTR(tmp);
 127 }
 128
 129 static void match_assign(struct expression *expr)
 130 {
 131         struct expression *left;
 132         struct symbol *sym;
 133         char *name;
 134
 135         left = strip_expr(expr->left);
 136         name = get_variable_from_expr(left, &sym);
 137         if (!name)
 138                 return;
 139         set_state(name, my_id, sym, alloc_extra_state(get_value(expr->right)));
 140         free_string(name);
 141 }
 142
 143 static void undef_expr(struct expression *expr)
 144 {
 145         struct symbol *sym;
 146         char *name;
 147
 148         name = get_variable_from_expr(expr->unop, &sym);
 149         if (!name)
 150                 return;
 151         if (!get_state(name, my_id, sym)) {
 152                 free_string(name);
 153                 return;
 154         }
 155         set_state(name, my_id, sym, &extra_undefined);
 156         free_string(name);
 157 }
 158
 159 static void match_declarations(struct symbol *sym)
 160 {
 161         const char *name;
 162
 163         if (sym->ident) {
 164                 name = sym->ident->name;
 165                 if (sym->initializer) {
 166                         set_state(name, my_id, sym, alloc_extra_state(get_value(sym->initializer)));
 167                 } else {
 168                         set_state(name, my_id, sym, &extra_undefined);
 169                 }
 170         }
 171 }
 172
 173 static void match_function_def(struct symbol *sym)
 174 {
 175         struct symbol *arg;
 176
 177         FOR_EACH_PTR(sym->ctype.base_type->arguments, arg) {
 178                 if (!arg->ident) {
 179                         continue;
 180                 }
 181                 set_state(arg->ident->name, my_id, arg, &extra_undefined);
 182         } END_FOR_EACH_PTR(arg);
 183 }
 184
 185 static void match_unop(struct expression *expr)
 186 {
 187         struct symbol *sym;
 188         char *name;
 189         const char *tmp;
 190
 191
 192         name = get_variable_from_expr(expr->unop, &sym);
 193         if (!name)
 194                 return;
 195
 196         tmp = show_special(expr->op);
 197         if ((!strcmp(tmp, "--")) || (!strcmp(tmp, "++")))
 198                 set_state(name, my_id, sym, &extra_undefined);
 199         free_string(name);
 200 }
 201
 202 static int expr_to_val(struct expression *expr)
 203 {
 204         struct smatch_state *state;
 205         int val;
 206         struct symbol *sym;
 207         char *name;
 208
 209         val = get_value(expr);
 210         if (val != UNDEFINED)
 211                 return val;
 212
 213         name = get_variable_from_expr(expr, &sym);
 214         if (!name)
 215                 return UNDEFINED;
 216         state = get_state(name, my_id, sym);
 217         free_string(name);
 218         if (!state || !state->data)
 219                 return UNDEFINED;
 220         return get_single_value((struct data_info *)state->data);
 221 }
 222
 223 int true_comparison(int left, int comparison, int right)
 224 {
 225         switch(comparison){
 226         case '<':
 227         case SPECIAL_UNSIGNED_LT:
 228                 if (left < right)
 229                         return 1;
 230                 return 0;
 231         case SPECIAL_UNSIGNED_LTE:
 232         case SPECIAL_LTE:
 233                 if (left < right)
 234                         return 1;
 235         case SPECIAL_EQUAL:
 236                 if (left == right)
 237                         return 1;
 238                 return 0;
 239         case SPECIAL_UNSIGNED_GTE:
 240         case SPECIAL_GTE:
 241                 if (left == right)
 242                         return 1;
 243         case '>':
 244         case SPECIAL_UNSIGNED_GT:
 245                 if (left > right)
 246                         return 1;
 247                 return 0;
 248         case SPECIAL_NOTEQUAL:
 249                 if (left != right)
 250                         return 1;
 251                 return 0;
 252         default:
 253                 smatch_msg("unhandled comparison %d\n", comparison);
 254                 return UNDEFINED;
 255         }
 256         return 0;
 257 }
 258
 259 static int do_comparison(struct expression *expr)
 260 {
 261         int left, right, ret;
 262
 263         if ((left = expr_to_val(expr->left)) == UNDEFINED)
 264                 return UNDEFINED;
 265
 266         if ((right = expr_to_val(expr->right)) == UNDEFINED)
 267                 return UNDEFINED;
 268
 269         ret = true_comparison(left, expr->op, right);
 270         if (ret == 1) {
 271                 SM_DEBUG("%d known condition: %d %s %d => true\n",
 272                         get_lineno(), left, show_special(expr->op), right);
 273         } else if (ret == 0) {
 274                 SM_DEBUG("%d known condition: %d %s %d => false\n",
 275                         get_lineno(), left, show_special(expr->op), right);
 276         }
 277         return ret;
 278 }
 279
 280 int last_stmt_val(struct statement *stmt)
 281 {
 282         struct expression *expr;
 283
 284         stmt = last_ptr_list((struct ptr_list *)stmt->stmts);
 285         if (stmt->type != STMT_EXPRESSION)
 286                 return UNDEFINED;
 287         expr = stmt->expression;
 288         return get_value(expr);
 289 }
 290
 291 static int variable_non_zero(struct expression *expr)
 292 {
 293         char *name;
 294         struct symbol *sym;
 295         struct smatch_state *state;
 296         int ret = UNDEFINED;
 297
 298         name = get_variable_from_expr(expr, &sym);
 299         if (!name || !sym)
 300                 goto exit;
 301         state = get_state(name, my_id, sym);
 302         if (!state || !state->data)
 303                 goto exit;
 304         ret = true_comparison(get_single_value((struct data_info *)state->data),
 305                               SPECIAL_NOTEQUAL, 0);
 306 exit:
 307         free_string(name);
 308         return ret;
 309 }
 310
 311 int known_condition_true(struct expression *expr)
 312 {
 313         struct statement *stmt;
 314         int tmp;
 315
 316         if (!expr)
 317                 return 0;
 318
 319         tmp = get_value(expr);
 320         if (tmp && tmp != UNDEFINED)
 321                 return 1;
 322
 323         expr = strip_expr(expr);
 324         switch(expr->type) {
 325         case EXPR_COMPARE:
 326                 if (do_comparison(expr) == 1)
 327                         return 1;
 328                 break;
 329         case EXPR_PREOP:
 330                 if (expr->op == '!') {
 331                         if (known_condition_false(expr->unop))
 332                                 return 1;
 333                         break;
 334                 }
 335                 stmt = get_block_thing(expr);
 336                 if (stmt && (last_stmt_val(stmt) == 1))
 337                         return 1;
 338                 break;
 339         default:
 340                 if (variable_non_zero(expr) == 1)
 341                         return 1;
 342                 break;
 343         }
 344         return 0;
 345 }
 346
 347 int known_condition_false(struct expression *expr)
 348 {
 349         struct statement *stmt;
 350         struct expression *tmp;
 351
 352         if (!expr)
 353                 return 0;
 354
 355         if (is_zero(expr))
 356                 return 1;
 357
 358         switch(expr->type) {
 359         case EXPR_COMPARE:
 360                 if (do_comparison(expr) == 0)
 361                         return 1;
 362         case EXPR_PREOP:
 363                 if (expr->op == '!') {
 364                         if (known_condition_true(expr->unop))
 365                                 return 1;
 366                         break;
 367                 }
 368                 stmt = get_block_thing(expr);
 369                 if (stmt && (last_stmt_val(stmt) == 0))
 370                         return 1;
 371                 tmp = strip_expr(expr);
 372                 if (tmp != expr)
 373                         return known_condition_false(tmp);
 374                 break;
 375         default:
 376                 if (variable_non_zero(expr) == 0)
 377                         return 1;
 378                 break;
 379         }
 380         return 0;
 381 }
 382
 383 void register_smatch_extra(int id)
 384 {
 385         my_id = id;
 386         add_merge_hook(my_id, &merge_func);
 387         add_unmatched_state_hook(my_id, &unmatched_state);
 388         add_hook(&undef_expr, OP_HOOK);
 389         add_hook(&match_function_def, FUNC_DEF_HOOK);
 390         add_hook(&match_function_call, FUNCTION_CALL_HOOK);
 391         add_hook(&match_assign, ASSIGNMENT_HOOK);
 392         add_hook(&match_declarations, DECLARATION_HOOK);
 393         add_hook(&match_unop, OP_HOOK);
 394 #ifdef KERNEL
 395         /* I don't know how to test for the ATTRIB_NORET attribute. :( */
 396         add_function_hook("panic", &__match_nullify_path_hook, NULL);
 397         add_function_hook("do_exit", &__match_nullify_path_hook, NULL);
 398         add_function_hook("complete_and_exit", &__match_nullify_path_hook, NULL);
 399         add_function_hook("do_group_exit", &__match_nullify_path_hook, NULL);
 400 #endif
 401 }