icache.c

Go to the documentation of this file.

/*
 * Copyright (c) 2020 Bitdefender
 * SPDX-License-Identifier: Apache-2.0
 */
#include "icache.h"
#include "hook.h"


static __inline DWORD
IntIcHashInv(
    _In_ PINS_CACHE Cache,
    _In_ QWORD Gva
    )
{
    // We must include the entire page in this hash-table. Can't use bits lower than 12.
    return (Gva >> 12) & (Cache->InvCount - 1);
}


static __inline DWORD
IntIcHashLine(
    _In_ PINS_CACHE Cache,
    _In_ QWORD Gva
    )
{
    // We use the frame number, so we can do fast invalidation on modified GVAs. Otherwise, we'd have to iterate
    // the entire cache, which is very slow.
    return (Gva >> 12) & (Cache->LinesCount - 1);
}


void
IntIcDumpIcache(
    void
    )
{
    PINS_CACHE cache;
    DWORD i, j;
    LIST_ENTRY *list;

    cache = (PINS_CACHE)gGuest.InstructionCache;

    LOG("Instruction cache:\n");

    NLOG("Number of lines:  %d\n", cache->LinesCount);
    NLOG("Entries per line: %d\n", cache->EntriesCount);
    NLOG("Invalidation size:%d\n", cache->InvCount);
    NLOG("Fill count:       %d\n", cache->FillRate);
    NLOG("Flush count:      %d\n", cache->FlushCount);
    NLOG("Hit count:        %d\n", cache->HitCount);
    NLOG("Miss count:       %d\n", cache->MissCount);
    NLOG("Replace count:    %d\n", cache->ReplaceCount);
    NLOG("Pgflush count:    %d\n", cache->PageFlushCount);


    // Dump the entries inside the cache
    for (i = 0; i < cache->LinesCount; i++)
    {
        for (j = 0; j < cache->EntriesCount; j++)
        {
            if (cache->Lines[i].Entries[j].Valid)
            {
                char text[ND_MIN_BUF_SIZE] = {0};

                NdToText(&cache->Lines[i].Entries[j].Instruction,
                         cache->Lines[i].Entries[j].Gva,
                         ND_MIN_BUF_SIZE,
                         text);

                NLOG("-> %04d - %04d: 0x%016llx:0x%016llx, %08d %d %d %d > %s\n",
                     i, j,
                     cache->Lines[i].Entries[j].Gva,
                     cache->Lines[i].Entries[j].Cr3,
                     cache->Lines[i].Entries[j].RefCount,
                     cache->Lines[i].Entries[j].Valid,
                     cache->Lines[i].Entries[j].Pinned,
                     cache->Lines[i].Entries[j].Global,
                     text);
            }
        }
    }

    NLOG("Invalidation queue:\n");

    // Dump the invalidation queue
    for (i = 0; i < cache->InvCount; i++)
    {
        if (IsListEmpty(&cache->InsInvGva[i]))
        {
            continue;
        }

        NLOG("%04d: ", i);

        list = cache->InsInvGva[i].Flink;
        while (list != &cache->InsInvGva[i])
        {
            PINS_CACHE_INV_ENTRY pInv = CONTAINING_RECORD(list, INS_CACHE_INV_ENTRY, Link);

            list = list->Flink;

            NLOG("0x%016llx:0x%016llx:0x%016llx:%04d    ", pInv->Gva, pInv->Gpa, pInv->Cr3, pInv->RefCount);
        }

        NLOG("\n");
    }
}


static INTSTATUS
IntIcFreeInvdEntry(
    _In_ PINS_CACHE_INV_ENTRY Invd
    )
{
    INTSTATUS status;

    status = INT_STATUS_SUCCESS;

    if (NULL != Invd->SwapHook)
    {
        status = IntHookPtsRemoveHook((HOOK_PTS **)&Invd->SwapHook, 0);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntHookPtsRemoveHook failed: 0x%08x\n", status);
        }
    }

    if (NULL != Invd->WriteHook)
    {
        status = IntHookGpaRemoveHook((HOOK_GPA **)&Invd->WriteHook, 0);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntHookGpaRemoveHook failed: 0x%08x\n", status);
        }
    }

    HpFreeAndNullWithTag(&Invd, IC_TAG_IINV);

    return status;
}


