Skip to main content

unityrs_core/
pin.rs

1//! What a slice keeps alive (plan sections 3.15 and 8, R3). A `Bytes`
2//! slice of a decoded run, or of an input's own bytes, keeps the whole
3//! buffer alive, with its charge, for as long as the slice lives: on the
4//! corpus one value kept past its input's handles kept the input's whole
5//! decoded run alive (up to 69.4 MB), through its strings and byte arrays
6//! and through the node lists that name its keys, whose strings are slices
7//! of the file too.
8//!
9//! So a value an object read returns ([`crate::object::ObjectRef`]) and
10//! each typetree a `SerializedFile` parses copy their slices out, into one
11//! buffer of their own charged to the same meter, when the slices would
12//! keep much more than themselves alive: when `L - S >= max(1 MiB, 4 S)`
13//! ([`worth_copying`]), `L` the length of the buffer they are slices of
14//! (the file's [`crate::files::SerializedFile::pinned`]) and `S` the
15//! distinct bytes they span. Below that, a kept value keeps at most
16//! `max(S + 1 MiB, 5 S)` of the buffer alive, its own slices included, and
17//! a copy would cost more than it frees. The copy's charge rides in its
18//! `Bytes`, its owner record included ([`crate::budget::charged_bytes`]), so
19//! it returns when the last slice of it drops. A refused copy leaves the
20//! slices in place. Legacy reads and parses proceed after a refusal, while a
21//! lossless read propagates it on the caller's meter. [`Copies`] counts what
22//! was copied, per file. The
23//! other slices the core hands out are not copied, and each keeps its whole
24//! buffer alive as any slice does: [`crate::object::ObjectRef::raw_data`],
25//! [`crate::files::BundleFile::entry_bytes`] and
26//! [`crate::files::BundleFile::entry_range`],
27//! [`crate::files::SerializedFile::data`], and the value of
28//! [`crate::walk::read_typetree`], whose caller hands it the buffer.
29//!
30//! **Each byte once.** The copy holds each byte of the buffer that some
31//! slice names once, however many slices name it, and each slice becomes the
32//! slice of the copy at the same place in those bytes: slices that were one
33//! buffer (an address and a length) are one buffer of the copy, and slices
34//! that overlapped overlap there as they did. So what a tree's compile reads
35//! and counts, which goes by buffer
36//! (`typetree::tree::names`: rows that share a buffer cost what one row
37//! naming it costs), is the same for its copied rows as for its rows read
38//! from a short run, and a name 300 rows share is held once (perf stage 2's
39//! review: each slice was copied on its own, so 300 rows naming one
40//! 1,000-byte string held 300 copies of it, and their compile, which no
41//! longer saw one buffer, counted 600,000 bytes of work where the same file
42//! read lazily counted 12,000). To find those bytes the slices are listed
43//! by where they lie, sorted, and merged where they overlap or touch: a
44//! table of two words a slice, charged to the meter while the copy is made,
45//! whose refusal is the copy's.
46
47use std::sync::Arc;
48use std::sync::atomic::{AtomicU64, Ordering};
49
50use bytes::Bytes;
51
52use crate::budget::DecodeBuf;
53use crate::error::LimitKind;
54use crate::limits::{ChargeError, Meter, MeteredVec};
55use crate::raw::RawStr;
56use crate::typetree::NodeRow;
57
58/// The least a copy frees: slices of a buffer this long or shorter are
59/// never copied.
60pub const UNPIN_MIN: u64 = 1 << 20;
61
62/// Whether slices of `s` bytes, of a buffer of `pinned` bytes, are copied
63/// out: `pinned - s >= max(1 MiB, 4 s)`, and there is something to copy.
64#[must_use]
65pub const fn worth_copying(pinned: u64, s: u64) -> bool {
66    let four = s.saturating_mul(4);
67    let floor = if four > UNPIN_MIN { four } else { UNPIN_MIN };
68    s > 0 && pinned.saturating_sub(s) >= floor
69}
70
71/// A slice a copy may replace.
72pub(crate) enum Slice<'a> {
73    Str(&'a mut RawStr),
74    Bytes(&'a mut Bytes),
75}
76
77impl Slice<'_> {
78    fn bytes(&self) -> &[u8] {
79        match self {
80            Self::Str(s) => s.as_bytes(),
81            Self::Bytes(b) => b,
82        }
83    }
84
85    fn set(&mut self, to: Bytes) {
86        match self {
87            Self::Str(s) => **s = RawStr::from_shared(to),
88            Self::Bytes(b) => **b = to,
89        }
90    }
91}
92
93/// What holds slices, each visited in one fixed order.
94pub(crate) trait Slices {
95    fn each(&mut self, f: &mut dyn FnMut(Slice<'_>));
96}
97
98impl Slices for MeteredVec<NodeRow> {
99    fn each(&mut self, f: &mut dyn FnMut(Slice<'_>)) {
100        for row in self.as_mut_slice() {
101            f(Slice::Str(&mut row.ty));
102            f(Slice::Str(&mut row.name));
103        }
104    }
105}
106
107fn len64(n: usize) -> u64 {
108    u64::try_from(n).unwrap_or(u64::MAX)
109}
110
111/// Where `b` lies in `within`, from and to, if it is a non-empty slice of it.
112fn place(within: &[u8], b: &[u8]) -> Option<(usize, usize)> {
113    let at = b.as_ptr().addr().checked_sub(within.as_ptr().addr())?;
114    let end = at.checked_add(b.len())?;
115    (!b.is_empty() && end <= within.len()).then_some((at, end))
116}
117
118/// `spans` sorted and merged where they overlap or touch, in place: the
119/// number of merged spans, which then lead the table.
120fn merge(spans: &mut [(usize, usize)]) -> usize {
121    spans.sort_unstable();
122    let mut kept = 0usize;
123    for i in 0..spans.len() {
124        let Some(&(from, to)) = spans.get(i) else {
125            break;
126        };
127        if let Some(last) = kept.checked_sub(1).and_then(|k| spans.get_mut(k))
128            && from <= last.1
129        {
130            last.1 = last.1.max(to);
131            continue;
132        }
133        // `kept <= i`: the slot is there.
134        if let Some(slot) = spans.get_mut(kept) {
135            *slot = (from, to);
136        }
137        kept += 1;
138    }
139    kept
140}
141
142/// Copies the slices of `target` that lie in `within` (a slice of a buffer
143/// of `pinned` bytes) into one buffer charged to `meter`, when
144/// [`worth_copying`] says so, each byte once (module docs), each slice then
145/// a slice of the copy: the bytes copied, 0 when nothing was (no slice lies
146/// in `within`, the copy would free too little, or the meter or the budget
147/// refused it or its table of slices).
148pub(crate) fn copy_out(
149    target: &mut dyn Slices,
150    within: &[u8],
151    pinned: u64,
152    meter: &Arc<Meter>,
153) -> u64 {
154    try_copy_out(target, within, pinned, meter, false).unwrap_or(0)
155}
156
157/// The lossless read also accounts for sort and copy work and surfaces refusals.
158pub(crate) fn try_copy_out(
159    target: &mut dyn Slices,
160    within: &[u8],
161    pinned: u64,
162    meter: &Arc<Meter>,
163    count_work: bool,
164) -> Result<u64, ChargeError> {
165    if pinned <= UNPIN_MIN {
166        return Ok(0);
167    }
168    let mut n = 0usize;
169    target.each(&mut |sl| n += usize::from(place(within, sl.bytes()).is_some()));
170    if n == 0 {
171        return Ok(0);
172    }
173    let mut table = MeteredVec::with_capacity(meter, n)?;
174    let mut listed = Ok(());
175    target.each(&mut |sl| {
176        if listed.is_ok()
177            && let Some(span) = place(within, sl.bytes())
178        {
179            listed = table.push(span);
180        }
181    });
182    listed?;
183    if count_work {
184        meter.count_decode(len64(n).saturating_mul(u64::from(n.ilog2() + 1)))?;
185    }
186    let kept = merge(table.as_mut_slice());
187    let Some(spans) = table.as_mut_slice().get_mut(..kept) else {
188        return Ok(0);
189    };
190    let s = spans
191        .iter()
192        .fold(0u64, |s, (from, to)| s.saturating_add(len64(to - from)));
193    if !worth_copying(pinned, s) {
194        return Ok(0);
195    }
196    if count_work {
197        meter.count_decode(s)?;
198    }
199    let mut buf = DecodeBuf::new(meter, s, s, LimitKind::InputMemory)?;
200    for span in spans.iter_mut() {
201        let Some(bytes) = within.get(span.0..span.1) else {
202            return Ok(0);
203        };
204        buf.extend_from_slice(bytes)?;
205        // From here a span is its start and where its bytes start in the copy.
206        span.1 = buf.len() - (span.1 - span.0);
207    }
208    let copy = buf.into_bytes()?;
209    target.each(&mut |mut sl| {
210        if let Some((from, to)) = place(within, sl.bytes()) {
211            // The span holding `from`: the last that starts at or before it.
212            let i = spans.partition_point(|&(start, _)| start <= from);
213            if let Some(&(start, at)) = i.checked_sub(1).and_then(|i| spans.get(i)) {
214                let at = at + (from - start);
215                sl.set(copy.slice(at..at + (to - from)));
216            }
217        }
218    });
219    Ok(s)
220}
221
222/// What a file's reads and its parse copied out of the buffer its bytes
223/// are a slice of (module docs; plan section 8, R3).
224#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
225#[non_exhaustive]
226pub struct Copies {
227    /// Values whose slices an object read copied out.
228    pub values: u64,
229    /// The bytes those copies hold.
230    pub value_bytes: u64,
231    /// Typetrees whose strings the parse copied out.
232    pub trees: u64,
233    /// The bytes those copies hold.
234    pub tree_bytes: u64,
235}
236
237const _: () = crate::send_sync::<Copies>();
238
239/// [`Copies`] as a file counts them, on any thread: two relaxed atomics
240/// per value copied, nothing per value read. A build with `--cfg
241/// unityrs_no_counters` compiles the counting out, as it does the bundles'
242/// counts (the copies are made all the same).
243#[derive(Debug, Default)]
244pub(crate) struct CopyCounts {
245    values: AtomicU64,
246    value_bytes: AtomicU64,
247    trees: u64,
248    tree_bytes: u64,
249}
250
251impl CopyCounts {
252    /// The parse's typetree copies: `trees` of them, holding `bytes`.
253    pub(crate) fn new(trees: u64, bytes: u64) -> Self {
254        let on = cfg!(not(unityrs_no_counters));
255        Self {
256            trees: if on { trees } else { 0 },
257            tree_bytes: if on { bytes } else { 0 },
258            ..Self::default()
259        }
260    }
261
262    /// A value read that copied `bytes` out (none for 0).
263    pub(crate) fn value(&self, bytes: u64) {
264        if cfg!(not(unityrs_no_counters)) && bytes > 0 {
265            self.values.fetch_add(1, Ordering::Relaxed);
266            self.value_bytes.fetch_add(bytes, Ordering::Relaxed);
267        }
268    }
269
270    pub(crate) fn get(&self) -> Copies {
271        Copies {
272            values: self.values.load(Ordering::Relaxed),
273            value_bytes: self.value_bytes.load(Ordering::Relaxed),
274            trees: self.trees,
275            tree_bytes: self.tree_bytes,
276        }
277    }
278}
279
280#[cfg(test)]
281mod tests;