xfs: introduce the free inode btree

Reserve a v5 read-only compatibility feature bit for the finobt and create the xfs_sb_version_hasfinobt() helper to determine whether an fs has the feature enabled.

The finobt does not change existing on-disk structures, but must remain consistent with the ialloc btree. Modifications from older kernels would violate that constrant. Therefore, we restrict older kernels to read-only mounts of finobt-enabled filesystems.

Note that this does not yet enable the ability to rw mount a finobt fs (by setting the feature bit in the XFS_SB_FEAT_RO_COMPAT_ALL mask).

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

Define the AGI fields for the finobt root/level and add magic numbers. Update the btree code to add support for the new XFS_BTNUM_FINOBT inode btree.

The finobt root block is reserved immediately following the inobt root block in the AG. Update XFS_PREALLOC_BLOCKS() to determine the starting AG data block based on whether finobt support is enabled.

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

---
 fs/xfs/xfs_ag.h           | 32 +++++++++++++++----------
 fs/xfs/xfs_btree.c        |  6 +++--
 fs/xfs/xfs_btree.h        |  3 +++
 fs/xfs/xfs_format.h       | 14 ++++++++++-
 fs/xfs/xfs_ialloc.c       | 37 +++++++++++++++++++++++++----
 fs/xfs/xfs_ialloc_btree.c | 60 +++++++++++++++++++++++++++++++++++++++++++++--
 fs/xfs/xfs_log_recover.c  |  2 ++
 fs/xfs/xfs_stats.c        |  1 +
 fs/xfs/xfs_stats.h        | 18 +++++++++++++-
 fs/xfs/xfs_types.h        |  2 +-
 10 files changed, 150 insertions(+), 25 deletions(-)

fs/xfs/xfs_ag.h +0 -0

index 3fc1098..5d3011f 100644

fs/xfs/xfs_ag.h +1 -1

 #ifdef DEBUG

