Windows进程CPU、内存等资源限制

Windows自身没有提供类似Linux cgroup的能力来限制进程或进程组的资源占用,进程CPU/IO/内存/网络等资源的控制只能由自己实现。目前已有第三方的实现,主要是限制进程CPU的占用,如文档 < 21 Best Ways to Limit the CPU Usage of a Process > 所描述的BES,Process Tamer等软件。自Windows 8及Server 2012开始Windows系统有提供以job为单位的CPU占用及内存上限设置,之前的版本则只能以进程或线程为单位进行限制。

进程CPU占用限制方案

即时轮询系统所有进程(线程)的CPU占用,当发现所设定进程有超标时强制暂停进程所有线程的执行,然后在适当的时机再恢复执行。其中所涉及技术点:

进程CPU占用查询 GetProcessTimes

BOOL GetProcessTimes(
  [in]  HANDLE     hProcess,
  [out] LPFILETIME lpCreationTime,
  [out] LPFILETIME lpExitTime,
  [out] LPFILETIME lpKernelTime,
  [out] LPFILETIME lpUserTime
);

此函数可以获取进程从创建至当前的总运行时间及总的CPU时间,(KernelTime + UserTime) < 系统CPU数 * (当前时间 - CreationTime)

线程CPU占用查询 GetThreadTimes

BOOL GetThreadTimes(
  [in]  HANDLE     hThread,
  [out] LPFILETIME lpCreationTime,
  [out] LPFILETIME lpExitTime,
  [out] LPFILETIME lpKernelTime,
  [out] LPFILETIME lpUserTime
);

QueryThreadCycleTime可以提供更精准的CPU时间数据,单位为CPU时钟周期

BOOL QueryThreadCycleTime(
  [in]  HANDLE   ThreadHandle,
  [out] PULONG64 CycleTime
);

线程暂停及恢复

Windows平台没有提供暂停整个进程的支持函数,只能以线程为单位来操作,即SuspendThread及ResumeThread:

DWORD SuspendThread(
  [in] HANDLE hThread
);
DWORD ResumeThread(
  [in] HANDLE hThread
);

CPU亲和性设置: SetProcessAffinityMask

BOOL SetProcessAffinityMask(
  [in] HANDLE    hProcess,
  [in] DWORD_PTR dwProcessAffinityMask
);

此函数可以限定进程及其所有线程所能使用的CPU,故一定程序上亦限定了进程最大的系统CPU占用率。

DWORD_PTR SetThreadAffinityMask(
  [in] HANDLE    hThread,
  [in] DWORD_PTR dwThreadAffinityMask
);

此函数可单独限制特定线程的CPU亲和性。

进程优先级设置: SetPriorityClass

优先级解决的是优先运行及退让CPU的问题,本质上并不能限定CPU占用,只是优先级高于当前任务的忙碌的时候,当前进程会主动退让CPU 线程优先级设置:SetThreadPriority

BOOL SetThreadPriority(
  [in] HANDLE hThread,
  [in] int    nPriority
);

Job Objects

Windows系统提供了Job的概念用以管理多个进程,可以限制Job对象内所有进程及期线程的CPU核心占用、CPU占用及内存分配上限等,均通过SetInformationJobObject来实现,具体的CPU限制由JOBOBJECT_CPU_RATE_CONTROL_INFORMATION管理,内存限制则由JOBOBJECT_EXTENDED_LIMIT_INFORMATION来管理。

BOOL SetInformationJobObject(
  [in] HANDLE             hJob,
  [in] JOBOBJECTINFOCLASS JobObjectInformationClass,
  [in] LPVOID             lpJobObjectInformation,
  [in] DWORD              cbJobObjectInformationLength
);

需要注意的是CPU占用设置只有Windows 8及Server 2012之后的版本有效。

CPU Sets

此部分只限定了CPU Affinity属性

实验验证

可以直接利用开源项目go-winjob验证,验证系统Windows 8 x64,go-winjob git repo: https://github.com/kolesnikovae/go-winjob

验证程序

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

void main(int argc, char *argv[])
{
        unsigned long total = 0, count = 0, i = 0;

        while (1) {
                if (malloc(1024)) {
                        total += 1024;
                        count++;
                }
                if (!(++i &amp; 4095))
                        printf(&quot;alloc: %u size: %u bytes\n&quot;, count, total);
    }
}

无限制

在无限制的情况下,此进程会占满一个CPU核心,commit内存总占用达2G CPUStress unlimited

单一进程

在设定CPU上限16%及内存16M上限之后,结果如下: CPUStress single process examples/job_object.go按如下修改:

var limits = []winjob.Limit{
        winjob.WithBreakawayOK(),
        winjob.WithKillOnJobClose(),
        winjob.WithActiveProcessLimit(3),
        winjob.WithProcessTimeLimit(10 * time.Second),
        winjob.WithCPUHardCapLimit(1600),        // 16%
        winjob.WithProcessMemoryLimit(16 &lt;&lt; 20), // 16MB
        winjob.WithWriteClipboardLimit(),
}

