1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // See net/disk_cache/disk_cache.h for the public interface. 6 7 #ifndef NET_DISK_CACHE_RANKINGS_H_ 8 #define NET_DISK_CACHE_RANKINGS_H_ 9 10 #include <list> 11 12 #include "base/scoped_ptr.h" 13 #include "net/disk_cache/addr.h" 14 #include "net/disk_cache/mapped_file.h" 15 #include "net/disk_cache/storage_block.h" 16 17 namespace disk_cache { 18 19 class BackendImpl; 20 21 // Type of crashes generated for the unit tests. 22 enum RankCrashes { 23 NO_CRASH = 0, 24 INSERT_EMPTY_1, 25 INSERT_EMPTY_2, 26 INSERT_EMPTY_3, 27 INSERT_ONE_1, 28 INSERT_ONE_2, 29 INSERT_ONE_3, 30 INSERT_LOAD_1, 31 INSERT_LOAD_2, 32 REMOVE_ONE_1, 33 REMOVE_ONE_2, 34 REMOVE_ONE_3, 35 REMOVE_ONE_4, 36 REMOVE_HEAD_1, 37 REMOVE_HEAD_2, 38 REMOVE_HEAD_3, 39 REMOVE_HEAD_4, 40 REMOVE_TAIL_1, 41 REMOVE_TAIL_2, 42 REMOVE_TAIL_3, 43 REMOVE_LOAD_1, 44 REMOVE_LOAD_2, 45 REMOVE_LOAD_3, 46 MAX_CRASH 47 }; 48 49 // This class handles the ranking information for the cache. 50 class Rankings { 51 public: 52 // Possible lists of entries. 53 enum List { 54 NO_USE = 0, // List of entries that have not been reused. 55 LOW_USE, // List of entries with low reuse. 56 HIGH_USE, // List of entries with high reuse. 57 RESERVED, // Reserved for future use. 58 DELETED, // List of recently deleted or doomed entries. 59 LAST_ELEMENT 60 }; 61 62 // This class provides a specialized version of scoped_ptr, that calls 63 // Rankings whenever a CacheRankingsBlock is deleted, to keep track of cache 64 // iterators that may go stale. 65 class ScopedRankingsBlock : public scoped_ptr<CacheRankingsBlock> { 66 public: ScopedRankingsBlock()67 ScopedRankingsBlock() : rankings_(NULL) {} ScopedRankingsBlock(Rankings * rankings)68 explicit ScopedRankingsBlock(Rankings* rankings) : rankings_(rankings) {} ScopedRankingsBlock(Rankings * rankings,CacheRankingsBlock * node)69 ScopedRankingsBlock(Rankings* rankings, CacheRankingsBlock* node) 70 : scoped_ptr<CacheRankingsBlock>(node), rankings_(rankings) {} 71 ~ScopedRankingsBlock()72 ~ScopedRankingsBlock() { 73 rankings_->FreeRankingsBlock(get()); 74 } 75 set_rankings(Rankings * rankings)76 void set_rankings(Rankings* rankings) { 77 rankings_ = rankings; 78 } 79 80 // scoped_ptr::reset will delete the object. 81 void reset(CacheRankingsBlock* p = NULL) { 82 if (p != get()) 83 rankings_->FreeRankingsBlock(get()); 84 scoped_ptr<CacheRankingsBlock>::reset(p); 85 } 86 87 private: 88 Rankings* rankings_; 89 DISALLOW_EVIL_CONSTRUCTORS(ScopedRankingsBlock); 90 }; 91 92 // If we have multiple lists, we have to iterate through all at the same time. 93 // This structure keeps track of where we are on the iteration. 94 struct Iterator { 95 List list; // Which entry was returned to the user. 96 CacheRankingsBlock* nodes[3]; // Nodes on the first three lists. 97 Rankings* my_rankings; IteratorIterator98 explicit Iterator(Rankings* rankings) { 99 memset(this, 0, sizeof(Iterator)); 100 my_rankings = rankings; 101 } ~IteratorIterator102 ~Iterator() { 103 for (int i = 0; i < 3; i++) 104 ScopedRankingsBlock(my_rankings, nodes[i]); 105 } 106 }; 107 Rankings()108 Rankings() : init_(false) {} ~Rankings()109 ~Rankings() {} 110 111 bool Init(BackendImpl* backend, bool count_lists); 112 113 // Restores original state, leaving the object ready for initialization. 114 void Reset(); 115 116 // Inserts a given entry at the head of the queue. 117 void Insert(CacheRankingsBlock* node, bool modified, List list); 118 119 // Removes a given entry from the LRU list. 120 void Remove(CacheRankingsBlock* node, List list); 121 122 // Moves a given entry to the head. 123 void UpdateRank(CacheRankingsBlock* node, bool modified, List list); 124 125 // Iterates through the list. 126 CacheRankingsBlock* GetNext(CacheRankingsBlock* node, List list); 127 CacheRankingsBlock* GetPrev(CacheRankingsBlock* node, List list); 128 void FreeRankingsBlock(CacheRankingsBlock* node); 129 130 // Controls tracking of nodes used for enumerations. 131 void TrackRankingsBlock(CacheRankingsBlock* node, bool start_tracking); 132 133 // Peforms a simple self-check of the lists, and returns the number of items 134 // or an error code (negative value). 135 int SelfCheck(); 136 137 // Returns false if the entry is clearly invalid. from_list is true if the 138 // node comes from the LRU list. 139 bool SanityCheck(CacheRankingsBlock* node, bool from_list); 140 141 private: 142 typedef std::pair<CacheAddr, CacheRankingsBlock*> IteratorPair; 143 typedef std::list<IteratorPair> IteratorList; 144 145 void ReadHeads(); 146 void ReadTails(); 147 void WriteHead(List list); 148 void WriteTail(List list); 149 150 // Gets the rankings information for a given rankings node. We may end up 151 // sharing the actual memory with a loaded entry, but we are not taking a 152 // reference to that entry, so |rankings| must be short lived. 153 bool GetRanking(CacheRankingsBlock* rankings); 154 155 // Makes |rankings| suitable to live a long life. 156 void ConvertToLongLived(CacheRankingsBlock* rankings); 157 158 // Finishes a list modification after a crash. 159 void CompleteTransaction(); 160 void FinishInsert(CacheRankingsBlock* rankings); 161 void RevertRemove(CacheRankingsBlock* rankings); 162 163 // Returns false if this entry will not be recognized as dirty (called during 164 // selfcheck). 165 bool CheckEntry(CacheRankingsBlock* rankings); 166 167 // Returns false if node is not properly linked. 168 bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, 169 CacheRankingsBlock* next, List list); 170 171 // Checks the links between two consecutive nodes. 172 bool CheckSingleLink(CacheRankingsBlock* prev, CacheRankingsBlock* next); 173 174 // Peforms a simple check of the list, and returns the number of items or an 175 // error code (negative value). 176 int CheckList(List list); 177 178 // Returns true if addr is the head or tail of any list. 179 bool IsHead(CacheAddr addr); 180 bool IsTail(CacheAddr addr); 181 182 // Updates the iterators whenever node is being changed. 183 void UpdateIterators(CacheRankingsBlock* node); 184 185 // Invalidates the iterators pointing to this node. 186 void InvalidateIterators(CacheRankingsBlock* node); 187 188 // Keeps track of the number of entries on a list. 189 void IncrementCounter(List list); 190 void DecrementCounter(List list); 191 192 bool init_; 193 bool count_lists_; 194 Addr heads_[LAST_ELEMENT]; 195 Addr tails_[LAST_ELEMENT]; 196 BackendImpl* backend_; 197 LruData* control_data_; // Data related to the LRU lists. 198 IteratorList iterators_; 199 200 DISALLOW_COPY_AND_ASSIGN(Rankings); 201 }; 202 203 } // namespace disk_cache 204 205 #endif // NET_DISK_CACHE_RANKINGS_H_ 206