/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

/* vim:set ts=4 sw=4 sts=4 cin et: */

/* 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/. */

#ifndef _nsDiskCacheMap_h_

#define _nsDiskCacheMap_h_

#include "mozilla/MemoryReporting.h"

#include <limits.h>

#include "prnetdb.h"

#include "nsDebug.h"

#include "nsError.h"

#include "nsIFile.h"

#include "nsITimer.h"

#include "nsDiskCache.h"

#include "nsDiskCacheBlockFile.h"

class nsDiskCacheBinding;

struct nsDiskCacheEntry;

/******************************************************************************

 *  nsDiskCacheRecord

 *

 *   Cache Location Format

 *

 *    1000 0000 0000 0000 0000 0000 0000 0000 : initialized bit

 *

 *    0011 0000 0000 0000 0000 0000 0000 0000 : File Selector (0 = separate file)

 *    0000 0011 0000 0000 0000 0000 0000 0000 : number of extra contiguous blocks 1-4

 *    0100 1100 0000 0000 0000 0000 0000 0000 : reserved bits

 *    0000 0000 1111 1111 1111 1111 1111 1111 : block#  0-16777216 (2^24)

 *

 *    0000 0000 1111 1111 1111 1111 0000 0000 : eFileSizeMask (size of file in k: see note)

 *    0000 0000 0000 0000 0000 0000 1111 1111 : eFileGenerationMask

 *

 *  File Selector:

 *      0 = separate file on disk

 *      1 = 256 byte block file

 *      2 = 1k block file

 *      3 = 4k block file

 *

 *  eFileSizeMask note:  Files larger than 65535 KiB have this limit stored in

 *                       the location.  The file itself must be examined to

 *                       determine its actual size if necessary.

 *

 *****************************************************************************/

/*

  We have 3 block files with roughly the same max size (32MB)

    1 - block size 256B, number of blocks 131072

    2 - block size  1kB, number of blocks  32768

    3 - block size  4kB, number of blocks   8192

*/

#define kNumBlockFiles             3

#define SIZE_SHIFT(idx)            (2 * ((idx) - 1))

#define BLOCK_SIZE_FOR_INDEX(idx)  ((idx) ? (256    << SIZE_SHIFT(idx)) : 0)

#define BITMAP_SIZE_FOR_INDEX(idx) ((idx) ? (131072 >> SIZE_SHIFT(idx)) : 0)

// Min and max values for the number of records in the DiskCachemap

#define kMinRecordCount    512

#define kSeparateFile      0

#define kBuckets           (1 << 5)    // must be a power of 2!

// Maximum size in K which can be stored in the location (see eFileSizeMask).

// Both data and metadata can be larger, but only up to kMaxDataSizeK can be

// counted into total cache size. I.e. if there are entries where either data or

// metadata is larger than kMaxDataSizeK, the total cache size will be

// inaccurate (smaller) than the actual cache size. The alternative is to stat

// the files to find the real size, which was decided against for performance

// reasons. See bug #651100 comment #21.

#define kMaxDataSizeK      0xFFFF

// preallocate up to 1MB of separate cache file

#define kPreallocateLimit  1 * 1024 * 1024

// The minimum amount of milliseconds to wait before re-attempting to

// revalidate the cache.

#define kRevalidateCacheTimeout 3000

#define kRevalidateCacheTimeoutTolerance 10

#define kRevalidateCacheErrorTimeout 1000

class nsDiskCacheRecord {

private:

    uint32_t    mHashNumber;

    uint32_t    mEvictionRank;

    uint32_t    mDataLocation;

    uint32_t    mMetaLocation;

    enum {

        eLocationInitializedMask = 0x80000000,

        eLocationSelectorMask    = 0x30000000,

        eLocationSelectorOffset  = 28,

        eExtraBlocksMask         = 0x03000000,

        eExtraBlocksOffset       = 24,

        eReservedMask            = 0x4C000000,

        eBlockNumberMask         = 0x00FFFFFF,

        eFileSizeMask            = 0x00FFFF00,

        eFileSizeOffset          = 8,

        eFileGenerationMask      = 0x000000FF,

        eFileReservedMask        = 0x4F000000

    };

public:

    nsDiskCacheRecord()

        :   mHashNumber(0), mEvictionRank(0), mDataLocation(0), mMetaLocation(0)

    {

    }

    bool    ValidRecord()

    {

        if ((mDataLocation & eReservedMask) || (mMetaLocation & eReservedMask))

            return false;

        return true;

    }

    // HashNumber accessors

    uint32_t  HashNumber() const                  { return mHashNumber; }

    void      SetHashNumber( uint32_t hashNumber) { mHashNumber = hashNumber; }

    // EvictionRank accessors

    uint32_t  EvictionRank() const              { return mEvictionRank; }

    void      SetEvictionRank( uint32_t rank)   { mEvictionRank = rank ? rank : 1; }

    // DataLocation accessors

    bool      DataLocationInitialized() const { return 0 != (mDataLocation & eLocationInitializedMask); }

    void      ClearDataLocation()       { mDataLocation = 0; }

    uint32_t  DataFile() const

    {

        return (uint32_t)(mDataLocation & eLocationSelectorMask) >> eLocationSelectorOffset;

    }

    void      SetDataBlocks( uint32_t index, uint32_t startBlock, uint32_t blockCount)

    {

        // clear everything

        mDataLocation = 0;

        // set file index

        NS_ASSERTION( index < (kNumBlockFiles + 1), "invalid location index");

        NS_ASSERTION( index > 0,"invalid location index");

        mDataLocation |= (index << eLocationSelectorOffset) & eLocationSelectorMask;

        // set startBlock

        NS_ASSERTION(startBlock == (startBlock & eBlockNumberMask), "invalid block number");

        mDataLocation |= startBlock & eBlockNumberMask;

        // set blockCount

        NS_ASSERTION( (blockCount>=1) && (blockCount<=4),"invalid block count");

        --blockCount;

        mDataLocation |= (blockCount << eExtraBlocksOffset) & eExtraBlocksMask;

        mDataLocation |= eLocationInitializedMask;

    }

    uint32_t   DataBlockCount() const

    {

        return (uint32_t)((mDataLocation & eExtraBlocksMask) >> eExtraBlocksOffset) + 1;

    }

    uint32_t   DataStartBlock() const

    {

        return (mDataLocation & eBlockNumberMask);

    }

    uint32_t   DataBlockSize() const

    {

        return BLOCK_SIZE_FOR_INDEX(DataFile());

    }

    uint32_t   DataFileSize() const  { return (mDataLocation & eFileSizeMask) >> eFileSizeOffset; }

    void       SetDataFileSize(uint32_t  size)

    {

        NS_ASSERTION((mDataLocation & eFileReservedMask) == 0, "bad location");

        mDataLocation &= ~eFileSizeMask;    // clear eFileSizeMask

        mDataLocation |= (size << eFileSizeOffset) & eFileSizeMask;

    }

    uint8_t   DataFileGeneration() const

    {

        return (mDataLocation & eFileGenerationMask);

    }

    void       SetDataFileGeneration( uint8_t generation)

    {

        // clear everything, (separate file index = 0)

        mDataLocation = 0;

        mDataLocation |= generation & eFileGenerationMask;

        mDataLocation |= eLocationInitializedMask;

    }

    // MetaLocation accessors

    bool      MetaLocationInitialized() const { return 0 != (mMetaLocation & eLocationInitializedMask); }

    void      ClearMetaLocation()             { mMetaLocation = 0; }

    uint32_t  MetaLocation() const            { return mMetaLocation; }

    uint32_t  MetaFile() const

    {

        return (uint32_t)(mMetaLocation & eLocationSelectorMask) >> eLocationSelectorOffset;

    }

    void      SetMetaBlocks( uint32_t index, uint32_t startBlock, uint32_t blockCount)

    {

        // clear everything

        mMetaLocation = 0;

        // set file index

        NS_ASSERTION( index < (kNumBlockFiles + 1), "invalid location index");

        NS_ASSERTION( index > 0, "invalid location index");

        mMetaLocation |= (index << eLocationSelectorOffset) & eLocationSelectorMask;

        // set startBlock

        NS_ASSERTION(startBlock == (startBlock & eBlockNumberMask), "invalid block number");

        mMetaLocation |= startBlock & eBlockNumberMask;

        // set blockCount

        NS_ASSERTION( (blockCount>=1) && (blockCount<=4),"invalid block count");

        --blockCount;

        mMetaLocation |= (blockCount << eExtraBlocksOffset) & eExtraBlocksMask;

        mMetaLocation |= eLocationInitializedMask;

    }

