nn/fnd/fnd_BuddyHeap.h

/*---------------------------------------------------------------------------*
  Project:  Horizon
  File:     fnd_BuddyHeap.h

  Copyright (C)2009 Nintendo Co., Ltd.  All rights reserved.

  These coded instructions, statements, and computer programs contain
  proprietary information of Nintendo of America Inc. and/or Nintendo
  Company Ltd., and are protected by Federal copyright law.  They may
  not be disclosed to third parties or copied or duplicated in any form,
  in whole or in part, without the prior written consent of Nintendo.

  $Rev: 23169 $
 *---------------------------------------------------------------------------*/

#ifndef NN_FND_FND_BUDDYHEAP_H_
#define NN_FND_FND_BUDDYHEAP_H_

#include <nn/types.h>
#include <nn/fnd/fnd_HeapBase.h>
#include <nn/fnd/fnd_Allocator.h>

namespace nn {
namespace fnd {

template<size_t PageSize, s32 MaxOrder>
class BuddyHeapBase : public nn::fnd::HeapBase
{
protected:
    template <s32 align, typename T>
    static T DivUp(T x)
    {
        return static_cast<T>( (x + (align - 1)) / align );
    }

    template<size_t alignment>
    static uptr RoundDown(uptr addr)
    {
        return (addr / alignment) * alignment;
    }

    template<size_t alignment>
    static uptr RoundUp(uptr addr)
    {
        return RoundDown<alignment>(addr + alignment - 1);
    }

public:
    static const size_t ALIGN = 8;

    /*!
        @brief 総ページ数を取得します。
    */
    static size_t GetNumMaxPages(void)
    {
        return 1 << (MAX_ORDER - 1);
    }

    /*!
        @brief 総データサイズをバイト単位で取得します。
    */
    static size_t GetMaxSize(void)
    {
        return GetNumMaxPages() * PAGE_SIZE;
    }

    /*!
        @brief バディヒープを初期化します。

        @param[in] addr ヒープの開始アドレス
        @param[in] numPages ページ数
    */
    void Initialize(uptr addr, size_t numPages)
    {
        NN_ASSERT((addr % ALIGN) == 0);

        m_HeapStart = addr;
        m_HeapSize  = PAGE_SIZE * numPages;

        NN_LOG_DEBUG("start %p\n", m_HeapStart);
        NN_LOG_DEBUG("size  %p\n", m_HeapSize);

        const size_t numMaxPages    = GetNumMaxPages();
        NN_LOG_DEBUG("numMaxPages %d\n", numMaxPages);
        const size_t maxSize        = GetMaxSize();
        NN_LOG_DEBUG("maxSize %d\n", maxSize);
        const size_t numMaxOrders   = m_HeapSize / maxSize;
        NN_LOG_DEBUG("numMaxOrders %d\n", numMaxOrders);

        NN_ASSERT(numMaxOrders > 0);

        // 管理領域の仮初期化
        // ページごとに1つ管理領域を割り当てします。
        m_pPages = reinterpret_cast<Page*>(m_HeapStart);

        for (size_t i = 0; i < numPages; i++)
        {
            m_pPages[i].pNext  = NULL;
        }

        for (size_t i = 0; i < MAX_ORDER; ++i )
        {
            m_FreeArea[i].Initialize();
        }
        for (size_t i = 0; i < numMaxOrders; i++)
        {
            // 各ページの開始アドレスをフリーリストに登録します。
            m_FreeArea[MAX_ORDER - 1].PushBack(&(m_pPages[i * numMaxPages]));
        }

        // 管理領域を再配置（普通は同じところに配置されるはず）
        const size_t manageAreaSize = sizeof(Page) * numPages;

        if(m_pPages != reinterpret_cast<Page*>(AllocateByOrder(GetNearestHigherOrder(DivUp<PAGE_SIZE>(manageAreaSize)))))
        {
            NN_LOG_WARN("failed to allocate page managing area.");
        }
    }

    /*!
        @brief バディヒープを破棄します。
    */
    void Finalize(void){}

