[PATCH] hfs: fix logic of alloc/free b-tree node

[PATCH] hfs: fix logic of alloc/free b-tree node

[Viacheslav Dubeyko]

The hfs_bmap_alloc() and hfs_bmap_free() modify
the b-tree's counters and nodes' bitmap of b-tree.
However, hfs_btree_write() synchronizes the state of
in-core b-tree's counters and node's bitmap with
b-tree's descriptor in header node. Postponing this
synchronization could result in inconsistent state of
file system volume. Add calling of hfs_btree_write()
in hfs_bmap_alloc() and hfs_bmap_free() methods.

HFS port of the HFS+ commit:
commit 63584d76765b ("hfsplus: fix logic of alloc/free b-tree node").

Signed-off-by: Viacheslav Dubeyko <slava@dubeyko.com>
cc: John Paul Adrian Glaubitz <glaubitz@physik.fu-berlin.de>
cc: Yangtao Li <frank.li@vivo.com>
cc: linux-fsdevel@vger.kernel.org
---
 fs/hfs/btree.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/fs/hfs/btree.c b/fs/hfs/btree.c
index b140d8597474..27a515a3dd0c 100644
--- a/fs/hfs/btree.c
+++ b/fs/hfs/btree.c
@@ -458,6 +458,7 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 						set_page_dirty(page);
 						kunmap_local(data);
 						tree->free_nodes--;
+						hfs_btree_write(tree);
 						mark_inode_dirty(tree->inode);
 						hfs_bnode_put(node);
 						return hfs_bnode_create(tree, idx);
@@ -478,6 +479,7 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 		if (!nidx) {
 			printk(KERN_DEBUG "create new bmap node...\n");
 			next_node = hfs_bmap_new_bmap(node, idx);
+			hfs_btree_write(tree);
 		} else
 			next_node = hfs_bnode_find(tree, nidx);
 		hfs_bnode_put(node);
@@ -545,6 +547,7 @@ void hfs_bmap_free(struct hfs_bnode *node)
 			nidx, node->type);
 	} else {
 		tree->free_nodes++;
+		hfs_btree_write(tree);
 		mark_inode_dirty(tree->inode);
 	}
 
-- 
2.43.0

[PATCH] hfs: fix orphaned b-tree node in hfs_bnode_split()

[Viacheslav Dubeyko]

The xfstests' test-case generic/013 finishes with
corrupted HFS volume:

generic/013 27s ... [failed, exit status 1]_check_generic_filesystem: filesystem on /dev/loop50 is inconsistent

** Checking HFS volume.
   The volume name is untitled
** Checking extents overflow file.
** Checking catalog file.
   Invalid B-tree header
   Invalid map node
(4, 0)
** Checking catalog hierarchy.
** Checking volume bitmap.
** Checking volume information.
** The volume untitled was found corrupt and needs to be repaired.

The fsck tool detected that Catalog b-tree is corrupted.
Namely, the header node's counters and map node bitmap
have inconsistent state with the real b-tree structure.
The same issue has been fixed for the case of HFS+
by commit c1307d18caa8 ("hfsplus: fix generic/642 failure").

The hfs_bnode_split() contains a loop that implements
a roughly 50/50 split of the B-tree node's records by scanning
the offset table to find where the data crosses the node's midpoint.
If this logic detects the incapability of splitting the node, then
it simply calls hfs_bnode_put() for newly created node. However,
node is not set as HFS_BNODE_DELETED and real deletion of node
doesn't happen. As a result, the empty node becomes orphaned but
it is still accounted as used. Finally, fsck tool detects this
inconsistency of HFS volume.

Add call of hfs_bnode_unlink() before hfs_bnode_put()
for the case if new node cannot be used for splitting the existing
node.

HFS port of the HFS+ commit:
commit c1307d18caa8 ("hfsplus: fix generic/642 failure").

Signed-off-by: Viacheslav Dubeyko <slava@dubeyko.com>
cc: John Paul Adrian Glaubitz <glaubitz@physik.fu-berlin.de>
cc: Yangtao Li <frank.li@vivo.com>
cc: linux-fsdevel@vger.kernel.org
---
 fs/hfs/brec.c | 32 ++++++++++++++++++++------------
 1 file changed, 20 insertions(+), 12 deletions(-)

