michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=8 sts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "nsAutoPtr.h"
michael@0: #include "nsCOMPtr.h"
michael@0: #include "nsDebug.h"
michael@0: #include "nsPrintfCString.h"
michael@0: #include "nsTArray.h"
michael@0: #include "nsString.h"
michael@0: #include "nsUrlClassifierPrefixSet.h"
michael@0: #include "nsIUrlClassifierPrefixSet.h"
michael@0: #include "nsIRandomGenerator.h"
michael@0: #include "nsIFile.h"
michael@0: #include "nsToolkitCompsCID.h"
michael@0: #include "nsTArray.h"
michael@0: #include "nsThreadUtils.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/Mutex.h"
michael@0: #include "mozilla/Telemetry.h"
michael@0: #include "mozilla/FileUtils.h"
michael@0: #include "prlog.h"
michael@0: 
michael@0: using namespace mozilla;
michael@0: 
michael@0: // NSPR_LOG_MODULES=UrlClassifierPrefixSet:5
michael@0: #if defined(PR_LOGGING)
michael@0: static const PRLogModuleInfo *gUrlClassifierPrefixSetLog = nullptr;
michael@0: #define LOG(args) PR_LOG(gUrlClassifierPrefixSetLog, PR_LOG_DEBUG, args)
michael@0: #define LOG_ENABLED() PR_LOG_TEST(gUrlClassifierPrefixSetLog, 4)
michael@0: #else
michael@0: #define LOG(args)
michael@0: #define LOG_ENABLED() (false)
michael@0: #endif
michael@0: 
michael@0: NS_IMPL_ISUPPORTS(
michael@0:   nsUrlClassifierPrefixSet, nsIUrlClassifierPrefixSet, nsIMemoryReporter)
michael@0: 
michael@0: nsUrlClassifierPrefixSet::nsUrlClassifierPrefixSet()
michael@0:   : mHasPrefixes(false)
michael@0:   , mMemoryReportPath()
michael@0: {
michael@0: #if defined(PR_LOGGING)
michael@0:   if (!gUrlClassifierPrefixSetLog)
michael@0:     gUrlClassifierPrefixSetLog = PR_NewLogModule("UrlClassifierPrefixSet");
michael@0: #endif
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::Init(const nsACString& aName)
michael@0: {
michael@0:   mMemoryReportPath =
michael@0:     nsPrintfCString(
michael@0:       "explicit/storage/prefix-set/%s",
michael@0:       (!aName.IsEmpty() ? PromiseFlatCString(aName).get() : "?!")
michael@0:     );
michael@0: 
michael@0:   RegisterWeakMemoryReporter(this);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsUrlClassifierPrefixSet::~nsUrlClassifierPrefixSet()
michael@0: {
michael@0:   UnregisterWeakMemoryReporter(this);
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::SetPrefixes(const uint32_t* aArray, uint32_t aLength)
michael@0: {
michael@0:   if (aLength <= 0) {
michael@0:     if (mHasPrefixes) {
michael@0:       LOG(("Clearing PrefixSet"));
michael@0:       mDeltas.Clear();
michael@0:       mIndexPrefixes.Clear();
michael@0:       mIndexStarts.Clear();
michael@0:       mHasPrefixes = false;
michael@0:     }
michael@0:   } else {
michael@0:     return MakePrefixSet(aArray, aLength);
michael@0:   }
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsUrlClassifierPrefixSet::MakePrefixSet(const uint32_t* aPrefixes, uint32_t aLength)
michael@0: {
michael@0:   if (aLength == 0) {
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   for (uint32_t i = 1; i < aLength; i++) {
michael@0:     MOZ_ASSERT(aPrefixes[i] >= aPrefixes[i-1]);
michael@0:   }
michael@0: #endif
michael@0: 
michael@0:   mIndexPrefixes.Clear();
michael@0:   mIndexStarts.Clear();
michael@0:   mDeltas.Clear();
michael@0: 
michael@0:   mIndexPrefixes.AppendElement(aPrefixes[0]);
michael@0:   mIndexStarts.AppendElement(mDeltas.Length());
michael@0: 
michael@0:   uint32_t numOfDeltas = 0;
michael@0:   uint32_t currentItem = aPrefixes[0];
michael@0:   for (uint32_t i = 1; i < aLength; i++) {
michael@0:     if ((numOfDeltas >= DELTAS_LIMIT) ||
michael@0:           (aPrefixes[i] - currentItem >= MAX_INDEX_DIFF)) {
michael@0:       mIndexStarts.AppendElement(mDeltas.Length());
michael@0:       mIndexPrefixes.AppendElement(aPrefixes[i]);
michael@0:       numOfDeltas = 0;
michael@0:     } else {
michael@0:       uint16_t delta = aPrefixes[i] - currentItem;
michael@0:       mDeltas.AppendElement(delta);
michael@0:       numOfDeltas++;
michael@0:     }
michael@0:     currentItem = aPrefixes[i];
michael@0:   }
michael@0: 
michael@0:   mIndexPrefixes.Compact();
michael@0:   mIndexStarts.Compact();
michael@0:   mDeltas.Compact();
michael@0: 
michael@0:   LOG(("Total number of indices: %d", mIndexPrefixes.Length()));
michael@0:   LOG(("Total number of deltas: %d", mDeltas.Length()));
michael@0: 
michael@0:   mHasPrefixes = true;
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::GetPrefixes(uint32_t* aCount,
michael@0:                                       uint32_t** aPrefixes)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aCount);
michael@0:   *aCount = 0;
michael@0:   NS_ENSURE_ARG_POINTER(aPrefixes);
michael@0:   *aPrefixes = nullptr;
michael@0: 
michael@0:   nsTArray<uint32_t> aArray;
michael@0:   uint32_t prefixLength = mIndexPrefixes.Length();
michael@0: 
michael@0:   for (uint32_t i = 0; i < prefixLength; i++) {
michael@0:     uint32_t prefix = mIndexPrefixes[i];
michael@0:     uint32_t start = mIndexStarts[i];
michael@0:     uint32_t end = (i == (prefixLength - 1)) ? mDeltas.Length()
michael@0:                                              : mIndexStarts[i + 1];
michael@0:     if (end > mDeltas.Length()) {
michael@0:       return NS_ERROR_FILE_CORRUPTED;
michael@0:     }
michael@0: 
michael@0:     aArray.AppendElement(prefix);
michael@0:     for (uint32_t j = start; j < end; j++) {
michael@0:       prefix += mDeltas[j];
michael@0:       aArray.AppendElement(prefix);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   NS_ASSERTION(mIndexStarts.Length() + mDeltas.Length() == aArray.Length(),
michael@0:                "Lengths are inconsistent");
michael@0: 
michael@0:   uint32_t itemCount = aArray.Length();
michael@0: 
michael@0:   uint32_t* retval = static_cast<uint32_t*>(nsMemory::Alloc(itemCount * sizeof(uint32_t)));
michael@0:   NS_ENSURE_TRUE(retval, NS_ERROR_OUT_OF_MEMORY);
michael@0:   for (uint32_t i = 0; i < itemCount; i++) {
michael@0:     retval[i] = aArray[i];
michael@0:   }
michael@0: 
michael@0:   *aCount = itemCount;
michael@0:   *aPrefixes = retval;
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: uint32_t nsUrlClassifierPrefixSet::BinSearch(uint32_t start,
michael@0:                                              uint32_t end,
michael@0:                                              uint32_t target)
michael@0: {
michael@0:   while (start != end && end >= start) {
michael@0:     uint32_t i = start + ((end - start) >> 1);
michael@0:     uint32_t value = mIndexPrefixes[i];
michael@0:     if (value < target) {
michael@0:       start = i + 1;
michael@0:     } else if (value > target) {
michael@0:       end = i - 1;
michael@0:     } else {
michael@0:       return i;
michael@0:     }
michael@0:   }
michael@0:   return end;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::Contains(uint32_t aPrefix, bool* aFound)
michael@0: {
michael@0:   *aFound = false;
michael@0: 
michael@0:   if (!mHasPrefixes) {
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   uint32_t target = aPrefix;
michael@0: 
michael@0:   // We want to do a "Price is Right" binary search, that is, we want to find
michael@0:   // the index of the value either equal to the target or the closest value
michael@0:   // that is less than the target.
michael@0:   //
michael@0:   if (target < mIndexPrefixes[0]) {
michael@0:     return NS_OK;
michael@0:   }
michael@0: 
michael@0:   // |binsearch| does not necessarily return the correct index (when the
michael@0:   // target is not found) but rather it returns an index at least one away
michael@0:   // from the correct index.
michael@0:   // Because of this, we need to check if the target lies before the beginning
michael@0:   // of the indices.
michael@0: 
michael@0:   uint32_t i = BinSearch(0, mIndexPrefixes.Length() - 1, target);
michael@0:   if (mIndexPrefixes[i] > target && i > 0) {
michael@0:     i--;
michael@0:   }
michael@0: 
michael@0:   // Now search through the deltas for the target.
michael@0:   uint32_t diff = target - mIndexPrefixes[i];
michael@0:   uint32_t deltaIndex = mIndexStarts[i];
michael@0:   uint32_t deltaSize  = mDeltas.Length();
michael@0:   uint32_t end = (i + 1 < mIndexStarts.Length()) ? mIndexStarts[i+1]
michael@0:                                                  : deltaSize;
michael@0: 
michael@0:   // Sanity check the read values
michael@0:   if (end > deltaSize) {
michael@0:     return NS_ERROR_FILE_CORRUPTED;
michael@0:   }
michael@0: 
michael@0:   while (diff > 0 && deltaIndex < end) {
michael@0:     diff -= mDeltas[deltaIndex];
michael@0:     deltaIndex++;
michael@0:   }
michael@0: 
michael@0:   if (diff == 0) {
michael@0:     *aFound = true;
michael@0:   }
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: MOZ_DEFINE_MALLOC_SIZE_OF(UrlClassifierMallocSizeOf)
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::CollectReports(nsIHandleReportCallback* aHandleReport,
michael@0:                                          nsISupports* aData)
michael@0: {
michael@0:   return aHandleReport->Callback(
michael@0:     EmptyCString(), mMemoryReportPath, KIND_HEAP, UNITS_BYTES,
michael@0:     SizeOfIncludingThis(UrlClassifierMallocSizeOf),
michael@0:     NS_LITERAL_CSTRING("Memory used by the prefix set for a URL classifier."),
michael@0:     aData);
michael@0: }
michael@0: 
michael@0: size_t
michael@0: nsUrlClassifierPrefixSet::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf)
michael@0: {
michael@0:   size_t n = 0;
michael@0:   n += aMallocSizeOf(this);
michael@0:   n += mDeltas.SizeOfExcludingThis(aMallocSizeOf);
michael@0:   n += mIndexPrefixes.SizeOfExcludingThis(aMallocSizeOf);
michael@0:   n += mIndexStarts.SizeOfExcludingThis(aMallocSizeOf);
michael@0:   return n;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::IsEmpty(bool * aEmpty)
michael@0: {
michael@0:   *aEmpty = !mHasPrefixes;
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsUrlClassifierPrefixSet::LoadFromFd(AutoFDClose& fileFd)
michael@0: {
michael@0:   uint32_t magic;
michael@0:   int32_t read;
michael@0: 
michael@0:   read = PR_Read(fileFd, &magic, sizeof(uint32_t));
michael@0:   NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FAILURE);
michael@0: 
michael@0:   if (magic == PREFIXSET_VERSION_MAGIC) {
michael@0:     uint32_t indexSize;
michael@0:     uint32_t deltaSize;
michael@0: 
michael@0:     read = PR_Read(fileFd, &indexSize, sizeof(uint32_t));
michael@0:     NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FILE_CORRUPTED);
michael@0:     read = PR_Read(fileFd, &deltaSize, sizeof(uint32_t));
michael@0:     NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FILE_CORRUPTED);
michael@0: 
michael@0:     if (indexSize == 0) {
michael@0:       LOG(("stored PrefixSet is empty!"));
michael@0:       return NS_OK;
michael@0:     }
michael@0: 
michael@0:     if (deltaSize > (indexSize * DELTAS_LIMIT)) {
michael@0:       return NS_ERROR_FILE_CORRUPTED;
michael@0:     }
michael@0: 
michael@0:     mIndexStarts.SetLength(indexSize);
michael@0:     mIndexPrefixes.SetLength(indexSize);
michael@0:     mDeltas.SetLength(deltaSize);
michael@0: 
michael@0:     int32_t toRead = indexSize*sizeof(uint32_t);
michael@0:     read = PR_Read(fileFd, mIndexPrefixes.Elements(), toRead);
michael@0:     NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);
michael@0:     read = PR_Read(fileFd, mIndexStarts.Elements(), toRead);
michael@0:     NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);
michael@0:     if (deltaSize > 0) {
michael@0:       toRead = deltaSize*sizeof(uint16_t);
michael@0:       read = PR_Read(fileFd, mDeltas.Elements(), toRead);
michael@0:       NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);
michael@0:     }
michael@0: 
michael@0:     mHasPrefixes = true;
michael@0:   } else {
michael@0:     LOG(("Version magic mismatch, not loading"));
michael@0:     return NS_ERROR_FILE_CORRUPTED;
michael@0:   }
michael@0: 
michael@0:   LOG(("Loading PrefixSet successful"));
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::LoadFromFile(nsIFile* aFile)
michael@0: {
michael@0:   Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_FILELOAD_TIME> timer;
michael@0: 
michael@0:   nsresult rv;
michael@0:   AutoFDClose fileFd;
michael@0:   rv = aFile->OpenNSPRFileDesc(PR_RDONLY | nsIFile::OS_READAHEAD,
michael@0:                                0, &fileFd.rwget());
michael@0:   NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:   return LoadFromFd(fileFd);
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsUrlClassifierPrefixSet::StoreToFd(AutoFDClose& fileFd)
michael@0: {
michael@0:   {
michael@0:       Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_FALLOCATE_TIME> timer;
michael@0:       int64_t size = 4 * sizeof(uint32_t);
michael@0:       size += 2 * mIndexStarts.Length() * sizeof(uint32_t);
michael@0:       size +=     mDeltas.Length() * sizeof(uint16_t);
michael@0: 
michael@0:       mozilla::fallocate(fileFd, size);
michael@0:   }
michael@0: 
michael@0:   int32_t written;
michael@0:   int32_t writelen = sizeof(uint32_t);
michael@0:   uint32_t magic = PREFIXSET_VERSION_MAGIC;
michael@0:   written = PR_Write(fileFd, &magic, writelen);
michael@0:   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
michael@0: 
michael@0:   uint32_t indexSize = mIndexStarts.Length();
michael@0:   uint32_t deltaSize = mDeltas.Length();
michael@0:   written = PR_Write(fileFd, &indexSize, writelen);
michael@0:   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
michael@0:   written = PR_Write(fileFd, &deltaSize, writelen);
michael@0:   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
michael@0: 
michael@0:   writelen = indexSize * sizeof(uint32_t);
michael@0:   written = PR_Write(fileFd, mIndexPrefixes.Elements(), writelen);
michael@0:   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
michael@0:   written = PR_Write(fileFd, mIndexStarts.Elements(), writelen);
michael@0:   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
michael@0:   if (deltaSize > 0) {
michael@0:     writelen = deltaSize * sizeof(uint16_t);
michael@0:     written = PR_Write(fileFd, mDeltas.Elements(), writelen);
michael@0:     NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
michael@0:   }
michael@0: 
michael@0:   LOG(("Saving PrefixSet successful\n"));
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsUrlClassifierPrefixSet::StoreToFile(nsIFile* aFile)
michael@0: {
michael@0:   AutoFDClose fileFd;
michael@0:   nsresult rv = aFile->OpenNSPRFileDesc(PR_RDWR | PR_TRUNCATE | PR_CREATE_FILE,
michael@0:                                         0644, &fileFd.rwget());
michael@0:   NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:   return StoreToFd(fileFd);
michael@0: }