1 // Copyright (c) 2011 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 // plus a collection of external files. 7 // 8 // Any data blob bigger than kMaxBlockSize (disk_cache/addr.h) will be stored in 9 // a separate file named f_xxx where x is a hexadecimal number. Shorter data 10 // will 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 is actually a collection of four files that store a hash table with 14 // allocation bitmaps and backup data. Hash collisions are handled directly by 15 // the table, which from some point of view behaves like a 4-way associative 16 // cache with overflow buckets (so not really open addressing). 17 // 18 // Basically the hash table is a collection of buckets. The first part of the 19 // table has a fixed number of buckets and it is directly addressed by the hash, 20 // while the second part of the table (stored on a second file) has a variable 21 // number of buckets. Each bucket stores up to four cells (each cell represents 22 // a possibl entry). The index bitmap tracks the state of individual cells. 23 // 24 // The last element of the cache is the block-file. A block file is a file 25 // designed to store blocks of data of a given size. For more details see 26 // disk_cache/disk_format_base.h 27 // 28 // A new cache is initialized with a set of block files (named data_0 through 29 // data_6), each one dedicated to store blocks of a given size or function. The 30 // number at the end of the file name is the block file number (in decimal). 31 // 32 // There are three "special" types of blocks: normal entries, evicted entries 33 // and control data for external files. 34 // 35 // The files that store internal information for the cache (blocks and index) 36 // are memory mapped. They have a location that is signaled every time the 37 // internal structures are modified, so it is possible to detect (most of the 38 // time) when the process dies in the middle of an update. There are dedicated 39 // backup files for cache bitmaps, used to detect entries out of date. 40 41 #ifndef NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ 42 #define NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ 43 44 #include "base/basictypes.h" 45 #include "net/disk_cache/disk_format_base.h" 46 47 namespace disk_cache { 48 49 const int kBaseTableLen = 0x10000; 50 const uint32 kIndexMagicV3 = 0xC103CAC3; 51 const uint32 kVersion3 = 0x30000; // Version 3.0. 52 53 // Flags for a given cache. 54 enum CacheFlags { 55 CACHE_EVICTION_2 = 1, // Keep multiple lists for eviction. 56 CACHE_EVICTED = 1 << 1 // Already evicted at least one entry. 57 }; 58 59 // Header for the master index file. 60 struct IndexHeaderV3 { 61 uint32 magic; 62 uint32 version; 63 int32 num_entries; // Number of entries currently stored. 64 int32 num_bytes; // Total size of the stored data. 65 int32 last_file; // Last external file created. 66 int32 reserved1; 67 CacheAddr stats; // Storage for usage data. 68 int32 table_len; // Actual size of the table. 69 int32 crash; // Signals a previous crash. 70 int32 experiment; // Id of an ongoing test. 71 int32 max_bytes; // Total maximum size of the stored data. 72 uint32 flags; 73 int32 used_cells; 74 int32 max_bucket; 75 uint64 create_time; // Creation time for this set of files. 76 uint64 base_time; // Current base for timestamps. 77 uint64 old_time; // Previous time used for timestamps. 78 int32 max_block_file; 79 int32 num_no_use_entries; 80 int32 num_low_use_entries; 81 int32 num_high_use_entries; 82 int32 reserved; 83 int32 num_evicted_entries; 84 int32 pad[6]; 85 }; 86 87 const int kBaseBitmapBytes = 3968; 88 // The IndexBitmap is directly saved to a file named index. The file grows in 89 // page increments (4096 bytes), but all bits don't have to be in use at any 90 // given time. The required file size can be computed from header.table_len. 91 struct IndexBitmap { 92 IndexHeaderV3 header; 93 uint32 bitmap[kBaseBitmapBytes / 4]; // First page of the bitmap. 94 }; 95 COMPILE_ASSERT(sizeof(IndexBitmap) == 4096, bad_IndexHeader); 96 97 // Possible states for a given entry. 98 enum EntryState { 99 ENTRY_FREE = 0, // Available slot. 100 ENTRY_NEW, // The entry is being created. 101 ENTRY_OPEN, // The entry is being accessed. 102 ENTRY_MODIFIED, // The entry is being modified. 103 ENTRY_DELETED, // The entry is being deleted. 104 ENTRY_FIXING, // Inconsistent state. The entry is being verified. 105 ENTRY_USED // The slot is in use (entry is present). 106 }; 107 COMPILE_ASSERT(ENTRY_USED <= 7, state_uses_3_bits); 108 109 enum EntryGroup { 110 ENTRY_NO_USE = 0, // The entry has not been reused. 111 ENTRY_LOW_USE, // The entry has low reuse. 112 ENTRY_HIGH_USE, // The entry has high reuse. 113 ENTRY_RESERVED, // Reserved for future use. 114 ENTRY_EVICTED // The entry was deleted. 115 }; 116 COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits); 117 118 #pragma pack(push, 1) 119 struct IndexCell { 120 void Clear() { memset(this, 0, sizeof(*this)); } 121 122 uint64 address : 22; 123 uint64 hash : 18; 124 uint64 timestamp : 20; 125 uint64 reuse : 4; 126 uint8 state : 3; 127 uint8 group : 3; 128 uint8 sum : 2; 129 }; 130 COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell); 131 132 struct IndexBucket { 133 IndexCell cells[4]; 134 int32 next; 135 uint32 hash : 24; // The last byte is only defined for buckets of 136 uint32 reserved : 8; // the extra table. 137 }; 138 COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket); 139 const int kBytesPerCell = 44 / 4; 140 141 // The main cache index. Backed by a file named index_tb1. 142 // The extra table (index_tb2) has a similar format, but different size. 143 struct Index { 144 // Default size. Actual size controlled by header.table_len. 145 IndexBucket table[kBaseTableLen / 4]; 146 }; 147 #pragma pack(pop) 148 149 // Flags that can be applied to an entry. 150 enum EntryFlags { 151 PARENT_ENTRY = 1, // This entry has children (sparse) entries. 152 CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. 153 }; 154 155 struct EntryRecord { 156 uint32 hash; 157 uint32 pad1; 158 uint8 reuse_count; 159 uint8 refetch_count; 160 int8 state; // Current EntryState. 161 uint8 flags; // Any combination of EntryFlags. 162 int32 key_len; 163 int32 data_size[4]; // We can store up to 4 data streams for each 164 CacheAddr data_addr[4]; // entry. 165 uint32 data_hash[4]; 166 uint64 creation_time; 167 uint64 last_modified_time; 168 uint64 last_access_time; 169 int32 pad[3]; 170 uint32 self_hash; 171 }; 172 COMPILE_ASSERT(sizeof(EntryRecord) == 104, bad_EntryRecord); 173 174 struct ShortEntryRecord { 175 uint32 hash; 176 uint32 pad1; 177 uint8 reuse_count; 178 uint8 refetch_count; 179 int8 state; // Current EntryState. 180 uint8 flags; 181 int32 key_len; 182 uint64 last_access_time; 183 uint32 long_hash[5]; 184 uint32 self_hash; 185 }; 186 COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord); 187 188 } // namespace disk_cache 189 190 #endif // NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_ 191
