diff options
Diffstat (limited to 'net/disk_cache/disk_format.h')
| -rw-r--r-- | net/disk_cache/disk_format.h | 192 |
1 files changed, 192 insertions, 0 deletions
diff --git a/net/disk_cache/disk_format.h b/net/disk_cache/disk_format.h new file mode 100644 index 0000000..4546c88 --- /dev/null +++ b/net/disk_cache/disk_format.h @@ -0,0 +1,192 @@ +// Copyright 2008, Google Inc. +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +// The cache is stored on disk as a collection of block-files, plus an index +// file plus a collection of external files. +// +// Any data blob bigger than kMaxBlockSize (net/addr.h) will be stored on a +// separate file named f_xxx where x is a hexadecimal number. Shorter data will +// be stored as a series of blocks on a block-file. In any case, CacheAddr +// represents the address of the data inside the cache. +// +// The index file is just a simple hash table that maps a particular entry to +// a CacheAddr value. Linking for a given hash bucket is handled internally +// by the cache entry. +// +// The last element of the cache is the block-file. A block file is a file +// designed to store blocks of data of a given size. It is able to store data +// that spans from one to four consecutive "blocks", and it grows as needed to +// store up to approximately 65000 blocks. It has a fixed size header used for +// book keeping such as tracking free of blocks on the file. For example, a +// block-file for 1KB blocks will grow from 8KB when totally empty to about 64MB +// when completely full. At that point, data blocks of 1KB will be stored on a +// second block file that will store the next set of 65000 blocks. The first +// file contains the number of the second file, and the second file contains the +// number of a third file, created when the second file reaches its limit. It is +// important to remember that no matter how long the chain of files is, any +// given block can be located directly by its address, which contains the file +// number and starting block inside the file. +// +// A new cache is initialized with four block files (named data_0 through +// data_3), each one dedicated to store blocks of a given size. The number at +// the end of the file name is the block file number (in decimal). +// +// There are two "special" types of blocks: an entry and a rankings node. An +// entry keeps track of all the information related to the same cache entry, +// such as the key, hash value, data pointers etc. A rankings node keeps track +// of the information that is updated frequently for a given entry, such as its +// location on the LRU list, last access time etc. +// +// The files that store internal information for the cache (blocks and index) +// are at least partially memory mapped. They have a location that is signaled +// every time the internal structures are modified, so it is possible to detect +// (most of the time) when the process dies in the middle of an update. +// +// In order to prevent dirty data to be used as valid (after a crash), every +// cache entry has a dirty identifier. Each running instance of the cache keeps +// a separate identifier (maintained on the "this_id" header field) that is used +// to mark every entry that is created or modified. When the entry is closed, +// and all the data can be trusted, the dirty flag is cleared from the entry. +// When the cache encounters an entry whose identifier is different than the one +// being currently used, it means that the entry was not properly closed on a +// previous run, so it is discarded. + +#ifndef NET_DISK_CACHE_DISK_FORMAT_H__ +#define NET_DISK_CACHE_DISK_FORMAT_H__ + +#include "base/basictypes.h" + +namespace disk_cache { + +typedef uint32 CacheAddr; + +const int kIndexTablesize = 0x10000; +const uint32 kIndexMagic = 0xC103CAC3; +const uint32 kCurrentVersion = 0x10002; // Version 1.2. + +// Header for the master index file. +struct IndexHeader { + uint32 magic; + uint32 version; + int32 num_entries; // Number of entries currently stored. + int32 num_bytes; // Total size of the stored data. + int32 last_file; // Last external file created. + int32 this_id; // Id for all entries being changed (dirty flag). + CacheAddr stats; // Storage for usage data. + int32 table_len; // Actual size of the table (0 == kIndexTablesize). + int32 pad[8]; + IndexHeader() { + memset(this, 0, sizeof(*this)); + magic = kIndexMagic; + version = kCurrentVersion; + }; +}; + +// The structure of the whole index file. +struct Index { + IndexHeader header; + CacheAddr table[kIndexTablesize]; // Default size. Actual size controlled + // by header.table_len. +}; + +// Main structure for an entry on the backing storage. If the key is longer than +// what can be stored on this structure, it will be extended on consecutive +// blocks (adding 256 bytes each time), up to 4 blocks (1024 - 32 - 1 chars). +// After that point, the whole key will be stored as a data block or external +// file. +struct EntryStore { + uint32 hash; // Full hash of the key. + CacheAddr next; // Next entry with the same hash or bucket. + CacheAddr rankings_node; // Rankings node for this entry. + int32 key_len; + CacheAddr long_key; // Optional address of a long key. + int32 data_size[2]; // We can store up to 2 data chunks for each + CacheAddr data_addr[2]; // entry. + char key[256 - 9 * 4]; // null terminated +}; + +COMPILE_ASSERT(sizeof(EntryStore) == 256, bad_EntyStore); +const int kMaxInternalKeyLength = 4 * sizeof(EntryStore) - + offsetof(EntryStore, key) - 1; + +#pragma pack(push, old, 4) +// Rankings information for a given entry. +struct RankingsNode { + uint64 last_used; // LRU info. + uint64 last_modified; // LRU info. + CacheAddr next; // LRU list. + CacheAddr prev; // LRU list. + CacheAddr contents; // Address of the EntryStore. + int32 dirty; // The entry is being modifyied. + void* pointer; // Pointer to the in-memory entry. +}; +#pragma pack(pop, old) + +COMPILE_ASSERT(sizeof(RankingsNode) == 36, bad_RankingsNode); + +const uint32 kBlockMagic = 0xC104CAC3; +const int kBlockHeaderSize = 8192; // Two pages: almost 64k entries +const int kMaxBlocks = (kBlockHeaderSize - 80) * 8; + +// Bitmap to track used blocks on a block-file. +typedef uint32 AllocBitmap[kMaxBlocks / 32]; + +// A block-file is the file used to store information in blocks (could be +// EntryStore blocks, RankingsNode blocks or user-data blocks). +// We store entries that can expand for up to 4 consecutive blocks, and keep +// counters of the number of blocks available for each type of entry. For +// instance, an entry of 3 blocks is an entry of type 3. We also keep track of +// where did we find the last entry of that type (to avoid searching the bitmap +// from the beginning every time). +// This Structure is the header of a block-file: +struct BlockFileHeader { + uint32 magic; + uint32 version; + int16 this_file; // Index of this file. + int16 next_file; // Next file when this one is full. + int32 entry_size; // Size of the blocks of this file. + int32 num_entries; // Number of stored entries. + int32 max_entries; // Current maximum number of entries. + int32 empty[4]; // Counters of empty entries for each type. + int32 hints[4]; // Last used position for each entry type. + volatile int32 updating; // Keep track of updates to the header. + int32 user[5]; + AllocBitmap allocation_map; + BlockFileHeader() { + memset(this, 0, sizeof(BlockFileHeader)); + magic = kBlockMagic; + version = kCurrentVersion; + }; +}; + +COMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header); + +} // namespace disk_cache + +#endif // NET_DISK_CACHE_DISK_FORMAT_H__ |