Repository: netty/netty
Issue: HTTP/2 Priority Tree Management
Labels: defect

We are currently removing streams from the priority tree as they are closed (maybe subject to a stream removal policy which is being removed as part of https://github.com/netty/netty/issues/3448).  However we should not remove streams from the priority tree at least until they have no dependencies which are in states eligible for data transfer (i.e. OPEN, HALF_CLOSED, ...), or may be eligible for data transfer in the future (i.e. IDLE).


Issue comments:
@nmittler - FYI.

We associate priority with the flow control window.  Therefore we rely on both peers sharing a common view of the priority tree.  However there seems to be some confusion (on my part or in the spec) with how to provide feedback when we don't accept a priority frame.  We can't rely upon sending a RST_STREAM to the other end because in [section 5.1](https://tools.ietf.org/html/draft-ietf-httpbis-http2-17#section-5.1):

> Endpoints MUST ignore
>       WINDOW_UPDATE or RST_STREAM frames received in this state, though
>       endpoints MAY choose to treat frames that arrive a significant
>       time after sending END_STREAM as a connection error
>       (Section 5.4.1) of type PROTOCOL_ERROR.

Some thought is needed (perhaps when I'm not so tired) as to how we can maintain the priority & flow control association and keep the peers in sync.

For example say stream X is closed, and it has no children.
1. We remove it from the priority tree.
2. Later our peer sends a priority frame for stream X.
What do we do:
- Should we have been keeping track of stream X's window? (it can't be controlled via WINDOW_UPDATE frames at this point)
- Should we ignore it? - What does that say about our windows throughout the tree?

I'm working on a PR for this.  I think I was confused in my late night thought process :)  The window of the individual node doesn't particularly matter because we are considering how much the whole subtree _wants_ to send, and any individual node which is not eligible to send will not contribute to this number.  So ignore my previous comment.

ignored :)

@nmittler - Humm this didn't get auto closed like we had hoped...closing manually.

@Scottmitch hmm ... maybe updates don't count and the original description has to have the "Fixes: " text?

@nmittler I wonder if a link has to be in the git commit too?

@Scottmitch ah yeah that would make sense.


Pull request review comments:
missing `.` on EOL

missing `.` on EOL

Done.

Done.

Boy, "writable" sure would be a good name .... (Nate giggles while sipping his tea) :)

maybe call this `isViableBranch()` which first checks `isViable()`?

Do we need 2 methods? Could `isViable` be recursive?

Hmm ... I don't like `viable` :/

I don't see it in the spec anywhere, so I suppose we're free to name this whatever we like.  What about just using `isNonClosed` and `isBranchNonClosed` instead?  Alternatively maybe something like `prioritizable`?

> Hmm ... I don't like viable :/

+1.  My goal in life is to introduce a "clear" concept and then let the word smiths figure out the rest :)

Seems like a viable strategy :)

Lets handle the `Do we need 2 methods? Could isViable be recursive?` comment here too.

We may be able to do this but I'm of the mindset that it is makes sense to have them separated.  For example there are places (takeChild, removeChild) where we don't want to recursively check the subtree and only want to check the immediate node. WDYT?

When I choose this nebulous name I didn't use `closed` because I wasn't sure if other states would need to be included here.  I like `isPrioritizable()` because we are really trying to define a concept that says "if this node by itself belongs in the priority tree".  We also need something that says "do any of this node's descendants belong in the priority tree"...`hasPrioritizableDescendant()`?

Yeah that's fine ... just a thought.

sgtm

Hah..."writable" in the flow controller context....maybe we can add a chapter in @normanmaurer's book explaining what we mean :)

@nmittler - Please verify.  We were created a circular dependency in the priority tree without this check.  I found it in one of the new unit tests with a StackOverFlow excpetion.

@Scottmitch should this check be `!newParent.isExclusiveChild(this)`, where `isExclusiveChild` would return `true` if `numChildren == 1` and the child is the one provided?

