ChakraCore/lib/Common/Memory/HeapBlockMap.cpp

//-------------------------------------------------------------------------------------------------------
// Copyright (C) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.
//-------------------------------------------------------------------------------------------------------
#include "CommonMemoryPch.h"

// The VS2013 linker treats this as a redefinition of an already
// defined constant and complains. So skip the declaration if we're compiling
// with VS2013 or below.
#if !defined(_MSC_VER) || _MSC_VER >= 1900
const uint Memory::HeapBlockMap32::L1Count;
const uint Memory::HeapBlockMap32::L2Count;
#endif

#if defined(TARGET_64)
HeapBlockMap32::HeapBlockMap32(__in char * startAddress) :
    startAddress(startAddress),
#else
HeapBlockMap32::HeapBlockMap32() :
#endif
    count(0)
{
    memset(map, 0, sizeof(map));

#if defined(TARGET_64)
    Assert(((size_t)startAddress) % TotalSize == 0);
#endif
}

HeapBlockMap32::~HeapBlockMap32()
{
    for (uint i = 0; i < _countof(map); i++)
    {
        L2MapChunk * chunk = map[i];
        if (chunk)
        {
            NoMemProtectHeapDelete(chunk);
        }
    }
}

HeapBlock *
HeapBlockMap32::GetHeapBlock(void * address)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * l2map = map[id1];
    if (l2map == nullptr)
    {
        return nullptr;
    }

    return l2map->Get(address);
}

bool
HeapBlockMap32::EnsureHeapBlock(void * address, uint pageCount)
{
    uint id1 = GetLevel1Id(address);
    uint id2 = GetLevel2Id(address);

    uint currentPageCount = min(pageCount, L2Count - id2);

    while (true)
    {
        if (map[id1] == nullptr)
        {
            L2MapChunk * newChunk = NoMemProtectHeapNewNoThrowZ(L2MapChunk);
            if (newChunk == nullptr)
            {
                // Leave any previously allocated L2MapChunks in place --
                // the concurrent thread may have already accessed them.
                // These will be cleaned up in the Cleanup method, after Sweep is complete.
                return false;
            }

            map[id1] = newChunk;
            count++;
        }

        pageCount -= currentPageCount;
        if (pageCount == 0)
        {
            break;
        }

        id2 = 0;
        id1++;
        currentPageCount = min(pageCount, L2Count);
    }

    return true;
}

void
HeapBlockMap32::SetHeapBlockNoCheck(void * address, uint pageCount, HeapBlock * heapBlock, HeapBlock::HeapBlockType blockType, byte bucketIndex)
{
    uint id1 = GetLevel1Id(address);
    uint id2 = GetLevel2Id(address);

    uint currentPageCount = min(pageCount, L2Count - id2);

    while (true)
    {
        Assert(map[id1] != nullptr);

        map[id1]->Set(id2, currentPageCount, heapBlock, blockType, bucketIndex);

        pageCount -= currentPageCount;
        if (pageCount == 0)
        {
            return;
        }

        id2 = 0;
        id1++;
        currentPageCount = min(pageCount, Memory::HeapBlockMap32::L2Count);
    }
}

bool
HeapBlockMap32::SetHeapBlock(void * address, uint pageCount, HeapBlock * heapBlock, HeapBlock::HeapBlockType blockType, byte bucketIndex)
{
    // First, make sure we have all the necessary L2MapChunks we'll need.
    // This ensures that in case of failure, the concurrent thread won't see an inconsistent state.
    if (!EnsureHeapBlock(address, pageCount))
    {
        return false;
    }

    // Now, do the actual set, which cannot fail.
    SetHeapBlockNoCheck(address, pageCount, heapBlock, blockType, bucketIndex);
    return true;
}

void
HeapBlockMap32::ClearHeapBlock(void * address, uint pageCount)
{
    uint id1 = GetLevel1Id(address);
    uint id2 = GetLevel2Id(address);

    uint currentPageCount = min(pageCount, L2Count - id2);

    while (true)
    {
        Assert(map[id1] != nullptr);

        map[id1]->Clear(id2, currentPageCount);

        pageCount -= currentPageCount;
        if (pageCount == 0)
        {
            return;
        }

        id2 = 0;
        id1++;
        currentPageCount = min(pageCount, L2Count);
    }
}

HeapBlockMap32::PageMarkBitVector *
HeapBlockMap32::GetPageMarkBitVector(void * address)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * l2map = map[id1];
    if (l2map == nullptr)
    {
        return nullptr;
    }

    return l2map->GetPageMarkBitVector(address);
}

template <size_t BitCount>
BVStatic<BitCount>*
HeapBlockMap32::GetMarkBitVectorForPages(void * address)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * l2map = map[id1];
    if (l2map == nullptr)
    {
        return nullptr;
    }

    return l2map->GetMarkBitVectorForPages<BitCount>(address);
}

template BVStatic<SmallAllocationBlockAttributes::BitVectorCount>* HeapBlockMap32::GetMarkBitVectorForPages<SmallAllocationBlockAttributes::BitVectorCount>(void * address);
template BVStatic<MediumAllocationBlockAttributes::BitVectorCount>* HeapBlockMap32::GetMarkBitVectorForPages<MediumAllocationBlockAttributes::BitVectorCount>(void * address);

uint
HeapBlockMap32::GetMarkCount(void * address, uint pageCount)
{
    uint markCount = 0;

    ForEachChunkInAddressRange(address, pageCount, [&](L2MapChunk* l2Map, uint chunkId)
    {
        markCount += l2Map->GetPageMarkBitVector(chunkId /* pageIndex */)->Count();
    });

    return markCount;
}

template <class Fn>
void
HeapBlockMap32::ForEachChunkInAddressRange(void * address, size_t pageCount, Fn fn)
{
    uint id1 = GetLevel1Id(address);
    uint id2 = GetLevel2Id(address);

    while (true)
    {
        L2MapChunk * l2map = map[id1];
        Assert(l2map != nullptr);

        if (l2map != nullptr)
        {
            while (id2 < L2Count)
            {
                fn(l2map, id2);

                id2++;
                pageCount--;
                if (pageCount == 0)
                {
                    return;
                }
            }

            id2 = 0;
            id1++;
        }
    }
}

bool
HeapBlockMap32::IsMarked(void * address) const
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * chunk = map[id1];

    Assert(chunk != nullptr);
    return chunk->IsMarked(address);
}

void
HeapBlockMap32::SetMark(void * address)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * chunk = map[id1];
    Assert(chunk != nullptr);

    return chunk->SetMark(address);
}

bool
HeapBlockMap32::TestAndSetMark(void * address)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * chunk = map[id1];
    if (chunk == nullptr)
    {
        // False reference
        return false;
    }

    uint bitIndex = chunk->GetMarkBitIndex(address);
    return (chunk->markBits.TestAndSet(bitIndex) != 0);
}

