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 "CacheLog.h"
   6 #include "CacheFileUtils.h"
   7 #include "LoadContextInfo.h"
   8 #include "nsCOMPtr.h"
   9 #include "nsAutoPtr.h"
  10 #include "nsString.h"
  11 #include <algorithm>
  12
  13
  14 namespace mozilla {
  15 namespace net {
  16 namespace CacheFileUtils {
  17
  18 namespace { // anon
  19
  20 /**
  21  * A simple recursive descent parser for the mapping key.
  22  */
  23 class KeyParser
  24 {
  25 public:
  26   KeyParser(nsACString::const_iterator aCaret, nsACString::const_iterator aEnd)
  27     : caret(aCaret)
  28     , end(aEnd)
  29     // Initialize attributes to their default values
  30     , appId(nsILoadContextInfo::NO_APP_ID)
  31     , isPrivate(false)
  32     , isInBrowser(false)
  33     , isAnonymous(false)
  34     // Initialize the cache key to a zero length by default
  35     , cacheKey(aEnd)
  36     , lastTag(0)
  37   {
  38   }
  39
  40 private:
  41   // Current character being parsed
  42   nsACString::const_iterator caret;
  43   // The end of the buffer
  44   nsACString::const_iterator const end;
  45
  46   // Results
  47   uint32_t appId;
  48   bool isPrivate;
  49   bool isInBrowser;
  50   bool isAnonymous;
  51   nsCString idEnhance;
  52   // Position of the cache key, if present
  53   nsACString::const_iterator cacheKey;
  54
  55   // Keeps the last tag name, used for alphabetical sort checking
  56   char lastTag;
  57
  58   bool ParseTags()
  59   {
  60     // Expects to be at the tag name or at the end
  61     if (caret == end)
  62       return true;
  63
  64     // 'Read' the tag name and move to the next char
  65     char const tag = *caret++;
  66     // Check the alphabetical order, hard-fail on disobedience
  67     if (!(lastTag < tag || tag == ':'))
  68       return false;
  69
  70     lastTag = tag;
  71
  72     switch (tag) {
  73     case ':':
  74       // last possible tag, when present there is the cacheKey following,
  75       // not terminated with ',' and no need to unescape.
  76       cacheKey = caret;
  77       caret = end;
  78       return true;
  79     case 'p':
  80       isPrivate = true;
  81       break;
  82     case 'b':
  83       isInBrowser = true;
  84       break;
  85     case 'a':
  86       isAnonymous = true;
  87       break;
  88     case 'i': {
  89       nsAutoCString appIdString;
  90       if (!ParseValue(&appIdString))
  91         return false;
  92
  93       nsresult rv;
  94       int64_t appId64 = appIdString.ToInteger64(&rv);
  95       if (NS_FAILED(rv))
  96         return false; // appid value is mandatory
  97       if (appId64 < 0 || appId64 > PR_UINT32_MAX)
  98         return false; // not in the range
  99       appId = static_cast<uint32_t>(appId64);
 100
 101       break;
 102     }
 103     case '~':
 104       if (!ParseValue(&idEnhance))
 105         return false;
 106       break;
 107     default:
 108       if (!ParseValue()) // skip any tag values, optional
 109         return false;
 110       break;
 111     }
 112
 113     // Recurse to the next tag
 114     return ParseNextTagOrEnd();
 115   }
 116
 117   bool ParseNextTagOrEnd()
 118   {
 119     // We expect a comma after every tag
 120     if (caret == end || *caret++ != ',')
 121       return false;
 122
 123     // Go to another tag
 124     return ParseTags();
 125   }
 126
 127   bool ParseValue(nsACString * result = nullptr)
 128   {
 129     // If at the end, fail since we expect a comma ; value may be empty tho
 130     if (caret == end)
 131       return false;
 132
 133     // Remeber where the value starts
 134     nsACString::const_iterator val = caret;
 135     nsACString::const_iterator comma = end;
 136     bool escape = false;
 137     while (caret != end) {
 138       nsACString::const_iterator at = caret;
 139       ++caret; // we can safely break/continue the loop now
 140
 141       if (*at == ',') {
 142         if (comma != end) {
 143           // another comma (we have found ",," -> escape)
 144           comma = end;
 145           escape = true;
 146         } else {
 147           comma = at;
 148         }
 149         continue;
 150       }
 151
 152       if (comma != end) {
 153         // after a single comma
 154         break;
 155       }
 156     }
 157
 158     // At this point |comma| points to the last and lone ',' we've hit.
 159     // If a lone comma was not found, |comma| is at the end of the buffer,
 160     // that is not expected and we return failure.
 161
 162     caret = comma;
 163     if (result) {
 164       if (escape) {
 165         // No ReplaceSubstring on nsACString..
 166         nsAutoCString _result(Substring(val, caret));
 167         _result.ReplaceSubstring(NS_LITERAL_CSTRING(",,"), NS_LITERAL_CSTRING(","));
 168         result->Assign(_result);
 169       } else {
 170         result->Assign(Substring(val, caret));
 171       }
 172     }
 173
 174     return caret != end;
 175   }
 176
 177 public:
 178   already_AddRefed<LoadContextInfo> Parse()
 179   {
 180     nsRefPtr<LoadContextInfo> info;
 181     if (ParseTags())
 182       info = GetLoadContextInfo(isPrivate, appId, isInBrowser, isAnonymous);
 183
 184     return info.forget();
 185   }
 186
 187   void URISpec(nsACString &result)
 188   {
 189     // cacheKey is either pointing to end or the position where the cache key is.
 190     result.Assign(Substring(cacheKey, end));
 191   }
 192
 193   void IdEnhance(nsACString &result)
 194   {
 195     result.Assign(idEnhance);
 196   }
 197 };
 198
 199 } // anon
 200
 201 already_AddRefed<nsILoadContextInfo>
 202 ParseKey(const nsCSubstring &aKey,
 203          nsCSubstring *aIdEnhance,
 204          nsCSubstring *aURISpec)
 205 {
 206   nsACString::const_iterator caret, end;
 207   aKey.BeginReading(caret);
 208   aKey.EndReading(end);
 209
 210   KeyParser parser(caret, end);
 211   nsRefPtr<LoadContextInfo> info = parser.Parse();
 212
 213   if (info) {
 214     if (aIdEnhance)
 215       parser.IdEnhance(*aIdEnhance);
 216     if (aURISpec)
 217       parser.URISpec(*aURISpec);
 218   }
 219
 220   return info.forget();
 221 }
 222
 223 void
 224 AppendKeyPrefix(nsILoadContextInfo* aInfo, nsACString &_retval)
 225 {
 226   /**
 227    * This key is used to salt file hashes.  When form of the key is changed
 228    * cache entries will fail to find on disk.
 229    *
 230    * IMPORTANT NOTE:
 231    * Keep the attributes list sorted according their ASCII code.
 232    */
 233
 234   if (aInfo->IsAnonymous()) {
 235     _retval.AppendLiteral("a,");
 236   }
 237
 238   if (aInfo->IsInBrowserElement()) {
 239     _retval.AppendLiteral("b,");
 240   }
 241
 242   if (aInfo->AppId() != nsILoadContextInfo::NO_APP_ID) {
 243     _retval.Append('i');
 244     _retval.AppendInt(aInfo->AppId());
 245     _retval.Append(',');
 246   }
 247
 248   if (aInfo->IsPrivate()) {
 249     _retval.AppendLiteral("p,");
 250   }
 251 }
 252
 253 void
 254 AppendTagWithValue(nsACString & aTarget, char const aTag, nsCSubstring const & aValue)
 255 {
 256   aTarget.Append(aTag);
 257
 258   // First check the value string to save some memory copying
 259   // for cases we don't need to escape at all (most likely).
 260   if (!aValue.IsEmpty()) {
 261     if (aValue.FindChar(',') == kNotFound) {
 262       // No need to escape
 263       aTarget.Append(aValue);
 264     } else {
 265       nsAutoCString escapedValue(aValue);
 266       escapedValue.ReplaceSubstring(
 267         NS_LITERAL_CSTRING(","), NS_LITERAL_CSTRING(",,"));
 268       aTarget.Append(escapedValue);
 269     }
 270   }
 271
 272   aTarget.Append(',');
 273 }
 274
 275 nsresult
 276 KeyMatchesLoadContextInfo(const nsACString &aKey, nsILoadContextInfo *aInfo,
 277                           bool *_retval)
 278 {
 279   nsCOMPtr<nsILoadContextInfo> info = ParseKey(aKey);
 280
 281   if (!info) {
 282     return NS_ERROR_FAILURE;
 283   }
 284
 285   *_retval = info->Equals(aInfo);
 286   return NS_OK;
 287 }
 288
 289 ValidityPair::ValidityPair(uint32_t aOffset, uint32_t aLen)
 290   : mOffset(aOffset), mLen(aLen)
 291 {}
 292
 293 ValidityPair&
 294 ValidityPair::operator=(const ValidityPair& aOther)
 295 {
 296   mOffset = aOther.mOffset;
 297   mLen = aOther.mLen;
 298   return *this;
 299 }
 300
 301 bool
 302 ValidityPair::CanBeMerged(const ValidityPair& aOther) const
 303 {
 304   // The pairs can be merged into a single one if the start of one of the pairs
 305   // is placed anywhere in the validity interval of other pair or exactly after
 306   // its end.
 307   return IsInOrFollows(aOther.mOffset) || aOther.IsInOrFollows(mOffset);
 308 }
 309
 310 bool
 311 ValidityPair::IsInOrFollows(uint32_t aOffset) const
 312 {
 313   return mOffset <= aOffset && mOffset + mLen >= aOffset;
 314 }
 315
 316 bool
 317 ValidityPair::LessThan(const ValidityPair& aOther) const
 318 {
 319   if (mOffset < aOther.mOffset) {
 320     return true;
 321   }
 322
 323   if (mOffset == aOther.mOffset && mLen < aOther.mLen) {
 324     return true;
 325   }
 326
 327   return false;
 328 }
 329
 330 void
 331 ValidityPair::Merge(const ValidityPair& aOther)
 332 {
 333   MOZ_ASSERT(CanBeMerged(aOther));
 334
 335   uint32_t offset = std::min(mOffset, aOther.mOffset);
 336   uint32_t end = std::max(mOffset + mLen, aOther.mOffset + aOther.mLen);
 337
 338   mOffset = offset;
 339   mLen = end - offset;
 340 }
 341
 342 void
 343 ValidityMap::Log() const
 344 {
 345   LOG(("ValidityMap::Log() - number of pairs: %u", mMap.Length()));
 346   for (uint32_t i=0; i<mMap.Length(); i++) {
 347     LOG(("    (%u, %u)", mMap[i].Offset() + 0, mMap[i].Len() + 0));
 348   }
 349 }
 350
 351 uint32_t
 352 ValidityMap::Length() const
 353 {
 354   return mMap.Length();
 355 }
 356
 357 void
 358 ValidityMap::AddPair(uint32_t aOffset, uint32_t aLen)
 359 {
 360   ValidityPair pair(aOffset, aLen);
 361
 362   if (mMap.Length() == 0) {
 363     mMap.AppendElement(pair);
 364     return;
 365   }
 366
 367   // Find out where to place this pair into the map, it can overlap only with
 368   // one preceding pair and all subsequent pairs.
 369   uint32_t pos = 0;
 370   for (pos = mMap.Length(); pos > 0; ) {
 371     --pos;
 372
 373     if (mMap[pos].LessThan(pair)) {
 374       // The new pair should be either inserted after pos or merged with it.
 375       if (mMap[pos].CanBeMerged(pair)) {
 376         // Merge with the preceding pair
 377         mMap[pos].Merge(pair);
 378       } else {
 379         // They don't overlap, element must be placed after pos element
 380         ++pos;
 381         if (pos == mMap.Length()) {
 382           mMap.AppendElement(pair);
 383         } else {
 384           mMap.InsertElementAt(pos, pair);
 385         }
 386       }
 387
 388       break;
 389     }
 390
 391     if (pos == 0) {
 392       // The new pair should be placed in front of all existing pairs.
 393       mMap.InsertElementAt(0, pair);
 394     }
 395   }
 396
 397   // pos now points to merged or inserted pair, check whether it overlaps with
 398   // subsequent pairs.
 399   while (pos + 1 < mMap.Length()) {
 400     if (mMap[pos].CanBeMerged(mMap[pos + 1])) {
 401       mMap[pos].Merge(mMap[pos + 1]);
 402       mMap.RemoveElementAt(pos + 1);
 403     } else {
 404       break;
 405     }
 406   }
 407 }
 408
 409 void
 410 ValidityMap::Clear()
 411 {
 412   mMap.Clear();
 413 }
 414
 415 size_t
 416 ValidityMap::SizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const
 417 {
 418   return mMap.SizeOfExcludingThis(mallocSizeOf);
 419 }
 420
 421 ValidityPair&
 422 ValidityMap::operator[](uint32_t aIdx)
 423 {
 424   return mMap.ElementAt(aIdx);
 425 }
 426
 427 } // CacheFileUtils
 428 } // net
 429 } // mozilla