Add an IO thread index bitmap to disk cache.

net/disk_cache/backend_impl.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/backend_impl.h"
 
 #include "base/bind.h"
 #include "base/bind_helpers.h"
 #include "base/file_path.h"
 #include "base/file_util.h"
@@ skipping 21 matching lines @@
 // This has to be defined before including histogram_macros.h from this file.
 #define NET_DISK_CACHE_BACKEND_IMPL_CC_
 #include "net/disk_cache/histogram_macros.h"
 
 using base::Time;
 using base::TimeDelta;
 using base::TimeTicks;
 
 namespace {
 
+using disk_cache::Bitmap;
+
 const char* kIndexName = "index";
 const int kMaxOldFolders = 100;
 
 // Seems like ~240 MB correspond to less than 50k entries for 99% of the people.
 // Note that the actual target is to keep the index table load factor under 55%
 // for most users.
 const int k64kEntriesStore = 240 * 1000 * 1000;
 const int kBaseTableLen = 64 * 1024;
 const int kDefaultCacheSize = 80 * 1024 * 1024;
 
@@ skipping 192 matching lines @@
   // is not there anymore... let's create a new set of files.
   int rv = Run();
   DCHECK_EQ(net::ERR_IO_PENDING, rv);
 }
 
 // A callback to perform final cleanup on the background thread.
 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
 
 // ------------------------------------------------------------------------
 
 namespace disk_cache {
 
 int CreateCacheBackend(net::CacheType type, const base::FilePath& path,
                        int max_bytes,
                        bool force, base::MessageLoopProxy* thread,
                        net::NetLog* net_log, Backend** backend,
@@ skipping 182 matching lines @@
   if (!(user_flags_ & kNoRandom)) {
     // The unit test controls directly what to test.
     new_eviction_ = (cache_type_ == net::DISK_CACHE);
   }
 
   if (!CheckIndex()) {
     ReportError(ERR_INIT_FAILED);
     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);
 
   if (!(user_flags_ & kNoRandom) &&
       cache_type_ == net::DISK_CACHE && !InitExperiment(&data_->header))
     return net::ERR_FAILED;
 
   // We don't care if the value overflows. The only thing we care about is that
   // the id cannot be zero, because that value is used as "not dirty".
   // Increasing the value once per second gives us many years before we start
@@ skipping 808 matching lines @@
 
 void BackendImpl::SetNewEviction() {
   user_flags_ |= kNewEviction;
   new_eviction_ = true;
 }
 
 void BackendImpl::SetFlags(uint32 flags) {
   user_flags_ |= flags;
 }
 
+void BackendImpl::ClearIndexBitmapForTest() {
+  index_bitmap_.Clear();
+}
+
 void BackendImpl::ClearRefCountForTest() {
   num_refs_ = 0;
 }
 
 int BackendImpl::FlushQueueForTest(const CompletionCallback& callback) {
   background_queue_.FlushQueue(callback);
   return net::ERR_IO_PENDING;
 }
 
 int BackendImpl::RunTaskForTest(const base::Closure& task,
@@ skipping 58 matching lines @@
     NOTREACHED();
     not_deleted = 0;
   }
 
   return not_deleted;
 }
 
 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;
 }
 
 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;
 }
 
 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;
 }
 
 int BackendImpl::DoomAllEntries(const CompletionCallback& callback) {
   DCHECK(!callback.is_null());
   background_queue_.DoomAllEntries(callback);
   return net::ERR_IO_PENDING;
 }
 
@@ skipping 853 matching lines @@
     if (total_memory > kMaxBuffersSize || total_memory <= 0)
       total_memory = kMaxBuffersSize;
 
     done = true;
   }
 
   return static_cast<int>(total_memory);
 }
 
 }  // namespace disk_cache