use super::{ParseError, get_u8, get_u16, get_u32, put_u16, put_u32};
use crate::acl::{Acl, AclEntry, AclError, AclQualifier, TAG_GROUP, TAG_USER};
use crate::xattr::Xattr;
pub(crate) const XATTR_MAGIC: u32 = 0xEA02_0000;
const ACL_VERSION: u32 = 0x0001;
#[must_use]
pub fn encode_acl(acl: &Acl) -> Vec<u8> {
let entries = acl.entries();
let mut out = Vec::with_capacity(4 + entries.len() * 8);
out.extend_from_slice(&ACL_VERSION.to_le_bytes());
for e in entries {
let (tag, id) = e.who.tag_and_id();
out.extend_from_slice(&tag.to_le_bytes());
out.extend_from_slice(&e.perm.to_le_bytes());
if let Some(id) = id {
out.extend_from_slice(&id.to_le_bytes());
}
}
out
}
pub fn decode_acl(bytes: &[u8]) -> Result<Acl, AclError> {
if bytes.len() < 4 {
return Err(AclError::Malformed {
reason: "shorter than the version header",
});
}
let (header, mut rest) = bytes.split_at(4);
let version = u32::from_le_bytes(header.try_into().expect("split at four bytes"));
if version != ACL_VERSION {
return Err(AclError::Malformed {
reason: "unexpected version",
});
}
let mut entries = Vec::new();
while !rest.is_empty() {
if rest.len() < 4 {
return Err(AclError::Malformed {
reason: "truncated entry",
});
}
let tag = get_u16(rest, 0);
let perm = get_u16(rest, 2);
rest = &rest[4..];
let id = if matches!(tag, TAG_USER | TAG_GROUP) {
if rest.len() < 4 {
return Err(AclError::Malformed {
reason: "truncated entry id",
});
}
let id = get_u32(rest, 0);
rest = &rest[4..];
id
} else {
0
};
let who = AclQualifier::from_tag(tag, id).ok_or(AclError::Malformed {
reason: "unknown tag",
})?;
entries.push(AclEntry { who, perm });
}
Acl::new(entries)
}
const IBODY_HEADER_LEN: usize = 4;
const BLOCK_HEADER_LEN: usize = 32;
pub(crate) const CHECKSUM_OFFSET: usize = 16;
const ENTRY_HEADER_LEN: usize = 16;
const fn align4(n: usize) -> usize {
(n + 3) & !3
}
const PREFIXES: &[(u8, &[u8])] = &[
(2, b"system.posix_acl_access"),
(3, b"system.posix_acl_default"),
(8, b"system.richacl"),
(1, b"user."),
(7, b"system."),
(4, b"trusted."),
(6, b"security."),
];
fn split_name(name: &[u8]) -> (u8, &[u8]) {
for &(index, prefix) in PREFIXES {
if matches!(index, 2 | 3 | 8) {
if name == prefix {
return (index, b"");
}
} else if let Some(rest) = name.strip_prefix(prefix) {
return (index, rest);
}
}
(0, name)
}
pub(crate) fn has_empty_name(name: &[u8]) -> bool {
let (index, stored) = split_name(name);
stored.is_empty() && !matches!(index, 2 | 3 | 8)
}
fn join_name(index: u8, stored: &[u8]) -> Vec<u8> {
for &(i, prefix) in PREFIXES {
if i == index {
let mut out = prefix.to_vec();
out.extend_from_slice(stored);
return out;
}
}
stored.to_vec()
}
fn hash_entry(name: &[u8], value: &[u8]) -> u32 {
let named = name
.iter()
.fold(0u32, |hash, &byte| hash.rotate_left(5) ^ u32::from(byte));
value.chunks(4).fold(named, |hash, chunk| {
let mut word = [0u8; 4];
word[..chunk.len()].copy_from_slice(chunk);
hash.rotate_left(16) ^ u32::from_le_bytes(word)
})
}
fn block_hash(entry_hashes: &[u32]) -> u32 {
if entry_hashes.contains(&0) {
return 0;
}
entry_hashes
.iter()
.fold(0, |hash, &entry| hash.rotate_left(16) ^ entry)
}
fn packed_len(attrs: &[Xattr]) -> usize {
let mut total = 4;
for x in attrs {
let (_, stored) = split_name(&x.name);
total += align4(ENTRY_HEADER_LEN + stored.len());
total += align4(x.value.len());
}
total
}
pub(crate) fn block_len(attrs: &[Xattr]) -> usize {
BLOCK_HEADER_LEN + packed_len(attrs)
}
fn attr_len(x: &Xattr) -> usize {
let (_, stored) = split_name(&x.name);
align4(ENTRY_HEADER_LEN + stored.len()) + align4(x.value.len())
}
pub(crate) fn split_for_storage(attrs: &[Xattr], region_len: usize) -> (Vec<Xattr>, Vec<Xattr>) {
let mut inline_free = region_len.saturating_sub(IBODY_HEADER_LEN + 4);
let mut inline = Vec::new();
let mut spilled = Vec::new();
for x in sorted(attrs) {
let need = attr_len(&x);
if need <= inline_free {
inline_free -= need;
inline.push(x);
} else {
spilled.push(x);
}
}
(inline, spilled)
}
pub(crate) fn longest_stored_name(attrs: &[Xattr]) -> usize {
attrs
.iter()
.map(|x| split_name(&x.name).1.len())
.max()
.unwrap_or(0)
}
fn sorted(attrs: &[Xattr]) -> Vec<Xattr> {
let mut v = attrs.to_vec();
v.sort_by(|a, b| {
let (ia, na) = split_name(&a.name);
let (ib, nb) = split_name(&b.name);
ia.cmp(&ib).then(na.len().cmp(&nb.len())).then(na.cmp(nb))
});
v
}
pub(crate) fn encode_inline(attrs: &[Xattr], region_len: usize) -> Option<Vec<u8>> {
if attrs.is_empty() {
return Some(vec![0u8; region_len]);
}
let attrs = sorted(attrs);
if IBODY_HEADER_LEN + packed_len(&attrs) > region_len {
return None;
}
let mut buf = vec![0u8; region_len];
put_u32(&mut buf, 0, XATTR_MAGIC);
let base = IBODY_HEADER_LEN;
let mut entry_off = base;
let mut value_off = region_len;
for x in &attrs {
let (index, stored) = split_name(&x.name);
value_off -= align4(x.value.len());
buf[value_off..value_off + x.value.len()].copy_from_slice(&x.value);
let value_offs = if x.value.is_empty() {
0
} else {
value_off - base
};
write_entry(
&mut buf,
entry_off,
index,
stored,
x.value.len(),
value_offs,
0,
);
entry_off += align4(ENTRY_HEADER_LEN + stored.len());
}
Some(buf)
}
pub(crate) fn encode_block(attrs: &[Xattr], block_size: usize) -> Vec<u8> {
let attrs = sorted(attrs);
assert!(
block_len(&attrs) <= block_size,
"xattr entries and values overflow the block"
);
let mut buf = vec![0u8; block_size];
let mut entry_off = BLOCK_HEADER_LEN;
let mut value_off = block_size;
let mut hashes = Vec::with_capacity(attrs.len());
for x in &attrs {
let (index, stored) = split_name(&x.name);
value_off -= align4(x.value.len());
buf[value_off..value_off + x.value.len()].copy_from_slice(&x.value);
let e_hash = hash_entry(stored, &x.value);
hashes.push(e_hash);
let value_offs = if x.value.is_empty() { 0 } else { value_off };
write_entry(
&mut buf,
entry_off,
index,
stored,
x.value.len(),
value_offs,
e_hash,
);
entry_off += align4(ENTRY_HEADER_LEN + stored.len());
}
assert!(
entry_off + 4 <= value_off,
"xattr entries and values overflow the block"
);
put_u32(&mut buf, 0, XATTR_MAGIC);
put_u32(&mut buf, 4, 1); put_u32(&mut buf, 8, 1); put_u32(&mut buf, 12, block_hash(&hashes));
buf
}
fn write_entry(
buf: &mut [u8],
off: usize,
name_index: u8,
stored: &[u8],
value_size: usize,
value_offs: usize,
e_hash: u32,
) {
assert!(
stored.len() <= 255,
"an xattr stored name is at most 255 bytes"
);
buf[off] = stored.len() as u8;
buf[off + 1] = name_index;
put_u16(buf, off + 2, value_offs as u16);
put_u32(buf, off + 4, 0); put_u32(buf, off + 8, value_size as u32);
put_u32(buf, off + 12, e_hash);
buf[off + ENTRY_HEADER_LEN..off + ENTRY_HEADER_LEN + stored.len()].copy_from_slice(stored);
}
#[cfg(test)]
pub(crate) fn parse_inline(region: &[u8]) -> Result<Vec<Xattr>, ParseError> {
Ok(attributes(parse_inline_stored(region)?))
}
pub(crate) fn parse_inline_stored(region: &[u8]) -> Result<Vec<Stored>, ParseError> {
if region.len() < IBODY_HEADER_LEN || get_u32(region, 0) != XATTR_MAGIC {
return Ok(Vec::new());
}
parse_entries(region, IBODY_HEADER_LEN, IBODY_HEADER_LEN)
}
#[cfg(test)]
pub(crate) fn parse_block(block: &[u8]) -> Result<Vec<Xattr>, ParseError> {
Ok(attributes(parse_block_stored(block)?))
}
pub(crate) fn parse_block_stored(block: &[u8]) -> Result<Vec<Stored>, ParseError> {
if block.len() < BLOCK_HEADER_LEN || get_u32(block, 0) != XATTR_MAGIC {
return Ok(Vec::new());
}
parse_entries(block, BLOCK_HEADER_LEN, 0)
}
#[cfg(test)]
fn attributes(stored: Vec<Stored>) -> Vec<Xattr> {
stored
.into_iter()
.filter(|entry| !entry.is_the_formats())
.map(|entry| Xattr {
name: entry.name,
value: match entry.value {
Value::Here(value) => value,
Value::InInode { .. } => Vec::new(),
},
})
.collect()
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) struct Stored {
pub(crate) name: Vec<u8>,
pub(crate) index: u8,
pub(crate) value: Value,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub(crate) enum Value {
Here(Vec<u8>),
InInode {
inode: u32,
size: u32,
},
}
impl Stored {
pub(crate) fn is_the_formats(&self) -> bool {
(self.index == 9 && self.name == b"c") || (self.index == 7 && self.name == b"system.data")
}
}
fn parse_entries(
buf: &[u8],
first_entry: usize,
value_base: usize,
) -> Result<Vec<Stored>, ParseError> {
let mut out = Vec::new();
let mut off = first_entry;
let mut value_bytes = 0usize;
loop {
if off + 4 <= buf.len() && get_u32(buf, off) == 0 {
break;
}
if off + ENTRY_HEADER_LEN > buf.len() {
return Err(ParseError::TooShort {
structure: "XattrEntry",
need: off + ENTRY_HEADER_LEN,
got: buf.len(),
});
}
let name_len = get_u8(buf, off) as usize;
let name_index = get_u8(buf, off + 1);
let value_offs = get_u16(buf, off + 2) as usize;
let value_inum = get_u32(buf, off + 4);
let value_size = get_u32(buf, off + 8) as usize;
let name_end = off + ENTRY_HEADER_LEN + name_len;
let stored = buf
.get(off + ENTRY_HEADER_LEN..name_end)
.ok_or(ParseError::TooShort {
structure: "XattrName",
need: name_end,
got: buf.len(),
})?;
let value = if value_inum != 0 {
Value::InInode {
inode: value_inum,
size: u32::try_from(value_size).unwrap_or(u32::MAX),
}
} else {
let vstart = value_base + value_offs;
let vend = vstart
.checked_add(value_size)
.ok_or(ParseError::InvalidField {
structure: "XattrEntry",
field: "e_value_size",
value: value_size as u64,
})?;
value_bytes = value_bytes.saturating_add(value_size);
if value_bytes > buf.len() {
return Err(ParseError::InvalidField {
structure: "XattrEntry",
field: "e_value_size",
value: value_bytes as u64,
});
}
Value::Here(
buf.get(vstart..vend)
.ok_or(ParseError::InvalidField {
structure: "XattrEntry",
field: "e_value_offs",
value: value_offs as u64,
})?
.to_vec(),
)
};
out.push(Stored {
name: join_name(name_index, stored),
index: name_index,
value,
});
off = name_end.next_multiple_of(4);
}
Ok(out)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_list_ending_within_a_header_of_its_region_ends_at_its_zero_word() {
let mut region = vec![0u8; 96];
put_u32(&mut region, 0, XATTR_MAGIC);
for k in 0..4u8 {
let at = 4 + usize::from(k) * 20;
region[at] = 2; region[at + 1] = 1; put_u32(&mut region, at + 4, 24 + u32::from(k)); put_u32(&mut region, at + 8, 2000); region[at + 16..at + 18].copy_from_slice(&[b'm', b'1' + k]);
}
let stored = parse_inline_stored(®ion).expect("the list ends at its zero word");
assert_eq!(stored.len(), 4);
assert_eq!(
stored[3].value,
Value::InInode {
inode: 27,
size: 2000
}
);
}
fn sample_acl() -> Acl {
Acl::new(vec![
AclEntry {
who: AclQualifier::Other,
perm: Acl::READ,
},
AclEntry {
who: AclQualifier::User(1000),
perm: Acl::READ | Acl::WRITE,
},
AclEntry {
who: AclQualifier::UserObj,
perm: Acl::READ | Acl::WRITE | Acl::EXEC,
},
AclEntry {
who: AclQualifier::Mask,
perm: Acl::READ | Acl::WRITE | Acl::EXEC,
},
AclEntry {
who: AclQualifier::GroupObj,
perm: Acl::READ | Acl::EXEC,
},
])
.expect("valid ACL")
}
#[test]
fn an_acl_encodes_to_the_exact_ext4_byte_form() {
let expected: Vec<u8> = vec![
0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x07, 0x00, 0x02, 0x00, 0x06, 0x00, 0xe8, 0x03, 0x00, 0x00, 0x04, 0x00, 0x05, 0x00, 0x10, 0x00, 0x07, 0x00, 0x20, 0x00, 0x04, 0x00, ];
assert_eq!(encode_acl(&sample_acl()), expected);
}
#[test]
fn an_acl_round_trips_through_the_stored_form() {
let acl = sample_acl();
assert_eq!(decode_acl(&encode_acl(&acl)).unwrap(), acl);
}
#[test]
fn the_stored_form_rejects_a_bad_version_and_truncation() {
assert!(matches!(
decode_acl(&[0x02, 0, 0, 0]),
Err(AclError::Malformed { .. })
));
assert!(matches!(
decode_acl(&[0x01]),
Err(AclError::Malformed { .. })
));
}
#[test]
fn the_stored_form_and_the_boundary_form_do_not_cross_silently() {
let acl = sample_acl();
assert!(matches!(
decode_acl(&acl.encode()),
Err(AclError::Malformed { .. })
));
assert!(matches!(
Acl::decode(&encode_acl(&acl)),
Err(AclError::Malformed { .. })
));
}
fn attrs() -> Vec<Xattr> {
vec![
Xattr {
name: b"security.capability".to_vec(),
value: vec![0x01, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00],
},
Xattr {
name: b"user.comment".to_vec(),
value: b"hello".to_vec(),
},
]
}
#[test]
fn name_index_split_and_join_round_trip() {
for name in [
&b"security.capability"[..],
b"user.comment",
b"system.posix_acl_access",
b"system.posix_acl_default",
b"trusted.overlay.opaque",
b"btrfs.something", ] {
let (index, stored) = split_name(name);
assert_eq!(
join_name(index, stored),
name,
"{name:?} did not round-trip"
);
}
assert_eq!(split_name(b"security.capability").0, 6);
assert_eq!(split_name(b"system.posix_acl_access"), (2, &b""[..]));
assert_eq!(split_name(b"nope").0, 0);
}
#[test]
fn inline_round_trips() {
let region_len = 96; let region = encode_inline(&attrs(), region_len).expect("fits inline");
assert_eq!(region.len(), region_len);
assert_eq!(get_u32(®ion, 0), XATTR_MAGIC);
let back = parse_inline(®ion).unwrap();
assert_eq!(back.len(), 2);
for a in attrs() {
assert!(back.contains(&a), "missing {a:?}");
}
}
#[test]
fn inline_returns_none_when_it_does_not_fit() {
let big = vec![Xattr {
name: b"user.big".to_vec(),
value: vec![0x55; 200],
}];
assert!(encode_inline(&big, 96).is_none());
assert_eq!(encode_inline(&[], 96), Some(vec![0u8; 96]));
}
#[test]
fn an_empty_value_records_offset_zero() {
let attrs = vec![Xattr {
name: b"user.empty".to_vec(),
value: Vec::new(),
}];
let block = encode_block(&attrs, 4096);
assert_eq!(
get_u16(&block, BLOCK_HEADER_LEN + 2),
0,
"block: an empty value records offset 0"
);
assert_eq!(parse_block(&block).unwrap(), attrs, "block round-trips");
let region = encode_inline(&attrs, 96).expect("fits inline");
assert_eq!(
get_u16(®ion, IBODY_HEADER_LEN + 2),
0,
"inline: an empty value records offset 0"
);
assert_eq!(parse_inline(®ion).unwrap(), attrs, "inline round-trips");
}
#[test]
fn block_round_trips_with_a_stable_nonzero_hash() {
let block = encode_block(&attrs(), 4096);
assert_eq!(get_u32(&block, 0), XATTR_MAGIC);
assert_eq!(get_u32(&block, 4), 1, "refcount");
assert_eq!(get_u32(&block, 8), 1, "blocks");
let h = get_u32(&block, 12);
assert_ne!(h, 0, "block hash is set");
assert_eq!(get_u32(&encode_block(&attrs(), 4096), 12), h);
let back = parse_block(&block).unwrap();
assert_eq!(back.len(), 2);
for a in attrs() {
assert!(back.contains(&a), "missing {a:?}");
}
}
#[test]
fn empty_value_and_empty_name_hash_to_defined_values() {
assert_eq!(hash_entry(b"", b""), 0);
assert_ne!(hash_entry(b"x", b"a"), hash_entry(b"x", b""));
}
#[test]
fn an_entry_hash_is_the_one_mke2fs_and_a_kernel_record() {
let pattern: Vec<u8> = (0..3000u32).map(|i| ((i * 131 + 7) % 251) as u8).collect();
let observed: [(&[u8], Vec<u8>, u32); 7] = [
(b"alpha", vec![b'A'; 500], 0x8c20_4766),
(b"beta", (0..512u32).map(|i| i as u8).collect(), 0x0030_9ae1),
(b"d", vec![b'q'; 301], 0x7171_7164),
(b"plain", vec![b'P'; 200], 0x0737_894e),
(b"gam\xe9", vec![b'Z'; 400], 0x0032_0949),
(b"\xff\x80x", vec![b'W'; 300], 0xbb2f_5754),
(b"big", pattern, 0x937c_311d),
];
for (name, value, hash) in observed {
assert_eq!(hash_entry(name, &value), hash, "{name:?}");
}
}
#[test]
fn a_block_hash_folds_its_entries_and_is_zero_beside_a_zero() {
assert_eq!(block_hash(&[0x937c_311d]), 0x937c_311d);
assert_eq!(
block_hash(&[1, 2]),
0x0001_0002,
"the first rotates past the second"
);
assert_eq!(block_hash(&[1, 0, 2]), 0);
assert_eq!(block_hash(&[]), 0);
}
#[test]
fn the_split_places_first_fit_in_canonical_order() {
let attrs = vec![
Xattr {
name: b"user.big".to_vec(),
value: vec![0x55; 200],
},
Xattr {
name: b"user.tiny".to_vec(),
value: vec![0x66; 4],
},
];
let (inline, spilled) = split_for_storage(&attrs, 96);
assert_eq!(inline.len(), 1);
assert_eq!(inline[0].name, b"user.tiny");
assert_eq!(spilled.len(), 1);
assert_eq!(spilled[0].name, b"user.big");
let (inline, spilled) = split_for_storage(&[], 96);
assert!(inline.is_empty() && spilled.is_empty());
}
#[test]
fn the_split_capacity_counts_the_magic_and_the_terminator() {
let attr = |len| {
vec![Xattr {
name: b"user.x".to_vec(),
value: vec![0x77; len],
}]
};
let exact = split_for_storage(&attr(68), 96);
assert!(exact.1.is_empty(), "an exact fill stays inline");
assert!(encode_inline(&exact.0, 96).is_some());
let over = split_for_storage(&attr(69), 96);
assert!(over.0.is_empty(), "one value byte more spills");
assert_eq!(over.1.len(), 1);
}
#[test]
fn parse_ignores_a_region_without_magic() {
assert!(parse_inline(&[0u8; 96]).unwrap().is_empty());
assert!(parse_block(&[0u8; 4096]).unwrap().is_empty());
}
#[test]
fn an_external_value_inode_entry_is_where_its_value_is_kept_not_garbage() {
let mut block = vec![0u8; 4096];
put_u32(&mut block, 0, XATTR_MAGIC);
let off = BLOCK_HEADER_LEN;
block[off] = 4; block[off + 1] = 1; put_u16(&mut block, off + 2, 0); put_u32(&mut block, off + 4, 42); put_u32(&mut block, off + 8, 1_000_000); block[off + ENTRY_HEADER_LEN..off + ENTRY_HEADER_LEN + 4].copy_from_slice(b"test");
let stored = parse_block_stored(&block).expect("an ea_inode entry does not fail the parse");
assert_eq!(stored.len(), 1);
assert_eq!(stored[0].name, b"user.test");
assert_eq!(
stored[0].value,
Value::InInode {
inode: 42,
size: 1_000_000
},
"the external value is where it is kept, not inline bytes"
);
}
#[test]
fn a_value_size_that_spans_the_address_space_is_refused() {
let mut block = vec![0u8; 4096];
put_u32(&mut block, 0, XATTR_MAGIC);
let off = BLOCK_HEADER_LEN;
block[off] = 4; block[off + 1] = 1; put_u16(&mut block, off + 2, 64); put_u32(&mut block, off + 4, 0); put_u32(&mut block, off + 8, u32::MAX); block[off + ENTRY_HEADER_LEN..off + ENTRY_HEADER_LEN + 4].copy_from_slice(b"test");
let err = parse_block(&block).expect_err("a value larger than the block is refused");
assert!(
matches!(
err,
ParseError::InvalidField {
structure: "XattrEntry",
field: "e_value_size",
..
}
),
"{err:?}"
);
}
#[test]
fn the_values_one_region_yields_cannot_outweigh_the_region() {
let mut block = vec![0u8; 4096];
put_u32(&mut block, 0, XATTR_MAGIC);
let mut off = BLOCK_HEADER_LEN;
for _ in 0..8 {
block[off] = 0; block[off + 1] = 1; put_u16(&mut block, off + 2, 0); put_u32(&mut block, off + 4, 0); put_u32(&mut block, off + 8, 4096); off += ENTRY_HEADER_LEN;
}
let err = parse_block(&block).expect_err("the sum outgrows the region");
assert!(
matches!(
err,
ParseError::InvalidField {
structure: "XattrEntry",
field: "e_value_size",
..
}
),
"{err:?}"
);
}
#[test]
fn empty_stored_name_attributes_round_trip() {
let attrs = vec![
Xattr {
name: b"system.posix_acl_access".to_vec(),
value: vec![0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x07, 0x00],
},
Xattr {
name: b"security.selinux".to_vec(),
value: b"unconfined_u:object_r:etc_t:s0\0".to_vec(),
},
];
let region = encode_inline(&attrs, 96).expect("fits inline");
let back = parse_inline(®ion).unwrap();
assert_eq!(
back.len(),
2,
"the empty-named ACL entry is not the terminator"
);
assert!(back.contains(&attrs[0]));
assert!(back.contains(&attrs[1]));
let block = encode_block(&attrs, 4096);
let back = parse_block(&block).unwrap();
assert_eq!(back.len(), 2);
assert!(back.contains(&attrs[0]));
}
}