Why does adding a lifetime work?
This blog post covers my adventure in fixing a bug in the Rust bindings for the Capstone C library, a disassembly library that supports several CPU architectures. The capstone-rs crate attempts to provide a Rusty, object-oriented interface.
You do not necessarily need previous experience in C code or foreign function (FFI) bindings to understand this blog post.
I will cover some of the steps I used to debug this problem. Hopefully, readers can learn from my mistakes.
Some code snippets have been simplified.
In order to make it easier to understand the discussion, I'll give a brief overview of Capstone and capstone-rs.
Capstone interprets an array of bytes as an array of instructions, providing information such as the address of the instruction, which registers are written, and information about the operands.
Capstone does not parse executable file formats such as ELF, Mach-O, or PE.
When I refer to "Capstone" or "the C code", I am referring to the base C library. When I refer to "the Rust code", I usually mean capstone-rs (unless otherwise specified).
I was unable to reproduce the bug on my GNU/Linux development machine (even after a thousand iterations of cargo test). I needed a Mac to reproduce the bug.
I first reproduced the bug with my brother-in-law (he provided the Mac computer). This was indeed the worst type of bug; the bug only showed up sometimes.
One case where tests fail only sometimes is a race condition. One type of race condition is a data race.
I started by reading over the capstone-rs Rust code but did not find a problem. capstone-rs does not spawn threads.
Then, I decided to look over the Capstone C source code. Capstone was not spawning threads, either.
I realized that the cargo test harness spawns multiple threads (to parallelize tests). But how could threads access the same memory location?
The only way left to share memory was through global variables. My brother-in-law and I searched the Capstone C code for global variable writes.
We looked at the body of archs_enable(). The static variable initialized is essentially a global variable (but only "visible" from within the archs_enable() function).
The arrays cs_arch_init, cs_arch_option, cs_arch_destroy, and cs_arch_disallowed_mode_mask are global!
The initialzed global variable was read and modified without a lock! This was a potential data race. Safe Rust code guarantees the absence of data races, but the C language makes no such guarantee.
If multiple threads entered archs_enabled() simultaneously, initialized would be false. Each thread would attempt to initialize the global variables simultaneously. Afterward, each thread would set initialzed to false.
Since each thread would be attempting to initialize the arrays with the same values (they are constant), you may be tempted to think that this construction is safe. However, due to complications such as out of order execution, a memory barrier is also required. Otherwise, some CPU cores could "see" that initialized is true but not yet "see" that global arrays are initialized the correct values.
Note: I have since eliminated the upstream data race with a pull-request.
I first tried to work around this bug from within the Rust code.
My brother-in-law and I investigated the primitives in the std::sync module that could help. We wanted a primitive that would guarantee that initialization of the global variables would happen exactly once.
A synchronization primitive which can be used to run a one-time global initialization. Useful for one-time initialization for FFI or related functionality.
This fit our use case perfectly!
However, because archs_enable() was declared as static, the symbol is not "visible" to consumers of library (such as capstone-sys or capstone-rs). static declarations in C are similar to non-pub declarations in Rust.
In order to work around this issue, we called cs_version() (which calls archs_enable()). Of the exported Capstone functions that called archs_enable(), cs_version() seemed to have the least overhead.
We defined a Rust function init_global_state() that peforms the initialization. Since the cs_version() is a C function, we had to use an unsafe block to call the function.
Next, we needed to call init_global_state() before calling a C Capstone function. That way, we would initialized globals in archs_enable() initialization in a thread-safe way.
In the first pass with my brother-in-law, we inserted calls to init_global_state() at the beginning of any Rust function that called a Capstone C function. The initial work resulted in a work-in-progress pull-request.
I knew that the global initialization we used was sub-optimal. While it would be safe to add extra synchronization, we would cause unnecessary slowdown in the capstone-rs Rust library. I decided to reason about the problem.
Requirement: Before the first call to a C function that writes to the global arrays, we must call init_global_state() to initialize safely.
impl methods: functions that are in an impl block AND take a self parameter.
If we call init_global_state() when we construct a new instance of a type (struct or enum), then we do not need to call init_global_state() in any of the impl methods of that type.
For example, if we call init_global_state() when we create a Capstone instance, then we do not need to call init_global_state() in Capstone::disasm_all() (which takes a self parameter).
Then, as long as all constructors call init_global_state(), then impl methods do not need to call init_global_state(). Any time an impl method would be called, a self parameter is required (by definition of impl method). This self instance would have been created by a constructor that already called init_global_state().
///    potentially mutates global state must ensure `init_global_state()` is called first.
///    then methods *M* that take a `self` parameter do not need to call `init_global_state()`.
///    cannot construct a *T* manually.
Using this reasoning, I was able to remove several calls to init_global_state(), elminating unnecessary synchronization.
After adding the thread-safe initialization code, cargo test would still fail sometimes!
My first attempt at using tools to help find the bug was not successful. Since I thought my bug was a threading issue, I tried Clang's ThreadSanitizer feature and Valgrind's Helgrind and DRD plugins. Each of the tools only reported false positives.
The stacktraces did not include code that I wrote, only code in the Rust test runner.
Through compile-time borrow checks, the Rust compiler ensures that there can only be up to one mutable reference OR any number of immutable references to a given variable.
Perhaps I was exposing a non-mut reference where I should be exposing a mut reference?
As the bindings author, I am responsible for describing to the Rust compiler how the borrowing and lifetimes work in the underlying C library.
I decided to check my assumptions where I only took a mutable reference.
If the architecture is ARM, then cs_disasm() mutates the handle.
In capstone-rs, we expose cs_disasm() through the Capstone::disasm_*() family of methods. But, the methods take &self parameter, which is not a mutable reference! As the bindings author, it is my responsibility to expose the correct interface that allows the Rust type system to ensure safety.
It was an easy fix to have the methods take &mut self instead of &self.
Perhaps some capstone-rs types were mistakenly identified as Send and/or Sync? Maybe Cargo generated tests that ran in parallel and had race conditions?
Since all of Capstone's fields are Send and Sync, the Rust compiler treated Capstone as Send and Sync.
But, the Capstone type should not be Send nor Sync.
The Capstone C library defines the handle type csh as an alias for size_t (equivalent to usize in Rust). However, under the hood, csh is cast as a pointer to an opaque type.
How can we tell the Rust compiler stop stop inferring that the Capstone struct is Send/Sync?
Since the C library already treated the csh field as a pointer, I just changed the csh type to a *mut c_void.
I decided to revisit tools to help find the bugs, specifically Valgrind (since it is the easy to use). I decided to use the Memcheck plugin (the default plugin) to look for non-threading bugs.
The Valgrind framework uses dynamic binary instrumentation (DBI) to run instrumentation code. Valgrind's Memcheck plugin works by tracking allocation calls (such as malloc()) and memory reads/writes. Memcheck can catch bugs such as invalid memory reads/writes and memory leaks.
To avoid issues, I decided to use the system allocator (instead of the default jemalloc implementation). To make the nightly toolchain optional, I added an alloc_system feature to toggle the system allocator.
Note: Since implementing the alloc_system feature, Rust 1.28 stabilized global allocators.
The tests actually failed! This was the first time cargo test failed on my Linux development machine. Different tests failed each time (like on Mac OS). Sometimes, the test program did not complete and exited with SIGILL: illegal instruction.
To make tests more consistent and reduce errors, I passed --test-threads=1 and test_syntax(). At this point, I had the reduced test case to run under Valgrind.
I ran the test binary directly (instead of the cargo test ... invocation) to simplify debugging. Since, cargo test spawns the test binary as a child process, I would have needed to trace the child process.
==12465== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==12465== Reachable blocks (those to which a pointer was found) are not shown.
We can see there that Valgrind's Memcheck plugin showed there was an error Invalid read of size 1. Memcheck also gave us stack traces of where the memory was originally allocated and freed (since we passed --track-origins=yes/--leak-check=full, ).
Notice that Rust functions (such as capstone::capstone::Capstone::disasm) and C functions (such as cs_disasm()) appeared in the output. Valgrind does not care about the source langauge of functions. Valgrind even correctly demangles the names.
We can see here that cs.disasm_all() caused the allocation. The resulting instructions are collected into a Vec<Insn>. The underlying memory buffer with the instructions is immediately freed after the collect() (implicitly through the Drop trait).
The insn_detail() method of the Capstone struct takes an Insn instance to get the InsnDetail struct that contains extra details about instructions. For example, InsnDetail contains information about registers that are implicitly read/written and logical groups to which an instruction belongs.
At this point, I knew that memory was being freed too soon. The InsnDetail struct relies on the memory allocated by cs_disasm() to remain.
Even though tests were passing on Linux with the default allocator, the tests actually read from freed memory. Rust's default allocator simply masked the issue.
The Capstone instance did not live long enough. How could we fix the problem?
Answer: Declaring a lifetime for the Capstone struct.
The new lifetime 'cs told the Rust type system that the Capstone struct logically contains a reference.
After implementing the change, the tests passed (on Mac OS and Linux).
Frees the memory allocated by disasm_all() in the Drop implementation.
The underlying buffer with the instructions will be dropped.
The final collect()'d vector will contain dangling references to instructions that have already been freed.
The local variable insns_backing lives until the end of the function, so the insns variable does not contain dangling references.
The "temporary value does not live long enough" error led me to the bug in the code. But, I'm not sure why adding a lifetime to the Capstone struct fixed the error. Why didn't the Rust compiler emit a warning when there was no lifetime?
Update 2018-10-05: Merged pull-request from earthengine that removes the extra lifetime on the Capstone structure. The Capstone structure "owns" the handle allocation, so no lifetime needs to be exposed.
This bug was originally classified as Mac OS-only. Even then, tests only failed sometimes.
There were several failed attempts to fix the bug, but I discovered (and fixed) other bugs. For example, the Capstone struct was found to be Send/Sync.
I was also able to finaly track down the underlying bug with Valgrind. Even though Valgrind is usually used on code that is written in C/C++, Valgrind is a useful tool for programs written in Rust.
Extensive tests help you find and fix bugs. capstone-rs contains over 2000 lines of tests. Without the Rust tests, the test failure on Mac OS would have never been reported.
Use debugging tools. Valgrind's Memcheck plugin helped track down the bug. Safe Rust code prevents the types of bugs that the Valgrind plugins catch. But, unsafe Rust code and C code can have these types of bugs. Hence, tools that are used to debug C code are useful for debugging unsafe Rust code.
You must be careful with not only the internal implementation, but the public interface to Rust FFI bindings. The public interfaces (including lifetimes) tells the Rust type system how long different items may live.
Thanks to Gulshan Singh for reviewing this post.