const defaultCommand = &quot;.\\CPUStress.exe&quot;

多进程(双进程)

将winjob.WithProcessMemoryLimit 改为 winjob.WithJobMemoryLimit,后者表示此job内所有进程要占用的总内存限制:

var limits = []winjob.Limit{
        winjob.WithBreakawayOK(),
        winjob.WithKillOnJobClose(),
        winjob.WithActiveProcessLimit(3),
        winjob.WithProcessTimeLimit(10 * time.Second),
        winjob.WithCPUHardCapLimit(1600),    // 16%
        winjob.WithJobMemoryLimit(16 &lt;&lt; 20), // 16MB
        winjob.WithWriteClipboardLimit(),
}

验证结果如下: CPUStress 2-processes CPUStress 2-processes

winjob example代码:

// +build windows

package main

import (
        &quot;encoding/json&quot;
        &quot;log&quot;
        &quot;os&quot;
        &quot;os/exec&quot;
        &quot;os/signal&quot;
        &quot;time&quot;

        &quot;golang.org/x/sys/windows&quot;

        &quot;github.com/kolesnikovae/go-winjob&quot;
)

var limits = []winjob.Limit{
        winjob.WithBreakawayOK(),
        winjob.WithKillOnJobClose(),
        winjob.WithActiveProcessLimit(3),
        winjob.WithProcessTimeLimit(10 * time.Second),
        winjob.WithCPUHardCapLimit(1600),    // 16%
        winjob.WithJobMemoryLimit(16 &lt;&lt; 20), // 16MB
        winjob.WithWriteClipboardLimit(),
}

const defaultCommand = &quot;.\\CPUStress.exe&quot;
const stressCommand  = &quot;.\\CPUStressX64.exe&quot;

