1 /* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.util.concurrent; 18 19 import static com.google.common.collect.Iterables.concat; 20 21 import com.google.common.base.Functions; 22 import com.google.common.base.Supplier; 23 import com.google.common.collect.ImmutableList; 24 import com.google.common.collect.Lists; 25 import com.google.common.collect.Maps; 26 import com.google.common.collect.Ordering; 27 import com.google.common.collect.Sets; 28 import com.google.common.testing.GcFinalization; 29 import com.google.common.testing.NullPointerTester; 30 import java.lang.ref.WeakReference; 31 import java.util.List; 32 import java.util.Map; 33 import java.util.Set; 34 import java.util.concurrent.Semaphore; 35 import java.util.concurrent.locks.Lock; 36 import java.util.concurrent.locks.ReadWriteLock; 37 import java.util.concurrent.locks.ReentrantLock; 38 import java.util.concurrent.locks.ReentrantReadWriteLock; 39 import junit.framework.TestCase; 40 41 /** 42 * Tests for Striped. 43 * 44 * @author Dimitris Andreou 45 */ 46 public class StripedTest extends TestCase { strongImplementations()47 private static List<Striped<?>> strongImplementations() { 48 return ImmutableList.of( 49 Striped.readWriteLock(100), 50 Striped.readWriteLock(256), 51 Striped.lock(100), 52 Striped.lock(256), 53 Striped.custom( 54 100, 55 new Supplier<Lock>() { 56 @Override 57 public Lock get() { 58 return new ReentrantLock(true); 59 } 60 }), 61 Striped.custom( 62 256, 63 new Supplier<Lock>() { 64 @Override 65 public Lock get() { 66 return new ReentrantLock(true); 67 } 68 }), 69 Striped.semaphore(100, 1), 70 Striped.semaphore(256, 1)); 71 } 72 73 private static final Supplier<ReadWriteLock> READ_WRITE_LOCK_SUPPLIER = 74 new Supplier<ReadWriteLock>() { 75 @Override 76 public ReadWriteLock get() { 77 return new ReentrantReadWriteLock(); 78 } 79 }; 80 81 private static final Supplier<Lock> LOCK_SUPPLER = 82 new Supplier<Lock>() { 83 @Override 84 public Lock get() { 85 return new ReentrantLock(); 86 } 87 }; 88 89 private static final Supplier<Semaphore> SEMAPHORE_SUPPLER = 90 new Supplier<Semaphore>() { 91 @Override 92 public Semaphore get() { 93 return new Semaphore(1, false); 94 } 95 }; 96 97 private static List<Striped<?>> weakImplementations() { 98 return ImmutableList.<Striped<?>>builder() 99 .add(new Striped.SmallLazyStriped<ReadWriteLock>(50, READ_WRITE_LOCK_SUPPLIER)) 100 .add(new Striped.SmallLazyStriped<ReadWriteLock>(64, READ_WRITE_LOCK_SUPPLIER)) 101 .add(new Striped.LargeLazyStriped<ReadWriteLock>(50, READ_WRITE_LOCK_SUPPLIER)) 102 .add(new Striped.LargeLazyStriped<ReadWriteLock>(64, READ_WRITE_LOCK_SUPPLIER)) 103 .add(new Striped.SmallLazyStriped<Lock>(50, LOCK_SUPPLER)) 104 .add(new Striped.SmallLazyStriped<Lock>(64, LOCK_SUPPLER)) 105 .add(new Striped.LargeLazyStriped<Lock>(50, LOCK_SUPPLER)) 106 .add(new Striped.LargeLazyStriped<Lock>(64, LOCK_SUPPLER)) 107 .add(new Striped.SmallLazyStriped<Semaphore>(50, SEMAPHORE_SUPPLER)) 108 .add(new Striped.SmallLazyStriped<Semaphore>(64, SEMAPHORE_SUPPLER)) 109 .add(new Striped.LargeLazyStriped<Semaphore>(50, SEMAPHORE_SUPPLER)) 110 .add(new Striped.LargeLazyStriped<Semaphore>(64, SEMAPHORE_SUPPLER)) 111 .build(); 112 } 113 114 private static Iterable<Striped<?>> allImplementations() { 115 return concat(strongImplementations(), weakImplementations()); 116 } 117 118 public void testNull() throws Exception { 119 for (Striped<?> striped : allImplementations()) { 120 new NullPointerTester().testAllPublicInstanceMethods(striped); 121 } 122 } 123 124 public void testSizes() { 125 // not bothering testing all variations, since we know they share implementations 126 assertTrue(Striped.lock(100).size() >= 100); 127 assertTrue(Striped.lock(256).size() == 256); 128 assertTrue(Striped.lazyWeakLock(100).size() >= 100); 129 assertTrue(Striped.lazyWeakLock(256).size() == 256); 130 } 131 132 public void testWeakImplementations() { 133 for (Striped<?> striped : weakImplementations()) { 134 WeakReference<Object> weakRef = new WeakReference<>(striped.get(new Object())); 135 GcFinalization.awaitClear(weakRef); 136 } 137 } 138 139 public void testWeakReadWrite() { 140 Striped<ReadWriteLock> striped = Striped.lazyWeakReadWriteLock(1000); 141 Object key = new Object(); 142 Lock readLock = striped.get(key).readLock(); 143 WeakReference<Object> garbage = new WeakReference<>(new Object()); 144 GcFinalization.awaitClear(garbage); 145 Lock writeLock = striped.get(key).writeLock(); 146 readLock.lock(); 147 assertFalse(writeLock.tryLock()); 148 readLock.unlock(); 149 } 150 151 public void testStrongImplementations() { 152 for (Striped<?> striped : strongImplementations()) { 153 WeakReference<Object> weakRef = new WeakReference<>(striped.get(new Object())); 154 WeakReference<Object> garbage = new WeakReference<>(new Object()); 155 GcFinalization.awaitClear(garbage); 156 assertNotNull(weakRef.get()); 157 } 158 } 159 160 public void testMaximalWeakStripedLock() { 161 Striped<Lock> stripedLock = Striped.lazyWeakLock(Integer.MAX_VALUE); 162 for (int i = 0; i < 10000; i++) { 163 stripedLock.get(new Object()).lock(); 164 // nothing special (e.g. an exception) happens 165 } 166 } 167 168 public void testBulkGetReturnsSorted() { 169 for (Striped<?> striped : allImplementations()) { 170 Map<Object, Integer> indexByLock = Maps.newHashMap(); 171 for (int i = 0; i < striped.size(); i++) { 172 indexByLock.put(striped.getAt(i), i); 173 } 174 175 // ensure that bulkGet returns locks in monotonically increasing order 176 for (int objectsNum = 1; objectsNum <= striped.size() * 2; objectsNum++) { 177 Set<Object> objects = Sets.newHashSetWithExpectedSize(objectsNum); 178 for (int i = 0; i < objectsNum; i++) { 179 objects.add(new Object()); 180 } 181 182 Iterable<?> locks = striped.bulkGet(objects); 183 assertTrue(Ordering.natural().onResultOf(Functions.forMap(indexByLock)).isOrdered(locks)); 184 185 // check idempotency 186 Iterable<?> locks2 = striped.bulkGet(objects); 187 assertEquals(Lists.newArrayList(locks), Lists.newArrayList(locks2)); 188 } 189 } 190 } 191 192 /** Checks idempotency, and that we observe the promised number of stripes. */ 193 public void testBasicInvariants() { 194 for (Striped<?> striped : allImplementations()) { 195 assertBasicInvariants(striped); 196 } 197 } 198 199 private static void assertBasicInvariants(Striped<?> striped) { 200 Set<Object> observed = Sets.newIdentityHashSet(); // for the sake of weakly referenced locks. 201 // this gets the stripes with #getAt(index) 202 for (int i = 0; i < striped.size(); i++) { 203 Object object = striped.getAt(i); 204 assertNotNull(object); 205 assertSame(object, striped.getAt(i)); // idempotent 206 observed.add(object); 207 } 208 assertTrue("All stripes observed", observed.size() == striped.size()); 209 210 // this uses #get(key), makes sure an already observed stripe is returned 211 for (int i = 0; i < striped.size() * 100; i++) { 212 assertTrue(observed.contains(striped.get(new Object()))); 213 } 214 215 try { 216 striped.getAt(-1); 217 fail(); 218 } catch (RuntimeException expected) { 219 } 220 221 try { 222 striped.getAt(striped.size()); 223 fail(); 224 } catch (RuntimeException expected) { 225 } 226 } 227 228 public void testMaxSize() { 229 for (Striped<?> striped : 230 ImmutableList.of( 231 Striped.lazyWeakLock(Integer.MAX_VALUE), 232 Striped.lazyWeakSemaphore(Integer.MAX_VALUE, Integer.MAX_VALUE), 233 Striped.lazyWeakReadWriteLock(Integer.MAX_VALUE))) { 234 for (int i = 0; i < 3; i++) { 235 // doesn't throw exception 236 Object unused = striped.getAt(Integer.MAX_VALUE - i); 237 } 238 } 239 } 240 } 241