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 com.google.common.truth.Truth.assertThat;
22import static java.util.Arrays.asList;
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 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