tools/objtool/builtin-check.c

   1 /*
   2  * Copyright (C) 2015 Josh Poimboeuf <jpoimboe@redhat.com>
   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/licenses/>.
  16  */
  17
  18 /*
  19  * objtool check:
  20  *
  21  * This command analyzes every .o file and ensures the validity of its stack
  22  * trace metadata.  It enforces a set of rules on asm code and C inline
  23  * assembly code so that stack traces can be reliable.
  24  *
  25  * For more information, see tools/objtool/Documentation/stack-validation.txt.
  26  */
  27
  28 #include <string.h>
  29 #include <subcmd/parse-options.h>
  30
  31 #include "builtin.h"
  32 #include "elf.h"
  33 #include "special.h"
  34 #include "arch.h"
  35 #include "warn.h"
  36
  37 #include <linux/hashtable.h>
  38
  39 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
  40
  41 #define STATE_FP_SAVED          0x1
  42 #define STATE_FP_SETUP          0x2
  43 #define STATE_FENTRY            0x4
  44
  45 struct instruction {
  46         struct list_head list;
  47         struct hlist_node hash;
  48         struct section *sec;
  49         unsigned long offset;
  50         unsigned int len, state;
  51         unsigned char type;
  52         unsigned long immediate;
  53         bool alt_group, visited;
  54         struct symbol *call_dest;
  55         struct instruction *jump_dest;
  56         struct list_head alts;
  57 };
  58
  59 struct alternative {
  60         struct list_head list;
  61         struct instruction *insn;
  62 };
  63
  64 struct objtool_file {
  65         struct elf *elf;
  66         struct list_head insn_list;
  67         DECLARE_HASHTABLE(insn_hash, 16);
  68         struct section *rodata, *whitelist;
  69 };
  70
  71 const char *objname;
  72 static bool nofp;
  73
  74 static struct instruction *find_insn(struct objtool_file *file,
  75                                      struct section *sec, unsigned long offset)
  76 {
  77         struct instruction *insn;
  78
  79         hash_for_each_possible(file->insn_hash, insn, hash, offset)
  80                 if (insn->sec == sec && insn->offset == offset)
  81                         return insn;
  82
  83         return NULL;
  84 }
  85
  86 static struct instruction *next_insn_same_sec(struct objtool_file *file,
  87                                               struct instruction *insn)
  88 {
  89         struct instruction *next = list_next_entry(insn, list);
  90
  91         if (&next->list == &file->insn_list || next->sec != insn->sec)
  92                 return NULL;
  93
  94         return next;
  95 }
  96
  97 #define for_each_insn(file, insn)                                       \
  98         list_for_each_entry(insn, &file->insn_list, list)
  99
 100 #define func_for_each_insn(file, func, insn)                            \
 101         for (insn = find_insn(file, func->sec, func->offset);           \
 102              insn && &insn->list != &file->insn_list &&                 \
 103                 insn->sec == func->sec &&                               \
 104                 insn->offset < func->offset + func->len;                \
 105              insn = list_next_entry(insn, list))
 106
 107 #define sec_for_each_insn_from(file, insn)                              \
 108         for (; insn; insn = next_insn_same_sec(file, insn))
 109
 110
 111 /*
 112  * Check if the function has been manually whitelisted with the
 113  * STACK_FRAME_NON_STANDARD macro, or if it should be automatically whitelisted
 114  * due to its use of a context switching instruction.
 115  */
 116 static bool ignore_func(struct objtool_file *file, struct symbol *func)
 117 {
 118         struct rela *rela;
 119         struct instruction *insn;
 120
 121         /* check for STACK_FRAME_NON_STANDARD */
 122         if (file->whitelist && file->whitelist->rela)
 123                 list_for_each_entry(rela, &file->whitelist->rela->rela_list, list)
 124                         if (rela->sym->sec == func->sec &&
 125                             rela->addend == func->offset)
 126                                 return true;
 127
 128         /* check if it has a context switching instruction */
 129         func_for_each_insn(file, func, insn)
 130                 if (insn->type == INSN_CONTEXT_SWITCH)
 131                         return true;
 132
 133         return false;
 134 }
 135
 136 /*
 137  * This checks to see if the given function is a "noreturn" function.
 138  *
 139  * For global functions which are outside the scope of this object file, we
 140  * have to keep a manual list of them.
 141  *
 142  * For local functions, we have to detect them manually by simply looking for
 143  * the lack of a return instruction.
 144  *
 145  * Returns:
 146  *  -1: error
 147  *   0: no dead end
 148  *   1: dead end
 149  */
 150 static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 151                                int recursion)
 152 {
 153         int i;
 154         struct instruction *insn;
 155         bool empty = true;
 156
 157         /*
 158          * Unfortunately these have to be hard coded because the noreturn
 159          * attribute isn't provided in ELF data.
 160          */
 161         static const char * const global_noreturns[] = {
 162                 "__stack_chk_fail",
 163                 "panic",
 164                 "do_exit",
 165                 "__module_put_and_exit",
 166                 "complete_and_exit",
 167                 "kvm_spurious_fault",
 168                 "__reiserfs_panic",
 169                 "lbug_with_loc"
 170         };
 171
 172         if (func->bind == STB_WEAK)
 173                 return 0;
 174
 175         if (func->bind == STB_GLOBAL)
 176                 for (i = 0; i < ARRAY_SIZE(global_noreturns); i++)
 177                         if (!strcmp(func->name, global_noreturns[i]))
 178                                 return 1;
 179
 180         if (!func->sec)
 181                 return 0;
 182
 183         func_for_each_insn(file, func, insn) {
 184                 empty = false;
 185
 186                 if (insn->type == INSN_RETURN)
 187                         return 0;
 188         }
 189
 190         if (empty)
 191                 return 0;
 192
 193         /*
 194          * A function can have a sibling call instead of a return.  In that
 195          * case, the function's dead-end status depends on whether the target
 196          * of the sibling call returns.
 197          */
 198         func_for_each_insn(file, func, insn) {
 199                 if (insn->sec != func->sec ||
 200                     insn->offset >= func->offset + func->len)
 201                         break;
 202
 203                 if (insn->type == INSN_JUMP_UNCONDITIONAL) {
 204                         struct instruction *dest = insn->jump_dest;
 205                         struct symbol *dest_func;
 206
 207                         if (!dest)
 208                                 /* sibling call to another file */
 209                                 return 0;
 210
 211                         if (dest->sec != func->sec ||
 212                             dest->offset < func->offset ||
 213                             dest->offset >= func->offset + func->len) {
 214                                 /* local sibling call */
 215                                 dest_func = find_symbol_by_offset(dest->sec,
 216                                                                   dest->offset);
 217                                 if (!dest_func)
 218                                         continue;
 219
 220                                 if (recursion == 5) {
 221                                         WARN_FUNC("infinite recursion (objtool bug!)",
 222                                                   dest->sec, dest->offset);
 223                                         return -1;
 224                                 }
 225
 226                                 return __dead_end_function(file, dest_func,
 227                                                            recursion + 1);
 228                         }
 229                 }
 230
 231                 if (insn->type == INSN_JUMP_DYNAMIC)
 232                         /* sibling call */
 233                         return 0;
 234         }
 235
 236         return 1;
 237 }
 238
 239 static int dead_end_function(struct objtool_file *file, struct symbol *func)
 240 {
 241         return __dead_end_function(file, func, 0);
 242 }
 243
 244 /*
 245  * Call the arch-specific instruction decoder for all the instructions and add
 246  * them to the global instruction list.
 247  */
 248 static int decode_instructions(struct objtool_file *file)
 249 {
 250         struct section *sec;
 251         unsigned long offset;
 252         struct instruction *insn;
 253         int ret;
 254
 255         list_for_each_entry(sec, &file->elf->sections, list) {
 256
 257                 if (!(sec->sh.sh_flags & SHF_EXECINSTR))
 258                         continue;
 259
 260                 for (offset = 0; offset < sec->len; offset += insn->len) {
 261                         insn = malloc(sizeof(*insn));
 262                         memset(insn, 0, sizeof(*insn));
 263
 264                         INIT_LIST_HEAD(&insn->alts);
 265                         insn->sec = sec;
 266                         insn->offset = offset;
 267
 268                         ret = arch_decode_instruction(file->elf, sec, offset,
 269                                                       sec->len - offset,
 270                                                       &insn->len, &insn->type,
 271                                                       &insn->immediate);
 272                         if (ret)
 273                                 return ret;
 274
 275                         if (!insn->type || insn->type > INSN_LAST) {
 276                                 WARN_FUNC("invalid instruction type %d",
 277                                           insn->sec, insn->offset, insn->type);
 278                                 return -1;
 279                         }
 280
 281                         hash_add(file->insn_hash, &insn->hash, insn->offset);
 282                         list_add_tail(&insn->list, &file->insn_list);
 283                 }
 284         }
 285
 286         return 0;
 287 }
 288
 289 /*
 290  * Warnings shouldn't be reported for ignored functions.
 291  */
 292 static void add_ignores(struct objtool_file *file)
 293 {
 294         struct instruction *insn;
 295         struct section *sec;
 296         struct symbol *func;
 297
 298         list_for_each_entry(sec, &file->elf->sections, list) {
 299                 list_for_each_entry(func, &sec->symbol_list, list) {
 300                         if (func->type != STT_FUNC)
 301                                 continue;
 302
 303                         if (!ignore_func(file, func))
 304                                 continue;
 305
 306                         func_for_each_insn(file, func, insn)
 307                                 insn->visited = true;
 308                 }
 309         }
 310 }
 311
 312 /*
 313  * Find the destination instructions for all jumps.
 314  */
 315 static int add_jump_destinations(struct objtool_file *file)
 316 {
 317         struct instruction *insn;
 318         struct rela *rela;
 319         struct section *dest_sec;
 320         unsigned long dest_off;
 321
 322         for_each_insn(file, insn) {
 323                 if (insn->type != INSN_JUMP_CONDITIONAL &&
 324                     insn->type != INSN_JUMP_UNCONDITIONAL)
 325                         continue;
 326
 327                 /* skip ignores */
 328                 if (insn->visited)
 329                         continue;
 330
 331                 rela = find_rela_by_dest_range(insn->sec, insn->offset,
 332                                                insn->len);
 333                 if (!rela) {
 334                         dest_sec = insn->sec;
 335                         dest_off = insn->offset + insn->len + insn->immediate;
 336                 } else if (rela->sym->type == STT_SECTION) {
 337                         dest_sec = rela->sym->sec;
 338                         dest_off = rela->addend + 4;
 339                 } else if (rela->sym->sec->idx) {
 340                         dest_sec = rela->sym->sec;
 341                         dest_off = rela->sym->sym.st_value + rela->addend + 4;
 342                 } else {
 343                         /* sibling call */
 344                         insn->jump_dest = 0;
 345                         continue;
 346                 }
 347
 348                 insn->jump_dest = find_insn(file, dest_sec, dest_off);
 349                 if (!insn->jump_dest) {
 350
 351                         /*
 352                          * This is a special case where an alt instruction
 353                          * jumps past the end of the section.  These are
 354                          * handled later in handle_group_alt().
 355                          */
 356                         if (!strcmp(insn->sec->name, ".altinstr_replacement"))
 357                                 continue;
 358
 359                         WARN_FUNC("can't find jump dest instruction at %s+0x%lx",
 360                                   insn->sec, insn->offset, dest_sec->name,
 361                                   dest_off);
 362                         return -1;
 363                 }
 364         }
 365
 366         return 0;
 367 }
 368
 369 /*
 370  * Find the destination instructions for all calls.
 371  */
 372 static int add_call_destinations(struct objtool_file *file)
 373 {
 374         struct instruction *insn;
 375         unsigned long dest_off;
 376         struct rela *rela;
 377
 378         for_each_insn(file, insn) {
 379                 if (insn->type != INSN_CALL)
 380                         continue;
 381
 382                 rela = find_rela_by_dest_range(insn->sec, insn->offset,
 383                                                insn->len);
 384                 if (!rela) {
 385                         dest_off = insn->offset + insn->len + insn->immediate;
 386                         insn->call_dest = find_symbol_by_offset(insn->sec,
 387                                                                 dest_off);
 388                         if (!insn->call_dest) {
 389                                 WARN_FUNC("can't find call dest symbol at offset 0x%lx",
 390                                           insn->sec, insn->offset, dest_off);
 391                                 return -1;
 392                         }
 393                 } else if (rela->sym->type == STT_SECTION) {
 394                         insn->call_dest = find_symbol_by_offset(rela->sym->sec,
 395                                                                 rela->addend+4);
 396                         if (!insn->call_dest ||
 397                             insn->call_dest->type != STT_FUNC) {
 398                                 WARN_FUNC("can't find call dest symbol at %s+0x%x",
 399                                           insn->sec, insn->offset,
 400                                           rela->sym->sec->name,
 401                                           rela->addend + 4);
 402                                 return -1;
 403                         }
 404                 } else
 405                         insn->call_dest = rela->sym;
 406         }
 407
 408         return 0;
 409 }
 410
 411 /*
 412  * The .alternatives section requires some extra special care, over and above
 413  * what other special sections require:
 414  *
 415  * 1. Because alternatives are patched in-place, we need to insert a fake jump
 416  *    instruction at the end so that validate_branch() skips all the original
 417  *    replaced instructions when validating the new instruction path.
 418  *
 419  * 2. An added wrinkle is that the new instruction length might be zero.  In
 420  *    that case the old instructions are replaced with noops.  We simulate that
 421  *    by creating a fake jump as the only new instruction.
 422  *
 423  * 3. In some cases, the alternative section includes an instruction which
 424  *    conditionally jumps to the _end_ of the entry.  We have to modify these
 425  *    jumps' destinations to point back to .text rather than the end of the
 426  *    entry in .altinstr_replacement.
 427  *
 428  * 4. It has been requested that we don't validate the !POPCNT feature path
 429  *    which is a "very very small percentage of machines".
 430  */
 431 static int handle_group_alt(struct objtool_file *file,
 432                             struct special_alt *special_alt,
 433                             struct instruction *orig_insn,
 434                             struct instruction **new_insn)
 435 {
 436         struct instruction *last_orig_insn, *last_new_insn, *insn, *fake_jump;
 437         unsigned long dest_off;
 438
 439         last_orig_insn = NULL;
 440         insn = orig_insn;
 441         sec_for_each_insn_from(file, insn) {
 442                 if (insn->offset >= special_alt->orig_off + special_alt->orig_len)
 443                         break;
 444
 445                 if (special_alt->skip_orig)
 446                         insn->type = INSN_NOP;
 447
 448                 insn->alt_group = true;
 449                 last_orig_insn = insn;
 450         }
 451
 452         if (!next_insn_same_sec(file, last_orig_insn)) {
 453                 WARN("%s: don't know how to handle alternatives at end of section",
 454                      special_alt->orig_sec->name);
 455                 return -1;
 456         }
 457
 458         fake_jump = malloc(sizeof(*fake_jump));
 459         if (!fake_jump) {
 460                 WARN("malloc failed");
 461                 return -1;
 462         }
 463         memset(fake_jump, 0, sizeof(*fake_jump));
 464         INIT_LIST_HEAD(&fake_jump->alts);
 465         fake_jump->sec = special_alt->new_sec;
 466         fake_jump->offset = -1;
 467         fake_jump->type = INSN_JUMP_UNCONDITIONAL;
 468         fake_jump->jump_dest = list_next_entry(last_orig_insn, list);
 469
 470         if (!special_alt->new_len) {
 471                 *new_insn = fake_jump;
 472                 return 0;
 473         }
 474
 475         last_new_insn = NULL;
 476         insn = *new_insn;
 477         sec_for_each_insn_from(file, insn) {
 478                 if (insn->offset >= special_alt->new_off + special_alt->new_len)
 479                         break;
 480
 481                 last_new_insn = insn;
 482
 483                 if (insn->type != INSN_JUMP_CONDITIONAL &&
 484                     insn->type != INSN_JUMP_UNCONDITIONAL)
 485                         continue;
 486
 487                 if (!insn->immediate)
 488                         continue;
 489
 490                 dest_off = insn->offset + insn->len + insn->immediate;
 491                 if (dest_off == special_alt->new_off + special_alt->new_len)
 492                         insn->jump_dest = fake_jump;
 493
 494                 if (!insn->jump_dest) {
 495                         WARN_FUNC("can't find alternative jump destination",
 496                                   insn->sec, insn->offset);
 497                         return -1;
 498                 }
 499         }
 500
 501         if (!last_new_insn) {
 502                 WARN_FUNC("can't find last new alternative instruction",
 503                           special_alt->new_sec, special_alt->new_off);
 504                 return -1;
 505         }
 506
 507         list_add(&fake_jump->list, &last_new_insn->list);
 508
 509         return 0;
 510 }
 511
 512 /*
 513  * A jump table entry can either convert a nop to a jump or a jump to a nop.
 514  * If the original instruction is a jump, make the alt entry an effective nop
 515  * by just skipping the original instruction.
 516  */
 517 static int handle_jump_alt(struct objtool_file *file,
 518                            struct special_alt *special_alt,
 519                            struct instruction *orig_insn,
 520                            struct instruction **new_insn)
 521 {
 522         if (orig_insn->type == INSN_NOP)
 523                 return 0;
 524
 525         if (orig_insn->type != INSN_JUMP_UNCONDITIONAL) {
 526                 WARN_FUNC("unsupported instruction at jump label",
 527                           orig_insn->sec, orig_insn->offset);
 528                 return -1;
 529         }
 530
 531         *new_insn = list_next_entry(orig_insn, list);
 532         return 0;
 533 }
 534
 535 /*
 536  * Read all the special sections which have alternate instructions which can be
 537  * patched in or redirected to at runtime.  Each instruction having alternate
 538  * instruction(s) has them added to its insn->alts list, which will be
 539  * traversed in validate_branch().
 540  */
 541 static int add_special_section_alts(struct objtool_file *file)
 542 {
 543         struct list_head special_alts;
 544         struct instruction *orig_insn, *new_insn;
 545         struct special_alt *special_alt, *tmp;
 546         struct alternative *alt;
 547         int ret;
 548
 549         ret = special_get_alts(file->elf, &special_alts);
 550         if (ret)
 551                 return ret;
 552
 553         list_for_each_entry_safe(special_alt, tmp, &special_alts, list) {
 554                 alt = malloc(sizeof(*alt));
 555                 if (!alt) {
 556                         WARN("malloc failed");
 557                         ret = -1;
 558                         goto out;
 559                 }
 560
 561                 orig_insn = find_insn(file, special_alt->orig_sec,
 562                                       special_alt->orig_off);
 563                 if (!orig_insn) {
 564                         WARN_FUNC("special: can't find orig instruction",
 565                                   special_alt->orig_sec, special_alt->orig_off);
 566                         ret = -1;
 567                         goto out;
 568                 }
 569
 570                 new_insn = NULL;
 571                 if (!special_alt->group || special_alt->new_len) {
 572                         new_insn = find_insn(file, special_alt->new_sec,
 573                                              special_alt->new_off);
 574                         if (!new_insn) {
 575                                 WARN_FUNC("special: can't find new instruction",
 576                                           special_alt->new_sec,
 577                                           special_alt->new_off);
 578                                 ret = -1;
 579                                 goto out;
 580                         }
 581                 }
 582
 583                 if (special_alt->group) {
 584                         ret = handle_group_alt(file, special_alt, orig_insn,
 585                                                &new_insn);
 586                         if (ret)
 587                                 goto out;
 588                 } else if (special_alt->jump_or_nop) {
 589                         ret = handle_jump_alt(file, special_alt, orig_insn,
 590                                               &new_insn);
 591                         if (ret)
 592                                 goto out;
 593                 }
 594
 595                 alt->insn = new_insn;
 596                 list_add_tail(&alt->list, &orig_insn->alts);
 597
 598                 list_del(&special_alt->list);
 599                 free(special_alt);
 600         }
 601
 602 out:
 603         return ret;
 604 }
 605
 606 static int add_switch_table(struct objtool_file *file, struct symbol *func,
 607                             struct instruction *insn, struct rela *table,
 608                             struct rela *next_table)
 609 {
 610         struct rela *rela = table;
 611         struct instruction *alt_insn;
 612         struct alternative *alt;
 613
 614         list_for_each_entry_from(rela, &file->rodata->rela->rela_list, list) {
 615                 if (rela == next_table)
 616                         break;
 617
 618                 if (rela->sym->sec != insn->sec ||
 619                     rela->addend <= func->offset ||
 620                     rela->addend >= func->offset + func->len)
 621                         break;
 622
 623                 alt_insn = find_insn(file, insn->sec, rela->addend);
 624                 if (!alt_insn) {
 625                         WARN("%s: can't find instruction at %s+0x%x",
 626                              file->rodata->rela->name, insn->sec->name,
 627                              rela->addend);
 628                         return -1;
 629                 }
 630
 631                 alt = malloc(sizeof(*alt));
 632                 if (!alt) {
 633                         WARN("malloc failed");
 634                         return -1;
 635                 }
 636
 637                 alt->insn = alt_insn;
 638                 list_add_tail(&alt->list, &insn->alts);
 639         }
 640
 641         return 0;
 642 }
 643
 644 static int add_func_switch_tables(struct objtool_file *file,
 645                                   struct symbol *func)
 646 {
 647         struct instruction *insn, *prev_jump;
 648         struct rela *text_rela, *rodata_rela, *prev_rela;
 649         int ret;
 650
 651         prev_jump = NULL;
 652
 653         func_for_each_insn(file, func, insn) {
 654                 if (insn->type != INSN_JUMP_DYNAMIC)
 655                         continue;
 656
 657                 text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
 658                                                     insn->len);
 659                 if (!text_rela || text_rela->sym != file->rodata->sym)
 660                         continue;
 661
 662                 /* common case: jmpq *[addr](,%rax,8) */
 663                 rodata_rela = find_rela_by_dest(file->rodata,
 664                                                 text_rela->addend);
 665
 666                 /*
 667                  * TODO: Document where this is needed, or get rid of it.
 668                  *
 669                  * rare case:   jmpq *[addr](%rip)
 670                  */
 671                 if (!rodata_rela)
 672                         rodata_rela = find_rela_by_dest(file->rodata,
 673                                                         text_rela->addend + 4);
 674
 675                 if (!rodata_rela)
 676                         continue;
 677
 678                 /*
 679                  * We found a switch table, but we don't know yet how big it
 680                  * is.  Don't add it until we reach the end of the function or
 681                  * the beginning of another switch table in the same function.
 682                  */
 683                 if (prev_jump) {
 684                         ret = add_switch_table(file, func, prev_jump, prev_rela,
 685                                                rodata_rela);
 686                         if (ret)
 687                                 return ret;
 688                 }
 689
 690                 prev_jump = insn;
 691                 prev_rela = rodata_rela;
 692         }
 693
 694         if (prev_jump) {
 695                 ret = add_switch_table(file, func, prev_jump, prev_rela, NULL);
 696                 if (ret)
 697                         return ret;
 698         }
 699
 700         return 0;
 701 }
 702
 703 /*
 704  * For some switch statements, gcc generates a jump table in the .rodata
 705  * section which contains a list of addresses within the function to jump to.
 706  * This finds these jump tables and adds them to the insn->alts lists.
 707  */
 708 static int add_switch_table_alts(struct objtool_file *file)
 709 {
 710         struct section *sec;
 711         struct symbol *func;
 712         int ret;
 713
 714         if (!file->rodata || !file->rodata->rela)
 715                 return 0;
 716
 717         list_for_each_entry(sec, &file->elf->sections, list) {
 718                 list_for_each_entry(func, &sec->symbol_list, list) {
 719                         if (func->type != STT_FUNC)
 720                                 continue;
 721
 722                         ret = add_func_switch_tables(file, func);
 723                         if (ret)
 724                                 return ret;
 725                 }
 726         }
 727
 728         return 0;
 729 }
 730
 731 static int decode_sections(struct objtool_file *file)
 732 {
 733         int ret;
 734
 735         file->whitelist = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
 736         file->rodata = find_section_by_name(file->elf, ".rodata");
 737
 738         ret = decode_instructions(file);
 739         if (ret)
 740                 return ret;
 741
 742         add_ignores(file);
 743
 744         ret = add_jump_destinations(file);
 745         if (ret)
 746                 return ret;
 747
 748         ret = add_call_destinations(file);
 749         if (ret)
 750                 return ret;
 751
 752         ret = add_special_section_alts(file);
 753         if (ret)
 754                 return ret;
 755
 756         ret = add_switch_table_alts(file);
 757         if (ret)
 758                 return ret;
 759
 760         return 0;
 761 }
 762
 763 static bool is_fentry_call(struct instruction *insn)
 764 {
 765         if (insn->type == INSN_CALL &&
 766             insn->call_dest->type == STT_NOTYPE &&
 767             !strcmp(insn->call_dest->name, "__fentry__"))
 768                 return true;
 769
 770         return false;
 771 }
 772
 773 static bool has_modified_stack_frame(struct instruction *insn)
 774 {
 775         return (insn->state & STATE_FP_SAVED) ||
 776                (insn->state & STATE_FP_SETUP);
 777 }
 778
 779 static bool has_valid_stack_frame(struct instruction *insn)
 780 {
 781         return (insn->state & STATE_FP_SAVED) &&
 782                (insn->state & STATE_FP_SETUP);
 783 }
 784
 785 static unsigned int frame_state(unsigned long state)
 786 {
 787         return (state & (STATE_FP_SAVED | STATE_FP_SETUP));
 788 }
 789
 790 /*
 791  * Follow the branch starting at the given instruction, and recursively follow
 792  * any other branches (jumps).  Meanwhile, track the frame pointer state at
 793  * each instruction and validate all the rules described in
 794  * tools/objtool/Documentation/stack-validation.txt.
 795  */
 796 static int validate_branch(struct objtool_file *file,
 797                            struct instruction *first, unsigned char first_state)
 798 {
 799         struct alternative *alt;
 800         struct instruction *insn;
 801         struct section *sec;
 802         unsigned char state;
 803         int ret;
 804
 805         insn = first;
 806         sec = insn->sec;
 807         state = first_state;
 808
 809         if (insn->alt_group && list_empty(&insn->alts)) {
 810                 WARN_FUNC("don't know how to handle branch to middle of alternative instruction group",
 811                           sec, insn->offset);
 812                 return 1;
 813         }
 814
 815         while (1) {
 816                 if (insn->visited) {
 817                         if (frame_state(insn->state) != frame_state(state)) {
 818                                 WARN_FUNC("frame pointer state mismatch",
 819                                           sec, insn->offset);
 820                                 return 1;
 821                         }
 822
 823                         return 0;
 824                 }
 825
 826                 /*
 827                  * Catch a rare case where a noreturn function falls through to
 828                  * the next function.
 829                  */
 830                 if (is_fentry_call(insn) && (state & STATE_FENTRY))
 831                         return 0;
 832
 833                 insn->visited = true;
 834                 insn->state = state;
 835
 836                 list_for_each_entry(alt, &insn->alts, list) {
 837                         ret = validate_branch(file, alt->insn, state);
 838                         if (ret)
 839                                 return 1;
 840                 }
 841
 842                 switch (insn->type) {
 843
 844                 case INSN_FP_SAVE:
 845                         if (!nofp) {
 846                                 if (state & STATE_FP_SAVED) {
 847                                         WARN_FUNC("duplicate frame pointer save",
 848                                                   sec, insn->offset);
 849                                         return 1;
 850                                 }
 851                                 state |= STATE_FP_SAVED;
 852                         }
 853                         break;
 854
 855                 case INSN_FP_SETUP:
 856                         if (!nofp) {
 857                                 if (state & STATE_FP_SETUP) {
 858                                         WARN_FUNC("duplicate frame pointer setup",
 859                                                   sec, insn->offset);
 860                                         return 1;
 861                                 }
 862                                 state |= STATE_FP_SETUP;
 863                         }
 864                         break;
 865
 866                 case INSN_FP_RESTORE:
 867                         if (!nofp) {
 868                                 if (has_valid_stack_frame(insn))
 869                                         state &= ~STATE_FP_SETUP;
 870
 871                                 state &= ~STATE_FP_SAVED;
 872                         }
 873                         break;
 874
 875                 case INSN_RETURN:
 876                         if (!nofp && has_modified_stack_frame(insn)) {
 877                                 WARN_FUNC("return without frame pointer restore",
 878                                           sec, insn->offset);
 879                                 return 1;
 880                         }
 881                         return 0;
 882
 883                 case INSN_CALL:
 884                         if (is_fentry_call(insn)) {
 885                                 state |= STATE_FENTRY;
 886                                 break;
 887                         }
 888
 889                         ret = dead_end_function(file, insn->call_dest);
 890                         if (ret == 1)
 891                                 return 0;
 892                         if (ret == -1)
 893                                 return 1;
 894
 895                         /* fallthrough */
 896                 case INSN_CALL_DYNAMIC:
 897                         if (!nofp && !has_valid_stack_frame(insn)) {
 898                                 WARN_FUNC("call without frame pointer save/setup",
 899                                           sec, insn->offset);
 900                                 return 1;
 901                         }
 902                         break;
 903
 904                 case INSN_JUMP_CONDITIONAL:
 905                 case INSN_JUMP_UNCONDITIONAL:
 906                         if (insn->jump_dest) {
 907                                 ret = validate_branch(file, insn->jump_dest,
 908                                                       state);
 909                                 if (ret)
 910                                         return 1;
 911                         } else if (has_modified_stack_frame(insn)) {
 912                                 WARN_FUNC("sibling call from callable instruction with changed frame pointer",
 913                                           sec, insn->offset);
 914                                 return 1;
 915                         } /* else it's a sibling call */
 916
 917                         if (insn->type == INSN_JUMP_UNCONDITIONAL)
 918                                 return 0;
 919
 920                         break;
 921
 922                 case INSN_JUMP_DYNAMIC:
 923                         if (list_empty(&insn->alts) &&
 924                             has_modified_stack_frame(insn)) {
 925                                 WARN_FUNC("sibling call from callable instruction with changed frame pointer",
 926                                           sec, insn->offset);
 927                                 return 1;
 928                         }
 929
 930                         return 0;
 931
 932                 case INSN_BUG:
 933                         return 0;
 934
 935                 default:
 936                         break;
 937                 }
 938
 939                 insn = next_insn_same_sec(file, insn);
 940                 if (!insn) {
 941                         WARN("%s: unexpected end of section", sec->name);
 942                         return 1;
 943                 }
 944         }
 945
 946         return 0;
 947 }
 948
 949 static bool is_gcov_insn(struct instruction *insn)
 950 {
 951         struct rela *rela;
 952         struct section *sec;
 953         struct symbol *sym;
 954         unsigned long offset;
 955
 956         rela = find_rela_by_dest_range(insn->sec, insn->offset, insn->len);
 957         if (!rela)
 958                 return false;
 959
 960         if (rela->sym->type != STT_SECTION)
 961                 return false;
 962
 963         sec = rela->sym->sec;
 964         offset = rela->addend + insn->offset + insn->len - rela->offset;
 965
 966         list_for_each_entry(sym, &sec->symbol_list, list) {
 967                 if (sym->type != STT_OBJECT)
 968                         continue;
 969
 970                 if (offset >= sym->offset && offset < sym->offset + sym->len)
 971                         return (!memcmp(sym->name, "__gcov0.", 8));
 972         }
 973
 974         return false;
 975 }
 976
 977 static bool is_kasan_insn(struct instruction *insn)
 978 {
 979         return (insn->type == INSN_CALL &&
 980                 !strcmp(insn->call_dest->name, "__asan_handle_no_return"));
 981 }
 982
 983 static bool is_ubsan_insn(struct instruction *insn)
 984 {
 985         return (insn->type == INSN_CALL &&
 986                 !strcmp(insn->call_dest->name,
 987                         "__ubsan_handle_builtin_unreachable"));
 988 }
 989
 990 static bool ignore_unreachable_insn(struct symbol *func,
 991                                     struct instruction *insn)
 992 {
 993         int i;
 994
 995         if (insn->type == INSN_NOP)
 996                 return true;
 997
 998         if (is_gcov_insn(insn))
 999                 return true;
1000
1001         /*
1002          * Check if this (or a subsequent) instruction is related to
1003          * CONFIG_UBSAN or CONFIG_KASAN.
1004          *
1005          * End the search at 5 instructions to avoid going into the weeds.
1006          */
1007         for (i = 0; i < 5; i++) {
1008
1009                 if (is_kasan_insn(insn) || is_ubsan_insn(insn))
1010                         return true;
1011
1012                 if (insn->type == INSN_JUMP_UNCONDITIONAL && insn->jump_dest) {
1013                         insn = insn->jump_dest;
1014                         continue;
1015                 }
1016
1017                 if (insn->offset + insn->len >= func->offset + func->len)
1018                         break;
1019                 insn = list_next_entry(insn, list);
1020         }
1021
1022         return false;
1023 }
1024
1025 static int validate_functions(struct objtool_file *file)
1026 {
1027         struct section *sec;
1028         struct symbol *func;
1029         struct instruction *insn;
1030         int ret, warnings = 0;
1031
1032         list_for_each_entry(sec, &file->elf->sections, list) {
1033                 list_for_each_entry(func, &sec->symbol_list, list) {
1034                         if (func->type != STT_FUNC)
1035                                 continue;
1036
1037                         insn = find_insn(file, sec, func->offset);
1038                         if (!insn) {
1039                                 WARN("%s(): can't find starting instruction",
1040                                      func->name);
1041                                 warnings++;
1042                                 continue;
1043                         }
1044
1045                         ret = validate_branch(file, insn, 0);
1046                         warnings += ret;
1047                 }
1048         }
1049
1050         list_for_each_entry(sec, &file->elf->sections, list) {
1051                 list_for_each_entry(func, &sec->symbol_list, list) {
1052                         if (func->type != STT_FUNC)
1053                                 continue;
1054
1055                         func_for_each_insn(file, func, insn) {
1056                                 if (insn->visited)
1057                                         continue;
1058
1059                                 if (!ignore_unreachable_insn(func, insn) &&
1060                                     !warnings) {
1061                                         WARN_FUNC("function has unreachable instruction", insn->sec, insn->offset);
1062                                         warnings++;
1063                                 }
1064
1065                                 insn->visited = true;
1066                         }
1067                 }
1068         }
1069
1070         return warnings;
1071 }
1072
1073 static int validate_uncallable_instructions(struct objtool_file *file)
1074 {
1075         struct instruction *insn;
1076         int warnings = 0;
1077
1078         for_each_insn(file, insn) {
1079                 if (!insn->visited && insn->type == INSN_RETURN) {
1080                         WARN_FUNC("return instruction outside of a callable function",
1081                                   insn->sec, insn->offset);
1082                         warnings++;
1083                 }
1084         }
1085
1086         return warnings;
1087 }
1088
1089 static void cleanup(struct objtool_file *file)
1090 {
1091         struct instruction *insn, *tmpinsn;
1092         struct alternative *alt, *tmpalt;
1093
1094         list_for_each_entry_safe(insn, tmpinsn, &file->insn_list, list) {
1095                 list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
1096                         list_del(&alt->list);
1097                         free(alt);
1098                 }
1099                 list_del(&insn->list);
1100                 hash_del(&insn->hash);
1101                 free(insn);
1102         }
1103         elf_close(file->elf);
1104 }
1105
1106 const char * const check_usage[] = {
1107         "objtool check [<options>] file.o",
1108         NULL,
1109 };
1110
1111 int cmd_check(int argc, const char **argv)
1112 {
1113         struct objtool_file file;
1114         int ret, warnings = 0;
1115
1116         const struct option options[] = {
1117                 OPT_BOOLEAN('f', "no-fp", &nofp, "Skip frame pointer validation"),
1118                 OPT_END(),
1119         };
1120
1121         argc = parse_options(argc, argv, options, check_usage, 0);
1122
1123         if (argc != 1)
1124                 usage_with_options(check_usage, options);
1125
1126         objname = argv[0];
1127
1128         file.elf = elf_open(objname);
1129         if (!file.elf) {
1130                 fprintf(stderr, "error reading elf file %s\n", objname);
1131                 return 1;
1132         }
1133
1134         INIT_LIST_HEAD(&file.insn_list);
1135         hash_init(file.insn_hash);
1136
1137         ret = decode_sections(&file);
1138         if (ret < 0)
1139                 goto out;
1140         warnings += ret;
1141
1142         ret = validate_functions(&file);
1143         if (ret < 0)
1144                 goto out;
1145         warnings += ret;
1146
1147         ret = validate_uncallable_instructions(&file);
1148         if (ret < 0)
1149                 goto out;
1150         warnings += ret;
1151
1152 out:
1153         cleanup(&file);
1154
1155         /* ignore warnings for now until we get all the code cleaned up */
1156         if (ret || warnings)
1157                 return 0;
1158         return 0;
1159 }