func main() {
        job, err := winjob.Create(&quot;&quot;, limits...)
        if err != nil {
                log.Fatalf(&quot;Create: %v&quot;, err)
        }

        cmd := exec.Command(defaultCommand)
        cmd.Stderr = os.Stderr
        cmd.SysProcAttr = &amp;windows.SysProcAttr{
                CreationFlags: windows.CREATE_SUSPENDED,
        }
        if err := cmd.Start(); err != nil {
                log.Fatalf(&quot;Start: %v&quot;, err)
        }

        stress := exec.Command(stressCommand)
        stress.Stderr = os.Stderr
        stress.SysProcAttr = &amp;windows.SysProcAttr{
                CreationFlags: windows.CREATE_SUSPENDED,
        }
        if err := stress.Start(); err != nil {
                log.Fatalf(&quot;Start: %v&quot;, err)
        }

        s := make(chan os.Signal, 1)
        signal.Notify(s, os.Interrupt)

        c := make(chan winjob.Notification)
        subscription, err := winjob.Notify(c, job)
        if err != nil {
                log.Fatalf(&quot;Notify: %v&quot;, err)
        }

        done := make(chan struct{})
        go func() {
                defer close(done)
                ticker := time.NewTicker(time.Second * 5)
                defer ticker.Stop()
                var counters winjob.Counters
                for {
                        select {
                        case &lt;-s:
                                log.Println(&quot;Closing job object&quot;)
                                if err := job.Close(); err != nil {
                                        log.Fatal(err)
                                }
                                log.Println(&quot;Closing subscription&quot;)
                                if err := subscription.Close(); err != nil {
                                        log.Fatal(err)
                                }
                                return

                        case n, ok := &lt;-c:
                                if ok {
                                        log.Printf(&quot;Notification: %#v\n&quot;, n)
                                } else if err := subscription.Err(); err != nil {
                                        log.Fatalf(&quot;Subscription: %v&quot;, err)
                                }

                        case &lt;-ticker.C:
                                if err := job.QueryCounters(&amp;counters); err != nil {
                                        log.Fatalf(&quot;QueryCounters: %v&quot;, err)
                                }
                                b, err := json.MarshalIndent(counters, &quot;&quot;, &quot;\t&quot;)
                                if err != nil {
                                        log.Fatal(err)
                                }
                                log.Printf(&quot;Counters: \n%s\n&quot;, b)
                        }
                }
        }()

        if err := job.Assign(cmd.Process); err != nil {
                log.Fatalf(&quot;Assign: %v&quot;, err)
        }
        if err := winjob.Resume(cmd); err != nil {
                log.Fatalf(&quot;Resume: %v&quot;, err)
        }

        if err := job.Assign(stress.Process); err != nil {
                log.Fatalf(&quot;Assign: %v&quot;, err)
        }
        if err := winjob.Resume(stress); err != nil {
                log.Fatalf(&quot;Resume: %v&quot;, err)
        }

        if err := cmd.Wait(); err != nil {
                log.Fatalf(&quot;Wait: %v&quot;, err)
        }
        if err := stress.Wait(); err != nil {
                log.Fatalf(&quot;Wait: %v&quot;, err)
        }

        // Wait for a signal.
        &lt;-done
}

参考链接

  1. 21 Best Ways to Limit the CPU Usage of a Process
  2. MSDN: Windows Process and Thread Functions
  3. MSDN: CPU Sets
  4. GetThreadTimes

Cache相联度测量

从上篇文章中我们得知Cache在兼顾性能及成本后都是设计成组相联方式的,以Intel Pentinum G5500T为例:L1是8路组相联,L2是4路组相联,LLC是16路组相联。针对一款未知CPU,可以通过cpuid指令来查询到以上信息,但我们的目标是通过内存访问延时的度量来测算出每级Cache的相联度。

测量方法

测量的原理是尝试制造“相联度冲突”强制触发CacheLine的驱逐(Evict),以此来推算出Cache的相联度。参见下图: Cache 相联度测量方法

这里我们先将整个测试内存块分成不同数量的Window大小,然后以Window为间隔进行跳跃式的访问,为此分别构造两个指针链,第一条指针链是左图所示的每个Cache Line的第一个DWORD(或QWORD),右图则是第二指针链,将每个Cache Line的最后一个DOWRD(或QWORD)串联起来。测量过程分为两步预热和度量:先通过第一条链的访问达成Cache的预热(从内存加载至Cache),然后度量遍历第二条链的访问时间。

如果所有Window的内存块均在Cache中,将不会发生冲突,此时的延时将是最短的。如果不断增加Window的数量(即相联度)的话,必然在超过Cache所设计的相联度之后发生冲刷效应,如L1 Cache是8路组的,就是说可容纳8个来自不同页面的Cache Line,如果再访问第9个内存页的话,CPU将不得不驱逐一个Cache Line,从而导致度量第二条指针链时访问延时的增加。

测量结果

Cache 相联度测量结果

1,水平方向基本呈现4个台阶,分别对应不同的访问速度,但并不严格对应L1/L2/L3和内存,因为每次测量都是混合访问的结果,即L1、L2、L3或内存都有访问,但各自的比率不同,Cache的命中率越高延时越低,即垂直方向上高度越低

2,先以1K的步长来分析,1K应该一直在最低台阶上,然后在X轴32处时间跳跃,说明L1 的Cache Size为32K,当探测组数超过32组时会发生挤出效应,同理2K/4K分别是16组及8组的探测位置出现分叉

3,打32K的第一个分叉点:8,这时说明以32K为步长的话,同时访问超过8组的话会导致时延变长,直接跳到了最高台阶,说明L1 Cache是8路分组的

4,从第二个台阶水平 ,从最右边向最左分别找到32 8K及16 16K两个分叉点,即256K的容量

5,然后以256K的线从最左侧向右寻找跃升点,分别在4和8的位置跃升,说明L2是4路分组的。那为什么会在8的位置也出现跃升呢?大家可以自己想一想

特殊的LLC

从上图中来看L3,疑似L3的台阶从右向左只在256K的线发生了跃升,跃升点是32,即32 * 256K = 4M; 然后再找4M的线,结果4M的线只在4和8点有跃升,然后一直平稳在L3的台阶上。8M的线亦同样,与L1及L2相对呈现出了不同的规律。

其实原因在于L3即LLC采用了不同的分组hash计算方式及不同的替换策略,以致当前的探测方式不再适用。但我们依然可以做个猜测,比如 32K、64K、128K的直接越过了L3,说明了什么问题?当32K、64K、128K超过8组的时就已经超出了L3的组容量,即产生了挤出效应,从而造成了直接内存访问的局面。关于LLC的映射算法及替换策略可以参见文末的参考链接,等后续有时间我再进行详细解读。

参考链接

Cache与内存的映射

1. 理解Cache Line

在大家印象中Cache Line就是一个数据块,能有什么理解难度呢?不妨再反问一下自己:真的是这样吗?

上篇文章中就说到Cache本身的容量远远小于内存容量,CPU为了能正确定位数据所在的CacheLine还需要做很多工作。简单来说可以将Cache Line理解成一个带标签的存储槽,下面以一个直观的例子来说明:

小A同学坐在座位上,如果老师想检查小A的作业的话就需要先定位到小A所在的座位号,然后再从小A的座位上拿到小A作业本。在这个例子中,小A的作业本就对应Cache Line中的数据,老师就是CPU Core,小A其实对应着内存地址(TAG),小A的座位就是Cache Line本身,而座位号就是Cache Line在Cache中的位置(索引,Index),教室里所有的座位就可以理解为整个Cache,而学校里所有的学生则是全部的系统内存。 Cache Flags

上图就是Cache的内部组织,除了TAG和数据外,还有两个标志位,V表示此CacheLine中的数据是否是有效的,即座位上有没有学生,D表示CacheLine中的数据有没有被修改过,修改过的数据是不能直接清除的,需要写回到主存(内存)。

2. Cache与内存的映射

映射方式有3种:

  1. 直接映射 (Direct Mapping)
  2. 组相联 (K-Way Set Associative Mapping)
  3. 全相联 (Full Associative Mapping)

2.1 全相联

继续以学生和座位为例,正常情况下我们并不限定位置,大家随便坐,先到先得。老师如果想检查一个同学的作业的话,也可以一个一个来找,即线性搜索,当然此举必然花费老师很多时间。另外一点需要强调,学生并不是老老实实坐在座位上的,不断会有学生进来或离开,也会有同学出去后又进来但前后的坐位并不相同的情况,这样的话“线性搜索”将不再可能。

想像最常见的一个场景,老师并不会主动来找,而是直接喊这个同学的学号(名字可能会有重名,但学号不会),所有的学生在听到名字后同时判断老师叫的是不是自己,只有被叫到的同学才会应答。在听到老师的请求后所有的学生同时并行判断的动作,对应于CPU及硬件实现就是一个并行的比较电路,而比较的内容则是座位上的同学和老师叫的学号,分别对应着TAG和内存地址。

这个例子中的随机编排座位的方式就是全相联映射。全相联映射方式的定位操作是最高效的,但是硬件成本亦最高,毕竟要实现复杂的并行比较电路,只有容量较小且对性能至关重要的缓存才会使用,如CPU的内存管理单元 (MMU, Mmemory Management Unit) 的TLB缓存 (Translation Lookaside Buffer),TLB中存放的是虚拟地址与物理地址的1:1的转换关系。

2.2 直接映射

假设上面例子中的教室只有20个座位,编号为0-19,全校共有400名学生,学号分别为0-399。直接映射方式的求是座位不能随便选择,而是通过学号和所有座位数的余数决定,即学号为0、20、40、60...的同学只能坐在0号座位上,同样学号为1、21、41、61...的同学只能争1号座位,后来的同学会将正坐在位置上的同学挤出去,如果1号和21号同学都要来教室的话就会发生两人不断被挤出去的情况,这就是Cache的颠簸效应(Cache Thrashing)。

2.3 组相联

为了解决直接映射的颠簸效应,遂引入了组相联映射。假设学校共有5个系,每个系均有80名学生,那我们可以这样安排座位,一系的学生只能选择0/5/10/15这4个座,二系则是1/6/11/16,依次类推,如下图所示:每个系有4个座位,这4个座位是没有顺序的,即本系的学生随意坐,但全系的80名学生将争抢这4个座位,这种分为5组的映射方式就是4路组相连映射,4路的意思是每组中有4个座位,即4个CacheLine。现实中CPU Cache无论是组数还是相联度(路)均是2的幂指数,不会出现本例中奇数5的情形。 Cache Groups 直接映射方式其实是组相联映射的一种特例,亦称作是单路组相联。

2.4 特别说明

更详细的阐述可参考链接1 [蜗窝科技: 浅谈Cache Memory],作者smcdef通过举例来说明三种方式的实现细节,作图精美,本文不再做过多说明。

3. Cache的分类及访问流程

目前主流的CPU,如Intel及AMD的桌面或服务器平台的CPU都是支持分页的,即物理内存的管理是以页划分和管理的。X86平台的页大小通常是4K,即4096字节。CPU层所操作的内存地址称作是虚拟地址(逻辑地址),并不是物理的内存地址,从虚拟地址至物理地址的翻译由硬件MMU来执行。Cache与MMU的位置关系直接决定了Cache的分类:如果Cache相对MMU离CORE的距离更近,则此类Cache被称作为逻辑Cache;相反则称作是物理Cache。下图是L1、L2及LLC与MMU的关系,L1是集成在CORE内部的,所以可以得出L1是逻辑Cache,而L2和LLC则是物理Cache。

Memory Paging & Addressing

如果再加上TAG的取值,取物理地址或虚拟地址,又可以组合成4种情况:

3.1. PIPT (Physically Indexed Virtually Tagged)

下图是2路组相联的PIPT的示例,CacheLine大小为64字节,即6个比特,组索引(SET)由S个比特来编址,剩余的部分即为标签项(TAG),CPU通过组索引来定位此地址所在Cache组,然后通过两组比较电路进行TAG值的并发比较,然后即可确定Cache所在位置,当然也有可能出现没有命中的情况。 Cache PIPT} L2及LLC,以及早期的CPU的L1均是使用PIPT的方式,这是因为内存的物理地址是唯一的,这就大大简单化PIPT的实现逻辑。

