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 = FsverityMetadataV33;
580
581#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, TypeFingerprint, Versioned)]
582#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
583pub struct FsverityMetadataV33 {
584    pub root_digest: RootDigestV33,
585    pub salt: Vec<u8>,
586}
587
588pub type EncryptionKey = EncryptionKeyV49;
589pub type EncryptionKeyV49 = fxfs_crypto::EncryptionKey;
590
591pub type EncryptionKeys = EncryptionKeysV49;
592
593#[derive(Clone, Default, Debug, PartialEq, Serialize, Deserialize, TypeFingerprint)]
594#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
595pub struct EncryptionKeysV49(Vec<(u64, EncryptionKeyV49)>);
596
597impl EncryptionKeys {
598    pub fn get(&self, id: u64) -> Option<&EncryptionKey> {
599        self.0.iter().find_map(|(i, key)| (*i == id).then_some(key))
600    }
601
602    pub fn insert(&mut self, id: u64, key: EncryptionKey) {
603        self.0.push((id, key))
604    }
605
606    pub fn remove(&mut self, id: u64) -> Option<EncryptionKey> {
607        if let Some(ix) = self.0.iter().position(|(k, _)| *k == id) {
608            Some(self.0.remove(ix).1)
609        } else {
610            None
611        }
612    }
613}
614
615impl From<EncryptionKeys> for BTreeMap<u64, WrappedKey> {
616    fn from(keys: EncryptionKeys) -> Self {
617        keys.0.into_iter().map(|(id, key)| (id, key.into())).collect()
618    }
619}
620
621impl From<Vec<(u64, EncryptionKey)>> for EncryptionKeys {
622    fn from(value: Vec<(u64, EncryptionKey)>) -> Self {
623        Self(value)
624    }
625}
626
627impl std::ops::Deref for EncryptionKeys {
628    type Target = Vec<(u64, EncryptionKey)>;
629    fn deref(&self) -> &Self::Target {
630        &self.0
631    }
632}
633
634/// ObjectValue is the value of an item in the object store.
635/// Note that the tree stores deltas on objects, so these values describe deltas. Unless specified
636/// otherwise, a value indicates an insert/replace mutation.
637pub type ObjectValue = ObjectValueV49;
638impl Value for ObjectValue {
639    const DELETED_MARKER: Self = Self::None;
640}
641
642#[derive(Clone, Debug, Serialize, Deserialize, PartialEq, TypeFingerprint, Versioned)]
643#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
644pub enum ObjectValueV49 {
645    /// Some keys have no value (this often indicates a tombstone of some sort).  Records with this
646    /// value are always filtered when a major compaction is performed, so the meaning must be the
647    /// same as if the item was not present.
648    None,
649    /// Some keys have no value but need to differentiate between a present value and no value
650    /// (None) i.e. their value is really a boolean: None => false, Some => true.
651    Some,
652    /// The value for an ObjectKey::Object record.
653    Object { kind: ObjectKindV49, attributes: ObjectAttributesV49 },
654    /// Specifies encryption keys to use for an object.
655    Keys(EncryptionKeysV49),
656    /// An attribute associated with a file object. |size| is the size of the attribute in bytes.
657    Attribute { size: u64, has_overwrite_extents: bool },
658    /// An extent associated with an object.
659    Extent(ExtentValueV38),
660    /// A child of an object.
661    Child(ChildValueV32),
662    /// Graveyard entries can contain these entries which will cause a file that has extents beyond
663    /// EOF to be trimmed at mount time.  This is used in cases where shrinking a file can exceed
664    /// the bounds of a single transaction.
665    Trim,
666    /// Added to support tracking Project ID usage and limits.
667    BytesAndNodes { bytes: i64, nodes: i64 },
668    /// A value for an extended attribute. Either inline or a redirection to an attribute with
669    /// extents.
670    ExtendedAttribute(ExtendedAttributeValueV32),
671    /// An attribute associated with a verified file object. |size| is the size of the attribute
672    /// in bytes. |fsverity_metadata| holds the descriptor for the fsverity-enabled file.
673    VerifiedAttribute { size: u64, fsverity_metadata: FsverityMetadataV33 },
674}
675
676impl ObjectValue {
677    /// Creates an ObjectValue for a file object.
678    pub fn file(
679        refs: u64,
680        allocated_size: u64,
681        creation_time: Timestamp,
682        modification_time: Timestamp,
683        access_time: Timestamp,
684        change_time: Timestamp,
685        project_id: u64,
686        posix_attributes: Option<PosixAttributes>,
687    ) -> ObjectValue {
688        ObjectValue::Object {
689            kind: ObjectKind::File { refs },
690            attributes: ObjectAttributes {
691                creation_time,
692                modification_time,
693                project_id,
694                posix_attributes,
695                allocated_size,
696                access_time,
697                change_time,
698            },
699        }
700    }
701    pub fn keys(encryption_keys: EncryptionKeys) -> ObjectValue {
702        ObjectValue::Keys(encryption_keys)
703    }
704    /// Creates an ObjectValue for an object attribute.
705    pub fn attribute(size: u64, has_overwrite_extents: bool) -> ObjectValue {
706        ObjectValue::Attribute { size, has_overwrite_extents }
707    }
708    /// Creates an ObjectValue for an object attribute of a verified file.
709    pub fn verified_attribute(size: u64, fsverity_metadata: FsverityMetadata) -> ObjectValue {
710        ObjectValue::VerifiedAttribute { size, fsverity_metadata }
711    }
712    /// Creates an ObjectValue for an insertion/replacement of an object extent.
713    pub fn extent(device_offset: u64, key_id: u64) -> ObjectValue {
714        ObjectValue::Extent(ExtentValue::new_raw(device_offset, key_id))
715    }
716    /// Creates an ObjectValue for an insertion/replacement of an object extent.
717    pub fn extent_with_checksum(
718        device_offset: u64,
719        checksum: Checksums,
720        key_id: u64,
721    ) -> ObjectValue {
722        ObjectValue::Extent(ExtentValue::with_checksum(device_offset, checksum, key_id))
723    }
724    /// Creates an ObjectValue for a deletion of an object extent.
725    pub fn deleted_extent() -> ObjectValue {
726        ObjectValue::Extent(ExtentValue::deleted_extent())
727    }
728    /// Creates an ObjectValue for an object child.
729    pub fn child(object_id: u64, object_descriptor: ObjectDescriptor) -> ObjectValue {
730        ObjectValue::Child(ChildValue { object_id, object_descriptor })
731    }
732    /// Creates an ObjectValue for an object symlink.
733    pub fn symlink(
734        link: impl Into<Box<[u8]>>,
735        creation_time: Timestamp,
736        modification_time: Timestamp,
737        project_id: u64,
738    ) -> ObjectValue {
739        ObjectValue::Object {
740            kind: ObjectKind::Symlink { refs: 1, link: link.into() },
741            attributes: ObjectAttributes {
742                creation_time,
743                modification_time,
744                project_id,
745                ..Default::default()
746            },
747        }
748    }
749    /// Creates an ObjectValue for an encrypted symlink object.
750    pub fn encrypted_symlink(
751        link: impl Into<Box<[u8]>>,
752        creation_time: Timestamp,
753        modification_time: Timestamp,
754        project_id: u64,
755    ) -> ObjectValue {
756        ObjectValue::Object {
757            kind: ObjectKind::EncryptedSymlink { refs: 1, link: link.into() },
758            attributes: ObjectAttributes {
759                creation_time,
760                modification_time,
761                project_id,
762                ..Default::default()
763            },
764        }
765    }
766    pub fn inline_extended_attribute(value: impl Into<Vec<u8>>) -> ObjectValue {
767        ObjectValue::ExtendedAttribute(ExtendedAttributeValue::Inline(value.into()))
768    }
769    pub fn extended_attribute(attribute_id: u64) -> ObjectValue {
770        ObjectValue::ExtendedAttribute(ExtendedAttributeValue::AttributeId(attribute_id))
771    }
772}
773
774pub type ObjectItem = ObjectItemV49;
775pub type ObjectItemV49 = Item<ObjectKeyV43, ObjectValueV49>;
776
777impl ObjectItem {
778    pub fn is_tombstone(&self) -> bool {
779        matches!(
780            self,
781            Item {
782                key: ObjectKey { data: ObjectKeyData::Object, .. },
783                value: ObjectValue::None,
784                ..
785            }
786        )
787    }
788}
789
790// If the given item describes an extent, unwraps it and returns the extent key/value.
791impl<'a> From<ItemRef<'a, ObjectKey, ObjectValue>>
792    for Option<(/*object-id*/ u64, /*attribute-id*/ u64, &'a ExtentKey, &'a ExtentValue)>
793{
794    fn from(item: ItemRef<'a, ObjectKey, ObjectValue>) -> Self {
795        match item {
796            ItemRef {
797                key:
798                    ObjectKey {
799                        object_id,
800                        data:
801                            ObjectKeyData::Attribute(
802                                attribute_id, //
803                                AttributeKey::Extent(extent_key),
804                            ),
805                    },
806                value: ObjectValue::Extent(extent_value),
807                ..
808            } => Some((*object_id, *attribute_id, extent_key, extent_value)),
809            _ => None,
810        }
811    }
812}
813
814pub type FxfsKey = FxfsKeyV49;
815pub type FxfsKeyV49 = fxfs_crypto::FxfsKey;
816
817#[cfg(test)]
818mod tests {
819    use super::{ObjectKey, ObjectKeyV43, TimestampV49};
820    use crate::lsm_tree::types::{
821        FuzzyHash as _, LayerKey, OrdLowerBound, OrdUpperBound, RangeKey,
822    };
823    use std::cmp::Ordering;
824    use std::ops::Add;
825    use std::time::{Duration, SystemTime, UNIX_EPOCH};
826
827    // Smoke test to ensure hash stability for Fxfs objects.
828    // If this test fails, the hash algorithm changed, and that won't do -- Fxfs relies on stable
829    // hash values, and existing images will appear to be corrupt if they change (see
830    // https://fxbug.dev/419133532).
831    #[test]
832    fn test_hash_stability() {
833        // Target a specific version of ObjectKey.  If you want to delete ObjectKeyV43, simply
834        // update this test with a later key version, which will also require re-generating the
835        // hashes.
836        assert_eq!(
837            &ObjectKeyV43::object(100).fuzzy_hash().collect::<Vec<_>>()[..],
838            &[11885326717398844384]
839        );
840        assert_eq!(
841            &ObjectKeyV43::extent(1, 0, 0..2 * 1024 * 1024).fuzzy_hash().collect::<Vec<_>>()[..],
842            &[11090579907097549012, 2814892992701560424]
843        );
844    }
845
846    #[test]
847    fn test_next_key() {
848        let next_key = ObjectKey::extent(1, 0, 0..100).next_key().unwrap();
849        assert_eq!(ObjectKey::extent(1, 0, 101..200).cmp_lower_bound(&next_key), Ordering::Greater);
850        assert_eq!(ObjectKey::extent(1, 0, 100..200).cmp_lower_bound(&next_key), Ordering::Equal);
851        assert_eq!(ObjectKey::extent(1, 0, 100..101).cmp_lower_bound(&next_key), Ordering::Equal);
852        assert_eq!(ObjectKey::extent(1, 0, 99..100).cmp_lower_bound(&next_key), Ordering::Less);
853        assert_eq!(ObjectKey::extent(1, 0, 0..100).cmp_upper_bound(&next_key), Ordering::Less);
854        assert_eq!(ObjectKey::extent(1, 0, 99..100).cmp_upper_bound(&next_key), Ordering::Less);
855        assert_eq!(ObjectKey::extent(1, 0, 100..101).cmp_upper_bound(&next_key), Ordering::Equal);
856        assert_eq!(ObjectKey::extent(1, 0, 100..200).cmp_upper_bound(&next_key), Ordering::Greater);
857        assert_eq!(ObjectKey::extent(1, 0, 50..101).cmp_upper_bound(&next_key), Ordering::Equal);
858        assert_eq!(ObjectKey::extent(1, 0, 50..200).cmp_upper_bound(&next_key), Ordering::Greater);
859    }
860    #[test]
861    fn test_range_key() {
862        // Make sure we disallow using extent keys with point queries. Other object keys should
863        // still be allowed with point queries.
864        assert!(ObjectKeyV43::extent(1, 0, 0..2 * 1024 * 1024).is_range_key());
865        assert!(!ObjectKeyV43::object(100).is_range_key());
866
867        assert_eq!(ObjectKey::object(1).overlaps(&ObjectKey::object(1)), true);
868        assert_eq!(ObjectKey::object(1).overlaps(&ObjectKey::object(2)), false);
869        assert_eq!(ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::object(1)), false);
870        assert_eq!(ObjectKey::object(1).overlaps(&ObjectKey::extent(1, 0, 0..100)), false);
871        assert_eq!(
872            ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::extent(2, 0, 0..100)),
873            false
874        );
875        assert_eq!(
876            ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::extent(1, 1, 0..100)),
877            false
878        );
879        assert_eq!(
880            ObjectKey::extent(1, 0, 0..100).overlaps(&ObjectKey::extent(1, 0, 0..100)),
881            true
882        );
883
884        assert_eq!(
885            ObjectKey::extent(1, 0, 0..50).overlaps(&ObjectKey::extent(1, 0, 49..100)),
886            true
887        );
888        assert_eq!(
889            ObjectKey::extent(1, 0, 49..100).overlaps(&ObjectKey::extent(1, 0, 0..50)),
890            true
891        );
892
893        assert_eq!(
894            ObjectKey::extent(1, 0, 0..50).overlaps(&ObjectKey::extent(1, 0, 50..100)),
895            false
896        );
897        assert_eq!(
898            ObjectKey::extent(1, 0, 50..100).overlaps(&ObjectKey::extent(1, 0, 0..50)),
899            false
900        );
901    }
902
903    #[test]
904    fn test_timestamp() {
905        fn compare_time(std_time: Duration) {
906            let ts_time: TimestampV49 = std_time.into();
907            assert_eq!(<TimestampV49 as Into<Duration>>::into(ts_time), std_time);
908            assert_eq!(ts_time.subsec_nanos(), std_time.subsec_nanos());
909            assert_eq!(ts_time.as_secs(), std_time.as_secs());
910            assert_eq!(ts_time.as_nanos() as u128, std_time.as_nanos());
911        }
912        compare_time(Duration::from_nanos(0));
913        compare_time(Duration::from_nanos(u64::MAX));
914        compare_time(SystemTime::now().duration_since(UNIX_EPOCH).unwrap());
915
916        let ts: TimestampV49 = Duration::from_secs(u64::MAX - 1).into();
917        assert_eq!(ts.nanos, u64::MAX);
918
919        let ts: TimestampV49 = (Duration::from_nanos(u64::MAX).add(Duration::from_nanos(1))).into();
920        assert_eq!(ts.nanos, u64::MAX);
921    }
922}
fxfs/object_store/object_record.rs

fxfs/object_store/
object_record.rs