    uint32_t   MetaBlockCount() const

    {

        return (uint32_t)((mMetaLocation & eExtraBlocksMask) >> eExtraBlocksOffset) + 1;

    }

    uint32_t   MetaStartBlock() const

    {

        return (mMetaLocation & eBlockNumberMask);

    }

    uint32_t   MetaBlockSize() const

    {

        return BLOCK_SIZE_FOR_INDEX(MetaFile());

    }

    uint32_t   MetaFileSize() const  { return (mMetaLocation & eFileSizeMask) >> eFileSizeOffset; }

    void       SetMetaFileSize(uint32_t  size)

    {

        mMetaLocation &= ~eFileSizeMask;    // clear eFileSizeMask

        mMetaLocation |= (size << eFileSizeOffset) & eFileSizeMask;

    }

    uint8_t   MetaFileGeneration() const

    {

        return (mMetaLocation & eFileGenerationMask);

    }

    void       SetMetaFileGeneration( uint8_t generation)

    {

        // clear everything, (separate file index = 0)

        mMetaLocation = 0;

        mMetaLocation |= generation & eFileGenerationMask;

        mMetaLocation |= eLocationInitializedMask;

    }

    uint8_t   Generation() const

    {

        if ((mDataLocation & eLocationInitializedMask)  &&

            (DataFile() == 0))

            return DataFileGeneration();

        if ((mMetaLocation & eLocationInitializedMask)  &&

            (MetaFile() == 0))

            return MetaFileGeneration();

        return 0;  // no generation

    }

#if defined(IS_LITTLE_ENDIAN)

    void        Swap()

    {

        mHashNumber   = htonl(mHashNumber);

        mEvictionRank = htonl(mEvictionRank);

        mDataLocation = htonl(mDataLocation);

        mMetaLocation = htonl(mMetaLocation);

    }

#endif

#if defined(IS_LITTLE_ENDIAN)

    void        Unswap()

    {

        mHashNumber   = ntohl(mHashNumber);

        mEvictionRank = ntohl(mEvictionRank);

        mDataLocation = ntohl(mDataLocation);

        mMetaLocation = ntohl(mMetaLocation);

    }

#endif

};

/******************************************************************************

 *  nsDiskCacheRecordVisitor

 *****************************************************************************/

enum {  kDeleteRecordAndContinue = -1,

        kStopVisitingRecords     =  0,

        kVisitNextRecord         =  1

};

class nsDiskCacheRecordVisitor {

    public:

    virtual int32_t  VisitRecord( nsDiskCacheRecord *  mapRecord) = 0;

};

/******************************************************************************

 *  nsDiskCacheHeader

 *****************************************************************************/

struct nsDiskCacheHeader {

    uint32_t    mVersion;                           // cache version.

    uint32_t    mDataSize;                          // size of cache in units of 1024bytes.

    int32_t     mEntryCount;                        // number of entries stored in cache.

    uint32_t    mIsDirty;                           // dirty flag.

    int32_t     mRecordCount;                       // Number of records

    uint32_t    mEvictionRank[kBuckets];            // Highest EvictionRank of the bucket

    uint32_t    mBucketUsage[kBuckets];             // Number of used entries in the bucket

    nsDiskCacheHeader()

        : mVersion(nsDiskCache::kCurrentVersion)

        , mDataSize(0)

        , mEntryCount(0)

        , mIsDirty(true)

        , mRecordCount(0)

    {}

    void        Swap()

    {

#if defined(IS_LITTLE_ENDIAN)

        mVersion     = htonl(mVersion);

        mDataSize    = htonl(mDataSize);

        mEntryCount  = htonl(mEntryCount);

        mIsDirty     = htonl(mIsDirty);

        mRecordCount = htonl(mRecordCount);

        for (uint32_t i = 0; i < kBuckets ; i++) {

            mEvictionRank[i] = htonl(mEvictionRank[i]);

            mBucketUsage[i]  = htonl(mBucketUsage[i]);

        }

#endif

    }

