1use std::{
2 collections::{BTreeMap, BTreeSet, VecDeque},
3 fmt,
4 num::NonZeroU16,
5 sync::{
6 Arc, Mutex, MutexGuard, PoisonError,
7 atomic::{AtomicBool, AtomicU32, AtomicUsize, Ordering},
8 },
9};
10
11use thiserror::Error;
12use tokio::{
13 sync::{Notify, OwnedSemaphorePermit, Semaphore, TryAcquireError},
14 time::{Instant, timeout_at},
15};
16
17pub const MAXIMUM_QUEUE_CAPACITY: usize = 1_048_576;
19pub const MAXIMUM_TOTAL_QUEUE_CAPACITY: usize = 1_048_576;
21pub const MAXIMUM_LINK_QUEUES: usize = 256;
23
24#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
26pub struct QueueId(u16);
27
28impl QueueId {
29 pub const DEFAULT: Self = Self(0);
31
32 pub const fn new(value: u16) -> Self {
34 Self(value)
35 }
36
37 pub const fn get(self) -> u16 {
39 self.0
40 }
41}
42
43impl From<u16> for QueueId {
44 fn from(value: u16) -> Self {
45 Self::new(value)
46 }
47}
48
49impl fmt::Display for QueueId {
50 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
51 write!(formatter, "{}", self.0)
52 }
53}
54
55#[derive(Debug, Clone, Copy, PartialEq, Eq)]
57pub enum QueuePriority {
58 Weighted(NonZeroU16),
60 Strict(u16),
65}
66
67impl QueuePriority {
68 pub const fn weighted(weight: u16) -> Result<Self, QueueConfigError> {
70 match NonZeroU16::new(weight) {
71 Some(weight) => Ok(Self::Weighted(weight)),
72 None => Err(QueueConfigError::ZeroWeight),
73 }
74 }
75
76 pub const fn strict(rank: u16) -> Self {
78 Self::Strict(rank)
79 }
80
81 pub const fn weight(self) -> Option<u16> {
83 match self {
84 Self::Weighted(weight) => Some(weight.get()),
85 Self::Strict(_) => None,
86 }
87 }
88
89 pub const fn strict_rank(self) -> Option<u16> {
91 match self {
92 Self::Weighted(_) => None,
93 Self::Strict(rank) => Some(rank),
94 }
95 }
96
97 const fn encode(self) -> u32 {
98 match self {
99 Self::Weighted(weight) => weight.get() as u32,
100 Self::Strict(rank) => (1_u32 << 31) | rank as u32,
101 }
102 }
103
104 const fn decode(value: u32) -> Self {
105 let bytes = value.to_le_bytes();
106 let lower = u16::from_le_bytes([bytes[0], bytes[1]]);
107 if value & (1_u32 << 31) != 0 {
108 Self::Strict(lower)
109 } else {
110 let weight = match NonZeroU16::new(lower) {
111 Some(weight) => weight,
112 None => NonZeroU16::MIN,
113 };
114 Self::Weighted(weight)
115 }
116 }
117}
118
119impl Default for QueuePriority {
120 fn default() -> Self {
121 Self::Weighted(NonZeroU16::MIN)
122 }
123}
124
125#[derive(Debug, Clone, Copy, PartialEq, Eq)]
127pub struct QueueConfig {
128 id: QueueId,
129 capacity: usize,
130 priority: QueuePriority,
131}
132
133impl QueueConfig {
134 pub fn weighted(
136 id: impl Into<QueueId>,
137 capacity: usize,
138 weight: u16,
139 ) -> Result<Self, QueueConfigError> {
140 Self::new(id.into(), capacity, QueuePriority::weighted(weight)?)
141 }
142
143 pub fn strict(
145 id: impl Into<QueueId>,
146 capacity: usize,
147 rank: u16,
148 ) -> Result<Self, QueueConfigError> {
149 Self::new(id.into(), capacity, QueuePriority::strict(rank))
150 }
151
152 pub fn new(
154 id: QueueId,
155 capacity: usize,
156 priority: QueuePriority,
157 ) -> Result<Self, QueueConfigError> {
158 if capacity == 0 {
159 return Err(QueueConfigError::ZeroCapacity(id));
160 }
161 if capacity > MAXIMUM_QUEUE_CAPACITY {
162 return Err(QueueConfigError::CapacityLimit {
163 queue: id,
164 capacity,
165 });
166 }
167 Ok(Self {
168 id,
169 capacity,
170 priority,
171 })
172 }
173
174 pub const fn id(self) -> QueueId {
176 self.id
177 }
178
179 pub const fn capacity(self) -> usize {
181 self.capacity
182 }
183
184 pub const fn priority(self) -> QueuePriority {
186 self.priority
187 }
188}
189
190#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
192pub enum QueueConfigError {
193 #[error("queue {0} capacity must be greater than zero")]
195 ZeroCapacity(QueueId),
196 #[error("queue {queue} capacity {capacity} exceeds the supported limit")]
198 CapacityLimit {
199 queue: QueueId,
201 capacity: usize,
203 },
204 #[error("weighted queue priority must be greater than zero")]
206 ZeroWeight,
207 #[error("queue id {0} is configured more than once")]
209 DuplicateId(QueueId),
210 #[error("a link requires at least one queue")]
212 Empty,
213 #[error("a link supports at most {MAXIMUM_LINK_QUEUES} queues")]
215 TooManyQueues,
216 #[error("total queue capacity {0} exceeds the supported limit")]
218 TotalCapacity(usize),
219 #[error("default queue {0} is not configured")]
221 MissingDefault(QueueId),
222}
223
224#[derive(Debug, Clone, Copy, PartialEq, Eq)]
226#[non_exhaustive]
227pub struct QueueSnapshot {
228 pub id: QueueId,
230 pub capacity: usize,
232 pub queued: usize,
234 pub priority: QueuePriority,
236}
237
238#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
240pub enum QueueError {
241 #[error("queue {0} is not configured on this link")]
243 Unknown(QueueId),
244 #[error("weighted queue priority must be greater than zero")]
246 ZeroWeight,
247}
248
249pub(crate) fn validate_layout(
250 definitions: &[QueueConfig],
251 default: QueueId,
252) -> Result<(), QueueConfigError> {
253 if definitions.is_empty() {
254 return Err(QueueConfigError::Empty);
255 }
256 if definitions.len() > MAXIMUM_LINK_QUEUES {
257 return Err(QueueConfigError::TooManyQueues);
258 }
259 let mut ids = BTreeSet::new();
260 let mut total = 0_usize;
261 for definition in definitions {
262 if !ids.insert(definition.id()) {
263 return Err(QueueConfigError::DuplicateId(definition.id()));
264 }
265 total = total
266 .checked_add(definition.capacity())
267 .ok_or(QueueConfigError::TotalCapacity(usize::MAX))?;
268 if total > MAXIMUM_TOTAL_QUEUE_CAPACITY {
269 return Err(QueueConfigError::TotalCapacity(total));
270 }
271 }
272 if !ids.contains(&default) {
273 return Err(QueueConfigError::MissingDefault(default));
274 }
275 Ok(())
276}
277
278#[derive(Debug, Clone, Copy, PartialEq, Eq)]
279pub(crate) enum QueuePushError {
280 Full,
281 Closed,
282 Deadline,
283 Unknown(QueueId),
284}
285
286pub(crate) struct QueueEntry<T> {
287 item: T,
288 _permit: OwnedSemaphorePermit,
289}
290
291impl<T> QueueEntry<T> {
292 pub(crate) const fn item(&self) -> &T {
293 &self.item
294 }
295
296 fn into_item(self) -> T {
297 self.item
298 }
299}
300
301struct QueueSlot<T> {
302 id: QueueId,
303 capacity: usize,
304 priority: AtomicU32,
305 permits: Arc<Semaphore>,
306 queued: AtomicUsize,
307 entries: Mutex<VecDeque<QueueEntry<T>>>,
308}
309
310impl<T> QueueSlot<T> {
311 fn new(config: QueueConfig) -> Self {
312 Self {
313 id: config.id(),
314 capacity: config.capacity(),
315 priority: AtomicU32::new(config.priority().encode()),
316 permits: Arc::new(Semaphore::new(config.capacity())),
317 queued: AtomicUsize::new(0),
318 entries: Mutex::new(VecDeque::new()),
319 }
320 }
321
322 fn entries(&self) -> MutexGuard<'_, VecDeque<QueueEntry<T>>> {
323 self.entries.lock().unwrap_or_else(PoisonError::into_inner)
324 }
325
326 fn priority(&self) -> QueuePriority {
327 QueuePriority::decode(self.priority.load(Ordering::Acquire))
328 }
329
330 fn pop_front(&self) -> Option<QueueEntry<T>> {
331 self.entries().pop_front()
332 }
333
334 fn push_front(&self, entry: QueueEntry<T>) {
335 self.entries().push_front(entry);
336 }
337
338 fn close(&self) {
339 self.permits.close();
340 }
341
342 fn snapshot(&self) -> QueueSnapshot {
343 QueueSnapshot {
344 id: self.id,
345 capacity: self.capacity,
346 queued: self.queued.load(Ordering::Acquire),
347 priority: self.priority(),
348 }
349 }
350}
351
352pub(crate) struct QueueCursor {
353 weighted_index: usize,
354 weighted_used: u16,
355 strict_index: usize,
356}
357
358impl QueueCursor {
359 pub(crate) const fn new() -> Self {
360 Self {
361 weighted_index: 0,
362 weighted_used: 0,
363 strict_index: 0,
364 }
365 }
366}
367
368pub(crate) struct QueueSet<T> {
369 slots: Box<[QueueSlot<T>]>,
370 indices: BTreeMap<QueueId, usize>,
371 notify: Notify,
372 input_closed: AtomicBool,
373 runner_closed: AtomicBool,
374}
375
376impl<T> QueueSet<T> {
377 pub(crate) fn new(definitions: &[QueueConfig]) -> Self {
378 let slots = definitions
379 .iter()
380 .copied()
381 .map(QueueSlot::new)
382 .collect::<Vec<_>>()
383 .into_boxed_slice();
384 let indices = slots
385 .iter()
386 .enumerate()
387 .map(|(index, slot)| (slot.id, index))
388 .collect();
389 Self {
390 slots,
391 indices,
392 notify: Notify::new(),
393 input_closed: AtomicBool::new(false),
394 runner_closed: AtomicBool::new(false),
395 }
396 }
397
398 pub(crate) fn contains(&self, id: QueueId) -> bool {
399 self.indices.contains_key(&id)
400 }
401
402 pub(crate) fn priority(&self, id: QueueId) -> Result<QueuePriority, QueueError> {
403 Ok(self.slot(id)?.priority())
404 }
405
406 pub(crate) fn set_priority(
407 &self,
408 id: QueueId,
409 priority: QueuePriority,
410 ) -> Result<(), QueueError> {
411 self.slot(id)?
412 .priority
413 .store(priority.encode(), Ordering::Release);
414 self.notify.notify_one();
415 Ok(())
416 }
417
418 pub(crate) fn set_weight(&self, id: QueueId, weight: u16) -> Result<(), QueueError> {
419 let priority = QueuePriority::weighted(weight).map_err(|_| QueueError::ZeroWeight)?;
420 self.set_priority(id, priority)
421 }
422
423 pub(crate) fn snapshot(&self, id: QueueId) -> Result<QueueSnapshot, QueueError> {
424 Ok(self.slot(id)?.snapshot())
425 }
426
427 pub(crate) fn snapshots(&self) -> Vec<QueueSnapshot> {
428 self.slots.iter().map(QueueSlot::snapshot).collect()
429 }
430
431 pub(crate) fn pending_total(&self) -> usize {
432 self.slots
433 .iter()
434 .map(|slot| slot.queued.load(Ordering::Acquire))
435 .sum()
436 }
437
438 pub(crate) async fn push(
439 &self,
440 id: QueueId,
441 item: T,
442 deadline: Instant,
443 ) -> Result<(), QueuePushError> {
444 let slot = self.slot(id).map_err(|_| QueuePushError::Unknown(id))?;
445 if self.runner_closed.load(Ordering::Acquire) {
446 return Err(QueuePushError::Closed);
447 }
448 let permit = timeout_at(deadline, Arc::clone(&slot.permits).acquire_owned())
449 .await
450 .map_err(|_| QueuePushError::Deadline)?
451 .map_err(|_| QueuePushError::Closed)?;
452 self.finish_push(slot, item, permit)
453 }
454
455 pub(crate) fn try_push(&self, id: QueueId, item: T) -> Result<(), QueuePushError> {
456 let slot = self.slot(id).map_err(|_| QueuePushError::Unknown(id))?;
457 if self.runner_closed.load(Ordering::Acquire) {
458 return Err(QueuePushError::Closed);
459 }
460 let permit =
461 Arc::clone(&slot.permits)
462 .try_acquire_owned()
463 .map_err(|error| match error {
464 TryAcquireError::NoPermits => QueuePushError::Full,
465 TryAcquireError::Closed => QueuePushError::Closed,
466 })?;
467 self.finish_push(slot, item, permit)
468 }
469
470 fn finish_push(
471 &self,
472 slot: &QueueSlot<T>,
473 item: T,
474 permit: OwnedSemaphorePermit,
475 ) -> Result<(), QueuePushError> {
476 if self.runner_closed.load(Ordering::Acquire) {
477 return Err(QueuePushError::Closed);
478 }
479 slot.entries().push_back(QueueEntry {
480 item,
481 _permit: permit,
482 });
483 slot.queued.fetch_add(1, Ordering::Release);
484 self.notify.notify_one();
485 Ok(())
486 }
487
488 pub(crate) fn pop_scheduled(
489 &self,
490 cursor: &mut QueueCursor,
491 ) -> Option<(QueueId, QueueEntry<T>)> {
492 self.pop_strict(cursor)
493 .or_else(|| self.pop_weighted(cursor))
494 }
495
496 fn pop_strict(&self, cursor: &mut QueueCursor) -> Option<(QueueId, QueueEntry<T>)> {
497 let rank = self
498 .slots
499 .iter()
500 .filter_map(|slot| match slot.priority() {
501 QueuePriority::Strict(rank) if slot.queued.load(Ordering::Acquire) > 0 => {
502 Some(rank)
503 }
504 QueuePriority::Weighted(_) | QueuePriority::Strict(_) => None,
505 })
506 .max()?;
507 for offset in 1..=self.slots.len() {
508 let index = (cursor.strict_index + offset) % self.slots.len();
509 let slot = &self.slots[index];
510 if slot.priority() == QueuePriority::Strict(rank)
511 && let Some(entry) = slot.pop_front()
512 {
513 cursor.strict_index = index;
514 return Some((slot.id, entry));
515 }
516 }
517 None
518 }
519
520 fn pop_weighted(&self, cursor: &mut QueueCursor) -> Option<(QueueId, QueueEntry<T>)> {
521 if self.slots.is_empty() {
522 return None;
523 }
524 if cursor.weighted_index >= self.slots.len() {
525 cursor.weighted_index = 0;
526 cursor.weighted_used = 0;
527 }
528 let current = &self.slots[cursor.weighted_index];
529 if let QueuePriority::Weighted(weight) = current.priority()
530 && cursor.weighted_used < weight.get()
531 && let Some(entry) = current.pop_front()
532 {
533 cursor.weighted_used = cursor.weighted_used.saturating_add(1);
534 return Some((current.id, entry));
535 }
536
537 for offset in 1..self.slots.len() {
538 let index = (cursor.weighted_index + offset) % self.slots.len();
539 let slot = &self.slots[index];
540 if matches!(slot.priority(), QueuePriority::Weighted(_))
541 && let Some(entry) = slot.pop_front()
542 {
543 cursor.weighted_index = index;
544 cursor.weighted_used = 1;
545 return Some((slot.id, entry));
546 }
547 }
548
549 if matches!(current.priority(), QueuePriority::Weighted(_))
550 && let Some(entry) = current.pop_front()
551 {
552 cursor.weighted_used = current.priority().weight().unwrap_or(1);
553 return Some((current.id, entry));
554 }
555 None
556 }
557
558 pub(crate) fn pop_from(&self, id: QueueId) -> Option<QueueEntry<T>> {
559 self.slot(id).ok()?.pop_front()
560 }
561
562 pub(crate) fn push_front(&self, id: QueueId, entry: QueueEntry<T>) {
563 if let Ok(slot) = self.slot(id) {
564 slot.push_front(entry);
565 self.notify.notify_one();
566 }
567 }
568
569 pub(crate) fn finish_entry(&self, id: QueueId, entry: QueueEntry<T>) -> T {
570 let item = entry.into_item();
571 if let Ok(slot) = self.slot(id) {
572 slot.queued.fetch_sub(1, Ordering::Release);
573 }
574 item
575 }
576
577 pub(crate) fn input_closed(&self) -> bool {
578 self.input_closed.load(Ordering::Acquire)
579 }
580
581 pub(crate) fn close_input(&self) {
582 self.input_closed.store(true, Ordering::Release);
583 self.notify.notify_waiters();
584 }
585
586 pub(crate) fn close_runner(&self) {
587 if !self.runner_closed.swap(true, Ordering::AcqRel) {
588 for slot in &self.slots {
589 slot.close();
590 }
591 self.notify.notify_waiters();
592 }
593 }
594
595 pub(crate) fn notified(&self) -> tokio::sync::futures::Notified<'_> {
596 self.notify.notified()
597 }
598
599 fn slot(&self, id: QueueId) -> Result<&QueueSlot<T>, QueueError> {
600 self.indices
601 .get(&id)
602 .map(|index| &self.slots[*index])
603 .ok_or(QueueError::Unknown(id))
604 }
605}