    /*!
        @brief オーダーを指定してメモリを確保します。

        @param[in] order サイズ(2のべき乗)

        @return 確保したメモリへのポインタ
    */
    void* AllocateByOrder(s32 order)
    {
        NN_ASSERT(order >= 0);

        NN_LOG_DEBUG("demands order %d\n", order);


        Page* pPage = GetFreePage(order);
        NN_LOG_DEBUG("pPage = %08x\n", pPage);

        if(pPage)
        {
            uptr addr = GetAddressFromPage(*pPage);

            NN_LOG_DEBUG("returns order %d, address 0x%08X\n", order, addr);

            return reinterpret_cast<void*>(addr);
        }
        else
        {
            return NULL;
        }
    }

    /*!
        @brief メモリを解放します。

               (Free の引数が違うので HeapBase 準拠は無理)

        @param[in] p 解放するメモリへのポインタ
        @param[in] order オーダー
    */
    void Free(void* p, s32 order)
    {
        if(!p)
        {
            return;
        }

        NN_ASSERT((reinterpret_cast<uptr>(p) - m_HeapStart) % PAGE_SIZE == 0);

        Page* pPage = GetPageFromAddress(reinterpret_cast<uptr>(p));

        // ページのインデックスがオーダーで割り切れるか。
        NN_ASSERT(GetIndexFromPage(*pPage) % (1 << order) == 0);

        NN_LOG_DEBUG("addr = 0x%08x, order = %d, pPage = 0x%08x\n", p, order, pPage);

        JointBuddies(pPage, order);
    }

    virtual void FreeV(void*) { NN_ASSERT(false); }

    /*!
        @brief このヒープが利用しているメモリ領域の先頭アドレスを返します。
    */
    virtual void* GetStartAddress() const { return reinterpret_cast<void*>(m_HeapStart); }

    /*!
        @brief このヒープが利用しているメモリ領域のサイズを返します。
    */
    virtual size_t GetTotalSize() const { return m_HeapSize; }

    /*!
        @brief デバッグ用にヒープの内容をダンプします。
    */
    virtual void Dump() const{};

    /*!
        @brief 指定したアドレスがヒープ領域に含まれているかどうかを判定します。
    */
    virtual bool HasAddress(const void* addr) const
    {
        return m_HeapStart <= reinterpret_cast<uptr>(addr)
           && reinterpret_cast<uptr>(addr) < m_HeapStart + m_HeapSize;
    }

    /*!
        @brief バイト単位のサイズからオーダー数を計算します。

        @param[in] size サイズ(バイト単位)

        @return オーダー数
    */
    static s32 GetOrder(size_t size)
    {
        return GetNearestHigherOrder(DivUp<PAGE_SIZE>(size));
    }

    static const size_t PAGE_SIZE = PageSize;
    static const s32    MAX_ORDER = MaxOrder;

private:
    // ページエントリーです。
    struct Page
    {
        Page* pNext;
    };

    // 同一サイズのメモリブロック毎にリンクリストを構成します。
    class PageList
    {
    private:
        Page* m_pFirstPage;    // ページリストの先頭要素
        Page* m_pLastPage;     // ページリストの最後尾要素

    public:
        // ページリストを初期化します。
        void Initialize()
        {
            m_pFirstPage = NULL;
            m_pLastPage = NULL;
        }

        /*
            @brief ページリストの先頭から1ページ取得します。

            @return ページリストの先頭要素。リストに何も登録されていなかったら NULL を返します。
        */
        Page* PopFront()
        {
            NN_ASSERT(m_pFirstPage);

            // ページリストの最初の1ページ分を取得します。
            Page* pPage = m_pFirstPage;

            // ページリストをひとつ進めます。
            m_pFirstPage = pPage->pNext;
            pPage->pNext = NULL;

            // もしページリストの先頭と末端が一緒の場合は
            // ページリストの末尾に到達しています。
            // (ページリストの要素が空になりました)
            if(pPage == m_pLastPage)
            {
                m_pLastPage = NULL;
            }

            return pPage;
        }

        /*
            @brief ページリストの最後尾に 1 ページ追加します。

            @param[in]  pPage   追加対象のページ
        */
        void PushBack(Page* pPage)
        {
            NN_ASSERT(!pPage->pNext);

            // ページリストは空か?
            if(!m_pFirstPage)
            {
                // 先頭要素として追加します。
                m_pFirstPage = pPage;
            }
            else
            {
                // リストの末尾に追加します。
                m_pLastPage->pNext = pPage;
            }

            m_pLastPage = pPage;
        }

