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 java.util.Arrays.asList; 22 import static org.junit.contrib.truth.Truth.ASSERT; 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 testUpdateRecency_onGet() { 135 IdentityLoader<Integer> loader = identityLoader(); 136 final LoadingCache<Integer, Integer> cache = 137 CacheBuilder.newBuilder().maximumSize(MAX_SIZE).build(loader); 138 CacheTesting.checkRecency(cache, MAX_SIZE, 139 new Receiver<ReferenceEntry<Integer, Integer>>() { 140 @Override 141 public void accept(ReferenceEntry<Integer, Integer> entry) { 142 cache.getUnchecked(entry.getKey()); 143 } 144 }); 145 } 146 147 public void testUpdateRecency_onInvalidate() { 148 IdentityLoader<Integer> loader = identityLoader(); 149 final LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 150 .maximumSize(MAX_SIZE) 151 .concurrencyLevel(1) 152 .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 Integer key = entry.getKey(); 158 cache.invalidate(key); 159 } 160 }); 161 } 162 163 public void testEviction_lru() { 164 // test lru within a single segment 165 IdentityLoader<Integer> loader = identityLoader(); 166 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 167 .concurrencyLevel(1) 168 .maximumSize(10) 169 .build(loader); 170 CacheTesting.warmUp(cache, 0, 10); 171 Set<Integer> keySet = cache.asMap().keySet(); 172 ASSERT.that(keySet).hasContentsAnyOrder(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 173 174 // re-order 175 getAll(cache, asList(0, 1, 2)); 176 CacheTesting.drainRecencyQueues(cache); 177 ASSERT.that(keySet).hasContentsAnyOrder(3, 4, 5, 6, 7, 8, 9, 0, 1, 2); 178 179 // evict 3, 4, 5 180 getAll(cache, asList(10, 11, 12)); 181 CacheTesting.drainRecencyQueues(cache); 182 ASSERT.that(keySet).hasContentsAnyOrder(6, 7, 8, 9, 0, 1, 2, 10, 11, 12); 183 184 // re-order 185 getAll(cache, asList(6, 7, 8)); 186 CacheTesting.drainRecencyQueues(cache); 187 ASSERT.that(keySet).hasContentsAnyOrder(9, 0, 1, 2, 10, 11, 12, 6, 7, 8); 188 189 // evict 9, 0, 1 190 getAll(cache, asList(13, 14, 15)); 191 CacheTesting.drainRecencyQueues(cache); 192 ASSERT.that(keySet).hasContentsAnyOrder(2, 10, 11, 12, 6, 7, 8, 13, 14, 15); 193 } 194 195 public void testEviction_weightedLru() { 196 // test weighted lru within a single segment 197 IdentityLoader<Integer> loader = identityLoader(); 198 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 199 .concurrencyLevel(1) 200 .maximumWeight(45) 201 .weigher(intKeyWeigher()) 202 .build(loader); 203 CacheTesting.warmUp(cache, 0, 10); 204 Set<Integer> keySet = cache.asMap().keySet(); 205 ASSERT.that(keySet).hasContentsAnyOrder(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 206 207 // re-order 208 getAll(cache, asList(0, 1, 2)); 209 CacheTesting.drainRecencyQueues(cache); 210 ASSERT.that(keySet).hasContentsAnyOrder(3, 4, 5, 6, 7, 8, 9, 0, 1, 2); 211 212 // evict 3, 4, 5 213 getAll(cache, asList(10)); 214 CacheTesting.drainRecencyQueues(cache); 215 ASSERT.that(keySet).hasContentsAnyOrder(6, 7, 8, 9, 0, 1, 2, 10); 216 217 // re-order 218 getAll(cache, asList(6, 7, 8)); 219 CacheTesting.drainRecencyQueues(cache); 220 ASSERT.that(keySet).hasContentsAnyOrder(9, 0, 1, 2, 10, 6, 7, 8); 221 222 // evict 9, 1, 2, 10 223 getAll(cache, asList(15)); 224 CacheTesting.drainRecencyQueues(cache); 225 ASSERT.that(keySet).hasContentsAnyOrder(0, 6, 7, 8, 15); 226 227 // fill empty space 228 getAll(cache, asList(9)); 229 CacheTesting.drainRecencyQueues(cache); 230 ASSERT.that(keySet).hasContentsAnyOrder(0, 6, 7, 8, 15, 9); 231 232 // evict 6 233 getAll(cache, asList(1)); 234 CacheTesting.drainRecencyQueues(cache); 235 ASSERT.that(keySet).hasContentsAnyOrder(0, 7, 8, 15, 9, 1); 236 } 237 238 public void testEviction_overweight() { 239 // test weighted lru within a single segment 240 IdentityLoader<Integer> loader = identityLoader(); 241 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 242 .concurrencyLevel(1) 243 .maximumWeight(45) 244 .weigher(intKeyWeigher()) 245 .build(loader); 246 CacheTesting.warmUp(cache, 0, 10); 247 Set<Integer> keySet = cache.asMap().keySet(); 248 ASSERT.that(keySet).hasContentsAnyOrder(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 249 250 // add an at-the-maximum-weight entry 251 getAll(cache, asList(45)); 252 CacheTesting.drainRecencyQueues(cache); 253 ASSERT.that(keySet).hasContentsAnyOrder(0, 45); 254 255 // add an over-the-maximum-weight entry 256 getAll(cache, asList(46)); 257 CacheTesting.drainRecencyQueues(cache); 258 ASSERT.that(keySet).hasContentsAnyOrder(0); 259 } 260 261 public void testEviction_invalidateAll() { 262 // test that .invalidateAll() resets total weight state correctly 263 IdentityLoader<Integer> loader = identityLoader(); 264 LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder() 265 .concurrencyLevel(1) 266 .maximumSize(10) 267 .build(loader); 268 269 Set<Integer> keySet = cache.asMap().keySet(); 270 ASSERT.that(keySet).isEmpty(); 271 272 // add 0, 1, 2, 3, 4 273 getAll(cache, asList(0, 1, 2, 3, 4)); 274 CacheTesting.drainRecencyQueues(cache); 275 ASSERT.that(keySet).hasContentsAnyOrder(0, 1, 2, 3, 4); 276 277 // invalidate all 278 cache.invalidateAll(); 279 CacheTesting.drainRecencyQueues(cache); 280 ASSERT.that(keySet).isEmpty(); 281 282 // add 5, 6, 7, 8, 9, 10, 11, 12 283 getAll(cache, asList(5, 6, 7, 8, 9, 10, 11, 12)); 284 CacheTesting.drainRecencyQueues(cache); 285 ASSERT.that(keySet).hasContentsAnyOrder(5, 6, 7, 8, 9, 10, 11, 12); 286 } 287 288 private void getAll(LoadingCache<Integer, Integer> cache, List<Integer> keys) { 289 for (int i : keys) { 290 cache.getUnchecked(i); 291 } 292 } 293 } 294
