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.truth0.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 
testEviction_setMaxSegmentSize()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 
testEviction_setMaxSegmentWeight()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 
testEviction_maxSizeOneSegment()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 
testEviction_maxWeightOneSegment()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 
testEviction_maxSize()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 
testEviction_maxWeight()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 
testUpdateRecency_onGet()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 
testUpdateRecency_onInvalidate()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 
testEviction_lru()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).has().exactly(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).has().exactly(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).has().exactly(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).has().exactly(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).has().exactly(2, 10, 11, 12, 6, 7, 8, 13, 14, 15);
193   }
194 
testEviction_weightedLru()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).has().exactly(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).has().exactly(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).has().exactly(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).has().exactly(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).has().exactly(0, 6, 7, 8, 15);
226 
227     // fill empty space
228     getAll(cache, asList(9));
229     CacheTesting.drainRecencyQueues(cache);
230     ASSERT.that(keySet).has().exactly(0, 6, 7, 8, 15, 9);
231 
232     // evict 6
233     getAll(cache, asList(1));
234     CacheTesting.drainRecencyQueues(cache);
235     ASSERT.that(keySet).has().exactly(0, 7, 8, 15, 9, 1);
236   }
237 
testEviction_overweight()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).has().exactly(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).has().exactly(0, 45);
254 
255     // add an over-the-maximum-weight entry
256     getAll(cache, asList(46));
257     CacheTesting.drainRecencyQueues(cache);
258     ASSERT.that(keySet).has().item(0);
259   }
260 
testEviction_invalidateAll()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).has().exactly(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).has().exactly(5, 6, 7, 8, 9, 10, 11, 12);
286   }
287 
getAll(LoadingCache<Integer, Integer> cache, List<Integer> keys)288   private void getAll(LoadingCache<Integer, Integer> cache, List<Integer> keys) {
289     for (int i : keys) {
290       cache.getUnchecked(i);
291     }
292   }
293 }
294