Java高级主题：深度讨论官方关于jdk1.8ConcurrentHashMap的resizeStamp源代码修复逻辑

前言

首先给出以下open JDK版本的序号说明和Oracle JDK序号说明

（1）对于JDK8或者Java 8

即可指代openjdk-8-jdk或者java-1.8.0-openjdk，

也可指代Oracle家的Java SE 8或者JDK 8u211 and later

（1）对于JDK16或者Java 16

即可指代openjdk的JDK 16.0.2 ，也可指代Oracle家的Java SE 16或者 jdk16.0.1，这里为何给出Java 8和Java 16版本说明？

首先resizeStamp的bug在Java8出现，并在Java 12被修复，因此本文直接给出最新版Java 16作为bug修复前后对比即可。

以下做个约定：统一以Java X形式作为版本称号，CHM：ConcurrentHashMap的简称，以此减少阅读障碍。

在前面的文章中，关于Java 8 的CHM addCount方法里面分支2：resizeStamp和sc==rs+1、sc==rs+MAX_RESIZERS的讨论中，已经指出其bug嫌疑：

private final void addCount(long x, int check) {
// 分支1 省略...
  
// 分支2 
if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n); // 注意这里计算出的rs是正值
                if (sc < 0) {
                  	// sc是负值，怎么会等于rs+1或者rs + MAX_RESIZERS这个正值呢？ 有可能是个bug
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSetInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                s = sumCount();
            }
        }

官方bug描述

其实这个bug在open jdk的官方bugs主页已经给出相关解释和修复过程，链接：官方bug描述页面：

从Detail这一块描述得到信息如下：

bug的描述：ConcurrentHashMap.addCount()设计逻辑中可能存在bug。（这里虽然提到addCount()方法，但本人更想强调的是扩容分支的resizeStamp的bug）

级别是：bug

当前状态：已经修复

影响的版本：Java 11、Java12

在哪个版本得到修复：Java 12

使用操作系统平台：所有

bug页面创建时间：2018-11-26

解决bug的最后时间：2018-12-11

bug所属库：Java的核心库——core-libs

提交者的修复建议

In the above code, condition of (sc == rs + 1 || sc == rs + MAX_RESIZERS ) would never be true , since the value of rs is positive and the value of sc is negative .

译：条件 (sc == rs + 1 || sc == rs + MAX_RESIZERS )永远不可能true，因为rs的值为正数，而sc值为负数

并建议修改为：

The correct condition should be (sc >>> RESIZE_STAMP_SHIFT) == rs + 1 || (sc >>> RESIZE_STAMP_SHIFT) == rs + MAX_RESIZERS, which can be used to dedect if resizing process finished or resizing threads reaches maxmium limitation

译：正常的条件应该是这样： (sc >>> RESIZE_STAMP_SHIFT) == rs + 1 || (sc >>> RESIZE_STAMP_SHIFT) == rs + MAX_RESIZERS，这两个条件表示扩容任务已结束或者参与扩容的线程总数达到最大值

确实，这个bug非常明显，以分支2作为说明

int rs = resizeStamp(n)，以容量n=16作为说明，rs计算为下面的值

0000 0000 0000 0000 1000 0000 0001 1011

考察低16位，rs+1的结果显然是一个正数

0000 0000 0000 0000 1000 0000 0001 1100

rs+MAX_RESIZERS同理也是一个正数，接着判断条件if(sc<0)成立才能进入rs+1等条件，也即此时sc是一个负数（其实是因为首个扩容线程会将sc设为(rs << RESIZE_STAMP_SHIFT) + 2的一个基础负数），基于此，有提交者在这里发现的了bug：sc是负数，而rs+1是正数，因此sc==rs+1永远不会成立

官方关于此bug的讨论过程

JCP JSR-166 Expert Group （关于Java并发编程的规范提案的专家组）几个相关成员的对话过程即可知道他们对问题的思考和处理方式。

在Activity这个栏目就是用于提交者已经相关专家bug讨论过程，“All”是显示所有他们的活动记录，一般无需关注，“Comments”显示他们的对话过程，bug的讨论过程就在这里，因此需要重点关注，具体如下：

