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 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2645
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

3859
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4848
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4025
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3145
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5317
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2707
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2577
来自专栏杨龙飞前端

scrollto 到指定位置

2504

扫码关注云+社区