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;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 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 can 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);
            }
        }
        
    }

    /**
     * Holder for the thread-local hash code. The code is initially
     * random, but may be set to a different value upon collisions.
     */
    static final class HashCode {
        static final Random rng = new Random();
        int code;
        HashCode() {
            int h = rng.nextInt(); // Avoid zero to allow xorShift rehash
            code = (h == 0) ? 1 : h;
        }
    }
    
    /**
     * The corresponding ThreadLocal class
     */
    static final class ThreadHashCode extends ThreadLocal<HashCode> {
        public HashCode initialValue() { return new HashCode(); }
    }

    /**
     * Static per-thread hash codes. Shared across all instances to
     * reduce ThreadLocal pollution and because adjustments due to
     * collisions in one table are likely to be appropriate for
     * others.
     */
    static final ThreadHashCode threadHashCode = new ThreadHashCode();

    /** Nomber 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 initializion 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() {
    }

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

    /**
     * CAS 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, HashCode hc, boolean wasUncontended) {
        int h = hc.code;
        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;
            }
            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
        }
        hc.code = h;                            // Record index for next time
    }


    /**
     * Set 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 se) {
            try {
                return java.security.AccessController.doPrivileged
                    (new java.security
                     .PrivilegedExceptionAction<sun.misc.Unsafe>() {
                        public sun.misc.Unsafe run() throws Exception {
                            java.lang.reflect.Field f = sun.misc
                                .Unsafe.class.getDeclaredField("theUnsafe");
                            f.setAccessible(true);
                            return (sun.misc.Unsafe) f.get(null);
                        }});
            } catch (java.security.PrivilegedActionException e) {
                throw new RuntimeException("Could not initialize intrinsics",
                                           e.getCause());
            }
        }
    }

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