以下是来自“Comments”区域的内容：

(最开始由Webbug Group 这个小组提交了该issue - 2018-11-26 00:53)

Stuart Marks 说：

Stuart Marks added a comment - 2018-11-28 09:10

Martin, can you take a look at this?

Martin，来，帮我看看这个bug？

Martin的回答，主要意思是：bug提交者在查一个确实是由addCount产生错误计数，但Martin说他们也没有可以使用的压测案例，并建议使用者用多线程做压测来让addCount的这个bug复现，但这个bug不好复现。

Resizing the internal bucket array is hairy race-prone code, and hard to stress test because resizes are relatively rare.

The reporter probably investigated an actual occurrence of incorrect count (we could ask!), but we don’t have a stress test reproduction that could be used.

One should be able to construct a stress test using multiple threads to trigger concurrent attempts to addCount, but it won’t be easy.

David Holmes 对Martin说：

What is your analysis just based on the code and the report? It certainly appears incorrect to me.

你的分析只是基于代码以及提交的报告？这个bug在我看来显然是不正确的。

Martin回答David Holmes ：

Martin说自己也看了看源码但研究时间不够长，自己还没能搞懂其设计，然后说Doug应该记得这个设计！

I stared at the code for a while, but not long enough to understand it. Doug will remember!

Doug Lea added a comment - 2018-11-28 15:53:

Doug Lea看到这个bug，做了基本的分析：这个bug会影响到CHM性能也即有些线程不能参与到扩容任务中，并指出这个bug只是影响性能而不是一个引起map发生错误的bug，指出这个bug需要修复。

Yes. Some of this check now includes dead code, because of a change of representation at one point that wasn’t adjusted for. With the possible effect of some threads not helping resize (a performance, not map correctness bug) This should be fixed (and is committed in jdr166 repo):

然后他贴出修复前后的源码diff

