论文翻译：快速检测多变量原子性违规的轻量级方法

2024-01-30

原文：C.-H. Bae, E. Choi, Y.-K. Jun, and O.-K. Ha, “Lightweight Method for On-the-fly Detection of Multivariable Atomicity Violations,” in 2023 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Dublin, Ireland: IEEE, Apr. 2023, pp. 165–171. doi: 10.1109/ICSTW58534.2023.00039.

摘要: 在多线程程序中测试检测实时并发错误（如由多个共享变量引起的原子性违规）具有挑战性，因为需要考虑各种因素，包括变量之间的相关性和访问事件交错。本研究提出了一种在程序执行过程中检测违反原子性的改进方法。该方法采用一种直接的方法，将构成原子性的大量相关变量识别为一个单独的组和一个变量。这种增强型方法与测试工具类似，并使用一组合成程序进行了实验比较，这些程序模拟了七个具有代表性的多变量原子性违规行为的执行过程。结果表明，与测试程序的原始运行和最先进的检测方法相比，执行时间分别增加了 1.07 倍和 1.05 倍。这一结果包括了先前方法未检测到的所有多变量原子性违规行为的检测精度。

I. 导言

并行或多线程程序中的同步是一种强制机制，用于协调各种计算系统中的线程执行和管理共享数据。然而，测试程序以发现由非功能事实（如线程同步）引起的并发错误（如违反原子性）是相当具有挑战性的，因为这需要各种知识和诀窍，如并发线程的交错预判定和共享资源的竞争分析。原子性违规是严重的并发错误之一，当两个或多个线程同时在一个临界区域内执行时，程序员会认为该临界区域将实现原子性。特别是，如果在预期实现原子性的区域内，对共享变量的访问中至少包括一次写入，就必须对其进行测试和检测，以提高软件系统的可靠性，因为这样会满足竞赛条件，并产生意想不到的后果。

以往检测原子性违规行为的研究确定观察到的程序执行是否与串行执行或串行化相同。技术[1]-[4]与支持静态检测的技术相比，即时检测原子性违规的技术会产生更多的误报。但仍可能造成误报和漏报。此外，它们可能无法检测到由多个变量引发的违反原子性的情况，因为它们只考虑了单个变量，而没有分析预期原子执行的关键部分中共享变量之间的相关性。

本研究提出了一种轻量级方法，该方法改进了多线程程序执行过程中检测原子性违规的最先进方法–预期不变（AI）[5]算法，考虑了临界区域中组成原子执行的多个变量。所提方法的关键点在于通过将与原子操作相关的多个共享变量分组为一个共享变量来检测违反原子性的情况。原子性违规行为是通过分析共享变量在执行过程中发生的方法来诊断的，这种方法基于程序员所希望的共享变量的接近顺序，反映了通过执行前收集的共享变量的相关性。实验中使用了一组合成程序，模拟了实际应用中出现的七种原子性违规行为的执行过程，比较了所介绍方法的准确性和效率。在实验结果中，与预期不变量不同的是，使用我们的增强型方法的测试工具能正确检测出所有七种情况。此外，与原始执行测试程序相比，该工具平均需要 10.7 次执行时间，仅增加了 6.8%；与预期不变量相比，平均需要 1.05 次执行时间，仅增加了 4.9%，从而有效地检测了由多个变量引起的违反原子性的情况。

本文的其余部分安排如下：第 2 节介绍了多线程程序中的并发错误，以及以往检测原子性违规的研究。第 3 节介绍了即时检测方法的设计和操作。第 4 节介绍了拟议方法的实现和实验，第 5 节给出了结论和未来研究。

II. 背景介绍

A. 并发错误

基于共享内存的多线程程序可能会产生并发错误，例如数据竞赛和原子性。在程序执行过程中，由于并发线程对共享变量的访问同步不当而造成的并发违规。众所周知，这些并发错误主要是调试和测试多线程程序时的麻烦缺陷，因为并发线程的交错是非确定性的。

根据 S. Lu 等人的研究[1]，并发错误可分为死锁错误和非死锁错误。在该研究调查的现实世界应用程序中，约 66% 的错误属于非死锁错误，即同时对共享资源执行线程操作（如数据竞赛和原子性违规）所导致的竞赛错误。数据竞赛是具有代表性的竞赛错误，当两个线程同时访问单个共享变量时就会发生，包括在没有适当同步的情况下至少写入一次。违反原子性是指线程在原子代码区域内同时访问共享变量时，意外违反了原子性，从而发生竞赛错误。

图 1 是一个在 Apache 应用程序中发生并发错误的示例 [6]。图 1 (a) 是由于在两个并发线程上接近共享变量而导致并发错误的代码区域。Content 和 Content_len 是共享变量，如果 Content 的内容发生变化，Content_len（保存在 Content 中的值的长度）也要更新。图 1(b)是(a)中的执行图示，箭头表示线程操作，圆圈表示每个共享变量的访问事件，圆圈中的 W 和 R 分别表示写入和读取访问事件。

图 1 中的执行潜藏着两个共享变量之间的数据竞赛，因为两个不同的线程在没有适当同步的情况下访问了两个共享变量中的每一个。利用数据竞赛检测技术（如 “发生前分析”），可以诊断出线程 1 中的 W 和线程 2 中的 R 分别在两个共享变量之间存在两个数据竞赛。图 2 (a) 显示了通过对每个共享变量使用相同的锁进行同步以保持预期的访问顺序来消除数据竞赛的结果。

在 Content_len 受不同锁保护的情况下，竞赛问题依然存在，因为在值更新前可能会发生读取。这是线程 1 中两个变量的两次写访问事件违反了程序员所希望的原子性的结果。如图 2 (b)所示，通过使用包含两个共享变量的单个相同锁来保持两个变量的原子性，可以轻松解决图 2 (a) 中的原子性违规问题。

B. 以往的研究

