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

net/disk_cache/disk_format.h

-// 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.
 
 // The cache is stored on disk as a collection of block-files, plus an index
 // file plus a collection of external files.
 //
 // Any data blob bigger than kMaxBlockSize (net/addr.h) will be stored on a
 // separate file named f_xxx where x is a hexadecimal number. Shorter data will
 // be stored as a series of blocks on a block-file. In any case, CacheAddr
 // represents the address of the data inside the cache.
@@ skipping 171 matching lines @@
   AllocBitmap     allocation_map;
   BlockFileHeader() {
     memset(this, 0, sizeof(BlockFileHeader));
     magic = kBlockMagic;
     version = kCurrentVersion;
   };
 };
 
 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_