Add an IO thread index bitmap to disk cache.

net/disk_cache/backend_impl.h

 // 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.
 
 // See net/disk_cache/disk_cache.h for the public interface of the cache.
 
 #ifndef NET_DISK_CACHE_BACKEND_IMPL_H_
 #define NET_DISK_CACHE_BACKEND_IMPL_H_
 
 #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"
 #include "net/disk_cache/eviction.h"
 #include "net/disk_cache/in_flight_backend_io.h"
 #include "net/disk_cache/rankings.h"
 #include "net/disk_cache/stats.h"
 #include "net/disk_cache/stress_support.h"
 #include "net/disk_cache/trace.h"
 
@@ skipping 31 matching lines @@
   // CreateCacheBackend().
   static int CreateBackend(const FilePath& full_path, bool force,
                            int max_bytes, net::CacheType type,
                            uint32 flags, base::MessageLoopProxy* thread,
                            net::NetLog* net_log, Backend** backend,
                            const CompletionCallback& callback);
 
   // 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.
   int OpenPrevEntry(void** iter, Entry** prev_entry,
                     const CompletionCallback& callback);
 
   // Synchronous implementation of the asynchronous interface.
   int SyncOpenEntry(const std::string& key, Entry** entry);
   int SyncCreateEntry(const std::string& key, Entry** entry);
   int SyncDoomEntry(const std::string& key);
@@ skipping 151 matching lines @@
 
   // Sets internal parameters to enable upgrade mode (for internal tools).
   void SetUpgradeMode();
 
   // Sets the eviction algorithm to version 2.
   void SetNewEviction();
 
   // 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();
 
   // Sends a dummy operation through the operation queue, for unit tests.
   int FlushQueueForTest(const CompletionCallback& callback);
 
   // Runs the provided task on the cache thread. The task will be automatically
   // deleted after it runs.
   int RunTaskForTest(const base::Closure& task,
                      const CompletionCallback& callback);
@@ skipping 30 matching lines @@
                                const CompletionCallback& callback) OVERRIDE;
   virtual int OpenNextEntry(void** iter, Entry** next_entry,
                             const CompletionCallback& callback) OVERRIDE;
   virtual void EndEnumeration(void** iter) OVERRIDE;
   virtual void GetStats(StatsItems* stats) OVERRIDE;
   virtual void OnExternalCacheHit(const std::string& key) OVERRIDE;
 
  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);
   void AdjustMaxCacheSize(int table_len);
 
   // Deletes the cache and starts again.
   void RestartCache(bool failure);
   void PrepareForRestart();
 
   // Creates a new entry object. Returns zero on success, or a disk_cache error
@@ skipping 81 matching lines @@
   uint32 user_flags_;  // Flags set by the user.
   bool init_;  // controls the initialization of the system.
   bool restarted_;
   bool unit_test_;
   bool read_only_;  // Prevents updates of the rankings data (used by tools).
   bool disabled_;
   bool new_eviction_;  // What eviction algorithm should be used.
   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.
   scoped_ptr<base::RepeatingTimer<BackendImpl> > timer_;  // Usage timer.
   base::WaitableEvent done_;  // Signals the end of background work.
   scoped_refptr<TraceObject> trace_object_;  // Initializes internal tracing.
   base::WeakPtrFactory<BackendImpl> ptr_factory_;
 
   DISALLOW_COPY_AND_ASSIGN(BackendImpl);
 };
 
 // Returns the preferred max cache size given the available disk space.
 NET_EXPORT_PRIVATE int PreferedCacheSize(int64 available);
 
 }  // namespace disk_cache
 
 #endif  // NET_DISK_CACHE_BACKEND_IMPL_H_