众所周知，由于线程交错，并发性错误（如违反原子性）很难重现，而且一般的软件测试方法也很难检测出顺序程序中的错误。因此，并发错误的检测需要基于错误诊断规则或协议的自动程序的帮助。在程序执行过程中检测违反原子性的技术分为基于还原的方法（REM）[7]-[9]、基于访问模式的方法（APM）[5]、[10]-[12]和基于发生关系的方法（HRM）[13]-[15]。REM基于 Lipton 的还原理论[16]，探索访问共享变量的事件的换向属性，并分析原子性，以确定和检测每个线程的访问事件序列是否与获取的执行中定义的模式相匹配。APM 通过分析交错共享变量的访问事件是否与定义的非序列化模式相匹配，来检测违反原子性的情况。最后，HRM 利用预期执行原子性操作的执行区域中访问事件之间的顺序关系，分析和检测共享变量访问事件的冲突。虽然这些即时检测违反原子性的方法比通过静态分析确定的方法更复杂，检测性能也更优越，但它们仍然会引起误报和漏报。

考虑到现有研究的准确性和开销，AI（预期不变性） [5] 是一种基于 APM 的适用于多线程程序的方法。该研究利用预测试信息诊断并发错误，如违反原子性，并通过停滞诊断出错误的线程来处理并发错误。AI 是 J. Yu 等人[17]方法的改进版。作者将数据结构中每个内存操作的顺序定义为 PSet（前置集）。因此，AI 同样将每条指令的顺序定义为 RPre（远程前置集）和 BSet（归属集）。 RPre 收集与分析共享变量并发访问相关的指令（$I_x$），如访问类型（读/写）、访问ID、线程ID、代码中的位置和内存地址。RPre 根据指令($I_x$)按以下规则更新信息：

它访问的地址与 $I_x$ 相同。
它是在另一个线程中执行的，而$I_x$不属于这个线程。
包括 RPre($I_x$) 的 BSet 根据动态指令 ($D_x$) 收集满足以下条件的静态指令 (S ) ：x
它访问的地址与 $D_x$ 相同。
它在另一个线程中执行，而 $D_x$ 不属于该线程。
在 $D_x$ 之前访问的 $S_x$ 会被执行并存储。

静态分析 - 数据流分析

2023-11-23

程序分析 / 静态分析

数据流分析（data flow analysis）

数据流分析是一类分析，其分析对象是控制流图（CFG），产生特定于应用程序的数据结果（application-specific Data）。

不同的数据流分析应用有着：

不同的数据抽象
不同的流安全近似（flow safe-approximation）策略
不同的传输函数和控制流处理（transfer functions & control-flow handings）

flow through

nodes (BBs/statements)
edges (control flows of)
cfg (a program)

输入和输出状态

在每个语句中，前一语句的输出作为当前语句的输入，生成当前的输出。

在每个数据流分析应用中，我们将每个程序点（program point）与数据流值（data-flow value）关联起来，这个数据流值表示该点可以观察到的所有可能的程序状态的抽象。
数据流分析旨在找到一个解，其中包含一组在In[s]和OUT[s]中的以安全近似为导向的约束，对于所有语句s：

基于语句语义的约束（传输函数，transfer function）
基于控制流的约束

传输函数约束的符号表示

两种类型：

正向分析（forward analysis）
OUT[s] = f_s(IN[s])
反向分析：（backward analysis）
IN[s] = f_s(OUT[s])

基本块内的控制流（control flow within a BB）：

IN[s_i+1] = OUT[s_i], for all i=1,2,...,n-1
基本块之间的控制流（control flow among BBs）：

参见图表
notations for control flow's constaints

meet operator ^.png

数据流分析应用（Data flow analysis Applications）

非常基础的3种数据流模式：

到达定义分析（Reaching Definitions Analysis）
活跃变量分析（Live Variables Analysis）
可用表达式分析（Available Expressions Analysis）

到达定义分析（Reaching Definitions Analysis）

A definition d at program point p reaches a point q if there is a path from p to q such that d is not killed along that path
在程序点p的定义d能够达到程序点q，是否有一个路径从p到q且d在路径上没有被killed

给定程序点q，能够检查某变量的值是何时定义的。

可以用于检查可能的未定义变量，在入口为每个变量v引入dummy定义，如果v的dummy定义能够到达使用v的某个程序点p没有被killed
也可以用于常量传播，复制传播上。

分类：

forward/backward analysis? forward analysis
must/may analysis? may analysis(over apprioximation)

data flow values/ facts: all definiton in a program，可以用bit vectors表示

algorithm

为什么OUT[entry]=空集？
- 回想out定义（在这一program point有什么定义可以流到这里）
为什么对各个基本块初始化entry被排除而单独对entry初始化？
- 因为这个算法是一个data algorithm模板，其他的data analysis(特别是must analysis) 中entry和各基本块的初始化会不一样
为什么需要判断OUT是否有变化然后多次迭代？
- CFG可能包含环，第一次遍历CFG时，某些边可能未初始化。多次迭代是为了获得最终结果。
为什么迭代一定会停止？
对于某个基本块B，kill和gen是常量，所以输入不变输出不变。
当一个fact（某个位）加到OUT[s]，要么是通过gen添加的，要么是前一个块的fact经过当前块的survivor。
当添加更多fact（某个位）时，它们要么被killed，要么流入到OUT[s]中。
因此，OUT[s]从来不会变小（其中的位只会从0变成1，或者保持1不变）

也就是说，如果某位想变0，不可能是kill或gen引起的（因为这俩是常量），只可能是前一个BB的OUT中该位从1变为了0，但这也是不可能的，理由同前，这个过程是递归的，直到入口都不会有人的OUT从1变为了0

因为fact集合是有限的，所以一定有一趟迭代没有任何东西添加到OUT，所以算法终止

活跃变量分析（Live Variables Analysis）

分析在程序点（program point）p的变量v的值是否在CFG中从p开始的路径中被使用（v在这条路径中使用前不能被重新定义）。

给定程序点p，某变量的值未来是否会使用到

一个重要用途：可用于为基本块进行寄存器分配。如果我们能分析出某寄存器中的值在以后不会被使用（dead value），我们更倾向于使用这个寄存器。

data flow values/ facts: all variable in a program

分类：

forward/backward analysis? backward analysis
must/may analysis? may analysis

注意方程中：
defb是指这样的变量：基本块中对其定值先于任何对其使用
useb是指这样的变量：基本块中对其使用先于任何对其定值

algorithm

可用表达式分析（Available Expressions Analysis）

A definition d at program point p reaches a point q if there is a path from p to q such that d is not killed along that path
在程序点p的表达式x op y是可用的，如果

所有从入口到p一定经过x op y的求值；
在最后一个x op y的求值以后，没有对x或y的重新定义。

这个定义意味着在程序点p，我们可以用最后依次x op y的求值结果替换表达式x op y

主要用途：寻找全局公共子表达式

分类：

forward/backward analysis? / analysis
must/may analysis? must analysis(under apprioximation) why? may report an expression as unavailable even if it is truly available

data flow values/ facts: all expression in a program

algorithm

注意基本块初始化为全1（因为后面对于汇聚都是取交集，初始化为0会导致错误）
注意汇聚都是取交集（因为must analysis，不能有误报，不能引起错误优化）

小结

静态分析导论 - introduction

2023-11-23

程序分析

静态分析导论 - Introduction

在软件工程中，静态分析是一种重要的程序分析方法，通过在不运行程序的情况下对其源代码或中间表示进行检查和推理，以获取有关程序行为和性质的信息。本文将介绍静态分析的基本概念以及与之相关的一些重要主题。

概述

程序的生命周期中的许多关键步骤都涉及到对程序的分析，以便更好地理解、维护和优化代码。静态分析是其中之一，它通过在编译或开发阶段对程序进行检查，提供了一种在运行时难以获得的洞察力。

静态分析通常包括以下步骤：

词法分析（Lexical Analysis）：将源代码转换为令牌流。
语法分析（Syntax Analysis）：将令牌流转换为抽象语法树（AST）。
语义分析（Semantic Analysis）：对AST进行类型检查和语义检查，生成带有语义信息的修饰AST。
翻译（Translation）：将修饰AST翻译为中间表示（IR）。
静态分析（Static Analysis）：对IR进行分析，进行诸如代码优化等操作。

[source] -> scanner(lexcial analysis) -> [tokens] -> parser(syntax analysis) -> [ast] -> type checker(semantic analysis) ->[decorated ast] -> translator -> [IR] -> static analysis, e.g code optimization -> code generator -> [machine code]

重要概念

AST vs IR

AST（抽象语法树）：表示源代码的语法结构，是语法分析的输出。
IR（中间表示）：在编译器中用于在高级源代码和目标机器代码之间进行转换的数据结构。

3AC（3-Address Code）

3AC是一种中间表示，每条语句最多包含一个操作符。它包括多种类型的语句，如赋值、条件跳转等。
右边最多一个operator( t1=a+b, t2=t1+3.)

典型语句类型：
- x = y bop z;
- x = uop y;
- x = y;
- goto L;
- if x goto L;
- if x rop y goto L
a typed 3AC: soot - jimple
- for
- do while
- method call

SSA（静态单赋值）

SSA是一种中间表示的形式，其中每个变量只被赋值（定义）一次。这有助于某些优化和分析，如条件常量传播和全局值编号。

为什么使用SSA？

部分精度的流不直接合并到单一变量名中，有助于流不敏感分析获得部分精度。
显式的定义和使用关系（define-and-use对），使得一些优化更高效（如conditional constant propagation, global value numbering）。

为什么不使用SSA？

引入了大量变量和phi函数。
在生成机器码时可能引入性能问题，因为需要进行复制操作。

控制流图（CFG）与基本块

控制流图是程序中基本块之间控制流的图形表示。节点通常是单独的3AC，或者是基本块（Basic Block）

基本块是一种最基本的控制流单元，它是一个连续的3AC序列，只有一个入口和一个出口。

从A到B有一条边，当且仅当：

有一个条件或无条件跳转从A的结束到B的开始（符合的出边）
B在指令原始序列中紧跟着A，且A的最后不是无条件跳转（不符合的出边）

Basic Block

最长的三地址指令序列满足：只有开始能进入，中间不存在入口；只有结尾能退出，中间不存在出口

两类分析

may analysis:
outputs information that may be true(over-approximation)

must analysisL
outputs information that must be true(under-approximation)

over-approximation & under-approximation are both for safety of analysis

初步了解了静态分析的基本流程、重要概念以及涉及的一些关键主题。在软件工程中，静态分析是提高代码质量、发现潜在问题和进行优化的强大工具。

memory order

2023-11-18

多线程并发

本文以c++内存模型为参考，但也适用于大多数其他语言（许多语言使用了类似c++的模型）。

同步发生(synchronizes-with)

“同步发生”只能在原子类型之间进行操作。例如对一个数据结构进行操作(对互斥量上锁)，如果数据结构包含有原子类型，并且操作内部执行了一定的原子操作，那么这些操作就是同步发生关系。从根本上说，这种关系只能来源于对原子类型的操作。

“同步发生”的基本想法是：在变量x进行适当标记的原子写操作W，同步与对x进行适当标记的原子读操作，读取的是W操作写入的内容；或是在W之后，同一线程上的原子写操作对x写入的值；亦或是任意线程对x的一系列原子读-改-写操作(例如，fetch_add()或compare_exchange_weak())。这里，第一个线程读取到的值是W操作写入的。

先将“适当的标记”放在一边，因为所有对原子类型的操作，默认都是适当标记的。这实际上就是：如果线程A存储了一个值，并且线程B读取了这个值，线程A的存储操作与线程B的载入操作就是同步发生的关系。

// code fragment 1:
// 当data_ready①为true，写操作就会与读操作同步，建立一个“先行发生”关系。
std::vector<int> data;
std::atomic<bool> data_ready(false);
void reader_thread()
{
  while(!data_ready.load())  // 1
  {
    std::this_thread::sleep(std::milliseconds(1));
  }
  std::cout<<"The answer="<<data[0]<<"\m";  // 2
}
void writer_thread()
{
  data.push_back(42);  // 3
  data_ready=true;  // 4
}

先行发生(happens-before)

“先行发生”关系是一个程序中，基本构建块的操作顺序；它指定了某个操作去影响另一个操作。对于单线程来说，就简单了：当一个操作排在另一个之后，那么这个操作就是先行执行的。这意味着，如果源码中操作A发生在操作B之前，那么A就先行于B发生。例如对于前一个程序，对data的写入③先于对data_ready④的写入。