3.2. VIVT (Virtually Indexed Virtually Tagged)

VIVT的Index和Tag均使用虚拟地址,全程不需要MMU的参与,是性能最好的定位方式,但是由于虚拟地址的特性会导致歧义和别名的问题,最终决定了VIVT方式的不可行:

歧义 (Ambiguity,亦称Homonyms问题):不同的进程拥有相同的虚拟地址空间,虚拟化平台上不同的虚拟机亦是同样的情况。从而会导致相同的虚拟地址(不同进程或不同虚拟机)所对应的物理页面不同的,VIVT的方式将不能正确区分。

别名 (Alias):是指同一个物理页映射至不同的虚拟地址,即同一个物理地址将有多个虚拟地址的别名。多个别名的情况下VIVT将会映射至不同的CacheLine,将不能保证数据的一致性。

3.3. VIPT (Virtually Indexed Physically Tagged)

CPU层的指令所操作的均是虚拟地址,使用虚拟地址作为索引来直接进行Cache的定位不必经过MMU的转换。此时Cache Set的定位和MMU的转换过程是并发的,定位到指定Cache Set之后再进行两个Cache Line的Tag的对比,此时两个Tag的比对也是并行处理的。 Cache VIPT}

3.4. PIVT (Physically Indexed Virtually Tagged)

