[PATCH v2 0/3] xfs: support removal of multi-record inode chunks

[PATCH v2 0/3] xfs: support removal of multi-record inode chunks

[Brian Foster]

Hi all,

This is an old series I'm dusting off that helps extend XFS' typical
dynamic inode chunk behavior to large block size filesystems. While XFS
currently supports such large block sizes, we don't ever remove inode
records on filesystems with a block size large enough such that a single
block covers more than one inode chunk.

This has been tested on ppc64 with a 64k block size and on other arches
(x86-64, i386) with more standard 4k blocksize configurations.

Brian

v2:
- Rebase to latest for-next.
v1: http://oss.sgi.com/pipermail/xfs/2015-May/041814.html

Brian Foster (3):
  xfs: create helper to delete multiple inobt records
  xfs: remove entire inode chunks when all inodes are free
  xfs: inobt record insert/delete tracepoints

 fs/xfs/libxfs/xfs_ialloc.c | 270 +++++++++++++++++++++++++++++++++++++++++----
 fs/xfs/xfs_trace.h         |  32 ++++++
 2 files changed, 281 insertions(+), 21 deletions(-)

-- 
2.5.5

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH v2 1/3] xfs: create helper to delete multiple inobt records

[Brian Foster]

In most cases an inode chunk is tracked by a single inode record. With
large block size support up to 64k, however, XFS supports conditions
where a single block might be large enough to allocate an inode chunk
that requires multiple inobt records. For example, an inode record is
fixed at 64 inodes. With a 64k block size, a 512b inode size results in
128-inode chunks and thus requires 2 inobt records per-chunk.

This is handled appropriately at inode allocation time via insertion of
multiple inobt records to span the chunk. We currently have no mechanism
to delete multiple records nor broader chunk context for a particular
record at inode deletion time. Therefore, inode chunks on such
filesystems are never freed and result in non-recoverable space
consumption for the lifetime of the filesystem.

Create the xfs_inobt_delete() helper to remove several inobt records at
a time. Call the helper from the appropriate locations instead of
xfs_btree_delete(). Note that we still do not have the requisite chunk
context at inode deletion time to delete multiple records and therefore
can still only delete records that map to full chunks.

This patch does not alter current behavior but provides a mechanism to
be used by future work that provides the appropriate chunk context.

Signed-off-by: Brian Foster <bfoster@redhat.com>
---
 fs/xfs/libxfs/xfs_ialloc.c | 56 +++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 53 insertions(+), 3 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
index 22297f9..67a4f3f 100644
--- a/fs/xfs/libxfs/xfs_ialloc.c
+++ b/fs/xfs/libxfs/xfs_ialloc.c
@@ -200,6 +200,53 @@ xfs_inobt_insert(
 }
 
 /*
+ * Delete a series of records from the inode btree. Handle multiple records as
+ * an inode chunk might consist of more than one record for large block sizes.
+ */
+static int
+xfs_inobt_delete(
+	struct xfs_mount		*mp,
+	struct xfs_btree_cur		*cur,
+	xfs_agnumber_t			agno,
+	xfs_agino_t			agino,
+	int				ilen)
+{
+	struct xfs_inobt_rec_incore	rec;
+	int				error;
+	int				i;
+
+	ASSERT(ilen % XFS_INODES_PER_CHUNK == 0);
+
+	while (ilen > 0) {
+		error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_EQ, &i);
+		if (error)
+			goto out_error;
+		XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
+
+		/* make sure the record is what we expect */
+		error = xfs_inobt_get_rec(cur, &rec, &i);
+		if (error)
+			goto out_error;
+		XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
+		XFS_WANT_CORRUPTED_GOTO(mp, rec.ir_startino == agino,
+					out_error);
+
+		error = xfs_btree_delete(cur, &i);
+		if (error)
+			goto out_error;
+		XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
+
+		agino += XFS_INODES_PER_CHUNK;
+		ilen -= XFS_INODES_PER_CHUNK;
+	}
+
+	return 0;
+
+out_error:
+	return error;
+}
+
+/*
  * Verify that the number of free inodes in the AGI is correct.
  */
 #ifdef DEBUG
