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