Author: markt
Date: Thu Nov 24 14:39:52 2016
New Revision: 1771156
URL: http://svn.apache.org/viewvc?rev=1771156&view=rev
Log:
Fix https://bz.apache.org/bugzilla/show_bug.cgi?id=60386
Implement a more sophisticated pruning algorithm for removing closed streams
from the priority tree to ensure that the tree does not grow too large.
Modified:
tomcat/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java
tomcat/trunk/java/org/apache/coyote/http2/Stream.java
tomcat/trunk/webapps/docs/changelog.xml
Modified: tomcat/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java
URL:
http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java?rev=1771156&r1=1771155&r2=1771156&view=diff
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java
(original)
+++ tomcat/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java Thu Nov
24 14:39:52 2016
@@ -1007,38 +1007,88 @@ class Http2UpgradeHandler extends Abstra
}
// Need to try and close some streams.
- // Use this Set to keep track of streams that might be part of the
- // priority tree. Only remove these if we absolutely have to.
- TreeSet<Integer> additionalCandidates = new TreeSet<>();
+ // Try to close streams in this order
+ // 1. Completed streams used for a request with no children
+ // 2. Completed streams used for a request with children
+ // 3. Closed final streams
+ //
+ // Steps 1 and 2 will always be completed.
+ // Step 3 will be completed to the minimum extent necessary to bring
the
+ // total number of streams under the limit.
+
+ // Use these sets to track the different classes of streams
+ TreeSet<Integer> candidatesStepOne = new TreeSet<>();
+ TreeSet<Integer> candidatesStepTwo = new TreeSet<>();
+ TreeSet<Integer> candidatesStepThree = new TreeSet<>();
Iterator<Entry<Integer,Stream>> entryIter =
streams.entrySet().iterator();
- while (entryIter.hasNext() && toClose > 0) {
+ while (entryIter.hasNext()) {
Entry<Integer,Stream> entry = entryIter.next();
Stream stream = entry.getValue();
- // Never remove active streams or streams with children
- if (stream.isActive() || stream.getChildStreams().size() > 0) {
+ // Never remove active streams
+ if (stream.isActive()) {
continue;
}
+
if (stream.isClosedFinal()) {
// This stream went from IDLE to CLOSED and is likely to have
- // been created by the client as part of the priority tree.
Keep
- // it if possible.
- additionalCandidates.add(entry.getKey());
+ // been created by the client as part of the priority tree.
+ candidatesStepThree.add(entry.getKey());
+ } else if (stream.getChildStreams().size() == 0) {
+ // Closed, no children
+ candidatesStepOne.add(entry.getKey());
} else {
+ // Closed, with children
+ candidatesStepTwo.add(entry.getKey());
+ }
+ }
+
+ // Process the step one list
+ Iterator<Integer> stepOneIter = candidatesStepOne.iterator();
+ while (stepOneIter.hasNext()) {
+ Integer streamIdToRemove = stepOneIter.next();
+ // Remove this childless stream
+ Stream removedStream = streams.remove(streamIdToRemove);
+ removedStream.detachFromParent();
+ toClose--;
+ if (log.isDebugEnabled()) {
+ log.debug(sm.getString("upgradeHandler.pruned", connectionId,
streamIdToRemove));
+ }
+
+ // Did this make the parent childless?
+ AbstractStream parent = removedStream.getParentStream();
+ while (parent instanceof Stream && !((Stream) parent).isActive() &&
+ !((Stream) parent).isClosedFinal() &&
parent.getChildStreams().size() == 0) {
+ streams.remove(parent.getIdentifier());
+ parent.detachFromParent();
+ toClose--;
if (log.isDebugEnabled()) {
- log.debug(sm.getString("upgradeHandler.pruned",
connectionId, entry.getKey()));
+ log.debug(sm.getString("upgradeHandler.pruned",
connectionId, streamIdToRemove));
}
- entryIter.remove();
- toClose--;
+ // Also need to remove this stream from the p2 list
+ candidatesStepTwo.remove(parent.getIdentifier());
+ parent = parent.getParentStream();
}
}
- while (toClose > 0 && additionalCandidates.size() > 0) {
- Integer pruned = additionalCandidates.pollLast();
+ // Process the P2 list
+ Iterator<Integer> stepTwoIter = candidatesStepTwo.iterator();
+ while (stepTwoIter.hasNext()) {
+ Integer streamIdToRemove = stepTwoIter.next();
+ removeStreamFromPriorityTree(streamIdToRemove);
+ toClose--;
if (log.isDebugEnabled()) {
- log.debug(sm.getString("upgradeHandler.prunedPriority",
connectionId, pruned));
+ log.debug(sm.getString("upgradeHandler.pruned", connectionId,
streamIdToRemove));
+ }
+ }
+
+ while (toClose > 0 && candidatesStepThree.size() > 0) {
+ Integer streamIdToRemove = candidatesStepThree.pollLast();
+ removeStreamFromPriorityTree(streamIdToRemove);
+ toClose--;
+ if (log.isDebugEnabled()) {
+ log.debug(sm.getString("upgradeHandler.prunedPriority",
connectionId, streamIdToRemove));
}
- toClose++;
}
if (toClose > 0) {
@@ -1048,6 +1098,30 @@ class Http2UpgradeHandler extends Abstra
}
+ private void removeStreamFromPriorityTree(Integer streamIdToRemove) {
+ Stream streamToRemove = streams.remove(streamIdToRemove);
+ // Move the removed Stream's children to the removed Stream's
+ // parent.
+ Set<Stream> children = streamToRemove.getChildStreams();
+ if (streamToRemove.getChildStreams().size() == 1) {
+ // Shortcut
+ streamToRemove.getChildStreams().iterator().next().rePrioritise(
+ streamToRemove.getParentStream(),
streamToRemove.getWeight());
+ } else {
+ int totalWeight = 0;
+ for (Stream child : children) {
+ totalWeight += child.getWeight();
+ }
+ for (Stream child : children) {
+
streamToRemove.getChildStreams().iterator().next().rePrioritise(
+ streamToRemove.getParentStream(),
+ streamToRemove.getWeight() * child.getWeight() /
totalWeight);
+ }
+ }
+ streamToRemove.detachFromParent();
+ }
+
+
void push(Request request, Stream associatedStream) throws IOException {
Stream pushStream = createLocalStream(request);
Modified: tomcat/trunk/java/org/apache/coyote/http2/Stream.java
URL:
http://svn.apache.org/viewvc/tomcat/trunk/java/org/apache/coyote/http2/Stream.java?rev=1771156&r1=1771155&r2=1771156&view=diff
==============================================================================
--- tomcat/trunk/java/org/apache/coyote/http2/Stream.java (original)
+++ tomcat/trunk/java/org/apache/coyote/http2/Stream.java Thu Nov 24 14:39:52
2016
@@ -130,6 +130,22 @@ class Stream extends AbstractStream impl
}
+ /*
+ * Used when removing closed streams from the tree and we know there is no
+ * need to check for circular references.
+ */
+ final void rePrioritise(AbstractStream parent, int weight) {
+ if (log.isDebugEnabled()) {
+ log.debug(sm.getString("stream.reprioritisation.debug",
+ getConnectionId(), getIdentifier(), Boolean.FALSE,
+ parent.getIdentifier(), Integer.toString(weight)));
+ }
+
+ parent.addChild(this);
+ this.weight = weight;
+ }
+
+
final void receiveReset(long errorCode) {
if (log.isDebugEnabled()) {
log.debug(sm.getString("stream.reset.receive", getConnectionId(),
getIdentifier(),
Modified: tomcat/trunk/webapps/docs/changelog.xml
URL:
http://svn.apache.org/viewvc/tomcat/trunk/webapps/docs/changelog.xml?rev=1771156&r1=1771155&r2=1771156&view=diff
==============================================================================
--- tomcat/trunk/webapps/docs/changelog.xml (original)
+++ tomcat/trunk/webapps/docs/changelog.xml Thu Nov 24 14:39:52 2016
@@ -107,6 +107,11 @@
Ensure that the availability of configured upgrade protocols that
require ALPN is correctly reported during Tomcat start. (markt)
</fix>
+ <fix>
+ <bug>60386</bug>: Implement a more sophisticated pruning algorithm for
+ removing closed streams from the priority tree to ensure that the tree
+ does not grow too large. (markt)
+ </fix>
</changelog>
</subsection>
<subsection name="Web applications">
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@tomcat.apache.org
For additional commands, e-mail: dev-h...@tomcat.apache.org