void
HeapBlockMap32::ResetMarks()
{
    for (uint i = 0; i < L1Count; i++)
    {
        L2MapChunk * chunk = map[i];
        if (chunk == nullptr)
        {
            continue;
        }

        chunk->markBits.ClearAll();

#ifdef RECYCLER_VERIFY_MARK
        chunk->isNewChunk = false;
#endif

#if DBG
        for (uint j = 0; j < L2Count; j++)
        {
            chunk->pageMarkCount[j] = 0;
        }
#endif
    }
}

#if DBG
ushort
HeapBlockMap32::GetPageMarkCount(void * address) const
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * l2map = map[id1];
    Assert(l2map != nullptr);

    uint id2 = GetLevel2Id(address);

    return l2map->pageMarkCount[id2];
}

void
HeapBlockMap32::SetPageMarkCount(void * address, ushort markCount)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * l2map = map[id1];
    Assert(l2map != nullptr);

    uint id2 = GetLevel2Id(address);

    // Callers should already have updated the mark bits by the time they call this,
    // so check that the new count is correct for the current mark bits.
    // Not true right now, will be true...
#if ENABLE_ALLOCATIONS_DURING_CONCURRENT_SWEEP
    DebugOnly(HeapBlock * heapBlock = this->GetHeapBlock(address));
    Assert(l2map->GetPageMarkBitVector(id2)->Count() == markCount || heapBlock->WasAllocatedFromDuringSweep());
#else
    Assert(l2map->GetPageMarkBitVector(id2)->Count() == markCount);
#endif

    l2map->pageMarkCount[id2] = markCount;
}

template void HeapBlockMap32::VerifyMarkCountForPages<SmallAllocationBlockAttributes::BitVectorCount>(void* address, uint pageCount);
template void HeapBlockMap32::VerifyMarkCountForPages<MediumAllocationBlockAttributes::BitVectorCount>(void* address, uint pageCount);

template <uint BitVectorCount>
void
HeapBlockMap32::VerifyMarkCountForPages(void * address, uint pageCount)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * l2map = map[id1];
    Assert(l2map != nullptr);

    uint id2 = GetLevel2Id(address);

    Assert(id2 + pageCount <= L2Count);
    for (uint i = id2; i < pageCount + id2; i++)
    {
        uint markCountForPage = l2map->GetPageMarkBitVector(i)->Count();
#if ENABLE_ALLOCATIONS_DURING_CONCURRENT_SWEEP
        DebugOnly(HeapBlock * heapBlock = this->GetHeapBlock(address));
        Assert(markCountForPage == l2map->pageMarkCount[i] || heapBlock->WasAllocatedFromDuringSweep());
#else
        Assert(markCountForPage == l2map->pageMarkCount[i]);
#endif
    }
}
#endif

HeapBlockMap32::L2MapChunk::L2MapChunk()
{
    // We are zero-initialized so don't need to actually init.

    // Mark bits should be cleared by default
    Assert(markBits.Count() == 0);

#ifdef RECYCLER_VERIFY_MARK
    this->isNewChunk = true;
#endif

#if DBG
    for (uint i = 0; i < L2Count; i++)
    {
        Assert(pageMarkCount[i] == 0);
    }
#endif
}

HeapBlockMap32::L2MapChunk::~L2MapChunk()
{
    // In debug builds, we guarantee that the heap block is clear on shutdown.
    // In free builds, we skip this to save time.
    // So this assert is only true in debug builds.
    Assert(IsEmpty());
}

HeapBlock *
HeapBlockMap32::L2MapChunk::Get(void * address)
{
    uint id2 = GetLevel2Id(address);
    Assert(id2 < L2Count);
    __analysis_assume(id2 < L2Count);
    return map[id2];
}

void
HeapBlockMap32::L2MapChunk::Set(uint id2, uint pageCount, HeapBlock * heapBlock, HeapBlock::HeapBlockType blockType, byte bucketIndex)
{
    uint id2End = id2 + pageCount;

    Assert(id2 < L2Count);
    Assert(id2End <= L2Count);

    for (uint i = id2; i < id2End; i++)
    {
        __analysis_assume(i < L2Count);
        Assert(map[i] == nullptr);
        Assert(blockInfo[i].blockType == HeapBlock::HeapBlockType::FreeBlockType);

        // Set the blockType last, because we will test this first during marking.
        // If it's not FreeBlock, then we expect bucketIndex and heapBlock to be valid.
        map[i] = heapBlock;
        blockInfo[i].bucketIndex = bucketIndex;

        // We need memory barrier here for ARM to ensure that the blockType is set last.
#if defined(_M_ARM32_OR_ARM64)
        MemoryBarrier();
#endif
        blockInfo[i].blockType = blockType;
    }
}

void
HeapBlockMap32::L2MapChunk::Clear(uint id2, uint pageCount)
{
    uint id2End = id2 + pageCount;

    Assert(id2 < L2Count);
    Assert(id2End <= L2Count);

    for (uint i = id2; i < id2End; i++)
    {
        __analysis_assume(i < L2Count);
        Assert(map[i] != nullptr);
        Assert(blockInfo[i].blockType != HeapBlock::HeapBlockType::FreeBlockType);

        // This shouldn't be called when concurrent marking is happening, so order does not matter.
        // Regardless, set the blockType first just to be internally consistent.
        // We don't actually clear the bucketIndex because it doesn't matter if the blockType is FreeBlock.
        blockInfo[i].blockType = HeapBlock::HeapBlockType::FreeBlockType;
        map[i] = nullptr;
    }
}

bool
HeapBlockMap32::L2MapChunk::IsEmpty() const
{
    for (uint i = 0; i < L2Count; i++)
    {
        if (map[i] != nullptr)
        {
            return false;
        }
    }

    return true;
}

HeapBlockMap32::PageMarkBitVector *
HeapBlockMap32::L2MapChunk::GetPageMarkBitVector(void * address)
{
    uint id2 = GetLevel2Id(address);
    Assert(id2 < L2Count);
    __analysis_assume(id2 < L2Count);
    return GetPageMarkBitVector(id2);
}

HeapBlockMap32::PageMarkBitVector *
HeapBlockMap32::L2MapChunk::GetPageMarkBitVector(uint pageIndex)
{
    return markBits.GetRange<PageMarkBitCount>(pageIndex * PageMarkBitCount);
}

template <size_t BitCount>
BVStatic<BitCount> *
HeapBlockMap32::L2MapChunk::GetMarkBitVectorForPages(void * address)
{
    uint id2 = GetLevel2Id(address);
    Assert(id2 < L2Count);
    __analysis_assume(id2 < L2Count);
    return GetMarkBitVectorForPages<BitCount>(id2);
}

