1use std::{
9 collections::{BTreeSet, HashSet},
10 iter::once,
11 sync::{
12 Arc,
13 atomic::{AtomicBool, Ordering},
14 },
15 time::Instant,
16};
17
18use async_trait::async_trait;
19use futures::{
20 FutureExt, Stream, StreamExt, TryFutureExt, pin_mut,
21 stream::{FuturesUnordered, unfold},
22};
23use ruma::{
24 EventId, OwnedEventId, OwnedRoomId, RoomId, RoomVersionId,
25 room_version_rules::RoomVersionRules,
26};
27use serde::Deserialize;
28use tuwunel_core::{
29 Err, Result, at, debug, debug_error, err, implement,
30 itertools::Itertools,
31 smallvec::SmallVec,
32 trace,
33 utils::{
34 BoolExt, IterStream,
35 stream::{BroadbandExt, ReadyExt, TryExpect, automatic_width},
36 },
37 validated, warn,
38};
39use tuwunel_database::Map;
40use tuwunel_matrix::{pdu::AuthEvents, room_version};
41
42use crate::rooms::short::ShortEventId;
43
44pub struct Service {
53 services: Arc<crate::services::OnceServices>,
54 db: Data,
55}
56
57struct Data {
58 authchainkey_authchain: Arc<Map>,
59}
60
61type Bucket<'a> = BTreeSet<(ShortEventId, &'a EventId)>;
62type CacheKey = SmallVec<[ShortEventId; 1]>;
63
64#[async_trait]
65impl crate::Service for Service {
66 fn build(args: &crate::Args<'_>) -> Result<Arc<Self>> {
67 Ok(Arc::new(Self {
68 services: args.services.clone(),
69 db: Data {
70 authchainkey_authchain: args.db["authchainkey_authchain"].clone(),
71 },
72 }))
73 }
74
75 async fn clear_cache(&self) { self.db.authchainkey_authchain.clear().await; }
76
77 fn name(&self) -> &str { crate::service::make_name(std::module_path!()) }
78}
79
80#[implement(Service)]
86pub fn event_ids_iter<'a, I>(
87 &'a self,
88 room_id: &'a RoomId,
89 room_version: &'a RoomVersionId,
90 starting_events: I,
91) -> impl Stream<Item = Result<OwnedEventId>> + Send + 'a
92where
93 I: Iterator<Item = &'a EventId> + Clone + ExactSizeIterator + Send + 'a,
94{
95 self.get_auth_chain(room_id, room_version, starting_events)
96 .map_ok(|chain| {
97 self.services
98 .short
99 .multi_get_eventid_from_short(chain.into_iter().stream())
100 .ready_filter(Result::is_ok)
101 })
102 .try_flatten_stream()
103}
104
105#[implement(Service)]
112pub fn event_ids_iter_strict<'a, I>(
113 &'a self,
114 room_id: &'a RoomId,
115 room_version: &'a RoomVersionId,
116 starting_events: I,
117 complete: &'a AtomicBool,
118) -> impl Stream<Item = Result<OwnedEventId>> + Send + 'a
119where
120 I: Iterator<Item = &'a EventId> + Clone + ExactSizeIterator + Send + 'a,
121{
122 self.get_auth_chain_strict(room_id, room_version, starting_events, complete)
123 .map_ok(move |chain| {
124 self.services
125 .short
126 .multi_get_eventid_from_short(chain.into_iter().stream())
127 .inspect(move |result| {
128 if result.is_err() {
129 complete.store(false, Ordering::Relaxed);
130 }
131 })
132 .ready_filter(Result::is_ok)
133 })
134 .try_flatten_stream()
135}
136
137#[implement(Service)]
138#[tracing::instrument(
139 name = "auth_chain",
140 level = "debug",
141 skip_all,
142 fields(
143 %room_id,
144 starting_events = %starting_events.clone().count(),
145 )
146)]
147pub async fn get_auth_chain<'a, I>(
155 &'a self,
156 room_id: &RoomId,
157 room_version: &RoomVersionId,
158 starting_events: I,
159) -> Result<Vec<ShortEventId>>
160where
161 I: Iterator<Item = &'a EventId> + Clone + ExactSizeIterator + Send + 'a,
162{
163 let complete = AtomicBool::new(true);
164
165 self.get_auth_chain_inner(room_id, room_version, starting_events, &complete)
166 .await
167}
168
169#[implement(Service)]
170#[tracing::instrument(
171 name = "auth_chain",
172 level = "debug",
173 skip_all,
174 fields(
175 %room_id,
176 starting_events = %starting_events.clone().count(),
177 )
178)]
179async fn get_auth_chain_strict<'a, I>(
180 &'a self,
181 room_id: &RoomId,
182 room_version: &RoomVersionId,
183 starting_events: I,
184 complete: &AtomicBool,
185) -> Result<Vec<ShortEventId>>
186where
187 I: Iterator<Item = &'a EventId> + Clone + ExactSizeIterator + Send + 'a,
188{
189 self.get_auth_chain_inner(room_id, room_version, starting_events, complete)
190 .inspect_err(|_| complete.store(false, Ordering::Relaxed))
191 .await
192}
193
194#[implement(Service)]
195async fn get_auth_chain_inner<'a, I>(
196 &'a self,
197 room_id: &RoomId,
198 room_version: &RoomVersionId,
199 starting_events: I,
200 complete: &AtomicBool,
201) -> Result<Vec<ShortEventId>>
202where
203 I: Iterator<Item = &'a EventId> + Clone + ExactSizeIterator + Send + 'a,
204{
205 const NUM_BUCKETS: usize = 50; const BUCKET: Bucket<'_> = BTreeSet::new();
207
208 let started = Instant::now();
209 let room_rules = room_version::rules(room_version)?;
210 let starting_events_count = starting_events.clone().count();
211 let starting_ids = self
212 .services
213 .short
214 .multi_get_or_create_shorteventid(starting_events.clone())
215 .zip(starting_events.stream());
216
217 pin_mut!(starting_ids);
218 let mut buckets = [BUCKET; NUM_BUCKETS];
219 while let Some((short, starting_event)) = starting_ids.next().await {
220 let bucket: usize = short.try_into()?;
221 let bucket: usize = validated!(bucket % NUM_BUCKETS);
222 buckets[bucket].insert((short, starting_event));
223 }
224
225 debug!(
226 starting_events = starting_events_count,
227 elapsed = ?started.elapsed(),
228 "start",
229 );
230
231 let full_auth_chain: Vec<ShortEventId> = buckets
232 .iter()
233 .stream()
234 .flat_map_unordered(automatic_width(), |starting_events| {
235 self.get_chunk_auth_chain(
236 room_id,
237 &started,
238 starting_events.iter().copied(),
239 &room_rules,
240 complete,
241 )
242 .boxed() })
244 .collect::<Vec<_>>()
245 .map(IntoIterator::into_iter)
246 .map(Itertools::sorted_unstable)
247 .map(Itertools::dedup)
248 .map(Iterator::collect)
249 .boxed() .await;
251
252 debug!(
253 chain_length = ?full_auth_chain.len(),
254 elapsed = ?started.elapsed(),
255 "done",
256 );
257
258 Ok(full_auth_chain)
259}
260
261#[implement(Service)]
262#[tracing::instrument(
263 name = "outer",
264 level = "trace",
265 skip_all,
266 fields(
267 starting_events = %starting_events.clone().count(),
268 )
269)]
270fn get_chunk_auth_chain<'a, I>(
271 &'a self,
272 room_id: &'a RoomId,
273 started: &'a Instant,
274 starting_events: I,
275 room_rules: &'a RoomVersionRules,
276 complete: &'a AtomicBool,
277) -> impl Stream<Item = ShortEventId> + Send + 'a
278where
279 I: Iterator<Item = (ShortEventId, &'a EventId)> + Clone + Send + Sync + 'a,
280{
281 self.get_cached_auth_chain(starting_events.clone().map(at!(0)))
282 .map_ok(IntoIterator::into_iter)
283 .map_ok(IterStream::try_stream)
284 .or_else(async move |_| {
285 let chain = self
286 .build_chunk_auth_chain(room_id, started, starting_events, room_rules, complete)
287 .await;
288
289 Ok(chain.into_iter().try_stream())
290 })
291 .try_flatten_stream()
292 .map_expect("either cache hit or cache miss yields a chain")
293}
294
295#[implement(Service)]
296async fn build_chunk_auth_chain<'a, I>(
297 &'a self,
298 room_id: &'a RoomId,
299 started: &'a Instant,
300 starting_events: I,
301 room_rules: &'a RoomVersionRules,
302 complete: &'a AtomicBool,
303) -> Vec<ShortEventId>
304where
305 I: Iterator<Item = (ShortEventId, &'a EventId)> + Clone + Send + Sync + 'a,
306{
307 let chunk_complete = AtomicBool::new(true);
308
309 let build_chain = async |(shortid, event_id): (ShortEventId, &'a EventId)| {
310 if let Ok(cached) = self.get_cached_auth_chain(once(shortid)).await {
311 return cached;
312 }
313
314 let event_complete = AtomicBool::new(true);
315 let auth_chain: Vec<_> = self
316 .get_event_auth_chain(room_id, event_id, room_rules, &event_complete)
317 .collect()
318 .await;
319
320 match event_complete.load(Ordering::Relaxed) {
321 | true => self.put_cached_auth_chain(once(shortid), auth_chain.as_slice()),
322 | false => {
323 chunk_complete.store(false, Ordering::Relaxed);
324 complete.store(false, Ordering::Relaxed);
325 },
326 }
327
328 debug!(
329 ?event_id,
330 elapsed = ?started.elapsed(),
331 "Cache missed event"
332 );
333
334 auth_chain
335 };
336
337 let chunk_chain: Vec<_> = starting_events
338 .clone()
339 .stream()
340 .broad_then(build_chain)
341 .collect::<Vec<_>>()
342 .map(IntoIterator::into_iter)
343 .map(Iterator::flatten)
344 .map(Itertools::sorted_unstable)
345 .map(Itertools::dedup)
346 .map(Iterator::collect)
347 .await;
348
349 match chunk_complete.load(Ordering::Relaxed) {
350 | false => debug!(
351 elapsed = ?started.elapsed(),
352 "Incomplete chunk not cached",
353 ),
354 | true => {
355 self.put_cached_auth_chain(starting_events.map(at!(0)), chunk_chain.as_slice());
356
357 debug!(
358 chunk_chain_length = ?chunk_chain.len(),
359 elapsed = ?started.elapsed(),
360 "Cache missed chunk",
361 );
362 },
363 }
364
365 chunk_chain
366}
367
368#[implement(Service)]
369#[tracing::instrument(name = "inner", level = "trace", skip_all)]
370fn get_event_auth_chain<'a>(
371 &'a self,
372 room_id: &'a RoomId,
373 event_id: &'a EventId,
374 room_rules: &'a RoomVersionRules,
375 complete: &'a AtomicBool,
376) -> impl Stream<Item = ShortEventId> + Send + 'a {
377 self.get_event_auth_chain_ids(room_id, event_id, room_rules, complete)
378 .broad_then(async move |auth_event| {
379 self.services
380 .short
381 .get_or_create_shorteventid(&auth_event)
382 .await
383 })
384}
385
386#[implement(Service)]
387#[tracing::instrument(
388 name = "inner_ids",
389 level = "trace",
390 skip_all,
391 fields(%event_id)
392)]
393fn get_event_auth_chain_ids<'a>(
394 &'a self,
395 room_id: &'a RoomId,
396 event_id: &'a EventId,
397 room_rules: &'a RoomVersionRules,
398 complete: &'a AtomicBool,
399) -> impl Stream<Item = OwnedEventId> + Send + 'a {
400 struct State<Fut> {
401 todo: FuturesUnordered<Fut>,
402 seen: HashSet<OwnedEventId>,
403 implied: Option<OwnedEventId>,
404 }
405
406 let create_event_id = room_rules
408 .authorization
409 .room_create_event_id_as_room_id
410 .and_then(|| room_id.as_event_id().ok())
411 .filter(|create_event_id| create_event_id.ne(&event_id));
412
413 let starting_events = self.get_event_auth_event_ids(room_id, event_id.to_owned());
414
415 let state = State {
416 todo: once(starting_events).collect(),
417 seen: create_event_id.iter().cloned().collect(),
418 implied: create_event_id,
419 };
420
421 let eval = |auth_events: AuthEvents, mut state: State<_>| {
422 let implied = state.implied.take();
423 let push = |auth_event: &OwnedEventId| {
424 trace!(todo = state.todo.len(), ?auth_event, "push");
425 state
426 .todo
427 .push(self.get_event_auth_event_ids(room_id, auth_event.clone()));
428 };
429
430 let seen = |auth_event: OwnedEventId| {
431 state
432 .seen
433 .insert(auth_event.clone())
434 .then_some(auth_event)
435 };
436
437 let unseen = auth_events
438 .into_iter()
439 .filter_map(seen)
440 .inspect(push);
441
442 let out = implied
443 .into_iter()
444 .chain(unseen)
445 .collect::<AuthEvents>()
446 .into_iter()
447 .stream();
448
449 (out, state)
450 };
451
452 #[expect(closure_returning_async_block)]
455 unfold(state, move |mut state| async move {
456 match state.todo.next().await {
457 | None => None,
458 | Some(Ok(auth_events)) => Some(eval(auth_events, state)),
459 | Some(Err(e)) => {
460 complete.store(false, Ordering::Relaxed);
461
462 e.is_not_found()
465 .then(move || (AuthEvents::new().into_iter().stream(), state))
466 },
467 }
468 })
469 .flatten()
470}
471
472#[implement(Service)]
473#[tracing::instrument(
474 name = "cache_put",
475 level = "debug",
476 skip_all,
477 fields(
478 key_len = key.clone().count(),
479 chain_len = auth_chain.len(),
480 )
481)]
482fn put_cached_auth_chain<I>(&self, key: I, auth_chain: &[ShortEventId])
483where
484 I: Iterator<Item = ShortEventId> + Clone + Send,
485{
486 let key = key.collect::<CacheKey>();
487
488 debug_assert!(!key.is_empty(), "auth_chain key must not be empty");
489
490 self.db
491 .authchainkey_authchain
492 .put(key.as_slice(), auth_chain);
493}
494
495#[implement(Service)]
496#[tracing::instrument(
497 name = "cache_get",
498 level = "trace",
499 err(level = "trace"),
500 skip_all,
501 fields(
502 key_len = %key.clone().count()
503 ),
504)]
505async fn get_cached_auth_chain<I>(&self, key: I) -> Result<Vec<ShortEventId>>
506where
507 I: Iterator<Item = ShortEventId> + Clone + Send,
508{
509 let key = key.collect::<CacheKey>();
510
511 if key.is_empty() {
512 return Ok(Vec::new());
513 }
514
515 let chain = self
516 .db
517 .authchainkey_authchain
518 .qry(key.as_slice())
519 .map_err(|_| err!(Request(NotFound("auth_chain not cached"))))
520 .await?;
521
522 if !chain.len().is_multiple_of(size_of::<u64>()) {
523 return Err!(Request(NotFound("malformed auth_chain cache")));
524 }
525
526 let chain = chain
527 .as_chunks::<{ size_of::<u64>() }>()
528 .0
529 .iter()
530 .copied()
531 .map(u64::from_be_bytes)
532 .collect();
533
534 Ok(chain)
535}
536
537#[implement(Service)]
538#[tracing::instrument(
539 name = "auth_events",
540 level = "trace",
541 ret(level = "trace"),
542 err(level = "trace"),
543 skip_all,
544 fields(%event_id)
545)]
546async fn get_event_auth_event_ids<'a>(
547 &'a self,
548 room_id: &'a RoomId,
549 event_id: OwnedEventId,
550) -> Result<AuthEvents> {
551 #[derive(Deserialize)]
552 struct Pdu {
553 auth_events: AuthEvents,
554 room_id: OwnedRoomId,
555 }
556
557 let pdu: Pdu = self
558 .services
559 .timeline
560 .get(&event_id)
561 .inspect_err(|e| {
562 debug_error!(?event_id, ?room_id, "auth chain event: {e}");
563 })
564 .await?;
565
566 if pdu.room_id != room_id {
567 return Err!(Request(Forbidden(error!(
568 ?event_id,
569 ?room_id,
570 wrong_room_id = ?pdu.room_id,
571 "auth event for incorrect room",
572 ))));
573 }
574
575 Ok(pdu.auth_events)
576}