--- ConcurrentHashMap.java.~1.314.~ 2018-10-05 13:42:39.860409607 -0400
+++ ConcurrentHashMap.java 2018-11-28 18:48:55.998082379 -0500
@@ -2307,9 +2307,9 @@
                    (n = tab.length) < MAXIMUM_CAPACITY) {
                 int rs = resizeStamp(n);
                 if (sc < 0) {
- if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
- sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
- transferIndex <= 0)
+ if ((sc >>> RESIZE_STAMP_SHIFT) == rs + 1 ||
+ (sc >>> RESIZE_STAMP_SHIFT) == rs + MAX_RESIZERS ||
+ (nt = nextTable) == null || transferIndex <= 0)
                         break;
                     if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
                         transfer(tab, nt);

可以看到判断条件变为:

if ((sc >>> RESIZE_STAMP_SHIFT) == rs + 1 ||(sc >>> RESIZE_STAMP_SHIFT) == rs + MAX_RESIZERS ||(nt = nextTable) == null || transferIndex <= 0)

根据修复的条件，可知rs是负数，因此(sc >>> RESIZE_STAMP_SHIFT) != rs 已经没有实际意义，因为(sc >>> RESIZE_STAMP_SHIFT)是一个正数，rs是一个负数，显然是不相等，因此(sc >>> RESIZE_STAMP_SHIFT) != rs是多余的。

这就是最终定稿修复源码吗？ 继续看后面的讨论

Pallavi Sonal (Inactive)](https://bugs.openjdk.java.net/secure/ViewProfile.jspa?name=psonal) added a comment - 2018-11-29 01:09

Pallavi Sonal收到提交者新的描述，

Additional Information from submitter:
I need to change the correct conditions given by me in the bug description ：

The correct condition shuold be

sc == ( rs<<<RESIZE_STAMP_SHIFT ) +1 || sc == ( rs<<<RESIZE_STAMP_SHIFT ) + MAX_RESIZERS

其实就是说一开始提交bug的描述中，两个条件应该是这样的形式：

(sc >>> RESIZE_STAMP_SHIFT) == rs + 1 || (sc >>> RESIZE_STAMP_SHIFT) == rs + MAX_RESIZERS

现在提交者应该是自己对扩容移位理解深入后，发现按下面这样写更能准确表达：

//int rs = resizeStamp(n);
sc == ( rs<<<RESIZE_STAMP_SHIFT ) +1 || sc == ( rs<<<RESIZE_STAMP_SHIFT ) + MAX_RESIZERS

本人也赞同这种建议：因为该if条件考察主体是以rs扩容戳的角度出发，因为rs由resizeStamp(n)计算出是正值:

0000 0000 0000 0000 1000 0000 0001 1011

因此将rs左移RESIZE_STAMP_SHIFT位后，扩容戳关键信息移动到高16位：

1000 0000 0001 1011 0000 0000 0000 000 （此时是一个负数）

然后再去判断sc == ( rs<<<RESIZE_STAMP_SHIFT ) +1 是否成立，这样才能符合rs的移位设计逻辑：高16位存放扩容印记信息，低16位用于存放扩容线程数量。

而sc >>> RESIZE_STAMP_SHIFT 的写法无法表达出“rs的高16位存放扩容印记信息，rs低16位用于存放扩容线程数量。”这种移位设计理念。

bug的复现方法

Pallavi Sonal最关键的贡献是提供了bug的复现方法，如下所示：

这里有个tricky：将MAX_RESIZERS设为2以及在transfer中挂起进入transfer线程 suspend Threads

This bug could be verifed by a small example :

1、将ConcurrentHashMap源码拷贝自己测试包目录下

First, copy the ConcurrentHashMap source code to your own package

2、还有其他相关的ThreadLocalRandom源码也要拷到自己项目包

Second, do some necessary modification to make it can be compiled (eg: change package declaration, make Unsafe instance works, copy ThreadLocalRandom to your package as well, since the ConcurrentHashMap used ThreadLocalRandom.probe() function, which is not public )

3、写个demo测试代码，以及在源码加一些修改（注意源码无法直接修改，可以选择拷到自己包下，个人推荐：最好的方式是在IDEA将SDKs 的Sourcepath替换自定义的源码目录，这样JDK源码就可以直接编辑，比上面提的方式要方便）

Third, reduce MAX_RESIZERS to 2, as the documentation shows, this should ensure there are at most 2 threads can do resizing concurrently

// CHM源码将MAX_RESIZERS数量设为2，以便观察进入transfer的线程数量

private static final int MAX_RESIZERS = 2;

Fourth, add the following code snippet into the customized ConcurrentHashMap class

public static void main(String[] args) {

ConcurrentHashMap hashMap = new ConcurrentHashMap(8);

for(int i = 0; i< 300; i++)
{
new Thread() {
@Override
public void run() {
hashMap.put(Thread.currentThread().getId(),”id: “+Thread.currentThread().getId());
}
}.start();
}
}

5、在transfer方法指定埋入一些让线程挂起的代码

Fifth, add the following code snippet into the transfer function of ConcurrentHashMap . To suspend any thread that entered into transfer

if (nextTab == null) { // initiating
try {
@SuppressWarnings(“unchecked”)
Node[] nt = (Node[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}

// The following added code here is to suspend Threads !!!! 在这里挂起线程
try {
String s = new String();
synchronized (s)
{
s.wait();
}
} catch (InterruptedException e) {
e.printStackTrace();
}

6、在以下 addCount 代码片段加入断点，并使用IDEA的 “Thread” option来测试
Six, add the Thread break point in the following code line in addCount function

( Tip: I used Idea Intellij , choose “Thread” option can suspend each thread in your application , otherwise it will only suspend only the first Thread which executed to the break point)

​ if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
​ transfer(tab, nt);
enter image description here

debug后会发现进入transfer方法的线程数量超过2个，这就可以证明sc==rs+MAX_RESIZERS完全没有起效，因为按原始写法：sc是负值，rs是正值，sc==rs+MAX_RESIZERS 本身不会成立，当然无法限制进入扩容逻辑线程的总数量

Then run the main function, you will see more than 2 threads entered transfer function, which means MAX_RESIZERS does not take any effect.

复现这个bug设计思路确实操作性很高！

Doug Lea added a comment - 2018-12-02 08:00

其实由于上面已经给出bug复现方法，Doug Lea肯定更加清楚问题所在，因此他说helpTransfer方法也有这个问题，最后他用了更加简化的移位表达式来修复这个bug，并且Doug Lea也亲自验证修复后条件是否能起到相关效果。

A similar change is also necessary in helpTransfer. These together with a simplification of the shift expressions are now in jsr166 repo. I also verified that limits are maintained.

bug修复的代码最终提交到仓库：

HG Updates added a comment - 2018-12-11 20:16

URL: http://hg.openjdk.java.net/jdk/jdk/rev/b4eaf570a588
User: martin
Date: 2018-12-12 04:13:15 +0000

8214427: probable bug in logic of ConcurrentHashMap.addCount() Reviewed-by: martin, dholmes

author	dl
date	Tue, 11 Dec 2018 19:55:27 -0800 (2018-12-12)
parents	c7c285b0b640
children	a35f7a452257
files	src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java
diffstat	1 files changed, 7 insertions(+), 9 deletions(-) [+])

修复代码提交者应该是Doug Lea，因为dl是(D)oug (L)ea的缩写，Reviewed-by：martin, dholmes

具体为diff如下：

+++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java	Tue Dec 11 19:55:27 2018 -0800
// 以下是addCount方法的源码修复 
@@ -2334,17 +2334,15 @@
             Node<K,V>[] tab, nt; int n, sc;
             while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                    (n = tab.length) < MAXIMUM_CAPACITY) {
                 // 删除原先的写法   
-                int rs = resizeStamp(n);
								 // 直接在这里对rs进行左移位操作
+                int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
                 if (sc < 0) {
-                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
-                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
-                        transferIndex <= 0)
									// rs左移后，(sc >>> RESIZE_STAMP_SHIFT) != rs是多余也是无实际意义条件，直接删除
									
+                    if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
+                        (nt = nextTable) == null || transferIndex <= 0)
                         break;
                     if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
                         transfer(tab, nt);
                 }
-                else if (U.compareAndSetInt(this, SIZECTL, sc,
-                                             (rs << RESIZE_STAMP_SHIFT) + 2))
				//显然这样看起来更容易理解：首个进入扩容逻辑的线程，将sizeCtl设为基础值rs+2
+                else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
                     transfer(tab, null);
                 s = sumCount();
             }
