Re: [PATCH 2.6 to 4.0] hfsplus: fix B-tree corruption after insertion at position 0

Re: [PATCH 2.6 to 4.0] hfsplus: fix B-tree corruption after insertion at position 0

[Sergei Antonov]

On 19 March 2015 at 18:40, Hin-Tak Leung <htl10@users.sourceforge.net> wrote:
>>> Also, the logic of hfs_brec_insert() in the plain hfs (without +) driver in
>>> fs/hfs/brec.c is essentially the same, so I believe there is the need of another
>>> similiar patch for that also. Can you provide that also?
>>
>>No. The original HFS is very old. The only reasonable purpose of its
>>implementation in Linux IMO is to read data from old disks. Read-only
>>mode that is.
>
> I don't think it is right to dictate how users should use their linux box.
> On the whole we should only stop fixing bugs if we are going
> to deprecate hfs (and subsequently remove it). Also, there is some value
> in keeping two file systems which are code-wise very similar in sync.
>
> If you cannot find the time, but otherwise have no objection, I'd be happy to
> spend the time to prepare the patch, and add your signed-off on it?

Of course, I have no objections. But, please, do not add me in
signed-off-by. Because signed-off-by implies some responsibility, and
I do not want to have one for hfs.

Re: [PATCH 2.6 to 4.0] hfsplus: fix B-tree corruption after insertion at position 0

[Sergei Antonov]

On 19 March 2015 at 18:40, Hin-Tak Leung <htl10@users.sourceforge.net> wrote:
> ------------------------------
> On Wed, Mar 18, 2015 11:05 PM GMT Sergei Antonov wrote:
>
>>On 18 March 2015 at 16:28, Hin-Tak Leung <htl10@users.sourceforge.net> wrote:
>>> Can you describe a bit more about the symptom please?
>>
>>Some files and directories are gone. Depending on which of the catalog
>>file's nodes reside in the unavailable extents, it may vary from "some
>>data can be salvaged" to "screw it, reformat the volume".
>>
>>> I am
>>> wondering whether it is related to an issue I have had which is quite reproducible:
>>> If I merely run "du" repeatedly on a large directory on an HFS+ formatted
>>> drive, on a somewhat resource-tight system (having firefox running with lots
>>> windows seems to make it happens sooner, and it was on a system with only 2GB memory).
>>
>>Then what?
>>
>
> The kernel getting very confused, not being able to read some files/directories
> on the HFS+ volume, and having lots of messages in the kernel log about inconsistent
> b-tree.
>
> This appears to be entirely in-memory and has no effect on on-disk data;
> also I can reproduce the problem by mounting read-only. If I reboot,
> fsck always says the hfs+ volume is clean, and I can repeat the exercise.

