use super::io::*;
use super::*;
impl<'a> GraphVerifier<'a> {
pub(super) fn walk_objects(&mut self) -> Result<(), String> {
let Some(tail) = self.object_walk_tail()? else {
return Ok(());
};
let mut offset = self.header.header_size;
let mut state = ObjectWalkState::default();
loop {
self.validate_walk_offset(offset, tail)?;
let (obj, aligned_size) = self.read_walk_object(offset)?;
self.record_walk_object(offset, obj);
self.parse_walk_object(offset, obj, &mut state)?;
if offset == tail {
break;
}
offset = offset
.checked_add(aligned_size)
.ok_or_else(|| "object offset overflow".to_string())?;
}
self.validate_walk_result(tail, &state)
}
pub(super) fn object_walk_tail(&self) -> Result<Option<u64>, String> {
let tail = self.header.tail_object_offset;
if tail == 0 {
if self.header.n_objects != 0 {
return Err("tail_object_offset is zero with objects recorded".to_string());
}
return Ok(None);
}
if tail < self.header.header_size {
return Err("tail_object_offset is before header_size".to_string());
}
Ok(Some(tail))
}
pub(super) fn validate_walk_offset(&self, offset: u64, tail: u64) -> Result<(), String> {
if offset > tail {
return Err("object walk skipped past tail_object_offset".to_string());
}
let max_header_offset = (self.data.len() as u64)
.checked_sub(OBJECT_HEADER_SIZE)
.ok_or_else(|| "file too small for object header".to_string())?;
if offset > max_header_offset {
return Err(format!(
"object header at offset {offset} exceeds file bounds"
));
}
Ok(())
}
pub(super) fn read_walk_object(&self, offset: u64) -> Result<(ObjectHeader, u64), String> {
let obj = ObjectHeader {
typ: byte_at(self.data, offset)?,
flags: byte_at(self.data, offset + 1)?,
size: u64_at_u64(self.data, offset + 8)?,
};
let aligned_size = align8_checked(obj.size).ok_or_else(|| {
format!(
"object size {} overflows alignment at offset {offset}",
obj.size
)
})?;
self.validate_walk_object_envelope(offset, obj, aligned_size)?;
self.validate_walk_object_flags(offset, obj)?;
Ok((obj, aligned_size))
}
pub(super) fn validate_walk_object_envelope(
&self,
offset: u64,
obj: ObjectHeader,
aligned_size: u64,
) -> Result<(), String> {
if obj.typ == 0 && obj.size == 0 {
return Err(format!("zero object before tail at offset {offset}"));
}
if !(OBJECT_TYPE_DATA..=OBJECT_TYPE_TAG).contains(&obj.typ) {
return Err(format!(
"unknown object type {} at offset {offset}",
obj.typ
));
}
if obj.size < OBJECT_HEADER_SIZE {
return Err(format!(
"object size {} too small at offset {offset}",
obj.size
));
}
if aligned_size == 0 || aligned_size > self.data.len() as u64 - offset {
return Err(format!("object at offset {offset} exceeds file bounds"));
}
if offset % 8 != 0 {
return Err(format!("object offset {offset} is not aligned"));
}
Ok(())
}
pub(super) fn validate_walk_object_flags(
&self,
offset: u64,
obj: ObjectHeader,
) -> Result<(), String> {
let flags = obj.flags;
if flags & !OBJECT_COMPRESSED_MASK != 0 {
return Err(format!(
"object at offset {offset} has unknown flags 0x{flags:x}"
));
}
if (flags & OBJECT_COMPRESSED_MASK).count_ones() > 1 {
return Err(format!(
"object at offset {offset} has multiple compression flags"
));
}
if obj.typ != OBJECT_TYPE_DATA && flags != 0 {
return Err(format!(
"object type {} at offset {offset} has compression flags",
obj.typ
));
}
self.validate_compressed_data_header_flag(offset, flags)
}
pub(super) fn validate_compressed_data_header_flag(
&self,
offset: u64,
flags: u8,
) -> Result<(), String> {
if flags & OBJECT_COMPRESSED_XZ != 0
&& self.header.incompatible_flags & INCOMPATIBLE_COMPRESSED_XZ == 0
{
return Err(format!(
"XZ DATA object without matching header flag at offset {offset}"
));
}
if flags & OBJECT_COMPRESSED_LZ4 != 0
&& self.header.incompatible_flags & INCOMPATIBLE_COMPRESSED_LZ4 == 0
{
return Err(format!(
"LZ4 DATA object without matching header flag at offset {offset}"
));
}
if flags & OBJECT_COMPRESSED_ZSTD != 0
&& self.header.incompatible_flags & INCOMPATIBLE_COMPRESSED_ZSTD == 0
{
return Err(format!(
"ZSTD DATA object without matching header flag at offset {offset}"
));
}
Ok(())
}
pub(super) fn record_walk_object(&mut self, offset: u64, obj: ObjectHeader) {
self.spans.insert(offset, obj);
self.order.push(offset);
self.counts[obj.typ as usize] += 1;
}
pub(super) fn parse_walk_object(
&mut self,
offset: u64,
obj: ObjectHeader,
state: &mut ObjectWalkState,
) -> Result<(), String> {
match obj.typ {
OBJECT_TYPE_DATA => self.parse_data(offset, obj),
OBJECT_TYPE_FIELD => self.parse_field(offset, obj),
OBJECT_TYPE_ENTRY => self.parse_walk_entry(offset, obj, state),
OBJECT_TYPE_DATA_HASH_TABLE | OBJECT_TYPE_FIELD_HASH_TABLE => {
self.parse_hash_table(offset, obj)
}
OBJECT_TYPE_ENTRY_ARRAY => self.parse_walk_entry_array(offset, obj),
OBJECT_TYPE_TAG => self.parse_walk_tag(offset, obj, state),
_ => unreachable!(),
}
}
pub(super) fn parse_walk_entry(
&mut self,
offset: u64,
obj: ObjectHeader,
state: &mut ObjectWalkState,
) -> Result<(), String> {
let entry = self.parse_entry(offset, obj)?;
self.validate_entry_tag_order(offset, &entry, state)?;
self.validate_entry_seqnum_order(offset, &entry, state)?;
self.validate_entry_monotonic_order(offset, &entry, state)?;
self.validate_entry_realtime_order(offset, &entry, state)?;
Ok(())
}
pub(super) fn validate_entry_tag_order(
&self,
offset: u64,
entry: &EntryObject,
state: &ObjectWalkState,
) -> Result<(), String> {
if self.header.compatible_flags & COMPATIBLE_SEALED != 0
&& self.counts[OBJECT_TYPE_TAG as usize] == 0
{
return Err(format!("first entry before first tag at offset {offset}"));
}
if entry.realtime < state.last_tag_realtime {
return Err(format!("older entry after newer tag at offset {offset}"));
}
Ok(())
}
pub(super) fn validate_entry_seqnum_order(
&self,
offset: u64,
entry: &EntryObject,
state: &mut ObjectWalkState,
) -> Result<(), String> {
if !state.entry_seqnum_set && entry.seqnum != self.header.head_entry_seqnum {
return Err(format!("head entry seqnum mismatch at offset {offset}"));
}
if state.entry_seqnum_set && state.entry_seqnum >= entry.seqnum {
return Err(format!("entry seqnum out of sync at offset {offset}"));
}
state.entry_seqnum = entry.seqnum;
state.entry_seqnum_set = true;
Ok(())
}
pub(super) fn validate_entry_monotonic_order(
&self,
offset: u64,
entry: &EntryObject,
state: &mut ObjectWalkState,
) -> Result<(), String> {
if state.entry_monotonic_set
&& entry.boot_id == state.entry_boot_id
&& state.entry_monotonic > entry.monotonic
{
return Err(format!("entry monotonic out of sync at offset {offset}"));
}
state.entry_monotonic = entry.monotonic;
state.entry_boot_id = entry.boot_id;
state.entry_monotonic_set = true;
Ok(())
}
pub(super) fn validate_entry_realtime_order(
&self,
offset: u64,
entry: &EntryObject,
state: &mut ObjectWalkState,
) -> Result<(), String> {
if !state.entry_realtime_set && entry.realtime != self.header.head_entry_realtime {
return Err(format!("head entry realtime mismatch at offset {offset}"));
}
state.entry_realtime = entry.realtime;
state.entry_realtime_set = true;
Ok(())
}
pub(super) fn parse_walk_entry_array(
&mut self,
offset: u64,
obj: ObjectHeader,
) -> Result<(), String> {
self.parse_entry_array(offset, obj)?;
if offset != self.header.entry_array_offset {
return Ok(());
}
if self.main_entry_array_found {
return Err("more than one main entry array".to_string());
}
self.main_entry_array_found = true;
Ok(())
}
pub(super) fn parse_walk_tag(
&self,
offset: u64,
obj: ObjectHeader,
state: &mut ObjectWalkState,
) -> Result<(), String> {
if self.header.compatible_flags & COMPATIBLE_SEALED == 0 {
return Err("TAG object in unsealed file".to_string());
}
if obj.size != TAG_OBJECT_SIZE {
return Err(format!("invalid TAG size at offset {offset}"));
}
let seqnum = u64_at_u64(self.data, offset + 16)?;
if seqnum != self.counts[OBJECT_TYPE_TAG as usize] {
return Err(format!("TAG seqnum mismatch at offset {offset}"));
}
if state.entry_realtime_set {
state.last_tag_realtime = state.entry_realtime;
}
Ok(())
}
pub(super) fn validate_walk_result(
&self,
tail: u64,
state: &ObjectWalkState,
) -> Result<(), String> {
if self.order.last().copied() != Some(tail) {
return Err("tail_object_offset does not point to walked tail".to_string());
}
if state.entry_seqnum_set && state.entry_seqnum != self.header.tail_entry_seqnum {
return Err("tail_entry_seqnum mismatch".to_string());
}
if state.entry_monotonic_set
&& self.header.compatible_flags & COMPATIBLE_TAIL_ENTRY_BOOT_ID != 0
&& state.entry_boot_id == self.header.tail_entry_boot_id
&& state.entry_monotonic != self.header.tail_entry_monotonic
{
return Err("tail_entry_monotonic mismatch".to_string());
}
if state.entry_realtime_set && state.entry_realtime != self.header.tail_entry_realtime {
return Err("tail_entry_realtime mismatch".to_string());
}
Ok(())
}
pub(super) fn parse_data(&mut self, offset: u64, obj: ObjectHeader) -> Result<(), String> {
let payload = self.data_payload(offset, obj)?;
self.validate_data_hash(offset, payload.as_ref())?;
let data = self.read_data_object(offset)?;
self.validate_data_object(offset, &data)?;
self.data_objects.insert(offset, data);
Ok(())
}
pub(super) fn data_payload(
&self,
offset: u64,
obj: ObjectHeader,
) -> Result<Cow<'_, [u8]>, String> {
let payload_offset = if self.compact {
COMPACT_DATA_OBJECT_HEADER_SIZE
} else {
DATA_OBJECT_HEADER_SIZE
};
if obj.size <= payload_offset {
return Err(format!("DATA object at offset {offset} has no payload"));
}
let payload = slice_u64(self.data, offset + payload_offset, offset + obj.size)?;
if obj.flags == 0 {
return Ok(Cow::Borrowed(payload));
}
decompress_payload(obj.flags, payload)
.map(Cow::Owned)
.map_err(|err| format!("DATA decompression failed at offset {offset}: {err}"))
}
pub(super) fn validate_data_hash(
&self,
offset: u64,
hash_payload: &[u8],
) -> Result<(), String> {
let stored_hash = u64_at_u64(self.data, offset + 16)?;
let computed_hash = self.hash(hash_payload);
if stored_hash == computed_hash {
return Ok(());
}
Err(format!(
"DATA hash mismatch at offset {offset}: {stored_hash:#x} != {computed_hash:#x}"
))
}
pub(super) fn read_data_object(&self, offset: u64) -> Result<DataObject, String> {
let entry_offset = u64_at_u64(self.data, offset + 40)?;
Ok(DataObject {
hash: u64_at_u64(self.data, offset + 16)?,
next_hash_offset: u64_at_u64(self.data, offset + 24)?,
next_field_offset: u64_at_u64(self.data, offset + 32)?,
entry_offset,
entry_array_offset: u64_at_u64(self.data, offset + 48)?,
n_entries: u64_at_u64(self.data, offset + 56)?,
})
}
pub(super) fn validate_data_object(
&self,
offset: u64,
data: &DataObject,
) -> Result<(), String> {
if (data.entry_offset == 0) != (data.n_entries == 0) {
return Err(format!("DATA object at offset {offset} has bad n_entries"));
}
self.valid_offset(data.next_hash_offset, "DATA next_hash_offset")?;
self.valid_offset(data.next_field_offset, "DATA next_field_offset")?;
self.valid_offset(data.entry_offset, "DATA entry_offset")?;
self.valid_offset(data.entry_array_offset, "DATA entry_array_offset")?;
self.validate_data_entry_array_presence(offset, data)
}
pub(super) fn validate_data_entry_array_presence(
&self,
offset: u64,
data: &DataObject,
) -> Result<(), String> {
if data.n_entries < 2 && data.entry_array_offset != 0 {
return Err(format!(
"DATA object at offset {offset} has unexpected entry array"
));
}
if data.n_entries >= 2 && data.entry_array_offset == 0 {
return Err(format!(
"DATA object at offset {offset} is missing entry array"
));
}
Ok(())
}
pub(super) fn parse_entry(
&mut self,
offset: u64,
obj: ObjectHeader,
) -> Result<EntryObject, String> {
let item_size = self.entry_item_size();
self.validate_entry_size(offset, obj, item_size)?;
let mut entry = self.read_entry_object(offset)?;
self.read_entry_items(offset, obj, item_size, &mut entry)?;
self.validate_entry_items(offset, &entry)?;
self.entry_objects.insert(offset, entry.clone());
Ok(entry)
}
pub(super) fn entry_item_size(&self) -> u64 {
if self.compact {
COMPACT_ENTRY_ITEM_SIZE
} else {
REGULAR_ENTRY_ITEM_SIZE
}
}
pub(super) fn validate_entry_size(
&self,
offset: u64,
obj: ObjectHeader,
item_size: u64,
) -> Result<(), String> {
if obj.size < ENTRY_OBJECT_HEADER_SIZE {
return Err(format!("ENTRY object at offset {offset} is too small"));
}
if (obj.size - ENTRY_OBJECT_HEADER_SIZE) % item_size != 0 {
return Err(format!(
"ENTRY object at offset {offset} has unaligned items"
));
}
Ok(())
}
pub(super) fn read_entry_object(&self, offset: u64) -> Result<EntryObject, String> {
let entry = EntryObject {
seqnum: u64_at_u64(self.data, offset + 16)?,
realtime: u64_at_u64(self.data, offset + 24)?,
monotonic: u64_at_u64(self.data, offset + 32)?,
boot_id: bytes16_at_u64(self.data, offset + 40)?,
items: Vec::new(),
};
if entry.seqnum == 0 {
return Err(format!("ENTRY object at offset {offset} has zero seqnum"));
}
if entry.realtime == 0 {
return Err(format!("ENTRY object at offset {offset} has zero realtime"));
}
Ok(entry)
}
pub(super) fn read_entry_items(
&self,
offset: u64,
obj: ObjectHeader,
item_size: u64,
entry: &mut EntryObject,
) -> Result<(), String> {
let mut item_offset = offset + ENTRY_OBJECT_HEADER_SIZE;
while item_offset < offset + obj.size {
let item = self.read_entry_item(item_offset)?;
if item == 0 {
return Err(format!("ENTRY object at offset {offset} has zero item"));
}
self.valid_offset(item, "ENTRY item")?;
entry.items.push(item);
item_offset += item_size;
}
Ok(())
}
pub(super) fn read_entry_item(&self, item_offset: u64) -> Result<u64, String> {
if self.compact {
return Ok(u32_at_u64(self.data, item_offset)? as u64);
}
u64_at_u64(self.data, item_offset)
}
pub(super) fn validate_entry_items(
&self,
offset: u64,
entry: &EntryObject,
) -> Result<(), String> {
if entry.items.is_empty() {
return Err(format!("ENTRY object at offset {offset} has no items"));
}
Ok(())
}
pub(super) fn parse_field(&mut self, offset: u64, obj: ObjectHeader) -> Result<(), String> {
if obj.size <= FIELD_OBJECT_HEADER_SIZE {
return Err(format!("FIELD object at offset {offset} has no payload"));
}
let payload = slice_u64(
self.data,
offset + FIELD_OBJECT_HEADER_SIZE,
offset + obj.size,
)?;
let stored_hash = u64_at_u64(self.data, offset + 16)?;
let computed_hash = self.hash(payload);
if stored_hash != computed_hash {
return Err(format!(
"FIELD hash mismatch at offset {offset}: {stored_hash:#x} != {computed_hash:#x}"
));
}
self.valid_offset(
u64_at_u64(self.data, offset + 24)?,
"FIELD next_hash_offset",
)?;
self.valid_offset(
u64_at_u64(self.data, offset + 32)?,
"FIELD head_data_offset",
)?;
Ok(())
}
pub(super) fn parse_hash_table(&self, offset: u64, obj: ObjectHeader) -> Result<(), String> {
if obj.size < OBJECT_HEADER_SIZE + HASH_ITEM_SIZE {
return Err(format!("hash table at offset {offset} is too small"));
}
if (obj.size - OBJECT_HEADER_SIZE) % HASH_ITEM_SIZE != 0 {
return Err(format!("hash table at offset {offset} has unaligned items"));
}
let (table_offset, table_size) = if obj.typ == OBJECT_TYPE_DATA_HASH_TABLE {
(
self.header.data_hash_table_offset,
self.header.data_hash_table_size,
)
} else {
(
self.header.field_hash_table_offset,
self.header.field_hash_table_size,
)
};
if table_offset != offset + OBJECT_HEADER_SIZE {
return Err(format!(
"hash table header offset mismatch at offset {offset}"
));
}
if table_size != obj.size - OBJECT_HEADER_SIZE {
return Err(format!(
"hash table header size mismatch at offset {offset}"
));
}
let mut item_offset = offset + OBJECT_HEADER_SIZE;
while item_offset < offset + obj.size {
let head = u64_at_u64(self.data, item_offset)?;
let tail = u64_at_u64(self.data, item_offset + 8)?;
if (head == 0) != (tail == 0) {
return Err("hash bucket head/tail mismatch".to_string());
}
self.valid_offset(head, "hash bucket head")?;
self.valid_offset(tail, "hash bucket tail")?;
item_offset += HASH_ITEM_SIZE;
}
Ok(())
}
pub(super) fn parse_entry_array(
&mut self,
offset: u64,
obj: ObjectHeader,
) -> Result<(), String> {
let item_size = if self.compact {
COMPACT_OFFSET_ARRAY_ITEM_SIZE
} else {
REGULAR_OFFSET_ARRAY_ITEM_SIZE
};
if obj.size < OFFSET_ARRAY_OBJECT_HEADER_SIZE + item_size {
return Err(format!(
"ENTRY_ARRAY object at offset {offset} is too small"
));
}
if (obj.size - OFFSET_ARRAY_OBJECT_HEADER_SIZE) % item_size != 0 {
return Err(format!(
"ENTRY_ARRAY object at offset {offset} has unaligned items"
));
}
let mut array = EntryArray {
next: u64_at_u64(self.data, offset + 16)?,
items: Vec::new(),
};
self.valid_offset(array.next, "ENTRY_ARRAY next")?;
let mut item_offset = offset + OFFSET_ARRAY_OBJECT_HEADER_SIZE;
while item_offset < offset + obj.size {
let item = if self.compact {
u32_at_u64(self.data, item_offset)? as u64
} else {
u64_at_u64(self.data, item_offset)?
};
if item != 0 {
self.valid_offset(item, "ENTRY_ARRAY item")?;
}
array.items.push(item);
item_offset += item_size;
}
self.entry_arrays.insert(offset, array);
Ok(())
}
}