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/file_util.h"
15 #include "base/files/file_enumerator.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(base::SingleThreadTaskRunner * io_thread,SimpleIndexDelegate * delegate,net::CacheType cache_type,scoped_ptr<SimpleIndexFile> index_file)138 SimpleIndex::SimpleIndex(base::SingleThreadTaskRunner* io_thread,
139 SimpleIndexDelegate* delegate,
140 net::CacheType cache_type,
141 scoped_ptr<SimpleIndexFile> index_file)
142 : delegate_(delegate),
143 cache_type_(cache_type),
144 cache_size_(0),
145 max_size_(0),
146 high_watermark_(0),
147 low_watermark_(0),
148 eviction_in_progress_(false),
149 initialized_(false),
150 index_file_(index_file.Pass()),
151 io_thread_(io_thread),
152 // Creating the callback once so it is reused every time
153 // write_to_disk_timer_.Start() is called.
154 write_to_disk_cb_(base::Bind(&SimpleIndex::WriteToDisk, AsWeakPtr())),
155 app_on_background_(false) {}
156
~SimpleIndex()157 SimpleIndex::~SimpleIndex() {
158 DCHECK(io_thread_checker_.CalledOnValidThread());
159
160 // Fail all callbacks waiting for the index to come up.
161 for (CallbackList::iterator it = to_run_when_initialized_.begin(),
162 end = to_run_when_initialized_.end(); it != end; ++it) {
163 it->Run(net::ERR_ABORTED);
164 }
165 }
166
Initialize(base::Time cache_mtime)167 void SimpleIndex::Initialize(base::Time cache_mtime) {
168 DCHECK(io_thread_checker_.CalledOnValidThread());
169
170 #if defined(OS_ANDROID)
171 if (base::android::IsVMInitialized()) {
172 app_status_listener_.reset(new base::android::ApplicationStatusListener(
173 base::Bind(&SimpleIndex::OnApplicationStateChange, AsWeakPtr())));
174 }
175 #endif
176
177 SimpleIndexLoadResult* load_result = new SimpleIndexLoadResult();
178 scoped_ptr<SimpleIndexLoadResult> load_result_scoped(load_result);
179 base::Closure reply = base::Bind(
180 &SimpleIndex::MergeInitializingSet,
181 AsWeakPtr(),
182 base::Passed(&load_result_scoped));
183 index_file_->LoadIndexEntries(cache_mtime, reply, load_result);
184 }
185
SetMaxSize(int max_bytes)186 bool SimpleIndex::SetMaxSize(int max_bytes) {
187 if (max_bytes < 0)
188 return false;
189
190 // Zero size means use the default.
191 if (!max_bytes)
192 return true;
193
194 max_size_ = max_bytes;
195 high_watermark_ = max_size_ - max_size_ / kEvictionMarginDivisor;
196 low_watermark_ = max_size_ - 2 * (max_size_ / kEvictionMarginDivisor);
197 return true;
198 }
199
ExecuteWhenReady(const net::CompletionCallback & task)200 int SimpleIndex::ExecuteWhenReady(const net::CompletionCallback& task) {
201 DCHECK(io_thread_checker_.CalledOnValidThread());
202 if (initialized_)
203 io_thread_->PostTask(FROM_HERE, base::Bind(task, net::OK));
204 else
205 to_run_when_initialized_.push_back(task);
206 return net::ERR_IO_PENDING;
207 }
208
GetEntriesBetween(base::Time initial_time,base::Time end_time)209 scoped_ptr<SimpleIndex::HashList> SimpleIndex::GetEntriesBetween(
210 base::Time initial_time, base::Time end_time) {
211 DCHECK_EQ(true, initialized_);
212
213 if (!initial_time.is_null())
214 initial_time -= EntryMetadata::GetLowerEpsilonForTimeComparisons();
215 if (end_time.is_null())
216 end_time = base::Time::Max();
217 else
218 end_time += EntryMetadata::GetUpperEpsilonForTimeComparisons();
219 const base::Time extended_end_time =
220 end_time.is_null() ? base::Time::Max() : end_time;
221 DCHECK(extended_end_time >= initial_time);
222 scoped_ptr<HashList> ret_hashes(new HashList());
223 for (EntrySet::iterator it = entries_set_.begin(), end = entries_set_.end();
224 it != end; ++it) {
225 EntryMetadata& metadata = it->second;
226 base::Time entry_time = metadata.GetLastUsedTime();
227 if (initial_time <= entry_time && entry_time < extended_end_time)
228 ret_hashes->push_back(it->first);
229 }
230 return ret_hashes.Pass();
231 }
232
GetAllHashes()233 scoped_ptr<SimpleIndex::HashList> SimpleIndex::GetAllHashes() {
234 return GetEntriesBetween(base::Time(), base::Time());
235 }
236
GetEntryCount() const237 int32 SimpleIndex::GetEntryCount() const {
238 // TODO(pasko): return a meaningful initial estimate before initialized.
239 return entries_set_.size();
240 }
241
Insert(uint64 entry_hash)242 void SimpleIndex::Insert(uint64 entry_hash) {
243 DCHECK(io_thread_checker_.CalledOnValidThread());
244 // Upon insert we don't know yet the size of the entry.
245 // It will be updated later when the SimpleEntryImpl finishes opening or
246 // creating the new entry, and then UpdateEntrySize will be called.
247 InsertInEntrySet(
248 entry_hash, EntryMetadata(base::Time::Now(), 0), &entries_set_);
249 if (!initialized_)
250 removed_entries_.erase(entry_hash);
251 PostponeWritingToDisk();
252 }
253
Remove(uint64 entry_hash)254 void SimpleIndex::Remove(uint64 entry_hash) {
255 DCHECK(io_thread_checker_.CalledOnValidThread());
256 EntrySet::iterator it = entries_set_.find(entry_hash);
257 if (it != entries_set_.end()) {
258 UpdateEntryIteratorSize(&it, 0);
259 entries_set_.erase(it);
260 }
261
262 if (!initialized_)
263 removed_entries_.insert(entry_hash);
264 PostponeWritingToDisk();
265 }
266
Has(uint64 hash) const267 bool SimpleIndex::Has(uint64 hash) const {
268 DCHECK(io_thread_checker_.CalledOnValidThread());
269 // If not initialized, always return true, forcing it to go to the disk.
270 return !initialized_ || entries_set_.count(hash) > 0;
271 }
272
UseIfExists(uint64 entry_hash)273 bool SimpleIndex::UseIfExists(uint64 entry_hash) {
274 DCHECK(io_thread_checker_.CalledOnValidThread());
275 // Always update the last used time, even if it is during initialization.
276 // It will be merged later.
277 EntrySet::iterator it = entries_set_.find(entry_hash);
278 if (it == entries_set_.end())
279 // If not initialized, always return true, forcing it to go to the disk.
280 return !initialized_;
281 it->second.SetLastUsedTime(base::Time::Now());
282 PostponeWritingToDisk();
283 return true;
284 }
285
StartEvictionIfNeeded()286 void SimpleIndex::StartEvictionIfNeeded() {
287 DCHECK(io_thread_checker_.CalledOnValidThread());
288 if (eviction_in_progress_ || cache_size_ <= high_watermark_)
289 return;
290 // Take all live key hashes from the index and sort them by time.
291 eviction_in_progress_ = true;
292 eviction_start_time_ = base::TimeTicks::Now();
293 SIMPLE_CACHE_UMA(MEMORY_KB,
294 "Eviction.CacheSizeOnStart2", cache_type_,
295 cache_size_ / kBytesInKb);
296 SIMPLE_CACHE_UMA(MEMORY_KB,
297 "Eviction.MaxCacheSizeOnStart2", cache_type_,
298 max_size_ / kBytesInKb);
299 std::vector<uint64> entry_hashes;
300 entry_hashes.reserve(entries_set_.size());
301 for (EntrySet::const_iterator it = entries_set_.begin(),
302 end = entries_set_.end(); it != end; ++it) {
303 entry_hashes.push_back(it->first);
304 }
305 std::sort(entry_hashes.begin(), entry_hashes.end(),
306 CompareHashesForTimestamp(entries_set_));
307
308 // Remove as many entries from the index to get below |low_watermark_|.
309 std::vector<uint64>::iterator it = entry_hashes.begin();
310 uint64 evicted_so_far_size = 0;
311 while (evicted_so_far_size < cache_size_ - low_watermark_) {
312 DCHECK(it != entry_hashes.end());
313 EntrySet::iterator found_meta = entries_set_.find(*it);
314 DCHECK(found_meta != entries_set_.end());
315 uint64 to_evict_size = found_meta->second.GetEntrySize();
316 evicted_so_far_size += to_evict_size;
317 ++it;
318 }
319
320 // Take out the rest of hashes from the eviction list.
321 entry_hashes.erase(it, entry_hashes.end());
322 SIMPLE_CACHE_UMA(COUNTS,
323 "Eviction.EntryCount", cache_type_, entry_hashes.size());
324 SIMPLE_CACHE_UMA(TIMES,
325 "Eviction.TimeToSelectEntries", cache_type_,
326 base::TimeTicks::Now() - eviction_start_time_);
327 SIMPLE_CACHE_UMA(MEMORY_KB,
328 "Eviction.SizeOfEvicted2", cache_type_,
329 evicted_so_far_size / kBytesInKb);
330
331 delegate_->DoomEntries(&entry_hashes, base::Bind(&SimpleIndex::EvictionDone,
332 AsWeakPtr()));
333 }
334
UpdateEntrySize(uint64 entry_hash,int entry_size)335 bool SimpleIndex::UpdateEntrySize(uint64 entry_hash, int entry_size) {
336 DCHECK(io_thread_checker_.CalledOnValidThread());
337 EntrySet::iterator it = entries_set_.find(entry_hash);
338 if (it == entries_set_.end())
339 return false;
340
341 UpdateEntryIteratorSize(&it, entry_size);
342 PostponeWritingToDisk();
343 StartEvictionIfNeeded();
344 return true;
345 }
346
EvictionDone(int result)347 void SimpleIndex::EvictionDone(int result) {
348 DCHECK(io_thread_checker_.CalledOnValidThread());
349
350 // Ignore the result of eviction. We did our best.
351 eviction_in_progress_ = false;
352 SIMPLE_CACHE_UMA(BOOLEAN, "Eviction.Result", cache_type_, result == net::OK);
353 SIMPLE_CACHE_UMA(TIMES,
354 "Eviction.TimeToDone", cache_type_,
355 base::TimeTicks::Now() - eviction_start_time_);
356 SIMPLE_CACHE_UMA(MEMORY_KB,
357 "Eviction.SizeWhenDone2", cache_type_,
358 cache_size_ / kBytesInKb);
359 }
360
361 // static
InsertInEntrySet(uint64 entry_hash,const disk_cache::EntryMetadata & entry_metadata,EntrySet * entry_set)362 void SimpleIndex::InsertInEntrySet(
363 uint64 entry_hash,
364 const disk_cache::EntryMetadata& entry_metadata,
365 EntrySet* entry_set) {
366 DCHECK(entry_set);
367 entry_set->insert(std::make_pair(entry_hash, entry_metadata));
368 }
369
PostponeWritingToDisk()370 void SimpleIndex::PostponeWritingToDisk() {
371 if (!initialized_)
372 return;
373 const int delay = app_on_background_ ? kWriteToDiskOnBackgroundDelayMSecs
374 : kWriteToDiskDelayMSecs;
375 // If the timer is already active, Start() will just Reset it, postponing it.
376 write_to_disk_timer_.Start(
377 FROM_HERE, base::TimeDelta::FromMilliseconds(delay), write_to_disk_cb_);
378 }
379
UpdateEntryIteratorSize(EntrySet::iterator * it,int entry_size)380 void SimpleIndex::UpdateEntryIteratorSize(EntrySet::iterator* it,
381 int entry_size) {
382 // Update the total cache size with the new entry size.
383 DCHECK(io_thread_checker_.CalledOnValidThread());
384 DCHECK_GE(cache_size_, implicit_cast<uint64>((*it)->second.GetEntrySize()));
385 cache_size_ -= (*it)->second.GetEntrySize();
386 cache_size_ += entry_size;
387 (*it)->second.SetEntrySize(entry_size);
388 }
389
MergeInitializingSet(scoped_ptr<SimpleIndexLoadResult> load_result)390 void SimpleIndex::MergeInitializingSet(
391 scoped_ptr<SimpleIndexLoadResult> load_result) {
392 DCHECK(io_thread_checker_.CalledOnValidThread());
393 DCHECK(load_result->did_load);
394
395 EntrySet* index_file_entries = &load_result->entries;
396
397 for (base::hash_set<uint64>::const_iterator it = removed_entries_.begin();
398 it != removed_entries_.end(); ++it) {
399 index_file_entries->erase(*it);
400 }
401 removed_entries_.clear();
402
403 for (EntrySet::const_iterator it = entries_set_.begin();
404 it != entries_set_.end(); ++it) {
405 const uint64 entry_hash = it->first;
406 std::pair<EntrySet::iterator, bool> insert_result =
407 index_file_entries->insert(EntrySet::value_type(entry_hash,
408 EntryMetadata()));
409 EntrySet::iterator& possibly_inserted_entry = insert_result.first;
410 possibly_inserted_entry->second = it->second;
411 }
412
413 uint64 merged_cache_size = 0;
414 for (EntrySet::iterator it = index_file_entries->begin();
415 it != index_file_entries->end(); ++it) {
416 merged_cache_size += it->second.GetEntrySize();
417 }
418
419 entries_set_.swap(*index_file_entries);
420 cache_size_ = merged_cache_size;
421 initialized_ = true;
422
423 // The actual IO is asynchronous, so calling WriteToDisk() shouldn't slow the
424 // merge down much.
425 if (load_result->flush_required)
426 WriteToDisk();
427
428 SIMPLE_CACHE_UMA(CUSTOM_COUNTS,
429 "IndexInitializationWaiters", cache_type_,
430 to_run_when_initialized_.size(), 0, 100, 20);
431 // Run all callbacks waiting for the index to come up.
432 for (CallbackList::iterator it = to_run_when_initialized_.begin(),
433 end = to_run_when_initialized_.end(); it != end; ++it) {
434 io_thread_->PostTask(FROM_HERE, base::Bind((*it), net::OK));
435 }
436 to_run_when_initialized_.clear();
437 }
438
439 #if defined(OS_ANDROID)
OnApplicationStateChange(base::android::ApplicationState state)440 void SimpleIndex::OnApplicationStateChange(
441 base::android::ApplicationState state) {
442 DCHECK(io_thread_checker_.CalledOnValidThread());
443 // For more info about android activities, see:
444 // developer.android.com/training/basics/activity-lifecycle/pausing.html
445 if (state == base::android::APPLICATION_STATE_HAS_RUNNING_ACTIVITIES) {
446 app_on_background_ = false;
447 } else if (state ==
448 base::android::APPLICATION_STATE_HAS_STOPPED_ACTIVITIES) {
449 app_on_background_ = true;
450 WriteToDisk();
451 }
452 }
453 #endif
454
WriteToDisk()455 void SimpleIndex::WriteToDisk() {
456 DCHECK(io_thread_checker_.CalledOnValidThread());
457 if (!initialized_)
458 return;
459 SIMPLE_CACHE_UMA(CUSTOM_COUNTS,
460 "IndexNumEntriesOnWrite", cache_type_,
461 entries_set_.size(), 0, 100000, 50);
462 const base::TimeTicks start = base::TimeTicks::Now();
463 if (!last_write_to_disk_.is_null()) {
464 if (app_on_background_) {
465 SIMPLE_CACHE_UMA(MEDIUM_TIMES,
466 "IndexWriteInterval.Background", cache_type_,
467 start - last_write_to_disk_);
468 } else {
469 SIMPLE_CACHE_UMA(MEDIUM_TIMES,
470 "IndexWriteInterval.Foreground", cache_type_,
471 start - last_write_to_disk_);
472 }
473 }
474 last_write_to_disk_ = start;
475
476 index_file_->WriteToDisk(entries_set_, cache_size_,
477 start, app_on_background_);
478 }
479
480 } // namespace disk_cache
481