Re: a take at cache coherency

["Simon 'corecode' Schubert" <corecode@xxxxxxxxxxxx>]

Csaba Henk wrote:
> > We need to linearize the cache entries anyways now, as we can't 
> > maintain a tree structure with doubly linked lists.
> We don't need to linearize them. We can use the same tree layout as in
> the fs hierarchy: pointers in one direction, list of neighbours in the
> other direction.

okay, I see now.  This is a possibility as well.  So we'd have

ncp_shadowed and SLIST_HEAD(ncp_shadows) and thus also ncp_shadowlink

> So, from this on I'll assume the latter: having the flat thing as an
> addendum.

actually I forgot about the need to have direct shadow associations and 
thought about a replacement.  You are right, we can't do this.

I'd still use a ncp_shadowroot to get O(1) locking.  And if you are 
concerned about data replication/keeping it in sync, we could even 
access most data (which is only used internally in the cache layer) 
directly from the shadowroot (== group head).

> From the performance POV: yeah, you could do locks in O(1) time instead
> of O(d), where d is the depth of the shadow tree. But is it worth for
> any effort and extending the namecache struct further? I doubt if ever
> anyone would want to create an overlay of about hundred levels... even
> ten would be pretty eccentric.

not at all.  i'm thinking of packaging systems which use layered 
filesystems to show packages (or not), stuff like this...

> > now, if we want to e.g. rename the whole group, we just start at 
> > ncp_shadowroot and cycle through ncp_shadowlinks.
> Renaming seems to be a truly individual act -- at least, I can't think
> of any useable semantics for an operation like "group rename".

i expressed myself wrongly.  i ment "rename which requires us to rename 
all associated namecache shadow entries in the group".

> AFAICS the critical one is breaking down the parent/child relation.  My
> idea is that a p/c cut should imply breaking down shadower/shadowed
> relatons. If we do that, the upper layer will see the lack of the link
> into the lower one, and will recreate that as it's appropriate in the
> new situation. The upper layer wouldn't be aware of the rename event in
> the lower one as such.

I don't understand this parent/child thing.  could you please elaborate 
on this?  We don't have disconnected namecache entries, but maybe it's 
something else you are talking about.

> > the only thing that (still) bothers me is:   what happens if somebody 
> > locks (cache_lookup) an unresolved (and thus unconnected) nullncp and 
> > locks the shadowed ncp (where the system doesn't know about yet about 
> > this connection).  imagine two processes doing this, each in 
> > different order:
> >
> > time	thread1			thread2
> > 1	lock null		lock lower
> > 2	resolve null (blocks)	lock null (blocks)
> >
> > we have a deadlock.  resolving null means having to lock lower, but 
> > this fails as another thread already obtained the lock.
> Locking is a group operation. Therefore it must be group atomic -- eg.,
> locking the group can't mean obtaining a lock (in the old sense) on 
> each
> entry simultaneously.

Yes, unless the null layer isn't yet associated with the lower layer.

> There must be one distinguished parameter in the group which carries
> locked/unlocked state. In my approach it's the nc_exlocks field of the
> group head. If a thread has that bumped, it has obtained the lock on 
> the
> whole group.

yes, all roger.

> Regarding your example, thread2 won't perform a separate "lock null"
> step.

unless it just wants to lock two entries of which it doesn't know the 
shadow assocition.  maybe for renaming or whatnot.

cheers
  simon

--
Serve - BSD     +++  RENT this banner advert  +++    ASCII Ribbon   /"\
Work - Mac      +++  space for low €€€ NOW!1  +++      Campaign     \ /
Party Enjoy Relax   |   http://dragonflybsd.org      Against  HTML   \
Dude 2c 2 the max   !   http://golden-apple.biz       Mail + News   / \

Attachment: PGP.sig
Description: This is a digitally signed message part