Skip to main content

harfrust/
budget.rs

1//! Limits on work and allocations while deriving cached OpenType layout data.
2//!
3//! These are independent of the buffer's shaping limits. They only run while
4//! building caches, including lazy builds shared across shaping calls. Once an
5//! allowance is insufficient, the affected lookup is discarded and stays
6//! skipped. Beyond the limits, the retained lookups can depend on use order.
7
8use core::mem::size_of;
9use core::sync::atomic::{AtomicUsize, Ordering};
10
11/// A font's preprocessing allowance, shared by lazy cache initializers.
12///
13/// Repeated visits to aliased data consume work again. Allocations consume
14/// their requested capacity, even if the resulting cache is later discarded.
15/// Neither allowance is replenished between lookup builds or shaping calls.
16#[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    // Calibrated against all lookups in 3716 Google Fonts and the HarfBuzz
27    // performance/monster font collections. The highest measured work and
28    // allocation use were below 5% of these allowances, including Gulzar's
29    // 3625-subtable lookup. Ceilings also bound padding with unused data.
30    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        // `try_update` is newer than the MSRV; `fetch_update` is deprecated.
58        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}