如果操作在同时发生，因为操作间无序执行，通常情况下，它们就没有先行关系了。这就是另一种排序未被指定的情况。下面的程序会输出“1，2”或“2，1”，因为两个get_num()的执行顺序未被指定。

// code fragment 2:
// 对于参数中的函数调用顺序是未指定顺序的
void foo(int a,int b)
{
  std::cout<<a<<”,”<<b<<std::endl;
}
int get_num()
{
  static int i=0;
  return ++i;
}
int main()
{
  foo(get_num(),get_num());  // 无序调用get_num()
}

线程间的互相作用：线程间的先行

如果操作A在线程上，并且线程先行于另一线程上的操作B，那么A就先行于B。这也没什么，你只是添加了一个新关系。

从基本层面上讲，线程间的先行比较简单，并且依赖与同步关系：如果操作A在一个线程上，与另一个线程上的操作B同步，那么A就线程间先行于B。这同样是一个传递关系：如果A线程间先行于B，并且B线程间先行于C，那么A就线程间先行于C。你可以回看一下第一个程序。

线程间先行可以与排序先行关系相结合：如果操作A排序先行于操作B，并且操作B线程间先行于操作C，那么A线程间先行于C。同样的，如果A同步于B，并且B排序先于C，那么A线程间先行于C。两者的结合，意味着当你对数据进行一系列修改(单线程)时，为线程后续执行C，只需要对可见数据进行一次同步。

这些是线程间强制排序操作的关键规则，也是让第一段程序正常运行的因素。并在数据依赖上有一些细微的差别，你马上就会看到。为了让你理解这些差别，需要讲述一下原子操作使用的内存排序标签，以及这些标签和同步发生之间的联系。

原子操作的内存顺序

六个内存序列选项可应用于对原子类型的操作：

memory_order_relaxed,
memory_order_consume
memory_order_acquire
memory_order_release
memory_order_acq_rel
memory_order_seq_cst（默认顺序）。

虽然有六个选项，但是它们仅代表三种内存模型：

排序一致序列(sequentially consistent)
获取-释放序列(memory_order_consume, memory_order_acquire, memory_order_release和memory_order_acq_rel)
自由序列(memory_order_relaxed)。

这些不同的内存序列模型，在不同的CPU架构下，功耗是不一样的。
例如，基于处理器架构的可视化精细操作的系统，比起其他系统，添加的同步指令可被排序一致序列使用(在获取-释放序列和自由序列之前)，或被获取-释放序列调用(在自由序列之前)。如果这些系统有多个处理器，这些额外添加的同步指令可能会消耗大量的时间，从而降低系统整体的性能。
另一方面，CPU使用的是x86或x86-64架构(例如，使用Intel或AMD处理器的台式电脑)，使用这种架构的CPU不需要任何对获取-释放序列添加额外的指令(没有保证原子性的必要了)，并且，即使是排序一致序列，对于加载操作也不需要任何特殊的处理，不过在进行存储时，有点额外的消耗。

不同种类的内存序列模型，允许专家利用其提升与更细粒度排序相关操作的性能。当默认使用排序一致序列(相较于其他序列，它是最简单的)时，对于在那些不大重要的情况下是有利的。

排序一致序列

默认序列命名为排序一致，因为程序中的行为从任意角度去看，序列顺序都保持一致。如果原子类型实例上的所有操作都是序列一致的，那么一个多线程程序的行为，就以某种特殊的排序执行，好像单线程那样。这是目前来看，最容易理解的内存序列，这也就是将其设置为默认的原因：所有线程都必须了解，不同的操作也遵守相同的顺序。

因为其简单的行为，可以使用原子变量进行编写。通过不同的线程，你可以写出所有序列上可能的操作，这样就可以消除那些不一致，以及验证你代码的行为是否与预期相符。

这也就意味着，所有操作都不能重排序；如果你的代码，在一个线程中，将一个操作放在另一个操作前面，那么这个顺序就必须让其他所有的线程所了解。

#include <atomic>
#include <thread>
#include <assert.h>

std::atomic<bool> x,y;
std::atomic<int> z;

void write_x()
{
  x.store(true,std::memory_order_seq_cst);  // 1
}

void write_y()
{
  y.store(true,std::memory_order_seq_cst);  // 2
}
void read_x_then_y()
{
  while(!x.load(std::memory_order_seq_cst));
  if(y.load(std::memory_order_seq_cst))  // 3
    ++z;
}
void read_y_then_x()
{
  while(!y.load(std::memory_order_seq_cst));
  if(x.load(std::memory_order_seq_cst))  // 4
    ++z;
}
int main()
{
  x=false;
  y=false;
  z=0;
  std::thread a(write_x);
  std::thread b(write_y);
  std::thread c(read_x_then_y);
  std::thread d(read_y_then_x);
  a.join();
  b.join();
  c.join();
  d.join();
  assert(z.load()!=0);  // 5
}

assert⑤语句是永远不会触发的。

如果在read_x_then_y中加载y③返回false，那是因为存储x的操作肯定发生在存储y的操作之前，那么在这种情况下在read_y_then_x中加载x④必定会返回true，因为while循环能保证在某一时刻y是true。
因为memory_order_seq_cst的语义需要一个单全序将所有操作都标记为memory_order_seq_cst，这就暗示着“加载y并返回false③”与“存储y①”的操作，有一个确定的顺序。只有一个全序时，如果一个线程看到x==true，随后又看到y==false，这就意味着在总序列中存储x的操作发生在存储y的操作之前。

只有一个全序时，如果一个线程看到x==true，随后又看到y==false，这就意味着在总序列中存储x的操作发生在存储y的操作之前。

当然，因为所有事情都是对称的，所以就有可能以其他方式发生，比如，加载x④的操作返回false，或强制加载y③的操作返回true。在这两种情况下，z都等于1。当两个加载操作都返回true，z就等于2，所以任何情况下，z都不能是0。

当read_x_then_y知道x为true，并且y为false，那么这些操作就有“先发执行”关系了，如图所示。

序列一致与先发执行

序列一致是最简单、直观的序列，但是他也是最昂贵的内存序列，因为它需要对所有线程进行全局同步。在一个多处理系统上，这就需要处理期间进行大量并且费时的信息交换。

