path: root/Fsck.mdwn

Fsck in bcachefs:
=================

This document is an overview of fsck in bcachefs, as well as what will need to
change for snapshots.

In bcachefs, the fsck code is only responsible for checking higher level
filesystem structure. Btree topology and allocation information are checked by
`btree_gc.c`, which doesn't need to be aware of snapshots. This reduces the
scope of fsck considerably.

What it does have to check is:

* For each extent, dirent and xattr, that a corresponding inode exists and is of
  the appropriate type.

* Dirents and xattrs indexed by hash, with linear probing. The fsck code is
  responsible for checking that they're stored at the correct index (in case
  there was a hash collision, every index between the hash value and the actual
  index must be occupied by keys or hash whiteouts) and that there are no
  duplicates.

* Dirents: check that target inode exists and matches dirent's `d_type`, and
  check the target inode's backpointer fields.

* Extents:
 * Check that extents do not overlap
 * Check that extents do not exist past inode's `i_size`
 * Count extents for each inode and check inode's `i_sectors`.

* Check that root directory exists

* Check that lost+found exists

* Check directory stucture: currently, this is done with a depth-first traversal
  from the root directory. We check for directories with multiple links, and
  then scan the inodes btree for directories that weren't found by the DFS.

* Check each inode's link count: At this point we know that every dirent exists
  in a directory (has a corresponding inode of the correct type), has a valid
  target, and is reachable (because we've checked that all directories are
  reachable). All that's left is to scan the dirents btree, counting the number
  of dirents that point to each inode number, and verifying that against each
  inode's link count.


Changes for snapshots:
======================

Subvolumes vs. snapshots:

Filesystem code has to know what subvolume it is in, in order to fetch the
current snapshot ID at the start of every btree transaction. Fsck code does not
know or care what subvolume a given key belongs to - a key may belong to multiple
subvolumes, if it's in a snapshot that's an interior node in the snapshots
tree.

Instead, when one key references another (e.g. a dirent that points to an
inode), it does the lookup for the inode by searching for an inode with a
snapshot ID equal to or an ancestor of the dirent key's snapshot ID.
 
IOW, snaphsot IDs represent (branchable) "points in time", and fsck wants to
check that every view of the filesystem, at every point in time, is consistent.

Checking the filesystem for consistency in this fashion is conceptually
straightforward - every key has a snapshot ID, and we use that when looking up
anything that it references. However, we'll have to be careful about how we
repair inconsistencies when the snapshot ID is an interior node:

If we repair an inconsistency by deleting a key, we need to ensure that key is
not referenced by child snapshots. For example, if we find an extent that does
not have an `S_ISREG` inode, currently we delete it. But we might find an extent
that doesn't have a corresponding inode in with a snapshot ID equal to or
ancestor to the extents snapshot ID, but does have an inode in a child snapshot.
If that were to occur, we should probably copy that inode to the extent's
snapshot ID.

We would like it to be as hard a rule as possible that fsck never deletes or
modifies keys that belong to interior node snapshot IDs, because when people are
using snapshots they'll generally want the data in that snapshot to always stay
intact and it would be rather bad form if data was torched due to a bug in fsck.

It may not be possible to adhere to this rule while fixing all filesystem
inconsistencies - e.g. if extents exist above an inode's `i_size`, then
generally speaking the right thing to do is to delete that extent. But if we
find inconsistencies in at interior node snapshot IDs, then perhaps the best
thing to do would be to just leave it, or only apply changes in leaf node
snapshot IDs. 

Algorithmic considerations:
===========================

We want bcachefs to scale well into the millions of snapshots. This means that
there can't generally be operations that have to run for each subvolume or
snapshot - the fsck algorithms have to work one key at a time, processing them
in natural btree order.

This means that the extents, dirents and xattrs passes need to use
`BTREE_ITER_ALL_SNAPSHOTS`, meaning that as they walk keys for a given inode,
they'll be seeing keys from every snapshot version mixed together - and there
will be multiple versions of the inode, in different snapshots, that they need
to be checked against.

There's a helper in the fsck code that these passes use, `walk_inode()`, that
fetches the inode for the current inode number when it changes. This will
probably change to load every copy of that inode, in each snapshot ID. Also,
where we have to maintain state we'll have to duplicate that state for every
snapshot ID that exists at that inode number.

We'll also need to know, for every key that we process, which snapshot IDs it is
visible in: so that e.g. the extents pass can correctly count `i_sectors`.

Note that "millions of snapshots" will not _typically_ mean "millions of snaphot
IDs at the same time" - when we allocate new inodes we pick inode numbers that
aren't in use in any other snapshot or subvolume, and most files in a filesytem
are created, written to once and then later atomically replaced with a rename
call. When we're dealing with a file that keys with many different snapshot IDs
we need to make sure we don't have any hidden O(n^2) algorithms, but if fsck
requires in the hundreds of megabytes of state to check these files with worst
case numbers of overwrites, that's not the end of the world.

## Checking directory structure:

The current approach of doing a DFS from the root directory still works with
snapshots, but algorithmically is too slow. If we have many sparse snapshots,
the DFS would recurse into each of those snapshots, walking directory structure
it has already seen in the original subvolume - but those snapshots could have
directory structure changes in one or two places, so it would have to. We need
an algorithm that iterators over keys, not filesystem structure.

Fortunately, since backpointers from inodes to dirents were recently added we
can take a different approach. We walk the inodes btree, and for every directory
inode we find we chase backpointers until we get to the root directory. Note
that since previous passes have already checked backpointers, we're really just
check for loops here. This will still check the same structure repeatedly, like
the DFS approach, but here we can solve it by adding every inum:snapshot tuple
to a hash table after we've verified it has a path to the root.

## Checking inode link counts:

This one will be tedious, but algorithmically doesn't change much. The existing
code walks the dirents btree in natural key order, and then for each dirent
increments a link count in a radix tree. After walking the dirents, we walk the
inodes btree and compare link counts we calculated to what's in the inode.

As before, we'll walk the dirents btree in natural key order. However, we can't
accumulate link counts without also looking at what actually exists in the inodes
btree: a dirent may point to multiple inodes with different snapshot IDs, and
which of those we increment also depends on which snapshots that dirent is
visible in (we'll already have a helper for that part, as discussed previously).

This means that instead of using a radix tree, we'll have to start by walking
the inodes btree, and for every inode we find creating a new in memory data
structure (eytzinger layout search tree, perhaps) indexed by inode
number:snapshot id and containing just the link count we'll be calculating.

Fortunately hardlinks are usually rare in actual practice. We can make use of
the fact that we've already checked inode backpointers and only include inodes
that actually have hardlinks in this table.