virtio_accel_split_queue/
chain.rs

1use alloc::boxed::Box;
2use alloc::rc::Rc;
3use alloc::vec::Vec;
4use core::cell::RefCell;
5use core::cmp::min;
6use core::fmt;
7use core::sync::atomic::{AtomicU64, Ordering};
8
9use virtio_accel_transport::{
10    ByteAccessError, ChainError, ChainId, ChainIo, ChainIoResult, ChainLayout, ChainRegion,
11    DeviceChain, DriverChainBuffer, MAX_SPLIT_QUEUE_SIZE, MalformedChain, QueueEpoch,
12    ReadableBytes, WritableBytes, validate_chain_layout,
13};
14
15/// Descriptor continues through its `next` field.
16pub const VIRTQ_DESC_F_NEXT: u16 = 1;
17/// Descriptor bytes are device-writable rather than device-readable.
18pub const VIRTQ_DESC_F_WRITE: u16 = 2;
19/// Descriptor points at an indirect descriptor table.
20pub const VIRTQ_DESC_F_INDIRECT: u16 = 4;
21
22const KNOWN_DESCRIPTOR_FLAGS: u16 = VIRTQ_DESC_F_NEXT | VIRTQ_DESC_F_WRITE | VIRTQ_DESC_F_INDIRECT;
23
24#[derive(Debug)]
25enum BufferStorage {
26    Mapped(Rc<RefCell<Box<[u8]>>>),
27    Unmapped(u64),
28}
29
30impl BufferStorage {
31    fn mapped(bytes: Vec<u8>) -> Self {
32        Self::Mapped(Rc::new(RefCell::new(bytes.into_boxed_slice())))
33    }
34
35    fn len(&self) -> u64 {
36        match self {
37            Self::Mapped(bytes) => bytes.borrow().len() as u64,
38            Self::Unmapped(bytes) => *bytes,
39        }
40    }
41
42    const fn is_mapped(&self) -> bool {
43        matches!(self, Self::Mapped(_))
44    }
45
46    fn read_at(&self, offset: u64, target: &mut [u8]) -> Result<(), ByteAccessError> {
47        let Self::Mapped(bytes) = self else {
48            return Err(ByteAccessError::Access);
49        };
50        let bytes = bytes.try_borrow().map_err(|_| ByteAccessError::Busy)?;
51        let range = checked_range(offset, target.len(), bytes.len())?;
52        target.copy_from_slice(&bytes[range]);
53        Ok(())
54    }
55
56    fn write_at(&self, offset: u64, source: &[u8]) -> Result<(), ByteAccessError> {
57        let Self::Mapped(bytes) = self else {
58            return Err(ByteAccessError::Access);
59        };
60        let mut bytes = bytes.try_borrow_mut().map_err(|_| ByteAccessError::Busy)?;
61        let range = checked_range(offset, source.len(), bytes.len())?;
62        bytes[range].copy_from_slice(source);
63        Ok(())
64    }
65}
66
67/// One address-free split-ring descriptor used by the in-memory model.
68#[derive(Debug)]
69pub struct Descriptor {
70    buffer: BufferStorage,
71    flags: u16,
72    next: u16,
73}
74
75impl Descriptor {
76    /// Construct one mapped device-readable descriptor.
77    pub fn readable(bytes: Vec<u8>) -> Self {
78        Self::raw(bytes, 0, 0)
79    }
80
81    /// Construct one mapped device-writable descriptor.
82    pub fn writable(bytes: Vec<u8>) -> Self {
83        Self::raw(bytes, VIRTQ_DESC_F_WRITE, 0)
84    }
85
86    /// Construct a mapped descriptor with raw split-ring flags and a local next index.
87    pub fn raw(bytes: Vec<u8>, flags: u16, next: u16) -> Self {
88        Self {
89            buffer: BufferStorage::mapped(bytes),
90            flags,
91            next,
92        }
93    }
94
95    /// Construct an unmapped descriptor for deterministic addressability tests.
96    pub const fn unmapped(bytes: u64, flags: u16, next: u16) -> Self {
97        Self {
98            buffer: BufferStorage::Unmapped(bytes),
99            flags,
100            next,
101        }
102    }
103
104    /// Descriptor length.
105    pub fn len(&self) -> u64 {
106        self.buffer.len()
107    }
108
109    /// Whether this descriptor has zero length.
110    pub fn is_empty(&self) -> bool {
111        self.len() == 0
112    }
113
114    /// Raw split-ring flags.
115    pub const fn flags(&self) -> u16 {
116        self.flags
117    }
118
119    /// Local next index used by [`DriverChain::raw`].
120    pub const fn next(&self) -> u16 {
121        self.next
122    }
123
124    const fn is_writable(&self) -> bool {
125        self.flags & VIRTQ_DESC_F_WRITE != 0
126    }
127}
128
129/// Failure while constructing driver-owned chain storage.
130#[derive(Clone, Copy, Debug, PartialEq, Eq)]
131pub enum ChainBuildError {
132    /// A chain must contain at least one descriptor.
133    Empty,
134    /// The supplied descriptor vector exceeds the maximum split queue size.
135    DescriptorCount,
136    /// Allocation of bounded chain metadata failed.
137    AllocationFailed,
138    /// A driver-created direct chain is malformed.
139    Malformed(MalformedChain),
140}
141
142#[derive(Debug)]
143enum ChainAnalysis {
144    Valid {
145        layout: ChainLayout,
146        order: Box<[u16]>,
147        regions: Box<[ChainRegion]>,
148    },
149    Invalid(MalformedChain),
150}
151
152impl ChainAnalysis {
153    const fn validation(&self) -> Result<ChainLayout, MalformedChain> {
154        match self {
155            Self::Valid { layout, .. } => Ok(*layout),
156            Self::Invalid(error) => Err(*error),
157        }
158    }
159
160    fn order(&self) -> &[u16] {
161        match self {
162            Self::Valid { order, .. } => order,
163            Self::Invalid(_) => &[],
164        }
165    }
166
167    fn regions(&self) -> &[ChainRegion] {
168        match self {
169            Self::Valid { regions, .. } => regions,
170            Self::Invalid(_) => &[],
171        }
172    }
173}
174
175#[derive(Debug)]
176pub(crate) struct ChainData {
177    descriptors: Box<[Descriptor]>,
178    analysis: ChainAnalysis,
179}
180
181/// Driver-owned descriptor chain and buffers.
182///
183/// Construction allocates metadata proportional only to the caller-provided descriptor vector.
184/// Queue publication, completion, and reset do not allocate or copy payload bytes.
185#[derive(Debug)]
186pub struct DriverChain {
187    data: Rc<ChainData>,
188    slots: Box<[u16]>,
189    head: u16,
190}
191
192impl DriverChain {
193    /// Construct a valid direct chain linked in vector order.
194    pub fn direct(mut descriptors: Vec<Descriptor>) -> Result<Self, ChainBuildError> {
195        let descriptor_count = descriptors.len();
196        for (index, descriptor) in descriptors.iter_mut().enumerate() {
197            descriptor.flags &= VIRTQ_DESC_F_WRITE;
198            if index + 1 < descriptor_count {
199                descriptor.flags |= VIRTQ_DESC_F_NEXT;
200                descriptor.next = (index + 1) as u16;
201            } else {
202                descriptor.next = 0;
203            }
204        }
205        let chain = Self::raw(descriptors, 0)?;
206        if let Err(error) = chain.validation() {
207            return Err(ChainBuildError::Malformed(error));
208        }
209        Ok(chain)
210    }
211
212    /// Construct a raw descriptor table for deterministic malformed-chain injection.
213    ///
214    /// `next` values are local indices in `descriptors`. Structural errors are retained and later
215    /// exposed by [`SplitDeviceChain::io`] when the chain is injected into a queue.
216    pub fn raw(descriptors: Vec<Descriptor>, head: u16) -> Result<Self, ChainBuildError> {
217        if descriptors.is_empty() {
218            return Err(ChainBuildError::Empty);
219        }
220        if descriptors.len() > usize::from(MAX_SPLIT_QUEUE_SIZE) {
221            return Err(ChainBuildError::DescriptorCount);
222        }
223
224        let mut slots = zeroed_u16_box(descriptors.len())?;
225        let analysis = analyze_chain(&descriptors, head, &mut slots)?;
226        Ok(Self {
227            data: Rc::new(ChainData {
228                descriptors: descriptors.into_boxed_slice(),
229                analysis,
230            }),
231            slots,
232            head,
233        })
234    }
235
236    /// Number of descriptor-table entries owned by this chain.
237    pub fn descriptor_count(&self) -> u16 {
238        self.data.descriptors.len() as u16
239    }
240
241    /// Validate descriptor topology independently of a queue's configured chain limit.
242    pub fn validation(&self) -> Result<ChainLayout, MalformedChain> {
243        self.data.analysis.validation()
244    }
245
246    /// Read bytes from one local descriptor after the queue returns ownership.
247    pub fn read_descriptor(
248        &self,
249        index: u16,
250        offset: u64,
251        target: &mut [u8],
252    ) -> Result<(), ByteAccessError> {
253        self.descriptor(index)?.buffer.read_at(offset, target)
254    }
255
256    /// Write bytes into one local descriptor while the driver owns the chain.
257    pub fn write_descriptor(
258        &self,
259        index: u16,
260        offset: u64,
261        source: &[u8],
262    ) -> Result<(), ByteAccessError> {
263        self.descriptor(index)?.buffer.write_at(offset, source)
264    }
265
266    fn descriptor(&self, index: u16) -> Result<&Descriptor, ByteAccessError> {
267        self.data
268            .descriptors
269            .get(usize::from(index))
270            .ok_or(ByteAccessError::OutOfBounds)
271    }
272
273    pub(crate) fn data(&self) -> Rc<ChainData> {
274        Rc::clone(&self.data)
275    }
276
277    pub(crate) fn slots(&self) -> &[u16] {
278        &self.slots
279    }
280
281    pub(crate) fn slots_mut(&mut self) -> &mut [u16] {
282        &mut self.slots
283    }
284
285    pub(crate) fn queue_head_slot(&self) -> u16 {
286        self.slots
287            .get(usize::from(self.head))
288            .copied()
289            .unwrap_or(self.slots[0])
290    }
291}
292
293impl DriverChainBuffer for DriverChain {
294    type Error = ByteAccessError;
295
296    fn device_readable_len(&self) -> u64 {
297        self.data
298            .analysis
299            .validation()
300            .map_or(0, ChainLayout::readable_bytes)
301    }
302
303    fn device_writable_len(&self) -> u64 {
304        self.data
305            .analysis
306            .validation()
307            .map_or(0, ChainLayout::writable_bytes)
308    }
309
310    fn write_device_readable(&mut self, offset: u64, source: &[u8]) -> Result<(), Self::Error> {
311        checked_logical_range(offset, source.len(), self.device_readable_len())?;
312        copy_to_descriptors(&self.data, false, offset, source)
313    }
314
315    fn read_device_writable(&self, offset: u64, target: &mut [u8]) -> Result<(), Self::Error> {
316        checked_logical_range(offset, target.len(), self.device_writable_len())?;
317        copy_from_descriptors(&self.data, true, offset, target)
318    }
319}
320
321/// Device-readable concatenation of a valid chain's readable descriptors.
322pub struct SplitSource {
323    data: Rc<ChainData>,
324    epoch: QueueEpoch,
325    current_epoch: Rc<AtomicU64>,
326}
327
328impl fmt::Debug for SplitSource {
329    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
330        formatter
331            .debug_struct("SplitSource")
332            .field("len", &self.len())
333            .field("epoch", &self.epoch)
334            .finish()
335    }
336}
337
338impl ReadableBytes for SplitSource {
339    fn len(&self) -> u64 {
340        self.data
341            .analysis
342            .validation()
343            .map_or(0, ChainLayout::readable_bytes)
344    }
345
346    fn read_at(&self, offset: u64, target: &mut [u8]) -> Result<(), ByteAccessError> {
347        self.check_epoch()?;
348        checked_logical_range(offset, target.len(), self.len())?;
349        copy_from_descriptors(&self.data, false, offset, target)
350    }
351}
352
353impl SplitSource {
354    fn check_epoch(&self) -> Result<(), ByteAccessError> {
355        if self.current_epoch.load(Ordering::Acquire) == self.epoch.get() {
356            Ok(())
357        } else {
358            Err(ByteAccessError::Reset)
359        }
360    }
361}
362
363/// Device-writable concatenation of a valid chain's writable descriptors.
364pub struct SplitSink {
365    data: Rc<ChainData>,
366    epoch: QueueEpoch,
367    current_epoch: Rc<AtomicU64>,
368}
369
370impl fmt::Debug for SplitSink {
371    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
372        formatter
373            .debug_struct("SplitSink")
374            .field("len", &self.len())
375            .field("epoch", &self.epoch)
376            .finish()
377    }
378}
379
380impl WritableBytes for SplitSink {
381    fn len(&self) -> u64 {
382        self.data
383            .analysis
384            .validation()
385            .map_or(0, ChainLayout::writable_bytes)
386    }
387
388    fn write_at(&mut self, offset: u64, source: &[u8]) -> Result<(), ByteAccessError> {
389        self.check_epoch()?;
390        checked_logical_range(offset, source.len(), self.len())?;
391        copy_to_descriptors(&self.data, true, offset, source)
392    }
393}
394
395impl SplitSink {
396    fn check_epoch(&self) -> Result<(), ByteAccessError> {
397        if self.current_epoch.load(Ordering::Acquire) == self.epoch.get() {
398            Ok(())
399        } else {
400            Err(ByteAccessError::Reset)
401        }
402    }
403}
404
405/// Non-copyable device ownership token for one available descriptor chain.
406#[derive(Debug)]
407pub struct SplitDeviceChain {
408    id: ChainId,
409    data: Rc<ChainData>,
410    max_descriptors: u16,
411    source: SplitSource,
412    sink: SplitSink,
413}
414
415impl SplitDeviceChain {
416    pub(crate) fn new(
417        id: ChainId,
418        data: Rc<ChainData>,
419        max_descriptors: u16,
420        current_epoch: Rc<AtomicU64>,
421    ) -> Self {
422        let source = SplitSource {
423            data: Rc::clone(&data),
424            epoch: id.epoch(),
425            current_epoch: Rc::clone(&current_epoch),
426        };
427        let sink = SplitSink {
428            data: Rc::clone(&data),
429            epoch: id.epoch(),
430            current_epoch,
431        };
432        Self {
433            id,
434            data,
435            max_descriptors,
436            source,
437            sink,
438        }
439    }
440
441    pub(crate) fn writable_capacity(&self) -> u64 {
442        self.data
443            .analysis
444            .validation()
445            .map_or(0, ChainLayout::writable_bytes)
446    }
447
448    fn check_epoch(&self) -> Result<(), ChainError<ByteAccessError>> {
449        let current = QueueEpoch::new(self.sink.current_epoch.load(Ordering::Acquire))
450            .expect("queue epochs are always nonzero");
451        if current == self.id.epoch() {
452            Ok(())
453        } else {
454            Err(ChainError::ResetRace {
455                chain: self.id.epoch(),
456                current,
457            })
458        }
459    }
460}
461
462impl DeviceChain for SplitDeviceChain {
463    type Request = SplitSource;
464    type Response = SplitSink;
465    type Error = ByteAccessError;
466
467    fn id(&self) -> ChainId {
468        self.id
469    }
470
471    fn io(&mut self) -> ChainIoResult<'_, Self::Request, Self::Response, Self::Error> {
472        self.check_epoch()?;
473        let layout = self
474            .data
475            .analysis
476            .validation()
477            .map_err(ChainError::Malformed)?;
478        if layout.descriptor_count() > self.max_descriptors {
479            return Err(ChainError::Malformed(MalformedChain::DescriptorCount));
480        }
481        Ok(ChainIo::new(
482            self.data.analysis.regions(),
483            &self.source,
484            &mut self.sink,
485        ))
486    }
487}
488
489fn analyze_chain(
490    descriptors: &[Descriptor],
491    head: u16,
492    visited: &mut [u16],
493) -> Result<ChainAnalysis, ChainBuildError> {
494    let mut order = Vec::new();
495    order
496        .try_reserve_exact(descriptors.len())
497        .map_err(|_| ChainBuildError::AllocationFailed)?;
498    let mut regions = Vec::new();
499    regions
500        .try_reserve_exact(descriptors.len())
501        .map_err(|_| ChainBuildError::AllocationFailed)?;
502
503    let mut current = head;
504    loop {
505        let Some(descriptor) = descriptors.get(usize::from(current)) else {
506            return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorIndex));
507        };
508        if visited[usize::from(current)] != 0 {
509            return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorLoop));
510        }
511        visited[usize::from(current)] = 1;
512        if descriptor.flags & !KNOWN_DESCRIPTOR_FLAGS != 0 {
513            return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorFlags));
514        }
515        if descriptor.flags & VIRTQ_DESC_F_INDIRECT != 0 {
516            return Ok(ChainAnalysis::Invalid(MalformedChain::IndirectUnsupported));
517        }
518        if !descriptor.buffer.is_mapped() {
519            return Ok(ChainAnalysis::Invalid(MalformedChain::Address));
520        }
521
522        order.push(current);
523        regions.push(if descriptor.is_writable() {
524            ChainRegion::writable(descriptor.len())
525        } else {
526            ChainRegion::readable(descriptor.len())
527        });
528
529        if descriptor.flags & VIRTQ_DESC_F_NEXT == 0 {
530            break;
531        }
532        current = descriptor.next;
533    }
534
535    if order.len() != descriptors.len() {
536        return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorCount));
537    }
538
539    let layout = match validate_chain_layout(&regions, u16::MAX) {
540        Ok(layout) => layout,
541        Err(error) => return Ok(ChainAnalysis::Invalid(error.into())),
542    };
543    Ok(ChainAnalysis::Valid {
544        layout,
545        order: order.into_boxed_slice(),
546        regions: regions.into_boxed_slice(),
547    })
548}
549
550fn copy_from_descriptors(
551    data: &ChainData,
552    writable: bool,
553    offset: u64,
554    target: &mut [u8],
555) -> Result<(), ByteAccessError> {
556    if target.is_empty() {
557        return Ok(());
558    }
559    let mut skip = offset;
560    let mut copied = 0;
561    for index in data.analysis.order() {
562        let descriptor = &data.descriptors[usize::from(*index)];
563        if descriptor.is_writable() != writable {
564            continue;
565        }
566        if skip >= descriptor.len() {
567            skip -= descriptor.len();
568            continue;
569        }
570        let available = usize::try_from(descriptor.len() - skip).unwrap_or(usize::MAX);
571        let count = min(available, target.len() - copied);
572        descriptor
573            .buffer
574            .read_at(skip, &mut target[copied..copied + count])?;
575        copied += count;
576        skip = 0;
577        if copied == target.len() {
578            return Ok(());
579        }
580    }
581    Err(ByteAccessError::OutOfBounds)
582}
583
584fn copy_to_descriptors(
585    data: &ChainData,
586    writable: bool,
587    offset: u64,
588    source: &[u8],
589) -> Result<(), ByteAccessError> {
590    if source.is_empty() {
591        return Ok(());
592    }
593    let mut skip = offset;
594    let mut copied = 0;
595    for index in data.analysis.order() {
596        let descriptor = &data.descriptors[usize::from(*index)];
597        if descriptor.is_writable() != writable {
598            continue;
599        }
600        if skip >= descriptor.len() {
601            skip -= descriptor.len();
602            continue;
603        }
604        let available = usize::try_from(descriptor.len() - skip).unwrap_or(usize::MAX);
605        let count = min(available, source.len() - copied);
606        descriptor
607            .buffer
608            .write_at(skip, &source[copied..copied + count])?;
609        copied += count;
610        skip = 0;
611        if copied == source.len() {
612            return Ok(());
613        }
614    }
615    Err(ByteAccessError::OutOfBounds)
616}
617
618fn zeroed_u16_box(len: usize) -> Result<Box<[u16]>, ChainBuildError> {
619    let mut values = Vec::new();
620    values
621        .try_reserve_exact(len)
622        .map_err(|_| ChainBuildError::AllocationFailed)?;
623    values.resize(len, 0);
624    Ok(values.into_boxed_slice())
625}
626
627fn checked_logical_range(offset: u64, bytes: usize, len: u64) -> Result<(), ByteAccessError> {
628    let bytes = u64::try_from(bytes).map_err(|_| ByteAccessError::OutOfBounds)?;
629    let end = offset
630        .checked_add(bytes)
631        .ok_or(ByteAccessError::OutOfBounds)?;
632    if end > len {
633        return Err(ByteAccessError::OutOfBounds);
634    }
635    Ok(())
636}
637
638fn checked_range(
639    offset: u64,
640    bytes: usize,
641    len: usize,
642) -> Result<core::ops::Range<usize>, ByteAccessError> {
643    let start = usize::try_from(offset).map_err(|_| ByteAccessError::OutOfBounds)?;
644    let end = start
645        .checked_add(bytes)
646        .filter(|end| *end <= len)
647        .ok_or(ByteAccessError::OutOfBounds)?;
648    Ok(start..end)
649}
virtio_accel_split_queue/chain.rs

virtio_accel_split_queue/
chain.rs
