17dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 27dd252788645e940eada959bdde927426e2531c9Paul Duffin * Copyright (C) 2011 The Guava Authors 37dd252788645e940eada959bdde927426e2531c9Paul Duffin * 47dd252788645e940eada959bdde927426e2531c9Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); 57dd252788645e940eada959bdde927426e2531c9Paul Duffin * you may not use this file except in compliance with the License. 67dd252788645e940eada959bdde927426e2531c9Paul Duffin * You may obtain a copy of the License at 77dd252788645e940eada959bdde927426e2531c9Paul Duffin * 87dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0 97dd252788645e940eada959bdde927426e2531c9Paul Duffin * 107dd252788645e940eada959bdde927426e2531c9Paul Duffin * Unless required by applicable law or agreed to in writing, software 117dd252788645e940eada959bdde927426e2531c9Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS, 127dd252788645e940eada959bdde927426e2531c9Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 137dd252788645e940eada959bdde927426e2531c9Paul Duffin * See the License for the specific language governing permissions and 147dd252788645e940eada959bdde927426e2531c9Paul Duffin * limitations under the License. 157dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 167dd252788645e940eada959bdde927426e2531c9Paul Duffin 177dd252788645e940eada959bdde927426e2531c9Paul Duffinpackage com.google.common.util.concurrent; 187dd252788645e940eada959bdde927426e2531c9Paul Duffin 197dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.Beta; 200888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.VisibleForTesting; 213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport com.google.common.base.MoreObjects; 227dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Preconditions; 237dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Supplier; 240888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.collect.ImmutableList; 257dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.Iterables; 267dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.MapMaker; 277dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.math.IntMath; 287dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.primitives.Ints; 297dd252788645e940eada959bdde927426e2531c9Paul Duffin 300888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.lang.ref.Reference; 310888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.lang.ref.ReferenceQueue; 320888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.lang.ref.WeakReference; 337dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.math.RoundingMode; 347dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Arrays; 357dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Collections; 367dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.List; 377dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.ConcurrentMap; 387dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.Semaphore; 390888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.concurrent.atomic.AtomicReferenceArray; 407dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.locks.Lock; 417dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.locks.ReadWriteLock; 427dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.locks.ReentrantLock; 437dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.locks.ReentrantReadWriteLock; 447dd252788645e940eada959bdde927426e2531c9Paul Duffin 457dd252788645e940eada959bdde927426e2531c9Paul Duffin/** 467dd252788645e940eada959bdde927426e2531c9Paul Duffin * A striped {@code Lock/Semaphore/ReadWriteLock}. This offers the underlying lock striping 477dd252788645e940eada959bdde927426e2531c9Paul Duffin * similar to that of {@code ConcurrentHashMap} in a reusable form, and extends it for 487dd252788645e940eada959bdde927426e2531c9Paul Duffin * semaphores and read-write locks. Conceptually, lock striping is the technique of dividing a lock 497dd252788645e940eada959bdde927426e2531c9Paul Duffin * into many <i>stripes</i>, increasing the granularity of a single lock and allowing independent 507dd252788645e940eada959bdde927426e2531c9Paul Duffin * operations to lock different stripes and proceed concurrently, instead of creating contention 517dd252788645e940eada959bdde927426e2531c9Paul Duffin * for a single lock. 527dd252788645e940eada959bdde927426e2531c9Paul Duffin * 537dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>The guarantee provided by this class is that equal keys lead to the same lock (or semaphore), 547dd252788645e940eada959bdde927426e2531c9Paul Duffin * i.e. {@code if (key1.equals(key2))} then {@code striped.get(key1) == striped.get(key2)} 557dd252788645e940eada959bdde927426e2531c9Paul Duffin * (assuming {@link Object#hashCode()} is correctly implemented for the keys). Note 567dd252788645e940eada959bdde927426e2531c9Paul Duffin * that if {@code key1} is <strong>not</strong> equal to {@code key2}, it is <strong>not</strong> 577dd252788645e940eada959bdde927426e2531c9Paul Duffin * guaranteed that {@code striped.get(key1) != striped.get(key2)}; the elements might nevertheless 587dd252788645e940eada959bdde927426e2531c9Paul Duffin * be mapped to the same lock. The lower the number of stripes, the higher the probability of this 597dd252788645e940eada959bdde927426e2531c9Paul Duffin * happening. 607dd252788645e940eada959bdde927426e2531c9Paul Duffin * 617dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>There are three flavors of this class: {@code Striped<Lock>}, {@code Striped<Semaphore>}, 627dd252788645e940eada959bdde927426e2531c9Paul Duffin * and {@code Striped<ReadWriteLock>}. For each type, two implementations are offered: 637dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@linkplain #lock(int) strong} and {@linkplain #lazyWeakLock(int) weak} 647dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code Striped<Lock>}, {@linkplain #semaphore(int, int) strong} and {@linkplain 657dd252788645e940eada959bdde927426e2531c9Paul Duffin * #lazyWeakSemaphore(int, int) weak} {@code Striped<Semaphore>}, and {@linkplain 667dd252788645e940eada959bdde927426e2531c9Paul Duffin * #readWriteLock(int) strong} and {@linkplain #lazyWeakReadWriteLock(int) weak} 677dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code Striped<ReadWriteLock>}. <i>Strong</i> means that all stripes (locks/semaphores) are 687dd252788645e940eada959bdde927426e2531c9Paul Duffin * initialized eagerly, and are not reclaimed unless {@code Striped} itself is reclaimable. 697dd252788645e940eada959bdde927426e2531c9Paul Duffin * <i>Weak</i> means that locks/semaphores are created lazily, and they are allowed to be reclaimed 707dd252788645e940eada959bdde927426e2531c9Paul Duffin * if nobody is holding on to them. This is useful, for example, if one wants to create a {@code 717dd252788645e940eada959bdde927426e2531c9Paul Duffin * Striped<Lock>} of many locks, but worries that in most cases only a small portion of these 727dd252788645e940eada959bdde927426e2531c9Paul Duffin * would be in use. 737dd252788645e940eada959bdde927426e2531c9Paul Duffin * 747dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Prior to this class, one might be tempted to use {@code Map<K, Lock>}, where {@code K} 757dd252788645e940eada959bdde927426e2531c9Paul Duffin * represents the task. This maximizes concurrency by having each unique key mapped to a unique 767dd252788645e940eada959bdde927426e2531c9Paul Duffin * lock, but also maximizes memory footprint. On the other extreme, one could use a single lock 777dd252788645e940eada959bdde927426e2531c9Paul Duffin * for all tasks, which minimizes memory footprint but also minimizes concurrency. Instead of 787dd252788645e940eada959bdde927426e2531c9Paul Duffin * choosing either of these extremes, {@code Striped} allows the user to trade between required 797dd252788645e940eada959bdde927426e2531c9Paul Duffin * concurrency and memory footprint. For example, if a set of tasks are CPU-bound, one could easily 807dd252788645e940eada959bdde927426e2531c9Paul Duffin * create a very compact {@code Striped<Lock>} of {@code availableProcessors() * 4} stripes, 817dd252788645e940eada959bdde927426e2531c9Paul Duffin * instead of possibly thousands of locks which could be created in a {@code Map<K, Lock>} 827dd252788645e940eada959bdde927426e2531c9Paul Duffin * structure. 837dd252788645e940eada959bdde927426e2531c9Paul Duffin * 847dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Dimitris Andreou 857dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 13.0 867dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 877dd252788645e940eada959bdde927426e2531c9Paul Duffin@Beta 887dd252788645e940eada959bdde927426e2531c9Paul Duffinpublic abstract class Striped<L> { 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * If there are at least this many stripes, we assume the memory usage of a ConcurrentMap will be 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * smaller than a large array. (This assumes that in the lazy case, most stripes are unused. As 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * always, if many stripes are in use, a non-lazy striped makes more sense.) 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final int LARGE_LAZY_CUTOFF = 1024; 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin 967dd252788645e940eada959bdde927426e2531c9Paul Duffin private Striped() {} 977dd252788645e940eada959bdde927426e2531c9Paul Duffin 987dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 997dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns the stripe that corresponds to the passed key. It is always guaranteed that if 1007dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code key1.equals(key2)}, then {@code get(key1) == get(key2)}. 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin * 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param key an arbitrary, non-null key 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return the stripe that the passed key corresponds to 1047dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1057dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract L get(Object key); 1067dd252788645e940eada959bdde927426e2531c9Paul Duffin 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns the stripe at the specified index. Valid indexes are 0, inclusively, to 1097dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code size()}, exclusively. 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin * 1117dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param index the index of the stripe to return; must be in {@code [0...size())} 1127dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return the stripe at the specified index 1137dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1147dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract L getAt(int index); 1157dd252788645e940eada959bdde927426e2531c9Paul Duffin 1167dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1177dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns the index to which the given key is mapped, so that getAt(indexFor(key)) == get(key). 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1197dd252788645e940eada959bdde927426e2531c9Paul Duffin abstract int indexFor(Object key); 1207dd252788645e940eada959bdde927426e2531c9Paul Duffin 1217dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1227dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns the total number of stripes in this instance. 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1247dd252788645e940eada959bdde927426e2531c9Paul Duffin public abstract int size(); 1257dd252788645e940eada959bdde927426e2531c9Paul Duffin 1267dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1277dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns the stripes that correspond to the passed objects, in ascending (as per 1287dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@link #getAt(int)}) order. Thus, threads that use the stripes in the order returned 1297dd252788645e940eada959bdde927426e2531c9Paul Duffin * by this method are guaranteed to not deadlock each other. 1307dd252788645e940eada959bdde927426e2531c9Paul Duffin * 1317dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>It should be noted that using a {@code Striped<L>} with relatively few stripes, and 1327dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code bulkGet(keys)} with a relative large number of keys can cause an excessive number 1337dd252788645e940eada959bdde927426e2531c9Paul Duffin * of shared stripes (much like the birthday paradox, where much fewer than anticipated birthdays 1347dd252788645e940eada959bdde927426e2531c9Paul Duffin * are needed for a pair of them to match). Please consider carefully the implications of the 1357dd252788645e940eada959bdde927426e2531c9Paul Duffin * number of stripes, the intended concurrency level, and the typical number of keys used in a 1367dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code bulkGet(keys)} operation. See <a href="http://www.mathpages.com/home/kmath199.htm">Balls 1377dd252788645e940eada959bdde927426e2531c9Paul Duffin * in Bins model</a> for mathematical formulas that can be used to estimate the probability of 1387dd252788645e940eada959bdde927426e2531c9Paul Duffin * collisions. 1397dd252788645e940eada959bdde927426e2531c9Paul Duffin * 1407dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param keys arbitrary non-null keys 1417dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return the stripes corresponding to the objects (one per each object, derived by delegating 1427dd252788645e940eada959bdde927426e2531c9Paul Duffin * to {@link #get(Object)}; may contain duplicates), in an increasing index order. 1437dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1447dd252788645e940eada959bdde927426e2531c9Paul Duffin public Iterable<L> bulkGet(Iterable<?> keys) { 1457dd252788645e940eada959bdde927426e2531c9Paul Duffin // Initially using the array to store the keys, then reusing it to store the respective L's 1467dd252788645e940eada959bdde927426e2531c9Paul Duffin final Object[] array = Iterables.toArray(keys, Object.class); 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (array.length == 0) { 1480888a09821a98ac0680fad765217302858e70fa4Paul Duffin return ImmutableList.of(); 1490888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1507dd252788645e940eada959bdde927426e2531c9Paul Duffin int[] stripes = new int[array.length]; 1517dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < array.length; i++) { 1527dd252788645e940eada959bdde927426e2531c9Paul Duffin stripes[i] = indexFor(array[i]); 1537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1547dd252788645e940eada959bdde927426e2531c9Paul Duffin Arrays.sort(stripes); 1550888a09821a98ac0680fad765217302858e70fa4Paul Duffin // optimize for runs of identical stripes 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin int previousStripe = stripes[0]; 1570888a09821a98ac0680fad765217302858e70fa4Paul Duffin array[0] = getAt(previousStripe); 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 1; i < array.length; i++) { 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin int currentStripe = stripes[i]; 1600888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (currentStripe == previousStripe) { 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin array[i] = array[i - 1]; 1620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } else { 1630888a09821a98ac0680fad765217302858e70fa4Paul Duffin array[i] = getAt(currentStripe); 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin previousStripe = currentStripe; 1650888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1667dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1677dd252788645e940eada959bdde927426e2531c9Paul Duffin /* 1687dd252788645e940eada959bdde927426e2531c9Paul Duffin * Note that the returned Iterable holds references to the returned stripes, to avoid 1697dd252788645e940eada959bdde927426e2531c9Paul Duffin * error-prone code like: 1707dd252788645e940eada959bdde927426e2531c9Paul Duffin * 1717dd252788645e940eada959bdde927426e2531c9Paul Duffin * Striped<Lock> stripedLock = Striped.lazyWeakXXX(...)' 1727dd252788645e940eada959bdde927426e2531c9Paul Duffin * Iterable<Lock> locks = stripedLock.bulkGet(keys); 1737dd252788645e940eada959bdde927426e2531c9Paul Duffin * for (Lock lock : locks) { 1747dd252788645e940eada959bdde927426e2531c9Paul Duffin * lock.lock(); 1757dd252788645e940eada959bdde927426e2531c9Paul Duffin * } 1767dd252788645e940eada959bdde927426e2531c9Paul Duffin * operation(); 1777dd252788645e940eada959bdde927426e2531c9Paul Duffin * for (Lock lock : locks) { 1787dd252788645e940eada959bdde927426e2531c9Paul Duffin * lock.unlock(); 1797dd252788645e940eada959bdde927426e2531c9Paul Duffin * } 1807dd252788645e940eada959bdde927426e2531c9Paul Duffin * 1817dd252788645e940eada959bdde927426e2531c9Paul Duffin * If we only held the int[] stripes, translating it on the fly to L's, the original locks 1827dd252788645e940eada959bdde927426e2531c9Paul Duffin * might be garbage collected after locking them, ending up in a huge mess. 1837dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // we carefully replaced all keys with their respective L's 1857dd252788645e940eada959bdde927426e2531c9Paul Duffin List<L> asList = (List<L>) Arrays.asList(array); 1867dd252788645e940eada959bdde927426e2531c9Paul Duffin return Collections.unmodifiableList(asList); 1877dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1887dd252788645e940eada959bdde927426e2531c9Paul Duffin 1897dd252788645e940eada959bdde927426e2531c9Paul Duffin // Static factories 1907dd252788645e940eada959bdde927426e2531c9Paul Duffin 1917dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a {@code Striped<Lock>} with eagerly initialized, strongly referenced locks. 1930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Every lock is reentrant. 1947dd252788645e940eada959bdde927426e2531c9Paul Duffin * 1957dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param stripes the minimum number of stripes (locks) required 1967dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return a new {@code Striped<Lock>} 1977dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1987dd252788645e940eada959bdde927426e2531c9Paul Duffin public static Striped<Lock> lock(int stripes) { 1997dd252788645e940eada959bdde927426e2531c9Paul Duffin return new CompactStriped<Lock>(stripes, new Supplier<Lock>() { 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Lock get() { 2017dd252788645e940eada959bdde927426e2531c9Paul Duffin return new PaddedLock(); 2027dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2037dd252788645e940eada959bdde927426e2531c9Paul Duffin }); 2047dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2057dd252788645e940eada959bdde927426e2531c9Paul Duffin 2067dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 2070888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a {@code Striped<Lock>} with lazily initialized, weakly referenced locks. 2080888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Every lock is reentrant. 2097dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2107dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param stripes the minimum number of stripes (locks) required 2117dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return a new {@code Striped<Lock>} 2127dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 2137dd252788645e940eada959bdde927426e2531c9Paul Duffin public static Striped<Lock> lazyWeakLock(int stripes) { 2140888a09821a98ac0680fad765217302858e70fa4Paul Duffin return lazy(stripes, new Supplier<Lock>() { 2150888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Lock get() { 2167dd252788645e940eada959bdde927426e2531c9Paul Duffin return new ReentrantLock(false); 2177dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2187dd252788645e940eada959bdde927426e2531c9Paul Duffin }); 2197dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2207dd252788645e940eada959bdde927426e2531c9Paul Duffin 2210888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static <L> Striped<L> lazy(int stripes, Supplier<L> supplier) { 2220888a09821a98ac0680fad765217302858e70fa4Paul Duffin return stripes < LARGE_LAZY_CUTOFF 2230888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? new SmallLazyStriped<L>(stripes, supplier) 2240888a09821a98ac0680fad765217302858e70fa4Paul Duffin : new LargeLazyStriped<L>(stripes, supplier); 2250888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2260888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2277dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 2287dd252788645e940eada959bdde927426e2531c9Paul Duffin * Creates a {@code Striped<Semaphore>} with eagerly initialized, strongly referenced semaphores, 2290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * with the specified number of permits. 2307dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2317dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param stripes the minimum number of stripes (semaphores) required 2327dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param permits the number of permits in each semaphore 2337dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return a new {@code Striped<Semaphore>} 2347dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 2357dd252788645e940eada959bdde927426e2531c9Paul Duffin public static Striped<Semaphore> semaphore(int stripes, final int permits) { 2367dd252788645e940eada959bdde927426e2531c9Paul Duffin return new CompactStriped<Semaphore>(stripes, new Supplier<Semaphore>() { 2370888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Semaphore get() { 2387dd252788645e940eada959bdde927426e2531c9Paul Duffin return new PaddedSemaphore(permits); 2397dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2407dd252788645e940eada959bdde927426e2531c9Paul Duffin }); 2417dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2427dd252788645e940eada959bdde927426e2531c9Paul Duffin 2437dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 2447dd252788645e940eada959bdde927426e2531c9Paul Duffin * Creates a {@code Striped<Semaphore>} with lazily initialized, weakly referenced semaphores, 2450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * with the specified number of permits. 2467dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2477dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param stripes the minimum number of stripes (semaphores) required 2487dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param permits the number of permits in each semaphore 2497dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return a new {@code Striped<Semaphore>} 2507dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 2517dd252788645e940eada959bdde927426e2531c9Paul Duffin public static Striped<Semaphore> lazyWeakSemaphore(int stripes, final int permits) { 2520888a09821a98ac0680fad765217302858e70fa4Paul Duffin return lazy(stripes, new Supplier<Semaphore>() { 2530888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Semaphore get() { 2547dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Semaphore(permits, false); 2557dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2567dd252788645e940eada959bdde927426e2531c9Paul Duffin }); 2577dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2587dd252788645e940eada959bdde927426e2531c9Paul Duffin 2597dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 2607dd252788645e940eada959bdde927426e2531c9Paul Duffin * Creates a {@code Striped<ReadWriteLock>} with eagerly initialized, strongly referenced 2610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * read-write locks. Every lock is reentrant. 2627dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2637dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param stripes the minimum number of stripes (locks) required 2647dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return a new {@code Striped<ReadWriteLock>} 2657dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 2667dd252788645e940eada959bdde927426e2531c9Paul Duffin public static Striped<ReadWriteLock> readWriteLock(int stripes) { 2677dd252788645e940eada959bdde927426e2531c9Paul Duffin return new CompactStriped<ReadWriteLock>(stripes, READ_WRITE_LOCK_SUPPLIER); 2687dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2697dd252788645e940eada959bdde927426e2531c9Paul Duffin 2707dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 2717dd252788645e940eada959bdde927426e2531c9Paul Duffin * Creates a {@code Striped<ReadWriteLock>} with lazily initialized, weakly referenced 2720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * read-write locks. Every lock is reentrant. 2737dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2747dd252788645e940eada959bdde927426e2531c9Paul Duffin * @param stripes the minimum number of stripes (locks) required 2757dd252788645e940eada959bdde927426e2531c9Paul Duffin * @return a new {@code Striped<ReadWriteLock>} 2767dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 2777dd252788645e940eada959bdde927426e2531c9Paul Duffin public static Striped<ReadWriteLock> lazyWeakReadWriteLock(int stripes) { 2780888a09821a98ac0680fad765217302858e70fa4Paul Duffin return lazy(stripes, READ_WRITE_LOCK_SUPPLIER); 2797dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2807dd252788645e940eada959bdde927426e2531c9Paul Duffin 2817dd252788645e940eada959bdde927426e2531c9Paul Duffin // ReentrantReadWriteLock is large enough to make padding probably unnecessary 2820888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final Supplier<ReadWriteLock> READ_WRITE_LOCK_SUPPLIER = 2830888a09821a98ac0680fad765217302858e70fa4Paul Duffin new Supplier<ReadWriteLock>() { 2840888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public ReadWriteLock get() { 2857dd252788645e940eada959bdde927426e2531c9Paul Duffin return new ReentrantReadWriteLock(); 2867dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2877dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 2887dd252788645e940eada959bdde927426e2531c9Paul Duffin 2897dd252788645e940eada959bdde927426e2531c9Paul Duffin private abstract static class PowerOfTwoStriped<L> extends Striped<L> { 2907dd252788645e940eada959bdde927426e2531c9Paul Duffin /** Capacity (power of two) minus one, for fast mod evaluation */ 2917dd252788645e940eada959bdde927426e2531c9Paul Duffin final int mask; 2927dd252788645e940eada959bdde927426e2531c9Paul Duffin 2937dd252788645e940eada959bdde927426e2531c9Paul Duffin PowerOfTwoStriped(int stripes) { 2947dd252788645e940eada959bdde927426e2531c9Paul Duffin Preconditions.checkArgument(stripes > 0, "Stripes must be positive"); 2957dd252788645e940eada959bdde927426e2531c9Paul Duffin this.mask = stripes > Ints.MAX_POWER_OF_TWO ? ALL_SET : ceilToPowerOfTwo(stripes) - 1; 2967dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2977dd252788645e940eada959bdde927426e2531c9Paul Duffin 2980888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override final int indexFor(Object key) { 2997dd252788645e940eada959bdde927426e2531c9Paul Duffin int hash = smear(key.hashCode()); 3007dd252788645e940eada959bdde927426e2531c9Paul Duffin return hash & mask; 3017dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3027dd252788645e940eada959bdde927426e2531c9Paul Duffin 3030888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public final L get(Object key) { 3047dd252788645e940eada959bdde927426e2531c9Paul Duffin return getAt(indexFor(key)); 3057dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3067dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3077dd252788645e940eada959bdde927426e2531c9Paul Duffin 3087dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 3097dd252788645e940eada959bdde927426e2531c9Paul Duffin * Implementation of Striped where 2^k stripes are represented as an array of the same length, 3107dd252788645e940eada959bdde927426e2531c9Paul Duffin * eagerly initialized. 3117dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 3127dd252788645e940eada959bdde927426e2531c9Paul Duffin private static class CompactStriped<L> extends PowerOfTwoStriped<L> { 3137dd252788645e940eada959bdde927426e2531c9Paul Duffin /** Size is a power of two. */ 3147dd252788645e940eada959bdde927426e2531c9Paul Duffin private final Object[] array; 3157dd252788645e940eada959bdde927426e2531c9Paul Duffin 3167dd252788645e940eada959bdde927426e2531c9Paul Duffin private CompactStriped(int stripes, Supplier<L> supplier) { 3177dd252788645e940eada959bdde927426e2531c9Paul Duffin super(stripes); 3187dd252788645e940eada959bdde927426e2531c9Paul Duffin Preconditions.checkArgument(stripes <= Ints.MAX_POWER_OF_TWO, "Stripes must be <= 2^30)"); 3197dd252788645e940eada959bdde927426e2531c9Paul Duffin 3207dd252788645e940eada959bdde927426e2531c9Paul Duffin this.array = new Object[mask + 1]; 3217dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int i = 0; i < array.length; i++) { 3227dd252788645e940eada959bdde927426e2531c9Paul Duffin array[i] = supplier.get(); 3237dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3257dd252788645e940eada959bdde927426e2531c9Paul Duffin 3260888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // we only put L's in the array 3270888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public L getAt(int index) { 3287dd252788645e940eada959bdde927426e2531c9Paul Duffin return (L) array[index]; 3297dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3307dd252788645e940eada959bdde927426e2531c9Paul Duffin 3310888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 3327dd252788645e940eada959bdde927426e2531c9Paul Duffin return array.length; 3337dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3357dd252788645e940eada959bdde927426e2531c9Paul Duffin 3367dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 3370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Implementation of Striped where up to 2^k stripes can be represented, using an 3380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * AtomicReferenceArray of size 2^k. To map a user key into a stripe, we take a k-bit slice of the 3390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * user key's (smeared) hashCode(). The stripes are lazily initialized and are weakly referenced. 3400888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 3410888a09821a98ac0680fad765217302858e70fa4Paul Duffin @VisibleForTesting static class SmallLazyStriped<L> extends PowerOfTwoStriped<L> { 3420888a09821a98ac0680fad765217302858e70fa4Paul Duffin final AtomicReferenceArray<ArrayReference<? extends L>> locks; 3430888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Supplier<L> supplier; 3440888a09821a98ac0680fad765217302858e70fa4Paul Duffin final int size; 3450888a09821a98ac0680fad765217302858e70fa4Paul Duffin final ReferenceQueue<L> queue = new ReferenceQueue<L>(); 3460888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3470888a09821a98ac0680fad765217302858e70fa4Paul Duffin SmallLazyStriped(int stripes, Supplier<L> supplier) { 3480888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(stripes); 3490888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.size = (mask == ALL_SET) ? Integer.MAX_VALUE : mask + 1; 3500888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.locks = new AtomicReferenceArray<ArrayReference<? extends L>>(size); 3510888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.supplier = supplier; 3520888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3530888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3540888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public L getAt(int index) { 3550888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (size != Integer.MAX_VALUE) { 3560888a09821a98ac0680fad765217302858e70fa4Paul Duffin Preconditions.checkElementIndex(index, size()); 3570888a09821a98ac0680fad765217302858e70fa4Paul Duffin } // else no check necessary, all index values are valid 3580888a09821a98ac0680fad765217302858e70fa4Paul Duffin ArrayReference<? extends L> existingRef = locks.get(index); 3590888a09821a98ac0680fad765217302858e70fa4Paul Duffin L existing = existingRef == null ? null : existingRef.get(); 3600888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (existing != null) { 3610888a09821a98ac0680fad765217302858e70fa4Paul Duffin return existing; 3620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3630888a09821a98ac0680fad765217302858e70fa4Paul Duffin L created = supplier.get(); 3640888a09821a98ac0680fad765217302858e70fa4Paul Duffin ArrayReference<L> newRef = new ArrayReference<L>(created, index, queue); 3650888a09821a98ac0680fad765217302858e70fa4Paul Duffin while (!locks.compareAndSet(index, existingRef, newRef)) { 3660888a09821a98ac0680fad765217302858e70fa4Paul Duffin // we raced, we need to re-read and try again 3670888a09821a98ac0680fad765217302858e70fa4Paul Duffin existingRef = locks.get(index); 3680888a09821a98ac0680fad765217302858e70fa4Paul Duffin existing = existingRef == null ? null : existingRef.get(); 3690888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (existing != null) { 3700888a09821a98ac0680fad765217302858e70fa4Paul Duffin return existing; 3710888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3720888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3730888a09821a98ac0680fad765217302858e70fa4Paul Duffin drainQueue(); 3740888a09821a98ac0680fad765217302858e70fa4Paul Duffin return created; 3750888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3760888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3770888a09821a98ac0680fad765217302858e70fa4Paul Duffin // N.B. Draining the queue is only necessary to ensure that we don't accumulate empty references 3780888a09821a98ac0680fad765217302858e70fa4Paul Duffin // in the array. We could skip this if we decide we don't care about holding on to Reference 3790888a09821a98ac0680fad765217302858e70fa4Paul Duffin // objects indefinitely. 3800888a09821a98ac0680fad765217302858e70fa4Paul Duffin private void drainQueue() { 3810888a09821a98ac0680fad765217302858e70fa4Paul Duffin Reference<? extends L> ref; 3820888a09821a98ac0680fad765217302858e70fa4Paul Duffin while ((ref = queue.poll()) != null) { 3830888a09821a98ac0680fad765217302858e70fa4Paul Duffin // We only ever register ArrayReferences with the queue so this is always safe. 3840888a09821a98ac0680fad765217302858e70fa4Paul Duffin ArrayReference<? extends L> arrayRef = (ArrayReference<? extends L>) ref; 3850888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Try to clear out the array slot, n.b. if we fail that is fine, in either case the 3860888a09821a98ac0680fad765217302858e70fa4Paul Duffin // arrayRef will be out of the array after this step. 3870888a09821a98ac0680fad765217302858e70fa4Paul Duffin locks.compareAndSet(arrayRef.index, arrayRef, null); 3880888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3890888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3900888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3910888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 3920888a09821a98ac0680fad765217302858e70fa4Paul Duffin return size; 3930888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 3940888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3950888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class ArrayReference<L> extends WeakReference<L> { 3960888a09821a98ac0680fad765217302858e70fa4Paul Duffin final int index; 3970888a09821a98ac0680fad765217302858e70fa4Paul Duffin 3980888a09821a98ac0680fad765217302858e70fa4Paul Duffin ArrayReference(L referent, int index, ReferenceQueue<L> queue) { 3990888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(referent, queue); 4000888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.index = index; 4010888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4020888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4030888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4040888a09821a98ac0680fad765217302858e70fa4Paul Duffin 4050888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 4060888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Implementation of Striped where up to 2^k stripes can be represented, using a ConcurrentMap 4077dd252788645e940eada959bdde927426e2531c9Paul Duffin * where the key domain is [0..2^k). To map a user key into a stripe, we take a k-bit slice of the 4087dd252788645e940eada959bdde927426e2531c9Paul Duffin * user key's (smeared) hashCode(). The stripes are lazily initialized and are weakly referenced. 4097dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 4100888a09821a98ac0680fad765217302858e70fa4Paul Duffin @VisibleForTesting static class LargeLazyStriped<L> extends PowerOfTwoStriped<L> { 4110888a09821a98ac0680fad765217302858e70fa4Paul Duffin final ConcurrentMap<Integer, L> locks; 4120888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Supplier<L> supplier; 4137dd252788645e940eada959bdde927426e2531c9Paul Duffin final int size; 4147dd252788645e940eada959bdde927426e2531c9Paul Duffin 4150888a09821a98ac0680fad765217302858e70fa4Paul Duffin LargeLazyStriped(int stripes, Supplier<L> supplier) { 4167dd252788645e940eada959bdde927426e2531c9Paul Duffin super(stripes); 4177dd252788645e940eada959bdde927426e2531c9Paul Duffin this.size = (mask == ALL_SET) ? Integer.MAX_VALUE : mask + 1; 4180888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.supplier = supplier; 4190888a09821a98ac0680fad765217302858e70fa4Paul Duffin this.locks = new MapMaker().weakValues().makeMap(); 4207dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4217dd252788645e940eada959bdde927426e2531c9Paul Duffin 4220888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public L getAt(int index) { 4230888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (size != Integer.MAX_VALUE) { 4240888a09821a98ac0680fad765217302858e70fa4Paul Duffin Preconditions.checkElementIndex(index, size()); 4250888a09821a98ac0680fad765217302858e70fa4Paul Duffin } // else no check necessary, all index values are valid 4260888a09821a98ac0680fad765217302858e70fa4Paul Duffin L existing = locks.get(index); 4270888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (existing != null) { 4280888a09821a98ac0680fad765217302858e70fa4Paul Duffin return existing; 4290888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 4300888a09821a98ac0680fad765217302858e70fa4Paul Duffin L created = supplier.get(); 4310888a09821a98ac0680fad765217302858e70fa4Paul Duffin existing = locks.putIfAbsent(index, created); 4323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return MoreObjects.firstNonNull(existing, created); 4337dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4347dd252788645e940eada959bdde927426e2531c9Paul Duffin 4350888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 4367dd252788645e940eada959bdde927426e2531c9Paul Duffin return size; 4377dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4387dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4397dd252788645e940eada959bdde927426e2531c9Paul Duffin 4407dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 4417dd252788645e940eada959bdde927426e2531c9Paul Duffin * A bit mask were all bits are set. 4427dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 4437dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final int ALL_SET = ~0; 4447dd252788645e940eada959bdde927426e2531c9Paul Duffin 4457dd252788645e940eada959bdde927426e2531c9Paul Duffin private static int ceilToPowerOfTwo(int x) { 4467dd252788645e940eada959bdde927426e2531c9Paul Duffin return 1 << IntMath.log2(x, RoundingMode.CEILING); 4477dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4487dd252788645e940eada959bdde927426e2531c9Paul Duffin 4497dd252788645e940eada959bdde927426e2531c9Paul Duffin /* 4507dd252788645e940eada959bdde927426e2531c9Paul Duffin * This method was written by Doug Lea with assistance from members of JCP 4517dd252788645e940eada959bdde927426e2531c9Paul Duffin * JSR-166 Expert Group and released to the public domain, as explained at 4527dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://creativecommons.org/licenses/publicdomain 4537dd252788645e940eada959bdde927426e2531c9Paul Duffin * 4547dd252788645e940eada959bdde927426e2531c9Paul Duffin * As of 2010/06/11, this method is identical to the (package private) hash 4557dd252788645e940eada959bdde927426e2531c9Paul Duffin * method in OpenJDK 7's java.util.HashMap class. 4567dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 4577dd252788645e940eada959bdde927426e2531c9Paul Duffin // Copied from java/com/google/common/collect/Hashing.java 4587dd252788645e940eada959bdde927426e2531c9Paul Duffin private static int smear(int hashCode) { 4597dd252788645e940eada959bdde927426e2531c9Paul Duffin hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12); 4607dd252788645e940eada959bdde927426e2531c9Paul Duffin return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4); 4617dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4627dd252788645e940eada959bdde927426e2531c9Paul Duffin 4637dd252788645e940eada959bdde927426e2531c9Paul Duffin private static class PaddedLock extends ReentrantLock { 4647dd252788645e940eada959bdde927426e2531c9Paul Duffin /* 4657dd252788645e940eada959bdde927426e2531c9Paul Duffin * Padding from 40 into 64 bytes, same size as cache line. Might be beneficial to add 4667dd252788645e940eada959bdde927426e2531c9Paul Duffin * a fourth long here, to minimize chance of interference between consecutive locks, 4677dd252788645e940eada959bdde927426e2531c9Paul Duffin * but I couldn't observe any benefit from that. 4687dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 4697dd252788645e940eada959bdde927426e2531c9Paul Duffin @SuppressWarnings("unused") 4707dd252788645e940eada959bdde927426e2531c9Paul Duffin long q1, q2, q3; 4717dd252788645e940eada959bdde927426e2531c9Paul Duffin 4727dd252788645e940eada959bdde927426e2531c9Paul Duffin PaddedLock() { 4737dd252788645e940eada959bdde927426e2531c9Paul Duffin super(false); 4747dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4757dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4767dd252788645e940eada959bdde927426e2531c9Paul Duffin 4777dd252788645e940eada959bdde927426e2531c9Paul Duffin private static class PaddedSemaphore extends Semaphore { 4787dd252788645e940eada959bdde927426e2531c9Paul Duffin // See PaddedReentrantLock comment 4797dd252788645e940eada959bdde927426e2531c9Paul Duffin @SuppressWarnings("unused") 4807dd252788645e940eada959bdde927426e2531c9Paul Duffin long q1, q2, q3; 4817dd252788645e940eada959bdde927426e2531c9Paul Duffin 4827dd252788645e940eada959bdde927426e2531c9Paul Duffin PaddedSemaphore(int permits) { 4837dd252788645e940eada959bdde927426e2531c9Paul Duffin super(permits, false); 4847dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4857dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4867dd252788645e940eada959bdde927426e2531c9Paul Duffin} 487