001/* 002 * Copyright (C) 2011 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.util.concurrent; 016 017import static com.google.common.collect.Lists.newArrayList; 018 019import com.google.common.annotations.GwtIncompatible; 020import com.google.common.annotations.J2ktIncompatible; 021import com.google.common.annotations.VisibleForTesting; 022import com.google.common.base.MoreObjects; 023import com.google.common.base.Preconditions; 024import com.google.common.base.Supplier; 025import com.google.common.collect.ImmutableList; 026import com.google.common.collect.MapMaker; 027import com.google.common.math.IntMath; 028import com.google.common.primitives.Ints; 029import java.lang.ref.Reference; 030import java.lang.ref.ReferenceQueue; 031import java.lang.ref.WeakReference; 032import java.math.RoundingMode; 033import java.util.Arrays; 034import java.util.Collections; 035import java.util.List; 036import java.util.concurrent.ConcurrentMap; 037import java.util.concurrent.Semaphore; 038import java.util.concurrent.atomic.AtomicReferenceArray; 039import java.util.concurrent.locks.Condition; 040import java.util.concurrent.locks.Lock; 041import java.util.concurrent.locks.ReadWriteLock; 042import java.util.concurrent.locks.ReentrantLock; 043import java.util.concurrent.locks.ReentrantReadWriteLock; 044import org.checkerframework.checker.nullness.qual.Nullable; 045 046/** 047 * A striped {@code Lock/Semaphore/ReadWriteLock}. This offers the underlying lock striping similar 048 * to that of {@code ConcurrentHashMap} in a reusable form, and extends it for semaphores and 049 * read-write locks. Conceptually, lock striping is the technique of dividing a lock into many 050 * <i>stripes</i>, increasing the granularity of a single lock and allowing independent operations 051 * to lock different stripes and proceed concurrently, instead of creating contention for a single 052 * lock. 053 * 054 * <p>The guarantee provided by this class is that equal keys lead to the same lock (or semaphore), 055 * i.e. {@code if (key1.equals(key2))} then {@code striped.get(key1) == striped.get(key2)} (assuming 056 * {@link Object#hashCode()} is correctly implemented for the keys). Note that if {@code key1} is 057 * <strong>not</strong> equal to {@code key2}, it is <strong>not</strong> guaranteed that {@code 058 * striped.get(key1) != striped.get(key2)}; the elements might nevertheless be mapped to the same 059 * lock. The lower the number of stripes, the higher the probability of this happening. 060 * 061 * <p>There are three flavors of this class: {@code Striped<Lock>}, {@code Striped<Semaphore>}, and 062 * {@code Striped<ReadWriteLock>}. For each type, two implementations are offered: {@linkplain 063 * #lock(int) strong} and {@linkplain #lazyWeakLock(int) weak} {@code Striped<Lock>}, {@linkplain 064 * #semaphore(int, int) strong} and {@linkplain #lazyWeakSemaphore(int, int) weak} {@code 065 * Striped<Semaphore>}, and {@linkplain #readWriteLock(int) strong} and {@linkplain 066 * #lazyWeakReadWriteLock(int) weak} {@code Striped<ReadWriteLock>}. <i>Strong</i> means that all 067 * stripes (locks/semaphores) are initialized eagerly, and are not reclaimed unless {@code Striped} 068 * itself is reclaimable. <i>Weak</i> means that locks/semaphores are created lazily, and they are 069 * allowed to be reclaimed if nobody is holding on to them. This is useful, for example, if one 070 * wants to create a {@code Striped<Lock>} of many locks, but worries that in most cases only a 071 * small portion of these would be in use. 072 * 073 * <p>Prior to this class, one might be tempted to use {@code Map<K, Lock>}, where {@code K} 074 * represents the task. This maximizes concurrency by having each unique key mapped to a unique 075 * lock, but also maximizes memory footprint. On the other extreme, one could use a single lock for 076 * all tasks, which minimizes memory footprint but also minimizes concurrency. Instead of choosing 077 * either of these extremes, {@code Striped} allows the user to trade between required concurrency 078 * and memory footprint. For example, if a set of tasks are CPU-bound, one could easily create a 079 * very compact {@code Striped<Lock>} of {@code availableProcessors() * 4} stripes, instead of 080 * possibly thousands of locks which could be created in a {@code Map<K, Lock>} structure. 081 * 082 * @author Dimitris Andreou 083 * @since 13.0 084 */ 085@J2ktIncompatible 086@GwtIncompatible 087@ElementTypesAreNonnullByDefault 088public abstract class Striped<L> { 089 /** 090 * If there are at least this many stripes, we assume the memory usage of a ConcurrentMap will be 091 * smaller than a large array. (This assumes that in the lazy case, most stripes are unused. As 092 * always, if many stripes are in use, a non-lazy striped makes more sense.) 093 */ 094 private static final int LARGE_LAZY_CUTOFF = 1024; 095 096 private Striped() {} 097 098 /** 099 * Returns the stripe that corresponds to the passed key. It is always guaranteed that if {@code 100 * key1.equals(key2)}, then {@code get(key1) == get(key2)}. 101 * 102 * @param key an arbitrary, non-null key 103 * @return the stripe that the passed key corresponds to 104 */ 105 public abstract L get(Object key); 106 107 /** 108 * Returns the stripe at the specified index. Valid indexes are 0, inclusively, to {@code size()}, 109 * exclusively. 110 * 111 * @param index the index of the stripe to return; must be in {@code [0...size())} 112 * @return the stripe at the specified index 113 */ 114 public abstract L getAt(int index); 115 116 /** 117 * Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key). 118 */ 119 abstract int indexFor(Object key); 120 121 /** Returns the total number of stripes in this instance. */ 122 public abstract int size(); 123 124 /** 125 * Returns the stripes that correspond to the passed objects, in ascending (as per {@link 126 * #getAt(int)}) order. Thus, threads that use the stripes in the order returned by this method 127 * are guaranteed to not deadlock each other. 128 * 129 * <p>It should be noted that using a {@code Striped<L>} with relatively few stripes, and {@code 130 * bulkGet(keys)} with a relative large number of keys can cause an excessive number of shared 131 * stripes (much like the birthday paradox, where much fewer than anticipated birthdays are needed 132 * for a pair of them to match). Please consider carefully the implications of the number of 133 * stripes, the intended concurrency level, and the typical number of keys used in a {@code 134 * bulkGet(keys)} operation. See <a href="http://www.mathpages.com/home/kmath199.htm">Balls in 135 * Bins model</a> for mathematical formulas that can be used to estimate the probability of 136 * collisions. 137 * 138 * @param keys arbitrary non-null keys 139 * @return the stripes corresponding to the objects (one per each object, derived by delegating to 140 * {@link #get(Object)}; may contain duplicates), in an increasing index order. 141 */ 142 public Iterable<L> bulkGet(Iterable<? extends Object> keys) { 143 // Initially using the list to store the keys, then reusing it to store the respective L's 144 List<Object> result = newArrayList(keys); 145 if (result.isEmpty()) { 146 return ImmutableList.of(); 147 } 148 int[] stripes = new int[result.size()]; 149 for (int i = 0; i < result.size(); i++) { 150 stripes[i] = indexFor(result.get(i)); 151 } 152 Arrays.sort(stripes); 153 // optimize for runs of identical stripes 154 int previousStripe = stripes[0]; 155 result.set(0, getAt(previousStripe)); 156 for (int i = 1; i < result.size(); i++) { 157 int currentStripe = stripes[i]; 158 if (currentStripe == previousStripe) { 159 result.set(i, result.get(i - 1)); 160 } else { 161 result.set(i, getAt(currentStripe)); 162 previousStripe = currentStripe; 163 } 164 } 165 /* 166 * Note that the returned Iterable holds references to the returned stripes, to avoid 167 * error-prone code like: 168 * 169 * Striped<Lock> stripedLock = Striped.lazyWeakXXX(...)' 170 * Iterable<Lock> locks = stripedLock.bulkGet(keys); 171 * for (Lock lock : locks) { 172 * lock.lock(); 173 * } 174 * operation(); 175 * for (Lock lock : locks) { 176 * lock.unlock(); 177 * } 178 * 179 * If we only held the int[] stripes, translating it on the fly to L's, the original locks might 180 * be garbage collected after locking them, ending up in a huge mess. 181 */ 182 @SuppressWarnings("unchecked") // we carefully replaced all keys with their respective L's 183 List<L> asStripes = (List<L>) result; 184 return Collections.unmodifiableList(asStripes); 185 } 186 187 // Static factories 188 189 /** 190 * Creates a {@code Striped<L>} with eagerly initialized, strongly referenced locks. Every lock is 191 * obtained from the passed supplier. 192 * 193 * @param stripes the minimum number of stripes (locks) required 194 * @param supplier a {@code Supplier<L>} object to obtain locks from 195 * @return a new {@code Striped<L>} 196 */ 197 static <L> Striped<L> custom(int stripes, Supplier<L> supplier) { 198 return new CompactStriped<>(stripes, supplier); 199 } 200 201 /** 202 * Creates a {@code Striped<Lock>} with eagerly initialized, strongly referenced locks. Every lock 203 * is reentrant. 204 * 205 * @param stripes the minimum number of stripes (locks) required 206 * @return a new {@code Striped<Lock>} 207 */ 208 public static Striped<Lock> lock(int stripes) { 209 return custom(stripes, PaddedLock::new); 210 } 211 212 /** 213 * Creates a {@code Striped<Lock>} with lazily initialized, weakly referenced locks. Every lock is 214 * reentrant. 215 * 216 * @param stripes the minimum number of stripes (locks) required 217 * @return a new {@code Striped<Lock>} 218 */ 219 public static Striped<Lock> lazyWeakLock(int stripes) { 220 return lazy(stripes, () -> new ReentrantLock(false)); 221 } 222 223 private static <L> Striped<L> lazy(int stripes, Supplier<L> supplier) { 224 return stripes < LARGE_LAZY_CUTOFF 225 ? new SmallLazyStriped<L>(stripes, supplier) 226 : new LargeLazyStriped<L>(stripes, supplier); 227 } 228 229 /** 230 * Creates a {@code Striped<Semaphore>} with eagerly initialized, strongly referenced semaphores, 231 * with the specified number of permits. 232 * 233 * @param stripes the minimum number of stripes (semaphores) required 234 * @param permits the number of permits in each semaphore 235 * @return a new {@code Striped<Semaphore>} 236 */ 237 public static Striped<Semaphore> semaphore(int stripes, int permits) { 238 return custom(stripes, () -> new PaddedSemaphore(permits)); 239 } 240 241 /** 242 * Creates a {@code Striped<Semaphore>} with lazily initialized, weakly referenced semaphores, 243 * with the specified number of permits. 244 * 245 * @param stripes the minimum number of stripes (semaphores) required 246 * @param permits the number of permits in each semaphore 247 * @return a new {@code Striped<Semaphore>} 248 */ 249 public static Striped<Semaphore> lazyWeakSemaphore(int stripes, int permits) { 250 return lazy(stripes, () -> new Semaphore(permits, false)); 251 } 252 253 /** 254 * Creates a {@code Striped<ReadWriteLock>} with eagerly initialized, strongly referenced 255 * read-write locks. Every lock is reentrant. 256 * 257 * @param stripes the minimum number of stripes (locks) required 258 * @return a new {@code Striped<ReadWriteLock>} 259 */ 260 public static Striped<ReadWriteLock> readWriteLock(int stripes) { 261 return custom(stripes, ReentrantReadWriteLock::new); 262 } 263 264 /** 265 * Creates a {@code Striped<ReadWriteLock>} with lazily initialized, weakly referenced read-write 266 * locks. Every lock is reentrant. 267 * 268 * @param stripes the minimum number of stripes (locks) required 269 * @return a new {@code Striped<ReadWriteLock>} 270 */ 271 public static Striped<ReadWriteLock> lazyWeakReadWriteLock(int stripes) { 272 return lazy(stripes, WeakSafeReadWriteLock::new); 273 } 274 /** 275 * ReadWriteLock implementation whose read and write locks retain a reference back to this lock. 276 * Otherwise, a reference to just the read lock or just the write lock would not suffice to ensure 277 * the {@code ReadWriteLock} is retained. 278 */ 279 private static final class WeakSafeReadWriteLock implements ReadWriteLock { 280 private final ReadWriteLock delegate; 281 282 WeakSafeReadWriteLock() { 283 this.delegate = new ReentrantReadWriteLock(); 284 } 285 286 @Override 287 public Lock readLock() { 288 return new WeakSafeLock(delegate.readLock(), this); 289 } 290 291 @Override 292 public Lock writeLock() { 293 return new WeakSafeLock(delegate.writeLock(), this); 294 } 295 } 296 297 /** Lock object that ensures a strong reference is retained to a specified object. */ 298 private static final class WeakSafeLock extends ForwardingLock { 299 private final Lock delegate; 300 301 @SuppressWarnings("unused") 302 private final WeakSafeReadWriteLock strongReference; 303 304 WeakSafeLock(Lock delegate, WeakSafeReadWriteLock strongReference) { 305 this.delegate = delegate; 306 this.strongReference = strongReference; 307 } 308 309 @Override 310 Lock delegate() { 311 return delegate; 312 } 313 314 @Override 315 public Condition newCondition() { 316 return new WeakSafeCondition(delegate.newCondition(), strongReference); 317 } 318 } 319 320 /** Condition object that ensures a strong reference is retained to a specified object. */ 321 private static final class WeakSafeCondition extends ForwardingCondition { 322 private final Condition delegate; 323 324 @SuppressWarnings("unused") 325 private final WeakSafeReadWriteLock strongReference; 326 327 WeakSafeCondition(Condition delegate, WeakSafeReadWriteLock strongReference) { 328 this.delegate = delegate; 329 this.strongReference = strongReference; 330 } 331 332 @Override 333 Condition delegate() { 334 return delegate; 335 } 336 } 337 338 private abstract static class PowerOfTwoStriped<L> extends Striped<L> { 339 /** Capacity (power of two) minus one, for fast mod evaluation */ 340 final int mask; 341 342 PowerOfTwoStriped(int stripes) { 343 Preconditions.checkArgument(stripes > 0, "Stripes must be positive"); 344 this.mask = stripes > Ints.MAX_POWER_OF_TWO ? ALL_SET : ceilToPowerOfTwo(stripes) - 1; 345 } 346 347 @Override 348 final int indexFor(Object key) { 349 int hash = smear(key.hashCode()); 350 return hash & mask; 351 } 352 353 @Override 354 public final L get(Object key) { 355 return getAt(indexFor(key)); 356 } 357 } 358 359 /** 360 * Implementation of Striped where 2^k stripes are represented as an array of the same length, 361 * eagerly initialized. 362 */ 363 private static class CompactStriped<L> extends PowerOfTwoStriped<L> { 364 /** Size is a power of two. */ 365 private final Object[] array; 366 367 private CompactStriped(int stripes, Supplier<L> supplier) { 368 super(stripes); 369 Preconditions.checkArgument(stripes <= Ints.MAX_POWER_OF_TWO, "Stripes must be <= 2^30)"); 370 371 this.array = new Object[mask + 1]; 372 for (int i = 0; i < array.length; i++) { 373 array[i] = supplier.get(); 374 } 375 } 376 377 @SuppressWarnings("unchecked") // we only put L's in the array 378 @Override 379 public L getAt(int index) { 380 return (L) array[index]; 381 } 382 383 @Override 384 public int size() { 385 return array.length; 386 } 387 } 388 389 /** 390 * Implementation of Striped where up to 2^k stripes can be represented, using an 391 * AtomicReferenceArray of size 2^k. To map a user key into a stripe, we take a k-bit slice of the 392 * user key's (smeared) hashCode(). The stripes are lazily initialized and are weakly referenced. 393 */ 394 @VisibleForTesting 395 static class SmallLazyStriped<L> extends PowerOfTwoStriped<L> { 396 final AtomicReferenceArray<@Nullable ArrayReference<? extends L>> locks; 397 final Supplier<L> supplier; 398 final int size; 399 final ReferenceQueue<L> queue = new ReferenceQueue<>(); 400 401 SmallLazyStriped(int stripes, Supplier<L> supplier) { 402 super(stripes); 403 this.size = (mask == ALL_SET) ? Integer.MAX_VALUE : mask + 1; 404 this.locks = new AtomicReferenceArray<>(size); 405 this.supplier = supplier; 406 } 407 408 @Override 409 public L getAt(int index) { 410 if (size != Integer.MAX_VALUE) { 411 Preconditions.checkElementIndex(index, size()); 412 } // else no check necessary, all index values are valid 413 ArrayReference<? extends L> existingRef = locks.get(index); 414 L existing = existingRef == null ? null : existingRef.get(); 415 if (existing != null) { 416 return existing; 417 } 418 L created = supplier.get(); 419 ArrayReference<L> newRef = new ArrayReference<>(created, index, queue); 420 while (!locks.compareAndSet(index, existingRef, newRef)) { 421 // we raced, we need to re-read and try again 422 existingRef = locks.get(index); 423 existing = existingRef == null ? null : existingRef.get(); 424 if (existing != null) { 425 return existing; 426 } 427 } 428 drainQueue(); 429 return created; 430 } 431 432 // N.B. Draining the queue is only necessary to ensure that we don't accumulate empty references 433 // in the array. We could skip this if we decide we don't care about holding on to Reference 434 // objects indefinitely. 435 private void drainQueue() { 436 Reference<? extends L> ref; 437 while ((ref = queue.poll()) != null) { 438 // We only ever register ArrayReferences with the queue so this is always safe. 439 ArrayReference<? extends L> arrayRef = (ArrayReference<? extends L>) ref; 440 // Try to clear out the array slot, n.b. if we fail that is fine, in either case the 441 // arrayRef will be out of the array after this step. 442 locks.compareAndSet(arrayRef.index, arrayRef, null); 443 } 444 } 445 446 @Override 447 public int size() { 448 return size; 449 } 450 451 private static final class ArrayReference<L> extends WeakReference<L> { 452 final int index; 453 454 ArrayReference(L referent, int index, ReferenceQueue<L> queue) { 455 super(referent, queue); 456 this.index = index; 457 } 458 } 459 } 460 461 /** 462 * Implementation of Striped where up to 2^k stripes can be represented, using a ConcurrentMap 463 * where the key domain is [0..2^k). To map a user key into a stripe, we take a k-bit slice of the 464 * user key's (smeared) hashCode(). The stripes are lazily initialized and are weakly referenced. 465 */ 466 @VisibleForTesting 467 static class LargeLazyStriped<L> extends PowerOfTwoStriped<L> { 468 final ConcurrentMap<Integer, L> locks; 469 final Supplier<L> supplier; 470 final int size; 471 472 LargeLazyStriped(int stripes, Supplier<L> supplier) { 473 super(stripes); 474 this.size = (mask == ALL_SET) ? Integer.MAX_VALUE : mask + 1; 475 this.supplier = supplier; 476 this.locks = new MapMaker().weakValues().makeMap(); 477 } 478 479 @Override 480 public L getAt(int index) { 481 if (size != Integer.MAX_VALUE) { 482 Preconditions.checkElementIndex(index, size()); 483 } // else no check necessary, all index values are valid 484 L existing = locks.get(index); 485 if (existing != null) { 486 return existing; 487 } 488 L created = supplier.get(); 489 existing = locks.putIfAbsent(index, created); 490 return MoreObjects.firstNonNull(existing, created); 491 } 492 493 @Override 494 public int size() { 495 return size; 496 } 497 } 498 499 /** A bit mask were all bits are set. */ 500 private static final int ALL_SET = ~0; 501 502 private static int ceilToPowerOfTwo(int x) { 503 return 1 << IntMath.log2(x, RoundingMode.CEILING); 504 } 505 506 /* 507 * This method was written by Doug Lea with assistance from members of JCP JSR-166 Expert Group 508 * and released to the public domain, as explained at 509 * http://creativecommons.org/licenses/publicdomain 510 * 511 * As of 2010/06/11, this method is identical to the (package private) hash method in OpenJDK 7's 512 * java.util.HashMap class. 513 */ 514 // Copied from java/com/google/common/collect/Hashing.java 515 private static int smear(int hashCode) { 516 hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12); 517 return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4); 518 } 519 520 private static class PaddedLock extends ReentrantLock { 521 /* 522 * Padding from 40 into 64 bytes, same size as cache line. Might be beneficial to add a fourth 523 * long here, to minimize chance of interference between consecutive locks, but I couldn't 524 * observe any benefit from that. 525 */ 526 long unused1; 527 long unused2; 528 long unused3; 529 530 PaddedLock() { 531 super(false); 532 } 533 } 534 535 private static class PaddedSemaphore extends Semaphore { 536 // See PaddedReentrantLock comment 537 long unused1; 538 long unused2; 539 long unused3; 540 541 PaddedSemaphore(int permits) { 542 super(permits, false); 543 } 544 } 545}