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

Adding Read/Write support.

BUG=12258
TEST=unittests.

original review: http://codereview.chromium.org/126179

Review URL: http://codereview.chromium.org/132031

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@18772 0039d316-1c4b-4281-b951-d872f2087c98

14 files changed, 1603 insertions, 14 deletions

diff --git a/net/base/io_buffer.cc b/net/base/io_buffer.cc
index c2401ab..db2bffb 100644
--- a/net/base/io_buffer.cc
+++ b/net/base/io_buffer.cc
@@ -12,5 +12,9 @@ IOBuffer::IOBuffer(int buffer_size) {
   DCHECK(buffer_size > 0);
   data_ = new char[buffer_size];
 }
+void ReusedIOBuffer::SetOffset(int offset) {
+  DCHECK(offset > 0 && offset < size_);
+  data_ = base_->data() + offset;
+}
 
 }  // namespace net
diff --git a/net/base/io_buffer.h b/net/base/io_buffer.h
index 122e434..ac79644 100644
--- a/net/base/io_buffer.h
+++ b/net/base/io_buffer.h
@@ -28,15 +28,50 @@ class IOBuffer : public base::RefCountedThreadSafe<IOBuffer> {
   char* data_;
 };
 
+// This version stores the size of the buffer so that the creator of the object
+// doesn't have to keep track of that value.
+// NOTE: This doesn't mean that we want to stop sending the size as an explictit
+// argument to IO functions. Please keep using IOBuffer* for API declarations.
+class IOBufferWithSize : public IOBuffer {
+ public:
+  explicit IOBufferWithSize(int size) : IOBuffer(size), size_(size) {}
+  ~IOBufferWithSize() {}
+
+  int size() const { return size_; }
+
+ private:
+  int size_;
+};
+
+// This version allows the caller to do multiple IO operations reusing a given
+// IOBuffer. We don't own data_, we simply make it point to the buffer of the
+// passed in IOBuffer, plus the desired offset.
+class ReusedIOBuffer : public IOBuffer {
+ public:
+  ReusedIOBuffer(IOBuffer* base, int size)
+      : IOBuffer(base->data()), base_(base), size_(size) {}
+  ~ReusedIOBuffer() {
+    // We don't really own a buffer.
+    data_ = NULL;
+  }
+
+  int size() const { return size_; }
+  void SetOffset(int offset);
+
+ private:
+  scoped_refptr<IOBuffer> base_;
+  int size_;
+};
+
 // This class allows the creation of a temporary IOBuffer that doesn't really
 // own the underlying buffer. Please use this class only as a last resort.
 // A good example is the buffer for a synchronous operation, where we can be
 // sure that nobody is keeping an extra reference to this object so the lifetime
 // of the buffer can be completely managed by its intended owner.
