Add parent refcount cache

The idea here is that we check with references towards root quite
often. Since we have a one-byte gap in StatementContextBase, we can
use it to track knowledge of what parent refs look like -- and
side-step a lot of pointer chasing on our way to root.

JIRA: YANGTOOLS-1184
Change-Id: I6342292d8f6675ef446dca8410bb859e2d6f230c
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java
index 646ea112183f0d6208132be305a550d5f4dbdbcc..b83df70b538c5d45a1bc8a84f395026cf62a6ce9 100644 (file)
--- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java
+++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/AbstractResumedStatement.java
@@ -206,6 +206,12 @@ abstract class AbstractResumedStatement<A, D extends DeclaredStatement<A>, E ext
         return effective.stream();
     }
 
+    @Override
+    final void markNoParentRef() {
+        markNoParentRef(substatements);
+        markNoParentRef(effective);
+    }
+
     @Override
     final int sweepSubstatements() {
         // First we need to sweep all statements, which may trigger sweeps all across the place, for example:

diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java
index c355148b604c94c05ba2246169c6c4294fd9f87f..0119c6bc329b9526f867bc8f07bf9397898add43 100644 (file)
--- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java
+++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/InferredStatementContext.java
@@ -294,6 +294,14 @@ final class InferredStatementContext<A, D extends DeclaredStatement<A>, E extend
         verify(substatements != SWEPT_SUBSTATEMENTS, "Attempted to access substatements of %s", this);
     }
 
