1use core::fmt;
5use core::ptr::NonNull;
6use std::sync::Arc;
7
8use crate::arena::{Arena, ArenaError, Protection};
9use crate::stack::IndexStack;
10use crate::sync::{AtomicU32, Ordering};
11use crate::wipe::wipe;
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
15pub struct ClassSpec {
16 pub size: usize,
18 pub count: u32,
20}
21
22#[derive(Debug, Clone, PartialEq, Eq)]
25pub struct PoolConfig {
26 pub align: usize,
29 pub classes: Vec<ClassSpec>,
31 pub sensitive: bool,
34}
35
36impl PoolConfig {
37 #[must_use]
40 pub fn uniform(align: usize, min: usize, max: usize, count: u32) -> Self {
41 let mut classes = Vec::new();
42 let mut size = min.max(align).next_power_of_two();
43 while size <= max {
44 classes.push(ClassSpec { size, count });
45 size = match size.checked_mul(2) {
46 Some(s) => s,
47 None => break,
48 };
49 }
50 Self {
51 align,
52 classes,
53 sensitive: false,
54 }
55 }
56}
57
58#[derive(Debug, Clone, Copy, PartialEq, Eq)]
60pub enum PoolError {
61 Config(&'static str),
65 Arena(ArenaError),
67}
68
69impl fmt::Display for PoolError {
70 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
71 match self {
72 Self::Config(why) => write!(f, "invalid buffer pool configuration: {why}"),
73 Self::Arena(e) => write!(f, "mapping the buffer arena failed (OS error {})", e.code),
74 }
75 }
76}
77
78impl std::error::Error for PoolError {}
79
80#[derive(Debug, Clone, Copy, PartialEq, Eq)]
82pub struct Exhausted;
83
84struct Class {
85 size: usize,
86 base: usize,
87 count: u32,
88 free: IndexStack,
90 background: Holdings,
92}
93
94pub(crate) struct Holdings {
99 held: AtomicU32,
100}
101
102impl Holdings {
103 pub(crate) fn new() -> Self {
104 Self {
105 held: AtomicU32::new(0),
106 }
107 }
108
109 pub(crate) fn try_hold(&self, cap: u32) -> bool {
111 let mut held = self.held.load(Ordering::Relaxed);
112 loop {
113 if held >= cap {
114 return false;
115 }
116 match self.held.compare_exchange_weak(
120 held,
121 held + 1,
122 Ordering::Acquire,
123 Ordering::Relaxed,
124 ) {
125 Ok(_) => return true,
126 Err(now) => {
127 held = now;
128 crate::sync::spin();
129 }
130 }
131 }
132 }
133
134 pub(crate) fn release(&self) {
136 let _was = self.held.fetch_sub(1, Ordering::Release);
137 }
138
139 pub(crate) fn held(&self) -> u32 {
141 self.held.load(Ordering::Relaxed)
142 }
143}
144
145struct Inner {
146 arena: Arena,
147 offset: usize,
148 classes: Box<[Class]>,
149 sensitive: bool,
150 protection: Protection,
151}
152
153#[derive(Clone)]
155pub struct BufPool {
156 inner: Arc<Inner>,
157}
158
159impl fmt::Debug for BufPool {
160 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
161 f.debug_struct("BufPool")
162 .field(
163 "classes",
164 &self
165 .inner
166 .classes
167 .iter()
168 .map(|c| (c.size, c.count))
169 .collect::<Vec<_>>(),
170 )
171 .field("sensitive", &self.inner.sensitive)
172 .finish()
173 }
174}
175
176impl BufPool {
177 pub fn new(cfg: &PoolConfig) -> Result<Self, PoolError> {
183 if cfg.align == 0 || !cfg.align.is_power_of_two() {
184 return Err(PoolError::Config("alignment must be a power of two"));
185 }
186 if cfg.classes.len() > usize::from(u16::MAX) + 1 {
191 return Err(PoolError::Config("at most 65,536 size classes"));
192 }
193 let mut specs = cfg.classes.clone();
194 specs.sort_by_key(|c| c.size);
195 let mut total: usize = 0;
196 for c in &specs {
197 if !c.size.is_power_of_two() || c.size < cfg.align {
198 return Err(PoolError::Config(
199 "class size must be a power of two ≥ the alignment",
200 ));
201 }
202 if c.count == 0 {
203 return Err(PoolError::Config("class count must be at least 1"));
204 }
205 if c.count > IndexStack::MAX_CAPACITY {
206 return Err(PoolError::Config("class count must be at most 16,777,215"));
207 }
208 let bytes = c
209 .size
210 .checked_mul(c.count as usize)
211 .ok_or(PoolError::Config("pool size overflows"))?;
212 total = total
213 .checked_add(bytes)
214 .ok_or(PoolError::Config("pool size overflows"))?;
215 }
216 if specs.is_empty() {
217 return Err(PoolError::Config("at least one size class is required"));
218 }
219 let mapped = total
220 .checked_add(cfg.align)
221 .ok_or(PoolError::Config("pool size overflows"))?;
222 let arena = Arena::new(mapped).map_err(PoolError::Arena)?;
223 let addr = arena.base().as_ptr() as usize;
224 let offset = addr.next_multiple_of(cfg.align) - addr;
225 let mut base = 0usize;
226 let mut classes = Vec::with_capacity(specs.len());
227 for c in &specs {
228 let free = IndexStack::with_capacity(c.count);
229 for i in 0..c.count {
230 let _initial_push = free.push(i);
232 }
233 classes.push(Class {
234 size: c.size,
235 base,
236 count: c.count,
237 free,
238 background: Holdings::new(),
239 });
240 base += c.size * c.count as usize;
241 }
242 let protection = if cfg.sensitive {
243 arena.protect_sensitive()
244 } else {
245 Protection::default()
246 };
247 Ok(Self {
248 inner: Arc::new(Inner {
249 arena,
250 offset,
251 classes: classes.into_boxed_slice(),
252 sensitive: cfg.sensitive,
253 protection,
254 }),
255 })
256 }
257
258 pub fn take(&self, len: usize) -> Result<IoBuf, Exhausted> {
269 self.take_within(len, usize::MAX)
270 }
271
272 pub fn take_capped(&self, len: usize, max: usize) -> Result<IoBuf, Exhausted> {
290 self.take_from(len, max, true)
291 }
292
293 #[must_use]
295 pub fn background_holdings(&self) -> Vec<(usize, u32, u32)> {
296 self.inner
297 .classes
298 .iter()
299 .map(|c| (c.size, c.background.held(), c.count / 2))
300 .collect()
301 }
302
303 #[must_use]
307 pub fn class_len(&self, len: usize) -> Option<usize> {
308 self.inner
309 .classes
310 .iter()
311 .map(|c| c.size)
312 .filter(|&s| s >= len)
313 .min()
314 }
315
316 pub fn take_within(&self, len: usize, max: usize) -> Result<IoBuf, Exhausted> {
324 self.take_from(len, max, false)
325 }
326
327 fn take_from(&self, len: usize, max: usize, background: bool) -> Result<IoBuf, Exhausted> {
328 let inner = &self.inner;
329 for (ci, class) in inner.classes.iter().enumerate() {
330 if class.size < len {
331 continue;
332 }
333 if class.size > max {
334 break;
335 }
336 if background && !class.background.try_hold(class.count / 2) {
337 continue;
338 }
339 let Some(index) = class.free.pop() else {
340 if background {
341 class.background.release();
342 }
343 continue;
344 };
345 let at = inner.offset + class.base + index as usize * class.size;
346 let ptr = unsafe { NonNull::new_unchecked(inner.arena.base().as_ptr().add(at)) };
349 return Ok(IoBuf {
350 pool: Arc::clone(&self.inner),
351 ptr,
352 cap: class.size,
353 len,
354 class: ci as u16,
355 index,
356 background,
357 });
358 }
359 Err(Exhausted)
360 }
361
362 #[must_use]
365 pub fn owns(&self, buf: &IoBuf) -> bool {
366 Arc::ptr_eq(&self.inner, &buf.pool)
367 }
368
369 #[must_use]
371 pub fn min_len(&self) -> usize {
372 self.inner.classes.first().map_or(0, |c| c.size)
373 }
374
375 #[must_use]
377 pub fn max_len(&self) -> usize {
378 self.inner.classes.last().map_or(0, |c| c.size)
379 }
380
381 #[must_use]
386 pub fn occupancy(&self) -> Vec<(usize, usize, u32)> {
387 self.inner
388 .classes
389 .iter()
390 .map(|c| {
391 let mut n = 0;
392 let mut held = Vec::new();
393 while let Some(i) = c.free.pop() {
394 held.push(i);
395 n += 1;
396 }
397 for &i in held.iter().rev() {
400 let _return_push = c.free.push(i);
401 }
402 (c.size, n, c.count)
403 })
404 .collect()
405 }
406
407 #[must_use]
409 pub fn protection(&self) -> Protection {
410 self.inner.protection
411 }
412}
413
414pub struct IoBuf {
420 pool: Arc<Inner>,
421 ptr: NonNull<u8>,
422 cap: usize,
423 len: usize,
424 class: u16,
425 index: u32,
426 background: bool,
429}
430
431unsafe impl Send for IoBuf {}
435unsafe impl Sync for IoBuf {}
437
438impl IoBuf {
439 #[inline]
441 #[must_use]
442 pub fn as_slice(&self) -> &[u8] {
443 unsafe { core::slice::from_raw_parts(self.ptr.as_ptr(), self.len) }
446 }
447
448 #[inline]
450 #[must_use]
451 pub fn as_mut_slice(&mut self) -> &mut [u8] {
452 unsafe { core::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.len) }
454 }
455
456 #[inline]
458 #[must_use]
459 pub fn as_ptr(&self) -> *const u8 {
460 self.ptr.as_ptr()
461 }
462
463 #[inline]
466 #[must_use]
467 pub fn as_mut_ptr(&mut self) -> *mut u8 {
468 self.ptr.as_ptr()
469 }
470
471 #[inline]
473 #[must_use]
474 pub fn len(&self) -> usize {
475 self.len
476 }
477
478 #[inline]
480 #[must_use]
481 pub fn is_empty(&self) -> bool {
482 self.len == 0
483 }
484
485 #[inline]
487 #[must_use]
488 pub fn capacity(&self) -> usize {
489 self.cap
490 }
491
492 #[inline]
495 #[must_use]
496 pub fn set_len(&mut self, len: usize) -> bool {
497 if len > self.cap {
498 return false;
499 }
500 self.len = len;
501 true
502 }
503
504 #[inline]
506 #[must_use]
507 pub fn as_mut_capacity(&mut self) -> &mut [u8] {
508 unsafe { core::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.cap) }
510 }
511}
512
513impl fmt::Debug for IoBuf {
514 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
515 f.debug_struct("IoBuf")
517 .field("len", &self.len)
518 .field("capacity", &self.cap)
519 .finish()
520 }
521}
522
523impl Drop for IoBuf {
524 fn drop(&mut self) {
525 if self.pool.sensitive {
526 wipe(self.as_mut_capacity());
527 }
528 if let Some(class) = self.pool.classes.get(usize::from(self.class)) {
529 let _returned = class.free.push(self.index);
531 if self.background {
534 class.background.release();
535 }
536 }
537 }
538}
539
540#[cfg(all(test, loom))]
541mod loom_tests {
542 use loom::sync::Arc;
543
544 use super::Holdings;
545
546 #[test]
550 fn loom_background_holdings_never_pass_their_cap() {
551 loom::model(|| {
552 let h = Arc::new(Holdings::new());
553 assert!(h.try_hold(2));
554 let t: Vec<_> = (0..2)
555 .map(|_| {
556 let h = Arc::clone(&h);
557 loom::thread::spawn(move || h.try_hold(2))
558 })
559 .collect();
560 let won = t
561 .into_iter()
562 .map(|t| t.join().unwrap())
563 .filter(|w| *w)
564 .count();
565 assert_eq!(won, 1);
566 assert_eq!(h.held(), 2);
567 h.release();
568 assert!(h.try_hold(2));
569 assert!(!h.try_hold(2));
570 });
571 }
572
573 #[test]
577 fn loom_a_capped_take_after_a_drop_finds_the_buffer() {
578 use crate::stack::IndexStack;
579 loom::model(|| {
580 let free = Arc::new(IndexStack::with_capacity(1));
581 let h = Arc::new(Holdings::new());
582 assert!(h.try_hold(1));
583 let dropper = {
584 let (free, h) = (Arc::clone(&free), Arc::clone(&h));
585 loom::thread::spawn(move || {
586 free.push(0).unwrap();
587 h.release();
588 })
589 };
590 if h.try_hold(1) {
591 assert_eq!(
592 free.pop(),
593 Some(0),
594 "the unit was free but the buffer was not"
595 );
596 }
597 dropper.join().unwrap();
598 });
599 }
600
601 #[test]
605 fn loom_background_release_racing_a_take() {
606 loom::model(|| {
607 let h = Arc::new(Holdings::new());
608 assert!(h.try_hold(1));
609 let r = {
610 let h = Arc::clone(&h);
611 loom::thread::spawn(move || h.release())
612 };
613 let got = h.try_hold(1);
614 r.join().unwrap();
615 assert_eq!(h.held(), u32::from(got));
616 });
617 }
618}
619
620#[cfg(all(test, not(loom)))]
621mod tests {
622 use super::*;
623
624 #[test]
625 fn test_take_capped_stops_at_half_a_class_and_frees_on_drop() {
626 let p = pool(4);
627 let a = p
628 .take_capped(4096, 4096)
629 .unwrap_or_else(|_| panic!("first"));
630 let b = p
631 .take_capped(4096, 4096)
632 .unwrap_or_else(|_| panic!("second"));
633 assert!(
634 p.take_capped(4096, 4096).is_err(),
635 "a third passes the cap of 2"
636 );
637 let c = p
639 .take_within(4096, 4096)
640 .unwrap_or_else(|_| panic!("commit 1"));
641 let d = p
642 .take_within(4096, 4096)
643 .unwrap_or_else(|_| panic!("commit 2"));
644 assert_eq!(p.background_holdings().first().copied(), Some((4096, 2, 2)));
645 drop(a);
646 assert_eq!(p.background_holdings()[0].1, 1);
647 let e = p
648 .take_capped(4096, 4096)
649 .unwrap_or_else(|_| panic!("after a drop"));
650 drop((b, c, d, e));
651 assert_eq!(p.background_holdings()[0].1, 0);
652 }
653
654 #[test]
655 fn test_take_capped_with_no_free_buffer_gives_its_unit_back() {
656 let p = pool(4);
657 let held: Vec<_> = (0..4)
658 .map(|_| p.take_within(4096, 4096).unwrap_or_else(|_| panic!("take")))
659 .collect();
660 assert!(p.take_capped(4096, 4096).is_err());
661 assert_eq!(p.background_holdings()[0].1, 0, "the unit was given back");
662 drop(held);
663 let x = p
664 .take_capped(4096, 4096)
665 .unwrap_or_else(|_| panic!("free again"));
666 assert_eq!(p.background_holdings()[0].1, 1);
667 drop(x);
668 }
669
670 #[test]
671 fn test_take_capped_moves_to_a_larger_class_under_the_cap() {
672 let p = pool(2);
673 let a = p
674 .take_capped(4096, 8192)
675 .unwrap_or_else(|_| panic!("4 KiB"));
676 assert_eq!(a.capacity(), 4096);
677 let b = p
678 .take_capped(4096, 8192)
679 .unwrap_or_else(|_| panic!("8 KiB"));
680 assert_eq!(b.capacity(), 8192, "the 4 KiB class's cap of 1 is used");
681 assert!(p.take_capped(4096, 8192).is_err());
682 drop((a, b));
683 }
684
685 fn pool(count: u32) -> BufPool {
686 let cfg = PoolConfig::uniform(4096, 4096, 65536, count);
687 match BufPool::new(&cfg) {
688 Ok(p) => p,
689 Err(e) => panic!("{e}"),
690 }
691 }
692
693 #[test]
694 fn test_take_is_aligned_sized_and_returns_on_drop() {
695 let p = pool(2);
696 let b = p.take(5000).unwrap_or_else(|_| panic!("exhausted"));
697 assert_eq!(b.capacity(), 8192);
698 assert_eq!(b.len(), 5000);
699 assert_eq!(b.as_ptr() as usize % 4096, 0);
700 drop(b);
701 let free: usize = p.occupancy().iter().map(|c| c.1).sum();
702 assert_eq!(free, 2 * 5);
703 }
704
705 #[test]
706 fn test_class_len_is_the_smallest_class_that_holds_the_length() {
707 let p = pool(1);
708 assert_eq!(p.class_len(1), Some(4096));
709 assert_eq!(p.class_len(4096), Some(4096));
710 assert_eq!(p.class_len(4097), Some(8192));
711 assert_eq!(p.class_len(65536), Some(65536));
712 assert_eq!(p.class_len(65537), None);
713 }
714
715 #[test]
716 fn test_take_within_never_falls_back_past_its_cap() {
717 let p = pool(1);
718 let small: Vec<_> = (0..5)
719 .filter_map(|_| p.take_within(4096, 32768).ok())
720 .collect();
721 assert_eq!(small.len(), 4);
723 assert!(p.take_within(4096, 32768).is_err());
724 assert_eq!(p.take(4096).map(|b| b.capacity()).ok(), Some(65536));
725 }
726
727 #[test]
728 fn test_owns_only_its_own_buffers() {
729 let p = pool(1);
730 let q = pool(1);
731 let b = p.take(1).unwrap_or_else(|_| panic!("exhausted"));
732 assert!(p.owns(&b));
733 assert!(p.clone().owns(&b));
734 assert!(!q.owns(&b));
735 }
736
737 #[test]
738 fn test_take_falls_back_to_larger_class_then_exhausts() {
739 let p = pool(1);
740 let a = p.take(4096);
741 let b = p.take(4096); assert_eq!(b.as_ref().map(IoBuf::capacity).ok(), Some(8192));
743 let _rest: Vec<_> = (0..3).filter_map(|_| p.take(1).ok()).collect();
744 assert!(p.take(1).is_err());
745 assert!(p.take(65537).is_err());
746 drop(a);
747 assert!(p.take(1).is_ok());
748 }
749
750 #[test]
751 fn test_buffers_do_not_overlap() {
752 let p = pool(4);
753 let mut bufs: Vec<IoBuf> = (0..20).filter_map(|_| p.take(1).ok()).collect();
754 assert_eq!(bufs.len(), 20);
755 for (i, b) in bufs.iter_mut().enumerate() {
756 let len = b.capacity();
757 assert!(b.set_len(len));
758 b.as_mut_slice().fill(i as u8);
759 }
760 for (i, b) in bufs.iter().enumerate() {
761 assert!(b.as_slice().iter().all(|&x| x == i as u8));
762 }
763 }
764
765 #[test]
766 fn test_set_len_rejects_beyond_capacity() {
767 let p = pool(1);
768 let mut b = p.take(10).unwrap_or_else(|_| panic!("exhausted"));
769 assert!(!b.set_len(4097));
770 assert_eq!(b.len(), 10);
771 assert!(b.set_len(4096));
772 }
773
774 #[test]
775 fn test_sensitive_pool_wipes_on_return() {
776 let cfg = PoolConfig {
777 sensitive: true,
778 ..PoolConfig::uniform(4096, 4096, 4096, 1)
779 };
780 let p = BufPool::new(&cfg).unwrap_or_else(|e| panic!("{e}"));
781 let mut b = p.take(4096).unwrap_or_else(|_| panic!("exhausted"));
782 b.as_mut_slice().fill(0xA5);
783 drop(b);
784 let b = p.take(4096).unwrap_or_else(|_| panic!("exhausted"));
785 assert!(b.as_slice().iter().all(|&x| x == 0));
786 }
787
788 #[test]
792 fn test_more_classes_than_a_buffer_can_record_are_refused() {
793 let mut classes = vec![ClassSpec { size: 1, count: 1 }; 65_536];
794 if !cfg!(miri) {
797 let ok = PoolConfig {
798 align: 1,
799 classes: classes.clone(),
800 sensitive: false,
801 };
802 assert!(BufPool::new(&ok).is_ok(), "65,536 classes fit");
803 }
804 classes.push(ClassSpec { size: 2, count: 1 });
805 let over = PoolConfig {
806 align: 1,
807 classes,
808 sensitive: false,
809 };
810 assert!(
811 matches!(
812 BufPool::new(&over),
813 Err(PoolError::Config("at most 65,536 size classes"))
814 ),
815 "a class past 16 bits was accepted"
816 );
817 }
818
819 #[test]
820 fn test_invalid_configs_are_rejected() {
821 assert!(
822 BufPool::new(&PoolConfig {
823 align: 3,
824 classes: vec![],
825 sensitive: false
826 })
827 .is_err()
828 );
829 assert!(
830 BufPool::new(&PoolConfig {
831 align: 4096,
832 classes: vec![],
833 sensitive: false
834 })
835 .is_err()
836 );
837 let small = PoolConfig {
838 align: 4096,
839 classes: vec![ClassSpec {
840 size: 512,
841 count: 1,
842 }],
843 sensitive: false,
844 };
845 assert!(BufPool::new(&small).is_err());
846 let zero = PoolConfig {
847 align: 4096,
848 classes: vec![ClassSpec {
849 size: 4096,
850 count: 0,
851 }],
852 sensitive: false,
853 };
854 assert!(BufPool::new(&zero).is_err());
855 let huge = PoolConfig {
856 align: 4096,
857 classes: vec![ClassSpec {
858 size: 4096,
859 count: IndexStack::MAX_CAPACITY + 1,
860 }],
861 sensitive: false,
862 };
863 assert!(BufPool::new(&huge).is_err());
864 }
865
866 #[test]
869 fn test_take_reuses_the_most_recently_returned_buffer() {
870 let p = pool(4);
871 let a = p.take(4096).unwrap_or_else(|_| panic!("exhausted"));
872 let b = p.take(4096).unwrap_or_else(|_| panic!("exhausted"));
873 let (pa, pb) = (a.as_ptr(), b.as_ptr());
874 drop(a);
875 drop(b);
876 let again = p.take(4096).unwrap_or_else(|_| panic!("exhausted"));
877 assert_eq!(
878 again.as_ptr(),
879 pb,
880 "the last buffer returned comes back first"
881 );
882 drop(again);
883 let _counted = p.occupancy();
884 let first = p.take(4096).unwrap_or_else(|_| panic!("exhausted"));
885 let second = p.take(4096).unwrap_or_else(|_| panic!("exhausted"));
886 assert_eq!(first.as_ptr(), pb, "occupancy keeps the order");
887 assert_eq!(second.as_ptr(), pa);
888 }
889
890 #[test]
891 fn test_concurrent_take_and_drop_never_share_a_slot() {
892 let p = pool(8);
893 let handles: Vec<_> = (0..8u8)
894 .map(|t| {
895 let p = p.clone();
896 std::thread::spawn(move || {
897 for _ in 0..if cfg!(miri) { 50 } else { 5_000 } {
898 if let Ok(mut b) = p.take(4096) {
899 let n = if cfg!(miri) { 64 } else { 4096 };
902 b.as_mut_slice()[..n].fill(t);
903 std::hint::spin_loop();
904 assert!(b.as_slice()[..n].iter().all(|&x| x == t), "slot shared");
905 }
906 }
907 })
908 })
909 .collect();
910 for h in handles {
911 assert!(h.join().is_ok());
912 }
913 }
914}