Nope-correctness, a.k.a. fearless concurrency

Every time someone reports a security bug to Chromium, Chromium’s security sheriffs have to reproduce the bug, often on several different Chromium versions.

Often, we rely on ClusterFuzz to do this — but sometimes it’s manual.

Either way, we have to unzip Chromium builds. Often, these are ASAN builds which are just enormous — currently 2.7GB. Sometimes, they’re UBSAN builds — weighing in at 36.5GB (because of an incompatibility with Chromium’s component builds).

Simply unzipping these is an impediment. ClusterFuzz can take 25 minutes just to unzip a Chromium build. (Even more when you add on the time to fetch the build over the network first).

Can we make the unzipping quicker?

Enter — Rust and its “fearless concurrency”. This is the woolly idea that you can take a normally single-threaded workload and, because Rust gives you extra protection against data races and other memory safety problems, simply throw it onto multiple threads.

Can this make our unzipping quicker?

Well, the first clue that there’s hope is a sentence in the documentation for the Rust zip crate:

At the moment, this type is cheap to clone if this is the case for the reader it uses.

We can create a cheap-to-clone file reader, right? Let’s try it. We’ll create a new Rust project, call it ripunzip (in homage to ripgrep ), and add some of the crates we’ll need:

mkdir ripunzip; cd ripunzip
cargo init
cargo add clap --features=derive
cargo add rayon
cargo add zip
cargo add anyhow
cargo run --release

Aside from the zip library itself, the key library here is rayon. Rayon gives us such things as parallel iterators, distributing tasks across a thread pool with minimal hassle.

Let’s start with the skeleton of a new tool, to check I know how to use the zip library :)

That works!

Now let’s try some actual unzipping.

So far, so good… and of course not at all parallel. So now for the fun bit…

Did you guess why the loop is done using iterators? It’s because we want to use Rayon. Specifically, we want to change

(0..file_count).for_each(…)

into

(0..file_count).into_par_iter().for_each(…)

and that’s literally all you need to do to parallelize the loop using Rayon.

Except… this form of for_each takes a Fn instead of a FnMut, and so we get an error:

error[E0596]: cannot borrow `zip` as mutable, as it is a captured variable in a `Fn` closure
   --> src/main.rs:102:24
    |
102 |         let mut file = zip.by_index(i).expect("Unable to get file from zip");
    |                        ^^^^^^^^^^^^^^^ cannot borrow as mutable

For more information about this error, try `rustc --explain E0596`.
error: could not compile `runzip` due to previous error

This is fearless concurrency. We can’t have multiple threads accessing the same ZipFileobject at the same time. Rust says nope. Let’s rely on continued nope-correctness as we rectify this.

First, in each iteration of the loop, let’s add

let mut myzip = zip.clone();

and then subsequently use myzip instead of zip .

Now what? Nope!

error[E0599]: the method `clone` exists for struct `ZipArchive<File>`, but its trait bounds were not satisfied
   --> src/main.rs:102:29
    |
102 |         let mut myzip = zip.clone();
    |                             ^^^^^ method cannot be called on `ZipArchive<File>` due to unsatisfied trait bounds
    |
   ::: /path/.rustup/toolchains/stable-x86_64-apple-darwin/lib/rustlib/src/rust/library/std/src/fs.rs:98:1
    |
98  | pub struct File {
    | --------------- doesn't satisfy `File: Clone`
    |
   ::: /path/.cargo/registry/src/github.com-1ecc6299db9ec823/zip-0.6.3/src/read.rs:69:5
    |
69  |     pub struct ZipArchive<R> {
    |     ------------------------ doesn't satisfy `ZipArchive<File>: Clone`
    |
    = note: the following trait bounds were not satisfied:
            `File: Clone`
            which is required by `ZipArchive<File>: Clone`

Nope again. Rust is telling me that we can’t clone the ZipArchive because the underlying File can’t be cloned.

This is exactly what we expected, and it’s nice to have confirmation. Again, Rust gives us the safeguards that we need to confidently do bold things. Let’s set about making File Clone …

Here we’re simply storing the file as an Arc<Mutex<File>> , but then we need to implement Read and Seek . Seek , in particular, requires us to store the position that each thread has seeked to.

(That code might not be perfect…. Obviously, it needs tests).

Putting it all together, here’s our renewed main function.

This… works.

For one (2.5GB) Mac ASAN build, the speed difference is substantial…

unzip:

real 1m10.807s
user 0m55.483s
sys 0m6.637s

ripunzip:

real 0m13.193s
user 0m39.767s
sys 0m43.872s

These results aren’t entirely consistent, with ripunzip sometimes taking up to 30 seconds, but the speedup is usually 4x on my machine.

Is this safe? The compiler says so, but might the underlying zip library authors have made mistakes? Well, there is no mention of unsafe in the code of the zip library itself so I’m confident that it’s fine. Some of the underlying decompressors use C FFI, but as a zip file stores each file compressed separately it seems unlikely that a parallel unzip could cause unsafety there.

My takeaways from this are:

• the overall strategy of unzipping a file in parallel does seem to be quicker;
• Rust makes it easy. (Interestingly, other folks seem to have done multithreaded unzippers in Java and Python, but I can’t spot one in C/C++.)

The next steps here are:

• Add tests and clean up the code.
• Publish this to crates.io, github etc. Working on it!
• Performance tweaks: Work out whether Rayon is creating a sensible number of threads given it’s a very IO-bound workload. Investigate whether BufReader makes things quicker or slower.
• The big project: Fetch the zip file over HTTP(S) at the same time as unzipping… this will require a few HTTP(S) range requests to read the zip end-of-file directory before fetching the rest of the file. This is going to be hard, but fun.

I’m really interested in whether async Rust would be suited for this use case, especially when we do Step 2 and get the HTTP fetch running in parallel too. Advice and thoughts welcome!