Home | History | Annotate | Download | only in disk_cache 
      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 
     18 namespace disk_cache {
     19 
     20 class BackendImpl;
     21 
     22 // Type of crashes generated for the unit tests.
     23 enum 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.
     51 class 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.
    116   void Remove(CacheRankingsBlock* node, List list);
    117 
    118   // Moves a given entry to the head.
    119   void UpdateRank(CacheRankingsBlock* node, bool modified, List list);
    120 
    121   // Iterates through the list.
    122   CacheRankingsBlock* GetNext(CacheRankingsBlock* node, List list);
    123   CacheRankingsBlock* GetPrev(CacheRankingsBlock* node, List list);
    124   void FreeRankingsBlock(CacheRankingsBlock* node);
    125 
    126   // Controls tracking of nodes used for enumerations.
    127   void TrackRankingsBlock(CacheRankingsBlock* node, bool start_tracking);
    128 
    129   // Peforms a simple self-check of the lists, and returns the number of items
    130   // or an error code (negative value).
    131   int SelfCheck();
    132 
    133   // Returns false if the entry is clearly invalid. from_list is true if the
    134   // node comes from the LRU list.
    135   bool SanityCheck(CacheRankingsBlock* node, bool from_list);
    136 
    137  private:
    138   typedef std::pair<CacheAddr, CacheRankingsBlock*> IteratorPair;
    139   typedef std::list<IteratorPair> IteratorList;
    140 
    141   void ReadHeads();
    142   void ReadTails();
    143   void WriteHead(List list);
    144   void WriteTail(List list);
    145 
    146   // Gets the rankings information for a given rankings node. We may end up
    147   // sharing the actual memory with a loaded entry, but we are not taking a
    148   // reference to that entry, so |rankings| must be short lived.
    149   bool GetRanking(CacheRankingsBlock* rankings);
    150 
    151   // Makes |rankings| suitable to live a long life.
    152   void ConvertToLongLived(CacheRankingsBlock* rankings);
    153 
    154   // Finishes a list modification after a crash.
    155   void CompleteTransaction();
    156   void FinishInsert(CacheRankingsBlock* rankings);
    157   void RevertRemove(CacheRankingsBlock* rankings);
    158 
    159   // Returns false if this entry will not be recognized as dirty (called during
    160   // selfcheck).
    161   bool CheckEntry(CacheRankingsBlock* rankings);
    162 
    163   // Returns false if node is not properly linked. This method may change the
    164   // provided |list| to reflect the list where this node is actually stored.
    165   bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
    166                   CacheRankingsBlock* next, List* list);
    167 
    168   // Checks the links between two consecutive nodes.
    169   bool CheckSingleLink(CacheRankingsBlock* prev, CacheRankingsBlock* next);
    170 
    171   // Peforms a simple check of the list, and returns the number of items or an
    172   // error code (negative value).
    173   int CheckList(List list);
    174 
    175   // Returns true if addr is the head or tail of any list. When there is a
    176   // match |list| will contain the list number for |addr|.
    177   bool IsHead(CacheAddr addr, List* list);
    178   bool IsTail(CacheAddr addr, List* list);
    179 
    180   // Updates the iterators whenever node is being changed.
    181   void UpdateIterators(CacheRankingsBlock* node);
    182 
    183   // Invalidates the iterators pointing to this node.
    184   void InvalidateIterators(CacheRankingsBlock* node);
    185 
    186   // Keeps track of the number of entries on a list.
    187   void IncrementCounter(List list);
    188   void DecrementCounter(List list);
    189 
    190   bool init_;
    191   bool count_lists_;
    192   Addr heads_[LAST_ELEMENT];
    193   Addr tails_[LAST_ELEMENT];
    194   BackendImpl* backend_;
    195   LruData* control_data_;  // Data related to the LRU lists.
    196   IteratorList iterators_;
    197 
    198   DISALLOW_COPY_AND_ASSIGN(Rankings);
    199 };
    200 
    201 }  // namespace disk_cache
    202 
    203 #endif  // NET_DISK_CACHE_RANKINGS_H_
    204