Disk cache: Add support for having a sparse entry block that...

net/disk_cache/sparse_control.cc

 // 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/message_loop.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"
 #include "net/disk_cache/file.h"
 
 using base::Time;
 
 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 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 StringPrintf("Range_%s:%llx:%llx", base_name.c_str(), signature,
                       child_id);
 }
@@ skipping 77 matching lines @@
   }
   std::string child_name = GenerateChildName(name_, signature_, child_id);
   backend_->DoomEntry(child_name);
   children_map_.Set(child_id, false);
 
   // Post a task to delete the next child.
   MessageLoop::current()->PostTask(FROM_HERE, NewRunnableMethod(
       this, &ChildrenDeleter::DeleteChildren));
 }
 
-}
+}  // namespace.
 
 namespace disk_cache {
 
 SparseControl::~SparseControl() {
   if (child_)
     CloseChild();
   if (init_)
     WriteSparseData();
 }
 
@@ skipping 191 matching lines @@
   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 (!child_present) {
-    if (kReadOperation == operation_)
-      return false;
-    if (kGetRangeOperation == operation_)
-      return true;
-  }
-
-  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;
-  }
+  if (!child_present || !entry_->backend_->OpenEntry(key, &child_))
+    return ContinueWithoutChild(key);
 
   EntryImpl* child = static_cast<EntryImpl*>(child_);
-  if (!(CHILD_ENTRY & child->GetEntryFlags())) {
-    result_ = net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
-    return false;
-  }
+  if (!(CHILD_ENTRY & child->GetEntryFlags()) ||
+      child->GetDataSize(kSparseIndex) <
+          static_cast<int>(sizeof(child_data_)))
+    return KillChildAndContinue(key, false);
 
   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;
-  }
+  if (rv != sizeof(child_data_))
+    return KillChildAndContinue(key, true);  // This is a fatal failure.
 
-  // 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;
+  if (child_data_.header.signature != sparse_header_.signature ||
+      child_data_.header.magic != kIndexMagic)
+    return KillChildAndContinue(key, false);
+
+  if (child_data_.header.last_block_len < 0 ||
+      child_data_.header.last_block_len > kBlockSize) {
+    // Make sure this values are always within range.
+    child_data_.header.last_block_len = 0;
+    child_data_.header.last_block = -1;
   }
 
   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;
 }
 
 std::string SparseControl::GenerateChildKey() {
   return GenerateChildName(entry_->GetKey(), sparse_header_.signature,
                            offset_ >> 20);
 }
 
+// We are deleting the child because something went wrong.
+bool SparseControl::KillChildAndContinue(const std::string& key, bool fatal) {
+  SetChildBit(false);
+  child_->Doom();
+  child_->Close();
+  child_ = NULL;
+  if (fatal) {
+    result_ = net::ERR_CACHE_READ_FAILURE;
+    return false;
+  }
+  return ContinueWithoutChild(key);
+}
+
+// We were not able to open this child; see what we can do.
+bool SparseControl::ContinueWithoutChild(const std::string& key) {
+  if (kReadOperation == operation_)
+    return false;
+  if (kGetRangeOperation == operation_)
+    return true;
+
+  if (!entry_->backend_->CreateEntry(key, &child_)) {
+    child_ = NULL;
+    result_ = net::ERR_CACHE_READ_FAILURE;
+    return false;
+  }
+  // Write signature.
+  InitChildData();
+  return true;
+}
+
 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() {
+void SparseControl::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, true);
+  children_map_.Set(child_bit, value);
 }
 
 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_);
+  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.
-    if (start == child_offset_ >> 10)
-      return false;
+    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.
-    // TODO(rvargas): Avoid coming back here again after the actual read.
     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 SparseControl::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 last_bit = (child_offset_ + result + 1023) >> 10;
-  child_map_.SetRange(child_offset_ >> 10, last_bit, true);
+  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++;
+  }
 
-  // TODO(rvargas): Keep track of partial writes so that we don't consider the
-  // whole block to be present.
+  int last_bit = (child_offset_ + result) >> 10;
+  block_offset = (child_offset_ + result) & (kBlockSize - 1);
+
+  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 SparseControl::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 SparseControl::InitChildData() {
   // We know the real type of child_.
   EntryImpl* child = static_cast<EntryImpl*>(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_),
                              NULL, false);
   if (rv != sizeof(child_data_))
     DLOG(ERROR) << "Failed to save child data";
-  SetChildBit();
+  SetChildBit(true);
 }
 
 void SparseControl::DoChildrenIO() {
   while (DoChildIO()) continue;
 
   if (pending_ && finished_)
     DoUserCallback();
 }
 
 bool SparseControl::DoChildIO() {
@@ skipping 32 matching lines @@
     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;
   }
+  if (!rv)
+    return false;
 
   DoChildIOCompleted(rv);
   return true;
 }
 
 int SparseControl::DoGetAvailableRange() {
   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 bits_found = child_map_.FindBits(&start, last_bit, true);
 
-  if (!bits_found)
+  // 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;
 
   // start now points to the first 1. Lets see if we have zeros before it.
   int empty_start = (start << 10) - child_offset_;
 
+  int bytes_found = bits_found << 10;
+  bytes_found += PartialBlockLength(start + bits_found);
+
   // 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 substarct from the range that we searched.
-  result_ = std::min(bits_found << 10, child_len_ - empty_start);
+  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;
 }
 
@@ skipping 29 matching lines @@
   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