simple_index.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311
  1. // Copyright (c) 2013 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef NET_DISK_CACHE_SIMPLE_SIMPLE_INDEX_H_
  5. #define NET_DISK_CACHE_SIMPLE_SIMPLE_INDEX_H_
  6. #include <stdint.h>
  7. #include <list>
  8. #include <memory>
  9. #include <unordered_map>
  10. #include <unordered_set>
  11. #include <vector>
  12. #include "base/callback.h"
  13. #include "base/gtest_prod_util.h"
  14. #include "base/memory/raw_ptr.h"
  15. #include "base/memory/ref_counted.h"
  16. #include "base/memory/weak_ptr.h"
  17. #include "base/numerics/safe_conversions.h"
  18. #include "base/sequence_checker.h"
  19. #include "base/task/sequenced_task_runner.h"
  20. #include "base/time/time.h"
  21. #include "base/timer/timer.h"
  22. #include "build/build_config.h"
  23. #include "net/base/cache_type.h"
  24. #include "net/base/completion_once_callback.h"
  25. #include "net/base/net_errors.h"
  26. #include "net/base/net_export.h"
  27. #if BUILDFLAG(IS_ANDROID)
  28. #include "base/android/application_status_listener.h"
  29. #endif
  30. namespace base {
  31. class Pickle;
  32. class PickleIterator;
  33. }
  34. namespace disk_cache {
  35. class BackendCleanupTracker;
  36. class SimpleIndexDelegate;
  37. class SimpleIndexFile;
  38. struct SimpleIndexLoadResult;
  39. class NET_EXPORT_PRIVATE EntryMetadata {
  40. public:
  41. EntryMetadata();
  42. EntryMetadata(base::Time last_used_time,
  43. base::StrictNumeric<uint32_t> entry_size);
  44. EntryMetadata(int32_t trailer_prefetch_size,
  45. base::StrictNumeric<uint32_t> entry_size);
  46. base::Time GetLastUsedTime() const;
  47. void SetLastUsedTime(const base::Time& last_used_time);
  48. int32_t GetTrailerPrefetchSize() const;
  49. void SetTrailerPrefetchSize(int32_t size);
  50. uint32_t RawTimeForSorting() const {
  51. return last_used_time_seconds_since_epoch_;
  52. }
  53. uint32_t GetEntrySize() const;
  54. void SetEntrySize(base::StrictNumeric<uint32_t> entry_size);
  55. uint8_t GetInMemoryData() const { return in_memory_data_; }
  56. void SetInMemoryData(uint8_t val) { in_memory_data_ = val; }
  57. // Serialize the data into the provided pickle.
  58. void Serialize(net::CacheType cache_type, base::Pickle* pickle) const;
  59. bool Deserialize(net::CacheType cache_type,
  60. base::PickleIterator* it,
  61. bool has_entry_in_memory_data,
  62. bool app_cache_has_trailer_prefetch_size);
  63. static base::TimeDelta GetLowerEpsilonForTimeComparisons() {
  64. return base::Seconds(1);
  65. }
  66. static base::TimeDelta GetUpperEpsilonForTimeComparisons() {
  67. return base::TimeDelta();
  68. }
  69. static const int kOnDiskSizeBytes = 16;
  70. private:
  71. friend class SimpleIndexFileTest;
  72. FRIEND_TEST_ALL_PREFIXES(SimpleIndexFileTest, ReadV8Format);
  73. FRIEND_TEST_ALL_PREFIXES(SimpleIndexFileTest, ReadV8FormatAppCache);
  74. // There are tens of thousands of instances of EntryMetadata in memory, so the
  75. // size of each entry matters. Even when the values used to set these members
  76. // are originally calculated as >32-bit types, the actual necessary size for
  77. // each shouldn't exceed 32 bits, so we use 32-bit types here.
  78. // In most modes we track the last access time in order to support automatic
  79. // eviction. In APP_CACHE mode, however, eviction is disabled. Instead of
  80. // storing the access time in APP_CACHE mode we instead store a hint about
  81. // how much entry file trailer should be prefetched when its opened.
  82. union {
  83. uint32_t last_used_time_seconds_since_epoch_;
  84. int32_t trailer_prefetch_size_; // in bytes
  85. };
  86. uint32_t entry_size_256b_chunks_ : 24; // in 256-byte blocks, rounded up.
  87. uint32_t in_memory_data_ : 8;
  88. };
  89. static_assert(sizeof(EntryMetadata) == 8, "incorrect metadata size");
  90. // This class is not Thread-safe.
  91. class NET_EXPORT_PRIVATE SimpleIndex
  92. : public base::SupportsWeakPtr<SimpleIndex> {
  93. public:
  94. // Used in histograms. Please only add entries at the end.
  95. enum IndexInitMethod {
  96. INITIALIZE_METHOD_RECOVERED = 0,
  97. INITIALIZE_METHOD_LOADED = 1,
  98. INITIALIZE_METHOD_NEWCACHE = 2,
  99. INITIALIZE_METHOD_MAX = 3,
  100. };
  101. // Used in histograms. Please only add entries at the end.
  102. enum IndexWriteToDiskReason {
  103. INDEX_WRITE_REASON_SHUTDOWN = 0,
  104. INDEX_WRITE_REASON_STARTUP_MERGE = 1,
  105. INDEX_WRITE_REASON_IDLE = 2,
  106. INDEX_WRITE_REASON_ANDROID_STOPPED = 3,
  107. INDEX_WRITE_REASON_MAX = 4,
  108. };
  109. typedef std::vector<uint64_t> HashList;
  110. SimpleIndex(const scoped_refptr<base::SequencedTaskRunner>& task_runner,
  111. scoped_refptr<BackendCleanupTracker> cleanup_tracker,
  112. SimpleIndexDelegate* delegate,
  113. net::CacheType cache_type,
  114. std::unique_ptr<SimpleIndexFile> simple_index_file);
  115. virtual ~SimpleIndex();
  116. void Initialize(base::Time cache_mtime);
  117. void SetMaxSize(uint64_t max_bytes);
  118. uint64_t max_size() const { return max_size_; }
  119. void Insert(uint64_t entry_hash);
  120. void Remove(uint64_t entry_hash);
  121. // Check whether the index has the entry given the hash of its key.
  122. bool Has(uint64_t entry_hash) const;
  123. // Update the last used time of the entry with the given key and return true
  124. // iff the entry exist in the index.
  125. bool UseIfExists(uint64_t entry_hash);
  126. uint8_t GetEntryInMemoryData(uint64_t entry_hash) const;
  127. void SetEntryInMemoryData(uint64_t entry_hash, uint8_t value);
  128. void WriteToDisk(IndexWriteToDiskReason reason);
  129. int32_t GetTrailerPrefetchSize(uint64_t entry_hash) const;
  130. void SetTrailerPrefetchSize(uint64_t entry_hash, int32_t size);
  131. // Update the size (in bytes) of an entry, in the metadata stored in the
  132. // index. This should be the total disk-file size including all streams of the
  133. // entry.
  134. bool UpdateEntrySize(uint64_t entry_hash,
  135. base::StrictNumeric<uint32_t> entry_size);
  136. using EntrySet = std::unordered_map<uint64_t, EntryMetadata>;
  137. // Insert an entry in the given set if there is not already entry present.
  138. // Returns true if the set was modified.
  139. static bool InsertInEntrySet(uint64_t entry_hash,
  140. const EntryMetadata& entry_metadata,
  141. EntrySet* entry_set);
  142. // For use in tests only. Updates cache_size_, but will not start evictions
  143. // or adjust index writing time. Requires entry to not already be in the set.
  144. void InsertEntryForTesting(uint64_t entry_hash,
  145. const EntryMetadata& entry_metadata);
  146. // Executes the |callback| when the index is ready. Allows multiple callbacks.
  147. // Never synchronous.
  148. void ExecuteWhenReady(net::CompletionOnceCallback callback);
  149. // Returns entries from the index that have last accessed time matching the
  150. // range between |initial_time| and |end_time| where open intervals are
  151. // possible according to the definition given in |DoomEntriesBetween()| in the
  152. // disk cache backend interface.
  153. //
  154. // Access times are not updated in net::APP_CACHE mode. GetEntriesBetween()
  155. // should only be called with null times indicating the full range when in
  156. // this mode.
  157. std::unique_ptr<HashList> GetEntriesBetween(const base::Time initial_time,
  158. const base::Time end_time);
  159. // Returns the list of all entries key hash.
  160. std::unique_ptr<HashList> GetAllHashes();
  161. // Returns number of indexed entries.
  162. int32_t GetEntryCount() const;
  163. // Returns the size of the entire cache in bytes. Can only be called after the
  164. // index has been initialized.
  165. uint64_t GetCacheSize() const;
  166. // Returns the size of the cache entries accessed between |initial_time| and
  167. // |end_time| in bytes. Can only be called after the index has been
  168. // initialized.
  169. uint64_t GetCacheSizeBetween(const base::Time initial_time,
  170. const base::Time end_time) const;
  171. // Returns whether the index has been initialized yet.
  172. bool initialized() const { return initialized_; }
  173. IndexInitMethod init_method() const { return init_method_; }
  174. // Returns base::Time() if hash not known.
  175. base::Time GetLastUsedTime(uint64_t entry_hash);
  176. void SetLastUsedTimeForTest(uint64_t entry_hash, const base::Time last_used);
  177. #if BUILDFLAG(IS_ANDROID)
  178. void set_app_status_listener(
  179. base::android::ApplicationStatusListener* app_status_listener) {
  180. app_status_listener_ = app_status_listener;
  181. }
  182. #endif
  183. // Return true if a pending disk write has been scheduled from
  184. // PostponeWritingToDisk().
  185. bool HasPendingWrite() const;
  186. private:
  187. friend class SimpleIndexTest;
  188. FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, IndexSizeCorrectOnMerge);
  189. FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, DiskWriteQueued);
  190. FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, DiskWriteExecuted);
  191. FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, DiskWritePostponed);
  192. FRIEND_TEST_ALL_PREFIXES(SimpleIndexAppCacheTest, DiskWriteQueued);
  193. FRIEND_TEST_ALL_PREFIXES(SimpleIndexCodeCacheTest, DisableEvictBySize);
  194. FRIEND_TEST_ALL_PREFIXES(SimpleIndexCodeCacheTest, EnableEvictBySize);
  195. void StartEvictionIfNeeded();
  196. void EvictionDone(int result);
  197. void PostponeWritingToDisk();
  198. // Update the size of the entry pointed to by the given iterator. Return
  199. // true if the new size actually results in a change.
  200. bool UpdateEntryIteratorSize(EntrySet::iterator* it,
  201. base::StrictNumeric<uint32_t> entry_size);
  202. // Must run on IO Thread.
  203. void MergeInitializingSet(std::unique_ptr<SimpleIndexLoadResult> load_result);
  204. #if BUILDFLAG(IS_ANDROID)
  205. void OnApplicationStateChange(base::android::ApplicationState state);
  206. std::unique_ptr<base::android::ApplicationStatusListener>
  207. owned_app_status_listener_;
  208. raw_ptr<base::android::ApplicationStatusListener> app_status_listener_ =
  209. nullptr;
  210. #endif
  211. scoped_refptr<BackendCleanupTracker> cleanup_tracker_;
  212. // The owner of |this| must ensure the |delegate_| outlives |this|.
  213. raw_ptr<SimpleIndexDelegate> delegate_;
  214. EntrySet entries_set_;
  215. const net::CacheType cache_type_;
  216. uint64_t cache_size_ = 0; // Total cache storage size in bytes.
  217. uint64_t max_size_ = 0;
  218. uint64_t high_watermark_ = 0;
  219. uint64_t low_watermark_ = 0;
  220. bool eviction_in_progress_ = false;
  221. base::TimeTicks eviction_start_time_;
  222. // This stores all the entry_hash of entries that are removed during
  223. // initialization.
  224. std::unordered_set<uint64_t> removed_entries_;
  225. bool initialized_ = false;
  226. IndexInitMethod init_method_ = INITIALIZE_METHOD_MAX;
  227. std::unique_ptr<SimpleIndexFile> index_file_;
  228. scoped_refptr<base::SequencedTaskRunner> task_runner_;
  229. // All nonstatic SimpleEntryImpl methods should always be called on its
  230. // creation sequance, in all cases. |sequence_checker_| documents and
  231. // enforces this.
  232. SEQUENCE_CHECKER(sequence_checker_);
  233. base::OneShotTimer write_to_disk_timer_;
  234. base::RepeatingClosure write_to_disk_cb_;
  235. typedef std::list<net::CompletionOnceCallback> CallbackList;
  236. CallbackList to_run_when_initialized_;
  237. // Set to true when the app is on the background. When the app is in the
  238. // background we can write the index much more frequently, to insure fresh
  239. // index on next startup.
  240. bool app_on_background_ = false;
  241. };
  242. } // namespace disk_cache
  243. #endif // NET_DISK_CACHE_SIMPLE_SIMPLE_INDEX_H_