Welcome back to the "Making our own executable packer" series, where digressions are our bread and butter.

Last time, we implemented indirect functions in a no-libc C program. Of course, we got lost on the way and accidentally implemented a couple of useful elk-powered GDB functions - with only the minimal required amount of Python code.

The article got pretty long, and we could use a nice distraction. And I have just the thing! A little while ago, a member of the Rust compiler team stumbled upon this series and gave me some feedback.

The first piece of feedback is easily addressed - there were a few "useless use of transmute", like here for example:

Rust code
// in `delf/src/lib.rs` impl Addr { pub unsafe fn as_ptr<T>(&self) -> *const T { std::mem::transmute(self.0 as usize) } pub unsafe fn as_mut_ptr<T>(&self) -> *mut T { std::mem::transmute(self.0 as usize) } }

While playing around with loading executables, I had gotten used to stuff being wildly unsafe, but it turns out - this is perfectly safe! Raw pointers are basically typed usize, so this is perfectly fine:

Rust code
// in `delf/src/lib.rs` impl Addr { pub fn as_ptr<T>(&self) -> *const T { self.0 as *const T } pub fn as_mut_ptr<T>(&self) -> *mut T { self.0 as *mut T } }

Deferencing those pointers is the unsafe thing to do, so this won't compile:

Rust code
// hypothetical code, not committed impl Addr { pub fn example(&self) { let x = *self.as_ptr::<u64>(); } }
Shell session
$ cargo b error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block --> /home/amos/ftl/delf/src/lib.rs:371:17 | 371 | let x = *self.as_ptr::<u64>(); | ^^^^^^^^^^^^^^^^^^^^^ dereference of raw pointer | = note: raw pointers may be NULL, dangling or unaligned; they can violate aliasing rules and cause data races: all of these are undefined behavior

We also don't need transmute when computing the base address of an ELF object:

Rust code
// in `elk/src/process.rs` // in `impl Process`, `fn load_object` let base = delf::Addr(unsafe { let u: usize = transmute(mem_map.data()); u as u64 }) - mem_range.start;

This can be rewritten with a simple cast:

Rust code
// in `elk/src/process.rs` // in `impl Process`, `fn load_object` let base = delf::Addr(mem_map.data() as u64) - mem_range.start;

A little lower, in our options to MemoryMap::new, we can also remove that unsafe block:

Rust code
// in `elk/src/process.rs` let map = MemoryMap::new( filesz.into(), &[ MapOption::MapReadable, MapOption::MapWritable, MapOption::MapExecutable, MapOption::MapFd(fs_file.as_raw_fd()), MapOption::MapOffset(offset.into()), // before: MapOption::MapAddr(unsafe { (base + vaddr).as_ptr() }), // after: MapOption::MapAddr((base + vaddr).as_ptr()), ], )?;

Ah. I feel lighter already. Not that unsafe has any performance penalty - it just weighs heavy on my shoulders.

So where do we need transmute?

We still need it when processing indirect functions:

Rust code
// in `elk/src/process.rs` // in `match reltype` RT::IRelative => unsafe { let selector: extern "C" fn() -> delf::Addr = transmute(obj.base + addend); objrel.addr().set(selector()); },

As a tiny nitpick, we should probably mark selector as unsafe - it is definitely not safe to call:

Rust code
// in `elk/src/process.rs` // in `match reltype` RT::IRelative => unsafe { // spread across two lines for readability type Selector = unsafe extern "C" fn() -> delf::Addr; let selector: Selector = transmute(obj.base + addend); objrel.addr().set(selector()); },

We also still need transmute when jumping to the entry point - and we can improve the function signature here too.

Rust code
// in `elk/src/main.rs` unsafe fn jmp(addr: *const u8) { let fn_ptr: fn() = std::mem::transmute(addr); fn_ptr(); }

Let's make a quick list. fn_ptr:

I had no idea you could annotate Rust functions with "never returns" but it's actually super easy:

Rust code
// in `elk/src/main.rs` unsafe fn jmp(addr: *const u8) { // spread across two lines for readability type EntryPoint = unsafe extern "C" fn() -> !; let entry_point: EntryPoint = transmute(addr); entry_point(); }

Now! Onto the meat of the article. One of the naughtiest things we did back in Dynamic linker speed and correctness is introduce the Name enum:

Rust code
// in `elk/src/name.rs` #[derive(Clone)] pub enum Name { FromAddr { addr: delf::Addr, len: usize }, Owned(Vec<u8>), }

So far it has been... wildly unsafe.

The constructor for the FromAddr variant was unsafe:

