Gestión de Punteros Cíclicos y GC en Rust Seguro: Un Deep Dive en 'gc-arena'

El sistema de propiedad y descarte determinista de Rust, si bien garantiza la seguridad de memoria y el rendimiento predecible, presenta una dificultad fundamental para la gestión de estructuras de datos con referencias cíclicas. A diferencia de los lenguajes garbage-collected que se basan en la 'alcanzabilidad' para liberar memoria, Rust requiere una propiedad clara, lo que hace que los ciclos de punteros sean problemáticos para el compilador. Este problema no es meramente académico; surge en la implementación de máquinas virtuales, motores de juegos y lenguajes de scripting dentro de Rust, donde las estructuras de datos intrínsecamente cíclicas son comunes. La tesis central es que, mediante el uso de características avanzadas del sistema de tipos de Rust, como la generatividad y los GATs, es posible construir un sistema de recolección de basura por trazado completamente seguro y eficiente que resuelva el problema de las referencias cíclicas, ofreciendo una alternativa a los índices basados en Vec o los punteros crudos.

Históricamente, la gestión automática de memoria ha tomado dos caminos principales: el conteo de referencias/propiedad (como en Rust, Swift, C++) y la recolección de basura por trazado (como en Java, Go, Python). Rust optó por el primero para ofrecer control determinista sobre los recursos, pero esto implica que los objetos en un ciclo de referencias nunca alcanzarán un conteo de referencias de cero, lo que impide su liberación automática. Esto ha llevado a soluciones como Rc<RefCell<T>> o Weak<T>, que añaden sobrecarga o complejidad. La propuesta aquí es reevaluar la GC por trazado no como un reemplazo global, sino como una 'estructura de datos elegante' que puede integrarse selectivamente para problemas específicos, como las VMs, donde la alcanzalibilidad es el modelo natural de gestión de memoria.

Arquitectura del Sistema

La solución propuesta se construye iterativamente, comenzando con un SlotAlloc basado en Vec e índices usize para representar punteros. Para mitigar problemas como el 'use-after-free' y el problema ABA, se introducen 'índices generacionales' que combinan el índice con un contador de generación, y un alloc_id para prevenir la confusión entre diferentes SlotAllocs. Estos índices, aunque seguros en tiempo de ejecución, carecen de las garantías en tiempo de compilación de las referencias de Rust.

Para lograr seguridad en tiempo de compilación, se introduce el concepto de 'generatividad' de tipos, utilizando un PhantomData<Cell<&'id ()>> para crear un Id<'id> invariante sobre su lifetime. Este Id se usa para 'marcar' (brand) los punteros Gc<'gc> y las instancias de ArenaCtx<'gc>, asegurando que un Gc solo pueda usarse con el ArenaCtx que lo generó. La Arena principal encapsula un ArenaCtx<'static> y proporciona un método enter que, a través de un HRTB (for<'gc> FnOnce(&mut ArenaCtx<'gc, A>) -> R), genera un lifetime 'gc único para cada invocación, permitiendo que los Gc<'gc> se comporten como punteros seguros dentro de ese contexto.

Para manejar múltiples tipos y la trazabilidad, se introduce el trait ArenaType con un GAT Value<'gc> y un trait unsafe Trace<'gc> con un método trace que visita todos los Gc contenidos. El Gc<'gc, T> se redefine como un NonNull<T> transparente con el Id<'gc> de branding, permitiendo accesos de puntero crudo sin comprobaciones de límites en tiempo de ejecución, ya que la seguridad se garantiza por el sistema de tipos. La implementación de Send y Sync para Gc<'gc, T> se logra al no implementar Deref, lo que lo convierte en un tipo inerte sin un ArenaCtx para desreferenciarlo. Finalmente, se utilizan 'handles' Root<A> basados en Arc<Weak<InnerRoot<A>>> para gestionar las raíces externas del grafo, permitiendo que la Arena::collect identifique y libere automáticamente los objetos inalcanzables mediante un algoritmo de 'mark-and-sweep'.

type Id<'id> = PhantomData<Cell<&'id ()>>;

impl<A: ArenaType> Arena<A> {
    fn enter<F, R>(&mut self, f: F) -> R
    where F: for<'gc> FnOnce(&mut ArenaCtx<'gc, A>) -> R
    {
        f(&mut self.ctx)
    }
}

#[derive(Copy, Clone)]
#[repr(transparent)]
struct Gc<'gc, T> {
    ptr: NonNull<T>,
    _id: Id<'gc>,
}

unsafe impl<'gc, T> Send for Gc<'gc, T> {}
unsafe impl<'gc, T> Sync for Gc<'gc, T> {}

trait ArenaType {
    type Value<'gc>: Trace<'gc>;
}

Fundamentos Teóricos

El problema de la gestión de memoria en presencia de referencias cíclicas es un tema clásico en la ciencia de la computación. El sistema de propiedad de Rust se alinea con los principios de la gestión de memoria basada en el conteo de referencias, donde los objetos son liberados cuando su contador de referencias llega a cero. Sin embargo, los ciclos impiden que esto ocurra, lo que llevó a la invención de algoritmos de recolección de basura por trazado, como el 'mark-and-sweep' propuesto por John McCarthy en 1960. Estos algoritmos operan identificando un conjunto de 'raíces' y marcando todos los objetos alcanzables desde ellas; los objetos no marcados se consideran 'basura' y se recolectan.

La técnica de 'generatividad' de tipos en Rust, fundamental para la seguridad en tiempo de compilación de los Gc punteros, fue formalizada por Gankra en su tesis de maestría, demostrando cómo las propiedades del sistema de tipos de Rust pueden emular tipos dependientes para garantizar la validez de los índices en tiempo de compilación sin comprobaciones en tiempo de ejecución. Este enfoque se inspira en sistemas de seguridad de punteros a nivel de hardware como CHERI (Capability Hardware Enhanced RISC Instructions), que utiliza metadatos en los punteros para garantizar su uso correcto y atrapar errores en tiempo de ejecución. La conexión es que, al igual que CHERI, la generatividad añade 'metadatos' (en forma de lifetimes y IDs de branding) a los punteros lógicos para hacerlos seguros, pero en tiempo de compilación.