2016年2月5日 星期五

實作一個簡單的 virtual machine

萬事起頭難
雖然標題是《實作一個簡單的 virtual machine》, 不過其實已經有現成的程式碼了, 這篇主要在討論這個 virtual machine 的設計。

對虛擬機器 (virtual machine 後文以 vm 簡稱) 一直很好奇, 買了 2 本 jvm 的書籍 (fig 1), 不過對 java 實在提不起什麼興趣, 只看過封面。而 sicp chapter 5 也有介紹 vm, 不過 scheme 語法和寫程式的思維太奇怪了, 很難頓悟, 我努力了很久, 沒什麼大突破。

手把手教你构建 C 语言编译器 - 手把手教你构建 C 语言编译器(2)——虚拟机》提供了一個很簡單的 vm 實作。總共只要 4 個暫存器, pc, sp, bp, ax, 再搭配上 38 個指令, 就可以將 c 語言的部份語法結果執行在這台 vm 上, 實在是太神了, 重點是她很簡單, 可以在短時間內學成。我打算以這系列來學習編譯器, 就先從 vm 這章開始吧!

這個 vm 雖然簡單, 但沒簡單到看過去就能理解, 我一開始先觀察 source code 和轉成 machine code 之間的對應關係, 試著去理解裡頭的 38 個指令, 不過人家把 vm 的 code 都寫完了, 那我要幹嘛? 我想辦法把她看懂, 並實作了除錯命令, 類似 gdb 的指令, 原本只是為了方便我學習這個 vm, 後來愈幹愈起勁, 就變成這樣了。我還加入 break pointer 和 continue 等命令, 好像搞錯學習方向了。

原文已經對這些指令有了些許介紹, 我補充一下自己的心得:
  1. IMM arg,
  2. JMP arg,
  3. CALL arg:
    push 下一個 pc (function return 後回 pop 這個值到 pc), 將目前的 pc 改成 arg 的值。
  4. JZ arg:
  5. JNZ arg:
  6. LEA arg: 使用 bp 來存取 function 裡頭的區域變數, 取出這些區域變數的位址, 存到 ax。
    ex:
    void f1()
    {
      int i,j;
      i=5;
      j=6;
      printf("%d\n", i, j);
    }
    
    LEA 0xffffffff(-1) 就是將 i 變數的位址存到 ax (bp 指到的位址減一, 但是 bp 是 int*, 所以其實是減四)。
  7. ENT arg: push bp; bp = sp; sp = sp - ent_arg
  8. LEV arg: sp = bp; bp = pop_stack; pc = pop_stack (這是 call 指令先 push 下一個要執行的指令而來的值)
  9. ADJ arg: function 的參數是用 push 到 stack 傳入的, 所以在執行完這個 function 後, 要用 ADJ 加回 stack 的指標。
    ex: push arg1; push arg2; push arg3; call func; adj 3
  10. LI ,
  11. LC ,
  12. SI: pop_stack, 將 ax 的值存到 pop_stack 的位址上。
    int main(int argc, char **argv)
      {
        int i;
    
        i=2;
        return 0;
      }
      
    i=2; 會用到 SI
  13. SC ,
  14. PUSH: 先將 sp - 4 byte, 在把 ax 的值存到 sp 指到的 stack。
    ex: *--sp=ax
  15. OR ,
  16. XOR ,
  17. AND ,
  18. EQ ,
  19. NE ,
  20. LT ,
  21. GT ,
  22. LE ,
  23. GE ,
  24. SHL ,
  25. SHR ,
  26. ADD:
    pop_stack 的那個值 + ax 的值
  27. SUB ,
  28. MUL ,
  29. DIV ,
  30. MOD ,
  31. OPEN,
  32. READ,
  33. CLOS,
  34. PRTF,
  35. MALC,
  36. MSET,
  37. MCMP,
  38. EXIT

本來這程式是可以自己編譯自己的 (中國術語是「自舉」), 不過再被我加入了一堆亂七八糟的程式碼後, 已經沒辦法這樣做了。

下方的影片展示這個 debug 功能, 很類似 gdb 吧!



我 fork 了原作者的專案:
https://github.com/descent/write-a-C-interpreter



fig 1. java virtual machine books

7 則留言:

  1. 不考慮直接讀Lua嗎,Lua interpreter相比其他程式語言的實現而言真的乾淨許多,大約20k行,大陸也有很多系列文章是分析Lua的內部機制

    回覆刪除
  2. lua 不熟, 還是比較喜歡 c 系列的語言, 謝謝你的資訊。

    回覆刪除
  3. 陳鐘城老師的系統程式一書,也有簡單的VM & simplified C compiler實作。

    回覆刪除
  4. Mars Cheng: 謝謝,那本有我, 不過忘記翻來看了。

    回覆刪除
  5. Mars Cheng: 原來 "軟體學徒 forever" 是你的 blog, 感謝, 受惠於其中不少文章。

    回覆刪除
  6. 不過很久沒更新了,應該保持寫作記錄的習慣才對。 :D

    回覆刪除
  7. 台灣工時真的高的不像話, 這樣的事情真的不容易維持。

    回覆刪除

使用 google 的 reCAPTCHA 驗證碼, 總算可以輕鬆留言了。

我實在受不了 spam 了, 又不想讓大家的眼睛花掉, 只好放棄匿名留言。這是沒辦法中的辦法了。留言的朋友需要有 google 帳號。