要解决的问题 Linux内核提供了seccomp来对syscall权限进行检查，被广泛应用在容器、沙盒等多种场景，例如Docker和Android。但原版seccomp的实现是通过BPF对定义的规则一条条进行检查，如下图所示，十分低效： 同时，作者也进行了一系列的benchmark发现这样的检查带来了较大的开销： 其中，左边的docker-default指的是Docker默认使用的seccomp-profile，syscall-noargs指的是使application-specific profile但只检查syscall id而不检查参数，而syscall-complete就在noargs的基础上加上参数检查，最后加上-2x的后缀表示的是这些检查复制2次，来建模更复杂的安全检查场景。 可以看出，seccomp检查带来的开销即使是对于像nginx这样的macro-benchmarks也是比较大的，但现有的seccomp使用BPF，规则十分灵活，因此需要针对这种灵活的规则设计一种加速的方法。 Observation 检查系统调用ID会给Docker容器中的应用带来明显(noticeable)的性能开销。 检查系统调用参数比只检查系统调用ID的开销大得多(significantly more expensive)。 规则加倍，开销加倍。 syscall with 相同id和参数存在局部性（下图指明了实验中的距离） 解决方法 为了解决这个问题，作者引入了一个Fast…
聊聊内存序
最近读完了 A Primer on Memory Consistency and Cache Coherence这本书，写一篇文章结合我个人了解的其他知识总结一下内存序。 文章假定读者学习了基本的体系结构。 概念 Cache Coherence 相信大家对Cache有一个基本的理解。但这里需要引出一个新的概念，共享内存中的Private Cache。 即使是简单的单核处理器，往往L1 I-Cache与D-Cache也是Private的。因为IFU（取指单元）与LSU（访存单元）通常分布在处理器流水线的不同阶段，它们可能需要同时访问。既然是Private，这个时候如果我们通过访存指令写入了一些指令（通过D-Cache）到某个内存地址，而这个地址已经在I-Cache中，结果就在取指时有可能取到旧值，如何解决这一问题？ 也许L1…
浅谈现代处理器实现超大L1 Cache的方式
浅谈现代处理器实现超大L1 Cache的方式 昨天观看WWDC时看到Apple M2处理器的L1 Cache大小已经达到了192K+128K，这不禁使我产生好奇，Apple如何做到这一点。（尽管事后发现M1处理器已经实现了，但那时的我还不懂电路上的困难。） 超大L1 Cache是一件复杂的事情，对于L1 Cache，我们都希望它的访问延迟尽可能低。而由于我们目前的处理器和操作系统采用的虚拟内存分页机制，在使用虚拟地址访问内存时，需要首先得到对应虚拟地址的物理地址，这就导致在一条访存指令算出访存的虚拟地址后，我们首先需要查询TLB，而若查询TLB再将地址送入缓存，无疑增加了访问延迟。而对于许多高性能设计的处理器而言，L1 Cache的访问往往是制约处理器频率的主要关键路径，因此涉及到L1 Cache的电路路径都需要非常慎重考虑具体设计的路径长度。 基于目前CPU中的Cache主要采用组相连的结构，在该结构上解决方法通常采用VIPT的方式，即Virtually Indexed Physically Tagged。如下图所示，通过虚拟地址的一部分作为访问Cache的索引，同时将虚拟地址送入TLB中，这样我们就实现了电路上访问Cache与访问TLB的并行，在访问结束后对比TLB输出的物理地址高位与Cache访问得到的物理地址Tag，就完成了缓存是否命中的判断。 VIPT Cache在具体实现时，我们需要考虑缓存重名的问题。例如CPU上运行着2个进程有一个共享内存，这块共享内存对应着一块物理地址，但在2个进程中的虚拟地址不同，而如果CPU只是简单地将两份虚拟地址的数据都直接保存在缓存中，就会导致缓存不一致的问题。 SOTA的大部分处理器并未解决该问题（例如我们常见的Intel和AMD），只是将VIPT简化为伪VIPT。因为在许多ISA的虚拟内存管理中，最小页面大小为4KB，因此，我只需要保证作为Index的部分在虚拟地址的低12位内（即4KB内）即可。不过，这种方法导致L1 Cache中单路的大小无法超过MMU规定的最小页面大小，而组相连的场景下，随着路数增加，电路上判断并选择带来的电路长度也随之增加，同样提高了电路的延迟，导致频率的降低或划分流水线阶段后IPC（Instructions…
大学前三年的流水账
首先在开头提醒未来保研的学弟学妹，一定要通过提前联系一些学校的老师给自己有个定位，特别是在大一的时候因为竞赛或者种种原因没有取得高绩点但是专业能力较强而在Rank上无法体现的同学。而保研签卖身契如果自己不打算鸽一定要非常非常慎重。 自己的经历从大一说起。 大一 大一的时候对计算机领域研究了解太少了，看大家都在卷AI以为科研就只有AI相关，但自己又特别不喜欢这个方向，于是当时对保研的想法就是能保就读个划水专硕混学历，若不能保就直接去大厂。然后大一上进来期中考试高数还考了班上120多人内的第3名，就觉得自己没必要把绩点卷成这样，当时恰好自己对高中的OI生涯结果不满意（NOIP省一），于是大学便想继续在ICPC/CCPC（以前称为ACM竞赛）完成自己的遗愿，随后就把重心放在了这些比赛上。 然后很快，大一后半学期在学业上开始摸鱼，竞赛训练倒是更加频繁了，期末考也远没有期中考那么好了，特别是历史课和英语课因为没重视加上自己本来不擅长拖了很大的后腿，最后那个学期大概排名刚好20%。 然后到了大一下，又开始揽了更多的比赛并在自己加入的组织承担了更多的工作。后来有一件事情彻底改变了学习的状态。当时给那届CQUPC（重庆大学程序设计大赛）编写了Web报名系统以及负责了群发短信通知的工作。结果当时需要群发短信通知的日子刚好是比赛前一天晚上，而当时恰好高数老师需要补进度连补了四节课，而我当时给那个比赛编写的群发短信脚本又出了问题，在上课时间一直在折腾这事情，但毕竟当时就得通知到，无论如何都得发出去，最后原因在于被运营商限制了，找了客服解决，但后果是我落下了一晚上的高数课。 至此以后，我高数课就再也听不懂了，而当时各种比赛的压力也日益繁重，当时除了*CPC的日常训练外还报名参加了一个微信小程序的比赛，导致各种压力在一起一直没有挤出时间补上那一晚上落下的高数课，于是过上了抄作业的生活。结果在期末考前三周，连续参加了CTF校赛、ICPC南昌邀请赛、四川省大学生程序设计竞赛，还在那个时间赶工交了微信小程序作品，结果期末复习也真的来不及了，最后那个学期绩点非常惨，四分制GPA直接掉到2.8，感觉自己已经保研无望了。而现在回头来看，当时取得的竞赛成绩在后来都有更好的替代了。 期末结束，开始了计算机类专业分流，我们这一届也是第一届专业分流。当时教务老师明说了我们这届开始保研的时候按照全学院拉通排名，不分专业，因此大家选择专业的时候也主要跟随自己兴趣为主，但大多数人还是选择了计算机科学与技术。然后我当时报名了计科卓越班的选拔，虽然我当时绩点不高但是大一上成绩其实还行，且靠着比赛经历的加成（感觉主要是省程序设计大赛的金牌），还是通过了卓越班的选拔面试，进入了计科卓越工程师班。不过这一选择也成为了我在大三时破防的一个点，若当时没有通过，我可能选择的是信息安全。 大二 经过了绩点倒闭的大一下学期，大二就彻底对GPA躺平了，把心思全部放在算法竞赛上。当时基本每周和队友开1-2场5小时的模拟训练赛外加自己训练以及补题。最后结果还是不错的，在当年的EC-Final上拿了银牌，并且最后最难的那题三个人都有各自的贡献，也在最后10分钟评测机不堪重负等不来结果的时候我们把可能错的位置全部都改一遍，最后终榜出来发现那题过了，尽管那题不过也是银牌，但是总算是对这场比赛没有任何遗憾了。 然后大二下因为疫情在家生活节奏不太适应，又每天晚上被父母拉着出去锻炼身体占用了许多时间，所以一事无成，这个学期就到此为止吧。 唯一需要铺垫的事情是大二下的时候第一次参加了CET-6考试，因为大二上ICPC Asia EC-Final时间与CET-6冲突了，然后第一次参加也没重视就想看看当前水平，就裸考了，最后成绩是350多（具体多少忘了），总之是非常倒闭。因此就打算大三竞赛打完好好补一下英语的短板了。 大三上，突然可以单列保研 到了大三，开学的时候和室友组队参加了数学建模竞赛，结果恰好遇到了一个我非常擅长的问题，是一个图论题，然后我就拿着之前参加算法竞赛攒下的DP+网络流知识搞出了一个非常好的结果，队友也拿强化学习做了一部分，且这些算法结果好又可以把算法写的非常详细，最后我们获得了全国一等奖。按照当时已经符合学校的单列保研标准了。当时也非常高兴自己可以去混个学历了。 大三上，突然有志于系统结构方向科研 但也很快，就在这个学期，我们当时有一位助教在做操作系统的教改，把清华的uCore操作系统实验引入了我们学校，然后我当时看了指导书后对OS非常着迷。特别是把那些实验自己读代码读文档后补全代码做完以后发现自己对计算机系统的认识发生了本质性的变化，特别是搞清楚了内存管理后，开始理解了为什么像Java这样需要GC的语言在某些场景具有优势，觉得一下子思维都开阔了。于是发现自己找到了自己真正喜欢的东西，计算机底层的相关研究，或者说体系结构。于是开始有了好好做研究的想法，从曾经只想读个水专硕变成了想直博认真做研究。…
阅读笔记《Lord of the Ring(s):基于Intel Ring总线的侧信道攻击》
Lord of the Ring(s): Side-Channel Attacks on the CPU On-Chip Ring Interconnect Are Practical 作者：Riccardo Paccagnella, Licheng Luo,…
我在OI中辗转的这千百天
今天是2017年12月16日，距离NOIP2017结束已经过去一个多月了。我想写一篇文章来留念一下我在OI中辗转的这千百天。 0x01 初识OI 我最初知道NOI系列赛事是在初一的时候。 小学到初中有在跟着思明区青少年宫的老师学电脑机器人，当时在班上有个比我大岁的朋友，他刚上高中，知道了有NOIP这个比赛，后来他拉着我学Pascal入坑了。 那段时间他带我入门了Pascal，水平大概达到了会写校门外的树的程度，后来由于我的时间关系和他的时间关系没有继续往下学。当时由于周末还拿出一天上电脑机器人的课，所以也没有太多的闲暇时间。 后来到了NOIP报名的时候，我问了我们班主任能不能我们学校找个信息老师挂名去参加NOIP，之后便没有下文了。 其实现在想来，当时的水平甚至连通过普及组初赛都不够的。那个时候我的水平仅仅只是会用Pascal写入门难度的程序。并且那个时候的我也不了解算法和数据结构，对于计算机的学习处在一个以自己玩为住的状态。当时搞机器人，搞单片机。搞Web开发，搞C#、VB、易语言写点小程序。记得小学六年级的时候写了个控制飞机躲避障碍的游戏和弹球游戏就觉得自己很厉害了，现在自己看来这些东西真是小儿科。正如我当时写的弹球游戏需要考虑的圆以一定的速度和角度与直线碰撞的问题，我根本不会判，当时易语言有个组件叫画板，基于DirectPlay，判断物体碰撞只要设置速度和角度物体就会在屏幕上移动，碰撞的时候会调用一个事件，根本不需要像我写OI的计算几何题目一样去考虑各种东西，所以我当时根本没有想过要学习算法和数据结构，不明白它甚至可以帮忙升学，初中阶段也就把这个事情搁置了。 0x02 高一的NOIP2015 由于一直对计算机感兴趣。初中的时候希望中考能考上一个OI强校成为了一个目标。然而不幸的是，中考的时候考的很差，高中来到了厦门集美中学。 高中的第一节信息课，信息老师就在问我们全班同学有没有人知道NOIP这个比赛，我记得当时全班就我一个人举了手，然后和老师交换了联系方式，周日开始在学校上课。 当时我们学校OI班上大概有20个人，招人方式几乎只是问问谁感兴趣谁进来。其中还有个高二的学长和高二的学姐都是之前电脑制作拿过奖，就被我们老师拉去参加NOIP了。显然这和OI不是一个知识体系，毕竟我们也是老师带的第一届OIer。但不幸的是，初赛结束之后就只剩4个人参加提高组复赛了。而初中普及组的初赛通过人数还是挺多的。 后来自然就到NOIP2015了，然而当时什么算法都不会，只知道C语言的基本使用，也不会STL，甚至连搜索都不太熟练。最后Day 1T1做了出来，剩下的题目要么打个搜索，要么打个特解，要么打个输出random，最后得分150。当年恰逢CCF取消省三等奖，福建省计算机学会和省教育厅自己发省三等奖，当然这个奖自然是毫无卵用除了免信息会考。对我而言也是一个信心上的鼓励。 并且我也听说了福师大附中的hzwer，高一拿省三，高二省一，省选R2翻盘最后进队，最后NOI Ag…
小绿锁背后的RSA算法
如今，我们上网时常能见到一把小绿锁，这便是多数浏览器对于HTTPS连接的标识。即HTTP over SSL，它代表着我们与网站服务器的连接是经过SSL加密的。然而，不论何种加密算法，总是有加密和解密的过程，其中最关键的就是密钥交换过程，如果在交换过程中这个密钥被窃取，之后的加密便毫无意义。那么SSL是如何确保即使我们的网络流量被抓取的情况下也能保证加密信息安全的呢？这就是我们今天要说的非对称加密算法，而最早的非对称加密算法便是从RSA开始。 算法介绍 RSA算法是1977年由麻省理工学院的Ron Rivest、Adi Shamir、Leonard Adleman三人共同提出的，RSA名字便取自他们三人的姓氏。在RSA算法之前，密钥交换主要采用预共享密钥的方式，例如我们生活中连接WPA2-PSK的Wi-Fi便是采用预共享密钥的方式，它的特点是需要通信双方事先共享密钥才能加密，也称为对称加密。而RSA采用的是非对称加密，需要生成两组密钥，称为公钥(Public Key)和私钥(Private Key)，这两组密钥是成对的。使用公钥加密的数据可以被私钥解密，使用私钥加密的数据可以被公钥解密。 在了解这个算法前，你需要了解以下数学知识，我假设读者已经具备初中数学知识。 对于OIer，你如果了解过扩展欧几里得、欧拉函数、费马小定理，你可以跳过这一段，而且你看这个会很轻松。 最大公因数： Greatest Common Divisor，即两个数的因数集合的交集中最大的数，通常我们使用gcd表示。 例如a、b的最大公因数记为gcd(a,b) 互质关系：…
Back to Top