blob: c3e3e028f344eb34f3f8380106df778c5621bfed [file] [log] [blame]
// Copyright (c) 2013 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.
#include <stdint.h>
#include <list>
#include <memory>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include "base/callback.h"
#include "base/feature_list.h"
#include "base/files/file_path.h"
#include "base/gtest_prod_util.h"
#include "base/memory/ref_counted.h"
#include "base/memory/weak_ptr.h"
#include "base/numerics/safe_conversions.h"
#include "base/single_thread_task_runner.h"
#include "base/threading/thread_checker.h"
#include "base/time/time.h"
#include "base/timer/timer.h"
#include "build/build_config.h"
#include "net/base/cache_type.h"
#include "net/base/completion_once_callback.h"
#include "net/base/net_errors.h"
#include "net/base/net_export.h"
#if defined(OS_ANDROID)
#include "base/android/application_status_listener.h"
namespace base {
class Pickle;
class PickleIterator;
namespace disk_cache {
class BackendCleanupTracker;
class SimpleIndexDelegate;
class SimpleIndexFile;
struct SimpleIndexLoadResult;
NET_EXPORT_PRIVATE extern const base::Feature kSimpleCacheEvictionWithSize;
class NET_EXPORT_PRIVATE EntryMetadata {
EntryMetadata(base::Time last_used_time,
base::StrictNumeric<uint32_t> entry_size);
EntryMetadata(int32_t trailer_prefetch_size,
base::StrictNumeric<uint32_t> entry_size);
base::Time GetLastUsedTime() const;
void SetLastUsedTime(const base::Time& last_used_time);
int32_t GetTrailerPrefetchSize() const;
void SetTrailerPrefetchSize(int32_t size);
uint32_t RawTimeForSorting() const {
return last_used_time_seconds_since_epoch_;
uint32_t GetEntrySize() const;
void SetEntrySize(base::StrictNumeric<uint32_t> entry_size);
uint8_t GetInMemoryData() const { return in_memory_data_; }
void SetInMemoryData(uint8_t val) { in_memory_data_ = val; }
// Serialize the data into the provided pickle.
void Serialize(net::CacheType cache_type, base::Pickle* pickle) const;
bool Deserialize(net::CacheType cache_type,
base::PickleIterator* it,
bool has_entry_in_memory_data,
bool app_cache_has_trailer_prefetch_size);
static base::TimeDelta GetLowerEpsilonForTimeComparisons() {
return base::TimeDelta::FromSeconds(1);
static base::TimeDelta GetUpperEpsilonForTimeComparisons() {
return base::TimeDelta();
static const int kOnDiskSizeBytes = 16;
friend class SimpleIndexFileTest;
FRIEND_TEST_ALL_PREFIXES(SimpleIndexFileTest, ReadV8Format);
FRIEND_TEST_ALL_PREFIXES(SimpleIndexFileTest, ReadV8FormatAppCache);
// There are tens of thousands of instances of EntryMetadata in memory, so the
// size of each entry matters. Even when the values used to set these members
// are originally calculated as >32-bit types, the actual necessary size for
// each shouldn't exceed 32 bits, so we use 32-bit types here.
// In most modes we track the last access time in order to support automatic
// eviction. In APP_CACHE mode, however, eviction is disabled. Instead of
// storing the access time in APP_CACHE mode we instead store a hint about
// how much entry file trailer should be prefetched when its opened.
union {
uint32_t last_used_time_seconds_since_epoch_;
int32_t trailer_prefetch_size_; // in bytes
uint32_t entry_size_256b_chunks_ : 24; // in 256-byte blocks, rounded up.
uint32_t in_memory_data_ : 8;
static_assert(sizeof(EntryMetadata) == 8, "incorrect metadata size");
// This class is not Thread-safe.
class NET_EXPORT_PRIVATE SimpleIndex
: public base::SupportsWeakPtr<SimpleIndex> {
// Used in histograms. Please only add entries at the end.
enum IndexInitMethod {
// Used in histograms. Please only add entries at the end.
enum IndexWriteToDiskReason {
typedef std::vector<uint64_t> HashList;
SimpleIndex(const scoped_refptr<base::SingleThreadTaskRunner>& io_thread,
scoped_refptr<BackendCleanupTracker> cleanup_tracker,
SimpleIndexDelegate* delegate,
net::CacheType cache_type,
std::unique_ptr<SimpleIndexFile> simple_index_file);
virtual ~SimpleIndex();
void Initialize(base::Time cache_mtime);
void SetMaxSize(uint64_t max_bytes);
uint64_t max_size() const { return max_size_; }
void Insert(uint64_t entry_hash);
void Remove(uint64_t entry_hash);
// Check whether the index has the entry given the hash of its key.
bool Has(uint64_t entry_hash) const;
// Update the last used time of the entry with the given key and return true
// iff the entry exist in the index.
bool UseIfExists(uint64_t entry_hash);
uint8_t GetEntryInMemoryData(uint64_t entry_hash) const;
void SetEntryInMemoryData(uint64_t entry_hash, uint8_t value);
void WriteToDisk(IndexWriteToDiskReason reason);
int32_t GetTrailerPrefetchSize(uint64_t entry_hash) const;
void SetTrailerPrefetchSize(uint64_t entry_hash, int32_t size);
// Update the size (in bytes) of an entry, in the metadata stored in the
// index. This should be the total disk-file size including all streams of the
// entry.
bool UpdateEntrySize(uint64_t entry_hash,
base::StrictNumeric<uint32_t> entry_size);
using EntrySet = std::unordered_map<uint64_t, EntryMetadata>;
// Insert an entry in the given set if there is not already entry present.
// Returns true if the set was modified.
static bool InsertInEntrySet(uint64_t entry_hash,
const EntryMetadata& entry_metadata,
EntrySet* entry_set);
// For use in tests only. Updates cache_size_, but will not start evictions
// or adjust index writing time. Requires entry to not already be in the set.
void InsertEntryForTesting(uint64_t entry_hash,
const EntryMetadata& entry_metadata);
// Executes the |callback| when the index is ready. Allows multiple callbacks.
net::Error ExecuteWhenReady(net::CompletionOnceCallback callback);
// Returns entries from the index that have last accessed time matching the
// range between |initial_time| and |end_time| where open intervals are
// possible according to the definition given in |DoomEntriesBetween()| in the
// disk cache backend interface.
// Access times are not updated in net::APP_CACHE mode. GetEntriesBetween()
// should only be called with null times indicating the full range when in
// this mode.
std::unique_ptr<HashList> GetEntriesBetween(const base::Time initial_time,
const base::Time end_time);
// Returns the list of all entries key hash.
std::unique_ptr<HashList> GetAllHashes();
// Returns number of indexed entries.
int32_t GetEntryCount() const;
// Returns the size of the entire cache in bytes. Can only be called after the
// index has been initialized.
uint64_t GetCacheSize() const;
// Returns the size of the cache entries accessed between |initial_time| and
// |end_time| in bytes. Can only be called after the index has been
// initialized.
uint64_t GetCacheSizeBetween(const base::Time initial_time,
const base::Time end_time) const;
// Returns whether the index has been initialized yet.
bool initialized() const { return initialized_; }
IndexInitMethod init_method() const { return init_method_; }
// Returns the estimate of dynamically allocated memory in bytes.
size_t EstimateMemoryUsage() const;
// Returns base::Time() if hash not known.
base::Time GetLastUsedTime(uint64_t entry_hash);
void SetLastUsedTimeForTest(uint64_t entry_hash, const base::Time last_used);
#if defined(OS_ANDROID)
void set_app_status_listener(
base::android::ApplicationStatusListener* app_status_listener) {
app_status_listener_ = app_status_listener;
// Return true if a pending disk write has been scheduled from
// PostponeWritingToDisk().
bool HasPendingWrite() const;
friend class SimpleIndexTest;
FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, IndexSizeCorrectOnMerge);
FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, DiskWriteQueued);
FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, DiskWriteExecuted);
FRIEND_TEST_ALL_PREFIXES(SimpleIndexTest, DiskWritePostponed);
FRIEND_TEST_ALL_PREFIXES(SimpleIndexAppCacheTest, DiskWriteQueued);
void StartEvictionIfNeeded();
void EvictionDone(int result);
void PostponeWritingToDisk();
// Update the size of the entry pointed to by the given iterator. Return
// true if the new size actually results in a change.
bool UpdateEntryIteratorSize(EntrySet::iterator* it,
base::StrictNumeric<uint32_t> entry_size);
// Must run on IO Thread.
void MergeInitializingSet(std::unique_ptr<SimpleIndexLoadResult> load_result);
#if defined(OS_ANDROID)
void OnApplicationStateChange(base::android::ApplicationState state);
base::android::ApplicationStatusListener* app_status_listener_ = nullptr;
scoped_refptr<BackendCleanupTracker> cleanup_tracker_;
// The owner of |this| must ensure the |delegate_| outlives |this|.
SimpleIndexDelegate* delegate_;
EntrySet entries_set_;
const net::CacheType cache_type_;
uint64_t cache_size_ = 0; // Total cache storage size in bytes.
uint64_t max_size_ = 0;
uint64_t high_watermark_ = 0;
uint64_t low_watermark_ = 0;
bool eviction_in_progress_ = false;
base::TimeTicks eviction_start_time_;
// This stores all the entry_hash of entries that are removed during
// initialization.
std::unordered_set<uint64_t> removed_entries_;
bool initialized_ = false;
IndexInitMethod init_method_ = INITIALIZE_METHOD_MAX;
std::unique_ptr<SimpleIndexFile> index_file_;
scoped_refptr<base::SingleThreadTaskRunner> io_thread_;
// All nonstatic SimpleEntryImpl methods should always be called on the IO
// thread, in all cases. |io_thread_checker_| documents and enforces this.
base::ThreadChecker io_thread_checker_;
// Timestamp of the last time we wrote the index to disk.
// PostponeWritingToDisk() may give up postponing and allow the write if it
// has been a while since last time we wrote.
base::TimeTicks last_write_to_disk_;
base::OneShotTimer write_to_disk_timer_;
base::Closure write_to_disk_cb_;
typedef std::list<net::CompletionOnceCallback> CallbackList;
CallbackList to_run_when_initialized_;
// Set to true when the app is on the background. When the app is in the
// background we can write the index much more frequently, to insure fresh
// index on next startup.
bool app_on_background_ = false;
} // namespace disk_cache