@@ -1515,14 +1517,39 @@ xfs_ialloc_log_agi(
 	ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
 #endif
 	/*
-	 * Compute byte offsets for the first and last fields.
+	 * The growth of the agi buffer over time now requires that we interpret

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

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

---
 fs/xfs/xfs_inode.c       |  4 +++-
 fs/xfs/xfs_trans_resv.c  | 47 +++++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trans_space.h |  7 ++++++-
 3 files changed, 52 insertions(+), 6 deletions(-)

fs/xfs/xfs_inode.c +0 -0

index 001aa89..57c77ed 100644

fs/xfs/xfs_inode.c +0 -0

 	if (error) {
 		ASSERT(XFS_FORCED_SHUTDOWN(mp));
 		xfs_trans_cancel(tp, XFS_TRANS_RELEASE_LOG_RES);

fs/xfs/xfs_trans_resv.c +0 -0

index 2fd59c0..32f35c1 100644

fs/xfs/xfs_trans_resv.c +1 -0

@@ -267,6 +298,7 @@ xfs_calc_remove_reservation(
  *    the superblock for the nlink flag: sector size
  *    the directory btree: (max depth + v2) * dir block size
  *    the directory inode's bmap btree: (max depth + v2) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_modify(

fs/xfs/xfs_trans_resv.c +1 -0

 /*

@@ -285,6 +318,7 @@ xfs_calc_create_resv_modify(
  *    the inode blocks allocated: XFS_IALLOC_BLOCKS * blocksize
  *    the inode btree: max depth * blocksize
  *    the allocation btrees: 2 trees * (max depth - 1) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_alloc(

Quoted 15 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

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

---
 fs/xfs/xfs_inode.c       |  4 +++-
 fs/xfs/xfs_trans_resv.c  | 47 +++++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trans_space.h |  7 ++++++-
 3 files changed, 52 insertions(+), 6 deletions(-)

fs/xfs/xfs_inode.c +0 -0

Quoted 5 lines

fs/xfs/xfs_trans_resv.c +0 -0

index 2fd59c0..32f35c1 100644

fs/xfs/xfs_trans_resv.c xfs_calc_inode_res( · line 106

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +6 -0

@@ -98,6 +98,37 @@ xfs_calc_inode_res(
 }
 
 /*
+ * The free inode btree is a conditional feature and the log reservation
+ * requirements differ slightly from that of the traditional inode allocation
+ * btree. The finobt tracks records for inode chunks with at least one free inode.
+ * Therefore, a record can be removed from the tree for an inode allocation or
+ * free and the associated merge reservation is unconditional. This also covers
+ * the possibility of a split on record insertion.

Slightly wider than 80 columns here. FWIW, if you use vim, add this rule to have it add a red line at the textwidth you have set:

" highlight textwidth
set cc=+1

And that will point out lines that are too long quite obviously ;)

fs/xfs/xfs_trans_resv.c xfs_calc_inode_res( · line 112

Quoted 6 lines

fs/xfs/xfs_trans_resv.c +6 -0

+ *
+ * the free inode btree: max depth * block size
+ * the free inode btree entry: block size
+ *
+ * TODO: is the modify res really necessary? covered by the merge/split res?
+ * This seems to be the pattern of ifree, but not create_resv_alloc. Why?

The modify case is for an allocation that only updates an inobt record (i.e. chunk already allocated, free inodes in it). Because we can remove a finobt record when "modifying" the last free inode record in a chunk, "modify" can cause a redcord removal and hence a tree merge. In which case it's no different of any of the other finobt reservations....

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +1 -0

@@ -267,6 +298,7 @@ xfs_calc_remove_reservation(
  *    the superblock for the nlink flag: sector size
  *    the directory btree: (max depth + v2) * dir block size
  *    the directory inode's bmap btree: (max depth + v2) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_modify(

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_modify( · line 312

Quoted 7 lines

fs/xfs/xfs_trans_resv.c +2 -1

@@ -275,7 +307,8 @@ xfs_calc_create_resv_modify(
 	return xfs_calc_inode_res(mp, 2) +
 		xfs_calc_buf_res(1, mp->m_sb.sb_sectsize) +
 		(uint)XFS_FSB_TO_B(mp, 1) +
-		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1));
+		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 1);
 }

And this is where is starts to get complex. The modify operation can now cause a finobt merge, when means blocks will be allocated/freed. That means we now need to take into account:

* the allocation btrees: 2 trees * (max depth - 1) * block size

and anything else freeing an extent requires.

Quoted 13 lines

fs/xfs/xfs_trans_resv.c +1 -0

 /*

@@ -285,6 +318,7 @@ xfs_calc_create_resv_modify(
  *    the inode blocks allocated: XFS_IALLOC_BLOCKS * blocksize
  *    the inode btree: max depth * blocksize
  *    the allocation btrees: 2 trees * (max depth - 1) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_alloc(

@@ -295,7 +329,8 @@ xfs_calc_create_resv_alloc(
 		xfs_calc_buf_res(XFS_IALLOC_BLOCKS(mp), XFS_FSB_TO_B(mp, 1)) +
 		xfs_calc_buf_res(mp->m_in_maxlevels, XFS_FSB_TO_B(mp, 1)) +
 		xfs_calc_buf_res(XFS_ALLOCFREE_LOG_COUNT(mp, 1),

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_alloc( · line 334

Quoted 4 lines

fs/xfs/xfs_trans_resv.c +2 -1

-				 XFS_FSB_TO_B(mp, 1));
+				 XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 0);
 }

This reservation is only for v4 superblocks - the icreate transaction reservation is used for v5 superblocks, so that's the only one you need to modify.

Cheers,

Dave.

Quoted 7 lines · Dave Chinner

Quoted 6 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

Quoted 7 lines

Quoted 6 lines

+ *
+ * the free inode btree: max depth * block size
+ * the free inode btree entry: block size
+ *
+ * TODO: is the modify res really necessary? covered by the merge/split res?
+ * This seems to be the pattern of ifree, but not create_resv_alloc. Why?

Quoted 6 lines

The modify case is for an allocation that only updates an inobt record (i.e. chunk already allocated, free inodes in it). Because we can remove a finobt record when "modifying" the last free inode record in a chunk, "modify" can cause a redcord removal and hence a tree merge. In which case it's no different of any of the other finobt reservations....

When I made this note, I think I was curious why there was a need to add to the reservation in the modify case. If we always made a reservation for a btree merge, wouldn't that be enough to cover the basic modify case?

In the code, it looks like we either delete the record or modify it. Is there something in the delete case that I'm missing, or are we just being conservative here? Nonetheless, I modelled this after the ifree requirements, assuming the reservation there was correct.

Quoted 23 lines

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +1 -0

@@ -267,6 +298,7 @@ xfs_calc_remove_reservation(
  *    the superblock for the nlink flag: sector size
  *    the directory btree: (max depth + v2) * dir block size
  *    the directory inode's bmap btree: (max depth + v2) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_modify(

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_modify( · line 312

Quoted 7 lines

fs/xfs/xfs_trans_resv.c +2 -1

@@ -275,7 +307,8 @@ xfs_calc_create_resv_modify(
 	return xfs_calc_inode_res(mp, 2) +
 		xfs_calc_buf_res(1, mp->m_sb.sb_sectsize) +
 		(uint)XFS_FSB_TO_B(mp, 1) +
-		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1));
+		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 1);
 }

And this is where is starts to get complex. The modify operation can now cause a finobt merge, when means blocks will be allocated/freed. That means we now need to take into account:

* the allocation btrees: 2 trees * (max depth - 1) * block size

Quoted 2 lines

and anything else freeing an extent requires.

So is the "allocation btrees: 2 trees ..." portion of xfs_calc_create_resv_alloc() associated with the allocation of the actual inode blocks or potential allocations due to inode btree management? I had thought the former, thus didn't include reservations for this in the finobt calculation.

Quoted 8 lines · Brian Foster

Quoted 7 lines · Dave Chinner

Quoted 6 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

....

Quoted 14 lines

Quoted 7 lines

Quoted 6 lines

+ *
+ * the free inode btree: max depth * block size
+ * the free inode btree entry: block size
+ *
+ * TODO: is the modify res really necessary? covered by the merge/split res?
+ * This seems to be the pattern of ifree, but not create_resv_alloc. Why?

Quoted 6 lines

The modify case is for an allocation that only updates an inobt record (i.e. chunk already allocated, free inodes in it). Because we can remove a finobt record when "modifying" the last free inode record in a chunk, "modify" can cause a redcord removal and hence a tree merge. In which case it's no different of any of the other finobt reservations....

Quoted 4 lines

When I made this note, I think I was curious why there was a need to add to the reservation in the modify case. If we always made a reservation for a btree merge, wouldn't that be enough to cover the basic modify case?

The two cases are kept separate because if we ever separate inode chunk allocation from individual inode allocation from an allocated chunk, then we need the different reservations. if you go back to the original RFD series that documented the finobt, it also discusses this separation and the optimisations in inode management that such a separation brings.

Hence we should not assume that an inode chunk allocation reservation covers the reservation of an inode allocation from an allocated chunk.

Quoted 4 lines

In the code, it looks like we either delete the record or modify it. Is there something in the delete case that I'm missing, or are we just being conservative here? Nonetheless, I modelled this after the ifree requirements, assuming the reservation there was correct.

But the ifree requirement changed, didn't they? i.e. Because the first inode freed in a chunk can now trigger allocation.

Basically, we have these cases:

Allocation:

- allocate chunk, insert inobt rec, insert finobt rec
- allocate inode, modify inobt rec, modify finobt rec
- allocate inode, modify inobt rec, remove finobt rec

The first case is obvious in that it needs to allocate blocks for the inode chunk, but also possibly the inbot and finobt need allocations too (split).

The second case obvious doesn't allocate any blocks at all, and tha tis the existing "modify reservation"

The third case is the new "modify reservation" case, where the removal of a finobt record can cause a merge and hence freeing of a block. That's the case we need to make sure we have the corerct reservation for.

In the case of ifree, it is similar:

- free inode, modify inobt rec, insert finobt rec
- free inode, modify inobt rec, modify finobt rec
- free chunk, remove inobt rec, remove finobt rec

And so it is clear that the same new case occurs here. however, the ifree transaction reservation is not split up like the create transaction, so it already takes into account allocation/freeing of blocks and hence didn't need updating.

Quoted 23 lines

Quoted 23 lines

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +1 -0

@@ -267,6 +298,7 @@ xfs_calc_remove_reservation(
  *    the superblock for the nlink flag: sector size
  *    the directory btree: (max depth + v2) * dir block size
  *    the directory inode's bmap btree: (max depth + v2) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_modify(

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_modify( · line 312

Quoted 7 lines

fs/xfs/xfs_trans_resv.c +2 -1

@@ -275,7 +307,8 @@ xfs_calc_create_resv_modify(
 	return xfs_calc_inode_res(mp, 2) +
 		xfs_calc_buf_res(1, mp->m_sb.sb_sectsize) +
 		(uint)XFS_FSB_TO_B(mp, 1) +
-		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1));
+		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 1);
 }

And this is where is starts to get complex. The modify operation can now cause a finobt merge, when means blocks will be allocated/freed. That means we now need to take into account:

* the allocation btrees: 2 trees * (max depth - 1) * block size

Quoted 8 lines

Quoted 2 lines

and anything else freeing an extent requires.

So is the "allocation btrees: 2 trees ..." portion of xfs_calc_create_resv_alloc() associated with the allocation of the actual inode blocks or potential allocations due to inode btree management? I had thought the former, thus didn't include reservations for this in the finobt calculation.

This is the log space reservation - so it's a reservation for the number of blocks in the btree that can be *modified* by the transaction. So if we have to allocate a block, we can potentially modify leaf-to-root in both free space trees if they both split or merge during the allocation. Hence any transaction that can allocate or free a block needs to reservae this space in the log for the freespace tree modifications.

We have a separate space reservation - as defined in xfs_trans_space.h - which is used to define the worst case metadata block allocation in a given transaction. It is assumed that the log space reservation covers all those blocks being modified, too.

Cheers,

Dave.

Quoted 21 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

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

---
 fs/xfs/xfs_inode.c       |  4 +++-
 fs/xfs/xfs_trans_resv.c  | 47 +++++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trans_space.h |  7 ++++++-
 3 files changed, 52 insertions(+), 6 deletions(-)

fs/xfs/xfs_inode.c +0 -0

index 001aa89..57c77ed 100644
@@ -1730,7 +1730,9 @@ xfs_inactive_ifree(
 	int			error;
 

fs/xfs/xfs_inode.c xfs_inactive_ifree( · line 1735

Quoted 5 lines

fs/xfs/xfs_inode.c +3 -1

 	tp = xfs_trans_alloc(mp, XFS_TRANS_INACTIVE);
-	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree, 0, 0);
+	tp->t_flags |= XFS_TRANS_RESERVE;
+	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree,
+				  XFS_IFREE_SPACE_RES(mp), 0);

Can you add a comment explaining why the XFS_TRANS_RESERVE flag is used here, and why it's use won't lead to accelerated reserve pool depletion?

Quoted 8 lines

fs/xfs/xfs_inode.c +0 -0

 	if (error) {
 		ASSERT(XFS_FORCED_SHUTDOWN(mp));
 		xfs_trans_cancel(tp, XFS_TRANS_RELEASE_LOG_RES);

fs/xfs/xfs_trans_resv.c +0 -0

index 2fd59c0..32f35c1 100644

fs/xfs/xfs_trans_resv.c xfs_calc_inode_res( · line 106

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +6 -0

@@ -98,6 +98,37 @@ xfs_calc_inode_res(
 }
 
 /*
+ * The free inode btree is a conditional feature and the log reservation
+ * requirements differ slightly from that of the traditional inode allocation
+ * btree. The finobt tracks records for inode chunks with at least one free inode.
+ * Therefore, a record can be removed from the tree for an inode allocation or
+ * free and the associated merge reservation is unconditional. This also covers
+ * the possibility of a split on record insertion.

Slightly wider than 80 columns here. FWIW, if you use vim, add this rule to have it add a red line at the textwidth you have set:

" highlight textwidth
set cc=+1

And that will point out lines that are too long quite obviously ;)

fs/xfs/xfs_trans_resv.c xfs_calc_inode_res( · line 112

Quoted 6 lines

fs/xfs/xfs_trans_resv.c +6 -0

+ *
+ * the free inode btree: max depth * block size
+ * the free inode btree entry: block size
+ *
+ * TODO: is the modify res really necessary? covered by the merge/split res?
+ * This seems to be the pattern of ifree, but not create_resv_alloc. Why?

The modify case is for an allocation that only updates an inobt record (i.e. chunk already allocated, free inodes in it). Because we can remove a finobt record when "modifying" the last free inode record in a chunk, "modify" can cause a redcord removal and hence a tree merge. In which case it's no different of any of the other finobt reservations....

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +1 -0

@@ -267,6 +298,7 @@ xfs_calc_remove_reservation(
  *    the superblock for the nlink flag: sector size
  *    the directory btree: (max depth + v2) * dir block size
  *    the directory inode's bmap btree: (max depth + v2) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_modify(

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_modify( · line 312

Quoted 7 lines

fs/xfs/xfs_trans_resv.c +2 -1

@@ -275,7 +307,8 @@ xfs_calc_create_resv_modify(
 	return xfs_calc_inode_res(mp, 2) +
 		xfs_calc_buf_res(1, mp->m_sb.sb_sectsize) +
 		(uint)XFS_FSB_TO_B(mp, 1) +
-		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1));
+		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 1);
 }

And this is where is starts to get complex. The modify operation can now cause a finobt merge, when means blocks will be allocated/freed. That means we now need to take into account:

* the allocation btrees: 2 trees * (max depth - 1) * block size

and anything else freeing an extent requires.

Quoted 10 lines

fs/xfs/xfs_trans_resv.c +1 -0

 /*

@@ -285,6 +318,7 @@ xfs_calc_create_resv_modify(
  *    the inode blocks allocated: XFS_IALLOC_BLOCKS * blocksize
  *    the inode btree: max depth * blocksize
  *    the allocation btrees: 2 trees * (max depth - 1) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_alloc(

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_alloc( · line 334

Quoted 7 lines

fs/xfs/xfs_trans_resv.c +2 -1

@@ -295,7 +329,8 @@ xfs_calc_create_resv_alloc(
 		xfs_calc_buf_res(XFS_IALLOC_BLOCKS(mp), XFS_FSB_TO_B(mp, 1)) +
 		xfs_calc_buf_res(mp->m_in_maxlevels, XFS_FSB_TO_B(mp, 1)) +
 		xfs_calc_buf_res(XFS_ALLOCFREE_LOG_COUNT(mp, 1),
-				 XFS_FSB_TO_B(mp, 1));
+				 XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 0);
 }

This reservation is only for v4 superblocks - the icreate transaction reservation is used for v5 superblocks, so that's the only one you need to modify.

Cheers,

Dave.

Quoted 22 lines · Dave Chinner

Quoted 21 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

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

---
 fs/xfs/xfs_inode.c       |  4 +++-
 fs/xfs/xfs_trans_resv.c  | 47 +++++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trans_space.h |  7 ++++++-
 3 files changed, 52 insertions(+), 6 deletions(-)

fs/xfs/xfs_inode.c +0 -0

index 001aa89..57c77ed 100644
@@ -1730,7 +1730,9 @@ xfs_inactive_ifree(
 	int			error;
 

Quoted 10 lines

fs/xfs/xfs_inode.c xfs_inactive_ifree( · line 1735

Quoted 5 lines

fs/xfs/xfs_inode.c +3 -1

 	tp = xfs_trans_alloc(mp, XFS_TRANS_INACTIVE);
-	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree, 0, 0);
+	tp->t_flags |= XFS_TRANS_RESERVE;
+	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree,
+				  XFS_IFREE_SPACE_RES(mp), 0);

Can you add a comment explaining why the XFS_TRANS_RESERVE flag is used here, and why it's use won't lead to accelerated reserve pool depletion?

So this aspect of things appears to be a bit more interesting than I originally anticipated. I "reserve enabled" this transaction to facilitate the ability to free up inodes under ENOSPC conditions. Without this, the problem of failing out of xfs_inactive_ifree() (and leaving an inode chained on the unlinked list) is easily reproducible with generic/083.

The basic argument for why this is reasonable is that releasing an inode releases used space (i.e., file blocks and potentially directory blocks and inode chunks over time). That said, I can manufacture situations where this is not the case. E.g., allocate a bunch of 0-sized files, consume remaining free space in some separate file, start removing inodes in a manner that removes a single inode per chunk or so. This creates a scenario where the inobt can be very large and the finobt very small (likely a single record). Removing the inodes in this manner reduces the likelihood of freeing up any space and thus rapidly grows the finobt towards the size of the inobt without any free space available. This might or might not qualify as sane use of the fs, but I don't think the failure scenario is acceptable as things currently stand.

I think there are several ways this can go from here. A couple ideas that have crossed my mind:

- Find a way to variably reserve the number of blocks that would be required to grow the finobt to the finobt, based on current state. This would require the total number of blocks (not just enough for a split), so this could get complex and somewhat overbearing (i.e., a lot of space could be quietly reserved, current tracking might not be sufficient and the allocation paths could get hairy).

- Work to push the ifree transaction allocation and reservation to the unlink codepath rather than the eviction codepath. Under normal circumstances, chain the tp to the xfs_inode such that the eviction code path can grab it and run. This prevents us going into the state where an inode is unlinked without having enough space to free up. On the flip side, ENOSPC on unlink isn't very forgiving behavior to the user.

I think the former approach is probably overkill for something that might be a pathological situation. The latter approach is more simple, but it feels like a bit of a hack. I've experimented with it a bit, but I'm not quite sure yet if it introduces any transaction issues by allocating the unlink and ifree transactions at the same time.

Perhaps another argument could be made that it's rather unlikely we run into an fs with as many 0-sized (or sub-inode chunk sized) files as required to deplete the reserve pool without freeing any space, and we should just touch up the failure handling. E.g.,

1.) Continue to reserve enable the ifree transaction. Consider expanding the reserve pool on finobt-enabled fs' if appropriate. Note that this is not guaranteed to provide enough resources to populate the finobt to the level of the inobt without freeing up more space.
2.) Attempt a !XFS_TRANS_RESERVE tp reservation in xfs_inactive_ifree(). If fails, xfs_warn()/notice() and enable XFS_TRANS_RESERVE. 3.) Attempt XFS_TRANS_RESERVE reservation. If fails, xfs_notice() and shutdown.

And this could probably be made more intelligent to bail out sooner if we repeat XFS_TRANS_RESERVE reservations without freeing up any space, etc. Before going too far in one direction... thoughts?

Brian

Quoted 89 lines

Quoted 8 lines

fs/xfs/xfs_inode.c +0 -0

 	if (error) {
 		ASSERT(XFS_FORCED_SHUTDOWN(mp));
 		xfs_trans_cancel(tp, XFS_TRANS_RELEASE_LOG_RES);

fs/xfs/xfs_trans_resv.c +0 -0

index 2fd59c0..32f35c1 100644

fs/xfs/xfs_trans_resv.c xfs_calc_inode_res( · line 106

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +6 -0

@@ -98,6 +98,37 @@ xfs_calc_inode_res(
 }
 
 /*
+ * The free inode btree is a conditional feature and the log reservation
+ * requirements differ slightly from that of the traditional inode allocation
+ * btree. The finobt tracks records for inode chunks with at least one free inode.
+ * Therefore, a record can be removed from the tree for an inode allocation or
+ * free and the associated merge reservation is unconditional. This also covers
+ * the possibility of a split on record insertion.

Slightly wider than 80 columns here. FWIW, if you use vim, add this rule to have it add a red line at the textwidth you have set:

" highlight textwidth
set cc=+1

And that will point out lines that are too long quite obviously ;)

fs/xfs/xfs_trans_resv.c xfs_calc_inode_res( · line 112

Quoted 6 lines

fs/xfs/xfs_trans_resv.c +6 -0

+ *
+ * the free inode btree: max depth * block size
+ * the free inode btree entry: block size
+ *
+ * TODO: is the modify res really necessary? covered by the merge/split res?
+ * This seems to be the pattern of ifree, but not create_resv_alloc. Why?

The modify case is for an allocation that only updates an inobt record (i.e. chunk already allocated, free inodes in it). Because we can remove a finobt record when "modifying" the last free inode record in a chunk, "modify" can cause a redcord removal and hence a tree merge. In which case it's no different of any of the other finobt reservations....

Quoted 9 lines

fs/xfs/xfs_trans_resv.c +1 -0

@@ -267,6 +298,7 @@ xfs_calc_remove_reservation(
  *    the superblock for the nlink flag: sector size
  *    the directory btree: (max depth + v2) * dir block size
  *    the directory inode's bmap btree: (max depth + v2) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_modify(

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_modify( · line 312

Quoted 7 lines

fs/xfs/xfs_trans_resv.c +2 -1

@@ -275,7 +307,8 @@ xfs_calc_create_resv_modify(
 	return xfs_calc_inode_res(mp, 2) +
 		xfs_calc_buf_res(1, mp->m_sb.sb_sectsize) +
 		(uint)XFS_FSB_TO_B(mp, 1) +
-		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1));
+		xfs_calc_buf_res(XFS_DIROP_LOG_COUNT(mp), XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 1);
 }

And this is where is starts to get complex. The modify operation can now cause a finobt merge, when means blocks will be allocated/freed. That means we now need to take into account:

* the allocation btrees: 2 trees * (max depth - 1) * block size

and anything else freeing an extent requires.

Quoted 10 lines

fs/xfs/xfs_trans_resv.c +1 -0

 /*

@@ -285,6 +318,7 @@ xfs_calc_create_resv_modify(
  *    the inode blocks allocated: XFS_IALLOC_BLOCKS * blocksize
  *    the inode btree: max depth * blocksize
  *    the allocation btrees: 2 trees * (max depth - 1) * block size
+ *    the finobt
  */
 STATIC uint
 xfs_calc_create_resv_alloc(

fs/xfs/xfs_trans_resv.c xfs_calc_create_resv_alloc( · line 334

Quoted 7 lines

fs/xfs/xfs_trans_resv.c +2 -1

@@ -295,7 +329,8 @@ xfs_calc_create_resv_alloc(
 		xfs_calc_buf_res(XFS_IALLOC_BLOCKS(mp), XFS_FSB_TO_B(mp, 1)) +
 		xfs_calc_buf_res(mp->m_in_maxlevels, XFS_FSB_TO_B(mp, 1)) +
 		xfs_calc_buf_res(XFS_ALLOCFREE_LOG_COUNT(mp, 1),
-				 XFS_FSB_TO_B(mp, 1));
+				 XFS_FSB_TO_B(mp, 1)) +
+		xfs_calc_finobt_res(mp, 0);
 }

This reservation is only for v4 superblocks - the icreate transaction reservation is used for v5 superblocks, so that's the only one you need to modify.

Cheers,

Quoted 2 lines

Dave.

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

Quoted 22 lines · Dave Chinner

Quoted 21 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

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

---
 fs/xfs/xfs_inode.c       |  4 +++-
 fs/xfs/xfs_trans_resv.c  | 47 +++++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trans_space.h |  7 ++++++-
 3 files changed, 52 insertions(+), 6 deletions(-)

fs/xfs/xfs_inode.c +0 -0

index 001aa89..57c77ed 100644
@@ -1730,7 +1730,9 @@ xfs_inactive_ifree(
 	int			error;
 

Quoted 10 lines

fs/xfs/xfs_inode.c xfs_inactive_ifree( · line 1735

Quoted 5 lines

fs/xfs/xfs_inode.c +3 -1

 	tp = xfs_trans_alloc(mp, XFS_TRANS_INACTIVE);
-	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree, 0, 0);
+	tp->t_flags |= XFS_TRANS_RESERVE;
+	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree,
+				  XFS_IFREE_SPACE_RES(mp), 0);

Can you add a comment explaining why the XFS_TRANS_RESERVE flag is used here, and why it's use won't lead to accelerated reserve pool depletion?

So this aspect of things appears to be a bit more interesting than I originally anticipated. I "reserve enabled" this transaction to facilitate the ability to free up inodes under ENOSPC conditions. Without this, the problem of failing out of xfs_inactive_ifree() (and leaving an inode chained on the unlinked list) is easily reproducible with generic/083.

The basic argument for why this is reasonable is that releasing an inode releases used space (i.e., file blocks and potentially directory blocks and inode chunks over time). That said, I can manufacture situations where this is not the case. E.g., allocate a bunch of 0-sized files,

consume remaining free space in some separate file, start removing inodes in a manner that removes a single inode per chunk or so. This creates a scenario where the inobt can be very large and the finobt very small (likely a single record). Removing the inodes in this manner reduces the likelihood of freeing up any space and thus rapidly grows the finobt towards the size of the inobt without any free space available. This might or might not qualify as sane use of the fs, but I don't think the failure scenario is acceptable as things currently stand.

I think there are several ways this can go from here. A couple ideas that have crossed my mind:

- Find a way to variably reserve the number of blocks that would be required to grow the finobt to the finobt, based on current state. This

would require the total number of blocks (not just enough for a split), so this could get complex and somewhat overbearing (i.e., a lot of space could be quietly reserved, current tracking might not be sufficient and the allocation paths could get hairy).

- Work to push the ifree transaction allocation and reservation to the unlink codepath rather than the eviction codepath. Under normal circumstances, chain the tp to the xfs_inode such that the eviction code path can grab it and run. This prevents us going into the state where an inode is unlinked without having enough space to free up. On the flip side, ENOSPC on unlink isn't very forgiving behavior to the user.

- Add some state or flags bits to the finobt and the associated ability to kill/invalidate it at runtime. Print a warning with regard to the situation that indicates performance might be affected and a repair is required to re-enable.

I think the former approach is probably overkill for something that might be a pathological situation. The latter approach is more simple, but it feels like a bit of a hack. I've experimented with it a bit, but I'm not quite sure yet if it introduces any transaction issues by allocating the unlink and ifree transactions at the same time.

Perhaps another argument could be made that it's rather unlikely we run into an fs with as many 0-sized (or sub-inode chunk sized) files as required to deplete the reserve pool without freeing any space, and we should just touch up the failure handling. E.g.,

1.) Continue to reserve enable the ifree transaction. Consider expanding the reserve pool on finobt-enabled fs' if appropriate. Note that this is not guaranteed to provide enough resources to populate the finobt to the level of the inobt without freeing up more space.
2.) Attempt a !XFS_TRANS_RESERVE tp reservation in xfs_inactive_ifree(). If fails, xfs_warn()/notice() and enable XFS_TRANS_RESERVE. 3.) Attempt XFS_TRANS_RESERVE reservation. If fails, xfs_notice() and shutdown.