PIVT方式相比PIPT和VIPT来说没有任何优势,性能上必须等MMU转换完成之后,而且在数据一致性上无法处理好别名问题。

4. L1 Cache (VIPT)的别名问题

在Cache与内存的映射关系上,考虑到成本及性能,多采用组相联方式;在CacheLine的定位和访问方式上,L1 Cache多是VIPT,而L2及LLC是PIPT。以Intel Pentinum G5500T为例:L1是8路组相联,大小为32K; L2是4路组相联,大小为256K;LLC即L3则是16路组相联,大小为4M。

L1采用的是VIPT映射方式,虽然VIPT方式通过物理地址TAG解决了歧义的问题,但别名的问题依然存在,是怎样解决的呢?

实际上L1 Cache的每个Cache Set的数量正好限定在 (PAGE_SIZE/CACHE_LINE) 之内的,以G5500T为例,32K/(8*64) = 4K/64 = 64。虚拟地址最低6位为CacheLine中的偏移;位6-11共6位是组索引,6+6正好是12,即一个4K PAGE的大小,从而可推论出不管虚拟地址是多少,任意内存页面的固定偏移总是映射到相同的Cache Set中,而TAG的选择正是物理地址中的是12-47,可以理解为PFN,即每一个物理页面的唯一帧号,所以同一物理页的不同的虚拟地址最终将定位到同一个Cache Set中的同一个Cache Line上。

L1是8路组相联的,也就是说一个Cache Set中容纳了8个Cache Line,由上面的结论可得出:这8个Cache Line将分别来自于不同的物理页。最后大家不妨想一个问题,如果要将L1 Cache从32K增加到64K的话,怎样构造L1的相联度及Cache Set组数才是合理的?有多少种组合?

5. 参考连接

Cache为什么能提升性能

1. Cache的容量设计

上篇文章中介绍到CPU Cache是分级的,L1 Cache是集成在Core内部的,L2则是紧贴着Core,而L3是多个Core共享的。离Core(流水线)越近的分级速度越快,但容量也更小,并且造价愈贵。Cache的实现采用了高速的SRAM电路 (静态随机存取存储器: Static Random-Access Memory),SRAM相对DRAM (动态随机存取存储器: Dynamic Random Access Memory)要复杂和庞大的多,即使不考虑成本能做到无限增大,但因为电路复杂度的提升其性能即访问速度必然会下降,另外也会使得CPU的面积急速膨胀。最终,CPU的每一级Cache的容量都是在设计之初考虑各方面因素折中后的结果(trade-off)。下图是AMD Zen的CCX的die shot[来源:1. Zen - Microarchitectures - AMD],从图中我们就能看中L2及L3 Cache占据了很大一部分的面积: AMD ZEN die shot

一般而言L1 Cache约几十K,L2则是几百K,L3是几M或几十、几百M,但相比较内存动不动几十G的大小来说还是小了太多,根本不在一个数量级上。那么问题来了:Cache容量比内存小了太多,为什么根本不在一个数据量级的Cache能够大副度提升系统性能?

2. 局部性原理 (Principle of Locality)

简言之,程序倾向于访问(或执行)刚刚访问过的数据(执行过的指令)或与之相临近的数据(指令)

2.1 时间局部性 (Temporal locality):

刚刚被访问的地址(数据)在未来有很大的可能性被再次访问,即用过的数据可能会再次被用到

2.2 空间局部性 (Spatial locality):

刚刚被访问的地址的临近位置在未来有很大的可能被访问,以数组D[]为例,当前访问的是D[i],那么D[i+1]有很大的可能将被访问

2.3 算法局部性:

程序代码也遵守2/8法则,即帕累托法则(Pareto principle,亦称关键少数法则),80%的时间都是在执行20%的代码

正是因为局部性原理,少量的Cache大大减少了数据的访问延迟,从而提升了整体性能。

3. Cache的放大效应

