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