diff --git a/fs/hfs/brec.c b/fs/hfs/brec.c
index 5a2f740ddefd..1ca1ee9f73ef 100644
--- a/fs/hfs/brec.c
+++ b/fs/hfs/brec.c
@@ -254,6 +254,9 @@ static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
 	struct hfs_bnode_desc node_desc;
 	int num_recs, new_rec_off, new_off, old_rec_off;
 	int data_start, data_end, size;
+	size_t rec_off_tbl_size;
+	size_t node_desc_size = sizeof(struct hfs_bnode_desc);
+	size_t rec_size = sizeof(__be16);
 
 	tree = fd->tree;
 	node = fd->bnode;
@@ -280,18 +283,22 @@ static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
 		return next_node;
 	}
 
-	size = tree->node_size / 2 - node->num_recs * 2 - 14;
-	old_rec_off = tree->node_size - 4;
+	rec_off_tbl_size = node->num_recs * rec_size;
+	size = tree->node_size / 2;
+	size -= node_desc_size;
+	size -= rec_off_tbl_size;
+	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 -= 2;
+		old_rec_off -= rec_size;
 		if (++num_recs < node->num_recs)
 			continue;
-		/* panic? */
 		hfs_bnode_put(node);
+		hfs_bnode_unlink(new_node);
 		hfs_bnode_put(new_node);
 		if (next_node)
 			hfs_bnode_put(next_node);
@@ -302,7 +309,7 @@ static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
 		/* new record is in the lower half,
 		 * so leave some more space there
 		 */
-		old_rec_off += 2;
+		old_rec_off += rec_size;
 		num_recs--;
 		data_start = hfs_bnode_read_u16(node, old_rec_off);
 	} else {
@@ -310,27 +317,28 @@ static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
 		hfs_bnode_get(new_node);
 		fd->bnode = new_node;
 		fd->record -= num_recs;
-		fd->keyoffset -= data_start - 14;
-		fd->entryoffset -= data_start - 14;
+		fd->keyoffset -= data_start - node_desc_size;
+		fd->entryoffset -= data_start - node_desc_size;
 	}
 	new_node->num_recs = node->num_recs - num_recs;
 	node->num_recs = num_recs;
 
-	new_rec_off = tree->node_size - 2;
-	new_off = 14;
+	new_rec_off = tree->node_size - rec_size;
+	new_off = node_desc_size;
 	size = data_start - new_off;
 	num_recs = new_node->num_recs;
 	data_end = data_start;
 	while (num_recs) {
 		hfs_bnode_write_u16(new_node, new_rec_off, new_off);
-		old_rec_off -= 2;
-		new_rec_off -= 2;
+		old_rec_off -= rec_size;
+		new_rec_off -= rec_size;
 		data_end = hfs_bnode_read_u16(node, old_rec_off);
 		new_off = data_end - size;
 		num_recs--;
 	}
 	hfs_bnode_write_u16(new_node, new_rec_off, new_off);
-	hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start);
+	hfs_bnode_copy(new_node, node_desc_size,
+			node, data_start, data_end - data_start);
 
 	/* update new bnode header */
 	node_desc.next = cpu_to_be32(new_node->next);
-- 
2.43.0

[PATCH] hfs: fix potential race conditions in b-tree functionality

[Viacheslav Dubeyko]

The HFS_BNODE_DELETED flag is checked in hfs_bnode_put()
under locked tree->hash_lock. Add locking for the case of
setting the HFS_BNODE_DELETED flag in hfs_bnode_unlink()
with the goal to avoid potential race conditions.

The hfs_btree_write() method should be called under
tree->tree_lock. Rework logic by adding locking
the tree->tree_lock for the calls of hfs_btree_write()
in hfs_write_inode() for the case of Extents and
Catalog b-tree inodes.

Also, add the lockdep_assert_held() in
hfs_bmap_reserve(), hfs_bmap_alloc(), and hfs_bmap_free().

