Skip to main content

tuwunel_service/sending/sender/select/
mod.rs

1mod device_changes;
2mod presence;
3mod receipts;
4
5use std::{
6	iter::repeat_with,
7	mem::replace,
8	sync::atomic::{AtomicU64, AtomicUsize, Ordering},
9	time::{Duration, SystemTime},
10};
11
12use futures::{StreamExt, future::join3};
13use ruma::{ServerName, api::federation::transactions::edu::Edu};
14use tuwunel_core::{
15	Result, implement, trace,
16	utils::{
17		BoolExt, ReadyExt,
18		time::{now_secs, timepoint_from_now},
19	},
20};
21use tuwunel_matrix::ShortRoomId;
22
23use super::{
24	DEQUEUE_LIMIT, EDU_LIMIT, NewEvents, RetryAction, TransactionStatus, TransactionStatuses,
25	split::{Split, pdu_room},
26};
27use crate::{
28	federation::ShouldAttempt,
29	sending::{
30		Destination, EduBuf, EduVec, SendingEvent, Service,
31		data::{Key, QueueItem},
32	},
33};
34
35/// Output of one EDU selector.
36///
37/// `shipped` rides the current transaction up to the shared budget; `overflow`
38/// past the budget is written as queued rows for later transactions to drain.
39#[derive(Default)]
40struct Selected {
41	shipped: EduVec,
42	overflow: Vec<EduBuf>,
43}
44
45#[derive(Debug, PartialEq, Eq)]
46pub(super) enum Selection {
47	Events(Vec<QueueItem>),
48	Slice(Vec<QueueItem>, Split),
49	Parked {
50		until: u64,
51	},
52	Busy,
53	Refused {
54		earliest_retry: SystemTime,
55	},
56}
57
58enum Current {
59	Ready {
60		replay: bool,
61	},
62	Split(Split),
63	Busy,
64	Refused {
65		earliest_retry: SystemTime,
66	},
67}
68
69impl Selected {
70	/// Take one EDU into the transaction while the shared budget lasts.
71	///
72	/// Once anything has overflowed every later EDU overflows too, so the
73	/// shipped set is always a prefix of the selection order.
74	fn push(&mut self, edu: EduBuf, events_len: &AtomicUsize) {
75		if !self.overflow.is_empty() || events_len.fetch_add(1, Ordering::Relaxed) >= EDU_LIMIT {
76			self.overflow.push(edu);
77		} else {
78			self.shipped.push(edu);
79		}
80	}
81}
82
83#[implement(Service)]
84#[tracing::instrument(
85	name = "select",
86	level = "debug",
87	skip_all,
88	fields(
89		?dest,
90		new_events = %new_events.len(),
91	),
92)]
93pub(super) async fn select_events(
94	&self,
95	dest: &Destination,
96	new_events: NewEvents,
97	statuses: &mut TransactionStatuses,
98) -> Result<Selection> {
99	let retry_action = if matches!(dest, Destination::Appservice(_))
100		&& new_events
101			.iter()
102			.any(|(_, event)| matches!(event, SendingEvent::Flush))
103	{
104		RetryAction::Force
105	} else {
106		RetryAction::None
107	};
108
109	let current = self
110		.select_events_current(dest, statuses, retry_action)
111		.await;
112
113	let retry = match current {
114		| Current::Busy => return Ok(Selection::Busy),
115		| Current::Refused { earliest_retry } =>
116			return Ok(Selection::Refused { earliest_retry }),
117		| Current::Ready { replay } => replay,
118		| Current::Split(split) => match self.slice(dest, split).await {
119			| Some((items, split)) => return Ok(Selection::Slice(items, split)),
120			| None => true,
121		},
122	};
123
124	if retry {
125		let active: Vec<_> = self.db.active_requests_for(dest).collect().await;
126
127		if !active.is_empty() {
128			return Ok(Selection::Events(active));
129		}
130	}
131
132	let _cork = self.db.db.cork();
133
134	if matches!(dest, Destination::Push(..)) && new_events.is_empty() {
135		let events = self.resume_queued(dest, &[]).await;
136
137		return Ok(Selection::Events(events));
138	}
139
140	let Destination::Federation(server) = dest else {
141		return Ok(Selection::Events(self.claim_new(new_events, &[]).await));
142	};
143
144	let selection = self
145		.federation_batch(dest, server, new_events)
146		.await;
147
148	Ok(selection)
149}
150
151#[implement(Service)]
152async fn select_events_current(
153	&self,
154	dest: &Destination,
155	statuses: &mut TransactionStatuses,
156	retry_action: RetryAction,
157) -> Current {
158	if matches!(dest, Destination::Federation(_))
159		&& matches!(
160			statuses.get(dest),
161			Some(TransactionStatus::Running { .. } | TransactionStatus::RunningForceRetry { .. })
162		) {
163		return Current::Busy;
164	}
165
166	if let Destination::Federation(server) = dest
167		&& let Some(earliest_retry) = self.refused_recheck(server)
168	{
169		return Current::Refused { earliest_retry };
170	}
171
172	// peer_status gates federation only; appservice and push fall through.
173	if let Destination::Federation(server) = dest
174		&& let ShouldAttempt::No { earliest_retry } = self
175			.services
176			.federation
177			.should_attempt(server)
178			.await
179	{
180		return Current::Refused { earliest_retry };
181	}
182
183	let Some(status) = statuses.get_mut(dest) else {
184		statuses.insert(dest.clone(), TransactionStatus::Running { tries: 0 });
185		return Current::Ready { replay: false };
186	};
187
188	let current = self.transition(dest, status, retry_action);
189
190	if matches!(current, Current::Ready { replay: true } | Current::Split(_)) {
191		self.clear_stalled(dest);
192	}
193
194	current
195}
196
197/// When to recheck a server that local policy refuses, or `None` if permitted.
198///
199/// No peer status paces a refusal, so this timer takes the place of backoff and
200/// notices the configuration reload that lifts it.
201#[implement(Service)]
202pub(super) fn refused_recheck(&self, server: &ServerName) -> Option<SystemTime> {
203	let config = &self.server.config;
204
205	config
206		.is_remote_permitted(server)
207		.is_false()
208		.then(|| {
209			let recheck = Duration::from_secs(config.sending.timeout);
210
211			timepoint_from_now(recheck).unwrap_or_else(|_| SystemTime::now())
212		})
213}
214
215/// Advance a destination's status for a new selection.
216///
217/// Distinguishes busy destinations from permitted selection and active replay.
218#[implement(Service)]
219fn transition(
220	&self,
221	dest: &Destination,
222	status: &mut TransactionStatus,
223	retry_action: RetryAction,
224) -> Current {
225	let remaining = self.push_backoff_remaining(Some(&*status));
226
227	match status {
228		| TransactionStatus::Retrying { .. } if matches!(dest, Destination::Push(..)) =>
229			Current::Busy,
230		| TransactionStatus::Running { tries }
231		| TransactionStatus::RunningForceRetry { tries } => {
232			if matches!(retry_action, RetryAction::Force) {
233				*status = TransactionStatus::RunningForceRetry { tries: *tries };
234			}
235
236			Current::Busy
237		},
238		| TransactionStatus::Failed { tries, .. } => {
239			let tries = *tries;
240
241			trace!(?dest, tries, ?remaining, "Push destination remains in backoff");
242			if remaining.is_some() {
243				return Current::Busy;
244			}
245
246			*status = TransactionStatus::Retrying { tries };
247			Current::Ready { replay: true }
248		},
249		| TransactionStatus::Pending => {
250			*status = TransactionStatus::Running { tries: 0 };
251			Current::Ready { replay: true }
252		},
253		| TransactionStatus::Retrying { tries } => {
254			*status = TransactionStatus::Running { tries: *tries };
255			Current::Ready { replay: true }
256		},
257		| TransactionStatus::Splitting { tries, .. } => {
258			let tries = *tries;
259
260			launch(status, tries)
261		},
262	}
263}
264
265fn launch(status: &mut TransactionStatus, tries: u32) -> Current {
266	match replace(status, TransactionStatus::Running { tries }) {
267		| TransactionStatus::Splitting { split, .. } => Current::Split(split),
268		| _ => Current::Ready { replay: true },
269	}
270}
271
272#[implement(Service)]
273fn clear_stalled(&self, dest: &Destination) {
274	if let Destination::Federation(server) = dest {
275		self.stalled
276			.lock()
277			.expect("locked")
278			.remove(server);
279	}
280}
281
282/// Compose a federation destination's next transaction around its parked rooms.
283///
284/// Each expired park is retried alone first, and one whose room has nothing
285/// queued ends. Rows of other parked rooms stay queued, and a destination
286/// holding nothing else waits for the earliest park to expire.
287#[implement(Service)]
288pub(super) async fn federation_batch(
289	&self,
290	dest: &Destination,
291	server: &ServerName,
292	new_events: NewEvents,
293) -> Selection {
294	let parks: Vec<_> = self.db.parks(server).collect().await;
295	let now = now_secs();
296
297	for park in parks.iter().filter(|park| park.until <= now) {
298		if let Some((items, split)) = self.slice(dest, Split::probe(park.room)).await {
299			return Selection::Slice(items, split);
300		}
301
302		self.db.unpark(server, park.room);
303	}
304
305	let skip: Vec<_> = parks.iter().map(|park| park.room).collect();
306	let items = self.claim_new(new_events, &skip).await;
307	let items = self.with_edus(dest, server, items, &skip).await;
308	let until = parks
309		.iter()
310		.map(|park| park.until)
311		.filter(|&until| until > now)
312		.min();
313
314	match until {
315		| Some(until) if items.is_empty() => Selection::Parked { until },
316		| _ => Selection::Events(items),
317	}
318}
319
320/// Claim a request's own queue rows, leaving those of skipped rooms queued.
321///
322/// Flush markers carry no row and are dropped; the claimed rows turn active
323/// in one batch.
324#[implement(Service)]
325async fn claim_new(&self, new_events: NewEvents, skip: &[ShortRoomId]) -> Vec<QueueItem> {
326	let items: Vec<_> = self
327		.db
328		.retain_queued(new_events)
329		.ready_filter(|item| {
330			matches!(item.1, SendingEvent::Flush).is_false()
331				&& pdu_room(item).is_none_or(|room| !skip.contains(&room))
332		})
333		.collect()
334		.await;
335
336	self.db.mark_as_active(items.iter());
337	items
338}
339
340/// Top up a federation transaction with the EDUs accrued since its last window.
341///
342/// An empty transaction first claims the head of the queue. Rows of the
343/// skipped rooms neither join the transaction nor hold back fresh EDUs.
344#[implement(Service)]
345async fn with_edus(
346	&self,
347	dest: &Destination,
348	server_name: &ServerName,
349	items: Vec<QueueItem>,
350	skip: &[ShortRoomId],
351) -> Vec<QueueItem> {
352	let items = if items.is_empty() {
353		self.resume_queued(dest, skip).await
354	} else {
355		items
356	};
357
358	// Fresh signing keys must not overtake an older queued signing update.
359	if self
360		.db
361		.queued_except(dest, skip)
362		.take(1)
363		.count()
364		.await
365		.ne(&0)
366	{
367		return items;
368	}
369
370	let budget_used = items
371		.iter()
372		.filter(|(_, event)| matches!(event, SendingEvent::Edu(_)))
373		.count();
374
375	let edus = self.select_edus(server_name, budget_used).await;
376
377	append_edus(items, edus)
378}
379
380fn append_edus(
381	mut items: Vec<QueueItem>,
382	edus: impl Iterator<Item = QueueItem>,
383) -> Vec<QueueItem> {
384	items.extend(edus);
385	items
386}
387
388/// Claim the head of a destination's queue as its next transaction.
389///
390/// Rows of the skipped rooms are passed over; the claimed rows turn active in
391/// one batch.
392#[implement(Service)]
393#[tracing::instrument(level = "trace", skip_all)]
394pub(super) async fn resume_queued(
395	&self,
396	dest: &Destination,
397	skip: &[ShortRoomId],
398) -> Vec<QueueItem> {
399	let queued: Vec<_> = self
400		.db
401		.queued_except(dest, skip)
402		.take(DEQUEUE_LIMIT)
403		.collect()
404		.await;
405
406	self.db.mark_as_active(queued.iter());
407	queued
408}
409
410#[implement(Service)]
411#[tracing::instrument(name = "edus", level = "debug", skip_all)]
412pub(super) async fn select_edus(
413	&self,
414	server_name: &ServerName,
415	budget_used: usize,
416) -> impl Iterator<Item = QueueItem> {
417	let since = self.db.get_latest_educount(server_name).await;
418	let since_upper = self.services.globals.current_count();
419
420	// Nothing new since the last window: skip the scan and the watermark.
421	if since == since_upper {
422		return keyed(Vec::new().into_iter(), EduVec::new());
423	}
424
425	let batch = (since, since_upper);
426
427	debug_assert!(batch.0 <= batch.1, "since range must not be negative");
428
429	let events_len = AtomicUsize::new(budget_used);
430	let max_edu_count = AtomicU64::new(since);
431	let device_changes =
432		self.select_edus_device_changes(server_name, batch, &max_edu_count, &events_len);
433
434	let receipts = self
435		.server
436		.config
437		.read_receipts
438		.allow_outgoing
439		.then_async(|| {
440			self.select_edus_receipts(server_name, batch, &max_edu_count, &events_len)
441		});
442
443	let presence = self
444		.server
445		.config
446		.presence
447		.allow_outgoing
448		.then_async(|| {
449			self.select_edus_presence(server_name, batch, &max_edu_count, &events_len)
450		});
451
452	let (device_changes, receipts, presence) = join3(device_changes, receipts, presence).await;
453	let receipts = receipts.unwrap_or_default();
454
455	// Presence rides last and is excluded from the durable prefix because
456	// its content is compose-time-relative and regenerates fresh.
457	let durable_len = device_changes
458		.shipped
459		.len()
460		.saturating_add(receipts.shipped.len());
461
462	let events: EduVec = device_changes
463		.shipped
464		.into_iter()
465		.chain(receipts.shipped)
466		.chain(presence.flatten())
467		.collect();
468
469	debug_assert!(budget_used.saturating_add(events.len()) <= EDU_LIMIT, "exceeded edus limit");
470
471	// EDUs past the budget become queued rows drained by later transactions.
472	let overflow: Vec<SendingEvent> = device_changes
473		.overflow
474		.into_iter()
475		.chain(receipts.overflow)
476		.map(SendingEvent::Edu)
477		.collect();
478
479	if !overflow.is_empty() {
480		let dest = Destination::Federation(server_name.to_owned());
481
482		self.db
483			.queue_requests(overflow.iter().map(|event| (event, &dest)));
484	}
485
486	// Persist the durable prefix so a failed or restarted transaction
487	// replays it; the ACK deletes these active rows.
488	let keys = self
489		.db
490		.persist_active_edus(server_name, &events[..durable_len]);
491
492	let last_count = max_edu_count.load(Ordering::Acquire);
493	if last_count > since {
494		self.db
495			.set_latest_educount(server_name, last_count);
496	}
497
498	keyed(keys, events)
499}
500
501/// Pair composed EDUs with their durable keys.
502///
503/// Presence rides past the durable prefix with empty keys, so a delivery has no
504/// row of it to acknowledge.
505fn keyed(keys: impl Iterator<Item = Key>, edus: EduVec) -> impl Iterator<Item = QueueItem> {
506	keys.chain(repeat_with(Key::new))
507		.zip(edus)
508		.map(|(key, edu)| (key, SendingEvent::Edu(edu)))
509}
510
511/// Serialize one EDU into its inline queue buffer.
512pub(super) fn edu_buf(edu: &Edu) -> EduBuf {
513	let mut buf = EduBuf::new(); // serde_json::to_writer out-param
514
515	serde_json::to_writer(&mut buf, edu).expect("EDU serializes to JSON");
516	buf
517}