-class WrappedIOBuffer : public net::IOBuffer {
+class WrappedIOBuffer : public IOBuffer {
  public:
   explicit WrappedIOBuffer(const char* data)
-      : net::IOBuffer(const_cast<char*>(data)) {}
+      : IOBuffer(const_cast<char*>(data)) {}
   ~WrappedIOBuffer() {
     data_ = NULL;
   }
diff --git a/net/disk_cache/bitmap.cc b/net/disk_cache/bitmap.cc
new file mode 100644
index 0000000..79606c5
--- /dev/null
+++ b/net/disk_cache/bitmap.cc
@@ -0,0 +1,282 @@
+// Copyright (c) 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.
+
+#include "net/disk_cache/bitmap.h"
+
+#include "base/logging.h"
+
+namespace {
+
+// Returns the number of trailing zeros.
+int FindLSBSetNonZero(uint32 word) {
+  // Get the LSB, put it on the exponent of a 32 bit float and remove the
+  // mantisa and the bias. This code requires IEEE 32 bit float compliance.
+  float f = static_cast<float>(word & -static_cast<int>(word));
+
+  // We use a union to go around strict-aliasing complains.
+  union {
+    float ieee_float;
+    uint32 as_uint;
+  } x;
+
+  x.ieee_float = f;
+  return (x.as_uint >> 23) - 0x7f;
+}
+
+// Returns the index of the first bit set to |value| from |word|. This code
+// assumes that we'll be able to find that bit.
+int FindLSBNonEmpty(uint32 word, bool value) {
+  // If we are looking for 0, negate |word| and look for 1.
+  if (!value)
+    word = ~word;
+
+  return FindLSBSetNonZero(word);
+}
+
+}
+
+namespace disk_cache {
+
+void Bitmap::Resize(int num_bits, bool clear_bits) {
+  DCHECK(alloc_ || !map_);
+  const int old_maxsize = num_bits_;
+  const int old_array_size = array_size_;
+  array_size_ = RequiredArraySize(num_bits);
+
+  if (array_size_ != old_array_size) {
+    uint32* new_map = new uint32[array_size_];
+    // Always clear the unused bits in the last word.
+    new_map[array_size_ - 1] = 0;
+    memcpy(new_map, map_,
+           sizeof(*map_) * std::min(array_size_, old_array_size));
+    if (alloc_)
+      delete[] map_;  // No need to check for NULL.
+    map_ = new_map;
+    alloc_ = true;
+  }
+
+  num_bits_ = num_bits;
+  if (old_maxsize < num_bits_ && clear_bits) {
+    SetRange(old_maxsize, num_bits_, false);
+  }
+}
+
+void Bitmap::Set(int index, bool value) {
+  DCHECK_LT(index, num_bits_);
+  DCHECK_GE(index, 0);
+  const int i = index & (kIntBits - 1);
+  const int j = index / kIntBits;
+  if (value)
+    map_[j] |= (1 << i);
+  else
+    map_[j] &= ~(1 << i);
+}
+
+bool Bitmap::Get(int index) const {
+  DCHECK_LT(index, num_bits_);
+  DCHECK_GE(index, 0);
+  const int i = index & (kIntBits-1);
+  const int j = index / kIntBits;
+  return map_[j] & (1 << i) ? true : false;
+}
+
+void Bitmap::Toggle(int index) {
+  DCHECK_LT(index, num_bits_);
+  DCHECK_GE(index, 0);
+  const int i = index & (kIntBits - 1);
+  const int j = index / kIntBits;
+  map_[j] ^= (1 << i);
+}
+
+void Bitmap::SetMapElement(int array_index, uint32 value) {
+  DCHECK_LT(array_index, array_size_);
+  DCHECK_GE(array_index, 0);
+  map_[array_index] = value;
+}
+
+uint32 Bitmap::GetMapElement(int array_index) const {
+  DCHECK_LT(array_index, array_size_);
+  DCHECK_GE(array_index, 0);
+  return map_[array_index];
+}
+
+void Bitmap::SetMap(const uint32* map, int size) {
+  memcpy(map_, map, std::min(size, array_size_) * sizeof(*map_));
+}
+
+void Bitmap::SetWordBits(int start, int len, bool value) {
+  DCHECK_LT(len, kIntBits);
+  if (!len)
+    return;
+
+  int word = start / kIntBits;
+  int offset = start % kIntBits;
+
+  uint32 to_add = 0xffffffff << len;
+  to_add = (~to_add) << offset;
+  if (value) {
+    map_[word] |= to_add;
+  } else {
+    map_[word] &= ~to_add;
+  }
+}
+
+void Bitmap::SetRange(int begin, int end, bool value) {
+  int start_offset = begin & (kIntBits - 1);
+  if (start_offset) {
+    // Set the bits in the first word.
+    int len = std::min(end - begin, kIntBits - start_offset);
+    SetWordBits(begin, len, value);
+    begin += len;
+  }
+
+  if (begin == end)
+    return;
+
+  // Now set the bits in the last word.
+  int end_offset = end & (kIntBits - 1);
+  end -= end_offset;
+  SetWordBits(end, end_offset, value);
+
+  // Set all the words in the middle.
+  memset(map_ + (begin / kIntBits), (value ? 0xFF : 0x00),
+         ((end / kIntBits) - (begin / kIntBits)) * sizeof(*map_));
+}
+
+// Return true if any bit between begin inclusive and end exclusive
+// is set.  0 <= begin <= end <= bits() is required.
+bool Bitmap::TestRange(int begin, int end, bool value) const {
+  DCHECK_LT(begin, num_bits_);
+  DCHECK_LE(end, num_bits_);
+  DCHECK_LE(begin, end);
+  DCHECK_GE(begin, 0);
+  DCHECK_GE(end, 0);
+
+  // Return false immediately if the range is empty.
+  if (begin >= end || end <= 0)
+    return false;
+
+  // Calculate the indices of the words containing the first and last bits,
+  // along with the positions of the bits within those words.
+  int word = begin / kIntBits;
+  int offset = begin & (kIntBits - 1);
+  int last_word = (end - 1) / kIntBits;
+  int last_offset = (end - 1) & (kIntBits - 1);
+
+  // If we are looking for zeros, negate the data from the map.
+  uint32 this_word = map_[word];
+  if (!value)
+    this_word = ~this_word;
+
+  // If the range spans multiple words, discard the extraneous bits of the
+  // first word by shifting to the right, and then test the remaining bits.
+  if (word < last_word) {
+    if (this_word >> offset)
+      return true;
+    offset = 0;
+
+    word++;
+    // Test each of the "middle" words that lies completely within the range.
+    while (word < last_word) {
+      this_word = map_[word++];
+      if (!value)
+        this_word = ~this_word;
+      if (this_word)
+        return true;
+    }
+  }
+
+  // Test the portion of the last word that lies within the range. (This logic
+  // also handles the case where the entire range lies within a single word.)
+  const uint32 mask = ((2 << (last_offset - offset)) - 1) << offset;
+
+  this_word = map_[last_word];
+  if (!value)
+    this_word = ~this_word;
+
+  return (this_word & mask) != 0;
+}
+
+bool Bitmap::FindNextBit(int* index, int limit, bool value) const {
+  DCHECK_LT(*index, num_bits_);
+  DCHECK_LE(limit, num_bits_);
+  DCHECK_LE(*index, limit);
+  DCHECK_GE(*index, 0);
+  DCHECK_GE(limit, 0);
+
+  const int bit_index = *index;
+  if (bit_index >= limit || limit <= 0)
+    return false;
+
+  // From now on limit != 0, since if it was we would have returned false.
+  int word_index = bit_index >> kLogIntBits;
+  uint32 one_word = map_[word_index];
+
+  // Simple optimization where we can immediately return true if the first
+  // bit is set.  This helps for cases where many bits are set, and doesn't
+  // hurt too much if not.
+  if (Get(bit_index) == value)
+    return true;
+
+  const int first_bit_offset = bit_index & (kIntBits - 1);
+
+  // First word is special - we need to mask off leading bits.
+  uint32 mask = 0xFFFFFFFF << first_bit_offset;
+  if (value) {
+    one_word &= mask;
+  } else {
+    one_word |= ~mask;
+  }
+
+  uint32 empty_value = value ? 0 : 0xFFFFFFFF;
+
+  // Loop through all but the last word.  Note that 'limit' is one
+  // past the last bit we want to check, and we don't want to read
+  // past the end of "words".  E.g. if num_bits_ == 32 only words[0] is
+  // valid, so we want to avoid reading words[1] when limit == 32.
+  const int last_word_index = (limit - 1) >> kLogIntBits;
+  while (word_index < last_word_index) {
+    if (one_word != empty_value) {
+      *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
+      return true;
+    }
+    one_word = map_[++word_index];
+  }
+
+  // Last word is special - we may need to mask off trailing bits.  Note that
+  // 'limit' is one past the last bit we want to check, and if limit is a
+  // multiple of 32 we want to check all bits in this word.
+  const int last_bit_offset = (limit - 1) & (kIntBits - 1);
+  mask = 0xFFFFFFFE << last_bit_offset;
+  if (value) {
+    one_word &= ~mask;
+  } else {
+    one_word |= mask;
+  }
+  if (one_word != empty_value) {
+    *index = (word_index << kLogIntBits) + FindLSBNonEmpty(one_word, value);
+    return true;
+  }
+  return false;
+}
+
+int Bitmap::FindBits(int* index, int limit, bool value) const {
+  DCHECK_LT(*index, num_bits_);
+  DCHECK_LE(limit, num_bits_);
+  DCHECK_LE(*index, limit);
+  DCHECK_GE(*index, 0);
+  DCHECK_GE(limit, 0);
+
+  if (!FindNextBit(index, limit, value))
+    return false;
+
+  // Now see how many bits have the same value.
+  int end = *index;
+  if (!FindNextBit(&end, limit, !value))
+    return limit - *index;
+
+  return end - *index;
+}
+
+}  // namespace disk_cache
diff --git a/net/disk_cache/bitmap.h b/net/disk_cache/bitmap.h
new file mode 100644
index 0000000..4d38f83
--- /dev/null
+++ b/net/disk_cache/bitmap.h
@@ -0,0 +1,153 @@
+// Copyright (c) 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.
+
+#ifndef NET_DISK_CACHE_BITMAP_H_
+#define NET_DISK_CACHE_BITMAP_H_
+
+#include <algorithm>
+
+#include "base/basictypes.h"
+
+namespace disk_cache {
+
+// This class provides support for simple maps of bits.
+class Bitmap {
+ public:
+  Bitmap() : map_(NULL), num_bits_(0), array_size_(0), alloc_(false) {}
+
+  // This constructor will allocate on a uint32 boundary. If |clear_bits| is
+  // false, the bitmap bits will not be initialized.
+  Bitmap(int num_bits, bool clear_bits)
+     : num_bits_(num_bits), array_size_(RequiredArraySize(num_bits)),
+       alloc_(true) {
+    map_ = new uint32[array_size_];
+
+    // Initialize all of the bits.
+    if (clear_bits)
+      Clear();
+  }
+
+  // Constructs a Bitmap with the actual storage provided by the caller. |map|
+  // has to be valid until this object destruction. |num_bits| is the number of
+  // bits in the bitmap, and |num_words| is the size of |map| in 32-bit words.
+  Bitmap(uint32* map, int num_bits, int num_words)
+     : map_(map), num_bits_(num_bits),
+       // If size is larger than necessary, trim because array_size_ is used
+       // as a bound by various methods.
+       array_size_(std::min(RequiredArraySize(num_bits), num_words)),
+       alloc_(false) {}
+
+  ~Bitmap() {
+    if (alloc_)
+      delete[] map_;
+  }
+
+  // Resizes the bitmap.
+  // If |num_bits| < Size(), the extra bits will be discarded.
+  // If |num_bits| > Size(), the extra bits will be filled with zeros if
+  // |clear_bits| is true.
+  // This object cannot be using memory provided during construction.
+  void Resize(int num_bits, bool clear_bits);
+
+  // Returns the number of bits in the bitmap.
+  int Size() const { return num_bits_; }
+
+  // Returns the number of 32-bit words in the bitmap.
+  int ArraySize() const { return array_size_; }
+
+  // Sets all the bits to true or false.
+  void SetAll(bool value) {
+    memset(map_, (value ? 0xFF : 0x00), array_size_ * sizeof(*map_));
+  }
+
+  // Clears all bits in the bitmap
+  void Clear() { SetAll(false); }
+
+  // Sets the value, gets the value or toggles the value of a given bit.
+  void Set(int index, bool value);
+  bool Get(int index) const;
+  void Toggle(int index);
+
+  // Directly sets an element of the internal map. Requires |array_index| <
+  // ArraySize();
+  void SetMapElement(int array_index, uint32 value);
+
+  // Gets an entry of the internal map. Requires array_index <
+  // ArraySize()
+  uint32 GetMapElement(int array_index) const;
+
+  // Directly sets the whole internal map. |size| is the number of 32-bit words
+  // to set from |map|. If  |size| > array_size(), it ignores the end of |map|.
+  void SetMap(const uint32* map, int size);
+
+  // Gets a pointer to the internal map.
+  const uint32* GetMap() const { return map_; }
+
+  // Sets a range of bits to |value|.
+  void SetRange(int begin, int end, bool value);
+
+  // Returns true if any bit between begin inclusive and end exclusive is set.
+  // 0 <= |begin| <= |end| <= Size() is required.
+  bool TestRange(int begin, int end, bool value) const;
+
+  // Scans bits starting at bit *|index|, looking for a bit set to |value|. If
+  // it finds that bit before reaching bit index |limit|, sets *|index| to the
+  // bit index and returns true. Otherwise returns false.
+  // Requires |limit| <= Size().
+  //
+  // Note that to use these methods in a loop you must increment the index
+  // after each use, as in:
+  //
+  //  for (int index = 0 ; map.FindNextBit(&index, limit, value) ; ++index) {
+  //    DoSomethingWith(index);
+  //  }
+  bool FindNextBit(int* index, int limit, bool value) const;
+
+  // Finds the first offset >= *|index| and < |limit| that has its bit set.
+  // See FindNextBit() for more info.
+  bool FindNextSetBitBeforeLimit(int* index, int limit) const {
+    return FindNextBit(index, limit, true);
+  }
+
+  // Finds the first offset >= *|index| that has its bit set.
+  // See FindNextBit() for more info.
+  bool FindNextSetBit(int *index) const {
+    return FindNextSetBitBeforeLimit(index, num_bits_);
+  }
+
+  // Scans bits starting at bit *|index|, looking for a bit set to |value|. If
+  // it finds that bit before reaching bit index |limit|, sets *|index| to the
+  // bit index and then counts the number of consecutive bits set to |value|
+  // (before reaching |limit|), and returns that count. If no bit is found
+  // returns 0. Requires |limit| <= Size().
+  int FindBits(int* index, int limit, bool value) const;
+
+  // Returns number of allocated words required for a bitmap of size |num_bits|.
+  static int RequiredArraySize(int num_bits) {
+    // Force at least one allocated word.
+    if (num_bits <= kIntBits)
+      return 1;
+
+    return (num_bits + kIntBits - 1) >> kLogIntBits;
+  }
+
+ private:
+  static const int kIntBits = sizeof(uint32) * 8;
+  static const int kLogIntBits = 5;  // 2^5 == 32 bits per word.
+
+  // Sets |len| bits from |start| to |value|. All the bits to be set should be
+  // stored in the same word, and len < kIntBits.
+  void SetWordBits(int start, int len, bool value);
+
+  uint32* map_;           // The bitmap.
+  int num_bits_;          // The upper bound of the bitmap.
+  int array_size_;        // The physical size (in uint32s) of the bitmap.
+  bool alloc_;            // Whether or not we allocated the memory.
+
+  DISALLOW_COPY_AND_ASSIGN(Bitmap);
+};
+
+}  // namespace disk_cache
+
+#endif  // NET_DISK_CACHE_BITMAP_H_
diff --git a/net/disk_cache/bitmap_unittest.cc b/net/disk_cache/bitmap_unittest.cc
new file mode 100644
index 0000000..d80ea74
--- /dev/null
+++ b/net/disk_cache/bitmap_unittest.cc
@@ -0,0 +1,293 @@
+// Copyright (c) 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.
+
+#include "net/disk_cache/bitmap.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+TEST(BitmapTest, OverAllocate) {
+  // Test that we don't over allocate on boundaries.
+  disk_cache::Bitmap map32(32, false);
+  EXPECT_EQ(1, map32.ArraySize());
+
+  disk_cache::Bitmap map64(64, false);
+  EXPECT_EQ(2, map64.ArraySize());
+}
+
+TEST(BitmapTest, DefaultConstructor) {
+  // Verify that the default constructor doesn't allocate a bitmap.
+  disk_cache::Bitmap map;
+  EXPECT_EQ(0, map.Size());
+  EXPECT_EQ(0, map.ArraySize());
+  EXPECT_TRUE(NULL == map.GetMap());
+}
+
+TEST(BitmapTest, Basics) {
+  disk_cache::Bitmap bitmap(80, true);
+  const uint32 kValue = 0x74f10060;
+
+  // Test proper allocation size.
+  EXPECT_EQ(80, bitmap.Size());
+  EXPECT_EQ(3, bitmap.ArraySize());
+
+  // Test Set/GetMapElement.
+  EXPECT_EQ(0U, bitmap.GetMapElement(1));
+  bitmap.SetMapElement(1, kValue);
+  EXPECT_EQ(kValue, bitmap.GetMapElement(1));
+
+  // Test Set/Get.
+  EXPECT_TRUE(bitmap.Get(48));
+  EXPECT_FALSE(bitmap.Get(49));
+  EXPECT_FALSE(bitmap.Get(50));
+  bitmap.Set(49, true);
+  EXPECT_TRUE(bitmap.Get(48));
+  EXPECT_TRUE(bitmap.Get(49));
+  EXPECT_FALSE(bitmap.Get(50));
+  bitmap.Set(49, false);
+  EXPECT_TRUE(bitmap.Get(48));
+  EXPECT_FALSE(bitmap.Get(49));
+  EXPECT_FALSE(bitmap.Get(50));
+
+  for (int i = 0; i < 80; i++)
+    bitmap.Set(i, (i % 7) == 0);
+  for (int i = 0; i < 80; i++)
+    EXPECT_EQ(bitmap.Get(i), (i % 7) == 0);
+}
+
+TEST(BitmapTest, Toggle) {
+  static const int kSize = 100;
+  disk_cache::Bitmap map(kSize, true);
+  for (int i = 0; i < 100; i += 3)
+    map.Toggle(i);
+  for (int i = 0; i < 100; i += 9)
+    map.Toggle(i);
+  for (int i = 0; i < 100; ++i)
+    EXPECT_EQ((i % 3 == 0) && (i % 9 != 0), map.Get(i));
+}
+
+TEST(BitmapTest, Resize) {
+  const int kSize1 = 50;
+  const int kSize2 = 100;
+  const int kSize3 = 30;
+  disk_cache::Bitmap map(kSize1, true);
+  map.Resize(kSize1, true);
+  EXPECT_EQ(kSize1, map.Size());
+  EXPECT_FALSE(map.Get(0));
+  EXPECT_FALSE(map.Get(kSize1 - 1));
+
+  map.Resize(kSize2, true);
+  EXPECT_FALSE(map.Get(kSize1 - 1));
+  EXPECT_FALSE(map.Get(kSize1));
+  EXPECT_FALSE(map.Get(kSize2 - 1));
+  EXPECT_EQ(kSize2, map.Size());
+
+  map.Resize(kSize3, true);
+  EXPECT_FALSE(map.Get(kSize3 - 1));
+  EXPECT_EQ(kSize3, map.Size());
+}
+
+TEST(BitmapTest, Map) {
+  // Tests Set/GetMap and the constructor that takes an array.
+  const int kMapSize = 80;
+  char local_map[kMapSize];
+  for (int i = 0; i < kMapSize; i++)
+    local_map[i] = static_cast<char>(i);
+
+  disk_cache::Bitmap bitmap(kMapSize * 8, false);
+  bitmap.SetMap(reinterpret_cast<uint32*>(local_map), kMapSize / 4);
+  for (int i = 0; i < kMapSize; i++) {
+    if (i % 2)
+      EXPECT_TRUE(bitmap.Get(i * 8));
+    else
+      EXPECT_FALSE(bitmap.Get(i * 8));
+  }
+
+  EXPECT_EQ(0, memcmp(local_map, bitmap.GetMap(), kMapSize));
+
+  // Now let's create a bitmap that shares local_map as storage.
+  disk_cache::Bitmap bitmap2(reinterpret_cast<uint32*>(local_map),
+                             kMapSize * 8, kMapSize / 4);
+  EXPECT_EQ(0, memcmp(local_map, bitmap2.GetMap(), kMapSize));
+
+  local_map[kMapSize / 2] = 'a';
+  EXPECT_EQ(0, memcmp(local_map, bitmap2.GetMap(), kMapSize));
+  EXPECT_NE(0, memcmp(local_map, bitmap.GetMap(), kMapSize));
+}
+
+TEST(BitmapTest, SetAll) {
+  // Tests SetAll and Clear.
+  const int kMapSize = 80;
+  char ones[kMapSize];
+  char zeros[kMapSize];
+  memset(ones, 0xff, kMapSize);
+  memset(zeros, 0, kMapSize);
+
+  disk_cache::Bitmap map(kMapSize * 8, true);
+  EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize));
+  map.SetAll(true);
+  EXPECT_EQ(0, memcmp(ones, map.GetMap(), kMapSize));
+  map.SetAll(false);
+  EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize));
+  map.SetAll(true);
+  map.Clear();
+  EXPECT_EQ(0, memcmp(zeros, map.GetMap(), kMapSize));
+}
+
+TEST(BitmapTest, Range) {
+  // Tests SetRange() and TestRange().
+  disk_cache::Bitmap map(100, true);
+  EXPECT_FALSE(map.TestRange(0, 100, true));
+  map.Set(50, true);
+  EXPECT_TRUE(map.TestRange(0, 100, true));
+
+  map.SetAll(false);
+  EXPECT_FALSE(map.TestRange(0, 1, true));
+  EXPECT_FALSE(map.TestRange(30, 31, true));
+  EXPECT_FALSE(map.TestRange(98, 99, true));
+  EXPECT_FALSE(map.TestRange(99, 100, true));
+  EXPECT_FALSE(map.TestRange(0, 100, true));
+
+  EXPECT_TRUE(map.TestRange(0, 1, false));
+  EXPECT_TRUE(map.TestRange(31, 32, false));
+  EXPECT_TRUE(map.TestRange(32, 33, false));
+  EXPECT_TRUE(map.TestRange(99, 100, false));
+  EXPECT_TRUE(map.TestRange(0, 32, false));
+
+  map.SetRange(11, 21, true);
+  for (int i = 0; i < 100; i++)
+    EXPECT_EQ(map.Get(i), (i >= 11) && (i < 21));
+
+  EXPECT_TRUE(map.TestRange(0, 32, true));
+  EXPECT_TRUE(map.TestRange(0, 100, true));
+  EXPECT_TRUE(map.TestRange(11, 21, true));
+  EXPECT_TRUE(map.TestRange(15, 16, true));
+  EXPECT_TRUE(map.TestRange(5, 12, true));
+  EXPECT_TRUE(map.TestRange(5, 11, false));
+  EXPECT_TRUE(map.TestRange(20, 60, true));
+  EXPECT_TRUE(map.TestRange(21, 60, false));
+
+  map.SetAll(true);
+  EXPECT_FALSE(map.TestRange(0, 100, false));
+
+  map.SetRange(70, 99, false);
+  EXPECT_TRUE(map.TestRange(69, 99, false));
+  EXPECT_TRUE(map.TestRange(70, 100, false));
+  EXPECT_FALSE(map.TestRange(70, 99, true));
+}
+
+TEST(BitmapTest, FindNextSetBitBeforeLimit) {
+  // Test FindNextSetBitBeforeLimit. Only check bits from 111 to 277 (limit
+  // bit == 278). Should find all multiples of 27 in that range.
+  disk_cache::Bitmap map(500, true);
+  for (int i = 0; i < 500; i++)
+    map.Set(i, (i % 27) == 0);
+
+  int find_me = 135;  // First one expected.
+  for (int index = 111; map.FindNextSetBitBeforeLimit(&index, 278);
+       ++index) {
+    EXPECT_EQ(index, find_me);
+    find_me += 27;
+  }
+  EXPECT_EQ(find_me, 297);  // The next find_me after 278.
+}
+
+TEST(BitmapTest, FindNextSetBitBeforeLimitAligned) {
+  // Test FindNextSetBitBeforeLimit on aligned scans.
+  disk_cache::Bitmap map(256, true);
+  for (int i = 0; i < 256; i++)
+    map.Set(i, (i % 32) == 0);
+  for (int i = 0; i < 256; i += 32) {
+    int index = i + 1;
+    EXPECT_FALSE(map.FindNextSetBitBeforeLimit(&index, i + 32));
+  }
+}
+
+TEST(BitmapTest, FindNextSetBit) {
+  // Test FindNextSetBit. Check all bits in map. Should find multiples
+  // of 7 from 0 to 98.
+  disk_cache::Bitmap map(100, true);
+  for (int i = 0; i < 100; i++)
+    map.Set(i, (i % 7) == 0);
+
+  int find_me = 0;  // First one expected.
+  for (int index = 0; map.FindNextSetBit(&index); ++index) {
+    EXPECT_EQ(index, find_me);
+    find_me += 7;
+  }
+  EXPECT_EQ(find_me, 105);  // The next find_me after 98.
+}
+
+TEST(BitmapTest, FindNextBit) {
+  // Almost the same test as FindNextSetBit, but find zeros instead of ones.
+  disk_cache::Bitmap map(100, false);
+  map.SetAll(true);
+  for (int i = 0; i < 100; i++)
+    map.Set(i, (i % 7) != 0);
+
+  int find_me = 0;  // First one expected.
+  for (int index = 0; map.FindNextBit(&index, 100, false); ++index) {
+    EXPECT_EQ(index, find_me);
+    find_me += 7;
+  }
+  EXPECT_EQ(find_me, 105);  // The next find_me after 98.
+}
+
+TEST(BitmapTest, SimpleFindBits) {
+  disk_cache::Bitmap bitmap(64, true);
+  bitmap.SetMapElement(0, 0x7ff10060);
+
+  // Bit at index off.
+  int index = 0;
+  EXPECT_EQ(5, bitmap.FindBits(&index, 63, false));
+  EXPECT_EQ(0, index);
+
+  EXPECT_EQ(2, bitmap.FindBits(&index, 63, true));
+  EXPECT_EQ(5, index);
+
+  index = 0;
+  EXPECT_EQ(2, bitmap.FindBits(&index, 63, true));
+  EXPECT_EQ(5, index);
+
+  index = 6;
+  EXPECT_EQ(9, bitmap.FindBits(&index, 63, false));
+  EXPECT_EQ(7, index);
+
+  // Bit at index on.
+  index = 16;
+  EXPECT_EQ(1, bitmap.FindBits(&index, 63, true));
+  EXPECT_EQ(16, index);
+
+  index = 17;
+  EXPECT_EQ(11, bitmap.FindBits(&index, 63, true));
+  EXPECT_EQ(20, index);
+
+  index = 31;
+  EXPECT_EQ(0, bitmap.FindBits(&index, 63, true));
+  EXPECT_EQ(31, index);
+
+  // With a limit.
+  index = 8;
+  EXPECT_EQ(0, bitmap.FindBits(&index, 16, true));
+}
+
+TEST(BitmapTest, MultiWordFindBits) {
+  disk_cache::Bitmap bitmap(500, true);
+  bitmap.SetMapElement(10, 0xff00);
+
+  int index = 0;
+  EXPECT_EQ(0, bitmap.FindBits(&index, 300, true));
+
+  EXPECT_EQ(8, bitmap.FindBits(&index, 500, true));
+  EXPECT_EQ(328, index);
+
+  bitmap.SetMapElement(10, 0xff000000);
+  bitmap.SetMapElement(11, 0xff);
+
+  index = 0;
+  EXPECT_EQ(16, bitmap.FindBits(&index, 500, true));
+  EXPECT_EQ(344, index);
+
+  index = 0;
+  EXPECT_EQ(4, bitmap.FindBits(&index, 348, true));
+  EXPECT_EQ(344, index);
+}
diff --git a/net/disk_cache/disk_cache_test_util.cc b/net/disk_cache/disk_cache_test_util.cc
index b05f59d..e4d3fb7 100644
--- a/net/disk_cache/disk_cache_test_util.cc
+++ b/net/disk_cache/disk_cache_test_util.cc
@@ -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.
 
