Add an IO thread index bitmap to disk cache.

net/disk_cache/backend_impl.cc

Index: net/disk_cache/backend_impl.cc
diff --git a/net/disk_cache/backend_impl.cc b/net/disk_cache/backend_impl.cc
index 232b3f8b295ee2ad0580b47deb9bbbcf9898bda5..8ce6095ecb001e9a074e384a9c2cbb24370067aa 100644
--- a/net/disk_cache/backend_impl.cc
+++ b/net/disk_cache/backend_impl.cc
@@ -39,6 +39,8 @@ using base::TimeTicks;
 
 namespace {
 
+using disk_cache::Bitmap;
+
 const char* kIndexName = "index";
 const int kMaxOldFolders = 100;
 
@@ -251,6 +253,30 @@ void FinalCleanupCallback(disk_cache::BackendImpl* backend) {
   backend->CleanupCache();
 }
 
+bool IsPowerOfTwo(size_t number) {
+  return !(number & (number - 1));
+}
+
+bool IndexBitmapLookup(const Bitmap& bitmap,
+                       const std::string& key) {
+  DCHECK_NE(0, bitmap.Size()) << "Call site should provide default behaviour";

[rvargas (doing something else), 2013/02/12 01:58:33]

nit: Can we just have the comment in the code (reduce executable size).

+  DCHECK(IsPowerOfTwo(bitmap.Size()));
+  const uint32 mask = bitmap.Size() - 1;
+  const uint32 hash = base::Hash(key);
+  return bitmap.Get(hash & mask);
+}
+
+void IndexBitmapSetValue(Bitmap* bitmap,
+                         const std::string& key,
+                         bool value) {
+  if (bitmap->Size() == 0)
+    return;
+  DCHECK(IsPowerOfTwo(bitmap->Size()));
+  const uint32 mask = bitmap->Size() - 1;
+  const uint32 hash = base::Hash(key);
+  bitmap->Set(hash & mask, value);
+}
+
 }  // namespace
 
 // ------------------------------------------------------------------------
@@ -453,6 +479,20 @@ int BackendImpl::SyncInit() {
     return net::ERR_FAILED;
   }
 
+  // TODO(gavinp): Consider clearing the |index_bitmap_| if the cache is being
+  // |restarted_|. It's not strictly required, because any bits set in
+  // |index_bitmap_| should not cause incorrect behaviour.
+  if (!restarted_) {

[rvargas (doing something else), 2013/02/12 01:58:33]

Maybe we should move this to InitBitmap()

+    // Although |index_bitmap_| is referenced on the IO thread, it is safe to
+    // initialize on the cache thread when !restarted_,  because the IO thread
+    // waits on Init() completion before using the cache and also because the
+    // callback PostTask includes a memory commit.
+    DCHECK(IsPowerOfTwo(mask_ + 1));
+    index_bitmap_.Resize(mask_ + 1, false);
+    for (size_t i = 0; i <= mask_; ++i)

[rvargas (doing something else), 2013/02/12 01:58:33]

nit: int

+      index_bitmap_.Set(i, data_->table[i] != 0);
+  }
+
   if (!restarted_ && (create_files || !data_->header.num_entries))
     ReportError(ERR_CACHE_CREATED);
 
@@ -1281,6 +1321,10 @@ void BackendImpl::SetFlags(uint32 flags) {
   user_flags_ |= flags;
 }
 
+void BackendImpl::ClearIndexBitmapForTest() {
+  index_bitmap_.Clear();
+}
+
 void BackendImpl::ClearRefCountForTest() {
   num_refs_ = 0;
 }
@@ -1359,6 +1403,10 @@ int32 BackendImpl::GetEntryCount() const {
 int BackendImpl::OpenEntry(const std::string& key, Entry** entry,
                            const CompletionCallback& callback) {
   DCHECK(!callback.is_null());
+  if (index_bitmap_.Size() != 0 && !IndexBitmapLookup(index_bitmap_, key)) {

[rvargas (doing something else), 2013/02/12 01:58:33]

when would Size be 0?

+    VLOG(4) << "BackendImpl::OpenEntry missed on bitmap";

[rvargas (doing something else), 2013/02/12 01:58:33]

remove tracing before checking in.

+    return net::ERR_FAILED;
+  }
   background_queue_.OpenEntry(key, entry, callback);
   return net::ERR_IO_PENDING;
 }
@@ -1366,6 +1414,8 @@ int BackendImpl::OpenEntry(const std::string& key, Entry** entry,
 int BackendImpl::CreateEntry(const std::string& key, Entry** entry,
                              const CompletionCallback& callback) {
   DCHECK(!callback.is_null());
+  // TODO(gavinp): Only set index_bitmap_ when CreateEntry succeeds.
+  IndexBitmapSetValue(&index_bitmap_, key, true);
   background_queue_.CreateEntry(key, entry, callback);
   return net::ERR_IO_PENDING;
 }
@@ -1373,6 +1423,7 @@ int BackendImpl::CreateEntry(const std::string& key, Entry** entry,
 int BackendImpl::DoomEntry(const std::string& key,
                            const CompletionCallback& callback) {
   DCHECK(!callback.is_null());
+  // TODO(gavinp): Clear the index_bitmap_ when appropriate after Doom.
   background_queue_.DoomEntry(key, callback);
   return net::ERR_IO_PENDING;
 }