mapping/

extents.rs

// Copyright 2026 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 crate::BLOCK_SIZE;
use anyhow::{Error, anyhow, ensure};
use std::borrow::Borrow;
use std::ops::Range;

const TYPE_MASK: u64 = 0xc0000000_00000000;
const REGULAR: u64 = 0x00000000_00000000;
const INLINE_TAIL: u64 = 0x40000000_00000000;
const SPARSE: u64 = 0x80000000_00000000;

// Regular extents are densely bit-packed into a single 64-bit hardware command (LSB 0):
//   Bits 62-63 (2 most significant bits): Type identifier (`REGULAR`)
//   Bits 32-61 (30 bits): Extent length in `BLOCK_SIZE` units (4096 bytes)
//   Bits 0-31  (32 least significant bits): Target device offset block address (in `BLOCK_SIZE`
//               units), relative to `base_device_offset`
// Therefore, the maximum contiguous chunk that can fit into a single regular command is 30 bits.
const MAX_REGULAR_EXTENT_BLOCKS: u64 = 0x3fff_ffff;

// Inline tail extents pack their relative byte offset (up to 16 TiB, matching REGULAR's 32-bit
// block index * 4096 bytes) into the low 44 bits.
const MAX_INLINE_TAIL_OFFSET: u64 = 0xfff_ffff_ffff;

// Sparse extents pack their length into the remaining 62 bits not occupied by the type header.
const MAX_SPARSE_EXTENT_BLOCKS: u64 = !TYPE_MASK;

/// Physical backing for a logical [`Extent`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DeviceExtent {
    /// Unbacked (sparse) extent that reads as zeros.
    Sparse,
    /// Block-aligned physical extent starting at the given device byte offset.
    Block(u64),
    /// Single-block inline tail extent starting at a sub-block device byte offset.
    InlineTail(u64),
}

impl From<Option<u64>> for DeviceExtent {
    fn from(offset: Option<u64>) -> Self {
        match offset {
            Some(offset) => Self::Block(offset),
            None => Self::Sparse,
        }
    }
}

/// Represents a logical extent and its physical backing (`DeviceExtent`).
/// `logical_range` boundaries must always be a multiple of `BLOCK_SIZE` (4096 bytes).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Extent {
    logical_range: Range<u64>,
    device_extent: DeviceExtent,
}

impl Extent {
    /// Returns the logical range of this extent.
    pub fn logical_range(&self) -> Range<u64> {
        self.logical_range.clone()
    }

    /// Returns the [`DeviceExtent`] backing this logical extent.
    pub fn device_extent(&self) -> DeviceExtent {
        self.device_extent
    }

    /// Returns the optional physical device offset of this extent. If None, this extent is sparse.
    pub fn device_offset(&self) -> Option<u64> {
        match self.device_extent {
            DeviceExtent::Sparse => None,
            DeviceExtent::Block(offset) | DeviceExtent::InlineTail(offset) => Some(offset),
        }
    }

    /// Returns true if this extent is sparse (unbacked by physical storage).
    pub fn is_sparse(&self) -> bool {
        matches!(self.device_extent, DeviceExtent::Sparse)
    }

    /// Returns the logical length of this extent in bytes.
    pub fn len(&self) -> u64 {
        self.logical_range.end - self.logical_range.start
    }

    /// Creates a new `Extent`.
    ///
    /// # Panics
    ///
    /// Panics if `logical_range.start` or `logical_range.end` is not a multiple of
    /// `BLOCK_SIZE` (4096 bytes), if `logical_range.start > logical_range.end`, or if an
    /// `InlineTail` extent is not a single block.
    pub fn new(logical_range: Range<u64>, device_extent: impl Into<DeviceExtent>) -> Self {
        Self::try_new(logical_range, device_extent).unwrap()
    }

