I think the following code is safe, but I would appreciate a) a review of it b) suggestions for how to do this without unsafe (or without transmute), and without additional dependencies.
use std::sync::Mutex;
/// Data pool we can borrow from for parsing ELF file sections. Handles that some
/// debug info sections can be compressed.
#[derive(Debug)]
pub struct DataPool {
/// The underlying memory-mapped file, if the ELF section is uncompressed we
/// can borrow directly from this.
file: memmap2::Mmap,
/// Sections of decompressed data
///
/// # Safety invariant
/// This is only appended to, which means the inner data lives as long
/// as DataPool does, and the *inner* contents have stable addresses.
compressed_sections: Mutex<Vec<Box<[u8]>>>,
}
impl DataPool {
pub fn new(file: memmap2::Mmap) -> Self {
Self {
file,
compressed_sections: Mutex::new(Vec::new()),
}
}
/// Add a section of compressed data to the pool, returning a reference
/// to the stored data.
///
/// The returned reference is valid as long as the DataPool lives.
pub fn add_decompressed_section<'this>(&'this self, data: Box<[u8]>) -> &'this [u8] {
let mut guard = self.compressed_sections.lock().expect("Mutex poisoned");
guard.push(data);
let inner: &[u8] = guard.last().expect("We just pushed...");
// SAFETY:
// * By the invariant on `compressed_sections`, the address is stable, so we can
// transmute from a temporary life time to 'this.
// * We return a read only reference to the data (and it has no interior
// mutability), so it is thread safe.
unsafe { transmute_lifetime(inner) }
}
/// Get the underlying memory-mapped file data.
pub fn file_data(&self) -> &[u8] {
&self.file
}
}
/// Helper to guarantee we only transmute lifetime of the outer reference, not
/// the type
///
/// # Safety
/// Same as for `std::mem::transmute`, but the type is fixed.
unsafe fn transmute_lifetime<'input, 'output, T: ?Sized>(input: &'input T) -> &'output T {
unsafe { std::mem::transmute(input) }
}
PS. I'm aware of the safety requirements of mmap: that the underlying file shouldn't change. That is "handled" elsewhere (i.e. it is up to the user to not use the debugging tool on binaries they are changing at the same time). That is not the topic of discussion here.
From my understanding obtaining a &mut Vec<Box<T>> means that you have unique access to all Ts in the boxes because Box has a Unique pointer. But Miri seems to disagree, so now I am unsure.
I would use Vec<*mut [u8]> but then you need even more unsafe.
In general I'd think this isn't safe because the contained value can be replaced, but you don't hand out a mutable reference and [u8] doesn't have internal mutation.
The safe mechanism for this would be Pin, I'd think, but I can't check that right now.
Wouldn't constructing that newtype have the same issue? Or do you not suggest Proxy(&[u8]) as the definition of the proxy? I suppose you could have Proxy(&DataPool, index_for_where_in_the_pool: usize, ... members to handle slicing ...)? Because otherwise this fails when you deref the proxy and try to throw away the proxy and just use the &[u8], which will happen in the object & gimli crates (unless I implement their traits on my proxy type). Their traits require being able to truncate & slice, so I then need to handle that in my proxy type.
But I found this area to be critically performance sensitive:
I used an Rc before going multi-threaded, and could see the that in my profile. (I don't have a direct comparison to no Rc as I changed other things as well between that point and now.)
With Arc once I started using rayon to speed up loading, 40% of the total runtime was spent contending on the reference counters(!). And that was with 4 cores & 8 threads. I cannot imagine what it would have looked like on a higher core count system.
I had a solution where I had an enum MaybeMmap<'data> { File(&'data Mmap), Owned(Arc<[u8]>), }. This too was more expensive than the current data pool, even for files that didn't need the owned variant. Going to the data pool improved runtime by 10% for the non-Arc case.
So I really don't want a type larger than a thick pointer, and I don't want any extra indirection or branches. (Really, if the accesses of the proxy doesn't compile to equivalent assembly as using slices, I think the idea is dead in the water. I should have stated that in my original post, sorry about that.)
the proxy type can borrow self, not self.compressed_sections (behind the temporary MutexGuard), and the actual borrow (Mutex::lock(), or better, replace Mutex with RwLock) is deferred to Deref::deref() at runtime.
the downside of this, is that it can panic if the data is concurrently accessed, so if that's the expected use case, it will not work.
I indeed don't hand out mutable references and this type is in a separate module, meaning other code can't reach into the internals and bypass the interface[1].
Box<[u8]> is Unpin. You would need a wrapper type to prevent that.
Pinning and a wrapper type would possibly make it easier to not mess up the (relatively simple) internals though.
Well: I'm writing a debugger. Of course it is possible to reach around abstractions. But ptrace, /proc/self/mem, etc doesn't really count. If it did, writing any safe rust code would be impossible. ↩︎
Locking a mutex in the hot path (when reading the data) would not really work. gimli internally clones the slice/proxy type a lot. Especially when parsing the .debug_info section as it is a tree structure and you need to clone it as you descend and start iterating the child nodes. On a large debug info file (such as for Firefox libxul.so[1]) I saw millions of clones.
And RwLock doesn't really help:
It would block adding new sections if the are concurrent readers. I load sections concurrently with parsing loaded ones.
Adding/removing readers would still contend on the cache line containing the reader count. This is why RwLock in general is an awful data structure, worse than a normal Mutex (since it is more complex and need more instructions to process) and still with the same bad contention. The only niche use case is for locks being held for a long time, which is not the case here.
Possibly you could do something with RCU or hazard pointers, but now it is getting much more complicated again. And likely less efficient than my current approach, where the mutex only needs to be taken once per section loaded.
The debug info for libxul.so is 1.8 GB. Yes, really. And before you say that I'm optimising for a non-use case. No I'm specifically working on a debugger solution that scales better to massive debug info and huge projects, such as browsers. That is my core use case. ↩︎
Also, it seems boxes of slices are missing both .leak() and .into_raw(), so I have no clue how to convert a box of a slice into a raw pointer...
Edit: I get a Cow<'_, [u8]> from the decompression API in the object crate. I know for a fact I have the owned variant of it in the cases I care about (so into_owned() is essentially free). This gives me a Vec<u8>.
I see no non-nightly way to get to a raw pointer that handles ownership for that without copying. That can't be right, surely? I must be missing something.
However, I don't believe Vec has the uniqueness property, so decompressed_sections: Mutex<Vec<Vec<u8>>> should be fine. It is less cache line efficient, but I don't expect that to matter, it is not called often.
that's not true, exclusive access to Vec doesn't transitively claim exclusivity to its contents. quoting a paragraph from Vec::as_mut_ptr():
This method guarantees that for the purpose of the aliasing model, this method does not materialize a reference to the underlying slice, and thus the returned pointer will remain valid when mixed with other calls to as_ptr, as_mut_ptr, and as_non_null. Note that calling other methods that materialize references to the slice, or references to specific elements you are planning on accessing through this pointer, may still invalidate this pointer.
they do exists for all Box<T>, but they are not callable as method, you must call them using function call syntax, e.g. Box::leak(b) and Box::into_raw(b).
A certainly non-unique thing would be spelled a Mutex<Vec<Arc<[u8]>>>; you would still need that lifetime transmutation on data_arc.clone().deref() to get &[u8] of proper lifetime and working fast enough, though.
As a micro-optimization, have you considered using non-poisoning mutex? (Not sure about crate name but it existed somewhere; you could also ignore poison.)
You may be thinking of parking_lot. Currently the mutex is not highly contended since adding data isn't the common operation (called maybe 10-20 times per ELF binary/library). The heavy part is using, cloning, subslicing etc of the slices returned. This may change as I add support for dwo (one of the 4 ways in which debug info can be split, corresponding to the unpacked option in Rust).
It will be worth looking at the mutex at that point.