template <size_t BitCount>
BVStatic<BitCount> *
HeapBlockMap32::L2MapChunk::GetMarkBitVectorForPages(uint pageIndex)
{
    return markBits.GetRange<BitCount>(pageIndex * PageMarkBitCount);
}

bool
HeapBlockMap32::L2MapChunk::IsMarked(void * address) const
{
    return markBits.Test(GetMarkBitIndex(address)) == TRUE;
}

void
HeapBlockMap32::L2MapChunk::SetMark(void * address)
{
    markBits.Set(GetMarkBitIndex(address));
}

#ifdef RECYCLER_STRESS
void
HeapBlockMap32::InduceFalsePositives(Recycler * recycler)
{
    for (uint i = 0; i < L1Count; i++)
    {
        L2MapChunk * chunk = map[i];
        if (chunk == nullptr)
        {
            continue;
        }

        for (uint j = 0; j < L2Count; j++)
        {
            HeapBlock * block = chunk->map[j];

            if (block == nullptr)
            {
                // Unallocated block.  Try to mark the first offset, in case
                // we are simultaneously allocating this block on the main thread.
                recycler->TryMarkNonInterior((void *)GetAddressFromIds(i, j), nullptr);
            }
            else if (!block->IsLargeHeapBlock())
            {
                ((SmallHeapBlock *)block)->InduceFalsePositive(recycler);
            }
        }
    }
}
#endif

#ifdef RECYCLER_VERIFY_MARK
bool
HeapBlockMap32::IsAddressInNewChunk(void * address)
{
    uint id1 = GetLevel1Id(address);

    L2MapChunk * l2map = map[id1];
    Assert(l2map != nullptr);
    return l2map->isNewChunk;
}
#endif

template <class Fn>
void
HeapBlockMap32::ForEachSegment(Recycler * recycler, Fn func)
{
    Segment * currentSegment = nullptr;

    for (uint i = 0; i < L1Count; i++)
    {
        L2MapChunk * chunk = map[i];
        if (chunk == nullptr)
        {
            continue;
        }

        for (uint j = 0; j < L2Count; j++)
        {
            HeapBlock * block = chunk->map[j];
            if (block == nullptr)
            {
                continue;
            }

            Assert(block->GetSegment() != nullptr);
            if (block->GetSegment() == currentSegment)
            {
                Assert(currentSegment != nullptr);
                Assert(currentSegment->IsInSegment(block->GetAddress()));
                continue;
            }

            // New segment.
            Assert(currentSegment == nullptr || !currentSegment->IsInSegment(block->GetAddress()));
            currentSegment = block->GetSegment();
            AnalysisAssert(currentSegment != nullptr);
            char * segmentStart = currentSegment->GetAddress();
            size_t segmentLength = currentSegment->GetPageCount() * PageSize;

            PageAllocator* segmentPageAllocator = (PageAllocator*)currentSegment->GetAllocator();

            Assert(segmentPageAllocator == block->GetPageAllocator(block->GetHeapInfo()));
#if defined(TARGET_64)
            // On 64 bit, the segment may span multiple HeapBlockMap32 structures.
            // Limit the processing to the portion of the segment in this HeapBlockMap32.
            // We'll process other portions when we visit the other HeapBlockMap32 structures.
            if (segmentStart < this->startAddress)
            {
                Assert(segmentLength > (size_t)(this->startAddress - segmentStart));
                segmentLength -= (this->startAddress - segmentStart);
                segmentStart = this->startAddress;
            }

            if ((segmentStart - this->startAddress) + segmentLength > HeapBlockMap32::TotalSize)
            {
                segmentLength = HeapBlockMap32::TotalSize - (segmentStart - this->startAddress);
            }
#endif

            func(segmentStart, segmentLength, currentSegment, segmentPageAllocator);
        }
    }
}

#if ENABLE_CONCURRENT_GC
void
HeapBlockMap32::ResetDirtyPages(Recycler * recycler)
{
    this->ForEachSegment(recycler, [=](char * segmentStart, size_t segmentLength, Segment * segment, PageAllocator * segmentPageAllocator) {

        Assert(segmentLength % AutoSystemInfo::PageSize == 0);

#ifdef RECYCLER_WRITE_WATCH
        if (!CONFIG_FLAG(ForceSoftwareWriteBarrier))
        {
            if (segmentPageAllocator->IsWriteWatchEnabled())
            {
                // Call ResetWriteWatch for Small non-leaf and Large segments.
                UINT ret = ::ResetWriteWatch(segmentStart, segmentLength);
                Assert(ret == 0);
            }
        }
#endif

#ifdef RECYCLER_WRITE_BARRIER
#if defined(TARGET_64)
        if (segment->IsWriteBarrierEnabled())
#endif
        {
            // Reset software write barrier for barrier segments.
            RecyclerWriteBarrierManager::ResetWriteBarrier(segmentStart, segmentLength / AutoSystemInfo::PageSize);
        }
#endif
    });
}
#endif

bool
HeapBlockMap32::RescanPage(void * dirtyPage, bool* anyObjectsMarkedOnPage, Recycler * recycler)
{
    uint id1 = GetLevel1Id(dirtyPage);
    L2MapChunk * chunk = map[id1];
    if (chunk != nullptr)
    {
        uint id2 = GetLevel2Id(dirtyPage);
        HeapBlock::HeapBlockType blockType = chunk->blockInfo[id2].blockType;
        // Determine block type and process as appropriate
        switch (blockType)
        {
        case HeapBlock::HeapBlockType::FreeBlockType:
            // We had a false reference to a free block.  Do nothing.
            break;

        case HeapBlock::HeapBlockType::SmallNormalBlockType:
#ifdef RECYCLER_WRITE_BARRIER
        case HeapBlock::HeapBlockType::SmallNormalBlockWithBarrierType:
#endif
            return RescanHeapBlock<SmallNormalHeapBlock>(dirtyPage, blockType, chunk, id2, anyObjectsMarkedOnPage, recycler);
        case HeapBlock::HeapBlockType::SmallFinalizableBlockType:
#ifdef RECYCLER_WRITE_BARRIER
        case HeapBlock::HeapBlockType::SmallFinalizableBlockWithBarrierType:
#endif
            return RescanHeapBlock<SmallFinalizableHeapBlock>(dirtyPage, blockType, chunk, id2, anyObjectsMarkedOnPage, recycler);
#ifdef RECYCLER_VISITED_HOST
        case HeapBlock::HeapBlockType::SmallRecyclerVisitedHostBlockType:
            return RescanHeapBlock<SmallRecyclerVisitedHostHeapBlock>(dirtyPage, blockType, chunk, id2, anyObjectsMarkedOnPage, recycler);
#endif
        case HeapBlock::HeapBlockType::MediumNormalBlockType:
#ifdef RECYCLER_WRITE_BARRIER
        case HeapBlock::HeapBlockType::MediumNormalBlockWithBarrierType:
#endif
            return RescanHeapBlock<MediumNormalHeapBlock>(dirtyPage, blockType, chunk, id2, anyObjectsMarkedOnPage, recycler);
        case HeapBlock::HeapBlockType::MediumFinalizableBlockType:
#ifdef RECYCLER_WRITE_BARRIER
        case HeapBlock::HeapBlockType::MediumFinalizableBlockWithBarrierType:
#endif
            return RescanHeapBlock<MediumFinalizableHeapBlock>(dirtyPage, blockType, chunk, id2, anyObjectsMarkedOnPage, recycler);
#ifdef RECYCLER_VISITED_HOST
        case HeapBlock::HeapBlockType::MediumRecyclerVisitedHostBlockType:
            return RescanHeapBlock<MediumRecyclerVisitedHostHeapBlock>(dirtyPage, blockType, chunk, id2, anyObjectsMarkedOnPage, recycler);
#endif
        default:
            // Shouldn't be here -- leaf blocks aren't rescanned, and large blocks are handled separately
            Assert(false);
            break;
        }
    }

    return false;
}

