Bug #129

namecache coherency 3rd turn

Added by csaba.henk over 8 years ago. Updated almost 3 years ago.

Status:ClosedStart date:
Priority:LowDue date:
Assignee:-% Done:

0%

Category:-
Target version:-

Description

Hi!

This time the following changes were made:

- Namecache locks are kept by shadowinfo structures which
can be embedded into the namecache structure itself (singleton
groups) or fetched from a pool (for non-singleton groups).

- Shadow group data structure: I ended up at what has been
suggested by Matt earlier: shadow group entries form a circular list.
Double linked in order to support O(1) node deletion, enhanced
with a height counter to retain tree semantics.

- cache_setunresolved(ncp) blows up subtree over ncp to break broken
topologies.

- Deadlock avoiding techniques of the previous patch have been kept.

- The "struct namecache *nc_shadowed" field of namecache structures
still exists, but is nowhere referred by cache code. Now it's sort
of a private field, almost like the "void *" fields in vnodes,
specinfo structures, etc. It could be easily ditched and replaced by
per-mount hash for those fs-es who would use it. I just kept it as
is -- I didn't want to do anything about it without having a
consensus.

- Nullfs adjusted to this API.

Regards,
Csaba

ncc3.diff Magnifier (18.5 KB) csaba.henk, 03/29/2006 10:02 AM

ncc3-null.diff Magnifier (14.2 KB) csaba.henk, 03/29/2006 10:02 AM

History

#1 Updated by csaba.henk over 8 years ago

Minor update:

- made cache code topology agnostic (ie., tree layout hints [height] are
maintained but not used by the cache code itself, group members are
treated uniformly);

- made group traversal routine public;

- panic fix for nullfs.

The respective diffs for the cache system and nullfs are available here:

http://creo.hu/~csaba/tmp/visible/dfly/

as well as incremental diffs from the latest posted patches.

Regards,
Csaba

#2 Updated by corecode over 8 years ago

On 03.04.2006, at 09:51, Csaba Henk wrote:

