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/GleanMetrics.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 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(
 371     uint32_t aNumOfBuckets) const {
 372   uint32_t bucketIdx = (aNumOfBuckets * mHitCnt) / (mHitCnt + mMissCnt);
 373   if (bucketIdx ==
 374       aNumOfBuckets) {  // make sure 100% falls into the last bucket
 375     --bucketIdx;
 376   }
 377
 378   return bucketIdx;
 379 }
 380
 381 uint32_t DetailedCacheHitTelemetry::HitRate::Count() {
 382   return mHitCnt + mMissCnt;
 383 }
 384
 385 void DetailedCacheHitTelemetry::HitRate::Reset() {
 386   mHitCnt = 0;
 387   mMissCnt = 0;
 388 }
 389
 390 // static
 391 void DetailedCacheHitTelemetry::AddRecord(ERecType aType,
 392                                           TimeStamp aLoadStart) {
 393   bool isUpToDate = false;
 394   CacheIndex::IsUpToDate(&isUpToDate);
 395   if (!isUpToDate) {
 396     // Ignore the record when the entry file count might be incorrect
 397     return;
 398   }
 399
 400   uint32_t entryCount;
 401   nsresult rv = CacheIndex::GetEntryFileCount(&entryCount);
 402   if (NS_FAILED(rv)) {
 403     return;
 404   }
 405
 406   uint32_t rangeIdx = entryCount / kRangeSize;
 407   if (rangeIdx >= kNumOfRanges) {  // The last range has no upper limit.
 408     rangeIdx = kNumOfRanges - 1;
 409   }
 410
 411   uint32_t hitMissValue = 2 * rangeIdx;  // 2 values per range
 412   if (aType == MISS) {                   // The order is HIT, MISS
 413     ++hitMissValue;
 414   }
 415
 416   StaticMutexAutoLock lock(sLock);
 417
 418   if (aType == MISS) {
 419     mozilla::Telemetry::AccumulateTimeDelta(
 420         mozilla::Telemetry::NETWORK_CACHE_V2_MISS_TIME_MS, aLoadStart);
 421   } else {
 422     mozilla::glean::network::cache_hit_time.AccumulateRawDuration(
 423         TimeStamp::Now() - aLoadStart);
 424   }
 425
 426   Telemetry::Accumulate(Telemetry::NETWORK_CACHE_HIT_MISS_STAT_PER_CACHE_SIZE,
 427                         hitMissValue);
 428
 429   sHRStats[rangeIdx].AddRecord(aType);
 430   ++sRecordCnt;
 431
 432   if (sRecordCnt < kTotalSamplesReportLimit) {
 433     return;
 434   }
 435
 436   sRecordCnt = 0;
 437
 438   for (uint32_t i = 0; i < kNumOfRanges; ++i) {
 439     if (sHRStats[i].Count() >= kHitRateSamplesReportLimit) {
 440       // The telemetry enums are grouped by buckets as follows:
 441       // Telemetry value : 0,1,2,3, ... ,19,20,21,22, ... ,398,399
 442       // Hit rate bucket : 0,0,0,0, ... , 0, 1, 1, 1, ... , 19, 19
 443       // Cache size range: 0,1,2,3, ... ,19, 0, 1, 2, ... , 18, 19
 444       uint32_t bucketOffset =
 445           sHRStats[i].GetHitRateBucket(kHitRateBuckets) * kNumOfRanges;
 446
 447       Telemetry::Accumulate(Telemetry::NETWORK_CACHE_HIT_RATE_PER_CACHE_SIZE,
 448                             bucketOffset + i);
 449       sHRStats[i].Reset();
 450     }
 451   }
 452 }
 453
 454 StaticMutex CachePerfStats::sLock;
 455 CachePerfStats::PerfData CachePerfStats::sData[CachePerfStats::LAST];
 456 uint32_t CachePerfStats::sCacheSlowCnt = 0;
 457 uint32_t CachePerfStats::sCacheNotSlowCnt = 0;
 458
 459 CachePerfStats::MMA::MMA(uint32_t aTotalWeight, bool aFilter)
 460     : mSum(0), mSumSq(0), mCnt(0), mWeight(aTotalWeight), mFilter(aFilter) {}
 461
 462 void CachePerfStats::MMA::AddValue(uint32_t aValue) {
 463   if (mFilter) {
 464     // Filter high spikes
 465     uint32_t avg = GetAverage();
 466     uint32_t stddev = GetStdDev();
 467     uint32_t maxdiff = avg + (3 * stddev);
 468     if (avg && aValue > avg + maxdiff) {
 469       return;
 470     }
 471   }
 472
 473   if (mCnt < mWeight) {
 474     // Compute arithmetic average until we have at least mWeight values
 475     CheckedInt<uint64_t> newSumSq = CheckedInt<uint64_t>(aValue) * aValue;
 476     newSumSq += mSumSq;
 477     if (!newSumSq.isValid()) {
 478       return;  // ignore this value
 479     }
 480     mSumSq = newSumSq.value();
 481     mSum += aValue;
 482     ++mCnt;
 483   } else {
 484     CheckedInt<uint64_t> newSumSq = mSumSq - mSumSq / mCnt;
 485     newSumSq += static_cast<uint64_t>(aValue) * aValue;
 486     if (!newSumSq.isValid()) {
 487       return;  // ignore this value
 488     }
 489     mSumSq = newSumSq.value();
 490
 491     // Compute modified moving average for more values:
 492     // newAvg = ((weight - 1) * oldAvg + newValue) / weight
 493     mSum -= GetAverage();
 494     mSum += aValue;
 495   }
 496 }
 497
 498 uint32_t CachePerfStats::MMA::GetAverage() {
 499   if (mCnt == 0) {
 500     return 0;
 501   }
 502
 503   return mSum / mCnt;
 504 }
 505
 506 uint32_t CachePerfStats::MMA::GetStdDev() {
 507   if (mCnt == 0) {
 508     return 0;
 509   }
 510
 511   uint32_t avg = GetAverage();
 512   uint64_t avgSq = static_cast<uint64_t>(avg) * avg;
 513   uint64_t variance = mSumSq / mCnt;
 514   if (variance < avgSq) {
 515     // Due to rounding error when using integer data type, it can happen that
 516     // average of squares of the values is smaller than square of the average
 517     // of the values. In this case fix mSumSq.
 518     variance = avgSq;
 519     mSumSq = variance * mCnt;
 520   }
 521
 522   variance -= avgSq;
 523   return sqrt(static_cast<double>(variance));
 524 }
 525
 526 CachePerfStats::PerfData::PerfData()
 527     : mFilteredAvg(50, true), mShortAvg(3, false) {}
 528
 529 void CachePerfStats::PerfData::AddValue(uint32_t aValue, bool aShortOnly) {
 530   if (!aShortOnly) {
 531     mFilteredAvg.AddValue(aValue);
 532   }
 533   mShortAvg.AddValue(aValue);
 534 }
 535
 536 uint32_t CachePerfStats::PerfData::GetAverage(bool aFiltered) {
 537   return aFiltered ? mFilteredAvg.GetAverage() : mShortAvg.GetAverage();
 538 }
 539
 540 uint32_t CachePerfStats::PerfData::GetStdDev(bool aFiltered) {
 541   return aFiltered ? mFilteredAvg.GetStdDev() : mShortAvg.GetStdDev();
 542 }
 543
 544 // static
 545 void CachePerfStats::AddValue(EDataType aType, uint32_t aValue,
 546                               bool aShortOnly) {
 547   StaticMutexAutoLock lock(sLock);
 548   sData[aType].AddValue(aValue, aShortOnly);
 549 }
 550
 551 // static
 552 uint32_t CachePerfStats::GetAverage(EDataType aType, bool aFiltered) {
 553   StaticMutexAutoLock lock(sLock);
 554   return sData[aType].GetAverage(aFiltered);
 555 }
 556
 557 // static
 558 uint32_t CachePerfStats::GetStdDev(EDataType aType, bool aFiltered) {
 559   StaticMutexAutoLock lock(sLock);
 560   return sData[aType].GetStdDev(aFiltered);
 561 }
 562
 563 // static
 564 bool CachePerfStats::IsCacheSlow() {
 565   StaticMutexAutoLock lock(sLock);
 566
 567   // Compare mShortAvg with mFilteredAvg to find out whether cache is getting
 568   // slower. Use only data about single IO operations because ENTRY_OPEN can be
 569   // affected by more factors than a slow disk.
 570   for (uint32_t i = 0; i < ENTRY_OPEN; ++i) {
 571     if (i == IO_WRITE) {
 572       // Skip this data type. IsCacheSlow is used for determining cache slowness
 573       // when opening entries. Writes have low priority and it's normal that
 574       // they are delayed a lot, but this doesn't necessarily affect opening
 575       // cache entries.
 576       continue;
 577     }
 578
 579     uint32_t avgLong = sData[i].GetAverage(true);
 580     if (avgLong == 0) {
 581       // We have no perf data yet, skip this data type.
 582       continue;
 583     }
 584     uint32_t avgShort = sData[i].GetAverage(false);
 585     uint32_t stddevLong = sData[i].GetStdDev(true);
 586     uint32_t maxdiff = avgLong + (3 * stddevLong);
 587
 588     if (avgShort > avgLong + maxdiff) {
 589       LOG(
 590           ("CachePerfStats::IsCacheSlow() - result is slow based on perf "
 591            "type %u [avgShort=%u, avgLong=%u, stddevLong=%u]",
 592            i, avgShort, avgLong, stddevLong));
 593       ++sCacheSlowCnt;
 594       return true;
 595     }
 596   }
 597
 598   ++sCacheNotSlowCnt;
 599   return false;
 600 }
 601
 602 // static
 603 void CachePerfStats::GetSlowStats(uint32_t* aSlow, uint32_t* aNotSlow) {
 604   StaticMutexAutoLock lock(sLock);
 605   *aSlow = sCacheSlowCnt;
 606   *aNotSlow = sCacheNotSlowCnt;
 607 }
 608
 609 void FreeBuffer(void* aBuf) {
 610 #ifndef NS_FREE_PERMANENT_DATA
 611   if (CacheObserver::ShuttingDown()) {
 612     return;
 613   }
 614 #endif
 615
 616   free(aBuf);
 617 }
 618
 619 nsresult ParseAlternativeDataInfo(const char* aInfo, int64_t* _offset,
 620                                   nsACString* _type) {
 621   // The format is: "1;12345,javascript/binary"
 622   //         <version>;<offset>,<type>
 623   mozilla::Tokenizer p(aInfo, nullptr, "/");
 624   uint32_t altDataVersion = 0;
 625   int64_t altDataOffset = -1;
 626
 627   // The metadata format has a wrong version number.
 628   if (!p.ReadInteger(&altDataVersion) || altDataVersion != kAltDataVersion) {
 629     LOG(
 630         ("ParseAlternativeDataInfo() - altDataVersion=%u, "
 631          "expectedVersion=%u",
 632          altDataVersion, kAltDataVersion));
 633     return NS_ERROR_NOT_AVAILABLE;
 634   }
 635
 636   if (!p.CheckChar(';') || !p.ReadInteger(&altDataOffset) ||
 637       !p.CheckChar(',')) {
 638     return NS_ERROR_NOT_AVAILABLE;
 639   }
 640
 641   // The requested alt-data representation is not available
 642   if (altDataOffset < 0) {
 643     return NS_ERROR_NOT_AVAILABLE;
 644   }
 645
 646   if (_offset) {
 647     *_offset = altDataOffset;
 648   }
 649
 650   if (_type) {
 651     mozilla::Unused << p.ReadUntil(Tokenizer::Token::EndOfFile(), *_type);
 652   }
 653
 654   return NS_OK;
 655 }
 656
 657 void BuildAlternativeDataInfo(const char* aInfo, int64_t aOffset,
 658                               nsACString& _retval) {
 659   _retval.Truncate();
 660   _retval.AppendInt(kAltDataVersion);
 661   _retval.Append(';');
 662   _retval.AppendInt(aOffset);
 663   _retval.Append(',');
 664   _retval.Append(aInfo);
 665 }
 666
 667 }  // namespace mozilla::net::CacheFileUtils