* incore extent b+tree fixups
@ 2017-11-09 13:26 Christoph Hellwig
2017-11-09 13:26 ` [PATCH 1/6] xfs: fix number of records handling in xfs_iext_split_leaf Christoph Hellwig
` (7 more replies)
0 siblings, 8 replies; 9+ messages in thread
From: Christoph Hellwig @ 2017-11-09 13:26 UTC (permalink / raw)
To: linux-xfs; +Cc: bfoster
A couple small patches to fix issue pointed out by Brian.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 1/6] xfs: fix number of records handling in xfs_iext_split_leaf
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
@ 2017-11-09 13:26 ` Christoph Hellwig
2017-11-09 13:26 ` [PATCH 2/6] xfs: add some comments to xfs_iext_insert/xfs_iext_insert_node Christoph Hellwig
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Christoph Hellwig @ 2017-11-09 13:26 UTC (permalink / raw)
To: linux-xfs; +Cc: bfoster
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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 2/6] xfs: add some comments to xfs_iext_insert/xfs_iext_insert_node
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
2017-11-09 13:26 ` [PATCH 1/6] xfs: fix number of records handling in xfs_iext_split_leaf Christoph Hellwig
@ 2017-11-09 13:26 ` Christoph Hellwig
2017-11-09 13:26 ` [PATCH 3/6] xfs: remove a superflous assignment in xfs_iext_remove_node Christoph Hellwig
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Christoph Hellwig @ 2017-11-09 13:26 UTC (permalink / raw)
To: linux-xfs; +Cc: bfoster
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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 3/6] xfs: remove a superflous assignment in xfs_iext_remove_node
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
2017-11-09 13:26 ` [PATCH 1/6] xfs: fix number of records handling in xfs_iext_split_leaf Christoph Hellwig
2017-11-09 13:26 ` [PATCH 2/6] xfs: add some comments to xfs_iext_insert/xfs_iext_insert_node Christoph Hellwig
@ 2017-11-09 13:26 ` Christoph Hellwig
2017-11-09 13:26 ` [PATCH 4/6] xfs: trivial indentation fixup for xfs_iext_remove_node Christoph Hellwig
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Christoph Hellwig @ 2017-11-09 13:26 UTC (permalink / raw)
To: linux-xfs; +Cc: bfoster
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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 4/6] xfs: trivial indentation fixup for xfs_iext_remove_node
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
` (2 preceding siblings ...)
2017-11-09 13:26 ` [PATCH 3/6] xfs: remove a superflous assignment in xfs_iext_remove_node Christoph Hellwig
@ 2017-11-09 13:26 ` Christoph Hellwig
2017-11-09 13:26 ` [PATCH 5/6] xfs: add comments documenting the rebalance algorithm Christoph Hellwig
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Christoph Hellwig @ 2017-11-09 13:26 UTC (permalink / raw)
To: linux-xfs; +Cc: bfoster
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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 5/6] xfs: add comments documenting the rebalance algorithm
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
` (3 preceding siblings ...)
2017-11-09 13:26 ` [PATCH 4/6] xfs: trivial indentation fixup for xfs_iext_remove_node Christoph Hellwig
@ 2017-11-09 13:26 ` Christoph Hellwig
2017-11-09 13:26 ` [PATCH 6/6] xfs: handle zero entries case in xfs_iext_rebalance_leaf Christoph Hellwig
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: Christoph Hellwig @ 2017-11-09 13:26 UTC (permalink / raw)
To: linux-xfs; +Cc: bfoster
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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 6/6] xfs: handle zero entries case in xfs_iext_rebalance_leaf
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
` (4 preceding siblings ...)
2017-11-09 13:26 ` [PATCH 5/6] xfs: add comments documenting the rebalance algorithm Christoph Hellwig
@ 2017-11-09 13:26 ` Christoph Hellwig
2017-11-09 14:32 ` incore extent b+tree fixups Brian Foster
2017-11-10 1:11 ` Darrick J. Wong
7 siblings, 0 replies; 9+ messages in thread
From: Christoph Hellwig @ 2017-11-09 13:26 UTC (permalink / raw)
To: linux-xfs; +Cc: bfoster
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
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: incore extent b+tree fixups
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
` (5 preceding siblings ...)
2017-11-09 13:26 ` [PATCH 6/6] xfs: handle zero entries case in xfs_iext_rebalance_leaf Christoph Hellwig
@ 2017-11-09 14:32 ` Brian Foster
2017-11-10 1:11 ` Darrick J. Wong
7 siblings, 0 replies; 9+ messages in thread
From: Brian Foster @ 2017-11-09 14:32 UTC (permalink / raw)
To: Christoph Hellwig; +Cc: linux-xfs
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: incore extent b+tree fixups
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
` (6 preceding siblings ...)
2017-11-09 14:32 ` incore extent b+tree fixups Brian Foster
@ 2017-11-10 1:11 ` Darrick J. Wong
7 siblings, 0 replies; 9+ messages in thread
From: Darrick J. Wong @ 2017-11-10 1:11 UTC (permalink / raw)
To: Christoph Hellwig; +Cc: linux-xfs, bfoster
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
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2017-11-10 1:12 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-11-09 13:26 incore extent b+tree fixups Christoph Hellwig
2017-11-09 13:26 ` [PATCH 1/6] xfs: fix number of records handling in xfs_iext_split_leaf Christoph Hellwig
2017-11-09 13:26 ` [PATCH 2/6] xfs: add some comments to xfs_iext_insert/xfs_iext_insert_node Christoph Hellwig
2017-11-09 13:26 ` [PATCH 3/6] xfs: remove a superflous assignment in xfs_iext_remove_node Christoph Hellwig
2017-11-09 13:26 ` [PATCH 4/6] xfs: trivial indentation fixup for xfs_iext_remove_node Christoph Hellwig
2017-11-09 13:26 ` [PATCH 5/6] xfs: add comments documenting the rebalance algorithm Christoph Hellwig
2017-11-09 13:26 ` [PATCH 6/6] xfs: handle zero entries case in xfs_iext_rebalance_leaf Christoph Hellwig
2017-11-09 14:32 ` incore extent b+tree fixups Brian Foster
2017-11-10 1:11 ` Darrick J. Wong
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.