Share
Embed
LLVM Backend Development for EFI Byte Code
EFI Byte Code (EBC) is architecture independent mechanism for executing UEFI device driver. Currently, there is only a few tools for EBC available online. Major open source compilers like GCC or LLVM/Clang do not support this architecture. To tackle this issue, I am developing a LLVM backend for EBC. In this presentation, I will introduce EBC and related tools I developed, and LLVM EBC backend specific problems.
Akira Moroo
July 20, 2019
Transcript
51 slides
-
LLVM Backend Development for EFI Byte Code July 20, 2019
kernelvm15@Tokyo @retrage -
TL;DR • LLVM backend development for EBC is hard. •
Source code: • yabits/llvm:retrage/ebc • yabits/clang:retrage/ebc • yabits/lld:retrage/ebc • Blog post: • LLVMのEFI Byte Codeバックエンドを作る (ja) 1 -
Device Driver in Option ROM • Some PCIe devices have
device drivers for UEFI in its Option ROM. 3 -
How to support multiple arch? • The device must have
multiple device drivers for each supported architecture. 4 -
EBC solves the problem • ”platform- and processor-independent mechanisms for
loading and executing EFI device drivers” 5 -
Available EBC Tools • EDK2[1] EBC VM reference implementation. •
Intel C Compiler for EFI Byte Code[2] • fasmg-ebc: flat assembler based EBC assembler[3] • EbcDebugger: A standalone EBC Debugger[4] 6 -
Available EBC Tools • EDK2[1] EBC VM reference implementation. •
EBC VM reference implementation[5]. • EBC assembly level debugger[6]. • You can run with QEMU+OVMF. • But UEFI does not provide memory protection. • Intel C Compiler for EFI Byte Code[2] • fasmg-ebc: flat assembler based EBC assembler[3] • EbcDebugger: A standalone EBC Debugger[4] 7 -
Available EBC Tools • EDK2[1] EBC VM reference implementation. •
Intel C Compiler for EFI Byte Code[2] • Closed source, non-free ($955) • Please someone donate it to me. • fasmg-ebc: flat assembler based EBC assembler[3] • EbcDebugger: A standalone EBC Debugger[4] 8 -
Available EBC Tools • EDK2[1] EBC VM reference implementation. •
Intel C Compiler for EFI Byte Code[2] • fasmg-ebc: flat assembler based EBC assembler[3] • It has a bug in encoding natural indexing. • EbcDebugger: A standalone EBC Debugger[4] • Not tried yet, but it seems re-packaging EDK2 EBC VM. 9 -
Available EBC Tools • EDK2[1] EBC VM reference implementation. •
Intel C Compiler for EFI Byte Code[2] • fasmg-ebc: flat assembler based EBC assembler[3] • EbcDebugger: A standalone EBC Debugger[4] • => No easy-to-use VM or free compiler • What we need to create: • User space EBC VM to make debugging easy • ELVM backend for EBC 10 -
ebcvm: user space EBC VM 11 • Motivation: • Can
I implement an EBC VM with only UEFI spec.? • For more details: • yabits/ebcvm • ebcvm: A Usermode EFI Byte Code Virtual Machine (ja) Registers Memory Decoder Executor Loader EFI Native Code Simple Debugger -
ELVM backend for EBC • ELVM: EsoLangVM Compiler Infrastructure •
It can emit little endian binaries. • EBC backend: • Add COFF binary format support. • Add EBC backend that generates raw binaries. • Test with ebcvm and passed all tests. • For more details: • retrage/elvm:retrage/ebc-v2 • ELVMのEFI Byte Codeバックエンドを作る (ja) 12 -
ELVM is great, but... • Generated code is not optimized.
• The binaries tend to be fat. • ELVM does not have linking stage. • Build means compiling and linking. • Only one file can be built at once. • => Using ELVM backend is not practical. • => Develop LLVM backend for EBC: • LLVM Core, Clang, LLD 14 -
Goal: Compile and Link this code 15 #include "efi.h" EFI_STATUS
efi_main(EFI_HANDLE ImageHandle, EFI_SYSTEM_TABLE *SystemTable) { CHAR16 *String = L"Hello, EBC!\n"; asm("movnw %0, @%0 (5,24)\n" // SystemTable->ConOut "pushn %1\n" // String "pushn %0\n" // SystemTable "call32exa @%0 (1,0)\n" // ConOut->OutputString "movqw r0, r0 (2,0)\n" ::"r"(SystemTable), "r"(String):); return EFI_SUCCESS; } -
MCLayer and CodeGen • MCLayer: • .s -> MCInst ->
.o • CodeGen: • LLVM IR -> SelectionDAG -> MachineInstr -> MCInst ->.o 16 -
MCLayer and CodeGen • MCLayer: • .s -> MCInst ->
.o • CodeGen: • LLVM IR -> SelectionDAG -> MachineInstr -> MCInst ->.o • Approach: start with MCLayer • Same approach with RISC-V backend. • https://speakerdeck.com/asb/llvm-backend- development-by-example-risc-v?slide=4 17 -
MCLayer: TODO list • Add Triple and EBC COFF defines.
• Describe register and instruction formats. • Define instructions and operand types. • Add MCTargetDesc/* and InstPrinter/*. • Add AsmParser. • Add Disassembler. • Add fixups support. • Write tests. 18 -
MCLayer: TODO list • Add Triple and EBC COFF defines.
• Describe register and instruction formats. • Define instructions and operand types. • Add MCTargetDesc/* and InstPrinter/*. • Add AsmParser. • Add Disassembler. • Add fixups support. • Write tests. 19 -
Natural Indexing: Example • Following arguments are passed at the
entry point: • ImageHandle • SystemTable 20 typedef EFI_STATUS (EFIAPI *EFI_IMAGE_ENTRY_POINT) ( IN EFI_HANDLE ImageHandle, IN EFI_SYSTEM_TABLE *SystemTable ); -
Natural Indexing: Example • In EBC Calling Convention, arguments are
passed via stack in reverse order. 21 typedef EFI_STATUS (EFIAPI *EFI_IMAGE_ENTRY_POINT) ( IN EFI_HANDLE ImageHandle, IN EFI_SYSTEM_TABLE *SystemTable ); ImageHandle SystemTable Low High Stack top Stack pointer -
Natural Indexing: Example • If you want to get SystemTable,
you have to know the size of ImageHandle. • However, the size of ImageHandle is host- dependent (as the type is void * in host) • On 32-bit host: 4-byte • On 64-bit host: 8-byte 22 ImageHandle SystemTable SP On 32-bit host 0 31 ImageHandle SystemTable SP 0 63 On 64-bit host -
Natural Indexing • Natural Indexing: (, ) • A set
of natural unit and constant unit • = ∗ ∗ + • Note: ( ∗) is host-dependent • For the previous case: (+1,0) • On 32-bit host: (1 ∗ 4 + 0) = 4 • On 64-bit host: (1 ∗ 8 + 0) = 8 • On LLVM EBC backend: • Both units are represented as immediate. • Implement custom natural index encoder/decoder. 23 -
Instruction defines: Easy mode • LLVM has TableGen domain specific
language. • TableGen has C++ like class. • Instructions are described by instantiating class. • Take a look at the simple example: STORESP 24 -
Instruction defines: STORESP 25 def STORESP : Instruction { field
bits<16> Inst; dag OutOperandList = (outs GPR:$op1); dag InOperandList = (ins DR:$op2); let Namespace = "EBC"; let AsmString = "storesp\t$op1, $op2"; let Size = 2; let Inst{14-12} = op2; let Inst{10-8} = op1; let Inst{5-0} = 0b101010; } -
Instruction defines: STORESP 26 def STORESP : Instruction { field
bits<16> Inst; dag OutOperandList = (outs GPR:$op1); dag InOperandList = (ins DR:$op2); let Namespace = "EBC"; let AsmString = "storesp\t$op1, $op2"; let Size = 2; let Inst{14-12} = op2; let Inst{10-8} = op1; let Inst{5-0} = 0b101010; } • Input/Output in DAG -
Instruction defines: STORESP 27 def STORESP : Instruction { field
bits<16> Inst; dag OutOperandList = (outs GPR:$op1); dag InOperandList = (ins DR:$op2); let Namespace = "EBC"; let AsmString = "storesp\t$op1, $op2"; let Size = 2; let Inst{14-12} = op2; let Inst{10-8} = op1; let Inst{5-0} = 0b101010; } • Assembly format -
Instruction defines: STORESP 28 def STORESP : Instruction { field
bits<16> Inst; dag OutOperandList = (outs GPR:$op1); dag InOperandList = (ins DR:$op2); let Namespace = "EBC"; let AsmString = "storesp\t$op1, $op2"; let Size = 2; let Inst{14-12} = op2; let Inst{10-8} = op1; let Inst{5-0} = 0b101010; } • Instruction Encoding -
Instruction defines: Hard mode • Most of EBC instructions have
optional operands. • Example: ALU operations • 32 64 @ @ , @ A {16|16} • 32-bit/64-bit operation • Operand 1 Direct/Indirect • Operand 2 Direct/Indirect • Operand 2 Optional Index/Immediate • 16 ways of combinations per instruction. • => Implement all using multiclass. 29 -
EBCALU multiclass 30 multiclass EBCALU<bits<6> opcode, string opcodestr> { foreach
hasImmIdx = [0b0, 0b1] in { foreach is64Bit = [0b0, 0b1] in { foreach Op1Indirect = [0b0, 0b1] in { foreach Op2Indirect = [0b0, 0b1] in def !if(is64Bit, "64", "32") # !if(Op1Indirect, "Op1I", "Op1D") # !if(Op2Indirect, "Op2I", "Op2D") # !cond(!eq(hasImmIdx, 0) : "", !eq(!and(hasImmIdx, Op2Indirect), 0) : "Imm", !eq(!and(hasImmIdx, Op2Indirect), 1) : "Idx") : EBCALUBase<opcode, hasImmIdx, is64Bit, Op1Indirect, Op2Indirect, (outs GPR:$dst), (ins GPR:$op1, GPR:$op2), (ins imm16:$imm), (ins idxn16:$idxn, idxc16:$idxc), opcodestr, "$op1", "$op2", "$imm", "(${idxn},${idxc})">; } } } } -
EBCALUBase class 31 class EBCALUBase<bits<6> opcode, bit hasImmIdx, bit is64Bit,
bit Op1Indirect, bit Op2Indirect, dag outs, dag ins, dag immins, dag idxins, string opcodestr, string op1str, string op2str, string immstr, string idxstr> : EBCInst2Op<opcode, hasImmIdx, is64Bit, Op1Indirect, Op2Indirect, outs, !cond(!eq(hasImmIdx, 0) : ins, !eq(!and(hasImmIdx, Op2Indirect), 0) : !con(ins, immins), !eq(!and(hasImmIdx, Op2Indirect), 1) : !con(ins, idxins)), opcodestr # !if(is64Bit, "64", "32"), !if(Op1Indirect, "@", "") # op1str # ", " # !if(Op2Indirect, "@", "") # op2str # !if(hasImmIdx, " ", "") # !cond(!eq(hasImmIdx, 0) : "", !eq(!and(hasImmIdx, Op2Indirect), 0) : immstr, !eq(!and(hasImmIdx, Op2Indirect), 1) : idxstr), []> { bits<3> dst; let CodeSize = !if(hasImmIdx, 4, 2); let mayLoad = !if(Op2Indirect, 1, 0); let mayStore = !if(Op1Indirect, 1, 0); } -
MCLayer and CodeGen • MCLayer: • .s -> MCInst ->
.o • CodeGen: • LLVM IR -> SelectionDAG -> MachineInstr -> MCInst ->.o 32 -
MCLayer and CodeGen • MCLayer: • .s -> MCInst ->
.o • CodeGen: • LLVM IR -> SelectionDAG -> MachineInstr -> MCInst ->.o • Just do it. 33 -
CodeGen: TODO list • ALU operations • Materializing constants •
Memory operation • Global address operation • Conditional branches • Function calls • SELECT/SELECT_CC • FrameIndex lowering • Prologue/Epilogue insertion • dynamic_stackalloc, stacksave, stackrestore • Inline assembly • And more! 34 -
EBC binary must be relocatable • This means that all
addresses must be relative. • MOVREL Operation: • 1 <= [ + ℎ + ] 35 MOVREL Instr Instruction Pointer Data0 .text section Data1 .data section Op1 Register= Data1 Offset -
Missing instruction in EBC • What about just calculate the
address from offset? • Something like: • 1 < = + ℎ + 36 ?? Instr Instruction Pointer Data0 .text section Data1 .data section Op1 Register = Absolute Address of Data 1 Offset -
Missing instruction in EBC • 1 < = + ℎ
+ • EBC does not have such an instruction. • We can use STORESP+MOVI+ADD set to achieve it. 37 STORESP MOVI .text section Data1 .data section ADD = 0 RST Offset -
Missing instruction in EBC • 1 < = + ℎ
+ • EBC does not have such an instruction. • We can use STORESP+MOVI+ADD set to achieve it. 38 STORESP MOVI .text section Data1 .data section ADD = 1 RS@ U = RS@ Offset -
Missing instruction in EBC • 1 < = + ℎ
+ • EBC does not have such an instruction. • We can use STORESP+MOVI+ADD set to achieve it. 39 STORESP MOVI .text section Data1 .data section ADD = 2 RSA U = RS@ V = Offset -
Missing instruction in EBC • 1 < = + ℎ
+ • EBC does not have such an instruction. • We can use STORESP+MOVI+ADD set to achieve it. 40 STORESP MOVI .text section Data1 .data section ADD = 3 U = RS@ + V = Offset -
Clang and LLD • Clang: • Add Triple, target specific
driver, and TargetInfo • Most of the code borrowed from MSVC driver. • LLD: • Add SectionChunk::applyRelEBC() • No DLL support • No PDB support 41 -
Demo Compile and Link the goal source code Execute the
generated EBC binary in QEMU+OVMF 42 -
Sad news: EBC is now optional 43 • 2.8: Remove
the EBC support requirement -
Conclusion • EFI Byte Code (EBC) is an architecture-independent mechanism
to execute UEFI device driver. • There is only a few tools for EBC. • I developed ebcvm and ELVM EBC backend. • For more practical use, I am developing LLVM backend for EBC. • EBC design is insane. • Complicated Instruction with Optional Operand. • Lack of necessary instruction. 44 -
References • [1] https://github.com/tianocore/edk2 • [2] https://software.intel.com/en-us/articles/intel-c- compiler-for-efi-byte-code-purchase • [3]
https://github.com/pbatard/fasmg-ebc • [4] https://github.com/pbatard/EbcDebugger • [5] https://github.com/tianocore/edk2/blob/master/Mde ModulePkg/Universal/EbcDxe/EbcExecute.c • [6] https://github.com/tianocore/edk2/tree/master/Mde ModulePkg/Universal/EbcDxe/EbcDebugger • [7] 45 -
Decoding hell II 48 • Why optional index come before
mandatory immediate? -
Unclear spec. • @ @ , Immed • Restriction: •
“Specifying an index value with Operand 1 direct results in an instruction encoding exception”. • @ @ , @ A {} • Spec does not explicitly imply that index value with Operand 2 direct is allowed. • It is actually allowed according to EDK2 VM. 49 -
Fixup kinds • fixups in EBC is {16,32,64}-bit IP-relative •
However, the offset is vary: • Most of EBC instruction: +2 • CALL32: -4 • JMP64: -8 • Is there any smart way to specify the offset? 50