topology.cpp

Go to the documentation of this file.

/* Copyright (c) 2011 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.
 */

/*
 * detection of CPU and cache topology
 */

#include "precompiled.h"
#include "lib/sysdep/arch/x86_x64/topology.h"

#include <bitset>

#include "lib/bits.h"
#include "lib/module_init.h"
#include "lib/sysdep/cpu.h" // ERR::CPU_FEATURE_MISSING
#include "lib/sysdep/os_cpu.h"
#include "lib/sysdep/numa.h"
#include "lib/sysdep/arch/x86_x64/x86_x64.h"
#include "lib/sysdep/arch/x86_x64/cache.h"
#include "lib/sysdep/arch/x86_x64/apic.h"

namespace topology {

//---------------------------------------------------------------------------------------------------------------------
// detect *maximum* number of cores/packages/caches.
// note: some of them may be disabled by the OS or BIOS.
// note: Intel Appnote 485 assures us that they are uniform across packages.

static size_t MaxCoresPerPackage()
{
    // assume single-core unless one of the following applies:
    size_t maxCoresPerPackage = 1;

    x86_x64::CpuidRegs regs = { 0 };
    switch(x86_x64::Vendor())
    {
    case x86_x64::VENDOR_INTEL:
        regs.eax = 4;
        regs.ecx = 0;
        if(x86_x64::cpuid(&regs))
            maxCoresPerPackage = bits(regs.eax, 26, 31)+1;
        break;

    case x86_x64::VENDOR_AMD:
        regs.eax = 0x80000008;
        if(x86_x64::cpuid(&regs))
            maxCoresPerPackage = bits(regs.ecx, 0, 7)+1;
        break;

    default:
        break;
    }

    return maxCoresPerPackage;
}


static size_t MaxLogicalPerCore()
{
    struct IsHyperthreadingCapable
    {
        bool operator()() const
        {
            // definitely not
            if(!x86_x64::Cap(x86_x64::CAP_HT))
                return false;

            // multi-core AMD systems falsely set the HT bit for reasons of
            // compatibility. we'll just ignore it, because clearing it might
            // confuse other callers.
            if(x86_x64::Vendor() == x86_x64::VENDOR_AMD && x86_x64::Cap(x86_x64::CAP_AMD_CMP_LEGACY))
                return false;

            return true;
        }
    };
    if(IsHyperthreadingCapable()())
    {
        x86_x64::CpuidRegs regs = { 0 };
        regs.eax = 1;
        if(!x86_x64::cpuid(&regs))
            DEBUG_WARN_ERR(ERR::CPU_FEATURE_MISSING);
        const size_t logicalPerPackage = bits(regs.ebx, 16, 23);
        const size_t maxCoresPerPackage = MaxCoresPerPackage();
        // cores ought to be uniform WRT # logical processors
        ENSURE(logicalPerPackage % maxCoresPerPackage == 0);
        const size_t maxLogicalPerCore = logicalPerPackage / maxCoresPerPackage;
        return maxLogicalPerCore;
    }
    else
        return 1;
}


static size_t MaxLogicalPerCache()
{
    return x86_x64::Caches(x86_x64::L2D)->sharedBy;
}


//---------------------------------------------------------------------------------------------------------------------
// CPU topology interface

// APIC IDs consist of variable-length bit fields indicating the logical,
// core, package and cache IDs. Vol3a says they aren't guaranteed to be
// contiguous, but that also applies to the individual fields.
// for example, quad-core E5630 CPUs report 4-bit core IDs 0, 1, 6, 7.
struct ApicField    // POD
{
    size_t operator()(size_t bits) const
    {
        return (bits >> shift) & mask;
    }

    size_t mask;    // zero for zero-width fields
    size_t shift;
};

struct CpuTopology  // POD
{
    size_t numProcessors;   // total reported by OS

    ApicField logical;
    ApicField core;
    ApicField package;

