ELVMのEFI Byte Codeバックエンドを作る

Jul 13, 2019

ここでは ELVM のEFI Byte Codeバックエンドについて紹介する．特にELVM IRとEFI Byte Codeのsemantic gapに注目する．

EFI Byte Codeについて

EFI Byte Code (EBC)はUEFI Specificationで定義されているアーキテクチャ非依存なUEFI向けデバイスドライバのための仮想マシンである， EBCの詳細については過去の記事である EFI Byte Code解説を参考にしたい．

EBCバックエンドのビルドとテスト

コードは以下で公開している．

https://github.com/retrage/elvm/tree/retrage/ebcvm

以下でビルドとebcvmによるテストが行える．

$ git clone https://github.com/retrage/elvm.git
$ cd elvm && git checkout retrage/ebcvm
$ make ebc

バックエンドの概要

EBCは64-bitなlittle endianなアーキテクチャであり， UEFIの仕様ではEBCのバイナリフォーマットはPE32+である． ELVMにはLinux向けのx86_32とARMのバックエンドが存在し，これらは直接ELFを出力する．一方でPEのサポートがないため新たにPEの出力をELVMに追加した．

EBCバックエンドの構成は既存のx86_32やARMのバックエンドを参考にしている．出力されるPEは.textセクションと.rodataセクションの2つのセクションを持つ． .textセクションにはELVM IRから変換したコードが配置され， .rodataセクションには後述のELVM IRでのプログラムカウンタと実アドレスのテーブルが配置される．

pc2addrの作成

ELVM IRではJMP命令などのターゲットのアドレスを ELVM IRにおけるプログラムカウンタの値で保持している．一方でEBCではターゲットのアドレスは実アドレスでなければならない．このため，ELVM IRでのプログラムカウンタの値と実アドレスの対応表を作成する必要がある．

  // pc_cnt: get program counter count
  int pc_cnt = 0;
  for (Inst* inst = module->text; inst; inst = inst->next) {
    pc_cnt++;
  }

最初にELVM IRのtextの命令数をpc_cntに数え上げる．

  // pc2addr: table from pc to addr
  int* pc2addr = calloc(pc_cnt, sizeof(int));
  int prev_pc = -1;
  for (Inst* inst = module->text; inst; inst = inst->next) {
    if (prev_pc != inst->pc) {
      pc2addr[inst->pc] = emit_cnt();
    }
    prev_pc = inst->pc;
    ebc_emit_inst(inst, pc2addr);
  }

次にpc2addrにプログラムカウンタの値をインデックスとして実アドレスの値のテーブルを作成する．ここでebc_emit_inst()を呼んでいるが，実際にEBCの命令を出力しているのではなく出力される命令の大きさ分 g_emit_cntをインクリメントしているだけである．

ヘッダの生成

ELFやPEなどのバイナリフォーマットでは各セクションの大きさが正しくヘッダに書き込まれている必要がある．このため，実際にバイナリを出力する前に必ず先にセクションの大きさを計算して置く必要がある．既にg_emit_cntとpc_cntに必要な値が取得できているので，これらを元に出力する．

  strcpy(text.name, ".text");
  text.vaddr = aligned(PE_HEADER_SIZE, PE_SEC_ALIGN);
  text.vsize = emit_cnt();
  text.raddr = aligned(PE_HEADER_SIZE, PE_FILE_ALIGN) - PE_FILE_ALIGN;
  text.rsize = aligned(text.vsize, PE_FILE_ALIGN);
  text.chars = 0x60000020; // r-x exec

  strcpy(rodata.name, ".rodata");
  rodata.vaddr = aligned(text.vaddr + text.vsize, PE_SEC_ALIGN);
  rodata.vsize = pc_cnt * 4;
  rodata.raddr = aligned(text.raddr + text.rsize, PE_FILE_ALIGN)
                                                    - PE_FILE_ALIGN;
  rodata.rsize = aligned(rodata.vsize, PE_FILE_ALIGN);
  rodata.chars = 0x40000040; // r-- inited

  int imagesz = PE_SEC_ALIGN;
  imagesz += aligned(text.vsize, PE_SEC_ALIGN);
  imagesz += aligned(rodata.vsize, PE_SEC_ALIGN);

  // generate PE header
  emit_headers(imagesz);

