fxprof_processed_profile/
stack_table.rs

1use serde::ser::{Serialize, SerializeMap, Serializer};
2
3use crate::fast_hash_map::FastHashMap;
4
5/// The stack table stores the tree of stack nodes of a thread. The shape of the tree is encoded in
6/// the prefix column: Root stack nodes have null as their prefix, and every non-root stack has the
7/// stack index of its "caller" / "parent" as its prefix. Every stack node also has a frame and a
8/// category. A "call stack" is a list of frames. Every stack index in the stack table represents
9/// such a call stack; the "list of frames" is obtained by walking the path in the tree from the
10/// root to the given stack node.
11///
12/// Stacks are used in the thread's samples; each sample refers to a stack index. Stacks can be
13/// shared between samples.
14///
15/// With this representation, every sample only needs to store a single integer to identify the
16/// sample's stack. We take advantage of the fact that many call stacks in the profile have a
17/// shared prefix; storing these stacks as a tree saves a lot of space compared to storing them as
18/// actual lists of frames.
19///
20/// The category of a stack node is always non-null and is derived from a stack's frame and its
21/// prefix. Frames can have null categories, stacks cannot. If a stack's frame has a null category,
22/// the stack inherits the category of its prefix stack. Root stacks whose frame has a null stack
23/// have their category set to the "default category". (The default category is currently defined
24/// as the category in the profile's category list whose color is "grey", and such a category is
25/// required to be present.)
26///
27/// You could argue that the stack table's category column is derived data and as such doesn't need
28/// to be stored in the profile itself. This is true, but storing this information in the stack
29/// table makes it a lot easier to carry it through various transforms that we apply to threads.
30/// For example, here's a case where a stack's category is not recoverable from any other
31/// information in the transformed thread:
32///
33/// In the call path
34///   someJSFunction [JS] -> Node.insertBefore [DOM] -> nsAttrAndChildArray::InsertChildAt,
35///
36/// the stack node for nsAttrAndChildArray::InsertChildAt should inherit the category DOM from its
37/// "Node.insertBefore" prefix stack. And it should keep the DOM category even if you apply the
38/// "Merge node into calling function" transform to Node.insertBefore. This transform removes the
39/// stack node "Node.insertBefore" from the stackTable, so the information about the DOM category
40/// would be lost if it wasn't inherited into the nsAttrAndChildArray::InsertChildAt stack before
41/// transforms are applied.
42#[derive(Debug, Clone, Default)]
43pub struct StackTable {
44    stack_prefixes: Vec<Option<usize>>,
45    stack_frames: Vec<usize>,
46
47    // (parent stack, frame_index) -> stack index
48    index: FastHashMap<(Option<usize>, usize), usize>,
49}
50
51impl StackTable {
52    pub fn new() -> Self {
53        Default::default()
54    }
55
56    pub fn index_for_stack(&mut self, prefix: Option<usize>, frame: usize) -> usize {
57        match self.index.get(&(prefix, frame)) {
58            Some(stack) => *stack,
59            None => {
60                let stack = self.stack_prefixes.len();
61                self.stack_prefixes.push(prefix);
62                self.stack_frames.push(frame);
63                self.index.insert((prefix, frame), stack);
64                stack
65            }
66        }
67    }
68}
69
70impl Serialize for StackTable {
71    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
72        let len = self.stack_prefixes.len();
73        let mut map = serializer.serialize_map(Some(3))?;
74        map.serialize_entry("length", &len)?;
75        map.serialize_entry("prefix", &self.stack_prefixes)?;
76        map.serialize_entry("frame", &self.stack_frames)?;
77        map.end()
78    }
79}
fxprof_processed_profile/stack_table.rs

fxprof_processed_profile/
stack_table.rs
