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
  47         *rl = cast_rl(get_type(call), *rl);
  48         return !!*rl;
  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 *pre, *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         if (pre_state)
 123                 pre = estate_rl(pre_state);
 124         else
 125                 pre = alloc_whole_rl(&ptr_ctype);
 126         call_results_to_rl(call_expr, &ptr_ctype, "0,(-4095)-(-1)", &rl);
 127         rl = rl_intersection(pre, rl);
 128         rl = cast_rl(get_type(arg), rl);
 129         end_state = alloc_estate_rl(rl);
 130         set_extra_expr_nomod(arg, end_state);
 131 }
 132
 133 static void match_not_err(const char *fn, struct expression *call_expr,
 134                         struct expression *assign_expr, void *unused)
 135 {
 136         struct expression *arg;
 137         struct smatch_state *pre_state;
 138         struct range_list *rl;
 139
 140         arg = get_argument_from_call_expr(call_expr->args, 0);
 141         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 142         if (pre_state) {
 143                 rl = estate_rl(pre_state);
 144                 rl = remove_range(rl, err_ptr_min, err_ptr_max);
 145         } else {
 146                 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 147         }
 148         rl = cast_rl(get_type(arg), rl);
 149         /* These are implied.  But implications don't work for empty states. */
 150         if (pre_state && rl)
 151                 return;
 152         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 153 }
 154
 155 static void match_err(const char *fn, struct expression *call_expr,
 156                         struct expression *assign_expr, void *unused)
 157 {
 158         struct expression *arg;
 159         struct smatch_state *pre_state;
 160         struct range_list *rl;
 161
 162         arg = get_argument_from_call_expr(call_expr->args, 0);
 163         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 164         rl = estate_rl(pre_state);
 165         if (!rl)
 166                 rl = alloc_rl(err_ptr_min, err_ptr_max);
 167         rl = rl_intersection(rl, alloc_rl(err_ptr_min, err_ptr_max));
 168         rl = cast_rl(get_type(arg), rl);
 169         if (pre_state && rl) {
 170                 /*
 171                  * Ideally this would all be handled by smatch_implied.c
 172                  * but it doesn't work very well for impossible paths.
 173                  *
 174                  */
 175                 return;
 176         }
 177         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 178 }
 179
 180 static void match_container_of_macro(const char *fn, struct expression *expr, void *unused)
 181 {
 182         set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 183 }
 184
 185 static void match_container_of(struct expression *expr)
 186 {
 187         struct expression *right = expr->right;
 188         char *macro;
 189
 190         /*
 191          * The problem here is that sometimes the container_of() macro is itself
 192          * inside a macro and get_macro() only returns the name of the outside
 193          * macro.
 194          */
 195
 196         /*
 197          * This actually an expression statement assignment but smatch_flow
 198          * pre-mangles it for us so we only get the last chunk:
 199          * sk = (typeof(sk))((char *)__mptr - offsetof(...))
 200          */
 201
 202         macro = get_macro_name(right->pos);
 203         if (!macro)
 204                 return;
 205         if (right->type != EXPR_CAST)
 206                 return;
 207         right = strip_expr(right);
 208         if (right->type != EXPR_BINOP || right->op != '-' ||
 209             right->left->type != EXPR_CAST)
 210                 return;
 211         right = strip_expr(right->left);
 212         if (right->type != EXPR_SYMBOL)
 213                 return;
 214         if (!right->symbol->ident ||
 215             strcmp(right->symbol->ident->name, "__mptr") != 0)
 216                 return;
 217         set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 218 }
 219
 220 static int match_next_bit(struct expression *call, void *unused, struct range_list **rl)
 221 {
 222         struct expression *start_arg;
 223         struct expression *size_arg;
 224         struct symbol *type;
 225         sval_t min, max, tmp;
 226
 227         size_arg = get_argument_from_call_expr(call->args, 1);
 228         /* btw. there isn't a start_arg for find_first_bit() */
 229         start_arg = get_argument_from_call_expr(call->args, 2);
 230
 231         type = get_type(call);
 232         min = sval_type_val(type, 0);
 233         max = sval_type_val(type, sizeof(long long) * 8);
 234
 235         if (get_implied_max(size_arg, &tmp) && tmp.uvalue < max.value)
 236                 max = tmp;
 237         if (start_arg && get_implied_min(start_arg, &tmp) && !sval_is_negative(tmp))
 238                 min = tmp;
 239         if (sval_cmp(min, max) > 0)
 240                 max = min;
 241         min = sval_cast(type, min);
 242         max = sval_cast(type, max);
 243         *rl = alloc_rl(min, max);
 244         return 1;
 245 }
 246
 247 static int match_array_size(struct expression *call, void *unused, struct range_list **rl)
 248 {
 249         struct expression *size;
 250         struct expression *count;
 251         struct expression *mult;
 252         struct range_list *ret;
 253
 254         size = get_argument_from_call_expr(call->args, 0);
 255         count = get_argument_from_call_expr(call->args, 1);
 256         mult = binop_expression(size, '*', count);
 257
 258         if (get_implied_rl(mult, &ret)) {
 259                 *rl = ret;
 260                 return 1;
 261         }
 262
 263         return 0;
 264 }
 265
 266 static int match_ffs(struct expression *call, void *unused, struct range_list **rl)
 267 {
 268         if (get_implied_rl(call, rl))
 269                 return true;
 270         return false;
 271 }
 272
 273 static int match_fls(struct expression *call, void *unused, struct range_list **rl)
 274 {
 275         struct expression *arg;
 276         struct range_list *arg_rl;
 277         sval_t zero = {};
 278         sval_t start = {
 279                 .type = &int_ctype,
 280                 .value = 0,
 281         };
 282         sval_t end = {
 283                 .type = &int_ctype,
 284                 .value = 32,
 285         };
 286         sval_t sval;
 287
 288         arg = get_argument_from_call_expr(call->args, 0);
 289         if (!get_implied_rl(arg, &arg_rl))
 290                 return 0;
 291         if (rl_to_sval(arg_rl, &sval)) {
 292                 int i;
 293
 294                 for (i = 63; i >= 0; i--) {
 295                         if (sval.uvalue & 1ULL << i)
 296                                 break;
 297                 }
 298                 sval.value = i + 1;
 299                 *rl = alloc_rl(sval, sval);
 300                 return 1;
 301         }
 302         zero.type = rl_type(arg_rl);
 303         if (!rl_has_sval(arg_rl, zero))
 304                 start.value = 1;
 305         *rl = alloc_rl(start, end);
 306         return 1;
 307 }
 308
 309 static void find_module_init_exit(struct symbol_list *sym_list)
 310 {
 311         struct symbol *sym;
 312         struct symbol *fn;
 313         struct statement *stmt;
 314         char *name;
 315         int init;
 316         int count;
 317
 318         /*
 319          * This is more complicated because Sparse ignores the "alias"
 320          * attribute.  I search backwards because module_init() is normally at
 321          * the end of the file.
 322          */
 323         count = 0;
 324         FOR_EACH_PTR_REVERSE(sym_list, sym) {
 325                 if (sym->type != SYM_NODE)
 326                         continue;
 327                 if (!(sym->ctype.modifiers & MOD_STATIC))
 328                         continue;
 329                 fn = get_base_type(sym);
 330                 if (!fn)
 331                         continue;
 332                 if (fn->type != SYM_FN)
 333                         continue;
 334                 if (!sym->ident)
 335                         continue;
 336                 if (!fn->inline_stmt)
 337                         continue;
 338                 if (strcmp(sym->ident->name, "__inittest") == 0)
 339                         init = 1;
 340                 else if (strcmp(sym->ident->name, "__exittest") == 0)
 341                         init = 0;
 342                 else
 343                         continue;
 344
 345                 count++;
 346
 347                 stmt = first_ptr_list((struct ptr_list *)fn->inline_stmt->stmts);
 348                 if (!stmt || stmt->type != STMT_RETURN)
 349                         continue;
 350                 name = expr_to_var(stmt->ret_value);
 351                 if (!name)
 352                         continue;
 353                 if (init)
 354                         sql_insert_function_ptr(name, "(struct module)->init");
 355                 else
 356                         sql_insert_function_ptr(name, "(struct module)->exit");
 357                 free_string(name);
 358                 if (count >= 2)
 359                         return;
 360         } END_FOR_EACH_PTR_REVERSE(sym);
 361 }
 362
 363 static void match_end_file(struct symbol_list *sym_list)
 364 {
 365         struct symbol *sym;
 366
 367         /* find the last static symbol in the file */
 368         FOR_EACH_PTR_REVERSE(sym_list, sym) {
 369                 if (!(sym->ctype.modifiers & MOD_STATIC))
 370                         continue;
 371                 if (!sym->scope)
 372                         continue;
 373                 find_module_init_exit(sym->scope->symbols);
 374                 return;
 375         } END_FOR_EACH_PTR_REVERSE(sym);
 376 }
 377
 378 static struct expression *get_val_expr(struct expression *expr)
 379 {
 380         struct symbol *sym, *val;
 381
 382         if (expr->type != EXPR_DEREF)
 383                 return NULL;
 384         expr = expr->deref;
 385         if (expr->type != EXPR_SYMBOL)
 386                 return NULL;
 387         if (strcmp(expr->symbol_name->name, "__u") != 0)
 388                 return NULL;
 389         sym = get_base_type(expr->symbol);
 390         val = first_ptr_list((struct ptr_list *)sym->symbol_list);
 391         if (!val || strcmp(val->ident->name, "__val") != 0)
 392                 return NULL;
 393         return member_expression(expr, '.', val->ident);
 394 }
 395
 396 static void match__write_once_size(const char *fn, struct expression *call,
 397                                void *unused)
 398 {
 399         struct expression *dest, *data, *assign;
 400         struct range_list *rl;
 401
 402         dest = get_argument_from_call_expr(call->args, 0);
 403         if (dest->type != EXPR_PREOP || dest->op != '&')
 404                 return;
 405         dest = strip_expr(dest->unop);
 406
 407         data = get_argument_from_call_expr(call->args, 1);
 408         data = get_val_expr(data);
 409         if (!data)
 410                 return;
 411         get_absolute_rl(data, &rl);
 412         assign = assign_expression(dest, '=', data);
 413
 414         __in_fake_assign++;
 415         __split_expr(assign);
 416         __in_fake_assign--;
 417 }
 418
 419 static void match__read_once_size(const char *fn, struct expression *call,
 420                                void *unused)
 421 {
 422         struct expression *dest, *data, *assign;
 423         struct symbol *type, *val_sym;
 424
 425         /*
 426          * We want to change:
 427          *      __read_once_size_nocheck(&(x), __u.__c, sizeof(x));
 428          * into a fake assignment:
 429          *      __u.val = x;
 430          *
 431          */
 432
 433         data = get_argument_from_call_expr(call->args, 0);
 434         if (data->type != EXPR_PREOP || data->op != '&')
 435                 return;
 436         data = strip_parens(data->unop);
 437
 438         dest = get_argument_from_call_expr(call->args, 1);
 439         if (dest->type != EXPR_DEREF || dest->op != '.')
 440                 return;
 441         if (!dest->member || strcmp(dest->member->name, "__c") != 0)
 442                 return;
 443         dest = dest->deref;
 444         type = get_type(dest);
 445         if (!type)
 446                 return;
 447         val_sym = first_ptr_list((struct ptr_list *)type->symbol_list);
 448         dest = member_expression(dest, '.', val_sym->ident);
 449
 450         assign = assign_expression(dest, '=', data);
 451         __in_fake_assign++;
 452         __split_expr(assign);
 453         __in_fake_assign--;
 454 }
 455
 456 static void match_closure_call(const char *name, struct expression *call,
 457                                void *unused)
 458 {
 459         struct expression *cl, *fn, *fake_call;
 460         struct expression_list *args = NULL;
 461
 462         cl = get_argument_from_call_expr(call->args, 0);
 463         fn = get_argument_from_call_expr(call->args, 1);
 464         if (!fn || !cl)
 465                 return;
 466
 467         add_ptr_list(&args, cl);
 468         fake_call = call_expression(fn, args);
 469         __split_expr(fake_call);
 470 }
 471
 472 static void match_kernel_param(struct symbol *sym)
 473 {
 474         struct expression *var;
 475         struct symbol *type;
 476
 477         /* This was designed to parse the module_param_named() macro */
 478
 479         if (!sym->ident ||
 480             !sym->initializer ||
 481             sym->initializer->type != EXPR_INITIALIZER)
 482                 return;
 483
 484         type = get_real_base_type(sym);
 485         if (!type || type->type != SYM_STRUCT || !type->ident)
 486                 return;
 487         if (strcmp(type->ident->name, "kernel_param") != 0)
 488                 return;
 489
 490         var = last_ptr_list((struct ptr_list *)sym->initializer->expr_list);
 491         if (!var || var->type != EXPR_INITIALIZER)
 492                 return;
 493         var = first_ptr_list((struct ptr_list *)var->expr_list);
 494         if (!var || var->type != EXPR_PREOP || var->op != '&')
 495                 return;
 496         var = strip_expr(var->unop);
 497
 498         type = get_type(var);
 499         update_mtag_data(var, alloc_estate_whole(type));
 500 }
 501
 502 bool is_ignored_kernel_data(const char *name)
 503 {
 504         char *p;
 505
 506         if (option_project != PROJ_KERNEL)
 507                 return false;
 508
 509         /*
 510          * On the file I was looking at lockdep was 25% of the DB.
 511          */
 512         if (strstr(name, ".dep_map."))
 513                 return true;
 514         if (strstr(name, ".lockdep_map."))
 515                 return true;
 516
 517         /* ignore mutex internals */
 518         p = strstr(name, ".rlock.");
 519         if (p) {
 520                 p += 7;
 521                 if (strncmp(p, "raw_lock", 8) == 0 ||
 522                     strcmp(p, "owner") == 0 ||
 523                     strcmp(p, "owner_cpu") == 0 ||
 524                     strcmp(p, "magic") == 0 ||
 525                     strcmp(p, "dep_map") == 0)
 526                         return true;
 527         }
 528
 529         return false;
 530 }
 531
 532 static void match_function_def(struct symbol *sym)
 533 {
 534         char *macro;
 535
 536         macro = get_macro_name(sym->pos);
 537         if (!macro)
 538                 return;
 539         if (strcmp(macro, "TRACE_EVENT") == 0)
 540                 set_function_skipped();
 541 }
 542
 543 void check_kernel(int id)
 544 {
 545         if (option_project != PROJ_KERNEL)
 546                 return;
 547
 548         err_ptr_min = sval_cast(&ptr_ctype, err_ptr_min);
 549         err_ptr_max = sval_cast(&ptr_ctype, err_ptr_max);
 550
 551         add_implied_return_hook("ERR_PTR", &implied_err_cast_return, NULL);
 552         add_implied_return_hook("ERR_CAST", &implied_err_cast_return, NULL);
 553         add_implied_return_hook("PTR_ERR", &implied_err_cast_return, NULL);
 554         add_hook(hack_ERR_PTR, AFTER_DEF_HOOK);
 555         return_implies_state("IS_ERR_OR_NULL", 0, 0, &match_param_valid_ptr, (void *)0);
 556         return_implies_state("IS_ERR_OR_NULL", 1, 1, &match_param_err_or_null, (void *)0);
 557         return_implies_state("IS_ERR", 0, 0, &match_not_err, NULL);
 558         return_implies_state("IS_ERR", 1, 1, &match_err, NULL);
 559         return_implies_state("tomoyo_memory_ok", 1, 1, &match_param_valid_ptr, (void *)0);
 560
 561         add_macro_assign_hook_extra("container_of", &match_container_of_macro, NULL);
 562         add_hook(match_container_of, ASSIGNMENT_HOOK);
 563
 564         add_implied_return_hook("find_next_bit", &match_next_bit, NULL);
 565         add_implied_return_hook("find_next_zero_bit", &match_next_bit, NULL);
 566         add_implied_return_hook("find_first_bit", &match_next_bit, NULL);
 567         add_implied_return_hook("find_first_zero_bit", &match_next_bit, NULL);
 568
 569         add_implied_return_hook("array_size", &match_array_size, NULL);
 570
 571         add_implied_return_hook("__ffs", &match_ffs, NULL);
 572         add_implied_return_hook("fls", &match_fls, NULL);
 573         add_implied_return_hook("fls64", &match_fls, NULL);
 574
 575         add_function_hook("__ftrace_bad_type", &__match_nullify_path_hook, NULL);
 576         add_function_hook("__write_once_size", &match__write_once_size, NULL);
 577
 578         add_function_hook("__read_once_size", &match__read_once_size, NULL);
 579         add_function_hook("__read_once_size_nocheck", &match__read_once_size, NULL);
 580
 581         add_function_hook("closure_call", &match_closure_call, NULL);
 582
 583         add_hook(&match_kernel_param, BASE_HOOK);
 584         add_hook(&match_function_def, FUNC_DEF_HOOK);
 585
 586         if (option_info)
 587                 add_hook(match_end_file, END_FILE_HOOK);
 588 }