src/net/disk_cache/v3/disk_format_v3.h

   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_