Repository: netty/netty
Issue: HTTP/2 Priority Tree circular link
Labels: defect

There is an issue with the HTTP/2 priority tree algorithm where circular links can be created.  The issue is if an exclusive dependency event described as `stream B should be an exclusive dependency of stream A` is requested and stream `B` is already a child of stream `A`...then we will add `B` to `B`'s own `children` map and create a circular link in the priority tree.  This leads to an infinite recursive loop and a stack overflow exception.


Issue comments:
@nmittler @buchgr - FYI...I have a fix for this.  Standby.

https://github.com/netty/netty/issues/3618 fixed this


Pull request review comments:
maybe just call this `retain`?

Doesn't `removeStream` notify the listeners that the stream was removed?

if `oldParent != null`, isn't it an error condition if removal of the child from `oldParent` is null?

Isn't it an error condition if the `put` != null? Maybe we should throw if that's the case?

I wonder if we really need a second hash map for this.  To reduce object allocation, could we just do something like:

``` java
DefaultStream[] childArray = children.values();
for(int index=0; index < childArray.length; ++index) {
    DefaultStream grandChild = childArray[index];
    if (child.id() != grandChild.id()) {
         child.takeChild(grandChild, false, events);
    }
}
```

Done.

Yes if it is able to remove the stream.  Is there a specific issue you are worried about here?

Ah I think I just read this too fast ... looks like that is the intent here.  Makes sense. Do you have a test for this?

I don't think so.  When a stream is created the connection stream does a `takeChild` on that stream....and the new stream's parent will be null.  After this it would be an error condition though...were you thinking of having the connection stream override this method and have the mainstream case not have to worry about the null check?

Yes I think with the new conditional statement guarding this we should no longer have to worry about a stream existing with the same ID.  This condition seems like a programming error, should we just assert?

I think this would lead to concurrent modification scenarios.  Unless you are implying a copy operation via the `children.values();`.

Ok. Yes `priorityChangeWithNoPrioritizableDependentsShouldRestructureTree` hits this.

@nmittler - Your comment was collapsed:

> > I wonder if we really need a second hash map for this. To reduce object allocation, could we just do something like:
> > 
> > DefaultStream[] childArray = children.values();
> > for(int index=0; index < childArray.length; ++index) {
> >     DefaultStream grandChild = childArray[index];
> >     if (child.id() != grandChild.id()) {
> >          child.takeChild(grandChild, false, events);
> >     }
> > }

my response:

> I think this would lead to concurrent modification scenarios.  Unless you are implying a copy operation via the `children.values();`.

@Scottmitch not quite sure I follow. So in the case of a new stream, I think you're saying that `oldParent == null`?  I was actually referring to the case where `oldParent != null`.

sgtm, thanks!

Are we concerned with any side-effects with calling back the listener here while we're in the middle of rearranging the priority tree?  I wonder if it would be better to store up these removal events and execute them at the end?

sgtm ... I think what you have is fine.

@nmittler - I think I'm confused now :)

> if oldParent != null, isn't it an error condition if removal of the child from oldParent is null?

Seems like you are saying "if `oldParent == null` isn't this an error".  This is what my `I don't think so` applied to.

> So in the case of a new stream, I think you're saying that oldParent == null

Yes.  New streams start with `parent = null`.  Then `connection.takeChild(newStream,...)` is called (for everything but the connection stream....connection stream parent remains `null`).

> > if oldParent != null, isn't it an error condition if removal of the child from oldParent is null?
> 
> Seems like you are saying "if `oldParent == null` isn't this an error".  This is what my `I don't think so` applied to.

Ah ok, I think I understand your confusion now :).  So looking at this line:

``` java
if (oldParent != null && oldParent.children.remove(child.id()) != null)
```

My original question was: how can `oldParent.children.remove(child.id())` ever be `null`? In fact, it seems like it should be an error condition as this would imply an inconsistency in the tree ... or am I missing something?

Yes there is concern not so much about notifying the listener but more about corrupting the tree links.  Priority tree operations are happening and we could be removing elements from the tree...I want to avoid keeping extra state and queueing these events if possible.  I'm not sure if this is entirely legitimate but I have been trying to justify it as "these nodes don't belong in the tree and are only their because of their dependents require them to be there.  If at any point they are no longer required through association they should immediately be removed.".

I went through a few scenarios (particularly when the new parent is a descendent of the current node) and didn't see any immediate issues with this approach...but would appreciate if you could come up with a case that would be problematic.

Ahh this makes sense now....this is the `remove` portion to your https://github.com/netty/netty/pull/3618#discussion_r28195572.  Yes, for the same rational as the other discussion.

