Cache FileStoreAttributeCache per directory

Cache FileStoreAttributeCache entries since looking up FileStore for a
file may be expensive on some platforms.

Implement a simple LRU cache based on ConcurrentHashMap using a simple
long counter to order access to cache entries.

Change-Id: I4881fa938ad2f17712c05da857838073a2fc4ddb
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>
Signed-off-by: Marc Strapetz <marc.strapetz@syntevo.com>
Also-By: Marc Strapetz <marc.strapetz@syntevo.com>

6 files changed, 428 insertions, 1 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/SimpleLruCacheTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/SimpleLruCacheTest.java
new file mode 100644
index 0000000000..5894f7dc5c
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/util/SimpleLruCacheTest.java
@@ -0,0 +1,135 @@
+/*
+ * Copyright (C) 2019, Matthias Sohn <matthias.sohn@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.util;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+public class SimpleLruCacheTest {
+
+	private Path trash;
+
+	private SimpleLruCache<String, String> cache;
+
+
+	@Before
+	public void setup() throws IOException {
+		trash = Files.createTempDirectory("tmp_");
+		cache = new SimpleLruCache<>(100, 0.2f);
+	}
+
+	@Before
+	@After
+	public void tearDown() throws Exception {
+		FileUtils.delete(trash.toFile(),
+				FileUtils.RECURSIVE | FileUtils.SKIP_MISSING);
+	}
+
+	@Test
+	public void testPutGet() {
+		cache.put("a", "A");
+		cache.put("z", "Z");
+		assertEquals("A", cache.get("a"));
+		assertEquals("Z", cache.get("z"));
+	}
+
+	@Test(expected = IllegalArgumentException.class)
+	public void testPurgeFactorTooLarge() {
+		cache.configure(5, 1.01f);
+	}
+
+	@Test(expected = IllegalArgumentException.class)
+	public void testPurgeFactorTooLarge2() {
+		cache.configure(5, 100);
+	}
+
+	@Test(expected = IllegalArgumentException.class)
+	public void testPurgeFactorTooSmall() {
+		cache.configure(5, 0);
+	}
+
+	@Test(expected = IllegalArgumentException.class)
+	public void testPurgeFactorTooSmall2() {
+		cache.configure(5, -100);
+	}
+
+	@Test
+	public void testGetMissing() {
+		assertEquals(null, cache.get("a"));
+	}
+
+	@Test
+	public void testPurge() {
+		for (int i = 0; i < 101; i++) {
+			cache.put("a" + i, "a" + i);
+		}
+		assertEquals(80, cache.size());
+		assertNull(cache.get("a0"));
+		assertNull(cache.get("a20"));
+		assertNotNull(cache.get("a21"));
+		assertNotNull(cache.get("a99"));
+	}
+
+	@Test
+	public void testConfigure() {
+		for (int i = 0; i < 100; i++) {
+			cache.put("a" + i, "a" + i);
+		}
+		assertEquals(100, cache.size());
+		cache.configure(10, 0.3f);
+		assertEquals(7, cache.size());
+		assertNull(cache.get("a0"));
+		assertNull(cache.get("a92"));
+		assertNotNull(cache.get("a93"));
+		assertNotNull(cache.get("a99"));
+	}
+}
diff --git a/org.eclipse.jgit/.settings/.api_filters b/org.eclipse.jgit/.settings/.api_filters
index 8277735e24..7aa7301b03 100644
--- a/org.eclipse.jgit/.settings/.api_filters
+++ b/org.eclipse.jgit/.settings/.api_filters
@@ -240,6 +240,14 @@
             </message_arguments>
         </filter>
     </resource>
+    <resource path="src/org/eclipse/jgit/util/SimpleLruCache.java" type="org.eclipse.jgit.util.SimpleLruCache">
+        <filter id="1109393411">
+            <message_arguments>
+                <message_argument value="5.1.9"/>
+                <message_argument value="org.eclipse.jgit.util.SimpleLruCache"/>
+            </message_arguments>
+        </filter>
+    </resource>
     <resource path="src/org/eclipse/jgit/util/Stats.java" type="org.eclipse.jgit.util.Stats">
         <filter id="1109393411">
             <message_arguments>
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 6ac6955f06..290a0a28ef 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -390,6 +390,7 @@ invalidPathContainsSeparator=Invalid path (contains separator ''{0}''): {1}
 invalidPathPeriodAtEndWindows=Invalid path (period at end is ignored by Windows): {0}
 invalidPathSpaceAtEndWindows=Invalid path (space at end is ignored by Windows): {0}
 invalidPathReservedOnWindows=Invalid path (''{0}'' is reserved on Windows): {1}
+invalidPurgeFactor=Invalid purgeFactor {0}, values have to be in range between 0 and 1
 invalidRedirectLocation=Invalid redirect location {0} -> {1}
 invalidRefAdvertisementLine=Invalid ref advertisement line: ''{1}''
 invalidReflogRevision=Invalid reflog revision: {0}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
index 38c063d071..00aaa42b47 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java
@@ -451,6 +451,7 @@ public class JGitText extends TranslationBundle {
 	/***/ public String invalidPathPeriodAtEndWindows;
 	/***/ public String invalidPathSpaceAtEndWindows;
 	/***/ public String invalidPathReservedOnWindows;
