Skip to main content

tuwunel_service/rooms/auth_chain/
mod.rs

1//! Resolves and caches transitive authorization-event ancestry.
2//!
3//! Traversals operate on short event IDs, enforce room membership on cache
4//! misses, and store complete chains for repeated starting sets. Public stream
5//! adapters translate the results back to event IDs with tolerant or explicit
6//! completeness reporting.
7
8use 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
44/// Computes transitive authorization chains and maintains their persistent cache.
45///
46/// Starting events are distributed across a fixed number of buckets before
47/// traversal. Only complete cache-miss walks are written. Existing cache hits
48/// are trusted without rechecking completeness, so historical or
49/// downgrade-written rows can still supply partial chains until they expire or
50/// are cleared. Combined bucket results are sorted and deduplicated by short
51/// event ID rather than graph order.
52pub 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/// Streams the transitive auth ancestors of a set of starting events.
81///
82/// The starting events themselves are not included unless encountered as
83/// ancestors. Traversal and reverse-mapping failures are filtered from this
84/// tolerant interface, so the stream can yield a partial chain without error.
85#[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/// Streams an auth chain and reports whether its observed inputs were complete.
106///
107/// The caller initializes `complete` to `true` and checks it after consuming
108/// the stream. Cached chains leave it unchanged. Any polled reverse-mapping or
109/// ancestor-walk failure sets it to `false`, so the stream must be fully
110/// consumed before the flag is inspected.
111#[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)]
147/// Returns sorted short IDs for the transitive auth ancestors of starting events.
148///
149/// Starting events are excluded unless reached again as ancestors, and missing
150/// ancestry can produce a partial successful result. Complete per-bucket
151/// results are cached under roomless keys derived from each bucket's exact set
152/// of starting short IDs; uncached traversal still rejects events from another
153/// room.
154pub 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; //TODO: change possible w/o disrupting db?
206	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() // Unpin for flat_map_unordered
243		})
244		.collect::<Vec<_>>()
245		.map(IntoIterator::into_iter)
246		.map(Itertools::sorted_unstable)
247		.map(Itertools::dedup)
248		.map(Iterator::collect)
249		.boxed() // erase region
250		.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	// MSC4291 rooms imply the create event rather than naming it in auth_events.
407	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	// unfold requires FnMut returning a nameable future; an async closure
453	// capturing eval does not satisfy it.
454	#[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				// A missing ancestor is a normal backfill gap and is skipped;
463				// any other error is corrupt data and ends the walk.
464				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}