Disk cache: remove the hard coded list from rankings.cc

The rankings module now works with any list, not just
the first one. This is part of the support needed for
new eviction algorithms.

note: Rankings::CheckList() is basically the code that
was implementing the old Rankings::SelfCheck() (moved
with this cl).

The disk cache behavior is not changing with this cl.

Review URL: http://codereview.chromium.org/14141

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@7074 0039d316-1c4b-4281-b951-d872f2087c98

1 files changed, 157 insertions, 116 deletions

diff --git a/net/disk_cache/rankings.cc b/net/disk_cache/rankings.cc
index b690c75..286998e 100644
--- a/net/disk_cache/rankings.cc
+++ b/net/disk_cache/rankings.cc
@@ -16,14 +16,6 @@ disk_cache::RankCrashes g_rankings_crash = disk_cache::NO_CRASH;
 
 namespace {
 
-enum Lists {
-  NO_USE = 0,   // List of entries that have not been reused.
-  LOW_USE,      // List of entries with low reuse.
-  HIGH_USE,     // List of entries with high reuse.
-  DELETED,      // List of recently deleted or doomed entries.
-  LAST_ELEMENT
-};
-
 enum Operation {
   INSERT = 1,
   REMOVE
@@ -170,8 +162,8 @@ bool Rankings::Init(BackendImpl* backend) {
 
   control_data_ = backend_->GetLruData();
 
-  head_ = ReadHead();
-  tail_ = ReadTail();
+  ReadHeads();
+  ReadTails();
 
   if (control_data_->transaction)
     CompleteTransaction();
@@ -182,8 +174,10 @@ bool Rankings::Init(BackendImpl* backend) {
 
 void Rankings::Reset() {
   init_ = false;
-  head_.set_value(0);
-  tail_.set_value(0);
+  for (int i = 0; i < LAST_ELEMENT; i++) {
+    heads_[i].set_value(0);
+    tails_[i].set_value(0);
+  }
   control_data_ = NULL;
 }
 
@@ -223,16 +217,18 @@ bool Rankings::GetRanking(CacheRankingsBlock* rankings) {
   return true;
 }
 
-void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
+void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) {
   Trace("Insert 0x%x", node->address().value());
   DCHECK(node->HasData());
-  Transaction lock(control_data_, node->address(), INSERT, NO_USE);
-  CacheRankingsBlock head(backend_->File(head_), head_);
-  if (head_.is_initialized()) {
+  Addr& my_head = heads_[list];
+  Addr& my_tail = tails_[list];
+  Transaction lock(control_data_, node->address(), INSERT, list);
+  CacheRankingsBlock head(backend_->File(my_head), my_head);
+  if (my_head.is_initialized()) {
     if (!GetRanking(&head))
       return;
 
-    if (head.Data()->prev != head_.value() &&  // Normal path.
+    if (head.Data()->prev != my_head.value() &&  // Normal path.
         head.Data()->prev != node->address().value()) {  // FinishInsert().
       backend_->CriticalError(ERR_INVALID_LINKS);
       return;
@@ -244,14 +240,14 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
     UpdateIterators(&head);
   }
 
-  node->Data()->next = head_.value();
+  node->Data()->next = my_head.value();
   node->Data()->prev = node->address().value();
-  head_.set_value(node->address().value());
+  my_head.set_value(node->address().value());
 
-  if (!tail_.is_initialized() || tail_.value() == node->address().value()) {
-    tail_.set_value(node->address().value());
-    node->Data()->next = tail_.value();
-    WriteTail();
+  if (!my_tail.is_initialized() || my_tail.value() == node->address().value()) {
+    my_tail.set_value(node->address().value());
+    node->Data()->next = my_tail.value();
+    WriteTail(list);
     GenerateCrash(ON_INSERT_2);
   }
 
@@ -263,7 +259,7 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
   GenerateCrash(ON_INSERT_3);
 
   // The last thing to do is move our head to point to a node already stored.
-  WriteHead();
+  WriteHead(list);
   GenerateCrash(ON_INSERT_4);
 }
 
@@ -293,7 +289,7 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified) {
 //    2. a(x, r), r(a, r), head(x), tail(a)           WriteTail()
 //    3. a(x, a), r(a, r), head(x), tail(a)           prev.Store()
 //    4. a(x, a), r(0, 0), head(x), tail(a)           next.Store()
-void Rankings::Remove(CacheRankingsBlock* node) {
+void Rankings::Remove(CacheRankingsBlock* node, List list) {
   Trace("Remove 0x%x (0x%x 0x%x)", node->address().value(), node->Data()->next,
         node->Data()->prev);
   DCHECK(node->HasData());
@@ -310,35 +306,37 @@ void Rankings::Remove(CacheRankingsBlock* node) {
   if (!GetRanking(&next) || !GetRanking(&prev))
     return;
 
-  if (!CheckLinks(node, &prev, &next))
+  if (!CheckLinks(node, &prev, &next, list))
     return;
 
-  Transaction lock(control_data_, node->address(), REMOVE, NO_USE);
+  Transaction lock(control_data_, node->address(), REMOVE, list);
   prev.Data()->next = next.address().value();
   next.Data()->prev = prev.address().value();
   GenerateCrash(ON_REMOVE_1);
 
   CacheAddr node_value = node->address().value();
-  if (node_value == head_.value() || node_value == tail_.value()) {
-    if (head_.value() == tail_.value()) {
-      head_.set_value(0);
-      tail_.set_value(0);
-
-      WriteHead();
+  Addr& my_head = heads_[list];
+  Addr& my_tail = tails_[list];
+  if (node_value == my_head.value() || node_value == my_tail.value()) {
+    if (my_head.value() == my_tail.value()) {
+      my_head.set_value(0);
+      my_tail.set_value(0);
+
+      WriteHead(list);
       GenerateCrash(ON_REMOVE_2);
-      WriteTail();
+      WriteTail(list);
       GenerateCrash(ON_REMOVE_3);
-    } else if (node_value == head_.value()) {
-      head_.set_value(next.address().value());
+    } else if (node_value == my_head.value()) {
+      my_head.set_value(next.address().value());
       next.Data()->prev = next.address().value();
 
-      WriteHead();
+      WriteHead(list);
       GenerateCrash(ON_REMOVE_4);
-    } else if (node_value == tail_.value()) {
-      tail_.set_value(prev.address().value());
+    } else if (node_value == my_tail.value()) {
+      my_tail.set_value(prev.address().value());
       prev.Data()->next = prev.address().value();
 
-      WriteTail();
+      WriteTail(list);
       GenerateCrash(ON_REMOVE_5);
 
       // Store the new tail to make sure we can undo the operation if we crash.
@@ -366,10 +364,10 @@ void Rankings::Remove(CacheRankingsBlock* node) {
 // list. We want to avoid that case as much as we can (as while waiting for IO),
 // but the net effect is just an assert on debug when attempting to remove the
 // entry. Otherwise we'll need reentrant transactions, which is an overkill.
-void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified) {
+void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) {
   Time start = Time::Now();
-  Remove(node);
-  Insert(node, modified);
+  Remove(node, list);
+  Insert(node, modified, list);
   UMA_HISTOGRAM_TIMES(L"DiskCache.UpdateRank", Time::Now() - start);
 }
 
@@ -390,14 +388,17 @@ void Rankings::CompleteTransaction() {
   node.Data()->pointer = NULL;
   node.Store();
 
+  Addr& my_head = heads_[control_data_->operation_list];
+  Addr& my_tail = tails_[control_data_->operation_list];
+
   // We want to leave the node inside the list. The entry must me marked as
   // dirty, and will be removed later. Otherwise, we'll get assertions when
   // attempting to remove the dirty entry.
   if (INSERT == control_data_->operation) {
-    Trace("FinishInsert h:0x%x t:0x%x", head_.value(), tail_.value());
+    Trace("FinishInsert h:0x%x t:0x%x", my_head.value(), my_tail.value());
     FinishInsert(&node);
   } else if (REMOVE == control_data_->operation) {
-    Trace("RevertRemove h:0x%x t:0x%x", head_.value(), tail_.value());
+    Trace("RevertRemove h:0x%x t:0x%x", my_head.value(), my_tail.value());
     RevertRemove(&node);
   } else {
     NOTREACHED();
@@ -408,13 +409,15 @@ void Rankings::CompleteTransaction() {
 void Rankings::FinishInsert(CacheRankingsBlock* node) {
   control_data_->transaction = 0;
   control_data_->operation = 0;
-  if (head_.value() != node->address().value()) {
-    if (tail_.value() == node->address().value()) {
+  Addr& my_head = heads_[control_data_->operation_list];
+  Addr& my_tail = tails_[control_data_->operation_list];
+  if (my_head.value() != node->address().value()) {
+    if (my_tail.value() == node->address().value()) {
       // This part will be skipped by the logic of Insert.
-      node->Data()->next = tail_.value();
+      node->Data()->next = my_tail.value();
     }
 
-    Insert(node, true);
+    Insert(node, true, static_cast<List>(control_data_->operation_list));
   }
 
   // Tell the backend about this entry.
@@ -454,19 +457,22 @@ void Rankings::RevertRemove(CacheRankingsBlock* node) {
   if (node_value != next_addr.value())
     next.Data()->prev = node_value;
 
-  if (!head_.is_initialized() || !tail_.is_initialized()) {
-    head_.set_value(node_value);
-    tail_.set_value(node_value);
-    WriteHead();
-    WriteTail();
-  } else if (head_.value() == next.address().value()) {
-    head_.set_value(node_value);
+  List my_list = static_cast<List>(control_data_->operation_list);
+  Addr& my_head = heads_[my_list];
+  Addr& my_tail = tails_[my_list];
+  if (!my_head.is_initialized() || !my_tail.is_initialized()) {
+    my_head.set_value(node_value);
+    my_tail.set_value(node_value);
+    WriteHead(my_list);
+    WriteTail(my_list);
+  } else if (my_head.value() == next.address().value()) {
+    my_head.set_value(node_value);
     prev.Data()->next = next.address().value();
-    WriteHead();
-  } else if (tail_.value() == prev.address().value()) {
-    tail_.set_value(node_value);
+    WriteHead(my_list);
+  } else if (my_tail.value() == prev.address().value()) {
+    my_tail.set_value(node_value);
     next.Data()->prev = prev.address().value();
-    WriteTail();
+    WriteTail(my_list);
   }
 
   next.Store();
@@ -475,16 +481,18 @@ void Rankings::RevertRemove(CacheRankingsBlock* node) {
   control_data_->operation = 0;
 }
 
-CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node) {
+CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) {
   ScopedRankingsBlock next(this);
   if (!node) {
-    if (!head_.is_initialized())
+    Addr& my_head = heads_[list];
+    if (!my_head.is_initialized())
       return NULL;
-    next.reset(new CacheRankingsBlock(backend_->File(head_), head_));
+    next.reset(new CacheRankingsBlock(backend_->File(my_head), my_head));
   } else {
-    if (!tail_.is_initialized())
+    Addr& my_tail = tails_[list];
+    if (!my_tail.is_initialized())
       return NULL;
-    if (tail_.value() == node->address().value())
+    if (my_tail.value() == node->address().value())
       return NULL;
     Addr address(node->Data()->next);
     next.reset(new CacheRankingsBlock(backend_->File(address), address));
@@ -501,16 +509,18 @@ CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node) {
   return next.release();
 }
 
-CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node) {
+CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) {
   ScopedRankingsBlock prev(this);
   if (!node) {
-    if (!tail_.is_initialized())
+    Addr& my_tail = tails_[list];
+    if (!my_tail.is_initialized())
       return NULL;
-    prev.reset(new CacheRankingsBlock(backend_->File(tail_), tail_));
+    prev.reset(new CacheRankingsBlock(backend_->File(my_tail), my_tail));
   } else {
-    if (!head_.is_initialized())
+    Addr& my_head = heads_[list];
+    if (!my_head.is_initialized())
       return NULL;
-    if (head_.value() == node->address().value())
+    if (my_head.value() == node->address().value())
       return NULL;
     Addr address(node->Data()->prev);
     prev.reset(new CacheRankingsBlock(backend_->File(address), address));
@@ -532,40 +542,14 @@ void Rankings::FreeRankingsBlock(CacheRankingsBlock* node) {
 }
 
 int Rankings::SelfCheck() {
-  if (!head_.is_initialized()) {
-    if (!tail_.is_initialized())
-      return 0;
-    return ERR_INVALID_TAIL;
+  int total = 0;
+  for (int i = 0; i < LAST_ELEMENT; i++) {
+    int partial = CheckList(static_cast<List>(i));
+    if (partial < 0)
+      return partial;
+    total += partial;
   }
-  if (!tail_.is_initialized())
-    return ERR_INVALID_HEAD;
-
-  if (tail_.is_separate_file())
-    return ERR_INVALID_TAIL;
-
-  if (head_.is_separate_file())
-    return ERR_INVALID_HEAD;
-
-  int num_items = 0;
-  Addr address(head_.value());
-  Addr prev(head_.value());
-  scoped_ptr<CacheRankingsBlock> node;
-  do {
-    node.reset(new CacheRankingsBlock(backend_->File(address), address));
-    node->Load();
-    if (node->Data()->prev != prev.value())
-      return ERR_INVALID_PREV;
-    if (!CheckEntry(node.get()))
-      return ERR_INVALID_ENTRY;
-
-    prev.set_value(address.value());
-    address.set_value(node->Data()->next);
-    if (!address.is_initialized() || address.is_separate_file())
-      return ERR_INVALID_NEXT;
-
-    num_items++;
-  } while (node->address().value() != address.value());
-  return num_items;
+  return total;
 }
 
 bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) {
@@ -584,29 +568,31 @@ bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) {
   if (!data->next && !data->prev && from_list)
     return false;
 
-  if ((node->address().value() == data->prev) && (head_.value() != data->prev))
+  if ((node->address().value() == data->prev) && !IsHead(data->prev))
     return false;
 
-  if ((node->address().value() == data->next) && (tail_.value() != data->next))
+  if ((node->address().value() == data->next) && !IsTail(data->next))
     return false;
 
   return true;
 }
 
-Addr Rankings::ReadHead() {
-  return Addr(control_data_->heads[NO_USE]);
+void Rankings::ReadHeads() {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    heads_[i] = Addr(control_data_->heads[i]);
 }
 
-Addr Rankings::ReadTail() {
-  return Addr(control_data_->tails[NO_USE]);
+void Rankings::ReadTails() {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    tails_[i] = Addr(control_data_->tails[i]);
 }
 
-void Rankings::WriteHead() {
-  control_data_->heads[NO_USE] = head_.value();
+void Rankings::WriteHead(List list) {
+  control_data_->heads[list] = heads_[list].value();
 }
 
-void Rankings::WriteTail() {
-  control_data_->tails[NO_USE] = tail_.value();
+void Rankings::WriteTail(List list) {
+  control_data_->tails[list] = tails_[list].value();
 }
 
 bool Rankings::CheckEntry(CacheRankingsBlock* rankings) {
@@ -618,11 +604,11 @@ bool Rankings::CheckEntry(CacheRankingsBlock* rankings) {
 }
 
 bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
-                          CacheRankingsBlock* next) {
+                          CacheRankingsBlock* next, List list) {
   if ((prev->Data()->next != node->address().value() &&
-       head_.value() != node->address().value()) ||
+       heads_[list].value() != node->address().value()) ||
       (next->Data()->prev != node->address().value() &&
-       tail_.value() != node->address().value())) {
+       tails_[list].value() != node->address().value())) {
     LOG(ERROR) << "Inconsistent LRU.";
 
     if (prev->Data()->next == next->address().value() &&
@@ -653,6 +639,61 @@ bool Rankings::CheckSingleLink(CacheRankingsBlock* prev,
   return true;
 }
 
+int Rankings::CheckList(List list) {
+  Addr& my_head = heads_[list];
+  Addr& my_tail = tails_[list];
+  if (!my_head.is_initialized()) {
+    if (!my_tail.is_initialized())
+      return 0;
+    // If there is no head, having a tail is an error.
+    return ERR_INVALID_TAIL;
+  }
+  // If there is no tail, having a head is an error.
+  if (!my_tail.is_initialized())
+    return ERR_INVALID_HEAD;
+
+  if (my_tail.is_separate_file())
+    return ERR_INVALID_TAIL;
+
+  if (my_head.is_separate_file())
+    return ERR_INVALID_HEAD;
+
+  int num_items = 0;
+  Addr address(my_head.value());
+  Addr prev(my_head.value());
+  scoped_ptr<CacheRankingsBlock> node;
+  do {
+    node.reset(new CacheRankingsBlock(backend_->File(address), address));
+    node->Load();
+    if (node->Data()->prev != prev.value())
+      return ERR_INVALID_PREV;
+    if (!CheckEntry(node.get()))
+      return ERR_INVALID_ENTRY;
+
+    prev.set_value(address.value());
+    address.set_value(node->Data()->next);
+    if (!address.is_initialized() || address.is_separate_file())
+      return ERR_INVALID_NEXT;
+
+    num_items++;
+  } while (node->address().value() != address.value());
+  return num_items;
+}
+
+bool Rankings::IsHead(CacheAddr addr) {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    if (addr == heads_[i].value())
+      return true;
+  return false;
+}
+
+bool Rankings::IsTail(CacheAddr addr) {
+  for (int i = 0; i < LAST_ELEMENT; i++)
+    if (addr == tails_[i].value())
+      return true;
+  return false;
+}
+
 void Rankings::TrackRankingsBlock(CacheRankingsBlock* node,
                                   bool start_tracking) {
   if (!node)