HFS port of the HFS+ commit:
commit 6dca66d7ba17 ("hfsplus: fix potential race conditions in b-tree functionality")

Signed-off-by: Viacheslav Dubeyko <slava@dubeyko.com>
cc: John Paul Adrian Glaubitz <glaubitz@physik.fu-berlin.de>
cc: Yangtao Li <frank.li@vivo.com>
cc: linux-fsdevel@vger.kernel.org
---
 fs/hfs/bnode.c |  3 +++
 fs/hfs/btree.c |  5 +++++
 fs/hfs/inode.c | 13 +++++++++++--
 3 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/fs/hfs/bnode.c b/fs/hfs/bnode.c
index 1b331108d9c0..93a13ece1eb4 100644
--- a/fs/hfs/bnode.c
+++ b/fs/hfs/bnode.c
@@ -271,7 +271,10 @@ void hfs_bnode_unlink(struct hfs_bnode *node)
 		tree->root = 0;
 		tree->depth = 0;
 	}
+
+	spin_lock(&tree->hash_lock);
 	set_bit(HFS_BNODE_DELETED, &node->flags);
+	spin_unlock(&tree->hash_lock);
 }
 
 static inline int hfs_bnode_hash(u32 num)
diff --git a/fs/hfs/btree.c b/fs/hfs/btree.c
index 4f0ddc76e8c5..b140d8597474 100644
--- a/fs/hfs/btree.c
+++ b/fs/hfs/btree.c
@@ -398,6 +398,8 @@ int hfs_bmap_reserve(struct hfs_btree *tree, u32 rsvd_nodes)
 	u32 count;
 	int res;
 
+	lockdep_assert_held(&tree->tree_lock);
+
 	while (tree->free_nodes < rsvd_nodes) {
 		res = hfs_extend_file(inode);
 		if (res)
@@ -424,6 +426,8 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 	u8 *data, byte, m;
 	int i, res;
 
+	lockdep_assert_held(&tree->tree_lock);
+
 	res = hfs_bmap_reserve(tree, 1);
 	if (res)
 		return ERR_PTR(res);
@@ -500,6 +504,7 @@ void hfs_bmap_free(struct hfs_bnode *node)
 
 	hfs_dbg("node %u\n", node->this);
 	tree = node->tree;
+	lockdep_assert_held(&tree->tree_lock);
 	nidx = node->this;
 	node = hfs_bnode_find(tree, 0);
 	if (IS_ERR(node))
diff --git a/fs/hfs/inode.c b/fs/hfs/inode.c
index cce3a7bb95e9..9dde4b43c88f 100644
--- a/fs/hfs/inode.c
+++ b/fs/hfs/inode.c
@@ -468,6 +468,7 @@ int hfs_write_inode(struct inode *inode, struct writeback_control *wbc)
 {
 	struct inode *main_inode = inode;
 	struct hfs_find_data fd;
+	struct hfs_btree *tree;
 	hfs_cat_rec rec;
 	int res;
 
@@ -481,10 +482,18 @@ int hfs_write_inode(struct inode *inode, struct writeback_control *wbc)
 		case HFS_ROOT_CNID:
 			break;
 		case HFS_EXT_CNID:
-			hfs_btree_write(HFS_SB(inode->i_sb)->ext_tree);
+			tree = HFS_SB(inode->i_sb)->ext_tree;
+			mutex_lock_nested(&tree->tree_lock,
+					  EXTENTS_BTREE_MUTEX);
+			hfs_btree_write(tree);
+			mutex_unlock(&tree->tree_lock);
 			return 0;
 		case HFS_CAT_CNID:
-			hfs_btree_write(HFS_SB(inode->i_sb)->cat_tree);
+			tree = HFS_SB(inode->i_sb)->cat_tree;
+			mutex_lock_nested(&tree->tree_lock,
+					  CATALOG_BTREE_MUTEX);
+			hfs_btree_write(tree);
+			mutex_unlock(&tree->tree_lock);
 			return 0;
 		default:
 			BUG();
-- 
2.43.0