The Tor Browser: toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp@925c144e1f1f

     1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

     2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */

     3 /* This Source Code Form is subject to the terms of the Mozilla Public

     4  * License, v. 2.0. If a copy of the MPL was not distributed with this

     5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     7 #include "nsAutoPtr.h"

     8 #include "nsCOMPtr.h"

     9 #include "nsDebug.h"

    10 #include "nsPrintfCString.h"

    11 #include "nsTArray.h"

    12 #include "nsString.h"

    13 #include "nsUrlClassifierPrefixSet.h"

    14 #include "nsIUrlClassifierPrefixSet.h"

    15 #include "nsIRandomGenerator.h"

    16 #include "nsIFile.h"

    17 #include "nsToolkitCompsCID.h"

    18 #include "nsTArray.h"

    19 #include "nsThreadUtils.h"

    20 #include "mozilla/MemoryReporting.h"

    21 #include "mozilla/Mutex.h"

    22 #include "mozilla/Telemetry.h"

    23 #include "mozilla/FileUtils.h"

    24 #include "prlog.h"

    26 using namespace mozilla;

    28 // NSPR_LOG_MODULES=UrlClassifierPrefixSet:5

    29 #if defined(PR_LOGGING)

    30 static const PRLogModuleInfo *gUrlClassifierPrefixSetLog = nullptr;

    31 #define LOG(args) PR_LOG(gUrlClassifierPrefixSetLog, PR_LOG_DEBUG, args)

    32 #define LOG_ENABLED() PR_LOG_TEST(gUrlClassifierPrefixSetLog, 4)

    33 #else

    34 #define LOG(args)

    35 #define LOG_ENABLED() (false)

    36 #endif

    38 NS_IMPL_ISUPPORTS(

    39   nsUrlClassifierPrefixSet, nsIUrlClassifierPrefixSet, nsIMemoryReporter)

    41 nsUrlClassifierPrefixSet::nsUrlClassifierPrefixSet()

    42   : mHasPrefixes(false)

    43   , mMemoryReportPath()

    44 {

    45 #if defined(PR_LOGGING)

    46   if (!gUrlClassifierPrefixSetLog)

    47     gUrlClassifierPrefixSetLog = PR_NewLogModule("UrlClassifierPrefixSet");

    48 #endif

    49 }

    51 NS_IMETHODIMP

    52 nsUrlClassifierPrefixSet::Init(const nsACString& aName)

    53 {

    54   mMemoryReportPath =

    55     nsPrintfCString(

    56       "explicit/storage/prefix-set/%s",

    57       (!aName.IsEmpty() ? PromiseFlatCString(aName).get() : "?!")

    58     );

    60   RegisterWeakMemoryReporter(this);

    62   return NS_OK;

    63 }

    65 nsUrlClassifierPrefixSet::~nsUrlClassifierPrefixSet()

    66 {

    67   UnregisterWeakMemoryReporter(this);

    68 }

    70 NS_IMETHODIMP

    71 nsUrlClassifierPrefixSet::SetPrefixes(const uint32_t* aArray, uint32_t aLength)

    72 {

    73   if (aLength <= 0) {

    74     if (mHasPrefixes) {

    75       LOG(("Clearing PrefixSet"));

    76       mDeltas.Clear();

    77       mIndexPrefixes.Clear();

    78       mIndexStarts.Clear();

    79       mHasPrefixes = false;

    80     }

    81   } else {

    82     return MakePrefixSet(aArray, aLength);

    83   }

    85   return NS_OK;

    86 }

    88 nsresult

    89 nsUrlClassifierPrefixSet::MakePrefixSet(const uint32_t* aPrefixes, uint32_t aLength)

    90 {

    91   if (aLength == 0) {

    92     return NS_OK;

    93   }

    95 #ifdef DEBUG

    96   for (uint32_t i = 1; i < aLength; i++) {

    97     MOZ_ASSERT(aPrefixes[i] >= aPrefixes[i-1]);

    98   }

    99 #endif

   101   mIndexPrefixes.Clear();

   102   mIndexStarts.Clear();

   103   mDeltas.Clear();

   105   mIndexPrefixes.AppendElement(aPrefixes[0]);

   106   mIndexStarts.AppendElement(mDeltas.Length());

   108   uint32_t numOfDeltas = 0;

   109   uint32_t currentItem = aPrefixes[0];

   110   for (uint32_t i = 1; i < aLength; i++) {

   111     if ((numOfDeltas >= DELTAS_LIMIT) ||

   112           (aPrefixes[i] - currentItem >= MAX_INDEX_DIFF)) {

   113       mIndexStarts.AppendElement(mDeltas.Length());

   114       mIndexPrefixes.AppendElement(aPrefixes[i]);

   115       numOfDeltas = 0;

   116     } else {

   117       uint16_t delta = aPrefixes[i] - currentItem;

   118       mDeltas.AppendElement(delta);

   119       numOfDeltas++;

   120     }

   121     currentItem = aPrefixes[i];

   122   }

   124   mIndexPrefixes.Compact();

   125   mIndexStarts.Compact();

   126   mDeltas.Compact();

   128   LOG(("Total number of indices: %d", mIndexPrefixes.Length()));

   129   LOG(("Total number of deltas: %d", mDeltas.Length()));

   131   mHasPrefixes = true;

   133   return NS_OK;

   134 }

   136 NS_IMETHODIMP

   137 nsUrlClassifierPrefixSet::GetPrefixes(uint32_t* aCount,

   138                                       uint32_t** aPrefixes)

   139 {

   140   NS_ENSURE_ARG_POINTER(aCount);

   141   *aCount = 0;

   142   NS_ENSURE_ARG_POINTER(aPrefixes);

   143   *aPrefixes = nullptr;

   145   nsTArray<uint32_t> aArray;

   146   uint32_t prefixLength = mIndexPrefixes.Length();

   148   for (uint32_t i = 0; i < prefixLength; i++) {

   149     uint32_t prefix = mIndexPrefixes[i];

   150     uint32_t start = mIndexStarts[i];

   151     uint32_t end = (i == (prefixLength - 1)) ? mDeltas.Length()

   152                                              : mIndexStarts[i + 1];

   153     if (end > mDeltas.Length()) {

   154       return NS_ERROR_FILE_CORRUPTED;

   155     }

   157     aArray.AppendElement(prefix);

   158     for (uint32_t j = start; j < end; j++) {

   159       prefix += mDeltas[j];

   160       aArray.AppendElement(prefix);

   161     }

   162   }

   164   NS_ASSERTION(mIndexStarts.Length() + mDeltas.Length() == aArray.Length(),

   165                "Lengths are inconsistent");

   167   uint32_t itemCount = aArray.Length();

   169   uint32_t* retval = static_cast<uint32_t*>(nsMemory::Alloc(itemCount * sizeof(uint32_t)));

   170   NS_ENSURE_TRUE(retval, NS_ERROR_OUT_OF_MEMORY);

   171   for (uint32_t i = 0; i < itemCount; i++) {

   172     retval[i] = aArray[i];

   173   }

   175   *aCount = itemCount;

   176   *aPrefixes = retval;

   178   return NS_OK;

   179 }

   181 uint32_t nsUrlClassifierPrefixSet::BinSearch(uint32_t start,

   182                                              uint32_t end,

   183                                              uint32_t target)

   184 {

   185   while (start != end && end >= start) {

   186     uint32_t i = start + ((end - start) >> 1);

   187     uint32_t value = mIndexPrefixes[i];

   188     if (value < target) {

   189       start = i + 1;

   190     } else if (value > target) {

   191       end = i - 1;

   192     } else {

   193       return i;

   194     }

   195   }

   196   return end;

   197 }

   199 NS_IMETHODIMP

   200 nsUrlClassifierPrefixSet::Contains(uint32_t aPrefix, bool* aFound)

   201 {

   202   *aFound = false;

   204   if (!mHasPrefixes) {

   205     return NS_OK;

   206   }

   208   uint32_t target = aPrefix;

   210   // We want to do a "Price is Right" binary search, that is, we want to find

   211   // the index of the value either equal to the target or the closest value

   212   // that is less than the target.

   213   //

   214   if (target < mIndexPrefixes[0]) {

   215     return NS_OK;

   216   }

   218   // |binsearch| does not necessarily return the correct index (when the

   219   // target is not found) but rather it returns an index at least one away

   220   // from the correct index.

   221   // Because of this, we need to check if the target lies before the beginning

   222   // of the indices.

   224   uint32_t i = BinSearch(0, mIndexPrefixes.Length() - 1, target);

   225   if (mIndexPrefixes[i] > target && i > 0) {

   226     i--;

   227   }

   229   // Now search through the deltas for the target.

   230   uint32_t diff = target - mIndexPrefixes[i];

   231   uint32_t deltaIndex = mIndexStarts[i];

   232   uint32_t deltaSize  = mDeltas.Length();

   233   uint32_t end = (i + 1 < mIndexStarts.Length()) ? mIndexStarts[i+1]

   234                                                  : deltaSize;

   236   // Sanity check the read values

   237   if (end > deltaSize) {

   238     return NS_ERROR_FILE_CORRUPTED;

   239   }

   241   while (diff > 0 && deltaIndex < end) {

   242     diff -= mDeltas[deltaIndex];

   243     deltaIndex++;

   244   }

   246   if (diff == 0) {

   247     *aFound = true;

   248   }

   250   return NS_OK;

   251 }

   253 MOZ_DEFINE_MALLOC_SIZE_OF(UrlClassifierMallocSizeOf)

   255 NS_IMETHODIMP

   256 nsUrlClassifierPrefixSet::CollectReports(nsIHandleReportCallback* aHandleReport,

   257                                          nsISupports* aData)

   258 {

   259   return aHandleReport->Callback(

   260     EmptyCString(), mMemoryReportPath, KIND_HEAP, UNITS_BYTES,

   261     SizeOfIncludingThis(UrlClassifierMallocSizeOf),

   262     NS_LITERAL_CSTRING("Memory used by the prefix set for a URL classifier."),

   263     aData);

   264 }

   266 size_t

   267 nsUrlClassifierPrefixSet::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf)

   268 {

   269   size_t n = 0;

   270   n += aMallocSizeOf(this);

   271   n += mDeltas.SizeOfExcludingThis(aMallocSizeOf);

   272   n += mIndexPrefixes.SizeOfExcludingThis(aMallocSizeOf);

   273   n += mIndexStarts.SizeOfExcludingThis(aMallocSizeOf);

   274   return n;

   275 }

   277 NS_IMETHODIMP

   278 nsUrlClassifierPrefixSet::IsEmpty(bool * aEmpty)

   279 {

   280   *aEmpty = !mHasPrefixes;

   281   return NS_OK;

   282 }

   284 nsresult

   285 nsUrlClassifierPrefixSet::LoadFromFd(AutoFDClose& fileFd)

   286 {

   287   uint32_t magic;

   288   int32_t read;

   290   read = PR_Read(fileFd, &magic, sizeof(uint32_t));

   291   NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FAILURE);

   293   if (magic == PREFIXSET_VERSION_MAGIC) {

   294     uint32_t indexSize;

   295     uint32_t deltaSize;

   297     read = PR_Read(fileFd, &indexSize, sizeof(uint32_t));

   298     NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FILE_CORRUPTED);

   299     read = PR_Read(fileFd, &deltaSize, sizeof(uint32_t));

   300     NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FILE_CORRUPTED);

   302     if (indexSize == 0) {

   303       LOG(("stored PrefixSet is empty!"));

   304       return NS_OK;

   305     }

   307     if (deltaSize > (indexSize * DELTAS_LIMIT)) {

   308       return NS_ERROR_FILE_CORRUPTED;

   309     }

   311     mIndexStarts.SetLength(indexSize);

   312     mIndexPrefixes.SetLength(indexSize);

   313     mDeltas.SetLength(deltaSize);

   315     int32_t toRead = indexSize*sizeof(uint32_t);

   316     read = PR_Read(fileFd, mIndexPrefixes.Elements(), toRead);

   317     NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);

   318     read = PR_Read(fileFd, mIndexStarts.Elements(), toRead);

   319     NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);

   320     if (deltaSize > 0) {

   321       toRead = deltaSize*sizeof(uint16_t);

   322       read = PR_Read(fileFd, mDeltas.Elements(), toRead);

   323       NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);

   324     }

   326     mHasPrefixes = true;

   327   } else {

   328     LOG(("Version magic mismatch, not loading"));

   329     return NS_ERROR_FILE_CORRUPTED;

   330   }

   332   LOG(("Loading PrefixSet successful"));

   334   return NS_OK;

   335 }

   337 NS_IMETHODIMP

   338 nsUrlClassifierPrefixSet::LoadFromFile(nsIFile* aFile)

   339 {

   340   Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_FILELOAD_TIME> timer;

   342   nsresult rv;

   343   AutoFDClose fileFd;

   344   rv = aFile->OpenNSPRFileDesc(PR_RDONLY | nsIFile::OS_READAHEAD,

   345                                0, &fileFd.rwget());

   346   NS_ENSURE_SUCCESS(rv, rv);

   348   return LoadFromFd(fileFd);

   349 }

   351 nsresult

   352 nsUrlClassifierPrefixSet::StoreToFd(AutoFDClose& fileFd)

   353 {

   354   {

   355       Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_FALLOCATE_TIME> timer;

   356       int64_t size = 4 * sizeof(uint32_t);

   357       size += 2 * mIndexStarts.Length() * sizeof(uint32_t);

   358       size +=     mDeltas.Length() * sizeof(uint16_t);

   360       mozilla::fallocate(fileFd, size);

   361   }

   363   int32_t written;

   364   int32_t writelen = sizeof(uint32_t);

   365   uint32_t magic = PREFIXSET_VERSION_MAGIC;

   366   written = PR_Write(fileFd, &magic, writelen);

   367   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);

   369   uint32_t indexSize = mIndexStarts.Length();

   370   uint32_t deltaSize = mDeltas.Length();

   371   written = PR_Write(fileFd, &indexSize, writelen);

   372   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);

   373   written = PR_Write(fileFd, &deltaSize, writelen);

   374   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);

   376   writelen = indexSize * sizeof(uint32_t);

   377   written = PR_Write(fileFd, mIndexPrefixes.Elements(), writelen);

   378   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);

   379   written = PR_Write(fileFd, mIndexStarts.Elements(), writelen);

   380   NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);

   381   if (deltaSize > 0) {

   382     writelen = deltaSize * sizeof(uint16_t);

   383     written = PR_Write(fileFd, mDeltas.Elements(), writelen);

   384     NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);

   385   }

   387   LOG(("Saving PrefixSet successful\n"));

   389   return NS_OK;

   390 }

   392 NS_IMETHODIMP

   393 nsUrlClassifierPrefixSet::StoreToFile(nsIFile* aFile)

   394 {

   395   AutoFDClose fileFd;

   396   nsresult rv = aFile->OpenNSPRFileDesc(PR_RDWR | PR_TRUNCATE | PR_CREATE_FILE,

   397                                         0644, &fileFd.rwget());

   398   NS_ENSURE_SUCCESS(rv, rv);

   400   return StoreToFd(fileFd);

   401 }

The Tor Browser / file revision

toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp@925c144e1f1f

toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp