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