Skip to main content

tuwunel_service/integrity/short_ids/
state.rs

1use std::{
2	collections::{BTreeMap, BTreeSet},
3	iter::repeat,
4};
5
6use futures::{
7	FutureExt, Stream, StreamExt, TryFutureExt, TryStreamExt, future::try_join, stream::unfold,
8};
9use ruma::events::TimelineEventType;
10use tuwunel_core::{
11	Err, Result, implement,
12	itertools::Itertools,
13	smallvec::SmallVec,
14	utils::{
15		BoolExt, IterStream, TryReadyExt,
16		result::NotFound,
17		stream::{TryBroadbandExt, TryWidebandExt},
18	},
19};
20use tuwunel_database::{Database, SEP, keyval::ValBuf};
21
22use super::{
23	Identity, Reason, Shape,
24	check::{Finding, Subject},
25	identity::{Candidate, Family, Identities, Kind, admitted},
26	short_of,
27};
28use crate::{
29	Services,
30	integrity::ScanExt,
31	rooms::state_compressor::{
32		CompressedState, CompressedStateEvent, compress_state_event, parse_compressed_state_event,
33	},
34};
35
36pub(crate) mod history;
37pub(crate) type Parents = BTreeMap<u64, Option<u64>>;
38pub(crate) type Aliases = BTreeMap<u64, (u64, Identity)>;
39type Occurrences = BTreeMap<u64, BTreeSet<u64>>;
40pub(crate) type Absences = Vec<Absence>;
41type Absence = (u64, u64, bool, bool);
42type Observations = [Option<Observation>; 2];
43type Observation = (Shape, u64, Reason);
44pub(crate) type Materialized = Option<(ValBuf, CompressedState)>;
45type Found = SmallVec<[Finding; 1]>;
46
47pub(crate) struct Mapping {
48	pub(crate) aliases: Aliases,
49	pub(crate) refused: BTreeSet<u64>,
50}
51
52pub(crate) struct Projection {
53	pub(crate) statekeys: Mapping,
54	pub(crate) events: Mapping,
55}
56
57pub(crate) struct Census {
58	pub(crate) parents: Parents,
59	pub(crate) seeds: BTreeSet<u64>,
60	pub(crate) unknown: bool,
61	pub(crate) held: Vec<u64>,
62	pub(crate) orphans: Occurrences,
63	pub(crate) complete: bool,
64	pub(crate) projection: Projection,
65	pub(crate) exposed: BTreeSet<u64>,
66}
67
68pub(crate) struct Scanned {
69	pub(crate) id: Option<u64>,
70	pub(crate) parent: Option<u64>,
71	pub(crate) diff: Option<Diff>,
72	pub(crate) absences: Absences,
73}
74
75pub(crate) struct Diff {
76	pub(crate) parent: Option<u64>,
77	pub(crate) added: CompressedState,
78	pub(crate) removed: CompressedState,
79}
80
81/// Streams what the state census finds, in the order verification records it.
82///
83/// A census that could not attribute every row leads, then each affected state
84/// follows with its own findings, inspected one at a time.
85#[tracing::instrument(level = "debug", skip_all)]
86pub(super) fn findings(
87	services: &Services,
88	census: Census,
89) -> impl Stream<Item = Result<Finding>> + Send + '_ {
90	let incomplete = census.unknown || !census.complete || !census.held.is_empty();
91	let head = incomplete.then_some(Finding {
92		shape: Shape::AffectedState,
93		subject: Subject::Incomplete,
94		reason: Reason::References,
95	});
96
97	let affected = descendants(&census.parents, &census.seeds).into_iter();
98
99	// Serial: each state materializes in full, and its entries already fan out.
100	// A state's findings are owned, as no item may borrow the census the unfold holds.
101	let states = unfold((census, affected), async |(census, mut affected)| {
102		let id = affected.next()?;
103		let found = inspect_state(services, &census, id).await;
104
105		Some((found, (census, affected)))
106	});
107
108	head.try_stream().chain(
109		states
110			.map_ok(IterStream::try_stream)
111			.try_flatten(),
112	)
113}
114
115#[tracing::instrument(level = "trace", skip_all)]
116async fn inspect_state(services: &Services, census: &Census, id: u64) -> Result<Found> {
117	services.server.check_running()?;
118	let state = |shape| Finding {
119		shape,
120		subject: Subject::State(id),
121		reason: Reason::HistoricalState,
122	};
123
124	let Some(bytes) = row(&services.db, id).await? else {
125		return Err!("state disappeared during final injectivity verification");
126	};
127
128	let Some(diff) = decode(&bytes) else {
129		return Ok([state(Shape::AffectedState)].into());
130	};
131
132	let collided = diff
133		.added
134		.is_disjoint(&diff.removed)
135		.is_false()
136		.then(|| state(Shape::DiffCollision));
137
138	let found = diff
139		.added
140		.iter()
141		.chain(&diff.removed)
142		.copied()
143		.try_stream()
144		.wide_and_then(|entry| inspect_entry(services, &census.projection, entry))
145		.ready_try_fold(collided.into_iter().collect(), observed)
146		.await?;
147
148	let invalid = materialize(services, id)
149		.await?
150		.and_then(|(_, state)| project(state, &census.projection))
151		.is_none();
152
153	let unverified = invalid || !census.seeds.contains(&id);
154
155	Ok(extended(found, unverified.then(|| state(Shape::AffectedState))))
156}
157
158#[tracing::instrument(level = "trace", skip_all)]
159async fn inspect_entry(
160	services: &Services,
161	projection: &Projection,
162	entry: CompressedStateEvent,
163) -> Result<Observations> {
164	let (key, event) = parse_compressed_state_event(entry);
165	let key = inspect_half(
166		services,
167		&projection.statekeys,
168		key,
169		"shortstatekey_statekey",
170		(Shape::StatekeyAliasEntry, Shape::StatekeyOrphanEntry),
171	);
172
173	let event = inspect_half(
174		services,
175		&projection.events,
176		event,
177		"shorteventid_eventid",
178		(Shape::EventAliasEntry, Shape::EventOrphanEntry),
179	);
180
181	try_join(key, event).map_ok(Into::into).await
182}
183
184fn observed(found: Found, observations: Observations) -> Result<Found> {
185	let entries = observations
186		.into_iter()
187		.flatten()
188		.map(|(shape, short, reason)| Finding {
189			shape,
190			subject: Subject::Short(short),
191			reason,
192		});
193
194	Ok(extended(found, entries))
195}
196
197fn extended(mut found: Found, more: impl IntoIterator<Item = Finding>) -> Found {
198	found.extend(more);
199	found
200}
201
202#[tracing::instrument(level = "trace", skip_all)]
203async fn inspect_half(
204	services: &Services,
205	mapping: &Mapping,
206	short: u64,
207	reverse: &str,
208	(alias, orphan): (Shape, Shape),
209) -> Result<Option<Observation>> {
210	if !present(&services.db, reverse, &short.to_be_bytes()).await? {
211		return Ok(Some((orphan, short, Reason::Identity)));
212	}
213
214	Ok(candidate(mapping, short).then_some((alias, short, Reason::HistoricalState)))
215}
216
217#[tracing::instrument(level = "trace", skip_all)]
218pub(crate) async fn survey(services: &Services, identities: &Identities) -> Result<Census> {
219	let (statekeys, events) =
220		try_join(mapping(services, &identities.statekeys), mapping(services, &identities.events))
221			.await?;
222
223	census(services, Projection { statekeys, events }).await
224}
225
226#[tracing::instrument(level = "trace", skip_all)]
227pub(crate) async fn census(services: &Services, projection: Projection) -> Result<Census> {
228	let statekeys = presence(services, "shortstatekey_statekey").await?;
229	let events = presence(services, "shorteventid_eventid").await?;
230	let initial = Census {
231		parents: Parents::new(),
232		seeds: BTreeSet::new(),
233		unknown: false,
234		held: Vec::new(),
235		orphans: Occurrences::new(),
236		complete: true,
237		projection,
238		exposed: BTreeSet::new(),
239	};
240
241	services.db["shortstatehash_statediff"]
242		.raw_stream()
243		.scanned(&services.server)
244		.map_ok(|(key, value)| Scanned {
245			id: short_of(key),
246			parent: value.get(..8).and_then(short_of),
247			diff: decode(value),
248			absences: Absences::new(),
249		})
250		.ready_try_fold(initial, |census, scanned| {
251			tally(census, scan(&statekeys, &events, scanned))
252		})
253		.await
254}
255
256#[tracing::instrument(level = "trace", skip_all)]
257pub(crate) async fn presence(services: &Services, column: &str) -> Result<Vec<u64>> {
258	// Exact big-endian keys retain numeric order, regardless of their values' validity.
259	services.db[column]
260		.raw_keys()
261		.scanned(&services.server)
262		.ready_try_filter_map(|key| Ok(short_of(key)))
263		.try_collect()
264		.await
265}
266
267#[tracing::instrument(level = "trace", skip_all)]
268pub(crate) fn scan(statekeys: &[u64], events: &[u64], scanned: Scanned) -> Scanned {
269	let Some(diff) = scanned.diff.as_ref() else {
270		return scanned;
271	};
272
273	let absences = diff
274		.added
275		.iter()
276		.chain(&diff.removed)
277		.copied()
278		.map(|entry| absence(statekeys, events, entry))
279		.filter(|(_, _, key_missing, event_missing)| *key_missing || *event_missing)
280		.collect();
281
282	Scanned { absences, ..scanned }
283}
284
285#[tracing::instrument(level = "trace", skip_all)]
286fn absence(statekeys: &[u64], events: &[u64], entry: CompressedStateEvent) -> Absence {
287	let (key, event) = parse_compressed_state_event(entry);
288	let key_missing = statekeys.binary_search(&key).is_err();
289	let event_missing = events.binary_search(&event).is_err();
290
291	(key, event, key_missing, event_missing)
292}
293
294fn tally(census: Census, Scanned { id, parent, diff, absences }: Scanned) -> Result<Census> {
295	let Some(diff) = diff else {
296		return Ok(index(incomplete(census), id, parent, true));
297	};
298
299	let exposed = !diff.added.is_disjoint(&diff.removed);
300	let seed = exposed || !absences.is_empty() || infected(&census.projection, &diff);
301	let census = absences
302		.into_iter()
303		.fold(exposure(census, id, exposed), occurrence);
304
305	Ok(index(census, id, parent, seed))
306}
307
308fn infected(projection: &Projection, diff: &Diff) -> bool {
309	diff.added
310		.iter()
311		.chain(&diff.removed)
312		.copied()
313		.map(parse_compressed_state_event)
314		.any(|(key, event)| {
315			candidate(&projection.statekeys, key) || candidate(&projection.events, event)
316		})
317}
318
319fn exposure(mut census: Census, id: Option<u64>, exposed: bool) -> Census {
320	census.exposed.extend(id.filter(|_| exposed));
321	census
322}
323
324fn candidate(mapping: &Mapping, short: u64) -> bool {
325	mapping.aliases.contains_key(&short) || mapping.refused.contains(&short)
326}
327
328fn incomplete(census: Census) -> Census { Census { complete: false, ..census } }
329
330fn occurrence(mut census: Census, (key, event, key_missing, event_missing): Absence) -> Census {
331	if key_missing {
332		census
333			.orphans
334			.entry(key)
335			.or_default()
336			.insert(event);
337
338		census.projection.statekeys.refused.insert(key);
339	}
340
341	if event_missing {
342		census.projection.events.refused.insert(event);
343	}
344
345	census
346}
347
348pub(crate) fn index(
349	mut census: Census,
350	id: Option<u64>,
351	parent: Option<u64>,
352	seed: bool,
353) -> Census {
354	census.unknown |= parent.is_none();
355	let parent = parent.filter(|parent| *parent != 0);
356	let Some(id) = id.filter(|id| *id != 0) else {
357		census.held.extend(parent);
358		return census;
359	};
360
361	census.parents.insert(id, parent);
362
363	if seed {
364		census.seeds.insert(id);
365	}
366
367	census
368}
369
370pub(crate) fn descendants(parents: &Parents, seeds: &BTreeSet<u64>) -> BTreeSet<u64> {
371	if seeds.is_empty() {
372		return BTreeSet::new();
373	}
374
375	parents
376		.keys()
377		.copied()
378		.filter(|id| ancestors(parents, *id).any(|ancestor| seeds.contains(&ancestor)))
379		.collect()
380}
381
382pub(crate) fn ancestors(parents: &Parents, id: u64) -> impl Iterator<Item = u64> + '_ {
383	repeat(()).scan((Some(id), BTreeSet::new()), |(next, visited), ()| {
384		let id = (*next)?;
385
386		if !visited.insert(id) {
387			return None;
388		}
389
390		*next = parents.get(&id).copied().flatten();
391		Some(id)
392	})
393}
394
395pub(crate) fn depth(parents: &Parents, id: u64) -> Option<usize> {
396	let (depth, root) = ancestors(parents, id)
397		.fold((0_usize, None), |(depth, _), id| (depth.saturating_add(1), Some(id)));
398
399	parents
400		.get(&root?)
401		.is_some_and(Option::is_none)
402		.then_some(depth)
403}
404
405pub(crate) fn claim(value: &[u8]) -> Option<u64> { value.get(..8).and_then(short_of) }
406
407#[tracing::instrument(level = "trace", skip_all)]
408pub(crate) async fn materialize(services: &Services, id: u64) -> Result<Materialized> {
409	let Some(original) = row(&services.db, id).await? else {
410		return Ok(None);
411	};
412
413	let bytes = original.as_slice();
414	let chain = unfold((Some(id), BTreeSet::new()), async |(next, visited)| {
415		let next = next?;
416		let loaded = match services.server.check_running() {
417			| Err(error) => Err(error),
418			| Ok(()) if visited.contains(&next) => Ok(None),
419			| Ok(()) if next == id => Ok(decode(bytes)),
420			| Ok(()) => layer(&services.db, next).await,
421		};
422
423		let parent = loaded
424			.as_ref()
425			.ok()
426			.and_then(Option::as_ref)
427			.and_then(|diff| diff.parent);
428
429		Some((loaded, (parent, visit(visited, next))))
430	})
431	.try_collect::<Vec<_>>()
432	.await?;
433
434	let state = chain
435		.into_iter()
436		.rev()
437		.try_fold(CompressedState::new(), |state, diff| {
438			// Overlapping runs do not establish their historical state.
439			diff.filter(|diff| diff.added.is_disjoint(&diff.removed))
440				.map(|diff| apply(state, diff))
441		});
442
443	Ok(state.map(|state| (original, state)))
444}
445
446#[tracing::instrument(level = "trace", skip_all)]
447pub(crate) async fn layer(db: &Database, id: u64) -> Result<Option<Diff>> {
448	fetch(db, "shortstatehash_statediff", &id.to_be_bytes(), decode)
449		.map_ok(Option::flatten)
450		.await
451}
452
453pub(crate) fn visit(mut visited: BTreeSet<u64>, id: u64) -> BTreeSet<u64> {
454	visited.insert(id);
455	visited
456}
457
458pub(crate) fn apply(state: CompressedState, diff: Diff) -> CompressedState {
459	let Diff { parent, added, removed } = diff;
460
461	// Extend the larger set, so a root layer is adopted rather than rebuilt.
462	let (mut state, smaller) = match state.len() >= added.len() {
463		| true => (state, added),
464		| false => (added, state),
465	};
466
467	state.extend(smaller);
468
469	if parent.is_some() {
470		for entry in &removed {
471			state.remove(entry);
472		}
473	}
474
475	state
476}
477
478pub(crate) fn decode(bytes: &[u8]) -> Option<Diff> {
479	let parent = short_of(bytes.get(..8)?)?;
480	let parent = parent.ne(&0).then_some(parent);
481	let tail = bytes.get(8..)?;
482	let separator = (0..tail.len())
483		.step_by(16)
484		.find(|offset| tail.get(*offset..offset.saturating_add(8)) == Some(&[0; 8]));
485
486	let (added, removed) = match separator {
487		| None => (tail, &[][..]),
488		| Some(offset) => {
489			let removed = tail
490				.get(offset.checked_add(8)?..)
491				.filter(|removed| !removed.is_empty())?;
492
493			(tail.get(..offset)?, removed)
494		},
495	};
496
497	let added = entries(added)?;
498	let removed = entries(removed)?;
499
500	Some(Diff { parent, added, removed })
501}
502
503fn entries(bytes: &[u8]) -> Option<CompressedState> {
504	let (chunks, []): (&[CompressedStateEvent], _) = bytes.as_chunks() else {
505		return None;
506	};
507
508	chunks
509		.iter()
510		.copied()
511		.map(|entry| {
512			let (key, event) = parse_compressed_state_event(entry);
513			let valid = key != 0 && event != 0;
514
515			valid.then_some(entry)
516		})
517		.collect()
518}
519
520#[tracing::instrument(level = "trace", skip_all)]
521pub(crate) async fn mapping(services: &Services, family: &Family) -> Result<Mapping> {
522	let initial = Mapping {
523		aliases: Aliases::new(),
524		refused: BTreeSet::new(),
525	};
526
527	family
528		.candidates
529		.iter()
530		.try_stream()
531		.broad_and_then(async |candidate| {
532			services.server.check_running()?;
533			let winner = match candidate.kind {
534				| Kind::Alias(winner) =>
535					admitted(&services.db, family, candidate)
536						.map_ok(|admitted| admitted.then_some(winner))
537						.await?,
538				| _ => None,
539			};
540
541			Ok((candidate, winner))
542		})
543		.ready_try_fold(initial, |mapping, (candidate, winner)| {
544			Ok(classify(mapping, candidate, winner))
545		})
546		.await
547}
548
549fn classify(mut mapping: Mapping, candidate: &Candidate, winner: Option<u64>) -> Mapping {
550	match winner {
551		| None => {
552			mapping.refused.insert(candidate.short);
553		},
554		| Some(winner) => {
555			mapping
556				.aliases
557				.insert(candidate.short, (winner, candidate.identity.clone()));
558		},
559	}
560
561	mapping
562}
563
564pub(crate) fn project(
565	state: CompressedState,
566	projection: &Projection,
567) -> Option<CompressedState> {
568	state
569		.into_iter()
570		.map(|entry| project_entry(entry, projection))
571		.collect::<Option<CompressedState>>()
572		.filter(unique_keys)
573}
574
575fn project_entry(
576	entry: CompressedStateEvent,
577	projection: &Projection,
578) -> Option<CompressedStateEvent> {
579	let (key, event) = parse_compressed_state_event(entry);
580	let (key, _) = projection.statekeys.resolve(key)?;
581	let (event, _) = projection.events.resolve(event)?;
582
583	Some(compress_state_event(key, event))
584}
585
586#[implement(Mapping)]
587fn resolve(&self, short: u64) -> Option<(u64, Option<&Identity>)> {
588	self.refused.contains(&short).is_false().then(|| {
589		self.aliases
590			.get(&short)
591			.map_or((short, None), |(winner, identity)| (*winner, Some(identity)))
592	})
593}
594
595fn unique_keys(state: &CompressedState) -> bool {
596	// Entries order by key half first, so a duplicate key sits beside its twin.
597	state
598		.iter()
599		.map(|entry| parse_compressed_state_event(*entry).0)
600		.tuple_windows()
601		.all(|(left, right)| left != right)
602}
603
604#[tracing::instrument(level = "trace", skip_all)]
605pub(crate) async fn identity(
606	db: &Database,
607	mapping: &Mapping,
608	short: u64,
609	reverse: &str,
610) -> Result<Option<(u64, Identity)>> {
611	let Some((winner, known)) = mapping.resolve(short) else {
612		return Ok(None);
613	};
614
615	match known {
616		| Some(identity) => Ok(Some((winner, identity.clone()))),
617		| None =>
618			lookup(db, reverse, &short.to_be_bytes())
619				.map_ok(|identity| identity.map(|identity| (short, identity)))
620				.await,
621	}
622}
623
624#[tracing::instrument(level = "trace", skip_all)]
625pub(crate) async fn row(db: &Database, id: u64) -> Result<Option<ValBuf>> {
626	fetch(db, "shortstatehash_statediff", &id.to_be_bytes(), ValBuf::from_slice).await
627}
628
629#[tracing::instrument(level = "trace", skip_all)]
630pub(crate) async fn lookup(db: &Database, map: &str, key: &[u8]) -> Result<Option<Identity>> {
631	fetch(db, map, key, Identity::from_slice).await
632}
633
634#[tracing::instrument(level = "trace", skip_all)]
635pub(crate) async fn fetch<T>(
636	db: &Database,
637	map: &str,
638	key: &[u8],
639	convert: impl FnOnce(&[u8]) -> T,
640) -> Result<Option<T>> {
641	db[map]
642		.get(key)
643		.map_ok(|value| convert(&value))
644		.map(NotFound::present)
645		.await
646}
647
648#[tracing::instrument(level = "trace", skip_all)]
649pub(crate) async fn present(db: &Database, map: &str, key: &[u8]) -> Result<bool> {
650	db[map]
651		.exists(key)
652		.map(NotFound::present)
653		.map_ok(|found| found.is_some())
654		.await
655}
656
657pub(crate) fn statekey(kind: &TimelineEventType, state_key: &str) -> Identity {
658	kind.to_cow_str()
659		.as_bytes()
660		.iter()
661		.copied()
662		.chain([SEP])
663		.chain(state_key.as_bytes().iter().copied())
664		.collect()
665}