15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The cache is stored on disk as a collection of block-files, plus an index 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// file plus a collection of external files. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 8868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Any data blob bigger than kMaxBlockSize (disk_cache/addr.h) will be stored in 9868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// a separate file named f_xxx where x is a hexadecimal number. Shorter data 10868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// will be stored as a series of blocks on a block-file. In any case, CacheAddr 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// represents the address of the data inside the cache. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The index file is just a simple hash table that maps a particular entry to 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a CacheAddr value. Linking for a given hash bucket is handled internally 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// by the cache entry. 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The last element of the cache is the block-file. A block file is a file 18868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// designed to store blocks of data of a given size. For more details see 19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// disk_cache/disk_format_base.h 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A new cache is initialized with four block files (named data_0 through 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// data_3), each one dedicated to store blocks of a given size. The number at 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the end of the file name is the block file number (in decimal). 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// There are two "special" types of blocks: an entry and a rankings node. An 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// entry keeps track of all the information related to the same cache entry, 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// such as the key, hash value, data pointers etc. A rankings node keeps track 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// of the information that is updated frequently for a given entry, such as its 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// location on the LRU lists, last access time etc. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The files that store internal information for the cache (blocks and index) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// are at least partially memory mapped. They have a location that is signaled 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// every time the internal structures are modified, so it is possible to detect 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (most of the time) when the process dies in the middle of an update. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// In order to prevent dirty data to be used as valid (after a crash), every 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// cache entry has a dirty identifier. Each running instance of the cache keeps 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a separate identifier (maintained on the "this_id" header field) that is used 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// to mark every entry that is created or modified. When the entry is closed, 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and all the data can be trusted, the dirty flag is cleared from the entry. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// When the cache encounters an entry whose identifier is different than the one 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// being currently used, it means that the entry was not properly closed on a 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// previous run, so it is discarded. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef NET_DISK_CACHE_DISK_FORMAT_H_ 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define NET_DISK_CACHE_DISK_FORMAT_H_ 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/base/net_export.h" 50868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "net/disk_cache/disk_format_base.h" 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace disk_cache { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kIndexTablesize = 0x10000; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const uint32 kIndexMagic = 0xC103CAC3; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const uint32 kCurrentVersion = 0x20000; // Version 2.0. 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct LruData { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 pad1[2]; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 filled; // Flag to tell when we filled the cache. 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 sizes[5]; 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr heads[5]; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr tails[5]; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr transaction; // In-flight operation target. 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 operation; // Actual in-flight operation. 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 operation_list; // In-flight operation list. 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 pad2[7]; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Header for the master index file. 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct NET_EXPORT_PRIVATE IndexHeader { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndexHeader(); 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 magic; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 version; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 num_entries; // Number of entries currently stored. 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 num_bytes; // Total size of the stored data. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 last_file; // Last external file created. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 this_id; // Id for all entries being changed (dirty flag). 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr stats; // Storage for usage data. 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 table_len; // Actual size of the table (0 == kIndexTablesize). 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 crash; // Signals a previous crash. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 experiment; // Id of an ongoing test. 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64 create_time; // Creation time for this set of files. 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 pad[52]; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LruData lru; // Eviction control data. 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The structure of the whole index file. 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct Index { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IndexHeader header; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr table[kIndexTablesize]; // Default size. Actual size controlled 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // by header.table_len. 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Main structure for an entry on the backing storage. If the key is longer than 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// what can be stored on this structure, it will be extended on consecutive 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// blocks (adding 256 bytes each time), up to 4 blocks (1024 - 32 - 1 chars). 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// After that point, the whole key will be stored as a data block or external 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// file. 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct EntryStore { 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 hash; // Full hash of the key. 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr next; // Next entry with the same hash or bucket. 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr rankings_node; // Rankings node for this entry. 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 reuse_count; // How often is this entry used. 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 refetch_count; // How often is this fetched from the net. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 state; // Current state. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64 creation_time; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 key_len; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr long_key; // Optional address of a long key. 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 data_size[4]; // We can store up to 4 data streams for each 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr data_addr[4]; // entry. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 flags; // Any combination of EntryFlags. 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 pad[4]; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 self_hash; // The hash of EntryStore up to this point. 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char key[256 - 24 * 4]; // null terminated 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)COMPILE_ASSERT(sizeof(EntryStore) == 256, bad_EntyStore); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int kMaxInternalKeyLength = 4 * sizeof(EntryStore) - 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) offsetof(EntryStore, key) - 1; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Possible states for a given entry. 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)enum EntryState { 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ENTRY_NORMAL = 0, 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ENTRY_EVICTED, // The entry was recently evicted from the cache. 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ENTRY_DOOMED // The entry was doomed. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Flags that can be applied to an entry. 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)enum EntryFlags { 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PARENT_ENTRY = 1, // This entry has children (sparse) entries. 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHILD_ENTRY = 1 << 1 // Child entry that stores sparse data. 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#pragma pack(push, 4) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Rankings information for a given entry. 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct RankingsNode { 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64 last_used; // LRU info. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64 last_modified; // LRU info. 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr next; // LRU list. 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr prev; // LRU list. 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CacheAddr contents; // Address of the EntryStore. 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 dirty; // The entry is being modifyied. 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 self_hash; // RankingsNode's hash. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#pragma pack(pop) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)COMPILE_ASSERT(sizeof(RankingsNode) == 36, bad_RankingsNode); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace disk_cache 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // NET_DISK_CACHE_DISK_FORMAT_H_ 154