diff options
Diffstat (limited to 'chromium/net/disk_cache/blockfile/rankings.h')
| -rw-r--r-- | chromium/net/disk_cache/blockfile/rankings.h | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/chromium/net/disk_cache/blockfile/rankings.h b/chromium/net/disk_cache/blockfile/rankings.h new file mode 100644 index 00000000000..4224d0058eb --- /dev/null +++ b/chromium/net/disk_cache/blockfile/rankings.h @@ -0,0 +1,214 @@ +// Copyright (c) 2012 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// See net/disk_cache/disk_cache.h for the public interface. + +#ifndef NET_DISK_CACHE_BLOCKFILE_RANKINGS_H_ +#define NET_DISK_CACHE_BLOCKFILE_RANKINGS_H_ + +#include <list> + +#include "base/memory/scoped_ptr.h" +#include "net/disk_cache/blockfile/addr.h" +#include "net/disk_cache/blockfile/mapped_file.h" +#include "net/disk_cache/blockfile/storage_block.h" + +namespace disk_cache { + +class BackendImpl; +struct LruData; +struct RankingsNode; +typedef StorageBlock<RankingsNode> CacheRankingsBlock; + +// Type of crashes generated for the unit tests. +enum RankCrashes { + NO_CRASH = 0, + INSERT_EMPTY_1, + INSERT_EMPTY_2, + INSERT_EMPTY_3, + INSERT_ONE_1, + INSERT_ONE_2, + INSERT_ONE_3, + INSERT_LOAD_1, + INSERT_LOAD_2, + REMOVE_ONE_1, + REMOVE_ONE_2, + REMOVE_ONE_3, + REMOVE_ONE_4, + REMOVE_HEAD_1, + REMOVE_HEAD_2, + REMOVE_HEAD_3, + REMOVE_HEAD_4, + REMOVE_TAIL_1, + REMOVE_TAIL_2, + REMOVE_TAIL_3, + REMOVE_LOAD_1, + REMOVE_LOAD_2, + REMOVE_LOAD_3, + MAX_CRASH +}; + +// This class handles the ranking information for the cache. +class Rankings { + public: + // Possible lists of entries. + enum List { + NO_USE = 0, // List of entries that have not been reused. + LOW_USE, // List of entries with low reuse. + HIGH_USE, // List of entries with high reuse. + RESERVED, // Reserved for future use. + DELETED, // List of recently deleted or doomed entries. + LAST_ELEMENT + }; + + // This class provides a specialized version of scoped_ptr, that calls + // Rankings whenever a CacheRankingsBlock is deleted, to keep track of cache + // iterators that may go stale. + class ScopedRankingsBlock : public scoped_ptr<CacheRankingsBlock> { + public: + ScopedRankingsBlock(); + explicit ScopedRankingsBlock(Rankings* rankings); + ScopedRankingsBlock(Rankings* rankings, CacheRankingsBlock* node); + + ~ScopedRankingsBlock() { + rankings_->FreeRankingsBlock(get()); + } + + void set_rankings(Rankings* rankings) { + rankings_ = rankings; + } + + // scoped_ptr::reset will delete the object. + void reset(CacheRankingsBlock* p = NULL) { + if (p != get()) + rankings_->FreeRankingsBlock(get()); + scoped_ptr<CacheRankingsBlock>::reset(p); + } + + private: + Rankings* rankings_; + DISALLOW_COPY_AND_ASSIGN(ScopedRankingsBlock); + }; + + // If we have multiple lists, we have to iterate through all at the same time. + // This structure keeps track of where we are on the iteration. + struct Iterator { + explicit Iterator(Rankings* rankings); + ~Iterator(); + + List list; // Which entry was returned to the user. + CacheRankingsBlock* nodes[3]; // Nodes on the first three lists. + Rankings* my_rankings; + }; + + Rankings(); + ~Rankings(); + + bool Init(BackendImpl* backend, bool count_lists); + + // Restores original state, leaving the object ready for initialization. + void Reset(); + + // Inserts a given entry at the head of the queue. + void Insert(CacheRankingsBlock* node, bool modified, List list); + + // Removes a given entry from the LRU list. If |strict| is true, this method + // assumes that |node| is not pointed to by an active iterator. On the other + // hand, removing that restriction allows the current "head" of an iterator + // to be removed from the list (basically without control of the code that is + // performing the iteration), so it should be used with extra care. + void Remove(CacheRankingsBlock* node, List list, bool strict); + + // Moves a given entry to the head. + void UpdateRank(CacheRankingsBlock* node, bool modified, List list); + + // Iterates through the list. + CacheRankingsBlock* GetNext(CacheRankingsBlock* node, List list); + CacheRankingsBlock* GetPrev(CacheRankingsBlock* node, List list); + void FreeRankingsBlock(CacheRankingsBlock* node); + + // Controls tracking of nodes used for enumerations. + void TrackRankingsBlock(CacheRankingsBlock* node, bool start_tracking); + + // Peforms a simple self-check of the lists, and returns the number of items + // or an error code (negative value). + int SelfCheck(); + + // Returns false if the entry is clearly invalid. from_list is true if the + // node comes from the LRU list. + bool SanityCheck(CacheRankingsBlock* node, bool from_list) const; + bool DataSanityCheck(CacheRankingsBlock* node, bool from_list) const; + + // Sets the |contents| field of |node| to |address|. + void SetContents(CacheRankingsBlock* node, CacheAddr address); + + private: + typedef std::pair<CacheAddr, CacheRankingsBlock*> IteratorPair; + typedef std::list<IteratorPair> IteratorList; + + void ReadHeads(); + void ReadTails(); + void WriteHead(List list); + void WriteTail(List list); + + // Gets the rankings information for a given rankings node. We may end up + // sharing the actual memory with a loaded entry, but we are not taking a + // reference to that entry, so |rankings| must be short lived. + bool GetRanking(CacheRankingsBlock* rankings); + + // Makes |rankings| suitable to live a long life. + void ConvertToLongLived(CacheRankingsBlock* rankings); + + // Finishes a list modification after a crash. + void CompleteTransaction(); + void FinishInsert(CacheRankingsBlock* rankings); + void RevertRemove(CacheRankingsBlock* rankings); + + // Returns false if node is not properly linked. This method may change the + // provided |list| to reflect the list where this node is actually stored. + bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev, + CacheRankingsBlock* next, List* list); + + // Checks the links between two consecutive nodes. + bool CheckSingleLink(CacheRankingsBlock* prev, CacheRankingsBlock* next); + + // Peforms a simple check of the list, and returns the number of items or an + // error code (negative value). + int CheckList(List list); + + // Walks a list in the desired direction until the nodes |end1| or |end2| are + // reached. Returns an error code (0 on success), the number of items verified + // and the addresses of the last nodes visited. + int CheckListSection(List list, Addr end1, Addr end2, bool forward, + Addr* last, Addr* second_last, int* num_items); + + // Returns true if addr is the head or tail of any list. When there is a + // match |list| will contain the list number for |addr|. + bool IsHead(CacheAddr addr, List* list) const; + bool IsTail(CacheAddr addr, List* list) const; + + // Updates the iterators whenever node is being changed. + void UpdateIterators(CacheRankingsBlock* node); + + // Invalidates the iterators pointing to this node. + void InvalidateIterators(CacheRankingsBlock* node); + + // Keeps track of the number of entries on a list. + void IncrementCounter(List list); + void DecrementCounter(List list); + + bool init_; + bool count_lists_; + Addr heads_[LAST_ELEMENT]; + Addr tails_[LAST_ELEMENT]; + BackendImpl* backend_; + LruData* control_data_; // Data related to the LRU lists. + IteratorList iterators_; + + DISALLOW_COPY_AND_ASSIGN(Rankings); +}; + +} // namespace disk_cache + +#endif // NET_DISK_CACHE_BLOCKFILE_RANKINGS_H_ |