@nmittler - I like it from a clarity point of view.  However I think it will be the same result in this case and it sounds like we would have to re-check some of the stuff we already know in this block (either parents are equal, or check the parent's child list, and size == 1).  If we were to add this new method do you have a preference for adding to `Http2Stream` or just private to `DefaultStream`?  The question is will this method have utility beyond this block.

Could we just make this the one and only initialization of `events` (and get rid of the `else`) to simplify the code?

@Scottmitch Oh I see ... by the time we're checking exclusive we know that the parent isn't changing, we're handling the exclusive case.  Yeah this change looks right to me.

We could but we already have to do the if check...and the if check also tells us what the size of the collection needs to be.

The arrays only differ in size by 1 ... just seemed like overkill to branch on creating the list.  But I'm fine leaving it as-is if you have a strong preference here.

Not a strong preference but I do think it clarifies expectations and we already have to evaluate the branch condition.

I have no statistics to back it up but I have a gut feeling the `else` condition will be true most of the time...so most of the time we won't need the extra space in the array.

@nmittler - Note that I change the notification for `onStreamRemoved` to be after it is removed from the priority tree and stream map.  I think this lines up with how the other listeners are used (notify after event takes place) and also the comments on the `onStreamRemoved` method.

@Scottmitch Yeah that makes sense.  Thanks for pointing it out!


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 cd507c953da..a10bc3f0cd1 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
@@ -81,7 +81,6 @@ public DefaultHttp2Connection(boolean server) {
      *            the policy to be used for removal of closed stream.
      */
     public DefaultHttp2Connection(boolean server, Http2StreamRemovalPolicy removalPolicy) {
-
         this.removalPolicy = checkNotNull(removalPolicy, "removalPolicy");
         localEndpoint = new DefaultEndpoint<Http2LocalFlowController>(server);
         remoteEndpoint = new DefaultEndpoint<Http2RemoteFlowController>(!server);
@@ -184,15 +183,25 @@ public void goAwaySent(int lastKnownStream, long errorCode, ByteBuf debugData) {
         }
     }
 
-    private void removeStream(DefaultStream stream) {
-        // Notify the listeners of the event first.
-        for (Listener listener : listeners) {
-            listener.onStreamRemoved(stream);
-        }
+    /**
+     * Closed streams may stay in the priority tree if they have dependents that are in prioritizable states.
+     * When a stream is requested to be removed we can only actually remove that stream when there are no more
+     * prioritizable children.
+     * (see [1] {@link Http2Stream#prioritizableForTree()} and [2] {@link DefaultStream#removeChild(DefaultStream)}).
+     * When a priority tree edge changes we also have to re-evaluate viable nodes
+     * (see [3] {@link DefaultStream#takeChild(DefaultStream, boolean, List)}).
+     * @param stream The stream to remove.
+     */
+    void removeStream(DefaultStream stream) {
+        // [1] Check if this stream can be removed because it has no prioritizable descendants.
+        if (stream.parent().removeChild(stream)) {
+            // Remove it from the map and priority tree.
+            streamMap.remove(stream.id());
 
-        // Remove it from the map and priority tree.
-        streamMap.remove(stream.id());
-        stream.parent().removeChild(stream);
+            for (Listener listener : listeners) {
+                listener.onStreamRemoved(stream);
+            }
+        }
     }
 
     /**
@@ -205,6 +214,7 @@ private class DefaultStream implements Http2Stream {
         private DefaultStream parent;
         private IntObjectMap<DefaultStream> children = newChildMap();
         private int totalChildWeights;
+        private int prioritizableForTree = 1;
         private boolean resetSent;
         private PropertyMap data;
 
@@ -235,17 +245,17 @@ public Http2Stream resetSent() {
         }
 
         @Override
-        public Object setProperty(Object key, Object value) {
+        public final Object setProperty(Object key, Object value) {
             return data.put(key, value);
         }
 
         @Override
-        public <V> V getProperty(Object key) {
+        public final <V> V getProperty(Object key) {
             return data.get(key);
         }
 
         @Override
-        public <V> V removeProperty(Object key) {
+        public final <V> V removeProperty(Object key) {
             return data.remove(key);
         }
 
@@ -269,6 +279,11 @@ public final DefaultStream parent() {
             return parent;
         }
 
+        @Override
+        public final int prioritizableForTree() {
+            return prioritizableForTree;
+        }
+
         @Override
         public final boolean isDescendantOf(Http2Stream stream) {
             Http2Stream next = parent();
@@ -325,10 +340,10 @@ public Http2Stream setPriority(int parentStreamId, short weight, boolean exclusi
             // Already have a priority. Re-prioritize the stream.
             weight(weight);
 
-            if (newParent != parent() || exclusive) {
-                List<ParentChangedEvent> events;
+            if (newParent != parent() || (exclusive && newParent.numChildren() != 1)) {
+                final List<ParentChangedEvent> events;
                 if (newParent.isDescendantOf(this)) {
-                    events = new ArrayList<ParentChangedEvent>(2 + (exclusive ? newParent.numChildren(): 0));
+                    events = new ArrayList<ParentChangedEvent>(2 + (exclusive ? newParent.numChildren() : 0));
                     parent.takeChild(newParent, false, events);
                 } else {
                     events = new ArrayList<ParentChangedEvent>(1 + (exclusive ? newParent.numChildren() : 0));
@@ -375,6 +390,7 @@ public Http2Stream close() {
             }
 
             state = CLOSED;
+            decrementPrioritizableForTree(1);
             if (activeStreams.remove(this)) {
                 try {
                     // Update the number of active streams initiated by the endpoint.
@@ -424,6 +440,59 @@ public Http2Stream closeRemoteSide() {
             return this;
         }
 
+        /**
+         * Recursively increment the {@link #prioritizableForTree} for this object up the parent links until
+         * either we go past the root or {@code oldParent} is encountered.
+         * @param amt The amount to increment by. This must be positive.
+         * @param oldParent The previous parent for this stream.
+         */
+        private void incrementPrioritizableForTree(int amt, Http2Stream oldParent) {
+            if (amt != 0) {
+                incrementPrioritizableForTree0(amt, oldParent);
+            }
+        }
+
+        /**
+         * Direct calls to this method are discouraged.
+         * Instead use {@link #incrementPrioritizableForTree(int, Http2Stream)}.
+         */
+        private void incrementPrioritizableForTree0(int amt, Http2Stream oldParent) {
+            assert amt > 0;
+            prioritizableForTree += amt;
+            if (parent != null && parent != oldParent) {
+                parent.incrementPrioritizableForTree(amt, oldParent);
+            }
+        }
+
+        /**
+         * Recursively increment the {@link #prioritizableForTree} for this object up the parent links until
+         * either we go past the root.
+         * @param amt The amount to decrement by. This must be positive.
+         */
+        private void decrementPrioritizableForTree(int amt) {
+            if (amt != 0) {
+                decrementPrioritizableForTree0(amt);
+            }
+        }
+
+        /**
+         * Direct calls to this method are discouraged. Instead use {@link #decrementPrioritizableForTree(int)}.
+         */
+        private void decrementPrioritizableForTree0(int amt) {
+            assert amt > 0;
+            prioritizableForTree -= amt;
+            if (parent != null) {
+                parent.decrementPrioritizableForTree(amt);
+            }
+        }
+
+        /**
+         * Determine if this node by itself is considered to be valid in the priority tree.
+         */
+        private boolean isPrioritizable() {
+            return state != CLOSED;
+        }
+
         private void notifyHalfClosed(Http2Stream stream) {
             for (Listener listener : listeners) {
                 listener.onStreamHalfClosed(stream);
@@ -464,6 +533,7 @@ final void weight(short weight) {
 
         final IntObjectMap<DefaultStream> removeAllChildren() {
             totalChildWeights = 0;
+            prioritizableForTree = isPrioritizable() ? 1 : 0;
             IntObjectMap<DefaultStream> prevChildren = children;
             children = newChildMap();
             return prevChildren;
@@ -481,8 +551,7 @@ final void takeChild(DefaultStream child, boolean exclusive, List<ParentChangedE
 
             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.
+                // move any previous children to the child node, becoming grand children of this node.
                 for (DefaultStream grandchild : removeAllChildren().values()) {
                     child.takeChild(grandchild, false, events);
                 }
@@ -490,31 +559,44 @@ final void takeChild(DefaultStream child, boolean exclusive, List<ParentChangedE
 
             if (children.put(child.id(), child) == null) {
                 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);
+                    }
+                }
             }
         }
 
         /**
          * Removes the child priority and moves any of its dependencies to being direct dependencies on this node.
          */
-        final void removeChild(DefaultStream child) {
-            if (children.remove(child.id()) != null) {
-                List<ParentChangedEvent> events = new ArrayList<ParentChangedEvent>(1 + child.children.size());
+        final boolean removeChild(DefaultStream child) {
+            if (child.prioritizableForTree() == 0 && children.remove(child.id()) != null) {
+                List<ParentChangedEvent> events = new ArrayList<ParentChangedEvent>(1 + child.numChildren());
                 events.add(new ParentChangedEvent(child, child.parent()));
                 notifyParentChanging(child, null);
                 child.parent = null;
                 totalChildWeights -= child.weight();
+                decrementPrioritizableForTree(child.prioritizableForTree());
 
                 // Move up any grand children to be directly dependent on this node.
                 for (DefaultStream grandchild : child.children.values()) {
                     takeChild(grandchild, false, events);
                 }
 
+                if (prioritizableForTree() == 0) {
+                    removeStream(this);
+                }
                 notifyParentChanged(events);
+                return true;
             }
+            return false;
         }
     }
 
@@ -644,6 +726,16 @@ private final class ConnectionStream extends DefaultStream {
             super(CONNECTION_STREAM_ID);
         }
 
+        @Override
+        public boolean isResetSent() {
+            return false;
+        }
+
+        @Override
+        public Http2Stream resetSent() {
+            throw new UnsupportedOperationException();
+        }
+
         @Override
         public Http2Stream setPriority(int parentStreamId, short weight, boolean exclusive) {
             throw new UnsupportedOperationException();
diff --git a/codec-http2/src/main/java/io/netty/handler/codec/http2/Http2Stream.java b/codec-http2/src/main/java/io/netty/handler/codec/http2/Http2Stream.java
index 676213d341c..0e741a5aaae 100644
--- a/codec-http2/src/main/java/io/netty/handler/codec/http2/Http2Stream.java
+++ b/codec-http2/src/main/java/io/netty/handler/codec/http2/Http2Stream.java
@@ -157,6 +157,13 @@ enum State {
      */
     Http2Stream parent();
 
+    /**
+     * Get the number of streams in the priority tree rooted at this node that are OK to exist in the priority
+     * tree on their own right. Some streams may be in the priority tree because their dependents require them to
+     * remain.
+     */
+    int prioritizableForTree();
+
     /**
      * Indicates whether or not this stream is a descendant in the priority tree from the given stream.
      */


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 6fe7c5a28f9..197be34baef 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
@@ -15,13 +15,13 @@
 
 package io.netty.handler.codec.http2;
 
-import static io.netty.handler.codec.http2.Http2CodecUtil.MIN_WEIGHT;
 import static io.netty.handler.codec.http2.Http2CodecUtil.DEFAULT_PRIORITY_WEIGHT;
+import static io.netty.handler.codec.http2.Http2CodecUtil.MIN_WEIGHT;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
-import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
 import static org.mockito.Matchers.any;
 import static org.mockito.Matchers.anyShort;
 import static org.mockito.Matchers.eq;
@@ -242,6 +242,7 @@ public void remoteStreamCanDependUponIdleStream() throws Http2Exception {
     public void prioritizeShouldUseDefaults() throws Exception {
         Http2Stream stream = client.local().createStream(1).open(false);
         assertEquals(1, client.connectionStream().numChildren());
+        assertEquals(2, client.connectionStream().prioritizableForTree());
         assertEquals(stream, client.connectionStream().child(1));
         assertEquals(DEFAULT_PRIORITY_WEIGHT, stream.weight());
         assertEquals(0, stream.parent().id());
@@ -253,6 +254,7 @@ public void reprioritizeWithNoChangeShouldDoNothing() throws Exception {
         Http2Stream stream = client.local().createStream(1).open(false);
         stream.setPriority(0, DEFAULT_PRIORITY_WEIGHT, false);
         assertEquals(1, client.connectionStream().numChildren());
+        assertEquals(2, client.connectionStream().prioritizableForTree());
         assertEquals(stream, client.connectionStream().child(1));
         assertEquals(DEFAULT_PRIORITY_WEIGHT, stream.weight());
         assertEquals(0, stream.parent().id());
@@ -275,6 +277,7 @@ public void insertExclusiveShouldAddNewLevel() throws Exception {
         // Level 0
         Http2Stream p = client.connectionStream();
         assertEquals(1, p.numChildren());
+        assertEquals(5, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 1
@@ -282,6 +285,7 @@ public void insertExclusiveShouldAddNewLevel() throws Exception {
         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
@@ -289,6 +293,7 @@ public void insertExclusiveShouldAddNewLevel() throws Exception {
         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
@@ -296,11 +301,13 @@ public void insertExclusiveShouldAddNewLevel() throws Exception {
         assertNotNull(p);
         assertEquals(streamD.id(), p.parent().id());
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
         p = p.parent().child(streamC.id());
         assertNotNull(p);
         assertEquals(streamD.id(), p.parent().id());
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
     }
 
@@ -327,10 +334,108 @@ public void weightChangeWithNoTreeChangeShouldNotifyListeners() throws Http2Exce
                 any(Http2Stream.class));
         verify(clientListener, never()).onPriorityTreeParentChanged(any(Http2Stream.class),
                 any(Http2Stream.class));
+        assertEquals(5, client.connectionStream().prioritizableForTree());
+        assertEquals(4, streamA.prioritizableForTree());
+        assertEquals(1, streamB.prioritizableForTree());
+        assertEquals(1, streamC.prioritizableForTree());
+        assertEquals(3, streamD.prioritizableForTree());
+    }
+
+    @Test
+    public void sameNodeDependentShouldNotStackOverflowNorChangePrioritizableForTree() 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(streamA.id(), DEFAULT_PRIORITY_WEIGHT, true);
+
+        boolean[] exclusive = new boolean[] {true, false};
+        short[] weights = new short[] { DEFAULT_PRIORITY_WEIGHT, 100, 200, streamD.weight() };
+
+        assertEquals(4, client.numActiveStreams());
+
+        Http2Stream connectionStream = client.connectionStream();
+        assertEquals(5, connectionStream.prioritizableForTree());
+        assertEquals(4, streamA.prioritizableForTree());
+        assertEquals(1, streamB.prioritizableForTree());
+        assertEquals(1, streamC.prioritizableForTree());
+        assertEquals(3, streamD.prioritizableForTree());
+
+        // The goal is to call setPriority with the same parent and vary the parameters
+        // we were at one point adding a circular depends to the tree and then throwing
+        // a StackOverflow due to infinite recursive operation.
+        for (int j = 0; j < weights.length; ++j) {
+            for (int i = 0; i < exclusive.length; ++i) {
+                streamD.setPriority(streamA.id(), weights[j], exclusive[i]);
+                assertEquals(5, connectionStream.prioritizableForTree());
+                assertEquals(4, streamA.prioritizableForTree());
+                assertEquals(1, streamB.prioritizableForTree());
+                assertEquals(1, streamC.prioritizableForTree());
+                assertEquals(3, streamD.prioritizableForTree());
+            }
+        }
     }
 
     @Test
-    public void removeShouldRestructureTree() throws Exception {
+    public void multipleCircularDependencyShouldUpdatePrioritizable() 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(streamA.id(), DEFAULT_PRIORITY_WEIGHT, true);
+
+        assertEquals(4, client.numActiveStreams());
+
+        Http2Stream connectionStream = client.connectionStream();
+        assertEquals(5, connectionStream.prioritizableForTree());
+        assertEquals(4, streamA.prioritizableForTree());
+        assertEquals(1, streamB.prioritizableForTree());
+        assertEquals(1, streamC.prioritizableForTree());
+        assertEquals(3, streamD.prioritizableForTree());
+
+        // Bring B to the root
+        streamA.setPriority(streamB.id(), DEFAULT_PRIORITY_WEIGHT, true);
+        assertEquals(5, connectionStream.prioritizableForTree());
+        assertEquals(3, streamA.prioritizableForTree());
+        assertEquals(4, streamB.prioritizableForTree());
+        assertEquals(1, streamC.prioritizableForTree());
+        assertEquals(2, streamD.prioritizableForTree());
+
+        // Move all streams to be children of B
+        streamC.setPriority(streamB.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamD.setPriority(streamB.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        assertEquals(5, connectionStream.prioritizableForTree());
+        assertEquals(1, streamA.prioritizableForTree());
+        assertEquals(4, streamB.prioritizableForTree());
+        assertEquals(1, streamC.prioritizableForTree());
+        assertEquals(1, streamD.prioritizableForTree());
+
+        // Move A back to the root
+        streamB.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, true);
+        assertEquals(5, connectionStream.prioritizableForTree());
+        assertEquals(4, streamA.prioritizableForTree());
+        assertEquals(3, streamB.prioritizableForTree());
+        assertEquals(1, streamC.prioritizableForTree());
+        assertEquals(1, streamD.prioritizableForTree());
+
+        // Move all streams to be children of A
+        streamC.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamD.setPriority(streamA.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        assertEquals(5, connectionStream.prioritizableForTree());
+        assertEquals(4, streamA.prioritizableForTree());
+        assertEquals(1, streamB.prioritizableForTree());
+        assertEquals(1, streamC.prioritizableForTree());
+        assertEquals(1, streamD.prioritizableForTree());
+    }
+
+    @Test
+    public void removeWithPrioritizableDependentsShouldNotRestructureTree() throws Exception {
         Http2Stream streamA = client.local().createStream(1).open(false);
         Http2Stream streamB = client.local().createStream(3).open(false);
         Http2Stream streamC = client.local().createStream(5).open(false);
@@ -345,27 +450,166 @@ public void removeShouldRestructureTree() throws Exception {
 
         // Level 0
         Http2Stream p = client.connectionStream();
+        assertEquals(4, p.prioritizableForTree());
         assertEquals(1, p.numChildren());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 1
         p = p.child(streamA.id());
         assertNotNull(p);
+        assertEquals(3, p.prioritizableForTree());
         assertEquals(0, p.parent().id());
-        assertEquals(2, p.numChildren());
+        assertEquals(1, p.numChildren());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 2
-        p = p.child(streamC.id());
+        p = p.child(streamB.id());
         assertNotNull(p);
+        assertEquals(2, p.prioritizableForTree());
         assertEquals(streamA.id(), p.parent().id());
+        assertEquals(2, p.numChildren());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 3
+        p = p.child(streamC.id());
+        assertNotNull(p);
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(streamB.id(), p.parent().id());
         assertEquals(0, p.numChildren());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
         p = p.parent().child(streamD.id());
         assertNotNull(p);
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(streamB.id(), p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+    }
+
+    @Test
+    public void closeWithNoPrioritizableDependentsShouldRestructureTree() throws Exception {
+        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(streamB.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamD.setPriority(streamB.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamE.setPriority(streamC.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamF.setPriority(streamD.id(), DEFAULT_PRIORITY_WEIGHT, false);
+
+        // Close internal nodes, leave 1 leaf node open, and ensure part of the tree (D & F) is cleaned up
+        streamA.close();
+        streamB.close();
+        streamC.close();
+        streamD.close();
+        streamF.close();
+
+        // Level 0
+        Http2Stream p = client.connectionStream();
+        assertEquals(1, p.numChildren());
+        assertEquals(2, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 1
+        p = p.child(streamA.id());
+        assertNotNull(p);
+        assertEquals(0, p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 2
+        p = p.child(streamB.id());
+        assertNotNull(p);
         assertEquals(streamA.id(), p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 3
+        p = p.child(streamC.id());
+        assertNotNull(p);
+        assertEquals(streamB.id(), p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 4
+        p = p.child(streamE.id());
+        assertNotNull(p);
+        assertEquals(streamC.id(), p.parent().id());
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+    }
+
+    @Test
+    public void priorityChangeWithNoPrioritizableDependentsShouldRestructureTree() throws Exception {
+        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(streamB.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamD.setPriority(streamB.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamE.setPriority(streamC.id(), DEFAULT_PRIORITY_WEIGHT, false);
+        streamF.setPriority(streamD.id(), DEFAULT_PRIORITY_WEIGHT, false);
+
+        // Leave leaf nodes open (E & F)
+        streamA.close();
+        streamB.close();
+        streamC.close();
+        streamD.close();
+
+        // Move F to depend on C, this should close D
+        streamF.setPriority(streamC.id(), DEFAULT_PRIORITY_WEIGHT, false);
+
+        // Level 0
+        Http2Stream p = client.connectionStream();
+        assertEquals(1, p.numChildren());
+        assertEquals(3, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 1
+        p = p.child(streamA.id());
+        assertNotNull(p);
+        assertEquals(0, p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(2, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 2
+        p = p.child(streamB.id());
+        assertNotNull(p);
+        assertEquals(streamA.id(), p.parent().id());
+        assertEquals(1, p.numChildren());
+        assertEquals(2, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 3
+        p = p.child(streamC.id());
+        assertNotNull(p);
+        assertEquals(streamB.id(), p.parent().id());
+        assertEquals(2, p.numChildren());
+        assertEquals(2, p.prioritizableForTree());
+        assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
+
+        // Level 4
+        p = p.child(streamE.id());
+        assertNotNull(p);
+        assertEquals(streamC.id(), p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
+        p = p.parent().child(streamF.id());
+        assertNotNull(p);
+        assertEquals(streamC.id(), p.parent().id());
+        assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
     }
 
     @Test
@@ -423,18 +667,21 @@ public void circularDependencyShouldRestructureTree() throws Exception {
         // Level 0
         Http2Stream p = client.connectionStream();
         assertEquals(1, p.numChildren());
+        assertEquals(7, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 1
         p = p.child(streamD.id());
         assertNotNull(p);
         assertEquals(2, p.numChildren());
+        assertEquals(6, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 2
         p = p.child(streamF.id());
         assertNotNull(p);
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
         p = p.parent().child(streamA.id());
         assertNotNull(p);
@@ -445,16 +692,19 @@ public void circularDependencyShouldRestructureTree() throws Exception {
         p = p.child(streamB.id());
         assertNotNull(p);
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
         p = p.parent().child(streamC.id());
         assertNotNull(p);
         assertEquals(1, p.numChildren());
+        assertEquals(2, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 4;
         p = p.child(streamE.id());
         assertNotNull(p);
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
     }
 
@@ -515,38 +765,45 @@ public void circularDependencyWithExclusiveShouldRestructureTree() throws Except
         // Level 0
         Http2Stream p = client.connectionStream();
         assertEquals(1, p.numChildren());
+        assertEquals(7, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 1
         p = p.child(streamD.id());
         assertNotNull(p);
         assertEquals(1, p.numChildren());
+        assertEquals(6, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 2
         p = p.child(streamA.id());
         assertNotNull(p);
         assertEquals(3, p.numChildren());
+        assertEquals(5, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 3
         p = p.child(streamB.id());
         assertNotNull(p);
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
         p = p.parent().child(streamF.id());
         assertNotNull(p);
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
         p = p.parent().child(streamC.id());
         assertNotNull(p);
         assertEquals(1, p.numChildren());
+        assertEquals(2, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
 
         // Level 4;
         p = p.child(streamE.id());
         assertNotNull(p);
         assertEquals(0, p.numChildren());
+        assertEquals(1, p.prioritizableForTree());
         assertEquals(p.numChildren() * DEFAULT_PRIORITY_WEIGHT, p.totalChildWeights());
     }
 
diff --git a/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2RemoteFlowControllerTest.java b/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2RemoteFlowControllerTest.java
index eeae7ca716b..064520f97e7 100644
--- a/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2RemoteFlowControllerTest.java
+++ b/codec-http2/src/test/java/io/netty/handler/codec/http2/DefaultHttp2RemoteFlowControllerTest.java
@@ -932,7 +932,7 @@ public void subTreeBytesShouldBeCorrectWithAddition() throws Http2Exception {
     }
 
     /**
-     * In this test, we block all streams and remove a node from the priority tree and verify
+     * In this test, we block all streams and close an internal stream in the priority tree but tree should not change
      *
      * <pre>
      *        [0]
@@ -941,17 +941,76 @@ public void subTreeBytesShouldBeCorrectWithAddition() throws Http2Exception {
      *      / \
      *     C   D
      * </pre>
+     */
+    @Test
+    public void subTreeBytesShouldBeCorrectWithInternalStreamClose() throws Http2Exception {
+        // Block the connection
+        exhaustStreamWindow(CONNECTION_STREAM_ID);
+
+        Http2Stream stream0 = connection.connectionStream();
+        Http2Stream streamA = connection.stream(STREAM_A);
+        Http2Stream streamB = connection.stream(STREAM_B);
+        Http2Stream streamC = connection.stream(STREAM_C);
+        Http2Stream streamD = connection.stream(STREAM_D);
+
+        // Send a bunch of data on each stream.
+        final IntObjectMap<Integer> streamSizes = new IntObjectHashMap<Integer>(4);
+        streamSizes.put(STREAM_A, 400);
+        streamSizes.put(STREAM_B, 500);
+        streamSizes.put(STREAM_C, 600);
+        streamSizes.put(STREAM_D, 700);
+
+        FakeFlowControlled dataA = new FakeFlowControlled(streamSizes.get(STREAM_A));
+        FakeFlowControlled dataB = new FakeFlowControlled(streamSizes.get(STREAM_B));
+        FakeFlowControlled dataC = new FakeFlowControlled(streamSizes.get(STREAM_C));
+        FakeFlowControlled dataD = new FakeFlowControlled(streamSizes.get(STREAM_D));
+
+        sendData(STREAM_A, dataA);
+        sendData(STREAM_B, dataB);
+        sendData(STREAM_C, dataC);
+        sendData(STREAM_D, dataD);
+
+        dataA.assertNotWritten();
+        dataB.assertNotWritten();
+        dataC.assertNotWritten();
+        dataD.assertNotWritten();
+
+        streamA.close();
+
+        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_B, STREAM_C, STREAM_D)),
+                streamableBytesForTree(stream0));
+        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_C, STREAM_D)),
+                streamableBytesForTree(streamA));
+        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_B)),
+                streamableBytesForTree(streamB));
+        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_C)),
+                streamableBytesForTree(streamC));
+        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_D)),
+                streamableBytesForTree(streamD));
+    }
+
+    /**
+     * In this test, we block all streams and close a leaf stream in the priority tree and verify
      *
-     * After the tree shift:
+     * <pre>
+     *        [0]
+     *        / \
+     *       A   B
+     *      / \
+     *     C   D
+     * </pre>
      *
+     * After the close:
      * <pre>
      *        [0]
-     *       / | \
-     *      C  D  B
+     *        / \
+     *       A   B
+     *       |
+     *       D
      * </pre>
      */
     @Test
-    public void subTreeBytesShouldBeCorrectWithRemoval() throws Http2Exception {
+    public void subTreeBytesShouldBeCorrectWithLeafStreamClose() throws Http2Exception {
         // Block the connection
         exhaustStreamWindow(CONNECTION_STREAM_ID);
 
@@ -983,15 +1042,15 @@ public void subTreeBytesShouldBeCorrectWithRemoval() throws Http2Exception {
         dataC.assertNotWritten();
         dataD.assertNotWritten();
 
-        streamA.close();
+        streamC.close();
 
-        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_B, STREAM_C, STREAM_D)),
+        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_A, STREAM_B, STREAM_D)),
                 streamableBytesForTree(stream0));
-        assertEquals(0, streamableBytesForTree(streamA));
+        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_A, STREAM_D)),
+                streamableBytesForTree(streamA));
         assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_B)),
                 streamableBytesForTree(streamB));
-        assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_C)),
-                streamableBytesForTree(streamC));
+        assertEquals(0, streamableBytesForTree(streamC));
         assertEquals(calculateStreamSizeSum(streamSizes, Arrays.asList(STREAM_D)),
                 streamableBytesForTree(streamD));
     }