page_evictioner_other.hpp

Go to the documentation of this file.

#ifndef __ZERO_PAGE_EVICTIONER_OTHER_HPP
#define __ZERO_PAGE_EVICTIONER_OTHER_HPP

#include "page_evictioner.hpp"
#include "buffer_pool.hpp"
#include "multi_clock.hpp"
#include "hashtable_deque.hpp"
#include <mutex>
#include <cmath>

namespace zero::buffer_pool {

    template<bool on_page_unfix/* = false*/>
    class PageEvictionerCAR : public PageEvictioner {
    public:
        PageEvictionerCAR(const BufferPool* bufferPool) :
                PageEvictioner(bufferPool),
                _clocks(bufferPool->getBlockCount()),
                _b1(bufferPool->getBlockCount() - 1),
                _b2(bufferPool->getBlockCount() - 1),
                _p(0),
                _c(bufferPool->getBlockCount() - 1),
                _handMovement(0) {};

        ~PageEvictionerCAR() final {};

        bf_idx pickVictim() noexcept final {
            bool evictedPage = false;
            bf_idx blockedT1 = 0;
            bf_idx blockedT2 = 0;

            while (!evictedPage) {
                if (should_exit()) {
                    return 0;
                } // the buffer index 0 has the semantics of null

                if (_handMovement >= _c) {
                    smlevel_0::bf->getPageCleaner()->wakeup(false);
                    DBG3(<< "Run Page_Cleaner ...");
                    _handMovement = 0;
                }
                uint32_t iterations = (blockedT1 + blockedT2) / _c;
                if ((blockedT1 + blockedT2) % _c == 0 && (blockedT1 + blockedT2) > 0) {
                    DBG1(<< "Iterated " << iterations << "-times in CAR's pick_victim().");
                }
                w_assert1(iterations < 3);
                DBG3(<< "p = " << _p);
                std::lock_guard<std::mutex> guard(_latch);
                if ((_clocks.sizeOf<T_1>() >= std::max<uint32_t>(uint32_t(1), _p) || blockedT2 >= _clocks.sizeOf<T_2>())
                    && blockedT1 < _clocks.sizeOf<T_1>()) {
                    bool t1Head;
                    _clocks.getHead<T_1>(t1Head);
                    bf_idx t1HeadIndex;
                    _clocks.getHeadIndex<T_1>(t1HeadIndex);
                    w_assert1(t1HeadIndex != 0);

                    if (!t1Head) {
                        evictedPage = evictOne(t1HeadIndex);
                        PageID evictedPID = smlevel_0::bf->getControlBlock(t1HeadIndex)._pid;

                        if (evictedPage) {
                            _clocks.removeHead<T_1>(t1HeadIndex);
                            _b1.pushToBack(evictedPID);
                            DBG5(<< "Removed from T_1: " << t1HeadIndex << "; New size: " << _clocks.sizeOf<T_1>() << "; Free frames: " << smlevel_0::bf->getFreeList()->getCount());
                            return t1HeadIndex;
                        } else {
                            _clocks.moveHead<T_1>();
                            blockedT1++;
                            _handMovement++;
                            continue;
                        }
                    } else {
                        _clocks.setHead<T_1>(false);

                        _clocks.switchHeadToTail<T_1, T_2>(t1HeadIndex);
                        DBG5(<< "Removed from T_1: " << t1HeadIndex << "; New size: " << _clocks.sizeOf<T_1>() << "; Free frames: " << smlevel_0::bf->getFreeList()->getCount());
                        DBG5(<< "Added to T_2: " << t1HeadIndex << "; New size: " << _clocks.sizeOf<T_2>() << "; Free frames: " << smlevel_0::bf->getFreeList()->getCount());
                        continue;
                    }
                } else if (blockedT2 < _clocks.sizeOf<T_2>()) {
                    bool t2Head;
                    _clocks.getHead<T_2>(t2Head);
                    bf_idx t2HeadIndex;
                    _clocks.getHeadIndex<T_2>(t2HeadIndex);
                    w_assert1(t2HeadIndex != 0);

                    if (!t2Head) {
                        evictedPage = evictOne(t2HeadIndex);
                        PageID evictedPID = smlevel_0::bf->getControlBlock(t2HeadIndex)._pid;

                        if (evictedPage) {
                            _clocks.removeHead<T_2>(t2HeadIndex);
                            _b2.pushToBack(evictedPID);
                            DBG5(<< "Removed from T_2: " << t2HeadIndex << "; New size: " << _clocks.sizeOf<T_2>() << "; Free frames: " << smlevel_0::bf->getFreeList()->getCount());

                            return t2HeadIndex;
                        } else {
                            _clocks.moveHead<T_2>();
                            blockedT2++;
                            _handMovement++;
                            continue;
                        }
                    } else {
                        _clocks.setHead<T_2>(false);

                        _clocks.moveHead<T_2>();
                        _handMovement++;
                        continue;
                    }
                } else {
                    return 0;
                }
            }
            return 0;           // Suppress compiler warning about missing return statement!
        };

