Author: thomasm
Date: Tue Jan 7 13:25:40 2014
New Revision: 1556209
URL: http://svn.apache.org/r1556209
Log:
OAK-1094 CacheLIRS implementation incomplete (asMap, refresh, some tests)
Added:
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStoreCacheTest.java
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java?rev=1556209&r1=1556208&r2=1556209&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java
Tue Jan 7 13:25:40 2014
@@ -17,6 +17,7 @@
package org.apache.jackrabbit.oak.cache;
import java.util.ArrayList;
+import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
@@ -24,16 +25,20 @@ import java.util.Map;
import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentMap;
-import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ExecutionException;
import javax.annotation.Nullable;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
import com.google.common.cache.CacheLoader;
import com.google.common.cache.CacheStats;
import com.google.common.cache.LoadingCache;
import com.google.common.cache.Weigher;
import com.google.common.collect.ImmutableMap;
+import com.google.common.util.concurrent.ListenableFuture;
+import com.google.common.util.concurrent.UncheckedExecutionException;
/**
* A scan resistant cache. It is meant to cache objects that are relatively
@@ -65,6 +70,8 @@ import com.google.common.collect.Immutab
* @param <V> the value type
*/
public class CacheLIRS<K, V> implements LoadingCache<K, V> {
+
+ private static final Logger LOG = LoggerFactory.getLogger(CacheLIRS.class);
/**
* The maximum memory this cache should use.
@@ -209,6 +216,32 @@ public class CacheLIRS<K, V> implements
return getSegment(hash).get(key, hash, valueLoader);
}
+ /**
+ * Get the value, loading it if needed.
+ * <p>
+ * If there is an exception loading, an UncheckedExecutionException is
+ * thrown.
+ *
+ * @param key the key
+ * @return the value
+ * @throws UncheckedExecutionException
+ */
+ @Override
+ public V getUnchecked(K key) {
+ try {
+ return get(key);
+ } catch (ExecutionException e) {
+ throw new UncheckedExecutionException(e);
+ }
+ }
+
+ /**
+ * Get the value, loading it if needed.
+ *
+ * @param key the key
+ * @return the value
+ * @throws ExecutionException
+ */
@Override
public V get(K key) throws ExecutionException {
int hash = getHash(key);
@@ -216,6 +249,45 @@ public class CacheLIRS<K, V> implements
}
/**
+ * Re-load the value for the given key.
+ * <p>
+ * If there is an exception while loading, it is logged and ignored. This
+ * method calls CacheLoader.reload, but synchronously replaces the old
+ * value.
+ *
+ * @param key the key
+ */
+ @Override
+ public void refresh(K key) {
+ int hash = getHash(key);
+ try {
+ getSegment(hash).refresh(key, hash, loader);
+ } catch (ExecutionException e) {
+ LOG.warn("Could not refresh value for key " + key, e);
+ }
+ }
+
+ V replace(K key, V value) {
+ int hash = getHash(key);
+ return getSegment(hash).replace(key, hash, value, sizeOf(key, value));
+ }
+
+ boolean replace(K key, V oldValue, V newValue) {
+ int hash = getHash(key);
+ return getSegment(hash).replace(key, hash, oldValue, newValue,
sizeOf(key, newValue));
+ }
+
+ boolean remove(Object key, Object value) {
+ int hash = getHash(key);
+ return getSegment(hash).remove(key, hash, value);
+ }
+
+ protected V putIfAbsent(K key, V value) {
+ int hash = getHash(key);
+ return getSegment(hash).putIfAbsent(key, hash, value, sizeOf(key,
value));
+ }
+
+ /**
* Get the value for the given key if the entry is cached. This method
* adjusts the internal state of the cache sometimes, to ensure commonly
* used entries stay in the cache.
@@ -252,11 +324,23 @@ public class CacheLIRS<K, V> implements
* @param key the key (may not be null)
*/
@Override
- public synchronized void invalidate(Object key) {
+ public void invalidate(Object key) {
int hash = getHash(key);
getSegment(hash).invalidate(key, hash);
}
+ /**
+ * Remove an entry. Both resident and non-resident entries can be
+ * removed.
+ *
+ * @param key the key (may not be null)
+ * @return the old value or null
+ */
+ public V remove(Object key) {
+ int hash = getHash(key);
+ return getSegment(hash).remove(key, hash);
+ }
+
@SuppressWarnings("unchecked")
@Override
public void invalidateAll(Iterable<?> keys) {
@@ -379,6 +463,29 @@ public class CacheLIRS<K, V> implements
}
return map.entrySet();
}
+
+ protected Collection<V> values() {
+ ArrayList<V> list = new ArrayList<V>();
+ for (K k : keySet()) {
+ V v = find(k).value;
+ if (v != null) {
+ list.add(v);
+ }
+ }
+ return list;
+ }
+
+ boolean containsValue(Object value) {
+ for (Segment<K, V> s : segments) {
+ for (K k : s.keySet()) {
+ V v = find(k).value;
+ if (v != null && v.equals(value)) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
/**
* Get the set of keys for resident entries.
@@ -445,6 +552,12 @@ public class CacheLIRS<K, V> implements
}
return x;
}
+
+ void clear() {
+ for (Segment<K, V> s : segments) {
+ s.clear();
+ }
+ }
/**
* Get the list of keys. This method allows to read the internal state of
@@ -598,7 +711,7 @@ public class CacheLIRS<K, V> implements
clear();
}
- private void clear() {
+ synchronized void clear() {
// calculate the size of the map array
// assume a fill factor of at most 80%
@@ -762,6 +875,65 @@ public class CacheLIRS<K, V> implements
}
return value;
}
+
+ synchronized V replace(K key, int hash, V value, int memory) {
+ if (containsKey(key, hash)) {
+ return put(key, hash, value, memory);
+ }
+ return null;
+ }
+
+ synchronized boolean replace(K key, int hash, V oldValue, V newValue,
int memory) {
+ V old = get(key, hash);
+ if (old != null && old.equals(oldValue)) {
+ put(key, hash, newValue, memory);
+ return true;
+ }
+ return false;
+ }
+
+ synchronized boolean remove(Object key, int hash, Object value) {
+ V old = get(key, hash);
+ if (old != null && old.equals(value)) {
+ invalidate(key, hash);
+ return true;
+ }
+ return false;
+ }
+
+ synchronized V remove(Object key, int hash) {
+ V old = get(key, hash);
+ // even if old is null, there might still be a cold entry
+ invalidate(key, hash);
+ return old;
+ }
+
+ synchronized V putIfAbsent(K key, int hash, V value, int memory) {
+ V old = get(key, hash);
+ if (old == null) {
+ put(key, hash, value, memory);
+ return null;
+ }
+ return old;
+ }
+
+ synchronized void refresh(K key, int hash, CacheLoader<K, V> loader)
throws ExecutionException {
+ V value;
+ V old = get(key, hash);
+ long start = System.nanoTime();
+ try {
+ ListenableFuture<V> future = loader.reload(key, old);
+ value = future.get();
+ loadSuccessCount++;
+ } catch (Exception e) {
+ loadExceptionCount++;
+ throw new ExecutionException(e);
+ } finally {
+ long time = System.nanoTime() - start;
+ totalLoadTime += time;
+ }
+ put(key, hash, value, cache.sizeOf(key, value));
+ }
/**
* Add an entry to the cache. The entry may or may not exist in the
@@ -1192,14 +1364,96 @@ public class CacheLIRS<K, V> implements
@Override
public ConcurrentMap<K, V> asMap() {
- ConcurrentMap<K, V> map = new ConcurrentSkipListMap<K, V>();
- for (K key : keySet()) {
- V value = peek(key);
- if (value != null) {
- map.put(key, value);
+ return new ConcurrentMap<K, V>() {
+
+ @Override
+ public int size() {
+ long size = CacheLIRS.this.size();
+ return (int) Math.min(size, Integer.MAX_VALUE);
}
- }
- return map;
+
+ @Override
+ public boolean isEmpty() {
+ return CacheLIRS.this.size() == 0;
+ }
+
+ @Override
+ public boolean containsKey(Object key) {
+ return CacheLIRS.this.containsKey(key);
+ }
+
+ @Override
+ public boolean containsValue(Object value) {
+ return CacheLIRS.this.containsValue(value);
+ }
+
+ @SuppressWarnings("unchecked")
+ @Override
+ public V get(Object key) {
+ return CacheLIRS.this.getUnchecked((K) key);
+ }
+
+ @Override
+ public V put(K key, V value) {
+ return CacheLIRS.this.put(key, value, sizeOf(key, value));
+ }
+
+ @Override
+ public V remove(Object key) {
+ @SuppressWarnings("unchecked")
+ V old = CacheLIRS.this.getUnchecked((K) key);
+ CacheLIRS.this.invalidate(key);
+ return old;
+ }
+
+ @Override
+ public void putAll(Map<? extends K, ? extends V> m) {
+ for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
+ put(e.getKey(), e.getValue());
+ }
+ }
+
+ @Override
+ public void clear() {
+ CacheLIRS.this.clear();
+ }
+
+ @Override
+ public Set<K> keySet() {
+ return CacheLIRS.this.keySet();
+ }
+
+ @Override
+ public Collection<V> values() {
+ return CacheLIRS.this.values();
+ }
+
+ @Override
+ public Set<java.util.Map.Entry<K, V>> entrySet() {
+ return CacheLIRS.this.entrySet();
+ }
+
+ @Override
+ public V putIfAbsent(K key, V value) {
+ return CacheLIRS.this.putIfAbsent(key, value);
+ }
+
+ @Override
+ public boolean remove(Object key, Object value) {
+ return CacheLIRS.this.remove(key, value);
+ }
+
+ @Override
+ public boolean replace(K key, V oldValue, V newValue) {
+ return CacheLIRS.this.replace(key, oldValue, newValue);
+ }
+
+ @Override
+ public V replace(K key, V value) {
+ return CacheLIRS.this.replace(key, value);
+ }
+
+ };
}
@Override
@@ -1215,28 +1469,18 @@ public class CacheLIRS<K, V> implements
}
@Override
- public V getUnchecked(K key) {
- // TODO Auto-generated method stub
- return null;
- }
-
- @Override
public ImmutableMap<K, V> getAll(Iterable<? extends K> keys)
throws ExecutionException {
- // TODO Auto-generated method stub
- return null;
+ throw new UnsupportedOperationException();
}
@Override
public V apply(K key) {
- // TODO Auto-generated method stub
- return null;
+ throw new UnsupportedOperationException();
}
- @Override
- public void refresh(K key) {
- // TODO Auto-generated method stub
-
+ public boolean isEmpty() {
+ return size() == 0;
}
}
Added:
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java?rev=1556209&view=auto
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java
(added)
+++
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java
Tue Jan 7 13:25:40 2014
@@ -0,0 +1,606 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.cache;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map.Entry;
+import java.util.Random;
+import java.util.concurrent.ConcurrentMap;
+
+import org.junit.Test;
+
+/**
+ * Tests the LIRS cache.
+ */
+public class CacheTest {
+
+ @Test
+ public void testRandomSmallCache() {
+ Random r = new Random(1);
+ for (int i = 0; i < 10000; i++) {
+ int j = 0;
+ StringBuilder buff = new StringBuilder();
+ CacheLIRS<Integer, Integer> test = createCache(1 + r.nextInt(10));
+ for (; j < 30; j++) {
+ int key = r.nextInt(5);
+ switch (r.nextInt(3)) {
+ case 0:
+ int memory = r.nextInt(5) + 1;
+ buff.append("add ").append(key).append('
').append(memory).append('\n');
+ test.put(key, j, memory);
+ break;
+ case 1:
+ buff.append("remove ").append(key).append('\n');
+ test.invalidate(key);
+ break;
+ case 2:
+ buff.append("get ").append(key).append('\n');
+ test.getIfPresent(key);
+ }
+ }
+ }
+ }
+
+ @Test
+ public void testEdgeCases() {
+ CacheLIRS<Integer, Integer> test = createCache(1);
+ test.put(1, 10, 100);
+ assertEquals(10, test.getUnchecked(1).intValue());
+ try {
+ test.put(null, 10, 100);
+ fail();
+ } catch (NullPointerException e) {
+ // expected
+ }
+ try {
+ test.put(1, null, 100);
+ fail();
+ } catch (NullPointerException e) {
+ // expected
+ }
+ try {
+ test.setMaxMemory(0);
+ fail();
+ } catch (IllegalArgumentException e) {
+ // expected
+ }
+ try {
+ test.setAverageMemory(0);
+ fail();
+ } catch (IllegalArgumentException e) {
+ // expected
+ }
+ }
+
+ @Test
+ public void testSize() {
+ verifyMapSize(7, 16);
+ verifyMapSize(13, 32);
+ verifyMapSize(25, 64);
+ verifyMapSize(49, 128);
+ verifyMapSize(97, 256);
+ verifyMapSize(193, 512);
+ verifyMapSize(385, 1024);
+ verifyMapSize(769, 2048);
+
+ CacheLIRS<Integer, Integer> test;
+ test = createCache(3, 10);
+ test.put(0, 0, 9);
+ test.put(1, 10, 9);
+ test.put(2, 20, 9);
+ test.put(3, 30, 9);
+ test.put(4, 40, 9);
+
+ test = createCache(1, 1);
+ test.put(1, 10);
+ test.put(0, 0);
+ test.getUnchecked(0);
+
+ test = createCache(1000);
+ for (int j = 0; j < 2000; j++) {
+ test.put(j, j);
+ }
+ // for a cache of size 1000,
+ // there are 62 cold entries (about 6.25%).
+ assertEquals(62, test.size() - test.sizeHot());
+ // at most as many non-resident elements
+ // as there are entries in the stack
+ assertEquals(968, test.sizeNonResident());
+ }
+
+ private static void verifyMapSize(int elements, int expectedMapSize) {
+ CacheLIRS<Integer, Integer> test;
+ test = createCache(elements - 1);
+ assertTrue(test.sizeMapArray() < expectedMapSize);
+ test = createCache(elements);
+ assertEquals(expectedMapSize, test.sizeMapArray());
+ test = createCache(elements * 100, 100);
+ assertEquals(expectedMapSize, test.sizeMapArray());
+ }
+
+ @Test
+ public void testGetPutPeekRemove() {
+ CacheLIRS<Integer, Integer> test = createCache(4);
+ test.put(1, 10);
+ test.put(2, 20);
+ test.put(3, 30);
+ assertNull(test.peek(4));
+ assertNull(test.getIfPresent(4));
+ test.put(4, 40);
+ verify(test, "mem: 4 stack: 4 3 2 1 cold: non-resident:");
+ // move middle to front
+ assertEquals(30, test.getUnchecked(3).intValue());
+ assertEquals(20, test.getUnchecked(2).intValue());
+ assertEquals(20, test.peek(2).intValue());
+ // already on (an optimization)
+ assertEquals(20, test.getUnchecked(2).intValue());
+ assertEquals(10, test.peek(1).intValue());
+ assertEquals(10, test.getUnchecked(1).intValue());
+ verify(test, "mem: 4 stack: 1 2 3 4 cold: non-resident:");
+ test.put(3, 30);
+ verify(test, "mem: 4 stack: 3 1 2 4 cold: non-resident:");
+ // 5 is cold; will make 4 non-resident
+ test.put(5, 50);
+ verify(test, "mem: 4 stack: 5 3 1 2 cold: 5 non-resident: 4");
+ assertEquals(1, test.getMemory(1));
+ assertEquals(1, test.getMemory(5));
+ assertEquals(0, test.getMemory(4));
+ assertEquals(0, test.getMemory(100));
+ assertNull(test.peek(4));
+ assertNull(test.getIfPresent(4));
+ assertEquals(10, test.getUnchecked(1).intValue());
+ assertEquals(20, test.getUnchecked(2).intValue());
+ assertEquals(30, test.getUnchecked(3).intValue());
+ verify(test, "mem: 4 stack: 3 2 1 cold: 5 non-resident: 4");
+ assertEquals(50, test.getUnchecked(5).intValue());
+ verify(test, "mem: 4 stack: 5 3 2 1 cold: 5 non-resident: 4");
+ assertEquals(50, test.getUnchecked(5).intValue());
+ verify(test, "mem: 4 stack: 5 3 2 cold: 1 non-resident: 4");
+
+ // remove
+ assertEquals(50, test.remove(5).intValue());
+ assertNull(test.remove(5));
+ verify(test, "mem: 3 stack: 3 2 1 cold: non-resident: 4");
+ assertNull(test.remove(4));
+ verify(test, "mem: 3 stack: 3 2 1 cold: non-resident:");
+ assertNull(test.remove(4));
+ verify(test, "mem: 3 stack: 3 2 1 cold: non-resident:");
+ test.put(4, 40);
+ test.put(5, 50);
+ verify(test, "mem: 4 stack: 5 4 3 2 cold: 5 non-resident: 1");
+ test.getUnchecked(5);
+ test.getUnchecked(2);
+ test.getUnchecked(3);
+ test.getUnchecked(4);
+ verify(test, "mem: 4 stack: 4 3 2 5 cold: 2 non-resident: 1");
+ assertEquals(50, test.remove(5).intValue());
+ verify(test, "mem: 3 stack: 4 3 2 cold: non-resident: 1");
+ assertEquals(20, test.remove(2).intValue());
+ assertFalse(test.containsKey(1));
+ assertNull(test.remove(1));
+ assertFalse(test.containsKey(1));
+ verify(test, "mem: 2 stack: 4 3 cold: non-resident:");
+ test.put(1, 10);
+ test.put(2, 20);
+ verify(test, "mem: 4 stack: 2 1 4 3 cold: non-resident:");
+ test.getUnchecked(1);
+ test.getUnchecked(3);
+ test.getUnchecked(4);
+ verify(test, "mem: 4 stack: 4 3 1 2 cold: non-resident:");
+ assertEquals(10, test.remove(1).intValue());
+ verify(test, "mem: 3 stack: 4 3 2 cold: non-resident:");
+ test.remove(2);
+ test.remove(3);
+ test.remove(4);
+
+ // test clear
+ test.clear();
+ verify(test, "mem: 0 stack: cold: non-resident:");
+
+ // strange situation where there is only a non-resident entry
+ test.put(1, 10);
+ test.put(2, 20);
+ test.put(3, 30);
+ test.put(4, 40);
+ test.put(5, 50);
+ assertTrue(test.containsValue(50));
+ verify(test, "mem: 4 stack: 5 4 3 2 cold: 5 non-resident: 1");
+ test.put(1, 10);
+ verify(test, "mem: 4 stack: 1 5 4 3 2 cold: 1 non-resident: 5");
+ assertFalse(test.containsValue(50));
+ test.remove(2);
+ test.remove(3);
+ test.remove(4);
+ verify(test, "mem: 1 stack: 1 cold: non-resident: 5");
+ assertTrue(test.containsKey(1));
+ test.remove(1);
+ assertFalse(test.containsKey(1));
+ verify(test, "mem: 0 stack: cold: non-resident: 5");
+ assertFalse(test.containsKey(5));
+ assertTrue(test.isEmpty());
+
+ // verify that converting a hot to cold entry will prune the stack
+ test.clear();
+ test.put(1, 10);
+ test.put(2, 20);
+ test.put(3, 30);
+ test.put(4, 40);
+ test.put(5, 50);
+ test.getUnchecked(4);
+ test.getUnchecked(3);
+ verify(test, "mem: 4 stack: 3 4 5 2 cold: 5 non-resident: 1");
+ test.put(6, 60);
+ verify(test, "mem: 4 stack: 6 3 4 5 2 cold: 6 non-resident: 5 1");
+ // this will prune the stack (remove entry 5 as entry 2 becomes cold)
+ test.getUnchecked(6);
+ verify(test, "mem: 4 stack: 6 3 4 cold: 2 non-resident: 5 1");
+ }
+
+ @Test
+ public void testPruneStack() {
+ CacheLIRS<Integer, Integer> test = createCache(5);
+ for (int i = 0; i < 7; i++) {
+ test.put(i, i * 10);
+ }
+ verify(test, "mem: 5 stack: 6 5 4 3 2 1 cold: 6 non-resident: 5 0");
+ test.getUnchecked(4);
+ test.getUnchecked(3);
+ test.getUnchecked(2);
+ verify(test, "mem: 5 stack: 2 3 4 6 5 1 cold: 6 non-resident: 5 0");
+ // this call needs to prune the stack
+ test.remove(1);
+ verify(test, "mem: 4 stack: 2 3 4 6 cold: non-resident: 5 0");
+ test.put(0, 0);
+ test.put(1, 10);
+ // the the stack was not pruned, the following will fail
+ verify(test, "mem: 5 stack: 1 0 2 3 4 cold: 1 non-resident: 6 5");
+ }
+
+ @Test
+ public void testClear() {
+ CacheLIRS<Integer, Integer> test = createCache(40, 10);
+ for (int i = 0; i < 5; i++) {
+ test.put(i, 10 * i, 9);
+ }
+ verify(test, "mem: 36 stack: 4 3 2 1 cold: 4 non-resident: 0");
+ for (Entry<Integer, Integer> e : test.entrySet()) {
+ assertTrue(e.getKey() >= 1 && e.getKey() <= 4);
+ assertTrue(e.getValue() >= 10 && e.getValue() <= 40);
+ }
+ for (int x : test.asMap().values()) {
+ assertTrue(x >= 10 && x <= 40);
+ }
+ for (int x : test.keySet()) {
+ assertTrue(x >= 1 && x <= 4);
+ }
+ assertEquals(40, test.getMaxMemory());
+ assertEquals(10, test.getAverageMemory());
+ assertEquals(36, test.getUsedMemory());
+ assertEquals(4, test.size());
+ assertEquals(3, test.sizeHot());
+ assertEquals(1, test.sizeNonResident());
+ assertFalse(test.isEmpty());
+
+ // changing the limit is not supposed to modify the map
+ test.setMaxMemory(10);
+ assertEquals(10, test.getMaxMemory());
+ test.setMaxMemory(40);
+ test.setAverageMemory(1);
+ assertEquals(1, test.getAverageMemory());
+ test.setAverageMemory(10);
+ verify(test, "mem: 36 stack: 4 3 2 1 cold: 4 non-resident: 0");
+
+ // putAll uses the average memory
+ test.asMap().putAll(test.asMap());
+ verify(test, "mem: 40 stack: 4 3 2 1 cold: non-resident: 0");
+
+ test.clear();
+ verify(test, "mem: 0 stack: cold: non-resident:");
+
+ assertEquals(40, test.getMaxMemory());
+ assertEquals(10, test.getAverageMemory());
+ assertEquals(0, test.getUsedMemory());
+ assertEquals(0, test.size());
+ assertEquals(0, test.sizeHot());
+ assertEquals(0, test.sizeNonResident());
+ assertTrue(test.isEmpty());
+ }
+
+ @Test
+ public void testLimitHot() {
+ CacheLIRS<Integer, Integer> test = createCache(100);
+ for (int i = 0; i < 300; i++) {
+ test.put(i, 10 * i);
+ }
+ assertEquals(100, test.size());
+ assertEquals(99, test.sizeNonResident());
+ assertEquals(93, test.sizeHot());
+ }
+
+ @Test
+ public void testLimitNonResident() {
+ CacheLIRS<Integer, Integer> test = createCache(4);
+ for (int i = 0; i < 20; i++) {
+ test.put(i, 10 * i);
+ }
+ verify(test, "mem: 4 stack: 19 18 17 16 3 2 1 cold: 19 non-resident:
18 17 16");
+ }
+
+ @Test
+ public void testBadHashMethod() {
+ // ensure an 2^n cache size
+ final int size = 4;
+
+ /**
+ * A class with a bad hashCode implementation.
+ */
+ class BadHash {
+ int x;
+
+ BadHash(int x) {
+ this.x = x;
+ }
+
+ @Override
+ public int hashCode() {
+ return (x & 1) * size * 2;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return ((BadHash) o).x == x;
+ }
+
+ @Override
+ public String toString() {
+ return "" + x;
+ }
+
+ }
+
+ CacheLIRS<BadHash, Integer> test = createCache(size * 2);
+ for (int i = 0; i < size; i++) {
+ test.put(new BadHash(i), i);
+ }
+ for (int i = 0; i < size; i++) {
+ if (i % 3 == 0) {
+ assertEquals(i, test.remove(new BadHash(i)).intValue());
+ assertNull(test.remove(new BadHash(i)));
+ }
+ }
+ for (int i = 0; i < size; i++) {
+ if (i % 3 == 0) {
+ assertNull(test.getIfPresent(new BadHash(i)));
+ } else {
+ assertEquals(i, test.getIfPresent(new BadHash(i)).intValue());
+ }
+ }
+ for (int i = 0; i < size; i++) {
+ test.put(new BadHash(i), i);
+ }
+ for (int i = 0; i < size; i++) {
+ if (i % 3 == 0) {
+ assertEquals(i, test.remove(new BadHash(i)).intValue());
+ assertNull(test.remove(new BadHash(i)));
+ }
+ }
+ for (int i = 0; i < size; i++) {
+ if (i % 3 == 0) {
+ assertNull(test.getIfPresent(new BadHash(i)));
+ } else {
+ assertEquals(i, test.getIfPresent(new BadHash(i)).intValue());
+ }
+ }
+ }
+
+ @Test
+ public void testScanResistance() {
+ boolean log = false;
+ int size = 20;
+ // cache size 11 (10 hot, 1 cold)
+ CacheLIRS<Integer, Integer> test = createCache(size / 2 + 1);
+ // init the cache with some dummy entries
+ for (int i = 0; i < size; i++) {
+ test.put(-i, -i * 10);
+ }
+ verify(test, null);
+ // init with 0..9, ensure those are hot entries
+ for (int i = 0; i < size / 2; i++) {
+ test.put(i, i * 10);
+ test.getUnchecked(i);
+ if (log) {
+ System.out.println("get " + i + " -> " + test);
+ }
+ }
+ verify(test, null);
+ // read 0..9, add 10..19 (cold)
+ for (int i = 0; i < size; i++) {
+ Integer x = test.getIfPresent(i);
+ Integer y = test.peek(i);
+ if (i < size / 2) {
+ assertTrue("i: " + i, x != null);
+ assertTrue("i: " + i, y != null);
+ assertEquals(i * 10, x.intValue());
+ assertEquals(i * 10, y.intValue());
+ } else {
+ assertNull(x);
+ assertNull(y);
+ test.put(i, i * 10);
+ // peek should have no effect
+ assertEquals(i * 10, test.peek(i).intValue());
+ }
+ if (log) {
+ System.out.println("get " + i + " -> " + test);
+ }
+ verify(test, null);
+ }
+ // ensure 0..9 are hot, 10..18 are not resident, 19 is cold
+ for (int i = 0; i < size; i++) {
+ Integer x = test.getIfPresent(i);
+ if (i < size / 2 || i == size - 1) {
+ assertTrue("i: " + i, x != null);
+ assertEquals(i * 10, x.intValue());
+ } else {
+ assertNull(x);
+ }
+ verify(test, null);
+ }
+ }
+
+ @Test
+ public void testRandomOperations() {
+ boolean log = false;
+ int size = 10;
+ Random r = new Random(1);
+ for (int j = 0; j < 100; j++) {
+ CacheLIRS<Integer, Integer> test = createCache(size / 2);
+ HashMap<Integer, Integer> good = new HashMap<Integer, Integer>();
+ for (int i = 0; i < 10000; i++) {
+ int key = r.nextInt(size);
+ int value = r.nextInt();
+ switch (r.nextInt(3)) {
+ case 0:
+ if (log) {
+ System.out.println(i + " put " + key + " " + value);
+ }
+ good.put(key, value);
+ test.put(key, value);
+ break;
+ case 1:
+ if (log) {
+ System.out.println(i + " get " + key);
+ }
+ Integer a = good.get(key);
+ Integer b = test.getIfPresent(key);
+ if (a == null) {
+ assertNull(b);
+ } else if (b != null) {
+ assertEquals(a, b);
+ }
+ break;
+ case 2:
+ if (log) {
+ System.out.println(i + " remove " + key);
+ }
+ good.remove(key);
+ test.remove(key);
+ break;
+ }
+ if (log) {
+ System.out.println(" -> " + toString(test));
+ }
+ }
+ verify(test, null);
+ }
+ }
+
+ private static <K, V> String toString(CacheLIRS<K, V> cache) {
+ StringBuilder buff = new StringBuilder();
+ buff.append("mem: " + cache.getUsedMemory());
+ buff.append(" stack:");
+ for (K k : cache.keys(false, false)) {
+ buff.append(' ').append(k);
+ }
+ buff.append(" cold:");
+ for (K k : cache.keys(true, false)) {
+ buff.append(' ').append(k);
+ }
+ buff.append(" non-resident:");
+ for (K k : cache.keys(true, true)) {
+ buff.append(' ').append(k);
+ }
+ return buff.toString();
+ }
+
+ private static <K, V> void verify(CacheLIRS<K, V> cache, String expected) {
+ if (expected != null) {
+ String got = toString(cache);
+ assertEquals(expected, got);
+ }
+ int mem = 0;
+ for (K k : cache.keySet()) {
+ mem += cache.getMemory(k);
+ }
+ assertEquals(mem, cache.getUsedMemory());
+ List<K> stack = cache.keys(false, false);
+ List<K> cold = cache.keys(true, false);
+ List<K> nonResident = cache.keys(true, true);
+ assertEquals(nonResident.size(), cache.sizeNonResident());
+ HashSet<K> hot = new HashSet<K>(stack);
+ hot.removeAll(cold);
+ hot.removeAll(nonResident);
+ assertEquals(hot.size(), cache.sizeHot());
+ assertEquals(hot.size() + cold.size(), cache.size());
+ if (stack.size() > 0) {
+ K lastStack = stack.get(stack.size() - 1);
+ assertTrue(hot.contains(lastStack));
+ }
+ }
+
+ private static <K, V> CacheLIRS<K, V> createCache(int maxElements) {
+ return createCache(maxElements, 1);
+ }
+
+ private static <K, V> CacheLIRS<K, V> createCache(int maxSize, int
averageSize) {
+ return new CacheLIRS<K, V>(null, maxSize, averageSize, 1, 0, null);
+ }
+
+ @Test
+ public void testAsMap() {
+ CacheLIRS<Integer, String> cache = createCache(10, 1);
+ ConcurrentMap<Integer, String> map = cache.asMap();
+ assertNull(map.putIfAbsent(1, "Hello"));
+ assertEquals(1, map.size());
+ assertEquals("Hello", cache.getIfPresent(1));
+ assertEquals("Hello", map.putIfAbsent(1, "Hallo"));
+ assertEquals("Hello", cache.getIfPresent(1));
+ assertEquals("Hello", map.replace(1, "Hallo"));
+ assertEquals("Hallo", cache.getIfPresent(1));
+ assertFalse(map.replace(1, "x", "y"));
+ assertTrue(map.replace(1, "Hallo", "Hi!"));
+ assertFalse(map.remove(1, "Hello"));
+ assertTrue(map.remove(1, "Hi!"));
+ assertEquals(0, map.size());
+
+ map.put(1, "Hello");
+ assertEquals("[1]", map.keySet().toString());
+ assertEquals("[1=Hello]", cache.entrySet().toString());
+ assertEquals("Hello", map.get(1));
+ assertTrue(map.containsKey(1));
+ assertFalse(map.containsKey(2));
+ assertTrue(map.containsValue("Hello"));
+ assertFalse(map.containsValue("Hallo"));
+ assertFalse(map.isEmpty());
+ map.remove(1);
+ assertTrue(map.isEmpty());
+
+ map.put(1, "Hello");
+ map.clear();
+ assertTrue(map.isEmpty());
+ }
+
+}
Modified:
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStoreCacheTest.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStoreCacheTest.java?rev=1556209&r1=1556208&r2=1556209&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStoreCacheTest.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/kernel/KernelNodeStoreCacheTest.java
Tue Jan 7 13:25:40 2014
@@ -71,7 +71,8 @@ public class KernelNodeStoreCacheTest {
int uncachedReads = readTreeWithCleanedCache();
modifyContent();
int cachedReads = readTreeWithCache();
- assertTrue(cachedReads < uncachedReads);
+ assertTrue("cachedReads: " + cachedReads + " uncachedReads: " +
uncachedReads,
+ cachedReads < uncachedReads);
}
/**
@@ -84,7 +85,8 @@ public class KernelNodeStoreCacheTest {
int uncachedReads = readTreeWithCleanedCache();
modifyContent();
int cachedReads = readTreeWithCache();
- assertEquals(cachedReads, uncachedReads);
+ assertEquals("cachedReads: " + cachedReads + " uncachedReads: " +
uncachedReads,
+ cachedReads, uncachedReads);
}
/**
@@ -96,7 +98,8 @@ public class KernelNodeStoreCacheTest {
int uncachedReads = readTreeWithCleanedCache();
modifyContent();
int cachedReads = readTreeWithCache();
- assertTrue(cachedReads < uncachedReads);
+ assertTrue("cachedReads: " + cachedReads + " uncachedReads: " +
uncachedReads,
+ cachedReads < uncachedReads);
}
/**
@@ -113,7 +116,8 @@ public class KernelNodeStoreCacheTest {
int cachedReads = readTreeWithCache();
// System.out.println("Cached reads: " + cachedReads);
- assertTrue(cachedReads < uncachedReads);
+ assertTrue("cachedReads: " + cachedReads + " uncachedReads: " +
uncachedReads,
+ cachedReads < uncachedReads);
}
//---------------------------< internal
>-----------------------------------
