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 231 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 std::vector<bool>& bitmap,
+                       const std::string& key) {
+  DCHECK(!bitmap.empty()) << "Call site should provide default behaviour";
+  DCHECK(IsPowerOfTwo(bitmap.size()));
+  const uint32 mask = bitmap.size() - 1;
+  const uint32 hash = base::Hash(key);
+  return bitmap[hash & mask];
+}
+
+void IndexBitmapSetValue(std::vector<bool>* bitmap,
+                         const std::string& key,
+                         bool value) {
+  if (bitmap->empty())
+    return;
+  DCHECK(IsPowerOfTwo(bitmap->size()));
+  const uint32 mask = bitmap->size() - 1;
+  const uint32 hash = base::Hash(key);
+  (*bitmap)[hash & mask] = value;
+}
+
 }  // namespace
 
 // ------------------------------------------------------------------------
 
 namespace disk_cache {
 
 int CreateCacheBackend(net::CacheType type, const FilePath& path, int max_bytes,
                        bool force, base::MessageLoopProxy* thread,
                        net::NetLog* net_log, Backend** backend,
                        const net::CompletionCallback& callback) {
@@ skipping 52 matching lines @@
       uma_report_(0),
       user_flags_(0),
       init_(false),
       restarted_(false),
       unit_test_(false),
       read_only_(false),
       disabled_(false),
       new_eviction_(false),
       first_timer_(true),
       user_load_(false),
+      index_bitmap_has_been_set_(false, false),
       net_log_(net_log),
       done_(true, false),
       ALLOW_THIS_IN_INITIALIZER_LIST(ptr_factory_(this)) {
 }
 
 BackendImpl::BackendImpl(const FilePath& path,
                          uint32 mask,
                          base::MessageLoopProxy* cache_thread,
                          net::NetLog* net_log)
     : ALLOW_THIS_IN_INITIALIZER_LIST(background_queue_(this, cache_thread)),
       path_(path),
       block_files_(path),
       mask_(mask),
       max_size_(0),
       up_ticks_(0),
       cache_type_(net::DISK_CACHE),
       uma_report_(0),
       user_flags_(kMask),
       init_(false),
       restarted_(false),
       unit_test_(false),
       read_only_(false),
       disabled_(false),
       new_eviction_(false),
       first_timer_(true),
       user_load_(false),
+      index_bitmap_has_been_set_(false, false),
       net_log_(net_log),
       done_(true, false),
       ALLOW_THIS_IN_INITIALIZER_LIST(ptr_factory_(this)) {
 }
 
 BackendImpl::~BackendImpl() {
   if (user_flags_ & kNoRandom) {
     // This is a unit test, so we want to be strict about not leaking entries
     // and completing all the work.
     background_queue_.WaitForPendingIO();
@@ skipping 36 matching lines @@
                        net_log, backend, callback);
   // This object will self-destroy when finished.
   return creator->Run();
 }
 
 int BackendImpl::Init(const CompletionCallback& callback) {
   background_queue_.Init(callback);
   return net::ERR_IO_PENDING;
 }
 
-int BackendImpl::SyncInit() {
+int BackendImpl::SyncInit(scoped_refptr<base::MessageLoopProxy> async_thread) {

[rvargas (doing something else), 2013/01/22 22:31:51]

We should be able to do this without sending the message loop around.

[gavinp, 2013/01/22 23:15:47]

Can you tell me more?

[rvargas (doing something else), 2013/01/22 23:46:14]

It seems like this is used for controlling when to init the bitmap (and
restarted_ will do that), and running stuff on the main thread (like disabling
the bitmap when the cache is actually restarted, todo).

I was overlooking the second case (I was thinking it was just a matter of
routing the call through InFlightBackendIO but that sounds like abusing the
system, even though it knows exactly what to call at any point)

Anyhow, if we need to keep another message loop as part of the backend just to
post tasks the other way around fine... we can just grab it at Init()

[gavinp, 2013/02/09 16:46:51]

Now removed, since we just initialize the bitmap in our first call to SyncInit.

 #if defined(NET_BUILD_STRESS_CACHE)
   // Start evictions right away.
   up_ticks_ = kTrimDelay * 2;
 #endif
   DCHECK(!init_);
   if (init_)
     return net::ERR_FAILED;
 
   bool create_files = false;
   if (!InitBackingStore(&create_files)) {
@@ skipping 26 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;
   }
 
+  if (async_thread) {

[rvargas (doing something else), 2013/01/22 22:31:51]

restarted_ can be used to avoid doing something more than once.

[gavinp, 2013/02/09 16:46:51]

Done.

+    std::vector<bool> bitmap;
+    CalculateIndexBitmap(&bitmap);
+    if (async_thread->BelongsToCurrentThread()) {
+      SetIndexBitmap(bitmap);
+    } else {
+      async_thread->PostTask(FROM_HERE, base::Bind(&BackendImpl::SetIndexBitmap,
+                                                   base::Unretained(this),
+                                                   bitmap));
+      index_bitmap_has_been_set_.Wait();

[rvargas (doing something else), 2013/01/22 22:31:51]

A lock doesn't sound so good.

Initialization is protected by the contract :). The caller is not allowed to
issue any command before Init() returns. (aka the completion callback for
creation).

As such, we know that while SyncInit is running (at least when not being
restarted), there won't be any access to members from the IO thread, so this
code can init the bitmap directly.

As for the threading model of the backend, it is pretty simple: everything is
only accessible from the cache thread (after init) with two exceptions:

1. The background queue (for obvious reasons)
2. Shutdown (where we do that dance to make sure that we finish everything, wait
until done etc).

(there may be a race-y access here and there, but confined to low value/uncommon
things (like getting stats)).

Other than that, we actually work when we have only one thread, so there is some
code to detect that scenario (some unit tests) and catch mistakes.

In other words, the bitmap would be a member to be used exclusively from the IO
thread (the first "general purpose" member at that)

[gavinp, 2013/01/22 23:15:47]

Yes, I did see that the cache is not used during Init, and so I thought this was
a very safe way to initialize it without risk of deadlock; the more conservative
PostTaskAndReply felt like overkill.

I thought the WaitLock was guaranteeing that both threads would see the same
view of the same object, and avoiding data races. What do you think of that
reasoning?

[rvargas (doing something else), 2013/01/22 23:46:14]

That is correct, assuming that the second thread can move freely to use the data
regardless of the first thread. In this case, you want to make sure the bitmap
is only accessed (init) from the IO thread, but we know that it won't be used
until we return. Data consistency is taken care by PostTask (when we invoke the
callback).

[gavinp, 2013/02/09 16:46:51]

Done.

+    }
+  }
   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_.empty() && !IndexBitmapLookup(index_bitmap_, key)) {
+    VLOG(4) << "BackendImpl::OpenEntry missed on bitmap";
+    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 48 matching lines @@
 
   stats_.GetItems(stats);
 }
 
 void BackendImpl::OnExternalCacheHit(const std::string& key) {
   background_queue_.OnExternalCacheHit(key);
 }
 
 // ------------------------------------------------------------------------
 
+void BackendImpl::CalculateIndexBitmap(std::vector<bool>* bitmap) const {
+  DCHECK(bitmap);
+  const int32 table_size = mask_ + 1;
+  DCHECK(IsPowerOfTwo(table_size));
+  bitmap->reserve(table_size);
+  for (int i = 0; i < table_size; ++i)
+    bitmap->push_back(data_->table[i] != 0);
+}
+
+void BackendImpl::SetIndexBitmap(const std::vector<bool>& index_bitmap) {
+  index_bitmap_ = index_bitmap;
+  index_bitmap_has_been_set_.Signal();
+}
+
 // We just created a new file so we're going to write the header and set the
 // file length to include the hash table (zero filled).
 bool BackendImpl::CreateBackingStore(disk_cache::File* file) {
   AdjustMaxCacheSize(0);
 
   IndexHeader header;
   header.table_len = DesiredIndexTableLen(max_size_);
 
   // We need file version 2.1 for the new eviction algorithm.
   if (new_eviction_)
@@ skipping 96 matching lines @@
     DCHECK(!open_entries_.size());
     DelayedCacheCleanup(path_);
   } else {
     DeleteCache(path_, false);
   }
 
   // Don't call Init() if directed by the unit test: we are simulating a failure
   // trying to re-enable the cache.
   if (unit_test_)
     init_ = true;  // Let the destructor do proper cleanup.
-  else if (SyncInit() == net::OK) {
+  else if (SyncInit(NULL) == net::OK) {
     stats_.SetCounter(Stats::FATAL_ERROR, errors);
     stats_.SetCounter(Stats::DOOM_CACHE, full_dooms);
     stats_.SetCounter(Stats::DOOM_RECENT, partial_dooms);
     stats_.SetCounter(Stats::GAJS_EVICTED, ga_evictions);
     stats_.SetCounter(Stats::LAST_REPORT, last_report);
   }
 }
 
 void BackendImpl::PrepareForRestart() {
   // Reset the mask_ if it was not given by the user.
@@ skipping 668 matching lines @@
     if (total_memory > kMaxBuffersSize || total_memory <= 0)
       total_memory = kMaxBuffersSize;
 
     done = true;
   }
 
   return static_cast<int>(total_memory);
 }
 
 }  // namespace disk_cache