1// Copyright (c) 2012 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/backend_impl.h"
6
7#include "base/bind.h"
8#include "base/bind_helpers.h"
9#include "base/file_util.h"
10#include "base/files/file_path.h"
11#include "base/hash.h"
12#include "base/message_loop/message_loop.h"
13#include "base/metrics/field_trial.h"
14#include "base/metrics/histogram.h"
15#include "base/metrics/stats_counters.h"
16#include "base/rand_util.h"
17#include "base/strings/string_util.h"
18#include "base/strings/stringprintf.h"
19#include "base/sys_info.h"
20#include "base/threading/thread_restrictions.h"
21#include "base/time/time.h"
22#include "base/timer/timer.h"
23#include "net/base/net_errors.h"
24#include "net/disk_cache/cache_util.h"
25#include "net/disk_cache/entry_impl.h"
26#include "net/disk_cache/errors.h"
27#include "net/disk_cache/experiments.h"
28#include "net/disk_cache/file.h"
29
30// This has to be defined before including histogram_macros.h from this file.
31#define NET_DISK_CACHE_BACKEND_IMPL_CC_
32#include "net/disk_cache/histogram_macros.h"
33
34using base::Time;
35using base::TimeDelta;
36using base::TimeTicks;
37
38namespace {
39
40const char* kIndexName = "index";
41
42// Seems like ~240 MB correspond to less than 50k entries for 99% of the people.
43// Note that the actual target is to keep the index table load factor under 55%
44// for most users.
45const int k64kEntriesStore = 240 * 1000 * 1000;
46const int kBaseTableLen = 64 * 1024;
47const int kDefaultCacheSize = 80 * 1024 * 1024;
48
49// Avoid trimming the cache for the first 5 minutes (10 timer ticks).
50const int kTrimDelay = 10;
51
52int DesiredIndexTableLen(int32 storage_size) {
53  if (storage_size <= k64kEntriesStore)
54    return kBaseTableLen;
55  if (storage_size <= k64kEntriesStore * 2)
56    return kBaseTableLen * 2;
57  if (storage_size <= k64kEntriesStore * 4)
58    return kBaseTableLen * 4;
59  if (storage_size <= k64kEntriesStore * 8)
60    return kBaseTableLen * 8;
61
62  // The biggest storage_size for int32 requires a 4 MB table.
63  return kBaseTableLen * 16;
64}
65
66int MaxStorageSizeForTable(int table_len) {
67  return table_len * (k64kEntriesStore / kBaseTableLen);
68}
69
70size_t GetIndexSize(int table_len) {
71  size_t table_size = sizeof(disk_cache::CacheAddr) * table_len;
72  return sizeof(disk_cache::IndexHeader) + table_size;
73}
74
75}  // namespace
76
77// ------------------------------------------------------------------------
78
79namespace disk_cache {
80
81BackendImpl::BackendImpl(const base::FilePath& path,
82                         base::MessageLoopProxy* cache_thread,
83                         net::NetLog* net_log)
84    : background_queue_(this, cache_thread),
85      path_(path),
86      block_files_(path),
87      mask_(0),
88      max_size_(0),
89      up_ticks_(0),
90      cache_type_(net::DISK_CACHE),
91      uma_report_(0),
92      user_flags_(0),
93      init_(false),
94      restarted_(false),
95      unit_test_(false),
96      read_only_(false),
97      disabled_(false),
98      new_eviction_(false),
99      first_timer_(true),
100      user_load_(false),
101      net_log_(net_log),
102      done_(true, false),
103      ptr_factory_(this) {
104}
105
106BackendImpl::BackendImpl(const base::FilePath& path,
107                         uint32 mask,
108                         base::MessageLoopProxy* cache_thread,
109                         net::NetLog* net_log)
110    : background_queue_(this, cache_thread),
111      path_(path),
112      block_files_(path),
113      mask_(mask),
114      max_size_(0),
115      up_ticks_(0),
116      cache_type_(net::DISK_CACHE),
117      uma_report_(0),
118      user_flags_(kMask),
119      init_(false),
120      restarted_(false),
121      unit_test_(false),
122      read_only_(false),
123      disabled_(false),
124      new_eviction_(false),
125      first_timer_(true),
126      user_load_(false),
127      net_log_(net_log),
128      done_(true, false),
129      ptr_factory_(this) {
130}
131
132BackendImpl::~BackendImpl() {
133  if (user_flags_ & kNoRandom) {
134    // This is a unit test, so we want to be strict about not leaking entries
135    // and completing all the work.
136    background_queue_.WaitForPendingIO();
137  } else {
138    // This is most likely not a test, so we want to do as little work as
139    // possible at this time, at the price of leaving dirty entries behind.
140    background_queue_.DropPendingIO();
141  }
142
143  if (background_queue_.BackgroundIsCurrentThread()) {
144    // Unit tests may use the same thread for everything.
145    CleanupCache();
146  } else {
147    background_queue_.background_thread()->PostTask(
148        FROM_HERE, base::Bind(&FinalCleanupCallback, base::Unretained(this)));
149    // http://crbug.com/74623
150    base::ThreadRestrictions::ScopedAllowWait allow_wait;
151    done_.Wait();
152  }
153}
154
155int BackendImpl::Init(const CompletionCallback& callback) {
156  background_queue_.Init(callback);
157  return net::ERR_IO_PENDING;
158}
159
160// ------------------------------------------------------------------------
161
162int BackendImpl::OpenPrevEntry(void** iter, Entry** prev_entry,
163                               const CompletionCallback& callback) {
164  DCHECK(!callback.is_null());
165  background_queue_.OpenPrevEntry(iter, prev_entry, callback);
166  return net::ERR_IO_PENDING;
167}
168
169bool BackendImpl::SetMaxSize(int max_bytes) {
170  COMPILE_ASSERT(sizeof(max_bytes) == sizeof(max_size_), unsupported_int_model);
171  if (max_bytes < 0)
172    return false;
173
174  // Zero size means use the default.
175  if (!max_bytes)
176    return true;
177
178  // Avoid a DCHECK later on.
179  if (max_bytes >= kint32max - kint32max / 10)
180    max_bytes = kint32max - kint32max / 10 - 1;
181
182  user_flags_ |= kMaxSize;
183  max_size_ = max_bytes;
184  return true;
185}
186
187void BackendImpl::SetType(net::CacheType type) {
188  DCHECK_NE(net::MEMORY_CACHE, type);
189  cache_type_ = type;
190}
191
192bool BackendImpl::CreateBlock(FileType block_type, int block_count,
193                             Addr* block_address) {
194  return block_files_.CreateBlock(block_type, block_count, block_address);
195}
196
197void BackendImpl::UpdateRank(EntryImpl* entry, bool modified) {
198  if (read_only_ || (!modified && cache_type() == net::SHADER_CACHE))
199    return;
200  eviction_.UpdateRank(entry, modified);
201}
202
203void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
204  uint32 hash = entry->GetHash();
205  std::string key = entry->GetKey();
206  Addr entry_addr = entry->entry()->address();
207  bool error;
208  EntryImpl* parent_entry = MatchEntry(key, hash, true, entry_addr, &error);
209  CacheAddr child(entry->GetNextAddress());
210
211  Trace("Doom entry 0x%p", entry);
212
213  if (!entry->doomed()) {
214    // We may have doomed this entry from within MatchEntry.
215    eviction_.OnDoomEntry(entry);
216    entry->InternalDoom();
217    if (!new_eviction_) {
218      DecreaseNumEntries();
219    }
220    stats_.OnEvent(Stats::DOOM_ENTRY);
221  }
222
223  if (parent_entry) {
224    parent_entry->SetNextAddress(Addr(child));
225    parent_entry->Release();
226  } else if (!error) {
227    data_->table[hash & mask_] = child;
228  }
229
230  FlushIndex();
231}
232
233void BackendImpl::OnEntryDestroyBegin(Addr address) {
234  EntriesMap::iterator it = open_entries_.find(address.value());
235  if (it != open_entries_.end())
236    open_entries_.erase(it);
237}
238
239void BackendImpl::OnEntryDestroyEnd() {
240  DecreaseNumRefs();
241  if (data_->header.num_bytes > max_size_ && !read_only_ &&
242      (up_ticks_ > kTrimDelay || user_flags_ & kNoRandom))
243    eviction_.TrimCache(false);
244}
245
246EntryImpl* BackendImpl::GetOpenEntry(CacheRankingsBlock* rankings) const {
247  DCHECK(rankings->HasData());
248  EntriesMap::const_iterator it =
249      open_entries_.find(rankings->Data()->contents);
250  if (it != open_entries_.end()) {
251    // We have this entry in memory.
252    return it->second;
253  }
254
255  return NULL;
256}
257
258int BackendImpl::MaxFileSize() const {
259  return max_size_ / 8;
260}
261
262void BackendImpl::ModifyStorageSize(int32 old_size, int32 new_size) {
263  if (disabled_ || old_size == new_size)
264    return;
265  if (old_size > new_size)
266    SubstractStorageSize(old_size - new_size);
267  else
268    AddStorageSize(new_size - old_size);
269
270  FlushIndex();
271
272  // Update the usage statistics.
273  stats_.ModifyStorageStats(old_size, new_size);
274}
275
276void BackendImpl::TooMuchStorageRequested(int32 size) {
277  stats_.ModifyStorageStats(0, size);
278}
279
280bool BackendImpl::IsAllocAllowed(int current_size, int new_size) {
281  DCHECK_GT(new_size, current_size);
282  if (user_flags_ & kNoBuffering)
283    return false;
284
285  int to_add = new_size - current_size;
286  if (buffer_bytes_ + to_add > MaxBuffersSize())
287    return false;
288
289  buffer_bytes_ += to_add;
290  CACHE_UMA(COUNTS_50000, "BufferBytes", 0, buffer_bytes_ / 1024);
291  return true;
292}
293
294void BackendImpl::BufferDeleted(int size) {
295  buffer_bytes_ -= size;
296  DCHECK_GE(size, 0);
297}
298
299bool BackendImpl::IsLoaded() const {
300  CACHE_UMA(COUNTS, "PendingIO", 0, num_pending_io_);
301  if (user_flags_ & kNoLoadProtection)
302    return false;
303
304  return (num_pending_io_ > 5 || user_load_);
305}
306
307std::string BackendImpl::HistogramName(const char* name, int experiment) const {
308  if (!experiment)
309    return base::StringPrintf("DiskCache.%d.%s", cache_type_, name);
310  return base::StringPrintf("DiskCache.%d.%s_%d", cache_type_,
311                            name, experiment);
312}
313
314base::WeakPtr<BackendImpl> BackendImpl::GetWeakPtr() {
315  return ptr_factory_.GetWeakPtr();
316}
317
318// We want to remove biases from some histograms so we only send data once per
319// week.
320bool BackendImpl::ShouldReportAgain() {
321  if (uma_report_)
322    return uma_report_ == 2;
323
324  uma_report_++;
325  int64 last_report = stats_.GetCounter(Stats::LAST_REPORT);
326  Time last_time = Time::FromInternalValue(last_report);
327  if (!last_report || (Time::Now() - last_time).InDays() >= 7) {
328    stats_.SetCounter(Stats::LAST_REPORT, Time::Now().ToInternalValue());
329    uma_report_++;
330    return true;
331  }
332  return false;
333}
334
335void BackendImpl::FirstEviction() {
336  DCHECK(data_->header.create_time);
337  if (!GetEntryCount())
338    return;  // This is just for unit tests.
339
340  Time create_time = Time::FromInternalValue(data_->header.create_time);
341  CACHE_UMA(AGE, "FillupAge", 0, create_time);
342
343  int64 use_time = stats_.GetCounter(Stats::TIMER);
344  CACHE_UMA(HOURS, "FillupTime", 0, static_cast<int>(use_time / 120));
345  CACHE_UMA(PERCENTAGE, "FirstHitRatio", 0, stats_.GetHitRatio());
346
347  if (!use_time)
348    use_time = 1;
349  CACHE_UMA(COUNTS_10000, "FirstEntryAccessRate", 0,
350            static_cast<int>(data_->header.num_entries / use_time));
351  CACHE_UMA(COUNTS, "FirstByteIORate", 0,
352            static_cast<int>((data_->header.num_bytes / 1024) / use_time));
353
354  int avg_size = data_->header.num_bytes / GetEntryCount();
355  CACHE_UMA(COUNTS, "FirstEntrySize", 0, avg_size);
356
357  int large_entries_bytes = stats_.GetLargeEntriesSize();
358  int large_ratio = large_entries_bytes * 100 / data_->header.num_bytes;
359  CACHE_UMA(PERCENTAGE, "FirstLargeEntriesRatio", 0, large_ratio);
360
361  if (new_eviction_) {
362    CACHE_UMA(PERCENTAGE, "FirstResurrectRatio", 0, stats_.GetResurrectRatio());
363    CACHE_UMA(PERCENTAGE, "FirstNoUseRatio", 0,
364              data_->header.lru.sizes[0] * 100 / data_->header.num_entries);
365    CACHE_UMA(PERCENTAGE, "FirstLowUseRatio", 0,
366              data_->header.lru.sizes[1] * 100 / data_->header.num_entries);
367    CACHE_UMA(PERCENTAGE, "FirstHighUseRatio", 0,
368              data_->header.lru.sizes[2] * 100 / data_->header.num_entries);
369  }
370
371  stats_.ResetRatios();
372}
373
374void BackendImpl::OnEvent(Stats::Counters an_event) {
375  stats_.OnEvent(an_event);
376}
377
378void BackendImpl::OnRead(int32 bytes) {
379  DCHECK_GE(bytes, 0);
380  byte_count_ += bytes;
381  if (byte_count_ < 0)
382    byte_count_ = kint32max;
383}
384
385void BackendImpl::OnWrite(int32 bytes) {
386  // We use the same implementation as OnRead... just log the number of bytes.
387  OnRead(bytes);
388}
389
390void BackendImpl::OnStatsTimer() {
391  stats_.OnEvent(Stats::TIMER);
392  int64 time = stats_.GetCounter(Stats::TIMER);
393  int64 current = stats_.GetCounter(Stats::OPEN_ENTRIES);
394
395  // OPEN_ENTRIES is a sampled average of the number of open entries, avoiding
396  // the bias towards 0.
397  if (num_refs_ && (current != num_refs_)) {
398    int64 diff = (num_refs_ - current) / 50;
399    if (!diff)
400      diff = num_refs_ > current ? 1 : -1;
401    current = current + diff;
402    stats_.SetCounter(Stats::OPEN_ENTRIES, current);
403    stats_.SetCounter(Stats::MAX_ENTRIES, max_refs_);
404  }
405
406  CACHE_UMA(COUNTS, "NumberOfReferences", 0, num_refs_);
407
408  CACHE_UMA(COUNTS_10000, "EntryAccessRate", 0, entry_count_);
409  CACHE_UMA(COUNTS, "ByteIORate", 0, byte_count_ / 1024);
410
411  // These values cover about 99.5% of the population (Oct 2011).
412  user_load_ = (entry_count_ > 300 || byte_count_ > 7 * 1024 * 1024);
413  entry_count_ = 0;
414  byte_count_ = 0;
415  up_ticks_++;
416
417  if (!data_)
418    first_timer_ = false;
419  if (first_timer_) {
420    first_timer_ = false;
421    if (ShouldReportAgain())
422      ReportStats();
423  }
424
425  // Save stats to disk at 5 min intervals.
426  if (time % 10 == 0)
427    StoreStats();
428}
429
430void BackendImpl::SetUnitTestMode() {
431  user_flags_ |= kUnitTestMode;
432  unit_test_ = true;
433}
434
435void BackendImpl::SetUpgradeMode() {
436  user_flags_ |= kUpgradeMode;
437  read_only_ = true;
438}
439
440void BackendImpl::SetNewEviction() {
441  user_flags_ |= kNewEviction;
442  new_eviction_ = true;
443}
444
445void BackendImpl::SetFlags(uint32 flags) {
446  user_flags_ |= flags;
447}
448
449int BackendImpl::FlushQueueForTest(const CompletionCallback& callback) {
450  background_queue_.FlushQueue(callback);
451  return net::ERR_IO_PENDING;
452}
453
454void BackendImpl::TrimForTest(bool empty) {
455  eviction_.SetTestMode();
456  eviction_.TrimCache(empty);
457}
458
459void BackendImpl::TrimDeletedListForTest(bool empty) {
460  eviction_.SetTestMode();
461  eviction_.TrimDeletedList(empty);
462}
463
464int BackendImpl::SelfCheck() {
465  if (!init_) {
466    LOG(ERROR) << "Init failed";
467    return ERR_INIT_FAILED;
468  }
469
470  int num_entries = rankings_.SelfCheck();
471  if (num_entries < 0) {
472    LOG(ERROR) << "Invalid rankings list, error " << num_entries;
473#if !defined(NET_BUILD_STRESS_CACHE)
474    return num_entries;
475#endif
476  }
477
478  if (num_entries != data_->header.num_entries) {
479    LOG(ERROR) << "Number of entries mismatch";
480#if !defined(NET_BUILD_STRESS_CACHE)
481    return ERR_NUM_ENTRIES_MISMATCH;
482#endif
483  }
484
485  return CheckAllEntries();
486}
487
488// ------------------------------------------------------------------------
489
490net::CacheType BackendImpl::GetCacheType() const {
491  return cache_type_;
492}
493
494int32 BackendImpl::GetEntryCount() const {
495  if (!index_.get() || disabled_)
496    return 0;
497  // num_entries includes entries already evicted.
498  int32 not_deleted = data_->header.num_entries -
499                      data_->header.lru.sizes[Rankings::DELETED];
500
501  if (not_deleted < 0) {
502    NOTREACHED();
503    not_deleted = 0;
504  }
505
506  return not_deleted;
507}
508
509EntryImpl* BackendImpl::OpenEntryImpl(const std::string& key) {
510  if (disabled_)
511    return NULL;
512
513  TimeTicks start = TimeTicks::Now();
514  uint32 hash = base::Hash(key);
515  Trace("Open hash 0x%x", hash);
516
517  bool error;
518  EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
519  if (cache_entry && ENTRY_NORMAL != cache_entry->entry()->Data()->state) {
520    // The entry was already evicted.
521    cache_entry->Release();
522    cache_entry = NULL;
523  }
524
525  int current_size = data_->header.num_bytes / (1024 * 1024);
526  int64 total_hours = stats_.GetCounter(Stats::TIMER) / 120;
527  int64 no_use_hours = stats_.GetCounter(Stats::LAST_REPORT_TIMER) / 120;
528  int64 use_hours = total_hours - no_use_hours;
529
530  if (!cache_entry) {
531    CACHE_UMA(AGE_MS, "OpenTime.Miss", 0, start);
532    CACHE_UMA(COUNTS_10000, "AllOpenBySize.Miss", 0, current_size);
533    CACHE_UMA(HOURS, "AllOpenByTotalHours.Miss", 0, total_hours);
534    CACHE_UMA(HOURS, "AllOpenByUseHours.Miss", 0, use_hours);
535    stats_.OnEvent(Stats::OPEN_MISS);
536    return NULL;
537  }
538
539  eviction_.OnOpenEntry(cache_entry);
540  entry_count_++;
541
542  Trace("Open hash 0x%x end: 0x%x", hash,
543        cache_entry->entry()->address().value());
544  CACHE_UMA(AGE_MS, "OpenTime", 0, start);
545  CACHE_UMA(COUNTS_10000, "AllOpenBySize.Hit", 0, current_size);
546  CACHE_UMA(HOURS, "AllOpenByTotalHours.Hit", 0, total_hours);
547  CACHE_UMA(HOURS, "AllOpenByUseHours.Hit", 0, use_hours);
548  stats_.OnEvent(Stats::OPEN_HIT);
549  SIMPLE_STATS_COUNTER("disk_cache.hit");
550  return cache_entry;
551}
552
553EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) {
554  if (disabled_ || key.empty())
555    return NULL;
556
557  TimeTicks start = TimeTicks::Now();
558  Trace("Create hash 0x%x", hash);
559
560  scoped_refptr<EntryImpl> parent;
561  Addr entry_address(data_->table[hash & mask_]);
562  if (entry_address.is_initialized()) {
563    // We have an entry already. It could be the one we are looking for, or just
564    // a hash conflict.
565    bool error;
566    EntryImpl* old_entry = MatchEntry(key, hash, false, Addr(), &error);
567    if (old_entry)
568      return ResurrectEntry(old_entry);
569
570    EntryImpl* parent_entry = MatchEntry(key, hash, true, Addr(), &error);
571    DCHECK(!error);
572    if (parent_entry) {
573      parent.swap(&parent_entry);
574    } else if (data_->table[hash & mask_]) {
575      // We should have corrected the problem.
576      NOTREACHED();
577      return NULL;
578    }
579  }
580
581  // The general flow is to allocate disk space and initialize the entry data,
582  // followed by saving that to disk, then linking the entry though the index
583  // and finally through the lists. If there is a crash in this process, we may
584  // end up with:
585  // a. Used, unreferenced empty blocks on disk (basically just garbage).
586  // b. Used, unreferenced but meaningful data on disk (more garbage).
587  // c. A fully formed entry, reachable only through the index.
588  // d. A fully formed entry, also reachable through the lists, but still dirty.
589  //
590  // Anything after (b) can be automatically cleaned up. We may consider saving
591  // the current operation (as we do while manipulating the lists) so that we
592  // can detect and cleanup (a) and (b).
593
594  int num_blocks = EntryImpl::NumBlocksForEntry(key.size());
595  if (!block_files_.CreateBlock(BLOCK_256, num_blocks, &entry_address)) {
596    LOG(ERROR) << "Create entry failed " << key.c_str();
597    stats_.OnEvent(Stats::CREATE_ERROR);
598    return NULL;
599  }
600
601  Addr node_address(0);
602  if (!block_files_.CreateBlock(RANKINGS, 1, &node_address)) {
603    block_files_.DeleteBlock(entry_address, false);
604    LOG(ERROR) << "Create entry failed " << key.c_str();
605    stats_.OnEvent(Stats::CREATE_ERROR);
606    return NULL;
607  }
608
609  scoped_refptr<EntryImpl> cache_entry(
610      new EntryImpl(this, entry_address, false));
611  IncreaseNumRefs();
612
613  if (!cache_entry->CreateEntry(node_address, key, hash)) {
614    block_files_.DeleteBlock(entry_address, false);
615    block_files_.DeleteBlock(node_address, false);
616    LOG(ERROR) << "Create entry failed " << key.c_str();
617    stats_.OnEvent(Stats::CREATE_ERROR);
618    return NULL;
619  }
620
621  cache_entry->BeginLogging(net_log_, true);
622
623  // We are not failing the operation; let's add this to the map.
624  open_entries_[entry_address.value()] = cache_entry.get();
625
626  // Save the entry.
627  cache_entry->entry()->Store();
628  cache_entry->rankings()->Store();
629  IncreaseNumEntries();
630  entry_count_++;
631
632  // Link this entry through the index.
633  if (parent.get()) {
634    parent->SetNextAddress(entry_address);
635  } else {
636    data_->table[hash & mask_] = entry_address.value();
637  }
638
639  // Link this entry through the lists.
640  eviction_.OnCreateEntry(cache_entry.get());
641
642  CACHE_UMA(AGE_MS, "CreateTime", 0, start);
643  stats_.OnEvent(Stats::CREATE_HIT);
644  SIMPLE_STATS_COUNTER("disk_cache.miss");
645  Trace("create entry hit ");
646  FlushIndex();
647  cache_entry->AddRef();
648  return cache_entry.get();
649}
650
651int BackendImpl::SyncDoomEntry(const std::string& key) {
652  if (disabled_)
653    return net::ERR_FAILED;
654
655  EntryImpl* entry = OpenEntryImpl(key);
656  if (!entry)
657    return net::ERR_FAILED;
658
659  entry->DoomImpl();
660  entry->Release();
661  return net::OK;
662}
663
664int BackendImpl::SyncDoomAllEntries() {
665  // This is not really an error, but it is an interesting condition.
666  ReportError(ERR_CACHE_DOOMED);
667  stats_.OnEvent(Stats::DOOM_CACHE);
668  if (!num_refs_) {
669    RestartCache(false);
670    return disabled_ ? net::ERR_FAILED : net::OK;
671  } else {
672    if (disabled_)
673      return net::ERR_FAILED;
674
675    eviction_.TrimCache(true);
676    return net::OK;
677  }
678}
679
680int BackendImpl::SyncDoomEntriesBetween(const base::Time initial_time,
681                                        const base::Time end_time) {
682  DCHECK_NE(net::APP_CACHE, cache_type_);
683  if (end_time.is_null())
684    return SyncDoomEntriesSince(initial_time);
685
686  DCHECK(end_time >= initial_time);
687
688  if (disabled_)
689    return net::ERR_FAILED;
690
691  EntryImpl* node;
692  void* iter = NULL;
693  EntryImpl* next = OpenNextEntryImpl(&iter);
694  if (!next)
695    return net::OK;
696
697  while (next) {
698    node = next;
699    next = OpenNextEntryImpl(&iter);
700
701    if (node->GetLastUsed() >= initial_time &&
702        node->GetLastUsed() < end_time) {
703      node->DoomImpl();
704    } else if (node->GetLastUsed() < initial_time) {
705      if (next)
706        next->Release();
707      next = NULL;
708      SyncEndEnumeration(iter);
709    }
710
711    node->Release();
712  }
713
714  return net::OK;
715}
716
717// We use OpenNextEntryImpl to retrieve elements from the cache, until we get
718// entries that are too old.
719int BackendImpl::SyncDoomEntriesSince(const base::Time initial_time) {
720  DCHECK_NE(net::APP_CACHE, cache_type_);
721  if (disabled_)
722    return net::ERR_FAILED;
723
724  stats_.OnEvent(Stats::DOOM_RECENT);
725  for (;;) {
726    void* iter = NULL;
727    EntryImpl* entry = OpenNextEntryImpl(&iter);
728    if (!entry)
729      return net::OK;
730
731    if (initial_time > entry->GetLastUsed()) {
732      entry->Release();
733      SyncEndEnumeration(iter);
734      return net::OK;
735    }
736
737    entry->DoomImpl();
738    entry->Release();
739    SyncEndEnumeration(iter);  // Dooming the entry invalidates the iterator.
740  }
741}
742
743int BackendImpl::OpenNextEntry(void** iter, Entry** next_entry,
744                               const CompletionCallback& callback) {
745  DCHECK(!callback.is_null());
746  background_queue_.OpenNextEntry(iter, next_entry, callback);
747  return net::ERR_IO_PENDING;
748}
749
750void BackendImpl::EndEnumeration(void** iter) {
751  background_queue_.EndEnumeration(*iter);
752  *iter = NULL;
753}
754
755void BackendImpl::GetStats(StatsItems* stats) {
756  if (disabled_)
757    return;
758
759  std::pair<std::string, std::string> item;
760
761  item.first = "Entries";
762  item.second = base::StringPrintf("%d", data_->header.num_entries);
763  stats->push_back(item);
764
765  item.first = "Pending IO";
766  item.second = base::StringPrintf("%d", num_pending_io_);
767  stats->push_back(item);
768
769  item.first = "Max size";
770  item.second = base::StringPrintf("%d", max_size_);
771  stats->push_back(item);
772
773  item.first = "Current size";
774  item.second = base::StringPrintf("%d", data_->header.num_bytes);
775  stats->push_back(item);
776
777  item.first = "Cache type";
778  item.second = "Blockfile Cache";
779  stats->push_back(item);
780
781  stats_.GetItems(stats);
782}
783
784void BackendImpl::SyncOnExternalCacheHit(const std::string& key) {
785  if (disabled_)
786    return;
787
788  uint32 hash = base::Hash(key);
789  bool error;
790  EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
791  if (cache_entry) {
792    if (ENTRY_NORMAL == cache_entry->entry()->Data()->state) {
793      UpdateRank(cache_entry, cache_type() == net::SHADER_CACHE);
794    }
795    cache_entry->Release();
796  }
797}
798
799// ------------------------------------------------------------------------
800
801// The maximum cache size will be either set explicitly by the caller, or
802// calculated by this code.
803void BackendImpl::AdjustMaxCacheSize(int table_len) {
804  if (max_size_)
805    return;
806
807  // If table_len is provided, the index file exists.
808  DCHECK(!table_len || data_->header.magic);
809
810  // The user is not setting the size, let's figure it out.
811  int64 available = base::SysInfo::AmountOfFreeDiskSpace(path_);
812  if (available < 0) {
813    max_size_ = kDefaultCacheSize;
814    return;
815  }
816
817  if (table_len)
818    available += data_->header.num_bytes;
819
820  max_size_ = PreferedCacheSize(available);
821
822  // Let's not use more than the default size while we tune-up the performance
823  // of bigger caches. TODO(rvargas): remove this limit.
824  if (max_size_ > kDefaultCacheSize * 4)
825    max_size_ = kDefaultCacheSize * 4;
826
827  if (!table_len)
828    return;
829
830  // If we already have a table, adjust the size to it.
831  int current_max_size = MaxStorageSizeForTable(table_len);
832  if (max_size_ > current_max_size)
833    max_size_= current_max_size;
834}
835
836bool BackendImpl::InitStats() {
837  Addr address(data_->header.stats);
838  int size = stats_.StorageSize();
839
840  if (!address.is_initialized()) {
841    FileType file_type = Addr::RequiredFileType(size);
842    DCHECK_NE(file_type, EXTERNAL);
843    int num_blocks = Addr::RequiredBlocks(size, file_type);
844
845    if (!CreateBlock(file_type, num_blocks, &address))
846      return false;
847    return stats_.Init(NULL, 0, address);
848  }
849
850  if (!address.is_block_file()) {
851    NOTREACHED();
852    return false;
853  }
854
855  // Load the required data.
856  size = address.num_blocks() * address.BlockSize();
857  MappedFile* file = File(address);
858  if (!file)
859    return false;
860
861  scoped_ptr<char[]> data(new char[size]);
862  size_t offset = address.start_block() * address.BlockSize() +
863                  kBlockHeaderSize;
864  if (!file->Read(data.get(), size, offset))
865    return false;
866
867  if (!stats_.Init(data.get(), size, address))
868    return false;
869  if (cache_type_ == net::DISK_CACHE && ShouldReportAgain())
870    stats_.InitSizeHistogram();
871  return true;
872}
873
874void BackendImpl::StoreStats() {
875  int size = stats_.StorageSize();
876  scoped_ptr<char[]> data(new char[size]);
877  Addr address;
878  size = stats_.SerializeStats(data.get(), size, &address);
879  DCHECK(size);
880  if (!address.is_initialized())
881    return;
882
883  MappedFile* file = File(address);
884  if (!file)
885    return;
886
887  size_t offset = address.start_block() * address.BlockSize() +
888                  kBlockHeaderSize;
889  file->Write(data.get(), size, offset);  // ignore result.
890}
891
892void BackendImpl::RestartCache(bool failure) {
893  int64 errors = stats_.GetCounter(Stats::FATAL_ERROR);
894  int64 full_dooms = stats_.GetCounter(Stats::DOOM_CACHE);
895  int64 partial_dooms = stats_.GetCounter(Stats::DOOM_RECENT);
896  int64 last_report = stats_.GetCounter(Stats::LAST_REPORT);
897
898  PrepareForRestart();
899  if (failure) {
900    DCHECK(!num_refs_);
901    DCHECK(!open_entries_.size());
902    DelayedCacheCleanup(path_);
903  } else {
904    DeleteCache(path_, false);
905  }
906
907  // Don't call Init() if directed by the unit test: we are simulating a failure
908  // trying to re-enable the cache.
909  if (unit_test_)
910    init_ = true;  // Let the destructor do proper cleanup.
911  else if (SyncInit() == net::OK) {
912    stats_.SetCounter(Stats::FATAL_ERROR, errors);
913    stats_.SetCounter(Stats::DOOM_CACHE, full_dooms);
914    stats_.SetCounter(Stats::DOOM_RECENT, partial_dooms);
915    stats_.SetCounter(Stats::LAST_REPORT, last_report);
916  }
917}
918
919void BackendImpl::PrepareForRestart() {
920  // Reset the mask_ if it was not given by the user.
921  if (!(user_flags_ & kMask))
922    mask_ = 0;
923
924  if (!(user_flags_ & kNewEviction))
925    new_eviction_ = false;
926
927  disabled_ = true;
928  data_->header.crash = 0;
929  index_->Flush();
930  index_ = NULL;
931  data_ = NULL;
932  block_files_.CloseFiles();
933  rankings_.Reset();
934  init_ = false;
935  restarted_ = true;
936}
937
938void BackendImpl::CleanupCache() {
939  Trace("Backend Cleanup");
940  eviction_.Stop();
941  timer_.reset();
942
943  if (init_) {
944    StoreStats();
945    if (data_)
946      data_->header.crash = 0;
947
948    if (user_flags_ & kNoRandom) {
949      // This is a net_unittest, verify that we are not 'leaking' entries.
950      File::WaitForPendingIO(&num_pending_io_);
951      DCHECK(!num_refs_);
952    } else {
953      File::DropPendingIO();
954    }
955  }
956  block_files_.CloseFiles();
957  FlushIndex();
958  index_ = NULL;
959  ptr_factory_.InvalidateWeakPtrs();
960  done_.Signal();
961}
962
963int BackendImpl::NewEntry(Addr address, EntryImpl** entry) {
964  EntriesMap::iterator it = open_entries_.find(address.value());
965  if (it != open_entries_.end()) {
966    // Easy job. This entry is already in memory.
967    EntryImpl* this_entry = it->second;
968    this_entry->AddRef();
969    *entry = this_entry;
970    return 0;
971  }
972
973  STRESS_DCHECK(block_files_.IsValid(address));
974
975  if (!address.SanityCheckForEntry()) {
976    LOG(WARNING) << "Wrong entry address.";
977    STRESS_NOTREACHED();
978    return ERR_INVALID_ADDRESS;
979  }
980
981  scoped_refptr<EntryImpl> cache_entry(
982      new EntryImpl(this, address, read_only_));
983  IncreaseNumRefs();
984  *entry = NULL;
985
986  TimeTicks start = TimeTicks::Now();
987  if (!cache_entry->entry()->Load())
988    return ERR_READ_FAILURE;
989
990  if (IsLoaded()) {
991    CACHE_UMA(AGE_MS, "LoadTime", 0, start);
992  }
993
994  if (!cache_entry->SanityCheck()) {
995    LOG(WARNING) << "Messed up entry found.";
996    STRESS_NOTREACHED();
997    return ERR_INVALID_ENTRY;
998  }
999
1000  STRESS_DCHECK(block_files_.IsValid(
1001                    Addr(cache_entry->entry()->Data()->rankings_node)));
1002
1003  if (!cache_entry->LoadNodeAddress())
1004    return ERR_READ_FAILURE;
1005
1006  if (!rankings_.SanityCheck(cache_entry->rankings(), false)) {
1007    STRESS_NOTREACHED();
1008    cache_entry->SetDirtyFlag(0);
1009    // Don't remove this from the list (it is not linked properly). Instead,
1010    // break the link back to the entry because it is going away, and leave the
1011    // rankings node to be deleted if we find it through a list.
1012    rankings_.SetContents(cache_entry->rankings(), 0);
1013  } else if (!rankings_.DataSanityCheck(cache_entry->rankings(), false)) {
1014    STRESS_NOTREACHED();
1015    cache_entry->SetDirtyFlag(0);
1016    rankings_.SetContents(cache_entry->rankings(), address.value());
1017  }
1018
1019  if (!cache_entry->DataSanityCheck()) {
1020    LOG(WARNING) << "Messed up entry found.";
1021    cache_entry->SetDirtyFlag(0);
1022    cache_entry->FixForDelete();
1023  }
1024
1025  // Prevent overwriting the dirty flag on the destructor.
1026  cache_entry->SetDirtyFlag(GetCurrentEntryId());
1027
1028  if (cache_entry->dirty()) {
1029    Trace("Dirty entry 0x%p 0x%x", reinterpret_cast<void*>(cache_entry.get()),
1030          address.value());
1031  }
1032
1033  open_entries_[address.value()] = cache_entry.get();
1034
1035  cache_entry->BeginLogging(net_log_, false);
1036  cache_entry.swap(entry);
1037  return 0;
1038}
1039
1040// This is the actual implementation for OpenNextEntry and OpenPrevEntry.
1041EntryImpl* BackendImpl::OpenFollowingEntry(bool forward, void** iter) {
1042  if (disabled_)
1043    return NULL;
1044
1045  DCHECK(iter);
1046
1047  const int kListsToSearch = 3;
1048  scoped_refptr<EntryImpl> entries[kListsToSearch];
1049  scoped_ptr<Rankings::Iterator> iterator(
1050      reinterpret_cast<Rankings::Iterator*>(*iter));
1051  *iter = NULL;
1052
1053  if (!iterator.get()) {
1054    iterator.reset(new Rankings::Iterator(&rankings_));
1055    bool ret = false;
1056
1057    // Get an entry from each list.
1058    for (int i = 0; i < kListsToSearch; i++) {
1059      EntryImpl* temp = NULL;
1060      ret |= OpenFollowingEntryFromList(forward, static_cast<Rankings::List>(i),
1061                                        &iterator->nodes[i], &temp);
1062      entries[i].swap(&temp);  // The entry was already addref'd.
1063    }
1064    if (!ret)
1065      return NULL;
1066  } else {
1067    // Get the next entry from the last list, and the actual entries for the
1068    // elements on the other lists.
1069    for (int i = 0; i < kListsToSearch; i++) {
1070      EntryImpl* temp = NULL;
1071      if (iterator->list == i) {
1072          OpenFollowingEntryFromList(forward, iterator->list,
1073                                     &iterator->nodes[i], &temp);
1074      } else {
1075        temp = GetEnumeratedEntry(iterator->nodes[i],
1076                                  static_cast<Rankings::List>(i));
1077      }
1078
1079      entries[i].swap(&temp);  // The entry was already addref'd.
1080    }
1081  }
1082
1083  int newest = -1;
1084  int oldest = -1;
1085  Time access_times[kListsToSearch];
1086  for (int i = 0; i < kListsToSearch; i++) {
1087    if (entries[i].get()) {
1088      access_times[i] = entries[i]->GetLastUsed();
1089      if (newest < 0) {
1090        DCHECK_LT(oldest, 0);
1091        newest = oldest = i;
1092        continue;
1093      }
1094      if (access_times[i] > access_times[newest])
1095        newest = i;
1096      if (access_times[i] < access_times[oldest])
1097        oldest = i;
1098    }
1099  }
1100
1101  if (newest < 0 || oldest < 0)
1102    return NULL;
1103
1104  EntryImpl* next_entry;
1105  if (forward) {
1106    next_entry = entries[newest].get();
1107    iterator->list = static_cast<Rankings::List>(newest);
1108  } else {
1109    next_entry = entries[oldest].get();
1110    iterator->list = static_cast<Rankings::List>(oldest);
1111  }
1112
1113  *iter = iterator.release();
1114  next_entry->AddRef();
1115  return next_entry;
1116}
1117
1118void BackendImpl::AddStorageSize(int32 bytes) {
1119  data_->header.num_bytes += bytes;
1120  DCHECK_GE(data_->header.num_bytes, 0);
1121}
1122
1123void BackendImpl::SubstractStorageSize(int32 bytes) {
1124  data_->header.num_bytes -= bytes;
1125  DCHECK_GE(data_->header.num_bytes, 0);
1126}
1127
1128void BackendImpl::IncreaseNumRefs() {
1129  num_refs_++;
1130  if (max_refs_ < num_refs_)
1131    max_refs_ = num_refs_;
1132}
1133
1134void BackendImpl::DecreaseNumRefs() {
1135  DCHECK(num_refs_);
1136  num_refs_--;
1137
1138  if (!num_refs_ && disabled_)
1139    base::MessageLoop::current()->PostTask(
1140        FROM_HERE, base::Bind(&BackendImpl::RestartCache, GetWeakPtr(), true));
1141}
1142
1143void BackendImpl::IncreaseNumEntries() {
1144  data_->header.num_entries++;
1145  DCHECK_GT(data_->header.num_entries, 0);
1146}
1147
1148void BackendImpl::DecreaseNumEntries() {
1149  data_->header.num_entries--;
1150  if (data_->header.num_entries < 0) {
1151    NOTREACHED();
1152    data_->header.num_entries = 0;
1153  }
1154}
1155
1156int BackendImpl::SyncInit() {
1157#if defined(NET_BUILD_STRESS_CACHE)
1158  // Start evictions right away.
1159  up_ticks_ = kTrimDelay * 2;
1160#endif
1161  DCHECK(!init_);
1162  if (init_)
1163    return net::ERR_FAILED;
1164
1165  bool create_files = false;
1166  if (!InitBackingStore(&create_files)) {
1167    ReportError(ERR_STORAGE_ERROR);
1168    return net::ERR_FAILED;
1169  }
1170
1171  num_refs_ = num_pending_io_ = max_refs_ = 0;
1172  entry_count_ = byte_count_ = 0;
1173
1174  if (!restarted_) {
1175    buffer_bytes_ = 0;
1176    trace_object_ = TraceObject::GetTraceObject();
1177    // Create a recurrent timer of 30 secs.
1178    int timer_delay = unit_test_ ? 1000 : 30000;
1179    timer_.reset(new base::RepeatingTimer<BackendImpl>());
1180    timer_->Start(FROM_HERE, TimeDelta::FromMilliseconds(timer_delay), this,
1181                  &BackendImpl::OnStatsTimer);
1182  }
1183
1184  init_ = true;
1185  Trace("Init");
1186
1187  if (data_->header.experiment != NO_EXPERIMENT &&
1188      cache_type_ != net::DISK_CACHE) {
1189    // No experiment for other caches.
1190    return net::ERR_FAILED;
1191  }
1192
1193  if (!(user_flags_ & kNoRandom)) {
1194    // The unit test controls directly what to test.
1195    new_eviction_ = (cache_type_ == net::DISK_CACHE);
1196  }
1197
1198  if (!CheckIndex()) {
1199    ReportError(ERR_INIT_FAILED);
1200    return net::ERR_FAILED;
1201  }
1202
1203  if (!restarted_ && (create_files || !data_->header.num_entries))
1204    ReportError(ERR_CACHE_CREATED);
1205
1206  if (!(user_flags_ & kNoRandom) && cache_type_ == net::DISK_CACHE &&
1207      !InitExperiment(&data_->header, create_files)) {
1208    return net::ERR_FAILED;
1209  }
1210
1211  // We don't care if the value overflows. The only thing we care about is that
1212  // the id cannot be zero, because that value is used as "not dirty".
1213  // Increasing the value once per second gives us many years before we start
1214  // having collisions.
1215  data_->header.this_id++;
1216  if (!data_->header.this_id)
1217    data_->header.this_id++;
1218
1219  bool previous_crash = (data_->header.crash != 0);
1220  data_->header.crash = 1;
1221
1222  if (!block_files_.Init(create_files))
1223    return net::ERR_FAILED;
1224
1225  // We want to minimize the changes to cache for an AppCache.
1226  if (cache_type() == net::APP_CACHE) {
1227    DCHECK(!new_eviction_);
1228    read_only_ = true;
1229  } else if (cache_type() == net::SHADER_CACHE) {
1230    DCHECK(!new_eviction_);
1231  }
1232
1233  eviction_.Init(this);
1234
1235  // stats_ and rankings_ may end up calling back to us so we better be enabled.
1236  disabled_ = false;
1237  if (!InitStats())
1238    return net::ERR_FAILED;
1239
1240  disabled_ = !rankings_.Init(this, new_eviction_);
1241
1242#if defined(STRESS_CACHE_EXTENDED_VALIDATION)
1243  trace_object_->EnableTracing(false);
1244  int sc = SelfCheck();
1245  if (sc < 0 && sc != ERR_NUM_ENTRIES_MISMATCH)
1246    NOTREACHED();
1247  trace_object_->EnableTracing(true);
1248#endif
1249
1250  if (previous_crash) {
1251    ReportError(ERR_PREVIOUS_CRASH);
1252  } else if (!restarted_) {
1253    ReportError(ERR_NO_ERROR);
1254  }
1255
1256  FlushIndex();
1257
1258  return disabled_ ? net::ERR_FAILED : net::OK;
1259}
1260
1261EntryImpl* BackendImpl::ResurrectEntry(EntryImpl* deleted_entry) {
1262  if (ENTRY_NORMAL == deleted_entry->entry()->Data()->state) {
1263    deleted_entry->Release();
1264    stats_.OnEvent(Stats::CREATE_MISS);
1265    Trace("create entry miss ");
1266    return NULL;
1267  }
1268
1269  // We are attempting to create an entry and found out that the entry was
1270  // previously deleted.
1271
1272  eviction_.OnCreateEntry(deleted_entry);
1273  entry_count_++;
1274
1275  stats_.OnEvent(Stats::RESURRECT_HIT);
1276  Trace("Resurrect entry hit ");
1277  return deleted_entry;
1278}
1279
1280EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) {
1281  if (disabled_ || key.empty())
1282    return NULL;
1283
1284  TimeTicks start = TimeTicks::Now();
1285  Trace("Create hash 0x%x", hash);
1286
1287  scoped_refptr<EntryImpl> parent;
1288  Addr entry_address(data_->table[hash & mask_]);
1289  if (entry_address.is_initialized()) {
1290    // We have an entry already. It could be the one we are looking for, or just
1291    // a hash conflict.
1292    bool error;
1293    EntryImpl* old_entry = MatchEntry(key, hash, false, Addr(), &error);
1294    if (old_entry)
1295      return ResurrectEntry(old_entry);
1296
1297    EntryImpl* parent_entry = MatchEntry(key, hash, true, Addr(), &error);
1298    DCHECK(!error);
1299    if (parent_entry) {
1300      parent.swap(&parent_entry);
1301    } else if (data_->table[hash & mask_]) {
1302      // We should have corrected the problem.
1303      NOTREACHED();
1304      return NULL;
1305    }
1306  }
1307
1308  // The general flow is to allocate disk space and initialize the entry data,
1309  // followed by saving that to disk, then linking the entry though the index
1310  // and finally through the lists. If there is a crash in this process, we may
1311  // end up with:
1312  // a. Used, unreferenced empty blocks on disk (basically just garbage).
1313  // b. Used, unreferenced but meaningful data on disk (more garbage).
1314  // c. A fully formed entry, reachable only through the index.
1315  // d. A fully formed entry, also reachable through the lists, but still dirty.
1316  //
1317  // Anything after (b) can be automatically cleaned up. We may consider saving
1318  // the current operation (as we do while manipulating the lists) so that we
1319  // can detect and cleanup (a) and (b).
1320
1321  int num_blocks = EntryImpl::NumBlocksForEntry(key.size());
1322  if (!block_files_.CreateBlock(BLOCK_256, num_blocks, &entry_address)) {
1323    LOG(ERROR) << "Create entry failed " << key.c_str();
1324    stats_.OnEvent(Stats::CREATE_ERROR);
1325    return NULL;
1326  }
1327
1328  Addr node_address(0);
1329  if (!block_files_.CreateBlock(RANKINGS, 1, &node_address)) {
1330    block_files_.DeleteBlock(entry_address, false);
1331    LOG(ERROR) << "Create entry failed " << key.c_str();
1332    stats_.OnEvent(Stats::CREATE_ERROR);
1333    return NULL;
1334  }
1335
1336  scoped_refptr<EntryImpl> cache_entry(
1337      new EntryImpl(this, entry_address, false));
1338  IncreaseNumRefs();
1339
1340  if (!cache_entry->CreateEntry(node_address, key, hash)) {
1341    block_files_.DeleteBlock(entry_address, false);
1342    block_files_.DeleteBlock(node_address, false);
1343    LOG(ERROR) << "Create entry failed " << key.c_str();
1344    stats_.OnEvent(Stats::CREATE_ERROR);
1345    return NULL;
1346  }
1347
1348  cache_entry->BeginLogging(net_log_, true);
1349
1350  // We are not failing the operation; let's add this to the map.
1351  open_entries_[entry_address.value()] = cache_entry;
1352
1353  // Save the entry.
1354  cache_entry->entry()->Store();
1355  cache_entry->rankings()->Store();
1356  IncreaseNumEntries();
1357  entry_count_++;
1358
1359  // Link this entry through the index.
1360  if (parent.get()) {
1361    parent->SetNextAddress(entry_address);
1362  } else {
1363    data_->table[hash & mask_] = entry_address.value();
1364  }
1365
1366  // Link this entry through the lists.
1367  eviction_.OnCreateEntry(cache_entry);
1368
1369  CACHE_UMA(AGE_MS, "CreateTime", 0, start);
1370  stats_.OnEvent(Stats::CREATE_HIT);
1371  SIMPLE_STATS_COUNTER("disk_cache.miss");
1372  Trace("create entry hit ");
1373  FlushIndex();
1374  cache_entry->AddRef();
1375  return cache_entry.get();
1376}
1377
1378void BackendImpl::LogStats() {
1379  StatsItems stats;
1380  GetStats(&stats);
1381
1382  for (size_t index = 0; index < stats.size(); index++)
1383    VLOG(1) << stats[index].first << ": " << stats[index].second;
1384}
1385
1386void BackendImpl::ReportStats() {
1387  CACHE_UMA(COUNTS, "Entries", 0, data_->header.num_entries);
1388
1389  int current_size = data_->header.num_bytes / (1024 * 1024);
1390  int max_size = max_size_ / (1024 * 1024);
1391  int hit_ratio_as_percentage = stats_.GetHitRatio();
1392
1393  CACHE_UMA(COUNTS_10000, "Size2", 0, current_size);
1394  // For any bin in HitRatioBySize2, the hit ratio of caches of that size is the
1395  // ratio of that bin's total count to the count in the same bin in the Size2
1396  // histogram.
1397  if (base::RandInt(0, 99) < hit_ratio_as_percentage)
1398    CACHE_UMA(COUNTS_10000, "HitRatioBySize2", 0, current_size);
1399  CACHE_UMA(COUNTS_10000, "MaxSize2", 0, max_size);
1400  if (!max_size)
1401    max_size++;
1402  CACHE_UMA(PERCENTAGE, "UsedSpace", 0, current_size * 100 / max_size);
1403
1404  CACHE_UMA(COUNTS_10000, "AverageOpenEntries2", 0,
1405            static_cast<int>(stats_.GetCounter(Stats::OPEN_ENTRIES)));
1406  CACHE_UMA(COUNTS_10000, "MaxOpenEntries2", 0,
1407            static_cast<int>(stats_.GetCounter(Stats::MAX_ENTRIES)));
1408  stats_.SetCounter(Stats::MAX_ENTRIES, 0);
1409
1410  CACHE_UMA(COUNTS_10000, "TotalFatalErrors", 0,
1411            static_cast<int>(stats_.GetCounter(Stats::FATAL_ERROR)));
1412  CACHE_UMA(COUNTS_10000, "TotalDoomCache", 0,
1413            static_cast<int>(stats_.GetCounter(Stats::DOOM_CACHE)));
1414  CACHE_UMA(COUNTS_10000, "TotalDoomRecentEntries", 0,
1415            static_cast<int>(stats_.GetCounter(Stats::DOOM_RECENT)));
1416  stats_.SetCounter(Stats::FATAL_ERROR, 0);
1417  stats_.SetCounter(Stats::DOOM_CACHE, 0);
1418  stats_.SetCounter(Stats::DOOM_RECENT, 0);
1419
1420  int64 total_hours = stats_.GetCounter(Stats::TIMER) / 120;
1421  if (!data_->header.create_time || !data_->header.lru.filled) {
1422    int cause = data_->header.create_time ? 0 : 1;
1423    if (!data_->header.lru.filled)
1424      cause |= 2;
1425    CACHE_UMA(CACHE_ERROR, "ShortReport", 0, cause);
1426    CACHE_UMA(HOURS, "TotalTimeNotFull", 0, static_cast<int>(total_hours));
1427    return;
1428  }
1429
1430  // This is an up to date client that will report FirstEviction() data. After
1431  // that event, start reporting this:
1432
1433  CACHE_UMA(HOURS, "TotalTime", 0, static_cast<int>(total_hours));
1434  // For any bin in HitRatioByTotalTime, the hit ratio of caches of that total
1435  // time is the ratio of that bin's total count to the count in the same bin in
1436  // the TotalTime histogram.
1437  if (base::RandInt(0, 99) < hit_ratio_as_percentage)
1438    CACHE_UMA(HOURS, "HitRatioByTotalTime", 0, implicit_cast<int>(total_hours));
1439
1440  int64 use_hours = stats_.GetCounter(Stats::LAST_REPORT_TIMER) / 120;
1441  stats_.SetCounter(Stats::LAST_REPORT_TIMER, stats_.GetCounter(Stats::TIMER));
1442
1443  // We may see users with no use_hours at this point if this is the first time
1444  // we are running this code.
1445  if (use_hours)
1446    use_hours = total_hours - use_hours;
1447
1448  if (!use_hours || !GetEntryCount() || !data_->header.num_bytes)
1449    return;
1450
1451  CACHE_UMA(HOURS, "UseTime", 0, static_cast<int>(use_hours));
1452  // For any bin in HitRatioByUseTime, the hit ratio of caches of that use time
1453  // is the ratio of that bin's total count to the count in the same bin in the
1454  // UseTime histogram.
1455  if (base::RandInt(0, 99) < hit_ratio_as_percentage)
1456    CACHE_UMA(HOURS, "HitRatioByUseTime", 0, implicit_cast<int>(use_hours));
1457  CACHE_UMA(PERCENTAGE, "HitRatio", 0, hit_ratio_as_percentage);
1458
1459  int64 trim_rate = stats_.GetCounter(Stats::TRIM_ENTRY) / use_hours;
1460  CACHE_UMA(COUNTS, "TrimRate", 0, static_cast<int>(trim_rate));
1461
1462  int avg_size = data_->header.num_bytes / GetEntryCount();
1463  CACHE_UMA(COUNTS, "EntrySize", 0, avg_size);
1464  CACHE_UMA(COUNTS, "EntriesFull", 0, data_->header.num_entries);
1465
1466  CACHE_UMA(PERCENTAGE, "IndexLoad", 0,
1467            data_->header.num_entries * 100 / (mask_ + 1));
1468
1469  int large_entries_bytes = stats_.GetLargeEntriesSize();
1470  int large_ratio = large_entries_bytes * 100 / data_->header.num_bytes;
1471  CACHE_UMA(PERCENTAGE, "LargeEntriesRatio", 0, large_ratio);
1472
1473  if (new_eviction_) {
1474    CACHE_UMA(PERCENTAGE, "ResurrectRatio", 0, stats_.GetResurrectRatio());
1475    CACHE_UMA(PERCENTAGE, "NoUseRatio", 0,
1476              data_->header.lru.sizes[0] * 100 / data_->header.num_entries);
1477    CACHE_UMA(PERCENTAGE, "LowUseRatio", 0,
1478              data_->header.lru.sizes[1] * 100 / data_->header.num_entries);
1479    CACHE_UMA(PERCENTAGE, "HighUseRatio", 0,
1480              data_->header.lru.sizes[2] * 100 / data_->header.num_entries);
1481    CACHE_UMA(PERCENTAGE, "DeletedRatio", 0,
1482              data_->header.lru.sizes[4] * 100 / data_->header.num_entries);
1483  }
1484
1485  stats_.ResetRatios();
1486  stats_.SetCounter(Stats::TRIM_ENTRY, 0);
1487
1488  if (cache_type_ == net::DISK_CACHE)
1489    block_files_.ReportStats();
1490}
1491
1492void BackendImpl::ReportError(int error) {
1493  STRESS_DCHECK(!error || error == ERR_PREVIOUS_CRASH ||
1494                error == ERR_CACHE_CREATED);
1495
1496  // We transmit positive numbers, instead of direct error codes.
1497  DCHECK_LE(error, 0);
1498  CACHE_UMA(CACHE_ERROR, "Error", 0, error * -1);
1499}
1500
1501bool BackendImpl::CheckIndex() {
1502  DCHECK(data_);
1503
1504  size_t current_size = index_->GetLength();
1505  if (current_size < sizeof(Index)) {
1506    LOG(ERROR) << "Corrupt Index file";
1507    return false;
1508  }
1509
1510  if (new_eviction_) {
1511    // We support versions 2.0 and 2.1, upgrading 2.0 to 2.1.
1512    if (kIndexMagic != data_->header.magic ||
1513        kCurrentVersion >> 16 != data_->header.version >> 16) {
1514      LOG(ERROR) << "Invalid file version or magic";
1515      return false;
1516    }
1517    if (kCurrentVersion == data_->header.version) {
1518      // We need file version 2.1 for the new eviction algorithm.
1519      UpgradeTo2_1();
1520    }
1521  } else {
1522    if (kIndexMagic != data_->header.magic ||
1523        kCurrentVersion != data_->header.version) {
1524      LOG(ERROR) << "Invalid file version or magic";
1525      return false;
1526    }
1527  }
1528
1529  if (!data_->header.table_len) {
1530    LOG(ERROR) << "Invalid table size";
1531    return false;
1532  }
1533
1534  if (current_size < GetIndexSize(data_->header.table_len) ||
1535      data_->header.table_len & (kBaseTableLen - 1)) {
1536    LOG(ERROR) << "Corrupt Index file";
1537    return false;
1538  }
1539
1540  AdjustMaxCacheSize(data_->header.table_len);
1541
1542#if !defined(NET_BUILD_STRESS_CACHE)
1543  if (data_->header.num_bytes < 0 ||
1544      (max_size_ < kint32max - kDefaultCacheSize &&
1545       data_->header.num_bytes > max_size_ + kDefaultCacheSize)) {
1546    LOG(ERROR) << "Invalid cache (current) size";
1547    return false;
1548  }
1549#endif
1550
1551  if (data_->header.num_entries < 0) {
1552    LOG(ERROR) << "Invalid number of entries";
1553    return false;
1554  }
1555
1556  if (!mask_)
1557    mask_ = data_->header.table_len - 1;
1558
1559  // Load the table into memory with a single read.
1560  scoped_ptr<char[]> buf(new char[current_size]);
1561  return index_->Read(buf.get(), current_size, 0);
1562}
1563
1564int BackendImpl::CheckAllEntries() {
1565  int num_dirty = 0;
1566  int num_entries = 0;
1567  DCHECK(mask_ < kuint32max);
1568  for (unsigned int i = 0; i <= mask_; i++) {
1569    Addr address(data_->table[i]);
1570    if (!address.is_initialized())
1571      continue;
1572    for (;;) {
1573      EntryImpl* tmp;
1574      int ret = NewEntry(address, &tmp);
1575      if (ret) {
1576        STRESS_NOTREACHED();
1577        return ret;
1578      }
1579      scoped_refptr<EntryImpl> cache_entry;
1580      cache_entry.swap(&tmp);
1581
1582      if (cache_entry->dirty())
1583        num_dirty++;
1584      else if (CheckEntry(cache_entry.get()))
1585        num_entries++;
1586      else
1587        return ERR_INVALID_ENTRY;
1588
1589      DCHECK_EQ(i, cache_entry->entry()->Data()->hash & mask_);
1590      address.set_value(cache_entry->GetNextAddress());
1591      if (!address.is_initialized())
1592        break;
1593    }
1594  }
1595
1596  Trace("CheckAllEntries End");
1597  if (num_entries + num_dirty != data_->header.num_entries) {
1598    LOG(ERROR) << "Number of entries " << num_entries << " " << num_dirty <<
1599                  " " << data_->header.num_entries;
1600    DCHECK_LT(num_entries, data_->header.num_entries);
1601    return ERR_NUM_ENTRIES_MISMATCH;
1602  }
1603
1604  return num_dirty;
1605}
1606
1607bool BackendImpl::CheckEntry(EntryImpl* cache_entry) {
1608  bool ok = block_files_.IsValid(cache_entry->entry()->address());
1609  ok = ok && block_files_.IsValid(cache_entry->rankings()->address());
1610  EntryStore* data = cache_entry->entry()->Data();
1611  for (size_t i = 0; i < arraysize(data->data_addr); i++) {
1612    if (data->data_addr[i]) {
1613      Addr address(data->data_addr[i]);
1614      if (address.is_block_file())
1615        ok = ok && block_files_.IsValid(address);
1616    }
1617  }
1618
1619  return ok && cache_entry->rankings()->VerifyHash();
1620}
1621
1622int BackendImpl::MaxBuffersSize() {
1623  static int64 total_memory = base::SysInfo::AmountOfPhysicalMemory();
1624  static bool done = false;
1625
1626  if (!done) {
1627    const int kMaxBuffersSize = 30 * 1024 * 1024;
1628
1629    // We want to use up to 2% of the computer's memory.
1630    total_memory = total_memory * 2 / 100;
1631    if (total_memory > kMaxBuffersSize || total_memory <= 0)
1632      total_memory = kMaxBuffersSize;
1633
1634    done = true;
1635  }
1636
1637  return static_cast<int>(total_memory);
1638}
1639
1640}  // namespace disk_cache
1641