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 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 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 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 } }