        /*
            @brief ページリストから 1 ページ削除します。

            @param[in] pPage 削除対象のページ

            @return 正常に削除できたら true、ページが存在しない場合は false
        */
        bool Remove(Page* pPage)
        {
            NN_NULL_TASSERT_(pPage);

            // ページリストは空か?
            if(m_pFirstPage == NULL)
            {
                return false;
            }

            Page* pPrevPage = NULL;
            Page* page = m_pFirstPage;

            for(;;)
            {
                if(page == pPage)
                {
                    // 削除対象のページが見つかった場合
                    if(page == m_pFirstPage)
                    {
                        // 削除対象のページがページリストの先頭だったため
                        // リストをひとつ進めつつ要素を削除します。
                        m_pFirstPage = page->pNext;
                    }
                    else if(page == m_pLastPage)
                    {
                        // 削除対象のページがページリストの末尾だったため
                        // 末尾の要素をひとつ戻します。
                        m_pLastPage = pPrevPage;
                        m_pLastPage->pNext = NULL;
                    }
                    else
                    {
                        // 先頭～末尾の間にあるページのため
                        // リンクリストをつなげなおします。
                        pPrevPage->pNext = page->pNext;
                    }

                    page->pNext = NULL;

                    return true;
                }

                if(page->pNext == NULL)
                {
                    return false;
                }

                pPrevPage = page;
                page = page->pNext;
            }

            // not reached
        }

        /*
            @brief ページリストは空か?

            @return ページリストに何も登録されていなければ true
        */
        bool IsEmpty() const
        {
            if(m_pFirstPage)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
    };

    PageList m_FreeArea[MAX_ORDER];

    uptr    m_HeapStart;
    size_t  m_HeapSize;

    /*
        :private

        @brief Order(2^order)に対応したサイズのフリーページを取得します。

        @param[in] order オーダー(2のべき乗)

        @return 割り当てられたページエントリー
    */
    Page* GetFreePage(s32 order)
    {
        for(s32 i = order; i < MAX_ORDER; i++)
        {
            // 2の order 乗(べき乗)に対応したページのリストを探索します。
            // もしそのページに空きページが登録さていない場合は、ひとつ上の order+1 乗の
            // ページを探索します。
            if(!(m_FreeArea[i].IsEmpty()))
            {
                // 空きメモリを見つけました。
                Page* pPage = m_FreeArea[i].PopFront();

                NN_NULL_TASSERT_(pPage);

                // 要求に対して大きすぎるメモリを割り当てする場合
                // 使用しない部分を分割し、空きページリストへ登録しなおします
                DivideBuddies(pPage, order, i);

                return pPage;
            }
        }

        NN_LOG_WARN("No free pages order %d\n", order);
        return NULL;
    }

    /*
        @brief 大きなページから必要な分だけを切り出します。

        @param[in] pPage 分割対象のページ
        @param[in] demandedOrder 割り当てを必要としているorder(2のべき乗)
        @param[in] freeOrder 分割対象のページのOrder(2のべき乗)
    */
    void DivideBuddies(Page* pPage, s32 demandedOrder, s32 freeOrder)
    {
        for(s32 i = freeOrder; demandedOrder < i; i--)
        {
            Page* pDividedPage = &pPage[(1 << (i - 1))];;

            // 細切れにして空きページリストへ登録します。
            // 4KB の要求に対して 16KB の大きな空きページが見つかった場合、差し引きして割り当てを必要としない
            // 12KB(16KB-4KB) を 4KB, 8KB の二つのページリストに分け、フリーリストへ追加します。

            NN_LOG_DEBUG("divides buddy address 0x%08X and 0x%08X, order%d\n", GetAddressFromPage(*pPage), GetAddressFromPage(*pDividedPage), i);
            m_FreeArea[i - 1].PushBack(pDividedPage);
        }
    }

