Reduce footprint of registry controlled domain table

net/base/registry_controlled_domains/registry_controlled_domain.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // NB: Modelled after Mozilla's code (originally written by Pamela Greene,
 // later modified by others), but almost entirely rewritten for Chrome.
 //   (netwerk/dns/src/nsEffectiveTLDService.cpp)
 /* ***** BEGIN LICENSE BLOCK *****
  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  *
@@ skipping 35 matching lines @@
 #include "net/base/registry_controlled_domains/registry_controlled_domain.h"
 
 #include "base/logging.h"
 #include "base/strings/string_util.h"
 #include "base/strings/utf_string_conversions.h"
 #include "net/base/net_module.h"
 #include "net/base/net_util.h"
 #include "url/gurl.h"
 #include "url/url_parse.h"
 
-#include "effective_tld_names.cc"
-
 namespace net {
 namespace registry_controlled_domains {
 
 namespace {
+#include "effective_tld_names-inc.cc"
+
+// See make_dafsa.py for documentation of the generated dafsa byte array.
+
+const unsigned char* graph = kDafsa;
+
+int LookupString(const unsigned char* pos, const char* key, int length) {

[Ryan Sleevi, 2014/03/19 03:08:32]

1) Needs documentation
2) int for byte length = better to use size_t here
3) Would it make more sense to use a StringPeice, which will get optimized out.

+  const char* end = key + length;
+  while (true) {
+    // Read links.
+    const unsigned char* child = pos;

[Ryan Sleevi, 2014/03/18 01:23:58]

Generally speaking, this level of manual string manipulation scares the crap out
of me.

I just mention it because it's going to take me a lot more time to reason about
the security on, even if it's (probably) correct.

That said, the use of magic values here (0x60, 0x40, 0x80, 0x0F) would all be
better if given symbolic names, and documented heavily within this code

const char kTerminalNodeMask = 0x80;
const char kOffsetLengthMask = 0x60;
const char kOffsetMask = 0x1F;

etc

+    while (true) {
+      bool is_last = (*pos & 0x80) != 0;

[Ryan Sleevi, 2014/03/19 03:08:32]

Normally within net/ we encapsulate a lot of the string parsing within iterators
(see header parsing, header value parsing, etc)

The optimizer should optimize it out all the same, but it makes it easier to
read.

For example, you could create an iterator to read links, where the returned type
can provide disambiguation about end of key, child, etc.

Examples:
see
https://code.google.com/p/chromium/codesearch#chromium/src/net/http/http_util...
https://code.google.com/p/chromium/codesearch#chromium/src/net/http/http_util...
https://code.google.com/p/chromium/codesearch#chromium/src/net/http/http_requ...

[Olle Liljenzin, 2014/03/19 14:19:42]

Iterators may increase readability by adding a familiar interface on the
implementation. But I can't see how it would fit here. E.g. reading a link has
side effects (both pos and child pointers are incremented), and hiding that in
an overloaded operator or GetNext() method would not make the code easier to
read. The current code does not contain repeated patterns and adding abstraction
layers will then just blow up code size and split the implementation on
different locations, making it harder to follow what really happens in case of
debugging.

The code is also extremely performance sensitive and compilers are far from
perfect. In case the compiler (on some platform) fails to reduce some redundant
instructions we will have to read the assembler code to find out where it
failed.

The current code is just about 50-60 statements (not counting white space and
comments), and I would prefer to not make it much larger.

+      switch (*pos & 0x60) {
+        case 0x60:  // Read three byte offset
+          child += ((pos[0] & 0x1F) << 16) | (pos[1] << 8) | pos[2];
+          pos += 3;
+          break;
+
+        case 0x40:  // Read two byte offset
+          child += ((pos[0] & 0x1F) << 8) | pos[1];
+          pos += 2;
+          break;
+
+        default:  // Read one byte offset
+          child += pos[0] & 0x3F;
+          pos += 1;
+      }
+      if (key == end) {
+        // End of key reached. A matching child node must be labeled by a
+        // single byte in range 0x80-0x9F encoding the return value.

[Ryan Sleevi, 2014/03/29 02:14:29]

As a justification for why we need to split this code into something more
readable - it took me way too long to figure out whether the comment was correct
and the code was wrong, or whether the code was correct and the comment wrong.

In this case, it's the latter. It's a single byte in the range 0x80 - 0x8F, as
reflected in the comments for make_dafsa.py

+        if (!(*child & 0x60)) {
+          // A return value must always be last in a label. If not the byte
+          // array is corrupt.
+          DCHECK(*child & 0x80);
+
+          // Extract return value.
+          return *child & 0x0F;
+        }
+        // The key matches and is exhausted, but child has more characters.
+        if (is_last) {
+          return -1;

[Ryan Sleevi, 2014/03/19 03:08:32]

Not a fan of magic values. If you took base::StringPiece(), returning  a size_t
(or npos) would be far clearer.

[Edit: After having written that, I realize it's instead some magic flags value;
definitely need to document this stuff, along with providing a meaningful
constant for this negative return value]

+        }
+        // Try next child.
+      } else {
+        // If child node has a single char label.
+        if (*child & 0x80) {
+          // If key matches char in child node label.
+          if ((*child & 0x7F) == *key) {
+            // Consume matching label. Step down in child node and read links.
+            ++key;
+            ++child;
+            pos = child;
+          } else {
+            // Key doesn't match label in this child node.
+            if (is_last) {
+              return -1;
+            }
+            // Try next child.
+          }
+        } else {
+          // Child node label has multi character label.
+          if (*child == *key) {
+            // Found a matching link. Step down in child node.
+            ++key;
+            pos = child + 1;
+            break;
+          } else {
+            // Key doesn't match label in this child node.
+            if (is_last) {
+              return -1;
+            }
+            // Try next child.
+          }
+        }
+      }
+    }
+    // Compare key with node label. First character is already consumed.
+    while (true) {
+      if (key == end) {
+        // End of key reached.
+        if (!(*pos & 0x60)) {
+          // Extract return value.
+          return *pos & 0x0F;
+        }
+        // Node label contains more characters that must match.
+        return -1;
+      }
+      if (*pos & 0x80) {
+        // Last character in node label.
+        if (*key & 0x80 || *key < 0x20 || (*key | 0x80) != *pos) {
+          // Not printable 7-bit ASCII in key or key didn't match.
+          return -1;
+        } else {
+          ++key;
+          ++pos;
+          break;
+          // Read links to child nodes.
+        }
+      } else {
+        if (*key++ != *pos++) {
+          // Key doesn't match node label.
+          return -1;
+        }
+        // Key matches so far and there are more characters to check in this
+        // node label.
+      }
+    }
+  }
+}
 
 const int kExceptionRule = 1;
 const int kWildcardRule = 2;
 const int kPrivateRule = 4;
 
-const FindDomainPtr kDefaultFindDomainFunction = Perfect_Hash::FindDomain;
-
-// 'stringpool' is defined as a macro by the gperf-generated
-// "effective_tld_names.cc". Provide a real constant value for it instead.
-const char* const kDefaultStringPool = stringpool;
-#undef stringpool
-
-FindDomainPtr g_find_domain_function = kDefaultFindDomainFunction;
-const char* g_stringpool = kDefaultStringPool;
-
 size_t GetRegistryLengthImpl(
     const std::string& host,
     UnknownRegistryFilter unknown_filter,
     PrivateRegistryFilter private_filter) {
   DCHECK(!host.empty());
 
   // Skip leading dots.
   const size_t host_check_begin = host.find_first_not_of('.');
   if (host_check_begin == std::string::npos)
     return 0;  // Host is only dots.
@@ skipping 11 matching lines @@
 
   // Walk up the domain tree, most specific to least specific,
   // looking for matches at each level.
   size_t prev_start = std::string::npos;
   size_t curr_start = host_check_begin;
   size_t next_dot = host.find('.', curr_start);
   if (next_dot >= host_check_len)  // Catches std::string::npos as well.
     return 0;  // This can't have a registry + domain.
   while (1) {
     const char* domain_str = host.data() + curr_start;
     int domain_length = host_check_len - curr_start;

[Ryan Sleevi, 2014/03/19 03:08:32]

this should have been a size_t, IINM.

-    const DomainRule* rule = g_find_domain_function(domain_str, domain_length);
+    int type = LookupString(graph, domain_str, domain_length);
+    bool do_check =
+        type != -1 && (!(type & kPrivateRule) ||
+                       private_filter == INCLUDE_PRIVATE_REGISTRIES);
 
-    // We need to compare the string after finding a match because the
-    // no-collisions of perfect hashing only refers to items in the set.  Since
-    // we're searching for arbitrary domains, there could be collisions.
-    // Furthermore, if the apparent match is a private registry and we're not
-    // including those, it can't be an actual match.
-    if (rule) {
-      bool do_check = !(rule->type & kPrivateRule) ||
-                      private_filter == INCLUDE_PRIVATE_REGISTRIES;
-      if (do_check && base::strncasecmp(domain_str,
-                                        g_stringpool + rule->name_offset,
-                                        domain_length) == 0) {
-        // Exception rules override wildcard rules when the domain is an exact
-        // match, but wildcards take precedence when there's a subdomain.
-        if (rule->type & kWildcardRule && (prev_start != std::string::npos)) {
-          // If prev_start == host_check_begin, then the host is the registry
-          // itself, so return 0.
-          return (prev_start == host_check_begin) ?
-              0 : (host.length() - prev_start);
+    // If the apparent match is a private registry and we're not including
+    //  those, it can't be an actual match.
+    if (do_check) {
+      // Exception rules override wildcard rules when the domain is an exact
+      // match, but wildcards take precedence when there's a subdomain.
+      if (type & kWildcardRule && (prev_start != std::string::npos)) {
+        // If prev_start == host_check_begin, then the host is the registry
+        // itself, so return 0.
+        return (prev_start == host_check_begin) ? 0
+                                                : (host.length() - prev_start);
+      }
+
+      if (type & kExceptionRule) {
+        if (next_dot == std::string::npos) {
+          // If we get here, we had an exception rule with no dots (e.g.
+          // "!foo").  This would only be valid if we had a corresponding
+          // wildcard rule, which would have to be "*".  But we explicitly
+          // disallow that case, so this kind of rule is invalid.
+          NOTREACHED() << "Invalid exception rule";
+          return 0;
         }
+        return host.length() - next_dot - 1;
+      }
 
-        if (rule->type & kExceptionRule) {
-          if (next_dot == std::string::npos) {
-            // If we get here, we had an exception rule with no dots (e.g.
-            // "!foo").  This would only be valid if we had a corresponding
-            // wildcard rule, which would have to be "*".  But we explicitly
-            // disallow that case, so this kind of rule is invalid.
-            NOTREACHED() << "Invalid exception rule";
-            return 0;
-          }
-          return host.length() - next_dot - 1;
-        }
-
-        // If curr_start == host_check_begin, then the host is the registry
-        // itself, so return 0.
-        return (curr_start == host_check_begin) ?
-            0 : (host.length() - curr_start);
-      }
+      // If curr_start == host_check_begin, then the host is the registry
+      // itself, so return 0.
+      return (curr_start == host_check_begin) ? 0
+                                              : (host.length() - curr_start);
     }
 
     if (next_dot >= host_check_len)  // Catches std::string::npos as well.
       break;
 
     prev_start = curr_start;
     curr_start = next_dot + 1;
     next_dot = host.find('.', curr_start);
   }
 
@@ skipping 99 matching lines @@
     PrivateRegistryFilter private_filter) {
   url_canon::CanonHostInfo host_info;
   const std::string canon_host(CanonicalizeHost(host, &host_info));
   if (canon_host.empty())
     return std::string::npos;
   if (host_info.IsIPAddress())
     return 0;
   return GetRegistryLengthImpl(canon_host, unknown_filter, private_filter);
 }
 
-void SetFindDomainFunctionAndStringPoolForTesting(FindDomainPtr function,
-                                                  const char* stringpool) {
-  g_find_domain_function = function ? function : kDefaultFindDomainFunction;
-  g_stringpool = stringpool ? stringpool : kDefaultStringPool;
+void SetFindDomainGraph(const unsigned char* domains) {
+  graph = domains ? domains : kDafsa;
 }
 
 }  // namespace registry_controlled_domains
 }  // namespace net