@@ -2358,11 +2356,11 @@
				 // 以下是helpTransfer方法的源码修复 
         Node<K,V>[] nextTab; int sc;
         if (tab != null && (f instanceof ForwardingNode) &&
             (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
             // 同上
-            int rs = resizeStamp(tab.length);
+            int rs = resizeStamp(tab.length) << RESIZE_STAMP_SHIFT;
             while (nextTab == nextTable && table == tab &&
                    (sc = sizeCtl) < 0) {
-                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
-                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
+                if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
+                    transferIndex <= 0)
                     break;
                 if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
                     transfer(tab, nextTab);

在Java 16源码验证其修复的代码

上面提到bug在Java 12就被修复了，考虑到当前最新的jdk版本为Java 16，因此可在JDK16验证其修复的源码，修改处为下面的三个更改：

private final void addCount(long x, int check) {
  CounterCell[] cs; long b, s;   
  		// 省略部分...
  		// 分支2
			if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                // 更改1
                int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
                if (sc < 0) {
                  	// 更改2
                    if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
                        (nt = nextTable) == null || transferIndex <= 0)
                        break;
                    
                    if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
              	// 更改3
                else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
                    transfer(tab, null);
                s = sumCount();
            }
        }
    

可以看到，rs移位操作设计简化了，逻辑容易理解，这里再次给出分支2的解释：

private final void addCount(long x, int check) {
  CounterCell[] cs; long b, s;   
  		// 省略部分...
  		// 分支2
			if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                // 更改1:将扩容印记先左移16位，以便低16位用于线程数量累计。显然此时rs是一个负数
                int rs = resizeStamp(n) << RESIZE_STAMP_SHIFT;
                if (sc < 0) {
                  	// 更改2：原来的条件1已被删除，原因已在前面给出。
                  	// 若一个线程遇到以下四种情况之一就会自行break结束：扩容的线程总数达到最大限制值或者扩容任务已结束（所有扩容线程已退出）或者nextTable为空，或者已经没有可分配的桶位。条件1和条件2参考下图加深理解。
                    if (sc == rs + MAX_RESIZERS || sc == rs + 1 ||
                        (nt = nextTable) == null || transferIndex <= 0)
                        break;
                    // 除去首个扩容线程，以后每来一个扩容线程就对sc加1，参考下图
                    if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
              	// 更改3：首个扩容线程对sc设为基础值为：rs+2后再进入transfer方法参与扩容，这种写法比之前版本要清晰很多，从这里也可以推导出：当sc的值为rs+1时，就能说明当前所有扩容线程都退出了扩容逻辑，CHM扩容完成。
                else if (U.compareAndSetInt(this, SIZECTL, sc, rs + 2))
                    transfer(tab, null);
                // 当前线程再次获取CHM的节点总数，然后回到上面while循环检查s有无达下一个阶段扩容阈值sizeCtl，如果需要进行下一阶段扩容，那么当前线程又会回到更改3的位置：作为下一节点扩容的首个扩容线程。
                s = sumCount();
            }
        }
    

解析本次bug的带来的技术收益

为何要如此详细的分析官方修复的这个bug呢？

最直观明显的技术收益：当你能对源代码的bug有深刻认识，并且知道专家组成员对bug的讨论以及修复过程，那么其实你对CHM的设计理念和源码实现能掌握得相当深入，感觉像是你也参与了CHM的部分源码编写，无形中对提高个人高级开发能力有一定帮助。

其次，当你知道有这么一个“open JDK bugs官方提交系统”，也许当你在研究难度比较高的源码设计时，若你能发现bug，你也可以提交，以此证明自身掌握高级研发能力程度。

最后，这个官方bugs提交系统也可以帮助个人快速找到想要深入解析的包或者类的关键设计原理，因为页面含有非常详细的bug描述、bug复现方法、bug出现原因分析、bug的代码修复。

查询页面如下：

基本用法也简单：在Projects里面选择你关注的领域，例如JDK，若不想加其他条件，可以直接使用关键字去检索你想要研究的源码

bugs系统还给出另外与resizeStamp相关的bug

不过是这个bug是提交者自己闹的乌龙，bug页面链接

提交者提交的描述：Bug in the logic of ConcurrentHashMap.addCount() when used in Threads

他认为主要问题不是sc==rs+1这边负数那边正数，而是应该关注当前数组的容量要两倍于原表

因此他认为if条件应该这么该：

将sc==rs+1 应该改为(sc >>>RESIZE_STAMP_SHIFT) == (rs>>>RESIZE_STAMP_SHIFT) + 1

A DESCRIPTION OF THE PROBLEM :
At java.util.concurrent.ConcurrentHashMap#addCount:2339
i think the condition is if the thread is reach maximum or the new table size is twice as before or the nextTable is null or the transferIndex is lesss than zero; the bug in jdk8 is “https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427“ , i think the main thing is not one is positive another is negtive, but the new table size is twice as before.
at jdk12 i think is not fix it, “sc == rs + 1” compare the work thread but not array size, i think the code should be

if (sc == rs + MAX_RESIZERS || (sc >>>RESIZE_STAMP_SHIFT) == (rs>>>RESIZE_STAMP_SHIFT) + 1 ||
(nt = nextTable) == null || transferIndex <= 0)
break;
rather than

if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;

REGRESSION : Last worked in version 8

FREQUENCY : always

到后面，提交者发现原来是自己理解错了，并再次加了以下comments：

他说很抱歉提交这样的bug，是他自己想错了，他以为(sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 这两个条件是用于描述检查数组size，其实不是的。他最终理解了sc == rs + 1 这样的条件目的在于对参与线程线程数量的计数

Additional Information from Submiiter:
I am so sorry for submiting it. at jdk 1.8 “java.util.concurrent.ConcurrentHashMap#helpTransfer:2304”, i think “(sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 “ is check the array size ,but yesterday i found that thinking of “ sc == rs + 1” as checking the count of thread was better.

个人评价：

首先这个提交者没有真正理解和掌握resizeStamp的设计理念，以及这if中相关条件的用意，

既然这个提交者说将sc == rs + 1 改为(sc >>>RESIZE_STAMP_SHIFT) == (rs>>>RESIZE_STAMP_SHIFT) + 1才合理，为何他又不会将sc == rs + MAX_RESIZERS 改为:

(sc >>>RESIZE_STAMP_SHIFT) == (rs>>>RESIZE_STAMP_SHIFT) + MAX_RESIZERS

基于此，说明提交者没有真正理解这两个条件的实际目的， 所以他提的描述以及修复是不合理的，从Comments也可以看到那些专家对提交者提到的bug不感冒也可看出，这次提交的bug修复申请似乎意义不大：

We need a clearer explanation of what we're fixing here
...
but we need better input from the reporter.

最后由提交者回复I am so sorry for submiting it. 结束。

从这个案例也告诉大家，对于JDK级别这种bug的提交，首先提交者自己能理解相关源码设计和实现，最好有测试case，然后给出详细的而准确的描述，如果提交者自己还未搞懂相关逻辑就急着提交，最后可能闹个笑话。

关于sizeCtl一个bug

这个bug比较简单，描述页面链接

它指出：sizeCtl在构造方法初始化时，选用同一个容量，但用以下不同的构造方法，结果发现两者计算出的sizeCtl不一样

public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel)

public ConcurrentHashMap(int initialCapacity)

具体bug例子：

The following two statements:

new ConcurrentHashMap(22,0.75f,1);
new ConcurrentHashMap(22).

The first construct method makes sizeCtl field value to 32, but the second one makes sizeCtl to 64.Both the two construct methods use the same parameter value. I think they should make the ‘sizeCtl’ value to be the same.

对于给定的初始容量22来说，易知计算后sizeCtl正常值为32，但前一个构造方法计算出的sizeCtl是32，后一个构造方法计算出的sizeCtl是64，因此出现bug。

感兴趣的同学，可以自行研究其修复过程，本文不再给出相关说明。

resizeStamp的bug复现方法（非常关键）

源代码修复前的复现过程

文章最前面提到的JDK-8214427提交者确实是一个有水平且能深入理解源码的人，他还给Doug Lea他们提供了复现问题的6个步骤，思路清晰，因此本节也按其步骤给出IDEA debug过程，如下：

1、使用IDEA创建一个普通（Java或者Maven）项目，并在java目录下创建包concurrent.demo（或者自行命名），将源码文件ConcurrentHashMap.java、ThreadLocalRandom.java拷贝到包concurrent.demo下，创建ResizeStampBugTest用于测试，最终项目结构如下

├── src
│   ├── main
│   │   ├── java
│   │   │   └── concurrent
│   │   │       └── demo
│   │   │           ├── ConcurrentHashMap.java
│   │   │           ├── ResizeStampBugTest.java
│   │   │           └── ThreadLocalRandom.java
│   │   └── resources

这两个源码文件在哪里找？简单问题不再回答。

2、修改ConcurrentHashMap.java和ThreadLocalRandom.java里面的Unsafe代码，使得Unsafe类在自己项目上可以使用

因为源码文件已经拷贝到自己项目下，因此可以对其进行编辑

对于ConcurrentHashMap.java的Unsafe代码修改（注意有两个Unsfafe地方都需要修改）：

// 以下三行是新增，通过反射获得的Unsafe实例      
      Field field = Unsafe.class.getDeclaredField("theUnsafe");
      field.setAccessible(true);
      U = (Unsafe) field.get(null);

// 以下是源码获取Unsafe的写法，注释它即可
    // U = sun.misc.Unsafe.getUnsafe();

对于ThreadLocalRandom.java的Unsafe代码修改方法也同上：

    // 以下三行是新增，通过反射获得的Unsafe实例      
       Field field = Unsafe.class.getDeclaredField("theUnsafe");
       field.setAccessible(true);
       UNSAFE = (Unsafe) field.get(null);
// 以下是源码获取Unsafe实例的写法，注释它即可
// UNSAFE = sun.misc.Unsafe.getUnsafe();

3、在transfer方法的代码片段位置加上能让当然线程挂起的代码

        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
    // 打印挂起的线程      
            System.out.println(Thread.currentThread().getName()+":线程挂起");
    // 本文使用的是LockSupport的park方法将当前线程挂起，其实内部调用了UNSAFE.park。this表示当前代码块。这种写法在TreeBin的读写锁竞争设计里面有被运用过。    
            LockSupport.park(this);
// 以下是提交者提供让线程挂起的写法之一，建议使用park方法来简直明了        
// The following added code here is to suspend Threads !
//            try {
//                String s = new String();
//                synchronized (s)
//                {
//                    System.out.println(Thread.currentThread().getName()+":线程暂停");
//                    s.wait();
//                }
//            } catch (InterruptedException e) {
//                e.printStackTrace();
//            }

4、更改其他常量属性

 	// 将桶位分配步长改为2，也即对一个容量为16的CHM，可以同时4个线程并发迁移各种桶位，也即至多有个4个线程能进入transfer方法
	private static final int MIN_TRANSFER_STRIDE = 4;
// 注释对应源码
  //private static final int MIN_TRANSFER_STRIDE = 16;



	//将MAX_RESIZERS设为3，由之前的CHM文章可知，实际参与到扩容线程数量为MAX_RESIZERS-1个，
	private static final int MAX_RESIZERS = 3;
	//注释对应源码
	//private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

5、使用断点位置1复现bug

JDK-8214427的提交者给出可以在AddCount的分支2以下两行打上断点

if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)){
    transfer(tab, nt);
}