> +static struct shadowinfo *
> +shadowinfo_fetch(void)
> +{
> + struct shadowinfo *shinf = STAILQ_FIRST(&shadowinfo_freeq);
> +
> + if (! shinf)
> + goto alloc;

I'm strongly against adding a cache mechanism here. We should use a
generic object cache whereever possible (and bring that one in shape,
hint, hint). Then this would be a matter of:

shinf = objcache_alloc(shadowinfo_cache, M_WAITOK);

the approach you are taking is not MP-friendly at all, as it needs a
lock, but I think you aware of this anyways. Just let us not do such
optimizations prematurely. using malloc() should be sufficient right
now.

> @@ -295,6 +360,10 @@ cache_alloc(int nlen)
> ncp->nc_error = ENOTCONN; /* needs to be resolved */
> ncp->nc_refs = 1;
> ncp->nc_fsmid = 1;
> + ncp->nc_shadowinfo = &ncp->nc_shadowinfo_internal;
> + ncp->nc_shadowinfo_internal.sh_refs = 2;
> + ncp->nc_shadow_prev = NULL;
> + ncp->nc_shadow_next = NULL;

why is refs == 2? This would at least need a comment explaining this
number.

sncp is locked here:
[1]:
> +int
> +cache_shadow_attach(struct namecache *ncp, struct namecache *sncp)
> +{
> + struct migrate_param mpm;
[..]
> + if (sncp->nc_shadowinfo == &sncp->nc_shadowinfo_internal) {
> + mpm.heightdelta = 0;
> + mpm.shadowinfo = shadowinfo_fetch();
> + mpm.exlocks = sncp->nc_shadowinfo->sh_exlocks;
> + migrate_updater(sncp, &mpm);
> + }

[2]:
[..]
> @@ -372,16 +628,15 @@ cache_lock(struct namecache *ncp)
[..]
> - ncp->nc_flag |= NCF_LOCKREQ;
> - if (tsleep(ncp, 0, "clock", nclockwarn) == EWOULDBLOCK) {
> + shinf->sh_lockreq = 1;
> + if (tsleep(shinf, 0, "clock", nclockwarn) == EWOULDBLOCK) {
[..]

[..]
> + if (--shinf->sh_exlocks == 0) {
> + shinf->sh_locktd = NULL;
> + if (shinf->sh_lockreq) {
> + shinf->sh_lockreq = 0;
> + wakeup(shinf);

I think there is a race condition which Matt already pointed out:

Thread1 Thread2
[2]

[2] (tsleeps on ncp->nc_shadowinfo_internal)

[1] (migrates shinfo to an external struct)
[3] (wakes up external shinfo)
ncp is unlocked and gets freed

thread2 will sleep on ncp, but will never get woken up. tsleep will
return after some time and then access a non-existing ncp.

cheers
simon

#3 Updated by csaba.henk over 8 years ago

On Mon, Apr 03, 2006 at 01:24:50PM +0200, Simon 'corecode' Schubert wrote:

I updated the patch according to your suggestions (plus fixed a panic). See
again

http://creo.hu/~csaba/tmp/visible/dfly/ ,

updated.

> generic object cache whereever possible (and bring that one in shape,
> hint, hint). Then this would be a matter of:
>
> shinf = objcache_alloc(shadowinfo_cache, M_WAITOK);

What do you think of? In what ways would this be more than a
macro-glorified version of the simplistic design I had for shadowinfo?
Would it use low-level optimized allocation routines?

> Just let us not do such optimizations prematurely. using malloc()
> should be sufficient right now.

Well OK, that just made the code simpler ATM.

> >@@ -295,6 +360,10 @@ cache_alloc(int nlen)
> > ncp->nc_error = ENOTCONN; /* needs to be resolved */
> > ncp->nc_refs = 1;
> > ncp->nc_fsmid = 1;
> >+ ncp->nc_shadowinfo = &ncp->nc_shadowinfo_internal;
> >+ ncp->nc_shadowinfo_internal.sh_refs = 2;
> >+ ncp->nc_shadow_prev = NULL;
> >+ ncp->nc_shadow_next = NULL;
>
> why is refs == 2? This would at least need a comment explaining this
> number.

Sure, I added:

/*
* nc_shadowinfo_internal:
* one ref for being contained in ncp, one for ncp being locked via it.
* (This leverages us from dealing with "internal" vs. "standalone"
* when dealing with shadowinfo references).
*/

Alternatively, there could be a flag displaying if the shadowinfo is
internal or standalone, and make the ref/put routines act based on this.
Would that be preferable?

> sncp is locked here:
> [1]:
> >+int
> >+cache_shadow_attach(struct namecache *ncp, struct namecache *sncp)
> >+{
> >+ struct migrate_param mpm;
> [..]
> >+ if (sncp->nc_shadowinfo == &sncp->nc_shadowinfo_internal) {
> >+ mpm.heightdelta = 0;
> >+ mpm.shadowinfo = shadowinfo_fetch();
> >+ mpm.exlocks = sncp->nc_shadowinfo->sh_exlocks;
> >+ migrate_updater(sncp, &mpm);
> >+ }
>
> [2]:
> [..]
> >@@ -372,16 +628,15 @@ cache_lock(struct namecache *ncp)
> [..]
> >- ncp->nc_flag |= NCF_LOCKREQ;
> >- if (tsleep(ncp, 0, "clock", nclockwarn) == EWOULDBLOCK) {
> >+ shinf->sh_lockreq = 1;
> >+ if (tsleep(shinf, 0, "clock", nclockwarn) == EWOULDBLOCK) {
> [..]
>
> [3]:
> >@@ -436,17 +695,45 @@ cache_unlock(struct namecache *ncp)
> > cache_unlock(struct namecache *ncp)
> > {
> [..]
> >+ if (--shinf->sh_exlocks == 0) {
> >+ shinf->sh_locktd = NULL;
> >+ if (shinf->sh_lockreq) {
> >+ shinf->sh_lockreq = 0;
> >+ wakeup(shinf);
>
>
> I think there is a race condition which Matt already pointed out:
>
> Thread1 Thread2
> [2]
>
> [2] (tsleeps on ncp->nc_shadowinfo_internal)
>
> [1] (migrates shinfo to an external struct)
> [3] (wakes up external shinfo)
> ncp is unlocked and gets freed
>
> thread2 will sleep on ncp, but will never get woken up. tsleep will
> return after some time and then access a non-existing ncp.

Right -- I just forgot about it... Now I simply inserted a wakeup() before
putting the shadowinfo in the migration routine.

AFAICS that's enough and we don't need to hold an extra ref for the
shadowinfo while sleeping on it in cache_lock(), because the variable
"shinf" gets re-initialized when sleeping is over (to the same value or
to something else -- that doesn't make a difference for the lock
routine).

Regards,
Csaba

#4 Updated by alexh over 5 years ago

There has been a lot of work on the namecache since this was posted; is it
still of interest?

Cheers,
Alex Hornung

#5 Updated by csaba.henk over 5 years ago

I think these things have been dealt with since then. (Pls confirm someone who is
more involved than me in Dfly...(O

Csaba

#6 Updated by ftigeot almost 3 years ago

  • Description updated (diff)
  • Status changed from New to Closed
  • Assignee deleted (0)

Closing due to lack of recent feedback.

Also available in: Atom PDF