Repository: netty/netty
Issue: HpackUtil.equals performance improvement
Labels: improvement

PR https://github.com/netty/netty/pull/5355 modified interfaces to reduce GC related to the HPACK code. However this came with an anticipated performance regression related to `HpackUtil.equals` due to `AsciiString`'s increase cost of `charAt(..)`. We should mitigate this performance regression.


Issue comments:
`HpackUtil.equals` currently implements an equality comparison which "doesn't leak timing information" [1]. @jpinner - can you provide some motivation for why this type of comparison is necessary in this specific case?

[1] https://github.com/twitter/hpack/commit/84e3438ae60efad587c7058c87b04064d7d6a536#diff-d23f44552b6381004428efb52e1667baR26

@Scottmitch I think it has something to do with security http://httpwg.org/specs/rfc7541.html#Security

@buchgr that's correct
@Scottmitch it's to help prevent timing-based side-channel attacks on header field values

Understood it is to prevent timing side-channel attacks. I guess the compromise was made to leak when the length is correct, but not how many characters are matching.

Thanks for looking into this Scott! I believe this is quite an urgent issue for gRPC that would be great to have in the next Netty 4.1.2. So please do let us know if you don't have enough cycles, we are happy to help out!  cc: @carl-mastrangelo 

@buchgr - Np. PR is pending.

This might be a dumb question, but does the constant time compare really need to be used for non-security sensitive headers?  HPACK provides a means to not use indexing and never indexing, which seems like it implies they sensitive.  Most of the time we do want the fast, time-leaking compare.

@carl-mastrangelo - +1

@jpinner - WDYT?

I'd have to take a pass through the code and see exactly how it's used. The compare does predate the inclusion of the "never index" flag. That being said I can certainly think of "sensitive" headers that you might want to index for performance in the table (e.g. domain cookies sent on every request).

I personally would be cautious here.

Sent from my iPhone

> On Jun 22, 2016, at 2:21 PM, Scott Mitchell notifications@github.com wrote:
> 
> @carl-mastrangelo - +1
> 
> @jpinner - WDYT?
> 
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub, or mute the thread.


Pull request review comments:
@Scottmitch could you not just use the methods in PlatformDependent0 ?

can you clarify which method you are suggesting I use? `PlatformDependent0` doesn't have a equals which accepts a `CharSequence`.

I ran benchmarks comparing some equals functions, and found that it is significantly faster to use an int rather than a byte:

```
HeadersBenchmark.arrays              4096  sample  129777  1227.096 ± 4.670  ns/op
HeadersBenchmark.digest              4096  sample  127528  2488.555 ± 6.749  ns/op
HeadersBenchmark.theBytes            4096  sample   99710  3170.983 ± 9.587  ns/op
HeadersBenchmark.theChars            4096  sample  105714  2992.226 ± 8.468  ns/op
HeadersBenchmark.theInts             4096  sample  126811  2497.360 ± 7.106  ns/op
HeadersBenchmark.theLongs            4096  sample   99672  3181.179 ± 8.380  ns/op
HeadersBenchmark.theShorts           4096  sample  100008  3158.683 ± 8.164  ns/op
```

`arrays` is Arrays.equals (for comparison)
`digest` is MessageDigest.isEqual  (broken upto in partly java6, fixed in 2009)
All the others are copy paste versions of MessageDigest.isEqual  using different accumulators.

