From d8f2d0982e53050b86cd4336b496a0256975818e Mon Sep 17 00:00:00 2001 From: tv Date: Tue, 17 Nov 2026 02:24:32 +0000 Subject: sync: send a peer all it lacks past what still counts as sent Messages taken as delivered and lost, more of them than still count as sent, leave a peer lacking changes we take it to have. Asking for the first of them, it got that one alone, and asked for the next once that arrived, a change per round trip; or, asking for our heads alone, the last of them again and again. When a peer needs a change in the history of the heads we share that no longer counts as sent, the session answers as if it had said it has nothing since the latest heads it said that we hold (`lost_beyond_sent`): everything since goes in one message. --- src/document/sync.rs | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 92 insertions(+) (limited to 'src') diff --git a/src/document/sync.rs b/src/document/sync.rs index db4eed7..4c633f5 100644 --- a/src/document/sync.rs +++ b/src/document/sync.rs @@ -208,6 +208,9 @@ pub(crate) struct SyncSession { /// The heads the peer said last, in the newest of its messages so far (one that /// comes late doesn't count: `older_keeps_newer`). said_heads: Option>, + /// The latest heads the peer said that we hold all of: what it has for certain, + /// where the heads we share may only be taken for its (`assume_delivered`). + held_said: Vec, /// What changes waiting in screening build on and we lack (`access::screen`): asked /// for in our next message (`lacks`). lacking: Vec, @@ -269,6 +272,7 @@ impl SyncSession { known_elsewhere: std::collections::HashMap::new(), assumed_lately: std::collections::VecDeque::new(), said_heads: None, + held_said: Vec::new(), lacking: Vec::new(), refused_backoff: Backoff::new(REFUSED_WAIT, REFUSED_WAIT_MAX), refusals_told: None, @@ -365,6 +369,11 @@ impl SyncSession { let said = message.0.heads.clone(); doc.receive_sync_message_log_patches(&mut self.state, message.0, log)?; self.older_keeps_newer(doc, &said); + if let Some(said) = &self.said_heads + && crate::document::changes::holds_all(doc, said) + { + self.held_said = said.clone(); + } self.known_last_sync(doc); Ok(()) } @@ -914,6 +923,7 @@ impl SyncSession { bloom: sync::BloomFilter::default(), }]); self.said_heads = Some(heads.to_vec()); + self.held_said = heads.to_vec(); before - self.state.sent_hashes.len() } @@ -967,6 +977,12 @@ impl SyncSession { } } } + if lost_beyond_sent(&mut self.state, doc, &self.held_said) { + debug!( + peer = %peer, + "Peer lacks changes we took it to have; sending everything since the heads it last said" + ); + } let forgotten = forget_sent_for_need(&mut self.state, doc); if forgotten > 0 { debug!( @@ -1182,6 +1198,40 @@ fn answer_for_everything_since_shared(state: &mut sync::State, doc: &Document) - true } +/// Messages taken as delivered (`assume_delivered`) and lost, more of them than still +/// count as sent (`ASSUMED_KEPT`), leave the peer lacking what we take it to have: it +/// needs (`their_need`) a change in the history of the heads we share that doesn't count +/// as sent, so isn't on its way. Nothing else sends what that change builds on: we take +/// the peer to have it. So answer as if it had said it has nothing since the heads it +/// last said that we hold (`held_said`): everything since goes in one message (a delta +/// when large: `swarm::sync`). Returns whether it did. Call after receiving, before +/// forgetting having sent what it needs (`forget_sent_for_need`): what still counts as +/// sent may only be late. +fn lost_beyond_sent( + state: &mut sync::State, + doc: &Document, + held_said: &[crate::document::ChangeHash], +) -> bool { + let lost = state.their_need.iter().flatten().any(|hash| { + !state.sent_hashes.contains(hash) + && crate::document::changes::holds(doc, hash) + && crate::document::changes::covers( + doc, + &state.shared_heads, + std::slice::from_ref(hash), + ) + }); + if !lost { + return false; + } + state.shared_heads = held_said.to_vec(); + state.their_have = Some(vec![sync::Have { + last_sync: held_said.to_vec(), + bloom: sync::BloomFilter::default(), + }]); + true +} + /// Forgets having sent what the peer needs (`their_need`) and the changes those build /// on that we sent too, following their predecessors as long as we sent them: so all of /// a run of lost messages goes again at once. Changes sent after them stay sent (they @@ -1575,6 +1625,48 @@ mod tests { assert_eq!(decode(&ask).unwrap().0.need, vec![lost]); } + /// Pushes taken as delivered and lost both ways, of one side more than still count + /// as sent (`ASSUMED_KEPT`): the other, holding the last waiting for what it builds + /// on, asks for what it lacks (`lacks`), and gets all of them in one message + /// (`lost_beyond_sent`), though neither knows the other's heads. + #[test] + fn pushes_lost_beyond_those_counted_as_sent_go_again_at_once() { + use crate::document::testing::change; + use automerge::{ROOT, transaction::Transactable}; + let (mut ours, mut theirs) = (Document::new(), Document::new()); + change(&mut ours, |doc| doc.put(ROOT, "early", 1).unwrap()); + let (mut a, mut b) = in_step(&mut ours, &mut theirs); + let (now, bytes) = (Instant::now(), SyncBytes::default()); + + change(&mut theirs, |doc| doc.put(ROOT, "theirs", 1).unwrap()); + b.push(&theirs, 1 << 20).expect("pushed, and lost"); + b.assume_delivered(&theirs.get_heads()); + b.send_succeeded(b.id()); + let mut lost = Vec::new(); + for n in 0..ASSUMED_KEPT + 2 { + change(&mut ours, |doc| doc.put(ROOT, "lost", n as i64).unwrap()); + lost.push(ours.get_heads()[0]); + a.push(&ours, 1 << 20).expect("pushed, and lost"); + a.assume_delivered(&ours.get_heads()); + a.send_succeeded(a.id()); + } + assert!(!a.state.sent_hashes.contains(&lost[0])); + + // b learns a's heads and asks for them, and for the first lost one, as it would + // holding the second back, waiting for it. + b.pull_from(ours.get_heads()); + b.lacks(vec![lost[0]]); + let ask = b.generate(&theirs, now, bytes).expect("an ask"); + assert!(decode(&ask).unwrap().0.need.contains(&lost[0])); + a.receive(&mut ours, decode(&ask).unwrap()).unwrap(); + a.resend_if_needed(&ours, "b", now); + a.generate(&ours, now, bytes).expect("the lost ones"); + assert!( + lost.iter().all(|hash| a.carried().contains(hash)), + "every lost one goes again" + ); + } + /// What changes held back in screening lack is asked for (`lacks`), as Automerge /// asks for what the changes it holds back lack. #[test] -- cgit v1.3.1