先来考虑一个问题:Cache命中率(Cache Hit) 99%与98%的差别会有多大?从数值上来看二者本身仅相差1%,性能上最终能有多大差别呢?

假设命中L1的延时为4 cycles,不命中的话需要从内存中读取数据的延时为150 cycles,那么: 99%命中率的情况: 0.99 4 + 0.01 150 = 5.46 98%命中率的情况: 0.98 4 + 0.02 150 = 6.92

后者比前者的延时多了(6.92 - 5.46) / 5.46 = 26.7% 之多。换成95%的命中率的话,延时将高达99%命中率时的一倍之多。由此看来,不命中(Cache Miss)所带的性能惩罚巨大,这也预示了未来Cache发展的趋势,即容量将越来越大,拥有GB级Cache容量的CPU将指日可待,另外增加L4分级也将是不可避免的,有兴趣的读者可进一步参阅 [2. The Next Platform: Cache Is King]。

4. Cache Miss的原因

前面说了Cache Miss的惩罚,下面说一下会导致Cache Miss的因素,可以简单归纳为3C:

  1. Cold (Compulsory) Miss: 第一次访问数据时,数据根本不在Cache中
  2. Conflict Miss: 因冲突导致Cache Line被驱逐出Cache,上一篇文章中提到了相关的方法,如Evict(驱逐)、Prime(装填)等,当然冲突所导致的Cache Miss只针对组相联的Cache结构(直接映射可以认为是单路组相联),而全相联的Cache结构是没有Conflict Miss的,后续还会针对此课题做详细的介绍
  3. Capacity Miss: Cache的容量毕竟有限,如果程序确实需要密集访问大量内存时,Cache必然是不够的

在指定的CPU硬件上如果想提升Cache Hit的话就要从这几个因素上着手,如通过硬件预取以减少Cold Miss,通过程序算法改进及结构重组可减少2和3所带来的Cache Miss的发生概率,本文先点到为止,后面将进行详细拆解。

5. 参考资料

  1. wikichip: Zen - Microarchitectures - AMD
  2. The Next Platform: Cache Is King

CPU Cache测量方法

通过上一篇文章《通过TSC观察CPU》知道了可以通过TSC来测量CPU的内部行为,本文将介绍CPU Cache的结构及几种常用的测量手法:

Cache的分级结构

Memory & Cache的分级结构

  • Cache 是分级的:一般分为3级,较老的CPU如Core 2 Duo只有2级。L1是集成是core内部的,指令与数据Cache是分离的,好L1C和L1D;L2是紧贴core的;L3是多核共享的,每个core有自己的Slice,通过Ring Bus或Mesh结构互联互访
  • Cache以Cache Line为访问单位,即Cache及内存的访问是以块为单位的,而不是字节单位。较新的X86 CPU的Cache Line一般是64字节。上一篇文章通过TSC观察CPU曾注意到一个有趣的测量结果:X86程序访问一个1字节与访问2个、4个及8个字节的延进均为31个指令周期,并不是线性增长的,就是这个原因
  • 层级包含与否由CPU实现决定:L2一般都是包含L1的全部内容的,L3可以是Non-inclusive,也可以是Exclusive。Intel的CPU一般是包含的,但AMD的Zen系列CPU的L3就是定义为L1/L2的Victim Cache,Victim是指从L1及L2中移除的Cache项
  • Cache自身的构造采用“组相联”方式

Cache不同分级的性能

Memory & Cache性能数据

在上图中看到Cache是分级的,用不同级的访问速度有很大不同,故我们可以通过制造冲突或直接Flush Cache的方式将数据从Cache中清除,从而通过前后内存访问的时间差来进行判定。

测量方法

制造冲突以清除Cache的常用手段有以下几种【参阅 1:Cache side channel attacks: CPU Design as a security problem by Anders Fog]】:

  1. Evict (驱逐) + Time (测量) : 通过制造冲突以达成被测量目标数据从cache中清除的目的
  2. Prime (装填) + Probe (探测) :与1)方法一样,只是作用对象是反的
  3. Flush (冲刷) + Reload (加载) ) :最主动和最快的办法,直接利用clflush指令刷新,然后再读取内存,此时会发生Cache Miss事件。
  4. Flush (冲刷) + Flush (冲刷) ) :与3)类似,但测量的是clflush指令针对数据在不在cache中的执行周期的不同 在条件许可的情况下,尽量采用第3种,即最快的办法。

实例:Flush + Reload

Flush即clflush指令,Visual C++中定义如下:

        extern void _mm_clflush(void const*_P);

测量代码:

        /* flush */
        _mm_clflush(&amp;data[0]);

        /* measure cache miss latency */
        ts = rdtscp(&amp;ui);
        m |= data[0];
        te = rdtscp(&amp;ui);

实战:Cache Line的测量

原理: Cache性能测量方法

结论: Cache性能结果

从图中我们可以看到64字节是一个明显的分界点。