template bool HeapBlockMap32::RescanHeapBlock<SmallNormalHeapBlock>(void * dirtyPage, HeapBlock::HeapBlockType blockType, L2MapChunk* chunk, uint id2, bool* anyObjectsMarkedOnPage, Recycler * recycler);
template bool HeapBlockMap32::RescanHeapBlock<SmallFinalizableHeapBlock>(void * dirtyPage, HeapBlock::HeapBlockType blockType, L2MapChunk* chunk, uint id2, bool* anyObjectsMarkedOnPage, Recycler * recycler);
template bool HeapBlockMap32::RescanHeapBlock<MediumNormalHeapBlock>(void * dirtyPage, HeapBlock::HeapBlockType blockType, L2MapChunk* chunk, uint id2, bool* anyObjectsMarkedOnPage, Recycler * recycler);
template bool HeapBlockMap32::RescanHeapBlock<MediumFinalizableHeapBlock>(void * dirtyPage, HeapBlock::HeapBlockType blockType, L2MapChunk* chunk, uint id2, bool* anyObjectsMarkedOnPage, Recycler * recycler);

template <class TBlockType>
bool
HeapBlockMap32::RescanHeapBlock(void * dirtyPage, HeapBlock::HeapBlockType blockType, L2MapChunk* chunk, uint id2, bool* anyObjectsMarkedOnPage, Recycler * recycler)
{
    Assert(chunk != nullptr);
    char* heapBlockPageAddress = TBlockType::GetBlockStartAddress((char*) dirtyPage);

    typedef typename TBlockType::HeapBlockAttributes TBlockAttributes;

    // We need to check the entire mark bit vector here. It's not sufficient to just check the page's
    // mark bit vector because the object that's dirty on the page could have started on an earlier page
    auto markBits = chunk->GetMarkBitVectorForPages<TBlockAttributes::BitVectorCount>(heapBlockPageAddress);
    if (!markBits->IsAllClear())
    {
        Assert(chunk->map[id2]->GetHeapBlockType() == blockType);

        // Small finalizable heap blocks require the HeapBlock * (to look up object attributes).
        // For others, this is null
        TBlockType* block = GetHeapBlockForRescan<TBlockType>(chunk, id2);
        uint bucketIndex = chunk->blockInfo[id2].bucketIndex;
        if (!SmallNormalHeapBucketBase<TBlockType>::RescanObjectsOnPage(block,
            (char *)dirtyPage, heapBlockPageAddress, markBits, HeapInfo::GetObjectSizeForBucketIndex<TBlockAttributes>(bucketIndex), bucketIndex, anyObjectsMarkedOnPage, recycler))
        {
            // Failed due to OOM
            ((TBlockType*) chunk->map[id2])->SetNeedOOMRescan(recycler);
            return false;
        }

        return true;
    }

    // Didn't actually rescan the block.
    return false;
}

template <typename TBlockType>
TBlockType*
HeapBlockMap32::GetHeapBlockForRescan(HeapBlockMap32::L2MapChunk* chunk, uint id2) const
{
    return nullptr;
}

template <>
SmallFinalizableHeapBlock*
HeapBlockMap32::GetHeapBlockForRescan(HeapBlockMap32::L2MapChunk* chunk, uint id2) const
{
    return (SmallFinalizableHeapBlock*) chunk->map[id2];
}

template <>
MediumFinalizableHeapBlock*
HeapBlockMap32::GetHeapBlockForRescan(HeapBlockMap32::L2MapChunk* chunk, uint id2) const
{
    return (MediumFinalizableHeapBlock*)chunk->map[id2];
}

#ifdef RECYCLER_VISITED_HOST
template <>
SmallRecyclerVisitedHostHeapBlock*
HeapBlockMap32::GetHeapBlockForRescan(HeapBlockMap32::L2MapChunk* chunk, uint id2) const
{
    return (SmallRecyclerVisitedHostHeapBlock*) chunk->map[id2];
}
#endif

#ifdef RECYCLER_VISITED_HOST
template <>
MediumRecyclerVisitedHostHeapBlock*
HeapBlockMap32::GetHeapBlockForRescan(HeapBlockMap32::L2MapChunk* chunk, uint id2) const
{
    return (MediumRecyclerVisitedHostHeapBlock*)chunk->map[id2];
}
#endif

void
HeapBlockMap32::MakeAllPagesReadOnly(Recycler* recycler)
{
    this->ChangeProtectionLevel(recycler, PAGE_READONLY, PAGE_READWRITE);
}

void
HeapBlockMap32::MakeAllPagesReadWrite(Recycler* recycler)
{
    this->ChangeProtectionLevel(recycler, PAGE_READWRITE, PAGE_READONLY);
}

void
HeapBlockMap32::ChangeProtectionLevel(Recycler* recycler, DWORD protectFlags, DWORD expectedOldFlags)
{
    this->ForEachSegment(recycler, [&](char* segmentStart, size_t segmentLength, Segment* currentSegment, PageAllocator* segmentPageAllocator)
    {
        // Ideally, we shouldn't to exclude LargeBlocks here but guest arenas are allocated
        // from this allocator and we touch them during marking if they're pending delete
        if (!recycler->autoHeap.IsRecyclerLeafPageAllocator(segmentPageAllocator)
            && !recycler->autoHeap.IsRecyclerLargeBlockPageAllocator(segmentPageAllocator))
        {
            Assert(currentSegment->IsPageSegment());
            ((PageSegment*)currentSegment)->ChangeSegmentProtection(protectFlags, expectedOldFlags);
        }
    });
}

