Skip to content

BTreeMap::split_off is not panic-safe leading to a potential double-free #158165

Closed
jonbaldie/rust
#2

Description

@ostrowr

Summary

A panic from a key comparator during BTreeMap::split_off can unwind after Root::split_off has already moved a suffix into the temporary right-hand tree, but before the lower levels are split, borders are repaired, and the map length is recomputed. After catching the panic, the original map can have a stale length and a partially-detached structure. Consuming iteration can then double-free values in entirely safe Rust.

This is very related to the allocator-panic insertion issue (#156490), but the trigger/path here is different.

Reproducer:

#![forbid(unsafe_code)]
use std::{cmp::Ordering, collections::BTreeMap, panic::catch_unwind, sync::Mutex};

#[derive(PartialEq, Eq)]
struct K(i32);

impl PartialOrd for K {
    fn partial_cmp(&self, r: &Self) -> Option<Ordering> { Some(self.cmp(r)) }
}
impl Ord for K {
    fn cmp(&self, r: &Self) -> Ordering {
        if self.0 == 6 && r.0 == 0 { panic!("cmp panic") }
        self.0.cmp(&r.0)
    }
}

fn main() {
    let m = Mutex::new(BTreeMap::new());
    {
        let mut g = m.lock().unwrap();
        for i in (6..12).chain(0..6) {
            g.insert(K(i), Box::new(0u8));
        }
    }

    assert!(catch_unwind(|| {
        drop(m.lock().unwrap().split_off(&K(6)));
    }).is_err());

    let m = m.into_inner().unwrap_or_else(|p| p.into_inner());
    eprintln!("len={} reachable={}", m.len(), m.range(..).count());
    drop(m.into_iter().nth_back(5));
}

This replicates on stable, beta, and nightly (1.96.0, 1.97.0, 1.98.0) (playground):

thread 'main' (41) panicked at src/main.rs:12:38:
cmp panic
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
len=12 reachable=6
free(): double free detected in tcache 2

Mechanism

Root::split_off currently interleaves comparison/search and destructive moves roughly like:

  1. left_node.search_node(key)
  2. split_edge.move_suffix(&mut right_node)
  3. descend to the next level
  4. repeat

In this repro, the first iteration moves a suffix at the root. The next lower-level search_node invokes cmp(6, 0) and panics. Unwinding skips fix_right_border, fix_left_border, and the caller-side calc_split_length / self.length update in map.rs. The original map is left with its old length (12) but only part of the tree reachable (6 entries), and later iteration trusts the stale length.


I used Codex to find this issue but manually verified it. I'm guessing a fix for this will be similar to that for #156490 but may have to be applied to both code paths.

Activity

  1. added
    needs-triageThis issue may need triage. Remove when done. See docs forge.rust-lang.org/release/issue-triaging
    on Jun 20, 2026
  2. added
    I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness
    on Jun 20, 2026
  3. added
    I-prioritizeIssue needs a team member to assess the impact. Will be replaced by P-{low,medium,high,critical}
    on Jun 20, 2026
  4. added
    A-collectionsArea: `std::collections` (prefer A-binaryheap, A-btree, A-hashtable, A-linkedlist, A-vecdeque)
    A-panicArea: Panicking machinery
    T-libsRelevant to the library team, which will review and decide on the PR/issue.
    and removed
    needs-triageThis issue may need triage. Remove when done. See docs forge.rust-lang.org/release/issue-triaging
    on Jun 20, 2026
  5. asquared31415 commented on Jun 20, 2026

    @asquared31415
    Contributor

    This is a violation of the Ord contract, but the data structure still should limit the impact to incorrect results, not UB.

  6. deleted a comment from ipezygj on Jun 21, 2026
  7. ostrowr commented on Jun 22, 2026

    @ostrowr
    Author

    This is a violation of the Ord contract

    I think cmp can panic - for example, RefCell's cmp can panic. Here's an example repro of the exact same issue without defining my own cmp but just making a refcell panic when calling it.

    https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=23c7a7d6a1c41fe00d2c10c87584763b

  8. added
    P-highHigh priority
    and removed
    I-prioritizeIssue needs a team member to assess the impact. Will be replaced by P-{low,medium,high,critical}
    on Jun 24, 2026
  9. Darksonn commented on Aug 5, 2026

    @Darksonn
    Member

    The fix PR was closed due to inactivity, so this is now unclaimed.

  10. added a commit that references this issue on Aug 29, 2026
    68ec897
  11. added a commit that references this issue on Aug 29, 2026
    a083cee
  12. added a commit that references this issue on Aug 30, 2026
    69748f4
  13. added
    A-btreeArea: `std::collections::{BTreeMap, BTreeSet}`
    and removed
    A-collectionsArea: `std::collections` (prefer A-binaryheap, A-btree, A-hashtable, A-linkedlist, A-vecdeque)
    on Nov 2, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-btreeArea: `std::collections::{BTreeMap, BTreeSet}`A-panicArea: Panicking machineryC-bugCategory: This is a bug.I-unsoundIssue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/SoundnessP-highHigh priorityT-libsRelevant to the library team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions