From 7abcaea438b6205b44c1c4a51ebc4fa15ca74f9c Mon Sep 17 00:00:00 2001 From: "rvargas@google.com" Date: Wed, 17 Nov 2010 21:34:17 +0000 Subject: Disk cache: A dirty entry can point to a list that is not the actual list where the entry is stored. This CL recognizes that case and hanldes removing that entry from the lists, without saying that there is critical corruption. BUG=38859 TEST=net_unittests Review URL: http://codereview.chromium.org/5119001 git-svn-id: svn://svn.chromium.org/chrome/trunk/src@66518 0039d316-1c4b-4281-b951-d872f2087c98 --- net/disk_cache/backend_unittest.cc | 20 +++++++ net/disk_cache/rankings.cc | 107 +++++++++++++++++++++++++------------ net/disk_cache/rankings.h | 12 +++-- 3 files changed, 101 insertions(+), 38 deletions(-) (limited to 'net') diff --git a/net/disk_cache/backend_unittest.cc b/net/disk_cache/backend_unittest.cc index 4298456..bfb78b6 100644 --- a/net/disk_cache/backend_unittest.cc +++ b/net/disk_cache/backend_unittest.cc @@ -1313,6 +1313,26 @@ TEST_F(DiskCacheBackendTest, NewEvictionInvalidEntry2) { BackendInvalidEntry2(); } +TEST_F(DiskCacheBackendTest, NewEvictionInvalidEntry3) { + ASSERT_TRUE(CopyTestCache("bad_rankings3")); + DisableFirstCleanup(); + SetNewEviction(); + InitCache(); + + // The second entry is dirty, but removing it should not corrupt the list. + disk_cache::Entry* entry; + ASSERT_NE(net::OK, OpenEntry("the second key", &entry)); + ASSERT_EQ(net::OK, OpenEntry("the first key", &entry)); + + // This should not delete the cache. + entry->Doom(); + FlushQueueForTest(); + entry->Close(); + + ASSERT_EQ(net::OK, OpenEntry("some other key", &entry)); + entry->Close(); +} + // We want to be able to deal with abnormal dirty entries. void DiskCacheBackendTest::BackendNotMarkedButDirty(const std::string& name) { ASSERT_TRUE(CopyTestCache(name)); diff --git a/net/disk_cache/rankings.cc b/net/disk_cache/rankings.cc index 1e9e06b..801d387 100644 --- a/net/disk_cache/rankings.cc +++ b/net/disk_cache/rankings.cc @@ -174,6 +174,14 @@ void GenerateCrash(CrashLocation location) { #endif // NDEBUG } +// Update the timestamp fields of |node|. +void UpdateTimes(disk_cache::CacheRankingsBlock* node, bool modified) { + base::Time now = base::Time::Now(); + node->Data()->last_used = now.ToInternalValue(); + if (modified) + node->Data()->last_modified = now.ToInternalValue(); +} + } // namespace namespace disk_cache { @@ -273,7 +281,7 @@ void Rankings::ConvertToLongLived(CacheRankingsBlock* rankings) { } void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { - Trace("Insert 0x%x", node->address().value()); + Trace("Insert 0x%x l %d", node->address().value(), list); DCHECK(node->HasData()); Addr& my_head = heads_[list]; Addr& my_tail = tails_[list]; @@ -306,10 +314,7 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { GenerateCrash(ON_INSERT_2); } - Time now = Time::Now(); - node->Data()->last_used = now.ToInternalValue(); - if (modified) - node->Data()->last_modified = now.ToInternalValue(); + UpdateTimes(node, modified); node->Store(); GenerateCrash(ON_INSERT_3); @@ -346,15 +351,17 @@ void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { // 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, List list) { - Trace("Remove 0x%x (0x%x 0x%x)", node->address().value(), node->Data()->next, - node->Data()->prev); + Trace("Remove 0x%x (0x%x 0x%x) l %d", node->address().value(), + node->Data()->next, node->Data()->prev, list); DCHECK(node->HasData()); InvalidateIterators(node); Addr next_addr(node->Data()->next); Addr prev_addr(node->Data()->prev); if (!next_addr.is_initialized() || next_addr.is_separate_file() || !prev_addr.is_initialized() || prev_addr.is_separate_file()) { - LOG(WARNING) << "Invalid rankings info."; + if (next_addr.is_initialized() || prev_addr.is_initialized()) { + LOG(ERROR) << "Invalid rankings info."; + } return; } @@ -363,7 +370,7 @@ void Rankings::Remove(CacheRankingsBlock* node, List list) { if (!GetRanking(&next) || !GetRanking(&prev)) return; - if (!CheckLinks(node, &prev, &next, list)) + if (!CheckLinks(node, &prev, &next, &list)) return; Transaction lock(control_data_, node->address(), REMOVE, list); @@ -423,6 +430,13 @@ void Rankings::Remove(CacheRankingsBlock* node, List list) { // 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, List list) { + Addr& my_head = heads_[list]; + if (my_head.value() == node->address().value()) { + UpdateTimes(node, modified); + node->set_modified(); + return; + } + TimeTicks start = TimeTicks::Now(); Remove(node, list); Insert(node, modified, list); @@ -649,10 +663,11 @@ bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) { if (!data->next && !data->prev && from_list) return false; - if ((node->address().value() == data->prev) && !IsHead(data->prev)) + List list = NO_USE; // Initialize it to something. + if ((node->address().value() == data->prev) && !IsHead(data->prev, &list)) return false; - if ((node->address().value() == data->next) && !IsTail(data->next)) + if ((node->address().value() == data->next) && !IsTail(data->next, &list)) return false; return true; @@ -685,26 +700,42 @@ bool Rankings::CheckEntry(CacheRankingsBlock* rankings) { } bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, - CacheRankingsBlock* next, List list) { - if ((prev->Data()->next != node->address().value() && - heads_[list].value() != node->address().value()) || - (next->Data()->prev != node->address().value() && - tails_[list].value() != node->address().value())) { - LOG(ERROR) << "Inconsistent LRU."; + CacheRankingsBlock* next, List* list) { + CacheAddr node_addr = node->address().value(); + if (prev->Data()->next == node_addr && + next->Data()->prev == node_addr) { + // A regular linked node. + return true; + } - if (prev->Data()->next == next->address().value() && - next->Data()->prev == prev->address().value()) { - // The list is actually ok, node is wrong. - node->Data()->next = 0; - node->Data()->prev = 0; - node->Store(); - return false; - } - backend_->CriticalError(ERR_INVALID_LINKS); + Trace("CheckLinks 0x%x (0x%x 0x%x)", node_addr, + prev->Data()->next, next->Data()->prev); + + if (node_addr != prev->address().value() && + node_addr != next->address().value() && + prev->Data()->next == next->address().value() && + next->Data()->prev == prev->address().value()) { + // The list is actually ok, node is wrong. + Trace("node 0x%x out of list %d", node_addr, list); + node->Data()->next = 0; + node->Data()->prev = 0; + node->Store(); return false; } - return true; + if (prev->Data()->next == node_addr || + next->Data()->prev == node_addr) { + // Only one link is weird, lets double check. + if (prev->Data()->next != node_addr && IsHead(node_addr, list)) + return true; + + if (next->Data()->prev != node_addr && IsTail(node_addr, list)) + return true; + } + + LOG(ERROR) << "Inconsistent LRU."; + backend_->CriticalError(ERR_INVALID_LINKS); + return false; } bool Rankings::CheckSingleLink(CacheRankingsBlock* prev, @@ -761,17 +792,27 @@ int Rankings::CheckList(List list) { return num_items; } -bool Rankings::IsHead(CacheAddr addr) { - for (int i = 0; i < LAST_ELEMENT; i++) - if (addr == heads_[i].value()) +bool Rankings::IsHead(CacheAddr addr, List* list) { + for (int i = 0; i < LAST_ELEMENT; i++) { + if (addr == heads_[i].value()) { + if (*list != i) + Trace("Changing list %d to %d", *list, i); + *list = static_cast(i); return true; + } + } return false; } -bool Rankings::IsTail(CacheAddr addr) { - for (int i = 0; i < LAST_ELEMENT; i++) - if (addr == tails_[i].value()) +bool Rankings::IsTail(CacheAddr addr, List* list) { + for (int i = 0; i < LAST_ELEMENT; i++) { + if (addr == tails_[i].value()) { + if (*list != i) + Trace("Changing list %d to %d", *list, i); + *list = static_cast(i); return true; + } + } return false; } diff --git a/net/disk_cache/rankings.h b/net/disk_cache/rankings.h index 1914cf6..6066fbf 100644 --- a/net/disk_cache/rankings.h +++ b/net/disk_cache/rankings.h @@ -159,9 +159,10 @@ class Rankings { // selfcheck). bool CheckEntry(CacheRankingsBlock* rankings); - // Returns false if node is not properly linked. + // Returns false if node is not properly linked. This method may change the + // provided |list| to reflect the list where this node is actually stored. bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, - CacheRankingsBlock* next, List list); + CacheRankingsBlock* next, List* list); // Checks the links between two consecutive nodes. bool CheckSingleLink(CacheRankingsBlock* prev, CacheRankingsBlock* next); @@ -170,9 +171,10 @@ class Rankings { // error code (negative value). int CheckList(List list); - // Returns true if addr is the head or tail of any list. - bool IsHead(CacheAddr addr); - bool IsTail(CacheAddr addr); + // Returns true if addr is the head or tail of any list. When there is a + // match |list| will contain the list number for |addr|. + bool IsHead(CacheAddr addr, List* list); + bool IsTail(CacheAddr addr, List* list); // Updates the iterators whenever node is being changed. void UpdateIterators(CacheRankingsBlock* node); -- cgit v1.1