Skip to main content

tuwunel_service/migrations/injectivity/seen/
state.rs

1use std::{
2	collections::{BTreeMap, BTreeSet},
3	iter::once,
4};
5
6use futures::{TryFutureExt, TryStreamExt};
7use tuwunel_core::{
8	Err, Result, err,
9	itertools::Itertools,
10	smallvec::SmallVec,
11	utils::{
12		IterStream, TryReadyExt,
13		hash::sha256::{concat, hash},
14		stream::TryBroadbandExt,
15	},
16};
17use tuwunel_database::{Database, Txn, TxnError};
18
19use super::identity::clear_cache;
20use crate::{
21	Services,
22	integrity::{
23		ScanExt,
24		short_ids::{
25			identity::{Identities, census as census_identities},
26			state::{
27				Aliases, Mapping, Materialized, Parents, Projection, ancestors, claim, decode,
28				depth, descendants, fetch,
29				history::{
30					References as Historical, references as history_references,
31					target as historical_target,
32				},
33				mapping, materialize, present, project, survey,
34			},
35		},
36	},
37	rooms::state_compressor::CompressedState,
38};
39
40pub(super) mod gc;
41mod orphan;
42#[cfg(test)]
43mod tests;
44
45use self::orphan::recover;
46
47type Claimed = BTreeMap<u64, Digests>;
48type Digests = SmallVec<[Digest; 1]>;
49type Digest = (SmallVec<[u8; 32]>, SmallVec<[u8; 8]>);
50
51const PARENTLESS: [u8; 8] = [0; 8];
52
53pub(super) struct States {
54	pub(super) unfinished: BTreeSet<u64>,
55	pub(super) rewritten: u64,
56	pub(super) original_bytes: u64,
57	pub(super) snapshot_bytes: u64,
58	pub(super) uncertain: bool,
59	pub(super) restored: bool,
60}
61
62struct Target {
63	original: [u8; 32],
64	snapshot: [u8; 32],
65}
66
67#[derive(Clone, Copy)]
68enum Operation {
69	Publish,
70	Restore,
71}
72
73enum Publication {
74	Applied(usize, usize),
75	Retained,
76	Restored,
77}
78
79#[tracing::instrument(level = "debug", skip_all)]
80pub(super) async fn repair(
81	services: &Services,
82	identities: Identities,
83) -> Result<(States, Identities)> {
84	let census = survey(services, &identities).await?;
85	let affected = descendants(&census.parents, &census.seeds);
86	let uncertain = census.unknown || !census.held.is_empty();
87	let pending = |unfinished| States {
88		unfinished,
89		rewritten: 0,
90		original_bytes: 0,
91		snapshot_bytes: 0,
92		uncertain,
93		restored: false,
94	};
95
96	if census.unknown {
97		return Ok((pending(affected), identities));
98	}
99
100	// The summaries clear before any snapshot or reinstated reverse row is written.
101	if !affected.is_empty() || !census.orphans.is_empty() {
102		clear_cache(services, "roomid_spacehierarchy").await?;
103	}
104
105	let recovered = recover(services, &census).await?;
106	let identities = match recovered.is_empty() {
107		| true => identities,
108		| false => census_identities(services).await?,
109	};
110
111	let projection = match recovered.is_empty() {
112		| true => census.projection,
113		| false => {
114			let statekeys = mapping(services, &identities.statekeys).await?;
115
116			with_recovered(census.projection, &recovered, statekeys)
117		},
118	};
119
120	let digests = digests(services, &affected).await?;
121	let historical = descendants(&census.parents, &census.exposed);
122	let history = history_references(services, historical).await?;
123
124	// Serial: each target holds a full state in memory, and history fans out within it.
125	let targets: BTreeMap<_, _> = affected
126		.iter()
127		.copied()
128		.try_stream()
129		.and_then(async |id| {
130			services.server.check_running()?;
131			target(services, &projection, &history, id)
132				.map_ok(|target| (id, target))
133				.await
134		})
135		.try_collect()
136		.await?;
137
138	let blocked = targets
139		.iter()
140		.filter(|(_, target)| target.is_none())
141		.map(|(id, _)| *id)
142		.chain(census.held.iter().copied())
143		.flat_map(|id| ancestors(&census.parents, id))
144		.collect();
145
146	let order = affected
147		.iter()
148		.filter_map(|id| depth(&census.parents, *id).map(|depth| (depth, *id)))
149		.sorted_unstable()
150		.rev();
151
152	let publish_next = async |(states, blocked): (States, BTreeSet<u64>),
153	                          (_, id): (usize, u64)| {
154		if blocked.contains(&id) {
155			return Ok((states, blocked));
156		}
157
158		let Some(Some(target)) = targets.get(&id) else {
159			return Ok((states, block(blocked, &census.parents, id)));
160		};
161
162		let digests = digests
163			.get(&id)
164			.map(Digests::as_slice)
165			.unwrap_or_default();
166
167		publish(services, &projection, &history, id, target, digests)
168			.map_ok(|published| match published {
169				| Publication::Applied(original, snapshot) =>
170					(accepted(states, id, original, snapshot), blocked),
171				| Publication::Retained => (states, block(blocked, &census.parents, id)),
172				| Publication::Restored =>
173					(restored(states), block(blocked, &census.parents, id)),
174			})
175			.await
176	};
177
178	order
179		.try_stream()
180		.try_fold((pending(affected), blocked), publish_next)
181		.map_ok(|(states, _)| (states, identities))
182		.await
183}
184
185fn block(mut blocked: BTreeSet<u64>, parents: &Parents, id: u64) -> BTreeSet<u64> {
186	blocked.extend(ancestors(parents, id));
187	blocked
188}
189
190#[tracing::instrument(level = "trace", skip_all)]
191async fn digests(services: &Services, affected: &BTreeSet<u64>) -> Result<Claimed> {
192	if affected.is_empty() {
193		return Ok(Claimed::new());
194	}
195
196	let gather = |mut digests: Claimed, (key, value): (&[u8], &[u8])| {
197		let Some(id) = claim(value).filter(|id| affected.contains(id)) else {
198			return Ok(digests);
199		};
200
201		digests
202			.entry(id)
203			.or_default()
204			.push((SmallVec::from_slice(key), SmallVec::from_slice(value)));
205
206		Ok(digests)
207	};
208
209	services.db["statehash_shortstatehash"]
210		.raw_stream()
211		.scanned(&services.server)
212		.ready_try_fold(Claimed::new(), gather)
213		.await
214}
215
216#[tracing::instrument(level = "trace", skip_all)]
217async fn target(
218	services: &Services,
219	projection: &Projection,
220	history: &Historical,
221	id: u64,
222) -> Result<Option<Target>> {
223	prepared(services, projection, history, id)
224		.map_ok(|prepared| {
225			prepared.map(|(original, state)| Target {
226				original: hash(original),
227				snapshot: fingerprint(&state),
228			})
229		})
230		.await
231}
232
233#[tracing::instrument(level = "trace", skip_all)]
234async fn prepared(
235	services: &Services,
236	projection: &Projection,
237	history: &Historical,
238	id: u64,
239) -> Result<Materialized> {
240	if history.affected.contains(&id) {
241		return historical_target(services, projection, history, id).await;
242	}
243
244	let Some((original, state)) = materialize(services, id).await? else {
245		return Ok(None);
246	};
247
248	Ok(project(state, projection).map(|state| (original, state)))
249}
250
251fn fingerprint(state: &CompressedState) -> [u8; 32] {
252	concat(once(PARENTLESS.as_slice()).chain(state.iter().map(AsRef::as_ref)))
253}
254
255fn with_recovered(
256	mut projection: Projection,
257	recovered: &Aliases,
258	statekeys: Mapping,
259) -> Projection {
260	projection
261		.statekeys
262		.refused
263		.retain(|short| !recovered.contains_key(short));
264
265	projection
266		.statekeys
267		.refused
268		.extend(statekeys.refused);
269
270	projection.statekeys.aliases = statekeys.aliases;
271
272	projection
273}
274
275#[tracing::instrument(level = "trace", skip_all)]
276async fn publish(
277	services: &Services,
278	projection: &Projection,
279	history: &Historical,
280	id: u64,
281	target: &Target,
282	digests: &[Digest],
283) -> Result<Publication> {
284	services.server.check_running()?;
285	let db = &services.db;
286	let Some((original, state)) = prepared(services, projection, history, id).await? else {
287		return Ok(Publication::Retained);
288	};
289
290	let snapshot = encode(&state)?;
291
292	decode(&snapshot)
293		.filter(|diff| diff.parent.is_none() && diff.removed.is_empty() && diff.added == state)
294		.ok_or_else(|| err!("snapshot prepublication verification failed"))?;
295
296	if hash(&original) != target.original || hash(&snapshot) != target.snapshot {
297		return Err!("snapshot target changed after preflight");
298	}
299
300	if !digests_match(db, digests).await? {
301		return Err!("snapshot digest changed after preflight");
302	}
303
304	commit(services, transaction(db, id, &snapshot, digests, Operation::Publish))
305		.map_err(|error| err!("{error}"))?;
306
307	if holds(db, id, &snapshot).await? && digests_absent(db, digests).await? {
308		return Ok(Publication::Applied(original.len(), snapshot.len()));
309	}
310
311	commit(services, transaction(db, id, &original, digests, Operation::Restore))
312		.map_err(|error| err!("snapshot restoration failed: {error}"))?;
313
314	if !holds(db, id, &original).await? {
315		return Err!("snapshot restoration verification failed");
316	}
317
318	if !digests_match(db, digests).await? {
319		return Err!("digest restoration verification failed");
320	}
321
322	Ok(Publication::Restored)
323}
324
325fn encode(state: &CompressedState) -> Result<Vec<u8>> {
326	let capacity = state
327		.len()
328		.checked_mul(16)
329		.and_then(|size| size.checked_add(8))
330		.ok_or_else(|| err!("snapshot size overflow"))?;
331
332	encoded(state, capacity)
333}
334
335fn encoded(state: &CompressedState, capacity: usize) -> Result<Vec<u8>> {
336	let mut bytes = Vec::new();
337
338	bytes
339		.try_reserve_exact(capacity)
340		.map_err(|error| err!("{error}"))?;
341
342	bytes.extend(PARENTLESS);
343	bytes.extend(state.iter().flatten());
344	Ok(bytes)
345}
346
347#[tracing::instrument(level = "trace", skip_all)]
348async fn digests_match(db: &Database, digests: &[Digest]) -> Result<bool> {
349	digests
350		.try_stream()
351		.broad_try_all(|(key, value)| {
352			db["statehash_shortstatehash"]
353				.get(key)
354				.map_ok(move |current| current.as_ref() == value.as_slice())
355		})
356		.await
357}
358
359fn transaction(
360	db: &Database,
361	id: u64,
362	bytes: &[u8],
363	digests: &[Digest],
364	operation: Operation,
365) -> Txn {
366	let statehashes = &db["statehash_shortstatehash"];
367	let txn = digests
368		.iter()
369		.fold(db.txn(), |mut txn, (key, value)| {
370			match operation {
371				| Operation::Publish => txn.del_raw(statehashes, key),
372				| Operation::Restore => txn.insert_raw(statehashes, key, value),
373			}
374
375			txn
376		});
377
378	once((id.to_be_bytes(), bytes)).fold(txn, |mut txn, (key, bytes)| {
379		txn.insert_raw(&db["shortstatehash_statediff"], key, bytes);
380		txn
381	})
382}
383
384fn commit(services: &Services, txn: Txn) -> Result<(), TxnError> {
385	// Acquire before acceptance, then clear even on accepted-write sync failure.
386	let mut cache = services
387		.state_compressor
388		.stateinfo_cache
389		.lock()
390		.map_err(|_| TxnError::Write(err!("state cache lock poisoned")))?;
391
392	let written = txn.try_execute();
393
394	if !matches!(written, Err(TxnError::Write(_))) {
395		cache.clear();
396	}
397
398	written
399}
400
401#[tracing::instrument(level = "trace", skip_all)]
402async fn holds(db: &Database, id: u64, bytes: &[u8]) -> Result<bool> {
403	fetch(db, "shortstatehash_statediff", &id.to_be_bytes(), |value| value == bytes)
404		.map_ok(Option::unwrap_or_default)
405		.await
406}
407
408#[tracing::instrument(level = "trace", skip_all)]
409async fn digests_absent(db: &Database, digests: &[Digest]) -> Result<bool> {
410	digests
411		.try_stream()
412		.broad_try_all(|(key, _)| {
413			present(db, "statehash_shortstatehash", key).map_ok(|found| !found)
414		})
415		.await
416}
417
418fn accepted(mut states: States, id: u64, original_len: usize, snapshot_len: usize) -> States {
419	states.unfinished.remove(&id);
420	states.rewritten = states.rewritten.saturating_add(1);
421	states.original_bytes = states
422		.original_bytes
423		.saturating_add(u64::try_from(original_len).unwrap_or(u64::MAX));
424
425	states.snapshot_bytes = states
426		.snapshot_bytes
427		.saturating_add(u64::try_from(snapshot_len).unwrap_or(u64::MAX));
428
429	states
430}
431
432fn restored(states: States) -> States { States { restored: true, ..states } }