wnuma.cpp

Go to the documentation of this file.

/* Copyright (c) 2010 Wildfire Games
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "precompiled.h"
#include "lib/sysdep/numa.h"

#include "lib/bits.h"   // PopulationCount
#include "lib/alignment.h"
#include "lib/timer.h"
#include "lib/module_init.h"
#include "lib/sysdep/vm.h"
#include "lib/sysdep/acpi.h"
#include "lib/sysdep/os_cpu.h"
#include "lib/sysdep/os/win/win.h"
#include "lib/sysdep/os/win/wutil.h"
#include "lib/sysdep/os/win/wcpu.h"
#include <Psapi.h>

#if ARCH_X86_X64
#include "lib/sysdep/arch/x86_x64/apic.h"   // ProcessorFromApicId
#endif


//-----------------------------------------------------------------------------
// nodes

struct Node // POD
{
    // (Windows doesn't guarantee node numbers are contiguous, so
    // we associate them with contiguous indices in nodes[])
    UCHAR nodeNumber;

    u32 proximityDomainNumber;
    uintptr_t processorMask;
};

static Node nodes[os_cpu_MaxProcessors];
static size_t numNodes;

static Node* AddNode()
{
    ENSURE(numNodes < ARRAY_SIZE(nodes));
    return &nodes[numNodes++];
}

static Node* FindNodeWithProcessorMask(uintptr_t processorMask)
{
    for(size_t node = 0; node < numNodes; node++)
    {
        if(nodes[node].processorMask == processorMask)
            return &nodes[node];
    }

    return 0;
}

static Node* FindNodeWithProcessor(size_t processor)
{
    for(size_t node = 0; node < numNodes; node++)
    {
        if(IsBitSet(nodes[node].processorMask, processor))
            return &nodes[node];
    }

    return 0;
}


//-----------------------------------------------------------------------------
// Windows topology

static UCHAR HighestNodeNumber()
{
    WUTIL_FUNC(pGetNumaHighestNodeNumber, BOOL, (PULONG));
    WUTIL_IMPORT_KERNEL32(GetNumaHighestNodeNumber, pGetNumaHighestNodeNumber);
    if(!pGetNumaHighestNodeNumber)
        return 0;   // NUMA not supported => only one node

    ULONG highestNodeNumber;
    const BOOL ok = pGetNumaHighestNodeNumber(&highestNodeNumber);
    WARN_IF_FALSE(ok);
    return (UCHAR)highestNodeNumber;
}

static void PopulateNodes()
{
    WUTIL_FUNC(pGetNumaNodeProcessorMask, BOOL, (UCHAR, PULONGLONG));
    WUTIL_IMPORT_KERNEL32(GetNumaNodeProcessorMask, pGetNumaNodeProcessorMask);
    if(!pGetNumaNodeProcessorMask)
        return;

    DWORD_PTR processAffinity, systemAffinity;
    {
        const BOOL ok = GetProcessAffinityMask(GetCurrentProcess(), &processAffinity, &systemAffinity);
        WARN_IF_FALSE(ok);
    }
    ENSURE(PopulationCount(processAffinity) <= PopulationCount(systemAffinity));

    for(UCHAR nodeNumber = 0; nodeNumber <= HighestNodeNumber(); nodeNumber++)
    {
        ULONGLONG affinity;
        {
            const BOOL ok = pGetNumaNodeProcessorMask(nodeNumber, &affinity);
            WARN_IF_FALSE(ok);
        }
        if(!affinity)
            continue;   // empty node, skip

        Node* node = AddNode();
        node->nodeNumber = nodeNumber;
        node->processorMask = wcpu_ProcessorMaskFromAffinity(processAffinity, (DWORD_PTR)affinity);
    }
}


//-----------------------------------------------------------------------------
// ACPI SRAT topology

#if ARCH_X86_X64

#pragma pack(push, 1)

// fields common to Affinity* structures
struct AffinityHeader
{
    u8 type;
    u8 length;  // size [bytes], including this header
};

struct AffinityAPIC
{
    static const u8 type = 0;

    AffinityHeader header;
    u8 proximityDomainNumber0;
    u8 apicId;
    u32 flags;
    u8 sapicId;
    u8 proximityDomainNumber123[3];
    u32 clockDomain;

    u32 ProximityDomainNumber() const
    {
        // (this is the apparent result of backwards compatibility, ugh.)
        u32 proximityDomainNumber;
        memcpy(&proximityDomainNumber, &proximityDomainNumber123[0]-1, sizeof(proximityDomainNumber));
        proximityDomainNumber &= ~0xFF;
        proximityDomainNumber |= proximityDomainNumber0;
        return proximityDomainNumber;
    }
};

struct AffinityMemory
{
    static const u8 type = 1;

    AffinityHeader header;
    u32 proximityDomainNumber;
    u16 reserved1;
    u64 baseAddress;
    u64 length;
    u32 reserved2;
    u32 flags;
    u64 reserved3;
};

// AffinityX2APIC omitted, since the APIC ID is sufficient for our purposes

// Static Resource Affinity Table
struct SRAT
{
    AcpiTable header;
    u32 reserved1;
    u8 reserved2[8];
    AffinityHeader affinities[1];
};

#pragma pack(pop)

template<class Affinity>
static const Affinity* DynamicCastFromHeader(const AffinityHeader* header)
{
    if(header->type != Affinity::type)
        return 0;

    // sanity check: ensure no padding was inserted
    ENSURE(header->length == sizeof(Affinity));

    const Affinity* affinity = (const Affinity*)header;
    if(!IsBitSet(affinity->flags, 0))   // not enabled
        return 0;

    return affinity;
}

struct ProximityDomain
{
    uintptr_t processorMask;
    // (AffinityMemory's fields are not currently needed)
};

typedef std::map<u32, ProximityDomain> ProximityDomains;

static ProximityDomains ExtractProximityDomainsFromSRAT(const SRAT* srat)
{
    ProximityDomains proximityDomains;

    for(const AffinityHeader* header = srat->affinities;
        header < (const AffinityHeader*)(uintptr_t(srat)+srat->header.size);
        header = (const AffinityHeader*)(uintptr_t(header) + header->length))
    {
        const AffinityAPIC* affinityAPIC = DynamicCastFromHeader<AffinityAPIC>(header);
        if(affinityAPIC)
        {
            const size_t processor = ProcessorFromApicId(affinityAPIC->apicId);
            const u32 proximityDomainNumber = affinityAPIC->ProximityDomainNumber();
            ProximityDomain& proximityDomain = proximityDomains[proximityDomainNumber];
            proximityDomain.processorMask |= Bit<uintptr_t>(processor);
        }
    }

    return proximityDomains;
}

static void PopulateNodesFromProximityDomains(const ProximityDomains& proximityDomains)
{
    for(ProximityDomains::const_iterator it = proximityDomains.begin(); it != proximityDomains.end(); ++it)
    {
        const u32 proximityDomainNumber = it->first;
        const ProximityDomain& proximityDomain = it->second;

        Node* node = FindNodeWithProcessorMask(proximityDomain.processorMask);
        if(!node)
            node = AddNode();
        // (we don't know Windows' nodeNumber; it has hopefully already been set)
        node->proximityDomainNumber = proximityDomainNumber;
        node->processorMask = proximityDomain.processorMask;
    }
}

#endif  // #if ARCH_X86_X64


//-----------------------------------------------------------------------------

static ModuleInitState initState;

static Status InitTopology()
{
    PopulateNodes();

#if ARCH_X86_X64
    const SRAT* srat = (const SRAT*)acpi_GetTable("SRAT");
    if(srat && AreApicIdsReliable())
    {
        const ProximityDomains proximityDomains = ExtractProximityDomainsFromSRAT(srat);
        PopulateNodesFromProximityDomains(proximityDomains);
    }
#endif

    // neither OS nor ACPI information is available
    if(numNodes == 0)
    {
        // add dummy node that contains all system processors
        Node* node = AddNode();
        node->nodeNumber = 0;
        node->proximityDomainNumber = 0;
        node->processorMask = os_cpu_ProcessorMask();
    }

    return INFO::OK;
}

size_t numa_NumNodes()
{
    (void)ModuleInit(&initState, InitTopology);
    return numNodes;
}

size_t numa_NodeFromProcessor(size_t processor)
{
    (void)ModuleInit(&initState, InitTopology);
    ENSURE(processor < os_cpu_NumProcessors());
    Node* node = FindNodeWithProcessor(processor);
    ENSURE(node);
    return nodes-node;
}

uintptr_t numa_ProcessorMaskFromNode(size_t node)
{
    (void)ModuleInit(&initState, InitTopology);
    ENSURE(node < numNodes);
    return nodes[node].processorMask;
}

static UCHAR NodeNumberFromNode(size_t node)
{
    (void)ModuleInit(&initState, InitTopology);
    ENSURE(node < numa_NumNodes());
    return nodes[node].nodeNumber;
}


//-----------------------------------------------------------------------------
// memory info

size_t numa_AvailableMemory(size_t node)
{
    // note: it is said that GetNumaAvailableMemoryNode sometimes incorrectly
    // reports zero bytes. the actual cause may however be unexpected
    // RAM configuration, e.g. not all slots filled.
    WUTIL_FUNC(pGetNumaAvailableMemoryNode, BOOL, (UCHAR, PULONGLONG));
    WUTIL_IMPORT_KERNEL32(GetNumaAvailableMemoryNode, pGetNumaAvailableMemoryNode);
    if(pGetNumaAvailableMemoryNode)
    {
        const UCHAR nodeNumber = NodeNumberFromNode(node);
        ULONGLONG availableBytes;
        const BOOL ok = pGetNumaAvailableMemoryNode(nodeNumber, &availableBytes);
        WARN_IF_FALSE(ok);
        const size_t availableMiB = size_t(availableBytes / MiB);
        return availableMiB;
    }
    // NUMA not supported - return available system memory
    else
        return os_cpu_MemoryAvailable();
}


#pragma pack(push, 1)

// ACPI System Locality Information Table
// (System Locality == Proximity Domain)
struct SLIT
{
    AcpiTable header;
    u64 numSystemLocalities;
    u8 entries[1];      // numSystemLocalities*numSystemLocalities entries
};

#pragma pack(pop)

static double ReadRelativeDistanceFromSLIT(const SLIT* slit)
{
    const size_t n = slit->numSystemLocalities;
    ENSURE(slit->header.size == sizeof(SLIT)-sizeof(slit->entries)+n*n);
    // diagonals are specified to be 10
    for(size_t i = 0; i < n; i++)
        ENSURE(slit->entries[i*n+i] == 10);
    // entries = relativeDistance * 10
    return *std::max_element(slit->entries, slit->entries+n*n) / 10.0;
}

// @return ratio between max/min time required to access one node's
// memory from each processor.
static double MeasureRelativeDistance()
{
    const size_t size = 32*MiB;
    void* mem = vm::Allocate(size);
    ASSUME_ALIGNED(mem, pageSize);

    const uintptr_t previousProcessorMask = os_cpu_SetThreadAffinityMask(os_cpu_ProcessorMask());

    double minTime = 1e10, maxTime = 0.0;
    for(size_t node = 0; node < numa_NumNodes(); node++)
    {
        const uintptr_t processorMask = numa_ProcessorMaskFromNode(node);
        os_cpu_SetThreadAffinityMask(processorMask);

        const double startTime = timer_Time();
        memset(mem, 0, size);
        const double elapsedTime = timer_Time() - startTime;

        minTime = std::min(minTime, elapsedTime);
        maxTime = std::max(maxTime, elapsedTime);
    }

    (void)os_cpu_SetThreadAffinityMask(previousProcessorMask);

    vm::Free(mem, size);

    return maxTime / minTime;
}

static double relativeDistance;

static Status InitRelativeDistance()
{
    // early-out for non-NUMA systems (saves some time)
    if(numa_NumNodes() == 1)
    {
        relativeDistance = 1.0;
        return INFO::OK;
    }

    // trust values reported by the BIOS, if available
    const SLIT* slit = (const SLIT*)acpi_GetTable("SLIT");
    if(slit)
        relativeDistance = ReadRelativeDistanceFromSLIT(slit);
    else
        relativeDistance = MeasureRelativeDistance();

    ENSURE(relativeDistance >= 1.0);
    ENSURE(relativeDistance <= 4.0);
    return INFO::OK;
}

double numa_Factor()
{
    static ModuleInitState initState;
    (void)ModuleInit(&initState, InitRelativeDistance);
    return relativeDistance;
}


static bool IsMemoryInterleaved()
{
    if(numa_NumNodes() == 1)
        return false;

    if(!acpi_GetTable("FACP"))  // no ACPI tables available
        return false;   // indeterminate, assume not interleaved

    if(acpi_GetTable("SRAT"))   // present iff not interleaved
        return false;

    return true;
}

static bool isMemoryInterleaved;

static Status InitMemoryInterleaved()
{
    isMemoryInterleaved = IsMemoryInterleaved();
    return INFO::OK;
}

bool numa_IsMemoryInterleaved()
{
    static ModuleInitState initState;
    (void)ModuleInit(&initState, InitMemoryInterleaved);
    return isMemoryInterleaved;
}


//-----------------------------------------------------------------------------

#if 0

static bool VerifyPages(void* mem, size_t size, size_t pageSize, size_t node)
{
    WUTIL_FUNC(pQueryWorkingSetEx, BOOL, (HANDLE, PVOID, DWORD));
    WUTIL_IMPORT_KERNEL32(QueryWorkingSetEx, pQueryWorkingSetEx);
    if(!pQueryWorkingSetEx)
        return true;    // can't do anything

#if WINVER >= 0x600
    size_t largePageSize = os_cpu_LargePageSize();
    ENSURE(largePageSize != 0); // this value is needed for later

    // retrieve attributes of all pages constituting mem
    const size_t numPages = (size + pageSize-1) / pageSize;
    PSAPI_WORKING_SET_EX_INFORMATION* wsi = new PSAPI_WORKING_SET_EX_INFORMATION[numPages];
    for(size_t i = 0; i < numPages; i++)
        wsi[i].VirtualAddress = (u8*)mem + i*pageSize;
    pQueryWorkingSetEx(GetCurrentProcess(), wsi, DWORD(sizeof(PSAPI_WORKING_SET_EX_INFORMATION)*numPages));

    // ensure each is valid and allocated on the correct node
    for(size_t i = 0; i < numPages; i++)
    {
        const PSAPI_WORKING_SET_EX_BLOCK& attributes = wsi[i].VirtualAttributes;
        if(!attributes.Valid)
            return false;
        if((attributes.LargePage != 0) != (pageSize == largePageSize))
        {
            debug_printf(L"NUMA: is not a large page\n");
            return false;
        }
        if(attributes.Node != node)
        {
            debug_printf(L"NUMA: allocated from remote node\n");
            return false;
        }
    }

    delete[] wsi;
#else
    UNUSED2(mem);
    UNUSED2(size);
    UNUSED2(pageSize);
    UNUSED2(node);
#endif

    return true;
}

#endif