SegPageIter Class Reference

When visiting a chain of pages via Segment.getPageSuccessor, SegPageIter can be used to automatically initiate prefetches. More...

#include <SegPageIter.h>

Inheritance diagram for SegPageIter:

SegPageEntryIter< EntryT > List of all members.

Public Member Functions

 SegPageIter ()
 Constructor: iterator starts out singular.
void mapRange (SegmentAccessor const &segmentAccessor, PageId beginPageId, PageId endPageId=NULL_PAGE_ID)
 Begins a new iteration.
PageId operator * () const
 
Returns:
the current PageId in the iteration

void operator++ ()
 Moves to the next prefetched PageId.
void forcePrefetchReject ()
 Forces the next pre-fetch request to be rejected.
void makeSingular ()
 Aborts any iteration in progress and release all resources.
bool isSingular () const
 
Returns:
true iff no iteration is in progress


Protected Member Functions

void initPrefetchQueue ()
 Reads the pre-fetch parameters, sizes the pre-fetch queue, and initializes various state variables related to the queue.
void prefetchPage (PageId pageId)
 Pre-fetches a specified page.

Protected Attributes

SegmentAccessor segmentAccessor
 Accessor for the Segment containing the pages to be visited.
PageId endPageId
 PageId at which to stop iteration.
std::vector< PageId > prefetchQueue
 Fixed-size circular queue of prefetched PageIds, indexed by iFetch.
uint iFetch
 Position in prefetchQueue.
bool atEnd
 Whether end of iteration has been reached by prefetch (but not necessarily by fetch).
uint queueSize
 Current size of the pre-fetch queue.
int nFreePageSlots
 Number of slots available in the prefetchQueue.

Private Attributes

uint prefetchPagesMax
 Maximum number of outstanding pre-fetch requests.
uint prefetchThrottleRate
 Number of successful pre-fetches before pre-fetch can be throttled back up.
uint currPageSlot
 Current slot in the prefetchQueue that needs to be populated.
bool noPrefetch
 True if pre-fetches have been turned off.
uint throttleCount
 The remaining number of successful pre-fetches that need to occur before the pre-fetch rate can be throttled back up.
bool forceReject
 If true, force the next pre-fetch request to be rejected.

Detailed Description

When visiting a chain of pages via Segment.getPageSuccessor, SegPageIter can be used to automatically initiate prefetches.

The caller supplies the starting point, and the SegPageIter class takes care of reading ahead in the chain via getPageSuccessor and issuing prefetch calls.

NOTE: this is not an STL-style iterator.

Definition at line 44 of file SegPageIter.h.

Constructor & Destructor Documentation

SegPageIter::SegPageIter (  )  [explicit]

Constructor: iterator starts out singular.

Definition at line 40 of file SegPageIter.cpp.

00041 {
00042 }

Member Function Documentation

void SegPageIter::initPrefetchQueue (  )  [protected]

Reads the pre-fetch parameters, sizes the pre-fetch queue, and initializes various state variables related to the queue.

Definition at line 66 of file SegPageIter.cpp.

References atEnd, currPageSlot, forceReject, iFetch, nFreePageSlots, noPrefetch, SegmentAccessor::pCacheAccessor, prefetchPagesMax, prefetchQueue, prefetchThrottleRate, queueSize, segmentAccessor, and throttleCount.

Referenced by mapRange(), and SegPageEntryIter< EntryT >::mapRange().

00067 {
00068     segmentAccessor.pCacheAccessor->getPrefetchParams(
00069         prefetchPagesMax,
00070         prefetchThrottleRate);
00071     queueSize = prefetchPagesMax;
00072     noPrefetch = (queueSize == 0);
00073     // Reset the queue size so we have space to store at least one page
00074     if (queueSize < 1) {
00075         queueSize = 1;
00076     }
00077     prefetchQueue.resize(queueSize);
00078 
00079     nFreePageSlots = queueSize;
00080     currPageSlot = 0;
00081     iFetch = 0;
00082     atEnd = 0;
00083     throttleCount = 0;
00084     forceReject = false;
00085 }

