Skip to main content

tuwunel_service/rooms/event_handler/
fetch_prev.rs

1use 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
32/// An incoming event's missing previous events, walked backwards.
33///
34/// The incoming event's handler upgrades the walked events and records
35/// `capped` in the prev-walk counters.
36pub(super) struct PrevFetch {
37	/// Walked event ids in topological order, including placeholders for events
38	/// that failed to fetch or fell past the cap.
39	pub(super) sorted: Vec<OwnedEventId>,
40
41	/// Fetched PDUs of the walked events.
42	pub(super) pdus: Pdus,
43
44	/// Whether the `max_fetch_prev_events` cap cut the walk.
45	pub(super) capped: bool,
46}
47
48/// Walk an incoming event's missing previous events backwards.
49///
50/// Each fetched event queues its own missing previous events in turn, until
51/// they reach the timeline, predate the room, or exceed the
52/// `max_fetch_prev_events` cap.
53#[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			// A prev event already in the timeline is not walked below, so its room is
114			// checked here instead.
115			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) // heterogeneous FuturesOrdered
134		.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			// Fetch and handle failed
155			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			// keep counting so the capped check below sees the cut
163			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			// Get json failed, so this was not fetched over federation
179			graph.insert(prev_event_id.clone(), Default::default());
180			continue;
181		};
182
183		// handle_prev_pdu upgrades events this old too, so their prev events must be
184		// walked and room-checked as well.
185		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()); // heterogeneous FuturesOrdered
213			}
214
215			graph.insert(
216				prev_event_id.clone(),
217				pdu.prev_events().map(ToOwned::to_owned).collect(),
218			);
219		} else {
220			// Time based check failed
221			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		// This return value is the key used for sorting events,
233		// events are then sorted by power level, time,
234		// and lexically by event_id.
235		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	// at most limit + 1 events are admitted, so more means one was cut
255	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	// Each watcher registers before its existence recheck, so a prev that
270	// arrives during the recheck still wakes us.
271	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/// Fill the prev gap below `incoming_event_id` with one `/get_missing_events`
290/// batch, landing each returned event as a local outlier so the per-event walk
291/// resolves it without a federation fetch. `latest_events` is the held event
292/// the server walks back from, bounded by our forward extremities so it returns
293/// only the gap; best effort, so a failed batch or rejected event just leaves
294/// that id for the walk.
295#[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/// Authenticate and persist one event from the missing-events batch as an
341/// outlier, deriving its id from content rather than trusting a requested id.
342#[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	// cold arm: missing events
367	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}