Introduce parent and child entries for MemEntryImpl

Defines enums for kParentEntry and kChildEntry in
MemEntryImpl. Also has code in MemBackendImpl to
create a slave entry. Parent entries are non-sparse
entries until sparse API are called on them, and
they would start to keep a list of child entries.
Child entries hold partial content and are not
susposed to be accessible from the public and
are managed by the parent entry that created it.
Child entries are registered in the backend's
ranking list to allow individual eviction. More
details about how child entries are to be used
are in the comments.

TEST=DiskCacheEntryTest.MemoryOnlyEnumerationWithSlaveEntries

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

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

5 files changed, 167 insertions, 32 deletions

diff --git a/net/disk_cache/entry_unittest.cc b/net/disk_cache/entry_unittest.cc
index 17bb4e9..6daaf14 100644
--- a/net/disk_cache/entry_unittest.cc
+++ b/net/disk_cache/entry_unittest.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.
 
@@ -11,6 +11,7 @@
 #include "net/disk_cache/disk_cache_test_base.h"
 #include "net/disk_cache/disk_cache_test_util.h"
 #include "net/disk_cache/entry_impl.h"
+#include "net/disk_cache/mem_entry_impl.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 using base::Time;
@@ -819,3 +820,46 @@ TEST_F(DiskCacheEntryTest, MemoryOnlyDoomedEntry) {
   InitCache();
   DoomEntry();
 }
+
+// Test that child entries in a memory cache backend are not visible from
+// enumerations.
+TEST_F(DiskCacheEntryTest, MemoryOnlyEnumerationWithSlaveEntries) {
+  SetMemoryOnlyMode();
+  SetDirectMode();
+  SetMaxSize(1024);
+  InitCache();
+
+  disk_cache::Entry* entry;
+  disk_cache::MemEntryImpl* parent_entry;
+
+  ASSERT_TRUE(cache_->CreateEntry("parent", &entry));
+  parent_entry = reinterpret_cast<disk_cache::MemEntryImpl*>(entry);
+  EXPECT_EQ(disk_cache::MemEntryImpl::kParentEntry, parent_entry->type());
+  parent_entry->Close();
+
+  disk_cache::MemEntryImpl* child_entry =
+      new disk_cache::MemEntryImpl(mem_cache_);
+  // TODO(hclam): we shouldn't create a child entry explicit. Once a parent
+  // entry can be triggered to create a child entry, we should change this
+  // to use another public method to do the creation.
+  EXPECT_TRUE(child_entry->CreateChildEntry(parent_entry));
+  EXPECT_EQ(disk_cache::MemEntryImpl::kChildEntry, child_entry->type());
+
+  // Perform the enumerations.
+  void* iter = NULL;
+  int count = 0;
+  while (cache_->OpenNextEntry(&iter, &entry)) {
+    ASSERT_TRUE(entry != NULL);
+    disk_cache::MemEntryImpl* mem_entry =
+        reinterpret_cast<disk_cache::MemEntryImpl*>(entry);
+    EXPECT_EQ(disk_cache::MemEntryImpl::kParentEntry, mem_entry->type());
+    EXPECT_TRUE(mem_entry == parent_entry);
+    mem_entry->Close();
+    ++count;
+  }
+  EXPECT_EQ(1, count);
+
+  // TODO(hclam): remove this when parent entry can doom child entries
+  // internally. Now we have to doom this child entry manually.
+  child_entry->Doom();
+}
diff --git a/net/disk_cache/mem_backend_impl.cc b/net/disk_cache/mem_backend_impl.cc
index 0b8802a..c3d3a26 100644
--- a/net/disk_cache/mem_backend_impl.cc
+++ b/net/disk_cache/mem_backend_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.
 
