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
38namespace {
39
40// How many milliseconds we delay writing the index to disk since the last cache
41// operation has happened.
42const int kWriteToDiskDelayMSecs = 20000;
43const int kWriteToDiskOnBackgroundDelayMSecs = 100;
44
45// Divides the cache space into this amount of parts to evict when only one part
46// is left.
47const uint32 kEvictionMarginDivisor = 20;
48
49const uint32 kBytesInKb = 1024;
50
51// Utility class used for timestamp comparisons in entry metadata while sorting.
52class 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
63CompareHashesForTimestamp::CompareHashesForTimestamp(const EntrySet& set)
64  : entry_set_(set) {
65}
66
67bool 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
77namespace disk_cache {
78
79EntryMetadata::EntryMetadata()
80  : last_used_time_seconds_since_epoch_(0),
81    entry_size_(0) {
82}
83
84EntryMetadata::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
90base::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
99void 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
120void 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
127bool 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
138SimpleIndex::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
159SimpleIndex::~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
169void 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
188bool 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
202int 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
211scoped_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
235scoped_ptr<SimpleIndex::HashList> SimpleIndex::GetAllHashes() {
236  return GetEntriesBetween(base::Time(), base::Time());
237}
238
239int32 SimpleIndex::GetEntryCount() const {
240  // TODO(pasko): return a meaningful initial estimate before initialized.
241  return entries_set_.size();
242}
243
244void 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
256void 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
269bool 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
275bool 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
288void 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
337bool 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
349void 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
364void 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
372void 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
382void 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
392void 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)
442void 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
457void 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