This is an automated email from the ASF dual-hosted git repository.
markt-asf pushed a commit to branch 9.0.x
in repository https://gitbox.apache.org/repos/asf/tomcat.git
The following commit(s) were added to refs/heads/9.0.x by this push:
new e7980851ab Improve performance of range validation
e7980851ab is described below
commit e7980851abd006716e795b11e0fd699c34cb839b
Author: Mark Thomas <[email protected]>
AuthorDate: Fri Jun 19 18:53:54 2026 +0100
Improve performance of range validation
---
.../apache/catalina/servlets/DefaultServlet.java | 123 ++++++++++++++-------
.../org/apache/tomcat/util/http/parser/Ranges.java | 35 +++++-
.../servlets/TestDefaultServletRangeRequests.java | 14 +++
webapps/docs/changelog.xml | 4 +
4 files changed, 138 insertions(+), 38 deletions(-)
diff --git a/java/org/apache/catalina/servlets/DefaultServlet.java
b/java/org/apache/catalina/servlets/DefaultServlet.java
index e5e850ac8d..d6212eac2f 100644
--- a/java/org/apache/catalina/servlets/DefaultServlet.java
+++ b/java/org/apache/catalina/servlets/DefaultServlet.java
@@ -43,6 +43,8 @@ import java.util.Enumeration;
import java.util.Iterator;
import java.util.List;
import java.util.Locale;
+import java.util.Objects;
+import java.util.TreeSet;
import java.util.function.Function;
import javax.servlet.DispatcherType;
@@ -1596,12 +1598,20 @@ public class DefaultServlet extends HttpServlet {
return FULL;
}
- // Can't update to use Ranges as this is a protected method. Only
backwards compatible API changes are allowed.
- // Convert to Range
+ /*
+ * Can't update to use Ranges as this is a protected method. Only
backwards compatible API changes are allowed.
+ *
+ * Combine converting to Range with checking for overlaps.
+ *
+ * Looking for overlapping ranges.
+ *
+ * Where the start or end (never both as that would be invalid) is -1,
update the start and/or end as
+ * appropriate to the actual start and end points in the file.
+ *
+ * Then process the ranges in order. If range starts before the
largest observed end so far, it must overlap.
+ */
ArrayList<Range> result = new ArrayList<>();
-
- List<long[]> rangeContext = new ArrayList<>();
- int overlapCount = 0;
+ TreeSet<Range> orderedRanges = new TreeSet<>();
for (Ranges.Entry entry : ranges.getEntries()) {
Range currentRange = new Range();
if (entry.getStart() == -1) {
@@ -1618,44 +1628,53 @@ public class DefaultServlet extends HttpServlet {
currentRange.end = entry.getEnd();
}
currentRange.length = fileLength;
-
if (!currentRange.validate()) {
response.addHeader("Content-Range", "bytes */" + fileLength);
response.sendError(HttpServletResponse.SC_REQUESTED_RANGE_NOT_SATISFIABLE);
return null;
}
- // See https://www.rfc-editor.org/rfc/rfc9110.html#status.416
- /*
- * See https://www.rfc-editor.org/rfc/rfc9110.html#name-range and
- * https://www.rfc-editor.org/rfc/rfc9110.html#status.416
- *
- * The server MAY ignore or reject Range headers with:
- *
- * - "Many" (undefined) small ranges not in ascending order - not
currently enforced.
- *
- * - More than two overlapping ranges (enforced)
- */
- for (long[] r : rangeContext) {
- long s2 = r[0];
- long e2 = r[1];
- // Given valid [s1,e1] and [s2,e2]
- // If { s1>e2 || s2>e1 } then no overlap
- // equivalent to
- // If not { s1>e2 || s2>e1 } then overlap
- // De Morgan's law
- if (currentRange.start <= e2 && s2 <= currentRange.end) {
- overlapCount++;
- // Off by one is deliberate. There is 1 more overlapping
range than there are overlaps.
- if (overlapCount > 1) {
- response.addHeader("Content-Range", "bytes */" +
fileLength);
-
response.sendError(HttpServletResponse.SC_REQUESTED_RANGE_NOT_SATISFIABLE);
- return null;
- }
- }
- }
- rangeContext.add(new long[] { currentRange.start, currentRange.end
});
result.add(currentRange);
+ orderedRanges.add(currentRange);
+ }
+
+ // This only detected duplicate ranges. Each duplicate is equivalent
to 1 overlap.
+ int overlapCount = ranges.getEntries().size() - orderedRanges.size();
+ // Off by one is deliberate. There is 1 more overlapping range than
there are overlaps.
+ if (overlapCount > 1) {
+ response.addHeader("Content-Range", "bytes */" + fileLength);
+
response.sendError(HttpServletResponse.SC_REQUESTED_RANGE_NOT_SATISFIABLE);
+ return null;
+ }
+
+ // See https://www.rfc-editor.org/rfc/rfc9110.html#status.416
+ /*
+ * See https://www.rfc-editor.org/rfc/rfc9110.html#name-range and
+ * https://www.rfc-editor.org/rfc/rfc9110.html#status.416
+ *
+ * The server MAY ignore or reject Range headers with:
+ *
+ * - "Many" (undefined) small ranges not in ascending order - not
currently enforced.
+ *
+ * - More than two overlapping ranges (enforced)
+ */
+ long latestObservedEnd = -1;
+ for (Range range : orderedRanges) {
+ if (range.start <= latestObservedEnd) {
+ overlapCount++;
+ }
+
+
+ if (range.end > latestObservedEnd) {
+ latestObservedEnd = range.end;
+ }
+
+ // Off by one is deliberate. There is 1 more overlapping range
than there are overlaps.
+ if (overlapCount > 1) {
+ response.addHeader("Content-Range", "bytes */" + fileLength);
+
response.sendError(HttpServletResponse.SC_REQUESTED_RANGE_NOT_SATISFIABLE);
+ return null;
+ }
}
return result;
@@ -2958,7 +2977,7 @@ public class DefaultServlet extends HttpServlet {
}
- protected static class Range {
+ protected static class Range implements Comparable<Range> {
public long start;
public long end;
@@ -2975,8 +2994,38 @@ public class DefaultServlet extends HttpServlet {
}
return (start >= 0) && (end >= 0) && (start <= end) && (length >
0);
}
+
+ @Override
+ public int compareTo(Range o) {
+ if (start == o.start) {
+ return Long.compare(end, o.end);
+ } else {
+ return Long.compare(start, o.start);
+ }
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(Long.valueOf(end), Long.valueOf(start));
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null) {
+ return false;
+ }
+ if (getClass() != obj.getClass()) {
+ return false;
+ }
+ Range other = (Range) obj;
+ return end == other.end && start == other.start;
+ }
}
+
protected static class CompressionFormat implements Serializable {
private static final long serialVersionUID = 1L;
public final String extension;
diff --git a/java/org/apache/tomcat/util/http/parser/Ranges.java
b/java/org/apache/tomcat/util/http/parser/Ranges.java
index bddb449139..66bc1dd075 100644
--- a/java/org/apache/tomcat/util/http/parser/Ranges.java
+++ b/java/org/apache/tomcat/util/http/parser/Ranges.java
@@ -22,6 +22,7 @@ import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Locale;
+import java.util.Objects;
/**
* Represents the value of an HTTP Range header.
@@ -65,7 +66,7 @@ public class Ranges {
/**
* Represents a single range entry with a start and end position.
*/
- public static class Entry {
+ public static class Entry implements Comparable<Entry> {
private final long start;
private final long end;
@@ -101,6 +102,38 @@ public class Ranges {
public long getEnd() {
return end;
}
+
+
+ @Override
+ public int compareTo(Entry o) {
+ if (start == o.start) {
+ return Long.compare(end, o.end);
+ } else {
+ return Long.compare(start, o.start);
+ }
+ }
+
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(Long.valueOf(end), Long.valueOf(start));
+ }
+
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null) {
+ return false;
+ }
+ if (getClass() != obj.getClass()) {
+ return false;
+ }
+ Entry other = (Entry) obj;
+ return end == other.end && start == other.start;
+ }
}
diff --git
a/test/org/apache/catalina/servlets/TestDefaultServletRangeRequests.java
b/test/org/apache/catalina/servlets/TestDefaultServletRangeRequests.java
index 60b1aec9bf..f560a2af20 100644
--- a/test/org/apache/catalina/servlets/TestDefaultServletRangeRequests.java
+++ b/test/org/apache/catalina/servlets/TestDefaultServletRangeRequests.java
@@ -106,6 +106,20 @@ public class TestDefaultServletRangeRequests extends
TomcatBaseTest {
"bytes=0-1000", null, Integer.valueOf(206), strLen, "0-" +
(len - 1) + "/" + len });
parameterSets.add(new Object[] {
"bytes=-1000", null, Integer.valueOf(206), strLen, "0-" + (len
- 1) + "/" + len });
+ // Lots of small ranges (test target has a little over 900 bytes.
Exact length varies by platform."
+ StringBuilder range = new StringBuilder();
+ range.append("bytes=");
+ int lastRange = 900;
+ for (int i = 1; i < lastRange; i++) {
+ range.append(i);
+ range.append('-');
+ range.append(i);
+ range.append(',');
+ }
+ range.append(lastRange);
+ range.append('-');
+ range.append(lastRange);
+ parameterSets.add(new Object[] { range.toString(), null,
Integer.valueOf(206), null, "500-500/" + len });
/* If-Range tests */
// Valid
diff --git a/webapps/docs/changelog.xml b/webapps/docs/changelog.xml
index 27bb378fbd..10aef95326 100644
--- a/webapps/docs/changelog.xml
+++ b/webapps/docs/changelog.xml
@@ -114,6 +114,10 @@
Avoid a race condition with concurrent lookups for a singleton JNDI
resource. (markt)
</fix>
+ <fix>
+ Improve the performance of range validation for the default servlet.
+ (markt)
+ </fix>
</changelog>
</subsection>
</section>
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
