Re: Question about hfs_cat_keycmp

[Vyacheslav Dubeyko <slava@dubeyko.com>]

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