为了避免这种同步消耗，你需要走出序列一致的世界，并且考虑使用其他内存序列。

非排序一致内存模型

当你踏出序列一致的世界，所有事情就开始变的复杂。可能最需要处理的问题就是：再也不会有全局的序列了。这就意味着不同线程看到相同操作，不一定有着相同的顺序，还有对于不同线程的操作，都会整齐的，一个接着另一个执行的想法是需要摒弃的。不仅是你有没有考虑事情真的同时发生的问题，还有线程没必要去保证一致性。为了写出(或仅是了解)任何一段使用非默认内存序列的代码，要想做这件事情，那么之前的那句话就是至关重要的。你要知道，这不仅仅是编译器可以重新排列指令的问题。即使线程运行相同的代码，它们都能拒绝遵循事件发生的顺序，因为操作在其他线程上没有明确的顺序限制；因为不同的CPU缓存和内部缓冲区，在同样的存储空间中可以存储不同的值。这非常重要，这里我再重申一遍：线程没必要去保证一致性。

不仅是要摒弃交错执行操作的想法，你还要放弃使用编译器或处理器重排指令的想法。在没有明确的顺序限制下，唯一的要求就是，所有线程都要统一对每一个独立变量的修改顺序。对不同变量的操作可以体现在不同线程的不同序列上，提供的值要与任意附加顺序限制保持一致。

踏出排序一致世界后，最好的示范就是使用memory_order_relaxed对所有操作进行约束。如果你已经对其有所了解，那么你可以跳到获取-释放序列继续阅读，获取-释放序列允许你选择在操作间引入顺序关系(并且收回你的理智)。

自由序列

在原子类型上的操作以自由序列执行，没有任何同步关系。在同一线程中对于同一变量的操作还是服从先发执行的关系，但是这里不同线程几乎不需要相对的顺序。

唯一的要求是，在访问同一线程中的单个原子变量不能重排序；当一个给定线程已经看到一个原子变量的特定值，线程随后的读操作就不会去检索变量较早的那个值。

当使用memory_order_relaxed，就不需要任何额外的同步，对于每个变量的修改顺序只是线程间共享的事情。

// 非限制操作只有非常少的顺序要求
#include <atomic>
#include <thread>
#include <assert.h>

std::atomic<bool> x,y;
std::atomic<int> z;

void write_x_then_y()
{
  x.store(true,std::memory_order_relaxed);  // 1
  y.store(true,std::memory_order_relaxed);  // 2
}
void read_y_then_x()
{
  while(!y.load(std::memory_order_relaxed));  // 3
  if(x.load(std::memory_order_relaxed))  // 4
    ++z;
}
int main()
{
  x=false;
  y=false;
  z=0;
  std::thread a(write_x_then_y);
  std::thread b(read_y_then_x);
  a.join();
  b.join();
  assert(z.load()!=0);  // 5
}

这次assert⑤可能会触发，因为加载x的操作④可能读取到false，即使加载y的操作③读取到true，并且存储x的操作①先发与存储y的操作②。x和y是两个不同的变量，所以这里没有顺序去保证每个操作产生相关值的可见性。

非限制操作对于不同变量可以自由重排序，只要它们服从任意的先发执行关系即可(比如，在同一线程中)。它们不会引入同步相关的顺序。清单5.5中的先发执行关系如图5.4所示(只是其中一个可能的结果)。尽管，在不同的存储/加载操作间有着先发执行关系，这里不是在一对存储于载入之间了，所以载入操作可以看到“违反”顺序的存储操作。

非限制原子操作与先发执行

让我们来看一个略微复杂的例子，其有三个变量和五个线程。

/*
你拥有三个全局原子变量①和五个线程。每一个线程循环10次，使用memory_order_relaxed读取三个原子变量的值，并且将它们存储在一个数组上。其中三个线程每次通过循环④来更新其中一个原子变量，这时剩下的两个线程就只负责读取。当所有线程都“加入”，就能打印出来每个线程存到数组上的值了。
*/
#include <thread>
#include <atomic>
#include <iostream>

std::atomic<int> x(0),y(0),z(0);  // 1
std::atomic<bool> go(false);  // 2

unsigned const loop_count=10;

struct read_values
{
  int x,y,z;
};

read_values values1[loop_count];
read_values values2[loop_count];
read_values values3[loop_count];
read_values values4[loop_count];
read_values values5[loop_count];

void increment(std::atomic<int>* var_to_inc,read_values* values)
{
  while(!go)
    std::this_thread::yield();  // 3 自旋，等待信号
  for(unsigned i=0;i<loop_count;++i)
  {
    values[i].x=x.load(std::memory_order_relaxed);
    values[i].y=y.load(std::memory_order_relaxed);
    values[i].z=z.load(std::memory_order_relaxed);
    var_to_inc->store(i+1,std::memory_order_relaxed);  // 4
    std::this_thread::yield();
  }
}

void read_vals(read_values* values)
{
  while(!go)
    std::this_thread::yield(); // 5 自旋，等待信号
  for(unsigned i=0;i<loop_count;++i)
  {
    values[i].x=x.load(std::memory_order_relaxed);
    values[i].y=y.load(std::memory_order_relaxed);
    values[i].z=z.load(std::memory_order_relaxed);
    std::this_thread::yield();
  }
}

void print(read_values* v)
{
  for(unsigned i=0;i<loop_count;++i)
  {
    if(i)
      std::cout<<",";
    std::cout<<"("<<v[i].x<<","<<v[i].y<<","<<v[i].z<<")";
  }
  std::cout<<std::endl;
}

int main()
{
  std::thread t1(increment,&x,values1);
  std::thread t2(increment,&y,values2);
  std::thread t3(increment,&z,values3);
  std::thread t4(read_vals,values4);
  std::thread t5(read_vals,values5);

  go=true;  // 6 开始执行主循环的信号

  t5.join();
  t4.join();
  t3.join();
  t2.join();
  t1.join();

  print(values1);  // 7 打印最终结果
  print(values2);
  print(values3);
  print(values4);
  print(values5);
}

程序一种可能的输出为：