And this could probably be made more intelligent to bail out sooner if we repeat XFS_TRANS_RESERVE reservations without freeing up any space, etc. Before going too far in one direction... thoughts?

[patched in the extra case from your subsequent reply]

Quoted 34 lines · Brian Foster

Quoted 22 lines · Dave Chinner

Quoted 21 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

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

---
 fs/xfs/xfs_inode.c       |  4 +++-
 fs/xfs/xfs_trans_resv.c  | 47 +++++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trans_space.h |  7 ++++++-
 3 files changed, 52 insertions(+), 6 deletions(-)

fs/xfs/xfs_inode.c +0 -0

index 001aa89..57c77ed 100644
@@ -1730,7 +1730,9 @@ xfs_inactive_ifree(
 	int			error;
 

Quoted 10 lines

fs/xfs/xfs_inode.c xfs_inactive_ifree( · line 1735

Quoted 5 lines

fs/xfs/xfs_inode.c +3 -1

 	tp = xfs_trans_alloc(mp, XFS_TRANS_INACTIVE);
-	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree, 0, 0);
+	tp->t_flags |= XFS_TRANS_RESERVE;
+	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree,
+				  XFS_IFREE_SPACE_RES(mp), 0);

Can you add a comment explaining why the XFS_TRANS_RESERVE flag is used here, and why it's use won't lead to accelerated reserve pool depletion?

