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
17namespace disk_cache {
18
19class BackendImpl;
20struct LruData;
21struct RankingsNode;
22typedef StorageBlock<RankingsNode> CacheRankingsBlock;
23
24// Type of crashes generated for the unit tests.
25enum 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.
53class 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_
215