1use std::{collections::HashSet, iter::once, num::NonZeroUsize};
8
9use futures::{
10 FutureExt, StreamExt, TryFutureExt,
11 future::{join, try_join, try_join4},
12};
13use rand::seq::SliceRandom;
14use ruma::{
15 CanonicalJsonObject, EventId, MilliSecondsSinceUnixEpoch, OwnedEventId, RoomId, ServerName,
16 api::Direction, events::TimelineEventType,
17};
18use serde::Deserialize;
19use serde_json::value::RawValue as RawJsonValue;
20use tuwunel_core::{
21 Err, Result, at, debug, debug_warn, implement, is_false,
22 utils::{
23 BoolExt, IterStream, ReadyExt,
24 future::{BoolExt as FutureBoolExt, TryExtExt},
25 },
26 validated, warn,
27};
28use tuwunel_database::Json;
29use tuwunel_matrix::{
30 PduEvent,
31 event::Event,
32 pdu::{PduCount, PduId, RawPduId},
33};
34
35use super::{ExtractBody, bias_count};
36use crate::{
37 federation::Candidates,
38 fetcher::{Op, Opts},
39 rooms::state_accessor::plain_text_topic,
40};
41
42const BACKFILL_LIMIT: NonZeroUsize = NonZeroUsize::new(100).unwrap();
44
45const BACKFILL_ATTEMPT_LIMIT: NonZeroUsize = NonZeroUsize::new(5).unwrap();
46
47const BACKFILL_BATCH_ATTEMPTS: usize = 3;
48
49#[derive(Deserialize)]
52struct TimestampHit {
53 event_id: OwnedEventId,
54 origin_server_ts: MilliSecondsSinceUnixEpoch,
55}
56
57#[implement(super::Service)]
63#[tracing::instrument(name = "backfill", level = "debug", skip(self))]
64pub async fn backfill_if_required(&self, room_id: &RoomId, from: PduCount) -> Result {
65 let (first_pdu_count, first_pdu) = self.first_item_in_room(room_id).await?;
66
67 if first_pdu_count < from {
68 return Ok(());
69 }
70
71 if *first_pdu.event_type() == TimelineEventType::RoomCreate {
73 return Ok(());
74 }
75
76 let empty_room = self
77 .services
78 .state_cache
79 .room_joined_count(room_id)
80 .map_ok_or(true, |count| count <= 1);
81
82 let not_world_readable = self
83 .services
84 .state_accessor
85 .is_world_readable(room_id)
86 .map(is_false!());
87
88 if empty_room.and(not_world_readable).await {
90 return Ok(());
91 }
92
93 let mut eligible = self.backfill_candidates(room_id).await;
94
95 let no_backfill = || {
96 warn!(%room_id, "No servers could backfill, but backfill was needed");
97 Ok(())
98 };
99
100 if eligible.is_empty() {
104 return no_backfill();
105 }
106
107 for _ in 0..BACKFILL_BATCH_ATTEMPTS {
108 let opts = Opts::new(Op::Backfill, room_id.to_owned())
109 .event_id(first_pdu.event_id().to_owned())
110 .candidates(eligible.iter().cloned())
111 .attempt_limit(BACKFILL_ATTEMPT_LIMIT)
112 .backfill_limit(BACKFILL_LIMIT);
113
114 let Ok(outcome) = self.services.fetcher.fetch(opts).await else {
115 return no_backfill();
116 };
117
118 let pdus: Vec<Box<RawJsonValue>> = serde_json::from_slice(&outcome.bytes)?;
119 let batch_size = pdus.len();
120 let prepended = pdus
121 .into_iter()
122 .stream()
123 .fold(0_usize, async |prepended, pdu| {
124 let inserted = self
125 .backfill_pdu(room_id, &outcome.origin, pdu)
126 .await
127 .inspect_err(|e| debug_warn!(%room_id, %e, "Failed to add backfilled pdu"))
128 .unwrap_or(false);
129
130 prepended.saturating_add(usize::from(inserted))
131 })
132 .await;
133
134 debug!(
135 %room_id,
136 origin = %outcome.origin,
137 batch_size,
138 prepended,
139 "Processed backfill response",
140 );
141
142 if prepended > 0 {
143 return Ok(());
144 }
145
146 eligible.retain(|server| server != &outcome.origin);
147 if eligible.is_empty() {
148 break;
149 }
150 }
151
152 warn!(%room_id, "Backfill was required but prepended no events");
153 Ok(())
154}
155
156#[implement(super::Service)]
157async fn backfill_candidates(&self, room_id: &RoomId) -> Candidates {
158 let canonical_alias = self
159 .services
160 .state_accessor
161 .get_canonical_alias(room_id);
162
163 let power_levels = self
164 .services
165 .state_accessor
166 .get_power_levels(room_id);
167
168 let (canonical_alias, power_levels) = join(canonical_alias, power_levels).await;
169
170 let power_servers = power_levels
171 .iter()
172 .flat_map(|power| {
173 power
174 .rules
175 .privileged_creators
176 .iter()
177 .flat_map(|creators| creators.iter())
178 })
179 .chain(power_levels.iter().flat_map(|power| {
180 power
181 .users
182 .iter()
183 .filter_map(|(user_id, level)| level.gt(&power.users_default).then_some(user_id))
184 }))
185 .filter_map(|user_id| {
186 self.services
187 .globals
188 .user_is_local(user_id)
189 .is_false()
190 .then_some(user_id.server_name())
191 })
192 .collect::<HashSet<_>>();
193
194 let power_servers = {
195 let mut vec: Vec<_> = power_servers
196 .into_iter()
197 .map(ToOwned::to_owned)
198 .collect();
199
200 vec.shuffle(&mut rand::rng());
201 vec.into_iter().stream()
202 };
203
204 let canonical_room_alias_server = once(canonical_alias)
205 .filter_map(Result::ok)
206 .map(|alias| alias.server_name().to_owned())
207 .stream();
208
209 let trusted_servers = self
210 .services
211 .server
212 .config
213 .federation
214 .keys
215 .trusted_servers
216 .iter()
217 .map(ToOwned::to_owned)
218 .stream();
219
220 power_servers
221 .chain(canonical_room_alias_server)
222 .chain(trusted_servers)
223 .ready_filter(|server_name| !self.services.globals.server_is_ours(server_name))
224 .filter_map(async |server_name| {
225 self.services
226 .state_cache
227 .server_in_room(&server_name, room_id)
228 .await
229 .then_some(server_name)
230 })
231 .collect()
232 .await
233}
234
235#[implement(super::Service)]
236pub async fn get_event_id_near_ts_with_fallback(
242 &self,
243 room_id: &RoomId,
244 ts: MilliSecondsSinceUnixEpoch,
245 dir: Direction,
246) -> Result<(MilliSecondsSinceUnixEpoch, OwnedEventId)> {
247 let local = self.get_event_id_near_ts(room_id, ts, dir).await;
248
249 let federate = match &local {
250 | Err(_) => true,
251 | Ok((_, event_id)) =>
252 dir == Direction::Forward && self.is_start_edge_hit(room_id, event_id).await,
253 };
254
255 if !federate {
256 return local;
257 }
258
259 let candidates = self.backfill_candidates(room_id).await;
260
261 if candidates.is_empty() {
262 return local;
263 }
264
265 let opts = Opts::new(Op::TimestampToEvent, room_id.to_owned())
266 .ts(ts)
267 .dir(dir)
268 .candidates(candidates)
269 .checks(false);
270
271 let Ok(outcome) = self.services.fetcher.fetch(opts).await else {
272 return local;
273 };
274
275 let Ok(TimestampHit { event_id, origin_server_ts }) = serde_json::from_slice(&outcome.bytes)
276 else {
277 return local;
278 };
279
280 if let Ok((local_ts, local_id)) = &local
281 && !nearer(dir, origin_server_ts, *local_ts)
282 {
283 return Ok((*local_ts, local_id.clone()));
284 }
285
286 let Ok(pdu) = self
288 .backfill_event(room_id, &event_id, &outcome.origin)
289 .inspect_err(|e| debug_warn!(%room_id, error = ?e, "timestamp fallback backfill failed"))
290 .await
291 else {
292 return local;
293 };
294
295 let actual_ts = pdu.origin_server_ts();
296 let matches_direction = match dir {
297 | Direction::Forward => actual_ts >= ts,
298 | Direction::Backward => actual_ts <= ts,
299 };
300
301 if actual_ts != origin_server_ts || !matches_direction {
302 debug_warn!(
303 %room_id,
304 %event_id,
305 ?dir,
306 ?ts,
307 ?origin_server_ts,
308 ?actual_ts,
309 "timestamp fallback claim was inconsistent with the ingested event"
310 );
311 return local;
312 }
313
314 Ok((actual_ts, event_id))
315}
316
317#[implement(super::Service)]
318async fn is_start_edge_hit(&self, room_id: &RoomId, event_id: &EventId) -> bool {
319 self.first_item_in_room(room_id)
320 .await
321 .is_ok_and(|(_, first)| {
322 *first.event_type() != TimelineEventType::RoomCreate && first.event_id() == event_id
323 })
324}
325
326fn nearer(dir: Direction, a: MilliSecondsSinceUnixEpoch, b: MilliSecondsSinceUnixEpoch) -> bool {
327 match dir {
328 | Direction::Forward => a < b,
329 | Direction::Backward => a > b,
330 }
331}
332
333#[implement(super::Service)]
334async fn backfill_event(
335 &self,
336 room_id: &RoomId,
337 event_id: &EventId,
338 origin: &ServerName,
339) -> Result<PduEvent> {
340 let opts = Opts::new(Op::Backfill, room_id.to_owned())
341 .event_id(event_id.to_owned())
342 .candidates([origin.to_owned()])
343 .backfill_limit(BACKFILL_LIMIT);
344
345 let outcome = self.services.fetcher.fetch(opts).await?;
346
347 let pdus: Vec<Box<RawJsonValue>> = serde_json::from_slice(&outcome.bytes)?;
348
349 let ingestion = pdus
350 .into_iter()
351 .stream()
352 .fold(Ok(()), async |prior, pdu| {
353 let current = self
354 .backfill_pdu(room_id, &outcome.origin, pdu)
355 .map_ok(|_| ())
356 .inspect_err(
357 |e| debug_warn!(%room_id, error = ?e, "Failed to add backfilled pdu"),
358 )
359 .await;
360
361 prior.and(current)
362 })
363 .await;
364
365 match self.get_pdu_count(event_id).await {
366 | Err(error) => ingestion.and(Err(error)),
367 | Ok(_) => {
368 let pdu = self.get_pdu(event_id).await?;
369
370 if pdu.room_id() != room_id {
371 return Err!(Request(NotFound(
372 "Timestamp fallback target belongs to another room."
373 )));
374 }
375
376 Ok(pdu)
377 },
378 }
379}
380
381#[implement(super::Service)]
388#[tracing::instrument(skip(self), level = "debug")]
389pub async fn fetch_remote_event(&self, room_id: &RoomId, event_id: &EventId) -> Result {
390 let opts = Opts::new(Op::Event, room_id.to_owned())
391 .event_id(event_id.to_owned())
392 .checks(false);
393
394 let outcome = self.services.fetcher.fetch(opts).await?;
395
396 let pdu: Box<RawJsonValue> = serde_json::from_slice(&outcome.bytes)?;
397
398 self.backfill_pdu(room_id, &outcome.origin, pdu)
399 .await?;
400
401 Ok(())
402}
403
404#[implement(super::Service)]
411#[tracing::instrument(skip(self, pdu), level = "debug")]
412pub async fn backfill_pdu(
413 &self,
414 room_id: &RoomId,
415 origin: &ServerName,
416 pdu: Box<RawJsonValue>,
417) -> Result<bool> {
418 let parsed = self
419 .services
420 .event_handler
421 .parse_incoming_pdu(&pdu);
422
423 let mutex_lock = self
425 .services
426 .event_handler
427 .mutex_federation
428 .lock(room_id)
429 .map(Ok);
430
431 let ((_, event_id, value), mutex_lock) = try_join(parsed, mutex_lock).await?;
432
433 let existed = self
434 .services
435 .event_handler
436 .handle_incoming_pdu(origin, room_id, &event_id, value, false)
437 .await?
438 .map(at!(1))
439 .is_some_and(is_false!());
440
441 if existed {
443 return Ok(false);
444 }
445
446 let pdu = self.get_pdu(&event_id);
447
448 let value = self.get_pdu_json(&event_id);
449
450 let shortroomid = self.services.short.get_shortroomid(room_id);
451
452 let insert_lock = self.mutex_insert.lock(room_id).map(Ok);
453
454 let (pdu, value, shortroomid, insert_lock) =
455 try_join4(pdu, value, shortroomid, insert_lock).await?;
456
457 let count = self.services.globals.next_count();
460 let count: i64 = (*count).try_into()?;
461 let pdu_id: RawPduId = PduId {
462 shortroomid,
463 count: PduCount::Backfilled(validated!(0 - count)),
464 }
465 .into();
466
467 self.prepend_backfill_pdu(
469 &pdu_id,
470 room_id,
471 &event_id,
472 u64::from(pdu.origin_server_ts),
473 &value,
474 );
475 drop(insert_lock);
476
477 match pdu.kind {
478 | TimelineEventType::RoomMessage => {
479 if let Ok(ExtractBody { body: Some(body) }) = pdu.get_content() {
480 self.services
481 .search
482 .index_pdu(shortroomid, &pdu_id, &body);
483 }
484 },
485 | TimelineEventType::RoomTopic =>
486 if let Some(topic) = pdu.get_content().ok().and_then(plain_text_topic) {
487 self.services
488 .search
489 .index_pdu(shortroomid, &pdu_id, &topic);
490 },
491 | _ => {},
492 }
493
494 drop(mutex_lock);
495
496 debug!("Prepended backfill pdu");
497 Ok(true)
498}
499
500#[implement(super::Service)]
501fn prepend_backfill_pdu(
502 &self,
503 pdu_id: &RawPduId,
504 room_id: &RoomId,
505 event_id: &EventId,
506 origin_server_ts: u64,
507 json: &CanonicalJsonObject,
508) {
509 let mut txn = self.db.db.txn();
510
511 txn.raw_put(&self.db.pduid_pdu, pdu_id, Json(json));
512 txn.insert_raw(&self.db.eventid_pduid, event_id, pdu_id);
513 txn.del_raw(&self.db.eventid_outlierpdu, event_id);
514
515 let count_key = bias_count(pdu_id.count());
516 let key = (room_id, origin_server_ts, count_key);
517 txn.put_raw(&self.db.roomid_tscount_pducount, key, pdu_id.count());
518
519 txn.execute();
520}