#if ENABLE_CONCURRENT_GC
#ifdef RECYCLER_WRITE_WATCH
///
/// The GetWriteWatch API can fail under low-mem situations if called to retrieve write-watch for a large number of pages
/// (On Win10, > 255 pages). This helper is to handle the failure case. In the case of failure, we degrade to retrieving
/// the write-watch one page at a time since that's expected to succeed
///
UINT
HeapBlockMap32::GetWriteWatchHelper(Recycler * recycler, DWORD writeWatchFlags, void* baseAddress, size_t regionSize,
    void** addresses, ULONG_PTR* count, LPDWORD granularity)
{
    UINT ret = 0;

#ifdef ENABLE_DEBUG_CONFIG_OPTIONS
    if (recycler->GetRecyclerFlagsTable().ForceGetWriteWatchOOM)
    {
        if (regionSize != AutoSystemInfo::PageSize)
        {
            ret = (UINT) -1;
        }
    }
    else
#endif
    {
        ret = ::GetWriteWatch(writeWatchFlags, baseAddress, regionSize, addresses, count, granularity);
    }

    if (ret != 0 && regionSize != AutoSystemInfo::PageSize)
    {
       ret = GetWriteWatchHelperOnOOM(writeWatchFlags, baseAddress, regionSize, addresses, count, granularity);
    }

    Assert(ret == 0);

    return ret;
}

// OOM codepath- Retrieve write-watch one page at a time
// It's slow, but we are okay with that during OOM
// Factored into its own function to help the compiler inline the parent
UINT
HeapBlockMap32::GetWriteWatchHelperOnOOM(DWORD writeWatchFlags, _In_ void* baseAddress, size_t regionSize,
    _Out_writes_(*count) void** addresses, _Inout_ ULONG_PTR* count, LPDWORD granularity)
{
    const size_t pageCount = (regionSize / AutoSystemInfo::PageSize);

    // Ensure target buffer
    AnalysisAssertMsg(*count >= pageCount, "Not enough space in the buffer to store the write watch state for the given region size");

    void* result = nullptr;
    size_t dirtyCount = 0;

    for (size_t i = 0; i < pageCount; i++)
    {
        result = nullptr;
        char* pageAddress = ((char*)baseAddress) + (i * AutoSystemInfo::PageSize);
        ULONG_PTR resultBufferCount = 1;

        DWORD r = ::GetWriteWatch(writeWatchFlags, pageAddress, AutoSystemInfo::PageSize, &result, &resultBufferCount, granularity);
        Assert(r == 0);
        Assert(resultBufferCount <= 1);
        AnalysisAssert(dirtyCount < pageCount);

        // The requested page was dirty
        if (resultBufferCount == 1)
        {
            Assert(result == pageAddress);
#pragma prefast(suppress:22102)
            addresses[dirtyCount] = pageAddress;
            dirtyCount++;
        }
    }

    Assert(dirtyCount <= *count);
    *count = dirtyCount;
    return 0;
}
#endif
#endif

#if ENABLE_CONCURRENT_GC
uint
HeapBlockMap32::Rescan(Recycler * recycler, bool resetWriteWatch)
{
    // Loop through segments and find dirty pages.
    uint scannedPageCount = 0;
    bool anyObjectsScannedOnPage = false;

    this->ForEachSegment(recycler, [&](char * segmentStart, size_t segmentLength, Segment * currentSegment, PageAllocator * segmentPageAllocator)
    {
        Assert(segmentLength % AutoSystemInfo::PageSize == 0);

#ifdef RECYCLER_WRITE_WATCH
        if (!CONFIG_FLAG(ForceSoftwareWriteBarrier))
        {
            // Call GetWriteWatch for Small non-leaf segments.
            // Large blocks have their own separate write watch handling.
            if (recycler->autoHeap.IsRecyclerPageAllocator(segmentPageAllocator))
            {
                Assert(segmentLength <= MaxGetWriteWatchPages * PageSize);

                void * dirtyPageAddresses[MaxGetWriteWatchPages];
                ULONG_PTR pageCount = MaxGetWriteWatchPages;
                DWORD pageSize = PageSize;
                const DWORD writeWatchFlags = (resetWriteWatch ? WRITE_WATCH_FLAG_RESET : 0);

                UINT ret = HeapBlockMap32::GetWriteWatchHelper(recycler, writeWatchFlags, segmentStart, segmentLength, dirtyPageAddresses, &pageCount, &pageSize);
                Assert(ret == 0);
                Assert(pageSize == PageSize);
                Assert(pageCount <= MaxGetWriteWatchPages);

                // Process results:
                // Loop through reported dirty pages and set their write watch bit.
                for (uint i = 0; i < pageCount; i++)
                {
                    char * dirtyPage = (char *)dirtyPageAddresses[i];
                    Assert((((size_t)dirtyPage) % PageSize) == 0);
                    Assert(dirtyPage >= segmentStart);
                    Assert(dirtyPage < segmentStart + segmentLength);

#if defined(TARGET_64)
                    Assert(HeapBlockMap64::GetNodeStartAddress(dirtyPage) == this->startAddress);
#endif

                    if (RescanPage(dirtyPage, &anyObjectsScannedOnPage, recycler) && anyObjectsScannedOnPage)
                    {
                        scannedPageCount++;
                    }
                }
                return;
            }
        }
#endif

#ifdef RECYCLER_WRITE_BARRIER
        if (recycler->autoHeap.IsRecyclerWithBarrierPageAllocator(segmentPageAllocator))
        {
            // Loop through pages for this segment and check write barrier.
            size_t pageCount = segmentLength / AutoSystemInfo::PageSize;
            for (size_t i = 0; i < pageCount; i++)
            {
                char * pageAddress = segmentStart + (i * AutoSystemInfo::PageSize);
                Assert((size_t)(pageAddress - segmentStart) < segmentLength);

#if defined(TARGET_64)
                Assert(HeapBlockMap64::GetNodeStartAddress(pageAddress) == this->startAddress);
#endif

                // TODO: We are not resetting the write barrier here when RescanFlags_ResetWriteWatch is passed.
                // We never have previously, but it still seems like we should.

                BYTE writeBarrierByte = RecyclerWriteBarrierManager::GetWriteBarrier(pageAddress);
                SwbVerboseTrace(recycler->GetRecyclerFlagsTable(), _u("Address: 0x%p, Write Barrier value: %u\n"), pageAddress, writeBarrierByte);
                bool isDirty = (writeBarrierByte & DIRTYBIT);

                if (isDirty)
                {
                    if (RescanPage(pageAddress, &anyObjectsScannedOnPage, recycler) && anyObjectsScannedOnPage)
                    {
                        scannedPageCount++;
                    }
                }
            }
            return;
        }
#endif
        Assert(recycler->autoHeap.IsRecyclerLeafPageAllocator(segmentPageAllocator) ||
            recycler->autoHeap.IsRecyclerLargeBlockPageAllocator(segmentPageAllocator));
    });

    return scannedPageCount;
}
#endif

