wasmtime_environ/
frame_table.rs

1//! Frame-table parser and lookup logic.
2//!
3//! This module contains utilities to interpret the `.wasmtime.frame`
4//! section in a compiled artifact as produced by
5//! [`crate::compile::frame_table::FrameTableBuilder`].
6
7use crate::FuncKey;
8use alloc::vec::Vec;
9use object::{Bytes, LittleEndian, U32Bytes};
10
11/// An index into the table of stack shapes.
12#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
13pub struct FrameStackShape(pub(crate) u32);
14impl FrameStackShape {
15    pub(crate) fn index(self) -> usize {
16        usize::try_from(self.0).unwrap()
17    }
18
19    /// Get the raw stack-shape index suitable for serializing into
20    /// metadata.
21    pub fn raw(self) -> u32 {
22        self.0
23    }
24
25    /// Wrap a raw stack shape index (e.g. from debug tags) into a FrameStackShape.
26    pub fn from_raw(index: u32) -> FrameStackShape {
27        FrameStackShape(index)
28    }
29}
30
31/// An index to a frame descriptor that can be referenced from a
32/// program point descriptor.
33#[derive(Clone, Copy, Debug)]
34pub struct FrameTableDescriptorIndex(pub(crate) u32);
35impl FrameTableDescriptorIndex {
36    fn index(self) -> usize {
37        usize::try_from(self.0).unwrap()
38    }
39}
40
41/// A parser for a frame-table section.
42///
43/// This parser holds slices to the in-memory section data, and is
44/// cheap to construct: it reads some header fields but does not
45/// interpret or validate content data until queried.
46pub struct FrameTable<'a> {
47    frame_descriptor_ranges: &'a [U32Bytes<LittleEndian>],
48    frame_descriptor_data: &'a [u8],
49
50    frame_descriptor_fp_offsets: &'a [U32Bytes<LittleEndian>],
51
52    progpoint_pcs: &'a [U32Bytes<LittleEndian>],
53    progpoint_descriptor_offsets: &'a [U32Bytes<LittleEndian>],
54    progpoint_descriptor_data: &'a [U32Bytes<LittleEndian>],
55}
56
57impl<'a> FrameTable<'a> {
58    /// Parse a frame table section from a byte-slice as produced by
59    /// [`crate::compile::frame_table::FrameTableBuilder`].
60    pub fn parse(data: &'a [u8]) -> anyhow::Result<FrameTable<'a>> {
61        let mut data = Bytes(data);
62        let num_frame_descriptors = data
63            .read::<U32Bytes<LittleEndian>>()
64            .map_err(|_| anyhow::anyhow!("Unable to read frame descriptor count prefix"))?;
65        let num_frame_descriptors = usize::try_from(num_frame_descriptors.get(LittleEndian))?;
66        let num_progpoint_descriptors = data
67            .read::<U32Bytes<LittleEndian>>()
68            .map_err(|_| anyhow::anyhow!("Unable to read progpoint descriptor count prefix"))?;
69        let num_progpoint_descriptors =
70            usize::try_from(num_progpoint_descriptors.get(LittleEndian))?;
71        let frame_descriptor_pool_length = data
72            .read::<U32Bytes<LittleEndian>>()
73            .map_err(|_| anyhow::anyhow!("Unable to read frame descriptor pool length"))?;
74        let frame_descriptor_pool_length =
75            usize::try_from(frame_descriptor_pool_length.get(LittleEndian))?;
76        let progpoint_descriptor_pool_length = data
77            .read::<U32Bytes<LittleEndian>>()
78            .map_err(|_| anyhow::anyhow!("Unable to read progpoint descriptor pool length"))?;
79        let progpoint_descriptor_pool_length =
80            usize::try_from(progpoint_descriptor_pool_length.get(LittleEndian))?;
81
82        let (frame_descriptor_ranges, data) =
83            object::slice_from_bytes::<U32Bytes<LittleEndian>>(data.0, 2 * num_frame_descriptors)
84                .map_err(|_| anyhow::anyhow!("Unable to read frame descriptor ranges slice"))?;
85        let (frame_descriptor_fp_offsets, data) =
86            object::slice_from_bytes::<U32Bytes<LittleEndian>>(data, num_frame_descriptors)
87                .map_err(|_| anyhow::anyhow!("Unable to read frame descriptor FP offset slice"))?;
88
89        let (progpoint_pcs, data) =
90            object::slice_from_bytes::<U32Bytes<LittleEndian>>(data, num_progpoint_descriptors)
91                .map_err(|_| anyhow::anyhow!("Unable to read progpoint PC slice"))?;
92        let (progpoint_descriptor_offsets, data) =
93            object::slice_from_bytes::<U32Bytes<LittleEndian>>(data, num_progpoint_descriptors)
94                .map_err(|_| anyhow::anyhow!("Unable to read progpoint descriptor offset slice"))?;
95
96        let (frame_descriptor_data, data) = data
97            .split_at_checked(frame_descriptor_pool_length)
98            .ok_or_else(|| anyhow::anyhow!("Unable to read frame descriptor pool"))?;
99
100        let (progpoint_descriptor_data, _) = object::slice_from_bytes::<U32Bytes<LittleEndian>>(
101            data,
102            progpoint_descriptor_pool_length,
103        )
104        .map_err(|_| anyhow::anyhow!("Unable to read progpoint descriptor pool"))?;
105
106        Ok(FrameTable {
107            frame_descriptor_ranges,
108            frame_descriptor_data,
109            frame_descriptor_fp_offsets,
110            progpoint_pcs,
111            progpoint_descriptor_offsets,
112            progpoint_descriptor_data,
113        })
114    }
115
116    /// Get raw frame descriptor data and slot-to-FP-offset for a
117    /// given frame descriptor.
118    pub fn frame_descriptor(
119        &self,
120        frame_descriptor: FrameTableDescriptorIndex,
121    ) -> Option<(&'a [u8], u32)> {
122        let range_start = self
123            .frame_descriptor_ranges
124            .get(frame_descriptor.index() * 2)?
125            .get(LittleEndian);
126        let range_end = self
127            .frame_descriptor_ranges
128            .get(frame_descriptor.index() * 2 + 1)?
129            .get(LittleEndian);
130        let range_start = usize::try_from(range_start).unwrap();
131        let range_end = usize::try_from(range_end).unwrap();
132        if range_end < range_start || range_end > self.frame_descriptor_data.len() {
133            return None;
134        }
135        let descriptor = &self.frame_descriptor_data[range_start..range_end];
136        let slot_to_fp_offset = self
137            .frame_descriptor_fp_offsets
138            .get(frame_descriptor.index())?
139            .get(LittleEndian);
140        Some((descriptor, slot_to_fp_offset))
141    }
142
143    /// Get frames for the program point at the PC upper-bounded by a
144    /// given search PC (offset in text section).
145    pub fn find_program_point(
146        &self,
147        search_pc: u32,
148        search_pos: FrameInstPos,
149    ) -> Option<impl Iterator<Item = (u32, FrameTableDescriptorIndex, FrameStackShape)>> {
150        let key = FrameInstPos::encode(search_pc, search_pos);
151        let index = match self
152            .progpoint_pcs
153            .binary_search_by_key(&key, |entry| entry.get(LittleEndian))
154        {
155            Ok(idx) => idx,
156            Err(idx) if idx > 0 => idx - 1,
157            Err(_) => return None,
158        };
159
160        Some(self.program_point_frame_iter(index))
161    }
162
163    /// Get all program point records with iterators over
164    /// corresponding frames for each.
165    pub fn into_program_points(
166        self,
167    ) -> impl Iterator<
168        Item = (
169            u32,
170            FrameInstPos,
171            Vec<(u32, FrameTableDescriptorIndex, FrameStackShape)>,
172        ),
173    > + 'a {
174        self.progpoint_pcs.iter().enumerate().map(move |(i, pc)| {
175            let pc_and_pos = pc.get(LittleEndian);
176            let (pc, pos) = FrameInstPos::decode(pc_and_pos);
177            (
178                pc,
179                pos,
180                self.program_point_frame_iter(i).collect::<Vec<_>>(),
181            )
182        })
183    }
184
185    fn program_point_frame_iter(
186        &self,
187        index: usize,
188    ) -> impl Iterator<Item = (u32, FrameTableDescriptorIndex, FrameStackShape)> {
189        let offset =
190            usize::try_from(self.progpoint_descriptor_offsets[index].get(LittleEndian)).unwrap();
191        let mut data = &self.progpoint_descriptor_data[offset..];
192
193        core::iter::from_fn(move || {
194            if data.len() < 3 {
195                return None;
196            }
197            let wasm_pc = data[0].get(LittleEndian);
198            let frame_descriptor = FrameTableDescriptorIndex(data[1].get(LittleEndian));
199            let stack_shape = FrameStackShape(data[2].get(LittleEndian));
200            data = &data[3..];
201            let not_last = wasm_pc & 0x8000_0000 != 0;
202            let wasm_pc = wasm_pc & 0x7fff_ffff;
203            if !not_last {
204                data = &[];
205            }
206            Some((wasm_pc, frame_descriptor, stack_shape))
207        })
208    }
209}
210
211/// An instruction position for a program point.
212///
213/// We attach debug metadata to a *position* on an offset in the text
214/// (code) section, either "post" or "pre". The "post" position
215/// logically comes first, and is associated with the instruction that
216/// ends at this offset (i.e., the previous instruction). The "pre"
217/// position comes next, and is associated with the instruction that
218/// begins at this offset (i.e., the next instruction).
219///
220/// We make this distinction because metadata lookups sometimes occur
221/// with a PC that is after the instruction (e.g., the return address
222/// after a call instruction), and sometimes at the instruction (e.g.,
223/// a trapping PC address). The lookup context will know which one to
224/// use -- e.g., when walking the stack, "pre" for a trapping PC and
225/// "post" for every frame after that -- so we simply encode it as
226/// part of the position and allow searching on it.
227///
228/// The need for this distinction can be understood by way of an
229/// example; say we have:
230///
231/// ```plain
232/// call ...
233/// trapping_store ...
234/// ```
235///
236/// where both instructions have debug metadata. We might look up the
237/// PC of `trapping_store` once as we walk the stack from within the
238/// call (we will get this PC because it is the return address) and
239/// once when `trapping_store` itself traps; and we want different
240/// metadata in each case.
241///
242/// An alternative is to universally attach tags to the end offset of
243/// an instruction, which allows us to handle return addresses
244/// naturally but requires traps to adjust their PC. However, this
245/// requires trap handlers to know the length of the trapping
246/// instruction, which is not always easy -- in the most general case,
247/// on variable-length instruction sets, it requires a full
248/// instruction decoder.
249#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
250pub enum FrameInstPos {
251    /// The "post" position at an offset attaches to the instruction
252    /// that ends at this offset, i.e., came previously.
253    Post,
254    /// The "pre" position at an offset attaches to the instruction
255    /// that begins at this offset, i.e., comes next.
256    Pre,
257}
258
259impl FrameInstPos {
260    pub(crate) fn encode(pc: u32, pos: FrameInstPos) -> u32 {
261        let lsb = match pos {
262            Self::Post => 0,
263            Self::Pre => 1,
264        };
265        debug_assert!(pc < 0x8000_0000);
266        (pc << 1) | lsb
267    }
268    pub(crate) fn decode(bits: u32) -> (u32, FrameInstPos) {
269        let pos = match bits & 1 {
270            0 => Self::Post,
271            1 => Self::Pre,
272            _ => unreachable!(),
273        };
274        let pc = bits >> 1;
275        (pc, pos)
276    }
277}
278
279/// An offset into the state slot.
280#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
281pub struct FrameStateSlotOffset(pub(crate) u32);
282impl FrameStateSlotOffset {
283    #[cfg(feature = "compile")]
284    pub(crate) fn add(self, offset: u32) -> FrameStateSlotOffset {
285        FrameStateSlotOffset(self.0 + offset)
286    }
287
288    /// Get the offset into the state stackslot, suitable for use in a
289    /// `stack_store`/`stack_load` instruction.
290    pub fn offset(self) -> i32 {
291        i32::try_from(self.0).unwrap()
292    }
293}
294
295/// A type stored in a frame.
296#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
297#[allow(missing_docs, reason = "self-describing variants")]
298pub enum FrameValType {
299    I32,
300    I64,
301    F32,
302    F64,
303    V128,
304    AnyRef,
305    FuncRef,
306    ExternRef,
307    ExnRef,
308    ContRef,
309}
310
311impl FrameValType {
312    #[cfg(feature = "compile")]
313    pub(crate) fn storage_size(&self, pointer_size: u32) -> u32 {
314        match self {
315            FrameValType::I32 => 4,
316            FrameValType::I64 => 8,
317            FrameValType::F32 => 4,
318            FrameValType::F64 => 8,
319            FrameValType::V128 => 16,
320            FrameValType::AnyRef | FrameValType::ExternRef | FrameValType::ExnRef => 4,
321            FrameValType::FuncRef => pointer_size,
322            FrameValType::ContRef => 2 * pointer_size,
323        }
324    }
325}
326
327impl From<FrameValType> for u8 {
328    fn from(value: FrameValType) -> u8 {
329        match value {
330            FrameValType::I32 => 0,
331            FrameValType::I64 => 1,
332            FrameValType::F32 => 2,
333            FrameValType::F64 => 3,
334            FrameValType::V128 => 4,
335            FrameValType::AnyRef => 5,
336            FrameValType::FuncRef => 6,
337            FrameValType::ExternRef => 7,
338            FrameValType::ExnRef => 8,
339            FrameValType::ContRef => 9,
340        }
341    }
342}
343
344impl TryFrom<u8> for FrameValType {
345    type Error = anyhow::Error;
346    fn try_from(value: u8) -> anyhow::Result<Self> {
347        match value {
348            0 => Ok(Self::I32),
349            1 => Ok(Self::I64),
350            2 => Ok(Self::F32),
351            3 => Ok(Self::F64),
352            4 => Ok(Self::V128),
353            5 => Ok(Self::AnyRef),
354            6 => Ok(Self::FuncRef),
355            7 => Ok(Self::ExternRef),
356            8 => Ok(Self::ExnRef),
357            9 => Ok(Self::ContRef),
358            _ => Err(anyhow::anyhow!("Invalid type")),
359        }
360    }
361}
362
363/// Parser for a frame state slot descriptor.
364///
365/// This provides the ability to extract offsets and types for locals
366/// and for the stack given a stack shape.
367pub struct FrameStateSlot<'a> {
368    func_key: FuncKey,
369    local_offsets: &'a [U32Bytes<LittleEndian>],
370    stack_shape_parents: &'a [U32Bytes<LittleEndian>],
371    stack_shape_offsets: &'a [U32Bytes<LittleEndian>],
372    local_types: &'a [u8],
373    stack_shape_types: &'a [u8],
374}
375
376impl<'a> FrameStateSlot<'a> {
377    /// Parse a slot descriptor.
378    ///
379    /// This parses the descriptor bytes as provided by
380    /// [`FrameTable::frame_descriptor`].
381    pub fn parse(descriptor: &'a [u8]) -> anyhow::Result<FrameStateSlot<'a>> {
382        let mut data = Bytes(descriptor);
383        let func_key_namespace = data
384            .read::<U32Bytes<LittleEndian>>()
385            .map_err(|_| anyhow::anyhow!("Unable to read func key namespace"))?
386            .get(LittleEndian);
387        let func_key_index = data
388            .read::<U32Bytes<LittleEndian>>()
389            .map_err(|_| anyhow::anyhow!("Unable to read func key index"))?
390            .get(LittleEndian);
391        let func_key = FuncKey::from_raw_parts(func_key_namespace, func_key_index);
392
393        let num_locals = data
394            .read::<U32Bytes<LittleEndian>>()
395            .map_err(|_| anyhow::anyhow!("Unable to read num_locals"))?
396            .get(LittleEndian);
397        let num_locals = usize::try_from(num_locals)?;
398        let num_stack_shapes = data
399            .read::<U32Bytes<LittleEndian>>()
400            .map_err(|_| anyhow::anyhow!("Unable to read num_stack_shapes"))?
401            .get(LittleEndian);
402        let num_stack_shapes = usize::try_from(num_stack_shapes)?;
403
404        let (local_offsets, data) =
405            object::slice_from_bytes::<U32Bytes<LittleEndian>>(data.0, num_locals)
406                .map_err(|_| anyhow::anyhow!("Unable to read local_offsets slice"))?;
407        let (stack_shape_parents, data) =
408            object::slice_from_bytes::<U32Bytes<LittleEndian>>(data, num_stack_shapes)
409                .map_err(|_| anyhow::anyhow!("Unable to read stack_shape_parents slice"))?;
410        let (stack_shape_offsets, data) =
411            object::slice_from_bytes::<U32Bytes<LittleEndian>>(data, num_stack_shapes)
412                .map_err(|_| anyhow::anyhow!("Unable to read stack_shape_offsets slice"))?;
413        let (local_types, data) = data
414            .split_at_checked(num_locals)
415            .ok_or_else(|| anyhow::anyhow!("Unable to read local_types slice"))?;
416        let (stack_shape_types, _) = data
417            .split_at_checked(num_stack_shapes)
418            .ok_or_else(|| anyhow::anyhow!("Unable to read stack_shape_types slice"))?;
419
420        Ok(FrameStateSlot {
421            func_key,
422            local_offsets,
423            stack_shape_parents,
424            stack_shape_offsets,
425            local_types,
426            stack_shape_types,
427        })
428    }
429
430    /// Get the FuncKey for the function that produced this frame
431    /// slot.
432    pub fn func_key(&self) -> FuncKey {
433        self.func_key
434    }
435
436    /// Get the local offsets and types.
437    pub fn locals(&self) -> impl Iterator<Item = (FrameStateSlotOffset, FrameValType)> {
438        (0..self.num_locals()).map(|i| self.local(i).unwrap())
439    }
440
441    /// Get the type and offset for a given local.
442    pub fn local(&self, index: usize) -> Option<(FrameStateSlotOffset, FrameValType)> {
443        let offset = FrameStateSlotOffset(self.local_offsets.get(index)?.get(LittleEndian));
444        let ty = FrameValType::try_from(*self.local_types.get(index)?).expect("Invalid type");
445        Some((offset, ty))
446    }
447
448    /// Get the number of locals in the frame.
449    pub fn num_locals(&self) -> usize {
450        self.local_offsets.len()
451    }
452
453    /// Get the offsets and types for operand stack values, from top
454    /// of stack (most recently pushed) down.
455    pub fn stack(
456        &self,
457        shape: FrameStackShape,
458    ) -> impl Iterator<Item = (FrameStateSlotOffset, FrameValType)> {
459        fn unpack_option_shape(shape: FrameStackShape) -> Option<FrameStackShape> {
460            if shape.0 == u32::MAX {
461                None
462            } else {
463                Some(shape)
464            }
465        }
466
467        let mut shape = unpack_option_shape(shape);
468        core::iter::from_fn(move || {
469            shape.map(|s| {
470                let parent = FrameStackShape(self.stack_shape_parents[s.index()].get(LittleEndian));
471                let parent = unpack_option_shape(parent);
472                let offset =
473                    FrameStateSlotOffset(self.stack_shape_offsets[s.index()].get(LittleEndian));
474                let ty = FrameValType::try_from(self.stack_shape_types[s.index()])
475                    .expect("Invalid type");
476                shape = parent;
477                (offset, ty)
478            })
479        })
480    }
481
482    /// Returns an iterator over all storage in this frame.
483    pub fn stack_and_locals(
484        &self,
485        shape: FrameStackShape,
486    ) -> impl Iterator<Item = (FrameStateSlotOffset, FrameValType)> + '_ {
487        self.locals().chain(self.stack(shape))
488    }
489}
wasmtime_environ/frame_table.rs

wasmtime_environ/
frame_table.rs
