fxfs/object_store/
object_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
5mod legacy;
6
7pub use legacy::*;
8
9// TODO(https://fxbug.dev/42178223): need validation after deserialization.
10use crate::checksum::Checksums;
11use crate::log::error;
12use crate::lsm_tree::types::{
13    FuzzyHash, Item, ItemRef, LayerKey, MergeType, OrdLowerBound, OrdUpperBound, RangeKey,
14    SortByU64, Value,
15};
16use crate::object_store::extent_record::{
17    ExtentKey, ExtentKeyPartitionIterator, ExtentKeyV32, ExtentValue, ExtentValueV38,
18};
19use crate::serialized_types::{Migrate, Versioned, migrate_nodefault, migrate_to_version};
20use fprint::TypeFingerprint;
21use fxfs_crypto::{WrappedKey, WrappingKeyId};
22use fxfs_unicode::CasefoldString;
23use serde::{Deserialize, Serialize};
24use std::collections::BTreeMap;
25use std::default::Default;
26use std::hash::Hash;
27use std::time::{Duration, SystemTime, UNIX_EPOCH};
28
29/// ObjectDescriptor is the set of possible records in the object store.
30pub type ObjectDescriptor = ObjectDescriptorV32;
31
32#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, TypeFingerprint)]
33#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
34pub enum ObjectDescriptorV32 {
35    /// A file (in the generic sense; i.e. an object with some attributes).
36    File,
37    /// A directory (in the generic sense; i.e. an object with children).
38    Directory,
39    /// A volume, which is the root of a distinct object store containing Files and Directories.
40    Volume,
41    /// A symbolic link.
42    Symlink,
43}
44
45/// For specifying what property of the project is being addressed.
46pub type ProjectProperty = ProjectPropertyV32;
47
48#[derive(
49    Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize, Deserialize, TypeFingerprint,
50)]
51#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
52pub enum ProjectPropertyV32 {
53    /// The configured limit for the project.
54    Limit,
55    /// The currently tracked usage for the project.
56    Usage,
57}
58
59pub type ObjectKeyData = ObjectKeyDataV43;
60
61#[derive(
62    Clone, Debug, Eq, Hash, PartialEq, PartialOrd, Ord, Serialize, Deserialize, TypeFingerprint,
63)]
64#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
65pub enum ObjectKeyDataV43 {
66    /// A generic, untyped object.  This must come first and sort before all other keys for a given
67    /// object because it's also used as a tombstone and it needs to merge with all following keys.
68    Object,
69    /// Encryption keys for an object.
70    Keys,
71    /// An attribute associated with an object.  It has a 64-bit ID.
72    Attribute(u64, AttributeKeyV32),
73    /// A child of a directory.
74    Child { name: String },
75    /// A graveyard entry for an entire object.
76    GraveyardEntry { object_id: u64 },
77    /// Project ID info. This should only be attached to the volume's root node. Used to address the
78    /// configured limit and the usage tracking which are ordered after the `project_id` to provide
79    /// locality of the two related values.
80    Project { project_id: u64, property: ProjectPropertyV32 },
81    /// An extended attribute associated with an object. It stores the name used for the extended
82    /// attribute, which has a maximum size of 255 bytes enforced by fuchsia.io.
83    ExtendedAttribute { name: Vec<u8> },
84    /// A graveyard entry for an attribute.
85    GraveyardAttributeEntry { object_id: u64, attribute_id: u64 },
86    /// A child of an encrypted directory.
87    /// We store the filename in its encrypted form.
88    /// hash_code is the hash of the casefolded human-readable name if a directory is
89    /// also casefolded, otherwise 0.
90    /// Legacy records may have a hash_code of 0 indicating "unknown".
91    EncryptedChild { hash_code: u32, name: Vec<u8> },
92    /// A child of a directory that uses the casefold feature.
93    /// (i.e. case insensitive, case preserving names)
94    CasefoldChild { name: CasefoldString },
95}
96
97pub type AttributeKey = AttributeKeyV32;
98
99#[derive(
100    Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize, Deserialize, TypeFingerprint,
101)]
102#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
103pub enum AttributeKeyV32 {
104    // Order here is important: code expects Attribute to precede Extent.
105    Attribute,
106    Extent(ExtentKeyV32),
107}
108
109/// ObjectKey is a key in the object store.
110pub type ObjectKey = ObjectKeyV43;
111
112#[derive(
113    Clone,
114    Debug,
115    Eq,
116    Ord,
117    Hash,
118    PartialEq,
119    PartialOrd,
120    Serialize,
121    Deserialize,
122    TypeFingerprint,
123    Versioned,
124)]
125#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
126pub struct ObjectKeyV43 {
127    /// The ID of the object referred to.
128    pub object_id: u64,
129    /// The type and data of the key.
130    pub data: ObjectKeyDataV43,
131}
132
133impl SortByU64 for ObjectKey {
134    fn get_leading_u64(&self) -> u64 {
135        self.object_id
136    }
137}
138
139impl ObjectKey {
140    /// Creates a generic ObjectKey.
141    pub fn object(object_id: u64) -> Self {
142        Self { object_id: object_id, data: ObjectKeyData::Object }
143    }
144
145    /// Creates an ObjectKey for encryption keys.
146    pub fn keys(object_id: u64) -> Self {
147        Self { object_id, data: ObjectKeyData::Keys }
148    }
149
150    /// Creates an ObjectKey for an attribute.
151    pub fn attribute(object_id: u64, attribute_id: u64, key: AttributeKey) -> Self {
152        Self { object_id, data: ObjectKeyData::Attribute(attribute_id, key) }
153    }
154
155    /// Creates an ObjectKey for an extent.
156    pub fn extent(object_id: u64, attribute_id: u64, range: std::ops::Range<u64>) -> Self {
157        Self {
158            object_id,
159            data: ObjectKeyData::Attribute(
160                attribute_id,
161                AttributeKey::Extent(ExtentKey::new(range)),
162            ),
163        }
164    }
165
166    /// Creates an ObjectKey from an extent.
167    pub fn from_extent(object_id: u64, attribute_id: u64, extent: ExtentKey) -> Self {
168        Self {
169            object_id,
170            data: ObjectKeyData::Attribute(attribute_id, AttributeKey::Extent(extent)),
171        }
172    }
173
174    /// Creates an ObjectKey for a child.
175    pub fn child(object_id: u64, name: &str, casefold: bool) -> Self {
176        if casefold {
177            Self { object_id, data: ObjectKeyData::CasefoldChild { name: name.into() } }
178        } else {
179            Self { object_id, data: ObjectKeyData::Child { name: name.into() } }
180        }
181    }
182
183    /// Creates an ObjectKey for an encrypted child.
184    ///
185    /// The hash_code is important here -- especially for fscrypt as it affects the
186    /// name of locked files.
187    ///
188    /// For case-insensitive lookups in large encrypted directories, we lose the ability to binary
189    /// search for an entry of interest because encryption breaks our sort order. In these cases
190    /// we prefix records with a 32-bit hash based on the stable *casefolded* name. Hash collisions
191    /// aside, this lets us jump straight to the entry of interest, if it exists.
192    pub fn encrypted_child(object_id: u64, name: Vec<u8>, hash_code: u32) -> Self {
193        Self { object_id, data: ObjectKeyData::EncryptedChild { hash_code, name } }
194    }
195
196    /// Creates a graveyard entry for an object.
197    pub fn graveyard_entry(graveyard_object_id: u64, object_id: u64) -> Self {
198        Self { object_id: graveyard_object_id, data: ObjectKeyData::GraveyardEntry { object_id } }
199    }
200
201    /// Creates a graveyard entry for an attribute.
202    pub fn graveyard_attribute_entry(
203        graveyard_object_id: u64,
204        object_id: u64,
205        attribute_id: u64,
206    ) -> Self {
207        Self {
208            object_id: graveyard_object_id,
209            data: ObjectKeyData::GraveyardAttributeEntry { object_id, attribute_id },
210        }
211    }
212
213    /// Creates an ObjectKey for a ProjectLimit entry.
214    pub fn project_limit(object_id: u64, project_id: u64) -> Self {
215        Self {
216            object_id,
217            data: ObjectKeyData::Project { project_id, property: ProjectProperty::Limit },
218        }
219    }
220
221    /// Creates an ObjectKey for a ProjectUsage entry.
222    pub fn project_usage(object_id: u64, project_id: u64) -> Self {
223        Self {
224            object_id,
225            data: ObjectKeyData::Project { project_id, property: ProjectProperty::Usage },
226        }
227    }
228
229    pub fn extended_attribute(object_id: u64, name: Vec<u8>) -> Self {
230        Self { object_id, data: ObjectKeyData::ExtendedAttribute { name } }
231    }
232
233    /// Returns the merge key for this key; that is, a key which is <= this key and any
234    /// other possibly overlapping key, under Ord. This would be used for the hint in |merge_into|.
235    pub fn key_for_merge_into(&self) -> Self {
236        if let Self {
237            object_id,
238            data: ObjectKeyData::Attribute(attribute_id, AttributeKey::Extent(e)),
239        } = self
240        {
241            Self::attribute(*object_id, *attribute_id, AttributeKey::Extent(e.key_for_merge_into()))
242        } else {
243            self.clone()
244        }
245    }
246}
247
248impl OrdUpperBound for ObjectKey {
249    fn cmp_upper_bound(&self, other: &ObjectKey) -> std::cmp::Ordering {
250        self.object_id.cmp(&other.object_id).then_with(|| match (&self.data, &other.data) {
251            (
252                ObjectKeyData::Attribute(left_attr_id, AttributeKey::Extent(left_extent)),
253                ObjectKeyData::Attribute(right_attr_id, AttributeKey::Extent(right_extent)),
254            ) => left_attr_id.cmp(right_attr_id).then(left_extent.cmp_upper_bound(right_extent)),
255            _ => self.data.cmp(&other.data),
256        })
257    }
258}
259
260impl OrdLowerBound for ObjectKey {
261    fn cmp_lower_bound(&self, other: &ObjectKey) -> std::cmp::Ordering {
262        self.object_id.cmp(&other.object_id).then_with(|| match (&self.data, &other.data) {
263            (
264                ObjectKeyData::Attribute(left_attr_id, AttributeKey::Extent(left_extent)),
265                ObjectKeyData::Attribute(right_attr_id, AttributeKey::Extent(right_extent)),
266            ) => left_attr_id.cmp(right_attr_id).then(left_extent.cmp_lower_bound(right_extent)),
267            _ => self.data.cmp(&other.data),
268        })
269    }
270}
271
272impl LayerKey for ObjectKey {
273    fn merge_type(&self) -> MergeType {
274        // This listing is intentionally exhaustive to force folks to think about how certain
275        // subsets of the keyspace are merged.
276        match self.data {
277            ObjectKeyData::Object
278            | ObjectKeyData::Keys
279            | ObjectKeyData::Attribute(..)
280            | ObjectKeyData::Child { .. }
281            | ObjectKeyData::EncryptedChild { .. }
282            | ObjectKeyData::CasefoldChild { .. }
283            | ObjectKeyData::GraveyardEntry { .. }
284            | ObjectKeyData::GraveyardAttributeEntry { .. }
285            | ObjectKeyData::Project { property: ProjectProperty::Limit, .. }
286            | ObjectKeyData::ExtendedAttribute { .. } => MergeType::OptimizedMerge,
287            ObjectKeyData::Project { property: ProjectProperty::Usage, .. } => MergeType::FullMerge,
288        }
289    }
290
291    fn next_key(&self) -> Option<Self> {
292        match self.data {
293            ObjectKeyData::Attribute(_, AttributeKey::Extent(_)) => {
294                let mut key = self.clone();
295                if let ObjectKey {
296                    data: ObjectKeyData::Attribute(_, AttributeKey::Extent(ExtentKey { range })),
297                    ..
298                } = &mut key
299                {
300                    // We want a key such that cmp_lower_bound returns Greater for any key which
301                    // starts after end, and a key such that if you search for it, you'll get an
302                    // extent whose end > range.end.
303                    *range = range.end..range.end + 1;
304                }
305                Some(key)
306            }
307            _ => None,
308        }
309    }
310
311    fn search_key(&self) -> Self {
312        if let Self {
313            object_id,
314            data: ObjectKeyData::Attribute(attribute_id, AttributeKey::Extent(e)),
315        } = self
316        {
317            Self::attribute(*object_id, *attribute_id, AttributeKey::Extent(e.search_key()))
318        } else {
319            self.clone()
320        }
321    }
322}
323
324impl RangeKey for ObjectKey {
325    fn overlaps(&self, other: &Self) -> bool {
326        if self.object_id != other.object_id {
327            return false;
328        }
329        match (&self.data, &other.data) {
330            (
331                ObjectKeyData::Attribute(left_attr_id, AttributeKey::Extent(left_key)),
332                ObjectKeyData::Attribute(right_attr_id, AttributeKey::Extent(right_key)),
333            ) if *left_attr_id == *right_attr_id => {
334                left_key.range.end > right_key.range.start
335                    && left_key.range.start < right_key.range.end
336            }
337            (a, b) => a == b,
338        }
339    }
340}
341
342pub enum ObjectKeyFuzzyHashIterator {
343    ExtentKey(/* object_id */ u64, /* attribute_id */ u64, ExtentKeyPartitionIterator),
344    NotExtentKey(/* hash */ Option<u64>),
345}
346
347impl Iterator for ObjectKeyFuzzyHashIterator {
348    type Item = u64;
349
350    fn next(&mut self) -> Option<Self::Item> {
351        match self {
352            Self::ExtentKey(oid, attr_id, extent_keys) => extent_keys.next().map(|range| {
353                let key = ObjectKey::extent(*oid, *attr_id, range);
354                crate::stable_hash::stable_hash(key)
355            }),
356            Self::NotExtentKey(hash) => hash.take(),
357        }
358    }
359}
360
361impl FuzzyHash for ObjectKey {
362    fn fuzzy_hash(&self) -> impl Iterator<Item = u64> {
363        match &self.data {
364            ObjectKeyData::Attribute(attr_id, AttributeKey::Extent(extent)) => {
365                ObjectKeyFuzzyHashIterator::ExtentKey(
366                    self.object_id,
367                    *attr_id,
368                    extent.fuzzy_hash_partition(),
369                )
370            }
371            _ => {
372                let hash = crate::stable_hash::stable_hash(self);
373                ObjectKeyFuzzyHashIterator::NotExtentKey(Some(hash))
374            }
375        }
376    }
377
378    fn is_range_key(&self) -> bool {
379        match &self.data {
380            ObjectKeyData::Attribute(_, AttributeKey::Extent(_)) => true,
381            _ => false,
382        }
383    }
384}
385
386/// UNIX epoch based timestamp in the UTC timezone.
387pub type Timestamp = TimestampV49;
388
389#[derive(
390    Copy,
391    Clone,
392    Debug,
393    Default,
394    Eq,
395    PartialEq,
396    Ord,
397    PartialOrd,
398    Serialize,
399    Deserialize,
400    TypeFingerprint,
401)]
402#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
403pub struct TimestampV49 {
404    nanos: u64,
405}
406
407impl Timestamp {
408    const NSEC_PER_SEC: u64 = 1_000_000_000;
409
410    pub fn now() -> Self {
411        SystemTime::now().duration_since(UNIX_EPOCH).unwrap_or(Duration::ZERO).into()
412    }
413
414    pub const fn zero() -> Self {
415        Self { nanos: 0 }
416    }
417
418    pub const fn from_nanos(nanos: u64) -> Self {
419        Self { nanos }
420    }
421
422    pub fn from_secs_and_nanos(secs: u64, nanos: u32) -> Self {
423        let Some(secs_in_nanos) = secs.checked_mul(Self::NSEC_PER_SEC) else {
424            error!("Fxfs doesn't support dates past 2554-07-21");
425            return Self { nanos: u64::MAX };
426        };
427        let Some(nanos) = secs_in_nanos.checked_add(nanos as u64) else {
428            error!("Fxfs doesn't support dates past 2554-07-21");
429            return Self { nanos: u64::MAX };
430        };
431        Self { nanos }
432    }
433
434    /// Returns the total number of nanoseconds represented by this `Timestamp` since the Unix
435    /// epoch.
436    pub fn as_nanos(&self) -> u64 {
437        self.nanos
438    }
439
440    /// Returns the fractional nanoseconds represented by this `Timestamp`.
441    pub fn subsec_nanos(&self) -> u32 {
442        (self.nanos % Self::NSEC_PER_SEC) as u32
443    }
444
445    /// Returns the total number of whole seconds represented by this `Timestamp` since the Unix
446    /// epoch.
447    pub fn as_secs(&self) -> u64 {
448        self.nanos / Self::NSEC_PER_SEC
449    }
450}
451
452impl From<std::time::Duration> for Timestamp {
453    fn from(duration: std::time::Duration) -> Self {
454        Self::from_secs_and_nanos(duration.as_secs(), duration.subsec_nanos())
455    }
456}
457
458impl From<Timestamp> for std::time::Duration {
459    fn from(timestamp: Timestamp) -> std::time::Duration {
460        Duration::from_nanos(timestamp.nanos)
461    }
462}
463
464pub type ObjectKind = ObjectKindV49;
465
466#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, TypeFingerprint)]
467#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
468pub enum ObjectKindV49 {
469    File {
470        /// The number of references to this file.
471        refs: u64,
472    },
473    Directory {
474        /// The number of sub-directories in this directory.
475        sub_dirs: u64,
476        /// If set, contains the wrapping key id used to encrypt the file contents and filenames in
477        /// this directory.
478        wrapping_key_id: Option<WrappingKeyId>,
479        /// If true, all files and sub-directories created in this directory will support case
480        /// insensitive (but case-preserving) file naming.
481        casefold: bool,
482    },
483    Graveyard,
484    Symlink {
485        /// The number of references to this symbolic link.
486        refs: u64,
487        /// `link` is the target of the link and has no meaning within Fxfs; clients are free to
488        /// interpret it however they like.
489        link: Box<[u8]>,
490    },
491    EncryptedSymlink {
492        /// The number of references to this symbolic link.
493        refs: u64,
494        /// `link` is the target of the link and has no meaning within Fxfs; clients are free to
495        /// interpret it however they like.
496        /// `link` is stored here in encrypted form, encrypted with the symlink's key using the
497        /// same encryption scheme as the one used to encrypt filenames.
498        link: Box<[u8]>,
499    },
500}
501
502/// This consists of POSIX attributes that are not used in Fxfs but it may be meaningful to some
503/// clients to have the ability to to set and retrieve these values.
504pub type PosixAttributes = PosixAttributesV32;
505
506#[derive(Clone, Debug, Copy, Default, Serialize, Deserialize, PartialEq, TypeFingerprint)]
507#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
508pub struct PosixAttributesV32 {
509    /// The mode bits associated with this object
510    pub mode: u32,
511    /// User ID of owner
512    pub uid: u32,
513    /// Group ID of owner
514    pub gid: u32,
515    /// Device ID
516    pub rdev: u64,
517}
518
519/// Object-level attributes.  Note that these are not the same as "attributes" in the
520/// ObjectValue::Attribute sense, which refers to an arbitrary data payload associated with an
521/// object.  This naming collision is unfortunate.
522pub type ObjectAttributes = ObjectAttributesV49;
523
524#[derive(Clone, Debug, Default, Serialize, Deserialize, PartialEq, TypeFingerprint)]
525#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
526pub struct ObjectAttributesV49 {
527    /// The timestamp at which the object was created (i.e. crtime).
528    pub creation_time: TimestampV49,
529    /// The timestamp at which the object's data was last modified (i.e. mtime).
530    pub modification_time: TimestampV49,
531    /// The project id to associate this object's resource usage with. Zero means none.
532    pub project_id: u64,
533    /// Mode, uid, gid, and rdev
534    pub posix_attributes: Option<PosixAttributesV32>,
535    /// The number of bytes allocated to all extents across all attributes for this object.
536    pub allocated_size: u64,
537    /// The timestamp at which the object was last read (i.e. atime).
538    pub access_time: TimestampV49,
539    /// The timestamp at which the object's status was last modified (i.e. ctime).
540    pub change_time: TimestampV49,
541}
542
543pub type ExtendedAttributeValue = ExtendedAttributeValueV32;
544
545#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, TypeFingerprint)]
546#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
547pub enum ExtendedAttributeValueV32 {
548    /// The extended attribute value is stored directly in this object. If the value is above a
549    /// certain size, it should be stored as an attribute with extents instead.
550    Inline(Vec<u8>),
551    /// The extended attribute value is stored as an attribute with extents. The attribute id
552    /// should be chosen to be within the range of 64-512.
553    AttributeId(u64),
554}
555
556/// Id and descriptor for a child entry.
557pub type ChildValue = ChildValueV32;
558
559#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, TypeFingerprint)]
560#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
561pub struct ChildValueV32 {
562    /// The ID of the child object.
563    pub object_id: u64,
564    /// Describes the type of the child.
565    pub object_descriptor: ObjectDescriptorV32,
566}
567
568pub type RootDigest = RootDigestV33;
569
570#[derive(
571    Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd, Serialize, Deserialize, TypeFingerprint,
572)]
573#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
574pub enum RootDigestV33 {
575    Sha256([u8; 32]),
576    Sha512(Vec<u8>),
577}
578
579pub type FsverityMetadata = FsverityMetadataV50;
580
581#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, TypeFingerprint, Versioned)]
582#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
583pub enum FsverityMetadataV50 {
584    /// The root hash and salt.
585    Internal(RootDigestV33, Vec<u8>),
586    /// The root hash and salt are in a descriptor inside the merkle attribute.
587    F2fs(std::ops::Range<u64>),
588}
589
590pub type EncryptionKey = EncryptionKeyV49;
591pub type EncryptionKeyV49 = fxfs_crypto::EncryptionKey;
592
593pub type EncryptionKeys = EncryptionKeysV49;
594
595#[derive(Clone, Default, Debug, PartialEq, Serialize, Deserialize, TypeFingerprint)]
596#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
597pub struct EncryptionKeysV49(Vec<(u64, EncryptionKeyV49)>);
598
599impl EncryptionKeys {
600    pub fn get(&self, id: u64) -> Option<&EncryptionKey> {
601        self.0.iter().find_map(|(i, key)| (*i == id).then_some(key))
602    }
603
604    pub fn insert(&mut self, id: u64, key: EncryptionKey) {
605        self.0.push((id, key))
606    }
607
608    pub fn remove(&mut self, id: u64) -> Option<EncryptionKey> {
609        if let Some(ix) = self.0.iter().position(|(k, _)| *k == id) {
610            Some(self.0.remove(ix).1)
611        } else {
612            None
613        }
614    }
615}
616
617impl From<EncryptionKeys> for BTreeMap<u64, WrappedKey> {
618    fn from(keys: EncryptionKeys) -> Self {
619        keys.0.into_iter().map(|(id, key)| (id, key.into())).collect()
620    }
621}
622
623impl From<Vec<(u64, EncryptionKey)>> for EncryptionKeys {
624    fn from(value: Vec<(u64, EncryptionKey)>) -> Self {
625        Self(value)
626    }
627}
628
629impl std::ops::Deref for EncryptionKeys {
630    type Target = Vec<(u64, EncryptionKey)>;
631    fn deref(&self) -> &Self::Target {
632        &self.0
633    }
634}
635
636/// ObjectValue is the value of an item in the object store.
637/// Note that the tree stores deltas on objects, so these values describe deltas. Unless specified
638/// otherwise, a value indicates an insert/replace mutation.
639pub type ObjectValue = ObjectValueV50;
640impl Value for ObjectValue {
641    const DELETED_MARKER: Self = Self::None;
642}
643
644#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, TypeFingerprint, Versioned)]
645#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
646pub enum ObjectValueV50 {
647    /// Some keys have no value (this often indicates a tombstone of some sort).  Records with this
648    /// value are always filtered when a major compaction is performed, so the meaning must be the
649    /// same as if the item was not present.
650    None,
651    /// Some keys have no value but need to differentiate between a present value and no value
652    /// (None) i.e. their value is really a boolean: None => false, Some => true.
653    Some,
654    /// The value for an ObjectKey::Object record.
655    Object { kind: ObjectKindV49, attributes: ObjectAttributesV49 },
656    /// Specifies encryption keys to use for an object.
657    Keys(EncryptionKeysV49),
658    /// An attribute associated with a file object. |size| is the size of the attribute in bytes.
659    Attribute { size: u64, has_overwrite_extents: bool },
660    /// An extent associated with an object.
661    Extent(ExtentValueV38),
662    /// A child of an object.
663    Child(ChildValueV32),
664    /// Graveyard entries can contain these entries which will cause a file that has extents beyond
665    /// EOF to be trimmed at mount time.  This is used in cases where shrinking a file can exceed
666    /// the bounds of a single transaction.
667    Trim,
668    /// Added to support tracking Project ID usage and limits.
669    BytesAndNodes { bytes: i64, nodes: i64 },
670    /// A value for an extended attribute. Either inline or a redirection to an attribute with
671    /// extents.
672    ExtendedAttribute(ExtendedAttributeValueV32),
673    /// An attribute associated with a verified file object. |size| is the size of the attribute
674    /// in bytes.
675    VerifiedAttribute { size: u64, fsverity_metadata: FsverityMetadataV50 },
676}
677
678impl ObjectValue {
679    /// Creates an ObjectValue for a file object.
680    pub fn file(
681        refs: u64,
682        allocated_size: u64,
683        creation_time: Timestamp,
684        modification_time: Timestamp,
685        access_time: Timestamp,
686        change_time: Timestamp,
687        project_id: u64,
688        posix_attributes: Option<PosixAttributes>,
689    ) -> ObjectValue {
690        ObjectValue::Object {
691            kind: ObjectKind::File { refs },
692            attributes: ObjectAttributes {
693                creation_time,
694                modification_time,
695                project_id,
696                posix_attributes,
697                allocated_size,
698                access_time,
699                change_time,
700            },
701        }
702    }
703    pub fn keys(encryption_keys: EncryptionKeys) -> ObjectValue {
704        ObjectValue::Keys(encryption_keys)
705    }
706    /// Creates an ObjectValue for an object attribute.
707    pub fn attribute(size: u64, has_overwrite_extents: bool) -> ObjectValue {
708        ObjectValue::Attribute { size, has_overwrite_extents }
709    }
710    /// Creates an ObjectValue for an object attribute of a verified file.
711    pub fn verified_attribute(size: u64, fsverity_metadata: FsverityMetadata) -> ObjectValue {
712        ObjectValue::VerifiedAttribute { size, fsverity_metadata }
713    }
714    /// Creates an ObjectValue for an insertion/replacement of an object extent.
715    pub fn extent(device_offset: u64, key_id: u64) -> ObjectValue {
716        ObjectValue::Extent(ExtentValue::new_raw(device_offset, key_id))
717    }
718    /// Creates an ObjectValue for an insertion/replacement of an object extent.
719    pub fn extent_with_checksum(
720        device_offset: u64,
721        checksum: Checksums,
722        key_id: u64,
723    ) -> ObjectValue {
724        ObjectValue::Extent(ExtentValue::with_checksum(device_offset, checksum, key_id))
725    }
726    /// Creates an ObjectValue for a deletion of an object extent.
727    pub fn deleted_extent() -> ObjectValue {
728        ObjectValue::Extent(ExtentValue::deleted_extent())
729    }
730    /// Creates an ObjectValue for an object child.
731    pub fn child(object_id: u64, object_descriptor: ObjectDescriptor) -> ObjectValue {
732        ObjectValue::Child(ChildValue { object_id, object_descriptor })
733    }
734    /// Creates an ObjectValue for an object symlink.
735    pub fn symlink(
736        link: impl Into<Box<[u8]>>,
737        creation_time: Timestamp,
738        modification_time: Timestamp,
739        project_id: u64,
740    ) -> ObjectValue {
741        ObjectValue::Object {
742            kind: ObjectKind::Symlink { refs: 1, link: link.into() },
743            attributes: ObjectAttributes {
744                creation_time,
745                modification_time,
746                project_id,
747                ..Default::default()
748            },
749        }
750    }
751    /// Creates an ObjectValue for an encrypted symlink object.
752    pub fn encrypted_symlink(
753        link: impl Into<Box<[u8]>>,
754        creation_time: Timestamp,
755        modification_time: Timestamp,
756        project_id: u64,
757    ) -> ObjectValue {
758        ObjectValue::Object {
759            kind: ObjectKind::EncryptedSymlink { refs: 1, link: link.into() },
760            attributes: ObjectAttributes {
761                creation_time,
762                modification_time,
763                project_id,
764                ..Default::default()
765            },
766        }
767    }
768    pub fn inline_extended_attribute(value: impl Into<Vec<u8>>) -> ObjectValue {
769        ObjectValue::ExtendedAttribute(ExtendedAttributeValue::Inline(value.into()))
770    }
771    pub fn extended_attribute(attribute_id: u64) -> ObjectValue {
772        ObjectValue::ExtendedAttribute(ExtendedAttributeValue::AttributeId(attribute_id))
773    }
774}
775
776pub type ObjectItem = ObjectItemV50;
777pub type ObjectItemV50 = Item<ObjectKeyV43, ObjectValueV50>;
778
779impl ObjectItem {
780    pub fn is_tombstone(&self) -> bool {
781        matches!(
782            self,
783            Item {
784                key: ObjectKey { data: ObjectKeyData::Object, .. },
785                value: ObjectValue::None,
786                ..
787            }
788        )
789    }
790}
791
792// If the given item describes an extent, unwraps it and returns the extent key/value.
793impl<'a> From<ItemRef<'a, ObjectKey, ObjectValue>>
794    for Option<(/*object-id*/ u64, /*attribute-id*/ u64, &'a ExtentKey, &'a ExtentValue)>
795{
796    fn from(item: ItemRef<'a, ObjectKey, ObjectValue>) -> Self {
797        match item {
798            ItemRef {
799                key:
800                    ObjectKey {
801                        object_id,
802                        data:
803                            ObjectKeyData::Attribute(
804                                attribute_id, //
805                                AttributeKey::Extent(extent_key),
806                            ),
807                    },
808                value: ObjectValue::Extent(extent_value),
809                ..
810            } => Some((*object_id, *attribute_id, extent_key, extent_value)),
811            _ => None,
812        }
813    }
814}
815
816pub type FxfsKey = FxfsKeyV49;
817pub type FxfsKeyV49 = fxfs_crypto::FxfsKey;
818
819#[cfg(test)]
820mod tests {
821    use super::{ObjectKey, ObjectKeyV43, TimestampV49};
822    use crate::lsm_tree::types::{
823        FuzzyHash as _, LayerKey, OrdLowerBound, OrdUpperBound, RangeKey,
824    };
825    use std::cmp::Ordering;
826    use std::ops::Add;
827    use std::time::{Duration, SystemTime, UNIX_EPOCH};
828
829    // Smoke test to ensure hash stability for Fxfs objects.
830    // If this test fails, the hash algorithm changed, and that won't do -- Fxfs relies on stable
831    // hash values, and existing images will appear to be corrupt if they change (see
832    // https://fxbug.dev/419133532).
833    #[test]
834    fn test_hash_stability() {
835        // Target a specific version of ObjectKey.  If you want to delete ObjectKeyV43, simply
836        // update this test with a later key version, which will also require re-generating the
837        // hashes.
838        assert_eq!(
839            &ObjectKeyV43::object(100).fuzzy_hash().collect::<Vec<_>>()[..],
840            &[11885326717398844384]
841        );
842        assert_eq!(
843            &ObjectKeyV43::extent(1, 0, 0..2 * 1024 * 1024).fuzzy_hash().collect::<Vec<_>>()[..],
844            &[11090579907097549012, 2814892992701560424]
845        );
846    }
847
848    #[test]
849    fn test_next_key() {
850        let next_key = ObjectKey::extent(1, 0, 0..100).next_key().unwrap();
851        assert_eq!(ObjectKey::extent(1, 0, 101..200).cmp_lower_bound(&next_key), Ordering::Greater);
852        assert_eq!(ObjectKey::extent(1, 0, 100..200).cmp_lower_bound(&next_key), Ordering::Equal);
853        assert_eq!(ObjectKey::extent(1, 0, 100..101).cmp_lower_bound(&next_key), Ordering::Equal);
854        assert_eq!(ObjectKey::extent(1, 0, 99..100).cmp_lower_bound(&next_key), Ordering::Less);
855        assert_eq!(ObjectKey::extent(1, 0, 0..100).cmp_upper_bound(&next_key), Ordering::Less);
856        assert_eq!(ObjectKey::extent(1, 0, 99..100).cmp_upper_bound(&next_key), Ordering::Less);
857        assert_eq!(ObjectKey::extent(1, 0, 100..101).cmp_upper_bound(&next_key), Ordering::Equal);
858        assert_eq!(ObjectKey::extent(1, 0, 100..200).cmp_upper_bound(&next_key), Ordering::Greater);
859        assert_eq!(ObjectKey::extent(1, 0, 50..101).cmp_upper_bound(&next_key), Ordering::Equal);
860        assert_eq!(ObjectKey::extent(1, 0, 50..200).cmp_upper_bound(&next_key), Ordering::Greater);
861    }
862    #[test]
863    fn test_range_key() {
864        // Make sure we disallow using extent keys with point queries. Other object keys should
865        // still be allowed with point queries.
866        assert!(ObjectKeyV43::extent(1, 0, 0..2 * 1024 * 1024).is_range_key());
867        assert!(!ObjectKeyV43::object(100).is_range_key());
868
869        assert_eq!(ObjectKey::object(1).overlaps(&ObjectKey::object(1)), true);
870        assert_eq!(ObjectKey::object(1).overlaps(&ObjectKey::object(2)), false);
871        assert_eq!(ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::object(1)), false);
872        assert_eq!(ObjectKey::object(1).overlaps(&ObjectKey::extent(1, 0, 0..100)), false);
873        assert_eq!(
874            ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::extent(2, 0, 0..100)),
875            false
876        );
877        assert_eq!(
878            ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::extent(1, 1, 0..100)),
879            false
880        );
881        assert_eq!(
882            ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::extent(1, 0, 0..100)),
883            true
884        );
885
886        assert_eq!(
887            ObjectKey::extent(1, 0, 0..50).overlaps(&ObjectKey::extent(1, 0, 49..100)),
888            true
889        );
890        assert_eq!(
891            ObjectKey::extent(1, 0, 49..100).overlaps(&ObjectKey::extent(1, 0, 0..50)),
892            true
893        );
894
895        assert_eq!(
896            ObjectKey::extent(1, 0, 0..50).overlaps(&ObjectKey::extent(1, 0, 50..100)),
897            false
898        );
899        assert_eq!(
900            ObjectKey::extent(1, 0, 50..100).overlaps(&ObjectKey::extent(1, 0, 0..50)),
901            false
902        );
903    }
904
905    #[test]
906    fn test_timestamp() {
907        fn compare_time(std_time: Duration) {
908            let ts_time: TimestampV49 = std_time.into();
909            assert_eq!(<TimestampV49 as Into<Duration>>::into(ts_time), std_time);
910            assert_eq!(ts_time.subsec_nanos(), std_time.subsec_nanos());
911            assert_eq!(ts_time.as_secs(), std_time.as_secs());
912            assert_eq!(ts_time.as_nanos() as u128, std_time.as_nanos());
913        }
914        compare_time(Duration::from_nanos(0));
915        compare_time(Duration::from_nanos(u64::MAX));
916        compare_time(SystemTime::now().duration_since(UNIX_EPOCH).unwrap());
917
918        let ts: TimestampV49 = Duration::from_secs(u64::MAX - 1).into();
919        assert_eq!(ts.nanos, u64::MAX);
920
921        let ts: TimestampV49 = (Duration::from_nanos(u64::MAX).add(Duration::from_nanos(1))).into();
922        assert_eq!(ts.nanos, u64::MAX);
923    }
924}
fxfs/object_store/object_record.rs

fxfs/object_store/
object_record.rs