bool
HeapBlockMap32::OOMRescan(Recycler * recycler)
{
    this->anyHeapBlockRescannedDuringOOM = false;
    bool noHeapBlockNeedsRescan = true;

    // Loop through segments and find pages that need OOM Rescan.

    this->ForEachSegment(recycler, [=, &noHeapBlockNeedsRescan] (char * segmentStart, size_t segmentLength, Segment * currentSegment, PageAllocator * segmentPageAllocator) {
        Assert(segmentLength % AutoSystemInfo::PageSize == 0);

        // Process Small non-leaf segments (including write barrier blocks).
        // Large blocks have their own separate write watch handling.
        if (recycler->autoHeap.IsRecyclerPageAllocator(segmentPageAllocator)
#ifdef RECYCLER_WRITE_BARRIER
            || recycler->autoHeap.IsRecyclerWithBarrierPageAllocator(segmentPageAllocator)
#endif
            )
        {
            if (recycler->NeedOOMRescan())
            {
                // We hit OOM again.  Don't try to process any more blocks, leave them for the next OOM pass.
                return;
            }

            // Loop through pages for this segment and check OOM flag.
            size_t pageCount = segmentLength / AutoSystemInfo::PageSize;
            for (size_t i = 0; i < pageCount; i++)
            {
                char * pageAddress = segmentStart + (i * AutoSystemInfo::PageSize);
                Assert((size_t)(pageAddress - segmentStart) < segmentLength);

#if defined(TARGET_64)
                Assert(HeapBlockMap64::GetNodeStartAddress(pageAddress) == this->startAddress);
#endif

                uint id1 = GetLevel1Id(pageAddress);
                L2MapChunk * chunk = map[id1];
                if (chunk != nullptr)
                {
                    uint id2 = GetLevel2Id(pageAddress);
                    HeapBlock * heapBlock = chunk->map[id2];
                    if (heapBlock != nullptr && heapBlock->GetAddress() == pageAddress)
                    {
                        if (heapBlock->GetAndClearNeedOOMRescan())
                        {
                            noHeapBlockNeedsRescan = false;

                            HeapBlock::HeapBlockType blockType = chunk->blockInfo[id2].blockType;

                            // Determine block type and process as appropriate
                            switch (blockType)
                            {
                            case HeapBlock::HeapBlockType::FreeBlockType:
                                // Can't have a free block that has OOMRescan flag set
                                Assert(false);
                                break;

                            case HeapBlock::HeapBlockType::SmallNormalBlockType:
#ifdef RECYCLER_WRITE_BARRIER
                            case HeapBlock::HeapBlockType::SmallNormalBlockWithBarrierType:
#endif
                                if (!RescanHeapBlockOnOOM<SmallNormalHeapBlock>((SmallNormalHeapBlock*)heapBlock, pageAddress, blockType, chunk->blockInfo[id2].bucketIndex, chunk, recycler))
                                {
                                    return;
                                }
                                break;

                            case HeapBlock::HeapBlockType::SmallFinalizableBlockType:
#ifdef RECYCLER_WRITE_BARRIER
                            case HeapBlock::HeapBlockType::SmallFinalizableBlockWithBarrierType:
#endif
                                if (!RescanHeapBlockOnOOM<SmallFinalizableHeapBlock>((SmallFinalizableHeapBlock*) heapBlock, pageAddress, blockType, chunk->blockInfo[id2].bucketIndex, chunk, recycler))
                                {
                                    return;
                                }
                                break;
#ifdef RECYCLER_VISITED_HOST
                            case HeapBlock::HeapBlockType::SmallRecyclerVisitedHostBlockType:
                                if (!RescanHeapBlockOnOOM<SmallRecyclerVisitedHostHeapBlock>((SmallRecyclerVisitedHostHeapBlock*) heapBlock, pageAddress, blockType, chunk->blockInfo[id2].bucketIndex, chunk, recycler))
                                {
                                    return;
                                }
                                break;
#endif

                            case HeapBlock::HeapBlockType::MediumNormalBlockType:
#ifdef RECYCLER_WRITE_BARRIER
                            case HeapBlock::HeapBlockType::MediumNormalBlockWithBarrierType:
#endif
                                if (!RescanHeapBlockOnOOM<MediumNormalHeapBlock>((MediumNormalHeapBlock*)heapBlock, pageAddress, blockType, chunk->blockInfo[id2].bucketIndex, chunk, recycler))
                                {
                                    return;
                                }
                                break;

                            case HeapBlock::HeapBlockType::MediumFinalizableBlockType:
#ifdef RECYCLER_WRITE_BARRIER
                            case HeapBlock::HeapBlockType::MediumFinalizableBlockWithBarrierType:
#endif
                                if (!RescanHeapBlockOnOOM<MediumFinalizableHeapBlock>((MediumFinalizableHeapBlock*) heapBlock, pageAddress, blockType, chunk->blockInfo[id2].bucketIndex, chunk, recycler))
                                {
                                    return;
                                }
                                break;
#ifdef RECYCLER_VISITED_HOST
                            case HeapBlock::HeapBlockType::MediumRecyclerVisitedHostBlockType:
                                if (!RescanHeapBlockOnOOM<MediumRecyclerVisitedHostHeapBlock>((MediumRecyclerVisitedHostHeapBlock*) heapBlock, pageAddress, blockType, chunk->blockInfo[id2].bucketIndex, chunk, recycler))
                                {
                                    return;
                                }
                                break;
#endif

                            default:
                                // Shouldn't be here -- leaf blocks aren't rescanned, and large blocks are handled separately
                                Assert(false);
                                break;
                            }
                        }
                    }
                }
            }
        }
        else
        {
            Assert(recycler->autoHeap.IsRecyclerLeafPageAllocator(segmentPageAllocator) ||
                recycler->autoHeap.IsRecyclerLargeBlockPageAllocator(segmentPageAllocator));
        }
    });

    // TODO: Enable this assert post-Win10
    // Assert(this->anyHeapBlockRescannedDuringOOM);
    // Success if:
    //  No heap block needs OOM rescan OR
    //  A single heap block was rescanned
    return noHeapBlockNeedsRescan || this->anyHeapBlockRescannedDuringOOM;
}