    /*
        :private

        @brief 空きページリストへ登録します。あわせてメモリの連結処理を行います。

        @param[in] pPage 追加対象のページ
        @param[in] order ページのサイズ
    */
    void JointBuddies(Page* pPage, s32 order)
    {
        // 最上位のオーダーの 1つ前まで
        while(order < MAX_ORDER - 1)
        {
            // バディ(相方)となるページを求めます。
            Page* pBuddyPage = GetBuddy(pPage, order);

            // フリーリストにバディがいるか
            if(m_FreeArea[order].Remove(pBuddyPage))
            {
                // いたら、フリーリストから削除して（＝ジョイントした）１つ上のオーダーでジョイントを試みる。

                // ページが１つ上のオーダーでアラインしていなかったら、アドレスを Buddy に。
                if(!IsAlignedToOrder(pPage, order + 1))
                {
                    pPage = pBuddyPage;
                }

                NN_LOG_DEBUG("joints buddy address 0x%08X and 0x%08X, order %d", GetAddressFromPage(*pPage), GetAddressFromPage(*GetBuddy(pPage, order)), order);


                order++;
            }
            else
            {
                // いなかったら、ジョイントできなかったので、ページをフリーリストに追加する。
                break;
            }
        }

        // Buddy が利用中だったか、最上位オーダーまでジョイントした
        NN_LOG_DEBUG("adding a free page, address 0x%08X, order %d", GetAddressFromPage(*pPage), order );
        m_FreeArea[order].PushBack(pPage);
    }

    /*!
        @brief ページが示すアドレスを取得します。

        @param[in] page ページエントリー

        @return アドレス
    */
    inline uptr GetAddressFromPage(const Page& page) const
    {
        return m_HeapStart + GetIndexFromPage(page) * PAGE_SIZE;
    }

    /*!
        @brief 指定したアドレスを含むページエントリーを取得します。

        @param[in] addr アドレス

        @return ページエントリー
    */
    inline Page* GetPageFromAddress(uptr addr)
    {
        // TODO: 範囲チェック
        return &m_pPages[(addr - m_HeapStart) / PAGE_SIZE];
    }

    /*
        @brief 指定したページエントリーが先頭から何番目のページかを取得します。

        @param[in] page ページエントリー

        @return 先頭から何番目か
    */
    inline s32 GetIndexFromPage(const Page& page) const
    {
        return &page - m_pPages;
    }

    inline Page* GetBuddy(Page* pPage, s32 order)
    {
        // ページのインデックスが上のオーダーで割り切れるなら、右隣が Buddy
        if(IsAlignedToOrder(pPage, order + 1))
        {
            return pPage + GetNumPagesByOrder(order);
        }
        else // でなければ、左隣が Buddy
        {
            return pPage - GetNumPagesByOrder(order);
        }
    }

    /*
        @brief ページエントリーはorderの境界か?

        @param[in] pPage 探索対象のページエントリー
        @param[in] order ページの order (2のべき乗)

        @return ページエントリーが境界にある場合は true
    */
    inline bool IsAlignedToOrder(Page* pPage, s32 order) const
    {
        return GetIndexFromPage(*pPage) % GetNumPagesByOrder(order) == 0;
    }

    /*
        @brief Orderからページ数をもとめます

        @param[in] order ページの order (2のべき乗)

        @return ページ数
    */
    inline int GetNumPagesByOrder(s32 order) const
    {
        return (1 << order);
    }

    static s32 GetNearestHigherOrder(size_t numPages)
    {
        for(int order = 0; order <= MAX_ORDER; order++)
        {
            if( numPages <= (1U << order) ) {
                return order;
            }
        }

        NN_LOG_WARN("No nearest higher order: numPages=%d, MAX_ORDER=%d", numPages, MAX_ORDER);
        return -1;
    }

    static s32 GetNearestLowerOrder(size_t numPages)
    {
        for(int order = 0; order <= MAX_ORDER; order++)
        {
            if( numPages < (1 << order) ) {
                return order - 1;
            }
        }

        NN_LOG_WARN("No nearest lower order: numPages=%d, MAX_ORDER=%d", numPages, MAX_ORDER);
        return -1;
    }

    Page* m_pPages;
};

template <size_t PageSize, s32 MaxOrder, class LockPolicy>
class BuddyHeapTemplate : public BuddyHeapBase<PageSize, MaxOrder>, private LockPolicy::LockObject
{
private:
    typedef BuddyHeapBase<PageSize, MaxOrder> Base;
    typedef typename LockPolicy::LockObject LockObject;
    typedef typename LockPolicy::ScopedLock ScopedLock;

public:
    BuddyHeapTemplate() {}

