heapdump_vmo/
resources_table_v1.rs

Help
1// Copyright 2023 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::alloc::Layout;
6use std::mem::{align_of, size_of, size_of_val};
7
8use crate::memory_mapped_vmo::{MemoryMappable, MemoryMappedVmo};
9
10/// An offset within the VMO.
11type Offset = u32;
12const OFFSET_INVALID: Offset = Offset::MAX;
13
14// Stack traces are stored in compressed form as an array of u8 prefixed by a u16 stating its
15// length. The u16 is guaranteed to be aligned.
16type StackTraceLength = u16;
17
18// Known stack traces are indexed by a hash table, whose linked list heads (one for each bucket) are
19// stored at the beginning of the VMO.
20//
21// Note that the presence and the format of the hash table is meant to be an internal detail of the
22// current ResourcesTableWriter implementation: ResourcesTableReader does not depend on it.
23const NUM_STACK_BUCKETS: usize = 1 << 13;
24type StackBucketHeads = [Offset; NUM_STACK_BUCKETS];
25
26/// A resource key is just an offset into the VMO.
27#[derive(Clone, Copy, Eq, Debug, Hash, Ord, PartialEq, PartialOrd)]
28#[repr(transparent)]
29pub struct ResourceKey(Offset);
30
31impl ResourceKey {
32    /// Used by tests in this crate to construct placeholder values.
33    #[cfg(test)]
34    pub(crate) const fn from_raw(offset: Offset) -> ResourceKey {
35        ResourceKey(offset)
36    }
37
38    pub const fn into_raw(self) -> Offset {
39        self.0
40    }
41}
42
43#[repr(C)]
44#[derive(Debug)]
45pub struct ThreadInfo {
46    pub koid: zx::sys::zx_koid_t,
47    pub name: zx::Name,
48}
49
50// SAFETY: ThreadInfo only contains memory-mappable types and we never parse the name in it.
51unsafe impl MemoryMappable for ThreadInfo {}
52
53/// Mediates write access to a VMO containing compressed stack traces and thread info structs.
54///
55/// Compressed stack traces are stored as a hash table for efficient deduplication. Thread
56/// information structures are not deduplicated (it is expected that deduplication happens at a
57/// higher level in the stack). Apart from the hash table's bucket heads, all data is immutable:
58/// neither stack traces nor thread info structs can be modified or deleted after having been
59/// inserted.
60///
61/// Hash collisions are handled by maintaining per-bucket linked lists. Specifically, an array of
62/// list heads, one for each bucket, is stored at the beginning of the VMO. The remaining part of
63/// the VMO contains the linked list nodes. Since nodes are immutable, insertion always happen at
64/// the head of the list.
65///
66/// Thanks to the fact that inserted data is immutable, other readers are allowed to read data from
67/// this VMO while ResourcesTableWriter is still alive. In particular, all insertion functions
68/// return a ResourceKey, which is simply the offset of the just-inserted now-immutable data, and
69/// that can be used by ResourcesTableReader to read data back without even having to know about the
70/// hash table.
71pub struct ResourcesTableWriter {
72    storage: MemoryMappedVmo,
73    watermark: usize, // Offset of the first unallocated byte.
74}
75
76impl ResourcesTableWriter {
77    /// Initializes a VMO as an empty table and creates an AllocationsTableWriter to write into it.
78    ///
79    /// The caller must guarantee that the `vmo` is not accessed by others (unless they use
80    /// ResourcesTableReader instances) while the returned instance is alive.
81    pub fn new(vmo: &zx::Vmo) -> Result<ResourcesTableWriter, crate::Error> {
82        let storage = MemoryMappedVmo::new_readwrite(vmo)?;
83        if storage.vmo_size() < size_of::<StackBucketHeads>() {
84            return Err(crate::Error::BufferTooSmall);
85        } else if storage.vmo_size() - 1 > Offset::MAX as usize {
86            return Err(crate::Error::BufferTooBig);
87        }
88
89        let mut result = ResourcesTableWriter { storage, watermark: size_of::<StackBucketHeads>() };
90
91        // Clear the hash table.
92        for bucket_index in 0..NUM_STACK_BUCKETS {
93            *result.stack_bucket_head_at(bucket_index) = OFFSET_INVALID;
94        }
95
96        Ok(result)
97    }
98
99    /// Allocates space in the VMO and returns the base offset of the allocated range.
100    fn allocate(&mut self, layout: Layout) -> Result<Offset, crate::Error> {
101        // Forbid alignment requirements greater than the page size, as they would have implications
102        // on how the VMO can be mapped for reading.
103        if layout.align() > zx::system_get_page_size() as usize {
104            return Err(crate::Error::InvalidInput);
105        }
106
107        let result_start = (self.watermark + layout.align() - 1) & !(layout.align() - 1);
108        let result_end = result_start + layout.size();
109
110        if result_end <= self.storage.vmo_size() {
111            self.watermark = result_end;
112            Ok(result_start as Offset)
113        } else {
114            Err(crate::Error::OutOfSpace)
115        }
116    }
117
118    /// This is the hash function for stack traces.
119    fn compute_bucket_index(compressed_stack_trace: &[u8]) -> usize {
120        let tmp = crc::crc32::checksum_ieee(compressed_stack_trace);
121        tmp as usize % NUM_STACK_BUCKETS
122    }
123
124    /// Returns a mutable reference to the head of a given bucket's linked list.
125    fn stack_bucket_head_at(&mut self, bucket_index: usize) -> &mut Offset {
126        // The bucket heads are always stored at the beginning of the VMO.
127        let bucket_heads = self.storage.get_object_mut::<StackBucketHeads>(0).unwrap();
128        &mut bucket_heads[bucket_index]
129    }
130
131    /// Tries to find an already-inserted stack trace in the given bucket by scanning its linked
132    /// list.
133    fn find_in_bucket(
134        &mut self,
135        bucket_index: usize,
136        compressed_stack_trace: &[u8],
137    ) -> Option<Offset> {
138        let mut curr = *self.stack_bucket_head_at(bucket_index);
139        while curr != OFFSET_INVALID {
140            // Read the "next" field in the current node and its compressed stack trace, which is
141            // stored immediately afterwards.
142            let curr_next: Offset = *self.storage.get_object(curr as usize).unwrap();
143            let payload_offset = curr as usize + size_of_val(&curr_next);
144            let curr_payload = get_compressed_stack_trace(&self.storage, payload_offset).unwrap();
145
146            // Is this stack trace the one we were looking for?
147            if *curr_payload == *compressed_stack_trace {
148                return Some(curr);
149            }
150
151            curr = curr_next;
152        }
153
154        // Not found.
155        None
156    }
157
158    fn insert_in_bucket(
159        &mut self,
160        bucket_index: usize,
161        compressed_stack_trace: &[u8],
162    ) -> Result<Offset, crate::Error> {
163        // Allocate space for:
164        // - The "next" field
165        // - The stack trace length
166        // - The actual stack trace
167        let alloc_bytes =
168            size_of::<Offset>() + size_of::<StackTraceLength>() + compressed_stack_trace.len();
169        let alloc_align = align_of::<Offset>();
170        let new = self.allocate(Layout::from_size_align(alloc_bytes, alloc_align).unwrap())?;
171
172        let old_head = *self.stack_bucket_head_at(bucket_index);
173
174        // Write them.
175        *self.storage.get_object_mut(new as usize).unwrap() = old_head;
176        set_compressed_stack_trace(
177            &mut self.storage,
178            new as usize + size_of::<Offset>(),
179            compressed_stack_trace,
180        )
181        .unwrap();
182
183        // Update the bucket's head pointer.
184        *self.stack_bucket_head_at(bucket_index) = new;
185
186        Ok(new)
187    }
188
189    /// Appends a compressed stack trace and returns its offset into the VMO.
190    ///
191    /// This function also applies deduplication: if a copy of the given stack trace is already
192    /// present, the offset of the existing copy is returned without modifying the VMO contents.
193    pub fn intern_compressed_stack_trace(
194        &mut self,
195        compressed_stack_trace: &[u8],
196    ) -> Result<(ResourceKey, bool), crate::Error> {
197        // Verify that the length fits in StackTraceLength and return error if it does not.
198        if compressed_stack_trace.len() > StackTraceLength::MAX as usize {
199            return Err(crate::Error::BufferTooBig);
200        }
201
202        // Find/insert a StackNode and get its offset within the memory region.
203        let bucket_index = Self::compute_bucket_index(compressed_stack_trace);
204        let (offset, inserted) = match self.find_in_bucket(bucket_index, compressed_stack_trace) {
205            Some(offset) => (offset, false),
206            None => (self.insert_in_bucket(bucket_index, compressed_stack_trace)?, true),
207        };
208
209        // Adjust the returned offset to skip the "next" field (which is an internal
210        // ResourcesTableWriter implementation detail) and point directly to the StackTraceLength
211        // field (which is what ResourcesTableReader expects to receive).
212        let resource_key = ResourceKey(offset + size_of::<Offset>() as Offset);
213        Ok((resource_key, inserted))
214    }
215
216    /// Appends a thread information entry and returns its offset into the VMO.
217    pub fn insert_thread_info(
218        &mut self,
219        koid: zx::sys::zx_koid_t,
220        name: &zx::Name,
221    ) -> Result<ResourceKey, crate::Error> {
222        let offset = self.allocate(Layout::new::<ThreadInfo>())?;
223        *self.storage.get_object_mut(offset as usize).unwrap() = ThreadInfo { koid, name: *name };
224        Ok(ResourceKey(offset))
225    }
226}
227
228/// Mediates read access to a VMO written by ResourcesTableWriter.
229pub struct ResourcesTableReader {
230    storage: MemoryMappedVmo,
231}
232
233impl ResourcesTableReader {
234    pub fn new(vmo: &zx::Vmo) -> Result<ResourcesTableReader, crate::Error> {
235        let storage = MemoryMappedVmo::new_readonly(vmo)?;
236        Ok(ResourcesTableReader { storage })
237    }
238
239    /// Gets the compressed stack trace identified by `resource_key`.
240    pub fn get_compressed_stack_trace(
241        &self,
242        resource_key: ResourceKey,
243    ) -> Result<&[u8], crate::Error> {
244        let ResourceKey(offset) = resource_key;
245        get_compressed_stack_trace(&self.storage, offset as usize)
246    }
247
248    /// Gets the thread info entry identified by `resource_key`.
249    pub fn get_thread_info(&self, resource_key: ResourceKey) -> Result<&ThreadInfo, crate::Error> {
250        let ResourceKey(offset) = resource_key;
251        Ok(self.storage.get_object(offset as usize)?)
252    }
253}
254
255fn get_compressed_stack_trace(
256    storage: &MemoryMappedVmo,
257    byte_offset: usize,
258) -> Result<&[u8], crate::Error> {
259    // Read the length.
260    let header: StackTraceLength = *storage.get_object(byte_offset)?;
261
262    // Get actual data, which is stored immediately after the length, as a slice.
263    Ok(storage.get_slice(byte_offset + size_of_val(&header), header as usize)?)
264}
265
266fn set_compressed_stack_trace(
267    storage: &mut MemoryMappedVmo,
268    byte_offset: usize,
269    compressed_stack_trace: &[u8],
270) -> Result<(), crate::Error> {
271    let header: StackTraceLength =
272        compressed_stack_trace.len().try_into().map_err(|_| crate::Error::BufferTooBig)?;
273
274    // Write the length.
275    *storage.get_object_mut(byte_offset)? = header;
276
277    // Write actual data immediately after the length.
278    storage
279        .get_slice_mut(byte_offset + size_of_val(&header), compressed_stack_trace.len())?
280        .copy_from_slice(compressed_stack_trace);
281
282    Ok(())
283}
284
285#[cfg(test)]
286mod tests {
287    use super::*;
288    use assert_matches::assert_matches;
289
290    // Some tests below use this constant to create a VMO with a known size.
291    const VMO_SIZE: usize = 4 * 1024 * 1024; // 4 MiB
292
293    struct TestStorage {
294        vmo: zx::Vmo,
295    }
296
297    impl TestStorage {
298        pub fn new(vmo_size: usize) -> TestStorage {
299            let vmo = zx::Vmo::create(vmo_size as u64).unwrap();
300            TestStorage { vmo }
301        }
302
303        fn create_writer(&self) -> ResourcesTableWriter {
304            ResourcesTableWriter::new(&self.vmo).unwrap()
305        }
306
307        fn create_reader(&self) -> ResourcesTableReader {
308            ResourcesTableReader::new(&self.vmo).unwrap()
309        }
310    }
311
312    #[test]
313    fn test_stack_trace_deduplication() {
314        let storage = TestStorage::new(VMO_SIZE);
315        let mut writer = storage.create_writer();
316
317        // Insert different distinct stack traces and store the corresponding resource keys.
318        // The number of stack traces is chosen so that at least one bucket contains at least three
319        // stack traces.
320        const COUNT: usize = 2 * NUM_STACK_BUCKETS + 1;
321        let mut pairs = Vec::new();
322        for i in 0..COUNT {
323            // Generate a unique array of bytes and pretend it is a compressed stack trace.
324            let stack_trace = i.to_ne_bytes();
325
326            let (resource_key, inserted) =
327                writer.intern_compressed_stack_trace(&stack_trace).unwrap();
328            assert!(inserted, "expected true because the stack trace was not present");
329
330            pairs.push((stack_trace, resource_key));
331        }
332
333        // Verify that trying to insert them again returns the same resource keys.
334        for (stack_trace, expected_resource_key) in &pairs {
335            let (actual_resource_key, inserted) =
336                writer.intern_compressed_stack_trace(stack_trace).unwrap();
337            assert!(!inserted, "expected false because the stack trace is already present");
338            assert_eq!(actual_resource_key, *expected_resource_key);
339        }
340
341        // Verify that they can be read back.
342        let reader = storage.create_reader();
343        for (expected_stack_trace, resource_key) in &pairs {
344            let actual_stack_trace = reader.get_compressed_stack_trace(*resource_key).unwrap();
345            assert_eq!(actual_stack_trace, *expected_stack_trace);
346        }
347    }
348
349    #[test]
350    fn test_empty_stack_trace() {
351        let storage = TestStorage::new(VMO_SIZE);
352        let mut writer = storage.create_writer();
353
354        // It must be possible to insert the empty stack trace.
355        let (resource_key, inserted) = writer.intern_compressed_stack_trace(&[]).unwrap();
356        assert!(inserted);
357
358        // Verify that is can be read back correctly.
359        let reader = storage.create_reader();
360        let read_result = reader.get_compressed_stack_trace(resource_key).unwrap();
361        assert_eq!(read_result, []);
362    }
363
364    #[test]
365    fn test_long_stack_traces() {
366        let storage = TestStorage::new(VMO_SIZE);
367        let mut writer = storage.create_writer();
368
369        // Inserting a stack trace whose length cannot be represented in the length field (u16).
370        // should fail.
371        let stack_trace_too_long = vec![0xAA; u16::MAX as usize + 1];
372        let result = writer.intern_compressed_stack_trace(&stack_trace_too_long);
373        assert_matches!(result, Err(crate::Error::BufferTooBig));
374
375        // Inserting a stack trace with the maximum representable length should succeed.
376        let stack_trace_max_len = vec![0x55; u16::MAX as usize];
377        let (resource_key, _) = writer.intern_compressed_stack_trace(&stack_trace_max_len).unwrap();
378
379        // And it must be possible to read it back.
380        let reader = storage.create_reader();
381        let read_result = reader.get_compressed_stack_trace(resource_key).unwrap();
382        assert_eq!(read_result, stack_trace_max_len);
383    }
384
385    #[test]
386    fn test_write_until_out_of_space() {
387        let storage = TestStorage::new(VMO_SIZE);
388        let mut writer = storage.create_writer();
389
390        // Insert many distinct stack traces and verify that, at some point, we get an OutOfSpace
391        // error. Instead of estimating exactly how many stack traces can fit, we just use VMO_SIZE
392        // as an upper bound before declaring failure (each distinct stack trace obviously requires
393        // at least one byte of storage).
394        for i in 0..=VMO_SIZE {
395            // Generate a unique array of bytes and pretend it is a compressed stack trace.
396            let stack_trace = i.to_ne_bytes();
397
398            if let Err(crate::Error::OutOfSpace) =
399                writer.intern_compressed_stack_trace(&stack_trace)
400            {
401                return; // Test passed
402            }
403        }
404
405        unreachable!("Inserted more than {} distinct stack traces", VMO_SIZE);
406    }
407
408    #[test]
409    fn test_thread_info() {
410        let storage = TestStorage::new(VMO_SIZE);
411        let mut writer = storage.create_writer();
412
413        // Insert a thread info struct with placeholder values (the name must be padded to the
414        // expected length).
415        const FAKE_KOID: zx::sys::zx_koid_t = 1234;
416        const FAKE_NAME: zx::Name = zx::Name::new_lossy("fake-name");
417        let resource_key = writer.insert_thread_info(FAKE_KOID, &FAKE_NAME).unwrap();
418
419        // Verify that it can be read back correctly.
420        let reader = storage.create_reader();
421        let thread_info = reader.get_thread_info(resource_key).unwrap();
422        assert_eq!(thread_info.koid, FAKE_KOID);
423        assert_eq!(thread_info.name, FAKE_NAME);
424    }
425}
heapdump_vmo/resources_table_v1.rs

heapdump_vmo/
resources_table_v1.rs
