src/jsr166e/Striped64.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package jsr166e;

import java.util.Random;

/**
 * A package-local class holding common representation and mechanics
 * for classes supporting dynamic striping on 64bit values. The class
 * extends Number so that concrete subclasses must publicly do so.
 */
abstract class Striped64 extends Number {
    /*
     * This class maintains a lazily-initialized table of atomically
     * updated variables, plus an extra "base" field. The table size
     * is a power of two. Indexing uses masked per-thread hash codes.
     * Nearly all declarations in this class are package-private,
     * accessed directly by subclasses.
     *
     * Table entries are of class Cell; a variant of AtomicLong padded
     * to reduce cache contention on most processors. Padding is
     * overkill for most Atomics because they are usually irregularly
     * scattered in memory and thus don't interfere much with each
     * other. But Atomic objects residing in arrays will tend to be
     * placed adjacent to each other, and so will most often share
     * cache lines (with a huge negative performance impact) without
     * this precaution.
     *
     * In part because Cells are relatively large, we avoid creating
     * them until they are needed.  When there is no contention, all
     * updates are made to the base field.  Upon first contention (a
     * failed CAS on base update), the table is initialized to size 2.
     * The table size is doubled upon further contention until
     * reaching the nearest power of two greater than or equal to the
     * number of CPUS. Table slots remain empty (null) until they are
     * needed.
     *
     * A single spinlock ("busy") is used for initializing and
     * resizing the table, as well as populating slots with new Cells.
     * There is no need for a blocking lock; when the lock is not
     * available, threads try other slots (or the base).  During these
     * retries, there is increased contention and reduced locality,
     * which is still better than alternatives.
     *
     * Per-thread hash codes are initialized to random values.
     * Contention and/or table collisions are indicated by failed
     * CASes when performing an update operation (see method
     * retryUpdate). Upon a collision, if the table size is less than
     * the capacity, it is doubled in size unless some other thread
     * holds the lock. If a hashed slot is empty, and lock is
     * available, a new Cell is created. Otherwise, if the slot
     * exists, a CAS is tried.  Retries proceed by "double hashing",
     * using a secondary hash (Marsaglia XorShift) to try to find a
     * free slot.
     *
     * The table size is capped because, when there are more threads
     * than CPUs, supposing that each thread were bound to a CPU,
     * there would exist a perfect hash function mapping threads to
     * slots that eliminates collisions. When we reach capacity, we
     * search for this mapping by randomly varying the hash codes of
     * colliding threads.  Because search is random, and collisions
     * only become known via CAS failures, convergence can be slow,
     * and because threads are typically not bound to CPUS forever,
     * may not occur at all. However, despite these limitations,
     * observed contention rates are typically low in these cases.
     *
     * It is possible for a Cell to become unused when threads that
     * once hashed to it terminate, as well as in the case where
     * doubling the table causes no thread to hash to it under
     * expanded mask.  We do not try to detect or remove such cells,
     * under the assumption that for long-running instances, observed
     * contention levels will recur, so the cells will eventually be
     * needed again; and for short-lived ones, it does not matter.
     */

    /**
     * Padded variant of AtomicLong supporting only raw accesses plus CAS.
     * The value field is placed between pads, hoping that the JVM doesn't
     * reorder them.
     *
     * JVM intrinsics note: It would be possible to use a release-only
     * form of CAS here, if it were provided.
     */
    static final class Cell {
        volatile long p0, p1, p2, p3, p4, p5, p6;
        volatile long value;
        volatile long q0, q1, q2, q3, q4, q5, q6;
        Cell(long x) { value = x; }

        final boolean cas(long cmp, long val) {
            return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
        }

        // Unsafe mechanics
        private static final sun.misc.Unsafe UNSAFE;
        private static final long valueOffset;
        static {
            try {
                UNSAFE = getUnsafe();
                Class<?> ak = Cell.class;
                valueOffset = UNSAFE.objectFieldOffset
                    (ak.getDeclaredField("value"));
            } catch (Exception e) {
                throw new Error(e);
            }
        }

    }

