1ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen// Copyright (c) 2011 The Chromium Authors. All rights reserved. 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Use of this source code is governed by a BSD-style license that can be 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// found in the LICENSE file. 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/rankings.h" 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 7731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick#include "base/metrics/histogram.h" 8c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/backend_impl.h" 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/entry_impl.h" 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/errors.h" 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "net/disk_cache/histogram_macros.h" 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottusing base::Time; 14c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochusing base::TimeTicks; 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This is used by crash_cache.exe to generate unit test files. 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottdisk_cache::RankCrashes g_rankings_crash = disk_cache::NO_CRASH; 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace { 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottenum Operation { 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott INSERT = 1, 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott REMOVE 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This class provides a simple lock for the LRU list of rankings. Whenever an 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// entry is to be inserted or removed from the list, a transaction object should 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// be created to keep track of the operation. If the process crashes before 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// finishing the operation, the transaction record (stored as part of the user 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// data on the file header) can be used to finish the operation. 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottclass Transaction { 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott public: 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // addr is the cache addres of the node being inserted or removed. We want to 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // avoid having the compiler doing optimizations on when to read or write 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // from user_data because it is the basis of the crash detection. Maybe 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // volatile is not enough for that, but it should be a good hint. 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Transaction(volatile disk_cache::LruData* data, disk_cache::Addr addr, 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Operation op, int list); 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ~Transaction(); 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott private: 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott volatile disk_cache::LruData* data_; 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DISALLOW_COPY_AND_ASSIGN(Transaction); 43c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTransaction::Transaction(volatile disk_cache::LruData* data, 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott disk_cache::Addr addr, Operation op, int list) 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott : data_(data) { 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(!data_->transaction); 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(addr.is_initialized()); 50c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott data_->operation = op; 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott data_->operation_list = list; 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott data_->transaction = addr.value(); 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottTransaction::~Transaction() { 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(data_->transaction); 57c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott data_->transaction = 0; 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott data_->operation = 0; 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott data_->operation_list = 0; 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Code locations that can generate crashes. 63c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottenum CrashLocation { 64c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ON_INSERT_1, ON_INSERT_2, ON_INSERT_3, ON_INSERT_4, ON_REMOVE_1, ON_REMOVE_2, 65c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ON_REMOVE_3, ON_REMOVE_4, ON_REMOVE_5, ON_REMOVE_6, ON_REMOVE_7, ON_REMOVE_8 66c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 67c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 68731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick#ifndef NDEBUG 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid TerminateSelf() { 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#if defined(OS_WIN) 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Windows does more work on _exit() than we would like, so we force exit. 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateProcess(GetCurrentProcess(), 0); 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#elif defined(OS_POSIX) 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // On POSIX, _exit() will terminate the process with minimal cleanup, 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // and it is cleaner than killing. 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott _exit(0); 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#endif 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 79731df977c0511bca2206b5f333555b1205ff1f43Iain Merrick#endif // NDEBUG 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Generates a crash on debug builds, acording to the value of g_rankings_crash. 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This used by crash_cache.exe to generate unit-test files. 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid GenerateCrash(CrashLocation location) { 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#ifndef NDEBUG 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::NO_CRASH == g_rankings_crash) 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (location) { 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_1: 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_ONE_1: 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_LOAD_1: 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_2: 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::INSERT_EMPTY_1 == g_rankings_crash) 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_3: 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_EMPTY_2: 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_ONE_2: 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_LOAD_2: 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_4: 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_EMPTY_3: 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_ONE_3: 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_1: 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_ONE_1: 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_HEAD_1: 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_TAIL_1: 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_LOAD_1: 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_2: 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_ONE_2 == g_rankings_crash) 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_3: 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_ONE_3 == g_rankings_crash) 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_4: 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_HEAD_2 == g_rankings_crash) 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_5: 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_TAIL_2 == g_rankings_crash) 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_6: 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_TAIL_3 == g_rankings_crash) 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_7: 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_ONE_4: 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_LOAD_2: 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_HEAD_3: 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_8: 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_HEAD_4: 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_LOAD_3: 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott NOTREACHED(); 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#endif // NDEBUG 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 1774a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch// Update the timestamp fields of |node|. 1784a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdochvoid UpdateTimes(disk_cache::CacheRankingsBlock* node, bool modified) { 1794a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch base::Time now = base::Time::Now(); 1804a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node->Data()->last_used = now.ToInternalValue(); 1814a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (modified) 1824a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node->Data()->last_modified = now.ToInternalValue(); 1834a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch} 1844a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace disk_cache { 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 1893345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::Iterator::Iterator(Rankings* rankings) { 1903345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick memset(this, 0, sizeof(Iterator)); 1913345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick my_rankings = rankings; 1923345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick} 1933345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 1943345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::Iterator::~Iterator() { 1953345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick for (int i = 0; i < 3; i++) 1963345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick ScopedRankingsBlock(my_rankings, nodes[i]); 1973345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick} 1983345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 1993345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::Rankings() : init_(false) {} 2003345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 2013345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::~Rankings() {} 2023345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 203c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::Init(BackendImpl* backend, bool count_lists) { 204c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(!init_); 205c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (init_) 206c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 207c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 208c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_ = backend; 209c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_ = backend_->GetLruData(); 210c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott count_lists_ = count_lists; 211c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 212c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ReadHeads(); 213c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ReadTails(); 214c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 215c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (control_data_->transaction) 216c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CompleteTransaction(); 217c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 218c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott init_ = true; 219c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 220c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 221c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 222c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::Reset() { 223c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott init_ = false; 224c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) { 225c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott heads_[i].set_value(0); 226c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott tails_[i].set_value(0); 227c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 228c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_ = NULL; 229c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 230c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 231c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { 2324a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch Trace("Insert 0x%x l %d", node->address().value(), list); 233c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(node->HasData()); 234c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 235c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 236c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Transaction lock(control_data_, node->address(), INSERT, list); 237c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock head(backend_->File(my_head), my_head); 238c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.is_initialized()) { 239c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(&head)) 240c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 241c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 242c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (head.Data()->prev != my_head.value() && // Normal path. 243c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott head.Data()->prev != node->address().value()) { // FinishInsert(). 244c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->CriticalError(ERR_INVALID_LINKS); 245c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 246c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 247c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 248c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott head.Data()->prev = node->address().value(); 249c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott head.Store(); 250c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_1); 251c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott UpdateIterators(&head); 252c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 253c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 254c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = my_head.value(); 255c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->prev = node->address().value(); 256c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(node->address().value()); 257c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 258c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized() || my_tail.value() == node->address().value()) { 259c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(node->address().value()); 260c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = my_tail.value(); 261c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(list); 262c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_2); 263c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 264c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 2654a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch UpdateTimes(node, modified); 266c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Store(); 267c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_3); 268c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 269c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The last thing to do is move our head to point to a node already stored. 270c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(list); 271c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott IncrementCounter(list); 272c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_4); 273c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 274c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 275c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// If a, b and r are elements on the list, and we want to remove r, the possible 276c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// states for the objects if a crash happens are (where y(x, z) means for object 277c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// y, prev is x and next is z): 278c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// A. One element: 279c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. r(r, r), head(r), tail(r) initial state 280c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. r(r, r), head(0), tail(r) WriteHead() 281c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. r(r, r), head(0), tail(0) WriteTail() 282c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. r(0, 0), head(0), tail(0) next.Store() 283c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 284c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// B. Remove a random element: 285c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. a(x, r), r(a, b), b(r, y), head(x), tail(y) initial state 286c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. a(x, r), r(a, b), b(a, y), head(x), tail(y) next.Store() 287c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. a(x, b), r(a, b), b(a, y), head(x), tail(y) prev.Store() 288c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. a(x, b), r(0, 0), b(a, y), head(x), tail(y) node.Store() 289c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 290c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// C. Remove head: 291c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. r(r, b), b(r, y), head(r), tail(y) initial state 292c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. r(r, b), b(r, y), head(b), tail(y) WriteHead() 293c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. r(r, b), b(b, y), head(b), tail(y) next.Store() 294c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. r(0, 0), b(b, y), head(b), tail(y) prev.Store() 295c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 296c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// D. Remove tail: 297c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. a(x, r), r(a, r), head(x), tail(r) initial state 298c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. a(x, r), r(a, r), head(x), tail(a) WriteTail() 299c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. a(x, a), r(a, r), head(x), tail(a) prev.Store() 300c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. a(x, a), r(0, 0), head(x), tail(a) next.Store() 301efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsenvoid Rankings::Remove(CacheRankingsBlock* node, List list, bool strict) { 3024a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch Trace("Remove 0x%x (0x%x 0x%x) l %d", node->address().value(), 3034a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node->Data()->next, node->Data()->prev, list); 304c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(node->HasData()); 305efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen if (strict) 306c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott InvalidateIterators(node); 307efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen 308c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr next_addr(node->Data()->next); 309c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr prev_addr(node->Data()->prev); 310c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!next_addr.is_initialized() || next_addr.is_separate_file() || 311c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott !prev_addr.is_initialized() || prev_addr.is_separate_file()) { 3124a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (next_addr.is_initialized() || prev_addr.is_initialized()) { 3134a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch LOG(ERROR) << "Invalid rankings info."; 3144a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 315c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 316c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 317c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 318c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock next(backend_->File(next_addr), next_addr); 319c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr); 320c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(&next) || !GetRanking(&prev)) 321c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 322c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 3234a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (!CheckLinks(node, &prev, &next, &list)) 324c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 325c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 326c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Transaction lock(control_data_, node->address(), REMOVE, list); 327c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next = next.address().value(); 328c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev = prev.address().value(); 329c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_1); 330c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 331c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr node_value = node->address().value(); 332c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 333c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 334c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node_value == my_head.value() || node_value == my_tail.value()) { 335c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.value() == my_tail.value()) { 336c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(0); 337c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(0); 338c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 339c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(list); 340c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_2); 341c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(list); 342c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_3); 343c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (node_value == my_head.value()) { 344c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(next.address().value()); 345c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev = next.address().value(); 346c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 347c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(list); 348c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_4); 349c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (node_value == my_tail.value()) { 350c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(prev.address().value()); 351c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next = prev.address().value(); 352c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 353c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(list); 354c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_5); 355c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 356c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Store the new tail to make sure we can undo the operation if we crash. 357c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Store(); 358c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_6); 359c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 360c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 361c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 362c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Nodes out of the list can be identified by invalid pointers. 363c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = 0; 364c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->prev = 0; 365c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 366c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The last thing to get to disk is the node itself, so before that there is 367c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // enough info to recover. 368c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Store(); 369c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_7); 370c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Store(); 371c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_8); 372c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Store(); 373c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DecrementCounter(list); 374c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott UpdateIterators(&next); 375c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott UpdateIterators(&prev); 376c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 377c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 378c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// A crash in between Remove and Insert will lead to a dirty entry not on the 379c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// list. We want to avoid that case as much as we can (as while waiting for IO), 380c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// but the net effect is just an assert on debug when attempting to remove the 381c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// entry. Otherwise we'll need reentrant transactions, which is an overkill. 382c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) { 3834a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch Addr& my_head = heads_[list]; 3844a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (my_head.value() == node->address().value()) { 3854a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch UpdateTimes(node, modified); 3864a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node->set_modified(); 3874a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch return; 3884a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 3894a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch 390c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TimeTicks start = TimeTicks::Now(); 391efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen Remove(node, list, true); 392c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Insert(node, modified, list); 393c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE_MS, "UpdateRank", 0, start); 394c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 395c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 396c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) { 397c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ScopedRankingsBlock next(this); 398c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node) { 399c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 400c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_head.is_initialized()) 401c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 402c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.reset(new CacheRankingsBlock(backend_->File(my_head), my_head)); 403c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 404c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node->HasData()) 405c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Load(); 406c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 407c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 408c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 409c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_tail.value() == node->address().value()) 410c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 411c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr address(node->Data()->next); 412c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (address.value() == node->address().value()) 413c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; // Another tail? fail it. 414c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.reset(new CacheRankingsBlock(backend_->File(address), address)); 415c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 416c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 417c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrackRankingsBlock(next.get(), true); 418c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 419c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(next.get())) 420c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 421c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 422c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ConvertToLongLived(next.get()); 423c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node && !CheckSingleLink(node, next.get())) 424c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 425c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 426c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return next.release(); 427c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 428c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 429c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) { 430c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ScopedRankingsBlock prev(this); 431c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node) { 432c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 433c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 434c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 435c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.reset(new CacheRankingsBlock(backend_->File(my_tail), my_tail)); 436c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 437c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node->HasData()) 438c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Load(); 439c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 440c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_head.is_initialized()) 441c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 442c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.value() == node->address().value()) 443c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 444c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr address(node->Data()->prev); 445c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (address.value() == node->address().value()) 446c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; // Another head? fail it. 447c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.reset(new CacheRankingsBlock(backend_->File(address), address)); 448c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 449c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 450c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrackRankingsBlock(prev.get(), true); 451c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 452c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(prev.get())) 453c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 454c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 455c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ConvertToLongLived(prev.get()); 456c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node && !CheckSingleLink(prev.get(), node)) 457c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 458c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 459c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return prev.release(); 460c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 461c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 462c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::FreeRankingsBlock(CacheRankingsBlock* node) { 463c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrackRankingsBlock(node, false); 464c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 465c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 466c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::TrackRankingsBlock(CacheRankingsBlock* node, 467c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bool start_tracking) { 468c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node) 469c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 470c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 471c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott IteratorPair current(node->address().value(), node); 472c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 473c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (start_tracking) 474c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott iterators_.push_back(current); 475c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott else 476c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott iterators_.remove(current); 477c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 478c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 479c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint Rankings::SelfCheck() { 480c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int total = 0; 481c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) { 482c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int partial = CheckList(static_cast<List>(i)); 483c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (partial < 0) 484c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return partial; 485c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott total += partial; 486c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 487c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return total; 488c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 489c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 490efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsenbool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) const { 491c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const RankingsNode* data = node->Data(); 492c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 493c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if ((!data->next && data->prev) || (data->next && !data->prev)) 494c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 495c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 496c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Both pointers on zero is a node out of the list. 497c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!data->next && !data->prev && from_list) 498c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 499c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 5004a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch List list = NO_USE; // Initialize it to something. 5014a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if ((node->address().value() == data->prev) && !IsHead(data->prev, &list)) 502c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 503c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 5044a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if ((node->address().value() == data->next) && !IsTail(data->next, &list)) 505c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 506c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 507ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen if (!data->next && !data->prev) 508ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen return true; 509ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen 510ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen Addr next_addr(data->next); 511ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen Addr prev_addr(data->prev); 512ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen if (!next_addr.SanityCheck() || next_addr.file_type() != RANKINGS || 513ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen !prev_addr.SanityCheck() || prev_addr.file_type() != RANKINGS) 514ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen return false; 515ddb351dbec246cf1fab5ec20d2d5520909041de1Kristian Monsen 516c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 517c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 518c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 519efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsenbool Rankings::DataSanityCheck(CacheRankingsBlock* node, bool from_list) const { 520efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen const RankingsNode* data = node->Data(); 521efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen if (!data->contents) 522efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen return false; 523efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen 524efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen // It may have never been inserted. 525efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen if (from_list && (!data->last_used || !data->last_modified)) 526efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen return false; 527efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen 528efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen return true; 529efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen} 530efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen 531efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsenvoid Rankings::SetContents(CacheRankingsBlock* node, CacheAddr address) { 532efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen node->Data()->contents = address; 533efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen node->Store(); 534efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen} 535efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsen 536c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::ReadHeads() { 537c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) 538c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott heads_[i] = Addr(control_data_->heads[i]); 539c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 540c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 541c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::ReadTails() { 542c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) 543c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott tails_[i] = Addr(control_data_->tails[i]); 544c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 545c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 546c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::WriteHead(List list) { 547c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->heads[list] = heads_[list].value(); 548c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 549c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 550c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::WriteTail(List list) { 551c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->tails[list] = tails_[list].value(); 552c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 553c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 55472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenbool Rankings::GetRanking(CacheRankingsBlock* rankings) { 55572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!rankings->address().is_initialized()) 55672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return false; 55772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 55872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen TimeTicks start = TimeTicks::Now(); 55972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!rankings->Load()) 56072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return false; 56172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 56272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!SanityCheck(rankings, true)) { 56372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen backend_->CriticalError(ERR_INVALID_LINKS); 56472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return false; 56572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 56672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 56772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen backend_->OnEvent(Stats::OPEN_RANKINGS); 56872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 56972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // "dummy" is the old "pointer" value, so it has to be 0. 57072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!rankings->Data()->dirty && !rankings->Data()->dummy) 57172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return true; 57272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 57372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen EntryImpl* entry = backend_->GetOpenEntry(rankings); 574dc0f95d653279beabeb9817299e2902918ba123eKristian Monsen if (!entry) { 57572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // We cannot trust this entry, but we cannot initiate a cleanup from this 57672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // point (we may be in the middle of a cleanup already). Just get rid of 57772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // the invalid pointer and continue; the entry will be deleted when detected 57872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // from a regular open/create path. 57972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen rankings->Data()->dummy = 0; 58072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen rankings->Data()->dirty = backend_->GetCurrentEntryId() - 1; 58172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!rankings->Data()->dirty) 58272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen rankings->Data()->dirty--; 58372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return true; 58472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 58572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 58672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // Note that we should not leave this module without deleting rankings first. 58772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen rankings->SetData(entry->rankings()->Data()); 58872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 58972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen CACHE_UMA(AGE_MS, "GetRankings", 0, start); 59072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return true; 59172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 59272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 59372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenvoid Rankings::ConvertToLongLived(CacheRankingsBlock* rankings) { 59472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (rankings->own_data()) 59572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return; 59672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 59772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // We cannot return a shared node because we are not keeping a reference 59872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // to the entry that owns the buffer. Make this node a copy of the one that 59972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // we have, and let the iterator logic update it when the entry changes. 60072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen CacheRankingsBlock temp(NULL, Addr(0)); 60172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen *temp.Data() = *rankings->Data(); 60272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen rankings->StopSharingData(); 60372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen *rankings->Data() = *temp.Data(); 60472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 60572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 60672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenvoid Rankings::CompleteTransaction() { 60772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr node_addr(static_cast<CacheAddr>(control_data_->transaction)); 60872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!node_addr.is_initialized() || node_addr.is_separate_file()) { 60972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen NOTREACHED(); 61072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen LOG(ERROR) << "Invalid rankings info."; 61172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return; 61272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 61372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 61472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Trace("CompleteTransaction 0x%x", node_addr.value()); 61572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 61672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen CacheRankingsBlock node(backend_->File(node_addr), node_addr); 61772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!node.Load()) 61872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return; 61972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 62072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen node.Data()->dummy = 0; 62172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen node.Store(); 62272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 62372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr& my_head = heads_[control_data_->operation_list]; 62472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr& my_tail = tails_[control_data_->operation_list]; 62572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 62672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // We want to leave the node inside the list. The entry must me marked as 62772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // dirty, and will be removed later. Otherwise, we'll get assertions when 62872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // attempting to remove the dirty entry. 62972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (INSERT == control_data_->operation) { 63072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Trace("FinishInsert h:0x%x t:0x%x", my_head.value(), my_tail.value()); 63172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen FinishInsert(&node); 63272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } else if (REMOVE == control_data_->operation) { 63372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Trace("RevertRemove h:0x%x t:0x%x", my_head.value(), my_tail.value()); 63472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen RevertRemove(&node); 63572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } else { 63672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen NOTREACHED(); 63772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen LOG(ERROR) << "Invalid operation to recover."; 63872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 63972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 64072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 64172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenvoid Rankings::FinishInsert(CacheRankingsBlock* node) { 64272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen control_data_->transaction = 0; 64372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen control_data_->operation = 0; 64472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr& my_head = heads_[control_data_->operation_list]; 64572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr& my_tail = tails_[control_data_->operation_list]; 64672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (my_head.value() != node->address().value()) { 64772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (my_tail.value() == node->address().value()) { 64872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // This part will be skipped by the logic of Insert. 64972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen node->Data()->next = my_tail.value(); 65072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 65172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 65272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Insert(node, true, static_cast<List>(control_data_->operation_list)); 65372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 65472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 65572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // Tell the backend about this entry. 65672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen backend_->RecoveredEntry(node); 65772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 65872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 65972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsenvoid Rankings::RevertRemove(CacheRankingsBlock* node) { 66072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr next_addr(node->Data()->next); 66172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr prev_addr(node->Data()->prev); 66272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!next_addr.is_initialized() || !prev_addr.is_initialized()) { 66372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen // The operation actually finished. Nothing to do. 66472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen control_data_->transaction = 0; 66572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return; 66672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 66772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (next_addr.is_separate_file() || prev_addr.is_separate_file()) { 66872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen NOTREACHED(); 66972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen LOG(WARNING) << "Invalid rankings info."; 67072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen control_data_->transaction = 0; 67172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return; 67272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 67372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 67472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen CacheRankingsBlock next(backend_->File(next_addr), next_addr); 67572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr); 67672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!next.Load() || !prev.Load()) 67772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen return; 67872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 67972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen CacheAddr node_value = node->address().value(); 68072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen DCHECK(prev.Data()->next == node_value || 68172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen prev.Data()->next == prev_addr.value() || 68272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen prev.Data()->next == next.address().value()); 68372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen DCHECK(next.Data()->prev == node_value || 68472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen next.Data()->prev == next_addr.value() || 68572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen next.Data()->prev == prev.address().value()); 68672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 68772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (node_value != prev_addr.value()) 68872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen prev.Data()->next = node_value; 68972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (node_value != next_addr.value()) 69072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen next.Data()->prev = node_value; 69172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 69272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen List my_list = static_cast<List>(control_data_->operation_list); 69372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr& my_head = heads_[my_list]; 69472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen Addr& my_tail = tails_[my_list]; 69572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen if (!my_head.is_initialized() || !my_tail.is_initialized()) { 69672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen my_head.set_value(node_value); 69772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen my_tail.set_value(node_value); 69872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen WriteHead(my_list); 69972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen WriteTail(my_list); 70072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } else if (my_head.value() == next.address().value()) { 70172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen my_head.set_value(node_value); 70272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen prev.Data()->next = next.address().value(); 70372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen WriteHead(my_list); 70472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } else if (my_tail.value() == prev.address().value()) { 70572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen my_tail.set_value(node_value); 70672a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen next.Data()->prev = prev.address().value(); 70772a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen WriteTail(my_list); 70872a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen } 70972a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 71072a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen next.Store(); 71172a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen prev.Store(); 71272a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen control_data_->transaction = 0; 71372a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen control_data_->operation = 0; 71472a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen} 71572a454cd3513ac24fbdd0e0cb9ad70b86a99b801Kristian Monsen 716c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::CheckEntry(CacheRankingsBlock* rankings) { 717c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!rankings->Data()->dummy) 718c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 719c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 720c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If this entry is not dirty, it is a serious problem. 721c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return backend_->GetCurrentEntryId() != rankings->Data()->dirty; 722c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 723c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 724c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, 7254a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch CacheRankingsBlock* next, List* list) { 7264a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch CacheAddr node_addr = node->address().value(); 7274a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (prev->Data()->next == node_addr && 7284a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch next->Data()->prev == node_addr) { 7294a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch // A regular linked node. 7304a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch return true; 7314a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 732c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 7334a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch Trace("CheckLinks 0x%x (0x%x 0x%x)", node_addr, 7344a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch prev->Data()->next, next->Data()->prev); 7354a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch 7364a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (node_addr != prev->address().value() && 7374a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node_addr != next->address().value() && 7384a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch prev->Data()->next == next->address().value() && 7394a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch next->Data()->prev == prev->address().value()) { 7404a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch // The list is actually ok, node is wrong. 7414a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch Trace("node 0x%x out of list %d", node_addr, list); 7424a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node->Data()->next = 0; 7434a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node->Data()->prev = 0; 7444a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch node->Store(); 745c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 746c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 747c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 7484a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (prev->Data()->next == node_addr || 7494a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch next->Data()->prev == node_addr) { 7504a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch // Only one link is weird, lets double check. 7514a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (prev->Data()->next != node_addr && IsHead(node_addr, list)) 7524a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch return true; 7534a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch 7544a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (next->Data()->prev != node_addr && IsTail(node_addr, list)) 7554a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch return true; 7564a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 7574a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch 7584a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch LOG(ERROR) << "Inconsistent LRU."; 7594a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch backend_->CriticalError(ERR_INVALID_LINKS); 7604a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch return false; 761c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 762c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 763c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::CheckSingleLink(CacheRankingsBlock* prev, 764c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock* next) { 765c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (prev->Data()->next != next->address().value() || 766c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next->Data()->prev != prev->address().value()) { 767c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(ERROR) << "Inconsistent LRU."; 768c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 769c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->CriticalError(ERR_INVALID_LINKS); 770c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 771c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 772c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 773c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 774c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 775c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 776c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint Rankings::CheckList(List list) { 777c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 778c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 779c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_head.is_initialized()) { 780c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 781c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return 0; 782c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If there is no head, having a tail is an error. 783c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_TAIL; 784c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 785c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If there is no tail, having a head is an error. 786c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 787c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_HEAD; 788c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 789c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_tail.is_separate_file()) 790c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_TAIL; 791c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 792c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.is_separate_file()) 793c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_HEAD; 794c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 795c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int num_items = 0; 796c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr address(my_head.value()); 797c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr prev(my_head.value()); 798c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott scoped_ptr<CacheRankingsBlock> node; 799c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott do { 800c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node.reset(new CacheRankingsBlock(backend_->File(address), address)); 801c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Load(); 802c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node->Data()->prev != prev.value()) 803c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_PREV; 804c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!CheckEntry(node.get())) 805c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_ENTRY; 806c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 807c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.set_value(address.value()); 808c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott address.set_value(node->Data()->next); 809c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!address.is_initialized() || address.is_separate_file()) 810c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_NEXT; 811c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 812c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott num_items++; 813c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } while (node->address().value() != address.value()); 814c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return num_items; 815c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 816c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 817efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsenbool Rankings::IsHead(CacheAddr addr, List* list) const { 8184a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch for (int i = 0; i < LAST_ELEMENT; i++) { 8194a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (addr == heads_[i].value()) { 8204a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (*list != i) 8214a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch Trace("Changing list %d to %d", *list, i); 8224a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch *list = static_cast<List>(i); 823c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 8244a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 8254a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 826c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 827c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 828c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 829efe273f2861c2ea723aa1f9edd20a73356da2b6bKristian Monsenbool Rankings::IsTail(CacheAddr addr, List* list) const { 8304a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch for (int i = 0; i < LAST_ELEMENT; i++) { 8314a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (addr == tails_[i].value()) { 8324a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch if (*list != i) 8334a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch Trace("Changing list %d to %d", *list, i); 8344a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch *list = static_cast<List>(i); 835c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 8364a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 8374a5e2dc747d50c653511c68ccb2cfbfb740bd5a7Ben Murdoch } 838c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 839c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 840c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 841c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// We expect to have just a few iterators at any given time, maybe two or three, 842c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// But we could have more than one pointing at the same mode. We walk the list 843c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// of cache iterators and update all that are pointing to the given node. 844c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::UpdateIterators(CacheRankingsBlock* node) { 845c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr address = node->address().value(); 846c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end(); 847c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ++it) { 848c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (it->first == address && it->second->HasData()) { 849c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock* other = it->second; 850c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *other->Data() = *node->Data(); 851c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 852c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 853c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 854c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 855c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::InvalidateIterators(CacheRankingsBlock* node) { 856c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr address = node->address().value(); 857c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end(); 858c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ++it) { 859c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (it->first == address) { 860cdf68fe0ba6e68493ea8d3af28834041bbfd87e9Kristian Monsen#ifndef ANDROID 861cdf68fe0ba6e68493ea8d3af28834041bbfd87e9Kristian Monsen// Confirmed with chromium developers that this is normal, and removing from 862cdf68fe0ba6e68493ea8d3af28834041bbfd87e9Kristian Monsen// Android to close bug 3239659 863c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(WARNING) << "Invalidating iterator at 0x" << std::hex << address; 864cdf68fe0ba6e68493ea8d3af28834041bbfd87e9Kristian Monsen#endif 865c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott it->second->Discard(); 866c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 867c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 868c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 869c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 870c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::IncrementCounter(List list) { 871c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!count_lists_) 872c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 873c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 874c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(control_data_->sizes[list] < kint32max); 875c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (control_data_->sizes[list] < kint32max) 876c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->sizes[list]++; 877c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 878c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 879c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::DecrementCounter(List list) { 880c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!count_lists_) 881c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 882c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 883c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(control_data_->sizes[list] > 0); 884c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (control_data_->sizes[list] > 0) 885c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->sizes[list]--; 886c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 887c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 888c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace disk_cache 889