Quelle CacheFileUtils.cpp Sprache: C

/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "CacheIndex.h"
#include "CacheLog.h"
#include "CacheFileUtils.h"
#include "CacheObserver.h"
#include "LoadContextInfo.h"
#include "mozilla/glean/NetwerkProtocolHttpMetrics.h"
#include "mozilla/Tokenizer.h"
#include "mozilla/Telemetry.h"
#include "nsCOMPtr.h"
#include "nsString.h"
#include <algorithm>
#include "mozilla/Unused.h"

namespace mozilla::net::CacheFileUtils {

// This designates the format for the "alt-data" metadata.
// When the format changes we need to update the version.
static uint32_t const kAltDataVersion = 1;
const char* kAltDataKey = "alt-data";

namespace {

/**
* A simple recursive descent parser for the mapping key.
*/
class KeyParser : protected Tokenizer {
public:
  explicit KeyParser(nsACString const& aInput)
      : Tokenizer(aInput),
        isAnonymous(false)
        // Initialize the cache key to a zero length by default
        ,
        lastTag(0) {}

private:
  // Results
  OriginAttributes originAttribs;
  bool isAnonymous;
  nsCString idEnhance;
  nsDependentCSubstring cacheKey;

  // Keeps the last tag name, used for alphabetical sort checking
  char lastTag;

  // Classifier for the 'tag' character valid range.
  // Explicitly using unsigned char as 127 is -1 when signed and it would only
  // produce a warning.
  static bool TagChar(const char aChar) {
    unsigned char c = static_cast<unsigned char>(aChar);
    return c >= ' ' && c <= '\x7f';
  }

  bool ParseTags() {
    // Expects to be at the tag name or at the end
    if (CheckEOF()) {
      return true;
    }

    char tag;
    if (!ReadChar(&TagChar, &tag)) {
      return false;
    }

    // Check the alphabetical order, hard-fail on disobedience
    if (!(lastTag < tag || tag == ':')) {
      return false;
    }
    lastTag = tag;

    switch (tag) {
      case ':':
        // last possible tag, when present there is the cacheKey following,
        // not terminated with ',' and no need to unescape.
        cacheKey.Rebind(mCursor, mEnd - mCursor);
        return true;
      case 'O': {
        nsAutoCString originSuffix;
        if (!ParseValue(&originSuffix) ||
            !originAttribs.PopulateFromSuffix(originSuffix)) {
          return false;
        }
        break;
      }
      case 'p':
        originAttribs.SyncAttributesWithPrivateBrowsing(true);
        break;
      case 'b':
        // Leaving to be able to read and understand oldformatted entries
        break;
      case 'a':
        isAnonymous = true;
        break;
      case 'i': {
        // Leaving to be able to read and understand oldformatted entries
        uint32_t deprecatedAppId = 0;
        if (!ReadInteger(&deprecatedAppId)) {
          return false;  // not a valid 32-bit integer
        }
        break;
      }
      case '~':
        if (!ParseValue(&idEnhance)) {
          return false;
        }
        break;
      default:
        if (!ParseValue()) {  // skip any tag values, optional
          return false;
        }
        break;
    }

    // We expect a comma after every tag
    if (!CheckChar(',')) {
      return false;
    }

    // Recurse to the next tag
    return ParseTags();
  }

  bool ParseValue(nsACString* result = nullptr) {
    // If at the end, fail since we expect a comma ; value may be empty tho
    if (CheckEOF()) {
      return false;
    }

    Token t;
    while (Next(t)) {
      if (!Token::Char(',').Equals(t)) {
        if (result) {
          result->Append(t.Fragment());
        }
        continue;
      }

      if (CheckChar(',')) {
        // Two commas in a row, escaping
        if (result) {
          result->Append(',');
        }
        continue;
      }

      // We must give the comma back since the upper calls expect it
      Rollback();
      return true;
    }

    return false;
  }

public:
  already_AddRefed<LoadContextInfo> Parse() {
    RefPtr<LoadContextInfo> info;
    if (ParseTags()) {
      info = GetLoadContextInfo(isAnonymous, originAttribs);
    }

    return info.forget();
  }

  void URISpec(nsACString& result) { result.Assign(cacheKey); }

