One of the perpetual scaling problems XFS has is indexing it's incore
inodes. We currently uses hashes and the default hash sizes chosen can
only ever be a tradeoff between memory consumption and the maximum
realistic size of the cache.

As a result, anyone who has millions of inodes cached on a filesystem
needs to tunes the size of the cache via the ihashsize mount option to
allow decent scalability with inode cache operations.

A further problem is the separate inode cluster hash, whose size is based
on the ihashsize but is smaller, and so under certain conditions (sparse
cluster cache population) this can become a limitation long before the
inode hash is causing issues.

The following patchset removes the inode hash and cluster hash and
replaces them with radix trees to avoid the scalability limitations of the
hashes. It also reduces the size of the inodes by 3 pointers....

SGI-PV: 969561
SGI-Modid: xfs-linux-melb:xfs-kern:29481a
Signed-off-by: NDavid Chinner <dgc@sgi.com>
Signed-off-by: NChristoph Hellwig <hch@infradead.org>
Signed-off-by: NTim Shimmin <tes@sgi.com>

SGI-PV: 963965
SGI-Modid: xfs-linux-melb:xfs-kern:28485a
Signed-off-by: NLachlan McIlroy <lachlan@sgi.com>
Signed-off-by: NDavid Chinner <dgc@sgi.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

The previous fixes for the use after free in xfs_iunpin left a nasty log
deadlock when xfslogd unpinned the inode and dropped the last reference to
the inode. the ->clear_inode() method can issue transactions, and if the
log was full, the transaction could push on the log and get stuck trying
to push the inode it was currently unpinning.

To fix this, we provide xfs_iunpin a guarantee that it will always have a
valid xfs_inode <-> linux inode link or a particular flag will be set on
the inode. We then use log forces during lookup to ensure transactions are
completed before we recycle the inode. This ensures that xfs_iunpin will
never use the linux inode after it is being freed, and any lookup on an
inode on the reclaim list will wait until it is safe to attach a new linux
inode to the xfs inode.

SGI-PV: 956832
SGI-Modid: xfs-linux-melb:xfs-kern:27359a
Signed-off-by: NDavid Chinner <dgc@sgi.com>
Signed-off-by: NShailendra Tripathi <stripathi@agami.com>
Signed-off-by: NTakenori Nagano <t-nagano@ah.jp.nec.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

SGI-PV: 956832
SGI-Modid: xfs-linux-melb:xfs-kern:27358a
Signed-off-by: NDavid Chinner <dgc@sgi.com>
Signed-off-by: NNathan Scott <nscott@aconex.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

SGI-PV: 956964
SGI-Modid: xfs-linux-melb:xfs-kern:27200a
Signed-off-by: NTim Shimmin <tes@sgi.com>
Signed-off-by: NDavid Chinner <dgc@sgi.com>
Signed-off-by: NEric Sandeen <sandeen@sandeen.net>

The previous attempts to fix the linux inode use-after-free in xfs_iunpin
simply made the problem harder to hit. We actually need complete exclusion
between xfs_reclaim and xfs_iunpin, as well as ensuring that the i_flags
are consistent during both of these functions. Introduce a new spinlock
for exclusion and the i_flags, and fix up xfs_iunpin to use igrab before
marking the inode dirty.

SGI-PV: 952967
SGI-Modid: xfs-linux-melb:xfs-kern:26964a
Signed-off-by: NDavid Chinner <dgc@sgi.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

One sema to rule them all, one sema to find them...

SGI-PV: 907752
SGI-Modid: xfs-linux-melb:xfs-kern:26911a
Signed-off-by: NEric Sandeen <sandeen@sandeen.net>
Signed-off-by: NNathan Scott <nathans@sgi.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

range.

SGI-PV: 955302
SGI-Modid: xfs-linux-melb:xfs-kern:26803a
Signed-off-by: NNathan Scott <nathans@sgi.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

one page.

SGI-PV: 955302
SGI-Modid: xfs-linux-melb:xfs-kern:26800a
Signed-off-by: NNathan Scott <nathans@sgi.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

SGI-PV: 953819
SGI-Modid: xfs-linux-melb:xfs-kern:26628a
Signed-off-by: NNathan Scott <nathans@sgi.com>
Signed-off-by: NTim Shimmin <tes@sgi.com>

pure bloat.

SGI-PV: 952969
SGI-Modid: xfs-linux-melb:xfs-kern:26251a
Signed-off-by: NNathan Scott <nathans@sgi.com>

is check if semaphore is actually locked, which can be trivially done in
portable way. Code gets more reabable, while we are at it... 

SGI-PV: 953915
SGI-Modid: xfs-linux-melb:xfs-kern:26274a
Signed-off-by: NAl Viro <viro@zeniv.linux.org.uk>
Signed-off-by: NNathan Scott <nathans@sgi.com>

SGI-PV: 953338
SGI-Modid: xfs-linux-melb:xfs-kern:26107a
Signed-off-by: NNathan Scott <nathans@sgi.com>

SGI-PV: 9533338
SGI-Modid: xfs-linux-melb:xfs-kern:26106a
Signed-off-by: NNathan Scott <nathans@sgi.com>

millions of inodes cached and has sparse cluster population, removing
inodes from the cluster hash consumes excessive amounts of CPU time.
Reduce the CPU cost by making removal O(1) via use of a double linked list
for the hash chains.

SGI-PV: 951551
SGI-Modid: xfs-linux-melb:xfs-kern:25683a
Signed-off-by: NDavid Chinner <dgc@sgi.com>
Signed-off-by: NNathan Scott <nathans@sgi.com>

these typos.

SGI-PV: 904196
SGI-Modid: xfs-linux-melb:xfs-kern:25539a
Signed-off-by: NNathan Scott <nathans@sgi.com>

SGI-PV: 947038
SGI-Modid: xfs-linux-melb:xfs-kern:25474a
Signed-off-by: NNathan Scott <nathans@sgi.com>

SGI-PV: 947206
SGI-Modid: xfs-linux-melb:xfs-kern:203960a
Signed-off-by: NChristoph Hellwig <hch@sgi.com>
Signed-off-by: NNathan Scott <nathans@sgi.com>

boilerplate.

SGI-PV: 913862
SGI-Modid: xfs-linux:xfs-kern:23903a
Signed-off-by: NNathan Scott <nathans@sgi.com>

SGI-PV: 943122
SGI-Modid: xfs-linux:xfs-kern:23901a
Signed-off-by: NNathan Scott <nathans@sgi.com>

fixes crashes under high nfs load

SGI-PV: 941429
SGI-Modid: xfs-linux:xfs-kern:197929a
Signed-off-by: NChristoph Hellwig <hch@sgi.com>
Signed-off-by: NNathan Scott <nathans@sgi.com>

SGI-PV: 934766
SGI-Modid: xfs-linux:xfs-kern:196852a
Signed-off-by: NChristoph Hellwig <hch@sgi.com>
Signed-off-by: NNathan Scott <nathans@sgi.com>

SGI Modid: xfs-linux:xfs-kern:21915a
Signed-off-by: NNathan Scott <nathans@sgi.com>
Signed-off-by: NChristoph Hellwig <hch@sgi.com>

Initial git repository build. I'm not bothering with the full history,
even though we have it. We can create a separate "historical" git
archive of that later if we want to, and in the meantime it's about
3.2GB when imported into git - space that would just make the early
git days unnecessarily complicated, when we don't have a lot of good
infrastructure for it.

Let it rip!