Home | History | Annotate | Download | only in disk_cache 
      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_RANKINGS_H_
      8 #define NET_DISK_CACHE_RANKINGS_H_
      9 
     10 #include <list>
     11 
     12 #include "base/memory/scoped_ptr.h"
     13 #include "net/disk_cache/addr.h"
     14 #include "net/disk_cache/mapped_file.h"
     15 #include "net/disk_cache/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     explicit Iterator(Rankings* rankings);
     98     ~Iterator();
     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_RANKINGS_H_
    215