Re: key64_t? ino64_t?

[Robert Collins <rbcollins at cygwin dot com>]

On Thu, 2003-05-15 at 09:34, Charles Wilson wrote:
> Corinna said:
> >On Wed, May 14, 2003 at 07:09:24PM +1000, Robert Collins wrote:
> >> Aliasing isn't bad. However: we *must* prevent clashes. Probability has
> >> nothing to do with it. I can't comment on the Linux implementation: I
> >> haven't reviewed it.
> >
> > My Linux man page tells me:
> >
> >    Of  course  no  guarantee  can be given that the resulting
> >    key_t is unique. Typically, a best effort attempt combines
> >    the  given  proj_id  byte, the lower 16 bits of the i-node
> >    number, and the lower 8 bits of the device number  into  a
> >    32-bit  result.  Collisions may easily happen, for example
> >    between files on /dev/hda1 and files on /dev/sda1.
> >
> > So Chuck's implementation is a multiple better than the Linux one
> > without the need to involve trees or tries.
> 
> Yes, and as I posted earlier (in another thread on the main list), MY
> linux man page says
> 
>        The generated key_t value is obtained  stat-ing  the  disk
>        file  corresponding to pathname in order to get its i-node
>        number and the minor device number of  the  filesystem  on
>        which  the  disk file resides, then by combining the 8 bit
>        proj value along with the lower 16 bits of the i-node num­
>        ber,  along  with  the  8 bits of the minor device number.
>        The algorithm does not guarantee a unique key  value.   In
>        fact
> 
>        ·      Two  different  names linking to the same file pro­
>               duce same key values.
> 
>        ·      Using the lower 16 bits of the i-node number, gives
>               some  chance  (also usually small) to have same key
>               values  for  file  names  referring  to   different
>               i-nodes.
> 
>        ·      Not  discriminating  among  major  device  numbers,
>               gives some chance of collision (also usually small)
>               for systems with multiple disk controllers.


And my copy of P1003.1 says:
"The ftok() function shall return the same key value for all paths that
name the same file, when called with the same id value, and return
different key values when called with different id values or with paths
that name differnet files existing on the same file system at the same
time."

Key things to note: sus doesn't require uniqueness across file systems 
- but it's a good idea if we can do that for low or no extra cost/
It *does* require uniqueness within a file system.

Rob
-- 
GPG key available at: <http://users.bigpond.net.au/robertc/keys.txt>.

Attachment: signature.asc
Description: This is a digitally signed message part