The [Go](https://golang.org/src/crypto/subtle/constant_time.go?s=490:531#L2) implementation uses a constant time comparison for the final check here.  You might consider using it too.

thanks @carl-mastrangelo !

never mind ... I thought this two methods are a copy of what you have implemented...

@carl-mastrangelo - I repeated your benchmark when charsequence is used and not surprisingly I see the same results ... i'll make the same change here too

```
Benchmark                  Mode     Cnt     Score   Error  Units
TestBenchmark.theChars   sample  152044  2105.563 ± 7.328  ns/op
TestBenchmark.theInts    sample  141490  1155.404 ± 6.013  ns/op
TestBenchmark.theLongs   sample  108386  1498.885 ± 8.700  ns/op
TestBenchmark.theShorts  sample  151317  2119.505 ± 8.116  ns/op
```

+1. Done

@carl-mastrangelo - note this change ... before it was skipping out early if the name didn't match ... which may yield some timing info.

I propose we do a follow up investigation if you think we can reduce the amount of "constant time comparisons" that we must do ... or just generally if we are using the  "constant time comparisons" where/how we should be.

I asked internally how "constant" a constant function needs to be, and so far the answer has been "nothing is constant and will basically be impossible with an optimizing compiler / processor".

This is best effort, and copying behavior of other security reviewed code feels like said effort.

Are you using & to avoid short circuit behavior?  If so, that's subtle and deserves a comment.   If not, then && seems appropriate.

Yes. I can add a comment (this preserves existing behavior).

That should be placed into `equalsConstantTime` in `ConstantTimeUtils` and `PlatformDependent` as that's generally useful for have in an equals method. Shorter strings are smaller or so.

I think the name is misleading, as it's not constant time equals?

We should probably come up with a better name for this class ... `EqualsUtils`?

Can you clarify your suggestion? `ConstantTimeUtils` for `CharSequence` does have this check. However the variant which operates on `byte[]` accepts a length parameter ... so it is implied the length which will be iterated is the same (and bounds checks are omitted are assumed to be outside the scope of the method per the docs).

Previously I was using `Consistent` instead of `Constant`. However [Go](https://golang.org/src/crypto/subtle/constant_time.go?s=490:531#L2) and various internet searches seem to associate `constant time` with this concept so I figured I would use the prevailing nomenclature ... do you have another suggestion?

This comment seems to be related to https://github.com/netty/netty/pull/5446#discussion_r68375984. lets discuss their.

The name constant implies that the contents of the array does not affect the time it takes to process.  There are always going to be compiler tricks or processor tricks or OS tricks that will mess with the timing.  The important thing is to not have different behavior based on the contents.  That's where the "constant" comes from.

That said, to @buchgr's comment, I think you may still need to do a bounds check.   Something like bytes1.length - startPos1 == bytes2.length - start2Pos.

> I think you may still need to do a bounds check. Something like bytes1.length - startPos1 == bytes2.length - start2Pos.

The bounds check is done through the length check. The "no bounds checking behavior" is also specified in the [javadocs](https://github.com/netty/netty/pull/5446/files#diff-ea8860513cb8af4c4392d1e295326fc6R639), PlatformDependent/ConstantTimeUtils are part of the internal API, and this behavior is consistent with [PlatformDependent.equals](https://github.com/netty/netty/blame/4.1/common/src/main/java/io/netty/util/internal/PlatformDependent.java#L625).

Sorry to be nitpicky, but my intuition says that this will be slower than the forward path just because it would be easier for the cache to take advantage of this.  

Also, how are you sure that byte arrays are word aligned?  Doing an unaligned access is pretty slow.  Arrays that are stack allocated may not have the same alignment guarantees as heap allocated.  

Is there benchmarking for this method?  

And fyi, I am proposing a similar change for Go: https://go-review.googlesource.com/#/c/24422/1/src/crypto/subtle/constant_time.go

> Sorry to be nitpicky, but my intuition says that this will be slower than the forward path just because it would be easier for the cache to take advantage of this.
> 
> Is there benchmarking for this method?

`PlatformDependentBenchmark` exists which I will run for a before/after. This was shown to provide benefits on smaller inputs when running benchmarks on `equalsConstantTime`. The overhead of allocating `i`, `j`, and `end` can be avoided for smaller inputs that don't need these variables.

> Also, how are you sure that byte arrays are word aligned?

`PlatformDependent.equalsConstantTime` checks if aligned access is allowed in general, but no check is done on the individual arrays. Do you know how I would check, and an example allocation which I can use to verify this method?

@carl-mastrangelo - Here are the results of `PlatformDependentBenchmark`. I switched the measurement to average time and added `1` for a size.

We gain on the smaller inputs, but start to perform worse around input size of `100`. However the gain may be negligible (or likely a loss) if there are larger headers involved ... let me revert this.

```
With this PR
Benchmark                                    (size)  Mode  Cnt     Score     Error  Units
PlatformDependentBenchmark.unsafeBytesEqual       1  avgt    5     4.453 ±   0.081  ns/op
PlatformDependentBenchmark.unsafeBytesEqual       7  avgt    5     4.756 ±   0.139  ns/op
PlatformDependentBenchmark.unsafeBytesEqual      10  avgt    5     5.493 ±   0.223  ns/op
PlatformDependentBenchmark.unsafeBytesEqual      50  avgt    5     9.630 ±   0.262  ns/op
PlatformDependentBenchmark.unsafeBytesEqual     100  avgt    5    13.559 ±   0.306  ns/op
PlatformDependentBenchmark.unsafeBytesEqual    1000  avgt    5   107.538 ±   1.410  ns/op
PlatformDependentBenchmark.unsafeBytesEqual   10000  avgt    5   995.796 ±  16.488  ns/op
PlatformDependentBenchmark.unsafeBytesEqual  100000  avgt    5  9942.613 ± 350.996  ns/op

Before This PR
Benchmark                                    (size)  Mode  Cnt     Score     Error  Units
PlatformDependentBenchmark.unsafeBytesEqual       1  avgt    5     4.906 ±   0.404  ns/op
PlatformDependentBenchmark.unsafeBytesEqual       7  avgt    5     5.469 ±   0.099  ns/op
PlatformDependentBenchmark.unsafeBytesEqual      10  avgt    5     6.051 ±   0.098  ns/op
PlatformDependentBenchmark.unsafeBytesEqual      50  avgt    5     9.634 ±   0.235  ns/op
PlatformDependentBenchmark.unsafeBytesEqual     100  avgt    5    12.056 ±   0.455  ns/op
PlatformDependentBenchmark.unsafeBytesEqual    1000  avgt    5    73.085 ±   1.784  ns/op
PlatformDependentBenchmark.unsafeBytesEqual   10000  avgt    5   649.883 ±  23.863  ns/op
PlatformDependentBenchmark.unsafeBytesEqual  100000  avgt    5  7254.138 ± 475.926  ns/op
```

@carl-mastrangelo - The following was collapsed but still open ...

> Also, how are you sure that byte arrays are word aligned?

`PlatformDependent.equalsConstantTime` checks if unaligned access is allowed in general, but no check is done on the individual arrays. Do you know how I would check, and an example allocation which I can use to verify this method?

> And fyi, I am proposing a similar change for Go: https://go-review.googlesource.com/#/c/24422/1/src/crypto/subtle/constant_time.go

I guess this would depend upon the answer to the first question ... maybe investigate this as a followup?

Not sure how you would check, but being able to do unaligned access has a noticeble performance degradation.  Intel lets you do it, but just does it slower.  (i.e. has to load two cache lines instead of one, and takes longer to go through the pipeline).  

The benchmark numbers on the Go version saw a boost (~460ns -> 320ns comparing two 4k buffers)  by having correct alignment.  I have no idea how Java tells you if something is aligned, since I don't know how the memory allocator works.  Since java has a compacting GC, any pointers to data are an extra level of indirection away right?

I think array contents on hotspot 64-bit intel should by default be 8 byte aligned. Due to compressed oops the array object is 8 byte aligned, followed by a 12 byte object header and the 4 byte array length, followed by array contents 😄 

> Since java has a compacting GC, any pointers to data are an extra level of indirection away right?

afaik the references to an object are updated when moved. so an array variable holds a pointer to the array contents (minus some offset for the object header + size).

That being said, apparently you can get the address of an object/array [somehow](http://hg.openjdk.java.net/code-tools/jol/file/30c3fbadf049/jol-samples/src/main/java/org/openjdk/jol/samples/JOLSample_17_Allocation.java#l64) (best guess via Unsafe)

However, since java GC can relocate an object between getting the address and doing the comparison, you might never know whether it's the right address at the time of comparison :-).

I think the whole complexity might not be worth it, especially since for headers we are likely not comparing 4K buffers but a few dozen bytes at a time.

@buchgr - Thanks for the details. I agree it doesn't seem practical to do this in java and may be more trouble than it is worth for this use case anyways.

@buchgr are you sure it has the same alignment, even when the array is stack allocated due to escape analysis?  Also, there were still about ~12% perf gain by using aligned access.  Whether or not this matters is debatable.


Patch that resolved the issue:
diff --git a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/Encoder.java b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/Encoder.java
index abc2948a451..ba0aa01bc28 100644
--- a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/Encoder.java
+++ b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/Encoder.java
@@ -40,6 +40,7 @@
 import static io.netty.handler.codec.http2.internal.hpack.HpackUtil.IndexType.INCREMENTAL;
 import static io.netty.handler.codec.http2.internal.hpack.HpackUtil.IndexType.NEVER;
 import static io.netty.handler.codec.http2.internal.hpack.HpackUtil.IndexType.NONE;
+import static io.netty.handler.codec.http2.internal.hpack.HpackUtil.equalsConstantTime;
 
 public final class Encoder {
 
@@ -304,9 +305,8 @@ private HeaderEntry getEntry(CharSequence name, CharSequence value) {
         int h = hash(name);
         int i = index(h);
         for (HeaderEntry e = headerFields[i]; e != null; e = e.next) {
-            if (e.hash == h &&
-                    HpackUtil.equals(name, e.name) &&
-                    HpackUtil.equals(value, e.value)) {
+            // To avoid short circuit behavior a bitwise operator is used instead of a boolean operator.
+            if (e.hash == h && (equalsConstantTime(name, e.name) & equalsConstantTime(value, e.value)) != 0) {
                 return e;
             }
         }
@@ -325,7 +325,7 @@ private int getIndex(CharSequence name) {
         int i = index(h);
         int index = -1;
         for (HeaderEntry e = headerFields[i]; e != null; e = e.next) {
-            if (e.hash == h && HpackUtil.equals(name, e.name)) {
+            if (e.hash == h && equalsConstantTime(name, e.name) != 0) {
                 index = e.index;
                 break;
             }
diff --git a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HeaderField.java b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HeaderField.java
index 41b82436be7..5c57037434b 100644
--- a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HeaderField.java
+++ b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HeaderField.java
@@ -31,6 +31,7 @@
  */
 package io.netty.handler.codec.http2.internal.hpack;
 
+import static io.netty.handler.codec.http2.internal.hpack.HpackUtil.equalsConstantTime;
 import static io.netty.util.internal.ObjectUtil.checkNotNull;
 
 class HeaderField {
@@ -72,9 +73,8 @@ public boolean equals(Object obj) {
             return false;
         }
         HeaderField other = (HeaderField) obj;
-        boolean nameEquals = HpackUtil.equals(name, other.name);
-        boolean valueEquals = HpackUtil.equals(value, other.value);
-        return nameEquals && valueEquals;
+        // To avoid short circuit behavior a bitwise operator is used instead of a boolean operator.
+        return (equalsConstantTime(name, other.name) & equalsConstantTime(value, other.value)) != 0;
     }
 
     @Override
diff --git a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HpackUtil.java b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HpackUtil.java
index 620ea2f43a6..658b422abe3 100644
--- a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HpackUtil.java
+++ b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/HpackUtil.java
@@ -31,19 +31,38 @@
  */
 package io.netty.handler.codec.http2.internal.hpack;
 
+import io.netty.util.AsciiString;
+import io.netty.util.internal.ConstantTimeUtils;
+import io.netty.util.internal.PlatformDependent;
+
 final class HpackUtil {
     /**
-     * A string compare that doesn't leak timing information.
+     * Compare two {@link CharSequence} objects without leaking timing information.
+     * <p>
+     * The {@code int} return type is intentional and is designed to allow cascading of constant time operations:
+     * <pre>
+     *     String s1 = "foo";
+     *     String s2 = "foo";
+     *     String s3 = "foo";
+     *     String s4 = "goo";
+     *     boolean equals = (equalsConstantTime(s1, s2) & equalsConstantTime(s3, s4)) != 0;
+     * </pre>
+     * @param s1 the first value.
+     * @param s2 the second value.
+     * @return {@code 0} if not equal. {@code 1} if equal.
      */
-    static boolean equals(CharSequence s1, CharSequence s2) {
-        if (s1.length() != s2.length()) {
-            return false;
-        }
-        char c = 0;
-        for (int i = 0; i < s1.length(); i++) {
-            c |= s1.charAt(i) ^ s2.charAt(i);
+    static int equalsConstantTime(CharSequence s1, CharSequence s2) {
+        if (s1 instanceof AsciiString && s2 instanceof AsciiString) {
+            if (s1.length() != s2.length()) {
+                return 0;
+            }
+            AsciiString s1Ascii = (AsciiString) s1;
+            AsciiString s2Ascii = (AsciiString) s2;
+            return PlatformDependent.equalsConstantTime(s1Ascii.array(), s1Ascii.arrayOffset(),
+                                                        s2Ascii.array(), s2Ascii.arrayOffset(), s1.length());
         }
-        return c == 0;
+
+        return ConstantTimeUtils.equalsConstantTime(s1, s2);
     }
 
     // Section 6.2. Literal Header Field Representation
diff --git a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/StaticTable.java b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/StaticTable.java
index bf1aa70fb61..b95a2a2f0ed 100644
--- a/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/StaticTable.java
+++ b/codec-http2/src/main/java/io/netty/handler/codec/http2/internal/hpack/StaticTable.java
@@ -38,6 +38,8 @@
 import java.util.Arrays;
 import java.util.List;
 
+import static io.netty.handler.codec.http2.internal.hpack.HpackUtil.equalsConstantTime;
+
 final class StaticTable {
 
     // Appendix A: Static Table
@@ -153,10 +155,10 @@ static int getIndex(CharSequence name, CharSequence value) {
         // Note this assumes all entries for a given header field are sequential.
         while (index <= length) {
             HeaderField entry = getEntry(index);
-            if (!HpackUtil.equals(name, entry.name)) {
+            if (equalsConstantTime(name, entry.name) == 0) {
                 break;
             }
-            if (HpackUtil.equals(value, entry.value)) {
+            if (equalsConstantTime(value, entry.value) != 0) {
                 return index;
             }
             index++;
diff --git a/common/src/main/java/io/netty/util/internal/ConstantTimeUtils.java b/common/src/main/java/io/netty/util/internal/ConstantTimeUtils.java
new file mode 100644
index 00000000000..8bddb629e49
--- /dev/null
+++ b/common/src/main/java/io/netty/util/internal/ConstantTimeUtils.java
@@ -0,0 +1,131 @@
+/*
+ * Copyright 2016 The Netty Project
+ *
+ * The Netty Project licenses this file to you under the Apache License,
+ * version 2.0 (the "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at:
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+package io.netty.util.internal;
+
+public final class ConstantTimeUtils {
+    private ConstantTimeUtils() { }
+
+    /**
+     * Compare two {@code int}s without leaking timing information.
+     * <p>
+     * The {@code int} return type is intentional and is designed to allow cascading of constant time operations:
+     * <pre>
+     *     int v1 = 1;
+     *     int v1 = 1;
+     *     int v1 = 1;
+     *     int v1 = 500;
+     *     boolean equals = (equalsConstantTime(l1, l2) & equalsConstantTime(l3, l4)) != 0;
+     * </pre>
+     * @param x the first value.
+     * @param y the second value.
+     * @return {@code 0} if not equal. {@code 1} if equal.
+     */
+    public static int equalsConstantTime(int x, int y) {
+        int z = -1 ^ (x ^ y);
+        z &= z >> 16;
+        z &= z >> 8;
+        z &= z >> 4;
+        z &= z >> 2;
+        z &= z >> 1;
+        return z & 1;
+    }
+
+    /**
+     * Compare two {@code longs}s without leaking timing information.
+     * <p>
+     * The {@code int} return type is intentional and is designed to allow cascading of constant time operations:
+     * <pre>
+     *     long v1 = 1;
+     *     long v1 = 1;
+     *     long v1 = 1;
+     *     long v1 = 500;
+     *     boolean equals = (equalsConstantTime(l1, l2) & equalsConstantTime(l3, l4)) != 0;
+     * </pre>
+     * @param x the first value.
+     * @param y the second value.
+     * @return {@code 0} if not equal. {@code 1} if equal.
+     */
+    public static int equalsConstantTime(long x, long y) {
+        long z = -1L ^ (x ^ y);
+        z &= z >> 32;
+        z &= z >> 16;
+        z &= z >> 8;
+        z &= z >> 4;
+        z &= z >> 2;
+        z &= z >> 1;
+        return (int) (z & 1);
+    }
+
+    /**
+     * Compare two {@code byte} arrays for equality without leaking timing information.
+     * For performance reasons no bounds checking on the parameters is performed.
+     * <p>
+     * The {@code int} return type is intentional and is designed to allow cascading of constant time operations:
+     * <pre>
+     *     byte[] s1 = new {1, 2, 3};
+     *     byte[] s2 = new {1, 2, 3};
+     *     byte[] s3 = new {1, 2, 3};
+     *     byte[] s4 = new {4, 5, 6};
+     *     boolean equals = (equalsConstantTime(s1, 0, s2, 0, s1.length) &
+     *                       equalsConstantTime(s3, 0, s4, 0, s3.length)) != 0;
+     * </pre>
+     * @param bytes1 the first byte array.
+     * @param startPos1 the position (inclusive) to start comparing in {@code bytes1}.
+     * @param bytes2 the second byte array.
+     * @param startPos2 the position (inclusive) to start comparing in {@code bytes2}.
+     * @param length the amount of bytes to compare. This is assumed to be validated as not going out of bounds
+     * by the caller.
+     * @return {@code 0} if not equal. {@code 1} if equal.
+     */
+    public static int equalsConstantTime(byte[] bytes1, int startPos1,
+                                         byte[] bytes2, int startPos2, int length) {
+        // Benchmarking demonstrates that using an int to accumulate is faster than other data types.
+        int b = 0;
+        final int end = startPos1 + length;
+        for (int i = startPos1, j = startPos2; i < end; ++i, ++j) {
+            b |= bytes1[i] ^ bytes2[j];
+        }
+        return equalsConstantTime(b, 0);
+    }
+
+    /**
+     * Compare two {@link CharSequence} objects without leaking timing information.
+     * <p>
+     * The {@code int} return type is intentional and is designed to allow cascading of constant time operations:
+     * <pre>
+     *     String s1 = "foo";
+     *     String s2 = "foo";
+     *     String s3 = "foo";
+     *     String s4 = "goo";
+     *     boolean equals = (equalsConstantTime(s1, s2) & equalsConstantTime(s3, s4)) != 0;
+     * </pre>
+     * @param s1 the first value.
+     * @param s2 the second value.
+     * @return {@code 0} if not equal. {@code 1} if equal.
+     */
+    public static int equalsConstantTime(CharSequence s1, CharSequence s2) {
+        if (s1.length() != s2.length()) {
+            return 0;
+        }
+
+        // Benchmarking demonstrates that using an int to accumulate is faster than other data types.
+        int c = 0;
+        for (int i = 0; i < s1.length(); ++i) {
+            c |= s1.charAt(i) ^ s2.charAt(i);
+        }
+        return equalsConstantTime(c, 0);
+    }
+}
diff --git a/common/src/main/java/io/netty/util/internal/PlatformDependent.java b/common/src/main/java/io/netty/util/internal/PlatformDependent.java
index 47d054c0d03..361e1ca1422 100644
--- a/common/src/main/java/io/netty/util/internal/PlatformDependent.java
+++ b/common/src/main/java/io/netty/util/internal/PlatformDependent.java
@@ -59,6 +59,7 @@
 import static io.netty.util.internal.PlatformDependent0.hashCodeAsciiCompute;
 import static io.netty.util.internal.PlatformDependent0.hashCodeAsciiSanitize;
 import static io.netty.util.internal.PlatformDependent0.hashCodeAsciiSanitizeAsByte;
+import static io.netty.util.internal.PlatformDependent0.unalignedAccess;
 
 /**
  * Utility that detects various properties specific to the current runtime
@@ -633,10 +634,36 @@ public static boolean useDirectBufferNoCleaner() {
      * by the caller.
      */
     public static boolean equals(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2, int length) {
-        if (!hasUnsafe() || !PlatformDependent0.unalignedAccess()) {
-            return equalsSafe(bytes1, startPos1, bytes2, startPos2, length);
-        }
-        return PlatformDependent0.equals(bytes1, startPos1, bytes2, startPos2, length);
+        return !hasUnsafe() || !unalignedAccess() ?
+                  equalsSafe(bytes1, startPos1, bytes2, startPos2, length) :
+                  PlatformDependent0.equals(bytes1, startPos1, bytes2, startPos2, length);
+    }
+
+    /**
+     * Compare two {@code byte} arrays for equality without leaking timing information.
+     * For performance reasons no bounds checking on the parameters is performed.
+     * <p>
+     * The {@code int} return type is intentional and is designed to allow cascading of constant time operations:
+     * <pre>
+     *     byte[] s1 = new {1, 2, 3};
+     *     byte[] s2 = new {1, 2, 3};
+     *     byte[] s3 = new {1, 2, 3};
+     *     byte[] s4 = new {4, 5, 6};
+     *     boolean equals = (equalsConstantTime(s1, 0, s2, 0, s1.length) &
+     *                       equalsConstantTime(s3, 0, s4, 0, s3.length)) != 0;
+     * </pre>
+     * @param bytes1 the first byte array.
+     * @param startPos1 the position (inclusive) to start comparing in {@code bytes1}.
+     * @param bytes2 the second byte array.
+     * @param startPos2 the position (inclusive) to start comparing in {@code bytes2}.
+     * @param length the amount of bytes to compare. This is assumed to be validated as not going out of bounds
+     * by the caller.
+     * @return {@code 0} if not equal. {@code 1} if equal.
+     */
+    public static int equalsConstantTime(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2, int length) {
+        return !hasUnsafe() || !unalignedAccess() ?
+                  ConstantTimeUtils.equalsConstantTime(bytes1, startPos1, bytes2, startPos2, length) :
+                  PlatformDependent0.equalsConstantTime(bytes1, startPos1, bytes2, startPos2, length);
     }
 
     /**
@@ -649,7 +676,7 @@ public static boolean equals(byte[] bytes1, int startPos1, byte[] bytes2, int st
      * The resulting hash code will be case insensitive.
      */
     public static int hashCodeAscii(byte[] bytes, int startPos, int length) {
-        if (!hasUnsafe() || !PlatformDependent0.unalignedAccess()) {
+        if (!hasUnsafe() || !unalignedAccess()) {
             return hashCodeAsciiSafe(bytes, startPos, length);
         }
         return PlatformDependent0.hashCodeAscii(bytes, startPos, length);
@@ -666,7 +693,7 @@ public static int hashCodeAscii(byte[] bytes, int startPos, int length) {
      * The resulting hash code will be case insensitive.
      */
     public static int hashCodeAscii(CharSequence bytes) {
-        if (!hasUnsafe() || !PlatformDependent0.unalignedAccess()) {
+        if (!hasUnsafe() || !unalignedAccess()) {
             return hashCodeAsciiSafe(bytes);
         } else if (PlatformDependent0.hasCharArray(bytes)) {
             return PlatformDependent0.hashCodeAscii(PlatformDependent0.charArray(bytes));
diff --git a/common/src/main/java/io/netty/util/internal/PlatformDependent0.java b/common/src/main/java/io/netty/util/internal/PlatformDependent0.java
index 98801528fd1..c6266fe898a 100644
--- a/common/src/main/java/io/netty/util/internal/PlatformDependent0.java
+++ b/common/src/main/java/io/netty/util/internal/PlatformDependent0.java
@@ -381,9 +381,6 @@ static void setMemory(Object o, long offset, long bytes, byte value) {
     }
 
     static boolean equals(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2, int length) {
-        if (length == 0) {
-            return true;
-        }
         final long baseOffset1 = BYTE_ARRAY_BASE_OFFSET + startPos1;
         final long baseOffset2 = BYTE_ARRAY_BASE_OFFSET + startPos2;
         final int remainingBytes = length & 7;
@@ -418,6 +415,47 @@ static boolean equals(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2
         }
     }
 
+    static int equalsConstantTime(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2, int length) {
+        long result = 0;
+        final long baseOffset1 = BYTE_ARRAY_BASE_OFFSET + startPos1;
+        final long baseOffset2 = BYTE_ARRAY_BASE_OFFSET + startPos2;
+        final int remainingBytes = length & 7;
+        final long end = baseOffset1 + remainingBytes;
+        for (long i = baseOffset1 - 8 + length, j = baseOffset2 - 8 + length; i >= end; i -= 8, j -= 8) {
+            result |= UNSAFE.getLong(bytes1, i) ^ UNSAFE.getLong(bytes2, j);
+        }
+        switch (remainingBytes) {
+            case 7:
+                return ConstantTimeUtils.equalsConstantTime(result |
+                        (UNSAFE.getInt(bytes1, baseOffset1 + 3) ^ UNSAFE.getInt(bytes2, baseOffset2 + 3)) |
+                        (UNSAFE.getChar(bytes1, baseOffset1 + 1) ^ UNSAFE.getChar(bytes2, baseOffset2 + 1)) |
+                        (UNSAFE.getByte(bytes1, baseOffset1) ^ UNSAFE.getByte(bytes2, baseOffset2)), 0);
+            case 6:
+                return ConstantTimeUtils.equalsConstantTime(result |
+                        (UNSAFE.getInt(bytes1, baseOffset1 + 2) ^ UNSAFE.getInt(bytes2, baseOffset2 + 2)) |
+                        (UNSAFE.getChar(bytes1, baseOffset1) ^ UNSAFE.getChar(bytes2, baseOffset2)), 0);
+            case 5:
+                return ConstantTimeUtils.equalsConstantTime(result |
+                        (UNSAFE.getInt(bytes1, baseOffset1 + 1) ^ UNSAFE.getInt(bytes2, baseOffset2 + 1)) |
+                        (UNSAFE.getByte(bytes1, baseOffset1) ^ UNSAFE.getByte(bytes2, baseOffset2)), 0);
+            case 4:
+                return ConstantTimeUtils.equalsConstantTime(result |
+                        (UNSAFE.getInt(bytes1, baseOffset1) ^ UNSAFE.getInt(bytes2, baseOffset2)), 0);
+            case 3:
+                return ConstantTimeUtils.equalsConstantTime(result |
+                        (UNSAFE.getChar(bytes1, baseOffset1 + 1) ^ UNSAFE.getChar(bytes2, baseOffset2 + 1)) |
+                        (UNSAFE.getByte(bytes1, baseOffset1) ^ UNSAFE.getByte(bytes2, baseOffset2)), 0);
+            case 2:
+                return ConstantTimeUtils.equalsConstantTime(result |
+                        (UNSAFE.getChar(bytes1, baseOffset1) ^ UNSAFE.getChar(bytes2, baseOffset2)), 0);
+            case 1:
+                return ConstantTimeUtils.equalsConstantTime(result |
+                        (UNSAFE.getByte(bytes1, baseOffset1) ^ UNSAFE.getByte(bytes2, baseOffset2)), 0);
+            default:
+                return ConstantTimeUtils.equalsConstantTime(result, 0);
+        }
+    }
+
     static int hashCodeAscii(byte[] bytes) {
         return hashCodeAscii(bytes, 0, bytes.length);
     }
diff --git a/microbench/src/main/java/io/netty/microbench/http2/internal/hpack/HpackUtilBenchmark.java b/microbench/src/main/java/io/netty/microbench/http2/internal/hpack/HpackUtilBenchmark.java
new file mode 100644
index 00000000000..2adf73566f2
--- /dev/null
+++ b/microbench/src/main/java/io/netty/microbench/http2/internal/hpack/HpackUtilBenchmark.java
@@ -0,0 +1,94 @@
+/*
+ * Copyright 2016 The Netty Project
+ *
+ * The Netty Project licenses this file to you under the Apache License,
+ * version 2.0 (the "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at:
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations
+ * under the License.
+ */
+package io.netty.microbench.http2.internal.hpack;
+
+import io.netty.microbench.util.AbstractMicrobenchmark;
+import io.netty.util.AsciiString;
+import io.netty.util.internal.ConstantTimeUtils;
+import io.netty.util.internal.PlatformDependent;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.Threads;
+import org.openjdk.jmh.annotations.Warmup;
+
+import java.util.List;
+
+@Threads(1)
+@Warmup(iterations = 5)
+@Measurement(iterations = 5)
+public class HpackUtilBenchmark extends AbstractMicrobenchmark {
+    @Param
+    public HeadersSize size;
+
+    private List<Header> headers;
+
+    @Setup(Level.Trial)
+    public void setup() {
+        headers = Util.headers(size, false);
+    }
+
+    @Benchmark
+    public int oldEquals() {
+        int count = 0;
+        for (int i = 0; i < headers.size(); ++i) {
+            Header header = headers.get(i);
+            if (oldEquals(header.name, header.name)) {
+                ++count;
+            }
+        }
+        return count;
+    }
+
+    @Benchmark
+    public int newEquals() {
+        int count = 0;
+        for (int i = 0; i < headers.size(); ++i) {
+            Header header = headers.get(i);
+            if (newEquals(header.name, header.name)) {
+                ++count;
+            }
+        }
+        return count;
+    }
+
+    private static boolean oldEquals(CharSequence s1, CharSequence s2) {
+        if (s1.length() != s2.length()) {
+            return false;
+        }
+        char c = 0;
+        for (int i = 0; i < s1.length(); i++) {
+            c |= s1.charAt(i) ^ s2.charAt(i);
+        }
+        return c == 0;
+    }
+
+    private static boolean newEquals(CharSequence s1, CharSequence s2) {
+        if (s1 instanceof AsciiString && s2 instanceof AsciiString) {
+            if (s1.length() != s2.length()) {
+                return false;
+            }
+            AsciiString s1Ascii = (AsciiString) s1;
+            AsciiString s2Ascii = (AsciiString) s2;
+            return PlatformDependent.equalsConstantTime(s1Ascii.array(), s1Ascii.arrayOffset(),
+                                                        s2Ascii.array(), s2Ascii.arrayOffset(), s1.length()) != 0;
+        }
+
+        return ConstantTimeUtils.equalsConstantTime(s1, s2) != 0;
+    }
+}


Test patch:
diff --git a/common/src/test/java/io/netty/util/internal/PlatformDependentTest.java b/common/src/test/java/io/netty/util/internal/PlatformDependentTest.java
index b31e36c0086..53ea6a846f6 100644
--- a/common/src/test/java/io/netty/util/internal/PlatformDependentTest.java
+++ b/common/src/test/java/io/netty/util/internal/PlatformDependentTest.java
@@ -19,6 +19,8 @@
 
 import java.util.Random;
 
+import static io.netty.util.internal.PlatformDependent.hashCodeAscii;
+import static io.netty.util.internal.PlatformDependent.hashCodeAsciiSafe;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotSame;
@@ -26,34 +28,57 @@
 
 public class PlatformDependentTest {
     private static final Random r = new Random();
+    @Test
+    public void testEqualsConsistentTime() {
+        testEquals(new EqualityChecker() {
+            @Override
+            public boolean equals(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2, int length) {
+                return PlatformDependent.equalsConstantTime(bytes1, startPos1, bytes2, startPos2, length) != 0;
+            }
+        });
+    }
+
     @Test
     public void testEquals() {
+        testEquals(new EqualityChecker() {
+            @Override
+            public boolean equals(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2, int length) {
+                return PlatformDependent.equals(bytes1, startPos1, bytes2, startPos2, length);
+            }
+        });
+    }
+
+    private interface EqualityChecker {
+        boolean equals(byte[] bytes1, int startPos1, byte[] bytes2, int startPos2, int length);
+    }
+
+    private void testEquals(EqualityChecker equalsChecker) {
         byte[] bytes1 = {'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd'};
         byte[] bytes2 = {'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd'};
         assertNotSame(bytes1, bytes2);
-        assertTrue(PlatformDependent.equals(bytes1, 0, bytes2, 0, bytes1.length));
-        assertTrue(PlatformDependent.equals(bytes1, 2, bytes2, 2, bytes1.length - 2));
+        assertTrue(equalsChecker.equals(bytes1, 0, bytes2, 0, bytes1.length));
+        assertTrue(equalsChecker.equals(bytes1, 2, bytes2, 2, bytes1.length - 2));
 
         bytes1 = new byte[] {1, 2, 3, 4, 5, 6};
         bytes2 = new byte[] {1, 2, 3, 4, 5, 6, 7};
         assertNotSame(bytes1, bytes2);
-        assertFalse(PlatformDependent.equals(bytes1, 0, bytes2, 1, bytes1.length));
-        assertTrue(PlatformDependent.equals(bytes2, 0, bytes1, 0, bytes1.length));
+        assertFalse(equalsChecker.equals(bytes1, 0, bytes2, 1, bytes1.length));
+        assertTrue(equalsChecker.equals(bytes2, 0, bytes1, 0, bytes1.length));
 
         bytes1 = new byte[] {1, 2, 3, 4};
         bytes2 = new byte[] {1, 2, 3, 5};
-        assertFalse(PlatformDependent.equals(bytes1, 0, bytes2, 0, bytes1.length));
-        assertTrue(PlatformDependent.equals(bytes1, 0, bytes2, 0, 3));
+        assertFalse(equalsChecker.equals(bytes1, 0, bytes2, 0, bytes1.length));
+        assertTrue(equalsChecker.equals(bytes1, 0, bytes2, 0, 3));
 
         bytes1 = new byte[] {1, 2, 3, 4};
         bytes2 = new byte[] {1, 3, 3, 4};
-        assertFalse(PlatformDependent.equals(bytes1, 0, bytes2, 0, bytes1.length));
-        assertTrue(PlatformDependent.equals(bytes1, 2, bytes2, 2, bytes1.length - 2));
+        assertFalse(equalsChecker.equals(bytes1, 0, bytes2, 0, bytes1.length));
+        assertTrue(equalsChecker.equals(bytes1, 2, bytes2, 2, bytes1.length - 2));
 
         bytes1 = new byte[0];
         bytes2 = new byte[0];
         assertNotSame(bytes1, bytes2);
-        assertTrue(PlatformDependent.equals(bytes1, 0, bytes2, 0, 0));
+        assertTrue(equalsChecker.equals(bytes1, 0, bytes2, 0, 0));
 
         bytes1 = new byte[100];
         bytes2 = new byte[100];
@@ -61,23 +86,23 @@ public void testEquals() {
             bytes1[i] = (byte) i;
             bytes2[i] = (byte) i;
         }
-        assertTrue(PlatformDependent.equals(bytes1, 0, bytes2, 0, bytes1.length));
+        assertTrue(equalsChecker.equals(bytes1, 0, bytes2, 0, bytes1.length));
         bytes1[50] = 0;
-        assertFalse(PlatformDependent.equals(bytes1, 0, bytes2, 0, bytes1.length));
-        assertTrue(PlatformDependent.equals(bytes1, 51, bytes2, 51, bytes1.length - 51));
-        assertTrue(PlatformDependent.equals(bytes1, 0, bytes2, 0, 50));
+        assertFalse(equalsChecker.equals(bytes1, 0, bytes2, 0, bytes1.length));
+        assertTrue(equalsChecker.equals(bytes1, 51, bytes2, 51, bytes1.length - 51));
+        assertTrue(equalsChecker.equals(bytes1, 0, bytes2, 0, 50));
 
         bytes1 = new byte[]{1, 2, 3, 4, 5};
         bytes2 = new byte[]{3, 4, 5};
-        assertFalse(PlatformDependent.equals(bytes1, 0, bytes2, 0, bytes2.length));
-        assertTrue(PlatformDependent.equals(bytes1, 2, bytes2, 0, bytes2.length));
-        assertTrue(PlatformDependent.equals(bytes2, 0, bytes1, 2, bytes2.length));
+        assertFalse(equalsChecker.equals(bytes1, 0, bytes2, 0, bytes2.length));
+        assertTrue(equalsChecker.equals(bytes1, 2, bytes2, 0, bytes2.length));
+        assertTrue(equalsChecker.equals(bytes2, 0, bytes1, 2, bytes2.length));
 
         for (int i = 0; i < 1000; ++i) {
             bytes1 = new byte[i];
             r.nextBytes(bytes1);
             bytes2 = bytes1.clone();
-            assertTrue(PlatformDependent.equals(bytes1, 0, bytes2, 0, bytes1.length));
+            assertTrue(equalsChecker.equals(bytes1, 0, bytes2, 0, bytes1.length));
         }
     }
 
@@ -97,14 +122,14 @@ public void testHashCodeAscii() {
             }
             String string = new String(bytesChar);
             assertEquals("length=" + i,
-                         PlatformDependent.hashCodeAsciiSafe(bytes, 0, bytes.length),
-                         PlatformDependent.hashCodeAscii(bytes, 0, bytes.length));
+                         hashCodeAsciiSafe(bytes, 0, bytes.length),
+                         hashCodeAscii(bytes, 0, bytes.length));
             assertEquals("length=" + i,
-                    PlatformDependent.hashCodeAsciiSafe(string),
-                    PlatformDependent.hashCodeAscii(string));
+                    hashCodeAsciiSafe(string),
+                    hashCodeAscii(string));
             assertEquals("length=" + i,
-                    PlatformDependent.hashCodeAscii(bytes, 0, bytes.length),
-                    PlatformDependent.hashCodeAscii(string));
+                    hashCodeAscii(bytes, 0, bytes.length),
+                    hashCodeAscii(string));
         }
     }
 }