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