net/disk_cache/blockfile/backend_impl_v3.cc

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