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