static INTSTATUS
IntIcRemoveAllInvdEntries(
    _In_ PINS_CACHE Cache
    )
{
    INTSTATUS status;
    DWORD i;

    for (i = 0; i < Cache->InvCount; i++)
    {
        LIST_ENTRY *list = Cache->InsInvGva[i].Flink;

        while (list != &Cache->InsInvGva[i])
        {
            PINS_CACHE_INV_ENTRY pInv = CONTAINING_RECORD(list, INS_CACHE_INV_ENTRY, Link);
            list = list->Flink;

            pInv->RefCount = 0;

            RemoveEntryList(&pInv->Link);

            status = IntIcFreeInvdEntry(pInv);
            if (!INT_SUCCESS(status))
            {
                ERROR("[ERROR] IntIcFreeInvdEntry failed: 0x%08x\n", status);
            }
        }
    }

    return INT_STATUS_SUCCESS;
}


static INTSTATUS
IntIcInvdEntry(
    _In_ PINS_CACHE Cache,
    _Inout_ PINS_CACHE_INV_ENTRY Invd
    )
{
    INTSTATUS status;

    UNREFERENCED_PARAMETER(Cache);

    if (0 == Invd->RefCount)
    {
        return INT_STATUS_INVALID_PARAMETER_2;
    }

    Invd->RefCount--;

    if (0 == Invd->RefCount)
    {
        RemoveEntryList(&Invd->Link);

        status = IntIcFreeInvdEntry(Invd);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntIcFreeInvdEntry failed: 0x%08x\n", status);
            return status;
        }
    }

    return INT_STATUS_SUCCESS;
}


static INTSTATUS
IntIcInvdCacheEntry(
    _In_ PINS_CACHE Cache,
    _In_ PINS_CACHE_ENTRY Entry
    )
{
    INTSTATUS status;

    if (NULL != Entry->Invd1)
    {
        status = IntIcInvdEntry(Cache, Entry->Invd1);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntIcInvdEntry failed: 0x%08x\n", status);
        }

        Entry->Invd1 = NULL;
    }

    if (NULL != Entry->Invd2)
    {
        status = IntIcInvdEntry(Cache, Entry->Invd2);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntIcInvdEntry failed: 0x%08x\n", status);
        }

        Entry->Invd2 = NULL;
    }

    return INT_STATUS_SUCCESS;
}


static INTSTATUS
IntIcWriteHandler(
    _In_ INS_CACHE_INV_ENTRY const *Context,
    _In_ void const *Hook,
    _In_ QWORD Address,
    _Out_ INTRO_ACTION *Action
    )
{
    PINS_CACHE pCache;
    INS_CACHE_INV_ENTRY const *pInv;
    QWORD gva, cr3;
    BOOLEAN spill;

    UNREFERENCED_PARAMETER(Address);
    UNREFERENCED_PARAMETER(Hook);

    // Get the cache.
    pCache = (PINS_CACHE)gGuest.InstructionCache;
    pInv = Context;

    gva = pInv->Gva;
    cr3 = pInv->Cr3;
    spill = pInv->Spill;

    // Note: calls to IntIcFlushGvaPage will remove the hook and will free the pInvd entry if the ref count reaches 0.
    // We cannot safely access the pInvd entry after calling IntIcFlushGvaPage.

    // Flush the instructions contained inside this (virtual) page.
    IntIcFlushGvaPage(pCache, gva, cr3, FALSE);

    if (spill)
    {
        // If this page contains spilled instructions, invalidate those too.
        IntIcFlushGvaPage(pCache, gva - 0x1000, cr3, TRUE);
    }

    // Obviously, we allow the write.
    *Action = introGuestAllowed;

    return INT_STATUS_SUCCESS;
}