@@ -1971,8 +2018,10 @@ xfs_difree_inobt(
 		xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen);
 		xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1));
 
-		if ((error = xfs_btree_delete(cur, &i))) {
-			xfs_warn(mp, "%s: xfs_btree_delete returned error %d.",
+		error = xfs_inobt_delete(mp, cur, agno, rec.ir_startino,
+					 XFS_INODES_PER_CHUNK);
+		if (error) {
+			xfs_warn(mp, "%s: xfs_inobt_delete returned error %d.",
 				__func__, error);
 			goto error0;
 		}
@@ -2089,7 +2138,8 @@ xfs_difree_finobt(
 	if (rec.ir_free == XFS_INOBT_ALL_FREE &&
 	    mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK &&
 	    !(mp->m_flags & XFS_MOUNT_IKEEP)) {
-		error = xfs_btree_delete(cur, &i);
+		error = xfs_inobt_delete(mp, cur, agno, rec.ir_startino,
+					 XFS_INODES_PER_CHUNK);
 		if (error)
 			goto error;
 		ASSERT(i == 1);
-- 
2.5.5

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH v2 2/3] xfs: remove entire inode chunks when all inodes are free

[Brian Foster]

Inode chunks are typically removed when the last allocated inode tracked
by the inobt record is freed. However, this only occurs under
circumstances where a chunk is tracked by a single inobt record because
only the context for the single record is available at the time an inode
is freed.

Add infrastructure to detect whether the overall chunk that happens to
own a particular inobt record is free. The xfs_inobt_ischunkfree()
helper first considers the more likely single-record-per-chunk case to
avoid unnecessary overhead. Otherwise, it uses the xfs_inobt_peek() low
level helper to tally the total real and free inode count over a set of
records that map to a chunk. If the entire chunk is free, the starting
agino of the chunk is returned.

We can remove multiple inobt records of a chunk now that chunk free
state is available. Update the xfs_inobt_delete() callers to free an
entire chunk at a time based on the variable inode allocation count in
the mount structure. Note that this is safe from a transaction
standpoint due to the same reasoning that multiple inode record
insertion is safe from xfs_inobt_insert(). Specifically, the transaction
reservation covers enough for a single bottom-to-top tree split or
merge. We can safely insert or remove ~50% of an inobt leaf block's
worth of records under this reservation and the maximum possible ratio
of inode records to inode chunks is 4:1 (i.e., maximum 64k block size
with minimum 256b inode size).

Signed-off-by: Brian Foster <bfoster@redhat.com>
---
 fs/xfs/libxfs/xfs_ialloc.c | 206 ++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 187 insertions(+), 19 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
index 67a4f3f..fdaeee8 100644
--- a/fs/xfs/libxfs/xfs_ialloc.c
+++ b/fs/xfs/libxfs/xfs_ialloc.c
@@ -40,6 +40,9 @@
 #include "xfs_trace.h"
 #include "xfs_log.h"
 
+STATIC int
+xfs_ialloc_next_rec(struct xfs_btree_cur *, struct xfs_inobt_rec_incore *,
+		    int *, int);
 
 /*
  * Allocation group level functions.
@@ -247,6 +250,155 @@ out_error:
 }
 
 /*
+ * Peek forward in the provided inobt cursor and sum up the real and free inode
+ * counts. The returned count covers the range of [agino,agino+len). Absent
+ * records do not affect the count.
+ */
+static int
+xfs_inobt_peek(
+	struct xfs_mount		*mp,
+	struct xfs_btree_cur		*cur,
+	xfs_agino_t			agino,		/* start agino */
+	int				ilen,		/* range length */
+	int				*count,		/* out: inode count */
+	int				*freecount)	/* out: free count */
+{
+	struct xfs_inobt_rec_incore	rec;
+	xfs_agino_t			agino_end;
+	int				error;
+	int				i;
+
+	ASSERT(ilen % XFS_INODES_PER_CHUNK == 0);
+	agino_end = agino + ilen;
+	*count = *freecount = 0;
+
+	/*
+	 * Look up the first at or beyond the start of the range. Note that
+	 * records for legitimate inode chunks might not exist if we're looking
+	 * at the finobt.
+	 */
+	error = xfs_inobt_lookup(cur, agino, XFS_LOOKUP_GE, &i);
+	if (error)
+		goto out_error;
+	if (i == 0)
+		return 0;
+
+	error = xfs_inobt_get_rec(cur, &rec, &i);
+	if (error)
+		goto out_error;
+	XFS_WANT_CORRUPTED_GOTO(mp, i == 1, out_error);
+
+	/*
+	 * Sum the real and free inode counts across all records in the range.
+	 */
+	while (rec.ir_startino < agino_end) {
+		*count += rec.ir_count;
+		*freecount += rec.ir_freecount;
+
+		error = xfs_ialloc_next_rec(cur, &rec, &i, 0);
+		if (error)
+			goto out_error;
+		if (i)	/* done */
+			break;
+	}
+
+	return 0;
+
+out_error:
+	return error;
+}
+
+/*
+ * Determine whether an inode chunk covered by a particular inobt record is
+ * free. This handles large block size cases where the inode chunk requires
+ * multiple inobt records by mapping from the inode offset of the first inode in
+ * the provided record to the record with inode offset 0 in the chunk. From
+ * there we determine whether each record in the chunk is completely free.
+ *
+ * An in-core record of the chunk to check is passed in rec. Any record that
+ * covers a portion of the chunk is suitable. The in-core record must be
+ * modified in advance if an inode is being freed. The expected free inode count
+ * for a free chunk is passed in icount. This is generally mp->m_ialloc_inos,
+ * but the caller must account for when an inode to be freed is not yet
+ * reflected as such in the inobt.
+ *
+ * If the chunk is free, the starting agino of the chunk is returned in
+ * freeagino. Otherwise, freeagino is set to NULLAGINO.
+ */
+static int
+xfs_inobt_ischunkfree(
+	struct xfs_mount		*mp,
+	struct xfs_btree_cur		*ocur,
+	struct xfs_inobt_rec_incore	*rec,
+	int				icount,/* icount for free chunk */
+	xfs_agino_t			*freeagino)/* out: first free agino */
+{
+	struct xfs_btree_cur		*cur;
+	xfs_agino_t			agino;
+	xfs_agblock_t			agbno;
+	int				count;
+	int				freecount;
+	int				error;
+
+	ASSERT(icount <= mp->m_ialloc_inos);
+
+	*freeagino = NULLAGINO;
+
+	/* if the record isn't free, the chunk certainly isn't */
+	if (rec->ir_free != XFS_INOBT_ALL_FREE)
+		return 0;
+
+	/*
+	 * The record is free so if the chunk corresponds to a single record, it
+	 * is free as well.
+	 */
+	if (mp->m_ialloc_inos == XFS_INODES_PER_CHUNK) {
+		ASSERT(rec->ir_free == XFS_INOBT_ALL_FREE);
+		*freeagino = rec->ir_startino;
+		return 0;
+	}
+
+	/*
+	 * A chunk corresponds to multiple inobt records. This typically occurs
+	 * for large block sizes where a single block of inodes requires
+	 * multiple records.
+	 *
+	 * Get the record that is aligned to the start of the block and verify
+	 * whether all inodes across the chunk are free. Dup the cursor so we
+	 * don't affect the caller's inobt update operation in progress and sum
+	 * the free inodes across the chunk.
+	 */
+	ASSERT(mp->m_ialloc_inos > XFS_INODES_PER_CHUNK);
+	error = xfs_btree_dup_cursor(ocur, &cur);
+	if (error)
+		return error;
+
+	/* get the agblock and the inode at offset 0 */
+	agbno = XFS_AGINO_TO_AGBNO(mp, rec->ir_startino);
+	agino = XFS_OFFBNO_TO_AGINO(mp, agbno, 0);
+
+	error = xfs_inobt_peek(mp, cur, agino, mp->m_ialloc_inos, &count,
+			       &freecount);
+	if (error)
+		goto out_cur;
+
+	/*
+	 * Check the free inode count against the count that indicates a free
+	 * chunk. Sparse records are irrelevant in this context since this is a
+	 * single block allocation.
+	 */
+	if (freecount == icount)
+		*freeagino = agino;
+
+	xfs_btree_del_cursor(cur, XFS_BTREE_NOERROR);
+	return 0;
+
+out_cur:
+	xfs_btree_del_cursor(cur, XFS_BTREE_ERROR);
+	return error;
+}
+
+/*
  * Verify that the number of free inodes in the AGI is correct.
  */
 #ifdef DEBUG
@@ -1950,6 +2102,7 @@ xfs_difree_inobt(
 	int				error;
 	int				i;
 	int				off;
+	xfs_agino_t			freeagino;
 
 	ASSERT(agi->agi_magicnum == cpu_to_be32(XFS_AGI_MAGIC));
 	ASSERT(XFS_AGINO_TO_AGBNO(mp, agino) < be32_to_cpu(agi->agi_length));
@@ -1992,23 +2145,38 @@ xfs_difree_inobt(
 	rec.ir_freecount++;
 
 	/*
-	 * When an inode chunk is free, it becomes eligible for removal. Don't
-	 * remove the chunk if the block size is large enough for multiple inode
-	 * chunks (that might not be free).
+	 * An inode chunk becomes eligible for removal when it is free. Check
+	 * whether this chunk is free while taking into consideration that the
+	 * chunk might consist of multiple records.
+	 *
+	 * Note that the free chunk inode count parameter must account for the
+	 * fact that this inode has not yet been freed in the inobt's...
 	 */
-	if (!(mp->m_flags & XFS_MOUNT_IKEEP) &&
-	    rec.ir_free == XFS_INOBT_ALL_FREE &&
-	    mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK) {
+	error = xfs_inobt_ischunkfree(mp, cur, &rec, mp->m_ialloc_inos - 1,
+				      &freeagino);
+	if (error)
+		goto error0;
+
+	if (!(mp->m_flags & XFS_MOUNT_IKEEP) && freeagino != NULLAGINO) {
 		xic->deleted = 1;
-		xic->first_ino = XFS_AGINO_TO_INO(mp, agno, rec.ir_startino);
+		xic->first_ino = XFS_AGINO_TO_INO(mp, agno, freeagino);
 		xic->alloc = xfs_inobt_irec_to_allocmask(&rec);
 
 		/*
+		 * Use the freecount if the record is sparse. Otherwise use the
+		 * chunk inode allocation count as the chunk could be larger
+		 * than a single record.
+		 */
+		if (xfs_inobt_issparse(rec.ir_holemask))
+			ilen = rec.ir_freecount;
+		else
+			ilen = mp->m_ialloc_inos;
+
+		/*
 		 * Remove the inode cluster from the AGI B+Tree, adjust the
 		 * AGI and Superblock inode counts, and mark the disk space
 		 * to be freed when the transaction is committed.
 		 */
-		ilen = rec.ir_freecount;
 		be32_add_cpu(&agi->agi_count, -ilen);
 		be32_add_cpu(&agi->agi_freecount, -(ilen - 1));
 		xfs_ialloc_log_agi(tp, agbp, XFS_AGI_COUNT | XFS_AGI_FREECOUNT);
@@ -2018,8 +2186,8 @@ xfs_difree_inobt(
 		xfs_trans_mod_sb(tp, XFS_TRANS_SB_ICOUNT, -ilen);
 		xfs_trans_mod_sb(tp, XFS_TRANS_SB_IFREE, -(ilen - 1));
 
-		error = xfs_inobt_delete(mp, cur, agno, rec.ir_startino,
-					 XFS_INODES_PER_CHUNK);
+		error = xfs_inobt_delete(mp, cur, agno, freeagino,
+					 mp->m_ialloc_inos);
 		if (error) {
 			xfs_warn(mp, "%s: xfs_inobt_delete returned error %d.",
 				__func__, error);
@@ -2079,6 +2247,7 @@ xfs_difree_finobt(
 	int				offset = agino - ibtrec->ir_startino;
 	int				error;
 	int				i;
+	xfs_agino_t			freeagino;
 
 	cur = xfs_inobt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_FINO);
 
@@ -2130,16 +2299,15 @@ xfs_difree_finobt(
 	 * free inode. Hence, if all of the inodes are free and we aren't
 	 * keeping inode chunks permanently on disk, remove the record.
 	 * Otherwise, update the record with the new information.
-	 *
-	 * Note that we currently can't free chunks when the block size is large
-	 * enough for multiple chunks. Leave the finobt record to remain in sync
-	 * with the inobt.
 	 */
-	if (rec.ir_free == XFS_INOBT_ALL_FREE &&
-	    mp->m_sb.sb_inopblock <= XFS_INODES_PER_CHUNK &&
-	    !(mp->m_flags & XFS_MOUNT_IKEEP)) {
-		error = xfs_inobt_delete(mp, cur, agno, rec.ir_startino,
-					 XFS_INODES_PER_CHUNK);
+	error = xfs_inobt_ischunkfree(mp, cur, &rec, mp->m_ialloc_inos - 1,
+				      &freeagino);
+	if (error)
+		goto error;
+
+	if (!(mp->m_flags & XFS_MOUNT_IKEEP) && freeagino != NULLAGINO) {
+		error = xfs_inobt_delete(mp, cur, agno, freeagino,
+					 mp->m_ialloc_inos);
 		if (error)
 			goto error;
 		ASSERT(i == 1);
-- 
2.5.5

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs

[PATCH v2 3/3] xfs: inobt record insert/delete tracepoints

[Brian Foster]

Add tracepoints for inobt record insert and delete. Be sure to
distinguish between the inobt and finobt in the tracepoints as the
record lifecycles differ between the trees.

Signed-off-by: Brian Foster <bfoster@redhat.com>
---
 fs/xfs/libxfs/xfs_ialloc.c | 16 +++++++++++++---
 fs/xfs/xfs_trace.h         | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 45 insertions(+), 3 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_ialloc.c b/fs/xfs/libxfs/xfs_ialloc.c
index fdaeee8..114b020 100644
--- a/fs/xfs/libxfs/xfs_ialloc.c
+++ b/fs/xfs/libxfs/xfs_ialloc.c
@@ -186,6 +186,8 @@ xfs_inobt_insert(
 		}
 		ASSERT(i == 0);
 
+		trace_xfs_irec_insert(mp, btnum, agno, thisino,
+				      XFS_INODES_PER_CHUNK);
 		error = xfs_inobt_insert_rec(cur, XFS_INOBT_HOLEMASK_FULL,
 					     XFS_INODES_PER_CHUNK,
 					     XFS_INODES_PER_CHUNK,
@@ -234,6 +236,8 @@ xfs_inobt_delete(
 		XFS_WANT_CORRUPTED_GOTO(mp, rec.ir_startino == agino,
 					out_error);
 
+		trace_xfs_irec_delete(mp, cur->bc_btnum, agno, rec.ir_startino,
+				      rec.ir_count);
 		error = xfs_btree_delete(cur, &i);
 		if (error)
 			goto out_error;
@@ -729,6 +733,8 @@ xfs_inobt_insert_sprec(
 		goto error;
 	/* if nothing there, insert a new record and return */
 	if (i == 0) {
+		trace_xfs_irec_insert(mp, btnum, agno, nrec->ir_startino,
+				      nrec->ir_count);
 		error = xfs_inobt_insert_rec(cur, nrec->ir_holemask,
 					     nrec->ir_count, nrec->ir_freecount,
 					     nrec->ir_free, &i);
@@ -1789,10 +1795,13 @@ xfs_dialloc_ag(
 	 */
 	rec.ir_free &= ~XFS_INOBT_MASK(offset);
 	rec.ir_freecount--;
-	if (rec.ir_freecount)
+	if (rec.ir_freecount) {
 		error = xfs_inobt_update(cur, &rec);
-	else
+	} else {
+		trace_xfs_irec_delete(mp, cur->bc_btnum, agno, rec.ir_startino,
+				      rec.ir_count);
 		error = xfs_btree_delete(cur, &i);
+	}
 	if (error)
 		goto error_cur;
 
@@ -2261,7 +2270,8 @@ xfs_difree_finobt(
 		 * something is out of sync.
 		 */
 		XFS_WANT_CORRUPTED_GOTO(mp, ibtrec->ir_freecount == 1, error);
-
+		trace_xfs_irec_insert(mp, cur->bc_btnum, agno,
+				      ibtrec->ir_startino, ibtrec->ir_count);
 		error = xfs_inobt_insert_rec(cur, ibtrec->ir_holemask,
 					     ibtrec->ir_count,
 					     ibtrec->ir_freecount,
diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h
index ea94ee0..3e27cdc 100644
--- a/fs/xfs/xfs_trace.h
+++ b/fs/xfs/xfs_trace.h
@@ -786,6 +786,38 @@ TRACE_EVENT(xfs_irec_merge_post,
 		  __entry->holemask)
 )
 
+DECLARE_EVENT_CLASS(xfs_irec_class,
+	TP_PROTO(struct xfs_mount *mp, xfs_btnum_t btnum, xfs_agnumber_t agno,
+		 xfs_agino_t agino, int count),
+	TP_ARGS(mp, btnum, agno, agino, count),
+	TP_STRUCT__entry(
+		__field(dev_t, dev)
+		__field(xfs_btnum_t, btnum)
+		__field(xfs_agnumber_t, agno)
+		__field(xfs_agino_t, agino)
+		__field(int, count)
+	),
+	TP_fast_assign(
+		__entry->dev = mp->m_super->s_dev;
+		__entry->btnum = btnum;
+		__entry->agno = agno;
+		__entry->agino = agino;
+		__entry->count = count;
+	),
+	TP_printk("dev %d:%d %s agno %d agino 0x%x count %d",
+		  MAJOR(__entry->dev), MINOR(__entry->dev),
+		  __entry->btnum == XFS_BTNUM_INOi ? "ibt" : "fibt",
+		  __entry->agno, __entry->agino, __entry->count)
+)
+
+#define DEFINE_IREC_EVENT(name) \
+DEFINE_EVENT(xfs_irec_class, name, \
+	TP_PROTO(struct xfs_mount *mp, xfs_btnum_t btnum, xfs_agnumber_t agno, \
+		 xfs_agino_t agino, int count), \
+	TP_ARGS(mp, btnum, agno, agino, count))
+DEFINE_IREC_EVENT(xfs_irec_insert);
+DEFINE_IREC_EVENT(xfs_irec_delete);
+
 #define DEFINE_IREF_EVENT(name) \
 DEFINE_EVENT(xfs_iref_class, name, \
 	TP_PROTO(struct xfs_inode *ip, unsigned long caller_ip), \
-- 
2.5.5

_______________________________________________
xfs mailing list
xfs@oss.sgi.com
http://oss.sgi.com/mailman/listinfo/xfs