Disk cache: Add explicit support for eviction / deletion

of sparse entries.

I started to add code to modify the children_map of the
parent entry when a child is evicted but that ended up
being too much trouble for too little gain. We have to be
prepared to handle the case of not finding a child entry
because there is no way to make sure that the process
doesn't go away at any time, so adding a lot of complexity
just to avoid an extra entry lookup is just not worth it.

On the other hand, potentially freeing up a lot of space when
a sparse entry is deleted (insetad of just waiting for the
eviction code to do the cleanup) seems like a good thing.

BUG=12258
TEST=unittest

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

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

7 files changed, 279 insertions, 13 deletions

diff --git a/net/disk_cache/block_files.cc b/net/disk_cache/block_files.cc
index 63a7c2e..8c8d2e2 100644
--- a/net/disk_cache/block_files.cc
+++ b/net/disk_cache/block_files.cc
@@ -261,7 +261,10 @@ bool BlockFiles::OpenBlockFile(int index) {
 }
 
 MappedFile* BlockFiles::GetFile(Addr address) {
-  CHECK(block_files_.size() >= 4);
+  DCHECK(block_files_.size() >= 4);
+  DCHECK(address.is_block_file() || !address.is_initialized());
+  if (!address.is_initialized())
+    return NULL;
 
   int file_index = address.FileNumber();
   if (static_cast<unsigned int>(file_index) >= block_files_.size() ||
diff --git a/net/disk_cache/disk_format.h b/net/disk_cache/disk_format.h
index d1f7fed..c98fc34 100644
--- a/net/disk_cache/disk_format.h
+++ b/net/disk_cache/disk_format.h
@@ -123,7 +123,8 @@ struct EntryStore {
   CacheAddr   long_key;           // Optional address of a long key.
   int32       data_size[4];       // We can store up to 4 data streams for each
   CacheAddr   data_addr[4];       // entry.
-  int32       pad[6];
+  uint32      flags;              // Any combination of EntryFlags.
+  int32       pad[5];
   char        key[256 - 24 * 4];  // null terminated
 };
 
@@ -138,6 +139,12 @@ enum EntryState {
   ENTRY_DOOMED      // The entry was doomed.
 };
 
+// Flags that can be applied to an entry.
+enum EntryFlags {
+  PARENT_ENTRY = 1,         // This entry has children (sparse) entries.
+  CHILD_ENTRY = 1 << 1      // Child entry that stores sparse data.
+};
+
 #pragma pack(push, 4)
 // Rankings information for a given entry.
 struct RankingsNode {
diff --git a/net/disk_cache/entry_impl.cc b/net/disk_cache/entry_impl.cc
index 4c17cbb..75fb92e5 100644
--- a/net/disk_cache/entry_impl.cc
+++ b/net/disk_cache/entry_impl.cc
@@ -453,6 +453,11 @@ void EntryImpl::InternalDoom() {
 void EntryImpl::DeleteEntryData(bool everything) {
   DCHECK(doomed_ || !everything);
 
+  if (GetEntryFlags() & PARENT_ENTRY) {
+    // We have some child entries that must go away.
+    SparseControl::DeleteChildren(this);
+  }
+
   if (GetDataSize(0))
     CACHE_UMA(COUNTS, "DeleteHeader", 0, GetDataSize(0));
   if (GetDataSize(1))
@@ -834,6 +839,38 @@ int EntryImpl::InitSparseData() {
   return result;
 }
 
+void EntryImpl::SetEntryFlags(uint32 flags) {
+  entry_.Data()->flags |= flags;
+  entry_.set_modified();
+}
+
+uint32 EntryImpl::GetEntryFlags() {
+  return entry_.Data()->flags;
+}
+
+void EntryImpl::GetData(int index, char** buffer, Addr* address) {
+  if (user_buffers_[index].get()) {
+    // The data is already in memory, just copy it an we're done.
+    int data_len = entry_.Data()->data_size[index];
+    DCHECK(data_len <= kMaxBlockSize);
+    *buffer = new char[data_len];
+    memcpy(*buffer, user_buffers_[index].get(), data_len);
+    return;
+  }
+
+  // Bad news: we'd have to read the info from disk so instead we'll just tell
+  // the caller where to read from.
+  *buffer = NULL;
+  address->set_value(entry_.Data()->data_addr[index]);
+  if (address->is_initialized()) {
+    // Prevent us from deleting the block from the backing store.
+    backend_->ModifyStorageSize(entry_.Data()->data_size[index] -
+                                    unreported_size_[index], 0);
+    entry_.Data()->data_addr[index] = 0;
+    entry_.Data()->data_size[index] = 0;
+  }
+}
+
 void EntryImpl::ReportIOTime(Operation op, const base::Time& start) {
   int group = backend_->GetSizeGroup();
   switch (op) {
diff --git a/net/disk_cache/entry_impl.h b/net/disk_cache/entry_impl.h
index ad254e0..da82396 100644
--- a/net/disk_cache/entry_impl.h
+++ b/net/disk_cache/entry_impl.h
@@ -150,6 +150,22 @@ class EntryImpl : public Entry, public base::RefCounted<EntryImpl> {
   // Initializes the sparse control object. Returns a net error code.
   int InitSparseData();
 
+  // Adds the provided |flags| to the current EntryFlags for this entry.
+  void SetEntryFlags(uint32 flags);
+
+  // Returns the current EntryFlags for this entry.
+  uint32 GetEntryFlags();
+
+  // Gets the data stored at the given index. If the information is in memory,
+  // a buffer will be allocated and the data will be copied to it (the caller
+  // can find out the size of the buffer before making this call). Otherwise,
+  // the cache address of the data will be returned, and that address will be
+  // removed from the regular book keeping of this entry so the caller is
+  // responsible for deleting the block (or file) from the backing store at some
+  // point; there is no need to report any storage-size change, only to do the
+  // actual cleanup.
+  void GetData(int index, char** buffer, Addr* address);
+
   // Generates a histogram for the time spent working on this operation.
   void ReportIOTime(Operation op, const base::Time& start);
 
diff --git a/net/disk_cache/entry_unittest.cc b/net/disk_cache/entry_unittest.cc
index bf111ec..86dd41e 100644
--- a/net/disk_cache/entry_unittest.cc
+++ b/net/disk_cache/entry_unittest.cc
@@ -38,6 +38,7 @@ class DiskCacheEntryTest : public DiskCacheTestWithCache {
   void BasicSparseIO(bool async);
   void HugeSparseIO(bool async);
   void GetAvailableRange();
+  void DoomSparseEntry();
 };
 
 void DiskCacheEntryTest::InternalSyncIO() {
@@ -826,7 +827,7 @@ TEST_F(DiskCacheEntryTest, MemoryOnlyDoomedEntry) {
 
 // Test that child entries in a memory cache backend are not visible from
 // enumerations.
-TEST_F(DiskCacheEntryTest, MemoryOnlyEnumerationWithSlaveEntries) {
+TEST_F(DiskCacheEntryTest, MemoryOnlyEnumerationWithSparseEntries) {
   SetMemoryOnlyMode();
   InitCache();
 
@@ -1128,3 +1129,59 @@ TEST_F(DiskCacheEntryTest, MemoryOnlyMisalignedGetAvailableRange) {
 
   entry->Close();
 }
+
+void DiskCacheEntryTest::DoomSparseEntry() {
+  std::string key1("the first key");
+  std::string key2("the second key");
+  disk_cache::Entry *entry1, *entry2;
+  ASSERT_TRUE(cache_->CreateEntry(key1, &entry1));
+  ASSERT_TRUE(cache_->CreateEntry(key2, &entry2));
+
+  const int kSize = 4 * 1024;
+  scoped_refptr<net::IOBuffer> buf = new net::IOBuffer(kSize);
+  CacheTestFillBuffer(buf->data(), kSize, false);
+
+  int64 offset = 1024;
+  // Write to a bunch of ranges.
+  for (int i = 0; i < 12; i++) {
+    EXPECT_EQ(kSize, entry1->WriteSparseData(offset, buf, kSize, NULL));
+    // Keep the second map under the default size.
+    if (i < 9)
+      EXPECT_EQ(kSize, entry2->WriteSparseData(offset, buf, kSize, NULL));
+    offset *= 4;
+  }
+
+  if (memory_only_)
+    EXPECT_EQ(2, cache_->GetEntryCount());
+  else
+    EXPECT_EQ(15, cache_->GetEntryCount());
+
+  // Doom the first entry while it's still open.
+  entry1->Doom();
+  entry1->Close();
+  entry2->Close();
+
+  // Doom the second entry after it's fully saved.
+  EXPECT_TRUE(cache_->DoomEntry(key2));
+
+  // Make sure we do all needed work. This may fail for entry2 if between Close
+  // and DoomEntry the system decides to remove all traces of the file from the
+  // system cache so we don't see that there is pending IO.
+  MessageLoop::current()->RunAllPending();
+
+  if (memory_only_)
+    EXPECT_EQ(0, cache_->GetEntryCount());
+  else
+    EXPECT_EQ(0, cache_->GetEntryCount());
+}
+
+TEST_F(DiskCacheEntryTest, DoomSparseEntry) {
+  InitCache();
+  DoomSparseEntry();
+}
+
+TEST_F(DiskCacheEntryTest, DISABLED_MemoryOnlyDoomSparseEntry) {
+  SetMemoryOnlyMode();
+  InitCache();
+  DoomSparseEntry();
+}
diff --git a/net/disk_cache/sparse_control.cc b/net/disk_cache/sparse_control.cc
index 461e0fa..4035bd3 100644
--- a/net/disk_cache/sparse_control.cc
+++ b/net/disk_cache/sparse_control.cc
@@ -5,12 +5,14 @@
 #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;
 
@@ -22,6 +24,106 @@ 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;
+
+// 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);
+}
+
+// This class deletes the children of a sparse entry.
+class ChildrenDeleter
+    : public base::RefCounted<ChildrenDeleter>,
+      public disk_cache::FileIOCallback {
+ public:
+  ChildrenDeleter(disk_cache::BackendImpl* backend, const std::string& name)
+      : backend_(backend), name_(name) {}
+
+  virtual void OnFileIOComplete(int bytes_copied);
+
+  // Two ways of deleting the children: if we have the children map, use Start()
+  // directly, otherwise pass the data address to ReadData().
+  void Start(char* buffer, int len);
+  void ReadData(disk_cache::Addr address, int len);
+
+ private:
+  void DeleteChildren();
+
+  disk_cache::BackendImpl* backend_;
+  std::string name_;
+  disk_cache::Bitmap children_map_;
+  int64 signature_;
+  scoped_array<char> buffer_;
+  DISALLOW_EVIL_CONSTRUCTORS(ChildrenDeleter);
+};
+
+// This is the callback of the file operation.
+void ChildrenDeleter::OnFileIOComplete(int bytes_copied) {
+  char* buffer = buffer_.release();
+  Start(buffer, bytes_copied);
+}
+
+void ChildrenDeleter::Start(char* buffer, int len) {
+  buffer_.reset(buffer);
+  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);
+  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);
+  buffer_.reset();
+
+  DeleteChildren();
+}
+
+void ChildrenDeleter::ReadData(disk_cache::Addr address, int len) {
+  DCHECK(address.is_block_file());
+  disk_cache::File* file(backend_->File(address));
+  if (!file)
+    return Release();
+
+  size_t file_offset = address.start_block() * address.BlockSize() +
+                       disk_cache::kBlockHeaderSize;
+
+  buffer_.reset(new char[len]);
+  bool completed;
+  if (!file->Read(buffer_.get(), len, file_offset, this, &completed))
+    return Release();
+
+  if (completed)
+    OnFileIOComplete(len);
+
+  // And wait until OnFileIOComplete gets called.
+}
+
+void ChildrenDeleter::DeleteChildren() {
+  int child_id = 0;
+  if (!children_map_.FindNextSetBit(&child_id)) {
+    // We are done. Just delete this object.
+    return Release();
+  }
+  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 disk_cache {
@@ -118,10 +220,43 @@ int SparseControl::GetAvailableRange(int64 offset, int len, int64* start) {
   return result < 0 ? result : 0;  // Don't mask error codes to the caller.
 }
 
+// Static
+void SparseControl::DeleteChildren(EntryImpl* 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;
+
+  char* buffer;
+  Addr address;
+  entry->GetData(kSparseIndex, &buffer, &address);
+  if (!buffer && !address.is_initialized())
+    return;
+
+  ChildrenDeleter* deleter = new ChildrenDeleter(entry->backend_,
+                                                 entry->GetKey());
+  // The object will self destruct when finished.
+  deleter->AddRef();
+
+  if (buffer) {
+    MessageLoop::current()->PostTask(FROM_HERE, NewRunnableMethod(
+        deleter, &ChildrenDeleter::Start, buffer, data_len));
+  } else {
+    MessageLoop::current()->PostTask(FROM_HERE, NewRunnableMethod(
+        deleter, &ChildrenDeleter::ReadData, address, data_len));
+  }
+}
+
 // 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.
+  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();
@@ -139,6 +274,8 @@ int SparseControl::CreateSparseEntry() {
     DLOG(ERROR) << "Unable to save sparse_header_";
     return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
   }
+
+  entry_->SetEntryFlags(PARENT_ENTRY);
   return net::OK;
 }
 
@@ -150,11 +287,12 @@ int SparseControl::OpenSparseEntry(int data_len) {
   if (entry_->GetDataSize(kSparseData))
     return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
 
-  // TODO(rvargas): Set/check a flag in EntryStore.
+  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 > 8 * 1024 || map_len % 4)
+  if (map_len > kMaxMapSize || map_len % 4)
     return net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
 
   scoped_refptr<net::IOBuffer> buf =
@@ -216,7 +354,11 @@ bool SparseControl::OpenChild() {
     return true;
   }
 
-  // TODO(rvargas): Set/check a flag in EntryStore.
+  EntryImpl* child = static_cast<EntryImpl*>(child_);
+  if (!(CHILD_ENTRY & child->GetEntryFlags())) {
+    result_ = net::ERR_CACHE_OPERATION_NOT_SUPPORTED;
+    return false;
+  }
 
   scoped_refptr<net::WrappedIOBuffer> buf =
       new net::WrappedIOBuffer(reinterpret_cast<char*>(&child_data_));
@@ -250,17 +392,14 @@ void SparseControl::CloseChild() {
   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);
+  return GenerateChildName(entry_->GetKey(), sparse_header_.signature,
+                           offset_ >> 20);
 }
 
 bool SparseControl::ChildPresent() {
   int child_bit = static_cast<int>(offset_ >> 20);
-  if (children_map_.Size() < child_bit)
+  if (children_map_.Size() <= child_bit)
     return false;
 
   return children_map_.Get(child_bit);
@@ -326,6 +465,10 @@ void SparseControl::UpdateRange(int result) {
 }
 
 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_;
 
diff --git a/net/disk_cache/sparse_control.h b/net/disk_cache/sparse_control.h
index 0c696ea..c93e5e4 100644
--- a/net/disk_cache/sparse_control.h
+++ b/net/disk_cache/sparse_control.h
@@ -63,6 +63,9 @@ class SparseControl {
   // Implements Entry::GetAvailableRange().
   int GetAvailableRange(int64 offset, int len, int64* start);
 
+  // Deletes the children entries of |entry|.
+  static void DeleteChildren(EntryImpl* entry);
+
  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