Skip to main content

hyperlight_common/virtq/pool/
slot.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 The Hyperlight Authors.
3
4//! Fixed-slot pool with optional lower and required upper tiers.
5//!
6//! [`SlotPool`] manages one or two non-overlapping [`SlotLayout`]s. Each tier
7//! contains independent, equal-sized slots tracked by a free list and an
8//! allocation bitmap. Eligible requests try the lower tier first and fall back
9//! to the upper tier only when the lower tier has no free slot.
10//!
11//! Each allocation occupies one slot. [`SlotPool::live_addrs`] reports ownership
12//! in deterministic index order.
13
14use alloc::rc::Rc;
15use alloc::vec::Vec;
16use core::cell::RefCell;
17
18use fixedbitset::FixedBitSet;
19use smallvec::SmallVec;
20
21use super::{AllocError, Allocation};
22
23/// Validated memory layout for one [`SlotPool`] tier.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub struct SlotLayout {
26    /// Start of the first slot.
27    base_addr: u64,
28    /// Capacity of each slot. Must fit in [`Allocation::len`].
29    slot_size: u32,
30    /// Number of slots.
31    slot_count: usize,
32}
33
34impl SlotLayout {
35    /// Validate exact fixed-slot placement.
36    ///
37    /// Rejects empty layouts, slots larger than [`u32::MAX`], and unrepresentable
38    /// backing or free-list byte ranges.
39    pub fn new(base_addr: u64, slot_size: usize, slot_count: usize) -> Result<Self, AllocError> {
40        let slot_size = u32::try_from(slot_size).map_err(|_| AllocError::InvalidArg)?;
41
42        if slot_size == 0 {
43            return Err(AllocError::InvalidArg);
44        }
45
46        if slot_count == 0 {
47            return Err(AllocError::EmptyRegion);
48        }
49
50        let byte_len = (slot_size as usize)
51            .checked_mul(slot_count)
52            .ok_or(AllocError::Overflow)?;
53
54        base_addr
55            .checked_add(u64::try_from(byte_len).map_err(|_| AllocError::Overflow)?)
56            .ok_or(AllocError::Overflow)?;
57
58        core::alloc::Layout::array::<u64>(slot_count).map_err(|_| AllocError::Overflow)?;
59
60        Ok(Self {
61            base_addr,
62            slot_size,
63            slot_count,
64        })
65    }
66
67    /// Start address of the first slot.
68    pub const fn base_addr(self) -> u64 {
69        self.base_addr
70    }
71
72    /// Capacity of each slot in bytes.
73    pub const fn slot_size(self) -> usize {
74        self.slot_size as usize
75    }
76
77    /// Number of equal-sized slots.
78    pub const fn slot_count(self) -> usize {
79        self.slot_count
80    }
81
82    /// Total bytes occupied by the slots.
83    pub const fn byte_len(self) -> usize {
84        self.slot_size as usize * self.slot_count
85    }
86
87    /// Exclusive end address.
88    pub const fn end_addr(self) -> u64 {
89        self.base_addr + self.byte_len() as u64
90    }
91}
92
93/// Single-tier fixed-slot free list.
94///
95/// Tracks a fixed set of equal-sized buffer slots. Allocation pops a free slot
96/// and deallocation returns it, both O(1). A [`FixedBitSet`] records which slots
97/// are currently allocated, so double frees and frees of unknown addresses are
98/// rejected without scanning the free list.
99struct Tier {
100    /// Start of this tier's backing memory.
101    base_addr: u64,
102    /// Capacity of this slot.
103    slot_size: u32,
104    /// Number of slots in this tier.
105    count: usize,
106    /// Free slot addresses, popped/pushed LIFO.
107    free: SmallVec<[u64; 64]>,
108    /// One bit per slot index; set means the slot is currently handed out.
109    allocated: FixedBitSet,
110}
111
112impl Tier {
113    fn from_layout(layout: SlotLayout) -> Result<Self, AllocError> {
114        let mut free = SmallVec::new();
115        free.try_reserve_exact(layout.slot_count)
116            .map_err(|_| AllocError::Bookkeeping)?;
117
118        for i in 0..layout.slot_count {
119            free.push(layout.base_addr + (i * layout.slot_size as usize) as u64);
120        }
121
122        Ok(Self {
123            base_addr: layout.base_addr,
124            slot_size: layout.slot_size,
125            count: layout.slot_count,
126            free,
127            allocated: FixedBitSet::with_capacity(layout.slot_count),
128        })
129    }
130
131    fn end(&self) -> u64 {
132        self.base_addr + self.count as u64 * u64::from(self.slot_size)
133    }
134
135    fn contains(&self, addr: u64) -> bool {
136        (self.base_addr..self.end()).contains(&addr)
137    }
138
139    /// Validate that `addr` names a slot start within the region.
140    fn slot_of(&self, addr: u64) -> Result<usize, AllocError> {
141        if !self.contains(addr) {
142            return Err(AllocError::InvalidFree(addr, 0));
143        }
144
145        let off = addr - self.base_addr;
146        if !off.is_multiple_of(u64::from(self.slot_size)) {
147            return Err(AllocError::InvalidFree(addr, 0));
148        }
149
150        Ok((off / u64::from(self.slot_size)) as usize)
151    }
152
153    /// Validate that `addr` is a live (currently allocated) slot start.
154    fn live_slot_of(&self, addr: u64) -> Result<usize, AllocError> {
155        let slot = self.slot_of(addr)?;
156        if !self.allocated.contains(slot) {
157            return Err(AllocError::InvalidFree(addr, 0));
158        }
159        Ok(slot)
160    }
161
162    fn alloc(&mut self, len: usize) -> Result<Allocation, AllocError> {
163        if len == 0 {
164            return Err(AllocError::InvalidArg);
165        }
166        if len > self.slot_size as usize {
167            return Err(AllocError::OutOfMemory);
168        }
169
170        let addr = self.free.pop().ok_or(AllocError::NoSpace)?;
171        // Safety of the index: `addr` came from `free`, which only ever holds
172        // valid slot starts.
173        self.allocated
174            .insert(((addr - self.base_addr) / u64::from(self.slot_size)) as usize);
175
176        Ok(Allocation {
177            addr,
178            len: self.slot_size,
179        })
180    }
181
182    fn dealloc_addr(&mut self, addr: u64) -> Result<(), AllocError> {
183        let slot = self.live_slot_of(addr)?;
184        self.allocated.set(slot, false);
185        self.free.push(addr);
186        Ok(())
187    }
188
189    /// Keep one queue-owned slot unavailable during generation recovery.
190    fn reserve_addr(&mut self, addr: u64) -> Result<(), AllocError> {
191        let slot = self.slot_of(addr)?;
192
193        if self.allocated.contains(slot) {
194            return Err(AllocError::InvalidArg);
195        }
196
197        self.allocated.insert(slot);
198        Ok(())
199    }
200
201    /// Rebuild the free list from the recovered ownership bitmap.
202    fn rebuild_free(&mut self) {
203        self.free.clear();
204
205        for slot in self.allocated.zeroes() {
206            self.free
207                .push(self.base_addr + slot as u64 * u64::from(self.slot_size));
208        }
209    }
210
211    fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
212        self.live_slot_of(addr)?;
213        Ok(self.slot_size as usize)
214    }
215
216    fn slot_addr(&self, index: usize) -> Option<u64> {
217        (index < self.count).then(|| self.base_addr + (index * self.slot_size as usize) as u64)
218    }
219
220    fn num_free(&self) -> usize {
221        self.free.len()
222    }
223
224    fn append_live_addrs(&self, addrs: &mut Vec<u64>) {
225        addrs.extend(
226            self.allocated
227                .ones()
228                .map(|slot| self.base_addr + (slot * self.slot_size as usize) as u64),
229        );
230    }
231
232    fn layout(&self) -> SlotLayout {
233        SlotLayout {
234            base_addr: self.base_addr,
235            slot_size: self.slot_size,
236            slot_count: self.count,
237        }
238    }
239}
240
241struct Inner {
242    lower: Option<Tier>,
243    upper: Tier,
244    generation: u64,
245}
246
247impl Inner {
248    fn new(lower: Option<SlotLayout>, upper: SlotLayout) -> Result<Self, AllocError> {
249        let Some(lower) = lower else {
250            return Ok(Self {
251                lower: None,
252                upper: Tier::from_layout(upper)?,
253                generation: 0,
254            });
255        };
256
257        if lower.slot_size > upper.slot_size || lower.end_addr() > upper.base_addr {
258            return Err(AllocError::InvalidArg);
259        }
260
261        if lower.slot_size == upper.slot_size {
262            if lower.end_addr() != upper.base_addr {
263                return Err(AllocError::InvalidArg);
264            }
265
266            let count = lower
267                .slot_count
268                .checked_add(upper.slot_count)
269                .ok_or(AllocError::Overflow)?;
270
271            let layout = SlotLayout::new(lower.base_addr, lower.slot_size(), count)?;
272
273            return Ok(Self {
274                lower: None,
275                upper: Tier::from_layout(layout)?,
276                generation: 0,
277            });
278        }
279
280        Ok(Self {
281            lower: Some(Tier::from_layout(lower)?),
282            upper: Tier::from_layout(upper)?,
283            generation: 0,
284        })
285    }
286
287    fn max_alloc_len(&self) -> usize {
288        self.upper.slot_size as usize
289    }
290
291    fn alloc(&mut self, len: usize) -> Result<Allocation, AllocError> {
292        if let Some(lower) = &mut self.lower
293            && len <= lower.slot_size as usize
294        {
295            match lower.alloc(len) {
296                Ok(alloc) => return Ok(alloc),
297                Err(AllocError::NoSpace) => {}
298                Err(err) => return Err(err),
299            }
300        }
301
302        self.upper.alloc(len)
303    }
304
305    fn dealloc_addr(&mut self, addr: u64) -> Result<(), AllocError> {
306        if let Some(lower) = &mut self.lower
307            && lower.contains(addr)
308        {
309            return lower.dealloc_addr(addr);
310        }
311        self.upper.dealloc_addr(addr)
312    }
313
314    /// Start a new generation and rebuild allocation state from `reserved`.
315    fn retire_generation(
316        &mut self,
317        reserved: impl Iterator<Item = u64> + Clone,
318    ) -> Result<(), AllocError> {
319        let generation = self.generation.checked_add(1).ok_or(AllocError::Overflow)?;
320
321        #[cfg(debug_assertions)]
322        for addr in reserved.clone() {
323            debug_assert!(
324                self.allocation_len(addr).is_ok(),
325                "address {addr:#x} is not a live pool slot"
326            );
327        }
328
329        self.generation = generation;
330        self.upper.allocated.clear();
331
332        if let Some(lower) = &mut self.lower {
333            lower.allocated.clear();
334        }
335
336        for addr in reserved {
337            if let Some(lower) = &mut self.lower
338                && lower.contains(addr)
339            {
340                lower.reserve_addr(addr)?;
341            } else {
342                self.upper.reserve_addr(addr)?;
343            }
344        }
345
346        self.upper.rebuild_free();
347
348        if let Some(lower) = &mut self.lower {
349            lower.rebuild_free();
350        }
351
352        Ok(())
353    }
354
355    fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
356        if let Some(lower) = &self.lower
357            && lower.contains(addr)
358        {
359            return lower.allocation_len(addr);
360        }
361        self.upper.allocation_len(addr)
362    }
363
364    fn slot_addr(&self, index: usize) -> Option<u64> {
365        if let Some(lower) = &self.lower {
366            if index < lower.count {
367                return lower.slot_addr(index);
368            }
369            return self.upper.slot_addr(index - lower.count);
370        }
371        self.upper.slot_addr(index)
372    }
373
374    fn live_addrs(&self) -> Vec<u64> {
375        let mut addrs = Vec::with_capacity(self.num_live());
376        if let Some(lower) = &self.lower {
377            lower.append_live_addrs(&mut addrs);
378        }
379        self.upper.append_live_addrs(&mut addrs);
380        addrs
381    }
382
383    fn base_addr(&self) -> u64 {
384        self.lower
385            .as_ref()
386            .map_or(self.upper.base_addr, |lower| lower.base_addr)
387    }
388
389    fn count(&self) -> usize {
390        self.lower.as_ref().map_or(0, |lower| lower.count) + self.upper.count
391    }
392
393    fn num_free(&self) -> usize {
394        self.lower.as_ref().map_or(0, Tier::num_free) + self.upper.num_free()
395    }
396
397    fn num_live(&self) -> usize {
398        self.count() - self.num_free()
399    }
400
401    fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
402        (self.lower.as_ref().map(Tier::layout), self.upper.layout())
403    }
404
405    /// Byte span of both tiers, including any gap.
406    fn byte_len(&self) -> usize {
407        (self.upper.layout().end_addr() - self.base_addr()) as usize
408    }
409}
410
411/// A buffer pool with one or two fixed-slot tiers.
412///
413/// Allocation and deallocation are O(1) per slot. Eligible allocations first
414/// try the optional lower tier and fall back to the required upper tier when
415/// the lower tier is full.
416#[derive(Clone)]
417pub struct SlotPool {
418    inner: Rc<RefCell<Inner>>,
419}
420
421impl SlotPool {
422    /// Generation owning the current scratch allocations.
423    pub(crate) fn generation(&self) -> u64 {
424        self.inner.borrow().generation
425    }
426
427    /// Retire existing leases and rebuild the pool around the supplied reservations.
428    ///
429    /// # Safety
430    ///
431    /// Retired views must already use backing independent of these scratch slots.
432    /// `reserved` must name every other live allocation exactly once.
433    /// No allocation or peer access may race this call.
434    pub(crate) unsafe fn retire_generation(
435        &self,
436        reserved: impl Iterator<Item = u64> + Clone,
437    ) -> Result<(), AllocError> {
438        self.inner.borrow_mut().retire_generation(reserved)
439    }
440
441    /// Create a single-tier recycling pool from exact slot placement.
442    pub fn new(layout: SlotLayout) -> Result<Self, AllocError> {
443        Self::from_layouts(None, layout)
444    }
445
446    /// Create a two-tier recycling pool from exact lower and upper layouts.
447    ///
448    /// The lower layout must precede the upper layout without overlap, and its
449    /// slot size must not exceed the upper slot size. Adjacent equal-sized
450    /// layouts form one tier.
451    pub fn new_tiered(lower: SlotLayout, upper: SlotLayout) -> Result<Self, AllocError> {
452        Self::from_layouts(Some(lower), upper)
453    }
454
455    fn from_layouts(lower: Option<SlotLayout>, upper: SlotLayout) -> Result<Self, AllocError> {
456        let inner = Inner::new(lower, upper)?;
457        Ok(Self {
458            inner: Rc::new(RefCell::new(inner)),
459        })
460    }
461
462    /// Return every live slot address in deterministic tier and index order.
463    pub fn live_addrs(&self) -> Vec<u64> {
464        self.inner.borrow().live_addrs()
465    }
466
467    /// Return the lower and upper tier layouts.
468    pub fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
469        self.inner.borrow().layouts()
470    }
471
472    /// Compute the address of slot `index`, with lower-tier slots first.
473    ///
474    /// Returns `None` if `index >= count`.
475    pub fn slot_addr(&self, index: usize) -> Option<u64> {
476        self.inner.borrow().slot_addr(index)
477    }
478
479    /// Total number of free slots across all tiers.
480    pub fn num_free(&self) -> usize {
481        self.inner.borrow().num_free()
482    }
483
484    /// Total number of currently allocated slots across all tiers.
485    pub fn num_live(&self) -> usize {
486        self.inner.borrow().num_live()
487    }
488
489    /// Total number of free slots in the lower tier.
490    pub fn num_free_lower(&self) -> usize {
491        self.inner.borrow().lower.as_ref().map_or(0, Tier::num_free)
492    }
493
494    /// Total number of free slots in the upper tier.
495    pub fn num_free_upper(&self) -> usize {
496        self.inner.borrow().upper.num_free()
497    }
498
499    /// Free a previously allocated slot by address.
500    pub fn dealloc(&self, addr: u64) -> Result<(), AllocError> {
501        self.inner.borrow_mut().dealloc_addr(addr)
502    }
503
504    /// Capacity of a live allocation by its start address.
505    pub fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
506        self.inner.borrow().allocation_len(addr)
507    }
508
509    /// Base address of the first managed tier.
510    pub fn base_addr(&self) -> u64 {
511        self.inner.borrow().base_addr()
512    }
513
514    /// Maximum slot size in bytes.
515    pub fn slot_size(&self) -> usize {
516        self.inner.borrow().max_alloc_len()
517    }
518
519    /// Slot size in bytes for the lower tier, if present.
520    pub fn lower_slot_size(&self) -> Option<usize> {
521        self.inner
522            .borrow()
523            .lower
524            .as_ref()
525            .map(|lower| lower.slot_size as usize)
526    }
527
528    /// Maximum slot size in bytes for the upper tier.
529    pub fn upper_slot_size(&self) -> usize {
530        self.inner.borrow().upper.slot_size as usize
531    }
532
533    /// Total number of slots across all tiers.
534    pub fn count(&self) -> usize {
535        self.inner.borrow().count()
536    }
537
538    /// Allocate one slot holding at least `len` bytes.
539    pub fn alloc(&self, len: usize) -> Result<Allocation, AllocError> {
540        self.inner.borrow_mut().alloc(len)
541    }
542
543    /// Byte span from the first slot to the last, including any gap between tiers.
544    pub fn byte_len(&self) -> usize {
545        self.inner.borrow().byte_len()
546    }
547
548    #[cfg(test)]
549    pub(crate) fn strong_count(&self) -> usize {
550        Rc::strong_count(&self.inner)
551    }
552}