    void        Unswap()

    {

#if defined(IS_LITTLE_ENDIAN)

        mVersion     = ntohl(mVersion);

        mDataSize    = ntohl(mDataSize);

        mEntryCount  = ntohl(mEntryCount);

        mIsDirty     = ntohl(mIsDirty);

        mRecordCount = ntohl(mRecordCount);

        for (uint32_t i = 0; i < kBuckets ; i++) {

            mEvictionRank[i] = ntohl(mEvictionRank[i]);

            mBucketUsage[i]  = ntohl(mBucketUsage[i]);

        }

#endif

    }

};

/******************************************************************************

 *  nsDiskCacheMap

 *****************************************************************************/

class nsDiskCacheMap {

public:

     nsDiskCacheMap() :

        mCacheDirectory(nullptr),

        mMapFD(nullptr),

        mCleanFD(nullptr),

        mRecordArray(nullptr),

        mBufferSize(0),

        mBuffer(nullptr),

        mMaxRecordCount(16384), // this default value won't matter

        mIsDirtyCacheFlushed(false),

        mLastInvalidateTime(0)

    { }

    ~nsDiskCacheMap()

    {

        (void) Close(true);

    }

/**

 *  File Operations

 *

 *  Open

 *

 *  Creates a new cache map file if one doesn't exist.

 *  Returns error if it detects change in format or cache wasn't closed.

 */

    nsresult  Open( nsIFile *  cacheDirectory,

                    nsDiskCache::CorruptCacheInfo *  corruptInfo);

    nsresult  Close(bool flush);

    nsresult  Trim();

    nsresult  FlushHeader();

    nsresult  FlushRecords( bool unswap);

    void      NotifyCapacityChange(uint32_t capacity);

/**

 *  Record operations

 */

    nsresult AddRecord( nsDiskCacheRecord *  mapRecord, nsDiskCacheRecord * oldRecord);

    nsresult UpdateRecord( nsDiskCacheRecord *  mapRecord);

    nsresult FindRecord( uint32_t  hashNumber, nsDiskCacheRecord *  mapRecord);

    nsresult DeleteRecord( nsDiskCacheRecord *  mapRecord);

    nsresult VisitRecords( nsDiskCacheRecordVisitor * visitor);

    nsresult EvictRecords( nsDiskCacheRecordVisitor * visitor);

/**

 *  Disk Entry operations

 */

    nsresult    DeleteStorage( nsDiskCacheRecord *  record);

    nsresult    GetFileForDiskCacheRecord( nsDiskCacheRecord * record,

                                           bool                meta,

                                           bool                createPath,

                                           nsIFile **          result);

    nsresult    GetLocalFileForDiskCacheRecord( nsDiskCacheRecord *  record,

                                                bool                 meta,

                                                bool                 createPath,

                                                nsIFile **           result);

    // On success, this returns the buffer owned by nsDiskCacheMap,

    // so it must not be deleted by the caller.

    nsDiskCacheEntry * ReadDiskCacheEntry( nsDiskCacheRecord *  record);

    nsresult    WriteDiskCacheEntry( nsDiskCacheBinding *  binding);

    nsresult    ReadDataCacheBlocks(nsDiskCacheBinding * binding, char * buffer, uint32_t size);

    nsresult    WriteDataCacheBlocks(nsDiskCacheBinding * binding, char * buffer, uint32_t size);

    nsresult    DeleteStorage( nsDiskCacheRecord * record, bool metaData);

    /**

     *  Statistical Operations

     */

    void     IncrementTotalSize( uint32_t  delta)

             {

                mHeader.mDataSize += delta;

                mHeader.mIsDirty   = true;

             }

    void     DecrementTotalSize( uint32_t  delta)

             {

                NS_ASSERTION(mHeader.mDataSize >= delta, "disk cache size negative?");

                mHeader.mDataSize  = mHeader.mDataSize > delta ? mHeader.mDataSize - delta : 0;

                mHeader.mIsDirty   = true;

             }

    inline void IncrementTotalSize( uint32_t  blocks, uint32_t blockSize)

