LRUVictimPolicy< PageT > Class Template Reference

LRUVictimPolicy implements the least-recently-used policy for cache victimization. More...

#include <LRUVictimPolicy.h>

List of all members.

Public Types

typedef IntrusiveDListIter<
PageT > 		PageIterator
 All models for VictimPolicy must define a nested public type PageIterator, which is used by CacheImpl to iterate over candidate victims in optimal order.
typedef IntrusiveDListIter<
PageT > 		DirtyPageIterator
 All models for VictimPolicy must define a nested public type DirtyPageIterator, which is used by CacheImpl to iterate over pages that can potentially be flushed by the lazy page writer that runs in a background thread.
typedef SXMutexSharedGuard SharedGuard
 All models for VictimPolicy must define a nested public type SharedGuard, which is held by CacheImpl while iterating over candidate victims.
typedef SXMutexExclusiveGuard ExclusiveGuard
 Guard for write access to mutex.

Public Member Functions

 LRUVictimPolicy ()
 All models for VictimPolicy must have a default constructor.
 LRUVictimPolicy (const CacheParams &params)
void setAllocatedPageCount (uint nCachePages)
 Receives notification from CacheImpl, indicating the total number of buffer pages in the cache.
void registerPage (PageT &page)
 Receives notification from CacheImpl when a page is allocated, giving the VictimPolicy a chance to initialize its own data structures for this page.
void unregisterPage (PageT &page)
 Receives notification from CacheImpl when a page is freed, giving the VictimPolicy a chance to deinitialize its own data structures for this page.
void notifyPageAccess (PageT &page, bool pin)
 Receives notification from CacheImpl when a page is accessed.
void notifyPageNice (PageT &page)
 Receives notification from CacheImpl on a hint that a page is a good candidate for victimization.
void notifyPageMap (PageT &page, bool pin)
 Receives notification from CacheImpl just after a page is mapped.
void notifyPageUnmap (PageT &page, bool discard)
 Receives notification from CacheImpl just before a page is unmapped.
void notifyPageUnpin (PageT &page)
 Receives notification from CacheImpl that a page no longer needs to be pinned.
void notifyPageDirty (PageT &page)
 Receives notification from CacheImpl that a page has been marked as dirty.
void notifyPageClean (PageT &page)
 Receives notification from CacheImpl that a page is no longer dirty.
void notifyPageDiscard (BlockId blockId)
 Receives notification from CacheImpl that a page has been discarded from the cache.
SXMutex & getMutex ()
 Provides an SXMutex to CacheImpl to be acquired before calling getVictimRange().
std::pair< PageIterator, PageIterator > getVictimRange ()
 Provides a range of candidate victims to CacheImpl.
std::pair< DirtyPageIterator,
DirtyPageIterator > 		getDirtyVictimRange ()
 Provides a range of candidate victims for flushing to CacheImpl.

Private Attributes

SXMutex mutex
 SXMutex protecting LRU page chain.
PageT * pageLRU
 Most-recently accessed page; this is one end of a queue implemented as a doubly-linked list.
PageT * pageMRU
 Least-recently accessed page; this is the other end of a queue implemented as a doubly-linked list.

Detailed Description

template<class PageT>
class LRUVictimPolicy< PageT >

LRUVictimPolicy implements the least-recently-used policy for cache victimization.

It is a model for the VictimPolicy concept. The public documentation on this class also serves as a generic specification of the VictimPolicy concept.

Note that any realization for PageT must inherit both CachePage and LRUVictim as bases.

Definition at line 55 of file LRUVictimPolicy.h.

Member Typedef Documentation

template<class PageT>
typedef IntrusiveDListIter<PageT> LRUVictimPolicy< PageT >::PageIterator

All models for VictimPolicy must define a nested public type PageIterator, which is used by CacheImpl to iterate over candidate victims in optimal order.

