1/* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the License 10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 11 * or implied. See the License for the specific language governing permissions and limitations under 12 * the License. 13 */ 14 15package com.google.common.cache; 16 17import static junit.framework.Assert.assertEquals; 18import static junit.framework.Assert.assertFalse; 19import static junit.framework.Assert.assertNotNull; 20import static junit.framework.Assert.assertNotSame; 21import static junit.framework.Assert.assertNull; 22import static junit.framework.Assert.assertSame; 23import static junit.framework.Assert.assertTrue; 24 25import com.google.common.base.Preconditions; 26import com.google.common.cache.LocalCache.LocalLoadingCache; 27import com.google.common.cache.LocalCache.ReferenceEntry; 28import com.google.common.cache.LocalCache.Segment; 29import com.google.common.cache.LocalCache.ValueReference; 30import com.google.common.collect.ImmutableList; 31import com.google.common.collect.ImmutableMap; 32import com.google.common.collect.ImmutableSet; 33import com.google.common.collect.Maps; 34import com.google.common.collect.Sets; 35import com.google.common.testing.EqualsTester; 36import com.google.common.testing.FakeTicker; 37 38import java.lang.ref.Reference; 39import java.util.Collection; 40import java.util.List; 41import java.util.Map; 42import java.util.Map.Entry; 43import java.util.Set; 44import java.util.concurrent.ConcurrentMap; 45import java.util.concurrent.TimeUnit; 46import java.util.concurrent.atomic.AtomicReferenceArray; 47 48import javax.annotation.Nullable; 49 50/** 51 * A collection of utilities for {@link Cache} testing. 52 * 53 * @author mike nonemacher 54 */ 55class CacheTesting { 56 57 /** 58 * Poke into the Cache internals to simulate garbage collection of the value associated with the 59 * given key. This assumes that the associated entry is a WeakValueReference or a 60 * SoftValueReference (and not a LoadingValueReference), and throws an IllegalStateException 61 * if that assumption does not hold. 62 */ 63 @SuppressWarnings("unchecked") // the instanceof check and the cast generate this warning 64 static <K, V> void simulateValueReclamation(Cache<K, V> cache, K key) { 65 ReferenceEntry<K, V> entry = getReferenceEntry(cache, key); 66 if (entry != null) { 67 ValueReference<K, V> valueRef = entry.getValueReference(); 68 // fail on strong/computing refs 69 Preconditions.checkState(valueRef instanceof Reference); 70 Reference<V> ref = (Reference<V>) valueRef; 71 if (ref != null) { 72 ref.clear(); 73 } 74 } 75 } 76 77 /** 78 * Poke into the Cache internals to simulate garbage collection of the given key. This assumes 79 * that the given entry is a weak or soft reference, and throws an IllegalStateException if that 80 * assumption does not hold. 81 */ 82 @SuppressWarnings("unchecked") // the instanceof check and the cast generate this warning 83 static <K, V> void simulateKeyReclamation(Cache<K, V> cache, K key) { 84 ReferenceEntry<K, V> entry = getReferenceEntry(cache, key); 85 86 Preconditions.checkState(entry instanceof Reference); 87 Reference<?> ref = (Reference<?>) entry; 88 if (ref != null) { 89 ref.clear(); 90 } 91 } 92 93 static <K, V> ReferenceEntry<K, V> getReferenceEntry(Cache<K, V> cache, K key) { 94 LocalCache<K, V> map = toLocalCache(cache); 95 return map.getEntry(key); 96 } 97 98 /** 99 * Forces the segment containing the given {@code key} to expand (see 100 * {@link Segment#expand()}. 101 */ 102 static <K, V> void forceExpandSegment(Cache<K, V> cache, K key) { 103 LocalCache<K, V> map = toLocalCache(cache); 104 int hash = map.hash(key); 105 Segment<K, V> segment = map.segmentFor(hash); 106 segment.expand(); 107 } 108 109 /** 110 * Gets the {@link LocalCache} used by the given {@link Cache}, if any, or throws an 111 * IllegalArgumentException if this is a Cache type that doesn't have a LocalCache. 112 */ 113 static <K, V> LocalCache<K, V> toLocalCache(Cache<K, V> cache) { 114 if (cache instanceof LocalLoadingCache) { 115 return ((LocalLoadingCache<K, V>) cache).localCache; 116 } 117 throw new IllegalArgumentException("Cache of type " + cache.getClass() 118 + " doesn't have a LocalCache."); 119 } 120 121 /** 122 * Determines whether the given cache can be converted to a LocalCache by 123 * {@link #toLocalCache} without throwing an exception. 124 */ 125 static boolean hasLocalCache(Cache<?, ?> cache) { 126 return (cache instanceof LocalLoadingCache); 127 } 128 129 static void drainRecencyQueues(Cache<?, ?> cache) { 130 if (hasLocalCache(cache)) { 131 LocalCache<?, ?> map = toLocalCache(cache); 132 for (Segment segment : map.segments) { 133 drainRecencyQueue(segment); 134 } 135 } 136 } 137 138 static void drainRecencyQueue(Segment<?, ?> segment) { 139 segment.lock(); 140 try { 141 segment.cleanUp(); 142 } finally { 143 segment.unlock(); 144 } 145 } 146 147 static void drainReferenceQueues(Cache<?, ?> cache) { 148 if (hasLocalCache(cache)) { 149 drainReferenceQueues(toLocalCache(cache)); 150 } 151 } 152 153 static void drainReferenceQueues(LocalCache<?, ?> cchm) { 154 for (LocalCache.Segment segment : cchm.segments) { 155 drainReferenceQueue(segment); 156 } 157 } 158 159 static void drainReferenceQueue(LocalCache.Segment<?, ?> segment) { 160 segment.lock(); 161 try { 162 segment.drainReferenceQueues(); 163 } finally { 164 segment.unlock(); 165 } 166 } 167 168 static int getTotalSegmentSize(Cache<?, ?> cache) { 169 LocalCache<?, ?> map = toLocalCache(cache); 170 int totalSize = 0; 171 for (Segment<?, ?> segment : map.segments) { 172 totalSize += segment.maxSegmentWeight; 173 } 174 return totalSize; 175 } 176 177 /** 178 * Peeks into the cache's internals to check its internal consistency. Verifies that each 179 * segment's count matches its #elements (after cleanup), each segment is unlocked, each entry 180 * contains a non-null key and value, and the eviction and expiration queues are consistent 181 * (see {@link #checkEviction}, {@link #checkExpiration}). 182 */ 183 static void checkValidState(Cache<?, ?> cache) { 184 if (hasLocalCache(cache)) { 185 checkValidState(toLocalCache(cache)); 186 } 187 } 188 189 static void checkValidState(LocalCache<?, ?> cchm) { 190 for (Segment<?, ?> segment : cchm.segments) { 191 segment.cleanUp(); 192 assertFalse(segment.isLocked()); 193 Map<?, ?> table = segmentTable(segment); 194 // cleanup and then check count after we have a strong reference to all entries 195 segment.cleanUp(); 196 // under high memory pressure keys/values may be nulled out but not yet enqueued 197 assertTrue(table.size() <= segment.count); 198 for (Entry entry : table.entrySet()) { 199 assertNotNull(entry.getKey()); 200 assertNotNull(entry.getValue()); 201 assertSame(entry.getValue(), cchm.get(entry.getKey())); 202 } 203 } 204 checkEviction(cchm); 205 checkExpiration(cchm); 206 } 207 208 /** 209 * Peeks into the cache's internals to verify that its expiration queue is consistent. Verifies 210 * that the next/prev links in the expiration queue are correct, and that the queue is ordered 211 * by expiration time. 212 */ 213 static void checkExpiration(Cache<?, ?> cache) { 214 if (hasLocalCache(cache)) { 215 checkExpiration(toLocalCache(cache)); 216 } 217 } 218 219 static void checkExpiration(LocalCache<?, ?> cchm) { 220 for (Segment<?, ?> segment : cchm.segments) { 221 if (cchm.usesWriteQueue()) { 222 Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet(); 223 224 ReferenceEntry<?, ?> prev = null; 225 for (ReferenceEntry<?, ?> current : segment.writeQueue) { 226 assertTrue(entries.add(current)); 227 if (prev != null) { 228 assertSame(prev, current.getPreviousInWriteQueue()); 229 assertSame(prev.getNextInWriteQueue(), current); 230 assertTrue(prev.getWriteTime() <= current.getWriteTime()); 231 } 232 Object key = current.getKey(); 233 if (key != null) { 234 assertSame(current, segment.getEntry(key, current.getHash())); 235 } 236 prev = current; 237 } 238 assertEquals(segment.count, entries.size()); 239 } else { 240 assertTrue(segment.writeQueue.isEmpty()); 241 } 242 243 if (cchm.usesAccessQueue()) { 244 Set<ReferenceEntry<?, ?>> entries = Sets.newIdentityHashSet(); 245 246 ReferenceEntry<?, ?> prev = null; 247 for (ReferenceEntry<?, ?> current : segment.accessQueue) { 248 assertTrue(entries.add(current)); 249 if (prev != null) { 250 assertSame(prev, current.getPreviousInAccessQueue()); 251 assertSame(prev.getNextInAccessQueue(), current); 252 // read accesses may be slightly misordered 253 assertTrue(prev.getAccessTime() <= current.getAccessTime() 254 || prev.getAccessTime() - current.getAccessTime() < 1000); 255 } 256 Object key = current.getKey(); 257 if (key != null) { 258 assertSame(current, segment.getEntry(key, current.getHash())); 259 } 260 prev = current; 261 } 262 assertEquals(segment.count, entries.size()); 263 } else { 264 assertTrue(segment.accessQueue.isEmpty()); 265 } 266 } 267 } 268 269 /** 270 * Peeks into the cache's internals to verify that its eviction queue is consistent. Verifies 271 * that the prev/next links are correct, and that all items in each segment are also in that 272 * segment's eviction (recency) queue. 273 */ 274 static void checkEviction(Cache<?, ?> cache) { 275 if (hasLocalCache(cache)) { 276 checkEviction(toLocalCache(cache)); 277 } 278 } 279 280 static void checkEviction(LocalCache<?, ?> map) { 281 if (map.evictsBySize()) { 282 for (Segment<?, ?> segment : map.segments) { 283 drainRecencyQueue(segment); 284 assertEquals(0, segment.recencyQueue.size()); 285 assertEquals(0, segment.readCount.get()); 286 287 ReferenceEntry<?, ?> prev = null; 288 for (ReferenceEntry<?, ?> current : segment.accessQueue) { 289 if (prev != null) { 290 assertSame(prev, current.getPreviousInAccessQueue()); 291 assertSame(prev.getNextInAccessQueue(), current); 292 } 293 Object key = current.getKey(); 294 if (key != null) { 295 assertSame(current, segment.getEntry(key, current.getHash())); 296 } 297 prev = current; 298 } 299 } 300 } else { 301 for (Segment segment : map.segments) { 302 assertEquals(0, segment.recencyQueue.size()); 303 } 304 } 305 } 306 307 static int segmentSize(Segment<?, ?> segment) { 308 Map<?, ?> map = segmentTable(segment); 309 return map.size(); 310 } 311 312 static <K, V> Map<K, V> segmentTable(Segment<K, V> segment) { 313 AtomicReferenceArray<? extends ReferenceEntry<K, V>> table = segment.table; 314 Map<K, V> map = Maps.newLinkedHashMap(); 315 for (int i = 0; i < table.length(); i++) { 316 for (ReferenceEntry<K, V> entry = table.get(i); entry != null; entry = entry.getNext()) { 317 K key = entry.getKey(); 318 V value = entry.getValueReference().get(); 319 if (key != null && value != null) { 320 assertNull(map.put(key, value)); 321 } 322 } 323 } 324 return map; 325 } 326 327 static int writeQueueSize(Cache<?, ?> cache) { 328 LocalCache<?, ?> cchm = toLocalCache(cache); 329 330 int size = 0; 331 for (Segment<?, ?> segment : cchm.segments) { 332 size += writeQueueSize(segment); 333 } 334 return size; 335 } 336 337 static int writeQueueSize(Segment<?, ?> segment) { 338 return segment.writeQueue.size(); 339 } 340 341 static int accessQueueSize(Cache<?, ?> cache) { 342 LocalCache<?, ?> cchm = toLocalCache(cache); 343 int size = 0; 344 for (Segment<?, ?> segment : cchm.segments) { 345 size += accessQueueSize(segment); 346 } 347 return size; 348 } 349 350 static int accessQueueSize(Segment<?, ?> segment) { 351 return segment.accessQueue.size(); 352 } 353 354 static int expirationQueueSize(Cache<?, ?> cache) { 355 return Math.max(accessQueueSize(cache), writeQueueSize(cache)); 356 } 357 358 static void processPendingNotifications(Cache<?, ?> cache) { 359 if (hasLocalCache(cache)) { 360 LocalCache<?, ?> cchm = toLocalCache(cache); 361 cchm.processPendingNotifications(); 362 } 363 } 364 365 interface Receiver<T> { 366 void accept(@Nullable T object); 367 } 368 369 /** 370 * Assuming the given cache has maximum size {@code maxSize}, this method populates the cache (by 371 * getting a bunch of different keys), then makes sure all the items in the cache are also in the 372 * eviction queue. It will invoke the given {@code operation} on the first element in the 373 * eviction queue, and then reverify that all items in the cache are in the eviction queue, and 374 * verify that the head of the eviction queue has changed as a result of the operation. 375 */ 376 static void checkRecency(LoadingCache<Integer, Integer> cache, int maxSize, 377 Receiver<ReferenceEntry<Integer, Integer>> operation) { 378 379 if (hasLocalCache(cache)) { 380 warmUp(cache, 0, 2 * maxSize); 381 382 LocalCache<Integer, Integer> cchm = toLocalCache(cache); 383 Segment<?, ?> segment = cchm.segments[0]; 384 drainRecencyQueue(segment); 385 assertEquals(maxSize, accessQueueSize(cache)); 386 assertEquals(maxSize, cache.size()); 387 388 ReferenceEntry<?, ?> originalHead = segment.accessQueue.peek(); 389 @SuppressWarnings("unchecked") 390 ReferenceEntry<Integer, Integer> entry = (ReferenceEntry) originalHead; 391 operation.accept(entry); 392 drainRecencyQueue(segment); 393 394 assertNotSame(originalHead, segment.accessQueue.peek()); 395 assertEquals(cache.size(), accessQueueSize(cache)); 396 } 397 } 398 399 /** 400 * Warms the given cache by getting all values in {@code [start, end)}, in order. 401 */ 402 static void warmUp(LoadingCache<Integer, Integer> map, int start, int end) { 403 for (int i = start; i < end; i++) { 404 map.getUnchecked(i); 405 } 406 } 407 408 static void expireEntries(Cache<?, ?> cache, long expiringTime, FakeTicker ticker) { 409 expireEntries(toLocalCache(cache), expiringTime, ticker); 410 } 411 412 static void expireEntries( 413 LocalCache<?, ?> cchm, long expiringTime, FakeTicker ticker) { 414 415 for (Segment<?, ?> segment : cchm.segments) { 416 drainRecencyQueue(segment); 417 } 418 419 ticker.advance(2 * expiringTime, TimeUnit.MILLISECONDS); 420 421 long now = ticker.read(); 422 for (Segment<?, ?> segment : cchm.segments) { 423 expireEntries(segment, now); 424 assertEquals("Expiration queue must be empty by now", 0, writeQueueSize(segment)); 425 assertEquals("Expiration queue must be empty by now", 0, accessQueueSize(segment)); 426 assertEquals("Segments must be empty by now", 0, segmentSize(segment)); 427 } 428 cchm.processPendingNotifications(); 429 } 430 431 static void expireEntries(Segment<?, ?> segment, long now) { 432 segment.lock(); 433 try { 434 segment.expireEntries(now); 435 segment.cleanUp(); 436 } finally { 437 segment.unlock(); 438 } 439 } 440 static void checkEmpty(Cache<?, ?> cache) { 441 assertEquals(0, cache.size()); 442 assertFalse(cache.asMap().containsKey(null)); 443 assertFalse(cache.asMap().containsKey(6)); 444 assertFalse(cache.asMap().containsValue(null)); 445 assertFalse(cache.asMap().containsValue(6)); 446 checkEmpty(cache.asMap()); 447 } 448 449 static void checkEmpty(ConcurrentMap<?, ?> map) { 450 checkEmpty(map.keySet()); 451 checkEmpty(map.values()); 452 checkEmpty(map.entrySet()); 453 assertEquals(ImmutableMap.of(), map); 454 assertEquals(ImmutableMap.of().hashCode(), map.hashCode()); 455 assertEquals(ImmutableMap.of().toString(), map.toString()); 456 457 if (map instanceof LocalCache) { 458 LocalCache<?, ?> cchm = (LocalCache<?, ?>) map; 459 460 checkValidState(cchm); 461 assertTrue(cchm.isEmpty()); 462 assertEquals(0, cchm.size()); 463 for (LocalCache.Segment segment : cchm.segments) { 464 assertEquals(0, segment.count); 465 assertEquals(0, segmentSize(segment)); 466 assertTrue(segment.writeQueue.isEmpty()); 467 assertTrue(segment.accessQueue.isEmpty()); 468 } 469 } 470 } 471 472 static void checkEmpty(Collection<?> collection) { 473 assertTrue(collection.isEmpty()); 474 assertEquals(0, collection.size()); 475 assertFalse(collection.iterator().hasNext()); 476 assertEquals(0, collection.toArray().length); 477 assertEquals(0, collection.toArray(new Object[0]).length); 478 if (collection instanceof Set) { 479 new EqualsTester() 480 .addEqualityGroup(ImmutableSet.of(), collection) 481 .addEqualityGroup(ImmutableSet.of("")) 482 .testEquals(); 483 } else if (collection instanceof List) { 484 new EqualsTester() 485 .addEqualityGroup(ImmutableList.of(), collection) 486 .addEqualityGroup(ImmutableList.of("")) 487 .testEquals(); 488 } 489 } 490} 491