This is an automated email from the ASF dual-hosted git repository. chibenwa pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/james-jdkim.git
commit f140f98296a2eefefbb52db0d67b34fa4eb3cdaf Author: Benoit TELLIER <[email protected]> AuthorDate: Thu Nov 19 06:07:20 2026 +0100 [PERF] TagValue: check the tag-list syntax with loops, parse lists once Each tag of a DKIM-Signature field or key record went through up to four regex matchers for its whitespace, one for its name and one for its value, every char of b=, p= or g= taking a chain of virtual calls. stringToColonSeparatedList compiled a regex on every call, and the verifier parsed h= three times per signature and the key lists twice. The tag name, value and FWS checks are now loops over the string, with the same grammar: VALCHAR plus U+0080-U+FFFF checked by code point, one FWS around tags and values, two around an empty value. A loop does not recurse, as the possessive patterns had to avoid. The empty-list check tests the last char, and g= is checked with a loop. SignatureRecordImpl keeps the parsed h= list and PublicKeyRecordImpl its s=, h=, k=, t= lists and the g= pattern, until the value or the strict validation setting changes. The lists returned are unmodifiable. The exception messages are unchanged. --- .../james/jdkim/tagvalue/PublicKeyRecordImpl.java | 92 +++++++++-- .../james/jdkim/tagvalue/SignatureRecordImpl.java | 14 +- .../org/apache/james/jdkim/tagvalue/TagValue.java | 181 ++++++++++++++++++--- 3 files changed, 242 insertions(+), 45 deletions(-) diff --git a/main/src/main/java/org/apache/james/jdkim/tagvalue/PublicKeyRecordImpl.java b/main/src/main/java/org/apache/james/jdkim/tagvalue/PublicKeyRecordImpl.java index 5d64587..f35365e 100644 --- a/main/src/main/java/org/apache/james/jdkim/tagvalue/PublicKeyRecordImpl.java +++ b/main/src/main/java/org/apache/james/jdkim/tagvalue/PublicKeyRecordImpl.java @@ -35,11 +35,6 @@ import java.util.regex.Pattern; public class PublicKeyRecordImpl extends TagValue implements PublicKeyRecord { - // Any run of atext: the same values as the former "(atom)?\*?(atom)?", atext including "*". - // One possessive class: the former pattern tried every split of the run between its two groups - // before failing, quadratic in the length of an invalid value. - private static final Pattern granularityPattern = Pattern.compile("^[a-zA-Z0-9!#$%&'*+/=?^_`{}|~-]*+$"); - // SPEC: hyphenated-word = ALPHA [ *(ALPHA / DIGIT / "-") (ALPHA / DIGIT) ] private static final Pattern hyphenatedWordPattern = Pattern .compile("^[a-zA-Z]([a-zA-Z0-9-]*[a-zA-Z0-9])?$"); @@ -48,6 +43,13 @@ public class PublicKeyRecordImpl extends TagValue implements PublicKeyRecord { private static final Pattern serviceTypePattern = Pattern .compile("^(\\*|[a-zA-Z]([a-zA-Z0-9-]*[a-zA-Z0-9])?)$"); + // the verifier reads these lists more than once per key: each one is parsed once + private volatile ParsedValue<List<CharSequence>> serviceTypes; + private volatile ParsedValue<List<CharSequence>> hashMethods; + private volatile ParsedValue<List<CharSequence>> keyTypes; + private volatile ParsedValue<List<CharSequence>> flags; + private volatile ParsedValue<Pattern> granularity; + public PublicKeyRecordImpl(String data) { super(data); } @@ -100,8 +102,18 @@ public class PublicKeyRecordImpl extends TagValue implements PublicKeyRecord { * @return the listed types; with strict validation, an {@link IllegalStateException} on a malformed list */ public List<CharSequence> getServiceTypes() { - String s = getValue("s").toString(); - if (isStrictValidation()) { + CharSequence source = getValue("s"); + boolean strict = isStrictValidation(); + ParsedValue<List<CharSequence>> cached = serviceTypes; + if (cached == null || !cached.isFor(source, strict)) { + cached = new ParsedValue<>(source, strict, unmodifiable(parseServiceTypes(source.toString(), strict))); + serviceTypes = cached; + } + return cached.get(); + } + + private List<CharSequence> parseServiceTypes(String s, boolean strict) { + if (strict) { return stringToColonSeparatedList(s, serviceTypePattern); } List<CharSequence> res = new ArrayList<>(); @@ -139,28 +151,64 @@ public class PublicKeyRecordImpl extends TagValue implements PublicKeyRecord { * @see org.apache.james.jdkim.api.PublicKeyRecord#getAcceptableHashMethods() */ public List<CharSequence> getAcceptableHashMethods() { - if (ANY.equals(getValue("h"))) - return null; - return stringToColonSeparatedList(getValue("h").toString(), - hyphenatedWordPattern); + CharSequence source = getValue("h"); + boolean strict = isStrictValidation(); + ParsedValue<List<CharSequence>> cached = hashMethods; + if (cached == null || !cached.isFor(source, strict)) { + cached = new ParsedValue<>(source, strict, ANY.equals(source) ? null + : unmodifiable(stringToColonSeparatedList(source.toString(), hyphenatedWordPattern))); + hashMethods = cached; + } + return cached.get(); } /** * @see org.apache.james.jdkim.api.PublicKeyRecord#getAcceptableKeyTypes() */ public List<CharSequence> getAcceptableKeyTypes() { - return stringToColonSeparatedList(getValue("k").toString(), - hyphenatedWordPattern); + CharSequence source = getValue("k"); + boolean strict = isStrictValidation(); + ParsedValue<List<CharSequence>> cached = keyTypes; + if (cached == null || !cached.isFor(source, strict)) { + cached = new ParsedValue<>(source, strict, + unmodifiable(stringToColonSeparatedList(source.toString(), hyphenatedWordPattern))); + keyTypes = cached; + } + return cached.get(); } /** * @see org.apache.james.jdkim.api.PublicKeyRecord#getGranularityPattern() */ public Pattern getGranularityPattern() { - String g = getValue("g").toString(); + CharSequence source = getValue("g"); + ParsedValue<Pattern> cached = granularity; + if (cached == null || !cached.isFor(source, false)) { + cached = new ParsedValue<>(source, false, parseGranularity(source.toString())); + granularity = cached; + } + return cached.get(); + } + + /** + * Any run of atext, "*" included: the same values as the former "(atom)?\*?(atom)?". A loop over the + * chars, since the value is chosen by the domain owner and may be long. + */ + private static boolean isGranularity(String g) { + for (int i = 0; i < g.length(); i++) { + char c = g.charAt(i); + if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') + || "!#$%&'*+/=?^_`{}|~-".indexOf(c) != -1)) { + return false; + } + } + return true; + } + + private static Pattern parseGranularity(String g) { int pStar = g.indexOf('*'); if (VALIDATION) { - if (!granularityPattern.matcher(g).matches()) + if (!isGranularity(g)) throw new IllegalStateException("Syntax error in granularity: " + g); } @@ -185,8 +233,18 @@ public class PublicKeyRecordImpl extends TagValue implements PublicKeyRecord { } public List<CharSequence> getFlags() { - String flags = getValue("t").toString(); - if (isStrictValidation() && containsTag("t")) { + CharSequence source = getValue("t"); + boolean strict = isStrictValidation(); + ParsedValue<List<CharSequence>> cached = flags; + if (cached == null || !cached.isFor(source, strict)) { + cached = new ParsedValue<>(source, strict, unmodifiable(parseFlags(source.toString(), strict))); + flags = cached; + } + return cached.get(); + } + + private List<CharSequence> parseFlags(String flags, boolean strict) { + if (strict && containsTag("t")) { // SPEC: key-t-tag-flag *( [FWS] ":" [FWS] key-t-tag-flag ), each a hyphenated-word return stringToColonSeparatedList(flags, hyphenatedWordPattern); } diff --git a/main/src/main/java/org/apache/james/jdkim/tagvalue/SignatureRecordImpl.java b/main/src/main/java/org/apache/james/jdkim/tagvalue/SignatureRecordImpl.java index 1c49856..d2cb413 100644 --- a/main/src/main/java/org/apache/james/jdkim/tagvalue/SignatureRecordImpl.java +++ b/main/src/main/java/org/apache/james/jdkim/tagvalue/SignatureRecordImpl.java @@ -237,6 +237,8 @@ public class SignatureRecordImpl extends TagValue implements SignatureRecord { private static final Pattern timestampPattern = Pattern.compile("^[0-9]{1,12}$"); private static final Pattern bodyLengthPattern = Pattern.compile("^[0-9]{1,76}$"); + private volatile ParsedValue<List<CharSequence>> parsedHeaders; + public SignatureRecordImpl(String data) { super(data); validate(); @@ -378,8 +380,16 @@ public class SignatureRecordImpl extends TagValue implements SignatureRecord { * @see org.apache.james.jdkim.api.SignatureRecord#getHeaders() */ public List<CharSequence> getHeaders() { - return stringToColonSeparatedList(getValue("h").toString(), - hdrNamePattern); + // the verifier asks for h= several times per signature: it is parsed once + CharSequence h = getValue("h"); + boolean strict = isStrictValidation(); + ParsedValue<List<CharSequence>> cached = parsedHeaders; + if (cached == null || !cached.isFor(h, strict)) { + cached = new ParsedValue<>(h, strict, + unmodifiable(stringToColonSeparatedList(h.toString(), hdrNamePattern))); + parsedHeaders = cached; + } + return cached.get(); } // If i= is unspecified the default is @d diff --git a/main/src/main/java/org/apache/james/jdkim/tagvalue/TagValue.java b/main/src/main/java/org/apache/james/jdkim/tagvalue/TagValue.java index 46d4079..46292d2 100644 --- a/main/src/main/java/org/apache/james/jdkim/tagvalue/TagValue.java +++ b/main/src/main/java/org/apache/james/jdkim/tagvalue/TagValue.java @@ -21,6 +21,7 @@ package org.apache.james.jdkim.tagvalue; import java.util.ArrayList; import java.util.Base64; +import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.List; @@ -51,22 +52,10 @@ public class TagValue { return !"false".equalsIgnoreCase(System.getProperty(STRICT_VALIDATION_PROPERTY, "true").trim()); } - private static final Pattern tagPattern = Pattern - .compile("^[A-Za-z][A-Za-z0-9_]*$"); - // RFC 6376 section 3.2: tval = 1*VALCHAR, VALCHAR = %x21-3A / %x3C-7E, plus the UTF8-non-ascii - // octets RFC 8616 section 4 allows in i= and z= for internationalized mail (header octets are read as - // ISO-8859-1, so they arrive as U+0080 to U+00FF; the header hashing rejects anything above). - // Use possessive matching to avoid heavy stack usage - private static final String tval = "[\\x21-\\x3a\\x3c-\\x7e\\u0080-\\uffff]++"; - // validate value chars - // Use possessive matching to avoid heavy stack usage - private static final Pattern valuePattern = Pattern.compile("^(?:" + tval - + "(?:(?:(?:\r\n)?[\t ])++" + tval + ")*+)?$"); + // The syntax checks below are loops over the chars rather than regular expressions: they run for every + // tag of every DKIM-Signature field and key record, and a loop does not recurse, which is why the former + // patterns had to be possessive (a long z= overflowed the stack). private static final Pattern fwsPattern = Pattern.compile("[ \t\r\n]"); - // FWS = [*WSP CRLF] 1*WSP, or nothing - private static final Pattern trailingFWSPattern = Pattern.compile("^(?:(?:[ \t]*\r\n)?[ \t]+)?$"); - // [FWS] tag-value [FWS] with an empty tag-value: up to two FWS, possessive to stay linear - private static final Pattern twoFWSPattern = Pattern.compile("^(?:(?:[ \t]*+\r\n)?+[ \t]++){0,2}+$"); // we may use a TreeMap because we may need to know original order. private final Map<String, CharSequence> tagValues; @@ -165,11 +154,10 @@ public class TagValue { int equal = data.indexOf('=', i); if (equal == -1) { // only FWS may follow the final ";" - String rest = data.substring(i); - if (!trailingFWSPattern.matcher(rest).matches()) { + if (!isFWS(data, i, data.length())) { throw new IllegalStateException( "Unexpected termination at position " + i + ": " - + data + " | [" + rest + "]"); + + data + " | [" + data.substring(i) + "]"); } i = data.length(); continue; @@ -192,7 +180,7 @@ public class TagValue { checkSingleFWSAround(data, equal + 1, next); } CharSequence tag = trimFWS(data, i, equal - 1, true).toString(); - if (VALIDATION && !tagPattern.matcher(tag).matches()) { + if (VALIDATION && !isTagName(tag)) { throw new IllegalStateException("Syntax error in tag: " + tag); } String tagString = tag.toString(); @@ -202,7 +190,7 @@ public class TagValue { } CharSequence value = trimFWS(data, equal + 1, next - 1, true); - if (VALIDATION && !valuePattern.matcher(value).matches()) { + if (VALIDATION && !isValue(value)) { throw new IllegalStateException("Syntax error in value: " + value); } @@ -227,17 +215,15 @@ public class TagValue { while (contentEnd > contentStart && isFWSChar(data.charAt(contentEnd - 1))) { contentEnd--; } - String leading = data.substring(start, contentStart); - String trailing = data.substring(contentEnd, end); if (contentStart == end) { // no content: the run holds the FWS before and the FWS after an empty value - if (!twoFWSPattern.matcher(leading).matches()) { + if (!isTwoFWS(data, start, end)) { throw new IllegalStateException("Syntax error: whitespace that is not FWS in [" - + leading + "]"); + + data.substring(start, end) + "]"); } return; } - if (!trailingFWSPattern.matcher(leading).matches() || !trailingFWSPattern.matcher(trailing).matches()) { + if (!isFWS(data, start, contentStart) || !isFWS(data, contentEnd, end)) { throw new IllegalStateException("Syntax error: whitespace that is not FWS in [" + data.substring(start, end) + "]"); } @@ -247,6 +233,116 @@ public class TagValue { return c == ' ' || c == '\t' || c == '\r' || c == '\n'; } + private static boolean isWSP(char c) { + return c == ' ' || c == '\t'; + } + + /** + * @return the end of the FWS = [*WSP CRLF] 1*WSP that starts data[start, end) at start, or -1 + */ + private static int endOfFWS(CharSequence data, int start, int end) { + int p = start; + while (p < end && isWSP(data.charAt(p))) { + p++; + } + if (p + 1 < end && data.charAt(p) == '\r' && data.charAt(p + 1) == '\n') { + int q = p + 2; + while (q < end && isWSP(data.charAt(q))) { + q++; + } + return q > p + 2 ? q : -1; + } + return p > start ? p : -1; + } + + /** + * @return whether data[start, end) is empty or a single FWS + */ + private static boolean isFWS(CharSequence data, int start, int end) { + return start == end || endOfFWS(data, start, end) == end; + } + + /** + * @return whether data[start, end) is at most two FWS + */ + private static boolean isTwoFWS(CharSequence data, int start, int end) { + int p = start; + for (int fws = 0; fws < 2 && p < end; fws++) { + p = endOfFWS(data, p, end); + if (p == -1) { + return false; + } + } + return p == end; + } + + /** + * SPEC: tag-name = ALPHA *ALNUMPUNC, ALNUMPUNC = ALPHA / DIGIT / "_" + */ + private static boolean isTagName(CharSequence tag) { + if (tag.length() == 0 || !isAlpha(tag.charAt(0))) { + return false; + } + for (int i = 1; i < tag.length(); i++) { + char c = tag.charAt(i); + if (!isAlpha(c) && !(c >= '0' && c <= '9') && c != '_') { + return false; + } + } + return true; + } + + private static boolean isAlpha(char c) { + return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); + } + + /** + * SPEC: tag-value = [ tval *( 1*(WSP / FWS) tval ) ], tval = 1*VALCHAR, VALCHAR = %x21-3A / %x3C-7E. + * VALCHAR also takes the UTF8-non-ascii octets RFC 8616 section 4 allows in i= and z= for + * internationalized mail: header octets are read as ISO-8859-1, so they arrive as U+0080 to U+00FF, and + * the header hashing rejects anything above. Code points are checked, so a surrogate pair (above U+FFFF) + * is not a VALCHAR. + */ + private static boolean isValue(CharSequence value) { + int n = value.length(); + int i = endOfTval(value, 0); + if (n > 0 && i == 0) { + return false; + } + while (i < n) { + // 1*([CRLF] WSP) between two tval + int j = i; + while (true) { + if (j < n && isWSP(value.charAt(j))) { + j++; + } else if (j + 2 < n && value.charAt(j) == '\r' && value.charAt(j + 1) == '\n' + && isWSP(value.charAt(j + 2))) { + j += 3; + } else { + break; + } + } + int k = endOfTval(value, j); + if (j == i || k == j) { + return false; + } + i = k; + } + return true; + } + + private static int endOfTval(CharSequence value, int start) { + int i = start; + while (i < value.length()) { + int cp = Character.codePointAt(value, i); + if (!((cp >= 0x21 && cp <= 0x3a) || (cp >= 0x3c && cp <= 0x7e) || (cp >= 0x80 && cp <= 0xffff))) { + break; + } + i += Character.charCount(cp); + } + return i; + } + public int hashCode() { final int prime = 31; int result = 1; @@ -335,7 +431,8 @@ public class TagValue { protected List<CharSequence> stringToColonSeparatedList(String h, Pattern pattern) { List<CharSequence> headers = new ArrayList<>(); // SPEC: entry *( [FWS] ":" [FWS] entry ): neither an empty list nor a trailing ":" - if (isStrictValidation() && h.trim().matches("(?s)|.*:")) { + String trimmed = h.trim(); + if (isStrictValidation() && (trimmed.isEmpty() || trimmed.charAt(trimmed.length() - 1) == ':')) { throw new IllegalStateException("Syntax error in list: empty entry in [" + h + "]"); } for (int i = 0; i < h.length(); i++) { @@ -354,6 +451,38 @@ public class TagValue { return headers; } + /** + * Something parsed from a tag value, kept as long as the value (the same instance: values only change + * through {@link #setValue(String, String)}) and the strictness of the validation are the same. The + * parsed object must be immutable: it is returned to every caller. + */ + protected static final class ParsedValue<T> { + private final CharSequence source; + private final boolean strict; + private final T parsed; + + protected ParsedValue(CharSequence source, boolean strict, T parsed) { + this.source = source; + this.strict = strict; + this.parsed = parsed; + } + + protected boolean isFor(CharSequence source, boolean strict) { + return this.source == source && this.strict == strict; + } + + protected T get() { + return parsed; + } + } + + /** + * @return list, unmodifiable, or null + */ + protected static List<CharSequence> unmodifiable(List<CharSequence> list) { + return list == null ? null : Collections.unmodifiableList(list); + } + protected boolean isInListCaseInsensitive(CharSequence hash, List<CharSequence> hashes) { for (CharSequence suppHash : hashes) { if (hash.toString().equalsIgnoreCase(suppHash.toString())) --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
