Home | History | Annotate | Download | only in simple 
      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
    462