Re: a take at cache coherency

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>]

:
:On 2006-01-24, Simon 'corecode' Schubert <corecode@xxxxxxxxxxxx> wrote:
:> actually I forgot about the need to have direct shadow associations and
:> thought about a replacement.  You are right, we can't do this.
:
:Unless Matt tells us how to live without direct shadow associations...

    I think we definitely need direct shadow assocations.

:> I'd still use a ncp_shadowroot to get O(1) locking.
:
:While you deref the the shadowroot pointer to go for the group lock,
:the group might get broken up, and the shadowroot info will be stale.

:With going step by step you can avoid such pitfalls: if the owner of the
:head lock (ie., the group lock) decides on to break up the group, then
:you will stop at some intermediate node (where the cut has taken place),
:but that's OK because that's then the new head, locked by you. So you
:end up with a consistent state.

    No, we run into a huge problem with separate locks.  For one thing,
    there is no safe way to manipulate the shadow chain in that case.

    We definitely need a common 'shadowroot' (I still hate that name)
    that contains a single lock representative of the entire chain.

    struct namecache {
	...
	struct shadowinfo *nc_shadowinfo;
	struct namecache *nc_shadowlink;	/* linked list or whatever */
	struct shadowinfo nc_shadowinfo_internal; /* degenerate case */
    }

    struct shadowinfo {
	lock
    }

    The common data structure for all elements of the shadow chain would 
    basically just contain the lock.  For the degenerate case 
    nc_shadowinfo would simply point to nc_shadowinfo_internal.

    The shadow chain would NEVER be allowed to be stale.  It could be
    partially unresolved, but the linkages cannot ever be stale (i.e.
    cannot ever be incorrect).  This generally means that an unresolved
    node needs to be disconnected from the chain.  The re-resolution of
    the node would reconnect it.


:There are no such concerns with a flat or star topology, but I really
:imagined node-to-node shadowing and not just one big hippie camp...

    Single child, multiple parents.  i.e. you have 10 nullfs mounts of /.  
    A simple circular linked list would be sufficient if the mount
    structure contains the relationship info, but its probably best to
    use a child pointer and a list of parents.

    struct namecache {
	...
	XXXXXX struct namecache *nc_shadowlink; XXXXX
	struct namecache *nc_shadow;	/* pointer to lower layer */
	TAILQ_HEAD ... 		/* list of parents */
	TAILQ_ENTRY ....	/* our node in a lower layer's parent list */
    }

:
:Hmm... it's true you can trade in cheap group modification for cheap
:locking: if you obtain all "interlocks" (non-head node locks) 
:before breaking up the group, you can keep the shadowroot data
:consistent. I think it would be deadlock free because only the group
:lock owner wants to have more than one interlock at a time.
:Given that you lock more than edit groups, it might be a good deal.

    I'd disagree with this.  Individual locking is a bad idea.  The
    entire chain needs to have a single lock because all operations
    generally have to manipulate the entire chain (or at least the shadow
    linkages within the chain).  You might as well just have a single
    lock.

:{f,t}ncp get invalidated, sure they have to. If they are leaf nodes,
:then it's the end of the story: when they get re-resolved they will get
:properly the post-rename associations. The overlay will do the same,
:as invalidations go up.

:Solution: upon tearing parent relations, also tear shadow associations.
:Yet another kind of invalidation. The upper layer will see the lack of a
:shadowed, and will recalculate it aptly.

    Yup.  Total agreement.  The invalidations would disconnect the
    shadow tree as they propogate upwards.  The common lock ensures
    that the data structure(s) can be manipulated without races.

:Regards,
:Csaba

					-Matt
					Matthew Dillon 
					<dillon@xxxxxxxxxxxxx>