check_kernel.c

   1 /*
   2  * Copyright (C) 2010 Dan Carpenter.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, see http://www.gnu.org/copyleft/gpl.txt
  16  */
  17
  18 /*
  19  * This is kernel specific stuff for smatch_extra.
  20  */
  21
  22 #include "scope.h"
  23 #include "smatch.h"
  24 #include "smatch_extra.h"
  25
  26 static sval_t err_ptr_min = {
  27         .type = &ptr_ctype,
  28         .value = -4095,
  29 };
  30 static sval_t err_ptr_max = {
  31         .type = &ptr_ctype,
  32         .value = -1,
  33 };
  34 static sval_t null_ptr = {
  35         .type = &ptr_ctype,
  36         .value = 0,
  37 };
  38
  39 static int implied_err_cast_return(struct expression *call, void *unused, struct range_list **rl)
  40 {
  41         struct expression *arg;
  42
  43         arg = get_argument_from_call_expr(call->args, 0);
  44         if (!get_implied_rl(arg, rl)) {
  45                 *rl = alloc_rl(err_ptr_min, err_ptr_max);
  46                 *rl = cast_rl(get_type(arg), *rl);
  47         }
  48         return 1;
  49 }
  50
  51 static void hack_ERR_PTR(struct symbol *sym)
  52 {
  53         struct symbol *arg;
  54         struct smatch_state *estate;
  55         struct range_list *after;
  56         sval_t low_error = {
  57                 .type = &long_ctype,
  58                 .value = -4095,
  59         };
  60         sval_t minus_one = {
  61                 .type = &long_ctype,
  62                 .value = -1,
  63         };
  64         sval_t zero = {
  65                 .type = &long_ctype,
  66                 .value = 0,
  67         };
  68
  69         if (!sym || !sym->ident)
  70                 return;
  71         if (strcmp(sym->ident->name, "ERR_PTR") != 0)
  72                 return;
  73
  74         arg = first_ptr_list((struct ptr_list *)sym->ctype.base_type->arguments);
  75         if (!arg || !arg->ident)
  76                 return;
  77
  78         estate = get_state(SMATCH_EXTRA, arg->ident->name, arg);
  79         if (!estate) {
  80                 after = alloc_rl(low_error, minus_one);
  81         } else {
  82                 after = rl_intersection(estate_rl(estate), alloc_rl(low_error, zero));
  83                 if (rl_equiv(estate_rl(estate), after))
  84                         return;
  85         }
  86         set_state(SMATCH_EXTRA, arg->ident->name, arg, alloc_estate_rl(after));
  87 }
  88
  89 static void match_param_valid_ptr(const char *fn, struct expression *call_expr,
  90                         struct expression *assign_expr, void *_param)
  91 {
  92         int param = PTR_INT(_param);
  93         struct expression *arg;
  94         struct smatch_state *pre_state;
  95         struct smatch_state *end_state;
  96         struct range_list *rl;
  97
  98         arg = get_argument_from_call_expr(call_expr->args, param);
  99         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 100         if (estate_rl(pre_state)) {
 101                 rl = estate_rl(pre_state);
 102                 rl = remove_range(rl, null_ptr, null_ptr);
 103                 rl = remove_range(rl, err_ptr_min, err_ptr_max);
 104         } else {
 105                 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 106         }
 107         end_state = alloc_estate_rl(rl);
 108         set_extra_expr_nomod(arg, end_state);
 109 }
 110
 111 static void match_param_err_or_null(const char *fn, struct expression *call_expr,
 112                         struct expression *assign_expr, void *_param)
 113 {
 114         int param = PTR_INT(_param);
 115         struct expression *arg;
 116         struct range_list *rl;
 117         struct smatch_state *pre_state;
 118         struct smatch_state *end_state;
 119
 120         arg = get_argument_from_call_expr(call_expr->args, param);
 121         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 122         call_results_to_rl(call_expr, &ptr_ctype, "0,(-4095)-(-1)", &rl);
 123         rl = rl_intersection(estate_rl(pre_state), rl);
 124         rl = cast_rl(get_type(arg), rl);
 125         end_state = alloc_estate_rl(rl);
 126         set_extra_expr_nomod(arg, end_state);
 127 }
 128
 129 static void match_not_err(const char *fn, struct expression *call_expr,
 130                         struct expression *assign_expr, void *unused)
 131 {
 132         struct expression *arg;
 133         struct smatch_state *pre_state;
 134         struct range_list *rl;
 135
 136         arg = get_argument_from_call_expr(call_expr->args, 0);
 137         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 138         if (estate_rl(pre_state)) {
 139                 rl = estate_rl(pre_state);
 140                 rl = remove_range(rl, err_ptr_min, err_ptr_max);
 141         } else {
 142                 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 143         }
 144         rl = cast_rl(get_type(arg), rl);
 145         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 146 }
 147
 148 static void match_err(const char *fn, struct expression *call_expr,
 149                         struct expression *assign_expr, void *unused)
 150 {
 151         struct expression *arg;
 152         struct smatch_state *pre_state;
 153         struct range_list *rl;
 154
 155         arg = get_argument_from_call_expr(call_expr->args, 0);
 156         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 157         rl = estate_rl(pre_state);
 158         if (!rl)
 159                 rl = alloc_rl(err_ptr_min, err_ptr_max);
 160         rl = rl_intersection(rl, alloc_rl(err_ptr_min, err_ptr_max));
 161         rl = cast_rl(get_type(arg), rl);
 162         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 163 }
 164
 165 static void match_container_of_macro(const char *fn, struct expression *expr, void *unused)
 166 {
 167         set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 168 }
 169
 170 static void match_container_of(struct expression *expr)
 171 {
 172         struct expression *right = expr->right;
 173         char *macro;
 174
 175         /*
 176          * The problem here is that sometimes the container_of() macro is itself
 177          * inside a macro and get_macro() only returns the name of the outside
 178          * macro.
 179          */
 180
 181         /*
 182          * This actually an expression statement assignment but smatch_flow
 183          * pre-mangles it for us so we only get the last chunk:
 184          * sk = (typeof(sk))((char *)__mptr - offsetof(...))
 185          */
 186
 187         macro = get_macro_name(right->pos);
 188         if (!macro)
 189                 return;
 190         if (right->type != EXPR_CAST)
 191                 return;
 192         right = strip_expr(right);
 193         if (right->type != EXPR_BINOP || right->op != '-' ||
 194             right->left->type != EXPR_CAST)
 195                 return;
 196         right = strip_expr(right->left);
 197         if (right->type != EXPR_SYMBOL)
 198                 return;
 199         if (!right->symbol->ident ||
 200             strcmp(right->symbol->ident->name, "__mptr") != 0)
 201                 return;
 202         set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 203 }
 204
 205 static int match_next_bit(struct expression *call, void *unused, struct range_list **rl)
 206 {
 207         struct expression *start_arg;
 208         struct expression *size_arg;
 209         struct symbol *type;
 210         sval_t min, max, tmp;
 211
 212         size_arg = get_argument_from_call_expr(call->args, 1);
 213         /* btw. there isn't a start_arg for find_first_bit() */
 214         start_arg = get_argument_from_call_expr(call->args, 2);
 215
 216         type = get_type(call);
 217         min = sval_type_val(type, 0);
 218         max = sval_type_val(type, sizeof(long long) * 8);
 219
 220         if (get_implied_max(size_arg, &tmp) && tmp.uvalue < max.value)
 221                 max = tmp;
 222         if (start_arg && get_implied_min(start_arg, &tmp) && !sval_is_negative(tmp))
 223                 min = tmp;
 224         if (sval_cmp(min, max) > 0)
 225                 max = min;
 226         min = sval_cast(type, min);
 227         max = sval_cast(type, max);
 228         *rl = alloc_rl(min, max);
 229         return 1;
 230 }
 231
 232 static int match_fls(struct expression *call, void *unused, struct range_list **rl)
 233 {
 234         struct expression *arg;
 235         struct range_list *arg_rl;
 236         sval_t zero = {};
 237         sval_t start = {
 238                 .type = &int_ctype,
 239                 .value = 0,
 240         };
 241         sval_t end = {
 242                 .type = &int_ctype,
 243                 .value = 32,
 244         };
 245         sval_t sval;
 246
 247         arg = get_argument_from_call_expr(call->args, 0);
 248         if (!get_implied_rl(arg, &arg_rl))
 249                 return 0;
 250         if (rl_to_sval(arg_rl, &sval)) {
 251                 int i;
 252
 253                 for (i = 63; i >= 0; i--) {
 254                         if (sval.uvalue & 1ULL << i)
 255                                 break;
 256                 }
 257                 sval.value = i + 1;
 258                 *rl = alloc_rl(sval, sval);
 259                 return 1;
 260         }
 261         zero.type = rl_type(arg_rl);
 262         if (!rl_has_sval(arg_rl, zero))
 263                 start.value = 1;
 264         *rl = alloc_rl(start, end);
 265         return 1;
 266 }
 267
 268
 269
 270 static void find_module_init_exit(struct symbol_list *sym_list)
 271 {
 272         struct symbol *sym;
 273         struct symbol *fn;
 274         struct statement *stmt;
 275         char *name;
 276         int init;
 277         int count;
 278
 279         /*
 280          * This is more complicated because Sparse ignores the "alias"
 281          * attribute.  I search backwards because module_init() is normally at
 282          * the end of the file.
 283          */
 284         count = 0;
 285         FOR_EACH_PTR_REVERSE(sym_list, sym) {
 286                 if (sym->type != SYM_NODE)
 287                         continue;
 288                 if (!(sym->ctype.modifiers & MOD_STATIC))
 289                         continue;
 290                 fn = get_base_type(sym);
 291                 if (!fn)
 292                         continue;
 293                 if (fn->type != SYM_FN)
 294                         continue;
 295                 if (!sym->ident)
 296                         continue;
 297                 if (!fn->inline_stmt)
 298                         continue;
 299                 if (strcmp(sym->ident->name, "__inittest") == 0)
 300                         init = 1;
 301                 else if (strcmp(sym->ident->name, "__exittest") == 0)
 302                         init = 0;
 303                 else
 304                         continue;
 305
 306                 count++;
 307
 308                 stmt = first_ptr_list((struct ptr_list *)fn->inline_stmt->stmts);
 309                 if (!stmt || stmt->type != STMT_RETURN)
 310                         continue;
 311                 name = expr_to_var(stmt->ret_value);
 312                 if (!name)
 313                         continue;
 314                 if (init)
 315                         sql_insert_function_ptr(name, "(struct module)->init");
 316                 else
 317                         sql_insert_function_ptr(name, "(struct module)->exit");
 318                 free_string(name);
 319                 if (count >= 2)
 320                         return;
 321         } END_FOR_EACH_PTR_REVERSE(sym);
 322 }
 323
 324 static void match_end_file(struct symbol_list *sym_list)
 325 {
 326         struct symbol *sym;
 327
 328         /* find the last static symbol in the file */
 329         FOR_EACH_PTR_REVERSE(sym_list, sym) {
 330                 if (!(sym->ctype.modifiers & MOD_STATIC))
 331                         continue;
 332                 if (!sym->scope)
 333                         continue;
 334                 find_module_init_exit(sym->scope->symbols);
 335                 return;
 336         } END_FOR_EACH_PTR_REVERSE(sym);
 337 }
 338
 339 static struct expression *get_val_expr(struct expression *expr)
 340 {
 341         struct symbol *sym, *val;
 342
 343         if (expr->type != EXPR_DEREF)
 344                 return NULL;
 345         expr = expr->deref;
 346         if (expr->type != EXPR_SYMBOL)
 347                 return NULL;
 348         if (strcmp(expr->symbol_name->name, "__u") != 0)
 349                 return NULL;
 350         sym = get_base_type(expr->symbol);
 351         val = first_ptr_list((struct ptr_list *)sym->symbol_list);
 352         if (!val || strcmp(val->ident->name, "__val") != 0)
 353                 return NULL;
 354         return member_expression(expr, '.', val->ident);
 355 }
 356
 357 static void match__write_once_size(const char *fn, struct expression *call,
 358                                void *unused)
 359 {
 360         struct expression *dest, *data, *assign;
 361         struct range_list *rl;
 362
 363         dest = get_argument_from_call_expr(call->args, 0);
 364         if (dest->type != EXPR_PREOP || dest->op != '&')
 365                 return;
 366         dest = strip_expr(dest->unop);
 367
 368         data = get_argument_from_call_expr(call->args, 1);
 369         data = get_val_expr(data);
 370         if (!data)
 371                 return;
 372         get_absolute_rl(data, &rl);
 373         assign = assign_expression(dest, '=', data);
 374
 375         __in_fake_assign++;
 376         __split_expr(assign);
 377         __in_fake_assign--;
 378 }
 379
 380 static void match__read_once_size(const char *fn, struct expression *call,
 381                                void *unused)
 382 {
 383         struct expression *dest, *data, *assign;
 384         struct symbol *type, *val_sym;
 385
 386         /*
 387          * We want to change:
 388          *      __read_once_size_nocheck(&(x), __u.__c, sizeof(x));
 389          * into a fake assignment:
 390          *      __u.val = x;
 391          *
 392          */
 393
 394         data = get_argument_from_call_expr(call->args, 0);
 395         if (data->type != EXPR_PREOP || data->op != '&')
 396                 return;
 397         data = strip_parens(data->unop);
 398
 399         dest = get_argument_from_call_expr(call->args, 1);
 400         if (dest->type != EXPR_DEREF || dest->op != '.')
 401                 return;
 402         if (!dest->member || strcmp(dest->member->name, "__c") != 0)
 403                 return;
 404         dest = dest->deref;
 405         type = get_type(dest);
 406         if (!type)
 407                 return;
 408         val_sym = first_ptr_list((struct ptr_list *)type->symbol_list);
 409         dest = member_expression(dest, '.', val_sym->ident);
 410
 411         assign = assign_expression(dest, '=', data);
 412         __in_fake_assign++;
 413         __split_expr(assign);
 414         __in_fake_assign--;
 415 }
 416
 417 bool is_ignored_kernel_data(const char *name)
 418 {
 419         if (option_project != PROJ_KERNEL)
 420                 return false;
 421
 422         /*
 423          * On the file I was looking at lockdep was 25% of the DB.
 424          */
 425         if (strstr(name, ".dep_map."))
 426                 return true;
 427         if (strstr(name, ".lockdep_map."))
 428                 return true;
 429         return false;
 430 }
 431
 432 void check_kernel(int id)
 433 {
 434         if (option_project != PROJ_KERNEL)
 435                 return;
 436
 437         add_implied_return_hook("ERR_PTR", &implied_err_cast_return, NULL);
 438         add_implied_return_hook("ERR_CAST", &implied_err_cast_return, NULL);
 439         add_implied_return_hook("PTR_ERR", &implied_err_cast_return, NULL);
 440         add_hook(hack_ERR_PTR, AFTER_DEF_HOOK);
 441         return_implies_state("IS_ERR_OR_NULL", 0, 0, &match_param_valid_ptr, (void *)0);
 442         return_implies_state("IS_ERR_OR_NULL", 1, 1, &match_param_err_or_null, (void *)0);
 443         return_implies_state("IS_ERR", 0, 0, &match_not_err, NULL);
 444         return_implies_state("IS_ERR", 1, 1, &match_err, NULL);
 445         return_implies_state("tomoyo_memory_ok", 1, 1, &match_param_valid_ptr, (void *)0);
 446
 447         add_macro_assign_hook_extra("container_of", &match_container_of_macro, NULL);
 448         add_hook(match_container_of, ASSIGNMENT_HOOK);
 449
 450         add_implied_return_hook("find_next_bit", &match_next_bit, NULL);
 451         add_implied_return_hook("find_next_zero_bit", &match_next_bit, NULL);
 452         add_implied_return_hook("find_first_bit", &match_next_bit, NULL);
 453         add_implied_return_hook("find_first_zero_bit", &match_next_bit, NULL);
 454
 455         add_implied_return_hook("fls", &match_fls, NULL);
 456         add_implied_return_hook("fls64", &match_fls, NULL);
 457
 458         add_function_hook("__ftrace_bad_type", &__match_nullify_path_hook, NULL);
 459         add_function_hook("__write_once_size", &match__write_once_size, NULL);
 460
 461         add_function_hook("__read_once_size", &match__read_once_size, NULL);
 462         add_function_hook("__read_once_size_nocheck", &match__read_once_size, NULL);
 463
 464         if (option_info)
 465                 add_hook(match_end_file, END_FILE_HOOK);
 466 }