讯享网

                <p class="f_center">　　<img src="http://dingyue.ws.126.net/2021/0708/ca054e53g00qvx8qd000hd200hs0028g00hs0028.gif"/><br/><br/></p><p>　　There are only two hard things in Computer Science: cache invalidation and naming things.</p><p>　　-- Phil Karlton</p><p>　　作者 | 宋宝华 责编 | 张红月<br/></p><p>　　出品 | Linux 阅码场</p><p>　　<strong>CACHE 基础</strong><br/></p><p>　　对cache的掌握，对于Linux工程师（其他的非Linux工程师也一样）写出高效能代码，以及优化Linux系统的性能是至关重要的。简单来说，cache快，内存慢，硬盘更慢。在一个典型的现代CPU中比较接近改进的哈佛结构，cache的排布大概是这样的：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fc139117cp00qvx8qe0003d200gq004qg00gq004q.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　L1速度&gt; L2速度&gt; L3速度&gt; RAM</p><p>　　L1容量&lt; L2容量&lt; L3容量&lt; RAM</p><p>　　现代CPU，通常L1 cache的指令和数据是分离的。这样可以实现2条高速公路并行访问，CPU可以同时load指令和数据。当然，cache也不一定是一个core独享，现代很多CPU的典型分布是这样的，比如多个core共享一个L3。比如这台的Linux里面运行lstopo命令：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fa5b61acap00qvx8qe000kd200cr00aog00cr00ao.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　人们也常常称呼L2cache为MLC（MiddleLevel Cache）,L3cache为LLC（Last LevelCache）。这些Cache究竟有多快呢？我们来看看Intel的数据，具体配置：Intel i7-4770 (Haswell), 3.4 GHz (Turbo Boostoff), 22 nm. RAM: 32 GB (PC3-12800 cl11 cr2)</p><p>　　访问延迟：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F84f199c7p00qvx8qf000id200gq0040g00gq0040.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　数据来源：https://www.7-cpu.com/cpu/Haswell.html</p><p>　　由此我们可以知道，我们应该尽可能追求cache的命中率高，以避免延迟，最好是低级cache的命中率越高越好。</p><p>　　<strong>CACHE 的组织</strong></p><p>　　现代的cache基本按照这个模式来组织：SET、WAY、TAG、INDEX，这几个概念是理解Cache的关键。随便打开一个数据手册，就可以看到这样的字眼：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F1bba35acp00qvx8qf000id200gq003pg00gq003p.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　翻译成中文就是4路（way）组（set）相联，VIPT表现为(behave as)PIPT --这尼玛什么鬼？，cacheline的长度是64字节。</p><p>　　下面我们来想象一个16KB大小的cache，假设是4路组相联，cacheline的长度是64字节。Cacheline的概念比较简单，cache的整个替换是以行为单位的，一行64个字节里面读了任何一个字节，其实整个64字节就进入了cache。</p><p>　　比如下面两段程序，前者的计算量是后者的8倍：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fc6af7c1cp00qvx8qg0009d200gq002yg00gq002y.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　但是它的执行时间，则远远不到后者的8倍：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F7aaeed11p00qvx8qg0005d200a70054g00a70054.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　16KB的cache是4way的话，每个set包括4*64B，则整个cache分为16KB/64B/4 = 64set，也即2的6次方。当CPU从cache里面读数据的时候，它会用地址位的BIT6-BIT11来寻址set，BIT0-BIT5是cacheline内的offset。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F5bd1ccf6p00qvx8qg000od200gq00beg00gq00be.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　比如CPU访问地址</p><p>　　<br/><br/></p><p>　　或者</p><p>　　<br/><br/></p><p>　　或者</p><p>　　<br/><br/></p><p>　　由于它们红色的6位都相同，所以他们全部都会找到第0个set的cacheline。第0个set里面有4个way，之后硬件会用地址的高位如0,1，YYYY作为tag，去检索这4个way的tag是否与地址的高位相同，而且cacheline是否有效，如果tag匹配且cacheline有效，则cache命中。</p><p>　　所以地址YYYYYY000000XXXXXX全部都是找第0个set，YYYYYY000001XXXXXX全部都是找第1个set，YYYYYY111111XXXXXX全部都是找第63个set。每个set中的4个way，都有可能命中。</p><p>　　中间红色的位就是INDEX，前面YYYY这些位就是TAG。具体的实现可以是用虚拟地址或者物理地址的相应位做TAG或者INDEX。如果用虚拟地址做TAG，我们叫VT；如果用物理地址做TAG，我们叫PT；如果用虚拟地址做INDEX，我们叫VI；如果用物理地址做TAG，我们叫PT。工程中碰到的cache可能有这么些组合：</p><p>　　VIVT、VIPT、PIPT。</p><p>　　VIVT的硬件实现开销最低，但是软件维护成本最高；PIPT的硬件实现开销最高，但是软件维护成本最低；VIPT介于二者之间，但是有些硬件是VIPT，但是behave as PIPT，这样对软件而言，维护成本与PIPT一样。</p><p>　　在VIVT的情况下，CPU发出的虚拟地址，不需要经过MMU的转化，直接就可以去查cache。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F60992575p00qvx8qg0008d2009h00amg009h00am.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　而在VIPT和PIPT的场景下，都涉及到虚拟地址转换为物理地址后，再去比对cache的过程。VIPT如下：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F00b8debap00qvx8qh0009d200bh00a2g00bh00a2.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　PIPT如下：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F7bd60709p00qvx8qh000ad200bp00aag00bp00aa.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　从图上看起来，VIVT的硬件实现效率很高，不需要经过MMU就可以去查cache了。不过，对软件来说，这是个灾难。因为VIVT有严重的歧义和别名问题。</p><p>　　歧义：一个虚拟地址先后指向两个（或者多个）物理地址</p><p>　　别名：两个（或者多个）虚拟地址同时指向一个物理地址</p><p>　　这里我们重点看别名问题。比如2个虚拟地址对应同一个物理地址，基于VIVT的逻辑，无论是INDEX还是TAG，2个虚拟地址都是可能不一样的(尽管他们的物理地址一样，但是物理地址在cache比对中完全不掺和)，这样它们完全可能在2个cacheline同时命中。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F5fdbd967p00qvx8qh0008d200et0091g00et0091.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　由于2个虚拟地址指向1个物理地址，这样CPU写过第一个虚拟地址后，写入cacheline1。CPU读第2个虚拟地址，读到的是过时的cacheline2，这样就出现了不一致。所以，为了避免这种情况，软件必须写完虚拟地址1后，对虚拟地址1对应的cache执行clean，对虚拟地址2对应的cache执行invalidate。</p><p>　　而PIPT完全没有这样的问题，因为无论多少虚拟地址对应一个物理地址，由于物理地址一样，我们是基于物理地址去寻找和比对cache的，所以不可能出现这种别名问题。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F92fd4372p00qvx8qh0007d200et008gg00et008g.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　那么VIPT有没有可能出现别名呢？答案是有可能，也有可能不能。如果VI恰好对于PI，就不可能，这个时候，VIPT对软件而言就是PIPT了：</p><p>　　VI=PI</p><p>　　PT=PT</p><p>　　那么什么时候VI会等于PI呢？这个时候我们来回忆下虚拟地址往物理地址的转换过程，它是以页为单位的。假设一页是4K，那么地址的第12位虚拟地址和物理地址是完全一样的。回忆我们前面的地址：</p><p>　　YYYYY000000XXXXXX</p><p>　　其中红色的000000是INDEX。在我们的例子中，红色的6位和后面的XXXXXX（cache内部偏移）加起来正好12位，所以这个000000经过虚实转换后，其实还是000000的，这个时候VI=PI，VIPT没有别名问题。</p><p>　　我们原先假设的cache是：16KB大小的cache，假设是4路组相联，cacheline的长度是64字节，这样我们正好需要红色的6位来作为INDEX。但是如果我们把cache的大小增加为32KB，这样我们需要 32KB/4/64B=128=2^7，也即7位来做INDEX。</p><p>　　YYYY0000000XXXXXX</p><p>　　这样VI就可能不等于PI了，因为红色的最高位超过了2^12的范围，完全可能出现如下2个虚拟地址，指向同一个物理地址：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fe3724b0ep00qvx8qi000dd200eg009cg00eg009c.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这样就出现了别名问题，我们在工程里，可能可以通过一些办法避免这种别名问题，比如软件在建立虚实转换的时候，把虚实转换往2^13而不是2^12对齐，让物理地址的低13位而不是低12位与物理地址相同，这样强行绕开别名问题，下图中，2个虚拟地址指向了同一个物理地址，但是它们的INDEX是相同的，这样VI=PI，就绕开了别名问题。这通常是PAGE COLOURING技术中的一种技巧。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F5b8a3b87p00qvx8qi000cd200ec009cg00ec009c.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　如果这种PAGE COLOURING的限制对软件仍然不可接受，而我们又想享受VIPT的INDEX不需要经过MMU虚实转换的快捷？有没有什么硬件技术来解决VIPT别名问题呢？确实是存在的，现代CPU很多都是把L1 CACHE做成VIPT，但是表现地（behave as）像PIPT。这是怎么做到的呢？</p><p>　　这要求VIPT的cache，硬件上具备alias detection的能力。比如，硬件知道YYYY0000000XXXXXX既有可能出现在第0000000，又可能出现在1000000这2个set，然后硬件自动去比对这2个set里面是否出现映射到相同物理地址的cacheline，并从硬件上解决好别名同步，那么软件就完全不用操心了。</p><p>　　下面我们记住一个简单的规则：</p><p>　　对于VIPT，如果cache的size除以WAY数，小于等于1个page的大小，则天然VI=PI，无别名问题；</p><p>　　对于VIPT，如果cache的size除以WAY数，大于1个page的大小，则天然VI≠PI，有别名问题；这个时候又分成2种情况:</p><p><ul><li></p><p>　　硬件不具备alias detection能力，软件需要pagecolouring；</p><p></li><li></p><p>　　硬件具备alias detection能力，软件把cache当成PIPT用。</p><p></li></ul></p><p>　　比如cache大小64KB，4WAY，PAGE SIZE是4K，显然有别名问题；这个时候，如果cache改为16WAY，或者PAGE SIZE改为16K，不再有别名问题。为什么？感觉小学数学知识也能算得清</p><p>　　<strong>CACHE 的一致性</strong></p><p>　　Cache的一致性有这么几个层面</p><p><ol><li></p><p>　　一个CPU的icache和dcache的同步问题</p><p></li><li></p><p>　　多个CPU各自的cache同步问题</p><p></li><li></p><p>　　CPU与设备（其实也可能是个异构处理器，不过在Linux运行的CPU眼里，都是设备，都是DMA）的cache同步问题</p><p></li></ol></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F4647241fp00qvx8qj0006d200gq008tg00gq008t.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　先看一下ICACHE和DCACHE同步问题。由于程序的运行而言，指令流的都流过icache，而指令中涉及到的数据流经过dcache。所以对于自修改的代码（Self-Modifying Code）而言，比如我们修改了内存p这个位置的代码（典型多见于JIT compiler），这个时候我们是通过store的方式去写的p，所以新的指令会进入dcache。但是我们接下来去执行p位置的指令的时候，icache里面可能命中的是修改之前的指令。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F1643d547p00qvx8qj0008d200bq007xg00bq007x.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　所以这个时候软件需要把dcache的东西clean出去，然后让icache invalidate，这个开销显然还是比较大的。</p><p>　　但是，比如ARM64的N1处理器，它支持硬件的icache同步，详见文档：The Arm Neoverse N1 Platform: Building Blocks for the Next-Gen Cloud-to-Edge Infrastructure SoC</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F8906ce22p00qvx8qk001ad200gq008dg00gq008d.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　特别注意画红色的几行。软件维护的成本实际很高，还涉及到icache的invalidation向所有核广播的动作。</p><p>　　接下来的一个问题就是多个核之间的cache同步。下面是一个简化版的处理器，CPU_A和B共享了一个L3，CPU_C和CPU_D共享了一个L3。实际的硬件架构由于涉及到NUMA，会比这个更加复杂，但是这个图反映层级关系是足够了。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F488b125dp00qvx8qk0008d200go008wg00go008w.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　比如CPU_A读了一个地址p的变量？CPU_B、C、D又读，难道B,C,D又必须从RAM里面经过L3,L2,L1再读一遍吗？这个显然是没有必要的，在硬件上，cache的snooping控制单元，可以协助直接把CPU_A的p地址cache拷贝到CPU_B、C和D的cache。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fbeb6b6bbp00qvx8qk0005d200gp003tg00gp003t.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这样A-B-C-D都得到了相同的p地址的棕色小球。</p><p>　　假设CPU B这个时候，把棕色小球写成红色，而其他CPU里面还是棕色，这样就会不一致了：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fcab75cc9p00qvx8qk0005d200gp003tg00gp003t.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这个时候怎么办？这里面显然需要一个协议，典型的多核cache同步协议有MESI和MOESI。MOESI相对MESI有些细微的差异，不影响对全局的理解。下面我们重点看MESI协议。</p><p>　　MESI协议定义了4种状态：</p><p>　　M（Modified）: 当前cache的内容有效，数据已被修改而且与内存中的数据不一致，数据只在当前cache里存在；类似RAM里面是棕色球，B里面是红色球（CACHE与RAM不一致），A、C、D都没有球。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F1270f662p00qvx8ql0005d200gp006mg00gp006m.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　E（Exclusive）：当前cache的内容有效，数据与内存中的数据一致，数据只在当前cache里存在；类似RAM里面是棕色球，B里面是棕色球（RAM和CACHE一致），A、C、D都没有球。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F7a934134p00qvx8ql0005d200gp006mg00gp006m.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　S（Shared）：当前cache的内容有效，数据与内存中的数据一致，数据在多个cache里存在。类似如下图，在CPU A-B-C里面cache的棕色球都与RAM一致。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F5d0247e5p00qvx8ql0006d200gp006mg00gp006m.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　I（Invalid）： 当前cache无效。前面三幅图里面cache没有球的那些都是属于这个情况。</p><p>　　然后它有个状态机</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F5064a3ebp00qvx8qm000dd200bh008ig00bh008i.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这个状态机比较难记，死记硬背是记不住的，也没必要记，它讲的cache原先的状态，经过一个硬件在本cache或者其他cache的读写操作后，各个cache的状态会如何变迁。所以，硬件上不仅仅是监控本CPU的cache读写行为，还会监控其他CPU的。只需要记住一点：这个状态机是为了保证多核之间cache的一致性，比如一个干净的数据，可以在多个CPU的cache share，这个没有一致性问题；但是，假设其中一个CPU写过了，比如A-B-C本来是这样：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F5d0247e5p00qvx8ql0006d200gp006mg00gp006m.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　然后B被写过了：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fbefe02c5p00qvx8qm0006d200gp006mg00gp006m.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这样A、C的cache实际是过时的数据，这是不允许的。这个时候，硬件会自动把A、C的cache invalidate掉，不需要软件的干预，A、C其实变地相当于不命中这个球了：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F0d1f1663p00qvx8qn0005d200gp006mg00gp006m.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这个时候，你可能会继续问，如果C要读这个球呢？它目前的状态在B里面是modified的，而且与RAM不一致，这个时候，硬件会把红球clean，然后B、C、RAM变地一致，B、C的状态都变化为S（Shared）：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F07868669p00qvx8qn0005d200gp006mg00gp006m.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这一系列的动作虽然由硬件完成，但是对软件而言不是免费的，因为它耗费了时间。如果编程的时候不注意，引起了硬件的大量cache同步行为，则程序的效率可能会急剧下降。</p><p>　　为了让大家直观感受到这个cache同步的开销，下面我们写一个程序，这个程序有2个线程，一个写变量，一个读变量：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F6b475d47p00qvx8qn000kd200a300c8g00a300c8.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这个程序里，x和y都是cacheline对齐的，这个程序的thread1的写，会不停地与thread2的读，进行cache同步。</p><p>　　它的执行时间为：</p><p>　　<br/><br/></p><p>　　它在2个CPU上的userspace共运行了7.021秒，累计这个程序从开始到结束的对应真实世界的时间是3.614秒（就是从命令开始到命令结束的时间）。</p><p>　　如果我们把程序改一句话，把thread2里面的c = x改为c = y，这样2个线程在2个CPU运行的时候，读写的是不同的cacheline，就没有这个硬件的cache同步开销了：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F6b18366bp00qvx8qo000kd200gq0072g00gq0072.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　它的运行时间：</p><p>　　<br/><br/></p><p>　　现在只需要1.8秒，几乎减小了一半。</p><p>　　感觉前面那个a.out，双核的帮助甚至都不大。如果我们改为单核跑呢？</p><p>　　<br/><br/></p><p>　　它单核跑，只需要3.299秒跑完，而双核跑，需要3.614s跑完。单核跑完这个程序，甚至比双核还快，有没有惊掉下巴？！！！因为单核里面没有cache同步的开销。</p><p>　　下一个cache同步的重大问题，就是设备与CPU之间。如果设备感知不到CPU的cache的话（下图中的红色数据流向不经过cache），这样，做DMA前后，CPU就需要进行相关的cacheclean和invalidate的动作，软件的开销会比较大。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F2332a822p00qvx8qo0006d200dh006ug00dh006u.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这些软件的动作，若我们在Linux编程的时候，使用的是streaming DMA APIs的话，都会被类似这样的API自动搞定：</p><p>　　<br/><br/></p><p>　　如果是使用的dma_alloc_coherent() API呢，则设备和CPU之间的buffer是cache一致的，不需要每次DMA进行同步。对于不支持硬件cache一致性的设备而言，很可能dma_alloc_coherent()会把CPU对那段DMA buffer的访问设置为uncachable的。</p><p>　　这些API把底层的硬件差异封装掉了，如果硬件不支持CPU和设备的cache同步的话，延时还是比较大的。那么，对于底层硬件而言，更好的实现方式，应该仍然是硬件帮我们来搞定。比如我们需要修改总线协议，延伸红线的触角：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F5d955775p00qvx8qo0007d200gq007vg00gq007v.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　当设备访问RAM的时候，可以去snoop CPU的cache：</p><p><ul><li></p><p>　　如果做内存到外设的DMA，则直接从CPU的cache取modified的数据；</p><p></li><li></p><p>　　如果做外设到内存的DMA，则直接把CPU的cache invalidate掉。</p><p></li></ul></p><p>　　这样，就实现硬件意义上的cache同步。当然，硬件的cache同步，还有一些其他方法，原理上是类似的。注意，这种同步仍然不是免费的，它仍然会消耗bus cycles的。实际上，cache的同步开销还与距离相关，可以说距离越远，同步开销越大，比如下图中A、B的同步开销比A、C小。</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F488b125dp00qvx8qk0008d200go008wg00go008w.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　对于一个NUMA服务器而言，跨NUMA的cache同步开销显然是要比NUMA内的同步开销大。</p><p>　　<strong>意识到 CACHE 的编程</strong></p><p>　　通过上一节的代码，读者应该意识到了cache的问题不处理好，程序的运行性能会急剧下降。所以意识到cache的编程，对程序员是至关重要的。</p><p>　　从CPU流水线的角度讲，任何内存的访问延迟都可以简化为如下公式：</p><p><blockquote>Average Access Latency = Hit Time + Miss Rate × Miss Penalty</blockquote></p><p>　　cache miss会导致CPU的stall状态，从而影响性能。现代CPU的微架构分了frontend和backend。frontend负责fetch指令给backend执行，backend执行依赖运算能力和Memory子系统（包括cache）延迟。<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fbeac9a78p00qvx80022d200u000icg00id00b7.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　backend执行中访问数据导致的cache miss会导致backend stall，从而降低IPC（instructions per cycle）。减小cache的miss，实际上是一个软硬件协同设计的任务。比如硬件方面，它支持预取prefetch，通过分析cache miss的pattern，硬件可以提前预取数据，在流水线需要某个数据前，提前先取到cache，从而CPU流水线跑到需要它的时候，不再miss。当然，硬件不一定有那么聪明，也许它可以学会一些简单的pattern。但是，对于复杂的无规律的数据，则可能需要软件通过预取指令，来暗示CPU进行预取。<br/></p><p>　　<strong>cache预取</strong><br/></p><p>　　比如在ARM处理器上就有一条指令叫pld，prefetch可以用pld指令：</p><p>　　<br/><br/></p><p>　　眼见为实，我们随便从Linux内核里面找一个commit：<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F183666b7p00qvx80025d200u000msg00id00dx.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　因为我们从WiFi收到了一个skb，我们很快就要访问这个skb里面的数据来进行packet的分类以及交给IP stack处理了，不如我们先prefetch一下，这样后面等需要访问这个skb-&gt;data的时候，流水线可以直接命中cache，从而不打断。<br/></p><p>　　预取的原理有点类似今天星期五，咱们在上海office，下周一需要北京分公司的人来上海office开会。于是，我们通知北京office的人周末坐飞机过来，这样周一开会的时候就不必等他们了。不预取的情况下，会议开始后，再等北京的人飞过来，会导致stall状态。</p><p>　　任何东西最终还是要落实到代码，talk is cheap，show me the code。下面这个是经典的二分查找法代码，这个代码是网上抄的。<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fff3e47ffp00qvx8qr000od200i700lbg00i700lb.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　特别留意ifdef DO_PREFETCH包着的代码，它提前预取了下次的中间值。我们来对比下，不预取和预取情况下，这个同样的代码执行时间的差异。先把cpufreq的影响尽可能关闭掉，设置为performance:</p><p>　　<br/><br/></p><p>　　然后我们来对比差异：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F16da8554p00qvx8qr000jd200m800dhg00id00b4.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　开启prefetch执行时间大约10s, 不prefetch的情况下，11.6s执行完成，性能提升大约14%，所以周末坐飞机太重要了！</p><p>　　现在我们来通过基于perf的pmu-tools（下载地址：https://github.com/andikleen/pmu-tools)，对上面的程序进行topdown分析，分析的时候，为了尽可能减小其他因子的影响，我们把程序通过taskset运行到CPU0。</p><p>　　先看prefetch的情况，很明显，程序是backend_bound的，其中DRAM_Bound占比大，达到75.8%。<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F42e676b7p00qvx8qt0063d200u000tag00id00hx.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　开启prefetch的情况呢？程序依然是backend_bound的，其中，backend bound的主体依然是DRAM_Bound，但是比例缩小到了60.7%。<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F78445770p00qvx8qu0065d200u000tkg00id00i3.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　DRAM_Bound主要对应cycle_activity.stalls_l3_miss事件，我们通过perf stat来分别进行搜集：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F022a8327p00qvx8qv001cd200u000ekg00id008w.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　我们看到，执行prefetch情况下，指令的条数明显多了，但是它的insn per cycle变大了，所以总的时间cycles反而减小。其中最主要的原因是cycle_activity.stalls_l3_miss变小了很多次。<br/></p><p>　　这个时候，我们可以进一步通过录制mem_load_retired.l3_miss来分析代码究竟哪里出了问题，先看noprefetch情况：<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Ffd56173cp00qvx8qv000ad200p30036g00id002b.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　焦点在main函数：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F4639c086p00qvx8qv0007d200nq002mg00id0020.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　继续annotate一下：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F14fb2228p00qvx8qw0016d200l500skg00id00os.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　明显问题出在array[mid] &lt; key这句话这里。做prefetch的情况下呢？</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F76591abbp00qvx8qw000ad200oz0037g00id002c.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　main的占比明显变小了（99.93% -&gt; 80.00%）：<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F10784729p00qvx8qx000bd200nr0044g00id0036.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　继续annotate一下：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F43dabe88p00qvx8qx001bd200pc00rbg00id00js.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　热点被分散了，预取缓解了Memory_Bound的情况。</p><p>　　<strong>避免false sharing</strong><br/></p><p>　　前面我们提到过，如果数据在一个cacheline，被多核访问的时候，多核间运行的cache一致性协议，会导致cacheline在多核间的同步。这个同步会有很大的延迟，是工程里著名的false sharing问题。<br/></p><p>　　比如下面一个结构体</p><p>　　<br/><br/></p><p>　　如果1个线程读写a，另外一个线程读写b，那么两个线程就有机会在不同的核，于是产生cacheline同步行为的来回颠簸。但是，如果我们把a和b之间padding一些区域，就可以把这两个缠绕在一起的人拉开：<br/></p><p>　　<br/><br/></p><p>　　因此，在实际的工程中，我们经常看到有人对数据的位置进行移位，或者在2个可能引起false sharing的数据间填充数据进行padding。这样的代码在内核不胜枚举，我们随便找一个：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2Fea4fe123p00qvx8qy0013d200jg00jeg00id00ib.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　它特别提到在tw_count后面60个字节（L1_CACHE_BYTES - sizeof(atomic_t)）的padding，从而避免false sharing：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F7103237bp00qvx8qy0011d200n900hsg00id00e1.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　下面这个则是通过移动结构体内部成员的位置，相关数据的cacheline分开的：</p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F905cb058p00qvx8qz001od200o200oag00id00ij.png&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　这个改动有明显的性能提升，最高可达9.9%。代码里面也有明显地注释，usage和parent靠地太近，一个频繁写，一个频繁读。移开了2边互相不打架了：<br/></p><p class="f_center">　　<img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2021%2F0708%2F01454a4bj00qvx8qz001pd200lm00eog00g200aw.jpg&thumbnail=660x2147483647&quality=80&type=jpg"/><br/><br/></p><p>　　把理论和代码能对上的感觉真爽。无论是996,还是007,都必须留些时间来思考，来让理论和实践结合，否则，就变成漫无目的的内卷，这样一定会卷输的。内卷并不可悲，可悲的是卷不赢别人。</p>