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