QEMU Internal – Block Chaining 3/3

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

2. Block Chaining

由 guest binary -> TCG IR 的過程中,gen_goto_tb 會做 block chaining 的準備。 我們先來看何時會呼叫到 gen_goto_tb。以 i386 為例,遇到 guest binary 中的條件分支和直接跳轉都會呼叫 gen_goto_tb (target-i386/translate.c)。這邊以條件分支當例子:

static inline void gen_jcc(DisasContext *s, int b,
                           target_ulong val, target_ulong next_eip)
{
    int l1, l2, cc_op;
 
    cc_op = s->cc_op;
    gen_update_cc_op(s);
    if (s->jmp_opt) { // use direct block chaining for direct jumps
        l1 = gen_new_label();
        gen_jcc1(s, cc_op, b, l1);
 
        gen_goto_tb(s, 0, next_eip); // 我猜是 taken
 
        gen_set_label(l1);
        gen_goto_tb(s, 1, val); // 我猜是 not taken
        s->is_jmp = DISAS_TB_JUMP;
    } else {
 
      /* 忽略不提 */
 
    }
}
  • gen_goto_tb。強烈建議閱讀 Porting QEMU to Plan 9: QEMU Internals and Port Strategy 2.2.3 和 2.2.4 節,也別忘了 SOURCEARCHIVE.com
  • // tb_num 代表目前 tb block linking 分支情況。eip 代表跳轉目標。
    static inline void gen_goto_tb(DisasContext *s, int tb_num, target_ulong eip)
    {
        TranslationBlock *tb;
        target_ulong pc;
     
        // s->pc 代表翻譯至目前 guest binary 的所在位址。tb->pc 表示 guest binary 的起始位址。
        // 注意! 這裡 s->cs_base + eip 代表跳轉位址; s->pc 代表目前翻譯到的 guest pc。
        pc = s->cs_base + eip; // 計算跳轉目標的 pc
        tb = s->tb; // 目前 tb
        // http://lists.nongnu.org/archive/html/qemu-devel/2011-08/msg02249.html
        // http://lists.gnu.org/archive/html/qemu-devel/2011-09/msg03065.html
        // 滿足底下兩個條件之一,則可以做 direct block linking
        // 第一,跳轉目標和目前 tb 起始的 pc 同屬一個 guest page。
        // 第二,跳轉目標和目前翻譯到的 pc 同屬一個 guest page。
        if ((pc & TARGET_PAGE_MASK) == (tb->pc & TARGET_PAGE_MASK) ||
            (pc & TARGET_PAGE_MASK) == ((s->pc - 1) & TARGET_PAGE_MASK))  {
            // 如果 guest jump 指令和其跳轉位址同屬一個 guest page,則做 direct block linking。
     
            tcg_gen_goto_tb(tb_num); // 生成準備做 block linking 的 TCG IR。詳情請見之後描述。
     
            // 更新 env 的 eip,使其指向此 tb 之後欲執行指令的位址。
            // tb_find_fast 會用 eip 查找該 TB 是否已被翻譯過。
            gen_jmp_im(eip);
     
            // 最終回到 QEMU tcg_qemu_tb_exec,賦值給 next_tb。
            // 注意! tb_num 會被 next_tb & 3 取出,由此可以得知 block chaining 的方向。
            tcg_gen_exit_tb((tcg_target_long)tb + tb_num);
        } else {
            /* jump to another page: currently not optimized */
            gen_jmp_im(eip);
            gen_eob(s);
        }
    }
    • tcg_gen_goto_tb 生成 TCG IR。
    • static inline void tcg_gen_goto_tb(int idx)
      {
          tcg_gen_op1i(INDEX_op_goto_tb, idx);
      }
    • tcg_out_op (tcg/i386/tcg-target.c) 將 TCG IR 翻成 host binary。注意! 這邊利用 patch jmp 跳轉位址達成 block linking。
    • static inline void tcg_out_op(TCGContext *s, TCGOpcode opc,
                                    const TCGArg *args, const int *const_args)
      {
          case INDEX_op_goto_tb:
              if (s->tb_jmp_offset) {
                  /* direct jump method */
                  tcg_out8(s, OPC_JMP_long); /* jmp im */
                  // 紀錄將來要 patch 的地方。
                  s->tb_jmp_offset[args[0]] = s->code_ptr - s->code_buf;
                  // jmp 的參數為 jmp 下一個指令與目標的偏移量。
                  // 如果還沒做 block chaining,則 jmp 0 代表 fall through。
                  tcg_out32(s, 0);
              } else {
       
                  /* 在此忽略 */
       
              }
              // 留待將來 "reset" direct jump 之用。
              s->tb_next_offset[args[0]] = s->code_ptr - s->code_buf;
              break;
      }

