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; 64]>,
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 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 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 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 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 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 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 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 fn byte_len(&self) -> usize {
407 (self.upper.layout().end_addr() - self.base_addr()) as usize
408 }
409}
410
411#[derive(Clone)]
417pub struct SlotPool {
418 inner: Rc<RefCell<Inner>>,
419}
420
421impl SlotPool {
422 pub(crate) fn generation(&self) -> u64 {
424 self.inner.borrow().generation
425 }
426
427 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 pub fn new(layout: SlotLayout) -> Result<Self, AllocError> {
443 Self::from_layouts(None, layout)
444 }
445
446 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 pub fn live_addrs(&self) -> Vec<u64> {
464 self.inner.borrow().live_addrs()
465 }
466
467 pub fn layouts(&self) -> (Option<SlotLayout>, SlotLayout) {
469 self.inner.borrow().layouts()
470 }
471
472 pub fn slot_addr(&self, index: usize) -> Option<u64> {
476 self.inner.borrow().slot_addr(index)
477 }
478
479 pub fn num_free(&self) -> usize {
481 self.inner.borrow().num_free()
482 }
483
484 pub fn num_live(&self) -> usize {
486 self.inner.borrow().num_live()
487 }
488
489 pub fn num_free_lower(&self) -> usize {
491 self.inner.borrow().lower.as_ref().map_or(0, Tier::num_free)
492 }
493
494 pub fn num_free_upper(&self) -> usize {
496 self.inner.borrow().upper.num_free()
497 }
498
499 pub fn dealloc(&self, addr: u64) -> Result<(), AllocError> {
501 self.inner.borrow_mut().dealloc_addr(addr)
502 }
503
504 pub fn allocation_len(&self, addr: u64) -> Result<usize, AllocError> {
506 self.inner.borrow().allocation_len(addr)
507 }
508
509 pub fn base_addr(&self) -> u64 {
511 self.inner.borrow().base_addr()
512 }
513
514 pub fn slot_size(&self) -> usize {
516 self.inner.borrow().max_alloc_len()
517 }
518
519 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 pub fn upper_slot_size(&self) -> usize {
530 self.inner.borrow().upper.slot_size as usize
531 }
532
533 pub fn count(&self) -> usize {
535 self.inner.borrow().count()
536 }
537
538 pub fn alloc(&self, len: usize) -> Result<Allocation, AllocError> {
540 self.inner.borrow_mut().alloc(len)
541 }
542
543 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}