ELVM IRとEBCの対応

ELVM IRはA, B, C, D, SP, BPの6個のレジスタを持つ．一方EBCはR0, R1, R2, R3, R4, R5, R6, R7, IP, FLAGSの10個のレジスタを持つ．このうちR0はスタックポインタとして予約されているため，以下のように対応させる．なお，R7は保存する必要のないレジスタとした．

static int EBCREG[] = { 
  1, // A - R1
  2, // B - R2
  3, // C - R3
  4, // D - R4
  5, // BP - R5
  6, // SP - R6
  7, // R7 - free register
  0, // R0 - stack pointer
};

前述の通り，ELVM IRとEBCにはsemantic gapが存在するため，これを埋めるように実装を行う．

setcc

ELVM IRにおいてEQ, NE, LT, GT, LE, GEなどのsetcc命令は srcとdstの2つのオペランドを持ち， dstとsrcを比較し結果をdstに0, 1で代入するというものである．

一方EBCではCMP命令が存在するが，これはOperand1とOperand2の2つオペランドを持ち，これらを比較して結果をFLAGSの0-bitにあるCフラグを設定するというものである． ELVM IRのsetccと対応させるためには次の2つの問題がある．

CMP命令の結果をOperand1に代入する必要がある．
ELVM IRにあるLT, GTに相当するものが存在しない．

1つ目の問題については以下のようなコードを生成することで対応させる． CMP命令の結果によって設定されたCフラグを元にconditional branchを行いそれぞれ飛んだ先でdstの値を設定する．なお，CMP命令にはELVM IRのNEに相当するものが存在しないが， conditional branchの設定を変えることでこれに対応できる．

    CMP32 dst, src
    JMP8[cc/cs] .L1
.L0:
    MOVIdd dst, 0x01
    JMP8 .L2
.L1:
    MOVIdd dst, 0x00
    JMP8 .L2
.L2

2つ目の問題についてELVM IRでは扱う値が整数のみであるため，以下のようなコードで対応できる．まずGTであればGE，LTであればLEで比較を行いその結果が0であればそのまま0をdstに代入する．結果が1であればさらにEQで比較を行う．

    CMP32 dst, src
    JMP8cc .L1
    CMPeq dst, src
    JMP8cs .L1
.L0:
    MOVIdd dst, 0x01
    JMP8 .L2
.L1:
    MOVIdd dst, 0x00
    JMP8 .L2
.L2

jcc

ELVM IRのJEQ, JNE, JLT, JGT, GLE, JGEなどのjcc命令についても setcc命令と同様である．ただし，ジャンプを行う点で大きく異なり，前述のpc2addrテーブルを用いる． pc2addrは.rodataに存在するため.rodataの先頭アドレスを取得し ELVM IRのプログラムカウンタの値を添字として目的のアドレスの値を取得する．以下が該当部分のコードである．

    // MOVREL R1, rodata
    emit_2(0xb9, EBCREG[R1]);
    emit_le(rodata.vaddr - (text.vaddr + emit_cnt() + 4));
    emit_ebc_mov_imm(R2, 0x04);
    emit_2(0x4e, (EBCREG[R2] << 4) + EBCREG[R7]); // MUL64 R7, R2
    emit_2(0x4c, (EBCREG[R1] << 4) + EBCREG[R7]); // ADD64 R7, R1
    emit_2(0x23, 0x80 + (EBCREG[R7] << 4) + EBCREG[R7]); // MOVdd R7, @R7

PUTC/GETC

EBCは単体では外部にアクセスすることができない．そのため，UEFIのnativeの機能をCALLexにより呼び出すことで文字の読み書きを実現する．ここではPUTCを例に挙げる．

