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 e7fad5b9ffe8def36969239edca1ebe9a49d5541..42b05e6f7a54d6c8f99e6c6e8a57e9a388684b6f 100644
--- a/net/disk_cache/backend_impl.cc
+++ b/net/disk_cache/backend_impl.cc
@@ -249,6 +249,30 @@ 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
 
 // ------------------------------------------------------------------------
@@ -321,6 +345,7 @@ BackendImpl::BackendImpl(const FilePath& path,
       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)) {
@@ -347,6 +372,7 @@ BackendImpl::BackendImpl(const FilePath& path,
       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)) {
@@ -403,7 +429,7 @@ int BackendImpl::Init(const CompletionCallback& 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;
@@ -450,6 +476,18 @@ int BackendImpl::SyncInit() {
     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);
 
@@ -1278,6 +1316,10 @@ void BackendImpl::SetFlags(uint32 flags) {
   user_flags_ |= flags;
 }
 
+void BackendImpl::ClearIndexBitmapForTest() {
+  index_bitmap_.clear();
+}
+
 void BackendImpl::ClearRefCountForTest() {
   num_refs_ = 0;
 }
@@ -1356,6 +1398,10 @@ int32 BackendImpl::GetEntryCount() const {
 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;
 }
@@ -1363,6 +1409,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;
 }
@@ -1370,6 +1418,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;
 }
@@ -1438,6 +1487,20 @@ void BackendImpl::OnExternalCacheHit(const std::string& 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) {
@@ -1554,7 +1617,7 @@ void BackendImpl::RestartCache(bool 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);