fxfs/fsck/
store_scanner.rs

Help
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
5use crate::fsck::errors::{FsckError, FsckFatal, FsckWarning};
6use crate::fsck::{FragmentationStats, Fsck, FsckResult};
7use crate::lsm_tree::types::{Item, ItemRef, LayerIterator};
8use crate::lsm_tree::Query;
9use crate::object_handle::INVALID_OBJECT_ID;
10use crate::object_store::allocator::{self, AllocatorKey, AllocatorValue};
11use crate::object_store::graveyard::Graveyard;
12use crate::object_store::{
13    AttributeKey, ChildValue, EncryptionKeys, ExtendedAttributeValue, ExtentKey, ExtentMode,
14    ExtentValue, ObjectAttributes, ObjectDescriptor, ObjectKey, ObjectKeyData, ObjectKind,
15    ObjectStore, ObjectValue, ProjectProperty, RootDigest, DEFAULT_DATA_ATTRIBUTE_ID,
16    EXTENDED_ATTRIBUTE_RANGE_END, EXTENDED_ATTRIBUTE_RANGE_START, FSVERITY_MERKLE_ATTRIBUTE_ID,
17};
18use crate::range::RangeExt;
19use crate::round::round_up;
20use anyhow::{bail, Error};
21use rustc_hash::FxHashSet as HashSet;
22use std::cell::UnsafeCell;
23use std::collections::btree_map::BTreeMap;
24use std::ops::Range;
25
26// Information about a specific attribute.
27#[derive(Debug)]
28struct ScannedAttribute {
29    // ID of the attribute. Most commonly zero, which is the attribute value regular data is stored
30    // in, but others are used for extended attributes and merkle trees.
31    attribute_id: u64,
32    // The logical size of this attribute according to its metadata.
33    size: u64,
34    // The attribute metadata claims to have at least one extents with an Overwrite or
35    // OverwritePartial ExtentMode. None for attributes that don't care about overwrite extents,
36    // like VerifiedAttribute.
37    has_overwrite_extents_flag: Option<bool>,
38    // An overwrite extent was found for this attribute.
39    observed_overwrite_extents: bool,
40}
41
42// Information for scanned objects about their allocated attributes.
43#[derive(Debug)]
44struct ScannedAttributes {
45    attributes: Vec<ScannedAttribute>,
46    // A list of attributes that have been tombstoned.
47    tombstoned_attributes: Vec<u64>,
48    // The object's allocated size, according to its metadata.
49    stored_allocated_size: u64,
50    // The allocated size of the object (computed by summing up the extents for the file).
51    observed_allocated_size: u64,
52    // The object is in the graveyard which means extents beyond the end of the file are allowed.
53    in_graveyard: bool,
54    // Any extended attributes which point at an fxfs attribute for this object.
55    extended_attributes: Vec<u64>,
56}
57
58#[derive(Debug)]
59struct ScannedFile {
60    // A list of parent object IDs for the file.  INVALID_OBJECT_ID indicates a reference from
61    // outside the object store (either the graveyard, or because the object is a root object of the
62    // store and probably has a reference to it in e.g. the StoreInfo or superblock).
63    parents: Vec<u64>,
64    // The number of references to the file, according to its metadata.
65    stored_refs: u64,
66    // Attributes for this file.
67    attributes: ScannedAttributes,
68    // If fsverity-enabled, contains the hash size.
69    is_verified: Option<usize>,
70}
71
72#[derive(Debug)]
73struct ScannedDir {
74    // The number of sub-directories of the dir, according to its metadata.
75    stored_sub_dirs: u64,
76    // The number of sub-directories we found for the dir.
77    observed_sub_dirs: u64,
78    // The parent object of the directory.  See ScannedFile::parents.  Note that directories can
79    // only have one parent, hence this is just an Option (not a Vec).
80    parent: Option<u64>,
81    // Used to detect directory cycles.
82    visited: UnsafeCell<bool>,
83    // If set, stores the wrapping_key_id that the directory was encrypted with.
84    wrapping_key_id: Option<u128>,
85    // Attributes for this directory.
86    attributes: ScannedAttributes,
87    // True if directory uses casefold
88    casefold: bool,
89}
90
91unsafe impl Sync for ScannedDir {}
92
93#[derive(Debug)]
94struct ScannedSymlink {
95    // A list of parent object IDs for the symlink.
96    parents: Vec<u64>,
97    // The number of references to the file, according to its metadata.
98    stored_refs: u64,
99    // Attributes for this symlink
100    attributes: ScannedAttributes,
101}
102
103#[derive(Debug)]
104enum ScannedObject {
105    Directory(ScannedDir),
106    File(ScannedFile),
107    Graveyard,
108    Symlink(ScannedSymlink),
109    // A tombstoned object, which should have no other records associated with it.
110    Tombstone,
111}
112
113struct ScannedStore<'a> {
114    fsck: &'a Fsck<'a>,
115    objects: BTreeMap<u64, ScannedObject>,
116    root_objects: Vec<u64>,
117    store_id: u64,
118    is_root_store: bool,
119    is_encrypted: bool,
120    current_object: Option<CurrentObject>,
121    root_dir_id: u64,
122    stored_project_usages: BTreeMap<u64, (i64, i64)>,
123    total_project_usages: BTreeMap<u64, (i64, i64)>,
124    /// Tracks project ids used and an example node to examine if it should not have been included.
125    used_project_ids: BTreeMap<u64, u64>,
126}
127
128struct CurrentObject {
129    object_id: u64,
130    key_ids: HashSet<u64>,
131    lazy_keys: bool,
132}
133
134impl<'a> ScannedStore<'a> {
135    fn new(
136        fsck: &'a Fsck<'a>,
137        root_objects: impl AsRef<[u64]>,
138        store_id: u64,
139        is_root_store: bool,
140        is_encrypted: bool,
141        root_dir_id: u64,
142    ) -> Self {
143        Self {
144            fsck,
145            objects: BTreeMap::new(),
146            root_objects: root_objects.as_ref().into(),
147            store_id,
148            is_root_store,
149            is_encrypted,
150            current_object: None,
151            root_dir_id,
152            stored_project_usages: BTreeMap::new(),
153            total_project_usages: BTreeMap::new(),
154            used_project_ids: BTreeMap::new(),
155        }
156    }
157
158    // Process an object store record, adding or updating any objects known to the ScannedStore.
159    fn process(&mut self, key: &ObjectKey, value: &ObjectValue) -> Result<(), Error> {
160        match key.data {
161            ObjectKeyData::Object => {
162                match value {
163                    ObjectValue::None => {
164                        if self.objects.insert(key.object_id, ScannedObject::Tombstone).is_some() {
165                            self.fsck.error(FsckError::TombstonedObjectHasRecords(
166                                self.store_id,
167                                key.object_id,
168                            ))?;
169                        }
170                    }
171                    ObjectValue::Some => {
172                        self.fsck.error(FsckError::UnexpectedRecordInObjectStore(
173                            self.store_id,
174                            key.into(),
175                            value.into(),
176                        ))?;
177                    }
178                    ObjectValue::Object {
179                        kind: ObjectKind::File { refs },
180                        attributes: ObjectAttributes { project_id, allocated_size, .. },
181                    } => {
182                        if *project_id > 0 {
183                            self.used_project_ids.insert(*project_id, key.object_id);
184                            let entry = self.total_project_usages.entry(*project_id).or_default();
185                            entry.0 += i64::try_from(*allocated_size).unwrap();
186                            entry.1 += 1;
187                        }
188                        self.current_object = Some(CurrentObject {
189                            object_id: key.object_id,
190                            key_ids: HashSet::default(),
191                            lazy_keys: false,
192                        });
193                        let parents = if self.root_objects.contains(&key.object_id) {
194                            vec![INVALID_OBJECT_ID]
195                        } else {
196                            vec![]
197                        };
198                        self.objects.insert(
199                            key.object_id,
200                            ScannedObject::File(ScannedFile {
201                                parents,
202                                stored_refs: *refs,
203                                attributes: ScannedAttributes {
204                                    attributes: Vec::new(),
205                                    tombstoned_attributes: Vec::new(),
206                                    stored_allocated_size: *allocated_size,
207                                    observed_allocated_size: 0,
208                                    in_graveyard: false,
209                                    extended_attributes: Vec::new(),
210                                },
211                                is_verified: None,
212                            }),
213                        );
214                    }
215                    ObjectValue::Object {
216                        // TODO: https://fxbug.dev/356897866: Add validation for fscrypt.
217                        kind: ObjectKind::Directory { sub_dirs, casefold, wrapping_key_id },
218                        attributes: ObjectAttributes { project_id, allocated_size, .. },
219                    } => {
220                        if *project_id > 0 {
221                            self.used_project_ids.insert(*project_id, key.object_id);
222                            let entry = self.total_project_usages.entry(*project_id).or_default();
223                            // Increment only nodes.
224                            entry.1 += 1;
225                        }
226                        let parent = if self.root_objects.contains(&key.object_id) {
227                            Some(INVALID_OBJECT_ID)
228                        } else {
229                            None
230                        };
231                        self.current_object = Some(CurrentObject {
232                            object_id: key.object_id,
233                            key_ids: HashSet::default(),
234                            lazy_keys: true,
235                        });
236                        // We've verified no duplicate keys, and Object records come first,
237                        // so this should always be the first time we encounter this object.
238                        self.objects.insert(
239                            key.object_id,
240                            ScannedObject::Directory(ScannedDir {
241                                stored_sub_dirs: *sub_dirs,
242                                observed_sub_dirs: 0,
243                                parent,
244                                visited: UnsafeCell::new(false),
245                                wrapping_key_id: *wrapping_key_id,
246                                attributes: ScannedAttributes {
247                                    attributes: Vec::new(),
248                                    tombstoned_attributes: Vec::new(),
249                                    stored_allocated_size: *allocated_size,
250                                    observed_allocated_size: 0,
251                                    in_graveyard: false,
252                                    extended_attributes: Vec::new(),
253                                },
254                                casefold: *casefold,
255                            }),
256                        );
257                    }
258                    ObjectValue::Object { kind: ObjectKind::Graveyard, attributes } => {
259                        self.objects.insert(key.object_id, ScannedObject::Graveyard);
260                        if attributes.project_id != 0 {
261                            self.fsck.error(FsckError::ProjectOnGraveyard(
262                                self.store_id,
263                                attributes.project_id,
264                                key.object_id,
265                            ))?;
266                        }
267                    }
268                    ObjectValue::Object {
269                        kind: ObjectKind::Symlink { refs, .. },
270                        attributes: ObjectAttributes { project_id, allocated_size, .. },
271                    } => {
272                        if *project_id > 0 {
273                            self.used_project_ids.insert(*project_id, key.object_id);
274                            let entry = self.total_project_usages.entry(*project_id).or_default();
275                            // Increment only nodes.
276                            entry.1 += 1;
277                        }
278                        self.current_object = Some(CurrentObject {
279                            object_id: key.object_id,
280                            key_ids: HashSet::default(),
281                            lazy_keys: true,
282                        });
283                        self.objects.insert(
284                            key.object_id,
285                            ScannedObject::Symlink(ScannedSymlink {
286                                parents: vec![],
287                                stored_refs: *refs,
288                                attributes: ScannedAttributes {
289                                    attributes: Vec::new(),
290                                    tombstoned_attributes: Vec::new(),
291                                    stored_allocated_size: *allocated_size,
292                                    observed_allocated_size: 0,
293                                    in_graveyard: false,
294                                    extended_attributes: Vec::new(),
295                                },
296                            }),
297                        );
298                    }
299                    _ => {
300                        self.fsck.error(FsckError::MalformedObjectRecord(
301                            self.store_id,
302                            key.into(),
303                            value.into(),
304                        ))?;
305                    }
306                }
307            }
308            ObjectKeyData::Keys => {
309                if let ObjectValue::Keys(keys) = value {
310                    match keys {
311                        EncryptionKeys::AES256XTS(keys) => {
312                            let keys = &**keys;
313                            if let Some(current_file) = &mut self.current_object {
314                                // Duplicates items should have already been checked, but not
315                                // duplicate key IDs.
316                                assert!(current_file.key_ids.is_empty());
317                                for (key_id, _) in keys {
318                                    if !current_file.key_ids.insert(*key_id) {
319                                        self.fsck.error(FsckError::DuplicateKey(
320                                            self.store_id,
321                                            key.object_id,
322                                            *key_id,
323                                        ))?;
324                                    }
325                                }
326                            } else {
327                                self.fsck.warning(FsckWarning::OrphanedKeys(
328                                    self.store_id,
329                                    key.object_id,
330                                ))?;
331                            }
332                        }
333                    }
334                } else {
335                    self.fsck.error(FsckError::MalformedObjectRecord(
336                        self.store_id,
337                        key.into(),
338                        value.into(),
339                    ))?;
340                }
341            }
342            ObjectKeyData::Attribute(attribute_id, AttributeKey::Attribute) => {
343                match value {
344                    ObjectValue::Attribute { size, has_overwrite_extents } => {
345                        match self.objects.get_mut(&key.object_id) {
346                            Some(
347                                ScannedObject::File(ScannedFile { attributes, .. })
348                                | ScannedObject::Directory(ScannedDir { attributes, .. })
349                                | ScannedObject::Symlink(ScannedSymlink { attributes, .. }),
350                            ) => {
351                                attributes.attributes.push(ScannedAttribute {
352                                    attribute_id,
353                                    size: *size,
354                                    has_overwrite_extents_flag: Some(*has_overwrite_extents),
355                                    observed_overwrite_extents: false,
356                                });
357                            }
358                            Some(ScannedObject::Graveyard) => { /* NOP */ }
359                            Some(ScannedObject::Tombstone) => {
360                                self.fsck.error(FsckError::TombstonedObjectHasRecords(
361                                    self.store_id,
362                                    key.object_id,
363                                ))?;
364                            }
365                            None => {
366                                // We verify key ordering elsewhere, and Object records come before
367                                // Attribute records, so we should never find an attribute without
368                                // its object already encountered.  Thus, this is an orphaned
369                                // attribute.
370                                self.fsck.warning(FsckWarning::OrphanedAttribute(
371                                    self.store_id,
372                                    key.object_id,
373                                    attribute_id,
374                                ))?;
375                            }
376                        }
377                    }
378                    ObjectValue::VerifiedAttribute { size, fsverity_metadata } => {
379                        match self.objects.get_mut(&key.object_id) {
380                            Some(ScannedObject::File(ScannedFile {
381                                attributes,
382                                is_verified,
383                                ..
384                            })) => {
385                                attributes.attributes.push(ScannedAttribute {
386                                    attribute_id,
387                                    size: *size,
388                                    has_overwrite_extents_flag: None,
389                                    observed_overwrite_extents: false,
390                                });
391                                let hash_size = match &fsverity_metadata.root_digest {
392                                    RootDigest::Sha256(root_hash) => root_hash.len(),
393                                    RootDigest::Sha512(root_hash) => root_hash.len(),
394                                };
395                                *is_verified = Some(hash_size);
396                            }
397                            Some(ScannedObject::Directory(..) | ScannedObject::Symlink(..)) => {
398                                self.fsck.error(FsckError::NonFileMarkedAsVerified(
399                                    self.store_id,
400                                    key.object_id,
401                                ))?;
402                            }
403                            Some(ScannedObject::Graveyard) => { /* NOP */ }
404                            Some(ScannedObject::Tombstone) => {
405                                self.fsck.error(FsckError::TombstonedObjectHasRecords(
406                                    self.store_id,
407                                    key.object_id,
408                                ))?;
409                            }
410                            None => {
411                                self.fsck.warning(FsckWarning::OrphanedAttribute(
412                                    self.store_id,
413                                    key.object_id,
414                                    attribute_id,
415                                ))?;
416                            }
417                        }
418                    }
419                    // Deleted attribute.
420                    ObjectValue::None => (),
421                    _ => {
422                        self.fsck.error(FsckError::MalformedObjectRecord(
423                            self.store_id,
424                            key.into(),
425                            value.into(),
426                        ))?;
427                    }
428                }
429            }
430            // Mostly ignore extents on this pass. We'll process them later.
431            ObjectKeyData::Attribute(_, AttributeKey::Extent(_)) => {
432                match value {
433                    // Regular extent record.
434                    ObjectValue::Extent(ExtentValue::Some { key_id, .. }) => {
435                        if let Some(current_file) = &self.current_object {
436                            if !self.is_encrypted && *key_id == 0 && current_file.key_ids.is_empty()
437                            {
438                                // Unencrypted files in unencrypted stores should use key ID 0.
439                            } else if !current_file.key_ids.contains(key_id) {
440                                self.fsck.error(FsckError::MissingKey(
441                                    self.store_id,
442                                    key.object_id,
443                                    *key_id,
444                                ))?;
445                            }
446                        } else {
447                            // This must be an orphaned extent, which should get picked up later.
448                        }
449                    }
450                    // Deleted extent.
451                    ObjectValue::Extent(ExtentValue::None) => {}
452                    _ => {
453                        self.fsck.error(FsckError::MalformedObjectRecord(
454                            self.store_id,
455                            key.into(),
456                            value.into(),
457                        ))?;
458                    }
459                }
460            }
461            // TODO(b/365631616): Check that the child type matches the directory metadata.
462            ObjectKeyData::Child { .. }
463            | ObjectKeyData::CasefoldChild { .. }
464            | ObjectKeyData::EncryptedChild { .. } => match value {
465                ObjectValue::None => {}
466                ObjectValue::Child(ChildValue { object_id: child_id, object_descriptor }) => {
467                    if *child_id == INVALID_OBJECT_ID {
468                        self.fsck.warning(FsckWarning::InvalidObjectIdInStore(
469                            self.store_id,
470                            key.into(),
471                            value.into(),
472                        ))?;
473                    }
474                    if self.root_objects.contains(child_id) {
475                        self.fsck.error(FsckError::RootObjectHasParent(
476                            self.store_id,
477                            *child_id,
478                            key.object_id,
479                        ))?;
480                    }
481                    if object_descriptor == &ObjectDescriptor::Volume && !self.is_root_store {
482                        self.fsck.error(FsckError::VolumeInChildStore(self.store_id, *child_id))?;
483                    }
484                }
485                _ => {
486                    self.fsck.error(FsckError::MalformedObjectRecord(
487                        self.store_id,
488                        key.into(),
489                        value.into(),
490                    ))?;
491                }
492            },
493            ObjectKeyData::Project { project_id, property: ProjectProperty::Limit } => {
494                // Should only be set on the root object store
495                if self.root_dir_id != key.object_id {
496                    self.fsck.error(FsckError::NonRootProjectIdMetadata(
497                        self.store_id,
498                        key.object_id,
499                        project_id,
500                    ))?;
501                }
502                match value {
503                    ObjectValue::None | ObjectValue::BytesAndNodes { .. } => {}
504                    _ => {
505                        self.fsck.error(FsckError::MalformedObjectRecord(
506                            self.store_id,
507                            key.into(),
508                            value.into(),
509                        ))?;
510                    }
511                }
512            }
513            ObjectKeyData::Project { project_id, property: ProjectProperty::Usage } => {
514                // Should only be set on the root object store
515                if self.root_dir_id != key.object_id {
516                    self.fsck.error(FsckError::NonRootProjectIdMetadata(
517                        self.store_id,
518                        key.object_id,
519                        project_id,
520                    ))?;
521                }
522                match value {
523                    ObjectValue::None => {
524                        self.stored_project_usages.remove(&project_id);
525                    }
526                    ObjectValue::BytesAndNodes { bytes, nodes } => {
527                        self.stored_project_usages.insert(project_id, (*bytes, *nodes));
528                    }
529                    _ => {
530                        self.fsck.error(FsckError::MalformedObjectRecord(
531                            self.store_id,
532                            key.into(),
533                            value.into(),
534                        ))?;
535                    }
536                }
537            }
538            ObjectKeyData::ExtendedAttribute { .. } => match value {
539                ObjectValue::None => {}
540                ObjectValue::ExtendedAttribute(ExtendedAttributeValue::Inline(_)) => {
541                    if self.objects.get(&key.object_id).is_none() {
542                        self.fsck.warning(FsckWarning::OrphanedExtendedAttributeRecord(
543                            self.store_id,
544                            key.object_id,
545                        ))?;
546                    }
547                }
548                ObjectValue::ExtendedAttribute(ExtendedAttributeValue::AttributeId(id)) => {
549                    match self.objects.get_mut(&key.object_id) {
550                        Some(
551                            ScannedObject::File(ScannedFile { attributes, .. })
552                            | ScannedObject::Directory(ScannedDir { attributes, .. })
553                            | ScannedObject::Symlink(ScannedSymlink { attributes, .. }),
554                        ) => {
555                            attributes.extended_attributes.push(*id);
556                        }
557                        Some(ScannedObject::Graveyard) => { /* NOP */ }
558                        Some(ScannedObject::Tombstone) => {
559                            self.fsck.error(FsckError::TombstonedObjectHasRecords(
560                                self.store_id,
561                                key.object_id,
562                            ))?;
563                        }
564                        None => {
565                            self.fsck.warning(FsckWarning::OrphanedExtendedAttributeRecord(
566                                self.store_id,
567                                key.object_id,
568                            ))?;
569                        }
570                    }
571                }
572                _ => {
573                    self.fsck.error(FsckError::MalformedObjectRecord(
574                        self.store_id,
575                        key.into(),
576                        value.into(),
577                    ))?;
578                }
579            },
580            ObjectKeyData::GraveyardEntry { .. } => {}
581            ObjectKeyData::GraveyardAttributeEntry { .. } => {}
582        }
583        Ok(())
584    }
585
586    /// Performs some checks on the child link and records information such as the sub-directory
587    /// count that get verified later.
588    fn process_child(
589        &mut self,
590        parent_id: u64,
591        child_id: u64,
592        object_descriptor: &ObjectDescriptor,
593        object_key_data: &ObjectKeyData,
594    ) -> Result<(), Error> {
595        let mut child_wrapping_key_id = None;
596        if let Some(ScannedObject::Directory(dir)) = self.objects.get(&parent_id) {
597            match object_key_data {
598                ObjectKeyData::Child { .. } => {
599                    if dir.casefold {
600                        self.fsck.error(FsckError::CasefoldInconsistency(
601                            self.store_id,
602                            parent_id,
603                            child_id,
604                        ))?;
605                    }
606                }
607                ObjectKeyData::CasefoldChild { .. } => {
608                    if !dir.casefold {
609                        self.fsck.error(FsckError::CasefoldInconsistency(
610                            self.store_id,
611                            parent_id,
612                            child_id,
613                        ))?;
614                    }
615                }
616                ObjectKeyData::EncryptedChild { .. } => {
617                    if dir.wrapping_key_id.is_none() {
618                        self.fsck.error(FsckError::UnencryptedDirectoryHasEncryptedChild(
619                            self.store_id,
620                            parent_id,
621                            child_id,
622                        ))?;
623                    }
624                }
625                _ => {
626                    bail!(
627                        "Unexpected object_key_data type in process_child: {:?}",
628                        object_key_data
629                    );
630                }
631            };
632        }
633        match (self.objects.get_mut(&child_id), object_descriptor) {
634            (
635                Some(ScannedObject::File(ScannedFile { parents, .. })),
636                ObjectDescriptor::File | ObjectDescriptor::Volume,
637            ) => {
638                parents.push(parent_id);
639            }
640            (
641                Some(ScannedObject::Directory(ScannedDir { parent, wrapping_key_id, .. })),
642                ObjectDescriptor::Directory,
643            ) => {
644                if matches!(object_key_data, ObjectKeyData::EncryptedChild { .. }) {
645                    if let Some(id) = wrapping_key_id {
646                        child_wrapping_key_id = Some(*id);
647                    } else {
648                        self.fsck.error(FsckError::EncryptedChildDirectoryNoWrappingKey(
649                            self.store_id,
650                            child_id,
651                        ))?;
652                    }
653                }
654                if parent.is_some() {
655                    // TODO(https://fxbug.dev/42168496): Accumulating and reporting all parents
656                    // might be useful.
657                    self.fsck
658                        .error(FsckError::MultipleLinksToDirectory(self.store_id, child_id))?;
659                }
660                *parent = Some(parent_id);
661            }
662            (Some(ScannedObject::Tombstone), _) => {
663                self.fsck.error(FsckError::TombstonedObjectHasRecords(self.store_id, parent_id))?;
664                return Ok(());
665            }
666            (None, _) => {
667                self.fsck.error(FsckError::MissingObjectInfo(self.store_id, child_id))?;
668                return Ok(());
669            }
670            (Some(s), _) => {
671                let expected = match s {
672                    ScannedObject::Directory(_) => ObjectDescriptor::Directory,
673                    ScannedObject::File(_) | ScannedObject::Graveyard => ObjectDescriptor::File,
674                    ScannedObject::Symlink(ScannedSymlink { parents, .. }) => {
675                        parents.push(parent_id);
676                        ObjectDescriptor::Symlink
677                    }
678                    ScannedObject::Tombstone => unreachable!(),
679                };
680                if &expected != object_descriptor {
681                    self.fsck.error(FsckError::ConflictingTypeForLink(
682                        self.store_id,
683                        child_id,
684                        expected.into(),
685                        object_descriptor.into(),
686                    ))?;
687                }
688            }
689        }
690        match self.objects.get_mut(&parent_id) {
691            Some(
692                ScannedObject::File(..) | ScannedObject::Graveyard | ScannedObject::Symlink(_),
693            ) => {
694                self.fsck.error(FsckError::ObjectHasChildren(self.store_id, parent_id))?;
695            }
696            Some(ScannedObject::Directory(ScannedDir {
697                observed_sub_dirs,
698                wrapping_key_id,
699                ..
700            })) => {
701                if let Some(parent_wrapping_key_id) = *wrapping_key_id {
702                    if !matches!(object_key_data, ObjectKeyData::EncryptedChild { .. }) {
703                        self.fsck.error(FsckError::EncryptedDirectoryHasUnencryptedChild(
704                            self.store_id,
705                            parent_id,
706                            child_id,
707                        ))?;
708                    } else {
709                        if let Some(child_wrapping_key_id) = child_wrapping_key_id {
710                            if child_wrapping_key_id != parent_wrapping_key_id {
711                                self.fsck.error(
712                                    FsckError::ChildEncryptedWithDifferentWrappingKeyThanParent(
713                                        self.store_id,
714                                        parent_id,
715                                        child_id,
716                                        parent_wrapping_key_id,
717                                        child_wrapping_key_id,
718                                    ),
719                                )?;
720                            }
721                        }
722                    }
723                }
724                if *object_descriptor == ObjectDescriptor::Directory {
725                    *observed_sub_dirs += 1;
726                }
727            }
728            Some(ScannedObject::Tombstone) => {
729                self.fsck.error(FsckError::TombstonedObjectHasRecords(self.store_id, parent_id))?;
730            }
731            None => self.fsck.error(FsckError::MissingObjectInfo(self.store_id, parent_id))?,
732        }
733        Ok(())
734    }
735
736    // Process an extent, performing some checks and building fsck.allocations.
737    async fn process_extent(
738        &mut self,
739        object_id: u64,
740        attribute_id: u64,
741        range: &Range<u64>,
742        device_offset: u64,
743        bs: u64,
744        is_overwrite_extent: bool,
745    ) -> Result<(), Error> {
746        if range.start % bs > 0 || range.end % bs > 0 {
747            self.fsck.error(FsckError::MisalignedExtent(
748                self.store_id,
749                object_id,
750                range.clone(),
751                0,
752            ))?;
753        }
754        if range.start >= range.end {
755            self.fsck.error(FsckError::MalformedExtent(
756                self.store_id,
757                object_id,
758                range.clone(),
759                0,
760            ))?;
761            return Ok(());
762        }
763        let len = range.end - range.start;
764        match self.objects.get_mut(&object_id) {
765            Some(
766                ScannedObject::File(ScannedFile { attributes, .. })
767                | ScannedObject::Directory(ScannedDir { attributes, .. })
768                | ScannedObject::Symlink(ScannedSymlink { attributes, .. }),
769            ) => {
770                let ScannedAttributes {
771                    attributes,
772                    tombstoned_attributes,
773                    observed_allocated_size: allocated_size,
774                    in_graveyard,
775                    ..
776                } = attributes;
777                match attributes.iter_mut().find(|attribute| attribute.attribute_id == attribute_id)
778                {
779                    Some(attribute) => {
780                        if !*in_graveyard
781                            && !tombstoned_attributes.contains(&attribute_id)
782                            && range.end > round_up(attribute.size, bs).unwrap()
783                        {
784                            self.fsck.error(FsckError::ExtentExceedsLength(
785                                self.store_id,
786                                object_id,
787                                attribute_id,
788                                attribute.size,
789                                range.into(),
790                            ))?;
791                        }
792                        attribute.observed_overwrite_extents =
793                            attribute.observed_overwrite_extents || is_overwrite_extent;
794                    }
795                    None => {
796                        self.fsck.warning(FsckWarning::ExtentForMissingAttribute(
797                            self.store_id,
798                            object_id,
799                            attribute_id,
800                        ))?;
801                    }
802                }
803                *allocated_size += len;
804            }
805            Some(ScannedObject::Graveyard | ScannedObject::Tombstone) => { /* NOP */ }
806            None => {
807                self.fsck
808                    .warning(FsckWarning::ExtentForNonexistentObject(self.store_id, object_id))?;
809            }
810        }
811        if device_offset % bs > 0 {
812            self.fsck.error(FsckError::MisalignedExtent(
813                self.store_id,
814                object_id,
815                range.clone(),
816                device_offset,
817            ))?;
818        }
819        let item = Item::new(
820            AllocatorKey { device_range: device_offset..device_offset + len },
821            AllocatorValue::Abs { count: 1, owner_object_id: self.store_id },
822        );
823        let lower_bound: AllocatorKey = item.key.lower_bound_for_merge_into();
824        self.fsck.allocations.merge_into(item, &lower_bound, allocator::merge::merge);
825        Ok(())
826    }
827
828    // A graveyard entry can either be for tombstoning a file/attribute, or for trimming a file.
829    fn handle_graveyard_entry(
830        &mut self,
831        object_id: u64,
832        attribute_id: Option<u64>,
833        tombstone: bool,
834    ) -> Result<(), Error> {
835        match self.objects.get_mut(&object_id) {
836            Some(ScannedObject::File(ScannedFile {
837                parents,
838                attributes: ScannedAttributes { in_graveyard, tombstoned_attributes, .. },
839                ..
840            })) => {
841                if attribute_id.is_none() {
842                    *in_graveyard = true;
843                }
844                if tombstone {
845                    if let Some(attribute_id) = attribute_id {
846                        tombstoned_attributes.push(attribute_id);
847                    } else {
848                        parents.push(INVALID_OBJECT_ID)
849                    }
850                }
851            }
852            Some(
853                ScannedObject::Directory(ScannedDir { attributes, .. })
854                | ScannedObject::Symlink(ScannedSymlink { attributes, .. }),
855            ) => {
856                if tombstone {
857                    if let Some(attribute_id) = attribute_id {
858                        attributes.tombstoned_attributes.push(attribute_id);
859                    } else {
860                        attributes.in_graveyard = true;
861                    }
862                } else {
863                    self.fsck.error(FsckError::UnexpectedObjectInGraveyard(object_id))?;
864                }
865            }
866            Some(ScannedObject::Graveyard | ScannedObject::Tombstone) => {
867                self.fsck.error(FsckError::UnexpectedObjectInGraveyard(object_id))?;
868            }
869            None => {
870                self.fsck.warning(FsckWarning::GraveyardRecordForAbsentObject(
871                    self.store_id,
872                    object_id,
873                ))?;
874            }
875        }
876        Ok(())
877    }
878
879    // Called when all items for the current file have been processed.
880    fn finish_file(&mut self) -> Result<(), Error> {
881        if let Some(current_file) = self.current_object.take() {
882            if self.is_encrypted {
883                let mut key_ids = vec![];
884                for id in current_file.key_ids.iter() {
885                    key_ids.push(*id);
886                }
887
888                // If the store is unencrypted, then the file might or might not have encryption
889                // keys (e.g. the root store has encrypted layer files). Also, if the object has
890                // lazily generated keys, like directories and symlinks, it will only have keys if
891                // an attribute has been written, in which case we check the existence of the key
892                // then.
893                if key_ids.is_empty() && !current_file.lazy_keys {
894                    self.fsck.error(FsckError::MissingEncryptionKeys(
895                        self.store_id,
896                        current_file.object_id,
897                    ))?;
898                }
899
900                match self.objects.get_mut(&current_file.object_id) {
901                    Some(ScannedObject::Directory(ScannedDir {
902                        wrapping_key_id,
903                        attributes,
904                        ..
905                    })) => {
906                        if !attributes.extended_attributes.is_empty() {
907                            if !key_ids.contains(&0) {
908                                self.fsck.error(FsckError::MissingKey(
909                                    self.store_id,
910                                    current_file.object_id,
911                                    0,
912                                ))?;
913                            }
914                        }
915                        if wrapping_key_id.is_some() {
916                            if !key_ids.contains(&1) {
917                                self.fsck.error(FsckError::MissingKey(
918                                    self.store_id,
919                                    current_file.object_id,
920                                    1,
921                                ))?;
922                            }
923                        }
924                    }
925                    Some(_) => {}
926                    None => self.fsck.error(FsckError::MissingObjectInfo(
927                        self.store_id,
928                        current_file.object_id,
929                    ))?,
930                }
931            }
932        }
933        Ok(())
934    }
935}
936
937// Scans extents and directory child entries in the store, emitting synthesized allocations into
938// |fsck.allocations|, updating the sizes for files in |scanned| and performing checks on directory
939// children.
940// TODO(https://fxbug.dev/42177485): Roll the extent scanning back into main function.
941async fn scan_extents_and_directory_children<'a>(
942    store: &ObjectStore,
943    scanned: &mut ScannedStore<'a>,
944    result: &mut FsckResult,
945) -> Result<(), Error> {
946    let bs = store.block_size();
947    let layer_set = store.tree().layer_set();
948    let mut merger = layer_set.merger();
949    let mut iter = merger.query(Query::FullScan).await?;
950    let mut allocated_bytes = 0;
951    let mut extent_count = 0;
952    let mut previous_object_id = INVALID_OBJECT_ID;
953    while let Some(itemref) = iter.get() {
954        match itemref {
955            ItemRef {
956                key:
957                    ObjectKey {
958                        object_id,
959                        data:
960                            ObjectKeyData::Attribute(
961                                attribute_id,
962                                AttributeKey::Extent(ExtentKey { range }),
963                            ),
964                    },
965                value: ObjectValue::Extent(extent),
966                ..
967            } => {
968                // Ignore deleted extents.
969                if let ExtentValue::Some { device_offset, mode, .. } = extent {
970                    let size = range.length().unwrap_or(0);
971                    allocated_bytes += size;
972
973                    if previous_object_id != *object_id {
974                        if previous_object_id != INVALID_OBJECT_ID {
975                            result.fragmentation.extent_count
976                                [FragmentationStats::get_histogram_bucket_for_count(
977                                    extent_count,
978                                )] += 1;
979                        }
980                        extent_count = 0;
981                        previous_object_id = *object_id;
982                    }
983                    result.fragmentation.extent_size
984                        [FragmentationStats::get_histogram_bucket_for_size(size)] += 1;
985                    extent_count += 1;
986
987                    let is_overwrite_extent =
988                        matches!(mode, ExtentMode::Overwrite | ExtentMode::OverwritePartial(_));
989
990                    scanned
991                        .process_extent(
992                            *object_id,
993                            *attribute_id,
994                            range,
995                            *device_offset,
996                            bs,
997                            is_overwrite_extent,
998                        )
999                        .await?;
1000                };
1001            }
1002            ItemRef {
1003                key: ObjectKey { object_id, data: object_key_data @ ObjectKeyData::Child { .. } },
1004                value: ObjectValue::Child(ChildValue { object_id: child_id, object_descriptor }),
1005                ..
1006            }
1007            | ItemRef {
1008                key:
1009                    ObjectKey {
1010                        object_id,
1011                        data: object_key_data @ ObjectKeyData::EncryptedChild { .. },
1012                    },
1013                value: ObjectValue::Child(ChildValue { object_id: child_id, object_descriptor }),
1014                ..
1015            }
1016            | ItemRef {
1017                key:
1018                    ObjectKey { object_id, data: object_key_data @ ObjectKeyData::CasefoldChild { .. } },
1019                value: ObjectValue::Child(ChildValue { object_id: child_id, object_descriptor }),
1020                ..
1021            } => {
1022                scanned.process_child(*object_id, *child_id, object_descriptor, object_key_data)?
1023            }
1024            _ => {}
1025        }
1026        iter.advance().await?;
1027    }
1028    if extent_count != 0 && previous_object_id != INVALID_OBJECT_ID {
1029        result.fragmentation.extent_count
1030            [FragmentationStats::get_histogram_bucket_for_count(extent_count)] += 1;
1031    }
1032    scanned.fsck.verbose(format!(
1033        "Store {} has {} bytes allocated",
1034        store.store_object_id(),
1035        allocated_bytes
1036    ));
1037    Ok(())
1038}
1039
1040fn validate_attributes(
1041    fsck: &Fsck<'_>,
1042    store_id: u64,
1043    object_id: u64,
1044    attributes: &ScannedAttributes,
1045    is_file: bool,
1046    is_verified: Option<usize>,
1047    block_size: u64,
1048) -> Result<(), Error> {
1049    let ScannedAttributes {
1050        attributes,
1051        tombstoned_attributes,
1052        observed_allocated_size,
1053        stored_allocated_size,
1054        extended_attributes,
1055        ..
1056    } = attributes;
1057    if observed_allocated_size != stored_allocated_size {
1058        fsck.error(FsckError::AllocatedSizeMismatch(
1059            store_id,
1060            object_id,
1061            *observed_allocated_size,
1062            *stored_allocated_size,
1063        ))?;
1064    }
1065
1066    if is_file {
1067        let data_attribute =
1068            attributes.iter().find(|attribute| attribute.attribute_id == DEFAULT_DATA_ATTRIBUTE_ID);
1069        match data_attribute {
1070            None => fsck.error(FsckError::MissingDataAttribute(store_id, object_id))?,
1071            Some(data_attribute) => {
1072                let merkle_attribute = attributes
1073                    .iter()
1074                    .find(|attribute| attribute.attribute_id == FSVERITY_MERKLE_ATTRIBUTE_ID);
1075
1076                // Note a merkle attribute can exist for a non-verified file in the case that the
1077                // power cut while we were writing the merkle attribute across multiple txns. In
1078                // this case, the merkle attribute will be cleaned up on reboot.
1079                if is_verified.is_some() && merkle_attribute.is_none() {
1080                    fsck.error(FsckError::VerifiedFileDoesNotHaveAMerkleAttribute(
1081                        store_id, object_id,
1082                    ))?;
1083                }
1084
1085                if let (Some(merkle_attribute), Some(hash_size)) = (merkle_attribute, is_verified) {
1086                    // If the file is empty, the merkle tree should just be a single hash.
1087                    let expected_size = if data_attribute.size == 0 {
1088                        hash_size as u64
1089                    // Else, use ceiling integer division in case data_size is not a multiple of
1090                    // block size.
1091                    } else {
1092                        ((data_attribute.size + (block_size - 1)) / block_size) * hash_size as u64
1093                    };
1094                    if merkle_attribute.size != expected_size {
1095                        fsck.error(FsckError::IncorrectMerkleTreeSize(
1096                            store_id,
1097                            object_id,
1098                            expected_size,
1099                            merkle_attribute.size,
1100                        ))?;
1101                    }
1102                }
1103            }
1104        }
1105    }
1106
1107    // Attributes queued for tombstoning must exist.
1108    for attr in tombstoned_attributes {
1109        if attributes.iter().find(|attribute| attribute.attribute_id == *attr).is_none() {
1110            fsck.error(FsckError::TombstonedAttributeDoesNotExist(store_id, object_id, *attr))?
1111        }
1112    }
1113
1114    for expected_attribute_id in extended_attributes {
1115        if attributes
1116            .iter()
1117            .find(|attribute| attribute.attribute_id == *expected_attribute_id)
1118            .is_none()
1119        {
1120            fsck.error(FsckError::MissingAttributeForExtendedAttribute(
1121                store_id,
1122                object_id,
1123                *expected_attribute_id,
1124            ))?;
1125        }
1126    }
1127
1128    for attribute in attributes {
1129        if attribute.attribute_id >= EXTENDED_ATTRIBUTE_RANGE_START
1130            && attribute.attribute_id < EXTENDED_ATTRIBUTE_RANGE_END
1131        {
1132            // For all the attributes in the extended attribute range, make sure there is an
1133            // extended attribute record for them.
1134            if extended_attributes
1135                .iter()
1136                .find(|xattr_id| attribute.attribute_id == **xattr_id)
1137                .is_none()
1138            {
1139                fsck.warning(FsckWarning::OrphanedExtendedAttribute(
1140                    store_id,
1141                    object_id,
1142                    attribute.attribute_id,
1143                ))?;
1144            }
1145        }
1146
1147        if attribute
1148            .has_overwrite_extents_flag
1149            .is_some_and(|has_flag| has_flag && !attribute.observed_overwrite_extents)
1150        {
1151            fsck.error(FsckError::MissingOverwriteExtents(
1152                store_id,
1153                object_id,
1154                attribute.attribute_id,
1155            ))?;
1156        }
1157        if attribute
1158            .has_overwrite_extents_flag
1159            .is_some_and(|has_flag| !has_flag && attribute.observed_overwrite_extents)
1160        {
1161            fsck.error(FsckError::OverwriteExtentFlagUnset(
1162                store_id,
1163                object_id,
1164                attribute.attribute_id,
1165            ))?;
1166        }
1167    }
1168
1169    Ok(())
1170}
1171
1172/// Scans an object store, accumulating all of its allocations into |fsck.allocations| and
1173/// validating various object properties.
1174pub(super) async fn scan_store(
1175    fsck: &Fsck<'_>,
1176    store: &ObjectStore,
1177    root_objects: impl AsRef<[u64]>,
1178    result: &mut FsckResult,
1179) -> Result<(), Error> {
1180    let store_id = store.store_object_id();
1181
1182    let mut scanned = ScannedStore::new(
1183        fsck,
1184        root_objects,
1185        store_id,
1186        store.is_root(),
1187        store.is_encrypted(),
1188        store.root_directory_object_id(),
1189    );
1190
1191    // Scan the store for objects, attributes, and parent/child relationships.
1192    let layer_set = store.tree().layer_set();
1193    let mut merger = layer_set.merger();
1194    let mut iter = merger.query(Query::FullScan).await?;
1195    let mut last_item: Option<Item<ObjectKey, ObjectValue>> = None;
1196    while let Some(item) = iter.get() {
1197        if let Some(last_item) = last_item {
1198            if last_item.key >= *item.key {
1199                fsck.fatal(FsckFatal::MisOrderedObjectStore(store_id))?;
1200            }
1201        }
1202        if item.key.object_id == INVALID_OBJECT_ID {
1203            fsck.warning(FsckWarning::InvalidObjectIdInStore(
1204                store_id,
1205                item.key.into(),
1206                item.value.into(),
1207            ))?;
1208        }
1209        if let Some(current_file) = &scanned.current_object {
1210            if item.key.object_id != current_file.object_id {
1211                scanned.finish_file()?;
1212            }
1213        }
1214        scanned.process(item.key, item.value)?;
1215        last_item = Some(item.cloned());
1216        iter.advance().await?;
1217    }
1218    scanned.finish_file()?;
1219
1220    for (project_id, node_id) in scanned.used_project_ids.iter() {
1221        if !scanned.stored_project_usages.contains_key(project_id) {
1222            fsck.error(FsckError::ProjectUsedWithNoUsageTracking(store_id, *project_id, *node_id))?;
1223        }
1224    }
1225    for (project_id, (bytes_stored, nodes_stored)) in scanned.stored_project_usages.iter() {
1226        if let Some((bytes_used, nodes_used)) = scanned.total_project_usages.get(&project_id) {
1227            if *bytes_stored != *bytes_used || *nodes_stored != *nodes_used {
1228                fsck.warning(FsckWarning::ProjectUsageInconsistent(
1229                    store_id,
1230                    *project_id,
1231                    (*bytes_stored, *nodes_stored),
1232                    (*bytes_used, *nodes_used),
1233                ))?;
1234            }
1235        } else {
1236            if *bytes_stored > 0 || *nodes_stored > 0 {
1237                fsck.warning(FsckWarning::ProjectUsageInconsistent(
1238                    store_id,
1239                    *project_id,
1240                    (*bytes_stored, *nodes_stored),
1241                    (0, 0),
1242                ))?;
1243            }
1244        }
1245    }
1246
1247    // Add a reference for files in the graveyard (which acts as the file's parent until it is
1248    // purged, leaving only the Object record in the original store and no links to the file).
1249    // This must be done after scanning the object store.
1250    let layer_set = store.tree().layer_set();
1251    let mut merger = layer_set.merger();
1252    let mut iter = fsck.assert(
1253        Graveyard::iter(store.graveyard_directory_object_id(), &mut merger).await,
1254        FsckFatal::MalformedGraveyard,
1255    )?;
1256    while let Some(info) = iter.get() {
1257        match info.value() {
1258            ObjectValue::Some => {
1259                scanned.handle_graveyard_entry(info.object_id(), info.attribute_id(), true)?
1260            }
1261            ObjectValue::Trim => {
1262                if let Some(attribute_id) = info.attribute_id() {
1263                    fsck.error(FsckError::TrimValueForGraveyardAttributeEntry(
1264                        store_id,
1265                        info.object_id(),
1266                        attribute_id,
1267                    ))?
1268                } else {
1269                    scanned.handle_graveyard_entry(info.object_id(), None, false)?
1270                }
1271            }
1272            _ => fsck.error(FsckError::BadGraveyardValue(store_id, info.object_id()))?,
1273        }
1274        fsck.assert(iter.advance().await, FsckFatal::MalformedGraveyard)?;
1275    }
1276
1277    scan_extents_and_directory_children(store, &mut scanned, result).await?;
1278
1279    // At this point, we've provided all of the inputs to |scanned|.
1280
1281    // Mark all the root directories as visited so that cycle detection below works.
1282    for oid in scanned.root_objects {
1283        if let Some(ScannedObject::Directory(ScannedDir { visited, .. })) =
1284            scanned.objects.get_mut(&oid)
1285        {
1286            *visited.get_mut() = true;
1287        }
1288    }
1289
1290    // Iterate over all objects performing checks we were unable to perform earlier.
1291    let mut num_objects = 0;
1292    let mut files = 0;
1293    let mut directories = 0;
1294    let mut symlinks = 0;
1295    let mut tombstones = 0;
1296    let mut other = 0;
1297    let mut stack = Vec::new();
1298    for (object_id, object) in &scanned.objects {
1299        num_objects += 1;
1300        match object {
1301            ScannedObject::File(ScannedFile {
1302                parents,
1303                stored_refs,
1304                attributes,
1305                is_verified,
1306                ..
1307            }) => {
1308                files += 1;
1309                let observed_refs = parents.len().try_into().unwrap();
1310                // observed_refs == 0 is handled separately to distinguish orphaned objects
1311                if observed_refs != *stored_refs && observed_refs > 0 {
1312                    fsck.error(FsckError::RefCountMismatch(
1313                        *object_id,
1314                        observed_refs,
1315                        *stored_refs,
1316                    ))?;
1317                }
1318                validate_attributes(
1319                    fsck,
1320                    store_id,
1321                    *object_id,
1322                    attributes,
1323                    true,
1324                    *is_verified,
1325                    store.block_size(),
1326                )?;
1327                if parents.is_empty() {
1328                    fsck.warning(FsckWarning::OrphanedObject(store_id, *object_id))?;
1329                }
1330                if parents.contains(&INVALID_OBJECT_ID) && parents.len() > 1 {
1331                    let parents = parents
1332                        .iter()
1333                        .filter(|oid| **oid != INVALID_OBJECT_ID)
1334                        .cloned()
1335                        .collect::<Vec<u64>>();
1336                    fsck.error(FsckError::ZombieFile(store_id, *object_id, parents))?;
1337                }
1338            }
1339            ScannedObject::Directory(ScannedDir {
1340                stored_sub_dirs,
1341                observed_sub_dirs,
1342                parent,
1343                visited,
1344                attributes,
1345                ..
1346            }) => {
1347                directories += 1;
1348                if *observed_sub_dirs != *stored_sub_dirs {
1349                    fsck.error(FsckError::SubDirCountMismatch(
1350                        store_id,
1351                        *object_id,
1352                        *observed_sub_dirs,
1353                        *stored_sub_dirs,
1354                    ))?;
1355                }
1356                validate_attributes(
1357                    fsck,
1358                    store_id,
1359                    *object_id,
1360                    attributes,
1361                    false,
1362                    None,
1363                    store.block_size(),
1364                )?;
1365                if let Some(mut oid) = parent {
1366                    if attributes.in_graveyard {
1367                        fsck.error(FsckError::ZombieDir(store_id, *object_id, oid))?;
1368                    }
1369                    // Check this directory is attached to a root object.
1370                    // SAFETY: This is safe because here and below are the only places that we
1371                    // manipulate `visited`.
1372                    if !std::mem::replace(unsafe { &mut *visited.get() }, true) {
1373                        stack.push(*object_id);
1374                        loop {
1375                            if let Some(ScannedObject::Directory(ScannedDir {
1376                                parent: Some(parent),
1377                                visited,
1378                                ..
1379                            })) = scanned.objects.get(&oid)
1380                            {
1381                                stack.push(oid);
1382                                oid = *parent;
1383                                // SAFETY: See above.
1384                                if std::mem::replace(unsafe { &mut *visited.get() }, true) {
1385                                    break;
1386                                }
1387                            } else {
1388                                // This indicates an error (e.g. missing parent), but they should be
1389                                // reported elsewhere.
1390                                break;
1391                            }
1392                        }
1393                        // Check that the object we got to isn't one in our stack which would
1394                        // indicate a cycle.
1395                        for s in stack.drain(..) {
1396                            if s == oid {
1397                                fsck.error(FsckError::LinkCycle(store_id, oid))?;
1398                                break;
1399                            }
1400                        }
1401                    }
1402                } else if !attributes.in_graveyard {
1403                    fsck.warning(FsckWarning::OrphanedObject(store_id, *object_id))?;
1404                }
1405            }
1406            ScannedObject::Graveyard => other += 1,
1407            ScannedObject::Symlink(ScannedSymlink { parents, stored_refs, attributes }) => {
1408                symlinks += 1;
1409                let observed_refs = parents.len().try_into().unwrap();
1410                // observed_refs == 0 is handled separately to distinguish orphaned objects
1411                if observed_refs != *stored_refs && observed_refs > 0 {
1412                    fsck.error(FsckError::RefCountMismatch(
1413                        *object_id,
1414                        observed_refs,
1415                        *stored_refs,
1416                    ))?;
1417                }
1418                validate_attributes(
1419                    fsck,
1420                    store_id,
1421                    *object_id,
1422                    attributes,
1423                    false,
1424                    None,
1425                    store.block_size(),
1426                )?;
1427                if attributes.in_graveyard {
1428                    if !parents.is_empty() {
1429                        fsck.error(FsckError::ZombieSymlink(
1430                            store_id,
1431                            *object_id,
1432                            parents.clone(),
1433                        ))?;
1434                    }
1435                } else if parents.is_empty() {
1436                    fsck.warning(FsckWarning::OrphanedObject(store_id, *object_id))?;
1437                }
1438            }
1439            ScannedObject::Tombstone => {
1440                tombstones += 1;
1441                num_objects -= 1;
1442            }
1443        }
1444    }
1445    if num_objects != store.object_count() {
1446        fsck.error(FsckError::ObjectCountMismatch(store_id, num_objects, store.object_count()))?;
1447    }
1448    fsck.verbose(format!(
1449        "Store {store_id} has {files} files, {directories} dirs, {symlinks} symlinks, \
1450         {tombstones} tombstones, {other} other objects",
1451    ));
1452
1453    Ok(())
1454}
fxfs/fsck/store_scanner.rs

fxfs/fsck/
store_scanner.rs
