netwerk/cache/src/nsDiskCacheMap.h

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /* vim:set ts=4 sw=4 sts=4 cin et: */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is nsDiskCacheMap.h, released
  17  * March 23, 2001.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 2001
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *   Patrick C. Beard <beard@netscape.com>
  26  *   Gordon Sheridan  <gordon@netscape.com>
  27  *
  28  * Alternatively, the contents of this file may be used under the terms of
  29  * either the GNU General Public License Version 2 or later (the "GPL"), or
  30  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  31  * in which case the provisions of the GPL or the LGPL are applicable instead
  32  * of those above. If you wish to allow use of your version of this file only
  33  * under the terms of either the GPL or the LGPL, and not to allow others to
  34  * use your version of this file under the terms of the MPL, indicate your
  35  * decision by deleting the provisions above and replace them with the notice
  36  * and other provisions required by the GPL or the LGPL. If you do not delete
  37  * the provisions above, a recipient may use your version of this file under
  38  * the terms of any one of the MPL, the GPL or the LGPL.
  39  *
  40  * ***** END LICENSE BLOCK ***** */
  41
  42 #ifndef _nsDiskCacheMap_h_
  43 #define _nsDiskCacheMap_h_
  44
  45 #include <limits.h>
  46
  47 #include "prtypes.h"
  48 #include "prnetdb.h"
  49 #include "nsDebug.h"
  50 #include "nsError.h"
  51 #include "nsILocalFile.h"
  52
  53 #include "nsDiskCache.h"
  54 #include "nsDiskCacheBlockFile.h"
  55
  56
  57 class nsDiskCacheBinding;
  58 struct nsDiskCacheEntry;
  59
  60 /******************************************************************************
  61  *  nsDiskCacheRecord
  62  *
  63  *   Cache Location Format
  64  *
  65  *    1000 0000 0000 0000 0000 0000 0000 0000 : initialized bit
  66  *
  67  *    0011 0000 0000 0000 0000 0000 0000 0000 : File Selector (0 = separate file)
  68  *    0000 0011 0000 0000 0000 0000 0000 0000 : number of extra contiguous blocks 1-4
  69  *    0100 1100 0000 0000 0000 0000 0000 0000 : reserved bits
  70  *    0000 0000 1111 1111 1111 1111 1111 1111 : block#  0-16777216 (2^24)
  71  *
  72  *    0000 0000 1111 1111 1111 1111 0000 0000 : eFileSizeMask (size of file in k: see note)
  73  *    0000 0000 0000 0000 0000 0000 1111 1111 : eFileGenerationMask
  74  *
  75  *  File Selector:
  76  *      0 = separate file on disk
  77  *      1 = 256 byte block file
  78  *      2 = 1k block file
  79  *      3 = 4k block file
  80  *
  81  *  eFileSizeMask note:  Files larger than 64 MiB have zero size stored in the
  82  *                       location.  The file itself must be examined to determine
  83  *                       its actual size.  (XXX This is broken in places -darin)
  84  *
  85  *****************************************************************************/
  86
  87 #define BLOCK_SIZE_FOR_INDEX(index)  ((index) ? (256 << (2 * ((index) - 1))) : 0)
  88
  89 // Min and max values for the number of records in the DiskCachemap
  90 #define kMinRecordCount    512
  91 #define kMaxRecordCount    8192
  92
  93 #define kSeparateFile      0
  94 #define kMaxDataFileSize   0x4000000   // 64 MiB
  95 #define kBuckets           (1 << 5)    // must be a power of 2!
  96
  97 class nsDiskCacheRecord {
  98
  99 private:
 100     PRUint32    mHashNumber;
 101     PRUint32    mEvictionRank;
 102     PRUint32    mDataLocation;
 103     PRUint32    mMetaLocation;
 104
 105     enum {
 106         eLocationInitializedMask = 0x80000000,
 107
 108         eLocationSelectorMask    = 0x30000000,
 109         eLocationSelectorOffset  = 28,
 110
 111         eExtraBlocksMask         = 0x03000000,
 112         eExtraBlocksOffset       = 24,
 113
 114         eReservedMask            = 0x4C000000,
 115
 116         eBlockNumberMask         = 0x00FFFFFF,
 117
 118         eFileSizeMask            = 0x00FFFF00,
 119         eFileSizeOffset          = 8,
 120         eFileGenerationMask      = 0x000000FF,
 121         eFileReservedMask        = 0x4F000000
 122
 123     };
 124
 125 public:
 126     nsDiskCacheRecord()
 127         :   mHashNumber(0), mEvictionRank(0), mDataLocation(0), mMetaLocation(0)
 128     {
 129     }
 130
 131     PRBool  ValidRecord()
 132     {
 133         if ((mDataLocation & eReservedMask) || (mMetaLocation & eReservedMask))
 134             return PR_FALSE;
 135         return PR_TRUE;
 136     }
 137
 138     // HashNumber accessors
 139     PRUint32  HashNumber() const                  { return mHashNumber; }
 140     void      SetHashNumber( PRUint32 hashNumber) { mHashNumber = hashNumber; }
 141
 142     // EvictionRank accessors
 143     PRUint32  EvictionRank() const              { return mEvictionRank; }
 144     void      SetEvictionRank( PRUint32 rank)   { mEvictionRank = rank ? rank : 1; }
 145
 146     // DataLocation accessors
 147     PRBool    DataLocationInitialized() const { return 0 != (mDataLocation & eLocationInitializedMask); }
 148     void      ClearDataLocation()       { mDataLocation = 0; }
 149
 150     PRUint32  DataFile() const
 151     {
 152         return (PRUint32)(mDataLocation & eLocationSelectorMask) >> eLocationSelectorOffset;
 153     }
 154
 155     void      SetDataBlocks( PRUint32 index, PRUint32 startBlock, PRUint32 blockCount)
 156     {
 157         // clear everything
 158         mDataLocation = 0;
 159
 160         // set file index
 161         NS_ASSERTION( index < 4,"invalid location index");
 162         NS_ASSERTION( index > 0,"invalid location index");
 163         mDataLocation |= (index << eLocationSelectorOffset) & eLocationSelectorMask;
 164
 165         // set startBlock
 166         NS_ASSERTION(startBlock == (startBlock & eBlockNumberMask), "invalid block number");
 167         mDataLocation |= startBlock & eBlockNumberMask;
 168
 169         // set blockCount
 170         NS_ASSERTION( (blockCount>=1) && (blockCount<=4),"invalid block count");
 171         --blockCount;
 172         mDataLocation |= (blockCount << eExtraBlocksOffset) & eExtraBlocksMask;
 173
 174         mDataLocation |= eLocationInitializedMask;
 175     }
 176
 177     PRUint32   DataBlockCount() const
 178     {
 179         return (PRUint32)((mDataLocation & eExtraBlocksMask) >> eExtraBlocksOffset) + 1;
 180     }
 181
 182     PRUint32   DataStartBlock() const
 183     {
 184         return (mDataLocation & eBlockNumberMask);
 185     }
 186
 187     PRUint32   DataBlockSize() const
 188     {
 189         return BLOCK_SIZE_FOR_INDEX(DataFile());
 190     }
 191
 192     PRUint32   DataFileSize() const  { return (mDataLocation & eFileSizeMask) >> eFileSizeOffset; }
 193     void       SetDataFileSize(PRUint32  size)
 194     {
 195         NS_ASSERTION((mDataLocation & eFileReservedMask) == 0, "bad location");
 196         mDataLocation &= ~eFileSizeMask;    // clear eFileSizeMask
 197         mDataLocation |= (size << eFileSizeOffset) & eFileSizeMask;
 198     }
 199
 200     PRUint8   DataFileGeneration() const
 201     {
 202         return (mDataLocation & eFileGenerationMask);
 203     }
 204
 205     void       SetDataFileGeneration( PRUint8 generation)
 206     {
 207         // clear everything, (separate file index = 0)
 208         mDataLocation = 0;
 209         mDataLocation |= generation & eFileGenerationMask;
 210         mDataLocation |= eLocationInitializedMask;
 211     }
 212
 213     // MetaLocation accessors
 214     PRBool    MetaLocationInitialized() const { return 0 != (mMetaLocation & eLocationInitializedMask); }
 215     void      ClearMetaLocation()             { mMetaLocation = 0; }
 216     PRUint32  MetaLocation() const            { return mMetaLocation; }
 217
 218     PRUint32  MetaFile() const
 219     {
 220         return (PRUint32)(mMetaLocation & eLocationSelectorMask) >> eLocationSelectorOffset;
 221     }
 222
 223     void      SetMetaBlocks( PRUint32 index, PRUint32 startBlock, PRUint32 blockCount)
 224     {
 225         // clear everything
 226         mMetaLocation = 0;
 227
 228         // set file index
 229         NS_ASSERTION( index < 4, "invalid location index");
 230         NS_ASSERTION( index > 0, "invalid location index");
 231         mMetaLocation |= (index << eLocationSelectorOffset) & eLocationSelectorMask;
 232
 233         // set startBlock
 234         NS_ASSERTION(startBlock == (startBlock & eBlockNumberMask), "invalid block number");
 235         mMetaLocation |= startBlock & eBlockNumberMask;
 236
 237         // set blockCount
 238         NS_ASSERTION( (blockCount>=1) && (blockCount<=4),"invalid block count");
 239         --blockCount;
 240         mMetaLocation |= (blockCount << eExtraBlocksOffset) & eExtraBlocksMask;
 241
 242         mMetaLocation |= eLocationInitializedMask;
 243     }
 244
 245     PRUint32   MetaBlockCount() const
 246     {
 247         return (PRUint32)((mMetaLocation & eExtraBlocksMask) >> eExtraBlocksOffset) + 1;
 248     }
 249
 250     PRUint32   MetaStartBlock() const
 251     {
 252         return (mMetaLocation & eBlockNumberMask);
 253     }
 254
 255     PRUint32   MetaBlockSize() const
 256     {
 257         return BLOCK_SIZE_FOR_INDEX(MetaFile());
 258     }
 259
 260     PRUint32   MetaFileSize() const  { return (mMetaLocation & eFileSizeMask) >> eFileSizeOffset; }
 261     void       SetMetaFileSize(PRUint32  size)
 262     {
 263         mMetaLocation &= ~eFileSizeMask;    // clear eFileSizeMask
 264         mMetaLocation |= (size << eFileSizeOffset) & eFileSizeMask;
 265     }
 266
 267     PRUint8   MetaFileGeneration() const
 268     {
 269         return (mMetaLocation & eFileGenerationMask);
 270     }
 271
 272     void       SetMetaFileGeneration( PRUint8 generation)
 273     {
 274         // clear everything, (separate file index = 0)
 275         mMetaLocation = 0;
 276         mMetaLocation |= generation & eFileGenerationMask;
 277         mMetaLocation |= eLocationInitializedMask;
 278     }
 279
 280     PRUint8   Generation() const
 281     {
 282         if ((mDataLocation & eLocationInitializedMask)  &&
 283             (DataFile() == 0))
 284             return DataFileGeneration();
 285
 286         if ((mMetaLocation & eLocationInitializedMask)  &&
 287             (MetaFile() == 0))
 288             return MetaFileGeneration();
 289
 290         return 0;  // no generation
 291     }
 292
 293 #if defined(IS_LITTLE_ENDIAN)
 294     void        Swap()
 295     {
 296         mHashNumber   = htonl(mHashNumber);
 297         mEvictionRank = htonl(mEvictionRank);
 298         mDataLocation = htonl(mDataLocation);
 299         mMetaLocation = htonl(mMetaLocation);
 300     }
 301 #endif
 302
 303 #if defined(IS_LITTLE_ENDIAN)
 304     void        Unswap()
 305     {
 306         mHashNumber   = ntohl(mHashNumber);
 307         mEvictionRank = ntohl(mEvictionRank);
 308         mDataLocation = ntohl(mDataLocation);
 309         mMetaLocation = ntohl(mMetaLocation);
 310     }
 311 #endif
 312
 313 };
 314
 315
 316 /******************************************************************************
 317  *  nsDiskCacheRecordVisitor
 318  *****************************************************************************/
 319
 320 enum {  kDeleteRecordAndContinue = -1,
 321         kStopVisitingRecords     =  0,
 322         kVisitNextRecord         =  1
 323 };
 324
 325 class nsDiskCacheRecordVisitor {
 326     public:
 327
 328     virtual PRInt32  VisitRecord( nsDiskCacheRecord *  mapRecord) = 0;
 329 };
 330
 331
 332 /******************************************************************************
 333  *  nsDiskCacheHeader
 334  *****************************************************************************/
 335
 336 struct nsDiskCacheHeader {
 337     PRUint32    mVersion;                           // cache version.
 338     PRUint32    mDataSize;                          // size of cache in units of 256bytes.
 339     PRInt32     mEntryCount;                        // number of entries stored in cache.
 340     PRUint32    mIsDirty;                           // dirty flag.
 341     PRInt32     mRecordCount;                       // Number of records
 342     PRUint32    mEvictionRank[kBuckets];            // Highest EvictionRank of the bucket
 343     PRUint32    mBucketUsage[kBuckets];             // Number of used entries in the bucket
 344
 345     nsDiskCacheHeader()
 346         : mVersion(nsDiskCache::kCurrentVersion)
 347         , mDataSize(0)
 348         , mEntryCount(0)
 349         , mIsDirty(PR_TRUE)
 350         , mRecordCount(0)
 351     {}
 352
 353     void        Swap()
 354     {
 355 #if defined(IS_LITTLE_ENDIAN)
 356         mVersion     = htonl(mVersion);
 357         mDataSize    = htonl(mDataSize);
 358         mEntryCount  = htonl(mEntryCount);
 359         mIsDirty     = htonl(mIsDirty);
 360         mRecordCount = htonl(mRecordCount);
 361
 362         for (PRUint32 i = 0; i < kBuckets ; i++) {
 363             mEvictionRank[i] = htonl(mEvictionRank[i]);
 364             mBucketUsage[i]  = htonl(mBucketUsage[i]);
 365         }
 366 #endif
 367     }
 368
 369     void        Unswap()
 370     {
 371 #if defined(IS_LITTLE_ENDIAN)
 372         mVersion     = ntohl(mVersion);
 373         mDataSize    = ntohl(mDataSize);
 374         mEntryCount  = ntohl(mEntryCount);
 375         mIsDirty     = ntohl(mIsDirty);
 376         mRecordCount = ntohl(mRecordCount);
 377
 378         for (PRUint32 i = 0; i < kBuckets ; i++) {
 379             mEvictionRank[i] = ntohl(mEvictionRank[i]);
 380             mBucketUsage[i]  = ntohl(mBucketUsage[i]);
 381         }
 382 #endif
 383     }
 384 };
 385
 386
 387 /******************************************************************************
 388  *  nsDiskCacheMap
 389  *****************************************************************************/
 390
 391 class nsDiskCacheMap {
 392 public:
 393
 394      nsDiskCacheMap() :
 395         mCacheDirectory(nsnull),
 396         mMapFD(nsnull),
 397         mRecordArray(nsnull),
 398         mBufferSize(0),
 399         mBuffer(nsnull) { }
 400
 401     ~nsDiskCacheMap() {
 402         (void) Close(PR_TRUE);
 403     }
 404
 405 /**
 406  *  File Operations
 407  *
 408  *  Open
 409  *
 410  *  Creates a new cache map file if one doesn't exist.
 411  *  Returns error if it detects change in format or cache wasn't closed.
 412  */
 413     nsresult  Open( nsILocalFile *  cacheDirectory);
 414     nsresult  Close(PRBool flush);
 415     nsresult  Trim();
 416
 417     nsresult  FlushHeader();
 418     nsresult  FlushRecords( PRBool unswap);
 419
 420 /**
 421  *  Record operations
 422  */
 423     nsresult AddRecord( nsDiskCacheRecord *  mapRecord, nsDiskCacheRecord * oldRecord);
 424     nsresult UpdateRecord( nsDiskCacheRecord *  mapRecord);
 425     nsresult FindRecord( PRUint32  hashNumber, nsDiskCacheRecord *  mapRecord);
 426     nsresult DeleteRecord( nsDiskCacheRecord *  mapRecord);
 427     nsresult VisitRecords( nsDiskCacheRecordVisitor * visitor);
 428     nsresult EvictRecords( nsDiskCacheRecordVisitor * visitor);
 429
 430 /**
 431  *  Disk Entry operations
 432  */
 433     nsresult    DeleteStorage( nsDiskCacheRecord *  record);
 434
 435     nsresult    GetFileForDiskCacheRecord( nsDiskCacheRecord * record,
 436                                            PRBool              meta,
 437                                            nsIFile **          result);
 438
 439     nsresult    GetLocalFileForDiskCacheRecord( nsDiskCacheRecord *  record,
 440                                                 PRBool               meta,
 441                                                 nsILocalFile **      result);
 442
 443     // On success, this returns the buffer owned by nsDiskCacheMap,
 444     // so it must not be deleted by the caller.
 445     nsDiskCacheEntry * ReadDiskCacheEntry( nsDiskCacheRecord *  record);
 446
 447     nsresult    WriteDiskCacheEntry( nsDiskCacheBinding *  binding);
 448
 449     nsresult    ReadDataCacheBlocks(nsDiskCacheBinding * binding, char * buffer, PRUint32 size);
 450     nsresult    WriteDataCacheBlocks(nsDiskCacheBinding * binding, char * buffer, PRUint32 size);
 451     nsresult    DeleteStorage( nsDiskCacheRecord * record, PRBool metaData);
 452
 453     /**
 454      *  Statistical Operations
 455      */
 456     void     IncrementTotalSize( PRUint32  delta)
 457              {
 458                 mHeader.mDataSize += delta;
 459                 mHeader.mIsDirty   = PR_TRUE;
 460              }
 461
 462     void     DecrementTotalSize( PRUint32  delta)
 463              {
 464                 NS_ASSERTION(mHeader.mDataSize >= delta, "disk cache size negative?");
 465                 mHeader.mDataSize  = mHeader.mDataSize > delta ? mHeader.mDataSize - delta : 0;
 466                 mHeader.mIsDirty   = PR_TRUE;
 467              }
 468
 469     inline void IncrementTotalSize( PRUint32  blocks, PRUint32 blockSize)
 470              {
 471                 // Round up to nearest K
 472                 IncrementTotalSize(((blocks*blockSize) + 0x03FF) >> 10);
 473              }
 474
 475     inline void DecrementTotalSize( PRUint32  blocks, PRUint32 blockSize)
 476              {
 477                 // Round up to nearest K
 478                 DecrementTotalSize(((blocks*blockSize) + 0x03FF) >> 10);
 479              }
 480
 481     PRUint32 TotalSize()   { return mHeader.mDataSize; }
 482
 483     PRInt32  EntryCount()  { return mHeader.mEntryCount; }
 484
 485
 486 private:
 487
 488     /**
 489      *  Private methods
 490      */
 491     nsresult    OpenBlockFiles();
 492     nsresult    CloseBlockFiles(PRBool flush);
 493     PRBool      CacheFilesExist();
 494
 495     PRUint32    CalculateFileIndex(PRUint32 size);
 496
 497     nsresult    GetBlockFileForIndex( PRUint32 index, nsILocalFile ** result);
 498     PRUint32    GetBlockSizeForIndex( PRUint32 index) const {
 499         return BLOCK_SIZE_FOR_INDEX(index);
 500     }
 501
 502     // returns the bucket number
 503     PRUint32 GetBucketIndex( PRUint32 hashNumber) const {
 504         return (hashNumber & (kBuckets - 1));
 505     }
 506
 507     // Gets the size of the bucket (in number of records)
 508     PRUint32 GetRecordsPerBucket() const {
 509         return mHeader.mRecordCount / kBuckets;
 510     }
 511
 512     // Gets the first record in the bucket
 513     nsDiskCacheRecord *GetFirstRecordInBucket(PRUint32 bucket) const {
 514         return mRecordArray + bucket * GetRecordsPerBucket();
 515     }
 516
 517     PRUint32 GetBucketRank(PRUint32 bucketIndex, PRUint32 targetRank);
 518
 519     PRInt32  VisitEachRecord(PRUint32                    bucketIndex,
 520                              nsDiskCacheRecordVisitor *  visitor,
 521                              PRUint32                    evictionRank);
 522
 523     nsresult GrowRecords();
 524     nsresult ShrinkRecords();
 525
 526     nsresult EnsureBuffer(PRUint32 bufSize);
 527
 528     // The returned structure will point to the buffer owned by nsDiskCacheMap,
 529     // so it must not be deleted by the caller.
 530     nsDiskCacheEntry *  CreateDiskCacheEntry(nsDiskCacheBinding *  binding,
 531                                              PRUint32 * size);
 532
 533 /**
 534  *  data members
 535  */
 536 private:
 537     nsCOMPtr<nsILocalFile>  mCacheDirectory;
 538     PRFileDesc *            mMapFD;
 539     nsDiskCacheRecord *     mRecordArray;
 540     nsDiskCacheBlockFile    mBlockFile[3];
 541     PRUint32                mBufferSize;
 542     char *                  mBuffer;
 543     nsDiskCacheHeader       mHeader;
 544 };
 545
 546 #endif // _nsDiskCacheMap_h_