use super::ReadError;
use super::ondisk::{BlockGroupFlags, Chunk, DiskKey, ItemType, Stripe, objectid};
#[derive(Clone, PartialEq, Eq, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
pub struct MappedChunk {
pub logical: u64,
pub length: u64,
pub flags: BlockGroupFlags,
pub copies: Vec<u64>,
}
impl MappedChunk {
#[must_use]
pub const fn logical_end(&self) -> u64 {
self.logical + self.length
}
}
#[derive(Clone, Default, Debug)]
pub struct ChunkMap {
chunks: Vec<MappedChunk>,
}
impl ChunkMap {
#[must_use]
pub fn new() -> Self {
Self { chunks: Vec::new() }
}
#[must_use]
pub fn chunks(&self) -> &[MappedChunk] {
&self.chunks
}
#[must_use]
pub fn len(&self) -> usize {
self.chunks.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.chunks.is_empty()
}
pub fn insert(
&mut self,
key: &DiskKey,
chunk: &Chunk,
record: &[u8],
devid: u64,
device_bytes: u64,
) -> Result<(), ReadError> {
let mapped = Self::mapped(key, chunk, record, devid, device_bytes)?;
let (logical, length) = (mapped.logical, mapped.length);
let at = self.chunks.partition_point(|c| c.logical < logical);
let overlaps_before = at
.checked_sub(1)
.is_some_and(|prev| self.chunks[prev].logical_end() > logical);
let overlaps_after = self
.chunks
.get(at)
.is_some_and(|next| next.logical < logical + length);
if overlaps_before || overlaps_after {
return Err(ReadError::ChunkOverlap { logical });
}
self.chunks.insert(at, mapped);
Ok(())
}
pub(super) fn mapped(
key: &DiskKey,
chunk: &Chunk,
record: &[u8],
devid: u64,
device_bytes: u64,
) -> Result<MappedChunk, ReadError> {
if key.kind != ItemType::CHUNK_ITEM || key.objectid != objectid::FIRST_CHUNK_TREE {
return Err(ReadError::BadChunk {
logical: key.offset,
fault: "a chunk item is keyed by the first-chunk-tree objectid and the chunk type",
});
}
let logical = key.offset;
if chunk.length == 0 {
return Err(ReadError::BadChunk {
logical,
fault: "a chunk covers no logical space",
});
}
if logical.checked_add(chunk.length).is_none() {
return Err(ReadError::BadChunk {
logical,
fault: "a chunk's logical run leaves the address space",
});
}
if chunk.num_stripes == 0 {
return Err(ReadError::BadChunk {
logical,
fault: "a chunk records no copy of itself",
});
}
if !chunk.ty.is_mirrored() {
return Err(ReadError::UnsupportedProfile {
logical,
flags: chunk.ty.bits(),
});
}
let mut copies = Vec::new();
for index in 0..chunk.num_stripes {
let Stripe {
devid: stripe_dev,
offset,
..
} = chunk.stripe_at(record, index)?;
if stripe_dev != devid {
continue;
}
match offset.checked_add(chunk.length) {
Some(end) if end <= device_bytes => copies.push(offset),
_ => {
return Err(ReadError::BadChunk {
logical,
fault: "a copy of a chunk is placed past the end of the device",
});
}
}
}
if copies.is_empty() {
return Err(ReadError::BadChunk {
logical,
fault: "no copy of a chunk is on the device this image holds",
});
}
Ok(MappedChunk {
logical,
length: chunk.length,
flags: chunk.ty,
copies,
})
}
pub fn from_bootstrap(array: &[u8], devid: u64, device_bytes: u64) -> Result<Self, ReadError> {
let mut map = Self::new();
let mut at = 0usize;
while at < array.len() {
let rest = &array[at..];
if rest.len() < DiskKey::SIZE {
return Err(ReadError::BadBootstrap {
at,
fault: "a key runs past the end of the bootstrap array",
});
}
let key = DiskKey::read_from(rest)?;
let head = &rest[DiskKey::SIZE..];
if head.len() < Chunk::SIZE {
return Err(ReadError::BadBootstrap {
at,
fault: "a chunk runs past the end of the bootstrap array",
});
}
let chunk = Chunk::read_from(head)?;
let encoded = chunk.encoded_len();
if head.len() < encoded {
return Err(ReadError::BadBootstrap {
at,
fault: "a chunk's stripes run past the end of the bootstrap array",
});
}
map.insert(&key, &chunk, &head[..encoded], devid, device_bytes)?;
at += DiskKey::SIZE + encoded;
}
if map.is_empty() {
return Err(ReadError::BadBootstrap {
at: 0,
fault: "the bootstrap array carries no chunk, so no address can be translated",
});
}
Ok(map)
}
#[must_use]
pub fn chunk_at(&self, logical: u64) -> Option<&MappedChunk> {
let at = self.chunks.partition_point(|c| c.logical <= logical);
let candidate = self.chunks.get(at.checked_sub(1)?)?;
(logical < candidate.logical_end()).then_some(candidate)
}
pub fn translate(&self, logical: u64, len: u64) -> Result<u64, ReadError> {
Ok(self.copies_of(logical, len)?[0])
}
pub(crate) fn copies_of(&self, logical: u64, len: u64) -> Result<Vec<u64>, ReadError> {
let chunk = self
.chunk_at(logical)
.ok_or(ReadError::UnmappedLogical { logical, len })?;
let within = logical - chunk.logical;
match within.checked_add(len) {
Some(end) if end <= chunk.length => {}
_ => return Err(ReadError::UnmappedLogical { logical, len }),
}
Ok(chunk.copies.iter().map(|©| copy + within).collect())
}
}
#[cfg(test)]
mod tests {
use super::*;
const DEVID: u64 = 1;
const DEVICE_BYTES: u64 = 1 << 30;
fn record(length: u64, flags: BlockGroupFlags, at: &[(u64, u64)]) -> (Chunk, Vec<u8>) {
let chunk = Chunk {
length,
owner: objectid::EXTENT_TREE,
stripe_len: 64 << 10,
ty: flags,
io_align: 64 << 10,
io_width: 64 << 10,
sector_size: 4096,
num_stripes: at.len() as u16,
sub_stripes: 1,
};
let mut buf = vec![0u8; chunk.encoded_len()];
chunk.write_to(&mut buf);
for (index, &(devid, offset)) in at.iter().enumerate() {
Stripe {
devid,
offset,
dev_uuid: [0xec; 16],
}
.write_to(&mut buf[Chunk::SIZE + index * Stripe::SIZE..]);
}
(chunk, buf)
}
fn key_at(logical: u64) -> DiskKey {
DiskKey::new(objectid::FIRST_CHUNK_TREE, ItemType::CHUNK_ITEM, logical)
}
type Entry<'a> = (u64, u64, BlockGroupFlags, &'a [(u64, u64)]);
fn map_with(entries: &[Entry<'_>]) -> ChunkMap {
let mut map = ChunkMap::new();
for &(logical, length, flags, at) in entries {
let (chunk, buf) = record(length, flags, at);
map.insert(&key_at(logical), &chunk, &buf, DEVID, DEVICE_BYTES)
.expect("a well-formed chunk");
}
map
}
#[test]
fn a_logical_address_lands_where_the_chunk_puts_it_and_not_where_it_started() {
let map = map_with(&[(
30_408_704,
53_673_984,
BlockGroupFlags::METADATA | BlockGroupFlags::DUP,
&[(DEVID, 38_797_312), (DEVID, 92_471_296)],
)]);
assert_eq!(
map.translate(30_605_312, 16_384).expect("mapped"),
38_993_920
);
assert_eq!(
map.translate(30_408_704, 16_384).expect("mapped"),
38_797_312
);
let last = 30_408_704 + 53_673_984 - 16_384;
assert_eq!(
map.translate(last, 16_384).expect("mapped"),
38_797_312 + 53_673_984 - 16_384
);
}
#[test]
fn an_address_no_chunk_covers_is_no_address() {
let map = map_with(&[(
1 << 20,
8 << 20,
BlockGroupFlags::SYSTEM | BlockGroupFlags::DUP,
&[(DEVID, 1 << 20)],
)]);
assert!(matches!(
map.translate(0, 4096),
Err(ReadError::UnmappedLogical { .. })
));
assert!(matches!(
map.translate((1 << 20) + (8 << 20), 4096),
Err(ReadError::UnmappedLogical { .. })
));
let gapped = map_with(&[
(0, 1 << 20, BlockGroupFlags::SYSTEM, &[(DEVID, 0)]),
(4 << 20, 1 << 20, BlockGroupFlags::DATA, &[(DEVID, 4 << 20)]),
]);
assert!(matches!(
gapped.translate(2 << 20, 4096),
Err(ReadError::UnmappedLogical { .. })
));
}
#[test]
fn a_run_that_leaves_its_chunk_is_refused_rather_than_translated_from_its_start() {
let map = map_with(&[
(0, 1 << 20, BlockGroupFlags::SYSTEM, &[(DEVID, 8 << 20)]),
(
1 << 20,
1 << 20,
BlockGroupFlags::METADATA,
&[(DEVID, 64 << 20)],
),
]);
assert_eq!(
map.translate((1 << 20) - 4096, 4096).expect("inside"),
(8 << 20) + (1 << 20) - 4096
);
assert!(matches!(
map.translate((1 << 20) - 4096, 8192),
Err(ReadError::UnmappedLogical { .. })
));
assert!(matches!(
map.translate(4096, u64::MAX),
Err(ReadError::UnmappedLogical { .. })
));
}
#[test]
fn two_chunks_claiming_one_address_is_two_answers_and_is_refused() {
let mut map = map_with(&[(0, 8 << 20, BlockGroupFlags::DATA, &[(DEVID, 0)])]);
let (chunk, buf) = record(1 << 20, BlockGroupFlags::DATA, &[(DEVID, 16 << 20)]);
assert!(matches!(
map.insert(&key_at(4 << 20), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::ChunkOverlap { .. })
));
let (chunk, buf) = record(8 << 20, BlockGroupFlags::DATA, &[(DEVID, 16 << 20)]);
assert!(matches!(
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::ChunkOverlap { .. })
));
let (chunk, buf) = record(1 << 20, BlockGroupFlags::DATA, &[(DEVID, 16 << 20)]);
map.insert(&key_at(8 << 20), &chunk, &buf, DEVID, DEVICE_BYTES)
.expect("abutting is not overlapping");
assert_eq!(map.len(), 2);
}
#[test]
fn a_chunk_whose_stripes_are_pieces_rather_than_copies_is_refused_by_name() {
let mut map = ChunkMap::new();
for striped in [
BlockGroupFlags::RAID0,
BlockGroupFlags::RAID10,
BlockGroupFlags::RAID5,
BlockGroupFlags::RAID6,
] {
let (chunk, buf) = record(1 << 20, BlockGroupFlags::DATA | striped, &[(DEVID, 0)]);
assert!(matches!(
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::UnsupportedProfile { .. })
));
}
let (chunk, buf) = record(
1 << 20,
BlockGroupFlags::DATA | BlockGroupFlags::RAID1 | BlockGroupFlags::DUP,
&[(DEVID, 0)],
);
assert!(matches!(
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::UnsupportedProfile { .. })
));
}
#[test]
fn a_copy_placed_past_the_device_is_refused_where_the_chunk_enters_the_map() {
let mut map = ChunkMap::new();
let (chunk, buf) = record(
1 << 20,
BlockGroupFlags::DATA,
&[(DEVID, DEVICE_BYTES - (1 << 20) + 1)],
);
assert!(matches!(
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::BadChunk { .. })
));
let (chunk, buf) = record(1 << 20, BlockGroupFlags::DATA, &[(DEVID, u64::MAX)]);
assert!(matches!(
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::BadChunk { .. })
));
let (chunk, buf) = record(
1 << 20,
BlockGroupFlags::DATA,
&[(DEVID, DEVICE_BYTES - (1 << 20))],
);
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES)
.expect("exactly filling the device");
}
#[test]
fn a_chunk_with_no_copy_on_this_device_is_not_in_the_map() {
let mut map = ChunkMap::new();
let (chunk, buf) = record(1 << 20, BlockGroupFlags::DATA, &[(DEVID + 1, 0)]);
assert!(matches!(
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::BadChunk { .. })
));
let (chunk, buf) = record(
1 << 20,
BlockGroupFlags::METADATA | BlockGroupFlags::RAID1,
&[(DEVID + 1, 0), (DEVID, 4 << 20)],
);
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES)
.expect("one copy is here");
assert_eq!(map.chunks()[0].copies, vec![4 << 20]);
assert_eq!(map.translate(4096, 4096).expect("mapped"), (4 << 20) + 4096);
}
#[test]
fn a_chunk_that_describes_no_run_at_all_is_refused() {
let mut map = ChunkMap::new();
for (length, stripes) in [(0u64, &[(DEVID, 0)][..]), (1 << 20, &[][..])] {
let (chunk, buf) = record(length, BlockGroupFlags::DATA, stripes);
assert!(matches!(
map.insert(&key_at(0), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::BadChunk { .. })
));
}
let (chunk, buf) = record(1 << 20, BlockGroupFlags::DATA, &[(DEVID, 0)]);
assert!(matches!(
map.insert(&key_at(u64::MAX), &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::BadChunk { .. })
));
}
#[test]
fn an_item_keyed_as_something_other_than_a_chunk_does_not_enter_the_map() {
let mut map = ChunkMap::new();
let (chunk, buf) = record(1 << 20, BlockGroupFlags::DATA, &[(DEVID, 0)]);
for key in [
DiskKey::new(objectid::FIRST_CHUNK_TREE, ItemType::DEV_ITEM, 0),
DiskKey::new(objectid::DEV_ITEMS, ItemType::CHUNK_ITEM, 0),
] {
assert!(matches!(
map.insert(&key, &chunk, &buf, DEVID, DEVICE_BYTES),
Err(ReadError::BadChunk { .. })
));
}
}
#[test]
fn the_bootstrap_array_is_read_pair_by_pair_to_the_length_the_superblock_recorded() {
let (_, buf) = record(
8 << 20,
BlockGroupFlags::SYSTEM | BlockGroupFlags::DUP,
&[(DEVID, 22_020_096), (DEVID, 30_408_704)],
);
let mut array = vec![0u8; DiskKey::SIZE];
key_at(22_020_096).write_to(&mut array);
array.extend_from_slice(&buf);
assert_eq!(array.len(), 129);
let map = ChunkMap::from_bootstrap(&array, DEVID, DEVICE_BYTES).expect("one pair");
assert_eq!(map.len(), 1);
assert_eq!(
map.translate(22_036_480, 16_384).expect("the chunk tree"),
22_036_480
);
assert_eq!(map.chunks()[0].copies, vec![22_020_096, 30_408_704]);
}
#[test]
fn a_bootstrap_array_whose_framing_does_not_hold_is_refused_rather_than_guessed_at() {
let (_, buf) = record(8 << 20, BlockGroupFlags::SYSTEM, &[(DEVID, 0)]);
let mut array = vec![0u8; DiskKey::SIZE];
key_at(0).write_to(&mut array);
array.extend_from_slice(&buf);
for cut in [
DiskKey::SIZE - 1,
DiskKey::SIZE + Chunk::SIZE - 1,
array.len() - 1,
] {
assert!(
matches!(
ChunkMap::from_bootstrap(&array[..cut], DEVID, DEVICE_BYTES),
Err(ReadError::BadBootstrap { .. })
),
"a pair cut at {cut} bytes"
);
}
assert!(matches!(
ChunkMap::from_bootstrap(&[], DEVID, DEVICE_BYTES),
Err(ReadError::BadBootstrap { .. })
));
}
}