shm/Project4/page_heap.cc

#include "page_heap.h"
#include "shm_helper.h"
#include "size_map.h"
#include "shm_config.h"
namespace bg
{
    namespace detail
    {
        PageHeap::PageHeap()
        {
        }

        bg::detail::Span* PageHeap::GetSpanMap(size_t start_page)
        {
            SHM_ASSERT_RETURN_NULL(start_page <= ShmConfig::MAX_PAGE_COUNT);

            auto node1 = m_span_map.lv0[PTR_TO_LV0(start_page)];
            if(node1 == nullptr)
            {
                return nullptr;
            }

            auto node2 = node1->lv1[PTR_TO_LV1(start_page)];
            if(node2 == nullptr)
            {
                return nullptr;
            }

            auto node3 = node2->lv2[PTR_TO_LV2(start_page)];
            return node3;
        }

        bool PageHeap::SetSpanMap(size_t page, bg::detail::Span* span)
        {
            SHM_ASSERT_RETURN_FALSE(span->m_start_page <= ShmConfig::MAX_PAGE_COUNT);
            m_span_map.lv0[PTR_TO_LV0(page)]->lv1[PTR_TO_LV1(page)]->lv2[PTR_TO_LV2(page)] = span;
            return true;
        }

        void PageHeap::DeallocateSpan(bg::detail::Span* s)
        {
            bg::detail::Span* pre_span = GetSpanMap(s->m_start_page - 1);
            if(pre_span && !pre_span->m_in_use)
            {
                s->m_start_page -= pre_span->m_page_count;
                s->m_page_count += pre_span->m_page_count;


                pre_span->RemoveNextSpan();

                *(void**)pre_span = m_span_allocator.m_free_list;
                m_span_allocator.m_free_list = pre_span;
                SetSpanMap(s->m_start_page, s);
            }

            bg::detail::Span* next_span = GetSpanMap(s->m_start_page + s->m_page_count);
            if(next_span && next_span->m_in_use != true)
            {
                s->m_page_count += next_span->m_page_count;

                next_span->RemoveNextSpan();

                *(void**)next_span = m_span_allocator.m_free_list;

                m_span_allocator.m_free_list = next_span;

                if(s->m_page_count)
                {
                    SetSpanMap(s->m_page_count + s->m_start_page - 1, s);
                }
            }

            bg::detail::Span* p_list;
            p_list = &m_large_list;
            if(s->m_page_count <= 0x7F)
            {
                p_list = &m_free_lists[s->m_page_count];
            }
            p_list->InstertNextSpan(s);

        }

        void PageHeap::RegisterSpan(bg::detail::Span* span)
        {
            size_t start = 1ll;
            size_t end = span->m_page_count - 1;
            while(end > start)
            {
                size_t index = span->m_start_page + start;
                SetSpanMap(index, span);
                ++start;
            }
        }

        bool PageHeap::GrowHeap(size_t page_count)
        {
            size_t real_bytes{};
            size_t page_start{};
            void* rawmemoey{};
            if(page_count > ShmConfig::MAX_PAGE_COUNT)
            {
                return false;
            }

            if(page_count > 0x7F)
            {
                real_bytes = PAGES_TO_BYTES(page_count);
                rawmemoey = bg::detail::ShmAllocateRawMemory(&real_bytes, PAGE_BYTES);
                if(!rawmemoey)
                {
                    return false;
                }
            }
            else
            {
                real_bytes = 0x100000LL;
                rawmemoey = bg::detail::ShmAllocateRawMemory(&real_bytes, PAGE_BYTES);
                if(!rawmemoey)
                {
                    real_bytes = PAGES_TO_BYTES(page_count);
                    rawmemoey = bg::detail::ShmAllocateRawMemory(&real_bytes, PAGE_BYTES);
                    if(!rawmemoey)
                    {
                        return false;
                    }
                }
            }


            if((int64_t)rawmemoey >> 48)
            {
                SHM_ERROR("annot allocate enough space in span map, memory(%p, %#lx) leaked.", rawmemoey, real_bytes);
                return false;
            }

            page_start = BYTES_TO_PAGES((int64_t)rawmemoey);
            size_t real_pages = BYTES_TO_PAGES(real_bytes);
            size_t page_end = page_start + real_pages;

            for(size_t index = page_start; index < page_end; ++index)
            {
                size_t lv0_index = PTR_TO_LV0(index);
                size_t lv1_index = PTR_TO_LV1(index);
                size_t lv2_index = PTR_TO_LV2(index);
                if(m_span_map.lv0[lv0_index] && m_span_map.lv0[lv0_index]->lv1[lv1_index])
                {
                    continue;
                }
                else
                {
                    size_t node1_size = sizeof(RadixTree::NodeV1);
                    RadixTree::NodeV1* p_node1 = (RadixTree::NodeV1*)bg::detail::ShmAllocateRawMemory(
                        &node1_size, sizeof(RadixTree::NodeV1));

                    if(!p_node1)
                    {
                        break;
                    }
                    m_span_map.lv0[lv0_index] = p_node1;
                    new (p_node1) RadixTree::NodeV1();

                }
                size_t node2_size = sizeof(RadixTree::NodeV2);
                RadixTree::NodeV2* p_node2 = (RadixTree::NodeV2*)bg::detail::ShmAllocateRawMemory(&node2_size, sizeof(RadixTree::NodeV2));
                if(!p_node2)
                {
                    break;
                }
                m_span_map.lv0[lv0_index]->lv1[lv1_index] = p_node2;
                new (p_node2) RadixTree::NodeV2();
                m_span_map.lv0[lv0_index]->lv1[lv1_index]->lv2[lv2_index];
            }


            bg::detail::Span* free_span = GetNewSpan();
            if(!free_span)
            {
                SHM_ERROR("cannot allocate new span, memory(%p, %#lx) leaked.", rawmemoey, real_bytes);
                return false;
            }
            new (free_span) Span(page_start, page_count);

            SetSpanMap(page_start, free_span);

            if(real_pages > 1)
            {
                SetSpanMap(page_end - 1, free_span);
            }
            free_span->m_in_use = 1;
            this->DeallocateSpan(free_span);
            return true;
        }