    // how many are actually enabled
    size_t logicalPerCore;
    size_t coresPerPackage;
    size_t numPackages;
};
static CpuTopology cpuTopology;
static ModuleInitState cpuInitState;

static Status InitCpuTopology()
{
    cpuTopology.numProcessors = os_cpu_NumProcessors();

    const size_t maxLogicalPerCore = MaxLogicalPerCore();
    const size_t maxCoresPerPackage = MaxCoresPerPackage();
    const size_t maxPackages = 256; // "enough"

    const size_t logicalWidth = ceil_log2(maxLogicalPerCore);
    const size_t coreWidth    = ceil_log2(maxCoresPerPackage);
    const size_t packageWidth = ceil_log2(maxPackages);

    cpuTopology.logical.mask = bit_mask<size_t>(logicalWidth);
    cpuTopology.core.mask    = bit_mask<size_t>(coreWidth);
    cpuTopology.package.mask = bit_mask<size_t>(packageWidth);

    cpuTopology.logical.shift = 0;
    cpuTopology.core.shift    = logicalWidth;
    cpuTopology.package.shift = logicalWidth + coreWidth;

    if(AreApicIdsReliable())
    {
        struct NumUniqueValuesInField
        {
            size_t operator()(const ApicField& apicField) const
            {
                std::bitset<os_cpu_MaxProcessors> values;
                for(size_t processor = 0; processor < os_cpu_NumProcessors(); processor++)
                {
                    const ApicId apicId = ApicIdFromProcessor(processor);
                    const size_t value = apicField(apicId);
                    values.set(value);
                }
                return values.count();
            }
        };

        cpuTopology.logicalPerCore  = NumUniqueValuesInField()(cpuTopology.logical);
        cpuTopology.coresPerPackage = NumUniqueValuesInField()(cpuTopology.core);
        cpuTopology.numPackages     = NumUniqueValuesInField()(cpuTopology.package);
    }
    else // processor lacks an xAPIC, or IDs are invalid
    {
        struct MinPackages
        {
            size_t operator()(size_t maxCoresPerPackage, size_t maxLogicalPerCore) const
            {
                const size_t numNodes = numa_NumNodes();
                const size_t logicalPerNode = PopulationCount(numa_ProcessorMaskFromNode(0));
                // NB: some cores or logical processors may be disabled.
                const size_t maxLogicalPerPackage = maxCoresPerPackage*maxLogicalPerCore;
                const size_t minPackagesPerNode = DivideRoundUp(logicalPerNode, maxLogicalPerPackage);
                return minPackagesPerNode*numNodes;
            }
        };

        // we can't differentiate between cores and logical processors.
        // since the former are less likely to be disabled, we seek the
        // maximum feasible number of cores and minimal number of packages:
        const size_t minPackages = MinPackages()(maxCoresPerPackage, maxLogicalPerCore);
        for(size_t numPackages = minPackages; numPackages <= cpuTopology.numProcessors; numPackages++)
        {
            if(cpuTopology.numProcessors % numPackages != 0)
                continue;
            const size_t logicalPerPackage = cpuTopology.numProcessors / numPackages;
            const size_t minCoresPerPackage = DivideRoundUp(logicalPerPackage, maxLogicalPerCore);
            for(size_t coresPerPackage = maxCoresPerPackage; coresPerPackage >= minCoresPerPackage; coresPerPackage--)
            {
                if(logicalPerPackage % coresPerPackage != 0)
                    continue;
                const size_t logicalPerCore = logicalPerPackage / coresPerPackage;
                if(logicalPerCore <= maxLogicalPerCore)
                {
                    ENSURE(cpuTopology.numProcessors == numPackages*coresPerPackage*logicalPerCore);
                    cpuTopology.logicalPerCore = logicalPerCore;
                    cpuTopology.coresPerPackage = coresPerPackage;
                    cpuTopology.numPackages = numPackages;

                    return INFO::OK;
                }
            }
        }

        DEBUG_WARN_ERR(ERR::LOGIC); // didn't find a feasible topology
    }

    return INFO::OK;
}


size_t NumPackages()
{
    ModuleInit(&cpuInitState, InitCpuTopology);
    return cpuTopology.numPackages;
}

size_t CoresPerPackage()
{
    ModuleInit(&cpuInitState, InitCpuTopology);
    return cpuTopology.coresPerPackage;
}

size_t LogicalPerCore()
{
    ModuleInit(&cpuInitState, InitCpuTopology);
    return cpuTopology.logicalPerCore;
}

size_t LogicalFromApicId(ApicId apicId)
{
    const size_t contiguousId = ContiguousIdFromApicId(apicId);
    return contiguousId % cpuTopology.logicalPerCore;
}

size_t CoreFromApicId(ApicId apicId)
{
    const size_t contiguousId = ContiguousIdFromApicId(apicId);
    return (contiguousId / cpuTopology.logicalPerCore) % cpuTopology.coresPerPackage;
}

size_t PackageFromApicId(ApicId apicId)
{
    const size_t contiguousId = ContiguousIdFromApicId(apicId);
    return contiguousId / (cpuTopology.logicalPerCore * cpuTopology.coresPerPackage);
}


ApicId ApicIdFromIndices(size_t idxLogical, size_t idxCore, size_t idxPackage)
{
    ModuleInit(&cpuInitState, InitCpuTopology);

    size_t contiguousId = 0;
    ENSURE(idxPackage < cpuTopology.numPackages);
    contiguousId += idxPackage;

    contiguousId *= cpuTopology.coresPerPackage;
    ENSURE(idxCore < cpuTopology.coresPerPackage);
    contiguousId += idxCore;

    contiguousId *= cpuTopology.logicalPerCore;
    ENSURE(idxLogical < cpuTopology.logicalPerCore);
    contiguousId += idxLogical;

    ENSURE(contiguousId < cpuTopology.numProcessors);
    return ApicIdFromContiguousId(contiguousId);
}


//---------------------------------------------------------------------------------------------------------------------
// cache topology

// note: Windows 2003 GetLogicalProcessorInformation provides similar
// functionality but returns incorrect results. (it claims all cores in
// an Intel Core2 Quad processor share a single L2 cache.)

class CacheRelations
{
public:
    /**
     * add processor to the processor mask owned by cache identified by <id>
     **/
    void Add(u8 cacheId, size_t processor)
    {
        SharedCache* cache = Find(cacheId);
        if(!cache)
        {
            m_caches.push_back(cacheId);
            cache = &m_caches.back();
        }
        cache->Add(processor);
    }

