A living document.  The basic algorithm.

TODO: (D == DONE)

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
	check).

	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
	there.

	Add knowledge of quota inodes.  size of quota inode is
	always zero.  We should maintain that.

8)  Basic quota stuff.

	Invariants
		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
	process_btinode()


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
		parameters.

	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
			bitmap.

		- 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
			trashed.

			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
	entries.

	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
	inode.

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
		bogus.

		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
		depth-first.

		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
appropriate).

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.