Quoted 6 lines

So this aspect of things appears to be a bit more interesting than I originally anticipated. I "reserve enabled" this transaction to facilitate the ability to free up inodes under ENOSPC conditions. Without this, the problem of failing out of xfs_inactive_ifree() (and leaving an inode chained on the unlinked list) is easily reproducible with generic/083.

*nod*

Quoted 4 lines

The basic argument for why this is reasonable is that releasing an inode releases used space (i.e., file blocks and potentially directory blocks and inode chunks over time). That said, I can manufacture situations where this is not the case. E.g., allocate a bunch of 0-sized files,

Quoted 8 lines

consume remaining free space in some separate file, start removing inodes in a manner that removes a single inode per chunk or so. This creates a scenario where the inobt can be very large and the finobt very small (likely a single record). Removing the inodes in this manner reduces the likelihood of freeing up any space and thus rapidly grows the finobt towards the size of the inobt without any free space available. This might or might not qualify as sane use of the fs, but I don't think the failure scenario is acceptable as things currently stand.

Right, that can happen. But my question is this: how realistic is it that we have someone who has ENOSPC because of enough zero length files to trigger this? I've never seen an application or user try to store any significant number of zero length files, so I suspect this is a theoretical problem, not a practical one.

Indeed, the finobt only needs to grow a block for every 250-odd records for a 4k block size filesystem. Hence, IMO, the default reserve pool size of 8192 filesystem blocks is going be sufficient for most users. i.e. the case you are talking about requires (ignoring node block usage for simplicity) 250 * 8192 * 64 = 131 million zero length inodes to be present in the filesystem to have this "1 inode per chunk" freeing pattern exhaust the default reserve pool with finobt tree allocations....

