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 61 namespace disk_cache { 62 63 typedef uint32 CacheAddr; 64 65 const int kIndexTablesize = 0x10000; 66 const uint32 kIndexMagic = 0xC103CAC3; 67 const uint32 kCurrentVersion = 0x20000; // Version 2.0. 68 69 struct 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. 82 struct 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. 101 struct 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. 112 struct 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 129 COMPILE_ASSERT(sizeof(EntryStore) == 256, bad_EntyStore); 130 const int kMaxInternalKeyLength = 4 * sizeof(EntryStore) - 131 offsetof(EntryStore, key) - 1; 132 133 // Possible states for a given entry. 134 enum 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. 141 enum 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. 148 struct 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 159 COMPILE_ASSERT(sizeof(RankingsNode) == 36, bad_RankingsNode); 160 161 const uint32 kBlockMagic = 0xC104CAC3; 162 const int kBlockHeaderSize = 8192; // Two pages: almost 64k entries 163 const int kMaxBlocks = (kBlockHeaderSize - 80) * 8; 164 165 // Bitmap to track used blocks on a block-file. 166 typedef 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: 176 struct 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 193 COMPILE_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. 234 struct 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. 245 struct 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. 255 const int kNumSparseBits = 1024; 256 COMPILE_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