Skip to main content

tuwunel_service/integrity/short_ids/
rooms.rs

1use std::{
2	collections::{BTreeMap, BTreeSet},
3	str::from_utf8,
4};
5
6use futures::{
7	Stream, StreamExt, TryStreamExt,
8	future::{ready, try_join},
9};
10use rows::{COLUMNS, SCANNED, decode, hints, word};
11use ruma::RoomId;
12use serde_json::from_slice;
13use tuwunel_core::{
14	Result, err,
15	utils::{BoolExt, IterStream, TryReadyExt, result::NotFound, stream::TryWidebandExt},
16};
17use tuwunel_database::{Database, Interfix};
18use tuwunel_matrix::PduEvent;
19
20use super::sweep;
21use crate::Services;
22
23pub(crate) mod rows;
24
25type Keys = BTreeMap<u64, Vec<Indexed>>;
26
27type Indexed = (usize, Box<[u8]>);
28
29pub(crate) struct Rooms {
30	pub(crate) unfinished: BTreeSet<u64>,
31	pub(crate) unknown: bool,
32	pub(crate) deleted: u64,
33	pub(crate) moved: u64,
34	pub(crate) restored: bool,
35}
36
37#[derive(Default)]
38pub(crate) struct Census {
39	pub(crate) candidates: BTreeSet<u64>,
40	pub(crate) held: BTreeSet<u64>,
41	claims: BTreeMap<u64, usize>,
42	pub(crate) keys: Keys,
43	pub(crate) owner_unknown: bool,
44	residue_unknown: bool,
45}
46
47pub(crate) struct Row {
48	pub(crate) column: usize,
49	pub(crate) key: Box<[u8]>,
50	pub(crate) value: Box<[u8]>,
51}
52
53#[derive(Clone, Copy)]
54pub(crate) enum Action {
55	Purge,
56	Move(u64),
57}
58
59#[tracing::instrument(level = "debug", skip_all)]
60pub(crate) async fn inspect(services: &Services) -> Result<Rooms> {
61	Ok(pending(&census(services).await?))
62}
63
64#[tracing::instrument(level = "debug", skip_all)]
65pub(crate) async fn census(services: &Services) -> Result<Census> {
66	let census = sweep(services, "roomid_shortroomid", Census::default(), owner).await?;
67
68	COLUMNS
69		.into_iter()
70		.enumerate()
71		.try_stream()
72		.try_fold(census, async |census, (column, name)| {
73			sweep(services, name, census, |census, key, value| {
74				residue(census, column, key, value)
75			})
76			.await
77		})
78		.await
79}
80
81fn owner(census: Census, key: &[u8], value: &[u8]) -> Census {
82	let id = value
83		.get(..8)
84		.and_then(word)
85		.filter(|id| *id != 0);
86
87	let valid =
88		from_utf8(key).is_ok_and(|key| <&RoomId>::try_from(key).is_ok()) && word(value).is_some();
89
90	claimed(census, id, valid)
91}
92
93fn claimed(mut census: Census, id: Option<u64>, valid: bool) -> Census {
94	match id {
95		| None => census.owner_unknown = true,
96		| Some(id) => {
97			let claims = census.claims.entry(id).or_default();
98
99			*claims = claims.saturating_add(1);
100			if !valid {
101				census.held.insert(id);
102			}
103		},
104	}
105
106	census
107}
108
109fn residue(census: Census, column: usize, key: &[u8], value: &[u8]) -> Census {
110	let decoded = decode(column, key, value);
111	let ids = decoded
112		.map(|row| row.rooms.map(|id| id.ne(&0).then_some(id)))
113		.unwrap_or_else(|| hints(column, key, value));
114
115	index(census, column, key, ids, decoded.is_some())
116}
117
118fn index(
119	mut census: Census,
120	column: usize,
121	key: &[u8],
122	ids: [Option<u64>; 2],
123	valid: bool,
124) -> Census {
125	census.residue_unknown |= !valid && ids == [None; 2];
126	ids.into_iter()
127		.enumerate()
128		.filter_map(|(position, id)| id.filter(|id| position == 0 || Some(*id) != ids[0]))
129		.for_each(|id| {
130			if !valid || ids.into_iter().flatten().any(|other| other != id) {
131				census.held.insert(id);
132			}
133
134			if !census.claims.contains_key(&id) {
135				census.candidates.insert(id);
136				indexed(&mut census.keys, id, column, key);
137			}
138		});
139
140	census
141}
142
143fn indexed(keys: &mut Keys, id: u64, column: usize, key: &[u8]) {
144	if !SCANNED.contains(&column) {
145		keys.entry(id)
146			.or_default()
147			.push((column, key.into()));
148	}
149}
150
151pub(crate) fn pending(census: &Census) -> Rooms {
152	let unfinished = census
153		.candidates
154		.union(&census.held)
155		.copied()
156		.collect();
157
158	Rooms {
159		unfinished,
160		unknown: census.owner_unknown || census.residue_unknown,
161		deleted: 0,
162		moved: 0,
163		restored: false,
164	}
165}
166
167#[tracing::instrument(level = "trace", skip_all)]
168pub(crate) async fn owned(
169	services: &Services,
170	candidate: u64,
171	keys: &[Indexed],
172) -> Result<Vec<Row>> {
173	let prefix = candidate.to_be_bytes();
174	let scanned = SCANNED
175		.stream()
176		.map(|column| scan(services, column, &prefix))
177		.flatten();
178
179	let indexed = keys
180		.iter()
181		.try_stream()
182		.wide_and_then(async |(column, key)| {
183			services.server.check_running()?;
184			let value = lookup(&services.db, COLUMNS[*column], key, |value| value.map(Box::from))
185				.await?
186				.ok_or_else(|| err!("room residue changed during census"))?;
187
188			Ok(Row { column: *column, key: key.clone(), value })
189		});
190
191	scanned.chain(indexed).try_collect().await
192}
193
194fn scan<'a>(
195	services: &'a Services,
196	column: usize,
197	prefix: &'a [u8],
198) -> impl Stream<Item = Result<Row>> + Send + 'a {
199	services.db[COLUMNS[column]]
200		.raw_stream_prefix(prefix)
201		.ready_and_then(move |(key, value)| {
202			services.server.check_running()?;
203			Ok(Row {
204				column,
205				key: key.into(),
206				value: value.into(),
207			})
208		})
209}
210
211#[tracing::instrument(level = "trace", skip_all)]
212pub(crate) async fn lookup<T>(
213	db: &Database,
214	column: &str,
215	key: &[u8],
216	project: impl FnOnce(Option<&[u8]>) -> T + Send,
217) -> Result<T> {
218	db[column]
219		.get(key)
220		.await
221		.present()
222		.map(|value| project(value.as_deref()))
223}
224
225#[tracing::instrument(level = "trace", skip_all)]
226pub(crate) async fn classify(
227	services: &Services,
228	census: &Census,
229	candidate: u64,
230	rows: &[Row],
231) -> Result<Option<Action>> {
232	if rows.iter().any(|row| !unmixed(row, candidate)) || dangling(rows) {
233		return Ok(None);
234	}
235
236	let Some(pdu) = rows
237		.iter()
238		.find(|row| row.column == 0)
239		.and_then(pdu)
240	else {
241		return Ok(None);
242	};
243
244	let room = &pdu.room_id;
245	let invalid = rows
246		.iter()
247		.filter(|row| row.column == 0)
248		.try_stream()
249		.wide_and_then(|row| misindexed(services, room, row))
250		.try_any(ready)
251		.await?;
252
253	if invalid {
254		return Ok(None);
255	}
256
257	let forward =
258		lookup(&services.db, "roomid_shortroomid", room.as_bytes(), |forward| forward.map(word));
259
260	let pointer = lookup(&services.db, "roomid_shortstatehash", room.as_bytes(), |pointer| {
261		pointer.is_some()
262	});
263
264	let (forward, pointer) = try_join(forward, pointer).await?;
265
266	let movable = |id: &u64| {
267		*id != 0
268			&& *id != candidate
269			&& census.claims.get(id) == Some(&1)
270			&& !census.held.contains(id)
271	};
272
273	let action = match (forward, pointer) {
274		| (None, false) if !census.residue_unknown => has_leaves(services, room)
275			.await?
276			.is_false()
277			.then_some(Action::Purge),
278		| (Some(forward), true) => has_leaves(services, room)
279			.await?
280			.into_option()
281			.and_then(|()| forward.filter(movable))
282			.map(Action::Move),
283		| _ => None,
284	};
285
286	Ok(action)
287}
288
289fn unmixed(row: &Row, candidate: u64) -> bool {
290	decode(row.column, &row.key, &row.value).is_some_and(|row| {
291		row.rooms
292			.into_iter()
293			.all(|id| id == 0 || id == candidate)
294	})
295}
296
297fn dangling(rows: &[Row]) -> bool {
298	let pdus: BTreeSet<&[u8]> = rows
299		.iter()
300		.filter(|row| row.column == 0)
301		.map(|row| &*row.key)
302		.collect();
303
304	rows.iter()
305		.filter(|row| row.column == 1)
306		.any(|row| !pdus.contains(&*row.value))
307}
308
309fn pdu(row: &Row) -> Option<PduEvent> { from_slice(&row.value).ok() }
310
311async fn misindexed(services: &Services, room: &RoomId, row: &Row) -> Result<bool> {
312	let Some(pdu) = pdu(row).filter(|pdu| pdu.room_id == room) else {
313		return Ok(true);
314	};
315
316	lookup(&services.db, COLUMNS[1], pdu.event_id.as_bytes(), |mapping| {
317		mapping != Some(&*row.key)
318	})
319	.await
320}
321
322async fn has_leaves(services: &Services, room: &RoomId) -> Result<bool> {
323	services.db["roomid_pduleaves"]
324		.keys_prefix_raw(&(room, Interfix))
325		.take(1)
326		.ready_try_fold(false, |_, _| Ok(true))
327		.await
328}