Line data Source code
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 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #ifndef _nsDiskCacheMap_h_
8 : #define _nsDiskCacheMap_h_
9 :
10 : #include "mozilla/MemoryReporting.h"
11 : #include <limits.h>
12 :
13 : #include "prnetdb.h"
14 : #include "nsDebug.h"
15 : #include "nsError.h"
16 : #include "nsIFile.h"
17 : #include "nsITimer.h"
18 :
19 : #include "nsDiskCache.h"
20 : #include "nsDiskCacheBlockFile.h"
21 :
22 :
23 : class nsDiskCacheBinding;
24 : struct nsDiskCacheEntry;
25 :
26 : /******************************************************************************
27 : * nsDiskCacheRecord
28 : *
29 : * Cache Location Format
30 : *
31 : * 1000 0000 0000 0000 0000 0000 0000 0000 : initialized bit
32 : *
33 : * 0011 0000 0000 0000 0000 0000 0000 0000 : File Selector (0 = separate file)
34 : * 0000 0011 0000 0000 0000 0000 0000 0000 : number of extra contiguous blocks 1-4
35 : * 0100 1100 0000 0000 0000 0000 0000 0000 : reserved bits
36 : * 0000 0000 1111 1111 1111 1111 1111 1111 : block# 0-16777216 (2^24)
37 : *
38 : * 0000 0000 1111 1111 1111 1111 0000 0000 : eFileSizeMask (size of file in k: see note)
39 : * 0000 0000 0000 0000 0000 0000 1111 1111 : eFileGenerationMask
40 : *
41 : * File Selector:
42 : * 0 = separate file on disk
43 : * 1 = 256 byte block file
44 : * 2 = 1k block file
45 : * 3 = 4k block file
46 : *
47 : * eFileSizeMask note: Files larger than 65535 KiB have this limit stored in
48 : * the location. The file itself must be examined to
49 : * determine its actual size if necessary.
50 : *
51 : *****************************************************************************/
52 :
53 : /*
54 : We have 3 block files with roughly the same max size (32MB)
55 : 1 - block size 256B, number of blocks 131072
56 : 2 - block size 1kB, number of blocks 32768
57 : 3 - block size 4kB, number of blocks 8192
58 : */
59 : #define kNumBlockFiles 3
60 : #define SIZE_SHIFT(idx) (2 * ((idx) - 1))
61 : #define BLOCK_SIZE_FOR_INDEX(idx) ((idx) ? (256 << SIZE_SHIFT(idx)) : 0)
62 : #define BITMAP_SIZE_FOR_INDEX(idx) ((idx) ? (131072 >> SIZE_SHIFT(idx)) : 0)
63 :
64 : // Min and max values for the number of records in the DiskCachemap
65 : #define kMinRecordCount 512
66 :
67 : #define kSeparateFile 0
68 : #define kBuckets (1 << 5) // must be a power of 2!
69 :
70 : // Maximum size in K which can be stored in the location (see eFileSizeMask).
71 : // Both data and metadata can be larger, but only up to kMaxDataSizeK can be
72 : // counted into total cache size. I.e. if there are entries where either data or
73 : // metadata is larger than kMaxDataSizeK, the total cache size will be
74 : // inaccurate (smaller) than the actual cache size. The alternative is to stat
75 : // the files to find the real size, which was decided against for performance
76 : // reasons. See bug #651100 comment #21.
77 : #define kMaxDataSizeK 0xFFFF
78 :
79 : // preallocate up to 1MB of separate cache file
80 : #define kPreallocateLimit 1 * 1024 * 1024
81 :
82 : // The minimum amount of milliseconds to wait before re-attempting to
83 : // revalidate the cache.
84 : #define kRevalidateCacheTimeout 3000
85 : #define kRevalidateCacheTimeoutTolerance 10
86 : #define kRevalidateCacheErrorTimeout 1000
87 :
88 : class nsDiskCacheRecord {
89 :
90 : private:
91 : uint32_t mHashNumber;
92 : uint32_t mEvictionRank;
93 : uint32_t mDataLocation;
94 : uint32_t mMetaLocation;
95 :
96 : enum {
97 : eLocationInitializedMask = 0x80000000,
98 :
99 : eLocationSelectorMask = 0x30000000,
100 : eLocationSelectorOffset = 28,
101 :
102 : eExtraBlocksMask = 0x03000000,
103 : eExtraBlocksOffset = 24,
104 :
105 : eReservedMask = 0x4C000000,
106 :
107 : eBlockNumberMask = 0x00FFFFFF,
108 :
109 : eFileSizeMask = 0x00FFFF00,
110 : eFileSizeOffset = 8,
111 : eFileGenerationMask = 0x000000FF,
112 : eFileReservedMask = 0x4F000000
113 :
114 : };
115 :
116 : public:
117 0 : nsDiskCacheRecord()
118 0 : : mHashNumber(0), mEvictionRank(0), mDataLocation(0), mMetaLocation(0)
119 : {
120 0 : }
121 :
122 0 : bool ValidRecord()
123 : {
124 0 : if ((mDataLocation & eReservedMask) || (mMetaLocation & eReservedMask))
125 0 : return false;
126 0 : return true;
127 : }
128 :
129 : // HashNumber accessors
130 0 : uint32_t HashNumber() const { return mHashNumber; }
131 0 : void SetHashNumber( uint32_t hashNumber) { mHashNumber = hashNumber; }
132 :
133 : // EvictionRank accessors
134 0 : uint32_t EvictionRank() const { return mEvictionRank; }
135 0 : void SetEvictionRank( uint32_t rank) { mEvictionRank = rank ? rank : 1; }
136 :
137 : // DataLocation accessors
138 0 : bool DataLocationInitialized() const { return 0 != (mDataLocation & eLocationInitializedMask); }
139 0 : void ClearDataLocation() { mDataLocation = 0; }
140 :
141 0 : uint32_t DataFile() const
142 : {
143 0 : return (uint32_t)(mDataLocation & eLocationSelectorMask) >> eLocationSelectorOffset;
144 : }
145 :
146 0 : void SetDataBlocks( uint32_t index, uint32_t startBlock, uint32_t blockCount)
147 : {
148 : // clear everything
149 0 : mDataLocation = 0;
150 :
151 : // set file index
152 0 : NS_ASSERTION( index < (kNumBlockFiles + 1), "invalid location index");
153 0 : NS_ASSERTION( index > 0,"invalid location index");
154 0 : mDataLocation |= (index << eLocationSelectorOffset) & eLocationSelectorMask;
155 :
156 : // set startBlock
157 0 : NS_ASSERTION(startBlock == (startBlock & eBlockNumberMask), "invalid block number");
158 0 : mDataLocation |= startBlock & eBlockNumberMask;
159 :
160 : // set blockCount
161 0 : NS_ASSERTION( (blockCount>=1) && (blockCount<=4),"invalid block count");
162 0 : --blockCount;
163 0 : mDataLocation |= (blockCount << eExtraBlocksOffset) & eExtraBlocksMask;
164 :
165 0 : mDataLocation |= eLocationInitializedMask;
166 0 : }
167 :
168 0 : uint32_t DataBlockCount() const
169 : {
170 0 : return (uint32_t)((mDataLocation & eExtraBlocksMask) >> eExtraBlocksOffset) + 1;
171 : }
172 :
173 0 : uint32_t DataStartBlock() const
174 : {
175 0 : return (mDataLocation & eBlockNumberMask);
176 : }
177 :
178 : uint32_t DataBlockSize() const
179 : {
180 : return BLOCK_SIZE_FOR_INDEX(DataFile());
181 : }
182 :
183 0 : uint32_t DataFileSize() const { return (mDataLocation & eFileSizeMask) >> eFileSizeOffset; }
184 0 : void SetDataFileSize(uint32_t size)
185 : {
186 0 : NS_ASSERTION((mDataLocation & eFileReservedMask) == 0, "bad location");
187 0 : mDataLocation &= ~eFileSizeMask; // clear eFileSizeMask
188 0 : mDataLocation |= (size << eFileSizeOffset) & eFileSizeMask;
189 0 : }
190 :
191 0 : uint8_t DataFileGeneration() const
192 : {
193 0 : return (mDataLocation & eFileGenerationMask);
194 : }
195 :
196 0 : void SetDataFileGeneration( uint8_t generation)
197 : {
198 : // clear everything, (separate file index = 0)
199 0 : mDataLocation = 0;
200 0 : mDataLocation |= generation & eFileGenerationMask;
201 0 : mDataLocation |= eLocationInitializedMask;
202 0 : }
203 :
204 : // MetaLocation accessors
205 0 : bool MetaLocationInitialized() const { return 0 != (mMetaLocation & eLocationInitializedMask); }
206 0 : void ClearMetaLocation() { mMetaLocation = 0; }
207 0 : uint32_t MetaLocation() const { return mMetaLocation; }
208 :
209 0 : uint32_t MetaFile() const
210 : {
211 0 : return (uint32_t)(mMetaLocation & eLocationSelectorMask) >> eLocationSelectorOffset;
212 : }
213 :
214 0 : void SetMetaBlocks( uint32_t index, uint32_t startBlock, uint32_t blockCount)
215 : {
216 : // clear everything
217 0 : mMetaLocation = 0;
218 :
219 : // set file index
220 0 : NS_ASSERTION( index < (kNumBlockFiles + 1), "invalid location index");
221 0 : NS_ASSERTION( index > 0, "invalid location index");
222 0 : mMetaLocation |= (index << eLocationSelectorOffset) & eLocationSelectorMask;
223 :
224 : // set startBlock
225 0 : NS_ASSERTION(startBlock == (startBlock & eBlockNumberMask), "invalid block number");
226 0 : mMetaLocation |= startBlock & eBlockNumberMask;
227 :
228 : // set blockCount
229 0 : NS_ASSERTION( (blockCount>=1) && (blockCount<=4),"invalid block count");
230 0 : --blockCount;
231 0 : mMetaLocation |= (blockCount << eExtraBlocksOffset) & eExtraBlocksMask;
232 :
233 0 : mMetaLocation |= eLocationInitializedMask;
234 0 : }
235 :
236 0 : uint32_t MetaBlockCount() const
237 : {
238 0 : return (uint32_t)((mMetaLocation & eExtraBlocksMask) >> eExtraBlocksOffset) + 1;
239 : }
240 :
241 0 : uint32_t MetaStartBlock() const
242 : {
243 0 : return (mMetaLocation & eBlockNumberMask);
244 : }
245 :
246 : uint32_t MetaBlockSize() const
247 : {
248 : return BLOCK_SIZE_FOR_INDEX(MetaFile());
249 : }
250 :
251 0 : uint32_t MetaFileSize() const { return (mMetaLocation & eFileSizeMask) >> eFileSizeOffset; }
252 0 : void SetMetaFileSize(uint32_t size)
253 : {
254 0 : mMetaLocation &= ~eFileSizeMask; // clear eFileSizeMask
255 0 : mMetaLocation |= (size << eFileSizeOffset) & eFileSizeMask;
256 0 : }
257 :
258 0 : uint8_t MetaFileGeneration() const
259 : {
260 0 : return (mMetaLocation & eFileGenerationMask);
261 : }
262 :
263 0 : void SetMetaFileGeneration( uint8_t generation)
264 : {
265 : // clear everything, (separate file index = 0)
266 0 : mMetaLocation = 0;
267 0 : mMetaLocation |= generation & eFileGenerationMask;
268 0 : mMetaLocation |= eLocationInitializedMask;
269 0 : }
270 :
271 0 : uint8_t Generation() const
272 : {
273 0 : if ((mDataLocation & eLocationInitializedMask) &&
274 0 : (DataFile() == 0))
275 0 : return DataFileGeneration();
276 :
277 0 : if ((mMetaLocation & eLocationInitializedMask) &&
278 0 : (MetaFile() == 0))
279 0 : return MetaFileGeneration();
280 :
281 0 : return 0; // no generation
282 : }
283 :
284 : #if defined(IS_LITTLE_ENDIAN)
285 0 : void Swap()
286 : {
287 0 : mHashNumber = htonl(mHashNumber);
288 0 : mEvictionRank = htonl(mEvictionRank);
289 0 : mDataLocation = htonl(mDataLocation);
290 0 : mMetaLocation = htonl(mMetaLocation);
291 0 : }
292 : #endif
293 :
294 : #if defined(IS_LITTLE_ENDIAN)
295 0 : void Unswap()
296 : {
297 0 : mHashNumber = ntohl(mHashNumber);
298 0 : mEvictionRank = ntohl(mEvictionRank);
299 0 : mDataLocation = ntohl(mDataLocation);
300 0 : mMetaLocation = ntohl(mMetaLocation);
301 0 : }
302 : #endif
303 :
304 : };
305 :
306 :
307 : /******************************************************************************
308 : * nsDiskCacheRecordVisitor
309 : *****************************************************************************/
310 :
311 : enum { kDeleteRecordAndContinue = -1,
312 : kStopVisitingRecords = 0,
313 : kVisitNextRecord = 1
314 : };
315 :
316 0 : class nsDiskCacheRecordVisitor {
317 : public:
318 :
319 : virtual int32_t VisitRecord( nsDiskCacheRecord * mapRecord) = 0;
320 : };
321 :
322 :
323 : /******************************************************************************
324 : * nsDiskCacheHeader
325 : *****************************************************************************/
326 :
327 : struct nsDiskCacheHeader {
328 : uint32_t mVersion; // cache version.
329 : uint32_t mDataSize; // size of cache in units of 1024bytes.
330 : int32_t mEntryCount; // number of entries stored in cache.
331 : uint32_t mIsDirty; // dirty flag.
332 : int32_t mRecordCount; // Number of records
333 : uint32_t mEvictionRank[kBuckets]; // Highest EvictionRank of the bucket
334 : uint32_t mBucketUsage[kBuckets]; // Number of used entries in the bucket
335 :
336 0 : nsDiskCacheHeader()
337 0 : : mVersion(nsDiskCache::kCurrentVersion)
338 : , mDataSize(0)
339 : , mEntryCount(0)
340 : , mIsDirty(true)
341 0 : , mRecordCount(0)
342 0 : {}
343 :
344 0 : void Swap()
345 : {
346 : #if defined(IS_LITTLE_ENDIAN)
347 0 : mVersion = htonl(mVersion);
348 0 : mDataSize = htonl(mDataSize);
349 0 : mEntryCount = htonl(mEntryCount);
350 0 : mIsDirty = htonl(mIsDirty);
351 0 : mRecordCount = htonl(mRecordCount);
352 :
353 0 : for (uint32_t i = 0; i < kBuckets ; i++) {
354 0 : mEvictionRank[i] = htonl(mEvictionRank[i]);
355 0 : mBucketUsage[i] = htonl(mBucketUsage[i]);
356 : }
357 : #endif
358 0 : }
359 :
360 0 : void Unswap()
361 : {
362 : #if defined(IS_LITTLE_ENDIAN)
363 0 : mVersion = ntohl(mVersion);
364 0 : mDataSize = ntohl(mDataSize);
365 0 : mEntryCount = ntohl(mEntryCount);
366 0 : mIsDirty = ntohl(mIsDirty);
367 0 : mRecordCount = ntohl(mRecordCount);
368 :
369 0 : for (uint32_t i = 0; i < kBuckets ; i++) {
370 0 : mEvictionRank[i] = ntohl(mEvictionRank[i]);
371 0 : mBucketUsage[i] = ntohl(mBucketUsage[i]);
372 : }
373 : #endif
374 0 : }
375 : };
376 :
377 :
378 : /******************************************************************************
379 : * nsDiskCacheMap
380 : *****************************************************************************/
381 :
382 : class nsDiskCacheMap {
383 : public:
384 :
385 0 : nsDiskCacheMap() :
386 : mCacheDirectory(nullptr),
387 : mMapFD(nullptr),
388 : mCleanFD(nullptr),
389 : mRecordArray(nullptr),
390 : mBufferSize(0),
391 : mBuffer(nullptr),
392 : mMaxRecordCount(16384), // this default value won't matter
393 : mIsDirtyCacheFlushed(false),
394 0 : mLastInvalidateTime(0)
395 0 : { }
396 :
397 0 : ~nsDiskCacheMap()
398 0 : {
399 0 : (void) Close(true);
400 0 : }
401 :
402 : /**
403 : * File Operations
404 : *
405 : * Open
406 : *
407 : * Creates a new cache map file if one doesn't exist.
408 : * Returns error if it detects change in format or cache wasn't closed.
409 : */
410 : nsresult Open( nsIFile * cacheDirectory,
411 : nsDiskCache::CorruptCacheInfo * corruptInfo);
412 : nsresult Close(bool flush);
413 : nsresult Trim();
414 :
415 : nsresult FlushHeader();
416 : nsresult FlushRecords( bool unswap);
417 :
418 : void NotifyCapacityChange(uint32_t capacity);
419 :
420 : /**
421 : * Record operations
422 : */
423 : nsresult AddRecord( nsDiskCacheRecord * mapRecord, nsDiskCacheRecord * oldRecord);
424 : nsresult UpdateRecord( nsDiskCacheRecord * mapRecord);
425 : nsresult FindRecord( uint32_t 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 : bool meta,
437 : bool createPath,
438 : nsIFile ** result);
439 :
440 : nsresult GetLocalFileForDiskCacheRecord( nsDiskCacheRecord * record,
441 : bool meta,
442 : bool createPath,
443 : nsIFile ** result);
444 :
445 : // On success, this returns the buffer owned by nsDiskCacheMap,
446 : // so it must not be deleted by the caller.
447 : nsDiskCacheEntry * ReadDiskCacheEntry( nsDiskCacheRecord * record);
448 :
449 : nsresult WriteDiskCacheEntry( nsDiskCacheBinding * binding);
450 :
451 : nsresult ReadDataCacheBlocks(nsDiskCacheBinding * binding, char * buffer, uint32_t size);
452 : nsresult WriteDataCacheBlocks(nsDiskCacheBinding * binding, char * buffer, uint32_t size);
453 : nsresult DeleteStorage( nsDiskCacheRecord * record, bool metaData);
454 :
455 : /**
456 : * Statistical Operations
457 : */
458 0 : void IncrementTotalSize( uint32_t delta)
459 : {
460 0 : mHeader.mDataSize += delta;
461 0 : mHeader.mIsDirty = true;
462 0 : }
463 :
464 0 : void DecrementTotalSize( uint32_t delta)
465 : {
466 0 : NS_ASSERTION(mHeader.mDataSize >= delta, "disk cache size negative?");
467 0 : mHeader.mDataSize = mHeader.mDataSize > delta ? mHeader.mDataSize - delta : 0;
468 0 : mHeader.mIsDirty = true;
469 0 : }
470 :
471 0 : inline void IncrementTotalSize( uint32_t blocks, uint32_t blockSize)
472 : {
473 : // Round up to nearest K
474 0 : IncrementTotalSize(((blocks*blockSize) + 0x03FF) >> 10);
475 0 : }
476 :
477 0 : inline void DecrementTotalSize( uint32_t blocks, uint32_t blockSize)
478 : {
479 : // Round up to nearest K
480 0 : DecrementTotalSize(((blocks*blockSize) + 0x03FF) >> 10);
481 0 : }
482 :
483 0 : uint32_t TotalSize() { return mHeader.mDataSize; }
484 :
485 0 : int32_t EntryCount() { return mHeader.mEntryCount; }
486 :
487 : size_t SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf);
488 :
489 :
490 : private:
491 :
492 : /**
493 : * Private methods
494 : */
495 : nsresult OpenBlockFiles(nsDiskCache::CorruptCacheInfo * corruptInfo);
496 : nsresult CloseBlockFiles(bool flush);
497 : bool CacheFilesExist();
498 :
499 : nsresult CreateCacheSubDirectories();
500 :
501 : uint32_t CalculateFileIndex(uint32_t size);
502 :
503 : nsresult GetBlockFileForIndex( uint32_t index, nsIFile ** result);
504 0 : uint32_t GetBlockSizeForIndex( uint32_t index) const {
505 0 : return BLOCK_SIZE_FOR_INDEX(index);
506 : }
507 0 : uint32_t GetBitMapSizeForIndex( uint32_t index) const {
508 0 : return BITMAP_SIZE_FOR_INDEX(index);
509 : }
510 :
511 : // returns the bucket number
512 0 : uint32_t GetBucketIndex( uint32_t hashNumber) const {
513 0 : return (hashNumber & (kBuckets - 1));
514 : }
515 :
516 : // Gets the size of the bucket (in number of records)
517 0 : uint32_t GetRecordsPerBucket() const {
518 0 : return mHeader.mRecordCount / kBuckets;
519 : }
520 :
521 : // Gets the first record in the bucket
522 0 : nsDiskCacheRecord *GetFirstRecordInBucket(uint32_t bucket) const {
523 0 : return mRecordArray + bucket * GetRecordsPerBucket();
524 : }
525 :
526 : uint32_t GetBucketRank(uint32_t bucketIndex, uint32_t targetRank);
527 :
528 : int32_t VisitEachRecord(uint32_t bucketIndex,
529 : nsDiskCacheRecordVisitor * visitor,
530 : uint32_t evictionRank);
531 :
532 : nsresult GrowRecords();
533 : nsresult ShrinkRecords();
534 :
535 : nsresult EnsureBuffer(uint32_t bufSize);
536 :
537 : // The returned structure will point to the buffer owned by nsDiskCacheMap,
538 : // so it must not be deleted by the caller.
539 : nsDiskCacheEntry * CreateDiskCacheEntry(nsDiskCacheBinding * binding,
540 : uint32_t * size);
541 :
542 : // Initializes the _CACHE_CLEAN_ related functionality
543 : nsresult InitCacheClean(nsIFile * cacheDirectory,
544 : nsDiskCache::CorruptCacheInfo * corruptInfo);
545 : // Writes out a value of '0' or '1' in the _CACHE_CLEAN_ file
546 : nsresult WriteCacheClean(bool clean);
547 : // Resets the timout for revalidating the cache
548 : nsresult ResetCacheTimer(int32_t timeout = kRevalidateCacheTimeout);
549 : // Invalidates the cache, calls WriteCacheClean and ResetCacheTimer
550 : nsresult InvalidateCache();
551 : // Determines if the cache is in a safe state
552 : bool IsCacheInSafeState();
553 : // Revalidates the cache by writting out the header, records, and finally
554 : // by calling WriteCacheClean(true).
555 : nsresult RevalidateCache();
556 : // Timer which revalidates the cache
557 : static void RevalidateTimerCallback(nsITimer *aTimer, void *arg);
558 :
559 : /**
560 : * data members
561 : */
562 : private:
563 : nsCOMPtr<nsITimer> mCleanCacheTimer;
564 : nsCOMPtr<nsIFile> mCacheDirectory;
565 : PRFileDesc * mMapFD;
566 : PRFileDesc * mCleanFD;
567 : nsDiskCacheRecord * mRecordArray;
568 : nsDiskCacheBlockFile mBlockFile[kNumBlockFiles];
569 : uint32_t mBufferSize;
570 : char * mBuffer;
571 : nsDiskCacheHeader mHeader;
572 : int32_t mMaxRecordCount;
573 : bool mIsDirtyCacheFlushed;
574 : PRIntervalTime mLastInvalidateTime;
575 : };
576 :
577 : #endif // _nsDiskCacheMap_h_
|