Quoted 5 lines

I think there are several ways this can go from here. A couple ideas that have crossed my mind:

- Find a way to variably reserve the number of blocks that would be required to grow the finobt to the finobt, based on current state. This

Not sure what "grow the finobt to the finobt" means. There's a typo or a key word missing there ;)

Quoted 4 lines

would require the total number of blocks (not just enough for a split), so this could get complex and somewhat overbearing (i.e., a lot of space could be quietly reserved, current tracking might not be sufficient and the allocation paths could get hairy).

Doesn't seem worth the complexity to me.

Quoted 6 lines

- Work to push the ifree transaction allocation and reservation to the unlink codepath rather than the eviction codepath. Under normal circumstances, chain the tp to the xfs_inode such that the eviction code path can grab it and run. This prevents us going into the state where an inode is unlinked without having enough space to free up. On the flip side, ENOSPC on unlink isn't very forgiving behavior to the user.

That's the long term plan anyway - to move to background freeing of the inodes once they are on the unlinked list and unreferenced by the VFS. But, really, once the inode is on the unlinked list we can probably ignore the ENOSPC problem because we know that it is unlinked.

Indeed, the long term plan (along with background freeing) is to allow inode allocation direct from the unlinked lists, and that means we could leave the inodes on the unlinked lists and not care about the ENOSPC problem at all ;)

Quoted 4 lines

- Add some state or flags bits to the finobt and the associated ability to kill/invalidate it at runtime. Print a warning with regard to the situation that indicates performance might be affected and a repair is required to re-enable.

We've already got that state through the unlinked lists. Again, go back to the RFD series and look through the followup work....

Quoted 12 lines

I think the former approach is probably overkill for something that might be a pathological situation. The latter approach is more simple, but it feels like a bit of a hack. I've experimented with it a bit, but I'm not quite sure yet if it introduces any transaction issues by allocating the unlink and ifree transactions at the same time.

Perhaps another argument could be made that it's rather unlikely we run into an fs with as many 0-sized (or sub-inode chunk sized) files as required to deplete the reserve pool without freeing any space, and we should just touch up the failure handling. E.g.,

Quoted 8 lines

1.) Continue to reserve enable the ifree transaction. Consider expanding the reserve pool on finobt-enabled fs' if appropriate. Note that this is not guaranteed to provide enough resources to populate the finobt to the level of the inobt without freeing up more space.
2.) Attempt a !XFS_TRANS_RESERVE tp reservation in xfs_inactive_ifree(). If fails, xfs_warn()/notice() and enable XFS_TRANS_RESERVE. 3.) Attempt XFS_TRANS_RESERVE reservation. If fails, xfs_notice() and shutdown.

I don't think we ned to shut down. Indeed, there's no point in doing an !XFS_TRANS_RESERVE in the first place because a warning will just generate unnecessary noise in the logs.

Realistically, we can leave inodes on the unlinked list indefinitely without causing any significant problems except for there being used space that users can't account for from the namespace. Log recovery cleans them up when it runs, or blows away the unlinked list when it fails, and that results in leaked inodes. If we get to that point, xfs-repair will clean it up just fine unless there's still not enough space. At that point, it's not a problem we can solve with tools - the user has to free up some space in the filesystem....

Quoted 3 lines

And this could probably be made more intelligent to bail out sooner if we repeat XFS_TRANS_RESERVE reservations without freeing up any space, etc. Before going too far in one direction... thoughts?

Right now, I just don't think it is a case we need to be pariticularly concerned with. There are plenty of theoretical issues that can occur (including data loss) when the reserve pool is depleted because of prolonged ENOSPC issues, but the reality is that the only place we see this code being exercised is by the tests in xfstests that intentionally trigger reserve pool depletion....

Cheers,

Dave.

Quoted 35 lines · Dave Chinner

[patched in the extra case from your subsequent reply]

Quoted 32 lines · Brian Foster

Quoted 31 lines · Dave Chinner

Quoted 19 lines · Brian Foster

Create the xfs_calc_finobt_res() helper to calculate the finobt log reservation for inode allocation and free. Update XFS_IALLOC_SPACE_RES() to reserve blocks for the additional finobt insertion on inode allocation. Create XFS_IFREE_SPACE_RES() to reserve blocks for the potential finobt record insertion on inode free (i.e., if an inode chunk was previously fully allocated).

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

---
 fs/xfs/xfs_inode.c       |  4 +++-
 fs/xfs/xfs_trans_resv.c  | 47 +++++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trans_space.h |  7 ++++++-
 3 files changed, 52 insertions(+), 6 deletions(-)

fs/xfs/xfs_inode.c +0 -0

index 001aa89..57c77ed 100644

fs/xfs/xfs_inode.c xfs_inactive_ifree( · line 1735

Quoted 7 lines

fs/xfs/xfs_inode.c +3 -1

@@ -1730,7 +1730,9 @@ xfs_inactive_ifree(
 	int			error;
 
 	tp = xfs_trans_alloc(mp, XFS_TRANS_INACTIVE);
-	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree, 0, 0);
+	tp->t_flags |= XFS_TRANS_RESERVE;
+	error = xfs_trans_reserve(tp, &M_RES(mp)->tr_ifree,
+				  XFS_IFREE_SPACE_RES(mp), 0);

Can you add a comment explaining why the XFS_TRANS_RESERVE flag is used here, and why it's use won't lead to accelerated reserve pool depletion?

Quoted 18 lines

Quoted 5 lines

Perhaps another argument could be made that it's rather unlikely we run into an fs with as many 0-sized (or sub-inode chunk sized) files as required to deplete the reserve pool without freeing any space, and we should just touch up the failure handling. E.g.,

Quoted 8 lines

1.) Continue to reserve enable the ifree transaction. Consider expanding the reserve pool on finobt-enabled fs' if appropriate. Note that this is not guaranteed to provide enough resources to populate the finobt to the level of the inobt without freeing up more space.
2.) Attempt a !XFS_TRANS_RESERVE tp reservation in xfs_inactive_ifree(). If fails, xfs_warn()/notice() and enable XFS_TRANS_RESERVE. 3.) Attempt XFS_TRANS_RESERVE reservation. If fails, xfs_notice() and shutdown.

I don't think we ned to shut down. Indeed, there's no point in doing an !XFS_TRANS_RESERVE in the first place because a warning will just generate unnecessary noise in the logs.

Quoted 9 lines

Realistically, we can leave inodes on the unlinked list indefinitely without causing any significant problems except for there being used space that users can't account for from the namespace. Log recovery cleans them up when it runs, or blows away the unlinked list when it fails, and that results in leaked inodes. If we get to that point, xfs-repair will clean it up just fine unless there's still not enough space. At that point, it's not a problem we can solve with tools - the user has to free up some space in the filesystem....

