net_wire/qpack/table/
dynamic.rs

1//! Caller-owned RFC 9204 dynamic-table storage.
2
3use core::fmt;
4
5use super::QpackHeaderFieldRef;
6
7/// A caller-owned slot for a QPACK dynamic table entry.
8///
9/// Slots outside the table's current length are inactive. Their contents are not
10/// cleared when entries are evicted.
11#[derive(Clone, Copy, Debug, Eq, PartialEq)]
12pub struct QpackDynamicTableEntry {
13    offset: usize,
14    name_len: usize,
15    value_len: usize,
16}
17
18impl QpackDynamicTableEntry {
19    /// An inactive entry slot suitable for initializing caller-owned metadata.
20    pub const EMPTY: Self = Self {
21        offset: 0,
22        name_len: 0,
23        value_len: 0,
24    };
25}
26
27/// A QPACK dynamic-table capacity, insertion, eviction, or index-resolution failure.
28#[derive(Clone, Copy, Debug, Eq, PartialEq)]
29pub enum QpackDynamicTableError {
30    /// The requested capacity exceeds the supplied storage's physical capacity.
31    CapacityExceedsStorage {
32        /// The requested RFC dynamic-table capacity.
33        requested: usize,
34        /// The greatest RFC dynamic-table capacity the supplied stores can support.
35        capacity: usize,
36    },
37    /// The RFC entry-size calculation overflowed `usize`.
38    EntrySizeOverflow,
39    /// The entry cannot fit within the current dynamic-table capacity.
40    EntryLargerThanCapacity {
41        /// The calculated RFC entry size.
42        entry_size: usize,
43        /// The current RFC dynamic-table capacity.
44        capacity: usize,
45    },
46    /// A successful insertion would overflow the absolute insert count.
47    InsertCountOverflow,
48    /// An eviction required by an operation was rejected by the caller's policy.
49    EvictionBlocked {
50        /// The zero-based absolute index of the first entry whose eviction was rejected.
51        absolute_index: u64,
52    },
53    /// An encoder-relative index exceeded the current insert count.
54    EncoderRelativeIndexUnderflow {
55        /// The current insert count.
56        insert_count: u64,
57        /// The requested encoder-relative index.
58        index: u64,
59    },
60    /// A field-relative index exceeded its base.
61    FieldRelativeIndexUnderflow {
62        /// The field section's base.
63        base: u64,
64        /// The requested field-relative index.
65        index: u64,
66    },
67    /// A post-base index overflowed its base.
68    PostBaseIndexOverflow {
69        /// The field section's base.
70        base: u64,
71        /// The requested post-base index.
72        index: u64,
73    },
74    /// An absolute index has not yet been inserted.
75    FutureAbsoluteIndex {
76        /// The requested zero-based absolute index.
77        requested: u64,
78        /// The current insert count.
79        insert_count: u64,
80    },
81    /// An absolute index was evicted from the active table.
82    EvictedAbsoluteIndex {
83        /// The requested zero-based absolute index.
84        requested: u64,
85        /// The oldest zero-based absolute index still available.
86        oldest_available: u64,
87    },
88    /// A field-line reference is at or after its Required Insert Count.
89    ReferenceAtOrAfterRequiredInsertCount {
90        /// The requested zero-based absolute index.
91        requested: u64,
92        /// The field section's Required Insert Count.
93        required_insert_count: u64,
94    },
95}
96
97impl fmt::Display for QpackDynamicTableError {
98    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
99        match self {
100            Self::CapacityExceedsStorage {
101                requested,
102                capacity,
103            } => {
104                write!(
105                    formatter,
106                    "requested capacity {requested} exceeds storage capacity {capacity}"
107                )
108            }
109            Self::EntrySizeOverflow => formatter.write_str("QPACK entry size overflowed usize"),
110            Self::EntryLargerThanCapacity {
111                entry_size,
112                capacity,
113            } => write!(
114                formatter,
115                "entry size {entry_size} exceeds capacity {capacity}"
116            ),
117            Self::InsertCountOverflow => formatter.write_str("QPACK insert count overflowed u64"),
118            Self::EvictionBlocked { absolute_index } => {
119                write!(
120                    formatter,
121                    "eviction of absolute index {absolute_index} was blocked"
122                )
123            }
124            Self::EncoderRelativeIndexUnderflow {
125                insert_count,
126                index,
127            } => write!(
128                formatter,
129                "encoder-relative index {index} exceeds insert count {insert_count}"
130            ),
131            Self::FieldRelativeIndexUnderflow { base, index } => {
132                write!(
133                    formatter,
134                    "field-relative index {index} exceeds base {base}"
135                )
136            }
137            Self::PostBaseIndexOverflow { base, index } => {
138                write!(formatter, "post-base index {index} overflows base {base}")
139            }
140            Self::FutureAbsoluteIndex {
141                requested,
142                insert_count,
143            } => write!(
144                formatter,
145                "absolute index {requested} is at or after insert count {insert_count}"
146            ),
147            Self::EvictedAbsoluteIndex {
148                requested,
149                oldest_available,
150            } => write!(
151                formatter,
152                "absolute index {requested} was evicted; oldest available is {oldest_available}"
153            ),
154            Self::ReferenceAtOrAfterRequiredInsertCount {
155                requested,
156                required_insert_count,
157            } => write!(
158                formatter,
159                "absolute index {requested} is at or after required insert count {required_insert_count}"
160            ),
161        }
162    }
163}
164
165impl core::error::Error for QpackDynamicTableError {}
166
167/// Caller-owned, allocation-free RFC 9204 dynamic-table storage.
168///
169/// Active entries and their bytes are packed newest first. Absolute indexes begin
170/// at zero and are never reset by eviction or capacity changes.
171pub struct QpackDynamicTable<'storage, 'entries> {
172    storage: &'storage mut [u8],
173    entries: &'entries mut [QpackDynamicTableEntry],
174    len: usize,
175    size: usize,
176    capacity: usize,
177    storage_capacity: usize,
178    insert_count: u64,
179}
180
181impl<'storage, 'entries> QpackDynamicTable<'storage, 'entries> {
182    /// Creates an empty table backed by caller-supplied byte and metadata storage.
183    pub fn new(
184        storage: &'storage mut [u8],
185        entries: &'entries mut [QpackDynamicTableEntry],
186    ) -> Self {
187        let storage_capacity = Self::calculate_storage_capacity(storage.len(), entries.len());
188        Self {
189            storage,
190            entries,
191            len: 0,
192            size: 0,
193            capacity: 0,
194            storage_capacity,
195            insert_count: 0,
196        }
197    }
198
199    /// Returns the greatest RFC dynamic-table capacity the supplied stores support.
200    pub const fn storage_capacity(&self) -> usize {
201        self.storage_capacity
202    }
203
204    /// Returns the current RFC dynamic-table capacity.
205    pub const fn capacity(&self) -> usize {
206        self.capacity
207    }
208
209    /// Returns the current RFC dynamic-table size.
210    pub const fn size(&self) -> usize {
211        self.size
212    }
213
214    /// Returns the number of active dynamic-table entries.
215    pub const fn len(&self) -> usize {
216        self.len
217    }
218
219    /// Returns whether no dynamic-table entries are active.
220    pub const fn is_empty(&self) -> bool {
221        self.len == 0
222    }
223
224    /// Returns the number of successful insertions since this table was created.
225    pub const fn insert_count(&self) -> u64 {
226        self.insert_count
227    }
228
229    /// Returns the oldest active zero-based absolute index, if any.
230    pub fn oldest_active_absolute(&self) -> Option<u64> {
231        if self.len == 0 {
232            return None;
233        }
234        u64::try_from(self.len)
235            .ok()
236            .and_then(|len| self.insert_count.checked_sub(len))
237    }
238
239    /// Calculates an RFC 9204 entry size from opaque name and value bytes.
240    pub fn entry_size(name: &[u8], value: &[u8]) -> Result<usize, QpackDynamicTableError> {
241        name.len()
242            .checked_add(value.len())
243            .and_then(|length| length.checked_add(32))
244            .ok_or(QpackDynamicTableError::EntrySizeOverflow)
245    }
246
247    /// Updates capacity, evicting the oldest entries allowed by `evictable` as needed.
248    pub fn set_capacity<F>(
249        &mut self,
250        capacity: usize,
251        mut evictable: F,
252    ) -> Result<(), QpackDynamicTableError>
253    where
254        F: FnMut(u64) -> bool,
255    {
256        if capacity > self.storage_capacity {
257            return Err(QpackDynamicTableError::CapacityExceedsStorage {
258                requested: capacity,
259                capacity: self.storage_capacity,
260            });
261        }
262
263        let (retained_len, retained_size) = self.retained_for_capacity(capacity);
264        self.confirm_evictions(retained_len, &mut evictable)?;
265        self.len = retained_len;
266        self.size = retained_size;
267        self.capacity = capacity;
268        Ok(())
269    }
270
271    /// Copies a field into the table as the newest entry and returns its absolute index.
272    pub fn insert<F>(
273        &mut self,
274        name: &[u8],
275        value: &[u8],
276        mut evictable: F,
277    ) -> Result<u64, QpackDynamicTableError>
278    where
279        F: FnMut(u64) -> bool,
280    {
281        let entry_size = Self::entry_size(name, value)?;
282        if entry_size > self.capacity {
283            return Err(QpackDynamicTableError::EntryLargerThanCapacity {
284                entry_size,
285                capacity: self.capacity,
286            });
287        }
288        let target_size = self.capacity - entry_size;
289        let (retained_len, retained_size) = self.retained_for_capacity(target_size);
290        self.confirm_evictions(retained_len, &mut evictable)?;
291        let next_insert_count = self
292            .insert_count
293            .checked_add(1)
294            .ok_or(QpackDynamicTableError::InsertCountOverflow)?;
295
296        let byte_len = name.len() + value.len();
297        let retained_bytes = self.packed_bytes(retained_len);
298        self.storage.copy_within(0..retained_bytes, byte_len);
299        if retained_len > 0 {
300            self.entries.copy_within(0..retained_len, 1);
301            for entry in &mut self.entries[1..=retained_len] {
302                entry.offset += byte_len;
303            }
304        }
305        self.storage[..name.len()].copy_from_slice(name);
306        self.storage[name.len()..byte_len].copy_from_slice(value);
307        self.entries[0] = QpackDynamicTableEntry {
308            offset: 0,
309            name_len: name.len(),
310            value_len: value.len(),
311        };
312        self.len = retained_len + 1;
313        self.size = retained_size + entry_size;
314        let absolute = self.insert_count;
315        self.insert_count = next_insert_count;
316        Ok(absolute)
317    }
318
319    /// Resolves a zero-based absolute index to an active borrowed header field.
320    pub fn get_absolute(
321        &self,
322        absolute: u64,
323    ) -> Result<QpackHeaderFieldRef<'_>, QpackDynamicTableError> {
324        if absolute >= self.insert_count {
325            return Err(QpackDynamicTableError::FutureAbsoluteIndex {
326                requested: absolute,
327                insert_count: self.insert_count,
328            });
329        }
330        let oldest_available = match self.oldest_active_absolute() {
331            Some(oldest) => oldest,
332            None => self.insert_count,
333        };
334        if absolute < oldest_available {
335            return Err(QpackDynamicTableError::EvictedAbsoluteIndex {
336                requested: absolute,
337                oldest_available,
338            });
339        }
340        let slot = (self.insert_count - absolute - 1) as usize;
341        let entry = self.entries[slot];
342        let name_end = entry.offset + entry.name_len;
343        let value_end = name_end + entry.value_len;
344        Ok(QpackHeaderFieldRef::new(
345            &self.storage[entry.offset..name_end],
346            &self.storage[name_end..value_end],
347        ))
348    }
349
350    /// Resolves an encoder-stream relative index to an active borrowed header field.
351    pub fn get_encoder_relative(
352        &self,
353        relative: u64,
354    ) -> Result<QpackHeaderFieldRef<'_>, QpackDynamicTableError> {
355        let absolute = self
356            .insert_count
357            .checked_sub(relative)
358            .and_then(|count| count.checked_sub(1))
359            .ok_or(QpackDynamicTableError::EncoderRelativeIndexUnderflow {
360                insert_count: self.insert_count,
361                index: relative,
362            })?;
363        self.get_absolute(absolute)
364    }
365
366    /// Resolves a field-section relative index to an active borrowed header field.
367    pub fn get_field_relative(
368        &self,
369        required_insert_count: u64,
370        base: u64,
371        relative: u64,
372    ) -> Result<QpackHeaderFieldRef<'_>, QpackDynamicTableError> {
373        let absolute = base
374            .checked_sub(relative)
375            .and_then(|base| base.checked_sub(1))
376            .ok_or(QpackDynamicTableError::FieldRelativeIndexUnderflow {
377                base,
378                index: relative,
379            })?;
380        self.get_before_required_insert_count(absolute, required_insert_count)
381    }
382
383    /// Resolves a post-base index to an active borrowed header field.
384    pub fn get_post_base(
385        &self,
386        required_insert_count: u64,
387        base: u64,
388        post_base: u64,
389    ) -> Result<QpackHeaderFieldRef<'_>, QpackDynamicTableError> {
390        let absolute =
391            base.checked_add(post_base)
392                .ok_or(QpackDynamicTableError::PostBaseIndexOverflow {
393                    base,
394                    index: post_base,
395                })?;
396        self.get_before_required_insert_count(absolute, required_insert_count)
397    }
398
399    fn get_before_required_insert_count(
400        &self,
401        absolute: u64,
402        required_insert_count: u64,
403    ) -> Result<QpackHeaderFieldRef<'_>, QpackDynamicTableError> {
404        if absolute >= required_insert_count {
405            return Err(
406                QpackDynamicTableError::ReferenceAtOrAfterRequiredInsertCount {
407                    requested: absolute,
408                    required_insert_count,
409                },
410            );
411        }
412        self.get_absolute(absolute)
413    }
414
415    fn retained_for_capacity(&self, capacity: usize) -> (usize, usize) {
416        let mut len = self.len;
417        let mut size = self.size;
418        while len > 0 && size > capacity {
419            len -= 1;
420            size -= Self::entry_size_from_slot(self.entries[len]);
421        }
422        (len, size)
423    }
424
425    fn confirm_evictions<F>(
426        &self,
427        retained_len: usize,
428        evictable: &mut F,
429    ) -> Result<(), QpackDynamicTableError>
430    where
431        F: FnMut(u64) -> bool,
432    {
433        for slot in (retained_len..self.len).rev() {
434            let absolute_index = self.insert_count - slot as u64 - 1;
435            if !evictable(absolute_index) {
436                return Err(QpackDynamicTableError::EvictionBlocked { absolute_index });
437            }
438        }
439        Ok(())
440    }
441
442    fn packed_bytes(&self, len: usize) -> usize {
443        if len == 0 {
444            0
445        } else {
446            let entry = self.entries[len - 1];
447            entry.offset + entry.name_len + entry.value_len
448        }
449    }
450
451    const fn calculate_storage_capacity(storage_len: usize, entry_capacity: usize) -> usize {
452        let bytes = storage_len.saturating_add(32);
453        let entries = entry_capacity.saturating_mul(32).saturating_add(31);
454        if bytes < entries { bytes } else { entries }
455    }
456
457    const fn entry_size_from_slot(entry: QpackDynamicTableEntry) -> usize {
458        entry.name_len + entry.value_len + 32
459    }
460}
net_wire/qpack/table/dynamic.rs

net_wire/qpack/table/
dynamic.rs
