Disk cache: Add base files for implementation of file format version 3.

net/disk_cache/v3/backend_impl_v3.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/disk_cache/backend_impl.h"
 
 #include "base/bind.h"
 #include "base/bind_helpers.h"
 #include "base/file_util.h"
 #include "base/files/file_path.h"
@@ skipping 54 matching lines @@
 
 int MaxStorageSizeForTable(int table_len) {
   return table_len * (k64kEntriesStore / kBaseTableLen);
 }
 
 size_t GetIndexSize(int table_len) {
   size_t table_size = sizeof(disk_cache::CacheAddr) * table_len;
   return sizeof(disk_cache::IndexHeader) + table_size;
 }
 
-// ------------------------------------------------------------------------
-
-// Sets group for the current experiment. Returns false if the files should be
-// discarded.
-bool InitExperiment(disk_cache::IndexHeader* header, bool cache_created) {
-  if (header->experiment == disk_cache::EXPERIMENT_OLD_FILE1 ||
-      header->experiment == disk_cache::EXPERIMENT_OLD_FILE2) {
-    // Discard current cache.
-    return false;
-  }
-
-  if (base::FieldTrialList::FindFullName("SimpleCacheTrial") ==
-          "ExperimentControl") {
-    if (cache_created) {
-      header->experiment = disk_cache::EXPERIMENT_SIMPLE_CONTROL;
-      return true;
-    } else if (header->experiment != disk_cache::EXPERIMENT_SIMPLE_CONTROL) {
-      return false;
-    }
-  }
-
-  header->experiment = disk_cache::NO_EXPERIMENT;
-  return true;
-}
-
-// A callback to perform final cleanup on the background thread.
-void FinalCleanupCallback(disk_cache::BackendImpl* backend) {
-  backend->CleanupCache();
-}
-
 }  // namespace
 
 // ------------------------------------------------------------------------
 
 namespace disk_cache {
 
-// Returns the preferred maximum number of bytes for the cache given the
-// number of available bytes.
-int PreferedCacheSize(int64 available) {
-  // Return 80% of the available space if there is not enough space to use
-  // kDefaultCacheSize.
-  if (available < kDefaultCacheSize * 10 / 8)
-    return static_cast<int32>(available * 8 / 10);
-
-  // Return kDefaultCacheSize if it uses 80% to 10% of the available space.
-  if (available < kDefaultCacheSize * 10)
-    return kDefaultCacheSize;
-
-  // Return 10% of the available space if the target size
-  // (2.5 * kDefaultCacheSize) is more than 10%.
-  if (available < static_cast<int64>(kDefaultCacheSize) * 25)
-    return static_cast<int32>(available / 10);
-
-  // Return the target size (2.5 * kDefaultCacheSize) if it uses 10% to 1%
-  // of the available space.
-  if (available < static_cast<int64>(kDefaultCacheSize) * 250)
-    return kDefaultCacheSize * 5 / 2;
-
-  // Return 1% of the available space if it does not exceed kint32max.
-  if (available < static_cast<int64>(kint32max) * 100)
-    return static_cast<int32>(available / 100);
-
-  return kint32max;
-}
-
-// ------------------------------------------------------------------------
-
 BackendImpl::BackendImpl(const base::FilePath& path,
                          base::MessageLoopProxy* cache_thread,
                          net::NetLog* net_log)
     : background_queue_(this, cache_thread),
       path_(path),
       block_files_(path),
       mask_(0),
       max_size_(0),
       up_ticks_(0),
       cache_type_(net::DISK_CACHE),
@@ skipping 59 matching lines @@
     base::ThreadRestrictions::ScopedAllowWait allow_wait;
     done_.Wait();
   }
 }
 
 int BackendImpl::Init(const CompletionCallback& callback) {
   background_queue_.Init(callback);
   return net::ERR_IO_PENDING;
 }
 
-int BackendImpl::SyncInit() {
-#if defined(NET_BUILD_STRESS_CACHE)
-  // Start evictions right away.
-  up_ticks_ = kTrimDelay * 2;
-#endif
-  DCHECK(!init_);
-  if (init_)
-    return net::ERR_FAILED;
-
-  bool create_files = false;
-  if (!InitBackingStore(&create_files)) {
-    ReportError(ERR_STORAGE_ERROR);
-    return net::ERR_FAILED;
-  }
-
-  num_refs_ = num_pending_io_ = max_refs_ = 0;
-  entry_count_ = byte_count_ = 0;
-
-  if (!restarted_) {
-    buffer_bytes_ = 0;
-    trace_object_ = TraceObject::GetTraceObject();
-    // Create a recurrent timer of 30 secs.
-    int timer_delay = unit_test_ ? 1000 : 30000;
-    timer_.reset(new base::RepeatingTimer<BackendImpl>());
-    timer_->Start(FROM_HERE, TimeDelta::FromMilliseconds(timer_delay), this,
-                  &BackendImpl::OnStatsTimer);
-  }
-
-  init_ = true;
-  Trace("Init");
-
-  if (data_->header.experiment != NO_EXPERIMENT &&
-      cache_type_ != net::DISK_CACHE) {
-    // No experiment for other caches.
-    return net::ERR_FAILED;
-  }
-
-  if (!(user_flags_ & kNoRandom)) {
-    // The unit test controls directly what to test.
-    new_eviction_ = (cache_type_ == net::DISK_CACHE);
-  }
-
-  if (!CheckIndex()) {
-    ReportError(ERR_INIT_FAILED);
-    return net::ERR_FAILED;
-  }
-
-  if (!restarted_ && (create_files || !data_->header.num_entries))
-    ReportError(ERR_CACHE_CREATED);
-
-  if (!(user_flags_ & kNoRandom) && cache_type_ == net::DISK_CACHE &&
-      !InitExperiment(&data_->header, create_files)) {
-    return net::ERR_FAILED;
-  }
-
-  // We don't care if the value overflows. The only thing we care about is that
-  // the id cannot be zero, because that value is used as "not dirty".
-  // Increasing the value once per second gives us many years before we start
-  // having collisions.
-  data_->header.this_id++;
-  if (!data_->header.this_id)
-    data_->header.this_id++;
-
-  bool previous_crash = (data_->header.crash != 0);
-  data_->header.crash = 1;
-
-  if (!block_files_.Init(create_files))
-    return net::ERR_FAILED;
-
-  // We want to minimize the changes to cache for an AppCache.
-  if (cache_type() == net::APP_CACHE) {
-    DCHECK(!new_eviction_);
-    read_only_ = true;
-  } else if (cache_type() == net::SHADER_CACHE) {
-    DCHECK(!new_eviction_);
-  }
-
-  eviction_.Init(this);
-
-  // stats_ and rankings_ may end up calling back to us so we better be enabled.
-  disabled_ = false;
-  if (!InitStats())
-    return net::ERR_FAILED;
-
-  disabled_ = !rankings_.Init(this, new_eviction_);
-
-#if defined(STRESS_CACHE_EXTENDED_VALIDATION)
-  trace_object_->EnableTracing(false);
-  int sc = SelfCheck();
-  if (sc < 0 && sc != ERR_NUM_ENTRIES_MISMATCH)
-    NOTREACHED();
-  trace_object_->EnableTracing(true);
-#endif
-
-  if (previous_crash) {
-    ReportError(ERR_PREVIOUS_CRASH);
-  } else if (!restarted_) {
-    ReportError(ERR_NO_ERROR);
-  }
-
-  FlushIndex();
-
-  return disabled_ ? net::ERR_FAILED : net::OK;
-}
-
-void BackendImpl::CleanupCache() {
-  Trace("Backend Cleanup");
-  eviction_.Stop();
-  timer_.reset();
-
-  if (init_) {
-    StoreStats();
-    if (data_)
-      data_->header.crash = 0;
-
-    if (user_flags_ & kNoRandom) {
-      // This is a net_unittest, verify that we are not 'leaking' entries.
-      File::WaitForPendingIO(&num_pending_io_);
-      DCHECK(!num_refs_);
-    } else {
-      File::DropPendingIO();
-    }
-  }
-  block_files_.CloseFiles();
-  FlushIndex();
-  index_ = NULL;
-  ptr_factory_.InvalidateWeakPtrs();
-  done_.Signal();
-}
-
 // ------------------------------------------------------------------------
 
 int BackendImpl::OpenPrevEntry(void** iter, Entry** prev_entry,
                                const CompletionCallback& callback) {
   DCHECK(!callback.is_null());
   background_queue_.OpenPrevEntry(iter, prev_entry, callback);
   return net::ERR_IO_PENDING;
 }
 