硬件预取: Hardware Prefetcher

如果你在自己的电脑上进行测试,你看到的可能不是上图所示的样子,很大的可能如下图所示,明显的分界点不是64字节而是128字节: Cache性能结果

这是因为硬件预取即HWPrefetcher的缘故,并且硬件预取默都是开启的。硬件预取功能会在每次Cache Miss的情况下多读一个Cache Line,可以理解为每次读取两个Cache Line即64 * 2 = 128字节,但数据并不是同时到达的,第二个Cache Line的数据的到达周期会晚些,这也是为什么在128这个点上的延时会比64高。 CPU Cache Prefetcher

如何关闭硬件预取:

  1. 通过BIOS设置: 通过BIOS选项来关闭hwprefetcher,对所有的CPU生效
  2. 通过内核调试器windbg直接关闭:通过直接改写msr寄存器关闭当前核的硬件预取功能:
    0: kd&gt; rdmsr 0x1a4
    msr[1a4] = 00000000&#x60;00000000
    0: kd&gt; wrmsr 0x1a4 0x0f
    0: kd&gt; ~1
    1: kd&gt; rdmsr 0x1a4
    msr[1a4] = 00000000&#x60;00000000
    1: kd&gt; wrmsr 0x1a4 0x0f
    1: kd&gt; rdmsr 0x1a4
    msr[1a4] = 00000000&#x60;0000000f
    1: kd&gt; ~0

实战:Cache不同分级的访问延时测量

如果我们以更大的的stride进行同样的测试则可以测量出Cache每一级的大小,即L1D,L2,LLC和内存访问的延时。下图中我们分别以1K、2K,直至64M的stride测量出来结果: Cache性能结果 可以看到整个曲线有4个平台,分别表示L1D、L2、LLC和内存。L1D的大小为32K,L2为256K,这部分和CPUZ的输出是一致的。 但第三个平台包含了512K、1M及2M,从4M开始延进有明显的跃升,从8M之后基本稳定在高位。这里就涉及到了LLC组织的不同:L1D及L2 Cache都是与物理核(Core)绑定的,而LLC是绑定CPU的,即2核的CPU的两个核心会共享同一个LLC,整个LLC是平均分配给每个核的,然后每个核心的LLC通过Ring Bus互联,即每个核又可以访问所有的LLC。这里在4M的stride发生波动的原因有两个:

  1. 当前运行测量程序的CPU核心用尽自己的LLC后会通过Ring Bus竞争访问另一个核心的LLC
  2. 测量程序运行时整个操作系统也在运行,所以整个系统均会竞争使用LLC,必然会带来挤出效应,从而增大了延时

参考资料

  1. CSCA: Cache side channel attacks: CPU Design as a security problem by Anders Fogh
  2. HWPF: Disclosure of Hardware Prefetcher Control on Some Intel® Processors
  3. SourceCode: CacheLatency Github Repo

通过TSC观察CPU

自Pentium开始x86 CPU均引入TSC了,可提供指令级执行时间度量的64位时间戳计数寄存器,随着CPU时钟自动增加。

CPU指令:

rdtsc: Real Time-Stamp Counter rdtscp: Real Time-Stamp Counter and Processor ID

调用:

Microsoft Visual C++:

unsigned __int64 __rdtsc();
unsigned __int64 __rdtscp( unsigned int * AUX );

Linux & gcc :

extern __inline unsigned long long
__attribute__((__gnu_inline__, __always_inline__, __artificial__))
__rdtsc (void) {
  return __builtin_ia32_rdtsc ();
}
extern __inline unsigned long long
__attribute__((__gnu_inline__, __always_inline__, __artificial__))
__rdtscp (unsigned int *__A)
{
  return __builtin_ia32_rdtscp (__A);
}

示例:

1: L1 cache及内存的延迟测量:

代码:

{
    ......
    /* flush cache line */
    _mm_clflush(&amp;data[0]);

    /* measure cache miss latency */
    ts = rdtscp(&amp;ui);
    m |= data[0];
    te = rdtscp(&amp;ui);
    CALC_MIN(csci[0], ts, te);

    /* measure cache hit latency */
    ts = rdtscp(&amp;ui);
    m &amp;= data[0];
    te = rdtscp(&amp;ui);
      /* flush cache line */
    _mm_clflush(&amp;data[0]);

    /* measure cache miss latency */
    ts = rdtscp(&amp;ui);
    m |= data[0];
    te = rdtscp(&amp;ui);
    CALC_MIN(csci[0], ts, te);

    /* measure cache hit latency */
    ts = rdtscp(&amp;ui);
    m &amp;= data[0];
    te = rdtscp(&amp;ui);
    CALC_MIN(csci[1], ts, te);
    CALC_MIN(csci[1], ts, te);
}

结果:

rdtscp指令自身耗时:X86: 31 X64: 33

