mergex/lib.rs
1//! A tree of per-thread slots that are folded lazily into their father.
2//!
3//! Writers only ever touch the node they own, so they never share a cache line;
4//! the aggregate is rebuilt on demand, when someone reads the root.
5//!
6//! # Contract
7//!
8//! `merge` and `identity` must form a commutative monoid over `T`:
9//!
10//! * **identity**: `merge(&mut x, &identity)` leaves `x` unchanged.
11//! * **associative** and **commutative**: sons are folded in an order that
12//! depends on thread scheduling, so any order must give the same answer.
13//!
14//! A node's data is the **delta not yet folded into its father**, not a local
15//! copy of the aggregate. A fresh son starts at `identity`, and a node is reset
16//! to `identity` as soon as its data has been folded upward.
17
18#![warn(missing_docs)]
19
20use std::mem;
21
22// The README's example is compiled and run as a doctest. It is the public API's
23// only prose description of itself, and it has drifted out of date before -- a
24// signature changed and the snippet kept claiming the old one.
25#[cfg(all(doctest, not(loom)))]
26#[doc = include_str!("../README.md")]
27struct ReadmeExamples;
28
29// Under `--cfg loom` the locks and the flags are rebuilt on loom's instrumented
30// primitives, so the model checker can drive every interleaving the memory
31// model allows. See tests/loom.rs.
32//
33// `Arc`/`Weak` stay on std: loom 0.7 has no `Weak` and its `Arc` cannot hold an
34// unsized `dyn Fn`, which is what `MergeFn` is. No loss for what is under test
35// here -- the protocol lives in the AtomicBools and the Mutexes, not in the
36// refcounts -- but it does mean loom is not watching the `Arc` graph, so it
37// will not catch a leaked cycle.
38#[cfg(loom)]
39use loom::sync::Mutex;
40#[cfg(loom)]
41use loom::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
42#[cfg(not(loom))]
43use std::sync::Mutex;
44#[cfg(not(loom))]
45use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
46use std::sync::Arc;
47
48/// Merge function: folds a son's data into its father's data.
49/// Must be associative and commutative; see the crate docs.
50pub type MergeFn<T> = Arc<dyn Fn(&mut T, &T) + Send + Sync>;
51
52/// The shared node. Never handed out directly: users get a `Mergex` handle.
53///
54/// Aligned to two cache lines: nodes are per-writer, so two of them landing on
55/// one line puts unrelated threads in a cache fight. Without this the write
56/// benchmark is bimodal, swinging 3x on allocator luck alone.
57#[repr(align(64))]
58struct Node<T> {
59 // There is deliberately no link back to the father. A dying node does not
60 // push its delta upward -- it leaves it where it is, and the father, which
61 // owns it, folds it on the next merge like any other son. That removes the
62 // two ways a hand-written flush loses data: forgetting the pending delta,
63 // and folding it from outside a merge walk, where `merge_sons` would not
64 // propagate it any further.
65 sons: Mutex<Vec<Arc<Node<T>>>>,
66 // live `Mergex` handles pointing here. `Arc::strong_count` cannot stand in:
67 // the father holds one, and `snapshot_sons` clones more for the duration of
68 // a merge, so it never settles.
69 handles: AtomicUsize,
70 // set once the last handle is gone. The node keeps its place, and whatever
71 // it still owes, until a merger folds it and reaps it.
72 dead: AtomicBool,
73 data: Mutex<T>,
74 dirty: AtomicBool, // if true means that it is not sync with father node
75 // conservative hint: true when some strict descendant may be dirty. Lets a
76 // clean subtree be skipped in O(1) instead of being walked son by son.
77 // Never a false negative, which is the only direction that would lose data.
78 subtree_dirty: Arc<AtomicBool>,
79 // the subtree_dirty flags of every ancestor, father first. Built once at
80 // copy() time so a write never has to upgrade a Weak: doing that per set
81 // is a CAS on the root's shared refcount from every writer at once.
82 ancestor_flags: Vec<Arc<AtomicBool>>,
83 // what a node holds when it has nothing pending for its father. Shared down
84 // from the root like `merge`, so every node of a tree agrees on it.
85 identity: Arc<T>,
86 merge: MergeFn<T>,
87}
88
89/// Handle to a node in the tree. Cloning (or moving one into a thread) shares
90/// the node, it does not copy it.
91///
92/// Except at the root, the data a node holds is the delta still owed to its
93/// father, not the aggregate: it goes back to `identity` every time it is
94/// folded upward.
95pub struct Mergex<T> {
96 node: Arc<Node<T>>,
97}
98
99impl<T> Clone for Mergex<T> {
100 fn clone(&self) -> Self {
101 self.node.handles.fetch_add(1, Ordering::Relaxed);
102 Mergex {
103 node: Arc::clone(&self.node),
104 }
105 }
106}
107
108impl<T> Drop for Mergex<T> {
109 /// Dropping the last handle only plants a tombstone. It cannot unlink the
110 /// node here: the node may still owe its father a delta, and only a merger
111 /// -- walking down from above, inside its own fold -- is in a position to
112 /// collect it. See `Node::reap`.
113 fn drop(&mut self) {
114 if self.node.handles.fetch_sub(1, Ordering::AcqRel) == 1 {
115 self.node.dead.store(true, Ordering::Release);
116 }
117 }
118}
119
120impl<T: std::fmt::Debug> std::fmt::Debug for Mergex<T> {
121 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
122 let sons: Vec<Mergex<T>> = self
123 .node
124 .sons
125 .lock()
126 .unwrap()
127 .iter()
128 .map(|n| Mergex { node: Arc::clone(n) })
129 .collect();
130 f.debug_struct("Mergex")
131 .field("data", &*self.node.data.lock().unwrap())
132 .field("dirty", &self.node.dirty.load(Ordering::Acquire))
133 .field("sons", &sons)
134 .finish()
135 }
136}
137
138impl<T: Clone> Mergex<T> {
139 /// Builds a root holding `data`.
140 ///
141 /// `identity` is the neutral element of `merge`: folding it into any value
142 /// must leave that value unchanged. Every node is reset to it once its data
143 /// has been folded into its father, which is what stops the same delta from
144 /// being counted twice by two successive reads.
145 pub fn new(data: T, identity: T, merge: impl Fn(&mut T, &T) + Send + Sync + 'static) -> Self {
146 Mergex {
147 node: Arc::new(Node {
148 sons: Mutex::new(vec![]),
149 handles: AtomicUsize::new(1),
150 dead: AtomicBool::new(false),
151 data: Mutex::new(data),
152 dirty: AtomicBool::new(false),
153 subtree_dirty: Arc::new(AtomicBool::new(false)),
154 ancestor_flags: vec![],
155 identity: Arc::new(identity),
156 merge: Arc::new(merge),
157 }),
158 }
159 }
160
161 /// Registers a new son and returns its handle. Move it into a thread.
162 ///
163 /// The son starts at `identity`: it owes its father nothing yet. Seeding it
164 /// with a value instead would be a write nobody ever asked for, and would
165 /// land in the aggregate the first time any of its own sons was folded.
166 pub fn copy(&self) -> Self {
167 let son = Arc::new(Node {
168 sons: Mutex::new(vec![]),
169 handles: AtomicUsize::new(1),
170 dead: AtomicBool::new(false),
171 data: Mutex::new((*self.node.identity).clone()),
172 dirty: AtomicBool::new(false),
173 subtree_dirty: Arc::new(AtomicBool::new(false)),
174 ancestor_flags: {
175 let mut f = Vec::with_capacity(self.node.ancestor_flags.len() + 1);
176 f.push(Arc::clone(&self.node.subtree_dirty));
177 f.extend(self.node.ancestor_flags.iter().cloned());
178 f
179 },
180 identity: Arc::clone(&self.node.identity),
181 merge: Arc::clone(&self.node.merge),
182 });
183 self.node.sons.lock().unwrap().push(Arc::clone(&son));
184 Mergex { node: son }
185 }
186
187 /// Overwrites this node's data and marks it out of sync with its father.
188 pub fn set(&self, data: T) {
189 self.update(|slot| *slot = data);
190 }
191
192 /// Read-modify-writes this node's data under a single lock and marks it out
193 /// of sync with its father. `set` is this with a closure that overwrites.
194 pub fn update(&self, f: impl FnOnce(&mut T)) {
195 // the dirty flag is raised while still holding the data lock, so a
196 // concurrent merge can never clear it in between and swallow the write
197 let mut guard = self.node.data.lock().unwrap();
198 f(&mut guard);
199 // A plain load and store, not a read-modify-write: `dirty` is only ever
200 // *written* under this data lock -- by `update` here, and by the merge
201 // that clears it -- so holding the lock already makes the pair atomic
202 // against everyone who could change it. The one unlocked reader,
203 // `merge_sons`' fast path, only loads. The old value says whether this
204 // node already owed its father something.
205 let was_dirty = self.node.dirty.load(Ordering::Relaxed);
206 self.node.dirty.store(true, Ordering::Release);
207 drop(guard);
208
209 // Walking up is what costs: `mark_ancestors` takes a line shared by
210 // every writer in the subtree, exclusively. Skipping it when the bit was
211 // already up turns a burst of writes on one node into a single walk,
212 // which is the difference between a per-write shared RMW and a
213 // per-fold one -- roughly a factor of ten under eight writers.
214 //
215 // Sound because a merge clears `dirty` under this same data lock. So
216 // `was_dirty` true means no merge has folded this node since the write
217 // that raised the bit, and that write is the one that flagged the
218 // ancestors: either it has finished doing so, or it is still on its way
219 // up, and its RMWs land in the same modification order the merger's
220 // clearing swap reads from. Nothing is left unflagged that a merge has
221 // already walked past.
222 if !was_dirty {
223 self.node.mark_ancestors();
224 }
225 }
226
227 /// This node's own data, with no merging. Away from the root that is the
228 /// delta still owed to the father, so it reads back as `identity` right
229 /// after a fold, not as everything this node has ever written.
230 pub fn get_threaded(&self) -> T {
231 self.node.data.lock().unwrap().clone()
232 }
233
234 /// Folds every dirty descendant into this node, deepest first, and returns
235 /// the result. Called on the root, that is the aggregate.
236 ///
237 /// When nothing below has changed this is a single atomic load, whatever
238 /// the size of the subtree. When several threads call it at once, one wins
239 /// the sweep and the others return what is currently there rather than
240 /// waiting -- so an individual call can be stale under concurrent readers,
241 /// though nothing is lost and a call on a quiet tree is exact.
242 ///
243 /// ```
244 /// # use mergex::Mergex;
245 /// let root = Mergex::new(10i64, 0, |f: &mut i64, s: &i64| *f += *s);
246 /// let son = root.copy();
247 /// son.set(5);
248 /// assert_eq!(root.get(), 15);
249 /// assert_eq!(root.get(), 15); // the delta is not folded twice
250 /// ```
251 pub fn get(&self) -> T {
252 self.node.merge_sons();
253 self.get_threaded()
254 }
255
256 /// Whether any descendant has something pending. `false` does not promise
257 /// that a `get` is free, only that no write is waiting to be folded.
258 ///
259 /// Costs one atomic load on a clean subtree, whatever its size.
260 pub fn check_children(&self) -> bool {
261 self.node.check_children()
262 }
263
264 /// Whether this node itself owes its father a delta.
265 pub fn check_dirty_bit(&self) -> bool {
266 self.node.dirty.load(Ordering::Acquire)
267 }
268}
269
270impl<T: Clone> Node<T> {
271 /// Flags every ancestor as having a dirty descendant. Stops at the first
272 /// one that was already flagged, so a burst of sets on the same node costs
273 /// one RMW, not one walk per set.
274 fn mark_ancestors(&self) {
275 for flag in &self.ancestor_flags {
276 // Always a read-modify-write, never a `load` fast path, even though
277 // the flag is usually already up and the RMW takes the line
278 // exclusive. The swap is not here to change the flag -- it is here
279 // to *publish*.
280 //
281 // `merge_sons` reads a son's `dirty` bit without taking that son's
282 // data lock, so the only thing that makes the raised bit visible to
283 // it is a release edge on the flag it clears. A `load` that returns
284 // true and bails out releases nothing: the writer leaves having
285 // published no edge at all, the merger may then read `dirty` stale,
286 // skip the son, and clear the flags on its way out -- and the write
287 // is gone for good, because nothing is left flagged to bring anyone
288 // back. loom finds it in a two-level tree; see tests/loom.rs.
289 //
290 // A plain load is also unsound for a second reason, one the lock
291 // would not fix either: it can read a stale `true` for an ancestor a
292 // merge has just cleared, and then the walk stops short of the root
293 // and no later read ever comes down. An RMW cannot -- it always
294 // reads the latest value in the flag's modification order.
295 //
296 // The RMW is what closes it: it lands in the flag's modification
297 // order, so the merger's own `swap(false)` either reads it -- and
298 // then acquires everything this writer did, `dirty` included -- or
299 // precedes it, in which case the flag is left up and the next read
300 // comes back down.
301 if flag.swap(true, Ordering::AcqRel) {
302 return;
303 }
304 }
305 }
306
307 /// Folds every dirty descendant into this node, deepest first.
308 /// Returns whether `self.data` changed.
309 fn merge_sons(&self) -> bool {
310 // cleared before the walk, not after: a set landing mid-walk re-flags
311 // this node and is picked up by the next merge instead of being lost
312 if !self.subtree_dirty.swap(false, Ordering::AcqRel) {
313 return false;
314 }
315
316 let mut changed = false;
317 let mut spent: Vec<Arc<Node<T>>> = Vec::new();
318 // one clone of the handle list per level: the sons lock must not be held
319 // across the recursion or copy() would block for the whole subtree merge.
320 // The subtree_dirty check above means a clean tree never gets here.
321 for son in self.snapshot_sons() {
322 // grandsons first: a son that absorbs a grandson is itself out of sync
323 let son_changed = son.merge_sons();
324 // cheap check first, to skip the lock on a clean son
325 if !son.dirty.load(Ordering::Acquire) && !son_changed {
326 // Nothing to fold. Reaping rides along on this same walk rather
327 // than a second pass: a second `snapshot_sons` would allocate a
328 // vector and touch every refcount again on every merge, spent
329 // sons or not, and that showed up as +47% on a 1000-son fold.
330 if son.is_spent() {
331 spent.push(son);
332 }
333 continue;
334 }
335 // read and clear under the son's lock: this pairs with set(), so the
336 // two can never interleave. copy the value out before taking our own
337 // lock, we must never hold two at once.
338 let son_data = {
339 let mut guard = son.data.lock().unwrap();
340 son.dirty.store(false, Ordering::Release);
341 // take the delta and leave the identity behind. Cloning it out
342 // and leaving it in place would fold the same delta again on
343 // the next read: `update(|x| *x += 1)` twice, with a get() in
344 // between, would land as +1 then +2.
345 mem::replace(&mut *guard, (*son.identity).clone())
346 };
347 (self.merge)(&mut self.data.lock().unwrap(), &son_data);
348 changed = true;
349 // folded and empty-handed: this is the moment it becomes reapable
350 if son.is_spent() {
351 spent.push(son);
352 }
353 }
354 if !spent.is_empty() {
355 self.reap(&spent);
356 }
357 changed
358 }
359
360 /// A node with no handles left, nothing pending, and nothing underneath it.
361 /// Anything less and unlinking it would lose data or orphan a live writer.
362 fn is_spent(&self) -> bool {
363 self.dead.load(Ordering::Acquire)
364 && self.handles.load(Ordering::Acquire) == 0
365 && !self.dirty.load(Ordering::Acquire)
366 && self.sons.lock().unwrap().is_empty()
367 }
368
369 /// Unlinks spent sons. `swap_remove` semantics via `retain`: nothing caches
370 /// a position, so there are no indices to patch. Because a dead son is
371 /// removed rather than tombstoned in place, the list stays the length of the
372 /// *live* sons, which is what keeps `snapshot_sons` from growing with the
373 /// number of nodes the process has ever created.
374 fn reap(&self, spent: &[Arc<Node<T>>]) {
375 // Two regimes. A pool recycling one worker at a time retires a single
376 // son per merge, and there a linear scan beats allocating and sorting.
377 // A whole generation retiring at once makes `spent` as long as `sons`,
378 // and then `any(ptr_eq)` inside `retain` is quadratic -- 362us to reap a
379 // thousand sons, against 154us by address.
380 const LINEAR: usize = 8;
381 let marks: Vec<*const Node<T>> = if spent.len() > LINEAR {
382 let mut m: Vec<*const Node<T>> = spent.iter().map(Arc::as_ptr).collect();
383 m.sort_unstable();
384 m
385 } else {
386 Vec::new()
387 };
388 let is_marked = |s: &Arc<Node<T>>| {
389 if spent.len() > LINEAR {
390 marks.binary_search(&Arc::as_ptr(s)).is_ok()
391 } else {
392 spent.iter().any(|d| Arc::ptr_eq(s, d))
393 }
394 };
395
396 let mut sons = self.sons.lock().unwrap();
397 sons.retain(|s| {
398 if !is_marked(s) {
399 return true;
400 }
401 // Re-check the flags, but never the son's own `sons` list: taking
402 // that lock here would mean holding two at once, which this crate
403 // does not do anywhere else. It is not needed. A new son can only
404 // appear through `copy()`, which needs a handle, and this node has
405 // none and can never be handed one again -- `dead` is permanent
406 // because nothing hands out a handle to an existing node.
407 s.handles.load(Ordering::Acquire) != 0 || s.dirty.load(Ordering::Acquire)
408 });
409 }
410
411 fn check_children(&self) -> bool {
412 if !self.subtree_dirty.load(Ordering::Acquire) {
413 return false;
414 }
415 self.snapshot_sons()
416 .iter()
417 .any(|s| s.dirty.load(Ordering::Acquire) || s.check_children())
418 }
419
420 /// Clones the son handles out so the `sons` lock is not held while
421 /// recursing: another thread calling copy() on us would block on it.
422 fn snapshot_sons(&self) -> Vec<Arc<Node<T>>> {
423 self.sons.lock().unwrap().to_vec()
424 }
425}
426
427#[cfg(all(test, not(loom)))]
428mod tests {
429 use super::*;
430 use std::thread;
431
432 fn sum() -> Mergex<i32> {
433 Mergex::new(7, 0, |father: &mut i32, son: &i32| *father += *son)
434 }
435
436 #[test]
437 fn thread_updates_reach_the_root() {
438 let root = sum();
439 let t1 = root.copy();
440 let t2 = root.copy();
441
442 let a = thread::spawn(move || t1.set(10));
443 let b = thread::spawn(move || t2.set(20));
444 a.join().unwrap();
445 b.join().unwrap();
446
447 assert!(root.check_children());
448 assert_eq!(root.get(), 37); // 7 + 10 + 20
449 assert!(!root.check_children()); // dirty bits cleared
450 }
451
452 #[test]
453 fn grandsons_merge_bottom_up() {
454 let root = sum();
455 let son = root.copy();
456 let grandson = son.copy();
457 grandson.set(5);
458
459 assert!(root.check_children()); // seen through the son
460 assert_eq!(root.get(), 12); // 7 + (0 + 5)
461 }
462
463 #[test]
464 fn sons_created_inside_a_thread_register() {
465 let root = sum();
466 let t1 = root.copy();
467
468 thread::spawn(move || {
469 let grandson = t1.copy();
470 grandson.set(1000);
471 })
472 .join()
473 .unwrap();
474
475 assert_eq!(root.get(), 1007); // 7 + (0 + 1000)
476 }
477
478 #[test]
479 fn dropping_the_root_strands_the_son() {
480 let son = {
481 let root = sum();
482 let son = root.copy();
483 son.set(3); // never folded: the root is about to go away
484 son
485 }; // root handle dropped here, nothing else holds it
486
487 // the tree is owned from the root down, so the son survives on its own
488 // handle but has nowhere left to fold into
489 assert_eq!(son.get_threaded(), 3);
490 }
491
492 #[test]
493 fn a_dropped_handle_still_delivers_its_write() {
494 let root = sum();
495 {
496 let worker = root.copy();
497 worker.set(5);
498 } // the worker is gone before anyone reads
499
500 assert_eq!(root.get(), 12); // 7 + 5, collected by the merge
501 }
502
503 #[test]
504 fn a_spent_son_is_unlinked_by_the_next_merge() {
505 let root = sum();
506 {
507 let worker = root.copy();
508 worker.set(5);
509 }
510 assert_eq!(root.node.sons.lock().unwrap().len(), 1); // still linked
511
512 assert_eq!(root.get(), 12); // folds, then reaps
513 assert_eq!(root.node.sons.lock().unwrap().len(), 0);
514 }
515
516 #[test]
517 fn a_live_son_is_never_unlinked() {
518 let root = sum();
519 let worker = root.copy();
520 worker.set(5);
521
522 assert_eq!(root.get(), 12);
523 assert_eq!(root.node.sons.lock().unwrap().len(), 1); // handle still held
524
525 worker.set(2);
526 assert_eq!(root.get(), 14); // and still usable
527 }
528
529 #[test]
530 fn a_dead_son_holding_a_live_grandson_stays() {
531 let root = sum();
532 let grandson = {
533 let son = root.copy();
534 son.copy()
535 }; // the intermediate handle is gone, but its son is not
536 grandson.set(9);
537
538 assert_eq!(root.get(), 16); // 7 + (0 + 9), through the dead intermediate
539 assert_eq!(root.node.sons.lock().unwrap().len(), 1); // not reaped: not empty
540 }
541
542 #[test]
543 fn a_pool_of_short_lived_workers_does_not_grow_the_son_list() {
544 let root = Mergex::new(0i64, 0, |f: &mut i64, s: &i64| *f += *s);
545 for i in 1..=100 {
546 let w = root.copy();
547 w.set(i);
548 drop(w);
549 root.get(); // a pool reads between tasks
550 }
551
552 assert_eq!(root.get(), (1..=100).sum::<i64>());
553 assert_eq!(root.node.sons.lock().unwrap().len(), 0);
554 }
555
556 #[test]
557 fn many_threads_registering_and_setting_at_once() {
558 let root = Mergex::new(0i64, 0, |father: &mut i64, son: &i64| *father += *son);
559
560 let handles: Vec<_> = (1..=50)
561 .map(|i| {
562 let r = root.clone(); // concurrent copy(): stresses the sons lock
563 thread::spawn(move || r.copy().set(i))
564 })
565 .collect();
566 for h in handles {
567 h.join().unwrap();
568 }
569
570 assert_eq!(root.get(), (1..=50).sum::<i64>()); // 1275, nothing lost
571 }
572
573 #[test]
574 fn merging_is_idempotent() {
575 let root = sum();
576 root.copy().set(10);
577
578 assert_eq!(root.get(), 17);
579 assert_eq!(root.get(), 17); // dirty bit cleared, no double counting
580 }
581
582 #[test]
583 fn a_read_does_not_replay_an_earlier_delta() {
584 let root = sum();
585 let son = root.copy();
586
587 // the son accumulates in place, so its data still holds the previous
588 // increments. Each read must fold only what is new since the last one.
589 son.update(|x| *x += 1);
590 assert_eq!(root.get(), 8);
591 son.update(|x| *x += 1);
592 assert_eq!(root.get(), 9); // not 10: the first +1 is not folded twice
593 son.update(|x| *x += 1);
594 assert_eq!(root.get(), 10);
595 }
596
597 #[test]
598 fn folding_resets_the_son_to_the_identity() {
599 let root = sum();
600 let son = root.copy();
601
602 assert_eq!(son.get_threaded(), 0); // a fresh son owes its father nothing
603 son.set(5);
604 assert_eq!(root.get(), 12);
605 assert_eq!(son.get_threaded(), 0); // and owes nothing again once folded
606 }
607
608 #[test]
609 fn an_intermediate_node_is_reset_too() {
610 let root = sum();
611 let son = root.copy();
612 let grandson = son.copy();
613
614 grandson.set(4);
615 assert_eq!(root.get(), 11);
616 assert_eq!(son.get_threaded(), 0); // the son passed the delta on
617 assert_eq!(grandson.get_threaded(), 0);
618
619 grandson.set(4);
620 assert_eq!(root.get(), 15); // 11 + 4, not 11 + 8
621 }
622}