Skip to content

BTreeMap::iter_mut asserts on coarsely aligned keys #67438

Closed
@ssomers

Description

@ssomers

thread 'main' panicked at 'assertion failed: mem::size_of::<NodeHeader<K, V>>() == mem::size_of::<NodeHeader<K, V, K>>()', src\liballoc\collections\btree\node.rs:612:13 is the result of this code on playground and elsewhere:

use std::collections::BTreeMap;

#[derive(Eq, PartialEq, PartialOrd, Ord)]
#[repr(align(32))]
struct Aligned(bool);

fn main() {
    let mut map = BTreeMap::new();
    map.insert(Aligned(true), true);
    for (k, _v) in map.iter_mut() {
        assert!(k.0);
    }
}

There is no problem with ordinary u64 or u128 keys (both have 8 byte alignment on x86), neither on 32-bit nor 64-bit builds.

Removing the assert (or relaxing the == to <= , which then states the obvious) makes everything pass, including testing with miri and including some more tests I wrote.

Whether that's the right solution, I can't tell, because I've been trying in vain to understand the changes to the into_key_slice function in #56648. All that is clear to me is that the comment "because we did the alignment check above" is misguided and I think this issue proves that. For your entertainment, here are some particular asserts that also succeed on x86_64-unknown-linux-gnu, x86_64-pc-windows-msvc and i686-pc-windows-msvc:

assert_eq!(mem::align_of::<u8>(), 1);
assert_eq!(mem::align_of::<u16>(), 2);
assert_eq!(mem::align_of::<u32>(), 4);
assert_eq!(mem::align_of::<u64>(), 8);
assert_eq!(mem::align_of::<u128>(), 8);
assert_eq!(mem::align_of::<Aligned>(), 32);
assert_eq!(mem::align_of::<InternalNode<Aligned, ()>>(), 32);
assert_eq!(mem::align_of::<LeafNode<Aligned, ()>>(), 32);
assert_eq!(mem::align_of::<NodeHeader<K, V, Aligned>>(), 32);
#[cfg(target_arch = "x86")]
{
assert_eq!(mem::align_of::<InternalNode<u32, u32>>(), 4);
assert_eq!(mem::align_of::<InternalNode<u64, u64>>(), 8);
assert_eq!(mem::align_of::<LeafNode<(), ()>>(), 4);
assert_eq!(mem::align_of::<LeafNode<u32, ()>>(), 4);
assert_eq!(mem::align_of::<LeafNode<u64, ()>>(), 8);
assert_eq!(mem::align_of::<NodeHeader<K, V>>(), 4);
assert_eq!(mem::align_of::<NodeHeader<K, V, u32>>(), 4);
assert_eq!(mem::align_of::<NodeHeader<K, V, u64>>(), 8);
assert_eq!(mem::size_of::<LeafNode<(), ()>>(), 8);
assert_eq!(mem::size_of::<LeafNode<u32, u32>>(), 96);
assert_eq!(mem::size_of::<LeafNode<u64, u64>>(), 184);
assert_eq!(mem::size_of::<NodeHeader<K, V>>(), 8);
assert_eq!(mem::size_of::<NodeHeader<K, V, u32>>(), 8);
assert_eq!(mem::size_of::<NodeHeader<K, V, u64>>(), 8);
assert_eq!(mem::size_of::<NodeHeader<K, V, Aligned>>(), 32);
}
#[cfg(target_arch = "x86_64")]
{
assert_eq!(mem::align_of::<InternalNode<u32, u32>>(), 8);
assert_eq!(mem::align_of::<InternalNode<u64, u64>>(), 8);
assert_eq!(mem::align_of::<LeafNode<(), ()>>(), 8);
assert_eq!(mem::align_of::<LeafNode<u32, ()>>(), 8);
assert_eq!(mem::align_of::<LeafNode<u64, ()>>(), 8);
assert_eq!(mem::align_of::<NodeHeader<K, V>>(), 8);
assert_eq!(mem::align_of::<NodeHeader<K, V, u32>>(), 8);
assert_eq!(mem::align_of::<NodeHeader<K, V, u64>>(), 8);
assert_eq!(mem::size_of::<LeafNode<(), ()>>(), 16);
assert_eq!(mem::size_of::<LeafNode<u32, u32>>(), 104);
assert_eq!(mem::size_of::<LeafNode<u64, u64>>(), 192);
assert_eq!(mem::size_of::<NodeHeader<K, V>>(), 16);
assert_eq!(mem::size_of::<NodeHeader<K, V, u32>>(), 16);
assert_eq!(mem::size_of::<NodeHeader<K, V, u64>>(), 16);
assert_eq!(mem::size_of::<NodeHeader<K, V, Aligned>>(), 32);
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-collectionsArea: `std::collections`C-bugCategory: This is a bug.T-libs-apiRelevant to the library API 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