    size_t NumCaches() const
    {
        return m_caches.size();
    }

    /**
     * store topology in an array (one entry per cache) of masks
     * representing the processors that share a cache.
     **/
    void StoreProcessorMasks(uintptr_t* cachesProcessorMask)
    {
        for(size_t i = 0; i < NumCaches(); i++)
            cachesProcessorMask[i] = m_caches[i].ProcessorMask();
    }

private:
    /**
     * stores ID and tracks which processors share this cache
     **/
    class SharedCache
    {
    public:
        SharedCache(u8 cacheId)
            : m_cacheId(cacheId), m_processorMask(0)
        {
        }

        bool Matches(u8 cacheId) const
        {
            return m_cacheId == cacheId;
        }

        void Add(size_t processor)
        {
            m_processorMask |= uintptr_t(1) << processor;
        }

        uintptr_t ProcessorMask() const
        {
            return m_processorMask;
        }

    private:
        u8 m_cacheId;
        uintptr_t m_processorMask;
    };

    SharedCache* Find(u8 cacheId)
    {
        for(size_t i = 0; i < m_caches.size(); i++)
        {
            if(m_caches[i].Matches(cacheId))
                return &m_caches[i];
        }

        return 0;
    }

    std::vector<SharedCache> m_caches;
};

static void DetermineCachesProcessorMask(uintptr_t* cachesProcessorMask, size_t& numCaches)
{
    CacheRelations cacheRelations;
    if(AreApicIdsReliable())
    {
        const size_t numBits = ceil_log2(MaxLogicalPerCache());
        const u8 cacheIdMask = u8((0xFF << numBits) & 0xFF);
        for(size_t processor = 0; processor < os_cpu_NumProcessors(); processor++)
        {
            const ApicId apicId = ApicIdFromProcessor(processor);
            const u8 cacheId = u8(apicId & cacheIdMask);
            cacheRelations.Add(cacheId, processor);
        }
    }
    else
    {
        for(size_t processor = 0; processor < os_cpu_NumProcessors(); processor++)
        {
            // assume each processor has exactly one cache with matching IDs
            const u8 cacheId = (u8)processor;
            cacheRelations.Add(cacheId, processor);
        }
    }

    numCaches = cacheRelations.NumCaches();
    cacheRelations.StoreProcessorMasks(cachesProcessorMask);
}


static void DetermineProcessorsCache(const uintptr_t* cachesProcessorMask, size_t numCaches, size_t* processorsCache, size_t numProcessors)
{
    for(size_t cache = 0; cache < numCaches; cache++)
    {
        // write to all entries that share this cache
        const uintptr_t processorMask = cachesProcessorMask[cache];
        for(size_t processor = 0; processor < numProcessors; processor++)
        {
            if(IsBitSet(processorMask, processor))
            {
                ENSURE(processorsCache[processor] == 0);
                processorsCache[processor] = cache;
            }
        }
    }
}


//---------------------------------------------------------------------------------------------------------------------
// cache topology interface

struct CacheTopology    // POD
{
    size_t numCaches;
    size_t processorsCache[os_cpu_MaxProcessors];
    uintptr_t cachesProcessorMask[os_cpu_MaxProcessors];
};
static CacheTopology cacheTopology;
static ModuleInitState cacheInitState;

static Status InitCacheTopology()
{
    ModuleInit(&cpuInitState, InitCpuTopology);
    DetermineCachesProcessorMask(cacheTopology.cachesProcessorMask, cacheTopology.numCaches);
    DetermineProcessorsCache(cacheTopology.cachesProcessorMask, cacheTopology.numCaches, cacheTopology.processorsCache, os_cpu_NumProcessors());
    return INFO::OK;
}

size_t NumCaches()
{
    ModuleInit(&cacheInitState, InitCacheTopology);
    return cacheTopology.numCaches;
}

size_t CacheFromProcessor(size_t processor)
{
    ModuleInit(&cacheInitState, InitCacheTopology);
    ENSURE(processor < os_cpu_NumProcessors());
    return cacheTopology.processorsCache[processor];
}

uintptr_t ProcessorMaskFromCache(size_t cache)
{
    ModuleInit(&cacheInitState, InitCacheTopology);
    ENSURE(cache < cacheTopology.numCaches);
    return cacheTopology.cachesProcessorMask[cache];
}

}   // namespace topology