nn/fnd/fnd_ToriaBuddyHeap.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: 2151 $
 *---------------------------------------------------------------------------*/

#ifndef NN_FND_FND_TORIABUDDYHEAP_H_
#define NN_FND_FND_TORIABUDDYHEAP_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 ToriaBuddyHeapBase : public nn::fnd::HeapBase
{
protected:
    template <s32 align, typename T>
    static inline T DivUp(T x)
    {
        return static_cast<T>( (x + (align - 1)) / align );
    }

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

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

public:
    static const size_t ALIGN = 4;
    static const size_t MIN_SIZE = 8;

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

    /*!
        @brief 総データサイズをバイト単位で取得します。
    */
    static inline 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)-1)) == 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 inline 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 を返します。
        */
        inline 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
        */
        inline bool IsEmpty() const
        {
            return m_pFirstPage ? false : 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 乗の
            // ページを探索します。
            PageList &freeArea = m_FreeArea[i];
            if(!(freeArea.IsEmpty()))
            {
                // 空きメモリを見つけました。
                Page* pPage = freeArea.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) - 1)) == 0;
    }

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

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

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

    inline size_t GetBytesByOrder(s32 order) const
    {
        return (1 << order);
    }

    static inline 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 inline 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 ToriaBuddyHeapTemplate : public ToriaBuddyHeapBase<PageSize, MaxOrder>, private LockPolicy::LockObject
{
private:
    typedef ToriaBuddyHeapBase<PageSize, MaxOrder> Base;
    typedef typename LockPolicy::LockObject LockObject;
    typedef typename LockPolicy::ScopedLock ScopedLock;

public:
    ToriaBuddyHeapTemplate() {}

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

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

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

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

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

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

        @return 確保したメモリへのポインタ
    */
    inline 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 ToriaBuddyHeapTemplate<PageSize, MaxOrder, LockPolicy>::Allocator /*: public nn::fnd::IAllocator*/
{
private:
    typedef ToriaBuddyHeapTemplate<PageSize, MaxOrder, LockPolicy> BuddyHeap;

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 アロケータにセットされているヒープ
     */
    inline BuddyHeap* GetHeap() { return m_Heap; }

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

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

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

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

        @return 確保したメモリ領域の先頭へのポインタ
    */
    void* Allocate(s32 *pOutOrder, size_t size)
    {
        s32 order = m_Heap->GetOrder(size);
        void* p = m_Heap->AllocateByOrder(order);
        if (!p)
        {
            return false;
        }
        //NN_LOG_DEBUG("Alloc size %d, order %d\n", size, order);
        *pOutOrder = order;
        return reinterpret_cast<void*>(reinterpret_cast<uptr>(p));
    }

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

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

    inline size_t GetBytesByOrder(s32 order) const
    {
        return m_Heap->GetBytesByOrder(order);
    }


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

}}

#endif /* NN_FND_FND_TORIABUDDYHEAP_H_ */