From: | "Simon 'corecode' Schubert" <corecode@xxxxxxxxxxxx> |
Date: | Tue, 24 Jan 2006 21:53:33 +0100 |
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.
So, from this on I'll assume the latter: having the flat thing as an addendum.
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.
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".
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.
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:Locking is a group operation. Therefore it must be group atomic -- eg.,
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 the group can't mean obtaining a lock (in the old sense) on each
entry simultaneously.
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.
Regarding your example, thread2 won't perform a separate "lock null" step.
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