        void updateOnPageHit(bf_idx idx) noexcept final {
            if constexpr (!on_page_unfix) {
                _clocks.set(idx, true);
            }
        };

        void updateOnPageUnfix(bf_idx idx) noexcept final {
            if constexpr (on_page_unfix) {
                _clocks.set(idx, true);
            }
        };

        void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            std::lock_guard<std::mutex> guard(_latch);
            if (!_b1.contains(pid) && !_b2.contains(pid)) {
                if (_clocks.sizeOf<T_1>() + _b1.length() >= _c) {
                    _b1.popFromFront();
                } else if (_clocks.sizeOf<T_1>() + _clocks.sizeOf<T_2>() + _b1.length() + _b2.length() >= 2 * (_c)) {
                    _b2.popFromFront();
                }
                _clocks.addTail<T_1>(idx);
                DBG5(<< "Added to T_1: " << idx << "; New size: " << _clocks.sizeOf<T_1>() << "; Free frames: " << smlevel_0::bf->getFreeList()->getCount());
                _clocks.set(idx, false);
            } else if (_b1.contains(pid)) {
                _p = std::min(_p + std::max<uint32_t>(uint32_t(1), (_b2.length() / _b1.length())), _c);
                _b1.remove(pid);
                _clocks.addTail<T_2>(idx);
                DBG5(<< "Added to T_2: " << idx << "; New size: " << _clocks.sizeOf<T_2>() << "; Free frames: " << smlevel_0::bf->getFreeList()->getCount());
                _clocks.set(idx, false);
            } else {
                _p = std::max<int32_t>(int32_t(_p) - std::max<int32_t>(1, (_b1.length() / _b2.length())), 0);
                _b2.remove(pid);
                _clocks.addTail<T_2>(idx);
                DBG5(<< "Added to T_2: " << idx << "; New size: " << _clocks.sizeOf<T_2>() << "; Free frames: " << smlevel_0::bf->getFreeList()->getCount());
                _clocks.set(idx, false);
            }
            w_assert1(0 <= _clocks.sizeOf<T_1>() + _clocks.sizeOf<T_2>()
                      && _clocks.sizeOf<T_1>() + _clocks.sizeOf<T_2>() <= _c);
            w_assert1(0 <= _clocks.sizeOf<T_1>() + _b1.length() && _clocks.sizeOf<T_1>() + _b1.length() <= _c);
            w_assert1(0 <= _clocks.sizeOf<T_2>() + _b2.length() && _clocks.sizeOf<T_2>() + _b2.length() <= 2 * (_c));
            w_assert1(0 <= _clocks.sizeOf<T_1>() + _clocks.sizeOf<T_2>() + _b1.length() + _b2.length()
                      && _clocks.sizeOf<T_1>() + _clocks.sizeOf<T_2>() + _b1.length() + _b2.length() <= 2 * (_c));
        };

        void updateOnPageFixed(bf_idx idx) noexcept final {};

        void updateOnPageDirty(bf_idx idx) noexcept final {};

        void updateOnPageBlocked(bf_idx idx) noexcept final {};

        void updateOnPageSwizzled(bf_idx idx) noexcept final {};

        void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            try {
                _clocks.remove(idx);
            } catch (const multi_clock::MultiHandedClockNotContainedException<bf_idx, bool, 2, 0>& ex) {}
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        virtual void releaseInternalLatches() noexcept final {
            _latch.unlock();
        };

    protected:
        multi_clock::MultiHandedClock<bf_idx, bool, 2, 0> _clocks;

        hashtable_deque::HashtableDeque<PageID, 1 | 0x80000000> _b1;

        hashtable_deque::HashtableDeque<PageID, 1 | 0x80000000> _b2;

        u_int32_t _p;

        u_int32_t _c;

        bf_idx _handMovement;

        std::mutex _latch;

        enum clock_index {
            T_1 = 0,
            T_2 = 1
        };
    };
} // zero::buffer_pool
#endif // __ZERO_PAGE_EVICTIONER_OTHER_HPP