The patch I published recently ("hfsplus: release bnode pages after
use, not before") will fix your problem. Please, test.

Re: [PATCH 2.6 to 4.0] hfsplus: fix B-tree corruption after insertion at position 0

[Sergei Antonov]

On 18 March 2015 at 16:28, Hin-Tak Leung <htl10@users.sourceforge.net> wrote:
> Can you describe a bit more about the symptom please?

Some files and directories are gone. Depending on which of the catalog
file's nodes reside in the unavailable extents, it may vary from "some
data can be salvaged" to "screw it, reformat the volume".

> I am
> wondering whether it is related to an issue I have had which is quite reproducible:
> If I merely run "du" repeatedly on a large directory on an HFS+ formatted
> drive, on a somewhat resource-tight system (having firefox running with lots
> windows seems to make it happens sooner, and it was on a system with only 2GB memory).

Then what?

> I was able to do with with two separate drives, one had user data
> which I have edited by hand somewhat,
> but the other was was a qcow2 image of an essentially newly installed and clean
> Mac OS X system disk through qemu/kvm.

> Also, the logic of hfs_brec_insert() in the plain hfs (without +) driver in
> fs/hfs/brec.c is essentially the same, so I believe there is the need of another
> similiar patch for that also. Can you provide that also?

No. The original HFS is very old. The only reasonable purpose of its
implementation in Linux IMO is to read data from old disks. Read-only
mode that is.

Re: [PATCH 2.6 to 4.0] hfsplus: fix B-tree corruption after insertion at position 0

[Viacheslav Dubeyko]

On Tue, 2015-03-17 at 03:10 +0100, Sergei Antonov wrote:
> Fix B-tree corruption when a new record is inserted at position 0 in the node
> in hfs_brec_insert(). In this case a hfs_brec_update_parent() is called to
> update the parent index node (if exists) and it is passed hfs_find_data with
> a search_key containing a newly inserted key instead of the key to be updated.
> This results in an inconsistent index node. The bug reproduces on my machine
> after an extents overflow record for the catalog file (CNID=4) is inserted into
> the extents overflow B-tree. Because of a low (reserved) value of CNID=4, it
> has to become the first record in the first leaf node.
> The resulting first leaf node is correct:
> ----------------------------------------------------
> | key0.CNID=4 | key1.CNID=123 | key2.CNID=456, ... |
> ----------------------------------------------------
> But the parent index key0 still contains the previous key CNID=123:
> -----------------------
> | key0.CNID=123 | ... |
> -----------------------
> 
> A change in hfs_brec_insert() makes hfs_brec_update_parent() work correctly
> by preventing it from getting fd->record=-1 value from __hfs_brec_find().
> 

The fix looks good for me. Thank you.
Reviewed-by: Vyacheslav Dubeyko <slava@dubeyko.com>

> Along the way, I removed duplicate code with unification of the if condition.
> The resulting code is equivalent to the original code because node is never 0.
> 
> Also hfs_brec_update_parent() will now return an error after getting a negative
> fd->record value. However, the return value of hfs_brec_update_parent() is not
> checked anywhere in the file and I'm leaving it unchanged by this patch.
> brec.c lacks error checking after some other calls too, but this issue is of
> less importance than the one being fixed by this patch.

But I think that to check the returned value is important. So, how do
you feel about adding checking of error codes and some error messages?

Thanks,
Vyacheslav Dubeyko.

> 
> Cc: stable@vger.kernel.org
> Cc: Joe Perches <joe@perches.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Vyacheslav Dubeyko <slava@dubeyko.com>
> Cc: Hin-Tak Leung <htl10@users.sourceforge.net>
> Cc: Anton Altaparmakov <aia21@cam.ac.uk>
> Cc: Al Viro <viro@zeniv.linux.org.uk>
> Cc: Christoph Hellwig <hch@infradead.org>
> Signed-off-by: Sergei Antonov <saproj@gmail.com>
> ---
>  fs/hfsplus/brec.c | 20 +++++++++++---------
>  1 file changed, 11 insertions(+), 9 deletions(-)
> 
> diff --git a/fs/hfsplus/brec.c b/fs/hfsplus/brec.c
> index 6e560d5..754fdf8 100644
> --- a/fs/hfsplus/brec.c
> +++ b/fs/hfsplus/brec.c
> @@ -131,13 +131,16 @@ skip:
>  	hfs_bnode_write(node, entry, data_off + key_len, entry_len);
>  	hfs_bnode_dump(node);
>  
> -	if (new_node) {
> -		/* update parent key if we inserted a key
> -		 * at the start of the first node
> -		 */
> -		if (!rec && new_node != node)
> -			hfs_brec_update_parent(fd);
> +	/*
> +	 * update parent key if we inserted a key
> +	 * at the start of the node and it is not the new node
> +	 */
> +	if (!rec && new_node != node) {
> +		hfs_bnode_read_key(node, fd->search_key, data_off + size);
> +		hfs_brec_update_parent(fd);
> +	}
>  
> +	if (new_node) {
>  		hfs_bnode_put(fd->bnode);
>  		if (!new_node->parent) {
>  			hfs_btree_inc_height(tree);
> @@ -168,9 +171,6 @@ skip:
>  		goto again;
>  	}
>  
> -	if (!rec)
> -		hfs_brec_update_parent(fd);
> -
>  	return 0;
>  }
>  
> @@ -370,6 +370,8 @@ again:
>  	if (IS_ERR(parent))
>  		return PTR_ERR(parent);
>  	__hfs_brec_find(parent, fd, hfs_find_rec_by_key);
> +	if (fd->record < 0)
> +		return -ENOENT;
>  	hfs_bnode_dump(parent);
>  	rec = fd->record;
>  

[PATCH 2.6 to 4.0] hfsplus: fix B-tree corruption after insertion at position 0

[Sergei Antonov]

Fix B-tree corruption when a new record is inserted at position 0 in the node
in hfs_brec_insert(). In this case a hfs_brec_update_parent() is called to
update the parent index node (if exists) and it is passed hfs_find_data with
a search_key containing a newly inserted key instead of the key to be updated.
This results in an inconsistent index node. The bug reproduces on my machine
after an extents overflow record for the catalog file (CNID=4) is inserted into
the extents overflow B-tree. Because of a low (reserved) value of CNID=4, it
has to become the first record in the first leaf node.
The resulting first leaf node is correct:
----------------------------------------------------
| key0.CNID=4 | key1.CNID=123 | key2.CNID=456, ... |
----------------------------------------------------
But the parent index key0 still contains the previous key CNID=123:
-----------------------
| key0.CNID=123 | ... |
-----------------------

A change in hfs_brec_insert() makes hfs_brec_update_parent() work correctly
by preventing it from getting fd->record=-1 value from __hfs_brec_find().

Along the way, I removed duplicate code with unification of the if condition.
The resulting code is equivalent to the original code because node is never 0.

Also hfs_brec_update_parent() will now return an error after getting a negative
fd->record value. However, the return value of hfs_brec_update_parent() is not
checked anywhere in the file and I'm leaving it unchanged by this patch.
brec.c lacks error checking after some other calls too, but this issue is of
less importance than the one being fixed by this patch.

Cc: stable@vger.kernel.org
Cc: Joe Perches <joe@perches.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Vyacheslav Dubeyko <slava@dubeyko.com>
Cc: Hin-Tak Leung <htl10@users.sourceforge.net>
Cc: Anton Altaparmakov <aia21@cam.ac.uk>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Christoph Hellwig <hch@infradead.org>
Signed-off-by: Sergei Antonov <saproj@gmail.com>
---
 fs/hfsplus/brec.c | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/fs/hfsplus/brec.c b/fs/hfsplus/brec.c
index 6e560d5..754fdf8 100644
--- a/fs/hfsplus/brec.c
+++ b/fs/hfsplus/brec.c
@@ -131,13 +131,16 @@ skip:
 	hfs_bnode_write(node, entry, data_off + key_len, entry_len);
 	hfs_bnode_dump(node);
 
-	if (new_node) {
-		/* update parent key if we inserted a key
-		 * at the start of the first node
-		 */
-		if (!rec && new_node != node)
-			hfs_brec_update_parent(fd);
+	/*
+	 * update parent key if we inserted a key
+	 * at the start of the node and it is not the new node
+	 */
+	if (!rec && new_node != node) {
+		hfs_bnode_read_key(node, fd->search_key, data_off + size);
+		hfs_brec_update_parent(fd);
+	}
 
+	if (new_node) {
 		hfs_bnode_put(fd->bnode);
 		if (!new_node->parent) {
 			hfs_btree_inc_height(tree);
@@ -168,9 +171,6 @@ skip:
 		goto again;
 	}
 
-	if (!rec)
-		hfs_brec_update_parent(fd);
-
 	return 0;
 }
 
@@ -370,6 +370,8 @@ again:
 	if (IS_ERR(parent))
 		return PTR_ERR(parent);
 	__hfs_brec_find(parent, fd, hfs_find_rec_by_key);
+	if (fd->record < 0)
+		return -ENOENT;
 	hfs_bnode_dump(parent);
 	rec = fd->record;
 
-- 
2.3.0