1use core::mem::size_of;
9use core::sync::atomic::{AtomicUsize, Ordering};
10
11#[derive(Debug)]
17pub(crate) struct Budget {
18 work: AtomicUsize,
19 bytes: AtomicUsize,
20}
21
22#[derive(Clone, Copy, Debug, PartialEq, Eq)]
23pub(crate) struct Exhausted;
24
25impl Budget {
26 pub fn for_table_bytes(bytes: usize) -> Self {
31 Self::new(
32 bytes.saturating_mul(256).clamp(4 << 20, 128 << 20),
33 bytes.saturating_mul(256).clamp(4 << 20, 128 << 20),
34 )
35 }
36
37 pub const fn new(work: usize, bytes: usize) -> Self {
38 Self {
39 work: AtomicUsize::new(work),
40 bytes: AtomicUsize::new(bytes),
41 }
42 }
43
44 pub fn work(&self, visits: usize) -> Result<(), Exhausted> {
45 Self::take(&self.work, visits)
46 }
47
48 pub fn alloc<T>(&self, count: usize) -> Result<(), Exhausted> {
49 let bytes = count.checked_mul(size_of::<T>()).ok_or(Exhausted)?;
50 Self::take(&self.bytes, bytes)
51 }
52
53 fn take(counter: &AtomicUsize, amount: usize) -> Result<(), Exhausted> {
54 if amount == 0 {
55 return Ok(());
56 }
57 let mut remaining = counter.load(Ordering::Relaxed);
59 loop {
60 let next = remaining.checked_sub(amount).ok_or(Exhausted)?;
61 match counter.compare_exchange_weak(
62 remaining,
63 next,
64 Ordering::Relaxed,
65 Ordering::Relaxed,
66 ) {
67 Ok(_) => return Ok(()),
68 Err(actual) => remaining = actual,
69 }
70 }
71 }
72
73 #[cfg(test)]
74 pub fn remaining(&self) -> (usize, usize) {
75 (
76 self.work.load(Ordering::Relaxed),
77 self.bytes.load(Ordering::Relaxed),
78 )
79 }
80}
81
82#[cfg(test)]
83mod tests {
84 use super::*;
85
86 #[test]
87 fn allowances_are_independent_and_cannot_wrap() {
88 let budget = Budget::new(3, 8);
89 assert_eq!(budget.work(3), Ok(()));
90 assert_eq!(budget.work(1), Err(Exhausted));
91 assert_eq!(budget.alloc::<u32>(2), Ok(()));
92 assert_eq!(budget.alloc::<u32>(1), Err(Exhausted));
93 assert_eq!(budget.alloc::<u32>(usize::MAX), Err(Exhausted));
94 assert_eq!(budget.remaining(), (0, 0));
95 }
96
97 #[test]
98 fn size_scaling_is_bounded() {
99 assert_eq!(Budget::for_table_bytes(0).remaining(), (4 << 20, 4 << 20));
100 assert_eq!(
101 Budget::for_table_bytes(usize::MAX).remaining(),
102 (128 << 20, 128 << 20)
103 );
104 }
105
106 #[test]
107 #[cfg(feature = "std")]
108 fn concurrent_builders_share_the_allowance() {
109 let budget = Budget::new(1000, 1000);
110 let spent = std::thread::scope(|scope| {
111 let handles: Vec<_> = (0..8)
112 .map(|_| {
113 scope.spawn(|| {
114 let mut spent = 0;
115 while budget.work(1).is_ok() {
116 spent += 1;
117 }
118 spent
119 })
120 })
121 .collect();
122 handles
123 .into_iter()
124 .map(|h| h.join().unwrap())
125 .sum::<usize>()
126 });
127 assert_eq!(spent, 1000);
128 assert_eq!(budget.remaining(), (0, 1000));
129 }
130}