void SegPageIter::prefetchPage ( PageId  pageId  )  [protected]

Pre-fetches a specified page.

Parameters:
pageId the id of the page to be pre-fetched

Definition at line 110 of file SegPageIter.cpp.

References atEnd, currPageSlot, endPageId, forceReject, iFetch, nFreePageSlots, noPrefetch, NULL_BLOCK_ID, SegmentAccessor::pCacheAccessor, prefetchPagesMax, prefetchQueue, prefetchThrottleRate, SegmentAccessor::pSegment, queueSize, segmentAccessor, and throttleCount.

Referenced by mapRange(), operator++(), and SegPageEntryIter< EntryT >::prefetchPages().

00111 {
00112     // Store the page we're about to pre-fetch in the first empty slot
00113     // in the queue
00114     prefetchQueue[currPageSlot++] = pageId;
00115     currPageSlot %= queueSize;
00116     --nFreePageSlots;
00117 
00118     if (pageId == endPageId) {
00119         atEnd = 1;
00120         return;
00121     }
00122 
00123     // If pre-fetches are turned off, don't bothering issuing the pre-fetch
00124     // request.
00125     BlockId blockId = NULL_BLOCK_ID;
00126     if (!forceReject && !noPrefetch) {
00127         blockId = segmentAccessor.pSegment->translatePageId(pageId);
00128     }
00129     if (!forceReject &&
00130         (noPrefetch ||
00131             segmentAccessor.pCacheAccessor->prefetchPage(
00132                 blockId,
00133                 segmentAccessor.pSegment->getMappedPageListener(blockId))))
00134     {
00135         // If the pre-fetch rate was throttled down, then wait until we
00136         // reach the desired number of successful pre-fetches before
00137         // throttling the rate back up, one page at a time.
00138         if (throttleCount > 0) {
00139             assert(prefetchPagesMax != 0);
00140             if (--throttleCount == 0) {
00141                 // At a minimum, reenable pre-fetches
00142                 noPrefetch = false;
00143 
00144                 // If we haven't throttled back to the max pre-fetch
00145                 // rate, then reset the counter so we can continue
00146                 // counting successful pre-fetches to allow the rate
00147                 // to continue throttling up.  In the case where the
00148                 // pre-fetch rate is a single page, no further throttling
00149                 // is possible.
00150                 if (prefetchPagesMax > 1) {
00151                     nFreePageSlots++;
00152                     if (nFreePageSlots < prefetchPagesMax) {
00153                         throttleCount = prefetchThrottleRate;
00154                     }
00155                 }
00156             }
00157         }
00158     } else {
00159         // If pre-fetches aren't already disabled, then set the number of
00160         // pre-fetches to the number of outstanding pre-fetches by
00161         // disallowing any new pre-fetches until the existing ones are used.
00162         // If we're down to doing a single pre-fetch, then turn off
00163         // pre-fetches.
00164         if (prefetchPagesMax > 0) {
00165             if (nFreePageSlots > 0) {
00166                 nFreePageSlots = 0;
00167             }
00168             if (iFetch == currPageSlot) {
00169                 noPrefetch = true;
00170             }
00171             throttleCount = prefetchThrottleRate;
00172         }
00173         forceReject = false;
00174     }
00175 }

void SegPageIter::mapRange ( SegmentAccessor const &  segmentAccessor,
PageId  beginPageId,
PageId  endPageId = NULL_PAGE_ID 
)

Begins a new iteration.

Parameters:
segmentAccessor accessor for the segment containing the pages to visit
beginPageId the ID of the first page to visit
endPageId the ID at which to end iteration; by default, this is NULL_PAGE_ID (representing the sentinel end of a chain) but the iteration (and prefetch) can be stopped earlier with some other known PageId; note that endPageId itself will not be prefetched