    /**
     * ThreadLocal holding a single-slot int array holding hash code.
     * Unlike the JDK8 version of this class, we use a suboptimal
     * int[] representation to avoid introducing a new type that can
     * impede class-unloading when ThreadLocals are not removed.
     */
    static final ThreadLocal<int[]> threadHashCode = new ThreadLocal<int[]>();

    /**
     * Generator of new random hash codes
     */
    static final Random rng = new Random();

    /** 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 busy;

    /**
     * Package-private default constructor
     */
    Striped64() {
    }

    /**
     * CASes the base field.
     */
    final boolean casBase(long cmp, long val) {
        return UNSAFE.compareAndSwapLong(this, baseOffset, cmp, val);
    }

    /**
     * CASes the busy field from 0 to 1 to acquire lock.
     */
    final boolean casBusy() {
        return UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1);
    }

    /**
     * Computes the function of current and new value. Subclasses
     * should open-code this update function for most uses, but the
     * virtualized form is needed within retryUpdate.
     *
     * @param currentValue the current value (of either base or a cell)
     * @param newValue the argument from a user update call
     * @return result of the update function
     */
    abstract long fn(long currentValue, long newValue);

    /**
     * Handles cases of updates involving initialization, resizing,
     * creating new Cells, and/or contention. See above for
     * explanation. This method suffers the usual non-modularity
     * problems of optimistic retry code, relying on rechecked sets of
     * reads.
     *
     * @param x the value
     * @param hc the hash code holder
     * @param wasUncontended false if CAS failed before call
     */
    final void retryUpdate(long x, int[] hc, boolean wasUncontended) {
        int h;
        if (hc == null) {
            threadHashCode.set(hc = new int[1]); // Initialize randomly
            int r = rng.nextInt(); // Avoid zero to allow xorShift rehash
            h = hc[0] = (r == 0) ? 1 : r;
        }
        else
            h = hc[0];
        boolean collide = false;                // True if last slot nonempty
        for (;;) {
            Cell[] as; Cell a; int n; long v;
            if ((as = cells) != null && (n = as.length) > 0) {
                if ((a = as[(n - 1) & h]) == null) {
                    if (busy == 0) {            // Try to attach new Cell
                        Cell r = new Cell(x);   // Optimistically create
                        if (busy == 0 && casBusy()) {
                            boolean created = false;
                            try {               // Recheck under lock
                                Cell[] rs; int m, j;
                                if ((rs = cells) != null &&
                                    (m = rs.length) > 0 &&
                                    rs[j = (m - 1) & h] == null) {
                                    rs[j] = r;
                                    created = true;
                                }
                            } finally {
                                busy = 0;
                            }
                            if (created)
                                break;
                            continue;           // Slot is now non-empty
                        }
                    }
                    collide = false;
                }
                else if (!wasUncontended)       // CAS already known to fail
                    wasUncontended = true;      // Continue after rehash
                else if (a.cas(v = a.value, fn(v, x)))
                    break;
                else if (n >= NCPU || cells != as)
                    collide = false;            // At max size or stale
                else if (!collide)
                    collide = true;
                else if (busy == 0 && casBusy()) {
                    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 {
                        busy = 0;
                    }
                    collide = false;
                    continue;                   // Retry with expanded table
                }
                h ^= h << 13;                   // Rehash
                h ^= h >>> 17;
                h ^= h << 5;
                hc[0] = h;                      // Record index for next time
            }
            else if (busy == 0 && cells == as && casBusy()) {
                boolean init = false;
                try {                           // Initialize table
                    if (cells == as) {
                        Cell[] rs = new Cell[2];
                        rs[h & 1] = new Cell(x);
                        cells = rs;
                        init = true;
                    }
                } finally {
                    busy = 0;
                }
                if (init)
                    break;
            }
            else if (casBase(v = base, fn(v, x)))
                break;                          // Fall back on using base
        }
    }


    /**
     * Sets base and all cells to the given value.
     */
    final void internalReset(long initialValue) {
        Cell[] as = cells;
        base = initialValue;
        if (as != null) {
            int n = as.length;
            for (int i = 0; i < n; ++i) {
                Cell a = as[i];
                if (a != null)
                    a.value = initialValue;
            }
        }
    }

    // Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long baseOffset;
    private static final long busyOffset;
    static {
        try {
            UNSAFE = getUnsafe();
            Class<?> sk = Striped64.class;
            baseOffset = UNSAFE.objectFieldOffset
                (sk.getDeclaredField("base"));
            busyOffset = UNSAFE.objectFieldOffset
                (sk.getDeclaredField("busy"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }

    /**
     * Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
     * Replace with a simple call to Unsafe.getUnsafe when integrating
     * into a jdk.
     *
     * @return a sun.misc.Unsafe
     */
    private static sun.misc.Unsafe getUnsafe() {
        try {
            return sun.misc.Unsafe.getUnsafe();
        } catch (SecurityException tryReflectionInstead) {}
        try {
            return java.security.AccessController.doPrivileged
            (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
                public sun.misc.Unsafe run() throws Exception {
                    Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
                    for (java.lang.reflect.Field f : k.getDeclaredFields()) {
                        f.setAccessible(true);
                        Object x = f.get(null);
                        if (k.isInstance(x))
                            return k.cast(x);
                    }
                    throw new NoSuchFieldError("the Unsafe");
                }});
        } catch (java.security.PrivilegedActionException e) {
            throw new RuntimeException("Could not initialize intrinsics",
                                       e.getCause());
        }
    }
}
Revision:	1.10
Committed:	Sun Jan 18 20:17:33 2015 UTC (9 years, 3 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.9:	+1 -0 lines
Log Message:	exactly one blank line before and after package statements
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain, as explained at
4	* http://creativecommons.org/publicdomain/zero/1.0/
5	*/
6
7	package jsr166e;
8
9	import java.util.Random;
10
11	/**
12	* A package-local class holding common representation and mechanics
13	* for classes supporting dynamic striping on 64bit values. The class
14	* extends Number so that concrete subclasses must publicly do so.
15	*/
16	abstract class Striped64 extends Number {
17	/*
18	* This class maintains a lazily-initialized table of atomically
19	* updated variables, plus an extra "base" field. The table size
20	* is a power of two. Indexing uses masked per-thread hash codes.
21	* Nearly all declarations in this class are package-private,
22	* accessed directly by subclasses.
23	*
24	* Table entries are of class Cell; a variant of AtomicLong padded
25	* to reduce cache contention on most processors. Padding is
26	* overkill for most Atomics because they are usually irregularly
27	* scattered in memory and thus don't interfere much with each
28	* other. But Atomic objects residing in arrays will tend to be
29	* placed adjacent to each other, and so will most often share
30	* cache lines (with a huge negative performance impact) without
31	* this precaution.
32	*
33	* In part because Cells are relatively large, we avoid creating
34	* them until they are needed. When there is no contention, all
35	* updates are made to the base field. Upon first contention (a
36	* failed CAS on base update), the table is initialized to size 2.
37	* The table size is doubled upon further contention until
38	* reaching the nearest power of two greater than or equal to the
39	* number of CPUS. Table slots remain empty (null) until they are
40	* needed.
41	*
42	* A single spinlock ("busy") is used for initializing and
43	* resizing the table, as well as populating slots with new Cells.
44	* There is no need for a blocking lock; when the lock is not
45	* available, threads try other slots (or the base). During these
46	* retries, there is increased contention and reduced locality,
47	* which is still better than alternatives.
48	*
49	* Per-thread hash codes are initialized to random values.
50	* Contention and/or table collisions are indicated by failed
51	* CASes when performing an update operation (see method
52	* retryUpdate). Upon a collision, if the table size is less than
53	* the capacity, it is doubled in size unless some other thread
54	* holds the lock. If a hashed slot is empty, and lock is
55	* available, a new Cell is created. Otherwise, if the slot
56	* exists, a CAS is tried. Retries proceed by "double hashing",
57	* using a secondary hash (Marsaglia XorShift) to try to find a
58	* free slot.
59	*
60	* The table size is capped because, when there are more threads
61	* than CPUs, supposing that each thread were bound to a CPU,
62	* there would exist a perfect hash function mapping threads to
63	* slots that eliminates collisions. When we reach capacity, we
64	* search for this mapping by randomly varying the hash codes of
65	* colliding threads. Because search is random, and collisions
66	* only become known via CAS failures, convergence can be slow,
67	* and because threads are typically not bound to CPUS forever,
68	* may not occur at all. However, despite these limitations,
69	* observed contention rates are typically low in these cases.
70	*
71	* It is possible for a Cell to become unused when threads that
72	* once hashed to it terminate, as well as in the case where
73	* doubling the table causes no thread to hash to it under
74	* expanded mask. We do not try to detect or remove such cells,
75	* under the assumption that for long-running instances, observed
76	* contention levels will recur, so the cells will eventually be
77	* needed again; and for short-lived ones, it does not matter.
78	*/
79
80	/**
81	* Padded variant of AtomicLong supporting only raw accesses plus CAS.
82	* The value field is placed between pads, hoping that the JVM doesn't
83	* reorder them.
84	*
85	* JVM intrinsics note: It would be possible to use a release-only
86	* form of CAS here, if it were provided.
87	*/
88	static final class Cell {
89	volatile long p0, p1, p2, p3, p4, p5, p6;
90	volatile long value;
91	volatile long q0, q1, q2, q3, q4, q5, q6;
92	Cell(long x) { value = x; }
93
94	final boolean cas(long cmp, long val) {
95	return UNSAFE.compareAndSwapLong(this, valueOffset, cmp, val);
96	}
97
98	// Unsafe mechanics
99	private static final sun.misc.Unsafe UNSAFE;
100	private static final long valueOffset;
101	static {
102	try {
103	UNSAFE = getUnsafe();
104	Class<?> ak = Cell.class;
105	valueOffset = UNSAFE.objectFieldOffset
106	(ak.getDeclaredField("value"));
107	} catch (Exception e) {
108	throw new Error(e);
109	}
110	}
111
112	}
113
114	/**
115	* ThreadLocal holding a single-slot int array holding hash code.
116	* Unlike the JDK8 version of this class, we use a suboptimal
117	* int[] representation to avoid introducing a new type that can
118	* impede class-unloading when ThreadLocals are not removed.
119	*/
120	static final ThreadLocal<int[]> threadHashCode = new ThreadLocal<int[]>();
121
122	/**
123	* Generator of new random hash codes
124	*/
125	static final Random rng = new Random();
126
127	/** Number of CPUS, to place bound on table size */
128	static final int NCPU = Runtime.getRuntime().availableProcessors();
129
130	/**
131	* Table of cells. When non-null, size is a power of 2.
132	*/
133	transient volatile Cell[] cells;
134
135	/**
136	* Base value, used mainly when there is no contention, but also as
137	* a fallback during table initialization races. Updated via CAS.
138	*/
139	transient volatile long base;
140
141	/**
142	* Spinlock (locked via CAS) used when resizing and/or creating Cells.
143	*/
144	transient volatile int busy;
145
146	/**
147	* Package-private default constructor
148	*/
149	Striped64() {
150	}
151
152	/**
153	* CASes the base field.
154	*/
155	final boolean casBase(long cmp, long val) {
156	return UNSAFE.compareAndSwapLong(this, baseOffset, cmp, val);
157	}
158
159	/**
160	* CASes the busy field from 0 to 1 to acquire lock.
161	*/
162	final boolean casBusy() {
163	return UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1);
164	}
165
166	/**
167	* Computes the function of current and new value. Subclasses
168	* should open-code this update function for most uses, but the
169	* virtualized form is needed within retryUpdate.
170	*
171	* @param currentValue the current value (of either base or a cell)
172	* @param newValue the argument from a user update call
173	* @return result of the update function
174	*/
175	abstract long fn(long currentValue, long newValue);
176
177	/**
178	* Handles cases of updates involving initialization, resizing,
179	* creating new Cells, and/or contention. See above for
180	* explanation. This method suffers the usual non-modularity
181	* problems of optimistic retry code, relying on rechecked sets of
182	* reads.
183	*
184	* @param x the value
185	* @param hc the hash code holder
186	* @param wasUncontended false if CAS failed before call
187	*/
188	final void retryUpdate(long x, int[] hc, boolean wasUncontended) {
189	int h;
190	if (hc == null) {
191	threadHashCode.set(hc = new int[1]); // Initialize randomly
192	int r = rng.nextInt(); // Avoid zero to allow xorShift rehash
193	h = hc[0] = (r == 0) ? 1 : r;
194	}
195	else
196	h = hc[0];
197	boolean collide = false; // True if last slot nonempty
198	for (;;) {
199	Cell[] as; Cell a; int n; long v;
200	if ((as = cells) != null && (n = as.length) > 0) {
201	if ((a = as[(n - 1) & h]) == null) {
202	if (busy == 0) { // Try to attach new Cell
203	Cell r = new Cell(x); // Optimistically create
204	if (busy == 0 && casBusy()) {
205	boolean created = false;
206	try { // Recheck under lock
207	Cell[] rs; int m, j;
208	if ((rs = cells) != null &&
209	(m = rs.length) > 0 &&
210	rs[j = (m - 1) & h] == null) {
211	rs[j] = r;
212	created = true;
213	}
214	} finally {
215	busy = 0;
216	}
217	if (created)
218	break;
219	continue; // Slot is now non-empty
220	}
221	}
222	collide = false;
223	}
224	else if (!wasUncontended) // CAS already known to fail
225	wasUncontended = true; // Continue after rehash
226	else if (a.cas(v = a.value, fn(v, x)))
227	break;
228	else if (n >= NCPU \|\| cells != as)
229	collide = false; // At max size or stale
230	else if (!collide)
231	collide = true;
232	else if (busy == 0 && casBusy()) {
233	try {
234	if (cells == as) { // Expand table unless stale
235	Cell[] rs = new Cell[n << 1];
236	for (int i = 0; i < n; ++i)
237	rs[i] = as[i];
238	cells = rs;
239	}
240	} finally {
241	busy = 0;
242	}
243	collide = false;
244	continue; // Retry with expanded table
245	}
246	h ^= h << 13; // Rehash
247	h ^= h >>> 17;
248	h ^= h << 5;
249	hc[0] = h; // Record index for next time
250	}
251	else if (busy == 0 && cells == as && casBusy()) {
252	boolean init = false;
253	try { // Initialize table
254	if (cells == as) {
255	Cell[] rs = new Cell[2];
256	rs[h & 1] = new Cell(x);
257	cells = rs;
258	init = true;
259	}
260	} finally {
261	busy = 0;
262	}
263	if (init)
264	break;
265	}
266	else if (casBase(v = base, fn(v, x)))
267	break; // Fall back on using base
268	}
269	}
270
271
272	/**
273	* Sets base and all cells to the given value.
274	*/
275	final void internalReset(long initialValue) {
276	Cell[] as = cells;
277	base = initialValue;
278	if (as != null) {
279	int n = as.length;
280	for (int i = 0; i < n; ++i) {
281	Cell a = as[i];
282	if (a != null)
283	a.value = initialValue;
284	}
285	}
286	}
287
288	// Unsafe mechanics
289	private static final sun.misc.Unsafe UNSAFE;
290	private static final long baseOffset;
291	private static final long busyOffset;
292	static {
293	try {
294	UNSAFE = getUnsafe();
295	Class<?> sk = Striped64.class;
296	baseOffset = UNSAFE.objectFieldOffset
297	(sk.getDeclaredField("base"));
298	busyOffset = UNSAFE.objectFieldOffset
299	(sk.getDeclaredField("busy"));
300	} catch (Exception e) {
301	throw new Error(e);
302	}
303	}
304
305	/**
306	* Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package.
307	* Replace with a simple call to Unsafe.getUnsafe when integrating
308	* into a jdk.
309	*
310	* @return a sun.misc.Unsafe
311	*/
312	private static sun.misc.Unsafe getUnsafe() {
313	try {
314	return sun.misc.Unsafe.getUnsafe();
315	} catch (SecurityException tryReflectionInstead) {}
316	try {
317	return java.security.AccessController.doPrivileged
318	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
319	public sun.misc.Unsafe run() throws Exception {
320	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
321	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
322	f.setAccessible(true);
323	Object x = f.get(null);
324	if (k.isInstance(x))
325	return k.cast(x);
326	}
327	throw new NoSuchFieldError("the Unsafe");
328	}});
329	} catch (java.security.PrivilegedActionException e) {
330	throw new RuntimeException("Could not initialize intrinsics",
331	e.getCause());
332	}
333	}
334	}