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