Rust code
pub unsafe fn from_addr(addr: delf::Addr) -> Self { let len = addr .as_slice::<u8>(2048) .iter() .position(|&c| c == 0) .expect("scanned 2048 bytes without finding null-terminator for name"); Self::FromAddr { addr, len } }

It's not that it's looking for a null terminator - that's just how ELF files (and C in general) work! The problem is that we're reading memory at an arbitrary address.

If we did the maths right, the delf::Addr in question points to a valid memory-mapped region, and if our ELF file is valid, and a bunch of other ifs, then we read a symbol name, and everything is fine.

But... if somehow a Name outlives the MemoryMap, then the region is unmapped, and we end up with a SIGBUS or SIGSEGV instead - if we're lucky. If we're not lucky, we end up reading arbitrary data, and that would be very hard to debug.

So the problem here is that Name is easy to mis-use and it can result in unsafe memory access. And it's not just a theoretical problem too. I ran into it the minute I introduced Name into the codebase.

See, originally, I had RelocationError like this:

Rust code
// in `elk/src/process.rs` (originally) #[derive(Error, Debug)] pub enum RelocationError { // omitted: other cariants #[error("undefined symbol: {0}")] UndefinedSymbol(NamedSym), }

(Note that NamedSym contains Name)

And it was used like so:

Rust code
// in `elk/src/process.rs` (originally) // in `fn apply_relocations` let found = match rel.sym { 0 => ResolvedSym::Undefined, _ => match self.lookup_symbol(&wanted, ignore_self) { undef @ ResolvedSym::Undefined => match wanted.sym.sym.bind { delf::SymBind::Weak => undef, // here: _ => return Err(RelocationError::UndefinedSymbol(wanted.sym.clone())), }, x => x, }, };

Seems all good, right? Our error type has rich information (a NamedSym), which is cloned so we can return it without worrying about ownership. It should work fine?

Except apply_relocations is called from cmd_run, like so:

Rust code
// in `elk/src/main.rs` fn cmd_run(args: RunArgs) -> Result<(), Box<dyn Error>> { let mut proc = process::Process::new(); let exec_index = proc.load_object_and_dependencies(args.exec_path)?; // right here proc.apply_relocations()?; proc.adjust_protections()?; let exec_obj = &proc.objects[exec_index]; let entry_point = exec_obj.file.entry_point + exec_obj.base; unsafe { jmp(entry_point.as_ptr()) }; Ok(()) }

So, within cmd_run, everything is fine - Process is in scope, it owns Object, which owns NamedSym and Segment, which in turns owns the MemoryMap:

But if we return an error... then the Process, and everything it owns, is thrown away. And the memory-mapped region is unmapped.

The Name, however, is cloned and returned as part of the error, but it now "points" to - at best - unmapped memory:

And that's... really something that shouldn't happen in a Rust program.

...but it's not as simple as using lifetimes either, is it.

See, you can't really have a struct where one member borrows from the other:

Rust code
// in `sample.rs`, just to try things out struct Container<'a> { vec: Vec<u8>, slice_of_vec: &'a [u8], }

Constructing Container like this doesn't work:

Rust code
fn test() { let vec = vec![1, 2, 3, 4, 5]; let a = Container { vec, slice_of_vec: &vec[2..3], }; }
Shell session
$ cargo b error[E0382]: borrow of moved value: `vec` --> src/sample.rs:10:24 | 7 | let vec = vec![1, 2, 3, 4, 5]; | --- move occurs because `vec` has type `std::vec::Vec<u8>`, which does not implement the `Copy` trait 8 | let a = Container { 9 | vec, | --- value moved here 10 | slice_of_vec: &vec[2..3], | ^^^ value borrowed here after move

This doesn't work either:

Rust code
fn test() { let vec = vec![1, 2, 3, 4, 5]; let a = Container { slice_of_vec: &vec[2..3], vec, }; }
Shell session
error[E0505]: cannot move out of `vec` because it is borrowed --> src/sample.rs:10:9 | 9 | slice_of_vec: &vec[2..3], | --- borrow of `vec` occurs here 10 | vec, | ^^^ move out of `vec` occurs here

We can "work around the problem" by first transferring ownership of the Vec to Container, and then setting slice_of_vec:

Rust code
struct Container<'a> { vec: Vec<u8>, slice_of_vec: Option<&'a [u8]>, } fn test() { let vec = vec![1, 2, 3, 4, 5]; let mut a = Container { vec, slice_of_vec: None, }; a.slice_of_vec = Some(&a.vec[2..3]); }

But this isn't the way. Not only can we now have Container with None slice_of_vec, we also can never return a Container with a Some slice_of_vec:

