TwoQVictimPolicy.h

Go to the documentation of this file.

/*
// $Id: //open/dev/fennel/cache/TwoQVictimPolicy.h#8 $
// Fennel is a library of data storage and processing components.
// Copyright (C) 2005-2009 The Eigenbase Project
// Copyright (C) 2005-2009 SQLstream, Inc.
// Copyright (C) 2005-2009 LucidEra, Inc.
// Portions Copyright (C) 1999-2009 John V. Sichi
//
// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 of the License, or (at your option)
// any later version approved by The Eigenbase Project.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#ifndef Fennel_TwoQVictimPolicy_Included
#define Fennel_TwoQVictimPolicy_Included

#include "fennel/common/IntrusiveDList.h"

#include <boost/dynamic_bitset.hpp>

FENNEL_BEGIN_NAMESPACE

class FENNEL_CACHE_EXPORT TwoQPageQueue
{
    IntrusiveDListNode *head;

    IntrusiveDListNode *tail;

    uint len;

    void validateQueue()
    {
        assert(head == NULL || head->getPrev() == NULL);
        assert(tail == NULL || tail->getNext() == NULL);

        uint actualLen = 0;
        IntrusiveDListNode *curr = head;
        while (curr != NULL) {
            actualLen++;
            curr = curr->getNext();
        }
        assert(actualLen == len);

        curr = tail;
        actualLen = 0;
        while (curr != NULL) {
            actualLen++;
            curr = curr->getPrev();
        }
        assert(actualLen == len);
    }

public:
    TwoQPageQueue()
    {
        head = NULL;
        tail = NULL;
        len = 0;
    }

    void insertAtHead(IntrusiveDListNode &page)
    {
        if (head == NULL) {
            assert(tail == NULL);
            tail = &page;
        } else {
            page.insertBefore(*head);
        }
        head = &page;
        len++;
    }

    void moveToHead(IntrusiveDListNode &page)
    {
        if (head == &page) {
            return;
        }
        if (tail == &page) {
            tail = page.getPrev();
        }
        page.detach();
        page.insertBefore(*head);
        head = &page;
    }

    void insertAtTail(IntrusiveDListNode &page)
    {
        if (tail == NULL) {
            assert(head == NULL);
            head = &page;
        } else {
            page.insertAfter(*tail);
        }
        tail = &page;
        len++;
    }

    void moveToTail(IntrusiveDListNode &page)
    {
        if (tail == &page) {
            return;
        }
        if (head == &page) {
            head = page.getNext();
        }
        page.detach();
        page.insertAfter(*tail);
        tail = &page;
    }

    void remove(IntrusiveDListNode &page)
    {
        assert(len == 1 || (page.getNext() != NULL || page.getPrev() != NULL));
        if (&page == head && &page == tail) {
            assert(len == 1);
            head = tail = NULL;
        } else if (&page == head) {
            head = head->getNext();
        } else if (&page == tail) {
            tail = tail->getPrev();
        }
        page.detach();
        assert(len > 0);
        len--;
    }

    uint size()
    {
        return len;
    }

    IntrusiveDListNode *getHead()
    {
        return head;
    }
};

class FENNEL_CACHE_EXPORT TwoQDirtyPage
    : public IntrusiveDListNode
{
public:
    enum DirtyPageState {
        PAGE_CLEAN,

        PAGE_DIRTY_POPULAR_UNPINNED,

        PAGE_DIRTY_FRESHMAN,

        PAGE_DIRTY_POPULAR_PINNED
    };

private:
    CachePage *pParentPage;

    DirtyPageState dirtyState;

public:
    void setParentPage(CachePage &parentPageInit)
    {
        pParentPage = &parentPageInit;
    }

    CachePage &getParentPage()
    {
        return *pParentPage;
    }

    DirtyPageState getDirtyState()
    {
        return dirtyState;
    }

    void setDirtyState(DirtyPageState newState)
    {
        dirtyState = newState;
    }
};

class FENNEL_CACHE_EXPORT TwoQVictim
    : public IntrusiveDListNode
{
public:
    enum PageState {
        PAGE_STATE_POPULAR_PINNED,
        PAGE_STATE_POPULAR_UNPINNED,
        PAGE_STATE_FRESHMAN,
        PAGE_STATE_FREE
    };

private:
    PageState state;

    TwoQDirtyPage dirtyPageNode;

public:

    TwoQVictim()
    {
        state = PAGE_STATE_FREE;
        dirtyPageNode.setDirtyState(TwoQDirtyPage::PAGE_CLEAN);
    }

    PageState getState()
    {
        return state;
    }

    void setState(PageState newState)
    {
        state = newState;
    }

    TwoQDirtyPage &getDirtyPageNode()
    {
        return dirtyPageNode;
    }
};

template <class PageT>
class TwoQPageListIter : public IntrusiveTwoDListIter<PageT, PageT>
{
    virtual PageT *getReturnElement(PageT *page) const
    {
        return page;
    }

public:
    TwoQPageListIter()
        : IntrusiveTwoDListIter<PageT, PageT>()
    {
    }

    TwoQPageListIter(PageT *list1, PageT *list2)
        : IntrusiveTwoDListIter<PageT, PageT>(list1, list2)
    {
    }

    ~TwoQPageListIter()
    {
    }
};


template <class PageT>
class TwoQDirtyPageListIter : public IntrusiveTwoDListIter<TwoQDirtyPage, PageT>
{
    virtual PageT *getReturnElement(TwoQDirtyPage *dirtyPage) const
    {
        if (dirtyPage == NULL) {
            return NULL;
        } else {
            return static_cast<PageT *>(&(dirtyPage->getParentPage()));
        }
    }

public:
    TwoQDirtyPageListIter()
        : IntrusiveTwoDListIter<TwoQDirtyPage, PageT>()
    {
    }

    TwoQDirtyPageListIter(TwoQDirtyPage *list1, TwoQDirtyPage *list2)
        : IntrusiveTwoDListIter<TwoQDirtyPage, PageT>(list1, list2)
    {
    }

    ~TwoQDirtyPageListIter()
    {
    }
};

template <class PageT>
class TwoQVictimPolicy
{
    SXMutex mutex;

    TwoQPageQueue popularPinnedQueue;

    TwoQPageQueue popularUnpinnedQueue;

    TwoQPageQueue freshmenQueue;

    TwoQPageQueue dirtyPopularUnpinnedQueue;

    TwoQPageQueue dirtyFreshmenQueue;

    std::vector<BlockId> historyQueue;

    uint historyQueueStart;

    uint currHistoryQueueLen;

    boost::dynamic_bitset<> historyBitmap;

    uint nCachePages;

    uint maxFreshmenQueueLen;

    uint maxHistoryQueueLen;

    uint freshmenQueuePercentage;

    uint pageHistoryQueuePercentage;

    void init()
    {
        nCachePages = 0;
        maxFreshmenQueueLen = 0;
        maxHistoryQueueLen = 0;
        historyQueueStart = 0;
        currHistoryQueueLen = 0;
    }

    bool isPageClean(PageT &page)
    {
        return
            (!page.isDirty() &&
                page.getDirtyPageNode().getDirtyState() ==
                    TwoQDirtyPage::PAGE_CLEAN);
    }

    void notifyPopularPageAccess(PageT &page, bool pin)
    {
        assert(mutex.isLocked(LOCKMODE_X));
        TwoQVictim::PageState state = page.TwoQVictim::getState();
        assert(
            state != TwoQVictim::PAGE_STATE_FRESHMAN &&
            state != TwoQVictim::PAGE_STATE_POPULAR_PINNED);

        if (pin) {
            // Remove the page from the popular-unpinned queues and add
            // it to the popular-pinned queue.
            if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
                popularUnpinnedQueue.remove(page);
                TwoQDirtyPage &dirtyPageNode =
                    page.TwoQVictim::getDirtyPageNode();
                if (dirtyPageNode.getDirtyState() ==
                    TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
                {
                    dirtyPopularUnpinnedQueue.remove(dirtyPageNode);
                    dirtyPageNode.setDirtyState(
                        TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED);
                } else {
                    assert(isPageClean(page));
                }
            }
            popularPinnedQueue.insertAtTail(page);
            page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_POPULAR_PINNED);

        } else {
            // Move the page to the end of the popular-unpinned queues.
            if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
                popularUnpinnedQueue.moveToTail(page);
                TwoQDirtyPage &dirtyPageNode =
                    page.TwoQVictim::getDirtyPageNode();
                if (dirtyPageNode.getDirtyState() ==
                    TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
                {
                    dirtyPopularUnpinnedQueue.moveToTail(dirtyPageNode);
                } else {
                    assert(isPageClean(page));
                }
            } else {
                // The page was originally free and now needs to be put
                // into the popular-unpinned queue.
                assert(isPageClean(page));
                popularUnpinnedQueue.insertAtTail(page);
                page.TwoQVictim::setState(
                    TwoQVictim::PAGE_STATE_POPULAR_UNPINNED);
            }
        }
    }

public:

    typedef TwoQPageListIter<PageT> PageIterator;

    typedef TwoQDirtyPageListIter<PageT> DirtyPageIterator;

    typedef SXMutexSharedGuard SharedGuard;

    typedef SXMutexExclusiveGuard ExclusiveGuard;

    TwoQVictimPolicy()
    {
        init();
        freshmenQueuePercentage = CacheParams::defaultFreshmenQueuePercentage;
        pageHistoryQueuePercentage =
            CacheParams::defaultPageHistoryQueuePercentage;
    }

    TwoQVictimPolicy(const CacheParams &params)
    {
        init();
        freshmenQueuePercentage = params.freshmenQueuePercentage;
        pageHistoryQueuePercentage = params.pageHistoryQueuePercentage;
    }

    void setAllocatedPageCount(uint nCachePagesInit)
    {
        ExclusiveGuard exclusiveGuard(mutex);

        if (nCachePagesInit == nCachePages) {
            return;
        }

        uint newHistoryQueueLen =
            nCachePagesInit * pageHistoryQueuePercentage / 100;
        if ((currHistoryQueueLen > newHistoryQueueLen) ||
            (historyQueueStart != 0))
        {
            // If the new queue is smaller than the currently used size,
            // copy the existing history queue into a temporary vector,
            // truncating the front of the queue to match the size of
            // the new vector.  We also need to recreate the vector if
            // the new queue is larger than the currently used size,
            // and the existing history queue has cycled around such
            // that the starting element is no longer at position 0.
            std::vector<BlockId> temp;
            temp.resize(newHistoryQueueLen);
            uint excess =
                (currHistoryQueueLen > newHistoryQueueLen)
                    ? (currHistoryQueueLen - newHistoryQueueLen) : 0;
            currHistoryQueueLen -= excess;
            for (uint i = 0; i < currHistoryQueueLen; i++) {
                temp[i] =
                    historyQueue[
                        (historyQueueStart + excess + i) %
                        maxHistoryQueueLen];
            }
            historyQueueStart = 0;
            historyQueue.resize(newHistoryQueueLen);
            historyQueue.swap(temp);
        } else {
            historyQueue.resize(newHistoryQueueLen);
        }

        // It's possible that a blockId has been removed from the history
        // bitmap, but the corresponding update hasn't been made in the
        // history queue itself.  If so, remove the blockId from the queue
        // so when we rebuild the bitmap below, that blockId won't be included.
        assert(historyQueueStart == 0);
        for (uint i = 0; i < currHistoryQueueLen; i++) {
            if (!historyBitmap.test(
                opaqueToInt(historyQueue[i] % historyBitmap.size())))
            {
                historyQueue[i] = NULL_BLOCK_ID;
            }
        }

        nCachePages = nCachePagesInit;
        maxFreshmenQueueLen = nCachePages * freshmenQueuePercentage / 100;
        maxHistoryQueueLen = newHistoryQueueLen;

        historyBitmap.resize(maxHistoryQueueLen * 64);
        // Rebuild the history bitmap, if there are existing entries in the
        // history queue.  Ignore the invalid blockIds.
        if (currHistoryQueueLen > 0) {
            historyBitmap.reset();
            for (uint i = 0; i < currHistoryQueueLen; i++) {
                if (historyQueue[i] != NULL_BLOCK_ID) {
                    historyBitmap.set(
                        opaqueToInt(historyQueue[i]) % historyBitmap.size());
                }
            }
        }
    }

    void registerPage(PageT &page)
    {
        page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_FREE);
        page.TwoQVictim::getDirtyPageNode().setParentPage(page);
        page.TwoQVictim::getDirtyPageNode().setDirtyState(
            TwoQDirtyPage::PAGE_CLEAN);
    }

    void unregisterPage(PageT &page)
    {
        assert(page.TwoQVictim::getState() == TwoQVictim::PAGE_STATE_FREE);
        assert(
            page.TwoQVictim::getDirtyPageNode().getDirtyState() ==
            TwoQDirtyPage::PAGE_CLEAN);
    }

    void notifyPageAccess(PageT &page, bool pin)
    {
        ExclusiveGuard exclusiveGuard(mutex);

        switch (page.TwoQVictim::getState()) {
        case TwoQVictim::PAGE_STATE_FRESHMAN:
        case TwoQVictim::PAGE_STATE_POPULAR_PINNED:
            return;

        case TwoQVictim::PAGE_STATE_POPULAR_UNPINNED:
            notifyPopularPageAccess(page, pin);
            break;

        case TwoQVictim::PAGE_STATE_FREE:
            if (historyBitmap.test(
                opaqueToInt(page.getBlockId()) % historyBitmap.size()))
            {
                notifyPopularPageAccess(page, pin);
            } else {
                assert(isPageClean(page));
                page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_FRESHMAN);
                freshmenQueue.insertAtTail(page);
            }
            break;

        default:
            permAssert(false);
        }
    }

    void notifyPageNice(PageT &page)
    {
        ExclusiveGuard exclusiveGuard(mutex);
        TwoQVictim::PageState state = page.TwoQVictim::getState();
        assert(state != TwoQVictim::PAGE_STATE_FREE);

        if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
            popularUnpinnedQueue.moveToHead(page);
            TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
            if (dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
            {
                dirtyPopularUnpinnedQueue.moveToHead(dirtyPageNode);
            } else {
                assert(isPageClean(page));
            }
        } else if (state == TwoQVictim::PAGE_STATE_FRESHMAN) {
            freshmenQueue.moveToHead(page);
            TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
            if (dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_FRESHMAN)
            {
                dirtyFreshmenQueue.moveToHead(dirtyPageNode);
            } else {
                assert(isPageClean(page));
            }
        }
    }

    void notifyPageMap(PageT &page, bool pin)
    {
        // first access for a newly mapped page will not get a corresponding
        // call to notifyPageAcces, so do it now
        notifyPageAccess(page, pin);
    }

    void notifyPageUnmap(PageT &page, bool discard)
    {
        ExclusiveGuard exclusiveGuard(mutex);
        TwoQVictim::PageState state = page.TwoQVictim::getState();
        assert(
            state != TwoQVictim::PAGE_STATE_POPULAR_PINNED &&
            state != TwoQVictim::PAGE_STATE_FREE);

        if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
            popularUnpinnedQueue.remove(page);
            TwoQDirtyPage &dirtyPageNode =
                page.TwoQVictim::getDirtyPageNode();
            if (dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED)
            {
                dirtyPopularUnpinnedQueue.remove(dirtyPageNode);
                dirtyPageNode.setDirtyState(TwoQDirtyPage::PAGE_CLEAN);
            } else {
                assert(isPageClean(page));
            }
        } else {
            // If the page is currently in the freshmen queue, add it to
            // the history queue, unless the page is being discarded.
            // Remove the page currently at the head of the history queue,
            // if the history queue is at max capacity.  Also make the
            // corresponding updates in the history bitmap.
            if (!discard) {
                if (currHistoryQueueLen >= maxHistoryQueueLen) {
                    historyBitmap.set(
                        opaqueToInt(historyQueue[historyQueueStart])
                            % historyBitmap.size(),
                        false);
                    historyQueueStart =
                        (historyQueueStart + 1) % maxHistoryQueueLen;
                    currHistoryQueueLen--;
                }
                uint currIdx =
                    (historyQueueStart + currHistoryQueueLen) %
                        maxHistoryQueueLen;
                historyQueue[currIdx] = page.getBlockId();
                historyBitmap.set(
                    opaqueToInt(page.getBlockId()) % historyBitmap.size());
                currHistoryQueueLen++;
            }

            freshmenQueue.remove(page);
            TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
            if (dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_FRESHMAN)
            {
                dirtyFreshmenQueue.remove(dirtyPageNode);
                dirtyPageNode.setDirtyState(TwoQDirtyPage::PAGE_CLEAN);
            } else {
                assert(isPageClean(page));
            }
        }

        // If the page is being discarded, remove it from the history bitmap.
        // Just clear the blockId from the history bitmap, but leave the
        // blockId in the history queue itself.  The page will get cleaned out
        // if we need to resize the history queue.
        if (discard) {
            historyBitmap.set(
                opaqueToInt(page.getBlockId()) % historyBitmap.size(),
                false);
        }

        page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_FREE);
        assert(page.getNext() == NULL && page.getPrev() == NULL);
    }

    void notifyPageUnpin(PageT &page)
    {
        ExclusiveGuard exclusiveGuard(mutex);
        TwoQVictim::PageState state = page.TwoQVictim::getState();
        assert(
            state != TwoQVictim::PAGE_STATE_POPULAR_UNPINNED &&
            state != TwoQVictim::PAGE_STATE_FREE);

        // If the page is poular and pinned, move it to the popular-unpinned
        // queues.
        if (state == TwoQVictim::PAGE_STATE_POPULAR_PINNED) {
            popularPinnedQueue.remove(page);
            popularUnpinnedQueue.insertAtTail(page);
            TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
            if (dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED)
            {
                dirtyPopularUnpinnedQueue.insertAtTail(dirtyPageNode);
                dirtyPageNode.setDirtyState(
                    TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED);
            } else {
                assert(isPageClean(page));
            }
            page.TwoQVictim::setState(TwoQVictim::PAGE_STATE_POPULAR_UNPINNED);
        }
        // If the page state is free or a freshman, then there's nothing to do
    }

    void notifyPageDirty(PageT &page)
    {
        ExclusiveGuard exclusiveGuard(mutex);
        TwoQVictim::PageState state = page.TwoQVictim::getState();
        assert(state != TwoQVictim::PAGE_STATE_FREE);

        TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
        assert(
            dirtyPageNode.getDirtyState() == TwoQDirtyPage::PAGE_CLEAN);

        // Set the dirty state to match the queue containing the page, and
        // then if appropriate, add the dirty node to the corresponding
        // dirty queue.  In the case of pages that are in the popular-pinned
        // queue, just set the dirty state since we don't have a dirty queue
        // for popular-pinned pages.  But we need to set the dirty state so
        // we know that the page is dirty when it's unpinned and moved to
        // the popular-unpinned queue.
        if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
            dirtyPopularUnpinnedQueue.insertAtTail(dirtyPageNode);
            dirtyPageNode.setDirtyState(
                TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED);
        } else if (state == TwoQVictim::PAGE_STATE_FRESHMAN) {
            dirtyFreshmenQueue.insertAtTail(dirtyPageNode);
            dirtyPageNode.setDirtyState(
                    TwoQDirtyPage::PAGE_DIRTY_FRESHMAN);
        } else if (state == TwoQVictim::PAGE_STATE_POPULAR_PINNED) {
            dirtyPageNode.setDirtyState(
                TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED);
        }
    }

    void notifyPageClean(PageT &page)
    {
        ExclusiveGuard exclusiveGuard(mutex);
        TwoQVictim::PageState state = page.TwoQVictim::getState();
        // Note that it is possible for the page to be in the popular-pinned
        // queue if the page has just been pinned and the thread accessing
        // the page is waiting for I/O on the page to complete before using it.
        assert(state != TwoQVictim::PAGE_STATE_FREE);

        // Remove the dirty node from the queue if it's currently in a
        // queue, and then reset its dirty state to indicate that the page
        // is now clean.
        TwoQDirtyPage &dirtyPageNode = page.TwoQVictim::getDirtyPageNode();
        if (state == TwoQVictim::PAGE_STATE_POPULAR_UNPINNED) {
            assert(
                dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_POPULAR_UNPINNED);
            dirtyPopularUnpinnedQueue.remove(dirtyPageNode);
        } else if (state == TwoQVictim::PAGE_STATE_FRESHMAN) {
            assert(
                dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_FRESHMAN);
            dirtyFreshmenQueue.remove(dirtyPageNode);
        } else if (state == TwoQVictim::PAGE_STATE_POPULAR_PINNED) {
            assert(
                dirtyPageNode.getDirtyState() ==
                TwoQDirtyPage::PAGE_DIRTY_POPULAR_PINNED);
        }
        dirtyPageNode.setDirtyState(TwoQDirtyPage::PAGE_CLEAN);
    }

    void notifyPageDiscard(BlockId blockId)
    {
        ExclusiveGuard exclusiveGuard(mutex);
        // Just clear the blockId from the history bitmap, but leave the
        // blockId in the history queue itself.  The page will get cleaned out
        // if we need to resize the history queue.
        historyBitmap.set(opaqueToInt(blockId % historyBitmap.size()), false);
    }

    SXMutex &getMutex()
    {
        return mutex;
    }

    std::pair<PageIterator,PageIterator> getVictimRange()
    {
        // If the freshmen queue has hit its size limit, victimize from
        // that queue first.  If all of its pages are pinned, then try
        // victimizing from the popular-unpinned page queue.  Do the
        // reverse if the freshmen queue has hit its size limit.

        if (freshmenQueue.size() < maxFreshmenQueueLen) {
            return std::pair<PageIterator, PageIterator>(
                PageIterator(
                    static_cast<PageT *>(popularUnpinnedQueue.getHead()),
                    static_cast<PageT *>(freshmenQueue.getHead())),
                PageIterator());
        } else {
            return std::pair<PageIterator, PageIterator>(
                PageIterator(
                    static_cast<PageT *>(freshmenQueue.getHead()),
                    static_cast<PageT *>(popularUnpinnedQueue.getHead())),
                PageIterator());
        }
    }

    std::pair<DirtyPageIterator,DirtyPageIterator> getDirtyVictimRange()
    {
        // If the freshmen queue has hit its size limit, victimize from
        // that queue first.  If all of its pages are pinned, then try
        // victimizing from the popular-unpinned page queue.  Do the
        // reverse if the freshmen queue has hit its size limit.

        if (freshmenQueue.size() < maxFreshmenQueueLen) {
            return std::pair<DirtyPageIterator, DirtyPageIterator>(
                DirtyPageIterator(
                    static_cast<TwoQDirtyPage *>(
                        dirtyPopularUnpinnedQueue.getHead()),
                    static_cast<TwoQDirtyPage *>(dirtyFreshmenQueue.getHead())),
                DirtyPageIterator());
        } else {
            return std::pair<DirtyPageIterator, DirtyPageIterator>(
                DirtyPageIterator(
                    static_cast<TwoQDirtyPage *>(dirtyFreshmenQueue.getHead()),
                    static_cast<TwoQDirtyPage *>(
                        dirtyPopularUnpinnedQueue.getHead())),
                DirtyPageIterator());
        }
    }
};

FENNEL_END_NAMESPACE

#endif

// End TwoQVictimPolicy.h

---