fxfs/object_store/
extent.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::errors::FxfsError;
6use crate::lsm_tree::types::{OrdLowerBound, OrdUpperBound};
7use crate::serialized_types::serialized_key::{KeyDeserializer, KeySerializer, SerializeKey};
8use crate::serialized_types::varint::Buffer;
9use anyhow::Context as _;
10use fprint::TypeFingerprint;
11use serde::{Deserialize, Serialize};
12use std::cmp::{max, min};
13use std::hash::Hash;
14use std::ops::Range;
15use storage_units::BlockSize;
16
17/// Minimum block size supported by Fxfs.
18/// Extents must be aligned to block size and must be a multiple of this.
19pub const MIN_BLOCK_SIZE: BlockSize = BlockSize::SIZE_512B;
20
21/// We use serde's try_from attribute here to allow deserialization to fail if
22/// an unaligned extent is encountered.
23#[derive(Serialize, Deserialize)]
24#[serde(transparent)]
25struct SerdeExtent(Range<u64>);
26
27impl TryFrom<SerdeExtent> for Extent {
28    type Error = &'static str;
29
30    fn try_from(val: SerdeExtent) -> Result<Self, Self::Error> {
31        if !MIN_BLOCK_SIZE.is_aligned(&val.0) {
32            return Err("Extent bounds must be aligned to MIN_BLOCK_SIZE");
33        }
34        Ok(Extent(val.0))
35    }
36}
37
38/// Extent represents a physical or logical range of bytes, aligned to a 512-byte boundary.
39#[derive(Clone, Debug, Eq, Hash, PartialEq, Serialize, Deserialize, TypeFingerprint)]
40#[serde(try_from = "SerdeExtent")]
41#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
42pub struct Extent(pub Range<u64>);
43
44impl Extent {
45    /// Returns the range of bytes common between this extent and |other|.
46    pub fn overlap(&self, other: &Extent) -> Option<Range<u64>> {
47        if self.end <= other.start || self.start >= other.end {
48            None
49        } else {
50            Some(max(self.start, other.start)..min(self.end, other.end))
51        }
52    }
53
54    /// Returns the search key for this extent; that is, a key which is <= this key under
55    /// OrdUpperBound.
56    /// This would be used when searching for an extent with |find| (when we want to find any
57    /// overlapping extent, which could include extents that start earlier).
58    /// For example, if the tree has extents 50..150 and 150..200 and we wish to read 100..200,
59    /// we'd search for 100..101 which would set the iterator to 50..150.
60    pub fn search_key(&self) -> Self {
61        assert_ne!(self.start, self.end);
62        Extent::search_key_from_offset(self.start)
63    }
64
65    /// Similar to previous, but from an offset.  Returns a search key that will find the first
66    /// extent that touches offset..
67    pub fn search_key_from_offset(offset: u64) -> Self {
68        Self(offset..offset + MIN_BLOCK_SIZE)
69    }
70
71    /// Returns the merge key for this extent; that is, a key which is <= this extent and any other
72    /// possibly overlapping or touching extent, under OrdUpperBound. This is used to set the hint
73    /// for |merge_into|.
74    ///
75    /// For example, if the tree has extents 0..50, 50..150 and 150..200 and we wish to insert
76    /// 100..150, we'd use a merge hint of 100..100 which would set the iterator to 50..150
77    /// (the first element >= 100..100 under OrdUpperBound).
78    pub fn key_for_merge_into(&self) -> Self {
79        Self(self.start..self.start)
80    }
81
82    /// Returns an iterator over the Extent partitions which overlap this key (see `FuzzyHash`).
83    pub fn fuzzy_hash_partition(&self) -> ExtentPartitionIterator {
84        ExtentPartitionIterator {
85            range: EXTENT_HASH_BUCKET_SIZE.align_down(self.start)
86                ..EXTENT_HASH_BUCKET_SIZE.align_up(self.end).unwrap_or(u64::MAX),
87        }
88    }
89
90    pub fn overlaps(&self, other: &Extent) -> bool {
91        self.start < other.end && self.end > other.start
92    }
93
94    pub fn is_search_key(&self) -> bool {
95        self.0.end == self.0.start + MIN_BLOCK_SIZE
96    }
97}
98
99impl SerializeKey for Extent {
100    type Output<'a, B: Buffer + 'a> = KeySerializer<'a, B>;
101
102    #[inline]
103    fn serialize_key_to<'a, B: Buffer>(
104        &self,
105        mut serializer: KeySerializer<'a, B>,
106    ) -> Self::Output<'a, B> {
107        assert!(
108            MIN_BLOCK_SIZE.is_aligned(&self.0),
109            "Extent bounds must be aligned to MIN_BLOCK_SIZE"
110        );
111        assert!(self.0.start <= self.0.end, "Extent length cannot be negative");
112        serializer.write_u64(self.0.end / MIN_BLOCK_SIZE);
113        serializer.write_u64((self.0.end - self.0.start) / MIN_BLOCK_SIZE);
114        serializer
115    }
116
117    #[inline]
118    fn deserialize_key_from(deserializer: &mut KeyDeserializer<'_>) -> Result<Self, anyhow::Error> {
119        let end = deserializer
120            .read_u64()?
121            .checked_mul(MIN_BLOCK_SIZE.get())
122            .ok_or(FxfsError::Inconsistent)
123            .context("Overflow")?;
124        let len_raw = deserializer.read_u64()?;
125        if len_raw == 0 {
126            return Err(FxfsError::Inconsistent).context("Zero-length extent");
127        }
128        let len = len_raw
129            .checked_mul(MIN_BLOCK_SIZE.get())
130            .ok_or(FxfsError::Inconsistent)
131            .context("Overflow")?;
132        let start = end.checked_sub(len).ok_or(FxfsError::Inconsistent).context("Underflow")?;
133        Ok(Self(start..end))
134    }
135}
136
137impl std::ops::Deref for Extent {
138    type Target = Range<u64>;
139    fn deref(&self) -> &Self::Target {
140        &self.0
141    }
142}
143
144impl std::ops::DerefMut for Extent {
145    fn deref_mut(&mut self) -> &mut Self::Target {
146        &mut self.0
147    }
148}
149
150impl From<Range<u64>> for Extent {
151    fn from(range: Range<u64>) -> Self {
152        Self(range)
153    }
154}
155
156impl From<Extent> for Range<u64> {
157    fn from(key: Extent) -> Self {
158        key.0
159    }
160}
161
162impl<T: storage_units::BlockSizeSpec> storage_units::IsAligned<T> for &Extent {
163    #[inline(always)]
164    fn is_aligned(self, block_size: storage_units::GenericBlockSize<T>) -> bool {
165        block_size.is_aligned(&self.0)
166    }
167}
168
169impl<T: storage_units::BlockSizeSpec> storage_units::IsAligned<T> for Extent {
170    #[inline(always)]
171    fn is_aligned(self, block_size: storage_units::GenericBlockSize<T>) -> bool {
172        block_size.is_aligned(&self.0)
173    }
174}
175
176const EXTENT_HASH_BUCKET_SIZE: BlockSize = BlockSize::SIZE_1MIB;
177
178pub struct ExtentPartitionIterator {
179    range: Range<u64>,
180}
181
182impl Iterator for ExtentPartitionIterator {
183    type Item = Range<u64>;
184
185    fn next(&mut self) -> Option<Self::Item> {
186        if self.range.start >= self.range.end {
187            None
188        } else {
189            let start = self.range.start;
190            self.range.start = start.saturating_add(EXTENT_HASH_BUCKET_SIZE.get());
191            let end = std::cmp::min(self.range.start, self.range.end);
192            Some(start..end)
193        }
194    }
195
196    fn size_hint(&self) -> (usize, Option<usize>) {
197        let len = if self.range.start >= self.range.end {
198            0
199        } else {
200            let diff = self.range.end - self.range.start;
201            let count = EXTENT_HASH_BUCKET_SIZE.align_up_to_blocks(diff);
202            usize::try_from(count).unwrap_or(usize::MAX)
203        };
204        (len, Some(len))
205    }
206}
207
208impl ExactSizeIterator for ExtentPartitionIterator {}
209
210// OrdUpperBound compares the end of the extent first, breaking ties by comparing the start
211// descending (i.e. shorter extents sort first). This matches the serialized (end, len) layout
212// and allows search routines to find overlapping extents using search_key().
213impl OrdUpperBound for Extent {
214    fn cmp_upper_bound(&self, other: &Extent) -> std::cmp::Ordering {
215        // The comparison uses the end of the range so that we can more easily do queries. Ties
216        // are broken by comparing the range start descending to match (end, len) layout.
217        // This prepares for key serialization where extents are encoded as (end, len) (enabling
218        // cheap varint length encoding) so byte-wise serialized comparisons match cmp_upper_bound.
219        //
220        // Well-formed layer files never contain overlapping extents, so ties on `end` never
221        // occur within a single layer, ensuring existing layer ordering is unaffected.
222        self.end.cmp(&other.end).then(other.start.cmp(&self.start))
223    }
224}
225
226impl OrdLowerBound for Extent {
227    // Orders by the start of the range rather than the end. This is used exclusively by the
228    // merger min-heap to stream keys out in left-to-right (lower-bound) order.
229    fn cmp_lower_bound(&self, other: &Extent) -> std::cmp::Ordering {
230        self.start.cmp(&other.start)
231    }
232}
233
234impl Ord for Extent {
235    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
236        // We expect cmp_upper_bound and cmp_lower_bound to be used mostly, but ObjectKey needs an
237        // Ord method in order to compare other enum variants, and Transaction requires an ObjectKey
238        // to implement Ord.
239        self.start.cmp(&other.start).then(self.end.cmp(&other.end))
240    }
241}
242
243impl PartialOrd for Extent {
244    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
245        Some(self.cmp(other))
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::{EXTENT_HASH_BUCKET_SIZE, Extent, MIN_BLOCK_SIZE};
252    use crate::lsm_tree::types::{OrdLowerBound, OrdUpperBound};
253    use crate::serialized_types::serialized_key::{KeyDeserializer, SerializeKey};
254    use std::cmp::Ordering;
255
256    #[test]
257    fn test_extent_key_serialization() {
258        let key = Extent(512..2048);
259        let mut buf = Vec::new();
260
261        // Serialize
262        {
263            let ser =
264                crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, Some(0));
265            key.serialize_key_to(ser).finalize();
266        }
267
268        let (mut deser, length) = KeyDeserializer::new(&buf, Some(0)).unwrap();
269        assert_eq!(length, buf.len());
270        let decoded_key = Extent::deserialize_key_from(&mut deser).unwrap();
271
272        assert_eq!(key, decoded_key);
273
274        // Verify bytes:
275        // end = 2048 / 512 = 4.
276        // len = 1536 / 512 = 3.
277        // Delta encoding applies to first field (end = 4). Base is 0. 4 - 0 = 4.
278        // Second field is len = 3. Base is None (taken). So writes 3.
279        // Buffer should be [2, 4, 3] with 1-byte varint length prefix (len = 2 bytes).
280        assert_eq!(buf, vec![2, 4, 3]);
281    }
282
283    #[test]
284    fn test_extent_key_deserialization_overflow() {
285        let mut buf = Vec::new();
286        {
287            let mut ser =
288                crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
289            ser.write_u64(u64::MAX);
290            ser.write_u64(u64::MAX);
291            ser.finalize();
292        }
293        let (mut deser, length) = KeyDeserializer::new(&buf, None).unwrap();
294        assert_eq!(length, buf.len());
295        let result = Extent::deserialize_key_from(&mut deser);
296        assert!(result.is_err());
297        assert_eq!(result.unwrap_err().to_string(), "Overflow");
298    }
299
300    #[test]
301    fn test_extent_key_deserialization_underflow() {
302        let mut buf = Vec::new();
303        {
304            let mut ser =
305                crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
306            ser.write_u64(1); // end = 512
307            ser.write_u64(2); // len = 1024 (len > end)
308            ser.finalize();
309        }
310        let (mut deser, length) = KeyDeserializer::new(&buf, None).unwrap();
311        assert_eq!(length, buf.len());
312        let result = Extent::deserialize_key_from(&mut deser);
313        assert!(result.is_err());
314        assert_eq!(result.unwrap_err().to_string(), "Underflow");
315    }
316
317    #[test]
318    #[should_panic(expected = "Extent bounds must be aligned to MIN_BLOCK_SIZE")]
319    fn test_extent_key_serialization_unaligned_end_panics() {
320        let key = Extent(1024..2049);
321        let mut buf = Vec::new();
322        let ser = crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
323        key.serialize_key_to(ser);
324    }
325
326    #[test]
327    #[should_panic(expected = "Extent bounds must be aligned to MIN_BLOCK_SIZE")]
328    fn test_extent_key_serialization_unaligned_start_panics() {
329        let key = Extent(1025..2048);
330        let mut buf = Vec::new();
331        let ser = crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
332        key.serialize_key_to(ser);
333    }
334
335    #[test]
336    fn test_extent_cmp() {
337        let extent = Extent(100..150);
338        assert_eq!(extent.cmp_upper_bound(&Extent(0..100)), Ordering::Greater);
339        assert_eq!(extent.cmp_upper_bound(&Extent(0..110)), Ordering::Greater);
340        assert_eq!(extent.cmp_upper_bound(&Extent(0..150)), Ordering::Less);
341        assert_eq!(extent.cmp_upper_bound(&Extent(99..150)), Ordering::Less);
342        assert_eq!(extent.cmp_upper_bound(&Extent(100..150)), Ordering::Equal);
343        assert_eq!(extent.cmp_upper_bound(&Extent(0..151)), Ordering::Less);
344        assert_eq!(extent.cmp_upper_bound(&Extent(100..151)), Ordering::Less);
345        assert_eq!(extent.cmp_upper_bound(&Extent(150..1000)), Ordering::Less);
346        assert_eq!(extent.cmp_upper_bound(&Extent(101..150)), Ordering::Greater);
347    }
348
349    #[test]
350    fn test_extent_cmp_lower_bound() {
351        let extent = Extent(100..150);
352        assert_eq!(extent.cmp_lower_bound(&Extent(0..100)), Ordering::Greater);
353        assert_eq!(extent.cmp_lower_bound(&Extent(0..110)), Ordering::Greater);
354        assert_eq!(extent.cmp_lower_bound(&Extent(0..150)), Ordering::Greater);
355        assert_eq!(extent.cmp_lower_bound(&Extent(0..1000)), Ordering::Greater);
356        assert_eq!(extent.cmp_lower_bound(&Extent(99..1000)), Ordering::Greater);
357        assert_eq!(extent.cmp_lower_bound(&Extent(100..150)), Ordering::Equal);
358        // cmp_lower_bound does not check the upper bound of the range
359        assert_eq!(extent.cmp_lower_bound(&Extent(100..1000)), Ordering::Equal);
360        assert_eq!(extent.cmp_lower_bound(&Extent(101..102)), Ordering::Less);
361    }
362
363    #[test]
364    fn test_extent_search_and_insertion_key() {
365        let extent = Extent(MIN_BLOCK_SIZE.get()..3 * MIN_BLOCK_SIZE);
366        assert!(!extent.is_search_key());
367        assert_eq!(extent.search_key(), Extent(MIN_BLOCK_SIZE.get()..2 * MIN_BLOCK_SIZE));
368        assert!(extent.search_key().is_search_key());
369        assert_eq!(extent.cmp_lower_bound(&extent.search_key()), Ordering::Equal);
370        assert_eq!(extent.cmp_upper_bound(&extent.search_key()), Ordering::Greater);
371        assert_eq!(extent.key_for_merge_into(), Extent(MIN_BLOCK_SIZE.get()..MIN_BLOCK_SIZE.get()));
372        assert_eq!(extent.cmp_lower_bound(&extent.key_for_merge_into()), Ordering::Equal);
373        assert_eq!(extent.cmp_upper_bound(&extent.key_for_merge_into()), Ordering::Greater);
374
375        // A search key must always be <= the key it came from under OrdUpperBound.
376        let extent = Extent(MIN_BLOCK_SIZE.get()..2 * MIN_BLOCK_SIZE);
377        assert!(extent.is_search_key());
378        assert_eq!(extent.search_key(), Extent(MIN_BLOCK_SIZE.get()..2 * MIN_BLOCK_SIZE));
379        assert_eq!(extent.cmp_lower_bound(&extent.search_key()), Ordering::Equal);
380        assert_eq!(extent.cmp_upper_bound(&extent.search_key()), Ordering::Equal);
381    }
382
383    #[test]
384    fn test_extent_cmp_same_end_descending_start() {
385        // If ends are identical, a higher start offset (shorter len) sorts BEFORE
386        // a lower start offset (longer len) to match the (end, len) serialization layout.
387        let short_extent = Extent(100 * MIN_BLOCK_SIZE..200 * MIN_BLOCK_SIZE);
388        let long_extent = Extent(50 * MIN_BLOCK_SIZE..200 * MIN_BLOCK_SIZE);
389        assert_eq!(short_extent.cmp_upper_bound(&long_extent), Ordering::Less);
390        assert_eq!(long_extent.cmp_upper_bound(&short_extent), Ordering::Greater);
391    }
392
393    #[test]
394    fn test_extent_serialization_compatibility() {
395        let extent = Extent(50 * 512..200 * 512);
396
397        let mut buf = Vec::new();
398        extent.serialize_key_into(&mut buf);
399
400        let (mut deser, length) = KeyDeserializer::new(&buf, None).unwrap();
401        assert_eq!(length, buf.len());
402        let decoded = Extent::deserialize_key_from(&mut deser).unwrap();
403        assert_eq!(extent, decoded);
404    }
405
406    #[test]
407    fn test_extent_partition_iterator_len() {
408        let mut iter = Extent(0..0).fuzzy_hash_partition();
409        assert_eq!(iter.len(), 0);
410        assert_eq!(iter.size_hint(), (0, Some(0)));
411        assert_eq!(iter.next(), None);
412
413        let mut iter = Extent(0..MIN_BLOCK_SIZE.get()).fuzzy_hash_partition();
414        assert_eq!(iter.len(), 1);
415        assert_eq!(iter.size_hint(), (1, Some(1)));
416        assert_eq!(iter.next(), Some(0..EXTENT_HASH_BUCKET_SIZE.get()));
417        assert_eq!(iter.len(), 0);
418        assert_eq!(iter.size_hint(), (0, Some(0)));
419        assert_eq!(iter.next(), None);
420
421        let mut iter = Extent(0..3 * EXTENT_HASH_BUCKET_SIZE).fuzzy_hash_partition();
422        assert_eq!(iter.len(), 3);
423        assert_eq!(iter.size_hint(), (3, Some(3)));
424        assert!(iter.next().is_some());
425        assert_eq!(iter.len(), 2);
426        assert_eq!(iter.size_hint(), (2, Some(2)));
427        assert!(iter.next().is_some());
428        assert_eq!(iter.len(), 1);
429        assert_eq!(iter.size_hint(), (1, Some(1)));
430        assert!(iter.next().is_some());
431        assert_eq!(iter.len(), 0);
432        assert_eq!(iter.size_hint(), (0, Some(0)));
433        assert_eq!(iter.next(), None);
434    }
435
436    #[test]
437    fn test_extent_key_serialization_zero_length() {
438        let key = Extent(2 * MIN_BLOCK_SIZE..2 * MIN_BLOCK_SIZE);
439        let mut buf = Vec::new();
440        key.serialize_key_into(&mut buf);
441        let (mut deser, length) = KeyDeserializer::new(&buf, None).unwrap();
442        assert_eq!(length, buf.len());
443        let result = Extent::deserialize_key_from(&mut deser);
444        assert!(result.is_err());
445        assert_eq!(result.unwrap_err().to_string(), "Zero-length extent");
446    }
447
448    #[test]
449    #[should_panic(expected = "Extent length cannot be negative")]
450    #[allow(clippy::reversed_empty_ranges)]
451    fn test_extent_key_serialization_inverted_panics() {
452        let key = Extent(2 * MIN_BLOCK_SIZE..MIN_BLOCK_SIZE.get());
453        let mut buf = Vec::new();
454        key.serialize_key_into(&mut buf);
455    }
456
457    #[test]
458    fn test_extent_key_deserialization_zero_length_fails() {
459        let mut buf = Vec::new();
460        {
461            let mut ser =
462                crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
463            ser.write_u64(4); // end = 2048 (4 * 512)
464            ser.write_u64(0); // len = 0
465            ser.finalize();
466        }
467        let (mut deser, length) = KeyDeserializer::new(&buf, None).unwrap();
468        assert_eq!(length, buf.len());
469        let result = Extent::deserialize_key_from(&mut deser);
470        assert!(result.is_err());
471        assert_eq!(result.unwrap_err().to_string(), "Zero-length extent");
472    }
473
474    #[test]
475    fn test_extent_serde_deserialization_unaligned_fails() {
476        use bincode::Options as _;
477        let options = bincode::DefaultOptions::new().allow_trailing_bytes();
478
479        let unaligned_start_bytes = options.serialize(&(1u64..1024u64)).unwrap();
480        assert!(options.deserialize::<Extent>(&unaligned_start_bytes).is_err());
481
482        let unaligned_end_bytes = options.serialize(&(0u64..1000u64)).unwrap();
483        assert!(options.deserialize::<Extent>(&unaligned_end_bytes).is_err());
484
485        let aligned_bytes = options.serialize(&(512u64..1024u64)).unwrap();
486        assert_eq!(options.deserialize::<Extent>(&aligned_bytes).unwrap(), Extent(512..1024));
487    }
488}
fxfs/object_store/extent.rs

fxfs/object_store/
extent.rs
