Skip to contentSkip to conversation

Question about hfs_cat_keycmp

PATCH In review Rasmus Villemoes 2 participants 4 messages Dec 9, 2014 – Dec 10, 2014

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

[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

#1 lore raw
Quoted 10 lines · 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...

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.

Quoted 6 lines

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

#2 lore raw

PATCH 1/1 fs: hfs: Fix comparison bug in hfs_cat_keycmp

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.

---
 fs/hfs/catalog.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)
fs/hfs/catalog.c +8 -6
index ff0316b925a5..db458ee3a546 100644
@@ -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 */
Signature · 1 line
2.1.3
maintainer Reviewed-by on v1 1/1
#3 lore raw

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

Quoted 8 lines · 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.

Looks good for me. Thank you for the fix.

Thanks,
Vyacheslav Dubeyko.

Quoted 32 lines
---
 fs/hfs/catalog.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)
fs/hfs/catalog.c +8 -6
index ff0316b925a5..db458ee3a546 100644
@@ -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 */