fxfs/object_store/
extent_record.rs

1// Copyright 2021 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
5// TODO(https://fxbug.dev/42178223): need validation after deserialization.
6
7use crate::checksum::{Checksums, ChecksumsV38};
8use crate::lsm_tree::types::{OrdLowerBound, OrdUpperBound};
9use crate::round::{round_down, round_up};
10use crate::serialized_types::serialized_key::{KeyDeserializer, KeySerializer, SerializeKey};
11use crate::serialized_types::varint::Buffer;
12use bit_vec::BitVec;
13use fprint::TypeFingerprint;
14use serde::{Deserialize, Serialize};
15use std::cmp::{max, min};
16use std::hash::Hash;
17use std::ops::Range;
18
19/// The common case for extents which cover the data payload of some object.
20pub const DEFAULT_DATA_ATTRIBUTE_ID: u64 = 0;
21
22/// Contains a serialized `BlobMetadataUnversioned` struct. This is attribute may still exist on
23/// blobs but should no longer be written. Use `BLOB_METADATA_ATTRIBUTE_ID` instead.
24pub const BLOB_MERKLE_ATTRIBUTE_ID: u64 = 1;
25/// Contains a serialized and versioned `BlobMetadata` struct. Use `BlobMetadata::read_from` and
26/// `BlobMetadata::write_to` to access this attribute.
27pub const BLOB_METADATA_ATTRIBUTE_ID: u64 = 3;
28
29/// For fsverity files in Fxfs, we store the merkle tree of the verified file at a well-known
30/// attribute.
31pub const FSVERITY_MERKLE_ATTRIBUTE_ID: u64 = 2;
32
33/// ExtentKey is a child of ObjectKey for Object attributes that have attached extents
34/// (at time of writing this was only the used for file contents).
35pub type ExtentKey = ExtentKeyV32;
36
37#[derive(Clone, Debug, Eq, Hash, PartialEq, Serialize, Deserialize, TypeFingerprint)]
38#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
39pub struct ExtentKeyV32 {
40    pub range: Range<u64>,
41}
42
43impl SerializeKey for ExtentKeyV32 {
44    fn serialize_key_to<B: Buffer>(&self, serializer: &mut KeySerializer<'_, B>) {
45        assert_eq!(self.range.end % 512, 0, "Extent end must be 512-byte aligned");
46        assert_eq!(self.range.start % 512, 0, "Extent start must be 512-byte aligned");
47        serializer.write_u64(self.range.end / 512);
48        serializer.write_u64(self.range.start / 512);
49    }
50
51    fn deserialize_key_from(deserializer: &mut KeyDeserializer<'_>) -> Result<Self, anyhow::Error> {
52        let end =
53            deserializer.read_u64()?.checked_mul(512).ok_or_else(|| anyhow::anyhow!("Overflow"))?;
54        let start =
55            deserializer.read_u64()?.checked_mul(512).ok_or_else(|| anyhow::anyhow!("Overflow"))?;
56        Ok(Self { range: start..end })
57    }
58}
59
60impl std::ops::Deref for ExtentKey {
61    type Target = Range<u64>;
62    fn deref(&self) -> &Self::Target {
63        &self.range
64    }
65}
66
67impl std::ops::DerefMut for ExtentKey {
68    fn deref_mut(&mut self) -> &mut Self::Target {
69        &mut self.range
70    }
71}
72
73impl From<Range<u64>> for ExtentKey {
74    fn from(range: Range<u64>) -> Self {
75        Self { range }
76    }
77}
78
79impl From<ExtentKey> for Range<u64> {
80    fn from(key: ExtentKey) -> Self {
81        key.range
82    }
83}
84
85const EXTENT_HASH_BUCKET_SIZE: u64 = 1 * 1024 * 1024;
86
87pub struct ExtentKeyPartitionIterator {
88    range: Range<u64>,
89}
90
91impl Iterator for ExtentKeyPartitionIterator {
92    type Item = Range<u64>;
93
94    fn next(&mut self) -> Option<Self::Item> {
95        if self.range.start >= self.range.end {
96            None
97        } else {
98            let start = self.range.start;
99            self.range.start = start.saturating_add(EXTENT_HASH_BUCKET_SIZE);
100            let end = std::cmp::min(self.range.start, self.range.end);
101            Some(start..end)
102        }
103    }
104}
105
106impl ExtentKey {
107    /// Creates an ExtentKey.
108    pub fn new(range: std::ops::Range<u64>) -> Self {
109        Self { range }
110    }
111
112    /// Returns the range of bytes common between this extent and |other|.
113    pub fn overlap(&self, other: &ExtentKey) -> Option<Range<u64>> {
114        if self.range.end <= other.range.start || self.range.start >= other.range.end {
115            None
116        } else {
117            Some(max(self.range.start, other.range.start)..min(self.range.end, other.range.end))
118        }
119    }
120
121    /// Returns the search key for this extent; that is, a key which is <= this key under Ord and
122    /// OrdLowerBound.
123    /// This would be used when searching for an extent with |find| (when we want to find any
124    /// overlapping extent, which could include extents that start earlier).
125    /// For example, if the tree has extents 50..150 and 150..200 and we wish to read 100..200,
126    /// we'd search for 0..101 which would set the iterator to 50..150.
127    pub fn search_key(&self) -> Self {
128        assert_ne!(self.range.start, self.range.end);
129        ExtentKey::search_key_from_offset(self.range.start)
130    }
131
132    /// Similar to previous, but from an offset.  Returns a search key that will find the first
133    /// extent that touches offset..
134    pub fn search_key_from_offset(offset: u64) -> Self {
135        Self { range: 0..offset + 1 }
136    }
137
138    /// Returns the merge key for this extent; that is, a key which is <= this extent and any other
139    /// possibly overlapping extent, under Ord. This would be used to set the hint for |merge_into|.
140    ///
141    /// For example, if the tree has extents 0..50, 50..150 and 150..200 and we wish to insert
142    /// 100..150, we'd use a merge hint of 0..100 which would set the iterator to 50..150 (the first
143    /// element > 100..150 under Ord).
144    pub fn key_for_merge_into(&self) -> Self {
145        Self { range: 0..self.range.start }
146    }
147
148    /// Returns an iterator over the ExtentKey partitions which overlap this key (see `FuzzyHash`).
149    pub fn fuzzy_hash_partition(&self) -> ExtentKeyPartitionIterator {
150        ExtentKeyPartitionIterator {
151            range: round_down(self.range.start, EXTENT_HASH_BUCKET_SIZE)
152                ..round_up(self.range.end, EXTENT_HASH_BUCKET_SIZE).unwrap_or(u64::MAX),
153        }
154    }
155}
156
157// The normal comparison uses the end of the range before the start of the range. This makes
158// searching for records easier because it's easy to find K.. (where K is the key you are searching
159// for), which is what we want since our search routines find items with keys >= a search key.
160// OrdLowerBound orders by the start of an extent.
161impl OrdUpperBound for ExtentKey {
162    fn cmp_upper_bound(&self, other: &ExtentKey) -> std::cmp::Ordering {
163        // The comparison uses the end of the range so that we can more easily do queries. Ties
164        // are broken by comparing the range start to provide a total ordering consistent with
165        // serialization. Since we do not support overlapping keys within the same layer, ties can
166        // always be broken using layer index. Insertions into the mutable layer should always be
167        // done using merge_into, which will ensure keys don't end up overlapping.
168        self.range.end.cmp(&other.range.end).then(self.range.start.cmp(&other.range.start))
169    }
170}
171
172impl OrdLowerBound for ExtentKey {
173    // Orders by the start of the range rather than the end, and doesn't include the end in the
174    // comparison. This is used when merging, where we want to merge keys in lower-bound order.
175    fn cmp_lower_bound(&self, other: &ExtentKey) -> std::cmp::Ordering {
176        self.range.start.cmp(&other.range.start)
177    }
178}
179
180impl Ord for ExtentKey {
181    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
182        // We expect cmp_upper_bound and cmp_lower_bound to be used mostly, but ObjectKey needs an
183        // Ord method in order to compare other enum variants, and Transaction requires an ObjectKey
184        // to implement Ord.
185        self.range.start.cmp(&other.range.start).then(self.range.end.cmp(&other.range.end))
186    }
187}
188
189impl PartialOrd for ExtentKey {
190    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
191        Some(self.cmp(other))
192    }
193}
194
195/// The mode the extent is operating in. This changes how writes work to this region of the file.
196pub type ExtentMode = ExtentModeV38;
197
198#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, TypeFingerprint)]
199pub enum ExtentModeV38 {
200    /// This extent doesn't have defined write semantics. The writer chooses how to handle the data
201    /// here. Notable uses of this are things which have their own separate checksum mechanism,
202    /// like the journal file and blobs.
203    Raw,
204    /// This extent uses copy-on-write semantics. We store the post-encryption checksums for data
205    /// validation. New writes to this logical range are written to new extents.
206    Cow(ChecksumsV38),
207    /// This extent uses overwrite semantics. The bitmap keeps track of blocks which have been
208    /// written to at least once. Blocks which haven't been written to at least once are logically
209    /// zero, so the bitmap needs to be accounted for while reading. While this extent exists, new
210    /// writes to this logical range will go to the same on-disk location.
211    OverwritePartial(BitVec),
212    /// This extent uses overwrite semantics. Every block in this extent has been written to at
213    /// least once, so we don't store the block bitmap anymore. While this extent exists, new
214    /// writes to this logical range will go to the same on-disk location.
215    Overwrite,
216}
217
218#[cfg(fuzz)]
219impl<'a> arbitrary::Arbitrary<'a> for ExtentMode {
220    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
221        Ok(match u.int_in_range(0..=3)? {
222            0 => ExtentMode::Raw,
223            1 => ExtentMode::Cow(u.arbitrary()?),
224            2 => ExtentMode::OverwritePartial(BitVec::from_bytes(u.arbitrary()?)),
225            3 => ExtentMode::Overwrite,
226            _ => unreachable!(),
227        })
228    }
229}
230
231/// ExtentValue is the payload for an extent in the object store, which describes where the extent
232/// is physically located.
233pub type ExtentValue = ExtentValueV38;
234
235#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, TypeFingerprint)]
236#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
237pub enum ExtentValueV38 {
238    /// Indicates a deleted extent; that is, the logical range described by the extent key is
239    /// considered to be deleted.
240    None,
241    /// The location of the extent and other related information.  `key_id` identifies which of the
242    /// object's keys should be used.  Unencrypted files should use 0 (which can also be used for
243    /// encrypted files).  `mode` describes the write pattern for this extent.
244    Some { device_offset: u64, mode: ExtentModeV38, key_id: u64 },
245}
246
247impl ExtentValue {
248    pub fn new(device_offset: u64, mode: ExtentMode, key_id: u64) -> ExtentValue {
249        ExtentValue::Some { device_offset, mode, key_id }
250    }
251
252    pub fn new_raw(device_offset: u64, key_id: u64) -> ExtentValue {
253        Self::new(device_offset, ExtentMode::Raw, key_id)
254    }
255
256    /// Creates an ExtentValue with a checksum
257    pub fn with_checksum(device_offset: u64, checksums: Checksums, key_id: u64) -> ExtentValue {
258        Self::new(device_offset, ExtentMode::Cow(checksums), key_id)
259    }
260
261    /// Creates an ExtentValue for an overwrite range with no blocks written to yet.
262    pub fn blank_overwrite_extent(
263        device_offset: u64,
264        num_blocks: usize,
265        key_id: u64,
266    ) -> ExtentValue {
267        Self::new(
268            device_offset,
269            ExtentMode::OverwritePartial(BitVec::from_elem(num_blocks, false)),
270            key_id,
271        )
272    }
273
274    /// Creates an ExtentValue for an overwrite range with all the blocks initialized.
275    pub fn initialized_overwrite_extent(device_offset: u64, key_id: u64) -> ExtentValue {
276        Self::new(device_offset, ExtentMode::Overwrite, key_id)
277    }
278
279    /// Creates an ObjectValue for a deletion of an object extent.
280    pub fn deleted_extent() -> ExtentValue {
281        ExtentValue::None
282    }
283
284    pub fn is_deleted(&self) -> bool {
285        if let ExtentValue::None = self { true } else { false }
286    }
287
288    /// Returns a new ExtentValue offset by `amount`.  Both `amount` and `extent_len` must be
289    /// multiples of the underlying block size.
290    pub fn offset_by(&self, amount: u64, extent_len: u64) -> Self {
291        match self {
292            ExtentValue::None => Self::deleted_extent(),
293            ExtentValue::Some { device_offset, mode, key_id } => {
294                let mode = match mode {
295                    ExtentMode::Raw => ExtentMode::Raw,
296                    ExtentMode::Cow(checksums) => {
297                        if checksums.len() > 0 {
298                            let index = (amount / (extent_len / checksums.len() as u64)) as usize;
299                            ExtentMode::Cow(checksums.offset_by(index))
300                        } else {
301                            ExtentMode::Cow(Checksums::fletcher(Vec::new()))
302                        }
303                    }
304                    ExtentMode::Overwrite => ExtentMode::Overwrite,
305                    ExtentMode::OverwritePartial(bitmap) => {
306                        debug_assert!(bitmap.len() > 0);
307                        let index = (amount / (extent_len / bitmap.len() as u64)) as usize;
308                        ExtentMode::OverwritePartial(bitmap.clone().split_off(index))
309                    }
310                };
311                ExtentValue::Some { device_offset: device_offset + amount, mode, key_id: *key_id }
312            }
313        }
314    }
315
316    /// Returns a new ExtentValue after shrinking the extent from |original_len| to |new_len|.
317    pub fn shrunk(&self, original_len: u64, new_len: u64) -> Self {
318        match self {
319            ExtentValue::None => Self::deleted_extent(),
320            ExtentValue::Some { device_offset, mode, key_id } => {
321                let mode = match mode {
322                    ExtentMode::Raw => ExtentMode::Raw,
323                    ExtentMode::Cow(checksums) => {
324                        if checksums.len() > 0 {
325                            let len = (new_len / (original_len / checksums.len() as u64)) as usize;
326                            ExtentMode::Cow(checksums.shrunk(len))
327                        } else {
328                            ExtentMode::Cow(Checksums::fletcher(Vec::new()))
329                        }
330                    }
331                    ExtentMode::Overwrite => ExtentMode::Overwrite,
332                    ExtentMode::OverwritePartial(bitmap) => {
333                        debug_assert!(bitmap.len() > 0);
334                        let len = (new_len / (original_len / bitmap.len() as u64)) as usize;
335                        let mut new_bitmap = bitmap.clone();
336                        new_bitmap.truncate(len);
337                        ExtentMode::OverwritePartial(new_bitmap)
338                    }
339                };
340                ExtentValue::Some { device_offset: *device_offset, mode, key_id: *key_id }
341            }
342        }
343    }
344}
345
346#[cfg(test)]
347mod tests {
348    use super::{ExtentKey, ExtentMode, ExtentValue};
349    use crate::checksum::Checksums;
350    use crate::lsm_tree::types::{OrdLowerBound, OrdUpperBound};
351    use crate::object_store::VOLUME_DATA_KEY_ID;
352    use crate::serialized_types::serialized_key::{KeyDeserializer, SerializeKey};
353    use bit_vec::BitVec;
354    use std::cmp::Ordering;
355
356    #[test]
357    fn test_extent_key_serialization() {
358        let key = ExtentKey::new(1024..2048);
359        let mut buf = Vec::new();
360
361        // Serialize
362        {
363            let mut ser =
364                crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, Some(0));
365            key.serialize_key_to(&mut ser);
366            ser.finalize();
367        }
368
369        let (mut deser, length) = KeyDeserializer::new(&buf, Some(0)).unwrap();
370        assert_eq!(length, buf.len());
371        let decoded_key = ExtentKey::deserialize_key_from(&mut deser).unwrap();
372
373        assert_eq!(key, decoded_key);
374
375        // Verify bytes:
376        // 2048 / 512 = 4.
377        // 1024 / 512 = 2.
378        // Delta encoding applies to first field (end = 4). Base is 0. 4 - 0 = 4.
379        // Second field is start = 2. Base is None (taken). So writes 2.
380        // Buffer should be [0, 2, 4, 2].
381        assert_eq!(buf, vec![0, 2, 4, 2]);
382    }
383
384    #[test]
385    fn test_extent_key_deserialization_overflow() {
386        let mut buf = Vec::new();
387        {
388            let mut ser =
389                crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
390            ser.write_u64(u64::MAX);
391            ser.write_u64(u64::MAX);
392            ser.finalize();
393        }
394        let (mut deser, length) = KeyDeserializer::new(&buf, None).unwrap();
395        assert_eq!(length, buf.len());
396        let result = ExtentKey::deserialize_key_from(&mut deser);
397        assert!(result.is_err());
398        assert_eq!(result.unwrap_err().to_string(), "Overflow");
399    }
400
401    #[test]
402    #[should_panic(expected = "Extent end must be 512-byte aligned")]
403    fn test_extent_key_serialization_unaligned_end_panics() {
404        let key = ExtentKey::new(1024..2049);
405        let mut buf = Vec::new();
406        let mut ser = crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
407        key.serialize_key_to(&mut ser);
408    }
409
410    #[test]
411    #[should_panic(expected = "Extent start must be 512-byte aligned")]
412    fn test_extent_key_serialization_unaligned_start_panics() {
413        let key = ExtentKey::new(1025..2048);
414        let mut buf = Vec::new();
415        let mut ser = crate::serialized_types::serialized_key::KeySerializer::new(&mut buf, None);
416        key.serialize_key_to(&mut ser);
417    }
418
419    #[test]
420    fn test_extent_cmp() {
421        let extent = ExtentKey::new(100..150);
422        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..100)), Ordering::Greater);
423        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..110)), Ordering::Greater);
424        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..150)), Ordering::Greater);
425        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(99..150)), Ordering::Greater);
426        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(100..150)), Ordering::Equal);
427        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..151)), Ordering::Less);
428        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(100..151)), Ordering::Less);
429        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(150..1000)), Ordering::Less);
430        assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(101..150)), Ordering::Less);
431    }
432
433    #[test]
434    fn test_extent_cmp_lower_bound() {
435        let extent = ExtentKey::new(100..150);
436        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..100)), Ordering::Greater);
437        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..110)), Ordering::Greater);
438        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..150)), Ordering::Greater);
439        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..1000)), Ordering::Greater);
440        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(99..1000)), Ordering::Greater);
441        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(100..150)), Ordering::Equal);
442        // cmp_lower_bound does not check the upper bound of the range
443        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(100..1000)), Ordering::Equal);
444        assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(101..102)), Ordering::Less);
445    }
446
447    #[test]
448    fn test_extent_search_and_insertion_key() {
449        let extent = ExtentKey::new(100..150);
450        assert_eq!(extent.search_key(), ExtentKey::new(0..101));
451        assert_eq!(extent.cmp_lower_bound(&extent.search_key()), Ordering::Greater);
452        assert_eq!(extent.cmp_upper_bound(&extent.search_key()), Ordering::Greater);
453        assert_eq!(extent.key_for_merge_into(), ExtentKey::new(0..100));
454        assert_eq!(extent.cmp_lower_bound(&extent.key_for_merge_into()), Ordering::Greater);
455    }
456
457    #[test]
458    fn extent_value_offset_by() {
459        assert_eq!(ExtentValue::None.offset_by(1024, 2048), ExtentValue::None);
460        assert_eq!(
461            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(0, 2048),
462            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
463        );
464        assert_eq!(
465            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(1024, 2048),
466            ExtentValue::new_raw(2048, VOLUME_DATA_KEY_ID)
467        );
468        assert_eq!(
469            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(2048, 2048),
470            ExtentValue::new_raw(3072, VOLUME_DATA_KEY_ID)
471        );
472
473        let make_checksums = |range: std::ops::Range<u64>| Checksums::fletcher(range.collect());
474
475        // In these tests we are making block size 256.
476        assert_eq!(
477            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
478                .offset_by(0, 2048),
479            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
480        );
481        assert_eq!(
482            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
483                .offset_by(1024, 2048),
484            ExtentValue::with_checksum(2048, make_checksums(4..8), VOLUME_DATA_KEY_ID)
485        );
486        assert_eq!(
487            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
488                .offset_by(2048, 2048),
489            ExtentValue::with_checksum(3072, Checksums::fletcher(Vec::new()), VOLUME_DATA_KEY_ID)
490        );
491
492        // Takes a place to switch from zeros to ones. The goal is to make sure there is exactly
493        // one zero and then only ones where we expect offset to slice.
494        let make_bitmap = |cut, length| {
495            let mut begin_bitmap = BitVec::from_elem(cut, false);
496            let mut end_bitmap = BitVec::from_elem(length - cut, true);
497            begin_bitmap.append(&mut end_bitmap);
498            ExtentMode::OverwritePartial(begin_bitmap)
499        };
500        let make_extent =
501            |device_offset, mode| ExtentValue::Some { device_offset, mode, key_id: 0 };
502
503        assert_eq!(
504            make_extent(1024, make_bitmap(1, 8)).offset_by(0, 2048),
505            make_extent(1024, make_bitmap(1, 8))
506        );
507        assert_eq!(
508            make_extent(1024, make_bitmap(5, 8)).offset_by(1024, 2048),
509            make_extent(2048, make_bitmap(1, 4))
510        );
511        assert_eq!(
512            make_extent(1024, make_bitmap(0, 8)).offset_by(2048, 2048),
513            make_extent(3072, ExtentMode::OverwritePartial(BitVec::new()))
514        );
515
516        assert_eq!(
517            make_extent(1024, ExtentMode::Overwrite).offset_by(0, 2048),
518            make_extent(1024, ExtentMode::Overwrite)
519        );
520        assert_eq!(
521            make_extent(1024, ExtentMode::Overwrite).offset_by(1024, 2048),
522            make_extent(2048, ExtentMode::Overwrite)
523        );
524        assert_eq!(
525            make_extent(1024, ExtentMode::Overwrite).offset_by(2048, 2048),
526            make_extent(3072, ExtentMode::Overwrite)
527        );
528    }
529
530    #[test]
531    fn extent_value_shrunk() {
532        assert_eq!(ExtentValue::None.shrunk(2048, 1024), ExtentValue::None);
533        assert_eq!(
534            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 2048),
535            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
536        );
537        assert_eq!(
538            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 1024),
539            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
540        );
541        assert_eq!(
542            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 0),
543            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
544        );
545
546        let make_checksums = |range: std::ops::Range<u64>| Checksums::fletcher(range.collect());
547
548        // In these tests we are making block size 256.
549        assert_eq!(
550            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
551                .shrunk(2048, 2048),
552            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
553        );
554        assert_eq!(
555            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
556                .shrunk(2048, 1024),
557            ExtentValue::with_checksum(1024, make_checksums(0..4), VOLUME_DATA_KEY_ID)
558        );
559        assert_eq!(
560            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
561                .shrunk(2048, 0),
562            ExtentValue::with_checksum(1024, Checksums::fletcher(Vec::new()), VOLUME_DATA_KEY_ID)
563        );
564
565        // Takes a place to switch from zeros to ones. The goal is to make sure there is exactly
566        // one zero and then only ones where we expect offset to slice.
567        let make_bitmap = |cut, length| {
568            let mut begin_bitmap = BitVec::from_elem(cut, false);
569            let mut end_bitmap = BitVec::from_elem(length - cut, true);
570            begin_bitmap.append(&mut end_bitmap);
571            ExtentMode::OverwritePartial(begin_bitmap)
572        };
573        let make_extent =
574            |device_offset, mode| ExtentValue::Some { device_offset, mode, key_id: 0 };
575
576        assert_eq!(
577            make_extent(1024, make_bitmap(1, 8)).shrunk(2048, 2048),
578            make_extent(1024, make_bitmap(1, 8))
579        );
580        assert_eq!(
581            make_extent(1024, make_bitmap(3, 8)).shrunk(2048, 1024),
582            make_extent(1024, make_bitmap(3, 4))
583        );
584        assert_eq!(
585            make_extent(1024, make_bitmap(0, 8)).shrunk(2048, 0),
586            make_extent(1024, ExtentMode::OverwritePartial(BitVec::new()))
587        );
588
589        assert_eq!(
590            make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 2048),
591            make_extent(1024, ExtentMode::Overwrite)
592        );
593        assert_eq!(
594            make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 1024),
595            make_extent(1024, ExtentMode::Overwrite)
596        );
597        assert_eq!(
598            make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 0),
599            make_extent(1024, ExtentMode::Overwrite)
600        );
601    }
602}
fxfs/object_store/extent_record.rs

fxfs/object_store/
extent_record.rs