template bool HeapBlockMap32::RescanHeapBlockOnOOM<SmallNormalHeapBlock>(SmallNormalHeapBlock* heapBlock, char* pageAddress, HeapBlock::HeapBlockType blockType, uint bucketIndex, L2MapChunk * chunk, Recycler * recycler);
template bool HeapBlockMap32::RescanHeapBlockOnOOM<SmallFinalizableHeapBlock>(SmallFinalizableHeapBlock* heapBlock, char* pageAddress, HeapBlock::HeapBlockType blockType, uint bucketIndex, L2MapChunk * chunk, Recycler * recycler);
template bool HeapBlockMap32::RescanHeapBlockOnOOM<MediumNormalHeapBlock>(MediumNormalHeapBlock* heapBlock, char* pageAddress, HeapBlock::HeapBlockType blockType, uint bucketIndex, L2MapChunk * chunk, Recycler * recycler);
template bool HeapBlockMap32::RescanHeapBlockOnOOM<MediumFinalizableHeapBlock>(MediumFinalizableHeapBlock* heapBlock, char* pageAddress, HeapBlock::HeapBlockType blockType, uint bucketIndex, L2MapChunk * chunk, Recycler * recycler);

template <class TBlockType>
bool
HeapBlockMap32::RescanHeapBlockOnOOM(TBlockType* heapBlock, char* pageAddress, HeapBlock::HeapBlockType blockType, uint bucketIndex, L2MapChunk * chunk, Recycler * recycler)
{
    // In the OOM codepath, we expect the heap block to be dereferenced since perf is not critical
    Assert(heapBlock != nullptr);
    Assert(heapBlock->GetHeapBlockType() == blockType);
    auto markBits = this->GetMarkBitVectorForPages<TBlockType::HeapBlockAttributes::BitVectorCount>(heapBlock->GetAddress());
    char* blockStartAddress = TBlockType::GetBlockStartAddress(pageAddress);

    // Rescan all pages in this block
    // The following assert makes sure that this method is called only once per heap block
    Assert(blockStartAddress == pageAddress);

    int inUsePageCount = heapBlock->GetPageCount() - heapBlock->GetUnusablePageCount();
    for (int i = 0; i < inUsePageCount; i++)
    {
        char* pageAddressToScan = blockStartAddress + (i * AutoSystemInfo::PageSize);

        if (!SmallNormalHeapBucketBase<TBlockType>::RescanObjectsOnPage(heapBlock,
            pageAddressToScan, blockStartAddress, markBits, HeapInfo::template GetObjectSizeForBucketIndex<typename TBlockType::HeapBlockAttributes>(bucketIndex), bucketIndex, nullptr, recycler))
        {
            // Failed due to OOM
            ((TBlockType*)heapBlock)->SetNeedOOMRescan(recycler);
        }

        if (recycler->NeedOOMRescan())
        {
            // We hit OOM again.  Don't try to process any more blocks, leave them for the next OOM pass.
            return false;
        }
    }

    this->anyHeapBlockRescannedDuringOOM = true;

    return true;
}

// This function is called in-thread after Sweep, to find empty L2 Maps and release them.

void
HeapBlockMap32::Cleanup(bool concurrentFindImplicitRoot)
{
    for (uint id1 = 0; id1 < L1Count; id1++)
    {
        L2MapChunk * l2map = map[id1];
        if (l2map != nullptr && l2map->IsEmpty())
        {
            // Concurrent searches for implicit roots will never see empty L2 maps.
            map[id1] = nullptr;
            NoMemProtectHeapDelete(l2map);
            Assert(count > 0);
            count--;
        }
    }
}

#if defined(TARGET_64)

HeapBlockMap64::HeapBlockMap64():
    list(nullptr)
{
}

HeapBlockMap64::~HeapBlockMap64()
{
    Node * node = list;
    list = nullptr;

    while (node != nullptr)
    {
        Node * next = node->next;
        NoMemProtectHeapDelete(node);
        node = next;
    }
}

bool
HeapBlockMap64::EnsureHeapBlock(void * address, size_t pageCount)
{
    uint lowerBitsAddress = ::Math::PointerCastToIntegralTruncate<uint>(address);
    size_t pageCountLeft = pageCount;
    uint nodePages = HeapBlockMap64::PagesPer4GB - lowerBitsAddress / AutoSystemInfo::PageSize;
    if (pageCountLeft < nodePages)
    {
        nodePages = (uint)pageCountLeft;
    }

    do
    {
        Node * node = FindOrInsertNode(address);
        if (node == nullptr || !node->map.EnsureHeapBlock(address, nodePages))
        {
            return false;
        }

        pageCountLeft -= nodePages;
        if (pageCountLeft == 0)
        {
            return true;
        }
        address = (void *)((size_t)address + ((size_t)nodePages * AutoSystemInfo::PageSize));
        nodePages = HeapBlockMap64::PagesPer4GB;
        if (pageCountLeft < HeapBlockMap64::PagesPer4GB)
        {
            nodePages = (uint)pageCountLeft;
        }
    }
    while (true);
}

void
HeapBlockMap64::SetHeapBlockNoCheck(void * address, size_t pageCount, HeapBlock * heapBlock, HeapBlock::HeapBlockType blockType, byte bucketIndex)
{
    ForEachNodeInAddressRange(address, pageCount, [&](Node * node, void * address, uint nodePages)
    {
        Assert(node != nullptr);
        node->map.SetHeapBlockNoCheck(address, nodePages, heapBlock, blockType, bucketIndex);
    });
}

bool
HeapBlockMap64::SetHeapBlock(void * address, size_t pageCount, HeapBlock * heapBlock, HeapBlock::HeapBlockType blockType, byte bucketIndex)
{
    if (!EnsureHeapBlock(address, pageCount))
    {
        return false;
    }

    SetHeapBlockNoCheck(address, pageCount, heapBlock, blockType, bucketIndex);

    return true;
}

void HeapBlockMap64::ClearHeapBlock(void * address, size_t pageCount)
{
    ForEachNodeInAddressRange(address, pageCount, [&](Node* node, void* address, uint nodePages)
    {
        Assert(node != nullptr);
        node->map.ClearHeapBlock(address, nodePages);
    });
}

template <class Fn>
void HeapBlockMap64::ForEachNodeInAddressRange(void * address, size_t pageCount, Fn fn)
{
    uint lowerBitsAddress = ::Math::PointerCastToIntegralTruncate<uint>(address);
    uint nodePages = HeapBlockMap64::PagesPer4GB - lowerBitsAddress / AutoSystemInfo::PageSize;

    if (pageCount < nodePages)
    {
        nodePages = (uint)pageCount;
    }

    // TODO: the loop is no longer needed as we are limiting the recycler object to be less than 2GB
    do
    {
        Node * node = FindNode(address);

        fn(node, address, nodePages);

        pageCount -= nodePages;
        if (pageCount == 0)
        {
            break;
        }
        address = (void *)((size_t)address + ((size_t)nodePages * AutoSystemInfo::PageSize));
        nodePages = HeapBlockMap64::PagesPer4GB;
        if (pageCount < HeapBlockMap64::PagesPer4GB)
        {
            nodePages = (uint)pageCount;
        }
    } while (true);
}

HeapBlock *
HeapBlockMap64::GetHeapBlock(void * address)
{
    Node * node = FindNode(address);
    if (node == nullptr)
    {
        return nullptr;
    }
    return node->map.GetHeapBlock(address);
}

