Line data Source code
1 : //* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : // Originally based on Chrome sources:
3 : // Copyright (c) 2010 The Chromium Authors. All rights reserved.
4 : //
5 : // Redistribution and use in source and binary forms, with or without
6 : // modification, are permitted provided that the following conditions are
7 : // met:
8 : //
9 : // * Redistributions of source code must retain the above copyright
10 : // notice, this list of conditions and the following disclaimer.
11 : // * Redistributions in binary form must reproduce the above
12 : // copyright notice, this list of conditions and the following disclaimer
13 : // in the documentation and/or other materials provided with the
14 : // distribution.
15 : // * Neither the name of Google Inc. nor the names of its
16 : // contributors may be used to endorse or promote products derived from
17 : // this software without specific prior written permission.
18 : //
19 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 :
31 :
32 : #include "HashStore.h"
33 : #include "nsICryptoHash.h"
34 : #include "nsISeekableStream.h"
35 : #include "nsIStreamConverterService.h"
36 : #include "nsNetUtil.h"
37 : #include "nsCheckSummedOutputStream.h"
38 : #include "prio.h"
39 : #include "mozilla/Logging.h"
40 : #include "mozilla/IntegerPrintfMacros.h"
41 : #include "mozilla/SizePrintfMacros.h"
42 : #include "zlib.h"
43 : #include "Classifier.h"
44 : #include "nsUrlClassifierDBService.h"
45 : #include "mozilla/Telemetry.h"
46 :
47 : // Main store for SafeBrowsing protocol data. We store
48 : // known add/sub chunks, prefixes and completions in memory
49 : // during an update, and serialize to disk.
50 : // We do not store the add prefixes, those are retrieved by
51 : // decompressing the PrefixSet cache whenever we need to apply
52 : // an update.
53 : //
54 : // byte slicing: Many of the 4-byte values stored here are strongly
55 : // correlated in the upper bytes, and uncorrelated in the lower
56 : // bytes. Because zlib/DEFLATE requires match lengths of at least
57 : // 3 to achieve good compression, and we don't get those if only
58 : // the upper 16-bits are correlated, it is worthwhile to slice 32-bit
59 : // values into 4 1-byte slices and compress the slices individually.
60 : // The slices corresponding to MSBs will compress very well, and the
61 : // slice corresponding to LSB almost nothing. Because of this, we
62 : // only apply DEFLATE to the 3 most significant bytes, and store the
63 : // LSB uncompressed.
64 : //
65 : // byte sliced (numValues) data format:
66 : // uint32_t compressed-size
67 : // compressed-size bytes zlib DEFLATE data
68 : // 0...numValues byte MSB of 4-byte numValues data
69 : // uint32_t compressed-size
70 : // compressed-size bytes zlib DEFLATE data
71 : // 0...numValues byte 2nd byte of 4-byte numValues data
72 : // uint32_t compressed-size
73 : // compressed-size bytes zlib DEFLATE data
74 : // 0...numValues byte 3rd byte of 4-byte numValues data
75 : // 0...numValues byte LSB of 4-byte numValues data
76 : //
77 : // Store data format:
78 : // uint32_t magic
79 : // uint32_t version
80 : // uint32_t numAddChunks
81 : // uint32_t numSubChunks
82 : // uint32_t numAddPrefixes
83 : // uint32_t numSubPrefixes
84 : // uint32_t numAddCompletes
85 : // uint32_t numSubCompletes
86 : // 0...numAddChunks uint32_t addChunk
87 : // 0...numSubChunks uint32_t subChunk
88 : // byte sliced (numAddPrefixes) uint32_t add chunk of AddPrefixes
89 : // byte sliced (numSubPrefixes) uint32_t add chunk of SubPrefixes
90 : // byte sliced (numSubPrefixes) uint32_t sub chunk of SubPrefixes
91 : // byte sliced (numSubPrefixes) uint32_t SubPrefixes
92 : // 0...numAddCompletes 32-byte Completions + uint32_t addChunk
93 : // 0...numSubCompletes 32-byte Completions + uint32_t addChunk
94 : // + uint32_t subChunk
95 : // 16-byte MD5 of all preceding data
96 :
97 : // Name of the SafeBrowsing store
98 : #define STORE_SUFFIX ".sbstore"
99 :
100 : // MOZ_LOG=UrlClassifierDbService:5
101 : extern mozilla::LazyLogModule gUrlClassifierDbServiceLog;
102 : #define LOG(args) MOZ_LOG(gUrlClassifierDbServiceLog, mozilla::LogLevel::Debug, args)
103 : #define LOG_ENABLED() MOZ_LOG_TEST(gUrlClassifierDbServiceLog, mozilla::LogLevel::Debug)
104 :
105 : namespace mozilla {
106 : namespace safebrowsing {
107 :
108 : const uint32_t STORE_MAGIC = 0x1231af3b;
109 : const uint32_t CURRENT_VERSION = 3;
110 :
111 : nsresult
112 0 : TableUpdateV2::NewAddPrefix(uint32_t aAddChunk, const Prefix& aHash)
113 : {
114 0 : AddPrefix *add = mAddPrefixes.AppendElement(fallible);
115 0 : if (!add) return NS_ERROR_OUT_OF_MEMORY;
116 0 : add->addChunk = aAddChunk;
117 0 : add->prefix = aHash;
118 0 : return NS_OK;
119 : }
120 :
121 : nsresult
122 0 : TableUpdateV2::NewSubPrefix(uint32_t aAddChunk, const Prefix& aHash, uint32_t aSubChunk)
123 : {
124 0 : SubPrefix *sub = mSubPrefixes.AppendElement(fallible);
125 0 : if (!sub) return NS_ERROR_OUT_OF_MEMORY;
126 0 : sub->addChunk = aAddChunk;
127 0 : sub->prefix = aHash;
128 0 : sub->subChunk = aSubChunk;
129 0 : return NS_OK;
130 : }
131 :
132 : nsresult
133 7 : TableUpdateV2::NewAddComplete(uint32_t aAddChunk, const Completion& aHash)
134 : {
135 7 : AddComplete *add = mAddCompletes.AppendElement(fallible);
136 7 : if (!add) return NS_ERROR_OUT_OF_MEMORY;
137 7 : add->addChunk = aAddChunk;
138 7 : add->complete = aHash;
139 7 : return NS_OK;
140 : }
141 :
142 : nsresult
143 0 : TableUpdateV2::NewSubComplete(uint32_t aAddChunk, const Completion& aHash, uint32_t aSubChunk)
144 : {
145 0 : SubComplete *sub = mSubCompletes.AppendElement(fallible);
146 0 : if (!sub) return NS_ERROR_OUT_OF_MEMORY;
147 0 : sub->addChunk = aAddChunk;
148 0 : sub->complete = aHash;
149 0 : sub->subChunk = aSubChunk;
150 0 : return NS_OK;
151 : }
152 :
153 : nsresult
154 0 : TableUpdateV2::NewMissPrefix(const Prefix& aPrefix)
155 : {
156 0 : Prefix *prefix = mMissPrefixes.AppendElement(aPrefix, fallible);
157 0 : if (!prefix) return NS_ERROR_OUT_OF_MEMORY;
158 0 : return NS_OK;
159 : }
160 :
161 : void
162 0 : TableUpdateV4::NewPrefixes(int32_t aSize, std::string& aPrefixes)
163 : {
164 0 : NS_ENSURE_TRUE_VOID(aSize >= 4 && aSize <= COMPLETE_SIZE);
165 0 : NS_ENSURE_TRUE_VOID(aPrefixes.size() % aSize == 0);
166 0 : NS_ENSURE_TRUE_VOID(!mPrefixesMap.Get(aSize));
167 :
168 0 : int numOfPrefixes = aPrefixes.size() / aSize;
169 :
170 0 : if (aSize > 4) {
171 : // TODO Bug 1364043 we may have a better API to record multiple samples into
172 : // histograms with one call
173 : #ifdef NIGHTLY_BUILD
174 0 : for (int i = 0; i < std::min(20, numOfPrefixes); i++) {
175 0 : Telemetry::Accumulate(Telemetry::URLCLASSIFIER_VLPS_LONG_PREFIXES, aSize);
176 : }
177 : #endif
178 0 : } else if (LOG_ENABLED()) {
179 0 : uint32_t* p = (uint32_t*)aPrefixes.c_str();
180 :
181 : // Dump the first/last 10 fixed-length prefixes for debugging.
182 0 : LOG(("* The first 10 (maximum) fixed-length prefixes: "));
183 0 : for (int i = 0; i < std::min(10, numOfPrefixes); i++) {
184 0 : uint8_t* c = (uint8_t*)&p[i];
185 0 : LOG(("%.2X%.2X%.2X%.2X", c[0], c[1], c[2], c[3]));
186 : }
187 :
188 0 : LOG(("* The last 10 (maximum) fixed-length prefixes: "));
189 0 : for (int i = std::max(0, numOfPrefixes - 10); i < numOfPrefixes; i++) {
190 0 : uint8_t* c = (uint8_t*)&p[i];
191 0 : LOG(("%.2X%.2X%.2X%.2X", c[0], c[1], c[2], c[3]));
192 : }
193 :
194 0 : LOG(("---- %" PRIuSIZE " fixed-length prefixes in total.", aPrefixes.size() / aSize));
195 : }
196 :
197 0 : PrefixStdString* prefix = new PrefixStdString(aPrefixes);
198 0 : mPrefixesMap.Put(aSize, prefix);
199 : }
200 :
201 : void
202 0 : TableUpdateV4::NewRemovalIndices(const uint32_t* aIndices, size_t aNumOfIndices)
203 : {
204 0 : for (size_t i = 0; i < aNumOfIndices; i++) {
205 0 : mRemovalIndiceArray.AppendElement(aIndices[i]);
206 : }
207 0 : }
208 :
209 : void
210 0 : TableUpdateV4::NewChecksum(const std::string& aChecksum)
211 : {
212 0 : mChecksum.Assign(aChecksum.data(), aChecksum.size());
213 0 : }
214 :
215 : nsresult
216 0 : TableUpdateV4::NewFullHashResponse(const Prefix& aPrefix,
217 : CachedFullHashResponse& aResponse)
218 : {
219 : CachedFullHashResponse* response =
220 0 : mFullHashResponseMap.LookupOrAdd(aPrefix.ToUint32());
221 0 : if (!response) {
222 0 : return NS_ERROR_OUT_OF_MEMORY;
223 : }
224 0 : *response = aResponse;
225 0 : return NS_OK;
226 : }
227 :
228 43 : HashStore::HashStore(const nsACString& aTableName,
229 : const nsACString& aProvider,
230 43 : nsIFile* aRootStoreDir)
231 : : mTableName(aTableName)
232 : , mInUpdate(false)
233 43 : , mFileSize(0)
234 : {
235 43 : nsresult rv = Classifier::GetPrivateStoreDirectory(aRootStoreDir,
236 : aTableName,
237 : aProvider,
238 86 : getter_AddRefs(mStoreDirectory));
239 43 : if (NS_FAILED(rv)) {
240 0 : LOG(("Failed to get private store directory for %s", mTableName.get()));
241 0 : mStoreDirectory = aRootStoreDir;
242 : }
243 43 : }
244 :
245 : HashStore::~HashStore()
246 : = default;
247 :
248 : nsresult
249 0 : HashStore::Reset()
250 : {
251 0 : LOG(("HashStore resetting"));
252 :
253 0 : nsCOMPtr<nsIFile> storeFile;
254 0 : nsresult rv = mStoreDirectory->Clone(getter_AddRefs(storeFile));
255 0 : NS_ENSURE_SUCCESS(rv, rv);
256 :
257 0 : rv = storeFile->AppendNative(mTableName + NS_LITERAL_CSTRING(STORE_SUFFIX));
258 0 : NS_ENSURE_SUCCESS(rv, rv);
259 :
260 0 : rv = storeFile->Remove(false);
261 0 : NS_ENSURE_SUCCESS(rv, rv);
262 :
263 0 : mFileSize = 0;
264 :
265 0 : return NS_OK;
266 : }
267 :
268 : nsresult
269 6 : HashStore::CheckChecksum(uint32_t aFileSize)
270 : {
271 6 : if (!mInputStream) {
272 0 : return NS_OK;
273 : }
274 :
275 : // Check for file corruption by
276 : // comparing the stored checksum to actual checksum of data
277 12 : nsAutoCString hash;
278 12 : nsAutoCString compareHash;
279 : char *data;
280 : uint32_t read;
281 :
282 6 : nsresult rv = CalculateChecksum(hash, aFileSize, true);
283 6 : NS_ENSURE_SUCCESS(rv, rv);
284 :
285 6 : compareHash.GetMutableData(&data, hash.Length());
286 :
287 6 : if (hash.Length() > aFileSize) {
288 0 : NS_WARNING("SafeBrowing file not long enough to store its hash");
289 0 : return NS_ERROR_FAILURE;
290 : }
291 12 : nsCOMPtr<nsISeekableStream> seekIn = do_QueryInterface(mInputStream);
292 6 : rv = seekIn->Seek(nsISeekableStream::NS_SEEK_SET, aFileSize - hash.Length());
293 6 : NS_ENSURE_SUCCESS(rv, rv);
294 :
295 6 : rv = mInputStream->Read(data, hash.Length(), &read);
296 6 : NS_ENSURE_SUCCESS(rv, rv);
297 6 : NS_ASSERTION(read == hash.Length(), "Could not read hash bytes");
298 :
299 6 : if (!hash.Equals(compareHash)) {
300 0 : NS_WARNING("Safebrowing file failed checksum.");
301 0 : return NS_ERROR_FAILURE;
302 : }
303 :
304 6 : return NS_OK;
305 : }
306 :
307 : nsresult
308 43 : HashStore::Open()
309 : {
310 86 : nsCOMPtr<nsIFile> storeFile;
311 43 : nsresult rv = mStoreDirectory->Clone(getter_AddRefs(storeFile));
312 43 : NS_ENSURE_SUCCESS(rv, rv);
313 :
314 43 : rv = storeFile->AppendNative(mTableName + NS_LITERAL_CSTRING(".sbstore"));
315 43 : NS_ENSURE_SUCCESS(rv, rv);
316 :
317 86 : nsCOMPtr<nsIInputStream> origStream;
318 86 : rv = NS_NewLocalFileInputStream(getter_AddRefs(origStream), storeFile,
319 43 : PR_RDONLY | nsIFile::OS_READAHEAD);
320 :
321 43 : if (rv == NS_ERROR_FILE_NOT_FOUND) {
322 1 : UpdateHeader();
323 1 : return NS_OK;
324 : }
325 42 : NS_ENSURE_SUCCESS(rv, rv);
326 :
327 : int64_t fileSize;
328 42 : rv = storeFile->GetFileSize(&fileSize);
329 42 : NS_ENSURE_SUCCESS(rv, rv);
330 :
331 42 : if (fileSize < 0 || fileSize > UINT32_MAX) {
332 0 : return NS_ERROR_FAILURE;
333 : }
334 :
335 42 : mFileSize = static_cast<uint32_t>(fileSize);
336 42 : mInputStream = NS_BufferInputStream(origStream, mFileSize);
337 :
338 42 : rv = ReadHeader();
339 42 : NS_ENSURE_SUCCESS(rv, rv);
340 :
341 42 : rv = SanityCheck();
342 42 : NS_ENSURE_SUCCESS(rv, rv);
343 :
344 42 : return NS_OK;
345 : }
346 :
347 : nsresult
348 42 : HashStore::ReadHeader()
349 : {
350 42 : if (!mInputStream) {
351 0 : UpdateHeader();
352 0 : return NS_OK;
353 : }
354 :
355 84 : nsCOMPtr<nsISeekableStream> seekable = do_QueryInterface(mInputStream);
356 42 : nsresult rv = seekable->Seek(nsISeekableStream::NS_SEEK_SET, 0);
357 42 : NS_ENSURE_SUCCESS(rv, rv);
358 :
359 42 : void *buffer = &mHeader;
360 42 : rv = NS_ReadInputStreamToBuffer(mInputStream,
361 : &buffer,
362 42 : sizeof(Header));
363 42 : NS_ENSURE_SUCCESS(rv, rv);
364 :
365 42 : return NS_OK;
366 : }
367 :
368 : nsresult
369 42 : HashStore::SanityCheck()
370 : {
371 42 : if (mHeader.magic != STORE_MAGIC || mHeader.version != CURRENT_VERSION) {
372 0 : NS_WARNING("Unexpected header data in the store.");
373 0 : return NS_ERROR_FAILURE;
374 : }
375 :
376 42 : return NS_OK;
377 : }
378 :
379 : nsresult
380 6 : HashStore::CalculateChecksum(nsAutoCString& aChecksum,
381 : uint32_t aFileSize,
382 : bool aChecksumPresent)
383 : {
384 6 : aChecksum.Truncate();
385 :
386 : // Reset mInputStream to start
387 12 : nsCOMPtr<nsISeekableStream> seekable = do_QueryInterface(mInputStream);
388 6 : nsresult rv = seekable->Seek(nsISeekableStream::NS_SEEK_SET, 0);
389 :
390 12 : nsCOMPtr<nsICryptoHash> hash = do_CreateInstance(NS_CRYPTO_HASH_CONTRACTID, &rv);
391 6 : NS_ENSURE_SUCCESS(rv, rv);
392 :
393 : // Size of MD5 hash in bytes
394 6 : const uint32_t CHECKSUM_SIZE = 16;
395 :
396 : // MD5 is not a secure hash function, but since this is a filesystem integrity
397 : // check, this usage is ok.
398 6 : rv = hash->Init(nsICryptoHash::MD5);
399 6 : NS_ENSURE_SUCCESS(rv, rv);
400 :
401 6 : if (!aChecksumPresent) {
402 : // Hash entire file
403 0 : rv = hash->UpdateFromStream(mInputStream, UINT32_MAX);
404 : } else {
405 : // Hash everything but last checksum bytes
406 6 : if (aFileSize < CHECKSUM_SIZE) {
407 0 : NS_WARNING("SafeBrowsing file isn't long enough to store its checksum");
408 0 : return NS_ERROR_FAILURE;
409 : }
410 6 : rv = hash->UpdateFromStream(mInputStream, aFileSize - CHECKSUM_SIZE);
411 : }
412 6 : NS_ENSURE_SUCCESS(rv, rv);
413 :
414 6 : rv = hash->Finish(false, aChecksum);
415 6 : NS_ENSURE_SUCCESS(rv, rv);
416 :
417 6 : return NS_OK;
418 : }
419 :
420 : void
421 7 : HashStore::UpdateHeader()
422 : {
423 7 : mHeader.magic = STORE_MAGIC;
424 7 : mHeader.version = CURRENT_VERSION;
425 :
426 7 : mHeader.numAddChunks = mAddChunks.Length();
427 7 : mHeader.numSubChunks = mSubChunks.Length();
428 7 : mHeader.numAddPrefixes = mAddPrefixes.Length();
429 7 : mHeader.numSubPrefixes = mSubPrefixes.Length();
430 7 : mHeader.numAddCompletes = mAddCompletes.Length();
431 7 : mHeader.numSubCompletes = mSubCompletes.Length();
432 7 : }
433 :
434 : nsresult
435 54 : HashStore::ReadChunkNumbers()
436 : {
437 54 : if (!mInputStream || AlreadyReadChunkNumbers()) {
438 24 : return NS_OK;
439 : }
440 :
441 60 : nsCOMPtr<nsISeekableStream> seekable = do_QueryInterface(mInputStream);
442 30 : nsresult rv = seekable->Seek(nsISeekableStream::NS_SEEK_SET,
443 30 : sizeof(Header));
444 30 : NS_ENSURE_SUCCESS(rv, rv);
445 :
446 30 : rv = mAddChunks.Read(mInputStream, mHeader.numAddChunks);
447 30 : NS_ENSURE_SUCCESS(rv, rv);
448 30 : NS_ASSERTION(mAddChunks.Length() == mHeader.numAddChunks, "Read the right amount of add chunks.");
449 :
450 30 : rv = mSubChunks.Read(mInputStream, mHeader.numSubChunks);
451 30 : NS_ENSURE_SUCCESS(rv, rv);
452 30 : NS_ASSERTION(mSubChunks.Length() == mHeader.numSubChunks, "Read the right amount of sub chunks.");
453 :
454 30 : return NS_OK;
455 : }
456 :
457 : nsresult
458 6 : HashStore::ReadHashes()
459 : {
460 6 : if (!mInputStream) {
461 : // BeginUpdate has been called but Open hasn't initialized mInputStream,
462 : // because the existing HashStore is empty.
463 0 : return NS_OK;
464 : }
465 :
466 12 : nsCOMPtr<nsISeekableStream> seekable = do_QueryInterface(mInputStream);
467 :
468 6 : uint32_t offset = sizeof(Header);
469 6 : offset += (mHeader.numAddChunks + mHeader.numSubChunks) * sizeof(uint32_t);
470 6 : nsresult rv = seekable->Seek(nsISeekableStream::NS_SEEK_SET, offset);
471 6 : NS_ENSURE_SUCCESS(rv, rv);
472 :
473 6 : rv = ReadAddPrefixes();
474 6 : NS_ENSURE_SUCCESS(rv, rv);
475 :
476 6 : rv = ReadSubPrefixes();
477 6 : NS_ENSURE_SUCCESS(rv, rv);
478 :
479 : // If completions was read before, then we are done here.
480 6 : if (AlreadyReadCompletions()) {
481 0 : return NS_OK;
482 : }
483 :
484 6 : rv = ReadTArray(mInputStream, &mAddCompletes, mHeader.numAddCompletes);
485 6 : NS_ENSURE_SUCCESS(rv, rv);
486 :
487 6 : rv = ReadTArray(mInputStream, &mSubCompletes, mHeader.numSubCompletes);
488 6 : NS_ENSURE_SUCCESS(rv, rv);
489 :
490 6 : return NS_OK;
491 : }
492 :
493 :
494 : nsresult
495 19 : HashStore::ReadCompletions()
496 : {
497 19 : if (!mInputStream || AlreadyReadCompletions()) {
498 7 : return NS_OK;
499 : }
500 :
501 24 : nsCOMPtr<nsIFile> storeFile;
502 12 : nsresult rv = mStoreDirectory->Clone(getter_AddRefs(storeFile));
503 12 : NS_ENSURE_SUCCESS(rv, rv);
504 :
505 12 : rv = storeFile->AppendNative(mTableName + NS_LITERAL_CSTRING(STORE_SUFFIX));
506 12 : NS_ENSURE_SUCCESS(rv, rv);
507 :
508 24 : uint32_t offset = mFileSize -
509 24 : sizeof(struct AddComplete) * mHeader.numAddCompletes -
510 12 : sizeof(struct SubComplete) * mHeader.numSubCompletes -
511 12 : nsCheckSummedOutputStream::CHECKSUM_SIZE;
512 :
513 24 : nsCOMPtr<nsISeekableStream> seekable = do_QueryInterface(mInputStream);
514 :
515 12 : rv = seekable->Seek(nsISeekableStream::NS_SEEK_SET, offset);
516 12 : NS_ENSURE_SUCCESS(rv, rv);
517 :
518 12 : rv = ReadTArray(mInputStream, &mAddCompletes, mHeader.numAddCompletes);
519 12 : NS_ENSURE_SUCCESS(rv, rv);
520 :
521 12 : rv = ReadTArray(mInputStream, &mSubCompletes, mHeader.numSubCompletes);
522 12 : NS_ENSURE_SUCCESS(rv, rv);
523 :
524 12 : return NS_OK;
525 : }
526 :
527 : nsresult
528 6 : HashStore::PrepareForUpdate()
529 : {
530 6 : nsresult rv = CheckChecksum(mFileSize);
531 6 : NS_ENSURE_SUCCESS(rv, rv);
532 :
533 6 : rv = ReadChunkNumbers();
534 6 : NS_ENSURE_SUCCESS(rv, rv);
535 :
536 6 : rv = ReadHashes();
537 6 : NS_ENSURE_SUCCESS(rv, rv);
538 :
539 6 : return NS_OK;
540 : }
541 :
542 : nsresult
543 6 : HashStore::BeginUpdate()
544 : {
545 : // Check wether the file is corrupted and read the rest of the store
546 : // in memory.
547 6 : nsresult rv = PrepareForUpdate();
548 6 : NS_ENSURE_SUCCESS(rv, rv);
549 :
550 : // Close input stream, won't be needed any more and
551 : // we will rewrite ourselves.
552 6 : if (mInputStream) {
553 6 : rv = mInputStream->Close();
554 6 : NS_ENSURE_SUCCESS(rv, rv);
555 : }
556 :
557 6 : mInUpdate = true;
558 :
559 6 : return NS_OK;
560 : }
561 :
562 : template<class T>
563 : static nsresult
564 24 : Merge(ChunkSet* aStoreChunks,
565 : FallibleTArray<T>* aStorePrefixes,
566 : ChunkSet& aUpdateChunks,
567 : FallibleTArray<T>& aUpdatePrefixes,
568 : bool aAllowMerging = false)
569 : {
570 24 : EntrySort(aUpdatePrefixes);
571 :
572 24 : auto storeIter = aStorePrefixes->begin();
573 24 : auto storeEnd = aStorePrefixes->end();
574 :
575 : // use a separate array so we can keep the iterators valid
576 : // if the nsTArray grows
577 48 : nsTArray<T> adds;
578 :
579 31 : for (const auto& updatePrefix : aUpdatePrefixes) {
580 : // skip this chunk if we already have it, unless we're
581 : // merging completions, in which case we'll always already
582 : // have the chunk from the original prefix
583 7 : if (aStoreChunks->Has(updatePrefix.Chunk()))
584 7 : if (!aAllowMerging)
585 0 : continue;
586 : // XXX: binary search for insertion point might be faster in common
587 : // case?
588 7 : while (storeIter < storeEnd && (storeIter->Compare(updatePrefix) < 0)) {
589 : // skip forward to matching element (or not...)
590 0 : storeIter++;
591 : }
592 : // no match, add
593 14 : if (storeIter == storeEnd
594 7 : || storeIter->Compare(updatePrefix) != 0) {
595 6 : if (!adds.AppendElement(updatePrefix))
596 0 : return NS_ERROR_OUT_OF_MEMORY;
597 : }
598 : }
599 :
600 : // Chunks can be empty, but we should still report we have them
601 : // to make the chunkranges continuous.
602 24 : aStoreChunks->Merge(aUpdateChunks);
603 :
604 24 : if (!aStorePrefixes->AppendElements(adds, fallible))
605 0 : return NS_ERROR_OUT_OF_MEMORY;
606 :
607 24 : EntrySort(*aStorePrefixes);
608 :
609 24 : return NS_OK;
610 : }
611 :
612 : nsresult
613 6 : HashStore::ApplyUpdate(TableUpdate &aUpdate)
614 : {
615 6 : auto updateV2 = TableUpdate::Cast<TableUpdateV2>(&aUpdate);
616 6 : NS_ENSURE_TRUE(updateV2, NS_ERROR_FAILURE);
617 :
618 6 : TableUpdateV2& update = *updateV2;
619 :
620 6 : nsresult rv = mAddExpirations.Merge(update.AddExpirations());
621 6 : NS_ENSURE_SUCCESS(rv, rv);
622 :
623 6 : rv = mSubExpirations.Merge(update.SubExpirations());
624 6 : NS_ENSURE_SUCCESS(rv, rv);
625 :
626 6 : rv = Expire();
627 6 : NS_ENSURE_SUCCESS(rv, rv);
628 :
629 6 : rv = Merge(&mAddChunks, &mAddPrefixes,
630 12 : update.AddChunks(), update.AddPrefixes());
631 6 : NS_ENSURE_SUCCESS(rv, rv);
632 :
633 6 : rv = Merge(&mAddChunks, &mAddCompletes,
634 12 : update.AddChunks(), update.AddCompletes(), true);
635 6 : NS_ENSURE_SUCCESS(rv, rv);
636 :
637 6 : rv = Merge(&mSubChunks, &mSubPrefixes,
638 12 : update.SubChunks(), update.SubPrefixes());
639 6 : NS_ENSURE_SUCCESS(rv, rv);
640 :
641 6 : rv = Merge(&mSubChunks, &mSubCompletes,
642 12 : update.SubChunks(), update.SubCompletes(), true);
643 6 : NS_ENSURE_SUCCESS(rv, rv);
644 :
645 6 : return NS_OK;
646 : }
647 :
648 : nsresult
649 6 : HashStore::Rebuild()
650 : {
651 6 : NS_ASSERTION(mInUpdate, "Must be in update to rebuild.");
652 :
653 6 : nsresult rv = ProcessSubs();
654 6 : NS_ENSURE_SUCCESS(rv, rv);
655 :
656 6 : UpdateHeader();
657 :
658 6 : return NS_OK;
659 : }
660 :
661 : void
662 0 : HashStore::ClearCompletes()
663 : {
664 0 : NS_ASSERTION(mInUpdate, "Must be in update to clear completes.");
665 :
666 0 : mAddCompletes.Clear();
667 0 : mSubCompletes.Clear();
668 :
669 0 : UpdateHeader();
670 0 : }
671 :
672 : template<class T>
673 : static void
674 24 : ExpireEntries(FallibleTArray<T>* aEntries, ChunkSet& aExpirations)
675 : {
676 24 : auto addIter = aEntries->begin();
677 :
678 31 : for (const auto& entry : *aEntries) {
679 7 : if (!aExpirations.Has(entry.Chunk())) {
680 1 : *addIter = entry;
681 1 : addIter++;
682 : }
683 : }
684 :
685 24 : aEntries->TruncateLength(addIter - aEntries->begin());
686 24 : }
687 :
688 : nsresult
689 6 : HashStore::Expire()
690 : {
691 6 : ExpireEntries(&mAddPrefixes, mAddExpirations);
692 6 : ExpireEntries(&mAddCompletes, mAddExpirations);
693 6 : ExpireEntries(&mSubPrefixes, mSubExpirations);
694 6 : ExpireEntries(&mSubCompletes, mSubExpirations);
695 :
696 6 : mAddChunks.Remove(mAddExpirations);
697 6 : mSubChunks.Remove(mSubExpirations);
698 :
699 6 : mAddExpirations.Clear();
700 6 : mSubExpirations.Clear();
701 :
702 6 : return NS_OK;
703 : }
704 :
705 : template<class T>
706 72 : nsresult DeflateWriteTArray(nsIOutputStream* aStream, nsTArray<T>& aIn)
707 : {
708 72 : uLongf insize = aIn.Length() * sizeof(T);
709 72 : uLongf outsize = compressBound(insize);
710 144 : FallibleTArray<char> outBuff;
711 72 : if (!outBuff.SetLength(outsize, fallible)) {
712 0 : return NS_ERROR_OUT_OF_MEMORY;
713 : }
714 :
715 72 : int zerr = compress(reinterpret_cast<Bytef*>(outBuff.Elements()),
716 : &outsize,
717 72 : reinterpret_cast<const Bytef*>(aIn.Elements()),
718 72 : insize);
719 72 : if (zerr != Z_OK) {
720 0 : return NS_ERROR_FAILURE;
721 : }
722 72 : LOG(("DeflateWriteTArray: %lu in %lu out", insize, outsize));
723 :
724 72 : outBuff.TruncateLength(outsize);
725 :
726 : // Length of compressed data stream
727 72 : uint32_t dataLen = outBuff.Length();
728 : uint32_t written;
729 72 : nsresult rv = aStream->Write(reinterpret_cast<char*>(&dataLen), sizeof(dataLen), &written);
730 72 : NS_ENSURE_SUCCESS(rv, rv);
731 :
732 72 : NS_ASSERTION(written == sizeof(dataLen), "Error writing deflate length");
733 :
734 : // Store to stream
735 72 : rv = WriteTArray(aStream, outBuff);
736 72 : NS_ENSURE_SUCCESS(rv, rv);
737 :
738 72 : return NS_OK;
739 : }
740 :
741 : template<class T>
742 72 : nsresult InflateReadTArray(nsIInputStream* aStream, FallibleTArray<T>* aOut,
743 : uint32_t aExpectedSize)
744 : {
745 :
746 : uint32_t inLen;
747 : uint32_t read;
748 72 : nsresult rv = aStream->Read(reinterpret_cast<char*>(&inLen), sizeof(inLen), &read);
749 72 : NS_ENSURE_SUCCESS(rv, rv);
750 :
751 72 : NS_ASSERTION(read == sizeof(inLen), "Error reading inflate length");
752 :
753 144 : FallibleTArray<char> inBuff;
754 72 : if (!inBuff.SetLength(inLen, fallible)) {
755 0 : return NS_ERROR_OUT_OF_MEMORY;
756 : }
757 :
758 72 : rv = ReadTArray(aStream, &inBuff, inLen);
759 72 : NS_ENSURE_SUCCESS(rv, rv);
760 :
761 72 : uLongf insize = inLen;
762 72 : uLongf outsize = aExpectedSize * sizeof(T);
763 72 : if (!aOut->SetLength(aExpectedSize, fallible)) {
764 0 : return NS_ERROR_OUT_OF_MEMORY;
765 : }
766 :
767 72 : int zerr = uncompress(reinterpret_cast<Bytef*>(aOut->Elements()),
768 : &outsize,
769 72 : reinterpret_cast<const Bytef*>(inBuff.Elements()),
770 72 : insize);
771 72 : if (zerr != Z_OK) {
772 0 : return NS_ERROR_FAILURE;
773 : }
774 72 : LOG(("InflateReadTArray: %lu in %lu out", insize, outsize));
775 :
776 72 : NS_ASSERTION(outsize == aExpectedSize * sizeof(T), "Decompression size mismatch");
777 :
778 72 : return NS_OK;
779 : }
780 :
781 : static nsresult
782 24 : ByteSliceWrite(nsIOutputStream* aOut, nsTArray<uint32_t>& aData)
783 : {
784 48 : nsTArray<uint8_t> slice;
785 24 : uint32_t count = aData.Length();
786 :
787 : // Only process one slice at a time to avoid using too much memory.
788 24 : if (!slice.SetLength(count, fallible)) {
789 0 : return NS_ERROR_OUT_OF_MEMORY;
790 : }
791 :
792 : // Process slice 1.
793 24 : for (uint32_t i = 0; i < count; i++) {
794 0 : slice[i] = (aData[i] >> 24);
795 : }
796 :
797 24 : nsresult rv = DeflateWriteTArray(aOut, slice);
798 24 : NS_ENSURE_SUCCESS(rv, rv);
799 :
800 : // Process slice 2.
801 24 : for (uint32_t i = 0; i < count; i++) {
802 0 : slice[i] = ((aData[i] >> 16) & 0xFF);
803 : }
804 :
805 24 : rv = DeflateWriteTArray(aOut, slice);
806 24 : NS_ENSURE_SUCCESS(rv, rv);
807 :
808 : // Process slice 3.
809 24 : for (uint32_t i = 0; i < count; i++) {
810 0 : slice[i] = ((aData[i] >> 8) & 0xFF);
811 : }
812 :
813 24 : rv = DeflateWriteTArray(aOut, slice);
814 24 : NS_ENSURE_SUCCESS(rv, rv);
815 :
816 : // Process slice 4.
817 24 : for (uint32_t i = 0; i < count; i++) {
818 0 : slice[i] = (aData[i] & 0xFF);
819 : }
820 :
821 : // The LSB slice is generally uncompressible, don't bother
822 : // compressing it.
823 24 : rv = WriteTArray(aOut, slice);
824 24 : NS_ENSURE_SUCCESS(rv, rv);
825 :
826 24 : return NS_OK;
827 : }
828 :
829 : static nsresult
830 24 : ByteSliceRead(nsIInputStream* aInStream, FallibleTArray<uint32_t>* aData, uint32_t count)
831 : {
832 48 : FallibleTArray<uint8_t> slice1;
833 48 : FallibleTArray<uint8_t> slice2;
834 48 : FallibleTArray<uint8_t> slice3;
835 48 : FallibleTArray<uint8_t> slice4;
836 :
837 24 : nsresult rv = InflateReadTArray(aInStream, &slice1, count);
838 24 : NS_ENSURE_SUCCESS(rv, rv);
839 :
840 24 : rv = InflateReadTArray(aInStream, &slice2, count);
841 24 : NS_ENSURE_SUCCESS(rv, rv);
842 :
843 24 : rv = InflateReadTArray(aInStream, &slice3, count);
844 24 : NS_ENSURE_SUCCESS(rv, rv);
845 :
846 24 : rv = ReadTArray(aInStream, &slice4, count);
847 24 : NS_ENSURE_SUCCESS(rv, rv);
848 :
849 24 : if (!aData->SetCapacity(count, fallible)) {
850 0 : return NS_ERROR_OUT_OF_MEMORY;
851 : }
852 :
853 24 : for (uint32_t i = 0; i < count; i++) {
854 0 : aData->AppendElement((slice1[i] << 24) |
855 0 : (slice2[i] << 16) |
856 0 : (slice3[i] << 8) |
857 0 : (slice4[i]),
858 0 : fallible);
859 : }
860 :
861 24 : return NS_OK;
862 : }
863 :
864 : nsresult
865 6 : HashStore::ReadAddPrefixes()
866 : {
867 12 : FallibleTArray<uint32_t> chunks;
868 6 : uint32_t count = mHeader.numAddPrefixes;
869 :
870 6 : nsresult rv = ByteSliceRead(mInputStream, &chunks, count);
871 6 : NS_ENSURE_SUCCESS(rv, rv);
872 :
873 6 : if (!mAddPrefixes.SetCapacity(count, fallible)) {
874 0 : return NS_ERROR_OUT_OF_MEMORY;
875 : }
876 6 : for (uint32_t i = 0; i < count; i++) {
877 0 : AddPrefix *add = mAddPrefixes.AppendElement(fallible);
878 0 : add->prefix.FromUint32(0);
879 0 : add->addChunk = chunks[i];
880 : }
881 :
882 6 : return NS_OK;
883 : }
884 :
885 : nsresult
886 6 : HashStore::ReadSubPrefixes()
887 : {
888 12 : FallibleTArray<uint32_t> addchunks;
889 12 : FallibleTArray<uint32_t> subchunks;
890 12 : FallibleTArray<uint32_t> prefixes;
891 6 : uint32_t count = mHeader.numSubPrefixes;
892 :
893 6 : nsresult rv = ByteSliceRead(mInputStream, &addchunks, count);
894 6 : NS_ENSURE_SUCCESS(rv, rv);
895 :
896 6 : rv = ByteSliceRead(mInputStream, &subchunks, count);
897 6 : NS_ENSURE_SUCCESS(rv, rv);
898 :
899 6 : rv = ByteSliceRead(mInputStream, &prefixes, count);
900 6 : NS_ENSURE_SUCCESS(rv, rv);
901 :
902 6 : if (!mSubPrefixes.SetCapacity(count, fallible)) {
903 0 : return NS_ERROR_OUT_OF_MEMORY;
904 : }
905 6 : for (uint32_t i = 0; i < count; i++) {
906 0 : SubPrefix *sub = mSubPrefixes.AppendElement(fallible);
907 0 : sub->addChunk = addchunks[i];
908 0 : sub->prefix.FromUint32(prefixes[i]);
909 0 : sub->subChunk = subchunks[i];
910 : }
911 :
912 6 : return NS_OK;
913 : }
914 :
915 : // Split up PrefixArray back into the constituents
916 : nsresult
917 6 : HashStore::WriteAddPrefixes(nsIOutputStream* aOut)
918 : {
919 12 : nsTArray<uint32_t> chunks;
920 6 : uint32_t count = mAddPrefixes.Length();
921 6 : if (!chunks.SetCapacity(count, fallible)) {
922 0 : return NS_ERROR_OUT_OF_MEMORY;
923 : }
924 :
925 6 : for (uint32_t i = 0; i < count; i++) {
926 0 : chunks.AppendElement(mAddPrefixes[i].Chunk());
927 : }
928 :
929 6 : nsresult rv = ByteSliceWrite(aOut, chunks);
930 6 : NS_ENSURE_SUCCESS(rv, rv);
931 :
932 6 : return NS_OK;
933 : }
934 :
935 : nsresult
936 6 : HashStore::WriteSubPrefixes(nsIOutputStream* aOut)
937 : {
938 12 : nsTArray<uint32_t> addchunks;
939 12 : nsTArray<uint32_t> subchunks;
940 12 : nsTArray<uint32_t> prefixes;
941 6 : uint32_t count = mSubPrefixes.Length();
942 6 : addchunks.SetCapacity(count);
943 6 : subchunks.SetCapacity(count);
944 6 : prefixes.SetCapacity(count);
945 :
946 6 : for (uint32_t i = 0; i < count; i++) {
947 0 : addchunks.AppendElement(mSubPrefixes[i].AddChunk());
948 0 : prefixes.AppendElement(mSubPrefixes[i].PrefixHash().ToUint32());
949 0 : subchunks.AppendElement(mSubPrefixes[i].Chunk());
950 : }
951 :
952 6 : nsresult rv = ByteSliceWrite(aOut, addchunks);
953 6 : NS_ENSURE_SUCCESS(rv, rv);
954 :
955 6 : rv = ByteSliceWrite(aOut, subchunks);
956 6 : NS_ENSURE_SUCCESS(rv, rv);
957 :
958 6 : rv = ByteSliceWrite(aOut, prefixes);
959 6 : NS_ENSURE_SUCCESS(rv, rv);
960 :
961 6 : return NS_OK;
962 : }
963 :
964 : nsresult
965 6 : HashStore::WriteFile()
966 : {
967 6 : NS_ASSERTION(mInUpdate, "Must be in update to write database.");
968 6 : if (nsUrlClassifierDBService::ShutdownHasStarted()) {
969 0 : return NS_ERROR_ABORT;
970 : }
971 :
972 12 : nsCOMPtr<nsIFile> storeFile;
973 6 : nsresult rv = mStoreDirectory->Clone(getter_AddRefs(storeFile));
974 6 : NS_ENSURE_SUCCESS(rv, rv);
975 6 : rv = storeFile->AppendNative(mTableName + NS_LITERAL_CSTRING(".sbstore"));
976 6 : NS_ENSURE_SUCCESS(rv, rv);
977 :
978 12 : nsCOMPtr<nsIOutputStream> out;
979 6 : rv = NS_NewCheckSummedOutputStream(getter_AddRefs(out), storeFile);
980 6 : NS_ENSURE_SUCCESS(rv, rv);
981 :
982 : uint32_t written;
983 6 : rv = out->Write(reinterpret_cast<char*>(&mHeader), sizeof(mHeader), &written);
984 6 : NS_ENSURE_SUCCESS(rv, rv);
985 :
986 : // Write chunk numbers.
987 6 : rv = mAddChunks.Write(out);
988 6 : NS_ENSURE_SUCCESS(rv, rv);
989 :
990 6 : rv = mSubChunks.Write(out);
991 6 : NS_ENSURE_SUCCESS(rv, rv);
992 :
993 : // Write hashes.
994 6 : rv = WriteAddPrefixes(out);
995 6 : NS_ENSURE_SUCCESS(rv, rv);
996 :
997 6 : rv = WriteSubPrefixes(out);
998 6 : NS_ENSURE_SUCCESS(rv, rv);
999 :
1000 6 : rv = WriteTArray(out, mAddCompletes);
1001 6 : NS_ENSURE_SUCCESS(rv, rv);
1002 :
1003 6 : rv = WriteTArray(out, mSubCompletes);
1004 6 : NS_ENSURE_SUCCESS(rv, rv);
1005 :
1006 12 : nsCOMPtr<nsISafeOutputStream> safeOut = do_QueryInterface(out, &rv);
1007 6 : NS_ENSURE_SUCCESS(rv, rv);
1008 :
1009 6 : rv = safeOut->Finish();
1010 6 : NS_ENSURE_SUCCESS(rv, rv);
1011 :
1012 6 : return NS_OK;
1013 : }
1014 :
1015 : template <class T>
1016 : static void
1017 36 : Erase(FallibleTArray<T>* array,
1018 : typename nsTArray<T>::iterator& iterStart,
1019 : typename nsTArray<T>::iterator& iterEnd)
1020 : {
1021 36 : uint32_t start = iterStart - array->begin();
1022 36 : uint32_t count = iterEnd - iterStart;
1023 :
1024 36 : if (count > 0) {
1025 0 : array->RemoveElementsAt(start, count);
1026 : }
1027 36 : }
1028 :
1029 : // Find items matching between |subs| and |adds|, and remove them,
1030 : // recording the item from |adds| in |adds_removed|. To minimize
1031 : // copies, the inputs are processing in parallel, so |subs| and |adds|
1032 : // should be compatibly ordered (either by SBAddPrefixLess or
1033 : // SBAddPrefixHashLess).
1034 : //
1035 : // |predAS| provides add < sub, |predSA| provides sub < add, for the
1036 : // tightest compare appropriate (see calls in SBProcessSubs).
1037 : template<class TSub, class TAdd>
1038 : static void
1039 12 : KnockoutSubs(FallibleTArray<TSub>* aSubs, FallibleTArray<TAdd>* aAdds)
1040 : {
1041 : // Keep a pair of output iterators for writing kept items. Due to
1042 : // deletions, these may lag the main iterators. Using erase() on
1043 : // individual items would result in O(N^2) copies. Using a list
1044 : // would work around that, at double or triple the memory cost.
1045 12 : auto addOut = aAdds->begin();
1046 12 : auto addIter = aAdds->begin();
1047 :
1048 12 : auto subOut = aSubs->begin();
1049 12 : auto subIter = aSubs->begin();
1050 :
1051 12 : auto addEnd = aAdds->end();
1052 12 : auto subEnd = aSubs->end();
1053 :
1054 12 : while (addIter != addEnd && subIter != subEnd) {
1055 : // additer compare, so it compares on add chunk
1056 0 : int32_t cmp = addIter->Compare(*subIter);
1057 0 : if (cmp > 0) {
1058 : // If |*sub_iter| < |*add_iter|, retain the sub.
1059 0 : *subOut = *subIter;
1060 0 : ++subOut;
1061 0 : ++subIter;
1062 0 : } else if (cmp < 0) {
1063 : // If |*add_iter| < |*sub_iter|, retain the add.
1064 0 : *addOut = *addIter;
1065 0 : ++addOut;
1066 0 : ++addIter;
1067 : } else {
1068 : // Drop equal items
1069 0 : ++addIter;
1070 0 : ++subIter;
1071 : }
1072 : }
1073 :
1074 12 : Erase(aAdds, addOut, addIter);
1075 12 : Erase(aSubs, subOut, subIter);
1076 12 : }
1077 :
1078 : // Remove items in |removes| from |fullHashes|. |fullHashes| and
1079 : // |removes| should be ordered by SBAddPrefix component.
1080 : template <class T>
1081 : static void
1082 12 : RemoveMatchingPrefixes(const SubPrefixArray& aSubs, FallibleTArray<T>* aFullHashes)
1083 : {
1084 : // Where to store kept items.
1085 12 : auto out = aFullHashes->begin();
1086 12 : auto hashIter = aFullHashes->begin();
1087 12 : auto hashEnd = aFullHashes->end();
1088 :
1089 12 : auto removeIter = aSubs.begin();
1090 12 : auto removeEnd = aSubs.end();
1091 :
1092 12 : while (hashIter != hashEnd && removeIter != removeEnd) {
1093 0 : int32_t cmp = removeIter->CompareAlt(*hashIter);
1094 0 : if (cmp > 0) {
1095 : // Keep items less than |*removeIter|.
1096 0 : *out = *hashIter;
1097 0 : ++out;
1098 0 : ++hashIter;
1099 0 : } else if (cmp < 0) {
1100 : // No hit for |*removeIter|, bump it forward.
1101 0 : ++removeIter;
1102 : } else {
1103 : // Drop equal items, there may be multiple hits.
1104 0 : do {
1105 0 : ++hashIter;
1106 0 : } while (hashIter != hashEnd &&
1107 0 : !(removeIter->CompareAlt(*hashIter) < 0));
1108 0 : ++removeIter;
1109 : }
1110 : }
1111 12 : Erase(aFullHashes, out, hashIter);
1112 12 : }
1113 :
1114 : static void
1115 6 : RemoveDeadSubPrefixes(SubPrefixArray& aSubs, ChunkSet& aAddChunks)
1116 : {
1117 6 : auto subIter = aSubs.begin();
1118 :
1119 6 : for (const auto& sub : aSubs) {
1120 0 : bool hasChunk = aAddChunks.Has(sub.AddChunk());
1121 : // Keep the subprefix if the chunk it refers to is one
1122 : // we haven't seen it yet.
1123 0 : if (!hasChunk) {
1124 0 : *subIter = sub;
1125 0 : subIter++;
1126 : }
1127 : }
1128 :
1129 6 : LOG(("Removed %" PRId64 " dead SubPrefix entries.",
1130 : static_cast<int64_t>(aSubs.end() - subIter)));
1131 6 : aSubs.TruncateLength(subIter - aSubs.begin());
1132 6 : }
1133 :
1134 : #ifdef DEBUG
1135 : template <class T>
1136 48 : static void EnsureSorted(FallibleTArray<T>* aArray)
1137 : {
1138 48 : auto start = aArray->begin();
1139 48 : auto end = aArray->end();
1140 48 : auto iter = start;
1141 48 : auto previous = start;
1142 :
1143 76 : while (iter != end) {
1144 14 : previous = iter;
1145 14 : ++iter;
1146 14 : if (iter != end) {
1147 2 : MOZ_ASSERT(iter->Compare(*previous) >= 0);
1148 : }
1149 : }
1150 :
1151 48 : return;
1152 : }
1153 : #endif
1154 :
1155 : nsresult
1156 6 : HashStore::ProcessSubs()
1157 : {
1158 : #ifdef DEBUG
1159 6 : EnsureSorted(&mAddPrefixes);
1160 6 : EnsureSorted(&mSubPrefixes);
1161 6 : EnsureSorted(&mAddCompletes);
1162 6 : EnsureSorted(&mSubCompletes);
1163 6 : LOG(("All databases seem to have a consistent sort order."));
1164 : #endif
1165 :
1166 6 : RemoveMatchingPrefixes(mSubPrefixes, &mAddCompletes);
1167 6 : RemoveMatchingPrefixes(mSubPrefixes, &mSubCompletes);
1168 :
1169 : // Remove any remaining subbed prefixes from both addprefixes
1170 : // and addcompletes.
1171 6 : KnockoutSubs(&mSubPrefixes, &mAddPrefixes);
1172 6 : KnockoutSubs(&mSubCompletes, &mAddCompletes);
1173 :
1174 : // Remove any remaining subprefixes referring to addchunks that
1175 : // we have (and hence have been processed above).
1176 6 : RemoveDeadSubPrefixes(mSubPrefixes, mAddChunks);
1177 :
1178 : #ifdef DEBUG
1179 6 : EnsureSorted(&mAddPrefixes);
1180 6 : EnsureSorted(&mSubPrefixes);
1181 6 : EnsureSorted(&mAddCompletes);
1182 6 : EnsureSorted(&mSubCompletes);
1183 6 : LOG(("All databases seem to have a consistent sort order."));
1184 : #endif
1185 :
1186 6 : return NS_OK;
1187 : }
1188 :
1189 : nsresult
1190 6 : HashStore::AugmentAdds(const nsTArray<uint32_t>& aPrefixes)
1191 : {
1192 6 : uint32_t cnt = aPrefixes.Length();
1193 6 : if (cnt != mAddPrefixes.Length()) {
1194 0 : LOG(("Amount of prefixes in cache not consistent with store (%" PRIuSIZE " vs %" PRIuSIZE ")",
1195 : aPrefixes.Length(), mAddPrefixes.Length()));
1196 0 : return NS_ERROR_FAILURE;
1197 : }
1198 6 : for (uint32_t i = 0; i < cnt; i++) {
1199 0 : mAddPrefixes[i].prefix.FromUint32(aPrefixes[i]);
1200 : }
1201 6 : return NS_OK;
1202 : }
1203 :
1204 : ChunkSet&
1205 24 : HashStore::AddChunks()
1206 : {
1207 24 : ReadChunkNumbers();
1208 :
1209 24 : return mAddChunks;
1210 : }
1211 :
1212 : ChunkSet&
1213 24 : HashStore::SubChunks()
1214 : {
1215 24 : ReadChunkNumbers();
1216 :
1217 24 : return mSubChunks;
1218 : }
1219 :
1220 : AddCompleteArray&
1221 19 : HashStore::AddCompletes()
1222 : {
1223 19 : ReadCompletions();
1224 :
1225 19 : return mAddCompletes;
1226 : }
1227 :
1228 : SubCompleteArray&
1229 0 : HashStore::SubCompletes()
1230 : {
1231 0 : ReadCompletions();
1232 :
1233 0 : return mSubCompletes;
1234 : }
1235 :
1236 : bool
1237 54 : HashStore::AlreadyReadChunkNumbers()
1238 : {
1239 : // If there are chunks but chunk set not yet contains any data
1240 : // Then we haven't read chunk numbers.
1241 108 : if ((mHeader.numAddChunks != 0 && mAddChunks.Length() == 0) ||
1242 24 : (mHeader.numSubChunks != 0 && mSubChunks.Length() == 0)) {
1243 30 : return false;
1244 : }
1245 24 : return true;
1246 : }
1247 :
1248 : bool
1249 24 : HashStore::AlreadyReadCompletions()
1250 : {
1251 : // If there are completions but completion set not yet contains any data
1252 : // Then we haven't read completions.
1253 48 : if ((mHeader.numAddCompletes != 0 && mAddCompletes.Length() == 0) ||
1254 6 : (mHeader.numSubCompletes != 0 && mSubCompletes.Length() == 0)) {
1255 18 : return false;
1256 : }
1257 6 : return true;
1258 : }
1259 :
1260 : } // namespace safebrowsing
1261 : } // namespace mozilla
|
