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