-int BackendImpl::SyncOpenEntry(const std::string& key, Entry** entry) {
-  DCHECK(entry);
-  *entry = OpenEntryImpl(key);
-  return (*entry) ? net::OK : net::ERR_FAILED;
-}
-
-int BackendImpl::SyncCreateEntry(const std::string& key, Entry** entry) {
-  DCHECK(entry);
-  *entry = CreateEntryImpl(key);
-  return (*entry) ? net::OK : net::ERR_FAILED;
-}
-
-int BackendImpl::SyncDoomEntry(const std::string& key) {
-  if (disabled_)
-    return net::ERR_FAILED;
-
-  EntryImpl* entry = OpenEntryImpl(key);
-  if (!entry)
-    return net::ERR_FAILED;
-
-  entry->DoomImpl();
-  entry->Release();
-  return net::OK;
-}
-
-int BackendImpl::SyncDoomAllEntries() {
-  // This is not really an error, but it is an interesting condition.
-  ReportError(ERR_CACHE_DOOMED);
-  stats_.OnEvent(Stats::DOOM_CACHE);
-  if (!num_refs_) {
-    RestartCache(false);
-    return disabled_ ? net::ERR_FAILED : net::OK;
-  } else {
-    if (disabled_)
-      return net::ERR_FAILED;
-
-    eviction_.TrimCache(true);
-    return net::OK;
-  }
-}
-
-int BackendImpl::SyncDoomEntriesBetween(const base::Time initial_time,
-                                        const base::Time end_time) {
-  DCHECK_NE(net::APP_CACHE, cache_type_);
-  if (end_time.is_null())
-    return SyncDoomEntriesSince(initial_time);
-
-  DCHECK(end_time >= initial_time);
-
-  if (disabled_)
-    return net::ERR_FAILED;
-
-  EntryImpl* node;
-  void* iter = NULL;
-  EntryImpl* next = OpenNextEntryImpl(&iter);
-  if (!next)
-    return net::OK;
-
-  while (next) {
-    node = next;
-    next = OpenNextEntryImpl(&iter);
-
-    if (node->GetLastUsed() >= initial_time &&
-        node->GetLastUsed() < end_time) {
-      node->DoomImpl();
-    } else if (node->GetLastUsed() < initial_time) {
-      if (next)
-        next->Release();
-      next = NULL;
-      SyncEndEnumeration(iter);
-    }
-
-    node->Release();
-  }
-
-  return net::OK;
-}
-
-// We use OpenNextEntryImpl to retrieve elements from the cache, until we get
-// entries that are too old.
-int BackendImpl::SyncDoomEntriesSince(const base::Time initial_time) {
-  DCHECK_NE(net::APP_CACHE, cache_type_);
-  if (disabled_)
-    return net::ERR_FAILED;
-
-  stats_.OnEvent(Stats::DOOM_RECENT);
-  for (;;) {
-    void* iter = NULL;
-    EntryImpl* entry = OpenNextEntryImpl(&iter);
-    if (!entry)
-      return net::OK;
-
-    if (initial_time > entry->GetLastUsed()) {
-      entry->Release();
-      SyncEndEnumeration(iter);
-      return net::OK;
-    }
-
-    entry->DoomImpl();
-    entry->Release();
-    SyncEndEnumeration(iter);  // Dooming the entry invalidates the iterator.
-  }
-}
-
-int BackendImpl::SyncOpenNextEntry(void** iter, Entry** next_entry) {
-  *next_entry = OpenNextEntryImpl(iter);
-  return (*next_entry) ? net::OK : net::ERR_FAILED;
-}
-
-int BackendImpl::SyncOpenPrevEntry(void** iter, Entry** prev_entry) {
-  *prev_entry = OpenPrevEntryImpl(iter);
-  return (*prev_entry) ? net::OK : net::ERR_FAILED;
-}
-
-void BackendImpl::SyncEndEnumeration(void* iter) {
-  scoped_ptr<Rankings::Iterator> iterator(
-      reinterpret_cast<Rankings::Iterator*>(iter));
-}
-
-void BackendImpl::SyncOnExternalCacheHit(const std::string& key) {
-  if (disabled_)
-    return;
-
-  uint32 hash = base::Hash(key);
-  bool error;
-  EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
-  if (cache_entry) {
-    if (ENTRY_NORMAL == cache_entry->entry()->Data()->state) {
-      UpdateRank(cache_entry, cache_type() == net::SHADER_CACHE);
-    }
-    cache_entry->Release();
-  }
-}
-
-EntryImpl* BackendImpl::OpenEntryImpl(const std::string& key) {
-  if (disabled_)
-    return NULL;
-
-  TimeTicks start = TimeTicks::Now();
-  uint32 hash = base::Hash(key);
-  Trace("Open hash 0x%x", hash);
-
-  bool error;
-  EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
-  if (cache_entry && ENTRY_NORMAL != cache_entry->entry()->Data()->state) {
-    // The entry was already evicted.
-    cache_entry->Release();
-    cache_entry = NULL;
-  }
-
-  int current_size = data_->header.num_bytes / (1024 * 1024);
-  int64 total_hours = stats_.GetCounter(Stats::TIMER) / 120;
-  int64 no_use_hours = stats_.GetCounter(Stats::LAST_REPORT_TIMER) / 120;
-  int64 use_hours = total_hours - no_use_hours;
-
-  if (!cache_entry) {
-    CACHE_UMA(AGE_MS, "OpenTime.Miss", 0, start);
-    CACHE_UMA(COUNTS_10000, "AllOpenBySize.Miss", 0, current_size);
-    CACHE_UMA(HOURS, "AllOpenByTotalHours.Miss", 0, total_hours);
-    CACHE_UMA(HOURS, "AllOpenByUseHours.Miss", 0, use_hours);
-    stats_.OnEvent(Stats::OPEN_MISS);
-    return NULL;
-  }
-
-  eviction_.OnOpenEntry(cache_entry);
-  entry_count_++;
-
-  Trace("Open hash 0x%x end: 0x%x", hash,
-        cache_entry->entry()->address().value());
-  CACHE_UMA(AGE_MS, "OpenTime", 0, start);
-  CACHE_UMA(COUNTS_10000, "AllOpenBySize.Hit", 0, current_size);
-  CACHE_UMA(HOURS, "AllOpenByTotalHours.Hit", 0, total_hours);
-  CACHE_UMA(HOURS, "AllOpenByUseHours.Hit", 0, use_hours);
-  stats_.OnEvent(Stats::OPEN_HIT);
-  SIMPLE_STATS_COUNTER("disk_cache.hit");
-  return cache_entry;
-}
-
-EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) {
-  if (disabled_ || key.empty())
-    return NULL;
-
-  TimeTicks start = TimeTicks::Now();
-  uint32 hash = base::Hash(key);
-  Trace("Create hash 0x%x", hash);
-
-  scoped_refptr<EntryImpl> parent;
-  Addr entry_address(data_->table[hash & mask_]);
-  if (entry_address.is_initialized()) {
-    // We have an entry already. It could be the one we are looking for, or just
-    // a hash conflict.
-    bool error;
-    EntryImpl* old_entry = MatchEntry(key, hash, false, Addr(), &error);
-    if (old_entry)
-      return ResurrectEntry(old_entry);
-
-    EntryImpl* parent_entry = MatchEntry(key, hash, true, Addr(), &error);
-    DCHECK(!error);
-    if (parent_entry) {
-      parent.swap(&parent_entry);
-    } else if (data_->table[hash & mask_]) {
-      // We should have corrected the problem.
-      NOTREACHED();
-      return NULL;
-    }
-  }
-
-  // The general flow is to allocate disk space and initialize the entry data,
-  // followed by saving that to disk, then linking the entry though the index
-  // and finally through the lists. If there is a crash in this process, we may
-  // end up with:
-  // a. Used, unreferenced empty blocks on disk (basically just garbage).
-  // b. Used, unreferenced but meaningful data on disk (more garbage).
-  // c. A fully formed entry, reachable only through the index.
-  // d. A fully formed entry, also reachable through the lists, but still dirty.
-  //
-  // Anything after (b) can be automatically cleaned up. We may consider saving
-  // the current operation (as we do while manipulating the lists) so that we
-  // can detect and cleanup (a) and (b).
-
-  int num_blocks = EntryImpl::NumBlocksForEntry(key.size());
-  if (!block_files_.CreateBlock(BLOCK_256, num_blocks, &entry_address)) {
-    LOG(ERROR) << "Create entry failed " << key.c_str();
-    stats_.OnEvent(Stats::CREATE_ERROR);
-    return NULL;
-  }
-
-  Addr node_address(0);
-  if (!block_files_.CreateBlock(RANKINGS, 1, &node_address)) {
-    block_files_.DeleteBlock(entry_address, false);
-    LOG(ERROR) << "Create entry failed " << key.c_str();
-    stats_.OnEvent(Stats::CREATE_ERROR);
-    return NULL;
-  }
-
-  scoped_refptr<EntryImpl> cache_entry(
-      new EntryImpl(this, entry_address, false));
-  IncreaseNumRefs();
-
-  if (!cache_entry->CreateEntry(node_address, key, hash)) {
-    block_files_.DeleteBlock(entry_address, false);
-    block_files_.DeleteBlock(node_address, false);
-    LOG(ERROR) << "Create entry failed " << key.c_str();
-    stats_.OnEvent(Stats::CREATE_ERROR);
-    return NULL;
-  }
-
-  cache_entry->BeginLogging(net_log_, true);
-
-  // We are not failing the operation; let's add this to the map.
-  open_entries_[entry_address.value()] = cache_entry;
-
-  // Save the entry.
-  cache_entry->entry()->Store();
-  cache_entry->rankings()->Store();
-  IncreaseNumEntries();
-  entry_count_++;
-
-  // Link this entry through the index.
-  if (parent.get()) {
-    parent->SetNextAddress(entry_address);
-  } else {
-    data_->table[hash & mask_] = entry_address.value();
-  }
-
-  // Link this entry through the lists.
-  eviction_.OnCreateEntry(cache_entry);
-
-  CACHE_UMA(AGE_MS, "CreateTime", 0, start);
-  stats_.OnEvent(Stats::CREATE_HIT);
-  SIMPLE_STATS_COUNTER("disk_cache.miss");
-  Trace("create entry hit ");
-  FlushIndex();
-  cache_entry->AddRef();
-  return cache_entry.get();
-}
-
-EntryImpl* BackendImpl::OpenNextEntryImpl(void** iter) {
-  return OpenFollowingEntry(true, iter);
-}
-
-EntryImpl* BackendImpl::OpenPrevEntryImpl(void** iter) {
-  return OpenFollowingEntry(false, iter);
-}
-
 bool BackendImpl::SetMaxSize(int max_bytes) {
   COMPILE_ASSERT(sizeof(max_bytes) == sizeof(max_size_), unsupported_int_model);
   if (max_bytes < 0)
     return false;
 
   // Zero size means use the default.
   if (!max_bytes)
     return true;
 
   // Avoid a DCHECK later on.
   if (max_bytes >= kint32max - kint32max / 10)
     max_bytes = kint32max - kint32max / 10 - 1;
 
   user_flags_ |= kMaxSize;
   max_size_ = max_bytes;
   return true;
 }
 
 void BackendImpl::SetType(net::CacheType type) {
   DCHECK_NE(net::MEMORY_CACHE, type);
   cache_type_ = type;
 }
 