回答上一篇最後留下的問題。在還未 patch code cache 中的分支跳轉指令的跳轉位址,它會 fall through,還記得 jmp 0 嗎? 我這邊在列出 gen_goto_tb 的部分內容:

tcg_gen_goto_tb(tb_num);
 
// Fall through
 
// 更新 env 的 eip,使其指向此 tb 之後欲執行指令的位址。
// tb_find_fast 會用 eip 查找該 TB 是否已被翻譯過。
gen_jmp_im(eip);
 
// 最終回到 QEMU tcg_qemu_tb_exec,賦值給 next_tb。
// 注意! tb_num 會被 next_tb & 3 取出,由此可以得知 block chaining 的方向。
tcg_gen_exit_tb((tcg_target_long)tb + tb_num);

目前執行的 tb 會賦值給 next_tb (末兩位編碼 block chaining 的方向)。等待下一次迴圈,tb_find_fast 回傳 next_tb 的下一個 tb。

if (next_tb != 0 && tb->page_addr[1] == -1) {
    // 這邊利用 TranlationBlock 指針的最低有效位後兩位指引 block chaining 的方向。
    // next_tb -> tb
    tb_add_jump((TranslationBlock *)(next_tb & ~3), next_tb & 3, tb);
}

That’s it! That’s how direct block chaining is done in QEMU, I think… 🙂

QEMU Internal – Block Chaining 2/3

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

2. Block Chaining

我們再回到 cpu_exec (cpu-exec.c) 的內層迴圈。這邊主要看 tb_add_jump。

if (next_tb != 0 && tb->page_addr[1] == -1) {
    // 這邊利用 TranlationBlock 指針的最低有效位後兩位指引 block chaining 的方向。
    // next_tb -> tb
    tb_add_jump((TranslationBlock *)(next_tb & ~3), next_tb & 3, tb);
}
 
// 這邊要注意到,QEMU 利用 TranslatonBlock 指針後兩位必為零的結果
// 做了一些手腳。QEMU 將其末兩位編碼成 0、1 或 2 來指引 block chaing
// 的方向。這種技巧在 QEMU 用得非常嫻熟。 
next_tb = tcg_qemu_tb_exec(tc_ptr);
  • tb_add_jump 呼叫 tb_set_jmp_target 做 block chaining 的 patch。另外,會利用 tb 的 jmp_next 和 tb_next 的 jmp_first 把 block chaining 中的 TranslationBlock 串成一個 circular list。這是以後做 block *unchaining* 之用。再複習一下 TranslationBlock,
        struct TranslationBlock*        code cache (host binary)
                tb->tc_ptr        ->            TB
    

    請注意! 當我們講 TB,可能是指 TranslationBlock,也可能是指 code cache 中的 TB。好! 當我們 patch code cache 中的 TB,將它們串接在一起。我們同時也要把它們相對應的 TranslationBlock 做點紀錄,利用 jmp_first 和 jmp_next 這兩個欄位。

    這邊我先回到 tb_link_page,還記得我留下一些地方沒講嘛? 開始吧! 😉

    // jmp_first 代表跳至此 tb 的其它 TB 中的頭一個。jmp_first 初值為自己,末兩位為 10 (2)。
    // 將來做 block chaining 時,jmp_first 指向跳至此 tb 的其它 TB 中的頭一個,tb1,末兩位
    // 為 00 或 01,這代表從 tb1 的哪一個分支跳至此 tb。
    tb->jmp_first = (TranslationBlock *)((long)tb | 2);
     
    // jmp_next[n] 代表此 tb 條件分支的目標 TB。
    // 注意! 如果目標 TB,tb2,孤身一人,jmp_next 就真的指向 tb2 (符合初次看到 jmp_next 所想
    // 的語意)。
    //
    // 如果已有其它 TB,tb3,跳至 tb2,則賦值給 tb->jmp_next 的是 tb2 的 jmp_first,也就是
    // tb3 (末兩位編碼 tb3 跳至 tb2 的方向)。
    tb->jmp_next[0] = NULL;
    tb->jmp_next[1] = NULL;
     
    // tb_next_offset 代表此 TB 在 code cache 中分支跳轉要被 patch 的位址 (相對於其 code cache
    // 的偏移量),為了 direct block chaining 之用。
    if (tb->tb_next_offset[0] != 0xffff)
        tb_reset_jump(tb, 0);
    if (tb->tb_next_offset[1] != 0xffff)
        tb_reset_jump(tb, 1);

    我們再回來看看 tb_add_jump 做了什麼。:-)

    // block chaining 方向為: tb -> tb_next。n 用來指示 tb 條件分支的方向。
    static inline void tb_add_jump(TranslationBlock *tb, int n,
                                   TranslationBlock *tb_next)
    {
        // jmp_next[0]/jmp_next[1] 代表 tb 條件分支的目標。
        if (!tb->jmp_next[n]) {
            /* patch the native jump address */
            tb_set_jmp_target(tb, n, (unsigned long)tb_next->tc_ptr);
     
            // tb_jmp_remove 會用到 jmp_next 做 block unchaining,這個以後再講。
     
            // tb_next->jmp_first 初值為自己,末兩位設為 10 (2)。
            // 如果已有其它 TB,tb1,跳至 tb_next,則下面這條語句會使得
            // tb->jmp_next 指向 tb1 (末兩位代表 tb1 跳至 tb_next 的方向)。
            // tb_next->jmp_first 由原本指向 tb1 改指向 tb。
            // 有沒有 circular list 浮現在你腦海中? 😉
            tb->jmp_next[n] = tb_next->jmp_first;
     
            // tb_next 的 jmp_first 指回 tb,末兩位代表由 tb 哪一個條件分支跳至 tb_next。
            tb_next->jmp_first = (TranslationBlock *)((long)(tb) | (n));
        }
    }