Ok, the current failure behavior (as unlikely as it seems to hit) seems less hasty given the roadmap for improved unlinked list management.

I'm not sure how log recovery plays into things unless there is a crash. In my experiments, the inodes are simply never freed and linger on the unlinked list until repair. Repair moves everything to lost+found as opposed to freeing (I presume since the inodes are still "allocated" after all), but repairs the fs nonetheless.

Quoted 6 lines

Right, that can happen. But my question is this: how realistic is it that we have someone who has ENOSPC because of enough zero length files to trigger this? I've never seen an application or user try to store any significant number of zero length files, so I suspect this is a theoretical problem, not a practical one.

Probably not very realistic. ;) The only thing I know that does rely on some zero-length files is gluster distribution to represent "link files" when one a file that hashes to one server ends up stored on another. Even then, I don't see how we would ever have a situation where those link files exist in such massive numbers and are removed in bulk. So it's likely a pathological scenario.

Quoted 7 lines · Brian Foster

Quoted 6 lines

Right, that can happen. But my question is this: how realistic is it that we have someone who has ENOSPC because of enough zero length files to trigger this? I've never seen an application or user try to store any significant number of zero length files, so I suspect this is a theoretical problem, not a practical one.

Quoted 6 lines

Probably not very realistic. ;) The only thing I know that does rely on some zero-length files is gluster distribution to represent "link files" when one a file that hashes to one server ends up stored on another. Even then, I don't see how we would ever have a situation where those link files exist in such massive numbers and are removed in bulk. So it's likely a pathological scenario.

Zero data blocks are the only case for device nodes or fifos, very common for symlinks that can be stored inline, and not unusual for directories.

A newly allocated inode chunk, by definition, has at least one free inode, so a record is always inserted into the finobt.

Create the xfs_inobt_insert() helper from existing code to insert a record in an inobt based on the provided BTNUM. Update xfs_ialloc_ag_alloc() to invoke the helper for the existing XFS_BTNUM_INO tree and XFS_BTNUM_FINO tree, if enabled.

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

Replace xfs_dialloc_ag() with an implementation that looks for a record in the finobt. The finobt only tracks records with at least one free inode. This eliminates the need for the intra-ag scan in the original algorithm. Once the inode is allocated, update the finobt appropriately (possibly removing the record) as well as the inobt.

Move the original xfs_dialloc_ag() algorithm to xfs_dialloc_ag_slow() and fall back as such if finobt support is not enabled.

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

---
 fs/xfs/xfs_ialloc.c | 211 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 210 insertions(+), 1 deletion(-)

fs/xfs/xfs_ialloc.c +0 -0

index bdaab76..afc9840 100644

fs/xfs/xfs_ialloc.c +77 -0

