Disk cache v3 ref2

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 "net/disk_cache/v3/backend_impl_v3.h"
 
 #include "base/bind.h"
 #include "base/bind_helpers.h"
 #include "base/file_util.h"
 #include "base/files/file_path.h"
 #include "base/hash.h"
 #include "base/message_loop/message_loop.h"
 #include "base/metrics/field_trial.h"
 #include "base/metrics/histogram.h"
 #include "base/metrics/stats_counters.h"
 #include "base/rand_util.h"
 #include "base/strings/string_util.h"
 #include "base/strings/stringprintf.h"
 #include "base/sys_info.h"
 #include "base/threading/thread_restrictions.h"
+#include "base/threading/worker_pool.h"
 #include "base/time/time.h"
 #include "base/timer/timer.h"
 #include "net/base/net_errors.h"
-#include "net/disk_cache/cache_util.h"
-#include "net/disk_cache/entry_impl.h"
+#include "net/base/io_buffer.h"
 #include "net/disk_cache/errors.h"
 #include "net/disk_cache/experiments.h"
 #include "net/disk_cache/file.h"
+#include "net/disk_cache/storage_block-inl.h"
+#include "net/disk_cache/v3/backend_worker.h"
+#include "net/disk_cache/v3/backend_work_item.h"
+#include "net/disk_cache/v3/disk_format_v3.h"
+#include "net/disk_cache/v3/entry_impl_v3.h"
+#include "net/disk_cache/v3/index_table.h"
 
 // This has to be defined before including histogram_macros.h from this file.
 #define NET_DISK_CACHE_BACKEND_IMPL_CC_
 #include "net/disk_cache/histogram_macros.h"
 
 using base::Time;
 using base::TimeDelta;
 using base::TimeTicks;
 
 namespace {
 
-const char* kIndexName = "index";
-
 // Seems like ~240 MB correspond to less than 50k entries for 99% of the people.
 // Note that the actual target is to keep the index table load factor under 55%
 // for most users.
 const int k64kEntriesStore = 240 * 1000 * 1000;
 const int kBaseTableLen = 64 * 1024;
 const int kDefaultCacheSize = 80 * 1024 * 1024;
 
 // Avoid trimming the cache for the first 5 minutes (10 timer ticks).
 const int kTrimDelay = 10;
+const int kTimerSeconds = 30;
+
+const size_t kMaxKeySize = 64 * 1024;
 
 int DesiredIndexTableLen(int32 storage_size) {
   if (storage_size <= k64kEntriesStore)
     return kBaseTableLen;
   if (storage_size <= k64kEntriesStore * 2)
     return kBaseTableLen * 2;
   if (storage_size <= k64kEntriesStore * 4)
     return kBaseTableLen * 4;
   if (storage_size <= k64kEntriesStore * 8)
     return kBaseTableLen * 8;
 
   // The biggest storage_size for int32 requires a 4 MB table.
   return kBaseTableLen * 16;
 }
 
 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;
+size_t GetIndexBitmapSize(int table_len) {
+  DCHECK_LT(table_len, 1 << 22);
+  size_t base_bits = disk_cache::kBaseBitmapBytes * 8;
+  if (table_len < static_cast<int>(base_bits))
+    return sizeof(disk_cache::IndexBitmap);
+
+  size_t num_pages = (table_len / 8) - disk_cache::kBaseBitmapBytes;
+  num_pages = (num_pages + 4095) / 4096;
+  return sizeof(disk_cache::IndexHeaderV3) + num_pages * 4096;
 }
 
 }  // namespace
 
 // ------------------------------------------------------------------------
 
 namespace disk_cache {
 
-BackendImpl::BackendImpl(const base::FilePath& path,
-                         base::MessageLoopProxy* cache_thread,
-                         net::NetLog* net_log)
-    : background_queue_(this, cache_thread),
+// Exported by disk_cache/backend_impl.cc
+// Returns the preferred max cache size given the available disk space.
+NET_EXPORT_PRIVATE int PreferedCacheSize(int64 available);
+
+BackendImplV3::BackendImplV3(const base::FilePath& path,
+                             base::MessageLoopProxy* cache_thread,
+                             net::NetLog* net_log)
+    : index_(this),
       path_(path),
-      block_files_(path),
-      mask_(0),
+      block_files_(this),
       max_size_(0),
       up_ticks_(0),
+      test_seconds_(0),
       cache_type_(net::DISK_CACHE),
       uma_report_(0),
       user_flags_(0),
       init_(false),
       restarted_(false),
-      unit_test_(false),
       read_only_(false),
       disabled_(false),
-      new_eviction_(false),
+      lru_eviction_(true),
       first_timer_(true),
       user_load_(false),
+      growing_index_(false),
+      growing_files_(false),
       net_log_(net_log),
-      done_(true, false),
+      cache_thread_(cache_thread),
       ptr_factory_(this) {
 }
 
-BackendImpl::BackendImpl(const base::FilePath& path,
-                         uint32 mask,
-                         base::MessageLoopProxy* cache_thread,
-                         net::NetLog* net_log)
-    : background_queue_(this, cache_thread),
-      path_(path),
-      block_files_(path),
-      mask_(mask),
-      max_size_(0),
-      up_ticks_(0),
-      cache_type_(net::DISK_CACHE),
-      uma_report_(0),
-      user_flags_(kMask),
-      init_(false),
-      restarted_(false),
-      unit_test_(false),
-      read_only_(false),
-      disabled_(false),
-      new_eviction_(false),
-      first_timer_(true),
-      user_load_(false),
-      net_log_(net_log),
-      done_(true, false),
-      ptr_factory_(this) {
+BackendImplV3::~BackendImplV3() {
+  CleanupCache();
 }
 
-BackendImpl::~BackendImpl() {
-  if (user_flags_ & kNoRandom) {
-    // This is a unit test, so we want to be strict about not leaking entries
-    // and completing all the work.
-    background_queue_.WaitForPendingIO();
-  } else {
-    // This is most likely not a test, so we want to do as little work as
-    // possible at this time, at the price of leaving dirty entries behind.
-    background_queue_.DropPendingIO();
-  }
+int BackendImplV3::Init(const CompletionCallback& callback) {
+  DCHECK(!init_);
+  if (init_)
+    return net::ERR_FAILED;
 
-  if (background_queue_.BackgroundIsCurrentThread()) {
-    // Unit tests may use the same thread for everything.
-    CleanupCache();
-  } else {
-    background_queue_.background_thread()->PostTask(
-        FROM_HERE, base::Bind(&FinalCleanupCallback, base::Unretained(this)));
-    // http://crbug.com/74623
-    base::ThreadRestrictions::ScopedAllowWait allow_wait;
-    done_.Wait();
-  }
-}
+  worker_ = new Worker(path_, base::MessageLoopProxy::current());
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_INIT);
+  work_item->set_user_callback(callback);
+  work_item->set_flags(user_flags_);
+  PostWorkItem(work_item);
 
-int BackendImpl::Init(const CompletionCallback& callback) {
-  background_queue_.Init(callback);
   return net::ERR_IO_PENDING;
 }
 
 // ------------------------------------------------------------------------
 
-int BackendImpl::OpenPrevEntry(void** iter, Entry** prev_entry,
+int BackendImplV3::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;
+  return OpenFollowingEntry(true, iter, prev_entry, callback);
 }
 
-bool BackendImpl::SetMaxSize(int max_bytes) {
+bool BackendImplV3::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;
+  user_flags_ |= MAX_SIZE;
   max_size_ = max_bytes;
   return true;
 }
 
-void BackendImpl::SetType(net::CacheType type) {
+void BackendImplV3::SetType(net::CacheType type) {
   DCHECK_NE(net::MEMORY_CACHE, type);
   cache_type_ = type;
 }
 
-bool BackendImpl::CreateBlock(FileType block_type, int block_count,
-                             Addr* block_address) {
+bool BackendImplV3::CreateBlock(FileType block_type, int block_count,
+                                Addr* block_address) {
   return block_files_.CreateBlock(block_type, block_count, block_address);
 }
 
-void BackendImpl::UpdateRank(EntryImpl* entry, bool modified) {
-  if (read_only_ || (!modified && cache_type() == net::SHADER_CACHE))
-    return;
-  eviction_.UpdateRank(entry, modified);
-}
-
-void BackendImpl::InternalDoomEntry(EntryImpl* entry) {
+void BackendImplV3::UpdateRank(EntryImplV3* entry, bool modified) {
+  if (!modified && (cache_type() == net::SHADER_CACHE || read_only_))
+    return;
+
+  index_.UpdateTime(entry->GetHash(), entry->GetAddress(), GetCurrentTime());
+}
+
+void BackendImplV3::InternalDoomEntry(EntryImplV3* 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());
-
+  Addr entry_addr = entry->GetAddress();
+  
   Trace("Doom entry 0x%p", entry);
 
-  if (!entry->doomed()) {
-    // We may have doomed this entry from within MatchEntry.
-    eviction_.OnDoomEntry(entry);
-    entry->InternalDoom();
-    if (!new_eviction_) {
-      DecreaseNumEntries();
+  index_.SetSate(hash, entry_addr, ENTRY_DELETED);
+
+  // The entry is transitioning from open to doomed.
+  doomed_entries_[entry_addr.value()] = entry;
+  EntriesMap::iterator it = open_entries_.find(entry_addr.value());
+  if (it != open_entries_.end())
+    open_entries_.erase(it);
+  else
+    NOTREACHED();
+
+  entry->InternalDoom();
+  DecreaseNumEntries();
+}
+
+bool BackendImplV3::ShouldDeleteNow(EntryImplV3* entry) {
+  Addr entry_addr = entry->GetAddress();
+  DCHECK(doomed_entries_.count(entry_addr.value()));
+  EntriesMap::iterator it = entries_to_delete_.find(entry_addr.value());
+  if (it == entries_to_delete_.end()) {
+    // Delay deletion until the next backup cycle.
+    entries_to_delete_[entry_addr.value()] = entry;
+    entry->AddRef();
+
+    // The entry was ready to be deleted. By opening it again we make sure
+    // we'll go again through the normal Close() logic later on, and we'll have
+    // a second chance to allow deletion.
+    entry->OnOpenEntry();
+    return false;
+  }
+
+  entries_to_delete_.erase(it);
+  return true;
+}
+
+void BackendImplV3::OnEntryCleanup(EntryImplV3* entry) {
+  // An entry may be going away pretty soon (as soon as all pending IO is done).
+  // Grab an extra reference so that the entry is alive for a little longer and
+  // we may reuse it directly.
+  if (recent_entries_.insert(entry).second)
+    entry->AddRef();
+}
+
+void BackendImplV3::OnEntryDestroyBegin(Addr address) {
+  if (disabled_)
+    return;
+  EntriesMap::iterator it = open_entries_.find(address.value());
+  if (it != open_entries_.end()) {
+    index_.SetSate(it->second->GetHash(), address, ENTRY_USED);
+    open_entries_.erase(it);
+  } else {
+    it = doomed_entries_.find(address.value());
+    if (it != doomed_entries_.end()) {
+      // All data is gone. Wait for the next backup cycle before releasing the
+      // cell itself.
+      CellInfo cell_info = { it->second->GetHash(), address };
+      deleted_entries_.push_back(cell_info);
+      doomed_entries_.erase(it);
     }
-    stats_.OnEvent(Stats::DOOM_ENTRY);
-  }
-
-  if (parent_entry) {
-    parent_entry->SetNextAddress(Addr(child));
-    parent_entry->Release();
-  } else if (!error) {
-    data_->table[hash & mask_] = child;
-  }
-
-  FlushIndex();
-}
-
-void BackendImpl::OnEntryDestroyBegin(Addr address) {
+  }
+}
+
+void BackendImplV3::OnEntryDestroyEnd() {
+  DecreaseNumRefs();
+  if (disabled_)
+    return;
+  if (index_.header()->num_bytes > max_size_ && !read_only_ &&
+      (up_ticks_ > kTrimDelay || user_flags_ & BASIC_UNIT_TEST)) {
+    eviction_.TrimCache();
+  }
+}
+
+void BackendImplV3::OnEntryModified(EntryImplV3* entry) {
+  index_.SetSate(entry->GetHash(), entry->GetAddress(), ENTRY_MODIFIED);
+}
+
+void BackendImplV3::ReadData(EntryImplV3* entry, Addr address, int offset,
+                             net::IOBuffer* buffer, int buffer_len,
+                             const CompletionCallback& callback) {
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_READ_DATA);
+  work_item->set_buffer(buffer);
+  work_item->set_buffer_len(buffer_len);
+  work_item->set_address(address);
+  work_item->set_offset(offset);
+  work_item->set_user_callback(callback);
+  if (entry)
+    work_item->set_owner_entry(entry);
+
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::WriteData(EntryImplV3* entry, Addr address, int offset,
+                              net::IOBuffer* buffer, int buffer_len,
+                              const CompletionCallback& callback) {
+  if (!buffer_len) {
+    DCHECK(callback.is_null());
+    return;
+  }
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_WRITE_DATA);
+  work_item->set_buffer(buffer);
+  work_item->set_buffer_len(buffer_len);
+  work_item->set_address(address);
+  work_item->set_offset(offset);
+  work_item->set_user_callback(callback);
+  work_item->set_owner_entry(entry);
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::MoveData(EntryImplV3* entry, Addr source,
+                             Addr destination, int len,
+                             const CompletionCallback& callback) {
+  DCHECK(len);
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_MOVE_DATA);
+  work_item->set_buffer_len(len);
+  work_item->set_address(source);
+  work_item->set_address2(destination);
+  work_item->set_user_callback(callback);
+  work_item->set_owner_entry(entry);
+  PostWorkItem(work_item);//+delete source
+}
+
+void BackendImplV3::Truncate(EntryImplV3* entry, Addr address, int offset) {
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_TRUNCATE);
+  work_item->set_address(address);
+  work_item->set_offset(offset);
+  work_item->set_owner_entry(entry);
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::Delete(EntryImplV3* entry, Addr address) {
+  if (disabled_)
+    return;
+  if (address.is_separate_file()) {
+    scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_DELETE);
+    work_item->set_address(address);
+    work_item->set_owner_entry(entry);
+    PostWorkItem(work_item);
+
+    // And now delete the block itself.
+    address = address.AsBlockFile();
+  }
+
+  int size = Addr::BlockSizeForFileType(address.file_type());
+  scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(size));
+  memset(buffer->data(), 0, size);
+  WriteData(entry, address, 0, buffer, size, net::CompletionCallback());
+
+  block_files_.DeleteBlock(address);
+}
+
+void BackendImplV3::Close(EntryImplV3* entry, Addr address) {
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_CLOSE);
+  work_item->set_address(address);
+  work_item->set_owner_entry(entry);
+  PostWorkItem(work_item);
+}
+
+bool BackendImplV3::EvictEntry(uint32 hash, 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);
+    return false;
+
+  EntryCell old_cell = index_.FindEntryCell(hash, address);
+  if (!old_cell.IsValid() || old_cell.GetState() != ENTRY_USED)
+    return false;
+
+  EntrySet entries;
+  entries.cells.push_back(old_cell);
+
+  uint32 flags = WorkItem::WORK_FOR_EVICT;
+  if (lru_eviction_) {
+    flags |= WorkItem::WORK_NO_COPY;
+  } else {
+    Addr new_address;
+    if (!block_files_.CreateBlock(BLOCK_EVICTED, 1, &new_address))
+      return false;
+
+    EntryCell new_cell = index_.CreateEntryCell(hash, new_address);
+    if (!new_cell.IsValid()) {
+      block_files_.DeleteBlock(new_address);
+      return false;
+    }
+    entries.cells.push_back(new_cell);
+  }
+
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_OPEN_ENTRY);
+  work_item->set_flags(flags);
+  work_item->set_entries(entries);
+  PostWorkItem(work_item);
+
+  return true;
+}
+
+EntryImplV3* BackendImplV3::GetOpenEntry(Addr address) const {
+  EntriesMap::const_iterator it = open_entries_.find(address.value());
   if (it != open_entries_.end()) {
     // We have this entry in memory.
+    it->second->AddRef();
+    it->second->OnOpenEntry();
     return it->second;
   }
 
   return NULL;
 }
 