  void IdEnhance(nsACString& result) { result.Assign(idEnhance); }
};

}  // namespace

already_AddRefed<nsILoadContextInfo> ParseKey(const nsACString& aKey,
                                              nsACString* aIdEnhance,
                                              nsACString* aURISpec) {
  KeyParser parser(aKey);
  RefPtr<LoadContextInfo> info = parser.Parse();

  if (info) {
    if (aIdEnhance) parser.IdEnhance(*aIdEnhance);
    if (aURISpec) parser.URISpec(*aURISpec);
  }

  return info.forget();
}

void AppendKeyPrefix(nsILoadContextInfo* aInfo, nsACString& _retval) {
  /**
   * This key is used to salt file hashes.  When form of the key is changed
   * cache entries will fail to find on disk.
   *
   * IMPORTANT NOTE:
   * Keep the attributes list sorted according their ASCII code.
   */

  if (!aInfo) {
    return;
  }

  OriginAttributes const* oa = aInfo->OriginAttributesPtr();
  nsAutoCString suffix;
  oa->CreateSuffix(suffix);
  if (!suffix.IsEmpty()) {
    AppendTagWithValue(_retval, 'O', suffix);
  }

  if (aInfo->IsAnonymous()) {
    _retval.AppendLiteral("a,");
  }

  if (aInfo->IsPrivate()) {
    _retval.AppendLiteral("p,");
  }
}

void AppendTagWithValue(nsACString& aTarget, char const aTag,
                        const nsACString& aValue) {
  aTarget.Append(aTag);

  // First check the value string to save some memory copying
  // for cases we don't need to escape at all (most likely).
  if (!aValue.IsEmpty()) {
    if (!aValue.Contains(',')) {
      // No need to escape
      aTarget.Append(aValue);
    } else {
      nsAutoCString escapedValue(aValue);
      escapedValue.ReplaceSubstring(","_ns, ",,"_ns);
      aTarget.Append(escapedValue);
    }
  }

  aTarget.Append(',');
}

nsresult KeyMatchesLoadContextInfo(const nsACString& aKey,
                                   nsILoadContextInfo* aInfo, bool* _retval) {
  nsCOMPtr<nsILoadContextInfo> info = ParseKey(aKey);

  if (!info) {
    return NS_ERROR_FAILURE;
  }

  *_retval = info->Equals(aInfo);
  return NS_OK;
}

ValidityPair::ValidityPair(uint32_t aOffset, uint32_t aLen)
    : mOffset(aOffset), mLen(aLen) {}

bool ValidityPair::CanBeMerged(const ValidityPair& aOther) const {
  // The pairs can be merged into a single one if the start of one of the pairs
  // is placed anywhere in the validity interval of other pair or exactly after
  // its end.
  return IsInOrFollows(aOther.mOffset) || aOther.IsInOrFollows(mOffset);
}

bool ValidityPair::IsInOrFollows(uint32_t aOffset) const {
  return mOffset <= aOffset && mOffset + mLen >= aOffset;
}

bool ValidityPair::LessThan(const ValidityPair& aOther) const {
  if (mOffset < aOther.mOffset) {
    return true;
  }

  if (mOffset == aOther.mOffset && mLen < aOther.mLen) {
    return true;
  }

  return false;
}

void ValidityPair::Merge(const ValidityPair& aOther) {
  MOZ_ASSERT(CanBeMerged(aOther));

  uint32_t offset = std::min(mOffset, aOther.mOffset);
  uint32_t end = std::max(mOffset + mLen, aOther.mOffset + aOther.mLen);

  mOffset = offset;
  mLen = end - offset;
}

void ValidityMap::Log() const {
  LOG(("ValidityMap::Log() - number of pairs: %zu", mMap.Length()));
  for (uint32_t i = 0; i < mMap.Length(); i++) {
    LOG((" (%u, %u)", mMap[i].Offset() + 0, mMap[i].Len() + 0));
  }
}

uint32_t ValidityMap::Length() const { return mMap.Length(); }

void ValidityMap::AddPair(uint32_t aOffset, uint32_t aLen) {
  ValidityPair pair(aOffset, aLen);

  if (mMap.Length() == 0) {
    mMap.AppendElement(pair);
    return;
  }

  // Find out where to place this pair into the map, it can overlap only with
  // one preceding pair and all subsequent pairs.
  uint32_t pos = 0;
  for (pos = mMap.Length(); pos > 0;) {
    --pos;

    if (mMap[pos].LessThan(pair)) {
      // The new pair should be either inserted after pos or merged with it.
      if (mMap[pos].CanBeMerged(pair)) {
        // Merge with the preceding pair
        mMap[pos].Merge(pair);
      } else {
        // They don't overlap, element must be placed after pos element
        ++pos;
        if (pos == mMap.Length()) {
          mMap.AppendElement(pair);
        } else {
          mMap.InsertElementAt(pos, pair);
        }
      }

      break;
    }

    if (pos == 0) {
      // The new pair should be placed in front of all existing pairs.
      mMap.InsertElementAt(0, pair);
    }
  }

  // pos now points to merged or inserted pair, check whether it overlaps with
  // subsequent pairs.
  while (pos + 1 < mMap.Length()) {
    if (mMap[pos].CanBeMerged(mMap[pos + 1])) {
      mMap[pos].Merge(mMap[pos + 1]);
      mMap.RemoveElementAt(pos + 1);
    } else {
      break;
    }
  }
}

void ValidityMap::Clear() { mMap.Clear(); }

size_t ValidityMap::SizeOfExcludingThis(
    mozilla::MallocSizeOf mallocSizeOf) const {
  return mMap.ShallowSizeOfExcludingThis(mallocSizeOf);
}

ValidityPair& ValidityMap::operator[](uint32_t aIdx) {
  return mMap.ElementAt(aIdx);
}

StaticMutex DetailedCacheHitTelemetry::sLock;
uint32_t DetailedCacheHitTelemetry::sRecordCnt = 0;
MOZ_RUNINIT DetailedCacheHitTelemetry::HitRate
    DetailedCacheHitTelemetry::sHRStats[kNumOfRanges];

DetailedCacheHitTelemetry::HitRate::HitRate() { Reset(); }

void DetailedCacheHitTelemetry::HitRate::AddRecord(ERecType aType) {
  if (aType == HIT) {
    ++mHitCnt;
  } else {
    ++mMissCnt;
  }
}

uint32_t DetailedCacheHitTelemetry::HitRate::GetHitRateBucket() const {
  if (mHitCnt + mMissCnt == 0) {
    return 0;
  }
  return (100 * mHitCnt) / (mHitCnt + mMissCnt);
}

uint32_t DetailedCacheHitTelemetry::HitRate::Count() {
  return mHitCnt + mMissCnt;
}

void DetailedCacheHitTelemetry::HitRate::Reset() {
  mHitCnt = 0;
  mMissCnt = 0;
}

// static
void DetailedCacheHitTelemetry::AddRecord(ERecType aType,
                                          TimeStamp aLoadStart) {
  bool isUpToDate = false;
  CacheIndex::IsUpToDate(&isUpToDate);
  if (!isUpToDate) {
    // Ignore the record when the entry file count might be incorrect
    return;
  }

  uint32_t entryCount;
  nsresult rv = CacheIndex::GetEntryFileCount(&entryCount);
  if (NS_FAILED(rv)) {
    return;
  }

  uint32_t rangeIdx = entryCount / kRangeSize;
  if (rangeIdx >= kNumOfRanges) {  // The last range has no upper limit.
    rangeIdx = kNumOfRanges - 1;
  }

#ifndef ANDROID
  nsAutoCString hitMissValue;
  if (aType == HIT) {
    hitMissValue.AppendLiteral("Hit ");
  } else {
    hitMissValue.AppendLiteral("Miss ");
  }

  uint32_t lowerBound = rangeIdx * kRangeSize;
  if (rangeIdx < kNumOfRanges - 1) {
    uint32_t upperBound = (rangeIdx + 1) * kRangeSize - 1;
    hitMissValue.AppendInt(lowerBound);
    hitMissValue.AppendLiteral("-");
    hitMissValue.AppendInt(upperBound);
  } else {
    // Since no upper limit
    hitMissValue.AppendInt(lowerBound);
    hitMissValue.AppendLiteral("+");
  }
#endif

  StaticMutexAutoLock lock(sLock);

  if (aType == MISS) {
    mozilla::glean::network::cache_miss_time.AccumulateRawDuration(
        TimeStamp::Now() - aLoadStart);
  } else {
    mozilla::glean::network::cache_hit_time.AccumulateRawDuration(
        TimeStamp::Now() - aLoadStart);
  }
#ifndef ANDROID
  mozilla::glean::network::cache_hit_miss_stat_per_cache_size.Get(hitMissValue)
      .Add(1);
#endif

  sHRStats[rangeIdx].AddRecord(aType);
  ++sRecordCnt;

  if (sRecordCnt < kTotalSamplesReportLimit) {
    return;
  }

  sRecordCnt = 0;

  for (uint32_t i = 0; i < kNumOfRanges; ++i) {
    if (sHRStats[i].Count() >= kHitRateSamplesReportLimit) {
#ifndef ANDROID
      nsAutoCString cacheSizeIdx;
      cacheSizeIdx.AppendInt(i);
      uint32_t hitRateBucket = sHRStats[i].GetHitRateBucket();

      mozilla::glean::network::cache_hit_rate_per_cache_size.Get(cacheSizeIdx)
          .AccumulateSingleSample(hitRateBucket);
#endif
      sHRStats[i].Reset();
    }
  }
}

StaticMutex CachePerfStats::sLock;
MOZ_RUNINIT CachePerfStats::PerfData
    CachePerfStats::sData[CachePerfStats::LAST];
uint32_t CachePerfStats::sCacheSlowCnt = 0;
uint32_t CachePerfStats::sCacheNotSlowCnt = 0;

CachePerfStats::MMA::MMA(uint32_t aTotalWeight, bool aFilter)
    : mSum(0), mSumSq(0), mCnt(0), mWeight(aTotalWeight), mFilter(aFilter) {}

void CachePerfStats::MMA::AddValue(uint32_t aValue) {
  if (mFilter) {
    // Filter high spikes
    uint32_t avg = GetAverage();
    uint32_t stddev = GetStdDev();
    uint32_t maxdiff = avg + (3 * stddev);
    if (avg && aValue > avg + maxdiff) {
      return;
    }
  }

  if (mCnt < mWeight) {
    // Compute arithmetic average until we have at least mWeight values
    CheckedInt<uint64_t> newSumSq = CheckedInt<uint64_t>(aValue) * aValue;
    newSumSq += mSumSq;
    if (!newSumSq.isValid()) {
      return;  // ignore this value
    }
    mSumSq = newSumSq.value();
    mSum += aValue;
    ++mCnt;
  } else {
    CheckedInt<uint64_t> newSumSq = mSumSq - mSumSq / mCnt;
    newSumSq += static_cast<uint64_t>(aValue) * aValue;
    if (!newSumSq.isValid()) {
      return;  // ignore this value
    }
    mSumSq = newSumSq.value();

    // Compute modified moving average for more values:
    // newAvg = ((weight - 1) * oldAvg + newValue) / weight
    mSum -= GetAverage();
    mSum += aValue;
  }
}

uint32_t CachePerfStats::MMA::GetAverage() {
  if (mCnt == 0) {
    return 0;
  }

  return mSum / mCnt;
}

uint32_t CachePerfStats::MMA::GetStdDev() {
  if (mCnt == 0) {
    return 0;
  }

  uint32_t avg = GetAverage();
  uint64_t avgSq = static_cast<uint64_t>(avg) * avg;
  uint64_t variance = mSumSq / mCnt;
  if (variance < avgSq) {
    // Due to rounding error when using integer data type, it can happen that
    // average of squares of the values is smaller than square of the average
    // of the values. In this case fix mSumSq.
    variance = avgSq;
    mSumSq = variance * mCnt;
  }

  variance -= avgSq;
  return sqrt(static_cast<double>(variance));
}

CachePerfStats::PerfData::PerfData()
    : mFilteredAvg(50, true), mShortAvg(3, false) {}

void CachePerfStats::PerfData::AddValue(uint32_t aValue, bool aShortOnly) {
  if (!aShortOnly) {
    mFilteredAvg.AddValue(aValue);
  }
  mShortAvg.AddValue(aValue);
}

uint32_t CachePerfStats::PerfData::GetAverage(bool aFiltered) {
  return aFiltered ? mFilteredAvg.GetAverage() : mShortAvg.GetAverage();
}

uint32_t CachePerfStats::PerfData::GetStdDev(bool aFiltered) {
  return aFiltered ? mFilteredAvg.GetStdDev() : mShortAvg.GetStdDev();
}

// static
void CachePerfStats::AddValue(EDataType aType, uint32_t aValue,
                              bool aShortOnly) {
  StaticMutexAutoLock lock(sLock);
  sData[aType].AddValue(aValue, aShortOnly);
}

// static
uint32_t CachePerfStats::GetAverage(EDataType aType, bool aFiltered) {
  StaticMutexAutoLock lock(sLock);
  return sData[aType].GetAverage(aFiltered);
}

// static
uint32_t CachePerfStats::GetStdDev(EDataType aType, bool aFiltered) {
  StaticMutexAutoLock lock(sLock);
  return sData[aType].GetStdDev(aFiltered);
}

// static
bool CachePerfStats::IsCacheSlow() {
  StaticMutexAutoLock lock(sLock);

  // Compare mShortAvg with mFilteredAvg to find out whether cache is getting
  // slower. Use only data about single IO operations because ENTRY_OPEN can be
  // affected by more factors than a slow disk.
  for (uint32_t i = 0; i < ENTRY_OPEN; ++i) {
    if (i == IO_WRITE) {
      // Skip this data type. IsCacheSlow is used for determining cache slowness
      // when opening entries. Writes have low priority and it's normal that
      // they are delayed a lot, but this doesn't necessarily affect opening
      // cache entries.
      continue;
    }

    uint32_t avgLong = sData[i].GetAverage(true);
    if (avgLong == 0) {
      // We have no perf data yet, skip this data type.
      continue;
    }
    uint32_t avgShort = sData[i].GetAverage(false);
    uint32_t stddevLong = sData[i].GetStdDev(true);
    uint32_t maxdiff = avgLong + (3 * stddevLong);

    if (avgShort > avgLong + maxdiff) {
      LOG(
          ("CachePerfStats::IsCacheSlow() - result is slow based on perf "
           "type %u [avgShort=%u, avgLong=%u, stddevLong=%u]",
           i, avgShort, avgLong, stddevLong));
      ++sCacheSlowCnt;
      return true;
    }
  }

  ++sCacheNotSlowCnt;
  return false;
}

// static
void CachePerfStats::GetSlowStats(uint32_t* aSlow, uint32_t* aNotSlow) {
  StaticMutexAutoLock lock(sLock);
  *aSlow = sCacheSlowCnt;
  *aNotSlow = sCacheNotSlowCnt;
}

void FreeBuffer(void* aBuf) {
#ifndef NS_FREE_PERMANENT_DATA
  if (CacheObserver::ShuttingDown()) {
    return;
  }
#endif

  free(aBuf);
}

nsresult ParseAlternativeDataInfo(const char* aInfo, int64_t* _offset,
                                  nsACString* _type) {
  // The format is: "1;12345,javascript/binary"
  //         <version>;<offset>,<type>
  mozilla::Tokenizer p(aInfo, nullptr, "/");
  uint32_t altDataVersion = 0;
  int64_t altDataOffset = -1;

  // The metadata format has a wrong version number.
  if (!p.ReadInteger(&altDataVersion) || altDataVersion != kAltDataVersion) {
    LOG(
        ("ParseAlternativeDataInfo() - altDataVersion=%u, "
         "expectedVersion=%u",
         altDataVersion, kAltDataVersion));
    return NS_ERROR_NOT_AVAILABLE;
  }

  if (!p.CheckChar(';') || !p.ReadInteger(&altDataOffset) ||
      !p.CheckChar(',')) {
    return NS_ERROR_NOT_AVAILABLE;
  }

  // The requested alt-data representation is not available
  if (altDataOffset < 0) {
    return NS_ERROR_NOT_AVAILABLE;
  }

  if (_offset) {
    *_offset = altDataOffset;
  }

  if (_type) {
    mozilla::Unused << p.ReadUntil(Tokenizer::Token::EndOfFile(), *_type);
  }

  return NS_OK;
}

void BuildAlternativeDataInfo(const char* aInfo, int64_t aOffset,
                              nsACString& _retval) {
  _retval.Truncate();
  _retval.AppendInt(kAltDataVersion);
  _retval.Append(';');
  _retval.AppendInt(aOffset);
  _retval.Append(',');
  _retval.Append(aInfo);
}

}  // namespace mozilla::net::CacheFileUtils

quality96%

¤ Dauer der Verarbeitung: 0.20 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.