Add an IO thread index bitmap to disk cache.

net/disk_cache/backend_impl.h

Index: net/disk_cache/backend_impl.h
diff --git a/net/disk_cache/backend_impl.h b/net/disk_cache/backend_impl.h
index ad6f8ffe1e8e0be5784bc1889f1fea928d7e31bd..72242e1a3c1cc29bbf6352e10ffea9e53497b6a4 100644
--- a/net/disk_cache/backend_impl.h
+++ b/net/disk_cache/backend_impl.h
@@ -9,6 +9,8 @@
 
 #include "base/file_path.h"
 #include "base/hash_tables.h"
+#include "base/memory/ref_counted.h"
+#include "base/message_loop_proxy.h"
 #include "base/timer.h"
 #include "net/disk_cache/block_files.h"
 #include "net/disk_cache/disk_cache.h"
@@ -60,8 +62,10 @@ class NET_EXPORT_PRIVATE BackendImpl : public Backend {
   // Performs general initialization for this current instance of the cache.
   int Init(const CompletionCallback& callback);
 
-  // Performs the actual initialization and final cleanup on destruction.
-  int SyncInit();
+  // Performs the actual initialization and final cleanup on destruction. If
+  // |async_thread| is non null, then |bitmap_| may be initialized on that
+  // thread, otherwise |bitmap_| is left unchanged.
+  int SyncInit(scoped_refptr<base::MessageLoopProxy> async_thread);
   void CleanupCache();
 
   // Same behavior as OpenNextEntry but walks the list from back to front.
@@ -233,6 +237,9 @@ class NET_EXPORT_PRIVATE BackendImpl : public Backend {
   // Sets an explicit set of BackendFlags.
   void SetFlags(uint32 flags);
 
+  // Clears the index bitmap for tests.
+  void ClearIndexBitmapForTest();
+
   // Clears the counter of references to test handling of corruptions.
   void ClearRefCountForTest();
 
@@ -283,6 +290,14 @@ class NET_EXPORT_PRIVATE BackendImpl : public Backend {
  private:
   typedef base::hash_map<CacheAddr, EntryImpl*> EntriesMap;
 
+
+  // Called on the cache thread. Construct a vector<bool> of the index table.
+  void CalculateIndexBitmap(std::vector<bool>* index_bitmap) const;
+
+  // Called on the IO thread. Sets index_bitmap_ so that future OpenEntry
+  // operations can fast miss if there is no entry chain to traverse.
+  void SetIndexBitmap(const std::vector<bool>& index_bitmap);
+
   // Creates a new backing file for the cache index.
   bool CreateBackingStore(disk_cache::File* file);
   bool InitBackingStore(bool* file_created);
@@ -384,6 +399,9 @@ class NET_EXPORT_PRIVATE BackendImpl : public Backend {
   bool first_timer_;  // True if the timer has not been called.
   bool user_load_;  // True if we see a high load coming from the caller.
 
+  base::WaitableEvent index_bitmap_has_been_set_;
+  std::vector<bool> index_bitmap_;

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

use disk_cache::Bitmap instead.

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

Will do!

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

Can you please tell me more about why this is preferable to the C++ library?

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

In this particular instance there's probably not that much of a difference
(given that the use pattern is look up one bit, set one bit). But the full
Bitmap class is already linked for this module so it's better to reuse that code
rather than linking another implementation.

+
   net::NetLog* net_log_;
 
   Stats stats_;  // Usage statistics.