no scenarios at the moment :) ... let's leave it as-is.  Maybe add a comment indicating the potential risk?

Yeah assert seems reasonable.

Yeah ok ... so add an assert here as well?

@nmittler - Logically this makes sense...but I'm getting unit test failures...trying to understand what is going on....

@nmittler - The `retain(..)` call when an exclusive dependency happens is messing things up.  We remove from the children collection in a special way such that we don't update the child's parent link until the next `takeChild` recursive call. This means that the `oldParent` won't have the child in its `children` collection...

Done. 

@nmittler - Turns out it is possible (and legit with the current code structure) for `oldParent.children.remove(child.id()) == null`.

> @nmittler - The `retain(..)` call when an exclusive dependency happens is messing things up.  We remove from the children collection in a special way such that we don't update the child's parent link until the next `takeChild` recursive call. This means that the `oldParent` won't have the child in its `children` collection...

@nmittler - Please review this comment.


Patch that resolved the issue:
diff --git a/codec-http2/src/main/java/io/netty/handler/codec/http2/DefaultHttp2Connection.java b/codec-http2/src/main/java/io/netty/handler/codec/http2/DefaultHttp2Connection.java
index 7c2fe828643..6ddf71ee78e 100644
--- a/codec-http2/src/main/java/io/netty/handler/codec/http2/DefaultHttp2Connection.java
+++ b/codec-http2/src/main/java/io/netty/handler/codec/http2/DefaultHttp2Connection.java
@@ -32,12 +32,12 @@
 import static io.netty.handler.codec.http2.Http2Stream.State.RESERVED_LOCAL;
 import static io.netty.handler.codec.http2.Http2Stream.State.RESERVED_REMOTE;
 import static io.netty.util.internal.ObjectUtil.checkNotNull;
-
 import io.netty.buffer.ByteBuf;
 import io.netty.util.collection.IntObjectHashMap;
 import io.netty.util.collection.IntObjectMap;
 import io.netty.util.collection.PrimitiveCollections;
 import io.netty.util.internal.PlatformDependent;
+import io.netty.util.internal.SystemPropertyUtil;
 import io.netty.util.internal.logging.InternalLogger;
 import io.netty.util.internal.logging.InternalLoggerFactory;
 
