1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5 #include "CacheIndex.h"
6 #include "CacheLog.h"
7 #include "CacheFileUtils.h"
8 #include "LoadContextInfo.h"
9 #include "mozilla/Tokenizer.h"
10 #include "mozilla/Telemetry.h"
11 #include "nsCOMPtr.h"
12 #include "nsAutoPtr.h"
13 #include "nsString.h"
14 #include <algorithm>
15 #include "mozilla/Unused.h"
16
17
18 namespace mozilla {
19 namespace net {
20 namespace CacheFileUtils {
21
22 // This designates the format for the "alt-data" metadata.
23 // When the format changes we need to update the version.
24 static uint32_t const kAltDataVersion = 1;
25 const char *kAltDataKey = "alt-data";
26
27 namespace {
28
29 /**
30 * A simple recursive descent parser for the mapping key.
31 */
32 class KeyParser : protected Tokenizer
33 {
34 public:
KeyParser(nsACString const & aInput)35 explicit KeyParser(nsACString const& aInput)
36 : Tokenizer(aInput)
37 // Initialize attributes to their default values
38 , originAttribs(0, false)
39 , isAnonymous(false)
40 // Initialize the cache key to a zero length by default
41 , lastTag(0)
42 {
43 }
44
45 private:
46 // Results
47 NeckoOriginAttributes originAttribs;
48 bool isAnonymous;
49 nsCString idEnhance;
50 nsDependentCSubstring cacheKey;
51
52 // Keeps the last tag name, used for alphabetical sort checking
53 char lastTag;
54
55 // Classifier for the 'tag' character valid range
TagChar(const char aChar)56 static bool TagChar(const char aChar)
57 {
58 return aChar >= ' ' && aChar <= '~';
59 }
60
ParseTags()61 bool ParseTags()
62 {
63 // Expects to be at the tag name or at the end
64 if (CheckEOF()) {
65 return true;
66 }
67
68 char tag;
69 if (!ReadChar(&TagChar, &tag)) {
70 return false;
71 }
72
73 // Check the alphabetical order, hard-fail on disobedience
74 if (!(lastTag < tag || tag == ':')) {
75 return false;
76 }
77 lastTag = tag;
78
79 switch (tag) {
80 case ':':
81 // last possible tag, when present there is the cacheKey following,
82 // not terminated with ',' and no need to unescape.
83 cacheKey.Rebind(mCursor, mEnd - mCursor);
84 return true;
85 case 'O': {
86 nsAutoCString originSuffix;
87 if (!ParseValue(&originSuffix) || !originAttribs.PopulateFromSuffix(originSuffix)) {
88 return false;
89 }
90 break;
91 }
92 case 'p':
93 originAttribs.SyncAttributesWithPrivateBrowsing(true);
94 break;
95 case 'b':
96 // Leaving to be able to read and understand oldformatted entries
97 originAttribs.mInIsolatedMozBrowser = true;
98 break;
99 case 'a':
100 isAnonymous = true;
101 break;
102 case 'i': {
103 // Leaving to be able to read and understand oldformatted entries
104 if (!ReadInteger(&originAttribs.mAppId)) {
105 return false; // not a valid 32-bit integer
106 }
107 break;
108 }
109 case '~':
110 if (!ParseValue(&idEnhance)) {
111 return false;
112 }
113 break;
114 default:
115 if (!ParseValue()) { // skip any tag values, optional
116 return false;
117 }
118 break;
119 }
120
121 // We expect a comma after every tag
122 if (!CheckChar(',')) {
123 return false;
124 }
125
126 // Recurse to the next tag
127 return ParseTags();
128 }
129
ParseValue(nsACString * result=nullptr)130 bool ParseValue(nsACString *result = nullptr)
131 {
132 // If at the end, fail since we expect a comma ; value may be empty tho
133 if (CheckEOF()) {
134 return false;
135 }
136
137 Token t;
138 while (Next(t)) {
139 if (!Token::Char(',').Equals(t)) {
140 if (result) {
141 result->Append(t.Fragment());
142 }
143 continue;
144 }
145
146 if (CheckChar(',')) {
147 // Two commas in a row, escaping
148 if (result) {
149 result->Append(',');
150 }
151 continue;
152 }
153
154 // We must give the comma back since the upper calls expect it
155 Rollback();
156 return true;
157 }
158
159 return false;
160 }
161
162 public:
Parse()163 already_AddRefed<LoadContextInfo> Parse()
164 {
165 RefPtr<LoadContextInfo> info;
166 if (ParseTags()) {
167 info = GetLoadContextInfo(isAnonymous, originAttribs);
168 }
169
170 return info.forget();
171 }
172
URISpec(nsACString & result)173 void URISpec(nsACString &result)
174 {
175 result.Assign(cacheKey);
176 }
177
IdEnhance(nsACString & result)178 void IdEnhance(nsACString &result)
179 {
180 result.Assign(idEnhance);
181 }
182 };
183
184 } // namespace
185
186 already_AddRefed<nsILoadContextInfo>
ParseKey(const nsCSubstring & aKey,nsCSubstring * aIdEnhance,nsCSubstring * aURISpec)187 ParseKey(const nsCSubstring &aKey,
188 nsCSubstring *aIdEnhance,
189 nsCSubstring *aURISpec)
190 {
191 KeyParser parser(aKey);
192 RefPtr<LoadContextInfo> info = parser.Parse();
193
194 if (info) {
195 if (aIdEnhance)
196 parser.IdEnhance(*aIdEnhance);
197 if (aURISpec)
198 parser.URISpec(*aURISpec);
199 }
200
201 return info.forget();
202 }
203
204 void
AppendKeyPrefix(nsILoadContextInfo * aInfo,nsACString & _retval)205 AppendKeyPrefix(nsILoadContextInfo* aInfo, nsACString &_retval)
206 {
207 /**
208 * This key is used to salt file hashes. When form of the key is changed
209 * cache entries will fail to find on disk.
210 *
211 * IMPORTANT NOTE:
212 * Keep the attributes list sorted according their ASCII code.
213 */
214
215 NeckoOriginAttributes const *oa = aInfo->OriginAttributesPtr();
216 nsAutoCString suffix;
217 oa->CreateSuffix(suffix);
218 if (!suffix.IsEmpty()) {
219 AppendTagWithValue(_retval, 'O', suffix);
220 }
221
222 if (aInfo->IsAnonymous()) {
223 _retval.AppendLiteral("a,");
224 }
225
226 if (aInfo->IsPrivate()) {
227 _retval.AppendLiteral("p,");
228 }
229 }
230
231 void
AppendTagWithValue(nsACString & aTarget,char const aTag,nsCSubstring const & aValue)232 AppendTagWithValue(nsACString & aTarget, char const aTag, nsCSubstring const & aValue)
233 {
234 aTarget.Append(aTag);
235
236 // First check the value string to save some memory copying
237 // for cases we don't need to escape at all (most likely).
238 if (!aValue.IsEmpty()) {
239 if (!aValue.Contains(',')) {
240 // No need to escape
241 aTarget.Append(aValue);
242 } else {
243 nsAutoCString escapedValue(aValue);
244 escapedValue.ReplaceSubstring(
245 NS_LITERAL_CSTRING(","), NS_LITERAL_CSTRING(",,"));
246 aTarget.Append(escapedValue);
247 }
248 }
249
250 aTarget.Append(',');
251 }
252
253 nsresult
KeyMatchesLoadContextInfo(const nsACString & aKey,nsILoadContextInfo * aInfo,bool * _retval)254 KeyMatchesLoadContextInfo(const nsACString &aKey, nsILoadContextInfo *aInfo,
255 bool *_retval)
256 {
257 nsCOMPtr<nsILoadContextInfo> info = ParseKey(aKey);
258
259 if (!info) {
260 return NS_ERROR_FAILURE;
261 }
262
263 *_retval = info->Equals(aInfo);
264 return NS_OK;
265 }
266
ValidityPair(uint32_t aOffset,uint32_t aLen)267 ValidityPair::ValidityPair(uint32_t aOffset, uint32_t aLen)
268 : mOffset(aOffset), mLen(aLen)
269 {}
270
271 ValidityPair&
operator =(const ValidityPair & aOther)272 ValidityPair::operator=(const ValidityPair& aOther)
273 {
274 mOffset = aOther.mOffset;
275 mLen = aOther.mLen;
276 return *this;
277 }
278
279 bool
CanBeMerged(const ValidityPair & aOther) const280 ValidityPair::CanBeMerged(const ValidityPair& aOther) const
281 {
282 // The pairs can be merged into a single one if the start of one of the pairs
283 // is placed anywhere in the validity interval of other pair or exactly after
284 // its end.
285 return IsInOrFollows(aOther.mOffset) || aOther.IsInOrFollows(mOffset);
286 }
287
288 bool
IsInOrFollows(uint32_t aOffset) const289 ValidityPair::IsInOrFollows(uint32_t aOffset) const
290 {
291 return mOffset <= aOffset && mOffset + mLen >= aOffset;
292 }
293
294 bool
LessThan(const ValidityPair & aOther) const295 ValidityPair::LessThan(const ValidityPair& aOther) const
296 {
297 if (mOffset < aOther.mOffset) {
298 return true;
299 }
300
301 if (mOffset == aOther.mOffset && mLen < aOther.mLen) {
302 return true;
303 }
304
305 return false;
306 }
307
308 void
Merge(const ValidityPair & aOther)309 ValidityPair::Merge(const ValidityPair& aOther)
310 {
311 MOZ_ASSERT(CanBeMerged(aOther));
312
313 uint32_t offset = std::min(mOffset, aOther.mOffset);
314 uint32_t end = std::max(mOffset + mLen, aOther.mOffset + aOther.mLen);
315
316 mOffset = offset;
317 mLen = end - offset;
318 }
319
320 void
Log() const321 ValidityMap::Log() const
322 {
323 LOG(("ValidityMap::Log() - number of pairs: %u", mMap.Length()));
324 for (uint32_t i=0; i<mMap.Length(); i++) {
325 LOG((" (%u, %u)", mMap[i].Offset() + 0, mMap[i].Len() + 0));
326 }
327 }
328
329 uint32_t
Length() const330 ValidityMap::Length() const
331 {
332 return mMap.Length();
333 }
334
335 void
AddPair(uint32_t aOffset,uint32_t aLen)336 ValidityMap::AddPair(uint32_t aOffset, uint32_t aLen)
337 {
338 ValidityPair pair(aOffset, aLen);
339
340 if (mMap.Length() == 0) {
341 mMap.AppendElement(pair);
342 return;
343 }
344
345 // Find out where to place this pair into the map, it can overlap only with
346 // one preceding pair and all subsequent pairs.
347 uint32_t pos = 0;
348 for (pos = mMap.Length(); pos > 0; ) {
349 --pos;
350
351 if (mMap[pos].LessThan(pair)) {
352 // The new pair should be either inserted after pos or merged with it.
353 if (mMap[pos].CanBeMerged(pair)) {
354 // Merge with the preceding pair
355 mMap[pos].Merge(pair);
356 } else {
357 // They don't overlap, element must be placed after pos element
358 ++pos;
359 if (pos == mMap.Length()) {
360 mMap.AppendElement(pair);
361 } else {
362 mMap.InsertElementAt(pos, pair);
363 }
364 }
365
366 break;
367 }
368
369 if (pos == 0) {
370 // The new pair should be placed in front of all existing pairs.
371 mMap.InsertElementAt(0, pair);
372 }
373 }
374
375 // pos now points to merged or inserted pair, check whether it overlaps with
376 // subsequent pairs.
377 while (pos + 1 < mMap.Length()) {
378 if (mMap[pos].CanBeMerged(mMap[pos + 1])) {
379 mMap[pos].Merge(mMap[pos + 1]);
380 mMap.RemoveElementAt(pos + 1);
381 } else {
382 break;
383 }
384 }
385 }
386
387 void
Clear()388 ValidityMap::Clear()
389 {
390 mMap.Clear();
391 }
392
393 size_t
SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const394 ValidityMap::SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const
395 {
396 return mMap.ShallowSizeOfExcludingThis(mallocSizeOf);
397 }
398
399 ValidityPair&
operator [](uint32_t aIdx)400 ValidityMap::operator[](uint32_t aIdx)
401 {
402 return mMap.ElementAt(aIdx);
403 }
404
405 StaticMutex DetailedCacheHitTelemetry::sLock;
406 uint32_t DetailedCacheHitTelemetry::sRecordCnt = 0;
407 DetailedCacheHitTelemetry::HitRate DetailedCacheHitTelemetry::sHRStats[kNumOfRanges];
408
HitRate()409 DetailedCacheHitTelemetry::HitRate::HitRate()
410 {
411 Reset();
412 }
413
414 void
AddRecord(ERecType aType)415 DetailedCacheHitTelemetry::HitRate::AddRecord(ERecType aType)
416 {
417 if (aType == HIT) {
418 ++mHitCnt;
419 } else {
420 ++mMissCnt;
421 }
422 }
423
424 uint32_t
GetHitRateBucket(uint32_t aNumOfBuckets) const425 DetailedCacheHitTelemetry::HitRate::GetHitRateBucket(uint32_t aNumOfBuckets) const
426 {
427 uint32_t bucketIdx = (aNumOfBuckets * mHitCnt) / (mHitCnt + mMissCnt);
428 if (bucketIdx == aNumOfBuckets) { // make sure 100% falls into the last bucket
429 --bucketIdx;
430 }
431
432 return bucketIdx;
433 }
434
435 uint32_t
Count()436 DetailedCacheHitTelemetry::HitRate::Count()
437 {
438 return mHitCnt + mMissCnt;
439 }
440
441 void
Reset()442 DetailedCacheHitTelemetry::HitRate::Reset()
443 {
444 mHitCnt = 0;
445 mMissCnt = 0;
446 }
447
448 // static
449 void
AddRecord(ERecType aType,TimeStamp aLoadStart)450 DetailedCacheHitTelemetry::AddRecord(ERecType aType, TimeStamp aLoadStart)
451 {
452 bool isUpToDate = false;
453 CacheIndex::IsUpToDate(&isUpToDate);
454 if (!isUpToDate) {
455 // Ignore the record when the entry file count might be incorrect
456 return;
457 }
458
459 uint32_t entryCount;
460 nsresult rv = CacheIndex::GetEntryFileCount(&entryCount);
461 if (NS_FAILED(rv)) {
462 return;
463 }
464
465 uint32_t rangeIdx = entryCount / kRangeSize;
466 if (rangeIdx >= kNumOfRanges) { // The last range has no upper limit.
467 rangeIdx = kNumOfRanges - 1;
468 }
469
470 uint32_t hitMissValue = 2 * rangeIdx; // 2 values per range
471 if (aType == MISS) { // The order is HIT, MISS
472 ++hitMissValue;
473 }
474
475 StaticMutexAutoLock lock(sLock);
476
477 if (aType == MISS) {
478 mozilla::Telemetry::AccumulateTimeDelta(
479 mozilla::Telemetry::NETWORK_CACHE_V2_MISS_TIME_MS,
480 aLoadStart);
481 } else {
482 mozilla::Telemetry::AccumulateTimeDelta(
483 mozilla::Telemetry::NETWORK_CACHE_V2_HIT_TIME_MS,
484 aLoadStart);
485 }
486
487 Telemetry::Accumulate(Telemetry::NETWORK_CACHE_HIT_MISS_STAT_PER_CACHE_SIZE,
488 hitMissValue);
489
490 sHRStats[rangeIdx].AddRecord(aType);
491 ++sRecordCnt;
492
493 if (sRecordCnt < kTotalSamplesReportLimit) {
494 return;
495 }
496
497 sRecordCnt = 0;
498
499 for (uint32_t i = 0; i < kNumOfRanges; ++i) {
500 if (sHRStats[i].Count() >= kHitRateSamplesReportLimit) {
501 // The telemetry enums are grouped by buckets as follows:
502 // Telemetry value : 0,1,2,3, ... ,19,20,21,22, ... ,398,399
503 // Hit rate bucket : 0,0,0,0, ... , 0, 1, 1, 1, ... , 19, 19
504 // Cache size range: 0,1,2,3, ... ,19, 0, 1, 2, ... , 18, 19
505 uint32_t bucketOffset = sHRStats[i].GetHitRateBucket(kHitRateBuckets) *
506 kNumOfRanges;
507
508 Telemetry::Accumulate(Telemetry::NETWORK_CACHE_HIT_RATE_PER_CACHE_SIZE,
509 bucketOffset + i);
510 sHRStats[i].Reset();
511 }
512 }
513 }
514
515 void
FreeBuffer(void * aBuf)516 FreeBuffer(void *aBuf) {
517 #ifndef NS_FREE_PERMANENT_DATA
518 if (CacheObserver::ShuttingDown()) {
519 return;
520 }
521 #endif
522
523 free(aBuf);
524 }
525
526 nsresult
ParseAlternativeDataInfo(const char * aInfo,int64_t * _offset,nsACString * _type)527 ParseAlternativeDataInfo(const char *aInfo, int64_t *_offset, nsACString *_type)
528 {
529 // The format is: "1;12345,javascript/binary"
530 // <version>;<offset>,<type>
531 mozilla::Tokenizer p(aInfo, nullptr, "/");
532 uint32_t altDataVersion = 0;
533 int64_t altDataOffset = -1;
534
535 // The metadata format has a wrong version number.
536 if (!p.ReadInteger(&altDataVersion) ||
537 altDataVersion != kAltDataVersion) {
538 LOG(("ParseAlternativeDataInfo() - altDataVersion=%u, "
539 "expectedVersion=%u", altDataVersion, kAltDataVersion));
540 return NS_ERROR_NOT_AVAILABLE;
541 }
542
543 if (!p.CheckChar(';') ||
544 !p.ReadInteger(&altDataOffset) ||
545 !p.CheckChar(',')) {
546 return NS_ERROR_NOT_AVAILABLE;
547 }
548
549 // The requested alt-data representation is not available
550 if (altDataOffset < 0) {
551 return NS_ERROR_NOT_AVAILABLE;
552 }
553
554 *_offset = altDataOffset;
555 if (_type) {
556 mozilla::Unused << p.ReadUntil(Tokenizer::Token::EndOfFile(), *_type);
557 }
558
559 return NS_OK;
560 }
561
562 void
BuildAlternativeDataInfo(const char * aInfo,int64_t aOffset,nsACString & _retval)563 BuildAlternativeDataInfo(const char *aInfo, int64_t aOffset, nsACString &_retval)
564 {
565 _retval.Truncate();
566 _retval.AppendInt(kAltDataVersion);
567 _retval.Append(';');
568 _retval.AppendInt(aOffset);
569 _retval.Append(',');
570 _retval.Append(aInfo);
571 }
572
573 } // namespace CacheFileUtils
574 } // namespace net
575 } // namespace mozilla
576