Skip to main content

hart_link/service/
queue_set.rs

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
17/// Maximum capacity of one request queue.
18pub const MAXIMUM_QUEUE_CAPACITY: usize = 1_048_576;
19/// Maximum total capacity reserved by all queues of one link.
20pub const MAXIMUM_TOTAL_QUEUE_CAPACITY: usize = 1_048_576;
21/// Maximum number of independently scheduled queues on one physical link.
22pub const MAXIMUM_LINK_QUEUES: usize = 256;
23
24/// Stable application-defined identifier of one queue.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
26pub struct QueueId(u16);
27
28impl QueueId {
29    /// Identifier used by the default one-queue configuration.
30    pub const DEFAULT: Self = Self(0);
31
32    /// Creates an identifier without allocating or registering global names.
33    pub const fn new(value: u16) -> Self {
34        Self(value)
35    }
36
37    /// Returns the numeric representation.
38    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/// Scheduling policy of one queue.
56#[derive(Debug, Clone, Copy, PartialEq, Eq)]
57pub enum QueuePriority {
58    /// Starvation-free weighted rotation among all ready weighted queues.
59    Weighted(NonZeroU16),
60    /// Absolute priority over every weighted queue. Larger ranks are selected first.
61    ///
62    /// Strict queues of equal rank rotate fairly. A continuously ready strict queue can
63    /// intentionally starve weighted queues, so this mode must be selected explicitly.
64    Strict(u16),
65}
66
67impl QueuePriority {
68    /// Creates a starvation-free weighted priority.
69    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    /// Creates an absolute priority. Larger ranks win over smaller strict ranks.
77    pub const fn strict(rank: u16) -> Self {
78        Self::Strict(rank)
79    }
80
81    /// Returns the weighted quota, or `None` for an absolute priority.
82    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    /// Returns the strict rank, or `None` for a weighted priority.
90    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/// Validated configuration of one independently bounded queue.
126#[derive(Debug, Clone, Copy, PartialEq, Eq)]
127pub struct QueueConfig {
128    id: QueueId,
129    capacity: usize,
130    priority: QueuePriority,
131}
132
133impl QueueConfig {
134    /// Creates a queue participating in starvation-free weighted scheduling.
135    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    /// Creates a queue with absolute priority over weighted queues.
144    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    /// Creates a queue with an explicit scheduling policy.
153    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    /// Returns the queue identifier.
175    pub const fn id(self) -> QueueId {
176        self.id
177    }
178
179    /// Returns the independently enforced capacity.
180    pub const fn capacity(self) -> usize {
181        self.capacity
182    }
183
184    /// Returns the initial scheduling policy.
185    pub const fn priority(self) -> QueuePriority {
186        self.priority
187    }
188}
189
190/// Invalid queue layout.
191#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
192pub enum QueueConfigError {
193    /// Every queue must admit at least one request.
194    #[error("queue {0} capacity must be greater than zero")]
195    ZeroCapacity(QueueId),
196    /// One queue is too large for the runtime safety bound.
197    #[error("queue {queue} capacity {capacity} exceeds the supported limit")]
198    CapacityLimit {
199        /// Invalid queue.
200        queue: QueueId,
201        /// Requested capacity.
202        capacity: usize,
203    },
204    /// A zero weighted quota would prevent progress.
205    #[error("weighted queue priority must be greater than zero")]
206    ZeroWeight,
207    /// The same identifier was configured more than once.
208    #[error("queue id {0} is configured more than once")]
209    DuplicateId(QueueId),
210    /// A link must contain at least one queue.
211    #[error("a link requires at least one queue")]
212    Empty,
213    /// One link contains too many scheduler classes.
214    #[error("a link supports at most {MAXIMUM_LINK_QUEUES} queues")]
215    TooManyQueues,
216    /// Aggregate bounded capacity is excessive.
217    #[error("total queue capacity {0} exceeds the supported limit")]
218    TotalCapacity(usize),
219    /// The selected default queue does not exist in the layout.
220    #[error("default queue {0} is not configured")]
221    MissingDefault(QueueId),
222}
223
224/// Runtime state of one configured queue.
225#[derive(Debug, Clone, Copy, PartialEq, Eq)]
226#[non_exhaustive]
227pub struct QueueSnapshot {
228    /// Queue identifier.
229    pub id: QueueId,
230    /// Fixed queue capacity.
231    pub capacity: usize,
232    /// Requests currently occupying this queue.
233    pub queued: usize,
234    /// Current scheduling policy.
235    pub priority: QueuePriority,
236}
237
238/// Error from selecting or reconfiguring one queue.
239#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
240pub enum QueueError {
241    /// The identifier is not part of this link.
242    #[error("queue {0} is not configured on this link")]
243    Unknown(QueueId),
244    /// A zero weighted quota would prevent progress.
245    #[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}