Skip to main content

tuwunel_service/integrity/
relatesto_typed.rs

1//! The relation index `relatesto_typed`.
2//!
3//! An edit or a reference is indexed under its parent, so a parent's edits and
4//! references are found without loading its other children. A row holds the
5//! child's short event id. The index derives from `pduid_pdu`, and its rebuild
6//! clears it before writing it again.
7
8use std::{fmt, sync::Arc};
9
10use futures::{Stream, StreamExt};
11use ruma::OwnedEventId;
12use tuwunel_core::{
13	Error, Result,
14	result::NotFound,
15	utils::{BoolExt, TryReadyExt, stream::TryBroadbandExt},
16};
17use tuwunel_database::{KeyBuf, KeyVal, Map};
18use tuwunel_matrix::{Pdu, PduId, RawPduId};
19
20use super::{Check, Report, ScanExt, tally};
21use crate::{
22	Services,
23	rooms::pdu_metadata::typed_relations::{Derived, Key, key_child},
24};
25
26pub(super) static CHECK: Check = Check {
27	name: "relation-index",
28	about: "relatesto_typed holds every row its rebuild derives from the timeline, and no other",
29	quiescent: true,
30	walk: |services, limit| tally(scan(services), limit),
31};
32
33/// A `relatesto_typed` row the timeline disagrees with, or an event it cannot
34/// read.
35///
36/// The rebuild writes every row the timeline derives and removes every other, so
37/// it repairs all but an unparsable event, an unreadable parent mapping or a
38/// malformed short id. A row whose child is absent is residue a history purge
39/// leaves on a healthy server, not damage.
40pub enum Finding {
41	/// An edit or a reference has no index row.
42	Missing {
43		/// The key the row belongs under.
44		key: Key,
45
46		/// The edit or reference.
47		child: OwnedEventId,
48	},
49
50	/// The row of an edit or a reference holds another event's short id.
51	Mismatched {
52		/// The row's key.
53		key: Key,
54
55		/// The edit or reference.
56		child: OwnedEventId,
57	},
58
59	/// The child's `eventid_shorteventid` value is not a short id, so whether its
60	/// row holds the right one is unknown.
61	MalformedShort {
62		/// The row's key.
63		key: Key,
64
65		/// The edit or reference.
66		child: OwnedEventId,
67	},
68
69	/// The row names a child with no event behind it, as a history purge leaves.
70	AbsentChild {
71		/// The row's key.
72		key: Key,
73	},
74
75	/// The row names a stored child that no longer derives it.
76	Stale {
77		/// The row's key.
78		key: Key,
79	},
80
81	/// The row's key has a length the index never writes.
82	UnparsableKey {
83		/// The stored key.
84		key: KeyBuf,
85	},
86
87	/// An event row does not decode as an event, so its relation is unknown.
88	UnparsableEvent {
89		/// The event row's key.
90		pdu_id: RawPduId,
91	},
92
93	/// An edit or a reference names a parent whose `eventid_pduid` value is not a
94	/// PDU id, so its row is unknown.
95	UnreadableParent {
96		/// The edit or reference.
97		child: OwnedEventId,
98
99		/// The parent it names.
100		parent: OwnedEventId,
101	},
102}
103
104/// One row the index should hold.
105///
106/// The rebuild writes the child's short event id under the key, creating the
107/// short id when the child has none.
108pub struct Row {
109	/// The row's key, naming the parent and the child.
110	pub key: Key,
111
112	/// The child, whose short event id the row holds.
113	pub child: OwnedEventId,
114}
115
116/// What one event row gives the index.
117///
118/// An event that does not decode, or names a parent whose mapping is unreadable,
119/// gives no row to write, but the check reports it. A parent lookup that fails
120/// gives no row either: the check returns its error, while the rebuild skips the
121/// relation and counts it.
122pub(crate) enum Expected {
123	/// The event's row.
124	Row(Row),
125
126	/// The event row does not decode as an event.
127	Unparsable(RawPduId),
128
129	/// The event's parent maps to a value that is not a PDU id.
130	UnreadableParent {
131		/// The edit or reference.
132		child: OwnedEventId,
133
134		/// The parent it names.
135		parent: OwnedEventId,
136	},
137
138	/// The lookup of the event's parent failed other than as absent.
139	Unresolved {
140		/// The event row's key.
141		pdu_id: RawPduId,
142
143		/// What the lookup returned.
144		error: Error,
145	},
146}
147
148// The event is `None` when the row's value does not decode.
149type Source = (RawPduId, Option<Pdu>);
150
151/// Streams each row the index lacks or should not hold, and each event that
152/// cannot be read.
153///
154/// The timeline's rows are read by key against the index, then the index is
155/// walked for rows no stored event derives, since the two sort differently. An
156/// event row whose key is not a PDU id is skipped, as the timestamp index check
157/// reports it.
158#[tracing::instrument(level = "trace", skip_all)]
159pub fn scan(services: &Services) -> impl Stream<Item = Result<Finding>> + Send + '_ {
160	let index = &services.db["relatesto_typed"];
161
162	expected(services)
163		.broad_and_then(async |expected| verify(services, index, expected).await)
164		.chain(stale(services))
165		.ready_try_filter_map(Ok)
166}
167
168/// Streams the row each edit and reference gives the index.
169///
170/// The check compares these with the index and the rebuild writes every one, so
171/// the two agree on what the index should hold.
172#[tracing::instrument(level = "trace", skip_all)]
173pub(crate) fn expected(services: &Services) -> impl Stream<Item = Result<Expected>> + Send + '_ {
174	services.db["pduid_pdu"]
175		.raw_scan()
176		.scanned(&services.server)
177		.ready_try_filter_map(|row| Ok(source(row)))
178		.broad_and_then(async |source| derive(services, source).await)
179		.ready_try_filter_map(Ok)
180}
181
182impl Report for Finding {
183	fn kind(&self) -> &'static str {
184		match self {
185			| Self::Missing { .. } => "missing-row",
186			| Self::Mismatched { .. } => "mismatched-child",
187			| Self::MalformedShort { .. } => "malformed-short-id",
188			| Self::AbsentChild { .. } => "absent-child",
189			| Self::Stale { .. } => "stale-row",
190			| Self::UnparsableKey { .. } => "unparsable-key",
191			| Self::UnparsableEvent { .. } => "unparsable-event",
192			| Self::UnreadableParent { .. } => "unreadable-parent",
193		}
194	}
195}
196
197impl fmt::Display for Finding {
198	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
199		match self {
200			| Self::Missing { child, .. } => write!(f, "relation {child} has no index row"),
201			| Self::Mismatched { child, .. } => {
202				write!(f, "index row of relation {child} holds another short id")
203			},
204			| Self::MalformedShort { child, .. } => {
205				write!(f, "relation {child} has a short event id that is not eight bytes")
206			},
207			| Self::AbsentChild { key } => write!(
208				f,
209				"index row names a child with no event behind it, as a history purge leaves; \
210				 the rebuild drops it: {}",
211				key.escape_ascii()
212			),
213			| Self::Stale { key } => {
214				write!(f, "index row no longer derives from its child: {}", key.escape_ascii())
215			},
216			| Self::UnparsableKey { key } => {
217				write!(f, "index key has the wrong length: {}", key.escape_ascii())
218			},
219			| Self::UnparsableEvent { pdu_id } => {
220				write!(f, "event {pdu_id:?} does not decode as an event")
221			},
222			| Self::UnreadableParent { child, parent } => {
223				write!(f, "relation {child} names {parent}, whose PDU id cannot be read")
224			},
225		}
226	}
227}
228
229fn source((key, value): KeyVal<'_>) -> Option<Source> {
230	let pdu_id = RawPduId::try_from_bytes(key)?;
231
232	Some((pdu_id, serde_json::from_slice(value).ok()))
233}
234
235#[tracing::instrument(level = "debug", skip_all)]
236async fn derive(services: &Services, (pdu_id, pdu): Source) -> Result<Option<Expected>> {
237	let Some(pdu) = pdu else {
238		return Ok(Some(Expected::Unparsable(pdu_id)));
239	};
240
241	let key = services
242		.pdu_metadata
243		.typed_relation_key(pdu_id.into(), &pdu)
244		.await;
245
246	let expected = match key {
247		| Ok(Derived::Unindexed) => None,
248		| Ok(Derived::Key(key)) => Some(Expected::Row(Row { key, child: pdu.event_id })),
249		| Ok(Derived::UnreadableParent(parent)) =>
250			Some(Expected::UnreadableParent { child: pdu.event_id, parent }),
251		| Err(error) => Some(Expected::Unresolved { pdu_id, error }),
252	};
253
254	Ok(expected)
255}
256
257#[tracing::instrument(level = "debug", skip_all)]
258async fn verify(
259	services: &Services,
260	index: &Arc<Map>,
261	expected: Expected,
262) -> Result<Option<Finding>> {
263	let Row { key, child } = match expected {
264		| Expected::Row(row) => row,
265		| Expected::Unparsable(pdu_id) => {
266			return Ok(Some(Finding::UnparsableEvent { pdu_id }));
267		},
268		| Expected::UnreadableParent { child, parent } => {
269			return Ok(Some(Finding::UnreadableParent { child, parent }));
270		},
271		| Expected::Unresolved { error, .. } => return Err(error),
272	};
273
274	let Some(stored) = index
275		.get(key.as_slice())
276		.await
277		.optional()?
278		.map(|short| <[u8; 8]>::try_from(&*short).ok())
279	else {
280		return Ok(Some(Finding::Missing { key, child }));
281	};
282
283	let short = services.db["eventid_shorteventid"]
284		.get(&child)
285		.await
286		.optional()?
287		.map(|short| <[u8; 8]>::try_from(&*short));
288
289	let short = match short {
290		| Some(Err(_)) => return Ok(Some(Finding::MalformedShort { key, child })),
291		| short => short.and_then(Result::ok),
292	};
293
294	let mismatched = stored
295		.zip(short)
296		.is_none_or(|(stored, short)| stored != short);
297
298	let finding = mismatched.then_some(Finding::Mismatched { key, child });
299
300	Ok(finding)
301}
302
303/// Streams each index row no stored event derives, and each unparsable key.
304///
305/// A row's child is read by key and derived again, and a row it does not derive
306/// is one the rebuild drops.
307fn stale(services: &Services) -> impl Stream<Item = Result<Option<Finding>>> + Send + '_ {
308	let pdus = &services.db["pduid_pdu"];
309
310	services.db["relatesto_typed"]
311		.raw_scan()
312		.scanned(&services.server)
313		.ready_and_then(|(key, _)| Ok(stored(key).ok_or_else(|| KeyBuf::from_slice(key))))
314		.broad_and_then(async |stored| match stored {
315			| Err(key) => Ok(Some(Finding::UnparsableKey { key })),
316			| Ok((key, child)) => derives(services, pdus, key, child).await,
317		})
318}
319
320fn stored(key: &[u8]) -> Option<(Key, PduId)> {
321	let child = key_child(key)?;
322
323	Some((Key::try_from(key).ok()?, child))
324}
325
326#[tracing::instrument(level = "debug", skip_all)]
327async fn derives(
328	services: &Services,
329	pdus: &Arc<Map>,
330	key: Key,
331	child: PduId,
332) -> Result<Option<Finding>> {
333	let pdu_id: RawPduId = child.into();
334	let Some(pdu) = pdus
335		.get(&pdu_id)
336		.await
337		.optional()?
338		.map(|pdu| serde_json::from_slice::<Pdu>(&pdu))
339	else {
340		return Ok(Some(Finding::AbsentChild { key }));
341	};
342
343	let derives = match pdu {
344		| Err(_) => false,
345		| Ok(pdu) => matches!(
346			services
347				.pdu_metadata
348				.typed_relation_key(child, &pdu)
349				.await?,
350			Derived::Key(derived) if derived == key
351		),
352	};
353
354	let finding = derives
355		.is_false()
356		.then_some(Finding::Stale { key });
357
358	Ok(finding)
359}