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

fxfs/object_store/
object_record.rs