(0,0,0),(1,0,0),(2,0,0),(3,0,0),(4,0,0),(5,7,0),(6,7,8),(7,9,8),(8,9,8),(9,9,10)
(0,0,0),(0,1,0),(0,2,0),(1,3,5),(8,4,5),(8,5,5),(8,6,6),(8,7,9),(10,8,9),(10,9,10)
(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,0,4),(0,0,5),(0,0,6),(0,0,7),(0,0,8),(0,0,9)
(1,3,0),(2,3,0),(2,4,1),(3,6,4),(3,9,5),(5,10,6),(5,10,8),(5,10,10),(9,10,10),(10,10,10)
(0,0,0),(0,0,0),(0,0,0),(6,3,7),(6,5,7),(7,7,7),(7,8,7),(8,8,7),(8,8,9),(8,8,9)

前三行中线程都做了更新，后两行线程只是做读取。每三个值都是一组x，y和z，并按照这样的顺序依次循环。对于输出，需要注意的一些事是：

第一组值中x增1，第二组值中y增1，并且第三组中z增1。
x元素只在给定集中增加，y和z也一样，但是增加是不均匀的，并且相对顺序在所有线程中都不同。
线程3看不到x或y的任何更新；他能看到的只有z的更新。这并不妨碍别的线程观察z的更新，并同时观察x和y的更新。

对于非限制操作，这个结果是合法的，但是不是唯一合法的输出。任意组值都用三个变量保持一致，值从0到10依次递增，并且线程递增给定变量，所以打印出来的值在0到10的范围内都是合法的。

注意：在各变量都是自增的前提下，即使线程1观察到x=3时y仍然为0，但不影响线程4仍然有机会观察到x=1时y已经自增到3。

了解自由排序

为了了解自由序列是如何工作的，先将每一个变量想象成一个在独立房间中拿着记事本的人。他的记事本上是一组值的列表。你可以通过打电话的方式让他给你一个值，或让他写下一个新值。如果你告诉他写下一个新值，他会将这个新值写在表的最后。如果你让他给你一个值，他会从列表中读取一个值给你。

在你第一次与这个人交谈时，如果你问他要一个值，他可能会给你现在列表中的任意值。如果之后你再问他要一个值，它可能会再给你同一个值，或将列表后面的值给你，他不会给你列表上端的值。如果你让他写一个值，并且随后再问他要一个值，他要不就给你你刚告诉他的那个值，要不就是一个列表下端的值。

试想当他的笔记本上开始有5，10，23，3，1，2这几个数。如果你问他索要一个值，你可能获取这几个数中的任意一个。如果他给你10，那么下次再问他要值的时候可能会再给你10，或者10后面的数，但绝对不会是5。如果那你问他要了五次，他就可能回答“10，10，1，2，2”。如果你让他写下42，他将会把这个值添加在列表的最后。如果你再问他要值，他可能会告诉你“42”，直到有其他值写在了后面并且他认为他愿意将那个数告诉你。

现在，想象你有个朋友叫Carl，他也有那个计数员的电话。Carl也可以打电话给计算员，让他写下一个值或获取一个值，他对Carl回应的规则和你是一样的。他只有一部电话，所以他一次只能处理一个人的请求，所以他记事本上的列表是一个简单的列表。但是，你让他写下一个新值的时候，不意味着他会将这个消息告诉Carl，反之亦然。如果Carl从他那里获取一个值“23”，之后因为你告诉他写下42，这不意味着下次他会将这件事告诉Carl。他可能会告诉Carl任意一个值，23，3，1，2，42亦或是67(是Fred在你之后告诉他的)。他会很高兴的告诉Carl“23，3，3，1，67”，与你告诉他的值完全不一致。这就像它在使用便签跟踪告诉每个人的数，就像图5.5那样。

现在，想象一下，不仅仅只有一个人在房间里，而是在一个小农场里，每个人都有一部电话和一个笔记本。这就是我们的原子变量。每一个变量拥有他们自己的修改顺序(笔记上的简单数值列表)，但是每个原子变量之间没有任何关系。如果每一个调用者(你，Carl，Anne，Dave和Fred)是一个线程，那么对每个操作使用memory_order_relaxed你就会得到上面的结果。这里还有些事情你可以告诉在小房子的人，例如，“写下这个值，并且告诉我现在列表中的最后一个值”(exchange)，或“写下这个值，当列表的最后一个值为某值；如果不是，告诉我看我是不是猜对了”(compare_exchange_strong)，但是这都不影响一般性原则。

如果你仔细想想清单5.5的逻辑，那么write_x_then_y就像某人打电话给房子x里的人，并且告诉他写下true，之后打电话给在y房间的另一个人，告诉他写下true。线程反复执行调用read_y_then_x，就像打电话给房间y的人问他要值，直到要到true，然后打电话给房间x的，继续问他要值。在x房间中的人有义务告诉你在他列表中任意指定的值，他也是有权利所false的。

这就让自由的原子操作变得难以处理。他们必须与原子操作结合使用，这些原子操作必须有较强的排序语义，为了让内部线程同步变得更有用。我强烈建议避免自由的原子操作，除非它们是硬性要求的，并且在使用它们的时候需要十二分的谨慎。给出的不直观的结果，就像是清单5.5中使用双线程和双变量的结果一样，不难想象在有更多线程和更多变量时，其会变的更加复杂。

要想获取额外的同步，且不使用全局排序一致，可以使用获取-释放序列(acquire-release ordering)。

释放序列

释放序列(release sequence)是一种内存顺序，用于描述对共享数据的写入操作的顺序。假设有两个线程，一个执行写入操作，另一个执行读取操作。释放序列确保在写入操作之前的所有读取和写入操作都在写入操作之前完成，从而确保了一致性。

释放序列是针对具有memory_order_release内存顺序的写入操作的概念。当一个线程执行一个具有释放顺序的写入操作时，它确保在这个写入操作之前的所有写入和读取操作都在这个写入操作之前完成。这样可以防止编译器和处理器对写入操作的重新排序，确保其他线程在读取这个写入的数据时能够看到写入操作之前的所有更新。

一些补充概念

