net/disk_cache/simple/simple_index.cc

   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
   5 #include "net/disk_cache/simple/simple_index.h"
   6
   7 #include <utility>
   8
   9 #include "base/bind.h"
  10 #include "base/bind_helpers.h"
  11 #include "base/file_util.h"
  12 #include "base/files/file_enumerator.h"
  13 #include "base/logging.h"
  14 #include "base/message_loop/message_loop.h"
  15 #include "base/metrics/field_trial.h"
  16 #include "base/metrics/histogram.h"
  17 #include "base/pickle.h"
  18 #include "base/strings/string_number_conversions.h"
  19 #include "base/strings/string_tokenizer.h"
  20 #include "base/task_runner.h"
  21 #include "base/threading/worker_pool.h"
  22 #include "base/time/time.h"
  23 #include "net/base/net_errors.h"
  24 #include "net/disk_cache/simple/simple_entry_format.h"
  25 #include "net/disk_cache/simple/simple_index_file.h"
  26 #include "net/disk_cache/simple/simple_synchronous_entry.h"
  27 #include "net/disk_cache/simple/simple_util.h"
  28
  29 #if defined(OS_POSIX)
  30 #include <sys/stat.h>
  31 #include <sys/time.h>
  32 #endif
  33
  34 namespace {
  35
  36 // How many milliseconds we delay writing the index to disk since the last cache
  37 // operation has happened.
  38 const int kDefaultWriteToDiskDelayMSecs = 20000;
  39 const int kDefaultWriteToDiskOnBackgroundDelayMSecs = 100;
  40
  41 // Divides the cache space into this amount of parts to evict when only one part
  42 // is left.
  43 const uint32 kEvictionMarginDivisor = 20;
  44
  45 const uint32 kBytesInKb = 1024;
  46
  47 // Utility class used for timestamp comparisons in entry metadata while sorting.
  48 class CompareHashesForTimestamp {
  49   typedef disk_cache::SimpleIndex SimpleIndex;
  50   typedef disk_cache::SimpleIndex::EntrySet EntrySet;
  51  public:
  52   explicit CompareHashesForTimestamp(const EntrySet& set);
  53
  54   bool operator()(uint64 hash1, uint64 hash2);
  55  private:
  56   const EntrySet& entry_set_;
  57 };
  58
  59 CompareHashesForTimestamp::CompareHashesForTimestamp(const EntrySet& set)
  60   : entry_set_(set) {
  61 }
  62
  63 bool CompareHashesForTimestamp::operator()(uint64 hash1, uint64 hash2) {
  64   EntrySet::const_iterator it1 = entry_set_.find(hash1);
  65   DCHECK(it1 != entry_set_.end());
  66   EntrySet::const_iterator it2 = entry_set_.find(hash2);
  67   DCHECK(it2 != entry_set_.end());
  68   return it1->second.GetLastUsedTime() < it2->second.GetLastUsedTime();
  69 }
  70
  71 }  // namespace
  72
  73 namespace disk_cache {
  74
  75 EntryMetadata::EntryMetadata() : last_used_time_(0), entry_size_(0) {}
  76
  77 EntryMetadata::EntryMetadata(base::Time last_used_time, uint64 entry_size)
  78     : last_used_time_(last_used_time.ToInternalValue()),
  79       entry_size_(entry_size) {}
  80
  81 base::Time EntryMetadata::GetLastUsedTime() const {
  82   return base::Time::FromInternalValue(last_used_time_);
  83 }
  84
  85 void EntryMetadata::SetLastUsedTime(const base::Time& last_used_time) {
  86   last_used_time_ = last_used_time.ToInternalValue();
  87 }
  88
  89 void EntryMetadata::Serialize(Pickle* pickle) const {
  90   DCHECK(pickle);
  91   COMPILE_ASSERT(sizeof(EntryMetadata) == (sizeof(int64) + sizeof(uint64)),
  92                  EntryMetadata_has_two_member_variables);
  93   pickle->WriteInt64(last_used_time_);
  94   pickle->WriteUInt64(entry_size_);
  95 }
  96
  97 bool EntryMetadata::Deserialize(PickleIterator* it) {
  98   DCHECK(it);
  99   return it->ReadInt64(&last_used_time_) && it->ReadUInt64(&entry_size_);
 100 }
 101
 102 SimpleIndex::SimpleIndex(base::SingleThreadTaskRunner* io_thread,
 103                          const base::FilePath& cache_directory,
 104                          scoped_ptr<SimpleIndexFile> index_file)
 105     : cache_size_(0),
 106       max_size_(0),
 107       high_watermark_(0),
 108       low_watermark_(0),
 109       eviction_in_progress_(false),
 110       initialized_(false),
 111       cache_directory_(cache_directory),
 112       index_file_(index_file.Pass()),
 113       io_thread_(io_thread),
 114       // Creating the callback once so it is reused every time
 115       // write_to_disk_timer_.Start() is called.
 116       write_to_disk_cb_(base::Bind(&SimpleIndex::WriteToDisk, AsWeakPtr())),
 117       app_on_background_(false) {}
 118
 119 SimpleIndex::~SimpleIndex() {
 120   DCHECK(io_thread_checker_.CalledOnValidThread());
 121
 122   // Fail all callbacks waiting for the index to come up.
 123   for (CallbackList::iterator it = to_run_when_initialized_.begin(),
 124        end = to_run_when_initialized_.end(); it != end; ++it) {
 125     it->Run(net::ERR_ABORTED);
 126   }
 127 }
 128
 129 void SimpleIndex::Initialize(base::Time cache_mtime) {
 130   DCHECK(io_thread_checker_.CalledOnValidThread());
 131
 132   // Take the foreground and background index flush delays from the experiment
 133   // settings only if both are valid.
 134   foreground_flush_delay_ = kDefaultWriteToDiskDelayMSecs;
 135   background_flush_delay_ = kDefaultWriteToDiskOnBackgroundDelayMSecs;
 136   const std::string index_flush_intervals = base::FieldTrialList::FindFullName(
 137       "SimpleCacheIndexFlushDelay_Foreground_Background");
 138   if (!index_flush_intervals.empty()) {
 139     base::StringTokenizer tokens(index_flush_intervals, "_");
 140     int foreground_delay, background_delay;
 141     if (tokens.GetNext() &&
 142         base::StringToInt(tokens.token(), &foreground_delay) &&
 143         tokens.GetNext() &&
 144         base::StringToInt(tokens.token(), &background_delay)) {
 145       foreground_flush_delay_ = foreground_delay;
 146       background_flush_delay_ = background_delay;
 147     }
 148   }
 149
 150 #if defined(OS_ANDROID)
 151   activity_status_listener_.reset(new base::android::ActivityStatus::Listener(
 152       base::Bind(&SimpleIndex::OnActivityStateChange, AsWeakPtr())));
 153 #endif
 154
 155   SimpleIndexLoadResult* load_result = new SimpleIndexLoadResult();
 156   scoped_ptr<SimpleIndexLoadResult> load_result_scoped(load_result);
 157   base::Closure reply = base::Bind(
 158       &SimpleIndex::MergeInitializingSet,
 159       AsWeakPtr(),
 160       base::Passed(&load_result_scoped));
 161   index_file_->LoadIndexEntries(cache_mtime, reply, load_result);
 162 }
 163
 164 bool SimpleIndex::SetMaxSize(int max_bytes) {
 165   if (max_bytes < 0)
 166     return false;
 167
 168   // Zero size means use the default.
 169   if (!max_bytes)
 170     return true;
 171
 172   max_size_ = max_bytes;
 173   high_watermark_ = max_size_ - max_size_ / kEvictionMarginDivisor;
 174   low_watermark_ = max_size_ - 2 * (max_size_ / kEvictionMarginDivisor);
 175   return true;
 176 }
 177
 178 int SimpleIndex::ExecuteWhenReady(const net::CompletionCallback& task) {
 179   DCHECK(io_thread_checker_.CalledOnValidThread());
 180   if (initialized_)
 181     io_thread_->PostTask(FROM_HERE, base::Bind(task, net::OK));
 182   else
 183     to_run_when_initialized_.push_back(task);
 184   return net::ERR_IO_PENDING;
 185 }
 186
 187 scoped_ptr<SimpleIndex::HashList> SimpleIndex::RemoveEntriesBetween(
 188     const base::Time initial_time, const base::Time end_time) {
 189   return ExtractEntriesBetween(initial_time, end_time, true);
 190 }
 191
 192 scoped_ptr<SimpleIndex::HashList> SimpleIndex::GetAllHashes() {
 193   const base::Time null_time = base::Time();
 194   return ExtractEntriesBetween(null_time, null_time, false);
 195 }
 196
 197 int32 SimpleIndex::GetEntryCount() const {
 198   // TODO(pasko): return a meaningful initial estimate before initialized.
 199   return entries_set_.size();
 200 }
 201
 202 void SimpleIndex::Insert(const std::string& key) {
 203   DCHECK(io_thread_checker_.CalledOnValidThread());
 204   // Upon insert we don't know yet the size of the entry.
 205   // It will be updated later when the SimpleEntryImpl finishes opening or
 206   // creating the new entry, and then UpdateEntrySize will be called.
 207   const uint64 hash_key = simple_util::GetEntryHashKey(key);
 208   InsertInEntrySet(
 209       hash_key, EntryMetadata(base::Time::Now(), 0), &entries_set_);
 210   if (!initialized_)
 211     removed_entries_.erase(hash_key);
 212   PostponeWritingToDisk();
 213 }
 214
 215 void SimpleIndex::Remove(const std::string& key) {
 216   DCHECK(io_thread_checker_.CalledOnValidThread());
 217   const uint64 hash_key = simple_util::GetEntryHashKey(key);
 218   EntrySet::iterator it = entries_set_.find(hash_key);
 219   if (it != entries_set_.end()) {
 220     UpdateEntryIteratorSize(&it, 0);
 221     entries_set_.erase(it);
 222   }
 223
 224   if (!initialized_)
 225     removed_entries_.insert(hash_key);
 226   PostponeWritingToDisk();
 227 }
 228
 229 bool SimpleIndex::Has(uint64 hash) const {
 230   DCHECK(io_thread_checker_.CalledOnValidThread());
 231   // If not initialized, always return true, forcing it to go to the disk.
 232   return !initialized_ || entries_set_.count(hash) > 0;
 233 }
 234
 235 bool SimpleIndex::UseIfExists(const std::string& key) {
 236   DCHECK(io_thread_checker_.CalledOnValidThread());
 237   // Always update the last used time, even if it is during initialization.
 238   // It will be merged later.
 239   EntrySet::iterator it = entries_set_.find(simple_util::GetEntryHashKey(key));
 240   if (it == entries_set_.end())
 241     // If not initialized, always return true, forcing it to go to the disk.
 242     return !initialized_;
 243   it->second.SetLastUsedTime(base::Time::Now());
 244   PostponeWritingToDisk();
 245   return true;
 246 }
 247
 248 void SimpleIndex::StartEvictionIfNeeded() {
 249   DCHECK(io_thread_checker_.CalledOnValidThread());
 250   if (eviction_in_progress_ || cache_size_ <= high_watermark_)
 251     return;
 252
 253   // Take all live key hashes from the index and sort them by time.
 254   eviction_in_progress_ = true;
 255   eviction_start_time_ = base::TimeTicks::Now();
 256   UMA_HISTOGRAM_MEMORY_KB("SimpleCache.Eviction.CacheSizeOnStart2",
 257                           cache_size_ / kBytesInKb);
 258   UMA_HISTOGRAM_MEMORY_KB("SimpleCache.Eviction.MaxCacheSizeOnStart2",
 259                           max_size_ / kBytesInKb);
 260   scoped_ptr<std::vector<uint64> > entry_hashes(new std::vector<uint64>());
 261   for (EntrySet::const_iterator it = entries_set_.begin(),
 262        end = entries_set_.end(); it != end; ++it) {
 263     entry_hashes->push_back(it->first);
 264   }
 265   std::sort(entry_hashes->begin(), entry_hashes->end(),
 266             CompareHashesForTimestamp(entries_set_));
 267
 268   // Remove as many entries from the index to get below |low_watermark_|.
 269   std::vector<uint64>::iterator it = entry_hashes->begin();
 270   uint64 evicted_so_far_size = 0;
 271   while (evicted_so_far_size < cache_size_ - low_watermark_) {
 272     DCHECK(it != entry_hashes->end());
 273     EntrySet::iterator found_meta = entries_set_.find(*it);
 274     DCHECK(found_meta != entries_set_.end());
 275     uint64 to_evict_size = found_meta->second.GetEntrySize();
 276     evicted_so_far_size += to_evict_size;
 277     entries_set_.erase(found_meta);
 278     ++it;
 279   }
 280   cache_size_ -= evicted_so_far_size;
 281
 282   // Take out the rest of hashes from the eviction list.
 283   entry_hashes->erase(it, entry_hashes->end());
 284   UMA_HISTOGRAM_COUNTS("SimpleCache.Eviction.EntryCount", entry_hashes->size());
 285   UMA_HISTOGRAM_TIMES("SimpleCache.Eviction.TimeToSelectEntries",
 286                       base::TimeTicks::Now() - eviction_start_time_);
 287   UMA_HISTOGRAM_MEMORY_KB("SimpleCache.Eviction.SizeOfEvicted2",
 288                           evicted_so_far_size / kBytesInKb);
 289
 290   index_file_->DoomEntrySet(
 291       entry_hashes.Pass(),
 292       base::Bind(&SimpleIndex::EvictionDone, AsWeakPtr()));
 293 }
 294
 295 bool SimpleIndex::UpdateEntrySize(const std::string& key, uint64 entry_size) {
 296   DCHECK(io_thread_checker_.CalledOnValidThread());
 297   EntrySet::iterator it = entries_set_.find(simple_util::GetEntryHashKey(key));
 298   if (it == entries_set_.end())
 299     return false;
 300
 301   UpdateEntryIteratorSize(&it, entry_size);
 302   PostponeWritingToDisk();
 303   StartEvictionIfNeeded();
 304   return true;
 305 }
 306
 307 void SimpleIndex::EvictionDone(int result) {
 308   DCHECK(io_thread_checker_.CalledOnValidThread());
 309
 310   // Ignore the result of eviction. We did our best.
 311   eviction_in_progress_ = false;
 312   UMA_HISTOGRAM_BOOLEAN("SimpleCache.Eviction.Result", result == net::OK);
 313   UMA_HISTOGRAM_TIMES("SimpleCache.Eviction.TimeToDone",
 314                       base::TimeTicks::Now() - eviction_start_time_);
 315   UMA_HISTOGRAM_MEMORY_KB("SimpleCache.Eviction.SizeWhenDone2",
 316                           cache_size_ / kBytesInKb);
 317 }
 318
 319 // static
 320 void SimpleIndex::InsertInEntrySet(
 321     uint64 hash_key,
 322     const disk_cache::EntryMetadata& entry_metadata,
 323     EntrySet* entry_set) {
 324   DCHECK(entry_set);
 325   entry_set->insert(std::make_pair(hash_key, entry_metadata));
 326 }
 327
 328 void SimpleIndex::PostponeWritingToDisk() {
 329   if (!initialized_)
 330     return;
 331   const int delay = app_on_background_ ? background_flush_delay_
 332                                        : foreground_flush_delay_;
 333   // If the timer is already active, Start() will just Reset it, postponing it.
 334   write_to_disk_timer_.Start(
 335       FROM_HERE, base::TimeDelta::FromMilliseconds(delay), write_to_disk_cb_);
 336 }
 337
 338 void SimpleIndex::UpdateEntryIteratorSize(EntrySet::iterator* it,
 339                                           uint64 entry_size) {
 340   // Update the total cache size with the new entry size.
 341   DCHECK(io_thread_checker_.CalledOnValidThread());
 342   DCHECK_GE(cache_size_, (*it)->second.GetEntrySize());
 343   cache_size_ -= (*it)->second.GetEntrySize();
 344   cache_size_ += entry_size;
 345   (*it)->second.SetEntrySize(entry_size);
 346 }
 347
 348 void SimpleIndex::MergeInitializingSet(
 349     scoped_ptr<SimpleIndexLoadResult> load_result) {
 350   DCHECK(io_thread_checker_.CalledOnValidThread());
 351   DCHECK(load_result->did_load);
 352
 353   SimpleIndex::EntrySet* index_file_entries = &load_result->entries;
 354   // First, remove the entries that are in the |removed_entries_| from both
 355   // sets.
 356   for (base::hash_set<uint64>::const_iterator it =
 357            removed_entries_.begin(); it != removed_entries_.end(); ++it) {
 358     entries_set_.erase(*it);
 359     index_file_entries->erase(*it);
 360   }
 361
 362   for (EntrySet::const_iterator it = entries_set_.begin();
 363        it != entries_set_.end(); ++it) {
 364     const uint64 entry_hash = it->first;
 365     std::pair<EntrySet::iterator, bool> insert_result =
 366         index_file_entries->insert(EntrySet::value_type(entry_hash,
 367                                                         EntryMetadata()));
 368     EntrySet::iterator& possibly_inserted_entry = insert_result.first;
 369     possibly_inserted_entry->second = it->second;
 370   }
 371
 372   uint64 merged_cache_size = 0;
 373   for (EntrySet::iterator it = index_file_entries->begin();
 374        it != index_file_entries->end(); ++it) {
 375     merged_cache_size += it->second.GetEntrySize();
 376   }
 377
 378   entries_set_.swap(*index_file_entries);
 379   cache_size_ = merged_cache_size;
 380   initialized_ = true;
 381   removed_entries_.clear();
 382
 383   // The actual IO is asynchronous, so calling WriteToDisk() shouldn't slow the
 384   // merge down much.
 385   if (load_result->flush_required)
 386     WriteToDisk();
 387
 388   UMA_HISTOGRAM_CUSTOM_COUNTS("SimpleCache.IndexInitializationWaiters",
 389                               to_run_when_initialized_.size(), 0, 100, 20);
 390   // Run all callbacks waiting for the index to come up.
 391   for (CallbackList::iterator it = to_run_when_initialized_.begin(),
 392        end = to_run_when_initialized_.end(); it != end; ++it) {
 393     io_thread_->PostTask(FROM_HERE, base::Bind((*it), net::OK));
 394   }
 395   to_run_when_initialized_.clear();
 396 }
 397
 398 #if defined(OS_ANDROID)
 399 void SimpleIndex::OnActivityStateChange(
 400     base::android::ActivityState state) {
 401   DCHECK(io_thread_checker_.CalledOnValidThread());
 402   // For more info about android activities, see:
 403   // developer.android.com/training/basics/activity-lifecycle/pausing.html
 404   // These values are defined in the file ActivityStatus.java
 405   if (state == base::android::ACTIVITY_STATE_RESUMED) {
 406     app_on_background_ = false;
 407   } else if (state == base::android::ACTIVITY_STATE_STOPPED) {
 408     app_on_background_ = true;
 409     WriteToDisk();
 410   }
 411 }
 412 #endif
 413
 414 void SimpleIndex::WriteToDisk() {
 415   DCHECK(io_thread_checker_.CalledOnValidThread());
 416   if (!initialized_)
 417     return;
 418   UMA_HISTOGRAM_CUSTOM_COUNTS("SimpleCache.IndexNumEntriesOnWrite",
 419                               entries_set_.size(), 0, 100000, 50);
 420   const base::TimeTicks start = base::TimeTicks::Now();
 421   if (!last_write_to_disk_.is_null()) {
 422     if (app_on_background_) {
 423       UMA_HISTOGRAM_MEDIUM_TIMES("SimpleCache.IndexWriteInterval.Background",
 424                                  start - last_write_to_disk_);
 425     } else {
 426       UMA_HISTOGRAM_MEDIUM_TIMES("SimpleCache.IndexWriteInterval.Foreground",
 427                                  start - last_write_to_disk_);
 428     }
 429   }
 430   last_write_to_disk_ = start;
 431
 432   index_file_->WriteToDisk(entries_set_, cache_size_,
 433                            start, app_on_background_);
 434 }
 435
 436 scoped_ptr<SimpleIndex::HashList> SimpleIndex::ExtractEntriesBetween(
 437     const base::Time initial_time, const base::Time end_time,
 438     bool delete_entries) {
 439   DCHECK_EQ(true, initialized_);
 440   const base::Time extended_end_time =
 441       end_time.is_null() ? base::Time::Max() : end_time;
 442   DCHECK(extended_end_time >= initial_time);
 443   scoped_ptr<HashList> ret_hashes(new HashList());
 444   for (EntrySet::iterator it = entries_set_.begin(), end = entries_set_.end();
 445        it != end;) {
 446     EntryMetadata& metadata = it->second;
 447     base::Time entry_time = metadata.GetLastUsedTime();
 448     if (initial_time <= entry_time && entry_time < extended_end_time) {
 449       ret_hashes->push_back(it->first);
 450       if (delete_entries) {
 451         cache_size_ -= metadata.GetEntrySize();
 452         entries_set_.erase(it++);
 453         continue;
 454       }
 455     }
 456     ++it;
 457   }
 458   return ret_hashes.Pass();
 459 }
 460
 461 }  // namespace disk_cache