Disk cache: First pass to add support for sparse entries....

net/disk_cache/disk_format.h

Index: net/disk_cache/disk_format.h
===================================================================
--- net/disk_cache/disk_format.h	(revision 18456)
+++ net/disk_cache/disk_format.h	(working copy)
@@ -1,4 +1,4 @@
-// Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
+// Copyright (c) 2006-2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -190,6 +190,65 @@
 
 COMPILE_ASSERT(sizeof(BlockFileHeader) == kBlockHeaderSize, bad_header);
 
+// Sparse data support:
+// We keep a two level hierarchy to enable sparse data for an entry: the first
+// level consists of using separate "child" entries to store ranges of 1 MB,
+// and the second level stores blocks of 1 KB inside each child entry.
+//
+// Whenever we need to access a particular sparse offset, we first locate the
+// child entry that stores that offset, so we discard the 20 least significant
+// bits of the offset, and end up with the child id. For instance, the child id
+// to store the first megabyte is 0, and the child that should store offset
+// 0x410000 has an id of 4.
+//
+// The child entry is stored the same way as any other entry, so it also has a
+// name (key). The key includes a signature to be able to identify children
+// created for different generations of the same resource. In other words, given
+// that a given sparse entry can have a large number of child entries, and the
+// resource can be invalidated and replaced with a new version at any time, it
+// is important to be sure that a given child actually belongs to certain entry.
+//
+// The full name of a child entry is composed with a prefix ("Range_"), and two
+// hexadecimal 64-bit numbers at the end, separated by semicolons. The first
+// number is the signature of the parent key, and the second number is the child
+// id as described previously. The signature itself is also stored internally by
+// the child and the parent entries. For example, a sparse entry with a key of
+// "sparse entry name", and a signature of 0x052AF76, may have a child entry
+// named "Range_sparse entry name:052af76:4", which stores data in the range
+// 0x400000 to 0x4FFFFF.
+//
+// Each child entry keeps track of all the 1 KB blocks that have been written
+// to the entry, but being a regular entry, it will happily return zeros for any
+// read that spans data not written before. The actual sparse data is stored in
+// one of the data streams of the child entry (at index 1), while the control
+// information is stored in another stream (at index 2), both by parents and
+// the children.
+
+// This structure contains the control information for parent and child entries.
+// It is stored at offset 0 of the data stream with index 2.
+struct SparseHeader {
+  int64 signature;          // The parent and children signature.
+  uint32 magic;             // Structure identifier (equal to kIndexMagic).
+  int32 parent_key_len;     // Key length for the parent entry.
+  int32 dummy[4];
+};
+
+// The SparseHeader will be followed by a bitmap, as described by this
+// structure.
+struct SparseData {
+  SparseHeader header;
+  uint32 bitmap[32];        // Bitmap representation of known children (if this
+                            // is a parent entry), or used blocks (for child
+                            // entries. The size is fixed for child entries but
+                            // not for parents; it can be as small as 4 bytes
+                            // and as large as 8 KB.
+};
+
+// The number of blocks stored by a child entry.
+const int kNumSparseBits = 1024;
+COMPILE_ASSERT(sizeof(SparseData) == sizeof(SparseHeader) + kNumSparseBits / 8,
+               Invalid_SparseData_bitmap);
+
 }  // namespace disk_cache
 
 #endif  // NET_DISK_CACHE_DISK_FORMAT_H_