@@ -7,6 +7,7 @@
 #include "base/logging.h"
 #include "base/file_util.h"
 #include "base/path_service.h"
+#include "net/base/net_errors.h"
 #include "net/disk_cache/backend_impl.h"
 #include "net/disk_cache/cache_util.h"
 #include "net/disk_cache/file.h"
@@ -118,11 +119,20 @@ void CallbackTest::RunWithParams(const Tuple1<int>& params) {
     reuse_++;
   }
 
+  result_ = params.a;
   g_cache_tests_received++;
 }
 
 // -----------------------------------------------------------------------
 
+int SimpleCallbackTest::GetResult(int result) {
+  if (net::ERR_IO_PENDING != result)
+    return result;
+  return WaitForResult();
+}
+
+// -----------------------------------------------------------------------
+
 MessageLoopHelper::MessageLoopHelper()
     : num_callbacks_(0),
       num_iterations_(0),
diff --git a/net/disk_cache/disk_cache_test_util.h b/net/disk_cache/disk_cache_test_util.h
index 45abe5b..9e17512 100644
--- a/net/disk_cache/disk_cache_test_util.h
+++ b/net/disk_cache/disk_cache_test_util.h
@@ -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.
 
@@ -11,6 +11,7 @@
 #include "base/message_loop.h"
 #include "base/task.h"
 #include "base/timer.h"
