path: root/src/zap/zapreadytorun.cpp

// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
//
// ZapReadyToRun.cpp
//

//
// Zapping of ready-to-run specific structures
// 
// ======================================================================================

#include "common.h"

#include "zapreadytorun.h"

#include "zapimport.h"

#include "nativeformatwriter.h"

#include "nibblestream.h"

#include "../vm/typehashingalgorithms.h"
#include "../vm/nativeformatreader.h"

using namespace NativeFormat;

void ZapReadyToRunHeader::Save(ZapWriter * pZapWriter)
{
    ZapImage * pImage = ZapImage::GetImage(pZapWriter);

    READYTORUN_HEADER readyToRunHeader;

    ZeroMemory(&readyToRunHeader, sizeof(readyToRunHeader));

    readyToRunHeader.Signature = READYTORUN_SIGNATURE;
    readyToRunHeader.MajorVersion = READYTORUN_MAJOR_VERSION;
    readyToRunHeader.MinorVersion = READYTORUN_MINOR_VERSION;

    if (pImage->m_ModuleDecoder.IsPlatformNeutral())
        readyToRunHeader.Flags |= READYTORUN_FLAG_PLATFORM_NEUTRAL_SOURCE;

    // If all types loaded succesfully, set a flag to skip type loading sanity checks at runtime
    if (pImage->GetCompileInfo()->AreAllClassesFullyLoaded(pImage->GetModuleHandle()))
        readyToRunHeader.Flags |= READYTORUN_FLAG_SKIP_TYPE_VALIDATION;

    if (pImage->GetZapperOptions()->m_fPartialNGen)
        readyToRunHeader.Flags |= READYTORUN_FLAG_PARTIAL;

    readyToRunHeader.NumberOfSections = m_Sections.GetCount();

    pZapWriter->Write(&readyToRunHeader, sizeof(readyToRunHeader));

    qsort(&m_Sections[0], m_Sections.GetCount(), sizeof(Section), SectionCmp);

    for(COUNT_T i = 0; i < m_Sections.GetCount(); i++)
    {
        READYTORUN_SECTION section;
        section.Type = m_Sections[i].type;
        ZapWriter::SetDirectoryData(&section.Section, m_Sections[i].pSection);
        pZapWriter->Write(&section, sizeof(section));
    }
}

class BlobVertex : public NativeFormat::Vertex
{
    int m_cbSize;

public:
    BlobVertex(int cbSize)
        : m_cbSize(cbSize)
    {
    }

    void * GetData()
    {
        return this + 1;
    }

    int GetSize()
    {
        return m_cbSize;
    }

    virtual void Save(NativeWriter * pWriter)
    {
        byte * pData = (byte *)GetData();
        for (int i = 0; i < m_cbSize; i++)
            pWriter->WriteByte(pData[i]);
    }
};

class BlobVertexKey
{
    PVOID   _pData;
    int     _cbSize;

public:
    BlobVertexKey(PVOID pData, int cbSize)
        : _pData(pData), _cbSize(cbSize)
    {
    }

    void * GetData()
    {
        return _pData;
    }

    int GetSize()
    {
        return _cbSize;
    }
};

class BlobVertexSHashTraits : public DefaultSHashTraits<BlobVertex *>
{
public:
    typedef BlobVertexKey key_t;

    static key_t GetKey(element_t e)
    {
        LIMITED_METHOD_CONTRACT;
        return key_t(e->GetData(), e->GetSize());
    }
    static BOOL Equals(key_t k1, key_t k2)
    {
        LIMITED_METHOD_CONTRACT;
        if (k1.GetSize() != k2.GetSize())
            return FALSE;
        return memcmp(k1.GetData(), k2.GetData(), k1.GetSize()) == 0;
    }
    static count_t Hash(key_t k)
    {
        LIMITED_METHOD_CONTRACT;
        count_t hash = 5381 + (count_t)(k.GetSize() << 7);

        PBYTE pbData = (PBYTE)k.GetData();
        PBYTE pbDataEnd = pbData + k.GetSize();

        for (/**/ ; pbData < pbDataEnd; pbData++)
        {
            hash = ((hash << 5) + hash) ^ *pbData;
        }
        return hash;
    }
};


class EntryPointVertex : public NativeFormat::Vertex
{
    DWORD m_methodIndex;
    BlobVertex * m_pFixups;

public:
    EntryPointVertex(DWORD methodIndex, BlobVertex * pFixups)
        : m_methodIndex(methodIndex), m_pFixups(pFixups)
    {
    }

    virtual void Save(NativeWriter * pWriter)
    {
        if (m_pFixups != NULL)
        {
            int existingOffset = pWriter->GetCurrentOffset(m_pFixups);
            if (existingOffset != -1)
            {
                pWriter->WriteUnsigned((m_methodIndex << 2) | 3);
                pWriter->WriteUnsigned(pWriter->GetCurrentOffset() - existingOffset);
            }
            else
            {
                pWriter->WriteUnsigned((m_methodIndex << 2) | 1);
                pWriter->SetCurrentOffset(m_pFixups);
                m_pFixups->Save(pWriter);
            }
        }
        else
        {
            pWriter->WriteUnsigned(m_methodIndex << 1);
        }
    }
};

class EntryPointWithBlobVertex : public EntryPointVertex
{
    BlobVertex * m_pBlob;

public:
    EntryPointWithBlobVertex(DWORD methodIndex, BlobVertex * pFixups, BlobVertex * pBlob)
        : EntryPointVertex(methodIndex, pFixups), m_pBlob(pBlob)
    {
    }

    virtual void Save(NativeWriter * pWriter)
    {
        m_pBlob->Save(pWriter);
        EntryPointVertex::Save(pWriter);
    }
};

void ZapImage::OutputEntrypointsTableForReadyToRun()
{
    BeginRegion(CORINFO_REGION_COLD);

    NativeWriter arrayWriter;
    NativeWriter hashtableWriter;

    NativeSection * pArraySection = arrayWriter.NewSection();
    NativeSection * pHashtableSection = hashtableWriter.NewSection();

    VertexArray vertexArray(pArraySection);
    pArraySection->Place(&vertexArray);
    VertexHashtable vertexHashtable;
    pHashtableSection->Place(&vertexHashtable);

    bool fEmpty = true;

    SHash< NoRemoveSHashTraits < BlobVertexSHashTraits > > fixupBlobs;

    COUNT_T nCount = m_MethodCompilationOrder.GetCount();
    for (COUNT_T i = 0; i < nCount; i++)
    {
        ZapMethodHeader * pMethod = m_MethodCompilationOrder[i];


        BlobVertex * pFixupBlob = NULL;

        if (pMethod->m_pFixupList != NULL)
        {
            NibbleWriter writer;
            m_pImportTable->PlaceFixups(pMethod->m_pFixupList, writer);

            DWORD cbBlob;
            PVOID pBlob = writer.GetBlob(&cbBlob);

            pFixupBlob = fixupBlobs.Lookup(BlobVertexKey(pBlob, cbBlob));
            if (pFixupBlob == NULL)
            {
                void * pMemory = new (GetHeap()) BYTE[sizeof(BlobVertex) + cbBlob];
                pFixupBlob = new (pMemory) BlobVertex(cbBlob);
                memcpy(pFixupBlob->GetData(), pBlob, cbBlob);

                fixupBlobs.Add(pFixupBlob);
            }
        }

        CORINFO_SIG_INFO sig;
        GetJitInfo()->getMethodSig(pMethod->GetHandle(), &sig);

        mdMethodDef token = GetJitInfo()->getMethodDefFromMethod(pMethod->GetHandle());
        int rid = RidFromToken(token);

        if (sig.sigInst.classInstCount > 0 || sig.sigInst.methInstCount > 0)
        {
            _ASSERTE(rid != 0);
            
            CORINFO_MODULE_HANDLE module = GetJitInfo()->getClassModule(pMethod->GetClassHandle());
            _ASSERTE(GetCompileInfo()->IsInCurrentVersionBubble(module));
            SigBuilder sigBuilder;
            CORINFO_RESOLVED_TOKEN resolvedToken = {};
            resolvedToken.tokenScope = module;
            resolvedToken.token = token;
            resolvedToken.hClass = pMethod->GetClassHandle();
            resolvedToken.hMethod = pMethod->GetHandle();
            GetCompileInfo()->EncodeMethod(module, pMethod->GetHandle(), &sigBuilder, m_pImportTable, EncodeModuleHelper, &resolvedToken);

            DWORD cbBlob;
            PVOID pBlob = sigBuilder.GetSignature(&cbBlob);
            void * pMemory = new (GetHeap()) BYTE[sizeof(BlobVertex) + cbBlob];
            BlobVertex * pSigBlob = new (pMemory) BlobVertex(cbBlob);
            memcpy(pSigBlob->GetData(), pBlob, cbBlob);

            int dwHash = GetCompileInfo()->GetVersionResilientMethodHashCode(pMethod->GetHandle());
            vertexHashtable.Append(dwHash, pHashtableSection->Place(new (GetHeap()) EntryPointWithBlobVertex(pMethod->GetMethodIndex(), pFixupBlob, pSigBlob)));
        }
        else
        {
            int rid = RidFromToken(token);
            if (rid != 0)
            {
                vertexArray.Set(rid - 1, new (GetHeap()) EntryPointVertex(pMethod->GetMethodIndex(), pFixupBlob));
            }
            else
            {
                // This is a p/invoke stub, get the list of methods associated with the stub, and put this code in that set of rids
                void *targetMethodEnum;
                BOOL isStubWithTargetMethods = GetCompileInfo()->EnumMethodsForStub(pMethod->GetHandle(), &targetMethodEnum);
                _ASSERTE(isStubWithTargetMethods);

                CORINFO_METHOD_HANDLE hTargetMethod;
                while (GetCompileInfo()->EnumNextMethodForStub(targetMethodEnum, &hTargetMethod))
                {
                    mdMethodDef token = GetJitInfo()->getMethodDefFromMethod(hTargetMethod);
                    int rid = RidFromToken(token);
                    _ASSERTE(rid != 0);
                    vertexArray.Set(rid - 1, new (GetHeap()) EntryPointVertex(pMethod->GetMethodIndex(), pFixupBlob));
                }

                GetCompileInfo()->EnumCloseForStubEnumerator(targetMethodEnum);
            }
        }

        fEmpty = false;
    }

    if (fEmpty)
        return;

    vertexArray.ExpandLayout();

    vector<byte>& arrayBlob = arrayWriter.Save();
    ZapNode * pArrayBlob = ZapBlob::NewBlob(this, &arrayBlob[0], arrayBlob.size());
    m_pCodeMethodDescsSection->Place(pArrayBlob);

    vector<byte>& hashtableBlob = hashtableWriter.Save();
    ZapNode * pHashtableBlob = ZapBlob::NewBlob(this, &hashtableBlob[0], hashtableBlob.size());
    m_pCodeMethodDescsSection->Place(pHashtableBlob);

    ZapReadyToRunHeader * pReadyToRunHeader = GetReadyToRunHeader();
    pReadyToRunHeader->RegisterSection(READYTORUN_SECTION_METHODDEF_ENTRYPOINTS, pArrayBlob);
    pReadyToRunHeader->RegisterSection(READYTORUN_SECTION_INSTANCE_METHOD_ENTRYPOINTS, pHashtableBlob);
    pReadyToRunHeader->RegisterSection(READYTORUN_SECTION_RUNTIME_FUNCTIONS, m_pRuntimeFunctionSection);

    if (m_pLazyMethodCallHelperSection->GetNodeCount() != 0)
        pReadyToRunHeader->RegisterSection(READYTORUN_SECTION_DELAYLOAD_METHODCALL_THUNKS, m_pLazyMethodCallHelperSection);

    if (m_pExceptionInfoLookupTable->GetSize() != 0)
        pReadyToRunHeader->RegisterSection(READYTORUN_SECTION_EXCEPTION_INFO, m_pExceptionInfoLookupTable);

    EndRegion(CORINFO_REGION_COLD);
}

