tuwunel_service/rooms/event_handler/
fetch_prev.rs1use std::{collections::HashMap, iter::once, time::Duration};
2
3use futures::{
4 FutureExt, StreamExt, TryStreamExt,
5 stream::{FuturesOrdered, FuturesUnordered},
6};
7use ruma::{
8 CanonicalJsonObject, CanonicalJsonValue, EventId, MilliSecondsSinceUnixEpoch, OwnedEventId,
9 RoomId, RoomVersionId, ServerName, int, uint,
10};
11use serde_json::value::RawValue as RawJsonValue;
12use tokio::time::{Instant, timeout_at};
13use tuwunel_core::{
14 Result, err, implement,
15 utils::{
16 BoolExt,
17 stream::{IterStream, automatic_width},
18 },
19};
20use tuwunel_matrix::{
21 Event, PduEvent,
22 event::gen_event_id,
23 pdu::{MAX_PREV_EVENTS, check_room_id},
24 room::state::resolution::topological_sort,
25};
26
27use super::handle_prev_pdu::PrevUpgrade;
28use crate::fetcher::{EventWindow, Op, Opts};
29
30pub(super) type Pdus = HashMap<OwnedEventId, (PduEvent, CanonicalJsonObject)>;
31
32pub(super) struct PrevFetch {
37 pub(super) sorted: Vec<OwnedEventId>,
40
41 pub(super) pdus: Pdus,
43
44 pub(super) capped: bool,
46}
47
48#[implement(super::Service)]
54#[tracing::instrument(
55 level = "debug",
56 skip_all,
57 fields(
58 %origin,
59 events = %initial_set.clone().count(),
60 ),
61)]
62pub(super) async fn fetch_prev<'a, Events>(
63 &self,
64 PrevUpgrade {
65 origin,
66 room_id,
67 event_id: incoming_event_id,
68 room_version,
69 recursion_level,
70 first_normal_ts,
71 ..
72 }: PrevUpgrade<'_>,
73 initial_set: Events,
74) -> Result<PrevFetch>
75where
76 Events: Iterator<Item = &'a EventId> + Clone + Send,
77{
78 let has_gap = initial_set
79 .clone()
80 .stream()
81 .any(async |event_id| !self.services.timeline.pdu_exists(event_id).await)
82 .await;
83
84 let wait_ms = self
85 .services
86 .server
87 .config
88 .federation
89 .history
90 .fetch_prev_wait_ms;
91
92 let has_gap = (has_gap && wait_ms > 0)
93 .then_async(|| self.await_prev_gap(initial_set.clone(), Duration::from_millis(wait_ms)))
94 .await
95 .unwrap_or(has_gap);
96
97 has_gap
98 .then_async(|| {
99 self.prefetch_missing_events(
100 origin,
101 room_id,
102 incoming_event_id,
103 room_version,
104 recursion_level,
105 )
106 })
107 .await;
108
109 let mut todo_outlier_stack: FuturesOrdered<_> = initial_set
110 .try_stream()
111 .map_ok(ToOwned::to_owned)
112 .try_filter_map(async |event_id| {
113 match self
116 .services
117 .timeline
118 .get_non_outlier_pdu(&event_id)
119 .await
120 {
121 | Ok(pdu) => check_room_id(&pdu, room_id).map(|()| None),
122 | Err(_) => Ok(Some(event_id)),
123 }
124 })
125 .map_ok(async |event_id| {
126 let events = once(event_id.as_ref());
127 let auth = self
128 .fetch_auth(origin, room_id, events, room_version, recursion_level)
129 .await;
130
131 (event_id, auth)
132 })
133 .map_ok(FutureExt::boxed) .try_collect()
135 .await?;
136
137 let limit: usize = self
138 .services
139 .server
140 .config
141 .federation
142 .history
143 .max_fetch_prev_events
144 .into();
145
146 let mut amount = 0_usize;
147 let mut pdus = HashMap::new();
148 let mut graph: HashMap<OwnedEventId, _> = HashMap::with_capacity(todo_outlier_stack.len());
149
150 while let Some((prev_event_id, mut outlier)) = todo_outlier_stack.next().await {
151 self.services.server.check_running()?;
152
153 let Some((pdu, mut json_opt)) = outlier.pop() else {
154 graph.insert(prev_event_id.clone(), Default::default());
156 continue;
157 };
158
159 check_room_id(&pdu, room_id)?;
160
161 if amount > limit {
162 amount = amount.saturating_add(1);
164 graph.insert(prev_event_id.clone(), Default::default());
165 continue;
166 }
167
168 if json_opt.is_none() {
169 json_opt = self
170 .services
171 .timeline
172 .get_outlier_pdu_json(&prev_event_id)
173 .await
174 .ok();
175 }
176
177 let Some(json) = json_opt else {
178 graph.insert(prev_event_id.clone(), Default::default());
180 continue;
181 };
182
183 if pdu.origin_server_ts() >= first_normal_ts {
186 amount = amount.saturating_add(1);
187 debug_assert!(
188 pdu.prev_events().count() <= MAX_PREV_EVENTS,
189 "PduEvent {prev_event_id} has too many prev_events"
190 );
191
192 for prev_prev in pdu.prev_events() {
193 if graph.contains_key(prev_prev) {
194 continue;
195 }
196
197 let prev_prev = prev_prev.to_owned();
198 let fetch = async move {
199 let fetch = self
200 .fetch_auth(
201 origin,
202 room_id,
203 once(prev_prev.as_ref()),
204 room_version,
205 recursion_level,
206 )
207 .await;
208
209 (prev_prev, fetch)
210 };
211
212 todo_outlier_stack.push_back(fetch.boxed()); }
214
215 graph.insert(
216 prev_event_id.clone(),
217 pdu.prev_events().map(ToOwned::to_owned).collect(),
218 );
219 } else {
220 graph.insert(prev_event_id.clone(), Default::default());
222 }
223
224 pdus.insert(prev_event_id.clone(), (pdu, json));
225 }
226
227 let event_fetch = async |event_id: OwnedEventId| {
228 let origin_server_ts = pdus
229 .get(&event_id)
230 .map_or_else(|| uint!(0), |info| info.0.origin_server_ts().get());
231
232 Ok((int!(0).into(), MilliSecondsSinceUnixEpoch(origin_server_ts)))
236 };
237
238 let graph_len = graph.len();
239 let sorted = topological_sort(graph, &event_fetch)
240 .await
241 .map_err(|e| err!(Database(error!("Error sorting prev events: {e}"))))?;
242
243 debug_assert_eq!(
244 sorted.len(),
245 graph_len,
246 "topological sort returned a different number of outputs than inputs"
247 );
248
249 debug_assert!(
250 sorted.len() >= pdus.len(),
251 "returned topologically sorted events differ from pdus"
252 );
253
254 let capped = amount > limit.saturating_add(1);
256
257 Ok(PrevFetch { sorted, pdus, capped })
258}
259
260#[implement(super::Service)]
261async fn await_prev_gap<'a, Events>(&self, initial_set: Events, wait: Duration) -> bool
262where
263 Events: Iterator<Item = &'a EventId> + Send,
264{
265 let deadline = Instant::now()
266 .checked_add(wait)
267 .expect("wait deadline overflows");
268
269 let pending: FuturesUnordered<_> = initial_set
272 .map(|event_id| (event_id, self.services.timeline.watch_event(event_id)))
273 .stream()
274 .filter_map(async |(event_id, watcher)| {
275 (!self.services.timeline.pdu_exists(event_id).await).then_some(watcher)
276 })
277 .collect()
278 .await;
279
280 if pending.is_empty() {
281 return false;
282 }
283
284 timeout_at(deadline, pending.count())
285 .await
286 .is_err()
287}
288
289#[implement(super::Service)]
296#[tracing::instrument(name = "missing", level = "debug", skip_all)]
297async fn prefetch_missing_events(
298 &self,
299 origin: &ServerName,
300 room_id: &RoomId,
301 incoming_event_id: &EventId,
302 room_version: &RoomVersionId,
303 recursion_level: usize,
304) {
305 let boundary: EventWindow = self
306 .services
307 .state
308 .get_forward_extremities(room_id)
309 .map(ToOwned::to_owned)
310 .collect()
311 .await;
312
313 let opts = Opts::new(Op::MissingEvents, room_id.to_owned())
314 .latest_events([incoming_event_id.to_owned()])
315 .earliest_events(boundary)
316 .hint(origin.to_owned())
317 .room_version(room_version.to_owned())
318 .attempt_limit(super::EVENT_FETCH_ATTEMPT_LIMIT)
319 .fanout_for_op();
320
321 let Ok(outcome) = self.services.fetcher.fetch(opts).await else {
322 return;
323 };
324
325 let Ok(events) = serde_json::from_slice::<Vec<Box<RawJsonValue>>>(&outcome.bytes) else {
326 return;
327 };
328
329 events
330 .into_iter()
331 .stream()
332 .for_each_concurrent(automatic_width(), async |pdu| {
333 self.land_missing_event(origin, room_id, &pdu, room_version, recursion_level)
334 .await
335 .ok();
336 })
337 .await;
338}
339
340#[implement(super::Service)]
343#[tracing::instrument(name = "land", level = "trace", skip_all)]
344async fn land_missing_event(
345 &self,
346 origin: &ServerName,
347 room_id: &RoomId,
348 pdu: &RawJsonValue,
349 room_version: &RoomVersionId,
350 recursion_level: usize,
351) -> Result {
352 let value: CanonicalJsonObject = serde_json::from_str(pdu.get())
353 .map_err(|e| err!(BadServerResponse("missing-events pdu is not canonical json: {e}")))?;
354
355 value
356 .get("room_id")
357 .and_then(CanonicalJsonValue::as_str)
358 .is_some_and(|id| id == room_id.as_str())
359 .then_some(())
360 .ok_or_else(|| {
361 err!(Request(InvalidParam("missing-events pdu is for a different room")))
362 })?;
363
364 let event_id = gen_event_id(&value, room_version)?;
365
366 Box::pin(self.handle_outlier_pdu(
368 origin,
369 room_id,
370 &event_id,
371 value,
372 room_version,
373 recursion_level,
374 false,
375 ))
376 .await
377 .map(|_| ())
378}