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)
45a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#ifndef NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_H_
46a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#define NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_H_
475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h"
495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "net/base/net_export.h"
50a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/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)
153a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#endif  // NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_H_
154