tools/objtool/check.c

   1 /*
   2  * Copyright (C) 2015-2017 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 #include <string.h>
  19 #include <stdlib.h>
  20
  21 #include "check.h"
  22 #include "elf.h"
  23 #include "special.h"
  24 #include "arch.h"
  25 #include "warn.h"
  26
  27 #include <linux/hashtable.h>
  28 #include <linux/kernel.h>
  29
  30 struct alternative {
  31         struct list_head list;
  32         struct instruction *insn;
  33 };
  34
  35 const char *objname;
  36 static bool no_fp;
  37 struct cfi_state initial_func_cfi;
  38
  39 struct instruction *find_insn(struct objtool_file *file,
  40                               struct section *sec, unsigned long offset)
  41 {
  42         struct instruction *insn;
  43
  44         hash_for_each_possible(file->insn_hash, insn, hash, offset)
  45                 if (insn->sec == sec && insn->offset == offset)
  46                         return insn;
  47
  48         return NULL;
  49 }
  50
  51 static struct instruction *next_insn_same_sec(struct objtool_file *file,
  52                                               struct instruction *insn)
  53 {
  54         struct instruction *next = list_next_entry(insn, list);
  55
  56         if (!next || &next->list == &file->insn_list || next->sec != insn->sec)
  57                 return NULL;
  58
  59         return next;
  60 }
  61
  62 #define func_for_each_insn(file, func, insn)                            \
  63         for (insn = find_insn(file, func->sec, func->offset);           \
  64              insn && &insn->list != &file->insn_list &&                 \
  65                 insn->sec == func->sec &&                               \
  66                 insn->offset < func->offset + func->len;                \
  67              insn = list_next_entry(insn, list))
  68
  69 #define func_for_each_insn_continue_reverse(file, func, insn)           \
  70         for (insn = list_prev_entry(insn, list);                        \
  71              &insn->list != &file->insn_list &&                         \
  72                 insn->sec == func->sec && insn->offset >= func->offset; \
  73              insn = list_prev_entry(insn, list))
  74
  75 #define sec_for_each_insn_from(file, insn)                              \
  76         for (; insn; insn = next_insn_same_sec(file, insn))
  77
  78 #define sec_for_each_insn_continue(file, insn)                          \
  79         for (insn = next_insn_same_sec(file, insn); insn;               \
  80              insn = next_insn_same_sec(file, insn))
  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 rela *rela;
  90
  91         /* check for STACK_FRAME_NON_STANDARD */
  92         if (file->whitelist && file->whitelist->rela)
  93                 list_for_each_entry(rela, &file->whitelist->rela->rela_list, list) {
  94                         if (rela->sym->type == STT_SECTION &&
  95                             rela->sym->sec == func->sec &&
  96                             rela->addend == func->offset)
  97                                 return true;
  98                         if (rela->sym->type == STT_FUNC && rela->sym == func)
  99                                 return true;
 100                 }
 101
 102         return false;
 103 }
 104
 105 /*
 106  * This checks to see if the given function is a "noreturn" function.
 107  *
 108  * For global functions which are outside the scope of this object file, we
 109  * have to keep a manual list of them.
 110  *
 111  * For local functions, we have to detect them manually by simply looking for
 112  * the lack of a return instruction.
 113  *
 114  * Returns:
 115  *  -1: error
 116  *   0: no dead end
 117  *   1: dead end
 118  */
 119 static int __dead_end_function(struct objtool_file *file, struct symbol *func,
 120                                int recursion)
 121 {
 122         int i;
 123         struct instruction *insn;
 124         bool empty = true;
 125
 126         /*
 127          * Unfortunately these have to be hard coded because the noreturn
 128          * attribute isn't provided in ELF data.
 129          */
 130         static const char * const global_noreturns[] = {
 131                 "__stack_chk_fail",
 132                 "panic",
 133                 "do_exit",
 134                 "do_task_dead",
 135                 "__module_put_and_exit",
 136                 "complete_and_exit",
 137                 "kvm_spurious_fault",
 138                 "__reiserfs_panic",
 139                 "lbug_with_loc",
 140                 "fortify_panic",
 141         };
 142
 143         if (func->bind == STB_WEAK)
 144                 return 0;
 145
 146         if (func->bind == STB_GLOBAL)
 147                 for (i = 0; i < ARRAY_SIZE(global_noreturns); i++)
 148                         if (!strcmp(func->name, global_noreturns[i]))
 149                                 return 1;
 150
 151         if (!func->sec)
 152                 return 0;
 153
 154         func_for_each_insn(file, func, insn) {
 155                 empty = false;
 156
 157                 if (insn->type == INSN_RETURN)
 158                         return 0;
 159         }
 160
 161         if (empty)
 162                 return 0;
 163
 164         /*
 165          * A function can have a sibling call instead of a return.  In that
 166          * case, the function's dead-end status depends on whether the target
 167          * of the sibling call returns.
 168          */
 169         func_for_each_insn(file, func, insn) {
 170                 if (insn->sec != func->sec ||
 171                     insn->offset >= func->offset + func->len)
 172                         break;
 173
 174                 if (insn->type == INSN_JUMP_UNCONDITIONAL) {
 175                         struct instruction *dest = insn->jump_dest;
 176                         struct symbol *dest_func;
 177
 178                         if (!dest)
 179                                 /* sibling call to another file */
 180                                 return 0;
 181
 182                         if (dest->sec != func->sec ||
 183                             dest->offset < func->offset ||
 184                             dest->offset >= func->offset + func->len) {
 185                                 /* local sibling call */
 186                                 dest_func = find_symbol_by_offset(dest->sec,
 187                                                                   dest->offset);
 188                                 if (!dest_func)
 189                                         continue;
 190
 191                                 if (recursion == 5) {
 192                                         WARN_FUNC("infinite recursion (objtool bug!)",
 193                                                   dest->sec, dest->offset);
 194                                         return -1;
 195                                 }
 196
 197                                 return __dead_end_function(file, dest_func,
 198                                                            recursion + 1);
 199                         }
 200                 }
 201
 202                 if (insn->type == INSN_JUMP_DYNAMIC && list_empty(&insn->alts))
 203                         /* sibling call */
 204                         return 0;
 205         }
 206
 207         return 1;
 208 }
 209
 210 static int dead_end_function(struct objtool_file *file, struct symbol *func)
 211 {
 212         return __dead_end_function(file, func, 0);
 213 }
 214
 215 static void clear_insn_state(struct insn_state *state)
 216 {
 217         int i;
 218
 219         memset(state, 0, sizeof(*state));
 220         state->cfa.base = CFI_UNDEFINED;
 221         for (i = 0; i < CFI_NUM_REGS; i++) {
 222                 state->regs[i].base = CFI_UNDEFINED;
 223                 state->vals[i].base = CFI_UNDEFINED;
 224         }
 225         state->drap_reg = CFI_UNDEFINED;
 226         state->drap_offset = -1;
 227 }
 228
 229 /*
 230  * Call the arch-specific instruction decoder for all the instructions and add
 231  * them to the global instruction list.
 232  */
 233 static int decode_instructions(struct objtool_file *file)
 234 {
 235         struct section *sec;
 236         struct symbol *func;
 237         unsigned long offset;
 238         struct instruction *insn;
 239         int ret;
 240
 241         for_each_sec(file, sec) {
 242
 243                 if (!(sec->sh.sh_flags & SHF_EXECINSTR))
 244                         continue;
 245
 246                 if (strcmp(sec->name, ".altinstr_replacement") &&
 247                     strcmp(sec->name, ".altinstr_aux") &&
 248                     strncmp(sec->name, ".discard.", 9))
 249                         sec->text = true;
 250
 251                 for (offset = 0; offset < sec->len; offset += insn->len) {
 252                         insn = malloc(sizeof(*insn));
 253                         if (!insn) {
 254                                 WARN("malloc failed");
 255                                 return -1;
 256                         }
 257                         memset(insn, 0, sizeof(*insn));
 258                         INIT_LIST_HEAD(&insn->alts);
 259                         clear_insn_state(&insn->state);
 260
 261                         insn->sec = sec;
 262                         insn->offset = offset;
 263
 264                         ret = arch_decode_instruction(file->elf, sec, offset,
 265                                                       sec->len - offset,
 266                                                       &insn->len, &insn->type,
 267                                                       &insn->immediate,
 268                                                       &insn->stack_op);
 269                         if (ret)
 270                                 goto err;
 271
 272                         if (!insn->type || insn->type > INSN_LAST) {
 273                                 WARN_FUNC("invalid instruction type %d",
 274                                           insn->sec, insn->offset, insn->type);
 275                                 ret = -1;
 276                                 goto err;
 277                         }
 278
 279                         hash_add(file->insn_hash, &insn->hash, insn->offset);
 280                         list_add_tail(&insn->list, &file->insn_list);
 281                 }
 282
 283                 list_for_each_entry(func, &sec->symbol_list, list) {
 284                         if (func->type != STT_FUNC)
 285                                 continue;
 286
 287                         if (!find_insn(file, sec, func->offset)) {
 288                                 WARN("%s(): can't find starting instruction",
 289                                      func->name);
 290                                 return -1;
 291                         }
 292
 293                         func_for_each_insn(file, func, insn)
 294                                 if (!insn->func)
 295                                         insn->func = func;
 296                 }
 297         }
 298
 299         return 0;
 300
 301 err:
 302         free(insn);
 303         return ret;
 304 }
 305
 306 /*
 307  * Mark "ud2" instructions and manually annotated dead ends.
 308  */
 309 static int add_dead_ends(struct objtool_file *file)
 310 {
 311         struct section *sec;
 312         struct rela *rela;
 313         struct instruction *insn;
 314         bool found;
 315
 316         /*
 317          * By default, "ud2" is a dead end unless otherwise annotated, because
 318          * GCC 7 inserts it for certain divide-by-zero cases.
 319          */
 320         for_each_insn(file, insn)
 321                 if (insn->type == INSN_BUG)
 322                         insn->dead_end = true;
 323
 324         /*
 325          * Check for manually annotated dead ends.
 326          */
 327         sec = find_section_by_name(file->elf, ".rela.discard.unreachable");
 328         if (!sec)
 329                 goto reachable;
 330
 331         list_for_each_entry(rela, &sec->rela_list, list) {
 332                 if (rela->sym->type != STT_SECTION) {
 333                         WARN("unexpected relocation symbol type in %s", sec->name);
 334                         return -1;
 335                 }
 336                 insn = find_insn(file, rela->sym->sec, rela->addend);
 337                 if (insn)
 338                         insn = list_prev_entry(insn, list);
 339                 else if (rela->addend == rela->sym->sec->len) {
 340                         found = false;
 341                         list_for_each_entry_reverse(insn, &file->insn_list, list) {
 342                                 if (insn->sec == rela->sym->sec) {
 343                                         found = true;
 344                                         break;
 345                                 }
 346                         }
 347
 348                         if (!found) {
 349                                 WARN("can't find unreachable insn at %s+0x%x",
 350                                      rela->sym->sec->name, rela->addend);
 351                                 return -1;
 352                         }
 353                 } else {
 354                         WARN("can't find unreachable insn at %s+0x%x",
 355                              rela->sym->sec->name, rela->addend);
 356                         return -1;
 357                 }
 358
 359                 insn->dead_end = true;
 360         }
 361
 362 reachable:
 363         /*
 364          * These manually annotated reachable checks are needed for GCC 4.4,
 365          * where the Linux unreachable() macro isn't supported.  In that case
 366          * GCC doesn't know the "ud2" is fatal, so it generates code as if it's
 367          * not a dead end.
 368          */
 369         sec = find_section_by_name(file->elf, ".rela.discard.reachable");
 370         if (!sec)
 371                 return 0;
 372
 373         list_for_each_entry(rela, &sec->rela_list, list) {
 374                 if (rela->sym->type != STT_SECTION) {
 375                         WARN("unexpected relocation symbol type in %s", sec->name);
 376                         return -1;
 377                 }
 378                 insn = find_insn(file, rela->sym->sec, rela->addend);
 379                 if (insn)
 380                         insn = list_prev_entry(insn, list);
 381                 else if (rela->addend == rela->sym->sec->len) {
 382                         found = false;
 383                         list_for_each_entry_reverse(insn, &file->insn_list, list) {
 384                                 if (insn->sec == rela->sym->sec) {
 385                                         found = true;
 386                                         break;
 387                                 }
 388                         }
 389
 390                         if (!found) {
 391                                 WARN("can't find reachable insn at %s+0x%x",
 392                                      rela->sym->sec->name, rela->addend);
 393                                 return -1;
 394                         }
 395                 } else {
 396                         WARN("can't find reachable insn at %s+0x%x",
 397                              rela->sym->sec->name, rela->addend);
 398                         return -1;
 399                 }
 400
 401                 insn->dead_end = false;
 402         }
 403
 404         return 0;
 405 }
 406
 407 /*
 408  * Warnings shouldn't be reported for ignored functions.
 409  */
 410 static void add_ignores(struct objtool_file *file)
 411 {
 412         struct instruction *insn;
 413         struct section *sec;
 414         struct symbol *func;
 415
 416         for_each_sec(file, sec) {
 417                 list_for_each_entry(func, &sec->symbol_list, list) {
 418                         if (func->type != STT_FUNC)
 419                                 continue;
 420
 421                         if (!ignore_func(file, func))
 422                                 continue;
 423
 424                         func_for_each_insn(file, func, insn)
 425                                 insn->ignore = true;
 426                 }
 427         }
 428 }
 429
 430 /*
 431  * Find the destination instructions for all jumps.
 432  */
 433 static int add_jump_destinations(struct objtool_file *file)
 434 {
 435         struct instruction *insn;
 436         struct rela *rela;
 437         struct section *dest_sec;
 438         unsigned long dest_off;
 439
 440         for_each_insn(file, insn) {
 441                 if (insn->type != INSN_JUMP_CONDITIONAL &&
 442                     insn->type != INSN_JUMP_UNCONDITIONAL)
 443                         continue;
 444
 445                 if (insn->ignore)
 446                         continue;
 447
 448                 rela = find_rela_by_dest_range(insn->sec, insn->offset,
 449                                                insn->len);
 450                 if (!rela) {
 451                         dest_sec = insn->sec;
 452                         dest_off = insn->offset + insn->len + insn->immediate;
 453                 } else if (rela->sym->type == STT_SECTION) {
 454                         dest_sec = rela->sym->sec;
 455                         dest_off = rela->addend + 4;
 456                 } else if (rela->sym->sec->idx) {
 457                         dest_sec = rela->sym->sec;
 458                         dest_off = rela->sym->sym.st_value + rela->addend + 4;
 459                 } else if (strstr(rela->sym->name, "_indirect_thunk_")) {
 460                         /*
 461                          * Retpoline jumps are really dynamic jumps in
 462                          * disguise, so convert them accordingly.
 463                          */
 464                         insn->type = INSN_JUMP_DYNAMIC;
 465                         continue;
 466                 } else {
 467                         /* sibling call */
 468                         insn->jump_dest = 0;
 469                         continue;
 470                 }
 471
 472                 insn->jump_dest = find_insn(file, dest_sec, dest_off);
 473                 if (!insn->jump_dest) {
 474
 475                         /*
 476                          * This is a special case where an alt instruction
 477                          * jumps past the end of the section.  These are
 478                          * handled later in handle_group_alt().
 479                          */
 480                         if (!strcmp(insn->sec->name, ".altinstr_replacement"))
 481                                 continue;
 482
 483                         WARN_FUNC("can't find jump dest instruction at %s+0x%lx",
 484                                   insn->sec, insn->offset, dest_sec->name,
 485                                   dest_off);
 486                         return -1;
 487                 }
 488         }
 489
 490         return 0;
 491 }
 492
 493 /*
 494  * Find the destination instructions for all calls.
 495  */
 496 static int add_call_destinations(struct objtool_file *file)
 497 {
 498         struct instruction *insn;
 499         unsigned long dest_off;
 500         struct rela *rela;
 501
 502         for_each_insn(file, insn) {
 503                 if (insn->type != INSN_CALL)
 504                         continue;
 505
 506                 rela = find_rela_by_dest_range(insn->sec, insn->offset,
 507                                                insn->len);
 508                 if (!rela) {
 509                         dest_off = insn->offset + insn->len + insn->immediate;
 510                         insn->call_dest = find_symbol_by_offset(insn->sec,
 511                                                                 dest_off);
 512                         if (!insn->call_dest) {
 513                                 WARN_FUNC("can't find call dest symbol at offset 0x%lx",
 514                                           insn->sec, insn->offset, dest_off);
 515                                 return -1;
 516                         }
 517                 } else if (rela->sym->type == STT_SECTION) {
 518                         insn->call_dest = find_symbol_by_offset(rela->sym->sec,
 519                                                                 rela->addend+4);
 520                         if (!insn->call_dest ||
 521                             insn->call_dest->type != STT_FUNC) {
 522                                 WARN_FUNC("can't find call dest symbol at %s+0x%x",
 523                                           insn->sec, insn->offset,
 524                                           rela->sym->sec->name,
 525                                           rela->addend + 4);
 526                                 return -1;
 527                         }
 528                 } else
 529                         insn->call_dest = rela->sym;
 530         }
 531
 532         return 0;
 533 }
 534
 535 /*
 536  * The .alternatives section requires some extra special care, over and above
 537  * what other special sections require:
 538  *
 539  * 1. Because alternatives are patched in-place, we need to insert a fake jump
 540  *    instruction at the end so that validate_branch() skips all the original
 541  *    replaced instructions when validating the new instruction path.
 542  *
 543  * 2. An added wrinkle is that the new instruction length might be zero.  In
 544  *    that case the old instructions are replaced with noops.  We simulate that
 545  *    by creating a fake jump as the only new instruction.
 546  *
 547  * 3. In some cases, the alternative section includes an instruction which
 548  *    conditionally jumps to the _end_ of the entry.  We have to modify these
 549  *    jumps' destinations to point back to .text rather than the end of the
 550  *    entry in .altinstr_replacement.
 551  *
 552  * 4. It has been requested that we don't validate the !POPCNT feature path
 553  *    which is a "very very small percentage of machines".
 554  */
 555 static int handle_group_alt(struct objtool_file *file,
 556                             struct special_alt *special_alt,
 557                             struct instruction *orig_insn,
 558                             struct instruction **new_insn)
 559 {
 560         struct instruction *last_orig_insn, *last_new_insn, *insn, *fake_jump;
 561         unsigned long dest_off;
 562
 563         last_orig_insn = NULL;
 564         insn = orig_insn;
 565         sec_for_each_insn_from(file, insn) {
 566                 if (insn->offset >= special_alt->orig_off + special_alt->orig_len)
 567                         break;
 568
 569                 if (special_alt->skip_orig)
 570                         insn->type = INSN_NOP;
 571
 572                 insn->alt_group = true;
 573                 last_orig_insn = insn;
 574         }
 575
 576         if (!next_insn_same_sec(file, last_orig_insn)) {
 577                 WARN("%s: don't know how to handle alternatives at end of section",
 578                      special_alt->orig_sec->name);
 579                 return -1;
 580         }
 581
 582         fake_jump = malloc(sizeof(*fake_jump));
 583         if (!fake_jump) {
 584                 WARN("malloc failed");
 585                 return -1;
 586         }
 587         memset(fake_jump, 0, sizeof(*fake_jump));
 588         INIT_LIST_HEAD(&fake_jump->alts);
 589         clear_insn_state(&fake_jump->state);
 590
 591         fake_jump->sec = special_alt->new_sec;
 592         fake_jump->offset = -1;
 593         fake_jump->type = INSN_JUMP_UNCONDITIONAL;
 594         fake_jump->jump_dest = list_next_entry(last_orig_insn, list);
 595         fake_jump->ignore = true;
 596
 597         if (!special_alt->new_len) {
 598                 *new_insn = fake_jump;
 599                 return 0;
 600         }
 601
 602         last_new_insn = NULL;
 603         insn = *new_insn;
 604         sec_for_each_insn_from(file, insn) {
 605                 if (insn->offset >= special_alt->new_off + special_alt->new_len)
 606                         break;
 607
 608                 last_new_insn = insn;
 609
 610                 if (insn->type != INSN_JUMP_CONDITIONAL &&
 611                     insn->type != INSN_JUMP_UNCONDITIONAL)
 612                         continue;
 613
 614                 if (!insn->immediate)
 615                         continue;
 616
 617                 dest_off = insn->offset + insn->len + insn->immediate;
 618                 if (dest_off == special_alt->new_off + special_alt->new_len)
 619                         insn->jump_dest = fake_jump;
 620
 621                 if (!insn->jump_dest) {
 622                         WARN_FUNC("can't find alternative jump destination",
 623                                   insn->sec, insn->offset);
 624                         return -1;
 625                 }
 626         }
 627
 628         if (!last_new_insn) {
 629                 WARN_FUNC("can't find last new alternative instruction",
 630                           special_alt->new_sec, special_alt->new_off);
 631                 return -1;
 632         }
 633
 634         list_add(&fake_jump->list, &last_new_insn->list);
 635
 636         return 0;
 637 }
 638
 639 /*
 640  * A jump table entry can either convert a nop to a jump or a jump to a nop.
 641  * If the original instruction is a jump, make the alt entry an effective nop
 642  * by just skipping the original instruction.
 643  */
 644 static int handle_jump_alt(struct objtool_file *file,
 645                            struct special_alt *special_alt,
 646                            struct instruction *orig_insn,
 647                            struct instruction **new_insn)
 648 {
 649         if (orig_insn->type == INSN_NOP)
 650                 return 0;
 651
 652         if (orig_insn->type != INSN_JUMP_UNCONDITIONAL) {
 653                 WARN_FUNC("unsupported instruction at jump label",
 654                           orig_insn->sec, orig_insn->offset);
 655                 return -1;
 656         }
 657
 658         *new_insn = list_next_entry(orig_insn, list);
 659         return 0;
 660 }
 661
 662 /*
 663  * Read all the special sections which have alternate instructions which can be
 664  * patched in or redirected to at runtime.  Each instruction having alternate
 665  * instruction(s) has them added to its insn->alts list, which will be
 666  * traversed in validate_branch().
 667  */
 668 static int add_special_section_alts(struct objtool_file *file)
 669 {
 670         struct list_head special_alts;
 671         struct instruction *orig_insn, *new_insn;
 672         struct special_alt *special_alt, *tmp;
 673         struct alternative *alt;
 674         int ret;
 675
 676         ret = special_get_alts(file->elf, &special_alts);
 677         if (ret)
 678                 return ret;
 679
 680         list_for_each_entry_safe(special_alt, tmp, &special_alts, list) {
 681                 alt = malloc(sizeof(*alt));
 682                 if (!alt) {
 683                         WARN("malloc failed");
 684                         ret = -1;
 685                         goto out;
 686                 }
 687
 688                 orig_insn = find_insn(file, special_alt->orig_sec,
 689                                       special_alt->orig_off);
 690                 if (!orig_insn) {
 691                         WARN_FUNC("special: can't find orig instruction",
 692                                   special_alt->orig_sec, special_alt->orig_off);
 693                         ret = -1;
 694                         goto out;
 695                 }
 696
 697                 new_insn = NULL;
 698                 if (!special_alt->group || special_alt->new_len) {
 699                         new_insn = find_insn(file, special_alt->new_sec,
 700                                              special_alt->new_off);
 701                         if (!new_insn) {
 702                                 WARN_FUNC("special: can't find new instruction",
 703                                           special_alt->new_sec,
 704                                           special_alt->new_off);
 705                                 ret = -1;
 706                                 goto out;
 707                         }
 708                 }
 709
 710                 if (special_alt->group) {
 711                         ret = handle_group_alt(file, special_alt, orig_insn,
 712                                                &new_insn);
 713                         if (ret)
 714                                 goto out;
 715                 } else if (special_alt->jump_or_nop) {
 716                         ret = handle_jump_alt(file, special_alt, orig_insn,
 717                                               &new_insn);
 718                         if (ret)
 719                                 goto out;
 720                 }
 721
 722                 alt->insn = new_insn;
 723                 list_add_tail(&alt->list, &orig_insn->alts);
 724
 725                 list_del(&special_alt->list);
 726                 free(special_alt);
 727         }
 728
 729 out:
 730         return ret;
 731 }
 732
 733 static int add_switch_table(struct objtool_file *file, struct symbol *func,
 734                             struct instruction *insn, struct rela *table,
 735                             struct rela *next_table)
 736 {
 737         struct rela *rela = table;
 738         struct instruction *alt_insn;
 739         struct alternative *alt;
 740
 741         list_for_each_entry_from(rela, &file->rodata->rela->rela_list, list) {
 742                 if (rela == next_table)
 743                         break;
 744
 745                 if (rela->sym->sec != insn->sec ||
 746                     rela->addend <= func->offset ||
 747                     rela->addend >= func->offset + func->len)
 748                         break;
 749
 750                 alt_insn = find_insn(file, insn->sec, rela->addend);
 751                 if (!alt_insn) {
 752                         WARN("%s: can't find instruction at %s+0x%x",
 753                              file->rodata->rela->name, insn->sec->name,
 754                              rela->addend);
 755                         return -1;
 756                 }
 757
 758                 alt = malloc(sizeof(*alt));
 759                 if (!alt) {
 760                         WARN("malloc failed");
 761                         return -1;
 762                 }
 763
 764                 alt->insn = alt_insn;
 765                 list_add_tail(&alt->list, &insn->alts);
 766         }
 767
 768         return 0;
 769 }
 770
 771 /*
 772  * find_switch_table() - Given a dynamic jump, find the switch jump table in
 773  * .rodata associated with it.
 774  *
 775  * There are 3 basic patterns:
 776  *
 777  * 1. jmpq *[rodata addr](,%reg,8)
 778  *
 779  *    This is the most common case by far.  It jumps to an address in a simple
 780  *    jump table which is stored in .rodata.
 781  *
 782  * 2. jmpq *[rodata addr](%rip)
 783  *
 784  *    This is caused by a rare GCC quirk, currently only seen in three driver
 785  *    functions in the kernel, only with certain obscure non-distro configs.
 786  *
 787  *    As part of an optimization, GCC makes a copy of an existing switch jump
 788  *    table, modifies it, and then hard-codes the jump (albeit with an indirect
 789  *    jump) to use a single entry in the table.  The rest of the jump table and
 790  *    some of its jump targets remain as dead code.
 791  *
 792  *    In such a case we can just crudely ignore all unreachable instruction
 793  *    warnings for the entire object file.  Ideally we would just ignore them
 794  *    for the function, but that would require redesigning the code quite a
 795  *    bit.  And honestly that's just not worth doing: unreachable instruction
 796  *    warnings are of questionable value anyway, and this is such a rare issue.
 797  *
 798  * 3. mov [rodata addr],%reg1
 799  *    ... some instructions ...
 800  *    jmpq *(%reg1,%reg2,8)
 801  *
 802  *    This is a fairly uncommon pattern which is new for GCC 6.  As of this
 803  *    writing, there are 11 occurrences of it in the allmodconfig kernel.
 804  *
 805  *    TODO: Once we have DWARF CFI and smarter instruction decoding logic,
 806  *    ensure the same register is used in the mov and jump instructions.
 807  */
 808 static struct rela *find_switch_table(struct objtool_file *file,
 809                                       struct symbol *func,
 810                                       struct instruction *insn)
 811 {
 812         struct rela *text_rela, *rodata_rela;
 813         struct instruction *orig_insn = insn;
 814
 815         text_rela = find_rela_by_dest_range(insn->sec, insn->offset, insn->len);
 816         if (text_rela && text_rela->sym == file->rodata->sym) {
 817                 /* case 1 */
 818                 rodata_rela = find_rela_by_dest(file->rodata,
 819                                                 text_rela->addend);
 820                 if (rodata_rela)
 821                         return rodata_rela;
 822
 823                 /* case 2 */
 824                 rodata_rela = find_rela_by_dest(file->rodata,
 825                                                 text_rela->addend + 4);
 826                 if (!rodata_rela)
 827                         return NULL;
 828                 file->ignore_unreachables = true;
 829                 return rodata_rela;
 830         }
 831
 832         /* case 3 */
 833         func_for_each_insn_continue_reverse(file, func, insn) {
 834                 if (insn->type == INSN_JUMP_DYNAMIC)
 835                         break;
 836
 837                 /* allow small jumps within the range */
 838                 if (insn->type == INSN_JUMP_UNCONDITIONAL &&
 839                     insn->jump_dest &&
 840                     (insn->jump_dest->offset <= insn->offset ||
 841                      insn->jump_dest->offset > orig_insn->offset))
 842                     break;
 843
 844                 /* look for a relocation which references .rodata */
 845                 text_rela = find_rela_by_dest_range(insn->sec, insn->offset,
 846                                                     insn->len);
 847                 if (!text_rela || text_rela->sym != file->rodata->sym)
 848                         continue;
 849
 850                 /*
 851                  * Make sure the .rodata address isn't associated with a
 852                  * symbol.  gcc jump tables are anonymous data.
 853                  */
 854                 if (find_symbol_containing(file->rodata, text_rela->addend))
 855                         continue;
 856
 857                 return find_rela_by_dest(file->rodata, text_rela->addend);
 858         }
 859
 860         return NULL;
 861 }
 862
 863 static int add_func_switch_tables(struct objtool_file *file,
 864                                   struct symbol *func)
 865 {
 866         struct instruction *insn, *prev_jump = NULL;
 867         struct rela *rela, *prev_rela = NULL;
 868         int ret;
 869
 870         func_for_each_insn(file, func, insn) {
 871                 if (insn->type != INSN_JUMP_DYNAMIC)
 872                         continue;
 873
 874                 rela = find_switch_table(file, func, insn);
 875                 if (!rela)
 876                         continue;
 877
 878                 /*
 879                  * We found a switch table, but we don't know yet how big it
 880                  * is.  Don't add it until we reach the end of the function or
 881                  * the beginning of another switch table in the same function.
 882                  */
 883                 if (prev_jump) {
 884                         ret = add_switch_table(file, func, prev_jump, prev_rela,
 885                                                rela);
 886                         if (ret)
 887                                 return ret;
 888                 }
 889
 890                 prev_jump = insn;
 891                 prev_rela = rela;
 892         }
 893
 894         if (prev_jump) {
 895                 ret = add_switch_table(file, func, prev_jump, prev_rela, NULL);
 896                 if (ret)
 897                         return ret;
 898         }
 899
 900         return 0;
 901 }
 902
 903 /*
 904  * For some switch statements, gcc generates a jump table in the .rodata
 905  * section which contains a list of addresses within the function to jump to.
 906  * This finds these jump tables and adds them to the insn->alts lists.
 907  */
 908 static int add_switch_table_alts(struct objtool_file *file)
 909 {
 910         struct section *sec;
 911         struct symbol *func;
 912         int ret;
 913
 914         if (!file->rodata || !file->rodata->rela)
 915                 return 0;
 916
 917         for_each_sec(file, sec) {
 918                 list_for_each_entry(func, &sec->symbol_list, list) {
 919                         if (func->type != STT_FUNC)
 920                                 continue;
 921
 922                         ret = add_func_switch_tables(file, func);
 923                         if (ret)
 924                                 return ret;
 925                 }
 926         }
 927
 928         return 0;
 929 }
 930
 931 static int read_unwind_hints(struct objtool_file *file)
 932 {
 933         struct section *sec, *relasec;
 934         struct rela *rela;
 935         struct unwind_hint *hint;
 936         struct instruction *insn;
 937         struct cfi_reg *cfa;
 938         int i;
 939
 940         sec = find_section_by_name(file->elf, ".discard.unwind_hints");
 941         if (!sec)
 942                 return 0;
 943
 944         relasec = sec->rela;
 945         if (!relasec) {
 946                 WARN("missing .rela.discard.unwind_hints section");
 947                 return -1;
 948         }
 949
 950         if (sec->len % sizeof(struct unwind_hint)) {
 951                 WARN("struct unwind_hint size mismatch");
 952                 return -1;
 953         }
 954
 955         file->hints = true;
 956
 957         for (i = 0; i < sec->len / sizeof(struct unwind_hint); i++) {
 958                 hint = (struct unwind_hint *)sec->data->d_buf + i;
 959
 960                 rela = find_rela_by_dest(sec, i * sizeof(*hint));
 961                 if (!rela) {
 962                         WARN("can't find rela for unwind_hints[%d]", i);
 963                         return -1;
 964                 }
 965
 966                 insn = find_insn(file, rela->sym->sec, rela->addend);
 967                 if (!insn) {
 968                         WARN("can't find insn for unwind_hints[%d]", i);
 969                         return -1;
 970                 }
 971
 972                 cfa = &insn->state.cfa;
 973
 974                 if (hint->type == UNWIND_HINT_TYPE_SAVE) {
 975                         insn->save = true;
 976                         continue;
 977
 978                 } else if (hint->type == UNWIND_HINT_TYPE_RESTORE) {
 979                         insn->restore = true;
 980                         insn->hint = true;
 981                         continue;
 982                 }
 983
 984                 insn->hint = true;
 985
 986                 switch (hint->sp_reg) {
 987                 case ORC_REG_UNDEFINED:
 988                         cfa->base = CFI_UNDEFINED;
 989                         break;
 990                 case ORC_REG_SP:
 991                         cfa->base = CFI_SP;
 992                         break;
 993                 case ORC_REG_BP:
 994                         cfa->base = CFI_BP;
 995                         break;
 996                 case ORC_REG_SP_INDIRECT:
 997                         cfa->base = CFI_SP_INDIRECT;
 998                         break;
 999                 case ORC_REG_R10:
1000                         cfa->base = CFI_R10;
1001                         break;
1002                 case ORC_REG_R13:
1003                         cfa->base = CFI_R13;
1004                         break;
1005                 case ORC_REG_DI:
1006                         cfa->base = CFI_DI;
1007                         break;
1008                 case ORC_REG_DX:
1009                         cfa->base = CFI_DX;
1010                         break;
1011                 default:
1012                         WARN_FUNC("unsupported unwind_hint sp base reg %d",
1013                                   insn->sec, insn->offset, hint->sp_reg);
1014                         return -1;
1015                 }
1016
1017                 cfa->offset = hint->sp_offset;
1018                 insn->state.type = hint->type;
1019         }
1020
1021         return 0;
1022 }
1023
1024 static int decode_sections(struct objtool_file *file)
1025 {
1026         int ret;
1027
1028         ret = decode_instructions(file);
1029         if (ret)
1030                 return ret;
1031
1032         ret = add_dead_ends(file);
1033         if (ret)
1034                 return ret;
1035
1036         add_ignores(file);
1037
1038         ret = add_jump_destinations(file);
1039         if (ret)
1040                 return ret;
1041
1042         ret = add_call_destinations(file);
1043         if (ret)
1044                 return ret;
1045
1046         ret = add_special_section_alts(file);
1047         if (ret)
1048                 return ret;
1049
1050         ret = add_switch_table_alts(file);
1051         if (ret)
1052                 return ret;
1053
1054         ret = read_unwind_hints(file);
1055         if (ret)
1056                 return ret;
1057
1058         return 0;
1059 }
1060
1061 static bool is_fentry_call(struct instruction *insn)
1062 {
1063         if (insn->type == INSN_CALL &&
1064             insn->call_dest->type == STT_NOTYPE &&
1065             !strcmp(insn->call_dest->name, "__fentry__"))
1066                 return true;
1067
1068         return false;
1069 }
1070
1071 static bool has_modified_stack_frame(struct insn_state *state)
1072 {
1073         int i;
1074
1075         if (state->cfa.base != initial_func_cfi.cfa.base ||
1076             state->cfa.offset != initial_func_cfi.cfa.offset ||
1077             state->stack_size != initial_func_cfi.cfa.offset ||
1078             state->drap)
1079                 return true;
1080
1081         for (i = 0; i < CFI_NUM_REGS; i++)
1082                 if (state->regs[i].base != initial_func_cfi.regs[i].base ||
1083                     state->regs[i].offset != initial_func_cfi.regs[i].offset)
1084                         return true;
1085
1086         return false;
1087 }
1088
1089 static bool has_valid_stack_frame(struct insn_state *state)
1090 {
1091         if (state->cfa.base == CFI_BP && state->regs[CFI_BP].base == CFI_CFA &&
1092             state->regs[CFI_BP].offset == -16)
1093                 return true;
1094
1095         if (state->drap && state->regs[CFI_BP].base == CFI_BP)
1096                 return true;
1097
1098         return false;
1099 }
1100
1101 static int update_insn_state_regs(struct instruction *insn, struct insn_state *state)
1102 {
1103         struct cfi_reg *cfa = &state->cfa;
1104         struct stack_op *op = &insn->stack_op;
1105
1106         if (cfa->base != CFI_SP)
1107                 return 0;
1108
1109         /* push */
1110         if (op->dest.type == OP_DEST_PUSH)
1111                 cfa->offset += 8;
1112
1113         /* pop */
1114         if (op->src.type == OP_SRC_POP)
1115                 cfa->offset -= 8;
1116
1117         /* add immediate to sp */
1118         if (op->dest.type == OP_DEST_REG && op->src.type == OP_SRC_ADD &&
1119             op->dest.reg == CFI_SP && op->src.reg == CFI_SP)
1120                 cfa->offset -= op->src.offset;
1121
1122         return 0;
1123 }
1124
1125 static void save_reg(struct insn_state *state, unsigned char reg, int base,
1126                      int offset)
1127 {
1128         if (arch_callee_saved_reg(reg) &&
1129             state->regs[reg].base == CFI_UNDEFINED) {
1130                 state->regs[reg].base = base;
1131                 state->regs[reg].offset = offset;
1132         }
1133 }
1134
1135 static void restore_reg(struct insn_state *state, unsigned char reg)
1136 {
1137         state->regs[reg].base = CFI_UNDEFINED;
1138         state->regs[reg].offset = 0;
1139 }
1140
1141 /*
1142  * A note about DRAP stack alignment:
1143  *
1144  * GCC has the concept of a DRAP register, which is used to help keep track of
1145  * the stack pointer when aligning the stack.  r10 or r13 is used as the DRAP
1146  * register.  The typical DRAP pattern is:
1147  *
1148  *   4c 8d 54 24 08             lea    0x8(%rsp),%r10
1149  *   48 83 e4 c0                and    $0xffffffffffffffc0,%rsp
1150  *   41 ff 72 f8                pushq  -0x8(%r10)
1151  *   55                         push   %rbp
1152  *   48 89 e5                   mov    %rsp,%rbp
1153  *                              (more pushes)
1154  *   41 52                      push   %r10
1155  *                              ...
1156  *   41 5a                      pop    %r10
1157  *                              (more pops)
1158  *   5d                         pop    %rbp
1159  *   49 8d 62 f8                lea    -0x8(%r10),%rsp
1160  *   c3                         retq
1161  *
1162  * There are some variations in the epilogues, like:
1163  *
1164  *   5b                         pop    %rbx
1165  *   41 5a                      pop    %r10
1166  *   41 5c                      pop    %r12
1167  *   41 5d                      pop    %r13
1168  *   41 5e                      pop    %r14
1169  *   c9                         leaveq
1170  *   49 8d 62 f8                lea    -0x8(%r10),%rsp
1171  *   c3                         retq
1172  *
1173  * and:
1174  *
1175  *   4c 8b 55 e8                mov    -0x18(%rbp),%r10
1176  *   48 8b 5d e0                mov    -0x20(%rbp),%rbx
1177  *   4c 8b 65 f0                mov    -0x10(%rbp),%r12
1178  *   4c 8b 6d f8                mov    -0x8(%rbp),%r13
1179  *   c9                         leaveq
1180  *   49 8d 62 f8                lea    -0x8(%r10),%rsp
1181  *   c3                         retq
1182  *
1183  * Sometimes r13 is used as the DRAP register, in which case it's saved and
1184  * restored beforehand:
1185  *
1186  *   41 55                      push   %r13
1187  *   4c 8d 6c 24 10             lea    0x10(%rsp),%r13
1188  *   48 83 e4 f0                and    $0xfffffffffffffff0,%rsp
1189  *                              ...
1190  *   49 8d 65 f0                lea    -0x10(%r13),%rsp
1191  *   41 5d                      pop    %r13
1192  *   c3                         retq
1193  */
1194 static int update_insn_state(struct instruction *insn, struct insn_state *state)
1195 {
1196         struct stack_op *op = &insn->stack_op;
1197         struct cfi_reg *cfa = &state->cfa;
1198         struct cfi_reg *regs = state->regs;
1199
1200         /* stack operations don't make sense with an undefined CFA */
1201         if (cfa->base == CFI_UNDEFINED) {
1202                 if (insn->func) {
1203                         WARN_FUNC("undefined stack state", insn->sec, insn->offset);
1204                         return -1;
1205                 }
1206                 return 0;
1207         }
1208
1209         if (state->type == ORC_TYPE_REGS || state->type == ORC_TYPE_REGS_IRET)
1210                 return update_insn_state_regs(insn, state);
1211
1212         switch (op->dest.type) {
1213
1214         case OP_DEST_REG:
1215                 switch (op->src.type) {
1216
1217                 case OP_SRC_REG:
1218                         if (op->src.reg == CFI_SP && op->dest.reg == CFI_BP &&
1219                             cfa->base == CFI_SP &&
1220                             regs[CFI_BP].base == CFI_CFA &&
1221                             regs[CFI_BP].offset == -cfa->offset) {
1222
1223                                 /* mov %rsp, %rbp */
1224                                 cfa->base = op->dest.reg;
1225                                 state->bp_scratch = false;
1226                         }
1227
1228                         else if (op->src.reg == CFI_SP &&
1229                                  op->dest.reg == CFI_BP && state->drap) {
1230
1231                                 /* drap: mov %rsp, %rbp */
1232                                 regs[CFI_BP].base = CFI_BP;
1233                                 regs[CFI_BP].offset = -state->stack_size;
1234                                 state->bp_scratch = false;
1235                         }
1236
1237                         else if (op->src.reg == CFI_SP && cfa->base == CFI_SP) {
1238
1239                                 /*
1240                                  * mov %rsp, %reg
1241                                  *
1242                                  * This is needed for the rare case where GCC
1243                                  * does:
1244                                  *
1245                                  *   mov    %rsp, %rax
1246                                  *   ...
1247                                  *   mov    %rax, %rsp
1248                                  */
1249                                 state->vals[op->dest.reg].base = CFI_CFA;
1250                                 state->vals[op->dest.reg].offset = -state->stack_size;
1251                         }
1252
1253                         else if (op->dest.reg == cfa->base) {
1254
1255                                 /* mov %reg, %rsp */
1256                                 if (cfa->base == CFI_SP &&
1257                                     state->vals[op->src.reg].base == CFI_CFA) {
1258
1259                                         /*
1260                                          * This is needed for the rare case
1261                                          * where GCC does something dumb like:
1262                                          *
1263                                          *   lea    0x8(%rsp), %rcx
1264                                          *   ...
1265                                          *   mov    %rcx, %rsp
1266                                          */
1267                                         cfa->offset = -state->vals[op->src.reg].offset;
1268                                         state->stack_size = cfa->offset;
1269
1270                                 } else {
1271                                         cfa->base = CFI_UNDEFINED;
1272                                         cfa->offset = 0;
1273                                 }
1274                         }
1275
1276                         break;
1277
1278                 case OP_SRC_ADD:
1279                         if (op->dest.reg == CFI_SP && op->src.reg == CFI_SP) {
1280
1281                                 /* add imm, %rsp */
1282                                 state->stack_size -= op->src.offset;
1283                                 if (cfa->base == CFI_SP)
1284                                         cfa->offset -= op->src.offset;
1285                                 break;
1286                         }
1287
1288                         if (op->dest.reg == CFI_SP && op->src.reg == CFI_BP) {
1289
1290                                 /* lea disp(%rbp), %rsp */
1291                                 state->stack_size = -(op->src.offset + regs[CFI_BP].offset);
1292                                 break;
1293                         }
1294
1295                         if (op->src.reg == CFI_SP && cfa->base == CFI_SP) {
1296
1297                                 /* drap: lea disp(%rsp), %drap */
1298                                 state->drap_reg = op->dest.reg;
1299
1300                                 /*
1301                                  * lea disp(%rsp), %reg
1302                                  *
1303                                  * This is needed for the rare case where GCC
1304                                  * does something dumb like:
1305                                  *
1306                                  *   lea    0x8(%rsp), %rcx
1307                                  *   ...
1308                                  *   mov    %rcx, %rsp
1309                                  */
1310                                 state->vals[op->dest.reg].base = CFI_CFA;
1311                                 state->vals[op->dest.reg].offset = \
1312                                         -state->stack_size + op->src.offset;
1313
1314                                 break;
1315                         }
1316
1317                         if (state->drap && op->dest.reg == CFI_SP &&
1318                             op->src.reg == state->drap_reg) {
1319
1320                                  /* drap: lea disp(%drap), %rsp */
1321                                 cfa->base = CFI_SP;
1322                                 cfa->offset = state->stack_size = -op->src.offset;
1323                                 state->drap_reg = CFI_UNDEFINED;
1324                                 state->drap = false;
1325                                 break;
1326                         }
1327
1328                         if (op->dest.reg == state->cfa.base) {
1329                                 WARN_FUNC("unsupported stack register modification",
1330                                           insn->sec, insn->offset);
1331                                 return -1;
1332                         }
1333
1334                         break;
1335
1336                 case OP_SRC_AND:
1337                         if (op->dest.reg != CFI_SP ||
1338                             (state->drap_reg != CFI_UNDEFINED && cfa->base != CFI_SP) ||
1339                             (state->drap_reg == CFI_UNDEFINED && cfa->base != CFI_BP)) {
1340                                 WARN_FUNC("unsupported stack pointer realignment",
1341                                           insn->sec, insn->offset);
1342                                 return -1;
1343                         }
1344
1345                         if (state->drap_reg != CFI_UNDEFINED) {
1346                                 /* drap: and imm, %rsp */
1347                                 cfa->base = state->drap_reg;
1348                                 cfa->offset = state->stack_size = 0;
1349                                 state->drap = true;
1350                         }
1351
1352                         /*
1353                          * Older versions of GCC (4.8ish) realign the stack
1354                          * without DRAP, with a frame pointer.
1355                          */
1356
1357                         break;
1358
1359                 case OP_SRC_POP:
1360                         if (!state->drap && op->dest.type == OP_DEST_REG &&
1361                             op->dest.reg == cfa->base) {
1362
1363                                 /* pop %rbp */
1364                                 cfa->base = CFI_SP;
1365                         }
1366
1367                         if (state->drap && cfa->base == CFI_BP_INDIRECT &&
1368                             op->dest.type == OP_DEST_REG &&
1369                             op->dest.reg == state->drap_reg &&
1370                             state->drap_offset == -state->stack_size) {
1371
1372                                 /* drap: pop %drap */
1373                                 cfa->base = state->drap_reg;
1374                                 cfa->offset = 0;
1375                                 state->drap_offset = -1;
1376
1377                         } else if (regs[op->dest.reg].offset == -state->stack_size) {
1378
1379                                 /* pop %reg */
1380                                 restore_reg(state, op->dest.reg);
1381                         }
1382
1383                         state->stack_size -= 8;
1384                         if (cfa->base == CFI_SP)
1385                                 cfa->offset -= 8;
1386
1387                         break;
1388
1389                 case OP_SRC_REG_INDIRECT:
1390                         if (state->drap && op->src.reg == CFI_BP &&
1391                             op->src.offset == state->drap_offset) {
1392
1393                                 /* drap: mov disp(%rbp), %drap */
1394                                 cfa->base = state->drap_reg;
1395                                 cfa->offset = 0;
1396                                 state->drap_offset = -1;
1397                         }
1398
1399                         if (state->drap && op->src.reg == CFI_BP &&
1400                             op->src.offset == regs[op->dest.reg].offset) {
1401
1402                                 /* drap: mov disp(%rbp), %reg */
1403                                 restore_reg(state, op->dest.reg);
1404
1405                         } else if (op->src.reg == cfa->base &&
1406                             op->src.offset == regs[op->dest.reg].offset + cfa->offset) {
1407
1408                                 /* mov disp(%rbp), %reg */
1409                                 /* mov disp(%rsp), %reg */
1410                                 restore_reg(state, op->dest.reg);
1411                         }
1412
1413                         break;
1414
1415                 default:
1416                         WARN_FUNC("unknown stack-related instruction",
1417                                   insn->sec, insn->offset);
1418                         return -1;
1419                 }
1420
1421                 break;
1422
1423         case OP_DEST_PUSH:
1424                 state->stack_size += 8;
1425                 if (cfa->base == CFI_SP)
1426                         cfa->offset += 8;
1427
1428                 if (op->src.type != OP_SRC_REG)
1429                         break;
1430
1431                 if (state->drap) {
1432                         if (op->src.reg == cfa->base && op->src.reg == state->drap_reg) {
1433
1434                                 /* drap: push %drap */
1435                                 cfa->base = CFI_BP_INDIRECT;
1436                                 cfa->offset = -state->stack_size;
1437
1438                                 /* save drap so we know when to restore it */
1439                                 state->drap_offset = -state->stack_size;
1440
1441                         } else if (op->src.reg == CFI_BP && cfa->base == state->drap_reg) {
1442
1443                                 /* drap: push %rbp */
1444                                 state->stack_size = 0;
1445
1446                         } else if (regs[op->src.reg].base == CFI_UNDEFINED) {
1447
1448                                 /* drap: push %reg */
1449                                 save_reg(state, op->src.reg, CFI_BP, -state->stack_size);
1450                         }
1451
1452                 } else {
1453
1454                         /* push %reg */
1455                         save_reg(state, op->src.reg, CFI_CFA, -state->stack_size);
1456                 }
1457
1458                 /* detect when asm code uses rbp as a scratch register */
1459                 if (!no_fp && insn->func && op->src.reg == CFI_BP &&
1460                     cfa->base != CFI_BP)
1461                         state->bp_scratch = true;
1462                 break;
1463
1464         case OP_DEST_REG_INDIRECT:
1465
1466                 if (state->drap) {
1467                         if (op->src.reg == cfa->base && op->src.reg == state->drap_reg) {
1468
1469                                 /* drap: mov %drap, disp(%rbp) */
1470                                 cfa->base = CFI_BP_INDIRECT;
1471                                 cfa->offset = op->dest.offset;
1472
1473                                 /* save drap offset so we know when to restore it */
1474                                 state->drap_offset = op->dest.offset;
1475                         }
1476
1477                         else if (regs[op->src.reg].base == CFI_UNDEFINED) {
1478
1479                                 /* drap: mov reg, disp(%rbp) */
1480                                 save_reg(state, op->src.reg, CFI_BP, op->dest.offset);
1481                         }
1482
1483                 } else if (op->dest.reg == cfa->base) {
1484
1485                         /* mov reg, disp(%rbp) */
1486                         /* mov reg, disp(%rsp) */
1487                         save_reg(state, op->src.reg, CFI_CFA,
1488                                  op->dest.offset - state->cfa.offset);
1489                 }
1490
1491                 break;
1492
1493         case OP_DEST_LEAVE:
1494                 if ((!state->drap && cfa->base != CFI_BP) ||
1495                     (state->drap && cfa->base != state->drap_reg)) {
1496                         WARN_FUNC("leave instruction with modified stack frame",
1497                                   insn->sec, insn->offset);
1498                         return -1;
1499                 }
1500
1501                 /* leave (mov %rbp, %rsp; pop %rbp) */
1502
1503                 state->stack_size = -state->regs[CFI_BP].offset - 8;
1504                 restore_reg(state, CFI_BP);
1505
1506                 if (!state->drap) {
1507                         cfa->base = CFI_SP;
1508                         cfa->offset -= 8;
1509                 }
1510
1511                 break;
1512
1513         case OP_DEST_MEM:
1514                 if (op->src.type != OP_SRC_POP) {
1515                         WARN_FUNC("unknown stack-related memory operation",
1516                                   insn->sec, insn->offset);
1517                         return -1;
1518                 }
1519
1520                 /* pop mem */
1521                 state->stack_size -= 8;
1522                 if (cfa->base == CFI_SP)
1523                         cfa->offset -= 8;
1524
1525                 break;
1526
1527         default:
1528                 WARN_FUNC("unknown stack-related instruction",
1529                           insn->sec, insn->offset);
1530                 return -1;
1531         }
1532
1533         return 0;
1534 }
1535
1536 static bool insn_state_match(struct instruction *insn, struct insn_state *state)
1537 {
1538         struct insn_state *state1 = &insn->state, *state2 = state;
1539         int i;
1540
1541         if (memcmp(&state1->cfa, &state2->cfa, sizeof(state1->cfa))) {
1542                 WARN_FUNC("stack state mismatch: cfa1=%d%+d cfa2=%d%+d",
1543                           insn->sec, insn->offset,
1544                           state1->cfa.base, state1->cfa.offset,
1545                           state2->cfa.base, state2->cfa.offset);
1546
1547         } else if (memcmp(&state1->regs, &state2->regs, sizeof(state1->regs))) {
1548                 for (i = 0; i < CFI_NUM_REGS; i++) {
1549                         if (!memcmp(&state1->regs[i], &state2->regs[i],
1550                                     sizeof(struct cfi_reg)))
1551                                 continue;
1552
1553                         WARN_FUNC("stack state mismatch: reg1[%d]=%d%+d reg2[%d]=%d%+d",
1554                                   insn->sec, insn->offset,
1555                                   i, state1->regs[i].base, state1->regs[i].offset,
1556                                   i, state2->regs[i].base, state2->regs[i].offset);
1557                         break;
1558                 }
1559
1560         } else if (state1->type != state2->type) {
1561                 WARN_FUNC("stack state mismatch: type1=%d type2=%d",
1562                           insn->sec, insn->offset, state1->type, state2->type);
1563
1564         } else if (state1->drap != state2->drap ||
1565                  (state1->drap && state1->drap_reg != state2->drap_reg) ||
1566                  (state1->drap && state1->drap_offset != state2->drap_offset)) {
1567                 WARN_FUNC("stack state mismatch: drap1=%d(%d,%d) drap2=%d(%d,%d)",
1568                           insn->sec, insn->offset,
1569                           state1->drap, state1->drap_reg, state1->drap_offset,
1570                           state2->drap, state2->drap_reg, state2->drap_offset);
1571
1572         } else
1573                 return true;
1574
1575         return false;
1576 }
1577
1578 /*
1579  * Follow the branch starting at the given instruction, and recursively follow
1580  * any other branches (jumps).  Meanwhile, track the frame pointer state at
1581  * each instruction and validate all the rules described in
1582  * tools/objtool/Documentation/stack-validation.txt.
1583  */
1584 static int validate_branch(struct objtool_file *file, struct instruction *first,
1585                            struct insn_state state)
1586 {
1587         struct alternative *alt;
1588         struct instruction *insn, *next_insn;
1589         struct section *sec;
1590         struct symbol *func = NULL;
1591         int ret;
1592
1593         insn = first;
1594         sec = insn->sec;
1595
1596         if (insn->alt_group && list_empty(&insn->alts)) {
1597                 WARN_FUNC("don't know how to handle branch to middle of alternative instruction group",
1598                           sec, insn->offset);
1599                 return 1;
1600         }
1601
1602         while (1) {
1603                 next_insn = next_insn_same_sec(file, insn);
1604
1605
1606                 if (file->c_file && func && insn->func && func != insn->func) {
1607                         WARN("%s() falls through to next function %s()",
1608                              func->name, insn->func->name);
1609                         return 1;
1610                 }
1611
1612                 if (insn->func)
1613                         func = insn->func;
1614
1615                 if (func && insn->ignore) {
1616                         WARN_FUNC("BUG: why am I validating an ignored function?",
1617                                   sec, insn->offset);
1618                         return 1;
1619                 }
1620
1621                 if (insn->visited) {
1622                         if (!insn->hint && !insn_state_match(insn, &state))
1623                                 return 1;
1624
1625                         return 0;
1626                 }
1627
1628                 if (insn->hint) {
1629                         if (insn->restore) {
1630                                 struct instruction *save_insn, *i;
1631
1632                                 i = insn;
1633                                 save_insn = NULL;
1634                                 func_for_each_insn_continue_reverse(file, func, i) {
1635                                         if (i->save) {
1636                                                 save_insn = i;
1637                                                 break;
1638                                         }
1639                                 }
1640
1641                                 if (!save_insn) {
1642                                         WARN_FUNC("no corresponding CFI save for CFI restore",
1643                                                   sec, insn->offset);
1644                                         return 1;
1645                                 }
1646
1647                                 if (!save_insn->visited) {
1648                                         /*
1649                                          * Oops, no state to copy yet.
1650                                          * Hopefully we can reach this
1651                                          * instruction from another branch
1652                                          * after the save insn has been
1653                                          * visited.
1654                                          */
1655                                         if (insn == first)
1656                                                 return 0;
1657
1658                                         WARN_FUNC("objtool isn't smart enough to handle this CFI save/restore combo",
1659                                                   sec, insn->offset);
1660                                         return 1;
1661                                 }
1662
1663                                 insn->state = save_insn->state;
1664                         }
1665
1666                         state = insn->state;
1667
1668                 } else
1669                         insn->state = state;
1670
1671                 insn->visited = true;
1672
1673                 list_for_each_entry(alt, &insn->alts, list) {
1674                         ret = validate_branch(file, alt->insn, state);
1675                         if (ret)
1676                                 return 1;
1677                 }
1678
1679                 switch (insn->type) {
1680
1681                 case INSN_RETURN:
1682                         if (func && has_modified_stack_frame(&state)) {
1683                                 WARN_FUNC("return with modified stack frame",
1684                                           sec, insn->offset);
1685                                 return 1;
1686                         }
1687
1688                         if (state.bp_scratch) {
1689                                 WARN("%s uses BP as a scratch register",
1690                                      insn->func->name);
1691                                 return 1;
1692                         }
1693
1694                         return 0;
1695
1696                 case INSN_CALL:
1697                         if (is_fentry_call(insn))
1698                                 break;
1699
1700                         ret = dead_end_function(file, insn->call_dest);
1701                         if (ret == 1)
1702                                 return 0;
1703                         if (ret == -1)
1704                                 return 1;
1705
1706                         /* fallthrough */
1707                 case INSN_CALL_DYNAMIC:
1708                         if (!no_fp && func && !has_valid_stack_frame(&state)) {
1709                                 WARN_FUNC("call without frame pointer save/setup",
1710                                           sec, insn->offset);
1711                                 return 1;
1712                         }
1713                         break;
1714
1715                 case INSN_JUMP_CONDITIONAL:
1716                 case INSN_JUMP_UNCONDITIONAL:
1717                         if (insn->jump_dest &&
1718                             (!func || !insn->jump_dest->func ||
1719                              func == insn->jump_dest->func)) {
1720                                 ret = validate_branch(file, insn->jump_dest,
1721                                                       state);
1722                                 if (ret)
1723                                         return 1;
1724
1725                         } else if (func && has_modified_stack_frame(&state)) {
1726                                 WARN_FUNC("sibling call from callable instruction with modified stack frame",
1727                                           sec, insn->offset);
1728                                 return 1;
1729                         }
1730
1731                         if (insn->type == INSN_JUMP_UNCONDITIONAL)
1732                                 return 0;
1733
1734                         break;
1735
1736                 case INSN_JUMP_DYNAMIC:
1737                         if (func && list_empty(&insn->alts) &&
1738                             has_modified_stack_frame(&state)) {
1739                                 WARN_FUNC("sibling call from callable instruction with modified stack frame",
1740                                           sec, insn->offset);
1741                                 return 1;
1742                         }
1743
1744                         return 0;
1745
1746                 case INSN_CONTEXT_SWITCH:
1747                         if (func && (!next_insn || !next_insn->hint)) {
1748                                 WARN_FUNC("unsupported instruction in callable function",
1749                                           sec, insn->offset);
1750                                 return 1;
1751                         }
1752                         return 0;
1753
1754                 case INSN_STACK:
1755                         if (update_insn_state(insn, &state))
1756                                 return 1;
1757
1758                         break;
1759
1760                 default:
1761                         break;
1762                 }
1763
1764                 if (insn->dead_end)
1765                         return 0;
1766
1767                 if (!next_insn) {
1768                         if (state.cfa.base == CFI_UNDEFINED)
1769                                 return 0;
1770                         WARN("%s: unexpected end of section", sec->name);
1771                         return 1;
1772                 }
1773
1774                 insn = next_insn;
1775         }
1776
1777         return 0;
1778 }
1779
1780 static int validate_unwind_hints(struct objtool_file *file)
1781 {
1782         struct instruction *insn;
1783         int ret, warnings = 0;
1784         struct insn_state state;
1785
1786         if (!file->hints)
1787                 return 0;
1788
1789         clear_insn_state(&state);
1790
1791         for_each_insn(file, insn) {
1792                 if (insn->hint && !insn->visited) {
1793                         ret = validate_branch(file, insn, state);
1794                         warnings += ret;
1795                 }
1796         }
1797
1798         return warnings;
1799 }
1800
1801 static bool is_kasan_insn(struct instruction *insn)
1802 {
1803         return (insn->type == INSN_CALL &&
1804                 !strcmp(insn->call_dest->name, "__asan_handle_no_return"));
1805 }
1806
1807 static bool is_ubsan_insn(struct instruction *insn)
1808 {
1809         return (insn->type == INSN_CALL &&
1810                 !strcmp(insn->call_dest->name,
1811                         "__ubsan_handle_builtin_unreachable"));
1812 }
1813
1814 static bool ignore_unreachable_insn(struct instruction *insn)
1815 {
1816         int i;
1817
1818         if (insn->ignore || insn->type == INSN_NOP)
1819                 return true;
1820
1821         /*
1822          * Ignore any unused exceptions.  This can happen when a whitelisted
1823          * function has an exception table entry.
1824          *
1825          * Also ignore alternative replacement instructions.  This can happen
1826          * when a whitelisted function uses one of the ALTERNATIVE macros.
1827          */
1828         if (!strcmp(insn->sec->name, ".fixup") ||
1829             !strcmp(insn->sec->name, ".altinstr_replacement") ||
1830             !strcmp(insn->sec->name, ".altinstr_aux"))
1831                 return true;
1832
1833         /*
1834          * Check if this (or a subsequent) instruction is related to
1835          * CONFIG_UBSAN or CONFIG_KASAN.
1836          *
1837          * End the search at 5 instructions to avoid going into the weeds.
1838          */
1839         if (!insn->func)
1840                 return false;
1841         for (i = 0; i < 5; i++) {
1842
1843                 if (is_kasan_insn(insn) || is_ubsan_insn(insn))
1844                         return true;
1845
1846                 if (insn->type == INSN_JUMP_UNCONDITIONAL && insn->jump_dest) {
1847                         insn = insn->jump_dest;
1848                         continue;
1849                 }
1850
1851                 if (insn->offset + insn->len >= insn->func->offset + insn->func->len)
1852                         break;
1853                 insn = list_next_entry(insn, list);
1854         }
1855
1856         return false;
1857 }
1858
1859 static int validate_functions(struct objtool_file *file)
1860 {
1861         struct section *sec;
1862         struct symbol *func;
1863         struct instruction *insn;
1864         struct insn_state state;
1865         int ret, warnings = 0;
1866
1867         clear_insn_state(&state);
1868
1869         state.cfa = initial_func_cfi.cfa;
1870         memcpy(&state.regs, &initial_func_cfi.regs,
1871                CFI_NUM_REGS * sizeof(struct cfi_reg));
1872         state.stack_size = initial_func_cfi.cfa.offset;
1873
1874         for_each_sec(file, sec) {
1875                 list_for_each_entry(func, &sec->symbol_list, list) {
1876                         if (func->type != STT_FUNC)
1877                                 continue;
1878
1879                         insn = find_insn(file, sec, func->offset);
1880                         if (!insn || insn->ignore)
1881                                 continue;
1882
1883                         ret = validate_branch(file, insn, state);
1884                         warnings += ret;
1885                 }
1886         }
1887
1888         return warnings;
1889 }
1890
1891 static int validate_reachable_instructions(struct objtool_file *file)
1892 {
1893         struct instruction *insn;
1894
1895         if (file->ignore_unreachables)
1896                 return 0;
1897
1898         for_each_insn(file, insn) {
1899                 if (insn->visited || ignore_unreachable_insn(insn))
1900                         continue;
1901
1902                 WARN_FUNC("unreachable instruction", insn->sec, insn->offset);
1903                 return 1;
1904         }
1905
1906         return 0;
1907 }
1908
1909 static void cleanup(struct objtool_file *file)
1910 {
1911         struct instruction *insn, *tmpinsn;
1912         struct alternative *alt, *tmpalt;
1913
1914         list_for_each_entry_safe(insn, tmpinsn, &file->insn_list, list) {
1915                 list_for_each_entry_safe(alt, tmpalt, &insn->alts, list) {
1916                         list_del(&alt->list);
1917                         free(alt);
1918                 }
1919                 list_del(&insn->list);
1920                 hash_del(&insn->hash);
1921                 free(insn);
1922         }
1923         elf_close(file->elf);
1924 }
1925
1926 int check(const char *_objname, bool _no_fp, bool no_unreachable, bool orc)
1927 {
1928         struct objtool_file file;
1929         int ret, warnings = 0;
1930
1931         objname = _objname;
1932         no_fp = _no_fp;
1933
1934         file.elf = elf_open(objname, orc ? O_RDWR : O_RDONLY);
1935         if (!file.elf)
1936                 return 1;
1937
1938         INIT_LIST_HEAD(&file.insn_list);
1939         hash_init(file.insn_hash);
1940         file.whitelist = find_section_by_name(file.elf, ".discard.func_stack_frame_non_standard");
1941         file.rodata = find_section_by_name(file.elf, ".rodata");
1942         file.c_file = find_section_by_name(file.elf, ".comment");
1943         file.ignore_unreachables = no_unreachable;
1944         file.hints = false;
1945
1946         arch_initial_func_cfi_state(&initial_func_cfi);
1947
1948         ret = decode_sections(&file);
1949         if (ret < 0)
1950                 goto out;
1951         warnings += ret;
1952
1953         if (list_empty(&file.insn_list))
1954                 goto out;
1955
1956         ret = validate_functions(&file);
1957         if (ret < 0)
1958                 goto out;
1959         warnings += ret;
1960
1961         ret = validate_unwind_hints(&file);
1962         if (ret < 0)
1963                 goto out;
1964         warnings += ret;
1965
1966         if (!warnings) {
1967                 ret = validate_reachable_instructions(&file);
1968                 if (ret < 0)
1969                         goto out;
1970                 warnings += ret;
1971         }
1972
1973         if (orc) {
1974                 ret = create_orc(&file);
1975                 if (ret < 0)
1976                         goto out;
1977
1978                 ret = create_orc_sections(&file);
1979                 if (ret < 0)
1980                         goto out;
1981
1982                 ret = elf_write(file.elf);
1983                 if (ret < 0)
1984                         goto out;
1985         }
1986
1987 out:
1988         cleanup(&file);
1989
1990         /* ignore warnings for now until we get all the code cleaned up */
1991         if (ret || warnings)
1992                 return 0;
1993         return 0;
1994 }