-int BackendImpl::MaxFileSize() const {
+int BackendImplV3::MaxFileSize() const {
   return max_size_ / 8;
 }
 
-void BackendImpl::ModifyStorageSize(int32 old_size, int32 new_size) {
+void BackendImplV3::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
     AddStorageSize(new_size - old_size);
 
-  FlushIndex();
-
   // Update the usage statistics.
   stats_.ModifyStorageStats(old_size, new_size);
 }
 
-void BackendImpl::TooMuchStorageRequested(int32 size) {
+void BackendImplV3::TooMuchStorageRequested(int32 size) {
   stats_.ModifyStorageStats(0, size);
 }
 
-bool BackendImpl::IsAllocAllowed(int current_size, int new_size) {
+bool BackendImplV3::IsAllocAllowed(int current_size, int new_size, bool force) {
   DCHECK_GT(new_size, current_size);
-  if (user_flags_ & kNoBuffering)
+  if (!force && (user_flags_ & NO_BUFFERING))
     return false;
 
   int to_add = new_size - current_size;
-  if (buffer_bytes_ + to_add > MaxBuffersSize())
+  if (!force && (buffer_bytes_ + to_add > MaxBuffersSize()))
     return false;
 
   buffer_bytes_ += to_add;
   CACHE_UMA(COUNTS_50000, "BufferBytes", 0, buffer_bytes_ / 1024);
   return true;
 }
 
-void BackendImpl::BufferDeleted(int size) {
+void BackendImplV3::BufferDeleted(int size) {
+  DCHECK_GE(size, 0);
   buffer_bytes_ -= size;
-  DCHECK_GE(size, 0);
+  DCHECK_GE(buffer_bytes_, 0);
 }
 
-bool BackendImpl::IsLoaded() const {
-  CACHE_UMA(COUNTS, "PendingIO", 0, num_pending_io_);
-  if (user_flags_ & kNoLoadProtection)
+bool BackendImplV3::IsLoaded() const {
+  if (user_flags_ & NO_LOAD_PROTECTION)
     return false;
 
-  return (num_pending_io_ > 5 || user_load_);
+  return user_load_;
 }
 
-std::string BackendImpl::HistogramName(const char* name, int experiment) const {
+base::Time BackendImplV3::GetCurrentTime() const {
+  Time base_time = Time::Now();
+  if (!test_seconds_)
+    return base_time;
+
+  return base_time + TimeDelta::FromSeconds(test_seconds_);
+}
+
+std::string BackendImplV3::HistogramName(const char* name,
+                                         int experiment) const {
+  static const char* names[] = { "Http", "", "Media", "AppCache", "Shader" };
+  DCHECK_NE(cache_type_, net::MEMORY_CACHE);
   if (!experiment)
-    return base::StringPrintf("DiskCache.%d.%s", cache_type_, name);
-  return base::StringPrintf("DiskCache.%d.%s_%d", cache_type_,
+    return base::StringPrintf("DiskCache3.%s.%s", names[cache_type_], name);
+  return base::StringPrintf("DiskCache3.%s.%s_%d", names[cache_type_],
                             name, experiment);
 }
 
-base::WeakPtr<BackendImpl> BackendImpl::GetWeakPtr() {
+base::WeakPtr<BackendImplV3> BackendImplV3::GetWeakPtr() {
   return ptr_factory_.GetWeakPtr();
 }
 
 // We want to remove biases from some histograms so we only send data once per
 // week.
-bool BackendImpl::ShouldReportAgain() {
+bool BackendImplV3::ShouldReportAgain() {
   if (uma_report_)
     return uma_report_ == 2;
 
   uma_report_++;
   int64 last_report = stats_.GetCounter(Stats::LAST_REPORT);
   Time last_time = Time::FromInternalValue(last_report);
-  if (!last_report || (Time::Now() - last_time).InDays() >= 7) {
-    stats_.SetCounter(Stats::LAST_REPORT, Time::Now().ToInternalValue());
+  if (!last_report || (GetCurrentTime() - last_time).InDays() >= 7) {
+    stats_.SetCounter(Stats::LAST_REPORT, GetCurrentTime().ToInternalValue());
     uma_report_++;
     return true;
   }
   return false;
 }
 
-void BackendImpl::FirstEviction() {
-  DCHECK(data_->header.create_time);
+void BackendImplV3::FirstEviction() {
+  IndexHeaderV3* header = index_.header();
+  header->flags |= CACHE_EVICTED;
+  DCHECK(header->create_time);
   if (!GetEntryCount())
     return;  // This is just for unit tests.
 
-  Time create_time = Time::FromInternalValue(data_->header.create_time);
+  Time create_time = Time::FromInternalValue(header->create_time);
   CACHE_UMA(AGE, "FillupAge", 0, create_time);
 
   int64 use_time = stats_.GetCounter(Stats::TIMER);
   CACHE_UMA(HOURS, "FillupTime", 0, static_cast<int>(use_time / 120));
   CACHE_UMA(PERCENTAGE, "FirstHitRatio", 0, stats_.GetHitRatio());
 
   if (!use_time)
     use_time = 1;
   CACHE_UMA(COUNTS_10000, "FirstEntryAccessRate", 0,
-            static_cast<int>(data_->header.num_entries / use_time));
+            static_cast<int>(header->num_entries / use_time));
   CACHE_UMA(COUNTS, "FirstByteIORate", 0,
-            static_cast<int>((data_->header.num_bytes / 1024) / use_time));
+            static_cast<int>((header->num_bytes / 1024) / use_time));
 
-  int avg_size = data_->header.num_bytes / GetEntryCount();
+  int avg_size = header->num_bytes / GetEntryCount();
   CACHE_UMA(COUNTS, "FirstEntrySize", 0, avg_size);
 
   int large_entries_bytes = stats_.GetLargeEntriesSize();
-  int large_ratio = large_entries_bytes * 100 / data_->header.num_bytes;
+  int large_ratio = large_entries_bytes * 100 / header->num_bytes;
   CACHE_UMA(PERCENTAGE, "FirstLargeEntriesRatio", 0, large_ratio);
 
-  if (new_eviction_) {
+  if (!lru_eviction_) {
     CACHE_UMA(PERCENTAGE, "FirstResurrectRatio", 0, stats_.GetResurrectRatio());
     CACHE_UMA(PERCENTAGE, "FirstNoUseRatio", 0,
-              data_->header.lru.sizes[0] * 100 / data_->header.num_entries);
+              header->num_no_use_entries * 100 / header->num_entries);
     CACHE_UMA(PERCENTAGE, "FirstLowUseRatio", 0,
-              data_->header.lru.sizes[1] * 100 / data_->header.num_entries);
+              header->num_low_use_entries * 100 / header->num_entries);
     CACHE_UMA(PERCENTAGE, "FirstHighUseRatio", 0,
-              data_->header.lru.sizes[2] * 100 / data_->header.num_entries);
+              header->num_high_use_entries * 100 / header->num_entries);
   }
 
-  stats_.ResetRatios();
+  stats_.ResetRatios(); 
 }
 
-void BackendImpl::OnEvent(Stats::Counters an_event) {
+void BackendImplV3::OnEvent(Stats::Counters an_event) {
   stats_.OnEvent(an_event);
 }
 
-void BackendImpl::OnRead(int32 bytes) {
+void BackendImplV3::OnRead(int32 bytes) {
   DCHECK_GE(bytes, 0);
   byte_count_ += bytes;
   if (byte_count_ < 0)
     byte_count_ = kint32max;
 }
 
-void BackendImpl::OnWrite(int32 bytes) {
+void BackendImplV3::OnWrite(int32 bytes) {
   // We use the same implementation as OnRead... just log the number of bytes.
   OnRead(bytes);
 }
 
-void BackendImpl::OnStatsTimer() {
+void BackendImplV3::GrowBlockFiles() {
+  if (growing_files_ || disabled_)
+    return;
+  growing_files_ = true;
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_GROW_FILES);
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::OnTimerTick() {
+  if (disabled_)
+    return;
+
   stats_.OnEvent(Stats::TIMER);
   int64 time = stats_.GetCounter(Stats::TIMER);
   int64 current = stats_.GetCounter(Stats::OPEN_ENTRIES);
 
   // OPEN_ENTRIES is a sampled average of the number of open entries, avoiding
   // the bias towards 0.
   if (num_refs_ && (current != num_refs_)) {
     int64 diff = (num_refs_ - current) / 50;
     if (!diff)
       diff = num_refs_ > current ? 1 : -1;
     current = current + diff;
     stats_.SetCounter(Stats::OPEN_ENTRIES, current);
     stats_.SetCounter(Stats::MAX_ENTRIES, max_refs_);
   }
 
   CACHE_UMA(COUNTS, "NumberOfReferences", 0, num_refs_);
 
   CACHE_UMA(COUNTS_10000, "EntryAccessRate", 0, entry_count_);
   CACHE_UMA(COUNTS, "ByteIORate", 0, byte_count_ / 1024);
 
   // These values cover about 99.5% of the population (Oct 2011).
   user_load_ = (entry_count_ > 300 || byte_count_ > 7 * 1024 * 1024);
   entry_count_ = 0;
   byte_count_ = 0;
   up_ticks_++;
 
-  if (!data_)
-    first_timer_ = false;
   if (first_timer_) {
     first_timer_ = false;
     if (ShouldReportAgain())
       ReportStats();
   }
 
+  index_.OnBackupTimer();
+  CloseDoomedEntries();
+  ReleaseRecentEntries();
+  UpdateDeletedEntries();
+
   // Save stats to disk at 5 min intervals.
   if (time % 10 == 0)
     StoreStats();
 }
 
-void BackendImpl::SetUnitTestMode() {
-  user_flags_ |= kUnitTestMode;
-  unit_test_ = true;
+void BackendImplV3::SetUnitTestMode() {
+  user_flags_ |= UNIT_TEST_MODE;
 }
 
-void BackendImpl::SetUpgradeMode() {
-  user_flags_ |= kUpgradeMode;
+void BackendImplV3::SetUpgradeMode() {
+  user_flags_ |= UPGRADE_MODE;
   read_only_ = true;
 }
 
-void BackendImpl::SetNewEviction() {
-  user_flags_ |= kNewEviction;
-  new_eviction_ = true;
+void BackendImplV3::SetNewEviction() {
+  user_flags_ |= EVICTION_V2;
+  lru_eviction_ = false;
 }
 
-void BackendImpl::SetFlags(uint32 flags) {
+void BackendImplV3::SetFlags(uint32 flags) {
   user_flags_ |= flags;
 }
 
-int BackendImpl::FlushQueueForTest(const CompletionCallback& callback) {
-  background_queue_.FlushQueue(callback);
+int BackendImplV3::FlushQueueForTest(const CompletionCallback& callback) {
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_NONE);
+  work_item->set_user_callback(callback);
+  PostWorkItem(work_item);
   return net::ERR_IO_PENDING;
 }
 
-void BackendImpl::TrimForTest(bool empty) {
-  eviction_.SetTestMode();
-  eviction_.TrimCache(empty);
+int BackendImplV3::CleanupForTest(const CompletionCallback& callback) {
+  CloseDoomedEntries();
+  ReleaseRecentEntries();
+  UpdateDeletedEntries();
+  index_.OnBackupTimer();
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_CLEANUP);
+  work_item->set_user_callback(callback);
+  PostWorkItem(work_item);
+  worker_ = NULL;
+  init_ = false;
+  disabled_ = true;
+  index_.Reset();
+  return net::ERR_IO_PENDING;
 }
 
-void BackendImpl::TrimDeletedListForTest(bool empty) {
+void BackendImplV3::TrimForTest(bool empty) {
+  eviction_.SetTestMode();
+  if (empty)
+    eviction_.TrimAllCache(CompletionCallback());
+  else
+    eviction_.TrimCache();
+}
+
+void BackendImplV3::TrimDeletedListForTest(bool empty) {
   eviction_.SetTestMode();
   eviction_.TrimDeletedList(empty);
 }
 
-int BackendImpl::SelfCheck() {
+void BackendImplV3::AddDelayForTest(int seconds) {
+  Trace("Add %d deconds", seconds);
+  int old_timers = test_seconds_ / kTimerSeconds;
+  test_seconds_ += seconds;
+  if (old_timers != test_seconds_ / kTimerSeconds)
+    OnTimerTick();
+}
+
+int BackendImplV3::WaitForEntryToCloseForTest(
+    const std::string& key,
+    const CompletionCallback& callback) {
+  DCHECK(!callback.is_null());
+  if (disabled_ || key.empty())
+    return net::ERR_FAILED;
+
+  uint32 hash = base::Hash(key);
+
+  EntrySet entries = index_.LookupEntry(hash);
+  if (!entries.cells.size())
+    return net::OK;
+
+  if (entries.cells.size() == static_cast<size_t>(entries.evicted_count))
+    return net::OK;
+
+  EntryImplV3* open_entry = LookupOpenEntry(entries, key);
+  if (open_entry) {
+    open_entry->NotifyDestructionForTest(callback);
+    open_entry->Close();
+    return net::ERR_IO_PENDING;
+  }
+
+  return net::OK;
+}
+
+int BackendImplV3::SelfCheck() {
   if (!init_) {
     LOG(ERROR) << "Init failed";
     return ERR_INIT_FAILED;
   }
 
-  int num_entries = rankings_.SelfCheck();
+  /*int num_entries = rankings_.SelfCheck();
   if (num_entries < 0) {
     LOG(ERROR) << "Invalid rankings list, error " << num_entries;
 #if !defined(NET_BUILD_STRESS_CACHE)
     return num_entries;
 #endif
   }
 
-  if (num_entries != data_->header.num_entries) {
+  if (num_entries != index_.header()->num_entries) {
     LOG(ERROR) << "Number of entries mismatch";
 #if !defined(NET_BUILD_STRESS_CACHE)
     return ERR_NUM_ENTRIES_MISMATCH;
 #endif
-  }
+  }*/
 
   return CheckAllEntries();
 }
 
+void BackendImplV3::GrowIndex() {
+  if (growing_index_ || disabled_)
+    return;
+  growing_index_ = true;
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_GROW_INDEX);
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::SaveIndex(net::IOBuffer* buffer, int buffer_len) {
+  if (disabled_ || !buffer_len)
+    return;
+
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_WRITE_INDEX);
+  work_item->set_buffer(buffer);
+  work_item->set_buffer_len(buffer_len);
+  work_item->set_offset(0);
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::DeleteCell(EntryCell cell) {
+  NOTREACHED();
+  // Post task to delete this cell.
+  // look at a local map of cells being deleted.
+}
+
+void BackendImplV3::FixCell(EntryCell cell) {
+  NOTREACHED();
+}
+
 // ------------------------------------------------------------------------
 
-net::CacheType BackendImpl::GetCacheType() const {
+net::CacheType BackendImplV3::GetCacheType() const {
   return cache_type_;
 }
 
-int32 BackendImpl::GetEntryCount() const {
-  if (!index_.get() || disabled_)
+int32 BackendImplV3::GetEntryCount() const {
+  if (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;
-}
-
-EntryImpl* BackendImpl::OpenEntryImpl(const std::string& key) {
-  if (disabled_)
-    return NULL;
-
-  TimeTicks start = TimeTicks::Now();
+  DCHECK(init_);
+  return index_.header()->num_entries;
+}
+
+int BackendImplV3::OpenEntry(const std::string& key, Entry** entry,
+                             const CompletionCallback& callback) {
+  DCHECK(!callback.is_null());
+  if (disabled_ || key.empty())
+    return net::ERR_FAILED;
+
   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) {
+  EntrySet entries = index_.LookupEntry(hash);
+  if (!entries.cells.size())
+    return net::ERR_FAILED;
+
+  if (entries.cells.size() == static_cast<size_t>(entries.evicted_count))
+    return net::ERR_FAILED;
+
+  EntryImplV3* open_entry = LookupOpenEntry(entries, key);
+  if (open_entry) {
+    *entry = open_entry;
+    eviction_.OnOpenEntry(open_entry);
+    entry_count_++;
+
+    Trace("Open hash 0x%x end: 0x%x", hash, open_entry->GetAddress().value());
+    stats_.OnEvent(Stats::OPEN_HIT);
+    SIMPLE_STATS_COUNTER("disk_cache.hit");
+    return net::OK;
+  }
+
+  // Read the entry from disk.
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_OPEN_ENTRY);
+  work_item->set_entries(entries);
+  work_item->set_user_callback(callback);
+  work_item->set_key(key);
+  work_item->set_entry_buffer(entry);
+  PostWorkItem(work_item);
+
+  return net::ERR_IO_PENDING;
+}
+
+int BackendImplV3::CreateEntry(const std::string& key, Entry** entry,
+                               const CompletionCallback& callback) {
+  DCHECK(init_);
+  DCHECK(!callback.is_null());
+  if (disabled_ || key.empty() || key.size() > kMaxKeySize)
+    return net::ERR_FAILED;
+
+  uint32 hash = base::Hash(key);
+  Trace("Create hash 0x%x", hash);
+
+  EntrySet entries = index_.LookupEntry(hash);
+  if (entries.cells.size()) {
+    if (entries.cells.size() != static_cast<size_t>(entries.evicted_count)) {
+      // but we may have a hash collision :(. So create a work item to check it here!.
+      // kep collission specfic map
+      return net::ERR_FAILED;
+    }
+
+    // On the other hand, we have only deleted items that we may resurrect.
+    // Read the entry from disk.
+    scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_OPEN_ENTRY);
+    work_item->set_flags(WorkItem::WORK_FOR_RESURRECT);
+    work_item->set_entries(entries);
+    work_item->set_user_callback(callback);
+    work_item->set_key(key);
+    work_item->set_entry_buffer(entry);
+    PostWorkItem(work_item);
+
+    return net::ERR_IO_PENDING;
+  }
+  return OnCreateEntryComplete(key, hash, NULL, entry, callback);
+}
+
+int BackendImplV3::DoomEntry(const std::string& key,
+                             const CompletionCallback& callback) {
+  DCHECK(!callback.is_null());
   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.get();
-
-  // 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.get());
-
-  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) {
+    return net::ERR_FAILED;
+
+  uint32 hash = base::Hash(key);
+  Trace("DoomEntry hash 0x%x", hash);
+
+  EntrySet entries = index_.LookupEntry(hash);
+  if (!entries.cells.size())
+    return net::ERR_FAILED;
+
+  if (entries.cells.size() == static_cast<size_t>(entries.evicted_count))
+    return net::ERR_FAILED;
+
+  EntryImplV3* open_entry = LookupOpenEntry(entries, key);
+  if (open_entry) {
+    open_entry->Doom();
+    open_entry->Close();
+    return net::OK;
+  }
+
+  // Read the entry from disk.
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_OPEN_ENTRY);
+  work_item->set_flags(WorkItem::WORK_FOR_DOOM);
+  work_item->set_entries(entries);
+  work_item->set_user_callback(callback);
+  work_item->set_key(key);
+  PostWorkItem(work_item);
+
+  return net::ERR_IO_PENDING;
+}
+
+int BackendImplV3::DoomAllEntries(const CompletionCallback& callback) {
   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);
+    RestartCache(callback);
+    return init_ ? net::OK : net::ERR_IO_PENDING;
+  }
+  return eviction_.TrimAllCache(callback);
+}
+
+int BackendImplV3::DoomEntriesBetween(base::Time initial_time,
+                                      base::Time end_time,
+                                      const CompletionCallback& callback) {
+  DCHECK_NE(net::APP_CACHE, cache_type_);
+  Time now = GetCurrentTime();
+  if (end_time.is_null() || end_time > now)
+    end_time = now;
+
+  DCHECK(end_time >= initial_time);
+
+  if (disabled_)
+    return net::ERR_FAILED;
+
+  scoped_ptr<IndexIterator> to_delete(new IndexIterator);
+  to_delete->forward = false;
+  to_delete->timestamp = index_.CalculateTimestamp(end_time) + 1;
+
+  // Prepare to read the first entry from disk.
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_OPEN_ENTRY);
+  work_item->set_flags(WorkItem::WORK_FOR_ITERATION |
+                       WorkItem::WORK_FOR_DOOM_RANGE);
+  work_item->set_initial_time(initial_time);
+  work_item->set_end_time(end_time);
+  work_item->set_iterator(to_delete.Pass());
+
+  if (OpenNext(work_item) != net::ERR_IO_PENDING)
     return net::OK;
-  }
-}
-
-int BackendImpl::SyncDoomEntriesBetween(const base::Time initial_time,
-                                        const base::Time end_time) {
+
+  work_item->set_user_callback(callback);
+  return net::ERR_IO_PENDING;
+}
+
+int BackendImplV3::DoomEntriesSince(base::Time initial_time,
+                                    const CompletionCallback& callback) {
   DCHECK_NE(net::APP_CACHE, cache_type_);
-  if (end_time.is_null())
-    return SyncDoomEntriesSince(initial_time);
-
-  DCHECK(end_time >= initial_time);
-
+  return DoomEntriesBetween(initial_time, GetCurrentTime(), callback);
+}
+
+int BackendImplV3::OpenNextEntry(void** iter, Entry** next_entry,
+                                 const CompletionCallback& callback) {
+  DCHECK(!callback.is_null());
+  return OpenFollowingEntry(false, iter, next_entry, callback);
+}
+
+void BackendImplV3::EndEnumeration(void** iter) {
+  scoped_ptr<IndexIterator> iterator(
+      reinterpret_cast<IndexIterator*>(*iter));
+  *iter = NULL;
+}
+
+void BackendImplV3::GetStats(StatsItems* stats) {
   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) {
-  background_queue_.EndEnumeration(*iter);
-  *iter = NULL;
-}
-
-void BackendImpl::GetStats(StatsItems* stats) {
-  if (disabled_)
     return;
 
   std::pair<std::string, std::string> item;
 
   item.first = "Entries";
-  item.second = base::StringPrintf("%d", data_->header.num_entries);
-  stats->push_back(item);
-
-  item.first = "Pending IO";
-  item.second = base::StringPrintf("%d", num_pending_io_);
+  item.second = base::StringPrintf("%d", index_.header()->num_entries);
   stats->push_back(item);
 
   item.first = "Max size";
   item.second = base::StringPrintf("%d", max_size_);
   stats->push_back(item);
 
   item.first = "Current size";
-  item.second = base::StringPrintf("%d", data_->header.num_bytes);
+  item.second = base::StringPrintf("%d", index_.header()->num_bytes);
   stats->push_back(item);
 
-  item.first = "Cache type";
-  item.second = "Blockfile Cache";
-  stats->push_back(item);
-
   stats_.GetItems(stats);
 }
 
-void BackendImpl::SyncOnExternalCacheHit(const std::string& key) {
-  if (disabled_)
+void BackendImplV3::OnExternalCacheHit(const std::string& key) {
+  if (disabled_ || key.empty())
     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);
+  EntrySet entries = index_.LookupEntry(hash);
+  if (!entries.cells.size())
+    return;
+
+  if (entries.cells.size() == static_cast<size_t>(entries.evicted_count))
+    return;
+
+  for (size_t i = 0; i < entries.cells.size(); i++) {
+    if (entries.cells[i].GetGroup() == ENTRY_EVICTED)
+      continue;
+
+    index_.UpdateTime(hash, entries.cells[i].GetAddress(), GetCurrentTime());
+  }
+
+  EntryImplV3* open_entry = LookupOpenEntry(entries, key);
+  if (open_entry) {
+    eviction_.OnOpenEntry(open_entry);
+    entry_count_++;
+    UpdateRank(open_entry, true);
+    open_entry->Close();
+    return;
+  }
+
+  if (user_flags_ & UNIT_TEST_MODE) {
+    for (size_t i = 0; i < entries.cells.size(); i++) {
+      // This method doesn't have a callback, and it may take a while for the
+      // operation to complete so update the time of any entry with this hash.
+      if (entries.cells[i].GetGroup() != ENTRY_EVICTED) {
+        index_.UpdateTime(hash, entries.cells[i].GetAddress(),
+                          GetCurrentTime());
+      }
     }
-    cache_entry->Release();
-  }
+  }
+
+  // Read the entry from disk.
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_OPEN_ENTRY);
+  work_item->set_flags(WorkItem::WORK_FOR_UPDATE);
+  work_item->set_entries(entries);
+  work_item->set_key(key);
+  PostWorkItem(work_item);
 }
 
 // ------------------------------------------------------------------------
 
 // The maximum cache size will be either set explicitly by the caller, or
 // calculated by this code.
-void BackendImpl::AdjustMaxCacheSize(int table_len) {
+void BackendImplV3::AdjustMaxCacheSize() {
   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.
   int64 available = base::SysInfo::AmountOfFreeDiskSpace(path_);
   if (available < 0) {
     max_size_ = kDefaultCacheSize;
     return;
   }
 
-  if (table_len)
-    available += data_->header.num_bytes;
+  available += index_.header()->num_bytes;
 
   max_size_ = PreferedCacheSize(available);
 
   // Let's not use more than the default size while we tune-up the performance
   // of bigger caches. TODO(rvargas): remove this limit.
   if (max_size_ > kDefaultCacheSize * 4)
     max_size_ = kDefaultCacheSize * 4;
-
-  if (!table_len)
-    return;
-
-  // If we already have a table, adjust the size to it.
-  int current_max_size = MaxStorageSizeForTable(table_len);
-  if (max_size_ > current_max_size)
-    max_size_= current_max_size;
 }
 
-bool BackendImpl::InitStats() {
-  Addr address(data_->header.stats);
+bool BackendImplV3::InitStats(void* stats_data) {
+  Addr address(index_.header()->stats);
   int size = stats_.StorageSize();
 
   if (!address.is_initialized()) {
     FileType file_type = Addr::RequiredFileType(size);
     DCHECK_NE(file_type, EXTERNAL);
     int num_blocks = Addr::RequiredBlocks(size, file_type);
 
     if (!CreateBlock(file_type, num_blocks, &address))
       return false;
     return stats_.Init(NULL, 0, address);
   }
 
-  if (!address.is_block_file()) {
-    NOTREACHED();
-    return false;
-  }
+  // Load the required data.
+  DCHECK(address.is_block_file());
+  size = address.num_blocks() * address.BlockSize();
 
-  // Load the required data.
-  size = address.num_blocks() * address.BlockSize();
-  MappedFile* file = File(address);
-  if (!file)
-    return false;
-
-  scoped_ptr<char[]> data(new char[size]);
-  size_t offset = address.start_block() * address.BlockSize() +
-                  kBlockHeaderSize;
-  if (!file->Read(data.get(), size, offset))
-    return false;
-
-  if (!stats_.Init(data.get(), size, address))
+  if (!stats_.Init(stats_data, size, address))
     return false;
   if (cache_type_ == net::DISK_CACHE && ShouldReportAgain())
     stats_.InitSizeHistogram();
   return true;
 }
 
-void BackendImpl::StoreStats() {
+void BackendImplV3::StoreStats() {
   int size = stats_.StorageSize();
-  scoped_ptr<char[]> data(new char[size]);
+  scoped_refptr<net::IOBuffer> buffer(new net::IOBuffer(size));
   Addr address;
-  size = stats_.SerializeStats(data.get(), size, &address);
+  size = stats_.SerializeStats(buffer->data(), size, &address);
   DCHECK(size);
   if (!address.is_initialized())
     return;
 
-  MappedFile* file = File(address);
-  if (!file)
-    return;
-
-  size_t offset = address.start_block() * address.BlockSize() +
-                  kBlockHeaderSize;
-  file->Write(data.get(), size, offset);  // ignore result.
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_WRITE_DATA);
+  work_item->set_buffer(buffer);
+  work_item->set_buffer_len(size);
+  work_item->set_address(address);
+  work_item->set_offset(0);
+  PostWorkItem(work_item);
 }
 
-void BackendImpl::RestartCache(bool failure) {
-  int64 errors = stats_.GetCounter(Stats::FATAL_ERROR);
-  int64 full_dooms = stats_.GetCounter(Stats::DOOM_CACHE);
-  int64 partial_dooms = stats_.GetCounter(Stats::DOOM_RECENT);
-  int64 last_report = stats_.GetCounter(Stats::LAST_REPORT);
-
+void BackendImplV3::RestartCache(const CompletionCallback& callback) {
   PrepareForRestart();
-  if (failure) {
-    DCHECK(!num_refs_);
-    DCHECK(!open_entries_.size());
-    DelayedCacheCleanup(path_);
-  } else {
-    DeleteCache(path_, false);
-  }
 
   // Don't call Init() if directed by the unit test: we are simulating a failure
   // trying to re-enable the cache.
-  if (unit_test_)
+  if (user_flags_ & UNIT_TEST_MODE) {
     init_ = true;  // Let the destructor do proper cleanup.
-  else if (SyncInit() == net::OK) {
-    stats_.SetCounter(Stats::FATAL_ERROR, errors);
-    stats_.SetCounter(Stats::DOOM_CACHE, full_dooms);
-    stats_.SetCounter(Stats::DOOM_RECENT, partial_dooms);
-    stats_.SetCounter(Stats::LAST_REPORT, last_report);
+  } else {
+    scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_RESTART);
+    work_item->set_user_callback(callback);
+    work_item->set_flags(user_flags_);
+    PostWorkItem(work_item);
   }
 }
 
-void BackendImpl::PrepareForRestart() {
-  // Reset the mask_ if it was not given by the user.
-  if (!(user_flags_ & kMask))
-    mask_ = 0;
-
-  if (!(user_flags_ & kNewEviction))
-    new_eviction_ = false;
-
+void BackendImplV3::PrepareForRestart() {
+  if (!(user_flags_ & EVICTION_V2))
+    lru_eviction_ = true;
+  
   disabled_ = true;
-  data_->header.crash = 0;
-  index_->Flush();
-  index_ = NULL;
-  data_ = NULL;
-  block_files_.CloseFiles();
-  rankings_.Reset();
+  index_.header()->crash = 0;
+  block_files_.Clear();
+  index_.Reset();
   init_ = false;
   restarted_ = true;
 }
 
-void BackendImpl::CleanupCache() {
+void BackendImplV3::CleanupCache() {
   Trace("Backend Cleanup");
-  eviction_.Stop();
+  //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();
+    if (!(user_flags_ & NO_CLEAN_ON_EXIT)) {
+      StoreStats();
+      CloseDoomedEntries();
+      ReleaseRecentEntries();
+      UpdateDeletedEntries();
+      index_.OnBackupTimer();
     }
+    scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_CLEANUP);
+    PostWorkItem(work_item);
+    worker_ = NULL;
   }
-  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()) {
+int BackendImplV3::NewEntry(WorkItem* work_item, EntryImplV3** entry) {
+  Addr address =
+      work_item->entries()->cells[work_item->entries()->current].GetAddress();
+
+  // The entry could have been opened since this task was posted to the cache
+  // thread, so let's check again.
+  EntryImplV3* this_entry = GetOpenEntry(address);
+  if (this_entry) {
     // Easy job. This entry is already in memory.
-    EntryImpl* this_entry = it->second;
-    this_entry->AddRef();
     *entry = this_entry;
     return 0;
   }
 
+  // Even if the entry is not in memory right now, it could have changed. Note
+  // that any state other than USED means we are either deleting this entry or
+  // it should be in memory.
+  uint32 hash =
+      work_item->entries()->cells[work_item->entries()->current].hash();
+  EntryCell cell = index_.FindEntryCell(hash, address);
+  if (!cell.IsValid() || cell.GetState() != ENTRY_USED)
+    return ERR_INVALID_ENTRY;
+
   STRESS_DCHECK(block_files_.IsValid(address));
 
-  if (!address.SanityCheckForEntry()) {
+  if (!address.SanityCheckForEntryV3()) {
     LOG(WARNING) << "Wrong entry address.";
     STRESS_NOTREACHED();
     return ERR_INVALID_ADDRESS;
   }
 
-  scoped_refptr<EntryImpl> cache_entry(
-      new EntryImpl(this, address, read_only_));
+  scoped_refptr<EntryImplV3> cache_entry;
+  if (address.file_type() == BLOCK_EVICTED) {
+    cache_entry = new EntryImplV3(this, address, work_item->key(),
+                                  work_item->short_entry_record().Pass());
+  } else {
+    cache_entry = new EntryImplV3(this, address, work_item->key(),
+                                  work_item->entry_record().Pass());
+  }
   IncreaseNumRefs();
   *entry = NULL;
 
-  TimeTicks start = TimeTicks::Now();
-  if (!cache_entry->entry()->Load())
-    return ERR_READ_FAILURE;
-
-  if (IsLoaded()) {
-    CACHE_UMA(AGE_MS, "LoadTime", 0, start);
-  }
-
   if (!cache_entry->SanityCheck()) {
     LOG(WARNING) << "Messed up entry found.";
     STRESS_NOTREACHED();
     return ERR_INVALID_ENTRY;
   }
 
   STRESS_DCHECK(block_files_.IsValid(
                     Addr(cache_entry->entry()->Data()->rankings_node)));
 
-  if (!cache_entry->LoadNodeAddress())
-    return ERR_READ_FAILURE;
-
-  if (!rankings_.SanityCheck(cache_entry->rankings(), false)) {
-    STRESS_NOTREACHED();
-    cache_entry->SetDirtyFlag(0);
-    // Don't remove this from the list (it is not linked properly). Instead,
-    // break the link back to the entry because it is going away, and leave the
-    // rankings node to be deleted if we find it through a list.
-    rankings_.SetContents(cache_entry->rankings(), 0);
-  } else if (!rankings_.DataSanityCheck(cache_entry->rankings(), false)) {
-    STRESS_NOTREACHED();
-    cache_entry->SetDirtyFlag(0);
-    rankings_.SetContents(cache_entry->rankings(), address.value());
-  }
-
-  if (!cache_entry->DataSanityCheck()) {
+  if (!cache_entry->DataSanityCheck()) {//----------------------------------------------
+    // just one path? make sure we delete the cell in the first case, and as much data as we can here
     LOG(WARNING) << "Messed up entry found.";
-    cache_entry->SetDirtyFlag(0);
     cache_entry->FixForDelete();
   }
 
-  // Prevent overwriting the dirty flag on the destructor.
-  cache_entry->SetDirtyFlag(GetCurrentEntryId());
-
-  if (cache_entry->dirty()) {
-    Trace("Dirty entry 0x%p 0x%x", reinterpret_cast<void*>(cache_entry.get()),
-          address.value());
-  }
-
-  open_entries_[address.value()] = cache_entry.get();
+  open_entries_[address.value()] = cache_entry;
+  index_.SetSate(cache_entry->GetHash(), address, ENTRY_OPEN);
 
   cache_entry->BeginLogging(net_log_, false);
+  cache_entry->OnOpenEntry();
   cache_entry.swap(entry);
   return 0;
 }
 
+EntryImplV3* BackendImplV3::LookupOpenEntry(const EntrySet& entries,
+                                            const std::string key) {
+  for (size_t i = 0; i < entries.cells.size(); i++) {
+    if (entries.cells[i].GetGroup() == ENTRY_EVICTED)
+      continue;
+
+    EntryImplV3* this_entry = GetOpenEntry(entries.cells[i].GetAddress());
+    if (this_entry && this_entry->GetKey() == key)
+      return this_entry;
+  }
+  return NULL;
+}
+
 // This is the actual implementation for OpenNextEntry and OpenPrevEntry.
-EntryImpl* BackendImpl::OpenFollowingEntry(bool forward, void** iter) {
+int BackendImplV3::OpenFollowingEntry(bool forward, void** iter,
+                                      Entry** next_entry,
+                                      const CompletionCallback& callback) {
   if (disabled_)
-    return NULL;
+    return net::ERR_FAILED;
 
   DCHECK(iter);
 
-  const int kListsToSearch = 3;
-  scoped_refptr<EntryImpl> entries[kListsToSearch];
-  scoped_ptr<Rankings::Iterator> iterator(
-      reinterpret_cast<Rankings::Iterator*>(*iter));
+  scoped_ptr<IndexIterator> iterator(
+      reinterpret_cast<IndexIterator*>(*iter));
   *iter = NULL;
 
   if (!iterator.get()) {
-    iterator.reset(new Rankings::Iterator(&rankings_));
-    bool ret = false;
-
-    // Get an entry from each list.
-    for (int i = 0; i < kListsToSearch; i++) {
-      EntryImpl* temp = NULL;
-      ret |= OpenFollowingEntryFromList(forward, static_cast<Rankings::List>(i),
-                                        &iterator->nodes[i], &temp);
-      entries[i].swap(&temp);  // The entry was already addref'd.
+    iterator.reset(new IndexIterator);
+    iterator->timestamp = index_.CalculateTimestamp(GetCurrentTime()) + 1;
+    iterator->forward = forward;
+  }
+
+  // Prepare to read the first entry from disk.
+  scoped_refptr<WorkItem> work_item = new WorkItem(WorkItem::WORK_OPEN_ENTRY);
+  work_item->set_flags(WorkItem::WORK_FOR_ITERATION);
+  work_item->set_iterator(iterator.Pass());
+  work_item->set_iter_buffer(iter);
+  work_item->set_entry_buffer(next_entry);
+
+  int rv = OpenNext(work_item);
+  if (rv == net::ERR_IO_PENDING)
+    work_item->set_user_callback(callback);
+
+  return rv;
+}
+
+bool BackendImplV3::GetMoreCells(WorkItem* work_item) {
+  DCHECK(work_item->flags() & WorkItem::WORK_FOR_ITERATION);
+  IndexIterator* iterator = work_item->iterator();
+
+  if (work_item->flags() & WorkItem::WORK_FOR_DOOM_RANGE) {
+    int lower_limit = index_.CalculateTimestamp(work_item->initial_time());
+    if (iterator->timestamp <= lower_limit ||
+        !index_.GetNextCells(iterator)) {
+      return false;
     }
-    if (!ret)
-      return NULL;
+    return true;
+  }
+
+  return index_.GetNextCells(iterator);
+}
+
+int BackendImplV3::OpenNext(WorkItem* work_item) {
+  Trace("OpenNext work item 0x%p", work_item);
+  CellList* cells = &work_item->iterator()->cells;
+  EntrySet entries;
+  for (;;) {
+    if (cells->empty()) {
+      if (!GetMoreCells(work_item)) {
+        UpdateIterator(NULL, work_item);
+        return net::ERR_FAILED;
+      }
+      DCHECK(!cells->empty());
+    }
+
+    while (!cells->empty()) {
+      EntryCell last_cell = index_.FindEntryCell(cells->back().hash,
+                                                 cells->back().address);
+      cells->pop_back();
+      if (!last_cell.IsValid())
+        continue;
+
+      entries.cells.push_back(last_cell);
+      
+      // See if the entry is currently open.
+      EntryImplV3* this_entry = GetOpenEntry(last_cell.GetAddress());
+      if (this_entry) {
+        if (work_item->flags() & WorkItem::WORK_FOR_DOOM_RANGE) {
+          Doom(this_entry, work_item);
+          continue;
+        } else {
+          UpdateIterator(this_entry, work_item);
+          return net::OK;
+        }
+      }
+
+      work_item->set_entries(entries);
+      PostWorkItem(work_item);
+      return net::ERR_IO_PENDING;
+    }
+  }
+}
+
+void BackendImplV3::Doom(EntryImplV3* entry, WorkItem* work_item) {
+  if (entry->GetLastUsed() >= work_item->initial_time() &&
+      entry->GetLastUsed() < work_item->end_time()) {
+    Trace("Doom 0x%p work item 0x%p", entry, work_item);
+    entry->Doom();
+  }
+  entry->Close();
+}
+
+void BackendImplV3::UpdateIterator(EntryImplV3* entry, WorkItem* work_item) {
+  int result;
+  if (entry) {
+    result = net::OK;
+    *work_item->iter_buffer() = work_item->ReleaseIterator();
+    *work_item->entry_buffer() = entry;
+  } else if (work_item->flags() & WorkItem::WORK_FOR_DOOM_RANGE) {
+    result = net::OK;
   } else {
-    // Get the next entry from the last list, and the actual entries for the
-    // elements on the other lists.
-    for (int i = 0; i < kListsToSearch; i++) {
-      EntryImpl* temp = NULL;
-      if (iterator->list == i) {
-          OpenFollowingEntryFromList(forward, iterator->list,
-                                     &iterator->nodes[i], &temp);
-      } else {
-        temp = GetEnumeratedEntry(iterator->nodes[i],
-                                  static_cast<Rankings::List>(i));
-      }
-
-      entries[i].swap(&temp);  // The entry was already addref'd.
-    }
-  }
-
-  int newest = -1;
-  int oldest = -1;
-  Time access_times[kListsToSearch];
-  for (int i = 0; i < kListsToSearch; i++) {
-    if (entries[i].get()) {
-      access_times[i] = entries[i]->GetLastUsed();
-      if (newest < 0) {
-        DCHECK_LT(oldest, 0);
-        newest = oldest = i;
-        continue;
-      }
-      if (access_times[i] > access_times[newest])
-        newest = i;
-      if (access_times[i] < access_times[oldest])
-        oldest = i;
-    }
-  }
-
-  if (newest < 0 || oldest < 0)
-    return NULL;
-
-  EntryImpl* next_entry;
-  if (forward) {
-    next_entry = entries[newest].get();
-    iterator->list = static_cast<Rankings::List>(newest);
-  } else {
-    next_entry = entries[oldest].get();
-    iterator->list = static_cast<Rankings::List>(oldest);
-  }
-
-  *iter = iterator.release();
-  next_entry->AddRef();
-  return next_entry;
-}
-
-void BackendImpl::AddStorageSize(int32 bytes) {
-  data_->header.num_bytes += bytes;
-  DCHECK_GE(data_->header.num_bytes, 0);
-}
-
-void BackendImpl::SubstractStorageSize(int32 bytes) {
-  data_->header.num_bytes -= bytes;
-  DCHECK_GE(data_->header.num_bytes, 0);
-}
-
-void BackendImpl::IncreaseNumRefs() {
+    result = net::ERR_FAILED;
+    *work_item->iter_buffer() = NULL;
+    *work_item->entry_buffer() = entry;
+  }
+
+  if (!work_item->user_callback().is_null())
+    work_item->user_callback().Run(result);
+}
+
+void BackendImplV3::CloseDoomedEntries() {
+  // Copy the current map to make sure no new entries are deleted.
+  EntriesMap to_delete(entries_to_delete_);
+  for (EntriesMap::iterator it = to_delete.begin();
+       it != to_delete.end(); ++it) {
+    it->second->Close();
+  }
+}
+
+void BackendImplV3::ReleaseRecentEntries() {
+  for (EntriesSet::iterator it = recent_entries_.begin();
+       it != recent_entries_.end(); ++it) {
+    (*it)->Release();
+  }
+  recent_entries_.clear();
+}
+
+void BackendImplV3::UpdateDeletedEntries() {
+  for (size_t i = 0; i < deleted_entries_.size(); i++) {
+    CellInfo& cell_info = deleted_entries_[i];
+    index_.SetSate(cell_info.hash, cell_info.address, ENTRY_FREE);
+  }
+  deleted_entries_.clear();
+}
+
+void BackendImplV3::AddStorageSize(int32 bytes) {
+  index_.header()->num_bytes += bytes;
+  DCHECK_GE(index_.header()->num_bytes, 0);
+}
+
+void BackendImplV3::SubstractStorageSize(int32 bytes) {
+  index_.header()->num_bytes -= bytes;
+  DCHECK_GE(index_.header()->num_bytes, 0);
+}
+
+void BackendImplV3::IncreaseNumRefs() {
   num_refs_++;
   if (max_refs_ < num_refs_)
     max_refs_ = num_refs_;
 }
 
-void BackendImpl::DecreaseNumRefs() {
+void BackendImplV3::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) {
+}
+
+void BackendImplV3::IncreaseNumEntries() {
+  index_.header()->num_entries++;
+  DCHECK_GT(index_.header()->num_entries, 0);
+}
+
+void BackendImplV3::DecreaseNumEntries() {
+  index_.header()->num_entries--;
+  if (index_.header()->num_entries < 0) {
     NOTREACHED();
-    data_->header.num_entries = 0;
-  }
-}
-
-int BackendImpl::SyncInit() {
+    index_.header()->num_entries = 0;
+  }
+}
+
+void BackendImplV3::PostWorkItem(WorkItem* work_item) {
+  if (!worker_)
+    return;
+  Trace("Post task 0x%p %d flags 0x%x", work_item, work_item->type(),
+        work_item->flags());
+
+  // Long story short: we expect to see the work item back on this thread.
+  // If the task is not executed we'll leak work_item, but that should only
+  // happen at shutdown.
+  work_item->AddRef();
+  work_item->set_closure(base::Bind(&BackendImplV3::OnWorkDone,
+                                    ptr_factory_.GetWeakPtr()));
+  cache_thread_->PostTask(
+      FROM_HERE,
+      base::Bind(&BackendImplV3::Worker::OnDoWork, worker_, work_item));
+}
+
+void BackendImplV3::OnWorkDone(WorkItem* work_item) {
+  Trace("Task done 0x%p %d flags 0x%x", work_item, work_item->type(),
+        work_item->flags());
+  // Balance the reference from PostWorkItem.
+  scoped_refptr<WorkItem> my_work_item;
+  my_work_item.swap(&work_item);
+
+  if (!worker_) {
+    // This may be called after CleanupForTest was called.
+    if (!my_work_item->user_callback().is_null())
+      my_work_item->user_callback().Run(my_work_item->result());
+    return;
+  }
+
+  switch (my_work_item->type()) {
+    case WorkItem::WORK_INIT: return OnInitComplete(my_work_item);
+    case WorkItem::WORK_RESTART: return OnInitComplete(my_work_item);
+    case WorkItem::WORK_GROW_INDEX: return OnGrowIndexComplete(my_work_item);
+    case WorkItem::WORK_GROW_FILES: return OnGrowFilesComplete(my_work_item);
+    case WorkItem::WORK_OPEN_ENTRY: return OnOpenEntryComplete(my_work_item);
+    default: return OnOperationComplete(my_work_item);
+  }
+}
+
+void BackendImplV3::OnInitComplete(WorkItem* work_item) {
+  int rv = work_item->result();
+  if (rv != ERR_NO_ERROR && rv != ERR_CACHE_CREATED &&
+      rv != ERR_PREVIOUS_CRASH) {
+    ReportError(rv);
+    return work_item->user_callback().Run(net::ERR_FAILED);
+  }
+
 #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;
+
+  num_refs_ = 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>());
+    // Create a recurrent timer of 30 secs (90 minutes for tests).
+    int timer_delay = user_flags_ & BASIC_UNIT_TEST ? 90 * 60 * 1000 :
+                                                      kTimerSeconds * 1000;
+    timer_.reset(new base::RepeatingTimer<BackendImplV3>());
     timer_->Start(FROM_HERE, TimeDelta::FromMilliseconds(timer_delay), this,
-                  &BackendImpl::OnStatsTimer);
-  }
-
+                  &BackendImplV3::OnTimerTick);
+  }
+  Trace("Init");
   init_ = true;
-  Trace("Init");
-
-  if (data_->header.experiment != NO_EXPERIMENT &&
+
+  scoped_ptr<InitResult> result = work_item->init_result();
+  index_.Init(&result.get()->index_data);
+
+  if (index_.header()->experiment != NO_EXPERIMENT &&
       cache_type_ != net::DISK_CACHE) {
     // No experiment for other caches.
-    return net::ERR_FAILED;
-  }
-
-  if (!(user_flags_ & kNoRandom)) {
+    ReportError(ERR_INIT_FAILED);
+    return work_item->user_callback().Run(net::ERR_FAILED);
+  }
+
+  if (!(user_flags_ & BASIC_UNIT_TEST)) {
     // The unit test controls directly what to test.
-    new_eviction_ = (cache_type_ == net::DISK_CACHE);
+    lru_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;
+    return work_item->user_callback().Run(net::ERR_FAILED);
+  }
+  AdjustMaxCacheSize();
+
+  block_files_.Init(result->block_bitmaps);
 
   // We want to minimize the changes to cache for an AppCache.
   if (cache_type() == net::APP_CACHE) {
-    DCHECK(!new_eviction_);
+    DCHECK(lru_eviction_);
     read_only_ = true;
   } else if (cache_type() == net::SHADER_CACHE) {
-    DCHECK(!new_eviction_);
+    DCHECK(lru_eviction_);
   }
 
   eviction_.Init(this);
 
-  // stats_ and rankings_ may end up calling back to us so we better be enabled.
+  int64 errors, full_dooms, partial_dooms, last_report;
+  errors = full_dooms = partial_dooms = last_report = 0;
+  if (work_item->type() == WorkItem::WORK_RESTART) {
+    int64 errors = stats_.GetCounter(Stats::FATAL_ERROR);
+    int64 full_dooms = stats_.GetCounter(Stats::DOOM_CACHE);
+    int64 partial_dooms = stats_.GetCounter(Stats::DOOM_RECENT);
+    int64 last_report = stats_.GetCounter(Stats::LAST_REPORT);
+  }
+
+  if (!InitStats(result->stats_data.get())) {
+    ReportError(ERR_INIT_FAILED);
+    return work_item->user_callback().Run(net::ERR_FAILED);
+  }
+
   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;
-}
-
-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;
+  if (work_item->type() == WorkItem::WORK_RESTART) {
+    stats_.SetCounter(Stats::FATAL_ERROR, errors);
+    stats_.SetCounter(Stats::DOOM_CACHE, full_dooms);
+    stats_.SetCounter(Stats::DOOM_RECENT, partial_dooms);
+    stats_.SetCounter(Stats::LAST_REPORT, last_report);
+  }
+
+  ReportError(rv);
+  return work_item->user_callback().Run(net::OK);
+}
+
+void BackendImplV3::OnGrowIndexComplete(WorkItem* work_item) {
+  if (work_item->result() != ERR_NO_ERROR || disabled_ ||
+      (work_item->flags() & WorkItem::WORK_COMPLETE)) {
+    growing_index_ = false;
+    return;
+  }
+
+  scoped_ptr<InitResult> result = work_item->init_result();
+  index_.Init(&result.get()->index_data);
+  work_item->set_flags(WorkItem::WORK_COMPLETE);
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::OnGrowFilesComplete(WorkItem* work_item) {
+  if (work_item->result() != ERR_NO_ERROR || disabled_ ||
+      (work_item->flags() & WorkItem::WORK_COMPLETE)) {
+    growing_files_ = false;
+    return;
+  }
+
+  scoped_ptr<InitResult> result = work_item->init_result();
+  block_files_.Init(result->block_bitmaps);
+  work_item->set_flags(WorkItem::WORK_COMPLETE);
+  PostWorkItem(work_item);
+}
+
+void BackendImplV3::OnOperationComplete(WorkItem* work_item) {
+  if (work_item->result() < 0 && work_item->owner_entry()) {
+    // Make sure that there's a call to Close() after Doom().
+    work_item->owner_entry()->AddRef();
+    work_item->owner_entry()->Doom();
+    work_item->owner_entry()->Close();
+  }
+
+  if (!work_item->user_callback().is_null())
+    work_item->user_callback().Run(work_item->result());
+}
+
+
+void BackendImplV3::OnOpenEntryComplete(WorkItem* work_item) {
+  Trace("Open complete");
+  if (work_item->flags() & WorkItem::WORK_FOR_RESURRECT)
+    return OnOpenForResurrectComplete(work_item);
+
+  if (work_item->flags() & WorkItem::WORK_FOR_EVICT)
+    return OnEvictEntryComplete(work_item);
+
+  if (work_item->flags() & WorkItem::WORK_FOR_ITERATION)
+    return OnOpenNextComplete(work_item);
+
+  if (work_item->result() == ERR_NO_ERROR) {
+    EntryImplV3* entry;
+    int error = NewEntry(work_item, &entry);
+    if (!error) {
+      if (work_item->flags() & WorkItem::WORK_FOR_DOOM) {
+        entry->Doom();
+        entry->Close();
+      } else {
+        eviction_.OnOpenEntry(entry);
+        entry_count_++;
+        if (work_item->flags() & WorkItem::WORK_FOR_UPDATE) {
+          UpdateRank(entry, true);
+          return;
+        }
+        *work_item->entry_buffer() = entry;
+
+        Trace("Open hash 0x%x end: 0x%x", entry->GetHash(),
+              entry->GetAddress().value());
+        stats_.OnEvent(Stats::OPEN_HIT);
+        SIMPLE_STATS_COUNTER("disk_cache.hit");
+      }
+
+      work_item->user_callback().Run(net::OK);
+      return;
     }
   }
 
-  // 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)) {
+  if (work_item->entries()->current >= work_item->entries()->cells.size() - 1) {// - 1?
+    // Not found.
+    work_item->user_callback().Run(net::ERR_FAILED);
+    return;
+  }
+
+  //+post a task to delete the cell
+
+  // Open the next entry on the list.
+  work_item->entries()->current++;
+  if (work_item->entries()->current < work_item->entries()->cells.size())
+    PostWorkItem(work_item);
+}
+
+void BackendImplV3::OnOpenForResurrectComplete(WorkItem* work_item) {
+  if (work_item->result() == ERR_NO_ERROR) {
+    EntryImplV3* deleted_entry;
+    int error = NewEntry(work_item, &deleted_entry);
+    if (!error) {
+      scoped_ptr<ShortEntryRecord> entry_record =
+          deleted_entry->GetShortEntryRecord();
+      CHECK(entry_record);
+      if (!entry_record) {
+        // This is an active entry.
+        deleted_entry->Close();
+        stats_.OnEvent(Stats::CREATE_MISS);
+        Trace("create entry miss ");
+        work_item->user_callback().Run(net::ERR_FAILED);//doesn't make any sense
+        return;
+      }
+
+      // We are attempting to create an entry and found out that the entry was
+      // previously deleted.
+
+      stats_.OnEvent(Stats::RESURRECT_HIT);
+      Trace("Resurrect entry hit ");
+      deleted_entry->Doom();
+      deleted_entry->Close();
+
+      int rv =
+        OnCreateEntryComplete(work_item->key(), deleted_entry->GetHash(),
+                              entry_record.get(), work_item->entry_buffer(),
+                              work_item->user_callback());
+      DCHECK_EQ(rv, net::OK);
+      return;
+    }
+  }
+
+  if (work_item->entries()->current >= work_item->entries()->cells.size()) {
+    // Not found.
+    work_item->user_callback().Run(net::ERR_FAILED);
+    return;
+  }
+
+  //+post a task to delete the cell
+
+  // Open the next entry on the list.
+  work_item->entries()->current++;
+  if (work_item->entries()->current < work_item->entries()->cells.size())
+    PostWorkItem(work_item);
+}
+
+void BackendImplV3::OnEvictEntryComplete(WorkItem* work_item) {
+  if (work_item->result() != ERR_NO_ERROR)
+    return eviction_.OnEvictEntryComplete();
+
+  EntryCell old_cell =
+      index_.FindEntryCell(work_item->entries()->cells[0].hash(),
+                           work_item->entries()->cells[0].GetAddress());
+  DCHECK(old_cell.IsValid());
+
+  if (!(work_item->flags() & WorkItem::WORK_NO_COPY)) {
+    EntryCell new_cell =
+        index_.FindEntryCell(work_item->entries()->cells[1].hash(),
+                             work_item->entries()->cells[1].GetAddress());
+    DCHECK(new_cell.IsValid());
+  }
+
+  EntryImplV3* entry;
+  int error = NewEntry(work_item, &entry);
+  if (!error) {
+    entry->Doom();
+    entry->Close();
+  }
+
+  //+delete old_cell after a timer (so add to deleted entries).
+
+  eviction_.OnEvictEntryComplete();
+}
+
+void BackendImplV3::OnOpenNextComplete(WorkItem* work_item) {
+  Trace("OpenNext complete, work item 0x%p", work_item);
+  if (work_item->result() != ERR_NO_ERROR) {
+    OpenNext(work_item);  // Ignore result.
+    return;
+  }
+
+  EntryImplV3* entry;
+  int error = NewEntry(work_item, &entry);
+  if (!error) {
+    if (work_item->flags() & WorkItem::WORK_FOR_DOOM_RANGE)
+      Doom(entry, work_item);
+    else
+      return UpdateIterator(entry, work_item);
+  }
+
+  // Grab another entry.
+  OpenNext(work_item);  // Ignore result.
+}
+
+int BackendImplV3::OnCreateEntryComplete(const std::string& key, uint32 hash,
+                                         ShortEntryRecord* short_record,
+                                         Entry** entry,
+                                         const CompletionCallback& callback) {
+  // Create a new object in memory and return it to the caller.
+  Addr entry_address;
+  Trace("Create complete hash 0x%x", hash);
+  if (!block_files_.CreateBlock(BLOCK_ENTRIES, 1, &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));
+    return net::ERR_FAILED;
+  }
+
+  EntryCell cell = index_.CreateEntryCell(hash, entry_address);
+  if (!cell.IsValid()) {
+    block_files_.DeleteBlock(entry_address);
+    return net::ERR_FAILED;
+  }
+
+  scoped_refptr<EntryImplV3> cache_entry(
+      new EntryImplV3(this, cell.GetAddress(), 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->CreateEntry(key, hash, short_record);
   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();
+  open_entries_[cell.GetAddress().value()] = cache_entry;
+
   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);
+  if (short_record)
+    eviction_.OnResurrectEntry(cache_entry);
+  else
+    eviction_.OnCreateEntry(cache_entry);
+
   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() {
+  *entry = cache_entry.get();
+
+  if (short_record)
+    callback.Run(net::OK);
+
+  return net::OK;
+}
+
+void BackendImplV3::LogStats() {
   StatsItems stats;
   GetStats(&stats);
 
   for (size_t index = 0; index < stats.size(); index++)
     VLOG(1) << stats[index].first << ": " << stats[index].second;
 }
 
-void BackendImpl::ReportStats() {
-  CACHE_UMA(COUNTS, "Entries", 0, data_->header.num_entries);
+void BackendImplV3::ReportStats() {
+  IndexHeaderV3* header = index_.header();
+  CACHE_UMA(COUNTS, "Entries", 0, header->num_entries);
 
-  int current_size = data_->header.num_bytes / (1024 * 1024);
+  int current_size = header->num_bytes / (1024 * 1024);
   int max_size = max_size_ / (1024 * 1024);
-  int hit_ratio_as_percentage = stats_.GetHitRatio();
 
-  CACHE_UMA(COUNTS_10000, "Size2", 0, current_size);
-  // For any bin in HitRatioBySize2, the hit ratio of caches of that size is the
-  // ratio of that bin's total count to the count in the same bin in the Size2
-  // histogram.
-  if (base::RandInt(0, 99) < hit_ratio_as_percentage)
-    CACHE_UMA(COUNTS_10000, "HitRatioBySize2", 0, current_size);
-  CACHE_UMA(COUNTS_10000, "MaxSize2", 0, max_size);
+  CACHE_UMA(COUNTS_10000, "Size", 0, current_size);
+  CACHE_UMA(COUNTS_10000, "MaxSize", 0, max_size);
   if (!max_size)
     max_size++;
   CACHE_UMA(PERCENTAGE, "UsedSpace", 0, current_size * 100 / max_size);
 
-  CACHE_UMA(COUNTS_10000, "AverageOpenEntries2", 0,
+  CACHE_UMA(COUNTS_10000, "AverageOpenEntries", 0,
             static_cast<int>(stats_.GetCounter(Stats::OPEN_ENTRIES)));
-  CACHE_UMA(COUNTS_10000, "MaxOpenEntries2", 0,
+  CACHE_UMA(COUNTS_10000, "MaxOpenEntries", 0,
             static_cast<int>(stats_.GetCounter(Stats::MAX_ENTRIES)));
   stats_.SetCounter(Stats::MAX_ENTRIES, 0);
 
   CACHE_UMA(COUNTS_10000, "TotalFatalErrors", 0,
             static_cast<int>(stats_.GetCounter(Stats::FATAL_ERROR)));
   CACHE_UMA(COUNTS_10000, "TotalDoomCache", 0,
             static_cast<int>(stats_.GetCounter(Stats::DOOM_CACHE)));
   CACHE_UMA(COUNTS_10000, "TotalDoomRecentEntries", 0,
             static_cast<int>(stats_.GetCounter(Stats::DOOM_RECENT)));
   stats_.SetCounter(Stats::FATAL_ERROR, 0);
   stats_.SetCounter(Stats::DOOM_CACHE, 0);
   stats_.SetCounter(Stats::DOOM_RECENT, 0);
 
   int64 total_hours = stats_.GetCounter(Stats::TIMER) / 120;
-  if (!data_->header.create_time || !data_->header.lru.filled) {
-    int cause = data_->header.create_time ? 0 : 1;
-    if (!data_->header.lru.filled)
-      cause |= 2;
-    CACHE_UMA(CACHE_ERROR, "ShortReport", 0, cause);
+  if (!(header->flags & CACHE_EVICTED)) {
     CACHE_UMA(HOURS, "TotalTimeNotFull", 0, static_cast<int>(total_hours));
     return;
   }
 
   // This is an up to date client that will report FirstEviction() data. After
   // that event, start reporting this:
 
   CACHE_UMA(HOURS, "TotalTime", 0, static_cast<int>(total_hours));
-  // For any bin in HitRatioByTotalTime, the hit ratio of caches of that total
-  // time is the ratio of that bin's total count to the count in the same bin in
-  // the TotalTime histogram.
-  if (base::RandInt(0, 99) < hit_ratio_as_percentage)
-    CACHE_UMA(HOURS, "HitRatioByTotalTime", 0, implicit_cast<int>(total_hours));
 
   int64 use_hours = stats_.GetCounter(Stats::LAST_REPORT_TIMER) / 120;
   stats_.SetCounter(Stats::LAST_REPORT_TIMER, stats_.GetCounter(Stats::TIMER));
 
   // We may see users with no use_hours at this point if this is the first time
   // we are running this code.
   if (use_hours)
     use_hours = total_hours - use_hours;
 
-  if (!use_hours || !GetEntryCount() || !data_->header.num_bytes)
+  if (!use_hours || !GetEntryCount() || !header->num_bytes)
     return;
 
   CACHE_UMA(HOURS, "UseTime", 0, static_cast<int>(use_hours));
-  // For any bin in HitRatioByUseTime, the hit ratio of caches of that use time
-  // is the ratio of that bin's total count to the count in the same bin in the
-  // UseTime histogram.
-  if (base::RandInt(0, 99) < hit_ratio_as_percentage)
-    CACHE_UMA(HOURS, "HitRatioByUseTime", 0, implicit_cast<int>(use_hours));
-  CACHE_UMA(PERCENTAGE, "HitRatio", 0, hit_ratio_as_percentage);
-
+  
   int64 trim_rate = stats_.GetCounter(Stats::TRIM_ENTRY) / use_hours;
   CACHE_UMA(COUNTS, "TrimRate", 0, static_cast<int>(trim_rate));
 
-  int avg_size = data_->header.num_bytes / GetEntryCount();
+  int avg_size = header->num_bytes / GetEntryCount();
   CACHE_UMA(COUNTS, "EntrySize", 0, avg_size);
-  CACHE_UMA(COUNTS, "EntriesFull", 0, data_->header.num_entries);
-
-  CACHE_UMA(PERCENTAGE, "IndexLoad", 0,
-            data_->header.num_entries * 100 / (mask_ + 1));
+  CACHE_UMA(COUNTS, "EntriesFull", 0, header->num_entries);
 
   int large_entries_bytes = stats_.GetLargeEntriesSize();
-  int large_ratio = large_entries_bytes * 100 / data_->header.num_bytes;
+  int large_ratio = large_entries_bytes * 100 / header->num_bytes;
   CACHE_UMA(PERCENTAGE, "LargeEntriesRatio", 0, large_ratio);
 
-  if (new_eviction_) {
+  if (!lru_eviction_) {
     CACHE_UMA(PERCENTAGE, "ResurrectRatio", 0, stats_.GetResurrectRatio());
     CACHE_UMA(PERCENTAGE, "NoUseRatio", 0,
-              data_->header.lru.sizes[0] * 100 / data_->header.num_entries);
+              header->num_no_use_entries * 100 / header->num_entries);
     CACHE_UMA(PERCENTAGE, "LowUseRatio", 0,
-              data_->header.lru.sizes[1] * 100 / data_->header.num_entries);
+              header->num_low_use_entries * 100 / header->num_entries);
     CACHE_UMA(PERCENTAGE, "HighUseRatio", 0,
-              data_->header.lru.sizes[2] * 100 / data_->header.num_entries);
+              header->num_high_use_entries * 100 / header->num_entries);
     CACHE_UMA(PERCENTAGE, "DeletedRatio", 0,
-              data_->header.lru.sizes[4] * 100 / data_->header.num_entries);
+              header->num_evicted_entries * 100 / header->num_entries);
   }
 
   stats_.ResetRatios();
   stats_.SetCounter(Stats::TRIM_ENTRY, 0);
 
   if (cache_type_ == net::DISK_CACHE)
     block_files_.ReportStats();
 }
 
-void BackendImpl::ReportError(int error) {
+void BackendImplV3::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_);
+bool BackendImplV3::CheckIndex() {
+  if (index_.header()->flags & CACHE_EVICTION_2)
+    lru_eviction_ = false;
 
-  size_t current_size = index_->GetLength();
-  if (current_size < sizeof(Index)) {
+  /*
+  if (!index_.header()->table_len) {
+    LOG(ERROR) << "Invalid table size";
+    return false;
+  }
+
+  if (current_size < GetIndexSize(index_.header()->table_len) ||
+      index_.header()->table_len & (kBaseTableLen - 1)) {
     LOG(ERROR) << "Corrupt Index file";
     return false;
   }
 
-  if (new_eviction_) {
-    // We support versions 2.0 and 2.1, upgrading 2.0 to 2.1.
-    if (kIndexMagic != data_->header.magic ||
-        kCurrentVersion >> 16 != data_->header.version >> 16) {
-      LOG(ERROR) << "Invalid file version or magic";
-      return false;
-    }
-    if (kCurrentVersion == data_->header.version) {
-      // We need file version 2.1 for the new eviction algorithm.
-      UpgradeTo2_1();
-    }
-  } else {
-    if (kIndexMagic != data_->header.magic ||
-        kCurrentVersion != data_->header.version) {
-      LOG(ERROR) << "Invalid file version or magic";
-      return false;
-    }
-  }
-
-  if (!data_->header.table_len) {
-    LOG(ERROR) << "Invalid table size";
-    return false;
-  }
-
-  if (current_size < GetIndexSize(data_->header.table_len) ||
-      data_->header.table_len & (kBaseTableLen - 1)) {
-    LOG(ERROR) << "Corrupt Index file";
-    return false;
-  }
-
-  AdjustMaxCacheSize(data_->header.table_len);
+  AdjustMaxCacheSize(index_.header()->table_len);
 
 #if !defined(NET_BUILD_STRESS_CACHE)
-  if (data_->header.num_bytes < 0 ||
+  if (index_.header()->num_bytes < 0 ||
       (max_size_ < kint32max - kDefaultCacheSize &&
-       data_->header.num_bytes > max_size_ + kDefaultCacheSize)) {
+       index_.header()->num_bytes > max_size_ + kDefaultCacheSize)) {
     LOG(ERROR) << "Invalid cache (current) size";
     return false;
   }
 #endif
 
-  if (data_->header.num_entries < 0) {
+  if (index_.header()->num_entries < 0) {
     LOG(ERROR) << "Invalid number of entries";
     return false;
   }
 
   if (!mask_)
-    mask_ = data_->header.table_len - 1;
+    mask_ = index_.header()->table_len - 1;
 
   // Load the table into memory with a single read.
-  scoped_ptr<char[]> buf(new char[current_size]);
+  scoped_array<char> buf(new char[current_size]);
   return index_->Read(buf.get(), current_size, 0);
+  */
+
+  //Make sure things look fine, maybe scan the whole thing if not.
+  return true;
 }
 
-int BackendImpl::CheckAllEntries() {
+int BackendImplV3::CheckAllEntries() {
+  /*
   int num_dirty = 0;
   int num_entries = 0;
   DCHECK(mask_ < kuint32max);
   for (unsigned int i = 0; i <= mask_; i++) {
     Addr address(data_->table[i]);
     if (!address.is_initialized())
       continue;
     for (;;) {
-      EntryImpl* tmp;
+      EntryImplV3* tmp;
       int ret = NewEntry(address, &tmp);
       if (ret) {
         STRESS_NOTREACHED();
         return ret;
       }
-      scoped_refptr<EntryImpl> cache_entry;
+      scoped_refptr<EntryImplV3> cache_entry;
       cache_entry.swap(&tmp);
 
       if (cache_entry->dirty())
         num_dirty++;
       else if (CheckEntry(cache_entry.get()))
         num_entries++;
       else
         return ERR_INVALID_ENTRY;
 
       DCHECK_EQ(i, cache_entry->entry()->Data()->hash & mask_);
       address.set_value(cache_entry->GetNextAddress());
       if (!address.is_initialized())
         break;
     }
   }
 
   Trace("CheckAllEntries End");
-  if (num_entries + num_dirty != data_->header.num_entries) {
+  if (num_entries + num_dirty != index_.header()->num_entries) {
     LOG(ERROR) << "Number of entries " << num_entries << " " << num_dirty <<
-                  " " << data_->header.num_entries;
-    DCHECK_LT(num_entries, data_->header.num_entries);
+                  " " << index_.header()->num_entries;
+    DCHECK_LT(num_entries, index_.header()->num_entries);
     return ERR_NUM_ENTRIES_MISMATCH;
   }
 
   return num_dirty;
+  */
+  return 0;
 }
 
-bool BackendImpl::CheckEntry(EntryImpl* cache_entry) {
+bool BackendImplV3::CheckEntry(EntryImplV3* cache_entry) {
+  /*
   bool ok = block_files_.IsValid(cache_entry->entry()->address());
   ok = ok && block_files_.IsValid(cache_entry->rankings()->address());
   EntryStore* data = cache_entry->entry()->Data();
   for (size_t i = 0; i < arraysize(data->data_addr); i++) {
     if (data->data_addr[i]) {
       Addr address(data->data_addr[i]);
       if (address.is_block_file())
         ok = ok && block_files_.IsValid(address);
     }
   }
 
   return ok && cache_entry->rankings()->VerifyHash();
+  */
+  return true;
 }
 
-int BackendImpl::MaxBuffersSize() {
+int BackendImplV3::MaxBuffersSize() {
   static int64 total_memory = base::SysInfo::AmountOfPhysicalMemory();
   static bool done = false;
 
   if (!done) {
     const int kMaxBuffersSize = 30 * 1024 * 1024;
 
     // We want to use up to 2% of the computer's memory.
     total_memory = total_memory * 2 / 100;
     if (total_memory > kMaxBuffersSize || total_memory <= 0)
       total_memory = kMaxBuffersSize;
 
     done = true;
   }
 
   return static_cast<int>(total_memory);
 }
 
 }  // namespace disk_cache