use crate::bytes::{get_u8, get_u64, put_u8, put_u64};
use super::ParseError;
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct ItemType(u8);
impl ItemType {
pub const INODE_ITEM: Self = Self(1);
pub const INODE_REF: Self = Self(12);
pub const INODE_EXTREF: Self = Self(13);
pub const XATTR_ITEM: Self = Self(24);
pub const VERITY_DESC_ITEM: Self = Self(36);
pub const VERITY_MERKLE_ITEM: Self = Self(37);
pub const FSCRYPT_INODE_CTX: Self = Self(41);
pub const FSCRYPT_CTX: Self = Self(42);
pub const ORPHAN_ITEM: Self = Self(48);
pub const DIR_LOG_ITEM: Self = Self(60);
pub const DIR_LOG_INDEX: Self = Self(72);
pub const DIR_ITEM: Self = Self(84);
pub const DIR_INDEX: Self = Self(96);
pub const EXTENT_DATA: Self = Self(108);
pub const EXTENT_CSUM: Self = Self(128);
pub const ROOT_ITEM: Self = Self(132);
pub const ROOT_BACKREF: Self = Self(144);
pub const ROOT_REF: Self = Self(156);
pub const EXTENT_ITEM: Self = Self(168);
pub const METADATA_ITEM: Self = Self(169);
pub const EXTENT_OWNER_REF: Self = Self(172);
pub const TREE_BLOCK_REF: Self = Self(176);
pub const EXTENT_DATA_REF: Self = Self(178);
pub const SHARED_BLOCK_REF: Self = Self(182);
pub const SHARED_DATA_REF: Self = Self(184);
pub const BLOCK_GROUP_ITEM: Self = Self(192);
pub const FREE_SPACE_INFO: Self = Self(198);
pub const FREE_SPACE_EXTENT: Self = Self(199);
pub const FREE_SPACE_BITMAP: Self = Self(200);
pub const DEV_EXTENT: Self = Self(204);
pub const DEV_ITEM: Self = Self(216);
pub const CHUNK_ITEM: Self = Self(228);
pub const RAID_STRIPE: Self = Self(230);
pub const QGROUP_STATUS: Self = Self(240);
pub const QGROUP_INFO: Self = Self(242);
pub const QGROUP_LIMIT: Self = Self(244);
pub const QGROUP_RELATION: Self = Self(246);
pub const TEMPORARY_ITEM: Self = Self(248);
pub const PERSISTENT_ITEM: Self = Self(249);
pub const DEV_REPLACE: Self = Self(250);
pub const UUID_SUBVOL: Self = Self(251);
pub const UUID_RECEIVED_SUBVOL: Self = Self(252);
pub const STRING_ITEM: Self = Self(253);
#[must_use]
pub const fn value(self) -> u8 {
self.0
}
#[must_use]
pub const fn from_value(value: u8) -> Self {
Self(value)
}
#[must_use]
pub const fn name(self) -> Option<&'static str> {
Some(match self {
Self::INODE_ITEM => "INODE_ITEM",
Self::INODE_REF => "INODE_REF",
Self::INODE_EXTREF => "INODE_EXTREF",
Self::XATTR_ITEM => "XATTR_ITEM",
Self::VERITY_DESC_ITEM => "VERITY_DESC_ITEM",
Self::VERITY_MERKLE_ITEM => "VERITY_MERKLE_ITEM",
Self::FSCRYPT_INODE_CTX => "FSCRYPT_INODE_CTX",
Self::FSCRYPT_CTX => "FSCRYPT_CTX",
Self::ORPHAN_ITEM => "ORPHAN_ITEM",
Self::DIR_LOG_ITEM => "DIR_LOG_ITEM",
Self::DIR_LOG_INDEX => "DIR_LOG_INDEX",
Self::DIR_ITEM => "DIR_ITEM",
Self::DIR_INDEX => "DIR_INDEX",
Self::EXTENT_DATA => "EXTENT_DATA",
Self::EXTENT_CSUM => "EXTENT_CSUM",
Self::ROOT_ITEM => "ROOT_ITEM",
Self::ROOT_BACKREF => "ROOT_BACKREF",
Self::ROOT_REF => "ROOT_REF",
Self::EXTENT_ITEM => "EXTENT_ITEM",
Self::METADATA_ITEM => "METADATA_ITEM",
Self::EXTENT_OWNER_REF => "EXTENT_OWNER_REF",
Self::TREE_BLOCK_REF => "TREE_BLOCK_REF",
Self::EXTENT_DATA_REF => "EXTENT_DATA_REF",
Self::SHARED_BLOCK_REF => "SHARED_BLOCK_REF",
Self::SHARED_DATA_REF => "SHARED_DATA_REF",
Self::BLOCK_GROUP_ITEM => "BLOCK_GROUP_ITEM",
Self::FREE_SPACE_INFO => "FREE_SPACE_INFO",
Self::FREE_SPACE_EXTENT => "FREE_SPACE_EXTENT",
Self::FREE_SPACE_BITMAP => "FREE_SPACE_BITMAP",
Self::DEV_EXTENT => "DEV_EXTENT",
Self::DEV_ITEM => "DEV_ITEM",
Self::CHUNK_ITEM => "CHUNK_ITEM",
Self::RAID_STRIPE => "RAID_STRIPE",
Self::QGROUP_STATUS => "QGROUP_STATUS",
Self::QGROUP_INFO => "QGROUP_INFO",
Self::QGROUP_LIMIT => "QGROUP_LIMIT",
Self::QGROUP_RELATION => "QGROUP_RELATION",
Self::TEMPORARY_ITEM => "TEMPORARY_ITEM",
Self::PERSISTENT_ITEM => "PERSISTENT_ITEM",
Self::DEV_REPLACE => "DEV_REPLACE",
Self::UUID_SUBVOL => "UUID_KEY_SUBVOL",
Self::UUID_RECEIVED_SUBVOL => "UUID_KEY_RECEIVED_SUBVOL",
Self::STRING_ITEM => "STRING_ITEM",
_ => return None,
})
}
}
pub mod objectid {
pub const ROOT_TREE: u64 = 1;
pub const DEV_ITEMS: u64 = 1;
pub const EXTENT_TREE: u64 = 2;
pub const CHUNK_TREE: u64 = 3;
pub const DEV_TREE: u64 = 4;
pub const FS_TREE: u64 = 5;
pub const ROOT_TREE_DIR: u64 = 6;
pub const CSUM_TREE: u64 = 7;
pub const QUOTA_TREE: u64 = 8;
pub const UUID_TREE: u64 = 9;
pub const FREE_SPACE_TREE: u64 = 10;
pub const BLOCK_GROUP_TREE: u64 = 11;
pub const RAID_STRIPE_TREE: u64 = 12;
pub const REMAP_TREE: u64 = 13;
pub const EXTENT_CSUM: u64 = u64::MAX - 9;
pub const FREE_SPACE: u64 = u64::MAX - 10;
pub const TREE_RELOC: u64 = u64::MAX - 7;
pub const DATA_RELOC_TREE: u64 = u64::MAX - 8;
pub const FIRST_FREE: u64 = 256;
pub const FIRST_CHUNK_TREE: u64 = 256;
pub const LAST_FREE: u64 = u64::MAX - 255;
#[must_use]
pub const fn name(objectid: u64) -> Option<&'static str> {
Some(match objectid {
ROOT_TREE => "ROOT_TREE",
EXTENT_TREE => "EXTENT_TREE",
CHUNK_TREE => "CHUNK_TREE",
DEV_TREE => "DEV_TREE",
FS_TREE => "FS_TREE",
ROOT_TREE_DIR => "ROOT_TREE_DIR",
CSUM_TREE => "CSUM_TREE",
QUOTA_TREE => "QUOTA_TREE",
UUID_TREE => "UUID_TREE",
FREE_SPACE_TREE => "FREE_SPACE_TREE",
BLOCK_GROUP_TREE => "BLOCK_GROUP_TREE",
RAID_STRIPE_TREE => "RAID_STRIPE_TREE",
REMAP_TREE => "REMAP_TREE",
TREE_RELOC => "TREE_RELOC",
DATA_RELOC_TREE => "DATA_RELOC_TREE",
EXTENT_CSUM => "EXTENT_CSUM",
FREE_SPACE => "FREE_SPACE",
_ => return None,
})
}
}
#[must_use]
pub fn name_hash(name: &[u8]) -> u64 {
u64::from(crate::crc32c(!1, name))
}
#[must_use]
pub fn extref_hash(parent_objectid: u64, name: &[u8]) -> u64 {
u64::from(crate::crc32c(parent_objectid as u32, name))
}
#[must_use]
pub fn uuid_key(uuid: [u8; 16]) -> (u64, u64) {
let (low, high) = uuid.split_at(8);
(
u64::from_le_bytes(low.try_into().expect("eight bytes")),
u64::from_le_bytes(high.try_into().expect("eight bytes")),
)
}
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
pub struct DiskKey {
pub objectid: u64,
pub kind: ItemType,
pub offset: u64,
}
impl DiskKey {
pub const SIZE: usize = 17;
pub const MIN: Self = Self::new(0, ItemType::from_value(0), 0);
#[must_use]
pub const fn new(objectid: u64, kind: ItemType, offset: u64) -> Self {
Self {
objectid,
kind,
offset,
}
}
#[must_use]
pub const fn first_of(objectid: u64, kind: ItemType) -> Self {
Self::new(objectid, kind, 0)
}
pub fn read_from(buf: &[u8]) -> Result<Self, ParseError> {
if buf.len() < Self::SIZE {
return Err(ParseError::TooShort {
structure: "btrfs_disk_key",
need: Self::SIZE,
got: buf.len(),
});
}
Ok(Self {
objectid: get_u64(buf, 0),
kind: ItemType::from_value(get_u8(buf, 8)),
offset: get_u64(buf, 9),
})
}
pub fn write_to(&self, buf: &mut [u8]) {
assert!(
buf.len() >= Self::SIZE,
"a key needs {} bytes and was given {}",
Self::SIZE,
buf.len()
);
put_u64(buf, 0, self.objectid);
put_u8(buf, 8, self.kind.value());
put_u64(buf, 9, self.offset);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_key_round_trips_through_its_seventeen_bytes() {
let key = DiskKey::new(
0x0123_4567_89ab_cdef,
ItemType::DIR_ITEM,
0xfedc_ba98_7654_3210,
);
let mut buf = [0u8; DiskKey::SIZE];
key.write_to(&mut buf);
assert_eq!(DiskKey::read_from(&buf).expect("a full key"), key);
assert_eq!(&buf[..8], &[0xef, 0xcd, 0xab, 0x89, 0x67, 0x45, 0x23, 0x01]);
assert_eq!(buf[8], 84);
assert_eq!(&buf[9..], &[0x10, 0x32, 0x54, 0x76, 0x98, 0xba, 0xdc, 0xfe]);
}
#[test]
fn a_buffer_shorter_than_a_key_holds_no_key() {
let err = DiskKey::read_from(&[0u8; DiskKey::SIZE - 1]).expect_err("sixteen bytes");
assert!(matches!(
err,
ParseError::TooShort {
need: 17,
got: 16,
..
}
));
}
#[test]
fn keys_sort_by_objectid_then_type_then_offset() {
let base = DiskKey::new(5, ItemType::DIR_ITEM, 100);
assert!(
base < DiskKey::new(6, ItemType::INODE_ITEM, 0),
"objectid outranks type"
);
assert!(
base < DiskKey::new(5, ItemType::DIR_INDEX, 0),
"type outranks offset"
);
assert!(base < DiskKey::new(5, ItemType::DIR_ITEM, 101));
assert!(
DiskKey::new(objectid::FS_TREE, ItemType::ROOT_ITEM, 0)
< DiskKey::new(objectid::DATA_RELOC_TREE, ItemType::ROOT_ITEM, 0)
);
}
#[test]
fn the_lowest_key_is_below_every_key_a_tree_can_hold() {
assert!(DiskKey::MIN <= DiskKey::new(0, ItemType::from_value(0), 0));
assert!(DiskKey::MIN < DiskKey::new(0, ItemType::from_value(0), 1));
assert_eq!(DiskKey::first_of(9, ItemType::UUID_SUBVOL).offset, 0);
}
#[test]
fn an_item_type_the_format_has_not_defined_keeps_its_byte_and_has_no_name() {
let unknown = ItemType::from_value(77);
assert_eq!(unknown.value(), 77);
assert_eq!(unknown.name(), None);
assert_eq!(ItemType::EXTENT_DATA.name(), Some("EXTENT_DATA"));
}
#[test]
fn the_two_bytes_that_name_two_records_answer_with_the_current_name() {
assert_eq!(ItemType::from_value(248).name(), Some("TEMPORARY_ITEM"));
assert_eq!(ItemType::from_value(249).name(), Some("PERSISTENT_ITEM"));
}
#[test]
fn the_relocation_roots_are_named_and_sit_at_the_top_of_the_range() {
assert_eq!(objectid::DATA_RELOC_TREE, 18_446_744_073_709_551_607);
assert_eq!(
objectid::name(objectid::DATA_RELOC_TREE),
Some("DATA_RELOC_TREE")
);
assert_eq!(objectid::name(objectid::TREE_RELOC), Some("TREE_RELOC"));
assert_eq!(objectid::name(257), None);
}
#[test]
fn a_subvolume_uuid_splits_into_the_key_the_baseline_writes_for_it() {
let uuid = [
0x79, 0xcc, 0x5e, 0x40, 0x2a, 0xab, 0x40, 0xea, 0x93, 0xf9, 0x6f, 0x9b, 0xc0, 0x62,
0x3d, 0x48,
];
assert_eq!(
uuid_key(uuid),
(0xea40_ab2a_405e_cc79, 0x483d_62c0_9b6f_f993)
);
assert_eq!(uuid_key([0; 16]), (0, 0));
}
}