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