+	struct xfs_mount		*mp = tp->t_mountp;
+	struct xfs_agi			*agi = XFS_BUF_TO_AGI(agbp);
+	xfs_agnumber_t			agno = be32_to_cpu(agi->agi_seqno);
+	xfs_agnumber_t			pagno = XFS_INO_TO_AGNO(mp, parent);
+	xfs_agino_t			pagino = XFS_INO_TO_AGINO(mp, parent);
+	struct xfs_perag		*pag;
+	struct xfs_btree_cur		*cur;
+	struct xfs_btree_cur		*tcur;
+	struct xfs_inobt_rec_incore	rec;
+	struct xfs_inobt_rec_incore	trec;
+	xfs_ino_t			ino;
+	int				error;
+	int				offset;
+	int				i, j;
+
+	if (!xfs_sb_version_hasfinobt(&mp->m_sb))
+		return xfs_dialloc_ag_slow(tp, agbp, parent, inop);
+
+	pag = xfs_perag_get(mp, agno);
+
+	/*
+	 * If pagino is 0 (this is the root inode allocation) use newino.
+	 * This must work because we've just allocated some.
+	 */
+	if (!pagino)
+		pagino = be32_to_cpu(agi->agi_newino);
+
+	cur = xfs_inobt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_FINO);
+
+	error = xfs_check_agi_freecount(cur, agi);
+	if (error)
+		goto error_cur;
+
+	if (agno == pagno) {
+		/*
+		 * We're in the same AG as the parent inode so allocate the
+		 * closest inode to the parent.
+		 */
+		error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i);
+		if (error)
+			goto error_cur;
+		if (i == 1) {
+			error = xfs_inobt_get_rec(cur, &rec, &i);
+			if (error)
+				goto error_cur;
+			XFS_WANT_CORRUPTED_GOTO(i == 1, error_cur);
+
+			/*
+			 * See if we've landed in the parent inode record. The
+			 * finobt only tracks chunks with at least one free
+			 * inode, so record existence is enough.
+			 */
+			if (pagino >= rec.ir_startino &&
+			    pagino < (rec.ir_startino + XFS_INODES_PER_CHUNK))
+				goto alloc_inode;
+		}
+
+		error = xfs_btree_dup_cursor(cur, &tcur);
+		if (error) 
+			goto error_cur;
+
+		error = xfs_inobt_lookup(tcur, pagino, XFS_LOOKUP_GE, &j);
+		if (error)
+			goto error_tcur;
+		if (j == 1) {
+			error = xfs_inobt_get_rec(tcur, &trec, &j);
+			if (error)
+				goto error_tcur;
+			XFS_WANT_CORRUPTED_GOTO(j == 1, error_tcur);
+		}
+
+		if (i == 1 && j == 1) {
+			if ((pagino - rec.ir_startino + XFS_INODES_PER_CHUNK - 1) >
+			    (trec.ir_startino - pagino)) {
+				rec = trec;
+				xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+				cur = tcur;

fs/xfs/xfs_ialloc.c +21 -0

+	} else {
+		/*
+		 * Different AG from the parent inode. Check the record for the
+		 * most recently allocated inode.
+		 */
+		if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
+			error = xfs_inobt_lookup(cur, agi->agi_newino,
+						 XFS_LOOKUP_EQ, &i);
+			if (error)
+				goto error_cur;
+			if (i == 1) {
+				error = xfs_inobt_get_rec(cur, &rec, &i);
+				if (error)
+					goto error_cur;
+				XFS_WANT_CORRUPTED_GOTO(i == 1, error_cur);
+				goto alloc_inode;
+			}
+		}
+
+		/*
+		 * Allocate the first inode available in the AG.

fs/xfs/xfs_ialloc.c +16 -0

+	}
+
+alloc_inode:
+	offset = xfs_lowbit64(rec.ir_free);
+	ASSERT(offset >= 0);
+	ASSERT(offset < XFS_INODES_PER_CHUNK);
+	ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
+				   XFS_INODES_PER_CHUNK) == 0);
+	ino = XFS_AGINO_TO_INO(mp, agno, rec.ir_startino + offset);
+
+	/*
+	 * Modify or remove the finobt record.
+	 */
+	rec.ir_free &= ~XFS_INOBT_MASK(offset);
+	rec.ir_freecount--;
+	if (rec.ir_freecount) 

fs/xfs/xfs_ialloc.c +26 -0

+
+	error = xfs_check_agi_freecount(tcur, agi);
+	if (error)
+		goto error_tcur;
+
+	error = xfs_inobt_lookup(tcur, rec.ir_startino, XFS_LOOKUP_EQ, &i);
+	if (error)
+		goto error_tcur;
+	XFS_WANT_CORRUPTED_GOTO(i == 1, error_tcur);
+
+	error = xfs_inobt_get_rec(tcur, &trec, &i);
+	if (error)
+		goto error_tcur;
+	XFS_WANT_CORRUPTED_GOTO(i == 1, error_tcur);
+	ASSERT((XFS_AGINO_TO_OFFSET(mp, trec.ir_startino) %
+				   XFS_INODES_PER_CHUNK) == 0);
+
+	trec.ir_free &= ~XFS_INOBT_MASK(offset);
+	trec.ir_freecount--;
+
+	XFS_WANT_CORRUPTED_GOTO((rec.ir_free == trec.ir_free) &&
+				(rec.ir_freecount == trec.ir_freecount),
+				error_tcur);
+
+	error = xfs_inobt_update(tcur, &trec);
+	if (error)

Quoted 16 lines · Brian Foster

Replace xfs_dialloc_ag() with an implementation that looks for a record in the finobt. The finobt only tracks records with at least one free inode. This eliminates the need for the intra-ag scan in the original algorithm. Once the inode is allocated, update the finobt appropriately (possibly removing the record) as well as the inobt.

Move the original xfs_dialloc_ag() algorithm to xfs_dialloc_ag_slow() and fall back as such if finobt support is not enabled.

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

---
 fs/xfs/xfs_ialloc.c | 211 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 210 insertions(+), 1 deletion(-)

fs/xfs/xfs_ialloc.c xfs_ialloc_get_rec( · line 729

Quoted 13 lines

fs/xfs/xfs_ialloc.c +1 -1

index bdaab76..afc9840 100644
@@ -723,7 +723,7 @@ xfs_ialloc_get_rec(
  * available.
  */
 STATIC int
-xfs_dialloc_ag(
+xfs_dialloc_ag_slow(
 	struct xfs_trans	*tp,
 	struct xfs_buf		*agbp,
 	xfs_ino_t		parent,

OK, though I would have called it xfs_dialloc_ag_from_inobt() or something similar to indicate what tree it is walking....

fs/xfs/xfs_ialloc.c error0: · line 990

Quoted 7 lines

fs/xfs/xfs_ialloc.c +7 -0

+STATIC int
+xfs_dialloc_ag(
+	struct xfs_trans	*tp,
+	struct xfs_buf		*agbp,
+	xfs_ino_t		parent,
+	xfs_ino_t		*inop)
+{

Initial thought: Wow, long, long function. How can we split this up?

Quoted 77 lines

fs/xfs/xfs_ialloc.c +77 -0

+	struct xfs_mount		*mp = tp->t_mountp;
+	struct xfs_agi			*agi = XFS_BUF_TO_AGI(agbp);
+	xfs_agnumber_t			agno = be32_to_cpu(agi->agi_seqno);
+	xfs_agnumber_t			pagno = XFS_INO_TO_AGNO(mp, parent);
+	xfs_agino_t			pagino = XFS_INO_TO_AGINO(mp, parent);
+	struct xfs_perag		*pag;
+	struct xfs_btree_cur		*cur;
+	struct xfs_btree_cur		*tcur;
+	struct xfs_inobt_rec_incore	rec;
+	struct xfs_inobt_rec_incore	trec;
+	xfs_ino_t			ino;
+	int				error;
+	int				offset;
+	int				i, j;
+
+	if (!xfs_sb_version_hasfinobt(&mp->m_sb))
+		return xfs_dialloc_ag_slow(tp, agbp, parent, inop);
+
+	pag = xfs_perag_get(mp, agno);
+
+	/*
+	 * If pagino is 0 (this is the root inode allocation) use newino.
+	 * This must work because we've just allocated some.
+	 */
+	if (!pagino)
+		pagino = be32_to_cpu(agi->agi_newino);
+
+	cur = xfs_inobt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_FINO);
+
+	error = xfs_check_agi_freecount(cur, agi);
+	if (error)
+		goto error_cur;
+
+	if (agno == pagno) {
+		/*
+		 * We're in the same AG as the parent inode so allocate the
+		 * closest inode to the parent.
+		 */
+		error = xfs_inobt_lookup(cur, pagino, XFS_LOOKUP_LE, &i);
+		if (error)
+			goto error_cur;
+		if (i == 1) {
+			error = xfs_inobt_get_rec(cur, &rec, &i);
+			if (error)
+				goto error_cur;
+			XFS_WANT_CORRUPTED_GOTO(i == 1, error_cur);
+
+			/*
+			 * See if we've landed in the parent inode record. The
+			 * finobt only tracks chunks with at least one free
+			 * inode, so record existence is enough.
+			 */
+			if (pagino >= rec.ir_startino &&
+			    pagino < (rec.ir_startino + XFS_INODES_PER_CHUNK))
+				goto alloc_inode;
+		}
+
+		error = xfs_btree_dup_cursor(cur, &tcur);
+		if (error) 
+			goto error_cur;
+
+		error = xfs_inobt_lookup(tcur, pagino, XFS_LOOKUP_GE, &j);
+		if (error)
+			goto error_tcur;
+		if (j == 1) {
+			error = xfs_inobt_get_rec(tcur, &trec, &j);
+			if (error)
+				goto error_tcur;
+			XFS_WANT_CORRUPTED_GOTO(j == 1, error_tcur);
+		}
+
+		if (i == 1 && j == 1) {
+			if ((pagino - rec.ir_startino + XFS_INODES_PER_CHUNK - 1) >
+			    (trec.ir_startino - pagino)) {
+				rec = trec;
+				xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+				cur = tcur;

fs/xfs/xfs_ialloc.c error0: · line 1077

Quoted 10 lines

fs/xfs/xfs_ialloc.c +10 -0

+			} else {
+				xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
+			}
+		} else if (j == 1) {
+			rec = trec;
+			xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+			cur = tcur;
+		} else {
+			xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
+		}

That entire branch can be easily factored into:

		error = xfs_dialloc_ag_finobt_near(cur, pagino, &rec);

/*
* Allocate as close to the target agino as possible */
static int
xfs_dialloc_ag_finobt_near(
struct xfs_btree_cur *cur,
xfs_agino_t agino,
struct xfs_inobt_rec_incore *rec)

{
	struct xfs_btree_cur	*rcur;	/* cursor for right search */
	struct xfs_inobt_rec_incore rrec; /* and the record used */
	int		error;
	int		i;
	int		l;

	error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_LE, &i);
	if (error)
		return error;

	if (i == 1) {
		error = xfs_inobt_get_rec(cur, rec, &i);
		if (error)
			return error;
		XFS_WANT_CORRUPTED_RETURN(i == 1);

		/*
		 * See if we've landed in the target inode record. The
		 * finobt only tracks chunks with at least one free
		 * inode, so record existence is enough.
		 */
		if (agino >= rec->ir_startino &&
		    agino < (rec->ir_startino + XFS_INODES_PER_CHUNK))
			return 0;
	}

	error = xfs_btree_dup_cursor(cur, &rcur);
	if (error)
		return error;

	error = xfs_inobt_lookup(rcur, agino, XFS_LOOKUP_GE, &j);
	if (error)
		goto error_rcur;
	if (j == 1) {
		error = xfs_inobt_get_rec(rcur, &rrec, &j);
		if (error)
			goto error_rcur;
		XFS_WANT_CORRUPTED_GOTO(j == 1, error_rcur);
	}

	if (i == 1 && j == 1) {
		/*
		 * both left and right records are valid, so choose
		 * the closer inode chunk to the target.
		 */
		if ((agino - rec.ir_startino + XFS_INODES_PER_CHUNK - 1) >
					(rrec.ir_startino - agino)) {
			*rec = rrec;
			xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
			cur = rcur;
		} else {
			xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR);
		}
	} else if (j == 1) {
		/* only right record is valid */
		*rec = rrec;
		xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
		cur = rcur;
	} else {
		/* Found neither left nor right.
		xfs_btree_del_cursor(rcur, XFS_BTREE_NOERROR);
	}
	return 0;

error_rcur:

	xfs_btree_del_cursor(rcur, XFS_BTREE_ERROR);
	return error;
}

Quoted 26 lines

fs/xfs/xfs_ialloc.c +26 -0

+	} else {
+		/*
+		 * Different AG from the parent inode. Check the record for the
+		 * most recently allocated inode.
+		 */
+		if (agi->agi_newino != cpu_to_be32(NULLAGINO)) {
+			error = xfs_inobt_lookup(cur, agi->agi_newino,
+						 XFS_LOOKUP_EQ, &i);
+			if (error)
+				goto error_cur;
+			if (i == 1) {
+				error = xfs_inobt_get_rec(cur, &rec, &i);
+				if (error)
+					goto error_cur;
+				XFS_WANT_CORRUPTED_GOTO(i == 1, error_cur);
+				goto alloc_inode;
+			}
+		}
+
+		/*
+		 * Allocate the first inode available in the AG.
+		 */
+		error = xfs_inobt_lookup(cur, 0, XFS_LOOKUP_GE, &i);
+		if (error)
+			goto error_cur;
+		XFS_WANT_CORRUPTED_GOTO(i == 1, error_cur);

fs/xfs/xfs_ialloc.c error0: · line 1036

Quoted 5 lines

fs/xfs/xfs_ialloc.c +5 -0

+
+		error = xfs_inobt_get_rec(cur, &rec, &i);
+		if (error)
+			goto error_cur;
+		XFS_WANT_CORRUPTED_GOTO(i == 1, error_cur);

And that can be factored in a similar manner in
xfs_dialloc_ag_newino()....

Quoted 16 lines

fs/xfs/xfs_ialloc.c +16 -0

+	}
+
+alloc_inode:
+	offset = xfs_lowbit64(rec.ir_free);
+	ASSERT(offset >= 0);
+	ASSERT(offset < XFS_INODES_PER_CHUNK);
+	ASSERT((XFS_AGINO_TO_OFFSET(mp, rec.ir_startino) %
+				   XFS_INODES_PER_CHUNK) == 0);
+	ino = XFS_AGINO_TO_INO(mp, agno, rec.ir_startino + offset);
+
+	/*
+	 * Modify or remove the finobt record.
+	 */
+	rec.ir_free &= ~XFS_INOBT_MASK(offset);
+	rec.ir_freecount--;
+	if (rec.ir_freecount) 

fs/xfs/xfs_ialloc.c error0: · line 1134

Quoted 10 lines

fs/xfs/xfs_ialloc.c +10 -0

+		error = xfs_inobt_update(cur, &rec);
+	else
+		error = xfs_btree_delete(cur, &i);
+	if (error)
+		goto error_cur;
+
+	/*
+	 * Lookup and modify the equivalent record in the inobt.
+	 */
+	tcur = xfs_inobt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_INO);

In case ou hadn't guessed, I don't like the "tcur/trec" variables because they make me thing "temporary" which they aren't. In this case it is the inobt cursor and record....

In fact, this whole segment could be factored into a function like xfs_dialloc_ag_inobt_update(), hence removing the second cursor from xfs_dialloc_ag() function altogether and that would clean a lot of the logic up....

Quoted 32 lines

fs/xfs/xfs_ialloc.c +32 -0

+
+	error = xfs_check_agi_freecount(tcur, agi);
+	if (error)
+		goto error_tcur;
+
+	error = xfs_inobt_lookup(tcur, rec.ir_startino, XFS_LOOKUP_EQ, &i);
+	if (error)
+		goto error_tcur;
+	XFS_WANT_CORRUPTED_GOTO(i == 1, error_tcur);
+
+	error = xfs_inobt_get_rec(tcur, &trec, &i);
+	if (error)
+		goto error_tcur;
+	XFS_WANT_CORRUPTED_GOTO(i == 1, error_tcur);
+	ASSERT((XFS_AGINO_TO_OFFSET(mp, trec.ir_startino) %
+				   XFS_INODES_PER_CHUNK) == 0);
+
+	trec.ir_free &= ~XFS_INOBT_MASK(offset);
+	trec.ir_freecount--;
+
+	XFS_WANT_CORRUPTED_GOTO((rec.ir_free == trec.ir_free) &&
+				(rec.ir_freecount == trec.ir_freecount),
+				error_tcur);
+
+	error = xfs_inobt_update(tcur, &trec);
+	if (error)
+		goto error_tcur;
+
+	/*
+	 * Update the perag and superblock.
+	 */
+	be32_add_cpu(&agi->agi_freecount, -1);

fs/xfs/xfs_ialloc.c error0: · line 1170

Quoted 4 lines

fs/xfs/xfs_ialloc.c +4 -0

+	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
+	pag->pagi_freecount--;
+
+	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);

This will need to be done before you update the inobt, though, so you can run the xfs_check_agi_freecount() count in it and it will come out correct....

Cheers,

Dave.

On Tue, Feb 04, 2014 at 12:49:37PM -0500, Brian Foster wrote:

fs/xfs/xfs_ialloc.c error0: · line 1134

Quoted 4 lines

fs/xfs/xfs_ialloc.c +4 -0

+	/*
+	 * Lookup and modify the equivalent record in the inobt.
+	 */
+	tcur = xfs_inobt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_INO);

In case ou hadn't guessed, I don't like the "tcur/trec" variables because they make me thing "temporary" which they aren't. In this case it is the inobt cursor and record....

In fact, this whole segment could be factored into a function like xfs_dialloc_ag_inobt_update(), hence removing the second cursor from xfs_dialloc_ag() function altogether and that would clean a lot of the logic up....

Quoted 4 lines

fs/xfs/xfs_ialloc.c +4 -0

+	/*
+	 * Update the perag and superblock.
+	 */
+	be32_add_cpu(&agi->agi_freecount, -1);

fs/xfs/xfs_ialloc.c error0: · line 1170

Quoted 4 lines

fs/xfs/xfs_ialloc.c +4 -0

+	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
+	pag->pagi_freecount--;
+
+	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);

This will need to be done before you update the inobt, though, so you can run the xfs_check_agi_freecount() count in it and it will come out correct....

Cheers,

Dave.

Quoted 1 line · Dave Chinner

On Tue, Feb 04, 2014 at 12:49:37PM -0500, Brian Foster wrote:

...

Quoted 14 lines

fs/xfs/xfs_ialloc.c error0: · line 1134

Quoted 4 lines

fs/xfs/xfs_ialloc.c +4 -0

+	/*
+	 * Lookup and modify the equivalent record in the inobt.
+	 */
+	tcur = xfs_inobt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_INO);