+#include "net/base/test_completion_callback.h"
 
 // Re-creates a given test file inside the cache test folder.
 bool CreateCacheTestFile(const wchar_t* name);
@@ -53,7 +54,8 @@ class ScopedTestCache {
 
 // -----------------------------------------------------------------------
 
-// Simple callback to process IO completions from the cache.
+// Simple callback to process IO completions from the cache. It allows tests
+// with multiple simultaneous IO operations.
 class CallbackTest : public CallbackRunner< Tuple1<int> >  {
  public:
   explicit CallbackTest(bool reuse) : result_(-1), reuse_(reuse ? 0 : 1) {}
@@ -70,6 +72,24 @@ class CallbackTest : public CallbackRunner< Tuple1<int> >  {
 
 // -----------------------------------------------------------------------
 
+// Simple callback to process IO completions from the cache. This object is not
+// intended to be used when multiple IO operations are in-flight at the same
+// time.
+class SimpleCallbackTest : public TestCompletionCallback  {
+ public:
+  SimpleCallbackTest() {}
+  ~SimpleCallbackTest() {}
+
+  // Returns the final result of the IO operation. If |result| is
+  // net::ERR_IO_PENDING, it waits for the callback be invoked.
+  int GetResult(int result);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(SimpleCallbackTest);
+};
+
+// -----------------------------------------------------------------------
+
 // Simple helper to deal with the message loop on a test.
 class MessageLoopHelper {
  public:
diff --git a/net/disk_cache/disk_format.h b/net/disk_cache/disk_format.h
index 0873e4d..d1f7fed 100644
--- a/net/disk_cache/disk_format.h
+++ b/net/disk_cache/disk_format.h
@@ -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 @@ struct BlockFileHeader {
 
 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_
diff --git a/net/disk_cache/entry_impl.cc b/net/disk_cache/entry_impl.cc
index ea20b3c..c9bab9a 100644
--- a/net/disk_cache/entry_impl.cc
+++ b/net/disk_cache/entry_impl.cc
@@ -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.
 
@@ -10,8 +10,10 @@
 #include "net/base/io_buffer.h"
 #include "net/base/net_errors.h"
 #include "net/disk_cache/backend_impl.h"
+#include "net/disk_cache/bitmap.h"
 #include "net/disk_cache/cache_util.h"
 #include "net/disk_cache/histogram_macros.h"
+#include "net/disk_cache/sparse_control.h"
 
 using base::Time;
 using base::TimeDelta;
@@ -91,6 +93,9 @@ EntryImpl::EntryImpl(BackendImpl* backend, Addr address)
 // data related to a previous cache entry because the range was not fully
 // written before).
 EntryImpl::~EntryImpl() {
+  // Save the sparse info to disk before deleting this entry.
+  sparse_.reset();
+
   if (doomed_) {
     DeleteEntryData(true);
   } else {
@@ -353,16 +358,32 @@ int EntryImpl::WriteData(int index, int offset, net::IOBuffer* buf, int buf_len,
 
 int EntryImpl::ReadSparseData(int64 offset, net::IOBuffer* buf, int buf_len,
                               net::CompletionCallback* completion_callback) {
-  return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+  DCHECK(node_.Data()->dirty);
+  int result = InitSparseData();
+  if (net::OK != result)
+    return result;
+
+  return sparse_->StartIO(SparseControl::kReadOperation, offset, buf, buf_len,
+                          completion_callback);
 }
 
 int EntryImpl::WriteSparseData(int64 offset, net::IOBuffer* buf, int buf_len,
                                net::CompletionCallback* completion_callback) {
-  return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+  DCHECK(node_.Data()->dirty);
+  int result = InitSparseData();
+  if (net::OK != result)
+    return result;
+
+  return sparse_->StartIO(SparseControl::kWriteOperation, offset, buf, buf_len,
+                          completion_callback);
 }
 
 int EntryImpl::GetAvailableRange(int64 offset, int len, int64* start) {
-  return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+  int result = InitSparseData();
+  if (net::OK != result)
+    return result;
+
+  return sparse_->GetAvailableRange(offset, len, start);
 }
 
 uint32 EntryImpl::GetHash() {
@@ -813,6 +834,17 @@ bool EntryImpl::Flush(int index, int size, bool async) {
   return true;
 }
 
+int EntryImpl::InitSparseData() {
+  if (sparse_.get())
+    return net::OK;
+
+  sparse_.reset(new SparseControl(this));
+  int result = sparse_->Init();
+  if (net::OK != result)
+    sparse_.reset();
+  return result;
+}
+
 void EntryImpl::Log(const char* msg) {
   void* pointer = NULL;
   int dirty = 0;
diff --git a/net/disk_cache/entry_impl.h b/net/disk_cache/entry_impl.h
index 72b38cb..00f44db 100644
--- a/net/disk_cache/entry_impl.h
+++ b/net/disk_cache/entry_impl.h
@@ -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.
 
@@ -13,11 +13,13 @@
 namespace disk_cache {
 
 class BackendImpl;
+class SparseControl;
 
 // This class implements the Entry interface. An object of this
 // class represents a single entry on the cache.
 class EntryImpl : public Entry, public base::RefCounted<EntryImpl> {
   friend class base::RefCounted<EntryImpl>;
+  friend class SparseControl;
  public:
   EntryImpl(BackendImpl* backend, Addr address);
 
@@ -98,9 +100,9 @@ class EntryImpl : public Entry, public base::RefCounted<EntryImpl> {
   void SetTimes(base::Time last_used, base::Time last_modified);
 
  private:
-   enum {
-     NUM_STREAMS = 3
-   };
+  enum {
+    NUM_STREAMS = 3
+  };
 
   ~EntryImpl();
 
@@ -138,6 +140,9 @@ class EntryImpl : public Entry, public base::RefCounted<EntryImpl> {
   // Flush the in-memory data to the backing storage.
   bool Flush(int index, int size, bool async);
 
+  // Initializes the sparse control object. Returns a net error code.
+  int InitSparseData();
+
   // Logs this entry to the internal trace buffer.
   void Log(const char* msg);
 
@@ -149,6 +154,8 @@ class EntryImpl : public Entry, public base::RefCounted<EntryImpl> {
                                                 // data and key.
   int unreported_size_[NUM_STREAMS];  // Bytes not reported yet to the backend.
   bool doomed_;               // True if this entry was removed from the cache.
+  scoped_ptr<SparseControl> sparse_;  // Support for sparse entries.
+
   DISALLOW_EVIL_CONSTRUCTORS(EntryImpl);
 };
 
diff --git a/net/disk_cache/entry_unittest.cc b/net/disk_cache/entry_unittest.cc
index 6daaf14..de9b153 100644
--- a/net/disk_cache/entry_unittest.cc
+++ b/net/disk_cache/entry_unittest.cc
@@ -35,6 +35,8 @@ class DiskCacheEntryTest : public DiskCacheTestWithCache {
   void InvalidData();
   void DoomEntry();
   void DoomedEntry();
+  void BasicSparseIO(bool async);
+  void HugeSparseIO(bool async);
 };
 
 void DiskCacheEntryTest::InternalSyncIO() {
@@ -863,3 +865,136 @@ TEST_F(DiskCacheEntryTest, MemoryOnlyEnumerationWithSlaveEntries) {
   // internally. Now we have to doom this child entry manually.
   child_entry->Doom();
 }
+
+// Writes |buf_1| to offset and reads it back as |buf_2|.
+void VerifySparseIO(disk_cache::Entry* entry, int64 offset,
+                    net::IOBuffer* buf_1, int size, bool async,
+                    net::IOBuffer* buf_2) {
+  SimpleCallbackTest callback;
+  SimpleCallbackTest* cb = async ? &callback : NULL;
+
+  memset(buf_2->data(), 0, size);
+  int ret = entry->ReadSparseData(offset, buf_2, size, cb);
+  ret = callback.GetResult(ret);
+  EXPECT_EQ(0, ret);
+
+  ret = entry->WriteSparseData(offset, buf_1, size, cb);
+  ret = callback.GetResult(ret);
+  EXPECT_EQ(size, ret);
+
+  ret = entry->ReadSparseData(offset, buf_2, size, cb);
+  ret = callback.GetResult(ret);
+  EXPECT_EQ(size, ret);
+
+  EXPECT_EQ(0, memcmp(buf_1->data(), buf_2->data(), size));
+}
+
+// Reads |size| bytes from |entry| at |offset| and verifies that they are the
+// same as the content of the provided |buffer|.
+void VerifyContentSparseIO(disk_cache::Entry* entry, int64 offset, char* buffer,
+                           int size, bool async) {
+  SimpleCallbackTest callback;
+  SimpleCallbackTest* cb = async ? &callback : NULL;
+
+  scoped_refptr<net::IOBuffer> buf_1 = new net::IOBuffer(size);
+  memset(buf_1->data(), 0, size);
+  int ret = entry->ReadSparseData(offset, buf_1, size, cb);
+  ret = callback.GetResult(ret);
+  EXPECT_EQ(size, ret);
+
+  EXPECT_EQ(0, memcmp(buf_1->data(), buffer, size));
+}
+
+void DiskCacheEntryTest::BasicSparseIO(bool async) {
+  std::string key("the first key");
+  disk_cache::Entry* entry;
+  ASSERT_TRUE(cache_->CreateEntry(key, &entry));
+
+  const int kSize = 2048;
+  scoped_refptr<net::IOBuffer> buf_1 = new net::IOBuffer(kSize);
+  scoped_refptr<net::IOBuffer> buf_2 = new net::IOBuffer(kSize);
+  CacheTestFillBuffer(buf_1->data(), kSize, false);
+
+  // Write at offset 0.
+  VerifySparseIO(entry, 0, buf_1, kSize, async, buf_2);
+
+  // Write at offset 0x400000 (4 MB).
+  VerifySparseIO(entry, 0x400000, buf_1, kSize, async, buf_2);
+
+  // Write at offset 0x800000000 (32 GB).
+  VerifySparseIO(entry, 0x800000000LL, buf_1, kSize, async, buf_2);
+
+  entry->Close();
+
+  // Check everything again.
+  ASSERT_TRUE(cache_->OpenEntry(key, &entry));
+  VerifyContentSparseIO(entry, 0, buf_1->data(), kSize, async);
+  VerifyContentSparseIO(entry, 0x400000, buf_1->data(), kSize, async);
+  VerifyContentSparseIO(entry, 0x800000000LL, buf_1->data(), kSize, async);
+  entry->Close();
+}
+
+TEST_F(DiskCacheEntryTest, BasicSparseSyncIO) {
+  InitCache();
+  BasicSparseIO(false);
+}
+
+TEST_F(DiskCacheEntryTest, DISABLED_MemoryOnlyBasicSparseSyncIO) {
+  SetMemoryOnlyMode();
+  InitCache();
+  BasicSparseIO(false);
+}
+
+TEST_F(DiskCacheEntryTest, BasicSparseAsyncIO) {
+  InitCache();
+  BasicSparseIO(true);
+}
+
+TEST_F(DiskCacheEntryTest, DISABLED_MemoryOnlyBasicSparseAsyncIO) {
+  SetMemoryOnlyMode();
+  InitCache();
+  BasicSparseIO(true);
+}
+
+void DiskCacheEntryTest::HugeSparseIO(bool async) {
+  std::string key("the first key");
+  disk_cache::Entry* entry;
+  ASSERT_TRUE(cache_->CreateEntry(key, &entry));
+
+  // Write 1.2 MB so that we cover multiple entries.
+  const int kSize = 1200 * 1024;
+  scoped_refptr<net::IOBuffer> buf_1 = new net::IOBuffer(kSize);
+  scoped_refptr<net::IOBuffer> buf_2 = new net::IOBuffer(kSize);
+  CacheTestFillBuffer(buf_1->data(), kSize, false);
+
+  // Write at offset 0x20F0000 (20 MB - 64 KB).
+  VerifySparseIO(entry, 0x20F0000, buf_1, kSize, async, buf_2);
+  entry->Close();
+
+  // Check it again.
+  ASSERT_TRUE(cache_->OpenEntry(key, &entry));
+  VerifyContentSparseIO(entry, 0x20F0000, buf_1->data(), kSize, async);
+  entry->Close();
+}
+
+TEST_F(DiskCacheEntryTest, HugeSparseSyncIO) {
+  InitCache();
+  HugeSparseIO(false);
+}
+
+TEST_F(DiskCacheEntryTest, DISABLED_MemoryOnlyHugeSparseSyncIO) {
+  SetMemoryOnlyMode();
+  InitCache();
+  HugeSparseIO(false);
+}
+
+TEST_F(DiskCacheEntryTest, HugeSparseAsyncIO) {
+  InitCache();
+  HugeSparseIO(true);
+}
+
+TEST_F(DiskCacheEntryTest, DISABLED_MemoryOnlyHugeSparseAsyncIO) {
+  SetMemoryOnlyMode();
+  InitCache();
+  HugeSparseIO(true);
+}
diff --git a/net/disk_cache/sparse_control.cc b/net/disk_cache/sparse_control.cc
new file mode 100644
index 0000000..4550e5c
--- /dev/null
+++ b/net/disk_cache/sparse_control.cc
@@ -0,0 +1,407 @@
+// Copyright (c) 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.
+
+#include "net/disk_cache/sparse_control.h"
+
+#include "base/logging.h"
+#include "base/string_util.h"
+#include "base/time.h"
+#include "net/base/io_buffer.h"
+#include "net/base/net_errors.h"
+#include "net/disk_cache/backend_impl.h"
+#include "net/disk_cache/entry_impl.h"
+
+using base::Time;
+
+namespace {
+
+// Stream of the sparse data index.
+const int kSparseIndex = 2;
+
+// Stream of the sparse data.
+const int kSparseData = 1;
+
+}
+
+namespace disk_cache {
+
+SparseControl::~SparseControl() {
+  if (child_)
+    CloseChild();
+  if (init_)
+    WriteSparseData();
+}
+
+int SparseControl::Init() {
+  DCHECK(!init_);
+
+  // We should not have sparse data for the exposed entry.
+  if (entry_->GetDataSize(kSparseData))
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  // Now see if there is something where we store our data.
+  int rv = net::OK;
+  int data_len = entry_->GetDataSize(kSparseIndex);
+  if (!data_len) {
+    rv = CreateSparseEntry();
+  } else {
+    rv = OpenSparseEntry(data_len);
+  }
+
+  if (rv == net::OK)
+    init_ = true;
+  return rv;
+}
+
+int SparseControl::StartIO(SparseOperation op, int64 offset, net::IOBuffer* buf,
+                           int buf_len, net::CompletionCallback* callback) {
+  DCHECK(init_);
+  // We don't support simultaneous IO for sparse data.
+  if (operation_ != kNoOperation)
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  if (offset < 0 || buf_len < 0)
+    return net::ERR_INVALID_ARGUMENT;
+
+  // We only support up to 64 GB.
+  if (offset + buf_len >= 0x1000000000LL)
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  DCHECK(!user_buf_);
+  DCHECK(!user_callback_);
+
+  // Copy the operation parameters.
+  operation_ = op;
+  offset_ = offset;
+  user_buf_ = new net::ReusedIOBuffer(buf, buf_len);
+  buf_len_ = buf_len;
+
+  result_ = 0;
+  pending_ = false;
+  finished_ = false;
+  user_callback_ = callback;
+
+  DoChildrenIO();
+
+  if (!pending_) {
+    // Everything was done synchronously.
+    operation_ = kNoOperation;
+    user_buf_ = NULL;
+    user_callback_ = NULL;
+    return result_;
+  }
+
+  return net::ERR_IO_PENDING;
+}
+
+int SparseControl::GetAvailableRange(int64 offset, int len, int64* start) {
+  DCHECK(init_);
+  NOTIMPLEMENTED();
+  return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+}
+
+// We are going to start using this entry to store sparse data, so we have to
+// initialize our control info.
+int SparseControl::CreateSparseEntry() {
+  // TODO(rvargas): Set/check a flag in EntryStore.
+
+  memset(&sparse_header_, 0, sizeof(sparse_header_));
+  sparse_header_.signature = Time::Now().ToInternalValue();
+  sparse_header_.magic = kIndexMagic;
+  sparse_header_.parent_key_len = entry_->GetKey().size();
+  children_map_.Resize(kNumSparseBits, true);
+
+  // Save the header. The bitmap is saved in the destructor.
+  scoped_refptr<net::IOBuffer> buf =
+      new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_));
+
+  int rv = entry_->WriteData(kSparseIndex, 0, buf, sizeof(sparse_header_), NULL,
+                             false);
+  if (rv != sizeof(sparse_header_)) {
+    DLOG(ERROR) << "Unable to save sparse_header_";
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+  }
+  return net::OK;
+}
+
+// We are opening an entry from disk. Make sure that our control data is there.
+int SparseControl::OpenSparseEntry(int data_len) {
+  if (data_len < static_cast<int>(sizeof(SparseData)))
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  if (entry_->GetDataSize(kSparseData))
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  // TODO(rvargas): Set/check a flag in EntryStore.
+
+  // Dont't go over board with the bitmap. 8 KB gives us offsets up to 64 GB.
+  int map_len = data_len - sizeof(sparse_header_);
+  if (map_len > 8 * 1024 || map_len % 4)
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  scoped_refptr<net::IOBuffer> buf =
+      new net::WrappedIOBuffer(reinterpret_cast<char*>(&sparse_header_));
+
+  // Read header.
+  int rv = entry_->ReadData(kSparseIndex, 0, buf, sizeof(sparse_header_), NULL);
+  if (rv != static_cast<int>(sizeof(sparse_header_)))
+    return net::ERR_CACHE_READ_FAILURE;
+
+  // The real validation should be performed by the caller. This is just to
+  // double check.
+  if (sparse_header_.magic != kIndexMagic ||
+      sparse_header_.parent_key_len !=
+          static_cast<int>(entry_->GetKey().size()))
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  // Read the actual bitmap.
+  buf = new net::IOBuffer(map_len);
+  rv = entry_->ReadData(kSparseIndex, sizeof(sparse_header_), buf, map_len,
+                        NULL);
+  if (rv != map_len)
+    return net::ERR_CACHE_READ_FAILURE;
+
+  // Grow the bitmap to the current size and copy the bits.
+  children_map_.Resize(map_len * 8, false);
+  children_map_.SetMap(reinterpret_cast<uint32*>(buf->data()), map_len);
+  return net::OK;
+}
+
+bool SparseControl::OpenChild() {
+  DCHECK_GE(result_, 0);
+
+  std::string key = GenerateChildKey();
+  if (child_) {
+    // Keep using the same child or open another one?.
+    if (key == child_->GetKey())
+      return true;
+    CloseChild();
+  }
+
+  // Se if we are tracking this child.
+  bool child_present = ChildPresent();
+  if (kReadOperation == operation_ && !child_present)
+    return false;
+
+  if (!child_present || !entry_->backend_->OpenEntry(key, &child_)) {
+    if (!entry_->backend_->CreateEntry(key, &child_)) {
+      child_ = NULL;
+      result_ = net::ERR_CACHE_READ_FAILURE;
+      return false;
+    }
+    // Write signature.
+    InitChildData();
+    return true;
+  }
+
+  // TODO(rvargas): Set/check a flag in EntryStore.
+
+  scoped_refptr<net::WrappedIOBuffer> buf =
+      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_));
+
+  // Read signature.
+  int rv = child_->ReadData(kSparseIndex, 0, buf, sizeof(child_data_), NULL);
+  if (rv != sizeof(child_data_)) {
+    result_ = net::ERR_CACHE_READ_FAILURE;
+    return false;
+  }
+
+  // TODO(rvargas): Proper error handling and check magic etc.
+  if (child_data_.header.signature != sparse_header_.signature) {
+    result_ = net::ERR_CACHE_READ_FAILURE;
+    return false;
+  }
+
+  return true;
+}
+
+void SparseControl::CloseChild() {
+  scoped_refptr<net::WrappedIOBuffer> buf =
+      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_));
+
+  // Save the allocation bitmap before closing the child entry.
+  int rv = child_->WriteData(kSparseIndex, 0, buf, sizeof(child_data_),
+                             NULL, false);
+  if (rv != sizeof(child_data_))
+    DLOG(ERROR) << "Failed to save child data";
+  child_->Close();
+  child_ = NULL;
+}
+
+// If this entry is called entry_name, child entreies will be named something
+// like Range_entry_name:XXX:YYY where XXX is the entry signature and YYY is the
+// number of the particular child.
+std::string SparseControl::GenerateChildKey() {
+  return StringPrintf("Range_%s:%llx:%llx", entry_->GetKey().c_str(),
+                      sparse_header_.signature, offset_ >> 20);
+}
+
+bool SparseControl::ChildPresent() {
+  int child_bit = static_cast<int>(offset_ >> 20);
+  if (children_map_.Size() < child_bit)
+    return false;
+
+  return children_map_.Get(child_bit);
+}
+
+void SparseControl::SetChildBit() {
+  int child_bit = static_cast<int>(offset_ >> 20);
+
+  // We may have to increase the bitmap of child entries.
+  if (children_map_.Size() <= child_bit)
+    children_map_.Resize(Bitmap::RequiredArraySize(child_bit + 1) * 32, true);
+
+  children_map_.Set(child_bit, true);
+}
+
+void SparseControl::WriteSparseData() {
+  scoped_refptr<net::IOBuffer> buf = new net::WrappedIOBuffer(
+      reinterpret_cast<const char*>(children_map_.GetMap()));
+
+  int len = children_map_.ArraySize() * 4;
+  int rv = entry_->WriteData(kSparseIndex, sizeof(sparse_header_), buf, len,
+                             NULL, false);
+  if (rv != len) {
+    DLOG(ERROR) << "Unable to save sparse map";
+  }
+}
+
+bool SparseControl::VerifyRange() {
+  DCHECK_GE(result_, 0);
+
+  child_offset_ = static_cast<int>(offset_) & 0xfffff;
+  child_len_ = std::min(buf_len_, 0x100000 - child_offset_);
+
+  // We can write to anywhere in this child.
+  if (operation_ != kReadOperation)
+    return true;
+
+  // Check that there are no holes in this range.
+  int last_bit = (child_offset_ + child_len_ + 1023) >> 10;
+  int start = child_offset_ >> 10;
+  if (child_map_.FindNextBit(&start, last_bit, false)) {
+    // Something is not here.
+    if (start == child_offset_ >> 10)
+      return false;
+
+    // We have the first part.
+    // TODO(rvargas): Avoid coming back here again after the actual read.
+    child_len_ = (start << 10) - child_offset_;
+  }
+  return true;
+}
+
+void SparseControl::UpdateRange(int result) {
+  if (result <= 0 || operation_ != kWriteOperation)
+    return;
+
+  // Write the bitmap.
+  int last_bit = (child_offset_ + result + 1023) >> 10;
+  child_map_.SetRange(child_offset_ >> 10, last_bit, true);
+
+  // TODO(rvargas): Keep track of partial writes so that we don't consider the
+  // whole block to be present.
+}
+
+void SparseControl::InitChildData() {
+  memset(&child_data_, 0, sizeof(child_data_));
+  child_data_.header = sparse_header_;
+
+  scoped_refptr<net::WrappedIOBuffer> buf =
+      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_));
+
+  int rv = child_->WriteData(kSparseIndex, 0, buf, sizeof(child_data_),
+                             NULL, false);
+  if (rv != sizeof(child_data_))
+    DLOG(ERROR) << "Failed to save child data";
+  SetChildBit();
+}
+
+void SparseControl::DoChildrenIO() {
+  while (DoChildIO()) continue;
+
+  if (pending_ && finished_)
+    DoUserCallback();
+}
+
+bool SparseControl::DoChildIO() {
+  finished_ = true;
+  if (!buf_len_ || result_ < 0)
+    return false;
+
+  if (!OpenChild())
+    return false;
+
+  if (!VerifyRange())
+    return false;
+
+  // We have more work to do. Let's not trigger a callback to the caller.
+  finished_ = false;
+  net::CompletionCallback* callback = user_callback_ ? &child_callback_ : NULL;
+
+  int rv;
+  if (kReadOperation == operation_) {
+    rv = child_->ReadData(kSparseData, child_offset_, user_buf_, child_len_,
+                          callback);
+  } else {
+    DCHECK(kWriteOperation == operation_);
+    rv = child_->WriteData(kSparseData, child_offset_, user_buf_, child_len_,
+                           callback, false);
+  }
+
+  if (rv == net::ERR_IO_PENDING) {
+    if (!pending_) {
+      pending_ = true;
+      // The child will protect himself against closing the entry while IO is in
+      // progress. However, this entry can still be closed, and that would not
+      // be a good thing for us, so we increase the refcount until we're
+      // finished doing sparse stuff.
+      entry_->AddRef();
+    }
+    return false;
+  }
+
+  DoChildIOCompleted(rv);
+  return true;
+}
+
+void SparseControl::DoChildIOCompleted(int result) {
+  if (result < 0) {
+    // We fail the whole operation if we encounter an error.
+    result_ = result;
+    return;
+  }
+
+  UpdateRange(result);
+
+  result_ += result;
+  offset_ += result;
+  buf_len_ -= result;
+
+  // We'll be reusing the user provided buffer for the next chunk.
+  if (buf_len_)
+    user_buf_->SetOffset(result_);
+}
+
+void SparseControl::OnChildIOCompleted(int result) {
+  DCHECK_NE(net::ERR_IO_PENDING, result);
+  DoChildIOCompleted(result);
+
+  // We are running a callback from the message loop. It's time to restart what
+  // we were doing before.
+  DoChildrenIO();
+}
+
+void SparseControl::DoUserCallback() {
+  DCHECK(user_callback_);
+  net::CompletionCallback* c = user_callback_;
+  user_callback_ = NULL;
+  user_buf_ = NULL;
+  pending_ = false;
+  operation_ = kNoOperation;
+  entry_->Release();  // Don't touch object after this line.
+  c->Run(result_);
+}
+
+}  // namespace disk_cache
diff --git a/net/disk_cache/sparse_control.h b/net/disk_cache/sparse_control.h
new file mode 100644
index 0000000..fe65035
--- /dev/null
+++ b/net/disk_cache/sparse_control.h
@@ -0,0 +1,147 @@
+// Copyright (c) 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.
+
+#ifndef NET_DISK_CACHE_SPARSE_CONTROL_H_
+#define NET_DISK_CACHE_SPARSE_CONTROL_H_
+
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/compiler_specific.h"
+#include "net/base/completion_callback.h"
+#include "net/disk_cache/bitmap.h"
+#include "net/disk_cache/disk_format.h"
+
+namespace net {
+class IOBuffer;
+class ReusedIOBuffer;
+}
+
+namespace disk_cache {
+
+class Entry;
+class EntryImpl;
+
+// This class provides support for the sparse capabilities of the disk cache.
+// Basically, sparse IO is directed from EntryImpl to this class, and we split
+// the operation into multiple small pieces, sending each one to the
+// appropriate entry. An instance of this class is asociated with each entry
+// used directly for sparse operations (the entry passed in to the constructor).
+class SparseControl {
+ public:
+  // The operation to perform.
+  enum SparseOperation {
+    kNoOperation,
+    kReadOperation,
+    kWriteOperation
+  };
+
+  explicit SparseControl(EntryImpl* entry)
+      : entry_(entry), child_(NULL), operation_(kNoOperation), init_(false),
+        child_map_(child_data_.bitmap, kNumSparseBits, kNumSparseBits / 32),
+        ALLOW_THIS_IN_INITIALIZER_LIST(
+            child_callback_(this, &SparseControl::OnChildIOCompleted)),
+        user_callback_(NULL) {}
+  ~SparseControl();
+
+  // Initializes the object for the current entry. If this entry already stores
+  // sparse data, or can be used to do it, it updates the relevant information
+  // on disk and returns net::OK. Otherwise it returns a net error code.
+  int Init();
+
+  // Performs an actual sparse read or write operation for this entry. |op| is
+  // the operation to perform, |offset| is the desired sparse offset, |buf| and
+  // |buf_len| specify the actual data to use and |callback| is the callback
+  // to use for asynchronous operations. See the description of the Read /
+  // WriteSparseData for details about the arguments. The return value is the
+  // number of bytes read or written, or a net error code.
+  int StartIO(SparseOperation op, int64 offset, net::IOBuffer* buf,
+              int buf_len, net::CompletionCallback* callback);
+
+  // Implements Entry::GetAvailableRange().
+  int GetAvailableRange(int64 offset, int len, int64* start);
+
+ private:
+  // Creates a new sparse entry or opens an aready created entry from disk.
+  // These methods just read / write the required info from disk for the current
+  // entry, and verify that everything is correct. The return value is a net
+  // error code.
+  int CreateSparseEntry();
+  int OpenSparseEntry(int data_len);
+
+  // Opens and closes a child entry. A child entry is a regular EntryImpl object
+  // with a key derived from the key of the resource to store and the range
+  // stored by that child.
+  bool OpenChild();
+  void CloseChild();
+  std::string GenerateChildKey();
+
+  // Returns true if the required child is tracked by the parent entry, i.e. it
+  // was already created.
+  bool ChildPresent();
+
+  // Starts tracking this child. A new child entry was created so we must set
+  // the corresponding bit on the bitmap of children.
+  void SetChildBit();
+
+  // Writes to disk the tracking information for this entry.
+  void WriteSparseData();
+
+  // Verify that the range to be accessed for the current child is appropriate.
+  // Returns false if an error is detected or there is no need to perform the
+  // current IO operation (for instance if the required range is not stored by
+  // the child).
+  bool VerifyRange();
+
+  // Updates the contents bitmap for the current range, based on the result of
+  // the current operation.
+  void UpdateRange(int result);
+
+  // Initializes the sparse info for the current child.
+  void InitChildData();
+
+  // Iterates through all the children needed to complete the current operation.
+  void DoChildrenIO();
+
+  // Performs a single operation with the current child. Returns true when we
+  // should move on to the next child and false when we should interrupt our
+  // work.
+  bool DoChildIO();
+
+  // Performs the required work after a single IO operations finishes.
+  void DoChildIOCompleted(int result);
+
+  // Invoked by the callback of asynchronous operations.
+  void OnChildIOCompleted(int result);
+
+  // Reports to the user that we are done.
+  void DoUserCallback();
+
+  EntryImpl* entry_;  // The sparse entry.
+  Entry* child_;  // The current child entry.
+  SparseOperation operation_;
+  bool pending_;  // True if any child IO operation returned pending.
+  bool finished_;
+  bool init_;
+
+  SparseHeader sparse_header_;  // Data about the children of entry_.
+  Bitmap children_map_;  // The actual bitmap of children.
+  SparseData child_data_;  // Parent and allocation map of child_.
+  Bitmap child_map_;  // The allocation map as a bitmap.
+
+  net::CompletionCallbackImpl<SparseControl> child_callback_;
+  net::CompletionCallback* user_callback_;
+  int64 offset_;  // Current sparse offset.
+  scoped_refptr<net::ReusedIOBuffer> user_buf_;
+  int buf_len_;  // Bytes to read or write.
+  int child_offset_;  // Offset to use for the current child.
+  int child_len_;  // Bytes to read or write for this child.
+  int result_;
+
+  DISALLOW_COPY_AND_ASSIGN(SparseControl);
+};
+
+}  // namespace disk_cache
+
+#endif  // NET_DISK_CACHE_SPARSE_CONTROL_H_
diff --git a/net/net.gyp b/net/net.gyp
index cbf302d..e368e5f 100644
--- a/net/net.gyp
+++ b/net/net.gyp
@@ -154,6 +154,8 @@
         'disk_cache/addr.h',
         'disk_cache/backend_impl.cc',
         'disk_cache/backend_impl.h',
+        'disk_cache/bitmap.cc',
+        'disk_cache/bitmap.h',
         'disk_cache/block_files.cc',
         'disk_cache/block_files.h',
         'disk_cache/cache_util.h',
@@ -186,6 +188,8 @@
         'disk_cache/mem_rankings.h',
         'disk_cache/rankings.cc',
         'disk_cache/rankings.h',
+        'disk_cache/sparse_control.cc',
+        'disk_cache/sparse_control.h',
         'disk_cache/stats.cc',
         'disk_cache/stats.h',
         'disk_cache/stats_histogram.cc',
@@ -434,6 +438,7 @@
         'base/x509_certificate_unittest.cc',
         'disk_cache/addr_unittest.cc',
         'disk_cache/backend_unittest.cc',
+        'disk_cache/bitmap_unittest.cc',
         'disk_cache/block_files_unittest.cc',
         'disk_cache/disk_cache_test_base.cc',
         'disk_cache/disk_cache_test_base.h',