class DebugInfoVertex : public NativeFormat::Vertex
{
    BlobVertex * m_pDebugInfo;

public:
    DebugInfoVertex(BlobVertex * pDebugInfo)
        : m_pDebugInfo(pDebugInfo)
    {
    }

    virtual void Save(NativeWriter * pWriter)
    {
        int existingOffset = pWriter->GetCurrentOffset(m_pDebugInfo);
        if (existingOffset != -1)
        {
            _ASSERTE(pWriter->GetCurrentOffset() > existingOffset);
            pWriter->WriteUnsigned(pWriter->GetCurrentOffset() - existingOffset);
        }
        else
        {
            pWriter->WriteUnsigned(0);
            pWriter->SetCurrentOffset(m_pDebugInfo);
            m_pDebugInfo->Save(pWriter);
        }
    }
};
// At ngen time Zapper::CompileModule PlaceFixups called from
//     code:ZapSig.GetSignatureForTypeHandle
//
/*static*/ DWORD ZapImage::EncodeModuleHelper(LPVOID compileContext,
    CORINFO_MODULE_HANDLE referencedModule)
{
    _ASSERTE(!IsReadyToRunCompilation() || IsLargeVersionBubbleEnabled());
    ZapImportTable * pTable = (ZapImportTable *)compileContext;
    return pTable->GetIndexOfModule(referencedModule);
}

