net/disk_cache/blockfile/rankings.h

   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_