xfs: sparse inode chunks

Add sb_spinoalignmt to the superblock to specify sparse inode chunk alignment. This also currently represents the minimum allowable sparse chunk allocation size.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_format.h | 6 +++---
 fs/xfs/libxfs/xfs_sb.c     | 4 ++--
 2 files changed, 5 insertions(+), 5 deletions(-)

fs/xfs/libxfs/xfs_format.h +0 -0

index 8eb7189..051c24d 100644

Quoted 17 lines · Brian Foster

Add sb_spinoalignmt to the superblock to specify sparse inode chunk alignment. This also currently represents the minimum allowable sparse chunk allocation size.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_format.h | 6 +++---
 fs/xfs/libxfs/xfs_sb.c     | 4 ++--
 2 files changed, 5 insertions(+), 5 deletions(-)

fs/xfs/libxfs/xfs_format.h +0 -0

index 8eb7189..051c24d 100644
@@ -170,7 +170,7 @@ typedef struct xfs_sb {
 	__uint32_t	sb_features_log_incompat;
 

fs/xfs/libxfs/xfs_format.h typedef struct xfs_sb { · line 173

Quoted 3 lines

fs/xfs/libxfs/xfs_format.h +1 -1

 	__uint32_t	sb_crc;		/* superblock crc */
-	__uint32_t	sb_pad;
+	xfs_extlen_t	sb_spinoalignmt;/* sparse inode chunk alignment */

That's a mounthful. sb_spino_align is a bit easier to read, IMO.

fs/xfs/libxfs/xfs_format.h typedef enum { · line 288

Quoted 9 lines

fs/xfs/libxfs/xfs_format.h +1 -1

@@ -282,7 +282,7 @@ typedef enum {
 	XFS_SBS_LOGSECTLOG, XFS_SBS_LOGSECTSIZE, XFS_SBS_LOGSUNIT,
 	XFS_SBS_FEATURES2, XFS_SBS_BAD_FEATURES2, XFS_SBS_FEATURES_COMPAT,
 	XFS_SBS_FEATURES_RO_COMPAT, XFS_SBS_FEATURES_INCOMPAT,
-	XFS_SBS_FEATURES_LOG_INCOMPAT, XFS_SBS_CRC, XFS_SBS_PAD,
+	XFS_SBS_FEATURES_LOG_INCOMPAT, XFS_SBS_CRC, XFS_SBS_SPINOALIGNMT,
 	XFS_SBS_PQUOTINO, XFS_SBS_LSN,
 	XFS_SBS_FIELDCOUNT
 } xfs_sb_field_t;

These are gone in the for-next tree.

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Quoted 18 lines · Dave Chinner

Quoted 17 lines · Brian Foster

Add sb_spinoalignmt to the superblock to specify sparse inode chunk alignment. This also currently represents the minimum allowable sparse chunk allocation size.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_format.h | 6 +++---
 fs/xfs/libxfs/xfs_sb.c     | 4 ++--
 2 files changed, 5 insertions(+), 5 deletions(-)

fs/xfs/libxfs/xfs_format.h +0 -0

index 8eb7189..051c24d 100644
@@ -170,7 +170,7 @@ typedef struct xfs_sb {
 	__uint32_t	sb_features_log_incompat;
 

Quoted 6 lines

fs/xfs/libxfs/xfs_format.h typedef struct xfs_sb { · line 173

Quoted 3 lines

fs/xfs/libxfs/xfs_format.h +1 -1

 	__uint32_t	sb_crc;		/* superblock crc */
-	__uint32_t	sb_pad;
+	xfs_extlen_t	sb_spinoalignmt;/* sparse inode chunk alignment */

That's a mounthful. sb_spino_align is a bit easier to read, IMO.

Ok.

Quoted 12 lines

fs/xfs/libxfs/xfs_format.h typedef enum { · line 288

Quoted 9 lines

fs/xfs/libxfs/xfs_format.h +1 -1

@@ -282,7 +282,7 @@ typedef enum {
 	XFS_SBS_LOGSECTLOG, XFS_SBS_LOGSECTSIZE, XFS_SBS_LOGSUNIT,
 	XFS_SBS_FEATURES2, XFS_SBS_BAD_FEATURES2, XFS_SBS_FEATURES_COMPAT,
 	XFS_SBS_FEATURES_RO_COMPAT, XFS_SBS_FEATURES_INCOMPAT,
-	XFS_SBS_FEATURES_LOG_INCOMPAT, XFS_SBS_CRC, XFS_SBS_PAD,
+	XFS_SBS_FEATURES_LOG_INCOMPAT, XFS_SBS_CRC, XFS_SBS_SPINOALIGNMT,
 	XFS_SBS_PQUOTINO, XFS_SBS_LSN,
 	XFS_SBS_FIELDCOUNT
 } xfs_sb_field_t;

These are gone in the for-next tree.

The per-field logging stuff is gone... this apparently still exists. It looks like it goes away as part of the icsb rework so this will drop naturally whenever that goes in.

The sparse inode chunks feature uses the helper function to enable the allocation of sparse inode chunks. The incompatible feature bit is set on disk at mkfs time to prevent mount from unsupported kernels.

Also, enforce the inode alignment requirements required for sparse inode chunks at mount time. When enabled, full inode chunks (and all inode record) alignment is increased from cluster size to inode chunk size. Sparse inode alignment must match the cluster size of the fs. Both superblock alignment fields are set as such by mkfs when sparse inode support is enabled.

Finally, warn that sparse inode chunks is an experimental feature until further notice.

Signed-off-by Brian Foster <[email protected]>

fs/xfs/libxfs/xfs_sb.c +1 -0

@@ -182,6 +182,28 @@ xfs_mount_validate_sb(
 			return -EFSCORRUPTED;
 	}
 
+	/*

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

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 both fields are initialized to zero to maintain backwards compatibility with existing filesystems (e.g., the higher order bytes of freecount are always 0). Tracking holes means that the hole mask is initialized to zero and thus remains "valid" in accordance with a non-sparse inode fs when no sparse chunks are physically allocated. Update the inode record management functions to handle the new fields and initialize to zero.

[XXX: The count field breaks backwards compatibility with !sparseinode fs. Should we reconsider the addition of total count or the idea of converting back and forth between sparse inode fs with a feature bit?]

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_format.h       |  8 ++++++--
 fs/xfs/libxfs/xfs_ialloc.c       | 12 ++++++++++--
 fs/xfs/libxfs/xfs_ialloc_btree.c |  4 +++-
 3 files changed, 19 insertions(+), 5 deletions(-)

fs/xfs/libxfs/xfs_format.h +0 -0

index 26e5d92..6c2f1be 100644

fs/xfs/libxfs/xfs_ialloc.c +2 -0

index 6f2153e..32fdb7c 100644
@@ -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);

Quoted 45 lines · Brian Foster

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

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 both fields are initialized to zero to maintain backwards compatibility with existing filesystems (e.g., the higher order bytes of freecount are always 0). Tracking holes means that the hole mask is initialized to zero and thus remains "valid" in accordance with a non-sparse inode fs when no sparse chunks are physically allocated. Update the inode record management functions to handle the new fields and initialize to zero.

[XXX: The count field breaks backwards compatibility with !sparseinode fs. Should we reconsider the addition of total count or the idea of converting back and forth between sparse inode fs with a feature bit?]

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_format.h       |  8 ++++++--
 fs/xfs/libxfs/xfs_ialloc.c       | 12 ++++++++++--
 fs/xfs/libxfs/xfs_ialloc_btree.c |  4 +++-
 3 files changed, 19 insertions(+), 5 deletions(-)

fs/xfs/libxfs/xfs_format.h +0 -0

index 26e5d92..6c2f1be 100644

fs/xfs/libxfs/xfs_format.h static inline xfs_inofree_t xfs_inobt_maskn(int i, int n) · line 1302

Quoted 9 lines

fs/xfs/libxfs/xfs_format.h +3 -1

@@ -1295,13 +1295,17 @@ static inline xfs_inofree_t xfs_inobt_maskn(int i, int n)
  */
 typedef struct xfs_inobt_rec {
 	__be32		ir_startino;	/* starting inode number */
-	__be32		ir_freecount;	/* count of free inodes (set bits) */
+	__be16		ir_holemask;	/* hole mask for sparse chunks */
+	__u8		ir_count;	/* total inode count */
+	__u8		ir_freecount;	/* count of free inodes (set bits) */
 	__be64		ir_free;	/* free inode mask */
 } xfs_inobt_rec_t;

I think I'd prefer to see a union here so that we explicitly state what the difference in the on-disk format is. i.e. similar to how we express the difference in long and short btree block headers.

struct xfs_inobt_rec {
	__be32		ir_startino;	/* starting inode number */
	__be32		ir_freecount;	/* count of free inodes (set bits) */
	union {
		struct {
			__be32	ir_freecount;
		} f;
		struct {
			__be16	ir_holemask;	/* hole mask for sparse chunks */
			__u8	ir_count;	/* total inode count */
			__u8	ir_freecount;	/* count of free inodes (set bits) */
		} sp;
	}
	__be64		ir_free;	/* free inode mask */
};

This will prevent us from using the wrong method of referencing/modifying the record because we now need to be explicit in how we modify it...

Quoted 5 lines

fs/xfs/libxfs/xfs_format.h +2 -1

 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 */

fs/xfs/libxfs/xfs_format.h static inline xfs_inofree_t xfs_inobt_maskn(int i, int n) · line 1310

Quoted 3 lines

fs/xfs/libxfs/xfs_format.h +1 -0

+	__uint8_t	ir_freecount;	/* count of free inodes (set bits) */
 	xfs_inofree_t	ir_free;	/* free inode mask */
 } xfs_inobt_rec_incore_t;

Though this is still fine - it doesn't need to explicitly follow the on-disk format structure, but it would be nice to be explicit on conversion to disk format records what we are actually using from this record.

Quoted 16 lines

fs/xfs/libxfs/xfs_ialloc.c +2 -0

index 6f2153e..32fdb7c 100644
@@ -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,9 @@ xfs_inobt_update(
 	union xfs_btree_rec	rec;
 

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_update( · line 92

Quoted 8 lines

fs/xfs/libxfs/xfs_ialloc.c +3 -1

 	rec.inobt.ir_startino = cpu_to_be32(irec->ir_startino);
-	rec.inobt.ir_freecount = cpu_to_be32(irec->ir_freecount);
+	rec.inobt.ir_holemask = cpu_to_be16(irec->ir_holemask);
+	rec.inobt.ir_count = irec->ir_count;
+	rec.inobt.ir_freecount = irec->ir_freecount;
 	rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
 	return xfs_btree_update(cur, &rec);
 }

Hmmm - perhaps a similar set of helpers for sparse inode enabled filesystems

Quoted 4 lines

fs/xfs/libxfs/xfs_ialloc.c +0 -0

@@ -118,6 +124,8 @@ xfs_inobt_insert_rec(
 	xfs_inofree_t		free,
 	int			*stat)
 {

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_insert_rec( · line 131

Quoted 5 lines

fs/xfs/libxfs/xfs_ialloc.c +2 -0

+	cur->bc_rec.i.ir_holemask = 0;
+	cur->bc_rec.i.ir_count = 0; /* zero for backwards compatibility */
 	cur->bc_rec.i.ir_freecount = freecount;
 	cur->bc_rec.i.ir_free = free;
 	return xfs_btree_insert(cur, stat);

That would make this sort of thing very clear - this doesn't look like it would work for a sparse chunk record...

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Quoted 76 lines · Dave Chinner

Quoted 45 lines · Brian Foster

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

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 both fields are initialized to zero to maintain backwards compatibility with existing filesystems (e.g., the higher order bytes of freecount are always 0). Tracking holes means that the hole mask is initialized to zero and thus remains "valid" in accordance with a non-sparse inode fs when no sparse chunks are physically allocated. Update the inode record management functions to handle the new fields and initialize to zero.

[XXX: The count field breaks backwards compatibility with !sparseinode fs. Should we reconsider the addition of total count or the idea of converting back and forth between sparse inode fs with a feature bit?]

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_format.h       |  8 ++++++--
 fs/xfs/libxfs/xfs_ialloc.c       | 12 ++++++++++--
 fs/xfs/libxfs/xfs_ialloc_btree.c |  4 +++-
 3 files changed, 19 insertions(+), 5 deletions(-)

fs/xfs/libxfs/xfs_format.h +0 -0

index 26e5d92..6c2f1be 100644

fs/xfs/libxfs/xfs_format.h static inline xfs_inofree_t xfs_inobt_maskn(int i, int n) · line 1302

Quoted 9 lines

fs/xfs/libxfs/xfs_format.h +3 -1

@@ -1295,13 +1295,17 @@ static inline xfs_inofree_t xfs_inobt_maskn(int i, int n)
  */
 typedef struct xfs_inobt_rec {
 	__be32		ir_startino;	/* starting inode number */
-	__be32		ir_freecount;	/* count of free inodes (set bits) */
+	__be16		ir_holemask;	/* hole mask for sparse chunks */
+	__u8		ir_count;	/* total inode count */
+	__u8		ir_freecount;	/* count of free inodes (set bits) */
 	__be64		ir_free;	/* free inode mask */
 } xfs_inobt_rec_t;

I think I'd prefer to see a union here so that we explicitly state what the difference in the on-disk format is. i.e. similar to how we express the difference in long and short btree block headers.

struct xfs_inobt_rec {
	__be32		ir_startino;	/* starting inode number */
	__be32		ir_freecount;	/* count of free inodes (set bits) */
	union {
		struct {
			__be32	ir_freecount;
		} f;
		struct {
			__be16	ir_holemask;	/* hole mask for sparse chunks */
			__u8	ir_count;	/* total inode count */
			__u8	ir_freecount;	/* count of free inodes (set bits) */
		} sp;
	}
	__be64		ir_free;	/* free inode mask */
};

Quoted 4 lines

This will prevent us from using the wrong method of referencing/modifying the record because we now need to be explicit in how we modify it...

I agree in principle. This is definitely explicit in that there are two variants of this structure that must be handled in a particular way. That said, 'sparse' and 'full' aren't quite logical differentiators given that we now have the ir_count field and that it is used whenever sparse inode support is enabled. In other words, a sparse enabled fs' always uses the 'sp' variant of the inobt record, regardless of whether the record happens to sparse.

Quoted 15 lines

fs/xfs/libxfs/xfs_format.h xfs_inobt_update( · line 92

Quoted 11 lines

fs/xfs/libxfs/xfs_format.h +3 -1

@@ -82,7 +84,9 @@ 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);
+	rec.inobt.ir_holemask = cpu_to_be16(irec->ir_holemask);
+	rec.inobt.ir_count = irec->ir_count;
+	rec.inobt.ir_freecount = irec->ir_freecount;
 	rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
 	return xfs_btree_update(cur, &rec);
 }

Hmmm - perhaps a similar set of helpers for sparse inode enabled filesystems

We could do that for the insert/update helpers, but note again the separate helpers would not split along the lines of sparse vs full chunks. Even if we were to change the design such that they do, that would have th effect of complicating some of the subsequent code. For

example, the merge/update code currently has no reason to care about whether it has created a full chunk out of multiple sparse chunks. This would require more code to make that distinction simply to pick the correct api, for something that can easily be done with a simple generic helper. The same goes for things like the finobt, where now lookup/update/insert has to make distinctions depending on the type of inode record.

An alternate approach could be to stick with the generic helpers, but try and tweak them to use the appropriate on-disk format depending on the record. Then again, how can one really identify one from the other in the lookup or _get_rec() scenarios?

Quoted 4 lines

Quoted 4 lines

fs/xfs/libxfs/xfs_format.h +0 -0

@@ -118,6 +124,8 @@ xfs_inobt_insert_rec(
 	xfs_inofree_t		free,
 	int			*stat)
 {

Quoted 8 lines

fs/xfs/libxfs/xfs_format.h xfs_inobt_insert_rec( · line 131

Quoted 5 lines

fs/xfs/libxfs/xfs_format.h +2 -0

+	cur->bc_rec.i.ir_holemask = 0;
+	cur->bc_rec.i.ir_count = 0; /* zero for backwards compatibility */
 	cur->bc_rec.i.ir_freecount = freecount;
 	cur->bc_rec.i.ir_free = free;
 	return xfs_btree_insert(cur, stat);

That would make this sort of thing very clear - this doesn't look like it would work for a sparse chunk record...

Right... but this is just a plumbing patch and effectively a placeholder for the subsequent patches that implement the mechanism. I suppose the api could have been pulled back sooner into this patch, but I'd rather not reshuffle things just for that intermediate state. That context probably wasn't quite clear to me at the time.

Before I go one way or another here with regard to the on-disk data structure, care to take a look at the subsequent patch(es) that use these helpers? Patch 10 in particular pretty much sums up how these helpers are used for sparse inode record management.

FWIW, comments on the generic bitmap stuff is also appreciated as that's another area I'm not totally convinved is done right. :)

Quoted 82 lines · Brian Foster

Quoted 76 lines · Dave Chinner

Quoted 45 lines · Brian Foster

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

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 both fields are initialized to zero to maintain backwards compatibility with existing filesystems (e.g., the higher order bytes of freecount are always 0). Tracking holes means that the hole mask is initialized to zero and thus remains "valid" in accordance with a non-sparse inode fs when no sparse chunks are physically allocated. Update the inode record management functions to handle the new fields and initialize to zero.

[XXX: The count field breaks backwards compatibility with !sparseinode fs. Should we reconsider the addition of total count or the idea of converting back and forth between sparse inode fs with a feature bit?]

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_format.h       |  8 ++++++--
 fs/xfs/libxfs/xfs_ialloc.c       | 12 ++++++++++--
 fs/xfs/libxfs/xfs_ialloc_btree.c |  4 +++-
 3 files changed, 19 insertions(+), 5 deletions(-)

fs/xfs/libxfs/xfs_format.h +0 -0

index 26e5d92..6c2f1be 100644

fs/xfs/libxfs/xfs_format.h static inline xfs_inofree_t xfs_inobt_maskn(int i, int n) · line 1302

Quoted 9 lines

fs/xfs/libxfs/xfs_format.h +3 -1

@@ -1295,13 +1295,17 @@ static inline xfs_inofree_t xfs_inobt_maskn(int i, int n)
  */
 typedef struct xfs_inobt_rec {
 	__be32		ir_startino;	/* starting inode number */
-	__be32		ir_freecount;	/* count of free inodes (set bits) */
+	__be16		ir_holemask;	/* hole mask for sparse chunks */
+	__u8		ir_count;	/* total inode count */
+	__u8		ir_freecount;	/* count of free inodes (set bits) */
 	__be64		ir_free;	/* free inode mask */
 } xfs_inobt_rec_t;

I think I'd prefer to see a union here so that we explicitly state what the difference in the on-disk format is. i.e. similar to how we express the difference in long and short btree block headers.

struct xfs_inobt_rec {
	__be32		ir_startino;	/* starting inode number */
	__be32		ir_freecount;	/* count of free inodes (set bits) */
	union {
		struct {
			__be32	ir_freecount;
		} f;
		struct {
			__be16	ir_holemask;	/* hole mask for sparse chunks */
			__u8	ir_count;	/* total inode count */
			__u8	ir_freecount;	/* count of free inodes (set bits) */
		} sp;
	}
	__be64		ir_free;	/* free inode mask */
};

Quoted 4 lines

This will prevent us from using the wrong method of referencing/modifying the record because we now need to be explicit in how we modify it...

Quoted 7 lines

I agree in principle. This is definitely explicit in that there are two variants of this structure that must be handled in a particular way. That said, 'sparse' and 'full' aren't quite logical differentiators given that we now have the ir_count field and that it is used whenever sparse inode support is enabled. In other words, a sparse enabled fs' always uses the 'sp' variant of the inobt record, regardless of whether the record happens to sparse.

Sure, that's fine for the in memory code, but we've always been explicit about the disk format and marshalling to/from it, especially in the cases where the structure on disk can have multiple formats.

Quoted 16 lines

Quoted 15 lines

fs/xfs/libxfs/xfs_format.h xfs_inobt_update( · line 92

Quoted 11 lines

fs/xfs/libxfs/xfs_format.h +3 -1

@@ -82,7 +84,9 @@ 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);
+	rec.inobt.ir_holemask = cpu_to_be16(irec->ir_holemask);
+	rec.inobt.ir_count = irec->ir_count;
+	rec.inobt.ir_freecount = irec->ir_freecount;
 	rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
 	return xfs_btree_update(cur, &rec);
 }

Hmmm - perhaps a similar set of helpers for sparse inode enabled filesystems

Quoted 4 lines

We could do that for the insert/update helpers, but note again the separate helpers would not split along the lines of sparse vs full chunks. Even if we were to change the design such that they do, that would have th effect of complicating some of the subsequent code. For

I suspect it might, but I really don't like the idea of writing fields that don't actually exist (and hence are always zero) in the on-disk format to disk. See, for example, the v5 superblock field writes are conditional in xfs_sb_to_disk, the v3 inode field writes are conditional in xfs_dinode_to_disk, etc.

Quoted 7 lines

example, the merge/update code currently has no reason to care about whether it has created a full chunk out of multiple sparse chunks. This would require more code to make that distinction simply to pick the correct api, for something that can easily be done with a simple generic helper. The same goes for things like the finobt, where now lookup/update/insert has to make distinctions depending on the type of inode record.

That was another thing that wasn't clear to me - does the finobt record format change on disk? I don't think it does, as it only holds a free count and a free inode bitmask, so it doesn't care which bits of the chunk are allocated or not....

Quoted 4 lines

An alternate approach could be to stick with the generic helpers, but try and tweak them to use the appropriate on-disk format depending on the record. Then again, how can one really identify one from the other in the lookup or _get_rec() scenarios?

Solving these problem was exactly why I suggested different helpers
- the btree ops structure that is chosen for the cursor is in a place where we know what format we are using, and that avoids needing "if (xfs_sb_version...)" checks in the helpers to determine what format we need to use.

Quoted 19 lines

Quoted 4 lines

Quoted 4 lines

fs/xfs/libxfs/xfs_format.h +0 -0

@@ -118,6 +124,8 @@ xfs_inobt_insert_rec(
 	xfs_inofree_t		free,
 	int			*stat)
 {

Quoted 8 lines

fs/xfs/libxfs/xfs_format.h xfs_inobt_insert_rec( · line 131

Quoted 5 lines

fs/xfs/libxfs/xfs_format.h +2 -0

+	cur->bc_rec.i.ir_holemask = 0;
+	cur->bc_rec.i.ir_count = 0; /* zero for backwards compatibility */
 	cur->bc_rec.i.ir_freecount = freecount;
 	cur->bc_rec.i.ir_free = free;
 	return xfs_btree_insert(cur, stat);

That would make this sort of thing very clear - this doesn't look like it would work for a sparse chunk record...

Right... but this is just a plumbing patch and effectively a placeholder for the subsequent patches that implement the mechanism. I suppose the api could have been pulled back sooner into this patch, but I'd rather not reshuffle things just for that intermediate state. That context probably wasn't quite clear to me at the time.

Quoted 4 lines

Before I go one way or another here with regard to the on-disk data structure, care to take a look at the subsequent patch(es) that use these helpers? Patch 10 in particular pretty much sums up how these helpers are used for sparse inode record management.

Yup, I'll get to it.

Quoted 2 lines

FWIW, comments on the generic bitmap stuff is also appreciated as that's another area I'm not totally convinved is done right. :)

Why use the generic bitmap stuff rather than the existing XFS code? If that's just an in-memory change to the free mask processing, then it can be done separately to the sparse inode functionality, and probably should be done first in the series....

Signature · 2 lines

Dave Chinner
[email protected]

Quoted 22 lines · Dave Chinner

Quoted 16 lines · Brian Foster

Quoted 15 lines

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_update( · line 92

Quoted 11 lines

fs/xfs/libxfs/xfs_ialloc.c +3 -1

@@ -82,7 +84,9 @@ 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);
+	rec.inobt.ir_holemask = cpu_to_be16(irec->ir_holemask);
+	rec.inobt.ir_count = irec->ir_count;
+	rec.inobt.ir_freecount = irec->ir_freecount;
 	rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
 	return xfs_btree_update(cur, &rec);
 }

Hmmm - perhaps a similar set of helpers for sparse inode enabled filesystems

Quoted 4 lines

We could do that for the insert/update helpers, but note again the separate helpers would not split along the lines of sparse vs full chunks. Even if we were to change the design such that they do, that would have th effect of complicating some of the subsequent code. For

Quoted 6 lines

I suspect it might, but I really don't like the idea of writing fields that don't actually exist (and hence are always zero) in the on-disk format to disk. See, for example, the v5 superblock field writes are conditional in xfs_sb_to_disk, the v3 inode field writes are conditional in xfs_dinode_to_disk, etc.

Indeed. The point here is just that a v1/v2 differentiation might be more relevant than full vs. sparse. As it is, a sparse inode enabled fs uses all of the fields (e.g., ir_count == 64 on a full chunk). So this is more about providing clean backwards compatibility than deciding between two different "allocation types," so to speak.

Beyond that, I'm more just probing for a clean use of the new on-disk format distinction. The references above actually use the associated feature checks in a single helper as opposed to a separate one, and that seems a bit more clean an approach to me.

Quoted 8 lines

Quoted 7 lines

example, the merge/update code currently has no reason to care about whether it has created a full chunk out of multiple sparse chunks. This would require more code to make that distinction simply to pick the correct api, for something that can easily be done with a simple generic helper. The same goes for things like the finobt, where now lookup/update/insert has to make distinctions depending on the type of inode record.

Quoted 5 lines

That was another thing that wasn't clear to me - does the finobt record format change on disk? I don't think it does, as it only holds a free count and a free inode bitmask, so it doesn't care which bits of the chunk are allocated or not....

No, it shouldn't change the format. But if we have a separate set of inobt helpers, it has to use one or the other depending on the type of record holding the inode that is freed or allocated.

Quoted 11 lines

Quoted 4 lines

An alternate approach could be to stick with the generic helpers, but try and tweak them to use the appropriate on-disk format depending on the record. Then again, how can one really identify one from the other in the lookup or _get_rec() scenarios?

Solving these problem was exactly why I suggested different helpers
- the btree ops structure that is chosen for the cursor is in a place where we know what format we are using, and that avoids needing "if (xfs_sb_version...)" checks in the helpers to determine what format we need to use.

Hmm, I'm not sure I follow the train of thought here. The examples above use exactly that kind of logic within the helper. Further, some of the

Quoted 5 lines

Quoted 4 lines

Before I go one way or another here with regard to the on-disk data structure, care to take a look at the subsequent patch(es) that use these helpers? Patch 10 in particular pretty much sums up how these helpers are used for sparse inode record management.

Quoted 2 lines

Yup, I'll get to it.

Thanks. I've made a quick pass and most of it makes sense save some of the helper business we're discussing here. I can start into some of the higher level refactoring, try to incorporate the on-disk record format union as clean as I can and we can move forward using the code of the next version, if that's easier. ;)

Quoted 8 lines

Quoted 2 lines

FWIW, comments on the generic bitmap stuff is also appreciated as that's another area I'm not totally convinved is done right. :)

Why use the generic bitmap stuff rather than the existing XFS code? If that's just an in-memory change to the free mask processing, then it can be done separately to the sparse inode functionality, and probably should be done first in the series....

http://oss.sgi.com/archives/xfs/2014-07/msg00380.html

Last comment in that mail. ;) To be honest, I liked the original code better because it didn't require the bitmap_to_u64() helper hack and

ports directly to userspace (so far I've managed to get away with dropping that stuff entirely in userspace). Alternatively, I've done significantly more testing with the latest code than the initial version so I'd rather not change it back unless a real need arises.

Quoted 36 lines · Brian Foster

Quoted 22 lines · Dave Chinner

Quoted 16 lines · Brian Foster

Quoted 15 lines

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_update( · line 92

Quoted 11 lines

fs/xfs/libxfs/xfs_ialloc.c +3 -1

@@ -82,7 +84,9 @@ 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);
+	rec.inobt.ir_holemask = cpu_to_be16(irec->ir_holemask);
+	rec.inobt.ir_count = irec->ir_count;
+	rec.inobt.ir_freecount = irec->ir_freecount;
 	rec.inobt.ir_free = cpu_to_be64(irec->ir_free);
 	return xfs_btree_update(cur, &rec);
 }

Hmmm - perhaps a similar set of helpers for sparse inode enabled filesystems

Quoted 4 lines

We could do that for the insert/update helpers, but note again the separate helpers would not split along the lines of sparse vs full chunks. Even if we were to change the design such that they do, that would have th effect of complicating some of the subsequent code. For

Quoted 6 lines

I suspect it might, but I really don't like the idea of writing fields that don't actually exist (and hence are always zero) in the on-disk format to disk. See, for example, the v5 superblock field writes are conditional in xfs_sb_to_disk, the v3 inode field writes are conditional in xfs_dinode_to_disk, etc.

Indeed. The point here is just that a v1/v2 differentiation might be more relevant than full vs. sparse. As it is, a sparse inode enabled fs uses all of the fields (e.g., ir_count == 64 on a full chunk). So this is more about providing clean backwards compatibility than deciding between two different "allocation types," so to speak.

Quoted 4 lines

Beyond that, I'm more just probing for a clean use of the new on-disk format distinction. The references above actually use the associated feature checks in a single helper as opposed to a separate one, and that seems a bit more clean an approach to me.

BUt that's because those object have enough information internally to determine what the correct action to take is. An inobt record doesn't have the internal information to say whay format it is supposed to be in. Hence we need to enforce the use of the correct marshalling logic in some way...

Quoted 14 lines

Quoted 8 lines

Quoted 7 lines

example, the merge/update code currently has no reason to care about whether it has created a full chunk out of multiple sparse chunks. This would require more code to make that distinction simply to pick the correct api, for something that can easily be done with a simple generic helper. The same goes for things like the finobt, where now lookup/update/insert has to make distinctions depending on the type of inode record.

Quoted 5 lines

That was another thing that wasn't clear to me - does the finobt record format change on disk? I don't think it does, as it only holds a free count and a free inode bitmask, so it doesn't care which bits of the chunk are allocated or not....

Quoted 3 lines

No, it shouldn't change the format. But if we have a separate set of inobt helpers, it has to use one or the other depending on the type of record holding the inode that is freed or allocated.

Ok, so we now have 3 instances of inode btrees that use the current format, and one that uses the new sparse record format. (i.e. existing inobt, existing finobt and sparse inode enable finobt vs sparse inode inobt). That really, to me, says we need clear demarcation....

Quoted 12 lines

Quoted 11 lines

Quoted 4 lines

An alternate approach could be to stick with the generic helpers, but try and tweak them to use the appropriate on-disk format depending on the record. Then again, how can one really identify one from the other in the lookup or _get_rec() scenarios?

Solving these problem was exactly why I suggested different helpers
- the btree ops structure that is chosen for the cursor is in a place where we know what format we are using, and that avoids needing "if (xfs_sb_version...)" checks in the helpers to determine what format we need to use.

Quoted 2 lines

Hmm, I'm not sure I follow the train of thought here. The examples above use exactly that kind of logic within the helper. Further, some of the

They use internal object state (i.e. inode version number, superblock flag field in sb being translated) to make that decision. the inobt changes use external structure state to do the conversion...

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

Before I go one way or another here with regard to the on-disk data structure, care to take a look at the subsequent patch(es) that use these helpers? Patch 10 in particular pretty much sums up how these helpers are used for sparse inode record management.

Quoted 8 lines

Quoted 2 lines

Yup, I'll get to it.

Thanks. I've made a quick pass and most of it makes sense save some of the helper business we're discussing here. I can start into some of the higher level refactoring, try to incorporate the on-disk record format union as clean as I can and we can move forward using the code of the next version, if that's easier. ;)

Yup, that's fine - refactoring the code might make a difference ;)

Quoted 9 lines

Quoted 8 lines

Quoted 2 lines

FWIW, comments on the generic bitmap stuff is also appreciated as that's another area I'm not totally convinved is done right. :)

Why use the generic bitmap stuff rather than the existing XFS code? If that's just an in-memory change to the free mask processing, then it can be done separately to the sparse inode functionality, and probably should be done first in the series....

Quoted 4 lines

http://oss.sgi.com/archives/xfs/2014-07/msg00380.html

Last comment in that mail. ;) To be honest, I liked the original code better because it didn't require the bitmap_to_u64() helper hack and

I didn't realise there were arch-specific warts in the generic bitmap code.

Quoted 4 lines

ports directly to userspace (so far I've managed to get away with dropping that stuff entirely in userspace). Alternatively, I've done significantly more testing with the latest code than the initial version so I'd rather not change it back unless a real need arises.

Well, either way I'd like to avoid nasty conversions if it can be avoided. Perhaps look at the in-memory bitmaps being held in LE format (i.e. __le64) and using the primitives in include/asm-generic/bitops/le.h to manipulate them (i.e find_next_zero_bit_le() and friends)? Maybe that would avoid all the problems of architectural layout of the bitmap fields and hence make conversion simple (i.e. just a le64_to_cpu() call?)

Cheers,

Dave.

Signature · 7 lines

Dave Chinner
[email protected]

_______________________________________________
xfs mailing list
[email protected]
http://oss.sgi.com/mailman/listinfo/xfs

Recovery of icreate transactions assumes hardcoded values for the inode count and chunk length.

Sparse inode chunks are allocated in units of m_ialloc_min_blks. Update the icreate validity checks to allow for appropriately sized inode chunks and verify the inode count matches what is expected based on the extent length rather than assuming a hardcoded count.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/xfs_log_recover.c | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

fs/xfs/xfs_log_recover.c +0 -3

index ecc73d5..5a5ee20 100644
@@ -3068,12 +3068,19 @@ xlog_recover_do_icreate_pass2(
 		return -EINVAL;
 	}
 
-	/* existing allocation is fixed value */
-	ASSERT(count == mp->m_ialloc_inos);
-	ASSERT(length == mp->m_ialloc_blks);

Quoted 31 lines · Brian Foster

Recovery of icreate transactions assumes hardcoded values for the inode count and chunk length.

Sparse inode chunks are allocated in units of m_ialloc_min_blks. Update the icreate validity checks to allow for appropriately sized inode chunks and verify the inode count matches what is expected based on the extent length rather than assuming a hardcoded count.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/xfs_log_recover.c | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

fs/xfs/xfs_log_recover.c +4 -6

index ecc73d5..5a5ee20 100644
@@ -3068,12 +3068,19 @@ xlog_recover_do_icreate_pass2(
 		return -EINVAL;
 	}
 
-	/* existing allocation is fixed value */
-	ASSERT(count == mp->m_ialloc_inos);
-	ASSERT(length == mp->m_ialloc_blks);
-	if (count != mp->m_ialloc_inos ||
-	     length != mp->m_ialloc_blks) {
-		xfs_warn(log->l_mp, "xlog_recover_do_icreate_trans: bad count 2");
+	/* inode chunk is either full or sparse */
+	if (length != mp->m_ialloc_blks &&
+	    length != mp->m_ialloc_min_blks) {
+		xfs_warn(log->l_mp,

fs/xfs/xfs_log_recover.c xlog_recover_do_icreate_pass2( · line 3077

Quoted 3 lines

fs/xfs/xfs_log_recover.c +3 -0

+			 "%s: unsupported chunk length", __FUNCTION__);
+		return -EINVAL;
+	}

Hmmm - this would prevent recovery of sparse inode chunk allocation in multiples of mp->m_ialloc_min_blks, right? Surely we can allow any sub-chunk extent size to be allocated as long as alignment and size restrictions are met?

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

The inobt record holemask field is a condensed data type designed to fit into the existing on-disk record and is zero based (allocated regions are set to 0, sparse regions are set to 1) to provide backwards compatibility. This makes the type somewhat complex for use in higher level inode manipulations such as individual inode allocation, etc.

Rather than foist the complexity of dealing with this field to every bit of logic that requires inode granular information, create the xfs_inobt_ialloc_bitmap() helper to convert the holemask to an inode allocation bitmap. The inode allocation bitmap is inode granularity similar to the inobt record free mask and indicates which inodes of the chunk are physically allocated on disk, irrespective of whether the inode is considered allocated or free by the filesystem. The generic bitmap type requires the use of generic kernel bitmap APIs.

The bitmap_to_u64() helper is provided to convert the bitmap back to a native 64-bit type (for native bitwise operations). This is required because the generic bitmap code represents a bitmap as an array of unsigned long in a little endian style (though each array value is cpu order). To ensure compatibility with various word sizes and endianness', bitmap_to_u64() exports the bitmap to little endian and swaps back to cpu byte order.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_ialloc.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)

fs/xfs/libxfs/xfs_ialloc.c +0 -0

index 72ade0e..fc001d9 100644

fs/xfs/libxfs/xfs_ialloc.c +8 -0

 /*
  * Allocation group level functions.

@@ -739,6 +741,73 @@ xfs_ialloc_get_rec(
 	return 0;
 }
 
+static inline uint64_t
+bitmap_to_u64(
+	const unsigned long	*bitmap,
+	int			nbits)
+{
+	__le64			lebitmap;
+
+	ASSERT(nbits <= 64);

fs/xfs/libxfs/xfs_ialloc.c +7 -0

+ */
+STATIC void
+xfs_inobt_ialloc_bitmap(
+	unsigned long			*allocbmap,
+	struct xfs_inobt_rec_incore	*rec)
+{
+	int				nextbit;

Quoted 36 lines · Brian Foster

The inobt record holemask field is a condensed data type designed to fit into the existing on-disk record and is zero based (allocated regions are set to 0, sparse regions are set to 1) to provide backwards compatibility. This makes the type somewhat complex for use in higher level inode manipulations such as individual inode allocation, etc.

Rather than foist the complexity of dealing with this field to every bit of logic that requires inode granular information, create the xfs_inobt_ialloc_bitmap() helper to convert the holemask to an inode allocation bitmap. The inode allocation bitmap is inode granularity similar to the inobt record free mask and indicates which inodes of the chunk are physically allocated on disk, irrespective of whether the inode is considered allocated or free by the filesystem. The generic bitmap type requires the use of generic kernel bitmap APIs.

The bitmap_to_u64() helper is provided to convert the bitmap back to a native 64-bit type (for native bitwise operations). This is required because the generic bitmap code represents a bitmap as an array of unsigned long in a little endian style (though each array value is cpu order). To ensure compatibility with various word sizes and endianness', bitmap_to_u64() exports the bitmap to little endian and swaps back to cpu byte order.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_ialloc.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)

fs/xfs/libxfs/xfs_ialloc.c +0 -0

index 72ade0e..fc001d9 100644
@@ -39,6 +39,8 @@
 #include "xfs_icache.h"
 #include "xfs_trace.h"
 

fs/xfs/libxfs/xfs_ialloc.c line 43

Quoted 2 lines

fs/xfs/libxfs/xfs_ialloc.c +2 -0

+STATIC void
+xfs_inobt_ialloc_bitmap(unsigned long *, struct xfs_inobt_rec_incore *);

xfs_inobt_irec_to_allocmap() seems more appropriate for what it does. I'd also suggest it should be in xfs_ialloc_btree.c, too.

Quoted 19 lines

fs/xfs/libxfs/xfs_ialloc.c +13 -0

 /*
  * Allocation group level functions.

@@ -739,6 +741,73 @@ xfs_ialloc_get_rec(
 	return 0;
 }
 
+static inline uint64_t
+bitmap_to_u64(
+	const unsigned long	*bitmap,
+	int			nbits)
+{
+	__le64			lebitmap;
+
+	ASSERT(nbits <= 64);
+
+	/*
+	 * The bitmap format depends on the native word size. E.g., bit 0 could
+	 * land in the middle of the 64 bits on a big endian 32-bit arch (see
+	 * arch/powerpc/include/asm/bitops.h). To handle this, export the bitmap

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_get_rec( · line 761

Quoted 5 lines

fs/xfs/libxfs/xfs_ialloc.c +5 -0

+	 * as 64-bit little endian and convert back to native byte order.
+	 */
+	bitmap_copy_le(&lebitmap, bitmap, nbits);
+	return le64_to_cpu(lebitmap);
+}

Ok, so this is for doing logic operations on the bitmap, such as inverting or masking out a bunch of bits?

The first use of this function is xfs_inobt_first_free_inode(), and the other use is in xfs_difree_inobt() to build the mask of inodes in the chunk that need to be freed, and in both those cases they do

	xfs_inobt_ialloc_bitmap(alloc, rec)
	allocmask = bitmap_to_u64(alloc, 64);

and the local stack bitmap is otherwise unused. So, wouldn't a helper like:

/*
* Return a host format mask of all the allocated inodes in the
* chunk. The bitmap format depends on the native word size (e.g.
* see arch/powerpc/include/asm/bitops.h) and so we have to marshall
* the bitmap through a defined endian conversion so that we can
* perform host native 64 bit logic operations on the resultant
* allocation mask.
*
* A bit value of 1 means the inode is allocated, a value of 0 means it
* is free.
*/
u64
xfs_inobt_irec_to_allocmask(
struct xfs_inobt_rec_incore *irec)

{
	DECLARE_BITMAP(allocmap, 64),
	__le64			lebitmap;

	xfs_inobt_rec_to_allocmap(&allocmap, irec);
	bitmap_copy_le(&lebitmap, allocmap, 64);
	return le64_to_cpu(lebitmap);
}

Quoted 4 lines

fs/xfs/libxfs/xfs_ialloc.c +4 -0

+
+/*
+ * Convert the inode record holemask to an inode allocation bitmap. The inode
+ * allocation bitmap is inode granularity and specifies whether an inode is

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_get_rec( · line 770

Quoted 5 lines

fs/xfs/libxfs/xfs_ialloc.c +5 -0

+ * physically allocated on disk (not whether the inode is considered allocated
+ * or free by the fs).
+ *
+ * We have to be careful with regard to byte order and word size since the
+ * generic bitmap code uses primitive types.

" a bit value of 1 means the inode is allocated, a value of 0 means it is free"

Quoted 7 lines

fs/xfs/libxfs/xfs_ialloc.c +7 -0

+ */
+STATIC void
+xfs_inobt_ialloc_bitmap(
+	unsigned long			*allocbmap,
+	struct xfs_inobt_rec_incore	*rec)
+{
+	int				nextbit;

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_get_rec( · line 787

Quoted 10 lines

fs/xfs/libxfs/xfs_ialloc.c +10 -0

+	DECLARE_BITMAP(holemask, 16);
+
+	bitmap_zero(allocbmap, 64);
+
+	/*
+	 * bitmaps are represented as an array of unsigned long (each in cpu
+	 * byte order). ir_holemask is only 16 bits, so direct assignment is
+	 * safe.
+	 */
+	ASSERT(sizeof(rec->ir_holemask) <= sizeof(holemask[0]));

BUILD_BUG_ON(sizeof(rec->ir_holemask) <= sizeof(holemask[0]));

i.e. if we come across a platform where this fails, break the build rather than waiting for the unlikely event of someone running a debug kernel on that platform...

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

The block allocator supports various arguments to tweak block allocation behavior and set allocation requirements. The sparse inode chunk feature introduces a new requirement not supported by the current arguments. Sparse inode allocations must convert or merge into an inode record that describes a fixed length chunk (64 inodes x inodesize). Full inode chunk allocations by definition always result in valid inode records. Sparse chunk allocations are smaller and the associated records can refer to blocks not owned by the inode chunk. This model can result in invalid inode records in certain cases.

For example, if a sparse allocation occurs near the start of an AG, the aligned inode record for that chunk might refer to agbno 0. If an allocation occurs towards the end of the AG and the AG size is not aligned, the inode record could refer to blocks beyond the end of the AG. While neither of these scenarios directly result in corruption, they both insert invalid inode records and at minimum cause repair to complain, are unlikely to merge into full chunks over time and set land mines for other areas of code.

To guarantee sparse inode chunk allocation creates valid inode records, support the ability to specify an agbno range limit for XFS_ALLOCTYPE_NEAR_BNO block allocations. The min/max agbno's are specified in the allocation arguments and limit the block allocation algorithms to that range. The starting 'agbno' hint is clamped to the range if the specified agbno is out of range. If no sufficient extent is available within the range, the allocation fails. For backwards compatibility, the min/max fields can be initialized to 0 to disable range limiting (e.g., equivalent to min=0,max=agsize).

Signed-off-by Brian Foster <[email protected]>

xfs_ialloc_ag_alloc() makes several attempts to allocate a full inode chunk. If all else fails, reduce the allocation to the minimum sparse granularity and attempt to allocate a sparse inode chunk.

If sparse chunk allocation succeeds, check whether an inobt record already exists that can track the chunk. If so, inherit and update the existing record. Otherwise, insert a new record for the sparse chunk.

Update xfs_inobt_insert_rec() to take the holemask as a parameter and set the associated field on disk. Create the xfs_inobt_update_insert() helper to handle the sparse chunk allocation case - insert or update an existing record depending on whether it already exists.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_ialloc.c | 397 +++++++++++++++++++++++++++++++++++++++++++--
 fs/xfs/xfs_trace.h         |  47 ++++++
 2 files changed, 426 insertions(+), 18 deletions(-)

fs/xfs/libxfs/xfs_ialloc.c +2 -0

index fc001d9..090d114 100644
@@ -122,12 +122,16 @@ 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)

fs/xfs/libxfs/xfs_ialloc.c +3 -0

@@ -151,6 +155,19 @@ xfs_inobt_insert(
 	xfs_agino_t		thisino;
 	int			i;
 	int			error;
+	uint8_t			count;
+
+	/*

fs/xfs/libxfs/xfs_ialloc.c +42 -0

@@ -174,8 +191,58 @@ xfs_inobt_insert(
 	}
 
 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+	return 0;
+}
 
+/*
+ * Update or insert a new record based on a sparse inode chunk allocation.
+ *
+ * If a record already exists, the new record is an updated version of that
+ * record based on a merge of sparse inode chunks. Update the record in place.
+ * Otherwise, insert a new record in the tree. Note that the record to insert
+ * must already have been aligned and merged, if necessary.
+ */
+STATIC int
+xfs_inobt_update_insert(
+	struct xfs_mount		*mp,
+	struct xfs_trans		*tp,
+	struct xfs_buf			*agbp,
+	struct xfs_inobt_rec_incore	*rec,
+	xfs_btnum_t			btnum)
+{
+	struct xfs_btree_cur		*cur;
+	struct xfs_agi			*agi = XFS_BUF_TO_AGI(agbp);
+	xfs_agnumber_t			agno = be32_to_cpu(agi->agi_seqno);
+	int				i;
+	int				error;
+
+	cur = xfs_inobt_init_cursor(mp, tp, agbp, agno, btnum);
+
+	error = xfs_inobt_lookup(cur, rec->ir_startino, XFS_LOOKUP_EQ, &i);
+	if (error)
+		goto error;
+	if (i == 1) {
+		/* found a record, update it with the merged record */
+		error = xfs_inobt_update(cur, rec);
+		if (error)
+			goto error;
+		goto out;
+	}
+
+	/* no existing record, insert a new one */
+	error = xfs_inobt_insert_rec(cur, rec->ir_holemask, rec->ir_count,
+				     rec->ir_freecount, rec->ir_free, &i);
+	if (error)
+		goto error;

fs/xfs/libxfs/xfs_ialloc.c +31 -0

@@ -358,6 +453,183 @@ xfs_ialloc_inode_init(
 }
 
 /*
+ * Align a record for a recently allocated sparse chunk. The input is a record
+ * that describes the unaligned chunk. The record is aligned such that it is fit
+ * for insertion (or merge) into the on-disk inode btrees.
+ */
+STATIC void
+xfs_align_sparse_rec(
+	struct xfs_mount		*mp,
+	struct xfs_inobt_rec_incore	*rec)
+{
+	xfs_agblock_t			agbno;
+	xfs_agblock_t			mod;
+	int				offset;
+	uint16_t			allocmask;
+
+	agbno = XFS_AGINO_TO_AGBNO(mp, rec->ir_startino);
+	mod = agbno % mp->m_sb.sb_inoalignmt;
+	if (!mod)
+		return;
+
+	/* calculate the inode offset and align startino */
+	offset = mod << mp->m_sb.sb_inopblog;
+	rec->ir_startino -= offset;
+
+	/*
+	 * Since startino has been aligned down, we have to left shift
+	 * ir_holemask such that it continues to represent the same physical
+	 * inodes as the unaligned record. The unaligned record by definition
+	 * tracks the allocated inodes with the lowest order bits.
+	 *
+	 * ir_holemask is inverted before the shift such that set bits represent
+	 * allocated inodes. This makes it safe for the bit-shift to introduce

fs/xfs/libxfs/xfs_ialloc.c +7 -0

+{
+	DECLARE_BITMAP(talloc, 64);
+	DECLARE_BITMAP(salloc, 64);
+	DECLARE_BITMAP(tmp, 64);
+
+	/* records must cover the same inode range */
+	if (trec->ir_startino != srec->ir_startino)

fs/xfs/libxfs/xfs_ialloc.c +41 -0

+}
+
+/*
+ * Determine whether a newly allocated sparse inode chunk record overlaps with
+ * an existing sparse record in the inobt. When sparse inode chunks are enabled,
+ * all inode chunk alignment is increased from cluster size to physical inode
+ * chunk size. This means that the smallest, non-zero gap between two inode
+ * chunks is at least one full inode chunk. When a sparse inode chunk is
+ * allocated, the containing record is also aligned in this manner such that
+ * future sparse allocations within that same range all align to the same record
+ * startino. This alignment policy supports the ability to merge sparse chunks
+ * into complete chunks over time.
+ *
+ * Given an newly allocated/aligned sparse inode record, look up whether a
+ * sparse record already exists at this startino. If so, merge the two records
+ * and return the merged record in nrec.
+ *
+ * An error is returned if records overlap but a merge is not possible. Given
+ * the alignment constraints described above, this should never happen and thus
+ * is treated as fs corruption.
+ */
+STATIC int
+xfs_inobt_rec_merge(
+	struct xfs_mount		*mp,
+	struct xfs_trans		*tp,
+	struct xfs_buf			*agbp,
+	xfs_btnum_t			btnum,
+	struct xfs_inobt_rec_incore	*nrec)	/* in/out: new/merged rec. */
+{
+	struct xfs_btree_cur		*cur;
+	struct xfs_agi			*agi = XFS_BUF_TO_AGI(agbp);
+	xfs_agnumber_t			agno = be32_to_cpu(agi->agi_seqno);
+	int				error;
+	int				i;
+	struct xfs_inobt_rec_incore	rec;
+
+	cur = xfs_inobt_init_cursor(mp, tp, agbp, agno, btnum);
+
+	/* the new record is pre-aligned so we know where to look */
+	error = xfs_inobt_lookup(cur, nrec->ir_startino, XFS_LOOKUP_EQ, &i);
+	if (error)

fs/xfs/libxfs/xfs_ialloc.c +4 -0

@@ -514,6 +828,65 @@ xfs_ialloc_ag_alloc(
 	 * Convert the results.
 	 */
 	newino = XFS_OFFBNO_TO_AGINO(args.mp, args.agbno, 0);
+
+	if (xfs_inobt_issparse(~allocmask)) {
+		/*
+		 * We've allocated a sparse chunk...

fs/xfs/libxfs/xfs_ialloc.c +16 -0

+		error = xfs_inobt_rec_merge(args.mp, tp, agbp, XFS_BTNUM_INO,
+					    &rec);
+		if (!error)
+			error = xfs_inobt_rec_check_count(args.mp, &rec);
+		if (error == -EFSCORRUPTED) {
+			xfs_alert(args.mp,
+	"invalid sparse inode record: ino 0x%llx holemask 0x%x count %u",
+				  XFS_AGINO_TO_INO(args.mp, agno,
+						   rec.ir_startino),
+				  rec.ir_holemask, rec.ir_count);
+			xfs_force_shutdown(args.mp, SHUTDOWN_CORRUPT_INCORE);
+		}
+		if (error)
+			return error;
+
+		error = xfs_inobt_update_insert(args.mp, tp, agbp, &rec,

Quoted 37 lines · Brian Foster

xfs_ialloc_ag_alloc() makes several attempts to allocate a full inode chunk. If all else fails, reduce the allocation to the minimum sparse granularity and attempt to allocate a sparse inode chunk.

If sparse chunk allocation succeeds, check whether an inobt record already exists that can track the chunk. If so, inherit and update the existing record. Otherwise, insert a new record for the sparse chunk.

Update xfs_inobt_insert_rec() to take the holemask as a parameter and set the associated field on disk. Create the xfs_inobt_update_insert() helper to handle the sparse chunk allocation case - insert or update an existing record depending on whether it already exists.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_ialloc.c | 397 +++++++++++++++++++++++++++++++++++++++++++--
 fs/xfs/xfs_trace.h         |  47 ++++++
 2 files changed, 426 insertions(+), 18 deletions(-)

fs/xfs/libxfs/xfs_ialloc.c +4 -2

index fc001d9..090d114 100644
@@ -122,12 +122,16 @@ 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 = 0;
-	cur->bc_rec.i.ir_count = 0; /* zero for backwards compatibility */
+	ASSERT(count == 0 || xfs_sb_version_hassparseinodes(&cur->bc_mp->m_sb));
+

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_get_rec( · line 137

Quoted 5 lines

fs/xfs/libxfs/xfs_ialloc.c +2 -0

+	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);

Ok, so I'd definitely prefer two separate helpers here so that we don't need asserts or validity checking....

Quoted 7 lines

fs/xfs/libxfs/xfs_ialloc.c +3 -0

@@ -151,6 +155,19 @@ xfs_inobt_insert(
 	xfs_agino_t		thisino;
 	int			i;
 	int			error;
+	uint8_t			count;
+
+	/*

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_insert( · line 170

Quoted 10 lines

fs/xfs/libxfs/xfs_ialloc.c +10 -0

+	 * Only set ir_count in the inobt record if the sparse inodes feature is
+	 * enabled. If disabled, we must maintain backwards compatibility with
+	 * the older inobt record format where the current count and holemask
+	 * fields map to the higher order bytes of freecount and thus must be
+	 * zeroed.
+	 */
+	if (xfs_sb_version_hassparseinodes(&mp->m_sb))
+		count = XFS_INODES_PER_CHUNK;
+	else
+		count = 0;

I'd strongly suggest that we pass the holemask, count and freecount from the caller, for reasons that will become obvious later.

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_insert( · line 187

Quoted 9 lines

fs/xfs/libxfs/xfs_ialloc.c +1 -1

@@ -164,7 +181,7 @@ xfs_inobt_insert(
 		}
 		ASSERT(i == 0);
 
-		error = xfs_inobt_insert_rec(cur, XFS_INODES_PER_CHUNK,
+		error = xfs_inobt_insert_rec(cur, 0, count, XFS_INODES_PER_CHUNK,
 					     XFS_INOBT_ALL_FREE, &i);
 		if (error) {
 			xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);

And this hunk would become:

		if (xfs_sb_version_hassparseinodes(&mp->m_sb)) {
			error = xfs_inobt_insert_sprec(cur, holemask, count,
						       freecount, &i);
						       holemask,
		else
			error = xfs_inobt_insert_rec(cur, count,
						     freecount, &i);

Quoted 47 lines

fs/xfs/libxfs/xfs_ialloc.c +42 -0

@@ -174,8 +191,58 @@ xfs_inobt_insert(
 	}
 
 	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+	return 0;
+}
 
+/*
+ * Update or insert a new record based on a sparse inode chunk allocation.
+ *
+ * If a record already exists, the new record is an updated version of that
+ * record based on a merge of sparse inode chunks. Update the record in place.
+ * Otherwise, insert a new record in the tree. Note that the record to insert
+ * must already have been aligned and merged, if necessary.
+ */
+STATIC int
+xfs_inobt_update_insert(
+	struct xfs_mount		*mp,
+	struct xfs_trans		*tp,
+	struct xfs_buf			*agbp,
+	struct xfs_inobt_rec_incore	*rec,
+	xfs_btnum_t			btnum)
+{
+	struct xfs_btree_cur		*cur;
+	struct xfs_agi			*agi = XFS_BUF_TO_AGI(agbp);
+	xfs_agnumber_t			agno = be32_to_cpu(agi->agi_seqno);
+	int				i;
+	int				error;
+
+	cur = xfs_inobt_init_cursor(mp, tp, agbp, agno, btnum);
+
+	error = xfs_inobt_lookup(cur, rec->ir_startino, XFS_LOOKUP_EQ, &i);
+	if (error)
+		goto error;
+	if (i == 1) {
+		/* found a record, update it with the merged record */
+		error = xfs_inobt_update(cur, rec);
+		if (error)
+			goto error;
+		goto out;
+	}
+
+	/* no existing record, insert a new one */
+	error = xfs_inobt_insert_rec(cur, rec->ir_holemask, rec->ir_count,
+				     rec->ir_freecount, rec->ir_free, &i);
+	if (error)
+		goto error;

fs/xfs/libxfs/xfs_ialloc.c xfs_inobt_insert( · line 246

Quoted 10 lines

fs/xfs/libxfs/xfs_ialloc.c +8 -0

+	XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+
+out:
+	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
 	return 0;
+
+error:
+	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
+	return error;
 }

I think that the way you've factored out the sparse inode record update code can do with some work. I'll come back to this.

Quoted 42 lines

fs/xfs/libxfs/xfs_ialloc.c +38 -0

@@ -358,6 +453,183 @@ xfs_ialloc_inode_init(
 }
 
 /*
+ * Align a record for a recently allocated sparse chunk. The input is a record
+ * that describes the unaligned chunk. The record is aligned such that it is fit
+ * for insertion (or merge) into the on-disk inode btrees.
+ */
+STATIC void
+xfs_align_sparse_rec(
+	struct xfs_mount		*mp,
+	struct xfs_inobt_rec_incore	*rec)
+{
+	xfs_agblock_t			agbno;
+	xfs_agblock_t			mod;
+	int				offset;
+	uint16_t			allocmask;
+
+	agbno = XFS_AGINO_TO_AGBNO(mp, rec->ir_startino);
+	mod = agbno % mp->m_sb.sb_inoalignmt;
+	if (!mod)
+		return;
+
+	/* calculate the inode offset and align startino */
+	offset = mod << mp->m_sb.sb_inopblog;
+	rec->ir_startino -= offset;
+
+	/*
+	 * Since startino has been aligned down, we have to left shift
+	 * ir_holemask such that it continues to represent the same physical
+	 * inodes as the unaligned record. The unaligned record by definition
+	 * tracks the allocated inodes with the lowest order bits.
+	 *
+	 * ir_holemask is inverted before the shift such that set bits represent
+	 * allocated inodes. This makes it safe for the bit-shift to introduce
+	 * zeroes in the lower order bits without corrupting the record.
+	 *
+	 * Note that no change is required for ir_count, ir_freecount or
+	 * ir_free. The count values are not affected by alignment and ir_free
+	 * is initialized to 1s for all inodes, sparse or otherwise.
+	 */
+	allocmask = ~rec->ir_holemask;

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 496

Quoted 3 lines

fs/xfs/libxfs/xfs_ialloc.c +3 -0

+	allocmask <<= offset / XFS_INODES_PER_HOLEMASK_BIT;
+	rec->ir_holemask = ~allocmask;
+}

I don't understand why the holemask would need changing. I would have expected this to be done before the hole mask has been placed inside the record. Indeed, putting it into the record first means we have to deal with inversions and jump through other hoops.

static void
xfs_align_sparse_ino(

	struct xfs_mount	*mp,
	xfs_agino_t		*startino,
	uint16_t		*allocmask)
{
	agbno = XFS_AGINO_TO_AGBNO(mp, *startino);
	mod = agbno % mp->m_sb.sb_inoalignmt;
	if (!mod)
		return;

	offset = mod << mp->m_sb.sb_inopblog;
	*startino -= offset;
	*allocmask <<= offset / XFS_INODES_PER_HOLEMASK_BIT;
}

And then place the result in the irec....

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 501

Quoted 4 lines

fs/xfs/libxfs/xfs_ialloc.c +4 -0

+/*
+ * Determine whether a sparse inode records can be merged. The inode ranges
+ * must match and there must be no allocation overlap between the records.
+ */

Hmmm - src + target is not great for an operation where both records are a source. Perhaps be explict in the comment? e.g.

/*
* Determine whether the source inode record can be merged into a
* target record. Both records must be sparse, the inode ranges
* must match and there must be no allocation overlap between the
* records.
*/

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 505

Quoted 4 lines

fs/xfs/libxfs/xfs_ialloc.c +4 -0

+STATIC bool
+__xfs_inobt_can_merge(
+	struct xfs_inobt_rec_incore	*trec,	/* tgt record */
+	struct xfs_inobt_rec_incore	*srec)	/* src record */

If we detect overlap, isn't that an indication of corruption?

Quoted 12 lines

fs/xfs/libxfs/xfs_ialloc.c +12 -0

+{
+	DECLARE_BITMAP(talloc, 64);
+	DECLARE_BITMAP(salloc, 64);
+	DECLARE_BITMAP(tmp, 64);
+
+	/* records must cover the same inode range */
+	if (trec->ir_startino != srec->ir_startino)
+		return false;
+
+	/* both records must be sparse */
+	if (!xfs_inobt_issparse(trec->ir_holemask) ||
+	    !xfs_inobt_issparse(srec->ir_holemask))

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 522

Quoted 5 lines

fs/xfs/libxfs/xfs_ialloc.c +5 -0

+		return false;
+
+	/* can't exceed capacity of a full record */
+	if (trec->ir_count + srec->ir_count > XFS_INODES_PER_CHUNK)
+		return false;

probably also need to check that both records have inodes allocated in them. ir_count == 0 is indicative of a corrupt record, right?

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 530

Quoted 8 lines

fs/xfs/libxfs/xfs_ialloc.c +8 -0

+
+	/* verify there is no allocation overlap */
+	xfs_inobt_ialloc_bitmap(talloc, trec);
+	xfs_inobt_ialloc_bitmap(salloc, srec);
+
+	bitmap_and(tmp, salloc, talloc, 64);
+	if (!bitmap_empty(tmp, 64))
+		return false;

And if one has an ir_count of zero, the bitmap will always be zero....

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 538

Quoted 4 lines

fs/xfs/libxfs/xfs_ialloc.c +4 -0

+/*
+ * Merge two sparse inode records. The caller must call __xfs_inobt_can_merge()
+ * to ensure the merge is valid.
+ */

same thing about src/target here.

Quoted 10 lines

fs/xfs/libxfs/xfs_ialloc.c +10 -0

+STATIC void
+__xfs_inobt_rec_merge(
+	struct xfs_inobt_rec_incore	*trec,	/* target */
+	struct xfs_inobt_rec_incore	*srec)	/* src */
+{
+	ASSERT(trec->ir_startino == srec->ir_startino);
+
+	/* combine the counts */
+	trec->ir_count += srec->ir_count;
+	trec->ir_freecount += srec->ir_freecount;

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 551

Quoted 3 lines

fs/xfs/libxfs/xfs_ialloc.c +3 -0

+
+	/* merge the holemask */
+	trec->ir_holemask &= srec->ir_holemask;

Comments in this function are not very useful. Please remind me:
does the holemask use bit value of 1 as allocated or as a hole? My head is full of allocmask stuff and so I can't tell if a merge should use |= or &= to get the correct value.

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 554

Quoted 2 lines

fs/xfs/libxfs/xfs_ialloc.c +2 -0

+	/* merge the free mask */
+	trec->ir_free &= srec->ir_free;

Same here.

Quoted 48 lines

fs/xfs/libxfs/xfs_ialloc.c +48 -0

+}
+
+/*
+ * Determine whether a newly allocated sparse inode chunk record overlaps with
+ * an existing sparse record in the inobt. When sparse inode chunks are enabled,
+ * all inode chunk alignment is increased from cluster size to physical inode
+ * chunk size. This means that the smallest, non-zero gap between two inode
+ * chunks is at least one full inode chunk. When a sparse inode chunk is
+ * allocated, the containing record is also aligned in this manner such that
+ * future sparse allocations within that same range all align to the same record
+ * startino. This alignment policy supports the ability to merge sparse chunks
+ * into complete chunks over time.
+ *
+ * Given an newly allocated/aligned sparse inode record, look up whether a
+ * sparse record already exists at this startino. If so, merge the two records
+ * and return the merged record in nrec.
+ *
+ * An error is returned if records overlap but a merge is not possible. Given
+ * the alignment constraints described above, this should never happen and thus
+ * is treated as fs corruption.
+ */
+STATIC int
+xfs_inobt_rec_merge(
+	struct xfs_mount		*mp,
+	struct xfs_trans		*tp,
+	struct xfs_buf			*agbp,
+	xfs_btnum_t			btnum,
+	struct xfs_inobt_rec_incore	*nrec)	/* in/out: new/merged rec. */
+{
+	struct xfs_btree_cur		*cur;
+	struct xfs_agi			*agi = XFS_BUF_TO_AGI(agbp);
+	xfs_agnumber_t			agno = be32_to_cpu(agi->agi_seqno);
+	int				error;
+	int				i;
+	struct xfs_inobt_rec_incore	rec;
+
+	cur = xfs_inobt_init_cursor(mp, tp, agbp, agno, btnum);
+
+	/* the new record is pre-aligned so we know where to look */
+	error = xfs_inobt_lookup(cur, nrec->ir_startino, XFS_LOOKUP_EQ, &i);
+	if (error)
+		goto error;
+	/* if nothing there, we're done */
+	if (i == 0)
+		goto out;
+
+	error = xfs_inobt_get_rec(cur, &rec, &i);
+	if (error)

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 605

Quoted 3 lines

fs/xfs/libxfs/xfs_ialloc.c +3 -0

+		goto error;
+	XFS_WANT_CORRUPTED_GOTO(i == 1, error);
+	ASSERT(rec.ir_startino == nrec->ir_startino);

XFS_WANT_CORRUPTED_GOTO() is better than an assert here. On a debug kernel, it will still assert, but on a production kernel it will trigger a corruption error rather than potentially propagating a corruption further.

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_inode_init( · line 614

Quoted 8 lines

fs/xfs/libxfs/xfs_ialloc.c +8 -0

+	/*
+	 * This should never happen. If we have coexisting records that cannot
+	 * merge, something is seriously wrong.
+	 */
+	if (!__xfs_inobt_can_merge(nrec, &rec)) {
+		error = -EFSCORRUPTED;
+		goto error;
+	}

Ah, so it is a corruption issue if merges can't occur. ;)

	XFS_WANT_CORRUPTED_GOTO(!__xfs_inobt_can_merge(nrec, &rec));

Quoted 8 lines

fs/xfs/libxfs/xfs_ialloc.c +4 -0

@@ -514,6 +828,65 @@ xfs_ialloc_ag_alloc(
 	 * Convert the results.
 	 */
 	newino = XFS_OFFBNO_TO_AGINO(args.mp, args.agbno, 0);
+
+	if (xfs_inobt_issparse(~allocmask)) {
+		/*
+		 * We've allocated a sparse chunk...

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 844

Quoted 10 lines

fs/xfs/libxfs/xfs_ialloc.c +10 -0

+		 */
+		rec.ir_startino = newino;
+		rec.ir_holemask = ~allocmask;
+		rec.ir_count = newlen;
+		rec.ir_freecount = newlen;
+		rec.ir_free = XFS_INOBT_ALL_FREE;
+
+		/* align record and update newino for agi_newino */
+		xfs_align_sparse_rec(args.mp, &rec);
+		newino = rec.ir_startino;

See my earlier comments about aligning before putting stuff into the record, especially as you are having to pull modified information straight back out of the record.

Quoted 16 lines

fs/xfs/libxfs/xfs_ialloc.c +16 -0

+		error = xfs_inobt_rec_merge(args.mp, tp, agbp, XFS_BTNUM_INO,
+					    &rec);
+		if (!error)
+			error = xfs_inobt_rec_check_count(args.mp, &rec);
+		if (error == -EFSCORRUPTED) {
+			xfs_alert(args.mp,
+	"invalid sparse inode record: ino 0x%llx holemask 0x%x count %u",
+				  XFS_AGINO_TO_INO(args.mp, agno,
+						   rec.ir_startino),
+				  rec.ir_holemask, rec.ir_count);
+			xfs_force_shutdown(args.mp, SHUTDOWN_CORRUPT_INCORE);
+		}
+		if (error)
+			return error;
+
+		error = xfs_inobt_update_insert(args.mp, tp, agbp, &rec,

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 871

Quoted 10 lines

fs/xfs/libxfs/xfs_ialloc.c +10 -0

+						XFS_BTNUM_INO);
+		if (error)
+			return error;
+
+		if (xfs_sb_version_hasfinobt(&args.mp->m_sb)) {
+			error = xfs_inobt_update_insert(args.mp, tp, agbp, &rec,
+							XFS_BTNUM_FINO);
+			if (error)
+				return error;
+		}

I think this needs to become a helper function, and the implementation refactored. The reason I say this is that the xfs_inobt_rec_merge() function already looks up the record that is to be updated, and if it exists if calculates the merged record value. If then drops all that state and returns the merged record.

Then we call xfs_inobt_update_insert() to determine if we have to update the existing record with the merged record (i.e. build all the state again), and then call xfs_inobt_update() on that record.

Essentially, if xfs_inobt_rec_merge() determines we have a merge candidate, we should do the btree update there immediately, as well as fix up the finobt record.

If we aren't doing a record merge and update, then it's just an insert operation, and we can use the modified xfs_inobt_insert() function I mentioned earlier to pass the partial chunk record information for insertion. Perhaps even just pass the irec structure...

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 884

Quoted 13 lines

fs/xfs/libxfs/xfs_ialloc.c +13 -0

+	} else {
+		/* full chunk - insert new records to both btrees */
+		error = xfs_inobt_insert(args.mp, tp, agbp, newino, newlen,
+					 XFS_BTNUM_INO);
+		if (error)
+			return error;
+
+		if (xfs_sb_version_hasfinobt(&args.mp->m_sb)) {
+			error = xfs_inobt_insert(args.mp, tp, agbp, newino,
+						 newlen, XFS_BTNUM_FINO);
+			if (error)
+				return error;
+		}

And this could pass an irec that indicates a full inode chunk rather than just the subset of inofmration needed to describe a full inode chunk.

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Sparse inode allocations generally only occur when full inode chunk allocation fails. This requires some level of filesystem space usage and fragmentation.

For filesystems formatted with sparse inode chunks enabled, do random sparse inode chunk allocs when compiled in DEBUG mode to increase test coverage.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_ialloc.c | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

fs/xfs/libxfs/xfs_ialloc.c +0 -0

index 090d114..3e5d3eb 100644
@@ -652,9 +652,18 @@ xfs_ialloc_ag_alloc(
 

fs/xfs/libxfs/xfs_ialloc.c +6 -2

 	memset(&args, 0, sizeof(args));
 	args.tp = tp;
 	args.mp = tp->t_mountp;
+	args.fsbno = NULLFSBLOCK;
 
 	/*
 	 * Locking will ensure that we don't have two callers in here

@@ -675,6 +684,10 @@ xfs_ialloc_ag_alloc(
 	agno = be32_to_cpu(agi->agi_seqno);
 	args.agbno = XFS_AGINO_TO_AGBNO(args.mp, newino) +
 		     args.mp->m_ialloc_blks;
+#ifdef DEBUG
+	if (do_sparse)
+		goto sparse_alloc;
+#endif
 	if (likely(newino != NULLAGINO &&
 		  (args.agbno < be32_to_cpu(agi->agi_length)))) {
 		args.fsbno = XFS_AGB_TO_FSB(args.mp, agno, args.agbno);

@@ -713,8 +726,7 @@ xfs_ialloc_ag_alloc(
 		 * subsequent requests.
 		 */
 		args.minalignslop = 0;
-	} else
-		args.fsbno = NULLFSBLOCK;
+	}
 
 	if (unlikely(args.fsbno == NULLFSBLOCK)) {
 		/*

Quoted 21 lines · Brian Foster

Sparse inode allocations generally only occur when full inode chunk allocation fails. This requires some level of filesystem space usage and fragmentation.

For filesystems formatted with sparse inode chunks enabled, do random sparse inode chunk allocs when compiled in DEBUG mode to increase test coverage.

Signed-off-by Brian Foster <[email protected]>

---
 fs/xfs/libxfs/xfs_ialloc.c | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

fs/xfs/libxfs/xfs_ialloc.c +0 -0

index 090d114..3e5d3eb 100644
@@ -652,9 +652,18 @@ xfs_ialloc_ag_alloc(
 
 	struct xfs_perag *pag;
 

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 662

Quoted 8 lines

fs/xfs/libxfs/xfs_ialloc.c +8 -0

+#ifdef DEBUG
+	int		do_sparse = 0;
+
+	/* randomly do sparse inode allocations */
+	if (xfs_sb_version_hassparseinodes(&tp->t_mountp->m_sb))
+		do_sparse = prandom_u32() & 1;
+#endif
+

Bit ugly with all the ifdefs. If you define the do_sparse variable outside the ifdef, then the rest of the code other than this check doesn't need ifdefs.

Quoted 37 lines

fs/xfs/libxfs/xfs_ialloc.c +9 -2

 	memset(&args, 0, sizeof(args));
 	args.tp = tp;
 	args.mp = tp->t_mountp;
+	args.fsbno = NULLFSBLOCK;
 
 	/*
 	 * Locking will ensure that we don't have two callers in here

@@ -675,6 +684,10 @@ xfs_ialloc_ag_alloc(
 	agno = be32_to_cpu(agi->agi_seqno);
 	args.agbno = XFS_AGINO_TO_AGBNO(args.mp, newino) +
 		     args.mp->m_ialloc_blks;
+#ifdef DEBUG
+	if (do_sparse)
+		goto sparse_alloc;
+#endif
 	if (likely(newino != NULLAGINO &&
 		  (args.agbno < be32_to_cpu(agi->agi_length)))) {
 		args.fsbno = XFS_AGB_TO_FSB(args.mp, agno, args.agbno);

@@ -713,8 +726,7 @@ xfs_ialloc_ag_alloc(
 		 * subsequent requests.
 		 */
 		args.minalignslop = 0;
-	} else
-		args.fsbno = NULLFSBLOCK;
+	}
 
 	if (unlikely(args.fsbno == NULLFSBLOCK)) {
 		/*

@@ -769,6 +781,9 @@ xfs_ialloc_ag_alloc(
 	 * Finally, try a sparse allocation if the filesystem supports it and
 	 * the sparse allocation length is smaller than a full chunk.
 	 */
+#ifdef DEBUG
+sparse_alloc:
+#endif
 	if (xfs_sb_version_hassparseinodes(&args.mp->m_sb) &&
 	    args.mp->m_ialloc_min_blks < args.mp->m_ialloc_blks &&

fs/xfs/libxfs/xfs_ialloc.c xfs_ialloc_ag_alloc( · line 789

Quoted 1 line

fs/xfs/libxfs/xfs_ialloc.c +0 -0

 	    args.fsbno == NULLFSBLOCK) {

The label can go after the if() statement, right? We've already guaranteed all those other parameters are true, though I suspect there's a case where that m_ialloc_min_blks < m_ialloc_blks will
fail: block size larger than inode chunk size (e.g. 64k block size, 512 byte inodes) so that would result in the code above failing to allocate any inode chunks at all...

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]