OLD | NEW |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 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 #include "chrome/browser/safe_browsing/prefix_set.h" | 5 #include "chrome/browser/safe_browsing/prefix_set.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <math.h> | 8 #include <math.h> |
9 | 9 |
| 10 #include "base/file_util.h" |
10 #include "base/logging.h" | 11 #include "base/logging.h" |
| 12 #include "base/md5.h" |
11 #include "base/metrics/histogram.h" | 13 #include "base/metrics/histogram.h" |
12 | 14 |
13 namespace { | 15 namespace { |
14 | 16 |
| 17 // |kMagic| should be reasonably unique, and not match itself across |
| 18 // endianness changes. I generated this value with: |
| 19 // md5 -qs chrome/browser/safe_browsing/prefix_set.cc | colrm 9 |
| 20 static uint32 kMagic = 0x864088dd; |
| 21 |
| 22 // Current version the code writes out. |
| 23 static uint32 kVersion = 0x1; |
| 24 |
| 25 typedef struct { |
| 26 uint32 magic; |
| 27 uint32 version; |
| 28 uint32 index_size; |
| 29 uint32 deltas_size; |
| 30 } FileHeader; |
| 31 |
15 // For |std::upper_bound()| to find a prefix w/in a vector of pairs. | 32 // For |std::upper_bound()| to find a prefix w/in a vector of pairs. |
16 bool PrefixLess(const std::pair<SBPrefix,size_t>& a, | 33 bool PrefixLess(const std::pair<SBPrefix,size_t>& a, |
17 const std::pair<SBPrefix,size_t>& b) { | 34 const std::pair<SBPrefix,size_t>& b) { |
18 return a.first < b.first; | 35 return a.first < b.first; |
19 } | 36 } |
20 | 37 |
21 } // namespace | 38 } // namespace |
22 | 39 |
23 namespace safe_browsing { | 40 namespace safe_browsing { |
24 | 41 |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
59 const size_t bits_used = index_.size() * sizeof(index_[0]) * CHAR_BIT + | 76 const size_t bits_used = index_.size() * sizeof(index_[0]) * CHAR_BIT + |
60 deltas_.size() * sizeof(deltas_[0]) * CHAR_BIT; | 77 deltas_.size() * sizeof(deltas_[0]) * CHAR_BIT; |
61 const size_t unique_prefixes = index_.size() + deltas_.size(); | 78 const size_t unique_prefixes = index_.size() + deltas_.size(); |
62 static const size_t kMaxBitsPerPrefix = sizeof(SBPrefix) * CHAR_BIT; | 79 static const size_t kMaxBitsPerPrefix = sizeof(SBPrefix) * CHAR_BIT; |
63 UMA_HISTOGRAM_ENUMERATION("SB2.PrefixSetBitsPerPrefix", | 80 UMA_HISTOGRAM_ENUMERATION("SB2.PrefixSetBitsPerPrefix", |
64 bits_used / unique_prefixes, | 81 bits_used / unique_prefixes, |
65 kMaxBitsPerPrefix); | 82 kMaxBitsPerPrefix); |
66 } | 83 } |
67 } | 84 } |
68 | 85 |
| 86 PrefixSet::PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, |
| 87 std::vector<uint16> *deltas) { |
| 88 DCHECK(index && deltas); |
| 89 index_.swap(*index); |
| 90 deltas_.swap(*deltas); |
| 91 } |
| 92 |
69 PrefixSet::~PrefixSet() {} | 93 PrefixSet::~PrefixSet() {} |
70 | 94 |
71 bool PrefixSet::Exists(SBPrefix prefix) const { | 95 bool PrefixSet::Exists(SBPrefix prefix) const { |
72 if (index_.empty()) | 96 if (index_.empty()) |
73 return false; | 97 return false; |
74 | 98 |
75 // Find the first position after |prefix| in |index_|. | 99 // Find the first position after |prefix| in |index_|. |
76 std::vector<std::pair<SBPrefix,size_t> >::const_iterator | 100 std::vector<std::pair<SBPrefix,size_t> >::const_iterator |
77 iter = std::upper_bound(index_.begin(), index_.end(), | 101 iter = std::upper_bound(index_.begin(), index_.end(), |
78 std::pair<SBPrefix,size_t>(prefix, 0), | 102 std::pair<SBPrefix,size_t>(prefix, 0), |
(...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
110 | 134 |
111 SBPrefix current = index_[ii].first; | 135 SBPrefix current = index_[ii].first; |
112 prefixes->push_back(current); | 136 prefixes->push_back(current); |
113 for (size_t di = index_[ii].second; di < deltas_end; ++di) { | 137 for (size_t di = index_[ii].second; di < deltas_end; ++di) { |
114 current += deltas_[di]; | 138 current += deltas_[di]; |
115 prefixes->push_back(current); | 139 prefixes->push_back(current); |
116 } | 140 } |
117 } | 141 } |
118 } | 142 } |
119 | 143 |
| 144 // static |
| 145 PrefixSet* PrefixSet::LoadFile(const FilePath& filter_name) { |
| 146 int64 size_64; |
| 147 if (!file_util::GetFileSize(filter_name, &size_64)) |
| 148 return NULL; |
| 149 if (size_64 < static_cast<int64>(sizeof(FileHeader) + sizeof(MD5Digest))) |
| 150 return NULL; |
| 151 |
| 152 file_util::ScopedFILE file(file_util::OpenFile(filter_name, "rb")); |
| 153 if (!file.get()) |
| 154 return NULL; |
| 155 |
| 156 FileHeader header; |
| 157 size_t read = fread(&header, sizeof(header), 1, file.get()); |
| 158 if (read != 1) |
| 159 return NULL; |
| 160 |
| 161 if (header.magic != kMagic || header.version != kVersion) |
| 162 return NULL; |
| 163 |
| 164 std::vector<std::pair<SBPrefix,size_t> > index; |
| 165 const size_t index_bytes = sizeof(index[0]) * header.index_size; |
| 166 |
| 167 std::vector<uint16> deltas; |
| 168 const size_t deltas_bytes = sizeof(deltas[0]) * header.deltas_size; |
| 169 |
| 170 // Check for bogus sizes before allocating any space. |
| 171 const size_t expected_bytes = |
| 172 sizeof(header) + index_bytes + deltas_bytes + sizeof(MD5Digest); |
| 173 if (static_cast<int64>(expected_bytes) != size_64) |
| 174 return NULL; |
| 175 |
| 176 // The file looks valid, start building the digest. |
| 177 MD5Context context; |
| 178 MD5Init(&context); |
| 179 MD5Update(&context, &header, sizeof(header)); |
| 180 |
| 181 // Read the index vector. Herb Sutter indicates that vectors are |
| 182 // guaranteed to be contiuguous, so reading to where element 0 lives |
| 183 // is valid. |
| 184 index.resize(header.index_size); |
| 185 read = fread(&(index[0]), sizeof(index[0]), index.size(), file.get()); |
| 186 if (read != index.size()) |
| 187 return NULL; |
| 188 MD5Update(&context, &(index[0]), index_bytes); |
| 189 |
| 190 // Read vector of deltas. |
| 191 deltas.resize(header.deltas_size); |
| 192 read = fread(&(deltas[0]), sizeof(deltas[0]), deltas.size(), file.get()); |
| 193 if (read != deltas.size()) |
| 194 return NULL; |
| 195 MD5Update(&context, &(deltas[0]), deltas_bytes); |
| 196 |
| 197 MD5Digest calculated_digest; |
| 198 MD5Final(&calculated_digest, &context); |
| 199 |
| 200 MD5Digest file_digest; |
| 201 read = fread(&file_digest, sizeof(file_digest), 1, file.get()); |
| 202 if (read != 1) |
| 203 return NULL; |
| 204 |
| 205 if (0 != memcmp(&file_digest, &calculated_digest, sizeof(file_digest))) |
| 206 return NULL; |
| 207 |
| 208 // Steals contents of |index| and |deltas| via swap(). |
| 209 return new PrefixSet(&index, &deltas); |
| 210 } |
| 211 |
| 212 bool PrefixSet::WriteFile(const FilePath& filter_name) const { |
| 213 FileHeader header; |
| 214 header.magic = kMagic; |
| 215 header.version = kVersion; |
| 216 header.index_size = static_cast<uint32>(index_.size()); |
| 217 header.deltas_size = static_cast<uint32>(deltas_.size()); |
| 218 |
| 219 // Sanity check that the 32-bit values never mess things up. |
| 220 if (static_cast<size_t>(header.index_size) != index_.size() || |
| 221 static_cast<size_t>(header.deltas_size) != deltas_.size()) { |
| 222 NOTREACHED(); |
| 223 return false; |
| 224 } |
| 225 |
| 226 file_util::ScopedFILE file(file_util::OpenFile(filter_name, "wb")); |
| 227 if (!file.get()) |
| 228 return false; |
| 229 |
| 230 MD5Context context; |
| 231 MD5Init(&context); |
| 232 |
| 233 // TODO(shess): The I/O code in safe_browsing_store_file.cc would |
| 234 // sure be useful about now. |
| 235 size_t written = fwrite(&header, sizeof(header), 1, file.get()); |
| 236 if (written != 1) |
| 237 return false; |
| 238 MD5Update(&context, &header, sizeof(header)); |
| 239 |
| 240 // As for reads, the standard guarantees the ability to access the |
| 241 // contents of the vector by a pointer to an element. |
| 242 const size_t index_bytes = sizeof(index_[0]) * index_.size(); |
| 243 written = fwrite(&(index_[0]), sizeof(index_[0]), index_.size(), file.get()); |
| 244 if (written != index_.size()) |
| 245 return false; |
| 246 MD5Update(&context, &(index_[0]), index_bytes); |
| 247 |
| 248 const size_t deltas_bytes = sizeof(deltas_[0]) * deltas_.size(); |
| 249 written = fwrite(&(deltas_[0]), sizeof(deltas_[0]), deltas_.size(), |
| 250 file.get()); |
| 251 if (written != deltas_.size()) |
| 252 return false; |
| 253 MD5Update(&context, &(deltas_[0]), deltas_bytes); |
| 254 |
| 255 MD5Digest digest; |
| 256 MD5Final(&digest, &context); |
| 257 written = fwrite(&digest, sizeof(digest), 1, file.get()); |
| 258 if (written != 1) |
| 259 return false; |
| 260 |
| 261 // TODO(shess): Can this code check that the close was successful? |
| 262 file.reset(); |
| 263 |
| 264 return true; |
| 265 } |
| 266 |
120 } // namespace safe_browsing | 267 } // namespace safe_browsing |
OLD | NEW |