+    @Override
+    void markNoParentRef() {
+        final Object local = substatements;
+        if (local != null) {
+            markNoParentRef(castEffective(local));
+        }
+    }
+
     @Override
     int sweepSubstatements() {
         final Object local = substatements;

diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java
index 0ce875db9e4ab2f57a69cac7c8f85b5b743d64d5..adca75ce7dcfadcc61bd3abf95ea34660cd02901 100644 (file)
--- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java
+++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReactorStmtCtx.java
@@ -545,6 +545,16 @@ abstract class ReactorStmtCtx<A, D extends DeclaredStatement<A>, E extends Effec
     //
     //
 
+    /**
+     * Local knowledge of {@link #refcount} values up to statement root. We use this field to prevent recursive lookups
+     * in {@link #noParentRefs(StatementContextBase)} -- once we discover a parent reference once, we keep that
+     * knowledge and update it when {@link #sweep()} is invoked.
+     */
+    private byte parentRef = PARENTREF_UNKNOWN;
+    private static final byte PARENTREF_UNKNOWN = -1;
+    private static final byte PARENTREF_ABSENT  = 0;
+    private static final byte PARENTREF_PRESENT = 1;
+
     /**
      * Acquire a reference on this context. As long as there is at least one reference outstanding,
      * {@link #buildEffective()} will not result in {@link #effectiveSubstatements()} being discarded.
@@ -582,28 +592,60 @@ abstract class ReactorStmtCtx<A, D extends DeclaredStatement<A>, E extends Effec
 
         refcount = current - 1;
         LOG.trace("Refcount {} on {}", refcount, this);
-        if (isSweepable()) {
+
+        if (refcount == REFCOUNT_NONE) {
+            lastDecRef();
+        }
+    }
+
+    private void lastDecRef() {
+        if (noImplictRef()) {
             // We are no longer guarded by effective instance
             sweepOnDecrement();
+            return;
+        }
+
+        final byte prevRefs = parentRef;
+        if (prevRefs == PARENTREF_ABSENT) {
+            // We are the last reference towards root, any children who observed PARENTREF_PRESENT from us need to be
+            // updated
+            markNoParentRef();
+        } else if (prevRefs == PARENTREF_UNKNOWN) {
+            // Noone observed our parentRef, just update it
+            loadParentRefcount();
         }
     }
 
-    /**
-     * Sweep this statement context as a result of {@link #sweepSubstatements()}, i.e. when parent is also being swept.
-     */
-    private void sweep() {
-        if (isSweepable()) {
-            LOG.trace("Releasing {}", this);
-            sweepState();
+    static final void markNoParentRef(final Collection<? extends ReactorStmtCtx<?, ?, ?>> substatements) {
+        for (ReactorStmtCtx<?, ?, ?> stmt : substatements) {
+            final byte prevRef = stmt.parentRef;
+            stmt.parentRef = PARENTREF_ABSENT;
+            if (prevRef == PARENTREF_PRESENT && stmt.refcount == REFCOUNT_NONE) {
+                // Child thinks it is pinned down, update its perspective
+                stmt.markNoParentRef();
+            }
         }
     }
 
+    abstract void markNoParentRef();
+
     static final void sweep(final Collection<? extends ReactorStmtCtx<?, ?, ?>> substatements) {
         for (ReactorStmtCtx<?, ?, ?> stmt : substatements) {
             stmt.sweep();
         }
     }
 
+    /**
+     * Sweep this statement context as a result of {@link #sweepSubstatements()}, i.e. when parent is also being swept.
+     */
+    private void sweep() {
+        parentRef = PARENTREF_ABSENT;
+        if (refcount == REFCOUNT_NONE && noImplictRef()) {
+            LOG.trace("Releasing {}", this);
+            sweepState();
+        }
+    }
+
     static final int countUnswept(final Collection<? extends ReactorStmtCtx<?, ?, ?>> substatements) {
         int result = 0;
         for (ReactorStmtCtx<?, ?, ?> stmt : substatements) {
@@ -629,7 +671,7 @@ abstract class ReactorStmtCtx<A, D extends DeclaredStatement<A>, E extends Effec
     // Called when this statement does not have an implicit reference and have reached REFCOUNT_NONE
     private void sweepOnDecrement() {
         LOG.trace("Sweeping on decrement {}", this);
-        if (noParentRefcount()) {
+        if (noParentRef()) {
             // No further parent references, sweep our state.
             sweepState();
         }
@@ -657,7 +699,7 @@ abstract class ReactorStmtCtx<A, D extends DeclaredStatement<A>, E extends Effec
         }
 
         // parent is potentially reclaimable
-        if (noParentRefcount()) {
+        if (noParentRef()) {
             LOG.trace("Cleanup {} of parent {}", refcount, this);
             if (sweepState()) {
                 final ReactorStmtCtx<?, ?, ?> parent = getParentContext();
@@ -672,29 +714,40 @@ abstract class ReactorStmtCtx<A, D extends DeclaredStatement<A>, E extends Effec
         return effectiveInstance != null || !isSupportedToBuildEffective();
     }
 
-    // FIXME: cache the resolution of this
-    private boolean noParentRefcount() {
+    private boolean noParentRef() {
+        return parentRefcount() == PARENTREF_ABSENT;
+    }
+
+    private byte parentRefcount() {
+        final byte refs;
+        return (refs = parentRef) != PARENTREF_UNKNOWN ? refs : loadParentRefcount();
+    }
+
+    private byte loadParentRefcount() {
+        return parentRef = calculateParentRefcount();
+    }
+
+    private byte calculateParentRefcount() {
         final ReactorStmtCtx<?, ?, ?> parent = getParentContext();
-        if (parent != null) {
-            // There are three possibilities:
-            // - REFCOUNT_NONE, in which case we need to search next parent
-            // - negative (< REFCOUNT_NONE), meaning parent is in some stage of sweeping, hence it does not have
-            //   a reference to us
-            // - positive (> REFCOUNT_NONE), meaning parent has an explicit refcount which is holding us down
-            final int refs = parent.refcount;
-            return refs == REFCOUNT_NONE ? parent.noParentRefcount() : refs < REFCOUNT_NONE;
+        if (parent == null) {
+            return PARENTREF_ABSENT;
+        }
+        // There are three possibilities:
+        // - REFCOUNT_NONE, in which case we need to search next parent
+        // - negative (< REFCOUNT_NONE), meaning parent is in some stage of sweeping, hence it does not have
+        //   a reference to us
+        // - positive (> REFCOUNT_NONE), meaning parent has an explicit refcount which is holding us down
+        final int refs = parent.refcount;
+        if (refs == REFCOUNT_NONE) {
+            return parent.parentRefcount();
         }
-        return true;
+        return refs < REFCOUNT_NONE ? PARENTREF_ABSENT : PARENTREF_PRESENT;
     }
 
     private boolean isAwaitingChildren() {
         return refcount > REFCOUNT_SWEEPING && refcount < REFCOUNT_NONE;
     }
 
-    private boolean isSweepable() {
-        return refcount == REFCOUNT_NONE && noImplictRef();
-    }
-
     private void sweepOnChildDone() {
         LOG.trace("Sweeping on child done {}", this);
         final int current = refcount;

diff --git a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java
index 173e9315bac5587fe15289c71eeda00e38bca1d1..199416dcf27da8da3794261d38c5646999993702 100644 (file)
--- a/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java
+++ b/yang/yang-parser-reactor/src/main/java/org/opendaylight/yangtools/yang/parser/stmt/reactor/ReplicaStatementContext.java
@@ -117,6 +117,11 @@ final class ReplicaStatementContext<A, D extends DeclaredStatement<A>, E extends
         return source.definition();
     }
 
+    @Override
+    void markNoParentRef() {
+        // No-op
+    }
+
     @Override
     int sweepSubstatements() {
         if (fullyDefined()) {