Una JVM escrita en Rust

 (andreabergia.com)
3 puntos por GN⁺ 2023-07-22 | 1 comentarios | Compartir por WhatsApp
  • rjvm, un proyecto paralelo para aprender Rust, es una JVM de juguete para aprendizaje, pero llega hasta implementar la lectura de .class y jar reales y la ejecución de bytecode de Java
  • Las funciones no compatibles son hilos, reflexión, anotaciones, I/O, compilador JIT e internado de cadenas, pero sí incluye flujo de control, creación de objetos, llamadas a métodos, excepciones y recolección de basura
  • Los ejemplos usan el rt.jar real de OpenJDK 7, por lo que clases como java.lang.StackTraceElement se cargan desde un JDK real
  • El código está dividido en tres crates de Rust: reader, vm y vm_cli, y cubre desde el parseo de .class hasta la pila de llamadas, métodos nativos y el modelado de valores y objetos
  • El último hito fue un stop-the-world semispace copying collector; una vez alcanzado el objetivo, el proyecto se detiene y no hay planes de corregir bugs conocidos

rjvm, una JVM de Rust para aprendizaje

  • rjvm es una Java Virtual Machine de juguete creada para aprender Rust
  • El código está publicado en GitHub
  • Más que una implementación seria de JVM, es una implementación con fines de aprendizaje, por lo que no soporta las siguientes funciones
    • hilos
    • reflexión
    • anotaciones
    • I/O
    • compilador JIT
    • internado de cadenas
  • Los genéricos aparecían al principio en la lista de no compatibles, pero en la práctica sí funcionan

Hasta dónde llega la implementación

  • rjvm no se queda en un parser simple, sino que implementa directamente varios comportamientos de la JVM
    • flujo de control como if y for
    • tipos primitivos y creación de objetos
    • llamadas a métodos virtuales y estáticos
    • manejo de excepciones
    • recolección de basura
    • resolución de clases desde archivos jar
  • El código de prueba incluye ejemplos que usan Throwable, Exception y StackTraceElement
  • Como no hay I/O real, usa un método nativo llamado tempPrint en lugar de System.out.println
  • Los ejemplos usan el rt.jar real de OpenJDK 7, y java.lang.StackTraceElement también se obtiene del JDK real

Tres crates de Rust

  • El proyecto es un proyecto estándar de Rust y está compuesto por tres crates
    • reader: contiene tipos para leer archivos .class y modelar su contenido
    • vm: ofrece, en forma de biblioteca, una máquina virtual capaz de ejecutar código
    • vm_cli: incluye un lanzador simple de línea de comandos, similar al ejecutable java
  • Se está considerando separar el crate reader en un repositorio independiente y publicarlo en crates.io

Parseo de archivos .class

  • El código Java se compila con javac en archivos .class, y normalmente se distribuye en archivos .jar, que tienen formato zip
  • Para ejecutar código Java, primero hay que cargar el archivo .class que contiene el bytecode generado por el compilador
  • El archivo de clase también contiene la información necesaria para la ejecución y la resolución de tipos
    • metadatos como el nombre de la clase y el nombre del archivo fuente
    • nombre de la superclase
    • interfaces implementadas
    • campos y tipos de campo, anotaciones
    • descriptores de métodos, cláusulas throws, anotaciones e información genérica
    • bytecode, tabla de manejadores de excepciones y tabla de números de línea
  • El crate reader parsea archivos de clase y devuelve una struct de Rust que modela la clase y su contenido

Ejecución de métodos y pila de llamadas

  • La API principal del crate vm es Vm::invoke, usada para ejecutar métodos
  • Cada método en ejecución tiene un CallFrame dentro de un CallStack
  • Al ejecutar main, la pila de llamadas empieza vacía y se crea un nuevo frame para iniciar la ejecución
  • Cada llamada a función agrega un nuevo frame a la pila de llamadas, y cuando termina la ejecución del método, ese frame se elimina
  • La mayoría de los métodos están implementados en bytecode de Java, pero rjvm también soporta métodos nativos
    • Los métodos nativos no están implementados en bytecode de Java, sino directamente por la propia JVM
    • Algunos ejemplos son System::currentTimeMillis, System::arraycopy y Throwable::fillInStackTrace
    • En rjvm, están implementados como funciones de Rust
  • La JVM es una máquina virtual basada en pila, así que las instrucciones de bytecode operan principalmente sobre una pila de valores
  • Cada frame de llamada tiene asociada una pila de valores y un conjunto de variables locales identificadas por índice

