Question about hfs_cat_keycmp

Question about hfs_cat_keycmp

[Rasmus Villemoes]

[scripts/get_maintainer.pl -f only gave this list, so here goes:]

hfs_cat_keycmp() in fs/hfs/catalog.c contains

  retval = be32_to_cpu(key1->cat.ParID) - be32_to_cpu(key2->cat.ParID);

Is it guaranteed/documented somewhere that these CNIDs are always within
2^31-1 of each other (in practice probably meaning that they are both in
[0, 2^31-1])? I suppose the answer to the 'guaranteed' part is yes, as
otherwise the Btree wouldn't work well...

Rasmus

Re: Question about hfs_cat_keycmp

[Vyacheslav Dubeyko]

On Tue, 2014-12-09 at 23:14 +0100, Rasmus Villemoes wrote:
> [scripts/get_maintainer.pl -f only gave this list, so here goes:]
> 
> hfs_cat_keycmp() in fs/hfs/catalog.c contains
> 
>   retval = be32_to_cpu(key1->cat.ParID) - be32_to_cpu(key2->cat.ParID);
> 
> Is it guaranteed/documented somewhere that these CNIDs are always within
> 2^31-1 of each other (in practice probably meaning that they are both in
> [0, 2^31-1])? I suppose the answer to the 'guaranteed' part is yes, as
> otherwise the Btree wouldn't work well...

Technical Note TN1150:

"Each file or folder in the catalog file is assigned a unique catalog
node ID (CNID). For folders, the CNID is the folder ID, sometimes called
a directory ID, or dirID; for files, it's the file ID. For any given
file or folder, the parent ID is the CNID of the folder containing the
file or folder, known as the parent folder.

The catalog node ID is defined by the CatalogNodeID data type.

typedef UInt32 HFSCatalogNodeID;

The first 16 CNIDs are reserved for use by Apple Computer, Inc. In
addition, the CNID of zero is never used and serves as a nil value.

Typically, CNIDs are allocated sequentially, starting at
kHFSFirstUserCatalogNodeID. Versions of the HFS Plus specification prior
to Jan. 18, 2000, required the nextCatalogID field of the volume header
to be greater than the largest CNID used on the volume (so that an
implementation could use nextCatalogID to determine the CNID to assign
to a newly created file or directory). However, this can be a problem
for volumes that create files or directories at a high rate (for
example, a busy server), since they might run out of CNID values.

HFS Plus volumes now allow CNID values to wrap around and be reused. The
kHFSCatalogNodeIDsReusedBit in the attributes field of the volume header
is set to indicate when CNID values have wrapped around and been reused.
When kHFSCatalogNodeIDsReusedBit is set, the nextCatalogID field is no
longer required to be greater than any existing CNID.

When kHFSCatalogNodeIDsReusedBit is set, nextCatalogID may still be used
as a hint for the CNID to assign to newly created files or directories,
but the implementation must verify that CNID is not currently in use
(and pick another value if it is in use). When CNID number nextCatalogID
is already in use, an implementation could just increment nextCatalogID
until it finds a CNID that is not in use. If nextCatalogID overflows to
zero, kHFSCatalogNodeIDsReusedBit must be set and nextCatalogID set to
kHFSFirstUserCatalogNodeID (to avoid using any reserved CNID values)."

I hope it helps.

Thanks,
Vyacheslav Dubeyko.

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

[PATCH] fs: hfs: Fix comparison bug in hfs_cat_keycmp

[Rasmus Villemoes]

Relying on the sign (after casting to int) of the difference of two
quantities for comparison is usually wrong. For example, should a-b
turn out to be 2^31, the return value of cmp(a,b) is -2^31; but that
would also be the return value from cmp(b, a). So a compares less than
b and b compares less than a. One can also easily find three values
a,b,c such that a compares less than b, b compares less than c, but a
does not compare less than c.

Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 fs/hfs/catalog.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/fs/hfs/catalog.c b/fs/hfs/catalog.c
index ff0316b925a5..db458ee3a546 100644
--- a/fs/hfs/catalog.c
+++ b/fs/hfs/catalog.c
@@ -162,14 +162,16 @@ err2:
  */
 int hfs_cat_keycmp(const btree_key *key1, const btree_key *key2)
 {
-	int retval;
+	__be32 k1p, k2p;
 
-	retval = be32_to_cpu(key1->cat.ParID) - be32_to_cpu(key2->cat.ParID);
-	if (!retval)
-		retval = hfs_strcmp(key1->cat.CName.name, key1->cat.CName.len,
-				    key2->cat.CName.name, key2->cat.CName.len);
+	k1p = key1->cat.ParID;
+	k2p = key2->cat.ParID;
 
-	return retval;
+	if (k1p != k2p)
+		return be32_to_cpu(k1p) < be32_to_cpu(k2p) ? -1 : 1;
+
+	return hfs_strcmp(key1->cat.CName.name, key1->cat.CName.len,
+			  key2->cat.CName.name, key2->cat.CName.len);
 }
 
 /* Try to get a catalog entry for given catalog id */
-- 
2.1.3

Re: [PATCH] fs: hfs: Fix comparison bug in hfs_cat_keycmp

[Vyacheslav Dubeyko]

On Wed, 2014-12-10 at 17:32 +0100, Rasmus Villemoes wrote:
> Relying on the sign (after casting to int) of the difference of two
> quantities for comparison is usually wrong. For example, should a-b
> turn out to be 2^31, the return value of cmp(a,b) is -2^31; but that
> would also be the return value from cmp(b, a). So a compares less than
> b and b compares less than a. One can also easily find three values
> a,b,c such that a compares less than b, b compares less than c, but a
> does not compare less than c.
> 

Looks good for me. Thank you for the fix.

Reviewed-by: Vyacheslav Dubeyko <slava@dubeyko.com>

Thanks,
Vyacheslav Dubeyko.

> Signed-off-by: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  fs/hfs/catalog.c | 14 ++++++++------
>  1 file changed, 8 insertions(+), 6 deletions(-)
> 
> diff --git a/fs/hfs/catalog.c b/fs/hfs/catalog.c
> index ff0316b925a5..db458ee3a546 100644
> --- a/fs/hfs/catalog.c
> +++ b/fs/hfs/catalog.c
> @@ -162,14 +162,16 @@ err2:
>   */
>  int hfs_cat_keycmp(const btree_key *key1, const btree_key *key2)
>  {
> -	int retval;
> +	__be32 k1p, k2p;
>  
> -	retval = be32_to_cpu(key1->cat.ParID) - be32_to_cpu(key2->cat.ParID);
> -	if (!retval)
> -		retval = hfs_strcmp(key1->cat.CName.name, key1->cat.CName.len,
> -				    key2->cat.CName.name, key2->cat.CName.len);
> +	k1p = key1->cat.ParID;
> +	k2p = key2->cat.ParID;
>  
> -	return retval;
> +	if (k1p != k2p)
> +		return be32_to_cpu(k1p) < be32_to_cpu(k2p) ? -1 : 1;
> +
> +	return hfs_strcmp(key1->cat.CName.name, key1->cat.CName.len,
> +			  key2->cat.CName.name, key2->cat.CName.len);
>  }
>  
>  /* Try to get a catalog entry for given catalog id */