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; 16]>,
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        Ok(Self {
119            base_addr: layout.base_addr,
120            slot_size: layout.slot_size,
121            count: layout.slot_count,
122            free,
123            allocated: FixedBitSet::with_capacity(layout.slot_count),
124        })
125    }
126
127    fn end(&self) -> u64 {
128        self.base_addr + self.count as u64 * u64::from(self.slot_size)
129    }
130
131    fn contains(&self, addr: u64) -> bool {
132        (self.base_addr..self.end()).contains(&addr)
133    }
134
135    /// Validate that `addr` names a slot start within the region.
136    fn slot_of(&self, addr: u64) -> Result<usize, AllocError> {
137        if !self.contains(addr) {
138            return Err(AllocError::InvalidFree(addr, 0));
139        }
140
141        let off = addr - self.base_addr;
142        if !off.is_multiple_of(u64::from(self.slot_size)) {
143            return Err(AllocError::InvalidFree(addr, 0));
144        }
145
146        Ok((off / u64::from(self.slot_size)) as usize)
147    }
148
149    /// Validate that `addr` is a live (currently allocated) slot start.
150    fn live_slot_of(&self, addr: u64) -> Result<usize, AllocError> {
151        let slot = self.slot_of(addr)?;
152        if !self.allocated.contains(slot) {
153            return Err(AllocError::InvalidFree(addr, 0));
154        }
155        Ok(slot)
156    }
157
158    fn alloc(&mut self, len: usize) -> Result<Allocation, AllocError> {
159        if len == 0 {
160            return Err(AllocError::InvalidArg);
161        }
162        if len > self.slot_size as usize {
163            return Err(AllocError::OutOfMemory);
164        }
165
166        let addr = self.free.pop().ok_or(AllocError::NoSpace)?;
167        // Safety of the index: `addr` came from `free`, which only ever holds
168        // valid slot starts.
169        self.allocated
170            .insert(((addr - self.base_addr) / u64::from(self.slot_size)) as usize);
171
172        Ok(Allocation {
173            addr,
174            len: self.slot_size,
175        })
176    }
177
178    fn dealloc_addr(&mut self, addr: u64) -> Result<(), AllocError> {
179        let slot = self.live_slot_of(addr)?;
180        self.allocated.set(slot, false);
181        self.free.push(addr);
182        Ok(())
183    }
184
185    /// Keep one queue-owned slot unavailable for a pool swap.
186    fn reserve_addr(&mut self, addr: u64) -> Result<(), AllocError> {
187        let slot = self.slot_of(addr)?;
188
189        if self.allocated.contains(slot) {
190            return Err(AllocError::InvalidArg);
191        }
192
193        self.allocated.insert(slot);
194        Ok(())
195    }
196
197    /// Populate the free list from the allocation bitmap.
198    fn rebuild_free(&mut self) {
199        self.free.clear();
200
201        for slot in self.allocated.zeroes() {
202            self.free
203                .push(self.base_addr + slot as u64 * u64::from(self.slot_size));
204        }
205    }
206
207    fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
208        self.live_slot_of(addr)?;
209        Ok(self.slot_size as usize)
210    }
211
212    fn slot_addr(&self, index: usize) -> Option<u64> {
213        (index < self.count).then(|| self.base_addr + (index * self.slot_size as usize) as u64)
214    }
215
216    fn num_free(&self) -> usize {
217        self.free.len()
218    }
219
220    fn append_live_addrs(&self, addrs: &mut Vec<u64>) {
221        addrs.extend(
222            self.allocated
223                .ones()
224                .map(|slot| self.base_addr + (slot * self.slot_size as usize) as u64),
225        );
226    }
227
228    fn layout(&self) -> SlotLayout {
229        SlotLayout {
230            base_addr: self.base_addr,
231            slot_size: self.slot_size,
232            slot_count: self.count,
233        }
234    }
235}
236
237struct Inner {
238    lower: Option<Tier>,
239    upper: Tier,
240}
241
242impl Inner {
243    fn new(lower: Option<SlotLayout>, upper: SlotLayout) -> Result<Self, AllocError> {
244        let Some(lower) = lower else {
245            return Ok(Self {
246                lower: None,
247                upper: Tier::from_layout(upper)?,
248            });
249        };
250
251        if lower.slot_size > upper.slot_size || lower.end_addr() > upper.base_addr {
252            return Err(AllocError::InvalidArg);
253        }
254
255        if lower.slot_size == upper.slot_size {
256            if lower.end_addr() != upper.base_addr {
257                return Err(AllocError::InvalidArg);
258            }
259
260            let count = lower
261                .slot_count
262                .checked_add(upper.slot_count)
263                .ok_or(AllocError::Overflow)?;
264
265            let layout = SlotLayout::new(lower.base_addr, lower.slot_size(), count)?;
266
267            return Ok(Self {
268                lower: None,
269                upper: Tier::from_layout(layout)?,
270            });
271        }
272
273        Ok(Self {
274            lower: Some(Tier::from_layout(lower)?),
275            upper: Tier::from_layout(upper)?,
276        })
277    }
278
279    fn max_alloc_len(&self) -> usize {
280        self.upper.slot_size as usize
281    }
282
283    fn alloc(&mut self, len: usize) -> Result<Allocation, AllocError> {
284        if let Some(lower) = &mut self.lower
285            && len <= lower.slot_size as usize
286        {
287            match lower.alloc(len) {
288                Ok(alloc) => return Ok(alloc),
289                Err(AllocError::NoSpace) => {}
290                Err(err) => return Err(err),
291            }
292        }
293
294        self.upper.alloc(len)
295    }
296
297    fn dealloc_addr(&mut self, addr: u64) -> Result<(), AllocError> {
298        if let Some(lower) = &mut self.lower
299            && lower.contains(addr)
300        {
301            return lower.dealloc_addr(addr);
302        }
303        self.upper.dealloc_addr(addr)
304    }
305
306    fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
307        if let Some(lower) = &self.lower
308            && lower.contains(addr)
309        {
310            return lower.allocation_len(addr);
311        }
312        self.upper.allocation_len(addr)
313    }
314
315    fn slot_addr(&self, index: usize) -> Option<u64> {
316        if let Some(lower) = &self.lower {
317            if index < lower.count {
318                return lower.slot_addr(index);
319            }
320            return self.upper.slot_addr(index - lower.count);
321        }
322        self.upper.slot_addr(index)
323    }
324
325    fn live_addrs(&self) -> Vec<u64> {
326        let mut addrs = Vec::with_capacity(self.num_live());
327        if let Some(lower) = &self.lower {
328            lower.append_live_addrs(&mut addrs);
329        }
330        self.upper.append_live_addrs(&mut addrs);
331        addrs
332    }
333
334    fn base_addr(&self) -> u64 {
335        self.lower
336            .as_ref()
337            .map_or(self.upper.base_addr, |lower| lower.base_addr)
338    }
339
340    fn count(&self) -> usize {
341        self.lower.as_ref().map_or(0, |lower| lower.count) + self.upper.count
342    }
343
344    fn num_free(&self) -> usize {
345        self.lower.as_ref().map_or(0, Tier::num_free) + self.upper.num_free()
346    }
347
348    fn num_live(&self) -> usize {
349        self.count() - self.num_free()
350    }
351
352    fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
353        (self.lower.as_ref().map(Tier::layout), self.upper.layout())
354    }
355
356    /// Byte span of both tiers, including any gap.
357    fn byte_len(&self) -> usize {
358        (self.upper.layout().end_addr() - self.base_addr()) as usize
359    }
360}
361
362/// A buffer pool with one or two fixed-slot tiers.
363///
364/// Allocation and deallocation are O(1) per slot. Eligible allocations first
365/// try the optional lower tier and fall back to the required upper tier when
366/// the lower tier is full.
367#[derive(Clone)]
368pub struct SlotPool {
369    inner: Rc<RefCell<Inner>>,
370}
371
372impl SlotPool {
373    /// Whether both handles share allocation state.
374    pub(crate) fn ptr_eq(&self, other: &Self) -> bool {
375        Rc::ptr_eq(&self.inner, &other.inner)
376    }
377
378    /// Create allocation state for a pool swap with the supplied live slots reserved.
379    ///
380    /// Invalid or duplicate reservations leave this pool unchanged.
381    pub(crate) fn swap(&self, reserved: impl Iterator<Item = u64>) -> Result<Self, AllocError> {
382        let current = self.inner.borrow();
383        let (lower, upper) = current.layouts();
384        let mut inner = Inner::new(lower, upper)?;
385
386        for addr in reserved {
387            // this address is a valid allocation in the current pool
388            current.allocation_len(addr)?;
389            if let Some(lower) = &mut inner.lower
390                && lower.contains(addr)
391            {
392                lower.reserve_addr(addr)?;
393            } else {
394                inner.upper.reserve_addr(addr)?;
395            }
396        }
397
398        Ok(Self::from_inner(inner))
399    }
400
401    /// Create a single-tier recycling pool from exact slot placement.
402    pub fn new(layout: SlotLayout) -> Result<Self, AllocError> {
403        Self::from_layouts(None, layout)
404    }
405
406    /// Create a two-tier recycling pool from exact lower and upper layouts.
407    ///
408    /// The lower layout must precede the upper layout without overlap, and its
409    /// slot size must not exceed the upper slot size. Adjacent equal-sized
410    /// layouts form one tier.
411    pub fn new_tiered(lower: SlotLayout, upper: SlotLayout) -> Result<Self, AllocError> {
412        Self::from_layouts(Some(lower), upper)
413    }
414
415    fn from_layouts(lower: Option<SlotLayout>, upper: SlotLayout) -> Result<Self, AllocError> {
416        Ok(Self::from_inner(Inner::new(lower, upper)?))
417    }
418
419    fn from_inner(mut inner: Inner) -> Self {
420        inner.upper.rebuild_free();
421        if let Some(lower) = &mut inner.lower {
422            lower.rebuild_free();
423        }
424
425        Self {
426            inner: Rc::new(RefCell::new(inner)),
427        }
428    }
429
430    /// Return every live slot address in deterministic tier and index order.
431    pub fn live_addrs(&self) -> Vec<u64> {
432        self.inner.borrow().live_addrs()
433    }
434
435    /// Return the lower and upper tier layouts.
436    pub fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
437        self.inner.borrow().layouts()
438    }
439
440    /// Compute the address of slot `index`, with lower-tier slots first.
441    ///
442    /// Returns `None` if `index >= count`.
443    pub fn slot_addr(&self, index: usize) -> Option<u64> {
444        self.inner.borrow().slot_addr(index)
445    }
446
447    /// Total number of free slots across all tiers.
448    pub fn num_free(&self) -> usize {
449        self.inner.borrow().num_free()
450    }
451
452    /// Total number of currently allocated slots across all tiers.
453    pub fn num_live(&self) -> usize {
454        self.inner.borrow().num_live()
455    }
456
457    /// Total number of free slots in the lower tier.
458    pub fn num_free_lower(&self) -> usize {
459        self.inner.borrow().lower.as_ref().map_or(0, Tier::num_free)
460    }
461
462    /// Total number of free slots in the upper tier.
463    pub fn num_free_upper(&self) -> usize {
464        self.inner.borrow().upper.num_free()
465    }
466
467    /// Free a previously allocated slot by address.
468    pub fn dealloc(&self, addr: u64) -> Result<(), AllocError> {
469        self.inner.borrow_mut().dealloc_addr(addr)
470    }
471
472    /// Capacity of a live allocation by its start address.
473    pub fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
474        self.inner.borrow().allocation_len(addr)
475    }
476
477    /// Base address of the first managed tier.
478    pub fn base_addr(&self) -> u64 {
479        self.inner.borrow().base_addr()
480    }
481
482    /// Maximum slot size in bytes.
483    pub fn slot_size(&self) -> usize {
484        self.inner.borrow().max_alloc_len()
485    }
486
487    /// Slot size in bytes for the lower tier, if present.
488    pub fn lower_slot_size(&self) -> Option<usize> {
489        self.inner
490            .borrow()
491            .lower
492            .as_ref()
493            .map(|lower| lower.slot_size as usize)
494    }
495
496    /// Maximum slot size in bytes for the upper tier.
497    pub fn upper_slot_size(&self) -> usize {
498        self.inner.borrow().upper.slot_size as usize
499    }
500
501    /// Total number of slots across all tiers.
502    pub fn count(&self) -> usize {
503        self.inner.borrow().count()
504    }
505
506    /// Allocate one slot holding at least `len` bytes.
507    pub fn alloc(&self, len: usize) -> Result<Allocation, AllocError> {
508        self.inner.borrow_mut().alloc(len)
509    }
510
511    /// Byte span from the first slot to the last, including any gap between tiers.
512    pub fn byte_len(&self) -> usize {
513        self.inner.borrow().byte_len()
514    }
515
516    #[cfg(test)]
517    pub(crate) fn strong_count(&self) -> usize {
518        Rc::strong_count(&self.inner)
519    }
520}