Cara Membuat Mesin Virtual (2022)

 (jmeiners.com)
3 poin oleh GN⁺ 2024-12-28 | 1 komentar | Bagikan ke WhatsApp
  • Untuk memahami cara kerja internal komputer dan bagaimana bahasa pemrograman dijalankan, dibuat sendiri VM berbasis C sekitar 250 baris yang menjalankan program assembly di atas arsitektur edukasi LC-3
  • Target implementasinya adalah model komputer kecil dengan 65.536 lokasi memori 16-bit, 10 register, 16 opcode, flag kondisi, trap routine, dan register memory-mapped
  • Loop eksekusi bekerja dengan struktur fetch-decode-execute: membaca instruksi yang ditunjuk PC, menaikkan nilainya, lalu menafsirkan opcode untuk menjalankan instruksi seperti ADD, LDI, BR, JMP, dan TRAP
  • Pemuatan program membaca origin 16-bit pertama dari file objek lalu menaruhnya ke memori, serta melakukan byte swap agar format big-endian LC-3 cocok dengan format little-endian yang dipakai kebanyakan komputer modern
  • Input keyboard dan output konsol ditangani lewat trap routine dan register memory-mapped KBSR/KBDR, dan membutuhkan kode buffering input terminal yang berbeda untuk Unix/macOS dan Windows

Tujuan dan prasyarat tutorial

  • Mengikuti proses menjalankan program bahasa assembly dengan mengimplementasikan sendiri mesin virtual LC-3
  • Kode akhirnya sekitar 250 baris dalam C, dan tersedia lc3.c untuk Unix serta lc3-win.c untuk Windows
  • Pengetahuan prasyarat yang dibutuhkan adalah kemampuan dasar membaca C atau C++ serta aritmetika biner
  • Seluruh kode ada di repo GitHub, dan tutorialnya sendiri berbentuk literate program yang merangkai blok-blok kode menjadi source akhir

Apa yang dilakukan mesin virtual

  • VM adalah program yang bertindak seperti CPU dan sebagian komponen hardware
    • Melakukan operasi aritmetika
    • Membaca dan menulis memori
    • Berinteraksi dengan perangkat I/O
    • Memahami bahasa mesin-nya sendiri untuk menjalankan program
  • Bergantung pada tujuannya, VM bisa mereproduksi hardware nyata dengan setia atau menyediakan arsitektur virtual baru demi kemudahan pengembangan software
  • JVM adalah contoh representatif VM yang menyediakan platform eksekusi standar; pada perangkat yang mengimplementasikan JVM, program Java, Kotlin, dan Clojure dapat dijalankan tanpa modifikasi
  • Eksekusi terisolasi juga merupakan kegunaan penting VM
    • Dalam garbage collection, VM dapat mengamati stack dan referensi memori dari luar program yang sedang berjalan
    • Ethereum smart contract berjalan di dalam VM yang tidak dapat mengakses file system, jaringan, disk, dan sebagainya

Struktur arsitektur LC-3

  • Target implementasi adalah LC-3, yang digunakan untuk pendidikan arsitektur komputer dan assembly di universitas
  • Memori LC-3 memiliki 65.536 lokasi, dan setiap lokasi menyimpan nilai 16-bit
    • Total kapasitas penyimpanannya adalah 128KB
    • Dalam implementasi C, ini direpresentasikan sebagai array uint16_t memory[MEMORY_MAX]
  • Total register ada 10 buah
    • R0~R7: 8 register serbaguna
    • PC: alamat memori instruksi berikutnya yang akan dieksekusi
    • COND: flag kondisi dari hasil komputasi terakhir
  • Semua instruksi LC-3 berukuran 16-bit, dan 4 bit paling kiri adalah opcode
    • Ada 16 opcode yang didefinisikan
    • Termasuk 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
  • Flag kondisi menunjukkan tanda dari hasil komputasi terakhir
    • FL_POS: positif
    • FL_ZRO: nol
    • FL_NEG: negatif