-base::FilePath BackendImpl::GetFileName(Addr address) const {
-  if (!address.is_separate_file() || !address.is_initialized()) {
-    NOTREACHED();
-    return base::FilePath();
-  }
-
-  std::string tmp = base::StringPrintf("f_%06x", address.FileNumber());
-  return path_.AppendASCII(tmp);
-}
-
-MappedFile* BackendImpl::File(Addr address) {
-  if (disabled_)
-    return NULL;
-  return block_files_.GetFile(address);
-}
-
-base::WeakPtr<InFlightBackendIO> BackendImpl::GetBackgroundQueue() {
-  return background_queue_.GetWeakPtr();
-}
-
-bool BackendImpl::CreateExternalFile(Addr* address) {
-  int file_number = data_->header.last_file + 1;
-  Addr file_address(0);
-  bool success = false;
-  for (int i = 0; i < 0x0fffffff; i++, file_number++) {
-    if (!file_address.SetFileNumber(file_number)) {
-      file_number = 1;
-      continue;
-    }
-    base::FilePath name = GetFileName(file_address);
-    int flags = base::PLATFORM_FILE_READ |
-                base::PLATFORM_FILE_WRITE |
-                base::PLATFORM_FILE_CREATE |
-                base::PLATFORM_FILE_EXCLUSIVE_WRITE;
-    base::PlatformFileError error;
-    scoped_refptr<disk_cache::File> file(new disk_cache::File(
-        base::CreatePlatformFile(name, flags, NULL, &error)));
-    if (!file->IsValid()) {
-      if (error != base::PLATFORM_FILE_ERROR_EXISTS) {
-        LOG(ERROR) << "Unable to create file: " << error;
-        return false;
-      }
-      continue;
-    }
-
-    success = true;
-    break;
-  }
-
-  DCHECK(success);
-  if (!success)
-    return false;
-
-  data_->header.last_file = file_number;
-  address->set_value(file_address.value());
-  return true;
-}
-
 bool BackendImpl::CreateBlock(FileType block_type, int block_count,
                              Addr* block_address) {
   return block_files_.CreateBlock(block_type, block_count, block_address);
 }
 
-void BackendImpl::DeleteBlock(Addr block_address, bool deep) {
-  block_files_.DeleteBlock(block_address, deep);
-}
-
-LruData* BackendImpl::GetLruData() {
-  return &data_->header.lru;
-}
-
 void BackendImpl::UpdateRank(EntryImpl* entry, bool modified) {
   if (read_only_ || (!modified && cache_type() == net::SHADER_CACHE))
     return;
   eviction_.UpdateRank(entry, modified);
 }
 
-void BackendImpl::RecoveredEntry(CacheRankingsBlock* rankings) {
-  Addr address(rankings->Data()->contents);
-  EntryImpl* cache_entry = NULL;
-  if (NewEntry(address, &cache_entry)) {
-    STRESS_NOTREACHED();
-    return;
-  }
-
-  uint32 hash = cache_entry->GetHash();
-  cache_entry->Release();
-
-  // Anything on the table means that this entry is there.
-  if (data_->table[hash & mask_])
-    return;
-
-  data_->table[hash & mask_] = address.value();
-  FlushIndex();
-}
-
 void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
   uint32 hash = entry->GetHash();
   std::string key = entry->GetKey();
   Addr entry_addr = entry->entry()->address();
   bool error;
   EntryImpl* parent_entry = MatchEntry(key, hash, true, entry_addr, &error);
   CacheAddr child(entry->GetNextAddress());
 
   Trace("Doom entry 0x%p", entry);
 
@@ skipping 10 matching lines @@
   if (parent_entry) {
     parent_entry->SetNextAddress(Addr(child));
     parent_entry->Release();
   } else if (!error) {
     data_->table[hash & mask_] = child;
   }
 
   FlushIndex();
 }
 