    /// Creates a new `Extent`, returning an `Error` if the alignment or length is invalid.
    pub fn try_new(
        logical_range: Range<u64>,
        device_extent: impl Into<DeviceExtent>,
    ) -> Result<Self, Error> {
        let device_extent = device_extent.into();
        ensure!(
            logical_range.start % BLOCK_SIZE == 0 && logical_range.end % BLOCK_SIZE == 0,
            "logical_range boundaries must be a multiple of BLOCK_SIZE (4096 bytes), got {:?}",
            logical_range
        );
        ensure!(
            logical_range.start <= logical_range.end,
            "logical_range.start must be <= logical_range.end, got {:?}",
            logical_range
        );
        let len = logical_range.end - logical_range.start;
        match device_extent {
            DeviceExtent::Sparse => {}
            DeviceExtent::Block(dev_offset) => {
                ensure!(
                    dev_offset.checked_add(len).is_some(),
                    "device_offset + extent length overflows u64"
                );
            }
            DeviceExtent::InlineTail(dev_offset) => {
                ensure!(
                    len == BLOCK_SIZE,
                    "Inline tail extent must be exactly 1 block ({BLOCK_SIZE} bytes), got {len}"
                );
                ensure!(
                    dev_offset.checked_add(BLOCK_SIZE).is_some(),
                    "device_offset + BLOCK_SIZE overflows u64"
                );
            }
        }
        Ok(Self { logical_range, device_extent })
    }
}

/// Compact in-memory representation of a single extent boundary (16 bytes).
/// By storing the ending logical offset (`end_logical_offset`), the start of extent `i`
/// is `0` for `i == 0` or `entries[i - 1].end_logical_offset` for `i > 0`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct ExtentEntry {
    end_logical_offset: u64,
    device_offset: u64, // u64::MAX sentinel indicates a SPARSE (unbacked) extent.
}

impl ExtentEntry {
    const SPARSE_DEVICE_OFFSET: u64 = u64::MAX;

    fn is_sparse(&self) -> bool {
        self.device_offset == Self::SPARSE_DEVICE_OFFSET
    }
}

fn encode_regular(length_blocks: u32, target_block: u32) -> u64 {
    REGULAR | ((length_blocks as u64 & MAX_REGULAR_EXTENT_BLOCKS) << 32) | (target_block as u64)
}

fn encode_inline_tail(relative_offset: u64) -> u64 {
    INLINE_TAIL | (relative_offset & MAX_INLINE_TAIL_OFFSET)
}

fn encode_sparse(length_blocks: u64) -> u64 {
    SPARSE | (length_blocks & !TYPE_MASK)
}

/// An iterator over a subset of `Extent`s in an `Extents` container.
#[derive(Debug, Clone)]
pub struct ExtentsIterator<'a> {
    extents: &'a Extents,
    index: usize,
}

impl<'a> Iterator for ExtentsIterator<'a> {
    type Item = Extent;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.extents.entries.len() {
            let res = self.extents.entry_to_result(self.index);
            self.index += 1;
            Some(res)
        } else {
            None
        }
    }
}

/// Container for active mappings associated with a session.
/// Extents are stored in compact form (`ExtentEntry`, 16 bytes) in a boxed slice
/// sorted by ascending `end_logical_offset` to support clean O(log N) binary search lookups.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct Extents {
    base_device_offset: u64,
    entries: Box<[ExtentEntry]>,
}

impl Extents {
    /// Returns the base device offset of this container.
    pub fn base_device_offset(&self) -> u64 {
        self.base_device_offset
    }

    /// Returns the number of encoded extent entries in this container.
    pub fn len(&self) -> usize {
        self.entries.len()
    }

    /// Returns true if this container has no extent entries.
    pub fn is_empty(&self) -> bool {
        self.entries.is_empty()
    }

