michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  *
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "nsCache.h"
michael@0: #include "nsDiskCache.h"
michael@0: #include "nsDiskCacheBlockFile.h"
michael@0: #include "mozilla/FileUtils.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include <algorithm>
michael@0: 
michael@0: using namespace mozilla;
michael@0: 
michael@0: /******************************************************************************
michael@0:  * nsDiskCacheBlockFile - 
michael@0:  *****************************************************************************/
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  Open
michael@0:  *****************************************************************************/
michael@0: nsresult
michael@0: nsDiskCacheBlockFile::Open(nsIFile * blockFile,
michael@0:                            uint32_t  blockSize,
michael@0:                            uint32_t  bitMapSize,
michael@0:                            nsDiskCache::CorruptCacheInfo *  corruptInfo)
michael@0: {
michael@0:     NS_ENSURE_ARG_POINTER(corruptInfo);
michael@0:     *corruptInfo = nsDiskCache::kUnexpectedError;
michael@0: 
michael@0:     if (bitMapSize % 32) {
michael@0:         *corruptInfo = nsDiskCache::kInvalidArgPointer;
michael@0:         return NS_ERROR_INVALID_ARG;
michael@0:     }
michael@0: 
michael@0:     mBlockSize = blockSize;
michael@0:     mBitMapWords = bitMapSize / 32;
michael@0:     uint32_t bitMapBytes = mBitMapWords * 4;
michael@0:     
michael@0:     // open the file - restricted to user, the data could be confidential
michael@0:     nsresult rv = blockFile->OpenNSPRFileDesc(PR_RDWR | PR_CREATE_FILE, 00600, &mFD);
michael@0:     if (NS_FAILED(rv)) {
michael@0:         *corruptInfo = nsDiskCache::kCouldNotCreateBlockFile;
michael@0:         CACHE_LOG_DEBUG(("CACHE: nsDiskCacheBlockFile::Open "
michael@0:                          "[this=%p] unable to open or create file: %d",
michael@0:                          this, rv));
michael@0:         return rv;  // unable to open or create file
michael@0:     }
michael@0:     
michael@0:     // allocate bit map buffer
michael@0:     mBitMap = new uint32_t[mBitMapWords];
michael@0:     
michael@0:     // check if we just creating the file
michael@0:     mFileSize = PR_Available(mFD);
michael@0:     if (mFileSize < 0) {
michael@0:         // XXX an error occurred. We could call PR_GetError(), but how would that help?
michael@0:         *corruptInfo = nsDiskCache::kBlockFileSizeError;
michael@0:         rv = NS_ERROR_UNEXPECTED;
michael@0:         goto error_exit;
michael@0:     }
michael@0:     if (mFileSize == 0) {
michael@0:         // initialize bit map and write it
michael@0:         memset(mBitMap, 0, bitMapBytes);
michael@0:         if (!Write(0, mBitMap, bitMapBytes)) {
michael@0:             *corruptInfo = nsDiskCache::kBlockFileBitMapWriteError;
michael@0:             goto error_exit;
michael@0:         }
michael@0:         
michael@0:     } else if ((uint32_t)mFileSize < bitMapBytes) {
michael@0:         *corruptInfo = nsDiskCache::kBlockFileSizeLessThanBitMap;
michael@0:         rv = NS_ERROR_UNEXPECTED;  // XXX NS_ERROR_CACHE_INVALID;
michael@0:         goto error_exit;
michael@0:         
michael@0:     } else {
michael@0:         // read the bit map
michael@0:         const int32_t bytesRead = PR_Read(mFD, mBitMap, bitMapBytes);
michael@0:         if ((bytesRead < 0) || ((uint32_t)bytesRead < bitMapBytes)) {
michael@0:             *corruptInfo = nsDiskCache::kBlockFileBitMapReadError;
michael@0:             rv = NS_ERROR_UNEXPECTED;
michael@0:             goto error_exit;
michael@0:         }
michael@0: #if defined(IS_LITTLE_ENDIAN)
michael@0:         // Swap from network format
michael@0:         for (unsigned int i = 0; i < mBitMapWords; ++i)
michael@0:             mBitMap[i] = ntohl(mBitMap[i]);
michael@0: #endif
michael@0:         // validate block file size
michael@0:         // Because not whole blocks are written, the size may be a 
michael@0:         // little bit smaller than used blocks times blocksize,
michael@0:         // because the last block will generally not be 'whole'.
michael@0:         const uint32_t  estimatedSize = CalcBlockFileSize();
michael@0:         if ((uint32_t)mFileSize + blockSize < estimatedSize) {
michael@0:             *corruptInfo = nsDiskCache::kBlockFileEstimatedSizeError;
michael@0:             rv = NS_ERROR_UNEXPECTED;
michael@0:             goto error_exit;
michael@0:         }
michael@0:     }
michael@0:     CACHE_LOG_DEBUG(("CACHE: nsDiskCacheBlockFile::Open [this=%p] succeeded",
michael@0:                       this));
michael@0:     return NS_OK;
michael@0: 
michael@0: error_exit:
michael@0:     CACHE_LOG_DEBUG(("CACHE: nsDiskCacheBlockFile::Open [this=%p] failed with "
michael@0:                      "error %d", this, rv));
michael@0:     Close(false);
michael@0:     return rv;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  Close
michael@0:  *****************************************************************************/
michael@0: nsresult
michael@0: nsDiskCacheBlockFile::Close(bool flush)
michael@0: {
michael@0:     nsresult rv = NS_OK;
michael@0: 
michael@0:     if (mFD) {
michael@0:         if (flush)
michael@0:             rv  = FlushBitMap();
michael@0:         PRStatus err = PR_Close(mFD);
michael@0:         if (NS_SUCCEEDED(rv) && (err != PR_SUCCESS))
michael@0:             rv = NS_ERROR_UNEXPECTED;
michael@0:         mFD = nullptr;
michael@0:     }
michael@0: 
michael@0:      if (mBitMap) {
michael@0:          delete [] mBitMap;
michael@0:          mBitMap = nullptr;
michael@0:      }
michael@0:         
michael@0:     return rv;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  AllocateBlocks
michael@0:  *
michael@0:  *  Allocates 1-4 blocks, using a first fit strategy,
michael@0:  *  so that no group of blocks spans a quad block boundary.
michael@0:  *
michael@0:  *  Returns block number of first block allocated or -1 on failure.
michael@0:  *
michael@0:  *****************************************************************************/
michael@0: int32_t
michael@0: nsDiskCacheBlockFile::AllocateBlocks(int32_t numBlocks)
michael@0: {
michael@0:     const int maxPos = 32 - numBlocks;
michael@0:     const uint32_t mask = (0x01 << numBlocks) - 1;
michael@0:     for (unsigned int i = 0; i < mBitMapWords; ++i) {
michael@0:         uint32_t mapWord = ~mBitMap[i]; // flip bits so free bits are 1
michael@0:         if (mapWord) {                  // At least one free bit
michael@0:             // Binary search for first free bit in word
michael@0:             int bit = 0;
michael@0:             if ((mapWord & 0x0FFFF) == 0) { bit |= 16; mapWord >>= 16; }
michael@0:             if ((mapWord & 0x000FF) == 0) { bit |= 8;  mapWord >>= 8;  }
michael@0:             if ((mapWord & 0x0000F) == 0) { bit |= 4;  mapWord >>= 4;  }
michael@0:             if ((mapWord & 0x00003) == 0) { bit |= 2;  mapWord >>= 2;  }
michael@0:             if ((mapWord & 0x00001) == 0) { bit |= 1;  mapWord >>= 1;  }
michael@0:             // Find first fit for mask
michael@0:             for (; bit <= maxPos; ++bit) {
michael@0:                 // all bits selected by mask are 1, so free
michael@0:                 if ((mask & mapWord) == mask) {
michael@0:                     mBitMap[i] |= mask << bit; 
michael@0:                     mBitMapDirty = true;
michael@0:                     return (int32_t)i * 32 + bit;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     
michael@0:     return -1;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  DeallocateBlocks
michael@0:  *****************************************************************************/
michael@0: nsresult
michael@0: nsDiskCacheBlockFile::DeallocateBlocks( int32_t  startBlock, int32_t  numBlocks)
michael@0: {
michael@0:     if (!mFD)  return NS_ERROR_NOT_AVAILABLE;
michael@0: 
michael@0:     if ((startBlock < 0) || ((uint32_t)startBlock > mBitMapWords * 32 - 1) ||
michael@0:         (numBlocks < 1)  || (numBlocks > 4))
michael@0:        return NS_ERROR_ILLEGAL_VALUE;
michael@0:            
michael@0:     const int32_t startWord = startBlock >> 5;      // Divide by 32
michael@0:     const uint32_t startBit = startBlock & 31;      // Modulo by 32 
michael@0:       
michael@0:     // make sure requested deallocation doesn't span a word boundary
michael@0:     if (startBit + numBlocks > 32)  return NS_ERROR_UNEXPECTED;
michael@0:     uint32_t mask = ((0x01 << numBlocks) - 1) << startBit;
michael@0:     
michael@0:     // make sure requested deallocation is currently allocated
michael@0:     if ((mBitMap[startWord] & mask) != mask)    return NS_ERROR_ABORT;
michael@0: 
michael@0:     mBitMap[startWord] ^= mask;    // flips the bits off;
michael@0:     mBitMapDirty = true;
michael@0:     // XXX rv = FlushBitMap();  // coherency vs. performance
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  WriteBlocks
michael@0:  *****************************************************************************/
michael@0: nsresult
michael@0: nsDiskCacheBlockFile::WriteBlocks( void *   buffer,
michael@0:                                    uint32_t size,
michael@0:                                    int32_t  numBlocks,
michael@0:                                    int32_t * startBlock)
michael@0: {
michael@0:     // presume buffer != nullptr and startBlock != nullptr
michael@0:     NS_ENSURE_TRUE(mFD, NS_ERROR_NOT_AVAILABLE);
michael@0: 
michael@0:     // allocate some blocks in the cache block file
michael@0:     *startBlock = AllocateBlocks(numBlocks);
michael@0:     if (*startBlock < 0)
michael@0:         return NS_ERROR_NOT_AVAILABLE;
michael@0: 
michael@0:     // seek to block position
michael@0:     int32_t blockPos = mBitMapWords * 4 + *startBlock * mBlockSize;
michael@0:     
michael@0:     // write the blocks
michael@0:     return Write(blockPos, buffer, size) ? NS_OK : NS_ERROR_FAILURE;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  ReadBlocks
michael@0:  *****************************************************************************/
michael@0: nsresult
michael@0: nsDiskCacheBlockFile::ReadBlocks( void *    buffer,
michael@0:                                   int32_t   startBlock,
michael@0:                                   int32_t   numBlocks,
michael@0:                                   int32_t * bytesRead)
michael@0: {
michael@0:     // presume buffer != nullptr and bytesRead != bytesRead
michael@0: 
michael@0:     if (!mFD)  return NS_ERROR_NOT_AVAILABLE;
michael@0:     nsresult rv = VerifyAllocation(startBlock, numBlocks);
michael@0:     if (NS_FAILED(rv))  return rv;
michael@0:     
michael@0:     // seek to block position
michael@0:     int32_t blockPos = mBitMapWords * 4 + startBlock * mBlockSize;
michael@0:     int32_t filePos = PR_Seek(mFD, blockPos, PR_SEEK_SET);
michael@0:     if (filePos != blockPos)  return NS_ERROR_UNEXPECTED;
michael@0: 
michael@0:     // read the blocks
michael@0:     int32_t bytesToRead = *bytesRead;
michael@0:     if ((bytesToRead <= 0) || ((uint32_t)bytesToRead > mBlockSize * numBlocks)) {
michael@0:         bytesToRead = mBlockSize * numBlocks;
michael@0:     }
michael@0:     *bytesRead = PR_Read(mFD, buffer, bytesToRead);
michael@0:     
michael@0:     CACHE_LOG_DEBUG(("CACHE: nsDiskCacheBlockFile::Read [this=%p] "
michael@0:                      "returned %d / %d bytes", this, *bytesRead, bytesToRead));
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  FlushBitMap
michael@0:  *****************************************************************************/
michael@0: nsresult
michael@0: nsDiskCacheBlockFile::FlushBitMap()
michael@0: {
michael@0:     if (!mBitMapDirty)  return NS_OK;
michael@0:     
michael@0: #if defined(IS_LITTLE_ENDIAN)
michael@0:     uint32_t *bitmap = new uint32_t[mBitMapWords];
michael@0:     // Copy and swap to network format
michael@0:     uint32_t *p = bitmap;
michael@0:     for (unsigned int i = 0; i < mBitMapWords; ++i, ++p)
michael@0:       *p = htonl(mBitMap[i]);
michael@0: #else
michael@0:     uint32_t *bitmap = mBitMap;
michael@0: #endif
michael@0: 
michael@0:     // write bitmap
michael@0:     bool written = Write(0, bitmap, mBitMapWords * 4);
michael@0: #if defined(IS_LITTLE_ENDIAN)
michael@0:     delete [] bitmap;
michael@0: #endif
michael@0:     if (!written)
michael@0:         return NS_ERROR_UNEXPECTED;
michael@0: 
michael@0:     PRStatus err = PR_Sync(mFD);
michael@0:     if (err != PR_SUCCESS)  return NS_ERROR_UNEXPECTED;
michael@0: 
michael@0:     mBitMapDirty = false;
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  VerifyAllocation
michael@0:  *
michael@0:  *  Return values:
michael@0:  *      NS_OK if all bits are marked allocated
michael@0:  *      NS_ERROR_ILLEGAL_VALUE if parameters don't obey constraints
michael@0:  *      NS_ERROR_FAILURE if some or all the bits are marked unallocated
michael@0:  *
michael@0:  *****************************************************************************/
michael@0: nsresult
michael@0: nsDiskCacheBlockFile::VerifyAllocation( int32_t  startBlock, int32_t  numBlocks)
michael@0: {
michael@0:     if ((startBlock < 0) || ((uint32_t)startBlock > mBitMapWords * 32 - 1) ||
michael@0:         (numBlocks < 1)  || (numBlocks > 4))
michael@0:        return NS_ERROR_ILLEGAL_VALUE;
michael@0:     
michael@0:     const int32_t startWord = startBlock >> 5;      // Divide by 32
michael@0:     const uint32_t startBit = startBlock & 31;      // Modulo by 32 
michael@0:       
michael@0:     // make sure requested deallocation doesn't span a word boundary
michael@0:     if (startBit + numBlocks > 32)  return NS_ERROR_ILLEGAL_VALUE;
michael@0:     uint32_t mask = ((0x01 << numBlocks) - 1) << startBit;
michael@0:     
michael@0:     // check if all specified blocks are currently allocated
michael@0:     if ((mBitMap[startWord] & mask) != mask)    return NS_ERROR_FAILURE;
michael@0:     
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  CalcBlockFileSize
michael@0:  *
michael@0:  *  Return size of the block file according to the bits set in mBitmap
michael@0:  *
michael@0:  *****************************************************************************/
michael@0: uint32_t
michael@0: nsDiskCacheBlockFile::CalcBlockFileSize()
michael@0: {
michael@0:     // search for last byte in mBitMap with allocated bits
michael@0:     uint32_t  estimatedSize = mBitMapWords * 4;
michael@0:     int32_t   i = mBitMapWords;
michael@0:     while (--i >= 0) {
michael@0:         if (mBitMap[i]) break;
michael@0:     }
michael@0: 
michael@0:     if (i >= 0) {
michael@0:         // binary search to find last allocated bit in byte
michael@0:         uint32_t mapWord = mBitMap[i];
michael@0:         uint32_t lastBit = 31;
michael@0:         if ((mapWord & 0xFFFF0000) == 0) { lastBit ^= 16; mapWord <<= 16; }
michael@0:         if ((mapWord & 0xFF000000) == 0) { lastBit ^= 8; mapWord <<= 8; }
michael@0:         if ((mapWord & 0xF0000000) == 0) { lastBit ^= 4; mapWord <<= 4; }
michael@0:         if ((mapWord & 0xC0000000) == 0) { lastBit ^= 2; mapWord <<= 2; }
michael@0:         if ((mapWord & 0x80000000) == 0) { lastBit ^= 1; mapWord <<= 1; }
michael@0:         estimatedSize +=  (i * 32 + lastBit + 1) * mBlockSize;
michael@0:     }
michael@0: 
michael@0:     return estimatedSize;
michael@0: }
michael@0: 
michael@0: /******************************************************************************
michael@0:  *  Write
michael@0:  *
michael@0:  *  Wrapper around PR_Write that grows file in larger chunks to combat fragmentation
michael@0:  *
michael@0:  *****************************************************************************/
michael@0: bool
michael@0: nsDiskCacheBlockFile::Write(int32_t offset, const void *buf, int32_t amount)
michael@0: {
michael@0:     /* Grow the file to 4mb right away, then double it until the file grows to 20mb.
michael@0:        20mb is a magic threshold because OSX stops autodefragging files bigger than that.
michael@0:        Beyond 20mb grow in 4mb chunks.
michael@0:      */
michael@0:     const int32_t upTo = offset + amount;
michael@0:     // Use a conservative definition of 20MB
michael@0:     const int32_t minPreallocate = 4*1024*1024;
michael@0:     const int32_t maxPreallocate = 20*1000*1000;
michael@0:     if (mFileSize < upTo) {
michael@0:         // maximal file size
michael@0:         const int32_t maxFileSize = mBitMapWords * 4 * (mBlockSize * 8 + 1);
michael@0:         if (upTo > maxPreallocate) {
michael@0:             // grow the file as a multiple of minPreallocate
michael@0:             mFileSize = ((upTo + minPreallocate - 1) / minPreallocate) * minPreallocate;
michael@0:         } else {
michael@0:             // Grow quickly between 1MB to 20MB
michael@0:             if (mFileSize)
michael@0:                 while(mFileSize < upTo)
michael@0:                     mFileSize *= 2;
michael@0:             mFileSize = clamped(mFileSize, minPreallocate, maxPreallocate);
michael@0:         }
michael@0:         mFileSize = std::min(mFileSize, maxFileSize);
michael@0: #if !defined(XP_MACOSX)
michael@0:         mozilla::fallocate(mFD, mFileSize);
michael@0: #endif
michael@0:     }
michael@0:     if (PR_Seek(mFD, offset, PR_SEEK_SET) != offset)
michael@0:         return false;
michael@0:     return PR_Write(mFD, buf, amount) == amount;
michael@0: }
michael@0: 
michael@0: size_t
michael@0: nsDiskCacheBlockFile::SizeOfExcludingThis(MallocSizeOf aMallocSizeOf)
michael@0: {
michael@0:     return aMallocSizeOf(mBitMap) + aMallocSizeOf(mFD);
michael@0: }