Disk cache v3: The main index table.

net/disk_cache/v3/disk_format_v3.h

Index: net/disk_cache/v3/disk_format_v3.h
===================================================================
--- net/disk_cache/v3/disk_format_v3.h	(revision 235026)
+++ net/disk_cache/v3/disk_format_v3.h	(working copy)
@@ -37,6 +37,10 @@
 // internal structures are modified, so it is possible to detect (most of the
 // time) when the process dies in the middle of an update. There are dedicated
 // backup files for cache bitmaps, used to detect entries out of date.
+//
+// Although cache files are to be consumed on the same machine that creates
+// them, if files are to be moved accross machines, little endian storage is
+// assumed.
 
 #ifndef NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_
 #define NET_DISK_CACHE_V3_DISK_FORMAT_V3_H_
@@ -46,14 +50,15 @@
 
 namespace disk_cache {
 
-const int kBaseTableLen = 0x10000;
+const int kBaseTableLen = 0x400;
 const uint32 kIndexMagicV3 = 0xC103CAC3;
 const uint32 kVersion3 = 0x30000;  // Version 3.0.
 
 // Flags for a given cache.
 enum CacheFlags {
-  CACHE_EVICTION_2 = 1,      // Keep multiple lists for eviction.
-  CACHE_EVICTED = 1 << 1     // Already evicted at least one entry.
+  SMALL_CACHE = 1 << 0,       // See IndexCell.
+  CACHE_EVICTION_2 = 1 << 1,  // Keep multiple lists for eviction.
+  CACHE_EVICTED = 1 << 2      // Already evicted at least one entry.

[Randy Smith (Not in Mondays), 2013/12/26 21:45:49]

nit, suggestion: It's a bit worrisome to see a non-backward compatible change in
a file describing disk format.  I poked around in the code, and as I'm sure you
know, this is fine because CACHE_EVICT* aren't used anywhere.  But is there a
reason not to have the discipline of adding new flags at the end of the enum so
that that type of thing doesn't need to be verified?

(I suppose that strictly speaking you should always bump the version when you
modify anything in the format, and I can completely understand not wanting to do
that during development, and as long as you're in development you're the only
person who'll be inconvenienced by mistakes in this space.  Thus "nit,
suggestion" :-}.  But it does look a bit weird from the outside.)

[rvargas (doing something else), 2013/12/27 19:31:47]

I intend to make 3.0 the version of the file that is released to users (Beta
ideally). Anything before that is not a stable file format, doesn't have users
or even code that can be compiled out of TOT, so we should be free to change
whatever we'd like to without worrying about compatibility.

A flag stating how to read the table should go before one that specifies an
eviction algorithm to be used.

 };
 
 // Header for the master index file.
@@ -119,30 +124,79 @@
 struct IndexCell {
   void Clear() { memset(this, 0, sizeof(*this)); }
 
-  uint64      address : 22;
-  uint64      hash : 18;
-  uint64      timestamp : 20;
-  uint64      reuse : 4;
-  uint8       state : 3;
-  uint8       group : 3;
-  uint8       sum : 2;
+  // A cell is a 9 byte bit-field that stores 7 values:
+  //   address : 22 bits
+  //   hash : 18 bits
+  //   timestamp : 20 bits
+  //   reuse : 4 bits
+  //   state : 3 bits
+  //   group : 3 bits
+  //   sum : 2 bits
+  // The actual layout is as follows:
+  //
+  // first_part (low order 32 bits):
+  //   0000 0000 0011 1111 1111 1111 1111 1111 : address
+  //   1111 1111 1100 0000 0000 0000 0000 0000 : hash
+  //
+  // first_part (high order 32 bits):
+  //   0000 0000 0000 0000 0000 0000 1111 1111 : hash
+  //   0000 1111 1111 1111 1111 1111 0000 0000 : timestamp
+  //   1111 0000 0000 0000 0000 0000 0000 0000 : reuse
+  //
+  // last_part:
+  //   0000 0111 : state
+  //   0011 1000 : group
+  //   1100 0000 : sum
+  //
+  // The small-cache version of the format moves some bits from the address to
+  // the hash fileds, like so:
+  //   address : 16 bits
+  //   hash : 24 bits
+  //
+  // first_part (low order 32 bits):
+  //   0000 0000 0000 0000 1111 1111 1111 1111 : address
+  //   1111 1111 1111 1111 0000 0000 0000 0000 : hash
+  //
+  // The actual bit distribution between address and hash is determined by the
+  // table size (IndexHeaderV3.table_len). Tables smaller than 65536 entries
+  // use the small-cache version; after that size, caches should have the
+  // SMALL_CACHE flag cleared.
+  //
+  // To locate a given entry after recovering the address from the cell, the
+  // file type and file number are appended (see disk_cache/addr.h). For a large
+  // table only the file type is implied; for a small table, the file number
+  // is also implied, and it should be the first file for that type of entry,
+  // as determined by the EntryGroup (two files in total, one for active entries
+  // and another one for evicted entries).
+  //
+  // For example, a small table may store something like 0x1234 as the address
+  // field. That means it stores the entry number 0x1234. If that record belongs
+  // to a deleted entry, the regular cache address may look something like
+  //     BLOCK_EVICTED + 1 block + file number 6 + entry number 0x1234
+  //     so Addr = 0xf0061234
+  //
+  // If that same Addr is stored on a large table, the address field would be
+  // 0x61234
+
+  uint64      first_part;
+  uint8       last_part;
 };
 COMPILE_ASSERT(sizeof(IndexCell) == 9, bad_IndexCell);
 
+const int kCellsPerBucket = 4;
 struct IndexBucket {
-  IndexCell   cells[4];
+  IndexCell   cells[kCellsPerBucket];
   int32       next;
-  uint32      hash : 24;      // The last byte is only defined for buckets of
-  uint32      reserved : 8;   // the extra table.
+  uint32      hash;  // The high order byte is reserved (should be zero).
 };
 COMPILE_ASSERT(sizeof(IndexBucket) == 44, bad_IndexBucket);
-const int kBytesPerCell = 44 / 4;
+const int kBytesPerCell = 44 / kCellsPerBucket;
 
 // The main cache index. Backed by a file named index_tb1.
 // The extra table (index_tb2) has a similar format, but different size.
 struct Index {
   // Default size. Actual size controlled by header.table_len.
-  IndexBucket table[kBaseTableLen / 4];
+  IndexBucket table[kBaseTableLen / kCellsPerBucket];
 };
 #pragma pack(pop)