fuchsia_rcu_collections/
rcu_raw_hash_map.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#![warn(unsafe_op_in_unsafe_fn)]
6
7use crate::rcu_array::RcuArray;
8use crate::rcu_intrusive_list::{
9    Link, RcuIntrusiveList, RcuIntrusiveListCursor, RcuListAdapter, rcu_list_adapter,
10};
11use crate::rcu_list::RcuList;
12use fuchsia_rcu::{RcuDroppable, RcuReadScope};
13use std::borrow::Borrow;
14use std::hash::{BuildHasher, Hash, Hasher};
15use std::sync::atomic::{AtomicUsize, Ordering};
16
17/// The initial capacity of the hash map.
18pub(crate) const INITIAL_CAPACITY: usize = 16;
19
20/// An entry in the hash table.
21#[derive(Debug, RcuDroppable)]
22struct Entry<K, V> {
23    /// The key for this entry.
24    key: K,
25
26    /// The value for this entry.
27    value: V,
28
29    /// The link to the next node in the collision chain for this bucket.
30    collision_chain: Link,
31
32    /// The link to the next node in the insertion chain for this bucket.
33    insertion_chain: Link,
34}
35
36impl<K, V> Entry<K, V> {
37    /// Create a new hash table entry.
38    fn new(key: K, value: V) -> Self {
39        Self {
40            key,
41            value,
42            collision_chain: Default::default(),
43            insertion_chain: Default::default(),
44        }
45    }
46}
47
48/// An RcuListAdapter for the collision chain.
49#[derive(Debug, RcuDroppable)]
50struct CollisionAdapter;
51
52impl<K, V> RcuListAdapter<Entry<K, V>> for CollisionAdapter {
53    rcu_list_adapter!(Entry<K, V>, collision_chain);
54}
55
56/// An RcuListAdapter for the insertion chain.
57#[derive(Debug, RcuDroppable)]
58struct InsertionAdapter;
59
60impl<K, V> RcuListAdapter<Entry<K, V>> for InsertionAdapter {
61    rcu_list_adapter!(Entry<K, V>, insertion_chain);
62}
63
64/// The result of inserting an entry into the map.
65pub enum InsertionResult<V> {
66    /// The entry was inserted.
67    ///
68    /// The number of entries in the map is returned.
69    Inserted(usize),
70
71    /// The entry was updated.
72    ///
73    /// The old value is returned.
74    Updated(V),
75}
76
77/// The bucket in the hash table.
78///
79/// Each bucket is a linked list to hold the collision chain.
80type Bucket<K, V> = RcuList<Entry<K, V>, CollisionAdapter>;
81
82/// A hash map that uses read-copy-update (RCU) to manage concurrent accesses.
83///
84/// By default, this map uses `rapidhash::RapidBuildHasher`, which provides high performance.
85/// However, if this map holds keys which may be attacker-controlled, consider using
86/// `std::collections::hash_map::RandomState` instead.
87#[derive(RcuDroppable)]
88pub struct RcuRawHashMap<K, V, S = rapidhash::RapidBuildHasher>
89where
90    K: Eq + Hash + Clone + RcuDroppable + Sync,
91    V: Clone + RcuDroppable + Sync,
92    S: BuildHasher + Send + Sync + 'static,
93{
94    /// The table of buckets.
95    table: RcuArray<Bucket<K, V>>,
96
97    /// The number of entries in the map.
98    num_entries: AtomicUsize,
99
100    /// The entries in this map in the order they were inserted.
101    insertion_chain: RcuIntrusiveList<Entry<K, V>, InsertionAdapter>,
102
103    /// The build hasher.
104    hash_builder: S,
105}
106
107impl<K, V> Default for RcuRawHashMap<K, V, rapidhash::RapidBuildHasher>
108where
109    K: Eq + Hash + Clone + RcuDroppable + Sync,
110    V: Clone + RcuDroppable + Sync,
111{
112    fn default() -> Self {
113        Self::with_capacity_and_hasher(0, rapidhash::RapidBuildHasher::default())
114    }
115}
116
117impl<K, V> RcuRawHashMap<K, V, rapidhash::RapidBuildHasher>
118where
119    K: Eq + Hash + Clone + RcuDroppable + Sync,
120    V: Clone + RcuDroppable + Sync,
121{
122    /// Creates a new hash map with the given capacity.
123    pub fn with_capacity(capacity: usize) -> Self {
124        Self::with_capacity_and_hasher(capacity, rapidhash::RapidBuildHasher::default())
125    }
126}
127
128impl<K, V, S> RcuRawHashMap<K, V, S>
129where
130    K: Eq + Hash + Clone + RcuDroppable + Sync,
131    V: Clone + RcuDroppable + Sync,
132    S: BuildHasher + Send + Sync + 'static,
133{
134    /// Creates a new hash map with the given capacity and hasher.
135    pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self {
136        let mut table = Vec::new();
137        table.resize_with((capacity + 1) / 2, Default::default);
138        Self {
139            table: RcuArray::from(table),
140            num_entries: AtomicUsize::new(0),
141            insertion_chain: Default::default(),
142            hash_builder,
143        }
144    }
145
146    /// Creates a new hash map with the given hasher.
147    pub fn with_hasher(hash_builder: S) -> Self {
148        Self::with_capacity_and_hasher(0, hash_builder)
149    }
150
151    /// Returns the hash of the key as a u64.
152    fn hash_key<Q>(&self, key: &Q) -> u64
153    where
154        Q: ?Sized + Hash,
155    {
156        let mut hasher = self.hash_builder.build_hasher();
157        key.hash(&mut hasher);
158        hasher.finish()
159    }
160
161    /// Returns the bucket for the given key in the given table.
162    fn get_bucket<'a, Q>(&self, table: &'a [Bucket<K, V>], key: &Q) -> &'a Bucket<K, V>
163    where
164        K: Borrow<Q>,
165        Q: ?Sized + Hash,
166    {
167        let hash = self.hash_key(key);
168        let index = hash as usize % table.len();
169        &table[index]
170    }
171
172    /// Returns a reference to the bucket for the given key.
173    fn read_bucket<'a, Q>(&self, scope: &'a RcuReadScope, key: &Q) -> Option<&'a Bucket<K, V>>
174    where
175        K: Borrow<Q>,
176        Q: ?Sized + Hash,
177    {
178        let table = self.table.as_slice(scope);
179        if table.is_empty() {
180            return None;
181        }
182        Some(self.get_bucket(table, key))
183    }
184
185    /// Returns a reference to the value corresponding to the key.
186    ///
187    /// Another thread running concurrently might see a different value for the object.
188    pub fn get<'a, Q>(&self, scope: &'a RcuReadScope, key: &Q) -> Option<&'a V>
189    where
190        K: Borrow<Q>,
191        Q: ?Sized + Hash + Eq,
192    {
193        let bucket = self.read_bucket(scope, key)?;
194        bucket.iter(scope).find(|entry| entry.key.borrow() == key).map(|entry| &entry.value)
195    }
196
197    /// Returns the number of entries in the map.
198    ///
199    /// The length can change concurrently with this call.
200    pub fn len(&self) -> usize {
201        self.num_entries.load(Ordering::Relaxed)
202    }
203
204    /// Inserts a key-value pair into the map.
205    ///
206    /// If the map did not have this key present, `None` is returned.
207    ///
208    /// If the map did have this key present, the value is updated, and the old
209    /// value is returned.
210    ///
211    /// Concurrent readers might not see the inserted value until the RCU state machine has made
212    /// sufficient progress to ensure that no concurrent readers are holding read guards.
213    ///
214    /// # Safety
215    ///
216    /// Requires external synchronization to exclude concurrent writers.
217    pub unsafe fn insert(&self, scope: &RcuReadScope, key: K, value: V) -> InsertionResult<V> {
218        let mut table = self.table.as_slice(scope);
219        if self.needs_to_grow(table) {
220            // SAFETY: Our caller is required to use external synchronization to exclude concurrent
221            // writers.
222            table = unsafe { self.grow(&scope, table) };
223        }
224        let bucket = self.get_bucket(table, &key);
225        let mut cursor = bucket.cursor(&scope);
226        while let Some(entry) = cursor.current() {
227            if entry.key == key {
228                let old_value = entry.value.clone();
229                // SAFETY: We have exclusive access to the bucket because we have exclusive access
230                // to the table.
231                unsafe {
232                    let removed_entry = cursor.remove();
233                    self.insertion_chain.remove(&scope, removed_entry);
234                    let entry = bucket.push_front(&scope, Entry::new(key, value));
235                    self.insertion_chain.push_back(&scope, entry);
236                };
237                return InsertionResult::Updated(old_value);
238            }
239            cursor.advance();
240        }
241
242        // SAFETY: We have exclusive access to the bucket because we have exclusive access to the
243        // table.
244        unsafe {
245            let entry = bucket.push_front(&scope, Entry::new(key, value));
246            self.insertion_chain.push_back(&scope, entry);
247        }
248        let count = self.num_entries.fetch_add(1, Ordering::Relaxed);
249        InsertionResult::Inserted(count + 1)
250    }
251
252    /// Removes a key from the map, returning the value at the key if the key
253    /// was previously in the map.
254    ///
255    /// Concurrent readers might see the removed value until the RCU state machine has made
256    /// sufficient progress to ensure that no concurrent readers are holding read guards.
257    ///
258    /// # Safety
259    ///
260    /// Requires external synchronization to exclude concurrent writers.
261    pub unsafe fn remove<Q>(&self, key: &Q) -> Option<V>
262    where
263        K: Borrow<Q>,
264        Q: ?Sized + Hash + Eq,
265    {
266        let scope = RcuReadScope::new();
267        let bucket = self.read_bucket(&scope, key)?;
268        let mut cursor = bucket.cursor(&scope);
269        while let Some(entry) = cursor.current() {
270            if entry.key.borrow() == key {
271                let old_value = entry.value.clone();
272                // SAFETY: We have exclusive access to the bucket because we have exclusive access
273                // to the table.
274                unsafe {
275                    let removed_entry = cursor.remove();
276                    self.insertion_chain.remove(&scope, removed_entry);
277                };
278                self.num_entries.fetch_sub(1, Ordering::Relaxed);
279                return Some(old_value);
280            }
281            cursor.advance();
282        }
283        None
284    }
285
286    /// Whether the given table needs to grow to reduce the number of collisions.
287    fn needs_to_grow(&self, table: &[Bucket<K, V>]) -> bool {
288        table.is_empty() || self.num_entries.load(Ordering::Relaxed) > table.len() * 2
289    }
290
291    /// Grows the table to reduce the number of collisions.
292    ///
293    /// Returns a reference to the new table. Callers should be sure to update the table reference
294    /// they are using to the returned value.
295    ///
296    /// # Safety
297    ///
298    /// Requires external synchronization to exclude concurrent writers.
299    #[must_use]
300    unsafe fn grow<'a>(
301        &self,
302        scope: &'a RcuReadScope,
303        old_table: &[Bucket<K, V>],
304    ) -> &'a [Bucket<K, V>] {
305        let new_size = if old_table.is_empty() { INITIAL_CAPACITY } else { old_table.len() * 2 };
306        let mut new_table = Vec::new();
307        let new_insertion_chain = RcuIntrusiveList::default();
308        new_table.resize_with(new_size, Default::default);
309
310        for entry in self.insertion_chain.iter(scope) {
311            let bucket = self.get_bucket(&new_table, &entry.key);
312            let key = entry.key.clone();
313            let value = entry.value.clone();
314            // SAFETY: We have exclusive access to new_table_vec because we just created it.
315            unsafe {
316                let entry = bucket.push_front(&scope, Entry::new(key, value));
317                new_insertion_chain.push_back(&scope, entry);
318            };
319        }
320
321        self.table.update(new_table);
322        // SAFETY: Our caller promises to exclude concurrent writers.
323        unsafe {
324            self.insertion_chain.update(&scope, new_insertion_chain);
325        }
326        self.table.as_slice(scope)
327    }
328
329    /// Returns true if the map contains no entries.
330    pub fn is_empty(&self) -> bool {
331        self.len() == 0
332    }
333
334    /// Removes all entries from the map.
335    ///
336    /// Concurrent readers holding an active `RcuReadScope` continue to observe a consistent snapshot
337    /// of the previous bucket table until the RCU grace period completes and `rcu_drop` reclaims the
338    /// retired bucket array and entry nodes.
339    ///
340    /// # Safety
341    ///
342    /// Requires external synchronization to exclude concurrent writers.
343    pub unsafe fn clear(&self) {
344        // SAFETY: Caller guarantees exclusive writer access. `self.table` retains ownership of the
345        // entry allocations until `self.table.update(Vec::new())` below.
346        unsafe {
347            self.insertion_chain.clear(&RcuReadScope::new(), |_| {});
348        }
349        self.table.update(Vec::new());
350        self.num_entries.store(0, Ordering::Relaxed);
351    }
352
353    /// Returns a cursor that can be used to traverse and modify the map.
354    ///
355    /// The cursor iterates through the map in insertion order.
356    pub fn cursor<'a>(&'a self, scope: &'a RcuReadScope) -> RcuRawHashMapCursor<'a, K, V, S> {
357        RcuRawHashMapCursor { inner: self.insertion_chain.cursor(scope), map: self }
358    }
359
360    /// Returns an iterator over the key-value pairs in the map in insertion order.
361    pub fn iter<'a>(&'a self, scope: &'a RcuReadScope) -> impl Iterator<Item = (&'a K, &'a V)> {
362        self.insertion_chain.iter(scope).map(|entry| (&entry.key, &entry.value))
363    }
364
365    /// Returns an iterator over the keys in the map.
366    pub fn keys<'a>(&'a self, scope: &'a RcuReadScope) -> impl Iterator<Item = &'a K> {
367        self.insertion_chain.iter(scope).map(|entry| &entry.key)
368    }
369
370    /// Returns an iterator over the values in the map.
371    pub fn values<'a>(&'a self, scope: &'a RcuReadScope) -> impl Iterator<Item = &'a V> {
372        self.insertion_chain.iter(scope).map(|entry| &entry.value)
373    }
374}
375
376// TODO(https://fxbug.dev/482462174): switch back to #[derive(Debug)]
377impl<K, V, S> std::fmt::Debug for RcuRawHashMap<K, V, S>
378where
379    K: Eq + Hash + Clone + RcuDroppable + Sync + std::fmt::Debug,
380    V: Clone + RcuDroppable + Sync + std::fmt::Debug,
381    S: std::hash::BuildHasher + Send + Sync + 'static,
382{
383    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
384        f.debug_struct("RcuRawHashMap")
385            .field("table", &self.table)
386            .field("num_entries", &self.num_entries)
387            .field("insertion_chain", &self.insertion_chain)
388            .field("hash_builder", &std::any::type_name::<S>())
389            .finish_non_exhaustive()
390    }
391}
392
393/// A cursor for traversing and modifying an `RcuRawHashMap`.
394///
395/// See `RcuRawHashMap::cursor` for more information.
396pub struct RcuRawHashMapCursor<'a, K, V, S = rapidhash::RapidBuildHasher>
397where
398    K: Eq + Hash + Clone + RcuDroppable + Sync,
399    V: Clone + RcuDroppable + Sync,
400    S: BuildHasher + Send + Sync + 'static,
401{
402    inner: RcuIntrusiveListCursor<'a, Entry<K, V>, InsertionAdapter>,
403    map: &'a RcuRawHashMap<K, V, S>,
404}
405
406impl<'a, K, V, S> RcuRawHashMapCursor<'a, K, V, S>
407where
408    K: Eq + Hash + Clone + RcuDroppable + Sync,
409    V: Clone + RcuDroppable + Sync,
410    S: BuildHasher + Send + Sync + 'static,
411{
412    /// Returns the element at the current cursor position.
413    pub fn current(&self) -> Option<(&'a K, &'a V)> {
414        self.inner.current().map(|entry| (&entry.key, &entry.value))
415    }
416
417    /// Advances the cursor to the next element in the list.
418    pub fn advance(&mut self) {
419        self.inner.advance()
420    }
421
422    /// Removes the element at the current cursor position.
423    ///
424    /// After calling `remove`, the cursor will be positioned at the next element in the list.
425    ///
426    /// Concurrent readers may continue to see this entry in the list until the RCU state machine
427    /// has made sufficient progress to ensure that no concurrent readers are holding read guards.
428    ///
429    /// # Safety
430    ///
431    /// Requires external synchronization to exclude concurrent writers.
432    pub unsafe fn remove(&mut self) -> Option<V> {
433        if let Some((key, _)) = self.current() {
434            self.advance();
435            // SAFETY: The caller promises to exclude concurrent writers.
436            unsafe { self.map.remove(key) }
437        } else {
438            None
439        }
440    }
441}
fuchsia_rcu_collections/rcu_raw_hash_map.rs

fuchsia_rcu_collections/
rcu_raw_hash_map.rs
