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 int implied_err_cast_return(struct expression *call, void *unused, struct range_list **rl)
  27 {
  28         struct expression *arg;
  29
  30         arg = get_argument_from_call_expr(call->args, 0);
  31         if (!get_implied_rl(arg, rl))
  32                 *rl = alloc_rl(ptr_err_min, ptr_err_max);
  33
  34         *rl = cast_rl(get_type(call), *rl);
  35         return !!*rl;
  36 }
  37
  38 static void hack_ERR_PTR(struct symbol *sym)
  39 {
  40         struct symbol *arg;
  41         struct smatch_state *estate;
  42         struct range_list *after;
  43         sval_t low_error = {
  44                 .type = &long_ctype,
  45                 .value = -4095,
  46         };
  47         sval_t minus_one = {
  48                 .type = &long_ctype,
  49                 .value = -1,
  50         };
  51         sval_t zero = {
  52                 .type = &long_ctype,
  53                 .value = 0,
  54         };
  55
  56         if (!sym || !sym->ident)
  57                 return;
  58         if (strcmp(sym->ident->name, "ERR_PTR") != 0)
  59                 return;
  60
  61         arg = first_ptr_list((struct ptr_list *)sym->ctype.base_type->arguments);
  62         if (!arg || !arg->ident)
  63                 return;
  64
  65         estate = get_state(SMATCH_EXTRA, arg->ident->name, arg);
  66         if (!estate) {
  67                 after = alloc_rl(low_error, minus_one);
  68         } else {
  69                 after = rl_intersection(estate_rl(estate), alloc_rl(low_error, zero));
  70                 if (rl_equiv(estate_rl(estate), after))
  71                         return;
  72         }
  73         set_state(SMATCH_EXTRA, arg->ident->name, arg, alloc_estate_rl(after));
  74 }
  75
  76 static void match_param_valid_ptr(const char *fn, struct expression *call_expr,
  77                         struct expression *assign_expr, void *_param)
  78 {
  79         int param = PTR_INT(_param);
  80         struct expression *arg;
  81         struct smatch_state *pre_state;
  82         struct smatch_state *end_state;
  83         struct range_list *rl;
  84
  85         arg = get_argument_from_call_expr(call_expr->args, param);
  86         pre_state = get_state_expr(SMATCH_EXTRA, arg);
  87         if (estate_rl(pre_state)) {
  88                 rl = estate_rl(pre_state);
  89                 rl = remove_range(rl, ptr_null, ptr_null);
  90                 rl = remove_range(rl, ptr_err_min, ptr_err_max);
  91         } else {
  92                 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
  93         }
  94         end_state = alloc_estate_rl(rl);
  95         set_extra_expr_nomod(arg, end_state);
  96 }
  97
  98 static void match_param_err_or_null(const char *fn, struct expression *call_expr,
  99                         struct expression *assign_expr, void *_param)
 100 {
 101         int param = PTR_INT(_param);
 102         struct expression *arg;
 103         struct range_list *pre, *rl;
 104         struct smatch_state *pre_state;
 105         struct smatch_state *end_state;
 106
 107         arg = get_argument_from_call_expr(call_expr->args, param);
 108         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 109         if (pre_state)
 110                 pre = estate_rl(pre_state);
 111         else
 112                 pre = alloc_whole_rl(&ptr_ctype);
 113         call_results_to_rl(call_expr, &ptr_ctype, "0,(-4095)-(-1)", &rl);
 114         rl = rl_intersection(pre, rl);
 115         rl = cast_rl(get_type(arg), rl);
 116         end_state = alloc_estate_rl(rl);
 117         set_extra_expr_nomod(arg, end_state);
 118 }
 119
 120 static void match_not_err(const char *fn, struct expression *call_expr,
 121                         struct expression *assign_expr, void *unused)
 122 {
 123         struct expression *arg;
 124         struct smatch_state *pre_state;
 125         struct range_list *rl;
 126
 127         arg = get_argument_from_call_expr(call_expr->args, 0);
 128         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 129         if (pre_state) {
 130                 rl = estate_rl(pre_state);
 131                 rl = remove_range(rl, ptr_err_min, ptr_err_max);
 132         } else {
 133                 rl = alloc_rl(valid_ptr_min_sval, valid_ptr_max_sval);
 134         }
 135         rl = cast_rl(get_type(arg), rl);
 136         /* These are implied.  But implications don't work for empty states. */
 137         if (pre_state && rl)
 138                 return;
 139         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 140 }
 141
 142 static void match_err(const char *fn, struct expression *call_expr,
 143                         struct expression *assign_expr, void *unused)
 144 {
 145         struct expression *arg;
 146         struct smatch_state *pre_state;
 147         struct range_list *rl;
 148
 149         arg = get_argument_from_call_expr(call_expr->args, 0);
 150         pre_state = get_state_expr(SMATCH_EXTRA, arg);
 151         rl = estate_rl(pre_state);
 152         if (!rl)
 153                 rl = alloc_rl(ptr_err_min, ptr_err_max);
 154         rl = rl_intersection(rl, alloc_rl(ptr_err_min, ptr_err_max));
 155         rl = cast_rl(get_type(arg), rl);
 156         if (pre_state && rl) {
 157                 /*
 158                  * Ideally this would all be handled by smatch_implied.c
 159                  * but it doesn't work very well for impossible paths.
 160                  *
 161                  */
 162                 return;
 163         }
 164         set_extra_expr_nomod(arg, alloc_estate_rl(rl));
 165 }
 166
 167 static void match_container_of_macro(const char *fn, struct expression *expr, void *unused)
 168 {
 169         set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 170 }
 171
 172 static void match_container_of(struct expression *expr)
 173 {
 174         struct expression *right = expr->right;
 175         char *macro;
 176
 177         /*
 178          * The problem here is that sometimes the container_of() macro is itself
 179          * inside a macro and get_macro() only returns the name of the outside
 180          * macro.
 181          */
 182
 183         /*
 184          * This actually an expression statement assignment but smatch_flow
 185          * pre-mangles it for us so we only get the last chunk:
 186          * sk = (typeof(sk))((char *)__mptr - offsetof(...))
 187          */
 188
 189         macro = get_macro_name(right->pos);
 190         if (!macro)
 191                 return;
 192         if (right->type != EXPR_CAST)
 193                 return;
 194         right = strip_expr(right);
 195         if (right->type != EXPR_BINOP || right->op != '-' ||
 196             right->left->type != EXPR_CAST)
 197                 return;
 198         right = strip_expr(right->left);
 199         if (right->type != EXPR_SYMBOL)
 200                 return;
 201         if (!right->symbol->ident ||
 202             strcmp(right->symbol->ident->name, "__mptr") != 0)
 203                 return;
 204         set_extra_expr_mod(expr->left, alloc_estate_range(valid_ptr_min_sval, valid_ptr_max_sval));
 205 }
 206
 207 static int match_next_bit(struct expression *call, void *unused, struct range_list **rl)
 208 {
 209         struct expression *start_arg;
 210         struct expression *size_arg;
 211         struct symbol *type;
 212         sval_t min, max, tmp;
 213
 214         size_arg = get_argument_from_call_expr(call->args, 1);
 215         /* btw. there isn't a start_arg for find_first_bit() */
 216         start_arg = get_argument_from_call_expr(call->args, 2);
 217
 218         type = get_type(call);
 219         min = sval_type_val(type, 0);
 220         max = sval_type_val(type, sizeof(long long) * 8);
 221
 222         if (get_implied_max(size_arg, &tmp) && tmp.uvalue < max.value)
 223                 max = tmp;
 224         if (start_arg && get_implied_min(start_arg, &tmp) && !sval_is_negative(tmp))
 225                 min = tmp;
 226         if (sval_cmp(min, max) > 0)
 227                 max = min;
 228         min = sval_cast(type, min);
 229         max = sval_cast(type, max);
 230         *rl = alloc_rl(min, max);
 231         return 1;
 232 }
 233
 234 static int match_array_size(struct expression *call, void *unused, struct range_list **rl)
 235 {
 236         struct expression *size;
 237         struct expression *count;
 238         struct expression *mult;
 239         struct range_list *ret;
 240
 241         size = get_argument_from_call_expr(call->args, 0);
 242         count = get_argument_from_call_expr(call->args, 1);
 243         mult = binop_expression(size, '*', count);
 244
 245         if (get_implied_rl(mult, &ret)) {
 246                 *rl = ret;
 247                 return 1;
 248         }
 249
 250         return 0;
 251 }
 252
 253 static int match_ffs(struct expression *call, void *unused, struct range_list **rl)
 254 {
 255         if (get_implied_rl(call, rl))
 256                 return true;
 257         return false;
 258 }
 259
 260 static int match_fls(struct expression *call, void *unused, struct range_list **rl)
 261 {
 262         struct expression *arg;
 263         struct range_list *arg_rl;
 264         sval_t zero = {};
 265         sval_t start = {
 266                 .type = &int_ctype,
 267                 .value = 0,
 268         };
 269         sval_t end = {
 270                 .type = &int_ctype,
 271                 .value = 32,
 272         };
 273         sval_t sval;
 274
 275         arg = get_argument_from_call_expr(call->args, 0);
 276         if (!get_implied_rl(arg, &arg_rl))
 277                 return 0;
 278         if (rl_to_sval(arg_rl, &sval)) {
 279                 int i;
 280
 281                 for (i = 63; i >= 0; i--) {
 282                         if (sval.uvalue & 1ULL << i)
 283                                 break;
 284                 }
 285                 sval.value = i + 1;
 286                 *rl = alloc_rl(sval, sval);
 287                 return 1;
 288         }
 289         zero.type = rl_type(arg_rl);
 290         if (!rl_has_sval(arg_rl, zero))
 291                 start.value = 1;
 292         *rl = alloc_rl(start, end);
 293         return 1;
 294 }
 295
 296 static void find_module_init_exit(struct symbol_list *sym_list)
 297 {
 298         struct symbol *sym;
 299         struct symbol *fn;
 300         struct statement *stmt;
 301         char *name;
 302         int init;
 303         int count;
 304
 305         /*
 306          * This is more complicated because Sparse ignores the "alias"
 307          * attribute.  I search backwards because module_init() is normally at
 308          * the end of the file.
 309          */
 310         count = 0;
 311         FOR_EACH_PTR_REVERSE(sym_list, sym) {
 312                 if (sym->type != SYM_NODE)
 313                         continue;
 314                 if (!(sym->ctype.modifiers & MOD_STATIC))
 315                         continue;
 316                 fn = get_base_type(sym);
 317                 if (!fn)
 318                         continue;
 319                 if (fn->type != SYM_FN)
 320                         continue;
 321                 if (!sym->ident)
 322                         continue;
 323                 if (!fn->inline_stmt)
 324                         continue;
 325                 if (strcmp(sym->ident->name, "__inittest") == 0)
 326                         init = 1;
 327                 else if (strcmp(sym->ident->name, "__exittest") == 0)
 328                         init = 0;
 329                 else
 330                         continue;
 331
 332                 count++;
 333
 334                 stmt = first_ptr_list((struct ptr_list *)fn->inline_stmt->stmts);
 335                 if (!stmt || stmt->type != STMT_RETURN)
 336                         continue;
 337                 name = expr_to_var(stmt->ret_value);
 338                 if (!name)
 339                         continue;
 340                 if (init)
 341                         sql_insert_function_ptr(name, "(struct module)->init");
 342                 else
 343                         sql_insert_function_ptr(name, "(struct module)->exit");
 344                 free_string(name);
 345                 if (count >= 2)
 346                         return;
 347         } END_FOR_EACH_PTR_REVERSE(sym);
 348 }
 349
 350 static void match_end_file(struct symbol_list *sym_list)
 351 {
 352         struct symbol *sym;
 353
 354         /* find the last static symbol in the file */
 355         FOR_EACH_PTR_REVERSE(sym_list, sym) {
 356                 if (!(sym->ctype.modifiers & MOD_STATIC))
 357                         continue;
 358                 if (!sym->scope)
 359                         continue;
 360                 find_module_init_exit(sym->scope->symbols);
 361                 return;
 362         } END_FOR_EACH_PTR_REVERSE(sym);
 363 }
 364
 365 static struct expression *get_val_expr(struct expression *expr)
 366 {
 367         struct symbol *sym, *val;
 368
 369         if (expr->type != EXPR_DEREF)
 370                 return NULL;
 371         expr = expr->deref;
 372         if (expr->type != EXPR_SYMBOL)
 373                 return NULL;
 374         if (strcmp(expr->symbol_name->name, "__u") != 0)
 375                 return NULL;
 376         sym = get_base_type(expr->symbol);
 377         val = first_ptr_list((struct ptr_list *)sym->symbol_list);
 378         if (!val || strcmp(val->ident->name, "__val") != 0)
 379                 return NULL;
 380         return member_expression(expr, '.', val->ident);
 381 }
 382
 383 static void match__write_once_size(const char *fn, struct expression *call,
 384                                void *unused)
 385 {
 386         struct expression *dest, *data, *assign;
 387         struct range_list *rl;
 388
 389         dest = get_argument_from_call_expr(call->args, 0);
 390         if (dest->type != EXPR_PREOP || dest->op != '&')
 391                 return;
 392         dest = strip_expr(dest->unop);
 393
 394         data = get_argument_from_call_expr(call->args, 1);
 395         data = get_val_expr(data);
 396         if (!data)
 397                 return;
 398         get_absolute_rl(data, &rl);
 399         assign = assign_expression(dest, '=', data);
 400
 401         __in_fake_assign++;
 402         __split_expr(assign);
 403         __in_fake_assign--;
 404 }
 405
 406 static void match__read_once_size(const char *fn, struct expression *call,
 407                                void *unused)
 408 {
 409         struct expression *dest, *data, *assign;
 410         struct symbol *type, *val_sym;
 411
 412         /*
 413          * We want to change:
 414          *      __read_once_size_nocheck(&(x), __u.__c, sizeof(x));
 415          * into a fake assignment:
 416          *      __u.val = x;
 417          *
 418          */
 419
 420         data = get_argument_from_call_expr(call->args, 0);
 421         if (data->type != EXPR_PREOP || data->op != '&')
 422                 return;
 423         data = strip_parens(data->unop);
 424
 425         dest = get_argument_from_call_expr(call->args, 1);
 426         if (dest->type != EXPR_DEREF || dest->op != '.')
 427                 return;
 428         if (!dest->member || strcmp(dest->member->name, "__c") != 0)
 429                 return;
 430         dest = dest->deref;
 431         type = get_type(dest);
 432         if (!type)
 433                 return;
 434         val_sym = first_ptr_list((struct ptr_list *)type->symbol_list);
 435         dest = member_expression(dest, '.', val_sym->ident);
 436
 437         assign = assign_expression(dest, '=', data);
 438         __in_fake_assign++;
 439         __split_expr(assign);
 440         __in_fake_assign--;
 441 }
 442
 443 static void match_closure_call(const char *name, struct expression *call,
 444                                void *unused)
 445 {
 446         struct expression *cl, *fn, *fake_call;
 447         struct expression_list *args = NULL;
 448
 449         cl = get_argument_from_call_expr(call->args, 0);
 450         fn = get_argument_from_call_expr(call->args, 1);
 451         if (!fn || !cl)
 452                 return;
 453
 454         add_ptr_list(&args, cl);
 455         fake_call = call_expression(fn, args);
 456         __split_expr(fake_call);
 457 }
 458
 459 static void match_kernel_param(struct symbol *sym)
 460 {
 461         struct expression *var;
 462         struct symbol *type;
 463
 464         /* This was designed to parse the module_param_named() macro */
 465
 466         if (!sym->ident ||
 467             !sym->initializer ||
 468             sym->initializer->type != EXPR_INITIALIZER)
 469                 return;
 470
 471         type = get_real_base_type(sym);
 472         if (!type || type->type != SYM_STRUCT || !type->ident)
 473                 return;
 474         if (strcmp(type->ident->name, "kernel_param") != 0)
 475                 return;
 476
 477         var = last_ptr_list((struct ptr_list *)sym->initializer->expr_list);
 478         if (!var || var->type != EXPR_INITIALIZER)
 479                 return;
 480         var = first_ptr_list((struct ptr_list *)var->expr_list);
 481         if (!var || var->type != EXPR_PREOP || var->op != '&')
 482                 return;
 483         var = strip_expr(var->unop);
 484
 485         type = get_type(var);
 486         update_mtag_data(var, alloc_estate_whole(type));
 487 }
 488
 489 bool is_ignored_kernel_data(const char *name)
 490 {
 491         char *p;
 492
 493         if (option_project != PROJ_KERNEL)
 494                 return false;
 495
 496         /*
 497          * On the file I was looking at lockdep was 25% of the DB.
 498          */
 499         if (strstr(name, ".dep_map."))
 500                 return true;
 501         if (strstr(name, "->dep_map."))
 502                 return true;
 503         if (strstr(name, ".lockdep_map."))
 504                 return true;
 505
 506         if (strstr(name, ".rwsem."))
 507                 return true;
 508         if (strstr(name, "->rwsem."))
 509                 return true;
 510
 511         if (strstr(name, "->mutex."))
 512                 return true;
 513         if (strstr(name, "->lockdep_mutex."))
 514                 return true;
 515
 516         if (strstr(name, ".completion.wait."))
 517                 return true;
 518
 519         if (strstr(name, "kobj.kset-"))
 520                 return true;
 521         if (strstr(name, "power.suspend_timer."))
 522                 return true;
 523         if (strstr(name, "power.work."))
 524                 return true;
 525         if (strstr(name, ".lock.rlock."))
 526                 return true;
 527         if (strstr(name, "lockdep_mutex."))
 528                 return true;
 529
 530         if (strstr(name, ">klist_devices."))
 531                 return true;
 532
 533         if (strstr(name, "->m_log->"))
 534                 return true;
 535
 536         if (strstr(name, ".wait_lock."))
 537                 return true;
 538         if (strstr(name, "regmap->lock_arg"))
 539                 return true;
 540         if (strstr(name, "kworker->task"))
 541                 return true;
 542         if (strstr(name, "->algo_data->"))
 543                 return true;
 544
 545         /* ignore mutex internals */
 546         if ((p = strstr(name, ".rlock.")) ||
 547             (p = strstr(name, ">rlock."))) {
 548                 p += 7;
 549                 if (strncmp(p, "raw_lock", 8) == 0 ||
 550                     strcmp(p, "owner") == 0 ||
 551                     strcmp(p, "owner_cpu") == 0 ||
 552                     strcmp(p, "magic") == 0 ||
 553                     strcmp(p, "dep_map") == 0)
 554                         return true;
 555         }
 556
 557         return false;
 558 }
 559
 560 int get_gfp_param(struct expression *expr)
 561 {
 562         struct symbol *type;
 563         struct symbol *arg, *arg_type;
 564         int param;
 565
 566         if (expr->type != EXPR_CALL)
 567                 return -1;
 568         type = get_type(expr->fn);
 569         if (!type)
 570                 return -1;
 571         if (type->type == SYM_PTR)
 572                 type = get_real_base_type(type);
 573         if (type->type != SYM_FN)
 574                 return -1;
 575
 576         param = 0;
 577         FOR_EACH_PTR(type->arguments, arg) {
 578                 arg_type = get_base_type(arg);
 579                 if (arg_type && arg_type->ident &&
 580                     strcmp(arg_type->ident->name, "gfp_t") == 0)
 581                         return param;
 582                 param++;
 583         } END_FOR_EACH_PTR(arg);
 584
 585         return -1;
 586 }
 587
 588 static void match_function_def(struct symbol *sym)
 589 {
 590         char *macro;
 591
 592         macro = get_macro_name(sym->pos);
 593         if (!macro)
 594                 return;
 595         if (strcmp(macro, "TRACE_EVENT") == 0)
 596                 set_function_skipped();
 597 }
 598
 599 static bool delete_pci_error_returns(struct expression *expr)
 600 {
 601         const char *macro;
 602         sval_t sval;
 603
 604         if (!get_value(expr, &sval))
 605                 return false;
 606         if (sval.value < 0x80 || sval.value > 0x90)
 607                 return false;
 608
 609         macro = get_macro_name(expr->pos);
 610         if (!macro)
 611                 return false;
 612
 613         if (strncmp(macro, "PCIBIOS_", 8) != 0)
 614                 return false;
 615
 616         if (strcmp(macro, "PCIBIOS_FUNC_NOT_SUPPORTED") == 0  ||
 617             strcmp(macro, "PCIBIOS_BAD_VENDOR_ID") == 0       ||
 618             strcmp(macro, "PCIBIOS_DEVICE_NOT_FOUND") == 0    ||
 619             strcmp(macro, "PCIBIOS_BAD_REGISTER_NUMBER") == 0 ||
 620             strcmp(macro, "PCIBIOS_SET_FAILED") == 0          ||
 621             strcmp(macro, "PCIBIOS_BUFFER_TOO_SMALL") == 0)
 622                 return true;
 623
 624         return false;
 625 }
 626
 627 void check_kernel(int id)
 628 {
 629         if (option_project != PROJ_KERNEL)
 630                 return;
 631
 632         add_implied_return_hook("ERR_PTR", &implied_err_cast_return, NULL);
 633         add_implied_return_hook("ERR_CAST", &implied_err_cast_return, NULL);
 634         add_implied_return_hook("PTR_ERR", &implied_err_cast_return, NULL);
 635         add_hook(hack_ERR_PTR, AFTER_DEF_HOOK);
 636         return_implies_state("IS_ERR_OR_NULL", 0, 0, &match_param_valid_ptr, (void *)0);
 637         return_implies_state("IS_ERR_OR_NULL", 1, 1, &match_param_err_or_null, (void *)0);
 638         return_implies_state("IS_ERR", 0, 0, &match_not_err, NULL);
 639         return_implies_state("IS_ERR", 1, 1, &match_err, NULL);
 640         return_implies_state("tomoyo_memory_ok", 1, 1, &match_param_valid_ptr, (void *)0);
 641
 642         add_macro_assign_hook_extra("container_of", &match_container_of_macro, NULL);
 643         add_hook(match_container_of, ASSIGNMENT_HOOK);
 644
 645         add_implied_return_hook("find_next_bit", &match_next_bit, NULL);
 646         add_implied_return_hook("find_next_zero_bit", &match_next_bit, NULL);
 647         add_implied_return_hook("find_first_bit", &match_next_bit, NULL);
 648         add_implied_return_hook("find_first_zero_bit", &match_next_bit, NULL);
 649
 650         add_implied_return_hook("array_size", &match_array_size, NULL);
 651
 652         add_implied_return_hook("__ffs", &match_ffs, NULL);
 653         add_implied_return_hook("fls", &match_fls, NULL);
 654         add_implied_return_hook("__fls", &match_fls, NULL);
 655         add_implied_return_hook("fls64", &match_fls, NULL);
 656
 657         add_function_hook("__ftrace_bad_type", &__match_nullify_path_hook, NULL);
 658         add_function_hook("__write_once_size", &match__write_once_size, NULL);
 659
 660         add_function_hook("__read_once_size", &match__read_once_size, NULL);
 661         add_function_hook("__read_once_size_nocheck", &match__read_once_size, NULL);
 662
 663         add_function_hook("closure_call", &match_closure_call, NULL);
 664
 665         add_hook(&match_kernel_param, BASE_HOOK);
 666         add_hook(&match_function_def, FUNC_DEF_HOOK);
 667
 668         if (option_info)
 669                 add_hook(match_end_file, END_FILE_HOOK);
 670
 671         add_delete_return_hook(&delete_pci_error_returns);
 672 }