Subject: Re: [netatalk-admins] DIDs - an idea -or- I didn't read the AFP specs completely yet

From: Duncan Sinclair <[email-masked]>
Date: Thu, 16 Apr 1998 20:22:41 +0100

"Donald L. Nash" writes:
>... DIDs are only 32
>bits long.  I looked into using inode numbers combined with major and minor
>device numbers to create an inode-based DID that worked for volumes which
>span filesystems, but had to give up on it because inode numbers are 24 bits
>long and major and minor device numbers are each 8 bits long.  I couldn't
>figure out a way to cram 40 bits into 32 without the possibility of
>collision. :-)

I would have thought this is still the key to the solution.  As a
database lookup has to be implemented anyway, you just use a hash
function, and hash the 40 bits down to 32.  When you get a collision,
use a secondary hash function.

I guess this sort of thing can be done by berkeley db or gdbm.  (I'd
prefer berkeley db myself.)  Or you can roll your own hash table
pretty easily.

This gives you everything you need.  The database is keyed by the DID or
the i-node/device combination and contains the (complete) path. Keeping
the database consistant should be an easy task.  E.g. when a directory is
moved you still know its inode/dev number, so you can reset the path.

I would still recommend a separate process for the management of this
database, but I'm sure the concurrent access problem could be solved
some other way.

I guess all the same applies to file numbers.

Hope this inspires someone...

Duncan Sinclair.

---

From: Andras Kadinger <[email-masked]>
Date: Fri, 17 Apr 1998 01:44:16 +0200

> prefer berkeley db myself.)  Or you can roll your own hash table

Not to open a debate, but I don't see what You gain by hashing, and not
just bumping a counter. You have to keep the database anyway.

> moved you still know its inode/dev number, so you can reset the path.

I assume, You discover a moved directory by not finding it at the right
place. If you try to locate that directory purely by inode/dev number,
You lose if the given inode was reused; not to mention, that - AFAIK -
there is no simple way to get a pathname from an inode/dev number (I
might be wrong here), so You would have to search the tree for the
directory, which is very close to searching for the unambiguous [in
contents I mean] .DID file in the directory. The only case I see You
could lose here is when some uneducated user removes the .DID file, in
which case all Your aliases pointing to this dir would break; but You
still would not resolve to a wrong one, as with inode reuse You could
based on inode/dev.

Or did You think about performance issues? Clear me up, please!

Sincerely,
Andras Kadinger
[email-masked]

---

From: William LeFebvre <[email-masked]>
Date: Thu, 16 Apr 1998 20:09:48 -0400

> Or did You think about performance issues? Clear me up, please!

If the inode number is for a directory, you actually can derive a
pathname for it, much in the same way that pwd does.  I wrote code
to do this aeons ago.  However, it requires lots of diddling around
on the raw device.  Since you can't open a file by inode number you
have to look at the file's contents baesd on the block numbers in
the inode,  Then you can find the inode number for "..".  Recurse
until you reach the root (special code needed for crossing mount
points, too).  For performance it's only slightly worse than a pwd,
and can't take advantage of any kernel caching.  It also requires
the ability to open the raw device, which usually means being root.

An inode number for a non-directory can't be translated in to a path
without scanning the whole disk.  This is primarily because it could
potentially be present in multiple directories.  But since we're
talking about DIDs here, then we're already dealing only with
directories.

				William LeFebvre
				Group sys Consulting
				<[email-masked]>
				+1 770 813 3224