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 bit_vec::BitVec;
9use fprint::TypeFingerprint;
10use serde::{Deserialize, Serialize};
11
12/// The mode the extent is operating in. This changes how writes work to this region of the file.
13pub type ExtentMode = ExtentModeV38;
14
15#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, TypeFingerprint)]
16pub enum ExtentModeV38 {
17    /// This extent doesn't have defined write semantics. The writer chooses how to handle the data
18    /// here. Notable uses of this are things which have their own separate checksum mechanism,
19    /// like the journal file and blobs.
20    Raw,
21    /// This extent uses copy-on-write semantics. We store the post-encryption checksums for data
22    /// validation. New writes to this logical range are written to new extents.
23    Cow(ChecksumsV38),
24    /// This extent uses overwrite semantics. The bitmap keeps track of blocks which have been
25    /// written to at least once. Blocks which haven't been written to at least once are logically
26    /// zero, so the bitmap needs to be accounted for while reading. While this extent exists, new
27    /// writes to this logical range will go to the same on-disk location.
28    OverwritePartial(BitVec),
29    /// This extent uses overwrite semantics. Every block in this extent has been written to at
30    /// least once, so we don't store the block bitmap anymore. While this extent exists, new
31    /// writes to this logical range will go to the same on-disk location.
32    Overwrite,
33}
34
35#[cfg(fuzz)]
36impl<'a> arbitrary::Arbitrary<'a> for ExtentMode {
37    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
38        Ok(match u.int_in_range(0..=3)? {
39            0 => ExtentMode::Raw,
40            1 => ExtentMode::Cow(u.arbitrary()?),
41            2 => ExtentMode::OverwritePartial(BitVec::from_bytes(u.arbitrary()?)),
42            3 => ExtentMode::Overwrite,
43            _ => unreachable!(),
44        })
45    }
46}
47
48/// ExtentValue is the payload for an extent in the object store, which describes where the extent
49/// is physically located.
50pub type ExtentValue = ExtentValueV38;
51
52#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, TypeFingerprint)]
53#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
54pub enum ExtentValueV38 {
55    /// Indicates a deleted extent; that is, the logical range described by the extent key is
56    /// considered to be deleted.
57    None,
58    /// The location of the extent and other related information.  `key_id` identifies which of the
59    /// object's keys should be used.  Unencrypted files should use 0 (which can also be used for
60    /// encrypted files).  `mode` describes the write pattern for this extent.
61    Some { device_offset: u64, mode: ExtentModeV38, key_id: u64 },
62}
63
64impl ExtentValue {
65    pub fn new(device_offset: u64, mode: ExtentMode, key_id: u64) -> ExtentValue {
66        ExtentValue::Some { device_offset, mode, key_id }
67    }
68
69    pub fn new_raw(device_offset: u64, key_id: u64) -> ExtentValue {
70        Self::new(device_offset, ExtentMode::Raw, key_id)
71    }
72
73    /// Creates an ExtentValue with a checksum
74    pub fn with_checksum(device_offset: u64, checksums: Checksums, key_id: u64) -> ExtentValue {
75        Self::new(device_offset, ExtentMode::Cow(checksums), key_id)
76    }
77
78    /// Creates an ExtentValue for an overwrite range with no blocks written to yet.
79    pub fn blank_overwrite_extent(
80        device_offset: u64,
81        num_blocks: usize,
82        key_id: u64,
83    ) -> ExtentValue {
84        Self::new(
85            device_offset,
86            ExtentMode::OverwritePartial(BitVec::from_elem(num_blocks, false)),
87            key_id,
88        )
89    }
90
91    /// Creates an ExtentValue for an overwrite range with all the blocks initialized.
92    pub fn initialized_overwrite_extent(device_offset: u64, key_id: u64) -> ExtentValue {
93        Self::new(device_offset, ExtentMode::Overwrite, key_id)
94    }
95
96    /// Creates an ObjectValue for a deletion of an object extent.
97    pub fn deleted_extent() -> ExtentValue {
98        ExtentValue::None
99    }
100
101    pub fn is_deleted(&self) -> bool {
102        if let ExtentValue::None = self { true } else { false }
103    }
104
105    /// Returns a new ExtentValue offset by `amount`.  Both `amount` and `extent_len` must be
106    /// multiples of the underlying block size.
107    pub fn offset_by(&self, amount: u64, extent_len: u64) -> Self {
108        match self {
109            ExtentValue::None => Self::deleted_extent(),
110            ExtentValue::Some { device_offset, mode, key_id } => {
111                let mode = match mode {
112                    ExtentMode::Raw => ExtentMode::Raw,
113                    ExtentMode::Cow(checksums) => {
114                        if checksums.len() > 0 {
115                            let index = (amount / (extent_len / checksums.len() as u64)) as usize;
116                            ExtentMode::Cow(checksums.offset_by(index))
117                        } else {
118                            ExtentMode::Cow(Checksums::fletcher(Vec::new()))
119                        }
120                    }
121                    ExtentMode::Overwrite => ExtentMode::Overwrite,
122                    ExtentMode::OverwritePartial(bitmap) => {
123                        debug_assert!(bitmap.len() > 0);
124                        let index = (amount / (extent_len / bitmap.len() as u64)) as usize;
125                        ExtentMode::OverwritePartial(bitmap.clone().split_off(index))
126                    }
127                };
128                ExtentValue::Some { device_offset: device_offset + amount, mode, key_id: *key_id }
129            }
130        }
131    }
132
133    /// Returns a new ExtentValue after shrinking the extent from |original_len| to |new_len|.
134    pub fn shrunk(&self, original_len: u64, new_len: u64) -> Self {
135        match self {
136            ExtentValue::None => Self::deleted_extent(),
137            ExtentValue::Some { device_offset, mode, key_id } => {
138                let mode = match mode {
139                    ExtentMode::Raw => ExtentMode::Raw,
140                    ExtentMode::Cow(checksums) => {
141                        if checksums.len() > 0 {
142                            let len = (new_len / (original_len / checksums.len() as u64)) as usize;
143                            ExtentMode::Cow(checksums.shrunk(len))
144                        } else {
145                            ExtentMode::Cow(Checksums::fletcher(Vec::new()))
146                        }
147                    }
148                    ExtentMode::Overwrite => ExtentMode::Overwrite,
149                    ExtentMode::OverwritePartial(bitmap) => {
150                        debug_assert!(bitmap.len() > 0);
151                        let len = (new_len / (original_len / bitmap.len() as u64)) as usize;
152                        let mut new_bitmap = bitmap.clone();
153                        new_bitmap.truncate(len);
154                        ExtentMode::OverwritePartial(new_bitmap)
155                    }
156                };
157                ExtentValue::Some { device_offset: *device_offset, mode, key_id: *key_id }
158            }
159        }
160    }
161}
162
163#[cfg(test)]
164mod tests {
165    use super::{ExtentMode, ExtentValue};
166    use crate::checksum::Checksums;
167    use crate::object_store::VOLUME_DATA_KEY_ID;
168    use bit_vec::BitVec;
169
170    #[test]
171    fn extent_value_offset_by() {
172        assert_eq!(ExtentValue::None.offset_by(1024, 2048), ExtentValue::None);
173        assert_eq!(
174            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(0, 2048),
175            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
176        );
177        assert_eq!(
178            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(1024, 2048),
179            ExtentValue::new_raw(2048, VOLUME_DATA_KEY_ID)
180        );
181        assert_eq!(
182            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(2048, 2048),
183            ExtentValue::new_raw(3072, VOLUME_DATA_KEY_ID)
184        );
185
186        let make_checksums = |range: std::ops::Range<u64>| Checksums::fletcher(range.collect());
187
188        // In these tests we are making block size 256.
189        assert_eq!(
190            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
191                .offset_by(0, 2048),
192            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
193        );
194        assert_eq!(
195            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
196                .offset_by(1024, 2048),
197            ExtentValue::with_checksum(2048, make_checksums(4..8), VOLUME_DATA_KEY_ID)
198        );
199        assert_eq!(
200            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
201                .offset_by(2048, 2048),
202            ExtentValue::with_checksum(3072, Checksums::fletcher(Vec::new()), VOLUME_DATA_KEY_ID)
203        );
204
205        // Takes a place to switch from zeros to ones. The goal is to make sure there is exactly
206        // one zero and then only ones where we expect offset to slice.
207        let make_bitmap = |cut, length| {
208            let mut begin_bitmap = BitVec::from_elem(cut, false);
209            let mut end_bitmap = BitVec::from_elem(length - cut, true);
210            begin_bitmap.append(&mut end_bitmap);
211            ExtentMode::OverwritePartial(begin_bitmap)
212        };
213        let make_extent =
214            |device_offset, mode| ExtentValue::Some { device_offset, mode, key_id: 0 };
215
216        assert_eq!(
217            make_extent(1024, make_bitmap(1, 8)).offset_by(0, 2048),
218            make_extent(1024, make_bitmap(1, 8))
219        );
220        assert_eq!(
221            make_extent(1024, make_bitmap(5, 8)).offset_by(1024, 2048),
222            make_extent(2048, make_bitmap(1, 4))
223        );
224        assert_eq!(
225            make_extent(1024, make_bitmap(0, 8)).offset_by(2048, 2048),
226            make_extent(3072, ExtentMode::OverwritePartial(BitVec::new()))
227        );
228
229        assert_eq!(
230            make_extent(1024, ExtentMode::Overwrite).offset_by(0, 2048),
231            make_extent(1024, ExtentMode::Overwrite)
232        );
233        assert_eq!(
234            make_extent(1024, ExtentMode::Overwrite).offset_by(1024, 2048),
235            make_extent(2048, ExtentMode::Overwrite)
236        );
237        assert_eq!(
238            make_extent(1024, ExtentMode::Overwrite).offset_by(2048, 2048),
239            make_extent(3072, ExtentMode::Overwrite)
240        );
241    }
242
243    #[test]
244    fn extent_value_shrunk() {
245        assert_eq!(ExtentValue::None.shrunk(2048, 1024), ExtentValue::None);
246        assert_eq!(
247            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 2048),
248            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
249        );
250        assert_eq!(
251            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 1024),
252            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
253        );
254        assert_eq!(
255            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 0),
256            ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
257        );
258
259        let make_checksums = |range: std::ops::Range<u64>| Checksums::fletcher(range.collect());
260
261        // In these tests we are making block size 256.
262        assert_eq!(
263            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
264                .shrunk(2048, 2048),
265            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
266        );
267        assert_eq!(
268            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
269                .shrunk(2048, 1024),
270            ExtentValue::with_checksum(1024, make_checksums(0..4), VOLUME_DATA_KEY_ID)
271        );
272        assert_eq!(
273            ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
274                .shrunk(2048, 0),
275            ExtentValue::with_checksum(1024, Checksums::fletcher(Vec::new()), VOLUME_DATA_KEY_ID)
276        );
277
278        // Takes a place to switch from zeros to ones. The goal is to make sure there is exactly
279        // one zero and then only ones where we expect offset to slice.
280        let make_bitmap = |cut, length| {
281            let mut begin_bitmap = BitVec::from_elem(cut, false);
282            let mut end_bitmap = BitVec::from_elem(length - cut, true);
283            begin_bitmap.append(&mut end_bitmap);
284            ExtentMode::OverwritePartial(begin_bitmap)
285        };
286        let make_extent =
287            |device_offset, mode| ExtentValue::Some { device_offset, mode, key_id: 0 };
288
289        assert_eq!(
290            make_extent(1024, make_bitmap(1, 8)).shrunk(2048, 2048),
291            make_extent(1024, make_bitmap(1, 8))
292        );
293        assert_eq!(
294            make_extent(1024, make_bitmap(3, 8)).shrunk(2048, 1024),
295            make_extent(1024, make_bitmap(3, 4))
296        );
297        assert_eq!(
298            make_extent(1024, make_bitmap(0, 8)).shrunk(2048, 0),
299            make_extent(1024, ExtentMode::OverwritePartial(BitVec::new()))
300        );
301
302        assert_eq!(
303            make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 2048),
304            make_extent(1024, ExtentMode::Overwrite)
305        );
306        assert_eq!(
307            make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 1024),
308            make_extent(1024, ExtentMode::Overwrite)
309        );
310        assert_eq!(
311            make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 0),
312            make_extent(1024, ExtentMode::Overwrite)
313        );
314    }
315}
fxfs/object_store/extent_record.rs

fxfs/object_store/
extent_record.rs