我們再來看是怎麼 patch code cache 中分支指令的目標地址。依據是否採用 direct jump,tb_set_jmp_target (exec-all.h) 有不同做法。採用 direct jump 的話,tb_set_jmp_target 會根據 host 呼叫不同的 tb_set_jmp_target1。tb_set_jmp_target1 會用到 TB 的 tb_jmp_offset。如果不採用 direct jump 做 block chaining,tb_set_jmp_target 會直接修改 TB 的 tb_next。

  • tb_set_jmp_target (exec-all.h)。
  • static inline void tb_set_jmp_target(TranslationBlock *tb,
                                         int n, unsigned long addr)
    {
        unsigned long offset;
     
        // n 可以為 0 或 1,代表分支跳轉的分向 taken 或 not taken。 
        offset = tb->tb_jmp_offset[n]; // tb 要 patch 的位址相對於 tb->tc_ptr 的偏移量。
        tb_set_jmp_target1((unsigned long)(tb->tc_ptr + offset), addr);
    }
  • tb_set_jmp_target1 (exec-all.h)。
  • #elif defined(__i386__) || defined(__x86_64__)
    static inline void tb_set_jmp_target1(unsigned long jmp_addr, unsigned long addr)
    {
        /* patch the branch destination */
        // jmp 的參數為 jmp 下一條指令與目標地址的偏移量。
        *(uint32_t *)jmp_addr = addr - (jmp_addr + 4);
        /* no need to flush icache explicitly */
    }

你會有這個疑問嗎? 在分支跳轉位址被 patch 到分支跳轉指令之前,它是要跳去哪裡? 🙂

QEMU – block chaining 可以幫助你比較清楚了解 block chaining 如何運作。

QEMU Internal – Block Chaining 1/3

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

2. Block Chaining

先複習一下 QEMU 的流程,目前的情況如底下這樣:

    QEMU -> code cache -> QEMU -> code cache -> ...

之前提到,QEMU 是以一個 translation block 為單位進行翻譯並執行。這也就是說,每當在 code cache 執行完一個 translation block 之後,控制權必須交還給 QEMU。這很沒有效率。理想情況下,大部分時間應該花在 code cache 中執行,只要在必要情況下才需要回到 QEMU。基本想法是把 code cache 中的 translation block 串接起來。只要 translation block 執行完之後,它的跳躍目標確定且該跳躍目標也已經在 code cache 裡,那我們就把這兩個 translation block 串接起來。這個就叫做 block chaining/linking。

在 QEMU 中,達成 block chaining 有兩種做法: 第一,採用 direct jump。此法直接修改 code cache 中分支指令的跳躍目標,因此依據 host 有不同的 patch 方式。第二,則是透過修改 TranslationBlock 的 tb_next 欄位達成 block chaining。exec-all.h 中定義那些 host 支援使用 direct jump。

這裡只介紹 direct jump。我們先回到 cpu_exec (cpu-exec.c) 的內層迴圈。

tb = tb_find_fast(env);
 
if (tb_invalidated_flag) {
    next_tb = 0; // 注意! next_tb 也被用來控制是否要做 block chaining。
    tb_invalidated_flag = 0;
}
 
// 注意!! next_tb 的名字會讓人誤解。block chaining 的方向為: next_tb -> tb。
// next_tb 不為 NULL 且 tb (guest binary) 不跨 guest page 的話,做 block
// chaining。原因之後再講。
if (next_tb != 0 && tb->page_addr[1] == -1) {
    // 這邊利用 TranlationBlock 指針的最低有效位後兩位指引 block chaining 的方向。
    tb_add_jump((TranslationBlock *)(next_tb & ~3), next_tb & 3, tb);
}
 