void ZapImage::OutputDebugInfoForReadyToRun()
{
    NativeWriter writer;

    NativeSection * pSection = writer.NewSection();

    VertexArray vertexArray(pSection);
    pSection->Place(&vertexArray);

    bool fEmpty = true;

    SHash< NoRemoveSHashTraits < BlobVertexSHashTraits > > debugInfoBlobs;

    COUNT_T nCount = m_MethodCompilationOrder.GetCount();
    for (COUNT_T i = 0; i < nCount; i++)
    {
        ZapMethodHeader * pMethod = m_MethodCompilationOrder[i];

        ZapBlob * pDebugInfo = pMethod->GetDebugInfo();
        if (pDebugInfo == NULL)
            continue;

        DWORD cbBlob = pDebugInfo->GetBlobSize();
        PVOID pBlob = pDebugInfo->GetData();

        BlobVertex * pDebugInfoBlob = debugInfoBlobs.Lookup(BlobVertexKey(pBlob, cbBlob));
        if (pDebugInfoBlob == NULL)
        {
            void * pMemory = new (GetHeap()) BYTE[sizeof(BlobVertex) + cbBlob];
            pDebugInfoBlob = new (pMemory) BlobVertex(cbBlob);
            memcpy(pDebugInfoBlob->GetData(), pBlob, cbBlob);

            debugInfoBlobs.Add(pDebugInfoBlob);
        }

        vertexArray.Set(pMethod->GetMethodIndex(), new (GetHeap()) DebugInfoVertex(pDebugInfoBlob));

        fEmpty = false;
    }

    if (fEmpty)
        return;

    vertexArray.ExpandLayout();

    vector<byte>& blob = writer.Save();

    ZapNode * pBlob = ZapBlob::NewBlob(this, &blob[0], blob.size());
    m_pDebugSection->Place(pBlob);

    GetReadyToRunHeader()->RegisterSection(READYTORUN_SECTION_DEBUG_INFO, pBlob);
}

void ZapImage::OutputInliningTableForReadyToRun()
{
    SBuffer serializedInlineTrackingBuffer;
    m_pPreloader->GetSerializedInlineTrackingMap(&serializedInlineTrackingBuffer);
    ZapNode * pBlob = ZapBlob::NewAlignedBlob(this, (PVOID)(const BYTE*) serializedInlineTrackingBuffer, serializedInlineTrackingBuffer.GetSize(), 4);
    m_pDebugSection->Place(pBlob);
    GetReadyToRunHeader()->RegisterSection(READYTORUN_SECTION_INLINING_INFO, pBlob);
}

void ZapImage::OutputProfileDataForReadyToRun()
{
    if (m_pInstrumentSection != nullptr)
    {
        GetReadyToRunHeader()->RegisterSection(READYTORUN_SECTION_PROFILEDATA_INFO, m_pInstrumentSection);
    }
}

void ZapImage::OutputManifestMetadataForReadyToRun()
{
    if (m_pMetaDataSection != nullptr)
    {
        GetReadyToRunHeader()->RegisterSection(READYTORUN_SECTION_MANIFEST_METADATA, m_pMetaDataSection);
    }
}

void ZapImage::OutputTypesTableForReadyToRun(IMDInternalImport * pMDImport)
{
    NativeWriter writer;
    VertexHashtable typesHashtable;

    NativeSection * pSection = writer.NewSection();
    pSection->Place(&typesHashtable);

    // Note on duplicate types with same name: there is not need to perform that check when building
    // the hashtable. If such types were encountered, the R2R compilation would fail before reaching here.

    // Save the TypeDefs to the hashtable
    {
        HENUMInternalHolder hEnum(pMDImport);
        hEnum.EnumAllInit(mdtTypeDef);

        mdToken mdTypeToken;
        while (pMDImport->EnumNext(&hEnum, &mdTypeToken))
        {
            mdTypeDef mdCurrentToken = mdTypeToken;
            DWORD dwHash = GetCompileInfo()->GetVersionResilientTypeHashCode(GetModuleHandle(), mdTypeToken);

            typesHashtable.Append(dwHash, pSection->Place(new UnsignedConstant(RidFromToken(mdTypeToken) << 1)));
        }
    }

    // Save the ExportedTypes to the hashtable
    {
        HENUMInternalHolder hEnum(pMDImport);
        hEnum.EnumInit(mdtExportedType, mdTokenNil);

        mdToken mdTypeToken;
        while (pMDImport->EnumNext(&hEnum, &mdTypeToken))
        {
            DWORD dwHash = GetCompileInfo()->GetVersionResilientTypeHashCode(GetModuleHandle(), mdTypeToken);

            typesHashtable.Append(dwHash, pSection->Place(new UnsignedConstant((RidFromToken(mdTypeToken) << 1) | 1)));
        }
    }

    vector<byte>& blob = writer.Save();

    ZapNode * pBlob = ZapBlob::NewBlob(this, &blob[0], blob.size());
    _ASSERTE(m_pAvailableTypesSection);
    m_pAvailableTypesSection->Place(pBlob);

    GetReadyToRunHeader()->RegisterSection(READYTORUN_SECTION_AVAILABLE_TYPES, pBlob);
}

