1// Copyright (c) 2006-2009 The Chromium Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5// The cache is stored on disk as a collection of block-files, plus an index 6// file plus a collection of external files. 7// 8// Any data blob bigger than kMaxBlockSize (net/addr.h) will be stored on a 9// separate file named f_xxx where x is a hexadecimal number. Shorter data will 10// be stored as a series of blocks on a block-file. In any case, CacheAddr 11// represents the address of the data inside the cache. 12// 13// The index file is just a simple hash table that maps a particular entry to 14// a CacheAddr value. Linking for a given hash bucket is handled internally 15// by the cache entry. 16// 17// The last element of the cache is the block-file. A block file is a file 18// designed to store blocks of data of a given size. It is able to store data 19// that spans from one to four consecutive "blocks", and it grows as needed to 20// store up to approximately 65000 blocks. It has a fixed size header used for 21// book keeping such as tracking free of blocks on the file. For example, a 22// block-file for 1KB blocks will grow from 8KB when totally empty to about 64MB 23// when completely full. At that point, data blocks of 1KB will be stored on a 24// second block file that will store the next set of 65000 blocks. The first 25// file contains the number of the second file, and the second file contains the 26// number of a third file, created when the second file reaches its limit. It is 27// important to remember that no matter how long the chain of files is, any 28// given block can be located directly by its address, which contains the file 29// number and starting block inside the file. 30// 31// A new cache is initialized with four block files (named data_0 through 32// data_3), each one dedicated to store blocks of a given size. The number at 33// the end of the file name is the block file number (in decimal). 34// 35// There are two "special" types of blocks: an entry and a rankings node. An 36// entry keeps track of all the information related to the same cache entry, 37// such as the key, hash value, data pointers etc. A rankings node keeps track 38// of the information that is updated frequently for a given entry, such as its 39// location on the LRU lists, last access time etc. 40// 41// The files that store internal information for the cache (blocks and index) 42// are at least partially memory mapped. They have a location that is signaled 43// every time the internal structures are modified, so it is possible to detect 44// (most of the time) when the process dies in the middle of an update. 45// 46// In order to prevent dirty data to be used as valid (after a crash), every 47// cache entry has a dirty identifier. Each running instance of the cache keeps 48// a separate identifier (maintained on the "this_id" header field) that is used 49// to mark every entry that is created or modified. When the entry is closed, 50// and all the data can be trusted, the dirty flag is cleared from the entry. 51// When the cache encounters an entry whose identifier is different than the one 52// being currently used, it means that the entry was not properly closed on a 53// previous run, so it is discarded. 54 55#ifndef NET_DISK_CACHE_DISK_FORMAT_H_ 56#define NET_DISK_CACHE_DISK_FORMAT_H_ 57#pragma once 58 59#include "base/basictypes.h" 60 61namespace disk_cache { 62 63typedef uint32 CacheAddr; 64 65const int kIndexTablesize = 0x10000; 66const uint32 kIndexMagic = 0xC103CAC3; 67const uint32 kCurrentVersion = 0x20000; // Version 2.0. 68 69struct LruData { 70 int32 pad1[2]; 71 int32 filled; // Flag to tell when we filled the cache. 72 int32 sizes[5]; 73 CacheAddr heads[5]; 74 CacheAddr tails[5]; 75 CacheAddr transaction; // In-flight operation target. 76 int32 operation; // Actual in-flight operation. 77 int32 operation_list; // In-flight operation list. 78 int32 pad2[7]; 79}; 80 81// Header for the master index file. 82struct IndexHeader { 83 IndexHeader(); 84 85 uint32 magic; 86 uint32 version; 87 int32 num_entries; // Number of entries currently stored. 88 int32 num_bytes; // Total size of the stored data. 89 int32 last_file; // Last external file created. 90 int32 this_id; // Id for all entries being changed (dirty flag). 91 CacheAddr stats; // Storage for usage data. 92 int32 table_len; // Actual size of the table (0 == kIndexTablesize). 93 int32 crash; // Signals a previous crash. 94 int32 experiment; // Id of an ongoing test. 95 uint64 create_time; // Creation time for this set of files. 96 int32 pad[52]; 97 LruData lru; // Eviction control data. 98}; 99 100// The structure of the whole index file. 101struct Index { 102 IndexHeader header; 103 CacheAddr table[kIndexTablesize]; // Default size. Actual size controlled 104 // by header.table_len. 105}; 106 107// Main structure for an entry on the backing storage. If the key is longer than 108// what can be stored on this structure, it will be extended on consecutive 109// blocks (adding 256 bytes each time), up to 4 blocks (1024 - 32 - 1 chars). 110// After that point, the whole key will be stored as a data block or external 111// file. 112struct EntryStore { 113 uint32 hash; // Full hash of the key. 114 CacheAddr next; // Next entry with the same hash or bucket. 115 CacheAddr rankings_node; // Rankings node for this entry. 116 int32 reuse_count; // How often is this entry used. 117 int32 refetch_count; // How often is this fetched from the net. 118 int32 state; // Current state. 119 uint64 creation_time; 120 int32 key_len; 121 CacheAddr long_key; // Optional address of a long key. 122 int32 data_size[4]; // We can store up to 4 data streams for each 123 CacheAddr data_addr[4]; // entry. 124 uint32 flags; // Any combination of EntryFlags. 125 int32 pad[5]; 126 char key[256 - 24 * 4]; // null terminated 127}; 128 129COMPILE_ASSERT(sizeof(EntryStore) == 256, bad_EntyStore); 130const int kMaxInternalKeyLength = 4 * sizeof(EntryStore) - 131 offsetof(EntryStore, key) - 1; 132 133// Possible states for a given entry. 134enum EntryState { 135 ENTRY_NORMAL = 0, 136 ENTRY_EVICTED, // The entry was recently evicted from the cache. 137 ENTRY_DOOMED // The entry was doomed. 138}; 139 140// Flags that can be applied to an entry. 141enum EntryFlags { 142 PARENT_ENTRY = 1, // This entry has children (sparse) entries. 143 CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. 144}; 145 146#pragma pack(push, 4) 147// Rankings information for a given entry. 148struct RankingsNode { 149 uint64 last_used; // LRU info. 150 uint64 last_modified; // LRU info. 151 CacheAddr next; // LRU list. 152 CacheAddr prev; // LRU list. 153 CacheAddr contents; // Address of the EntryStore. 154 int32 dirty; // The entry is being modifyied. 155 int32 dummy; // Old files may have a pointer here. 156}; 157#pragma pack(pop) 158 159COMPILE_ASSERT(sizeof(RankingsNode) == 36, bad_RankingsNode); 160 161const uint32 kBlockMagic = 0xC104CAC3; 162const int kBlockHeaderSize = 8192; // Two pages: almost 64k entries 163const int kMaxBlocks = (kBlockHeaderSize - 80) * 8; 164 165// Bitmap to track used blocks on a block-file. 166typedef uint32 AllocBitmap[kMaxBlocks / 32]; 167 168// A block-file is the file used to store information in blocks (could be 169// EntryStore blocks, RankingsNode blocks or user-data blocks). 170// We store entries that can expand for up to 4 consecutive blocks, and keep 171// counters of the number of blocks available for each type of entry. For 172// instance, an entry of 3 blocks is an entry of type 3. We also keep track of 173// where did we find the last entry of that type (to avoid searching the bitmap 174// from the beginning every time). 175// This Structure is the header of a block-file: 176struct BlockFileHeader { 177 BlockFileHeader(); 178 179 uint32 magic; 180 uint32 version; 181 int16 this_file; // Index of this file. 182 int16 next_file; // Next file when this one is full. 183 int32 entry_size; // Size of the blocks of this file. 184 int32 num_entries; // Number of stored entries. 185 int32 max_entries; // Current maximum number of entries. 186 int32 empty[4]; // Counters of empty entries for each type. 187 int32 hints[4]; // Last used position for each entry type. 188 volatile int32 updating; // Keep track of updates to the header. 189 int32 user[5]; 190 AllocBitmap allocation_map; 191}; 192 193COMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header); 194 195// Sparse data support: 196// We keep a two level hierarchy to enable sparse data for an entry: the first 197// level consists of using separate "child" entries to store ranges of 1 MB, 198// and the second level stores blocks of 1 KB inside each child entry. 199// 200// Whenever we need to access a particular sparse offset, we first locate the 201// child entry that stores that offset, so we discard the 20 least significant 202// bits of the offset, and end up with the child id. For instance, the child id 203// to store the first megabyte is 0, and the child that should store offset 204// 0x410000 has an id of 4. 205// 206// The child entry is stored the same way as any other entry, so it also has a 207// name (key). The key includes a signature to be able to identify children 208// created for different generations of the same resource. In other words, given 209// that a given sparse entry can have a large number of child entries, and the 210// resource can be invalidated and replaced with a new version at any time, it 211// is important to be sure that a given child actually belongs to certain entry. 212// 213// The full name of a child entry is composed with a prefix ("Range_"), and two 214// hexadecimal 64-bit numbers at the end, separated by semicolons. The first 215// number is the signature of the parent key, and the second number is the child 216// id as described previously. The signature itself is also stored internally by 217// the child and the parent entries. For example, a sparse entry with a key of 218// "sparse entry name", and a signature of 0x052AF76, may have a child entry 219// named "Range_sparse entry name:052af76:4", which stores data in the range 220// 0x400000 to 0x4FFFFF. 221// 222// Each child entry keeps track of all the 1 KB blocks that have been written 223// to the entry, but being a regular entry, it will happily return zeros for any 224// read that spans data not written before. The actual sparse data is stored in 225// one of the data streams of the child entry (at index 1), while the control 226// information is stored in another stream (at index 2), both by parents and 227// the children. 228 229// This structure contains the control information for parent and child entries. 230// It is stored at offset 0 of the data stream with index 2. 231// It is possible to write to a child entry in a way that causes the last block 232// to be only partialy filled. In that case, last_block and last_block_len will 233// keep track of that block. 234struct SparseHeader { 235 int64 signature; // The parent and children signature. 236 uint32 magic; // Structure identifier (equal to kIndexMagic). 237 int32 parent_key_len; // Key length for the parent entry. 238 int32 last_block; // Index of the last written block. 239 int32 last_block_len; // Lenght of the last written block. 240 int32 dummy[10]; 241}; 242 243// The SparseHeader will be followed by a bitmap, as described by this 244// structure. 245struct SparseData { 246 SparseHeader header; 247 uint32 bitmap[32]; // Bitmap representation of known children (if this 248 // is a parent entry), or used blocks (for child 249 // entries. The size is fixed for child entries but 250 // not for parents; it can be as small as 4 bytes 251 // and as large as 8 KB. 252}; 253 254// The number of blocks stored by a child entry. 255const int kNumSparseBits = 1024; 256COMPILE_ASSERT(sizeof(SparseData) == sizeof(SparseHeader) + kNumSparseBits / 8, 257 Invalid_SparseData_bitmap); 258 259} // namespace disk_cache 260 261#endif // NET_DISK_CACHE_DISK_FORMAT_H_ 262