Reimplemented in SegPageEntryIter< EntryT >, SegPageEntryIter< BTreePrefetchSearchKey >, and SegPageEntryIter< LcsRid >.

Definition at line 44 of file SegPageIter.cpp.

References atEnd, endPageId, initPrefetchQueue(), SegmentAccessor::pCacheAccessor, prefetchPage(), prefetchQueue, SegmentAccessor::pSegment, queueSize, and segmentAccessor.

Referenced by SegInputStream::startPrefetch(), and SegPageIterTest::testIter().

00048 {
00049     assert(segmentAccessorInit.pSegment);
00050     assert(segmentAccessorInit.pCacheAccessor);
00051     segmentAccessor = segmentAccessorInit;
00052     initPrefetchQueue();
00053     endPageId = endPageIdInit;
00054     for (uint i = 0; i < queueSize; i++) {
00055         if (atEnd) {
00056             break;
00057         }
00058         if (i > 0) {
00059             beginPageIdInit = segmentAccessor.pSegment->getPageSuccessor(
00060                 prefetchQueue[i - 1]);
00061         }
00062         prefetchPage(beginPageIdInit);
00063     }
00064 }

PageId SegPageIter::operator * (  )  const [inline]

Returns:
the current PageId in the iteration

Definition at line 156 of file SegPageIter.h.

00157     {
00158         assert(!isSingular());
00159         return prefetchQueue[iFetch];
00160     }

void SegPageIter::operator++ (  ) 

Moves to the next prefetched PageId.

An assertion violation results if called when positioned on endPageId.

Reimplemented in SegPageEntryIter< EntryT >, SegPageEntryIter< BTreePrefetchSearchKey >, and SegPageEntryIter< LcsRid >.

Definition at line 87 of file SegPageIter.cpp.

References atEnd, currPageSlot, endPageId, iFetch, isSingular(), nFreePageSlots, prefetchPage(), prefetchQueue, SegmentAccessor::pSegment, queueSize, and segmentAccessor.

00088 {
00089     assert(!isSingular());
00090     assert(**this != endPageId);
00091 
00092     // Move past the page currently at the front of the queue.
00093     iFetch = (iFetch + 1) % queueSize;
00094     ++nFreePageSlots;
00095 
00096     if (atEnd) {
00097         return;
00098     }
00099 
00100     // Pre-fetch a page to replace the page that was at the front
00101     // of the queue.
00102     int iPrev = currPageSlot - 1;
00103     if (iPrev < 0) {
00104         iPrev += queueSize;
00105     }
00106     prefetchPage(
00107         segmentAccessor.pSegment->getPageSuccessor(prefetchQueue[iPrev]));
00108 }

void SegPageIter::forcePrefetchReject (  ) 

Forces the next pre-fetch request to be rejected.

Used for testing purposes.

Definition at line 177 of file SegPageIter.cpp.

References forceReject.

Referenced by SegPageIterTest::testIter(), and SegPageEntryIterTest::testIter().

00178 {
00179     forceReject = true;
00180 }

void SegPageIter::makeSingular (  )  [inline]

Aborts any iteration in progress and release all resources.

Reimplemented in SegPageEntryIter< EntryT >, SegPageEntryIter< BTreePrefetchSearchKey >, and SegPageEntryIter< LcsRid >.

Definition at line 177 of file SegPageIter.h.

Referenced by SegInputStream::closeImpl(), SegInputStream::endPrefetch(), SegPageEntryIter< LcsRid >::makeSingular(), and SegPageIterTest::testIter().

00178     {
00179         segmentAccessor.reset();
00180     }

bool SegPageIter::isSingular (  )  const [inline]

Returns:
true iff no iteration is in progress

Reimplemented in SegPageEntryIter< EntryT >, SegPageEntryIter< BTreePrefetchSearchKey >, and SegPageEntryIter< LcsRid >.

Definition at line 185 of file SegPageIter.h.

Referenced by SegPageEntryIter< LcsRid >::isSingular(), operator++(), SegInputStream::readNextBuffer(), SegInputStream::readPrevBuffer(), SegInputStream::reset(), and SegInputStream::seekSegPos().