This type must be a model for a standard forward iterator. For LRUVictimPolicy, this is accomplished by iterating over the doubly-linked list of pages from LRU to MRU.

Definition at line 83 of file LRUVictimPolicy.h.

template<class PageT>
typedef IntrusiveDListIter<PageT> LRUVictimPolicy< PageT >::DirtyPageIterator

All models for VictimPolicy must define a nested public type DirtyPageIterator, which is used by CacheImpl to iterate over pages that can potentially be flushed by the lazy page writer that runs in a background thread.

In the case of LRUVictimPolicy, this iterator is identical to PageIterator. A separate iterator is defined to allow victimization policies to optimize the iterator to exclude "clean" pages.

Definition at line 94 of file LRUVictimPolicy.h.

template<class PageT>
typedef SXMutexSharedGuard LRUVictimPolicy< PageT >::SharedGuard

All models for VictimPolicy must define a nested public type SharedGuard, which is held by CacheImpl while iterating over candidate victims.

This guard must provide any synchronization required to protect the iteration against concurrent modifications. The guard will be initialized with the result of getMutex(). For LRUVictimPolicy, the guard is a read guard protecting the doubly-linked list, meaning notifications are blocked during iteration since they have to modify the chain.

Definition at line 106 of file LRUVictimPolicy.h.

template<class PageT>
typedef SXMutexExclusiveGuard LRUVictimPolicy< PageT >::ExclusiveGuard

Guard for write access to mutex.

Definition at line 111 of file LRUVictimPolicy.h.

Constructor & Destructor Documentation

template<class PageT>
LRUVictimPolicy< PageT >::LRUVictimPolicy (  )  [inline]

All models for VictimPolicy must have a default constructor.

Definition at line 116 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::pageLRU, and LRUVictimPolicy< PageT >::pageMRU.

00117     {
00118         pageLRU = NULL;
00119         pageMRU = NULL;
00120     }

template<class PageT>
LRUVictimPolicy< PageT >::LRUVictimPolicy ( const CacheParams &  params  )  [inline]

Definition at line 122 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::pageLRU, and LRUVictimPolicy< PageT >::pageMRU.

00123     {
00124         pageLRU = NULL;
00125         pageMRU = NULL;
00126     }

Member Function Documentation

template<class PageT>
void LRUVictimPolicy< PageT >::setAllocatedPageCount ( uint  nCachePages  )  [inline]

Receives notification from CacheImpl, indicating the total number of buffer pages in the cache.

Parameters:
nCachePages number of buffer pages in the cache

Definition at line 134 of file LRUVictimPolicy.h.

00135     {
00136     }

template<class PageT>
void LRUVictimPolicy< PageT >::registerPage ( PageT &  page  )  [inline]

Receives notification from CacheImpl when a page is allocated, giving the VictimPolicy a chance to initialize its own data structures for this page.

Parameters:
page the page being allocated

Definition at line 145 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::mutex, LRUVictimPolicy< PageT >::pageLRU, and LRUVictimPolicy< PageT >::pageMRU.

00146     {
00147         // TODO:  use a DList container to avoid this edge case
00148         ExclusiveGuard exclusiveGuard(mutex);
00149         if (!pageLRU) {
00150             pageLRU = &page;
00151         } else {
00152             page.IntrusiveDListNode::insertAfter(*pageMRU);
00153         }
00154         pageMRU = &page;
00155     }

template<class PageT>
void LRUVictimPolicy< PageT >::unregisterPage ( PageT &  page  )  [inline]

Receives notification from CacheImpl when a page is freed, giving the VictimPolicy a chance to deinitialize its own data structures for this page.

Parameters:
page the page being freed

Definition at line 164 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::mutex, LRUVictimPolicy< PageT >::pageLRU, and LRUVictimPolicy< PageT >::pageMRU.

