Disk cache: Reference CL for the implementation of file format version 3.

net/disk_cache/v3/sparse_control_v3.cc

+// Copyright (c) 2012 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/v3/sparse_control_v3.h"
+
+#include "base/bind.h"
+#include "base/format_macros.h"
+#include "base/logging.h"
+#include "base/message_loop.h"
+#include "base/stringprintf.h"
+#include "base/time.h"
+#include "net/base/io_buffer.h"
+#include "net/base/net_errors.h"
+#include "net/disk_cache/net_log_parameters.h"
+#include "net/disk_cache/v3/backend_impl_v3.h"
+#include "net/disk_cache/v3/entry_impl_v3.h"
+
+using base::Time;
+using base::Bind;
+
+namespace {
+
+// Stream of the sparse data index.
+const int kSparseIndex = 2;
+
+// Stream of the sparse data.
+const int kSparseData = 1;
+
+// We can have up to 64k children.
+const int kMaxMapSize = 8 * 1024;
+
+// The maximum number of bytes that a child can store.
+const int kMaxEntrySize = 0x100000;
+
+// The size of each data block (tracked by the child allocation bitmap).
+const int kBlockSize = 1024;
+
+// Returns the name of a child entry given the base_name and signature of the
+// parent and the child_id.
+// If the entry is called entry_name, child entries 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 GenerateChildName(const std::string& base_name, int64 signature,
+                              int64 child_id) {
+  return base::StringPrintf("Range_%s:%" PRIx64 ":%" PRIx64, base_name.c_str(),
+                            signature, child_id);
+}
+
+// This class deletes the children of a sparse entry.
+class ChildrenDeleter : public base::RefCountedThreadSafe<ChildrenDeleter> {
+ public:
+  ChildrenDeleter(disk_cache::BackendImplV3* backend, const std::string& name)
+      : backend_(backend->GetWeakPtr()), name_(name), signature_(0) {}
+
+  // Two ways of deleting the children: if we have the children map, use Start()
+  // directly, otherwise pass the data address to ReadData().
+  void Start(net::IOBuffer* buffer, int len);
+  void ReadData(disk_cache::Addr address, int len);
+
+ private:
+  friend class base::RefCountedThreadSafe<ChildrenDeleter>;
+  virtual ~ChildrenDeleter() {}
+
+  void DeleteChildren();
+  void OnReadComplete(int result);
+  void OnDoomComplete(int result);
+
+  base::WeakPtr<disk_cache::BackendImplV3> backend_;
+  std::string name_;
+  disk_cache::Bitmap children_map_;
+  int64 signature_;
+  scoped_refptr<net::IOBuffer> buffer_;
+  DISALLOW_COPY_AND_ASSIGN(ChildrenDeleter);
+};
+
+void ChildrenDeleter::Start(net::IOBuffer* buffer, int len) {
+  if (len < static_cast<int>(sizeof(disk_cache::SparseData)))
+    return Release();
+
+  // Just copy the information from |buffer|, delete |buffer| and start deleting
+  // the child entries.
+  disk_cache::SparseData* data =
+      reinterpret_cast<disk_cache::SparseData*>(buffer->data());
+  signature_ = data->header.signature;
+
+  int num_bits = (len - sizeof(disk_cache::SparseHeader)) * 8;
+  children_map_.Resize(num_bits, false);
+  children_map_.SetMap(data->bitmap, num_bits / 32);
+
+  MessageLoop::current()->PostTask(FROM_HERE,
+                                   Bind(&ChildrenDeleter::DeleteChildren,
+                                        this));
+}
+
+void ChildrenDeleter::ReadData(disk_cache::Addr address, int len) {
+  DCHECK(address.is_block_file());
+  if (!backend_)
+    return Release();
+
+  buffer_ = new net::IOBuffer(len);
+  backend_->ReadData(NULL, address, 0, buffer_, len,
+                     Bind(&ChildrenDeleter::OnReadComplete, this));
+}
+
+void ChildrenDeleter::DeleteChildren() {
+  int child_id = 0;
+  for (int rv = net::OK; rv != net::ERR_IO_PENDING;) {
+    if (!children_map_.FindNextSetBit(&child_id) || !backend_) {
+      // We are done. Just delete this object.
+      return Release();
+    }
+    std::string child_name = GenerateChildName(name_, signature_, child_id);
+    rv = backend_->DoomEntry(child_name,
+                             Bind(&ChildrenDeleter::OnDoomComplete, this));
+    children_map_.Set(child_id, false);
+  }
+}
+
+void ChildrenDeleter::OnReadComplete(int result) {
+  Start(buffer_, result);
+}
+
+void ChildrenDeleter::OnDoomComplete(int result) {
+  DeleteChildren();
+}
+
+// -----------------------------------------------------------------------
+
+// Returns the NetLog event type corresponding to a SparseOperation.
+net::NetLog::EventType GetSparseEventType(
+    disk_cache::SparseControlV3::SparseOperation operation) {
+  switch (operation) {
+    case disk_cache::SparseControlV3::kReadOperation:
+      return net::NetLog::TYPE_SPARSE_READ;
+    case disk_cache::SparseControlV3::kWriteOperation:
+      return net::NetLog::TYPE_SPARSE_WRITE;
+    case disk_cache::SparseControlV3::kGetRangeOperation:
+      return net::NetLog::TYPE_SPARSE_GET_RANGE;
+    default:
+      NOTREACHED();
+      return net::NetLog::TYPE_CANCELLED;
+  }
+}
+
+}  // namespace.
+
+namespace disk_cache {
+
+SparseControlV3::SparseControlV3(EntryImplV3* entry)
+    : entry_(entry),
+      child_(NULL),
+      operation_(kNoOperation),
+      next_state_(STATE_NONE),
+      init_(false),
+      range_found_(false),
+      abort_(false),
+      valid_(false),
+      closing_(false),
+      child_map_(child_data_.bitmap, kNumSparseBits, kNumSparseBits / 32),
+      callback_(base::Bind(&SparseControlV3::OnIOComplete,
+                           base::Unretained(this))),
+      offset_(0),
+      buf_len_(0),
+      child_offset_(0),
+      child_len_(0),
+      result_(0),
+      range_start_(NULL) {
+  memset(&sparse_header_, 0, sizeof(sparse_header_));
+  memset(&child_data_, 0, sizeof(child_data_));
+}
+
+SparseControlV3::~SparseControlV3() {
+}
+
+void SparseControlV3::Close() {
+  if (closing_)
+    return;
+  if (operation_ != kNoOperation || valid_) {
+    closing_ = true;
+    entry_->AddRef();
+    if (operation_ != kNoOperation)
+      return;
+
+    DCHECK_EQ(next_state_, STATE_NONE);
+    DCHECK(user_callback_.is_null());
+    next_state_ = STATE_CLOSE;
+    int rv = DoLoop(net::OK);
+    return;
+  }
+}
+
+bool SparseControlV3::CouldBeSparse() const {
+  if (init_)
+    return valid_;
+
+  if (entry_->GetDataSize(kSparseData))
+    return false;
+
+  // We don't verify the data, just see if it could be there.
+  return (entry_->GetDataSize(kSparseIndex) != 0);
+}
+
+int SparseControlV3::StartIO(SparseOperation op, int64 offset,
+                             net::IOBuffer* buf, int buf_len,
+                             const CompletionCallback& callback) {
+  // 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 || offset + buf_len < 0)
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  DCHECK(!user_buf_);
+  DCHECK(user_callback_.is_null());
+
+  if (init_ && !valid_)
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  if (!buf && (op == kReadOperation || op == kWriteOperation))
+    return 0;
+
+  // Copy the operation parameters.
+  operation_ = op;
+  offset_ = offset;
+  user_buf_ = buf ? new net::DrainableIOBuffer(buf, buf_len) : NULL;
+  buf_len_ = buf_len;
+
+  result_ = 0;
+  abort_ = false;
+
+  if (entry_->net_log().IsLoggingAllEvents()) {
+    entry_->net_log().BeginEvent(
+        GetSparseEventType(operation_),
+        CreateNetLogSparseOperationCallback(offset_, buf_len_));
+  }
+
+  DCHECK_EQ(next_state_, STATE_NONE);
+  next_state_ = init_ ? STATE_GET_CHILD_KEY : STATE_INIT;
+
+  int rv = DoLoop(net::OK);
+  if (rv == net::ERR_IO_PENDING) {
+     user_callback_ = callback;
+     entry_->AddRef();  // Self preservation while we're working.
+  } else {
+    operation_ = kNoOperation;
+    user_buf_ = NULL;
+  }
+
+  return rv;
+}
+
+int SparseControlV3::GetAvailableRange(int64 offset, int len, int64* start,
+                                       const CompletionCallback& callback) {
+  // We don't support simultaneous IO for sparse data.
+  if (operation_ != kNoOperation)
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  DCHECK(start);
+
+  // If there is a failure, we want to return a valid start.
+  *start = offset;
+  range_found_ = false;
+  range_start_ = start;
+  int result = StartIO(kGetRangeOperation, offset, NULL, len, callback);
+  if (range_found_) {
+    *start = offset_;
+    return result;
+  }
+
+  return result;
+}
+
+void SparseControlV3::CancelIO() {
+  if (operation_ == kNoOperation)
+    return;
+  abort_ = true;
+}
+
+int SparseControlV3::ReadyToUse(const CompletionCallback& callback) {
+  if (!abort_)
+    return net::OK;
+
+  // We'll grab another reference to keep this object alive because we just have
+  // one extra reference due to the pending IO operation itself, but we'll
+  // release that one before invoking user_callback_.
+  entry_->AddRef();  // Balanced in HanldeAbortCallbacks.
+  abort_callbacks_.push_back(callback);
+  return net::ERR_IO_PENDING;
+}
+
+// Static
+void SparseControlV3::DeleteChildren(EntryImplV3* entry) {
+  DCHECK(entry->GetEntryFlags() & PARENT_ENTRY);
+  int data_len = entry->GetDataSize(kSparseIndex);
+  if (data_len < static_cast<int>(sizeof(SparseData)) ||
+      entry->GetDataSize(kSparseData))
+    return;
+
+  int map_len = data_len - sizeof(SparseHeader);
+  if (map_len > kMaxMapSize || map_len % 4)
+    return;
+
+  scoped_refptr<net::IOBuffer> buffer;
+  Addr address;
+  entry->GetData(kSparseIndex, &buffer, &address);
+  if (!buffer && !address.is_initialized())
+    return;
+
+  entry->net_log().AddEvent(net::NetLog::TYPE_SPARSE_DELETE_CHILDREN);
+
+  DCHECK(entry->backend_);
+  ChildrenDeleter* deleter = new ChildrenDeleter(entry->backend_,
+                                                 entry->GetKey());
+  // The object will self destruct when finished.
+  deleter->AddRef();
+
+  if (buffer)
+    deleter->Start(buffer, data_len);
+  else
+    deleter->ReadData(address, data_len);
+}
+
+// -----------------------------------------------------------------------
+
+int SparseControlV3::DoLoop(int result) {
+  DCHECK(next_state_ != STATE_NONE);
+
+  int rv = result;
+  do {
+    State state = next_state_;
+    next_state_ = STATE_NONE;
+    switch (state) {
+      case STATE_INIT:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoInit();
+        break;
+      case STATE_CREATE_SPARSE_ENTRY:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoCreateSparseEntry();
+        break;
+      case STATE_CREATE_SPARSE_ENTRY_COMPLETE:
+        rv = DoCreateSparseEntryComplete(rv);
+        break;
+      case STATE_OPEN_SPARSE_ENTRY:
+        rv = DoOpenSparseEntry(rv);
+        break;
+      case STATE_OPEN_SPARSE_ENTRY_COMPLETE:
+        rv = DoOpenSparseEntryComplete(rv);
+        break;
+      case STATE_READ_BITMAP_COMPLETE:
+        rv = DoReadBitmapComplete(rv);
+        break;
+      case STATE_GET_CHILD_KEY:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoGetChildKey();
+        break;
+      case STATE_OPEN_CHILD:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoOpenChild();
+        break;
+      case STATE_OPEN_CHILD_COMPLETE:
+        rv = DoOpenChildComplete(rv);
+        break;
+      case STATE_CREATE_CHILD:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoCreateChild();
+        break;
+      case STATE_CREATE_CHILD_COMPLETE:
+        rv = DoCreateChildComplete(rv);
+        break;
+      case STATE_READ_SIGNATURE_COMPLETE:
+        rv = DoReadSignatureComplete(rv);
+        break;
+      case STATE_CLOSE_CHILD:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoCloseChild();
+        break;
+      case STATE_CLOSE_CHILD_COMPLETE:
+        rv = DoCloseChildComplete(rv);
+        break;
+      case STATE_DO_CHILD_IO:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoChildIO();
+        break;
+      case STATE_DO_CHILD_IO_COMPLETE:
+        rv = DoChildIOComplete(rv);
+        break;
+      case STATE_CLOSE:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoClose();
+        break;
+      case STATE_WRITE_BITMAP:
+        DCHECK_EQ(net::OK, rv);
+        rv = DoWriteBitmap();
+        break;
+      case STATE_WRITE_BITMAP_COMPLETE:
+        rv = DoWriteBitmapComplete(rv);
+        break;
+      default:
+        NOTREACHED();
+    }
+  } while (rv != net::ERR_IO_PENDING && next_state_ != STATE_NONE);
+
+  if (rv != net::ERR_IO_PENDING)
+    HandleResult(rv);
+
+  return rv;
+}
+
+int SparseControlV3::DoInit() {
+  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) {
+    next_state_ = STATE_OPEN_SPARSE_ENTRY;
+    return data_len;
+  }
+  next_state_ = STATE_CREATE_SPARSE_ENTRY;
+  return net::OK;
+}
+
+// We are going to start using this entry to store sparse data, so we have to
+// initialize our control info.
+int SparseControlV3::DoCreateSparseEntry() {
+  if (CHILD_ENTRY & entry_->GetEntryFlags())
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  memset(&sparse_header_, 0, sizeof(sparse_header_));
+  sparse_header_.signature = Time::Now().ToInternalValue();
+  sparse_header_.magic = kIndexMagicV3;
+  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_)));
+
+  next_state_ = STATE_CREATE_SPARSE_ENTRY_COMPLETE;
+  return entry_->WriteData(kSparseIndex, 0, buf, sizeof(sparse_header_),
+                           callback_, false);
+}
+
+int SparseControlV3::DoCreateSparseEntryComplete(int result) {
+  if (result != sizeof(sparse_header_)) {
+    DLOG(ERROR) << "Unable to save sparse_header_";
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+  }
+
+  entry_->SetEntryFlags(PARENT_ENTRY);
+  init_ = true;
+  valid_ = true;
+  next_state_ = STATE_GET_CHILD_KEY;
+  return net::OK;
+}
+
+// We are opening an entry from disk. Make sure that our control data is there.
+int SparseControlV3::DoOpenSparseEntry(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;
+
+  if (!(PARENT_ENTRY & entry_->GetEntryFlags()))
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  // 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 > kMaxMapSize || 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.
+  next_state_ = STATE_OPEN_SPARSE_ENTRY_COMPLETE;
+  return entry_->ReadData(kSparseIndex, 0, buf, sizeof(sparse_header_),
+                          callback_);
+}
+
+int SparseControlV3::DoOpenSparseEntryComplete(int result) {
+  if (result != 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 != kIndexMagicV3 ||
+      sparse_header_.parent_key_len !=
+          static_cast<int>(entry_->GetKey().size()))
+    return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+
+  // Read the actual bitmap.
+  int map_len = entry_->GetDataSize(kSparseIndex) - sizeof(sparse_header_);
+  buf_ = new net::IOBuffer(map_len);
+  next_state_ = STATE_READ_BITMAP_COMPLETE;
+  return entry_->ReadData(kSparseIndex, sizeof(sparse_header_), buf_, map_len,
+                          callback_);
+}
+
+int SparseControlV3::DoReadBitmapComplete(int result) {
+  int map_len = entry_->GetDataSize(kSparseIndex) - sizeof(sparse_header_);
+  if (result != 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);
+  init_ = true;
+  valid_ = true;
+  next_state_ = STATE_GET_CHILD_KEY;
+  return net::OK;
+}
+
+int SparseControlV3::DoGetChildKey() {
+  key_ = GenerateChildKey();
+  if (child_) {
+    // Keep using the same child or open another one?.
+    if (key_ == child_->GetKey()) {
+      next_state_ = STATE_DO_CHILD_IO;
+      return net::OK;
+    }
+    next_state_ = STATE_CLOSE_CHILD;
+    return net::OK;
+  }
+  next_state_ = STATE_OPEN_CHILD;
+  return net::OK;
+}
+
+int SparseControlV3::DoOpenChild() {
+  // See if we are tracking this child.
+  if (!ChildPresent()) {
+    next_state_ = STATE_CREATE_CHILD;
+    return net::OK;
+  }
+
+  if (!entry_->backend_)
+    return net::ERR_FAILED;
+
+  next_state_ = STATE_OPEN_CHILD_COMPLETE;
+  return entry_->backend_->OpenEntry(key_, &child_, callback_);
+}
+
+int SparseControlV3::DoOpenChildComplete(int result) {
+  if (!child_) {
+    next_state_ = STATE_CREATE_CHILD;
+    return net::OK;
+  }
+
+  EntryImplV3* child = static_cast<EntryImplV3*>(child_);
+  if (!(CHILD_ENTRY & child->GetEntryFlags()) ||
+      child->GetDataSize(kSparseIndex) <
+          static_cast<int>(sizeof(child_data_))) {
+    return KillChildAndContinue();
+  }
+
+  scoped_refptr<net::WrappedIOBuffer> buf(
+      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
+
+  // Read signature.
+  next_state_ = STATE_READ_SIGNATURE_COMPLETE;
+  return child_->ReadData(kSparseIndex, 0, buf, sizeof(child_data_),
+                          callback_);
+}
+
+int SparseControlV3::DoReadSignatureComplete(int result) {
+  if (result != sizeof(child_data_))
+    return KillChildAndContinue();
+
+  if (child_data_.header.signature != sparse_header_.signature ||
+      child_data_.header.magic != kIndexMagicV3)
+    return KillChildAndContinue();
+
+  if (child_data_.header.last_block_len < 0 ||
+      child_data_.header.last_block_len > kBlockSize) {
+    // Make sure these values are always within range.
+    child_data_.header.last_block_len = 0;
+    child_data_.header.last_block = -1;
+  }
+
+  next_state_ = STATE_DO_CHILD_IO;
+  return net::OK;
+}
+
+int SparseControlV3::DoCloseChild() {
+  next_state_ = STATE_CLOSE_CHILD_COMPLETE;
+  scoped_refptr<net::WrappedIOBuffer> buf(
+      new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_)));
+
+  // Save the allocation bitmap before closing the child entry.
+  return child_->WriteData(kSparseIndex, 0, buf, sizeof(child_data_),
+                           callback_, false);
+}
+
+int SparseControlV3::DoCloseChildComplete(int result) {
+  if (result != sizeof(child_data_))
+    DLOG(ERROR) << "Failed to save child data";
+  child_->Close();
+  child_ = NULL;
+
+  DCHECK(valid_);
+  if (closing_ && user_callback_.is_null())
+    next_state_= STATE_WRITE_BITMAP;
+  else
+    next_state_ = STATE_OPEN_CHILD;
+
+  return net::OK;
+}
+
+// We were not able to open this child; see what we can do.
+int SparseControlV3::DoCreateChild() {
+  if (kReadOperation == operation_)
+    return 0;
+  if (kGetRangeOperation == operation_) {
+    next_state_ = STATE_DO_CHILD_IO;
+    return net::OK;
+  }
+
+  if (!entry_->backend_)
+    return net::ERR_FAILED;
+
+  next_state_ = STATE_CREATE_CHILD_COMPLETE;
+  return entry_->backend_->CreateEntry(key_, &child_, callback_);
+}
+
+int SparseControlV3::DoCreateChildComplete(int result) {
+  if (result != net::OK)
+    return net::ERR_CACHE_READ_FAILURE;
+
+  // Write signature.
+  InitChildData();
+  next_state_ = STATE_DO_CHILD_IO;
+  return net::OK;
+}
+
+int SparseControlV3::DoWriteBitmap() {
+  next_state_ = STATE_WRITE_BITMAP_COMPLETE;
+  scoped_refptr<net::IOBuffer> buf(new net::WrappedIOBuffer(
+      reinterpret_cast<const char*>(children_map_.GetMap())));
+
+  int len = children_map_.ArraySize() * 4;
+  return entry_->WriteData(kSparseIndex, sizeof(sparse_header_), buf, len,
+                           callback_, false);
+}
+
+int SparseControlV3::DoWriteBitmapComplete(int result) {
+  if (result != children_map_.ArraySize() * 4) {
+    DLOG(ERROR) << "Unable to save sparse map";
+  }
+  return net::OK;
+}
+
+int SparseControlV3::DoChildIO() {
+  if (!VerifyRange())
+    return 0;
+
+  int rv = 0;
+  switch (operation_) {
+    case kReadOperation:
+      LogChildOperationStart();
+      rv = child_->ReadData(kSparseData, child_offset_, user_buf_,
+                            child_len_, callback_);
+      break;
+    case kWriteOperation:
+      LogChildOperationStart();
+      rv = child_->WriteData(kSparseData, child_offset_, user_buf_,
+                             child_len_, callback_, false);
+      break;
+    case kGetRangeOperation:
+      rv = GetAvailableRangeImpl();
+      break;
+    default:
+      NOTREACHED();
+  }
+
+  next_state_ = STATE_DO_CHILD_IO_COMPLETE;
+  return rv;
+}
+
+int SparseControlV3::DoChildIOComplete(int result) {
+  LogChildOperationEnd(result);
+
+  if (result < 0)
+    return LogCompletion(result);
+
+  UpdateRange(result);
+
+  if (operation_ != kGetRangeOperation)
+    result_ += result;
+  offset_ += result;
+  buf_len_ -= result;
+
+  if (!buf_len_)
+    return LogCompletion(result_);
+
+  // We'll be reusing the user provided buffer for the next chunk.
+  if (buf_len_ && user_buf_)
+    user_buf_->DidConsume(result);
+
+  next_state_ = STATE_GET_CHILD_KEY;
+  return net::OK;
+}
+
+int SparseControlV3::DoClose() {
+  DCHECK(valid_);
+  DCHECK(user_callback_.is_null());
+  if (child_)
+    next_state_= STATE_CLOSE_CHILD;
+  else if (valid_)
+    next_state_= STATE_WRITE_BITMAP;
+
+  return net::OK;
+}
+
+std::string SparseControlV3::GenerateChildKey() {
+  return GenerateChildName(entry_->GetKey(), sparse_header_.signature,
+                           offset_ >> 20);
+}
+
+// We are deleting the child because something went wrong.
+int SparseControlV3::KillChildAndContinue() {
+  SetChildBit(false);
+  child_->Doom();
+  child_->Close();
+  child_ = NULL;
+  next_state_ = STATE_CREATE_CHILD;
+  return net::OK;
+}
+
+bool SparseControlV3::ChildPresent() {
+  int child_bit = static_cast<int>(offset_ >> 20);
+  if (children_map_.Size() <= child_bit)
+    return false;
+
+  return children_map_.Get(child_bit);
+}
+
+void SparseControlV3::SetChildBit(bool value) {
+  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, value);
+}
+
+bool SparseControlV3::VerifyRange() {
+  child_offset_ = static_cast<int>(offset_) & (kMaxEntrySize - 1);
+  child_len_ = std::min(buf_len_, kMaxEntrySize - child_offset_);
+
+  // We can write to (or get info from) 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.
+    DCHECK_GE(child_data_.header.last_block_len, 0);
+    DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize);
+    int partial_block_len = PartialBlockLength(start);
+    if (start == child_offset_ >> 10) {
+      // It looks like we don't have anything.
+      if (partial_block_len <= (child_offset_ & (kBlockSize - 1)))
+        return false;
+    }
+
+    // We have the first part.
+    child_len_ = (start << 10) - child_offset_;
+    if (partial_block_len) {
+      // We may have a few extra bytes.
+      child_len_ = std::min(child_len_ + partial_block_len, buf_len_);
+    }
+    // There is no need to read more after this one.
+    buf_len_ = child_len_;
+  }
+  return true;
+}
+
+void SparseControlV3::UpdateRange(int result) {
+  if (result <= 0 || operation_ != kWriteOperation)
+    return;
+
+  DCHECK_GE(child_data_.header.last_block_len, 0);
+  DCHECK_LT(child_data_.header.last_block_len, kMaxEntrySize);
+
+  // Write the bitmap.
+  int first_bit = child_offset_ >> 10;
+  int block_offset = child_offset_ & (kBlockSize - 1);
+  if (block_offset && (child_data_.header.last_block != first_bit ||
+                       child_data_.header.last_block_len < block_offset)) {
+    // The first block is not completely filled; ignore it.
+    first_bit++;
+  }
+
+  int last_bit = (child_offset_ + result) >> 10;
+  block_offset = (child_offset_ + result) & (kBlockSize - 1);
+
+  // This condition will hit with the following criteria:
+  // 1. The first byte doesn't follow the last write.
+  // 2. The first byte is in the middle of a block.
+  // 3. The first byte and the last byte are in the same block.
+  if (first_bit > last_bit)
+    return;
+
+  if (block_offset && !child_map_.Get(last_bit)) {
+    // The last block is not completely filled; save it for later.
+    child_data_.header.last_block = last_bit;
+    child_data_.header.last_block_len = block_offset;
+  } else {
+    child_data_.header.last_block = -1;
+  }
+
+  child_map_.SetRange(first_bit, last_bit, true);
+}
+
+int SparseControlV3::PartialBlockLength(int block_index) const {
+  if (block_index == child_data_.header.last_block)
+    return child_data_.header.last_block_len;
+
+  // This may be the last stored index.
+  int entry_len = child_->GetDataSize(kSparseData);
+  if (block_index == entry_len >> 10)
+    return entry_len & (kBlockSize - 1);
+
+  // This is really empty.
+  return 0;
+}
+
+void SparseControlV3::InitChildData() {
+  // We know the real type of child_.
+  EntryImplV3* child = static_cast<EntryImplV3*>(child_);
+  child->SetEntryFlags(CHILD_ENTRY);
+
+  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_),
+                             CompletionCallback(), false);
+  if (rv != sizeof(child_data_))
+    DLOG(ERROR) << "Failed to save child data";
+  SetChildBit(true);
+}
+
+int SparseControlV3::GetAvailableRangeImpl() {
+  if (!child_)
+    return child_len_;  // Move on to the next child.
+
+  // Check that there are no holes in this range.
+  int last_bit = (child_offset_ + child_len_ + 1023) >> 10;
+  int start = child_offset_ >> 10;
+  int partial_start_bytes = PartialBlockLength(start);
+  int found = start;
+  int bits_found = child_map_.FindBits(&found, last_bit, true);
+
+  // We don't care if there is a partial block in the middle of the range.
+  int block_offset = child_offset_ & (kBlockSize - 1);
+  if (!bits_found && partial_start_bytes <= block_offset)
+    return child_len_;
+
+  // We are done. Just break the loop and reset result_ to our real result.
+  range_found_ = true;
+
+  // found now points to the first 1. Lets see if we have zeros before it.
+  int empty_start = std::max((found << 10) - child_offset_, 0);
+
+  int bytes_found = bits_found << 10;
+  bytes_found += PartialBlockLength(found + bits_found);
+
+  if (start == found)
+    bytes_found -= block_offset;
+
+  // If the user is searching past the end of this child, bits_found is the
+  // right result; otherwise, we have some empty space at the start of this
+  // query that we have to subtract from the range that we searched.
+  result_ = std::min(bytes_found, child_len_ - empty_start);
+
+  if (!bits_found) {
+    result_ = std::min(partial_start_bytes - block_offset, child_len_);
+    empty_start = 0;
+  }
+
+  // Only update offset_ when this query found zeros at the start.
+  if (empty_start)
+    offset_ += empty_start;
+
+  // This will actually break the loop.
+  buf_len_ = 0;
+  return 0;
+}
+
+void SparseControlV3::LogChildOperationStart() {
+  net::NetLog::EventType type = (operation_ == kReadOperation) ?
+                                    net::NetLog::TYPE_SPARSE_READ_CHILD_DATA :
+                                    net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA;
+
+  if (entry_->net_log().IsLoggingAllEvents()) {
+    disk_cache::EntryImplV3* entry =
+        reinterpret_cast<disk_cache::EntryImplV3*>(child_);
+    entry_->net_log().BeginEvent(
+        type,
+        CreateNetLogSparseReadWriteCallback(entry->net_log().source(),
+                                            child_len_));
+  }
+}
+
+void SparseControlV3::LogChildOperationEnd(int result) {
+  if (entry_->net_log().IsLoggingAllEvents()) {
+    net::NetLog::EventType event_type;
+    switch (operation_) {
+      case disk_cache::SparseControlV3::kReadOperation:
+        event_type = net::NetLog::TYPE_SPARSE_READ_CHILD_DATA;
+        break;
+      case disk_cache::SparseControlV3::kWriteOperation:
+        event_type = net::NetLog::TYPE_SPARSE_WRITE_CHILD_DATA;
+        break;
+      case disk_cache::SparseControlV3::kGetRangeOperation:
+        return;
+      default:
+        NOTREACHED();
+        return;
+    }
+    entry_->net_log().EndEventWithNetErrorCode(event_type, result);
+  }
+}
+
+int SparseControlV3::LogCompletion(int result) {
+  if (!entry_->net_log().IsLoggingAllEvents())
+    return result;
+
+  if (kGetRangeOperation == operation_) {
+    entry_->net_log().EndEvent(
+        net::NetLog::TYPE_SPARSE_GET_RANGE,
+        CreateNetLogGetAvailableRangeResultCallback(offset_, result));
+  } else {
+    entry_->net_log().EndEvent(GetSparseEventType(operation_));
+  }
+  return result;
+}
+
+void SparseControlV3::HandleResult(int result) {
+  if (!result && result_)
+    result = result_;
+
+  if (result > 0 && operation_ == kGetRangeOperation)
+    *range_start_ = offset_;
+
+  user_buf_ = NULL;
+  operation_ = kNoOperation;
+  next_state_ = STATE_NONE;
+
+  if (user_callback_.is_null()) {
+    if (closing_) {
+      closing_ = false;
+      entry_->Release();  // Don't touch object after this line.
+    }
+    return;
+  }
+
+  CompletionCallback cb = user_callback_;
+  user_callback_.Reset();
+  bool closing = closing_;
+  DCHECK(!closing_ || !entry_->HasOneRef());
+
+  entry_->Release();  // Don't touch object after this line.
+  cb.Run(result);
+
+  if (closing) {
+    // This object is not gone yet, but there's more work to do before the
+    // destructor runs.
+    next_state_ = STATE_CLOSE;
+    int rv = DoLoop(net::OK);
+  }
+}
+
+void SparseControlV3::HanldeAbortCallbacks() {
+  for (size_t i = 0; i < abort_callbacks_.size(); i++) {
+    // Releasing all references to entry_ may result in the destruction of this
+    // object so we should not be touching it after the last Release().
+    CompletionCallback cb = abort_callbacks_[i];
+    if (i == abort_callbacks_.size() - 1)
+      abort_callbacks_.clear();
+
+    entry_->Release();  // Don't touch object after this line.
+    cb.Run(net::OK);
+  }
+}
+
+void SparseControlV3::OnIOComplete(int result) {
+  DCHECK_NE(net::ERR_IO_PENDING, result);
+
+  if (abort_) {
+    // We'll return the current result of the operation, which may be less than
+    // the bytes to read or write, but the user cancelled the operation.
+    abort_ = false;
+    if (entry_->net_log().IsLoggingAllEvents()) {
+      entry_->net_log().AddEvent(net::NetLog::TYPE_CANCELLED);
+      entry_->net_log().EndEvent(GetSparseEventType(operation_));
+    }
+    // We have an indirect reference to this object for every callback so if
+    // there is only one callback, we may delete this object before reaching
+    // HanldeAbortCallbacks.
+    bool has_abort_callbacks = !abort_callbacks_.empty();
+    HandleResult(result);
+    if (has_abort_callbacks)
+      HanldeAbortCallbacks();
+    return;
+  }
+
+  DoLoop(result);
+}
+
+}  // namespace disk_cache