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>

3 files changed, 284 insertions, 1 deletions

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();
+			}
+		}
+	}
+}