Modelado de valores y objetos

  • Value modela los valores que pueden almacenarse en variables locales, elementos de la pila y campos de objetos
  • Value está implementado como un enum de Rust e incluye los siguientes estados
    • Uninitialized
    • Int(i32)
    • Long(i64)
    • Float(f32)
    • Double(f64)
    • Object(AbstractObject<'a>)
    • Null
  • Los tipos suma como enum en Rust son muy adecuados para expresar que un solo valor puede ser uno entre varios tipos
  • El almacenamiento de objetos comenzó con una struct Object simple basada en Vec<Value>, que guardaba una referencia a la clase y valores de campos
  • Después de implementar el recolector de basura, cambió a una implementación de más bajo nivel que usa muchos punteros y casts
  • Actualmente, AbstractObject modela objetos reales o arreglos, y es un puntero a un arreglo de bytes que contiene algunas header words y los valores de los campos

Ejecución de instrucciones de bytecode

  • La ejecución de un método es el proceso de manejar las instrucciones de bytecode una por una
  • Hay más de 200 instrucciones de JVM, y en bytecode se codifican en 1 byte
  • Muchas instrucciones llevan argumentos a continuación y algunas tienen longitud variable
  • rjvm modela las instrucciones de bytecode de Java con el tipo Instruction
  • Al ejecutar un método, se mantiene la pila de valores y el arreglo de variables locales, y el contador de programa se inicializa en 0, que es la dirección de la siguiente instrucción a ejecutar
  • Normalmente, después de ejecutar una instrucción, el contador de programa avanza a la siguiente, pero las instrucciones de salto pueden moverlo a otra posición
  • Las instrucciones de salto se usan para implementar estructuras de control de flujo como if, for y while
  • También existe una familia aparte de instrucciones para invocar otros métodos
    • Hay varias formas de determinar qué método llamar, como resolución virtual y resolución estática
    • Tras resolver el método objetivo, se agrega un nuevo frame a la pila de llamadas y comienza la ejecución
    • Si el valor de retorno no es void, se hace push del valor devuelto en la pila y la ejecución se reanuda

Manejo de excepciones

  • Las excepciones rompen el flujo de control normal, provocan retornos anticipados desde métodos y pueden propagarse a través de la pila de llamadas, por lo que su implementación es compleja
  • Cada bloque catch corresponde a una entrada de la tabla de excepciones del método
  • Una entrada de la tabla de excepciones contiene la información necesaria para encontrar un manejador
    • el rango del contador de programa al que aplica
    • la dirección de la primera instrucción del bloque catch
    • el nombre de la clase de excepción que ese bloque captura
  • CallFrame::execute_instruction usa Result de Rust para expresar el resultado de ejecutar una instrucción
  • El resultado de ejecutar una instrucción se divide en cuatro estados
    • fue exitoso y continúa la ejecución del método actual
    • fue exitoso y, al ser una instrucción return, el método actual termina junto con su valor de retorno
    • la ejecución falla por un error interno de la VM
    • la ejecución falla porque se lanzó una excepción de Java
  • El bucle de ejecución de métodos parsea una instrucción, mueve el contador de programa a la siguiente dirección y luego ejecuta la instrucción
  • Si ocurre una excepción, busca un manejador de excepciones que coincida con la posición de la instrucción actual
    • si no hay manejador, propaga la excepción al llamador
    • si lo hay, vuelve a hacer push del objeto de excepción en la pila y continúa la ejecución en la posición del manejador catch
  • Result de Rust y el pattern matching encajan muy bien para expresar esta lógica en la estructura del código

Recolección de basura

  • El último gran hito de rjvm fue la implementación del recolector de basura
  • El algoritmo elegido fue un stop-the-world semispace copying collector
  • Como no hay hilos, el enfoque stop-the-world se cumple de forma natural
  • La implementación es una variante más simple del algoritmo de Cheney, y el código está en gc.rs
  • Este enfoque divide la memoria disponible en dos semispaces
    • uno se usa como área activa para asignar objetos
    • el otro queda como área sin usar
    • cuando el área activa se llena, los objetos vivos se copian al otro semispace
    • todas las referencias a objetos se actualizan para que apunten a las nuevas copias
    • se intercambian los roles de los dos semispaces
  • Este procedimiento se compara, a modo de analogía, con un blue-green deployment
  • El algoritmo tiene ventajas y desventajas claras
    • no puede usar hasta la mitad de la memoria máxima, por lo que hay mucho desperdicio de memoria
    • la asignación es muy rápida porque solo incrementa punteros
    • como copia y compacta objetos, no hace falta lidiar con la fragmentación de memoria
    • la compactación de objetos puede mejorar el rendimiento al aprovechar mejor las líneas de caché
  • Las VM de Java reales suelen usar recolectores generacionales más sofisticados, como G1 o parallel GC

El punto final del proyecto

  • Al crear rjvm, se aprendió mucho sobre Rust y sobre la implementación de máquinas virtuales, y en especial hubo satisfacción con haber implementado un recolector de basura que realmente funciona
  • El recolector de basura no tiene un nivel de terminación muy alto, pero sí funciona en la práctica
  • Como el objetivo original ya se cumplió, el proyecto se detiene aquí
  • Hay bugs conocidos, pero no hay planes de corregirlos
  • Rust fue un lenguaje divertido de usar para implementar una JVM, y en publicaciones posteriores se planea tratar con más detalle la implementación de rjvm y el funcionamiento de la JVM

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-22
Opiniones en Hacker News

  • Lo difícil de implementar recolección de basura es asegurarse de que todas las referencias queden correctamente marcadas como raíces, sobre todo en recolectores con movimiento
    El método do_garbage_collection está marcado como unsafe[1], pero no explica qué debe garantizar quien lo llama para invocarlo de forma segura
    Me pregunto cómo se garantiza que todas las referencias al heap queden marcadas como raíces, y no es un problema trivial[2][3][4]
    Además, cloné el repositorio y ejecuté cargo test, y todas las pruebas fallan con el 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...

    • Esta VM mantiene su propia pila de llamadas virtual en lugar de usar la pila de llamadas nativa, así que es bastante intuitivo
      Por eso se puede recorrer esa pila para encontrar parámetros y variables locales, y usarlos como raíces
      Este enfoque tiene un costo de rendimiento, pero simplifica mucho el rastreo para la recolección de basura y también facilita implementar primitivas de concurrencia y de flujo de control como corrutinas o continuations
    • Los garbage collectors son básicamente contabilidad minuciosa, así que tienden a ser bastante fáciles; pero en cuanto empiezas con recolección de basura concurrente, se vuelven endemoniadamente difíciles

  • Buen proyecto, felicitaciones
    Sin embargo, la parte de “no soportado: genéricos” me resulta un poco rara
    Me pregunto qué significaría soportar genéricos en la JVM
    A nivel de bytecode, por el borrado de tipos, ¿no se puede pensar simplemente que todo es Object, es decir, tipos de referencia? ¿O se refiere al parser de definiciones de clases? Aun así, fuera de la sintaxis básica, no parece haber lógica para verificar si un archivo de clase es válido

    • Sobre los genéricos, en reddit salió el mismo comentario, y es correcto
      En realidad, lo que habría que hacer es leer el atributo Signature, que contiene la información genérica de clases, métodos y campos (https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-4.ht...)
      De hecho, acabo de probarlo y el siguiente código también funciona :-)
      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); }
    • Quizás se refiera a la operación checkcast: https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.ht...
      Por ejemplo, se genera si escribes código como final Main value = list.get(0);
      http://henrikeichenhardt.blogspot.com/2013/05/how-are-java-g...
    • En general, sí. Los genéricos rara vez afectan la reflexión, pero la reflexión tampoco está soportada, y en general se sustituyen en compilación por la clase o interfaz más cercana
      En cambio, que no haya internado de strings es muy raro. Además, implementarlo es relativamente trivial; sin eso, difícilmente se puede considerar una JVM
      Que los strings sean iguales por referencia es importante y forma parte del JLS
      La falta de threads convierte todo el intento en algo al nivel de un proyecto de juguete

  • Realmente genial. Cuando me sumé al trabajo en Java en 1992, se llamaba Oak, y el grupo en el que estaba estaba mirando hacia la idea de escribir todo un sistema operativo en Java
    La idea era reducir la superficie de ataque de un sistema operativo embebido dejando solo la parte mínima necesaria en “código máquina”, es decir, métodos nativos
    Originalmente Java apuntaba a correr en lugares como televisores o electrodomésticos, y en ese entonces los métodos nativos se trabajaban en C, no en Rust
    Una JVM hecha en Rust le suma bastante seguridad de memoria a todo este proceso

  • También vale la pena ver https://jacobin.org/, una implementación de JVM 17 escrita en Go

    • También está https://github.com/lihaoyi/Metascala, una JVM implementada en Scala que se ejecuta sobre la JVM
    • Como nombre para un proyecto de programación, es bastante interesante
      Los jacobinos fueron un club político revolucionario de la Revolución francesa en la década de 1790, y también es el nombre de la revista en https://jacobin.com

  • Me pregunto si se toparon con límites por el parámetro de vida útil de esta firma
    fn execute_instruction(&mut self, vm: &mut Vm<'a>, call_stack: &mut CallStack<'a>, instruction: Instruction) -> Result, MethodCallFailed<'a>>
    Si se agrega una vida útil a la variante Err de Result y esa vida útil es invariante, como suele pasar aquí por vm y call_stack, normalmente ya no se puede usar el operador ? ni retornos tempranos[1]
    Eso hace que el manejo de errores sea más verboso y difícil de leer, y me pregunto si esa fue efectivamente la experiencia
    [1] https://users.rust-lang.org/t/nll-and-early-return-not-allow...

  • Es un excelente proyecto de aprendizaje, y me alegra que el autor se esté divirtiendo
    Implementar una VM desde cero es realmente divertido, y en el pasado aprendí mucho haciendo ese tipo de trabajo
    Si quieres agregarle recolección de basura, podrías echarle un vistazo a MMTk (https://www.mmtk.io/)
    Tiene algoritmos de recolección de alta calidad diseñados para integrarse en varias VM, y está escrito en Rust

    • Para que conste, MMTk es solo para x86
      Intenté usarlo en un proyecto de juguete, pero lo dejé porque uso Mac

  • Muy bien hecho
    Crear una VM siempre es divertido, y combinado con el sistema de tipos de Rust debe haber sido una experiencia de aprendizaje interesante
    Si estás buscando trabajo, puedes contactarme por Twitter, Mastodon o el correo de la empresa. Deberías poder encontrarme por mi ID de usuario aquí

  • Ver proyectos tan geniales como este me hace sentir abrumado.
    Me gustaría que el autor original explicara cómo empezar con Rust y qué tanto dominio de los fundamentos hace falta para animarse a intentar algo así.

    • Me pasa lo mismo.
      No quiero desviarme demasiado del tema, pero personalmente últimamente estoy lidiando bastante con este sentimiento.
      Llevo casi 10 años trabajando como desarrollador de software profesional y, viendo mi puesto actual y mi capacidad real para lanzar productos, sé que soy competente y que no soy un desarrollador falso.
      Pero últimamente, cuando leo blogs de desarrolladores, me siento abrumado, como si no supiera lo suficiente y no fuera un desarrollador “de verdad”.
      Creo que este sentimiento surge porque tengo en la cabeza una imagen idealizada de lo que es un desarrollador y me comparo con ese estándar imaginario.
      Admiro a las personas que tienen mucho conocimiento profundo y lo expresan de forma clara y concisa, pero también termino preguntándome por qué yo no soy así.
      Después del trabajo y de cuidar a mi familia, casi no me queda energía para hacer algo más, y sé que la programación no lo es todo, pero aun así tengo ganas de aprender más y crecer.
      Sé que no es sano ni racional, pero últimamente es un sentimiento difícil de sacudirme.
    • Honestamente, casi la mitad de las veces que abro HN siento síndrome del impostor.
      Antes tuve algo de experiencia con VM, y hace unos años escribí una breve serie de posts en un blog.
      En un trabajo anterior también llegué a tocar un poco el bytecode de la JVM para resolver un problema muy particular de un cliente.
      Además, hace unos años leí el excelente https://craftinginterpreters.com/, de donde saqué ideas.
      Pero este proyecto sin duda fue grande y complejo.
      Me tomó mucho tiempo y, como muchos de mis proyectos paralelos, también quedó abandonado algunas veces, pero me alegra haberlo terminado :-)
    • No soy experto en Rust ni el autor original, pero puedo poner como ejemplo otra tecnología: los sockets.
      Hace poco me metí a fondo con sockets; hace dos semanas solo tenía una comprensión de alto nivel obtenida leyendo por encima páginas de manual, documentación, posts de blogs, etc.
      Como quería entender los fundamentos de redes, decidí leer todo lo que pudiera, y una semana después ya había aprendido lo suficiente como para escribir código con sockets en Python y C.
      Como conozco bastante bien Python, después de profundizar me resultó más fácil entender la biblioteca sockets.
      Si quieres mejorar en la tecnología A con el lenguaje X, recomiendo leer o ver todo lo que puedas sobre la tecnología A y construir algo en el lenguaje Y.
      Luego, cuando vuelvas al lenguaje X, ya habrás aprendido bastante de los conceptos alrededor de la tecnología A.
    • Hay que dividirlo en partes pequeñas.
      Una VM para un lenguaje simple probablemente tenga una representación de objetos en memoria, un intérprete de bytecode, un recolector de basura sencillo y un cargador.
      El intérprete de bytecode puede verse como una pila, una forma de representar funciones sobre esa pila y un bucle que interpreta cada bytecode y mueve el contador de programa.
    • Importa cuánto programas en tu tiempo libre. En promedio, cuántas horas por semana.
      Si son 0 horas, por supuesto no es algo reprochable y hay muchas otras cosas en las que enfocarse, pero no sorprende que alguien que durante años dedicó en promedio entre 10 y 20 horas semanales a proyectos paralelos termine produciendo algo impresionante.

  • Promocionando descaradamente un proyecto parecido: https://github.com/tenaf0/rust-jvm3

  • Estoy creando un sistema operativo libre para clones AT 386(486). Es solo un hobby, no será algo grande y profesional como gnu :-)

    • Hay un tutorial no-std para escribir un kernel de demostración en Rust: https://os.phil-opp.com
      También vale la pena consultar osdev.org, sandpile.org, RBIL y freevga.
      El mayor dolor de cabeza es el soporte de hardware.
      También hay muchos buenos libros antiguos en papel con recetas como I/O de puertos confiable o trucos de hardware no documentados.
      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, incluidas llamadas BIOS en modo real
      PC Interrupts
      Undocumented PC
      PC Intern
      Programmer's Guide To The EGA, VGA, And Super VGA Cards
      Graphics Programming Black Book Special Edition
      También vale la pena experimentar con los avances en desarrollo de sistemas operativos posteriores a las eras de los kernels monolíticos, microkernels e híbridos.
      Las estructuras basadas en capabilities, como seL4, tienen varias ventajas inherentes de rendimiento y seguridad, incluidas las capabilities y un IPC excelente.
      Una capa de compatibilidad POSIX también es importante. Incluso un sistema operativo embebido sin conceptos de hilos o procesos puede implementar POSIX.
      Un hipervisor puede agregarse mucho más fácilmente si se cuenta con Intel VT-[xd]; si no, se puede recurrir a la emulación. La emulación por traducción tiene muy buen rendimiento.
      Hay que volverse hábil en generalizar y acelerar los manejadores de interrupciones, evitar condiciones de carrera y usar patrones lock-free.
      También hace falta reescribir o atrapar instrucciones no soportadas, incluidas x87 y MMX.
      La razón por la que los microkernels puros fracasaron fue el aumento de la complejidad necesaria para ordenar y gestionar varios recursos de forma transaccional.
      Las arquitecturas de microkernel tienen, en teoría, grandes ventajas de seguridad y operación, pero en su forma pura no lograron imponerse ampliamente.