incore extent b+tree fixups

incore extent b+tree fixups

[Christoph Hellwig]

A couple small patches to fix issue pointed out by Brian.

[PATCH 1/6] xfs: fix number of records handling in xfs_iext_split_leaf

[Christoph Hellwig]

Fix to check the correct value, and remove a duplicate handling of the
uneven record number split algorith,

Reported-by: Brian Foster <bfoster@redhat.com>
Signed-off-by: Christoph Hellwig <hch@lst.de>
---
 fs/xfs/libxfs/xfs_iext_tree.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c
index 00d660dcb05e..85d7f708eafc 100644
--- a/fs/xfs/libxfs/xfs_iext_tree.c
+++ b/fs/xfs/libxfs/xfs_iext_tree.c
@@ -555,16 +555,13 @@ xfs_iext_split_leaf(
 	int			i;
 
 	/* for sequential append operations just spill over into the new node */
-	if (cur->pos == KEYS_PER_NODE) {
+	if (cur->pos == RECS_PER_LEAF) {
 		cur->leaf = new;
 		cur->pos = 0;
 		*nr_entries = 0;
 		goto done;
 	}
 
-	if (nr_keep & 1)
-		nr_keep++;
-
 	for (i = 0; i < nr_move; i++) {
 		new->recs[i] = leaf->recs[nr_keep + i];
 		xfs_iext_rec_clear(&leaf->recs[nr_keep + i]);
-- 
2.14.2

[PATCH 2/6] xfs: add some comments to xfs_iext_insert/xfs_iext_insert_node

[Christoph Hellwig]

Reported-by: Brian Foster <bfoster@redhat.com>
Signed-off-by: Christoph Hellwig <hch@lst.de>
---
 fs/xfs/libxfs/xfs_iext_tree.c | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c
index 85d7f708eafc..c28a24aca9c5 100644
--- a/fs/xfs/libxfs/xfs_iext_tree.c
+++ b/fs/xfs/libxfs/xfs_iext_tree.c
@@ -525,6 +525,10 @@ xfs_iext_insert_node(
 	if (nr_entries == KEYS_PER_NODE)
 		new = xfs_iext_split_node(&node, &pos, &nr_entries);
 
+	/*
+	 * Update the pointers in higher levels if the first entry changes
+	 * in an existing node.
+	 */
 	if (node != new && pos == 0 && nr_entries > 0)
 		xfs_iext_update_node(ifp, node->keys[0], offset, level, node);
 
@@ -643,6 +647,10 @@ xfs_iext_insert(
 	if (nr_entries == RECS_PER_LEAF)
 		new = xfs_iext_split_leaf(cur, &nr_entries);
 
+	/*
+	 * Update the pointers in higher levels if the first entry changes
+	 * in an existing node.
+	 */
 	if (cur->leaf != new && cur->pos == 0 && nr_entries > 0) {
 		xfs_iext_update_node(ifp, xfs_iext_leaf_key(cur->leaf, 0),
 				offset, 1, cur->leaf);
-- 
2.14.2

[PATCH 3/6] xfs: remove a superflous assignment in xfs_iext_remove_node

[Christoph Hellwig]

Reported-by: Brian Foster <bfoster@redhat.com>
Signed-off-by: Christoph Hellwig <hch@lst.de>
---
 fs/xfs/libxfs/xfs_iext_tree.c | 1 -
 1 file changed, 1 deletion(-)

diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c
index c28a24aca9c5..11b95bea23a9 100644
--- a/fs/xfs/libxfs/xfs_iext_tree.c
+++ b/fs/xfs/libxfs/xfs_iext_tree.c
@@ -751,7 +751,6 @@ xfs_iext_remove_node(
 
 		node = xfs_iext_rebalance_node(parent, &pos, node, nr_entries);
 		if (node) {
-			offset = node->keys[0];
 			victim = node;
 			node = parent;
 			goto again;
-- 
2.14.2

[PATCH 4/6] xfs: trivial indentation fixup for xfs_iext_remove_node

[Christoph Hellwig]

Signed-off-by: Christoph Hellwig <hch@lst.de>
---
 fs/xfs/libxfs/xfs_iext_tree.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c
index 11b95bea23a9..3974989b0929 100644
--- a/fs/xfs/libxfs/xfs_iext_tree.c
+++ b/fs/xfs/libxfs/xfs_iext_tree.c
@@ -733,8 +733,7 @@ xfs_iext_remove_node(
 	node->ptrs[nr_entries] = NULL;
 
 	if (pos == 0 && nr_entries > 0) {
-		xfs_iext_update_node(ifp, offset, node->keys[0], level,
-				node);
+		xfs_iext_update_node(ifp, offset, node->keys[0], level, node);
 		offset = node->keys[0];
 	}
 
-- 
2.14.2

[PATCH 5/6] xfs: add comments documenting the rebalance algorithm

[Christoph Hellwig]

Reported-by: Brian Foster <bfoster@redhat.com>
Signed-off-by: Christoph Hellwig <hch@lst.de>
---
 fs/xfs/libxfs/xfs_iext_tree.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c
index 3974989b0929..81e0480822d8 100644
--- a/fs/xfs/libxfs/xfs_iext_tree.c
+++ b/fs/xfs/libxfs/xfs_iext_tree.c
@@ -672,6 +672,11 @@ xfs_iext_rebalance_node(
 	struct xfs_iext_node	*node,
 	int			nr_entries)
 {
+	/*
+	 * If the neighbouring nodes are completely full, or have different
+	 * parents, we might never be able to merge our node, and will only
+	 * delete it once the number of entries hits zero.
+	 */
 	if (nr_entries == 0)
 		return node;
 
@@ -693,6 +698,11 @@ xfs_iext_rebalance_node(
 		int nr_next = xfs_iext_node_nr_entries(next, 0), i;
 
 		if (nr_entries + nr_next <= KEYS_PER_NODE) {
+			/*
+			 * Merge the next node into this node so that we don't
+			 * have to do an additional update of the keys in the
+			 * higher levels.
+			 */
 			for (i = 0; i < nr_next; i++) {
 				node->keys[nr_entries + i] = next->keys[i];
 				node->ptrs[nr_entries + i] = next->ptrs[i];
@@ -741,6 +751,11 @@ xfs_iext_remove_node(
 		return;
 
 	if (level < ifp->if_height) {
+		/*
+		 * If we aren't at the root yet try to find a neighbour node to
+		 * merge with (or delete the node if it is empty), and then
+		 * recurse up to the next level.
+		 */
 		level++;
 		parent = xfs_iext_find_level(ifp, offset, level);
 		pos = xfs_iext_node_pos(parent, offset);
@@ -755,6 +770,10 @@ xfs_iext_remove_node(
 			goto again;
 		}
 	} else if (nr_entries == 1) {
+		/*
+		 * If we are at the root and only one entry is left we can just
+		 * free this node and update the root pointer.
+		 */
 		ASSERT(node == ifp->if_u1.if_root);
 		ifp->if_u1.if_root = node->ptrs[0];
 		ifp->if_height--;
@@ -789,6 +808,11 @@ xfs_iext_rebalance_leaf(
 		int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i;
 
 		if (fill + nr_next <= RECS_PER_LEAF) {
+			/*
+			 * Merge the next node into this node so that we don't
+			 * have to do an additional update of the keys in the
+			 * higher levels.
+			 */
 			for (i = 0; i < nr_next; i++)
 				leaf->recs[fill + i] = leaf->next->recs[i];
 
-- 
2.14.2

[PATCH 6/6] xfs: handle zero entries case in xfs_iext_rebalance_leaf

[Christoph Hellwig]

And also rename fill to nr_entries to match the rest of the code.

Reported-by: Brian Foster <bfoster@redhat.com>
Signed-off-by: Christoph Hellwig <hch@lst.de>
---
 fs/xfs/libxfs/xfs_iext_tree.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)

diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c
index 81e0480822d8..343a94246f5b 100644
--- a/fs/xfs/libxfs/xfs_iext_tree.c
+++ b/fs/xfs/libxfs/xfs_iext_tree.c
@@ -787,13 +787,21 @@ xfs_iext_rebalance_leaf(
 	struct xfs_iext_cursor	*cur,
 	struct xfs_iext_leaf	*leaf,
 	xfs_fileoff_t		offset,
-	int			fill)
+	int			nr_entries)
 {
+	/*
+	 * If the neighbouring nodes are completely full we might never be able
+	 * to merge our node, and will only delete it once the number of
+	 * entries hits zero.
+	 */
+	if (nr_entries == 0)
+		goto remove_node;
+
 	if (leaf->prev) {
 		int nr_prev = xfs_iext_leaf_nr_entries(ifp, leaf->prev, 0), i;
 
-		if (nr_prev + fill <= RECS_PER_LEAF) {
-			for (i = 0; i < fill; i++)
+		if (nr_prev + nr_entries <= RECS_PER_LEAF) {
+			for (i = 0; i < nr_entries; i++)
 				leaf->prev->recs[nr_prev + i] = leaf->recs[i];
 
 			if (cur->leaf == leaf) {
@@ -807,18 +815,20 @@ xfs_iext_rebalance_leaf(
 	if (leaf->next) {
 		int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i;
 
-		if (fill + nr_next <= RECS_PER_LEAF) {
+		if (nr_entries + nr_next <= RECS_PER_LEAF) {
 			/*
 			 * Merge the next node into this node so that we don't
 			 * have to do an additional update of the keys in the
 			 * higher levels.
 			 */
-			for (i = 0; i < nr_next; i++)
-				leaf->recs[fill + i] = leaf->next->recs[i];
+			for (i = 0; i < nr_next; i++) {
+				leaf->recs[nr_entries + i] =
+					leaf->next->recs[i];
+			}
 
 			if (cur->leaf == leaf->next) {
 				cur->leaf = leaf;
-				cur->pos += fill;
+				cur->pos += nr_entries;
 			}
 
 			offset = xfs_iext_leaf_key(leaf->next, 0);
-- 
2.14.2

Re: incore extent b+tree fixups

[Brian Foster]

On Thu, Nov 09, 2017 at 02:26:50PM +0100, Christoph Hellwig wrote:
> A couple small patches to fix issue pointed out by Brian.
> 

These all look good to me, thanks!

Reviewed-by: Brian Foster <bfoster@redhat.com>

> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: incore extent b+tree fixups

[Darrick J. Wong]

On Thu, Nov 09, 2017 at 02:26:50PM +0100, Christoph Hellwig wrote:
> A couple small patches to fix issue pointed out by Brian.

Looks ok, tests ok,
Reviewed-by: Darrick J. Wong <darrick.wong@oracle.com>

> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-xfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html