-#if defined(NET_BUILD_STRESS_CACHE)
-
-CacheAddr BackendImpl::GetNextAddr(Addr address) {
-  EntriesMap::iterator it = open_entries_.find(address.value());
-  if (it != open_entries_.end()) {
-    EntryImpl* this_entry = it->second;
-    return this_entry->GetNextAddress();
-  }
-  DCHECK(block_files_.IsValid(address));
-  DCHECK(!address.is_separate_file() && address.file_type() == BLOCK_256);
-
-  CacheEntryBlock entry(File(address), address);
-  CHECK(entry.Load());
-  return entry.Data()->next;
-}
-
-void BackendImpl::NotLinked(EntryImpl* entry) {
-  Addr entry_addr = entry->entry()->address();
-  uint32 i = entry->GetHash() & mask_;
-  Addr address(data_->table[i]);
-  if (!address.is_initialized())
-    return;
-
-  for (;;) {
-    DCHECK(entry_addr.value() != address.value());
-    address.set_value(GetNextAddr(address));
-    if (!address.is_initialized())
-      break;
-  }
-}
-#endif  // NET_BUILD_STRESS_CACHE
-
-// An entry may be linked on the DELETED list for a while after being doomed.
-// This function is called when we want to remove it.
-void BackendImpl::RemoveEntry(EntryImpl* entry) {
-#if defined(NET_BUILD_STRESS_CACHE)
-  NotLinked(entry);
-#endif
-  if (!new_eviction_)
-    return;
-
-  DCHECK_NE(ENTRY_NORMAL, entry->entry()->Data()->state);
-
-  Trace("Remove entry 0x%p", entry);
-  eviction_.OnDestroyEntry(entry);
-  DecreaseNumEntries();
-}
-
 void BackendImpl::OnEntryDestroyBegin(Addr address) {
   EntriesMap::iterator it = open_entries_.find(address.value());
   if (it != open_entries_.end())
     open_entries_.erase(it);
 }
 
 void BackendImpl::OnEntryDestroyEnd() {
   DecreaseNumRefs();
   if (data_->header.num_bytes > max_size_ && !read_only_ &&
       (up_ticks_ > kTrimDelay || user_flags_ & kNoRandom))
     eviction_.TrimCache(false);
 }
 
 EntryImpl* BackendImpl::GetOpenEntry(CacheRankingsBlock* rankings) const {
   DCHECK(rankings->HasData());
   EntriesMap::const_iterator it =
       open_entries_.find(rankings->Data()->contents);
   if (it != open_entries_.end()) {
     // We have this entry in memory.
     return it->second;
   }
 
   return NULL;
 }
 
-int32 BackendImpl::GetCurrentEntryId() const {
-  return data_->header.this_id;
-}
-
 int BackendImpl::MaxFileSize() const {
   return max_size_ / 8;
 }
 
 void BackendImpl::ModifyStorageSize(int32 old_size, int32 new_size) {
   if (disabled_ || old_size == new_size)
     return;
   if (old_size > new_size)
     SubstractStorageSize(old_size - new_size);
   else
@@ skipping 96 matching lines @@
               data_->header.lru.sizes[0] * 100 / data_->header.num_entries);
     CACHE_UMA(PERCENTAGE, "FirstLowUseRatio", 0,
               data_->header.lru.sizes[1] * 100 / data_->header.num_entries);
     CACHE_UMA(PERCENTAGE, "FirstHighUseRatio", 0,
               data_->header.lru.sizes[2] * 100 / data_->header.num_entries);
   }
 
   stats_.ResetRatios();
 }
 
-void BackendImpl::CriticalError(int error) {
-  STRESS_NOTREACHED();
-  LOG(ERROR) << "Critical error found " << error;
-  if (disabled_)
-    return;
-
-  stats_.OnEvent(Stats::FATAL_ERROR);
-  LogStats();
-  ReportError(error);
-
-  // Setting the index table length to an invalid value will force re-creation
-  // of the cache files.
-  data_->header.table_len = 1;
-  disabled_ = true;
-
-  if (!num_refs_)
-    base::MessageLoop::current()->PostTask(
-        FROM_HERE, base::Bind(&BackendImpl::RestartCache, GetWeakPtr(), true));
-}
-
-void BackendImpl::ReportError(int error) {
-  STRESS_DCHECK(!error || error == ERR_PREVIOUS_CRASH ||
-                error == ERR_CACHE_CREATED);
-
-  // We transmit positive numbers, instead of direct error codes.
-  DCHECK_LE(error, 0);
-  CACHE_UMA(CACHE_ERROR, "Error", 0, error * -1);
-}
-
 void BackendImpl::OnEvent(Stats::Counters an_event) {
   stats_.OnEvent(an_event);
 }
 
 void BackendImpl::OnRead(int32 bytes) {
   DCHECK_GE(bytes, 0);
   byte_count_ += bytes;
   if (byte_count_ < 0)
     byte_count_ = kint32max;
 }
@@ skipping 36 matching lines @@
     first_timer_ = false;
     if (ShouldReportAgain())
       ReportStats();
   }
 
   // Save stats to disk at 5 min intervals.
   if (time % 10 == 0)
     StoreStats();
 }
 
-void BackendImpl::IncrementIoCount() {
-  num_pending_io_++;
-}
-
-void BackendImpl::DecrementIoCount() {
-  num_pending_io_--;
-}
-
 void BackendImpl::SetUnitTestMode() {
   user_flags_ |= kUnitTestMode;
   unit_test_ = true;
 }
 
 void BackendImpl::SetUpgradeMode() {
   user_flags_ |= kUpgradeMode;
   read_only_ = true;
 }
 
 void BackendImpl::SetNewEviction() {
   user_flags_ |= kNewEviction;
   new_eviction_ = true;
 }
 
 void BackendImpl::SetFlags(uint32 flags) {
   user_flags_ |= flags;
 }
 
-void BackendImpl::ClearRefCountForTest() {
-  num_refs_ = 0;
-}
-
 int BackendImpl::FlushQueueForTest(const CompletionCallback& callback) {
   background_queue_.FlushQueue(callback);
   return net::ERR_IO_PENDING;
 }
 
-int BackendImpl::RunTaskForTest(const base::Closure& task,
-                                const CompletionCallback& callback) {
-  background_queue_.RunTask(task, callback);
-  return net::ERR_IO_PENDING;
-}
-
 void BackendImpl::TrimForTest(bool empty) {
   eviction_.SetTestMode();
   eviction_.TrimCache(empty);
 }
 
 void BackendImpl::TrimDeletedListForTest(bool empty) {
   eviction_.SetTestMode();
   eviction_.TrimDeletedList(empty);
 }
 
@@ skipping 14 matching lines @@
   if (num_entries != data_->header.num_entries) {
     LOG(ERROR) << "Number of entries mismatch";
 #if !defined(NET_BUILD_STRESS_CACHE)
     return ERR_NUM_ENTRIES_MISMATCH;
 #endif
   }
 
   return CheckAllEntries();
 }
 
-void BackendImpl::FlushIndex() {
-  if (index_ && !disabled_)
-    index_->Flush();
-}
-
 // ------------------------------------------------------------------------
 
 net::CacheType BackendImpl::GetCacheType() const {
   return cache_type_;
 }
 
 int32 BackendImpl::GetEntryCount() const {
   if (!index_ || disabled_)
     return 0;
   // num_entries includes entries already evicted.
   int32 not_deleted = data_->header.num_entries -
                       data_->header.lru.sizes[Rankings::DELETED];
 
   if (not_deleted < 0) {
     NOTREACHED();
     not_deleted = 0;
   }
 
   return not_deleted;
 }
 