template<class Tlambda>
HRESULT EnumerateAllCustomAttributes(IMDInternalImport *pMDImport, Tlambda lambda)
{
    HENUMInternalHolder hEnum(pMDImport);
    hEnum.EnumAllInit(mdtCustomAttribute);

    HRESULT hr = S_OK;

    mdCustomAttribute tkCustomAttribute;
    while (pMDImport->EnumNext(&hEnum, &tkCustomAttribute))
    {
        LPCUTF8 szNamespace;
        LPCUTF8 szName;

        hr = pMDImport->GetNameOfCustomAttribute(tkCustomAttribute, &szNamespace, &szName);
        if (FAILED(hr))
            return hr;
        
        if (szNamespace == NULL)
            continue;

        if (szName == NULL)
            continue;

        // System.Runtime.CompilerServices.NullableAttribute is NEVER added to the table (There are *many* of these, and they provide no useful value to the runtime)
        if ((strcmp(szNamespace, "System.Runtime.CompilerServices") == 0) && (strcmp(szName, "NullableAttribute") == 0))
            continue;

        bool addToTable = false;
        // Other than Nullable attribute, all attributes under System.Runtime are added to the table
        if (strncmp(szNamespace, "System.Runtime.", strlen("System.Runtime.")) == 0)
        {
            addToTable = true;
        }
        else if (strcmp(szNamespace, "Windows.Foundation.Metadata") == 0)
        {
            // Windows.Foundation.Metadata attributes are a similar construct to compilerservices attributes. Add them to the table
            addToTable = true;
        }
        else if (strcmp(szNamespace, "System") == 0)
        {
            // Some historical well known attributes were placed in the System namespace. Special case them
            if (strcmp(szName, "ParamArrayAttribute") == 0)
                addToTable = true;
            else if (strcmp(szName, "ThreadStaticAttribute") == 0)
                addToTable = true;
        }
        else if (strcmp(szNamespace, "System.Reflection") == 0)
        {
            // Historical attribute in the System.Reflection namespace
            if (strcmp(szName, "DefaultMemberAttribute") == 0)
                addToTable = true;
        }

        if (!addToTable)
            continue;

        mdToken tkParent;
        hr = pMDImport->GetParentToken(tkCustomAttribute, &tkParent);
        if (FAILED(hr))
            return hr;
        
        hr = lambda(szNamespace, szName, tkParent);
        if (FAILED(hr))
            return hr;
    }

    return hr;
}

uint32_t xorshift128(uint32_t state[4])
{
    /* Algorithm "xor128" from p. 5 of Marsaglia, "Xorshift RNGs" */
    uint32_t s, t = state[3];
    state[3] = state[2];
    state[2] = state[1];
    state[1] = s = state[0];
    t ^= t << 11;
    t ^= t >> 8;
    return state[0] = t ^ s ^ (s >> 19);
}