             {

                // Round up to nearest K

                IncrementTotalSize(((blocks*blockSize) + 0x03FF) >> 10);

             }

    inline void DecrementTotalSize( uint32_t  blocks, uint32_t blockSize)

             {

                // Round up to nearest K

                DecrementTotalSize(((blocks*blockSize) + 0x03FF) >> 10);

             }

    uint32_t TotalSize()   { return mHeader.mDataSize; }

    int32_t  EntryCount()  { return mHeader.mEntryCount; }

    size_t  SizeOfExcludingThis(mozilla::MallocSizeOf aMallocSizeOf);

private:

    /**

     *  Private methods

     */

    nsresult    OpenBlockFiles(nsDiskCache::CorruptCacheInfo *  corruptInfo);

    nsresult    CloseBlockFiles(bool flush);

    bool        CacheFilesExist();

    nsresult    CreateCacheSubDirectories();

    uint32_t    CalculateFileIndex(uint32_t size);

    nsresult    GetBlockFileForIndex( uint32_t index, nsIFile ** result);

    uint32_t    GetBlockSizeForIndex( uint32_t index) const {

        return BLOCK_SIZE_FOR_INDEX(index);

    }

    uint32_t    GetBitMapSizeForIndex( uint32_t index) const {

        return BITMAP_SIZE_FOR_INDEX(index);

    }

    // returns the bucket number

    uint32_t GetBucketIndex( uint32_t hashNumber) const {

        return (hashNumber & (kBuckets - 1));

    }

    // Gets the size of the bucket (in number of records)

    uint32_t GetRecordsPerBucket() const {

        return mHeader.mRecordCount / kBuckets;

    }

    // Gets the first record in the bucket

    nsDiskCacheRecord *GetFirstRecordInBucket(uint32_t bucket) const {

        return mRecordArray + bucket * GetRecordsPerBucket();

    }

    uint32_t GetBucketRank(uint32_t bucketIndex, uint32_t targetRank);

    int32_t  VisitEachRecord(uint32_t                    bucketIndex,

                             nsDiskCacheRecordVisitor *  visitor,

                             uint32_t                    evictionRank);

    nsresult GrowRecords();

    nsresult ShrinkRecords();

    nsresult EnsureBuffer(uint32_t bufSize);

    // The returned structure will point to the buffer owned by nsDiskCacheMap,

    // so it must not be deleted by the caller.

    nsDiskCacheEntry *  CreateDiskCacheEntry(nsDiskCacheBinding *  binding,

                                             uint32_t * size);

    // Initializes the _CACHE_CLEAN_ related functionality

    nsresult InitCacheClean(nsIFile *  cacheDirectory,

                            nsDiskCache::CorruptCacheInfo *  corruptInfo);

    // Writes out a value of '0' or '1' in the _CACHE_CLEAN_ file

    nsresult WriteCacheClean(bool clean);

    // Resets the timout for revalidating the cache

    nsresult ResetCacheTimer(int32_t timeout = kRevalidateCacheTimeout);

    // Invalidates the cache, calls WriteCacheClean and ResetCacheTimer

    nsresult InvalidateCache();

    // Determines if the cache is in a safe state

    bool IsCacheInSafeState();

    // Revalidates the cache by writting out the header, records, and finally

    // by calling WriteCacheClean(true).

    nsresult RevalidateCache();

    // Timer which revalidates the cache

    static void RevalidateTimerCallback(nsITimer *aTimer, void *arg);

/**

 *  data members

 */

private:

    nsCOMPtr<nsITimer>      mCleanCacheTimer;

    nsCOMPtr<nsIFile>       mCacheDirectory;

    PRFileDesc *            mMapFD;

    PRFileDesc *            mCleanFD;

    nsDiskCacheRecord *     mRecordArray;

    nsDiskCacheBlockFile    mBlockFile[kNumBlockFiles];

    uint32_t                mBufferSize;

    char *                  mBuffer;

    nsDiskCacheHeader       mHeader;

    int32_t                 mMaxRecordCount;

    bool                    mIsDirtyCacheFlushed;

    PRIntervalTime          mLastInvalidateTime;

};

#endif // _nsDiskCacheMap_h_