JDK1.8 ConcurrentHashMap死锁Bug

Introduce this bug

在js介绍完seata之后，我闲来无事跑到seata官网的blog逛逛：blog link

Snipaste_2022-03-23_11-27-07 然后被这个标题深深吸引【ConcurrentHashMap导致的Seata死锁问题】，虽然其他全部都是知识点，默默流下了技术的泪水😭😭

点进去我们猛一顿操作，会找到这个网站（openjdk bug集合网站）：openjdk bug web

接下来我们先认真分析下这个Bug，居然大名鼎鼎的CHM都有死锁的问题。

从上面的截图，我们可以知道这个bug大概是什么东西

ConcurrentHashMap.computeIfAbsent有个死循环，这是一个jdk的bug，不是业务的bug。然后这被Doug Lea在JDK1.9的时候才修复了这个bug。

为什么特别指出修复人是Doug Lea呢？

因为ConcurrentHashMap的作者就是这位老板～～

为了进一步讨论，导致是怎么导致的，我们先来看看computeIfAbsent是干啥子的。

If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. 

如果key对应的value不存在，则调用mappingFunction函数的执行结果（不为null）建立映射

The entire method invocation is performed atomically, so the function is applied at most once per key. 

这个方法是原子的，线程安全的

Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

不建议这个方法执行太复杂的操作，因为在更新的过程，其他线程的操作将会阻塞。更不建议在这个mapping执行更新操作

The default implementation is equivalent to the following steps for this map, then returning the current value or null if now absent:

默认实现如下
  
 if (map.get(key) == null) {
     V newValue = mappingFunction.apply(key);
     if (newValue != null)
         map.put(key, newValue);
 }

具体例子：

到此我们知道了computeIfAbsent的用法了。但是具体是怎么导致死循环的bug，我们还没展示讲。别急～我们马上进入bug演示。

How to reproduce the bug

我们直接在附件中找到这100%复现的bug

private static void chmBug() {

    Map<String, Integer> map = new ConcurrentHashMap<>(16);

    map.computeIfAbsent(
            "AaAa",
            // if the computation detectably attempts a recursive update to this map that would otherwise never complete
            key -> map.computeIfAbsent("BBBB", key2 -> 16)
    );

    log.info("end method,map:{}", map);
}

理论上，我们期望上面运行的结果是{BBBB=16, AaAa=16}。但是我们发现end method这句日志永远没有被打印。

我们通过Pardeep老板的描述可以很清晰知道bug原因，这位老板还给了上面最小原型复现bug的代码。

还是针对该问题给出解决方案：在文档中明确写出，不要在代码中写出递归调用该方法更新/新增map操作，否则会陷入死循环。并且要抛出IllegalStateException

最后Doug Lea无条件采纳。

Source code analysis

接下来我们进入大家喜闻了见的源码分析流程。

上面Pardeep大佬说”AaAa”和”BBBB”在CHM中有相同的hashCode。

"AaAa"->2031744
"BBBB"->2031744

从上面的截图我们可以看到这相同hashCode是本次bug的导火索。在ConcurrentHashMap第1649行是一个死循环，只有满足条件的地方才break。

当AaAa第一次进入循环，执行到1⃣️的时候，初始化table，

当AaAa第二次进入循环，执行到2⃣️，根据计算出数组下标，判断该下标的Node为空，进入逻辑：

第3⃣️步，创建出临时的Node，并且执行CAS替换数组下标为空的Node。
第4⃣️步，设置binCount=1，跳出循环的依据，mappingFunction.apply执行获取value，进入我们BBBB的流程computeIfAbsent的操作

进入重点BBBB的流程分析：分析会进入这个死循环，退出步了。

第一步是数组不为空，跳过初始化
第二步是获取根据hashCode获取数组下标，是否为空。因为AaAa已经生成了临时Node抢占了位置，不满足条件，跳过。
第3-1步是判断是否在扩容中，获取到的f=-3(transient reservations短暂的临时对象)，不符合-1(扩容)，跳过。
第3-2步是else，进入逻辑我们最终冲击的逻辑了。

我们接着分析3-2的内部逻辑。

第3-3步从上面的第二步，我们知道了是相同对象（AaAa）创建的临时对象，符合。进入逻辑。
第3-4步fh= -3，不满足。
第3-5步不是二叉树，不满足跳过。
最后的binCount代表这个下标里面，有几个node节点。很明显我们一个都没有。

哦嘿，进入了一次新的循环，死循环死锤。

我们使用arthas来分析下，这个死循环。

How to fix

我们已经确定这个是死循环了，接下来我们要去看怎么解决这个问题。

在JDK1.9版本中修复了这个bug，我们看下是怎么修复的。

解决方案也很简单，在最后else分支里面，最后的else if里面判断当前坐标里面的Node是不是临时节点，如果是直接抛出异常 IllegalStateException。

Dubbo在2.7.7修复了ConcurrentHashMap有可能导致死锁的问题，具体可以看下图红框部分：

dubbo具体怎么修复的呢？我们看下具体的commit记录

最后，我们来看看seata是怎么解决这个死循环的

SeataDataSourceProxy dsProxy = dataSourceProxyMap.get(originalDataSource);
if (dsProxy == null) {
    synchronized (dataSourceProxyMap) {
        dsProxy = dataSourceProxyMap.get(originalDataSource);
        if (dsProxy == null) {
            dsProxy = createDsProxyByMode(dataSourceProxyMode, originalDataSource);
            dataSourceProxyMap.put(originalDataSource, dsProxy);
        }
    }
}
return dsProxy;

使用双重检查锁的方式替换ConcurrentHashMap#computeIfAbsent的方法

参考链接

seata deadlock

dubbo-2.7.7 release

JDK1.8 ConcurrentHashMap Bug

why