kovan_map/hashmap/resize.rs
1//! Replacing the table: a resize copies it into a table of another capacity, a clear replaces it
2//! by an empty one. Both take the single resizer latch, freeze every link of the old table in
3//! chain order (copying, for a resize, each node that is not deleted), and publish the new table
4//! with the exact count of what it holds.
5//!
6//! Freezing is what makes a write final: every write is one CAS on one link, and a frozen link
7//! fails every CAS a writer makes (it expects the word without the flag). A write whose CAS
8//! landed before the freeze reached its link is in the chain the copy reads; a write that meets
9//! a frozen link waits for the new table and writes there. No write lands in a table after its
10//! copy read the link, so no landed write is lost and none is retried: an insert that landed
11//! never meets its own copy and never reports it as another caller's entry, and a remove never
12//! removes a copy of what it already removed. Modelled in `tla/chained/ChainedMap.tla` (actions
13//! Z0 to Z6), where 0.1.20's read-then-revalidate protocol (Mutation "revalidate") breaks both.
14
15use super::node::{FROZEN, Node, is_frozen, is_marked, ptr, with, word};
16use super::table::TableRef;
17use super::{HashMap, MIN_CAPACITY};
18use crate::sync::spin_hint;
19use alloc::boxed::Box;
20use core::hash::{BuildHasher, Hash};
21use core::sync::atomic::Ordering;
22use kovan::{Atomic, Guard, Shared, pin, retire};
23
24extern crate alloc;
25
26impl<K, V, S> HashMap<K, V, S>
27where
28 K: Hash + Eq + Clone + 'static,
29 V: Clone + 'static,
30 S: BuildHasher,
31{
32 /// Spin until the resize or clear in flight has published its table (a writer that met a
33 /// frozen link, its guard dropped).
34 #[inline]
35 pub(super) fn wait_for_resize(&self) {
36 while self.resizing.load(Ordering::Acquire) {
37 spin_hint();
38 }
39 }
40
41 /// Resize the table to `new_capacity` buckets (the single resizer wins; a call that finds
42 /// the latch taken returns at once).
43 pub(super) fn try_resize(&self, new_capacity: usize) {
44 if self
45 .resizing
46 .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
47 .is_err()
48 {
49 return;
50 }
51 let new_capacity = new_capacity
52 .next_power_of_two()
53 .max(MIN_CAPACITY)
54 .max(self.floor);
55 let guard = pin();
56 let old = self.table_ref(&guard);
57 if old.capacity() != new_capacity {
58 let new = TableRef::alloc(new_capacity);
59 let copied = Self::migrate(old, Some(new), &guard);
60 // Relaxed: the table's publication below releases it.
61 new.count().store(copied as isize, Ordering::Relaxed);
62 self.publish(old, new);
63 }
64 drop(guard);
65 self.resizing.store(false, Ordering::Release);
66 }
67
68 /// Clears the map, removing all key-value pairs.
69 ///
70 /// Linearizes when the empty table is published: a write that landed before its link was
71 /// frozen is cleared, a write that met a frozen link lands in the empty table after.
72 pub fn clear(&self) {
73 while self
74 .resizing
75 .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
76 .is_err()
77 {
78 spin_hint();
79 }
80 let guard = pin();
81 let old = self.table_ref(&guard);
82 Self::migrate(old, None, &guard);
83 self.publish(old, TableRef::alloc(old.capacity()));
84 drop(guard);
85 self.resizing.store(false, Ordering::Release);
86 }
87
88 /// Freeze `link` and return its frozen word.
89 fn freeze(link: &Atomic<Node<K, V>>, guard: &Guard) -> *mut Node<K, V> {
90 loop {
91 // A word a failed CAS returns is reloaded here rather than used: only a load
92 // protects the node it names.
93 let w = link.load(Ordering::Acquire, guard).as_raw();
94 if is_frozen(w) {
95 return w;
96 }
97 let frozen = with(w, FROZEN);
98 // AcqRel: the copy below reads the fields of the node the word names.
99 if link
100 .compare_exchange(
101 word(w),
102 word(frozen),
103 Ordering::AcqRel,
104 Ordering::Relaxed,
105 guard,
106 )
107 .is_ok()
108 {
109 return frozen;
110 }
111 }
112 }
113
114 /// Freeze every link of `old`, bucket by bucket in chain order, and copy each node that is
115 /// not deleted into `into` (a table no other thread sees yet). Returns the number copied.
116 fn migrate(old: TableRef<K, V>, into: Option<TableRef<K, V>>, guard: &Guard) -> usize {
117 let mut copied = 0;
118 for b in 0..old.capacity() {
119 let mut w = Self::freeze(old.bucket(b), guard);
120 loop {
121 let cur = ptr(w);
122 if cur.is_null() {
123 break;
124 }
125 // SAFETY: the frozen link that names it named it when this thread froze it, and
126 // a frozen link never changes, so it stays reachable (never retired) from here.
127 let node = unsafe { &*cur };
128 w = Self::freeze(&node.next, guard);
129 if is_marked(w) {
130 continue;
131 }
132 if let Some(new) = into {
133 let dst = new.bucket(new.bucket_index(node.hash));
134 let copy = Node::new(node.hash, node.key.clone(), node.value.clone());
135 // Relaxed: `new` is private to this thread until its publication releases it.
136 copy.next
137 .store(dst.load(Ordering::Relaxed, guard), Ordering::Relaxed);
138 dst.store(word(Box::into_raw(Box::new(copy))), Ordering::Relaxed);
139 copied += 1;
140 }
141 }
142 }
143 copied
144 }
145
146 /// Make `new` the current table and retire `old`, every link of which is frozen.
147 fn publish(&self, old: TableRef<K, V>, new: TableRef<K, V>) {
148 // Release: a thread that acquires the new table sees its buckets, nodes and count.
149 // SAFETY: `new` is a live table allocation.
150 self.table
151 .store(unsafe { Shared::from_raw(new.as_raw()) }, Ordering::Release);
152 // SAFETY: the old table is unreachable from the map now; kovan frees it (and the nodes
153 // its frozen chains hold) once no guard that loaded it remains. TableProxy is
154 // #[repr(C)] with its RetiredNode at offset 0.
155 unsafe { retire(old.take_proxy()) };
156 }
157}