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// Although cache files are to be consumed on the same machine that creates 42// them, if files are to be moved accross machines, little endian storage is 43// assumed. 44 45#ifndef NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_ 46#define NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_ 47 48#include "base/basictypes.h" 49#include "net/disk_cache/blockfile/disk_format_base.h" 50 51namespace disk_cache { 52 53const int kBaseTableLen = 0x400; 54const uint32 kIndexMagicV3 = 0xC103CAC3; 55const uint32 kVersion3 = 0x30000; // Version 3.0. 56 57// Flags for a given cache. 58enum CacheFlags { 59 SMALL_CACHE = 1 << 0, // See IndexCell. 60 CACHE_EVICTION_2 = 1 << 1, // Keep multiple lists for eviction. 61 CACHE_EVICTED = 1 << 2 // Already evicted at least one entry. 62}; 63 64// Header for the master index file. 65struct IndexHeaderV3 { 66 uint32 magic; 67 uint32 version; 68 int32 num_entries; // Number of entries currently stored. 69 int32 num_bytes; // Total size of the stored data. 70 int32 last_file; // Last external file created. 71 int32 reserved1; 72 CacheAddr stats; // Storage for usage data. 73 int32 table_len; // Actual size of the table. 74 int32 crash; // Signals a previous crash. 75 int32 experiment; // Id of an ongoing test. 76 int32 max_bytes; // Total maximum size of the stored data. 77 uint32 flags; 78 int32 used_cells; 79 int32 max_bucket; 80 uint64 create_time; // Creation time for this set of files. 81 uint64 base_time; // Current base for timestamps. 82 uint64 old_time; // Previous time used for timestamps. 83 int32 max_block_file; 84 int32 num_no_use_entries; 85 int32 num_low_use_entries; 86 int32 num_high_use_entries; 87 int32 reserved; 88 int32 num_evicted_entries; 89 int32 pad[6]; 90}; 91 92const int kBaseBitmapBytes = 3968; 93// The IndexBitmap is directly saved to a file named index. The file grows in 94// page increments (4096 bytes), but all bits don't have to be in use at any 95// given time. The required file size can be computed from header.table_len. 96struct IndexBitmap { 97 IndexHeaderV3 header; 98 uint32 bitmap[kBaseBitmapBytes / 4]; // First page of the bitmap. 99}; 100COMPILE_ASSERT(sizeof(IndexBitmap) == 4096, bad_IndexHeader); 101 102// Possible states for a given entry. 103enum EntryState { 104 ENTRY_FREE = 0, // Available slot. 105 ENTRY_NEW, // The entry is being created. 106 ENTRY_OPEN, // The entry is being accessed. 107 ENTRY_MODIFIED, // The entry is being modified. 108 ENTRY_DELETED, // The entry is being deleted. 109 ENTRY_FIXING, // Inconsistent state. The entry is being verified. 110 ENTRY_USED // The slot is in use (entry is present). 111}; 112COMPILE_ASSERT(ENTRY_USED <= 7, state_uses_3_bits); 113 114enum EntryGroup { 115 ENTRY_NO_USE = 0, // The entry has not been reused. 116 ENTRY_LOW_USE, // The entry has low reuse. 117 ENTRY_HIGH_USE, // The entry has high reuse. 118 ENTRY_RESERVED, // Reserved for future use. 119 ENTRY_EVICTED // The entry was deleted. 120}; 121COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits); 122 123#pragma pack(push, 1) 124struct IndexCell { 125 void Clear() { memset(this, 0, sizeof(*this)); } 126 127 // A cell is a 9 byte bit-field that stores 7 values: 128 // location : 22 bits 129 // id : 18 bits 130 // timestamp : 20 bits 131 // reuse : 4 bits 132 // state : 3 bits 133 // group : 3 bits 134 // sum : 2 bits 135 // The id is derived from the full hash of the entry. 136 // 137 // The actual layout is as follows: 138 // 139 // first_part (low order 32 bits): 140 // 0000 0000 0011 1111 1111 1111 1111 1111 : location 141 // 1111 1111 1100 0000 0000 0000 0000 0000 : id 142 // 143 // first_part (high order 32 bits): 144 // 0000 0000 0000 0000 0000 0000 1111 1111 : id 145 // 0000 1111 1111 1111 1111 1111 0000 0000 : timestamp 146 // 1111 0000 0000 0000 0000 0000 0000 0000 : reuse 147 // 148 // last_part: 149 // 0000 0111 : state 150 // 0011 1000 : group 151 // 1100 0000 : sum 152 // 153 // The small-cache version of the format moves some bits from the location to 154 // the id fileds, like so: 155 // location : 16 bits 156 // id : 24 bits 157 // 158 // first_part (low order 32 bits): 159 // 0000 0000 0000 0000 1111 1111 1111 1111 : location 160 // 1111 1111 1111 1111 0000 0000 0000 0000 : id 161 // 162 // The actual bit distribution between location and id is determined by the 163 // table size (IndexHeaderV3.table_len). Tables smaller than 65536 entries 164 // use the small-cache version; after that size, caches should have the 165 // SMALL_CACHE flag cleared. 166 // 167 // To locate a given entry after recovering the location from the cell, the 168 // file type and file number are appended (see disk_cache/addr.h). For a large 169 // table only the file type is implied; for a small table, the file number 170 // is also implied, and it should be the first file for that type of entry, 171 // as determined by the EntryGroup (two files in total, one for active entries 172 // and another one for evicted entries). 173 // 174 // For example, a small table may store something like 0x1234 as the location 175 // field. That means it stores the entry number 0x1234. If that record belongs 176 // to a deleted entry, the regular cache address may look something like 177 // BLOCK_EVICTED + 1 block + file number 6 + entry number 0x1234 178 // so Addr = 0xf0061234 179 // 180 // If that same Addr is stored on a large table, the location field would be 181 // 0x61234 182 183 uint64 first_part; 184 uint8 last_part; 185}; 186COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell); 187 188const int kCellsPerBucket = 4; 189struct IndexBucket { 190 IndexCell cells[kCellsPerBucket]; 191 int32 next; 192 uint32 hash; // The high order byte is reserved (should be zero). 193}; 194COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket); 195const int kBytesPerCell = 44 / kCellsPerBucket; 196 197// The main cache index. Backed by a file named index_tb1. 198// The extra table (index_tb2) has a similar format, but different size. 199struct Index { 200 // Default size. Actual size controlled by header.table_len. 201 IndexBucket table[kBaseTableLen / kCellsPerBucket]; 202}; 203#pragma pack(pop) 204 205// Flags that can be applied to an entry. 206enum EntryFlags { 207 PARENT_ENTRY = 1, // This entry has children (sparse) entries. 208 CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. 209}; 210 211struct EntryRecord { 212 uint32 hash; 213 uint32 pad1; 214 uint8 reuse_count; 215 uint8 refetch_count; 216 int8 state; // Current EntryState. 217 uint8 flags; // Any combination of EntryFlags. 218 int32 key_len; 219 int32 data_size[4]; // We can store up to 4 data streams for each 220 CacheAddr data_addr[4]; // entry. 221 uint32 data_hash[4]; 222 uint64 creation_time; 223 uint64 last_modified_time; 224 uint64 last_access_time; 225 int32 pad[3]; 226 uint32 self_hash; 227}; 228COMPILE_ASSERT(sizeof(EntryRecord) == 104, bad_EntryRecord); 229 230struct ShortEntryRecord { 231 uint32 hash; 232 uint32 pad1; 233 uint8 reuse_count; 234 uint8 refetch_count; 235 int8 state; // Current EntryState. 236 uint8 flags; 237 int32 key_len; 238 uint64 last_access_time; 239 uint32 long_hash[5]; 240 uint32 self_hash; 241}; 242COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord); 243 244} // namespace disk_cache 245 246#endif // NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_ 247