-int BackendImpl::OpenEntry(const std::string& key, Entry** entry,
-                           const CompletionCallback& callback) {
-  DCHECK(!callback.is_null());
-  background_queue_.OpenEntry(key, entry, callback);
-  return net::ERR_IO_PENDING;
-}
-
-int BackendImpl::CreateEntry(const std::string& key, Entry** entry,
-                             const CompletionCallback& callback) {
-  DCHECK(!callback.is_null());
-  background_queue_.CreateEntry(key, entry, callback);
-  return net::ERR_IO_PENDING;
-}
-
-int BackendImpl::DoomEntry(const std::string& key,
-                           const CompletionCallback& callback) {
-  DCHECK(!callback.is_null());
-  background_queue_.DoomEntry(key, callback);
-  return net::ERR_IO_PENDING;
-}
-
-int BackendImpl::DoomAllEntries(const CompletionCallback& callback) {
-  DCHECK(!callback.is_null());
-  background_queue_.DoomAllEntries(callback);
-  return net::ERR_IO_PENDING;
-}
-
-int BackendImpl::DoomEntriesBetween(const base::Time initial_time,
-                                    const base::Time end_time,
-                                    const CompletionCallback& callback) {
-  DCHECK(!callback.is_null());
-  background_queue_.DoomEntriesBetween(initial_time, end_time, callback);
-  return net::ERR_IO_PENDING;
-}
-
-int BackendImpl::DoomEntriesSince(const base::Time initial_time,
-                                  const CompletionCallback& callback) {
-  DCHECK(!callback.is_null());
-  background_queue_.DoomEntriesSince(initial_time, callback);
-  return net::ERR_IO_PENDING;
+EntryImpl* BackendImpl::OpenEntryImpl(const std::string& key) {

[gavinp, 2013/06/04 17:02:30]

No method by this name exists in the header; I know this isn't supposed to
compile, but this just causes me a lot of confusion. Why would we want the
header and body to disagree so radically?

[rvargas (doing something else), 2013/06/04 17:31:13]

Because otherwise I would be violating the premise of no code being modified by
this CL.

This method will obviously be renamed (and the signature modified), but the bulk
of the code (of this method) should be used to compare against the
implementation of the new method XXX::OpenEntry.

If I just leave BackendImpl::OpenEntry here (the one that appears on the
header), we'll have a trivial forwarding method instead of the one that actually
provides the implementation, so the whole point of starting from existing code
is lost.

+  if (disabled_)
+    return NULL;
+
+  TimeTicks start = TimeTicks::Now();
+  uint32 hash = base::Hash(key);
+  Trace("Open hash 0x%x", hash);
+
+  bool error;
+  EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
+  if (cache_entry && ENTRY_NORMAL != cache_entry->entry()->Data()->state) {
+    // The entry was already evicted.
+    cache_entry->Release();
+    cache_entry = NULL;
+  }
+
+  int current_size = data_->header.num_bytes / (1024 * 1024);
+  int64 total_hours = stats_.GetCounter(Stats::TIMER) / 120;
+  int64 no_use_hours = stats_.GetCounter(Stats::LAST_REPORT_TIMER) / 120;
+  int64 use_hours = total_hours - no_use_hours;
+
+  if (!cache_entry) {
+    CACHE_UMA(AGE_MS, "OpenTime.Miss", 0, start);
+    CACHE_UMA(COUNTS_10000, "AllOpenBySize.Miss", 0, current_size);
+    CACHE_UMA(HOURS, "AllOpenByTotalHours.Miss", 0, total_hours);
+    CACHE_UMA(HOURS, "AllOpenByUseHours.Miss", 0, use_hours);
+    stats_.OnEvent(Stats::OPEN_MISS);
+    return NULL;
+  }
+
+  eviction_.OnOpenEntry(cache_entry);
+  entry_count_++;
+
+  Trace("Open hash 0x%x end: 0x%x", hash,
+        cache_entry->entry()->address().value());
+  CACHE_UMA(AGE_MS, "OpenTime", 0, start);
+  CACHE_UMA(COUNTS_10000, "AllOpenBySize.Hit", 0, current_size);
+  CACHE_UMA(HOURS, "AllOpenByTotalHours.Hit", 0, total_hours);
+  CACHE_UMA(HOURS, "AllOpenByUseHours.Hit", 0, use_hours);
+  stats_.OnEvent(Stats::OPEN_HIT);
+  SIMPLE_STATS_COUNTER("disk_cache.hit");
+  return cache_entry;
+}
+
+EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) {
+  if (disabled_ || key.empty())
+    return NULL;
+
+  TimeTicks start = TimeTicks::Now();
+  Trace("Create hash 0x%x", hash);
+
+  scoped_refptr<EntryImpl> parent;
+  Addr entry_address(data_->table[hash & mask_]);
+  if (entry_address.is_initialized()) {
+    // We have an entry already. It could be the one we are looking for, or just
+    // a hash conflict.
+    bool error;
+    EntryImpl* old_entry = MatchEntry(key, hash, false, Addr(), &error);
+    if (old_entry)
+      return ResurrectEntry(old_entry);
+
+    EntryImpl* parent_entry = MatchEntry(key, hash, true, Addr(), &error);
+    DCHECK(!error);
+    if (parent_entry) {
+      parent.swap(&parent_entry);
+    } else if (data_->table[hash & mask_]) {
+      // We should have corrected the problem.
+      NOTREACHED();
+      return NULL;
+    }
+  }
+
+  // The general flow is to allocate disk space and initialize the entry data,
+  // followed by saving that to disk, then linking the entry though the index
+  // and finally through the lists. If there is a crash in this process, we may
+  // end up with:
+  // a. Used, unreferenced empty blocks on disk (basically just garbage).
+  // b. Used, unreferenced but meaningful data on disk (more garbage).
+  // c. A fully formed entry, reachable only through the index.
+  // d. A fully formed entry, also reachable through the lists, but still dirty.
+  //
+  // Anything after (b) can be automatically cleaned up. We may consider saving
+  // the current operation (as we do while manipulating the lists) so that we
+  // can detect and cleanup (a) and (b).
+
+  int num_blocks = EntryImpl::NumBlocksForEntry(key.size());
+  if (!block_files_.CreateBlock(BLOCK_256, num_blocks, &entry_address)) {
+    LOG(ERROR) << "Create entry failed " << key.c_str();
+    stats_.OnEvent(Stats::CREATE_ERROR);
+    return NULL;
+  }
+
+  Addr node_address(0);
+  if (!block_files_.CreateBlock(RANKINGS, 1, &node_address)) {
+    block_files_.DeleteBlock(entry_address, false);
+    LOG(ERROR) << "Create entry failed " << key.c_str();
+    stats_.OnEvent(Stats::CREATE_ERROR);
+    return NULL;
+  }
+
+  scoped_refptr<EntryImpl> cache_entry(
+      new EntryImpl(this, entry_address, false));
+  IncreaseNumRefs();
+
+  if (!cache_entry->CreateEntry(node_address, key, hash)) {
+    block_files_.DeleteBlock(entry_address, false);
+    block_files_.DeleteBlock(node_address, false);
+    LOG(ERROR) << "Create entry failed " << key.c_str();
+    stats_.OnEvent(Stats::CREATE_ERROR);
+    return NULL;
+  }
+
+  cache_entry->BeginLogging(net_log_, true);
+
+  // We are not failing the operation; let's add this to the map.
+  open_entries_[entry_address.value()] = cache_entry;
+
+  // Save the entry.
+  cache_entry->entry()->Store();
+  cache_entry->rankings()->Store();
+  IncreaseNumEntries();
+  entry_count_++;
+
+  // Link this entry through the index.
+  if (parent.get()) {
+    parent->SetNextAddress(entry_address);
+  } else {
+    data_->table[hash & mask_] = entry_address.value();
+  }
+
+  // Link this entry through the lists.
+  eviction_.OnCreateEntry(cache_entry);
+
+  CACHE_UMA(AGE_MS, "CreateTime", 0, start);
+  stats_.OnEvent(Stats::CREATE_HIT);
+  SIMPLE_STATS_COUNTER("disk_cache.miss");
+  Trace("create entry hit ");
+  FlushIndex();
+  cache_entry->AddRef();
+  return cache_entry.get();
+}
+
+int BackendImpl::SyncDoomEntry(const std::string& key) {
+  if (disabled_)
+    return net::ERR_FAILED;
+
+  EntryImpl* entry = OpenEntryImpl(key);
+  if (!entry)
+    return net::ERR_FAILED;
+
+  entry->DoomImpl();
+  entry->Release();
+  return net::OK;
+}
+
+int BackendImpl::SyncDoomAllEntries() {
+  // This is not really an error, but it is an interesting condition.
+  ReportError(ERR_CACHE_DOOMED);
+  stats_.OnEvent(Stats::DOOM_CACHE);
+  if (!num_refs_) {
+    RestartCache(false);
+    return disabled_ ? net::ERR_FAILED : net::OK;
+  } else {
+    if (disabled_)
+      return net::ERR_FAILED;
+
+    eviction_.TrimCache(true);
+    return net::OK;
+  }
+}
+
+int BackendImpl::SyncDoomEntriesBetween(const base::Time initial_time,
+                                        const base::Time end_time) {
+  DCHECK_NE(net::APP_CACHE, cache_type_);
+  if (end_time.is_null())
+    return SyncDoomEntriesSince(initial_time);
+
+  DCHECK(end_time >= initial_time);
+
+  if (disabled_)
+    return net::ERR_FAILED;
+
+  EntryImpl* node;
+  void* iter = NULL;
+  EntryImpl* next = OpenNextEntryImpl(&iter);
+  if (!next)
+    return net::OK;
+
+  while (next) {
+    node = next;
+    next = OpenNextEntryImpl(&iter);
+
+    if (node->GetLastUsed() >= initial_time &&
+        node->GetLastUsed() < end_time) {
+      node->DoomImpl();
+    } else if (node->GetLastUsed() < initial_time) {
+      if (next)
+        next->Release();
+      next = NULL;
+      SyncEndEnumeration(iter);
+    }
+
+    node->Release();
+  }
+
+  return net::OK;
+}
+
+// We use OpenNextEntryImpl to retrieve elements from the cache, until we get
+// entries that are too old.
+int BackendImpl::SyncDoomEntriesSince(const base::Time initial_time) {
+  DCHECK_NE(net::APP_CACHE, cache_type_);
+  if (disabled_)
+    return net::ERR_FAILED;
+
+  stats_.OnEvent(Stats::DOOM_RECENT);
+  for (;;) {
+    void* iter = NULL;
+    EntryImpl* entry = OpenNextEntryImpl(&iter);
+    if (!entry)
+      return net::OK;
+
+    if (initial_time > entry->GetLastUsed()) {
+      entry->Release();
+      SyncEndEnumeration(iter);
+      return net::OK;
+    }
+
+    entry->DoomImpl();
+    entry->Release();
+    SyncEndEnumeration(iter);  // Dooming the entry invalidates the iterator.
+  }
 }
 
 int BackendImpl::OpenNextEntry(void** iter, Entry** next_entry,
                                const CompletionCallback& callback) {
   DCHECK(!callback.is_null());
   background_queue_.OpenNextEntry(iter, next_entry, callback);
   return net::ERR_IO_PENDING;
 }
 
 void BackendImpl::EndEnumeration(void** iter) {
@@ skipping 19 matching lines @@
   item.second = base::StringPrintf("%d", max_size_);
   stats->push_back(item);
 
   item.first = "Current size";
   item.second = base::StringPrintf("%d", data_->header.num_bytes);
   stats->push_back(item);
 
   stats_.GetItems(stats);
 }
 