// 執行 TB,也就是 tc_ptr 所指到的位址。注意,產生 TCG IR 的過程中,在 block 的最後會是
// exit_tb addr,此 addr 是正在執行的 TranslationBlock 指針,同時也是 tcg_qemu_tb_exec
// 的回傳值。該位址後兩位會被填入 0、1 或 2 以指示 block chaining 的方向。
next_tb = tcg_qemu_tb_exec(tc_ptr);

是不是有點暈頭轉向? 我們來仔細檢驗 guest binary -> TCG IR -> host binary 到底怎麼做的。在一個 translation block 的結尾,TCG 都會產生 TCG IR exit_tb。我們來看看。:-)

  • tcg_gen_exit_tb (tcg/tcg-op.h) 呼叫 tcg_gen_op1i 生成 TCG IR,其 opcode 為 INDEX_op_exit_tb (還記得 tcg.i 裡的 TCGOpcode 嗎?),operand 為 val。
  • // 一般是這樣呼叫: tcg_gen_exit_tb((tcg_target_long)tb + tb_num);
    // 注意! 請留意其參數: (tcg_target_long)tb + tb_num。
    static inline void tcg_gen_exit_tb(tcg_target_long val)
    {
        // 將 INDEX_op_exit_tb 寫入 gen_opc_buf; val 寫入 gen_opparam_buf。
        tcg_gen_op1i(INDEX_op_exit_tb, val);
    }
  • tcg/ARCH/tcg-target.c 根據 TCG IR 產生對應 host binary。以 i386 為例: (關於每一行的作用,我是憑經驗用猜的。如有錯請指正。)
  • static inline void tcg_out_op(TCGContext *s, int opc,
                                  const TCGArg *args, const int *const_args)
    {
        // 總和效果: 返回 QEMU。
        //           next_tb = tcg_qemu_tb_exec(tc_ptr);
        //
        // 圖示:
        // struct TranslationBlock*         code cache
        //        next_tb->tc_ptr    ->        tb
        //
        // next_tb 的末兩位編碼 next_tb 條件分支的方向。
        // 等待下一次迴圈取得 tb = tb_find_fast(),
        // 試圖做 block chaining: next_tb -> tb 
        //
        case INDEX_op_exit_tb:
            // QEMU 把跳至 code cache 執行當作是函式呼叫,EAX 存放返回值。
            // 將 val 寫進 EAX,val 是 (tcg_target_long)tb + tb_num。 
            tcg_out_movi(s, TCG_TYPE_I32, TCG_REG_EAX, args[0]);
     
            // e9 是 jmp 指令,後面的 operand 為相對偏移量,將會加上 eip。
            // 底下兩條的總和效果是跳回 code_gen_prologue 中 prologue 以後的位置。
            tcg_out8(s, 0xe9); /* jmp tb_ret_addr */
            // tb_ret_addr 在 tcg_target_qemu_prologue 初始成指向
            // code_gen_prologue 中 prologue 以後的位置。
            // 生成 host binary 的同時,s->code_ptr 會移向下一個 code buffer 的位址。
            // 所以要減去 4。
            tcg_out32(s, tb_ret_addr - s->code_ptr - 4);
            break;
    }
    • tcg_out_movi 將 arg 移至 ret 代表的暫存器。
    • static inline void tcg_out_movi(TCGContext *s, TCGType type,
                                      int ret, int32_t arg)
      {
          if (arg == 0) {
              /* xor r0,r0 */
              tcg_out_modrm(s, 0x01 | (ARITH_XOR << 3), ret, ret);
          } else {
              // move arg 至 ret
              // 0xb8 為 move,ret 代表目地暫存器。
              // 0xb8 + ret 合成一個 opcode。
              tcg_out8(s, 0xb8 + ret);
              tcg_out32(s, arg);
          }
      }

小結一下,QEMU 函式名稱命名慣例為:

  • tcg_gen_xxx – 產生 TCG Opcode 和 operand 至 gen_opc_buf 和 gen_opparam_buf。
  • tcg_out_xxx – 產生 host binary 至 TCGContext 所指的 code cache。

QEMU Internal – Tiny Code Generator (TCG) 2/2

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

1.2 TCG Flow

介紹完一些資料結構之後,我開始介紹 cpu_exec 的流程。底下複習一下 process mode 的流程:

cpu_loop (linux-user/main.c) -> cpu_x86_exec/cpu_exec (cpu-exec.c)

