Lancern的小本本 编程 / PL / 工具链 / 运维 / 以及更多!
理解 C++ 的六种 Memory Order

今天上午的分布式系统课程内容中包含了可线性化(Linearizability)和序列一致(Sequential Consistent)的内容,不知不觉联想到了 C++11 中新引入的六种 memory order。我又阅读了若干文章和文献(文章和文献来源主要是知乎 / Stack Overflow / 相关论文等)加深了一下对 memory order 的理解。我将在这篇文章中谈一谈 C++ 的 memory order 相关内容。 Memory order 是 C++11 中最难以理解的几个特性之一。因此我将详细地解释其来龙去脉,希望大家能够学到对自己有用的东西。 本文的逻辑结构是这样的: 首先我会在第一节中给出 C++ memory order 需要解决的问题,以及相关的背景知识; 接着我会在第二节中给出 C++ 标准中对 memory order 的定义和解释,以及实现 memory order 的方法; 最后我会在第三节中对本文所有内容进行简单的总结。 C++ Abstract Machine, Thread of Execution and Memory Order所有的高级通用程序语...

由一个性能下降问题引发的对 CPU 缓存一致性协议性能开销的粗略测量

问题实验室的 L 同学最近在进行对多线程程序进行模糊测试的研究工作。在实验阶段,L 同学发现了一个有趣的现象:在使用著名的模糊测试工具 AFL 对一个多线程程序进行测试时,被测试程序的性能大约只有直接运行该程序的性能的 20% 左右。需要注意,直接运行的程序也经过 afl-gcc 处理,进行了覆盖率插桩。因此排除了是插桩的代码本身造成了性能下降的可能。我对这个有趣的问题进行了研究。在介绍结论前,我们需要先了解 AFL 这一模糊测试工具对被测试程序的插桩原理。 背景:AFL 的插桩机制AFL 是一个灰盒模糊测试工具。“灰盒”意味着 AFL 会在运行被测试程序的同时收集被测试程序的代码覆盖率。AFL 使用“边覆盖率”这一指标作为被测程序的代码覆盖率,这里的“边”指程序中两个基本块之间的控制流转移边。AFL 提供了一个经过修改的编译器 afl-gcc,被测试程序需要使用 afl-gcc 进行编译后才能进行测试。afl-gcc 会在程序中的每个基本块的起始位置处插入一小段代码,这段代码在程序执行时会将程序控制流的上一条边的编号写入一块共享内存(以下称这块共享内存为 trace bitmap)中。在程序结束运行后...

Peach Fuzzer 实现原理介绍

Peach fuzzer 是一款著名的通用黑盒模糊测试工具,被广泛地应用于真实世界的软件测试中。本文将简要介绍 peach 模糊测试工具的实现原理。 简介Peach 是一款基于生成的模糊测试工具。Peach 运行时需要用户提供一个以 XML 格式编码的配置文件,这个配置文件中给出了测试目标程序、测试方式、测试例数据结构等一切测试所需的信息。因此,只要弄明白这个配置文件中提供的信息的具体含义,就能够理解 Peach 的运作方式。但是,在我们探索 Peach 的配置文件的各个部分的含义之前,我们需要首先对 Peach 的设计目标有基本的了解。 设计目标测试目标的多样性与经典的 AFL 等模糊测试工具不同,Peach 不仅支持对传统的、通过 CLI 运行的程序的测试,也支持对其他类型的程序(例如 Windows 服务等)进行测试。测试目标的多样性会导致: 运行目标程序的方式是多样的。可能直接使用命令行参数启动程序、可能通过 Windows 服务相关设施启动服务、可能复用已有的程序实例等; 为目标程序提供输入数据的方式是多样的。可能通过文件输入数据、通过 stdin 输入数据、通过网络连接输入数据等; 监控目...

Lancern的小本本正式开始营业

经过一天的配置,Lancern的小本本正式开始营业。本文将介绍本站的技术选型和部署方法等内容。 本站采用静态网站生成器(static site generator)生成,使用的生成器是著名的 hexo,使用的主题是基于 macleaya 改进的主题,在原主题的基础上增强了网站美观性、文章可读性和网站响应性。另外,本站的 RSS feed 使用 hexo 官方的 hexo-generator-feed 插件进行生成。 本站的内容源代码托管在 github 上的一个私有仓库中,静态网页托管在 DigitalOcean 平台上。DigitalOcean 面向个人用户推出了网页应用托管服务,如果只需要托管静态页网站则该服务是免费的,且支持 github 的 webhook。每当内容作者向 github 上的源代码仓库的 master 分支推送内容时,DigitalOcean 会自动从 github 仓库中拉取最新的内容源代码并构建为静态页。 本站域名是 lancern.xyz,从阿里云购买并由国内的DNS提供商提供解析服务。该域名的DNS记录是一个CNAME记录,实际指向blog-tluyk.ondigital...

In Search of an Understandable Consensus Algorithm (2)

本文将介绍以下内容: Leader election Leader Election为搞清楚 Raft 算法中 leader election 的机制,需要明白如下的一些关键点: 触发系统进入 leader election 的条件; 当系统进入 leader election 后,如何选择下一个 leader。 Leader Election Triggering当一个节点启动时,节点的初始角色为 follower。在 follower 角色下,如果一个节点在一段被称为 election timeout 的时间内没有收到来自 leader 的任何 RPC 请求,那么这个节点将切换成为 candidate 角色。在正常情况下,即使没有任何的任务,leader 也会定期向所有的 follower 发送不包含任何 log entry 的 AppendEntries RPC 请求,起到 heartbeat 的作用。 当某个 follower 节点因为触发 election timeout 而切换成为 candidate 节点后,这个节点将完成下列的操作: 将节点内部维护的当前 term ID 递增;...

In Search of an Understandable Consensus Algorithm (1)

本文是对 In Search of an Understandable Consensus Algorithm[1] 这篇论文的系列阅读笔记的第一篇。本文将主要介绍如下内容: Replicated state machine 与 consensus algorithm 的概念; Raft 算法的总体介绍; Raft 算法介绍中需要了解的一些概念和术语。 Motivation诸如 Paxos[2] 等的分布式一致算法(consensus algorithm)在设计上有一定缺陷导致其难以被学习者理解。本文提出了一种名为 Raft 的分布式一致算法,其首要设计目标是可理解性(understandability)。 Background: Replicated State Machine (RSM)状态机(state machine)[3]是计算的抽象。一个状态机包括两个重要的部分:状态(state)和状态转移函数(state transfer function)。本文中所提到的状态机都是确定性状态机(deterministic state machine)。RSM 是一组分布在多个节点上的、状态一致的确定...

经典分布式系统论文列表

最近因为课程和项目需要,将要读一些经典的分布式系统方面的论文。论文阅读笔记将记录在这个系列中。 论文列表如下。 Ghemawat, Sanjay, Howard Gobioff, and Shun-Tak Leung. “The Google file system.” Proceedings of the nineteenth ACM symposium on Operating systems principles. 2003. Dean, Jeffrey, and Sanjay Ghemawat. “MapReduce: simplified data processing on large clusters.” Communications of the ACM 51.1 (2008): 107-113. Ongaro, Diego, and John Ousterhout. “In search of an understandable consensus algorithm (extended version).” (2013). Scales, Daniel J., Mike Nelso...

std::format

在 C++20 之前,C++ 的格式化字符串相关设施一直饱受诟病。具体来说,在不依赖第三方库的情况下,有两种方式实现格式化字符串: 使用从 C 语言沿袭过来的 sprintf 以及相关函数; 使用 C++ 的 std::stringstream 以及流相关设施。 然而,这两种方式都有明显的缺点。 对于第一种方式,即使用 sprintf 等函数进行格式化字符串,首先只能使用 C 风格字符串作为格式化结果,这意味着程序员需要手工管理存放字符串的内存空间;其次,sprintf 只能对有限的几种内置类型(例如整数、浮点数和 C 风格字符串等) 进行格式化,不支持也无法拓展支持格式化其他类型的数据;最后一点是 printf 系列函数一直存在的安全性问题,因为这些函数不是类型安全的。 对于第二种方式,不论是从语法上还是从本质上都与直接拼接字符串没有任何区别。在需要大规模进行字符串格式化的场景下,这种方式代码冗长、语法噪音极多,很不直观。 在 C++20 以前,除了 C/C++ 之外,几乎任意一个合格的现代命令式编程语言都在其标准库中实现有完备的格式化字符串设施。终于,在 C++ 社区长时间的呼吁声中,C++20...

Coroutines

Coroutines(协程)是 C++20 引入的几个重要的语言级新特性之一。C++20 引入的协程机制与其他语言的异步(async)或类似机制有相似的地方,但也有很大的不同:C++20 的协程机制能实现的功能更多,但在实现细节上也更加复杂。为了清晰起见,本文不会对其他语言的协程机制或异步机制进行介绍或将其与 C++20 的协程机制进行细节上的比较。 C++20 的协程的主要设计目标是支持保存和恢复代码的执行状态。一个简单的例子是斐波那契数列生成器: FibonacciGenerator fibonacci() { auto prev = 1; auto prev2 = 1; auto n = 1; while (true) { if (n <= 2) { co_yield 1; // #1 } else { co_yield prev + prev2; // #1 std::swap(prev, prev2); prev += prev...