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类型导致的良性和错误的数据竞争。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏贾老师の博客

一致性哈希 Consistant Hash

1165
来自专栏猿人谷

对缓存的思考【续】——编写高速缓存友好代码

开篇 上一篇博文对缓存的思考——提高命中率详细介绍了高速缓存的组织结构,并通过实例说详细明了cpu从高速缓存中取数据的过程,对于缓存的工作机制应该有了清晰的认识...

19410
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

781
来自专栏吉浦迅科技

DAY32:阅读local Memory

803
来自专栏大神带我来搬砖

分布式系统小知识:Apche Storm可靠性机制里为什么要采用异或来判断消息得到完整性处理?

想起这个问题,是因为知乎上有人提问,https://www.zhihu.com/question/48583003/answer/111853985 stor...

27410
来自专栏决胜机器学习

Redis专题(四) ——Redis排序、消息队列、优化存储

Redis专题(四) ——Redis排序、消息队列、优化存储 (原创内容,转载请注明来源,谢谢) 一、排序 1、命令 SORTkey [A...

3337
来自专栏用户画像

3.2.7 地址翻译

 因为本系统以字节编址,页面大小为64字节,则页内偏移址为log2(64B/1B)=6位,

721
来自专栏逆向技术

16位汇编第八讲指令第四讲

        16位汇编第八讲指令第四讲 一丶串操作类指令 1.什么是串操作?   1.串操作指令是8086指令系统中比较独特的一类指令,采用比较特殊的数据串...

1846
来自专栏码匠的流水账

分布式id生成方案概述

对于每个标识,都需要有一个命名空间(namespace),来保证其相对唯一性。 分布式的ID生成,以Twitter Snowflake为代表的, Flake 系...

502
来自专栏xingoo, 一个梦想做发明家的程序员

Redis初级介绍

1 什么是Redis Redis(REmote DIctionary Server,远程数据字典服务器)是开源的内存数据库,常用作缓存或者消息队列。 Redis...

1759

扫码关注云+社区