cpu_exec 有兩層 for 迴圈。我們先看內層:

next_tb = 0; /* force lookup of first TB */
for(;;) {
 
    tb = tb_find_fast();
 
    tc_ptr = tb->tc_ptr;
 
    next_tb = tcg_qemu_tb_exec(tc_ptr);
}
  • tb_find_fast 會先試圖查看目前 pc (guest virtual address) 是否已有翻譯過的 host binary 存放在 code cache。
  • // pc = eip + cs_base
    cpu_get_tb_cpu_state(env, &pc, &cs_base, &flags);
     
    // CPUState 中的 tb_jmp_cache 即是做此用途。
    tb = env->tb_jmp_cache[tb_jmp_cache_hash_func(pc)];
     
    // 檢查該 tb 是否合法。這是因為不同的 eip + cs_base 可能會得到相同的 pc。
    if (unlikely(!tb || tb->pc != pc || tb->cs_base != cs_base ||
                   tb->flags != flags)) {
            tb = tb_find_slow(pc, cs_base, flags);
    }
     
    // code cache 已有翻譯過的 host binary,返回 TranslationBlock。
    return tb;
  • tb_find_slow 以 pc 對映的物理位址 (guest physcal address) 查找 TB。如果成功,則將該 TB 寫入 env->tb_jmp_cache; 若否,則進行翻譯。
  • phys_pc = get_page_addr_code(env, pc);
    phys_page1 = phys_pc & TARGET_PAGE_MASK;
     
    // 除了 env->tb_jmp_cache 這個以 guest virtual address 為索引的緩存之外,
    // QEMU 還維護了一個 tb_phys_hash,這個是以 guest physical address 為索引。
    h = tb_phys_hash_func(phys_pc);
    ptb1 = &tb_phys_hash[h];
    for (;;) {
     
      not_found:
     
      found:
     
      // TranslationBlock 中的 phys_hash_next 用在這裡。
      // 如果 phys_pc 索引到同一個 tb_phys_hash 欄位,用 phys_hash_next 串接起來。
      ptb1 = &tb->phys_hash_next;
    }
     
    not_found:
      tb = tb_gen_code(env, pc, cs_base, flags, 0);
     
    found:
      env->tb_jmp_cache[tb_jmp_cache_hash_func(pc)] = tb;
      return tb;

    這裡小結一下流程。

    cpu_exec (cpu-exec.c) -> tb_find_fast (cpu-exec.c)
      -> tb_find_slow (cpu-exec.c)
    

    QEMU 先以 guest virtual address (GVA) 查找是否已有翻譯過的 TB,再以 guest physical address (GPA) 查找是否已有翻譯過的 TB。

    如果沒有翻譯過的 TB,開始進行 guest binary -> TCG IR -> host binary 的翻譯。大致流程如下:

    tb_gen_code (exec.c) -> cpu_gen_code (translate-all.c)
      -> gen_intermediate_code (target-i386/translate.c)
      -> tcg_gen_code (tcg/tcg.c) -> tcg_gen_code_common (tcg/tcg.c)
    
    • tb_gen_code 配置內存給 TB (TranslationBlock),再交由 cpu_gen_code。
    • // 注意! 這裡會將 GVA 轉成 GPA。phys_pc 將交給之後的 tb_link_page 使用。
      phys_pc = get_page_addr_code(env, pc);
      tb = tb_alloc(pc);
      if (!tb) {
        // 清空 code cache
      }
       
      // 初始 tb
       
      // 開始 guest binary -> TCG IR -> host binary 的翻譯。
      cpu_gen_code(env, tb, &code_gen_size);
       
      // 將 tb 加入 tb_phys_hash 和二級頁表 l1_map。
      // phys_pc 和 phys_page2 分別代表 tb (guest pc) 對映的 GPA 和所屬的第二個
      // 頁面 (如果 tb 代表的 guest binary 跨頁面的話)。
      tb_link_page(tb, phys_pc, phys_page2);
      return tb;

    我底下分別針對 cpu_gen_code 和 tb_link_page 稍微深入的介紹一下。

    • cpu_gen_code 負責 guest binary -> TCG IR -> host binary 的翻譯。
    • // 初始 TCGContext 的 gen_opc_ptr 和 gen_opparam_ptr,使其分別指向
      // gen_opc_buf 和 gen_opparam_buf。gen_opc_buf 和 gen_opparam_buf
      // 分別存放 TCGOpcode 和 operand。
      tcg_func_start(s);
       
      // 呼叫 gen_intermediate_code_internal 產生 TCG IR
      gen_intermediate_code(env, tb);
       
      // TCG IR -> host binary
      gen_code_size = tcg_gen_code(s, gen_code_buf);
    • gen_intermediate_code_internal (target-*/translate.c) 初始化並呼叫 disas_insn 反組譯 guest binary 成 TCG IR。disas_insn 呼叫 tcg_gen_xxx (tcg/tcg-op.h) 產生 TCG IR。分別將 opcode 寫入 gen_opc_ptr 指向的緩衝區 (translate-all.c 裡的 gen_opc_buf); operand 寫入 gen_opparam_ptr 指向的緩衝區 (translate-all.c 裡的 gen_opparam_buf)。
    • tcg_gen_code (tcg/tcg.c) 呼叫 tcg_gen_code_common (tcg/tcg.c) 將 TCG IR 轉成 host binary。
    • tcg_reg_alloc_start(s);
       
      s->code_buf = gen_code_buf;
      // host binary 會寫入 TCGContext s 的 code_ptr 所指向的緩衝區。
      s->code_ptr = gen_code_buf;

      至此,guest binary -> TCG IR -> host binary 算是完成了。剩下把 TranslationBlock (TB) 納入 QEMU 的管理,這是 tb_link_page 做的事。

    • tb_link_page (exec.c) 把新的 TB 加進 tb_phys_hash 和 l1_map 二級頁表。 tb_find_slow 會用 pc 對映的 GPA 的哈希值索引 tb_phys_hash。
    • /* 把新的 TB 加進 tb_phys_hash */
      h = tb_phys_hash_func(phys_pc);
      ptb = &tb_phys_hash[h];
      // 如果兩個以上的 TB 其 phys_pc 的哈希值相同,則做 chaining。
      tb->phys_hash_next = *ptb;
      *ptb = tb; // 新加入的 TB 放至 chaining 的開頭。
       
      // 在 l1_map 中配置 PageDesc 給 TB,並設置 TB 的 page_addr 和 page_next。
      tb_alloc_page(tb, 0, phys_pc & TARGET_PAGE_MASK);
      if (phys_page2 != -1) // TB 對應的 guest binary 跨頁
          tb_alloc_page(tb, 1, phys_page2);
      else
          tb->page_addr[1] = -1;
       
      // 以下和 block chaining 有關,留待下次再講,這邊暫且不提。
      tb->jmp_first = (TranslationBlock *)((long)tb | 2);
    • tb_alloc_page (exec.c) 設置 TB 的 page_addr 和 page_next,並在 l1_map 中配置 PageDesc 給 TB。
    • static inline void tb_alloc_page(TranslationBlock *tb,
                                       unsigned int n, tb_page_addr_t page_addr)
      {
        // 代表 tb (guest binary) 所屬 guest page。
        tb->page_addr[n] = page_addr;
        // 在 l1_map 中配置一個 PageDesc,返回該 PageDesc。
        p = page_find_alloc(page_addr >> TARGET_PAGE_BITS, 1);
        // 將該頁面目前第一個 TB 串接到此 TB。將來有需要將某頁面所屬所有 TB 清空。
        tb->page_next[n] = p->first_tb;
        // n 為 1 代表 tb 對應的 guest binary 跨 page。
        p->first_tb = (TranslationBlock *)((long)tb | n);
        // PageDesc 會維護一個 bitmap,這是給 SMC 之用。這裡不提。
        invalidate_page_bitmap(p);
      }

