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