+	/***/ public String invalidPurgeFactor;
 	/***/ public String invalidRedirectLocation;
 	/***/ public String invalidRefAdvertisementLine;
 	/***/ public String invalidReflogRevision;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/FS.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/FS.java
index c30be36dde..19c04619df 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/util/FS.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/FS.java
@@ -230,6 +230,9 @@ public abstract class FS {
 
 		private static final Map<FileStore, FileStoreAttributes> attributeCache = new ConcurrentHashMap<>();
 
+		private static final SimpleLruCache<Path, FileStoreAttributes> attrCacheByPath = new SimpleLruCache<>(
+				100, 0.2f);
+
 		private static AtomicBoolean background = new AtomicBoolean();
 
 		private static Map<FileStore, Lock> locks = new ConcurrentHashMap<>();
@@ -246,6 +249,26 @@ public abstract class FS {
 				.ofMillis(10);
 
 		/**
+		 * Configures size and purge factor of the path-based cache for file
+		 * system attributes. Caching of file system attributes avoids recurring
+		 * lookup of @{code FileStore} of files which may be expensive on some
+		 * platforms.
+		 *
+		 * @param maxSize
+		 *            maximum size of the cache, default is 100
+		 * @param purgeFactor
+		 *            when the size of the map reaches maxSize the oldest
+		 *            entries will be purged to free up some space for new
+		 *            entries, {@code purgeFactor} is the fraction of
+		 *            {@code maxSize} to purge when this happens
+		 * @since 5.1.9
+		 */
+		public static void configureAttributesPathCache(int maxSize,
+				float purgeFactor) {
+			FileStoreAttributes.attrCacheByPath.configure(maxSize, purgeFactor);
+		}
+
+		/**
 		 * Get the FileStoreAttributes for the given FileStore
 		 *
 		 * @param path
@@ -255,7 +278,13 @@ public abstract class FS {
 		public static FileStoreAttributes get(Path path) {
 			path = path.toAbsolutePath();
 			Path dir = Files.isDirectory(path) ? path : path.getParent();
-			return getFileStoreAttributes(dir);
+			FileStoreAttributes cached = attrCacheByPath.get(dir);
+			if (cached != null) {
+				return cached;
+			}
+			FileStoreAttributes attrs = getFileStoreAttributes(dir);
+			attrCacheByPath.put(dir, attrs);
+			return attrs;
 		}
 
 		private static FileStoreAttributes getFileStoreAttributes(Path dir) {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java
new file mode 100644
index 0000000000..709d9ee73d
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/SimpleLruCache.java
@@ -0,0 +1,253 @@
+/*
+ * Copyright (C) 2019, Marc Strapetz <marc.strapetz@syntevo.com>
+ * Copyright (C) 2019, Matthias Sohn <matthias.sohn@sap.com>
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.util;
+
+import java.text.MessageFormat;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+
+import org.eclipse.jgit.annotations.NonNull;
+import org.eclipse.jgit.internal.JGitText;
+
+/**
+ * Simple limited size cache based on ConcurrentHashMap purging entries in LRU
+ * order when reaching size limit
+ *
+ * @param <K>
+ *            the type of keys maintained by this cache
+ * @param <V>
+ *            the type of mapped values
+ *
+ * @since 5.1.9
+ */
+public class SimpleLruCache<K, V> {
+
+	private static class Entry<K, V> {
+
+		private final K key;
+
+		private final V value;
+
+		// pseudo clock timestamp of the last access to this entry
+		private volatile long lastAccessed;
+
+		private long lastAccessedSorting;
+
+		Entry(K key, V value, long lastAccessed) {
+			this.key = key;
+			this.value = value;
+			this.lastAccessed = lastAccessed;
+		}
+
+		void copyAccessTime() {
+			lastAccessedSorting = lastAccessed;
+		}
+
+		@SuppressWarnings("nls")
+		@Override
+		public String toString() {
+			return "Entry [lastAccessed=" + lastAccessed + ", key=" + key
+					+ ", value=" + value + "]";
+		}
+	}
+
+	private Lock lock = new ReentrantLock();
+
+	private Map<K, Entry<K,V>> map = new ConcurrentHashMap<>();
+
+	private volatile int maximumSize;
+
+	private int purgeSize;
+
+	// pseudo clock to implement LRU order of access to entries
+	private volatile long time = 0L;
+
+	private static void checkPurgeFactor(float purgeFactor) {
+		if (purgeFactor <= 0 || purgeFactor >= 1) {
+			throw new IllegalArgumentException(
+					MessageFormat.format(JGitText.get().invalidPurgeFactor,
+							Float.valueOf(purgeFactor)));
+		}
+	}
+
+	private static int purgeSize(int maxSize, float purgeFactor) {
+		return (int) ((1 - purgeFactor) * maxSize);
+	}
+
+	/**
+	 * Create a new cache
+	 *
+	 * @param maxSize
+	 *            maximum size of the cache, to reduce need for synchronization
+	 *            this is not a hard limit. The real size of the cache could be
+	 *            slightly above this maximum if multiple threads put new values
+	 *            concurrently
+	 * @param purgeFactor
+	 *            when the size of the map reaches maxSize the oldest entries
+	 *            will be purged to free up some space for new entries,
+	 *            {@code purgeFactor} is the fraction of {@code maxSize} to
+	 *            purge when this happens
+	 */
+	public SimpleLruCache(int maxSize, float purgeFactor) {
+		checkPurgeFactor(purgeFactor);
+		this.maximumSize = maxSize;
+		this.purgeSize = purgeSize(maxSize, purgeFactor);
+	}
+
+	/**
+	 * Returns the value to which the specified key is mapped, or {@code null}
+	 * if this map contains no mapping for the key.
+	 *
+	 * <p>
+	 * More formally, if this cache contains a mapping from a key {@code k} to a
+	 * value {@code v} such that {@code key.equals(k)}, then this method returns
+	 * {@code v}; otherwise it returns {@code null}. (There can be at most one
+	 * such mapping.)
+	 *
+	 * @param key
+	 *            the key
+	 *
+	 * @throws NullPointerException
+	 *             if the specified key is null
+	 *
+	 * @return value mapped for this key, or {@code null} if no value is mapped
+	 */
+	public V get(Object key) {
+		Entry<K, V> entry = map.get(key);
+		if (entry != null) {
+			entry.lastAccessed = ++time;
+			return entry.value;
+		}
+		return null;
+	}
+
+	/**
+	 * Maps the specified key to the specified value in this cache. Neither the
+	 * key nor the value can be null.
+	 *
+	 * <p>
+	 * The value can be retrieved by calling the {@code get} method with a key
+	 * that is equal to the original key.
+	 *
+	 * @param key
+	 *            key with which the specified value is to be associated
+	 * @param value
+	 *            value to be associated with the specified key
+	 * @return the previous value associated with {@code key}, or {@code null}
+	 *         if there was no mapping for {@code key}
+	 * @throws NullPointerException
+	 *             if the specified key or value is null
+	 */
+	public V put(@NonNull K key, @NonNull V value) {
+		map.put(key, new Entry<>(key, value, ++time));
+		if (map.size() > maximumSize) {
+			purge();
+		}
+		return value;
+	}
+
+	/**
+	 * Returns the current size of this cache
+	 *
+	 * @return the number of key-value mappings in this cache
+	 */
+	public int size() {
+		return map.size();
+	}
+
+	/**
+	 * Reconfigures the cache. If {@code maxSize} is reduced some entries will
+	 * be purged.
+	 *
+	 * @param maxSize
+	 *            maximum size of the cache
+	 *
+	 * @param purgeFactor
+	 *            when the size of the map reaches maxSize the oldest entries
+	 *            will be purged to free up some space for new entries,
+	 *            {@code purgeFactor} is the fraction of {@code maxSize} to
+	 *            purge when this happens
+	 */
+	public void configure(int maxSize, float purgeFactor) {
+		lock.lock();
+		try {
+			checkPurgeFactor(purgeFactor);
+			this.maximumSize = maxSize;
+			this.purgeSize = purgeSize(maxSize, purgeFactor);
+			if (map.size() >= maximumSize) {
+				purge();
+			}
+		} finally {
+			lock.unlock();
+		}
+	}
+
+	private void purge() {
+		// don't try to compete if another thread already has the lock
+		if (lock.tryLock()) {
+			try {
+				List<Entry> entriesToPurge = new ArrayList<>(map.values());
+				// copy access times to avoid other threads interfere with
+				// sorting
+				for (Entry e : entriesToPurge) {
+					e.copyAccessTime();
+				}
+				Collections.sort(entriesToPurge,
+						Comparator.comparingLong(o -> -o.lastAccessedSorting));
+				for (int index = purgeSize; index < entriesToPurge
+						.size(); index++) {
+					map.remove(entriesToPurge.get(index).key);
+				}
+			} finally {
+				lock.unlock();
+			}
+		}
+	}
+}