Assembly dan bahasa mesin

  • Yang benar-benar dijalankan VM LC-3 bukan assembly yang bisa dibaca manusia, melainkan array instruksi bahasa mesin 16-bit
  • Assembler mengubah assembly LC-3 yang ditulis sebagai teks menjadi instruksi biner 16-bit
  • Contoh Hello World memiliki alur berikut
    • .ORIG x3000: menentukan alamat memori tempat program dimuat
    • LEA R0, HELLO_STR: memuat alamat string ke R0
    • PUTS: mencetak string yang ditunjuk R0
    • HALT: menghentikan program
    • .STRINGZ "Hello World!": menyimpan data string di dalam program
  • .ORIG, .STRINGZ bukan instruksi CPU, melainkan directive assembler
  • Kondisi dan perulangan diimplementasikan dengan instruksi branch yang lebih mirip goto, seperti BRn LOOP

Prosedur inti loop eksekusi

  • Eksekusi VM mengulangi prosedur yang sama
    • Membaca instruksi dari alamat register PC
    • Menaikkan PC
    • Mengambil opcode dari 4 bit teratas instruksi
    • Menjalankan kode implementasi yang sesuai dengan opcode
    • Kembali membaca instruksi berikutnya
  • Alamat awal default adalah 0x3000
  • Sebagian instruksi mengubah PC secara langsung untuk melompat dalam alur eksekusi
    • Berkat instruksi branch dan jump, struktur yang sekadar menaikkan PC tetap dapat menjalankan loop dan eksekusi kondisional
  • Loop main memanggil kode penanganan per opcode lewat switch (op)
    • Menangani 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_RTI adalah opcode yang tidak digunakan dan bisa ditangani dengan abort()

Cara implementasi instruksi

  • ADD menjumlahkan dua nilai, menyimpan hasilnya ke register tujuan, lalu memperbarui flag kondisi
  • ADD memiliki dua mode
    • Mode register: operand kedua dibaca dari register lain
    • Mode immediate: operand kedua dibaca dari imm5, yaitu 5 bit terbawah instruksi
  • Nilai yang lebih pendek dari 16-bit seperti imm5 harus diperluas menjadi nilai 16-bit lewat sign extension
    • Nilai positif diisi dengan 0
    • Nilai negatif diisi dengan 1 agar nilainya tetap terjaga
  • Instruksi yang menulis nilai ke register memperbarui R_COND lewat update_flags
    • Jika nilainya 0 maka FL_ZRO
    • Jika bit paling atas bernilai 1 maka FL_NEG
    • Selain itu maka FL_POS
  • LDI adalah instruksi “load indirect”
    • PCoffset9 pada instruksi di-sign-extend
    • Ditambahkan ke PC saat ini untuk mendapatkan alamat memori
    • Nilai yang tersimpan di lokasi itu dipakai lagi sebagai alamat untuk membaca data akhir
    • Nilai yang dibaca disimpan ke register tujuan dan flag kondisi diperbarui

Set instruksi utama

  • Operasi aritmetika dan bit
    • ADD: penjumlahan
    • AND: bit AND
    • NOT: bit NOT
  • Alur kontrol
    • BR: memindahkan PC dengan membandingkan flag kondisi dan bit kondisi pada instruksi
    • JMP: menetapkan nilai register tertentu ke PC
    • RET: secara spesifikasi adalah keyword terpisah, tetapi merupakan kasus khusus dari JMP
    • JSR, JSRR: menyimpan PC saat ini ke R7 lalu melompat ke lokasi subrutin
  • Membaca memori
    • LD: membaca dari alamat offset berbasis PC
    • LDI: membaca dengan mengikuti alamat tidak langsung sekali lagi
    • LDR: membaca dari alamat hasil perhitungan base register dan offset
    • LEA: menyimpan alamat efektif itu sendiri ke register
  • Menulis memori
    • ST: menyimpan ke alamat offset berbasis PC
    • STI: menyimpan dengan mengikuti alamat tidak langsung
    • STR: menyimpan ke alamat hasil perhitungan base register dan offset