Rust code
struct Container<'a> { vec: Vec<u8>, slice_of_vec: Option<&'a [u8]>, } fn test() { let make_container = || { let vec = vec![1, 2, 3, 4, 5]; let mut res = Container { vec, slice_of_vec: None, }; res.slice_of_vec = Some(&res.vec[2..3]); res }; let a = make_container(); }
Shell session
$ cargo b error[E0515]: cannot return value referencing local data `res.vec` --> src/sample.rs:14:9 | 13 | res.slice_of_vec = Some(&res.vec[2..3]); | ------- `res.vec` is borrowed here 14 | res | ^^^ returns a value referencing data owned by the current function error[E0505]: cannot move out of `res` because it is borrowed --> src/sample.rs:14:9 | 7 | let make_container = || { | - return type of closure is sample::Container<'1> ... 13 | res.slice_of_vec = Some(&res.vec[2..3]); | ------- borrow of `res.vec` occurs here 14 | res | ^^^ | | | move out of `res` occurs here | returning this value requires that `res.vec` is borrowed for `'1`

...because res.slice_of_vec borrows res.slice_of_vec, and res is a local, and returning it would move it. And this is where "moving" a value take on its full meaning. We're not just "transferring ownership", we're actually changing its address. And Rust doesn't have any run-time magic to make sure the address res.slice_of_vec is pointing to also changes. So the checker steps in and disallows that.

What we can do is have Container own the Vec, and have a Range that refers to a range of the Vec, like so:

Rust code
// in `sample.rs`, still messing around use std::ops::Range; struct Container { vec: Vec<u8>, range_of_vec: Range<usize>, } impl Container { fn slice_of_vec(&self) -> &[u8] { // Range is *not* Copy for a good reason: // https://github.com/rust-lang/rust/pull/27186 &self.vec[self.range_of_vec.clone()] } } fn test() { let make_container = || Container { vec: vec![1, 2, 3, 4, 5], range_of_vec: 2..4, }; let a = make_container(); println!(" vec = {:?}", a.vec); println!("slice = {:?}", a.slice_of_vec()); }
Shell session
$ cargo run --quiet vec = [1, 2, 3, 4, 5] slice = [3, 4]

And that's kind of the situation we have with Object (~ Container) and Name (~ &[u8]).

Object would own a Vec of NamedSym, which own Name values, which borrow... something Object owns (that comes from the addr::MemoryMap).

Reduced, the problem looks like this:

Rust code
use std::ops::Range; struct Object<'a> { map: Vec<u8>, names: Vec<Name<'a>>, } struct Name<'a> { slice: &'a [u8], } fn test() { let load_object = || { let mut obj = Object { map: "foobarbaz".bytes().collect(), names: vec![], }; obj.names.push(Name { slice: &obj.map[0..3], }); obj }; let obj = load_object(); }

This code looks familiar - and doesn't compile:

Shell session
error[E0515]: cannot return value referencing local data `obj.map` --> src/sample.rs:21:9 | 19 | slice: &obj.map[0..3], | ------- `obj.map` is borrowed here 20 | }); 21 | obj | ^^^ returns a value referencing data owned by the current function error[E0505]: cannot move out of `obj` because it is borrowed --> src/sample.rs:21:9 | 13 | let load_object = || { | - return type of closure is sample::Object<'1> ... 19 | slice: &obj.map[0..3], | ------- borrow of `obj.map` occurs here 20 | }); 21 | obj | ^^^ | | | move out of `obj` occurs here | returning this value requires that `obj.map` is borrowed for `'1`

Again, we can store a Range instead:

Rust code
use std::ops::Range; struct Object { map: Vec<u8>, names: Vec<Name>, } struct Name { range: Range<usize>, } pub fn test() { let load_object = || { let mut obj = Object { map: "foobarbaz".bytes().collect(), names: vec![], }; obj.names.push(Name { range: 0..3 }); obj }; let obj = load_object(); }

...but then we have to keep track of which Object a Name belongs to.

To illustrate this, how would we implement Name::slice?

Rust code
impl Name { fn slice(&self) -> &[u8] { // what is `self.range` indexing into?? unimplemented!() } }

We'd either need to have Name::slice take a reference to Object, which is not ideal:

Rust code
impl Name { fn slice<'a>(&self, obj: &'a Object) -> &'a [u8] { &obj.map[self.range.clone()] } } pub fn test() { let load_object = || { let mut obj = Object { map: "foobarbaz".bytes().collect(), names: vec![], }; obj.names.push(Name { range: 0..3 }); obj.names.push(Name { range: 3..6 }); obj.names.push(Name { range: 6..9 }); obj }; let obj = load_object(); use std::str::from_utf8; for name in &obj.names { println!("name = {:?}", from_utf8(name.slice(&obj))); } }
Shell session
$ cargo run --quiet name = Ok("foo") name = Ok("bar") name = Ok("baz")

Why is this not ideal? Because nothing stops you from passing to slice a different Object than the one Name was originally associated with.

Rust code
pub fn test() { let load_object = || { let mut obj = Object { map: "foobarbaz".bytes().collect(), names: vec![], }; obj.names.push(Name { range: 0..3 }); obj.names.push(Name { range: 3..6 }); obj.names.push(Name { range: 6..9 }); obj }; let obj1 = load_object(); let obj2 = Object { map: vec![], names: vec![], }; use std::str::from_utf8; for name in &obj1.names { println!("name = {:?}", from_utf8(name.slice(&obj2 /* woops */))); } }
Shell session
$ cargo run thread 'main' panicked at 'index 3 out of range for slice of length 0', src/libcore/slice/mod.rs:2674:5 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

Alternatively, we could have name_slice method on Object, but we'd have exactly the same potential misuse:

Rust code
impl Object { fn name_slice(&self, name: &Name) -> &[u8] { &self.map[name.range.clone()] } } pub fn test() { let load_object = || { // omitted: same as before }; let obj1 = load_object(); let obj2 = Object { map: vec![], names: vec![], }; use std::str::from_utf8; for name in &obj1.names { // woops println!("name = {:?}", from_utf8(obj2.name_slice(&name))); } }

...so it's not ideal either.

One way to solve it is with reference counting. Rust has reference-counting smart pointer types like Rc and Arc.

Rust code
use std::ops::Range; use std::rc::Rc; struct Object { map: Rc<Vec<u8>>, names: Vec<Name>, } struct Name { map: Rc<Vec<u8>>, range: Range<usize>, } impl Name { fn for_object(obj: &Object, range: Range<usize>) -> Self { Self { map: obj.map.clone(), range, } } fn slice(&self) -> &[u8] { &self.map[self.range.clone()] } } pub fn test() { let load_object = || { let mut obj = Object { map: Rc::new("foobarbaz".bytes().collect()), names: vec![], }; obj.names.push(Name::for_object(&obj, 0..3)); obj.names.push(Name::for_object(&obj, 3..6)); obj.names.push(Name::for_object(&obj, 6..9)); obj }; let obj = load_object(); use std::str::from_utf8; for name in &obj.names { println!("name = {:?}", from_utf8(name.slice())); } }

With this scheme, the Vec<u8> stays alive as long as there's at least one reference to it. By the end of our closure, we have:

When returning from load_object, Object and the three Name values are moved, but not dropped! So they don't decrease the reference count of the Rc<Vec<u8>>

We can even separate Name from the original Object, like so:

Rust code
pub fn test() { let get_some_names = || { let load_object = || { let mut obj = Object { map: Rc::new("foobarbaz".bytes().collect()), names: vec![], }; obj.names.push(Name::for_object(&obj, 0..3)); obj.names.push(Name::for_object(&obj, 3..6)); obj.names.push(Name::for_object(&obj, 6..9)); obj }; let obj = load_object(); obj.names .into_iter() .filter(|n| n.slice().iter().next().map(|&b| b == b'b').unwrap_or(false)) }; let names = get_some_names(); use std::str::from_utf8; for name in names { println!("name = {:?}", from_utf8(name.slice())); } }

After get_some_names returns, our Rc<Vec<u8>> has lost two references, but still has two:

So everything still works fine:

Shell session
$ cargo run --quiet name = Ok("bar") name = Ok("baz")

This seems great on paper! One caveat: Rc isn't thread-safe, so this doesn't work:

Rust code
pub fn test() { let get_some_names = || { let load_object = || { // same as before }; let obj = load_object(); std::thread::spawn(|| { obj.names .into_iter() .filter(|n| n.slice().iter().next().map(|&b| b == b'b').unwrap_or(false)) }) .join() .unwrap() }; let names = get_some_names(); use std::str::from_utf8; for name in names { println!("name = {:?}", from_utf8(name.slice())); } }
Shell session
error[E0277]: `std::rc::Rc<std::vec::Vec<u8>>` cannot be sent between threads safely --> src/sample.rs:41:9 | 41 | std::thread::spawn(|| { | ^^^^^^^^^^^^^^^^^^ `std::rc::Rc<std::vec::Vec<u8>>` cannot be sent between threads safely | = help: within `sample::Name`, the trait `std::marker::Send` is not implemented for `std::rc::Rc<std::vec::Vec<u8>>` = note: required because it appears within the type `sample::Name` = note: required because of the requirements on the impl of `std::marker::Send` for `std::vec::IntoIter<sample::Name>` = note: required because it appears within the type `std::iter::Filter<std::vec::IntoIter<sample::Name>, [closure@src/sample.rs:44:25: 44:89]>`

Luckily, std::sync::Arc is a drop-in, thread-safe replacement for std::rc::Rc:

Rust code
use std::ops::Range; // was Rc use std::sync::Arc; struct Object { // was Rc map: Arc<Vec<u8>>, names: Vec<Name>, } struct Name { // was Rc map: Arc<Vec<u8>>, range: Range<usize>, } impl Name { // same as before } pub fn test() { let get_some_names = || { let load_object = || { // same as before }; let obj = load_object(); // same std::thread::spawn(|| { obj.names .into_iter() .filter(|n| n.slice().iter().next().map(|&b| b == b'b').unwrap_or(false)) }) .join() .unwrap() }; // same let names = get_some_names(); use std::str::from_utf8; for name in names { println!("name = {:?}", from_utf8(name.slice())); } }

And now our (unnecessary) use of thread::spawn works:

Shell session
$ cargo run --quiet name = Ok("bar") name = Ok("baz")

This works nicely because we have Name and Object both refer to a third thing: a Vec<u8>.

But what if we wanted to keep track of which Object a Name belongs to?

We could have Name refer to Object instead Vec<u8>.

Cool bear's hot tip

We're pushing it a little, so the code sample gets a bit long, but try to power through it.

The tricky bit here is mostly that we need to construct Object first, then construct some Name values that refer to Object (through Arc<Mutex<T>>), and add them to the Object.

Hold my coffee:

Rust code
use std::{ fmt, ops::Range, path::PathBuf, sync::{Arc, Mutex}, }; struct Object { // objects now have a path path: PathBuf, // this is back to a regular Vec<u8> map: Vec<u8>, names: Vec<Name>, } // derive clone for later #[derive(Clone)] struct Name { // names now refer directly to an object object: Arc<Mutex<Object>>, range: Range<usize>, } impl Name { // now taking an `object` directly fn for_object(object: &Arc<Mutex<Object>>, range: Range<usize>) -> Self { Self { object: object.clone(), range, } } fn slice(&self) -> &[u8] { &self.object.lock().unwrap().map[self.range.clone()] } } // for printing below impl fmt::Debug for Name { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { use std::str::from_utf8; let obj = self.object.lock().unwrap(); write!( f, "{:?}/{}", obj.path, from_utf8(self.slice()).unwrap_or("<not a string>") ) } } pub fn test() { let get_some_names = || { let load_object = || { // we need to first build the object, move into into an `Arc<Mutex<>>` let obj = Arc::new(Mutex::new(Object { path: PathBuf::from("libtest.so"), map: "foobarbaz".bytes().collect(), names: vec![], })); let mut names = vec![ Name::for_object(&obj, 0..3), Name::for_object(&obj, 3..6), Name::for_object(&obj, 6..9), ]; { // and *then* acquire the mutex so we can add the names to the object let mut obj = obj.lock().unwrap(); for name in names.drain(..) { obj.names.push(name); } } obj }; let obj = load_object(); { // again here, we need to acquire the mutex to read the names from the mutex let obj = obj.lock().unwrap(); obj.names .iter() .cloned() // that's why we derived Clone .filter(|n| n.slice().iter().next().map(|&b| b == b'b').unwrap_or(false)) .collect::<Vec<_>>() } }; let names = get_some_names(); use std::str::from_utf8; for name in names { println!("name = {:?}", name); } }

Unfortunately... this doesn't compile:

Shell session
error[E0515]: cannot return value referencing temporary value --> src/sample.rs:29:9 | 29 | &self.object.lock().unwrap().map[self.range.clone()] | ^---------------------------^^^^^^^^^^^^^^^^^^^^^^^^ | || | |temporary value created here | returns a value referencing data owned by the current function

This is the offending function:

Rust code
impl Name { fn slice(&self) -> &[u8] { &self.object.lock().unwrap().map[self.range.clone()] } }

And, yeah, this is illegal. We acquire the lock within slice, but we release it when we return. So we can't return data borrowed from what's guarded by the mutex.

What we can do though is.. flip it around.

And this is a pretty cool pattern I discovered while writing the actual (elk) code for this article. Instead of returning a &[u8], we can just take a closure that takes a &[u8]. This way, we can ensure they only use it while we hold the lock.

Rust code
impl Name { fn with_slice<F, T>(&self, mut f: F) -> T where F: FnMut(&[u8]) -> T, { f(&self.object.lock().unwrap().map[self.range.clone()]) } }

The Debug implementation becomes:

Rust code
impl fmt::Debug for Name { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { use std::str::from_utf8; write!(f, "{:?}/", self.object.lock().unwrap().path)?; self.with_slice(|s| write!(f, "{:?}", from_utf8(s).unwrap_or("<not a string>"))) } }

Note that we can do everything within the closure - with_slice holds the lock, we'd just deadlock. If we used an RwLock instead, it would work.

The name filtering part of test becomes:

Rust code
pub fn test() { let get_some_names = || { let load_object = || { /* cut */ }; let obj = load_object(); { let obj = obj.lock().unwrap(); obj.names .iter() .cloned() // changed code's here: .filter(|n| n.with_slice(|s| s.iter().next().map(|&b| b == b'b').unwrap_or(false))) .collect::<Vec<_>>() } }; }

Overall, minimal code changes.

Unfortunately, this.. deadlocks.

Rust code
$ cargo run (remains stuck forever)

Because we're trying to acquire the lock in test:

Rust code
// first lock let obj = obj.lock().unwrap(); obj.names .iter() .cloned() // second lock (inside `with_slice`) .filter(|n| n.with_slice(|s| s.iter().next().map(|&b| b == b'b').unwrap_or(false))) .collect::<Vec<_>>()

Ah, the joys of using (relatively) low-level locking primitives.

We can fix that like so:

Rust code
let obj = load_object(); let names = { // first lock let obj = obj.lock().unwrap(); obj.names.iter().cloned().collect::<Vec<_>>() // release first lock }; names .into_iter() // second lock .filter(|n| n.with_slice(|s| s.iter().next().map(|&b| b == b'b').unwrap_or(false))) .collect::<Vec<_>>()

Again, an RwLock wouldn't have had these issues - as you can hold several RwLockReadGuards for the same lock.

We also could've used try_lock().unwrap() instead, which would've panicked if we couldn't acquire the lock immediately.

With that last change, the code finally runs:

Rust code
$ cargo run --quiet name = "libtest.so"/"bar" name = "libtest.so"/"baz"

But now we have... another problem. Object owns Name and Name holds a counting reference to Object, so we have cycles:

...which means neither are ever going to be freed.

There is, of course, a way to sidestep that. We can have Name hold a weak reference to Object instead.

Rust code
use std::{ fmt, ops::Range, path::PathBuf, // new: Weak sync::{Arc, Mutex, Weak}, }; #[derive(Clone)] struct Name { // was: `Arc`, now `Weak` object: Weak<Mutex<Object>>, range: Range<usize>, } impl Name { fn for_object(object: &Arc<Mutex<Object>>, range: Range<usize>) -> Self { Self { // was: object.clone() object: Arc::downgrade(object), range, } } fn with_slice<F, T>(&self, mut f: F) -> T where F: FnMut(&[u8]) -> T, { // I probably wouldn't write code like this in production, // but with IDE assistance it's not that bad. // // Let's follow the type chain: // Weak<Mutex<Object>> (upgrade - can return None if Arc was freed) // -> Option<Arc<Mutex<Object>>> (unwrap - can panic) // -> Arc<Mutex<Object>> (lock - can fail if we double-lock) // -> Result<MutexGuard<Object>> (unwrap - can panic) // -> MutexGuard<Object> f(&self.object.upgrade().unwrap().lock().unwrap().map[self.range.clone()]) } } // the Debug implementation is changed similarly, using `.unwrap()`.

And with these changes... our code crashes:

Rust code
$ cargo run --quiet thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', /rustc/5e1a799842ba6ed4a57e91f7ab9435947482f7d8/src/libcore/macros/mod.rs:15:40 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

Now, when we clone the Name and drop the Arc<Mutex<Object>>, all strong references to the Object are dropped, and the Object itself is dropped, too. So when we call upgrade(), it returns None, and when we call unwrap() on that, it panics.

If we don't want it to panic, we need to keep a strong reference to the object around.

Rust code
pub fn test() { let get_some_names = || { let load_object = || { // cut }; let obj = load_object(); let names = { let obj = obj.lock().unwrap(); obj.names.iter().cloned().collect::<Vec<_>>() }; let names = names .into_iter() .filter(|n| n.with_slice(|s| s.iter().next().map(|&b| b == b'b').unwrap_or(false))) .collect::<Vec<_>>(); // new: return both `Arc<Mutex<Object>>` and `Vec<Name>` (obj, names) }; let (_obj, names) = get_some_names(); use std::str::from_utf8; for name in names { println!("name = {:?}", name); } }

And now it runs again.

Shell session
$ cargo run --quiet name = "libtest.so"/"bar" name = "libtest.so"/"baz"

But, as you can see... it goes places. We don't need that complexity in elk.

For our use case, a much better alternative would be to split Object into two structs.

Rust code
use std::{fmt, ops::Range, path::PathBuf, sync::Arc}; struct Object { // some of the data was split into a new struct data: Arc<ObjectData>, names: Vec<Name>, } // and here's that new struct. It owns the path // and the memory contents. struct ObjectData { path: PathBuf, map: Vec<u8>, } #[derive(Clone)] struct Name { // this doesn't refer to `Object` aymore obj_data: Arc<ObjectData>, range: Range<usize>, } impl Name { fn for_object(object: &Object, range: Range<usize>) -> Self { Self { // note that the lifetime of `Name` isn't tied to the lifetime of // `Object` in any way obj_data: object.data.clone(), range, } } fn with_slice<F, T>(&self, mut f: F) -> T where F: FnMut(&[u8]) -> T, { // much simpler! f(&self.obj_data.map[self.range.clone()]) } } impl fmt::Debug for Name { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { use std::str::from_utf8; write!(f, "{:?}/", self.obj_data.path)?; self.with_slice(|s| write!(f, "{:?}", from_utf8(s).unwrap_or("<not a string>"))) } } pub fn test() { let get_some_names = || { let load_object = || { // build the `Object` and `ObjectData` in one fell swoop let mut obj = Object { data: Arc::new(ObjectData { path: PathBuf::from("libtest.so"), map: "foobarbaz".bytes().collect(), }), names: vec![], }; // our `Object` is mutable and we fully own it, // no need to acquire a lock to mutate it let mut names = vec![ Name::for_object(&obj, 0..3), Name::for_object(&obj, 3..6), Name::for_object(&obj, 6..9), ]; for name in names.drain(..) { obj.names.push(name); } obj }; // look mom, no locks! let obj = load_object(); obj.names .into_iter() .filter(|n| n.with_slice(|s| s.iter().next().map(|&b| b == b'b').unwrap_or(false))) .collect::<Vec<_>>() }; // no need to hold a reference to `Object`, because our `Name` values hold // references to `ObjectData` - and that's all they need. let names = get_some_names(); use std::str::from_utf8; for name in &names { println!("name = {:?}", name); } }

This version works just as well:

Shell session
$ cargo run --quiet name = "libtest.so"/"bar" name = "libtest.so"/"baz"
What did we learn?

Gather round team, what did we learn?

Many of the lifetime (and Rc/Arc) issues encountered when writing Rust are due to the developer being stubborn and absolutely wanting to fit everything in a single struct.

But oftentimes it's advantageous to split things across multiple structs! Separate data from metadata, immutable values from mutable values, etc.

So! Now that we know enough about this, how do we apply it to Name?

Well, we'll have Name hold a reference to MemoryMap. We don't really care where a Name comes from right now. If we did, we'd have to reorganize things a little (because Object owns several Segments, and they own the MemoryMaps).

The next question is: should Name hold a strong reference to MemoryMap, or a weak one? If we want to use it in one of our error types, it has to be a strong one.

Next question: Rc or Arc? It doesn't really matter. We're not especially concerned with squeezing every bit of performance out of our code, so we can go with Arc in case we do some parallel things later.

Let's get going! The definition of Name was:

Rust code
// in `elk/src/name.rs` (old) #[derive(Clone)] pub enum Name { FromAddr { addr: delf::Addr, len: usize }, Owned(Vec<u8>), }

And, from now on, we'll be working with this:

Rust code
// in `elk/src/name.rs` (new) use mmap::MemoryMap; use std::{ops::Range, sync::Arc}; #[derive(Clone)] pub enum Name { Mapped { map: Arc<MemoryMap>, range: Range<usize>, }, Owned(Vec<u8>), }

For convenience, we'll add a method to MemoryMap - turns out the mmap crate is rather low-level and only gives us pointers, but we'd rather work with slices.

Rust code
// in `elk/src/name.rs` trait MemoryMapExt { fn as_slice(&self) -> &[u8]; } impl MemoryMapExt for MemoryMap { fn as_slice(&self) -> &[u8] { // we're hiding unsafe code in a safe function, so we // better make sure it's correct! // looks correct to me. unsafe { std::slice::from_raw_parts(self.data(), self.len()) } } }

Now, we need a new constructor: from_map:

Rust code
// in `elk/src/name.rs` impl Name { // constructor for mapped variant pub fn from_map(map: &Arc<MemoryMap>, offset: usize) -> Self { let len = map .as_slice() .iter() .skip(offset) .position(|&c| c == 0) .expect("scanned 2048 bytes without finding null-terminator for name"); Self::Mapped { map: map.clone(), range: offset..offset + len, } } // construct for owned variant (unchanged) pub fn owned<T: Into<Vec<u8>>>(value: T) -> Self { Self::Owned(value.into()) } }

This looks a lot like the old from_addr constructor, you can go back to Dynamic linker speed and correctness for more details.

The as_slice implementation looks similar:

Rust code
// in `elk/src/name.rs` impl Name { pub fn as_slice(&self) -> &[u8] { match self { Self::Mapped { map, range } => &map.as_slice()[range.clone()], Self::Owned(vec) => &vec[..], } } }

...and that's all the changes we need! In name.rs, that is.

In process.rs - where we declare and construct Object, we need the following changes:

Rust code
// in `elk/src/process.rs` use std::sync::Arc; #[derive(CustomDebug)] pub struct Segment { // now wrapped in `Arc` #[debug(skip)] pub map: Arc<MemoryMap>, // new! will be handy to find out *which* MemoryMap we need pub vaddr_range: Range<delf::Addr>, // same as before: pub padding: delf::Addr, pub flags: BitFlags<delf::SegmentFlag>, } // (cut) // in `impl Process` // in `fn load_object` // in `load_segments()` iterator chain: Ok(Segment { map: Arc::new(map), vaddr_range: vaddr..(ph.vaddr + ph.memsz), padding, flags: ph.flags, }) // (cut) // later in `fn load_object` let syms = file.read_dynsym_entries()?; let syms: Vec<_> = if syms.is_empty() { vec![] } else { let dynstr = file .get_dynamic_entry(delf::DynamicTag::StrTab) .unwrap_or_else(|_| panic!("String table not found in {:?}", path)); // we're not just dealing with random `delf::Addr` values now, // we have to find the right `MemoryMap` to refer to. let segment = segments .iter() // and here's where `vaddr_range` comes in handy .find(|seg| seg.vaddr_range.contains(&dynstr)) .unwrap_or_else(|| panic!("Segment not found for string table in {:#?}", path)); syms.into_iter() .map(|sym| { let name = Name::mapped( &segment.map, // a little bit of maths can't hurt (dynstr + sym.name - segment.vaddr_range.start).into(), ); NamedSym { sym, name } }) .collect() };

And that's it.

No other changes are needed. Name, once built, behaves the exact same way. It still implements PartialEq, Eq, Debug, Hash - everything we care about.

All our samples still run:

Shell session
$ ../target/debug/elk run hello-dl Loading "/home/amos/ftl/elk/samples/hello-dl" Found RPATH entry "/home/amos/ftl/elk/samples" Loading "/home/amos/ftl/elk/samples/libmsg.so" this is way longer than sixteen bytes
Shell session
$ ../target/debug/elk run hello-nolibc Loading "/home/amos/ftl/elk/samples/hello-nolibc" Hello from C!
Shell session
$ ../target/debug/elk run ifunc-nolibc Loading "/home/amos/ftl/elk/samples/ifunc-nolibc" Hello, regular user!
Shell session
sudo ../target/debug/elk run ifunc-nolibc [sudo] password for coolbear: Loading "/home/amos/ftl/elk/samples/ifunc-nolibc" Hello, root!

Our loader is functionally the same. But now, Name is much harder to mis-use.

Heck, we can use it in return types now!

Rust code
// in `elk/src/process.rs` #[derive(Error, Debug)] pub enum RelocationError { // changed: #[error("undefined symbol: {0:?}")] UndefinedSymbol(NamedSym), } // (cut) // in `fn apply_relocation` let found = match rel.sym { 0 => ResolvedSym::Undefined, _ => match self.lookup_symbol(&wanted, ignore_self) { undef @ ResolvedSym::Undefined => match wanted.sym.sym.bind { delf::SymBind::Weak => undef, // was using `format!` _ => return Err(RelocationError::UndefinedSymbol(wanted.sym.clone())), }, x => x, }, }; // note: `NamedSym` also needs to be made `pub`.

To test it out, we need to.. artifically clear out the symbol map, to force an undefined symbol error:

Rust code
// in `elk/src/process.rs` // in `fn load_object` let mut sym_map = MultiMap::new(); for sym in &syms { sym_map.insert(sym.name.clone(), sym.clone()) } // FIXME: just testing sym_map.clear();
Shell session
$ ../target/debug/elk run hello-dl Loading "/home/amos/ftl/elk/samples/hello-dl" Found RPATH entry "/home/amos/ftl/elk/samples" Loading "/home/amos/ftl/elk/samples/libmsg.so" Fatal error: undefined symbol: NamedSym { sym: Sym { name: 000000000000000b, bind: Global, type: Object, shndx: 10, value: 0000000000003000, size: 38 }, name: msg } ^^^^^^^^^ there it is!

Wonderful! Don't forget to remove sym_map.clear() from your copy if you're following along :)

I'm looking for my next job!

August 2020 will be my last month at my current job, and I'm excited to figure out the next step.

If you're a remote-friendly company and you think we'd be a good fit, don't hesitate to get in touch!