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 com.google.common.cache.TestingCacheLoaders.identityLoader;
18import static com.google.common.cache.TestingRemovalListeners.countingRemovalListener;
19import static com.google.common.cache.TestingWeighers.constantWeigher;
20import static com.google.common.cache.TestingWeighers.intKeyWeigher;
21import static java.util.Arrays.asList;
22import static org.junit.contrib.truth.Truth.ASSERT;
23
24import com.google.common.cache.CacheTesting.Receiver;
25import com.google.common.cache.LocalCache.ReferenceEntry;
26import com.google.common.cache.TestingCacheLoaders.IdentityLoader;
27import com.google.common.cache.TestingRemovalListeners.CountingRemovalListener;
28
29import junit.framework.TestCase;
30
31import java.util.List;
32import 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 */
40public 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