This is an automated email from the ASF dual-hosted git repository.
markt-asf pushed a commit to branch 11.0.x
in repository https://gitbox.apache.org/repos/asf/tomcat.git
The following commit(s) were added to refs/heads/11.0.x by this push:
new 1b7b9993d0 Improve performance of range validation
1b7b9993d0 is described below
commit 1b7b9993d044e6249e5b8e6d6ff1b1298af14f2c
Author: Mark Thomas <[email protected]>
AuthorDate: Fri Jun 19 18:53:54 2026 +0100
Improve performance of range validation
---
.../apache/catalina/servlets/DefaultServlet.java | 82 ++++++++++++++--------
.../org/apache/tomcat/util/http/parser/Ranges.java | 35 ++++++++-
.../servlets/TestDefaultServletRangeRequests.java | 14 ++++
webapps/docs/changelog.xml | 4 ++
4 files changed, 103 insertions(+), 32 deletions(-)
diff --git a/java/org/apache/catalina/servlets/DefaultServlet.java
b/java/org/apache/catalina/servlets/DefaultServlet.java
index 6868717fff..12a0e3a87f 100644
--- a/java/org/apache/catalina/servlets/DefaultServlet.java
+++ b/java/org/apache/catalina/servlets/DefaultServlet.java
@@ -42,6 +42,7 @@ import java.util.Comparator;
import java.util.Enumeration;
import java.util.List;
import java.util.Locale;
+import java.util.TreeSet;
import java.util.function.Function;
import javax.xml.transform.Source;
@@ -1368,43 +1369,62 @@ public class DefaultServlet extends HttpServlet {
}
private static boolean validate(Ranges ranges, long length) {
- List<long[]> rangeContext = new ArrayList<>();
- int overlapCount = 0;
+ /*
+ * 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.
+ */
+ TreeSet<Ranges.Entry> orderedRanges = new TreeSet<>();
for (Ranges.Entry range : ranges.getEntries()) {
- long start = getStart(range, length);
- long end = getEnd(range, length);
- if (start < 0 || start > end) {
+ // Adjusted values depend on both original values so calculate
both adjusted values first then update range.
+ long adjustedStart = getStart(range, length);
+ long adjustedEnd = getEnd(range, length);
+ if (adjustedStart > adjustedEnd) {
// Invalid range
return false;
}
- /*
- * 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 (start <= e2 && s2 <= end) {
- overlapCount++;
- // Off by one is deliberate. There is 1 more overlapping
range than there are overlaps.
- if (overlapCount > 1) {
- return false;
- }
- }
+ Ranges.Entry adjustedRange = new Ranges.Entry(adjustedStart,
adjustedEnd);
+
+ orderedRanges.add(adjustedRange);
+ }
+
+ int overlapCount = ranges.getEntries().size() - orderedRanges.size();
+ // This only detected duplicate ranges. Each duplicate is equivalent
to 1 overlap.
+ // Off by one is deliberate. There is 1 more overlapping range than
there are overlaps.
+ if (overlapCount > 1) {
+ return false;
+ }
+
+ /*
+ * 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 (Ranges.Entry range : orderedRanges) {
+ if (range.getStart() <= latestObservedEnd) {
+ overlapCount++;
+ }
+
+
+ if (range.getEnd() > latestObservedEnd) {
+ latestObservedEnd = range.getEnd();
+ }
+
+ // Off by one is deliberate. There is 1 more overlapping range
than there are overlaps.
+ if (overlapCount > 1) {
+ return false;
}
- rangeContext.add(new long[] { start, end });
}
+
return true;
}
diff --git a/java/org/apache/tomcat/util/http/parser/Ranges.java
b/java/org/apache/tomcat/util/http/parser/Ranges.java
index d7e9fa6b2d..6cd73fab31 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.
@@ -71,7 +72,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;
@@ -107,6 +108,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 f92fa9ed58..520ac52efb 100644
--- a/webapps/docs/changelog.xml
+++ b/webapps/docs/changelog.xml
@@ -974,6 +974,10 @@
<bug>69932</bug>: Fix request end access log pattern regression,
which would log the start time of the request instead. (remm)
</fix>
+ <fix>
+ Improve the performance of range validation for the default servlet.
+ (markt)
+ </fix>
</changelog>
</subsection>
<subsection name="Coyote">
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