這裡先回顧一下,QEMU 查看當前 env->pc 是否已翻譯過。若否,則進行翻譯。

tb_find_fast (cpu-exec.c) -> tb_find_slow (cpu-exec.c)
  -> tb_gen_code (exec.c)

tb_gen_code 講到這裡,guest binary -> host binary 已翻譯完成,相關資料結構也已設置完畢。返回 TB (TranslationBlock *) 給 tb_find_fast。

tb = tb_find_fast();
 
tc_ptr = tb->tc_ptr; // tc_ptr 指向 code cache (host binary)
 
next_tb = tcg_qemu_tb_exec(tc_ptr);

很好,我們準備從 QEMU 跳入 code cache 開始執行了。:-) tcg_qemu_tb_exec 被定義在 tcg/tcg.h。

#define tcg_qemu_tb_exec(tb_ptr) ((long REGPARM (*)(void *))code_gen_prologue)(tb_ptr)

(long REGPARM (*)(void *)) 將 code_gen_prologue 轉型成函式指針,void * 為該函式的參數,返回值為 long。REGPARM 指示 GCC 此函式透過暫存器而非棧傳遞參數。至此,(long REGPARM (*)(void *)) 將數組指針 code_gen_prologue 轉型成函式指針。tb_ptr 為該函式指針的參數。綜合以上所述,code_gen_prologue 被視為一函式,其參數為 tb_ptr,返回當前 TB (tc_ptr 代表的 TB,等講到 block chaining 會比較清楚)。code_gen_prologue 所做的事為一般函式呼叫前的 prologue,之後將控制交由 tc_ptr 指向的 host binary 並開始執行。

