• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
CompareHashesForTimestamp(const EntrySet & set)63 CompareHashesForTimestamp::CompareHashesForTimestamp(const EntrySet& set)
64   : entry_set_(set) {
65 }
66 
operator ()(uint64 hash1,uint64 hash2)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 
EntryMetadata()79 EntryMetadata::EntryMetadata()
80   : last_used_time_seconds_since_epoch_(0),
81     entry_size_(0) {
82 }
83 
EntryMetadata(base::Time last_used_time,int entry_size)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 
GetLastUsedTime() const90 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 
SetLastUsedTime(const base::Time & last_used_time)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 
Serialize(Pickle * pickle) const120 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 
Deserialize(PickleIterator * it)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 
SimpleIndex(const scoped_refptr<base::SingleThreadTaskRunner> & io_thread,SimpleIndexDelegate * delegate,net::CacheType cache_type,scoped_ptr<SimpleIndexFile> index_file)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 
~SimpleIndex()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 
Initialize(base::Time cache_mtime)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 
SetMaxSize(int max_bytes)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 
ExecuteWhenReady(const net::CompletionCallback & task)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 
GetEntriesBetween(base::Time initial_time,base::Time end_time)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 
GetAllHashes()235 scoped_ptr<SimpleIndex::HashList> SimpleIndex::GetAllHashes() {
236   return GetEntriesBetween(base::Time(), base::Time());
237 }
238 
GetEntryCount() const239 int32 SimpleIndex::GetEntryCount() const {
240   // TODO(pasko): return a meaningful initial estimate before initialized.
241   return entries_set_.size();
242 }
243 
Insert(uint64 entry_hash)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 
Remove(uint64 entry_hash)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 
Has(uint64 hash) const269 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 
UseIfExists(uint64 entry_hash)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 
StartEvictionIfNeeded()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 
UpdateEntrySize(uint64 entry_hash,int entry_size)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 
EvictionDone(int result)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
InsertInEntrySet(uint64 entry_hash,const disk_cache::EntryMetadata & entry_metadata,EntrySet * entry_set)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 
PostponeWritingToDisk()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 
UpdateEntryIteratorSize(EntrySet::iterator * it,int entry_size)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 
MergeInitializingSet(scoped_ptr<SimpleIndexLoadResult> load_result)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)
OnApplicationStateChange(base::android::ApplicationState state)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 
WriteToDisk()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