Re: unionfs: ULFS information storage issues

[Sergiu Ivanov]

Hello,

On Thu, Oct 29, 2009 at 07:30:41AM +0100, olafBuddenhagen@gmx.net wrote:
> On Mon, Aug 17, 2009 at 01:03:30PM +0300, Sergiu Ivanov wrote:
> 
> > If one would like to keep *both* the information about the filesystems
> > *and* the ports to their root nodes in *a single* place, one would
> > have two choices: either add something like a ``port'' field to each
> > entry in the ulfs_chain, thus duplicating the port list in the
> > netfs_root_node and still leaving the necessity of synchronizing
> > things explicitly; or keep the information about the filesystems (i.e.
> > the information stored in ulfs_chain) in *every* node, thus
> > duplicating the same bits of information across a (potentially) large
> > number of locations.
> 
> Obviously we can't keep the information for all the nodes and for the
> constituent filesystmes in one place, considering that there are several
> nodes per filesystem. All we want is to make sure that the information
> in the list of any particular node and in the list of filesystems can be
> easily associated.
> 
> I can see at least three ways to do it:
> 
> - Make sure that the per-node lists can also easily be addressed by a
>   numeric index, so we can read both the filesystem list and the
>   per-node lists with a simple loop counter.

I guess the efficient implementation of this approach is possible
either via arrays or libihash (if I understand correctly what its
purpose is).  At first I thought that arrays are a clumsy solution,
but having looked at it more, I am not so sure of it.  Arrays would
have to be resized when the list of unioned directories is modified,
which isn't normally a frequent operation.  Provided this reasoning, I
wouldn't be much of a fan of libihash in this context.
 
> - Make sure that it's easy to figure out the numeric index of any given
>   per-node list entry, so when iterating the per-node list, we can
>   directly look up the corresponding entry in the filesystem list
>   without having to keep an extra counter.

This might be possible by keeping an index in each entry in the
per-node lists, but I'm not sure whether this is really efficient,
because if both global and per-node lists are still implemented as
linked lists, knowing the index is not an advantage at all.

OTOH, we could combine the current and the previous points and keep
the global list in an array and implement per-node lists as linked
lists.  To iterate the lists in parallel, one would traverse the
per-node list and directly access the corresponding global list entry
by the index in the current per-node list entry.
 
> - Let the per-node entries keep pointers to the entries in the
>   filesystem list, so we can access them directly when iterating the
>   per-node lists.

I think I'll declare myself a fan of this idea :-) IMHO, it's the most
efficient and elegant of all :-) It keeps the advantage of linked
lists, and the cost of keeping the local and per-node lists
synchronized is still minimal.

Regards,
scolobb