Trap routine dan I/O

  • LC-3 menyediakan trap routine untuk pekerjaan umum dan akses perangkat I/O
  • Trap routine dapat dipandang sebagai sistem operasi atau API untuk LC-3
  • Trap code didefinisikan sebagai berikut
    • TRAP_GETC = 0x20: input satu karakter dari keyboard, tanpa echo ke terminal
    • TRAP_OUT = 0x21: output satu karakter
    • TRAP_PUTS = 0x22: output word string
    • TRAP_IN = 0x23: input satu karakter lalu echo ke terminal
    • TRAP_PUTSP = 0x24: output byte string
    • TRAP_HALT = 0x25: menghentikan program
  • Pada simulator resmi LC-3, trap routine ditulis dalam assembly, tetapi pada VM ini diimplementasikan sebagai fungsi C
  • PUTS mencetak karakter mulai dari alamat yang tersimpan di R0 sampai menemukan x0000
    • String LC-3 tidak menyimpan satu karakter per 1 byte seperti string C, melainkan satu karakter per lokasi memori
    • Karena setiap lokasi memori berukuran 16-bit, saat mencetak di C nilainya dikonversi ke char
  • Trap HALT mencetak "HALT", lalu mengubah flag eksekusi menjadi 0 untuk menghentikan loop VM

Memuat image program

  • Saat program assembly LC-3 diubah menjadi bahasa mesin, akan dihasilkan file berisi array instruksi dan data
  • 16-bit pertama pada file objek adalah origin yang menunjukkan di mana program harus diletakkan di memori
  • Loader membaca origin terlebih dahulu, lalu menyalin sisa data ke memori mulai dari alamat origin
  • Program LC-3 menggunakan format big-endian
    • Karena kebanyakan komputer modern menggunakan little-endian, setiap uint16_t yang dimuat perlu diterapkan swap16
    • Pada komputer big-endian seperti PPC Mac lama, swap tidak boleh dilakukan
  • read_image membuka file dalam mode biner, memanggil read_image_file, lalu menutup file

Register memory-mapped

  • Register khusus yang tidak diakses lewat tabel register biasa dipetakan ke alamat memori tertentu
  • Dalam LC-3, ada dua register memory-mapped yang perlu diimplementasikan
    • MR_KBSR = 0xFE00: keyboard status register
    • MR_KBDR = 0xFE02: keyboard data register
  • KBSR menunjukkan apakah ada tombol yang ditekan, dan KBDR menyimpan tombol apa yang ditekan
  • GETC menghentikan eksekusi sampai ada input, tetapi KBSR dan KBDR memungkinkan program terus responsif saat menunggu input dengan melakukan polling status perangkat
  • Pembacaan memori tidak dilakukan dengan membaca array secara langsung, melainkan melalui mem_read
    • Jika alamatnya MR_KBSR, status keyboard diperiksa dengan check_key()
    • Jika ada tombol, bit paling atas KBSR diaktifkan dan nilai getchar() disimpan ke KBDR
    • Jika tidak ada tombol, KBSR diatur menjadi 0

Penanganan terminal per platform

  • Untuk menangani input keyboard dan perilaku terminal dengan benar, diperlukan pengaturan buffering input yang berbeda per platform
  • Implementasi Linux/macOS/UNIX menggunakan termios, select, dan sebagainya
    • Menonaktifkan canonical mode dan echo
    • Memeriksa ketersediaan input dengan select
  • Implementasi Windows menggunakan GetStdHandle, GetConsoleMode, SetConsoleMode, _kbhit, dan sebagainya
    • Mengatur echo dan line input
    • Memeriksa input keyboard dengan WaitForSingleObject dan _kbhit
  • Saat program dimulai, disable_input_buffering() dipanggil, dan saat selesai restore_input_buffering() dipanggil
  • Saat menerima SIGINT, pengaturan terminal dipulihkan, karakter baris baru dicetak, lalu program keluar

Menjalankan dan men-debug VM

  • Contoh build VM adalah sebagai berikut
gcc lc3.c -o lc3-vm
  • Untuk menjalankannya, berikan file objek LC-3 yang sudah dirakit sebagai argumen
lc3-vm path/to/2048.obj
  • File objek contoh yang disediakan adalah 2048.obj dan rogue.obj
  • Contoh 2048 dikendalikan dengan tombol WASD
  • Jika program tidak berjalan dengan benar, kemungkinan besar ada kesalahan pada implementasi instruksi
    • Disarankan membaca source assembly LC-3 sambil menjalankan instruksi VM satu per satu dengan debugger
    • Jika ada titik yang tidak berpindah ke instruksi yang diharapkan, periksa kembali spesifikasi dan implementasi instruksi tersebut