    template <class MemoryBlockT>
    explicit BuddyHeapTemplate(const MemoryBlockT& block)
    {
        Initialize(block.GetAddress(), block.GetSize());
    }

    /*
        @brief バディヒープを初期化します。

        @param[in] addr ヒープに割り当てる領域のアドレス
        @param[in] size ヒープに割り当てる領域のサイズ
    */
    void Initialize(uptr addr, size_t size)
    {
        uptr addrAligned = Base::RoundUp<Base::ALIGN>(addr);
        size -= addrAligned - addr;

        Base::Initialize(addrAligned, size / Base::PAGE_SIZE);
        LockObject::Initialize();
    }

    /*
        @brief バディヒープを破棄します。
    */
    void Finalize()
    {
        LockObject::Finalize();
        Base::Finalize();
    }

    /*!
        @brief バディヒープからメモリを確保します。

        @param[in] order サイズ(2のるい乗)

        @return 確保したメモリへのポインタ
    */
    void* AllocateByOrder(s32 order)
    {
        ScopedLock lk(*this);
        return Base::AllocateByOrder(order);
    }

    /*!
        @brief バディヒープから確保したメモリブロックを解放します。

        @param[in] p 解放するメモリブロックの先頭アドレスを指定します。
        @param[in] order サイズ(2のるい乗)
     */
    void Free(void* p, s32 order)
    {
        ScopedLock lk(*this);
        Base::Free(p, order);
    }

    class Allocator;
};

template <size_t PageSize, s32 MaxOrder, class LockPolicy>
class BuddyHeapTemplate<PageSize, MaxOrder, LockPolicy>::Allocator : public nn::fnd::IAllocator
{
private:
    typedef BuddyHeapTemplate<PageSize, MaxOrder, LockPolicy> BuddyHeap;
    static const size_t ALIGN = BuddyHeap::ALIGN;

public:
    Allocator(BuddyHeap& heap) : m_Heap(0) { Initialize(heap); }

    /*!
        @brief 初期化をしないコンストラクタです。
     */
    Allocator() : m_Heap(0) {}

    /*!
        @breif アロケータを初期化します。

        @param[in] heap バディヒープ
    */
    void Initialize(BuddyHeap& heap)
    {
        NN_TASSERT_(!this->m_Heap);
        this->m_Heap = &heap;
    }

    /*!
        @brief アロケータにセットされているヒープを返します。

        @return アロケータにセットされているヒープ
     */
    BuddyHeap* GetHeap() { return m_Heap; }

    /*!
        @brief アロケータにセットされている拡張ヒープを返します。

        @return アロケータにセットされている拡張ヒープ
     */
    const BuddyHeap* GetHeap() const { return m_Heap; }

    /*!
        @brief 指定したサイズとアラインメントでメモリ領域を確保します。

        @param[in] size 確保するメモリのサイズ
        @param[in] alignment 確保するメモリのアラインメント

        @return 確保したメモリ領域の先頭へのポインタ
    */
    virtual void* Allocate(size_t size, s32 alignment = nn::fnd::HeapBase::DEFAULT_ALIGNMENT)
    {
        NN_ASSERT(alignment <= ALIGN);
        if (alignment > ALIGN)
        {
            return NULL;
        }

        // 確保したメモリの先頭にオーダーを保存しておくために
        // 余分にメモリを確保します。
        s32 order = m_Heap->GetOrder(size + ALIGN);
        //NN_TLOG_("size: %d => order: %d\n", size, order);
        void* p = m_Heap->AllocateByOrder(order);
        if (!p)
        {
            return NULL;
        }
        NN_LOG_DEBUG("Alloc size %d, order %d\n", size + ALIGN, order);
        *reinterpret_cast<s32*>(p) = order;
        return reinterpret_cast<void*>(reinterpret_cast<uptr>(p) + ALIGN);
    }

    /*!
        @brief メモリ領域を解放します。

        @param[in] p 確保されているメモリ領域の先頭へのポインタ
    */
    virtual void Free(void* p)
    {
        p = reinterpret_cast<void*>(reinterpret_cast<uptr>(p) - ALIGN);
        s32 order = *reinterpret_cast<s32*>(p);
        m_Heap->Free(p, order);
    }

private:
    BuddyHeap* m_Heap;     //!< バディヒープ
};

}}

#endif /* NN_FND_FND_BUDDYHEAP_H_ */