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