OLD | NEW |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 // NB: Modelled after Mozilla's code (originally written by Pamela Greene, | 5 // NB: Modelled after Mozilla's code (originally written by Pamela Greene, |
6 // later modified by others), but almost entirely rewritten for Chrome. | 6 // later modified by others), but almost entirely rewritten for Chrome. |
7 // (netwerk/dns/src/nsEffectiveTLDService.cpp) | 7 // (netwerk/dns/src/nsEffectiveTLDService.cpp) |
8 /* ***** BEGIN LICENSE BLOCK ***** | 8 /* ***** BEGIN LICENSE BLOCK ***** |
9 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 | 9 * Version: MPL 1.1/GPL 2.0/LGPL 2.1 |
10 * | 10 * |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
46 #include "net/base/registry_controlled_domains/registry_controlled_domain.h" | 46 #include "net/base/registry_controlled_domains/registry_controlled_domain.h" |
47 | 47 |
48 #include "base/logging.h" | 48 #include "base/logging.h" |
49 #include "base/strings/string_util.h" | 49 #include "base/strings/string_util.h" |
50 #include "base/strings/utf_string_conversions.h" | 50 #include "base/strings/utf_string_conversions.h" |
51 #include "net/base/net_module.h" | 51 #include "net/base/net_module.h" |
52 #include "net/base/net_util.h" | 52 #include "net/base/net_util.h" |
53 #include "url/gurl.h" | 53 #include "url/gurl.h" |
54 #include "url/url_parse.h" | 54 #include "url/url_parse.h" |
55 | 55 |
56 #include "effective_tld_names.cc" | |
57 | |
58 namespace net { | 56 namespace net { |
59 namespace registry_controlled_domains { | 57 namespace registry_controlled_domains { |
60 | 58 |
61 namespace { | 59 namespace { |
| 60 #include "effective_tld_names-inc.cc" |
62 | 61 |
| 62 // See make_dafsa.py for documentation of the generated dafsa byte array. |
| 63 |
| 64 const unsigned char* g_graph = kDafsa; |
| 65 size_t g_graph_length = sizeof(kDafsa); |
| 66 |
| 67 const int kNotFound = -1; |
63 const int kExceptionRule = 1; | 68 const int kExceptionRule = 1; |
64 const int kWildcardRule = 2; | 69 const int kWildcardRule = 2; |
65 const int kPrivateRule = 4; | 70 const int kPrivateRule = 4; |
66 | 71 |
67 const FindDomainPtr kDefaultFindDomainFunction = Perfect_Hash::FindDomain; | 72 // Read next offset from pos. |
| 73 // Returns true if an offset could be read, false otherwise. |
| 74 bool GetNextOffset(const unsigned char** pos, const unsigned char* end, |
| 75 const unsigned char** offset) { |
| 76 if (*pos == end) |
| 77 return false; |
68 | 78 |
69 // 'stringpool' is defined as a macro by the gperf-generated | 79 // When reading an offset the byte array must always contain at least |
70 // "effective_tld_names.cc". Provide a real constant value for it instead. | 80 // three more bytes to consume. First the offset to read, then a node |
71 const char* const kDefaultStringPool = stringpool; | 81 // to skip over and finally a destination node. No object can be smaller |
72 #undef stringpool | 82 // than one byte. |
| 83 CHECK_LT(*pos + 2, end); |
| 84 size_t bytes_consumed; |
| 85 switch (**pos & 0x60) { |
| 86 case 0x60: // Read three byte offset |
| 87 *offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2]; |
| 88 bytes_consumed = 3; |
| 89 break; |
| 90 case 0x40: // Read two byte offset |
| 91 *offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1]; |
| 92 bytes_consumed = 2; |
| 93 break; |
| 94 default: |
| 95 *offset += (*pos)[0] & 0x3F; |
| 96 bytes_consumed = 1; |
| 97 } |
| 98 if ((**pos & 0x80) != 0) { |
| 99 *pos = end; |
| 100 } else { |
| 101 *pos += bytes_consumed; |
| 102 } |
| 103 return true; |
| 104 } |
73 | 105 |
74 FindDomainPtr g_find_domain_function = kDefaultFindDomainFunction; | 106 // Check if byte at offset is last in label. |
75 const char* g_stringpool = kDefaultStringPool; | 107 bool IsEOL(const unsigned char* offset, const unsigned char* end) { |
| 108 CHECK_LT(offset, end); |
| 109 return (*offset & 0x80) != 0; |
| 110 } |
| 111 |
| 112 // Check if byte at offset matches first character in key. |
| 113 // This version matches characters not last in label. |
| 114 bool IsMatch(const unsigned char* offset, const unsigned char* end, |
| 115 const char* key) { |
| 116 CHECK_LT(offset, end); |
| 117 return *offset == *key; |
| 118 } |
| 119 |
| 120 // Check if byte at offset matches first character in key. |
| 121 // This version matches characters last in label. |
| 122 bool IsEndCharMatch(const unsigned char* offset, const unsigned char* end, |
| 123 const char* key) { |
| 124 CHECK_LT(offset, end); |
| 125 return *offset == (*key | 0x80); |
| 126 } |
| 127 |
| 128 // Read return value at offset. |
| 129 // Returns true if a return value could be read, false otherwise. |
| 130 bool GetReturnValue(const unsigned char* offset, const unsigned char* end, |
| 131 int* return_value) { |
| 132 CHECK_LT(offset, end); |
| 133 if ((*offset & 0xE0) == 0x80) { |
| 134 *return_value = *offset & 0x0F; |
| 135 return true; |
| 136 } |
| 137 return false; |
| 138 } |
| 139 |
| 140 // Lookup a domain key in a byte array generated by make_dafsa.py. |
| 141 // The rule type is returned if key is found, otherwise kNotFound is returned. |
| 142 int LookupString(const unsigned char* graph, size_t length, const char* key, |
| 143 size_t key_length) { |
| 144 const unsigned char* pos = graph; |
| 145 const unsigned char* end = graph + length; |
| 146 const unsigned char* offset = pos; |
| 147 const char* key_end = key + key_length; |
| 148 while (GetNextOffset(&pos, end, &offset)) { |
| 149 // char <char>+ end_char offsets |
| 150 // char <char>+ return value |
| 151 // char end_char offsets |
| 152 // char return value |
| 153 // end_char offsets |
| 154 // return_value |
| 155 bool did_consume = false; |
| 156 if (key != key_end && !IsEOL(offset, end)) { |
| 157 // Leading <char> is not a match. Don't dive into this child |
| 158 if (!IsMatch(offset, end, key)) |
| 159 continue; |
| 160 did_consume = true; |
| 161 ++offset; |
| 162 ++key; |
| 163 // Possible matches at this point: |
| 164 // <char>+ end_char offsets |
| 165 // <char>+ return value |
| 166 // end_char offsets |
| 167 // return value |
| 168 // Remove all remaining <char> nodes possible |
| 169 while (!IsEOL(offset, end) && key != key_end) { |
| 170 if (!IsMatch(offset, end, key)) |
| 171 return kNotFound; |
| 172 ++key; |
| 173 ++offset; |
| 174 } |
| 175 } |
| 176 // Possible matches at this point: |
| 177 // end_char offsets |
| 178 // return_value |
| 179 // If one or more <char> elements were consumed, a failure |
| 180 // to match is terminal. Otherwise, try the next node. |
| 181 if (key == key_end) { |
| 182 int return_value; |
| 183 if (GetReturnValue(offset, end, &return_value)) |
| 184 return return_value; |
| 185 // The DAFSA guarantees that if the first char is a match, all |
| 186 // remaining char elements MUST match if the key is truly present. |
| 187 if (did_consume) |
| 188 return kNotFound; |
| 189 continue; |
| 190 } |
| 191 if (!IsEndCharMatch(offset, end, key)) { |
| 192 if (did_consume) |
| 193 return kNotFound; // Unexpected |
| 194 continue; |
| 195 } |
| 196 ++key; |
| 197 pos = ++offset; // Dive into child |
| 198 } |
| 199 return kNotFound; // No match |
| 200 } |
76 | 201 |
77 size_t GetRegistryLengthImpl( | 202 size_t GetRegistryLengthImpl( |
78 const std::string& host, | 203 const std::string& host, |
79 UnknownRegistryFilter unknown_filter, | 204 UnknownRegistryFilter unknown_filter, |
80 PrivateRegistryFilter private_filter) { | 205 PrivateRegistryFilter private_filter) { |
81 DCHECK(!host.empty()); | 206 DCHECK(!host.empty()); |
82 | 207 |
83 // Skip leading dots. | 208 // Skip leading dots. |
84 const size_t host_check_begin = host.find_first_not_of('.'); | 209 const size_t host_check_begin = host.find_first_not_of('.'); |
85 if (host_check_begin == std::string::npos) | 210 if (host_check_begin == std::string::npos) |
(...skipping 12 matching lines...) Expand all Loading... |
98 | 223 |
99 // Walk up the domain tree, most specific to least specific, | 224 // Walk up the domain tree, most specific to least specific, |
100 // looking for matches at each level. | 225 // looking for matches at each level. |
101 size_t prev_start = std::string::npos; | 226 size_t prev_start = std::string::npos; |
102 size_t curr_start = host_check_begin; | 227 size_t curr_start = host_check_begin; |
103 size_t next_dot = host.find('.', curr_start); | 228 size_t next_dot = host.find('.', curr_start); |
104 if (next_dot >= host_check_len) // Catches std::string::npos as well. | 229 if (next_dot >= host_check_len) // Catches std::string::npos as well. |
105 return 0; // This can't have a registry + domain. | 230 return 0; // This can't have a registry + domain. |
106 while (1) { | 231 while (1) { |
107 const char* domain_str = host.data() + curr_start; | 232 const char* domain_str = host.data() + curr_start; |
108 int domain_length = host_check_len - curr_start; | 233 size_t domain_length = host_check_len - curr_start; |
109 const DomainRule* rule = g_find_domain_function(domain_str, domain_length); | 234 int type = LookupString(g_graph, g_graph_length, domain_str, domain_length); |
| 235 bool do_check = |
| 236 type != kNotFound && (!(type & kPrivateRule) || |
| 237 private_filter == INCLUDE_PRIVATE_REGISTRIES); |
110 | 238 |
111 // We need to compare the string after finding a match because the | 239 // If the apparent match is a private registry and we're not including |
112 // no-collisions of perfect hashing only refers to items in the set. Since | 240 // those, it can't be an actual match. |
113 // we're searching for arbitrary domains, there could be collisions. | 241 if (do_check) { |
114 // Furthermore, if the apparent match is a private registry and we're not | 242 // Exception rules override wildcard rules when the domain is an exact |
115 // including those, it can't be an actual match. | 243 // match, but wildcards take precedence when there's a subdomain. |
116 if (rule) { | 244 if (type & kWildcardRule && (prev_start != std::string::npos)) { |
117 bool do_check = !(rule->type & kPrivateRule) || | 245 // If prev_start == host_check_begin, then the host is the registry |
118 private_filter == INCLUDE_PRIVATE_REGISTRIES; | 246 // itself, so return 0. |
119 if (do_check && base::strncasecmp(domain_str, | 247 return (prev_start == host_check_begin) ? 0 |
120 g_stringpool + rule->name_offset, | 248 : (host.length() - prev_start); |
121 domain_length) == 0) { | 249 } |
122 // Exception rules override wildcard rules when the domain is an exact | 250 |
123 // match, but wildcards take precedence when there's a subdomain. | 251 if (type & kExceptionRule) { |
124 if (rule->type & kWildcardRule && (prev_start != std::string::npos)) { | 252 if (next_dot == std::string::npos) { |
125 // If prev_start == host_check_begin, then the host is the registry | 253 // If we get here, we had an exception rule with no dots (e.g. |
126 // itself, so return 0. | 254 // "!foo"). This would only be valid if we had a corresponding |
127 return (prev_start == host_check_begin) ? | 255 // wildcard rule, which would have to be "*". But we explicitly |
128 0 : (host.length() - prev_start); | 256 // disallow that case, so this kind of rule is invalid. |
| 257 NOTREACHED() << "Invalid exception rule"; |
| 258 return 0; |
129 } | 259 } |
| 260 return host.length() - next_dot - 1; |
| 261 } |
130 | 262 |
131 if (rule->type & kExceptionRule) { | 263 // If curr_start == host_check_begin, then the host is the registry |
132 if (next_dot == std::string::npos) { | 264 // itself, so return 0. |
133 // If we get here, we had an exception rule with no dots (e.g. | 265 return (curr_start == host_check_begin) ? 0 |
134 // "!foo"). This would only be valid if we had a corresponding | 266 : (host.length() - curr_start); |
135 // wildcard rule, which would have to be "*". But we explicitly | |
136 // disallow that case, so this kind of rule is invalid. | |
137 NOTREACHED() << "Invalid exception rule"; | |
138 return 0; | |
139 } | |
140 return host.length() - next_dot - 1; | |
141 } | |
142 | |
143 // If curr_start == host_check_begin, then the host is the registry | |
144 // itself, so return 0. | |
145 return (curr_start == host_check_begin) ? | |
146 0 : (host.length() - curr_start); | |
147 } | |
148 } | 267 } |
149 | 268 |
150 if (next_dot >= host_check_len) // Catches std::string::npos as well. | 269 if (next_dot >= host_check_len) // Catches std::string::npos as well. |
151 break; | 270 break; |
152 | 271 |
153 prev_start = curr_start; | 272 prev_start = curr_start; |
154 curr_start = next_dot + 1; | 273 curr_start = next_dot + 1; |
155 next_dot = host.find('.', curr_start); | 274 next_dot = host.find('.', curr_start); |
156 } | 275 } |
157 | 276 |
(...skipping 99 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
257 PrivateRegistryFilter private_filter) { | 376 PrivateRegistryFilter private_filter) { |
258 url_canon::CanonHostInfo host_info; | 377 url_canon::CanonHostInfo host_info; |
259 const std::string canon_host(CanonicalizeHost(host, &host_info)); | 378 const std::string canon_host(CanonicalizeHost(host, &host_info)); |
260 if (canon_host.empty()) | 379 if (canon_host.empty()) |
261 return std::string::npos; | 380 return std::string::npos; |
262 if (host_info.IsIPAddress()) | 381 if (host_info.IsIPAddress()) |
263 return 0; | 382 return 0; |
264 return GetRegistryLengthImpl(canon_host, unknown_filter, private_filter); | 383 return GetRegistryLengthImpl(canon_host, unknown_filter, private_filter); |
265 } | 384 } |
266 | 385 |
267 void SetFindDomainFunctionAndStringPoolForTesting(FindDomainPtr function, | 386 void SetFindDomainGraph() { |
268 const char* stringpool) { | 387 g_graph = kDafsa; |
269 g_find_domain_function = function ? function : kDefaultFindDomainFunction; | 388 g_graph_length = sizeof(kDafsa); |
270 g_stringpool = stringpool ? stringpool : kDefaultStringPool; | 389 } |
| 390 |
| 391 void SetFindDomainGraph(const unsigned char* domains, size_t length) { |
| 392 CHECK(domains); |
| 393 CHECK_NE(length, 0); |
| 394 g_graph = domains; |
| 395 g_graph_length = length; |
271 } | 396 } |
272 | 397 |
273 } // namespace registry_controlled_domains | 398 } // namespace registry_controlled_domains |
274 } // namespace net | 399 } // namespace net |
OLD | NEW |