HRESULT ZapImage::ComputeAttributePresenceTable(IMDInternalImport * pMDImport, SArray<UINT16> *table)
{
    int countOfEntries = 0;
    HRESULT hr = EnumerateAllCustomAttributes(pMDImport, [&countOfEntries](LPCUTF8 szNamespace, LPCUTF8 szName, mdToken tkParent)
        {
            countOfEntries++;
            return S_OK;
        });
    if (FAILED(hr))
        return hr;

    if (countOfEntries == 0)
    {
        table->Clear();
        _ASSERTE(table->IsEmpty());
        return S_OK;
    }

    // Buckets have 8 entries
    UINT minTableBucketCount = (countOfEntries / 8) + 1;
    UINT bucketCount = 1;

    // Bucket count must be power of two
    while (bucketCount < minTableBucketCount)
        bucketCount *= 2;

    // Resize the array.
    bool tryAgainWithBiggerTable = false;
    int countOfRetries = 0;
    do
    {
        tryAgainWithBiggerTable = false;
        UINT actualSizeOfTable = bucketCount * 8; // Buckets have 8 entries in them
        UINT16* pTable = table->OpenRawBuffer(actualSizeOfTable);
        memset(pTable, 0, sizeof(UINT16) * actualSizeOfTable);
        table->CloseRawBuffer();

        uint32_t state[4] = {729055690, 833774698, 218408041, 493449127}; // 4 randomly generated numbers to initialize random number state

        // Attempt to fill  table

        hr = EnumerateAllCustomAttributes(pMDImport, [&](LPCUTF8 szNamespace, LPCUTF8 szName, mdToken tkParent)
        {
            StackSString name(SString::Utf8);
            name.AppendUTF8(szNamespace);
            name.AppendUTF8(NAMESPACE_SEPARATOR_STR);
            name.AppendUTF8(szName);

            StackScratchBuffer buff;
            const char* pDebugNameUTF8 = name.GetUTF8(buff);
            size_t len = strlen(pDebugNameUTF8);

            // This hashing algorithm MUST match exactly the logic in NativeCuckooFilter
            DWORD hashOfAttribute = ComputeNameHashCode(pDebugNameUTF8);
            UINT32 hash = CombineTwoValuesIntoHash(hashOfAttribute, tkParent);
            UINT16 fingerprint = (UINT16)(hash >> 16);
            if (fingerprint == 0)
                fingerprint = 1;

            UINT bucketAIndex = hash % bucketCount;
            UINT bucketBIndex = (bucketAIndex ^ (NativeFormat::NativeCuckooFilter::ComputeFingerprintHash(fingerprint)  % bucketCount));

            _ASSERTE(bucketAIndex == (bucketBIndex ^ (NativeFormat::NativeCuckooFilter::ComputeFingerprintHash(fingerprint) % bucketCount)));

            if (xorshift128(state) & 1) // Randomly choose which bucket to attempt to fill first
            {
                UINT temp = bucketAIndex;
                bucketAIndex = bucketBIndex;
                bucketBIndex = temp;
            }

            auto hasEntryInBucket = [&table](UINT bucketIndex, UINT16 fprint)
            {
                for (int i = 0; i < 8; i++)
                {
                    if ((*table)[(bucketIndex * 8) + i] == fprint)
                        return true;
                }
                return false;
            };

            auto isEmptyEntryInBucket = [&table](UINT bucketIndex)
            {
                for (int i = 0; i < 8; i++)
                {
                    if ((*table)[(bucketIndex * 8) + i] == 0)
                        return true;
                }
                return false;
            };

            auto fillEmptyEntryInBucket = [&table](UINT bucketIndex, UINT16 fprint)
            {
                for (int i = 0; i < 8; i++)
                {
                    if ((*table)[(bucketIndex * 8) + i] == 0)
                    {
                        (*table)[(bucketIndex * 8) + i] = fprint;
                        return;
                    }
                }
                _ASSERTE(!"Not possible to reach here");
                return;
            };

            // Scan for pre-existing fingerprint entry in buckets
            if (hasEntryInBucket(bucketAIndex, fingerprint) || hasEntryInBucket(bucketBIndex, fingerprint))
                return S_OK;

            // Determine if there is space in a bucket to add a new entry
            if (isEmptyEntryInBucket(bucketAIndex))
            {
                fillEmptyEntryInBucket(bucketAIndex, fingerprint);
                return S_OK;
            }
            if (isEmptyEntryInBucket(bucketBIndex))
            {
                fillEmptyEntryInBucket(bucketBIndex, fingerprint);
                return S_OK;
            }

            int MaxNumKicks = 256;
            // Note, that bucketAIndex itself was chosen randomly above.
            for (int n = 0; n < MaxNumKicks; n++)
            {
                // Randomly swap an entry in bucket bucketAIndex with fingerprint
                UINT entryIndexInBucket = xorshift128(state) & 0x7;
                UINT16 temp = fingerprint;
                fingerprint = (*table)[(bucketAIndex * 8) + entryIndexInBucket];
                (*table)[(bucketAIndex * 8) + entryIndexInBucket] = temp;

                // Find other bucket
                bucketAIndex = bucketAIndex ^ (NativeFormat::NativeCuckooFilter::ComputeFingerprintHash(fingerprint) % bucketCount);
                if (isEmptyEntryInBucket(bucketAIndex))
                {
                    fillEmptyEntryInBucket(bucketAIndex, fingerprint);
                    return S_OK;
                }
            }

            tryAgainWithBiggerTable = true;
            return E_FAIL;
        });

        if (tryAgainWithBiggerTable)
        {
            // bucket entry kicking path requires bucket counts to be power of two in size due to use of xor to retrieve second hash
            bucketCount *= 2;
        }
    } while(tryAgainWithBiggerTable && ((countOfRetries++) < 2));

    if (tryAgainWithBiggerTable)
    {
        return E_FAIL;
    }

    return S_OK;
}