UEFIでは文字の出力はSystemTableに含まれるConOutがStdErrを利用する．これらはSimple Text Output Protocolであり，実際に文字の出力を行うのは OutputString()である，

typedef
EFI_STATUS
(EFIAPI *EFI_TEXT_STRING) (
    IN EFI_SIMPLE_TEXT_OUTPUT_PROTOCOL  *This,
    IN CHAR16                           *String
);

ここに示すように第2引数に出力したい文字列へのポインタを渡すようになっている． EBCの呼出規約はCDECLであり，関数の引数は全てスタック経由で渡すように定められている．この場合，逆順にStringが先にスタックにプッシュされることとなる，ここでStringはCHAR16のポインタであることに注意したい．

渡されるStringはEBCのバックエンドではスタック上に確保した8-byteの領域となっている．以下に対応するコードを示す．

      emit_ebc_mov(R7, &inst->src);
      emit_ebc_mov_imm(R2, 0xff00);
      emit_2(0x6b, EBCREG[R2]); // PUSH64 R2; String
      emit_ebc_mov_reg(R2, R0);
      // MOVbw @R2, R7
      emit_2(0x1d, (EBCREG[R7] << 4) + 0x08 + EBCREG[R2]);

最初にR7に出力したい文字を代入し，R2に0xff00を代入する． R2をプッシュしスタック上にStringとなる領域を確保する． R2にスタックポインタR0の値を代入しR7の値を確保した領域にコピーする．以上の操作でR2の指すスタック上の領域は次のようになる．

00 00 00 00 00 00 ff xx

ここでxxは出力される文字であり，ff以降の00 00は終端文字として扱われる．間にffを入れている理由については後述する．

次にCALLexを呼ぶためにConOutのOutputString()のアドレスを計算する．ここで注意したいのはSystemTableのアドレスはnativeなものであり，アドレスは環境依存である点である． EBCにはNatural Indexと呼ばれる環境依存のアドレスに対応するための仕様が存在するためこれを用いてアドレスを計算する．

UEFIのイメージのエントリポイントからConOutのOutputString()までは SystemTable->ConOut->OutputStringとたどれるようになっている．

R1にOutputString()のアドレス，R2にStringのアドレスが代入されたのでこれらをプッシュしてCALLexを呼ぶ．

      emit_4(0x60, 0x07, 0x28, 0x00); // MOVqw R7, R0 (0, +40)
      emit_4(0x72, 0xf1, 0x41, 0x10); // MOVn R1, @R7(.SystemTable)
      emit_4(0x72, 0x91, 0x85, 0x21); // MOVn R1, @R1(.ConOut)
      emit_2(0x35, 0x02); // PUSHn R2
      emit_2(0x35, 0x01); // PUSHn R1
      emit_6(0x83, 0x29, 0x01, 0x00, 0x00, 0x10); // CALLEX @R1(.OutputString)

終端文字の扱いについて

TianoCoreの実装ではCHAR_NULL=0x0000を終端文字としているが， ELVMのテストでは標準入出力を用いてバイナリの入出力を行っている．このため，出力したいCHAR16文字の後半を0x00としてしまうと期待される出力が0x00だった場合に終端文字として扱われてしまう．そこで出力されるCHAR16の後半を0xffで埋めることでこれを回避する．実際に文字を出力する際には0x00ffでマスクをかけて文字を得る．

テスト

以上のように実装したEBCバックエンドだが， ELVMのテストはUnix-likeな環境を想定しており，UEFI Shellではテストができない．そこで以前に作成したユーザ空間で動作するEBCの実装である ebcvm を用いてテストを行った． ebcvmについては ebcvm: A Usermode EFI Byte Code Virtual Machine で紹介している．

ELVMのテストで生成されたバイナリの一部はQEMU上のOVMFで実際に動作する．以下はCで書かれたfizzbuzzの実行結果の一部である．

FS0:\bin\> fizzbuzz_fast.c.eir.ebc
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23