Opsi: implementasi berbasis generik C++

  • Teknik implementasi C++ yang lebih ringkas juga dibahas sebagai opsi
  • Karena banyak instruksi berbagi pekerjaan berulang seperti sign extension, offset berbasis PC, dan perhitungan alamat tidak langsung, eksekusi instruksi dapat dipandang sebagai pipeline dari langkah-langkah pemrosesan kecil
  • Dengan template C++ dan bit flag, hanya langkah pemrosesan yang dibutuhkan untuk tiap opcode yang disertakan saat kompilasi
  • Pendekatan ini mengurangi duplikasi kode dan lebih mirip dengan cara wiring hardware nyata yang menempati ruang fisik pada chip
  • Sebagai sumber ide disebutkan Bisqwit’s NES emulator

Materi dan kontribusi

  • atul-g menyumbangkan reference card yang merangkum cara kerja seluruh sistem
  • Implementasi dalam berbagai bahasa dirangkum lewat topik GitHub lc3
    • Termasuk C, C++, Go, Haskell, Java, JavaScript, Kotlin, Lua, OCaml, Python, Ruby, Rust, Swift, TypeScript, Zig, dan lainnya
  • Agar implementasi Anda muncul dalam daftar, cukup tambahkan topik GitHub lc3
  • Dukungan platform Windows dikontribusikan oleh inkydragon
  • Proyek ini memiliki good first issue terkait pengujian terintegrasi

Bacaan terkait

