Improve performance for large multi-part boundaries.
Patch provided by Felix Schumacher.
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 0c9241f..3e53518 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -58,6 +58,7 @@
<action issue="FILEUPLOAD-245" dev="sebb" type="fix">DiskFileItem.get() may not fully read the data</action>
<action issue="FILEUPLOAD-243" dev="sebb" type="update" due-to="Ville Skyttä">Make some MultipartStream private fields final</action>
<action dev="ecki" type="add">Site: added security report</action>
+ <action dev="markt" due-to="Felix Schumacher">Improve performance for large multi-part boundaries</action>
</release>
<release version="1.3.2" description="Bugfix release for 1.3.1" date="2016-05-26">
diff --git a/src/main/java/org/apache/commons/fileupload/MultipartStream.java b/src/main/java/org/apache/commons/fileupload/MultipartStream.java
index 0d05b71..851c6eb 100644
--- a/src/main/java/org/apache/commons/fileupload/MultipartStream.java
+++ b/src/main/java/org/apache/commons/fileupload/MultipartStream.java
@@ -230,6 +230,11 @@
private final byte[] boundary;
/**
+ * The table for Knuth-Morris-Pratt search algorithm
+ */
+ private int[] boundaryTable;
+
+ /**
* The length of the buffer used for processing the request.
*/
private final int bufSize;
@@ -339,12 +344,14 @@
this.notifier = pNotifier;
this.boundary = new byte[this.boundaryLength];
+ this.boundaryTable = new int[this.boundaryLength + 1];
this.keepRegion = this.boundary.length;
System.arraycopy(BOUNDARY_PREFIX, 0, this.boundary, 0,
BOUNDARY_PREFIX.length);
System.arraycopy(boundary, 0, this.boundary, BOUNDARY_PREFIX.length,
boundary.length);
+ computeBoundaryTable();
head = 0;
tail = 0;
@@ -506,6 +513,31 @@
}
System.arraycopy(boundary, 0, this.boundary, BOUNDARY_PREFIX.length,
boundary.length);
+ computeBoundaryTable();
+ }
+
+ /**
+ * Compute the table used for Knuth-Morris-Pratt search algorithm.
+ */
+ private void computeBoundaryTable() {
+ int position = 2;
+ int candidate = 0;
+
+ boundaryTable[0] = -1;
+ boundaryTable[1] = 0;
+
+ while (position <= boundaryLength) {
+ if (boundary[position - 1] == boundary[candidate]) {
+ boundaryTable[position] = candidate + 1;
+ candidate++;
+ position++;
+ } else if (candidate > 0) {
+ candidate = boundaryTable[candidate];
+ } else {
+ boundaryTable[position] = 0;
+ position++;
+ }
+ }
}
/**
@@ -628,6 +660,7 @@
// First delimiter may be not preceeded with a CRLF.
System.arraycopy(boundary, 2, boundary, 0, boundary.length - 2);
boundaryLength = boundary.length - 2;
+ computeBoundaryTable();
try {
// Discard all data up to the delimiter.
discardBodyData();
@@ -643,6 +676,7 @@
boundaryLength = boundary.length;
boundary[0] = CR;
boundary[1] = LF;
+ computeBoundaryTable();
}
}
@@ -698,23 +732,20 @@
* not found.
*/
protected int findSeparator() {
- int first;
- int match = 0;
- int maxpos = tail - boundaryLength;
- for (first = head; first <= maxpos && match != boundaryLength; first++) {
- first = findByte(boundary[0], first);
- if (first == -1 || first > maxpos) {
- return -1;
+
+ int bufferPos = this.head;
+ int tablePos = 0;
+
+ while (bufferPos < this.tail) {
+ while (tablePos >= 0 && buffer[bufferPos] != boundary[tablePos]) {
+ tablePos = boundaryTable[tablePos];
}
- for (match = 1; match < boundaryLength; match++) {
- if (buffer[first + match] != boundary[match]) {
- break;
- }
+ bufferPos++;
+ tablePos++;
+ if (tablePos == boundaryLength) {
+ return bufferPos - boundaryLength;
}
}
- if (match == boundaryLength) {
- return first - 1;
- }
return -1;
}
