JVM yang Ditulis dengan Rust

 (andreabergia.com)
3 poin oleh GN⁺ 2023-07-22 | 1 komentar | Bagikan ke WhatsApp
  • rjvm, proyek sampingan untuk belajar Rust, adalah JVM mainan untuk pembelajaran, tetapi sudah diimplementasikan sampai tingkat bisa membaca .class dan jar sungguhan serta menjalankan bytecode Java
  • Fitur yang tidak didukung adalah thread, reflection, annotation, I/O, kompiler JIT, dan string interning, tetapi mencakup alur kontrol, pembuatan objek, pemanggilan metode, exception, dan garbage collection
  • Contohnya menggunakan rt.jar asli dari OpenJDK 7, sehingga kelas seperti java.lang.StackTraceElement dimuat dari JDK sungguhan
  • Kodenya dibagi menjadi tiga crate Rust: reader, vm, dan vm_cli, yang mencakup mulai dari parsing .class hingga call stack, native method, serta pemodelan nilai dan objek
  • Tonggak terakhirnya adalah stop-the-world semispace copying collector, dan setelah target tercapai proyek dihentikan tanpa rencana memperbaiki bug yang sudah diketahui

rjvm, Rust JVM untuk pembelajaran

  • rjvm adalah Java Virtual Machine mainan yang dibuat untuk belajar Rust
  • Kodenya dipublikasikan di GitHub
  • Karena ini lebih merupakan implementasi untuk tujuan belajar daripada implementasi JVM yang serius, fitur berikut tidak didukung
    • thread
    • reflection
    • annotation
    • I/O
    • kompiler JIT
    • string interning
  • Generic awalnya masuk daftar yang tidak didukung, tetapi ternyata sebenarnya berfungsi

Sejauh mana implementasinya

  • rjvm bukan sekadar parser sederhana, tetapi juga mengimplementasikan langsung berbagai perilaku JVM
    • alur kontrol seperti if dan for
    • tipe primitif dan pembuatan objek
    • pemanggilan metode virtual dan metode statis
    • penanganan exception
    • garbage collection
    • resolusi kelas dari file jar
  • Kode pengujian mencakup contoh yang menggunakan Throwable, Exception, dan StackTraceElement
  • Karena tidak ada I/O sungguhan, tempPrint digunakan sebagai native method sebagai pengganti System.out.println
  • Contohnya memakai rt.jar asli dari OpenJDK 7, dan java.lang.StackTraceElement juga diambil dari JDK sungguhan

Tiga crate Rust

  • Proyek ini adalah proyek Rust standar dan terdiri dari tiga crate
    • reader: membaca file .class dan berisi tipe untuk memodelkan isinya
    • vm: menyediakan mesin virtual dalam bentuk library yang dapat menjalankan kode
    • vm_cli: berisi launcher command line sederhana yang mirip executable java
  • Ada pertimbangan untuk memisahkan crate reader ke repositori terpisah dan menerbitkannya ke crates.io

Parsing file .class

  • Kode Java dikompilasi dengan javac menjadi file .class, dan biasanya didistribusikan dalam file .jar yang berformat zip
  • Untuk menjalankan kode Java, pertama-tama perlu memuat file .class yang berisi bytecode hasil keluaran kompiler
  • File kelas juga memuat informasi yang diperlukan untuk eksekusi dan resolusi tipe
    • metadata seperti nama kelas dan nama file sumber
    • nama superclass
    • interface yang diimplementasikan
    • field, tipe field, dan annotation
    • descriptor metode, klausa throws, annotation, dan informasi generic
    • bytecode, tabel exception handler, dan tabel nomor baris
  • Crate reader mem-parsing file kelas dan mengembalikan Rust struct yang memodelkan kelas dan isinya

