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