static INTSTATUS
IntIcSwapHandler(
    _In_ void *Context,
    _In_ QWORD VirtualAddress,
    _In_ QWORD OldEntry,
    _In_ QWORD NewEntry,
    _In_ QWORD OldPageSize,
    _In_ QWORD NewPageSize
    )
{
    PINS_CACHE pCache;
    PINS_CACHE_INV_ENTRY pInv;
    QWORD gva, cr3;
    BOOLEAN spill;

    UNREFERENCED_PARAMETER(Context);
    UNREFERENCED_PARAMETER(VirtualAddress);
    UNREFERENCED_PARAMETER(OldPageSize);
    UNREFERENCED_PARAMETER(NewPageSize);

    pCache = (PINS_CACHE)gGuest.InstructionCache;
    pInv = (PINS_CACHE_INV_ENTRY)Context;

    gva = pInv->Gva;
    cr3 = pInv->Cr3;
    spill = pInv->Spill;

    // Note: calls to IntIcFlushGvaPage will remove the hook and will free the pInvd entry if the ref count reaches 0.

#define INV_MASK (~0x60ULL)

    if ((OldEntry & INV_MASK) != (NewEntry & INV_MASK))
    {
        // Flush the instructions contained inside this page.
        IntIcFlushGvaPage(pCache, gva, cr3, FALSE);

        if (spill)
        {
            // If this page contains spilled instructions, invalidate those too.
            IntIcFlushGvaPage(pCache, gva - 0x1000, cr3, TRUE);
        }
    }

    return INT_STATUS_SUCCESS;
}


static INTSTATUS
IntIcLookupInstructionInternal(
    _In_ PINS_CACHE Cache,
    _Out_ PINSTRUX Instrux,
    _In_ QWORD Gva,
    _In_ QWORD Cr3,
    _In_ DWORD Lru
    )
{
    INTSTATUS status;
    DWORD line, i;

    // This function is internal, there's no point on validating the parameters - they have already been
    // validated by the caller.

    // Get the cache line for this address
    line = IntIcHashLine(Cache, Gva);

    status = INT_STATUS_NOT_FOUND;

    // Check every set for the tag & valid bit
    for (i = 0; i < Cache->EntriesCount; i++)
    {
        if ((Cache->Lines[line].Entries[i].Gva == Gva) &&
            (Cache->Lines[line].Entries[i].Valid) &&
            ((Cache->Lines[line].Entries[i].Cr3 == Cr3) ||
             (IC_ANY_VAS == Cr3) ||
             (Cache->Lines[line].Entries[i].Global)))
        {
            memcpy(Instrux, &Cache->Lines[line].Entries[i].Instruction, sizeof(INSTRUX));

            Cache->Lines[line].Entries[i].RefCount += Lru;

            status = INT_STATUS_SUCCESS;

            break;
        }
    }

    if (INT_STATUS_NOT_FOUND == status)
    {
        Cache->MissCount++;
    }
    else
    {
        Cache->HitCount++;
    }

    return status;
}