00186     {
00187         return segmentAccessor.pSegment ? false : true;
00188     }

Member Data Documentation

uint SegPageIter::prefetchPagesMax [private]

Maximum number of outstanding pre-fetch requests.

Definition at line 49 of file SegPageIter.h.

Referenced by initPrefetchQueue(), and prefetchPage().

uint SegPageIter::prefetchThrottleRate [private]

Number of successful pre-fetches before pre-fetch can be throttled back up.

Definition at line 55 of file SegPageIter.h.

Referenced by initPrefetchQueue(), and prefetchPage().

uint SegPageIter::currPageSlot [private]

Current slot in the prefetchQueue that needs to be populated.

Definition at line 60 of file SegPageIter.h.

Referenced by initPrefetchQueue(), operator++(), and prefetchPage().

bool SegPageIter::noPrefetch [private]

True if pre-fetches have been turned off.

Definition at line 65 of file SegPageIter.h.

Referenced by initPrefetchQueue(), and prefetchPage().

uint SegPageIter::throttleCount [private]

The remaining number of successful pre-fetches that need to occur before the pre-fetch rate can be throttled back up.

Definition at line 71 of file SegPageIter.h.

Referenced by initPrefetchQueue(), and prefetchPage().

bool SegPageIter::forceReject [private]

If true, force the next pre-fetch request to be rejected.

Definition at line 76 of file SegPageIter.h.

Referenced by forcePrefetchReject(), initPrefetchQueue(), and prefetchPage().

SegmentAccessor SegPageIter::segmentAccessor [protected]

Accessor for the Segment containing the pages to be visited.

Definition at line 82 of file SegPageIter.h.

Referenced by initPrefetchQueue(), mapRange(), SegPageEntryIter< EntryT >::mapRange(), operator++(), and prefetchPage().

PageId SegPageIter::endPageId [protected]

PageId at which to stop iteration.

Definition at line 87 of file SegPageIter.h.

Referenced by mapRange(), SegPageEntryIter< EntryT >::mapRange(), operator++(), SegPageEntryIter< EntryT >::operator++(), prefetchPage(), and SegPageEntryIter< EntryT >::prefetchPages().

std::vector<PageId> SegPageIter::prefetchQueue [protected]

Fixed-size circular queue of prefetched PageIds, indexed by iFetch.

Definition at line 92 of file SegPageIter.h.

Referenced by initPrefetchQueue(), mapRange(), SegPageEntryIter< LcsRid >::operator *(), operator++(), and prefetchPage().

uint SegPageIter::iFetch [protected]

Position in prefetchQueue.

Definition at line 97 of file SegPageIter.h.

Referenced by initPrefetchQueue(), SegPageEntryIter< LcsRid >::operator *(), operator++(), SegPageEntryIter< EntryT >::operator++(), and prefetchPage().

bool SegPageIter::atEnd [protected]

Whether end of iteration has been reached by prefetch (but not necessarily by fetch).

Definition at line 103 of file SegPageIter.h.

Referenced by initPrefetchQueue(), mapRange(), operator++(), SegPageEntryIter< EntryT >::operator++(), prefetchPage(), and SegPageEntryIter< EntryT >::prefetchPages().

uint SegPageIter::queueSize [protected]

Current size of the pre-fetch queue.

Definition at line 108 of file SegPageIter.h.

Referenced by initPrefetchQueue(), mapRange(), operator++(), SegPageEntryIter< EntryT >::operator++(), and prefetchPage().

int SegPageIter::nFreePageSlots [protected]

Number of slots available in the prefetchQueue.

May temporarily become negative in the case where pre-fetches are turned off.

Definition at line 114 of file SegPageIter.h.

Referenced by initPrefetchQueue(), operator++(), SegPageEntryIter< EntryT >::operator++(), prefetchPage(), and SegPageEntryIter< EntryT >::prefetchPages().

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