You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@tomcat.apache.org by ma...@apache.org on 2016/11/24 14:41:41 UTC
svn commit: r1771158 - in /tomcat/tc8.5.x/trunk: ./
java/org/apache/coyote/http2/Http2UpgradeHandler.java
java/org/apache/coyote/http2/Stream.java webapps/docs/changelog.xml
Author: markt
Date: Thu Nov 24 14:41:41 2016
New Revision: 1771158
URL: http://svn.apache.org/viewvc?rev=1771158&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/tc8.5.x/trunk/ (props changed)
tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java
tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Stream.java
tomcat/tc8.5.x/trunk/webapps/docs/changelog.xml
Propchange: tomcat/tc8.5.x/trunk/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Thu Nov 24 14:41:41 2016
@@ -1 +1 @@
-/tomcat/trunk:1734785,1734799,1734845,1734928,1735041,1735044,1735480,1735577,1735597,1735599-1735600,1735615,1736145,1736162,1736209,1736280,1736297,1736299,1736489,1736646,1736703,1736836,1736849,1737104-1737105,1737112,1737117,1737119-1737120,1737155,1737157,1737192,1737280,1737339,1737632,1737664,1737715,1737748,1737785,1737834,1737860,1737903,1737959,1738005,1738007,1738014-1738015,1738018,1738022,1738039,1738043,1738059-1738060,1738147,1738149,1738174-1738175,1738261,1738589,1738623-1738625,1738643,1738816,1738850,1738855,1738946-1738948,1738953-1738954,1738979,1738982,1739079-1739081,1739087,1739113,1739153,1739172,1739176,1739191,1739474,1739726,1739762,1739775,1739814,1739817-1739818,1739975,1740131,1740324,1740465,1740495,1740508-1740509,1740520,1740535,1740707,1740803,1740810,1740969,1740980,1740991,1740997,1741015,1741033,1741036,1741058,1741060,1741080,1741147,1741159,1741164,1741173,1741181,1741190,1741197,1741202,1741208,1741213,1741221,1741225,1741232,1741409,1741501
,1741677,1741892,1741896,1741984,1742023,1742042,1742071,1742090,1742093,1742101,1742105,1742111,1742139,1742146,1742148,1742166,1742181,1742184,1742187,1742246,1742248-1742251,1742263-1742264,1742268,1742276,1742369,1742387,1742448,1742509-1742512,1742917,1742919,1742933,1742975-1742976,1742984,1742986,1743019,1743115,1743117,1743124-1743125,1743134,1743425,1743554,1743679,1743696-1743698,1743700-1743701,1744058,1744064-1744065,1744125,1744194,1744229,1744270,1744323,1744432,1744684,1744697,1744705,1744713,1744760,1744786,1745083,1745142-1745143,1745145,1745177,1745179-1745180,1745227,1745248,1745254,1745337,1745467,1745473,1745576,1745735,1745744,1746304,1746306-1746307,1746319,1746327,1746338,1746340-1746341,1746344,1746427,1746441,1746473,1746490,1746492,1746495-1746496,1746499-1746501,1746503-1746507,1746509,1746549,1746551,1746554,1746556,1746558,1746584,1746620,1746649,1746724,1746939,1746989,1747014,1747028,1747035,1747210,1747225,1747234,1747253,1747404,1747506,1747536,1747
924,1747980,1747993,1748001,1748253,1748452,1748547,1748629,1748676,1748715,1749287,1749296,1749328,1749373,1749465,1749506,1749508,1749665-1749666,1749763,1749865-1749866,1749898,1749978,1749980,1750011,1750015,1750056,1750480,1750617,1750634,1750692,1750697,1750700,1750703,1750707,1750714,1750718,1750723,1750774,1750899,1750975,1750995,1751061,1751097,1751173,1751438,1751447,1751463,1751702,1752212,1752737,1752745,1753078,1753080,1753358,1753363,1754111,1754140-1754141,1754281,1754310,1754445,1754467,1754494,1754496,1754528,1754532-1754533,1754613,1754714,1754874,1754941,1754944,1754950-1754951,1755005,1755007,1755009,1755132,1755180-1755181,1755185,1755190,1755204-1755206,1755208,1755214,1755224,1755227,1755230,1755629,1755646-1755647,1755650,1755653,1755675,1755680,1755683,1755693,1755717,1755731-1755737,1755812,1755828,1755884,1755890,1755918-1755919,1755942,1755958,1755960,1755970,1755993,1756013,1756019,1756039,1756056,1756083-1756114,1756175,1756288-1756289,1756408-1756410,1
756778,1756798,1756878,1756898,1756939,1757123-1757124,1757126,1757128,1757132-1757133,1757136,1757145,1757167-1757168,1757175,1757180,1757182,1757195,1757271,1757278,1757347,1757353-1757354,1757363,1757374,1757399,1757406,1757408,1757485,1757495,1757499,1757527,1757578,1757684,1757722,1757727,1757790,1757799,1757813,1757853,1757883,1757903,1757976,1757997,1758000,1758058,1758072-1758075,1758078-1758079,1758223,1758257,1758261,1758276,1758292,1758369,1758378-1758383,1758421,1758423,1758425-1758427,1758430,1758443,1758448,1758459,1758483,1758486-1758487,1758499,1758525,1758556,1758580,1758582,1758584,1758588,1758842,1759019,1759212,1759224,1759227,1759252,1759274,1759513-1759516,1759611,1759757,1759785-1759790,1760005,1760022,1760109-1760110,1760135,1760200-1760201,1760227,1760300,1760397,1760446,1760454,1760640,1760648,1761057,1761422,1761491,1761498,1761500-1761501,1761550,1761553,1761572,1761574,1761625-1761626,1761628,1761682,1761740,1761752,1762051-1762053,1762123,1762168,176217
2,1762182,1762201-1762202,1762204,1762208,1762288,1762296,1762324,1762348,1762353,1762362,1762374,1762492,1762503,1762505,1762541,1762608,1762710,1762753,1762766,1762769,1762944,1762947,1762953,1763167,1763179,1763232,1763259,1763271-1763272,1763276-1763277,1763319-1763320,1763370,1763372,1763375,1763377,1763393,1763412,1763430,1763450,1763462,1763505,1763511-1763512,1763516,1763518,1763520,1763529,1763559,1763565,1763568,1763574,1763619,1763634-1763635,1763718,1763786,1763798-1763799,1763813,1763815,1763819,1763831,1764083,1764425,1764646,1764648-1764649,1764659,1764663,1764682,1764862,1764866-1764867,1764870,1764897,1765133,1765299,1765358,1765439,1765447,1765495,1765502,1765569-1765571,1765579,1765582,1765589-1765590,1765794,1765801,1765813,1765815,1766276,1766514,1766533,1766535,1766664,1766675,1766698,1766700,1767047,1767328,1767362,1767368,1767429,1767471,1767505,1767641-1767644,1767903,1767945-1767946,1768123,1768283,1768520,1768569,1768651,1768762,1768922,1769191,1769263,176
9630,1769833,1769975,1770047,1770140,1770180,1770258,1770389,1770656,1770666,1770718,1770762,1770952,1770954,1770956,1770961,1771087,1771126,1771139,1771143,1771149
+/tomcat/trunk:1734785,1734799,1734845,1734928,1735041,1735044,1735480,1735577,1735597,1735599-1735600,1735615,1736145,1736162,1736209,1736280,1736297,1736299,1736489,1736646,1736703,1736836,1736849,1737104-1737105,1737112,1737117,1737119-1737120,1737155,1737157,1737192,1737280,1737339,1737632,1737664,1737715,1737748,1737785,1737834,1737860,1737903,1737959,1738005,1738007,1738014-1738015,1738018,1738022,1738039,1738043,1738059-1738060,1738147,1738149,1738174-1738175,1738261,1738589,1738623-1738625,1738643,1738816,1738850,1738855,1738946-1738948,1738953-1738954,1738979,1738982,1739079-1739081,1739087,1739113,1739153,1739172,1739176,1739191,1739474,1739726,1739762,1739775,1739814,1739817-1739818,1739975,1740131,1740324,1740465,1740495,1740508-1740509,1740520,1740535,1740707,1740803,1740810,1740969,1740980,1740991,1740997,1741015,1741033,1741036,1741058,1741060,1741080,1741147,1741159,1741164,1741173,1741181,1741190,1741197,1741202,1741208,1741213,1741221,1741225,1741232,1741409,1741501
,1741677,1741892,1741896,1741984,1742023,1742042,1742071,1742090,1742093,1742101,1742105,1742111,1742139,1742146,1742148,1742166,1742181,1742184,1742187,1742246,1742248-1742251,1742263-1742264,1742268,1742276,1742369,1742387,1742448,1742509-1742512,1742917,1742919,1742933,1742975-1742976,1742984,1742986,1743019,1743115,1743117,1743124-1743125,1743134,1743425,1743554,1743679,1743696-1743698,1743700-1743701,1744058,1744064-1744065,1744125,1744194,1744229,1744270,1744323,1744432,1744684,1744697,1744705,1744713,1744760,1744786,1745083,1745142-1745143,1745145,1745177,1745179-1745180,1745227,1745248,1745254,1745337,1745467,1745473,1745576,1745735,1745744,1746304,1746306-1746307,1746319,1746327,1746338,1746340-1746341,1746344,1746427,1746441,1746473,1746490,1746492,1746495-1746496,1746499-1746501,1746503-1746507,1746509,1746549,1746551,1746554,1746556,1746558,1746584,1746620,1746649,1746724,1746939,1746989,1747014,1747028,1747035,1747210,1747225,1747234,1747253,1747404,1747506,1747536,1747
924,1747980,1747993,1748001,1748253,1748452,1748547,1748629,1748676,1748715,1749287,1749296,1749328,1749373,1749465,1749506,1749508,1749665-1749666,1749763,1749865-1749866,1749898,1749978,1749980,1750011,1750015,1750056,1750480,1750617,1750634,1750692,1750697,1750700,1750703,1750707,1750714,1750718,1750723,1750774,1750899,1750975,1750995,1751061,1751097,1751173,1751438,1751447,1751463,1751702,1752212,1752737,1752745,1753078,1753080,1753358,1753363,1754111,1754140-1754141,1754281,1754310,1754445,1754467,1754494,1754496,1754528,1754532-1754533,1754613,1754714,1754874,1754941,1754944,1754950-1754951,1755005,1755007,1755009,1755132,1755180-1755181,1755185,1755190,1755204-1755206,1755208,1755214,1755224,1755227,1755230,1755629,1755646-1755647,1755650,1755653,1755675,1755680,1755683,1755693,1755717,1755731-1755737,1755812,1755828,1755884,1755890,1755918-1755919,1755942,1755958,1755960,1755970,1755993,1756013,1756019,1756039,1756056,1756083-1756114,1756175,1756288-1756289,1756408-1756410,1
756778,1756798,1756878,1756898,1756939,1757123-1757124,1757126,1757128,1757132-1757133,1757136,1757145,1757167-1757168,1757175,1757180,1757182,1757195,1757271,1757278,1757347,1757353-1757354,1757363,1757374,1757399,1757406,1757408,1757485,1757495,1757499,1757527,1757578,1757684,1757722,1757727,1757790,1757799,1757813,1757853,1757883,1757903,1757976,1757997,1758000,1758058,1758072-1758075,1758078-1758079,1758223,1758257,1758261,1758276,1758292,1758369,1758378-1758383,1758421,1758423,1758425-1758427,1758430,1758443,1758448,1758459,1758483,1758486-1758487,1758499,1758525,1758556,1758580,1758582,1758584,1758588,1758842,1759019,1759212,1759224,1759227,1759252,1759274,1759513-1759516,1759611,1759757,1759785-1759790,1760005,1760022,1760109-1760110,1760135,1760200-1760201,1760227,1760300,1760397,1760446,1760454,1760640,1760648,1761057,1761422,1761491,1761498,1761500-1761501,1761550,1761553,1761572,1761574,1761625-1761626,1761628,1761682,1761740,1761752,1762051-1762053,1762123,1762168,176217
2,1762182,1762201-1762202,1762204,1762208,1762288,1762296,1762324,1762348,1762353,1762362,1762374,1762492,1762503,1762505,1762541,1762608,1762710,1762753,1762766,1762769,1762944,1762947,1762953,1763167,1763179,1763232,1763259,1763271-1763272,1763276-1763277,1763319-1763320,1763370,1763372,1763375,1763377,1763393,1763412,1763430,1763450,1763462,1763505,1763511-1763512,1763516,1763518,1763520,1763529,1763559,1763565,1763568,1763574,1763619,1763634-1763635,1763718,1763786,1763798-1763799,1763813,1763815,1763819,1763831,1764083,1764425,1764646,1764648-1764649,1764659,1764663,1764682,1764862,1764866-1764867,1764870,1764897,1765133,1765299,1765358,1765439,1765447,1765495,1765502,1765569-1765571,1765579,1765582,1765589-1765590,1765794,1765801,1765813,1765815,1766276,1766514,1766533,1766535,1766664,1766675,1766698,1766700,1767047,1767328,1767362,1767368,1767429,1767471,1767505,1767641-1767644,1767903,1767945-1767946,1768123,1768283,1768520,1768569,1768651,1768762,1768922,1769191,1769263,176
9630,1769833,1769975,1770047,1770140,1770180,1770258,1770389,1770656,1770666,1770718,1770762,1770952,1770954,1770956,1770961,1771087,1771126,1771139,1771143,1771149,1771156
Modified: tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java
URL: http://svn.apache.org/viewvc/tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java?rev=1771158&r1=1771157&r2=1771158&view=diff
==============================================================================
--- tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java (original)
+++ tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Http2UpgradeHandler.java Thu Nov 24 14:41:41 2016
@@ -1015,38 +1015,88 @@ public class Http2UpgradeHandler extends
}
// 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) {
@@ -1056,6 +1106,30 @@ public class Http2UpgradeHandler extends
}
+ 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/tc8.5.x/trunk/java/org/apache/coyote/http2/Stream.java
URL: http://svn.apache.org/viewvc/tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Stream.java?rev=1771158&r1=1771157&r2=1771158&view=diff
==============================================================================
--- tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Stream.java (original)
+++ tomcat/tc8.5.x/trunk/java/org/apache/coyote/http2/Stream.java Thu Nov 24 14:41:41 2016
@@ -130,6 +130,22 @@ public class Stream extends AbstractStre
}
+ /*
+ * 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;
+ }
+
+
void receiveReset(long errorCode) {
if (log.isDebugEnabled()) {
log.debug(sm.getString("stream.reset.debug", getConnectionId(), getIdentifier(),
@@ -546,6 +562,7 @@ public class Stream extends AbstractStre
* @deprecated Unused. Will be removed in Tomcat 9. Use
* {@link #doWrite(ByteBuffer)}
*/
+ @Deprecated
@Override
public synchronized int doWrite(ByteChunk chunk) throws IOException {
if (closed) {
@@ -721,6 +738,7 @@ public class Stream extends AbstractStre
* @deprecated Unused. Will be removed in Tomcat 9. Use
* {@link #doRead(ApplicationBufferHandler)}
*/
+ @Deprecated
@Override
public int doRead(ByteChunk chunk) throws IOException {
Modified: tomcat/tc8.5.x/trunk/webapps/docs/changelog.xml
URL: http://svn.apache.org/viewvc/tomcat/tc8.5.x/trunk/webapps/docs/changelog.xml?rev=1771158&r1=1771157&r2=1771158&view=diff
==============================================================================
--- tomcat/tc8.5.x/trunk/webapps/docs/changelog.xml (original)
+++ tomcat/tc8.5.x/trunk/webapps/docs/changelog.xml Thu Nov 24 14:41:41 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-unsubscribe@tomcat.apache.org
For additional commands, e-mail: dev-help@tomcat.apache.org