1	//===- bolt/Rewrite/LinuxKernelRewriter.cpp -------------------------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// Support for updating Linux Kernel metadata.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "bolt/Core/BinaryFunction.h"
14	#include "bolt/Rewrite/MetadataRewriter.h"
15	#include "bolt/Rewrite/MetadataRewriters.h"
16	#include "bolt/Utils/CommandLineOpts.h"
17	#include "llvm/ADT/ArrayRef.h"
18	#include "llvm/ADT/DenseSet.h"
19	#include "llvm/MC/MCDisassembler/MCDisassembler.h"
20	#include "llvm/Support/BinaryStreamWriter.h"
21	#include "llvm/Support/CommandLine.h"
22	#include "llvm/Support/Debug.h"
23	#include "llvm/Support/Errc.h"
24	#include "llvm/Support/ErrorOr.h"
25	#include <regex>
26
27	#define DEBUG_TYPE "bolt-linux"
28
29	using namespace llvm;
30	using namespace bolt;
31
32	namespace opts {
33
34	static cl::opt<bool>
35	AltInstHasPadLen("alt-inst-has-padlen",
36	cl::desc("specify that .altinstructions has padlen field"),
37	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
38
39	static cl::opt<uint32_t>
40	AltInstFeatureSize("alt-inst-feature-size",
41	cl::desc("size of feature field in .altinstructions"),
42	cl::init(Val: 2), cl::Hidden, cl::cat(BoltCategory));
43
44	static cl::opt<bool>
45	DumpAltInstructions("dump-alt-instructions",
46	cl::desc("dump Linux alternative instructions info"),
47	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
48
49	static cl::opt<bool>
50	DumpExceptions("dump-linux-exceptions",
51	cl::desc("dump Linux kernel exception table"),
52	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
53
54	static cl::opt<bool>
55	DumpORC("dump-orc", cl::desc("dump raw ORC unwind information (sorted)"),
56	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
57
58	static cl::opt<bool> DumpParavirtualPatchSites(
59	"dump-para-sites", cl::desc("dump Linux kernel paravitual patch sites"),
60	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
61
62	static cl::opt<bool>
63	DumpPCIFixups("dump-pci-fixups",
64	cl::desc("dump Linux kernel PCI fixup table"),
65	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
66
67	static cl::opt<bool> DumpSMPLocks("dump-smp-locks",
68	cl::desc("dump Linux kernel SMP locks"),
69	cl::init(Val: false), cl::Hidden,
70	cl::cat(BoltCategory));
71
72	static cl::opt<bool> DumpStaticCalls("dump-static-calls",
73	cl::desc("dump Linux kernel static calls"),
74	cl::init(Val: false), cl::Hidden,
75	cl::cat(BoltCategory));
76
77	static cl::opt<bool>
78	DumpStaticKeys("dump-static-keys",
79	cl::desc("dump Linux kernel static keys jump table"),
80	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
81
82	static cl::opt<bool> LongJumpLabels(
83	"long-jump-labels",
84	cl::desc("always use long jumps/nops for Linux kernel static keys"),
85	cl::init(Val: false), cl::Hidden, cl::cat(BoltCategory));
86
87	static cl::opt<bool>
88	PrintORC("print-orc",
89	cl::desc("print ORC unwind information for instructions"),
90	cl::init(Val: true), cl::Hidden, cl::cat(BoltCategory));
91
92	} // namespace opts
93
94	/// Linux kernel version
95	struct LKVersion {
96	LKVersion() {}
97	LKVersion(unsigned Major, unsigned Minor, unsigned Rev)
98	: Major(Major), Minor(Minor), Rev(Rev) {}
99
100	bool operator<(const LKVersion &Other) const {
101	return std::make_tuple(args: Major, args: Minor, args: Rev) <
102	std::make_tuple(args: Other.Major, args: Other.Minor, args: Other.Rev);
103	}
104
105	bool operator>(const LKVersion &Other) const { return Other < *this; }
106
107	bool operator<=(const LKVersion &Other) const { return !(*this > Other); }
108
109	bool operator>=(const LKVersion &Other) const { return !(*this < Other); }
110
111	bool operator==(const LKVersion &Other) const {
112	return Major == Other.Major && Minor == Other.Minor && Rev == Other.Rev;
113	}
114
115	bool operator!=(const LKVersion &Other) const { return !(*this == Other); }
116
117	unsigned Major{0};
118	unsigned Minor{0};
119	unsigned Rev{0};
120	};
121
122	/// Linux Kernel supports stack unwinding using ORC (oops rewind capability).
123	/// ORC state at every IP can be described by the following data structure.
124	struct ORCState {
125	int16_t SPOffset;
126	int16_t BPOffset;
127	int16_t Info;
128
129	bool operator==(const ORCState &Other) const {
130	return SPOffset == Other.SPOffset && BPOffset == Other.BPOffset &&
131	Info == Other.Info;
132	}
133
134	bool operator!=(const ORCState &Other) const { return !(*this == Other); }
135	};
136
137	/// Section terminator ORC entry.
138	static ORCState NullORC = {.SPOffset: 0, .BPOffset: 0, .Info: 0};
139
140	/// Basic printer for ORC entry. It does not provide the same level of
141	/// information as objtool (for now).
142	inline raw_ostream &operator<<(raw_ostream &OS, const ORCState &E) {
143	if (!opts::PrintORC)
144	return OS;
145	if (E != NullORC)
146	OS << format(Fmt: "{sp: %d, bp: %d, info: 0x%x}", Vals: E.SPOffset, Vals: E.BPOffset,
147	Vals: E.Info);
148	else
149	OS << "{terminator}";
150
151	return OS;
152	}
153
154	namespace {
155
156	/// Extension to DataExtractor that supports reading addresses stored in
157	/// PC-relative format.
158	class AddressExtractor : public DataExtractor {
159	uint64_t DataAddress;
160
161	public:
162	AddressExtractor(StringRef Data, uint64_t DataAddress, bool IsLittleEndian,
163	uint8_t AddressSize)
164	: DataExtractor(Data, IsLittleEndian, AddressSize),
165	DataAddress(DataAddress) {}
166
167	/// Extract 32-bit PC-relative address/pointer.
168	uint64_t getPCRelAddress32(Cursor &C) {
169	const uint64_t Base = DataAddress + C.tell();
170	return Base + (int32_t)getU32(C);
171	}
172
173	/// Extract 64-bit PC-relative address/pointer.
174	uint64_t getPCRelAddress64(Cursor &C) {
175	const uint64_t Base = DataAddress + C.tell();
176	return Base + (int64_t)getU64(C);
177	}
178	};
179
180	class LinuxKernelRewriter final : public MetadataRewriter {
181	LKVersion LinuxKernelVersion;
182
183	/// Information required for updating metadata referencing an instruction.
184	struct InstructionFixup {
185	BinarySection &Section; // Section referencing the instruction.
186	uint64_t Offset; // Offset in the section above.
187	BinaryFunction &BF; // Function containing the instruction.
188	MCSymbol &Label; // Label marking the instruction.
189	bool IsPCRelative; // If the reference type is relative.
190	};
191	std::vector<InstructionFixup> Fixups;
192
193	/// Size of an entry in .smp_locks section.
194	static constexpr size_t SMP_LOCKS_ENTRY_SIZE = 4;
195
196	/// Linux ORC sections.
197	ErrorOr<BinarySection &> ORCUnwindSection = std::errc::bad_address;
198	ErrorOr<BinarySection &> ORCUnwindIPSection = std::errc::bad_address;
199
200	/// Size of entries in ORC sections.
201	static constexpr size_t ORC_UNWIND_ENTRY_SIZE = 6;
202	static constexpr size_t ORC_UNWIND_IP_ENTRY_SIZE = 4;
203
204	struct ORCListEntry {
205	uint64_t IP; /// Instruction address.
206	BinaryFunction *BF; /// Binary function corresponding to the entry.
207	ORCState ORC; /// Stack unwind info in ORC format.
208
209	/// ORC entries are sorted by their IPs. Terminator entries (NullORC)
210	/// should precede other entries with the same address.
211	bool operator<(const ORCListEntry &Other) const {
212	if (IP < Other.IP)
213	return 1;
214	if (IP > Other.IP)
215	return 0;
216	return ORC == NullORC && Other.ORC != NullORC;
217	}
218	};
219
220	using ORCListType = std::vector<ORCListEntry>;
221	ORCListType ORCEntries;
222
223	/// Number of entries in the input file ORC sections.
224	uint64_t NumORCEntries = 0;
225
226	/// Section containing static keys jump table.
227	ErrorOr<BinarySection &> StaticKeysJumpSection = std::errc::bad_address;
228	uint64_t StaticKeysJumpTableAddress = 0;
229	static constexpr size_t STATIC_KEYS_JUMP_ENTRY_SIZE = 8;
230
231	struct JumpInfoEntry {
232	bool Likely;
233	bool InitValue;
234	};
235	SmallVector<JumpInfoEntry, 16> JumpInfo;
236
237	/// Static key entries that need nop conversion.
238	DenseSet<uint32_t> NopIDs;
239
240	/// Section containing static call table.
241	ErrorOr<BinarySection &> StaticCallSection = std::errc::bad_address;
242	uint64_t StaticCallTableAddress = 0;
243	static constexpr size_t STATIC_CALL_ENTRY_SIZE = 8;
244
245	struct StaticCallInfo {
246	uint32_t ID; /// Identifier of the entry in the table.
247	BinaryFunction *Function; /// Function containing associated call.
248	MCSymbol *Label; /// Label attached to the call.
249	};
250	using StaticCallListType = std::vector<StaticCallInfo>;
251	StaticCallListType StaticCallEntries;
252
253	/// Section containing the Linux exception table.
254	ErrorOr<BinarySection &> ExceptionsSection = std::errc::bad_address;
255	static constexpr size_t EXCEPTION_TABLE_ENTRY_SIZE = 12;
256
257	/// Functions with exception handling code.
258	DenseSet<BinaryFunction *> FunctionsWithExceptions;
259
260	/// Section with paravirtual patch sites.
261	ErrorOr<BinarySection &> ParavirtualPatchSection = std::errc::bad_address;
262
263	/// Alignment of paravirtual patch structures.
264	static constexpr size_t PARA_PATCH_ALIGN = 8;
265
266	/// .altinstructions section.
267	ErrorOr<BinarySection &> AltInstrSection = std::errc::bad_address;
268
269	/// Section containing Linux bug table.
270	ErrorOr<BinarySection &> BugTableSection = std::errc::bad_address;
271
272	/// Size of bug_entry struct.
273	static constexpr size_t BUG_TABLE_ENTRY_SIZE = 12;
274
275	/// List of bug entries per function.
276	using FunctionBugListType =
277	DenseMap<BinaryFunction *, SmallVector<uint32_t, 2>>;
278	FunctionBugListType FunctionBugList;
279
280	/// .pci_fixup section.
281	ErrorOr<BinarySection &> PCIFixupSection = std::errc::bad_address;
282	static constexpr size_t PCI_FIXUP_ENTRY_SIZE = 16;
283
284	Error detectLinuxKernelVersion();
285
286	/// Process linux kernel special sections and their relocations.
287	void processLKSections();
288
289	/// Process __ksymtab and __ksymtab_gpl.
290	void processLKKSymtab(bool IsGPL = false);
291
292	// Create relocations in sections requiring fixups.
293	//
294	// Make sure functions that will not be emitted are marked as such before this
295	// function is executed.
296	void processInstructionFixups();
297
298	/// Process .smp_locks section.
299	Error processSMPLocks();
300
301	/// Read ORC unwind information and annotate instructions.
302	Error readORCTables();
303
304	/// Update ORC for functions once CFG is constructed.
305	Error processORCPostCFG();
306
307	/// Update ORC data in the binary.
308	Error rewriteORCTables();
309
310	/// Validate written ORC tables after binary emission.
311	Error validateORCTables();
312
313	/// Static call table handling.
314	Error readStaticCalls();
315	Error rewriteStaticCalls();
316
317	Error readExceptionTable();
318	Error rewriteExceptionTable();
319
320	/// Paravirtual instruction patch sites.
321	Error readParaInstructions();
322	Error rewriteParaInstructions();
323
324	/// __bug_table section handling.
325	Error readBugTable();
326	Error rewriteBugTable();
327
328	/// Do no process functions containing instruction annotated with
329	/// \p Annotation.
330	void skipFunctionsWithAnnotation(StringRef Annotation) const;
331
332	/// Handle alternative instruction info from .altinstructions.
333	Error readAltInstructions();
334	void processAltInstructionsPostCFG();
335	Error tryReadAltInstructions(uint32_t AltInstFeatureSize,
336	bool AltInstHasPadLen, bool ParseOnly);
337
338	/// Read .pci_fixup
339	Error readPCIFixupTable();
340
341	/// Handle static keys jump table.
342	Error readStaticKeysJumpTable();
343	Error rewriteStaticKeysJumpTable();
344	Error updateStaticKeysJumpTablePostEmit();
345
346	public:
347	LinuxKernelRewriter(BinaryContext &BC)
348	: MetadataRewriter("linux-kernel-rewriter", BC) {}
349
350	Error preCFGInitializer() override {
351	if (Error E = detectLinuxKernelVersion())
352	return E;
353
354	processLKSections();
355
356	if (Error E = processSMPLocks())
357	return E;
358
359	if (Error E = readStaticCalls())
360	return E;
361
362	if (Error E = readExceptionTable())
363	return E;
364
365	if (Error E = readParaInstructions())
366	return E;
367
368	if (Error E = readBugTable())
369	return E;
370
371	if (Error E = readAltInstructions())
372	return E;
373
374	// Some ORC entries could be linked to alternative instruction
375	// sequences. Hence, we read ORC after .altinstructions.
376	if (Error E = readORCTables())
377	return E;
378
379	if (Error E = readPCIFixupTable())
380	return E;
381
382	if (Error E = readStaticKeysJumpTable())
383	return E;
384
385	return Error::success();
386	}
387
388	Error postCFGInitializer() override {
389	if (Error E = processORCPostCFG())
390	return E;
391
392	processAltInstructionsPostCFG();
393
394	return Error::success();
395	}
396
397	Error preEmitFinalizer() override {
398	// Since rewriteExceptionTable() can mark functions as non-simple, run it
399	// before other rewriters that depend on simple/emit status.
400	if (Error E = rewriteExceptionTable())
401	return E;
402
403	if (Error E = rewriteParaInstructions())
404	return E;
405
406	if (Error E = rewriteORCTables())
407	return E;
408
409	if (Error E = rewriteStaticCalls())
410	return E;
411
412	if (Error E = rewriteStaticKeysJumpTable())
413	return E;
414
415	if (Error E = rewriteBugTable())
416	return E;
417
418	processInstructionFixups();
419
420	return Error::success();
421	}
422
423	Error postEmitFinalizer() override {
424	if (Error E = updateStaticKeysJumpTablePostEmit())
425	return E;
426
427	if (Error E = validateORCTables())
428	return E;
429
430	return Error::success();
431	}
432	};
433
434	Error LinuxKernelRewriter::detectLinuxKernelVersion() {
435	if (BinaryData *BD = BC.getBinaryDataByName(Name: "linux_banner")) {
436	const BinarySection &Section = BD->getSection();
437	const std::string S =
438	Section.getContents().substr(Start: BD->getOffset(), N: BD->getSize()).str();
439
440	const std::regex Re(R"---(Linux version ((\d+)\.(\d+)(\.(\d+))?))---");
441	std::smatch Match;
442	if (std::regex_search(s: S, m&: Match, e: Re)) {
443	const unsigned Major = std::stoi(str: Match[2].str());
444	const unsigned Minor = std::stoi(str: Match[3].str());
445	const unsigned Rev = Match[5].matched ? std::stoi(str: Match[5].str()) : 0;
446	LinuxKernelVersion = LKVersion(Major, Minor, Rev);
447	BC.outs() << "BOLT-INFO: Linux kernel version is " << Match[1].str()
448	<< "\n";
449	return Error::success();
450	}
451	}
452	return createStringError(EC: errc::executable_format_error,
453	S: "Linux kernel version is unknown");
454	}
455
456	void LinuxKernelRewriter::processLKSections() {
457	processLKKSymtab();
458	processLKKSymtab(IsGPL: true);
459	}
460
461	/// Process __ksymtab[_gpl] sections of Linux Kernel.
462	/// This section lists all the vmlinux symbols that kernel modules can access.
463	///
464	/// All the entries are 4 bytes each and hence we can read them by one by one
465	/// and ignore the ones that are not pointing to the .text section. All pointers
466	/// are PC relative offsets. Always, points to the beginning of the function.
467	void LinuxKernelRewriter::processLKKSymtab(bool IsGPL) {
468	StringRef SectionName = "__ksymtab";
469	if (IsGPL)
470	SectionName = "__ksymtab_gpl";
471	ErrorOr<BinarySection &> SectionOrError =
472	BC.getUniqueSectionByName(SectionName);
473	assert(SectionOrError &&
474	"__ksymtab[_gpl] section not found in Linux Kernel binary");
475	const uint64_t SectionSize = SectionOrError->getSize();
476	const uint64_t SectionAddress = SectionOrError->getAddress();
477	assert((SectionSize % 4) == 0 &&
478	"The size of the __ksymtab[_gpl] section should be a multiple of 4");
479
480	for (uint64_t I = 0; I < SectionSize; I += 4) {
481	const uint64_t EntryAddress = SectionAddress + I;
482	ErrorOr<int64_t> Offset = BC.getSignedValueAtAddress(Address: EntryAddress, Size: 4);
483	assert(Offset && "Reading valid PC-relative offset for a ksymtab entry");
484	const int32_t SignedOffset = *Offset;
485	const uint64_t RefAddress = EntryAddress + SignedOffset;
486	BinaryFunction *BF = BC.getBinaryFunctionAtAddress(Address: RefAddress);
487	if (!BF)
488	continue;
489
490	BC.addRelocation(Address: EntryAddress, Symbol: BF->getSymbol(), Type: Relocation::getPC32(), Addend: 0,
491	Value: *Offset);
492	}
493	}
494
495	/// .smp_locks section contains PC-relative references to instructions with LOCK
496	/// prefix. The prefix can be converted to NOP at boot time on non-SMP systems.
497	Error LinuxKernelRewriter::processSMPLocks() {
498	ErrorOr<BinarySection &> SMPLocksSection =
499	BC.getUniqueSectionByName(SectionName: ".smp_locks");
500	if (!SMPLocksSection)
501	return Error::success();
502
503	const uint64_t SectionSize = SMPLocksSection->getSize();
504	const uint64_t SectionAddress = SMPLocksSection->getAddress();
505	if (SectionSize % SMP_LOCKS_ENTRY_SIZE)
506	return createStringError(EC: errc::executable_format_error,
507	S: "bad size of .smp_locks section");
508
509	AddressExtractor AE(SMPLocksSection->getContents(), SectionAddress,
510	BC.AsmInfo->isLittleEndian(),
511	BC.AsmInfo->getCodePointerSize());
512	AddressExtractor::Cursor Cursor(0);
513	while (Cursor && Cursor.tell() < SectionSize) {
514	const uint64_t Offset = Cursor.tell();
515	const uint64_t IP = AE.getPCRelAddress32(C&: Cursor);
516
517	// Consume the status of the cursor.
518	if (!Cursor)
519	return createStringError(EC: errc::executable_format_error,
520	Fmt: "error while reading .smp_locks: %s",
521	Vals: toString(E: Cursor.takeError()).c_str());
522
523	if (opts::DumpSMPLocks)
524	BC.outs() << "SMP lock at 0x: " << Twine::utohexstr(Val: IP) << '\n';
525
526	BinaryFunction *BF = BC.getBinaryFunctionContainingAddress(Address: IP);
527	if (!BF || !BC.shouldEmit(Function: *BF))
528	continue;
529
530	MCInst *Inst = BF->getInstructionAtOffset(Offset: IP - BF->getAddress());
531	if (!Inst)
532	return createStringError(EC: errc::executable_format_error,
533	Fmt: "no instruction matches lock at 0x%" PRIx64, Vals: IP);
534
535	// Check for duplicate entries.
536	if (BC.MIB->hasAnnotation(Inst: *Inst, Name: "SMPLock"))
537	return createStringError(EC: errc::executable_format_error,
538	Fmt: "duplicate SMP lock at 0x%" PRIx64, Vals: IP);
539
540	BC.MIB->addAnnotation(Inst&: *Inst, Name: "SMPLock", Val: true);
541	MCSymbol *Label =
542	BC.MIB->getOrCreateInstLabel(Inst&: *Inst, Name: "__SMPLock_", Ctx: BC.Ctx.get());
543
544	Fixups.push_back(x: {.Section: *SMPLocksSection, .Offset: Offset, .BF: *BF, .Label: *Label,
545	/*IsPCRelative*/ true});
546	}
547
548	const uint64_t NumEntries = SectionSize / SMP_LOCKS_ENTRY_SIZE;
549	BC.outs() << "BOLT-INFO: parsed " << NumEntries << " SMP lock entries\n";
550
551	return Error::success();
552	}
553
554	void LinuxKernelRewriter::processInstructionFixups() {
555	for (InstructionFixup &Fixup : Fixups) {
556	if (!BC.shouldEmit(Function: Fixup.BF))
557	continue;
558
559	Fixup.Section.addRelocation(Offset: Fixup.Offset, Symbol: &Fixup.Label,
560	Type: Fixup.IsPCRelative ? ELF::R_X86_64_PC32
561	: ELF::R_X86_64_64,
562	/*Addend*/ 0);
563	}
564	}
565
566	Error LinuxKernelRewriter::readORCTables() {
567	// NOTE: we should ignore relocations for orc tables as the tables are sorted
568	// post-link time and relocations are not updated.
569	ORCUnwindSection = BC.getUniqueSectionByName(SectionName: ".orc_unwind");
570	ORCUnwindIPSection = BC.getUniqueSectionByName(SectionName: ".orc_unwind_ip");
571
572	if (!ORCUnwindSection && !ORCUnwindIPSection)
573	return Error::success();
574
575	if (!ORCUnwindSection || !ORCUnwindIPSection)
576	return createStringError(EC: errc::executable_format_error,
577	S: "missing ORC section");
578
579	NumORCEntries = ORCUnwindIPSection->getSize() / ORC_UNWIND_IP_ENTRY_SIZE;
580	if (ORCUnwindSection->getSize() != NumORCEntries * ORC_UNWIND_ENTRY_SIZE ||
581	ORCUnwindIPSection->getSize() != NumORCEntries * ORC_UNWIND_IP_ENTRY_SIZE)
582	return createStringError(EC: errc::executable_format_error,
583	S: "ORC entries number mismatch detected");
584
585	DataExtractor OrcDE(ORCUnwindSection->getContents(),
586	BC.AsmInfo->isLittleEndian(),
587	BC.AsmInfo->getCodePointerSize());
588	AddressExtractor IPAE(
589	ORCUnwindIPSection->getContents(), ORCUnwindIPSection->getAddress(),
590	BC.AsmInfo->isLittleEndian(), BC.AsmInfo->getCodePointerSize());
591	DataExtractor::Cursor ORCCursor(0);
592	DataExtractor::Cursor IPCursor(0);
593	uint64_t PrevIP = 0;
594	for (uint32_t Index = 0; Index < NumORCEntries; ++Index) {
595	const uint64_t IP = IPAE.getPCRelAddress32(C&: IPCursor);
596	// Consume the status of the cursor.
597	if (!IPCursor)
598	return createStringError(EC: errc::executable_format_error,
599	Fmt: "out of bounds while reading ORC IP table: %s",
600	Vals: toString(E: IPCursor.takeError()).c_str());
601
602	if (IP < PrevIP && opts::Verbosity)
603	BC.errs() << "BOLT-WARNING: out of order IP 0x" << Twine::utohexstr(Val: IP)
604	<< " detected while reading ORC\n";
605
606	PrevIP = IP;
607
608	// Store all entries, includes those we are not going to update as the
609	// tables need to be sorted globally before being written out.
610	ORCEntries.push_back(x: ORCListEntry());
611	ORCListEntry &Entry = ORCEntries.back();
612
613	Entry.IP = IP;
614	Entry.ORC.SPOffset = (int16_t)OrcDE.getU16(C&: ORCCursor);
615	Entry.ORC.BPOffset = (int16_t)OrcDE.getU16(C&: ORCCursor);
616	Entry.ORC.Info = (int16_t)OrcDE.getU16(C&: ORCCursor);
617	Entry.BF = nullptr;
618
619	// Consume the status of the cursor.
620	if (!ORCCursor)
621	return createStringError(EC: errc::executable_format_error,
622	Fmt: "out of bounds while reading ORC: %s",
623	Vals: toString(E: ORCCursor.takeError()).c_str());
624
625	if (Entry.ORC == NullORC)
626	continue;
627
628	BinaryFunction *&BF = Entry.BF;
629	BF = BC.getBinaryFunctionContainingAddress(Address: IP, /*CheckPastEnd*/ true);
630
631	// If the entry immediately pointing past the end of the function is not
632	// the terminator entry, then it does not belong to this function.
633	if (BF && BF->getAddress() + BF->getSize() == IP)
634	BF = 0;
635
636	if (!BF) {
637	if (opts::Verbosity)
638	BC.errs() << "BOLT-WARNING: no binary function found matching ORC 0x"
639	<< Twine::utohexstr(Val: IP) << ": " << Entry.ORC << '\n';
640	continue;
641	}
642
643	BF->setHasORC(true);
644
645	if (!BF->hasInstructions())
646	continue;
647
648	const uint64_t Offset = IP - BF->getAddress();
649	MCInst *Inst = BF->getInstructionAtOffset(Offset);
650	if (!Inst) {
651	// Check if there is an alternative instruction(s) at this IP. Multiple
652	// alternative instructions can take a place of a single original
653	// instruction and each alternative can have a separate ORC entry.
654	// Since ORC table is shared between all alternative sequences, there's
655	// a requirement that only one (out of many) sequences can have an
656	// instruction from the ORC table to avoid ambiguities/conflicts.
657	//
658	// For now, we have limited support for alternatives. I.e. we still print
659	// functions with them, but will not change the code in the output binary.
660	// As such, we can ignore alternative ORC entries. They will be preserved
661	// in the binary, but will not get printed in the instruction stream.
662	Inst = BF->getInstructionContainingOffset(Offset);
663	if (Inst || BC.MIB->hasAnnotation(Inst: *Inst, Name: "AltInst"))
664	continue;
665
666	return createStringError(
667	EC: errc::executable_format_error,
668	Fmt: "no instruction at address 0x%" PRIx64 " in .orc_unwind_ip", Vals: IP);
669	}
670
671	// Some addresses will have two entries associated with them. The first
672	// one being a "weak" section terminator. Since we ignore the terminator,
673	// we should only assign one entry per instruction.
674	if (BC.MIB->hasAnnotation(Inst: *Inst, Name: "ORC"))
675	return createStringError(
676	EC: errc::executable_format_error,
677	Fmt: "duplicate non-terminal ORC IP 0x%" PRIx64 " in .orc_unwind_ip", Vals: IP);
678
679	BC.MIB->addAnnotation(Inst&: *Inst, Name: "ORC", Val: Entry.ORC);
680	}
681
682	BC.outs() << "BOLT-INFO: parsed " << NumORCEntries << " ORC entries\n";
683
684	if (opts::DumpORC) {
685	BC.outs() << "BOLT-INFO: ORC unwind information:\n";
686	for (const ORCListEntry &E : ORCEntries) {
687	BC.outs() << "0x" << Twine::utohexstr(Val: E.IP) << ": " << E.ORC;
688	if (E.BF)
689	BC.outs() << ": " << *E.BF;
690	BC.outs() << '\n';
691	}
692	}
693
694	// Add entries for functions that don't have explicit ORC info at the start.
695	// We'll have the correct info for them even if ORC for the preceding function
696	// changes.
697	ORCListType NewEntries;
698	for (BinaryFunction &BF : llvm::make_second_range(c&: BC.getBinaryFunctions())) {
699	auto It = llvm::partition_point(Range&: ORCEntries, P: [&](const ORCListEntry &E) {
700	return E.IP <= BF.getAddress();
701	});
702	if (It != ORCEntries.begin())
703	--It;
704
705	if (It->BF == &BF)
706	continue;
707
708	if (It->ORC == NullORC && It->IP == BF.getAddress()) {
709	assert(!It->BF);
710	It->BF = &BF;
711	continue;
712	}
713
714	NewEntries.push_back(x: {.IP: BF.getAddress(), .BF: &BF, .ORC: It->ORC});
715	if (It->ORC != NullORC)
716	BF.setHasORC(true);
717	}
718
719	llvm::copy(Range&: NewEntries, Out: std::back_inserter(x&: ORCEntries));
720	llvm::sort(C&: ORCEntries);
721
722	if (opts::DumpORC) {
723	BC.outs() << "BOLT-INFO: amended ORC unwind information:\n";
724	for (const ORCListEntry &E : ORCEntries) {
725	BC.outs() << "0x" << Twine::utohexstr(Val: E.IP) << ": " << E.ORC;
726	if (E.BF)
727	BC.outs() << ": " << *E.BF;
728	BC.outs() << '\n';
729	}
730	}
731
732	return Error::success();
733	}
734
735	Error LinuxKernelRewriter::processORCPostCFG() {
736	if (!NumORCEntries)
737	return Error::success();
738
739	// Propagate ORC to the rest of the function. We can annotate every
740	// instruction in every function, but to minimize the overhead, we annotate
741	// the first instruction in every basic block to reflect the state at the
742	// entry. This way, the ORC state can be calculated based on annotations
743	// regardless of the basic block layout. Note that if we insert/delete
744	// instructions, we must take care to attach ORC info to the new/deleted ones.
745	for (BinaryFunction &BF : llvm::make_second_range(c&: BC.getBinaryFunctions())) {
746
747	std::optional<ORCState> CurrentState;
748	for (BinaryBasicBlock &BB : BF) {
749	for (MCInst &Inst : BB) {
750	ErrorOr<ORCState> State =
751	BC.MIB->tryGetAnnotationAs<ORCState>(Inst, Name: "ORC");
752
753	if (State) {
754	CurrentState = *State;
755	continue;
756	}
757
758	// Get state for the start of the function.
759	if (!CurrentState) {
760	// A terminator entry (NullORC) can match the function address. If
761	// there's also a non-terminator entry, it will be placed after the
762	// terminator. Hence, we are looking for the last ORC entry that
763	// matches the address.
764	auto It =
765	llvm::partition_point(Range&: ORCEntries, P: [&](const ORCListEntry &E) {
766	return E.IP <= BF.getAddress();
767	});
768	if (It != ORCEntries.begin())
769	--It;
770
771	assert(It->IP == BF.getAddress() && (!It->BF || It->BF == &BF) &&
772	"ORC info at function entry expected.");
773
774	if (It->ORC == NullORC && BF.hasORC()) {
775	BC.errs() << "BOLT-WARNING: ORC unwind info excludes prologue for "
776	<< BF << '\n';
777	}
778
779	It->BF = &BF;
780
781	CurrentState = It->ORC;
782	if (It->ORC != NullORC)
783	BF.setHasORC(true);
784	}
785
786	// While printing ORC, attach info to every instruction for convenience.
787	if (opts::PrintORC || &Inst == &BB.front())
788	BC.MIB->addAnnotation(Inst, Name: "ORC", Val: *CurrentState);
789	}
790	}
791	}
792
793	return Error::success();
794	}
795
796	Error LinuxKernelRewriter::rewriteORCTables() {
797	if (!NumORCEntries)
798	return Error::success();
799
800	// Update ORC sections in-place. As we change the code, the number of ORC
801	// entries may increase for some functions. However, as we remove terminator
802	// redundancy (see below), more space is freed up and we should always be able
803	// to fit new ORC tables in the reserved space.
804	auto createInPlaceWriter = [&](BinarySection &Section) -> BinaryStreamWriter {
805	const size_t Size = Section.getSize();
806	uint8_t *NewContents = new uint8_t[Size];
807	Section.updateContents(NewData: NewContents, NewSize: Size);
808	Section.setOutputFileOffset(Section.getInputFileOffset());
809	return BinaryStreamWriter({NewContents, Size}, BC.AsmInfo->isLittleEndian()
810	? endianness::little
811	: endianness::big);
812	};
813	BinaryStreamWriter UnwindWriter = createInPlaceWriter(*ORCUnwindSection);
814	BinaryStreamWriter UnwindIPWriter = createInPlaceWriter(*ORCUnwindIPSection);
815
816	uint64_t NumEmitted = 0;
817	std::optional<ORCState> LastEmittedORC;
818	auto emitORCEntry = [&](const uint64_t IP, const ORCState &ORC,
819	MCSymbol *Label = 0, bool Force = false) -> Error {
820	if (LastEmittedORC && ORC == *LastEmittedORC && !Force)
821	return Error::success();
822
823	LastEmittedORC = ORC;
824
825	if (++NumEmitted > NumORCEntries)
826	return createStringError(EC: errc::executable_format_error,
827	S: "exceeded the number of allocated ORC entries");
828
829	if (Label)
830	ORCUnwindIPSection->addRelocation(Offset: UnwindIPWriter.getOffset(), Symbol: Label,
831	Type: Relocation::getPC32(), /*Addend*/ 0);
832
833	const int32_t IPValue =
834	IP - ORCUnwindIPSection->getAddress() - UnwindIPWriter.getOffset();
835	if (Error E = UnwindIPWriter.writeInteger(Value: IPValue))
836	return E;
837
838	if (Error E = UnwindWriter.writeInteger(Value: ORC.SPOffset))
839	return E;
840	if (Error E = UnwindWriter.writeInteger(Value: ORC.BPOffset))
841	return E;
842	if (Error E = UnwindWriter.writeInteger(Value: ORC.Info))
843	return E;
844
845	return Error::success();
846	};
847
848	// Emit new ORC entries for the emitted function.
849	auto emitORC = [&](const FunctionFragment &FF) -> Error {
850	ORCState CurrentState = NullORC;
851	for (BinaryBasicBlock *BB : FF) {
852	for (MCInst &Inst : *BB) {
853	ErrorOr<ORCState> ErrorOrState =
854	BC.MIB->tryGetAnnotationAs<ORCState>(Inst, Name: "ORC");
855	if (!ErrorOrState || *ErrorOrState == CurrentState)
856	continue;
857
858	// Issue label for the instruction.
859	MCSymbol *Label =
860	BC.MIB->getOrCreateInstLabel(Inst, Name: "__ORC_", Ctx: BC.Ctx.get());
861
862	if (Error E = emitORCEntry(0, *ErrorOrState, Label))
863	return E;
864
865	CurrentState = *ErrorOrState;
866	}
867	}
868
869	return Error::success();
870	};
871
872	// Emit ORC entries for cold fragments. We assume that these fragments are
873	// emitted contiguously in memory using reserved space in the kernel. This
874	// assumption is validated in post-emit pass validateORCTables() where we
875	// check that ORC entries are sorted by their addresses.
876	auto emitColdORC = [&]() -> Error {
877	for (BinaryFunction &BF :
878	llvm::make_second_range(c&: BC.getBinaryFunctions())) {
879	if (!BC.shouldEmit(Function: BF))
880	continue;
881	for (FunctionFragment &FF : BF.getLayout().getSplitFragments())
882	if (Error E = emitORC(FF))
883	return E;
884	}
885
886	return Error::success();
887	};
888
889	bool ShouldEmitCold = !BC.BOLTReserved.empty();
890	for (ORCListEntry &Entry : ORCEntries) {
891	if (ShouldEmitCold && Entry.IP > BC.BOLTReserved.start()) {
892	if (Error E = emitColdORC())
893	return E;
894
895	// Emit terminator entry at the end of the reserved region.
896	if (Error E = emitORCEntry(BC.BOLTReserved.end(), NullORC))
897	return E;
898
899	ShouldEmitCold = false;
900	}
901
902	// Emit original entries for functions that we haven't modified.
903	if (!Entry.BF || !BC.shouldEmit(Function: *Entry.BF)) {
904	// Emit terminator only if it marks the start of a function.
905	if (Entry.ORC == NullORC && !Entry.BF)
906	continue;
907	if (Error E = emitORCEntry(Entry.IP, Entry.ORC))
908	return E;
909	continue;
910	}
911
912	// Emit all ORC entries for a function referenced by an entry and skip over
913	// the rest of entries for this function by resetting its ORC attribute.
914	if (Entry.BF->hasORC()) {
915	if (Error E = emitORC(Entry.BF->getLayout().getMainFragment()))
916	return E;
917	Entry.BF->setHasORC(false);
918	}
919	}
920
921	LLVM_DEBUG(dbgs() << "BOLT-DEBUG: emitted " << NumEmitted
922	<< " ORC entries\n");
923
924	// Populate ORC tables with a terminator entry with max address to match the
925	// original table sizes.
926	const uint64_t LastIP = std::numeric_limits<uint64_t>::max();
927	while (UnwindWriter.bytesRemaining()) {
928	if (Error E = emitORCEntry(LastIP, NullORC, nullptr, /*Force*/ true))
929	return E;
930	}
931
932	return Error::success();
933	}
934
935	Error LinuxKernelRewriter::validateORCTables() {
936	if (!ORCUnwindIPSection)
937	return Error::success();
938
939	AddressExtractor IPAE(
940	ORCUnwindIPSection->getOutputContents(), ORCUnwindIPSection->getAddress(),
941	BC.AsmInfo->isLittleEndian(), BC.AsmInfo->getCodePointerSize());
942	AddressExtractor::Cursor IPCursor(0);
943	uint64_t PrevIP = 0;
944	for (uint32_t Index = 0; Index < NumORCEntries; ++Index) {
945	const uint64_t IP = IPAE.getPCRelAddress32(C&: IPCursor);
946	if (!IPCursor)
947	return createStringError(EC: errc::executable_format_error,
948	Fmt: "out of bounds while reading ORC IP table: %s",
949	Vals: toString(E: IPCursor.takeError()).c_str());
950
951	assert(IP >= PrevIP && "Unsorted ORC table detected");
952	(void)PrevIP;
953	PrevIP = IP;
954	}
955
956	return Error::success();
957	}
958
959	/// The static call site table is created by objtool and contains entries in the
960	/// following format:
961	///
962	/// struct static_call_site {
963	/// s32 addr;
964	/// s32 key;
965	/// };
966	///
967	Error LinuxKernelRewriter::readStaticCalls() {
968	const BinaryData *StaticCallTable =
969	BC.getBinaryDataByName(Name: "__start_static_call_sites");
970	if (!StaticCallTable)
971	return Error::success();
972
973	StaticCallTableAddress = StaticCallTable->getAddress();
974
975	const BinaryData *Stop = BC.getBinaryDataByName(Name: "__stop_static_call_sites");
976	if (!Stop)
977	return createStringError(EC: errc::executable_format_error,
978	S: "missing __stop_static_call_sites symbol");
979
980	ErrorOr<BinarySection &> ErrorOrSection =
981	BC.getSectionForAddress(Address: StaticCallTableAddress);
982	if (!ErrorOrSection)
983	return createStringError(EC: errc::executable_format_error,
984	S: "no section matching __start_static_call_sites");
985
986	StaticCallSection = *ErrorOrSection;
987	if (!StaticCallSection->containsAddress(Address: Stop->getAddress() - 1))
988	return createStringError(EC: errc::executable_format_error,
989	S: "__stop_static_call_sites not in the same section "
990	"as __start_static_call_sites");
991
992	if ((Stop->getAddress() - StaticCallTableAddress) % STATIC_CALL_ENTRY_SIZE)
993	return createStringError(EC: errc::executable_format_error,
994	S: "static call table size error");
995
996	const uint64_t SectionAddress = StaticCallSection->getAddress();
997	AddressExtractor AE(StaticCallSection->getContents(), SectionAddress,
998	BC.AsmInfo->isLittleEndian(),
999	BC.AsmInfo->getCodePointerSize());
1000	AddressExtractor::Cursor Cursor(StaticCallTableAddress - SectionAddress);
1001	uint32_t EntryID = 0;
1002	while (Cursor && Cursor.tell() < Stop->getAddress() - SectionAddress) {
1003	const uint64_t CallAddress = AE.getPCRelAddress32(C&: Cursor);
1004	const uint64_t KeyAddress = AE.getPCRelAddress32(C&: Cursor);
1005
1006	// Consume the status of the cursor.
1007	if (!Cursor)
1008	return createStringError(EC: errc::executable_format_error,
1009	Fmt: "out of bounds while reading static calls: %s",
1010	Vals: toString(E: Cursor.takeError()).c_str());
1011
1012	++EntryID;
1013
1014	if (opts::DumpStaticCalls) {
1015	BC.outs() << "Static Call Site: " << EntryID << '\n';
1016	BC.outs() << "\tCallAddress: 0x" << Twine::utohexstr(Val: CallAddress)
1017	<< "\n\tKeyAddress: 0x" << Twine::utohexstr(Val: KeyAddress)
1018	<< '\n';
1019	}
1020
1021	BinaryFunction *BF = BC.getBinaryFunctionContainingAddress(Address: CallAddress);
1022	if (!BF)
1023	continue;
1024
1025	if (!BC.shouldEmit(Function: *BF))
1026	continue;
1027
1028	if (!BF->hasInstructions())
1029	continue;
1030
1031	MCInst *Inst = BF->getInstructionAtOffset(Offset: CallAddress - BF->getAddress());
1032	if (!Inst)
1033	return createStringError(EC: errc::executable_format_error,
1034	Fmt: "no instruction at call site address 0x%" PRIx64,
1035	Vals: CallAddress);
1036
1037	// Check for duplicate entries.
1038	if (BC.MIB->hasAnnotation(Inst: *Inst, Name: "StaticCall"))
1039	return createStringError(EC: errc::executable_format_error,
1040	Fmt: "duplicate static call site at 0x%" PRIx64,
1041	Vals: CallAddress);
1042
1043	BC.MIB->addAnnotation(Inst&: *Inst, Name: "StaticCall", Val: EntryID);
1044
1045	MCSymbol *Label =
1046	BC.MIB->getOrCreateInstLabel(Inst&: *Inst, Name: "__SC_", Ctx: BC.Ctx.get());
1047
1048	StaticCallEntries.push_back(x: {.ID: EntryID, .Function: BF, .Label: Label});
1049	}
1050
1051	BC.outs() << "BOLT-INFO: parsed " << StaticCallEntries.size()
1052	<< " static call entries\n";
1053
1054	return Error::success();
1055	}
1056
1057	/// The static call table is sorted during boot time in
1058	/// static_call_sort_entries(). This makes it possible to update existing
1059	/// entries in-place ignoring their relative order.
1060	Error LinuxKernelRewriter::rewriteStaticCalls() {
1061	if (!StaticCallTableAddress || !StaticCallSection)
1062	return Error::success();
1063
1064	for (auto &Entry : StaticCallEntries) {
1065	if (!Entry.Function)
1066	continue;
1067
1068	BinaryFunction &BF = *Entry.Function;
1069	if (!BC.shouldEmit(Function: BF))
1070	continue;
1071
1072	// Create a relocation against the label.
1073	const uint64_t EntryOffset = StaticCallTableAddress -
1074	StaticCallSection->getAddress() +
1075	(Entry.ID - 1) * STATIC_CALL_ENTRY_SIZE;
1076	StaticCallSection->addRelocation(Offset: EntryOffset, Symbol: Entry.Label,
1077	Type: ELF::R_X86_64_PC32, /*Addend*/ 0);
1078	}
1079
1080	return Error::success();
1081	}
1082
1083	/// Instructions that access user-space memory can cause page faults. These
1084	/// faults will be handled by the kernel and execution will resume at the fixup
1085	/// code location if the address was invalid. The kernel uses the exception
1086	/// table to match the faulting instruction to its fixup. The table consists of
1087	/// the following entries:
1088	///
1089	/// struct exception_table_entry {
1090	/// int insn;
1091	/// int fixup;
1092	/// int data;
1093	/// };
1094	///
1095	/// More info at:
1096	/// https://www.kernel.org/doc/Documentation/x86/exception-tables.txt
1097	Error LinuxKernelRewriter::readExceptionTable() {
1098	ExceptionsSection = BC.getUniqueSectionByName(SectionName: "__ex_table");
1099	if (!ExceptionsSection)
1100	return Error::success();
1101
1102	if (ExceptionsSection->getSize() % EXCEPTION_TABLE_ENTRY_SIZE)
1103	return createStringError(EC: errc::executable_format_error,
1104	S: "exception table size error");
1105
1106	AddressExtractor AE(
1107	ExceptionsSection->getContents(), ExceptionsSection->getAddress(),
1108	BC.AsmInfo->isLittleEndian(), BC.AsmInfo->getCodePointerSize());
1109	AddressExtractor::Cursor Cursor(0);
1110	uint32_t EntryID = 0;
1111	while (Cursor && Cursor.tell() < ExceptionsSection->getSize()) {
1112	const uint64_t InstAddress = AE.getPCRelAddress32(C&: Cursor);
1113	const uint64_t FixupAddress = AE.getPCRelAddress32(C&: Cursor);
1114	const uint64_t Data = AE.getU32(C&: Cursor);
1115
1116	// Consume the status of the cursor.
1117	if (!Cursor)
1118	return createStringError(
1119	EC: errc::executable_format_error,
1120	Fmt: "out of bounds while reading exception table: %s",
1121	Vals: toString(E: Cursor.takeError()).c_str());
1122
1123	++EntryID;
1124
1125	if (opts::DumpExceptions) {
1126	BC.outs() << "Exception Entry: " << EntryID << '\n';
1127	BC.outs() << "\tInsn: 0x" << Twine::utohexstr(Val: InstAddress) << '\n'
1128	<< "\tFixup: 0x" << Twine::utohexstr(Val: FixupAddress) << '\n'
1129	<< "\tData: 0x" << Twine::utohexstr(Val: Data) << '\n';
1130	}
1131
1132	MCInst *Inst = nullptr;
1133	MCSymbol *FixupLabel = nullptr;
1134
1135	BinaryFunction *InstBF = BC.getBinaryFunctionContainingAddress(Address: InstAddress);
1136	if (InstBF && BC.shouldEmit(Function: *InstBF)) {
1137	Inst = InstBF->getInstructionAtOffset(Offset: InstAddress - InstBF->getAddress());
1138	if (!Inst)
1139	return createStringError(EC: errc::executable_format_error,
1140	Fmt: "no instruction at address 0x%" PRIx64
1141	" in exception table",
1142	Vals: InstAddress);
1143	BC.MIB->addAnnotation(Inst&: *Inst, Name: "ExceptionEntry", Val: EntryID);
1144	FunctionsWithExceptions.insert(V: InstBF);
1145	}
1146
1147	if (!InstBF && opts::Verbosity) {
1148	BC.outs() << "BOLT-INFO: no function matches instruction at 0x"
1149	<< Twine::utohexstr(Val: InstAddress)
1150	<< " referenced by Linux exception table\n";
1151	}
1152
1153	BinaryFunction *FixupBF =
1154	BC.getBinaryFunctionContainingAddress(Address: FixupAddress);
1155	if (FixupBF && BC.shouldEmit(Function: *FixupBF)) {
1156	const uint64_t Offset = FixupAddress - FixupBF->getAddress();
1157	if (!FixupBF->getInstructionAtOffset(Offset))
1158	return createStringError(EC: errc::executable_format_error,
1159	Fmt: "no instruction at fixup address 0x%" PRIx64
1160	" in exception table",
1161	Vals: FixupAddress);
1162	FixupLabel = Offset ? FixupBF->addEntryPointAtOffset(Offset)
1163	: FixupBF->getSymbol();
1164	if (Inst)
1165	BC.MIB->addAnnotation(Inst&: *Inst, Name: "Fixup", Val: FixupLabel->getName());
1166	FunctionsWithExceptions.insert(V: FixupBF);
1167	}
1168
1169	if (!FixupBF && opts::Verbosity) {
1170	BC.outs() << "BOLT-INFO: no function matches fixup code at 0x"
1171	<< Twine::utohexstr(Val: FixupAddress)
1172	<< " referenced by Linux exception table\n";
1173	}
1174	}
1175
1176	BC.outs() << "BOLT-INFO: parsed "
1177	<< ExceptionsSection->getSize() / EXCEPTION_TABLE_ENTRY_SIZE
1178	<< " exception table entries\n";
1179
1180	return Error::success();
1181	}
1182
1183	/// Depending on the value of CONFIG_BUILDTIME_TABLE_SORT, the kernel expects
1184	/// the exception table to be sorted. Hence we have to sort it after code
1185	/// reordering.
1186	Error LinuxKernelRewriter::rewriteExceptionTable() {
1187	// Disable output of functions with exceptions before rewrite support is
1188	// added.
1189	for (BinaryFunction *BF : FunctionsWithExceptions)
1190	BF->setSimple(false);
1191
1192	return Error::success();
1193	}
1194
1195	/// .parainsrtuctions section contains information for patching parvirtual call
1196	/// instructions during runtime. The entries in the section are in the form:
1197	///
1198	/// struct paravirt_patch_site {
1199	/// u8 *instr; /* original instructions */
1200	/// u8 type; /* type of this instruction */
1201	/// u8 len; /* length of original instruction */
1202	/// };
1203	///
1204	/// Note that the structures are aligned at 8-byte boundary.
1205	Error LinuxKernelRewriter::readParaInstructions() {
1206	ParavirtualPatchSection = BC.getUniqueSectionByName(SectionName: ".parainstructions");
1207	if (!ParavirtualPatchSection)
1208	return Error::success();
1209
1210	DataExtractor DE(ParavirtualPatchSection->getContents(),
1211	BC.AsmInfo->isLittleEndian(),
1212	BC.AsmInfo->getCodePointerSize());
1213	uint32_t EntryID = 0;
1214	DataExtractor::Cursor Cursor(0);
1215	while (Cursor && !DE.eof(C: Cursor)) {
1216	const uint64_t NextOffset = alignTo(Size: Cursor.tell(), A: Align(PARA_PATCH_ALIGN));
1217	if (!DE.isValidOffset(offset: NextOffset))
1218	break;
1219
1220	Cursor.seek(NewOffSet: NextOffset);
1221
1222	const uint64_t InstrLocation = DE.getU64(C&: Cursor);
1223	const uint8_t Type = DE.getU8(C&: Cursor);
1224	const uint8_t Len = DE.getU8(C&: Cursor);
1225
1226	if (!Cursor)
1227	return createStringError(
1228	EC: errc::executable_format_error,
1229	Fmt: "out of bounds while reading .parainstructions: %s",
1230	Vals: toString(E: Cursor.takeError()).c_str());
1231
1232	++EntryID;
1233
1234	if (opts::DumpParavirtualPatchSites) {
1235	BC.outs() << "Paravirtual patch site: " << EntryID << '\n';
1236	BC.outs() << "\tInstr: 0x" << Twine::utohexstr(Val: InstrLocation)
1237	<< "\n\tType: 0x" << Twine::utohexstr(Val: Type) << "\n\tLen: 0x"
1238	<< Twine::utohexstr(Val: Len) << '\n';
1239	}
1240
1241	BinaryFunction *BF = BC.getBinaryFunctionContainingAddress(Address: InstrLocation);
1242	if (!BF && opts::Verbosity) {
1243	BC.outs() << "BOLT-INFO: no function matches address 0x"
1244	<< Twine::utohexstr(Val: InstrLocation)
1245	<< " referenced by paravirutal patch site\n";
1246	}
1247
1248	if (BF && BC.shouldEmit(Function: *BF)) {
1249	MCInst *Inst =
1250	BF->getInstructionAtOffset(Offset: InstrLocation - BF->getAddress());
1251	if (!Inst)
1252	return createStringError(EC: errc::executable_format_error,
1253	Fmt: "no instruction at address 0x%" PRIx64
1254	" in paravirtual call site %d",
1255	Vals: InstrLocation, Vals: EntryID);
1256	BC.MIB->addAnnotation(Inst&: *Inst, Name: "ParaSite", Val: EntryID);
1257	}
1258	}
1259
1260	BC.outs() << "BOLT-INFO: parsed " << EntryID << " paravirtual patch sites\n";
1261
1262	return Error::success();
1263	}
1264
1265	void LinuxKernelRewriter::skipFunctionsWithAnnotation(
1266	StringRef Annotation) const {
1267	for (BinaryFunction &BF : llvm::make_second_range(c&: BC.getBinaryFunctions())) {
1268	if (!BC.shouldEmit(Function: BF))
1269	continue;
1270	for (const BinaryBasicBlock &BB : BF) {
1271	const bool HasAnnotation = llvm::any_of(Range: BB, P: [&](const MCInst &Inst) {
1272	return BC.MIB->hasAnnotation(Inst, Name: Annotation);
1273	});
1274	if (HasAnnotation) {
1275	BF.setSimple(false);
1276	break;
1277	}
1278	}
1279	}
1280	}
1281
1282	Error LinuxKernelRewriter::rewriteParaInstructions() {
1283	// Disable output of functions with paravirtual instructions before the
1284	// rewrite support is complete.
1285	skipFunctionsWithAnnotation(Annotation: "ParaSite");
1286
1287	return Error::success();
1288	}
1289
1290	/// Process __bug_table section.
1291	/// This section contains information useful for kernel debugging, mostly
1292	/// utilized by WARN()/WARN_ON() macros and deprecated BUG()/BUG_ON().
1293	///
1294	/// Each entry in the section is a struct bug_entry that contains a pointer to
1295	/// the ud2 instruction corresponding to the bug, corresponding file name (both
1296	/// pointers use PC relative offset addressing), line number, and flags.
1297	/// The definition of the struct bug_entry can be found in
1298	/// `include/asm-generic/bug.h`. The first entry in the struct is an instruction
1299	/// address encoded as a PC-relative offset. In theory, it could be an absolute
1300	/// address if CONFIG_GENERIC_BUG_RELATIVE_POINTERS is not set, but in practice
1301	/// the kernel code relies on it being a relative offset on x86-64.
1302	Error LinuxKernelRewriter::readBugTable() {
1303	BugTableSection = BC.getUniqueSectionByName(SectionName: "__bug_table");
1304	if (!BugTableSection)
1305	return Error::success();
1306
1307	if (BugTableSection->getSize() % BUG_TABLE_ENTRY_SIZE)
1308	return createStringError(EC: errc::executable_format_error,
1309	S: "bug table size error");
1310
1311	AddressExtractor AE(
1312	BugTableSection->getContents(), BugTableSection->getAddress(),
1313	BC.AsmInfo->isLittleEndian(), BC.AsmInfo->getCodePointerSize());
1314	AddressExtractor::Cursor Cursor(0);
1315	uint32_t EntryID = 0;
1316	while (Cursor && Cursor.tell() < BugTableSection->getSize()) {
1317	const uint64_t Pos = Cursor.tell();
1318	const uint64_t InstAddress = AE.getPCRelAddress32(C&: Cursor);
1319	Cursor.seek(NewOffSet: Pos + BUG_TABLE_ENTRY_SIZE);
1320
1321	if (!Cursor)
1322	return createStringError(EC: errc::executable_format_error,
1323	Fmt: "out of bounds while reading __bug_table: %s",
1324	Vals: toString(E: Cursor.takeError()).c_str());
1325
1326	++EntryID;
1327
1328	BinaryFunction *BF = BC.getBinaryFunctionContainingAddress(Address: InstAddress);
1329	if (!BF && opts::Verbosity) {
1330	BC.outs() << "BOLT-INFO: no function matches address 0x"
1331	<< Twine::utohexstr(Val: InstAddress)
1332	<< " referenced by bug table\n";
1333	}
1334
1335	if (BF && BC.shouldEmit(Function: *BF)) {
1336	MCInst *Inst = BF->getInstructionAtOffset(Offset: InstAddress - BF->getAddress());
1337	if (!Inst)
1338	return createStringError(EC: errc::executable_format_error,
1339	Fmt: "no instruction at address 0x%" PRIx64
1340	" referenced by bug table entry %d",
1341	Vals: InstAddress, Vals: EntryID);
1342	BC.MIB->addAnnotation(Inst&: *Inst, Name: "BugEntry", Val: EntryID);
1343
1344	FunctionBugList[BF].push_back(Elt: EntryID);
1345	}
1346	}
1347
1348	BC.outs() << "BOLT-INFO: parsed " << EntryID << " bug table entries\n";
1349
1350	return Error::success();
1351	}
1352
1353	/// find_bug() uses linear search to match an address to an entry in the bug
1354	/// table. Hence, there is no need to sort entries when rewriting the table.
1355	/// When we need to erase an entry, we set its instruction address to zero.
1356	Error LinuxKernelRewriter::rewriteBugTable() {
1357	if (!BugTableSection)
1358	return Error::success();
1359
1360	for (BinaryFunction &BF : llvm::make_second_range(c&: BC.getBinaryFunctions())) {
1361	if (!BC.shouldEmit(Function: BF))
1362	continue;
1363
1364	if (!FunctionBugList.count(Val: &BF))
1365	continue;
1366
1367	// Bugs that will be emitted for this function.
1368	DenseSet<uint32_t> EmittedIDs;
1369	for (BinaryBasicBlock &BB : BF) {
1370	for (MCInst &Inst : BB) {
1371	if (!BC.MIB->hasAnnotation(Inst, Name: "BugEntry"))
1372	continue;
1373	const uint32_t ID = BC.MIB->getAnnotationAs<uint32_t>(Inst, Name: "BugEntry");
1374	EmittedIDs.insert(V: ID);
1375
1376	// Create a relocation entry for this bug entry.
1377	MCSymbol *Label =
1378	BC.MIB->getOrCreateInstLabel(Inst, Name: "__BUG_", Ctx: BC.Ctx.get());
1379	const uint64_t EntryOffset = (ID - 1) * BUG_TABLE_ENTRY_SIZE;
1380	BugTableSection->addRelocation(Offset: EntryOffset, Symbol: Label, Type: ELF::R_X86_64_PC32,
1381	/*Addend*/ 0);
1382	}
1383	}
1384
1385	// Clear bug entries that were not emitted for this function, e.g. as a
1386	// result of DCE, but setting their instruction address to zero.
1387	for (const uint32_t ID : FunctionBugList[&BF]) {
1388	if (!EmittedIDs.count(V: ID)) {
1389	const uint64_t EntryOffset = (ID - 1) * BUG_TABLE_ENTRY_SIZE;
1390	BugTableSection->addRelocation(Offset: EntryOffset, Symbol: nullptr, Type: ELF::R_X86_64_PC32,
1391	/*Addend*/ 0);
1392	}
1393	}
1394	}
1395
1396	return Error::success();
1397	}
1398
1399	/// The kernel can replace certain instruction sequences depending on hardware
1400	/// it is running on and features specified during boot time. The information
1401	/// about alternative instruction sequences is stored in .altinstructions
1402	/// section. The format of entries in this section is defined in
1403	/// arch/x86/include/asm/alternative.h:
1404	///
1405	/// struct alt_instr {
1406	/// s32 instr_offset;
1407	/// s32 repl_offset;
1408	/// uXX feature;
1409	/// u8 instrlen;
1410	/// u8 replacementlen;
1411	/// u8 padlen; // present in older kernels
1412	/// } __packed;
1413	///
1414	/// Note that the structure is packed.
1415	///
1416	/// Since the size of the "feature" field could be either u16 or u32, and
1417	/// "padlen" presence is unknown, we attempt to parse .altinstructions section
1418	/// using all possible combinations (four at this time). Since we validate the
1419	/// contents of the section and its size, the detection works quite well.
1420	/// Still, we leave the user the opportunity to specify these features on the
1421	/// command line and skip the guesswork.
1422	Error LinuxKernelRewriter::readAltInstructions() {
1423	AltInstrSection = BC.getUniqueSectionByName(SectionName: ".altinstructions");
1424	if (!AltInstrSection)
1425	return Error::success();
1426
1427	// Presence of "padlen" field.
1428	std::vector<bool> PadLenVariants;
1429	if (opts::AltInstHasPadLen.getNumOccurrences())
1430	PadLenVariants.push_back(x: opts::AltInstHasPadLen);
1431	else
1432	PadLenVariants = {false, true};
1433
1434	// Size (in bytes) variants of "feature" field.
1435	std::vector<uint32_t> FeatureSizeVariants;
1436	if (opts::AltInstFeatureSize.getNumOccurrences())
1437	FeatureSizeVariants.push_back(x: opts::AltInstFeatureSize);
1438	else
1439	FeatureSizeVariants = {2, 4};
1440
1441	for (bool AltInstHasPadLen : PadLenVariants) {
1442	for (uint32_t AltInstFeatureSize : FeatureSizeVariants) {
1443	LLVM_DEBUG({
1444	dbgs() << "BOLT-DEBUG: trying AltInstHasPadLen = " << AltInstHasPadLen
1445	<< "; AltInstFeatureSize = " << AltInstFeatureSize << ";\n";
1446	});
1447	if (Error E = tryReadAltInstructions(AltInstFeatureSize, AltInstHasPadLen,
1448	/*ParseOnly*/ true)) {
1449	consumeError(Err: std::move(E));
1450	continue;
1451	}
1452
1453	LLVM_DEBUG(dbgs() << "Matched .altinstructions format\n");
1454
1455	if (!opts::AltInstHasPadLen.getNumOccurrences())
1456	BC.outs() << "BOLT-INFO: setting --" << opts::AltInstHasPadLen.ArgStr
1457	<< '=' << AltInstHasPadLen << '\n';
1458
1459	if (!opts::AltInstFeatureSize.getNumOccurrences())
1460	BC.outs() << "BOLT-INFO: setting --" << opts::AltInstFeatureSize.ArgStr
1461	<< '=' << AltInstFeatureSize << '\n';
1462
1463	return tryReadAltInstructions(AltInstFeatureSize, AltInstHasPadLen,
1464	/*ParseOnly*/ false);
1465	}
1466	}
1467
1468	// We couldn't match the format. Read again to properly propagate the error
1469	// to the user.
1470	return tryReadAltInstructions(AltInstFeatureSize: opts::AltInstFeatureSize,
1471	AltInstHasPadLen: opts::AltInstHasPadLen, /*ParseOnly*/ false);
1472	}
1473
1474	Error LinuxKernelRewriter::tryReadAltInstructions(uint32_t AltInstFeatureSize,
1475	bool AltInstHasPadLen,
1476	bool ParseOnly) {
1477	AddressExtractor AE(
1478	AltInstrSection->getContents(), AltInstrSection->getAddress(),
1479	BC.AsmInfo->isLittleEndian(), BC.AsmInfo->getCodePointerSize());
1480	AddressExtractor::Cursor Cursor(0);
1481	uint64_t EntryID = 0;
1482	while (Cursor && !AE.eof(C: Cursor)) {
1483	const uint64_t OrgInstAddress = AE.getPCRelAddress32(C&: Cursor);
1484	const uint64_t AltInstAddress = AE.getPCRelAddress32(C&: Cursor);
1485	const uint64_t Feature = AE.getUnsigned(C&: Cursor, Size: AltInstFeatureSize);
1486	const uint8_t OrgSize = AE.getU8(C&: Cursor);
1487	const uint8_t AltSize = AE.getU8(C&: Cursor);
1488
1489	// Older kernels may have the padlen field.
1490	const uint8_t PadLen = AltInstHasPadLen ? AE.getU8(C&: Cursor) : 0;
1491
1492	if (!Cursor)
1493	return createStringError(
1494	EC: errc::executable_format_error,
1495	Fmt: "out of bounds while reading .altinstructions: %s",
1496	Vals: toString(E: Cursor.takeError()).c_str());
1497
1498	++EntryID;
1499
1500	if (opts::DumpAltInstructions) {
1501	BC.outs() << "Alternative instruction entry: " << EntryID
1502	<< "\n\tOrg: 0x" << Twine::utohexstr(Val: OrgInstAddress)
1503	<< "\n\tAlt: 0x" << Twine::utohexstr(Val: AltInstAddress)
1504	<< "\n\tFeature: 0x" << Twine::utohexstr(Val: Feature)
1505	<< "\n\tOrgSize: " << (int)OrgSize
1506	<< "\n\tAltSize: " << (int)AltSize << '\n';
1507	if (AltInstHasPadLen)
1508	BC.outs() << "\tPadLen: " << (int)PadLen << '\n';
1509	}
1510
1511	if (AltSize > OrgSize)
1512	return createStringError(EC: errc::executable_format_error,
1513	S: "error reading .altinstructions");
1514
1515	BinaryFunction *BF = BC.getBinaryFunctionContainingAddress(Address: OrgInstAddress);
1516	if (!BF && opts::Verbosity) {
1517	BC.outs() << "BOLT-INFO: no function matches address 0x"
1518	<< Twine::utohexstr(Val: OrgInstAddress)
1519	<< " of instruction from .altinstructions\n";
1520	}
1521
1522	BinaryFunction *AltBF =
1523	BC.getBinaryFunctionContainingAddress(Address: AltInstAddress);
1524	if (!ParseOnly && AltBF && BC.shouldEmit(Function: *AltBF)) {
1525	BC.errs()
1526	<< "BOLT-WARNING: alternative instruction sequence found in function "
1527	<< *AltBF << '\n';
1528	AltBF->setIgnored();
1529	}
1530
1531	if (!BF || !BF->hasInstructions())
1532	continue;
1533
1534	if (OrgInstAddress + OrgSize > BF->getAddress() + BF->getSize())
1535	return createStringError(EC: errc::executable_format_error,
1536	S: "error reading .altinstructions");
1537
1538	MCInst *Inst =
1539	BF->getInstructionAtOffset(Offset: OrgInstAddress - BF->getAddress());
1540	if (!Inst)
1541	return createStringError(EC: errc::executable_format_error,
1542	Fmt: "no instruction at address 0x%" PRIx64
1543	" referenced by .altinstructions entry %d",
1544	Vals: OrgInstAddress, Vals: EntryID);
1545
1546	if (ParseOnly)
1547	continue;
1548
1549	// There could be more than one alternative instruction sequences for the
1550	// same original instruction. Annotate each alternative separately.
1551	std::string AnnotationName = "AltInst";
1552	unsigned N = 2;
1553	while (BC.MIB->hasAnnotation(Inst: *Inst, Name: AnnotationName))
1554	AnnotationName = "AltInst" + std::to_string(val: N++);
1555
1556	BC.MIB->addAnnotation(Inst&: *Inst, Name: AnnotationName, Val: EntryID);
1557
1558	// Annotate all instructions from the original sequence. Note that it's not
1559	// the most efficient way to look for instructions in the address range,
1560	// but since alternative instructions are uncommon, it will do for now.
1561	for (uint32_t Offset = 1; Offset < OrgSize; ++Offset) {
1562	Inst = BF->getInstructionAtOffset(Offset: OrgInstAddress + Offset -
1563	BF->getAddress());
1564	if (Inst)
1565	BC.MIB->addAnnotation(Inst&: *Inst, Name: AnnotationName, Val: EntryID);
1566	}
1567	}
1568
1569	if (!ParseOnly)
1570	BC.outs() << "BOLT-INFO: parsed " << EntryID
1571	<< " alternative instruction entries\n";
1572
1573	return Error::success();
1574	}
1575
1576	void LinuxKernelRewriter::processAltInstructionsPostCFG() {
1577	// Disable optimization and output of functions with alt instructions before
1578	// the rewrite support is complete. Alt instructions can modify the control
1579	// flow, hence we may end up deleting seemingly unreachable code.
1580	skipFunctionsWithAnnotation(Annotation: "AltInst");
1581	}
1582
1583	/// When the Linux kernel needs to handle an error associated with a given PCI
1584	/// device, it uses a table stored in .pci_fixup section to locate a fixup code
1585	/// specific to the vendor and the problematic device. The section contains a
1586	/// list of the following structures defined in include/linux/pci.h:
1587	///
1588	/// struct pci_fixup {
1589	/// u16 vendor; /* Or PCI_ANY_ID */
1590	/// u16 device; /* Or PCI_ANY_ID */
1591	/// u32 class; /* Or PCI_ANY_ID */
1592	/// unsigned int class_shift; /* should be 0, 8, 16 */
1593	/// int hook_offset;
1594	/// };
1595	///
1596	/// Normally, the hook will point to a function start and we don't have to
1597	/// update the pointer if we are not relocating functions. Hence, while reading
1598	/// the table we validate this assumption. If a function has a fixup code in the
1599	/// middle of its body, we issue a warning and ignore it.
1600	Error LinuxKernelRewriter::readPCIFixupTable() {
1601	PCIFixupSection = BC.getUniqueSectionByName(SectionName: ".pci_fixup");
1602	if (!PCIFixupSection)
1603	return Error::success();
1604
1605	if (PCIFixupSection->getSize() % PCI_FIXUP_ENTRY_SIZE)
1606	return createStringError(EC: errc::executable_format_error,
1607	S: "PCI fixup table size error");
1608
1609	AddressExtractor AE(
1610	PCIFixupSection->getContents(), PCIFixupSection->getAddress(),
1611	BC.AsmInfo->isLittleEndian(), BC.AsmInfo->getCodePointerSize());
1612	AddressExtractor::Cursor Cursor(0);
1613	uint64_t EntryID = 0;
1614	while (Cursor && !AE.eof(C: Cursor)) {
1615	const uint16_t Vendor = AE.getU16(C&: Cursor);
1616	const uint16_t Device = AE.getU16(C&: Cursor);
1617	const uint32_t Class = AE.getU32(C&: Cursor);
1618	const uint32_t ClassShift = AE.getU32(C&: Cursor);
1619	const uint64_t HookAddress = AE.getPCRelAddress32(C&: Cursor);
1620
1621	if (!Cursor)
1622	return createStringError(EC: errc::executable_format_error,
1623	Fmt: "out of bounds while reading .pci_fixup: %s",
1624	Vals: toString(E: Cursor.takeError()).c_str());
1625
1626	++EntryID;
1627
1628	if (opts::DumpPCIFixups) {
1629	BC.outs() << "PCI fixup entry: " << EntryID << "\n\tVendor 0x"
1630	<< Twine::utohexstr(Val: Vendor) << "\n\tDevice: 0x"
1631	<< Twine::utohexstr(Val: Device) << "\n\tClass: 0x"
1632	<< Twine::utohexstr(Val: Class) << "\n\tClassShift: 0x"
1633	<< Twine::utohexstr(Val: ClassShift) << "\n\tHookAddress: 0x"
1634	<< Twine::utohexstr(Val: HookAddress) << '\n';
1635	}
1636
1637	BinaryFunction *BF = BC.getBinaryFunctionContainingAddress(Address: HookAddress);
1638	if (!BF && opts::Verbosity) {
1639	BC.outs() << "BOLT-INFO: no function matches address 0x"
1640	<< Twine::utohexstr(Val: HookAddress)
1641	<< " of hook from .pci_fixup\n";
1642	}
1643
1644	if (!BF || !BC.shouldEmit(Function: *BF))
1645	continue;
1646
1647	if (const uint64_t Offset = HookAddress - BF->getAddress()) {
1648	BC.errs() << "BOLT-WARNING: PCI fixup detected in the middle of function "
1649	<< *BF << " at offset 0x" << Twine::utohexstr(Val: Offset) << '\n';
1650	BF->setSimple(false);
1651	}
1652	}
1653
1654	BC.outs() << "BOLT-INFO: parsed " << EntryID << " PCI fixup entries\n";
1655
1656	return Error::success();
1657	}
1658
1659	/// Runtime code modification used by static keys is the most ubiquitous
1660	/// self-modifying feature of the Linux kernel. The idea is to eliminate the
1661	/// condition check and associated conditional jump on a hot path if that
1662	/// condition (based on a boolean value of a static key) does not change often.
1663	/// Whenever the condition changes, the kernel runtime modifies all code paths
1664	/// associated with that key flipping the code between nop and (unconditional)
1665	/// jump. The information about the code is stored in a static key jump table
1666	/// and contains the list of entries of the following type from
1667	/// include/linux/jump_label.h:
1668	//
1669	/// struct jump_entry {
1670	/// s32 code;
1671	/// s32 target;
1672	/// long key; // key may be far away from the core kernel under KASLR
1673	/// };
1674	///
1675	/// The list does not have to be stored in any sorted way, but it is sorted at
1676	/// boot time (or module initialization time) first by "key" and then by "code".
1677	/// jump_label_sort_entries() is responsible for sorting the table.
1678	///
1679	/// The key in jump_entry structure uses lower two bits of the key address
1680	/// (which itself is aligned) to store extra information. We are interested in
1681	/// the lower bit which indicates if the key is likely to be set on the code
1682	/// path associated with this jump_entry.
1683	///
1684	/// static_key_{enable,disable}() functions modify the code based on key and
1685	/// jump table entries.
1686	///
1687	/// jump_label_update() updates all code entries for a given key. Batch mode is
1688	/// used for x86.
1689	///
1690	/// The actual patching happens in text_poke_bp_batch() that overrides the first
1691	/// byte of the sequence with int3 before proceeding with actual code
1692	/// replacement.
1693	Error LinuxKernelRewriter::readStaticKeysJumpTable() {
1694	const BinaryData *StaticKeysJumpTable =
1695	BC.getBinaryDataByName(Name: "__start___jump_table");
1696	if (!StaticKeysJumpTable)
1697	return Error::success();
1698
1699	StaticKeysJumpTableAddress = StaticKeysJumpTable->getAddress();
1700
1701	const BinaryData *Stop = BC.getBinaryDataByName(Name: "__stop___jump_table");
1702	if (!Stop)
1703	return createStringError(EC: errc::executable_format_error,
1704	S: "missing __stop___jump_table symbol");
1705
1706	ErrorOr<BinarySection &> ErrorOrSection =
1707	BC.getSectionForAddress(Address: StaticKeysJumpTableAddress);
1708	if (!ErrorOrSection)
1709	return createStringError(EC: errc::executable_format_error,
1710	S: "no section matching __start___jump_table");
1711
1712	StaticKeysJumpSection = *ErrorOrSection;
1713	if (!StaticKeysJumpSection->containsAddress(Address: Stop->getAddress() - 1))
1714	return createStringError(EC: errc::executable_format_error,
1715	S: "__stop___jump_table not in the same section "
1716	"as __start___jump_table");
1717
1718	if ((Stop->getAddress() - StaticKeysJumpTableAddress) %
1719	STATIC_KEYS_JUMP_ENTRY_SIZE)
1720	return createStringError(EC: errc::executable_format_error,
1721	S: "static keys jump table size error");
1722
1723	const uint64_t SectionAddress = StaticKeysJumpSection->getAddress();
1724	AddressExtractor AE(StaticKeysJumpSection->getContents(), SectionAddress,
1725	BC.AsmInfo->isLittleEndian(),
1726	BC.AsmInfo->getCodePointerSize());
1727	AddressExtractor::Cursor Cursor(StaticKeysJumpTableAddress - SectionAddress);
1728	uint32_t EntryID = 0;
1729	while (Cursor && Cursor.tell() < Stop->getAddress() - SectionAddress) {
1730	const uint64_t JumpAddress = AE.getPCRelAddress32(C&: Cursor);
1731	const uint64_t TargetAddress = AE.getPCRelAddress32(C&: Cursor);
1732	const uint64_t KeyAddress = AE.getPCRelAddress64(C&: Cursor);
1733
1734	// Consume the status of the cursor.
1735	if (!Cursor)
1736	return createStringError(
1737	EC: errc::executable_format_error,
1738	Fmt: "out of bounds while reading static keys jump table: %s",
1739	Vals: toString(E: Cursor.takeError()).c_str());
1740
1741	++EntryID;
1742
1743	JumpInfo.push_back(Elt: JumpInfoEntry());
1744	JumpInfoEntry &Info = JumpInfo.back();
1745	Info.Likely = KeyAddress & 1;
1746
1747	if (opts::DumpStaticKeys) {
1748	BC.outs() << "Static key jump entry: " << EntryID
1749	<< "\n\tJumpAddress: 0x" << Twine::utohexstr(Val: JumpAddress)
1750	<< "\n\tTargetAddress: 0x" << Twine::utohexstr(Val: TargetAddress)
1751	<< "\n\tKeyAddress: 0x" << Twine::utohexstr(Val: KeyAddress)
1752	<< "\n\tIsLikely: " << Info.Likely << '\n';
1753	}
1754
1755	BinaryFunction *BF = BC.getBinaryFunctionContainingAddress(Address: JumpAddress);
1756	if (!BF && opts::Verbosity) {
1757	BC.outs()
1758	<< "BOLT-INFO: no function matches address 0x"
1759	<< Twine::utohexstr(Val: JumpAddress)
1760	<< " of jump instruction referenced from static keys jump table\n";
1761	}
1762
1763	if (!BF || !BC.shouldEmit(Function: *BF))
1764	continue;
1765
1766	MCInst *Inst = BF->getInstructionAtOffset(Offset: JumpAddress - BF->getAddress());
1767	if (!Inst)
1768	return createStringError(
1769	EC: errc::executable_format_error,
1770	Fmt: "no instruction at static keys jump site address 0x%" PRIx64,
1771	Vals: JumpAddress);
1772
1773	if (!BF->containsAddress(PC: TargetAddress))
1774	return createStringError(
1775	EC: errc::executable_format_error,
1776	Fmt: "invalid target of static keys jump at 0x%" PRIx64 " : 0x%" PRIx64,
1777	Vals: JumpAddress, Vals: TargetAddress);
1778
1779	const bool IsBranch = BC.MIB->isBranch(Inst: *Inst);
1780	if (!IsBranch && !BC.MIB->isNoop(Inst: *Inst))
1781	return createStringError(EC: errc::executable_format_error,
1782	Fmt: "jump or nop expected at address 0x%" PRIx64,
1783	Vals: JumpAddress);
1784
1785	const uint64_t Size = BC.computeInstructionSize(Inst: *Inst);
1786	if (Size != 2 && Size != 5) {
1787	return createStringError(
1788	EC: errc::executable_format_error,
1789	Fmt: "unexpected static keys jump size at address 0x%" PRIx64,
1790	Vals: JumpAddress);
1791	}
1792
1793	MCSymbol *Target = BF->registerBranch(Src: JumpAddress, Dst: TargetAddress);
1794	MCInst StaticKeyBranch;
1795
1796	// Create a conditional branch instruction. The actual conditional code type
1797	// should not matter as long as it's a valid code. The instruction should be
1798	// treated as a conditional branch for control-flow purposes. Before we emit
1799	// the code, it will be converted to a different instruction in
1800	// rewriteStaticKeysJumpTable().
1801	//
1802	// NB: for older kernels, under LongJumpLabels option, we create long
1803	// conditional branch to guarantee that code size estimation takes
1804	// into account the extra bytes needed for long branch that will be used
1805	// by the kernel patching code. Newer kernels can work with both short
1806	// and long branches. The code for long conditional branch is larger
1807	// than unconditional one, so we are pessimistic in our estimations.
1808	if (opts::LongJumpLabels)
1809	BC.MIB->createLongCondBranch(Inst&: StaticKeyBranch, Target, CC: 0, Ctx: BC.Ctx.get());
1810	else
1811	BC.MIB->createCondBranch(Inst&: StaticKeyBranch, Target, CC: 0, Ctx: BC.Ctx.get());
1812	BC.MIB->moveAnnotations(SrcInst: std::move(*Inst), DstInst&: StaticKeyBranch);
1813	BC.MIB->setDynamicBranch(Inst&: StaticKeyBranch, ID: EntryID);
1814	*Inst = StaticKeyBranch;
1815
1816	// IsBranch = InitialValue ^ LIKELY
1817	//
1818	// 0 0 0
1819	// 1 0 1
1820	// 1 1 0
1821	// 0 1 1
1822	//
1823	// => InitialValue = IsBranch ^ LIKELY
1824	Info.InitValue = IsBranch ^ Info.Likely;
1825
1826	// Add annotations to facilitate manual code analysis.
1827	BC.MIB->addAnnotation(Inst&: *Inst, Name: "Likely", Val: Info.Likely);
1828	BC.MIB->addAnnotation(Inst&: *Inst, Name: "InitValue", Val: Info.InitValue);
1829	if (!BC.MIB->getSize(Inst: *Inst))
1830	BC.MIB->setSize(Inst&: *Inst, Size);
1831
1832	if (!BC.MIB->getOffset(Inst: *Inst))
1833	BC.MIB->setOffset(Inst&: *Inst, Offset: JumpAddress - BF->getAddress());
1834
1835	if (opts::LongJumpLabels)
1836	BC.MIB->setSize(Inst&: *Inst, Size: 5);
1837	}
1838
1839	BC.outs() << "BOLT-INFO: parsed " << EntryID << " static keys jump entries\n";
1840
1841	return Error::success();
1842	}
1843
1844	// Pre-emit pass. Convert dynamic branch instructions into jumps that could be
1845	// relaxed. In post-emit pass we will convert those jumps into nops when
1846	// necessary. We do the unconditional conversion into jumps so that the jumps
1847	// can be relaxed and the optimal size of jump/nop instruction is selected.
1848	Error LinuxKernelRewriter::rewriteStaticKeysJumpTable() {
1849	if (!StaticKeysJumpSection)
1850	return Error::success();
1851
1852	uint64_t NumShort = 0;
1853	uint64_t NumLong = 0;
1854	for (BinaryFunction &BF : llvm::make_second_range(c&: BC.getBinaryFunctions())) {
1855	if (!BC.shouldEmit(Function: BF))
1856	continue;
1857
1858	for (BinaryBasicBlock &BB : BF) {
1859	for (MCInst &Inst : BB) {
1860	if (!BC.MIB->isDynamicBranch(Inst))
1861	continue;
1862
1863	const uint32_t EntryID = *BC.MIB->getDynamicBranchID(Inst);
1864	MCSymbol *Target =
1865	const_cast<MCSymbol *>(BC.MIB->getTargetSymbol(Inst));
1866	assert(Target && "Target symbol should be set.");
1867
1868	const JumpInfoEntry &Info = JumpInfo[EntryID - 1];
1869	const bool IsBranch = Info.Likely ^ Info.InitValue;
1870
1871	uint32_t Size = *BC.MIB->getSize(Inst);
1872	if (Size == 2)
1873	++NumShort;
1874	else if (Size == 5)
1875	++NumLong;
1876	else
1877	llvm_unreachable("Wrong size for static keys jump instruction.");
1878
1879	MCInst NewInst;
1880	// Replace the instruction with unconditional jump even if it needs to
1881	// be nop in the binary.
1882	if (opts::LongJumpLabels) {
1883	BC.MIB->createLongUncondBranch(Inst&: NewInst, Target, Ctx: BC.Ctx.get());
1884	} else {
1885	// Newer kernels can handle short and long jumps for static keys.
1886	// Optimistically, emit short jump and check if it gets relaxed into
1887	// a long one during post-emit. Only then convert the jump to a nop.
1888	BC.MIB->createUncondBranch(Inst&: NewInst, TBB: Target, Ctx: BC.Ctx.get());
1889	}
1890
1891	BC.MIB->moveAnnotations(SrcInst: std::move(Inst), DstInst&: NewInst);
1892	Inst = NewInst;
1893
1894	// Mark the instruction for nop conversion.
1895	if (!IsBranch)
1896	NopIDs.insert(V: EntryID);
1897
1898	MCSymbol *Label =
1899	BC.MIB->getOrCreateInstLabel(Inst, Name: "__SK_", Ctx: BC.Ctx.get());
1900
1901	// Create a relocation against the label.
1902	const uint64_t EntryOffset = StaticKeysJumpTableAddress -
1903	StaticKeysJumpSection->getAddress() +
1904	(EntryID - 1) * 16;
1905	StaticKeysJumpSection->addRelocation(Offset: EntryOffset, Symbol: Label,
1906	Type: ELF::R_X86_64_PC32,
1907	/*Addend*/ 0);
1908	StaticKeysJumpSection->addRelocation(Offset: EntryOffset + 4, Symbol: Target,
1909	Type: ELF::R_X86_64_PC32, /*Addend*/ 0);
1910	}
1911	}
1912	}
1913
1914	BC.outs() << "BOLT-INFO: the input contains " << NumShort << " short and "
1915	<< NumLong << " long static keys jumps in optimized functions\n";
1916
1917	return Error::success();
1918	}
1919
1920	// Post-emit pass of static keys jump section. Convert jumps to nops.
1921	Error LinuxKernelRewriter::updateStaticKeysJumpTablePostEmit() {
1922	if (!StaticKeysJumpSection || !StaticKeysJumpSection->isFinalized())
1923	return Error::success();
1924
1925	const uint64_t SectionAddress = StaticKeysJumpSection->getAddress();
1926	AddressExtractor AE(StaticKeysJumpSection->getOutputContents(),
1927	SectionAddress, BC.AsmInfo->isLittleEndian(),
1928	BC.AsmInfo->getCodePointerSize());
1929	AddressExtractor::Cursor Cursor(StaticKeysJumpTableAddress - SectionAddress);
1930	const BinaryData *Stop = BC.getBinaryDataByName(Name: "__stop___jump_table");
1931	uint32_t EntryID = 0;
1932	uint64_t NumShort = 0;
1933	uint64_t NumLong = 0;
1934	while (Cursor && Cursor.tell() < Stop->getAddress() - SectionAddress) {
1935	const uint64_t JumpAddress = AE.getPCRelAddress32(C&: Cursor);
1936	const uint64_t TargetAddress = AE.getPCRelAddress32(C&: Cursor);
1937	const uint64_t KeyAddress = AE.getPCRelAddress64(C&: Cursor);
1938
1939	// Consume the status of the cursor.
1940	if (!Cursor)
1941	return createStringError(EC: errc::executable_format_error,
1942	Fmt: "out of bounds while updating static keys: %s",
1943	Vals: toString(E: Cursor.takeError()).c_str());
1944
1945	++EntryID;
1946
1947	LLVM_DEBUG({
1948	dbgs() << "\n\tJumpAddress: 0x" << Twine::utohexstr(JumpAddress)
1949	<< "\n\tTargetAddress: 0x" << Twine::utohexstr(TargetAddress)
1950	<< "\n\tKeyAddress: 0x" << Twine::utohexstr(KeyAddress) << '\n';
1951	});
1952	(void)TargetAddress;
1953	(void)KeyAddress;
1954
1955	BinaryFunction *BF =
1956	BC.getBinaryFunctionContainingAddress(Address: JumpAddress,
1957	/*CheckPastEnd*/ false,
1958	/*UseMaxSize*/ true);
1959	assert(BF && "Cannot get function for modified static key.");
1960
1961	if (!BF->isEmitted())
1962	continue;
1963
1964	// Disassemble instruction to collect stats even if nop-conversion is
1965	// unnecessary.
1966	MutableArrayRef<uint8_t> Contents = MutableArrayRef<uint8_t>(
1967	reinterpret_cast<uint8_t *>(BF->getImageAddress()), BF->getImageSize());
1968	assert(Contents.size() && "Non-empty function image expected.");
1969
1970	MCInst Inst;
1971	uint64_t Size;
1972	const uint64_t JumpOffset = JumpAddress - BF->getAddress();
1973	if (!BC.DisAsm->getInstruction(Instr&: Inst, Size, Bytes: Contents.slice(N: JumpOffset), Address: 0,
1974	CStream&: nulls())) {
1975	llvm_unreachable("Unable to disassemble jump instruction.");
1976	}
1977	assert(BC.MIB->isBranch(Inst) && "Branch instruction expected.");
1978
1979	if (Size == 2)
1980	++NumShort;
1981	else if (Size == 5)
1982	++NumLong;
1983	else
1984	llvm_unreachable("Unexpected size for static keys jump instruction.");
1985
1986	// Check if we need to convert jump instruction into a nop.
1987	if (!NopIDs.contains(V: EntryID))
1988	continue;
1989
1990	SmallString<15> NopCode;
1991	raw_svector_ostream VecOS(NopCode);
1992	BC.MAB->writeNopData(OS&: VecOS, Count: Size, STI: BC.STI.get());
1993	for (uint64_t I = 0; I < Size; ++I)
1994	Contents[JumpOffset + I] = NopCode[I];
1995	}
1996
1997	BC.outs() << "BOLT-INFO: written " << NumShort << " short and " << NumLong
1998	<< " long static keys jumps in optimized functions\n";
1999
2000	return Error::success();
2001	}
2002
2003	} // namespace
2004
2005	std::unique_ptr<MetadataRewriter>
2006	llvm::bolt::createLinuxKernelRewriter(BinaryContext &BC) {
2007	return std::make_unique<LinuxKernelRewriter>(args&: BC);
2008	}
2009