@@ -128,6 +128,9 @@ bool MemBackendImpl::DoomEntry(const std::string& key) {
 }
 
 void MemBackendImpl::InternalDoomEntry(MemEntryImpl* entry) {
+  // Only parent entries can be passed into this method.
+  DCHECK(entry->type() == MemEntryImpl::kParentEntry);
+
   rankings_.Remove(entry);
   EntryMap::iterator it = entries_.find(entry->GetKey());
   if (it != entries_.end())
@@ -162,38 +165,33 @@ bool MemBackendImpl::DoomEntriesBetween(const Time initial_time,
     if (node->GetLastUsed() < initial_time)
       break;
 
-    if (node->GetLastUsed() < end_time) {
+    if (node->GetLastUsed() < end_time)
       node->Doom();
-    }
   }
 
   return true;
 }
 
-// We use OpenNextEntry to retrieve elements from the cache, until we get
-// entries that are too old.
 bool MemBackendImpl::DoomEntriesSince(const Time initial_time) {
   for (;;) {
-    Entry* entry;
-    void* iter = NULL;
-    if (!OpenNextEntry(&iter, &entry))
-      return true;
+    // Get the entry in the front.
+    Entry* entry = rankings_.GetNext(NULL);
 
-    if (initial_time > entry->GetLastUsed()) {
-      entry->Close();
-      EndEnumeration(&iter);
+    // Break the loop when there are no more entries or the entry is too old.
+    if (!entry || entry->GetLastUsed() < initial_time)
       return true;
-    }
-
     entry->Doom();
-    entry->Close();
-    EndEnumeration(&iter);  // Dooming the entry invalidates the iterator.
   }
 }
 
 bool MemBackendImpl::OpenNextEntry(void** iter, Entry** next_entry) {
   MemEntryImpl* current = reinterpret_cast<MemEntryImpl*>(*iter);
   MemEntryImpl* node = rankings_.GetNext(current);
+  // We should never return a child entry so iterate until we hit a parent
+  // entry.
+  while (node && node->type() != MemEntryImpl::kParentEntry) {
+    node = rankings_.GetNext(node);
+  }
   *next_entry = node;
   *iter = node;
 
@@ -252,4 +250,12 @@ int MemBackendImpl::MaxFileSize() const {
   return max_size_ / 8;
 }
 
+void MemBackendImpl::InsertIntoRankingList(MemEntryImpl* entry) {
+  rankings_.Insert(entry);
+}
+
+void MemBackendImpl::RemoveFromRankingList(MemEntryImpl* entry) {
+  rankings_.Remove(entry);
+}
+
 }  // namespace disk_cache
diff --git a/net/disk_cache/mem_backend_impl.h b/net/disk_cache/mem_backend_impl.h
index 2c23a67..66683a2 100644
--- a/net/disk_cache/mem_backend_impl.h
+++ b/net/disk_cache/mem_backend_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.
 