In case ou hadn't guessed, I don't like the "tcur/trec" variables because they make me thing "temporary" which they aren't. In this case it is the inobt cursor and record....

In fact, this whole segment could be factored into a function like xfs_dialloc_ag_inobt_update(), hence removing the second cursor from xfs_dialloc_ag() function altogether and that would clean a lot of the logic up....

...

Quoted 4 lines

Quoted 4 lines

fs/xfs/xfs_ialloc.c +4 -0

+	/*
+	 * Update the perag and superblock.
+	 */
+	be32_add_cpu(&agi->agi_freecount, -1);

Quoted 9 lines

fs/xfs/xfs_ialloc.c error0: · line 1170

Quoted 4 lines

fs/xfs/xfs_ialloc.c +4 -0

+	xfs_ialloc_log_agi(tp, agbp, XFS_AGI_FREECOUNT);
+	pag->pagi_freecount--;
+
+	xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -1);

This will need to be done before you update the inobt, though, so you can run the xfs_check_agi_freecount() count in it and it will come out correct....

After cleaning up some of this code and taking a closer look, I end up with something just short of complete removal of the inobt cursor in this function. Reason being... the point above with regard to checking the btrees against the agi freecount pre and post modification.

Refactor xfs_difree() in preparation for the finobt. xfs_difree() performs the validity checks against the ag and reads the agi header. The work of physically updating the inode allocation btree is pushed down into the new xfs_difree_inobt() helper.

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

An inode free operation can have several effects on the finobt. If all inodes have been freed and the chunk deallocated, we remove the finobt record. If the inode chunk was previously full, we must insert a new record based on the existing inobt record. Otherwise, we modify the record in place.

Create the xfs_ifree_finobt() function to identify the potential scenarios and update the finobt appropriately.

fs/xfs/xfs_ialloc.c +11 -0

+	if (rec.ir_freecount == XFS_IALLOC_INODES(mp) &&
+	    !(mp->m_flags & XFS_MOUNT_IKEEP)) {
+		/*
+		 * If all inodes are free and we're in !ikeep mode, the entire
+		 * inode chunk has been deallocated. Remove the record from the
+		 * finobt.
+		 */
+		error = xfs_btree_delete(cur, &i);
+		if (error)
+			goto error;
+		ASSERT(i == 1);

Define the XFS_FSOP_GEOM_FLAGS_FINOBT fs geometry flag and set the associated bit if the filesystem supports the free inode btree.

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

Add the finobt feature bit to the list of known features. As of this point, the kernel code knows how to mount and manage both finobt and non-finobt formatted filesystems.

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