net/disk_cache/blockfile/backend_impl.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.h"
   6
   7 #include "base/bind.h"
   8 #include "base/bind_helpers.h"
   9 #include "base/files/file.h"
  10 #include "base/files/file_path.h"
  11 #include "base/files/file_util.h"
  12 #include "base/hash.h"
  13 #include "base/message_loop/message_loop.h"
  14 #include "base/metrics/field_trial.h"
  15 #include "base/metrics/histogram.h"
  16 #include "base/rand_util.h"
  17 #include "base/single_thread_task_runner.h"
  18 #include "base/strings/string_util.h"
  19 #include "base/strings/stringprintf.h"
  20 #include "base/sys_info.h"
  21 #include "base/threading/thread_restrictions.h"
  22 #include "base/time/time.h"
  23 #include "base/timer/timer.h"
  24 #include "net/base/net_errors.h"
  25 #include "net/disk_cache/blockfile/disk_format.h"
  26 #include "net/disk_cache/blockfile/entry_impl.h"
  27 #include "net/disk_cache/blockfile/errors.h"
  28 #include "net/disk_cache/blockfile/experiments.h"
  29 #include "net/disk_cache/blockfile/file.h"
  30 #include "net/disk_cache/blockfile/histogram_macros.h"
  31 #include "net/disk_cache/blockfile/webfonts_histogram.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 const char kIndexName[] = "index";
  44
  45 // Seems like ~240 MB correspond to less than 50k entries for 99% of the people.
  46 // Note that the actual target is to keep the index table load factor under 55%
  47 // for most users.
  48 const int k64kEntriesStore = 240 * 1000 * 1000;
  49 const int kBaseTableLen = 64 * 1024;
  50
  51 // Avoid trimming the cache for the first 5 minutes (10 timer ticks).
  52 const int kTrimDelay = 10;
  53
  54 int DesiredIndexTableLen(int32 storage_size) {
  55   if (storage_size <= k64kEntriesStore)
  56     return kBaseTableLen;
  57   if (storage_size <= k64kEntriesStore * 2)
  58     return kBaseTableLen * 2;
  59   if (storage_size <= k64kEntriesStore * 4)
  60     return kBaseTableLen * 4;
  61   if (storage_size <= k64kEntriesStore * 8)
  62     return kBaseTableLen * 8;
  63
  64   // The biggest storage_size for int32 requires a 4 MB table.
  65   return kBaseTableLen * 16;
  66 }
  67
  68 int MaxStorageSizeForTable(int table_len) {
  69   return table_len * (k64kEntriesStore / kBaseTableLen);
  70 }
  71
  72 size_t GetIndexSize(int table_len) {
  73   size_t table_size = sizeof(disk_cache::CacheAddr) * table_len;
  74   return sizeof(disk_cache::IndexHeader) + table_size;
  75 }
  76
  77 // ------------------------------------------------------------------------
  78
  79 // Sets group for the current experiment. Returns false if the files should be
  80 // discarded.
  81 bool InitExperiment(disk_cache::IndexHeader* header, bool cache_created) {
  82   if (header->experiment == disk_cache::EXPERIMENT_OLD_FILE1 ||
  83       header->experiment == disk_cache::EXPERIMENT_OLD_FILE2) {
  84     // Discard current cache.
  85     return false;
  86   }
  87
  88   if (base::FieldTrialList::FindFullName("SimpleCacheTrial") ==
  89           "ExperimentControl") {
  90     if (cache_created) {
  91       header->experiment = disk_cache::EXPERIMENT_SIMPLE_CONTROL;
  92       return true;
  93     }
  94     return header->experiment == disk_cache::EXPERIMENT_SIMPLE_CONTROL;
  95   }
  96
  97   header->experiment = disk_cache::NO_EXPERIMENT;
  98   return true;
  99 }
 100
 101 // A callback to perform final cleanup on the background thread.
 102 void FinalCleanupCallback(disk_cache::BackendImpl* backend) {
 103   backend->CleanupCache();
 104 }
 105
 106 }  // namespace
 107
 108 // ------------------------------------------------------------------------
 109
 110 namespace disk_cache {
 111
 112 BackendImpl::BackendImpl(
 113     const base::FilePath& path,
 114     const scoped_refptr<base::SingleThreadTaskRunner>& cache_thread,
 115     net::NetLog* net_log)
 116     : background_queue_(this, cache_thread),
 117       path_(path),
 118       block_files_(path),
 119       mask_(0),
 120       max_size_(0),
 121       up_ticks_(0),
 122       cache_type_(net::DISK_CACHE),
 123       uma_report_(0),
 124       user_flags_(0),
 125       init_(false),
 126       restarted_(false),
 127       unit_test_(false),
 128       read_only_(false),
 129       disabled_(false),
 130       new_eviction_(false),
 131       first_timer_(true),
 132       user_load_(false),
 133       net_log_(net_log),
 134       done_(true, false),
 135       ptr_factory_(this) {
 136 }
 137
 138 BackendImpl::BackendImpl(
 139     const base::FilePath& path,
 140     uint32 mask,
 141     const scoped_refptr<base::SingleThreadTaskRunner>& cache_thread,
 142     net::NetLog* net_log)
 143     : background_queue_(this, cache_thread),
 144       path_(path),
 145       block_files_(path),
 146       mask_(mask),
 147       max_size_(0),
 148       up_ticks_(0),
 149       cache_type_(net::DISK_CACHE),
 150       uma_report_(0),
 151       user_flags_(kMask),
 152       init_(false),
 153       restarted_(false),
 154       unit_test_(false),
 155       read_only_(false),
 156       disabled_(false),
 157       new_eviction_(false),
 158       first_timer_(true),
 159       user_load_(false),
 160       net_log_(net_log),
 161       done_(true, false),
 162       ptr_factory_(this) {
 163 }
 164
 165 BackendImpl::~BackendImpl() {
 166   if (user_flags_ & kNoRandom) {
 167     // This is a unit test, so we want to be strict about not leaking entries
 168     // and completing all the work.
 169     background_queue_.WaitForPendingIO();
 170   } else {
 171     // This is most likely not a test, so we want to do as little work as
 172     // possible at this time, at the price of leaving dirty entries behind.
 173     background_queue_.DropPendingIO();
 174   }
 175
 176   if (background_queue_.BackgroundIsCurrentThread()) {
 177     // Unit tests may use the same thread for everything.
 178     CleanupCache();
 179   } else {
 180     background_queue_.background_thread()->PostTask(
 181         FROM_HERE, base::Bind(&FinalCleanupCallback, base::Unretained(this)));
 182     // http://crbug.com/74623
 183     base::ThreadRestrictions::ScopedAllowWait allow_wait;
 184     done_.Wait();
 185   }
 186 }
 187
 188 int BackendImpl::Init(const CompletionCallback& callback) {
 189   background_queue_.Init(callback);
 190   return net::ERR_IO_PENDING;
 191 }
 192
 193 int BackendImpl::SyncInit() {
 194 #if defined(NET_BUILD_STRESS_CACHE)
 195   // Start evictions right away.
 196   up_ticks_ = kTrimDelay * 2;
 197 #endif
 198   DCHECK(!init_);
 199   if (init_)
 200     return net::ERR_FAILED;
 201
 202   bool create_files = false;
 203   if (!InitBackingStore(&create_files)) {
 204     ReportError(ERR_STORAGE_ERROR);
 205     return net::ERR_FAILED;
 206   }
 207
 208   num_refs_ = num_pending_io_ = max_refs_ = 0;
 209   entry_count_ = byte_count_ = 0;
 210
 211   bool should_create_timer = false;
 212   if (!restarted_) {
 213     buffer_bytes_ = 0;
 214     trace_object_ = TraceObject::GetTraceObject();
 215     should_create_timer = true;
 216   }
 217
 218   init_ = true;
 219   Trace("Init");
 220
 221   if (data_->header.experiment != NO_EXPERIMENT &&
 222       cache_type_ != net::DISK_CACHE) {
 223     // No experiment for other caches.
 224     return net::ERR_FAILED;
 225   }
 226
 227   if (!(user_flags_ & kNoRandom)) {
 228     // The unit test controls directly what to test.
 229     new_eviction_ = (cache_type_ == net::DISK_CACHE);
 230   }
 231
 232   if (!CheckIndex()) {
 233     ReportError(ERR_INIT_FAILED);
 234     return net::ERR_FAILED;
 235   }
 236
 237   if (!restarted_ && (create_files || !data_->header.num_entries))
 238     ReportError(ERR_CACHE_CREATED);
 239
 240   if (!(user_flags_ & kNoRandom) && cache_type_ == net::DISK_CACHE &&
 241       !InitExperiment(&data_->header, create_files)) {
 242     return net::ERR_FAILED;
 243   }
 244
 245   // We don't care if the value overflows. The only thing we care about is that
 246   // the id cannot be zero, because that value is used as "not dirty".
 247   // Increasing the value once per second gives us many years before we start
 248   // having collisions.
 249   data_->header.this_id++;
 250   if (!data_->header.this_id)
 251     data_->header.this_id++;
 252
 253   bool previous_crash = (data_->header.crash != 0);
 254   data_->header.crash = 1;
 255
 256   if (!block_files_.Init(create_files))
 257     return net::ERR_FAILED;
 258
 259   // We want to minimize the changes to cache for an AppCache.
 260   if (cache_type() == net::APP_CACHE) {
 261     DCHECK(!new_eviction_);
 262     read_only_ = true;
 263   } else if (cache_type() == net::SHADER_CACHE) {
 264     DCHECK(!new_eviction_);
 265   }
 266
 267   eviction_.Init(this);
 268
 269   // stats_ and rankings_ may end up calling back to us so we better be enabled.
 270   disabled_ = false;
 271   if (!InitStats())
 272     return net::ERR_FAILED;
 273
 274   disabled_ = !rankings_.Init(this, new_eviction_);
 275
 276 #if defined(STRESS_CACHE_EXTENDED_VALIDATION)
 277   trace_object_->EnableTracing(false);
 278   int sc = SelfCheck();
 279   if (sc < 0 && sc != ERR_NUM_ENTRIES_MISMATCH)
 280     NOTREACHED();
 281   trace_object_->EnableTracing(true);
 282 #endif
 283
 284   if (previous_crash) {
 285     ReportError(ERR_PREVIOUS_CRASH);
 286   } else if (!restarted_) {
 287     ReportError(ERR_NO_ERROR);
 288   }
 289
 290   FlushIndex();
 291
 292   if (!disabled_ && should_create_timer) {
 293     // Create a recurrent timer of 30 secs.
 294     int timer_delay = unit_test_ ? 1000 : 30000;
 295     timer_.reset(new base::RepeatingTimer<BackendImpl>());
 296     timer_->Start(FROM_HERE, TimeDelta::FromMilliseconds(timer_delay), this,
 297                   &BackendImpl::OnStatsTimer);
 298   }
 299
 300   return disabled_ ? net::ERR_FAILED : net::OK;
 301 }
 302
 303 void BackendImpl::CleanupCache() {
 304   Trace("Backend Cleanup");
 305   eviction_.Stop();
 306   timer_.reset();
 307
 308   if (init_) {
 309     StoreStats();
 310     if (data_)
 311       data_->header.crash = 0;
 312
 313     if (user_flags_ & kNoRandom) {
 314       // This is a net_unittest, verify that we are not 'leaking' entries.
 315       File::WaitForPendingIO(&num_pending_io_);
 316       DCHECK(!num_refs_);
 317     } else {
 318       File::DropPendingIO();
 319     }
 320   }
 321   block_files_.CloseFiles();
 322   FlushIndex();
 323   index_ = NULL;
 324   ptr_factory_.InvalidateWeakPtrs();
 325   done_.Signal();
 326 }
 327
 328 // ------------------------------------------------------------------------
 329
 330 int BackendImpl::SyncOpenEntry(const std::string& key, Entry** entry) {
 331   DCHECK(entry);
 332   *entry = OpenEntryImpl(key);
 333   return (*entry) ? net::OK : net::ERR_FAILED;
 334 }
 335
 336 int BackendImpl::SyncCreateEntry(const std::string& key, Entry** entry) {
 337   DCHECK(entry);
 338   *entry = CreateEntryImpl(key);
 339   return (*entry) ? net::OK : net::ERR_FAILED;
 340 }
 341
 342 int BackendImpl::SyncDoomEntry(const std::string& key) {
 343   if (disabled_)
 344     return net::ERR_FAILED;
 345
 346   EntryImpl* entry = OpenEntryImpl(key);
 347   if (!entry)
 348     return net::ERR_FAILED;
 349
 350   entry->DoomImpl();
 351   entry->Release();
 352   return net::OK;
 353 }
 354
 355 int BackendImpl::SyncDoomAllEntries() {
 356   if (disabled_)
 357     return net::ERR_FAILED;
 358
 359   // This is not really an error, but it is an interesting condition.
 360   ReportError(ERR_CACHE_DOOMED);
 361   stats_.OnEvent(Stats::DOOM_CACHE);
 362   if (!num_refs_) {
 363     RestartCache(false);
 364     return disabled_ ? net::ERR_FAILED : net::OK;
 365   } else {
 366     if (disabled_)
 367       return net::ERR_FAILED;
 368
 369     eviction_.TrimCache(true);
 370     return net::OK;
 371   }
 372 }
 373
 374 int BackendImpl::SyncDoomEntriesBetween(const base::Time initial_time,
 375                                         const base::Time end_time) {
 376   DCHECK_NE(net::APP_CACHE, cache_type_);
 377   if (end_time.is_null())
 378     return SyncDoomEntriesSince(initial_time);
 379
 380   DCHECK(end_time >= initial_time);
 381
 382   if (disabled_)
 383     return net::ERR_FAILED;
 384
 385   EntryImpl* node;
 386   scoped_ptr<Rankings::Iterator> iterator(new Rankings::Iterator());
 387   EntryImpl* next = OpenNextEntryImpl(iterator.get());
 388   if (!next)
 389     return net::OK;
 390
 391   while (next) {
 392     node = next;
 393     next = OpenNextEntryImpl(iterator.get());
 394
 395     if (node->GetLastUsed() >= initial_time &&
 396         node->GetLastUsed() < end_time) {
 397       node->DoomImpl();
 398     } else if (node->GetLastUsed() < initial_time) {
 399       if (next)
 400         next->Release();
 401       next = NULL;
 402       SyncEndEnumeration(iterator.Pass());
 403     }
 404
 405     node->Release();
 406   }
 407
 408   return net::OK;
 409 }
 410
 411 // We use OpenNextEntryImpl to retrieve elements from the cache, until we get
 412 // entries that are too old.
 413 int BackendImpl::SyncDoomEntriesSince(const base::Time initial_time) {
 414   DCHECK_NE(net::APP_CACHE, cache_type_);
 415   if (disabled_)
 416     return net::ERR_FAILED;
 417
 418   stats_.OnEvent(Stats::DOOM_RECENT);
 419   for (;;) {
 420     scoped_ptr<Rankings::Iterator> iterator(new Rankings::Iterator());
 421     EntryImpl* entry = OpenNextEntryImpl(iterator.get());
 422     if (!entry)
 423       return net::OK;
 424
 425     if (initial_time > entry->GetLastUsed()) {
 426       entry->Release();
 427       SyncEndEnumeration(iterator.Pass());
 428       return net::OK;
 429     }
 430
 431     entry->DoomImpl();
 432     entry->Release();
 433     SyncEndEnumeration(iterator.Pass());  // The doom invalidated the iterator.
 434   }
 435 }
 436
 437 int BackendImpl::SyncOpenNextEntry(Rankings::Iterator* iterator,
 438                                    Entry** next_entry) {
 439   *next_entry = OpenNextEntryImpl(iterator);
 440   return (*next_entry) ? net::OK : net::ERR_FAILED;
 441 }
 442
 443 void BackendImpl::SyncEndEnumeration(scoped_ptr<Rankings::Iterator> iterator) {
 444   iterator->Reset();
 445 }
 446
 447 void BackendImpl::SyncOnExternalCacheHit(const std::string& key) {
 448   if (disabled_)
 449     return;
 450
 451   uint32 hash = base::Hash(key);
 452   bool error;
 453   EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
 454   if (cache_entry) {
 455     if (ENTRY_NORMAL == cache_entry->entry()->Data()->state) {
 456       UpdateRank(cache_entry, cache_type() == net::SHADER_CACHE);
 457     }
 458     cache_entry->Release();
 459   }
 460 }
 461
 462 EntryImpl* BackendImpl::OpenEntryImpl(const std::string& key) {
 463   if (disabled_)
 464     return NULL;
 465
 466   TimeTicks start = TimeTicks::Now();
 467   uint32 hash = base::Hash(key);
 468   Trace("Open hash 0x%x", hash);
 469
 470   bool error;
 471   EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
 472   if (cache_entry && ENTRY_NORMAL != cache_entry->entry()->Data()->state) {
 473     // The entry was already evicted.
 474     cache_entry->Release();
 475     cache_entry = NULL;
 476     web_fonts_histogram::RecordEvictedEntry(key);
 477   } else if (!cache_entry) {
 478     web_fonts_histogram::RecordCacheMiss(key);
 479   }
 480
 481   int current_size = data_->header.num_bytes / (1024 * 1024);
 482   int64 total_hours = stats_.GetCounter(Stats::TIMER) / 120;
 483   int64 no_use_hours = stats_.GetCounter(Stats::LAST_REPORT_TIMER) / 120;
 484   int64 use_hours = total_hours - no_use_hours;
 485
 486   if (!cache_entry) {
 487     CACHE_UMA(AGE_MS, "OpenTime.Miss", 0, start);
 488     CACHE_UMA(COUNTS_10000, "AllOpenBySize.Miss", 0, current_size);
 489     CACHE_UMA(HOURS, "AllOpenByTotalHours.Miss", 0,
 490               static_cast<base::HistogramBase::Sample>(total_hours));
 491     CACHE_UMA(HOURS, "AllOpenByUseHours.Miss", 0,
 492               static_cast<base::HistogramBase::Sample>(use_hours));
 493     stats_.OnEvent(Stats::OPEN_MISS);
 494     return NULL;
 495   }
 496
 497   eviction_.OnOpenEntry(cache_entry);
 498   entry_count_++;
 499
 500   Trace("Open hash 0x%x end: 0x%x", hash,
 501         cache_entry->entry()->address().value());
 502   CACHE_UMA(AGE_MS, "OpenTime", 0, start);
 503   CACHE_UMA(COUNTS_10000, "AllOpenBySize.Hit", 0, current_size);
 504   CACHE_UMA(HOURS, "AllOpenByTotalHours.Hit", 0,
 505             static_cast<base::HistogramBase::Sample>(total_hours));
 506   CACHE_UMA(HOURS, "AllOpenByUseHours.Hit", 0,
 507             static_cast<base::HistogramBase::Sample>(use_hours));
 508   stats_.OnEvent(Stats::OPEN_HIT);
 509   web_fonts_histogram::RecordCacheHit(cache_entry);
 510   return cache_entry;
 511 }
 512
 513 EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) {
 514   if (disabled_ || key.empty())
 515     return NULL;
 516
 517   TimeTicks start = TimeTicks::Now();
 518   uint32 hash = base::Hash(key);
 519   Trace("Create hash 0x%x", hash);
 520
 521   scoped_refptr<EntryImpl> parent;
 522   Addr entry_address(data_->table[hash & mask_]);
 523   if (entry_address.is_initialized()) {
 524     // We have an entry already. It could be the one we are looking for, or just
 525     // a hash conflict.
 526     bool error;
 527     EntryImpl* old_entry = MatchEntry(key, hash, false, Addr(), &error);
 528     if (old_entry)
 529       return ResurrectEntry(old_entry);
 530
 531     EntryImpl* parent_entry = MatchEntry(key, hash, true, Addr(), &error);
 532     DCHECK(!error);
 533     if (parent_entry) {
 534       parent.swap(&parent_entry);
 535     } else if (data_->table[hash & mask_]) {
 536       // We should have corrected the problem.
 537       NOTREACHED();
 538       return NULL;
 539     }
 540   }
 541
 542   // The general flow is to allocate disk space and initialize the entry data,
 543   // followed by saving that to disk, then linking the entry though the index
 544   // and finally through the lists. If there is a crash in this process, we may
 545   // end up with:
 546   // a. Used, unreferenced empty blocks on disk (basically just garbage).
 547   // b. Used, unreferenced but meaningful data on disk (more garbage).
 548   // c. A fully formed entry, reachable only through the index.
 549   // d. A fully formed entry, also reachable through the lists, but still dirty.
 550   //
 551   // Anything after (b) can be automatically cleaned up. We may consider saving
 552   // the current operation (as we do while manipulating the lists) so that we
 553   // can detect and cleanup (a) and (b).
 554
 555   int num_blocks = EntryImpl::NumBlocksForEntry(key.size());
 556   if (!block_files_.CreateBlock(BLOCK_256, num_blocks, &entry_address)) {
 557     LOG(ERROR) << "Create entry failed " << key.c_str();
 558     stats_.OnEvent(Stats::CREATE_ERROR);
 559     return NULL;
 560   }
 561
 562   Addr node_address(0);
 563   if (!block_files_.CreateBlock(RANKINGS, 1, &node_address)) {
 564     block_files_.DeleteBlock(entry_address, false);
 565     LOG(ERROR) << "Create entry failed " << key.c_str();
 566     stats_.OnEvent(Stats::CREATE_ERROR);
 567     return NULL;
 568   }
 569
 570   scoped_refptr<EntryImpl> cache_entry(
 571       new EntryImpl(this, entry_address, false));
 572   IncreaseNumRefs();
 573
 574   if (!cache_entry->CreateEntry(node_address, key, hash)) {
 575     block_files_.DeleteBlock(entry_address, false);
 576     block_files_.DeleteBlock(node_address, false);
 577     LOG(ERROR) << "Create entry failed " << key.c_str();
 578     stats_.OnEvent(Stats::CREATE_ERROR);
 579     return NULL;
 580   }
 581
 582   cache_entry->BeginLogging(net_log_, true);
 583
 584   // We are not failing the operation; let's add this to the map.
 585   open_entries_[entry_address.value()] = cache_entry.get();
 586
 587   // Save the entry.
 588   cache_entry->entry()->Store();
 589   cache_entry->rankings()->Store();
 590   IncreaseNumEntries();
 591   entry_count_++;
 592
 593   // Link this entry through the index.
 594   if (parent.get()) {
 595     parent->SetNextAddress(entry_address);
 596   } else {
 597     data_->table[hash & mask_] = entry_address.value();
 598   }
 599
 600   // Link this entry through the lists.
 601   eviction_.OnCreateEntry(cache_entry.get());
 602
 603   CACHE_UMA(AGE_MS, "CreateTime", 0, start);
 604   stats_.OnEvent(Stats::CREATE_HIT);
 605   Trace("create entry hit ");
 606   FlushIndex();
 607   cache_entry->AddRef();
 608   return cache_entry.get();
 609 }
 610
 611 EntryImpl* BackendImpl::OpenNextEntryImpl(Rankings::Iterator* iterator) {
 612   if (disabled_)
 613     return NULL;
 614
 615   const int kListsToSearch = 3;
 616   scoped_refptr<EntryImpl> entries[kListsToSearch];
 617   if (!iterator->my_rankings) {
 618     iterator->my_rankings = &rankings_;
 619     bool ret = false;
 620
 621     // Get an entry from each list.
 622     for (int i = 0; i < kListsToSearch; i++) {
 623       EntryImpl* temp = NULL;
 624       ret |= OpenFollowingEntryFromList(static_cast<Rankings::List>(i),
 625                                         &iterator->nodes[i], &temp);
 626       entries[i].swap(&temp);  // The entry was already addref'd.
 627     }
 628     if (!ret) {
 629       iterator->Reset();
 630       return NULL;
 631     }
 632   } else {
 633     // Get the next entry from the last list, and the actual entries for the
 634     // elements on the other lists.
 635     for (int i = 0; i < kListsToSearch; i++) {
 636       EntryImpl* temp = NULL;
 637       if (iterator->list == i) {
 638           OpenFollowingEntryFromList(
 639               iterator->list, &iterator->nodes[i], &temp);
 640       } else {
 641         temp = GetEnumeratedEntry(iterator->nodes[i],
 642                                   static_cast<Rankings::List>(i));
 643       }
 644
 645       entries[i].swap(&temp);  // The entry was already addref'd.
 646     }
 647   }
 648
 649   int newest = -1;
 650   int oldest = -1;
 651   Time access_times[kListsToSearch];
 652   for (int i = 0; i < kListsToSearch; i++) {
 653     if (entries[i].get()) {
 654       access_times[i] = entries[i]->GetLastUsed();
 655       if (newest < 0) {
 656         DCHECK_LT(oldest, 0);
 657         newest = oldest = i;
 658         continue;
 659       }
 660       if (access_times[i] > access_times[newest])
 661         newest = i;
 662       if (access_times[i] < access_times[oldest])
 663         oldest = i;
 664     }
 665   }
 666
 667   if (newest < 0 || oldest < 0) {
 668     iterator->Reset();
 669     return NULL;
 670   }
 671
 672   EntryImpl* next_entry;
 673   next_entry = entries[newest].get();
 674   iterator->list = static_cast<Rankings::List>(newest);
 675   next_entry->AddRef();
 676   return next_entry;
 677 }
 678
 679 bool BackendImpl::SetMaxSize(int max_bytes) {
 680   static_assert(sizeof(max_bytes) == sizeof(max_size_),
 681                 "unsupported int model");
 682   if (max_bytes < 0)
 683     return false;
 684
 685   // Zero size means use the default.
 686   if (!max_bytes)
 687     return true;
 688
 689   // Avoid a DCHECK later on.
 690   if (max_bytes >= kint32max - kint32max / 10)
 691     max_bytes = kint32max - kint32max / 10 - 1;
 692
 693   user_flags_ |= kMaxSize;
 694   max_size_ = max_bytes;
 695   return true;
 696 }
 697
 698 void BackendImpl::SetType(net::CacheType type) {
 699   DCHECK_NE(net::MEMORY_CACHE, type);
 700   cache_type_ = type;
 701 }
 702
 703 base::FilePath BackendImpl::GetFileName(Addr address) const {
 704   if (!address.is_separate_file() || !address.is_initialized()) {
 705     NOTREACHED();
 706     return base::FilePath();
 707   }
 708
 709   std::string tmp = base::StringPrintf("f_%06x", address.FileNumber());
 710   return path_.AppendASCII(tmp);
 711 }
 712
 713 MappedFile* BackendImpl::File(Addr address) {
 714   if (disabled_)
 715     return NULL;
 716   return block_files_.GetFile(address);
 717 }
 718
 719 base::WeakPtr<InFlightBackendIO> BackendImpl::GetBackgroundQueue() {
 720   return background_queue_.GetWeakPtr();
 721 }
 722
 723 bool BackendImpl::CreateExternalFile(Addr* address) {
 724   int file_number = data_->header.last_file + 1;
 725   Addr file_address(0);
 726   bool success = false;
 727   for (int i = 0; i < 0x0fffffff; i++, file_number++) {
 728     if (!file_address.SetFileNumber(file_number)) {
 729       file_number = 1;
 730       continue;
 731     }
 732     base::FilePath name = GetFileName(file_address);
 733     int flags = base::File::FLAG_READ | base::File::FLAG_WRITE |
 734                 base::File::FLAG_CREATE | base::File::FLAG_EXCLUSIVE_WRITE;
 735     base::File file(name, flags);
 736     if (!file.IsValid()) {
 737       base::File::Error error = file.error_details();
 738       if (error != base::File::FILE_ERROR_EXISTS) {
 739         LOG(ERROR) << "Unable to create file: " << error;
 740         return false;
 741       }
 742       continue;
 743     }
 744
 745     success = true;
 746     break;
 747   }
 748
 749   DCHECK(success);
 750   if (!success)
 751     return false;
 752
 753   data_->header.last_file = file_number;
 754   address->set_value(file_address.value());
 755   return true;
 756 }
 757
 758 bool BackendImpl::CreateBlock(FileType block_type, int block_count,
 759                              Addr* block_address) {
 760   return block_files_.CreateBlock(block_type, block_count, block_address);
 761 }
 762
 763 void BackendImpl::DeleteBlock(Addr block_address, bool deep) {
 764   block_files_.DeleteBlock(block_address, deep);
 765 }
 766
 767 LruData* BackendImpl::GetLruData() {
 768   return &data_->header.lru;
 769 }
 770
 771 void BackendImpl::UpdateRank(EntryImpl* entry, bool modified) {
 772   if (read_only_ || (!modified && cache_type() == net::SHADER_CACHE))
 773     return;
 774   eviction_.UpdateRank(entry, modified);
 775 }
 776
 777 void BackendImpl::RecoveredEntry(CacheRankingsBlock* rankings) {
 778   Addr address(rankings->Data()->contents);
 779   EntryImpl* cache_entry = NULL;
 780   if (NewEntry(address, &cache_entry)) {
 781     STRESS_NOTREACHED();
 782     return;
 783   }
 784
 785   uint32 hash = cache_entry->GetHash();
 786   cache_entry->Release();
 787
 788   // Anything on the table means that this entry is there.
 789   if (data_->table[hash & mask_])
 790     return;
 791
 792   data_->table[hash & mask_] = address.value();
 793   FlushIndex();
 794 }
 795
 796 void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
 797   uint32 hash = entry->GetHash();
 798   std::string key = entry->GetKey();
 799   Addr entry_addr = entry->entry()->address();
 800   bool error;
 801   EntryImpl* parent_entry = MatchEntry(key, hash, true, entry_addr, &error);
 802   CacheAddr child(entry->GetNextAddress());
 803
 804   Trace("Doom entry 0x%p", entry);
 805
 806   if (!entry->doomed()) {
 807     // We may have doomed this entry from within MatchEntry.
 808     eviction_.OnDoomEntry(entry);
 809     entry->InternalDoom();
 810     if (!new_eviction_) {
 811       DecreaseNumEntries();
 812     }
 813     stats_.OnEvent(Stats::DOOM_ENTRY);
 814   }
 815
 816   if (parent_entry) {
 817     parent_entry->SetNextAddress(Addr(child));
 818     parent_entry->Release();
 819   } else if (!error) {
 820     data_->table[hash & mask_] = child;
 821   }
 822
 823   FlushIndex();
 824 }
 825
 826 #if defined(NET_BUILD_STRESS_CACHE)
 827
 828 CacheAddr BackendImpl::GetNextAddr(Addr address) {
 829   EntriesMap::iterator it = open_entries_.find(address.value());
 830   if (it != open_entries_.end()) {
 831     EntryImpl* this_entry = it->second;
 832     return this_entry->GetNextAddress();
 833   }
 834   DCHECK(block_files_.IsValid(address));
 835   DCHECK(!address.is_separate_file() && address.file_type() == BLOCK_256);
 836
 837   CacheEntryBlock entry(File(address), address);
 838   CHECK(entry.Load());
 839   return entry.Data()->next;
 840 }
 841
 842 void BackendImpl::NotLinked(EntryImpl* entry) {
 843   Addr entry_addr = entry->entry()->address();
 844   uint32 i = entry->GetHash() & mask_;
 845   Addr address(data_->table[i]);
 846   if (!address.is_initialized())
 847     return;
 848
 849   for (;;) {
 850     DCHECK(entry_addr.value() != address.value());
 851     address.set_value(GetNextAddr(address));
 852     if (!address.is_initialized())
 853       break;
 854   }
 855 }
 856 #endif  // NET_BUILD_STRESS_CACHE
 857
 858 // An entry may be linked on the DELETED list for a while after being doomed.
 859 // This function is called when we want to remove it.
 860 void BackendImpl::RemoveEntry(EntryImpl* entry) {
 861 #if defined(NET_BUILD_STRESS_CACHE)
 862   NotLinked(entry);
 863 #endif
 864   if (!new_eviction_)
 865     return;
 866
 867   DCHECK_NE(ENTRY_NORMAL, entry->entry()->Data()->state);
 868
 869   Trace("Remove entry 0x%p", entry);
 870   eviction_.OnDestroyEntry(entry);
 871   DecreaseNumEntries();
 872 }
 873
 874 void BackendImpl::OnEntryDestroyBegin(Addr address) {
 875   EntriesMap::iterator it = open_entries_.find(address.value());
 876   if (it != open_entries_.end())
 877     open_entries_.erase(it);
 878 }
 879
 880 void BackendImpl::OnEntryDestroyEnd() {
 881   DecreaseNumRefs();
 882   if (data_->header.num_bytes > max_size_ && !read_only_ &&
 883       (up_ticks_ > kTrimDelay || user_flags_ & kNoRandom))
 884     eviction_.TrimCache(false);
 885 }
 886
 887 EntryImpl* BackendImpl::GetOpenEntry(CacheRankingsBlock* rankings) const {
 888   DCHECK(rankings->HasData());
 889   EntriesMap::const_iterator it =
 890       open_entries_.find(rankings->Data()->contents);
 891   if (it != open_entries_.end()) {
 892     // We have this entry in memory.
 893     return it->second;
 894   }
 895
 896   return NULL;
 897 }
 898
 899 int32 BackendImpl::GetCurrentEntryId() const {
 900   return data_->header.this_id;
 901 }
 902
 903 int BackendImpl::MaxFileSize() const {
 904   return cache_type() == net::PNACL_CACHE ? max_size_ : max_size_ / 8;
 905 }
 906
 907 void BackendImpl::ModifyStorageSize(int32 old_size, int32 new_size) {
 908   if (disabled_ || old_size == new_size)
 909     return;
 910   if (old_size > new_size)
 911     SubstractStorageSize(old_size - new_size);
 912   else
 913     AddStorageSize(new_size - old_size);
 914
 915   FlushIndex();
 916
 917   // Update the usage statistics.
 918   stats_.ModifyStorageStats(old_size, new_size);
 919 }
 920
 921 void BackendImpl::TooMuchStorageRequested(int32 size) {
 922   stats_.ModifyStorageStats(0, size);
 923 }
 924
 925 bool BackendImpl::IsAllocAllowed(int current_size, int new_size) {
 926   DCHECK_GT(new_size, current_size);
 927   if (user_flags_ & kNoBuffering)
 928     return false;
 929
 930   int to_add = new_size - current_size;
 931   if (buffer_bytes_ + to_add > MaxBuffersSize())
 932     return false;
 933
 934   buffer_bytes_ += to_add;
 935   CACHE_UMA(COUNTS_50000, "BufferBytes", 0, buffer_bytes_ / 1024);
 936   return true;
 937 }
 938
 939 void BackendImpl::BufferDeleted(int size) {
 940   buffer_bytes_ -= size;
 941   DCHECK_GE(size, 0);
 942 }
 943
 944 bool BackendImpl::IsLoaded() const {
 945   CACHE_UMA(COUNTS, "PendingIO", 0, num_pending_io_);
 946   if (user_flags_ & kNoLoadProtection)
 947     return false;
 948
 949   return (num_pending_io_ > 5 || user_load_);
 950 }
 951
 952 std::string BackendImpl::HistogramName(const char* name, int experiment) const {
 953   if (!experiment)
 954     return base::StringPrintf("DiskCache.%d.%s", cache_type_, name);
 955   return base::StringPrintf("DiskCache.%d.%s_%d", cache_type_,
 956                             name, experiment);
 957 }
 958
 959 base::WeakPtr<BackendImpl> BackendImpl::GetWeakPtr() {
 960   return ptr_factory_.GetWeakPtr();
 961 }
 962
 963 // We want to remove biases from some histograms so we only send data once per
 964 // week.
 965 bool BackendImpl::ShouldReportAgain() {
 966   if (uma_report_)
 967     return uma_report_ == 2;
 968
 969   uma_report_++;
 970   int64 last_report = stats_.GetCounter(Stats::LAST_REPORT);
 971   Time last_time = Time::FromInternalValue(last_report);
 972   if (!last_report || (Time::Now() - last_time).InDays() >= 7) {
 973     stats_.SetCounter(Stats::LAST_REPORT, Time::Now().ToInternalValue());
 974     uma_report_++;
 975     return true;
 976   }
 977   return false;
 978 }
 979
 980 void BackendImpl::FirstEviction() {
 981   DCHECK(data_->header.create_time);
 982   if (!GetEntryCount())
 983     return;  // This is just for unit tests.
 984
 985   Time create_time = Time::FromInternalValue(data_->header.create_time);
 986   CACHE_UMA(AGE, "FillupAge", 0, create_time);
 987
 988   int64 use_time = stats_.GetCounter(Stats::TIMER);
 989   CACHE_UMA(HOURS, "FillupTime", 0, static_cast<int>(use_time / 120));
 990   CACHE_UMA(PERCENTAGE, "FirstHitRatio", 0, stats_.GetHitRatio());
 991
 992   if (!use_time)
 993     use_time = 1;
 994   CACHE_UMA(COUNTS_10000, "FirstEntryAccessRate", 0,
 995             static_cast<int>(data_->header.num_entries / use_time));
 996   CACHE_UMA(COUNTS, "FirstByteIORate", 0,
 997             static_cast<int>((data_->header.num_bytes / 1024) / use_time));
 998
 999   int avg_size = data_->header.num_bytes / GetEntryCount();
1000   CACHE_UMA(COUNTS, "FirstEntrySize", 0, avg_size);
1001
1002   int large_entries_bytes = stats_.GetLargeEntriesSize();
1003   int large_ratio = large_entries_bytes * 100 / data_->header.num_bytes;
1004   CACHE_UMA(PERCENTAGE, "FirstLargeEntriesRatio", 0, large_ratio);
1005
1006   if (new_eviction_) {
1007     CACHE_UMA(PERCENTAGE, "FirstResurrectRatio", 0, stats_.GetResurrectRatio());
1008     CACHE_UMA(PERCENTAGE, "FirstNoUseRatio", 0,
1009               data_->header.lru.sizes[0] * 100 / data_->header.num_entries);
1010     CACHE_UMA(PERCENTAGE, "FirstLowUseRatio", 0,
1011               data_->header.lru.sizes[1] * 100 / data_->header.num_entries);
1012     CACHE_UMA(PERCENTAGE, "FirstHighUseRatio", 0,
1013               data_->header.lru.sizes[2] * 100 / data_->header.num_entries);
1014   }
1015
1016   stats_.ResetRatios();
1017 }
1018
1019 void BackendImpl::CriticalError(int error) {
1020   STRESS_NOTREACHED();
1021   LOG(ERROR) << "Critical error found " << error;
1022   if (disabled_)
1023     return;
1024
1025   stats_.OnEvent(Stats::FATAL_ERROR);
1026   LogStats();
1027   ReportError(error);
1028
1029   // Setting the index table length to an invalid value will force re-creation
1030   // of the cache files.
1031   data_->header.table_len = 1;
1032   disabled_ = true;
1033
1034   if (!num_refs_)
1035     base::MessageLoop::current()->PostTask(
1036         FROM_HERE, base::Bind(&BackendImpl::RestartCache, GetWeakPtr(), true));
1037 }
1038
1039 void BackendImpl::ReportError(int error) {
1040   STRESS_DCHECK(!error || error == ERR_PREVIOUS_CRASH ||
1041                 error == ERR_CACHE_CREATED);
1042
1043   // We transmit positive numbers, instead of direct error codes.
1044   DCHECK_LE(error, 0);
1045   CACHE_UMA(CACHE_ERROR, "Error", 0, error * -1);
1046 }
1047
1048 void BackendImpl::OnEvent(Stats::Counters an_event) {
1049   stats_.OnEvent(an_event);
1050 }
1051
1052 void BackendImpl::OnRead(int32 bytes) {
1053   DCHECK_GE(bytes, 0);
1054   byte_count_ += bytes;
1055   if (byte_count_ < 0)
1056     byte_count_ = kint32max;
1057 }
1058
1059 void BackendImpl::OnWrite(int32 bytes) {
1060   // We use the same implementation as OnRead... just log the number of bytes.
1061   OnRead(bytes);
1062 }
1063
1064 void BackendImpl::OnStatsTimer() {
1065   if (disabled_)
1066     return;
1067
1068   stats_.OnEvent(Stats::TIMER);
1069   int64 time = stats_.GetCounter(Stats::TIMER);
1070   int64 current = stats_.GetCounter(Stats::OPEN_ENTRIES);
1071
1072   // OPEN_ENTRIES is a sampled average of the number of open entries, avoiding
1073   // the bias towards 0.
1074   if (num_refs_ && (current != num_refs_)) {
1075     int64 diff = (num_refs_ - current) / 50;
1076     if (!diff)
1077       diff = num_refs_ > current ? 1 : -1;
1078     current = current + diff;
1079     stats_.SetCounter(Stats::OPEN_ENTRIES, current);
1080     stats_.SetCounter(Stats::MAX_ENTRIES, max_refs_);
1081   }
1082
1083   CACHE_UMA(COUNTS, "NumberOfReferences", 0, num_refs_);
1084
1085   CACHE_UMA(COUNTS_10000, "EntryAccessRate", 0, entry_count_);
1086   CACHE_UMA(COUNTS, "ByteIORate", 0, byte_count_ / 1024);
1087
1088   // These values cover about 99.5% of the population (Oct 2011).
1089   user_load_ = (entry_count_ > 300 || byte_count_ > 7 * 1024 * 1024);
1090   entry_count_ = 0;
1091   byte_count_ = 0;
1092   up_ticks_++;
1093
1094   if (!data_)
1095     first_timer_ = false;
1096   if (first_timer_) {
1097     first_timer_ = false;
1098     if (ShouldReportAgain())
1099       ReportStats();
1100   }
1101
1102   // Save stats to disk at 5 min intervals.
1103   if (time % 10 == 0)
1104     StoreStats();
1105 }
1106
1107 void BackendImpl::IncrementIoCount() {
1108   num_pending_io_++;
1109 }
1110
1111 void BackendImpl::DecrementIoCount() {
1112   num_pending_io_--;
1113 }
1114
1115 void BackendImpl::SetUnitTestMode() {
1116   user_flags_ |= kUnitTestMode;
1117   unit_test_ = true;
1118 }
1119
1120 void BackendImpl::SetUpgradeMode() {
1121   user_flags_ |= kUpgradeMode;
1122   read_only_ = true;
1123 }
1124
1125 void BackendImpl::SetNewEviction() {
1126   user_flags_ |= kNewEviction;
1127   new_eviction_ = true;
1128 }
1129
1130 void BackendImpl::SetFlags(uint32 flags) {
1131   user_flags_ |= flags;
1132 }
1133
1134 void BackendImpl::ClearRefCountForTest() {
1135   num_refs_ = 0;
1136 }
1137
1138 int BackendImpl::FlushQueueForTest(const CompletionCallback& callback) {
1139   background_queue_.FlushQueue(callback);
1140   return net::ERR_IO_PENDING;
1141 }
1142
1143 int BackendImpl::RunTaskForTest(const base::Closure& task,
1144                                 const CompletionCallback& callback) {
1145   background_queue_.RunTask(task, callback);
1146   return net::ERR_IO_PENDING;
1147 }
1148
1149 void BackendImpl::TrimForTest(bool empty) {
1150   eviction_.SetTestMode();
1151   eviction_.TrimCache(empty);
1152 }
1153
1154 void BackendImpl::TrimDeletedListForTest(bool empty) {
1155   eviction_.SetTestMode();
1156   eviction_.TrimDeletedList(empty);
1157 }
1158
1159 base::RepeatingTimer<BackendImpl>* BackendImpl::GetTimerForTest() {
1160   return timer_.get();
1161 }
1162
1163 int BackendImpl::SelfCheck() {
1164   if (!init_) {
1165     LOG(ERROR) << "Init failed";
1166     return ERR_INIT_FAILED;
1167   }
1168
1169   int num_entries = rankings_.SelfCheck();
1170   if (num_entries < 0) {
1171     LOG(ERROR) << "Invalid rankings list, error " << num_entries;
1172 #if !defined(NET_BUILD_STRESS_CACHE)
1173     return num_entries;
1174 #endif
1175   }
1176
1177   if (num_entries != data_->header.num_entries) {
1178     LOG(ERROR) << "Number of entries mismatch";
1179 #if !defined(NET_BUILD_STRESS_CACHE)
1180     return ERR_NUM_ENTRIES_MISMATCH;
1181 #endif
1182   }
1183
1184   return CheckAllEntries();
1185 }
1186
1187 void BackendImpl::FlushIndex() {
1188   if (index_.get() && !disabled_)
1189     index_->Flush();
1190 }
1191
1192 // ------------------------------------------------------------------------
1193
1194 net::CacheType BackendImpl::GetCacheType() const {
1195   return cache_type_;
1196 }
1197
1198 int32 BackendImpl::GetEntryCount() const {
1199   if (!index_.get() || disabled_)
1200     return 0;
1201   // num_entries includes entries already evicted.
1202   int32 not_deleted = data_->header.num_entries -
1203                       data_->header.lru.sizes[Rankings::DELETED];
1204
1205   if (not_deleted < 0) {
1206     NOTREACHED();
1207     not_deleted = 0;
1208   }
1209
1210   return not_deleted;
1211 }
1212
1213 int BackendImpl::OpenEntry(const std::string& key, Entry** entry,
1214                            const CompletionCallback& callback) {
1215   DCHECK(!callback.is_null());
1216   background_queue_.OpenEntry(key, entry, callback);
1217   return net::ERR_IO_PENDING;
1218 }
1219
1220 int BackendImpl::CreateEntry(const std::string& key, Entry** entry,
1221                              const CompletionCallback& callback) {
1222   DCHECK(!callback.is_null());
1223   background_queue_.CreateEntry(key, entry, callback);
1224   return net::ERR_IO_PENDING;
1225 }
1226
1227 int BackendImpl::DoomEntry(const std::string& key,
1228                            const CompletionCallback& callback) {
1229   DCHECK(!callback.is_null());
1230   background_queue_.DoomEntry(key, callback);
1231   return net::ERR_IO_PENDING;
1232 }
1233
1234 int BackendImpl::DoomAllEntries(const CompletionCallback& callback) {
1235   DCHECK(!callback.is_null());
1236   background_queue_.DoomAllEntries(callback);
1237   return net::ERR_IO_PENDING;
1238 }
1239
1240 int BackendImpl::DoomEntriesBetween(const base::Time initial_time,
1241                                     const base::Time end_time,
1242                                     const CompletionCallback& callback) {
1243   DCHECK(!callback.is_null());
1244   background_queue_.DoomEntriesBetween(initial_time, end_time, callback);
1245   return net::ERR_IO_PENDING;
1246 }
1247
1248 int BackendImpl::DoomEntriesSince(const base::Time initial_time,
1249                                   const CompletionCallback& callback) {
1250   DCHECK(!callback.is_null());
1251   background_queue_.DoomEntriesSince(initial_time, callback);
1252   return net::ERR_IO_PENDING;
1253 }
1254
1255 class BackendImpl::IteratorImpl : public Backend::Iterator {
1256  public:
1257   explicit IteratorImpl(base::WeakPtr<InFlightBackendIO> background_queue)
1258       : background_queue_(background_queue),
1259         iterator_(new Rankings::Iterator()) {
1260   }
1261
1262   ~IteratorImpl() override {
1263     if (background_queue_)
1264       background_queue_->EndEnumeration(iterator_.Pass());
1265   }
1266
1267   int OpenNextEntry(Entry** next_entry,
1268                     const net::CompletionCallback& callback) override {
1269     if (!background_queue_)
1270       return net::ERR_FAILED;
1271     background_queue_->OpenNextEntry(iterator_.get(), next_entry, callback);
1272     return net::ERR_IO_PENDING;
1273   }
1274
1275  private:
1276   const base::WeakPtr<InFlightBackendIO> background_queue_;
1277   scoped_ptr<Rankings::Iterator> iterator_;
1278 };
1279
1280 scoped_ptr<Backend::Iterator> BackendImpl::CreateIterator() {
1281   return scoped_ptr<Backend::Iterator>(new IteratorImpl(GetBackgroundQueue()));
1282 }
1283
1284 void BackendImpl::GetStats(StatsItems* stats) {
1285   if (disabled_)
1286     return;
1287
1288   std::pair<std::string, std::string> item;
1289
1290   item.first = "Entries";
1291   item.second = base::StringPrintf("%d", data_->header.num_entries);
1292   stats->push_back(item);
1293
1294   item.first = "Pending IO";
1295   item.second = base::StringPrintf("%d", num_pending_io_);
1296   stats->push_back(item);
1297
1298   item.first = "Max size";
1299   item.second = base::StringPrintf("%d", max_size_);
1300   stats->push_back(item);
1301
1302   item.first = "Current size";
1303   item.second = base::StringPrintf("%d", data_->header.num_bytes);
1304   stats->push_back(item);
1305
1306   item.first = "Cache type";
1307   item.second = "Blockfile Cache";
1308   stats->push_back(item);
1309
1310   stats_.GetItems(stats);
1311 }
1312
1313 void BackendImpl::OnExternalCacheHit(const std::string& key) {
1314   background_queue_.OnExternalCacheHit(key);
1315 }
1316
1317 // ------------------------------------------------------------------------
1318
1319 // We just created a new file so we're going to write the header and set the
1320 // file length to include the hash table (zero filled).
1321 bool BackendImpl::CreateBackingStore(disk_cache::File* file) {
1322   AdjustMaxCacheSize(0);
1323
1324   IndexHeader header;
1325   header.table_len = DesiredIndexTableLen(max_size_);
1326
1327   // We need file version 2.1 for the new eviction algorithm.
1328   if (new_eviction_)
1329     header.version = 0x20001;
1330
1331   header.create_time = Time::Now().ToInternalValue();
1332
1333   if (!file->Write(&header, sizeof(header), 0))
1334     return false;
1335
1336   return file->SetLength(GetIndexSize(header.table_len));
1337 }
1338
1339 bool BackendImpl::InitBackingStore(bool* file_created) {
1340   if (!base::CreateDirectory(path_))
1341     return false;
1342
1343   base::FilePath index_name = path_.AppendASCII(kIndexName);
1344
1345   int flags = base::File::FLAG_READ | base::File::FLAG_WRITE |
1346               base::File::FLAG_OPEN_ALWAYS | base::File::FLAG_EXCLUSIVE_WRITE;
1347   base::File base_file(index_name, flags);
1348   if (!base_file.IsValid())
1349     return false;
1350
1351   bool ret = true;
1352   *file_created = base_file.created();
1353
1354   scoped_refptr<disk_cache::File> file(new disk_cache::File(base_file.Pass()));
1355   if (*file_created)
1356     ret = CreateBackingStore(file.get());
1357
1358   file = NULL;
1359   if (!ret)
1360     return false;
1361
1362   index_ = new MappedFile();
1363   data_ = static_cast<Index*>(index_->Init(index_name, 0));
1364   if (!data_) {
1365     LOG(ERROR) << "Unable to map Index file";
1366     return false;
1367   }
1368
1369   if (index_->GetLength() < sizeof(Index)) {
1370     // We verify this again on CheckIndex() but it's easier to make sure now
1371     // that the header is there.
1372     LOG(ERROR) << "Corrupt Index file";
1373     return false;
1374   }
1375
1376   return true;
1377 }
1378
1379 // The maximum cache size will be either set explicitly by the caller, or
1380 // calculated by this code.
1381 void BackendImpl::AdjustMaxCacheSize(int table_len) {
1382   if (max_size_)
1383     return;
1384
1385   // If table_len is provided, the index file exists.
1386   DCHECK(!table_len || data_->header.magic);
1387
1388   // The user is not setting the size, let's figure it out.
1389   int64 available = base::SysInfo::AmountOfFreeDiskSpace(path_);
1390   if (available < 0) {
1391     max_size_ = kDefaultCacheSize;
1392     return;
1393   }
1394
1395   if (table_len)
1396     available += data_->header.num_bytes;
1397
1398   max_size_ = PreferredCacheSize(available);
1399
1400   if (!table_len)
1401     return;
1402
1403   // If we already have a table, adjust the size to it.
1404   int current_max_size = MaxStorageSizeForTable(table_len);
1405   if (max_size_ > current_max_size)
1406     max_size_= current_max_size;
1407 }
1408
1409 bool BackendImpl::InitStats() {
1410   Addr address(data_->header.stats);
1411   int size = stats_.StorageSize();
1412
1413   if (!address.is_initialized()) {
1414     FileType file_type = Addr::RequiredFileType(size);
1415     DCHECK_NE(file_type, EXTERNAL);
1416     int num_blocks = Addr::RequiredBlocks(size, file_type);
1417
1418     if (!CreateBlock(file_type, num_blocks, &address))
1419       return false;
1420
1421     data_->header.stats = address.value();
1422     return stats_.Init(NULL, 0, address);
1423   }
1424
1425   if (!address.is_block_file()) {
1426     NOTREACHED();
1427     return false;
1428   }
1429
1430   // Load the required data.
1431   size = address.num_blocks() * address.BlockSize();
1432   MappedFile* file = File(address);
1433   if (!file)
1434     return false;
1435
1436   scoped_ptr<char[]> data(new char[size]);
1437   size_t offset = address.start_block() * address.BlockSize() +
1438                   kBlockHeaderSize;
1439   if (!file->Read(data.get(), size, offset))
1440     return false;
1441
1442   if (!stats_.Init(data.get(), size, address))
1443     return false;
1444   if (cache_type_ == net::DISK_CACHE && ShouldReportAgain())
1445     stats_.InitSizeHistogram();
1446   return true;
1447 }
1448
1449 void BackendImpl::StoreStats() {
1450   int size = stats_.StorageSize();
1451   scoped_ptr<char[]> data(new char[size]);
1452   Addr address;
1453   size = stats_.SerializeStats(data.get(), size, &address);
1454   DCHECK(size);
1455   if (!address.is_initialized())
1456     return;
1457
1458   MappedFile* file = File(address);
1459   if (!file)
1460     return;
1461
1462   size_t offset = address.start_block() * address.BlockSize() +
1463                   kBlockHeaderSize;
1464   file->Write(data.get(), size, offset);  // ignore result.
1465 }
1466
1467 void BackendImpl::RestartCache(bool failure) {
1468   int64 errors = stats_.GetCounter(Stats::FATAL_ERROR);
1469   int64 full_dooms = stats_.GetCounter(Stats::DOOM_CACHE);
1470   int64 partial_dooms = stats_.GetCounter(Stats::DOOM_RECENT);
1471   int64 last_report = stats_.GetCounter(Stats::LAST_REPORT);
1472
1473   PrepareForRestart();
1474   if (failure) {
1475     DCHECK(!num_refs_);
1476     DCHECK(!open_entries_.size());
1477     DelayedCacheCleanup(path_);
1478   } else {
1479     DeleteCache(path_, false);
1480   }
1481
1482   // Don't call Init() if directed by the unit test: we are simulating a failure
1483   // trying to re-enable the cache.
1484   if (unit_test_)
1485     init_ = true;  // Let the destructor do proper cleanup.
1486   else if (SyncInit() == net::OK) {
1487     stats_.SetCounter(Stats::FATAL_ERROR, errors);
1488     stats_.SetCounter(Stats::DOOM_CACHE, full_dooms);
1489     stats_.SetCounter(Stats::DOOM_RECENT, partial_dooms);
1490     stats_.SetCounter(Stats::LAST_REPORT, last_report);
1491   }
1492 }
1493
1494 void BackendImpl::PrepareForRestart() {
1495   // Reset the mask_ if it was not given by the user.
1496   if (!(user_flags_ & kMask))
1497     mask_ = 0;
1498
1499   if (!(user_flags_ & kNewEviction))
1500     new_eviction_ = false;
1501
1502   disabled_ = true;
1503   data_->header.crash = 0;
1504   index_->Flush();
1505   index_ = NULL;
1506   data_ = NULL;
1507   block_files_.CloseFiles();
1508   rankings_.Reset();
1509   init_ = false;
1510   restarted_ = true;
1511 }
1512
1513 int BackendImpl::NewEntry(Addr address, EntryImpl** entry) {
1514   EntriesMap::iterator it = open_entries_.find(address.value());
1515   if (it != open_entries_.end()) {
1516     // Easy job. This entry is already in memory.
1517     EntryImpl* this_entry = it->second;
1518     this_entry->AddRef();
1519     *entry = this_entry;
1520     return 0;
1521   }
1522
1523   STRESS_DCHECK(block_files_.IsValid(address));
1524
1525   if (!address.SanityCheckForEntryV2()) {
1526     LOG(WARNING) << "Wrong entry address.";
1527     STRESS_NOTREACHED();
1528     return ERR_INVALID_ADDRESS;
1529   }
1530
1531   scoped_refptr<EntryImpl> cache_entry(
1532       new EntryImpl(this, address, read_only_));
1533   IncreaseNumRefs();
1534   *entry = NULL;
1535
1536   TimeTicks start = TimeTicks::Now();
1537   if (!cache_entry->entry()->Load())
1538     return ERR_READ_FAILURE;
1539
1540   if (IsLoaded()) {
1541     CACHE_UMA(AGE_MS, "LoadTime", 0, start);
1542   }
1543
1544   if (!cache_entry->SanityCheck()) {
1545     LOG(WARNING) << "Messed up entry found.";
1546     STRESS_NOTREACHED();
1547     return ERR_INVALID_ENTRY;
1548   }
1549
1550   STRESS_DCHECK(block_files_.IsValid(
1551                     Addr(cache_entry->entry()->Data()->rankings_node)));
1552
1553   if (!cache_entry->LoadNodeAddress())
1554     return ERR_READ_FAILURE;
1555
1556   if (!rankings_.SanityCheck(cache_entry->rankings(), false)) {
1557     STRESS_NOTREACHED();
1558     cache_entry->SetDirtyFlag(0);
1559     // Don't remove this from the list (it is not linked properly). Instead,
1560     // break the link back to the entry because it is going away, and leave the
1561     // rankings node to be deleted if we find it through a list.
1562     rankings_.SetContents(cache_entry->rankings(), 0);
1563   } else if (!rankings_.DataSanityCheck(cache_entry->rankings(), false)) {
1564     STRESS_NOTREACHED();
1565     cache_entry->SetDirtyFlag(0);
1566     rankings_.SetContents(cache_entry->rankings(), address.value());
1567   }
1568
1569   if (!cache_entry->DataSanityCheck()) {
1570     LOG(WARNING) << "Messed up entry found.";
1571     cache_entry->SetDirtyFlag(0);
1572     cache_entry->FixForDelete();
1573   }
1574
1575   // Prevent overwriting the dirty flag on the destructor.
1576   cache_entry->SetDirtyFlag(GetCurrentEntryId());
1577
1578   if (cache_entry->dirty()) {
1579     Trace("Dirty entry 0x%p 0x%x", reinterpret_cast<void*>(cache_entry.get()),
1580           address.value());
1581   }
1582
1583   open_entries_[address.value()] = cache_entry.get();
1584
1585   cache_entry->BeginLogging(net_log_, false);
1586   cache_entry.swap(entry);
1587   return 0;
1588 }
1589
1590 EntryImpl* BackendImpl::MatchEntry(const std::string& key, uint32 hash,
1591                                    bool find_parent, Addr entry_addr,
1592                                    bool* match_error) {
1593   Addr address(data_->table[hash & mask_]);
1594   scoped_refptr<EntryImpl> cache_entry, parent_entry;
1595   EntryImpl* tmp = NULL;
1596   bool found = false;
1597   std::set<CacheAddr> visited;
1598   *match_error = false;
1599
1600   for (;;) {
1601     if (disabled_)
1602       break;
1603
1604     if (visited.find(address.value()) != visited.end()) {
1605       // It's possible for a buggy version of the code to write a loop. Just
1606       // break it.
1607       Trace("Hash collision loop 0x%x", address.value());
1608       address.set_value(0);
1609       parent_entry->SetNextAddress(address);
1610     }
1611     visited.insert(address.value());
1612
1613     if (!address.is_initialized()) {
1614       if (find_parent)
1615         found = true;
1616       break;
1617     }
1618
1619     int error = NewEntry(address, &tmp);
1620     cache_entry.swap(&tmp);
1621
1622     if (error || cache_entry->dirty()) {
1623       // This entry is dirty on disk (it was not properly closed): we cannot
1624       // trust it.
1625       Addr child(0);
1626       if (!error)
1627         child.set_value(cache_entry->GetNextAddress());
1628
1629       if (parent_entry.get()) {
1630         parent_entry->SetNextAddress(child);
1631         parent_entry = NULL;
1632       } else {
1633         data_->table[hash & mask_] = child.value();
1634       }
1635
1636       Trace("MatchEntry dirty %d 0x%x 0x%x", find_parent, entry_addr.value(),
1637             address.value());
1638
1639       if (!error) {
1640         // It is important to call DestroyInvalidEntry after removing this
1641         // entry from the table.
1642         DestroyInvalidEntry(cache_entry.get());
1643         cache_entry = NULL;
1644       } else {
1645         Trace("NewEntry failed on MatchEntry 0x%x", address.value());
1646       }
1647
1648       // Restart the search.
1649       address.set_value(data_->table[hash & mask_]);
1650       visited.clear();
1651       continue;
1652     }
1653
1654     DCHECK_EQ(hash & mask_, cache_entry->entry()->Data()->hash & mask_);
1655     if (cache_entry->IsSameEntry(key, hash)) {
1656       if (!cache_entry->Update())
1657         cache_entry = NULL;
1658       found = true;
1659       if (find_parent && entry_addr.value() != address.value()) {
1660         Trace("Entry not on the index 0x%x", address.value());
1661         *match_error = true;
1662         parent_entry = NULL;
1663       }
1664       break;
1665     }
1666     if (!cache_entry->Update())
1667       cache_entry = NULL;
1668     parent_entry = cache_entry;
1669     cache_entry = NULL;
1670     if (!parent_entry.get())
1671       break;
1672
1673     address.set_value(parent_entry->GetNextAddress());
1674   }
1675
1676   if (parent_entry.get() && (!find_parent || !found))
1677     parent_entry = NULL;
1678
1679   if (find_parent && entry_addr.is_initialized() && !cache_entry.get()) {
1680     *match_error = true;
1681     parent_entry = NULL;
1682   }
1683
1684   if (cache_entry.get() && (find_parent || !found))
1685     cache_entry = NULL;
1686
1687   find_parent ? parent_entry.swap(&tmp) : cache_entry.swap(&tmp);
1688   FlushIndex();
1689   return tmp;
1690 }
1691
1692 bool BackendImpl::OpenFollowingEntryFromList(Rankings::List list,
1693                                              CacheRankingsBlock** from_entry,
1694                                              EntryImpl** next_entry) {
1695   if (disabled_)
1696     return false;
1697
1698   if (!new_eviction_ && Rankings::NO_USE != list)
1699     return false;
1700
1701   Rankings::ScopedRankingsBlock rankings(&rankings_, *from_entry);
1702   CacheRankingsBlock* next_block = rankings_.GetNext(rankings.get(), list);
1703   Rankings::ScopedRankingsBlock next(&rankings_, next_block);
1704   *from_entry = NULL;
1705
1706   *next_entry = GetEnumeratedEntry(next.get(), list);
1707   if (!*next_entry)
1708     return false;
1709
1710   *from_entry = next.release();
1711   return true;
1712 }
1713
1714 EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next,
1715                                            Rankings::List list) {
1716   if (!next || disabled_)
1717     return NULL;
1718
1719   EntryImpl* entry;
1720   int rv = NewEntry(Addr(next->Data()->contents), &entry);
1721   if (rv) {
1722     STRESS_NOTREACHED();
1723     rankings_.Remove(next, list, false);
1724     if (rv == ERR_INVALID_ADDRESS) {
1725       // There is nothing linked from the index. Delete the rankings node.
1726       DeleteBlock(next->address(), true);
1727     }
1728     return NULL;
1729   }
1730
1731   if (entry->dirty()) {
1732     // We cannot trust this entry.
1733     InternalDoomEntry(entry);
1734     entry->Release();
1735     return NULL;
1736   }
1737
1738   if (!entry->Update()) {
1739     STRESS_NOTREACHED();
1740     entry->Release();
1741     return NULL;
1742   }
1743
1744   // Note that it is unfortunate (but possible) for this entry to be clean, but
1745   // not actually the real entry. In other words, we could have lost this entry
1746   // from the index, and it could have been replaced with a newer one. It's not
1747   // worth checking that this entry is "the real one", so we just return it and
1748   // let the enumeration continue; this entry will be evicted at some point, and
1749   // the regular path will work with the real entry. With time, this problem
1750   // will disasappear because this scenario is just a bug.
1751
1752   // Make sure that we save the key for later.
1753   entry->GetKey();
1754
1755   return entry;
1756 }
1757
1758 EntryImpl* BackendImpl::ResurrectEntry(EntryImpl* deleted_entry) {
1759   if (ENTRY_NORMAL == deleted_entry->entry()->Data()->state) {
1760     deleted_entry->Release();
1761     stats_.OnEvent(Stats::CREATE_MISS);
1762     Trace("create entry miss ");
1763     return NULL;
1764   }
1765
1766   // We are attempting to create an entry and found out that the entry was
1767   // previously deleted.
1768
1769   eviction_.OnCreateEntry(deleted_entry);
1770   entry_count_++;
1771
1772   stats_.OnEvent(Stats::RESURRECT_HIT);
1773   Trace("Resurrect entry hit ");
1774   return deleted_entry;
1775 }
1776
1777 void BackendImpl::DestroyInvalidEntry(EntryImpl* entry) {
1778   LOG(WARNING) << "Destroying invalid entry.";
1779   Trace("Destroying invalid entry 0x%p", entry);
1780
1781   entry->SetPointerForInvalidEntry(GetCurrentEntryId());
1782
1783   eviction_.OnDoomEntry(entry);
1784   entry->InternalDoom();
1785
1786   if (!new_eviction_)
1787     DecreaseNumEntries();
1788   stats_.OnEvent(Stats::INVALID_ENTRY);
1789 }
1790
1791 void BackendImpl::AddStorageSize(int32 bytes) {
1792   data_->header.num_bytes += bytes;
1793   DCHECK_GE(data_->header.num_bytes, 0);
1794 }
1795
1796 void BackendImpl::SubstractStorageSize(int32 bytes) {
1797   data_->header.num_bytes -= bytes;
1798   DCHECK_GE(data_->header.num_bytes, 0);
1799 }
1800
1801 void BackendImpl::IncreaseNumRefs() {
1802   num_refs_++;
1803   if (max_refs_ < num_refs_)
1804     max_refs_ = num_refs_;
1805 }
1806
1807 void BackendImpl::DecreaseNumRefs() {
1808   DCHECK(num_refs_);
1809   num_refs_--;
1810
1811   if (!num_refs_ && disabled_)
1812     base::MessageLoop::current()->PostTask(
1813         FROM_HERE, base::Bind(&BackendImpl::RestartCache, GetWeakPtr(), true));
1814 }
1815
1816 void BackendImpl::IncreaseNumEntries() {
1817   data_->header.num_entries++;
1818   DCHECK_GT(data_->header.num_entries, 0);
1819 }
1820
1821 void BackendImpl::DecreaseNumEntries() {
1822   data_->header.num_entries--;
1823   if (data_->header.num_entries < 0) {
1824     NOTREACHED();
1825     data_->header.num_entries = 0;
1826   }
1827 }
1828
1829 void BackendImpl::LogStats() {
1830   StatsItems stats;
1831   GetStats(&stats);
1832
1833   for (size_t index = 0; index < stats.size(); index++)
1834     VLOG(1) << stats[index].first << ": " << stats[index].second;
1835 }
1836
1837 void BackendImpl::ReportStats() {
1838   CACHE_UMA(COUNTS, "Entries", 0, data_->header.num_entries);
1839
1840   int current_size = data_->header.num_bytes / (1024 * 1024);
1841   int max_size = max_size_ / (1024 * 1024);
1842   int hit_ratio_as_percentage = stats_.GetHitRatio();
1843
1844   CACHE_UMA(COUNTS_10000, "Size2", 0, current_size);
1845   // For any bin in HitRatioBySize2, the hit ratio of caches of that size is the
1846   // ratio of that bin's total count to the count in the same bin in the Size2
1847   // histogram.
1848   if (base::RandInt(0, 99) < hit_ratio_as_percentage)
1849     CACHE_UMA(COUNTS_10000, "HitRatioBySize2", 0, current_size);
1850   CACHE_UMA(COUNTS_10000, "MaxSize2", 0, max_size);
1851   if (!max_size)
1852     max_size++;
1853   CACHE_UMA(PERCENTAGE, "UsedSpace", 0, current_size * 100 / max_size);
1854
1855   CACHE_UMA(COUNTS_10000, "AverageOpenEntries2", 0,
1856             static_cast<int>(stats_.GetCounter(Stats::OPEN_ENTRIES)));
1857   CACHE_UMA(COUNTS_10000, "MaxOpenEntries2", 0,
1858             static_cast<int>(stats_.GetCounter(Stats::MAX_ENTRIES)));
1859   stats_.SetCounter(Stats::MAX_ENTRIES, 0);
1860
1861   CACHE_UMA(COUNTS_10000, "TotalFatalErrors", 0,
1862             static_cast<int>(stats_.GetCounter(Stats::FATAL_ERROR)));
1863   CACHE_UMA(COUNTS_10000, "TotalDoomCache", 0,
1864             static_cast<int>(stats_.GetCounter(Stats::DOOM_CACHE)));
1865   CACHE_UMA(COUNTS_10000, "TotalDoomRecentEntries", 0,
1866             static_cast<int>(stats_.GetCounter(Stats::DOOM_RECENT)));
1867   stats_.SetCounter(Stats::FATAL_ERROR, 0);
1868   stats_.SetCounter(Stats::DOOM_CACHE, 0);
1869   stats_.SetCounter(Stats::DOOM_RECENT, 0);
1870
1871   int age = (Time::Now() -
1872              Time::FromInternalValue(data_->header.create_time)).InHours();
1873   if (age)
1874     CACHE_UMA(HOURS, "FilesAge", 0, age);
1875
1876   int64 total_hours = stats_.GetCounter(Stats::TIMER) / 120;
1877   if (!data_->header.create_time || !data_->header.lru.filled) {
1878     int cause = data_->header.create_time ? 0 : 1;
1879     if (!data_->header.lru.filled)
1880       cause |= 2;
1881     CACHE_UMA(CACHE_ERROR, "ShortReport", 0, cause);
1882     CACHE_UMA(HOURS, "TotalTimeNotFull", 0, static_cast<int>(total_hours));
1883     return;
1884   }
1885
1886   // This is an up to date client that will report FirstEviction() data. After
1887   // that event, start reporting this:
1888
1889   CACHE_UMA(HOURS, "TotalTime", 0, static_cast<int>(total_hours));
1890   // For any bin in HitRatioByTotalTime, the hit ratio of caches of that total
1891   // time is the ratio of that bin's total count to the count in the same bin in
1892   // the TotalTime histogram.
1893   if (base::RandInt(0, 99) < hit_ratio_as_percentage)
1894     CACHE_UMA(HOURS, "HitRatioByTotalTime", 0, static_cast<int>(total_hours));
1895
1896   int64 use_hours = stats_.GetCounter(Stats::LAST_REPORT_TIMER) / 120;
1897   stats_.SetCounter(Stats::LAST_REPORT_TIMER, stats_.GetCounter(Stats::TIMER));
1898
1899   // We may see users with no use_hours at this point if this is the first time
1900   // we are running this code.
1901   if (use_hours)
1902     use_hours = total_hours - use_hours;
1903
1904   if (!use_hours || !GetEntryCount() || !data_->header.num_bytes)
1905     return;
1906
1907   CACHE_UMA(HOURS, "UseTime", 0, static_cast<int>(use_hours));
1908   // For any bin in HitRatioByUseTime, the hit ratio of caches of that use time
1909   // is the ratio of that bin's total count to the count in the same bin in the
1910   // UseTime histogram.
1911   if (base::RandInt(0, 99) < hit_ratio_as_percentage)
1912     CACHE_UMA(HOURS, "HitRatioByUseTime", 0, static_cast<int>(use_hours));
1913   CACHE_UMA(PERCENTAGE, "HitRatio", 0, hit_ratio_as_percentage);
1914
1915   int64 trim_rate = stats_.GetCounter(Stats::TRIM_ENTRY) / use_hours;
1916   CACHE_UMA(COUNTS, "TrimRate", 0, static_cast<int>(trim_rate));
1917
1918   int avg_size = data_->header.num_bytes / GetEntryCount();
1919   CACHE_UMA(COUNTS, "EntrySize", 0, avg_size);
1920   CACHE_UMA(COUNTS, "EntriesFull", 0, data_->header.num_entries);
1921
1922   CACHE_UMA(PERCENTAGE, "IndexLoad", 0,
1923             data_->header.num_entries * 100 / (mask_ + 1));
1924
1925   int large_entries_bytes = stats_.GetLargeEntriesSize();
1926   int large_ratio = large_entries_bytes * 100 / data_->header.num_bytes;
1927   CACHE_UMA(PERCENTAGE, "LargeEntriesRatio", 0, large_ratio);
1928
1929   if (new_eviction_) {
1930     CACHE_UMA(PERCENTAGE, "ResurrectRatio", 0, stats_.GetResurrectRatio());
1931     CACHE_UMA(PERCENTAGE, "NoUseRatio", 0,
1932               data_->header.lru.sizes[0] * 100 / data_->header.num_entries);
1933     CACHE_UMA(PERCENTAGE, "LowUseRatio", 0,
1934               data_->header.lru.sizes[1] * 100 / data_->header.num_entries);
1935     CACHE_UMA(PERCENTAGE, "HighUseRatio", 0,
1936               data_->header.lru.sizes[2] * 100 / data_->header.num_entries);
1937     CACHE_UMA(PERCENTAGE, "DeletedRatio", 0,
1938               data_->header.lru.sizes[4] * 100 / data_->header.num_entries);
1939   }
1940
1941   stats_.ResetRatios();
1942   stats_.SetCounter(Stats::TRIM_ENTRY, 0);
1943
1944   if (cache_type_ == net::DISK_CACHE)
1945     block_files_.ReportStats();
1946 }
1947
1948 void BackendImpl::UpgradeTo2_1() {
1949   // 2.1 is basically the same as 2.0, except that new fields are actually
1950   // updated by the new eviction algorithm.
1951   DCHECK(0x20000 == data_->header.version);
1952   data_->header.version = 0x20001;
1953   data_->header.lru.sizes[Rankings::NO_USE] = data_->header.num_entries;
1954 }
1955
1956 bool BackendImpl::CheckIndex() {
1957   DCHECK(data_);
1958
1959   size_t current_size = index_->GetLength();
1960   if (current_size < sizeof(Index)) {
1961     LOG(ERROR) << "Corrupt Index file";
1962     return false;
1963   }
1964
1965   if (new_eviction_) {
1966     // We support versions 2.0 and 2.1, upgrading 2.0 to 2.1.
1967     if (kIndexMagic != data_->header.magic ||
1968         kCurrentVersion >> 16 != data_->header.version >> 16) {
1969       LOG(ERROR) << "Invalid file version or magic";
1970       return false;
1971     }
1972     if (kCurrentVersion == data_->header.version) {
1973       // We need file version 2.1 for the new eviction algorithm.
1974       UpgradeTo2_1();
1975     }
1976   } else {
1977     if (kIndexMagic != data_->header.magic ||
1978         kCurrentVersion != data_->header.version) {
1979       LOG(ERROR) << "Invalid file version or magic";
1980       return false;
1981     }
1982   }
1983
1984   if (!data_->header.table_len) {
1985     LOG(ERROR) << "Invalid table size";
1986     return false;
1987   }
1988
1989   if (current_size < GetIndexSize(data_->header.table_len) ||
1990       data_->header.table_len & (kBaseTableLen - 1)) {
1991     LOG(ERROR) << "Corrupt Index file";
1992     return false;
1993   }
1994
1995   AdjustMaxCacheSize(data_->header.table_len);
1996
1997 #if !defined(NET_BUILD_STRESS_CACHE)
1998   if (data_->header.num_bytes < 0 ||
1999       (max_size_ < kint32max - kDefaultCacheSize &&
2000        data_->header.num_bytes > max_size_ + kDefaultCacheSize)) {
2001     LOG(ERROR) << "Invalid cache (current) size";
2002     return false;
2003   }
2004 #endif
2005
2006   if (data_->header.num_entries < 0) {
2007     LOG(ERROR) << "Invalid number of entries";
2008     return false;
2009   }
2010
2011   if (!mask_)
2012     mask_ = data_->header.table_len - 1;
2013
2014   // Load the table into memory.
2015   return index_->Preload();
2016 }
2017
2018 int BackendImpl::CheckAllEntries() {
2019   int num_dirty = 0;
2020   int num_entries = 0;
2021   DCHECK(mask_ < kuint32max);
2022   for (unsigned int i = 0; i <= mask_; i++) {
2023     Addr address(data_->table[i]);
2024     if (!address.is_initialized())
2025       continue;
2026     for (;;) {
2027       EntryImpl* tmp;
2028       int ret = NewEntry(address, &tmp);
2029       if (ret) {
2030         STRESS_NOTREACHED();
2031         return ret;
2032       }
2033       scoped_refptr<EntryImpl> cache_entry;
2034       cache_entry.swap(&tmp);
2035
2036       if (cache_entry->dirty())
2037         num_dirty++;
2038       else if (CheckEntry(cache_entry.get()))
2039         num_entries++;
2040       else
2041         return ERR_INVALID_ENTRY;
2042
2043       DCHECK_EQ(i, cache_entry->entry()->Data()->hash & mask_);
2044       address.set_value(cache_entry->GetNextAddress());
2045       if (!address.is_initialized())
2046         break;
2047     }
2048   }
2049
2050   Trace("CheckAllEntries End");
2051   if (num_entries + num_dirty != data_->header.num_entries) {
2052     LOG(ERROR) << "Number of entries " << num_entries << " " << num_dirty <<
2053                   " " << data_->header.num_entries;
2054     DCHECK_LT(num_entries, data_->header.num_entries);
2055     return ERR_NUM_ENTRIES_MISMATCH;
2056   }
2057
2058   return num_dirty;
2059 }
2060
2061 bool BackendImpl::CheckEntry(EntryImpl* cache_entry) {
2062   bool ok = block_files_.IsValid(cache_entry->entry()->address());
2063   ok = ok && block_files_.IsValid(cache_entry->rankings()->address());
2064   EntryStore* data = cache_entry->entry()->Data();
2065   for (size_t i = 0; i < arraysize(data->data_addr); i++) {
2066     if (data->data_addr[i]) {
2067       Addr address(data->data_addr[i]);
2068       if (address.is_block_file())
2069         ok = ok && block_files_.IsValid(address);
2070     }
2071   }
2072
2073   return ok && cache_entry->rankings()->VerifyHash();
2074 }
2075
2076 int BackendImpl::MaxBuffersSize() {
2077   static int64 total_memory = base::SysInfo::AmountOfPhysicalMemory();
2078   static bool done = false;
2079
2080   if (!done) {
2081     const int kMaxBuffersSize = 30 * 1024 * 1024;
2082
2083     // We want to use up to 2% of the computer's memory.
2084     total_memory = total_memory * 2 / 100;
2085     if (total_memory > kMaxBuffersSize || total_memory <= 0)
2086       total_memory = kMaxBuffersSize;
2087
2088     done = true;
2089   }
2090
2091   return static_cast<int>(total_memory);
2092 }
2093
2094 }  // namespace disk_cache