@@ -17,7 +17,7 @@ namespace disk_cache {
 class MemEntryImpl;
 
 // This class implements the Backend interface. An object of this class handles
-// the operations of the cache without writting to disk.
+// the operations of the cache without writing to disk.
 class MemBackendImpl : public Backend {
  public:
   MemBackendImpl() : max_size_(0), current_size_(0) {}
@@ -55,6 +55,15 @@ class MemBackendImpl : public Backend {
   // Returns the maximum size for a file to reside on the cache.
   int MaxFileSize() const;
 
+  // Insert an MemEntryImpl into the ranking list. This method is only called
+  // from MemEntryImpl to insert child entries. The reference can be removed
+  // by calling RemoveFromRankingList(|entry|).
+  void InsertIntoRankingList(MemEntryImpl* entry);
+
+  // Remove |entry| from ranking list. This method is only called from
+  // MemEntryImpl to remove a child entry from the ranking list.
+  void RemoveFromRankingList(MemEntryImpl* entry);
+
  private:
   // Deletes entries from the cache until the current size is below the limit.
   // If empty is true, the whole cache will be trimmed, regardless of being in
diff --git a/net/disk_cache/mem_entry_impl.cc b/net/disk_cache/mem_entry_impl.cc
index ea55a18..4905785 100644
--- a/net/disk_cache/mem_entry_impl.cc
+++ b/net/disk_cache/mem_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.
 
@@ -17,6 +17,7 @@ MemEntryImpl::MemEntryImpl(MemBackendImpl* backend) {
   doomed_ = false;
   backend_ = backend;
   ref_count_ = 0;
+  parent_ = NULL;
   next_ = NULL;
   prev_ = NULL;
   for (int i = 0; i < NUM_STREAMS; i++)
@@ -33,12 +34,25 @@ bool MemEntryImpl::CreateEntry(const std::string& key) {
   key_ = key;
   last_modified_ = Time::Now();
   last_used_ = Time::Now();
+  type_ = kParentEntry;
   Open();
   backend_->ModifyStorageSize(0, static_cast<int32>(key.size()));
   return true;
 }
 
+bool MemEntryImpl::CreateChildEntry(MemEntryImpl* parent) {
+  parent_ = parent;
+  last_modified_ = Time::Now();
+  last_used_ = Time::Now();
+  type_ = kChildEntry;
+  // Insert this to the backend's ranking list.
+  backend_->InsertIntoRankingList(this);
+  return true;
+}
+
 void MemEntryImpl::Close() {
+  // Only a parent entry can be closed.
+  DCHECK(type_ == kParentEntry);
   ref_count_--;
   DCHECK(ref_count_ >= 0);
   if (!ref_count_ && doomed_)
@@ -46,28 +60,52 @@ void MemEntryImpl::Close() {
 }
 
 void MemEntryImpl::Open() {
+  // Only a parent entry can be opened.
+  DCHECK(type_ == kParentEntry);
   ref_count_++;
   DCHECK(ref_count_ >= 0);
   DCHECK(!doomed_);
 }
 
 bool MemEntryImpl::InUse() {
-  return ref_count_ > 0;
+  if (type_ == kParentEntry) {
+    return ref_count_ > 0;
+  } else {
+    // A child entry is always not in use. The consequence is that a child entry
+    // can always be evicted while the associated parent entry is currently in
+    // used (i.e. opened).
+    return false;
+  }
 }
 
 void MemEntryImpl::Doom() {
   if (doomed_)
     return;
-  backend_->InternalDoomEntry(this);
+  if (type_ == kParentEntry) {
+    // Perform internal doom from the backend if this is a parent entry.
+    backend_->InternalDoomEntry(this);
+  } else {
+    // Manually detach from the parent entry and perform internal doom.
+    backend_->RemoveFromRankingList(this);
+    InternalDoom();
+  }
 }
 
 void MemEntryImpl::InternalDoom() {
   doomed_ = true;
-  if (!ref_count_)
+  if (!ref_count_) {
+    if (type_ == kParentEntry) {
+      // TODO(hclam): doom all child entries associated with this entry.
+    } else {
+      // TODO(hclam): detach this child entry from the parent entry.
+    }
     delete this;
+  }
 }
 
 std::string MemEntryImpl::GetKey() const {
+  // A child entry doesn't have key so this method should not be called.
+  DCHECK(type_ == kParentEntry);
   return key_;
 }
 
@@ -83,11 +121,16 @@ int32 MemEntryImpl::GetDataSize(int index) const {
   if (index < 0 || index >= NUM_STREAMS)
     return 0;
 
+  // TODO(hclam): handle the case when this is a parent entry and has associated
+  // child entries.
   return data_size_[index];
 }
 
 int MemEntryImpl::ReadData(int index, int offset, net::IOBuffer* buf,
     int buf_len, net::CompletionCallback* completion_callback) {
+  // This method can only be called with a parent entry.
+  DCHECK(type_ == kParentEntry);
+
   if (index < 0 || index >= NUM_STREAMS)
     return net::ERR_INVALID_ARGUMENT;
 
@@ -109,6 +152,9 @@ int MemEntryImpl::ReadData(int index, int offset, net::IOBuffer* buf,
 
 int MemEntryImpl::WriteData(int index, int offset, net::IOBuffer* buf,
     int buf_len, net::CompletionCallback* completion_callback, bool truncate) {
+  // This method can only be called with a parent entry.
+  DCHECK(type_ == kParentEntry);
+
   if (index < 0 || index >= NUM_STREAMS)
     return net::ERR_INVALID_ARGUMENT;
 
diff --git a/net/disk_cache/mem_entry_impl.h b/net/disk_cache/mem_entry_impl.h
index 65eb450..c63f928 100644
--- a/net/disk_cache/mem_entry_impl.h
+++ b/net/disk_cache/mem_entry_impl.h
@@ -1,20 +1,38 @@
-// 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.
 
-#ifndef NET_DISK_CACHE_MEM_ENTRY_IMPL_H__
-#define NET_DISK_CACHE_MEM_ENTRY_IMPL_H__
+#ifndef NET_DISK_CACHE_MEM_ENTRY_IMPL_H_
+#define NET_DISK_CACHE_MEM_ENTRY_IMPL_H_
 
 #include "net/disk_cache/disk_cache.h"
+#include "testing/gtest/include/gtest/gtest_prod.h"
 
 namespace disk_cache {
 
 class MemBackendImpl;
 
 // This class implements the Entry interface for the memory-only cache. An
-// object of this class represents a single entry on the cache.
+// object of this class represents a single entry on the cache. We use two
+// types of entries, parent and child to support sparse caching.
+// A parent entry is non-sparse until a sparse method is invoked (i.e.
+// ReadSparseData, WriteSparseData, GetAvailableRange) when sparse information
+// is initialized. It then manages a list of child entries and delegates the
+// sparse API calls to the child entries. It creates and deletes child entries
+// and updates the list when needed.
+// A child entry is used to carry partial cache content, non-sparse methods like
+// ReadData and WriteData cannot be applied to them. The lifetime of a child
+// entry is managed by the parent entry that created it except that the entry
+// can be evicted independently. A child entry does not have a key and it is not
+// registered in the backend's entry map. It is registered in the backend's
+// ranking list to enable eviction of a partial content.
 class MemEntryImpl : public Entry {
  public:
+  enum EntryType {
+    kParentEntry,
+    kChildEntry,
+  };
+
   explicit MemEntryImpl(MemBackendImpl* backend);
 
   // Entry interface.
@@ -39,9 +57,18 @@ class MemEntryImpl : public Entry {
   // cache.
   bool CreateEntry(const std::string& key);
 
-  // Permamently destroys this entry
+  // Performs the initialization of a MemEntryImpl as a child entry.
+  // TODO(hclam): this method should be private. Leave this as public because
+  // this is the only way to create a child entry. Move this method to private
+  // once child entries are created by parent entry.
+  bool CreateChildEntry(MemEntryImpl* parent);
+
+  // Permanently destroys this entry.
   void InternalDoom();
 
+  void Open();
+  bool InUse();
+
   MemEntryImpl* next() const {
     return next_;
   }
@@ -58,8 +85,9 @@ class MemEntryImpl : public Entry {
     prev_ = prev;
   }
 
-  void Open();
-  bool InUse();
+  EntryType type() const {
+    return type_;
+  }
 
  private:
    enum {
@@ -81,14 +109,16 @@ class MemEntryImpl : public Entry {
 
   MemEntryImpl* next_;         // Pointers for the LRU list.
   MemEntryImpl* prev_;
-  base::Time last_modified_;         // LRU information.
+  MemEntryImpl* parent_;       // Pointer to the parent entry.
+  base::Time last_modified_;   // LRU information.
   base::Time last_used_;
   MemBackendImpl* backend_;    // Back pointer to the cache.
   bool doomed_;                // True if this entry was removed from the cache.
+  EntryType type_;             // The type of this entry.
 
   DISALLOW_EVIL_CONSTRUCTORS(MemEntryImpl);
 };
 
 }  // namespace disk_cache
 
-#endif  // NET_DISK_CACHE_MEM_ENTRY_IMPL_H__
+#endif  // NET_DISK_CACHE_MEM_ENTRY_IMPL_H_