@@ -61,6 +61,15 @@ public class DefaultHttp2Connection implements Http2Connection {
     final ConnectionStream connectionStream = new ConnectionStream();
     final DefaultEndpoint<Http2LocalFlowController> localEndpoint;
     final DefaultEndpoint<Http2RemoteFlowController> remoteEndpoint;
+    /**
+     * The initial size of the children map is chosen to be conservative on initial memory allocations under
+     * the assumption that most streams will have a small number of children. This choice may be
+     * sub-optimal if when children are present there are many children (i.e. a web page which has many
+     * dependencies to load).
+     */
+    private static final int INITIAL_CHILDREN_MAP_SIZE =
+            Math.max(1, SystemPropertyUtil.getInt("io.netty.http2.childrenMapSize", 4));
+
     /**
      * We chose a {@link List} over a {@link Set} to avoid allocating an {@link Iterator} objects when iterating over
      * the listeners.
@@ -453,7 +462,7 @@ private void incrementPrioritizableForTree(int amt, Http2Stream oldParent) {
          * Instead use {@link #incrementPrioritizableForTree(int, Http2Stream)}.
          */
         private void incrementPrioritizableForTree0(int amt, Http2Stream oldParent) {
-            assert amt > 0;
+            assert amt > 0 && Integer.MAX_VALUE - amt >= prioritizableForTree;
             prioritizableForTree += amt;
             if (parent != null && parent != oldParent) {
                 parent.incrementPrioritizableForTree0(amt, oldParent);
@@ -475,7 +484,7 @@ private void decrementPrioritizableForTree(int amt) {
          * Direct calls to this method are discouraged. Instead use {@link #decrementPrioritizableForTree(int)}.
          */
         private void decrementPrioritizableForTree0(int amt) {
-            assert amt > 0;
+            assert amt > 0 && prioritizableForTree >= amt;
             prioritizableForTree -= amt;
             if (parent != null) {
                 parent.decrementPrioritizableForTree0(amt);
@@ -501,10 +510,14 @@ private void notifyHalfClosed(Http2Stream stream) {
 
         private void initChildrenIfEmpty() {
             if (children == PrimitiveCollections.<DefaultStream>emptyIntObjectMap()) {
-                children = new IntObjectHashMap<DefaultStream>(4);
+                initChildren();
             }
         }
 
+        private void initChildren() {
+            children = new IntObjectHashMap<DefaultStream>(INITIAL_CHILDREN_MAP_SIZE);
+        }
+
         @Override
         public final boolean remoteSideOpen() {
             return state == HALF_CLOSED_LOCAL || state == OPEN || state == RESERVED_REMOTE;
@@ -541,11 +554,26 @@ final void weight(short weight) {
             }
         }
 
-        final IntObjectMap<DefaultStream> removeAllChildren() {
-            totalChildWeights = 0;
-            prioritizableForTree = isPrioritizable() ? 1 : 0;
+        /**
+         * Remove all children with the exception of {@code streamToRetain}.
+         * This method is intended to be used to support an exclusive priority dependency operation.
+         * @return The map of children prior to this operation, excluding {@code streamToRetain} if present.
+         */
+        private IntObjectMap<DefaultStream> retain(DefaultStream streamToRetain) {
+            streamToRetain = children.remove(streamToRetain.id());
             IntObjectMap<DefaultStream> prevChildren = children;
-            children = PrimitiveCollections.emptyIntObjectMap();
+            // This map should be re-initialized in anticipation for the 1 exclusive child which will be added.
+            // It will either be added directly in this method, or after this method is called...but it will be added.
+            initChildren();
+            if (streamToRetain == null) {
+                totalChildWeights = 0;
+                prioritizableForTree = isPrioritizable() ? 1 : 0;
+            } else {
+                totalChildWeights = streamToRetain.weight();
+                // prioritizableForTree does not change because it is assumed all children node will still be
+                // descendants through an exclusive priority tree operation.
+                children.put(streamToRetain.id(), streamToRetain);
+            }
             return prevChildren;
         }
 
@@ -555,33 +583,44 @@ final IntObjectMap<DefaultStream> removeAllChildren() {
          */
         final void takeChild(DefaultStream child, boolean exclusive, List<ParentChangedEvent> events) {
             DefaultStream oldParent = child.parent();
-            events.add(new ParentChangedEvent(child, oldParent));
-            notifyParentChanging(child, this);
-            child.parent = this;
 
-            if (exclusive && !children.isEmpty()) {
-                // If it was requested that this child be the exclusive dependency of this node,
-                // move any previous children to the child node, becoming grand children of this node.
-                for (DefaultStream grandchild : removeAllChildren().values()) {
-                    child.takeChild(grandchild, false, events);
+            if (oldParent != this) {
+                events.add(new ParentChangedEvent(child, oldParent));
+                notifyParentChanging(child, this);
+                child.parent = this;
+                // We need the removal operation to happen first so the prioritizableForTree for the old parent to root
+                // path is updated with the correct child.prioritizableForTree() value. Note that the removal operation
+                // may not be successful and may return null. This is because when an exclusive dependency is processed
+                // the children are removed in a previous recursive call but the child's parent link is updated here.
+                if (oldParent != null && oldParent.children.remove(child.id()) != null) {
+                    oldParent.totalChildWeights -= child.weight();
+                    if (!child.isDescendantOf(oldParent)) {
+                        oldParent.decrementPrioritizableForTree(child.prioritizableForTree());
+                        if (oldParent.prioritizableForTree() == 0) {
+                            // There are a few risks with immediately removing nodes from the priority tree:
+                            // 1. We are removing nodes while we are potentially shifting the tree. There are no
+                            // concrete cases known but is risky because it could invalidate the data structure.
+                            // 2. We are notifying listeners of the removal while the tree is in flux. Currently the
+                            // codec listeners make no assumptions about priority tree structure when being notified.
+                            removeStream(oldParent);
+                        }
+                    }
                 }
-            }
 
-            // Lazily initialize the children to save object allocations.
-            initChildrenIfEmpty();
+                // Lazily initialize the children to save object allocations.
+                initChildrenIfEmpty();
 
-            if (children.put(child.id(), child) == null) {
+                final Http2Stream oldChild = children.put(child.id(), child);
+                assert oldChild == null : "A stream with the same stream ID was already in the child map.";
                 totalChildWeights += child.weight();
                 incrementPrioritizableForTree(child.prioritizableForTree(), oldParent);
             }
 
-            if (oldParent != null && oldParent.children.remove(child.id()) != null) {
-                oldParent.totalChildWeights -= child.weight();
-                if (!child.isDescendantOf(oldParent)) {
-                    oldParent.decrementPrioritizableForTree(child.prioritizableForTree());
-                    if (oldParent.prioritizableForTree() == 0) {
-                        removeStream(oldParent);
-                    }
+            if (exclusive && !children.isEmpty()) {
+                // If it was requested that this child be the exclusive dependency of this node,
+                // move any previous children to the child node, becoming grand children of this node.
+                for (DefaultStream grandchild : retain(child).values()) {
+                    child.takeChild(grandchild, false, events);
                 }
             }
         }
@@ -604,6 +643,11 @@ final boolean removeChild(DefaultStream child) {
                 }
 
                 if (prioritizableForTree() == 0) {
+                    // There are a few risks with immediately removing nodes from the priority tree:
+                    // 1. We are removing nodes while we are potentially shifting the tree. There are no
+                    // concrete cases known but is risky because it could invalidate the data structure.
+                    // 2. We are notifying listeners of the removal while the tree is in flux. Currently the
+                    // codec listeners make no assumptions about priority tree structure when being notified.
                     removeStream(this);
                 }
                 notifyParentChanged(events);


Test patch:
diff --git a/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2ConnectionTest.java b/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2ConnectionTest.java
index e145b8eb42c..2569d5d5c1c 100644
--- a/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2ConnectionTest.java
+++ b/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2ConnectionTest.java
@@ -362,6 +362,130 @@ public void insertExclusiveShouldAddNewLevel() throws Exception {
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
     }
 
+    @Test
+    public void existingChildMadeExclusiveShouldNotCreateTreeCycle() throws Http2Exception {
+        Http2Stream streamA = client.local().createStream(1).open(false);
+        Http2Stream streamB = client.local().createStream(3).open(false);
+        Http2Stream streamC = client.local().createStream(5).open(false);
+        Http2Stream streamD = client.local().createStream(7).open(false);
+
+        streamB.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamC.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamD.setPriority(streamC.id(), DEFAULT_PRIORITY_WEIGHT, false);
+
+        // Stream C is already dependent on Stream A, but now make that an exclusive dependency
+        streamC.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, true);
+
+        assertEquals(4, client.numActiveStreams());
+
+        // Level 0
+        Http2Stream p = client.connectionStream();
+        assertEquals(1, p.numChildren());
+        assertEquals(5, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 1
+        p = child(p, streamA.id());
+        assertNotNull(p);
+        assertEquals(0, p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(4, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 2
+        p = child(p, streamC.id());
+        assertNotNull(p);
+        assertEquals(streamA.id(), p.parent().id());
+        assertEquals(2, p.numChildren());
+        assertEquals(3, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 3
+        p = child(p, streamB.id());
+        assertNotNull(p);
+        assertEquals(streamC.id(), p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+        p = child(p.parent(), streamD.id());
+        assertNotNull(p);
+        assertEquals(streamC.id(), p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+    }
+
+    @Test
+    public void newExclusiveChildShouldUpdateOldParentCorrectly() throws Http2Exception {
+        Http2Stream streamA = client.local().createStream(1).open(false);
+        Http2Stream streamB = client.local().createStream(3).open(false);
+        Http2Stream streamC = client.local().createStream(5).open(false);
+        Http2Stream streamD = client.local().createStream(7).open(false);
+        Http2Stream streamE = client.local().createStream(9).open(false);
+        Http2Stream streamF = client.local().createStream(11).open(false);
+
+        streamB.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamC.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamD.setPriority(streamC.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamF.setPriority(streamE.id(), DEFAULT_PRIORITY_WEIGHT, false);
+
+        // F is now going to be exclusively dependent on A, after this we should check that stream E
+        // prioritizableForTree is not over decremented.
+        streamF.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, true);
+
+        assertEquals(6, client.numActiveStreams());
+
+        // Level 0
+        Http2Stream p = client.connectionStream();
+        assertEquals(2, p.numChildren());
+        assertEquals(7, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 1
+        p = child(p, streamE.id());
+        assertNotNull(p);
+        assertEquals(0, p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+        p = child(p.parent(), streamA.id());
+        assertNotNull(p);
+        assertEquals(0, p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(5, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 2
+        p = child(p, streamF.id());
+        assertNotNull(p);
+        assertEquals(streamA.id(), p.parent().id());
+        assertEquals(2, p.numChildren());
+        assertEquals(4, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 3
+        p = child(p, streamB.id());
+        assertNotNull(p);
+        assertEquals(streamF.id(), p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+        p = child(p.parent(), streamC.id());
+        assertNotNull(p);
+        assertEquals(streamF.id(), p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(2, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 4
+        p = child(p, streamD.id());
+        assertNotNull(p);
+        assertEquals(streamC.id(), p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+    }
+
     @Test
     public void weightChangeWithNoTreeChangeShouldNotifyListeners() throws Http2Exception {
         Http2Stream streamA = client.local().createStream(1).open(false);