mapping/
extents.rs

1// Copyright 2026 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use crate::BLOCK_SIZE;
6use anyhow::{Error, anyhow};
7use std::ops::Range;
8
9const TYPE_MASK: u64 = 0xc0000000_00000000;
10const REGULAR: u64 = 0x00000000_00000000;
11const SPARSE: u64 = 0x80000000_00000000;
12
13// Regular extents are densely bit-packed into a single 64-bit hardware command (LSB 0):
14//   Bits 62-63 (2 most significant bits): Type identifier (`REGULAR`)
15//   Bits 32-61 (30 bits): Extent length in blocks
16//   Bits 0-31  (32 least significant bits): Target physical device offset block address
17// Therefore, the maximum contiguous chunk that can fit into a single regular command is 30 bits.
18const MAX_REGULAR_EXTENT_BLOCKS: u64 = 0x3fff_ffff;
19
20// Sparse extents pack their length into the remaining 62 bits not occupied by the type header.
21const MAX_SPARSE_EXTENT_BLOCKS: u64 = !TYPE_MASK;
22
23/// Represents a logical extent and its optional physical device starting offset.
24/// Both `logical_range` boundaries and `device_offset` must always be a multiple of
25/// `BLOCK_SIZE` (4096 bytes). The physical device range length is identical to `logical_range`.
26#[derive(Debug, Clone, PartialEq, Eq)]
27pub struct Extent {
28    logical_range: Range<u64>,
29    device_offset: Option<u64>,
30}
31
32impl Extent {
33    /// Returns the logical range of this extent.
34    pub fn logical_range(&self) -> Range<u64> {
35        self.logical_range.clone()
36    }
37
38    /// Returns the optional physical device offset of this extent. If None, this extent is sparse.
39    pub fn device_offset(&self) -> Option<u64> {
40        self.device_offset
41    }
42
43    /// Returns true if this extent is sparse (unbacked by physical storage).
44    pub fn is_sparse(&self) -> bool {
45        self.device_offset.is_none()
46    }
47
48    /// Returns the logical length of this extent in bytes.
49    pub fn len(&self) -> u64 {
50        self.logical_range.end - self.logical_range.start
51    }
52
53    /// Creates a new `Extent`.
54    ///
55    /// # Panics
56    ///
57    /// Panics if `logical_range.start`, `logical_range.end`, or `device_offset`
58    /// (when `Some`) is not a multiple of `BLOCK_SIZE` (4096 bytes), or if
59    /// `logical_range.start > logical_range.end`.
60    pub fn new(logical_range: Range<u64>, device_offset: Option<u64>) -> Self {
61        Self::try_new(logical_range, device_offset).unwrap()
62    }
63
64    /// Creates a new `Extent`, returning an `Error` if the alignment is invalid.
65    pub fn try_new(logical_range: Range<u64>, device_offset: Option<u64>) -> Result<Self, Error> {
66        if logical_range.start % BLOCK_SIZE != 0 || logical_range.end % BLOCK_SIZE != 0 {
67            return Err(anyhow!(
68                "logical_range boundaries must be a multiple of BLOCK_SIZE (4096 bytes), got {:?}",
69                logical_range
70            ));
71        }
72        if logical_range.start > logical_range.end {
73            return Err(anyhow!(
74                "logical_range.start must be <= logical_range.end, got {:?}",
75                logical_range
76            ));
77        }
78
79        let length_blocks = (logical_range.end - logical_range.start) / BLOCK_SIZE;
80        if let Some(dev_offset) = device_offset {
81            if dev_offset % BLOCK_SIZE != 0 {
82                return Err(anyhow!(
83                    "device_offset must be a multiple of BLOCK_SIZE (4096 bytes), got {}",
84                    dev_offset
85                ));
86            }
87
88            if length_blocks > MAX_REGULAR_EXTENT_BLOCKS {
89                // TODO(https://fxbug.dev/535489428): Handle large extents if needed.
90                return Err(anyhow!("Extent length bounds exceed maximum encodeable length"));
91            }
92
93            let target_block = dev_offset / BLOCK_SIZE;
94            if u32::try_from(target_block).is_err() {
95                return Err(anyhow!("Extent device_offset block index exceeds u32::MAX"));
96            }
97        } else {
98            if length_blocks > MAX_SPARSE_EXTENT_BLOCKS {
99                // TODO(https://fxbug.dev/535489428): Handle large extents if needed.
100                return Err(anyhow!("Extent length bounds exceed maximum encodeable length"));
101            }
102        }
103        Ok(Self { logical_range, device_offset })
104    }
105}
106
107/// Compact in-memory representation of a single extent boundary (16 bytes).
108/// By storing the ending logical offset (`end_logical_offset`), the start of extent `i`
109/// is `0` for `i == 0` or `entries[i - 1].end_logical_offset` for `i > 0`.
110#[derive(Debug, Clone, Copy, PartialEq, Eq)]
111struct ExtentEntry {
112    end_logical_offset: u64,
113    device_offset: u64, // u64::MAX sentinel indicates a SPARSE (unbacked) extent.
114}
115
116impl ExtentEntry {
117    const SPARSE_DEVICE_OFFSET: u64 = u64::MAX;
118
119    fn is_sparse(&self) -> bool {
120        self.device_offset == Self::SPARSE_DEVICE_OFFSET
121    }
122}
123
124fn encode_regular(length_blocks: u32, target_block: u32) -> u64 {
125    REGULAR | ((length_blocks as u64 & MAX_REGULAR_EXTENT_BLOCKS) << 32) | (target_block as u64)
126}
127
128fn encode_sparse(length_blocks: u64) -> u64 {
129    SPARSE | (length_blocks & !TYPE_MASK)
130}
131
132/// An iterator over a subset of `Extent`s in an `Extents` container.
133#[derive(Debug, Clone)]
134pub struct ExtentsIterator<'a> {
135    extents: &'a Extents,
136    index: usize,
137}
138
139impl<'a> Iterator for ExtentsIterator<'a> {
140    type Item = Extent;
141
142    fn next(&mut self) -> Option<Self::Item> {
143        if self.index < self.extents.entries.len() {
144            let res = self.extents.entry_to_result(self.index);
145            self.index += 1;
146            Some(res)
147        } else {
148            None
149        }
150    }
151}
152
153/// Container for active mappings associated with a session.
154/// Extents are stored in compact form (`ExtentEntry`, 16 bytes) in a boxed slice
155/// sorted by ascending `end_logical_offset` to support clean O(log N) binary search lookups.
156#[derive(Debug, Clone, PartialEq, Eq, Default)]
157pub struct Extents {
158    entries: Box<[ExtentEntry]>,
159}
160
161impl Extents {
162    /// Encodes a slice of `Extent`s into 64-bit mapping descriptors.
163    pub fn encode_extents(extents: &[Extent]) -> Vec<u64> {
164        Self::encode_extents_iter(extents).collect()
165    }
166
167    /// Returns an iterator of 64-bit mapping descriptors from a slice of `Extent`s.
168    pub fn encode_extents_iter<'a>(extents: &'a [Extent]) -> impl Iterator<Item = u64> + 'a {
169        extents.iter().map(|extent| {
170            let length_blocks = extent.len() / BLOCK_SIZE;
171            match extent.device_offset() {
172                Some(dev_offset) => {
173                    let target_block = dev_offset / BLOCK_SIZE;
174                    encode_regular(length_blocks as u32, target_block as u32)
175                }
176                None => encode_sparse(length_blocks),
177            }
178        })
179    }
180
181    /// Decodes a sequence of 64-bit mapping descriptors into a compact `Extents` container.
182    /// Returns `None` if an unknown mapping descriptor type is encountered.
183    pub fn from_encoded(encoded: &[u64]) -> Option<Self> {
184        let mut entries = Vec::with_capacity(encoded.len());
185        let mut current_logical_offset = 0;
186
187        for &val in encoded {
188            let kind = val & TYPE_MASK;
189            if kind == REGULAR {
190                let length_blocks = ((val & !TYPE_MASK) >> 32) as u64;
191                let target_block = (val & 0xffff_ffff) as u64;
192                let length_bytes = length_blocks * BLOCK_SIZE;
193                current_logical_offset += length_bytes;
194                entries.push(ExtentEntry {
195                    end_logical_offset: current_logical_offset,
196                    device_offset: target_block * BLOCK_SIZE,
197                });
198            } else if kind == SPARSE {
199                let length_blocks = (val & !TYPE_MASK) as u64;
200                let length_bytes = length_blocks * BLOCK_SIZE;
201                current_logical_offset += length_bytes;
202                entries.push(ExtentEntry {
203                    end_logical_offset: current_logical_offset,
204                    device_offset: ExtentEntry::SPARSE_DEVICE_OFFSET,
205                });
206            } else {
207                return None;
208            }
209        }
210
211        Some(Self { entries: entries.into_boxed_slice() })
212    }
213
214    /// Returns an iterator over all extents whose logical range ends after `start_offset`,
215    /// jumping directly to the first overlapping extent in O(log N) time via binary search.
216    pub fn iter_extents(&self, start_offset: u64) -> ExtentsIterator<'_> {
217        let index = self.entries.partition_point(|e| e.end_logical_offset <= start_offset);
218        ExtentsIterator { extents: self, index }
219    }
220
221    /// Maps a logical byte offset to the corresponding `Extent` in O(log N) time
222    /// using binary search, translating logical and physical ranges to start at `offset`.
223    ///
224    /// # Panics
225    ///
226    /// Panics if `offset` is not a multiple of `BLOCK_SIZE` (4096 bytes).
227    pub fn map(&self, offset: u64) -> Option<Extent> {
228        assert!(
229            offset % BLOCK_SIZE == 0,
230            "offset must be a multiple of BLOCK_SIZE (4096 bytes), got {offset}"
231        );
232        let idx = self.entries.partition_point(|e| e.end_logical_offset <= offset);
233        if idx >= self.entries.len() {
234            return None;
235        }
236
237        let entry = &self.entries[idx];
238        let start_logical = self.entry_start_offset(idx);
239        let end_logical = entry.end_logical_offset;
240
241        let offset_within = offset - start_logical;
242        let device_offset =
243            if entry.is_sparse() { None } else { Some(entry.device_offset + offset_within) };
244
245        Some(Extent { logical_range: offset..end_logical, device_offset })
246    }
247
248    /// Returns all mappings as full `Extent` structs.
249    pub fn mappings(&self) -> Vec<Extent> {
250        (0..self.entries.len()).map(|i| self.entry_to_result(i)).collect()
251    }
252
253    fn entry_start_offset(&self, idx: usize) -> u64 {
254        if idx == 0 { 0 } else { self.entries[idx - 1].end_logical_offset }
255    }
256
257    fn entry_to_result(&self, idx: usize) -> Extent {
258        let entry = &self.entries[idx];
259        let start_logical = self.entry_start_offset(idx);
260        let end_logical = entry.end_logical_offset;
261        let device_offset = if entry.is_sparse() { None } else { Some(entry.device_offset) };
262        Extent { logical_range: start_logical..end_logical, device_offset }
263    }
264}
265
266#[cfg(test)]
267mod tests {
268    use super::*;
269
270    #[test]
271    fn test_encode_decode_regular() {
272        let extents = vec![
273            Extent::new(0..(4 * BLOCK_SIZE), Some(10 * BLOCK_SIZE)),
274            Extent::new((4 * BLOCK_SIZE)..(6 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
275        ];
276        let encoded = Extents::encode_extents(&extents);
277        assert_eq!(encoded.len(), 2);
278
279        let extents_container = Extents::from_encoded(&encoded).expect("from_encoded failed");
280
281        let decoded = extents_container.mappings();
282        assert_eq!(decoded.len(), 2);
283
284        assert_eq!(decoded[0].logical_range, 0..(4 * BLOCK_SIZE));
285        assert_eq!(decoded[0].device_offset, Some(10 * BLOCK_SIZE));
286
287        assert_eq!(decoded[1].logical_range, (4 * BLOCK_SIZE)..(6 * BLOCK_SIZE));
288        assert_eq!(decoded[1].device_offset, Some(100 * BLOCK_SIZE));
289    }
290
291    #[test]
292    fn test_encode_decode_sparse() {
293        let extents = vec![
294            Extent::new(0..(2 * BLOCK_SIZE), Some(50 * BLOCK_SIZE)),
295            Extent::new((2 * BLOCK_SIZE)..(5 * BLOCK_SIZE), None),
296            Extent::new((5 * BLOCK_SIZE)..(6 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
297        ];
298        let encoded = Extents::encode_extents(&extents);
299
300        let extents_container = Extents::from_encoded(&encoded).expect("from_encoded failed");
301
302        let decoded = extents_container.mappings();
303        assert_eq!(decoded.len(), 3);
304
305        assert_eq!(decoded[0].logical_range, 0..(2 * BLOCK_SIZE));
306        assert_eq!(decoded[0].device_offset, Some(50 * BLOCK_SIZE));
307
308        assert_eq!(decoded[1].logical_range, (2 * BLOCK_SIZE)..(5 * BLOCK_SIZE));
309        assert_eq!(decoded[1].device_offset, None);
310
311        assert_eq!(decoded[2].logical_range, (5 * BLOCK_SIZE)..(6 * BLOCK_SIZE));
312        assert_eq!(decoded[2].device_offset, Some(200 * BLOCK_SIZE));
313    }
314
315    #[test]
316    fn test_binary_search_map_logical_offset() {
317        let extents = vec![
318            Extent::new(0..(10 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
319            Extent::new((10 * BLOCK_SIZE)..(20 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
320            Extent::new((20 * BLOCK_SIZE)..(30 * BLOCK_SIZE), Some(300 * BLOCK_SIZE)),
321        ];
322        let encoded = Extents::encode_extents(&extents);
323        let extents_container = Extents::from_encoded(&encoded).expect("from_encoded failed");
324
325        let mapped = extents_container.map(0).expect("should map at offset 0");
326        assert_eq!(mapped.logical_range, 0..(10 * BLOCK_SIZE));
327        assert_eq!(mapped.device_offset, Some(100 * BLOCK_SIZE));
328
329        let mapped_mid = extents_container
330            .map(12 * BLOCK_SIZE)
331            .expect("should map inside second extent via binary search");
332        assert_eq!(mapped_mid.logical_range, (12 * BLOCK_SIZE)..(20 * BLOCK_SIZE));
333        assert_eq!(mapped_mid.device_offset, Some(202 * BLOCK_SIZE));
334    }
335
336    #[test]
337    fn test_map_out_of_bounds() {
338        let extents = vec![Extent::new(0..(2 * BLOCK_SIZE), Some(10 * BLOCK_SIZE))];
339        let encoded = Extents::encode_extents(&extents);
340        let extents_container = Extents::from_encoded(&encoded).expect("from_encoded failed");
341
342        assert!(extents_container.map(2 * BLOCK_SIZE).is_none());
343        assert!(extents_container.map(100 * BLOCK_SIZE).is_none());
344    }
345
346    #[test]
347    fn test_binary_search_iter_extents() {
348        let extents = vec![
349            Extent::new(0..(2 * BLOCK_SIZE), Some(10 * BLOCK_SIZE)),
350            Extent::new((2 * BLOCK_SIZE)..(4 * BLOCK_SIZE), Some(20 * BLOCK_SIZE)),
351            Extent::new((4 * BLOCK_SIZE)..(6 * BLOCK_SIZE), Some(30 * BLOCK_SIZE)),
352        ];
353        let encoded = Extents::encode_extents(&extents);
354        let extents_container = Extents::from_encoded(&encoded).expect("from_encoded failed");
355
356        let results: Vec<_> = extents_container.iter_extents(3 * BLOCK_SIZE).collect();
357        assert_eq!(results.len(), 2);
358        assert_eq!(results[0].logical_range, (2 * BLOCK_SIZE)..(4 * BLOCK_SIZE));
359        assert_eq!(results[1].logical_range, (4 * BLOCK_SIZE)..(6 * BLOCK_SIZE));
360    }
361
362    #[test]
363    fn test_exact_boundary_queries() {
364        let extents = vec![
365            Extent::new(0..(10 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
366            Extent::new((10 * BLOCK_SIZE)..(20 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
367        ];
368        let encoded = Extents::encode_extents(&extents);
369        let extents_container = Extents::from_encoded(&encoded).expect("from_encoded failed");
370
371        let mapped = extents_container.map(10 * BLOCK_SIZE).expect("should map at exact boundary");
372        assert_eq!(mapped.logical_range, (10 * BLOCK_SIZE)..(20 * BLOCK_SIZE));
373        assert_eq!(mapped.device_offset, Some(200 * BLOCK_SIZE));
374
375        let results: Vec<_> = extents_container.iter_extents(10 * BLOCK_SIZE).collect();
376        assert_eq!(results.len(), 1);
377        assert_eq!(results[0].logical_range, (10 * BLOCK_SIZE)..(20 * BLOCK_SIZE));
378    }
379
380    #[test]
381    #[should_panic(expected = "multiple of BLOCK_SIZE")]
382    fn test_extent_new_unaligned_logical_start_panics() {
383        Extent::new(1..(2 * BLOCK_SIZE), Some(10 * BLOCK_SIZE));
384    }
385
386    #[test]
387    #[should_panic(expected = "multiple of BLOCK_SIZE")]
388    fn test_extent_new_unaligned_logical_end_panics() {
389        Extent::new(0..(2 * BLOCK_SIZE + 1), Some(10 * BLOCK_SIZE));
390    }
391
392    #[test]
393    #[should_panic(expected = "multiple of BLOCK_SIZE")]
394    fn test_extent_new_unaligned_device_offset_panics() {
395        Extent::new(0..(2 * BLOCK_SIZE), Some(10 * BLOCK_SIZE + 500));
396    }
397
398    #[test]
399    #[should_panic(expected = "multiple of BLOCK_SIZE")]
400    fn test_map_unaligned_offset_panics() {
401        Extents::default().map(500);
402    }
403
404    #[test]
405    fn test_iter_extents_unaligned_start_offset() {
406        let extents = vec![
407            Extent::new(0..(10 * BLOCK_SIZE), Some(100 * BLOCK_SIZE)),
408            Extent::new((10 * BLOCK_SIZE)..(20 * BLOCK_SIZE), Some(200 * BLOCK_SIZE)),
409        ];
410        let encoded = Extents::encode_extents(&extents);
411        let extents_container = Extents::from_encoded(&encoded).expect("from_encoded failed");
412        let results: Vec<_> = extents_container.iter_extents(500).collect();
413        assert_eq!(results.len(), 2);
414        assert_eq!(results[0].logical_range, 0..(10 * BLOCK_SIZE));
415    }
416
417    #[test]
418    fn test_encode_extents_device_offset_overflow_errors() {
419        let result = Extent::try_new(0..BLOCK_SIZE, Some((u32::MAX as u64 + 1) * BLOCK_SIZE));
420        assert!(result.is_err());
421        assert_eq!(
422            result.unwrap_err().to_string(),
423            "Extent device_offset block index exceeds u32::MAX"
424        );
425    }
426
427    #[test]
428    fn test_encode_extents_regular_length_overflow_errors() {
429        let result = Extent::try_new(
430            0..((MAX_REGULAR_EXTENT_BLOCKS + 1) * BLOCK_SIZE),
431            Some(10 * BLOCK_SIZE),
432        );
433        assert!(result.is_err());
434        assert_eq!(
435            result.unwrap_err().to_string(),
436            "Extent length bounds exceed maximum encodeable length"
437        );
438    }
439
440    #[test]
441    fn test_from_encoded_unknown_kind_returns_none() {
442        let unknown_descriptor = 0x40000000_00000000;
443        assert!(Extents::from_encoded(&[unknown_descriptor]).is_none());
444    }
445}
mapping/extents.rs

mapping/
extents.rs
