Use a more compact HSTS representation.

Use a more compact HSTS representation.

The current, preloaded HSTS table is nearly 80KB now. We match it linearly so
we trash the D1 cache with it for every lookup. Additionally, we have to do
multiple passes through it, removing a label from the target each time.

This changes the HSTS information to be a trie. The trie only consumes about
10KB and only a single lookup is needed for a given hostname since the
organisation of the trie means that all matches (from least to most specific)
for a given hostname will be found with a single walk.

BUG=none
R=palmer@chromium.org

Committed: https://chromium.googlesource.com/chromium/src/+/0653ece4f182ab947d6809c311dfd4e8febaee1f

[agl, 2014-09-29 23:25:12]

agl@chromium.org changed reviewers:
+ palmer@chromium.org

[agl, 2014-10-02 19:20:35]

ping, since you're back :)

[palmer, 2014-10-02 20:26:36]

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
File net/http/transport_security_state.cc (right):

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:276: BitReader(const uint8 *bytes, size_t
num_bits)
Style nit: "const uint8* bytes" (throughout).

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:306: for (unsigned i = 0; i < num_bits;
i++) {
Style nit: Chromium style is pre-increment (here and on 332).

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:359: uint8 current_;
Nit: I might name this |current_byte_|, and name |used_bytes_| to
|current_byte_index_| or similar, and name |current_used_| to
|number_of_bits_read_| or similar.

This is purely personal preference, but I like to obviate comments with concise
but explanatory identifier names.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:416: uint32 pinset_id;
Nit: Maybe we could pack this struct every-so-slightly tighter (on some
architectures).

struct PreloadResult {
  uint32 pinset_id;    // 0 means no pins.
  uint32 domain_id;
  size_t hostname_offset;
  bool include_subdomains;
  bool force_https;
};

This also might be pointless.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:424: // false on internal error and true
otherwise. After a successful return,
Would any internal errors be due to bugs? What are callers supposed to do when
this returns false?

Can we change the API to return a struct { bool success; const PreloadResult&
result } ? Or some C++ semblance of a Maybe type.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:436: // In the disable table, the zero
character represents the "end of string"
Typo: "dispatch table"?

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
File net/http/transport_security_state_static.h (right):

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state_static.h:686: static const uint8
kPreloadedHSTSData[] = {
I have no way of verifying this.

[palmer, 2014-10-02 21:55:50]

Can we write a program to turn the JSON into the trie at compile time? (Or at
least at Chrome startup time?) That would be better than the manual approach.

[agl, 2014-10-03 00:01:16]

On 2014/10/02 21:55:50, Chromium Palmer wrote:
> Can we write a program to turn the JSON into the trie at compile time? (Or at
> least at Chrome startup time?) That would be better than the manual approach.

We can't have Go code in the Chromium tree thus the generator lives on GitHub.

[agl, 2014-10-03 00:01:21]

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
File net/http/transport_security_state.cc (right):

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:276: BitReader(const uint8 *bytes, size_t
num_bits)
On 2014/10/02 20:26:36, Chromium Palmer wrote:
> Style nit: "const uint8* bytes" (throughout).

Done.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:306: for (unsigned i = 0; i < num_bits;
i++) {
On 2014/10/02 20:26:36, Chromium Palmer wrote:
> Style nit: Chromium style is pre-increment (here and on 332).

Done.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:359: uint8 current_;
On 2014/10/02 20:26:36, Chromium Palmer wrote:
> Nit: I might name this |current_byte_|, and name |used_bytes_| to
> |current_byte_index_| or similar, and name |current_used_| to
> |number_of_bits_read_| or similar.
> 
> This is purely personal preference, but I like to obviate comments with
concise
> but explanatory identifier names.

Done.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:416: uint32 pinset_id;
On 2014/10/02 20:26:35, Chromium Palmer wrote:
> Nit: Maybe we could pack this struct every-so-slightly tighter (on some
> architectures).
> 
> struct PreloadResult {
>   uint32 pinset_id;    // 0 means no pins.
>   uint32 domain_id;
>   size_t hostname_offset;
>   bool include_subdomains;
>   bool force_https;
> };
> 
> This also might be pointless.

I've moved the bools to the end but I don't think that having a magic value for
pinset_id is worth the savings.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:424: // false on internal error and true
otherwise. After a successful return,
On 2014/10/02 20:26:36, Chromium Palmer wrote:
> Would any internal errors be due to bugs? What are callers supposed to do when
> this returns false?

Log the fact, essentially. However, you're correct that's not helpful at the
callsites so I've renamed it DecodeHSTSPreloadRaw and wrapped it in
DecodeHSTSPreload, which handles the logging of internal errors and pretends
that nothing was found.

> 
> Can we change the API to return a struct { bool success; const PreloadResult&
> result } ? Or some C++ semblance of a Maybe type.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state.cc:436: // In the disable table, the zero
character represents the "end of string"
On 2014/10/02 20:26:35, Chromium Palmer wrote:
> Typo: "dispatch table"?

Done.

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
File net/http/transport_security_state_static.h (right):

https://codereview.chromium.org/619433002/diff/40001/net/http/transport_secur...
net/http/transport_security_state_static.h:686: static const uint8
kPreloadedHSTSData[] = {
On 2014/10/02 20:26:36, Chromium Palmer wrote:
> I have no way of verifying this.

The unittests pass :)

Also, see https://github.com/agl/transport-security-state-generate/tree/compact

[palmer, 2014-10-06 19:32:25]

Is it too onerous to reimplement the Go program in Python or C++ so that we can
have it in the Chromium tree?

If so, at least add a comment pointing to transport-security-state-generate in
the Chromium code.

[Daniel Bratell, 2014-10-06 20:09:41]

On 2014/10/06 19:32:25, Chromium Palmer wrote:
> Is it too onerous to reimplement the Go program in Python or C++ so that we
can
> have it in the Chromium tree?
> 
> If so, at least add a comment pointing to transport-security-state-generate in
> the Chromium code.

Quite a coincidence but I've spent some time today porting the generator to
python. It's not fully functioning yet and after finding this, I will put it on
hold until this has landed.

The main issue with doing it in Python is that Go has native X509 libs, while
Python "only" has third party libs which have no official backing. I've used
pyx509 and pyasn1 and I think it will work (but I need to extend pyx509 to be
able to extract rawSubjectPublicKeyInfo from the cert) but those will have to be
bundled with the generator.

[agl, 2014-10-06 21:08:54]

On 2014/10/06 19:32:25, Chromium Palmer wrote:
> Is it too onerous to reimplement the Go program in Python or C++ so that we
can
> have it in the Chromium tree?

I don't want to maintain a Python program, C++ would be mess because of X.509
processing and nor do I believe that the build needs to do this processing every
time.

> If so, at least add a comment pointing to transport-security-state-generate in
> the Chromium code.

Sure, done. It's just been that way since the beginning.

[palmer, 2014-10-07 19:10:50]

LGTM.

[agl, 2014-10-07 21:14:51]

The CQ bit was checked by agl@chromium.org

[commit-bot: I haz the power, 2014-10-07 21:17:17]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/619433002/100001

[commit-bot: I haz the power, 2014-10-07 21:28:20]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-10-07 21:28:21]

Try jobs failed on following builders:
  chromium_presubmit on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)

[commit-bot: I haz the power, 2014-10-07 21:52:32]

Patchset 6 (id:??) landed as
https://crrev.com/0653ece4f182ab947d6809c311dfd4e8febaee1f
Cr-Commit-Position: refs/heads/master@{#298580}

[agl, 2014-10-07 21:52:34]

Committed patchset #6 (id:100001) manually as
0653ece4f182ab947d6809c311dfd4e8febaee1f (presubmit successful).

[jamesr, 2014-10-08 00:50:59]

jamesr@chromium.org changed reviewers:
+ jamesr@chromium.org

[jamesr, 2014-10-08 00:51:01]

https://codereview.chromium.org/619433002/diff/100001/net/http/transport_secu...
File net/http/transport_security_state_static.h (right):

https://codereview.chromium.org/619433002/diff/100001/net/http/transport_secu...
net/http/transport_security_state_static.h:657: static const struct Pinset
kPinsets[] = {
this'll generate a static initializer, sadly