java - 如何在ConcurrentHashMap(JDK1.8或更高版本)的addCount函数中实现条件(sc == rs + 1 || sc == rs + MAX_RESIZERS)

Question

我在ConcurrentHashMap中阅读了addCount函数的源代码，
但我不知道什么时候可以实现( sc == rs + 1 || sc == rs + MAX_RESIZERS)条件。

为什么不使用sc == ( rs<<<RESIZE_STAMP_SHIFT ) +1 || sc == ( rs<<<RESIZE_STAMP_SHIFT ) + MAX_RESIZERS
在ConcurrentHashMap(JDK1.8或更高版本)的addCount(long x, int check)函数中，有一些如下代码

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);

        if (sc < 0) {
            // the problem is here : 
            // the condition sc == rs + 1 ||  sc == rs + MAX_RESIZERS
            // seems always to be false
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)

                break;
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                transfer(tab, nt);
        } else if (U.compareAndSwapInt(this, SIZECTL, sc,
                (rs << RESIZE_STAMP_SHIFT) + 2))
            transfer(tab, null);
        s = sumCount();
    }
}

我已经做了一些研究工作，以了解resizeStamp(n)的工作方式以及可变的 sizeCtl的工作方式。

因此，基本上，当一个线程首先有机会在ConcurrentHashMap中调整存储区数组的大小时，它将执行操作
U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2)
使 sizeCtl变为负值，这可以表示有些线程正在对bucket数组进行大小调整。

当 sizeCtl变为负数时，低16位包含有关并行调整大小的线程的信息。

这是我的想法:

因为变量 sc是本地int变量，如代码所示 int n, sc;
在执行 s >= (long) (sc = sizeCtl)之后，

一次迭代中， sc的值将永远不会更改。

我列出了所有有机会在一轮while循环中更改sizeCtl的代码片段
addCount函数中有两部分:

else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2))

的目的是试图抓住机会成为第一个调整

大小的线程

if ( U.compareAndSwapInt(this, SIZECTL, sc, sc + 1) )

的目的是试图抓住机会来帮助调整

的大小

三首 transfer功能

sizeCtl = Integer.MAX_VALUE;

这是为了应对OOP错误

sizeCtl = (n << 1) - (n >>> 1);

当旧表中的所有元素都已转移到新表时会发生这种情况，最后一个尚未从transfer返回的线程会将sizeCtl设置为下一个阈值，即0.75 * (2n)，请注意n是旧容量。 2n是新容量

U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)

这是做调整线程号控制的大小，它可以识别一个线程将要从传输中返回

根据以上所有信息，我发现:

输入if分支 if (sc < 0)(这意味着 sizeCtl已由 (rs << RESIZE_STAMP_SHIFT) + 2分配)后， sc shuold是一个“大”负数，从 resizeStamp(n)计算得出的高16位。条件

   sc == rs + 1 
 ||sc == rs + MAX_RESIZERS 

鉴于以下事实是永远不可能实现的

MAX_RESIZERS等于65535

rs的最大值是Integer.numberOfLeadingZeros(MAXIMUM_CAPACITY ) | (1 << (RESIZE_STAMP_BITS - 1))，等于32769

我认为以下条件更合理
sc == ( rs<<<RESIZE_STAMP_SHIFT ) +1判断所有线程是否完成大小调整
sc == ( rs<<<RESIZE_STAMP_SHIFT ) + MAX_RESIZERS判断调整线程大小是否已达到最大限制MAX_RESIZERS。

有人可以帮我解释一下我是否错了，非常感谢!

以下是我做的一个小实验，用于验证我的想法

感谢Carlos Heuberger的建议

您可以发布一个最小，完整和可验证的示例来演示该问题吗？

首先，将ConcurrentHashMap源代码复制到您自己的包

中

其次，进行一些必要的修改以使其可以被编译(例如:更改程序包声明，使Unsafe实例正常工作，也将ThreadLocalRandom复制到您的程序包中，因为ConcurrentHashMap使用了不是公共的ThreadLocalRandom.probe()函数)

第三，如文档所示，将MAX_RESIZERS减少为2，此应该来确保最多有2个线程可以同时进行大小调整
private static final int MAX_RESIZERS = 2;

第四，将以下代码段添加到自定义的ConcurrentHashMap类中

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();
}

第五，将以下代码片段添加到ConcurrentHashMap的 transfer函数中。暂停输入 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;
}
//  The following added code here is to suspend Threads !!!!
try {
    String s = new String();
    synchronized (s)
    {
        s.wait();
    }
} catch (InterruptedException e) {
    e.printStackTrace();
}

六，在addCount函数的以下代码行中添加线程断点

(提示:我使用Idea Intellij，选择“线程”选项可以挂起应用程序中的每个线程，否则仅挂起执行到断点的第一个线程)

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

然后运行main函数，您将看到进入2个以上线程的transfer函数，这意味着MAX_RESIZERS不起作用。

Answer 1

我已将此问题作为错误报告提交给Oracle。它已通过评估，并在带有错误ID的JDK错误数据库中可见:JDK-8214427

这是错误报告的链接:BUG: JDK-8214427。注意由于我的错误，错误报告中给出的修复方法是错误的

总结:

条件

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

应该更改为

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

Fixed JDK-12 code is now available here

 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) << RESIZE_STAMP_SHIFT;
                if (sc < 0) {
                    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 + 2))
                    transfer(tab, null);
                s = sumCount();
            }
        }