    /// Creates an `Extents` container from an iterator of `Extent`s, returning an `Error`
    /// if validation fails.
    pub fn try_new(
        extents: impl IntoIterator<Item = impl Borrow<Extent>>,
        base_device_offset: u64,
    ) -> Result<Self, Error> {
        let iter = extents.into_iter();
        let (lower_bound, _) = iter.size_hint();
        let mut entries = Vec::with_capacity(lower_bound);
        let mut current_logical_offset = 0u64;

        for extent in iter {
            let extent = extent.borrow();
            ensure!(
                extent.logical_range.start == current_logical_offset,
                "Extents must be contiguous and start at 0: expected start \
                 {current_logical_offset}, got {}",
                extent.logical_range.start
            );
            ensure!(
                extent.logical_range.start < extent.logical_range.end,
                "Extent logical range must be non-empty, got {:?}",
                extent.logical_range
            );
            ensure!(
                extent.logical_range.start % BLOCK_SIZE == 0
                    && extent.logical_range.end % BLOCK_SIZE == 0,
                "logical_range boundaries must be a multiple of BLOCK_SIZE ({BLOCK_SIZE} bytes), \
                 got {:?}",
                extent.logical_range
            );
            let length_blocks = extent.len() / BLOCK_SIZE;
            match extent.device_extent {
                DeviceExtent::InlineTail(dev_offset) => {
                    ensure!(
                        dev_offset >= base_device_offset,
                        "device_offset ({dev_offset}) must be >= base_device_offset \
                         ({base_device_offset})"
                    );
                    ensure!(
                        length_blocks == 1,
                        "Inline tail extent must be exactly 1 block ({BLOCK_SIZE} bytes)"
                    );
                    let relative_offset = dev_offset - base_device_offset;
                    ensure!(
                        relative_offset <= MAX_INLINE_TAIL_OFFSET,
                        "Relative device byte offset exceeds 44-bit maximum"
                    );
                    current_logical_offset += BLOCK_SIZE;
                    entries.push(ExtentEntry {
                        end_logical_offset: current_logical_offset,
                        device_offset: dev_offset,
                    });
                }
                DeviceExtent::Block(dev_offset) => {
                    ensure!(
                        dev_offset >= base_device_offset,
                        "device_offset ({dev_offset}) must be >= base_device_offset \
                         ({base_device_offset})"
                    );
                    let relative_offset = dev_offset - base_device_offset;
                    ensure!(
                        relative_offset % BLOCK_SIZE == 0,
                        "Relative device offset ({dev_offset} - {base_device_offset} = \
                         {relative_offset}) must be a multiple of BLOCK_SIZE ({BLOCK_SIZE} bytes)"
                    );
                    let mut remaining_blocks = length_blocks;
                    let mut current_dev_offset = dev_offset;
                    while remaining_blocks > 0 {
                        let entry_blocks =
                            std::cmp::min(remaining_blocks, MAX_REGULAR_EXTENT_BLOCKS);
                        let entry_bytes = entry_blocks * BLOCK_SIZE;
                        let entry_relative_offset = current_dev_offset - base_device_offset;
                        let target_block = entry_relative_offset / BLOCK_SIZE;
                        ensure!(
                            target_block <= u32::MAX as u64,
                            "Relative device offset block index exceeds u32::MAX"
                        );
                        current_logical_offset += entry_bytes;
                        entries.push(ExtentEntry {
                            end_logical_offset: current_logical_offset,
                            device_offset: current_dev_offset,
                        });
                        current_dev_offset =
                            current_dev_offset.checked_add(entry_bytes).ok_or_else(|| {
                                anyhow!("device_offset + extent length overflows u64")
                            })?;
                        remaining_blocks -= entry_blocks;
                    }
                }
                DeviceExtent::Sparse => {
                    ensure!(
                        length_blocks <= MAX_SPARSE_EXTENT_BLOCKS,
                        "Extent length bounds exceed maximum encodeable length"
                    );
                    current_logical_offset = extent.logical_range.end;
                    entries.push(ExtentEntry {
                        end_logical_offset: current_logical_offset,
                        device_offset: ExtentEntry::SPARSE_DEVICE_OFFSET,
                    });
                }
            }
        }

        Ok(Self { base_device_offset, entries: entries.into_boxed_slice() })
    }

