[XFS] Radix tree based inode caching
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: David Chinner <dgc@sgi.com>
Signed-off-by: Christoph Hellwig <hch@infradead.org>
Signed-off-by: Tim Shimmin <tes@sgi.com>
diff --git a/fs/xfs/xfs_inode.h b/fs/xfs/xfs_inode.h
index 873b9f7..b6dd23d 100644
--- a/fs/xfs/xfs_inode.h
+++ b/fs/xfs/xfs_inode.h
@@ -172,41 +172,18 @@
extern void xfs_iocore_inode_init(struct xfs_inode *);
extern void xfs_iocore_inode_reinit(struct xfs_inode *);
-
/*
- * This is the type used in the xfs inode hash table.
- * An array of these is allocated for each mounted
- * file system to hash the inodes for that file system.
+ * This is the xfs inode cluster structure. This structure is used by
+ * xfs_iflush to find inodes that share a cluster and can be flushed to disk at
+ * the same time.
*/
-typedef struct xfs_ihash {
- struct xfs_inode *ih_next;
- rwlock_t ih_lock;
- uint ih_version;
-} xfs_ihash_t;
-
-#define XFS_IHASH(mp,ino) ((mp)->m_ihash + (((uint)(ino)) % (mp)->m_ihsize))
-
-/*
- * This is the xfs inode cluster hash. This hash is used by xfs_iflush to
- * find inodes that share a cluster and can be flushed to disk at the same
- * time.
- */
-typedef struct xfs_chashlist {
- struct xfs_chashlist *chl_next;
- struct xfs_chashlist *chl_prev;
- struct xfs_inode *chl_ip;
- xfs_daddr_t chl_blkno; /* starting block number of
+typedef struct xfs_icluster {
+ struct hlist_head icl_inodes; /* list of inodes on cluster */
+ xfs_daddr_t icl_blkno; /* starting block number of
* the cluster */
- struct xfs_buf *chl_buf; /* the inode buffer */
-} xfs_chashlist_t;
-
-typedef struct xfs_chash {
- xfs_chashlist_t *ch_list;
- lock_t ch_lock;
-} xfs_chash_t;
-
-#define XFS_CHASH(mp,blk) ((mp)->m_chash + (((uint)blk) % (mp)->m_chsize))
-
+ struct xfs_buf *icl_buf; /* the inode buffer */
+ lock_t icl_lock; /* inode list lock */
+} xfs_icluster_t;
/*
* This is the xfs in-core inode structure.
@@ -269,21 +246,15 @@
} xfs_icdinode_t;
typedef struct {
- struct xfs_ihash *ip_hash; /* pointer to hash header */
- struct xfs_inode *ip_next; /* inode hash link forw */
struct xfs_inode *ip_mnext; /* next inode in mount list */
struct xfs_inode *ip_mprev; /* ptr to prev inode */
- struct xfs_inode **ip_prevp; /* ptr to prev i_next */
struct xfs_mount *ip_mount; /* fs mount struct ptr */
} xfs_iptr_t;
typedef struct xfs_inode {
/* Inode linking and identification information. */
- struct xfs_ihash *i_hash; /* pointer to hash header */
- struct xfs_inode *i_next; /* inode hash link forw */
struct xfs_inode *i_mnext; /* next inode in mount list */
struct xfs_inode *i_mprev; /* ptr to prev inode */
- struct xfs_inode **i_prevp; /* ptr to prev i_next */
struct xfs_mount *i_mount; /* fs mount struct ptr */
struct list_head i_reclaim; /* reclaim list */
struct bhv_desc i_bhv_desc; /* inode behavior descriptor*/
@@ -324,9 +295,8 @@
unsigned int i_delayed_blks; /* count of delay alloc blks */
xfs_icdinode_t i_d; /* most of ondisk inode */
- xfs_chashlist_t *i_chash; /* cluster hash list header */
- struct xfs_inode *i_cnext; /* cluster hash link forward */
- struct xfs_inode *i_cprev; /* cluster hash link backward */
+ xfs_icluster_t *i_cluster; /* cluster list header */
+ struct hlist_node i_cnode; /* cluster link node */
xfs_fsize_t i_size; /* in-memory size */
/* Trace buffers per inode. */
@@ -521,8 +491,6 @@
*/
void xfs_ihash_init(struct xfs_mount *);
void xfs_ihash_free(struct xfs_mount *);
-void xfs_chash_init(struct xfs_mount *);
-void xfs_chash_free(struct xfs_mount *);
xfs_inode_t *xfs_inode_incore(struct xfs_mount *, xfs_ino_t,
struct xfs_trans *);
void xfs_inode_lock_init(xfs_inode_t *, struct bhv_vnode *);
@@ -633,7 +601,7 @@
#define xfs_inobp_check(mp, bp)
#endif /* DEBUG */
-extern struct kmem_zone *xfs_chashlist_zone;
+extern struct kmem_zone *xfs_icluster_zone;
extern struct kmem_zone *xfs_ifork_zone;
extern struct kmem_zone *xfs_inode_zone;
extern struct kmem_zone *xfs_ili_zone;