-void BackendImpl::OnExternalCacheHit(const std::string& key) {
-  background_queue_.OnExternalCacheHit(key);
+void BackendImpl::SyncOnExternalCacheHit(const std::string& key) {
+  if (disabled_)
+    return;
+
+  uint32 hash = base::Hash(key);
+  bool error;
+  EntryImpl* cache_entry = MatchEntry(key, hash, false, Addr(), &error);
+  if (cache_entry) {
+    if (ENTRY_NORMAL == cache_entry->entry()->Data()->state) {
+      UpdateRank(cache_entry, cache_type() == net::SHADER_CACHE);
+    }
+    cache_entry->Release();
+  }
 }
 
 // ------------------------------------------------------------------------
 
-// We just created a new file so we're going to write the header and set the
-// file length to include the hash table (zero filled).
-bool BackendImpl::CreateBackingStore(disk_cache::File* file) {
-  AdjustMaxCacheSize(0);
-
-  IndexHeader header;
-  header.table_len = DesiredIndexTableLen(max_size_);
-
-  // We need file version 2.1 for the new eviction algorithm.
-  if (new_eviction_)
-    header.version = 0x20001;
-
-  header.create_time = Time::Now().ToInternalValue();
-
-  if (!file->Write(&header, sizeof(header), 0))
-    return false;
-
-  return file->SetLength(GetIndexSize(header.table_len));
-}
-
-bool BackendImpl::InitBackingStore(bool* file_created) {
-  if (!file_util::CreateDirectory(path_))
-    return false;
-
-  base::FilePath index_name = path_.AppendASCII(kIndexName);
-
-  int flags = base::PLATFORM_FILE_READ |
-              base::PLATFORM_FILE_WRITE |
-              base::PLATFORM_FILE_OPEN_ALWAYS |
-              base::PLATFORM_FILE_EXCLUSIVE_WRITE;
-  scoped_refptr<disk_cache::File> file(new disk_cache::File(
-      base::CreatePlatformFile(index_name, flags, file_created, NULL)));
-
-  if (!file->IsValid())
-    return false;
-
-  bool ret = true;
-  if (*file_created)
-    ret = CreateBackingStore(file);
-
-  file = NULL;
-  if (!ret)
-    return false;
-
-  index_ = new MappedFile();
-  data_ = reinterpret_cast<Index*>(index_->Init(index_name, 0));
-  if (!data_) {
-    LOG(ERROR) << "Unable to map Index file";
-    return false;
-  }
-
-  if (index_->GetLength() < sizeof(Index)) {
-    // We verify this again on CheckIndex() but it's easier to make sure now
-    // that the header is there.
-    LOG(ERROR) << "Corrupt Index file";
-    return false;
-  }
-
-  return true;
-}
-
 // The maximum cache size will be either set explicitly by the caller, or
 // calculated by this code.
 void BackendImpl::AdjustMaxCacheSize(int table_len) {
   if (max_size_)
     return;
 
   // If table_len is provided, the index file exists.
   DCHECK(!table_len || data_->header.magic);
 
   // The user is not setting the size, let's figure it out.
@@ skipping 117 matching lines @@
   data_->header.crash = 0;
   index_->Flush();
   index_ = NULL;
   data_ = NULL;
   block_files_.CloseFiles();
   rankings_.Reset();
   init_ = false;
   restarted_ = true;
 }
 
+void BackendImpl::CleanupCache() {
+  Trace("Backend Cleanup");
+  eviction_.Stop();
+  timer_.reset();
+
+  if (init_) {
+    StoreStats();
+    if (data_)
+      data_->header.crash = 0;
+
+    if (user_flags_ & kNoRandom) {
+      // This is a net_unittest, verify that we are not 'leaking' entries.
+      File::WaitForPendingIO(&num_pending_io_);
+      DCHECK(!num_refs_);
+    } else {
+      File::DropPendingIO();
+    }
+  }
+  block_files_.CloseFiles();
+  FlushIndex();
+  index_ = NULL;
+  ptr_factory_.InvalidateWeakPtrs();
+  done_.Signal();
+}
+
 int BackendImpl::NewEntry(Addr address, EntryImpl** entry) {
   EntriesMap::iterator it = open_entries_.find(address.value());
   if (it != open_entries_.end()) {
     // Easy job. This entry is already in memory.
     EntryImpl* this_entry = it->second;
     this_entry->AddRef();
     *entry = this_entry;
     return 0;
   }
 
@@ skipping 57 matching lines @@
           address.value());
   }
 
   open_entries_[address.value()] = cache_entry;
 
   cache_entry->BeginLogging(net_log_, false);
   cache_entry.swap(entry);
   return 0;
 }
 
-EntryImpl* BackendImpl::MatchEntry(const std::string& key, uint32 hash,
-                                   bool find_parent, Addr entry_addr,
-                                   bool* match_error) {
-  Addr address(data_->table[hash & mask_]);
-  scoped_refptr<EntryImpl> cache_entry, parent_entry;
-  EntryImpl* tmp = NULL;
-  bool found = false;
-  std::set<CacheAddr> visited;
-  *match_error = false;
-
-  for (;;) {
-    if (disabled_)
-      break;
-
-    if (visited.find(address.value()) != visited.end()) {
-      // It's possible for a buggy version of the code to write a loop. Just
-      // break it.
-      Trace("Hash collision loop 0x%x", address.value());
-      address.set_value(0);
-      parent_entry->SetNextAddress(address);
-    }
-    visited.insert(address.value());
-
-    if (!address.is_initialized()) {
-      if (find_parent)
-        found = true;
-      break;
-    }
-
-    int error = NewEntry(address, &tmp);
-    cache_entry.swap(&tmp);
-
-    if (error || cache_entry->dirty()) {
-      // This entry is dirty on disk (it was not properly closed): we cannot
-      // trust it.
-      Addr child(0);
-      if (!error)
-        child.set_value(cache_entry->GetNextAddress());
-
-      if (parent_entry) {
-        parent_entry->SetNextAddress(child);
-        parent_entry = NULL;
-      } else {
-        data_->table[hash & mask_] = child.value();
-      }
-
-      Trace("MatchEntry dirty %d 0x%x 0x%x", find_parent, entry_addr.value(),
-            address.value());
-
-      if (!error) {
-        // It is important to call DestroyInvalidEntry after removing this
-        // entry from the table.
-        DestroyInvalidEntry(cache_entry);
-        cache_entry = NULL;
-      } else {
-        Trace("NewEntry failed on MatchEntry 0x%x", address.value());
-      }
-
-      // Restart the search.
-      address.set_value(data_->table[hash & mask_]);
-      visited.clear();
-      continue;
-    }
-
-    DCHECK_EQ(hash & mask_, cache_entry->entry()->Data()->hash & mask_);
-    if (cache_entry->IsSameEntry(key, hash)) {
-      if (!cache_entry->Update())
-        cache_entry = NULL;
-      found = true;
-      if (find_parent && entry_addr.value() != address.value()) {
-        Trace("Entry not on the index 0x%x", address.value());
-        *match_error = true;
-        parent_entry = NULL;
-      }
-      break;
-    }
-    if (!cache_entry->Update())
-      cache_entry = NULL;
-    parent_entry = cache_entry;
-    cache_entry = NULL;
-    if (!parent_entry)
-      break;
-
-    address.set_value(parent_entry->GetNextAddress());
-  }
-
-  if (parent_entry && (!find_parent || !found))
-    parent_entry = NULL;
-
-  if (find_parent && entry_addr.is_initialized() && !cache_entry) {
-    *match_error = true;
-    parent_entry = NULL;
-  }
-
-  if (cache_entry && (find_parent || !found))
-    cache_entry = NULL;
-
-  find_parent ? parent_entry.swap(&tmp) : cache_entry.swap(&tmp);
-  FlushIndex();
-  return tmp;
-}
-
 // This is the actual implementation for OpenNextEntry and OpenPrevEntry.
 EntryImpl* BackendImpl::OpenFollowingEntry(bool forward, void** iter) {
   if (disabled_)
     return NULL;
 
   DCHECK(iter);
 
   const int kListsToSearch = 3;
   scoped_refptr<EntryImpl> entries[kListsToSearch];
   scoped_ptr<Rankings::Iterator> iterator(
@@ skipping 58 matching lines @@
   } else {
     next_entry = entries[oldest].get();
     iterator->list = static_cast<Rankings::List>(oldest);
   }
 
   *iter = iterator.release();
   next_entry->AddRef();
   return next_entry;
 }
 
