rankings.cc revision 3345a6884c488ff3a535c2c9acdd33d74b37e311
1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Copyright (c) 2006-2008 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 7c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "base/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 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid TerminateSelf() { 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#if defined(OS_WIN) 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Windows does more work on _exit() than we would like, so we force exit. 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateProcess(GetCurrentProcess(), 0); 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#elif defined(OS_POSIX) 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // On POSIX, _exit() will terminate the process with minimal cleanup, 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // and it is cleaner than killing. 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott _exit(0); 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#endif 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Generates a crash on debug builds, acording to the value of g_rankings_crash. 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// This used by crash_cache.exe to generate unit-test files. 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid GenerateCrash(CrashLocation location) { 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#ifndef NDEBUG 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::NO_CRASH == g_rankings_crash) 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (location) { 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_1: 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_ONE_1: 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_LOAD_1: 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_2: 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::INSERT_EMPTY_1 == g_rankings_crash) 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_3: 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_EMPTY_2: 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_ONE_2: 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_LOAD_2: 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_INSERT_4: 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_EMPTY_3: 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::INSERT_ONE_3: 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_1: 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_ONE_1: 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_HEAD_1: 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_TAIL_1: 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_LOAD_1: 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_2: 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_ONE_2 == g_rankings_crash) 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_3: 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_ONE_3 == g_rankings_crash) 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_4: 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_HEAD_2 == g_rankings_crash) 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_5: 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_TAIL_2 == g_rankings_crash) 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_6: 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (disk_cache::REMOVE_TAIL_3 == g_rankings_crash) 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_7: 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_ONE_4: 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_LOAD_2: 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_HEAD_3: 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case ON_REMOVE_8: 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott switch (g_rankings_crash) { 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_HEAD_4: 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott case disk_cache::REMOVE_LOAD_3: 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TerminateSelf(); 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott break; 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott default: 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott NOTREACHED(); 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#endif // NDEBUG 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 177c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace disk_cache { 178c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 1793345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::Iterator::Iterator(Rankings* rankings) { 1803345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick memset(this, 0, sizeof(Iterator)); 1813345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick my_rankings = rankings; 1823345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick} 1833345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 1843345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::Iterator::~Iterator() { 1853345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick for (int i = 0; i < 3; i++) 1863345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick ScopedRankingsBlock(my_rankings, nodes[i]); 1873345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick} 1883345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 1893345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::Rankings() : init_(false) {} 1903345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 1913345a6884c488ff3a535c2c9acdd33d74b37e311Iain MerrickRankings::~Rankings() {} 1923345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 193c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::Init(BackendImpl* backend, bool count_lists) { 194c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(!init_); 195c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (init_) 196c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 197c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 198c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_ = backend; 199c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_ = backend_->GetLruData(); 200c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott count_lists_ = count_lists; 201c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 202c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ReadHeads(); 203c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ReadTails(); 204c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 205c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (control_data_->transaction) 206c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CompleteTransaction(); 207c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 208c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott init_ = true; 209c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 210c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 211c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 212c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::Reset() { 213c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott init_ = false; 214c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) { 215c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott heads_[i].set_value(0); 216c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott tails_[i].set_value(0); 217c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 218c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_ = NULL; 219c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 220c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 221c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::GetRanking(CacheRankingsBlock* rankings) { 222c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!rankings->address().is_initialized()) 223c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 224c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 225c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TimeTicks start = TimeTicks::Now(); 226c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!rankings->Load()) 227c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 228c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 229c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!SanityCheck(rankings, true)) { 230c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->CriticalError(ERR_INVALID_LINKS); 231c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 232c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 233c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 234c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->OnEvent(Stats::OPEN_RANKINGS); 235c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 236c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // "dummy" is the old "pointer" value, so it has to be 0. 237c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!rankings->Data()->dirty && !rankings->Data()->dummy) 238c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 239c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 240c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott EntryImpl* entry = backend_->GetOpenEntry(rankings); 241c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (backend_->GetCurrentEntryId() != rankings->Data()->dirty || !entry) { 242c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // We cannot trust this entry, but we cannot initiate a cleanup from this 243c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // point (we may be in the middle of a cleanup already). Just get rid of 244c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // the invalid pointer and continue; the entry will be deleted when detected 245c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // from a regular open/create path. 246c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings->Data()->dummy = 0; 247c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings->Data()->dirty = backend_->GetCurrentEntryId() - 1; 248c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!rankings->Data()->dirty) 249c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings->Data()->dirty--; 250c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 251c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 252c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 253c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Note that we should not leave this module without deleting rankings first. 254c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings->SetData(entry->rankings()->Data()); 255c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 256c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE_MS, "GetRankings", 0, start); 257c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 258c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 259c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 260c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::ConvertToLongLived(CacheRankingsBlock* rankings) { 261c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (rankings->own_data()) 262c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 263c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 264c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // We cannot return a shared node because we are not keeping a reference 265c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // to the entry that owns the buffer. Make this node a copy of the one that 266c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // we have, and let the iterator logic update it when the entry changes. 267c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock temp(NULL, Addr(0)); 268c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *temp.Data() = *rankings->Data(); 269c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rankings->StopSharingData(); 270c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *rankings->Data() = *temp.Data(); 271c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 272c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 273c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { 274c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("Insert 0x%x", node->address().value()); 275c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(node->HasData()); 276c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 277c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 278c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Transaction lock(control_data_, node->address(), INSERT, list); 279c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock head(backend_->File(my_head), my_head); 280c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.is_initialized()) { 281c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(&head)) 282c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 283c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 284c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (head.Data()->prev != my_head.value() && // Normal path. 285c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott head.Data()->prev != node->address().value()) { // FinishInsert(). 286c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->CriticalError(ERR_INVALID_LINKS); 287c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 288c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 289c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 290c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott head.Data()->prev = node->address().value(); 291c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott head.Store(); 292c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_1); 293c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott UpdateIterators(&head); 294c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 295c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 296c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = my_head.value(); 297c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->prev = node->address().value(); 298c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(node->address().value()); 299c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 300c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized() || my_tail.value() == node->address().value()) { 301c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(node->address().value()); 302c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = my_tail.value(); 303c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(list); 304c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_2); 305c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 306c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 307c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Time now = Time::Now(); 308c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->last_used = now.ToInternalValue(); 309c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (modified) 310c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->last_modified = now.ToInternalValue(); 311c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Store(); 312c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_3); 313c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 314c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The last thing to do is move our head to point to a node already stored. 315c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(list); 316c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott IncrementCounter(list); 317c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_INSERT_4); 318c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 319c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 320c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// If a, b and r are elements on the list, and we want to remove r, the possible 321c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// states for the objects if a crash happens are (where y(x, z) means for object 322c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// y, prev is x and next is z): 323c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// A. One element: 324c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. r(r, r), head(r), tail(r) initial state 325c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. r(r, r), head(0), tail(r) WriteHead() 326c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. r(r, r), head(0), tail(0) WriteTail() 327c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. r(0, 0), head(0), tail(0) next.Store() 328c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 329c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// B. Remove a random element: 330c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. a(x, r), r(a, b), b(r, y), head(x), tail(y) initial state 331c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. a(x, r), r(a, b), b(a, y), head(x), tail(y) next.Store() 332c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. a(x, b), r(a, b), b(a, y), head(x), tail(y) prev.Store() 333c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. a(x, b), r(0, 0), b(a, y), head(x), tail(y) node.Store() 334c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 335c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// C. Remove head: 336c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. r(r, b), b(r, y), head(r), tail(y) initial state 337c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. r(r, b), b(r, y), head(b), tail(y) WriteHead() 338c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. r(r, b), b(b, y), head(b), tail(y) next.Store() 339c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. r(0, 0), b(b, y), head(b), tail(y) prev.Store() 340c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 341c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// D. Remove tail: 342c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 1. a(x, r), r(a, r), head(x), tail(r) initial state 343c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 2. a(x, r), r(a, r), head(x), tail(a) WriteTail() 344c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 3. a(x, a), r(a, r), head(x), tail(a) prev.Store() 345c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4. a(x, a), r(0, 0), head(x), tail(a) next.Store() 346c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::Remove(CacheRankingsBlock* node, List list) { 347c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("Remove 0x%x (0x%x 0x%x)", node->address().value(), node->Data()->next, 348c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->prev); 349c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(node->HasData()); 350c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott InvalidateIterators(node); 351c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr next_addr(node->Data()->next); 352c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr prev_addr(node->Data()->prev); 353c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!next_addr.is_initialized() || next_addr.is_separate_file() || 354c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott !prev_addr.is_initialized() || prev_addr.is_separate_file()) { 355c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(WARNING) << "Invalid rankings info."; 356c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 357c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 358c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 359c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock next(backend_->File(next_addr), next_addr); 360c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr); 361c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(&next) || !GetRanking(&prev)) 362c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 363c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 364c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!CheckLinks(node, &prev, &next, list)) 365c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 366c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 367c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Transaction lock(control_data_, node->address(), REMOVE, list); 368c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next = next.address().value(); 369c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev = prev.address().value(); 370c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_1); 371c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 372c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr node_value = node->address().value(); 373c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 374c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 375c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node_value == my_head.value() || node_value == my_tail.value()) { 376c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.value() == my_tail.value()) { 377c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(0); 378c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(0); 379c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 380c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(list); 381c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_2); 382c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(list); 383c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_3); 384c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (node_value == my_head.value()) { 385c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(next.address().value()); 386c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev = next.address().value(); 387c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 388c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(list); 389c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_4); 390c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (node_value == my_tail.value()) { 391c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(prev.address().value()); 392c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next = prev.address().value(); 393c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 394c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(list); 395c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_5); 396c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 397c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Store the new tail to make sure we can undo the operation if we crash. 398c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Store(); 399c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_6); 400c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 401c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 402c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 403c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Nodes out of the list can be identified by invalid pointers. 404c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = 0; 405c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->prev = 0; 406c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 407c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The last thing to get to disk is the node itself, so before that there is 408c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // enough info to recover. 409c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Store(); 410c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_7); 411c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Store(); 412c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott GenerateCrash(ON_REMOVE_8); 413c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Store(); 414c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DecrementCounter(list); 415c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott UpdateIterators(&next); 416c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott UpdateIterators(&prev); 417c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 418c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 419c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// A crash in between Remove and Insert will lead to a dirty entry not on the 420c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// list. We want to avoid that case as much as we can (as while waiting for IO), 421c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// but the net effect is just an assert on debug when attempting to remove the 422c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// entry. Otherwise we'll need reentrant transactions, which is an overkill. 423c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) { 424c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch TimeTicks start = TimeTicks::Now(); 425c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Remove(node, list); 426c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Insert(node, modified, list); 427c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CACHE_UMA(AGE_MS, "UpdateRank", 0, start); 428c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 429c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 430c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::CompleteTransaction() { 431c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr node_addr(static_cast<CacheAddr>(control_data_->transaction)); 432c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node_addr.is_initialized() || node_addr.is_separate_file()) { 433c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott NOTREACHED(); 434c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(ERROR) << "Invalid rankings info."; 435c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 436c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 437c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 438c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("CompleteTransaction 0x%x", node_addr.value()); 439c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 440c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock node(backend_->File(node_addr), node_addr); 441c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node.Load()) 442c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 443c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 444c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node.Data()->dummy = 0; 445c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node.Store(); 446c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 447c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[control_data_->operation_list]; 448c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[control_data_->operation_list]; 449c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 450c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // We want to leave the node inside the list. The entry must me marked as 451c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // dirty, and will be removed later. Otherwise, we'll get assertions when 452c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // attempting to remove the dirty entry. 453c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (INSERT == control_data_->operation) { 454c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("FinishInsert h:0x%x t:0x%x", my_head.value(), my_tail.value()); 455c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott FinishInsert(&node); 456c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (REMOVE == control_data_->operation) { 457c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Trace("RevertRemove h:0x%x t:0x%x", my_head.value(), my_tail.value()); 458c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott RevertRemove(&node); 459c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 460c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott NOTREACHED(); 461c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(ERROR) << "Invalid operation to recover."; 462c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 463c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 464c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 465c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::FinishInsert(CacheRankingsBlock* node) { 466c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->transaction = 0; 467c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->operation = 0; 468c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[control_data_->operation_list]; 469c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[control_data_->operation_list]; 470c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.value() != node->address().value()) { 471c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_tail.value() == node->address().value()) { 472c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This part will be skipped by the logic of Insert. 473c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = my_tail.value(); 474c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 475c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 476c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Insert(node, true, static_cast<List>(control_data_->operation_list)); 477c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 478c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 479c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Tell the backend about this entry. 480c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->RecoveredEntry(node); 481c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 482c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 483c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::RevertRemove(CacheRankingsBlock* node) { 484c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr next_addr(node->Data()->next); 485c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr prev_addr(node->Data()->prev); 486c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!next_addr.is_initialized() || !prev_addr.is_initialized()) { 487c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The operation actually finished. Nothing to do. 488c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->transaction = 0; 489c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 490c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 491c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (next_addr.is_separate_file() || prev_addr.is_separate_file()) { 492c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott NOTREACHED(); 493c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(WARNING) << "Invalid rankings info."; 494c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->transaction = 0; 495c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 496c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 497c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 498c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock next(backend_->File(next_addr), next_addr); 499c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock prev(backend_->File(prev_addr), prev_addr); 500c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!next.Load() || !prev.Load()) 501c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 502c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 503c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr node_value = node->address().value(); 504c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(prev.Data()->next == node_value || 505c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next == prev_addr.value() || 506c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next == next.address().value()); 507c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(next.Data()->prev == node_value || 508c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev == next_addr.value() || 509c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev == prev.address().value()); 510c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 511c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node_value != prev_addr.value()) 512c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next = node_value; 513c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node_value != next_addr.value()) 514c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev = node_value; 515c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 516c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott List my_list = static_cast<List>(control_data_->operation_list); 517c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[my_list]; 518c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[my_list]; 519c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_head.is_initialized() || !my_tail.is_initialized()) { 520c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(node_value); 521c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(node_value); 522c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(my_list); 523c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(my_list); 524c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (my_head.value() == next.address().value()) { 525c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_head.set_value(node_value); 526c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Data()->next = next.address().value(); 527c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteHead(my_list); 528c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else if (my_tail.value() == prev.address().value()) { 529c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott my_tail.set_value(node_value); 530c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Data()->prev = prev.address().value(); 531c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott WriteTail(my_list); 532c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 533c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 534c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.Store(); 535c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.Store(); 536c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->transaction = 0; 537c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->operation = 0; 538c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 539c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 540c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) { 541c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ScopedRankingsBlock next(this); 542c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node) { 543c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 544c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_head.is_initialized()) 545c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 546c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.reset(new CacheRankingsBlock(backend_->File(my_head), my_head)); 547c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 548c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node->HasData()) 549c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Load(); 550c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 551c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 552c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 553c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_tail.value() == node->address().value()) 554c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 555c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr address(node->Data()->next); 556c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (address.value() == node->address().value()) 557c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; // Another tail? fail it. 558c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next.reset(new CacheRankingsBlock(backend_->File(address), address)); 559c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 560c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 561c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrackRankingsBlock(next.get(), true); 562c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 563c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(next.get())) 564c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 565c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 566c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ConvertToLongLived(next.get()); 567c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node && !CheckSingleLink(node, next.get())) 568c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 569c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 570c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return next.release(); 571c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 572c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 573c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottCacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) { 574c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ScopedRankingsBlock prev(this); 575c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node) { 576c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 577c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 578c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 579c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.reset(new CacheRankingsBlock(backend_->File(my_tail), my_tail)); 580c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } else { 581c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node->HasData()) 582c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Load(); 583c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 584c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_head.is_initialized()) 585c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 586c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.value() == node->address().value()) 587c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 588c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr address(node->Data()->prev); 589c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (address.value() == node->address().value()) 590c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; // Another head? fail it. 591c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.reset(new CacheRankingsBlock(backend_->File(address), address)); 592c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 593c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 594c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrackRankingsBlock(prev.get(), true); 595c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 596c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!GetRanking(prev.get())) 597c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 598c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 599c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ConvertToLongLived(prev.get()); 600c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node && !CheckSingleLink(prev.get(), node)) 601c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return NULL; 602c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 603c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return prev.release(); 604c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 605c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 606c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::FreeRankingsBlock(CacheRankingsBlock* node) { 607c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott TrackRankingsBlock(node, false); 608c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 609c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 610c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::TrackRankingsBlock(CacheRankingsBlock* node, 611c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bool start_tracking) { 612c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!node) 613c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 614c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 615c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott IteratorPair current(node->address().value(), node); 616c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 617c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (start_tracking) 618c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott iterators_.push_back(current); 619c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott else 620c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott iterators_.remove(current); 621c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 622c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 623c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint Rankings::SelfCheck() { 624c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int total = 0; 625c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) { 626c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int partial = CheckList(static_cast<List>(i)); 627c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (partial < 0) 628c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return partial; 629c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott total += partial; 630c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 631c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return total; 632c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 633c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 634c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) { 635c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const RankingsNode* data = node->Data(); 636c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!data->contents) 637c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 638c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 639c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // It may have never been inserted. 640c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (from_list && (!data->last_used || !data->last_modified)) 641c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 642c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 643c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if ((!data->next && data->prev) || (data->next && !data->prev)) 644c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 645c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 646c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Both pointers on zero is a node out of the list. 647c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!data->next && !data->prev && from_list) 648c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 649c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 650c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if ((node->address().value() == data->prev) && !IsHead(data->prev)) 651c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 652c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 653c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if ((node->address().value() == data->next) && !IsTail(data->next)) 654c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 655c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 656c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 657c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 658c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 659c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::ReadHeads() { 660c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) 661c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott heads_[i] = Addr(control_data_->heads[i]); 662c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 663c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 664c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::ReadTails() { 665c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) 666c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott tails_[i] = Addr(control_data_->tails[i]); 667c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 668c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 669c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::WriteHead(List list) { 670c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->heads[list] = heads_[list].value(); 671c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 672c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 673c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::WriteTail(List list) { 674c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->tails[list] = tails_[list].value(); 675c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 676c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 677c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::CheckEntry(CacheRankingsBlock* rankings) { 678c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!rankings->Data()->dummy) 679c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 680c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 681c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If this entry is not dirty, it is a serious problem. 682c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return backend_->GetCurrentEntryId() != rankings->Data()->dirty; 683c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 684c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 685c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, 686c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock* next, List list) { 687c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if ((prev->Data()->next != node->address().value() && 688c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott heads_[list].value() != node->address().value()) || 689c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott (next->Data()->prev != node->address().value() && 690c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott tails_[list].value() != node->address().value())) { 691c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(ERROR) << "Inconsistent LRU."; 692c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 693c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (prev->Data()->next == next->address().value() && 694c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next->Data()->prev == prev->address().value()) { 695c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The list is actually ok, node is wrong. 696c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->next = 0; 697c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Data()->prev = 0; 698c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Store(); 699c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 700c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 701c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->CriticalError(ERR_INVALID_LINKS); 702c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 703c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 704c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 705c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 706c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 707c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 708c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::CheckSingleLink(CacheRankingsBlock* prev, 709c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock* next) { 710c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (prev->Data()->next != next->address().value() || 711c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott next->Data()->prev != prev->address().value()) { 712c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(ERROR) << "Inconsistent LRU."; 713c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 714c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott backend_->CriticalError(ERR_INVALID_LINKS); 715c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 716c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 717c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 718c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 719c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 720c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 721c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottint Rankings::CheckList(List list) { 722c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_head = heads_[list]; 723c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr& my_tail = tails_[list]; 724c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_head.is_initialized()) { 725c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 726c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return 0; 727c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If there is no head, having a tail is an error. 728c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_TAIL; 729c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 730c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // If there is no tail, having a head is an error. 731c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!my_tail.is_initialized()) 732c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_HEAD; 733c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 734c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_tail.is_separate_file()) 735c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_TAIL; 736c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 737c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (my_head.is_separate_file()) 738c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_HEAD; 739c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 740c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott int num_items = 0; 741c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr address(my_head.value()); 742c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Addr prev(my_head.value()); 743c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott scoped_ptr<CacheRankingsBlock> node; 744c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott do { 745c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node.reset(new CacheRankingsBlock(backend_->File(address), address)); 746c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott node->Load(); 747c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (node->Data()->prev != prev.value()) 748c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_PREV; 749c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!CheckEntry(node.get())) 750c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_ENTRY; 751c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 752c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott prev.set_value(address.value()); 753c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott address.set_value(node->Data()->next); 754c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!address.is_initialized() || address.is_separate_file()) 755c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return ERR_INVALID_NEXT; 756c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 757c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott num_items++; 758c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } while (node->address().value() != address.value()); 759c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return num_items; 760c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 761c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 762c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::IsHead(CacheAddr addr) { 763c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) 764c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (addr == heads_[i].value()) 765c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 766c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 767c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 768c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 769c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottbool Rankings::IsTail(CacheAddr addr) { 770c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (int i = 0; i < LAST_ELEMENT; i++) 771c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (addr == tails_[i].value()) 772c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return true; 773c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return false; 774c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 775c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 776c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// We expect to have just a few iterators at any given time, maybe two or three, 777c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// But we could have more than one pointing at the same mode. We walk the list 778c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// of cache iterators and update all that are pointing to the given node. 779c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::UpdateIterators(CacheRankingsBlock* node) { 780c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr address = node->address().value(); 781c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end(); 782c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ++it) { 783c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (it->first == address && it->second->HasData()) { 784c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheRankingsBlock* other = it->second; 785c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *other->Data() = *node->Data(); 786c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 787c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 788c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 789c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 790c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::InvalidateIterators(CacheRankingsBlock* node) { 791c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott CacheAddr address = node->address().value(); 792c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (IteratorList::iterator it = iterators_.begin(); it != iterators_.end(); 793c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ++it) { 794c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (it->first == address) { 795c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott LOG(WARNING) << "Invalidating iterator at 0x" << std::hex << address; 796c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott it->second->Discard(); 797c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 798c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 799c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 800c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 801c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::IncrementCounter(List list) { 802c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!count_lists_) 803c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 804c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 805c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(control_data_->sizes[list] < kint32max); 806c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (control_data_->sizes[list] < kint32max) 807c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->sizes[list]++; 808c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 809c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 810c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid Rankings::DecrementCounter(List list) { 811c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (!count_lists_) 812c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return; 813c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 814c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DCHECK(control_data_->sizes[list] > 0); 815c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (control_data_->sizes[list] > 0) 816c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott control_data_->sizes[list]--; 817c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 818c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 819c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace disk_cache 820