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