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        spans: Box<[DescriptorSpan]>,
147        regions: Box<[ChainRegion]>,
148    },
149    Invalid(MalformedChain),
150}
151
152#[derive(Clone, Copy, Debug, PartialEq, Eq)]
153struct DescriptorSpan {
154    descriptor: u16,
155    end: u64,
156}
157
158impl ChainAnalysis {
159    const fn validation(&self) -> Result<ChainLayout, MalformedChain> {
160        match self {
161            Self::Valid { layout, .. } => Ok(*layout),
162            Self::Invalid(error) => Err(*error),
163        }
164    }
165
166    fn spans(&self, writable: bool) -> &[DescriptorSpan] {
167        match self {
168            Self::Valid { layout, spans, .. } => {
169                let readable = usize::from(layout.readable_descriptors());
170                if writable {
171                    &spans[readable..]
172                } else {
173                    &spans[..readable]
174                }
175            }
176            Self::Invalid(_) => &[],
177        }
178    }
179
180    fn regions(&self) -> &[ChainRegion] {
181        match self {
182            Self::Valid { regions, .. } => regions,
183            Self::Invalid(_) => &[],
184        }
185    }
186}
187
188#[derive(Debug)]
189pub(crate) struct ChainData {
190    descriptors: Box<[Descriptor]>,
191    analysis: ChainAnalysis,
192}
193
194/// Driver-owned descriptor chain and buffers.
195///
196/// Construction allocates metadata proportional only to the caller-provided descriptor vector.
197/// Queue publication, completion, and reset do not allocate or copy payload bytes.
198#[derive(Debug)]
199pub struct DriverChain {
200    data: Rc<ChainData>,
201    slots: Box<[u16]>,
202    head: u16,
203}
204
205impl DriverChain {
206    /// Construct a valid direct chain linked in vector order.
207    pub fn direct(mut descriptors: Vec<Descriptor>) -> Result<Self, ChainBuildError> {
208        let descriptor_count = descriptors.len();
209        for (index, descriptor) in descriptors.iter_mut().enumerate() {
210            descriptor.flags &= VIRTQ_DESC_F_WRITE;
211            if index + 1 < descriptor_count {
212                descriptor.flags |= VIRTQ_DESC_F_NEXT;
213                descriptor.next = (index + 1) as u16;
214            } else {
215                descriptor.next = 0;
216            }
217        }
218        let chain = Self::raw(descriptors, 0)?;
219        if let Err(error) = chain.validation() {
220            return Err(ChainBuildError::Malformed(error));
221        }
222        Ok(chain)
223    }
224
225    /// Construct a raw descriptor table for deterministic malformed-chain injection.
226    ///
227    /// `next` values are local indices in `descriptors`. Structural errors are retained and later
228    /// exposed by [`SplitDeviceChain::io`] when the chain is injected into a queue.
229    pub fn raw(descriptors: Vec<Descriptor>, head: u16) -> Result<Self, ChainBuildError> {
230        if descriptors.is_empty() {
231            return Err(ChainBuildError::Empty);
232        }
233        if descriptors.len() > usize::from(MAX_SPLIT_QUEUE_SIZE) {
234            return Err(ChainBuildError::DescriptorCount);
235        }
236
237        let mut slots = zeroed_u16_box(descriptors.len())?;
238        let analysis = analyze_chain(&descriptors, head, &mut slots)?;
239        Ok(Self {
240            data: Rc::new(ChainData {
241                descriptors: descriptors.into_boxed_slice(),
242                analysis,
243            }),
244            slots,
245            head,
246        })
247    }
248
249    /// Number of descriptor-table entries owned by this chain.
250    pub fn descriptor_count(&self) -> u16 {
251        self.data.descriptors.len() as u16
252    }
253
254    /// Validate descriptor topology independently of a queue's configured chain limit.
255    pub fn validation(&self) -> Result<ChainLayout, MalformedChain> {
256        self.data.analysis.validation()
257    }
258
259    /// Read bytes from one local descriptor after the queue returns ownership.
260    pub fn read_descriptor(
261        &self,
262        index: u16,
263        offset: u64,
264        target: &mut [u8],
265    ) -> Result<(), ByteAccessError> {
266        self.descriptor(index)?.buffer.read_at(offset, target)
267    }
268
269    /// Write bytes into one local descriptor while the driver owns the chain.
270    pub fn write_descriptor(
271        &self,
272        index: u16,
273        offset: u64,
274        source: &[u8],
275    ) -> Result<(), ByteAccessError> {
276        self.descriptor(index)?.buffer.write_at(offset, source)
277    }
278
279    fn descriptor(&self, index: u16) -> Result<&Descriptor, ByteAccessError> {
280        self.data
281            .descriptors
282            .get(usize::from(index))
283            .ok_or(ByteAccessError::OutOfBounds)
284    }
285
286    pub(crate) fn data(&self) -> Rc<ChainData> {
287        Rc::clone(&self.data)
288    }
289
290    pub(crate) fn slots(&self) -> &[u16] {
291        &self.slots
292    }
293
294    pub(crate) fn slots_mut(&mut self) -> &mut [u16] {
295        &mut self.slots
296    }
297
298    pub(crate) fn queue_head_slot(&self) -> u16 {
299        self.slots
300            .get(usize::from(self.head))
301            .copied()
302            .unwrap_or(self.slots[0])
303    }
304}
305
306impl DriverChainBuffer for DriverChain {
307    type Error = ByteAccessError;
308
309    fn device_readable_len(&self) -> u64 {
310        self.data
311            .analysis
312            .validation()
313            .map_or(0, ChainLayout::readable_bytes)
314    }
315
316    fn device_writable_len(&self) -> u64 {
317        self.data
318            .analysis
319            .validation()
320            .map_or(0, ChainLayout::writable_bytes)
321    }
322
323    fn write_device_readable(&mut self, offset: u64, source: &[u8]) -> Result<(), Self::Error> {
324        checked_logical_range(offset, source.len(), self.device_readable_len())?;
325        copy_to_descriptors(&self.data, false, offset, source)
326    }
327
328    fn read_device_writable(&self, offset: u64, target: &mut [u8]) -> Result<(), Self::Error> {
329        checked_logical_range(offset, target.len(), self.device_writable_len())?;
330        copy_from_descriptors(&self.data, true, offset, target)
331    }
332}
333
334/// Device-readable concatenation of a valid chain's readable descriptors.
335pub struct SplitSource {
336    data: Rc<ChainData>,
337    epoch: QueueEpoch,
338    current_epoch: Rc<AtomicU64>,
339}
340
341impl fmt::Debug for SplitSource {
342    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
343        formatter
344            .debug_struct("SplitSource")
345            .field("len", &self.len())
346            .field("epoch", &self.epoch)
347            .finish()
348    }
349}
350
351impl ReadableBytes for SplitSource {
352    fn len(&self) -> u64 {
353        self.data
354            .analysis
355            .validation()
356            .map_or(0, ChainLayout::readable_bytes)
357    }
358
359    fn read_at(&self, offset: u64, target: &mut [u8]) -> Result<(), ByteAccessError> {
360        self.check_epoch()?;
361        checked_logical_range(offset, target.len(), self.len())?;
362        copy_from_descriptors(&self.data, false, offset, target)
363    }
364}
365
366impl SplitSource {
367    fn check_epoch(&self) -> Result<(), ByteAccessError> {
368        if self.current_epoch.load(Ordering::Acquire) == self.epoch.get() {
369            Ok(())
370        } else {
371            Err(ByteAccessError::Reset)
372        }
373    }
374}
375
376/// Device-writable concatenation of a valid chain's writable descriptors.
377pub struct SplitSink {
378    data: Rc<ChainData>,
379    epoch: QueueEpoch,
380    current_epoch: Rc<AtomicU64>,
381}
382
383impl fmt::Debug for SplitSink {
384    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
385        formatter
386            .debug_struct("SplitSink")
387            .field("len", &self.len())
388            .field("epoch", &self.epoch)
389            .finish()
390    }
391}
392
393impl WritableBytes for SplitSink {
394    fn len(&self) -> u64 {
395        self.data
396            .analysis
397            .validation()
398            .map_or(0, ChainLayout::writable_bytes)
399    }
400
401    fn write_at(&mut self, offset: u64, source: &[u8]) -> Result<(), ByteAccessError> {
402        self.check_epoch()?;
403        checked_logical_range(offset, source.len(), self.len())?;
404        copy_to_descriptors(&self.data, true, offset, source)
405    }
406}
407
408impl SplitSink {
409    fn check_epoch(&self) -> Result<(), ByteAccessError> {
410        if self.current_epoch.load(Ordering::Acquire) == self.epoch.get() {
411            Ok(())
412        } else {
413            Err(ByteAccessError::Reset)
414        }
415    }
416}
417
418/// Non-copyable device ownership token for one available descriptor chain.
419#[derive(Debug)]
420pub struct SplitDeviceChain {
421    id: ChainId,
422    data: Rc<ChainData>,
423    max_descriptors: u16,
424    source: SplitSource,
425    sink: SplitSink,
426}
427
428impl SplitDeviceChain {
429    pub(crate) fn new(
430        id: ChainId,
431        data: Rc<ChainData>,
432        max_descriptors: u16,
433        current_epoch: Rc<AtomicU64>,
434    ) -> Self {
435        let source = SplitSource {
436            data: Rc::clone(&data),
437            epoch: id.epoch(),
438            current_epoch: Rc::clone(&current_epoch),
439        };
440        let sink = SplitSink {
441            data: Rc::clone(&data),
442            epoch: id.epoch(),
443            current_epoch,
444        };
445        Self {
446            id,
447            data,
448            max_descriptors,
449            source,
450            sink,
451        }
452    }
453
454    pub(crate) fn writable_capacity(&self) -> u64 {
455        self.data
456            .analysis
457            .validation()
458            .map_or(0, ChainLayout::writable_bytes)
459    }
460
461    fn check_epoch(&self) -> Result<(), ChainError<ByteAccessError>> {
462        let current = QueueEpoch::new(self.sink.current_epoch.load(Ordering::Acquire))
463            .expect("queue epochs are always nonzero");
464        if current == self.id.epoch() {
465            Ok(())
466        } else {
467            Err(ChainError::ResetRace {
468                chain: self.id.epoch(),
469                current,
470            })
471        }
472    }
473}
474
475impl DeviceChain for SplitDeviceChain {
476    type Request = SplitSource;
477    type Response = SplitSink;
478    type Error = ByteAccessError;
479
480    fn id(&self) -> ChainId {
481        self.id
482    }
483
484    fn io(&mut self) -> ChainIoResult<'_, Self::Request, Self::Response, Self::Error> {
485        self.check_epoch()?;
486        let layout = self
487            .data
488            .analysis
489            .validation()
490            .map_err(ChainError::Malformed)?;
491        if layout.descriptor_count() > self.max_descriptors {
492            return Err(ChainError::Malformed(MalformedChain::DescriptorCount));
493        }
494        Ok(ChainIo::new(
495            self.data.analysis.regions(),
496            &self.source,
497            &mut self.sink,
498        ))
499    }
500}
501
502fn analyze_chain(
503    descriptors: &[Descriptor],
504    head: u16,
505    visited: &mut [u16],
506) -> Result<ChainAnalysis, ChainBuildError> {
507    let mut spans = Vec::new();
508    spans
509        .try_reserve_exact(descriptors.len())
510        .map_err(|_| ChainBuildError::AllocationFailed)?;
511    let mut regions = Vec::new();
512    regions
513        .try_reserve_exact(descriptors.len())
514        .map_err(|_| ChainBuildError::AllocationFailed)?;
515
516    let mut readable_end = 0_u64;
517    let mut writable_end = 0_u64;
518    let mut current = head;
519    loop {
520        let Some(descriptor) = descriptors.get(usize::from(current)) else {
521            return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorIndex));
522        };
523        if visited[usize::from(current)] != 0 {
524            return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorLoop));
525        }
526        visited[usize::from(current)] = 1;
527        if descriptor.flags & !KNOWN_DESCRIPTOR_FLAGS != 0 {
528            return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorFlags));
529        }
530        if descriptor.flags & VIRTQ_DESC_F_INDIRECT != 0 {
531            return Ok(ChainAnalysis::Invalid(MalformedChain::IndirectUnsupported));
532        }
533        if !descriptor.buffer.is_mapped() {
534            return Ok(ChainAnalysis::Invalid(MalformedChain::Address));
535        }
536
537        let logical_end = if descriptor.is_writable() {
538            &mut writable_end
539        } else {
540            &mut readable_end
541        };
542        let Some(end) = logical_end.checked_add(descriptor.len()) else {
543            return Ok(ChainAnalysis::Invalid(MalformedChain::LengthOverflow));
544        };
545        *logical_end = end;
546        spans.push(DescriptorSpan {
547            descriptor: current,
548            end,
549        });
550        regions.push(if descriptor.is_writable() {
551            ChainRegion::writable(descriptor.len())
552        } else {
553            ChainRegion::readable(descriptor.len())
554        });
555
556        if descriptor.flags & VIRTQ_DESC_F_NEXT == 0 {
557            break;
558        }
559        current = descriptor.next;
560    }
561
562    if spans.len() != descriptors.len() {
563        return Ok(ChainAnalysis::Invalid(MalformedChain::DescriptorCount));
564    }
565
566    let layout = match validate_chain_layout(&regions, u16::MAX) {
567        Ok(layout) => layout,
568        Err(error) => return Ok(ChainAnalysis::Invalid(error.into())),
569    };
570    Ok(ChainAnalysis::Valid {
571        layout,
572        spans: spans.into_boxed_slice(),
573        regions: regions.into_boxed_slice(),
574    })
575}
576
577fn first_touched_span(spans: &[DescriptorSpan], offset: u64) -> usize {
578    spans.partition_point(|span| span.end <= offset)
579}
580
581fn copy_from_descriptors(
582    data: &ChainData,
583    writable: bool,
584    offset: u64,
585    target: &mut [u8],
586) -> Result<(), ByteAccessError> {
587    if target.is_empty() {
588        return Ok(());
589    }
590    let mut copied = 0;
591    let spans = data.analysis.spans(writable);
592    let first = first_touched_span(spans, offset);
593    for (index, span) in spans.iter().enumerate().skip(first) {
594        let descriptor = &data.descriptors[usize::from(span.descriptor)];
595        let span_start = index.checked_sub(1).map_or(0, |prior| spans[prior].end);
596        let logical_offset = offset + copied as u64;
597        let descriptor_offset = logical_offset
598            .checked_sub(span_start)
599            .ok_or(ByteAccessError::OutOfBounds)?;
600        let span_remaining = span
601            .end
602            .checked_sub(logical_offset)
603            .ok_or(ByteAccessError::OutOfBounds)?;
604        let available = usize::try_from(span_remaining).unwrap_or(usize::MAX);
605        let count = min(available, target.len() - copied);
606        descriptor
607            .buffer
608            .read_at(descriptor_offset, &mut target[copied..copied + count])?;
609        copied += count;
610        if copied == target.len() {
611            return Ok(());
612        }
613    }
614    Err(ByteAccessError::OutOfBounds)
615}
616
617fn copy_to_descriptors(
618    data: &ChainData,
619    writable: bool,
620    offset: u64,
621    source: &[u8],
622) -> Result<(), ByteAccessError> {
623    if source.is_empty() {
624        return Ok(());
625    }
626    let mut copied = 0;
627    let spans = data.analysis.spans(writable);
628    let first = first_touched_span(spans, offset);
629    for (index, span) in spans.iter().enumerate().skip(first) {
630        let descriptor = &data.descriptors[usize::from(span.descriptor)];
631        let span_start = index.checked_sub(1).map_or(0, |prior| spans[prior].end);
632        let logical_offset = offset + copied as u64;
633        let descriptor_offset = logical_offset
634            .checked_sub(span_start)
635            .ok_or(ByteAccessError::OutOfBounds)?;
636        let span_remaining = span
637            .end
638            .checked_sub(logical_offset)
639            .ok_or(ByteAccessError::OutOfBounds)?;
640        let available = usize::try_from(span_remaining).unwrap_or(usize::MAX);
641        let count = min(available, source.len() - copied);
642        descriptor
643            .buffer
644            .write_at(descriptor_offset, &source[copied..copied + count])?;
645        copied += count;
646        if copied == source.len() {
647            return Ok(());
648        }
649    }
650    Err(ByteAccessError::OutOfBounds)
651}
652
653fn zeroed_u16_box(len: usize) -> Result<Box<[u16]>, ChainBuildError> {
654    let mut values = Vec::new();
655    values
656        .try_reserve_exact(len)
657        .map_err(|_| ChainBuildError::AllocationFailed)?;
658    values.resize(len, 0);
659    Ok(values.into_boxed_slice())
660}
661
662fn checked_logical_range(offset: u64, bytes: usize, len: u64) -> Result<(), ByteAccessError> {
663    let bytes = u64::try_from(bytes).map_err(|_| ByteAccessError::OutOfBounds)?;
664    let end = offset
665        .checked_add(bytes)
666        .ok_or(ByteAccessError::OutOfBounds)?;
667    if end > len {
668        return Err(ByteAccessError::OutOfBounds);
669    }
670    Ok(())
671}
672
673fn checked_range(
674    offset: u64,
675    bytes: usize,
676    len: usize,
677) -> Result<core::ops::Range<usize>, ByteAccessError> {
678    let start = usize::try_from(offset).map_err(|_| ByteAccessError::OutOfBounds)?;
679    let end = start
680        .checked_add(bytes)
681        .filter(|end| *end <= len)
682        .ok_or(ByteAccessError::OutOfBounds)?;
683    Ok(start..end)
684}
685
686#[cfg(test)]
687mod tests {
688    use super::{DescriptorSpan, first_touched_span};
689
690    #[test]
691    fn logical_span_search_skips_every_untouched_descriptor_prefix() {
692        let spans = [
693            DescriptorSpan {
694                descriptor: 4,
695                end: 8,
696            },
697            DescriptorSpan {
698                descriptor: 2,
699                end: 24,
700            },
701            DescriptorSpan {
702                descriptor: 7,
703                end: 32,
704            },
705        ];
706
707        assert_eq!(first_touched_span(&spans, 0), 0);
708        assert_eq!(first_touched_span(&spans, 7), 0);
709        assert_eq!(first_touched_span(&spans, 8), 1);
710        assert_eq!(first_touched_span(&spans, 23), 1);
711        assert_eq!(first_touched_span(&spans, 24), 2);
712        assert_eq!(first_touched_span(&spans, 32), 3);
713    }
714}
virtio_accel_split_queue/chain.rs

virtio_accel_split_queue/
chain.rs
