TagArena strawman proposal

tagarena.rs

// tagarena strawman
// pcwalton, 9/5/2019

// Allocate memory freely within a TagArena and get back Tags, which you can
// use to fetch the object later.
struct TagArena {
    // Globally unique ID for this arena, to prevent looking up a tag in the
    // wrong arena.
    id: u32,
    ...
}

// Tags are typed with the data they point to.
// Note that tags are Copy!
#[derive(Clone, Copy)]
struct Tag<T> {
    // Pointer to object in the associated tag arena.
    ptr: *const T,
    // Tag for the object.
    tag: u32,
    // ID of the matching arena.
    arena_id: u32,
}

// Monotonically increasing arena IDs.
static NEXT_ARENA_ID: AtomicUsize = ...;

impl TagArena {
    // Create a new tag arena with a globally unique ID.
    pub fn new() -> TagArena {
        let arena_id = NEXT_ARENA_ID.fetch_add(1);
        ... check overflow on arena ID ...
        TagArena { arena_id, ... }
    }

    // Allocate an object.
    pub fn alloc<T>(&mut self, value: T) -> Tag<T> {
        ...allocate some memory in this arena...
        ...copy value in...

        // If it's a new allocation, tag is 0. Otherwise, use tag in free block.
        Tag { ptr, tag, arena_id: self.id }
    }

    // Verify that a tag is valid.
    fn verify_tag(&self, tag: Tag<T>) {
        unsafe {
            // Check arena ID.
            assert_eq!(tag.arena_id, self.id);
            // Check tag ID.
            assert_eq!(*ptr::offset(tag.ptr, -4), self.tag);
        }
    }

    // Free an object, given its pointer.
    // Further attempts to access an object will fail because of tag mismatch.
    pub fn free<T>(&mut self, tag: Tag<T>) {
        unsafe {
            self.verify_tag(tag);
            // Change tag in freed region.
            *ptr::offset(tag.ptr, -4) += 1;
            ... panic on overflow ...
            ... mark object as free ...
        }
    }

    // Fetch a previously-allocated object for reading.
    // Maybe this could be a Deref impl
    pub fn get<T>(&self, tag: Tag<T>) -> &T {
        unsafe {
            self.verify_tag(tag)
            // Fetch value.
            mem::transmute::<*const T, &T>(tag.ptr)
        }
    }

    // Fetch a previously-allocated object for writing.
    // Note that this borrows the whole arena mutably.
    // Maybe this could be a DerefMut impl
    pub fn get_mut<T>(&mut self, tag: Tag<T>) -> &mut T {
        // Ditto as above.
    }
}

------

// Let's write a linked list!

pub struct IntList {
    first: Option<Tag<IntList>>,
    last: Option<Tag<IntList>>,
}

struct IntListItem {
    value: i32,
    next: Option<Tag<IntList>>,
    prev: Option<Tag<IntList>>,
}

impl IntList {
    pub fn new() -> IntList {
        IntList { first: None, last: None }
    }

    pub fn push_back(&mut self, arena: &mut TagArena, value: i32) {
        let mut new_item = arena.alloc(IntListItem { value, next: None, prev: None });
        match self.last {
            None => {
                // Multiple pointers to the same item are no problem!
                self.first = Some(new_item);
                self.last = Some(new_item);
            }
            Some(ref mut last) => {
                // Deref/DerefMut impls on arenas might be nice!
                arena.get_mut(new_item).prev = *last;
                arena.get_mut(*last).next = new_item;
                *last = new_item;
            }
        }
    }

    ... more methods here ...

    pub fn destroy(&mut self, arena: &mut TagArena) {
        // Have to free manually. Quite a nuisance!
        // One could imagine a way for an int list to keep a reference to its
        // arena so this isn't necessary.
        ... destroy all objects ...
    }
}