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

fxfs/fsck/
store_scanner.rs
