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

mapping/
extents.rs
