netwerk/cache2/CacheFileUtils.cpp

   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 "CacheObserver.h"
   9 #include "LoadContextInfo.h"
  10 #include "mozilla/glean/NetwerkProtocolHttpMetrics.h"
  11 #include "mozilla/Tokenizer.h"
  12 #include "mozilla/Telemetry.h"
  13 #include "nsCOMPtr.h"
  14 #include "nsString.h"
  15 #include <algorithm>
  16 #include "mozilla/Unused.h"
  17
  18 namespace mozilla::net::CacheFileUtils {
  19
  20 // This designates the format for the "alt-data" metadata.
  21 // When the format changes we need to update the version.
  22 static uint32_t const kAltDataVersion = 1;
  23 const char* kAltDataKey = "alt-data";
  24
  25 namespace {
  26
  27 /**
  28  * A simple recursive descent parser for the mapping key.
  29  */
  30 class KeyParser : protected Tokenizer {
  31  public:
  32   explicit KeyParser(nsACString const& aInput)
  33       : Tokenizer(aInput),
  34         isAnonymous(false)
  35         // Initialize the cache key to a zero length by default
  36         ,
  37         lastTag(0) {}
  38
  39  private:
  40   // Results
  41   OriginAttributes originAttribs;
  42   bool isAnonymous;
  43   nsCString idEnhance;
  44   nsDependentCSubstring cacheKey;
  45
  46   // Keeps the last tag name, used for alphabetical sort checking
  47   char lastTag;
  48
  49   // Classifier for the 'tag' character valid range.
  50   // Explicitly using unsigned char as 127 is -1 when signed and it would only
  51   // produce a warning.
  52   static bool TagChar(const char aChar) {
  53     unsigned char c = static_cast<unsigned char>(aChar);
  54     return c >= ' ' && c <= '\x7f';
  55   }
  56
  57   bool ParseTags() {
  58     // Expects to be at the tag name or at the end
  59     if (CheckEOF()) {
  60       return true;
  61     }
  62
  63     char tag;
  64     if (!ReadChar(&TagChar, &tag)) {
  65       return false;
  66     }
  67
  68     // Check the alphabetical order, hard-fail on disobedience
  69     if (!(lastTag < tag || tag == ':')) {
  70       return false;
  71     }
  72     lastTag = tag;
  73
  74     switch (tag) {
  75       case ':':
  76         // last possible tag, when present there is the cacheKey following,
  77         // not terminated with ',' and no need to unescape.
  78         cacheKey.Rebind(mCursor, mEnd - mCursor);
  79         return true;
  80       case 'O': {
  81         nsAutoCString originSuffix;
  82         if (!ParseValue(&originSuffix) ||
  83             !originAttribs.PopulateFromSuffix(originSuffix)) {
  84           return false;
  85         }
  86         break;
  87       }
  88       case 'p':
  89         originAttribs.SyncAttributesWithPrivateBrowsing(true);
  90         break;
  91       case 'b':
  92         // Leaving to be able to read and understand oldformatted entries
  93         break;
  94       case 'a':
  95         isAnonymous = true;
  96         break;
  97       case 'i': {
  98         // Leaving to be able to read and understand oldformatted entries
  99         uint32_t deprecatedAppId = 0;
 100         if (!ReadInteger(&deprecatedAppId)) {
 101           return false;  // not a valid 32-bit integer
 102         }
 103         break;
 104       }
 105       case '~':
 106         if (!ParseValue(&idEnhance)) {
 107           return false;
 108         }
 109         break;
 110       default:
 111         if (!ParseValue()) {  // skip any tag values, optional
 112           return false;
 113         }
 114         break;
 115     }
 116
 117     // We expect a comma after every tag
 118     if (!CheckChar(',')) {
 119       return false;
 120     }
 121
 122     // Recurse to the next tag
 123     return ParseTags();
 124   }
 125
 126   bool ParseValue(nsACString* result = nullptr) {
 127     // If at the end, fail since we expect a comma ; value may be empty tho
 128     if (CheckEOF()) {
 129       return false;
 130     }
 131
 132     Token t;
 133     while (Next(t)) {
 134       if (!Token::Char(',').Equals(t)) {
 135         if (result) {
 136           result->Append(t.Fragment());
 137         }
 138         continue;
 139       }
 140
 141       if (CheckChar(',')) {
 142         // Two commas in a row, escaping
 143         if (result) {
 144           result->Append(',');
 145         }
 146         continue;
 147       }
 148
 149       // We must give the comma back since the upper calls expect it
 150       Rollback();
 151       return true;
 152     }
 153
 154     return false;
 155   }
 156
 157  public:
 158   already_AddRefed<LoadContextInfo> Parse() {
 159     RefPtr<LoadContextInfo> info;
 160     if (ParseTags()) {
 161       info = GetLoadContextInfo(isAnonymous, originAttribs);
 162     }
 163
 164     return info.forget();
 165   }
 166
 167   void URISpec(nsACString& result) { result.Assign(cacheKey); }
 168
 169   void IdEnhance(nsACString& result) { result.Assign(idEnhance); }
 170 };
 171
 172 }  // namespace
 173
 174 already_AddRefed<nsILoadContextInfo> ParseKey(const nsACString& aKey,
 175                                               nsACString* aIdEnhance,
 176                                               nsACString* aURISpec) {
 177   KeyParser parser(aKey);
 178   RefPtr<LoadContextInfo> info = parser.Parse();
 179
 180   if (info) {
 181     if (aIdEnhance) parser.IdEnhance(*aIdEnhance);
 182     if (aURISpec) parser.URISpec(*aURISpec);
 183   }
 184
 185   return info.forget();
 186 }
 187
 188 void AppendKeyPrefix(nsILoadContextInfo* aInfo, nsACString& _retval) {
 189   /**
 190    * This key is used to salt file hashes.  When form of the key is changed
 191    * cache entries will fail to find on disk.
 192    *
 193    * IMPORTANT NOTE:
 194    * Keep the attributes list sorted according their ASCII code.
 195    */
 196
 197   if (!aInfo) {
 198     return;
 199   }
 200
 201   OriginAttributes const* oa = aInfo->OriginAttributesPtr();
 202   nsAutoCString suffix;
 203   oa->CreateSuffix(suffix);
 204   if (!suffix.IsEmpty()) {
 205     AppendTagWithValue(_retval, 'O', suffix);
 206   }
 207
 208   if (aInfo->IsAnonymous()) {
 209     _retval.AppendLiteral("a,");
 210   }
 211
 212   if (aInfo->IsPrivate()) {
 213     _retval.AppendLiteral("p,");
 214   }
 215 }
 216
 217 void AppendTagWithValue(nsACString& aTarget, char const aTag,
 218                         const nsACString& aValue) {
 219   aTarget.Append(aTag);
 220
 221   // First check the value string to save some memory copying
 222   // for cases we don't need to escape at all (most likely).
 223   if (!aValue.IsEmpty()) {
 224     if (!aValue.Contains(',')) {
 225       // No need to escape
 226       aTarget.Append(aValue);
 227     } else {
 228       nsAutoCString escapedValue(aValue);
 229       escapedValue.ReplaceSubstring(","_ns, ",,"_ns);
 230       aTarget.Append(escapedValue);
 231     }
 232   }
 233
 234   aTarget.Append(',');
 235 }
 236
 237 nsresult KeyMatchesLoadContextInfo(const nsACString& aKey,
 238                                    nsILoadContextInfo* aInfo, bool* _retval) {
 239   nsCOMPtr<nsILoadContextInfo> info = ParseKey(aKey);
 240
 241   if (!info) {
 242     return NS_ERROR_FAILURE;
 243   }
 244
 245   *_retval = info->Equals(aInfo);
 246   return NS_OK;
 247 }
 248
 249 ValidityPair::ValidityPair(uint32_t aOffset, uint32_t aLen)
 250     : mOffset(aOffset), mLen(aLen) {}
 251
 252 bool ValidityPair::CanBeMerged(const ValidityPair& aOther) const {
 253   // The pairs can be merged into a single one if the start of one of the pairs
 254   // is placed anywhere in the validity interval of other pair or exactly after
 255   // its end.
 256   return IsInOrFollows(aOther.mOffset) || aOther.IsInOrFollows(mOffset);
 257 }
 258
 259 bool ValidityPair::IsInOrFollows(uint32_t aOffset) const {
 260   return mOffset <= aOffset && mOffset + mLen >= aOffset;
 261 }
 262
 263 bool ValidityPair::LessThan(const ValidityPair& aOther) const {
 264   if (mOffset < aOther.mOffset) {
 265     return true;
 266   }
 267
 268   if (mOffset == aOther.mOffset && mLen < aOther.mLen) {
 269     return true;
 270   }
 271
 272   return false;
 273 }
 274
 275 void ValidityPair::Merge(const ValidityPair& aOther) {
 276   MOZ_ASSERT(CanBeMerged(aOther));
 277
 278   uint32_t offset = std::min(mOffset, aOther.mOffset);
 279   uint32_t end = std::max(mOffset + mLen, aOther.mOffset + aOther.mLen);
 280
 281   mOffset = offset;
 282   mLen = end - offset;
 283 }
 284
 285 void ValidityMap::Log() const {
 286   LOG(("ValidityMap::Log() - number of pairs: %zu", mMap.Length()));
 287   for (uint32_t i = 0; i < mMap.Length(); i++) {
 288     LOG(("    (%u, %u)", mMap[i].Offset() + 0, mMap[i].Len() + 0));
 289   }
 290 }
 291
 292 uint32_t ValidityMap::Length() const { return mMap.Length(); }
 293
 294 void ValidityMap::AddPair(uint32_t aOffset, uint32_t aLen) {
 295   ValidityPair pair(aOffset, aLen);
 296
 297   if (mMap.Length() == 0) {
 298     mMap.AppendElement(pair);
 299     return;
 300   }
 301
 302   // Find out where to place this pair into the map, it can overlap only with
 303   // one preceding pair and all subsequent pairs.
 304   uint32_t pos = 0;
 305   for (pos = mMap.Length(); pos > 0;) {
 306     --pos;
 307
 308     if (mMap[pos].LessThan(pair)) {
 309       // The new pair should be either inserted after pos or merged with it.
 310       if (mMap[pos].CanBeMerged(pair)) {
 311         // Merge with the preceding pair
 312         mMap[pos].Merge(pair);
 313       } else {
 314         // They don't overlap, element must be placed after pos element
 315         ++pos;
 316         if (pos == mMap.Length()) {
 317           mMap.AppendElement(pair);
 318         } else {
 319           mMap.InsertElementAt(pos, pair);
 320         }
 321       }
 322
 323       break;
 324     }
 325
 326     if (pos == 0) {
 327       // The new pair should be placed in front of all existing pairs.
 328       mMap.InsertElementAt(0, pair);
 329     }
 330   }
 331
 332   // pos now points to merged or inserted pair, check whether it overlaps with
 333   // subsequent pairs.
 334   while (pos + 1 < mMap.Length()) {
 335     if (mMap[pos].CanBeMerged(mMap[pos + 1])) {
 336       mMap[pos].Merge(mMap[pos + 1]);
 337       mMap.RemoveElementAt(pos + 1);
 338     } else {
 339       break;
 340     }
 341   }
 342 }
 343
 344 void ValidityMap::Clear() { mMap.Clear(); }
 345
 346 size_t ValidityMap::SizeOfExcludingThis(
 347     mozilla::MallocSizeOf mallocSizeOf) const {
 348   return mMap.ShallowSizeOfExcludingThis(mallocSizeOf);
 349 }
 350
 351 ValidityPair& ValidityMap::operator[](uint32_t aIdx) {
 352   return mMap.ElementAt(aIdx);
 353 }
 354
 355 StaticMutex DetailedCacheHitTelemetry::sLock;
 356 uint32_t DetailedCacheHitTelemetry::sRecordCnt = 0;
 357 MOZ_RUNINIT DetailedCacheHitTelemetry::HitRate
 358     DetailedCacheHitTelemetry::sHRStats[kNumOfRanges];
 359
 360 DetailedCacheHitTelemetry::HitRate::HitRate() { Reset(); }
 361
 362 void DetailedCacheHitTelemetry::HitRate::AddRecord(ERecType aType) {
 363   if (aType == HIT) {
 364     ++mHitCnt;
 365   } else {
 366     ++mMissCnt;
 367   }
 368 }
 369
 370 uint32_t DetailedCacheHitTelemetry::HitRate::GetHitRateBucket() const {
 371   if (mHitCnt + mMissCnt == 0) {
 372     return 0;
 373   }
 374   return (100 * mHitCnt) / (mHitCnt + mMissCnt);
 375 }
 376
 377 uint32_t DetailedCacheHitTelemetry::HitRate::Count() {
 378   return mHitCnt + mMissCnt;
 379 }
 380
 381 void DetailedCacheHitTelemetry::HitRate::Reset() {
 382   mHitCnt = 0;
 383   mMissCnt = 0;
 384 }
 385
 386 // static
 387 void DetailedCacheHitTelemetry::AddRecord(ERecType aType,
 388                                           TimeStamp aLoadStart) {
 389   bool isUpToDate = false;
 390   CacheIndex::IsUpToDate(&isUpToDate);
 391   if (!isUpToDate) {
 392     // Ignore the record when the entry file count might be incorrect
 393     return;
 394   }
 395
 396   uint32_t entryCount;
 397   nsresult rv = CacheIndex::GetEntryFileCount(&entryCount);
 398   if (NS_FAILED(rv)) {
 399     return;
 400   }
 401
 402   uint32_t rangeIdx = entryCount / kRangeSize;
 403   if (rangeIdx >= kNumOfRanges) {  // The last range has no upper limit.
 404     rangeIdx = kNumOfRanges - 1;
 405   }
 406
 407 #ifndef ANDROID
 408   nsAutoCString hitMissValue;
 409   if (aType == HIT) {
 410     hitMissValue.AppendLiteral("Hit ");
 411   } else {
 412     hitMissValue.AppendLiteral("Miss ");
 413   }
 414
 415   uint32_t lowerBound = rangeIdx * kRangeSize;
 416   if (rangeIdx < kNumOfRanges - 1) {
 417     uint32_t upperBound = (rangeIdx + 1) * kRangeSize - 1;
 418     hitMissValue.AppendInt(lowerBound);
 419     hitMissValue.AppendLiteral("-");
 420     hitMissValue.AppendInt(upperBound);
 421   } else {
 422     // Since no upper limit
 423     hitMissValue.AppendInt(lowerBound);
 424     hitMissValue.AppendLiteral("+");
 425   }
 426 #endif
 427
 428   StaticMutexAutoLock lock(sLock);
 429
 430   if (aType == MISS) {
 431     mozilla::glean::network::cache_miss_time.AccumulateRawDuration(
 432         TimeStamp::Now() - aLoadStart);
 433   } else {
 434     mozilla::glean::network::cache_hit_time.AccumulateRawDuration(
 435         TimeStamp::Now() - aLoadStart);
 436   }
 437 #ifndef ANDROID
 438   mozilla::glean::network::cache_hit_miss_stat_per_cache_size.Get(hitMissValue)
 439       .Add(1);
 440 #endif
 441
 442   sHRStats[rangeIdx].AddRecord(aType);
 443   ++sRecordCnt;
 444
 445   if (sRecordCnt < kTotalSamplesReportLimit) {
 446     return;
 447   }
 448
 449   sRecordCnt = 0;
 450
 451   for (uint32_t i = 0; i < kNumOfRanges; ++i) {
 452     if (sHRStats[i].Count() >= kHitRateSamplesReportLimit) {
 453 #ifndef ANDROID
 454       nsAutoCString cacheSizeIdx;
 455       cacheSizeIdx.AppendInt(i);
 456       uint32_t hitRateBucket = sHRStats[i].GetHitRateBucket();
 457
 458       mozilla::glean::network::cache_hit_rate_per_cache_size.Get(cacheSizeIdx)
 459           .AccumulateSingleSample(hitRateBucket);
 460 #endif
 461       sHRStats[i].Reset();
 462     }
 463   }
 464 }
 465
 466 StaticMutex CachePerfStats::sLock;
 467 MOZ_RUNINIT CachePerfStats::PerfData
 468     CachePerfStats::sData[CachePerfStats::LAST];
 469 uint32_t CachePerfStats::sCacheSlowCnt = 0;
 470 uint32_t CachePerfStats::sCacheNotSlowCnt = 0;
 471
 472 CachePerfStats::MMA::MMA(uint32_t aTotalWeight, bool aFilter)
 473     : mSum(0), mSumSq(0), mCnt(0), mWeight(aTotalWeight), mFilter(aFilter) {}
 474
 475 void CachePerfStats::MMA::AddValue(uint32_t aValue) {
 476   if (mFilter) {
 477     // Filter high spikes
 478     uint32_t avg = GetAverage();
 479     uint32_t stddev = GetStdDev();
 480     uint32_t maxdiff = avg + (3 * stddev);
 481     if (avg && aValue > avg + maxdiff) {
 482       return;
 483     }
 484   }
 485
 486   if (mCnt < mWeight) {
 487     // Compute arithmetic average until we have at least mWeight values
 488     CheckedInt<uint64_t> newSumSq = CheckedInt<uint64_t>(aValue) * aValue;
 489     newSumSq += mSumSq;
 490     if (!newSumSq.isValid()) {
 491       return;  // ignore this value
 492     }
 493     mSumSq = newSumSq.value();
 494     mSum += aValue;
 495     ++mCnt;
 496   } else {
 497     CheckedInt<uint64_t> newSumSq = mSumSq - mSumSq / mCnt;
 498     newSumSq += static_cast<uint64_t>(aValue) * aValue;
 499     if (!newSumSq.isValid()) {
 500       return;  // ignore this value
 501     }
 502     mSumSq = newSumSq.value();
 503
 504     // Compute modified moving average for more values:
 505     // newAvg = ((weight - 1) * oldAvg + newValue) / weight
 506     mSum -= GetAverage();
 507     mSum += aValue;
 508   }
 509 }
 510
 511 uint32_t CachePerfStats::MMA::GetAverage() {
 512   if (mCnt == 0) {
 513     return 0;
 514   }
 515
 516   return mSum / mCnt;
 517 }
 518
 519 uint32_t CachePerfStats::MMA::GetStdDev() {
 520   if (mCnt == 0) {
 521     return 0;
 522   }
 523
 524   uint32_t avg = GetAverage();
 525   uint64_t avgSq = static_cast<uint64_t>(avg) * avg;
 526   uint64_t variance = mSumSq / mCnt;
 527   if (variance < avgSq) {
 528     // Due to rounding error when using integer data type, it can happen that
 529     // average of squares of the values is smaller than square of the average
 530     // of the values. In this case fix mSumSq.
 531     variance = avgSq;
 532     mSumSq = variance * mCnt;
 533   }
 534
 535   variance -= avgSq;
 536   return sqrt(static_cast<double>(variance));
 537 }
 538
 539 CachePerfStats::PerfData::PerfData()
 540     : mFilteredAvg(50, true), mShortAvg(3, false) {}
 541
 542 void CachePerfStats::PerfData::AddValue(uint32_t aValue, bool aShortOnly) {
 543   if (!aShortOnly) {
 544     mFilteredAvg.AddValue(aValue);
 545   }
 546   mShortAvg.AddValue(aValue);
 547 }
 548
 549 uint32_t CachePerfStats::PerfData::GetAverage(bool aFiltered) {
 550   return aFiltered ? mFilteredAvg.GetAverage() : mShortAvg.GetAverage();
 551 }
 552
 553 uint32_t CachePerfStats::PerfData::GetStdDev(bool aFiltered) {
 554   return aFiltered ? mFilteredAvg.GetStdDev() : mShortAvg.GetStdDev();
 555 }
 556
 557 // static
 558 void CachePerfStats::AddValue(EDataType aType, uint32_t aValue,
 559                               bool aShortOnly) {
 560   StaticMutexAutoLock lock(sLock);
 561   sData[aType].AddValue(aValue, aShortOnly);
 562 }
 563
 564 // static
 565 uint32_t CachePerfStats::GetAverage(EDataType aType, bool aFiltered) {
 566   StaticMutexAutoLock lock(sLock);
 567   return sData[aType].GetAverage(aFiltered);
 568 }
 569
 570 // static
 571 uint32_t CachePerfStats::GetStdDev(EDataType aType, bool aFiltered) {
 572   StaticMutexAutoLock lock(sLock);
 573   return sData[aType].GetStdDev(aFiltered);
 574 }
 575
 576 // static
 577 bool CachePerfStats::IsCacheSlow() {
 578   StaticMutexAutoLock lock(sLock);
 579
 580   // Compare mShortAvg with mFilteredAvg to find out whether cache is getting
 581   // slower. Use only data about single IO operations because ENTRY_OPEN can be
 582   // affected by more factors than a slow disk.
 583   for (uint32_t i = 0; i < ENTRY_OPEN; ++i) {
 584     if (i == IO_WRITE) {
 585       // Skip this data type. IsCacheSlow is used for determining cache slowness
 586       // when opening entries. Writes have low priority and it's normal that
 587       // they are delayed a lot, but this doesn't necessarily affect opening
 588       // cache entries.
 589       continue;
 590     }
 591
 592     uint32_t avgLong = sData[i].GetAverage(true);
 593     if (avgLong == 0) {
 594       // We have no perf data yet, skip this data type.
 595       continue;
 596     }
 597     uint32_t avgShort = sData[i].GetAverage(false);
 598     uint32_t stddevLong = sData[i].GetStdDev(true);
 599     uint32_t maxdiff = avgLong + (3 * stddevLong);
 600
 601     if (avgShort > avgLong + maxdiff) {
 602       LOG(
 603           ("CachePerfStats::IsCacheSlow() - result is slow based on perf "
 604            "type %u [avgShort=%u, avgLong=%u, stddevLong=%u]",
 605            i, avgShort, avgLong, stddevLong));
 606       ++sCacheSlowCnt;
 607       return true;
 608     }
 609   }
 610
 611   ++sCacheNotSlowCnt;
 612   return false;
 613 }
 614
 615 // static
 616 void CachePerfStats::GetSlowStats(uint32_t* aSlow, uint32_t* aNotSlow) {
 617   StaticMutexAutoLock lock(sLock);
 618   *aSlow = sCacheSlowCnt;
 619   *aNotSlow = sCacheNotSlowCnt;
 620 }
 621
 622 void FreeBuffer(void* aBuf) {
 623 #ifndef NS_FREE_PERMANENT_DATA
 624   if (CacheObserver::ShuttingDown()) {
 625     return;
 626   }
 627 #endif
 628
 629   free(aBuf);
 630 }
 631
 632 nsresult ParseAlternativeDataInfo(const char* aInfo, int64_t* _offset,
 633                                   nsACString* _type) {
 634   // The format is: "1;12345,javascript/binary"
 635   //         <version>;<offset>,<type>
 636   mozilla::Tokenizer p(aInfo, nullptr, "/");
 637   uint32_t altDataVersion = 0;
 638   int64_t altDataOffset = -1;
 639
 640   // The metadata format has a wrong version number.
 641   if (!p.ReadInteger(&altDataVersion) || altDataVersion != kAltDataVersion) {
 642     LOG(
 643         ("ParseAlternativeDataInfo() - altDataVersion=%u, "
 644          "expectedVersion=%u",
 645          altDataVersion, kAltDataVersion));
 646     return NS_ERROR_NOT_AVAILABLE;
 647   }
 648
 649   if (!p.CheckChar(';') || !p.ReadInteger(&altDataOffset) ||
 650       !p.CheckChar(',')) {
 651     return NS_ERROR_NOT_AVAILABLE;
 652   }
 653
 654   // The requested alt-data representation is not available
 655   if (altDataOffset < 0) {
 656     return NS_ERROR_NOT_AVAILABLE;
 657   }
 658
 659   if (_offset) {
 660     *_offset = altDataOffset;
 661   }
 662
 663   if (_type) {
 664     mozilla::Unused << p.ReadUntil(Tokenizer::Token::EndOfFile(), *_type);
 665   }
 666
 667   return NS_OK;
 668 }
 669
 670 void BuildAlternativeDataInfo(const char* aInfo, int64_t aOffset,
 671                               nsACString& _retval) {
 672   _retval.Truncate();
 673   _retval.AppendInt(kAltDataVersion);
 674   _retval.Append(';');
 675   _retval.AppendInt(aOffset);
 676   _retval.Append(',');
 677   _retval.Append(aInfo);
 678 }
 679
 680 }  // namespace mozilla::net::CacheFileUtils