net/osl/osl_BuddyHeap.h

/*---------------------------------------------------------------------------*
  Project:  Horizon
  File:     osl_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: 15690 $
 *---------------------------------------------------------------------------*/

#ifndef NN_NET_OSL_BUDDYHEAP_H_
#define NN_NET_OSL_BUDDYHEAP_H_

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

namespace nn {
namespace net {
namespace osl {

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;

    static size_t GetNumMaxPages(void)
    {
        return 1 << (MAX_ORDER - 1);
    }

    static size_t GetMaxSize(void)
    {
        return GetNumMaxPages() * PAGE_SIZE;
    }

    void Initialize(uptr addr, size_t numPages)
    {
        NN_POINTER_ASSERT(addr);
        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);

        // 管理領域の仮初期化
        m_pPages = reinterpret_cast<Page*>(m_HeapStart);

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

        for( int i = 0; i < MAX_ORDER; ++i )
        {
            m_FreeArea[i].Initialize();
        }
        for(int 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.");
        }
    }
    void Finalize(void){}

    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;
        }
    }

    // Free の引数が違うので HeapBase 準拠は無理
    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{};
    virtual bool HasAddress(const void* addr) const
    {
        return m_HeapStart <= reinterpret_cast<uptr>(addr)
           && reinterpret_cast<uptr>(addr) < m_HeapStart + m_HeapSize;
    }

    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;
        }

        Page* PopFront()
        {
            NN_ASSERT(m_pFirstPage);

            Page* pPage = m_pFirstPage;

            m_pFirstPage = pPage->pNext;
            pPage->pNext = NULL;

            if(pPage == m_pLastPage)
            {
                m_pLastPage = NULL;
            }

            return pPage;
        }

        void PushBack(Page* pPage)
        {
            NN_ASSERT(!pPage->pNext);

            if(!m_pFirstPage)
            {
                m_pFirstPage = pPage;
            }
            else
            {
                m_pLastPage->pNext = pPage;
            }

            m_pLastPage = pPage;
        }

        bool Remove(Page* pPage)
        {
            if(!m_pFirstPage)
            {
                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;
            }
        }

        bool IsEmpty() const
        {
            if(m_pFirstPage)
            {
                return false;
            }
            else
            {
                return true;
            }
        }
    };

    PageList m_FreeArea[MAX_ORDER];

    uptr    m_HeapStart;
    size_t  m_HeapSize;

    Page* GetFreePage(s32 order)
    {
        for(int i = order; i < MAX_ORDER; i++)
        {
            if(!(m_FreeArea[i].IsEmpty()))
            {
                Page* pPage = m_FreeArea[i].PopFront();

                NN_ASSERT(pPage);

                DivideBuddies(pPage, order, i);

                return pPage;
            }
        }

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

    void  DivideBuddies(Page* pPage, s32 demandedOrder, s32 freeOrder)
    {
        for(int i = freeOrder; demandedOrder < i; i--)
        {
            Page* pDividedPage = &pPage[(1 << (i - 1))];;

            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);
        }
    }

    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);
    }

    inline uptr GetAddressFromPage(const Page& page) const
    {
        return m_HeapStart + GetIndexFromPage(page) * PAGE_SIZE;
    }

    inline Page* GetPageFromAddress(uptr addr)
    {
        return &m_pPages[(addr - m_HeapStart) / PAGE_SIZE];
    }

    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);
        }
    }

    inline bool IsAlignedToOrder(Page* pPage, s32 order) const
    {
        return GetIndexFromPage(*pPage) % GetNumPagesByOrder(order) == 0;
    }

    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 <= (1 << 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());
    }

    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();
    }
    void Initialize(const nn::os::MemoryBlockBase& block)
    {
        Initialize(block.GetAddress(), block.GetSize());
    }

    void Finalize()
    {
        LockObject::Finalize();
        Base::Finalize();
    }

    void* AllocateByOrder(s32 order)
    {
        ScopedLock lk(*this);
        return Base::AllocateByOrder(order);
    }

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

        @param[in] p    解放するメモリブロックの先頭アドレスを指定します。

        @return 無し。
     */
    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) {}

    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);
        void* p = m_Heap->Allocate(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_NET_OSL_BUDDYHEAP_H_ */