Cách viết máy ảo (2022)
(jmeiners.com)- Để hiểu cách máy tính hoạt động bên trong và cách ngôn ngữ lập trình được thực thi, tác giả tự triển khai một VM dựa trên C khoảng 250 dòng chạy chương trình assembly trên kiến trúc giáo dục LC-3
- Đối tượng triển khai là một mô hình máy tính nhỏ có 65.536 vị trí bộ nhớ 16-bit, 10 thanh ghi, 16 opcode, cờ điều kiện, trap routine và thanh ghi ánh xạ bộ nhớ
- Vòng lặp thực thi hoạt động theo cấu trúc fetch-decode-execute: đọc lệnh mà
PCtrỏ tới, tăngPC, sau đó diễn giải opcode để thực hiện các lệnh nhưADD,LDI,BR,JMP,TRAP - Việc nạp chương trình đọc origin 16-bit đầu tiên của object file để đặt vào bộ nhớ, rồi byte-swap định dạng big-endian của LC-3 cho phù hợp với định dạng little-endian được dùng trên hầu hết máy tính hiện đại
- Nhập bàn phím và xuất console được xử lý bằng trap routine và các thanh ghi ánh xạ bộ nhớ
KBSR/KBDR; Unix/macOS và Windows cần mã xử lý input buffering terminal khác nhau
Mục tiêu và tiền đề của hướng dẫn
- Theo dõi quá trình tự triển khai máy ảo LC-3 để chạy chương trình ngôn ngữ assembly
- Mã cuối cùng dài khoảng 250 dòng theo chuẩn C; có cung cấp
lc3.ccho Unix vàlc3-win.ccho Windows - Kiến thức nền cần có là đọc C hoặc C++ cơ bản và số học nhị phân
- Toàn bộ mã nằm trong GitHub repo, còn bản hướng dẫn được viết theo dạng literate program, ghép các khối mã lại để tạo nguồn cuối cùng
Máy ảo làm gì
- VM là chương trình hoạt động giống CPU và một số thành phần phần cứng
- Thực hiện phép toán số học
- Đọc và ghi bộ nhớ
- Tương tác với thiết bị I/O
- Hiểu mã máy riêng của nó để chạy chương trình
- Tùy mục đích của VM, nó có thể tái hiện phần cứng thật một cách trung thực, hoặc cung cấp một kiến trúc ảo mới để tiện phát triển phần mềm
- JVM là ví dụ tiêu biểu về VM cung cấp nền tảng thực thi chuẩn; trên thiết bị có triển khai JVM, các chương trình Java, Kotlin, Clojure có thể chạy mà không cần chỉnh sửa
- Thực thi cô lập cũng là một công dụng quan trọng của VM
- Trong garbage collection, VM có thể quan sát stack và tham chiếu bộ nhớ từ bên ngoài chương trình đang chạy
- Ethereum smart contract chạy bên trong VM không được truy cập hệ thống tệp, mạng, ổ đĩa, v.v.
Cấu trúc kiến trúc LC-3
- Đối tượng triển khai là LC-3, được dùng trong giảng dạy kiến trúc máy tính và assembly ở đại học
- Bộ nhớ LC-3 có 65.536 vị trí, mỗi vị trí lưu một giá trị 16-bit
- Tổng dung lượng lưu trữ là 128KB
- Trong triển khai C, được biểu diễn bằng mảng
uint16_t memory[MEMORY_MAX]
- Có tổng cộng 10 thanh ghi
R0~R7: 8 thanh ghi đa dụngPC: địa chỉ bộ nhớ của lệnh sẽ thực thi tiếp theoCOND: cờ điều kiện của kết quả tính toán ngay trước đó
- Tất cả lệnh LC-3 đều là 16-bit, 4 bit bên trái là opcode
- Có 16 opcode được định nghĩa
- Bao gồm
OP_BR,OP_ADD,OP_LD,OP_ST,OP_JSR,OP_AND,OP_LDR,OP_STR,OP_RTI,OP_NOT,OP_LDI,OP_STI,OP_JMP,OP_RES,OP_LEA,OP_TRAP
- Cờ điều kiện biểu thị dấu của kết quả tính toán ngay trước đó
FL_POS: số dươngFL_ZRO: 0FL_NEG: số âm
Assembly và mã máy
- Thứ LC-3 VM thực sự chạy không phải assembly mà con người đọc được, mà là mảng lệnh mã máy 16-bit
- Assembler chuyển assembly LC-3 viết bằng văn bản thành các lệnh nhị phân 16-bit
- Ví dụ
Hello Worldcó luồng như sau.ORIG x3000: chỉ định địa chỉ bộ nhớ nơi chương trình sẽ được nạpLEA R0, HELLO_STR: nạp địa chỉ chuỗi vàoR0PUTS: in chuỗi màR0trỏ tớiHALT: dừng chương trình.STRINGZ "Hello World!": lưu dữ liệu chuỗi bên trong chương trình
.ORIG,.STRINGZkhông phải lệnh CPU mà là chỉ thị assembler- Điều kiện và vòng lặp được triển khai bằng lệnh rẽ nhánh gần giống
goto, chẳng hạnBRn LOOP
Quy trình cốt lõi của vòng lặp thực thi
- Thực thi VM lặp lại cùng một quy trình
- Đọc lệnh tại địa chỉ của thanh ghi
PC - Tăng
PC - Lấy opcode từ 4 bit cao của lệnh
- Chạy mã triển khai tương ứng với opcode
- Đọc lại lệnh tiếp theo
- Đọc lệnh tại địa chỉ của thanh ghi
- Địa chỉ bắt đầu mặc định là
0x3000 - Một số lệnh trực tiếp thay đổi
PCđể nhảy luồng thực thi- Nhờ các lệnh rẽ nhánh và nhảy, có thể có vòng lặp và thực thi có điều kiện ngay cả với cấu trúc chỉ đơn giản tăng
PC
- Nhờ các lệnh rẽ nhánh và nhảy, có thể có vòng lặp và thực thi có điều kiện ngay cả với cấu trúc chỉ đơn giản tăng
- Vòng lặp
maingọi mã xử lý theo từng opcode bằngswitch (op)- Xử lý
OP_ADD,OP_AND,OP_NOT,OP_BR,OP_JMP,OP_JSR,OP_LD,OP_LDI,OP_LDR,OP_LEA,OP_ST,OP_STI,OP_STR,OP_TRAP OP_RES,OP_RTIlà opcode không dùng đến, có thể xử lý bằngabort()
- Xử lý
Cách triển khai lệnh
ADDcộng hai giá trị, lưu vào thanh ghi đích và cập nhật cờ điều kiệnADDcó hai chế độ- Chế độ thanh ghi: đọc toán hạng thứ hai từ thanh ghi khác
- Chế độ giá trị tức thời: đọc toán hạng thứ hai từ 5 bit thấp
imm5của lệnh
- Các giá trị ngắn hơn 16-bit như
imm5phải được mở rộng thành giá trị 16-bit thông qua sign extension- Số dương được điền bằng 0
- Số âm được điền bằng 1 để bảo toàn giá trị ban đầu
- Lệnh ghi giá trị vào thanh ghi cập nhật
R_CONDbằngupdate_flags- Nếu giá trị là 0 thì
FL_ZRO - Nếu bit cao nhất là 1 thì
FL_NEG - Trường hợp còn lại là
FL_POS
- Nếu giá trị là 0 thì
LDIlà lệnh “load indirect”- Sign extension
PCoffset9của lệnh - Cộng vào
PChiện tại để lấy địa chỉ bộ nhớ - Dùng giá trị được lưu ở vị trí đó làm địa chỉ lần nữa để đọc dữ liệu cuối cùng
- Lưu giá trị đã đọc vào thanh ghi đích và cập nhật cờ điều kiện
- Sign extension
Tập lệnh chính
- Số học và thao tác bit
ADD: phép cộngAND: bit ANDNOT: bit NOT
- Luồng điều khiển
BR: so sánh cờ điều kiện với các bit điều kiện của lệnh để di chuyểnPCJMP: đặt giá trị thanh ghi được chỉ định vàoPCRET: theo đặc tả là một từ khóa riêng, nhưng là trường hợp đặc biệt củaJMPJSR,JSRR: lưuPChiện tại vàoR7rồi nhảy tới vị trí subroutine
- Đọc bộ nhớ
LD: đọc từ địa chỉ offset dựa trênPCLDI: đi theo địa chỉ gián tiếp thêm một lần để đọcLDR: đọc từ địa chỉ tính bằng base register và offsetLEA: lưu chính địa chỉ hiệu dụng vào thanh ghi
- Ghi bộ nhớ
ST: lưu vào địa chỉ offset dựa trênPCSTI: đi theo địa chỉ gián tiếp để lưuSTR: lưu vào địa chỉ tính bằng base register và offset
Trap routine và I/O
- LC-3 cung cấp trap routine cho các tác vụ chung và truy cập thiết bị I/O
- Có thể xem trap routine như hệ điều hành hoặc API của LC-3
- Trap code được định nghĩa như sau
TRAP_GETC = 0x20: nhập ký tự từ bàn phím, không echo ra terminalTRAP_OUT = 0x21: xuất ký tựTRAP_PUTS = 0x22: xuất word stringTRAP_IN = 0x23: nhập ký tự rồi echo ra terminalTRAP_PUTSP = 0x24: xuất byte stringTRAP_HALT = 0x25: dừng chương trình
- Trong trình mô phỏng LC-3 chính thức, trap routine được viết bằng assembly, nhưng trong VM này chúng được triển khai bằng hàm C
PUTSin ký tự từ địa chỉ lưu trongR0cho đến khi gặpx0000- Chuỗi LC-3 không lưu theo đơn vị 1 byte như chuỗi C, mà lưu mỗi ký tự trên một vị trí bộ nhớ
- Vì mỗi vị trí bộ nhớ là 16-bit, khi xuất bằng C sẽ chuyển thành
char
- Trap
HALTin"HALT", đổi cờ thực thi thành 0 và kết thúc vòng lặp VM
Nạp image chương trình
- Khi chuyển chương trình assembly LC-3 thành mã máy, sẽ tạo ra tệp chứa mảng lệnh và dữ liệu
- 16-bit đầu tiên của object file là origin, cho biết đặt chương trình ở đâu trong bộ nhớ
- Loader đọc origin trước, sau đó sao chép phần dữ liệu còn lại vào bộ nhớ bắt đầu từ địa chỉ origin
- Chương trình LC-3 có định dạng big-endian
- Vì hầu hết máy tính hiện đại là little-endian, áp dụng
swap16cho từnguint16_tđã nạp - Trên máy tính big-endian như PPC Mac cũ thì không nên swap
- Vì hầu hết máy tính hiện đại là little-endian, áp dụng
read_imagemở tệp ở chế độ nhị phân, gọiread_image_file, rồi đóng tệp
Thanh ghi ánh xạ bộ nhớ
- Các thanh ghi đặc biệt không được truy cập qua bảng thanh ghi thông thường mà được ánh xạ tới địa chỉ bộ nhớ cụ thể
- Trong LC-3, cần triển khai hai thanh ghi ánh xạ bộ nhớ
MR_KBSR = 0xFE00: keyboard status registerMR_KBDR = 0xFE02: keyboard data register
KBSRbiểu thị phím đã được nhấn hay chưa, cònKBDRlưu phím nào đã được nhấnGETCchặn thực thi cho đến khi có input, nhưngKBSRvàKBDRpolling trạng thái thiết bị để chương trình vẫn có thể tiếp tục phản hồi trong lúc chờ input- Đọc bộ nhớ không đọc trực tiếp mảng mà đi qua
mem_read- Nếu địa chỉ là
MR_KBSR, kiểm tra trạng thái bàn phím bằngcheck_key() - Nếu có phím, đặt bit cao nhất của
KBSRvà lưu giá trịgetchar()vàoKBDR - Nếu không có phím, đặt
KBSRthành 0
- Nếu địa chỉ là
Xử lý terminal theo từng nền tảng
- Để xử lý đúng nhập bàn phím và hoạt động của terminal, cần cấu hình input buffering theo từng nền tảng
- Triển khai Linux/macOS/UNIX dùng
termios,select, v.v.- Tắt canonical mode và echo
- Dùng
selectđể kiểm tra có thể nhập hay chưa
- Triển khai Windows dùng
GetStdHandle,GetConsoleMode,SetConsoleMode,_kbhit, v.v.- Điều chỉnh echo và line input
- Dùng
WaitForSingleObjectvà_kbhitđể kiểm tra nhập phím
- Khi chương trình bắt đầu, gọi
disable_input_buffering(); khi kết thúc, gọirestore_input_buffering() - Khi nhận
SIGINT, khôi phục cấu hình terminal, in dòng mới rồi thoát
Chạy và debug VM
- Ví dụ build VM như sau
gcc lc3.c -o lc3-vm
- Để chạy, truyền object file LC-3 đã được assemble làm đối số
lc3-vm path/to/2048.obj
- Các object file được cung cấp làm ví dụ là
2048.objvàrogue.obj - Ví dụ 2048 được điều khiển bằng phím WASD
- Nếu chương trình không hoạt động đúng, khả năng cao là do lỗi triển khai lệnh
- Nên đọc mã nguồn assembly LC-3 và dùng debugger để chạy từng bước các lệnh VM
- Nếu có điểm không nhảy tới lệnh mong đợi, hãy kiểm tra lại đặc tả và phần triển khai của lệnh đó
Tùy chọn: triển khai dựa trên generic C++
- Hướng dẫn cũng đề cập như một tùy chọn đến kỹ thuật triển khai C++ ngắn hơn
- Vì nhiều lệnh cùng chia sẻ các công việc lặp lại như sign extension, offset dựa trên
PC, tính địa chỉ gián tiếp, có thể xem thực thi lệnh như một pipeline gồm các bước xử lý nhỏ - Dùng template C++ và bit flag để chỉ đưa vào khi biên dịch những bước xử lý cần thiết cho từng opcode
- Cách này giảm trùng lặp mã và gần hơn với cách đi dây phần cứng thật, nơi mỗi bước xử lý chiếm không gian vật lý trên chip
- Bisqwit’s NES emulator được nhắc đến như nguồn ý tưởng
Tài liệu và đóng góp
- atul-g đã đóng góp reference card tóm tắt cách toàn bộ hệ thống hoạt động
- Các triển khai bằng nhiều ngôn ngữ được tập hợp dưới GitHub topic
lc3- Bao gồm C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript, Zig, v.v.
- Nếu muốn triển khai của mình xuất hiện trong danh sách, chỉ cần gắn GitHub topic
lc3 - Hỗ trợ nền tảng Windows do inkydragon đóng góp
- Dự án có good first issue liên quan đến integration test
1 bình luận
Ý kiến trên Hacker News
Khi còn là thiếu niên, trong lớp nhập môn khoa học máy tính ở community college, tôi đã thiết kế một tập lệnh CPU đơn giản, tự làm máy ảo và assembler để viết rồi chạy thử chương trình assembly
Nó dễ đến đáng ngạc nhiên, và máy tính trở nên bớt bí ẩn hơn rất nhiều
Tôi nghĩ có thể học mọi tầng của điện toán theo cách này, từ thiết kế CPU thật cho FPGA cho đến viết một hệ điều hành đơn giản và các chương trình chạy trên đó
Nếu bỏ qua hiệu năng và bảo mật mà điện toán hiện đại đòi hỏi, và chỉ đặt mục tiêu “chạy được là được”, thì lĩnh vực này đơn giản ngoài dự kiến
Nếu tôi nhớ đúng thì tối thiểu đã có phân đoạn bộ nhớ, chế độ bảo vệ và MMU
Đó là một máy tính/assembler đơn giản viết bằng BASIC trên PDP, và một trong các bài tập là triển khai phép nhân đơn giản bằng cách cộng trong vòng lặp
Thay vào đó bạn tôi sửa chương trình để tạo một lệnh MUL mới, và giáo viên thì hoàn toàn không thích chuyện đó
Người có tò mò và muốn học có thể dễ dàng nắm các tầng nền tảng này, nhưng với người muốn “kiếm tiền nhanh và có thể đi làm càng sớm càng tốt” thì không như vậy
Các sách được đề xuất:
Nếu ai đã đọc các cuốn trên bổ sung bình luận thì sẽ hữu ích cho mọi người
Trình giả lập Nintendo, hypervisor dùng VT-x, hệ điều hành đa nhiệm truyền thống, interpreter cho một ngôn ngữ scripting mới, bộ tối ưu truy vấn SQL, bộ khớp biểu thức chính quy, bộ giám sát bảo mật chạy mã người chơi không tin cậy trên server game — những thứ này dường như gần như không có các mối quan tâm chung, nhưng tất cả đều là máy ảo
Ngay cả trong định dạng terminfo dùng để mô tả chuỗi escape của terminal dạng ô ký tự cũng có một máy ảo dựa trên stack
Nhìn sâu hơn, thứ khiến máy tính trở thành máy tính theo nghĩa ngày nay chính là máy ảo, và bài báo năm 1936 của Turing về Entscheidungsproblem cũng xoay quanh việc các máy ảo có thể bắt chước lẫn nhau
Sau khi xem series CPU trên breadboard của Ben Eater, tôi chỉ muốn tự thiết kế và mô phỏng CPU
Ước gì tôi tìm được thời gian ngồi xuống để thiết kế nó
Tôi cho rằng các kiến trúc dùng cho giáo dục như Brookshear Machine hay Little Computer không hề giống kiến trúc thực tế, nên không chỉ vô dụng mà còn có hại
Tôi đã thấy những sinh viên học các lớp dùng những thứ đó hiểu về máy tính méo mó hơn cả những người chưa học lớp nào
Với hầu hết những người muốn học một chút về cách máy tính của mình hoạt động, lớp hệ điều hành sẽ tốt hơn; và nếu ở đây chỉ có thời gian cho một tutorial ngắn, tôi khuyên “Writing my own bootloader”
https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
Điều này không có nghĩa tutorial “Write your own VM” là tệ, mà theo kinh nghiệm của tôi, với phần lớn những người sẽ làm nó, một chủ đề khác sẽ hữu ích hơn
Bạn có thể giải thích thêm vì sao LC-3 không tốt để học kiến trúc máy tính không
Tôi hiểu là nó hoàn toàn khác phần cứng thực và quá đơn giản, nhưng tôi tò mò liệu từ góc nhìn viết CPU emulator thì nó cũng tệ không
Đó là một máy thập phân kiểu có thể đã được chế tạo vào thập niên 1960, nhưng sau thập niên 1970 thì không ai còn làm dạng đó nữa
Những hệ thống như vậy có thể dạy nhiều kiến thức nền tảng, nhưng các kỹ thuật trong https://en.wikipedia.org/wiki/Hacker%27s_Delight chủ yếu dựa vào các cách biểu diễn số thông dụng, nên khó học được
Vì không biết rõ nên tôi xem lướt Wikipedia; sau khi nhìn truyện tranh tôi đã đoán là sẽ có gì đó kỳ quặc, nhưng thoạt nhìn thì không đến mức gây sốc
Nó có cảm giác pha trộn giữa s/360, một chút x86, một chút rất nhỏ ARM hoặc một họ kiến trúc RISC khác; có nhiều phần bị lược bỏ và kỳ lạ, nhưng mục tiêu dường như là nhanh chóng đi đến một bản triển khai chạy được
Tôi muốn biết điều gì khiến bạn xem nó là “không chỉ vô dụng mà còn có hại” cho giáo dục
Có vẻ nhiều lớp khoa học máy tính ở Ấn Độ vẫn dùng 8086/8088
Đặc biệt là có thể làm load gián tiếp kép thông qua một word tương đối PC nằm ở giữa
Vậy mà phép trừ lại phải tạo từ phép phủ định, còn phủ định thì phải tạo từ NOT và ADD ,,#-1
Nếu xét không gian mã hóa lệnh hạn chế, có lẽ NOT d,s = XOR d,s,#-1 sẽ là cách dùng tốt hơn
Nếu phải phân định cho thật chặt thì đây không phải là máy ảo mà là trình giả lập
Theo nghĩa mô tả thì thuật ngữ đó có thể áp dụng được, và trước thời kỳ ảo hóa phần cứng thì cũng có phần mơ hồ nhất định, nhưng trong hiện đại, cách dùng áp đảo phổ biến của “Virtual Machine” là chỉ môi trường sử dụng các tính năng ảo hóa phần cứng như VT-x
JVM được triển khai rộng rãi, Ethereum VM được gọi là EVM, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... cũng liên tục mô tả BPF và eBPF là “virtual machines”, còn https://webassembly.org/ mở đầu rằng “WebAssembly (viết tắt là Wasm) là một định dạng lệnh nhị phân cho một máy ảo dựa trên ngăn xếp”
“Máy ảo” vẫn là cách gọi phổ biến nhất cho một cỗ máy mang tính ảo
Cá nhân tôi thích những cách diễn đạt như “fictive machine”, “fictious machine”, “imaginary computer”, “fantastic automaton” hơn, nhưng có lẽ chúng sẽ không được chấp nhận
Không phải lúc nào cũng có thể dùng “trình giả lập” thay cho “máy ảo”
Có thể gọi wasmtime là trình giả lập, nhưng gọi bản thân WebAssembly là trình giả lập thì không chính xác; WebAssembly là máy ảo mà wasmtime giả lập
Gọi trình giả lập là máy ảo cũng là chuyện phổ biến, và một phiên bản trình giả lập đang chạy cũng là máy ảo theo một nghĩa khác
Gọi môi trường ảo hóa phần cứng là “máy ảo” cũng hợp lý, và phần nào chồng lấn với nghĩa sau cùng này
Trong môi trường hiện tại, cách dùng đó có thể áp đảo phổ biến, nhưng ở những nơi khác thì không nhất thiết như vậy
Theo nghĩa thuần túy nhất, máy ảo chỉ là một chiếc máy tính được tạo ra, và không hàm ý nó sẽ được dùng vào việc gì hay hoạt động ra sao
Bài viết cũng lấy giả lập console cổ điển làm ví dụ, nhưng rõ ràng theo định nghĩa được đưa ra thì còn có nhiều loại máy ảo khả dĩ hơn rất nhiều
Điểm cốt lõi là máy ảo là một khái niệm trừu tượng và có rất nhiều loại
Simulator, emulator, hypervisor đều là máy ảo, và còn có cả những dạng máy ảo kỳ lạ chưa được đặt tên
Tôi không có ý nói bất lịch sự, trái lại là muốn tôn trọng, và muốn làm rõ thuật ngữ này cho những người đang học
“Máy ảo” thường được dùng cho mọi phần mềm thực thi mã máy hoặc bytecode, bất kể lý do là gì
Nó có thể bao gồm ảo hóa, nhưng cũng thường được dùng cho runtime ngôn ngữ như JVM của Java hay YARV (Yet Another Ruby VM) của Ruby
Ngược lại, lĩnh vực mà người ta không nghe thuật ngữ này thường xuyên lắm lại là giả lập; một phần cũng vì phần lớn trình giả lập hiện đại đã nghiêng về kỹ thuật biên dịch lại động phần mềm mục tiêu thay vì giả lập toàn bộ hệ thống
Java hẳn có thể được xem là thuộc “cách dùng áp đảo phổ biến”