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. 116 void Remove(CacheRankingsBlock* node, List list); 117 118 // Moves a given entry to the head. 119 void UpdateRank(CacheRankingsBlock* node, bool modified, List list); 120 121 // Iterates through the list. 122 CacheRankingsBlock* GetNext(CacheRankingsBlock* node, List list); 123 CacheRankingsBlock* GetPrev(CacheRankingsBlock* node, List list); 124 void FreeRankingsBlock(CacheRankingsBlock* node); 125 126 // Controls tracking of nodes used for enumerations. 127 void TrackRankingsBlock(CacheRankingsBlock* node, bool start_tracking); 128 129 // Peforms a simple self-check of the lists, and returns the number of items 130 // or an error code (negative value). 131 int SelfCheck(); 132 133 // Returns false if the entry is clearly invalid. from_list is true if the 134 // node comes from the LRU list. 135 bool SanityCheck(CacheRankingsBlock* node, bool from_list); 136 137 private: 138 typedef std::pair<CacheAddr, CacheRankingsBlock*> IteratorPair; 139 typedef std::list<IteratorPair> IteratorList; 140 141 void ReadHeads(); 142 void ReadTails(); 143 void WriteHead(List list); 144 void WriteTail(List list); 145 146 // Gets the rankings information for a given rankings node. We may end up 147 // sharing the actual memory with a loaded entry, but we are not taking a 148 // reference to that entry, so |rankings| must be short lived. 149 bool GetRanking(CacheRankingsBlock* rankings); 150 151 // Makes |rankings| suitable to live a long life. 152 void ConvertToLongLived(CacheRankingsBlock* rankings); 153 154 // Finishes a list modification after a crash. 155 void CompleteTransaction(); 156 void FinishInsert(CacheRankingsBlock* rankings); 157 void RevertRemove(CacheRankingsBlock* rankings); 158 159 // Returns false if this entry will not be recognized as dirty (called during 160 // selfcheck). 161 bool CheckEntry(CacheRankingsBlock* rankings); 162 163 // Returns false if node is not properly linked. This method may change the 164 // provided |list| to reflect the list where this node is actually stored. 165 bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, 166 CacheRankingsBlock* next, List* list); 167 168 // Checks the links between two consecutive nodes. 169 bool CheckSingleLink(CacheRankingsBlock* prev, CacheRankingsBlock* next); 170 171 // Peforms a simple check of the list, and returns the number of items or an 172 // error code (negative value). 173 int CheckList(List list); 174 175 // Returns true if addr is the head or tail of any list. When there is a 176 // match |list| will contain the list number for |addr|. 177 bool IsHead(CacheAddr addr, List* list); 178 bool IsTail(CacheAddr addr, List* list); 179 180 // Updates the iterators whenever node is being changed. 181 void UpdateIterators(CacheRankingsBlock* node); 182 183 // Invalidates the iterators pointing to this node. 184 void InvalidateIterators(CacheRankingsBlock* node); 185 186 // Keeps track of the number of entries on a list. 187 void IncrementCounter(List list); 188 void DecrementCounter(List list); 189 190 bool init_; 191 bool count_lists_; 192 Addr heads_[LAST_ELEMENT]; 193 Addr tails_[LAST_ELEMENT]; 194 BackendImpl* backend_; 195 LruData* control_data_; // Data related to the LRU lists. 196 IteratorList iterators_; 197 198 DISALLOW_COPY_AND_ASSIGN(Rankings); 199 }; 200 201 } // namespace disk_cache 202 203 #endif // NET_DISK_CACHE_RANKINGS_H_ 204