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