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