net/disk_cache/blockfile/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 // 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
  51 namespace disk_cache {
  52
  53 const int kBaseTableLen = 0x400;
  54 const uint32 kIndexMagicV3 = 0xC103CAC3;
  55 const uint32 kVersion3 = 0x30000;  // Version 3.0.
  56
  57 // Flags for a given cache.
  58 enum 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.
  65 struct 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
  92 const 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.
  96 struct IndexBitmap {
  97   IndexHeaderV3   header;
  98   uint32          bitmap[kBaseBitmapBytes / 4];  // First page of the bitmap.
  99 };
 100 static_assert(sizeof(IndexBitmap) == 4096, "bad IndexHeader");
 101
 102 // Possible states for a given entry.
 103 enum 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 };
 112 static_assert(ENTRY_USED <= 7, "state uses 3 bits");
 113
 114 enum 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 };
 121 static_assert(ENTRY_USED <= 7, "group uses 3 bits");
 122
 123 #pragma pack(push, 1)
 124 struct 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 };
 186 static_assert(sizeof(IndexCell) == 9, "bad IndexCell");
 187
 188 const int kCellsPerBucket = 4;
 189 struct IndexBucket {
 190   IndexCell   cells[kCellsPerBucket];
 191   int32       next;
 192   uint32      hash;  // The high order byte is reserved (should be zero).
 193 };
 194 static_assert(sizeof(IndexBucket) == 44, "bad IndexBucket");
 195 const 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.
 199 struct 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.
 206 enum EntryFlags {
 207   PARENT_ENTRY = 1,         // This entry has children (sparse) entries.
 208   CHILD_ENTRY = 1 << 1      // Child entry that stores sparse data.
 209 };
 210
 211 struct 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 };
 228 static_assert(sizeof(EntryRecord) == 104, "bad EntryRecord");
 229
 230 struct 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 };
 242 static_assert(sizeof(ShortEntryRecord) == 48, "bad ShortEntryRecord");
 243
 244 }  // namespace disk_cache
 245
 246 #endif  // NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_