在IDEA执行debug可以查看到以下每个线程方法调用栈的情况：（以下默认读者已经熟悉IDEA多线程调试操作以及相关界面的含义。）

而且是多个线程被观测：从线程Thread-12到Thread63都可以被观测。

这里需要解释为何是从IDEA捕抓到RUNNING状态的是线程Thread-12开始，而是不是从Thread-0开始？

因为前面第0号到10号线程总共put 入了11个节点（put结束后，这些线程发现不用扩容故结束），接着线程Thread-11去put节点完后发现此时CHM节点数量达到扩容阈值12（16*0.75），线程Thread-11就开始进入以下代码，可见线程Thread-11是作为首个进入扩容线程，但这里不是IDEA断点位置，这就是前面0到11线程不会在IDEA Frames或者Threads界面出现。

else if (U.compareAndSwapInt(this, SIZECTL, sc,
                             (rs << RESIZE_STAMP_SHIFT) + 2)){
    transfer(tab, null);
}

又因为后续来了线程Thread-12put如节点后也发生s达到扩容阈值，会进入以下代码对sc加1计数，而这恰好是断点位置，因此线程Thread-12会IDEA 放入观测Frames中，而且线程Thread-12还是处于RUNNING状态

if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)){
    transfer(tab, nt);
}

同理后续的线程Thread-13、Thread-14…… 直到线程Thread-63都会被IDEA放入观测Frames中，如下图所示：
有了以上铺垫，现在如何在Debug界面将bug复现？

