The Tor Browser / file comparison

comparison: toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp

toolkit/components/url-classifier/nsUrlClassifierPrefixSet.cpp

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:9145b4e3cf33
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/. */
6
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"
25
26 using namespace mozilla;
27
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
37
38 NS_IMPL_ISUPPORTS(
39 nsUrlClassifierPrefixSet, nsIUrlClassifierPrefixSet, nsIMemoryReporter)
40
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 }
50
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 );
59
60 RegisterWeakMemoryReporter(this);
61
62 return NS_OK;
63 }
64
65 nsUrlClassifierPrefixSet::~nsUrlClassifierPrefixSet()
66 {
67 UnregisterWeakMemoryReporter(this);
68 }
69
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 }
84
85 return NS_OK;
86 }
87
88 nsresult
89 nsUrlClassifierPrefixSet::MakePrefixSet(const uint32_t* aPrefixes, uint32_t aLength)
90 {
91 if (aLength == 0) {
92 return NS_OK;
93 }
94
95 #ifdef DEBUG
96 for (uint32_t i = 1; i < aLength; i++) {
97 MOZ_ASSERT(aPrefixes[i] >= aPrefixes[i-1]);
98 }
99 #endif
100
101 mIndexPrefixes.Clear();
102 mIndexStarts.Clear();
103 mDeltas.Clear();
104
105 mIndexPrefixes.AppendElement(aPrefixes[0]);
106 mIndexStarts.AppendElement(mDeltas.Length());
107
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 }
123
124 mIndexPrefixes.Compact();
125 mIndexStarts.Compact();
126 mDeltas.Compact();
127
128 LOG(("Total number of indices: %d", mIndexPrefixes.Length()));
129 LOG(("Total number of deltas: %d", mDeltas.Length()));
130
131 mHasPrefixes = true;
132
133 return NS_OK;
134 }
135
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;
144
145 nsTArray<uint32_t> aArray;
146 uint32_t prefixLength = mIndexPrefixes.Length();
147
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 }
156
157 aArray.AppendElement(prefix);
158 for (uint32_t j = start; j < end; j++) {
159 prefix += mDeltas[j];
160 aArray.AppendElement(prefix);
161 }
162 }
163
164 NS_ASSERTION(mIndexStarts.Length() + mDeltas.Length() == aArray.Length(),
165 "Lengths are inconsistent");
166
167 uint32_t itemCount = aArray.Length();
168
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 }
174
175 *aCount = itemCount;
176 *aPrefixes = retval;
177
178 return NS_OK;
179 }
180
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 }
198
199 NS_IMETHODIMP
200 nsUrlClassifierPrefixSet::Contains(uint32_t aPrefix, bool* aFound)
201 {
202 *aFound = false;
203
204 if (!mHasPrefixes) {
205 return NS_OK;
206 }
207
208 uint32_t target = aPrefix;
209
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 }
217
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.
223
224 uint32_t i = BinSearch(0, mIndexPrefixes.Length() - 1, target);
225 if (mIndexPrefixes[i] > target && i > 0) {
226 i--;
227 }
228
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;
235
236 // Sanity check the read values
237 if (end > deltaSize) {
238 return NS_ERROR_FILE_CORRUPTED;
239 }
240
241 while (diff > 0 && deltaIndex < end) {
242 diff -= mDeltas[deltaIndex];
243 deltaIndex++;
244 }
245
246 if (diff == 0) {
247 *aFound = true;
248 }
249
250 return NS_OK;
251 }
252
253 MOZ_DEFINE_MALLOC_SIZE_OF(UrlClassifierMallocSizeOf)
254
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 }
265
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 }
276
277 NS_IMETHODIMP
278 nsUrlClassifierPrefixSet::IsEmpty(bool * aEmpty)
279 {
280 *aEmpty = !mHasPrefixes;
281 return NS_OK;
282 }
283
284 nsresult
285 nsUrlClassifierPrefixSet::LoadFromFd(AutoFDClose& fileFd)
286 {
287 uint32_t magic;
288 int32_t read;
289
290 read = PR_Read(fileFd, &magic, sizeof(uint32_t));
291 NS_ENSURE_TRUE(read == sizeof(uint32_t), NS_ERROR_FAILURE);
292
293 if (magic == PREFIXSET_VERSION_MAGIC) {
294 uint32_t indexSize;
295 uint32_t deltaSize;
296
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);
301
302 if (indexSize == 0) {
303 LOG(("stored PrefixSet is empty!"));
304 return NS_OK;
305 }
306
307 if (deltaSize > (indexSize * DELTAS_LIMIT)) {
308 return NS_ERROR_FILE_CORRUPTED;
309 }
310
311 mIndexStarts.SetLength(indexSize);
312 mIndexPrefixes.SetLength(indexSize);
313 mDeltas.SetLength(deltaSize);
314
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 }
325
326 mHasPrefixes = true;
327 } else {
328 LOG(("Version magic mismatch, not loading"));
329 return NS_ERROR_FILE_CORRUPTED;
330 }
331
332 LOG(("Loading PrefixSet successful"));
333
334 return NS_OK;
335 }
336
337 NS_IMETHODIMP
338 nsUrlClassifierPrefixSet::LoadFromFile(nsIFile* aFile)
339 {
340 Telemetry::AutoTimer<Telemetry::URLCLASSIFIER_PS_FILELOAD_TIME> timer;
341
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);
347
348 return LoadFromFd(fileFd);
349 }
350
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);
359
360 mozilla::fallocate(fileFd, size);
361 }
362
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);
368
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);
375
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 }
386
387 LOG(("Saving PrefixSet successful\n"));
388
389 return NS_OK;
390 }
391
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);
399
400 return StoreToFd(fileFd);
401 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial