tuwunel_service/integrity/short_ids/
rooms.rs1use 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}