数据流分析（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）
• 基于控制流的约束

传输函数约束的符号表示

两种类型：

1. 正向分析（forward analysis）
   OUT[s] = f_s(IN[s])

2. 反向分析：（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）：

参见图表

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

1. 到达定义分析（Reaching Definitions Analysis）
2. 活跃变量分析（Live Variables Analysis）
3. 可用表达式分析（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是可用的，如果

1. 所有从入口到p一定经过x op y的求值；
2. 在最后一个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

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

概述

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

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

1. 词法分析（Lexical Analysis）：将源代码转换为令牌流。
2. 语法分析（Syntax Analysis）：将令牌流转换为抽象语法树（AST）。
3. 语义分析（Semantic Analysis）：对AST进行类型检查和语义检查，生成带有语义信息的修饰AST。
4. 翻译（Translation）：将修饰AST翻译为中间表示（IR）。
5. 静态分析（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

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

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

同步发生(synchronizes-with)

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 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()的执行顺序未被指定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 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不需要任何对获取-释放序列添加额外的指令(没有保证原子性的必要了)，并且，即使是排序一致序列，对于加载操作也不需要任何特殊的处理，不过在进行存储时，有点额外的消耗。

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

排序一致序列

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#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，就不需要任何额外的同步，对于每个变量的修改顺序只是线程间共享的事情。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// 非限制操作只有非常少的顺序要求
#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所示(只是其中一个可能的结果)。尽管，在不同的存储/加载操作间有着先发执行关系，这里不是在一对存储于载入之间了，所以载入操作可以看到“违反”顺序的存储操作。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

/*
你拥有三个全局原子变量①和五个线程。每一个线程循环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);
}

程序一种可能的输出为：

1
2
3
4
5

(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，并按照这样的顺序依次循环。对于输出，需要注意的一些事是：

1. 第一组值中x增1，第二组值中y增1，并且第三组中z增1。
2. x元素只在给定集中增加，y和z也一样，但是增加是不均匀的，并且相对顺序在所有线程中都不同。
3. 线程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

感谢该书作者和译者。

wsl1适用版：

1
2
3
4
5
6
7
8
9
10
11
12
13

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适用版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 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本机时也会被错误转发到宿主机代理然后访问成宿主机，导致一些程序出错。

windows用户：

1

netsh interface tcp set global timestamps=enabled

linux用户：

1

sysctl -w net.ipv4.tcp_timestamps=1

首先说结论，这个问题（在我所遇到的情况中）大多数是由于加速器软件或者全局代理类软件修改了系统的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）：

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

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

1
2
3
4
5

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 版本有不同的安装文件夹名。

步骤：

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

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

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

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

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

1
2
3
4
5

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

示例 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序列

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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

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

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

答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
};

参考资料：

• C语言中四种取整方式,取余/取模运算以及负数取模问题详解
• 2020字节跳动面试算法题—十进制转负3进制

记录一下：

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