总序（total order）是指一个对于所有的操作，都存在一个全局的一致的执行顺序。即，任意两个操作都可以被比较出一个先后顺序。这意味着所有的操作都有一个明确定义的顺序，不会存在模糊或不一致的情况。
单一总序（Single total order）是总序的一个特例，它要求所有的操作都按照它们在程序中出现的顺序执行。
修改顺序（Modification order）是指在多线程环境中，每个变量（或对象）的修改操作有一个明确定义的顺序。这意味着如果一个线程对变量进行了修改，那么其他线程对同一变量的修改操作会按照一定的顺序进行：并且在同一线程上读取对象的操作，要不返回一个已写入的值，要不在对象的修改顺序后(也就是在读取后)再写入的另一个值。
总修改序（Total Modification Order）是对修改顺序的一种强化，它要求对所有变量的修改操作都存在一个全局的一致的执行顺序。保证了在整个系统中对于所有变量的修改都有一个确定的顺序。

Releax 序、Rel-Acq 序都提供修改顺序保证（注意是对于同一变量的），不提供总序保证，不提供总修改顺序保证。(Rel-Acq 序比Releax序多的是，提供Rel-Acq成对操作之间的顺序保证)
顺序一致性排序拥有总序、修改顺序、总修改序。

引用和致谢

本文极大程度引用和借鉴了《C++ Concurrency In Action》，特别是其中文翻译版的内容：
http://shouce.jb51.net/cpp_concurrency_in_action/content/chapter5/5.3-chinese.html

感谢该书作者和译者。

wsl配置代理

2023-09-06

技术实践

wsl1适用版：

hostip="127.0.0.1"
socks_hostport=10808
http_hostport=10809
export all_proxy="socks5://${hostip}:${socks_hostport}"
export http_proxy="http://${hostip}:${http_hostport}"
export https_proxy="http://${hostip}:${http_hostport}"
export ftp_proxy=$http_proxy
export rsync_proxy=$http_proxy
export ALL_PROXY=$all_proxy
export HTTP_PROXY=$http_proxy
export HTTPS_PROXY=$https_proxy
export FTP_PROXY=$ftp_proxy
export RSYNC_PROXY=$rsync_proxy

特点：
因为wsl1在逻辑上与宿主机属于相同的主机，ip直接使用127.0.0.1

wsl2适用版：

# Set network proxy
hostip=$(ip route | grep default | awk '{print $3}')
socks_hostport=10810
http_hostport=10811
export all_proxy="socks5://${hostip}:${socks_hostport}"
export http_proxy="http://${hostip}:${http_hostport}"
export https_proxy="http://${hostip}:${http_hostport}"
export ftp_proxy=$http_proxy
export rsync_proxy=$http_proxy
export ALL_PROXY=$all_proxy
export HTTP_PROXY=$http_proxy
export HTTPS_PROXY=$https_proxy
export FTP_PROXY=$ftp_proxy
export RSYNC_PROXY=$rsync_proxy
export no_proxy="localhost,127.0.0.1"

特点：
因为wsl2在逻辑上与宿主机属于不同的主机，
使用ip route | grep default | awk '{print $3}'获取宿主机ip
另外需要设置no_proxy，否则wsl2运行的程序试图访问wsl2本机时也会被错误转发到宿主机代理然后访问成宿主机，导致一些程序出错。

TCP开启timestamps

2023-08-14

技术实践

windows用户：

1	netsh interface tcp set global timestamps=enabled

linux用户：

1	sysctl -w net.ipv4.tcp_timestamps=1

WSL2 Error code: Wsl/Service/0x8007273d解决

2023-08-07

折腾记录

首先说结论，这个问题（在我所遇到的情况中）大多数是由于加速器软件或者全局代理类软件修改了系统的Winsock来全局加载代理导致的，而WSL2与其不兼容，所以产生 0x8007273d 错误。

你可以通过简单地命令行中运行netsh winsock reset（管理员权限，本文后续也默认在管理员权限cmd中运行）来重置Winsock，然后 WSL2 就可以正常工作了。
但也这会使 Proxifier等（使用 winsock 的软件）不再能工作。

如果你希望能使用此类软件也能使用WSL2，请继续向下看：

我首先通过搜索找到了这样一篇文章：https://wangyj.medium.com/the-solution-to-wsl-error-the-attempted-operation-is-not-supported-for-the-type-of-object-aa559854d1e3

我发现它的思路是正确的，但对当前最新版本的WSL2（从Micosoft store安装或更新的）而言不适用，需要做一些小调整。
下面分别详细介绍早期版本和当前最新版的详细修复方法。

早期版本的步骤（如果你是新安装的Win系统或从 “启用或关闭Windows功能” 安装的wsl）：

下载 Nolsp.exe：http://www.proxifier.com/tmp/Test20200228/NoLsp.exe
通过 NoLSP.exe "C:\Windows\System32\wsl.exe"配置 nolsp，它会添加适当的注册表项。
关闭所有 wsl 终端并重新打开 wsl
现在，wsl2 可以正常工作了。