HeapBlockMap32::PageMarkBitVector *
HeapBlockMap64::GetPageMarkBitVector(void * address)
{
    Node * node = FindNode(address);
    Assert(node != nullptr);
    return node->map.GetPageMarkBitVector(address);
}

template <size_t BitCount>
BVStatic<BitCount>* HeapBlockMap64::GetMarkBitVectorForPages(void * address)
{
    Node * node = FindNode(address);
    Assert(node != nullptr);
    return node->map.GetMarkBitVectorForPages<BitCount>(address);
}

template BVStatic<SmallAllocationBlockAttributes::BitVectorCount>* HeapBlockMap64::GetMarkBitVectorForPages<SmallAllocationBlockAttributes::BitVectorCount>(void * address);
template BVStatic<MediumAllocationBlockAttributes::BitVectorCount>* HeapBlockMap64::GetMarkBitVectorForPages<MediumAllocationBlockAttributes::BitVectorCount>(void * address);

uint
HeapBlockMap64::GetMarkCount(void * address, uint pageCount)
{
    uint markCount = 0;

    ForEachNodeInAddressRange(address, pageCount, [&](Node* node, void* address, uint nodePageCount)
    {
        Assert(node != nullptr);
        markCount += node->map.GetMarkCount(address, nodePageCount);
    });

    return markCount;
}

bool
HeapBlockMap64::IsMarked(void * address) const
{
    Node * node = FindNode(address);
    if (node != nullptr)
    {
        return node->map.IsMarked(address);
    }
    return false;
}

void
HeapBlockMap64::SetMark(void * address)
{
    Node * node = FindNode(address);
    if (node != nullptr)
    {
        node->map.SetMark(address);
    }
}

bool
HeapBlockMap64::TestAndSetMark(void * address)
{
    Node * node = FindNode(address);
    if (node == nullptr)
    {
        return false;
    }

    return node->map.TestAndSetMark(address);
}

HeapBlockMap64::Node *
HeapBlockMap64::FindOrInsertNode(void * address)
{
    Node * node = FindNode(address);

    if (node == nullptr)
    {
        node = NoMemProtectHeapNewNoThrowZ(Node, GetNodeStartAddress(address));
        if (node != nullptr)
        {
            node->nodeIndex = GetNodeIndex(address);
            node->next = list;
#ifdef _M_ARM64
            // For ARM we need to make sure that the list remains traversable during this insert.
            MemoryBarrier();
#endif
            list = node;
        }
    }

    return node;
}

HeapBlockMap64::Node *
HeapBlockMap64::FindNode(void * address) const
{
    uint index = GetNodeIndex(address);

    Node * node = list;
    while (node != nullptr)
    {
        if (node->nodeIndex == index)
        {
            return node;
        }

        node = node->next;
    }

    return nullptr;
}

void
HeapBlockMap64::ResetMarks()
{
    Node * node = this->list;
    while (node != nullptr)
    {
        node->map.ResetMarks();
        node = node->next;
    }
}

bool
HeapBlockMap64::OOMRescan(Recycler * recycler)
{
    Node * node = this->list;
    while (node != nullptr)
    {
        if (!node->map.OOMRescan(recycler))
        {
            return false;
        }

        node = node->next;
    }
    return true;
}

#if ENABLE_CONCURRENT_GC
void
HeapBlockMap64::ResetDirtyPages(Recycler * recycler)
{
    Node * node = this->list;
    while (node != nullptr)
    {
        node->map.ResetDirtyPages(recycler);
        node = node->next;
    }
}
#endif

void
HeapBlockMap64::MakeAllPagesReadOnly(Recycler* recycler)
{
    Node * node = this->list;
    while (node != nullptr)
    {
        node->map.MakeAllPagesReadOnly(recycler);
        node = node->next;
    }
}

void
HeapBlockMap64::MakeAllPagesReadWrite(Recycler* recycler)
{
    Node * node = this->list;
    while (node != nullptr)
    {
        node->map.MakeAllPagesReadWrite(recycler);
        node = node->next;
    }
}

#if ENABLE_CONCURRENT_GC
uint
HeapBlockMap64::Rescan(Recycler * recycler, bool resetWriteWatch)
{
    uint scannedPageCount = 0;

    Node * node = this->list;
    while (node != nullptr)
    {
        scannedPageCount += node->map.Rescan(recycler, resetWriteWatch);
        node = node->next;
    }

    return scannedPageCount;
}
#endif

void
HeapBlockMap64::Cleanup(bool concurrentFindImplicitRoot)
{
    Node ** prevnext = &this->list;
    Node * node = *prevnext;
    while (node != nullptr)
    {
        node->map.Cleanup(concurrentFindImplicitRoot);
        Node * nextNode = node->next;
        if (!concurrentFindImplicitRoot && node->map.Empty())
        {
            // Concurrent traversals of the node list would result in a race and possible UAF.
            // Currently we simply defer node free for the lifetime of the heap (only affects MemProtect).
            *prevnext = node->next;
            NoMemProtectHeapDelete(node);
        }
        else
        {
            prevnext = &node->next;
        }
        node = nextNode;
    }
}

#if DBG
ushort
HeapBlockMap64::GetPageMarkCount(void * address) const
{
    Node * node = FindNode(address);
    Assert(node != nullptr);

    return node->map.GetPageMarkCount(address);
}

void
HeapBlockMap64::SetPageMarkCount(void * address, ushort markCount)
{
    Node * node = FindNode(address);
    Assert(node != nullptr);

    node->map.SetPageMarkCount(address, markCount);
}

template void HeapBlockMap64::VerifyMarkCountForPages<SmallAllocationBlockAttributes::BitVectorCount>(void* address, uint pageCount);
template void HeapBlockMap64::VerifyMarkCountForPages<MediumAllocationBlockAttributes::BitVectorCount>(void* address, uint pageCount);

template <uint BitVectorCount>
void
HeapBlockMap64::VerifyMarkCountForPages(void * address, uint pageCount)
{
    Node * node = FindNode(address);
    Assert(node != nullptr);

    node->map.VerifyMarkCountForPages<BitVectorCount>(address, pageCount);
}

#endif

#ifdef RECYCLER_STRESS
void
HeapBlockMap64::InduceFalsePositives(Recycler * recycler)
{
    Node * node = this->list;
    while (node != nullptr)
    {
        node->map.InduceFalsePositives(recycler);
        node = node->next;
    }
}
#endif

#ifdef RECYCLER_VERIFY_MARK
bool
HeapBlockMap64::IsAddressInNewChunk(void * address)
{
    Node * node = FindNode(address);
    Assert(node != nullptr);

    return node->map.IsAddressInNewChunk(address);
}
#endif
#endif