001 /*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.util.concurrent;
018
019 import com.google.common.annotations.Beta;
020 import com.google.common.base.Functions;
021 import com.google.common.base.Preconditions;
022 import com.google.common.base.Supplier;
023 import com.google.common.collect.Iterables;
024 import com.google.common.collect.MapMaker;
025 import com.google.common.math.IntMath;
026 import com.google.common.primitives.Ints;
027
028 import java.math.RoundingMode;
029 import java.util.Arrays;
030 import java.util.Collections;
031 import java.util.List;
032 import java.util.concurrent.ConcurrentMap;
033 import java.util.concurrent.Semaphore;
034 import java.util.concurrent.locks.Lock;
035 import java.util.concurrent.locks.ReadWriteLock;
036 import java.util.concurrent.locks.ReentrantLock;
037 import java.util.concurrent.locks.ReentrantReadWriteLock;
038
039 /**
040 * A striped {@code Lock/Semaphore/ReadWriteLock}. This offers the underlying lock striping
041 * similar to that of {@code ConcurrentHashMap} in a reusable form, and extends it for
042 * semaphores and read-write locks. Conceptually, lock striping is the technique of dividing a lock
043 * into many <i>stripes</i>, increasing the granularity of a single lock and allowing independent
044 * operations to lock different stripes and proceed concurrently, instead of creating contention
045 * for a single lock.
046 *
047 * <p>The guarantee provided by this class is that equal keys lead to the same lock (or semaphore),
048 * i.e. {@code if (key1.equals(key2))} then {@code striped.get(key1) == striped.get(key2)}
049 * (assuming {@link Object#hashCode()} is correctly implemented for the keys). Note
050 * that if {@code key1} is <strong>not</strong> equal to {@code key2}, it is <strong>not</strong>
051 * guaranteed that {@code striped.get(key1) != striped.get(key2)}; the elements might nevertheless
052 * be mapped to the same lock. The lower the number of stripes, the higher the probability of this
053 * happening.
054 *
055 * <p>There are three flavors of this class: {@code Striped<Lock>}, {@code Striped<Semaphore>},
056 * and {@code Striped<ReadWriteLock>}. For each type, two implementations are offered:
057 * {@linkplain #lock(int) strong} and {@linkplain #lazyWeakLock(int) weak}
058 * {@code Striped<Lock>}, {@linkplain #semaphore(int, int) strong} and {@linkplain
059 * #lazyWeakSemaphore(int, int) weak} {@code Striped<Semaphore>}, and {@linkplain
060 * #readWriteLock(int) strong} and {@linkplain #lazyWeakReadWriteLock(int) weak}
061 * {@code Striped<ReadWriteLock>}. <i>Strong</i> means that all stripes (locks/semaphores) are
062 * initialized eagerly, and are not reclaimed unless {@code Striped} itself is reclaimable.
063 * <i>Weak</i> means that locks/semaphores are created lazily, and they are allowed to be reclaimed
064 * if nobody is holding on to them. This is useful, for example, if one wants to create a {@code
065 * Striped<Lock>} of many locks, but worries that in most cases only a small portion of these
066 * would be in use.
067 *
068 * <p>Prior to this class, one might be tempted to use {@code Map<K, Lock>}, where {@code K}
069 * represents the task. This maximizes concurrency by having each unique key mapped to a unique
070 * lock, but also maximizes memory footprint. On the other extreme, one could use a single lock
071 * for all tasks, which minimizes memory footprint but also minimizes concurrency. Instead of
072 * choosing either of these extremes, {@code Striped} allows the user to trade between required
073 * concurrency and memory footprint. For example, if a set of tasks are CPU-bound, one could easily
074 * create a very compact {@code Striped<Lock>} of {@code availableProcessors() * 4} stripes,
075 * instead of possibly thousands of locks which could be created in a {@code Map<K, Lock>}
076 * structure.
077 *
078 * @author Dimitris Andreou
079 * @since 13.0
080 */
081 @Beta
082 public abstract class Striped<L> {
083 private Striped() {}
084
085 /**
086 * Returns the stripe that corresponds to the passed key. It is always guaranteed that if
087 * {@code key1.equals(key2)}, then {@code get(key1) == get(key2)}.
088 *
089 * @param key an arbitrary, non-null key
090 * @return the stripe that the passed key corresponds to
091 */
092 public abstract L get(Object key);
093
094 /**
095 * Returns the stripe at the specified index. Valid indexes are 0, inclusively, to
096 * {@code size()}, exclusively.
097 *
098 * @param index the index of the stripe to return; must be in {@code [0...size())}
099 * @return the stripe at the specified index
100 */
101 public abstract L getAt(int index);
102
103 /**
104 * Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key).
105 */
106 abstract int indexFor(Object key);
107
108 /**
109 * Returns the total number of stripes in this instance.
110 */
111 public abstract int size();
112
113 /**
114 * Returns the stripes that correspond to the passed objects, in ascending (as per
115 * {@link #getAt(int)}) order. Thus, threads that use the stripes in the order returned
116 * by this method are guaranteed to not deadlock each other.
117 *
118 * <p>It should be noted that using a {@code Striped<L>} with relatively few stripes, and
119 * {@code bulkGet(keys)} with a relative large number of keys can cause an excessive number
120 * of shared stripes (much like the birthday paradox, where much fewer than anticipated birthdays
121 * are needed for a pair of them to match). Please consider carefully the implications of the
122 * number of stripes, the intended concurrency level, and the typical number of keys used in a
123 * {@code bulkGet(keys)} operation. See <a href="http://www.mathpages.com/home/kmath199.htm">Balls
124 * in Bins model</a> for mathematical formulas that can be used to estimate the probability of
125 * collisions.
126 *
127 * @param keys arbitrary non-null keys
128 * @return the stripes corresponding to the objects (one per each object, derived by delegating
129 * to {@link #get(Object)}; may contain duplicates), in an increasing index order.
130 */
131 public Iterable<L> bulkGet(Iterable<?> keys) {
132 // Initially using the array to store the keys, then reusing it to store the respective L's
133 final Object[] array = Iterables.toArray(keys, Object.class);
134 int[] stripes = new int[array.length];
135 for (int i = 0; i < array.length; i++) {
136 stripes[i] = indexFor(array[i]);
137 }
138 Arrays.sort(stripes);
139 for (int i = 0; i < array.length; i++) {
140 array[i] = getAt(stripes[i]);
141 }
142 /*
143 * Note that the returned Iterable holds references to the returned stripes, to avoid
144 * error-prone code like:
145 *
146 * Striped<Lock> stripedLock = Striped.lazyWeakXXX(...)'
147 * Iterable<Lock> locks = stripedLock.bulkGet(keys);
148 * for (Lock lock : locks) {
149 * lock.lock();
150 * }
151 * operation();
152 * for (Lock lock : locks) {
153 * lock.unlock();
154 * }
155 *
156 * If we only held the int[] stripes, translating it on the fly to L's, the original locks
157 * might be garbage collected after locking them, ending up in a huge mess.
158 */
159 @SuppressWarnings("unchecked") // we carefully replaced all keys with their respective L's
160 List<L> asList = (List<L>) Arrays.asList(array);
161 return Collections.unmodifiableList(asList);
162 }
163
164 // Static factories
165
166 /**
167 * Creates a {@code Striped<Lock>} with eagerly initialized, strongly referenced locks, with the
168 * specified fairness. Every lock is reentrant.
169 *
170 * @param stripes the minimum number of stripes (locks) required
171 * @return a new {@code Striped<Lock>}
172 */
173 public static Striped<Lock> lock(int stripes) {
174 return new CompactStriped<Lock>(stripes, new Supplier<Lock>() {
175 public Lock get() {
176 return new PaddedLock();
177 }
178 });
179 }
180
181 /**
182 * Creates a {@code Striped<Lock>} with lazily initialized, weakly referenced locks, with the
183 * specified fairness. Every lock is reentrant.
184 *
185 * @param stripes the minimum number of stripes (locks) required
186 * @return a new {@code Striped<Lock>}
187 */
188 public static Striped<Lock> lazyWeakLock(int stripes) {
189 return new LazyStriped<Lock>(stripes, new Supplier<Lock>() {
190 public Lock get() {
191 return new ReentrantLock(false);
192 }
193 });
194 }
195
196 /**
197 * Creates a {@code Striped<Semaphore>} with eagerly initialized, strongly referenced semaphores,
198 * with the specified number of permits and fairness.
199 *
200 * @param stripes the minimum number of stripes (semaphores) required
201 * @param permits the number of permits in each semaphore
202 * @return a new {@code Striped<Semaphore>}
203 */
204 public static Striped<Semaphore> semaphore(int stripes, final int permits) {
205 return new CompactStriped<Semaphore>(stripes, new Supplier<Semaphore>() {
206 public Semaphore get() {
207 return new PaddedSemaphore(permits);
208 }
209 });
210 }
211
212 /**
213 * Creates a {@code Striped<Semaphore>} with lazily initialized, weakly referenced semaphores,
214 * with the specified number of permits and fairness.
215 *
216 * @param stripes the minimum number of stripes (semaphores) required
217 * @param permits the number of permits in each semaphore
218 * @return a new {@code Striped<Semaphore>}
219 */
220 public static Striped<Semaphore> lazyWeakSemaphore(int stripes, final int permits) {
221 return new LazyStriped<Semaphore>(stripes, new Supplier<Semaphore>() {
222 public Semaphore get() {
223 return new Semaphore(permits, false);
224 }
225 });
226 }
227
228 /**
229 * Creates a {@code Striped<ReadWriteLock>} with eagerly initialized, strongly referenced
230 * read-write locks, with the specified fairness. Every lock is reentrant.
231 *
232 * @param stripes the minimum number of stripes (locks) required
233 * @return a new {@code Striped<ReadWriteLock>}
234 */
235 public static Striped<ReadWriteLock> readWriteLock(int stripes) {
236 return new CompactStriped<ReadWriteLock>(stripes, READ_WRITE_LOCK_SUPPLIER);
237 }
238
239 /**
240 * Creates a {@code Striped<ReadWriteLock>} with lazily initialized, weakly referenced
241 * read-write locks, with the specified fairness. Every lock is reentrant.
242 *
243 * @param stripes the minimum number of stripes (locks) required
244 * @return a new {@code Striped<ReadWriteLock>}
245 */
246 public static Striped<ReadWriteLock> lazyWeakReadWriteLock(int stripes) {
247 return new LazyStriped<ReadWriteLock>(stripes, READ_WRITE_LOCK_SUPPLIER);
248 }
249
250 // ReentrantReadWriteLock is large enough to make padding probably unnecessary
251 private static final Supplier<ReadWriteLock> READ_WRITE_LOCK_SUPPLIER =
252 new Supplier<ReadWriteLock>() {
253 public ReadWriteLock get() {
254 return new ReentrantReadWriteLock();
255 }
256 };
257
258 private abstract static class PowerOfTwoStriped<L> extends Striped<L> {
259 /** Capacity (power of two) minus one, for fast mod evaluation */
260 final int mask;
261
262 PowerOfTwoStriped(int stripes) {
263 Preconditions.checkArgument(stripes > 0, "Stripes must be positive");
264 this.mask = stripes > Ints.MAX_POWER_OF_TWO ? ALL_SET : ceilToPowerOfTwo(stripes) - 1;
265 }
266
267 @Override final int indexFor(Object key) {
268 int hash = smear(key.hashCode());
269 return hash & mask;
270 }
271
272 @Override public final L get(Object key) {
273 return getAt(indexFor(key));
274 }
275 }
276
277 /**
278 * Implementation of Striped where 2^k stripes are represented as an array of the same length,
279 * eagerly initialized.
280 */
281 private static class CompactStriped<L> extends PowerOfTwoStriped<L> {
282 /** Size is a power of two. */
283 private final Object[] array;
284
285 private CompactStriped(int stripes, Supplier<L> supplier) {
286 super(stripes);
287 Preconditions.checkArgument(stripes <= Ints.MAX_POWER_OF_TWO, "Stripes must be <= 2^30)");
288
289 this.array = new Object[mask + 1];
290 for (int i = 0; i < array.length; i++) {
291 array[i] = supplier.get();
292 }
293 }
294
295 @SuppressWarnings("unchecked") // we only put L's in the array
296 @Override public L getAt(int index) {
297 return (L) array[index];
298 }
299
300 @Override public int size() {
301 return array.length;
302 }
303 }
304
305 /**
306 * Implementation of Striped where up to 2^k stripes can be represented, using a Cache
307 * where the key domain is [0..2^k). To map a user key into a stripe, we take a k-bit slice of the
308 * user key's (smeared) hashCode(). The stripes are lazily initialized and are weakly referenced.
309 */
310 private static class LazyStriped<L> extends PowerOfTwoStriped<L> {
311 final ConcurrentMap<Integer, L> cache;
312 final int size;
313
314 LazyStriped(int stripes, Supplier<L> supplier) {
315 super(stripes);
316 this.size = (mask == ALL_SET) ? Integer.MAX_VALUE : mask + 1;
317 this.cache = new MapMaker().weakValues().makeComputingMap(Functions.forSupplier(supplier));
318 }
319
320 @Override public L getAt(int index) {
321 Preconditions.checkElementIndex(index, size());
322 return cache.get(index);
323 }
324
325 @Override public int size() {
326 return size;
327 }
328 }
329
330 /**
331 * A bit mask were all bits are set.
332 */
333 private static final int ALL_SET = ~0;
334
335 private static int ceilToPowerOfTwo(int x) {
336 return 1 << IntMath.log2(x, RoundingMode.CEILING);
337 }
338
339 /*
340 * This method was written by Doug Lea with assistance from members of JCP
341 * JSR-166 Expert Group and released to the public domain, as explained at
342 * http://creativecommons.org/licenses/publicdomain
343 *
344 * As of 2010/06/11, this method is identical to the (package private) hash
345 * method in OpenJDK 7's java.util.HashMap class.
346 */
347 // Copied from java/com/google/common/collect/Hashing.java
348 private static int smear(int hashCode) {
349 hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
350 return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
351 }
352
353 private static class PaddedLock extends ReentrantLock {
354 /*
355 * Padding from 40 into 64 bytes, same size as cache line. Might be beneficial to add
356 * a fourth long here, to minimize chance of interference between consecutive locks,
357 * but I couldn't observe any benefit from that.
358 */
359 @SuppressWarnings("unused")
360 long q1, q2, q3;
361
362 PaddedLock() {
363 super(false);
364 }
365 }
366
367 private static class PaddedSemaphore extends Semaphore {
368 // See PaddedReentrantLock comment
369 @SuppressWarnings("unused")
370 long q1, q2, q3;
371
372 PaddedSemaphore(int permits) {
373 super(permits, false);
374 }
375 }
376 }