1 /* 2 * Copyright (C) 2009 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.cache; 18 19 import static com.google.common.cache.TestingCacheLoaders.constantLoader; 20 import static com.google.common.cache.TestingCacheLoaders.identityLoader; 21 import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener; 22 import static com.google.common.cache.TestingRemovalListeners.nullRemovalListener; 23 import static com.google.common.cache.TestingRemovalListeners.queuingRemovalListener; 24 import static com.google.common.cache.TestingWeighers.constantWeigher; 25 import static java.util.concurrent.TimeUnit.NANOSECONDS; 26 import static java.util.concurrent.TimeUnit.SECONDS; 27 28 import com.google.common.annotations.GwtCompatible; 29 import com.google.common.annotations.GwtIncompatible; 30 import com.google.common.base.Ticker; 31 import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener; 32 import com.google.common.cache.TestingRemovalListeners.QueuingRemovalListener; 33 import com.google.common.collect.Maps; 34 import com.google.common.collect.Sets; 35 import com.google.common.testing.NullPointerTester; 36 37 import junit.framework.TestCase; 38 39 import java.util.Map; 40 import java.util.Random; 41 import java.util.Set; 42 import java.util.concurrent.CountDownLatch; 43 import java.util.concurrent.ExecutorService; 44 import java.util.concurrent.Executors; 45 import java.util.concurrent.TimeUnit; 46 import java.util.concurrent.atomic.AtomicBoolean; 47 import java.util.concurrent.atomic.AtomicInteger; 48 49 /** 50 * Unit tests for CacheBuilder. 51 */ 52 @GwtCompatible(emulated = true) 53 public class CacheBuilderTest extends TestCase { 54 55 @GwtIncompatible("removalListener") 56 public void testNewBuilder() { 57 CacheLoader<Object, Integer> loader = constantLoader(1); 58 59 LoadingCache<String, Integer> cache = CacheBuilder.newBuilder() 60 .removalListener(countingRemovalListener()) 61 .build(loader); 62 63 assertEquals(Integer.valueOf(1), cache.getUnchecked("one")); 64 assertEquals(1, cache.size()); 65 } 66 67 public void testInitialCapacity_negative() { 68 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 69 try { 70 builder.initialCapacity(-1); 71 fail(); 72 } catch (IllegalArgumentException expected) {} 73 } 74 75 public void testInitialCapacity_setTwice() { 76 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().initialCapacity(16); 77 try { 78 // even to the same value is not allowed 79 builder.initialCapacity(16); 80 fail(); 81 } catch (IllegalStateException expected) {} 82 } 83 84 @GwtIncompatible("CacheTesting") 85 public void testInitialCapacity_small() { 86 LoadingCache<?, ?> cache = CacheBuilder.newBuilder() 87 .initialCapacity(5) 88 .build(identityLoader()); 89 LocalCache<?, ?> map = CacheTesting.toLocalCache(cache); 90 91 assertEquals(4, map.segments.length); 92 assertEquals(2, map.segments[0].table.length()); 93 assertEquals(2, map.segments[1].table.length()); 94 assertEquals(2, map.segments[2].table.length()); 95 assertEquals(2, map.segments[3].table.length()); 96 } 97 98 @GwtIncompatible("CacheTesting") 99 public void testInitialCapacity_smallest() { 100 LoadingCache<?, ?> cache = CacheBuilder.newBuilder() 101 .initialCapacity(0) 102 .build(identityLoader()); 103 LocalCache<?, ?> map = CacheTesting.toLocalCache(cache); 104 105 assertEquals(4, map.segments.length); 106 // 1 is as low as it goes, not 0. it feels dirty to know this/test this. 107 assertEquals(1, map.segments[0].table.length()); 108 assertEquals(1, map.segments[1].table.length()); 109 assertEquals(1, map.segments[2].table.length()); 110 assertEquals(1, map.segments[3].table.length()); 111 } 112 113 public void testInitialCapacity_large() { 114 CacheBuilder.newBuilder().initialCapacity(Integer.MAX_VALUE); 115 // that the builder didn't blow up is enough; 116 // don't actually create this monster! 117 } 118 119 public void testConcurrencyLevel_zero() { 120 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 121 try { 122 builder.concurrencyLevel(0); 123 fail(); 124 } catch (IllegalArgumentException expected) {} 125 } 126 127 public void testConcurrencyLevel_setTwice() { 128 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().concurrencyLevel(16); 129 try { 130 // even to the same value is not allowed 131 builder.concurrencyLevel(16); 132 fail(); 133 } catch (IllegalStateException expected) {} 134 } 135 136 @GwtIncompatible("CacheTesting") 137 public void testConcurrencyLevel_small() { 138 LoadingCache<?, ?> cache = CacheBuilder.newBuilder() 139 .concurrencyLevel(1) 140 .build(identityLoader()); 141 LocalCache<?, ?> map = CacheTesting.toLocalCache(cache); 142 assertEquals(1, map.segments.length); 143 } 144 145 public void testConcurrencyLevel_large() { 146 CacheBuilder.newBuilder().concurrencyLevel(Integer.MAX_VALUE); 147 // don't actually build this beast 148 } 149 150 public void testMaximumSize_negative() { 151 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 152 try { 153 builder.maximumSize(-1); 154 fail(); 155 } catch (IllegalArgumentException expected) {} 156 } 157 158 public void testMaximumSize_setTwice() { 159 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().maximumSize(16); 160 try { 161 // even to the same value is not allowed 162 builder.maximumSize(16); 163 fail(); 164 } catch (IllegalStateException expected) {} 165 } 166 167 @GwtIncompatible("maximumWeight") 168 public void testMaximumSize_andWeight() { 169 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().maximumSize(16); 170 try { 171 builder.maximumWeight(16); 172 fail(); 173 } catch (IllegalStateException expected) {} 174 } 175 176 @GwtIncompatible("maximumWeight") 177 public void testMaximumWeight_negative() { 178 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 179 try { 180 builder.maximumWeight(-1); 181 fail(); 182 } catch (IllegalArgumentException expected) {} 183 } 184 185 @GwtIncompatible("maximumWeight") 186 public void testMaximumWeight_setTwice() { 187 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>().maximumWeight(16); 188 try { 189 // even to the same value is not allowed 190 builder.maximumWeight(16); 191 fail(); 192 } catch (IllegalStateException expected) {} 193 try { 194 builder.maximumSize(16); 195 fail(); 196 } catch (IllegalStateException expected) {} 197 } 198 199 @GwtIncompatible("maximumWeight") 200 public void testMaximumWeight_withoutWeigher() { 201 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>() 202 .maximumWeight(1); 203 try { 204 builder.build(identityLoader()); 205 fail(); 206 } catch (IllegalStateException expected) {} 207 } 208 209 @GwtIncompatible("weigher") 210 public void testWeigher_withoutMaximumWeight() { 211 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>() 212 .weigher(constantWeigher(42)); 213 try { 214 builder.build(identityLoader()); 215 fail(); 216 } catch (IllegalStateException expected) {} 217 } 218 219 @GwtIncompatible("weigher") 220 public void testWeigher_withMaximumSize() { 221 try { 222 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>() 223 .weigher(constantWeigher(42)) 224 .maximumSize(1); 225 fail(); 226 } catch (IllegalStateException expected) {} 227 try { 228 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>() 229 .maximumSize(1) 230 .weigher(constantWeigher(42)); 231 fail(); 232 } catch (IllegalStateException expected) {} 233 } 234 235 @GwtIncompatible("weakKeys") 236 public void testKeyStrengthSetTwice() { 237 CacheBuilder<Object, Object> builder1 = new CacheBuilder<Object, Object>().weakKeys(); 238 try { 239 builder1.weakKeys(); 240 fail(); 241 } catch (IllegalStateException expected) {} 242 } 243 244 @GwtIncompatible("weakValues") 245 public void testValueStrengthSetTwice() { 246 CacheBuilder<Object, Object> builder1 = new CacheBuilder<Object, Object>().weakValues(); 247 try { 248 builder1.weakValues(); 249 fail(); 250 } catch (IllegalStateException expected) {} 251 try { 252 builder1.softValues(); 253 fail(); 254 } catch (IllegalStateException expected) {} 255 256 CacheBuilder<Object, Object> builder2 = new CacheBuilder<Object, Object>().softValues(); 257 try { 258 builder2.softValues(); 259 fail(); 260 } catch (IllegalStateException expected) {} 261 try { 262 builder2.weakValues(); 263 fail(); 264 } catch (IllegalStateException expected) {} 265 } 266 267 public void testTimeToLive_negative() { 268 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 269 try { 270 builder.expireAfterWrite(-1, SECONDS); 271 fail(); 272 } catch (IllegalArgumentException expected) {} 273 } 274 275 public void testTimeToLive_small() { 276 CacheBuilder.newBuilder() 277 .expireAfterWrite(1, NANOSECONDS) 278 .build(identityLoader()); 279 // well, it didn't blow up. 280 } 281 282 public void testTimeToLive_setTwice() { 283 CacheBuilder<Object, Object> builder = 284 new CacheBuilder<Object, Object>().expireAfterWrite(3600, SECONDS); 285 try { 286 // even to the same value is not allowed 287 builder.expireAfterWrite(3600, SECONDS); 288 fail(); 289 } catch (IllegalStateException expected) {} 290 } 291 292 @GwtIncompatible("expireAfterAccess") 293 public void testTimeToIdle_negative() { 294 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 295 try { 296 builder.expireAfterAccess(-1, SECONDS); 297 fail(); 298 } catch (IllegalArgumentException expected) {} 299 } 300 301 @GwtIncompatible("expireAfterAccess") 302 public void testTimeToIdle_small() { 303 CacheBuilder.newBuilder() 304 .expireAfterAccess(1, NANOSECONDS) 305 .build(identityLoader()); 306 // well, it didn't blow up. 307 } 308 309 @GwtIncompatible("expireAfterAccess") 310 public void testTimeToIdle_setTwice() { 311 CacheBuilder<Object, Object> builder = 312 new CacheBuilder<Object, Object>().expireAfterAccess(3600, SECONDS); 313 try { 314 // even to the same value is not allowed 315 builder.expireAfterAccess(3600, SECONDS); 316 fail(); 317 } catch (IllegalStateException expected) {} 318 } 319 320 @GwtIncompatible("expireAfterAccess") 321 public void testTimeToIdleAndToLive() { 322 CacheBuilder.newBuilder() 323 .expireAfterWrite(1, NANOSECONDS) 324 .expireAfterAccess(1, NANOSECONDS) 325 .build(identityLoader()); 326 // well, it didn't blow up. 327 } 328 329 @GwtIncompatible("refreshAfterWrite") 330 public void testRefresh_zero() { 331 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 332 try { 333 builder.refreshAfterWrite(0, SECONDS); 334 fail(); 335 } catch (IllegalArgumentException expected) {} 336 } 337 338 @GwtIncompatible("refreshAfterWrite") 339 public void testRefresh_setTwice() { 340 CacheBuilder<Object, Object> builder = 341 new CacheBuilder<Object, Object>().refreshAfterWrite(3600, SECONDS); 342 try { 343 // even to the same value is not allowed 344 builder.refreshAfterWrite(3600, SECONDS); 345 fail(); 346 } catch (IllegalStateException expected) {} 347 } 348 349 @GwtIncompatible("ticker") 350 public void testTicker_setTwice() { 351 Ticker testTicker = Ticker.systemTicker(); 352 CacheBuilder<Object, Object> builder = 353 new CacheBuilder<Object, Object>().ticker(testTicker); 354 try { 355 // even to the same instance is not allowed 356 builder.ticker(testTicker); 357 fail(); 358 } catch (IllegalStateException expected) {} 359 } 360 361 @GwtIncompatible("removalListener") 362 public void testRemovalListener_setTwice() { 363 RemovalListener<Object, Object> testListener = nullRemovalListener(); 364 CacheBuilder<Object, Object> builder = 365 new CacheBuilder<Object, Object>().removalListener(testListener); 366 try { 367 // even to the same instance is not allowed 368 builder = builder.removalListener(testListener); 369 fail(); 370 } catch (IllegalStateException expected) {} 371 } 372 373 @GwtIncompatible("removalListener") 374 public void testNullCache() { 375 CountingRemovalListener<Object, Object> listener = countingRemovalListener(); 376 LoadingCache<Object, Object> nullCache = new CacheBuilder<Object, Object>() 377 .maximumSize(0) 378 .removalListener(listener) 379 .build(identityLoader()); 380 assertEquals(0, nullCache.size()); 381 Object key = new Object(); 382 assertSame(key, nullCache.getUnchecked(key)); 383 assertEquals(1, listener.getCount()); 384 assertEquals(0, nullCache.size()); 385 CacheTesting.checkEmpty(nullCache.asMap()); 386 } 387 388 @GwtIncompatible("removalListener") 389 390 public void testRemovalNotification_clear() throws InterruptedException { 391 // If a clear() happens while a computation is pending, we should not get a removal 392 // notification. 393 394 final AtomicBoolean shouldWait = new AtomicBoolean(false); 395 final CountDownLatch computingLatch = new CountDownLatch(1); 396 CacheLoader<String, String> computingFunction = new CacheLoader<String, String>() { 397 @Override public String load(String key) throws InterruptedException { 398 if (shouldWait.get()) { 399 computingLatch.await(); 400 } 401 return key; 402 } 403 }; 404 QueuingRemovalListener<String, String> listener = queuingRemovalListener(); 405 406 final LoadingCache<String, String> cache = CacheBuilder.newBuilder() 407 .concurrencyLevel(1) 408 .removalListener(listener) 409 .build(computingFunction); 410 411 // seed the map, so its segment's count > 0 412 cache.getUnchecked("a"); 413 shouldWait.set(true); 414 415 final CountDownLatch computationStarted = new CountDownLatch(1); 416 final CountDownLatch computationComplete = new CountDownLatch(1); 417 new Thread(new Runnable() { 418 @Override public void run() { 419 computationStarted.countDown(); 420 cache.getUnchecked("b"); 421 computationComplete.countDown(); 422 } 423 }).start(); 424 425 // wait for the computingEntry to be created 426 computationStarted.await(); 427 cache.invalidateAll(); 428 // let the computation proceed 429 computingLatch.countDown(); 430 // don't check cache.size() until we know the get("b") call is complete 431 computationComplete.await(); 432 433 // At this point, the listener should be holding the seed value (a -> a), and the map should 434 // contain the computed value (b -> b), since the clear() happened before the computation 435 // completed. 436 assertEquals(1, listener.size()); 437 RemovalNotification<String, String> notification = listener.remove(); 438 assertEquals("a", notification.getKey()); 439 assertEquals("a", notification.getValue()); 440 assertEquals(1, cache.size()); 441 assertEquals("b", cache.getUnchecked("b")); 442 } 443 444 // "Basher tests", where we throw a bunch of stuff at a LoadingCache and check basic invariants. 445 446 /** 447 * This is a less carefully-controlled version of {@link #testRemovalNotification_clear} - this is 448 * a black-box test that tries to create lots of different thread-interleavings, and asserts that 449 * each computation is affected by a call to {@code clear()} (and therefore gets passed to the 450 * removal listener), or else is not affected by the {@code clear()} (and therefore exists in the 451 * cache afterward). 452 */ 453 @GwtIncompatible("removalListener") 454 455 public void testRemovalNotification_clear_basher() throws InterruptedException { 456 // If a clear() happens close to the end of computation, one of two things should happen: 457 // - computation ends first: the removal listener is called, and the cache does not contain the 458 // key/value pair 459 // - clear() happens first: the removal listener is not called, and the cache contains the pair 460 AtomicBoolean computationShouldWait = new AtomicBoolean(); 461 CountDownLatch computationLatch = new CountDownLatch(1); 462 QueuingRemovalListener<String, String> listener = queuingRemovalListener(); 463 final LoadingCache <String, String> cache = CacheBuilder.newBuilder() 464 .removalListener(listener) 465 .concurrencyLevel(20) 466 .build( 467 new DelayingIdentityLoader<String>(computationShouldWait, computationLatch)); 468 469 int nThreads = 100; 470 int nTasks = 1000; 471 int nSeededEntries = 100; 472 Set<String> expectedKeys = Sets.newHashSetWithExpectedSize(nTasks + nSeededEntries); 473 // seed the map, so its segments have a count>0; otherwise, clear() won't visit the in-progress 474 // entries 475 for (int i = 0; i < nSeededEntries; i++) { 476 String s = "b" + i; 477 cache.getUnchecked(s); 478 expectedKeys.add(s); 479 } 480 computationShouldWait.set(true); 481 482 final AtomicInteger computedCount = new AtomicInteger(); 483 ExecutorService threadPool = Executors.newFixedThreadPool(nThreads); 484 final CountDownLatch tasksFinished = new CountDownLatch(nTasks); 485 for (int i = 0; i < nTasks; i++) { 486 final String s = "a" + i; 487 threadPool.submit(new Runnable() { 488 @Override public void run() { 489 cache.getUnchecked(s); 490 computedCount.incrementAndGet(); 491 tasksFinished.countDown(); 492 } 493 }); 494 expectedKeys.add(s); 495 } 496 497 computationLatch.countDown(); 498 // let some computations complete 499 while (computedCount.get() < nThreads) { 500 Thread.yield(); 501 } 502 cache.invalidateAll(); 503 tasksFinished.await(); 504 505 // Check all of the removal notifications we received: they should have had correctly-associated 506 // keys and values. (An earlier bug saw removal notifications for in-progress computations, 507 // which had real keys with null values.) 508 Map<String, String> removalNotifications = Maps.newHashMap(); 509 for (RemovalNotification<String, String> notification : listener) { 510 removalNotifications.put(notification.getKey(), notification.getValue()); 511 assertEquals("Unexpected key/value pair passed to removalListener", 512 notification.getKey(), notification.getValue()); 513 } 514 515 // All of the seed values should have been visible, so we should have gotten removal 516 // notifications for all of them. 517 for (int i = 0; i < nSeededEntries; i++) { 518 assertEquals("b" + i, removalNotifications.get("b" + i)); 519 } 520 521 // Each of the values added to the map should either still be there, or have seen a removal 522 // notification. 523 assertEquals(expectedKeys, Sets.union(cache.asMap().keySet(), removalNotifications.keySet())); 524 assertTrue(Sets.intersection(cache.asMap().keySet(), removalNotifications.keySet()).isEmpty()); 525 } 526 527 /** 528 * Calls get() repeatedly from many different threads, and tests that all of the removed entries 529 * (removed because of size limits or expiration) trigger appropriate removal notifications. 530 */ 531 @GwtIncompatible("removalListener") 532 533 public void testRemovalNotification_get_basher() throws InterruptedException { 534 int nTasks = 3000; 535 int nThreads = 100; 536 final int getsPerTask = 1000; 537 final int nUniqueKeys = 10000; 538 final Random random = new Random(); // Randoms.insecureRandom(); 539 540 QueuingRemovalListener<String, String> removalListener = queuingRemovalListener(); 541 final AtomicInteger computeCount = new AtomicInteger(); 542 final AtomicInteger exceptionCount = new AtomicInteger(); 543 final AtomicInteger computeNullCount = new AtomicInteger(); 544 CacheLoader<String, String> countingIdentityLoader = 545 new CacheLoader<String, String>() { 546 @Override public String load(String key) throws InterruptedException { 547 int behavior = random.nextInt(4); 548 if (behavior == 0) { // throw an exception 549 exceptionCount.incrementAndGet(); 550 throw new RuntimeException("fake exception for test"); 551 } else if (behavior == 1) { // return null 552 computeNullCount.incrementAndGet(); 553 return null; 554 } else if (behavior == 2) { // slight delay before returning 555 Thread.sleep(5); 556 computeCount.incrementAndGet(); 557 return key; 558 } else { 559 computeCount.incrementAndGet(); 560 return key; 561 } 562 } 563 }; 564 final LoadingCache<String, String> cache = CacheBuilder.newBuilder() 565 .concurrencyLevel(2) 566 .expireAfterWrite(100, TimeUnit.MILLISECONDS) 567 .removalListener(removalListener) 568 .maximumSize(5000) 569 .build(countingIdentityLoader); 570 571 ExecutorService threadPool = Executors.newFixedThreadPool(nThreads); 572 for (int i = 0; i < nTasks; i++) { 573 threadPool.submit(new Runnable() { 574 @Override public void run() { 575 for (int j = 0; j < getsPerTask; j++) { 576 try { 577 cache.getUnchecked("key" + random.nextInt(nUniqueKeys)); 578 } catch (RuntimeException e) { 579 } 580 } 581 } 582 }); 583 } 584 585 threadPool.shutdown(); 586 threadPool.awaitTermination(300, TimeUnit.SECONDS); 587 588 // Since we're not doing any more cache operations, and the cache only expires/evicts when doing 589 // other operations, the cache and the removal queue won't change from this point on. 590 591 // Verify that each received removal notification was valid 592 for (RemovalNotification<String, String> notification : removalListener) { 593 assertEquals("Invalid removal notification", notification.getKey(), notification.getValue()); 594 } 595 596 CacheStats stats = cache.stats(); 597 assertEquals(removalListener.size(), stats.evictionCount()); 598 assertEquals(computeCount.get(), stats.loadSuccessCount()); 599 assertEquals(exceptionCount.get() + computeNullCount.get(), stats.loadExceptionCount()); 600 // each computed value is still in the cache, or was passed to the removal listener 601 assertEquals(computeCount.get(), cache.size() + removalListener.size()); 602 } 603 604 @GwtIncompatible("NullPointerTester") 605 public void testNullParameters() throws Exception { 606 NullPointerTester tester = new NullPointerTester(); 607 CacheBuilder<Object, Object> builder = new CacheBuilder<Object, Object>(); 608 tester.testAllPublicInstanceMethods(builder); 609 } 610 611 @GwtIncompatible("CacheTesting") 612 public void testSizingDefaults() { 613 LoadingCache<?, ?> cache = CacheBuilder.newBuilder().build(identityLoader()); 614 LocalCache<?, ?> map = CacheTesting.toLocalCache(cache); 615 assertEquals(4, map.segments.length); // concurrency level 616 assertEquals(4, map.segments[0].table.length()); // capacity / conc level 617 } 618 619 @GwtIncompatible("CountDownLatch") 620 static final class DelayingIdentityLoader<T> extends CacheLoader<T, T> { 621 private final AtomicBoolean shouldWait; 622 private final CountDownLatch delayLatch; 623 624 DelayingIdentityLoader(AtomicBoolean shouldWait, CountDownLatch delayLatch) { 625 this.shouldWait = shouldWait; 626 this.delayLatch = delayLatch; 627 } 628 629 @Override public T load(T key) throws InterruptedException { 630 if (shouldWait.get()) { 631 delayLatch.await(); 632 } 633 return key; 634 } 635 } 636 } 637