Baike.dev
Log in
Back to tool/Back to issues
#1319·rayon

Tree Borrow violation in par_merge

Author: zhouxt1Created Sep 16, 2026Updated Sep 17, 2026

Hi, during my testing, I found a Tree Borrow violation in par_merge function in rayon/src/slice/sort.rs.

The problem is in rayon/src/slice/sort.rs. Essentially, at

rust
        let mut s = State {
            left_start: left.as_mut_ptr(),
            left_end: left.as_mut_ptr().add(left_len),
            right_start: right.as_mut_ptr(),
            right_end: right.as_mut_ptr().add(right_len),
            dest,
        };

it created a child node for left, say it has tag A.

Then, when during the function call for split_for_merge,

rust
            let (left_mid, right_mid) = split_for_merge(left, right, is_less);

it created a sibling tag, S, and this was used to create a child tag when calling is_less

rust
            is_less(&right[right_mid], &left[m])

So the problem is when function is_less modify the second item, the modification propagates thorugh the tree, which acts as a foreign write to s.left_start, making A disabled. Therefore, when we want to touch s.left_start in the drop function, it fails the Tree Borrow.

Reproducer

Here is a minimal reproducer, adding it to tests/tb_repro.rs.

rust
use rayon::prelude::*;
use std::cell::Cell;
use std::sync::atomic::{AtomicUsize, Ordering::Relaxed};

#[test]
fn par_merge_state_uses_invalidated_pointer_on_panic() {
    let mut v: Vec<Cell<u32>> = (0..5000).map(|i| Cell::new(((i * 7919) % 1000) as u32)).collect();

    // Comparison #46687 is the second probe of the binary search in `split_for_merge`,
    // called from the top-level `par_merge(left = 2000, right = 3000)`.
    let countdown = AtomicUsize::new(46687);

    let _ = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
        v.par_sort_by(|a, b| {
            if countdown.fetch_sub(1, Relaxed) == 1 {
                panic!();
            }
            b.set(b.get()); // safe interior-mutable write through the comparator's argument
            a.get().cmp(&b.get())
        })
    }));
}

Then run:

bash
RUSTFLAGS="--cap-lints=warn" RAYON_NUM_THREADS=1 \
MIRIFLAGS="-Zmiri-disable-isolation -Zmiri-ignore-leaks -Zmiri-tree-borrows" \
cargo +nightly miri test --test tb_repro

will give you a TB violation: 

error: Undefined Behavior: read access through <3902217> at alloc119318[0xfa0] is forbidden
    --> src/slice/sort.rs:1414:21
     |
1414 |                     ptr::copy_nonoverlapping(self.left_start, self.dest, left_len);
     |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Undefined Behavior occurred here
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the Tree Borrows rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/tree-borrows.md for further information
     = help: the accessed tag <3902217> has state Disabled which forbids this child read access
help: the accessed tag <3902217> was created here, in the initial state Reserved
    --> src/slice/sort.rs:1357:25
     |
1357 |             left_start: left.as_mut_ptr(),
     |                         ^^^^^^^^^^^^^^^^^
help: the accessed tag <3902217> later transitioned to Disabled due to a foreign write access at offsets [0xfa0..0xfa4]
    --> tests/tb_repro.rs:18:13
     |
  18 |             b.set(b.get()); // safe interior-mutable write through the comparator's argument
     |             ^^^^^^^^^^^^^^
     = help: this transition corresponds to a loss of read and write permissions
     = note: this is on thread `par_merge_state`
     = note: stack backtrace:
             0: <rayon::slice::sort::par_merge::State<std::cell::Cell<u32>> as std::ops::Drop>::drop
                 at src/slice/sort.rs:1414:21: 1414:83
             1: std::ptr::drop_in_place::<rayon::slice::sort::par_merge::State<std::cell::Cell<u32>>> - shim(Some(rayon::slice::sort::par_merge::State<std::cell::Cell<u32>>))
                 at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:809:1: 811:25
             2: rayon::slice::sort::par_merge::<std::cell::Cell<u32>, {closure@<[std::cell::Cell<u32>] as rayon::prelude::ParallelSliceMut<std::cell::Cell<u32>>>::par_sort_by<{closure@tests/tb_repro.rs:14:23: 14:29}>::{closure#0}}>
                 at src/slice/sort.rs:1422:5: 1422:6
             3: rayon::slice::sort::merge_recurse::<std::cell::Cell<u32>, {closure@<[std::cell::Cell<u32>] as rayon::prelude::ParallelSliceMut<std::cell::Cell<u32>>>::par_sort_by<{closure@tests/tb_repro.rs:14:23: 14:29}>::{closure#0}}>
                 at src/slice/sort.rs:1506:9: 1506:65
             4: rayon::slice::sort::par_mergesort::<std::cell::Cell<u32>, {closure@<[std::cell::Cell<u32>] as rayon::prelude::ParallelSliceMut<std::cell::Cell<u32>>>::par_sort_by<{closure@tests/tb_repro.rs:14:23: 14:29}>::{closure#0}}>
                 at src/slice/sort.rs:1610:9: 1610:69
             5: <[std::cell::Cell<u32>] as rayon::prelude::ParallelSliceMut<std::cell::Cell<u32>>>::par_sort_by::<{closure@tests/tb_repro.rs:14:23: 14:29}>
                 at src/slice/mod.rs:457:9: 459:11
             6: par_merge_state_uses_invalidated_pointer_on_panic::{closure#1}
                 at tests/tb_repro.rs:14:9: 20:11
             7: <{closure@tests/tb_repro.rs:13:67: 13:69} as std::ops::FnOnce<()>>::call_once - shim
                 at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:250:5: 250:71
             8: <std::panic::AssertUnwindSafe<{closure@tests/tb_repro.rs:13:67: 13:69}> as std::ops::FnOnce<()>>::call_once
                 at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/panic/unwind_safe.rs:275:9: 275:19
             9: std::panicking::catch_unwind::do_call::<std::panic::AssertUnwindSafe<{closure@tests/tb_repro.rs:13:67: 13:69}>, ()>
                 at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:581:40: 581:43
             10: std::panicking::catch_unwind::<(), std::panic::AssertUnwindSafe<{closure@tests/tb_repro.rs:13:67: 13:69}>>
                 at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:544:19: 544:88
             11: std::panic::catch_unwind::<std::panic::AssertUnwindSafe<{closure@tests/tb_repro.rs:13:67: 13:69}>, ()>
                 at ~/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:359:14: 359:40
             12: par_merge_state_uses_invalidated_pointer_on_panic
                 at tests/tb_repro.rs:13:13: 21:8
             13: par_merge_state_uses_invalidated_pointer_on_panic::{closure#0}
                 at tests/tb_repro.rs:6:55: 6:55

This bug was originally found when testing rayon/tests/sort-panic-safe.rs. It is hard to reproduce it in Miri with that test case, thus we provide this reproducer.

Potential Fix

A potential fix is as follows in src/slice/sort.rs: 

// replace this: let (left_mid, right_mid) = split_for_merge(left, right, is_less);
        let (left_mid, right_mid) = split_for_merge(
            slice::from_raw_parts(s.left_start, left_len),
            slice::from_raw_parts(s.right_start, right_len),
            is_less,
        );

This makes the left in the function call a descendants of s.left_start instead of a sibling, so the write becomes a 'local write', and will not disable the parent. This prevents the Tree Borrow violation.

I can make a PR if a fix is wanted.

Source: rayon-rs/rayon

View original on GitHubView discussion on GitHub