Eksekusi metode dan call stack

  • API utama dari crate vm adalah Vm::invoke, yang digunakan untuk menjalankan metode
  • Setiap metode yang sedang berjalan memiliki satu CallFrame di dalam CallStack
  • Saat main dijalankan, call stack awalnya kosong, lalu frame baru dibuat untuk eksekusi
  • Setiap pemanggilan fungsi menambahkan frame baru ke call stack, dan ketika eksekusi metode selesai frame tersebut dihapus
  • Sebagian besar metode diimplementasikan dengan bytecode Java, tetapi rjvm juga mendukung native method
    • Native method adalah metode yang tidak diimplementasikan dengan bytecode Java, melainkan langsung oleh JVM itu sendiri
    • Contohnya System::currentTimeMillis, System::arraycopy, dan Throwable::fillInStackTrace
    • Di rjvm, ini diimplementasikan sebagai fungsi Rust
  • JVM adalah mesin virtual berbasis stack, sehingga instruksi bytecode terutama bekerja di atas value stack
  • Setiap call frame terhubung ke value stack dan sekumpulan variabel lokal yang diidentifikasi lewat indeks

Pemodelan nilai dan objek

  • Value memodelkan nilai yang dapat disimpan dalam variabel lokal, elemen stack, atau field objek
  • Value diimplementasikan sebagai Rust enum dan mencakup status berikut
    • Uninitialized
    • Int(i32)
    • Long(i64)
    • Float(f32)
    • Double(f64)
    • Object(AbstractObject<'a>)
    • Null
  • Sum type seperti Rust enum sangat cocok untuk menyatakan bahwa satu nilai bisa menjadi salah satu dari beberapa tipe
  • Penyimpanan objek awalnya dimulai dari struct Object sederhana berbasis Vec<Value> yang memuat referensi kelas dan nilai field
  • Setelah implementasi garbage collector, itu berubah menjadi implementasi tingkat lebih rendah yang banyak memakai pointer dan cast
  • Saat ini AbstractObject memodelkan objek nyata atau array, berupa pointer ke array byte yang berisi beberapa header word dan nilai field

Eksekusi instruksi bytecode

  • Eksekusi metode adalah proses menangani instruksi bytecode satu per satu
  • Instruksi JVM berjumlah lebih dari 200 dan dikodekan sebagai 1 byte dalam bytecode
  • Banyak instruksi diikuti argumen, dan sebagian instruksi memiliki panjang variabel
  • rjvm memodelkan instruksi bytecode Java dengan tipe Instruction
  • Saat metode dijalankan, value stack dan array variabel lokal dipertahankan, lalu program counter yang menunjukkan alamat instruksi berikutnya diinisialisasi ke 0
  • Biasanya setelah sebuah instruksi dieksekusi, program counter berpindah ke instruksi berikutnya, tetapi instruksi lompat dapat memindahkannya ke posisi lain
  • Instruksi lompat digunakan untuk mengimplementasikan pernyataan kontrol alur seperti if, for, dan while
  • Ada kelompok instruksi tersendiri untuk memanggil metode lain
    • Cara menentukan metode yang akan dipanggil mencakup lookup virtual dan lookup statis
    • Setelah metode target di-resolve, frame baru ditambahkan ke call stack dan eksekusi dimulai
    • Jika nilai kembalian bukan void, nilai itu akan di-push ke stack dan eksekusi dilanjutkan

Penanganan exception

  • Exception memutus alur kontrol normal, menyebabkan return lebih awal dari metode, dan bisa merambat sepanjang call stack, sehingga implementasinya rumit
  • Setiap blok catch berkorespondensi dengan satu entri tabel exception milik metode
  • Entri tabel exception berisi informasi yang diperlukan untuk menemukan handler
    • rentang program counter yang berlaku
    • alamat instruksi pertama dari blok catch
    • nama kelas exception yang ditangkap blok tersebut
  • CallFrame::execute_instruction memakai Result dari Rust untuk menyatakan hasil eksekusi instruksi
  • Hasil eksekusi instruksi dibagi menjadi empat status
    • berhasil dan melanjutkan eksekusi metode saat ini
    • berhasil dan, karena instruksi return, metode saat ini selesai beserta nilai kembaliannya
    • eksekusi gagal karena galat internal VM
    • eksekusi gagal karena exception Java dilempar
  • Loop eksekusi metode mem-parsing instruksi, memindahkan program counter ke alamat berikutnya, lalu mengeksekusi instruksi
  • Jika exception terjadi, handler exception yang cocok untuk posisi instruksi saat ini akan dicari
    • jika tidak ada handler, exception diteruskan ke pemanggil
    • jika ada handler, objek exception di-push kembali ke stack dan eksekusi dilanjutkan dari posisi handler catch
  • Result dan pattern matching di Rust sangat cocok untuk mengekspresikan perilaku ini dalam struktur kode

Garbage collection

  • Tonggak besar terakhir rjvm adalah implementasi garbage collector
  • Algoritme yang dipilih adalah stop-the-world semispace copying collector
  • Karena tidak ada thread, pendekatan stop-the-world berlaku secara alami
  • Implementasinya adalah variasi yang lebih sederhana dari algoritme Cheney, dan kodenya ada di gc.rs
  • Pendekatan ini membagi memori yang tersedia menjadi dua semispace
    • satu sebagai area aktif untuk alokasi objek
    • satu lagi dibiarkan sebagai area yang tidak digunakan
    • ketika area aktif penuh, objek yang masih hidup disalin ke semispace lain
    • semua referensi objek diperbarui agar menunjuk ke salinan yang baru
    • peran kedua semispace kemudian ditukar
  • Prosedur ini dianalogikan dengan pendekatan yang mirip blue-green deployment
  • Algoritme ini memiliki kelebihan dan kekurangan yang jelas
    • hanya setengah dari memori maksimum yang bisa digunakan, sehingga pemborosan memori cukup besar
    • alokasi sangat cepat karena hanya menaikkan pointer
    • karena objek disalin dan dipadatkan, tidak perlu menangani fragmentasi memori
    • pemadatan objek dapat meningkatkan kinerja lewat pemanfaatan cache line yang lebih baik
  • VM Java nyata umumnya menggunakan garbage collector generasional yang lebih canggih seperti G1 atau parallel GC

Titik akhir proyek

  • Dengan membuat rjvm, banyak hal dipelajari tentang Rust dan implementasi mesin virtual, terutama kepuasan karena berhasil membuat garbage collector yang benar-benar bekerja
  • Garbage collector ini belum terlalu matang, tetapi benar-benar berfungsi
  • Karena target awal telah tercapai, proyek dihentikan sampai di sini
  • Ada bug yang sudah diketahui, tetapi tidak ada rencana untuk memperbaikinya
  • Rust adalah bahasa yang menyenangkan untuk dipakai membangun JVM, dan di tulisan berikutnya implementasi rjvm serta cara kerja JVM akan dibahas lebih detail

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-22
Komentar Hacker News

  • Bagian sulit dalam implementasi garbage collection adalah memastikan semua referensi benar-benar tertangkap sebagai root, terutama pada collector yang memindahkan objek
    Metode do_garbage_collection ditandai sebagai unsafe[1], tetapi tidak ada penjelasan tentang apa yang harus dijamin oleh pihak pemanggil agar bisa memanggilnya dengan aman
    Saya penasaran bagaimana mereka menjamin bahwa semua referensi ke heap tertangkap sebagai root, dan ini bukan masalah sepele[2][3][4]
    Selain itu, setelah meng-clone repositori dan menjalankan cargo test, semua test gagal dengan error should be able to add entries to the classpath: InvalidEntry(".../vm/rt.jar"): vm/tests/integration/real_code_tests.rs:15:10
    [1] https://github.com/andreabergia/rjvm/blob/be9c54066c64a82879...
    [2] https://manishearth.github.io/blog/2021/04/05/a-tour-of-safe...
    [3] https://without.boats/blog/shifgrethor-iii/
    [4] https://coredumped.dev/2022/04/11/implementing-a-safe-garbag...

    • VM ini memelihara stack pemanggilan virtual sendiri, bukan stack pemanggilan native, jadi cukup intuitif
      Karena itu, stack tersebut bisa ditelusuri untuk menemukan parameter dan variabel lokal, lalu menggunakannya sebagai root
      Pendekatan seperti ini punya biaya performa, tetapi tracing untuk garbage collection menjadi jauh lebih sederhana, dan primitive konkurensi maupun alur kontrol seperti coroutine atau continuation juga lebih mudah diimplementasikan
    • Garbage collector pada dasarnya adalah pembukuan yang teliti, jadi relatif mudah, tetapi begitu mulai membuat garbage collection konkuren, tingkat kesulitannya langsung seperti neraka

  • Proyek yang bagus, selamat
    Namun bagian “yang tidak didukung: generics” terasa agak aneh
    Saya penasaran dalam arti apa JVM harus mendukung generics
    Pada level bytecode, karena type erasure, bukankah semuanya bisa dianggap sederhana sebagai Object, yaitu tipe referensi? Atau yang dimaksud parser definisi class? Meski begitu, selain sintaks dasar, sepertinya tidak ada logika untuk memeriksa apakah class file valid

    • Soal generics, hal yang sama juga muncul di reddit, dan itu benar
      Yang sebenarnya perlu dilakukan hanya membaca atribut Signature yang memuat informasi generics untuk class, method, dan field (https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.ht...)
      Saya baru saja mencobanya, dan kode di bawah ini juga berjalan :-)
      public class Generic { public static void main(String[] args) { List strings = new ArrayList(10); strings.add("hey"); strings.add("hackernews"); for (String s : strings) { tempPrint(s); } } private static native void tempPrint(String value); }
    • Mungkin yang dimaksud adalah operasi checkcast: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.ht...
      Misalnya, kode seperti final Main value = list.get(0); akan menghasilkannya
      http://henrikeichenhardt.blogspot.com/2013/05/how-are-java-g...
    • Secara umum benar. Generics kadang memengaruhi reflection, tetapi reflection juga belum didukung, dan secara keseluruhan digantikan pada waktu kompilasi dengan class atau interface terdekat
      Sebaliknya, tidak adanya string interning terasa sangat aneh. Implementasinya juga cenderung sepele, dan tanpa ini sulit menyebutnya JVM
      Kesamaan string berdasarkan referensi itu penting dan merupakan bagian dari JLS
      Tidak adanya thread membuat seluruh upaya ini terasa setingkat proyek mainan

  • Benar-benar keren. Saat saya bergabung mengerjakan Java pada 1992, namanya masih Oak, dan grup tempat saya berada sedang melihat arah untuk menulis seluruh sistem operasi dengan Java
    Idenya adalah mengurangi permukaan serangan sistem operasi tertanam dengan hanya menyisakan bagian minimum yang diperlukan sebagai “bahasa mesin”, yaitu metode native
    Awalnya Java ditujukan untuk berjalan di tempat seperti TV atau peralatan rumah tangga, dan saat itu metode native dikerjakan dengan C, bukan Rust
    JVM yang dibuat dengan Rust menambahkan keamanan memori yang cukup kuat ke seluruh proses ini

  • Implementasi JVM 17 yang ditulis dengan Go, https://jacobin.org/, juga layak dilihat

    • Ada juga https://github.com/lihaoyi/Metascala, JVM yang diimplementasikan dengan Scala dan berjalan di atas JVM
    • Sebagai nama proyek pemrograman, ini cukup menarik
      Jacobins adalah klub politik revolusioner pada masa Revolusi Prancis tahun 1790-an, dan juga nama majalah di https://jacobin.com

  • Saya penasaran apakah mereka terbentur batasan karena parameter lifetime pada signature ini
    fn execute_instruction(&mut self, vm: &mut Vm<'a>, call_stack: &mut CallStack<'a>, instruction: Instruction) -> Result, MethodCallFailed<'a>>
    Jika Anda menambahkan lifetime ke varian Err dari Result dan lifetime itu invariant, seperti biasanya terjadi di sini karena vm dan call_stack, Anda biasanya jadi tidak bisa memakai operator ? atau melakukan early return[1]
    Akibatnya penanganan error menjadi lebih bertele-tele dan sulit dibaca; saya penasaran apakah memang seperti itu pengalamannya
    [1] https://users.rust-lang.org/t/nll-and-early-return-not-allow...

  • Ini proyek belajar yang bagus, dan menyenangkan melihat penulisnya menikmatinya
    Mengimplementasikan VM dari nol itu benar-benar menyenangkan, dan dulu saya banyak belajar saat mengerjakan hal semacam itu
    Jika ingin mencoba menambahkan garbage collection, ada baiknya melihat MMTk (https://www.mmtk.io/)
    Ada algoritma koleksi berkualitas tinggi yang dirancang agar bisa dipasang ke berbagai VM, dan ditulis dengan Rust

    • Sebagai catatan, MMTK khusus x86
      Saya sempat ingin memakainya untuk proyek mainan, tapi menyerah karena memakai Mac

  • Dibuat dengan sangat baik
    Membuat VM selalu menyenangkan, dan jika digabungkan dengan sistem tipe Rust, sepertinya ini menjadi pengalaman belajar yang menarik
    Jika sedang mencari pekerjaan, silakan hubungi saya lewat Twitter, Mastodon, atau email perusahaan. Seharusnya bisa ditemukan dari ID pengguna saya di sini

  • Saat melihat proyek sekeren ini, rasanya kewalahan
    Saya ingin penulis aslinya menjelaskan bagaimana memulai Rust dan seberapa jauh perlu menguasai dasar-dasarnya sampai bisa mencoba hal seperti ini

    • Saya juga merasakan hal yang sama
      Saya tidak ingin terlalu melenceng, tetapi secara pribadi belakangan ini saya cukup bergulat dengan perasaan seperti ini
      Saya sudah bekerja sebagai pengembang perangkat lunak profesional hampir 10 tahun, dan melihat jabatan saya saat ini serta kemampuan saya untuk benar-benar merilis produk, saya tahu saya kompeten dan bukan pengembang palsu
      Namun belakangan ini, saat membaca blog pengembang, saya merasa kewalahan seolah-olah saya tidak cukup tahu dan bukan pengembang “sungguhan”
      Sepertinya perasaan ini muncul karena saya membuat sosok pengembang ideal di kepala, lalu membandingkan diri saya dengan standar khayalan itu
      Sambil mengagumi orang-orang yang punya banyak pengetahuan mendalam dan mampu mengungkapkannya dengan jelas dan ringkas, saya jadi bertanya-tanya mengapa saya tidak seperti itu
      Setelah selesai bekerja dan mengurus keluarga, saya hampir tidak punya energi untuk melakukan hal lain, dan saya juga tahu pemrograman bukan segalanya, tetapi tetap ada keinginan untuk belajar lebih banyak dan berkembang
      Saya tahu ini tidak sehat dan tidak rasional, tetapi belakangan ini perasaan itu sulit disingkirkan
    • Jujur saja, hampir setiap kali membuka HN saya merasakan sindrom impostor
      Dulu saya punya sedikit pengalaman dengan VM, dan beberapa tahun lalu pernah menulis seri tulisan pendek di blog
      Di pekerjaan sebelumnya, saya juga pernah sedikit mengutak-atik bytecode JVM untuk menyelesaikan masalah pelanggan yang sangat spesifik
      Beberapa tahun lalu saya juga membaca https://craftinginterpreters.com/ yang sangat bagus, dan mendapat ide dari sana
      Namun proyek ini jelas besar dan kompleks
      Ini memakan banyak waktu, dan seperti banyak proyek sampingan saya, sempat beberapa kali terbengkalai, tetapi saya senang akhirnya selesai :-)
    • Saya bukan ahli Rust dan juga bukan penulis aslinya, tetapi saya bisa memberi contoh dari teknologi lain, yaitu socket
      Baru-baru ini saya mendalami socket, dan dua minggu lalu saya hanya punya pemahaman tingkat tinggi yang didapat dari membaca sekilas halaman manual, dokumentasi, tulisan blog, dan sebagainya
      Karena ingin memahami dasar-dasar networking, saya memutuskan untuk membaca sebanyak mungkin, dan seminggu kemudian saya sudah belajar cukup untuk menulis kode socket dengan Python dan C
      Karena saya cukup memahami Python, setelah mendalaminya, melihat library sockets jadi lebih mudah dipahami
      Jika Anda ingin lebih mahir pada teknologi A dengan bahasa X, saya menyarankan untuk membaca atau menonton sebanyak mungkin tentang teknologi A, lalu mencoba membuat sesuatu dengan bahasa Y
      Setelah itu, ketika kembali ke bahasa X, Anda sudah cukup banyak menguasai konsep di sekitar teknologi A
    • Pecah saja menjadi bagian-bagian kecil
      VM untuk bahasa sederhana mungkin memiliki representasi objek di memori, interpreter bytecode, garbage collector sederhana, dan loader
      Interpreter bytecode bisa dilihat sebagai stack, cara merepresentasikan fungsi di atas stack itu, serta loop yang menafsirkan setiap bytecode dan menggerakkan program counter
    • Yang penting adalah seberapa banyak Anda ngoding di waktu luang. Rata-rata berapa jam per minggu
      Jika 0 jam, tentu itu bukan sesuatu yang patut disalahkan dan ada banyak hal lain yang bisa difokuskan, tetapi tidak mengherankan jika orang yang selama bertahun-tahun rata-rata mengerjakan proyek sampingan 10–20 jam per minggu menghasilkan sesuatu yang mengesankan

  • Sekalian promosi tanpa malu-malu proyek serupa: https://github.com/tenaf0/rust-jvm3

  • Saya sedang membuat sistem operasi gratis untuk klon 386(486) AT. Ini hanya hobi, bukan sesuatu yang besar dan profesional seperti gnu :-)

    • Ada tutorial no-std untuk menulis kernel demo dengan Rust: https://os.phil-opp.com
      osdev.org, sandpile.org, RBIL, dan freevga juga layak dijadikan referensi
      Sakit kepala terbesarnya adalah dukungan hardware
      Ada juga banyak buku kertas vintage yang bagus berisi resep seperti port I/O yang andal atau trik hardware yang tidak terdokumentasi
      Intel® 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 2D, 3A, 3B, 3C, 3D, and 4
      Microsoft MS-DOS Programmer's Reference, termasuk pemanggilan BIOS real-mode
      PC Interrupts
      Undocumented PC
      PC Intern
      Programmer's Guide To The EGA, VGA, And Super VGA Cards
      Graphics Programming Black Book Special Edition
      Perkembangan pengembangan sistem operasi setelah era kernel monolitik, microkernel, dan hibrida juga layak dieksperimenkan
      Struktur berbasis capability seperti seL4 memiliki sejumlah keunggulan mendasar dalam performa dan keamanan, termasuk capability dan IPC yang unggul
      Lapisan kompatibilitas POSIX juga penting. Sistem operasi embedded yang tidak memiliki konsep thread atau proses pun bisa mengimplementasikan POSIX
      Hypervisor jauh lebih mudah ditambahkan jika ada Intel VT-[xd], dan jika tidak ada, bisa mundur ke emulasi. Emulasi berbasis translasi memiliki performa yang sangat baik
      Anda perlu mahir menggeneralisasi dan mempercepat interrupt handler, menghindari race condition, dan menggunakan pola lock-free
      Juga perlu menulis ulang atau menjebak instruksi yang tidak didukung, termasuk x87 dan MMX
      Alasan microkernel murni gagal adalah karena kompleksitas untuk mengurutkan dan mengelola berbagai resource secara transaksional menjadi besar
      Arsitektur microkernel secara teori memiliki keunggulan besar dalam keamanan dan operasional, tetapi dalam bentuk murninya tidak pernah tersebar luas