INTSTATUS
IntIcLookupInstruction(
    _In_ PINS_CACHE Cache,
    _Out_ PINSTRUX Instrux,
    _In_ QWORD Gva,
    _In_ QWORD Cr3
    )
{
    INTSTATUS status;

    if (Cache == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    if (Instrux == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_2;
    }

    status = IntIcLookupInstructionInternal(Cache, Instrux, Gva, Cr3, 1);

    return status;
}


INTSTATUS
IntIcFlush(
    _In_ PINS_CACHE Cache
    )
//
{
    INTSTATUS status;
    DWORD i, j;

    if (Cache == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    if (!Cache->Dirty)
    {
        return INT_STATUS_SUCCESS;
    }

    for (i = 0; i < Cache->LinesCount; i++)
    {
        for (j = 0; j < Cache->EntriesCount; j++)
        {
            if (Cache->Lines[i].Entries[j].Valid)
            {
                Cache->Lines[i].Entries[j].Gva = 0;
                Cache->Lines[i].Entries[j].Cr3 = 0;
                Cache->Lines[i].Entries[j].Invd1 = NULL;
                Cache->Lines[i].Entries[j].Invd2 = NULL;
                Cache->Lines[i].Entries[j].Pinned = FALSE;
                Cache->Lines[i].Entries[j].Global = FALSE;
                Cache->Lines[i].Entries[j].RefCount = 0;
                Cache->Lines[i].Entries[j].Valid = FALSE;
            }
        }
    }

    status = IntIcRemoveAllInvdEntries(Cache);
    if (!INT_SUCCESS(status))
    {
        ERROR("[ERROR] IntIcRemoveAllInvdEntries failed: 0x%08x\n", status);
    }

    Cache->FillRate = 0;
    Cache->FlushCount++;
    Cache->Dirty = FALSE;

    return INT_STATUS_SUCCESS;
}


INTSTATUS
IntIcFlushAddress(
    _In_ PINS_CACHE Cache,
    _In_ QWORD Gva,
    _In_ QWORD Cr3
    )
{
    INTSTATUS status;
    DWORD line, i;

    if (Cache == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    line = IntIcHashLine(Cache, Gva);

    status = INT_STATUS_NOT_FOUND;

    for (i = 0; i < Cache->EntriesCount; i++)
    {
        if ((Cache->Lines[line].Entries[i].Gva == Gva) &&
            (Cache->Lines[line].Entries[i].Valid) &&
            ((Cache->Lines[line].Entries[i].Cr3 == Cr3) ||
             (IC_ANY_VAS == Cr3) ||
             (Cache->Lines[line].Entries[i].Global)))
        {
            // Invalidate the Invd entry.
            status = IntIcInvdCacheEntry(Cache, &Cache->Lines[line].Entries[i]);
            if (!INT_SUCCESS(status))
            {
                ERROR("[ERROR] IntIcInvdCacheEntry failed: 0x%08x\n", status);
            }

            Cache->Lines[line].Entries[i].Valid = 0;
            Cache->Lines[line].Entries[i].Gva = 0;
            Cache->Lines[line].Entries[i].Cr3 = 0;
            Cache->Lines[line].Entries[i].Invd1 = NULL;
            Cache->Lines[line].Entries[i].Invd2 = NULL;

            status = INT_STATUS_SUCCESS;
        }
    }

    return status;
}


INTSTATUS
IntIcFlushGvaPage(
    _In_ PINS_CACHE Cache,
    _In_ QWORD Gva,
    _In_ QWORD Cr3,
    _In_ BOOLEAN Spill
    )
{
    INTSTATUS status;
    DWORD line, i;

    if (Cache == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    Cache->PageFlushCount++;

    line = IntIcHashLine(Cache, Gva);

    Gva &= PAGE_MASK;
    status = INT_STATUS_NOT_FOUND;

    for (i = 0; i < Cache->EntriesCount; i++)
    {
        if (((Cache->Lines[line].Entries[i].Gva & PAGE_MASK) == Gva) &&
            (Cache->Lines[line].Entries[i].Valid) &&
            ((Cache->Lines[line].Entries[i].Cr3 == Cr3) ||
             (IC_ANY_VAS == Cr3) ||
             (Cache->Lines[line].Entries[i].Global)) &&
            ((!Spill) || ((Cache->Lines[line].Entries[i].Gva & PAGE_OFFSET) +
                          Cache->Lines[line].Entries[i].Instruction.Length > PAGE_SIZE)))
        {
            // Invalidate the Invd entry.
            status = IntIcInvdCacheEntry(Cache, &Cache->Lines[line].Entries[i]);
            if (!INT_SUCCESS(status))
            {
                ERROR("[ERROR] IntIcInvdCacheEntry failed: 0x%08x\n", status);
            }

            Cache->Lines[line].Entries[i].Valid = 0;
            Cache->Lines[line].Entries[i].Gva = 0;
            Cache->Lines[line].Entries[i].Cr3 = 0;
            Cache->Lines[line].Entries[i].Invd1 = NULL;
            Cache->Lines[line].Entries[i].Invd2 = NULL;

            status = INT_STATUS_SUCCESS;
        }
    }

    return status;
}


INTSTATUS
IntIcFlushGpaPage(
    _In_ PINS_CACHE Cache,
    _In_ QWORD Gpa
    )
{
    INTSTATUS status;
    DWORD i, j;

    if (Cache == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    status = INT_STATUS_NOT_FOUND;

    Gpa &= PHYS_PAGE_MASK;

    Cache->PageFlushCount++;

    for (i = 0; i < Cache->LinesCount; i++)
    {
        for (j = 0; j < Cache->EntriesCount; j++)
        {
            if ((Cache->Lines[i].Entries[j].Valid) &&
                (((NULL != Cache->Lines[i].Entries[j].Invd1) && (Cache->Lines[i].Entries[j].Invd1->Gpa == Gpa)) ||
                 ((NULL != Cache->Lines[i].Entries[j].Invd2) && (Cache->Lines[i].Entries[j].Invd2->Gpa == Gpa))))
            {
                // Invalidate the Invd entry.
                status = IntIcInvdCacheEntry(Cache, &Cache->Lines[i].Entries[j]);
                if (!INT_SUCCESS(status))
                {
                    ERROR("[ERROR] IntIcInvdCacheEntry failed: 0x%08x\n", status);
                }

                Cache->Lines[i].Entries[j].Valid = 0;
                Cache->Lines[i].Entries[j].Gva = 0;
                Cache->Lines[i].Entries[j].Cr3 = 0;
                Cache->Lines[i].Entries[j].Invd1 = NULL;
                Cache->Lines[i].Entries[j].Invd2 = NULL;

                status = INT_STATUS_SUCCESS;
            }
        }
    }

    return status;
}


INTSTATUS
IntIcFlushVaSpace(
    _In_ PINS_CACHE Cache,
    _In_ QWORD Cr3
    )
{
    INTSTATUS status;
    DWORD i, j;

    if (Cache == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    status = INT_STATUS_SUCCESS;

    for (i = 0; i < Cache->LinesCount; i++)
    {
        for (j = 0; j < Cache->EntriesCount; j++)
        {
            if ((Cache->Lines[i].Entries[j].Cr3 == Cr3) || (IC_ANY_VAS == Cr3))
            {
                // Invalidate the Invd entry.
                status = IntIcInvdCacheEntry(Cache, &Cache->Lines[i].Entries[j]);
                if (!INT_SUCCESS(status))
                {
                    ERROR("[ERROR] IntIcInvdCacheEntry failed: 0x%08x\n", status);
                }

                Cache->Lines[i].Entries[j].Valid = 0;
                Cache->Lines[i].Entries[j].Gva = 0;
                Cache->Lines[i].Entries[j].Cr3 = 0;
                Cache->Lines[i].Entries[j].Invd1 = NULL;
                Cache->Lines[i].Entries[j].Invd2 = NULL;

                status = INT_STATUS_SUCCESS;
            }
        }
    }

    return status;
}


static INTSTATUS
IntIcAddInvdForInstruction(
    _In_ PINS_CACHE Cache,
    _In_ QWORD Gva,
    _In_ QWORD Cr3,
    _Out_ PINS_CACHE_INV_ENTRY *Invd
    )
{
    INTSTATUS status;
    LIST_ENTRY *list;
    DWORD invline;
    BOOLEAN bFound;
    PINS_CACHE_INV_ENTRY pInv;
    VA_TRANSLATION tr = { 0 };

    bFound = FALSE;
    pInv = NULL;

    invline = IntIcHashInv(Cache, Gva);

    // We first iterate the existing list of invalidation entries and simply increment the refcount of an existing
    // entry, if available.
    list = Cache->InsInvGva[invline].Flink;
    while (list != &Cache->InsInvGva[invline])
    {
        pInv = CONTAINING_RECORD(list, INS_CACHE_INV_ENTRY, Link);
        list = list->Flink;

        if ((pInv->Gva == (Gva & PAGE_MASK)) && (pInv->Cr3 == Cr3))
        {
            pInv->RefCount++;

            bFound = TRUE;

            break;
        }
    }

    // Invalidation entry not added yet - allocate it & add it now.
    if (!bFound)
    {
        status = IntTranslateVirtualAddressEx(Gva & PAGE_MASK, Cr3 != 0 ? Cr3 : gGuest.Mm.SystemCr3, TRFLG_NONE, &tr);
        if (!INT_SUCCESS(status))
        {
            return status;
        }

        pInv = HpAllocWithTag(sizeof(*pInv), IC_TAG_IINV);
        if (NULL == pInv)
        {
            return INT_STATUS_INSUFFICIENT_RESOURCES;
        }

        pInv->Cr3 = Cr3;
        pInv->RefCount = 1;
        pInv->Gva = Gva & PAGE_MASK;
        pInv->Gpa = tr.PhysicalAddress & PHYS_PAGE_MASK;

        status = IntHookPtsSetHook(Cr3, pInv->Gva, IntIcSwapHandler, pInv, NULL, 0, (PHOOK_PTS *)&pInv->SwapHook);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntHookPtsSetHook failed: 0x%08x\n", status);
            IntIcFreeInvdEntry(pInv);
            return status;
        }

        status = IntHookGpaSetHook(pInv->Gpa, PAGE_SIZE, IG_EPT_HOOK_WRITE, IntIcWriteHandler,
                                   pInv, NULL, 0, (PHOOK_GPA *)&pInv->WriteHook);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntHookGpaSetHook failed on %llx: 0x%08x\n", pInv->Gva, status);
            IntIcFreeInvdEntry(pInv);
            return status;
        }

        // Insert the invalidation line inside the list.
        InsertTailList(&Cache->InsInvGva[invline], &pInv->Link);
    }

    *Invd = pInv;

    return INT_STATUS_SUCCESS;
}


INTSTATUS
IntIcAddInstruction(
    _In_ PINS_CACHE Cache,
    _In_ PINSTRUX Instruction,
    _In_ QWORD Gva,
    _In_ QWORD Cr3,
    _In_ BOOLEAN Global
    )
{
    INTSTATUS status;
    DWORD line, target, i;

    if (Cache == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    if (Instruction == NULL)
    {
        return INT_STATUS_INVALID_PARAMETER_2;
    }

    line = IntIcHashLine(Cache, Gva);

    target = 0xFFFFFFFF;

    for (i = 0; i < Cache->EntriesCount; i++)
    {
        if (!Cache->Lines[line].Entries[i].Valid)
        {
            Cache->FillRate++;

            target = i;

            break;
        }
    }

    if (0xFFFFFFFF == target)
    {
        target = __rdtsc() % Cache->EntriesCount;
    }

    // Check if we need to decrement the refcount for the entry
    if (Cache->Lines[line].Entries[target].Valid)
    {
        status = IntIcInvdCacheEntry(Cache, &Cache->Lines[line].Entries[target]);
        if (!INT_SUCCESS(status))
        {
            ERROR("[ERROR] IntIcInvdCacheEntry failed: 0x%08x\n", status);
        }
    }

    // Mark the entry as invalid, until we completely initialize it - this includes an invalidation entry, if
    // needed.
    Cache->Lines[line].Entries[target].Valid = FALSE;

    Cache->Lines[line].Entries[target].Gva = Gva;
    Cache->Lines[line].Entries[target].Cr3 = Cr3;
    Cache->Lines[line].Entries[target].RefCount = 0;
    Cache->Lines[line].Entries[target].Pinned = FALSE;
    Cache->Lines[line].Entries[target].Global = Global;

    memcpy(&Cache->Lines[line].Entries[target].Instruction, Instruction, sizeof(INSTRUX));

    Cache->Lines[line].Entries[target].Invd1 = NULL;
    Cache->Lines[line].Entries[target].Invd2 = NULL;

    // Add the invalidation entry for this page.
    status = IntIcAddInvdForInstruction(Cache, Gva, Cr3, &Cache->Lines[line].Entries[target].Invd1);
    if (!INT_SUCCESS(status))
    {
        if ((INT_STATUS_PAGE_NOT_PRESENT != status) &&
            (INT_STATUS_NO_MAPPING_STRUCTURES != status))
        {
            ERROR("[ERROR] IntIcAddInvdForInstruction failed: 0x%08x\n", status);
        }

        return status;
    }

    // Handle instructions that cross the page boundary.
    if ((Gva & PAGE_MASK) != ((Gva + Instruction->Length - 1) & PAGE_MASK))
    {
        TRACE("[ICACHE] Instruction at %llx:%d spills the page...\n", Gva, Instruction->Length);

        status = IntIcAddInvdForInstruction(Cache, (Gva & PAGE_MASK) + 0x1000, Cr3,
                                            &Cache->Lines[line].Entries[target].Invd2);
        if (!INT_SUCCESS(status))
        {
            if ((INT_STATUS_PAGE_NOT_PRESENT != status) &&
                (INT_STATUS_NO_MAPPING_STRUCTURES != status))
            {
                ERROR("[ERROR] IntIcAddInvdForInstruction failed: 0x%08x\n", status);
            }

            IntIcInvdEntry(Cache, Cache->Lines[line].Entries[target].Invd1);

            return status;
        }

        // We need to know if this entry is the spill page, so we can properly invalidate the previous page in case
        // if swap/writes.
        Cache->Lines[line].Entries[target].Invd2->Spill = TRUE;
    }

    // Successfully added, the entry is now valid!
    Cache->Lines[line].Entries[target].Valid = TRUE;

    Cache->Dirty = TRUE;

    return INT_STATUS_SUCCESS;
}


INTSTATUS
IntIcCreate(
    _Inout_ INS_CACHE **Cache,
    _In_ DWORD LinesCount,
    _In_ DWORD EntriesCount,
    _In_ DWORD InvCount
    )
{
    INTSTATUS status = INT_STATUS_SUCCESS;
    INS_CACHE *pCache;

    if (NULL == Cache)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    // LinesCount and InvCount must be powers of two.
    if (0 != (LinesCount & (LinesCount - 1)))
    {
        return INT_STATUS_INVALID_PARAMETER_2;
    }

    if (0 != (InvCount & (InvCount - 1)))
    {
        return INT_STATUS_INVALID_PARAMETER_4;
    }

    pCache = HpAllocWithTag(sizeof(*pCache), IC_TAG_INSC);
    if (NULL == pCache)
    {
        return INT_STATUS_INSUFFICIENT_RESOURCES;
    }

    pCache->LinesCount = LinesCount;
    pCache->EntriesCount = EntriesCount;
    pCache->InvCount = InvCount;

    pCache->HitCount = 0;
    pCache->MissCount = 0;
    pCache->FillRate = 0;
    pCache->FlushCount = 0;
    pCache->ReplaceCount = 0;
    pCache->PageFlushCount = 0;

    pCache->Lines = HpAllocWithTag(sizeof(*pCache->Lines) * LinesCount, IC_TAG_INSC);
    if (NULL == pCache->Lines)
    {
        status = INT_STATUS_INSUFFICIENT_RESOURCES;
        goto cleanup_and_exit;
    }

    for (DWORD i = 0; i < LinesCount; i++)
    {
        pCache->Lines[i].Entries = HpAllocWithTag(sizeof(*pCache->Lines[0].Entries) * EntriesCount, IC_TAG_INSC);
        if (NULL == pCache->Lines[i].Entries)
        {
            status = INT_STATUS_INSUFFICIENT_RESOURCES;
            goto cleanup_and_exit;
        }
    }

    pCache->InsInvGva = HpAllocWithTag(sizeof(*pCache->InsInvGva) * InvCount, IC_TAG_INSC);
    if (NULL == pCache->InsInvGva)
    {
        status = INT_STATUS_INSUFFICIENT_RESOURCES;
        goto cleanup_and_exit;
    }

    for (DWORD j = 0; j < InvCount; j++)
    {
        InitializeListHead(&pCache->InsInvGva[j]);
    }

cleanup_and_exit:
    if (!INT_SUCCESS(status))
    {
        if (NULL != pCache)
        {
            if (NULL != pCache->InsInvGva)
            {
                HpFreeAndNullWithTag(&pCache->InsInvGva, IC_TAG_INSC);
            }

            if (NULL != pCache->Lines)
            {
                for (DWORD i = 0; i < LinesCount; i++)
                {
                    if (NULL != pCache->Lines[i].Entries)
                    {
                        HpFreeAndNullWithTag(&pCache->Lines[i].Entries, IC_TAG_INSC);
                    }
                }

                HpFreeAndNullWithTag(&pCache->Lines, IC_TAG_INSC);
            }

            HpFreeAndNullWithTag(&pCache, IC_TAG_INSC);
        }
    }
    else
    {
        IntIcFlush(pCache);
    }

    *Cache = pCache;

    return status;
}


INTSTATUS
IntIcDestroy(
    _Inout_ PINS_CACHE *Cache
    )
{
    INTSTATUS status;
    DWORD i;
    PINS_CACHE pCache;

    if (NULL == Cache)
    {
        return INT_STATUS_INVALID_PARAMETER_1;
    }

    pCache = *Cache;
    if (NULL == pCache)
    {
        return INT_STATUS_NOT_INITIALIZED_HINT;
    }

    status = IntIcRemoveAllInvdEntries(*Cache);
    if (!INT_SUCCESS(status))
    {
        ERROR("[ERROR] IntIcRemoveAllInvdEntries failed: 0x%08x\n", status);
    }

    for (i = 0; i < pCache->LinesCount; i++)
    {
        HpFreeAndNullWithTag(&pCache->Lines[i].Entries, IC_TAG_INSC);
    }

    HpFreeAndNullWithTag(&pCache->Lines, IC_TAG_INSC);

    HpFreeAndNullWithTag(&pCache->InsInvGva, IC_TAG_INSC);

    HpFreeAndNullWithTag(Cache, IC_TAG_INSC);

    return INT_STATUS_SUCCESS;
}