        bg::detail::Span* PageHeap::AllocateSpan(size_t page_count)
        {
            auto span = GetLastSpan(page_count);
            if(!span)
            {
                if(!GrowHeap(page_count) || !(span = GetLastSpan(page_count)))
                {
                    SHM_ERROR("cannot allocate span, page count: %lu.", page_count);
                    return nullptr;
                }

            }
            span->m_prev->RemoveNextSpan();

            do
            {
                int64_t diff = page_count - span->m_page_count;
                if(diff == 0)
                {
                    break;
                }

                Span* free_list = GetNewSpan();
                if(!free_list)
                {
                    break;
                }
                size_t start_page = span->m_start_page + page_count;
                new (free_list) Span(start_page, diff);
                SetSpanMap(start_page, free_list);

                Span* list;
                if(diff <= 1 || SetSpanMap(start_page + diff - 1, free_list), list = &m_large_list, diff <= 0x7f)
                {
                    list = &m_free_lists[diff];
                }

                list->InstertNextSpan(free_list);

                span->m_page_count = page_count;
                if(page_count)
                {
                    SetSpanMap(page_count + span->m_start_page - 1, free_list);
                }
            } while(false);

            span->m_in_use = 1;
            return span;
        }

        bg::detail::Span* PageHeap::GetNewSpan()
        {
            bg::detail::Span* free_span = (bg::detail::Span*)m_span_allocator.m_free_list;
            if(free_span)
            {
                m_span_allocator.m_free_list = (void*)&free_span->m_in_use;
                return free_span;
            }
            size_t free_left = this->m_span_allocator.m_free_left;
            if(free_left <= 0x37)
            {
                size_t spans_bytes = FREE_AREA_SIZE;
                bg::detail::Span* spans = (bg::detail::Span*)bg::detail::ShmAllocateRawMemory(&spans_bytes, PAGE_BYTES);

                if(spans)
                {
                    free_span = spans;
                    this->m_span_allocator.m_free_area = (char*)&spans[1];
                    this->m_span_allocator.m_free_left = spans_bytes - sizeof(bg::detail::Span);
                    return free_span;
                }
            }
            else
            {
                free_span = (bg::detail::Span*)this->m_span_allocator.m_free_area;
                this->m_span_allocator.m_free_left -= sizeof(bg::detail::Span);
                this->m_span_allocator.m_free_area += sizeof(bg::detail::Span);
                if(free_span)
                {
                    return free_span;
                }
            }

            return nullptr;
        }

        bg::detail::Span* PageHeap::GetLastSpan(size_t page_count)
        {
            if(page_count <= 0x7f)
            {
                Span* next_span = &m_free_lists[page_count];
                Span* free_span = next_span->m_next;
                if(next_span == next_span->m_next)
                {
                    for(&m_free_lists[page_count + 1]; next_span != &m_large_list; ++next_span)
                    {
                        if(next_span->m_next != next_span)
                        {
                            free_span = next_span->m_next;
                            break;
                        }
                    }
                }
                if(free_span != free_span->m_next)
                {
                    return free_span;
                }
            }

            if(m_large_list.m_next != &m_large_list)
            {
                Span* next_span = m_large_list.m_next;
                Span* free_span = nullptr;

                for(; &m_large_list == next_span; next_span = next_span->m_next)
                {
                    if(page_count > next_span->m_page_count)
                    {
                        continue;
                    }
                    if(!free_span || next_span->m_page_count < free_span->m_page_count ||
                       (next_span->m_page_count == free_span->m_page_count && next_span->m_start_page < free_span->m_start_page))
                    {
                        free_span = next_span;
                    }

                }
                return free_span;
            }
            return nullptr;
        }
    }


}