现在回顾文章开头提出源码（如下代码片段）中出现的问题：sc=rs+1以及sc=rs+MAX_RESIZERS不会成立，因此sc本身为负数，rs这边为正数，因此if中的sc == rs + MAX_RESIZERS 限制参与扩容线程的总数量的条件不会起效

if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
    transferIndex <= 0){
    System.out.println(Thread.currentThread().getName()+"因无桶位可分配，此线程直接退出");
    break;
}

那么如何证明呢？很简单，因为我们前面已经将 MAX_RESIZERS设为3，表示最多只允许 (MAX_RESIZERS-1)也即最多只能有2个线程进入扩容逻辑transfer方法，如果在IDEA界面观测到3个以上线程进入扩容逻辑transfer方法，说明bug成功复现，操作过程如下：

（1）在Frames界面，线程选择下拉框中选中一个线程，例如Thread-12，点击Step Over 跳过断点位置1的sc+1计数，接着点击Step Into 让线程在断点位置2进入transfer方法 ，此时在Thread-12的方法调用栈上出现transfer方法帧：

（2）同理选中其他线程按（1）的“Step Over—>（多次）Step Over—>Step Into”操作,你发现超过2个线程都能进入transfer方法，其实后面的线程都可以进入transfer方法。这里不再一一给出图示。