-bool BackendImpl::OpenFollowingEntryFromList(bool forward, Rankings::List list,
-                                             CacheRankingsBlock** from_entry,
-                                             EntryImpl** next_entry) {
-  if (disabled_)
-    return false;
-
-  if (!new_eviction_ && Rankings::NO_USE != list)
-    return false;
-
-  Rankings::ScopedRankingsBlock rankings(&rankings_, *from_entry);
-  CacheRankingsBlock* next_block = forward ?
-      rankings_.GetNext(rankings.get(), list) :
-      rankings_.GetPrev(rankings.get(), list);
-  Rankings::ScopedRankingsBlock next(&rankings_, next_block);
-  *from_entry = NULL;
-
-  *next_entry = GetEnumeratedEntry(next.get(), list);
-  if (!*next_entry)
-    return false;
-
-  *from_entry = next.release();
-  return true;
+void BackendImpl::AddStorageSize(int32 bytes) {
+  data_->header.num_bytes += bytes;
+  DCHECK_GE(data_->header.num_bytes, 0);
 }
 
-EntryImpl* BackendImpl::GetEnumeratedEntry(CacheRankingsBlock* next,
-                                           Rankings::List list) {
-  if (!next || disabled_)
-    return NULL;
+void BackendImpl::SubstractStorageSize(int32 bytes) {
+  data_->header.num_bytes -= bytes;
+  DCHECK_GE(data_->header.num_bytes, 0);
+}
 
-  EntryImpl* entry;
-  int rv = NewEntry(Addr(next->Data()->contents), &entry);
-  if (rv) {
-    STRESS_NOTREACHED();
-    rankings_.Remove(next, list, false);
-    if (rv == ERR_INVALID_ADDRESS) {
-      // There is nothing linked from the index. Delete the rankings node.
-      DeleteBlock(next->address(), true);
-    }
-    return NULL;
+void BackendImpl::IncreaseNumRefs() {
+  num_refs_++;
+  if (max_refs_ < num_refs_)
+    max_refs_ = num_refs_;
+}
+
+void BackendImpl::DecreaseNumRefs() {
+  DCHECK(num_refs_);
+  num_refs_--;
+
+  if (!num_refs_ && disabled_)
+    base::MessageLoop::current()->PostTask(
+        FROM_HERE, base::Bind(&BackendImpl::RestartCache, GetWeakPtr(), true));
+}
+
+void BackendImpl::IncreaseNumEntries() {
+  data_->header.num_entries++;
+  DCHECK_GT(data_->header.num_entries, 0);
+}
+
+void BackendImpl::DecreaseNumEntries() {
+  data_->header.num_entries--;
+  if (data_->header.num_entries < 0) {
+    NOTREACHED();
+    data_->header.num_entries = 0;
+  }
+}
+
+int BackendImpl::SyncInit() {
+#if defined(NET_BUILD_STRESS_CACHE)
+  // Start evictions right away.
+  up_ticks_ = kTrimDelay * 2;
+#endif
+  DCHECK(!init_);
+  if (init_)
+    return net::ERR_FAILED;
+
+  bool create_files = false;
+  if (!InitBackingStore(&create_files)) {
+    ReportError(ERR_STORAGE_ERROR);
+    return net::ERR_FAILED;
   }
 
-  if (entry->dirty()) {
-    // We cannot trust this entry.
-    InternalDoomEntry(entry);
-    entry->Release();
-    return NULL;
+  num_refs_ = num_pending_io_ = max_refs_ = 0;
+  entry_count_ = byte_count_ = 0;
+
+  if (!restarted_) {
+    buffer_bytes_ = 0;
+    trace_object_ = TraceObject::GetTraceObject();
+    // Create a recurrent timer of 30 secs.
+    int timer_delay = unit_test_ ? 1000 : 30000;
+    timer_.reset(new base::RepeatingTimer<BackendImpl>());
+    timer_->Start(FROM_HERE, TimeDelta::FromMilliseconds(timer_delay), this,
+                  &BackendImpl::OnStatsTimer);
   }
 
-  if (!entry->Update()) {
-    STRESS_NOTREACHED();
-    entry->Release();
-    return NULL;
+  init_ = true;
+  Trace("Init");
+
+  if (data_->header.experiment != NO_EXPERIMENT &&
+      cache_type_ != net::DISK_CACHE) {
+    // No experiment for other caches.
+    return net::ERR_FAILED;
   }
 
-  // Note that it is unfortunate (but possible) for this entry to be clean, but
-  // not actually the real entry. In other words, we could have lost this entry
-  // from the index, and it could have been replaced with a newer one. It's not
-  // worth checking that this entry is "the real one", so we just return it and
-  // let the enumeration continue; this entry will be evicted at some point, and
-  // the regular path will work with the real entry. With time, this problem
-  // will disasappear because this scenario is just a bug.
+  if (!(user_flags_ & kNoRandom)) {
+    // The unit test controls directly what to test.
+    new_eviction_ = (cache_type_ == net::DISK_CACHE);
+  }
 
-  // Make sure that we save the key for later.
-  entry->GetKey();
+  if (!CheckIndex()) {
+    ReportError(ERR_INIT_FAILED);
+    return net::ERR_FAILED;
+  }
 
-  return entry;
+  if (!restarted_ && (create_files || !data_->header.num_entries))
+    ReportError(ERR_CACHE_CREATED);
+
+  if (!(user_flags_ & kNoRandom) && cache_type_ == net::DISK_CACHE &&
+      !InitExperiment(&data_->header, create_files)) {
+    return net::ERR_FAILED;
+  }
+
+  // We don't care if the value overflows. The only thing we care about is that
+  // the id cannot be zero, because that value is used as "not dirty".
+  // Increasing the value once per second gives us many years before we start
+  // having collisions.
+  data_->header.this_id++;
+  if (!data_->header.this_id)
+    data_->header.this_id++;
+
+  bool previous_crash = (data_->header.crash != 0);
+  data_->header.crash = 1;
+
+  if (!block_files_.Init(create_files))
+    return net::ERR_FAILED;
+
+  // We want to minimize the changes to cache for an AppCache.
+  if (cache_type() == net::APP_CACHE) {
+    DCHECK(!new_eviction_);
+    read_only_ = true;
+  } else if (cache_type() == net::SHADER_CACHE) {
+    DCHECK(!new_eviction_);
+  }
+
+  eviction_.Init(this);
+
+  // stats_ and rankings_ may end up calling back to us so we better be enabled.
+  disabled_ = false;
+  if (!InitStats())
+    return net::ERR_FAILED;
+
+  disabled_ = !rankings_.Init(this, new_eviction_);
+
+#if defined(STRESS_CACHE_EXTENDED_VALIDATION)
+  trace_object_->EnableTracing(false);
+  int sc = SelfCheck();
+  if (sc < 0 && sc != ERR_NUM_ENTRIES_MISMATCH)
+    NOTREACHED();
+  trace_object_->EnableTracing(true);
+#endif
+
+  if (previous_crash) {
+    ReportError(ERR_PREVIOUS_CRASH);
+  } else if (!restarted_) {
+    ReportError(ERR_NO_ERROR);
+  }
+
+  FlushIndex();
+
+  return disabled_ ? net::ERR_FAILED : net::OK;
 }
 
 EntryImpl* BackendImpl::ResurrectEntry(EntryImpl* deleted_entry) {
   if (ENTRY_NORMAL == deleted_entry->entry()->Data()->state) {
     deleted_entry->Release();
     stats_.OnEvent(Stats::CREATE_MISS);
     Trace("create entry miss ");
     return NULL;
   }
 
   // We are attempting to create an entry and found out that the entry was
   // previously deleted.
 
   eviction_.OnCreateEntry(deleted_entry);
   entry_count_++;
 
   stats_.OnEvent(Stats::RESURRECT_HIT);
   Trace("Resurrect entry hit ");
   return deleted_entry;
 }
 
-void BackendImpl::DestroyInvalidEntry(EntryImpl* entry) {
-  LOG(WARNING) << "Destroying invalid entry.";
-  Trace("Destroying invalid entry 0x%p", entry);
+EntryImpl* BackendImpl::CreateEntryImpl(const std::string& key) {
+  if (disabled_ || key.empty())
+    return NULL;
 
-  entry->SetPointerForInvalidEntry(GetCurrentEntryId());
+  TimeTicks start = TimeTicks::Now();
+  Trace("Create hash 0x%x", hash);
 
-  eviction_.OnDoomEntry(entry);
-  entry->InternalDoom();
+  scoped_refptr<EntryImpl> parent;
+  Addr entry_address(data_->table[hash & mask_]);
+  if (entry_address.is_initialized()) {
+    // We have an entry already. It could be the one we are looking for, or just
+    // a hash conflict.
+    bool error;
+    EntryImpl* old_entry = MatchEntry(key, hash, false, Addr(), &error);
+    if (old_entry)
+      return ResurrectEntry(old_entry);
 
-  if (!new_eviction_)
-    DecreaseNumEntries();
-  stats_.OnEvent(Stats::INVALID_ENTRY);
-}
+    EntryImpl* parent_entry = MatchEntry(key, hash, true, Addr(), &error);
+    DCHECK(!error);
+    if (parent_entry) {
+      parent.swap(&parent_entry);
+    } else if (data_->table[hash & mask_]) {
+      // We should have corrected the problem.
+      NOTREACHED();
+      return NULL;
+    }
+  }
 
-void BackendImpl::AddStorageSize(int32 bytes) {
-  data_->header.num_bytes += bytes;
-  DCHECK_GE(data_->header.num_bytes, 0);
-}
+  // The general flow is to allocate disk space and initialize the entry data,
+  // followed by saving that to disk, then linking the entry though the index
+  // and finally through the lists. If there is a crash in this process, we may
+  // end up with:
+  // a. Used, unreferenced empty blocks on disk (basically just garbage).
+  // b. Used, unreferenced but meaningful data on disk (more garbage).
+  // c. A fully formed entry, reachable only through the index.
+  // d. A fully formed entry, also reachable through the lists, but still dirty.
+  //
+  // Anything after (b) can be automatically cleaned up. We may consider saving
+  // the current operation (as we do while manipulating the lists) so that we
+  // can detect and cleanup (a) and (b).
 
-void BackendImpl::SubstractStorageSize(int32 bytes) {
-  data_->header.num_bytes -= bytes;
-  DCHECK_GE(data_->header.num_bytes, 0);
-}
+  int num_blocks = EntryImpl::NumBlocksForEntry(key.size());
+  if (!block_files_.CreateBlock(BLOCK_256, num_blocks, &entry_address)) {
+    LOG(ERROR) << "Create entry failed " << key.c_str();
+    stats_.OnEvent(Stats::CREATE_ERROR);
+    return NULL;
+  }
 
-void BackendImpl::IncreaseNumRefs() {
-  num_refs_++;
-  if (max_refs_ < num_refs_)
-    max_refs_ = num_refs_;
-}
+  Addr node_address(0);
+  if (!block_files_.CreateBlock(RANKINGS, 1, &node_address)) {
+    block_files_.DeleteBlock(entry_address, false);
+    LOG(ERROR) << "Create entry failed " << key.c_str();
+    stats_.OnEvent(Stats::CREATE_ERROR);
+    return NULL;
+  }
 
-void BackendImpl::DecreaseNumRefs() {
-  DCHECK(num_refs_);
-  num_refs_--;
+  scoped_refptr<EntryImpl> cache_entry(
+      new EntryImpl(this, entry_address, false));
+  IncreaseNumRefs();
 
-  if (!num_refs_ && disabled_)
-    base::MessageLoop::current()->PostTask(
-        FROM_HERE, base::Bind(&BackendImpl::RestartCache, GetWeakPtr(), true));
-}
+  if (!cache_entry->CreateEntry(node_address, key, hash)) {
+    block_files_.DeleteBlock(entry_address, false);
+    block_files_.DeleteBlock(node_address, false);
+    LOG(ERROR) << "Create entry failed " << key.c_str();
+    stats_.OnEvent(Stats::CREATE_ERROR);
+    return NULL;
+  }
 
-void BackendImpl::IncreaseNumEntries() {
-  data_->header.num_entries++;
-  DCHECK_GT(data_->header.num_entries, 0);
-}
+  cache_entry->BeginLogging(net_log_, true);
 
-void BackendImpl::DecreaseNumEntries() {
-  data_->header.num_entries--;
-  if (data_->header.num_entries < 0) {
-    NOTREACHED();
-    data_->header.num_entries = 0;
+  // We are not failing the operation; let's add this to the map.
+  open_entries_[entry_address.value()] = cache_entry;
+
+  // Save the entry.
+  cache_entry->entry()->Store();
+  cache_entry->rankings()->Store();
+  IncreaseNumEntries();
+  entry_count_++;
+
+  // Link this entry through the index.
+  if (parent.get()) {
+    parent->SetNextAddress(entry_address);
+  } else {
+    data_->table[hash & mask_] = entry_address.value();
   }
+
+  // Link this entry through the lists.
+  eviction_.OnCreateEntry(cache_entry);
+
+  CACHE_UMA(AGE_MS, "CreateTime", 0, start);
+  stats_.OnEvent(Stats::CREATE_HIT);
+  SIMPLE_STATS_COUNTER("disk_cache.miss");
+  Trace("create entry hit ");
+  FlushIndex();
+  cache_entry->AddRef();
+  return cache_entry.get();
 }
 
 void BackendImpl::LogStats() {
   StatsItems stats;
   GetStats(&stats);
 
   for (size_t index = 0; index < stats.size(); index++)
     VLOG(1) << stats[index].first << ": " << stats[index].second;
 }
 
@@ skipping 96 matching lines @@
               data_->header.lru.sizes[4] * 100 / data_->header.num_entries);
   }
 
   stats_.ResetRatios();
   stats_.SetCounter(Stats::TRIM_ENTRY, 0);
 
   if (cache_type_ == net::DISK_CACHE)
     block_files_.ReportStats();
 }
 
-void BackendImpl::UpgradeTo2_1() {
-  // 2.1 is basically the same as 2.0, except that new fields are actually
-  // updated by the new eviction algorithm.
-  DCHECK(0x20000 == data_->header.version);
-  data_->header.version = 0x20001;
-  data_->header.lru.sizes[Rankings::NO_USE] = data_->header.num_entries;
+void BackendImpl::ReportError(int error) {
+  STRESS_DCHECK(!error || error == ERR_PREVIOUS_CRASH ||
+                error == ERR_CACHE_CREATED);
+
+  // We transmit positive numbers, instead of direct error codes.
+  DCHECK_LE(error, 0);
+  CACHE_UMA(CACHE_ERROR, "Error", 0, error * -1);
 }
 
 bool BackendImpl::CheckIndex() {
   DCHECK(data_);
 
   size_t current_size = index_->GetLength();
   if (current_size < sizeof(Index)) {
     LOG(ERROR) << "Corrupt Index file";
     return false;
   }
@@ skipping 122 matching lines @@
     if (total_memory > kMaxBuffersSize || total_memory <= 0)
       total_memory = kMaxBuffersSize;
 
     done = true;
   }
 
   return static_cast<int>(total_memory);
 }
 
 }  // namespace disk_cache