(替代方法）如果不想使用 Nolsp.exe 二进制文件，可以使用 regedit.exe 在注册表中手动添加以下项目。

Windows Registry Editor Version 5.00

[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\WinSock2\Parameters\AppId_Catalog\0408F7A3]
"AppFullPath"="C:\Windows\System32\wsl.exe"
"PermittedLspCategories"=dword:80000000

（或保存为.reg文件运行导入）

如果你是从 Micosoft store 安装的WSL，或者你曾经运行过 `wsl --update` （也是 Store 版 WSL）：

这两种情况使用的是 Micosoft Store 中的 wsl2，它们真正执行主要功能的程序路径不同，因此在修复步骤中需要指定 WinApps 应用程序的文件路径（”C:\Program Files\WindowsApps\WSl安装文件夹名\wsl.exe”），而不是系统目录中”C:\Windows\System32\wsl.exe”，另外，最新版本还涉及wslservice.exe的文件（它作为后台服务运行，也需要重启）

首先，你可以通过在 cmd(admin) 中执行以下指令来查看WSl安装文件夹名：

1 2	cd "C:\Program Files\WindowsApps\" dir MicrosoftCorporationII.WindowsSubsystemForLinux_*

你会看到WSl安装文件夹名，格式类似 MicrosoftCorporationII.WindowsSubsystemForLinux_1.2.5.0_x64__8wekyb3d8bbwe，复制它并且在后续步骤中的路径中替换WSl安装文件夹名，完整的路径类似C:\Program Files\WindowsApps\MicrosoftCorporationII.WindowsSubsystemForLinux_1.2.5.0_x64__8wekyb3d8bbwe\wsl.exe。
(不同的 wsl2 版本有不同的安装文件夹名。

步骤：

下载 Nolsp.exe: http://www.proxifier.com/tmp/Test20200228/NoLsp.exe
运行 NoLSP.exe "C:\Program Files\WindowsApps\MicrosoftCorporationII.WindowsSubsystemForLinux_1.2.5.0_x64__8wekyb3d8bbwe\wsl.exe", 它会添加一个正确的注册表。
运行 NoLSP.exe "C:\Program Files\WindowsApps\MicrosoftCorporationII.WindowsSubsystemForLinux_1.2.5.0_x64__8wekyb3d8bbwe\wslservice.exe" ，它将添加一个正确的注册表。
(注意：如果你使用的是不同的版本，记得在以上两步使用你的WSl安装文件夹名来替换掉1.2.5.0_x64__8wekyb3d8bbwe）
运行 wsl --shutdown && net stop WslService && net start WslService，关闭所有 wsl 终端并重新打开 wsl
现在，wsl2 可以正常工作了。

另外，请注意，每次 wsl 更新后，WindowsApps 的路径都会发生变化（因此将来更新后需要重新配置 nolsp）。

查看gcc编译器的默认include目录

2023-07-01

有时候我们在配置一些代码编辑器的intellisense功能时，需要添加编译时的系统头文件列表，而这些不是太容易寻找（可能有很多个目录组成），这时候我们可以使用以下方法：

运行gcc -xc++ -E -v -，
该命令通过指定C++语言选项-xc++来启动GCC编译器，并使用-E选项告诉它仅进行预处理，-v选项启用详细输出。最后的-表示从标准输入中读取代码。

运行上述命令后，GCC将输出许多详细信息，可以在输出中找到类似以下内容的行：

#include "..." search starts here:
#include <...> search starts here:
 /path/to/include/dir1
 /path/to/include/dir2
 ...

这些目录路径就是gcc编译器的默认include目录。

如果不需要c++的头文件而只需要c语言的头文件，也可以将选项-xc++换成-xc。

负二进制转换与负M进制转换

2023-04-10

算法

LeetCode原题“1017. 负二进制转换”：https://leetcode.cn/problems/convert-to-base-2/

给你一个整数 n ，以二进制字符串的形式返回该整数的负二进制（base -2）表示。

注意，除非字符串就是 “0”，否则返回的字符串中不能含有前导零。

示例 1：

输入：n = 2
输出："110"
解释：(-2)2 + (-2)1 = 2
示例 2：

输入：n = 3
输出："111"
解释：(-2)2 + (-2)1 + (-2)0 = 3
示例 3：

输入：n = 4
输出："100"
解释：(-2)2 = 4

本题给出了负二进制的转换

给你一个整数 n ，以二进制字符串的形式返回该整数的负二进制（base -2）表示。

注意，除非字符串就是 “0”，否则返回的字符串中不能含有前导零。

即，a_0*(-2)^0 + a_1*(-2)^1 +... = n，其中ai在负二进制下为0或1，求a_i序列

答案：

class Solution {
public:
    string baseNeg2(int n) {
        if (n == 0 || n == 1) {
            return to_string(n);
        }
        string res;
        while (n != 0) {
            int remainder = n & 1;
            res.push_back('0' + remainder);
            n -= remainder;
            n /= -2;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

// 作者：LeetCode-Solution

那么现在提问，进行扩展：

如果需要转换为任意负M进制呢？
如何同时支持正进制和负进制？

即，a_0*M^0 + a_1*M^1 +... = n，其中ai在负M进制下为0到-N-1，在正M进制下为0到N-1，求a_i序列

答案：

class Solution {
public:
    const int M = -2;
    string baseNeg2(int n) {
        if(n==0) return "0"s;
        string ans;
        while(n) {
            int remainder = n % toM;
            if(remainder<0) {
                // n=M*quotient+remainder
                // 当n为正数而M是负数时，n%M的结果remainder在大多数编程语言（c/c++/java）也是负数，remainder调回正数只需要-M（加上M的绝对值）
                // 同时为了保持n不变，商需要+1（M*quotient为更大的负）来抵消掉多出来的部分
                remainder-=M;
                n = n/M+1;
            } else {
                // 当余数恰好为0 或者 n和M同号（此时remainder为正），不需要任何处理
                n /= M;
            }
            ans.push_back('0' + remainder);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

参考资料：

两个很经典的位运算记录

2022-10-21

算法

记录一下：

x&(-x)：保留二进制下最后出现的1的位置，其余位置置0
x&(x-1)：消除二进制下最后出现1的位置，其余保持不变

数据流分析（data flow analysis）

输入和输出状态

传输函数约束的符号表示

数据流分析应用（Data flow analysis Applications）

到达定义分析（Reaching Definitions Analysis）

algorithm

活跃变量分析（Live Variables Analysis）

algorithm

可用表达式分析（Available Expressions Analysis）

algorithm

小结

静态分析导论 - Introduction

概述

重要概念

AST vs IR

3AC（3-Address Code）

SSA（静态单赋值）

为什么使用SSA？

为什么不使用SSA？

控制流图（CFG）与基本块

Basic Block

两类分析

同步发生(synchronizes-with)

先行发生(happens-before)

线程间的互相作用：线程间的先行

原子操作的内存顺序

排序一致序列

非排序一致内存模型

自由序列

了解自由排序

释放序列

一些补充概念

引用和致谢

早期版本的步骤（如果你是新安装的Win系统或从 “启用或关闭Windows功能” 安装的wsl）：

如果你是从 Micosoft store 安装的WSL，或者你曾经运行过 wsl --update （也是 Store 版 WSL）：

如果你是从 Micosoft store 安装的WSL，或者你曾经运行过 `wsl --update` （也是 Store 版 WSL）：