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

fxfs/object_store/
extent_record.rs
