Striped64.java revision dfa41d2291e8d96e8c985cfe2ea9a43c301ce381
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.7 10 */ 11 12package com.google.common.cache; 13 14import 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 */ 21abstract 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 * Holder for the thread-local hash code. The code is initially 121 * random, but may be set to a different value upon collisions. 122 */ 123 static final class HashCode { 124 static final Random rng = new Random(); 125 int code; 126 HashCode() { 127 int h = rng.nextInt(); // Avoid zero to allow xorShift rehash 128 code = (h == 0) ? 1 : h; 129 } 130 } 131 132 /** 133 * The corresponding ThreadLocal class 134 */ 135 static final class ThreadHashCode extends ThreadLocal<HashCode> { 136 public HashCode initialValue() { return new HashCode(); } 137 } 138 139 /** 140 * Static per-thread hash codes. Shared across all instances to 141 * reduce ThreadLocal pollution and because adjustments due to 142 * collisions in one table are likely to be appropriate for 143 * others. 144 */ 145 static final ThreadHashCode threadHashCode = new ThreadHashCode(); 146 147 /** Number of CPUS, to place bound on table size */ 148 static final int NCPU = Runtime.getRuntime().availableProcessors(); 149 150 /** 151 * Table of cells. When non-null, size is a power of 2. 152 */ 153 transient volatile Cell[] cells; 154 155 /** 156 * Base value, used mainly when there is no contention, but also as 157 * a fallback during table initialization races. Updated via CAS. 158 */ 159 transient volatile long base; 160 161 /** 162 * Spinlock (locked via CAS) used when resizing and/or creating Cells. 163 */ 164 transient volatile int busy; 165 166 /** 167 * Package-private default constructor 168 */ 169 Striped64() { 170 } 171 172 /** 173 * CASes the base field. 174 */ 175 final boolean casBase(long cmp, long val) { 176 return UNSAFE.compareAndSwapLong(this, baseOffset, cmp, val); 177 } 178 179 /** 180 * CASes the busy field from 0 to 1 to acquire lock. 181 */ 182 final boolean casBusy() { 183 return UNSAFE.compareAndSwapInt(this, busyOffset, 0, 1); 184 } 185 186 /** 187 * Computes the function of current and new value. Subclasses 188 * should open-code this update function for most uses, but the 189 * virtualized form is needed within retryUpdate. 190 * 191 * @param currentValue the current value (of either base or a cell) 192 * @param newValue the argument from a user update call 193 * @return result of the update function 194 */ 195 abstract long fn(long currentValue, long newValue); 196 197 /** 198 * Handles cases of updates involving initialization, resizing, 199 * creating new Cells, and/or contention. See above for 200 * explanation. This method suffers the usual non-modularity 201 * problems of optimistic retry code, relying on rechecked sets of 202 * reads. 203 * 204 * @param x the value 205 * @param hc the hash code holder 206 * @param wasUncontended false if CAS failed before call 207 */ 208 final void retryUpdate(long x, HashCode hc, boolean wasUncontended) { 209 int h = hc.code; 210 boolean collide = false; // True if last slot nonempty 211 for (;;) { 212 Cell[] as; Cell a; int n; long v; 213 if ((as = cells) != null && (n = as.length) > 0) { 214 if ((a = as[(n - 1) & h]) == null) { 215 if (busy == 0) { // Try to attach new Cell 216 Cell r = new Cell(x); // Optimistically create 217 if (busy == 0 && casBusy()) { 218 boolean created = false; 219 try { // Recheck under lock 220 Cell[] rs; int m, j; 221 if ((rs = cells) != null && 222 (m = rs.length) > 0 && 223 rs[j = (m - 1) & h] == null) { 224 rs[j] = r; 225 created = true; 226 } 227 } finally { 228 busy = 0; 229 } 230 if (created) 231 break; 232 continue; // Slot is now non-empty 233 } 234 } 235 collide = false; 236 } 237 else if (!wasUncontended) // CAS already known to fail 238 wasUncontended = true; // Continue after rehash 239 else if (a.cas(v = a.value, fn(v, x))) 240 break; 241 else if (n >= NCPU || cells != as) 242 collide = false; // At max size or stale 243 else if (!collide) 244 collide = true; 245 else if (busy == 0 && casBusy()) { 246 try { 247 if (cells == as) { // Expand table unless stale 248 Cell[] rs = new Cell[n << 1]; 249 for (int i = 0; i < n; ++i) 250 rs[i] = as[i]; 251 cells = rs; 252 } 253 } finally { 254 busy = 0; 255 } 256 collide = false; 257 continue; // Retry with expanded table 258 } 259 h ^= h << 13; // Rehash 260 h ^= h >>> 17; 261 h ^= h << 5; 262 } 263 else if (busy == 0 && cells == as && casBusy()) { 264 boolean init = false; 265 try { // Initialize table 266 if (cells == as) { 267 Cell[] rs = new Cell[2]; 268 rs[h & 1] = new Cell(x); 269 cells = rs; 270 init = true; 271 } 272 } finally { 273 busy = 0; 274 } 275 if (init) 276 break; 277 } 278 else if (casBase(v = base, fn(v, x))) 279 break; // Fall back on using base 280 } 281 hc.code = h; // Record index for next time 282 } 283 284 /** 285 * Sets base and all cells to the given value. 286 */ 287 final void internalReset(long initialValue) { 288 Cell[] as = cells; 289 base = initialValue; 290 if (as != null) { 291 int n = as.length; 292 for (int i = 0; i < n; ++i) { 293 Cell a = as[i]; 294 if (a != null) 295 a.value = initialValue; 296 } 297 } 298 } 299 300 // Unsafe mechanics 301 private static final sun.misc.Unsafe UNSAFE; 302 private static final long baseOffset; 303 private static final long busyOffset; 304 static { 305 try { 306 UNSAFE = getUnsafe(); 307 Class<?> sk = Striped64.class; 308 baseOffset = UNSAFE.objectFieldOffset 309 (sk.getDeclaredField("base")); 310 busyOffset = UNSAFE.objectFieldOffset 311 (sk.getDeclaredField("busy")); 312 } catch (Exception e) { 313 throw new Error(e); 314 } 315 } 316 317 /** 318 * Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package. 319 * Replace with a simple call to Unsafe.getUnsafe when integrating 320 * into a jdk. 321 * 322 * @return a sun.misc.Unsafe 323 */ 324 private static sun.misc.Unsafe getUnsafe() { 325 try { 326 return sun.misc.Unsafe.getUnsafe(); 327 } catch (SecurityException tryReflectionInstead) {} 328 try { 329 return java.security.AccessController.doPrivileged 330 (new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() { 331 public sun.misc.Unsafe run() throws Exception { 332 Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class; 333 for (java.lang.reflect.Field f : k.getDeclaredFields()) { 334 f.setAccessible(true); 335 Object x = f.get(null); 336 if (k.isInstance(x)) 337 return k.cast(x); 338 } 339 throw new NoSuchFieldError("the Unsafe"); 340 }}); 341 } catch (java.security.PrivilegedActionException e) { 342 throw new RuntimeException("Could not initialize intrinsics", 343 e.getCause()); 344 } 345 } 346 347} 348