2

QEMU Internal – Tiny Code Generator (TCG) 1/2

Copyright (c) 2011 陳韋任 (Chen Wei-Ren)

前言

因為工作上的關係,必須接觸 QEMU。雖然網路上有不少文件,但總覺得講得不夠深入。QEMU 是一個仿真器 (emulator),可以 process mode 或是 system mode 運行。process mode 可以運行不同 ISA 同一 OS 的 binary; system mode 可以在當前作業系統上運行另外一個 OS。我在收集各方資料,閱讀代碼和在郵件列表上發問之後,覺得略有心得。在此對 QEMU internal 作一個較為深入的介紹。憑我個人之力,難免有疏漏或是錯誤。權且當作拋磚引玉吧。希望各位不吝指教。

0. 術語、線上資源和技巧

對 QEMU 而言,被仿真的平台被稱為 guest,又稱 target; 運行 QEMU 的平台稱為 host。QEMU 是利用動態翻譯 (dynamic translation) 的技術將 guest binary 動態翻譯成 host binary,並交由 host 運行翻譯所得的 host binary。Tiny Code Generator (TCG) 是 QEMU 中負責動態翻譯的組件。對 TCG 而言,target 有不同的含意,它代表 TCG 是針對哪一個 host 生成 host binary。

網路上對 QEMU 有較為完整描述的文件為:

然而需要注意的是,上述文件在動態翻譯的部分均是針對 QEMU 0.9 版。QEMU 0.9 版以前是使用 dyngen 技術; QEMU 0.10 版以後採用 TCG。雖說如此,但在 QEMU 的其它部分差異不大,上述文件仍可供參考。SOURCEARCHIVE.com 收集了自 QEMU 0.6.1 版至今的所有 QEMU 源代碼。各位可以邊看文件邊看源代碼。

QEMU 極為依賴 macro,這使得直接閱讀源代碼通常無法確定其函數呼叫,或是執行流程倒底為何。請在編譯 QEMU 的時候加上 --extra-cflags="-save-temps",如此可得展開 marco 的 *.i 檔。

其餘部分請見:

1. TCG

TCG 是 QEMU 的核心。其基本流程如下:

guest binary -> TCG IR -> host binary

1.1 TCG IR

TCG 定義了一組 IR (intermediate representation),熟悉 GCC 的各位對此應該不陌生。TCG IR 大致分成以下幾類:

  • Move Operation: mov, movi, …
  • Logic Operation: and, or, xor, shl, shr, …
  • Arithmetic peration: add, sub, mul, div, …
  • Branch Operation: jmp, br, brcond
  • Fuction call: call
  • Memory Operation: ld, st
  • QEMU specific Operation: tb_exit, goto_tb, qemu_ld/qemu_st