1 komentar

 
GN⁺ 2024-12-28
Pendapat di Hacker News

  • Saat remaja, di kelas pengantar ilmu komputer di community college, saya merancang set instruksi CPU sederhana, lalu membuat sendiri virtual machine dan assembler untuk menulis serta menjalankan program assembly
    Ternyata sangat mudah, dan komputer terasa jauh tidak terlalu misterius
    Rasanya semua lapisan komputasi bisa dipelajari dengan cara seperti ini, mulai dari merancang CPU sungguhan untuk FPGA hingga menulis sistem operasi sederhana dan program yang berjalan di atasnya
    Kalau mengesampingkan performa dan keamanan yang dituntut komputasi modern, dan targetnya hanya “asal jalan”, bidang ini ternyata sederhana di luar dugaan

    • Sepertinya kelas yang menarik, dan terlihat sangat mirip dengan https://www.nand2tetris.org/ atau buku Code karya Charles Petzold
    • Begitu beralih dari CPU imajiner awal ke CPU produksi nyata generasi awal seperti 80286, kompleksitasnya melonjak tajam
      Kalau ingatan saya benar, setidaknya ada segmentasi memori, protected mode, dan MMU
    • Di kelas CS 101 juga ada sistem seperti itu
      Itu komputer/assembler sederhana yang ditulis dengan BASIC di PDP, dan salah satu tugasnya adalah mengimplementasikan perkalian sederhana dengan melakukan penjumlahan berulang dalam loop
      Teman saya malah memodifikasi programnya untuk membuat instruksi MUL baru, dan gurunya sama sekali tidak senang
    • Komponen-komponen sederhana itu sendiri memang sangat mudah, tetapi masih berjarak ratusan lapisan dari hasil tingkat komersial yang benar-benar dilihat dan disentuh pengguna nyata di komputer
      Orang yang punya rasa ingin tahu dan ingin belajar bisa dengan mudah memahami lapisan-lapisan dasar seperti ini, tetapi tidak demikian bagi orang yang ingin “cepat menghasilkan uang dan secepat mungkin siap kerja”
    • Sepertinya kursus nand2tetris memang melakukan hal seperti itu

  • Buku-buku yang direkomendasikan:

    1. Virtual Machines: Versatile Platforms for Systems and Processes karya Smith dan Nair — tampaknya buku yang mengulas topik ini secara menyeluruh
    2. Virtual Machines karya Iain Craig — tampaknya buku yang lebih praktis tentang bahasa dan virtual machine
    3. Virtual Machine Design and Implementation in C/C++ karya Bill Blunden — tampaknya buku praktik yang berfokus pada implementasi
      Kalau ada yang sudah membaca buku-buku di atas dan bisa menambahkan komentar, itu akan bermanfaat bagi semua orang
    • Saya tidak yakin topik ini cukup sempit untuk bisa diulas dalam satu buku
      Emulator Nintendo, hypervisor yang memakai VT-x, sistem operasi multitasking tradisional, interpreter untuk bahasa scripting baru, pengoptimal kueri SQL, regex matcher, sandbox keamanan yang menjalankan kode pemain tak tepercaya di server game, dan sebagainya tampaknya hampir tidak punya pertimbangan yang sama, tetapi semuanya adalah virtual machine
      Bahkan di dalam format terminfo yang menentukan escape sequence terminal sel karakter, ada virtual machine berbasis stack
      Kalau dilihat lebih dalam, virtual machine-lah yang membuat komputer menjadi “komputer” dalam pengertian masa kini, dan makalah Entscheidungsproblem Turing tahun 1936 pun bergantung pada fakta bahwa virtual machine dapat meniru satu sama lain

  • Setelah menonton seri CPU breadboard Ben Eater, saya hanya jadi ingin merancang dan mengemulasikan CPU sendiri
    Semoga saya bisa menemukan waktu untuk duduk dan merancangnya

  • Menurut saya arsitektur edukasional seperti Brookshear Machine atau Little Computer sama sekali tidak mirip arsitektur nyata, sehingga bukan hanya tidak berguna tetapi bahkan berbahaya
    Saya pernah melihat mahasiswa yang mengikuti kelas memakai hal semacam itu justru memahami komputer dengan lebih keliru daripada orang yang tidak pernah mengikuti kelas apa pun
    Bagi kebanyakan orang yang ingin sedikit belajar tentang cara kerja komputer mereka, kelas sistem operasi lebih baik, dan kalau di sana pun hanya ada waktu untuk satu tutorial singkat, saya merekomendasikan “Writing my own bootloader”
    https://dev.to/frosnerd/writing-my-own-boot-loader-3mld
    Ini bukan berarti tutorial “Write your own VM” itu buruk, melainkan menurut pengalaman saya, bagi sebagian besar orang yang akan mengikutinya, topik lain akan lebih membantu

    • Saya baru saja mencoba LC-3, dan dalam proyek saat ini saya ingin sedikit belajar dynamic recompilation dengan menjadikan LC-3 sebagai target machine yang tidak cocok
      Bisa jelaskan lebih lanjut mengapa LC-3 buruk untuk mempelajari arsitektur komputer?
      Saya paham bahwa itu sangat berbeda dari hardware nyata dan terlalu sederhana, tetapi saya penasaran apakah itu juga buruk dari sudut pandang menulis emulator CPU
    • Saya teringat MIX lama dari Knuth
      Itu mesin desimal yang mungkin saja dibuat pada 1960-an, tetapi setelah 1970-an tidak ada lagi yang membuat bentuk seperti itu
      Sistem seperti itu bisa mengajarkan banyak dasar, tetapi teknik-teknik di https://en.wikipedia.org/wiki/Hacker%27s_Delight sebagian besar bergantung pada cara representasi angka yang umum, sehingga sulit dipelajari dengannya
    • Saya penasaran apa yang khususnya tidak Anda sukai dari LC-3
      Karena tidak terlalu tahu, saya sempat melihat Wikipedia, dan setelah melihat kartunnya saya mengira akan menemukan sesuatu yang aneh, tetapi sekilas tidak terlihat terlalu mengejutkan
      Terasa seperti campuran s/360, sedikit x86, dan sedikit sekali ARM atau arsitektur RISC lain; memang banyak bagian yang dihilangkan dan ada bagian yang aneh, tetapi tujuannya tampaknya agar cepat sampai pada implementasi yang berjalan
      Saya ingin tahu apa yang membuat Anda menganggapnya “bukan hanya tidak berguna tetapi berbahaya” untuk pendidikan
    • Saya merekomendasikan memakai arsitektur 8-bit lama seperti 6502 atau Z80
      Di banyak kelas ilmu komputer di India, tampaknya mereka masih memakai 8086/8088
    • Mode pengalamatan LC-3 cukup aneh
      Khususnya, ia bisa melakukan load indirect ganda melalui word relatif PC yang berada di tengah
      Namun demikian, pengurangan harus dibangun dari negasi, dan negasi harus dibuat dari NOT dan ADD ,,#-1
      Mengingat ruang encoding instruksi yang terbatas, rasanya NOT d,s = XOR d,s,#-1 akan menjadi pemanfaatan yang lebih baik

  • Kalau mau benar-benar dibedakan, ini bukan virtual machine, melainkan emulator
    Dalam arti deskriptif, istilah itu bisa saja diterapkan, dan pada era sebelum virtualisasi perangkat keras memang ada sedikit ambiguitas, tetapi dalam penggunaan modern, makna “Virtual Machine” yang sangat dominan merujuk pada lingkungan yang memakai fitur virtualisasi perangkat keras seperti VT-x

    • Saya tidak setuju bahwa istilah itu “sangat dominan”, dan sulit juga menganggap pembedaan itu sepenuhnya tepat
      JVM tersebar luas, Ethereum VM disebut EVM, https://www.linuxfoundation.org/hubfs/LF%20Research/The_Stat... juga berulang kali menjelaskan BPF dan eBPF sebagai “virtual machines”, dan https://webassembly.org/ dibuka dengan kalimat “WebAssembly (disingkat Wasm) adalah format instruksi biner untuk virtual machine berbasis stack”
      “Virtual machine” masih merupakan istilah paling umum untuk menyebut mesin virtual
      Secara pribadi saya lebih menyukai ungkapan seperti “fictive machine”, “fictious machine”, “imaginary computer”, atau “fantastic automaton”, tetapi sepertinya tidak akan diadopsi
      Kita tidak bisa selalu memakai “emulator” sebagai pengganti “virtual machine”
      wasmtime mungkin bisa disebut emulator, tetapi menyebut WebAssembly itu sendiri sebagai emulator tidaklah akurat; WebAssembly adalah virtual machine yang diemulasi oleh wasmtime
      Menyebut emulator sebagai virtual machine juga umum, dan instance emulator yang sedang berjalan juga merupakan virtual machine dalam arti lain
      Menyebut lingkungan virtualisasi perangkat keras sebagai “virtual machine” juga valid, dan sampai batas tertentu tumpang tindih dengan makna terakhir ini
      Dalam lingkungan saat ini, penggunaan itu mungkin sangat dominan, tetapi belum tentu demikian di tempat lain
    • Dengan hormat, saya sulit setuju
      Dalam makna yang paling murni, virtual machine hanyalah komputer yang dibuat-buat, dan tidak mengimplikasikan untuk apa ia digunakan atau bagaimana cara kerjanya
      Artikel ini juga memakai emulasi konsol klasik sebagai contoh, tetapi jelas bahwa menurut definisi yang diberikan, ada jauh lebih banyak virtual machine yang mungkin
      Intinya, virtual machine adalah konsep abstrak dan jenisnya sangat banyak
      Simulator, emulator, hypervisor, dan sebagainya semuanya adalah virtual machine, dan ada juga bentuk-bentuk virtual machine aneh yang belum diberi nama
      Saya tidak bermaksud bersikap kasar, justru ingin menghormati, dan ingin memperjelas istilah ini bagi orang-orang yang sedang belajar
    • Menurut saya pembedaan yang Anda bela sebenarnya tidak ada
      “Virtual machine” lazim dipakai untuk perangkat lunak apa pun yang menjalankan kode mesin atau bytecode, terlepas dari alasannya
      Itu bisa mencakup virtualisasi, tetapi juga sering dipakai untuk runtime bahasa, seperti JVM milik Java atau YARV (Yet Another Ruby VM) milik Ruby
      Justru bidang tempat istilah ini tidak terlalu sering terdengar adalah emulasi, sebagian juga karena kebanyakan emulator modern cenderung memakai teknik recompilation dinamis terhadap perangkat lunak target yang diemulasi, alih-alih mengemulasi seluruh sistem
    • Ini adalah VM dalam arti JVM, yaitu Java Virtual Machine
      Java sendiri rasanya bisa dianggap termasuk “penggunaan yang sangat dominan”