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