From 598366b03679eac9d04f32d9194f3ba4ba9c3da8 Mon Sep 17 00:00:00 2001 From: tv Date: Wed, 18 Nov 2026 17:26:53 +0000 Subject: store: a drop refuses whatever writes what a dropped event writes A fold may say what an event writes that others may write alike (`Fold::writes`): of the federation, a version event's version. A node whose operator has it drop such an event drops the taken events writing the same with it, and refuses any writing it from then on, whoever wrote it anew: of a version, it takes no other version event naming it and writes none itself, though it holds the votes that passed it. The node keeps what each dropped event writes in its store file, across restarts; allowing one of them takes them all back. Row 51 of the federation's attacks has its test, and waits no more. --- src/federation/store/memory.rs | 114 ++++++++++++++++++++++++++++++++++++----- 1 file changed, 102 insertions(+), 12 deletions(-) (limited to 'src/federation/store/memory.rs') diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index bc0c672..7527a44 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -19,7 +19,7 @@ pub(crate) enum Refusal { NotAbove, /// Its history takes it, but the node doesn't, by what it took before. Own, - /// Its operator had the node drop it. + /// Its operator had the node drop it, or one writing what it writes (`Fold::writes`). Dropped, } @@ -68,6 +68,9 @@ pub(crate) struct Store { waits_for: HashMap>, /// The events refused, and why. refused: HashMap, + /// Of the events refused as dropped, those writing what other events may write alike, + /// and what each writes (`Fold::writes`): an event writing that is refused as dropped. + writes: HashMap, /// What a move to a checkpoint forgot that came before its heads: held as accounted /// for, and nothing after the checkpoint builds on it. forgotten: HashSet, @@ -112,6 +115,7 @@ impl Store { waiting: HashMap::new(), waits_for: HashMap::new(), refused: HashMap::new(), + writes: HashMap::new(), forgotten: HashSet::new(), }) } @@ -443,6 +447,12 @@ impl Store { } fn judged(&mut self, id: Id, event: Event, taken: &mut Vec) -> Offered { + if let Some(writes) = F::writes(&event.bytes) + && self.writes.values().any(|dropped| *dropped == writes) + { + self.writes.insert(id, writes); + return self.refuse(id, Refusal::Dropped); + } if let Some(refused) = event .dependencies .iter() @@ -503,22 +513,31 @@ impl Store { self.refused.iter() } - /// Drops events taken after the checkpoint, with everything built on them, as their - /// operator has the node do: it refuses them from then on, until its operator allows - /// them again. What the checkpoint keeps, or holds by ID, it drops not: every event - /// after it builds on that. Returns what it dropped, in the order taken. + /// Drops events taken after the checkpoint, those writing what they write alike + /// (`Fold::writes`), and everything built on them, as their operator has the node do: + /// it refuses them from then on, and whatever writes what they write, until its + /// operator allows them again. What the checkpoint keeps, or holds by ID, it drops not: + /// every event after it builds on that. Returns what it dropped, in the order taken. pub(crate) fn drop_taken(&mut self, ids: &[Id]) -> Result, Refused> { if let Some(id) = ids.iter().find(|id| !self.events.contains_key(id)) { return Err(Refused::new(format!( "{id} isn't an event taken after the checkpoint" ))); } + let named: HashSet = ids + .iter() + .filter_map(|id| F::writes(&self.events[id].bytes)) + .collect(); let mut dropped: HashMap = ids.iter().map(|id| (*id, Refusal::Dropped)).collect(); for id in &self.order { if dropped.contains_key(id) { continue; } + if F::writes(&self.events[id].bytes).is_some_and(|writes| named.contains(&writes)) { + dropped.insert(*id, Refusal::Dropped); + continue; + } if let Some(on) = self.events[id] .dependencies .iter() @@ -536,7 +555,11 @@ impl Store { .collect(); self.order.retain(|id| !dropped.contains_key(id)); for id in &order { - self.events.remove(id); + if let Some(event) = self.events.remove(id) + && let Some(writes) = F::writes(&event.bytes) + { + self.writes.insert(*id, writes); + } } self.refused.extend(dropped); let mut state = self.start.clone(); @@ -548,14 +571,27 @@ impl Store { } /// Takes back what the node refused of its own, or dropped, as its operator says - /// otherwise: `ids`, and what was refused for being built on them. They are taken when - /// offered again, where the store takes them then. + /// otherwise: `ids`, what was dropped for writing what a dropped one among them writes, + /// and what was refused for being built on them. They are taken when offered again, + /// where the store takes them then. pub(crate) fn allow(&mut self, ids: &[Id]) { let mut todo: Vec = ids .iter() .filter(|id| matches!(self.refused.get(id), Some(Refusal::Own | Refusal::Dropped))) .copied() .collect(); + let lifted: HashSet = todo + .iter() + .filter_map(|id| self.writes.get(id)) + .copied() + .collect(); + todo.extend( + self.writes + .iter() + .filter(|(_, writes)| lifted.contains(writes)) + .map(|(id, _)| *id), + ); + self.writes.retain(|_, writes| !lifted.contains(writes)); while let Some(id) = todo.pop() { self.refused.remove(&id); todo.extend( @@ -568,17 +604,31 @@ impl Store { } /// Itself, refusing `own` as its node refused them of its own and `dropped` as its - /// operator had it drop them: a store read anew, before anything is offered to it, - /// refuses what its node refused so before, whatever order the events come in + /// operator had it drop them, and whatever writes what one of `writes`, each a dropped + /// event and what it writes, does: a store read anew, before anything is offered to + /// it, refuses what its node refused so before, whatever order the events come in /// (`docs/store.md`, A node's own). - pub(crate) fn refusing(mut self, own: &[Id], dropped: &[Id]) -> Self { + pub(crate) fn refusing(mut self, own: &[Id], dropped: &[Id], writes: &[(Id, Id)]) -> Self { self.refused .extend(own.iter().map(|id| (*id, Refusal::Own))); self.refused .extend(dropped.iter().map(|id| (*id, Refusal::Dropped))); + self.writes.extend(writes.iter().copied()); self } + /// Of what its operator had it drop, the events writing what others may write alike, + /// each with what it writes, in the order of their IDs. + pub(crate) fn dropped_writes(&self) -> Vec<(Id, Id)> { + let mut writes: Vec<(Id, Id)> = self + .writes + .iter() + .map(|(id, writes)| (*id, *writes)) + .collect(); + writes.sort_unstable(); + writes + } + /// What its node refused of its own, and what its operator had it drop. pub(crate) fn own(&self) -> (Vec, Vec) { let of = |refusal: Refusal| { @@ -778,6 +828,46 @@ mod tests { assert!(store.drop_taken(&[root]).is_err()); } + /// An event its operator had the node drop writing what others write alike: they are + /// dropped with it, taken or offered later, and whatever writes it, before or after a + /// store is read anew, until its operator allows one. + #[test] + fn a_drop_refuses_whatever_writes_what_the_dropped_write() { + let mut store = store(); + let root = store.id(); + let mark = taken(store.offer(testfold::put(&[root], "mark", "1"))); + let one = testfold::era(&[root], 1, "one"); + let again = testfold::era(&[mark], 1, "one"); + let anew = testfold::era(&[root, mark], 1, "one"); + let one_id = taken(store.offer(one.clone())); + let again_id = taken(store.offer(again)); + assert_eq!(store.drop_taken(&[one_id]).unwrap(), vec![one_id, again_id]); + assert_eq!(store.state().era().0, 0); + assert_eq!( + store.offer(anew.clone()), + Offered::Refused(Refusal::Dropped) + ); + assert_eq!(store.dropped_writes().len(), 3); + // Read anew: one writing the same, never offered before, is refused as dropped. + let (own, drops) = store.own(); + let mut read = self::store().refusing(&own, &drops, &store.dropped_writes()); + taken(read.offer(testfold::put(&[root], "mark", "1"))); + let later = taken(read.offer(testfold::put(&[mark], "later", "1"))); + assert_eq!( + read.offer(testfold::era(&[later], 1, "one")), + Offered::Refused(Refusal::Dropped) + ); + assert!(matches!( + read.offer(testfold::era(&[root], 1, "two")), + Offered::Taken(_) + )); + // Allowed again: all of them. + store.allow(&[one_id]); + assert!(store.dropped_writes().is_empty()); + assert!(matches!(store.offer(one), Offered::Taken(_))); + assert!(matches!(store.offer(anew), Offered::Taken(_))); + } + #[test] fn a_store_read_anew_refuses_what_its_node_refused_of_its_own() { let mut store = store(); @@ -794,7 +884,7 @@ mod tests { (&[Id::of(&other)][..], &[dropped][..]) ); // Read anew, the other era first: refused as before. - let mut anew = self::store().refusing(&own, &drops); + let mut anew = self::store().refusing(&own, &drops, &store.dropped_writes()); assert_eq!(anew.offer(other), Offered::Refused(Refusal::Own)); assert_eq!( anew.offer(testfold::put(&[root], "b", "1")), -- cgit v1.3.1