This is the mail archive of the cygwin-developers@cygwin.com mailing list for the Cygwin project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: key64_t? ino64_t?


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.

--Chuck
--
  Charles Wilson
  cygwin at removespam cwilson dot fastmail dot fm


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]