long adder

LongAdder.java

    /** Number of CPUS, to place bound on table size */
    static final int NCPU = Runtime.getRuntime().availableProcessors();

    /**
     * Table of cells. When non-null, size is a power of 2.
     */
    transient volatile Cell[] cells;

    /**
     * Base value, used mainly when there is no contention, but also as
     * a fallback during table initialization races. Updated via CAS.
     */
    transient volatile long base;

    /**
     * Spinlock (locked via CAS) used when resizing and/or creating Cells.
     */
    transient volatile int cellsBusy;

final void longAccumulate(long x, LongBinaryOperator fn,
                              boolean wasUncontended) {
        int h;
        // 获取当前线程的probe值（与随机值有关）
        // 如果为0，则初始化当前线程probe随机值(hash)
        if ((h = getProbe()) == 0) {
            // 该静态方法会初始化当前线程所持有的随机值
            ThreadLocalRandom.current();
            // 获取生成后的probe值，用于选择cells数组下标元素
            h = getProbe();
            // 由于重新生成了probe，未冲突标志位设置为true
            wasUncontended = true;
        }
        // 当前线程的probe值，分配到cells数组下标元素不为空，则需要设置cell冲突标志位
        boolean collide = false;                // True if last slot nonempty
        // 直接进入死循环
        for (;;) {
            Cell[] as; Cell a; int n; long v;
            // cells数组已经被成功初始化，则放入对应的cell元素中, 这个条件在前面可以省去一次CAS的失败
            if ((as = cells) != null && (n = as.length) > 0) {
                // --------------------- 1.0 存在cell数组 ---------------------
                // n为2的次幂，n-1则为一个二进制低位全1的值，通过该值与当前线程probe求与，获得cells的下标元素
                // 该if语句对应的情况：当前线程probe值对应的cell数组下标处为null，则需要创建该cell元素
                if ((a = as[(n - 1) & h]) == null) {
                    // --------------------- 1.1 ---------------------
                    // cellsBusy不为0表示cells数组不在初始化或者扩容状态下
                    if (cellsBusy == 0) {      // Try to attach new Cell
                        Cell r = new Cell(x);  // Optimistically create
                        // CAS设置cellsBusy，进入临界区，将创建的元素r放入cells数组中
                        if (cellsBusy == 0 && casCellsBusy()) {
                            boolean created = false;
                            try {              // Recheck under lock
                                Cell[] rs; int m, j;
                                // double check, 这里 cellsBusy是volatile类型的, 保证了内存的可见性
                                if ((rs = cells) != null &&
                                    (m = rs.length) > 0 &&
                                    rs[j = (m - 1) & h] == null) {
                                    // 对应下标的cell为空，将新创建的cell放入对应下标位置，则累加操作成功
                                    rs[j] = r;
                                    created = true;
                                }
                            } finally {
                                // 释放临界区
                                cellsBusy = 0;
                            }
                            // 对应下标的cell为空，将新创建的cell放入对应下标位置，则累加操作成功
                            // 直接返回退出死循环
                            if (created)
                                break;
                            // 当前cell数组下标位置不为空，并发导致的不一致，重新进入死循环
                            continue;
                        }
                    }
                    collide = false;
                }
                // 获取了probe对应cells数组中的下标元素，发现不为空
                // 并且调用该函数前，调用方CAS操作也已经失败（已经发生竞争）
                else if (!wasUncontended)      // CAS already known to fail
                    // 设置未冲突标志位为true后，重新生成probe，进入死循环
                    // --------------------- 1.2 ---------------------
                    wasUncontended = true;      // Continue after rehash
                // 使用CAS操作，在当前下标处的cell元素中执行累加
                else if (a.cas(v = a.value, ((fn == null) ? v + x :
                                            fn.applyAsLong(v, x))))
                    // 累加成功，则退出死循环
                    // --------------------- 1.3 ---------------------
                    break;
                // cells数组元素足够大（不扩容），亦或者表在扩容过程中，已经过时
                // 重新生成probe后，进入死循环重试
                else if (n >= NCPU || cells != as)
                    // --------------------- 1.4 ---------------------
                    collide = false;            // At max size or stale
                // 当前cells数组中下标元素不为空，则设置cell冲突标志位
                // 重新生成probe后，进入死循环重试
                // 该if语句避免了一冲突就扩容的情况
                else if (!collide)
                    // --------------------- 1.5 ---------------------
                    collide = true;
                // 对Cell数组进行扩容，CAS设置cellsBusy进入临界区
                else if (cellsBusy == 0 && casCellsBusy()) {
                // --------------------- 1.6 扩容 ---------------------
                    try {
                        if (cells == as) {      // Expand table unless stale
                            Cell[] rs = new Cell[n << 1];
                            for (int i = 0; i < n; ++i)
                                rs[i] = as[i];
                            cells = rs;
                        }
                    } finally {
                        cellsBusy = 0;
                    }
                    collide = false;
                    continue;                  // Retry with expanded table
                }
                // 与ThreadLocalRandom中的方法一样
                // 为当前线程重新生成一个probe值，用于重新选择cells下标
                h = advanceProbe(h);
            }


            // 尝试初始化cells数组
            // 将cellsBusy变量从0设置为1，获取锁，进入初始化的临界区
            else if (cellsBusy == 0 && cells == as && casCellsBusy()) {
                // --------------------- 2.0 不存在cells数组且没有被其他线程修改(扩容)---------------------
                boolean init = false;
                try {                          // Initialize table
                    if (cells == as) { // double check
                        // cell数组大小必须为2的次幂
                        Cell[] rs = new Cell[2];
                        // 将需要累加的值x，放入cell数组元素中
                        // 选择的下标与当前线程的probe随机值有关
                        rs[h & 1] = new Cell(x);
                        cells = rs;
                        init = true;
                    }
                } finally {
                    cellsBusy = 0; // 释放锁资源, 一定要在finally语句中
                }
                // 临界区中初始化成功，并且该x值被累加入cell中，则退出死循环
                if (init)
                    break;

                // double check 失败, 可能已经被其他线程修改, 继续cas
            }


            // 没有cells数组，并且没有初始化的情况下，考虑直接累加在base变量中
            else if (casBase(v = base, ((fn == null) ? v + x :
                                        fn.applyAsLong(v, x))))
                // --------------------- 3.0 ---------------------
                // 如果直接累加在base中成功，则可直接退出死循环
                break;                       
        }
    }