Skip to contentSkip to conversation

hfsplus: fix hfs_bnode_split() failure on sparsely-filled nodes

PATCH In review Shardul Bankar 2 participants 2 messages Apr 23 – Apr 24

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 hfsplus: fix hfs_bnode_split() failure on sparsely-filled nodes

hfs_bnode_split() determines the split point by scanning the node's offset table for the first record whose data offset exceeds a threshold derived from node_size / 2. When all record data fits within the first half of the node, no record offset exceeds the threshold, the loop exhausts all records, and the function returns -ENOSPC even though the node can be validly split. This causes xattr insertions to fail silently.

The failing code path is exercised by xfstests generic/070 and generic/642 during xattr stress operations.

Fix this by re-scanning with a threshold based on the actual data midpoint when the position-based scan exhausts. If the re-scan also exhausts, fall back to splitting off the last record.

---
 fs/hfsplus/brec.c | 32 ++++++++++++++++++++++++++------
 1 file changed, 26 insertions(+), 6 deletions(-)
fs/hfsplus/brec.c +26 -6
index e3df89284079..cfc909c808a4 100644
@@ -282,12 +282,32 @@ static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
 		old_rec_off -= rec_size;
 		if (++num_recs < node->num_recs)
 			continue;
-		hfs_bnode_put(node);
-		hfs_bnode_unlink(new_node);
-		hfs_bnode_put(new_node);
-		if (next_node)
-			hfs_bnode_put(next_node);
-		return ERR_PTR(-ENOSPC);
+		/*
+		 * All data fits within the node_size/2 threshold,
+		 * so re-scan using the actual data midpoint.
+		 */
+		size = hfs_bnode_read_u16(node, tree->node_size -
+			(node->num_recs + 1) * rec_size);
+		size = ((int)node_desc_size + size) / 2;
+		old_rec_off = tree->node_size - (2 * rec_size);
+		num_recs = 1;
+		for (;;) {
+			data_start = hfs_bnode_read_u16(node,
+							old_rec_off);
+			if (data_start > size)
+				break;
+			old_rec_off -= rec_size;
+			if (++num_recs < node->num_recs)
+				continue;
+			/* last record holds most of the data */
+			num_recs = node->num_recs - 1;
+			old_rec_off = tree->node_size -
+				(num_recs + 1) * rec_size;
+			data_start = hfs_bnode_read_u16(node,
+							old_rec_off);
+			break;
+		}
+		break;
 	}
 
 	if (fd->record + 1 < num_recs) {
Signature · 1 line
2.34.1
#1 lore raw
Quoted 26 lines · Shardul Bankar

hfs_bnode_split() determines the split point by scanning the node's offset table for the first record whose data offset exceeds a threshold derived from node_size / 2. When all record data fits within the first half of the node, no record offset exceeds the threshold, the loop exhausts all records, and the function returns -ENOSPC even though the node can be validly split. This causes xattr insertions to fail silently.

The failing code path is exercised by xfstests generic/070 and generic/642 during xattr stress operations.

Fix this by re-scanning with a threshold based on the actual data midpoint when the position-based scan exhausts. If the re-scan also exhausts, fall back to splitting off the last record.

---
 fs/hfsplus/brec.c | 32 ++++++++++++++++++++++++++------
 1 file changed, 26 insertions(+), 6 deletions(-)
fs/hfsplus/brec.c +0 -0
index e3df89284079..cfc909c808a4 100644

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 290

Quoted 9 lines
fs/hfsplus/brec.c +0 -6
@@ -282,12 +282,32 @@ static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
 		old_rec_off -= rec_size;
 		if (++num_recs < node->num_recs)
 			continue;
-		hfs_bnode_put(node);
-		hfs_bnode_unlink(new_node);
-		hfs_bnode_put(new_node);
-		if (next_node)
-			hfs_bnode_put(next_node);
-		return ERR_PTR(-ENOSPC);

I don't quite follow why do we completely remove this logic? Potentially, it could be valid situation. No?

Also, I think we need to add hfs_bnode_unlink(new_node) here [1]. Otherwise, hfs_bnode_put() will be unable to destroy the node.

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 288

Quoted 4 lines
fs/hfsplus/brec.c +4 -0
+		/*
+		 * All data fits within the node_size/2 threshold,
+		 * so re-scan using the actual data midpoint.
+		 */

First of all, I don't see the answer on question. Why we call this method for node that is not completely full (or near to be full). If we have half empty node, then, what's the point to execute node splitting? We have enough space to add more items. Do we have the same issue for Catalog File and Extents file?

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 290

Quoted 2 lines
fs/hfsplus/brec.c +2 -0
+		size = hfs_bnode_read_u16(node, tree->node_size -
+			(node->num_recs + 1) * rec_size);

I prefer to executes likewise calculation more carefully. We could have incorrect tree->node_size, weird node->num_recs value.

Why do we need node->num_recs + 1?

Potentially, we could have overflow here.

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 291

Quoted 1 line
fs/hfsplus/brec.c +1 -0
+		size = ((int)node_desc_size + size) / 2;

How can we blindly rely on size that we received from hfs_bnode_read_u16()? What if it was really huge or really small value?

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 292

Quoted 1 line
fs/hfsplus/brec.c +1 -0
+		old_rec_off = tree->node_size - (2 * rec_size);

Why 2 was hardcoded here? What this value mean? Why do we need to multiple rec_size on 2?

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 294

Quoted 2 lines
fs/hfsplus/brec.c +2 -0
+		num_recs = 1;
+		for (;;) {

I slightly dislike infinite loop here. Why do we need to use infinite loop? We have size or number of items estimation. What the point to use infinite loop? It is always bad coding style.

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 300

Quoted 6 lines
fs/hfsplus/brec.c +6 -0
+			data_start = hfs_bnode_read_u16(node,
+							old_rec_off);
+			if (data_start > size)
+				break;
+			old_rec_off -= rec_size;
+			if (++num_recs < node->num_recs)

This is can be used as for loop boundary. Why infinite loop has been used?

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 305

Quoted 5 lines
fs/hfsplus/brec.c +5 -0
+				continue;
+			/* last record holds most of the data */
+			num_recs = node->num_recs - 1;
+			old_rec_off = tree->node_size -
+				(num_recs + 1) * rec_size;

The same concerns related to calculation here.

Thanks,
Slava.

fs/hfsplus/brec.c static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd) · line 313

Quoted 8 lines
fs/hfsplus/brec.c +5 -0
+			data_start = hfs_bnode_read_u16(node,
+							old_rec_off);
+			break;
+		}
+		break;
 	}
 
 	if (fd->record + 1 < num_recs) {

[1] https://elixir.bootlin.com/linux/v7.0/source/fs/hfsplus/brec.c#L262