架构 X86 X64
长度 BYTE WORD DWORD QWORD BYTE WORD DWORD QWORD
冷:内存 244 241 246 250 254 254 260 261
热:L1 31 31 31 31 35 35 35 35

问题:读取1个字节与8个字节的所用的时间是一样的,为什么?

2: 常见整型运算及多条指令执行周期:

代码:

{
    ......
    /* measure mul latency */
    ts = rdtscp(&amp;ui);
    m *= *((U32 *)&amp;data[0]);
    te = rdtscp(&amp;ui);
    CALC_MIN(csci[2], ts, te);

    /* measure div latnecy */
    ts = rdtscp(&amp;ui);
    m /= *((U32 *)&amp;data[0]);
    te = rdtscp(&amp;ui);
    CALC_MIN(csci[3], ts, te);

    /* measure 2*mul latnecy */
    ts = rdtscp(&amp;ui);
    m *= *((U32 *)&amp;data[0]);
    m *= *((U32 *)&amp;data[0]);
    te = rdtscp(&amp;ui);
    CALC_MIN(csci2[0], ts, te);

    /* double div */
    ts = rdtscp(&amp;ui);
    m /= *((U32 *)&amp;data[0]);
    m /= *((U32 *)&amp;data[0]);
    te = rdtscp(&amp;ui);
    CALC_MIN(csci2[1], ts, te);

    /* mul + div */
    ts = rdtscp(&amp;ui);
    m *= *((U32 *)&amp;data[0]);
    m /= *((U32 *)&amp;data[0]);
    te = rdtscp(&amp;ui);
    CALC_MIN(csci2[2], ts, te);

    /* measure float mul latency */
    ts = rdtscp(&amp;ui);
    f = f * m;
    te = rdtscp(&amp;ui);
    CALC_MIN(csci[4], ts, te);

    /* measure float div latency */
    while (!m)
        m = rand();
    ts = rdtscp(&amp;ui);
    f = f / m;
    te = rdtscp(&amp;ui);
    CALC_MIN(csci[5], ts, te);
}

结果:

指令周期
数据类型 整型 浮点数
指令组合 m* m/ m, m m, n m/, m/ m/, n/ m*, m/ f* f/
指行时间 2 20 4 4 48 26 24 17 26

问题:m及n的除法运算的耗时只比m的除法多了一点,但却明显少于m的两次除法,为什么?

注意事项:

  1. 考虑到CPU乱序执行的问题,rdtsc需要配合cpuid或lfence指令,以保证计这一刻流水线已排空,即rdtsc要测量的指令已执行完。后来的CPU提供了rdtscp指令,相当于cpuid + rdtsc,但cpuid指令本身的执行周期有波动,而rdtscp指令的执行更稳定。不过rdtscp不是所有的CPU都支持,使用前要通过cpuid指令查询是不是支持: 即CPUID.80000001H:EDX.RDTSCP[bit 27]是不是为1
  2. 多核系统:新的CPU支持了Invariant TSC特性,可以保证在默认情况下各核心看到的TSC是一致的,否则测量代码执行时不能调度至其它核心上。另外TSC是可以通过MSR来修改的,这种情况下也要注意: Invariant TSC: Software can modify the value of the time-stamp counter (TSC) of a logical processor by using the WRMSR instruction to write to the IA32_TIME_STAMP_COUNTER MSR
  3. CPU降频问题:第一代TSC的实现是Varient TSC,没有考虑到降频的问题,故在低功耗TSC计数会变慢,甚至停止;后来又有了Constant TSC,解决了降频的问题,但在DEEP-C状态下依然会发生停止计数的情况,所以又有了最新的Invariant TSC的特性: The time stamp counter in newer processors may support an enhancement, referred to as invariant TSC. Processor’s support for invariant TSC is indicated by CPUID.80000007H:EDX[8]. The invariant TSC will run at a constant rate in all ACPI P-, C-. and T-states. This is the architectural behavior moving forward. On processors with invariant TSC support, the OS may use the TSC for wall clock timer services (instead of ACPI or HPET timers). TSC reads are much more efficient and do not incur the overhead associated with a ring transition or access to a platform resource.
  4. 指令本身的时间开销 Pentinum Gold G5500T: 31 cycles Core i7-7820HQ: 25 cycles
  5. 权限问题(此指令可用于时序攻击,如Meltdown及Spectre): CR4.TSD: Time Stamp Disable (bit 2 of CR4) — Restricts the execution of the RDTSC instruction to procedures running at privilege level 0 when set; allows RDTSC instruction to be executed at any privilege level when clear. This bit also applies to the RDTSCP instruction if supported (if CPUID.80000001H:EDX[27] = 1).
  6. 计数器溢出可能:计算器本身是64位的,即使是主频4G的CPU,也要100多年才会溢出,对于我们的测量来说可以不用考虑
  7. 时序测量容易被干扰(线程调度、抢占、系统中断、虚拟化等),要求测量的指令序列尽量短,并且需要进行多次测量