blob: 4692463de2df62ffe7e799d5d5fe8239b5250d7e [file] [log] [blame]
A living document. The basic algorithm.
0) Need to bring some sanity into the case of flags that can
be set in the secondaries at mkfs time but reset or cleared
in the primary later in the filesystem's life.
0) Clear the persistent read-only bit if set. Clear the
shared bit if set and the version number is zero. This
brings the filesystem back to a known state.
0) make sure that superblock geometry code checks the logstart
value against whether or not we have an internal log.
If we have an internal log and a logdev, that's ok.
(Maybe we just aren't using it). If we have an external
log (logstart == 0) but no logdev, that's right out.
0) write secondary superblock search code. Rewrite initial
superblock parsing code to be less complicated. Just
use variables to indicate primary, secondary, etc.,
and use a function to get the SB given a specific location
or something.
2) For inode alignment, if the SB bit is set and the
inode alignment size field in the SB is set, then
believe that the fs inodes MUST be aligned and
disallow any non-aligned inodes. Likewise, if
the SB bit isn't set (or earlier version) and
the inode alignment size field is zero, then
never set the bit even if the inodes are aligned.
Note that the bits and alignment values are
replicated in the secondary superblocks.
0) add feature specification options to parse_arguments
0) add logic to add_inode_ref(), add_inode_reached()
to detect nlink overflows in cases where the fs
(or user had indicated fs) doesn't support new nlinks.
6) check to make sure that the inodes containing btree blocks
with # recs < minrecs aren't legit -- e.g. the only
descendant of a root block.
7) inode di_size value sanity checking -- should always be less than
the biggest filebno offset mentioned in the bmaps. Doesn't
have to be equal though since we're allowed to overallocate
(it just wastes a little space). This is for both regular
files and directories (have to modify the existing directory
Add tracking of largest offset in bmap scanning code. Compare
value against di_size. Should be >= di_size.
Alternatively, you could pass the inode into down through
the extent record processing layer and make the checks
Add knowledge of quota inodes. size of quota inode is
always zero. We should maintain that.
8) Basic quota stuff.
if quota feature bit is set, the quota inodes
if set, should point to disconnected, 0 len inodes.
D - if quota inodes exist, the quota bits must be
turned on. It's ok for the quota flags to be
zeroed but they should be in a legal state
(see xfs_quota.h).
D - if the quota flags are non-zero, the corresponding
quota inodes must exist.
quota inodes are never deleted, only their space
is freed.
if quotas are being downgraded, then check quota inodes
at the end of phase 3. If they haven't been cleared yet,
clear them. Regardless, then clear sb flags (quota inode
fields, quota flags, and quota bit).
5) look at verify_inode_chunk(). it's probably really broken.
9) Complicated quota stuff. Add code to bmap scan code to
track used blocks. Add another pair of AVL trees
to track user and project quota limits. Set AVL
trees up at the beginning of phase 3. Quota inodes
can be rebuilt or corrected later if damaged.
D - 0) fix directory processing. phase 3, if an entry references
a free inode, *don't* mark it used. wait for the rest of
phase 3 processing to hit that inode. If it looks like it's
in use, we'll mark in use then. If not, we'll clear it and
mark the inode map. then in phase 4, you can depend on the
inode map. should probably set the parent info in phase 4.
So we have a check_dups flag. Maybe we should change the
name of check_dir to discover_inodes. During phase 3
(discover_inodes == 1), uncertain inodes are added to list.
During phase 4 (discover_inodes == 0), they aren't. And
we never mark inodes in use from the directory code.
During phase 4, we shouldn't complain about names with
a leading '/' since we made those names in phase 3.
Have to change dino_chunks.c (parent setting), dinode.c
and dir.c.
D - 0) make sure we don't screw up filesystems with real-time inodes.
remember to initialize real-time map with all blocks XR_E_FREE.
D - 4) check contents of symlinks as well as lengths in process_symlinks()
in dinode.c. Right now, we only check lengths.
D - 1) Feature mismatches -- for quotas and attributes,
if the stuff exists in the filesystem, set the
superblock version bits.
D - 0) rewrite directory leaf block holemap comparison code.
probably should just check the leaf block hole info
against our incore bitmap. If the hole flag is not
set, then we know that there can only be one hole and
it has to be between the entry table and the top of heap.
If the hole flag is set, then it's ok if the on-disk
holemap doesn't describe everything as long as what
it does describe doesn't conflict with reality.
D - 0) rewrite setting nlinks handling -- for version 1
inodes, set both nlinks and onlinks (zero projid_lo/hi
and pad) if we have to change anything. For
version 2, I think we're ok.
D - 0) Put awareness of quota inode into mark_standalone_inodes.
D - 8) redo handling of superblocks with bad version numbers. need
to bail out (without harming) fs's that have sbs that
are newer than we are.
D - 0) How do we handle feature mismatches between fs and
superblock? For nlink, check each inode after you
know it's good. If onlinks is 0 and nlinks is > 0
and it's a version 2 inode, then it really is a version
2 inode and the nlinks flag in the SB needs to be set.
If it's a version 2 inode and the SB agrees but onlink
is non-zero, then clear onlink.
D - 3) keep cumulative counts of freeblocks, inodes, etc. to set in
the superblock at the end of phase 5. Remember that
agf freeblock counters don't include blocks used by
the non-root levels of the freespace trees but that
the sb free block counters include those.
D - 0) Do parent setting in directory code (called by phase 3).
actually, I put it in process_inode_set and propagated
the parent up to it from the process_dinode/process_dir
routines. seemed cleaner than pushing the irec down
and letting them bang on it.
D - 0) If we clear a file in phase 4, make sure that if it's
a directory that the parent info is cleared also.
D - 0) put inode tree flashover (call to add_ino_backptrs) into phase 5.
D - 0) do set/get_inode_parent functions in incore_ino.c.
also do is/set/ inode_processed.
D - 0) do a versions.c to extract feature info and set global vars
from the superblock version number and possibly feature bits
D - 0) change longform_dir_entry_check + shortform_dir_entry_check
to return a count of how many illegal '/' entries exist.
if > 0, then process_dirstack needs to call prune_dir_entry
with a hash value of 0 to delete the entries.
D - 0) add the "processed" bitfield
to the backptrs_t struct that gets attached after
phase 4.
D- ) Phase 6 !!!
D - 0) look at usage of XFS_MAKE_IPTR(). It does the right
arithmetic assuming you count your offsets from the
beginning of the buffer.
D - 0) look at references to XFS_INODES_PER_CHUNK. change the
ones that really mean sizeof(uint64_t)*NBBY to
something else (like that only defined as a constant
INOS_PER_IREC. this isn't as important since
XFS_INODES_PER_CHUNK will never chang
D - 0) look at junk_zerolen_dir_leaf_entries() to make sure it isn't hosing
the freemap since it assumed that bytes between the
end of the table and firstused didn't show up in the
freemap when they actually do.
D - 0) track down XFS_INO_TO_OFFSET() usage. I don't think I'm
using it right. (e.g. I think
it gives you the offset of an inode into a block but
on small block filesystems, I may be reading in inodes
in multiblock buffers and working from the start of
the buffer plus I'm using it to get offsets into
my ino_rec's which may not be a good idea since I
use 64-inode ino_rec's whereas the offset macro
works off blocksize).
D - 0.0) put buffer -> dirblock conversion macros into xfs kernel code
D - 0.2) put in sibling pointer checking and path fixup into
bmap (long form) scan routines in scan.c
D - 0.3) find out if bmap btrees with only root blocks are legal. I'm
betting that they're not because they'd be extent inodes
instead. If that's the case, rip some code out of
Algorithm (XXX means not done yet):
Phase 1 -- get a superblock and zero log
get a superblock -- either read in primary or
find a secondary (ag header), check ag headers
To find secondary:
Go for brute force and read in the filesystem N meg
at a time looking for a superblock. as a
slight optimization, we could maybe skip
ahead some number of blocks to try and get
towards the end of the first ag.
After you find a secondary, try and find at least
other ags as a verification that the
secondary is a good superblock.
XXX - Ugh. Have to take growfs'ed filesystems into account.
The root superblock geometry info may not be right if
recovery hasn't run or it's been trashed. The old ag's
may or may not be right since the system could have crashed
during growfs or the bwrite() to the superblocks could have
failed and the buffer been reused. So we need to check
to see if another ag exists beyond the "last" ag
to see if a growfs happened. If not, then we know that
the geometry info is good and treat the fs as a non-growfs'ed
fs. If we do have inconsistencies, then the smaller geometry
is the old fs and the larger the new. We can check the
new superblocks to see if they're good. If not, then we
know the system crashed at or soon after the growfs and
we can choose to either accept the new geometry info or
trash it and truncate the fs back to the old geometry
Cross-check geometry information in secondary sb's with
primary to ensure that it's correct.
Use sim code to allow mount filesystems *without* reading
in root inode. This sets up the xfs_mount_t structure
and allows us to use XFS_* macros that we wouldn't
otherwise be able to use.
Note, I split phase 1 and 2 into separate pieces because I want
to initialize the xfs_repair incore data structures after phase 1.
parse superblock version and feature flags and set appropriate
global vars to reflect the flags (attributes, quotas, etc.)
Workaround for the mkfs "not zeroing the superblock buffer" bug.
Determine what field is the last valid non-zero field in
the superblock. The trick here is to be able to differentiate
the last valid non-zero field in the primary superblock and
secondaries because they may not be the same. Fields in
the primary can be set as the filesystem gets upgraded but
the upgrades won't touch the secondaries. This means that
we need to find some number of secondaries and check them.
So we do the checking here and the setting in phase2.
Phase 2 -- check integrity of allocation group allocation structures
zero the log if in no modify mode
sanity check ag headers -- superblocks match, agi isn't
trashed -- the agf and agfl
don't really matter because we can
just recreate them later.
Zero part of the superblock buffer if necessary
Walk the freeblock trees to get an
initial idea of what the fs thinks is free.
Files that disagree (claim free'd blocks)
can be salvaged or deleted. If the btree is
internally inconsistent, when in doubt, mark
blocks free. If they're used, they'll be stolen
back later. don't have to check sibling pointers
for each level since we're going to regenerate
all the trees anyway.
Walk the inode allocation trees and
make sure they're ok, otherwise the sim
inode routines will probably just barf.
mark inode allocation tree blocks and ag header
blocks as used blocks. If the trees are
corrupted, this phase will generate "uncertain"
inode chunks. Those chunks go on a list and
will have to verified later. Record the blocks
that are used to detect corruption and multiply
claimed blocks. These trees will be regenerated
later. Mark the blocks containing inodes referenced
by uncorrupted inode trees as being used by inodes.
The other blocks will get marked when/if the inodes
are verified.
calculate root and realtime inode numbers from the
filesystem geometry, fix up mount structure's
incore superblock if they're wrong.
ASSUMPTION: at end of phase 2, we've got superblocks and ag headers
that are not garbage (some data in them like counters and the
freeblock and inode trees may be inconsistent but the header
is readable and otherwise makes sense).
XXX if in no_modify mode, check for blocks claimed by one freespace
btree and not the other
Phase 3 -- traverse inodes to make the inodes, bmaps and freespace maps
consistent. For each ag, use either the incore inode map or
scan the ag for inodes.
Let's use the incore inode map, now that we've made one
up in phase2. If we lose the maps, we'll locate inodes
when we traverse the directory heirarchy. If we lose both,
we could scan the disk. Ugh. Maybe make that a command-line
option that we support later.
ASSUMPTION: we know if the ag allocation btrees are intact (phase 2)
First - Walk and clear the ag unlinked lists. We'll process
the inodes later. Check and make sure that the unlinked
lists reference known inodes. If not, add to the list
of uncertain inodes.
Second, check the uncertain inode list generated in phase2 and
above and get them into the inode tree if they're good.
The incore inode cluster tree *always* has good
clusters (alignment, etc.) in it.
Third, make sure that the root inode is known. If not,
and we know the inode number from the superblock,
discover that inode and its chunk.
Then, walk the incore inode-cluster tree.
Maintain an in-core bitmap over the entire fs for block allocation.
traverse each inode, make sure inode mode field matches free/allocated
bit in the incore inode allocation tree. If there's a mismatch,
assume that the inode is in use.
- for each in-use inode, traverse each bmap/dir/attribute
map or tree. Maintain a map (extent list?) for the
current inode.
- For each block marked as used, check to see if already known
(referenced by another file or directory) and sanity
check the contents of the block as well if possible
(in the case of meta-blocks).
- if the inode claims already used blocks, mark the blocks
as multiply claimed (duplicate) and go on. the inode
will be cleared in phase 4.
- if metablocks are garbaged, clear the inode after
traversing what you can of the bmap and
proceed to next inode. We don't have to worry
about trashing the maps or trees in cleared inodes
because the blocks will show up as free in the
ag freespace trees that we set up in phase 5.
- clear the di_next_unlinked pointer -- all unlinked
but active files go bye-bye.
- All blocks start out unknown. We need the last state
in case we run into a case where we need to step
on a block to store filesystem meta-data and it
turns out later that it's referenced by some inode's
bmap. In that case, the inode loses because we've
already trashed the block. This shouldn't happen
in the first version unless some inode has a bogus
bmap referencing blocks in the ag header but the
4th state will keep us from inadvertently doing
something stupid in that case.
- If inode is allocated, mark all blocks allocated to the
current inode as allocated in the incore freespace
- If inode is good and a directory, scan through it to
find leaf entries and discover any unknown inodes.
For shortform, we correct what we can.
If the directory is corrupt, we try and fix it in
place. If it has zero good entries, then we blast it.
All unknown inodes get put onto the uncertain inode
list. This is safe because we only put inodes onto
the list when we're processing known inodes so the
uncertain inode list isn't in use.
We fix only one problem -- an entry that has
a mathematically invalid inode numbers in them.
If that's the case, we replace the inode number
with NULLFSINO and we'll fix up the entry in
phase 6.
That info may conflict with the inode information,
but we'll straighten out any inconsistencies there
in phase4 when we process the inodes again.
Errors involving bogus forward/back links,
zero-length entries make the directory get
if an entry references a free inode, ignore that
fact for now. wait for the rest of phase 3
processing to hit that inode. If it looks like it's
in use, we'll mark in use then. If not, we'll
clear it and mark the inode map. then in phase
4, you can depend on the inode map.
Entries that point to non-existent or free
inodes, and extra blocks in the directory
will get fixed in place in a later pass.
Entries that point to a quota inode are
marked TBD.
If the directory internally points to the same
block twice, the directory gets blown away.
Note that processing uncertain inodes can add more inodes
to the uncertain list if they're directories. So we loop
until the uncertain list is empty.
During inode verification, if the inode blocks are unknown,
mark then as in-use by inodes.
XXX HEURISTIC -- if we blow an inode away that has space,
assume that the freespace btree is now out of wack.
If it was ok earlier, it's certain to be wrong now.
And the odds of this space free cancelling out the
existing error is so small I'm willing to ignore it.
Should probably do this via a global var and complain
about this later.
Assumption: All known inodes are now marked as in-use or free. Any
inodes that we haven't found by now are hosed (lost) since
we can't reach them via either the inode btrees or via directory
Directories are semi-clean. All '.' entries are good.
Root '..' entry is good if root inode exists. All entries
referencing non-existent inodes, free inodes, etc.
XXX verify that either quota inode is 0 or NULLFSINO or
if sb quota flag is non zero, verify that quota inode
is NULLFSINO or is referencing a used, but disconnected
XXX if in no_modify mode, check for unclaimed blocks
- Phase 4 - Check for inodes referencing duplicate blocks
At this point, all known duplicate blocks are marked in
the block map. However, some of the claimed blocks in
the bmap may in fact be free because they belong to inodes
that have to be cleared either due to being a trashed
directory or because it's the first inode to claim a
block that was then claimed later. There's a similar
problem with meta-data blocks that are referenced by
inode bmaps that are going to be freed once the inode
(or directory) gets cleared.
So at this point, we collect the duplicate blocks into
extents and put them into the duplicate extent list.
Mark the ag header blocks as in use.
We then process each inode twice -- the first time
we check to see if the inode claims a duplicate extent
and we do NOT set the block bitmap. If the inode claims
a duplicate extent, we clear the inode. Since the bitmap
hasn't been set, that automatically frees all blocks associated
with the cleared inode. If the inode is ok, process it a second
time and set the bitmap since we know that this inode will live.
The unlinked list gets cleared in every inode at this point as
well. We no longer need to preserve it since we've discovered
every inode we're going to find from it.
verify existence of root inode. if it exists, check for
existence of "lost+found". If it exists, mark the entry
to be deleted, and clear the inode. All the inodes that
were connected to the lost+found will be reconnected later.
XXX HEURISTIC -- if we blow an inode away that has space,
assume that the freespace btree is now out of wack.
If it was ok earlier, it's certain to be wrong now.
And the odds of this space free cancelling out the
existing error is so small I'm willing to ignore it.
Should probably do this via a global var and complain
about this later.
Clear the quota inodes if the inode btree says that
they're not in use. The space freed will get picked
up by phase 5.
XXX Clear the quota inodes if the filesystem is being downgraded.
- Phase 5 - Build inode allocation trees, freespace trees and
agfl's for each ag. After this, we should be able to
unmount the filesystem and remount it for real.
For each ag: (if no in no_modify mode)
scan bitmap first to figure out number of extents.
calculate space required for all trees. Start with inode trees.
Setup the btree cursor which includes the list of preallocated
blocks. As a by-product, this will delete the extents required
for the inode tree from the incore extent tree.
Calculate how many extents will be required to represent the
remaining free extent tree on disk (twice, one for bybno and
one for bycnt). You have to iterate on this because consuming
extents can alter the number of blocks required to represent
the remaining extents. If there's slop left over, you can
put it in the agfl though.
Then, manually build the trees, agi, agfs, and agfls.
XXX if in no_modify mode, scan the on-disk inode allocation
trees and compare against the incore versions. Don't have
to scan the freespace trees because we caught the problems
there in phase2 and phase3. But if we cleared any inodes
with space during phases 3 or 4, now is the time to complain.
XXX - Free duplicate extent lists. ???
Assumptions: at this point, sim code having to do with inode
creation/modification/deletion and space allocation
work because the inode maps, space maps, and bmaps
for all files in the filesystem are good. The only
structures that are screwed up are the directory contents,
which means that lookup may not work for beans, the
root inode which exists but may be completely bogus and
the link counts on all inodes which may also be bogus.
Free the bitmap, the freespace tree.
Flash the incore inode tree over from parent list to having
full backpointers.
realtime processing, if any --
(Skip to below if running in no_modify mode).
Generate the realtime bitmap from the incore realtime
extent map and slam the info into the realtime bitmap
inode. Generate summary info from the realtime extent map.
XXX if in no_modify mode, compare contents of realtime bitmap
inode to the incore realtime extent map. generate the
summary info from the incore realtime extent map.
compare against the contents of the realtime summary inode.
complain if bad.
reset superblock counters, sync version numbers
- Phase 6 - directory traversal -- check reference counts,
attach disconnected inodes, fix up bogus directories
Assumptions: all on-disk space and inode trees are structurally
sound. Incore and on-disk inode trees agree on whether
an inode is in use.
Directories are structurally sound. All hashvalues
are monotonically increasing and interior nodes are
correct so lookups work. All legal directory entries
point to inodes that are in use and exist. Shortform
directories are fine except that the links haven't been
checked for conflicts (cycles, ".." being correct, etc.).
Longform directories haven't been checked for those problems
either PLUS longform directories may still contain
entries beginning with '/'. No zero-length entries
exist (they've been deleted or converted to '/').
Root directory may or may not exist. orphange may
or may not exist. Contents of either may be completely
Entries may point to free or non-existent inodes.
At this we point, we may need new incore structures and
may be able to trash an old one (like the filesystem
block map)
If '/' is trashed, then reinitialize it.
If no realtime inodes, make them and if necessary, slam the
summary info into the realtime summary
inode. Ditto with the realtime bitmap inode.
Make orphanage (lost+found ???).
Traverse each directory from '/' (unless it was created).
Check directory structure and each directory entry.
If the entry is bogus (points to a non-existent or
free inode, for example), mark that entry TBD. Maintain
link counts on all inodes. Currently, traversal is
Mark every inode reached as "reached" (includes
bumping up link counts).
If a entry points to a directory but the parent (..)
disagrees, then blow away the entry. if the directory
being pointed to winds up disconnected, it'll be moved
to the orphanage (and the link count incremented to
account for the link and the reached bit set then).
If an entry points to a directory that we've already
reached, then some entry is bad and should be blown
away. It's easiest to blow away the current entry
plus since presumably the parent entry in the
reached directory points to another directory,
then it's far more likely that the current
entry is bogus (otherwise the parent should point
at it).
If an entry points to a non-existent of free inode,
blow the entry away.
Every time a good entry is encountered update the
link count for the inode that the entry points to.
After traversal, scan incore inode map for directories not
reached. Go to first one and try and find its root
by following .. entries. Once at root, run traversal
algorithm. When algorithm terminates, move subtree
root inode to the orphanage. Repeat as necessary
until all disconnected directories are attached.
Move all disconnected inodes to orphanage.
- Phase 7: reset reference counts if required.
Now traverse the on-disk inodes again, and make sure on-disk
reference counts are correct. Reset if necessary.
SKIP all unused inodes -- that also makes us
skip the orphanage inode which we think is
unused but is really used. However, the ref counts
on that should be right so that's ok.
multiple TB xfs_repair
modify above to work in a couple of AGs at a time. The bitmaps
should span only the current set of AGs.
The key it scan the inode bmaps and keep a list of inodes
that span multiple AG sets and keep the list in a data structure
that's keyed off AG set # as well as inode # and also has a bit
to indicate whether or not the inode will be cleared.
Then in each AG set, when doing duplicate extent processing,
you have to process all multi-AG-set inodes that claim blocks in
the current AG set. If there's a conflict, you mark clear the
inode in the current AG and you mark the multi-AG inode as
"to be cleared".
After going through all AGs, you can clear the to-be-cleared
multi-AG-set inodes and pull them off the list.
When building up the AG freespace trees, you walk the bmaps
of all multi-AG-set inodes that are in the AG-set and include
blocks claimed in the AG by the inode as used.
This probably involves adding a phase 3-0 which would have to
check all the inodes to see which ones are multi-AG-set inodes
and set up the multi-AG-set inode data structure. Plus the
process_dinode routines may have to be altered just a bit
to do the right thing if running in tera-byte mode (call
out to routines that check the multi-AG-set inodes when
To make things go faster, phase 3-0 could probably run
in parallel. It should be possible to run phases 2-5
in parallel as well once the appropriate synchronization
is added to the incore routines and the static directory
leaf block bitmap is changed to be on the stack.
Phase 7 probably can be in parallel as well.
By in parallel, I mean that assuming that an AG-set
contains 4 AGs, you could run 4 threads, 1 per AG
in parallel to process the AG set.
I don't see how phase 6 can be run in parallel though.
And running Phase 8 in parallel is just silly.