    /// Encodes this `Extents` container into 64-bit mapping descriptors relative to its base
    /// device offset.
    pub fn encode(&self) -> impl Iterator<Item = u64> + '_ {
        let mut prev_logical = 0u64;
        self.entries.iter().map(move |entry| {
            let length_blocks = (entry.end_logical_offset - prev_logical) / BLOCK_SIZE;
            prev_logical = entry.end_logical_offset;
            if entry.is_sparse() {
                encode_sparse(length_blocks)
            } else {
                let relative_offset = entry.device_offset - self.base_device_offset;
                if relative_offset % BLOCK_SIZE != 0 {
                    encode_inline_tail(relative_offset)
                } else {
                    let target_block = (relative_offset / BLOCK_SIZE) as u32;
                    encode_regular(length_blocks as u32, target_block)
                }
            }
        })
    }

    /// Encodes an `Extents` container into 64-bit mapping descriptors.
    pub fn encode_extents(extents: &Extents) -> impl Iterator<Item = u64> + '_ {
        extents.encode()
    }

    /// Encodes an `Extents` container into 64-bit mapping descriptors relative to its base
    /// device offset.
    pub fn encode_extents_with_base_offset(extents: &Extents) -> impl Iterator<Item = u64> + '_ {
        extents.encode()
    }

    /// Decodes a sequence of 64-bit mapping descriptors into a compact `Extents` container,
    /// offsetting regular extents by `base_device_offset`.
    /// Returns `None` if an unknown mapping descriptor type is encountered or if an arithmetic
    /// overflow occurs while decoding.
    pub fn from_encoded(
        encoded: impl IntoIterator<Item = u64>,
        base_device_offset: u64,
    ) -> Option<Self> {
        let iter = encoded.into_iter();
        let (lower_bound, _) = iter.size_hint();
        let mut entries = Vec::with_capacity(lower_bound);
        let mut current_logical_offset = 0u64;

        for val in iter {
            let kind = val & TYPE_MASK;
            if kind == REGULAR {
                let length_blocks = ((val & !TYPE_MASK) >> 32) as u64;
                let target_block = (val & 0xffff_ffff) as u64;
                let length_bytes = length_blocks.checked_mul(BLOCK_SIZE)?;
                current_logical_offset = current_logical_offset.checked_add(length_bytes)?;
                let device_offset =
                    base_device_offset.checked_add(target_block.checked_mul(BLOCK_SIZE)?)?;
                entries.push(ExtentEntry {
                    end_logical_offset: current_logical_offset,
                    device_offset,
                });
            } else if kind == INLINE_TAIL {
                let relative_offset = val & !TYPE_MASK;
                if relative_offset % BLOCK_SIZE == 0 || relative_offset > MAX_INLINE_TAIL_OFFSET {
                    return None;
                }
                current_logical_offset = current_logical_offset.checked_add(BLOCK_SIZE)?;
                let device_offset = base_device_offset.checked_add(relative_offset)?;
                entries.push(ExtentEntry {
                    end_logical_offset: current_logical_offset,
                    device_offset,
                });
            } else if kind == SPARSE {
                let length_blocks = (val & !TYPE_MASK) as u64;
                let length_bytes = length_blocks.checked_mul(BLOCK_SIZE)?;
                current_logical_offset = current_logical_offset.checked_add(length_bytes)?;
                entries.push(ExtentEntry {
                    end_logical_offset: current_logical_offset,
                    device_offset: ExtentEntry::SPARSE_DEVICE_OFFSET,
                });
            } else {
                return None;
            }
        }

        Some(Self { base_device_offset, entries: entries.into_boxed_slice() })
    }

    /// Returns an iterator over all extents whose logical range ends after `start_offset`,
    /// jumping directly to the first overlapping extent in O(log N) time via binary search.
    pub fn iter_extents(&self, start_offset: u64) -> ExtentsIterator<'_> {
        let index = self.entries.partition_point(|e| e.end_logical_offset <= start_offset);
        ExtentsIterator { extents: self, index }
    }

    /// Maps a logical byte offset to the corresponding `Extent` in O(log N) time
    /// using binary search, translating logical and physical ranges to start at `offset`.
    ///
    /// # Panics
    ///
    /// Panics if `offset` is not a multiple of `BLOCK_SIZE` (4096 bytes).
    pub fn map(&self, offset: u64) -> Option<Extent> {
        assert!(
            offset % BLOCK_SIZE == 0,
            "offset must be a multiple of BLOCK_SIZE (4096 bytes), got {offset}"
        );
        let idx = self.entries.partition_point(|e| e.end_logical_offset <= offset);
        if idx >= self.entries.len() {
            return None;
        }

        let entry = &self.entries[idx];
        let start_logical = self.entry_start_offset(idx);
        let end_logical = entry.end_logical_offset;

        let offset_within = offset.checked_sub(start_logical)?;
        let device_extent = if entry.is_sparse() {
            DeviceExtent::Sparse
        } else {
            let dev_offset = entry.device_offset.checked_add(offset_within)?;
            if (dev_offset - self.base_device_offset) % BLOCK_SIZE != 0 {
                DeviceExtent::InlineTail(dev_offset)
            } else {
                DeviceExtent::Block(dev_offset)
            }
        };

        Some(Extent { logical_range: offset..end_logical, device_extent })
    }

    /// Returns all mappings as full `Extent` structs.
    pub fn mappings(&self) -> Vec<Extent> {
        (0..self.entries.len()).map(|i| self.entry_to_result(i)).collect()
    }

    fn entry_start_offset(&self, idx: usize) -> u64 {
        if idx == 0 { 0 } else { self.entries[idx - 1].end_logical_offset }
    }

    fn entry_to_result(&self, idx: usize) -> Extent {
        let entry = &self.entries[idx];
        let start_logical = self.entry_start_offset(idx);
        let end_logical = entry.end_logical_offset;
        let device_extent = if entry.is_sparse() {
            DeviceExtent::Sparse
        } else if (entry.device_offset - self.base_device_offset) % BLOCK_SIZE != 0 {
            DeviceExtent::InlineTail(entry.device_offset)
        } else {
            DeviceExtent::Block(entry.device_offset)
        };
        Extent { logical_range: start_logical..end_logical, device_extent }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_encode_decode_regular() {
        let extents = Extents::try_new(
            [
                Extent::new(0..(4 * BLOCK_SIZE), Some(10 * BLOCK_SIZE)),
                Extent::new((4 * BLOCK_SIZE)..(6 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
            ],
            0,
        )
        .unwrap();
        let encoded = Extents::encode_extents(&extents);
        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");

        let decoded = extents_container.mappings();
        assert_eq!(decoded.len(), 2);

        assert_eq!(decoded[0].logical_range, 0..(4 * BLOCK_SIZE));
        assert_eq!(decoded[0].device_offset(), Some(10 * BLOCK_SIZE));

        assert_eq!(decoded[1].logical_range, (4 * BLOCK_SIZE)..(6 * BLOCK_SIZE));
        assert_eq!(decoded[1].device_offset(), Some(100 * BLOCK_SIZE));
    }

    #[test]
    fn test_encode_decode_sparse() {
        let extents = Extents::try_new(
            [
                Extent::new(0..(2 * BLOCK_SIZE), Some(50 * BLOCK_SIZE)),
                Extent::new((2 * BLOCK_SIZE)..(5 * BLOCK_SIZE), None),
                Extent::new((5 * BLOCK_SIZE)..(6 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
            ],
            0,
        )
        .unwrap();
        let encoded = Extents::encode_extents(&extents);
        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");

        let decoded = extents_container.mappings();
        assert_eq!(decoded.len(), 3);

        assert_eq!(decoded[0].logical_range, 0..(2 * BLOCK_SIZE));
        assert_eq!(decoded[0].device_offset(), Some(50 * BLOCK_SIZE));

        assert_eq!(decoded[1].logical_range, (2 * BLOCK_SIZE)..(5 * BLOCK_SIZE));
        assert_eq!(decoded[1].device_offset(), None);

        assert_eq!(decoded[2].logical_range, (5 * BLOCK_SIZE)..(6 * BLOCK_SIZE));
        assert_eq!(decoded[2].device_offset(), Some(200 * BLOCK_SIZE));
    }

    #[test]
    fn test_encode_decode_non_aligned_start() {
        let base_device_offset = 17408u64; // e.g. LBA 34 on 512-byte sector disk
        let extents = Extents::try_new(
            [
                Extent::new(0..(4 * BLOCK_SIZE), Some(base_device_offset)),
                Extent::new(
                    (4 * BLOCK_SIZE)..(6 * BLOCK_SIZE),
                    Some(base_device_offset + 100 * BLOCK_SIZE),
                ),
            ],
            base_device_offset,
        )
        .unwrap();
        let encoded = Extents::encode_extents_with_base_offset(&extents);
        let extents_container =
            Extents::from_encoded(encoded, base_device_offset).expect("from_encoded failed");

        let decoded = extents_container.mappings();
        assert_eq!(decoded.len(), 2);
        assert_eq!(decoded[0].logical_range, 0..(4 * BLOCK_SIZE));
        assert_eq!(decoded[0].device_offset(), Some(base_device_offset));
        assert_eq!(decoded[1].logical_range, (4 * BLOCK_SIZE)..(6 * BLOCK_SIZE));
        assert_eq!(decoded[1].device_offset(), Some(base_device_offset + 100 * BLOCK_SIZE));

        let mapped = extents_container.map(0).expect("should map at 0");
        assert_eq!(mapped.device_offset(), Some(base_device_offset));

        let mapped_next = extents_container.map(4 * BLOCK_SIZE).expect("should map next");
        assert_eq!(mapped_next.device_offset(), Some(base_device_offset + 100 * BLOCK_SIZE));
    }

    #[test]
    fn test_extents_validation_relative_offset_unaligned_fails() {
        let base_device_offset = 17408u64;
        // 17408 + 500 is not aligned to BLOCK_SIZE relative to base_device_offset
        let result = Extents::try_new(
            [Extent::new(0..BLOCK_SIZE, Some(base_device_offset + 500))],
            base_device_offset,
        );
        assert!(result.is_err());
        assert!(
            result.unwrap_err().to_string().contains("Relative device offset"),
            "Error should mention relative device offset"
        );
    }

    #[test]
    fn test_extents_validation_device_offset_smaller_than_base_fails() {
        let base_device_offset = 17408u64;
        let result = Extents::try_new([Extent::new(0..BLOCK_SIZE, Some(0))], base_device_offset);
        assert!(result.is_err());
        assert!(
            result.unwrap_err().to_string().contains("must be >= base_device_offset"),
            "Error should mention dev_offset >= base_device_offset"
        );
    }

    #[test]
    fn test_extents_validation_non_contiguous_logical_fails() {
        let result = Extents::try_new(
            [
                Extent::new(0..BLOCK_SIZE, Some(0)),
                Extent::new((2 * BLOCK_SIZE)..(3 * BLOCK_SIZE), Some(BLOCK_SIZE)),
            ],
            0,
        );
        assert!(result.is_err());
        assert!(
            result.unwrap_err().to_string().contains("must be contiguous and start at 0"),
            "Error should mention non-contiguous start"
        );
    }

    #[test]
    fn test_binary_search_map_logical_offset() {
        let extents = Extents::try_new(
            [
                Extent::new(0..(10 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
                Extent::new((10 * BLOCK_SIZE)..(20 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
                Extent::new((20 * BLOCK_SIZE)..(30 * BLOCK_SIZE), Some(300 * BLOCK_SIZE)),
            ],
            0,
        )
        .unwrap();
        let encoded = Extents::encode_extents(&extents);
        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");

        let mapped = extents_container.map(0).expect("should map at offset 0");
        assert_eq!(mapped.logical_range, 0..(10 * BLOCK_SIZE));
        assert_eq!(mapped.device_offset(), Some(100 * BLOCK_SIZE));

        let mapped_mid = extents_container
            .map(12 * BLOCK_SIZE)
            .expect("should map inside second extent via binary search");
        assert_eq!(mapped_mid.logical_range, (12 * BLOCK_SIZE)..(20 * BLOCK_SIZE));
        assert_eq!(mapped_mid.device_offset(), Some(202 * BLOCK_SIZE));
    }

    #[test]
    fn test_map_out_of_bounds() {
        let extents =
            Extents::try_new([Extent::new(0..(2 * BLOCK_SIZE), Some(10 * BLOCK_SIZE))], 0).unwrap();
        let encoded = Extents::encode_extents(&extents);
        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");

        assert!(extents_container.map(2 * BLOCK_SIZE).is_none());
        assert!(extents_container.map(100 * BLOCK_SIZE).is_none());
    }

    #[test]
    fn test_binary_search_iter_extents() {
        let extents = Extents::try_new(
            [
                Extent::new(0..(2 * BLOCK_SIZE), Some(10 * BLOCK_SIZE)),
                Extent::new((2 * BLOCK_SIZE)..(4 * BLOCK_SIZE), Some(20 * BLOCK_SIZE)),
                Extent::new((4 * BLOCK_SIZE)..(6 * BLOCK_SIZE), Some(30 * BLOCK_SIZE)),
            ],
            0,
        )
        .unwrap();
        let encoded = Extents::encode_extents(&extents);
        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");

        let results: Vec<_> = extents_container.iter_extents(3 * BLOCK_SIZE).collect();
        assert_eq!(results.len(), 2);
        assert_eq!(results[0].logical_range, (2 * BLOCK_SIZE)..(4 * BLOCK_SIZE));
        assert_eq!(results[1].logical_range, (4 * BLOCK_SIZE)..(6 * BLOCK_SIZE));
    }

    #[test]
    fn test_exact_boundary_queries() {
        let extents = Extents::try_new(
            [
                Extent::new(0..(10 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
                Extent::new((10 * BLOCK_SIZE)..(20 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
            ],
            0,
        )
        .unwrap();
        let encoded = Extents::encode_extents(&extents);
        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");

        let mapped = extents_container.map(10 * BLOCK_SIZE).expect("should map at exact boundary");
        assert_eq!(mapped.logical_range, (10 * BLOCK_SIZE)..(20 * BLOCK_SIZE));
        assert_eq!(mapped.device_offset(), Some(200 * BLOCK_SIZE));

        let results: Vec<_> = extents_container.iter_extents(10 * BLOCK_SIZE).collect();
        assert_eq!(results.len(), 1);
        assert_eq!(results[0].logical_range, (10 * BLOCK_SIZE)..(20 * BLOCK_SIZE));
    }

    #[test]
    #[should_panic(expected = "multiple of BLOCK_SIZE")]
    fn test_extent_new_unaligned_logical_start_panics() {
        Extent::new(1..(2 * BLOCK_SIZE), Some(10 * BLOCK_SIZE));
    }

    #[test]
    #[should_panic(expected = "multiple of BLOCK_SIZE")]
    fn test_extent_new_unaligned_logical_end_panics() {
        Extent::new(0..(2 * BLOCK_SIZE + 1), Some(10 * BLOCK_SIZE));
    }

    #[test]
    #[should_panic(expected = "multiple of BLOCK_SIZE")]
    fn test_map_unaligned_offset_panics() {
        Extents::default().map(500);
    }

    #[test]
    fn test_iter_extents_unaligned_start_offset() {
        let extents = Extents::try_new(
            [
                Extent::new(0..(10 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
                Extent::new((10 * BLOCK_SIZE)..(20 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
            ],
            0,
        )
        .unwrap();
        let encoded = Extents::encode_extents(&extents);
        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");
        let results: Vec<_> = extents_container.iter_extents(500).collect();
        assert_eq!(results.len(), 2);
        assert_eq!(results[0].logical_range, 0..(10 * BLOCK_SIZE));
    }

    #[test]
    fn test_encode_decode_large_regular_extent() {
        let entry_bytes = MAX_REGULAR_EXTENT_BLOCKS * BLOCK_SIZE;
        let large_len = 2 * entry_bytes + 5 * BLOCK_SIZE;
        let start_dev = 10 * BLOCK_SIZE;
        let next_len = 3 * BLOCK_SIZE;
        let next_dev = 50 * BLOCK_SIZE;

        let extents = Extents::try_new(
            [
                Extent::new(0..large_len, Some(start_dev)),
                Extent::new(large_len..(large_len + next_len), Some(next_dev)),
            ],
            0,
        )
        .expect("Extents::try_new should split large regular extent");

        let encoded: Vec<u64> = Extents::encode_extents(&extents).collect();
        assert_eq!(encoded.len(), 4);

        let extents_container = Extents::from_encoded(encoded, 0).expect("from_encoded failed");
        assert_eq!(extents_container, extents);

        let decoded = extents_container.mappings();
        assert_eq!(
            decoded,
            vec![
                Extent::new(0..entry_bytes, Some(start_dev)),
                Extent::new(entry_bytes..(2 * entry_bytes), Some(start_dev + entry_bytes)),
                Extent::new((2 * entry_bytes)..large_len, Some(start_dev + 2 * entry_bytes)),
                Extent::new(large_len..(large_len + next_len), Some(next_dev)),
            ]
        );

        let mapped_second_entry =
            extents_container.map(entry_bytes + BLOCK_SIZE).expect("should map in second entry");
        assert_eq!(
            mapped_second_entry.logical_range,
            (entry_bytes + BLOCK_SIZE)..(2 * entry_bytes)
        );
        assert_eq!(mapped_second_entry.device_offset(), Some(start_dev + entry_bytes + BLOCK_SIZE));
    }

    #[test]
    fn test_large_regular_extent_target_block_overflow_errors() {
        let large_len = (MAX_REGULAR_EXTENT_BLOCKS + 1) * BLOCK_SIZE;
        let start_dev = (u32::MAX as u64 - 10) * BLOCK_SIZE;
        let extent = Extent::try_new(0..large_len, Some(start_dev))
            .expect("Extent::try_new should allow large length");
        let result = Extents::try_new([extent], 0);
        assert!(result.is_err());
        assert!(
            result
                .unwrap_err()
                .to_string()
                .contains("Relative device offset block index exceeds u32::MAX"),
            "Second split entry exceeding u32::MAX target_block should fail"
        );
    }

    #[test]
    fn test_from_encoded_unknown_kind_returns_none() {
        let unknown_descriptor = 0x40000000_00000000;
        assert!(Extents::from_encoded([unknown_descriptor], 0).is_none());
        let unknown_descriptor_2 = 0xc0000000_00000000;
        assert!(Extents::from_encoded([unknown_descriptor_2], 0).is_none());
    }

    #[test]
    fn test_encode_decode_inline_tail() {
        let extents = Extents::try_new(
            [
                Extent::new(0..(2 * BLOCK_SIZE), DeviceExtent::Block(10 * BLOCK_SIZE)),
                Extent::new(
                    (2 * BLOCK_SIZE)..(3 * BLOCK_SIZE),
                    DeviceExtent::InlineTail(3 * BLOCK_SIZE + 64),
                ),
            ],
            0,
        )
        .unwrap();
        let encoded: Vec<u64> = Extents::encode_extents(&extents).collect();
        assert_eq!(encoded.len(), 2);
        let decoded = Extents::from_encoded(encoded, 0).expect("from_encoded failed");
        assert_eq!(decoded, extents);
        let mapped = decoded.map(2 * BLOCK_SIZE).expect("should map inline tail");
        assert_eq!(mapped.logical_range, (2 * BLOCK_SIZE)..(3 * BLOCK_SIZE));
        assert_eq!(mapped.device_extent(), DeviceExtent::InlineTail(3 * BLOCK_SIZE + 64));
        assert_eq!(mapped.device_offset(), Some(3 * BLOCK_SIZE + 64));
    }
}