1868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved.
2868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be
3868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// found in the LICENSE file.
4868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
5868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The cache is stored on disk as a collection of block-files, plus an index
67d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// plus a collection of external files.
7868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
87d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// Any data blob bigger than kMaxBlockSize (disk_cache/addr.h) will be stored in
97d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// a separate file named f_xxx where x is a hexadecimal number. Shorter data
107d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// will be stored as a series of blocks on a block-file. In any case, CacheAddr
11868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// represents the address of the data inside the cache.
12868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// The index is actually a collection of four files that store a hash table with
147d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// allocation bitmaps and backup data. Hash collisions are handled directly by
157d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// the table, which from some point of view behaves like a 4-way associative
167d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// cache with overflow buckets (so not really open addressing).
177d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)//
187d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// Basically the hash table is a collection of buckets. The first part of the
197d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// table has a fixed number of buckets and it is directly addressed by the hash,
207d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// while the second part of the table (stored on a second file) has a variable
217d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// number of buckets. Each bucket stores up to four cells (each cell represents
227d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// a possibl entry). The index bitmap tracks the state of individual cells.
23868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
24868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The last element of the cache is the block-file. A block file is a file
257d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// designed to store blocks of data of a given size. For more details see
267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// disk_cache/disk_format_base.h
27868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
287d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// A new cache is initialized with a set of block files (named data_0 through
297d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// data_6), each one dedicated to store blocks of a given size or function. The
307d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// number at the end of the file name is the block file number (in decimal).
31868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
327d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// There are three "special" types of blocks: normal entries, evicted entries
337d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// and control data for external files.
34868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
35868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The files that store internal information for the cache (blocks and index)
367d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// are memory mapped. They have a location that is signaled every time the
377d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// internal structures are modified, so it is possible to detect (most of the
387d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// time) when the process dies in the middle of an update. There are dedicated
397d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// backup files for cache bitmaps, used to detect entries out of date.
405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)//
415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// Although cache files are to be consumed on the same machine that creates
425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// them, if files are to be moved accross machines, little endian storage is
435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// assumed.
447d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)
45a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#ifndef NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_
46a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#define NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_
47868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
48868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/basictypes.h"
49a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#include "net/disk_cache/blockfile/disk_format_base.h"
50868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
51868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)namespace disk_cache {
52868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kBaseTableLen = 0x400;
547d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)const uint32 kIndexMagicV3 = 0xC103CAC3;
557d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)const uint32 kVersion3 = 0x30000;  // Version 3.0.
56868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
577d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// Flags for a given cache.
587d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)enum CacheFlags {
595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  SMALL_CACHE = 1 << 0,       // See IndexCell.
605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  CACHE_EVICTION_2 = 1 << 1,  // Keep multiple lists for eviction.
615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  CACHE_EVICTED = 1 << 2      // Already evicted at least one entry.
627d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)};
63868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
647d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// Header for the master index file.
657d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct IndexHeaderV3 {
66868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  uint32      magic;
67868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  uint32      version;
68868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  int32       num_entries;   // Number of entries currently stored.
69868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  int32       num_bytes;     // Total size of the stored data.
70868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  int32       last_file;     // Last external file created.
717d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       reserved1;
72868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  CacheAddr   stats;         // Storage for usage data.
737d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       table_len;     // Actual size of the table.
74868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  int32       crash;         // Signals a previous crash.
75868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  int32       experiment;    // Id of an ongoing test.
767d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       max_bytes;     // Total maximum size of the stored data.
777d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      flags;
787d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       used_cells;
797d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       max_bucket;
80868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  uint64      create_time;   // Creation time for this set of files.
817d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint64      base_time;     // Current base for timestamps.
827d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint64      old_time;      // Previous time used for timestamps.
837d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       max_block_file;
847d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       num_no_use_entries;
857d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       num_low_use_entries;
867d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       num_high_use_entries;
877d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       reserved;
887d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       num_evicted_entries;
897d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       pad[6];
90868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)};
91868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
927d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)const int kBaseBitmapBytes = 3968;
937d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// The IndexBitmap is directly saved to a file named index. The file grows in
947d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// page increments (4096 bytes), but all bits don't have to be in use at any
957d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// given time. The required file size can be computed from header.table_len.
967d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct IndexBitmap {
977d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  IndexHeaderV3   header;
987d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32          bitmap[kBaseBitmapBytes / 4];  // First page of the bitmap.
99868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)};
1007d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)COMPILE_ASSERT(sizeof(IndexBitmap) == 4096, bad_IndexHeader);
101868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
102868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Possible states for a given entry.
103868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)enum EntryState {
1047d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_FREE = 0,   // Available slot.
1057d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_NEW,        // The entry is being created.
1067d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_OPEN,       // The entry is being accessed.
1077d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_MODIFIED,   // The entry is being modified.
1087d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_DELETED,    // The entry is being deleted.
1097d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_FIXING,     // Inconsistent state. The entry is being verified.
1107d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_USED        // The slot is in use (entry is present).
1117d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)};
1127d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)COMPILE_ASSERT(ENTRY_USED <= 7, state_uses_3_bits);
1137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)
1147d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)enum EntryGroup {
1157d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_NO_USE = 0,   // The entry has not been reused.
1167d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_LOW_USE,      // The entry has low reuse.
1177d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_HIGH_USE,     // The entry has high reuse.
1187d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_RESERVED,     // Reserved for future use.
1197d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  ENTRY_EVICTED       // The entry was deleted.
120868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)};
1217d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)COMPILE_ASSERT(ENTRY_USED <= 7, group_uses_3_bits);
1227d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)
1237d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#pragma pack(push, 1)
1247d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct IndexCell {
1257d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  void Clear() { memset(this, 0, sizeof(*this)); }
1267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)
1275d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // A cell is a 9 byte bit-field that stores 7 values:
1285d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   location : 22 bits
1295d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   id : 18 bits
1305d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   timestamp : 20 bits
1315d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   reuse : 4 bits
1325d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   state : 3 bits
1335d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   group : 3 bits
1345d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   sum : 2 bits
1355d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // The id is derived from the full hash of the entry.
1365d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1375d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // The actual layout is as follows:
1385d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1395d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // first_part (low order 32 bits):
1405d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   0000 0000 0011 1111 1111 1111 1111 1111 : location
1415d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   1111 1111 1100 0000 0000 0000 0000 0000 : id
1425d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1435d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // first_part (high order 32 bits):
1445d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   0000 0000 0000 0000 0000 0000 1111 1111 : id
1455d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   0000 1111 1111 1111 1111 1111 0000 0000 : timestamp
1465d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   1111 0000 0000 0000 0000 0000 0000 0000 : reuse
1475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // last_part:
1495d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   0000 0111 : state
1505d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   0011 1000 : group
1515d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   1100 0000 : sum
1525d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1535d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // The small-cache version of the format moves some bits from the location to
1545d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // the id fileds, like so:
1555d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   location : 16 bits
1565d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   id : 24 bits
1575d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1585d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // first_part (low order 32 bits):
1595d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   0000 0000 0000 0000 1111 1111 1111 1111 : location
1605d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //   1111 1111 1111 1111 0000 0000 0000 0000 : id
1615d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1625d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // The actual bit distribution between location and id is determined by the
1635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // table size (IndexHeaderV3.table_len). Tables smaller than 65536 entries
1645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // use the small-cache version; after that size, caches should have the
1655d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // SMALL_CACHE flag cleared.
1665d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1675d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // To locate a given entry after recovering the location from the cell, the
1685d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // file type and file number are appended (see disk_cache/addr.h). For a large
1695d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // table only the file type is implied; for a small table, the file number
1705d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // is also implied, and it should be the first file for that type of entry,
1715d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // as determined by the EntryGroup (two files in total, one for active entries
1725d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // and another one for evicted entries).
1735d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1745d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // For example, a small table may store something like 0x1234 as the location
1755d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // field. That means it stores the entry number 0x1234. If that record belongs
1765d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // to a deleted entry, the regular cache address may look something like
1775d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //     BLOCK_EVICTED + 1 block + file number 6 + entry number 0x1234
1785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //     so Addr = 0xf0061234
1795d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  //
1805d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // If that same Addr is stored on a large table, the location field would be
1815d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  // 0x61234
1825d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)
1835d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  uint64      first_part;
1845d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  uint8       last_part;
1857d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)};
1867d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell);
1877d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)
1885d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kCellsPerBucket = 4;
1897d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct IndexBucket {
1905d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  IndexCell   cells[kCellsPerBucket];
1917d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       next;
1925d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  uint32      hash;  // The high order byte is reserved (should be zero).
1937d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)};
1947d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket);
1955d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)const int kBytesPerCell = 44 / kCellsPerBucket;
1967d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)
1977d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// The main cache index. Backed by a file named index_tb1.
1987d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// The extra table (index_tb2) has a similar format, but different size.
1997d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct Index {
2007d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  // Default size. Actual size controlled by header.table_len.
2015d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)  IndexBucket table[kBaseTableLen / kCellsPerBucket];
2027d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)};
2037d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)#pragma pack(pop)
204868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
205868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Flags that can be applied to an entry.
206868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)enum EntryFlags {
207868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  PARENT_ENTRY = 1,         // This entry has children (sparse) entries.
208868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  CHILD_ENTRY = 1 << 1      // Child entry that stores sparse data.
209868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)};
210868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
2117d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct EntryRecord {
2127d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      hash;
2137d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      pad1;
2147d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint8       reuse_count;
2157d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint8       refetch_count;
2167d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int8        state;              // Current EntryState.
2177d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint8       flags;              // Any combination of EntryFlags.
218868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  int32       key_len;
219868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  int32       data_size[4];       // We can store up to 4 data streams for each
220868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  CacheAddr   data_addr[4];       // entry.
2217d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      data_hash[4];
2227d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint64      creation_time;
2237d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint64      last_modified_time;
2247d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint64      last_access_time;
2257d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       pad[3];
2267d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      self_hash;
227868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)};
2287d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)COMPILE_ASSERT(sizeof(EntryRecord) == 104, bad_EntryRecord);
229868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
2307d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)struct ShortEntryRecord {
2317d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      hash;
2327d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      pad1;
2337d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint8       reuse_count;
2347d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint8       refetch_count;
2357d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int8        state;              // Current EntryState.
2367d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint8       flags;
2377d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  int32       key_len;
2387d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint64      last_access_time;
2397d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      long_hash[5];
2407d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)  uint32      self_hash;
2417d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)};
2427d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)COMPILE_ASSERT(sizeof(ShortEntryRecord) == 48, bad_ShortEntryRecord);
243868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
244868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)}  // namespace disk_cache
245868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
246a1401311d1ab56c4ed0a474bd38c108f75cb0cd9Torne (Richard Coles)#endif  // NET_DISK_CACHE_BLOCKFILE_DISK_FORMAT_V3_H_
247