void ZapImage::OutputAttributePresenceFilter(IMDInternalImport * pMDImport)
{
    // Core library attributes are checked FAR more often than other dlls
    // attributes, so produce a highly efficient table for determining if they are
    // present. Other assemblies *MAY* benefit from this feature, but it doesn't show
    // as useful at this time.

    if (m_hModule != m_zapper->m_pEECompileInfo->GetLoaderModuleForMscorlib())
        return;

    SArray<UINT16> table;
    if (SUCCEEDED(ComputeAttributePresenceTable(pMDImport, &table)))
    {
        UINT16* pRawTable = table.OpenRawBuffer(table.GetCount());
        ZapNode * pBlob = ZapBlob::NewBlob(this, pRawTable, table.GetCount() * sizeof(UINT16));
        table.CloseRawBuffer();

        _ASSERTE(m_pAttributePresenceSection);
        m_pAttributePresenceSection->Place(pBlob);
        GetReadyToRunHeader()->RegisterSection(READYTORUN_SECTION_ATTRIBUTEPRESENCE, pBlob);
    }
}

//
// Verify that data structures and flags shared between NGen and ReadyToRun are in sync
//

//
// READYTORUN_IMPORT_SECTION
//
static_assert_no_msg(sizeof(READYTORUN_IMPORT_SECTION)          == sizeof(CORCOMPILE_IMPORT_SECTION));

static_assert_no_msg((int)READYTORUN_IMPORT_SECTION_TYPE_UNKNOWN     == (int)CORCOMPILE_IMPORT_TYPE_UNKNOWN);

static_assert_no_msg((int)READYTORUN_IMPORT_SECTION_FLAGS_EAGER      == (int)CORCOMPILE_IMPORT_FLAGS_EAGER);

//
// READYTORUN_METHOD_SIG
//
static_assert_no_msg((int)READYTORUN_METHOD_SIG_UnboxingStub         == (int)ENCODE_METHOD_SIG_UnboxingStub);
static_assert_no_msg((int)READYTORUN_METHOD_SIG_InstantiatingStub    == (int)ENCODE_METHOD_SIG_InstantiatingStub);
static_assert_no_msg((int)READYTORUN_METHOD_SIG_MethodInstantiation  == (int)ENCODE_METHOD_SIG_MethodInstantiation);
static_assert_no_msg((int)READYTORUN_METHOD_SIG_SlotInsteadOfToken   == (int)ENCODE_METHOD_SIG_SlotInsteadOfToken);
static_assert_no_msg((int)READYTORUN_METHOD_SIG_MemberRefToken       == (int)ENCODE_METHOD_SIG_MemberRefToken);
static_assert_no_msg((int)READYTORUN_METHOD_SIG_Constrained          == (int)ENCODE_METHOD_SIG_Constrained);
static_assert_no_msg((int)READYTORUN_METHOD_SIG_OwnerType            == (int)ENCODE_METHOD_SIG_OwnerType);

//
// READYTORUN_FIELD_SIG
//
static_assert_no_msg((int)READYTORUN_FIELD_SIG_IndexInsteadOfToken   == (int)ENCODE_FIELD_SIG_IndexInsteadOfToken);
static_assert_no_msg((int)READYTORUN_FIELD_SIG_MemberRefToken        == (int)ENCODE_FIELD_SIG_MemberRefToken);
static_assert_no_msg((int)READYTORUN_FIELD_SIG_OwnerType             == (int)ENCODE_FIELD_SIG_OwnerType);

//
// READYTORUN_FIXUP
//
static_assert_no_msg((int)READYTORUN_FIXUP_ThisObjDictionaryLookup   == (int)ENCODE_DICTIONARY_LOOKUP_THISOBJ);
static_assert_no_msg((int)READYTORUN_FIXUP_TypeDictionaryLookup      == (int)ENCODE_DICTIONARY_LOOKUP_TYPE);
static_assert_no_msg((int)READYTORUN_FIXUP_MethodDictionaryLookup    == (int)ENCODE_DICTIONARY_LOOKUP_METHOD);

static_assert_no_msg((int)READYTORUN_FIXUP_TypeHandle                == (int)ENCODE_TYPE_HANDLE);
static_assert_no_msg((int)READYTORUN_FIXUP_MethodHandle              == (int)ENCODE_METHOD_HANDLE);
static_assert_no_msg((int)READYTORUN_FIXUP_FieldHandle               == (int)ENCODE_FIELD_HANDLE);

