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 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
  38
  39 #define STATE_FP_SAVED          0x1
  40 #define STATE_FP_SETUP          0x2
  41 #define STATE_FENTRY            0x4
  42
  43 struct instruction {
  44         struct list_head list;
  45         struct section *sec;
  46         unsigned long offset;
  47         unsigned int len, state;
  48         unsigned char type;
  49         unsigned long immediate;
  50         bool alt_group, visited;
  51         struct symbol *call_dest;
  52         struct instruction *jump_dest;
  53         struct list_head alts;
  54 };
  55
  56 struct alternative {
  57         struct list_head list;
  58         struct instruction *insn;
  59 };
  60
  61 struct objtool_file {
  62         struct elf *elf;
  63         struct list_head insns;
  64 };
  65
  66 const char *objname;
  67 static bool nofp;
  68
  69 static struct instruction *find_instruction(struct objtool_file *file,
  70                                             struct section *sec,
  71                                             unsigned long offset)
  72 {
  73         struct instruction *insn;
  74
  75         list_for_each_entry(insn, &file->insns, list)
  76                 if (insn->sec == sec && insn->offset == offset)
  77                         return insn;
  78
  79         return NULL;
  80 }
  81
  82 /*
  83  * Check if the function has been manually whitelisted with the
  84  * STACK_FRAME_NON_STANDARD macro, or if it should be automatically whitelisted
  85  * due to its use of a context switching instruction.
  86  */
  87 static bool ignore_func(struct objtool_file *file, struct symbol *func)
  88 {
  89         struct section *macro_sec;
  90         struct rela *rela;
  91         struct instruction *insn;
  92
  93         /* check for STACK_FRAME_NON_STANDARD */
  94         macro_sec = find_section_by_name(file->elf, "__func_stack_frame_non_standard");
  95         if (macro_sec && macro_sec->rela)
  96                 list_for_each_entry(rela, &macro_sec->rela->relas, list)
  97                         if (rela->sym->sec == func->sec &&
  98                             rela->addend == func->offset)
  99                                 return true;
 100
 101         /* check if it has a context switching instruction */
 102         insn = find_instruction(file, func->sec, func->offset);
 103         if (!insn)
 104                 return false;
 105         list_for_each_entry_from(insn, &file->insns, list) {
 106                 if (insn->sec != func->sec ||
 107                     insn->offset >= func->offset + func->len)
 108                         break;
 109                 if (insn->type == INSN_CONTEXT_SWITCH)
 110                         return true;
 111         }
 112
 113         return false;
 114 }
 115
 116 /*
 117  * This checks to see if the given function is a "noreturn" function.
 118  *
 119  * For global functions which are outside the scope of this object file, we
 120  * have to keep a manual list of them.
 121  *
 122  * For local functions, we have to detect them manually by simply looking for
 123  * the lack of a return instruction.
 124  *
 125  * Returns:
 126  *  -1: error
 127  *   0: no dead end
 128  *   1: dead end
 129  */
 130 static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 131                                int recursion)
 132 {
 133         int i;
 134         struct instruction *insn, *func_insn;
 135         bool empty = true;
 136
 137         /*
 138          * Unfortunately these have to be hard coded because the noreturn
 139          * attribute isn't provided in ELF data.
 140          */
 141         static const char * const global_noreturns[] = {
 142                 "__stack_chk_fail",
 143                 "panic",
 144                 "do_exit",
 145                 "__module_put_and_exit",
 146                 "complete_and_exit",
 147                 "kvm_spurious_fault",
 148                 "__reiserfs_panic",
 149                 "lbug_with_loc"
 150         };
 151
 152         if (func->bind == STB_WEAK)
 153                 return 0;
 154
 155         if (func->bind == STB_GLOBAL)
 156                 for (i = 0; i < ARRAY_SIZE(global_noreturns); i++)
 157                         if (!strcmp(func->name, global_noreturns[i]))
 158                                 return 1;
 159
 160         if (!func->sec)
 161                 return 0;
 162
 163         func_insn = find_instruction(file, func->sec, func->offset);
 164         if (!func_insn)
 165                 return 0;
 166
 167         insn = func_insn;
 168         list_for_each_entry_from(insn, &file->insns, list) {
 169                 if (insn->sec != func->sec ||
 170                     insn->offset >= func->offset + func->len)
 171                         break;
 172
 173                 empty = false;
 174
 175                 if (insn->type == INSN_RETURN)
 176                         return 0;
 177         }
 178
 179         if (empty)
 180                 return 0;
 181
 182         /*
 183          * A function can have a sibling call instead of a return.  In that
 184          * case, the function's dead-end status depends on whether the target
 185          * of the sibling call returns.
 186          */
 187         insn = func_insn;
 188         list_for_each_entry_from(insn, &file->insns, list) {
 189                 if (insn->sec != func->sec ||
 190                     insn->offset >= func->offset + func->len)
 191                         break;
 192
 193                 if (insn->type == INSN_JUMP_UNCONDITIONAL) {
 194                         struct instruction *dest = insn->jump_dest;
 195                         struct symbol *dest_func;
 196
 197                         if (!dest)
 198                                 /* sibling call to another file */
 199                                 return 0;
 200
 201                         if (dest->sec != func->sec ||
 202                             dest->offset < func->offset ||
 203                             dest->offset >= func->offset + func->len) {
 204                                 /* local sibling call */
 205                                 dest_func = find_symbol_by_offset(dest->sec,
 206                                                                   dest->offset);
 207                                 if (!dest_func)
 208                                         continue;
 209
 210                                 if (recursion == 5) {
 211                                         WARN_FUNC("infinite recursion (objtool bug!)",
 212                                                   dest->sec, dest->offset);
 213                                         return -1;
 214                                 }
 215
 216                                 return __dead_end_function(file, dest_func,
 217                                                            recursion + 1);
 218                         }
 219                 }
 220
 221                 if (insn->type == INSN_JUMP_DYNAMIC)
 222                         /* sibling call */
 223                         return 0;
 224         }
 225
 226         return 1;
 227 }
 228
 229 static int dead_end_function(struct objtool_file *file, struct symbol *func)
 230 {
 231         return __dead_end_function(file, func, 0);
 232 }
 233
 234 /*
 235  * Call the arch-specific instruction decoder for all the instructions and add
 236  * them to the global insns list.
 237  */
 238 static int decode_instructions(struct objtool_file *file)
 239 {
 240         struct section *sec;
 241         unsigned long offset;
 242         struct instruction *insn;
 243         int ret;
 244
 245         INIT_LIST_HEAD(&file->insns);
 246
 247         list_for_each_entry(sec, &file->elf->sections, list) {
 248
 249                 if (!(sec->sh.sh_flags & SHF_EXECINSTR))
 250                         continue;
 251
 252                 for (offset = 0; offset < sec->len; offset += insn->len) {
 253                         insn = malloc(sizeof(*insn));
 254                         memset(insn, 0, sizeof(*insn));
 255
 256                         INIT_LIST_HEAD(&insn->alts);
 257                         insn->sec = sec;
 258                         insn->offset = offset;
 259
 260                         ret = arch_decode_instruction(file->elf, sec, offset,
 261                                                       sec->len - offset,
 262                                                       &insn->len, &insn->type,
 263                                                       &insn->immediate);
 264                         if (ret)
 265                                 return ret;
 266
 267                         if (!insn->type || insn->type > INSN_LAST) {
 268                                 WARN_FUNC("invalid instruction type %d",
 269                                           insn->sec, insn->offset, insn->type);
 270                                 return -1;
 271                         }
 272
 273                         list_add_tail(&insn->list, &file->insns);
 274                 }
 275         }
 276
 277         return 0;
 278 }
 279
 280 /*
 281  * Warnings shouldn't be reported for ignored functions.
 282  */
 283 static void get_ignores(struct objtool_file *file)
 284 {
 285         struct instruction *insn;
 286         struct section *sec;
 287         struct symbol *func;
 288
 289         list_for_each_entry(sec, &file->elf->sections, list) {
 290                 list_for_each_entry(func, &sec->symbols, list) {
 291                         if (func->type != STT_FUNC)
 292                                 continue;
 293
 294                         if (!ignore_func(file, func))
 295                                 continue;
 296
 297                         insn = find_instruction(file, sec, func->offset);
 298                         if (!insn)
 299                                 continue;
 300
 301                         list_for_each_entry_from(insn, &file->insns, list) {
 302                                 if (insn->sec != func->sec ||
 303                                     insn->offset >= func->offset + func->len)
 304                                         break;
 305
 306                                 insn->visited = true;
 307                         }
 308                 }
 309         }
 310 }
 311
 312 /*
 313  * Find the destination instructions for all jumps.
 314  */
 315 static int get_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         list_for_each_entry(insn, &file->insns, list) {
 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_instruction(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 get_call_destinations(struct objtool_file *file)
 373 {
 374         struct instruction *insn;
 375         unsigned long dest_off;
 376         struct rela *rela;
 377
 378         list_for_each_entry(insn, &file->insns, list) {
 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         list_for_each_entry_from(insn, &file->insns, list) {
 442                 if (insn->sec != special_alt->orig_sec ||
 443                     insn->offset >= special_alt->orig_off + special_alt->orig_len)
 444                         break;
 445
 446                 if (special_alt->skip_orig)
 447                         insn->type = INSN_NOP;
 448
 449                 insn->alt_group = true;
 450                 last_orig_insn = insn;
 451         }
 452
 453         if (list_is_last(&last_orig_insn->list, &file->insns) ||
 454             list_next_entry(last_orig_insn, list)->sec != special_alt->orig_sec) {
 455                 WARN("%s: don't know how to handle alternatives at end of section",
 456                      special_alt->orig_sec->name);
 457                 return -1;
 458         }
 459
 460         fake_jump = malloc(sizeof(*fake_jump));
 461         if (!fake_jump) {
 462                 WARN("malloc failed");
 463                 return -1;
 464         }
 465         memset(fake_jump, 0, sizeof(*fake_jump));
 466         INIT_LIST_HEAD(&fake_jump->alts);
 467         fake_jump->sec = special_alt->new_sec;
 468         fake_jump->offset = -1;
 469         fake_jump->type = INSN_JUMP_UNCONDITIONAL;
 470         fake_jump->jump_dest = list_next_entry(last_orig_insn, list);
 471
 472         if (!special_alt->new_len) {
 473                 *new_insn = fake_jump;
 474                 return 0;
 475         }
 476
 477         last_new_insn = NULL;
 478         insn = *new_insn;
 479         list_for_each_entry_from(insn, &file->insns, list) {
 480                 if (insn->sec != special_alt->new_sec ||
 481                     insn->offset >= special_alt->new_off + special_alt->new_len)
 482                         break;
 483
 484                 last_new_insn = insn;
 485
 486                 if (insn->type != INSN_JUMP_CONDITIONAL &&
 487                     insn->type != INSN_JUMP_UNCONDITIONAL)
 488                         continue;
 489
 490                 if (!insn->immediate)
 491                         continue;
 492
 493                 dest_off = insn->offset + insn->len + insn->immediate;
 494                 if (dest_off == special_alt->new_off + special_alt->new_len)
 495                         insn->jump_dest = fake_jump;
 496
 497                 if (!insn->jump_dest) {
 498                         WARN_FUNC("can't find alternative jump destination",
 499                                   insn->sec, insn->offset);
 500                         return -1;
 501                 }
 502         }
 503
 504         if (!last_new_insn) {
 505                 WARN_FUNC("can't find last new alternative instruction",
 506                           special_alt->new_sec, special_alt->new_off);
 507                 return -1;
 508         }
 509
 510         list_add(&fake_jump->list, &last_new_insn->list);
 511
 512         return 0;
 513 }
 514
 515 /*
 516  * A jump table entry can either convert a nop to a jump or a jump to a nop.
 517  * If the original instruction is a jump, make the alt entry an effective nop
 518  * by just skipping the original instruction.
 519  */
 520 static int handle_jump_alt(struct objtool_file *file,
 521                            struct special_alt *special_alt,
 522                            struct instruction *orig_insn,
 523                            struct instruction **new_insn)
 524 {
 525         if (orig_insn->type == INSN_NOP)
 526                 return 0;
 527
 528         if (orig_insn->type != INSN_JUMP_UNCONDITIONAL) {
 529                 WARN_FUNC("unsupported instruction at jump label",
 530                           orig_insn->sec, orig_insn->offset);
 531                 return -1;
 532         }
 533
 534         *new_insn = list_next_entry(orig_insn, list);
 535         return 0;
 536 }
 537
 538 /*
 539  * Read all the special sections which have alternate instructions which can be
 540  * patched in or redirected to at runtime.  Each instruction having alternate
 541  * instruction(s) has them added to its insn->alts list, which will be
 542  * traversed in validate_branch().
 543  */
 544 static int get_special_section_alts(struct objtool_file *file)
 545 {
 546         struct list_head special_alts;
 547         struct instruction *orig_insn, *new_insn;
 548         struct special_alt *special_alt, *tmp;
 549         struct alternative *alt;
 550         int ret;
 551
 552         ret = special_get_alts(file->elf, &special_alts);
 553         if (ret)
 554                 return ret;
 555
 556         list_for_each_entry_safe(special_alt, tmp, &special_alts, list) {
 557                 alt = malloc(sizeof(*alt));
 558                 if (!alt) {
 559                         WARN("malloc failed");
 560                         ret = -1;
 561                         goto out;
 562                 }
 563
 564                 orig_insn = find_instruction(file, special_alt->orig_sec,
 565                                              special_alt->orig_off);
 566                 if (!orig_insn) {
 567                         WARN_FUNC("special: can't find orig instruction",
 568                                   special_alt->orig_sec, special_alt->orig_off);
 569                         ret = -1;
 570                         goto out;
 571                 }
 572
 573                 new_insn = NULL;
 574                 if (!special_alt->group || special_alt->new_len) {
 575                         new_insn = find_instruction(file, special_alt->new_sec,
 576                                                     special_alt->new_off);
 577                         if (!new_insn) {
 578                                 WARN_FUNC("special: can't find new instruction",
 579                                           special_alt->new_sec,
 580                                           special_alt->new_off);
 581                                 ret = -1;
 582                                 goto out;
 583                         }
 584                 }
 585
 586                 if (special_alt->group) {
 587                         ret = handle_group_alt(file, special_alt, orig_insn,
 588                                                &new_insn);
 589                         if (ret)
 590                                 goto out;
 591                 } else if (special_alt->jump_or_nop) {
 592                         ret = handle_jump_alt(file, special_alt, orig_insn,
 593                                               &new_insn);
 594                         if (ret)
 595                                 goto out;
 596                 }
 597
 598                 alt->insn = new_insn;
 599                 list_add_tail(&alt->list, &orig_insn->alts);
 600
 601                 list_del(&special_alt->list);
 602                 free(special_alt);
 603         }
 604
 605 out:
 606         return ret;
 607 }
 608
 609 /*
 610  * For some switch statements, gcc generates a jump table in the .rodata
 611  * section which contains a list of addresses within the function to jump to.
 612  * This finds these jump tables and adds them to the insn->alts lists.
 613  */
 614 static int get_switch_alts(struct objtool_file *file)
 615 {
 616         struct instruction *insn, *alt_insn;
 617         struct rela *rodata_rela, *rela;
 618         struct section *rodata;
 619         struct symbol *func;
 620         struct alternative *alt;
 621
 622         list_for_each_entry(insn, &file->insns, list) {
 623                 if (insn->type != INSN_JUMP_DYNAMIC)
 624                         continue;
 625
 626                 rodata_rela = find_rela_by_dest_range(insn->sec, insn->offset,
 627                                                       insn->len);
 628                 if (!rodata_rela || strcmp(rodata_rela->sym->name, ".rodata"))
 629                         continue;
 630
 631                 rodata = find_section_by_name(file->elf, ".rodata");
 632                 if (!rodata || !rodata->rela)
 633                         continue;
 634
 635                 /* common case: jmpq *[addr](,%rax,8) */
 636                 rela = find_rela_by_dest(rodata, rodata_rela->addend);
 637
 638                 /* rare case:   jmpq *[addr](%rip) */
 639                 if (!rela)
 640                         rela = find_rela_by_dest(rodata,
 641                                                  rodata_rela->addend + 4);
 642                 if (!rela)
 643                         continue;
 644
 645                 func = find_containing_func(insn->sec, insn->offset);
 646                 if (!func) {
 647                         WARN_FUNC("can't find containing func",
 648                                   insn->sec, insn->offset);
 649                         return -1;
 650                 }
 651
 652                 list_for_each_entry_from(rela, &rodata->rela->relas, list) {
 653                         if (rela->sym->sec != insn->sec ||
 654                             rela->addend <= func->offset ||
 655                             rela->addend >= func->offset + func->len)
 656                                 break;
 657
 658                         alt_insn = find_instruction(file, insn->sec,
 659                                                     rela->addend);
 660                         if (!alt_insn) {
 661                                 WARN("%s: can't find instruction at %s+0x%x",
 662                                      rodata->rela->name, insn->sec->name,
 663                                      rela->addend);
 664                                 return -1;
 665                         }
 666
 667                         alt = malloc(sizeof(*alt));
 668                         if (!alt) {
 669                                 WARN("malloc failed");
 670                                 return -1;
 671                         }
 672
 673                         alt->insn = alt_insn;
 674                         list_add_tail(&alt->list, &insn->alts);
 675                 }
 676         }
 677
 678         return 0;
 679 }
 680
 681 static int decode_sections(struct objtool_file *file)
 682 {
 683         int ret;
 684
 685         ret = decode_instructions(file);
 686         if (ret)
 687                 return ret;
 688
 689         get_ignores(file);
 690
 691         ret = get_jump_destinations(file);
 692         if (ret)
 693                 return ret;
 694
 695         ret = get_call_destinations(file);
 696         if (ret)
 697                 return ret;
 698
 699         ret = get_special_section_alts(file);
 700         if (ret)
 701                 return ret;
 702
 703         ret = get_switch_alts(file);
 704         if (ret)
 705                 return ret;
 706
 707         return 0;
 708 }
 709
 710 static bool is_fentry_call(struct instruction *insn)
 711 {
 712         if (insn->type == INSN_CALL &&
 713             insn->call_dest->type == STT_NOTYPE &&
 714             !strcmp(insn->call_dest->name, "__fentry__"))
 715                 return true;
 716
 717         return false;
 718 }
 719
 720 static bool has_modified_stack_frame(struct instruction *insn)
 721 {
 722         return (insn->state & STATE_FP_SAVED) ||
 723                (insn->state & STATE_FP_SETUP);
 724 }
 725
 726 static bool has_valid_stack_frame(struct instruction *insn)
 727 {
 728         return (insn->state & STATE_FP_SAVED) &&
 729                (insn->state & STATE_FP_SETUP);
 730 }
 731
 732 /*
 733  * Follow the branch starting at the given instruction, and recursively follow
 734  * any other branches (jumps).  Meanwhile, track the frame pointer state at
 735  * each instruction and validate all the rules described in
 736  * tools/objtool/Documentation/stack-validation.txt.
 737  */
 738 static int validate_branch(struct objtool_file *file,
 739                            struct instruction *first, unsigned char first_state)
 740 {
 741         struct alternative *alt;
 742         struct instruction *insn;
 743         struct section *sec;
 744         unsigned char state;
 745         int ret, warnings = 0;
 746
 747         insn = first;
 748         sec = insn->sec;
 749         state = first_state;
 750
 751         if (insn->alt_group && list_empty(&insn->alts)) {
 752                 WARN_FUNC("don't know how to handle branch to middle of alternative instruction group",
 753                           sec, insn->offset);
 754                 warnings++;
 755         }
 756
 757         while (1) {
 758                 if (insn->visited) {
 759                         if (insn->state != state) {
 760                                 WARN_FUNC("frame pointer state mismatch",
 761                                           sec, insn->offset);
 762                                 warnings++;
 763                         }
 764
 765                         return warnings;
 766                 }
 767
 768                 /*
 769                  * Catch a rare case where a noreturn function falls through to
 770                  * the next function.
 771                  */
 772                 if (is_fentry_call(insn) && (state & STATE_FENTRY))
 773                         return warnings;
 774
 775                 insn->visited = true;
 776                 insn->state = state;
 777
 778                 list_for_each_entry(alt, &insn->alts, list) {
 779                         ret = validate_branch(file, alt->insn, state);
 780                         warnings += ret;
 781                 }
 782
 783                 switch (insn->type) {
 784
 785                 case INSN_FP_SAVE:
 786                         if (!nofp) {
 787                                 if (state & STATE_FP_SAVED) {
 788                                         WARN_FUNC("duplicate frame pointer save",
 789                                                   sec, insn->offset);
 790                                         warnings++;
 791                                 }
 792                                 state |= STATE_FP_SAVED;
 793                         }
 794                         break;
 795
 796                 case INSN_FP_SETUP:
 797                         if (!nofp) {
 798                                 if (state & STATE_FP_SETUP) {
 799                                         WARN_FUNC("duplicate frame pointer setup",
 800                                                   sec, insn->offset);
 801                                         warnings++;
 802                                 }
 803                                 state |= STATE_FP_SETUP;
 804                         }
 805                         break;
 806
 807                 case INSN_FP_RESTORE:
 808                         if (!nofp) {
 809                                 if (has_valid_stack_frame(insn))
 810                                         state &= ~STATE_FP_SETUP;
 811
 812                                 state &= ~STATE_FP_SAVED;
 813                         }
 814                         break;
 815
 816                 case INSN_RETURN:
 817                         if (!nofp && has_modified_stack_frame(insn)) {
 818                                 WARN_FUNC("return without frame pointer restore",
 819                                           sec, insn->offset);
 820                                 warnings++;
 821                         }
 822                         return warnings;
 823
 824                 case INSN_CALL:
 825                         if (is_fentry_call(insn)) {
 826                                 state |= STATE_FENTRY;
 827                                 break;
 828                         }
 829
 830                         ret = dead_end_function(file, insn->call_dest);
 831                         if (ret == 1)
 832                                 return warnings;
 833                         if (ret == -1)
 834                                 warnings++;
 835
 836                         /* fallthrough */
 837                 case INSN_CALL_DYNAMIC:
 838                         if (!nofp && !has_valid_stack_frame(insn)) {
 839                                 WARN_FUNC("call without frame pointer save/setup",
 840                                           sec, insn->offset);
 841                                 warnings++;
 842                         }
 843                         break;
 844
 845                 case INSN_JUMP_CONDITIONAL:
 846                 case INSN_JUMP_UNCONDITIONAL:
 847                         if (insn->jump_dest) {
 848                                 ret = validate_branch(file, insn->jump_dest,
 849                                                       state);
 850                                 warnings += ret;
 851                         } else if (has_modified_stack_frame(insn)) {
 852                                 WARN_FUNC("sibling call from callable instruction with changed frame pointer",
 853                                           sec, insn->offset);
 854                                 warnings++;
 855                         } /* else it's a sibling call */
 856
 857                         if (insn->type == INSN_JUMP_UNCONDITIONAL)
 858                                 return warnings;
 859
 860                         break;
 861
 862                 case INSN_JUMP_DYNAMIC:
 863                         if (list_empty(&insn->alts) &&
 864                             has_modified_stack_frame(insn)) {
 865                                 WARN_FUNC("sibling call from callable instruction with changed frame pointer",
 866                                           sec, insn->offset);
 867                                 warnings++;
 868                         }
 869
 870                         return warnings;
 871
 872                 case INSN_BUG:
 873                         return warnings;
 874
 875                 default:
 876                         break;
 877                 }
 878
 879                 insn = list_next_entry(insn, list);
 880
 881                 if (&insn->list == &file->insns || insn->sec != sec) {
 882                         WARN("%s: unexpected end of section", sec->name);
 883                         warnings++;
 884                         return warnings;
 885                 }
 886         }
 887
 888         return warnings;
 889 }
 890
 891 static bool is_gcov_insn(struct instruction *insn)
 892 {
 893         struct rela *rela;
 894         struct section *sec;
 895         struct symbol *sym;
 896         unsigned long offset;
 897
 898         rela = find_rela_by_dest_range(insn->sec, insn->offset, insn->len);
 899         if (!rela)
 900                 return false;
 901
 902         if (rela->sym->type != STT_SECTION)
 903                 return false;
 904
 905         sec = rela->sym->sec;
 906         offset = rela->addend + insn->offset + insn->len - rela->offset;
 907
 908         list_for_each_entry(sym, &sec->symbols, list) {
 909                 if (sym->type != STT_OBJECT)
 910                         continue;
 911
 912                 if (offset >= sym->offset && offset < sym->offset + sym->len)
 913                         return (!memcmp(sym->name, "__gcov0.", 8));
 914         }
 915
 916         return false;
 917 }
 918
 919 static bool is_kasan_insn(struct instruction *insn)
 920 {
 921         return (insn->type == INSN_CALL &&
 922                 !strcmp(insn->call_dest->name, "__asan_handle_no_return"));
 923 }
 924
 925 static bool is_ubsan_insn(struct instruction *insn)
 926 {
 927         return (insn->type == INSN_CALL &&
 928                 !strcmp(insn->call_dest->name,
 929                         "__ubsan_handle_builtin_unreachable"));
 930 }
 931
 932 static bool ignore_unreachable_insn(struct instruction *insn,
 933                                     unsigned long func_end)
 934 {
 935         int i;
 936
 937         if (insn->type == INSN_NOP)
 938                 return true;
 939
 940         if (is_gcov_insn(insn))
 941                 return true;
 942
 943         /*
 944          * Check if this (or a subsequent) instruction is related to
 945          * CONFIG_UBSAN or CONFIG_KASAN.
 946          *
 947          * End the search at 5 instructions to avoid going into the weeds.
 948          */
 949         for (i = 0; i < 5; i++) {
 950
 951                 if (is_kasan_insn(insn) || is_ubsan_insn(insn))
 952                         return true;
 953
 954                 if (insn->type == INSN_JUMP_UNCONDITIONAL && insn->jump_dest) {
 955                         insn = insn->jump_dest;
 956                         continue;
 957                 }
 958
 959                 if (insn->offset + insn->len >= func_end)
 960                         break;
 961                 insn = list_next_entry(insn, list);
 962         }
 963
 964         return false;
 965 }
 966
 967 static int validate_functions(struct objtool_file *file)
 968 {
 969         struct section *sec;
 970         struct symbol *func;
 971         struct instruction *insn;
 972         unsigned long func_end;
 973         int ret, warnings = 0;
 974
 975         list_for_each_entry(sec, &file->elf->sections, list) {
 976                 list_for_each_entry(func, &sec->symbols, list) {
 977                         if (func->type != STT_FUNC)
 978                                 continue;
 979
 980                         insn = find_instruction(file, sec, func->offset);
 981                         if (!insn) {
 982                                 WARN("%s(): can't find starting instruction",
 983                                      func->name);
 984                                 warnings++;
 985                                 continue;
 986                         }
 987
 988                         ret = validate_branch(file, insn, 0);
 989                         warnings += ret;
 990                 }
 991         }
 992
 993         list_for_each_entry(sec, &file->elf->sections, list) {
 994                 list_for_each_entry(func, &sec->symbols, list) {
 995                         if (func->type != STT_FUNC)
 996                                 continue;
 997
 998                         insn = find_instruction(file, sec, func->offset);
 999                         if (!insn)
1000                                 continue;
1001
1002                         func_end = func->offset + func->len;
1003
1004                         list_for_each_entry_from(insn, &file->insns, list) {
1005                                 if (insn->sec != func->sec ||
1006                                     insn->offset >= func_end)
1007                                         break;
1008
1009                                 if (insn->visited)
1010                                         continue;
1011
1012                                 if (!ignore_unreachable_insn(insn, func_end)) {
1013                                         WARN_FUNC("function has unreachable instruction", insn->sec, insn->offset);
1014                                         warnings++;
1015                                 }
1016
1017                                 insn->visited = true;
1018                         }
1019                 }
1020         }
1021
1022         return warnings;
1023 }
1024
1025 static int validate_uncallable_instructions(struct objtool_file *file)
1026 {
1027         struct instruction *insn;
1028         int warnings = 0;
1029
1030         list_for_each_entry(insn, &file->insns, list) {
1031                 if (!insn->visited && insn->type == INSN_RETURN) {
1032                         WARN_FUNC("return instruction outside of a callable function",
1033                                   insn->sec, insn->offset);
1034                         warnings++;
1035                 }
1036         }
1037
1038         return warnings;
1039 }
1040
1041 static void cleanup(struct objtool_file *file)
1042 {
1043         struct instruction *insn, *tmpinsn;
1044         struct alternative *alt, *tmpalt;
1045
1046         list_for_each_entry_safe(insn, tmpinsn, &file->insns, list) {
1047                 list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
1048                         list_del(&alt->list);
1049                         free(alt);
1050                 }
1051                 list_del(&insn->list);
1052                 free(insn);
1053         }
1054         elf_close(file->elf);
1055 }
1056
1057 const char * const check_usage[] = {
1058         "objtool check [<options>] file.o",
1059         NULL,
1060 };
1061
1062 int cmd_check(int argc, const char **argv)
1063 {
1064         struct objtool_file file;
1065         int ret, warnings = 0;
1066
1067         const struct option options[] = {
1068                 OPT_BOOLEAN('f', "no-fp", &nofp, "Skip frame pointer validation"),
1069                 OPT_END(),
1070         };
1071
1072         argc = parse_options(argc, argv, options, check_usage, 0);
1073
1074         if (argc != 1)
1075                 usage_with_options(check_usage, options);
1076
1077         objname = argv[0];
1078
1079         file.elf = elf_open(objname);
1080         if (!file.elf) {
1081                 fprintf(stderr, "error reading elf file %s\n", objname);
1082                 return 1;
1083         }
1084
1085         INIT_LIST_HEAD(&file.insns);
1086
1087         ret = decode_sections(&file);
1088         if (ret < 0)
1089                 goto out;
1090         warnings += ret;
1091
1092         ret = validate_functions(&file);
1093         if (ret < 0)
1094                 goto out;
1095         warnings += ret;
1096
1097         ret = validate_uncallable_instructions(&file);
1098         if (ret < 0)
1099                 goto out;
1100         warnings += ret;
1101
1102 out:
1103         cleanup(&file);
1104
1105         /* ignore warnings for now until we get all the code cleaned up */
1106         if (ret || warnings)
1107                 return 0;
1108         return 0;
1109 }