| // Copyright 2019 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| use { |
| super::{validate::ROOT_ID, Data, LazyNode, Metrics, Node, Payload, Property, ROOT_NAME}, |
| crate::metrics::{BlockMetrics, BlockStatus}, |
| anyhow::{bail, format_err, Error}, |
| diagnostics_hierarchy::LinkNodeDisposition, |
| fuchsia_inspect::{ |
| self, |
| format::{ |
| block::{ArrayFormat, Block, PropertyFormat}, |
| block_type::BlockType, |
| constants::MIN_ORDER_SIZE, |
| }, |
| reader as ireader, |
| }, |
| fuchsia_zircon::Vmo, |
| std::{ |
| self, |
| cmp::min, |
| collections::{HashMap, HashSet}, |
| convert::TryFrom, |
| }, |
| }; |
| |
| // When reading from a VMO, the keys of the HashMaps are the indexes of the relevant |
| // blocks. Thus, they will never collide. |
| // |
| // Reading from a VMO is a complicated process. |
| // 1) Try to take a fuchsia_inspect::reader::snapshot::Snapshot of the VMO. |
| // 2) Iterate through it, pedantically examining all its blocks and loading |
| // the relevant blocks into a ScannedObjects structure (which contains |
| // ScannedNode, ScannedName, ScannedProperty, and ScannedExtent). |
| // 2.5) ScannedNodes may be added before they're scanned, since they need to |
| // track their child nodes and properties. In this case, their "validated" |
| // field will be false until they're actually scanned. |
| // 3) Starting from the "0" node, create Node and Property objects for all the |
| // dependent children and properties (verifying that all dependent objects |
| // exist (and are valid in the case of Nodes)). This is also when Extents are |
| // combined into byte vectors, and in the case of String, verified to be valid UTF-8. |
| // 4) Add the Node and Property objects (each with its ID) into the "nodes" and |
| // "properties" HashMaps of a new Data object. Note that these HashMaps do not |
| // hold the hierarchical information; instead, each Node contains a HashSet of |
| // the keys of its children and properties. |
| |
| #[derive(Debug)] |
| pub struct Scanner { |
| nodes: HashMap<u32, ScannedNode>, |
| names: HashMap<u32, ScannedName>, |
| properties: HashMap<u32, ScannedProperty>, |
| extents: HashMap<u32, ScannedExtent>, |
| final_nodes: HashMap<u32, Node>, |
| final_properties: HashMap<u32, Property>, |
| metrics: Metrics, |
| child_trees: Option<HashMap<String, LazyNode>>, |
| } |
| |
| impl TryFrom<&[u8]> for Scanner { |
| type Error = Error; |
| |
| fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> { |
| let scanner = Scanner::new(None); |
| scanner.scan(ireader::snapshot::Snapshot::try_from(bytes)?, bytes) |
| } |
| } |
| |
| impl TryFrom<&Vmo> for Scanner { |
| type Error = Error; |
| fn try_from(vmo: &Vmo) -> Result<Self, Self::Error> { |
| let scanner = Scanner::new(None); |
| scanner.scan(ireader::snapshot::Snapshot::try_from(vmo)?, &vmo_as_buffer(vmo)?) |
| } |
| } |
| |
| impl TryFrom<LazyNode> for Scanner { |
| type Error = Error; |
| |
| fn try_from(mut vmo_tree: LazyNode) -> Result<Self, Self::Error> { |
| let snapshot = ireader::snapshot::Snapshot::try_from(vmo_tree.vmo())?; |
| let buffer = vmo_as_buffer(vmo_tree.vmo())?; |
| let scanner = Scanner::new(vmo_tree.take_children()); |
| scanner.scan(snapshot, &buffer) |
| } |
| } |
| |
| fn vmo_as_buffer(vmo: &Vmo) -> Result<Vec<u8>, Error> { |
| // NOTE: In any context except a controlled test, it's not safe to read the VMO manually - |
| // the contents may differ or even be invalid (mid-update). |
| let size = vmo.get_size()?; |
| let mut buffer = vec![0u8; size as usize]; |
| vmo.read(&mut buffer[..], 0)?; |
| Ok(buffer) |
| } |
| |
| fn low_bits(number: u8, n_bits: usize) -> u8 { |
| let n_bits = min(n_bits, 8); |
| let mask = !(0xff_u16 << n_bits) as u8; |
| number & mask |
| } |
| |
| fn high_bits(number: u8, n_bits: usize) -> u8 { |
| let n_bits = min(n_bits, 8); |
| let mask = !(0xff_u16 >> n_bits) as u8; |
| number & mask |
| } |
| |
| const BITS_PER_BYTE: usize = 8; |
| |
| /// Get size in bytes of a given |order|. Copied from private mod fuchsia-inspect/src/utils.rs |
| fn order_to_size(order: usize) -> usize { |
| MIN_ORDER_SIZE << order |
| } |
| |
| // Checks if these bits (start...end) are 0. Restricts the range checked to the given block. |
| fn check_zero_bits( |
| buffer: &[u8], |
| block: &Block<&[u8]>, |
| start: usize, |
| end: usize, |
| ) -> Result<(), Error> { |
| if end < start { |
| return Err(format_err!("End must be >= start")); |
| } |
| let bits_in_block = order_to_size(block.order()) * BITS_PER_BYTE; |
| if start > bits_in_block - 1 { |
| return Ok(()); |
| } |
| let end = min(end, bits_in_block - 1); |
| let block_offset = block.index() as usize * MIN_ORDER_SIZE; |
| let low_byte = start / BITS_PER_BYTE; |
| let high_byte = end / BITS_PER_BYTE; |
| let bottom_bits = high_bits(buffer[low_byte + block_offset], 8 - (start % 8)); |
| let top_bits = low_bits(buffer[high_byte + block_offset], (end % 8) + 1); |
| if low_byte == high_byte { |
| match bottom_bits & top_bits { |
| 0 => return Ok(()), |
| nonzero => bail!( |
| "Bits {}...{} of block type {} at {} have nonzero value {}", |
| start, |
| end, |
| block.block_type_or()?, |
| block.index(), |
| nonzero |
| ), |
| } |
| } |
| if bottom_bits != 0 { |
| bail!( |
| "Non-zero value {} for bits {}.. of block type {} at {}", |
| bottom_bits, |
| start, |
| block.block_type_or()?, |
| block.index() |
| ); |
| } |
| if top_bits != 0 { |
| bail!( |
| "Non-zero value {} for bits ..{} of block type {} at {}", |
| top_bits, |
| end, |
| block.block_type_or()?, |
| block.index() |
| ); |
| } |
| for byte in low_byte + 1..high_byte { |
| if buffer[byte + block_offset] != 0 { |
| bail!( |
| "Non-zero value {} for byte {} of block type {} at {}", |
| buffer[byte], |
| byte, |
| block.block_type_or()?, |
| block.index() |
| ); |
| } |
| } |
| Ok(()) |
| } |
| |
| impl Scanner { |
| fn new(child_trees: Option<HashMap<String, LazyNode>>) -> Scanner { |
| let mut ret = Scanner { |
| nodes: HashMap::new(), |
| names: HashMap::new(), |
| properties: HashMap::new(), |
| extents: HashMap::new(), |
| metrics: Metrics::new(), |
| final_nodes: HashMap::new(), |
| final_properties: HashMap::new(), |
| child_trees, |
| }; |
| // The ScannedNode at 0 is the "root" node. It exists to receive pointers to objects |
| // whose parent is 0 while scanning the VMO. |
| ret.nodes.insert( |
| 0, |
| ScannedNode { |
| validated: true, |
| parent: 0, |
| name: 0, |
| children: HashSet::new(), |
| properties: HashSet::new(), |
| metrics: None, |
| }, |
| ); |
| ret |
| } |
| |
| fn scan(mut self, snapshot: ireader::snapshot::Snapshot, buffer: &[u8]) -> Result<Self, Error> { |
| let mut link_blocks: Vec<Block<&[u8]>> = Vec::new(); |
| for block in snapshot.scan() { |
| match block.block_type_or() { |
| Ok(BlockType::Free) => self.process_free(block)?, |
| Ok(BlockType::Reserved) => self.process_reserved(block)?, |
| Ok(BlockType::Header) => self.process_header(block)?, |
| Ok(BlockType::NodeValue) => self.process_node(block)?, |
| Ok(BlockType::IntValue) |
| | Ok(BlockType::UintValue) |
| | Ok(BlockType::DoubleValue) |
| | Ok(BlockType::ArrayValue) |
| | Ok(BlockType::BufferValue) |
| | Ok(BlockType::BoolValue) => self.process_property(block, buffer)?, |
| Ok(BlockType::LinkValue) => link_blocks.push(block), |
| Ok(BlockType::Extent) => self.process_extent(block, buffer)?, |
| Ok(BlockType::Name) => self.process_name(block, buffer)?, |
| Ok(BlockType::Tombstone) => self.process_tombstone(block)?, |
| Err(error) => return Err(format_err!("Failed to read block type: {:?}", error)), |
| } |
| } |
| // We defer processing LINK blocks after because the population of the ScannedPayload::Link depends on all NAME blocks having been read. |
| for block in link_blocks.into_iter() { |
| self.process_property(block, buffer)? |
| } |
| |
| let (mut new_nodes, mut new_properties) = self.make_valid_node_tree(ROOT_ID)?; |
| for (node, id) in new_nodes.drain(..) { |
| self.final_nodes.insert(id, node); |
| } |
| for (property, id) in new_properties.drain(..) { |
| self.final_properties.insert(id, property); |
| } |
| self.record_unused_metrics(); |
| Ok(self) |
| } |
| |
| pub fn data(self) -> Data { |
| Data::build(self.final_nodes, self.final_properties) |
| } |
| |
| pub fn metrics(self) -> Metrics { |
| self.metrics |
| } |
| |
| // ***** Utility functions |
| fn record_unused_metrics(&mut self) { |
| for (_, node) in self.nodes.drain() { |
| if let Some(metrics) = node.metrics { |
| self.metrics.record(&metrics, BlockStatus::NotUsed); |
| } |
| } |
| for (_, name) in self.names.drain() { |
| self.metrics.record(&name.metrics, BlockStatus::NotUsed); |
| } |
| for (_, property) in self.properties.drain() { |
| self.metrics.record(&property.metrics, BlockStatus::NotUsed); |
| } |
| for (_, extent) in self.extents.drain() { |
| self.metrics.record(&extent.metrics, BlockStatus::NotUsed); |
| } |
| } |
| |
| fn use_node(&mut self, node_id: u32) -> Result<ScannedNode, Error> { |
| let mut node = |
| self.nodes.remove(&node_id).ok_or(format_err!("No node at index {}", node_id))?; |
| match node.metrics { |
| None => { |
| if node_id != 0 { |
| return Err(format_err!("Invalid node (no metrics) at index {}", node_id)); |
| } |
| } |
| Some(metrics) => { |
| // I actually want as_deref() but that's nightly-only. |
| self.metrics.record(&metrics, BlockStatus::Used); |
| node.metrics = Some(metrics); // Put it back after I borrow it. |
| } |
| } |
| Ok(node) |
| } |
| |
| fn use_property(&mut self, property_id: u32) -> Result<ScannedProperty, Error> { |
| let property = self |
| .properties |
| .remove(&property_id) |
| .ok_or(format_err!("No property at index {}", property_id))?; |
| self.metrics.record(&property.metrics, BlockStatus::Used); |
| Ok(property) |
| } |
| |
| fn use_owned_name(&mut self, name_id: u32) -> Result<String, Error> { |
| let name = |
| self.names.remove(&name_id).ok_or(format_err!("No string at index {}", name_id))?; |
| self.metrics.record(&name.metrics, BlockStatus::Used); |
| Ok(name.name.clone()) |
| } |
| |
| // ***** Functions which read fuchsia_inspect::format::block::Block (actual |
| // ***** VMO blocks), validate them, turn them into Scanned* objects, and |
| // ***** add the ones we care about to Self. |
| |
| // Some blocks' metrics can only be calculated in the context of a tree. Metrics aren't run |
| // on those in the process_ functions, but rather while the tree is being built. |
| |
| // Note: process_ functions are only called from the scan() iterator on the |
| // VMO's blocks, so indexes of the blocks themselves will never be duplicated; that's one |
| // thing we don't have to verify. |
| fn process_free(&mut self, block: Block<&[u8]>) -> Result<(), Error> { |
| // TODO(fxbug.dev/39975): Uncomment or delete this line depending on the resolution of fxbug.dev/40012. |
| // check_zero_bits(buffer, &block, 64, MAX_BLOCK_BITS)?; |
| self.metrics.process(block)?; |
| Ok(()) |
| } |
| |
| fn process_header(&mut self, block: Block<&[u8]>) -> Result<(), Error> { |
| self.metrics.process(block)?; |
| Ok(()) |
| } |
| |
| fn process_tombstone(&mut self, block: Block<&[u8]>) -> Result<(), Error> { |
| self.metrics.process(block)?; |
| Ok(()) |
| } |
| |
| fn process_reserved(&mut self, block: Block<&[u8]>) -> Result<(), Error> { |
| self.metrics.process(block)?; |
| Ok(()) |
| } |
| |
| fn process_extent(&mut self, block: Block<&[u8]>, buffer: &[u8]) -> Result<(), Error> { |
| check_zero_bits(buffer, &block, 40, 63)?; |
| self.extents.insert( |
| block.index(), |
| ScannedExtent { |
| next: block.next_extent()?, |
| data: block.extent_contents()?, |
| metrics: Metrics::analyze(block)?, |
| }, |
| ); |
| Ok(()) |
| } |
| |
| fn process_name(&mut self, block: Block<&[u8]>, buffer: &[u8]) -> Result<(), Error> { |
| check_zero_bits(buffer, &block, 28, 63)?; |
| self.names.insert( |
| block.index(), |
| ScannedName { name: block.name_contents()?, metrics: Metrics::analyze(block)? }, |
| ); |
| Ok(()) |
| } |
| |
| fn process_node(&mut self, block: Block<&[u8]>) -> Result<(), Error> { |
| let parent = block.parent_index()?; |
| let id = block.index(); |
| let name = block.name_index()?; |
| let mut node; |
| let metrics = Some(Metrics::analyze(block)?); |
| if let Some(placeholder) = self.nodes.remove(&id) { |
| // We need to preserve the children and properties. |
| node = placeholder; |
| node.validated = true; |
| node.parent = parent; |
| node.name = name; |
| node.metrics = metrics; |
| } else { |
| node = ScannedNode { |
| validated: true, |
| name, |
| parent, |
| children: HashSet::new(), |
| properties: HashSet::new(), |
| metrics, |
| } |
| } |
| self.nodes.insert(id, node); |
| self.add_to_parent(parent, id, |node| &mut node.children); |
| Ok(()) |
| } |
| |
| fn add_to_parent<F: FnOnce(&mut ScannedNode) -> &mut HashSet<u32>>( |
| &mut self, |
| parent: u32, |
| id: u32, |
| get_the_hashset: F, // Gets children or properties |
| ) { |
| if !self.nodes.contains_key(&parent) { |
| self.nodes.insert( |
| parent, |
| ScannedNode { |
| validated: false, |
| name: 0, |
| parent: 0, |
| children: HashSet::new(), |
| properties: HashSet::new(), |
| metrics: None, |
| }, |
| ); |
| } |
| if let Some(parent_node) = self.nodes.get_mut(&parent) { |
| get_the_hashset(parent_node).insert(id); |
| } |
| } |
| |
| fn build_scanned_payload( |
| &mut self, |
| block: &Block<&[u8]>, |
| block_type: BlockType, |
| ) -> Result<ScannedPayload, Error> { |
| Ok(match block_type { |
| BlockType::IntValue => ScannedPayload::Int(block.int_value()?), |
| BlockType::UintValue => ScannedPayload::Uint(block.uint_value()?), |
| BlockType::DoubleValue => ScannedPayload::Double(block.double_value()?), |
| BlockType::BoolValue => ScannedPayload::Bool(block.bool_value()?), |
| BlockType::BufferValue => { |
| let format = block.property_format()?; |
| let length = block.property_total_length()?; |
| let link = block.property_extent_index()?; |
| match format { |
| PropertyFormat::String => ScannedPayload::String { length, link }, |
| PropertyFormat::Bytes => ScannedPayload::Bytes { length, link }, |
| } |
| } |
| BlockType::ArrayValue => { |
| let entry_type = block.array_entry_type()?; |
| let array_format = block.array_format()?; |
| let slots = block.array_slots()? as usize; |
| match entry_type { |
| BlockType::IntValue => { |
| let numbers: Result<Vec<i64>, _> = |
| (0..slots).map(|i| block.array_get_int_slot(i)).collect(); |
| ScannedPayload::IntArray(numbers?, array_format) |
| } |
| BlockType::UintValue => { |
| let numbers: Result<Vec<u64>, _> = |
| (0..slots).map(|i| block.array_get_uint_slot(i)).collect(); |
| ScannedPayload::UintArray(numbers?, array_format) |
| } |
| BlockType::DoubleValue => { |
| let numbers: Result<Vec<f64>, _> = |
| (0..slots).map(|i| block.array_get_double_slot(i)).collect(); |
| ScannedPayload::DoubleArray(numbers?, array_format) |
| } |
| illegal_type => { |
| return Err(format_err!( |
| "No way I should see {:?} for ArrayEntryType", |
| illegal_type |
| )) |
| } |
| } |
| } |
| BlockType::LinkValue => { |
| let child_trees = self |
| .child_trees |
| .as_mut() |
| .ok_or(format_err!("LinkValue encountered without child tree."))?; |
| let child_name = &self |
| .names |
| .get(&block.link_content_index()?) |
| .ok_or(format_err!( |
| "Child name not found for LinkValue block {}.", |
| block.index() |
| ))? |
| .name; |
| let child_tree = child_trees.remove(child_name).ok_or(format_err!( |
| "Lazy node not found for LinkValue block {} with name {}.", |
| block.index(), |
| child_name |
| ))?; |
| ScannedPayload::Link { |
| disposition: block.link_node_disposition()?, |
| scanned_tree: Scanner::try_from(child_tree)?, |
| } |
| } |
| illegal_type => { |
| return Err(format_err!("No way I should see {:?} for BlockType", illegal_type)) |
| } |
| }) |
| } |
| |
| fn process_property(&mut self, block: Block<&[u8]>, buffer: &[u8]) -> Result<(), Error> { |
| if block.block_type_or()? == BlockType::ArrayValue { |
| check_zero_bits(buffer, &block, 80, 127)?; |
| } |
| let id = block.index(); |
| let parent = block.parent_index()?; |
| let block_type = block.block_type_or()?; |
| let payload = self.build_scanned_payload(&block, block_type)?; |
| let property = ScannedProperty { |
| name: block.name_index()?, |
| parent, |
| payload, |
| metrics: Metrics::analyze(block)?, |
| }; |
| self.properties.insert(id, property); |
| self.add_to_parent(parent, id, |node| &mut node.properties); |
| Ok(()) |
| } |
| |
| // ***** Functions which convert Scanned* objects into Node and Property objects. |
| |
| fn make_valid_node_tree( |
| &mut self, |
| id: u32, |
| ) -> Result<(Vec<(Node, u32)>, Vec<(Property, u32)>), Error> { |
| let scanned_node = self.use_node(id)?; |
| if !scanned_node.validated { |
| return Err(format_err!("No node at {}", id)); |
| } |
| let mut nodes_in_tree = vec![]; |
| let mut properties_under = vec![]; |
| for node_id in scanned_node.children.iter() { |
| let (mut nodes_of, mut properties_of) = self.make_valid_node_tree(*node_id)?; |
| nodes_in_tree.append(&mut nodes_of); |
| properties_under.append(&mut properties_of); |
| } |
| for property_id in scanned_node.properties.iter() { |
| properties_under.push((self.make_valid_property(*property_id)?, *property_id)); |
| } |
| let name = |
| if id == 0 { ROOT_NAME.to_owned() } else { self.use_owned_name(scanned_node.name)? }; |
| let this_node = Node { |
| name, |
| parent: scanned_node.parent, |
| children: scanned_node.children.clone(), |
| properties: scanned_node.properties.clone(), |
| }; |
| nodes_in_tree.push((this_node, id)); |
| Ok((nodes_in_tree, properties_under)) |
| } |
| |
| fn make_valid_property(&mut self, id: u32) -> Result<Property, Error> { |
| let scanned_property = self.use_property(id)?; |
| let name = self.use_owned_name(scanned_property.name)?; |
| let payload = self.make_valid_payload(scanned_property.payload)?; |
| Ok(Property { id, name, parent: scanned_property.parent, payload }) |
| } |
| |
| fn make_valid_payload(&mut self, payload: ScannedPayload) -> Result<Payload, Error> { |
| Ok(match payload { |
| ScannedPayload::Int(data) => Payload::Int(data), |
| ScannedPayload::Uint(data) => Payload::Uint(data), |
| ScannedPayload::Double(data) => Payload::Double(data), |
| ScannedPayload::Bool(data) => Payload::Bool(data), |
| ScannedPayload::IntArray(data, format) => Payload::IntArray(data, format), |
| ScannedPayload::UintArray(data, format) => Payload::UintArray(data, format), |
| ScannedPayload::DoubleArray(data, format) => Payload::DoubleArray(data, format), |
| ScannedPayload::Bytes { length, link } => { |
| Payload::Bytes(self.make_valid_vector(length, link)?) |
| } |
| ScannedPayload::String { length, link } => Payload::String( |
| std::str::from_utf8(&self.make_valid_vector(length, link)?)?.to_owned(), |
| ), |
| ScannedPayload::Link { disposition, scanned_tree } => { |
| Payload::Link { disposition, parsed_data: scanned_tree.data() } |
| } |
| }) |
| } |
| |
| fn make_valid_vector(&mut self, length: usize, link: u32) -> Result<Vec<u8>, Error> { |
| let mut dest = vec![]; |
| let mut length_remaining = length; |
| let mut next_link = link; |
| while length_remaining > 0 { |
| // This is effectively use_extent() |
| let mut extent = |
| self.extents.remove(&next_link).ok_or(format_err!("No extent at {}", next_link))?; |
| let copy_len = min(extent.data.len(), length_remaining); |
| extent.metrics.set_data_bytes(copy_len); |
| self.metrics.record(&extent.metrics, BlockStatus::Used); |
| dest.extend_from_slice(&extent.data[..copy_len]); |
| length_remaining -= copy_len; |
| next_link = extent.next; |
| } |
| Ok(dest) |
| } |
| } |
| |
| #[derive(Debug)] |
| struct ScannedNode { |
| // These may be created two ways: Either from being named as a parent, or |
| // from being processed in the VMO. Those named but not yet processed will |
| // have validated = false. Of course after a complete VMO scan, |
| // everything descended from a root node must be validated. |
| // validated refers to the binary contents of this block; it doesn't |
| // guarantee that properties, descendents, name, etc. are valid. |
| validated: bool, |
| name: u32, |
| parent: u32, |
| children: HashSet<u32>, |
| properties: HashSet<u32>, |
| metrics: Option<BlockMetrics>, |
| } |
| |
| #[derive(Debug)] |
| struct ScannedProperty { |
| name: u32, |
| parent: u32, |
| payload: ScannedPayload, |
| metrics: BlockMetrics, |
| } |
| |
| #[derive(Debug)] |
| struct ScannedName { |
| name: String, |
| metrics: BlockMetrics, |
| } |
| |
| #[derive(Debug)] |
| struct ScannedExtent { |
| next: u32, |
| data: Vec<u8>, |
| metrics: BlockMetrics, |
| } |
| |
| #[derive(Debug)] |
| enum ScannedPayload { |
| String { length: usize, link: u32 }, |
| Bytes { length: usize, link: u32 }, |
| Int(i64), |
| Uint(u64), |
| Double(f64), |
| Bool(bool), |
| IntArray(Vec<i64>, ArrayFormat), |
| UintArray(Vec<u64>, ArrayFormat), |
| DoubleArray(Vec<f64>, ArrayFormat), |
| Link { disposition: LinkNodeDisposition, scanned_tree: Scanner }, |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use num_traits::ToPrimitive; |
| use { |
| super::*, |
| crate::*, |
| fidl_test_inspect_validate::Number, |
| fuchsia_async as fasync, |
| fuchsia_inspect::format::{ |
| bitfields::{BlockHeader, Payload as BlockPayload}, |
| block_type::BlockType, |
| constants, |
| }, |
| }; |
| |
| // TODO(fxbug.dev/39975): Depending on the resolution of fxbug.dev/40012, move this const out of mod test. |
| const MAX_BLOCK_BITS: usize = constants::MAX_ORDER_SIZE * BITS_PER_BYTE; |
| |
| fn copy_into(source: &[u8], dest: &mut [u8], offset: usize) { |
| dest[offset..offset + source.len()].copy_from_slice(source); |
| } |
| |
| // Run "fx run-test inspect_validator_tests -- --nocapture" to see all the output |
| // and verify you're getting appropriate error messages for each tweaked byte. |
| // (The alternative is hard-coding expected error strings, which is possible but ugh.) |
| fn try_byte( |
| buffer: &mut [u8], |
| (index, offset): (usize, usize), |
| value: u8, |
| predicted: Option<&str>, |
| ) { |
| let location = index * 16 + offset; |
| let previous = buffer[location]; |
| buffer[location] = value; |
| let actual = data::Scanner::try_from(buffer as &[u8]).map(|d| d.data().to_string()); |
| if predicted.is_none() { |
| if actual.is_err() { |
| println!( |
| "With ({},{}) -> {}, got expected error {:?}", |
| index, offset, value, actual |
| ); |
| } else { |
| println!( |
| "BAD: With ({},{}) -> {}, expected error but got string {:?}", |
| index, |
| offset, |
| value, |
| actual.as_ref().unwrap() |
| ); |
| } |
| } else { |
| if actual.is_err() { |
| println!( |
| "BAD: With ({},{}) -> {}, got unexpected error {:?}", |
| index, offset, value, actual |
| ); |
| } else if actual.as_ref().ok().map(|s| &s[..]) == predicted { |
| println!( |
| "With ({},{}) -> {}, got expected string {:?}", |
| index, |
| offset, |
| value, |
| predicted.unwrap() |
| ); |
| } else { |
| println!( |
| "BAD: With ({},{}) -> {}, expected string {:?} but got {:?}", |
| index, |
| offset, |
| value, |
| predicted.unwrap(), |
| actual.as_ref().unwrap() |
| ); |
| println!("Raw data: {:?}", data::Scanner::try_from(buffer as &[u8])) |
| } |
| } |
| assert_eq!(predicted, actual.as_ref().ok().map(|s| &s[..])); |
| buffer[location] = previous; |
| } |
| |
| fn put_header(header: &BlockHeader, buffer: &mut [u8], index: usize) { |
| copy_into(&header.value().to_le_bytes(), buffer, index * 16); |
| } |
| |
| fn put_payload(payload: &BlockPayload, buffer: &mut [u8], index: usize) { |
| copy_into(&payload.value().to_le_bytes(), buffer, index * 16 + 8); |
| } |
| |
| #[test] |
| fn test_scanning_logic() { |
| let mut buffer = [0u8; 4096]; |
| // VMO Header block (index 0) |
| const HEADER: usize = 0; |
| let mut header = BlockHeader(0); |
| header.set_order(0); |
| header.set_block_type(BlockType::Header.to_u8().unwrap()); |
| header.set_header_magic(constants::HEADER_MAGIC_NUMBER); |
| header.set_header_version(constants::HEADER_VERSION_NUMBER); |
| put_header(&header, &mut buffer, HEADER); |
| const ROOT: usize = 1; |
| let mut header = BlockHeader(0); |
| header.set_order(0); |
| header.set_block_type(BlockType::NodeValue.to_u8().unwrap()); |
| header.set_value_name_index(2); |
| header.set_value_parent_index(0); |
| put_header(&header, &mut buffer, ROOT); |
| // Root's Name block |
| const ROOT_NAME: usize = 2; |
| let mut header = BlockHeader(0); |
| header.set_order(0); |
| header.set_block_type(BlockType::Name.to_u8().unwrap()); |
| header.set_name_length(4); |
| put_header(&header, &mut buffer, ROOT_NAME); |
| copy_into(b"node", &mut buffer, ROOT_NAME * 16 + 8); |
| try_byte(&mut buffer, (16, 0), 0, Some("root ->\n> node ->")); |
| // Mess up HEADER_MAGIC_NUMBER - it should fail to load. |
| try_byte(&mut buffer, (HEADER, 7), 0, None); |
| // Mess up node's parent; should disappear. |
| try_byte(&mut buffer, (ROOT, 1), 1, Some("root ->")); |
| // Mess up root's name; should fail. |
| try_byte(&mut buffer, (ROOT, 5), 1, None); |
| // Mess up generation count; should fail (and not hang). |
| try_byte(&mut buffer, (HEADER, 8), 1, None); |
| // But an even generation count should work. |
| try_byte(&mut buffer, (HEADER, 8), 2, Some("root ->\n> node ->")); |
| // Let's give it a property. |
| const NUMBER: usize = 4; |
| let mut number_header = BlockHeader(0); |
| number_header.set_order(0); |
| number_header.set_block_type(BlockType::IntValue.to_u8().unwrap()); |
| number_header.set_value_name_index(3); |
| number_header.set_value_parent_index(1); |
| put_header(&number_header, &mut buffer, NUMBER); |
| const NUMBER_NAME: usize = 3; |
| let mut header = BlockHeader(0); |
| header.set_order(0); |
| header.set_block_type(BlockType::Name.to_u8().unwrap()); |
| header.set_name_length(6); |
| put_header(&header, &mut buffer, NUMBER_NAME); |
| copy_into(b"number", &mut buffer, NUMBER_NAME * 16 + 8); |
| try_byte(&mut buffer, (HEADER, 8), 2, Some("root ->\n> node ->\n> > number: Int(0)")); |
| try_byte(&mut buffer, (NUMBER, 1), 5, Some("root ->\n> node ->\n> > number: Uint(0)")); |
| try_byte(&mut buffer, (NUMBER, 1), 6, Some("root ->\n> node ->\n> > number: Double(0.0)")); |
| try_byte(&mut buffer, (NUMBER, 1), 7, Some("root ->\n> node ->\n> > number: String(\"\")")); |
| // Array block will have illegal Array Entry Type of 0. |
| try_byte(&mut buffer, (NUMBER, 1), 0xb0, None); |
| // 15 is an illegal block type. |
| try_byte(&mut buffer, (NUMBER, 1), 0xf, None); |
| number_header.set_order(2); |
| number_header.set_block_type(BlockType::ArrayValue.to_u8().unwrap()); |
| put_header(&number_header, &mut buffer, NUMBER); |
| // Array block again has illegal Array Entry Type of 0. |
| try_byte(&mut buffer, (128, 0), 0, None); |
| // 4, 5, and 6 are legal array types. |
| try_byte( |
| &mut buffer, |
| (NUMBER, 8), |
| 0x04, |
| Some("root ->\n> node ->\n> > number: IntArray([], Default)"), |
| ); |
| try_byte( |
| &mut buffer, |
| (NUMBER, 8), |
| 0x05, |
| Some("root ->\n> node ->\n> > number: UintArray([], Default)"), |
| ); |
| try_byte( |
| &mut buffer, |
| (NUMBER, 8), |
| 0x06, |
| Some("root ->\n> node ->\n> > number: DoubleArray([], Default)"), |
| ); |
| // 0, 1, and 2 are legal formats. |
| try_byte( |
| &mut buffer, |
| (NUMBER, 8), |
| 0x14, |
| Some("root ->\n> node ->\n> > number: IntArray([], LinearHistogram)"), |
| ); |
| try_byte( |
| &mut buffer, |
| (NUMBER, 8), |
| 0x24, |
| Some("root ->\n> node ->\n> > number: IntArray([], ExponentialHistogram)"), |
| ); |
| try_byte(&mut buffer, (NUMBER, 8), 0x34, None); |
| // Let's make sure other Value block-type numbers are rejected. |
| try_byte(&mut buffer, (NUMBER, 8), BlockType::ArrayValue.to_u8().unwrap(), None); |
| buffer[NUMBER * 16 + 8] = 4; // Int, Default |
| buffer[NUMBER * 16 + 9] = 2; // 2 entries |
| try_byte( |
| &mut buffer, |
| (NUMBER, 16), |
| 42, |
| Some("root ->\n> node ->\n> > number: IntArray([42, 0], Default)"), |
| ); |
| try_byte( |
| &mut buffer, |
| (NUMBER, 24), |
| 42, |
| Some("root ->\n> node ->\n> > number: IntArray([0, 42], Default)"), |
| ); |
| } |
| |
| #[fasync::run_singlethreaded(test)] |
| async fn test_to_string_order() -> Result<(), Error> { |
| // Make sure property payloads are distinguished by name, value, and type |
| // but ignore id and parent, and that prefix is used. |
| let int0 = Property { name: "int0".into(), id: 2, parent: 1, payload: Payload::Int(0) } |
| .to_string(""); |
| let int1_struct = |
| Property { name: "int1".into(), id: 2, parent: 1, payload: Payload::Int(1) }; |
| let int1 = int1_struct.to_string(""); |
| assert_ne!(int0, int1); |
| let uint0 = Property { name: "uint0".into(), id: 2, parent: 1, payload: Payload::Uint(0) } |
| .to_string(""); |
| assert_ne!(int0, uint0); |
| let int0_different_name = Property { |
| name: "int0_different_name".into(), |
| id: 2, |
| parent: 1, |
| payload: Payload::Int(0), |
| } |
| .to_string(""); |
| assert_ne!(int0, int0_different_name); |
| let uint0_different_ids = |
| Property { name: "uint0".into(), id: 3, parent: 4, payload: Payload::Uint(0) } |
| .to_string(""); |
| assert_eq!(uint0, uint0_different_ids); |
| let int1_different_prefix = int1_struct.to_string("foo"); |
| assert_ne!(int1, int1_different_prefix); |
| // Test that order doesn't matter. Use a real VMO rather than Data's |
| // HashMaps which may not reflect order of addition. |
| let mut puppet1 = puppet::tests::local_incomplete_puppet().await?; |
| let mut child1_action = create_node!(parent:0, id:1, name:"child1"); |
| let mut child2_action = create_node!(parent:0, id:2, name:"child2"); |
| let mut property1_action = |
| create_numeric_property!(parent:0, id:1, name:"prop1", value: Number::IntT(1)); |
| let mut property2_action = |
| create_numeric_property!(parent:0, id:2, name:"prop2", value: Number::IntT(2)); |
| puppet1.apply(&mut child1_action).await?; |
| puppet1.apply(&mut child2_action).await?; |
| let mut puppet2 = puppet::tests::local_incomplete_puppet().await?; |
| puppet2.apply(&mut child2_action).await?; |
| puppet2.apply(&mut child1_action).await?; |
| assert_eq!(puppet1.read_data().await?.to_string(), puppet2.read_data().await?.to_string()); |
| puppet1.apply(&mut property1_action).await?; |
| puppet1.apply(&mut property2_action).await?; |
| puppet2.apply(&mut property2_action).await?; |
| puppet2.apply(&mut property1_action).await?; |
| assert_eq!(puppet1.read_data().await?.to_string(), puppet2.read_data().await?.to_string()); |
| // Make sure the tree distinguishes based on node position |
| puppet1 = puppet::tests::local_incomplete_puppet().await?; |
| puppet2 = puppet::tests::local_incomplete_puppet().await?; |
| let mut subchild2_action = create_node!(parent:1, id:2, name:"child2"); |
| puppet1.apply(&mut child1_action).await?; |
| puppet2.apply(&mut child1_action).await?; |
| puppet1.apply(&mut child2_action).await?; |
| puppet2.apply(&mut subchild2_action).await?; |
| assert_ne!(puppet1.read_data().await?.to_string(), puppet2.read_data().await?.to_string()); |
| // ... and property position |
| let mut subproperty2_action = |
| create_numeric_property!(parent:1, id:2, name:"prop2", value: Number::IntT(1)); |
| puppet1.apply(&mut child1_action).await?; |
| puppet2.apply(&mut child1_action).await?; |
| puppet1.apply(&mut property2_action).await?; |
| puppet2.apply(&mut subproperty2_action).await?; |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_bit_ops() -> Result<(), Error> { |
| assert_eq!(low_bits(0xff, 3), 7); |
| assert_eq!(low_bits(0x04, 3), 4); |
| assert_eq!(low_bits(0xf8, 3), 0); |
| assert_eq!(low_bits(0xab, 99), 0xab); |
| assert_eq!(low_bits(0xff, 0), 0); |
| assert_eq!(high_bits(0xff, 3), 0xe0); |
| assert_eq!(high_bits(0x20, 3), 0x20); |
| assert_eq!(high_bits(0x1f, 3), 0); |
| assert_eq!(high_bits(0xab, 99), 0xab); |
| assert_eq!(high_bits(0xff, 0), 0); |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_zero_bits() -> Result<(), Error> { |
| let mut buffer = [0u8; 48]; |
| for byte in 0..16 { |
| buffer[byte] = 0xff; |
| } |
| for byte in 32..48 { |
| buffer[byte] = 0xff; |
| } |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 1, 0).is_err()); |
| assert!(check_zero_bits(&buffer, &block, 0, 0).is_ok()); |
| assert!(check_zero_bits(&buffer, &block, 0, MAX_BLOCK_BITS).is_ok()); |
| } |
| // Don't mess with buffer[0]; that defines block size and type. |
| // The block I'm testing (index 1) is in between two all-ones blocks. |
| // Its bytes are thus 16..23 in the buffer. |
| buffer[1 + 16] = 1; |
| // Now bit 8 of the block is 1. Checking any range that includes bit 8 should give an |
| // error (even single-bit 8...8). Other ranges should succeed. |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 8, 8).is_err()); |
| assert!(check_zero_bits(&buffer, &block, 8, MAX_BLOCK_BITS).is_err()); |
| assert!(check_zero_bits(&buffer, &block, 9, MAX_BLOCK_BITS).is_ok()); |
| } |
| buffer[2 + 16] = 0x80; |
| // Now bits 8 and 23 are 1. The range 9...MAX_BLOCK_BITS that succeeded before should fail. |
| // 9...22 and 24...MAX_BLOCK_BITS should succeed. So should 24...63. |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 9, MAX_BLOCK_BITS).is_err()); |
| assert!(check_zero_bits(&buffer, &block, 9, 22).is_ok()); |
| assert!(check_zero_bits(&buffer, &block, 24, MAX_BLOCK_BITS).is_ok()); |
| assert!(check_zero_bits(&buffer, &block, 24, 63).is_ok()); |
| } |
| buffer[2 + 16] = 0x20; |
| // Now bits 8 and 21 are 1. This tests bit-checks in the middle of the byte. |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 16, 20).is_ok()); |
| assert!(check_zero_bits(&buffer, &block, 21, 21).is_err()); |
| assert!(check_zero_bits(&buffer, &block, 22, 63).is_ok()); |
| } |
| buffer[7 + 16] = 0x80; |
| // Now bits 8, 21, and 63 are 1. Checking 22...63 should fail; 22...62 should succeed. |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 22, 63).is_err()); |
| assert!(check_zero_bits(&buffer, &block, 22, 62).is_ok()); |
| } |
| buffer[3 + 16] = 0x10; |
| // Here I'm testing whether 1 bits in the bytes between the ends of the range are also |
| // detected (cause the check to fail) (to make sure my loop doesn't have an off by 1 error). |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 22, 62).is_err()); |
| } |
| buffer[3 + 16] = 0; |
| buffer[4 + 16] = 0x10; |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 22, 62).is_err()); |
| } |
| buffer[4 + 16] = 0; |
| buffer[5 + 16] = 0x10; |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 22, 62).is_err()); |
| } |
| buffer[5 + 16] = 0; |
| buffer[6 + 16] = 0x10; |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 22, 62).is_err()); |
| } |
| buffer[1 + 16] = 0x81; |
| // Testing whether I can correctly ignore 1 bits within a single byte that are outside |
| // the specified range, and detect 1 bits that are inside the range. |
| { |
| let block = Block::new(&buffer[..], 1); |
| assert!(check_zero_bits(&buffer, &block, 9, 14).is_ok()); |
| assert!(check_zero_bits(&buffer, &block, 8, 14).is_err()); |
| assert!(check_zero_bits(&buffer, &block, 9, 15).is_err()); |
| } |
| Ok(()) |
| } |
| |
| #[test] |
| fn test_reserved_fields() { |
| let mut buffer = [0u8; 4096]; |
| // VMO Header block (index 0) |
| const HEADER: usize = 0; |
| let mut header = BlockHeader(0); |
| header.set_order(0); |
| header.set_block_type(BlockType::Header.to_u8().unwrap()); |
| header.set_header_magic(constants::HEADER_MAGIC_NUMBER); |
| header.set_header_version(constants::HEADER_VERSION_NUMBER); |
| put_header(&header, &mut buffer, HEADER); |
| const VALUE: usize = 1; |
| let mut value_header = BlockHeader(0); |
| value_header.set_order(0); |
| value_header.set_block_type(BlockType::NodeValue.to_u8().unwrap()); |
| value_header.set_value_name_index(2); |
| value_header.set_value_parent_index(0); |
| put_header(&value_header, &mut buffer, VALUE); |
| // Root's Name block |
| const VALUE_NAME: usize = 2; |
| let mut header = BlockHeader(0); |
| header.set_order(0); |
| header.set_block_type(BlockType::Name.to_u8().unwrap()); |
| header.set_name_length(5); |
| put_header(&header, &mut buffer, VALUE_NAME); |
| copy_into(b"value", &mut buffer, VALUE_NAME * 16 + 8); |
| // Extent block (not linked into tree) |
| const EXTENT: usize = 3; |
| let mut header = BlockHeader(0); |
| header.set_order(0); |
| header.set_block_type(BlockType::Extent.to_u8().unwrap()); |
| header.set_extent_next_index(0); |
| put_header(&header, &mut buffer, EXTENT); |
| // Let's make sure it scans. |
| try_byte(&mut buffer, (16, 0), 0, Some("root ->\n> value ->")); |
| // Put garbage in a random FREE block body - should fail. |
| // TODO(fxbug.dev/39975): Depending on the resolution of fxbug.dev/40012, uncomment or delete this test. |
| //try_byte(&mut buffer, (6, 9), 42, None); |
| // Put garbage in a random FREE block header - should be fine. |
| try_byte(&mut buffer, (6, 7), 42, Some("root ->\n> value ->")); |
| // Put garbage in NAME header - should fail. |
| try_byte(&mut buffer, (VALUE_NAME, 7), 42, None); |
| // Put garbage in EXTENT header - should fail. |
| try_byte(&mut buffer, (EXTENT, 6), 42, None); |
| value_header.set_block_type(BlockType::ArrayValue.to_u8().unwrap()); |
| put_header(&value_header, &mut buffer, VALUE); |
| let mut array_subheader = BlockPayload(0); |
| array_subheader.set_array_entry_type(BlockType::IntValue.to_u8().unwrap()); |
| array_subheader.set_array_flags(ArrayFormat::Default.to_u8().unwrap()); |
| put_payload(&array_subheader, &mut buffer, VALUE); |
| try_byte(&mut buffer, (16, 0), 0, Some("root ->\n> value: IntArray([], Default)")); |
| // Put garbage in reserved part of Array spec, should fail. |
| try_byte(&mut buffer, (VALUE, 12), 42, None); |
| value_header.set_block_type(BlockType::IntValue.to_u8().unwrap()); |
| put_header(&value_header, &mut buffer, VALUE); |
| // Now the array spec is just a (large) value; it should succeed. |
| try_byte(&mut buffer, (VALUE, 12), 42, Some("root ->\n> value: Int(180388626436)")); |
| } |
| } |