00165     {
00166         ExclusiveGuard exclusiveGuard(mutex);
00167         if (&page == pageLRU) {
00168             pageLRU = (PageT *) (page.getNext());
00169         }
00170         if (&page == pageMRU) {
00171             pageMRU = (PageT *) (page.getPrev());
00172         }
00173         page.IntrusiveDListNode::detach();
00174     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageAccess ( PageT &  page,
bool  pin 
) [inline]

Receives notification from CacheImpl when a page is accessed.

On entry, the page's mutex is held by the calling thread, so the state of the page (e.g. its mapped BlockId) is guaranteed to remain stable. This is true for all other notify methods as well. For LRUVictimPolicy, a page access results in the page being moved to the MRU end of the list.

Parameters:
page the page being accessed
pin if true, the page being accessed will be pinned in the cache

Definition at line 186 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::mutex, LRUVictimPolicy< PageT >::pageLRU, and LRUVictimPolicy< PageT >::pageMRU.

Referenced by LRUVictimPolicy< PageT >::notifyPageMap(), and LRUVictimPolicy< PageT >::notifyPageUnmap().

00187     {
00188         ExclusiveGuard exclusiveGuard(mutex);
00189         if (&page == pageMRU) {
00190             return;
00191         }
00192         if (&page == pageLRU) {
00193             pageLRU = (PageT *) (page.getNext());
00194         }
00195         page.IntrusiveDListNode::detach();
00196         page.IntrusiveDListNode::insertAfter(*pageMRU);
00197         pageMRU = &page;
00198     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageNice ( PageT &  page  )  [inline]

Receives notification from CacheImpl on a hint that a page is a good candidate for victimization.

For LRUVictimPolicy, this results in the page being moved to the LRU end of the list.

Parameters:
page the page to which the hint pertains

Definition at line 207 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::mutex, LRUVictimPolicy< PageT >::pageLRU, and LRUVictimPolicy< PageT >::pageMRU.

00208     {
00209         ExclusiveGuard exclusiveGuard(mutex);
00210         if (&page == pageLRU) {
00211             return;
00212         }
00213         if (&page == pageMRU) {
00214             pageMRU = (PageT *) (page.getPrev());
00215         }
00216         page.IntrusiveDListNode::detach();
00217         page.IntrusiveDListNode::insertBefore(*pageLRU);
00218         pageLRU = &page;
00219     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageMap ( PageT &  page,
bool  pin 
) [inline]

Receives notification from CacheImpl just after a page is mapped.

This implies an access as well, so for efficiency no corresponding notifyPageAccess notification is received.

Parameters:
page the page being mapped
pin if true, the page being mapped will be pinned in the cache

Definition at line 229 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::notifyPageAccess().

00230     {
00231         // first access for a newly mapped page will not get a corresponding
00232         // call to notifyPageAccess, so do it now
00233         notifyPageAccess(page, pin);
00234     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageUnmap ( PageT &  page,
bool  discard 
) [inline]

Receives notification from CacheImpl just before a page is unmapped.

The Page object still has the ID being unmapped.

Parameters:
page the page being unmapped
discard true if the page is also being discarded from the cache

Definition at line 244 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::notifyPageAccess().

00245     {
00246         // move the unmapped page to the MRU position so that it will not be
00247         // treated as a candidate for flush
00248         notifyPageAccess(page, false);
00249     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageUnpin ( PageT &  page  )  [inline]

Receives notification from CacheImpl that a page no longer needs to be pinned.

Parameters:
page the unpinned page

Definition at line 257 of file LRUVictimPolicy.h.

00258     {
00259     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageDirty ( PageT &  page  )  [inline]

Receives notification from CacheImpl that a page has been marked as dirty.

Parameters:
page the dirty page

Definition at line 267 of file LRUVictimPolicy.h.

00268     {
00269     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageClean ( PageT &  page  )  [inline]

Receives notification from CacheImpl that a page is no longer dirty.

Parameters:
page the clean page

Definition at line 276 of file LRUVictimPolicy.h.

00277     {
00278     }

template<class PageT>
void LRUVictimPolicy< PageT >::notifyPageDiscard ( BlockId  blockId  )  [inline]

Receives notification from CacheImpl that a page has been discarded from the cache.

This allows the policy to remove any history of the page, if it's tracking that information.

Parameters:
blockId the blockId of the page being deallocated

Definition at line 287 of file LRUVictimPolicy.h.

00288     {
00289     }

template<class PageT>
SXMutex& LRUVictimPolicy< PageT >::getMutex (  )  [inline]

Provides an SXMutex to CacheImpl to be acquired before calling getVictimRange().

The mutex guard is held for the duration of the iteration.

Returns:
a reference to the RW_Mutex protecting the LRU list

Definition at line 298 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::mutex.

00299     {
00300         return mutex;
00301     }

template<class PageT>
std::pair<PageIterator,PageIterator> LRUVictimPolicy< PageT >::getVictimRange (  )  [inline]

Provides a range of candidate victims to CacheImpl.

Returns:
a pair of PageIterators, where pair.first references the best victim and pair.second is the end of the victim range

Definition at line 309 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::pageLRU.

Referenced by LRUVictimPolicy< PageT >::getDirtyVictimRange().

00310     {
00311         return std::pair<PageIterator,PageIterator>(
00312             PageIterator(pageLRU),PageIterator());
00313     }

template<class PageT>
std::pair<DirtyPageIterator,DirtyPageIterator> LRUVictimPolicy< PageT >::getDirtyVictimRange (  )  [inline]

Provides a range of candidate victims for flushing to CacheImpl.

Returns:
a pair of DirtyPageIterators, where pair.first references the best victim and pair.second is the end of the victim range

Definition at line 321 of file LRUVictimPolicy.h.

References LRUVictimPolicy< PageT >::getVictimRange().

00322     {
00323         return
00324             static_cast<std::pair<DirtyPageIterator,DirtyPageIterator> >(
00325                 getVictimRange());
00326     }

Member Data Documentation

template<class PageT>
SXMutex LRUVictimPolicy< PageT >::mutex [private]

SXMutex protecting LRU page chain.

Definition at line 60 of file LRUVictimPolicy.h.

Referenced by LRUVictimPolicy< PageT >::getMutex(), LRUVictimPolicy< PageT >::notifyPageAccess(), LRUVictimPolicy< PageT >::notifyPageNice(), LRUVictimPolicy< PageT >::registerPage(), and LRUVictimPolicy< PageT >::unregisterPage().

template<class PageT>
PageT* LRUVictimPolicy< PageT >::pageLRU [private]

Most-recently accessed page; this is one end of a queue implemented as a doubly-linked list.

Definition at line 66 of file LRUVictimPolicy.h.

Referenced by LRUVictimPolicy< PageT >::getVictimRange(), LRUVictimPolicy< PageT >::LRUVictimPolicy(), LRUVictimPolicy< PageT >::notifyPageAccess(), LRUVictimPolicy< PageT >::notifyPageNice(), LRUVictimPolicy< PageT >::registerPage(), and LRUVictimPolicy< PageT >::unregisterPage().

template<class PageT>
PageT* LRUVictimPolicy< PageT >::pageMRU [private]

Least-recently accessed page; this is the other end of a queue implemented as a doubly-linked list.

Definition at line 72 of file LRUVictimPolicy.h.

Referenced by LRUVictimPolicy< PageT >::LRUVictimPolicy(), LRUVictimPolicy< PageT >::notifyPageAccess(), LRUVictimPolicy< PageT >::notifyPageNice(), LRUVictimPolicy< PageT >::registerPage(), and LRUVictimPolicy< PageT >::unregisterPage().

The documentation for this class was generated from the following file:
Generated on Mon Jun 22 04:00:39 2009 for Fennel by  doxygen 1.5.1