xfs: introduce inode record hole mask for sparse inode chunks

The inode btrees track 64 inodes per record regardless of inode size.
Thus, inode chunks on disk vary in size depending on the size of the
inodes. This creates a contiguous allocation requirement for new inode
chunks that can be difficult to satisfy on an aged and fragmented (free
space) filesystems.

The inode record freecount currently uses 4 bytes on disk to track the
free inode count. With a maximum freecount value of 64, only one byte is
required. Convert the freecount field to a single byte and use two of
the remaining 3 higher order bytes left for the hole mask field. Use the
final leftover byte for the total count field.

The hole mask field tracks holes in the chunks of physical space that
the inode record refers to. This facilitates the sparse allocation of
inode chunks when contiguous chunks are not available and allows the
inode btrees to identify what portions of the chunk contain valid
inodes. The total count field contains the total number of valid inodes
referred to by the record. This can also be deduced from the hole mask.
The count field provides clarity and redundancy for internal record
verification.

Note that neither of the new fields can be written to disk on fs'
without sparse inode support. Doing so writes to the high-order bytes of
freecount and causes corruption from the perspective of older kernels.
The on-disk inobt record data structure is updated with a union to
distinguish between the original, "full" format and the new, "sparse"
format. The conversion routines to get, insert and update records are
updated to translate to and from the on-disk record accordingly such
that freecount remains a 4-byte value on non-supported fs, yet the new
fields of the in-core record are always valid with respect to the
record. This means that higher level code can refer to the current
in-core record format unconditionally and lower level code ensures that
records are translated to/from disk according to the capabilities of the
fs.

Signed-off-by: Brian Foster <bfoster@redhat.com>
Reviewed-by: Dave Chinner <dchinner@redhat.com>
Signed-off-by: Dave Chinner <david@fromorbit.com>

diff --git a/fs/xfs/libxfs/xfs_format.h b/fs/xfs/libxfs/xfs_format.h
index 6b8a64e..afc5834 100644 (file)
--- a/fs/xfs/libxfs/xfs_format.h
+++ b/fs/xfs/libxfs/xfs_format.h
@@ -1223,26 +1223,54 @@ typedef __uint64_t      xfs_inofree_t;
 #define        XFS_INOBT_ALL_FREE              ((xfs_inofree_t)-1)
 #define        XFS_INOBT_MASK(i)               ((xfs_inofree_t)1 << (i))
 
+#define XFS_INOBT_HOLEMASK_FULL                0       /* holemask for full chunk */
+#define XFS_INOBT_HOLEMASK_BITS                (NBBY * sizeof(__uint16_t))
+#define XFS_INODES_PER_HOLEMASK_BIT    \
+       (XFS_INODES_PER_CHUNK / (NBBY * sizeof(__uint16_t)))
+
 static inline xfs_inofree_t xfs_inobt_maskn(int i, int n)
 {
        return ((n >= XFS_INODES_PER_CHUNK ? 0 : XFS_INOBT_MASK(n)) - 1) << i;
 }
 
 /*
- * Data record structure
+ * The on-disk inode record structure has two formats. The original "full"
+ * format uses a 4-byte freecount. The "sparse" format uses a 1-byte freecount
+ * and replaces the 3 high-order freecount bytes wth the holemask and inode
+ * count.
+ *
+ * The holemask of the sparse record format allows an inode chunk to have holes
+ * that refer to blocks not owned by the inode record. This facilitates inode
+ * allocation in the event of severe free space fragmentation.
  */
 typedef struct xfs_inobt_rec {
        __be32          ir_startino;    /* starting inode number */
-       __be32          ir_freecount;   /* count of free inodes (set bits) */
+       union {
+               struct {
+                       __be32  ir_freecount;   /* count of free inodes */
+               } f;
+               struct {
+                       __be16  ir_holemask;/* hole mask for sparse chunks */
+                       __u8    ir_count;       /* total inode count */
+                       __u8    ir_freecount;   /* count of free inodes */
+               } sp;
+       } ir_u;
        __be64          ir_free;        /* free inode mask */
 } xfs_inobt_rec_t;
 
 typedef struct xfs_inobt_rec_incore {
        xfs_agino_t     ir_startino;    /* starting inode number */
-       __int32_t       ir_freecount;   /* count of free inodes (set bits) */
+       __uint16_t      ir_holemask;    /* hole mask for sparse chunks */
+       __uint8_t       ir_count;       /* total inode count */
+       __uint8_t       ir_freecount;   /* count of free inodes (set bits) */
        xfs_inofree_t   ir_free;        /* free inode mask */
 } xfs_inobt_rec_incore_t;
 
