hyperlight_common/virtq/pool/
slot.rs1use 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub struct SlotLayout {
26 base_addr: u64,
28 slot_size: u32,
30 slot_count: usize,
32}
33
34impl SlotLayout {
35 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 pub const fn base_addr(self) -> u64 {
69 self.base_addr
70 }
71
72 pub const fn slot_size(self) -> usize {
74 self.slot_size as usize
75 }
76
77 pub const fn slot_count(self) -> usize {
79 self.slot_count
80 }
81
82 pub const fn byte_len(self) -> usize {
84 self.slot_size as usize * self.slot_count
85 }
86
87 pub const fn end_addr(self) -> u64 {
89 self.base_addr + self.byte_len() as u64
90 }
91}
92
93struct Tier {
100 base_addr: u64,
102 slot_size: u32,
104 count: usize,
106 free: SmallVec<[u64; 16]>,
108 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 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 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 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 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 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 fn byte_len(&self) -> usize {
358 (self.upper.layout().end_addr() - self.base_addr()) as usize
359 }
360}
361
362#[derive(Clone)]
368pub struct SlotPool {
369 inner: Rc<RefCell<Inner>>,
370}
371
372impl SlotPool {
373 pub(crate) fn ptr_eq(&self, other: &Self) -> bool {
375 Rc::ptr_eq(&self.inner, &other.inner)
376 }
377
378 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 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 pub fn new(layout: SlotLayout) -> Result<Self, AllocError> {
403 Self::from_layouts(None, layout)
404 }
405
406 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 pub fn live_addrs(&self) -> Vec<u64> {
432 self.inner.borrow().live_addrs()
433 }
434
435 pub fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
437 self.inner.borrow().layouts()
438 }
439
440 pub fn slot_addr(&self, index: usize) -> Option<u64> {
444 self.inner.borrow().slot_addr(index)
445 }
446
447 pub fn num_free(&self) -> usize {
449 self.inner.borrow().num_free()
450 }
451
452 pub fn num_live(&self) -> usize {
454 self.inner.borrow().num_live()
455 }
456
457 pub fn num_free_lower(&self) -> usize {
459 self.inner.borrow().lower.as_ref().map_or(0, Tier::num_free)
460 }
461
462 pub fn num_free_upper(&self) -> usize {
464 self.inner.borrow().upper.num_free()
465 }
466
467 pub fn dealloc(&self, addr: u64) -> Result<(), AllocError> {
469 self.inner.borrow_mut().dealloc_addr(addr)
470 }
471
472 pub fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
474 self.inner.borrow().allocation_len(addr)
475 }
476
477 pub fn base_addr(&self) -> u64 {
479 self.inner.borrow().base_addr()
480 }
481
482 pub fn slot_size(&self) -> usize {
484 self.inner.borrow().max_alloc_len()
485 }
486
487 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 pub fn upper_slot_size(&self) -> usize {
498 self.inner.borrow().upper.slot_size as usize
499 }
500
501 pub fn count(&self) -> usize {
503 self.inner.borrow().count()
504 }
505
506 pub fn alloc(&self, len: usize) -> Result<Allocation, AllocError> {
508 self.inner.borrow_mut().alloc(len)
509 }
510
511 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}