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