Home | History | Annotate | Download | only in disk_cache 
      1 // Copyright (c) 2006-2008 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/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 
     21 // Type of crashes generated for the unit tests.
     22 enum RankCrashes {
     23   NO_CRASH = 0,
     24   INSERT_EMPTY_1,
     25   INSERT_EMPTY_2,
     26   INSERT_EMPTY_3,
     27   INSERT_ONE_1,
     28   INSERT_ONE_2,
     29   INSERT_ONE_3,
     30   INSERT_LOAD_1,
     31   INSERT_LOAD_2,
     32   REMOVE_ONE_1,
     33   REMOVE_ONE_2,
     34   REMOVE_ONE_3,
     35   REMOVE_ONE_4,
     36   REMOVE_HEAD_1,
     37   REMOVE_HEAD_2,
     38   REMOVE_HEAD_3,
     39   REMOVE_HEAD_4,
     40   REMOVE_TAIL_1,
     41   REMOVE_TAIL_2,
     42   REMOVE_TAIL_3,
     43   REMOVE_LOAD_1,
     44   REMOVE_LOAD_2,
     45   REMOVE_LOAD_3,
     46   MAX_CRASH
     47 };
     48 
     49 // This class handles the ranking information for the cache.
     50 class Rankings {
     51  public:
     52   // Possible lists of entries.
     53   enum List {
     54     NO_USE = 0,   // List of entries that have not been reused.
     55     LOW_USE,      // List of entries with low reuse.
     56     HIGH_USE,     // List of entries with high reuse.
     57     RESERVED,     // Reserved for future use.
     58     DELETED,      // List of recently deleted or doomed entries.
     59     LAST_ELEMENT
     60   };
     61 
     62   // This class provides a specialized version of scoped_ptr, that calls
     63   // Rankings whenever a CacheRankingsBlock is deleted, to keep track of cache
     64   // iterators that may go stale.
     65   class ScopedRankingsBlock : public scoped_ptr<CacheRankingsBlock> {
     66    public:
     67     ScopedRankingsBlock() : rankings_(NULL) {}
     68     explicit ScopedRankingsBlock(Rankings* rankings) : rankings_(rankings) {}
     69     ScopedRankingsBlock(Rankings* rankings, CacheRankingsBlock* node)
     70         : scoped_ptr<CacheRankingsBlock>(node), rankings_(rankings) {}
     71 
     72     ~ScopedRankingsBlock() {
     73       rankings_->FreeRankingsBlock(get());
     74     }
     75 
     76     void set_rankings(Rankings* rankings) {
     77       rankings_ = rankings;
     78     }
     79 
     80     // scoped_ptr::reset will delete the object.
     81     void reset(CacheRankingsBlock* p = NULL) {
     82       if (p != get())
     83         rankings_->FreeRankingsBlock(get());
     84       scoped_ptr<CacheRankingsBlock>::reset(p);
     85     }
     86 
     87    private:
     88     Rankings* rankings_;
     89     DISALLOW_EVIL_CONSTRUCTORS(ScopedRankingsBlock);
     90   };
     91 
     92   // If we have multiple lists, we have to iterate through all at the same time.
     93   // This structure keeps track of where we are on the iteration.
     94   struct Iterator {
     95     List list;                     // Which entry was returned to the user.
     96     CacheRankingsBlock* nodes[3];  // Nodes on the first three lists.
     97     Rankings* my_rankings;
     98     explicit Iterator(Rankings* rankings) {
     99       memset(this, 0, sizeof(Iterator));
    100       my_rankings = rankings;
    101     }
    102     ~Iterator() {
    103       for (int i = 0; i < 3; i++)
    104         ScopedRankingsBlock(my_rankings, nodes[i]);
    105     }
    106   };
    107 
    108   Rankings() : init_(false) {}
    109   ~Rankings() {}
    110 
    111   bool Init(BackendImpl* backend, bool count_lists);
    112 
    113   // Restores original state, leaving the object ready for initialization.
    114   void Reset();
    115 
    116   // Inserts a given entry at the head of the queue.
    117   void Insert(CacheRankingsBlock* node, bool modified, List list);
    118 
    119   // Removes a given entry from the LRU list.
    120   void Remove(CacheRankingsBlock* node, List list);
    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);
    140 
    141  private:
    142   typedef std::pair<CacheAddr, CacheRankingsBlock*> IteratorPair;
    143   typedef std::list<IteratorPair> IteratorList;
    144 
    145   void ReadHeads();
    146   void ReadTails();
    147   void WriteHead(List list);
    148   void WriteTail(List list);
    149 
    150   // Gets the rankings information for a given rankings node. We may end up
    151   // sharing the actual memory with a loaded entry, but we are not taking a
    152   // reference to that entry, so |rankings| must be short lived.
    153   bool GetRanking(CacheRankingsBlock* rankings);
    154 
    155   // Makes |rankings| suitable to live a long life.
    156   void ConvertToLongLived(CacheRankingsBlock* rankings);
    157 
    158   // Finishes a list modification after a crash.
    159   void CompleteTransaction();
    160   void FinishInsert(CacheRankingsBlock* rankings);
    161   void RevertRemove(CacheRankingsBlock* rankings);
    162 
    163   // Returns false if this entry will not be recognized as dirty (called during
    164   // selfcheck).
    165   bool CheckEntry(CacheRankingsBlock* rankings);
    166 
    167   // Returns false if node is not properly linked.
    168   bool CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
    169                   CacheRankingsBlock* next, List list);
    170 
    171   // Checks the links between two consecutive nodes.
    172   bool CheckSingleLink(CacheRankingsBlock* prev, CacheRankingsBlock* next);
    173 
    174   // Peforms a simple check of the list, and returns the number of items or an
    175   // error code (negative value).
    176   int CheckList(List list);
    177 
    178   // Returns true if addr is the head or tail of any list.
    179   bool IsHead(CacheAddr addr);
    180   bool IsTail(CacheAddr addr);
    181 
    182   // Updates the iterators whenever node is being changed.
    183   void UpdateIterators(CacheRankingsBlock* node);
    184 
    185   // Invalidates the iterators pointing to this node.
    186   void InvalidateIterators(CacheRankingsBlock* node);
    187 
    188   // Keeps track of the number of entries on a list.
    189   void IncrementCounter(List list);
    190   void DecrementCounter(List list);
    191 
    192   bool init_;
    193   bool count_lists_;
    194   Addr heads_[LAST_ELEMENT];
    195   Addr tails_[LAST_ELEMENT];
    196   BackendImpl* backend_;
    197   LruData* control_data_;  // Data related to the LRU lists.
    198   IteratorList iterators_;
    199 
    200   DISALLOW_COPY_AND_ASSIGN(Rankings);
    201 };
    202 
    203 }  // namespace disk_cache
    204 
    205 #endif  // NET_DISK_CACHE_RANKINGS_H_
    206