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
18namespace disk_cache {
19
20class BackendImpl;
21
22// Type of crashes generated for the unit tests.
23enum 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.
51class 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:
68    ScopedRankingsBlock() : rankings_(NULL) {}
69    explicit ScopedRankingsBlock(Rankings* rankings) : rankings_(rankings) {}
70    ScopedRankingsBlock(Rankings* rankings, CacheRankingsBlock* node)
71        : scoped_ptr<CacheRankingsBlock>(node), rankings_(rankings) {}
72
73    ~ScopedRankingsBlock() {
74      rankings_->FreeRankingsBlock(get());
75    }
76
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