找到规避系统级错误使用内存一致性算法

2015年复活节周末有一个珠宝抢劫保险箱大楼在伦敦哈顿花园。保险箱库是在建筑物的地下室和珠宝商的区域用于存储大量的钻石,珠宝、贵金属、和现金。小偷偷走了超过3亿美元的掠夺,使其成为英国历史上最大的盗窃案。一段时间看起来是完美的犯罪。小偷没有留下任何痕迹。没有指纹,DNA片段,没有识别。没有证人,也没有视频监控。苏格兰场了几乎没有线索。被盗后的数周内,公众是猜测,他可能会从这样一个惊人的壮举。人们设想一个“十一罗汉”类型机组人员训练有素的犯罪策划者。

原来抢劫犯罪是由一群老年人;老年罪犯是厌倦了退休。他们差点就蒙混过关了。这让有趣的阅读。故事的一个帐户可以在这里找到:http://www.vanityfair.com/culture/2016/03/biggest-jewel-heist-in-british-history。

他们是怎么在伦敦几乎无处不在的视频监控。英国有超过180万个摄像机看一切(http://www.theguardian.com/uk/2011/mar/02/cctv-cameras-watching-surveillance)。除了捕获视频,很多视频配有车牌的读者。在伦敦尤其如此,汽车的自动监测是用来执行一个拥堵税(https://tfl.gov.uk/modes/driving/congestion-charge),要求司机购买许可证在伦敦市中心交通高峰期开车。

汽车的警察使用这个数据库寻找那些已经在该地区犯罪前,但在某种程度上奇怪的地方。大多数车辆在该地区属于那些定期访问。他们在那里工作,或发货,或者生活在该地区,所以他们的存在可以被视为“。“警察可以消除那些汽车匹配多个许可证之前和之后的地方犯罪。其他人可能会通过。所以警察会看到只有一个发生的这些汽车。但是有人计划抢劫案件犯罪现场。会有多个目击的汽车抢劫前,但没有。警察使用“大数据”技术,能够筛选汽车在附近的巨大数据库和识别少数潜在的犯罪嫌疑人。他们遵循每一个犯罪嫌疑人,最终发现一群退休人员有更多的现金比可以解释他们的养老金和吹嘘在当地的小酒吧约拉有史以来最大的抢劫。 The rest is, as they say, history.

寻找异常不仅仅是一个好办法找到坏人在现实生活中,这也是设计好的寻找坏的东西。斯坦福大学有一个项目叫做DIDUCE,检测一个编译器来保存所有值由一个变量当程序运行。这个项目是由莫妮卡林博士,和一篇论文可以在这里找到:http://suif.stanford.edu/papers/Diduce.pdf。

从本质上说,该计划着眼于由所有变量的值随着时间的推移,发现不寻常的值,并将这些值的注意程序员是否代表一个bug。如果一个变量通常值在500年至1000年之间,除了当了2384294103年价值——这可能是一个错误。尽管该计划可能不会在任何特定的测试用例失败,它可能是值得看看发生了什么事情在这个不寻常的发生。项目发现了一个可怕的潜在的错误数量很多开源项目,包括在Java安全套接字层缺陷。本文绝对是值得一读。

我们可以将这些相同的狩猎技术应用到系统级调试,寻找,但不应该是什么。

我最近在设计调试Linux引导失败在仿真运行。问题是,部分通过引导内核会陷入恐慌和不幸的事故。是什么让这个特别混淆是Linux内核的事实,任何改变会改变位置和恐慌# heisenbug的症状。有趣的是,即使改变引导装入程序,U-boot或磁盘映像也将在引导过程的恐慌。添加一个printf辅助程序加载程序造成了恐慌,发生在Linux引导,将超过10秒。添加一个调试器的混合是没有帮助。单步进点的失败总是让搬到另一个位置。

Codelink是一种非侵入性的调试技术。它使调试器来显示你在处理器是怎么回事,但这并不影响程序执行。因此,它使它更容易发现问题。Codelink痕迹的处理器运行并将数据存储在我们称之为“重播数据库。“它使用这个数据库重构处理器的状态。嵌在这读和写操作都是在程序运行时进行。当然,它的大量的数据——从字面上g Linux引导。但这正是需要喂养一个大数据的算法。

Codelink环境

以来的Linux映像和相应的磁盘镜像失败在我的RTL设计正确引导的虚拟样机设计,我很确定这个软件很好。在一个硬件/软件系统中,被淘汰的过程,这使得硬件的头号嫌疑犯。对硬件的软件去坏它必须提供某种坏计划的输入。我的怀疑是总线上的织物,是由开发人员正在AXI协议第一次。

考虑到系统的读和写,一个检查是看如果读匹配前面写。如果处理器写道“x”的值对于一个给定的内存位置,然后读取的值在稍后的时间点“y”——这将是一个错误。

但这不是那么简单。有许多情况下,一个读值将不同于之前的写。例如,硬件设备。一个串行端口将返回一个不同的数据值的数据端口每次读。端口状态将返回不同的值。首先,我需要过滤掉所有的IO位置差异内存映射。同时,DMA操作可以更新内存,而处理器无关。它是容易关掉DMA操作。在以后的博客中,我将描述如何引进DMA操作。

所以数十亿的读和写操作,过滤后IO位置我剩下的几十名怀疑值。几十个我能追捕犯罪嫌疑人。

看问题的内存访问了,出现了一个明显的模式。对的问题:

和对总有0 x40xxxxxx和0 x60xxxxxx。和预期,数据读取的数据交换。事实证明,返回的数据被错误的外围。

这给了我“啊哈”的时刻。我会让你所有的调试步骤和快进到解决方案。

但首先,简要底漆AXI协议。AXI协议允许总线主控有多个优秀的交易。这些返回的多个优秀的交易可以按照任何顺序主人的奴隶。的事务ID用于解决返回的数据应该与一个特定的事务。但是,等等,这里有一些小字。主可以有多个未完成请求相同的事务ID#为什么# dontgetmestarted,总线结构的责任迫使这些交易的回归在相同的顺序发出。

问题的根源是,处理器是两个不同的外围设备发送两个事务。总线结构需要注意这一点,按照规范,并迫使的顺序返回。但是写总线结构的人错过了这个小细节(嘿,其两个句子在一个80页的文档)。如果多个请求相同的事务ID被送往相同的存储设备,存储设备序列化事务,没问题。如果请求到不同的设备,大多数时候首先完成第一次交易,所以一切正常。但偶尔当交易被送到不同的奴隶,第二个交易将完成。因此,数据值与错误的有关事务。令人惊讶的是,这是并不总是导致Linux引导去出轨的。十几个发生过导致Linux火山口。

找到这个盯着波形或戳在调试器会永远了。后加工的跟踪数据归零法快得多的问题——以至于我们决定添加此功能特性我们Codelink产品。我们称之为内存一致性检验。伟大的寻找这样的总线结构问题我这里描述,而且还擅长隔离缓存一致性问题。有一个坏Heisenbug ?你可能想看看Codelink能为你做什么。