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