Skip to main content

tuwunel_service/integrity/short_ids/
identity.rs

1use std::{
2	collections::BTreeMap,
3	hash::{BuildHasher, RandomState},
4	str::from_utf8,
5	sync::Arc,
6};
7
8use futures::{FutureExt, StreamExt, TryStreamExt, future::lazy};
9use ruma::EventId;
10use tuwunel_core::{
11	Result, err,
12	utils::{TryReadyExt, result::NotFound, stream::TryWidebandExt},
13};
14use tuwunel_database::{Database, Map, SEP};
15
16use super::{Identity, short_of};
17use crate::{Services, integrity::ScanExt};
18
19pub(crate) struct Identities {
20	pub(crate) events: Family,
21	pub(crate) statekeys: Family,
22}
23
24pub(crate) struct Family {
25	pub(crate) candidates: Vec<Candidate>,
26	pub(crate) malformed: u64,
27	pub(crate) forward: &'static str,
28	pub(crate) reverse: &'static str,
29
30	/// Number of forward rows claiming each candidate short or alias winner.
31	claims: BTreeMap<u64, u64>,
32
33	/// Number of reverse rows naming each identity whose forward row is absent.
34	reverse_claims: BTreeMap<Identity, u64>,
35}
36
37pub(crate) struct Candidate {
38	pub(crate) short: u64,
39	pub(crate) identity: Identity,
40	pub(crate) kind: Kind,
41}
42
43/// How a candidate row departs from a consistent identity pair.
44///
45/// Healing writes the missing row of an admitted `Reverse` or `Forward`
46/// candidate, and cleanup deletes the reverse row of an admitted `Alias`.
47/// Nothing writes an `Unresolved` row.
48#[derive(Clone, Copy)]
49pub(crate) enum Kind {
50	/// The forward row names a short that has no reverse row.
51	Reverse,
52
53	/// The reverse row names an identity that has no forward row.
54	Forward,
55
56	/// The reverse row names an identity whose forward row names a different
57	/// short, carried here as the winner.
58	Alias(u64),
59
60	/// The row is malformed or contradicts its counterpart.
61	Unresolved,
62}
63
64/// The forward and reverse columns of one short-id family.
65///
66/// The forward column maps each identity to its short id, and the reverse column
67/// maps the short id back.
68#[derive(Clone, Copy)]
69struct Columns {
70	forward: &'static str,
71	reverse: &'static str,
72}
73
74/// Row count, malformed count and order-free digest of one column's pairs.
75///
76/// The digest sums a hash of each `(short, identity)` pair, so row order does
77/// not change it.
78#[derive(Default, Eq, PartialEq)]
79struct Tally {
80	rows: u64,
81	malformed: u64,
82	digest: u64,
83}
84
85const EVENTS: Columns = Columns {
86	forward: "eventid_shorteventid",
87	reverse: "shorteventid_eventid",
88};
89
90const STATEKEYS: Columns = Columns {
91	forward: "statekey_shortstatekey",
92	reverse: "shortstatekey_statekey",
93};
94
95#[tracing::instrument(level = "debug", skip_all)]
96pub(crate) async fn census(services: &Services) -> Result<Identities> {
97	let events = family(services, EVENTS).await?;
98	let statekeys = family(services, STATEKEYS).await?;
99
100	Ok(Identities { events, statekeys })
101}
102
103#[tracing::instrument(level = "debug", skip_all)]
104async fn family(services: &Services, Columns { forward, reverse }: Columns) -> Result<Family> {
105	let db = &services.db;
106	let dangling = db[forward]
107		.raw_stream()
108		.scanned(&services.server)
109		.map_ok(|(identity, short)| decode(short, identity))
110		.wide_and_then(async |(short, identity)| {
111			let kind = match malformed(forward, short, &identity) {
112				| true => Some(Kind::Unresolved),
113				| false => reverse_kind(&db[reverse], short, &identity).await?,
114			};
115
116			Ok(kind.map(|kind| Candidate { short, identity, kind }))
117		});
118
119	// Construction opens a cursor, so the reverse one is deferred until the forward scan ends.
120	let unpointed = lazy(|_| db[reverse].raw_stream())
121		.flatten_stream()
122		.scanned(&services.server)
123		.map_ok(|(short, identity)| decode(short, identity))
124		.wide_and_then(async |(short, identity)| {
125			let kind = match malformed(forward, short, &identity) {
126				| true => Some(Kind::Unresolved),
127				| false => forward_kind(&db[forward], short, &identity).await?,
128			};
129
130			Ok(kind.map(|kind| Candidate { short, identity, kind }))
131		});
132
133	let candidates: Vec<_> = dangling
134		.chain(unpointed)
135		.ready_try_filter_map(Ok)
136		.try_collect()
137		.await?;
138
139	let claims: BTreeMap<u64, u64> = candidates
140		.iter()
141		.flat_map(|candidate| {
142			let winner = match candidate.kind {
143				| Kind::Alias(winner) => Some(winner),
144				| _ => None,
145			};
146
147			[Some(candidate.short), winner]
148				.into_iter()
149				.flatten()
150				.map(|short| (short, 0_u64))
151		})
152		.collect();
153
154	let claims = count_claims(services, forward, claims).await?;
155
156	let reverse_claims: BTreeMap<Identity, u64> = candidates
157		.iter()
158		.filter(|candidate| matches!(candidate.kind, Kind::Forward))
159		.map(|candidate| (candidate.identity.clone(), 0_u64))
160		.collect();
161
162	let reverse_claims = count_reverse_claims(services, reverse, reverse_claims).await?;
163
164	let malformed_rows = candidates
165		.iter()
166		.filter(|candidate| malformed(forward, candidate.short, &candidate.identity))
167		.count()
168		.try_into()
169		.map_err(|_| err!("candidate count exceeds integer width"))?;
170
171	Ok(Family {
172		candidates,
173		malformed: malformed_rows,
174		forward,
175		reverse,
176		claims,
177		reverse_claims,
178	})
179}
180
181fn decode(short: &[u8], identity: &[u8]) -> (u64, Identity) {
182	(short_of(short).unwrap_or_default(), Identity::from_slice(identity))
183}
184
185fn malformed(forward: &str, short: u64, identity: &[u8]) -> bool {
186	short == 0 || !valid(identity, forward == EVENTS.forward)
187}
188
189fn valid(identity: &[u8], event: bool) -> bool {
190	if event {
191		return from_utf8(identity).is_ok_and(|event_id| <&EventId>::try_from(event_id).is_ok());
192	}
193
194	let Some(separator) = identity.iter().position(|byte| *byte == SEP) else {
195		return false;
196	};
197
198	let (event_type, key) = identity.split_at(separator);
199
200	// The spec bounds only an event type's length, so an empty type is well formed.
201	from_utf8(event_type).is_ok() && from_utf8(&key[1..]).is_ok()
202}
203
204#[tracing::instrument(level = "trace", skip_all)]
205async fn reverse_kind(map: &Arc<Map>, short: u64, identity: &[u8]) -> Result<Option<Kind>> {
206	map.get(&short.to_be_bytes())
207		.map(NotFound::present)
208		.await
209		.map(|value| match value.as_deref() {
210			| Some(stored) if stored == identity => None,
211			| Some(_) => Some(Kind::Unresolved),
212			| None => Some(Kind::Reverse),
213		})
214}
215
216#[tracing::instrument(level = "trace", skip_all)]
217async fn forward_kind(map: &Arc<Map>, short: u64, identity: &[u8]) -> Result<Option<Kind>> {
218	map.get(identity)
219		.map(NotFound::present)
220		.await
221		.map(|value| match value.as_deref().map(short_of) {
222			| None => Some(Kind::Forward),
223			| Some(Some(winner)) if winner == short => None,
224			| Some(Some(winner)) => Some(Kind::Alias(winner)),
225			| Some(None) => Some(Kind::Unresolved),
226		})
227}
228
229#[tracing::instrument(level = "debug", skip_all)]
230async fn count_claims(
231	services: &Services,
232	forward: &str,
233	claims: BTreeMap<u64, u64>,
234) -> Result<BTreeMap<u64, u64>> {
235	// Only claims on candidate shorts are counted, so no candidates means no scan.
236	if claims.is_empty() {
237		return Ok(claims);
238	}
239
240	services.db[forward]
241		.raw_stream()
242		.scanned(&services.server)
243		.ready_try_fold(claims, |mut claims: BTreeMap<u64, u64>, (_, value)| {
244			// Prefix width counts an overlong value as a claim, which can only block a repair.
245			if let Some(count) = value
246				.get(..8)
247				.and_then(short_of)
248				.and_then(|short| claims.get_mut(&short))
249			{
250				*count = count.saturating_add(1);
251			}
252
253			Ok(claims)
254		})
255		.await
256}
257
258#[tracing::instrument(level = "debug", skip_all)]
259async fn count_reverse_claims(
260	services: &Services,
261	reverse: &str,
262	claims: BTreeMap<Identity, u64>,
263) -> Result<BTreeMap<Identity, u64>> {
264	if claims.is_empty() {
265		return Ok(claims);
266	}
267
268	services.db[reverse]
269		.raw_stream()
270		.scanned(&services.server)
271		.ready_try_fold(claims, |mut claims: BTreeMap<Identity, u64>, (_, identity)| {
272			if let Some(count) = claims.get_mut(identity) {
273				*count = count.saturating_add(1);
274			}
275
276			Ok(claims)
277		})
278		.await
279}
280
281#[tracing::instrument(level = "trace", skip_all)]
282pub(crate) async fn admitted(
283	db: &Database,
284	family: &Family,
285	candidate: &Candidate,
286) -> Result<bool> {
287	let Candidate { short, identity, kind } = candidate;
288
289	if malformed(family.forward, *short, identity) {
290		return Ok(false);
291	}
292
293	let claims = |short| {
294		family
295			.claims
296			.get(&short)
297			.copied()
298			.unwrap_or_default()
299	};
300
301	let (forward, reverse) = (&db[family.forward], &db[family.reverse]);
302	let accepted = match *kind {
303		| Kind::Unresolved => false,
304		| Kind::Reverse =>
305			claims(*short) == 1
306				&& points_to(forward, identity, *short).await?
307				&& absent(reverse, &short.to_be_bytes()).await?,
308		| Kind::Forward =>
309			claims(*short) == 0
310				&& family.reverse_claims.get(identity) == Some(&1)
311				&& names(reverse, *short, identity).await?
312				&& absent(forward, identity).await?,
313		| Kind::Alias(winner) =>
314			winner != 0
315				&& winner != *short
316				&& claims(*short) == 0
317				&& claims(winner) == 1
318				&& points_to(forward, identity, winner).await?
319				&& names(reverse, *short, identity).await?
320				&& names(reverse, winner, identity).await?,
321	};
322
323	Ok(accepted)
324}
325
326#[tracing::instrument(level = "trace", skip_all)]
327async fn points_to(map: &Arc<Map>, identity: &[u8], short: u64) -> Result<bool> {
328	map.get(identity)
329		.map(NotFound::present)
330		.await
331		.map(|value| value.as_deref().and_then(short_of) == Some(short))
332}
333
334#[tracing::instrument(level = "trace", skip_all)]
335async fn absent(map: &Arc<Map>, key: &[u8]) -> Result<bool> {
336	map.get(key)
337		.map(NotFound::present)
338		.await
339		.map(|value| value.is_none())
340}
341
342#[tracing::instrument(level = "trace", skip_all)]
343async fn names(map: &Arc<Map>, short: u64, identity: &[u8]) -> Result<bool> {
344	map.get(&short.to_be_bytes())
345		.map(NotFound::present)
346		.await
347		.map(|value| value.as_deref() == Some(identity))
348}
349
350/// Whether each short-id family pairs its forward and reverse rows one to one.
351///
352/// It agrees with a census that finds no candidates, reading every row once in
353/// key order and never looking up its counterpart. Columns holding the same
354/// pairs tally equal row counts and digests. Only forward rows are validated,
355/// since a reverse column holding the same pairs holds no others.
356#[tracing::instrument(level = "debug", skip_all)]
357pub(crate) async fn consistent(services: &Services) -> Result<bool> {
358	let hasher = RandomState::new();
359
360	Ok(paired(services, &hasher, EVENTS).await? && paired(services, &hasher, STATEKEYS).await?)
361}
362
363#[tracing::instrument(level = "debug", skip_all)]
364async fn paired(services: &Services, hasher: &RandomState, columns: Columns) -> Result<bool> {
365	let forward = tally(services, hasher, columns, columns.forward).await?;
366	let agree = forward.malformed == 0
367		&& tally(services, hasher, columns, columns.reverse).await? == forward;
368
369	Ok(agree)
370}
371
372#[tracing::instrument(
373	level = "debug",
374	skip_all,
375	fields(
376		%column,
377	),
378)]
379async fn tally(
380	services: &Services,
381	hasher: &RandomState,
382	columns: Columns,
383	column: &str,
384) -> Result<Tally> {
385	let forward = column == columns.forward;
386
387	services.db[column]
388		.raw_stream()
389		.scanned(&services.server)
390		.ready_try_fold(Tally::default(), |tally, (key, value)| {
391			let (short, identity) = match forward {
392				| true => (value, key),
393				| false => (key, value),
394			};
395
396			let short = short_of(short).unwrap_or_default();
397			let invalid = forward && malformed(columns.forward, short, identity);
398
399			Ok(tally.add(hasher, short, identity, invalid))
400		})
401		.await
402}
403
404impl Tally {
405	fn add(self, hasher: &RandomState, short: u64, identity: &[u8], invalid: bool) -> Self {
406		let digest = hasher.hash_one((short, identity));
407
408		Self {
409			rows: self.rows.saturating_add(1),
410			malformed: self.malformed.saturating_add(invalid.into()),
411			digest: self.digest.wrapping_add(digest),
412		}
413	}
414}