crashrustler/unwind/
dwarf_expr.rs

1//! DWARF expression evaluator (stack machine).
2//!
3//! Evaluates DWARF expressions used in CFI register rules and CFA definitions.
4//! Supports the standard opcodes needed for macOS unwinding.
5
6use super::registers::RegisterContext;
7use super::{MemoryReader, UnwindError};
8
9/// DW_OP constants
10mod op {
11    pub const ADDR: u8 = 0x03;
12    pub const DEREF: u8 = 0x06;
13    pub const CONST1U: u8 = 0x08;
14    pub const CONST1S: u8 = 0x09;
15    pub const CONST2U: u8 = 0x0A;
16    pub const CONST2S: u8 = 0x0B;
17    pub const CONST4U: u8 = 0x0C;
18    pub const CONST4S: u8 = 0x0D;
19    pub const CONST8U: u8 = 0x0E;
20    pub const CONST8S: u8 = 0x0F;
21    pub const CONSTU: u8 = 0x10;
22    pub const CONSTS: u8 = 0x11;
23    pub const DUP: u8 = 0x12;
24    pub const DROP: u8 = 0x13;
25    pub const OVER: u8 = 0x14;
26    pub const PICK: u8 = 0x15;
27    pub const SWAP: u8 = 0x16;
28    pub const ROT: u8 = 0x17;
29    pub const ABS: u8 = 0x19;
30    pub const AND: u8 = 0x1A;
31    pub const DIV: u8 = 0x1B;
32    pub const MINUS: u8 = 0x1C;
33    pub const MOD: u8 = 0x1D;
34    pub const MUL: u8 = 0x1E;
35    pub const NEG: u8 = 0x1F;
36    pub const NOT: u8 = 0x20;
37    pub const OR: u8 = 0x21;
38    pub const PLUS: u8 = 0x22;
39    pub const PLUS_UCONST: u8 = 0x23;
40    pub const SHL: u8 = 0x24;
41    pub const SHR: u8 = 0x25;
42    pub const SHRA: u8 = 0x26;
43    pub const XOR: u8 = 0x27;
44    pub const LIT0: u8 = 0x30; // 0x30 - 0x4F = lit0-lit31
45    pub const REG0: u8 = 0x50; // 0x50 - 0x6F = reg0-reg31
46    pub const BREG0: u8 = 0x70; // 0x70 - 0x8F = breg0-breg31
47    pub const REGX: u8 = 0x90;
48    pub const FBREG: u8 = 0x91;
49    pub const BREGX: u8 = 0x92;
50    pub const DEREF_SIZE: u8 = 0x94;
51    pub const NOP: u8 = 0x96;
52}
53
54/// Evaluates a DWARF expression and returns the resulting value.
55///
56/// # Arguments
57/// * `expr` — The DWARF expression bytecode.
58/// * `regs` — Current register context.
59/// * `reader` — Memory reader for DW_OP_deref operations.
60/// * `is_64_bit` — Whether addresses are 64-bit.
61pub fn evaluate(
62    expr: &[u8],
63    regs: &RegisterContext,
64    reader: &dyn MemoryReader,
65    is_64_bit: bool,
66) -> Result<u64, UnwindError> {
67    let mut stack: Vec<u64> = Vec::new();
68    let mut cursor = ExprCursor::new(expr);
69
70    while cursor.remaining() > 0 {
71        let opcode = cursor.read_u8()?;
72
73        match opcode {
74            // Literal encodings: DW_OP_lit0 through DW_OP_lit31
75            op::LIT0..=0x4F => {
76                stack.push((opcode - op::LIT0) as u64);
77            }
78
79            // Register: DW_OP_reg0 through DW_OP_reg31
80            op::REG0..=0x6F => {
81                let reg = (opcode - op::REG0) as u16;
82                let val = regs
83                    .get(reg)
84                    .ok_or_else(|| UnwindError::InvalidDwarf(format!("reg{reg} not set")))?;
85                stack.push(val);
86            }
87
88            // Base register + offset: DW_OP_breg0 through DW_OP_breg31
89            op::BREG0..=0x8F => {
90                let reg = (opcode - op::BREG0) as u16;
91                let offset = cursor.read_sleb128()?;
92                let val = regs
93                    .get(reg)
94                    .ok_or_else(|| UnwindError::InvalidDwarf(format!("breg{reg} not set")))?;
95                stack.push(val.wrapping_add(offset as u64));
96            }
97
98            op::ADDR => {
99                let addr = if is_64_bit {
100                    cursor.read_u64()?
101                } else {
102                    cursor.read_u32()? as u64
103                };
104                stack.push(addr);
105            }
106
107            op::CONST1U => {
108                let val = cursor.read_u8()? as u64;
109                stack.push(val);
110            }
111            op::CONST1S => {
112                let val = cursor.read_u8()? as i8 as i64 as u64;
113                stack.push(val);
114            }
115            op::CONST2U => {
116                let val = cursor.read_u16()? as u64;
117                stack.push(val);
118            }
119            op::CONST2S => {
120                let val = cursor.read_u16()? as i16 as i64 as u64;
121                stack.push(val);
122            }
123            op::CONST4U => {
124                let val = cursor.read_u32()? as u64;
125                stack.push(val);
126            }
127            op::CONST4S => {
128                let val = cursor.read_u32()? as i32 as i64 as u64;
129                stack.push(val);
130            }
131            op::CONST8U => {
132                let val = cursor.read_u64()?;
133                stack.push(val);
134            }
135            op::CONST8S => {
136                let val = cursor.read_u64()?;
137                stack.push(val);
138            }
139            op::CONSTU => {
140                let val = cursor.read_uleb128()?;
141                stack.push(val);
142            }
143            op::CONSTS => {
144                let val = cursor.read_sleb128()? as u64;
145                stack.push(val);
146            }
147
148            // Stack operations
149            op::DUP => {
150                let val = *stack
151                    .last()
152                    .ok_or(UnwindError::InvalidDwarf("DUP on empty stack".into()))?;
153                stack.push(val);
154            }
155            op::DROP => {
156                stack
157                    .pop()
158                    .ok_or(UnwindError::InvalidDwarf("DROP on empty stack".into()))?;
159            }
160            op::OVER => {
161                if stack.len() < 2 {
162                    return Err(UnwindError::InvalidDwarf("OVER needs 2 values".into()));
163                }
164                let val = stack[stack.len() - 2];
165                stack.push(val);
166            }
167            op::PICK => {
168                let idx = cursor.read_u8()? as usize;
169                if idx >= stack.len() {
170                    return Err(UnwindError::InvalidDwarf("PICK index out of range".into()));
171                }
172                let val = stack[stack.len() - 1 - idx];
173                stack.push(val);
174            }
175            op::SWAP => {
176                if stack.len() < 2 {
177                    return Err(UnwindError::InvalidDwarf("SWAP needs 2 values".into()));
178                }
179                let len = stack.len();
180                stack.swap(len - 1, len - 2);
181            }
182            op::ROT => {
183                if stack.len() < 3 {
184                    return Err(UnwindError::InvalidDwarf("ROT needs 3 values".into()));
185                }
186                let len = stack.len();
187                let top = stack[len - 1];
188                stack[len - 1] = stack[len - 2];
189                stack[len - 2] = stack[len - 3];
190                stack[len - 3] = top;
191            }
192
193            // Memory operations
194            op::DEREF => {
195                let addr = stack
196                    .pop()
197                    .ok_or(UnwindError::InvalidDwarf("DEREF on empty stack".into()))?;
198                let val = reader
199                    .read_pointer(addr, is_64_bit)
200                    .ok_or(UnwindError::MemoryReadFailed(addr))?;
201                stack.push(val);
202            }
203            op::DEREF_SIZE => {
204                let size = cursor.read_u8()?;
205                let addr = stack.pop().ok_or(UnwindError::InvalidDwarf(
206                    "DEREF_SIZE on empty stack".into(),
207                ))?;
208                let val = match size {
209                    1 => reader.read_u8(addr).map(|v| v as u64),
210                    2 => reader.read_u16(addr).map(|v| v as u64),
211                    4 => reader.read_u32(addr).map(|v| v as u64),
212                    8 => reader.read_u64(addr),
213                    _ => None,
214                }
215                .ok_or(UnwindError::MemoryReadFailed(addr))?;
216                stack.push(val);
217            }
218
219            // Arithmetic
220            op::ABS => {
221                let val = stack
222                    .pop()
223                    .ok_or(UnwindError::InvalidDwarf("ABS on empty stack".into()))?;
224                stack.push((val as i64).unsigned_abs());
225            }
226            op::AND => {
227                let (b, a) = pop_two(&mut stack, "AND")?;
228                stack.push(a & b);
229            }
230            op::DIV => {
231                let (b, a) = pop_two(&mut stack, "DIV")?;
232                if b == 0 {
233                    return Err(UnwindError::InvalidDwarf("DIV by zero".into()));
234                }
235                stack.push(((a as i64) / (b as i64)) as u64);
236            }
237            op::MINUS => {
238                let (b, a) = pop_two(&mut stack, "MINUS")?;
239                stack.push(a.wrapping_sub(b));
240            }
241            op::MOD => {
242                let (b, a) = pop_two(&mut stack, "MOD")?;
243                if b == 0 {
244                    return Err(UnwindError::InvalidDwarf("MOD by zero".into()));
245                }
246                stack.push(a % b);
247            }
248            op::MUL => {
249                let (b, a) = pop_two(&mut stack, "MUL")?;
250                stack.push(a.wrapping_mul(b));
251            }
252            op::NEG => {
253                let val = stack
254                    .pop()
255                    .ok_or(UnwindError::InvalidDwarf("NEG on empty stack".into()))?;
256                stack.push((-(val as i64)) as u64);
257            }
258            op::NOT => {
259                let val = stack
260                    .pop()
261                    .ok_or(UnwindError::InvalidDwarf("NOT on empty stack".into()))?;
262                stack.push(!val);
263            }
264            op::OR => {
265                let (b, a) = pop_two(&mut stack, "OR")?;
266                stack.push(a | b);
267            }
268            op::PLUS => {
269                let (b, a) = pop_two(&mut stack, "PLUS")?;
270                stack.push(a.wrapping_add(b));
271            }
272            op::PLUS_UCONST => {
273                let val = stack.pop().ok_or(UnwindError::InvalidDwarf(
274                    "PLUS_UCONST on empty stack".into(),
275                ))?;
276                let addend = cursor.read_uleb128()?;
277                stack.push(val.wrapping_add(addend));
278            }
279            op::SHL => {
280                let (b, a) = pop_two(&mut stack, "SHL")?;
281                stack.push(a.wrapping_shl(b as u32));
282            }
283            op::SHR => {
284                let (b, a) = pop_two(&mut stack, "SHR")?;
285                stack.push(a.wrapping_shr(b as u32));
286            }
287            op::SHRA => {
288                let (b, a) = pop_two(&mut stack, "SHRA")?;
289                stack.push(((a as i64).wrapping_shr(b as u32)) as u64);
290            }
291            op::XOR => {
292                let (b, a) = pop_two(&mut stack, "XOR")?;
293                stack.push(a ^ b);
294            }
295
296            // Register indirect
297            op::REGX => {
298                let reg = cursor.read_uleb128()? as u16;
299                let val = regs
300                    .get(reg)
301                    .ok_or_else(|| UnwindError::InvalidDwarf(format!("regx({reg}) not set")))?;
302                stack.push(val);
303            }
304            op::BREGX => {
305                let reg = cursor.read_uleb128()? as u16;
306                let offset = cursor.read_sleb128()?;
307                let val = regs
308                    .get(reg)
309                    .ok_or_else(|| UnwindError::InvalidDwarf(format!("bregx({reg}) not set")))?;
310                stack.push(val.wrapping_add(offset as u64));
311            }
312            op::FBREG => {
313                // Frame base register — use FP as the frame base
314                let offset = cursor.read_sleb128()?;
315                let fp = regs
316                    .fp()
317                    .ok_or_else(|| UnwindError::InvalidDwarf("fbreg: no FP".into()))?;
318                stack.push(fp.wrapping_add(offset as u64));
319            }
320
321            op::NOP => {}
322
323            _ => {
324                return Err(UnwindError::InvalidDwarf(format!(
325                    "unsupported DW_OP 0x{opcode:02x}"
326                )));
327            }
328        }
329    }
330
331    stack
332        .last()
333        .copied()
334        .ok_or_else(|| UnwindError::InvalidDwarf("expression produced empty stack".into()))
335}
336
337fn pop_two(stack: &mut Vec<u64>, op_name: &str) -> Result<(u64, u64), UnwindError> {
338    if stack.len() < 2 {
339        return Err(UnwindError::InvalidDwarf(format!(
340            "{op_name} needs 2 values"
341        )));
342    }
343    let b = stack.pop().unwrap();
344    let a = stack.pop().unwrap();
345    Ok((b, a))
346}
347
348/// Cursor for reading bytes from a DWARF expression.
349struct ExprCursor<'a> {
350    data: &'a [u8],
351    pos: usize,
352}
353
354impl<'a> ExprCursor<'a> {
355    fn new(data: &'a [u8]) -> Self {
356        Self { data, pos: 0 }
357    }
358
359    fn remaining(&self) -> usize {
360        self.data.len() - self.pos
361    }
362
363    fn read_u8(&mut self) -> Result<u8, UnwindError> {
364        if self.pos >= self.data.len() {
365            return Err(UnwindError::InvalidDwarf(
366                "unexpected end of expression".into(),
367            ));
368        }
369        let val = self.data[self.pos];
370        self.pos += 1;
371        Ok(val)
372    }
373
374    fn read_u16(&mut self) -> Result<u16, UnwindError> {
375        if self.pos + 2 > self.data.len() {
376            return Err(UnwindError::InvalidDwarf(
377                "unexpected end of expression".into(),
378            ));
379        }
380        let val = u16::from_le_bytes([self.data[self.pos], self.data[self.pos + 1]]);
381        self.pos += 2;
382        Ok(val)
383    }
384
385    fn read_u32(&mut self) -> Result<u32, UnwindError> {
386        if self.pos + 4 > self.data.len() {
387            return Err(UnwindError::InvalidDwarf(
388                "unexpected end of expression".into(),
389            ));
390        }
391        let val = u32::from_le_bytes([
392            self.data[self.pos],
393            self.data[self.pos + 1],
394            self.data[self.pos + 2],
395            self.data[self.pos + 3],
396        ]);
397        self.pos += 4;
398        Ok(val)
399    }
400
401    fn read_u64(&mut self) -> Result<u64, UnwindError> {
402        if self.pos + 8 > self.data.len() {
403            return Err(UnwindError::InvalidDwarf(
404                "unexpected end of expression".into(),
405            ));
406        }
407        let val = u64::from_le_bytes([
408            self.data[self.pos],
409            self.data[self.pos + 1],
410            self.data[self.pos + 2],
411            self.data[self.pos + 3],
412            self.data[self.pos + 4],
413            self.data[self.pos + 5],
414            self.data[self.pos + 6],
415            self.data[self.pos + 7],
416        ]);
417        self.pos += 8;
418        Ok(val)
419    }
420
421    fn read_uleb128(&mut self) -> Result<u64, UnwindError> {
422        let mut result = 0u64;
423        let mut shift = 0;
424        loop {
425            let byte = self.read_u8()?;
426            result |= ((byte & 0x7F) as u64) << shift;
427            if byte & 0x80 == 0 {
428                return Ok(result);
429            }
430            shift += 7;
431            if shift >= 64 {
432                return Err(UnwindError::InvalidDwarf("ULEB128 overflow".into()));
433            }
434        }
435    }
436
437    fn read_sleb128(&mut self) -> Result<i64, UnwindError> {
438        let mut result = 0i64;
439        let mut shift = 0;
440        let mut byte;
441        loop {
442            byte = self.read_u8()?;
443            result |= ((byte & 0x7F) as i64) << shift;
444            shift += 7;
445            if byte & 0x80 == 0 {
446                break;
447            }
448            if shift >= 64 {
449                return Err(UnwindError::InvalidDwarf("SLEB128 overflow".into()));
450            }
451        }
452        // Sign extend
453        if shift < 64 && (byte & 0x40) != 0 {
454            result |= !0i64 << shift;
455        }
456        Ok(result)
457    }
458}
459
460// Also export LEB128 readers for use in dwarf_cfi
461pub fn read_uleb128(data: &[u8], pos: &mut usize) -> Result<u64, UnwindError> {
462    let mut result = 0u64;
463    let mut shift = 0;
464    loop {
465        if *pos >= data.len() {
466            return Err(UnwindError::InvalidDwarf("ULEB128 past end".into()));
467        }
468        let byte = data[*pos];
469        *pos += 1;
470        result |= ((byte & 0x7F) as u64) << shift;
471        if byte & 0x80 == 0 {
472            return Ok(result);
473        }
474        shift += 7;
475        if shift >= 64 {
476            return Err(UnwindError::InvalidDwarf("ULEB128 overflow".into()));
477        }
478    }
479}
480
481pub fn read_sleb128(data: &[u8], pos: &mut usize) -> Result<i64, UnwindError> {
482    let mut result = 0i64;
483    let mut shift = 0;
484    let mut byte;
485    loop {
486        if *pos >= data.len() {
487            return Err(UnwindError::InvalidDwarf("SLEB128 past end".into()));
488        }
489        byte = data[*pos];
490        *pos += 1;
491        result |= ((byte & 0x7F) as i64) << shift;
492        shift += 7;
493        if byte & 0x80 == 0 {
494            break;
495        }
496        if shift >= 64 {
497            return Err(UnwindError::InvalidDwarf("SLEB128 overflow".into()));
498        }
499    }
500    if shift < 64 && (byte & 0x40) != 0 {
501        result |= !0i64 << shift;
502    }
503    Ok(result)
504}
505
506#[cfg(test)]
507mod tests {
508    use super::*;
509    use crate::types::CpuType;
510    use crate::unwind::SliceMemoryReader;
511
512    fn make_reader() -> SliceMemoryReader {
513        let mut data = vec![0u8; 256];
514        // Put a known value at address 0x1080
515        data[0x80..0x88].copy_from_slice(&0xDEAD_BEEF_CAFE_BABEu64.to_le_bytes());
516        SliceMemoryReader {
517            data,
518            base_address: 0x1000,
519        }
520    }
521
522    fn make_regs() -> RegisterContext {
523        let mut regs = RegisterContext::new(CpuType::ARM64);
524        regs.set(0, 100); // x0
525        regs.set(29, 0x1080); // fp
526        regs.set(31, 0x2000); // sp
527        regs
528    }
529
530    #[test]
531    fn lit_values() {
532        let reader = make_reader();
533        let regs = make_regs();
534        // DW_OP_lit5
535        assert_eq!(evaluate(&[0x35], &regs, &reader, true).unwrap(), 5);
536        // DW_OP_lit0
537        assert_eq!(evaluate(&[0x30], &regs, &reader, true).unwrap(), 0);
538        // DW_OP_lit31
539        assert_eq!(evaluate(&[0x4F], &regs, &reader, true).unwrap(), 31);
540    }
541
542    #[test]
543    fn const_u_s() {
544        let reader = make_reader();
545        let regs = make_regs();
546        // DW_OP_const1u 42
547        assert_eq!(evaluate(&[0x08, 42], &regs, &reader, true).unwrap(), 42);
548        // DW_OP_const1s -1 (0xFF)
549        assert_eq!(
550            evaluate(&[0x09, 0xFF], &regs, &reader, true).unwrap(),
551            (-1i64) as u64
552        );
553    }
554
555    #[test]
556    fn breg_fp_offset() {
557        let reader = make_reader();
558        let regs = make_regs();
559        // DW_OP_breg29(0) = FP value = 0x1080
560        // breg29 = 0x70 + 29 = 0x8D, offset 0 as SLEB128
561        assert_eq!(
562            evaluate(&[0x8D, 0x00], &regs, &reader, true).unwrap(),
563            0x1080
564        );
565    }
566
567    #[test]
568    fn deref() {
569        let reader = make_reader();
570        let regs = make_regs();
571        // DW_OP_breg29(0), DW_OP_deref = read 8 bytes from FP (0x1080)
572        assert_eq!(
573            evaluate(&[0x8D, 0x00, op::DEREF], &regs, &reader, true).unwrap(),
574            0xDEAD_BEEF_CAFE_BABE
575        );
576    }
577
578    #[test]
579    fn arithmetic_plus() {
580        let reader = make_reader();
581        let regs = make_regs();
582        // DW_OP_lit5, DW_OP_lit3, DW_OP_plus = 8
583        assert_eq!(
584            evaluate(&[0x35, 0x33, op::PLUS], &regs, &reader, true).unwrap(),
585            8
586        );
587    }
588
589    #[test]
590    fn plus_uconst() {
591        let reader = make_reader();
592        let regs = make_regs();
593        // DW_OP_lit10, DW_OP_plus_uconst 20 = 30
594        assert_eq!(
595            evaluate(&[0x3A, op::PLUS_UCONST, 20], &regs, &reader, true).unwrap(),
596            30
597        );
598    }
599
600    #[test]
601    fn stack_operations() {
602        let reader = make_reader();
603        let regs = make_regs();
604        // DW_OP_lit1, DW_OP_lit2, DW_OP_swap, result = 1 (was top after swap)
605        // Stack: [1, 2] → swap → [2, 1], top = 1
606        assert_eq!(
607            evaluate(&[0x31, 0x32, op::SWAP], &regs, &reader, true).unwrap(),
608            1
609        );
610    }
611
612    #[test]
613    fn uleb128_encoding() {
614        // Test multi-byte ULEB128
615        let mut pos = 0;
616        let data = [0x80, 0x01]; // 128
617        assert_eq!(read_uleb128(&data, &mut pos).unwrap(), 128);
618        assert_eq!(pos, 2);
619    }
620
621    #[test]
622    fn sleb128_encoding() {
623        // Test negative SLEB128
624        let mut pos = 0;
625        let data = [0x7F]; // -1
626        assert_eq!(read_sleb128(&data, &mut pos).unwrap(), -1);
627    }
628
629    #[test]
630    fn empty_expression_error() {
631        let reader = make_reader();
632        let regs = make_regs();
633        assert!(evaluate(&[], &regs, &reader, true).is_err());
634    }
635}
crashrustler/unwind/dwarf_expr.rs

crashrustler/unwind/
dwarf_expr.rs