static_assert_no_msg((int)READYTORUN_FIXUP_MethodEntry               == (int)ENCODE_METHOD_ENTRY);
static_assert_no_msg((int)READYTORUN_FIXUP_MethodEntry_DefToken      == (int)ENCODE_METHOD_ENTRY_DEF_TOKEN);
static_assert_no_msg((int)READYTORUN_FIXUP_MethodEntry_RefToken      == (int)ENCODE_METHOD_ENTRY_REF_TOKEN);

static_assert_no_msg((int)READYTORUN_FIXUP_VirtualEntry              == (int)ENCODE_VIRTUAL_ENTRY);
static_assert_no_msg((int)READYTORUN_FIXUP_VirtualEntry_DefToken     == (int)ENCODE_VIRTUAL_ENTRY_DEF_TOKEN);
static_assert_no_msg((int)READYTORUN_FIXUP_VirtualEntry_RefToken     == (int)ENCODE_VIRTUAL_ENTRY_REF_TOKEN);
static_assert_no_msg((int)READYTORUN_FIXUP_VirtualEntry_Slot         == (int)ENCODE_VIRTUAL_ENTRY_SLOT);

static_assert_no_msg((int)READYTORUN_FIXUP_Helper                    == (int)ENCODE_READYTORUN_HELPER);
static_assert_no_msg((int)READYTORUN_FIXUP_StringHandle              == (int)ENCODE_STRING_HANDLE);

static_assert_no_msg((int)READYTORUN_FIXUP_NewObject                 == (int)ENCODE_NEW_HELPER);
static_assert_no_msg((int)READYTORUN_FIXUP_NewArray                  == (int)ENCODE_NEW_ARRAY_HELPER);

static_assert_no_msg((int)READYTORUN_FIXUP_IsInstanceOf              == (int)ENCODE_ISINSTANCEOF_HELPER);
static_assert_no_msg((int)READYTORUN_FIXUP_ChkCast                   == (int)ENCODE_CHKCAST_HELPER);

static_assert_no_msg((int)READYTORUN_FIXUP_FieldAddress              == (int)ENCODE_FIELD_ADDRESS);
static_assert_no_msg((int)READYTORUN_FIXUP_CctorTrigger              == (int)ENCODE_CCTOR_TRIGGER);

static_assert_no_msg((int)READYTORUN_FIXUP_StaticBaseNonGC           == (int)ENCODE_STATIC_BASE_NONGC_HELPER);
static_assert_no_msg((int)READYTORUN_FIXUP_StaticBaseGC              == (int)ENCODE_STATIC_BASE_GC_HELPER);
static_assert_no_msg((int)READYTORUN_FIXUP_ThreadStaticBaseNonGC     == (int)ENCODE_THREAD_STATIC_BASE_NONGC_HELPER);
static_assert_no_msg((int)READYTORUN_FIXUP_ThreadStaticBaseGC        == (int)ENCODE_THREAD_STATIC_BASE_GC_HELPER);

static_assert_no_msg((int)READYTORUN_FIXUP_FieldBaseOffset           == (int)ENCODE_FIELD_BASE_OFFSET);
static_assert_no_msg((int)READYTORUN_FIXUP_FieldOffset               == (int)ENCODE_FIELD_OFFSET);

static_assert_no_msg((int)READYTORUN_FIXUP_TypeDictionary            == (int)ENCODE_TYPE_DICTIONARY);
static_assert_no_msg((int)READYTORUN_FIXUP_MethodDictionary          == (int)ENCODE_METHOD_DICTIONARY);

static_assert_no_msg((int)READYTORUN_FIXUP_Check_TypeLayout          == (int)ENCODE_CHECK_TYPE_LAYOUT);
static_assert_no_msg((int)READYTORUN_FIXUP_Check_FieldOffset         == (int)ENCODE_CHECK_FIELD_OFFSET);

static_assert_no_msg((int)READYTORUN_FIXUP_DelegateCtor              == (int)ENCODE_DELEGATE_CTOR);

static_assert_no_msg((int)READYTORUN_FIXUP_DeclaringTypeHandle       == (int)ENCODE_DECLARINGTYPE_HANDLE);

static_assert_no_msg((int)READYTORUN_FIXUP_IndirectPInvokeTarget     == (int)ENCODE_INDIRECT_PINVOKE_TARGET);

//
// READYTORUN_EXCEPTION
//
static_assert_no_msg(sizeof(READYTORUN_EXCEPTION_LOOKUP_TABLE_ENTRY) == sizeof(CORCOMPILE_EXCEPTION_LOOKUP_TABLE_ENTRY));
static_assert_no_msg(sizeof(READYTORUN_EXCEPTION_CLAUSE) == sizeof(CORCOMPILE_EXCEPTION_CLAUSE));