1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,401 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "nsAutoPtr.h"
1.11 +#include "nsCOMPtr.h"
1.12 +#include "nsDebug.h"
1.13 +#include "nsPrintfCString.h"
1.14 +#include "nsTArray.h"
1.15 +#include "nsString.h"
1.16 +#include "nsUrlClassifierPrefixSet.h"
1.17 +#include "nsIUrlClassifierPrefixSet.h"
1.18 +#include "nsIRandomGenerator.h"
1.19 +#include "nsIFile.h"
1.20 +#include "nsToolkitCompsCID.h"
1.21 +#include "nsTArray.h"
1.22 +#include "nsThreadUtils.h"
1.23 +#include "mozilla/MemoryReporting.h"
1.24 +#include "mozilla/Mutex.h"
1.25 +#include "mozilla/Telemetry.h"
1.26 +#include "mozilla/FileUtils.h"
1.27 +#include "prlog.h"
1.28 +
1.29 +using namespace mozilla;
1.30 +
1.31 +// NSPR_LOG_MODULES=UrlClassifierPrefixSet:5
1.32 +#if defined(PR_LOGGING)
1.33 +static const PRLogModuleInfo *gUrlClassifierPrefixSetLog = nullptr;
1.34 +#define LOG(args) PR_LOG(gUrlClassifierPrefixSetLog, PR_LOG_DEBUG, args)
1.35 +#define LOG_ENABLED() PR_LOG_TEST(gUrlClassifierPrefixSetLog, 4)
1.36 +#else
1.37 +#define LOG(args)
1.38 +#define LOG_ENABLED() (false)
1.39 +#endif
1.40 +
1.41 +NS_IMPL_ISUPPORTS(
1.42 + nsUrlClassifierPrefixSet, nsIUrlClassifierPrefixSet, nsIMemoryReporter)
1.43 +
1.44 +nsUrlClassifierPrefixSet::nsUrlClassifierPrefixSet()
1.45 + : mHasPrefixes(false)
1.46 + , mMemoryReportPath()
1.47 +{
1.48 +#if defined(PR_LOGGING)
1.49 + if (!gUrlClassifierPrefixSetLog)
1.50 + gUrlClassifierPrefixSetLog = PR_NewLogModule("UrlClassifierPrefixSet");
1.51 +#endif
1.52 +}
1.53 +
1.54 +NS_IMETHODIMP
1.55 +nsUrlClassifierPrefixSet::Init(const nsACString& aName)
1.56 +{
1.57 + mMemoryReportPath =
1.58 + nsPrintfCString(
1.59 + "explicit/storage/prefix-set/%s",
1.60 + (!aName.IsEmpty() ? PromiseFlatCString(aName).get() : "?!")
1.61 + );
1.62 +
1.63 + RegisterWeakMemoryReporter(this);
1.64 +
1.65 + return NS_OK;
1.66 +}
1.67 +
1.68 +nsUrlClassifierPrefixSet::~nsUrlClassifierPrefixSet()
1.69 +{
1.70 + UnregisterWeakMemoryReporter(this);
1.71 +}
1.72 +
1.73 +NS_IMETHODIMP
1.74 +nsUrlClassifierPrefixSet::SetPrefixes(const uint32_t* aArray, uint32_t aLength)
1.75 +{
1.76 + if (aLength <= 0) {
1.77 + if (mHasPrefixes) {
1.78 + LOG(("Clearing PrefixSet"));
1.79 + mDeltas.Clear();
1.80 + mIndexPrefixes.Clear();
1.81 + mIndexStarts.Clear();
1.82 + mHasPrefixes = false;
1.83 + }
1.84 + } else {
1.85 + return MakePrefixSet(aArray, aLength);
1.86 + }
1.87 +
1.88 + return NS_OK;
1.89 +}
1.90 +
1.91 +nsresult
1.92 +nsUrlClassifierPrefixSet::MakePrefixSet(const uint32_t* aPrefixes, uint32_t aLength)
1.93 +{
1.94 + if (aLength == 0) {
1.95 + return NS_OK;
1.96 + }
1.97 +
1.98 +#ifdef DEBUG
1.99 + for (uint32_t i = 1; i < aLength; i++) {
1.100 + MOZ_ASSERT(aPrefixes[i] >= aPrefixes[i-1]);
1.101 + }
1.102 +#endif
1.103 +
1.104 + mIndexPrefixes.Clear();
1.105 + mIndexStarts.Clear();
1.106 + mDeltas.Clear();
1.107 +
1.108 + mIndexPrefixes.AppendElement(aPrefixes[0]);
1.109 + mIndexStarts.AppendElement(mDeltas.Length());
1.110 +
1.111 + uint32_t numOfDeltas = 0;
1.112 + uint32_t currentItem = aPrefixes[0];
1.113 + for (uint32_t i = 1; i < aLength; i++) {
1.114 + if ((numOfDeltas >= DELTAS_LIMIT) ||
1.115 + (aPrefixes[i] - currentItem >= MAX_INDEX_DIFF)) {
1.116 + mIndexStarts.AppendElement(mDeltas.Length());
1.117 + mIndexPrefixes.AppendElement(aPrefixes[i]);
1.118 + numOfDeltas = 0;
1.119 + } else {
1.120 + uint16_t delta = aPrefixes[i] - currentItem;
1.121 + mDeltas.AppendElement(delta);
1.122 + numOfDeltas++;
1.123 + }
1.124 + currentItem = aPrefixes[i];
1.125 + }
1.126 +
1.127 + mIndexPrefixes.Compact();
1.128 + mIndexStarts.Compact();
1.129 + mDeltas.Compact();
1.130 +
1.131 + LOG(("Total number of indices: %d", mIndexPrefixes.Length()));
1.132 + LOG(("Total number of deltas: %d", mDeltas.Length()));
1.133 +
1.134 + mHasPrefixes = true;
1.135 +
1.136 + return NS_OK;
1.137 +}
1.138 +
1.139 +NS_IMETHODIMP
1.140 +nsUrlClassifierPrefixSet::GetPrefixes(uint32_t* aCount,
1.141 + uint32_t** aPrefixes)
1.142 +{
1.143 + NS_ENSURE_ARG_POINTER(aCount);
1.144 + *aCount = 0;
1.145 + NS_ENSURE_ARG_POINTER(aPrefixes);
1.146 + *aPrefixes = nullptr;
1.147 +
1.148 + nsTArray<uint32_t> aArray;
1.149 + uint32_t prefixLength = mIndexPrefixes.Length();
1.150 +
1.151 + for (uint32_t i = 0; i < prefixLength; i++) {
1.152 + uint32_t prefix = mIndexPrefixes[i];
1.153 + uint32_t start = mIndexStarts[i];
1.154 + uint32_t end = (i == (prefixLength - 1)) ? mDeltas.Length()
1.155 + : mIndexStarts[i + 1];
1.156 + if (end > mDeltas.Length()) {
1.157 + return NS_ERROR_FILE_CORRUPTED;
1.158 + }
1.159 +
1.160 + aArray.AppendElement(prefix);
1.161 + for (uint32_t j = start; j < end; j++) {
1.162 + prefix += mDeltas[j];
1.163 + aArray.AppendElement(prefix);
1.164 + }
1.165 + }
1.166 +
1.167 + NS_ASSERTION(mIndexStarts.Length() + mDeltas.Length() == aArray.Length(),
1.168 + "Lengths are inconsistent");
1.169 +
1.170 + uint32_t itemCount = aArray.Length();
1.171 +
1.172 + uint32_t* retval = static_cast<uint32_t*>(nsMemory::Alloc(itemCount * sizeof(uint32_t)));
1.173 + NS_ENSURE_TRUE(retval, NS_ERROR_OUT_OF_MEMORY);
1.174 + for (uint32_t i = 0; i < itemCount; i++) {
1.175 + retval[i] = aArray[i];
1.176 + }
1.177 +
1.178 + *aCount = itemCount;
1.179 + *aPrefixes = retval;
1.180 +
1.181 + return NS_OK;
1.182 +}
1.183 +
1.184 +uint32_t nsUrlClassifierPrefixSet::BinSearch(uint32_t start,
1.185 + uint32_t end,
1.186 + uint32_t target)
1.187 +{
1.188 + while (start != end && end >= start) {
1.189 + uint32_t i = start + ((end - start) >> 1);
1.190 + uint32_t value = mIndexPrefixes[i];
1.191 + if (value < target) {
1.192 + start = i + 1;
1.193 + } else if (value > target) {
1.194 + end = i - 1;
1.195 + } else {
1.196 + return i;
1.197 + }
1.198 + }
1.199 + return end;
1.200 +}
1.201 +
1.202 +NS_IMETHODIMP
1.203 +nsUrlClassifierPrefixSet::Contains(uint32_t aPrefix, bool* aFound)
1.204 +{
1.205 + *aFound = false;
1.206 +
1.207 + if (!mHasPrefixes) {
1.208 + return NS_OK;
1.209 + }
1.210 +
1.211 + uint32_t target = aPrefix;
1.212 +
1.213 + // We want to do a "Price is Right" binary search, that is, we want to find
1.214 + // the index of the value either equal to the target or the closest value
1.215 + // that is less than the target.
1.216 + //
1.217 + if (target < mIndexPrefixes[0]) {
1.218 + return NS_OK;
1.219 + }
1.220 +
1.221 + // |binsearch| does not necessarily return the correct index (when the
1.222 + // target is not found) but rather it returns an index at least one away
1.223 + // from the correct index.
1.224 + // Because of this, we need to check if the target lies before the beginning
1.225 + // of the indices.
1.226 +
1.227 + uint32_t i = BinSearch(0, mIndexPrefixes.Length() - 1, target);
1.228 + if (mIndexPrefixes[i] > target && i > 0) {
1.229 + i--;
1.230 + }
1.231 +
1.232 + // Now search through the deltas for the target.
1.233 + uint32_t diff = target - mIndexPrefixes[i];
1.234 + uint32_t deltaIndex = mIndexStarts[i];
1.235 + uint32_t deltaSize = mDeltas.Length();
1.236 + uint32_t end = (i + 1 < mIndexStarts.Length()) ? mIndexStarts[i+1]
1.237 + : deltaSize;
1.238 +
1.239 + // Sanity check the read values
1.240 + if (end > deltaSize) {
1.241 + return NS_ERROR_FILE_CORRUPTED;
1.242 + }
1.243 +
1.244 + while (diff > 0 && deltaIndex < end) {
1.245 + diff -= mDeltas[deltaIndex];
1.246 + deltaIndex++;
1.247 + }
1.248 +
1.249 + if (diff == 0) {
1.250 + *aFound = true;
1.251 + }
1.252 +
1.253 + return NS_OK;
1.254 +}
1.255 +
1.256 +MOZ_DEFINE_MALLOC_SIZE_OF(UrlClassifierMallocSizeOf)
1.257 +
1.258 +NS_IMETHODIMP
1.259 +nsUrlClassifierPrefixSet::CollectReports(nsIHandleReportCallback* aHandleReport,
1.260 + nsISupports* aData)
1.261 +{
1.262 + return aHandleReport->Callback(
1.263 + EmptyCString(), mMemoryReportPath, KIND_HEAP, UNITS_BYTES,
1.264 + SizeOfIncludingThis(UrlClassifierMallocSizeOf),
1.265 + NS_LITERAL_CSTRING("Memory used by the prefix set for a URL classifier."),
1.266 + aData);
1.267 +}
1.268 +
1.269 +size_t
1.270 +nsUrlClassifierPrefixSet::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf)
1.271 +{
1.272 + size_t n = 0;
1.273 + n += aMallocSizeOf(this);
1.274 + n += mDeltas.SizeOfExcludingThis(aMallocSizeOf);
1.275 + n += mIndexPrefixes.SizeOfExcludingThis(aMallocSizeOf);
1.276 + n += mIndexStarts.SizeOfExcludingThis(aMallocSizeOf);
1.277 + return n;
1.278 +}
1.279 +
1.280 +NS_IMETHODIMP
1.281 +nsUrlClassifierPrefixSet::IsEmpty(bool * aEmpty)
1.282 +{
1.283 + *aEmpty = !mHasPrefixes;
1.284 + return NS_OK;
1.285 +}
1.286 +
1.287 +nsresult
1.288 +nsUrlClassifierPrefixSet::LoadFromFd(AutoFDClose& fileFd)
1.289 +{
1.290 + uint32_t magic;
1.291 + int32_t read;
1.292 +
1.293 + read = PR_Read(fileFd, &magic, sizeof(uint32_t));
1.294 + NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FAILURE);
1.295 +
1.296 + if (magic == PREFIXSET_VERSION_MAGIC) {
1.297 + uint32_t indexSize;
1.298 + uint32_t deltaSize;
1.299 +
1.300 + read = PR_Read(fileFd, &indexSize, sizeof(uint32_t));
1.301 + NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FILE_CORRUPTED);
1.302 + read = PR_Read(fileFd, &deltaSize, sizeof(uint32_t));
1.303 + NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FILE_CORRUPTED);
1.304 +
1.305 + if (indexSize == 0) {
1.306 + LOG(("stored PrefixSet is empty!"));
1.307 + return NS_OK;
1.308 + }
1.309 +
1.310 + if (deltaSize > (indexSize * DELTAS_LIMIT)) {
1.311 + return NS_ERROR_FILE_CORRUPTED;
1.312 + }
1.313 +
1.314 + mIndexStarts.SetLength(indexSize);
1.315 + mIndexPrefixes.SetLength(indexSize);
1.316 + mDeltas.SetLength(deltaSize);
1.317 +
1.318 + int32_t toRead = indexSize*sizeof(uint32_t);
1.319 + read = PR_Read(fileFd, mIndexPrefixes.Elements(), toRead);
1.320 + NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);
1.321 + read = PR_Read(fileFd, mIndexStarts.Elements(), toRead);
1.322 + NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);
1.323 + if (deltaSize > 0) {
1.324 + toRead = deltaSize*sizeof(uint16_t);
1.325 + read = PR_Read(fileFd, mDeltas.Elements(), toRead);
1.326 + NS_ENSURE_TRUE(read == toRead, NS_ERROR_FILE_CORRUPTED);
1.327 + }
1.328 +
1.329 + mHasPrefixes = true;
1.330 + } else {
1.331 + LOG(("Version magic mismatch, not loading"));
1.332 + return NS_ERROR_FILE_CORRUPTED;
1.333 + }
1.334 +
1.335 + LOG(("Loading PrefixSet successful"));
1.336 +
1.337 + return NS_OK;
1.338 +}
1.339 +
1.340 +NS_IMETHODIMP
1.341 +nsUrlClassifierPrefixSet::LoadFromFile(nsIFile* aFile)
1.342 +{
1.343 + Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_FILELOAD_TIME> timer;
1.344 +
1.345 + nsresult rv;
1.346 + AutoFDClose fileFd;
1.347 + rv = aFile->OpenNSPRFileDesc(PR_RDONLY | nsIFile::OS_READAHEAD,
1.348 + 0, &fileFd.rwget());
1.349 + NS_ENSURE_SUCCESS(rv, rv);
1.350 +
1.351 + return LoadFromFd(fileFd);
1.352 +}
1.353 +
1.354 +nsresult
1.355 +nsUrlClassifierPrefixSet::StoreToFd(AutoFDClose& fileFd)
1.356 +{
1.357 + {
1.358 + Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_FALLOCATE_TIME> timer;
1.359 + int64_t size = 4 * sizeof(uint32_t);
1.360 + size += 2 * mIndexStarts.Length() * sizeof(uint32_t);
1.361 + size += mDeltas.Length() * sizeof(uint16_t);
1.362 +
1.363 + mozilla::fallocate(fileFd, size);
1.364 + }
1.365 +
1.366 + int32_t written;
1.367 + int32_t writelen = sizeof(uint32_t);
1.368 + uint32_t magic = PREFIXSET_VERSION_MAGIC;
1.369 + written = PR_Write(fileFd, &magic, writelen);
1.370 + NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
1.371 +
1.372 + uint32_t indexSize = mIndexStarts.Length();
1.373 + uint32_t deltaSize = mDeltas.Length();
1.374 + written = PR_Write(fileFd, &indexSize, writelen);
1.375 + NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
1.376 + written = PR_Write(fileFd, &deltaSize, writelen);
1.377 + NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
1.378 +
1.379 + writelen = indexSize * sizeof(uint32_t);
1.380 + written = PR_Write(fileFd, mIndexPrefixes.Elements(), writelen);
1.381 + NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
1.382 + written = PR_Write(fileFd, mIndexStarts.Elements(), writelen);
1.383 + NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
1.384 + if (deltaSize > 0) {
1.385 + writelen = deltaSize * sizeof(uint16_t);
1.386 + written = PR_Write(fileFd, mDeltas.Elements(), writelen);
1.387 + NS_ENSURE_TRUE(written == writelen, NS_ERROR_FAILURE);
1.388 + }
1.389 +
1.390 + LOG(("Saving PrefixSet successful\n"));
1.391 +
1.392 + return NS_OK;
1.393 +}
1.394 +
1.395 +NS_IMETHODIMP
1.396 +nsUrlClassifierPrefixSet::StoreToFile(nsIFile* aFile)
1.397 +{
1.398 + AutoFDClose fileFd;
1.399 + nsresult rv = aFile->OpenNSPRFileDesc(PR_RDWR | PR_TRUNCATE | PR_CREATE_FILE,
1.400 + 0644, &fileFd.rwget());
1.401 + NS_ENSURE_SUCCESS(rv, rv);
1.402 +
1.403 + return StoreToFd(fileFd);
1.404 +}