請見 tcg/*,特別是 tcg.i,可以看到 TCGOpcode。tcg/README 也別忘了。TCG 在翻譯 guest binary 的時候是以一個 translation block (tb) 為單位,其結尾通常是分支指令。

target-ARCH/* 定義了如何將 ARCH binary 反匯編成 TCG IR。tcg/ARCH 定義了如何將 TCG IR 翻譯成 ARCH binary。

1.2 TCG Flow

先介紹一些資料結構:

  • gen_opc_buf 和 gen_opparam_buf (translate-all.c) 分別放置 TCG Opcode 和 Operand。
  • 如果使用靜態配置的緩衝區,static_code_gen_buffer (exec.c) 即為 code cache,放置 host binary。
  • 在跳入/出 code cache 執行之前/後,要執行 prologue/epilogue,請見 code_gen_prologue (exec.c)。這邊的 prologue/epilogue 就是指 function prologue/epilogue。QEMU 將跳至 code cache (host binary) 執行的過程看成是函式呼叫,故有此 prologue/epilogue。

以 qemu-i386 為例,流程大致如下:

main (linux-user/main.c) -> cpu_exec_init_all (exec.c)
  -> cpu_init/cpu_x86_init (target-i386/helper.c)
  -> tcg_prologue_init (tcg/tcg.c) -> cpu_loop (linux-user/main.c)

函式名之所以會出現 cpu_init/cpu_x86_init,是因為 QEMU 經常使用 #define 替換函式名。cpu_init 是 main 裡呼叫的函式,經 #define 替換後,實際上是 cpu_x86_init (target-i386/helper.c)。GDB 下斷點時請注意此種情況。

這邊只介紹 tcg_prologue_init (tcg/tcg.c) -> cpu_loop (linux-user/main.c) 這一段,因為這一段跟 TCG 較為相關。容我先講 cpu_loop (linux-user/main.c)。

  • cpu_loop (linux-user/main.c) -> cpu_x86_exec/cpu_exec (cpu-exec.c)。cpu_exec 是主要執行迴圈,其結構大致如下:
  • /* prepare setjmp context for exception handling */
    for(;;) {
        if (setjmp(env->jmp_env) == 0) { // 例外處理。
        }
     
        next_tb = 0; /* force lookup of first TB */
        for(;;) {
          // 判斷是否有中斷。若有,跳回例外處理。
     
          next_tb = tcg_qemu_tb_exec(tc_ptr); // 跳至 code cache 執行。
     
        }
    }
  • tcg_prologue_init (tcg/tcg.c) -> tcg_target_qemu_prologue (tcg/i386/tcg-target.c)。如前所述,QEMU 將跳至 code cache (host binary) 執行的過程看成是函式呼叫。不同平台的 calling convention 各有不同,tcg_prologue_init 將產生 prologue/epilogue 的工作轉交 tcg_target_qemu_prologue。
  • static void tcg_target_qemu_prologue(TCGContext *s)
    {
      /* QEMU (cpu_exec) -> 入棧 */
     
      // OPC_GRP5 (0xff) 為 call,EXT5_JMPN_Ev 是其 opcode extension。
      // tcg_target_call_iarg_regs 是函式呼叫負責傳遞參數的暫存器。
      // 跳至 code cache 執行。
      tcg_out_modrm(s, OPC_GRP5, EXT5_JMPN_Ev, tcg_target_call_iarg_regs[0]);
     
      // 此時,s->code_ptr 指向 code_gen_prologue 中 prologue 和 jmp to code cache
      // 之後的位址。
      // tb_ret_addr 是紀錄 code cache 跳回 code_gen_prologue 的哪個地方。
      tb_ret_addr = s->code_ptr;
     
      /* 出棧 -> 返回 QEMU (cpu_exec),確切的講是返回 tcg_qemu_tb_exec */
    }

這邊小結一下。

QEMU -> prologue -> code cache -> epilogue -> QEMU

tb_ret_addr 就是用來由 code cache 返回至 code_gen_prologue,執行 epilogue,再返回 QEMU。

在介紹 cpu_exec 之前,我先介紹幾個 QEMU 資料結構,請善用 SOURCEARCHIVE.com。我們要知道所謂仿真或是虛擬化一個 CPU (ISA),簡單來說就是用一個資料結構 (struct) 儲存該 CPU 的狀態。執行該虛擬 CPU,就是從內存中讀取該虛擬 CPU 的資料結構,運算後再存回去。

  • CPUX86State: 保存 x86 register,eflags,eip,cs,…。不同 ISA 之間通用的資料結構被 QEMU #define 成 CPU_COMMON。一般稱此資料結構為 CPUState。下文所提 env 即為 CPUState。 QEMU 運行虛擬 CPU 都會利用 env 這個變數。
  • TranslationBlock: 之前說過,QEMU 是以一個 translation block 為單位進行翻譯。其中保存此 translation block 對應 guest binary 的 pc, cs_base, eflags。另外,tc_ptr 指向 code cache (host binary)。其它欄位待以後再談。
  • PageDesc: 主要保存 guest page 中的第一個 tb (TranslationBlock *)。這跟 QEMU 內部運作機制有關。某些情況下,guest page (guest binary) 可能被替換或是被寫。這個時候,QEMU 會以 guest page (guest binary) 為單位,清空與它相關聯的 TB (code cache)。這時再回來講 TranslationBlock。TranslationBlock 有底下兩個欄位:
    • page_addr[2]: 存放 TranslationBlock 對應 guest binary 所在的 guest page。注意! guest binary 有可能跨 guest page,故這裡有兩個欄位。
    • page_next[2]: 當透過 PageDesc->first_tb 找到該 guest page 的第一個 tb,tb->page_next 就被用來找尋該 guest page 的下一個 tb。

    再回來講 PageDesc。QEMU 替 PageDesc 維護了一個二級頁表 l1_map。page_find 這個函式根據輸入的 address 搜尋 l1_map,返回 PageDesc。這在以 guest page (guest binary) 為單位,清空與它相關聯的 TB (code cache) 的時候會用到。有一個名字很像的資料結構叫 PhysPageDesc,QEMU 也替它維護一個二級頁表 l1_phys_map。這是在 system mode 做地址轉換之用,這邊不談。

  • TCGContext: 生成 TCG IR 時會用到。
  • DisasContext: 反匯編 guest binary 時會用到。