Ad-hoc类型同步识别

尽管之前的我们提出的动态数据竞争验证和检测方法能够比较精确地找到数据竞争，但是该方法还是会存在一部分误检，误检主要就是由于ad-hoc类型的同步引起的，下图展示了两个例子。

ad-hoc示例

图(a)中动态数据竞争验证和检测方法会报告出两个数据竞争L1，L4和L2，L3。其中L2和L3对于FLAG的访问其实就是一个ad-hoc类型的同步，是一种良性的数据竞争，同时L1必定在L4之前发生，这两个操作不存在数据竞争。

图(b)中动态数据竞争验证和检测方法会报告出来两个数据竞争L1，L3和L2，L3。其中这三个访问构成一个ad-hoc类型的同步，也是一种良性的数据竞争。

Ad-hoc类型的同步指的就是用户自定义的一些简单同步。程序员使用ad-hoc类型的同步主要的目的就是尽量减少程序中过多使用确定性同步带来的性能开销。这篇文章主要研究的是由对端写（counterpart write）和自旋读（spinning read）构成的ad-hoc类型的同步，如上图所示。本文提出一种动静结合ad-hoc类型同步识别方法，主要分为如下几个阶段：

Phase1：静态识别潜在的ad-hoc类型的同步

静态识别潜在的ad-hoc类型的同步主要是为在动态时更加精确地定位ad-hoc类型同步收集必要相关的信息。由于在静态时精确地定位对端写比较困难，因此我们在静态时主要用来识别潜在的自旋读循环相关信息。这部分主要分为如下几个步骤：

1. 找到所有的循环 对于C/C++程序来说，循环主要包括while、do-while、for以及goto-label这四种类型。其中前三种利用一些已有的静态分析工具比较容易识别，最后一种稍微复杂一些。识别goto-label循环，主要就是遍历每一个函数中label和goto语句，然后对goto语句集合进行倒排，对label语句集合进行正排。然后就遍历label语句找到第一个能够匹配的goto语句。
2. 剔除计算型循环 对端写和自旋读构成的循环一般来说结构都比较简单并且包含的语句比较少。因此我们通过控制流图能够轻松得到循环中块的数量，超过5就会被认为是计算型循环。同时，如果循环开始到结束的语句包含超过10的话，也会被认为是计算型循环。
3. 找到循环中所有的退出条件 循环中的退出条件主要包括两类，一类是循环自带的控制表达式，在while、do-while以及for循环中；另外一类是使用break、return、goto语句退出循环。根据这些退出循环标识，就能够找到对应的循环退出条件分支，即if-else分支。
4. 剔除计算型循环退出条件 如果上述找到的循环退出条件分支和共享变量的读不存在任何直接或是间接地数据依赖，那么这个循环退出条件就是计算型的。同时，如果循环退出条件相关的共享变量在循环中有写访问，那么同样循环退出条件也是计算型的。
   

   反例
   图(a)中由于cnt不是共享变量，并且不存在和共享变量之间存在数据依赖，因此肯定不是自旋读循环。图(b)中while中仅仅的一个循环退出条件直接和共享变量相关，但是该共享变量在循环中有写访问，因此也不是自旋读循环。图(c)中ptr指向共享变量flag，但是在循环退出条件中是调用了相关的函数，对于这种情况，我们会继续深入该函数进行相关的分析，但也仅仅停留在该函数中，并不会继续深入下去。

完成上述4个捕捉之后，如果循环中不存在任何我们期待的退出条件，那么该循环就不是自旋读循环。

这样，我们就通过静态分析得到了自旋读循环相关的信息。

Phase2：动态确认ad-hoc类型的同步

根据静态得到的潜在的自旋读循环，我们在动态是监视相关的自旋读访问，同时也会监视对共享内存空间的最后一次写访问。当自旋读线程即将执行条件退出分支的第一条语句或是执行循环外的第一条语句，此时才会确认ad-hoc类型的同步。

这样的话，通过动静结合的ad-hoc类型同步识别，我们能够剔除一部分良性和错误的数据竞争，进一步优化我们的数据竞争报告。

下表展示了我们进一步实验结果：

结果

同样也是针对Unittest程序进行测试，其中VD表示就是我们之前提出的动态数据竞争验证和检测方法，而PVD是之前提出的并行化的动态数据竞争验证和检测方法，而VDP表示就是动态数据竞争验证和检测方法执行之后，再执行动态ad-hoc类型同步确认方法。从这张图表中可以明显的发现我们剔除了大部分ad-hoc类型导致的良性和错误的数据竞争。