+static inline bool xfs_inobt_issparse(uint16_t holemask)
+{
+       /* non-zero holemask represents a sparse rec. */
+       return holemask;
+}
 
 /*
  * Key structure

diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
index 269d9ca..85a477a 100644 (file)
--- a/fs/xfs/libxfs/xfs_ialloc.c
+++ b/fs/xfs/libxfs/xfs_ialloc.c
@@ -65,6 +65,8 @@ xfs_inobt_lookup(
        int                     *stat)  /* success/failure */
 {
        cur->bc_rec.i.ir_startino = ino;
+       cur->bc_rec.i.ir_holemask = 0;
+       cur->bc_rec.i.ir_count = 0;
        cur->bc_rec.i.ir_freecount = 0;
        cur->bc_rec.i.ir_free = 0;
        return xfs_btree_lookup(cur, dir, stat);
@@ -82,7 +84,14 @@ xfs_inobt_update(
        union xfs_btree_rec     rec;
 
        rec.inobt.ir_startino = cpu_to_be32(irec->ir_startino);
-       rec.inobt.ir_freecount = cpu_to_be32(irec->ir_freecount);
+       if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) {
+               rec.inobt.ir_u.sp.ir_holemask = cpu_to_be16(irec->ir_holemask);
+               rec.inobt.ir_u.sp.ir_count = irec->ir_count;
+               rec.inobt.ir_u.sp.ir_freecount = irec->ir_freecount;
+       } else {
+               /* ir_holemask/ir_count not supported on-disk */
+               rec.inobt.ir_u.f.ir_freecount = cpu_to_be32(irec->ir_freecount);
+       }
        rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
        return xfs_btree_update(cur, &rec);
 }
@@ -100,12 +109,27 @@ xfs_inobt_get_rec(
        int                     error;
 
        error = xfs_btree_get_rec(cur, &rec, stat);
-       if (!error && *stat == 1) {
-               irec->ir_startino = be32_to_cpu(rec->inobt.ir_startino);
-               irec->ir_freecount = be32_to_cpu(rec->inobt.ir_freecount);
-               irec->ir_free = be64_to_cpu(rec->inobt.ir_free);
+       if (error || *stat == 0)
+               return error;
+
+       irec->ir_startino = be32_to_cpu(rec->inobt.ir_startino);
+       if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) {
+               irec->ir_holemask = be16_to_cpu(rec->inobt.ir_u.sp.ir_holemask);
+               irec->ir_count = rec->inobt.ir_u.sp.ir_count;
+               irec->ir_freecount = rec->inobt.ir_u.sp.ir_freecount;
+       } else {
+               /*
+                * ir_holemask/ir_count not supported on-disk. Fill in hardcoded
+                * values for full inode chunks.
+                */
+               irec->ir_holemask = XFS_INOBT_HOLEMASK_FULL;
+               irec->ir_count = XFS_INODES_PER_CHUNK;
+               irec->ir_freecount =
+                               be32_to_cpu(rec->inobt.ir_u.f.ir_freecount);
        }
-       return error;
+       irec->ir_free = be64_to_cpu(rec->inobt.ir_free);
+
+       return 0;
 }
 
 /*
@@ -114,10 +138,14 @@ xfs_inobt_get_rec(
 STATIC int
 xfs_inobt_insert_rec(
        struct xfs_btree_cur    *cur,
+       __uint16_t              holemask,
+       __uint8_t               count,
        __int32_t               freecount,
        xfs_inofree_t           free,
        int                     *stat)
 {
+       cur->bc_rec.i.ir_holemask = holemask;
+       cur->bc_rec.i.ir_count = count;
        cur->bc_rec.i.ir_freecount = freecount;
        cur->bc_rec.i.ir_free = free;
        return xfs_btree_insert(cur, stat);
@@ -154,7 +182,9 @@ xfs_inobt_insert(
                }
                ASSERT(i == 0);
 
-               error = xfs_inobt_insert_rec(cur, XFS_INODES_PER_CHUNK,
+               error = xfs_inobt_insert_rec(cur, XFS_INOBT_HOLEMASK_FULL,
+                                            XFS_INODES_PER_CHUNK,
+                                            XFS_INODES_PER_CHUNK,
                                             XFS_INOBT_ALL_FREE, &i);
                if (error) {
                        xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
@@ -1609,7 +1639,9 @@ xfs_difree_finobt(
                 */
                XFS_WANT_CORRUPTED_GOTO(mp, ibtrec->ir_freecount == 1, error);
 
-               error = xfs_inobt_insert_rec(cur, ibtrec->ir_freecount,
+               error = xfs_inobt_insert_rec(cur, ibtrec->ir_holemask,
+                                            ibtrec->ir_count,
+                                            ibtrec->ir_freecount,
                                             ibtrec->ir_free, &i);
                if (error)
                        goto error;

diff --git a/fs/xfs/libxfs/xfs_ialloc_btree.c b/fs/xfs/libxfs/xfs_ialloc_btree.c
index 964c465..b95aac5 100644 (file)
--- a/fs/xfs/libxfs/xfs_ialloc_btree.c
+++ b/fs/xfs/libxfs/xfs_ialloc_btree.c
@@ -167,7 +167,16 @@ xfs_inobt_init_rec_from_cur(
        union xfs_btree_rec     *rec)
 {
        rec->inobt.ir_startino = cpu_to_be32(cur->bc_rec.i.ir_startino);
-       rec->inobt.ir_freecount = cpu_to_be32(cur->bc_rec.i.ir_freecount);
+       if (xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb)) {
+               rec->inobt.ir_u.sp.ir_holemask =
+                                       cpu_to_be16(cur->bc_rec.i.ir_holemask);
+               rec->inobt.ir_u.sp.ir_count = cur->bc_rec.i.ir_count;
+               rec->inobt.ir_u.sp.ir_freecount = cur->bc_rec.i.ir_freecount;
+       } else {
+               /* ir_holemask/ir_count not supported on-disk */
+               rec->inobt.ir_u.f.ir_freecount =
+                                       cpu_to_be32(cur->bc_rec.i.ir_freecount);
+       }
        rec->inobt.ir_free = cpu_to_be64(cur->bc_rec.i.ir_free);
 }