key64_t? ino64_t?

Charles Wilson
Wed May 14 23:34:00 GMT 2003

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

       ·      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

       ·      Not  discriminating  among  major  device  numbers,
              gives some chance of collision (also usually small)
              for systems with multiple disk controllers.

  Charles Wilson
  cygwin at removespam cwilson dot fastmail dot fm

More information about the Cygwin-developers mailing list