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 15 package com.google.common.cache; 16 17 import static com.google.common.cache.TestingCacheLoaders.identityLoader; 18 import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener; 19 import static com.google.common.cache.TestingWeighers.constantWeigher; 20 import static com.google.common.cache.TestingWeighers.intKeyWeigher; 21 import static com.google.common.truth.Truth.assertThat; 22 import static java.util.Arrays.asList; 23 24 import com.google.common.cache.CacheTesting.Receiver; 25 import com.google.common.cache.LocalCache.ReferenceEntry; 26 import com.google.common.cache.TestingCacheLoaders.IdentityLoader; 27 import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener; 28 29 import junit.framework.TestCase; 30 31 import java.util.List; 32 import java.util.Set; 33 34 /** 35 * Tests relating to cache eviction: what does and doesn't count toward maximumSize, what happens 36 * when maximumSize is reached, etc. 37 * 38 * @author mike nonemacher 39 */ 40 public class CacheEvictionTest extends TestCase { 41 static final int MAX_SIZE = 100; 42 43 public void testEviction_setMaxSegmentSize() { 44 IdentityLoader<Object> loader = identityLoader(); 45 for (int i = 1; i < 1000; i++) { 46 LoadingCache<Object, Object> cache = CacheBuilder.newBuilder() 47 .maximumSize(i) 48 .build(loader); 49 assertEquals(i, CacheTesting.getTotalSegmentSize(cache)); 50 } 51 } 52 53 public void testEviction_setMaxSegmentWeight() { 54 IdentityLoader<Object> loader = identityLoader(); 55 for (int i = 1; i < 1000; i++) { 56 LoadingCache<Object, Object> cache = CacheBuilder.newBuilder() 57 .maximumWeight(i) 58 .weigher(constantWeigher(1)) 59 .build(loader); 60 assertEquals(i, CacheTesting.getTotalSegmentSize(cache)); 61 } 62 } 63 64 public void testEviction_maxSizeOneSegment() { 65 IdentityLoader<Integer> loader = identityLoader(); 66 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 67 .concurrencyLevel(1) 68 .maximumSize(MAX_SIZE) 69 .build(loader); 70 for (int i = 0; i < 2 * MAX_SIZE; i++) { 71 cache.getUnchecked(i); 72 assertEquals(Math.min(i + 1, MAX_SIZE), cache.size()); 73 } 74 75 assertEquals(MAX_SIZE, cache.size()); 76 CacheTesting.checkValidState(cache); 77 } 78 79 public void testEviction_maxWeightOneSegment() { 80 IdentityLoader<Integer> loader = identityLoader(); 81 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 82 .concurrencyLevel(1) 83 .maximumWeight(2 * MAX_SIZE) 84 .weigher(constantWeigher(2)) 85 .build(loader); 86 for (int i = 0; i < 2 * MAX_SIZE; i++) { 87 cache.getUnchecked(i); 88 assertEquals(Math.min(i + 1, MAX_SIZE), cache.size()); 89 } 90 91 assertEquals(MAX_SIZE, cache.size()); 92 CacheTesting.checkValidState(cache); 93 } 94 95 public void testEviction_maxSize() { 96 CountingRemovalListener<Integer, Integer> removalListener = countingRemovalListener(); 97 IdentityLoader<Integer> loader = identityLoader(); 98 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 99 .maximumSize(MAX_SIZE) 100 .removalListener(removalListener) 101 .build(loader); 102 for (int i = 0; i < 2 * MAX_SIZE; i++) { 103 cache.getUnchecked(i); 104 assertTrue(cache.size() <= MAX_SIZE); 105 } 106 107 assertEquals(MAX_SIZE, CacheTesting.accessQueueSize(cache)); 108 assertEquals(MAX_SIZE, cache.size()); 109 CacheTesting.processPendingNotifications(cache); 110 assertEquals(MAX_SIZE, removalListener.getCount()); 111 CacheTesting.checkValidState(cache); 112 } 113 114 public void testEviction_maxWeight() { 115 CountingRemovalListener<Integer, Integer> removalListener = countingRemovalListener(); 116 IdentityLoader<Integer> loader = identityLoader(); 117 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 118 .maximumWeight(2 * MAX_SIZE) 119 .weigher(constantWeigher(2)) 120 .removalListener(removalListener) 121 .build(loader); 122 for (int i = 0; i < 2 * MAX_SIZE; i++) { 123 cache.getUnchecked(i); 124 assertTrue(cache.size() <= MAX_SIZE); 125 } 126 127 assertEquals(MAX_SIZE, CacheTesting.accessQueueSize(cache)); 128 assertEquals(MAX_SIZE, cache.size()); 129 CacheTesting.processPendingNotifications(cache); 130 assertEquals(MAX_SIZE, removalListener.getCount()); 131 CacheTesting.checkValidState(cache); 132 } 133 134 public void testEviction_overflow() { 135 CountingRemovalListener<Object, Object> removalListener = countingRemovalListener(); 136 IdentityLoader<Object> loader = identityLoader(); 137 LoadingCache<Object, Object> cache = CacheBuilder.newBuilder() 138 .concurrencyLevel(1) 139 .maximumWeight(1L << 31) 140 .weigher(constantWeigher(Integer.MAX_VALUE)) 141 .removalListener(removalListener) 142 .build(loader); 143 cache.getUnchecked(objectWithHash(0)); 144 cache.getUnchecked(objectWithHash(0)); 145 CacheTesting.processPendingNotifications(cache); 146 assertEquals(1, removalListener.getCount()); 147 } 148 149 public void testUpdateRecency_onGet() { 150 IdentityLoader<Integer> loader = identityLoader(); 151 final LoadingCache<Integer, Integer> cache = 152 CacheBuilder.newBuilder().maximumSize(MAX_SIZE).build(loader); 153 CacheTesting.checkRecency(cache, MAX_SIZE, 154 new Receiver<ReferenceEntry<Integer, Integer>>() { 155 @Override 156 public void accept(ReferenceEntry<Integer, Integer> entry) { 157 cache.getUnchecked(entry.getKey()); 158 } 159 }); 160 } 161 162 public void testUpdateRecency_onInvalidate() { 163 IdentityLoader<Integer> loader = identityLoader(); 164 final LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 165 .maximumSize(MAX_SIZE) 166 .concurrencyLevel(1) 167 .build(loader); 168 CacheTesting.checkRecency(cache, MAX_SIZE, 169 new Receiver<ReferenceEntry<Integer, Integer>>() { 170 @Override 171 public void accept(ReferenceEntry<Integer, Integer> entry) { 172 Integer key = entry.getKey(); 173 cache.invalidate(key); 174 } 175 }); 176 } 177 178 public void testEviction_lru() { 179 // test lru within a single segment 180 IdentityLoader<Integer> loader = identityLoader(); 181 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 182 .concurrencyLevel(1) 183 .maximumSize(10) 184 .build(loader); 185 CacheTesting.warmUp(cache, 0, 10); 186 Set<Integer> keySet = cache.asMap().keySet(); 187 assertThat(keySet).has().exactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 188 189 // re-order 190 getAll(cache, asList(0, 1, 2)); 191 CacheTesting.drainRecencyQueues(cache); 192 assertThat(keySet).has().exactly(3, 4, 5, 6, 7, 8, 9, 0, 1, 2); 193 194 // evict 3, 4, 5 195 getAll(cache, asList(10, 11, 12)); 196 CacheTesting.drainRecencyQueues(cache); 197 assertThat(keySet).has().exactly(6, 7, 8, 9, 0, 1, 2, 10, 11, 12); 198 199 // re-order 200 getAll(cache, asList(6, 7, 8)); 201 CacheTesting.drainRecencyQueues(cache); 202 assertThat(keySet).has().exactly(9, 0, 1, 2, 10, 11, 12, 6, 7, 8); 203 204 // evict 9, 0, 1 205 getAll(cache, asList(13, 14, 15)); 206 CacheTesting.drainRecencyQueues(cache); 207 assertThat(keySet).has().exactly(2, 10, 11, 12, 6, 7, 8, 13, 14, 15); 208 } 209 210 public void testEviction_weightedLru() { 211 // test weighted lru within a single segment 212 IdentityLoader<Integer> loader = identityLoader(); 213 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 214 .concurrencyLevel(1) 215 .maximumWeight(45) 216 .weigher(intKeyWeigher()) 217 .build(loader); 218 CacheTesting.warmUp(cache, 0, 10); 219 Set<Integer> keySet = cache.asMap().keySet(); 220 assertThat(keySet).has().exactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 221 222 // re-order 223 getAll(cache, asList(0, 1, 2)); 224 CacheTesting.drainRecencyQueues(cache); 225 assertThat(keySet).has().exactly(3, 4, 5, 6, 7, 8, 9, 0, 1, 2); 226 227 // evict 3, 4, 5 228 getAll(cache, asList(10)); 229 CacheTesting.drainRecencyQueues(cache); 230 assertThat(keySet).has().exactly(6, 7, 8, 9, 0, 1, 2, 10); 231 232 // re-order 233 getAll(cache, asList(6, 7, 8)); 234 CacheTesting.drainRecencyQueues(cache); 235 assertThat(keySet).has().exactly(9, 0, 1, 2, 10, 6, 7, 8); 236 237 // evict 9, 1, 2, 10 238 getAll(cache, asList(15)); 239 CacheTesting.drainRecencyQueues(cache); 240 assertThat(keySet).has().exactly(0, 6, 7, 8, 15); 241 242 // fill empty space 243 getAll(cache, asList(9)); 244 CacheTesting.drainRecencyQueues(cache); 245 assertThat(keySet).has().exactly(0, 6, 7, 8, 15, 9); 246 247 // evict 6 248 getAll(cache, asList(1)); 249 CacheTesting.drainRecencyQueues(cache); 250 assertThat(keySet).has().exactly(0, 7, 8, 15, 9, 1); 251 } 252 253 public void testEviction_overweight() { 254 // test weighted lru within a single segment 255 IdentityLoader<Integer> loader = identityLoader(); 256 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 257 .concurrencyLevel(1) 258 .maximumWeight(45) 259 .weigher(intKeyWeigher()) 260 .build(loader); 261 CacheTesting.warmUp(cache, 0, 10); 262 Set<Integer> keySet = cache.asMap().keySet(); 263 assertThat(keySet).has().exactly(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 264 265 // add an at-the-maximum-weight entry 266 getAll(cache, asList(45)); 267 CacheTesting.drainRecencyQueues(cache); 268 assertThat(keySet).has().exactly(0, 45); 269 270 // add an over-the-maximum-weight entry 271 getAll(cache, asList(46)); 272 CacheTesting.drainRecencyQueues(cache); 273 assertThat(keySet).has().item(0); 274 } 275 276 public void testEviction_invalidateAll() { 277 // test that .invalidateAll() resets total weight state correctly 278 IdentityLoader<Integer> loader = identityLoader(); 279 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 280 .concurrencyLevel(1) 281 .maximumSize(10) 282 .build(loader); 283 284 Set<Integer> keySet = cache.asMap().keySet(); 285 assertThat(keySet).isEmpty(); 286 287 // add 0, 1, 2, 3, 4 288 getAll(cache, asList(0, 1, 2, 3, 4)); 289 CacheTesting.drainRecencyQueues(cache); 290 assertThat(keySet).has().exactly(0, 1, 2, 3, 4); 291 292 // invalidate all 293 cache.invalidateAll(); 294 CacheTesting.drainRecencyQueues(cache); 295 assertThat(keySet).isEmpty(); 296 297 // add 5, 6, 7, 8, 9, 10, 11, 12 298 getAll(cache, asList(5, 6, 7, 8, 9, 10, 11, 12)); 299 CacheTesting.drainRecencyQueues(cache); 300 assertThat(keySet).has().exactly(5, 6, 7, 8, 9, 10, 11, 12); 301 } 302 303 private void getAll(LoadingCache<Integer, Integer> cache, List<Integer> keys) { 304 for (int i : keys) { 305 cache.getUnchecked(i); 306 } 307 } 308 309 private Object objectWithHash(final int hash) { 310 return new Object() { 311 @Override public int hashCode() { 312 return hash; 313 } 314 }; 315 } 316 } 317
