Upgrade Turbopack to hashbrown 0.15

@@ -405,7 +405,7 @@ version = "0.1.0" dependencies = [  "bincode 2.0.1",  "codspeed-criterion-compat",- "hashbrown 0.14.5",+ "hashbrown 0.15.4",  "rustc-hash 2.1.1",  "serde",  "shrink-to-fit",@@ -2148,6 +2148,20 @@ dependencies = [  "parking_lot_core", ] +[[package]]+name = "dashmap"+version = "7.0.0-rc2"+source = "registry+https://github.com/rust-lang/crates.io-index"+checksum = "e4a1e35a65fe0538a60167f0ada6e195ad5d477f6ddae273943596d4a1a5730b"+dependencies = [+ "cfg-if",+ "crossbeam-utils",+ "equivalent",+ "hashbrown 0.15.4",+ "lock_api",+ "parking_lot_core",+]+ [[package]] name = "data-encoding" version = "2.4.0"@@ -2554,7 +2568,7 @@ checksum = "d4029edd3e734da6fe05b6cd7bd2960760a616bd2ddd0d59a0124746d6272af0" dependencies = [  "cfg-if",  "libc",- "redox_syscall",+ "redox_syscall 0.3.5",  "windows-sys 0.48.0", ] @@ -3172,7 +3186,6 @@ checksum = "e5274423e17b7c9fc20b6e7e208532f9b19825d82dfd615708b70edd83df41f1" dependencies = [  "ahash 0.8.12",  "allocator-api2",- "serde", ]  [[package]]@@ -4416,11 +4429,10 @@ checksum = "b4ce301924b7887e9d637144fdade93f9dfff9b60981d4ac161db09720d39aa5"  [[package]] name = "lock_api"-version = "0.4.10"+version = "0.4.14" source = "registry+https://github.com/rust-lang/crates.io-index"-checksum = "c1cc9717a20b1bb222f333e6a92fd32f7d8a18ddc5a3191a11af45dcbf4dcd16"+checksum = "224399e74b87b5f3557511d98dff8b14089b3dadafcab6bb93eab67d3aace965" dependencies = [- "autocfg",  "scopeguard",  "serde", ]@@ -5591,15 +5603,15 @@ dependencies = [  [[package]] name = "parking_lot_core"-version = "0.9.8"+version = "0.9.12" source = "registry+https://github.com/rust-lang/crates.io-index"-checksum = "93f00c865fe7cabf650081affecd3871070f26767e7b2070a3ffae14c654b447"+checksum = "2621685985a2ebf1c516881c026032ac7deafcda1a2c9b7850dc81e3dfcb64c1" dependencies = [  "cfg-if",  "libc",- "redox_syscall",+ "redox_syscall 0.5.18",  "smallvec",- "windows-targets 0.48.5",+ "windows-link 0.2.1", ]  [[package]]@@ -6508,6 +6520,15 @@ dependencies = [  "bitflags 1.3.2", ] +[[package]]+name = "redox_syscall"+version = "0.5.18"+source = "registry+https://github.com/rust-lang/crates.io-index"+checksum = "ed2bf2547551a7053d6fdfafda3f938979645c44812fbfcda098faae3f1a362d"+dependencies = [+ "bitflags 2.9.1",+]+ [[package]] name = "ref-cast" version = "1.0.24"@@ -10007,7 +10028,7 @@ dependencies = [  "byteorder",  "codspeed-criterion-compat",  "crc32fast",- "dashmap 6.1.0",+ "dashmap 7.0.0-rc2",  "either",  "fs-err",  "jiff",@@ -10079,7 +10100,7 @@ dependencies = [  "bincode 2.0.1",  "codspeed-criterion-compat",  "concurrent-queue",- "dashmap 6.1.0",+ "dashmap 7.0.0-rc2",  "either",  "erased-serde",  "event-listener",@@ -10122,10 +10143,10 @@ dependencies = [  "bitfield",  "codspeed-criterion-compat",  "crossbeam-utils",- "dashmap 6.1.0",+ "dashmap 7.0.0-rc2",  "fs-err",  "futures",- "hashbrown 0.14.5",+ "hashbrown 0.15.4",  "indexmap 2.14.0",  "indoc",  "jiff",@@ -10228,7 +10249,7 @@ dependencies = [  "bytes",  "codspeed-criterion-compat",  "concurrent-queue",- "dashmap 6.1.0",+ "dashmap 7.0.0-rc2",  "fs-err",  "futures",  "include_dir",@@ -10654,7 +10675,7 @@ dependencies = [  "bumpalo",  "bytes-str",  "codspeed-criterion-compat",- "dashmap 6.1.0",+ "dashmap 7.0.0-rc2",  "data-encoding",  "either",  "forked_react_compiler",@@ -10854,7 +10875,7 @@ dependencies = [  "bincode 2.0.1",  "bytes",  "const_format",- "dashmap 6.1.0",+ "dashmap 7.0.0-rc2",  "either",  "futures",  "futures-retry",@@ -11012,7 +11033,7 @@ dependencies = [  "anyhow",  "either",  "flate2",- "hashbrown 0.14.5",+ "hashbrown 0.15.4",  "indexmap 2.14.0",  "itertools 0.10.5",  "postcard",

@@ -267,7 +267,7 @@ criterion = { package = "codspeed-criterion-compat", version = "4.3.0" } ctor = "1.0.7" crossbeam-channel = "0.5.8" crossbeam-utils = "0.8"-dashmap = "6.1.0"+dashmap = "7.0.0-rc2" data-encoding = "2.3.3" dhat = { version = "0.3.2" } dunce = "1.0.3"@@ -279,7 +279,7 @@ fs-err = "3.1.1" futures = "0.3.31" futures-retry = "0.6.0" futures-util = "0.3.31"-hashbrown = "0.14.5"+hashbrown = "0.15.4" image = { version = "0.25.8", default-features = false } indexmap = "2.14.0" indoc = "2.0.0"

@@ -10,7 +10,7 @@ workspace = true  [dependencies] bincode = { workspace = true }-hashbrown = { workspace = true, features = ["serde"]}+hashbrown = { workspace = true, features = ["raw-entry", "serde"]} rustc-hash = { workspace = true } serde = { workspace = true, features = ["derive"] } shrink-to-fit = { workspace = true, features = ["hashbrown"] }

@@ -43,7 +43,7 @@ bitfield = { workspace = true } crossbeam-utils = { workspace = true } dashmap = { workspace = true, features = ["raw-api"]} fs-err = { workspace = true }-hashbrown = { workspace = true, features = ["raw"] }+hashbrown = { workspace = true } indexmap = { workspace = true } jiff = "0.2.10" lzzzz = { workspace = true, optional = true }

@@ -22,6 +22,7 @@ use std::{  use anyhow::{Context, Result, bail}; use auto_hash_map::{AutoMap, AutoSet};+use hashbrown::hash_table::Entry; use indexmap::IndexSet; use parking_lot::Mutex; use rustc_hash::{FxHashMap, FxHashSet, FxHasher};@@ -80,7 +81,7 @@ use crate::{     error::TaskError,     kv_backing_storage::TurboBackingStorage,     utils::{-        dash_map_raw_entry::{RawEntry, get_shard, raw_entry_in_shard, raw_get_in_shard},+        dash_map_entry::{get_in_shard, get_shard, with_entry_in_shard},         shard_amount::compute_shard_amount,         stopwatch::Stopwatch,     },@@ -1552,7 +1553,7 @@ impl TurboTasksBackend {         // Use a read lock rather than a write lock to avoid contention. connect_child         // may re-enter task_cache with a write lock, so we must not hold a write lock here.         if let Some(task_id) =-            raw_get_in_shard(shard, hash, |k| k.eq_components(native_fn, this, arg_ref))+            get_in_shard(shard, hash, |k| k.eq_components(native_fn, this, arg_ref))         {             self.track_cache_hit_by_fn(native_fn);             operation::ConnectChildOperation::run(parent_task, task_id, ctx);@@ -1569,76 +1570,88 @@ impl TurboTasksBackend {             self.track_cache_hit_by_fn(native_fn);             // Step 3a: Insert into in-memory cache using the pre-located shard.             // Use the existing Arc from storage to avoid a duplicate allocation.-            match raw_entry_in_shard(shard, self.storage.task_cache.hasher(), hash, |k| {-                k.eq_components(native_fn, this, arg_ref)-            }) {-                RawEntry::Occupied(_) => {}-                RawEntry::Vacant(e) => {-                    e.insert(stored_type, task_id);-                }-            };+            with_entry_in_shard(+                shard,+                self.storage.task_cache.hasher(),+                hash,+                arg,+                |k, arg| k.eq_components(native_fn, this, arg.as_ref()),+                |entry, _arg| {+                    if let Entry::Vacant(entry) = entry {+                        entry.insert((stored_type, task_id));+                    }+                },+            );             task_id         } else {-            match raw_entry_in_shard(shard, self.storage.task_cache.hasher(), hash, |k| {-                k.eq_components(native_fn, this, arg_ref)-            }) {-                RawEntry::Occupied(e) => {-                    // Another thread beat us to creating this task — use their task_id.-                    // They will handle logging the new task as modified.-                    let task_id = *e.get();-                    drop(e);-                    self.track_cache_hit_by_fn(native_fn);-                    task_id-                }-                RawEntry::Vacant(e) => {-                    // Only now do we force the allocation.-                    // NOTE: if our caller had to perform resolution, then this will have already-                    // been boxed and take_box just takes it.-                    let task_type = CachedTaskTypeArc::new(CachedTaskType {-                        native_fn,-                        this,-                        arg: arg.take_box(),-                    });-                    let task_id = if transient {-                        self.transient_task_id_factory.get()-                    } else {-                        self.persisted_task_id_factory.get()-                    };-                    // Initialize storage BEFORE making task_id visible in the cache.-                    // This ensures any thread that reads task_id from the cache sees-                    // the storage entry already initialized (restored flags set).-                    self.storage-                        .initialize_new_task(task_id, Some(task_type.clone()));-                    // insert() consumes e, releasing the shard write lock.-                    e.insert(task_type, task_id);-                    self.track_cache_miss_by_fn(native_fn);-                    // Update the aggregation number before connecting the child-                    // We don't need this on any of the task recovery paths above because the-                    // aggregation number will already be set.-                    if is_root {-                        AggregationUpdateQueue::run(-                            AggregationUpdateJob::UpdateAggregationNumber {-                                task_id,-                                base_aggregation_number: u32::MAX,-                                distance: None,-                            },-                            &mut ctx,-                        );-                    } else if native_fn.is_session_dependent && self.should_track_dependencies() {-                        const SESSION_DEPENDENT_AGGREGATION_NUMBER: u32 = u32::MAX >> 2;-                        AggregationUpdateQueue::run(-                            AggregationUpdateJob::UpdateAggregationNumber {-                                task_id,-                                base_aggregation_number: SESSION_DEPENDENT_AGGREGATION_NUMBER,-                                distance: None,-                            },-                            &mut ctx,-                        );-                    };+            let (task_id, created) = with_entry_in_shard(+                shard,+                self.storage.task_cache.hasher(),+                hash,+                arg,+                |k, arg| k.eq_components(native_fn, this, arg.as_ref()),+                |entry, arg| match entry {+                    Entry::Occupied(entry) => {+                        // Another thread beat us to creating this task — use their task_id.+                        // They will handle logging the new task as modified.+                        (entry.get().1, false)+                    }+                    Entry::Vacant(entry) => {+                        // Only now do we force the allocation.+                        // NOTE: if our caller had to perform resolution, then this will have+                        // already been boxed and take_box just takes it.+                        let task_type = CachedTaskTypeArc::new(CachedTaskType {+                            native_fn,+                            this,+                            arg: arg.take_box(),+                        });+                        let task_id = if transient {+                            self.transient_task_id_factory.get()+                        } else {+                            self.persisted_task_id_factory.get()+                        };+                        // Initialize storage BEFORE making task_id visible in the cache.+                        // This ensures any thread that reads task_id from the cache sees+                        // the storage entry already initialized (restored flags set).+                        self.storage+                            .initialize_new_task(task_id, Some(task_type.clone()));+                        entry.insert((task_type, task_id));+                        (task_id, true)+                    }+                },+            ); -                    task_id+            // The entry closure has returned, so the task_cache shard lock is released before+            // cache tracking or aggregation updates can re-enter the backend.+            if created {+                self.track_cache_miss_by_fn(native_fn);+                // Update the aggregation number before connecting the child. We don't need this on+                // recovery paths because the aggregation number will already be set.+                if is_root {+                    AggregationUpdateQueue::run(+                        AggregationUpdateJob::UpdateAggregationNumber {+                            task_id,+                            base_aggregation_number: u32::MAX,+                            distance: None,+                        },+                        &mut ctx,+                    );+                } else if native_fn.is_session_dependent && self.should_track_dependencies() {+                    const SESSION_DEPENDENT_AGGREGATION_NUMBER: u32 = u32::MAX >> 2;+                    AggregationUpdateQueue::run(+                        AggregationUpdateJob::UpdateAggregationNumber {+                            task_id,+                            base_aggregation_number: SESSION_DEPENDENT_AGGREGATION_NUMBER,+                            distance: None,+                        },+                        &mut ctx,+                    );                 }+            } else {+                self.track_cache_hit_by_fn(native_fn);             }++            task_id         };          operation::ConnectChildOperation::run(parent_task, task_id, ctx);

@@ -9,8 +9,7 @@ use std::{     }, }; -use dashmap::SharedValue;-use hashbrown::raw::RawIntoIter;+use hashbrown::hash_table; use thread_local::ThreadLocal; use tracing::span::Id; use turbo_bincode::TurboBincodeBuffer;@@ -24,8 +23,8 @@ use crate::{     database::key_value_database::KeySpace,     utils::{         dash_map_drop_contents::drop_contents,-        dash_map_multi::{RefMut, get_multiple_mut},-        dash_map_raw_entry::{TryLockAndRemove, try_lock_and_remove},+        dash_map_entry::{TryLockAndRemove, try_lock_and_remove},+        dash_map_multi::{RefMut, get_disjoint_mut},     }, }; @@ -340,25 +339,18 @@ impl Storage {             let work = {                 let mut shard_guard = shard.write();                 if drain_entries {-                    // SAFETY: shard_guard outlives the iterator and we hold it for the whole scan.-                    for bucket in unsafe { shard_guard.iter() } {-                        // Read the key and modified flag, then drop the borrow before any erase.-                        // SAFETY: the guard outlives the bucket reference.-                        let (key, modified_task) = {-                            let (key, shared_value) = unsafe { bucket.as_ref() };-                            (*key, shared_value.get().flags.any_modified())-                        };+                    shard_guard.retain(|(key, task)| {+                        let modified_task = task.flags.any_modified();                         if modified_task {                             debug_assert!(                                 !key.is_transient(),                                 "found a modified transient task: {key:?}"                             );-                        } else {-                            // Unmodified entries are not part of the snapshot. Erase and free them-                            // now so the table we move out below holds only modified entries.-                            unsafe { shard_guard.erase(bucket) };                         }-                    }+                        // Unmodified entries are not part of the snapshot. Remove and free them+                        // now so the table we move out below holds only modified entries.+                        modified_task+                    });                     if shard_guard.is_empty() {                         // The shard held only unmodified entries, which we've now erased and freed.                         // No iterator is created for an empty shard.@@ -369,15 +361,12 @@ impl Storage {                     ShardWork::Drain(std::mem::take(&mut *shard_guard).into_iter())                 } else {                     let mut modified = Vec::with_capacity(modified_count as usize);-                    // SAFETY: shard_guard outlives the iterator and we hold it for the whole scan.-                    for bucket in unsafe { shard_guard.iter() } {-                        // SAFETY: the guard outlives the bucket reference.-                        let (key, shared_value) = unsafe { bucket.as_ref() };+                    for (key, task) in shard_guard.iter() {                         // Only check modified flags — transient tasks never have modified flags set                         // (track_modification guards against it), so this naturally excludes them.                         // new_task always comes with modified flags (set_persistent_task_type calls                         // track_modification), so any_modified() is sufficient.-                        if shared_value.get().flags.any_modified() {+                        if task.flags.any_modified() {                             debug_assert!(                                 !key.is_transient(),                                 "found a modified transient task: {key:?}"@@ -473,7 +462,7 @@ impl Storage {             let snap_shard = &snapshot_shards[shard_idx];              // Acquire in documented order: map first, snapshots second.-            let map_guard = map_shard.write();+            let mut map_guard = map_shard.write();             let mut snap_guard = snap_shard.write();              for (key, _) in snap_guard.drain() {@@ -482,11 +471,8 @@ impl Storage {                 // through `self.map.get_mut`, which would attempt to re-acquire this shard's                 // write lock and would also obscure the pairing.                 let hash = self.map.hasher().hash_one(key);-                if let Some(bucket) = map_guard.find(hash, |(k, _)| *k == key) {-                    // SAFETY: We hold `map_shard`'s write lock for the duration of this-                    // access, so the bucket pointer is valid and no other thread can alias it.-                    let (_, shared_value) = unsafe { bucket.as_mut() };-                    self.promote_during_snapshot_flags(shared_value.get_mut(), shard_idx);+                if let Some((_, task)) = map_guard.find_mut(hash, |(k, _)| *k == key) {+                    self.promote_during_snapshot_flags(task, shard_idx);                 }             }             // If we are saving a non-trivial amount of memory just clear it out.@@ -523,7 +509,7 @@ impl Storage {         key1: TaskId,         key2: TaskId,     ) -> (StorageWriteGuard<'_>, StorageWriteGuard<'_>) {-        let (a, b) = get_multiple_mut(&self.map, key1, key2, || Box::new(TaskStorage::new()));+        let (a, b) = get_disjoint_mut(&self.map, key1, key2, || Box::new(TaskStorage::new()));         (             StorageWriteGuard {                 storage: self,@@ -579,21 +565,18 @@ impl Storage {             // avoid a lock cycle with get_or_create_persistent_task, which takes task_cache             // before map. Allocated lazily on first conflict.             let mut deferred_task_cache_removals: Vec<CachedTaskTypeArc> = Vec::new();-            // SAFETY: We hold the write lock for the duration of iteration.-            for bucket in unsafe { shard.iter() } {-                // SAFETY: The write lock guard outlives the bucket reference.-                let (task_id, task) = unsafe { bucket.as_mut() };+            shard.retain(|(task_id, task)| {                 if task_id.is_transient() {                     evicted.unevictable_reasons[UnevictableReason::Transient.index()] += 1;-                    continue;+                    return true;                 }-                let (key_evictability, value_evictability) = task.get().evictability();+                let (key_evictability, value_evictability) = task.evictability();                 match key_evictability {                     KeyEvictability::Evictable => {                         // The task type is persisted to backing storage (new_task = false),                         // so task_cache is a pure perf cache. Remove it now; it will be                         // re-populated by task_by_type() on the next cache miss.-                        let task_type = task.get().get_persistent_task_type().unwrap();+                        let task_type = task.get_persistent_task_type().unwrap();                         // Only try to acquire the lock, if we cannot just remove at the end                         // Because `get_or_create_task` acquires 'task_cache' then `storage.map` and                         // we do the opposite we need to be defensive here.  Attempting here is just@@ -616,12 +599,10 @@ impl Storage {                 }                 match value_evictability {                     ValueEvictability::Evictable { meta, data } => {-                        match task.get_mut().drop_partial(data, meta) {+                        match task.drop_partial(data, meta) {                             DropPartialOutcome::Empty => {-                                unsafe {-                                    shard.erase(bucket);-                                }                                 evicted.full += 1;+                                return false;                             }                             DropPartialOutcome::HasResidue => {                                 if data && meta {@@ -639,7 +620,8 @@ impl Storage {                         evicted.unevictable_reasons[reason.index()] += 1;                     }                 }-            }+                true+            });             // Shrink the shard if it's less than half full, to reclaim slack capacity             // after bulk evictions. We already hold the write lock, so this is free             // from a locking perspective. TaskId hashing is cheap (it's just an integer).@@ -924,7 +906,7 @@ enum ShardWork {     /// (modified-only) shard table out of the map. The iterator owns that table and drains it     /// directly, freeing each task box as it is serialized. No second map lookup, no flag     /// bookkeeping (the whole map is discarded right after this snapshot).-    Drain(RawIntoIter<(TaskId, SharedValue<Box<TaskStorage>>)>),+    Drain(hash_table::IntoIter<(TaskId, Box<TaskStorage>)>), }  pub struct SnapshotShard<'l, P> {@@ -1008,7 +990,6 @@ where                 // bookkeeping the normal path does, since the entire map is discarded right after                 // this snapshot.                 let (task_id, inner) = entries.next()?;-                let inner = inner.into_inner();                 Some(serialize_task(task_id, &inner))                 // we don't need to update any bits because everything is getting dropped.             }

@@ -0,0 +1,97 @@+use std::hash::{BuildHasher, Hash};++use crossbeam_utils::CachePadded;+use dashmap::{DashMap, RwLock};+use hashbrown::{HashTable, hash_table};++/// The type of a single shard inside a [`DashMap`].+///+/// `dashmap::HashMap<K, V>` is a private alias for `HashTable<(K, V)>`.+pub type Shard<K, V> = CachePadded<RwLock<HashTable<(K, V)>>>;++/// Returns a reference to the shard that owns the given pre-computed hash,+/// without locking anything.+///+/// Pass the returned reference to [`get_in_shard`] and+/// [`with_entry_in_shard`] so that the shard is only located once even when a+/// read-lock miss is followed by a write-lock retry.+pub fn get_shard<K: Eq + Hash, V, S: BuildHasher + Clone>(+    map: &DashMap<K, V, S>,+    hash: u64,+) -> &Shard<K, V> {+    let idx = map.determine_shard(hash as usize);+    &map.shards()[idx]+}++/// Read-only heterogeneous lookup using a pre-located shard reference.+/// Returns `Some(value)` on hit, `None` on miss. Uses only a read lock.+pub fn get_in_shard<K: Eq + Hash, V: Copy>(+    shard: &Shard<K, V>,+    hash: u64,+    eq: impl Fn(&K) -> bool,+) -> Option<V> {+    let guard = shard.read();+    guard.find(hash, |(k, _v)| eq(k)).map(|(_k, v)| *v)+}++/// Runs `then` with the native Hashbrown entry for a pre-located DashMap shard.+///+/// The shard write lock is held only for the duration of `then`. The caller+/// controls the precise point where the entry is consumed and the lock is+/// released by returning from the closure.+pub fn with_entry_in_shard<K: Eq + Hash, V, S: BuildHasher + Clone, Q: ?Sized, R>(+    shard: &Shard<K, V>,+    map_hasher: &S,+    hash: u64,+    query: &mut Q,+    eq: impl Fn(&K, &Q) -> bool,+    then: impl FnOnce(hash_table::Entry<'_, (K, V)>, &mut Q) -> R,+) -> R {+    let mut guard = shard.write();+    let entry = guard.entry(+        hash,+        |(k, _v)| eq(k, query),+        |(k, _v)| map_hasher.hash_one(k),+    );+    then(entry, query)+}++/// Outcome of [`try_lock_and_remove`].+pub enum TryLockAndRemove {+    /// The shard lock was acquired and a matching entry was removed.+    Removed,+    /// The shard lock was acquired but no matching entry was present.+    NotFound,+    /// The shard lock was contended; the caller should retry later after releasing+    /// any other locks they are holding.+    WouldBlock,+}++/// Remove `key` from `map` without blocking on shard contention.+///+/// Intended for call sites that already hold another lock and want to avoid a+/// cyclic wait. On contention (`WouldBlock`), the caller is expected to defer the+/// removal and retry after dropping the other lock.+pub fn try_lock_and_remove<+    K: Eq + Hash + AsRef<Q>,+    V,+    Q: Eq + Hash + ?Sized,+    S: BuildHasher + Clone,+>(+    map: &DashMap<K, V, S>,+    key: &Q,+) -> TryLockAndRemove {+    let hasher = map.hasher();+    let hash = hasher.hash_one(key);+    let shard_idx = map.determine_shard(hash as usize);+    let Some(mut shard) = map.shards()[shard_idx].try_write() else {+        return TryLockAndRemove::WouldBlock;+    };+    match shard.find_entry(hash, |(k, _v)| k.as_ref() == key) {+        Ok(entry) => {+            entry.remove();+            TryLockAndRemove::Removed+        }+        Err(_) => TryLockAndRemove::NotFound,+    }+}

@@ -2,23 +2,25 @@ use std::{     hash::{BuildHasher, Hash},     marker::PhantomData,     ops::{Deref, DerefMut},+    ptr::NonNull,     sync::Arc, }; -use dashmap::{DashMap, RwLockWriteGuard, SharedValue};-use hashbrown::raw::{Bucket, RawTable};+use dashmap::{DashMap, RawRwLock};+use hashbrown::HashTable;+use parking_lot::lock_api::RwLockWriteGuard; -type RwLockWriteTableGuard<'a, K, V> = RwLockWriteGuard<'a, RawTable<(K, SharedValue<V>)>>;+type RwLockWriteTableGuard<'a, K, V> = RwLockWriteGuard<'a, RawRwLock, HashTable<(K, V)>>;  pub enum RefMut<'a, K, V> {     Base(dashmap::mapref::one::RefMut<'a, K, V>),     Simple {         _guard: RwLockWriteTableGuard<'a, K, V>,-        bucket: Bucket<(K, SharedValue<V>)>,+        entry: NonNull<(K, V)>,     },     Shared {         _guard: Arc<RwLockWriteTableGuard<'a, K, V>>,-        bucket: Bucket<(K, SharedValue<V>)>,+        entry: NonNull<(K, V)>,         // Ensures that RefMut is !Send, preventing holding RefMut across .await points in async         // code, which can cause deadlocks. See safety comment on `unsafe impl Sync for RefMut`         // below.@@ -34,13 +36,13 @@ pub enum RefMut<'a, K, V> { // while every other tokio worker piles up trying to take the same lock — leaving no thread free // to poll the parked future. Marking the type `!Send` makes the borrow checker reject those call // sites at compile time.-// SAFETY (Sync): `RefMut` contains a raw `Bucket` pointer into a `DashMap` shard's `RawTable`.+// SAFETY (Sync): `RefMut` contains a non-null pointer into a `DashMap` shard's `HashTable`. // Sharing `&RefMut` is safe because:-// - `Simple` variant: The `Bucket` is accessed under an exclusive `RwLockWriteGuard` on a single+// - `Simple` variant: The entry is accessed under an exclusive `RwLockWriteGuard` on a single //   shard. The guard provides exclusive access to all data in that shard.-// - `Shared` variant: The `Bucket` is accessed under an `Arc<RwLockWriteGuard>`. The-//   `get_multiple_mut` function asserts that bucket pointers do not alias, so each `RefMut` has-//   exclusive access to its bucket even when sharing a guard.+// - `Shared` variant: The entry is accessed under an `Arc<RwLockWriteGuard>`. The+//   `get_disjoint_mut` function validates that the keys differ before obtaining both references+//   through `HashTable::get_many_unchecked_mut`. // - `K: Sync + V: Sync` bounds ensure the key and value types are safe to share across threads. unsafe impl<K: Eq + Hash + Sync, V: Sync> Sync for RefMut<'_, K, V> {} @@ -60,28 +62,24 @@ impl<K: Eq + Hash, V> RefMut<'_, K, V> {     pub fn pair(&self) -> (&K, &V) {         match self {             RefMut::Base(r) => r.pair(),-            RefMut::Simple { bucket, .. } | RefMut::Shared { bucket, .. } => {-                // SAFETY:-                // - The bucket is still valid, as we're holding a write guard on the shard-                // - These bucket pointers are convertible to references-                //-                // https://doc.rust-lang.org/std/ptr/index.html#pointer-to-reference-conversion-                let entry = unsafe { bucket.as_ref() };-                (&entry.0, entry.1.get())+            RefMut::Simple { entry, .. } | RefMut::Shared { entry, .. } => {+                // SAFETY: The entry remains valid while the shard write guard is held.+                let entry = unsafe { entry.as_ref() };+                (&entry.0, &entry.1)             }         }     }      pub fn pair_mut(&mut self) -> (&K, &mut V) {         match self {             RefMut::Base(r) => r.pair_mut(),-            RefMut::Simple { bucket, .. } | RefMut::Shared { bucket, .. } => {+            RefMut::Simple { entry, .. } | RefMut::Shared { entry, .. } => {                 // SAFETY: Same as above in `pair`, plus aliasing is prevented via:                 // 1. The lifetime of `&mut self`.-                // 2. `Simple` values come from separate shards (no aliasing possible)-                // 3. `Shared` values are asserted in `get_multiple_mut` to have unique pointers-                let entry = unsafe { bucket.as_mut() };-                (&entry.0, entry.1.get_mut())+                // 2. `Simple` values come from separate shards (no aliasing possible).+                // 3. `Shared` values were validated as disjoint before the pointers were created.+                let entry = unsafe { entry.as_mut() };+                (&entry.0, &mut entry.1)             }         }     }@@ -110,7 +108,7 @@ where     } } -pub fn get_multiple_mut<K, V>(+pub fn get_disjoint_mut<K, V>(     map: &DashMap<K, V, impl BuildHasher + Clone>,     key1: K,     key2: K,@@ -135,49 +133,43 @@ where      let shards = map.shards();     if s1 == s2 {-        let mut guard = shards[s1].write();--        // we need to call `find_or_find_insert_slot` to avoid overwriting existing entries, but we-        // can't use the returned bucket until after we get `bucket2` (below)-        let _ = guard-            .find_or_find_insert_slot(h1, eq1, hash_entry)-            .unwrap_or_else(|slot| unsafe {-                // SAFETY: This slot was previously returned by `find_or_find_insert_slot`, and no-                // mutation of the table has occurred since that call.-                guard.insert_in_slot(h1, slot, (key1.clone(), SharedValue::new(insert_with())))-            });+        // Equal keys would resolve to a single entry below. This must be a release-mode assertion+        // because the unchecked lookup relies on it for memory safety.+        assert!(+            key1 != key2,+            "`get_disjoint_mut` was called with equal keys, which breaks mutable referencing rules"+        ); -        let bucket2 = guard-            .find_or_find_insert_slot(h2, eq2, hash_entry)-            .unwrap_or_else(|slot| unsafe {-                // SAFETY: See previous call above-                guard.insert_in_slot(h2, slot, (key2.clone(), SharedValue::new(insert_with())))-            });+        let mut guard = shards[s1].write(); -        // Getting `bucket2` might invalidate the bucket pointer of the first entry, *even if no-        // insert happens* as `RawTable::find_or_find_insert_slot` will *sometimes* resize the-        // table, as it unconditionally reserves space for a potential insertion.-        let bucket1 = guard.find(h1, eq1).expect(-            "failed to find bucket of previously inserted item, is the hash or eq implementation \-             incorrect?",-        );+        if guard.find(h1, eq1).is_none() {+            guard.insert_unique(h1, (key1.clone(), insert_with()), hash_entry);+        }+        if guard.find(h2, eq2).is_none() {+            guard.insert_unique(h2, (key2.clone(), insert_with()), hash_entry);+        } -        // this assertion is needed for memory safety reasons-        assert!(-            !std::ptr::eq(bucket1.as_ptr(), bucket2.as_ptr()),-            "`get_multiple_mut` was called with equal keys, which breaks mutable referencing rules"-        );+        // SAFETY: `key1 != key2` was asserted above. Since `K: Eq`, the two equality closures+        // cannot select the same entry, even when the hashes collide.+        let [entry1, entry2] =+            unsafe {+                guard.get_many_unchecked_mut([h1, h2], |index, entry| {+                    if index == 0 { eq1(entry) } else { eq2(entry) }+                })+            };+        let entry1 = NonNull::from(entry1.expect("the first entry was inserted above"));+        let entry2 = NonNull::from(entry2.expect("the second entry was inserted above"));          let guard = Arc::new(guard);         (             RefMut::Shared {                 _guard: guard.clone(),-                bucket: bucket1,+                entry: entry1,                 phantom: PhantomData,             },             RefMut::Shared {                 _guard: guard,-                bucket: bucket2,+                entry: entry2,                 phantom: PhantomData,             },         )@@ -197,27 +189,31 @@ where             }         }; -        let bucket1 = guard1-            .find_or_find_insert_slot(h1, eq1, hash_entry)-            .unwrap_or_else(|slot| unsafe {-                // SAFETY: See first insert_in_slot call-                guard1.insert_in_slot(h1, slot, (key1.clone(), SharedValue::new(insert_with())))-            });-        let bucket2 = guard2-            .find_or_find_insert_slot(h2, eq2, hash_entry)-            .unwrap_or_else(|slot| unsafe {-                // SAFETY: See first insert_in_slot call-                guard2.insert_in_slot(h2, slot, (key2.clone(), SharedValue::new(insert_with())))-            });+        if guard1.find(h1, eq1).is_none() {+            guard1.insert_unique(h1, (key1.clone(), insert_with()), hash_entry);+        }+        if guard2.find(h2, eq2).is_none() {+            guard2.insert_unique(h2, (key2.clone(), insert_with()), hash_entry);+        }+        let entry1 = NonNull::from(+            guard1+                .find_mut(h1, eq1)+                .expect("the first entry was inserted"),+        );+        let entry2 = NonNull::from(+            guard2+                .find_mut(h2, eq2)+                .expect("the second entry was inserted"),+        );          (             RefMut::Simple {                 _guard: guard1,-                bucket: bucket1,+                entry: entry1,             },             RefMut::Simple {                 _guard: guard2,-                bucket: bucket2,+                entry: entry2,             },         )     }@@ -250,7 +246,7 @@ mod tests {             for indices in indices {                 s.spawn(|| {                     for i in indices {-                        let (mut a, mut b) = get_multiple_mut(map, i, i + 1, || 0);+                        let (mut a, mut b) = get_disjoint_mut(map, i, i + 1, || 0);                         *a += 1;                         *b += 1;                     }

@@ -1,143 +0,0 @@-use std::hash::{BuildHasher, Hash};--use crossbeam_utils::CachePadded;-use dashmap::{DashMap, RwLock, RwLockWriteGuard, SharedValue};-use hashbrown::raw::{Bucket, InsertSlot, RawTable};--/// The type of a single shard inside a [`DashMap`].-///-/// `dashmap::HashMap<K, V>` is a private alias for `RawTable<(K, SharedValue<V>)>`.-pub type Shard<K, V> = CachePadded<RwLock<RawTable<(K, SharedValue<V>)>>>;--/// Returns a reference to the shard that owns the given pre-computed hash,-/// without locking anything.-///-/// Pass the returned reference to [`raw_get_in_shard`] and-/// [`raw_entry_in_shard`] so that the shard is only located once even when a-/// read-lock miss is followed by a write-lock retry.-pub fn get_shard<K: Eq + Hash, V, S: BuildHasher + Clone>(-    map: &DashMap<K, V, S>,-    hash: u64,-) -> &Shard<K, V> {-    let idx = map.determine_shard(hash as usize);-    &map.shards()[idx]-}--/// Read-only heterogeneous lookup using a pre-located shard reference.-/// Returns `Some(value)` on hit, `None` on miss. Uses only a read lock.-pub fn raw_get_in_shard<K: Eq + Hash, V: Copy>(-    shard: &Shard<K, V>,-    hash: u64,-    eq: impl Fn(&K) -> bool,-) -> Option<V> {-    let guard = shard.read();-    // Safety: We have a read lock on the shard.-    guard-        .find(hash, |(k, _v)| eq(k))-        .map(|bucket| *unsafe { bucket.as_ref() }.1.get())-}--/// Write-lock entry lookup using a pre-located shard reference and-/// heterogeneous equality.-///-/// Takes a pre-located `shard` (from [`get_shard`]) and `hash` so the shard is-/// not located a second time on a read-miss / write-retry path.-pub fn raw_entry_in_shard<'l, K: Eq + Hash, V, S: BuildHasher + Clone>(-    shard: &'l Shard<K, V>,-    map_hasher: &S,-    hash: u64,-    eq: impl Fn(&K) -> bool,-) -> RawEntry<'l, K, V> {-    let mut guard = shard.write();-    let result =-        guard.find_or_find_insert_slot(hash, |(k, _v)| eq(k), |(k, _v)| map_hasher.hash_one(k));-    match result {-        Ok(bucket) => RawEntry::Occupied(OccupiedEntry {-            bucket,-            shard: guard,-        }),-        Err(insert_slot) => RawEntry::Vacant(VacantEntry {-            hash,-            insert_slot,-            shard: guard,-        }),-    }-}--/// Outcome of [`try_lock_and_remove`].-pub enum TryLockAndRemove {-    /// The shard lock was acquired and a matching entry was removed.-    Removed,-    /// The shard lock was acquired but no matching entry was present.-    NotFound,-    /// The shard lock was contended; the caller should retry later after releasing-    /// any other locks they are holding.-    WouldBlock,-}--/// Remove `key` from `map` without blocking on shard contention.-///-/// Intended for call sites that already hold another lock and want to avoid a-/// cyclic wait. On contention (`WouldBlock`), the caller is expected to defer the-/// removal and retry after dropping the other lock.-pub fn try_lock_and_remove<-    K: Eq + Hash + AsRef<Q>,-    V,-    Q: Eq + Hash + ?Sized,-    S: BuildHasher + Clone,->(-    map: &DashMap<K, V, S>,-    key: &Q,-) -> TryLockAndRemove {-    let hasher = map.hasher();-    let hash = hasher.hash_one(key);-    let shard_idx = map.determine_shard(hash as usize);-    let Some(mut shard) = map.shards()[shard_idx].try_write() else {-        return TryLockAndRemove::WouldBlock;-    };-    // SAFETY: we hold the write lock for the duration of the find/erase.-    match shard.find(hash, |(k, _v)| k.as_ref() == key) {-        Some(bucket) => {-            unsafe { shard.erase(bucket) };-            TryLockAndRemove::Removed-        }-        None => TryLockAndRemove::NotFound,-    }-}--pub enum RawEntry<'l, K, V> {-    Occupied(OccupiedEntry<'l, K, V>),-    Vacant(VacantEntry<'l, K, V>),-}--pub struct OccupiedEntry<'l, K, V> {-    bucket: Bucket<(K, SharedValue<V>)>,-    #[allow(dead_code, reason = "kept to ensure the lock lives long enough")]-    shard: RwLockWriteGuard<'l, RawTable<(K, SharedValue<V>)>>,-}--impl<'l, K, V> OccupiedEntry<'l, K, V> {-    pub fn get(&self) -> &V {-        // Safety: We have a write lock on the shard, so no other references to the value can-        // exist.-        unsafe { self.bucket.as_ref().1.get() }-    }-}--pub struct VacantEntry<'l, K, V> {-    hash: u64,-    insert_slot: InsertSlot,-    shard: RwLockWriteGuard<'l, RawTable<(K, SharedValue<V>)>>,-}--impl<'l, K, V> VacantEntry<'l, K, V> {-    pub fn insert(mut self, key: K, value: V) {-        let shared_value = SharedValue::new(value);-        // Safety: The insert slot is valid and the map has not been modified since we obtained it-        // (we hold the write lock).-        unsafe {-            self.shard-                .insert_in_slot(self.hash, self.insert_slot, (key, shared_value));-        }-    }-}

@@ -1,6 +1,6 @@ pub mod dash_map_drop_contents;+pub mod dash_map_entry; pub mod dash_map_multi;-pub mod dash_map_raw_entry; pub mod markdown_table; pub mod ptr_eq_arc; pub mod shard_amount;

@@ -19,7 +19,7 @@ bench = false anyhow = { workspace = true } either = { workspace = true } flate2 = { workspace = true }-hashbrown = { workspace = true, features = ["raw"] }+hashbrown = { workspace = true, features = ["raw-entry"] } indexmap = { workspace = true, features = ["serde"] } itertools = { workspace = true } postcard = { workspace = true }