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 `proofs/tla/chained/ChainedMap.tla`
13//! (actions Z0 to Z6), where 0.1.20's read-then-revalidate protocol (Mutation "revalidate")
14//! breaks both.
15
16use super::node::{FROZEN, Node, is_frozen, is_held, is_marked, ptr, with, word};
17use super::table::TableRef;
18use super::{HashMap, MIN_CAPACITY};
19use crate::sync::spin_hint;
20use core::hash::{BuildHasher, Hash};
21use core::sync::atomic::Ordering;
22use kovan::{Atomic, Guard, Shared, alloc_node, pin, retire_node};
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. A held link is waited for: only its holder
89 /// writes it, and the conditional write holding it lands in this table before the link
90 /// freezes (so the copy reads it).
91 fn freeze(link: &Atomic<Node<K, V>>, guard: &Guard) -> *mut Node<K, V> {
92 loop {
93 // A word a failed CAS returns is reloaded here rather than used: only a load
94 // protects the node it names.
95 let w = link.load(Ordering::Acquire, guard).as_raw();
96 if is_frozen(w) {
97 return w;
98 }
99 if is_held(w) {
100 spin_hint();
101 continue;
102 }
103 let frozen = with(w, FROZEN);
104 // AcqRel: the copy below reads the fields of the node the word names.
105 if link
106 .compare_exchange(
107 word(w),
108 word(frozen),
109 Ordering::AcqRel,
110 Ordering::Relaxed,
111 guard,
112 )
113 .is_ok()
114 {
115 return frozen;
116 }
117 }
118 }
119
120 /// Freeze every link of `old`, bucket by bucket in chain order, and copy each node that is
121 /// not deleted into `into` (a table no other thread sees yet). Returns the number copied.
122 fn migrate(old: TableRef<K, V>, into: Option<TableRef<K, V>>, guard: &Guard) -> usize {
123 let mut copied = 0;
124 for b in 0..old.capacity() {
125 let mut w = Self::freeze(old.bucket(b), guard);
126 loop {
127 let cur = ptr(w);
128 if cur.is_null() {
129 break;
130 }
131 // SAFETY: the frozen link that names it named it when this thread froze it, and
132 // a frozen link never changes, so it stays reachable (never retired) from here.
133 let node = unsafe { &*cur };
134 w = Self::freeze(&node.next, guard);
135 if is_marked(w) {
136 continue;
137 }
138 if let Some(new) = into {
139 let dst = new.bucket(new.bucket_index(node.hash));
140 let copy = Node::new(node.hash, node.key.clone(), node.value.clone());
141 // Relaxed: `new` is private to this thread until its publication releases it.
142 copy.next
143 .store(dst.load(Ordering::Relaxed, guard), Ordering::Relaxed);
144 dst.store(word(alloc_node(copy)), Ordering::Relaxed);
145 copied += 1;
146 }
147 }
148 }
149 copied
150 }
151
152 /// Make `new` the current table and retire `old`, every link of which is frozen.
153 fn publish(&self, old: TableRef<K, V>, new: TableRef<K, V>) {
154 // Release: a thread that acquires the new table sees its buckets, nodes and count.
155 // SAFETY: `new` is a live table allocation.
156 self.table
157 .store(unsafe { Shared::from_raw(new.as_raw()) }, Ordering::Release);
158 // SAFETY: the old table is unreachable from the map now; kovan frees it (and the nodes
159 // its frozen chains hold) once no guard that loaded it remains. TableProxy is
160 // #[repr(C)] with its RetiredNode at offset 0.
161 unsafe { retire_node(old.take_proxy()) };
162 }
163}