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;