这里为何说是（多次）Step Over呢，因此Thread-12 抢到CAS对sc加1，那么Thread-13只能回到While处再次来到断点位置去竞争CAS，所以需要对Thread-13（多次）Step Over。

（3）经过以上环节可以看到总共有64号到11号共24个线程能进入扩容逻辑，bug得到完美复现。

6、使用断点位置2复现bug

在5提到的方法中，需要手动Step Over—>（多次）Step Over—>Step Into操作将线程执行流进入到transfer方法，线程数量多，这么一个个操作去观察，显然方式很不smart。考虑另外一种方式：

去掉原来两个断点，新增一个断点，打在以下位置：

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;  // 断点位置

给断点设置线程“Suspend条件”：

断点条件：tab.length==16 && nextTab !=null ，表示CHM还在容量为16阶段的扩容流程中，那么此时一定会有线程进入到transfer方法里面，通过查看Frames，你可以发现有很多扩容线程，也再次使得bug完美复现，这里不再累赘。

源代码修复后的验证过程

本小节尝试将源代码修复后，观测进入transfer线程的数量是否与（MAX_RESIZERS-1）设定的总数一致，如果一致，说明源码修改的逻辑可接受：将AddCount方法的分支2改为正常的写法后，断点位置如下：

if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { // 断点
    transfer(tab, nt); // 断点

在transfer方法中加入线程挂起代码LockSupport.park(this)：

if (nextTab == null) {            // initiating
    try {
        @SuppressWarnings("unchecked")
        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
        nextTab = nt;
    } catch (Throwable ex) {      // try to cope with OOME
        sizeCtl = Integer.MAX_VALUE;
        return;
    }
    nextTable = nextTab;
    transferIndex = n;
    LockSupport.park(this);

观测过程：根据前面分析可知，从线程Thread-12到Thread-63都会同一时刻来到sc+1计数逻辑进行CAS竞争，接下来的IDEA Debug步骤如下：

（1）选中Thread-12，对其执行sc+1计数逻辑进行CAS竞争，因此Thread-12优先来sc+1这个位置并CAS竞争成功，它可进入transfer内部。

（2）接着选中Thread-13，对其执行sc+1计数逻辑进行CAS竞争，因为竞争失败，因此回到While循环继续：

图中可以清晰看见：sc==rs+MAX_RESIZERS 为true，表名当前参与到扩容线程的数量达到最大的限定值，Thread-13将会进入break然后退出

（3）同理选中Thread-14等后续线程也会跟Thread-13同一逻辑，

也即，Thread-13到Thread-63线程都会break掉

（4）在（1）中只有1个线程Thread-12进入transfer内部，不是说好会有（MAX_RESIZERS-1），也即2个线程能进入transfer内部吗？

别忘记线程Thread-11已经通过以下逻辑作为第1个扩容线程进入了transfer方法内部

else if (U.compareAndSwapInt(this, SIZECTL, sc, rs + 2)){
    transfer(tab, null);
}

因此总共有2个线程：Thread-11和线程Thread-12进入到transfer方法内部，说明修复之后的代码逻辑正确。