Skip to main content

tuwunel_service/migrations/injectivity/
seen.rs

1use serde::{Deserialize, Serialize};
2use tuwunel_core::{
3	Err, Result, async_noinline, debug_warn, err, implement, info, result::NotFound,
4	smallvec::SmallVec, utils::TryReadyExt, warn,
5};
6use tuwunel_database::{Database, Json, Txn, keyval::ValBuf, serialize_key, serialize_val};
7
8use self::{
9	identity::{cleanup, repair as repair_identities},
10	rooms::repair as repair_rooms,
11	state::{gc::collect, repair as repair_states},
12};
13use crate::{
14	Services,
15	integrity::short_ids::{
16		Identity, Reason, Shape,
17		check::{Finding, Subject, scan},
18		identity::consistent,
19		references::References,
20	},
21};
22
23mod identity;
24mod rooms;
25mod state;
26#[cfg(test)]
27mod tests;
28
29type Samples = SmallVec<[Sample; 1]>;
30type Observed = (Outcome, Uncertain);
31
32pub(super) const MARKER: &str = "repair_short_injectivity_seen";
33const VERSION: u8 = 1;
34const SAMPLE_LIMIT: usize = 4;
35const IDENTITY_LIMIT: usize = 128;
36const RECORD_LIMIT: usize = 4096;
37
38// Stored count positions, so the order is part of the record format.
39const SHAPES: [Shape; 15] = [
40	Shape::EventAlias,
41	Shape::StatekeyAlias,
42	Shape::DanglingWinner,
43	Shape::PromotableReverse,
44	Shape::EventAliasEntry,
45	Shape::StatekeyAliasEntry,
46	Shape::AffectedState,
47	Shape::DiffCollision,
48	Shape::EventOrphanEntry,
49	Shape::StatekeyOrphanEntry,
50	Shape::AuthChainCache,
51	Shape::UnreachableState,
52	Shape::PurgeResidue,
53	Shape::LiveRoomAlias,
54	Shape::DeclinedMarker,
55];
56
57#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
58#[serde(deny_unknown_fields)]
59pub(super) struct Outcome {
60	version: u8,
61	status: Status,
62
63	/// Each count tallies occurrences, including overlaps and unknown censuses.
64	counts: [u64; SHAPES.len()],
65	samples: Samples,
66	truncated: bool,
67}
68
69#[derive(Clone, Copy, Debug, Deserialize, PartialEq, Serialize)]
70#[serde(rename_all = "snake_case")]
71enum Status {
72	/// The repair verified that no residue remains.
73	Clean,
74
75	/// The repair left residue, which the counts and samples describe.
76	Unfinished,
77
78	/// The superseded repair settled the database and its short-id families agree.
79	Superseded,
80}
81
82#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
83#[serde(deny_unknown_fields)]
84struct Sample {
85	shape: Shape,
86	identity: Identity,
87	reason: Reason,
88}
89
90struct Boundary<'a> {
91	db: &'a Database,
92}
93
94#[derive(Clone, Copy, Default)]
95struct Uncertain {
96	states: bool,
97	collected: bool,
98	rooms: bool,
99}
100
101impl From<Shape> for u8 {
102	fn from(shape: Shape) -> Self {
103		match shape {
104			| Shape::EventAlias => 1,
105			| Shape::StatekeyAlias => 2,
106			| Shape::DanglingWinner => 3,
107			| Shape::PromotableReverse => 4,
108			| Shape::EventAliasEntry => 12,
109			| Shape::StatekeyAliasEntry => 13,
110			| Shape::AffectedState => 15,
111			| Shape::DiffCollision => 19,
112			| Shape::EventOrphanEntry => 23,
113			| Shape::StatekeyOrphanEntry => 24,
114			| Shape::AuthChainCache => 27,
115			| Shape::UnreachableState => 29,
116			| Shape::PurgeResidue => 32,
117			| Shape::LiveRoomAlias => 33,
118			| Shape::DeclinedMarker => 37,
119		}
120	}
121}
122
123impl TryFrom<u8> for Shape {
124	type Error = u8;
125
126	fn try_from(code: u8) -> Result<Self, Self::Error> {
127		match code {
128			| 1 => Ok(Self::EventAlias),
129			| 2 => Ok(Self::StatekeyAlias),
130			| 3 => Ok(Self::DanglingWinner),
131			| 4 => Ok(Self::PromotableReverse),
132			| 12 => Ok(Self::EventAliasEntry),
133			| 13 => Ok(Self::StatekeyAliasEntry),
134			| 15 => Ok(Self::AffectedState),
135			| 19 => Ok(Self::DiffCollision),
136			| 23 => Ok(Self::EventOrphanEntry),
137			| 24 => Ok(Self::StatekeyOrphanEntry),
138			| 27 => Ok(Self::AuthChainCache),
139			| 29 => Ok(Self::UnreachableState),
140			| 32 => Ok(Self::PurgeResidue),
141			| 33 => Ok(Self::LiveRoomAlias),
142			| 37 => Ok(Self::DeclinedMarker),
143			| unknown => Err(unknown),
144		}
145	}
146}
147
148/// Records the superseded repair's settlement when the short-id families agree.
149///
150/// Returns whether the settlement stands; disagreement or a failed check leaves
151/// the full repair to run.
152#[tracing::instrument(level = "debug", skip_all)]
153pub(super) async fn settle(services: &Services) -> bool {
154	stands(&services.db, async || {
155		services.server.progress.begin(MARKER);
156		consistent(services).await
157	})
158	.await
159}
160
161/// Runs the repair unless a recognized outcome is already recorded.
162///
163/// The repair must finish its durability barriers and uncached verification
164/// before returning, and its outcome is recorded only after another sync. A
165/// read-only open or any error leaves completion unestablished without failing
166/// startup.
167#[tracing::instrument(level = "debug", skip_all)]
168pub(super) async fn run(
169	db: &Database,
170	repair: impl AsyncFnOnce() -> Result<Outcome>,
171) -> Option<Outcome> {
172	Boundary::writable(db)?
173		.attempt(repair)
174		.await
175		.inspect_err(|error| {
176			warn!(%error, "Injectivity repair interrupted; completion remains unestablished.");
177		})
178		.ok()
179		.flatten()
180}
181
182/// Records a clean outcome for a fresh database without scanning it.
183///
184/// The record is written and synced before it counts. A read-only open or a
185/// failed write or sync returns `None` and leaves completion unestablished.
186#[tracing::instrument(level = "debug", skip_all)]
187pub(super) fn stamp(db: &Database) -> Option<Outcome> {
188	Boundary::writable(db)?
189		.stamp(Status::Clean)
190		.inspect_err(|error| {
191			warn!(%error, "Injectivity clean stamp failed; completion remains unestablished.");
192		})
193		.ok()
194}
195
196/// Completes independent repair passes and verifies their residual populations.
197///
198/// Identity mutations refresh the census before final alias reclamation. Every
199/// final inspection is read-only and uses freshly scanned committed raw rows.
200// query-depth firewall
201#[async_noinline]
202#[tracing::instrument(level = "debug", skip_all)]
203pub(super) async fn repair(services: &Services) -> Result<Outcome> {
204	let progress = &services.server.progress;
205
206	progress.enter("short ids");
207	let identities = repair_identities(services).await?;
208
209	progress.enter("state snapshots");
210	let (states, identities) = repair_states(services, identities).await?;
211
212	progress.enter("unreachable states");
213	let collected = collect(services).await?;
214
215	progress.enter("rooms");
216	let rooms = repair_rooms(services).await?;
217
218	progress.enter("references");
219	let references = References::census(services, &identities).await?;
220
221	cleanup(services, &identities.events, &references.events, references.event_complete).await?;
222
223	cleanup(
224		services,
225		&identities.statekeys,
226		&references.statekeys,
227		references.statekey_complete,
228	)
229	.await?;
230
231	// A verified restore leaves its own unit unestablished; independent stages still ran.
232	if states.restored || rooms.restored {
233		return Err!(
234			"published data failed verification and was restored; completion remains \
235			 unestablished"
236		);
237	}
238
239	progress.enter("verify");
240	services.server.check_running()?;
241	services.db.engine.sync()?;
242
243	let uncertain = Uncertain {
244		states: states.uncertain,
245		collected: collected.unknown,
246		rooms: rooms.unknown,
247	};
248
249	let outcome = verify(services, uncertain).await?;
250
251	info!(
252		rewritten = states.rewritten,
253		original_bytes = states.original_bytes,
254		snapshot_bytes = states.snapshot_bytes,
255		collected = collected.deleted,
256		purged = rooms.deleted,
257		moved = rooms.moved,
258		?outcome.counts,
259		"Injectivity repair verified; purge residue counts include unclassified room strays."
260	);
261
262	Ok(outcome)
263}
264
265/// Folds the census into the outcome a completed repair records.
266///
267/// A finding counts where the stream yields it, except a census that could not
268/// prove further residue absent: that joins the uncertainty the repair captured
269/// before its writes, and each kind counts once at the end. A clean final census
270/// therefore never erases what an earlier pass could not prove.
271#[tracing::instrument(level = "debug", skip_all)]
272async fn verify(services: &Services, uncertain: Uncertain) -> Result<Outcome> {
273	services.server.check_running()?;
274	let (outcome, uncertain) = scan(services)
275		.ready_try_fold((Outcome::clean(), uncertain), observe)
276		.await?;
277
278	outcome
279		.uncertain(Shape::AffectedState, uncertain.states, Reason::HistoricalState)?
280		.uncertain(Shape::UnreachableState, uncertain.collected, Reason::References)?
281		.uncertain(Shape::PurgeResidue, uncertain.rooms, Reason::Ownership)
282}
283
284fn observe((outcome, uncertain): Observed, finding: Finding) -> Result<Observed> {
285	match (&finding.subject, uncertain.raised(finding.shape)) {
286		| (Subject::Uncertain, Some(uncertain)) => Ok((outcome, uncertain)),
287		| _ => outcome
288			.observed(finding)
289			.map(|outcome| (outcome, uncertain)),
290	}
291}
292
293#[implement(Uncertain)]
294fn raised(self, shape: Shape) -> Option<Self> {
295	match shape {
296		| Shape::AffectedState => Some(Self { states: true, ..self }),
297		| Shape::UnreachableState => Some(Self { collected: true, ..self }),
298		| Shape::PurgeResidue => Some(Self { rooms: true, ..self }),
299		| _ => None,
300	}
301}
302
303#[implement(Outcome)]
304fn observed(self, finding: Finding) -> Result<Self> {
305	let Finding { shape, subject, reason } = finding;
306
307	match subject {
308		| Subject::Identity(identity) => self.residue(shape, 1, &identity, reason),
309		| Subject::Short(id) | Subject::State(id) | Subject::Room(id) =>
310			self.residue(shape, 1, &id.to_be_bytes(), reason),
311		| Subject::Malformed(count) => self.residue(shape, count, &[], reason),
312		| Subject::Incomplete | Subject::Uncertain => self.residue(shape, 1, &[], reason),
313	}
314}
315
316#[implement(Outcome)]
317fn uncertain(self, shape: Shape, unknown: bool, reason: Reason) -> Result<Self> {
318	self.residue(shape, u64::from(unknown), &[], reason)
319}
320
321/// Whether the settlement stands, recording it when the check agrees.
322///
323/// The record claims only that agreement. A read-only open is left unchecked,
324/// and a failed record leaves the check to the next start.
325#[tracing::instrument(level = "debug", skip_all)]
326async fn stands(db: &Database, check: impl AsyncFnOnce() -> Result<bool>) -> bool {
327	let Some(boundary) = Boundary::writable(db) else {
328		return true;
329	};
330
331	let Ok(agree) = check().await.inspect_err(|error| {
332		if !error.is_interrupted() {
333			warn!(%error, "Short id family check failed; running the full repair.");
334		}
335	}) else {
336		return false;
337	};
338
339	if !agree {
340		warn!("Short id families disagree after the superseded repair; running the full repair.");
341		return false;
342	}
343
344	boundary
345		.stamp(Status::Superseded)
346		.inspect(|_| {
347			info!("Short id families verified; the superseded repair's settlement stands.");
348		})
349		.inspect_err(|error| {
350			warn!(%error, "Injectivity settlement record failed; the check repeats on the next start.");
351		})
352		.ok();
353
354	true
355}
356
357#[implement(Boundary, generics = "<'a>", params = "<'a>")]
358fn writable(db: &'a Database) -> Option<Self> {
359	if db.engine.is_read_only() {
360		warn!("Injectivity repair cannot run on a read-only or secondary database.");
361		return None;
362	}
363
364	Some(Self { db })
365}
366
367#[implement(Boundary, params = "<'_>")]
368#[tracing::instrument(level = "debug", skip_all)]
369async fn attempt(
370	&self,
371	repair: impl AsyncFnOnce() -> Result<Outcome>,
372) -> Result<Option<Outcome>> {
373	let db = self.db;
374	let recorded = db["global"]
375		.get(MARKER)
376		.await
377		.present()?
378		.as_deref()
379		.and_then(Outcome::decode);
380
381	if let Some(outcome) = recorded {
382		db.engine.sync()?;
383		if outcome.status == Status::Unfinished {
384			debug_warn!(
385				?outcome.counts,
386				"Injectivity repair left unrepaired rows on an earlier start."
387			);
388		}
389
390		return Ok(None);
391	}
392
393	let outcome = repair().await?;
394	let bytes = outcome.encode()?;
395
396	db.engine.sync()?;
397	self.record(bytes)?;
398	if outcome.status == Status::Unfinished {
399		debug_warn!(
400			?outcome.counts,
401			?outcome.samples,
402			truncated = outcome.truncated,
403			"Injectivity repair left unrepaired rows; purge residue counts include \
404			 unclassified room strays."
405		);
406	}
407
408	Ok(Some(outcome))
409}
410
411#[implement(Boundary, params = "<'_>")]
412#[tracing::instrument(level = "debug", skip_all)]
413fn stamp(&self, status: Status) -> Result<Outcome> {
414	let outcome = Outcome { status, ..Outcome::clean() };
415
416	self.record(outcome.encode()?)?;
417
418	Ok(outcome)
419}
420
421#[implement(Boundary, params = "<'_>")]
422#[tracing::instrument(level = "debug", skip_all)]
423fn record(&self, bytes: ValBuf) -> Result {
424	let key = serialize_key((MARKER,))?;
425
426	Txn::insert(&self.db["global"], [(key, bytes)])
427		.try_execute()
428		.map_err(Into::into)
429}
430
431#[implement(Outcome)]
432fn clean() -> Self {
433	Self {
434		version: VERSION,
435		status: Status::Clean,
436		counts: [0; SHAPES.len()],
437		samples: Samples::new(),
438		truncated: false,
439	}
440}
441
442#[implement(Outcome)]
443fn residue(mut self, shape: Shape, count: u64, identity: &[u8], reason: Reason) -> Result<Self> {
444	if count == 0 {
445		return Ok(self);
446	}
447
448	let total = shape
449		.slot()
450		.and_then(|slot| self.counts.get_mut(slot))
451		.ok_or_else(|| err!("unsupported injectivity diagnostic shape"))?;
452
453	*total = total.saturating_add(count);
454	self.status = Status::Unfinished;
455	if self.samples.len() < SAMPLE_LIMIT {
456		let identity = identity.get(..IDENTITY_LIMIT).unwrap_or(identity);
457
458		self.samples.push(Sample {
459			shape,
460			identity: Identity::from_slice(identity),
461			reason,
462		});
463	} else {
464		self.truncated = true;
465	}
466
467	self.truncated |= identity.len() > IDENTITY_LIMIT || count > 1;
468	Ok(self)
469}
470
471impl Shape {
472	fn slot(self) -> Option<usize> { SHAPES.iter().position(|shape| *shape == self) }
473}
474
475#[implement(Outcome)]
476fn encode(&self) -> Result<ValBuf> {
477	if !self.valid() {
478		return Err!("invalid injectivity repair outcome");
479	}
480
481	serialize_val(Json(self))
482}
483
484#[implement(Outcome)]
485fn decode(bytes: &[u8]) -> Option<Self> {
486	Some(bytes)
487		.filter(|bytes| bytes.len() <= RECORD_LIMIT)
488		.and_then(|bytes| serde_json::from_slice(bytes).ok())
489		.filter(Self::valid)
490}
491
492#[implement(Outcome)]
493fn valid(&self) -> bool {
494	self.version == VERSION
495		&& self.samples.len() <= SAMPLE_LIMIT
496		&& self
497			.samples
498			.iter()
499			.all(|sample| sample.identity.len() <= IDENTITY_LIMIT)
500		&& match self.status {
501			| Status::Unfinished => self.counts.iter().any(|count| *count > 0),
502			| Status::Clean | Status::Superseded =>
503				self.counts == [0; SHAPES.len()] && self.samples.is_empty() && !self.truncated,
504		}
505}