DragonFly BSD
DragonFly kernel List (threaded) for 2006-01
[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]

Re: a take at cache coherency


From: "Simon 'corecode' Schubert" <corecode@xxxxxxxxxxxx>
Date: Tue, 24 Jan 2006 21:53:33 +0100

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



[Date Prev][Date Next]  [Thread Prev][Thread Next]  [Date Index][Thread Index]