1 #![allow(trivial_numeric_casts)] 2 3 use super::address_transform::AddressTransform; 4 use crate::debug::ModuleMemoryOffset; 5 use crate::translate::get_vmctx_value_label; 6 use anyhow::{Context, Error, Result}; 7 use cranelift_codegen::ir::ValueLabel; 8 use cranelift_codegen::isa::TargetIsa; 9 use cranelift_codegen::LabelValueLoc; 10 use cranelift_codegen::ValueLabelsRanges; 11 use gimli::{write, Expression, Operation, Reader, ReaderOffset}; 12 use std::cmp::PartialEq; 13 use std::collections::{HashMap, HashSet}; 14 use std::hash::{Hash, Hasher}; 15 use std::rc::Rc; 16 17 #[derive(Debug)] 18 pub struct FunctionFrameInfo<'a> { 19 pub value_ranges: &'a ValueLabelsRanges, 20 pub memory_offset: ModuleMemoryOffset, 21 } 22 23 struct ExpressionWriter(write::EndianVec<gimli::RunTimeEndian>); 24 25 enum VmctxBase { 26 Reg(u16), 27 OnStack, 28 } 29 30 impl ExpressionWriter { 31 fn new() -> Self { 32 let endian = gimli::RunTimeEndian::Little; 33 let writer = write::EndianVec::new(endian); 34 ExpressionWriter(writer) 35 } 36 37 fn write_op(&mut self, op: gimli::DwOp) -> write::Result<()> { 38 self.write_u8(op.0) 39 } 40 41 fn write_op_reg(&mut self, reg: u16) -> write::Result<()> { 42 if reg < 32 { 43 self.write_u8(gimli::constants::DW_OP_reg0.0 + reg as u8) 44 } else { 45 self.write_op(gimli::constants::DW_OP_regx)?; 46 self.write_uleb128(reg.into()) 47 } 48 } 49 50 fn write_op_breg(&mut self, reg: u16) -> write::Result<()> { 51 if reg < 32 { 52 self.write_u8(gimli::constants::DW_OP_breg0.0 + reg as u8) 53 } else { 54 self.write_op(gimli::constants::DW_OP_bregx)?; 55 self.write_uleb128(reg.into()) 56 } 57 } 58 59 fn write_u8(&mut self, b: u8) -> write::Result<()> { 60 write::Writer::write_u8(&mut self.0, b) 61 } 62 63 fn write_u32(&mut self, b: u32) -> write::Result<()> { 64 write::Writer::write_u32(&mut self.0, b) 65 } 66 67 fn write_uleb128(&mut self, i: u64) -> write::Result<()> { 68 write::Writer::write_uleb128(&mut self.0, i) 69 } 70 71 fn write_sleb128(&mut self, i: i64) -> write::Result<()> { 72 write::Writer::write_sleb128(&mut self.0, i) 73 } 74 75 fn into_vec(self) -> Vec<u8> { 76 self.0.into_vec() 77 } 78 79 fn gen_address_of_memory_base_pointer( 80 &mut self, 81 vmctx: VmctxBase, 82 memory_base: &ModuleMemoryOffset, 83 ) -> write::Result<()> { 84 match *memory_base { 85 ModuleMemoryOffset::Defined(offset) => match vmctx { 86 VmctxBase::Reg(reg) => { 87 self.write_op_breg(reg)?; 88 self.write_sleb128(offset.into())?; 89 } 90 VmctxBase::OnStack => { 91 self.write_op(gimli::constants::DW_OP_consts)?; 92 self.write_sleb128(offset.into())?; 93 self.write_op(gimli::constants::DW_OP_plus)?; 94 } 95 }, 96 ModuleMemoryOffset::Imported { 97 offset_to_vm_memory_definition, 98 offset_to_memory_base, 99 } => { 100 match vmctx { 101 VmctxBase::Reg(reg) => { 102 self.write_op_breg(reg)?; 103 self.write_sleb128(offset_to_vm_memory_definition.into())?; 104 } 105 VmctxBase::OnStack => { 106 if offset_to_vm_memory_definition > 0 { 107 self.write_op(gimli::constants::DW_OP_consts)?; 108 self.write_sleb128(offset_to_vm_memory_definition.into())?; 109 } 110 self.write_op(gimli::constants::DW_OP_plus)?; 111 } 112 } 113 self.write_op(gimli::constants::DW_OP_deref)?; 114 if offset_to_memory_base > 0 { 115 self.write_op(gimli::constants::DW_OP_consts)?; 116 self.write_sleb128(offset_to_memory_base.into())?; 117 self.write_op(gimli::constants::DW_OP_plus)?; 118 } 119 } 120 ModuleMemoryOffset::None => return Err(write::Error::InvalidAttributeValue), 121 } 122 Ok(()) 123 } 124 } 125 126 #[derive(Debug, Clone, PartialEq)] 127 enum CompiledExpressionPart { 128 // Untranslated DWARF expression. 129 Code(Vec<u8>), 130 // The wasm-local DWARF operator. The label points to `ValueLabel`. 131 // The trailing field denotes that the operator was last in sequence, 132 // and it is the DWARF location (not a pointer). 133 Local { 134 label: ValueLabel, 135 trailing: bool, 136 }, 137 // Dereference is needed. 138 Deref, 139 // Jumping in the expression. 140 Jump { 141 conditionally: bool, 142 target: JumpTargetMarker, 143 }, 144 // Floating landing pad. 145 LandingPad(JumpTargetMarker), 146 } 147 148 #[derive(Debug, Clone, PartialEq)] 149 pub struct CompiledExpression { 150 parts: Vec<CompiledExpressionPart>, 151 need_deref: bool, 152 } 153 154 impl CompiledExpression { 155 pub fn vmctx() -> CompiledExpression { 156 CompiledExpression::from_label(get_vmctx_value_label()) 157 } 158 159 pub fn from_label(label: ValueLabel) -> CompiledExpression { 160 CompiledExpression { 161 parts: vec![CompiledExpressionPart::Local { 162 label, 163 trailing: true, 164 }], 165 need_deref: false, 166 } 167 } 168 } 169 170 fn translate_loc( 171 loc: LabelValueLoc, 172 isa: &dyn TargetIsa, 173 add_stack_value: bool, 174 ) -> Result<Option<Vec<u8>>> { 175 Ok(match loc { 176 LabelValueLoc::Reg(r) => { 177 let machine_reg = isa.map_regalloc_reg_to_dwarf(r)?; 178 let mut writer = ExpressionWriter::new(); 179 if add_stack_value { 180 writer.write_op_reg(machine_reg)?; 181 } else { 182 writer.write_op_breg(machine_reg)?; 183 writer.write_sleb128(0)?; 184 } 185 Some(writer.into_vec()) 186 } 187 LabelValueLoc::CFAOffset(off) => { 188 let mut writer = ExpressionWriter::new(); 189 writer.write_op(gimli::constants::DW_OP_fbreg)?; 190 writer.write_sleb128(off)?; 191 if !add_stack_value { 192 writer.write_op(gimli::constants::DW_OP_deref)?; 193 } 194 return Ok(Some(writer.into_vec())); 195 } 196 }) 197 } 198 199 fn append_memory_deref( 200 buf: &mut Vec<u8>, 201 frame_info: &FunctionFrameInfo, 202 vmctx_loc: LabelValueLoc, 203 isa: &dyn TargetIsa, 204 ) -> Result<bool> { 205 let mut writer = ExpressionWriter::new(); 206 let vmctx_base = match vmctx_loc { 207 LabelValueLoc::Reg(r) => VmctxBase::Reg(isa.map_regalloc_reg_to_dwarf(r)?), 208 LabelValueLoc::CFAOffset(off) => { 209 writer.write_op(gimli::constants::DW_OP_fbreg)?; 210 writer.write_sleb128(off)?; 211 writer.write_op(gimli::constants::DW_OP_deref)?; 212 VmctxBase::OnStack 213 } 214 }; 215 writer.gen_address_of_memory_base_pointer(vmctx_base, &frame_info.memory_offset)?; 216 writer.write_op(gimli::constants::DW_OP_deref)?; 217 writer.write_op(gimli::constants::DW_OP_swap)?; 218 writer.write_op(gimli::constants::DW_OP_const4u)?; 219 writer.write_u32(0xffff_ffff)?; 220 writer.write_op(gimli::constants::DW_OP_and)?; 221 writer.write_op(gimli::constants::DW_OP_plus)?; 222 buf.extend(writer.into_vec()); 223 Ok(true) 224 } 225 226 impl CompiledExpression { 227 pub fn is_simple(&self) -> bool { 228 if let [CompiledExpressionPart::Code(_)] = self.parts.as_slice() { 229 true 230 } else { 231 self.parts.is_empty() 232 } 233 } 234 235 pub fn build(&self) -> Option<write::Expression> { 236 if let [CompiledExpressionPart::Code(code)] = self.parts.as_slice() { 237 return Some(write::Expression::raw(code.to_vec())); 238 } 239 // locals found, not supported 240 None 241 } 242 243 pub fn build_with_locals<'a>( 244 &'a self, 245 scope: &'a [(u64, u64)], // wasm ranges 246 addr_tr: &'a AddressTransform, 247 frame_info: Option<&'a FunctionFrameInfo>, 248 isa: &'a dyn TargetIsa, 249 ) -> impl Iterator<Item = Result<(write::Address, u64, write::Expression)>> + 'a { 250 enum BuildWithLocalsResult<'a> { 251 Empty, 252 Simple( 253 Box<dyn Iterator<Item = (write::Address, u64)> + 'a>, 254 Vec<u8>, 255 ), 256 Ranges(Box<dyn Iterator<Item = Result<(usize, usize, usize, Vec<u8>)>> + 'a>), 257 } 258 impl Iterator for BuildWithLocalsResult<'_> { 259 type Item = Result<(write::Address, u64, write::Expression)>; 260 fn next(&mut self) -> Option<Self::Item> { 261 match self { 262 BuildWithLocalsResult::Empty => None, 263 BuildWithLocalsResult::Simple(it, code) => it 264 .next() 265 .map(|(addr, len)| Ok((addr, len, write::Expression::raw(code.to_vec())))), 266 BuildWithLocalsResult::Ranges(it) => it.next().map(|r| { 267 r.map(|(symbol, start, end, code_buf)| { 268 ( 269 write::Address::Symbol { 270 symbol, 271 addend: start as i64, 272 }, 273 (end - start) as u64, 274 write::Expression::raw(code_buf), 275 ) 276 }) 277 }), 278 } 279 } 280 } 281 282 if scope.is_empty() { 283 return BuildWithLocalsResult::Empty; 284 } 285 286 // If it a simple DWARF code, no need in locals processing. Just translate 287 // the scope ranges. 288 if let [CompiledExpressionPart::Code(code)] = self.parts.as_slice() { 289 return BuildWithLocalsResult::Simple( 290 Box::new(scope.iter().flat_map(move |(wasm_start, wasm_end)| { 291 addr_tr.translate_ranges(*wasm_start, *wasm_end) 292 })), 293 code.clone(), 294 ); 295 } 296 297 let vmctx_label = get_vmctx_value_label(); 298 299 // Some locals are present, preparing and divided ranges based on the scope 300 // and frame_info data. 301 let mut ranges_builder = ValueLabelRangesBuilder::new(scope, addr_tr, frame_info); 302 for p in self.parts.iter() { 303 match p { 304 CompiledExpressionPart::Code(_) 305 | CompiledExpressionPart::Jump { .. } 306 | CompiledExpressionPart::LandingPad { .. } => (), 307 CompiledExpressionPart::Local { label, .. } => ranges_builder.process_label(*label), 308 CompiledExpressionPart::Deref => ranges_builder.process_label(vmctx_label), 309 } 310 } 311 if self.need_deref { 312 ranges_builder.process_label(vmctx_label); 313 } 314 let ranges = ranges_builder.into_ranges(); 315 316 return BuildWithLocalsResult::Ranges(Box::new( 317 ranges 318 .into_iter() 319 .map( 320 move |CachedValueLabelRange { 321 func_index, 322 start, 323 end, 324 label_location, 325 }| { 326 // build expression 327 let mut code_buf = Vec::new(); 328 let mut jump_positions = Vec::new(); 329 let mut landing_positions = HashMap::new(); 330 331 macro_rules! deref { 332 () => { 333 if let (Some(vmctx_loc), Some(frame_info)) = 334 (label_location.get(&vmctx_label), frame_info) 335 { 336 if !append_memory_deref( 337 &mut code_buf, 338 frame_info, 339 *vmctx_loc, 340 isa, 341 )? { 342 return Ok(None); 343 } 344 } else { 345 return Ok(None); 346 } 347 }; 348 } 349 for part in &self.parts { 350 match part { 351 CompiledExpressionPart::Code(c) => { 352 code_buf.extend_from_slice(c.as_slice()) 353 } 354 CompiledExpressionPart::LandingPad(marker) => { 355 landing_positions.insert(marker.clone(), code_buf.len()); 356 } 357 CompiledExpressionPart::Jump { 358 conditionally, 359 target, 360 } => { 361 code_buf.push( 362 match conditionally { 363 true => gimli::constants::DW_OP_bra, 364 false => gimli::constants::DW_OP_skip, 365 } 366 .0, 367 ); 368 code_buf.push(!0); 369 code_buf.push(!0); // these will be relocated below 370 jump_positions.push((target.clone(), code_buf.len())); 371 } 372 CompiledExpressionPart::Local { label, trailing } => { 373 let loc = 374 *label_location.get(&label).context("label_location")?; 375 if let Some(expr) = translate_loc(loc, isa, *trailing)? { 376 code_buf.extend_from_slice(&expr) 377 } else { 378 return Ok(None); 379 } 380 } 381 CompiledExpressionPart::Deref => deref!(), 382 } 383 } 384 if self.need_deref { 385 deref!(); 386 } 387 388 for (marker, new_from) in jump_positions { 389 // relocate jump targets 390 let new_to = landing_positions[&marker]; 391 let new_diff = new_to as isize - new_from as isize; 392 // FIXME: use encoding? LittleEndian for now... 393 code_buf[new_from - 2..new_from] 394 .copy_from_slice(&(new_diff as i16).to_le_bytes()); 395 } 396 Ok(Some((func_index, start, end, code_buf))) 397 }, 398 ) 399 .filter_map(Result::transpose), 400 )); 401 } 402 } 403 404 fn is_old_expression_format(buf: &[u8]) -> bool { 405 // Heuristic to detect old variable expression format without DW_OP_fbreg: 406 // DW_OP_plus_uconst op must be present, but not DW_OP_fbreg. 407 if buf.contains(&(gimli::constants::DW_OP_fbreg.0)) { 408 // Stop check if DW_OP_fbreg exist. 409 return false; 410 } 411 buf.contains(&(gimli::constants::DW_OP_plus_uconst.0)) 412 } 413 414 pub fn compile_expression<R>( 415 expr: &Expression<R>, 416 encoding: gimli::Encoding, 417 frame_base: Option<&CompiledExpression>, 418 ) -> Result<Option<CompiledExpression>, Error> 419 where 420 R: Reader, 421 { 422 // Bail when `frame_base` is complicated. 423 if let Some(expr) = frame_base { 424 if expr.parts.iter().any(|p| match p { 425 CompiledExpressionPart::Jump { .. } => true, 426 _ => false, 427 }) { 428 return Ok(None); 429 } 430 } 431 432 // jump_targets key is offset in buf starting from the end 433 // (see also `unread_bytes` below) 434 let mut jump_targets: HashMap<u64, JumpTargetMarker> = HashMap::new(); 435 let mut pc = expr.0.clone(); 436 437 let buf = expr.0.to_slice()?; 438 let mut parts = Vec::new(); 439 macro_rules! push { 440 ($part:expr) => {{ 441 let part = $part; 442 if let (CompiledExpressionPart::Code(cc2), Some(CompiledExpressionPart::Code(cc1))) = 443 (&part, parts.last_mut()) 444 { 445 cc1.extend_from_slice(cc2); 446 } else { 447 parts.push(part) 448 } 449 }}; 450 } 451 let mut need_deref = false; 452 if is_old_expression_format(&buf) && frame_base.is_some() { 453 // Still supporting old DWARF variable expressions without fbreg. 454 parts.extend_from_slice(&frame_base.unwrap().parts); 455 if let Some(CompiledExpressionPart::Local { trailing, .. }) = parts.last_mut() { 456 *trailing = false; 457 } 458 need_deref = frame_base.unwrap().need_deref; 459 } 460 let mut code_chunk = Vec::new(); 461 macro_rules! flush_code_chunk { 462 () => { 463 if !code_chunk.is_empty() { 464 push!(CompiledExpressionPart::Code(code_chunk)); 465 code_chunk = Vec::new(); 466 let _ = code_chunk; // suppresses warning for final flush 467 } 468 }; 469 } 470 471 // Find all landing pads by scanning bytes, do not care about 472 // false location at this moment. 473 // Looks hacky but it is fast; does not need to be really exact. 474 if buf.len() > 2 { 475 for i in 0..buf.len() - 2 { 476 let op = buf[i]; 477 if op == gimli::constants::DW_OP_bra.0 || op == gimli::constants::DW_OP_skip.0 { 478 // TODO fix for big-endian 479 let offset = i16::from_le_bytes([buf[i + 1], buf[i + 2]]); 480 let origin = i + 3; 481 // Discarding out-of-bounds jumps (also some of falsely detected ops) 482 if (offset >= 0 && offset as usize + origin <= buf.len()) 483 || (offset < 0 && -offset as usize <= origin) 484 { 485 let target = buf.len() as isize - origin as isize - offset as isize; 486 jump_targets.insert(target as u64, JumpTargetMarker::new()); 487 } 488 } 489 } 490 } 491 492 while !pc.is_empty() { 493 let unread_bytes = pc.len().into_u64(); 494 if let Some(marker) = jump_targets.get(&unread_bytes) { 495 flush_code_chunk!(); 496 parts.push(CompiledExpressionPart::LandingPad(marker.clone())); 497 } 498 499 need_deref = true; 500 501 let pos = pc.offset_from(&expr.0).into_u64() as usize; 502 let op = Operation::parse(&mut pc, encoding)?; 503 match op { 504 Operation::FrameOffset { offset } => { 505 // Expand DW_OP_fbreg into frame location and DW_OP_plus_uconst. 506 if frame_base.is_some() { 507 // Add frame base expressions. 508 flush_code_chunk!(); 509 parts.extend_from_slice(&frame_base.unwrap().parts); 510 } 511 if let Some(CompiledExpressionPart::Local { trailing, .. }) = parts.last_mut() { 512 // Reset local trailing flag. 513 *trailing = false; 514 } 515 // Append DW_OP_plus_uconst part. 516 let mut writer = ExpressionWriter::new(); 517 writer.write_op(gimli::constants::DW_OP_plus_uconst)?; 518 writer.write_uleb128(offset as u64)?; 519 code_chunk.extend(writer.into_vec()); 520 continue; 521 } 522 Operation::Drop { .. } 523 | Operation::Pick { .. } 524 | Operation::Swap { .. } 525 | Operation::Rot { .. } 526 | Operation::Nop { .. } 527 | Operation::UnsignedConstant { .. } 528 | Operation::SignedConstant { .. } 529 | Operation::ConstantIndex { .. } 530 | Operation::PlusConstant { .. } 531 | Operation::Abs { .. } 532 | Operation::And { .. } 533 | Operation::Or { .. } 534 | Operation::Xor { .. } 535 | Operation::Shl { .. } 536 | Operation::Plus { .. } 537 | Operation::Minus { .. } 538 | Operation::Div { .. } 539 | Operation::Mod { .. } 540 | Operation::Mul { .. } 541 | Operation::Neg { .. } 542 | Operation::Not { .. } 543 | Operation::Lt { .. } 544 | Operation::Gt { .. } 545 | Operation::Le { .. } 546 | Operation::Ge { .. } 547 | Operation::Eq { .. } 548 | Operation::Ne { .. } 549 | Operation::TypedLiteral { .. } 550 | Operation::Convert { .. } 551 | Operation::Reinterpret { .. } 552 | Operation::Piece { .. } => (), 553 Operation::Bra { target } | Operation::Skip { target } => { 554 flush_code_chunk!(); 555 let arc_to = (pc.len().into_u64() as isize - target as isize) as u64; 556 let marker = match jump_targets.get(&arc_to) { 557 Some(m) => m.clone(), 558 None => { 559 // Marker not found: probably out of bounds. 560 return Ok(None); 561 } 562 }; 563 push!(CompiledExpressionPart::Jump { 564 conditionally: match op { 565 Operation::Bra { .. } => true, 566 _ => false, 567 }, 568 target: marker, 569 }); 570 continue; 571 } 572 Operation::StackValue => { 573 need_deref = false; 574 575 // Find extra stack_value, that follow wasm-local operators, 576 // and mark such locals with special flag. 577 if let (Some(CompiledExpressionPart::Local { trailing, .. }), true) = 578 (parts.last_mut(), code_chunk.is_empty()) 579 { 580 *trailing = true; 581 continue; 582 } 583 } 584 Operation::Deref { .. } => { 585 flush_code_chunk!(); 586 push!(CompiledExpressionPart::Deref); 587 // Don't re-enter the loop here (i.e. continue), because the 588 // DW_OP_deref still needs to be kept. 589 } 590 Operation::WasmLocal { index } => { 591 flush_code_chunk!(); 592 let label = ValueLabel::from_u32(index); 593 push!(CompiledExpressionPart::Local { 594 label, 595 trailing: false, 596 }); 597 continue; 598 } 599 Operation::Shr { .. } | Operation::Shra { .. } => { 600 // Insert value normalisation part. 601 // The semantic value is 32 bits (TODO: check unit) 602 // but the target architecture is 64-bits. So we'll 603 // clean out the upper 32 bits (in a sign-correct way) 604 // to avoid contamination of the result with randomness. 605 let mut writer = ExpressionWriter::new(); 606 writer.write_op(gimli::constants::DW_OP_plus_uconst)?; 607 writer.write_uleb128(32)?; // increase shift amount 608 writer.write_op(gimli::constants::DW_OP_swap)?; 609 writer.write_op(gimli::constants::DW_OP_const1u)?; 610 writer.write_u8(32)?; 611 writer.write_op(gimli::constants::DW_OP_shl)?; 612 writer.write_op(gimli::constants::DW_OP_swap)?; 613 code_chunk.extend(writer.into_vec()); 614 // Don't re-enter the loop here (i.e. continue), because the 615 // DW_OP_shr* still needs to be kept. 616 } 617 Operation::Address { .. } 618 | Operation::AddressIndex { .. } 619 | Operation::Call { .. } 620 | Operation::Register { .. } 621 | Operation::RegisterOffset { .. } 622 | Operation::CallFrameCFA 623 | Operation::PushObjectAddress 624 | Operation::TLS 625 | Operation::ImplicitValue { .. } 626 | Operation::ImplicitPointer { .. } 627 | Operation::EntryValue { .. } 628 | Operation::ParameterRef { .. } => { 629 return Ok(None); 630 } 631 Operation::WasmGlobal { index: _ } | Operation::WasmStack { index: _ } => { 632 // TODO support those two 633 return Ok(None); 634 } 635 } 636 let chunk = &buf[pos..pc.offset_from(&expr.0).into_u64() as usize]; 637 code_chunk.extend_from_slice(chunk); 638 } 639 640 flush_code_chunk!(); 641 if let Some(marker) = jump_targets.get(&0) { 642 parts.push(CompiledExpressionPart::LandingPad(marker.clone())); 643 } 644 645 Ok(Some(CompiledExpression { parts, need_deref })) 646 } 647 648 #[derive(Debug, Clone)] 649 struct CachedValueLabelRange { 650 func_index: usize, 651 start: usize, 652 end: usize, 653 label_location: HashMap<ValueLabel, LabelValueLoc>, 654 } 655 656 struct ValueLabelRangesBuilder<'a, 'b> { 657 ranges: Vec<CachedValueLabelRange>, 658 frame_info: Option<&'a FunctionFrameInfo<'b>>, 659 processed_labels: HashSet<ValueLabel>, 660 } 661 662 impl<'a, 'b> ValueLabelRangesBuilder<'a, 'b> { 663 pub fn new( 664 scope: &[(u64, u64)], // wasm ranges 665 addr_tr: &'a AddressTransform, 666 frame_info: Option<&'a FunctionFrameInfo<'b>>, 667 ) -> Self { 668 let mut ranges = Vec::new(); 669 for (wasm_start, wasm_end) in scope { 670 if let Some((func_index, tr)) = addr_tr.translate_ranges_raw(*wasm_start, *wasm_end) { 671 ranges.extend(tr.into_iter().map(|(start, end)| CachedValueLabelRange { 672 func_index, 673 start, 674 end, 675 label_location: HashMap::new(), 676 })); 677 } 678 } 679 ranges.sort_unstable_by(|a, b| a.start.cmp(&b.start)); 680 ValueLabelRangesBuilder { 681 ranges, 682 frame_info, 683 processed_labels: HashSet::new(), 684 } 685 } 686 687 fn process_label(&mut self, label: ValueLabel) { 688 if self.processed_labels.contains(&label) { 689 return; 690 } 691 self.processed_labels.insert(label); 692 693 let value_ranges = match self.frame_info.and_then(|fi| fi.value_ranges.get(&label)) { 694 Some(value_ranges) => value_ranges, 695 None => { 696 return; 697 } 698 }; 699 700 let ranges = &mut self.ranges; 701 for value_range in value_ranges { 702 let range_start = value_range.start as usize; 703 let range_end = value_range.end as usize; 704 let loc = value_range.loc; 705 if range_start == range_end { 706 continue; 707 } 708 assert!(range_start < range_end); 709 710 // Find acceptable scope of ranges to intersect with. 711 let i = match ranges.binary_search_by(|s| s.start.cmp(&range_start)) { 712 Ok(i) => i, 713 Err(i) => { 714 if i > 0 && range_start < ranges[i - 1].end { 715 i - 1 716 } else { 717 i 718 } 719 } 720 }; 721 let j = match ranges.binary_search_by(|s| s.start.cmp(&range_end)) { 722 Ok(i) | Err(i) => i, 723 }; 724 // Starting from the end, intersect (range_start..range_end) with 725 // self.ranges array. 726 for i in (i..j).rev() { 727 if range_end <= ranges[i].start || ranges[i].end <= range_start { 728 continue; 729 } 730 if range_end < ranges[i].end { 731 // Cutting some of the range from the end. 732 let mut tail = ranges[i].clone(); 733 ranges[i].end = range_end; 734 tail.start = range_end; 735 ranges.insert(i + 1, tail); 736 } 737 assert!(ranges[i].end <= range_end); 738 if range_start <= ranges[i].start { 739 ranges[i].label_location.insert(label, loc); 740 continue; 741 } 742 // Cutting some of the range from the start. 743 let mut tail = ranges[i].clone(); 744 ranges[i].end = range_start; 745 tail.start = range_start; 746 tail.label_location.insert(label, loc); 747 ranges.insert(i + 1, tail); 748 } 749 } 750 } 751 752 pub fn into_ranges(self) -> impl Iterator<Item = CachedValueLabelRange> { 753 // Ranges with not-enough labels are discarded. 754 let processed_labels_len = self.processed_labels.len(); 755 self.ranges 756 .into_iter() 757 .filter(move |r| r.label_location.len() == processed_labels_len) 758 } 759 } 760 761 /// Marker for tracking incoming jumps. 762 /// Different when created new, and the same when cloned. 763 #[derive(Clone, Eq)] 764 struct JumpTargetMarker(Rc<u32>); 765 766 impl JumpTargetMarker { 767 fn new() -> JumpTargetMarker { 768 // Create somewhat unique hash data -- using part of 769 // the pointer of the RcBox. 770 let mut rc = Rc::new(0); 771 let hash_data = rc.as_ref() as *const u32 as usize as u32; 772 *Rc::get_mut(&mut rc).unwrap() = hash_data; 773 JumpTargetMarker(rc) 774 } 775 } 776 777 impl PartialEq for JumpTargetMarker { 778 fn eq(&self, other: &JumpTargetMarker) -> bool { 779 Rc::ptr_eq(&self.0, &other.0) 780 } 781 } 782 783 impl Hash for JumpTargetMarker { 784 fn hash<H: Hasher>(&self, hasher: &mut H) { 785 hasher.write_u32(*self.0); 786 } 787 } 788 impl std::fmt::Debug for JumpTargetMarker { 789 fn fmt(&self, f: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> { 790 write!( 791 f, 792 "JumpMarker<{:08x}>", 793 self.0.as_ref() as *const u32 as usize 794 ) 795 } 796 } 797 798 #[cfg(test)] 799 mod tests { 800 use super::{ 801 compile_expression, AddressTransform, CompiledExpression, CompiledExpressionPart, 802 FunctionFrameInfo, JumpTargetMarker, ValueLabel, ValueLabelsRanges, 803 }; 804 use crate::CompiledFunctionMetadata; 805 use gimli::{constants, Encoding, EndianSlice, Expression, RunTimeEndian}; 806 use wasmtime_environ::FilePos; 807 808 macro_rules! dw_op { 809 (DW_OP_WASM_location) => { 810 0xed 811 }; 812 ($i:literal) => { 813 $i 814 }; 815 ($d:ident) => { 816 constants::$d.0 as u8 817 }; 818 ($e:expr) => { 819 $e as u8 820 }; 821 } 822 823 macro_rules! expression { 824 ($($t:tt),*) => { 825 Expression(EndianSlice::new( 826 &[$(dw_op!($t)),*], 827 RunTimeEndian::Little, 828 )) 829 } 830 } 831 832 fn find_jump_targets<'a>(ce: &'a CompiledExpression) -> Vec<&'a JumpTargetMarker> { 833 ce.parts 834 .iter() 835 .filter_map(|p| { 836 if let CompiledExpressionPart::LandingPad(t) = p { 837 Some(t) 838 } else { 839 None 840 } 841 }) 842 .collect::<Vec<_>>() 843 } 844 845 static DWARF_ENCODING: Encoding = Encoding { 846 address_size: 4, 847 format: gimli::Format::Dwarf32, 848 version: 4, 849 }; 850 851 #[test] 852 fn test_debug_expression_jump_target() { 853 let m1 = JumpTargetMarker::new(); 854 let m2 = JumpTargetMarker::new(); 855 assert!(m1 != m2); 856 assert!(m1 == m1.clone()); 857 858 // Internal hash_data test (theoretically can fail intermittently). 859 assert!(m1.0 != m2.0); 860 } 861 862 #[test] 863 fn test_debug_parse_expressions() { 864 use cranelift_entity::EntityRef; 865 866 let (val1, val3, val20) = (ValueLabel::new(1), ValueLabel::new(3), ValueLabel::new(20)); 867 868 let e = expression!(DW_OP_WASM_location, 0x0, 20, DW_OP_stack_value); 869 let ce = compile_expression(&e, DWARF_ENCODING, None) 870 .expect("non-error") 871 .expect("expression"); 872 assert_eq!( 873 ce, 874 CompiledExpression { 875 parts: vec![CompiledExpressionPart::Local { 876 label: val20, 877 trailing: true 878 }], 879 need_deref: false, 880 } 881 ); 882 883 let e = expression!( 884 DW_OP_WASM_location, 885 0x0, 886 1, 887 DW_OP_plus_uconst, 888 0x10, 889 DW_OP_stack_value 890 ); 891 let ce = compile_expression(&e, DWARF_ENCODING, None) 892 .expect("non-error") 893 .expect("expression"); 894 assert_eq!( 895 ce, 896 CompiledExpression { 897 parts: vec![ 898 CompiledExpressionPart::Local { 899 label: val1, 900 trailing: false 901 }, 902 CompiledExpressionPart::Code(vec![35, 16, 159]) 903 ], 904 need_deref: false, 905 } 906 ); 907 908 let e = expression!(DW_OP_WASM_location, 0x0, 3, DW_OP_stack_value); 909 let fe = compile_expression(&e, DWARF_ENCODING, None).expect("non-error"); 910 let e = expression!(DW_OP_fbreg, 0x12); 911 let ce = compile_expression(&e, DWARF_ENCODING, fe.as_ref()) 912 .expect("non-error") 913 .expect("expression"); 914 assert_eq!( 915 ce, 916 CompiledExpression { 917 parts: vec![ 918 CompiledExpressionPart::Local { 919 label: val3, 920 trailing: false 921 }, 922 CompiledExpressionPart::Code(vec![35, 18]) 923 ], 924 need_deref: true, 925 } 926 ); 927 928 let e = expression!( 929 DW_OP_WASM_location, 930 0x0, 931 1, 932 DW_OP_plus_uconst, 933 5, 934 DW_OP_deref, 935 DW_OP_stack_value 936 ); 937 let ce = compile_expression(&e, DWARF_ENCODING, None) 938 .expect("non-error") 939 .expect("expression"); 940 assert_eq!( 941 ce, 942 CompiledExpression { 943 parts: vec![ 944 CompiledExpressionPart::Local { 945 label: val1, 946 trailing: false 947 }, 948 CompiledExpressionPart::Code(vec![35, 5]), 949 CompiledExpressionPart::Deref, 950 CompiledExpressionPart::Code(vec![6, 159]) 951 ], 952 need_deref: false, 953 } 954 ); 955 956 let e = expression!( 957 DW_OP_WASM_location, 958 0x0, 959 1, 960 DW_OP_lit16, 961 DW_OP_shra, 962 DW_OP_stack_value 963 ); 964 let ce = compile_expression(&e, DWARF_ENCODING, None) 965 .expect("non-error") 966 .expect("expression"); 967 assert_eq!( 968 ce, 969 CompiledExpression { 970 parts: vec![ 971 CompiledExpressionPart::Local { 972 label: val1, 973 trailing: false 974 }, 975 CompiledExpressionPart::Code(vec![64, 35, 32, 22, 8, 32, 36, 22, 38, 159]) 976 ], 977 need_deref: false, 978 } 979 ); 980 981 let e = expression!( 982 DW_OP_lit1, 983 DW_OP_dup, 984 DW_OP_WASM_location, 985 0x0, 986 1, 987 DW_OP_and, 988 DW_OP_bra, 989 5, 990 0, // --> pointer 991 DW_OP_swap, 992 DW_OP_shr, 993 DW_OP_skip, 994 2, 995 0, // --> done 996 // pointer: 997 DW_OP_plus, 998 DW_OP_deref, 999 // done: 1000 DW_OP_stack_value 1001 ); 1002 let ce = compile_expression(&e, DWARF_ENCODING, None) 1003 .expect("non-error") 1004 .expect("expression"); 1005 let targets = find_jump_targets(&ce); 1006 assert_eq!(targets.len(), 2); 1007 assert_eq!( 1008 ce, 1009 CompiledExpression { 1010 parts: vec![ 1011 CompiledExpressionPart::Code(vec![49, 18]), 1012 CompiledExpressionPart::Local { 1013 label: val1, 1014 trailing: false 1015 }, 1016 CompiledExpressionPart::Code(vec![26]), 1017 CompiledExpressionPart::Jump { 1018 conditionally: true, 1019 target: targets[0].clone(), 1020 }, 1021 CompiledExpressionPart::Code(vec![22, 35, 32, 22, 8, 32, 36, 22, 37]), 1022 CompiledExpressionPart::Jump { 1023 conditionally: false, 1024 target: targets[1].clone(), 1025 }, 1026 CompiledExpressionPart::LandingPad(targets[0].clone()), // capture from 1027 CompiledExpressionPart::Code(vec![34]), 1028 CompiledExpressionPart::Deref, 1029 CompiledExpressionPart::Code(vec![6]), 1030 CompiledExpressionPart::LandingPad(targets[1].clone()), // capture to 1031 CompiledExpressionPart::Code(vec![159]) 1032 ], 1033 need_deref: false, 1034 } 1035 ); 1036 1037 let e = expression!( 1038 DW_OP_lit1, 1039 DW_OP_dup, 1040 DW_OP_bra, 1041 2, 1042 0, // --> target 1043 DW_OP_deref, 1044 DW_OP_lit0, 1045 // target: 1046 DW_OP_stack_value 1047 ); 1048 let ce = compile_expression(&e, DWARF_ENCODING, None) 1049 .expect("non-error") 1050 .expect("expression"); 1051 let targets = find_jump_targets(&ce); 1052 assert_eq!(targets.len(), 1); 1053 assert_eq!( 1054 ce, 1055 CompiledExpression { 1056 parts: vec![ 1057 CompiledExpressionPart::Code(vec![49, 18]), 1058 CompiledExpressionPart::Jump { 1059 conditionally: true, 1060 target: targets[0].clone(), 1061 }, 1062 CompiledExpressionPart::Deref, 1063 CompiledExpressionPart::Code(vec![6, 48]), 1064 CompiledExpressionPart::LandingPad(targets[0].clone()), // capture to 1065 CompiledExpressionPart::Code(vec![159]) 1066 ], 1067 need_deref: false, 1068 } 1069 ); 1070 1071 let e = expression!( 1072 DW_OP_lit1, 1073 /* loop */ DW_OP_dup, 1074 DW_OP_lit25, 1075 DW_OP_ge, 1076 DW_OP_bra, 1077 5, 1078 0, // --> done 1079 DW_OP_plus_uconst, 1080 1, 1081 DW_OP_skip, 1082 (-11_i8), 1083 (!0), // --> loop 1084 /* done */ DW_OP_stack_value 1085 ); 1086 let ce = compile_expression(&e, DWARF_ENCODING, None) 1087 .expect("non-error") 1088 .expect("expression"); 1089 let targets = find_jump_targets(&ce); 1090 assert_eq!(targets.len(), 2); 1091 assert_eq!( 1092 ce, 1093 CompiledExpression { 1094 parts: vec![ 1095 CompiledExpressionPart::Code(vec![49]), 1096 CompiledExpressionPart::LandingPad(targets[0].clone()), 1097 CompiledExpressionPart::Code(vec![18, 73, 42]), 1098 CompiledExpressionPart::Jump { 1099 conditionally: true, 1100 target: targets[1].clone(), 1101 }, 1102 CompiledExpressionPart::Code(vec![35, 1]), 1103 CompiledExpressionPart::Jump { 1104 conditionally: false, 1105 target: targets[0].clone(), 1106 }, 1107 CompiledExpressionPart::LandingPad(targets[1].clone()), 1108 CompiledExpressionPart::Code(vec![159]) 1109 ], 1110 need_deref: false, 1111 } 1112 ); 1113 1114 let e = expression!(DW_OP_WASM_location, 0x0, 1, DW_OP_plus_uconst, 5); 1115 let ce = compile_expression(&e, DWARF_ENCODING, None) 1116 .expect("non-error") 1117 .expect("expression"); 1118 assert_eq!( 1119 ce, 1120 CompiledExpression { 1121 parts: vec![ 1122 CompiledExpressionPart::Local { 1123 label: val1, 1124 trailing: false 1125 }, 1126 CompiledExpressionPart::Code(vec![35, 5]) 1127 ], 1128 need_deref: true, 1129 } 1130 ); 1131 } 1132 1133 fn create_mock_address_transform() -> AddressTransform { 1134 use crate::FunctionAddressMap; 1135 use cranelift_entity::PrimaryMap; 1136 use wasmtime_environ::InstructionAddressMap; 1137 use wasmtime_environ::WasmFileInfo; 1138 1139 let mut module_map = PrimaryMap::new(); 1140 let code_section_offset: u32 = 100; 1141 let func = CompiledFunctionMetadata { 1142 address_map: FunctionAddressMap { 1143 instructions: vec![ 1144 InstructionAddressMap { 1145 srcloc: FilePos::new(code_section_offset + 12), 1146 code_offset: 5, 1147 }, 1148 InstructionAddressMap { 1149 srcloc: FilePos::default(), 1150 code_offset: 8, 1151 }, 1152 InstructionAddressMap { 1153 srcloc: FilePos::new(code_section_offset + 17), 1154 code_offset: 15, 1155 }, 1156 InstructionAddressMap { 1157 srcloc: FilePos::default(), 1158 code_offset: 23, 1159 }, 1160 ] 1161 .into(), 1162 start_srcloc: FilePos::new(code_section_offset + 10), 1163 end_srcloc: FilePos::new(code_section_offset + 20), 1164 body_offset: 0, 1165 body_len: 30, 1166 }, 1167 ..Default::default() 1168 }; 1169 module_map.push(&func); 1170 let fi = WasmFileInfo { 1171 code_section_offset: code_section_offset.into(), 1172 funcs: Vec::new(), 1173 imported_func_count: 0, 1174 path: None, 1175 }; 1176 AddressTransform::mock(&module_map, fi) 1177 } 1178 1179 fn create_mock_value_ranges() -> (ValueLabelsRanges, (ValueLabel, ValueLabel, ValueLabel)) { 1180 use cranelift_codegen::{LabelValueLoc, ValueLocRange}; 1181 use cranelift_entity::EntityRef; 1182 use std::collections::HashMap; 1183 let mut value_ranges = HashMap::new(); 1184 let value_0 = ValueLabel::new(0); 1185 let value_1 = ValueLabel::new(1); 1186 let value_2 = ValueLabel::new(2); 1187 value_ranges.insert( 1188 value_0, 1189 vec![ValueLocRange { 1190 loc: LabelValueLoc::CFAOffset(0), 1191 start: 0, 1192 end: 25, 1193 }], 1194 ); 1195 value_ranges.insert( 1196 value_1, 1197 vec![ValueLocRange { 1198 loc: LabelValueLoc::CFAOffset(0), 1199 start: 5, 1200 end: 30, 1201 }], 1202 ); 1203 value_ranges.insert( 1204 value_2, 1205 vec![ 1206 ValueLocRange { 1207 loc: LabelValueLoc::CFAOffset(0), 1208 start: 0, 1209 end: 10, 1210 }, 1211 ValueLocRange { 1212 loc: LabelValueLoc::CFAOffset(0), 1213 start: 20, 1214 end: 30, 1215 }, 1216 ], 1217 ); 1218 (value_ranges, (value_0, value_1, value_2)) 1219 } 1220 1221 #[test] 1222 fn test_debug_value_range_builder() { 1223 use super::ValueLabelRangesBuilder; 1224 use crate::debug::ModuleMemoryOffset; 1225 1226 let addr_tr = create_mock_address_transform(); 1227 let (value_ranges, value_labels) = create_mock_value_ranges(); 1228 let fi = FunctionFrameInfo { 1229 memory_offset: ModuleMemoryOffset::None, 1230 value_ranges: &value_ranges, 1231 }; 1232 1233 // No value labels, testing if entire function range coming through. 1234 let builder = ValueLabelRangesBuilder::new(&[(10, 20)], &addr_tr, Some(&fi)); 1235 let ranges = builder.into_ranges().collect::<Vec<_>>(); 1236 assert_eq!(ranges.len(), 1); 1237 assert_eq!(ranges[0].func_index, 0); 1238 assert_eq!(ranges[0].start, 0); 1239 assert_eq!(ranges[0].end, 30); 1240 1241 // Two labels ([email protected] and [email protected]), their common lifetime intersect at 5..25. 1242 let mut builder = ValueLabelRangesBuilder::new(&[(10, 20)], &addr_tr, Some(&fi)); 1243 builder.process_label(value_labels.0); 1244 builder.process_label(value_labels.1); 1245 let ranges = builder.into_ranges().collect::<Vec<_>>(); 1246 assert_eq!(ranges.len(), 1); 1247 assert_eq!(ranges[0].start, 5); 1248 assert_eq!(ranges[0].end, 25); 1249 1250 // Adds val2 with complex lifetime @0..10 and @20..30 to the previous test, and 1251 // also narrows range. 1252 let mut builder = ValueLabelRangesBuilder::new(&[(11, 17)], &addr_tr, Some(&fi)); 1253 builder.process_label(value_labels.0); 1254 builder.process_label(value_labels.1); 1255 builder.process_label(value_labels.2); 1256 let ranges = builder.into_ranges().collect::<Vec<_>>(); 1257 // Result is two ranges @5..10 and @20..23 1258 assert_eq!(ranges.len(), 2); 1259 assert_eq!(ranges[0].start, 5); 1260 assert_eq!(ranges[0].end, 10); 1261 assert_eq!(ranges[1].start, 20); 1262 assert_eq!(ranges[1].end, 23); 1263 } 1264 } 1265