soldb_core/
memory.rs

1//! The memory of every step of a trace, held as what each frame wrote.
2//!
3//! A step's memory is the memory of its EVM frame after some number of that frame's
4//! recorded entries. An entry is either a write (some bytes at an offset, and the size of
5//! memory after it) or a full image. A frame recorded write by write takes an image
6//! whenever the bytes written since the last one reach the size of its memory, so
7//! rebuilding a step's memory never replays more than about one memory's worth of
8//! writes. A producer that has every step's memory in full, as a node's `structLogs` or a
9//! trace file do, records images only, and then a step's memory is one of them.
10
11use std::sync::Mutex;
12
13use bytes::Bytes;
14use thiserror::Error;
15
16use crate::same_buffer;
17
18/// Which memory a step has: its frame and how many of that frame's entries are applied.
19/// Packed into one word per step; [`MemoryRef::NONE`] is a step without memory.
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub(crate) struct MemoryRef(u64);
22
23impl MemoryRef {
24    pub(crate) const NONE: Self = Self(u64::MAX);
25
26    fn new(frame: usize, applied: usize) -> Self {
27        // Both are counts of things held in memory, far below `u32::MAX` for any trace
28        // that fits in memory at all.
29        let frame = u32::try_from(frame).unwrap_or(u32::MAX - 1);
30        let applied = u32::try_from(applied).unwrap_or(u32::MAX);
31        Self(u64::from(frame) << 32 | u64::from(applied))
32    }
33
34    fn frame(self) -> usize {
35        (self.0 >> 32) as usize
36    }
37
38    fn applied(self) -> usize {
39        (self.0 & u64::from(u32::MAX)) as usize
40    }
41
42    pub(crate) fn is_none(self) -> bool {
43        self == Self::NONE
44    }
45}
46
47/// Why a memory write cannot be recorded.
48#[derive(Debug, Clone, PartialEq, Eq, Error)]
49pub enum MemoryWriteError {
50    /// The written bytes end past the size the memory is said to have after the write.
51    #[error("{length} bytes written at offset {offset} end past the memory size {size}")]
52    PastEnd {
53        offset: u64,
54        length: usize,
55        size: u64,
56    },
57    /// The memory is said to have shrunk, which EVM memory never does within a frame.
58    #[error("memory shrank from {before} to {after} bytes")]
59    Shrank { before: u64, after: u64 },
60    /// More memory than this platform can address.
61    #[error("a memory of {0} bytes does not fit in this platform's address space")]
62    TooLarge(u64),
63}
64
65#[derive(Debug, Clone)]
66enum Entry {
67    Image(Bytes),
68    Write {
69        offset: usize,
70        size: usize,
71        data: Span,
72    },
73}
74
75/// Where the bytes of one write are in the [`Arena`].
76#[derive(Debug, Clone, Copy)]
77struct Span {
78    chunk: u32,
79    start: u32,
80    length: u32,
81}
82
83#[derive(Debug, Clone, Default)]
84struct Frame {
85    entries: Vec<Entry>,
86    /// The positions of the image entries, ascending.
87    images: Vec<u32>,
88    /// The memory as recorded so far, while writes are being recorded into the frame.
89    live: Option<Vec<u8>>,
90    /// Bytes written since the last image, which decides when to take the next.
91    written_since_image: usize,
92}
93
94/// The bytes of every write, appended into fixed chunks so that recording never moves
95/// what was recorded before.
96#[derive(Debug, Clone, Default)]
97struct Arena {
98    chunks: Vec<Vec<u8>>,
99}
100
101const ARENA_CHUNK: usize = 1 << 20;
102
103impl Arena {
104    fn push(&mut self, data: &[u8]) -> Span {
105        let fits = self
106            .chunks
107            .last()
108            .is_some_and(|chunk| chunk.capacity() - chunk.len() >= data.len());
109        if !fits {
110            self.chunks
111                .push(Vec::with_capacity(ARENA_CHUNK.max(data.len())));
112        }
113        let index = self.chunks.len() - 1;
114        let chunk = &mut self.chunks[index];
115        let start = chunk.len();
116        chunk.extend_from_slice(data);
117        // A chunk holds at most one write larger than `ARENA_CHUNK`, so its offsets and
118        // lengths fit in `u32` unless a single write is 4 GiB.
119        Span {
120            chunk: u32::try_from(index).unwrap_or(u32::MAX),
121            start: u32::try_from(start).unwrap_or(u32::MAX),
122            length: u32::try_from(data.len()).unwrap_or(u32::MAX),
123        }
124    }
125
126    fn get(&self, span: Span) -> &[u8] {
127        let start = span.start as usize;
128        &self.chunks[span.chunk as usize][start..start + span.length as usize]
129    }
130}
131
132/// The memory last rebuilt, so that reading the steps of a frame in order applies each
133/// write once.
134#[derive(Debug)]
135struct Cached {
136    frame: usize,
137    applied: usize,
138    memory: Vec<u8>,
139}
140
141#[derive(Debug, Default)]
142pub(crate) struct MemoryStore {
143    frames: Vec<Frame>,
144    /// The frames writes go to, innermost last.
145    active: Vec<usize>,
146    /// The frame full images go to.
147    snapshots: Option<usize>,
148    arena: Arena,
149    cache: Mutex<Option<Cached>>,
150}
151
152impl Clone for MemoryStore {
153    fn clone(&self) -> Self {
154        Self {
155            frames: self.frames.clone(),
156            active: self.active.clone(),
157            snapshots: self.snapshots,
158            arena: self.arena.clone(),
159            cache: Mutex::new(None),
160        }
161    }
162}
163
164impl MemoryStore {
165    /// The memory of a step whose memory is `memory` in full.
166    pub(crate) fn snapshot(&mut self, memory: Bytes) -> MemoryRef {
167        let frame = *self.snapshots.get_or_insert_with(|| {
168            self.frames.push(Frame::default());
169            self.frames.len() - 1
170        });
171        let frame_entries = &mut self.frames[frame];
172        let unchanged = match frame_entries.entries.last() {
173            Some(Entry::Image(last)) => {
174                same_buffer(last, &memory) || (last.len() == memory.len() && *last == memory)
175            }
176            _ => false,
177        };
178        if !unchanged {
179            let position = frame_entries.entries.len();
180            frame_entries.entries.push(Entry::Image(memory));
181            frame_entries
182                .images
183                .push(u32::try_from(position).unwrap_or(u32::MAX));
184        }
185        MemoryRef::new(frame, frame_entries.entries.len())
186    }
187
188    /// Starts recording a new frame, empty, as a call or a creation starts one.
189    pub(crate) fn start_frame(&mut self) {
190        self.frames.push(Frame {
191            live: Some(Vec::new()),
192            ..Frame::default()
193        });
194        self.active.push(self.frames.len() - 1);
195    }
196
197    /// Whether a frame is being recorded write by write.
198    pub(crate) fn recording(&self) -> bool {
199        !self.active.is_empty()
200    }
201
202    /// Stops recording the innermost frame; writes go to its caller's again.
203    pub(crate) fn end_frame(&mut self) {
204        if let Some(frame) = self.active.pop() {
205            self.frames[frame].live = None;
206        }
207    }
208
209    /// Records that `data` was written at `offset` of the innermost frame's memory, which
210    /// is `size` bytes long afterwards. A write without data records the memory growing.
211    pub(crate) fn write(
212        &mut self,
213        offset: u64,
214        data: &[u8],
215        size: u64,
216    ) -> Result<(), MemoryWriteError> {
217        if self.active.is_empty() {
218            self.start_frame();
219        }
220        let frame_index = *self.active.last().unwrap_or(&0);
221        let size_bytes = usize::try_from(size).map_err(|_| MemoryWriteError::TooLarge(size))?;
222        let start = usize::try_from(offset).map_err(|_| MemoryWriteError::TooLarge(offset))?;
223        let past_end = MemoryWriteError::PastEnd {
224            offset,
225            length: data.len(),
226            size,
227        };
228        let end = start.checked_add(data.len()).ok_or(past_end.clone())?;
229        if end > size_bytes {
230            return Err(past_end);
231        }
232        let before = self.frames[frame_index].live.as_ref().map_or(0, Vec::len);
233        if size_bytes < before {
234            return Err(MemoryWriteError::Shrank {
235                before: before as u64,
236                after: size,
237            });
238        }
239        let span = self.arena.push(data);
240        let frame = &mut self.frames[frame_index];
241        let live = frame.live.get_or_insert_with(Vec::new);
242        live.resize(size_bytes, 0);
243        live[start..end].copy_from_slice(data);
244        frame.entries.push(Entry::Write {
245            offset: start,
246            size: size_bytes,
247            data: span,
248        });
249        frame.written_since_image += data.len();
250        if frame.written_since_image >= live.len() && !live.is_empty() {
251            let position = frame.entries.len();
252            frame
253                .entries
254                .push(Entry::Image(Bytes::copy_from_slice(live)));
255            frame
256                .images
257                .push(u32::try_from(position).unwrap_or(u32::MAX));
258            frame.written_since_image = 0;
259        }
260        Ok(())
261    }
262
263    /// The memory of a step appended now, as recorded write by write: the innermost
264    /// frame's after everything written to it so far, or none when no frame was started.
265    pub(crate) fn current(&self) -> MemoryRef {
266        self.active.last().map_or(MemoryRef::NONE, |frame| {
267            MemoryRef::new(*frame, self.frames[*frame].entries.len())
268        })
269    }
270
271    /// The bytes `memory` refers to.
272    pub(crate) fn read(&self, memory: MemoryRef) -> Option<Bytes> {
273        if memory.is_none() {
274            return None;
275        }
276        let frame_index = memory.frame();
277        let applied = memory.applied();
278        let frame = self.frames.get(frame_index)?;
279        if applied == 0 {
280            return Some(Bytes::new());
281        }
282        let images_before = frame
283            .images
284            .partition_point(|position| (*position as usize) < applied);
285        let image = images_before
286            .checked_sub(1)
287            .map(|index| frame.images[index] as usize);
288        if let Some(position) = image {
289            if position + 1 == applied {
290                if let Entry::Image(bytes) = &frame.entries[position] {
291                    return Some(bytes.clone());
292                }
293            }
294        }
295
296        // Rebuild from the image before the step, or from the cached memory when it is the
297        // same frame at or past that image and not past the step.
298        let replay_from = image.map_or(0, |position| position + 1);
299        let mut cache = self
300            .cache
301            .lock()
302            .unwrap_or_else(std::sync::PoisonError::into_inner);
303        let reusable = cache.as_ref().is_some_and(|cached| {
304            cached.frame == frame_index
305                && cached.applied >= replay_from
306                && cached.applied <= applied
307        });
308        if !reusable {
309            let base = match image.map(|position| &frame.entries[position]) {
310                Some(Entry::Image(bytes)) => bytes.to_vec(),
311                _ => Vec::new(),
312            };
313            *cache = Some(Cached {
314                frame: frame_index,
315                applied: replay_from,
316                memory: base,
317            });
318        }
319        let cached = cache.as_mut()?;
320        for entry in &frame.entries[cached.applied..applied] {
321            if let Entry::Write { offset, size, data } = entry {
322                let bytes = self.arena.get(*data);
323                cached.memory.resize(*size, 0);
324                cached.memory[*offset..*offset + bytes.len()].copy_from_slice(bytes);
325            }
326        }
327        cached.applied = applied;
328        Some(Bytes::copy_from_slice(&cached.memory))
329    }
330}
331
332#[cfg(test)]
333mod tests {
334    use super::*;
335
336    #[test]
337    fn snapshots_share_unchanged_memory() {
338        let mut store = MemoryStore::default();
339        let first = store.snapshot(Bytes::from_static(&[1, 2]));
340        let same = store.snapshot(Bytes::from(vec![1, 2]));
341        let changed = store.snapshot(Bytes::from_static(&[3]));
342        assert_eq!(first, same);
343        assert_ne!(first, changed);
344        assert_eq!(store.read(first).as_deref(), Some(&[1, 2][..]));
345        assert_eq!(store.read(changed).as_deref(), Some(&[3][..]));
346        assert_eq!(store.read(MemoryRef::NONE), None);
347    }
348
349    #[test]
350    fn rebuilds_memory_from_writes_and_images() {
351        let mut store = MemoryStore::default();
352        store.start_frame();
353        let empty = store.current();
354        store.write(0, &[0xaa; 32], 32).expect("write");
355        // 32 bytes written into 32 bytes of memory takes an image.
356        let after_first = store.current();
357        store.write(40, &[0xbb], 64).expect("write");
358        let after_second = store.current();
359
360        // A call's frame does not see the caller's memory, and the caller resumes.
361        store.start_frame();
362        store.write(0, &[0xcc], 32).expect("write");
363        let callee = store.current();
364        store.end_frame();
365        assert_eq!(store.current(), after_second);
366
367        store.write(0, &[], 96).expect("grow");
368        let grown = store.current();
369
370        assert_eq!(store.read(empty).as_deref(), Some(&[][..]));
371        assert_eq!(store.read(after_first).as_deref(), Some(&[0xaa; 32][..]));
372        let mut expected = vec![0xaa; 32];
373        expected.resize(64, 0);
374        expected[40] = 0xbb;
375        assert_eq!(store.read(after_second).as_deref(), Some(&expected[..]));
376        let mut callee_memory = [0; 32];
377        callee_memory[0] = 0xcc;
378        assert_eq!(store.read(callee).as_deref(), Some(&callee_memory[..]));
379        expected.resize(96, 0);
380        assert_eq!(store.read(grown).as_deref(), Some(&expected[..]));
381        // Reading backwards rebuilds from the image again.
382        assert_eq!(store.read(after_second).as_deref(), Some(&expected[..64]));
383    }
384
385    #[test]
386    fn refuses_writes_that_do_not_fit() {
387        let mut store = MemoryStore::default();
388        assert_eq!(
389            store.write(31, &[1, 2], 32),
390            Err(MemoryWriteError::PastEnd {
391                offset: 31,
392                length: 2,
393                size: 32
394            })
395        );
396        store.write(0, &[1], 64).expect("write");
397        assert_eq!(
398            store.write(0, &[1], 32),
399            Err(MemoryWriteError::Shrank {
400                before: 64,
401                after: 32
402            })
403        );
404    }
405}
soldb_core/memory.rs

soldb_core/
memory.rs
